Sinhronizacija tri niti sa tri resursa

Postovani prijatelji,

Nadam se da biste mogli da mi sugerisete ispravno resenje za sledeci problem koji se dotice programiranja u
realnom vremenu. U pitanju je jedan ispitni zadatak, pa cu Vam izloziti prvo postavku a onda varijante resenja.
Verujem da u teoriji operativnih sistema postoji optimalno resenje ovog problema, ali ga nisam mogao pronaci
u literaturi koja mi je dostupna.

Naime, postoje tri procesa (ili, svejedno, niti) koji konkurentno pristupaju do tri identicna resursa, po obrascu:

...
use one unit
use two units
...

Potrebno je osmisliti komunikaciju izmedju procesa koristeci semafore tako da se izbegnu 'deadlock' i 'starvation' efekti.

Dodatni zahtev (koji se ne pominje u zadatku ali je cini mi se jako potreban) jeste optimalno iskoriscenje tri resursa.
Podrazumeva se postojanje sinhronizacionih primitiva u operativnom sistemu.

Prvo resenje koje odmah pada na pamet jeste pristup resursima preko centralnog servera. Postoji server kome se
niti obracaju sa zahtevom za resursima, a server se brine o rasporedjivanju resursa. Ovakav pristup obavezno
izbegava deadlock (ne i starvation!) ali server postaje usko grlo kada se sistem skalira na veci broj niti odnosno resursa,
odnosno bespotrebno serijalizuje pristup resursima.

Ono sto se trazi u ovom slucaju (i ono sto se nadam da ce pronaci i ovde napisati neka dobra dusa:) jeste distribuirano
resenje koje sto bolje radi nezavisno od broja niti, bez stvaranja uskih grla. U ovom resenju je znatno teze obezbediti
izbegavanje problema itd.

Zahvaljujem se svima koji uzmu u obzir ovu poruku.

f

Ne zameri, ali meni se cini da si pitanje postavio suvise "akademski", to jest uopsteno. Sta su ta tri resursa? Govoris li u stvari o jednoj klasi, po cijim metodama "zare i pale" tri thread-a istovremeno?
Sve sto je u vezi sa thread-ovima me zanima (citaj: rado bih pomogao), ali tvoje pitanje je bas (bar meni) nejasno.


Rajko

Ok, ne zameram i sasvim mi je jasno zasto si se nasao u nedoumici. Pitanje ni ne moze da bude konkretnije,
tipa: koju funkciju da pozovem tu-i-tu, zato sto radim na jednoj internoj verziji kernela za rad u realnom
vremenu koji podrzava dosta od 'knjiskih' primitiva za sinhronizaciju a ne na nekom od poznatih
operativnih sistema. Sta da se radi. :)

Dakle, mozda konkretnija verzija pitanja je sledeca:

Imam tri uredjaja (recimo sinhronizovane klase) kojima po gore navedenom obrascu treba da
pristupaju tri niti.

Ocigledno resenje je da se tri klase zapakuju u jedan monitor koji ce nitima dodeljivati resurse onako kako
budu trazili, dakle u klasu koja semaforom forsira da pristup njenim metodama bude sekvencijalan,
da se dve niti ne mogu nalaziti u isto vreme unutar njenih metoda.

Problem ovog resenja je sa skaliranjem. Zamisli povecanje broja niti i resursa.
Tada bi vecina niti, umesto da radi svoj posao, cekala da se oslobodi monitorov
semafor. Hteo bih da izbegnem resenje koje ima ovakvo usko grlo.

Idealno bi bilo obezbediti da svaka nit moze da pristupi bilo kom resursu u bilo koje
cime bi se izbeglo 'centralno mesto' za sinhronizaciju, tipa servera kojem se niti obracaju
zahtevom za resursima.

f

Nema tu sta mnogo da se filozofira.
Po meni ili ces semafore da koristis, pa da niti cekaju kao na granicnim prelazima :), ili, ako to situacija dozvoljava, za svaki klijent ces da kreiras novi objekat, cija je klasa neka od ta tri resursa.

Kao u stvarnom zivotu, ako je red dugacak - granicari ce da puste u rad novu traku, pa ce saobracaj da se rasporedi, i bice manje cekanja.

Znaci, gubis ili memoriju, ili vreme.
Meni nije poznata neka treca tehnika za resavanje ovog problema.

I jos nesto, oprezno sa semaforima u multithread modu !!!
Dve, ili vise niti, mogu u istom momentu da pogledaju na semafor, vide zeleno, a zatim oba ukljuce crveno - i tako si izgubio kontrolu nad procesima.
O tome vise na dnu stranice http://www.elitesecurity.org/tema/13236

Mislim da nemaš mnogo izbora. Jednostavno moraš da serijalizuješ pristup resursima preko nekog MUTEX-a ili sličnog sinhronizacionog objekta. Jedina optimizacija koju ja tu vidim je upotreba RW (read-write) lock-ova, koji dozvoljavaju da više niti istovremeno "čita" resurs, a samo jedna sme da ga menja. Ovo je poonekad jako efektna optimizacija, a nekad jednostavno nema smisla - sve zavisi od konkretnog problema.

Potpis

IOCC

Nije obavezna serijalizacija.

Hijerarhijsko uređivanje resursa često daje dobre rezultate (pomalo je besmislena sa tri resursa, ali za veći broj ima smisla).

O čemu se konkretno radi pogledaj staru knjigu Rafaela Finkela (Raphael Finkel): ,,Operating Systems Vade Mecum''. Poseti http://cs.engr.uky.edu/~raphael/

Rešenje koje zahtevaš mislim da bi oslobodilo muke sve tvorce operativnih sistema. Koliko mi je poznato, takvo rešenje ne postoji (optimalno korišćenje resursa nezavisno o njihovom broju).

U najgorem slučaju, Rafael Finkel je smatrao hijerarhijsko uređenje resursa najboljim opštim algoritmom 1989. godine. Nisam u toku sa novijim rezultatima (www.acm.org može biti od pomoći u tome), ali i dalje izgleda tako.

Nadam se da je od pomoći.

PS. Neko nebulozno objašnjenje hij. raspodele resursa se nalazi u mom maturskom radu iz 2001. godine (,,Razvoj operativnih sistema''). Zbog (ne)kvaliteta istog, sramota me je da napišem adresu gde se može skinuti, ali ako ima interesovanja, prevazići ću to. ,,Operating Systems Vade Mecum'' je sigurno bolji izvor :)

Potpis

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Hm, ako nit trazi bilo koja dva resursa a ne odredjena dva resursa, pada mi napamet jos jedna optimizacija - sa jednim celobrojnim semaforom koji se smanjuje/povecava za 1 ili 2 kod P odnosno V operacije. Pocetno stanje semafora je 3. Ovde treba upotrabiti jos jedan mutex, ali on je zakljucan kratko - samo kada prodje P operacija i kada se dodeljuju konkretni resursi.

Ako je bitno kojim resursima pristupa (tj. nit trazi odredjena dva resursa) mislim da je bolje da svaki resurs kontrolise po jedan monitor nego jedan monitor sva tri resursa. Mada, ni ovo nije idealno, ali bar lici na poznat problem (filozofi i viljuske :)

Semafor sa brojacem...
To me podseca na CriticalSection (iz Windows-a). On ima LockCount ili tako nesto.
Svaki poziv EnterCriticalSection() inkrementuje, a LeaveCriticalSection dekrementuje taj LockCount. Kad se LockCount dekrementuje do nule (0), zasticeni deo koda postaje slobodan.

Rajko

P.S. Filmil, u pravu si: veoma tesko i nezgodno pitanje. Punmo srece sa kernelom.

Peco mislim da si pobrkao loncice, semafore upravo obezbedjuju da samo jedan proces moze da upadne u kriticnu sekciju. Ne moze da se desi da oba ukljuce crveno. Ukoliko se to ipak tebi desava onda imas losu implementaciju.

Potpis

http://speedy-order.com

E taj problem koji ti opisujes je jedan od klasicnih problema u IPC, ovaj problem se svodi na problem "5 filozofa" poslacu ti deo teksta iz neke nazovi studentske skripte gde je to opisano. E sada nemoj zameriti sto je kod pola ADA pola C :)))) . Profesor voli adu a studenti C pa su u skripti izmenjali sto su mogli :)

Potpis

http://speedy-order.com

Dejane,

skoro da si u pravu.

Ovo je problem 'tri filozofa', osim sto postoji jedna (fundamentalna!) razlika. Naime,
bilo koja nit (filozof) moze pristupiti bilo kom resursu (viljusci). U originalnom problemu 5 (odnosno N)
filozofa koriste samo resurse koji su neposredno s 'leve' odn. 'desne' strane, tako da se zahtevi filozofa koji
nisu susedi _nikada_ ne sudaraju. U ovom problemu to nije slucaj, jer je svako sa svakim u interakciji.

Resenje koje si dao zove se 'central server model without addressing starvation'. Karakteristike modela su (1)
da postoji centralni 'server' koji isporucuje viljusku i (2) da dva filozofa mogu, kooperativnim delovanjem, da
'izgladne' zajednickog suseda (starvation). U teoriji postoji resenje za problem N filozofa koje nema centralni
'server' i koje eliminise 'izgladnjivanje'. Za tri uredjaja i tri resursa tako nesto nisam nasao. Ostali klasici su
'mutual exclusion', 'sleeping barber' i 'readers and writers'.

f

Nisi me razumeo.
Upozorio sam ga da ne sme da koristi tamo neki
bool semafor;
pa posle da proverava sa:
if (semafor==true)

Dakle, ovo bi drzalo vodu u single-thread modu, a u multi-thread nikako...
Prakticno, upozorio sam ga da mora da ima potpuno drugu implementaciju, o kojoj si ti govorio u onom thread-u.