Međusobno isključivanje Flashcards
Skup zauzetih sredstava je ISTI za sve dretve ISTOG procesa.
- postoji zajednički spremnik (globalne varijable)
- brža komunikacija među dretvama (-||-)
- komunikacija među njima bez uplitanja OS-a
Višedretveni vs. višezadaćni rad?
Višedretveni rad - u paraleli izvođenje (ne nužno istovremeno)
Višezadaćni rad - više zadataka odjednom, svaki zad u zasebnoj dretvi
Zadatak se može podijeliti na… (i koja dretva je za to)
podzadatak za čitanje ulaznih podataka - ulazna dretva
podzadatak za obradu - radna dretva
podzadatak za obavljanje izlaznih operacija - izlazna dretva
Kako ostvariti sinkronizaciju?
Međusobnim isključivanjem, semaforima.
Kada se 2 zadatka (dretve) mogu izvoditi paralelno?
Dva su podzadatka nezavisna ako nemaju nikakvih zajedničkih spremničkih lokacija ili imaju presjeka samo u domenama. Tada se mogu izvoditi proizvoljno ili paralelno.
uvjet nezavisnosti: (Xi ∩ Yj ) ∪ (Xj ∩ Yi) ∪ (Yi ∩ Yj ) = ϕ
*ako su zavisni mora se ustvrditi redoslijed izvođenja
Međusobno isključivanje…
Podjela koda dretvni na kritične i nekritične odsječke.
Kritični odsječak se ostvaruje funkcijama uđi_u_KO i izađi_iz_KO.
Koji su zahtjevi na algoritme međusobnog isključivanja?
1) u KO u svakom trenutku smije biti najviše 1 dretva
2) mehanizam MI mora djelovati i kada su brzine izvođenja dretvi proizvoljne
3) kada neka dretva zastane u svom NKO, ona ne smije spriječiti drugu dretvu da uđe u KO
4) izbor dretve koja ulazi u KO treba odrediti u konačnom vremenu
Problem kod korištenja zastavica…
Ako dretve rade paralelno, obje mogu pročitati 0 i ući u KO.
Problem kod korištenja varijable PRAVO?
Ulazak u KO je naizmjeničan i nisu ispunjeni uvjeti 2 i 3.
Dekkerov algoritam za 2 dretve…
U slučaju obostrana zahtjeva za ulazak, dretva koja nije na redu će spustiti svoju zastavicu i pričekati da druga završi sa KO.
Prednost Petersonovog algoritma nad Dekerovim?
Algoritam za više od dvije varijable?
Kraći, brži, ne ovisi o početnoj varijabli PRAVO.
LAMPORT.
Lamportov algoritam…
Svaka dretva prije ulaska u KO dobije svoj broj koji je za jedan veći od najvećeg dodijeljenog (taj postupak je isto KO). U KO ulazi dretva s najmanjim brojem.
*ako dvije dobiju isti broj, gleda se indeks
BROJ[N] i ULAZ[N]
**radi za proizvoljan broj dretvi na proizvoljnom broju procesora, potrebno je dosta struktura podataka
Sklopovska potpora međusobnom isključivanju?
Korištenje 2 uzastopna sabirnička ciklusa. U prvom se čita vrijednost zastave, a u drugom se zastavica postavlja u 1.
- u obliku instrukcija TAS, SWP, INC, CAS
- *problemi su radno čekanje i nepoštivanje redoslijeda zahtijeva (ne bude ona dretva koja je najduže čekala) -> rj. je korištenje jezgrinih funkcija
