|
|
|
Song Jiang's Token Algorithm Officially Adopted in the Linux Kernel The token-ordered thrashing protection algorithm proposed by Song Jiang (Ph.D.'04) and Xiaodong Zhang has been officially adopted in Linux kernel starting in version 2.6.10. The source code for kernel version 2.6.11 has been placed in the Cross-Referencing Linux Kernel Code Repositories at http://lxr.linux.no/source/mm/thrash.c. A paper about this algorithm entitled "Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems" was published in Journal of Performance Evaluation (Vol 60/1-4, pp. 5-29, 2005). This algorithm effectively schedules multiple processes to avoid memory thrashing. The code development in the most recent Linux kernel based on this algorithm was initiated by Rik van Riel from Red Hat Inc. in July 2004, and many other Linux kernel hackers were also involved for its testing and optimization. Another project based on a page replacement algorithm called CLOCK-Pro proposed and evaluated by Song Jiang, Feng Chen and Xiaodong Zhang is also actively going on in the Linux open source community. This work was published in paper entitled "CLOCK-Pro: An Effective Improvement of the CLOCK Replacement", in the 2005 USENIX Annual Technical Conference. The code development progress for its inclusion in the Linux kernel is being timely reported at http://wiki.linux-mm.org/wiki/AdvancedPageReplacement. The Department of Computer Science |