ОС1/Јун 2013

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

1. задатак

Поставка

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

Решење

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

2. задатак

Поставка

Ако се над следећим програмом креира један процес, колико ће укупно бити елемената са вредношћу различитом од 0 у низовима pid свих креираних процеса (укључујући и тај један почетни) када сви ти процеси изађу из петље, под претпоставком да су сви системски позиви успели?

const int N = 2;
int pid[N];
void main() {
    for (int i = 0; i < N; i++)
        pid[i] = fork();
}

Решење

• Прва итерација: П1 прави П2, pid[0] = 2 у П1
• Друга итерација: П1 прави П3, pid[1] = 3 у П1 док је pid[0] = 2 у П3 због тога што је тај низ копиран из П1
• Друга итерација: П2 прави П4, pid[1] = 4 у П2

На крају постоји 4 вредности које нису нула.

3. задатак

Поставка

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

Решење

Претпоставимо да оба процеса упослено чекају. Променљива турн "прелама" у ситуацији када оба процеса желе да уђу у критичну секцију јер турн може имати вредност или 1 или 2. Дакле, немогуће је да дође до утркивања.

4. задатак

Поставка

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

Решење

var mutex : Semaphore := N;
process P:
    begin
        loop
            wait(mutex);
            <critical>
            signal(mutex);
            <non-critical>
        end
    end
end P;

5. задатак

Поставка

Коју услугу оперативни систем треба да обезбеди процесима да би они користили преклопе (оверлаyс)?

Решење

Видети решење 5. задатка из јула 2013. године.

6. задатак

Поставка

Дата је дефиниција структуре FreeSegment која представља један сегмент слободне меморије. Ове структуре увезане су у двоструко уланчану, неуређену листу чија је глава freeSegHead. Имплементирати функцију getBestFit(size_t) која треба да пронађе и врати (али не мења ни њега ни листу) сегмент слободне меморије у који се може сместити блок дате величине, по бест фит алгоритму.

struct FreeSegment {
    size_t size;
    FreeSegment *prev, *next;
};

Решење

void* getBestFit(size_t sz) {
    FreeSegment* bestFit = 0
    size_t smallestFragment = MAX_SIZE;
    for (FreeSegment* cur = freeSegHead; cur != 0; cur = cur->next) {
        if (cur->size < sz) {
            continue;
        }
        if (cur->size < smallestFragment) {
            smallestFragment = cur->size;
            bestFit = cur;
        }
    }
    if (bestFit == 0) {
        return 0;
    }
    FreeSegment* newFrag = (FreeSegment*)((char*)bestFit + sz);
    if (bestFit->prev) {
        bestFit->prev->next = newFrag;
    } else {
        freeSegHead = bestFit->next;
    }
    if (bestFit->next) {
        bestFit->next->prev = newFrag;
    }
    newFrag->prev = bestFit->prev;
    newFrag->next = bestFit->next;
    newFrag->size = bestFit->size - sz;
    return bestFit;
}

7. задатак

Поставка

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

Решење

ВА: 10 ПМТ1 | 10 ПМТ2 | 12 оффсет

Улаз ПМТ 1. нивоа садрзи физичку адресу почетка ПМТ 2. нивоа. Како је физичка адреса 32б = 4Б одавде следи да величина ПМТ 1. нивоа је:

4Б * 2¹⁰ = 4КБ

8. задатак

Поставка

Укратко објаснити технику двоструког баферисања (доубле буфферинг) код улаза/излаза.

Решење

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

9. задатак

Поставка

Неки процес извршава редом следеће системске позиве. Под претпоставком да корисник у чије име се извршава овај процес има право приступа до оба фајла и на читање и на упис, и да оба позива за отварање фајлова успевају, навести који од преосталих позива ће бити успешан, а који неуспешан (уписати на линији поред позива).

FHANDLE f1 = fopen(“x.doc”,read);
FHANDLE f2 = fopen(“y.doc”,read|write);

1. fread(f1,buffer1,n1);
2. fwrite(f1,buffer2,n2);
3. fread(f2,buffer1,n1);
4. fwrite(f2,buffer2,n2);

Решење

Видети задатак из јунског рока 2011.

10. задатак

Поставка

Неки фајл систем користи бит вектор за евиденцију слободних блокова на диску. Колика је величина овог вектора у бајтовима, за диск величине 256 ГБ са блоком величине 512Б

Решење

На диску има укупно $\frac{256GB}{512B} = 2^{29}$ блокова. Пошто је за сваки блок потребан по један бит, количину простора одређујемо као $\frac{2^{29}}{2^3} = 64 MB$.