DIO I – TEORETSKA PITANJA


Q1. (15 poena)

1.	Navesti i objasniti potrebne korake za izvršavanje nekog algoritma za zamenu stranica (engl. page replacement algorithm). Takođe, navesti osnovne zahteve koje bi trebalo da ispuni svaki algoritam zamene stranica. Dati precizan i jasan odgovor.

Najjednostavniji algoritam zamene stranica je FIFO. Dodeljuje svakoj stranici vreme kada je stranica dovedena u memoriju. Kada se mora zameniti stranica, bira se najstarija. Kada se stranica dovodi u memoriju, ubacuje se na kraj reda. Zamenjuje se stranica na celu reda.

Osnovni zahtevi koje mora ispuniti algoritam zamene stranica jeste razvijanje algoritma dodele okvira i algoritma zamene stranica.

2.	Objasniti princip DMA prenosa i korake za njegovo izvršenje. Na koji način DMA doprinosi boljem radu procesora?

DMA sistem obezbedjuje prenos podataka nekoliko puta brzi od onoga koji bi CPU mogao ostvariti, zahvaljujuci tome sto se istovremeno realizuje citanje i upis podataka.

Procesor pokrece DMAprenos formirajuci blok podataka, kojeg cine pokazivaci, izvor transfera, odredista i broj bajtove koje treba preneti. Procesor prenosi adresu bloka DMA kontroleru i time se prenos realizuje. DMA kontroler aktivira I/O kontroler dajuci mu informacije o planiranom prenosu.

3.	Data je sledeća sekvenca referenci stranica nekog programa:

5,4,3,2,1,4,3,5,4,3,2,1,5,…..

Pokazati, korak po korak, kako će stranice biti dodeljene korišćenjem FIFO algoritma zamene stranica. Takođe, izračunati ukupan broj grešaka stranica za okvire stranica sa 3 i 4 pozicije. U početku su svi okviri prazni.

4.	Objasniti koncept segmentacije memorije. Navesti glavne problem segmentacije memorije.

Segmentacija je sema upravljanja memorijom koja podrzava korisnicki pogled na memoriju. Logicki adresni prostor je skup segmenata. Svaki segment ima ime i duzinu. Adrese definisu ime segmenta i pomeraj u segmentu. Segmenti su numerisani i pozivaju se pomocu broja, umesto po imenu segmenta.

Problem segmentacije memorije jeste sto se slobodna memorija ne moze iskoristiti za smestaj segmenta ukoliko ne postoji dovoljno velika supljina

Q2. (10 poena)

5.	Neka su data dva primerka resursa A, 4 primerka resoursa B i 3 primerka resursa C. Neka proces P1 drži  po jedan primerak resursa B and C i čeka na primerak resursa A. Proces P2 drži jedan primerak resursa A i čeka na jedan primerak resursa B. Proces P3 drži jedan primerak resursa A, dva primerka resursa B i jedan primerak resursa C. Nacrtati graf dodele resursa (resource allocation graph). Da li je sistem u stanju zastoja (deadlock)? Zašto ili zašto ne?

Graf jeste u stanju zastoja jer sadrzi ciklus i svaki tip dodele resursa ima po jednu instancu. Nacrtati nekad mozda.

6.	Detaljno objasniti potrebne uslove za nastajanje zastoja.

-	Uzajamna iskljucenost: najmanje jedan resurs se mora drzati u rezimu gde se ne moze deliti resurs, tj. samo jedan proces u jednom trenutku moze koristiti resurs.
-	Hold and wait: proces mora drzzati najmanje jedan resurs i cekati da stekne dodatne resurse koje trenutno drze drugi procesi.
-	No preemption: resursi se ne mogu oduzeti, tj. resurs moze biti oslobodjen samo dobrovoljno od strane procesa koji ga drzi, nakon sto taj proces zavrsi posao.
-	Kruzna cekanja: skup procesa koji cekaju mora postojati tako da svaki proces ceka resurs koji drzi sledeci proces i tako dok se ne napravi ciklus.

Q3. (20 poena)

1.	Šta je proces? Koju struktura podataka (engl.data structure) koristi OS za praćenje procesa? Opisati komponente te strukture. Dati jasan i precizan odgovor.

Proces je program u statusu izvrsavanja, zajedno sa svim resursima koji su potrebni za rad programa.

2.	Nacrtati dijagram stanja procesa od njegovog kreiranja do terminacije uključujući sve prelaze iz stanja u stanje. Ukratko opisati svako stanje i svaki prelaz.



Postoji ukupno 5 razlicitih stanje. Start i Stop stanja predstavljaju pokretanje i zaustavljanje procesa. Run predstavlja stanje realizacije, tj. procesor izvrsava instrukcije procesa. Ready predstavlja stanje cekanja na procesor i Wait predstavlja stanje cekanja na odredjene operativne ili resursne uslove.

Tranzicije stanja su jednosmerne i dvosmerne. Start-Ready tranzicija je akcija pripreme procesa za rad. Ready-Run tranzicija prevodi proces iz stanja cekanja u stanje izvrsavanja. Run-Ready tranzicija prevodi proces u stanje mirovanja, nakon isteka vremenskog intervala u kome je tom procesu dodeljen procesor. Run-Wait tranzicija prevodi proces u stanje mirovanja dok proces ceka na ispunjenje nekih operativnih ili resursnih uslova.

3.	Objasniti razlike između niti korisnika i niti koje podržava kernel. Dati detaljan odgovor.

Implementacija niti na nivou korisnika (ULT) podrazumeva da sav posao upravljanja nitima vrsi aplikacija i kernel nije svestan postojanja niti. U tom slucaju prebacivanje niti ne zahteva privilegije rezima kernela jer se sve strukture podataka za upravljanje nitima nalaze unutar korisnickog adresnog prostora jednog procesa. Rasporedjivanje moze biti specificno za datu aplikaciju. ULT se moze izvrsavati na svakom operativnom sistemu.

Kod niti nivoa kernela (KLT), na nivou aplikacije ne postoji kod za upravljanje nitima, vec jednostavni programski interfejs aplikacije (API) na objekat niti karnela. U ovom slucaju, kernel odrzava konteksne informacije procesa kao jednu celinu i za pojedinacne niti unutarprocesa. Kernel vrsi rasporedjivanje niti na bazi niti. Same rutine kernela mogu biti visenitne.

4.	Dati oblasti primene i detaljno objasniti tri različita sistemska poziva (engl. system call) koji izvršavaju zadatke OS. Budite precizni u svojim odgovorima.

Tri razlicita sistemska poziva: glavni program koji poziva sistemske procedure; skup sistemskih procedura koje izvrsavaju sistemske pozive; skup pomocnih procedura koje se koriste od strane sistemskih procedura.

Oblasti primene sistemskih poziva jesu da pruzi mogucnost aplikaciji, koja je u toku realizovanja, da pokrene neku od sistemskih rutina ili aplikacija operativnog sistema, da se po realizovanju tog poziva kontrola vrati samoj aplikaicji. Druga oblast primene jeste potreba da se omoguci razdvajanje aplikacije od operativnog sistema sto sprecava sirenje greske van aplikacije i rusenje sistema.

Q4. (10 poena)

1.	Objasniti algoritme FCFS, FIFO, SJF i RR za raspoređivanje procesa i detaljno navesti  nedostatke svakog od njih. Budite jasni i precizni u svojim odgovorima.

FCFS algoritam rasporedjuje pristigle proceses po redosledu pristizanja. Redosled pristizanja procesa utice na srednje vreme cekanja. Mana je to sto ne postoji mogucnost istovremenog posluzivanja i iz tog razloga dolazi do cekanja u prijemu pojedinih procesa.

SJF algoritam pri rasporedjivanju uzima u obzir procenu vremena izvrsavanja pristiglog procesa i obezbedjuje povoljniji izbor sa stanovista smanjenja vremena cekanja i vremena odziva. Procena vremena nije precizna zbog poteskoca predvidjanja cekanja na I/O operacije.

SRT algoritam bira proces koji ima najkrace ocekivano preostalo vreme obrade. Kada se pojavi novi proces u redu cekanja spremnih procesa, u slucaju da taj novi proces ima kracepreostalo vreme od procesa koji se trenutno izvrsava, on moze da prekine tekuci proces kada novi proces postane spreman. Mana je sto postoji rizik od gladovanja duzih procesa.

RR je vrsta FCFS algoritma sa pretpraznjenjem kojim se oslobadjamo problema zahtevnih procesa. Procesi se posluzuju po redosledu dolazenja, ali u ogranicenim vremenskih intervalima. Mana je izvesno usporenje rada zbog samog algoritma i zbog dodatnih gubitaka zbog visestrukog preklapanja.

2.	Objasnti stanje trke (engl. race condition) i detaljno opisati kako kritična sekcija izbegava ovaj uslov.

Stanje trke predstavlja primer deljenja memorijskog segmenta namenjenog za potrebe print spiiler softvera, liste datoteka koje printer treba da stampa. Procedura se sastoji u tome da razliciti procesi dopunjavaju redom listu datoteka, printer povremeno kontrolise stanje na toj listi te redom uzima podatke o fajlovima, istovremeno prazneci te lokacije.

Kriticna sekcija izbegava ovaj uslov tako sto se mora garantovati da u jednom memontu samo jedan proces moze biti u fazi kriticne sekcije. Procesi koji su izvan kriticne sekcije ne smeju sprecavati ulazak drugih procesa u tu fazu. Procesi ne smeju jako dugo cekati da dobiju pravo na ulaz u svoju kriticnu sekciju. Proces ne sme predugo ostati u kriticnoj sekciji i time blokirati druge procese da nastave rad.


Q5. (10 poena)

1.	Detaljno objasniti ulogu prekida (engl. interrupt) i kako ih OS obrađuje.

Tehnika prekida e metoda za obavestavanje operativnog sistema da se neka akcija, to jest I/O komanda, zavrsila. Tehnika prekida obezbedjuje visoke performanske i izlolovanost od I/O uredjaja: DMA prenosi podatke po kanalu, a odgovarajucim prekidnim signalom sistem se obavestava da je transfer zavrsen. Prekidnim signalom se upravljanje centralnim procesorom prenosi na neku drugu lokaciju. Pri tom se cuva prethodna vrednost programskog brojaca, sto omogucava da se prekinuti program nastavi.

2.	Objasniti koncept semafora. Implementirati karakteristiku “međusobnog isključivanja” (engl. mutual exclusion) pomoću semafora i navesti nedostake ove implementacije.

Semafor je deljena integer varijabla. Njegova vrednos je pozivitna ili nula i moze mu se pristupiti samo preko metoda wait(s) i signal(s) gde je s identifikator koji predstavlja semafor. Semafori se implementiraju u kernelu sistema, i njegove vrednosti se cuvaju u tabeli koja se nalazi u memoriji kernela.

while (True){
	nc1:
		wait(s);
	crit1:
		signal(s);
}
nc1 – non critial section
crit1 – critical section

Problemi mogu da nastanu onda kada je implementacija cekanja u semaforu kombinovala sa manipulisanjem drugacije strukture podataka.