Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Sinhronizacija tri niti sa tri resursa

[es] :: Art of Programming :: Sinhronizacija tri niti sa tri resursa

[ Pregleda: 5245 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.etf.bg.ac.yu

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Sinhronizacija tri niti sa tri resursa03.09.2002. u 16:16 - pre 262 meseci

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
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
*.beg.sezampro.yu



+62 Profil

icon Re: Sinhronizacija tri niti sa tri resursa04.09.2002. u 10:06 - pre 262 meseci
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
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.etf.bg.ac.yu

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Sinhronizacija tri niti sa tri resursa04.09.2002. u 11:58 - pre 262 meseci

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
 
Odgovor na temu

Predrag Damnjanovic
Predrag Damnjanovic
Nis, Srbija

Član broj: 141
Poruke: 1305
*.rcub.bg.ac.yu

Sajt: www.mycity.rs


+1 Profil

icon Re: Sinhronizacija tri niti sa tri resursa04.09.2002. u 13:09 - pre 262 meseci
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
 
Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*



+6 Profil

icon Re: Sinhronizacija tri niti sa tri resursa04.09.2002. u 17:17 - pre 262 meseci
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.
 
Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.dial.InfoSky.Net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..


+2 Profil

icon Re: Sinhronizacija tri niti sa tri resursa04.09.2002. u 19:38 - pre 262 meseci
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 :)
Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.
 
Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521


Profil

icon Re: Sinhronizacija tri niti sa tri resursa04.09.2002. u 21:43 - pre 262 meseci
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 :)
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
*.beg.sezampro.yu



+62 Profil

icon Re: Sinhronizacija tri niti sa tri resursa05.09.2002. u 09:23 - pre 262 meseci
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.
 
Odgovor na temu

Dejan Lozanovic
Dejan Lozanovic
Beograd

Član broj: 691
Poruke: 2325
*.beograd-3.tehnicom.net

Jabber: null@elitesecurity.org
Sajt: speedy-order.com


+75 Profil

icon Re: Sinhronizacija tri niti sa tri resursa10.09.2002. u 12:52 - pre 262 meseci
Citat:
Predrag Damnjanovic:
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.


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.
 
Odgovor na temu

Dejan Lozanovic
Dejan Lozanovic
Beograd

Član broj: 691
Poruke: 2325
*.beograd-3.tehnicom.net

Jabber: null@elitesecurity.org
Sajt: speedy-order.com


+75 Profil

icon Re: Sinhronizacija tri niti sa tri resursa10.09.2002. u 13:27 - pre 262 meseci
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 :)

Citat:


IPC (Inter Processor Communication) su standardni problemi ovog tipa. Jedan od zadataka je. Za okruglim stolom sedi pet filozofa i pred svakim je tanjir, a izmeðu svaka dva je vilju¹ka. Da bi neko jeo treba da ima dve vilju¹ke. Potrebno je simulirati rad filozofa. (malo razmi¹lja, malo jede). Potrebno je deklarisati niz s(0..4) tipa semafora, mutex i niz stanje(0..4).


Proces k
while(true) {
razmislja();
uzmeviljuske(i);
jede();
vrativiljuske(i);
end;
parbegin
filozof(0);
.
filozof(4);
parend.


uzmiviljuske(k)
{
down(mutex);
stanje[k]=gladan;
test(i);
up(mutex);
down(s[k]);
}

vrativiljuske(k)
{
down(mutex);
stanje[k]=razmislja;
test(levi);
test(desni);
up(mutex)
}

test(i)
{
if( stanje[k] == gladan && stanje[levi] != jede && stanje[desni] != jede)
up(s[k]);
}

 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.etf.bg.ac.yu

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Sinhronizacija tri niti sa tri resursa10.09.2002. u 13:48 - pre 262 meseci

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
 
Odgovor na temu

Predrag Damnjanovic
Predrag Damnjanovic
Nis, Srbija

Član broj: 141
Poruke: 1305
*.041net.co.yu

Sajt: www.mycity.rs


+1 Profil

icon Re: Sinhronizacija tri niti sa tri resursa10.09.2002. u 13:49 - pre 262 meseci
Citat:
Dejan Lozanovic:
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.


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.
 
Odgovor na temu

[es] :: Art of Programming :: Sinhronizacija tri niti sa tri resursa

[ Pregleda: 5245 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.