ОС1/Јул 2014

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

1. задатак

Поставка

Шта је био основни мотив за увођење расподеле времена (енгл. тиме-схаринг) код интерактивних система? Објаснити.

Решење

Видети задатак из фебруарског рока 2013.

2. задатак

Поставка

На асемблеру неког замишљеног РИСЦ процесора са ЛОАД/СТОРЕ архитектуром написати превод следеће рекурзивне функције:

int fib (int n) { 
  if (n<=1) return 1; 
  else return fib(n-1)+fib(n-2); 
}

Решење

fib:	LD R1, #n[SP]
		LD R0, #1
		CMP R1, R0
		JG else
		RTS
else:	SUB R1, R0
		PUSH R1
		CALL fib
		POP R2
		SUB R1, R0
		PUSH R1
		CALL fib
		POP R0
		ADD R0, R1
		RTS

3. задатак

Поставка

Уколико су сви системски позиви извршени успешно, колико процеса се укупно креира када се над следећим програмом креира један процес (рачунајући и тај један)?

	
void main () {   
    for (int i=0; i<7; i++) 
        if (fork()==0) 
            return; 
}

Решење

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

4. задатак

Поставка

Коришћењем стандардних бројачких семафора написати код три упоредна процеса који сарађују на следећи начин. Процес А уписује једну вредност у дељену променљиву x, а независни процес Б упоредо уписује једну вредност у дељену променљиву y. Процес C потом чита x и y да би израчунао њихов збир. Тек када је C прочитао x, процес А уписује нову вредност у x; тек када је C прочитао вредност y, процес Б уписује нову вредност у y, и тако циклично.

Решење

var: sax : Semaphore := 1, scx : Semaphore := 0, sby : Semaphore := 1, sbc : Semaphore := 0;
	 x, y, z : Integer;

process A:
	begin
		loop
			wait(sax);
			x := ...
			signal(scx);
	end;
end A;

process B:
	begin
		loop
			wait(sby);
			y := ...
			signal(scy);
	end;
end B;

process C:
	begin
		loop
			wait(scx);
			z := x;
			signal(sax);
			wait(scy);
			z := z + y;
			signal(sby);
	end;
end A;

5. задатак

Поставка

Неки програм користи две велике структуре података наизменично: најпре за неку сложену обраду користи само прву структуру, па онда за неку другу обраду користи само другу структуру, па онда поново прву, па другу итд. Ако се ове две структуре учитавају динамички и преклапају се (код коришћења преклопа, оверлаyс), у ком случају ће извршавање тог програма трајати дуже, а у ком ће користити више меморије: када се користи само динамичко учитавање, или када се користе преклопи? Кратко образложити.

Решење

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

6. задатак

Поставка

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

1. релокатибилност процеса
2. заштита меморијског простора једног процеса од других процеса?

Решење

1. релокатибилност процеса - компакција слободног простора -> кернел реалоцира све процесе тако да их слаже један иза другог редом тако да сав слободан простор фузионише у један слободан фрагмент.
2. заштита меморијског простора - лимит регистар

7. задатак

Поставка

Учестаност поготка у ТЛБ је 90%, а ПМТ је организована у три нивоа. ТЛБ је 10 пута бржа него оперативна меморија. За колико процената је ефективан приступ меморији спорији од приступа физичкој меморији?

Решење

$t_{TLB} = 0.1 t_{RAM}$

$0.9 \cdot (t_{TLB} + t_{RAM}) + 0.1 \cdot (t_{TLB} + 4 \cdot t_{RAM}) = 1.4 t_{RAM}$

Однос: $(1.4 - 1) / 1 = 40\%$

8. задатак

Поставка

Навести основне операције класе знаковно-оријентисаних улазно/излазних уређаја (токова).

Решење

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

9. задатак

Поставка

Неки фајл систем пружа следеће операције у свом АПИ за текстуалне фајлове:

1. int size(FHANDLE) Враћа тренутну величину садржаја фајла у знаковима.
2. void append(FHANDLE,int) Проширује садржај фајла за дати број знакова на крају.
3. void seek(FHANDLE,int) Поставља курзор датог фајла на дату позицију (редни број знака почев од 0).
4. void write(FHANDLE,char*,int size) На позицију курзора датог фајла уписује дати низ знакова задате дужине, и помера курзор иза уписаног низа знакова. Операције сеек и wрите раде само у опсегу тренутне величине садржаја фајла (не померају курзор и не уписују иза краја садржаја фајла).

Написати операцију write(FHANDLE,int position,char*,int size);

која на задату позицију уписује задати низ знакова дате величине, при чему се фајл имплицитно најпре проширује на потребну величину уколико би задата позиција или задати упис прекорачио тренутну величину садржаја фајла. Занемарити све могуће грешке у улазу/излазу.

Решење

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

10. задатак

Поставка

Објаснити како се у фајл систему типа ФАТ води евиденција о слобном простору.

Решење

Слободни блокови се уланчавају у листу показивача који се налазе у сваком блоку. Алокација једног блока је једноставна. Узима се први блок из листе. ФАТ варијанта је инхерентна - улази за слободне блокове у ФАТ су посебно означени.