Please enable JavaScript.
Coggle requires JavaScript to display documents.
Resenja zasnovana na aktivnom cekanju - Coggle Diagram
Resenja zasnovana na aktivnom cekanju
Uvod
veci broj resenja za zastitu kriticne sekcije je zasnovano na tzv. aktivnom cekanju
-> cekanje u ciklusu (petlji) dok se ne stvore uslovi za ulazak procesa u kriticnu sekciju
moze se steci utisak da je relativno jednostavno implementirati granicnike koji bi omogucili zastitu kriticne sekcije
Algoritmi
Zastita kriticne sekcije (1)
ideja: cekanje da promenljiva
moze
postane 1, po zavrsetku rada u kriticnoj sekciji proces postavlja
moze
na 1 cime omogucava drugom procesu da, ako zeli, udje u kriticnu sekciju
problem: najvazniji uslov
uzajamne iskljucivosti
nije zadovoljen; moze se dogoditi da jedan proces izvrsi proveru da li je
moze
jednako 1 i posto utvrdi da jeste, krene da je postavi na 0; ukoliko taj proces bude prekinut pre nego sto stigne da postavi
moze
na 0, drugi proces moze videti da je ulaz u kriticnu sekciju slobodan i u nju uci
Zastita kriticne sekcije (2)
ideja: uvesti dve promenljive
zeli_1
i
zeli_2
umesto promenljive
moze
kako bi se zadovoljio uslov uzajamnog iskljucivanja; one se koriste da bi procesi mogli da najave zelju za ulaskom u kriticnu sekciju
tok: svaki proces najavi da zeli da udje u kriticnu sekciju i aktivno ceka dok i drugi to zeli; kada proces zavrsi sa radom u kriticnoj sekciji svoju
zeli
promenljivu postavlja na 0 cime drugi proces oslobadja od aktivnog cekanja i propusta ga
problem:
problem zaglavljivanja
-> ako prvi proces najavi da zeli da udje u kriticnu sekciju i u tom trenutku bude prekinut, drugi proces ce tada postaviti svoju promenljivu
zeli
na 1 i zaglaviti se u petlji jer je
zeli_1
jednak 1; po nastavku rada prvog procesa, on ce se takodje zaglaviti u petlji jer je sada vrednost promenljive
zeli_2
jednaka 1.
Striktna alternacija
ideja: zasniva se na koriscenju promenljive
na_redu
kojom se odredjuje koji od dva procesa ima prednost; na pocetku, prednost se daje prvom procesu.
tok: procesi aktivno cekaju da dodju na red, kada napusti kriticnu sekciju proces promenljivoj
na_redu
daje vrednost drugog procesa koji tako dobija sansu da prsitupi kriticnoj sekciji ukoliko to zeli
problem: resenje ispunjava samo uslov uzajamne iskljucivosti; ukoliko jedan proces ima prednost, a ne zeli da udje u kriticnu sekciju on ce blokirati i drugi proces, cime ce onemoguciti progres; kako to blokiranje moze da bude na neodredjeno vreme jasno je da ni uslov konacnog cekanja nije dozvoljen.
mana: namenjen za situacije koje podrazumevaju ucesce samo dva procesa
prednost: pogodna za problem sinhronizacije kada procesi treba da naizmenicno pristupaju deljenim resursima
Dekerov algoritam
- prvo kompletno resenje
ideja: potrebne su 3 promenljive:
zeli_proces_1 - kojom prvi proces najavljuje da zeli da udje u kriticnu sekciju
zeli_proces_2 - kojom drugi proces najavljuje da zeli da udje u kriticnu sekciju
na_redu - kojom se void racuna o tome koji je proces na redu da udje u kriticnu sekciju
tok: ...
problem: narusen
princip pravednosti
mana: namenjen iskljucivo za situacije kada dva procesa konkurisu za iste podatke
Pitersonov algoritam
ideja: kada proces najavi da zeli da udje u kriticnu sekciju "dzentlmenski" ustupa prednost drugom procesu - vazi samo ukoliko i drugi proces zeli da udje u kriticnu sekciju
prednost: procesi naizmenicno ulaze u kriticnu sekciju ako to zele, nezavisno od njihove brzine
mana: primenljiv samo za dva procesa
Lamportov (pekarski) algoritam
- uopstenje Pitersonovog algoritma
ideja: zasnovana na opsluzivanju musterija u pekari gde musterija dobija svoj broj koji je veci od brojeva koje su dobile prethodne musterije; musterije se opsluzuju redom od najnizih brojeva
tok: posto se ne moze garantovati da dva procesa nece imati isti broj jer je i dodela brojeva kriticna sekcija, u tom slucaju se onaj sa manjim indeksom opsluzuje prvi
potrebno je uvesti sledece oznake:
(A, B) < (C, D) ako A < C ili A = C i B < D
max(A1, A2, ..., An) = K, gde K>= Ai za i=1, 2, ..., n
Potrebno je kao globalne promenljive definisati i inicijalizovati ih na nulu:
celobrojni niz (broj[n]) i
niz logickih promenljivih (uzima[n])
prednosti: radi za proizvoljan broj procesa i zadovoljena su sva tri uslova koje treba da zadovolji dobro resenje, a moze i da radi na sistemima sa vise procesora
Hardverska resenja
Uvod
podrazumevaju upotrebu posebnih instrukcija procesora
ideja: napraviti posebne masinske instrukcije koje su u stanju da urade bar dve operacije bez mogucnosti prekida -
atomicno
Koriste se:
TAS (Test and Set)
FAA (Fetch and Add)
SWAP (zamena)
TAS
operise sa 2 promenljive A = TAS(B) i funkcionise tako sto se vrednost koja se nalazi u promenljivoj B prebacuje u promenljivu A, a u promenljivu B se postavlja 1
FAA
takodje operise sa 2 promenljive, FAA(A, B) - vrednost B prebacuje u A, a vrednost B+A u promenljivu B (u A+B se koristi stara vrednost promenljive A)
SWAP
operise sa 2 promenljive, SWAP(A, B) i rezultat je atomicna zamena vrednosti A i B; zamena se sastoji iz bar 3 operacije
Koriscenje za zastitu kriticne sekcije
uglavnom postoji jedna promenljiva kojom se stiti ulaz u kriticnu sekciju, a procesi aktivno cekaju da se ulaz oslobodi, kada se to desi onda atomicnost ovih instrukcija omogucava da tacno jedan proces udje u kriticnu sekciju
Zastita kriticne sekcije (TAS)
ideja: deklarise se globalna promenljiva
zauzeto
i postavi se na 0, dok svaki proces ima promenljivu
ne_moze
tok: ...
mana: cinjenica da je zasnovana na hardverskoj podrsci, odnosno da je potrebno da procesor ima ugradjenu tu instrukciju
prednost: moze se primeniti na proizvoljan broj procesa (moze doci do "izgladnjivanja" procesa - dugo cekanje procesa da udje u kriticnu sekciju jer drugi imaju vise "srece")
Zastita kriticne sekcije (TAS) - modifikacija
ideja: obezbediti garanciju da ce proces konacno dugo cekati na ulazak u kriticnu sekciju; potrebno je deklarisati globalni niz
ceka[n]
ciji se clanovi inicijalizuju na 0 i promenljivu celobrojnog tipa
zauzeto
koja se takodje postavlja na 0
modifikacija se satoji u tome da po zavrsetku rada u kriticnoj sekciji, proces koji je zavrsio pronadje sledeci od procesa koji cekaju i da ga "prozove" da udje u kriticnu sekciju -> ceka[j] je 0; ako takav proces ne postoji, promenljiva zauzeto se posatvlja na 0, cime se ulaz u kriticnu sekciju oslobadja
mana: sporije resenje jer se i drugi procesi proveravaju i nudi im se da udju u kriticnu sekciju sto iziskuje dodatnu potrosnju procesorskog vremena
prednost: pravedan i garantuje da ce svaki proces da ceka konacno dugo u redu za pristup kritcnooj sekciji
Zastita kriticne sekcije (SWAP)
ideja: brava je globalna promenljiva koja se postavlja na 0 sto oznacava da je prolaz u kriticnu sekciju slobodan (brava bez kljuca); procesi koji se nadmecu imaju kljuc sa vrednoscu 1 koja govori da ljuc nije u bravi, odnosno da cekaju da udju u kriticnu sekciju. U petlji pokusavaju da ubace kljuc u bravu i time "zakljucaju" bravu dok ne izadju iz kriticne sekcije