Use C++ to implement a red black trees and a system to simulate Shared Memory De-duplication which is a popular application used on Linux Kernel.
Develop an algorithm that mimics the de-duplication operations in Linux Kernel.
Instead of using real memory, the program simulate the memory operations using a byte arrayy, which will be considered to be the available memory.
The system has the following 3 operations:
Accept a list of <page id, hash of page content> records.
Accept another list of <page id, hash of page content>. If page id is already loaded, update its hash, which is equivalent to page content changing. If it's not loaded, add it to the system.
Run algorithm explained in IBM's website and display if any memory is freed.
Three test data set will be randomly generated in the program.
The first set is only for testing Load(), which only loads data of 5 pages into the unstable tree.
The second set (10 pages) is for testing Update() and Deduplicate(). One of them intends to have the same hash value as one page from the first set, and another two have same hash value with each other’s. These two pairs show the function of merging (the will be moved to stable tree for merging).
The third set (5 pages) is for testing Update(). One of them intends to have the same page id as one of pairs mentioned above. This is for testing the function of moving changed pages to unstable tree.
After each function (Load and Update), the trees will show for checking in detail.
Build and run Shared Memory deduplication file.
See Report to understand more about implementation, time complexity and examples.