Изворни код странице ОС1/Јун 2012

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2012/jun/Jun%202012.pdf 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: 
<syntaxhighlight lang="c">
int f (int n) { 
    if (n <= 0) return 0;
    else return f(n - 1) + 1; 
}
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="asm">
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
</syntaxhighlight>

== 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)?
<syntaxhighlight lang="c">
void main() {
    for (int i = 0; i < 7; i++) if (fork() > 0) return;
}
</syntaxhighlight>

=== 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 ===
<syntaxhighlight lang="pascal">
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;
</syntaxhighlight>

== 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:
# sortiranu ulančanu listu,
# 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 ===
# <math>n</math>
# <math>log_{2}(n)</math>

== 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 ===
<math>0.9 \cdot (0.1 t_{RAM} + t_{RAM}) + 0.1 \cdot (0.1t_{RAM} + 3t_{RAM}) = 1.3t_{RAM}</math>

Odgovor: <math>30\%</math>

== 8. zadatak ==
=== Postavka ===
Navesti osnovne operacije klase blokovski orijentisanih uređaja sa direktnim pristupom.

=== Rešenje ===
{{delimično rešeno}}

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
* <syntaxhighlight lang="c" inline>int size(FHANDLE)</syntaxhighlight> Vraća trenutnu veličinu sadržaja fajla u znakovima. 
* <syntaxhighlight lang="c" inline>void append(FHANDLE, int)</syntaxhighlight> Proširuje sadržaj fajla za dati broj znakova na kraju.
* <syntaxhighlight lang="c" inline>void seek(FHANDLE, int)</syntaxhighlight> Postavlja kurzor datog fajla na datu poziciju (redni broj znaka počev od 0).
* <syntaxhighlight lang="c" inline>void write(FHANDLE, char*, int size)</syntaxhighlight> Na poziciju kurzora datog fajla upisuje dati niz znakova zadate dužine, i pomera kurzor iza upisanog niza znakova.

Operacije <code>seek</code> i <code>write</code> rade samo u opsegu trenutne veličine sadržaja fajla (ne pomeraju kurzor i ne upisuju iza kraja sadržaja fajla). Napisati operaciju 

<code>write(FHANDLE,int position,char*,int size);</code>

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 ===
<syntaxhighlight lang="c">
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);
}
</syntaxhighlight>

== 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:
# ulančana lista blokova, pri čemu na prvi blok sadržaja fajla ukazuje polje u FCB,
# 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 ===
# n
# 3

[[Категорија:Рокови]]
[[Категорија:ОС1]]