ОС1/Фебруар 2014

Zadaci na stranici predmeta.

1. zadatak

Postavka

Objasniti zašto je i kako uvođenje magnetnih diskova bilo od ključnog značaja kod prelaska sa paketnih sistema na sisteme sa multiprogramiranjem.

Rešenje

Operativni sistem može da pristupa disku direktno, u proizvoljnom redosledu, bez značajnih razlika u vremenu odziva kao kod traka (zbog premotavanja) bez obzira na to kako su podaci smešteni na samom disku. Disk je blokovski orijentisan ulazno-izlazni uređaj. Podaci se mogu i učitavati sa diska i upisivati na njega, ali se prenose isključivo u blokovima fiksne veličine. Zbog ovoga je skup poslova koji su podneti na izvršavanje mogao da se snimi na disk a da OS sa njega učitava one koje odluči da će se izvršavati, na osnovu zauzeća procesora i memorije, a ne na osnovu redosleda kojim su podneti.

2. zadatak

Postavka

Objasniti kako se međusobno isključenje kritičnih sekcija jezgra operativnog sistema može obezbediti kod jednosprocesorskih, a kako kod višeprocesorskih sistema.

Rešenje

1. jednosprocesorski sistemi:
   • maskirati prekide
   • zabraniti preuzimanje
   • optimistički pristup
2. višeprocesorski sistemi:
   • test-and-set
   • swap

3. zadatak

Postavka

Korišćenjem standardnih sistemskih poziva fork() i wait() napisati C program koji kreira tačno N procesa svoje dece, gde je N parametar programa, a potom čeka da se sva deca završe. Procesi-deca samo ispišu neku poruku na standardni izlaz i potom se završavaju.

Rešenje

#include <stdio.h>
int main(int argc, char* argv[]) {
    if (argc < 2) {
        return -1;
    }
    int N = atoi(argv[1]);
    int pid[N];
    for (int i = 0; i < N; i++) {
        pid[i] = fork();
        if (pid[i] < 0) {
            return -2;
        } else if (pid[i] == 0) {
            printf("Child %d", i);
            exit(0);
        }
    }
    for (int i = 0; i < N; i++) {
        wait(pid[i]);
    }
    return 0;
}

4. zadatak

Postavka

Korišćenjem standardnih brojačkih semafora napisati kod za sinhronizaciju proizvođača i potrošača sa neograničenim baferom. (Kod za smeštanje i uzimanje elemenata ne treba pisati, već samo naznačiti njegovo mesto.)

Rešenje

Semaphore mutex(1), spaceAvailable(N), itemAvailable(0);

void append(Data* d) {
    spaceAvailable.wait();
    mutex.wait();
    <add>
    mutex.signal();
    itemAvailable.signal();
}

Data* take() {
    itemAvailable.wait();
    mutex.wait();
    <get data>
    mutex.signal();
    spaceAvailable.signal();
    return data;
}

5. zadatak

Postavka

Ukratko objasniti osnovnu razliku između tehnika dinamičkog učitavanja (dynamic loading) i preklopa (overlays).

Rešenje

Videti zadatak iz julskog roka 2011.

6. zadatak

Postavka

Šta je eksterna fragmentacija kod alokacije memorije? Da li je ona moguća kod segmentno-stranične alokacije memorije?

Rešenje

Eksterna fragmentacija nastaje kada se procesi učitavaju u memoriju a zatim dealociraju. Kako se delovi proizvoljnih dimenzija zauzimaju i oslobađaju dinamički, slobodni fragmenti se stvaraju i nazivaju eksternim.

Nije moguća eksterna fragmentacija kod segmentno-stranične organizacije jer alociraju blokovi iste veličine.

7. zadatak

Postavka

U nekom sistemu sa straničnom organizacijom virtuelne memorije virtuelna i fizička adresa su 32-bitne, adresibilna jedinica je bajt, a stranica je veličine 64 KB. PMT je organizovana u dva nivoa i jedan ulaz u PMT oba nivoa zauzima po jednu 32-bitnu reč. PMT oba nivoa su iste veličine. Koliko ukupno zauzimaju PMT za proces koji je alocirao samo svoju prvu i poslednju stranicu?

Rešenje

Videti 7. zadatak iz januarskog roka 2015.

8. zadatak

Postavka

Ukratko objasniti tehniku spooling.

Rešenje

Videti rešenje 6. zadatka iz februara 2013. godine.

9. zadatak

Postavka

Dati procenu kompleksnosti u najgorem slučaju sledećih operacija sa direktorijumom u odnosu na broj postojećih fajlova n u direktorijumu, za navedene implementacije direktorijuma.

Rešenje

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

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 a) indeksna, pri čemu je indeks fajla uvek u dva nivoa, a na blok sa indeksom prvog nivoa ukazuje polje u FCB, b) FAT, pri čemu je cela FAT u memoriji? FCB fajla je u memoriji.

Rešenje

1. 3
2. 1