ОС1/Јун 2013

Zadaci na stranici predmeta.

1. zadatak

Postavka

Šta su multiprocesorski, a šta distribuirani sistemi?

Rešenje

Videti prvi zadatak iz julskog roka 2012. godine.

2. zadatak

Postavka

Ako se nad sledećim programom kreira jedan proces, koliko će ukupno biti elemenata sa vrednošću različitom od 0 u nizovima pid svih kreiranih procesa (uključujući i taj jedan početni) kada svi ti procesi izađu iz petlje, pod pretpostavkom da su svi sistemski pozivi uspeli?

const int N = 2;
int pid[N];
void main() {
    for (int i = 0; i < N; i++)
        pid[i] = fork();
}

Rešenje

• Prva iteracija: P1 pravi P2, pid[0] = 2 u P1
• Druga iteracija: P1 pravi P3, pid[1] = 3 u P1 dok je pid[0] = 2 u P3 zbog toga što je taj niz kopiran iz P1
• Druga iteracija: P2 pravi P4, pid[1] = 4 u P2

Na kraju postoji 4 vrednosti koje nisu nula.

3. zadatak

Postavka

Dokazati da Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa uposlenim čekanjem zaista obezbeđuje međusobno isključenje, odnosno ne poseduje problem utrkivanja (race condition).

Rešenje

Pretpostavimo da oba procesa uposleno čekaju. Promenljiva turn "prelama" u situaciji kada oba procesa žele da uđu u kritičnu sekciju jer turn može imati vrednost ili 1 ili 2. Dakle, nemoguće je da dođe do utrkivanja.

4. zadatak

Postavka

Korišćenjem klasičnih brojačkih semafora, napisati kod za kritičnu sekciju u koju može uporedo ući najviše N procesa.

Rešenje

var mutex : Semaphore := N;
process P:
    begin
        loop
            wait(mutex);
            <critical>
            signal(mutex);
            <non-critical>
        end
    end
end P;

5. zadatak

Postavka

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

Rešenje

Videti rešenje 5. zadatka iz jula 2013. godine.

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 getBestFit(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 best fit algoritmu.

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

Rešenje

void* getBestFit(size_t sz) {
    FreeSegment* bestFit = 0
    size_t smallestFragment = MAX_SIZE;
    for (FreeSegment* cur = freeSegHead; cur != 0; cur = cur->next) {
        if (cur->size < sz) {
            continue;
        }
        if (cur->size < smallestFragment) {
            smallestFragment = cur->size;
            bestFit = cur;
        }
    }
    if (bestFit == 0) {
        return 0;
    }
    FreeSegment* newFrag = (FreeSegment*)((char*)bestFit + sz);
    if (bestFit->prev) {
        bestFit->prev->next = newFrag;
    } else {
        freeSegHead = bestFit->next;
    }
    if (bestFit->next) {
        bestFit->next->prev = newFrag;
    }
    newFrag->prev = bestFit->prev;
    newFrag->next = bestFit->next;
    newFrag->size = bestFit->size - sz;
    return bestFit;
}

7. zadatak

Postavka

Memorija nekog računara organizovana je stranično, sa stranicom veličine 4KB. Adresibilna jedinica je bajt, a virtuelna adresa je 32-bitna. Fizička adresa je veličine 32 bita. Ako je PMT organizovana u dva nivoa, s tim da su veličine polja za broj ulaza u tabele oba nivoa isti, kolika je veličina (u bajtovima) PMT prvog nivoa?

Rešenje

VA: 10 PMT1 | 10 PMT2 | 12 offset

Ulaz PMT 1. nivoa sadrzi fizičku adresu početka PMT 2. nivoa. Kako je fizička adresa 32b = 4B odavde sledi da veličina PMT 1. nivoa je:

4B * 2¹² = 4KB

8. zadatak

Postavka

Ukratko objasniti tehniku dvostrukog baferisanja (double buffering) kod ulaza/izlaza.

Rešenje

Proizvođač upisuje u jedan bafer dok potrošač čita iz drugog bafora. Kada oba završe, baferi zamenjuju uloge.

9. zadatak

Postavka

Neki proces izvršava redom sledeće sistemske pozive. Pod pretpostavkom da korisnik u čije ime se izvršava ovaj proces ima pravo pristupa do oba fajla i na čitanje i na upis, i da oba poziva za otvaranje fajlova uspevaju, navesti koji od preostalih poziva će biti uspešan, a koji neuspešan (upisati na liniji pored poziva).

FHANDLE f1 = fopen(“x.doc”,read);
FHANDLE f2 = fopen(“y.doc”,read|write);

1. fread(f1,buffer1,n1);
2. fwrite(f1,buffer2,n2);
3. fread(f2,buffer1,n1);
4. fwrite(f2,buffer2,n2);

Rešenje

Videti zadatak iz junskog roka 2011.

10. zadatak

Postavka

Neki fajl sistem koristi bit vektor za evidenciju slobodnih blokova na disku. Kolika je veličina ovog vektora u bajtovima, za disk veličine 256 GB sa blokom veličine 512B

Rešenje

Na disku ima ukupno $\frac{256GB}{512B} = 2^{29}$ blokova. Pošto je za svaki blok potreban po jedan bit, količinu prostora određujemo kao $\frac{2^{29}}{2^3} = 64 MB$.