ОС1/Јун 2016

Zadaci na stranici predmeta.

1. zadatak

Postavka

Šta se smatralo najvećim nedostatkom prvobitnih paketnih (batch) sistema i kako je taj nedostatak rešen?

Rešenje

Prvobitni batch sistemi su efikasno delili resurse ali nisu interaktivni. Osnovni nedostatak bio je slabo iskorišćenje glavnog resursa računara - procesora. Nedostatak je rešen uvođenjem time sharing-a

2. zadatak

Postavka

Korišćenjem funkcije yield(jmp_buf old, jmp_buf new) koja čuva kontekst jedne niti i predaje procesor drugoj niti, realizovati operaciju wait na brojačkom semaforu u školskom jezgru

Rešenje

Videti zadatak iz oktobarskog roka 2013.

3. zadatak

Postavka

Za sledeće slučajeve navesti u koje stanje prelazi tekući (running) proces i naznačiti da li se to dešava kao posledica sistemskog poziva od strane tog tekućeg procesa ili spoljašnjeg prekida.

4. zadatak

Postavka

Napisati kod koji realizuje Petersonov algoritam međusobnog isključenja dva uporedna procesa pomoću uposlenog čekanja.

Rešenje

shared var turn : integer := 1, flag1, flag2 : boolean := false;

process P1 
begin 
  loop 
    flag1 := true; turn := 2; 
    while flag2 and turn = 2 do null; 
    <critical section> 
    flag1 := false; 
    <non-critical section> 
  end 
end P1;

process P2 
begin 
  loop 
    flag2 := true; turn := 1; 
    while flag1 and turn = 1 do null; 
    <critical section> 
    flag2 := false; 
    <non-critical section> 
  end 
end P2;

5. zadatak

Postavka

Precizno objasniti zašto klasičan linker svoj posao obavlja u dva prolaza (a ne može samo u jednom). Obrazloženje ilustrovati primerom.

Rešenje

U prvom prolazu linker pravi globalnu mapu .obj fajlova i globalno definisanih izvezenih simbola i njihovih adresa relativno u odnosu na početak .obj fajla. U drugom prolazu razrešava nerazrešena adresna polja koristeći definisane simbole u tabeli simbola.

6. zadatak

Postavka

Virtuelni adresni prostor sistema je 8GB, adresibilna jedinica je 16-bitna reč, a virtuelni adresni prostor je organizovan stranično sa stranicom veličine 32KB. Fizički adresni prostor je veličine 2GB. Tabele preslikavanja stranica su organizovane u dva nivoa, s tim da tabela prvog nivoa ima 2K ulaza. Svaki ulaz u PMT oba nivoa zauzima samo onoliko koliko je potrebno da se smesti broj okvira (PMT drugog nivoa je poravnata na okvir). Koliko memorije zauzimaju ukupno PMT procesa koji je alocirao svojih prvih 128 stranica?

Rešenje

VAS: 2^33B -> VA: 32b, page size 32KB = 2^15B -> page 14b, AU = 2B

PAS: 2GB = 2^31B -> PA: 30b

PMT1: 2K = 2^11 -> 11b

VA: page1(11) : page2(7) : offset(14)

128 stranica -> PMT1 i 1 PMT2 = 2^11 * 2^2 + 2^7 * 2^2 = 8.5KB

7. zadatak

Postavka

Neki sistem sa straničnom organizacijom memorije koristi tehniku copy on write. Jedan proces je tek kreirao drugi proces pozivom fork(). Ako novokreirani proces odmah po pokretanju izvrši operaciju upisa u memoriju, koji izuzetak će generisati procesor, page fault ili neki drugi i koji? Precizno objasniti zašto i kako.

Rešenje

Procesor će generisati izuzetak write prohibited, jer je u desktriptoru ove stranice označeno da ona nije dozvoljena za upis zbog tek kreiranog procesa deteta.

8. zadatak

Postavka

Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji prenosi blok podataka zadate dužine sa zadate adrese na izlazni uređaj korišćenjem programiranog ulaza/izlaza sa prozivanjem (polling).

Rešenje

		LD R1, blockAddr
		LD R2, cnt
		ST [ctrl], #0..1
wait:	LD R0, [status]
		AND R0, #1..0
		JZ wait
		LD R0, [R1]
		ST [data], R0
		INC R1
		DEC R2
		JNZ wait
		ST [ctrl], R0

9. zadatak

Postavka

Ako fajl sistem koristi dve vrste ključeva, deljeni (shared) i ekskluzivni (exclusive), sa implicitnim zaključavanjem prilikom otvaranja fajla, koji ključ će biti zahtevan od strane procesa koji otvara fajl sa najavom samo operacije čitanja?

Rešenje

Deljeni (shared) ključ.

10. zadatak

Postavka

Neki sistem evidentira slobodne blokove fajl sistema tako što u jedan slobodan blok smešta spisak (indeks) do n narednih slobodnih blokova (najmanje 0, najviše n), kao i broj sledećeg takvog indeksnog bloka. Koliki je broj blokova kojima sistem treba da pristupi (na čitanje ili upis) u najgorem slučaju prilikom alokacije jednog slobodnog bloka za sadržaj fajla? Broj prvog takvog bloka u lancu je globalni podatak koji se nalazi u memoriji i njegova eventualna izmena se ne broji.

Rešenje

Broj blokova kojima sistem treba da pristupi je u svakom slučaju 1. Kada se na spisku nalazi bar jedan slobodan blok, on se alocira i briše sa spiska. Kada se na spisku ne nalazi nijedan slobodan blok, blok u kome se nalazi spisak se alocira kao slobodan blok i u memoriji se menja pokazivač sa njega na sledeći blok sa spiskom.