2021-08 [cvičenie] zámky - otázky a odpovede

Zhrnutie prednášky

Cvičenie je venované diskusii k dvom domácim úlohám z tém zámkov a paralelizmu v operačných systémoch – pamäťovému alokátoru a implementácii cache bufferov s vlastnou náhradou least recently used. Rieši sa konkrétny problém deadlocku pri hľadaní najmenej používaného buffera medzi baketmi, keď proces drží viacero zámkov naraz a čaká na uvoľnenie zámku, ktorý drží iný procesor. Vysvetľuje sa, že prehľadávanie jednotlivých baketov možno paralelizovať pomocou zámkov na úrovni baketov, no pri recyklácii buffera (keď sa hľadaný blok nenachádza v cache) je legitímne použiť jeden veľký zámok na celú cache, keďže vtedy je nutné prehľadať celú štruktúru. Ako alternatíva k zložitému systému s timestampmi a viacerými zamykanými baketmi sa navrhuje jednoduchšie riešenie s jedným globálnym zoznamom least recently used, kde sa uvoľnený buffer presúva na koniec a pri recyklácii stačí zamknúť len tento jeden zoznam. Cieľom oboch úloh je znížiť súperenie o zámky (lock contention) a zlepšiť paralelizmus, pričom sa demonštrujú aj reálne výsledky meraní počtu zamknutí a spinov na jednotlivých zámkoch.

• - Cvičenie rieši dve úlohy: pamäťový alokátor a cache bufferov s vlastnou LRU implementáciou.
• - Cieľom oboch úloh je znížiť súperenie o zámky a zvýšiť paralelizmus prístupu.
• - Analyzuje sa konkrétny deadlock pri súčasnom držaní viacerých zámkov (aktuálny, posledný najlepší, blok) počas hľadania najmenej používaného buffera.
• - Odporúča sa paralelizovať prehľadávanie jednotlivých baketov, no pri recyklácii buffera (keď blok nie je v cache) je v poriadku použiť jeden veľký zámok na celú cache.
• - Ako alternatíva k timestampom sa navrhuje jednoduchšie riešenie s jedným globálnym LRU zoznamom, kde stačí zamknúť len tento zoznam pri recyklácii.
• - Demonštrujú sa výsledky meraní zamknutí a spinov (superenia) na jednotlivých zámkoch pre overenie efektivity riešenia.
• - Diskutuje sa debugovanie kódu vrátane logovania zámkov a chybného priraďovania hodnoty last bucket v cykle.

Zhrnutie pripravené s pomocou AI z prepisu videa.