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

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

1. задатак

Поставка

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

Решење

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

2. задатак

Поставка

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

Решење

Видети решење 2. задатка из јунског рока 2014. године.

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 minDiff = INT_MAX;
    FreeSegment* tmp = freeSegHead;
    FreeSegment* ans = NULL;
    while (tmp) {
        if (tmp->size == s) {
            return tmp;
        }
        if (tmp->size > s) {
            if (tmp->size - s < minDiff) {
                minDif = tmp->size - s;
                ans = tmp;
            }
        }
        tmp = tmp->next;
    }
    return ans;
}

7. задатак

Поставка

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

Решење

• За страницу од $4KB = 2^{12}B$ потребно је 12 бита за адресирање.
• Структура виртуелне адресе је ВА(32): паге1(10) паге2(10) оффсет(12)
• Величину ПМТ првог нивоа онда добијамо као: $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 truncate(FCB* fcb){
	if (!fcb || fcb->sizeInBlocks == 0 ) return;
	unsigned head = fcb->head;
	while(head != 0){
		prev = head;
		head = fat[head];
		fat[prev] = ~0U;
	}
}