Here is another full-project that you should add to the list of possibilities: LRU dates back at least to 1965 and has been the de facto buffer cache replacement policy ever since. While there have been many contenders, none has caught on. In March 2003, a new algorithm called the Adaptive Replacement Cache (ARC) replacement algorithm in your buffer cache. This replacement policy was proposed in March 2003 by two IBM Almaden researchers, N. Megiddo and D. Modha. According to their paper: "In response to evolving and changing access patterns, ARC dynamically, adaptively, and continually balances between the recentcy and frequency components [of a cache replacement policy] in an online and self-tuning fashion." In a nutshell, the idea is to create two lists of pages each of size c, where c is the number of pages in the buffer cache. Pages that have been accessed exactly once are put in one list (for recentcy); pages that have been accessed more than once are put in the other list (for frequency). The pages actually held in memory are a subset of these two lists. The key benefits of ARC are that it does not need workload specific parameters (like most of the other algorithms since LRU), and that, unlike LRU, it is scan-resistant (a scan of a large file does not empty the buffer cache of pages that actually will be accessed soon). The project would be to: - implement ARC - evaluate it with a mixture of workloads that (a) exhibit strong temporal locality (b) perform scans that far exceed memory capacity (c) include looping behavior (d) include a mixture. Paper abstract: http://www.usenix.org/events/fast03/tech/megiddo.html Full paper: http://www.eecs.harvard.edu/~jonathan/papers/2003/megiddo03arc.pdf I'd be happy to go over this in detail with any group that would like to do it, particularly with what experiments to run. -jonathan _______________________________________________ cs161-list mailing list cs161-list(a)fas.harvard.edu http://www.fas.harvard.edu/mailman/listinfo/cs161-list