1
$\begingroup$

I am wondering why data fragmentation is a problem on main memory.

On a software level, virtual addresses are used anyway. So why can one address space not be split up into multiple segments, like a hard disk might do? I don't see how the performance would be affected, as the time needed to access memory addresses does not vary. Is this just a limit of the MMU?

In other words, my question is why does a process need continuous memory segments? For example:

Table, 1 Row, 5 equally big cells. Cell 1 is allocated to Process A, Cell 2 and 4 are free (not allocated), Cell 3 is allocated to Process B, Cell 4 is allocated to Process C.

Process D requests a memory block that could fit into the two free segments, if the block were split into two pieces. Why can't this be done?

Table, 1 Row, 5 cells. Cell 1 is allocated to Process A, Cell 2 and 4 are allocated to Process D (which got split/fragmented to fit), Cell 3 is allocated to Process B, Cell 4 is allocated to Process C.

It would be great if you could add a source so I could read more about this topic, if you have one.

$\endgroup$
  • 2
    $\begingroup$ Who says main memory is not fragmented? If so we wouldn't need pages, the MMU, TLBs and so on. $\endgroup$ – Paebbels Dec 1 '15 at 21:32
1
$\begingroup$

[Disclaimer : I probably don't actually understand the question]

-DRAM access time is not constant, as memory is physically arranged in rows, columns, banks. It is beneficial to limit fragmentation of actual memory.

-On multi-cpus hardware, memory can also have different access times ("NUMA"), so the OS needs to avoid putting programs at random.

-The physical address range can be not contiguous, it may be hidden by hardware mechanisms, or managed by the OS. For example a computer equipped with 8 slots for 4GB memory modules, can use a fixed 4GB address for each module, and if 1GB modules are installed, there are 3GB "holes" every 4GB.

MMUs can effectively hide to application software how memory is allocated. Each page (page size is often 4kB) can be mapped to actual memory, only on disk, or unitialised, several pages initialised to zero can be allocated to the same physical memory, several applications can share the same physical memory for code and nonmodified data...


So ? When a process does a malloc() for a 1MB array, the stdlib/OS will eventually return a pointer to a 1MB area of virtual memory. It is typically split into around 256 pages of 4kB. These 256 pages may be placed at random in the physical RAM, or maybe don't even exist until the process eventually accesses them. The OS maintains memory allocation structures for identifying which memory is used by what, and page tables for the MMU to perform virtual to physical translations.

(Note : Pages are not always 4kB on all architectures, some MMUs expect software management of virtual to physical translation instead of directly accessing tables, a.k.a. "tablewalking")

$\endgroup$
  • $\begingroup$ Thank you for your answer, @TEMLIB . Please see the updated question. Sorry for not giving an example ;) $\endgroup$ – PStigerID Nov 29 '15 at 19:08
  • $\begingroup$ OK, I didn't know that access time to different memory addresses is not constant. Nevertheless, there can't be a big difference, like on a HDD. Wouldn't compressing take longer than taking that none-uniform access time into consideration? I still don't see a good reason not to do what I did in my example... $\endgroup$ – PStigerID Nov 29 '15 at 19:26
2
$\begingroup$

According to https://lwn.net/Articles/211505/, what you imagine should be done by the OS, is already done:

Since Linux is a virtual memory system, fragmentation normally is not a problem; physically scattered memory can be made virtually contiguous by way of the page tables.

There are limits to this, as hardware devices may request contiguous hardware memory, and this creates memory holes (at least for hardware devices).

Another limitation is that doing all memory allocations and deallocations through page tables is inefficient. Setting up new page table entries takes longer than managing allocations through software and, if the page size is 4K, only works for allocations that are a multiple of 4K. Therefore the malloc and free glibc calls first allocate 4K blocks through mmap (using page tables) and manage this memory. They divide it into smaller contiguous memory areas and return them when a malloc call requests a small chunk of memory. Algorithms to reduce memory fragmentation of software-managed memory are for example the Buddy memory allocator.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.