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

Решење

Одговор: 8

• П1 прави дете П2 и инкрементира своје i.
• П2 је дете, те fork() враћа 0 у контексту детета и завршава се програм.
• П1 прави дете П3 и инкрементира своје i.
• П1 прави дете П4 и инкрементира своје i.
• П1 прави дете П5 и инкрементира своје i.
• П1 прави дете П6 и инкрементира своје i.
• П1 прави дете П7 и инкрементира своје i.
• П1 прави дете П8 и инкрементира своје i.
• П3, П4, П5, П6, П7, П8 се исто завршавају као процес П2.
• П1 завршава свој for циклус јер је i постало 7.

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

Однос: $\frac{1.4 - 1}{1} = 40\%$

8. задатак

Поставка

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

Решење

1. инт гетц(ФИЛЕ * ф) Учитава и враћа 1 знак из улазног тока.
2. инт путц(инт ц, ФИЛЕ * ф) Шаље 1 знак на задати излазни ток.

9. задатак

Поставка

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

1. инт сизе(ФХАНДЛЕ) Враћа тренутну величину садржаја фајла у знаковима.
2. воид аппенд(ФХАНДЛЕ, инт) Проширује садржај фајла за дати број знакова на крају.
3. воид сеек(ФХАНДЛЕ, инт) Поставља курзор датог фајла на дату позицију (редни број знака почев од 0).
4. воид wрите(ФХАНДЛЕ, цхар*, инт сизе) На позицију курзора датог фајла уписује дати низ знакова задате дужине, и помера курзор иза уписаног низа знакова. Операције сеек и wрите раде само у опсегу тренутне величине садржаја фајла (не померају курзор и не уписују иза краја садржаја фајла).

Написати операцију wрите(ФХАНДЛЕ, инт поситион, цхар*, инт сизе); која на задату позицију уписује задати низ знакова дате величине, при чему се фајл имплицитно најпре проширује на потребну величину уколико би задата позиција или задати упис прекорачио тренутну величину садржаја фајла. Занемарити све могуће грешке у улазу/излазу.

Решење

void write(FHANDLE f, int position, char* b, int size) {
    int curSize = size(f);
    if (position + size > curSize) {
        append(f, position + size - curSize);
    }
    seek(f, position);
    write(f, b, size);
}

10. задатак

Поставка

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

Решење

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