Контрольная работа 1-00

Вариант 2

0. За разговоры с соседом -3 балла за каждый.

1. (6 баллов) Возможны ли следующие переходы процесса из одного состояния в другое?

1. Из состояния ожидание в состояние готовность.
2. Из состояния рождение в состояние ожидание.
3. Из состояния исполнение в состояние готовность.

 

Если переход возможен, кратко сформулируйте, когда он происходит. Если невозможен, напишите почему.

2. (3 балла) Кратко сформулируйте разницу между программой и процессом.

3. (12 баллов) Пусть в вычислительную систему поступают пять процессов различной длительности по следующей схеме:

 

Номер процесса	Время поступления в систему	Время исполнения
1	2	4
2	3	10
3	6	5
4	4	1
5	0	4

Вычислите среднее время между стартом процесса и его завершением (turnaroud time) и среднее время ожидания процесса (waiting time) для каждого из трех алгоритмов планирования FCFS (First Come First Served), RR (Round Robin) и SJF (Short Job First). При вычислениях считать, что процессы не совершают операций ввода-вывода, величину кванта времени принять равной 1, временем переключения контекста пренебречь. Для алгоритма RR принять, что вновь прибывший процесс выбирается для исполнения первым..

4. (3 балла) Дайте краткое определение термина “race condition (состояние гонки)”.

 

5. (18 баллов) Рассмотрим задачу “поможем матушке природе”. Пусть в вычислительной системе существуют процессы, которые “добывают атомы элементов” для последующего их “объединения в молекулы”. Нас будет интересовать “создание молекулы воды”. Для этого в системе существует три процесса: два, добывающих водород, и один, добывающий кислород. Когда в наличии имеется два атома водорода и один кислорода, синтезируется молекула воды. Для решения этой задачи была предложена следующая неправильная схема организации взаимодействия процессов:

int nh = 0; /* количество атомов водорода в наличии */
int no = 0; /* количество атомов кислорода в наличии */

Процессы, добывающие водород Ph1 и Ph2:

while (1) {


take_h_atom();
nh = nh +1;
}

Процесс, добывающий кислород Po:

while (1) {


take_o_atom();
no = no +1;
while(nh < 2);
nh = nh-2;
no = no-1;
make_water();
}


Укажите, почему она является неправильной, и предложите правильную схему с использованием семафоров. Докажите, что она удовлетворяет условию взаимоисключения (mutual exclusion).

6. (5 баллов) В вычислительной системе с сегментной организацией памяти из 32-х бит адреса старшие 10 его бит отводятся для номера сегмента.

1. Какое максимальное количество сегментов может иметь процесс? Каков максимальный размер сегмента?
2. Для некоторого процесса таблица сегментов имеет вид:

Номер сегмента	Адрес начала сегмента	Длина сегмента
1	0x000000	0x100000
2	0x200000	0x080000
3	0x100000	0x080000
5	0x300000	0x300000

Каким физическим адресам соответствуют адреса 0х245678, 0x500001, 0x00c700de?

7. (9 баллов) Для некоторого процесса известна следующая строка запросов страниц памяти:
   

2, 0, 3, 7, 0, 3, 2, 7, 2, 7, 1, 3, 2, 0, 7

Сколько ситуаций отказа страницы (page fault) возникнет для данного процесса при каждом из трех алгоритмов замещения страниц — FIFO (Fist Input Fist Output) , LRU (the Least Recently Used), OPT (optimal) , если процессу выделено 3 кадра памяти?

8. (15 баллов) Ваш научный руководитель обратился к Вам за помощью для составления конфигурации приобретаемого компьютера. Вы можете потратить $1500 на приобретение следующих компонент:

Компонента	Время доступа	Минимальный размер	Стоимость
TLB	10 наносекунд	4 входа	$20 за вход
Оперативная память	200 наносекунд	16 Mb	$2 за Mb
Жесткий диск	10 миллисекунд	2 Gb	$0.20 за Mb

Размер страницы памяти в системе фиксирован и составляет 16 Kb. Предполагается, что в системе будут одновременно работать 3-4 приложения, каждое из которых требует не более 64 Mb памяти и имеет рабочий объем памяти (общий размер рабочего набора страниц) 256 Kb. Сформулируйте Ваши предложения руководителю по конфигурации системы.