OS1/Jun 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 deljenja vremena.

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.

Rešenje

Slučaj	Tekući proces prelazi u stanje	Uzrok (prekid ili sistemski poziv)
Istek vremenskog kvantuma kod time-sharing sistema	ready	prekid
Operacija wait na semaforu koji ima vrednost 0	blocked	sistemski poziv
Došlo vreme aktivacije prioritetnijeg periodičnog procesa	ready	prekid

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

Videti rešenje 5. zadatka iz jula 2017. godine.

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

• Virtuelni adresni prostor je $2^{33}B$, a adresibilna jedinica dva bajta, tako da dobijamo da je virtuelna adresa 32 bita.
• Veličina stranice je $32KB = 2^{15}B$, tako da je za stranicu u virtuelnoj adresi potrebno odvojiti 14 bita.
• Fizički adresni prostor je $2GB = 2^{31}B$, tako da je fizička adresa 30 bitova.
• PMT prvog nivoa ima $2K = 2^{11}$ ulaza, tako da je to 11 bita adrese potrebno za PMT prvog nivoa.
• Iz toga dobijamo da je struktura VA: page1(11) page2(7) offset(14)
• Za 128 stranica potreban je jedan PMT prvog nivoa i jedan drugog, tako da je to ukupno $2^{11} * 2^2B + 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 access violation, 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.