Контрольная работа 1-01
Вариант 2
(6 баллов) В операционных системах, поддерживающих нити исполнения (threads) внутри одного процесса на уровне ядра системы, наряду с блоками управления процессами (PCB) существуют структуры данных для управления нитями - TCB (Thread Control Block). Укажите, какие данные из перечисленных ниже, хранятся, по Вашему мнению, в TCB:
Номер процесса |
Время поступления в систему |
Время исполнения |
1 |
2 |
7 |
2 |
6 |
6 |
3 |
4 |
4 |
4 |
1 |
2 |
5 |
0 |
5 |
Вычислите среднее время между стартом процесса и его завершением (turnaround time) и среднее время ожидания процесса (waiting time) для каждого из трех алгоритмов планирования FCFS (First Come First Served), RR (Round Robin) и SJF (Short Job First). При вычислениях считать, что процессы не совершают операций ввода-вывода, величину кванта времени принять равной 1, временем переключения контекста пренебречь. Процесс, поступающий в систему, считать готовым к исполнению в момент поступления. Для алгоритма RR принять, что вновь прибывший процесс помещается в начало очереди процессов, готовых к исполнению, и, следовательно, сразу выбирается на исполнение.
(18 баллов) В вычислительной системе моделируется движение самосвалов от карьера к заводу и обратно по дороге со стареньким мостом. Движение по мосту может осуществляться в обоих направлениях, но на нем не может быть одновременно более трех машин, иначе он рухнет. Каждый самосвал представлен в системе процессом следующей структуры:
Процесс i-й самосвал:
While (1) {
Опишите схему безопасного пересечения моста, используя семафоры. Докажите, что Ваша схема удовлетворяет условиям bounded waiting (ограниченного ожидания) и progress. Если несколько процессов ожидают выполнения операции Signal над семафором, то считайте, что процесс, который продолжит исполнение после выполнения этой операции, выбирается по принципу FIFO.
Номер сегмента |
Адрес начала сегмента |
Длина сегмента |
1 |
0x000000 |
0x100000 |
2 |
0x200000 |
0x080000 |
3 |
0x100000 |
0x080000 |
5 |
0x300000 |
0x300000 |
Каким физическим адресам соответствуют адреса 0х245678, 0x1000006, 0x018b00de?
1, 2, 0, 3, 2, 1, 3, 0, 5, 2, 7, 1, 2, 7, 0
Сколько ситуаций отказа страницы (page fault) возникнет для данного процесса при каждом из трех алгоритмов замещения страниц - FIFO (Fist Input Fist Output) , LRU (the Least Recently Used), OPT (optimal) , если процессу выделено 3 кадра памяти?
(15 баллов) Рассмотрим вычислительную систему со страничной организацией памяти, на которой выполняется одна программа, несколько раз последовательно сканирующая большой одномерный массив данных (это означает, что для массива, занимающего, например, в памяти четыре страницы, строка запроса страниц выглядит следующим образом: 1, 2, 3, 4, 1, 2, 3, 4, ...). Для каждого из трех алгоритмов замещения страниц - FIFO (First Input First Output), LRU (the Least Recently Used) и OPT (OPTimal) нарисуйте график зависимости частоты page faults от размеров массива. По оси y откладывается отношение числа page faults к длине строки запроса (если массив, занимающий четыре страницы памяти, сканируется 2 раза, то длина строки запроса равна 8), по оси x - размер массива: от размеров, требующих одну страницу, и до размеров, значительно превыщающих размер физической памяти. Опишите наиболее характерные точки на графике.