Page Frame Allocation: Difference between revisions
Jump to navigation
Jump to search
[unchecked revision] | [unchecked revision] |
Content deleted Content added
m adding links |
|||
Line 102: | Line 102: | ||
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. |
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]] |
|||
<pre> |
|||
tree _________ tree ________ |
|||
root | B.start | root | D.size | |
|||
| B.size | | D.start| |
|||
|_________| |________| |
|||
/ \ / \ |
|||
____/____ ____\____ ____/___ ___\____ |
|||
| A.start | | C.start | | C.size | | B.size | |
|||
| A.size | | C.size | | C.start| | B.start| |
|||
|_________| |_________| |________| |________| |
|||
\ \ |
|||
____\____ ____\___ |
|||
| D.start | | A.size | |
|||
| D.size | | A.start| |
|||
|_________| |________| |
|||
by-address ordering by-size ordering. |
|||
</pre> |
|||
While insertion/deletion in such a balanced tree requires more complex operations than linked list manipulation, searching the tree is usually achieved with O(log2(N)) rather than O(N) for linked lists -- that is, if you have 1000 entries, it requires 1000 iterations to scan the list against 10 iterations to find a given interval in the tree. |
While insertion/deletion in such a balanced tree requires more complex operations than linked list manipulation, searching the tree is usually achieved with O(log2(N)) rather than O(N) for linked lists -- that is, if you have 1000 entries, it requires 1000 iterations to scan the list against 10 iterations to find a given interval in the tree. |