[OSy] Neblokujici seznamy

[Cestmir Houska]

Diky za odpoved!

S pozdravem,

Cestmir Houska

2011/3/16 Martin Decky <decky at d3s.mff.cuni.cz>

> 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.
>
> _______________________________________________
> OSy mailing list
> OSy at d3s.mff.cuni.cz
> https://d3s.mff.cuni.cz/mailman/listinfo/osy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20110316/45e7f38b/attachment.html>