OS1/Septembar 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

void yield(Thread* old, Thread* new) {
	if(setjmp(old->context) == 0)
		longjmp(new->context, 1);
}

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 minDif = INT_MAX;
	FreeSegment *tmp = freeSeghead, *ans = 0;
	while (tmp) {
		if (tmp->size == s) return tmp;
		if (tmp->size > s) {
			if (tmp->size - s < minDif) {
				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

page: 4KB -> 12b

VA(32) : page1(10) : page2(10) : offset(12)

pmt1_size = $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 clearAll(FCB* file) {
	if(file == 0 || file->sizeInBlocks == 0 || file->head == 0) return;
	while(file->head) {
		auto tmp = file->head;
		file->head = file->head->next;
		tmp->value = ~0U;
	}
}