OS1/Jul 2021

Zadaci na stranici predmeta. Svi zadaci vrede 3 poena.

1. zadatak

Postavka

Šta je preotimanje procesora (engl. preemption) i koji hardverski mehanizam ga omogućuje? Šta se postiže uvođenjem ove tehnike u računarske sisteme?

Rešenje

• Preotimanje procesora je prekidanje izvršavanja jednog procesa na procesoru da bi se izvršio kernel kod ili neki drugi proces.
• Mehanizam prekida omogućuje preotimanje procesora - procesor dobija signal da prekine trenutni proces i pređe na kod kernela. Preotimanjem se postiže multiprogramiranje sa boljom raspodelom vremena i vremenom odziva.

2. zadatak

Postavka

Dat je potpis jednog sistemskog poziva na sistemima nalik sistemu Unix. Kratko, ali prezino objasniti šta radi ovaj sistemski poziv i značenje svakog parametra i rezultata.

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

Rešenje

mmap je sistemski poziv koji mapira fajl ili uređaj u memoriju. Značenja parametara:

• void *addr je (željena) početna adresa mapiranja. Ukoliko je NULL, operativni sistem sam bira početnu adresu.
• size_t length je dužina mapirane memorije
• int prot je fleg koji označava dozvoljene načine pristupa mapiranoj memoriji (da li sme da se čita, upisuje, izvršava) i mora se slagati sa načinom pristupa fajla.
• int flags je fleg koji označava da li je mapirana memorija vidljiva ostalim procesima koji mapiraju isti fajl, da li se promene u memoriji upisuju u fajl itd.
• int fd je ručka fajla
• off_t offset je pomeraj od početka fajla od kojeg se vrši mapiranje

Ukoliko je poziv uspešan, vraća se void pokazivač na memoriju koja je mapirana.

3. zadatak

Postavka

Šta se postiže tehnikom “kopiranja pri upisu” kod upravljanja memorijom? Kratko, ali precizno objasniti način rada ove tehnike.

Rešenje

Tehnikom copy-on-write postiže se ušteda memorije, tako što se memorija koja se koristi u više procesa ne kopira dok je jedan proces ne promeni. Implementira se tako što se deskriptor logičkog segmenta koji se deli između procesa označi kao dozvoljen za upis, ali u ulazu PMT-a kao zabranjen za upis. U situaciju kada se desi upis, hardver generiše izuzetak koji se obrađuje od strane OS-a. OS zaključuje da se radi o kopiranju pri upisu iz deskriptora logičkog segmenta i vrši kopiranje, usmeravanje PMT-a drugog procesa na kopiju i u deskriptorima stranica obe kopije dozvoljava upis.

4. zadatak

Postavka

Ako se nad sledećim programom kreira jedan proces, koliko će ukupno biti elemenata sa vrednošću različitom od 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

fork() u kontekstu roditelja vraća pravi pid deteta, a u kontekstu deteta vraća 0. Odgovor je 4: child1 i child3 u parent, child2 u child1 i child1 u child3.

Objašnjenje

5. zadatak

Postavka

Dokazati da Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa uposlenim čekanjem zaista obezbeđuje međusobno isključenje, odnosno ne poseduje problem utrkivanja (engl. race condition). (Dati kod samo jednog procesa sa međusobnim isključenjem pomoću ovog algoritma.)

Rešenje

Petersonov algoritam:

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;

Pretpostavimo da algoritam ne obezbeđuje međusobno isključenje. Ako algoritam NE obezbeđuje međusobno isključenje, dogodiće se situacija da su oba procesa ušla u kritičnu sekciju. Ako se to desilo, to znači da su oba uslova petlji uposlenog čekanja false. Pošto oba procesa odmah pred ulazak u petlju postavljaju svoj flag na true, jedini način da uslov za petlju bude netačan je da uslov sa turn bude netačan, a pošto su oba uslova netačna, to bi značilo da promenljiva turn nema ni vrednost 1 ni vrednost 2. Pošto promenljivu turn koriste samo ova dva procesa i samo postavljaju vrednost na 1 ili 2, do ovoga nikako ne može doći. Time dobijamo kontradikciju na početnu pretpostavku i dobijamo da algoritam zaista omogućava međusobno isključenje.

6. zadatak

Postavka

Šta je simbolička veza (symbolic link, soft link) u fajl sistemu? Kako se ona implementira?

Rešenje

Simbolička veza je veza do nekog fajla u fajl sistemu koja se ne ažurira automatski. Implementira se kao fajl sa posebnim tretmanom od strane operativnog sistema i u sebi sadrži apsolutnu i relativnu putanju do nekog fajla u fajl sistemu. Razlikuje se od tvrde veze tako što ne pokazuje direktno do FCB-a i može da postane prekinuta tj. landarava, ako se target fajl premesti ili preimenuje.

7. zadatak

Postavka

Neki fajl sistem koristi bit vektor za evidenciju slobodnih blokova na disku. Kolika je veličina ovog vektora u bajtovima, za disk veličine 16 TB sa blokom veličine 512B.

Rešenje

• 16 TB = 2⁴ * 2⁴⁰ B = 2⁴⁴ B.
• 2⁴⁴ B / 512 B = 2⁴⁴ B / 2⁹ = 2³⁵ blokova.
• 2³⁵ / 8 bita u B = 2³² = 2² * 2³⁰ = 4 GB.