OS1/Jun 2018

Zadaci na stranici predmeta.

1. zadatak

Postavka

Objasniti razliku između pojmova proces i nit (engl. thread).

Rešenje

Proces je jedno izvršavanje programa sa jednim adresnim prostorom. Nit (thread) ili laki proces je tok kontrole koji teče uporedo sa drugim tokovima kontrole, ali koji deli virtuelni adresni prostor sa nekim drugim tokom ili tokovima kontrole.

2. zadatak

Postavka

Korišćenjem standardnih bibliotečnih operacija setjmp i longjmp, implementirati operaciju wait na binarnom semaforu koji je realizovan klasom Event poput one u školskom jezgru.

Rešenje

void Event::wait() {
    if (val == 1) {
        val = 0;
    } else {
        if (setjmp(Thread::running->context) == 0) {
            blocked.put(running);
            Thread::running = Scheduler::get();
            longjmp(Thread::running->context, 1);
        }
    }
}

3. zadatak

Postavka

Korišćenjem sistemskih poziva fork i exec, napisati funkciju run koja kreira proces nad programom u fajlu sa zadatom putanjom i vraća negativnu vrednost u slučaju greške, a pid kreiranog procesa u slučaju uspeha pri fork. Ukoliko ne uspe exec, kreirani proces-dete treba ugasiti.

Rešenje

int run(char* path) {
    pid_t pid = fork();
    if (pid < 0) {
        return -1;
    }
    if (pid == 0) {
        int t = exec(path);
        if (t < 0) {
            exit(-2);
        }
    }
    return pid;
}

4. zadatak

Postavka

Dva procesa pristupaju kritičnoj sekciji. Dat je presudokod jednog od njih, koji bi trebalo da obezbedi međusobno isključenje uposlenim čekanjem (kod drugog procesa izgleda analogno). Da li ovo rešenje obezbeđuje međusobno isključenje? Da li ima neki problem (ako ima, koji)?

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

Rešenje

Ovo rešenje ne valja jer se dešava livelock odnosno oba procesa se međusobno zaključaju i ni jedan ni drugi se neće dalje izvršavati. To se desi kada proces P1 postavi flag1 na true a zatim se desi promena konteksta i P2 postavi flag2 na true.

5. zadatak

Postavka

Za koju od ove dve tehnike, dinamičko učitavanje (dynamic loading) ili preklopi (overlays), se može očekivati duže izvršavanje istog programa u najgorem slučaju? Precizno obrazložiti.

Rešenje

Duže vreme izvršavanja u najgorem slučaju se može očekivati kod preklopa jer će program stalno učitavati iz memorije iznova i iznova, dok će dinamičko učitavanje zauzeti više memorije, svaki potreban modul će učitati po jednom.

6. zadatak

Postavka

U nekom sistemu primenjuje se worst-fit algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 256KB potpuno slobodan za alokaciju korisničkih procesa. Potom su različiti procesi zadavali sledeće zahteve (slovna oznaka označava proces koji je postavio zahtev, brojna oznaka označava veličinu alociranog prostora u KB, a minus označava gašenje procesa i oslobađanje njegove memorije): A64, B16, C128, D32, A-, E8, F32, B-

Odgovoriti na sledeća pitanja koja se odnose na stanje memorije nakon ove sekvence zahteva:

1. Koliko je ukupno slobodnih fragmenata?
2. Kolika je veličina najmanjeg slobodnog fragmenta?
3. Kolika je veličina najvećeg slobodnog fragmenta?

Rešenje

Jedno slovo označava 8KB prostora.

AAAAAAAA------------------------
AAAAAAAABB----------------------
AAAAAAAABBCCCCCCCCCCCCCCCC------
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDD--
E-------BBCCCCCCCCCCCCCCCCDDDD--
EFFFF---BBCCCCCCCCCCCCCCCCDDDD--
EFFFF-----CCCCCCCCCCCCCCCCDDDD--

• Slobodnih fragmenata: 2
• Najmanji slobodan fragment: 16KB
• Najveći slobodan fragment: 40KB

7. zadatak

Postavka

Prilikom preslikavanja virtuelne adrese, procesor je generisao izuzetak zbog pokušaja upisa na tu adresu koji je u deskriptoru stranice označen kao zabranjen. Operativni sistem ipak neće ugasiti taj proces. Precizno objasniti zašto.

Rešenje

Neće ugasiti program jer se zapravo radi o tehnici copy-on-write odnosno kopiranja na upis. U ovoj tehnici, MMU vidi tu memoriju kao zabranjenu za upis. Prilikom generisanja greške, OS proverava da li je zabranjena, i kako vidi da zapravo nije nije, to znači da se radi o tehnici kopiranja na upis pa će operativni sistem kopirati stranicu i reći MMU da je dozvoljena za upis.

8. zadatak

Postavka

Navesti tri usluge vezane za realno vreme koje operativni sistem može da nudi i predložiti i kratko objasniti funkcije – sistemske pozive za te usluge.

Rešenje

1. Informacija o tekućem realnom vremenu:

   time_t time (time_t* tloc);

   Vraća broj sekundi koje su protekle od 1. 1. 1970. u 0 časova. Postoje i bibliotečke funkcije u time.h koje vraćaju “kalendarsko” vreme, rastavljeno na datum i sat itd, a oslanjaju se na ovaj sistemski poziv: asctime, ctime, gmtime, localtime.

2. Suspenzija pozivajućeg procesa (“uspavljivanje”) za zadato vreme

   unsigned int sleep (unsigned int seconds);

3. Čekanje na događaje, uslove ili na sinhronizacione primitive, ali vremenski ograničeno (tzv. timeout kontrole); ako se proces ne deblokira u zadatom vremenu, biće deblokiran zbog isteka vremenske kontrole; npr. za semafore:

   int sem_timedwait (sem_t *sem, const struct timespec *abs_timeout);

9. zadatak

Postavka

Ako je tekući direktorijum nekog procesa /a/b/c, koja je apsolutna putanja do fajla koji taj proces otvara davanjem putanje d/../../e/f.txt?

Rešenje

Raščlanimo relativnu putanju na delove:

• d: idemo u direktorijum d, sada je putanja /a/b/c/d
• .. idemo jedan direktorijum iznad, sada je putanja /a/b/c
• .. idemo jedan direktorijum iznad, sada je putanja /a/b
• e idemo u direktorijum e, sada je putanja /a/b/e
• f.txt posećujemo fajl f.txt, krajnja putanja je /a/b/e/f.txt

10. zadatak

Postavka

Fajl sistem primenjuje ulančanu alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje head sadrži broj prvog bloka sa sadržajem fajla, a polje size veličinu sadržaja. Funkcija jezgra free prima kao argument broj prvog bloka u lancu blokova koje treba proglasiti slobodnim. Napisati funkciju jezgra truncate koja briše sadržaj fajla na čiji FCB ukazuje argument.

Rešenje

Pretpostavimo da free_head i free_tail predstavljaju pokazivače na početak i kraj ulančane liste slobodnih blokova.

void truncate(FCB *f) {
    if (f->head == NULL) {
        return;
    }
    int numOfBlocks = f->size / BLOCK_SIZE, i = 0, cur = f->head, tmp_head = f->head, prev;
    while (i < numOfBlocks) {
        free(cur);
        prev = cur;
        cur = cur->next;
        i++;
    }
    if (free_head == NULL) {
        free_head = tmp_head;
    } else {
        free_tail->next = tmp_head;
    }
    free_tail = prev;
}