OS1/Jul 2014

Zadaci na stranici predmeta.

1. zadatak

Postavka

Šta je bio osnovni motiv za uvođenje raspodele vremena (engl. time-sharing) kod interaktivnih sistema? Objasniti.

Rešenje

Videti zadatak iz februarskog roka 2013.

2. zadatak

Postavka

Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati prevod sledeće rekurzivne funkcije:

int fib (int n) {
    if (n <= 1) return 1;
    else return fib(n - 1) + fib(n - 2);
}

Rešenje

fib:    LD R1, #n[SP]
        LD R0, #1
        CMP R1, R0
        JG else
        RTS
else:   SUB R1, R0
        PUSH R1
        CALL fib
        POP R2
        SUB R1, R0
        PUSH R1
        CALL fib
        POP R0
        ADD R0, R1
        RTS

3. zadatak

Postavka

Ukoliko su svi sistemski pozivi izvršeni uspešno, koliko procesa se ukupno kreira kada se nad sledećim programom kreira jedan proces (računajući i taj jedan)?

void main() {
    for (int i = 0; i < 7; i++)
        if (fork() == 0)
            return;
}

Rešenje

Odgovor: 8

• P1 pravi dete P2 i inkrementira svoje i.
• P2 je dete, te fork() vraća 0 u kontekstu deteta i završava se program.
• P1 pravi dete P3 i inkrementira svoje i.
• P1 pravi dete P4 i inkrementira svoje i.
• P1 pravi dete P5 i inkrementira svoje i.
• P1 pravi dete P6 i inkrementira svoje i.
• P1 pravi dete P7 i inkrementira svoje i.
• P1 pravi dete P8 i inkrementira svoje i.
• P3, P4, P5, P6, P7, P8 se isto završavaju kao proces P2.
• P1 završava svoj for ciklus jer je i postalo 7.

4. zadatak

Postavka

Korišćenjem standardnih brojačkih semafora napisati kod tri uporedna procesa koji sarađuju na sledeći način. Proces A upisuje jednu vrednost u deljenu promenljivu x, a nezavisni proces B uporedo upisuje jednu vrednost u deljenu promenljivu y. Proces C potom čita x i y da bi izračunao njihov zbir. Tek kada je C pročitao x, proces A upisuje novu vrednost u x; tek kada je C pročitao vrednost y, proces B upisuje novu vrednost u y, i tako ciklično.

Rešenje

var: sax : Semaphore := 1, scx : Semaphore := 0, sby : Semaphore := 1, sbc : Semaphore := 0;
     x, y, z : Integer;

process A:
    begin
        loop
            wait(sax);
            x := ...
            signal(scx);
    end;
end A;

process B:
    begin
        loop
            wait(sby);
            y := ...
            signal(scy);
    end;
end B;

process C:
    begin
        loop
            wait(scx);
            z := x;
            signal(sax);
            wait(scy);
            z := z + y;
            signal(sby);
    end;
end A;

5. zadatak

Postavka

Neki program koristi dve velike strukture podataka naizmenično: najpre za neku složenu obradu koristi samo prvu strukturu, pa onda za neku drugu obradu koristi samo drugu strukturu, pa onda ponovo prvu, pa drugu itd. Ako se ove dve strukture učitavaju dinamički i preklapaju se (kod korišćenja preklopa, overlays), u kom slučaju će izvršavanje tog programa trajati duže, a u kom će koristiti više memorije: kada se koristi samo dinamičko učitavanje, ili kada se koriste preklopi? Kratko obrazložiti.

Rešenje

Kod preklopa će izvršavanje trajati duže zbog toliko učitavanja, a dinamičko učitavanje će koristiti više memorije.

6. zadatak

Postavka

Neki sistem primenjuje kontinualnu alokaciju memorije. Kakva je hardverska podrška potrebna za ovaj pristup da bi se obezbedila:

1. relokatibilnost procesa
2. zaštita memorijskog prostora jednog procesa od drugih procesa?

Rešenje

1. Relokatibilnost procesa - mora da obezbedi da je base registar dostupan i za čitanje i za upis, kako bi operativni sistem tu prilikom promene konteksta upisao baznu adresu tekućeg procesa, a u slučaju realokacije procesa operativni sistem menja vrednost bazne adrese za taj proces u svojoj evidenciji koju ima za svaki proces.
2. Zaštita memorijskog prostora - limit registar.

7. zadatak

Postavka

Učestanost pogotka u TLB je 90%, a PMT je organizovana u tri nivoa. TLB je 10 puta brža nego operativna memorija. Za koliko procenata je efektivan pristup memoriji sporiji od pristupa fizičkoj memoriji?

Rešenje

$t_{TLB} = 0.1 t_{RAM}$

$0.9 \cdot (t_{TLB} + t_{RAM}) + 0.1 \cdot (t_{TLB} + 4 \cdot t_{RAM}) = 1.4 t_{RAM}$

Odnos: $\frac{1.4 - 1}{1} = 40\%$

8. zadatak

Postavka

Navesti osnovne operacije klase znakovno-orijentisanih ulazno/izlaznih uređaja (tokova).

Rešenje

1. int getc(FILE * f) Učitava i vraća 1 znak iz ulaznog toka.
2. int putc(int c, FILE * f) Šalje 1 znak na zadati izlazni tok.

9. zadatak

Postavka

Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:

1. int size(FHANDLE) Vraća trenutnu veličinu sadržaja fajla u znakovima.
2. void append(FHANDLE, int) Proširuje sadržaj fajla za dati broj znakova na kraju.
3. void seek(FHANDLE, int) Postavlja kurzor datog fajla na datu poziciju (redni broj znaka počev od 0).
4. void write(FHANDLE, char*, int size) Na poziciju kurzora datog fajla upisuje dati niz znakova zadate dužine, i pomera kurzor iza upisanog niza znakova. Operacije seek i write rade samo u opsegu trenutne veličine sadržaja fajla (ne pomeraju kurzor i ne upisuju iza kraja sadržaja fajla).

Napisati operaciju write(FHANDLE, int position, char*, int size); koja na zadatu poziciju upisuje zadati niz znakova date veličine, pri čemu se fajl implicitno najpre proširuje na potrebnu veličinu ukoliko bi zadata pozicija ili zadati upis prekoračio trenutnu veličinu sadržaja fajla. Zanemariti sve moguće greške u ulazu/izlazu.

Rešenje

void write(FHANDLE f, int position, char* b, int size) {
    int curSize = size(f);
    if (position + size > curSize) {
        append(f, position + size - curSize);
    }
    seek(f, position);
    write(f, b, size);
}

10. zadatak

Postavka

Objasniti kako se u fajl sistemu tipa FAT vodi evidencija o slobnom^[sic] prostoru.

Rešenje

Slobodni blokovi se ulančavaju u listu pokazivača koji se nalaze u svakom bloku. Alokacija jednog bloka je jednostavna. Uzima se prvi blok iz liste. FAT varijanta je inherentna - ulazi za slobodne blokove u FAT su posebno označeni.