KDP/Jul 2021

Postavka ovog roka može se naći sa stranice predmeta.

1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Kod Tie breaker algoritma za n procesa se dogodio sledeći slučaj – prilikom izvršavanja koda za ulazak u kritičnu sekciju, svih n procesa su ušli u stanje 1 i nijedan još nije ušao u stanje 2. Odgovoriti na sledeća pitanja i obrazložiti odgovor:

1. Da li proces koji je prvi ušao u stanje 1 prvi ulazi u stanje 2?
2. Da li proces koji je prvi ušao u stanje n-2 prvi ulazi u kritičnu sekciju?
3. Da li proces koji je poslednji ušao u stanje 1 može da bude treći koji ulazi u stanje 2?
4. Da li proces koji je poslednji ušao u stanje 1 može da bude prvi koji ulazi u kritičnu sekciju?

Rešenje

1. U opštem slučaju, ne mora da znači da će proces koji je prvi ušao u stanje 1 prvi ući i u stanje 2. Pošto se u tom trenutku svi procesi nalaze u stanju 1, bilo koji proces koji nije poslednji stigao u stanje 1 će moći da prvi uđe u stanje 2. Specijalno, u slučaju kada je $n = 2$, proces koji je prvi ušao u stanje 1 će garantovano prvi ući u stanje 2.
2. U prvom stanju mogu da se nađu $n$ procesa, u drugom stanju $n-1$ procesa... tom logikom u stanju $n-2$ mogu da se nađu 3 procesa istovremeno. Jedan od ta tri procesa će poslednji ući i neće moći da napreduje, dok će ostala dva moći da napreduju i ne garantuje se koji od ta dva procesa će prvi napredovati.
3. Proces koji je poslednji ušao u stanje 1 će biti poslednji koji će iz njega izaći. Moguće je da on bude treći koji ulazi u stanje 2 ukoliko je $n = 3$, u suprotnom ne mora da znači.
4. Proces koji je poslednji ušao u stanje 1 je poslednji koji ulazi u kritičnu sekciju. Da bi takođe bio i prvi, moralo bi da važi $n = 1$ a to nema smisla.

2. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

3. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

4. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.