[OSy] Neblokujici seznamy

[Martin Decky]

Hezky den,

> uz nekolikaty den premyslime nad implementaci neblokujicich seznamu.
> Implementace v paperu, odkazovanem v rozsirenem prvnim zadani, jenom
> vypojuje uzly ze seznamu, ale nijak je nedealokuje. Staci implementace,
> ktera data dealokuje az po ukonceni prace se seznamem a nebo je potreba
> mit i podporu pro dealokaci uzlu?

Pro splneni zadani urcite staci varianta s doprednou alokaci a deferred 
dealokaci prvku seznamu. Cilem zadani je ziskat praktickou zkusenost se 
zakladnimi operacemi nad blokujicim a neblokujicim seznamem (insert, 
find, remove) s pouzitim jiz naalokovanych prvku.

Kdybychom striktne vyzadovali i zaintegrovani alokace a dealokace, 
vlastne bychom tim pozadovali implementaci uplneho RCU mechanismu.

> Pokud by bylo treba i dealokovat, mam jeste jednu otazku - jako
> nejschudnejsi se mi zdaji reseni, ktera pouzivaji reference counting,
> ale k tomu potrebuju pouzit konstrukt, hodne podobny spinlocku, abych
> ziskal pointer z pameti a inkrementoval pamet na miste, kam ukazuje - to
> vse atomicky. V podstate by se jednalo o spinlock, ktery pri zamceni
> vypne interrupty a pri odemceni je zase zapne. Tak bude zaruceno, ze
> vlakno, ktere spinlock zamklo, nebude odswapovano uvnitr spinlocku, a
> tim padem nebude blokovat ostatni vlakna. Da se timto smerem jit, nebo
> je podobne uvazovani zcestne?

Temito uvahami mozna jdete jeste o kousek dal nez jde klasicke RCU (kde 
je alokace i dealokace stale explicitni operace), vlastne uvazujete o 
necem, co by se dalo nazvat neblokujici garbage collector.

Jinak spinlock, ktery vypina preruseni, neni nic tak zvlastniho, ale 
porad jeste bych to nepovazoval za "neblokujici" primitivum. Moznosti, 
jak implementovat wait-free reference counting, se daji dohledat v 
odbornych clancich, ale je to zcela nad ramec toho, co pozadujeme v 
zadani semestralky.


M.D.