OSDev.org https://forum.osdev.org/ |
|
Fragmentation in slab/LFH vs buddy allocator? https://forum.osdev.org/viewtopic.php?f=15&t=30717 |
Page 1 of 1 |
Author: | simeonz [ Sat Aug 20, 2016 12:47 am ] |
Post subject: | Fragmentation in slab/LFH vs buddy allocator? |
I am reading on various OS topics. I am examining the trade-offs of general-purpose sub-page allocator designs. Here is what I have so far:
Drawbacks/advantages (IMHO):
Note that I am not assuming stationary distribution, because every reasonable allocator manages that somehow. Why do you think was the slab allocator chosen over the buddy allocator in the Linux kernel and for the Windows heap? Do you think it was performance based decision, or does it offer improvements with respect to fragmentation (which I fail to see.) |
Author: | ~ [ Sat Aug 20, 2016 2:14 pm ] |
Post subject: | Re: Fragmentation in slab/LFH vs buddy allocator? |
Memory managers for paged and multitasked environments are no different to a file system. Memory management was originally thought to serve a single process and at most several threads of a single process. But with multitasking comes the need to use paging (virtual addresses) to provide all of the processes, an address space that they can access contiguously from memory pieces (pages) that are expected to be physically apart in a random order. If you implement a single-process, single-thread OS, you could assign all memory to that process without worrying too much about fragmentation. But think about the fact that even a single process running would always end up seeing memory fragmentation if it ever allocates memory dynamically. It would always need to keep track of free, reserved and used memory chunks, and if it does many things, it would always end up freeing buffers, objects or structures that are in memory, and it would always end up freeing them in random order, according to the processes it needs to do, so it's in that randomness in freeing memory that the process would always end up seeing memory fragmentation and the need to manage it, if it ever allocates and frees memory dynamically (the simplest being a single-tasking OS with a bit map to keep track of free 65536-byte segments). Instead of having a disk share its space between many files and directories whose sectors are normally scattered in a random order but linked somehow to retrieve them, we do the same in memory. We also align data in pages, and we apply access and execution privileges just like an advanced file system. Since implementing a paged and multitasking-capable memory manager is basically the same as implementing an on-disk file system, fragmentation is impossible to avoid in practice. Actually, we need to deliberately allocate pages in a random order in memory to prove to ourselves that our memory manager is properly implemented and that it's actually able to easily and efficiently find free and reserved pages no matter how fragmented they are (as they would, for example, when running TV applications, web browsers with dozens of tabs and windows, text editors, compilers and multimedia players), and that is able to know to which process/user all of those pages belong to. |
Author: | simeonz [ Sat Aug 20, 2016 4:31 pm ] |
Post subject: | Re: Fragmentation in slab/LFH vs buddy allocator? |
Quote: Since implementing a paged and multitasking-capable memory manager is basically the same as implementing an on-disk file system, fragmentation is impossible to avoid in practice. Of course. I only ask for opinion on the comparative qualities of the slab and buddy allocator for small allocations. Some scenarios:
My analysis:
In defense of the slab allocator, its header is more compact, its coalescing is faster, and the buddy system tears free chunks on alignment boundaries. I still wonder. What tilts the scale in favor of the slab allocator over the buddy allocator for heap and pool usage in real systems. |
Page 1 of 1 | All times are UTC - 6 hours |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |