ОС1/Јун 2013

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

1. задатак

Поставка

Шта су мултипроцесорски, а шта дистрибуирани системи?

Решење

Видети задатак из јунског рока 2011.

2. задатак

Поставка

Ако се над следећим програмом креира један процес, колико ће укупно бити елемената са вредношћу различитом од 0 у низовима pid свих креираних процеса (укључујући и тај један почетни) када сви ти процеси изађу из петље, под претпоставком да су сви системски позиви успели?

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

Решење

Биће укупно 4 елемената са вредношћу различитом од 0.

3. задатак

Поставка

Доказати да Петерсонов алгоритам за међусобно искључење критичних секција два упоредна процеса упосленим чекањем заиста обезбеђује међусобно искључење, односно не поседује проблем утркивања (раце цондитион)

Решење

Претпоставимо да оба процеса упослено чекају. Променљива турн "прелама" у ситуацији када оба процеса желе да уђу у критичну секцију јер турн може имати вредност или 1 или 2. Дакле, немогуће је да дође до утркивања

4. задатак

Поставка

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

Решење

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

5. задатак

Поставка

Коју услугу оперативни систем треба да обезбеди процесима да би они користили преклопе (оверлаyс)?

Решење

Преклопи не захтевају подршку ОС-а. Све обавља преводилац и генерисани код. ОС само обезбеђује услуге за алокацију дела виртуелног адресног простора.

6. задатак

Поставка

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

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

Решење

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

Поставка

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

Решење

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

8. задатак

Поставка

Укратко објаснити технику двоструког баферисања (доубле буфферинг) код улаза/излаза.

Решење

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

9. задатак

Поставка

Неки процес извршава редом следеће системске позиве. Под претпоставком да корисник у чије име се извршава овај процес има право приступа до оба фајла и на читање и на упис, и да оба позива за отварање фајлова успевају, навести који од преосталих позива ће бити успешан, а који неуспешан (уписати на линији поред позива).

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

Решење

Видети задатак из јунског рока 2011.

10. задатак

Поставка

Неки фајл систем користи бит вектор за евиденцију слободних блокова на диску. Колика је величина овог вектора у бајтовима, за диск величине 256 ГБ са блоком величине 512Б

Решење

256ГБ / 512Б = 2^29 блокова

2^29 / 2^3 = 64МБ