ОС1/Фебруар 2013

Zadaci na stranici predmeta.

1. zadatak

Postavka

Neki interaktivni višeprocesni i višekorisnički sistem ne podržava raspodelu vremena (time sharing). Šta je njegov osnovni problem?

Rešenje

Osnovni problem je nejednakost u vremenu odziva na korisničku akciju. Ukoliko je više procesa spremno i treba da obradi korisničku akciju, oni procesi koji ranije dobiju procesor imaće kraće vreme odziva, dok oni koji kasnije dobiju procesor imaju duže vreme odziva. Još gore, vreme odziva istog procesa na sukcesivne korisničke akcije potpuno je nedeterminističko i zavisi od toga kako se rasporede procesi čineći da se korinsici osećaju kao da "smetaju" jedni drugima.

2. zadatak

Postavka

Ako se nad sledećim programom kreira jedan proces, koliko će ukupno biti elemenata sa vrednošću 0 u nizovima pid svih kreiranih procesa (uključujući i taj jedan početni) kada svi ti procesi izađu iz petlje, pod pretpostavkom da su svi sistemski pozivi uspeli?

const int N = 2; 
int pid[N];
void main() {
    for (int i = 0; i < N; i++)
        pid[i] = fork();
}

Rešenje

Videti rešenje 2. zadatka iz junskog roka 2013. godine. (Pitanje je obrnuto, ali je rešenje isto.)

3. zadatak

Postavka

Šta je problem sledeće implementacije kritične sekcije uposlenim čekanjem?

process P1
  loop
    while flag2 = true do null end; (* Busy wait *)
    flag1 := true;
    <critical section>          (* Critical section *)
    flag1 := false;             (* Exit protocol *)
    <non-critical section>
  end
end P1;

process P2
  loop
    while flag1 = true do null end; (* Busy wait *)
    flag2 := true;
    <critical section>          (* Critical section *)
    flag2 := false;             (* Exit protocol *)
    <non-critical section>
  end
end P2;

Rešenje

Problem je u tome što ovo rešenje uopšte ne obezbeđuje međusobno isključenje jer oba procesa mogu da uđu u kritičnu sekciju.

4. zadatak

Postavka

Dva procesa X i Y "proizvode" cele brojeve uporedo, nezavisnim i promenljivim brzinama. Proces Z treba da uzima po dva proizvedena broja, i to uvek tačno jedan koji je proizveo X i jedan koji je proizveo Y, i njihov zbir ispisuje na standardni izlaz. Važno je obezbediti da proces Z uvek uzima samo "sveže" proizvedene brojeve, tj. nikada ne uzme više puta isti proizvedeni broj. Korišćenjem deljenih promenljivih i klasičnih brojačkih semafora, napisati sve potrebne deklaracije i kod procesa X i Z.

Rešenje

Potrebno je X i Y implementirati kao bounded buffer jer mogu proizvoditi cele brojeve različitim brzinama. Proces Z će jednostavno pozivati operaciju take() nad tim dvama baferima.

5. zadatak

Postavka

U prvom prolazu kroz ulazne .obj fajlove, linker nailazi na izvezeni simbol koji se već nalazi u njegovoj tabeli simbola. Da li će to prijaviti kao grešku?

Rešenje

Da, jer ako se nalazi u tabeli simbola znači da je već definisan i dolazi do sukoba imena.

6. zadatak

Postavka

Da li kod stranične organizacije virtuelne memorije ima smisla hardverski vršiti proveru prekoračenja granice opsega dozvoljenih adresa unutar stranice radi zaštite od nedozvoljenog pristupa fizičkim adresama koje koriste drugi procesi? Kratko obrazložiti.

Rešenje

Nema potrebe, kod stranične organizacije veličina stranice u virtuelnoj memoriji je ista kao veličina okvira u fizičkoj memoriji tako da se ne može desiti da isti okvir dele 2 različita procesa, niti da je jedna stranica preslikana u 2+ okvira.

7. zadatak

Postavka

U nekom sistemu postoje sledeći sistemski pozivi:

int async_write (char* buffer);
void wait (int request_id);

Operacija async_write asinhrono zadaje operaciju izlaza datog niza znakova na neki izlazni uređaj i vraća interni sistemski identifikator tog zahteva (veći od 0), odnosno kod greške (manji od nula). Operacija wait suspenduje pozivajući proces sve dok operacija sa datim identifikatorom nije završena. Korišćenjem ovih sistemskih poziva, realizovati sinhroni izlaz:

int sync_write (char* buffer);

Rešenje

Videti rešenje 5. zadatka iz avgusta 2020. godine.

8. zadatak

Postavka

Ukratko objasniti šta je spooling.

Rešenje

Kada neki nedeljivi spori uređaj želi da odradi posao, prvo se zatraži korišćenje tog uređaja sistemskim pozivom, OS tada pravi poseban fajl na određenom mestu u svom fajl sistemu u koji će preusmeriti sve ulazne operacije tog procesa sa štampaem i vraća kontrolu procesu. OS predaje fajl na obradu posebnom procesu ili niti (spuleru) koji će jedan po jedan fajl da uzima i njihove sadržaje da šalje datom uređaju.

9. zadatak

Postavka

Neki fajl sistem podržava implicitno zaključavanje fajla prilikom njegovog otvaranja. Postoje dve vrste ključa: deljeni (shared), koji se traži prilikom otvaranja fajla samo za čitanje (proces koji je tako otvorio fajl ima pravo samo da čita iz fajla) i ekskluzivni (exclusive), koji se traži prilikom otvaranja fajla i za upis (proces koji je otvorio fajl ima pravo upisa). Popuniti sledeću tabelu upisivanjem oznaka onih procesa čiji će zahtev za otvaranjem istog fajla biti ispunjen, za svaki od dva data slučaja. Procesi postavljaju zahteve redom navedenim u drugoj koloni, pri čemu oznaka npr. A-Rd označava da proces A postavlja zahtev za otvaranjem fajla za čitanje, a B-Wr da proces B postavlja zahtev za otvaranjem fajla za upis

1. A-Rd, B-Wr, C-Rd, D-Rd, E-Wr
2. A-Wr, B-Rd, C-Wr, D-Rd, E-Rd

Rešenje

1. A, C i D su uspeli da otvore fajl.
2. Samo A je uspeo da otvori fajl.

10. zadatak

Postavka

Neki fajl sistem koristi indeksirani pristup alokaciji blokova za fajlove sa indeksima u dva nivoa. Prvi nivo indeksa smešten je u sam FCB (file control block) i ima 256 ulaza koji direktno referenciraju blokove sa podacima, a još jedan ulaz u FCB ukazuje na jedan blok sa indeksom drugog nivoa čiji ulazi takođe ukazuju na blokove sa podacima. Veličina ulaza u indeksnom bloku (reference na blok diska) je 8 bajtova, a veličina bloka na disku je 512KB. Kolika je maksimalna veličina fajla u ovom fajl sistemu?

Rešenje

• Broj ulaza: $\frac{512KB}{8B} = 64K = 2^{16}$
• Maksimalna veličina fajla: $(256 + 2^{16}) \cdot 512KB = 2^{27} + 2^{35} = 32GB + 128MB = 32.125GB$