2020-08 [seminár] zámky

Zhrnutie prednášky

Seminár sa venuje implementácii jemnozrnného zamykania v blokovej vyrovnávacej pamäti (b-cache) operačného systému xv6, ktorá sa nachádza v súbore kernel/bio.c a slúži ako medzičlánok medzi diskom a súborovým systémom. Vysvetľuje sa fungovanie cache pomocou funkcií b-get, b-read, b-write a b-release, ako aj problém pôvodného riešenia, ktoré používa jediný globálny spin lock chrániaci zreťazený zoznam bufferov, počet referencií a identitu blokov (device a block number). Pomocou nástroja Barrier's Test sa demonštruje vysoká miera contention (počet spinov pri acquire), ktorú je potrebné znížiť rozdelením cache na 13 hashovacích baketov s vlastnými zámkami namiesto jedného globálneho zámku. Prakticky sa ukazuje príprava dátových štruktúr – pole 13 zreťazených zoznamov a 13 zámkov s prefixom bcache, inicializácia pomocou cyklu a hashovacia funkcia založená na zvyšku po delení čísla bloku počtom baketov. Na konci sa začína úprava funkcie b-get tak, aby využívala príslušný baket podľa vypočítaného hashu namiesto pôvodného globálneho zámku.

• - B-cache v kernel/bio.c ukladá často používané diskové bloky v pamäti, aby sa znížil počet pomalých prístupov na disk.
• - Pôvodná implementácia používa jediný globálny spin lock, ktorý chráni zreťazený zoznam bufferov, počet referencií a identitu blokov (device, block number).
• - Musí platiť invariant, že každý blok je v cache maximálne raz.
• - Barrier's Test meria contention pomocou počítadiel acquire (n) a spinovania (nts) cez atomické operácie sync_fetch_and_add.
• - Riešením je rozdeliť cache na 13 hashovacích baketov (prvočíslo) s vlastnými zoznamami a samostatnými zámkami namiesto jedného globálneho zámku.
• - Hashovacia funkcia je jednoduché modulo: číslo bloku mod počet baketov, ktoré určuje príslušný baket.
• - Inicializácia vyžaduje unikátne pomenovanie každého zámku (prefix bcache) a alokáciu pamäte pre názvy, následne úpravu funkcie b-get na použitie zámku príslušného baketu.

Zhrnutie pripravené s pomocou AI z prepisu videa.