Anonymous user
Page Frame Allocation: Difference between revisions
no edit summary
[unchecked revision] | [unchecked revision] |
m (Interwiki) |
No edit summary |
||
(11 intermediate revisions by 10 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 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)).
*
* 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 unsuccessfully)
===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 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 93 ⟶ 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]]
|