메모리 조각화 란 무엇입니까?

메모리 조각화 란 무엇입니까?

---

C ++ 동적 메모리 할당의 맥락에서 "메모리 조각화"라는 용어가 몇 번 사용되었다고 들었습니다. 메모리 조각화를 처리하는 방법에 대한 몇 가지 질문을 찾았지만 그 자체를 다루는 직접적인 질문을 찾을 수 없습니다. 그래서:

• 메모리 조각화 란 무엇입니까?
• 메모리 조각화가 응용 프로그램에 문제가 있는지 어떻게 알 수 있습니까? 어떤 종류의 프로그램이 가장 고통받을까요?
• 메모리 조각화를 처리하는 좋은 일반적인 방법은 무엇입니까?

또한:

• 동적 할당을 사용하면 메모리 조각화가 많이 발생할 수 있다고 들었습니다. 이것이 사실입니까? C ++의 맥락에서 모든 표준 컨테이너 (std :: string, std :: vector 등)가 동적 메모리 할당을 사용한다는 것을 알고 있습니다. 프로그램 전체에서 (특히 std :: string) 사용되는 경우 메모리 조각화가 문제가 될 가능성이 더 큽니까?
• STL이 많은 응용 프로그램에서 메모리 조각화를 어떻게 처리 할 수 ​​있습니까?

---

사용 가능한 메모리의 "큰"(32 바이트) 확장이 있다고 상상해보십시오.

----------------------------------
|                                |
----------------------------------

이제 그 중 일부를 할당하십시오 (5 개의 할당).

----------------------------------
|aaaabbccccccddeeee              |
----------------------------------

이제 첫 번째 네 개의 할당을 해제하고 다섯 번째는 할당하지 마십시오.

----------------------------------
|              eeee              |
----------------------------------

이제 16 바이트를 할당하십시오. 거의 두 배나 많은 공짜가 있어도 할 수 없습니다.

가상 메모리가있는 시스템에서는 조각화가 생각보다 문제가 되지 않습니다 . 큰 할당 은 물리적 주소 공간이 아닌 가상 주소 공간 에서만 인접해야하기 때문 입니다. 예를 들어, 페이지 크기가 2 바이트 인 가상 메모리가 있으면 아무런 문제없이 16 바이트를 할당 할 수 있습니다. 실제 메모리는 다음과 같습니다.

----------------------------------
|ffffffffffffffeeeeff            |
----------------------------------

반면 가상 메모리 (훨씬 더 큰)는 다음과 같습니다.

------------------------------------------------------...
|              eeeeffffffffffffffff                   
------------------------------------------------------...

메모리 조각화의 고전적인 증상은 큰 블록을 할당하려고 시도하는데 메모리가 충분하지 않은 것처럼 보일 수는 없다는 것입니다. 또 다른 가능한 결과는 프로세스가 메모리를 OS로 다시 릴리스 할 수 없다는 것입니다 (이들 블록은 현재 대부분 사용되지 않더라도 OS에서 할당 한 모든 블록에서 여전히 사용중인 객체가 있기 때문에).

C ++에서 메모리 조각화를 방지하는 전술은 크기 및 / 또는 예상 수명에 따라 다른 영역의 객체를 할당하여 작동합니다. 따라서 많은 객체를 생성하고 나중에 모두 함께 파괴하려면 메모리 풀에서 할당하십시오. 당신이 그들 사이에 다른 할당은 풀에서 온 것이 아니므로 메모리에서 그들 사이에 위치하지 않으므로 결과적으로 메모리가 조각화되지 않습니다.

일반적으로 프로그램이 오래 실행되고 많은 할당 및 해제를 수행하지 않는 한 크게 걱정할 필요가 없습니다. 가장 위험에 처한 단기 및 장기 개체의 혼합이있을 때에도 malloc도움을주기 위해 최선을 다할 것입니다. 기본적으로 프로그램에 할당 실패가 발생하거나 예기치 않게 시스템의 메모리가 부족해질 때까지이를 무시하십시오 (환경 설정을 위해 테스트에서 캐치하십시오!).

표준 라이브러리는 메모리를 할당하는 다른 것보다 나쁘지 않으며 표준 컨테이너에는 모두 Alloc필요한 경우 할당 전략을 미세 조정하는 데 사용할 수 있는 템플릿 매개 변수가 있습니다.

---

메모리 조각화 란 무엇입니까?

메모리 조각화는 대부분의 메모리가 많은 비 연속 블록 또는 청크에 할당되어 총 메모리의 상당 부분이 할당되지 않지만 대부분의 일반적인 시나리오에서는 사용할 수없는 상태입니다. 이로 인해 메모리 부족 예외 또는 할당 오류가 발생합니다 (예 : malloc은 널을 리턴 함).

이것에 대해 생각하는 가장 쉬운 방법 은 다양한 크기의 그림 을 올려야 하는 큰 빈 벽이 있다고 상상하는 것 입니다. 각 사진은 특정 크기를 차지하며 분명히 작은 조각으로 나눌 수 없습니다. 벽에 빈 자리, 그림의 크기가 필요합니다. 그렇지 않으면 그림을 올릴 수 없습니다. 이제 벽에 그림을 걸기 시작하고 정렬 방법에 신경 쓰지 않으면 곧 부분적으로 그림으로 덮여있는 벽으로 끝나고 빈 자리가 있더라도 대부분의 새로운 그림은 적합하지 않습니다. 사용 가능한 지점보다 크기 때문입니다. 당신은 여전히 ​​작은 그림을 걸 수 있지만 대부분의 사진은 적합하지 않습니다. 따라서 더 많은 공간을 확보하기 위해 이미 벽에있는 것을 다시 정리 (컴팩트)해야합니다.

이제 벽이 당신의 (힙) 기억이고 그림들이 물체라고 상상해보십시오. 그것은 기억 조각화입니다.

메모리 조각화가 응용 프로그램에 문제가 있는지 어떻게 알 수 있습니까? 어떤 종류의 프로그램이 가장 고통받을까요?

메모리 조각화를 처리 할 수 ​​있다는 신호는 특히 사용 된 메모리의 백분율이 높을 때 (하지만 아직 모든 메모리를 다 사용하지는 않았을 때) 많은 할당 오류가 발생하는 경우 기술적으로 충분한 공간이 있어야합니다. 할당하려는 객체에 대해

메모리가 많이 조각화되면 메모리 할당자가 새 객체에 적합한 공간을 찾기 위해 더 많은 작업을 수행해야하기 때문에 메모리 할당이 더 오래 걸릴 수 있습니다. 결과적으로 많은 메모리 할당이있는 경우 (메모리 조각화로 인해 발생했을 수 있음) 할당 시간이 눈에 띄게 지연 될 수 있습니다.

메모리 조각화를 처리하는 좋은 일반적인 방법은 무엇입니까?

메모리 할당에 좋은 알고리즘을 사용하십시오. 많은 작은 개체에 메모리를 할당하는 대신 작은 개체의 연속 배열에 메모리를 미리 할당하십시오. 메모리 할당시 약간의 낭비가 발생하여 성능이 저하 될 수 있으며 메모리 조각화를 처리해야하는 번거 로움을 덜 수 있습니다.

---

Memory fragmentation is the same concept as disk fragmentation: it refers to space being wasted because the areas in use are not packed closely enough together.

Suppose for a simple toy example that you have ten bytes of memory:

 |   |   |   |   |   |   |   |   |   |   |
   0   1   2   3   4   5   6   7   8   9

Now let's allocate three three-byte blocks, name A, B, and C:

 | A | A | A | B | B | B | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Now deallocate block B:

 | A | A | A |   |   |   | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Now what happens if we try to allocate a four-byte block D? Well, we have four bytes of memory free, but we don't have four contiguous bytes of memory free, so we can't allocate D! This is inefficient use of memory, because we should have been able to store D, but we were unable to. And we can't move C to make room, because very likely some variables in our program are pointing at C, and we can't automatically find and change all of these values.

How do you know it's a problem? Well, the biggest sign is that your program's virtual memory size is considerably larger than the amount of memory you're actually using. In a real-world example, you would have many more than ten bytes of memory, so D would just get allocated starting a byte 9, and bytes 3-5 would remain unused unless you later allocated something three bytes long or smaller.

In this example, 3 bytes is not a whole lot to waste, but consider a more pathological case where two allocations of a a couple of bytes are, for example, ten megabytes apart in memory, and you need to allocate a block of size 10 megabytes + 1 byte. You have to go ask the OS for over ten megabytes more virtual memory to do that, even though you're just one byte shy of having enough space already.

How do you prevent it? The worst cases tend to arise when you frequently create and destroy small objects, since that tends to produce a "swiss cheese" effect with many small objects separated by many small holes, making it impossible to allocate larger objects in those holes. When you know you're going to be doing this, an effective strategy is to pre-allocate a large block of memory as a pool for your small objects, and then manually manage the creation of the small objects within that block, rather than letting the default allocator handle it.

In general, the fewer allocations you do, the less likely memory is to get fragmented. However, STL deals with this rather effectively. If you have a string which is using the entirety of its current allocation and you append one character to it, it doesn't simply re-allocate to its current length plus one, it doubles its length. This is a variation on the "pool for frequent small allocations" strategy. The string is grabbing a large chunk of memory so that it can deal efficiently with repeated small increases in size without doing repeated small reallocations. All STL containers in fact do this sort of thing, so generally you won't need to worry too much about fragmentation caused by automatically-reallocating STL containers.

Although of course STL containers don't pool memory between each other, so if you're going to create many small containers (rather than a few containers that get resized frequently) you may have to concern yourself with preventing fragmentation in the same way you would for any frequently-created small objects, STL or not.

---

• What is memory fragmentation?

Memory fragmentation is the problem of memory becoming unusable even though it is theoretically available. There are two kinds of fragmentation: internal fragmentation is memory that is allocated but cannot be used (e.g. when memory is allocated in 8 byte chunks but the program repeatedly does single allications when it needs only 4 bytes). external fragmentation is the problem of free memory becoming divided into many small chunks so that large allocation requests cannot be met although there is enough overall free memory.

• How can I tell if memory fragmentation is a problem for my application? What kind of program is most likely to suffer?

memory fragmentation is a problem if your program uses much more system memory than its actual paylod data would require (and you've ruled out memory leaks).

• What are good common ways to deal with memory fragmentation?

Use a good memory allocator. IIRC, those that use a "best fit" strategy are generally much superior at avoiding fragmentation, if a little slower. However, it has also been shown that for any allocation strategy, there are pathological worst cases. Fortunately, the typical allocation patterns of most applications are actually relatively benign for the allocators to handle. There's a bunch of papers out there if you're interested in the details:

• Paul R. Wilson, Mark S. Johnstone, Michael Neely and David Boles. Dynamic Storage Allocation: A Survey and Critical Review. In Proceedings of the 1995 International Workshop on Memory Management, Springer Verlag LNCS, 1995
• Mark S.Johnstone, Paul R. Wilson. The Memory Fragmentation Problem: Solved? In ACM SIG-PLAN Notices, volume 34 No. 3, pages 26-36, 1999
• M.R. Garey, R.L. Graham and J.D. Ullman. Worst-Case analysis of memory allocation algorithms. In Fourth Annual ACM Symposium on the Theory of Computing, 1972

---

Update:
Google TCMalloc: Thread-Caching Malloc
It has been found that it is quite good at handling fragmentation in a long running process.

---

I have been developing a server application that had problems with memory fragmentation on HP-UX 11.23/11.31 ia64.

It looked like this. There was a process that made memory allocations and deallocations and ran for days. And even though there were no memory leaks memory consumption of the process kept increasing.

About my experience. On HP-UX it is very easy to find memory fragmentation using HP-UX gdb. You set a break-point and when you hit it you run this command: info heap and see all memory allocations for the process and the total size of heap. Then your continue your program and then some time later your again hit the break-point. You do again info heap. If the total size of heap is bigger but the number and the size of separate allocations are the same then it is likely that you have memory allocation problems. If necessary do this check few fore times.

My way of improving the situation was this. After I had done some analysis with HP-UX gdb I saw that memory problems were caused by the fact that I used std::vector for storing some types of information from a database. std::vector requires that its data must be kept in one block. I had a few containers based on std::vector. These containers were regularly recreated. There were often situations when new records were added to the database and after that the containers were recreated. And since the recreated containers were bigger their did not fit into available blocks of free memory and the runtime asked for a new bigger block from the OS. As a result even though there were no memory leaks the memory consumption of the process grew. I improved the situation when I changed the containers. Instead of std::vector I started using std::deque which has a different way of allocating memory for data.

I know that one of ways to avoid memory fragmentation on HP-UX is to use either Small Block Allocator or use MallocNextGen. On RedHat Linux the default allocator seems to handle pretty well allocating of a lot of small blocks. On Windows there is Low-fragmentation Heap and it adresses the problem of large number of small allocations.

My understanding is that in an STL-heavy application you have first to identify problems. Memory allocators (like in libc) actually handle the problem of a lot of small allocations, which is typical for std::string (for instance in my server application there are lots of STL strings but as I see from running info heap they are not causing any problems). My impression is that you need to avoid frequent large allocations. Unfortunately there are situations when you can't avoid them and have to change your code. As I say in my case I improved the situation when switched to std::deque. If you identify your memory fragmention it might be possible to talk about it more precisely.

---

Memory fragmentation is most likely to occur when you allocate and deallocate many objects of varying sizes. Suppose you have the following layout in memory:

obj1 (10kb) | obj2(20kb) | obj3(5kb) | unused space (100kb)

Now, when obj2 is released, you have 120kb of unused memory, but you cannot allocate a full block of 120kb, because the memory is fragmented.

Common techniques to avoid that effect include ring buffers and object pools. In the context of the STL, methods like std::vector::reserve() can help.

---

A very detailed answer on memory fragmentation can be found here.

http://library.softwareverify.com/memory-fragmentation-your-worst-nightmare/

This is the culmination of 11 years of memory fragmentation answers I have been providing to people asking me questions about memory fragmentation at softwareverify.com

---

What is memory fragmentation?

When your app uses dynamic memory, it allocates and frees chunks of memory. In the beginning, the whole memory space of your app is one contiguous block of free memory. However, when you allocate and free blocks of different size, the memory starts to get fragmented, i.e. instead of a big contiguous free block and a number of contiguous allocated blocks, there will be a allocated and free blocks mixed up. Since the free blocks have limited size, it is difficult to reuse them. E.g. you may have 1000 bytes of free memory, but can't allocate memory for a 100 byte block, because all the free blocks are at most 50 bytes long.

Another, unavoidable, but less problematic source of fragmentation is that in most architectures, memory addresses must be aligned to 2, 4, 8 etc. byte boundaries (i.e. the addresses must be multiples of 2, 4, 8 etc.) This means that even if you have e.g. a struct containing 3 char fields, your struct may have a size of 12 instead of 3, due to the fact that each field is aligned to a 4-byte boundary.

How can I tell if memory fragmentation is a problem for my application? What kind of program is most likely to suffer?

The obvious answer is that you get an out of memory exception.

Apparently there is no good portable way to detect memory fragmentation in C++ apps. See this answer for more details.

What are good common ways to deal with memory fragmentation?

It is difficult in C++, since you use direct memory addresses in pointers, and you have no control over who references a specific memory address. So rearranging the allocated memory blocks (the way the Java garbage collector does) is not an option.

A custom allocator may help by managing the allocation of small objects in a bigger chunk of memory, and reusing the free slots within that chunk.

---

This is a super-simplified version for dummies.

As objects get created in memory, they get added to the end of the used portion in memory.

If an object that is not at the end of the used portion of memory is deleted, meaning this object was in between 2 other objects, it will create a "hole".

This is what's called fragmentation.

---

When you want to add an item on the heap what happens is that the computer has to do a search for space to fit that item. That's why dynamic allocations when not done on a memory pool or with a pooled allocator can "slow" things down. For a heavy STL application if you're doing multi-threading there is the Hoard allocator or the TBB Intel version.

Now, when memory is fragmented two things can occur:

1. There will have to be more searches to find a good space to stick "large" objects. That is, with many small objects scattered about finding a nice contigous chunk of memory could under certain conditions be difficult (these are extreme.)
2. Memory is not some easily read entity. Processors are limited to how much they can hold and where. They do this by swapping pages if an item they need is one place but the current addresses are another. If you are constantly having to swap pages, processing can slow down (again, extreme scenarios where this impacts performance.) See this posting on virtual memory.

---

Memory fragmentation occurs because memory blocks of different sizes are requested. Consider a buffer of 100 bytes. You request two chars, then an integer. Now you free the two chars, then request a new integer- but that integer can't fit in the space of the two chars. That memory cannot be re-used because it is not in a large enough contiguous block to re-allocate. On top of that, you've invoked a lot of allocator overhead for your chars.

Essentially, memory only comes in blocks of a certain size on most systems. Once you split these blocks up, they cannot be rejoined until the whole block is freed. This can lead to whole blocks in use when actually only a small part of the block is in use.

The primary way to reduce heap fragmentation is to make larger, less frequent allocations. In the extreme, you can use a managed heap that is capable of moving objects, at least, within your own code. This completely eliminates the problem - from a memory perspective, anyway. Obviously moving objects and such has a cost. In reality, you only really have a problem if you are allocating very small amounts off the heap often. Using contiguous containers (vector, string, etc) and allocating on the stack as much as humanly possible (always a good idea for performance) is the best way to reduce it. This also increases cache coherence, which makes your application run faster.

What you should remember is that on a 32bit x86 desktop system, you have an entire 2GB of memory, which is split into 4KB "pages" (pretty sure the page size is the same on all x86 systems). You will have to invoke some omgwtfbbq fragmentation to have a problem. Fragmentation really is an issue of the past, since modern heaps are excessively large for the vast majority of applications, and there's a prevalence of systems that are capable of withstanding it, such as managed heaps.

참고URL : https://stackoverflow.com/questions/3770457/what-is-memory-fragmentation