Abstract
The central component of any operating system is the Memory Management Unit (MMU). As the name implies, memory-management facilities are responsible for the management of memory resources available on a machine. Virtual memory (VM) in MMU allows a program to execute as if the primary memory is larger than its actual size. The whole purpose of virtual memory is to enlarge the address space, the set of addresses a program can utilize. A program would not be able to fit in main memory all at once when it is using all of virtual memory. Nevertheless, operating system could execute such a program by copying required portions into main memory at any given point during execution. To facilitate copying virtual memory into real memory, operating system divides virtual memory into pages. Each page contains a fixed number of addresses. Each page is stored on a disk, when the page is needed it is copied into the main memory. In order to achieve better performance, the system needs to provide requested pages quickly from memory. Tree search algorithm find requested pages from virtual page data structure. Its efficiency is highly depends on the structure and number of nodes. That is why data structure is an important feature of virtual memory. The splay tree and the radix tree are the most popular data structure for the current Linux operating system. FreeBSD OS uses the splay tree data structure. In some situation like prefix searching, the splay tree data structure is not the most effective data structure. As a result, the OS needs a better data structure than the splay tree to access VM pages quickly in that situation. The radix tree structure is implemented and used in place of the splay tree. The objective is efficient use of memory and faster performance. Both the data structures are used in parallel to check the correctness of newly implemented radix tree. Once the results are satisfactory, I also benchmarked the data structures and found that the radix tree gave much better performance over the splay trees when a process holds more pages.