Page Frame Allocation: Difference between revisions
[unchecked revision] | [unchecked revision] |
Content deleted Content added
m s/dword/uint32_t/g |
No edit summary |
||
(4 intermediate revisions by 4 users not shown) | |||
Line 1:
==Physical Memory Allocators==
These are the algorithms that will provide you with a new page frame when you
N will be the size of the memory in pages in the following text.
Line 13:
===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
===Sized Portion Scheme===
Line 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.
0 4 8 12 16 20 24 28 32 36
Line 65:
[[Image:Flat_list.png]]
===Tree-based approach
Since it is frequent that the list is searched for a given address or a given size, it may be interesting 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.
Line 77:
==See Also==
===Articles===
* [[Writing A Page Frame Allocator]]
* [[Memory Allocation]]
* [[Memory management]]
Line 101 ⟶ 102:
[[Category:Common_Algorithms]]
[[Category:Memory management]]
[[Category:Physical Memory]]
[[de:Physische Speicherverwaltung]]
|