ОС1/Октобар 2012

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

1. задатак

Поставка

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

Решење

Видети први задатак из јулског рока 2012. године.

2. задатак

Поставка

Дата је операција yиелд(јмп_буф олд, јмп_буф неw) која чува контекст нити чији је jmp_buf дат као први аргумент, одузима јој процесор и рестаурира контекст нити чији је jmp_buf дат као други аргумент, којој предаје процесор. Користећи ову операцију, реализовати операцију dispatch() која има исти ефекат као и она дата у школском језгру.

Решење

void dispatch () {
    lock();
    jmp_buf old = Thread::running->context;
    Scheduler::put(Thread::running);
    Thread::running = Scheduler::get();
    jmp_buf new = Thread::running->context;
    yield(old,new);
    unlock();
}

3. задатак

Поставка

Како се у коду који се извршава након системског позива fork() може знати да ли се тај код извршава у контексту процеса-родитеља или процеса-детета? Објаснити и дати пример.

Решење

Може се знати у ком се контексту извршава код на основу повратне вредности форк-а. Тј. 0 у контексту детета, вредност већа од 0 у контексту родитеља, а мања од 0 ако дође до грешке.

int main(int argc, char* argv[]) {
    pid_t pid = fork();
    if (pid < 0) {
        return -1; 
        // greška
    } else if (pid == 0) {
        // dete
    } else {
        // roditelj
    }
    return 0;
}

4. задатак

Поставка

Написати код једног од два процеса који приступају критичној секцији са међусобним искључењем помоћу упосленог чекања (бусy wаитинг) Петерсоновим алгоритмом.

Решење

process P1:
    begin
        loop
            flag1 := true; turn := 2;
            while flag2 and turn = 2 do null;
            <critical section>
            flag1 := false;
            <non-critical section>
        end
    end
end P1;

process P2:
    begin
        loop
            flag2 := true; turn := 1;
            while flag1 and turn = 1 do null;
            <critical section>
            flag2 := false;
            <non-critical section>
        end
    end
end P2;

5. задатак

Поставка

Дате су следеће декларације у једном изворном C фајлу. Који од ових симбола ће бити означени као „извежени“, а који као „увежени“ у .обј фајлу?

extern int a(int);
void b(int);
void b(int) {}
void c(int);
extern int d;
static int e;
int f;

Решење

• Увежени: а, ц, д
• Извежени: б, ф

6. задатак

Поставка

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

typedef unsigned int size_t;
struct FreeFragment {
    size_t size; // Veličina fragmenta u jedinicama sizeof(char)
    FreeFragment* prev; // Prethodni u listi
    FreeFragment* next; // Sledeći u listi
}
FreeFragment* head; // Glava liste slobodnih fragmenata 
void* getFirstFitFragment(size_t);

Решење

void* getFirstFitFragment(size_t sz) {
    if (head == 0 || sz == 0) {
        return 0;
    }
    for (FreeFragment* cur = head; cur; cur = cur->next) {
        if (cur->size < sz) {
            continue;
        }
        FreeFragment* newFrg = (FreeFragment*)((char*)cur + sz);
        if (cur->prev) {
            cur->prev->next = newFrg;
        } else {
            head = cur->next;
        }
        if (cur->next) {
            cur->next->prev = newFrg;
        }
        newFrg->prev = curr->prev;
        newFrg->next = curr->next;
        newFrg->size = cur->size - sz;
        return cur;
    }
    return 0;
}

7. задатак

Поставка

Објаснити шта је основни мотив и погодност технике страничења у више нивоа у односу на страничење у једном нивоу?

Решење

Већи капацитет виртуелне меморије.

8. задатак

Поставка

Којом техником се физички недељиви излазни уређај може учинити логички (виртуелно) дељивим између процеса који га упоредо користе?

Решење

Споолинг-ом.

9. задатак

Поставка

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

Решење

Та информација чува се у табели отворених фајлова локалној за тај процес.

10. задатак

Поставка

Неки фајл систем користи индексирану алокацију фајлова на диску са једноструким индексом. Ако се претпоставља да је простор за смештање фајлова (укључујући и њихове индексе) на диску величине 32 ГБ, величина кластера (једине јединице алокације) 2 КБ, и цео простор потпуно испуњен фајловима тако да је сваки фајл максималне величине такве да има само један индексни кластер, колики проценат укупног простора за смештање фајлова на овом диску заузимају индекси?

Решење

• $\frac{32GB}{2KB} = 16M = 2^{24} \implies 3B$ адреса
• $\frac{2KB}{3B} = 682$ улаза у индексу
• Проценат заузетости: 100/(682 + 1)%