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

Задаци на страници предмета.

1. задатак

Поставка

Први интерактивни рачунарски системи увели су једну значајну новину у оперативне системе. Која је то новина? Објаснити укратко њену суштину.

Решење

Новина која је уведена је интеракција са корисницима преко терминала. Она је у почетку имала проблеме спорог и неравномерног одзива за кориснике, па су уведени концепти преотимања процесора и тиме схаринг механизам, који су омогућили брз и равномеран одзив корисницима.

2. задатак

Поставка

Коришћењем стандардних библиотечних функција setjmp() и longjmp(), у школском језгру имплементирати операцију yield(Thread* old, Thread* new) која пребацује контекст извршавања са једне (old) на другу (new) нит.

Решење

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

3. задатак

Поставка

Коришћењем школског језгра, направити нит која се иницијализује целобројним параметром н и која креира једну исту такву нит-дете, ова нит-дете креира једну своју нит-дете, и тако даље, рекурзивно, али тако да укупно буде креирано н нити.

Решење

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. задатак

Поставка

Дато је једно могуће решење за међусобно искључење два процеса упосленим чекањем. Да ли ово решење обезбеђује међусобно искључење? Да ли има неки други проблем?

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;

Решење

Решење обезбеђује међусобно искључење али је проблем строга наизменичност што је сувишна синхронизација.

5. задатак

Поставка

Шта значи кад је процес сwаппед оут?

Ако је процес сwаппед оут, у ком стању се од следећих он налази?

1. цреатед
2. реадy
3. руннинг
4. суспендед
5. терминатед

Решење

Сwаппед оут процес је процес који је био избачен из меморије и уписан на диск како би се у меморију учитао неки други који се убацује меморију.

Налази се у суспендед стању када се сwап-оут-ује.

6. задатак

Поставка

Дата је дефиниција структуре FreeSegment која представља један сегмент слободне меморије. Ове структуре увезане су у двоструко уланчану, неуређену листу чија је глава freeSegHead. Имплементирати функцију getBestFit(size_t) која треба да пронађе и врати (али не мења ни њега ни листу) сегмент слободне меморије у који се може сместити блок дате величине, по бест фит алгоритму.

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

Решење

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. задатак

Поставка

Меморија неког рачунара организована је странично, са страницом величине 4КБ. Адресибилна јединица је бајт, а виртуелна адреса је 32-битна. Физичка адреса је величине 32 бита. Ако је ПМТ организована у два нивоа, с тим да су величине поља за број улаза у табеле оба нивоа исти, колика је величина (у бајтовима) ПМТ првог нивоа?

Решење

page: 4KB -> 12b

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

pmt1_size = $2^{10} \cdot 4B = 4KB$

8. задатак

Поставка

Којом техником се недељиви уређај може учинити виртуелно дељивим?

Решење

Споолинг-ом.

9. задатак

Поставка

У неком систему симбол . означава текући, а .. родитељски директоријум. Која од следећих наредби (свака се извршава успешно) сигурно неће променити текући директоријум? (Заокружити један или више тачних одговора.)

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

Решење

4. наредба сигурно неће променити текући директоријум.

10. задатак

Поставка

Неки фајл систем примењује ФАТ за алокацију садржаја фајла. ФАТ је цела кеширана у меморији, на њу указује показивач fat, и има FATSIZE улаза типа unsigned. Приликом уланчавања блокова са садржајем фајла, нулл вредност се означава вредношћу 0 у одговарајућем улазу у ФАТ, док се слободни блокове не уланчавају посебно, већ су њима одговарајући улази у ФАТ означени вредностима ~0U (све јединице бинарно); блокови број 0 и број ~0U се не користе у фајл систему. У ФЦБ поље head типа unsigned садржи број првог блока са садржајем фајла (0 ако је садржај празан). Написати код којим се ослобађају сви блокови са садржајем фајла.

Решење

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;
	}
}