2021-07 [seminár] zámky

Zhrnutie prednášky

Seminár nadväzuje na prednášku o zámkoch a rieši problém súperenia o zámky (lock contention) v operačnom systéme XV6, kde je dátová štruktúra chránená jedným spinlockom prístupná vždy len jednému procesoru, čo obmedzuje paralelizmus. Vysvetľuje sa interfejs a fungovanie keše diskových bufferov (bio.c) – funkcie bread, bget, bwrite a brelease, ktoré slúžia na cachovanie diskových blokov medzi súborovým systémom a diskom. Hlavnou praktickou úlohou je prerobiť pôvodný jeden globálny zreťazený zoznam bufferov na hašovaciu tabuľku s viacerými bucketmi (odporúčaný prvočíselný počet, napr. 13 alebo 17), z ktorých každý má vlastný zámok, čím sa zníži súperenie o zámky. Demonštruje sa postupná implementácia v XV6: pridanie makra počtu bucketov, poľa bucket zámkov, rozdelenie pôvodného zoznamu na viacero zreťazených zoznamov a ich inicializácia vo funkcii binit. Zdôrazňuje sa dodržanie invariantov (buffer je v keši len raz, počítadlo referencií, ochrana identity bloku) a cieľ znížiť počet meraných súperení o zámky pod stanovený limit.

• - Cieľom úlohy je znížiť počet súperení o zámky (lock contention) v subsystéme keše diskových bufferov XV6.
• - Kešu bufferov (bio.c) tvorí zreťazený zoznam blokov medzi súborovým systémom a diskom, spravovaný funkciami bread, bget, bwrite, brelease.
• - Pôvodne je celý zoznam bufferov chránený jedným globálnym zámkom, čo obmedzuje paralelný prístup viacerých procesorov.
• - Riešením je rozdeliť globálny zoznam na hašovaciu tabuľku s viacerými bucketmi, každý s vlastným zámkom.
• - Odporúča sa prvočíselný počet bucketov (napr. 13 alebo 17) pre rovnomerné rozloženie blokov.
• - Pri implementácii treba inicializovať bucket zámky aj samostatné zreťazené zoznamy pre každý bucket vo funkcii binit.
• - Musia zostať zachované invarianty: jedinečnosť bloku v keši, správne počítadlo referencií a ochrana identity kešovaných blokov (device, block number).

Zhrnutie pripravené s pomocou AI z prepisu videa.