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

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

1. задатак

Поставка

Укратко објаснити основни мотив настанка концепта мултипрограмирања.

Решење

Код монопроцесних рачунара уз спору обраду и споре улазно-излазне уређаје, извршавање самог програма и искоришћење процесора је било слабо. Решење (мултипрограмирање) огледа се у учитавању више процеса у оперативну меморију и њиховом упоредом извршавању. Док један процес чека на завршетак I/О операције, процесор може да извршава инструкције неког другог процеса.

2. задатак

Поставка

Зашто није добро користити упослено чекање у прекидној рутини?

Решење

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

3. задатак

Поставка

На језику C, коришћењем системских позива fork() и execlp() за Униx, написати програм који покреће други програм из фајла чији је назив задат као параметар командне линије првог програма.

Решење

int main(int argc, char* argv[]) {
    if (argc < 2) {
        return -1;
    }
    pid_t pid = fork();
    if (pid < 0) {
        return -2;
    } else if (pid == 0) {
        execlp(argv[1]);
    } else {
        wait(0);
    }
    return 0;
}

4. задатак

Поставка

Коришћењем стандардних бројачких семафора у школском језгру, на језику C++ написати глобалне декларације и иницијализације, као и код тела две упоредне нити А и Б које циклично раде следеће:

А: уписује вредност у дељене променљиве x и y, а затим чека да процес Б упише збир x и y у променљиву з чију вредност исписује на стандардни излаз;

Б: чека да процес А упише вредности у дељене променљиве x и y, затим ове две вредности сабира и збир уписује у дељену променљиву з.

Решење

Semaphore xySem(0), zSem(0);
int x, y, z;

// A:
while (1) {
    x = ...;
    y = ...;
    xySem.signal();
    zSem.wait();
    cout << z;
}

// B:
while (1) {
    xySem.wait();
    z = x + y;
    zSem.signal();
}

5. задатак

Поставка

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

Решење

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

Може се догодити следеће:

• једна нит уђе у извршавање неког потпрограма П који припада једном преклопу, провери и по потреби учита код за тај потпрограм у преклоп X.
• оперативни систем извршава промену контекста нити и покрене другу нит
• ова друга нит улази у потпрограм Q који припада другом преклопу
• систем преклопа учитава преклоп коме припада Q на место X
• поново дође до промене контекста и прва нит настави од адресе коју очекује (потпрограм П) али се ту налази код потпрограма Q.

6. задатак

Поставка

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

1. двоструко уланчана листа слободних фрагмената уређених по величини или
2. двоструко уланчана листа слободних фрагмената уређених по позицији у меморији.

Кратко образложити.

Решење

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

7. задатак

Поставка

Којом техником се недељиви уређај може учинити виртуелно дељивим?

Решење

Техником под именом споолинг.

8. задатак

Поставка

У фајл подсистему неког оперативног система не води се табела отворених фајлова за сваки процес, већ постоји само једна глобална табела отворених фајлова за цео систем. Другим речима, не постоји никаква информација о употреби отвореног фајла локална (приватна) за појединачни процес, већ су све такве информације глобално дељене. Да ли појам показивача тренутне локације (курзора) за читање/упис у фајл има смисла чувати у глобалној табели отворених фајлова и зашто?

Решење

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

9. задатак

Поставка

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

Решење

1. Хеш табела са двоструко уланчаним листама за решавање колизија:
   • Проналажење улаза са датим именом - О(н)
   • Брисање пронађеног улаза (не рачунајући проналажење по имену) - О(1)
2. Двоструко уланчана листа са показивачима на главу и реп листе:
   • Проналажење улаза са датим именом - О(н)
   • Брисање пронађеног улаза (не рачунајући проналажење по имену) - О(1)

10. задатак

Поставка

Неки фајл систем користи индексирани приступ алокацији фајлова са индексима у два нивоа, блоком величине 512КБ и 64-битним адресама физичких блокова. Колика је максимална величина фајла у овом систему?

Решење

$\frac{512KB}{8B} = 64K = 2^{16}$ улаза

Максимална величина је $2^{16} \cdot 2^{16} \cdot 512KB = 2^{51}B = 2PB$