ОС1/Јун 2012

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

1. задатак

Поставка

Шта је то систем са расподелом времена (енгл. тиме-схаринг)?

Решење

Систем са расподелом времена је систем у коме ОС додељује процесор неком процесу на одређено време, затим се процесу преотима процесор, врши промена контекста и процесор предаје другом процесу коме се поново ограничава време извршавања. На овај начин процеси деле време на процесору.

2. задатак

Поставка

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

int f (int n) { 
    if (n <= 0) return 0;
    else return f(n - 1) + 1; 
}

Решење

f:    LD R0, #0      ;Registar u kome se nalazi povratna vrednost
      LD R1, #n[SP]
      CMP R1, R0
      JG else
      RTS
else: LD R2, #1
      SUB R1, R2
      PUSH R1
      call f         ;nakon zavrsetka funkcije f, u R0 se nalazi rezultat
      POP R1
      ADD R0, R2
      RTS

3. задатак

Поставка

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

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

Решење

Пошто само дете наставља даље, а прави се 7 деце, укупно има 8 процеса.

4. задатак

Поставка

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

Решење

shared var x : Integer;
           semA : Semaphore := 0;
           semB : Semaphore := 0;

process A
    begin
        loop
            x = ...
            signal(semB);
            wait(semA);
        end
    end
end A;

process B
    begin
        loop
            wait(semB);
            y = ...
            signal(semA);
        end
    end
end B;

5. задатак

Поставка

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

Решење

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

6. задатак

Поставка

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

1. сортирану уланчану листу,
2. балансирано бинарно стабло.

Колико сегмената треба обићи у најгорем случају да би се пронашао одговарајући слободан сегмент приликом алокације, уколико је слободних сегмената н?

Решење

1. $n$
2. $log_{2}(n)$

7. задатак

Поставка

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

Решење

$0.9 \cdot (0.1 t_{RAM} + t_{RAM}) + 0.1 \cdot (0.1t_{RAM} + 3t_{RAM}) = 1.3t_{RAM}$

Одговор: $30\%$

8. задатак

Поставка

Навести основне операције класе блоковски оријентисаних уређаја са директним приступом.

Решење

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

9. задатак

Поставка

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

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

Операције seek и write раде само у опсегу тренутне величине садржаја фајла (не померају курзор и не уписују иза краја садржаја фајла). Написати операцију

write(FHANDLE,int position,char*,int size);

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

Решење

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

10. задатак

Поставка

Колико приступа блоковима на диску треба извршити за приступ н-том логичком блоку садржаја фајла ако је алокација фајла:

1. уланчана листа блокова, при чему на први блок садржаја фајла указује поље у ФЦБ,
2. индексна, при чему је индекс фајла увек у два нивоа, а на блок са индексом првог нивоа указује поље у ФЦБ? ФЦБ фајла је у меморији

Решење

1. н
2. 3