CLOCK-Pro: hatékonyabb algoritmus a VM alrendszerben

Kernel

A folyton növekvő szakadék a memória rendszerek és a diszkek teljesíménye közt, és a szintén egyre növekvő CPU teljesítmények arra ösztönzik az operációs rendszerekben található virtuális memória menedzsment (VMM) alrendszerek fejlesztőit, hogy lépés tartsanak ezzel a fejlődéssel, hiszen a rosszul teljesítő VM alrendszer könnyen lehet szűk keresztmetszete az operációs rendszer teljesítményének.

Sajnos a mostani operációs rendszerek (köztük a Linux) VM-jében a mai napig egy olyan (a fenti szempontok szerint kritikus) algoritmus dominál, amelyet minimum 35 éve fejlesztettek. Ez a kritikus komponens a CLOCK névre hallgató page replacement policy.Néhány szakember 2005 áprilisában prezentált egy továbbfejlesztett CLOCK algoritmust CLOCK-Pro néven (PDF) az USENIX'05 konferencián. Ez az algoritmus hasonlóan, de a VM rendszer számára ``olcsóbban'' működik, mint a CLOCK.

Peter Zijlstra azon dolgozik, hogy ezt a CLOCK-Pro algoritmust implementálja a Linux kernel számára. Ennek érdekében tegnap véleményezésre el is küldte az eddigi munkáját a LKML-re.

Egyes mérések szerint a CLOCK-Pro algortimussal működő 2.4.21-es Linux kernelen futó, általánosan használt alkalmazások végrehajtási ideje (execution time) 47%-kal csökkent.

A patch bejelentése itt.

A PDF szerint:

``Unfortunately, an approximation of LRU, the CLOCK replacement policy [5], which was developed almost 40 years ago, is still dominating nearly all the major operating systems including MVS, Unix, Linux and Windows,''

Ugyhogy gondolom azokban is az van.

A NetBSD-sek szinten egy jobb page replacement policy-t keresnek [marc.theaimsgroup.com]. Szoba jott a szalban az ARC, amelyet a PostgreSQL implementalt korabban, de kiderult, hogy az IBM altal szabadalmaztatott, es ezert iden el is tavolitottak [www.postgresql.org], majd helyette 2Q algoritmust hasznaltak fel.

Jo kiindulopontok:

- Page_replacement_algorithms [en.wikipedia.org]

- AdvancedPageReplacement [linux-mm.org]

( bra | 2005. 12. 31., szo – 17:47 )

"volt már":

http://lwn.net/Articles/147879/

:)

( monas | 2006. 01. 02., h – 07:46 )

Ez a patch honnan toltheto le 2.6.x kernelhez?