Transcript Slide 1
VM Algorithm Improvement • Student’s Name: Kamlesh Patel • Date: Oct 13, 2008 • Advisor’s Name: Dr. Chung-E-Wang Prof. Dick Smith Department of Computer Science California State University Sacramento Motivation • 1. I am highly interested in the development of different Kernel modules . • 2. Virtual Memory is my most interesting part in Kernel. • 3. I would like to work for Open Source Community. • 4. My Interesting classes: – Algorithm and Paradigms, Data structure – Operating System Pragmatics • 5. VM algorithm improvement covers all the above criteria. So, it is suitable for my master project. About FreeBSD • FreeBSD is an advanced operating system for x86 compatible, amd64 compatible UltraSPARC, IA-64, PC-98 and ARM architectures. • It is derived from Berkeley Software Distribution (BSD), the version of UNIX developed at the University of California, Berkeley. • It is developed and maintained by a large team of individuals. Memory allocation in OS Page-level Allocation • Operating system’s virtual memory manager uses different data structures to organize memory pages. • Kernel maintains a list of free page frames (physical memory). • Pages are allocated from the free list. • Memory management operations have been measured to consume up to 10% of the CPU time on a busy system. Splay tree in VMM • The FreeBSD operating system uses splay trees to organize memory pages in it its virtual memory manager. • A splay tree is a self-adjusting binary search tree. • If we search for an element that we looked up recently, we will find it very quickly because it is near the top. This is a nice property because many real-world programs will access some values much more frequently than other values. Splay tree penalties • First, in the worst case, a lookup in a splay tree may take O(N) time, even though amortized over many operations, it is guaranteed to be O(log N) on average. • The second penalty is that lookups modify the tree as they perform rotations to move the recently accessed element to the root. The fact that a lookup performs O(log N) writes into the tree significantly adds to its cost on a modern hardware. • It seems that at least some contributors do not consider splay trees to be ideal for this purpose and trying to modify the virtual memory manager to use a different data structure. Project Objective • Implementing Better Data Structures and Algorithms to Support Large VM Objects of freeBSD kernel in place of splay tree data structure. • The objective is efficient use of memory and faster performance • For the management of resident pages the splay trees are used, which are not suitable for the purpose • To replace the splay tree with another data-structure such that even ordered traversal is possible. • The ordered traversal will allow us to reduce size of structure vm_page. Project Plan • To implement the new data structure in user-space first. Test for memory leaks and correctness. Evaluate space and time efficiency. • The new data structure is generalized radix tree. • Move the code to kernel and run the new data structure parallel to old data structure, test for identical functionality. • Performance evaluation. To Do List • Understand VM Space Management. • Test for memory leaks and functional correctness. – Test strategy: For memory leaks add/remove/lookup operations for long time. – Test for different tree configurations. • Integrate a new tree with kernel code and run in parallel with the existing splay tree, check if the values returned are identical. • Remove the splay tree and measure performance for the new data structure. Future Expansion • Future Operating Systems can use the concept of memory management by using different data structures for faster performance.