ОС1/Јун 2012

Zadaci na stranici predmeta.

1. zadatak

Postavka

Šta je to sistem sa raspodelom vremena (engl. time-sharing)?

Rešenje

Sistem sa raspodelom vremena je sistem u kome OS dodeljuje procesor nekom procesu na određeno vreme, zatim se procesu preotima procesor, vrši promena konteksta i procesor predaje drugom procesu kome se ponovo ograničava vreme izvršavanja. Na ovaj način procesi dele vreme na procesoru.

2. zadatak

Postavka

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

int f (int n) { 
    if (n <= 0) return 0;
    else return f(n - 1) + 1; 
}

Rešenje

f:    LD R0, #0      ;Registar u kome se nalazi povratna vrednost
      LD R1, #n[SP]
      CMP R1, R0
      JG else
      RTS
else: LD R2, #1
      SUB R1, R2
      PUSH R1
      call f         ;nakon zavrsetka funkcije f, u R0 se nalazi rezultat
      POP R1
      ADD R0, R2
      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

Pošto samo dete nastavlja dalje, a pravi se 7 dece, ukupno ima 8 procesa.

4. zadatak

Postavka

Korišćenjem standardnih brojačkih semafora napisati kod dva uporedna procesa koji sarađuju na sledeći način. Proces A upisuje jednu vrednost u deljenu promenljivu x, koju proces B potom čita. Tek kada je B pročitao tu vrednost, proces A upisuje novu vrednost u x, koju proces B onda čita, i tako ciklično

Rešenje

shared var x : Integer;
           semA : Semaphore := 0;
           semB : Semaphore := 0;

process A
    begin
        loop
            x = ...
            signal(semB);
            wait(semA);
        end
    end
end A;

process B
    begin
        loop
            wait(semB);
            y = ...
            signal(semA);
        end
    end
end B;

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 učitavanja, a dinamičko učitavanje će koristiti više memorije.

6. zadatak

Postavka

Neki sistem primenjuje kontinualnu alokaciju memorije i best-fit algoritam alokacije, pri čemu su segmenti slobodne memorije organizovani u sledeću strukturu podataka:

1. sortiranu ulančanu listu,
2. balansirano binarno stablo.

Koliko segmenata treba obići u najgorem slučaju da bi se pronašao odgovarajući slobodan segment prilikom alokacije, ukoliko je slobodnih segmenata n?

Rešenje

1. $n$
2. $log_{2}(n)$

7. zadatak

Postavka

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

Rešenje

$0.9 \cdot (0.1 t_{RAM} + t_{RAM}) + 0.1 \cdot (0.1t_{RAM} + 3t_{RAM}) = 1.3t_{RAM}$

Odgovor: $30\%$

8. zadatak

Postavka

Navesti osnovne operacije klase blokovski orijentisanih uređaja sa direktnim pristupom.

Rešenje

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

9. zadatak

Postavka

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

• int size(FHANDLE) Vraća trenutnu veličinu sadržaja fajla u znakovima.
• void append(FHANDLE, int) Proširuje sadržaj fajla za dati broj znakova na kraju.
• void seek(FHANDLE, int) Postavlja kurzor datog fajla na datu poziciju (redni broj znaka počev od 0).
• 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* s, int size){
    int curSize = size(f);
    if(position + size > curSize){
        append(f, position + size - curSize);
    }
    seek(f, position);
    write(f, s, size);
}

10. zadatak

Postavka

Koliko pristupa blokovima na disku treba izvršiti za pristup n-tom logičkom bloku sadržaja fajla ako je alokacija fajla:

1. ulančana lista blokova, pri čemu na prvi blok sadržaja fajla ukazuje polje u FCB,
2. indeksna, pri čemu je indeks fajla uvek u dva nivoa, a na blok sa indeksom prvog nivoa ukazuje polje u FCB? FCB fajla je u memoriji

Rešenje

1. n
2. 3