OS1/Jul 2013

Zadaci na stranici predmeta.

1. zadatak

Postavka

Objasniti pojam raspodele vremena (time sharing) kod multiprocesnih sistema.

Rešenje

Operativni sistem dodeljuje procesoru vreme izvršavanja svakog posla i relativno često preuzima procesor. Osnovna ideja je da posao (engl. task) može da izgubi procesor nakon isteka dodeljenog procesorskog vremena ili kada sam zatraži promenu konteksta. Rezultat je da svaki korisnik ima utisak da računar radi samo za njega sa dovoljno dobrim vremenskim odzivom, dok računar opslužuje više korisnika.

2. zadatak

Postavka

Data je pogrešna implementacija operacije yield() za neki troadresni procesor. Ova operacija bi trebalo da izvrši preuzimanje procesora od niti na čiji vrh steka ukazuje vrednost sačuvana na lokaciji na koju ukazuje argument cur, i predaju procesora niti na čiji vrh steka ukazuje vrednost sačuvana na lokaciji na koju ukazuje argument next. Objasniti zašto ova implementacija nije ispravna i korigovati je.

void yield (void* cur, void* next) {
   asm { 
      push r0
      push r1
      ...
      push rn
      add  r0, sp, #cur
      mov  [r0], sp
      add  r0, sp, #next
      mov  sp, [r0]
      pop  rn
      ...
      pop  r1
      pop  r0
      pop  pc ; return
   } 
}

Rešenje

Umesto add r0, sp, #cur treba napisati mov r0, #cur[sp], tj. u r0 treba upisati adresu sp pa ubaciti na tu adresu sp. Umesto add r0, sp, #next treba napisati mov r0, #next[sp], tj. u r0 treba upisati adresu novog sp.

3. zadatak

Postavka

Korišćenjem sistemskog poziva fork(), napisati program koji, kada se pokrene kao proces, kreira onoliko procesa-dece, koliko je dato argumentom tog programа. Ni taj proces, ni njegova deca ne treba da rade ništa više.

Rešenje

int main(int argc, char* argv[]) {
    if (argc < 2) {
        return -1;
    }
    int N = atoi(argv[1]);
    for (int i = 0; i < N; i++) {
        if (fork() == 0) {
            return 0;
        }
    }
    return 0;
}

4. zadatak

Postavka

Data dva procesa međusobno se iključuju^[sic] pri ulazu u dve kritične sekcije pomoću semafora čija je inicijalna vrednost 1. Objasniti šta je problem ove implementacije.

process P1;  	  process P2: 
  wait(S1);         wait(S2); 
  wait(S2);         wait(S1); 
    ...               ... 
  signal(S2);       signal(S1); 
  signal(S1);       signal(S2); 
end P1;           end P2;

Rešenje

Problem je što će doći do mrtvog blokiranja, odnosno, moguće je da P1 i P2 prođu prvi wait jer je inicijalna vrednost semafora 1 ali će se zatim blokirati na drugim wait() pozivima.

5. zadatak

Postavka

Koju uslugu operativni sistem treba da obezbedi procesima da bi oni koristili preklope (overlays)?

Rešenje

Preklopi ne zahtevaju podršku operativnog sistema. Sve obavlja prevodilac i generisani kod. Operativni sistem samo obezbeđuje usluge za alokaciju dela virtuelnog adresnog prostora.

6. zadatak

Postavka

Data je definicija strukture FreeSegment koja predstavlja jedan segment slobodne memorije. Ove strukture uvezane su u dvostruko ulančanu, neuređenu listu čija je glava freeSegHead. Implementirati funkciju getWorstFit(size_t) koja treba da pronađe i vrati (ali ne menja ni njega ni listu) segment slobodne memorije u koji se može smestiti blok date veličine, po worst fit algoritmu.

struct FreeSegment {
  size_t size;
  FreeSegment *prev, *next;
};

Rešenje

FreeSegment* getWorstFit(size_t size) {
    FreeSegment* curr = freeSegHead;
    FreeSegment* max = NULL;
    size_t maxSize = 0;
    while (curr) {
        if (curr->size >= size && curr->size > maxSize) {
            max = curr;
            maxSize = curr->size;
        }
        curr = curr->next;
    }
    return max;
}

7. zadatak

Postavka

Neki računar podržava segmentno-straničnu organizaciju virtuelne memorije, pri čemu je virtuelna adresa 16-bitna, fizički adresni prostor je veličine 8GB, a adresibilna jedinica je 16-bitna reč. Stranica je veličine 512B. Maksimalan broj segmenata u virtuelnom adresnom prostoru je 4. Prikazati logičku strukturu virtuelne i fizičke adrese i navesti širinu svakog polja.

Rešenje

VA(16):= seg(2):page(6):offset(8) PA(32):= frame(24):offset(8)

8. zadatak

Postavka

Kojom tehnikom se fizički nedeljiv izlazni uređaj može učiniti logički (virtuelno) deljivim između procesa koji ga uporedo koriste?

Rešenje

Spooling.

9. zadatak

Postavka

Napisati punu stazu (path) do fajla resenja.doc koji se nalazi u direktorijumu d:/nastava/os/ispiti/jul2013 na uređaju d: posle sledeće operacije montiranja (prvi argument je fajl sistem koji montira, drugi je odredište montaže): mount d: /etf/rti

Rešenje

/etf/rti/nastava/os/ispiti/jul2013

10. zadatak

Postavka

Neki fajl sistem koristi indeksiranu alokaciju fajlova na disku sa jednostrukim indeksom. Ako se pretpostavlja da je prostor za smeštanje fajlova (uključujući i njihove indekse) na disku veličine 32 GB, veličina klastera (jedine jedinice alokacije) 2 KB, i ceo prostor potpuno ispunjen fajlovima, gde je svaki fajl maksimalne veličine i ima samo jedan indeksni klaster, koliki procenat ukupnog prostora za smeštanje fajlova na ovom disku zauzimaju indeksi?

Rešenje

Videti zadatak iz oktobarskog roka 2012.