ОС1/Октобар 2012

Zadaci na stranici predmeta.

1. zadatak

Postavka

Šta je multiprocesorski, a šta distribuirani sistem?

Rešenje

Videti prvi zadatak iz julskog roka 2012. godine.

2. zadatak

Postavka

Data je operacija yield(jmp_buf old, jmp_buf new) koja čuva kontekst niti čiji je jmp_buf dat kao prvi argument, oduzima joj procesor i restaurira kontekst niti čiji je jmp_buf dat kao drugi argument, kojoj predaje procesor. Koristeći ovu operaciju, realizovati operaciju dispatch() koja ima isti efekat kao i ona data u školskom jezgru.

Rešenje

void dispatch () {
    lock();
    jmp_buf old = Thread::running->context;
    Scheduler::put(Thread::running);
    Thread::running = Scheduler::get();
    jmp_buf new = Thread::running->context;
    yield(old,new);
    unlock();
}

3. zadatak

Postavka

Kako se u kodu koji se izvršava nakon sistemskog poziva fork() može znati da li se taj kod izvršava u kontekstu procesa-roditelja ili procesa-deteta? Objasniti i dati primer.

Rešenje

Može se znati u kom se kontekstu izvršava kod na osnovu povratne vrednosti fork-a. Tj. 0 u kontekstu deteta, vrednost veća od 0 u kontekstu roditelja, a manja od 0 ako dođe do greške.

int main(int argc, char* argv[]) {
    pid_t pid = fork();
    if (pid < 0) {
        return -1; 
        // greška
    } else if (pid == 0) {
        // dete
    } else {
        // roditelj
    }
    return 0;
}

4. zadatak

Postavka

Napisati kod jednog od dva procesa koji pristupaju kritičnoj sekciji sa međusobnim isključenjem pomoću uposlenog čekanja (busy waiting) Petersonovim algoritmom.

Rešenje

process P1:
    begin
        loop
            flag1 := true; turn := 2;
            while flag2 and turn = 2 do null;
            <critical section>
            flag1 := false;
            <non-critical section>
        end
    end
end P1;

process P2:
    begin
        loop
            flag2 := true; turn := 1;
            while flag1 and turn = 1 do null;
            <critical section>
            flag2 := false;
            <non-critical section>
        end
    end
end P2;

5. zadatak

Postavka

Date su sledeće deklaracije u jednom izvornom C fajlu. Koji od ovih simbola će biti označeni kao „izveženi“, a koji kao „uveženi“ u .obj fajlu?

extern int a(int);
void b(int);
void b(int) {}
void c(int);
extern int d;
static int e;
int f;

Rešenje

• Uveženi: a, c, d
• Izveženi: b, f

6. zadatak

Postavka

Neki sistem koristi kontinualnu alokaciju operativne memorije. Data je deklaracija strukture podataka koja predstavlja zaglavlje svakog slobodnog fragmenta memorije. Ova zaglavlja čine dvostruko ulančanu listu slobodnih fragmenata i upisuju se na sam početak svakog slobodnog fragmenta memorije. Napisati telo funkcije getFirstFitFragment() koja treba da pronađe fragment slobodne memorije veličine date argumentom po first-fit algoritmu i vrati njegovu adresu. Preostali deo fragmenta treba da postane novi (manji) fragment u listi slobodnih

typedef unsigned int size_t;
struct FreeFragment {
    size_t size; // Veličina fragmenta u jedinicama sizeof(char)
    FreeFragment* prev; // Prethodni u listi
    FreeFragment* next; // Sledeći u listi
}
FreeFragment* head; // Glava liste slobodnih fragmenata 
void* getFirstFitFragment(size_t);

Rešenje

void* getFirstFitFragment(size_t sz) {
    if (head == 0 || sz == 0) {
        return 0;
    }
    for (FreeFragment* cur = head; cur; cur = cur->next) {
        if (cur->size < sz) {
            continue;
        }
        FreeFragment* newFrg = (FreeFragment*)((char*)cur + sz);
        if (cur->prev) {
            cur->prev->next = newFrg;
        } else {
            head = cur->next;
        }
        if (cur->next) {
            cur->next->prev = newFrg;
        }
        newFrg->prev = curr->prev;
        newFrg->next = curr->next;
        newFrg->size = cur->size - sz;
        return cur;
    }
    return 0;
}

7. zadatak

Postavka

Objasniti šta je osnovni motiv i pogodnost tehnike straničenja u više nivoa u odnosu na straničenje u jednom nivou?

Rešenje

Veći kapacitet virtuelne memorije.

8. zadatak

Postavka

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

Rešenje

Spooling-om.

9. zadatak

Postavka

Neki proces otvara neki fajl samo za čitanje, iako „vlasnik“ tog procesa ima i pravo upisa u taj fajl. Da li se informacija da je taj proces otvorio taj fajl samo za čitanje čuva u tabeli otvorenih fajlova koja je globalna za sve procese, ili u onoj koja je lokalna za taj proces

Rešenje

Ta informacija čuva se u tabeli otvorenih fajlova lokalnoj za taj proces.

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 tako da je svaki fajl maksimalne veličine takve da ima samo jedan indeksni klaster, koliki procenat ukupnog prostora za smeštanje fajlova na ovom disku zauzimaju indeksi?

Rešenje

• $\frac{32GB}{2KB} = 16M = 2^{24} \implies 3B$ adresa
• $\frac{2KB}{3B} = 682$ ulaza u indeksu
• Procenat zauzetosti: 100/(682 + 1)%