ОС1/Септембар 2015

Zadaci na stranici predmeta.

1. zadatak

Postavka

Prvi interaktivni računarski sistemi uveli su jednu značajnu novinu u operativne sisteme. Koja je to novina? Objasniti ukratko njenu suštinu.

Rešenje

Novina koja je uvedena je interakcija sa korisnicima preko terminala. Ona je u početku imala probleme sporog i neravnomernog odziva za korisnike, pa su uvedeni koncepti preotimanja procesora i time sharing mehanizam, koji su omogućili brz i ravnomeran odziv korisnicima.

2. zadatak

Postavka

Korišćenjem standardnih bibliotečnih funkcija setjmp() i longjmp(), u školskom jezgru implementirati operaciju yield(Thread* old, Thread* new) koja prebacuje kontekst izvršavanja sa jedne (old) na drugu (new) nit.

Rešenje

Videti rešenje 2. zadatka iz junskog roka 2014. godine.

3. zadatak

Postavka

Кorišćenjem školskog jezgra, napraviti nit koja se inicijalizuje celobrojnim parametrom n i koja kreira jednu istu takvu nit-dete, ova nit-dete kreira jednu svoju nit-dete, i tako dalje, rekurzivno, ali tako da ukupno bude kreirano n niti.

Rešenje

class MyThread : public Thread {
    public:
        MyThread(int val) {
            n = val;
            start();
        }
    protected:
        void run() {
            if (n <= 0) {
                return;
            } else {
                new MyThread(n - 1);
            }
        }
    private:
        int n;
};

4. zadatak

Postavka

Dato je jedno moguće rešenje za međusobno isključenje dva procesa uposlenim čekanjem. Da li ovo rešenje obezbeđuje međusobno isključenje? Da li ima neki drugi problem?

shared var turn : integer = 1;
process P1                       process P2
begin                              begin
  loop                                loop
    while turn = 2 do null end;          while turn = 1 do null end;
    <critical section>                    <critical section>
    turn := 2;                            turn := 1;
    <non-critical section>              <non-critical section>
  end                                 end
end P1;                          end P2;

Rešenje

Rešenje obezbeđuje međusobno isključenje ali je problem stroga naizmeničnost što je suvišna sinhronizacija.

5. zadatak

Postavka

Šta znači kad je proces swapped out?

Ako je proces swapped out, u kom stanju se od sledećih on nalazi?

1. created
2. ready
3. running
4. suspended
5. terminated

Rešenje

Swapped out proces je proces koji je bio izbačen iz memorije i upisan na disk kako bi se u memoriju učitao neki drugi koji se ubacuje memoriju.

Nalazi se u suspended stanju kada se swap-out-uje.

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

FreeSegment* getBestFit(size_t s) {
    int minDiff = INT_MAX;
    FreeSegment* tmp = freeSegHead;
    FreeSegment* ans = NULL;
    while (tmp) {
        if (tmp->size == s) {
            return tmp;
        }
        if (tmp->size > s) {
            if (tmp->size - s < minDiff) {
                minDif = tmp->size - s;
                ans = tmp;
            }
        }
        tmp = tmp->next;
    }
    return ans;
}

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

• Za stranicu od $4KB = 2^{12}B$ potrebno je 12 bita za adresiranje.
• Struktura virtuelne adrese je VA(32): page1(10) page2(10) offset(12)
• Veličinu PMT prvog nivoa onda dobijamo kao: $2^{10} \cdot 4B = 4KB$

8. zadatak

Postavka

Kojom tehnikom se nedeljivi uređaj može učiniti virtuelno deljivim?

Rešenje

Spooling-om.

9. zadatak

Postavka

U nekom sistemu simbol . označava tekući, a .. roditeljski direktorijum. Koja od sledećih naredbi (svaka se izvršava uspešno) sigurno neće promeniti tekući direktorijum? (Zaokružiti jedan ili više tačnih odgovora.)

1. cd ./../../x/y/z
2. cd ./x/y/z/../..
3. cd ./../../../x/y/z
4. cd ./x/y/z/../../..

Rešenje

4. naredba sigurno neće promeniti tekući direktorijum.

10. zadatak

Postavka

Neki fajl sistem primenjuje FAT za alokaciju sadržaja fajla. FAT je cela keširana u memoriji, na nju ukazuje pokazivač fat, i ima FATSIZE ulaza tipa unsigned. Prilikom ulančavanja blokova sa sadržajem fajla, null vrednost se označava vrednošću 0 u odgovarajućem ulazu u FAT, dok se slobodni blokove ne ulančavaju posebno, već su njima odgovarajući ulazi u FAT označeni vrednostima ~0U (sve jedinice binarno); blokovi broj 0 i broj ~0U se ne koriste u fajl sistemu. U FCB polje head tipa unsigned sadrži broj prvog bloka sa sadržajem fajla (0 ako je sadržaj prazan). Napisati kod kojim se oslobađaju svi blokovi sa sadržajem fajla.

Rešenje

void truncate(FCB* fcb){
	if (!fcb || fcb->sizeInBlocks == 0 ) return;
	unsigned head = fcb->head;
	while(head != 0){
		prev = head;
		head = fat[head];
		fat[prev] = ~0U;
	}
}