OSDev.wiki

Page Frame Allocation: Difference between revisions

Page Discussion

Page Frame Allocation (view source)

Revision as of 18:50, 10 July 2023

572 bytes removed ,  11 months ago
no edit summary
[unchecked revision][unchecked revision]
VisualWikitext
No edit summary
No edit summary
 
(21 intermediate revisions by 16 users not shown)
Line 1:
==Physical Memory Allocators==
 
These are the algorithmalgorithms that will provide you with a new page frame when you'll need it. The client of this algorithm is usually indifferent to which frame is returned, and especially, a request for n frames needndoesn't need to return contiguous frames (unless you are allocating memory for DMA operations like network packet buffers).
 
N will be the size of the memory in pages in the following text.
Line 8:
A large array of N/8 bytes is used as a large bit map of the memory usage (that is, bit #i in byte #n define the status of page #n*8+i). Setting the state of a given page is fast (O(1)), allocating a page may take time (O(N)).
 
* aan dworduint32_t comparison can test up to 32 bits at once and thus speed up allocsallocations
* keeping a pointer to the last allocated bit may improve the performance of the next search (keeping information about the fact all the previous bytes were searched unsucessfullyunsuccessfully)
 
===Stack/List of pages===
 
The address of each available physical frame is stored in a [[stack]]-like dynamic structure. Allocating a page is fast (O(1)), freeing a page too but checking the state of a page is not practical, unless additional metadata is sorted by physical address.
 
===Sized Portion Scheme===
Line 19:
You split each area of, say 16kb into (for example) chunks of 1 8kb, and 2 4kb's. Then you hand out each chunk. By doing this you can find closer fits to exact sizes. That means less waste. So say that you have an area of 32kb
 
[[Image:Sized Portion Scheme.png]]
<---------------------------------------->
|8kb....|4kb|4kb||8kb....|4kb|4kb|
<---------------------------------------->
 
You can even have 1, 2, even 3 or 4 (or more!) types of layouts for each portion. This way you have even more sizes to choose from.
 
 
===Buddy Allocation System===
Line 37 ⟶ 34:
buddy[3]---> # # # # # 0 free 32K, 5-bits map
 
A buddy for N pages is about twice the size of a bitmap for the same area, but it allows a faster location of collections of pages. FigureThe figure above shows a 4-buddy with free pages/blocks denoted as . and used pages/blocks denoted as #. When a block contains at least one used sub-block, it is itself marked as used and sub-blocks that are part of a larger block are also marked as used (x onin the figure). Say we want to allocate a 12-K region on this buddy, we'll lookuplook up the bitmap of free 16K blocks (which says we have one such starting at page #12 and another starting at page #36). buddy[2]->bit[4] is then set to 'used'. Now we only want 3 pages out of the 4 we got, so the remaining page is returned to the appropriated buddy bitmap (e.g. the single pages map). The resulting buddy is
 
0 4 8 12 16 20 24 28 32 36
Line 62 ⟶ 59:
===Flat List===
 
One straightforward way to manage big areas of addresses space is a linked-list (as depicted below). Each "free" region is associated with a descriptor giving its size and its base address. When some space needs to be allocated, the list is scanned for a region being large enough with a "first fit" or "best fit" (or watheverwhatever) algorithm. This was e.g. the way memory was managed by MS-DOS. When memory is allocated, the suitable entry is either removed (the whole region is allocated) or resized (only a portion of the region is allocated).
 
Note that with flat linked-lists, both "is memory at address XXX free" or "where can i get a block of size YYY" questions may require a complete traversal of the list to get answered. If virtual memory gets fragmented and the list gets longer, that may become an issue. "Is memory at address XXX free?" is mainly used to merge two free zone into a new (bigger) one when a block is released, and it is easier to deal with if the list is kept ordered by growing addresses.
 
[[Image:Flat_list.png]]
<pre>
address space
_______ ______
Start--------------->| | | (A) |
Size--------------\ | free | -> | free |
Block_before \ | space | |------|
,-Block_after \|_______| |\\\\\\|
| |\used\|
| _______ |\\\\\\|
| Start--------------->| | |------|
| Size--------------\ | free | | (B)|
'-Block_before \ | space | -> | free |
,-Block_after \|_______| | |
| |------|
| _______ |\used\|
| Start--------------->| | |---(C)|
| Size--------------\ | free | -> | free |
'-Block_before \ | space | |------|
,-Block_after \|_______| |\\\\\\|
| |\used\|
| _______ |\\\\\\|
| Start--------------->| | |------|
| Size--------------\ | free | | (D)|
'-Block_before \ | space | -> | free |
Block_after \|_______| |______|
 
===Tree-based approach.===▼
</pre>
 
Since it is frequent that the list is searched for a given address or a given size, it may be interrestinginteresting to use more efficient data structures. One of them that still keeps the ability of traversing the whole list is the AVL Tree. Each "node" in the AVL tree will describe a memory region and has pointer to the subtree of lower nodes and to the subtree of higher nodes.▼
▲===Tree-based approach.===
 
▲Since it is frequent that the list is searched for a given address or a given size, it may be interresting to use more efficient data structures. One of them that still keeps the ability of traversing the whole list is the AVL Tree. Each "node" in the AVL tree will describe a memory region and has pointer to the subtree of lower nodes and to the subtree of higher nodes.
 
[[Image:Tree based.png|none]]
Line 105 ⟶ 76:
 
==See Also==
===Articles===
* [[Writing A Page Frame Allocator]]
* [[Memory Allocation]]
* [[Memory management]]
* [[Writing a memory manager]] - a tutorial
 
===Threads===
* [[Topic:11320|Allocating memory for an allocator without an allocator]]
Line 117 ⟶ 94:
* [[Topic:10279|Malloc, etc. (tute by curufir)]]
* [[Topic:10747|Physical MM (by Freanan)]]
* [[Post:195116|Concepts and key points on alternative memory management schemes]]
 
===External Links===
*mystran's [http://replay.web.archive.org/20081206102136/http://www.cs.hut.fi/~tvoipio/memtutor.html Basic VMM for Dummies (cached)]
* [[wikipedia:Page replacement algorithm|Page replacement algorithm]] on Wikipedia
 
[[Category:Common_Algorithms]]
[[Category:Memory management]]
[[Category:Physical Memory]]
[[de:Physische Speicherverwaltung]]
Anonymous user
Retrieved from "https://osdev.wiki/wiki/Special:MobileDiff/19355...19377"