Приложение 5
Примеры решения задач по дисциплине
“Операционные системы” Задача № 2.1 Работу однопоточного сервера можно представить временной диаграммой, показанной на рис. 1 а). Как следует из диаграммы за промежуток времени, равный 105 мс обрабатывается два запроса, поскольку потоки работают последовательно (сервер однопоточный). Таким образом. За 1 с будет обработано Nз = (1000 / 105) * 2 = 19, 04 запроса.
[pic]
Рис. 1 Работа многопоточного сервера представляется временной диаграммой, показанной на рис. 1 б). В этом случае два запроса обрабатывается за промежуток времени, равный 75 мс, поскольку потоки работают параллельно (сервер многопоточный). Таким образом. За 1 с будет обработано Nз = (1000 / 75) * 2 = 26, 6 запроса. Задача № 2.3 Последовательное выполнение заданий показано на временной диаграмме рис. 2 а). Здесь черным цветом обозначено счета (процессора). Каждое задание требует для своего выполнения 10 мин. времени процессора, а так как по условию вероятность ввода-вывода равна 0,5, то это означает, время, затрачиваемое заданием на ввод-вывод тоже равно 10 мин. Суммарное время выполнения одного задания равно сумме времени ввода-вывода и счета, т.е. 20 минутам:

Tвып = Tвв + Tсч = 10 + 10 = 20 мин.

Два задания при последовательном выполнении займут 40 мин. машинного времени. При этом вероятности ввода-вывода и счета по каждому заданию равны:

Pвв = Pсч = Tвв / Tвып = Tсч / Tвып = 10 / 20 = 0,5.

Теперь определим вероятность ввода-вывода при одновременном выполнении двух заданий (рис. 2 б). По правилу вычисления вероятности совместного появления нескольких событий (в нашем случае одновременного ввода-вывода двух заданий) она равна произведению вероятностей этих событий, т.е.

P2вв = Pвв * Pвв = 0,5 * 0,5 = 0,25.

Соответственно вероятность счета (работы процессора) при одновременном выполнении двух заданий равна

P2сч = 1 – P2вв = 1 – 0,25 = 0,75.

Для выполнения 20 мин. счета (это нужно для выполнения двух заданий) при таком значении вероятности работы процессора потребуется следующее значение времени работы процессора

Tпроц = T2сч / P2сч = 20 / 0,75 = 26,6 мин.

Заметим, что за это время задания выполнят все операции ввода-вывода (на это требуется 20 мин.). Таким образом, при одновременном выполнении заданий потребуется 26,6 мин. машинного времени.

[pic]
Рис. 2

Задача № 2.4 На начальном этапе решение задач можно пояснить схемами, приведенными на рис. 3. На рис. 3 а) показан цикл работы процессора, а на рис. 3 б) – временная диаграмма выполнения задач. Определим продолжительность цикла на первом этапе выполнения задач (решаются задачи A, B, C – см. рис. 3 а): T1ц = 20 * 3 + 2 * 3 = 66 мс Очевидно, что первой будет решена задача B. Время ее решения можно найти из следующего выражения: Tb = (tb / tкв ) * T1ц = (2 * 60 *1000 / 20) * 66 = 396000 мс = 396 с = 6,6 мин. Здесь tb – время решения задачи B в монопольном режиме (2 мин.), tкв – время кванта (20 мс). Первый этап завершается решением задачи B, его продолжительность – 6,6 мин. Задачи A и C на этом этапе также решались в течение двух минут. Поэтому после завершения задачи B схема цикла по рис. 3 а) преобразуется к виду по рис. 4.
[pic]
[pic]
Рис. 3

[pic]
Рис. 4 Определим продолжительность цикла на втором этапе выполнения задач (решаются задачи A и C – см. рис. 4): T2ц = 20 * 2 + 2 * 2 = 44 мс Очевидно, что первой (из задач A и C) будет решена задача A. Время ее решения можно на втором этапе найти из следующего выражения: T2a = ((ta - tb ) / tкв ) * T1ц = ((4 – 2) * 60 *1000 / 20) * 44 = 264000 мс = 264 с = 4,4 мин.
Полное время решения задачи A с учетом того, что она решалась на двух этапах (см. рис. 3 б) составит значение Ta = T2a + Tb = 6,4 + 4,4 = 11 мин. После завершения второго этапа решается (в режиме квантования!) только задача C (рис. 5).
[pic]
Рис. 5 Продолжительность цикла на третьем этапе выполнения задач (решается только задача C – см. рис. 5) T3ц = 20 + 2 = 22 мс. На этом этапе задача C завершится через промежуток времени T3с = ((tс – ta) / tкв ) * T3ц = ((7 – 4) * 60 * 1000 / 20) * 22 = 198000 мс = 198 с = 3,3 мин.
Полное время решения задачи C составит значение Tc = Ta + T3с = 11 + 3?3 = 14,3 мин. Теперь можно найти среднее время решения задач A, B, C: tср = (ta + ta + tс) / 3 = (11 + 6,6 + 14,3) / 3 = 10,63 мин.

Задача № 2.13 Для заполнения столбцов “Требуется” необходимо от элементов столбцов “Максимальные требования” вычесть соответствующие элементы столбца “Предоставлено”. В результате получим следующую таблицу:

|Процесс |Предоставлено |Максимальные требования | Требуется | Доступно |
| |R1 R2 R3 R4 |R1 R2 R3 R4 |R1 R2 R3 R4 |R1 R2 R3 R4 |
|A | 0 0 1 2 | 0 0 1 2 | 0 0 0 0 | 2 1 0 0 |
|B | 2 0 0 0 | 2 7 5 0 | 0 7 5 0 | |
|C | 0 0 3 4 | 6 6 5 6 | 6 6 2 2 | |
|D | 2 3 5 4 | 4 3 5 6 | 2 0 0 2 | |
|E | 0 3 3 2 | 0 6 5 2 | 0 3 2 0 | |

Немедленное удовлетворение запроса (0, 1, 0, 0) по требованию процесса С приведет к уменьшению вектора свободных (доступных) ресурсов до значения (2, 0, 0, 0), кроме того изменится вектор ресурсов, предоставленных процессу С. Таким образом, исходная таблица преобразуется к следующему виду:

|Процесс |Предоставлено |Максимальные требования | Требуется | Доступно |
| |R1 R2 R3 R4 |R1 R2 R3 R4 |R1 R2 R3 R4 |R1 R2 R3 R4 |
|A √ (1) | 0 0 1 2 | 0 0 1 2 | 0 0 0 0 | 2 0 0 0 |
|B | 2 0 0 0 | 2 7 5 0 | 0 7 5 0 | |
|C | 0 1 3 4 | 6 6 5 6 | 6 5 2 2 | |
|D √ (2) | 2 3 5 4 | 4 3 5 6 | 2 0 0 2 | |
|E √ (3) | 0 3 3 2 | 0 6 5 2 | 0 3 2 0 | |

Теперь нужно определить, безопасно ли полученное распределение ресурсов. Рассмотрим процесс A. Для его завершения не требуются какие-либо ресурсы. Он может завершиться и освободить занятые ресурсы, после чего вектор доступных ресурсов будет иметь следующее значение (2, 0, 1, 2). Маркируем процесс A (ставим около него значок √ и отмечаем в скобках цифру 1 – это первый выполненный процесс). Переходим к рассмотрению процесса B. Сравниваем значение ресурсов, которые ему требуются для завершения (0, 7 , 5, 0) с вектором свободных ресурсов (2, 0, 1, 2). Как видно ресурсов недостаточно для завершения процесса. Переходим к рассмотрению процесса C и проводим аналогичный анализ, в результате которого определяем невозможность его завершения. Рассматриваем возможность завершения процесса D. В данном случае требуемые для его завершения ресурсы (2, 0, 0, 2) меньше вектора свободных ресурсов (2, 0, 1, 2). Следовательно, процесс D может завершиться, маркируем его и корректируем вектор свободных ресурсов, который после завершения процесса D будет иметь следующее значение (4, 3, 6, 6). Рассматриваем процесс E. В данном случае достаточно ресурсов для его завершения. Маркируем процесс E и корректируем вектор свободных ресурсов до значения (4, 6, 9, 8). Вновь рассматриваем процесс B. Для его выполнения необходимы ресурсы в соответствии с вектором (0, 7, 5, 0). Он не может быть выполнен, так как нет в наличии семи единиц ресурса 2. Рассматриваем процесс C. Он также не может быть выполнен, так как вектор свободных ресурсов (4, 6, 9, 8) не позволяет удовлетворить требования по ресурсу 1. Таким образом, если немедленно удовлетворить запрос процесса C, то в тупиковой ситуации оказываются процессы B и С.

Задача № 3.1

Построим график, отображающий возможные варианты соотношения свободной и занятой памяти. На оси абсцисс будем откладывать значение занятой памяти - eз, а на оси ординат – свободной памяти – eс. Тогда любой точке прямой АБ соответствует некоторый вариант соотношения свободной и занятой памяти. В точке А вся память занята и, следовательно, некуда перемещать, да и нет необходимости. В точке Б вся память свободна и нечего перемещать. Как видно на рис. 6, максимальный объем перемещаемых данных (64 Мбайт) соответствует точке В. Определим время уплотнения данных для этого случая. Для этого сначала найдем число слов, которое нужно считать и, соответственно записать в память в процессе уплотнения: Nсл = 64 Мбайт / 4 байт = 64 * 220 / 22 = 224 слов. По условию задачи время для чтения или записи 32-разрядного слова в памяти равно 10 нс. Следовательно, время перемещения в худшем случае (для передачи 64 Мбайт) будет равно: Tмакс = ( tсч + tз ) * Nсл = (10 + 10) * 10-9 * 224 = 335544320 * 10-9 с = 33 мс

[pic]

Рис. 6

Задача № 3.6

При известном времени записи слова в аппаратуру для определения времени копирования таблицы страниц нужно знать число слов в таблице. Оно должно быть равно числу виртуальных страниц в виртуальном адресном пространстве. Размер виртуального адресного пространства Eв определяется разрядностью адреса, которая равна 32-м. Следовательно, Eв = 232 байт. При заданном размере страницы Eстр = 8 Кбайт число виртуальных страниц Nстр = Eв / Eстр = 232 / 213 = 219. Теперь можно найти время копирования таблицы страниц в аппаратуру Tкоп = t коп * Nстр = 10 * 219 нс = 5242880 нс = 5,24 мс (здесь t коп – время копирования одного слова). Так как процесс работает в течение 100 мс, то доля времени процессора, затрачиваемая на загрузку таблицы страниц будет равна Δ = ( Tкоп / Tпроц ) * 100 % = 5.24 / 100 * 100 % = 5,24 %

Задача № 3.18

Среднее время Tср преобразования виртуального адреса в физический адрес при наличии в компьютере блока TLB можно найти из выражения Tср = pTLB * TTLB + pОП * TТС , где pTLB – вероятность обращения к блоку TLB при преобразовании виртуального адреса;
TTLB – время преобразования виртуального адреса при обращении к блоку TLB (1 нс); pОП – вероятность обращения к памяти при преобразовании виртуального адреса;
TТС – время преобразования виртуального адреса при обращении к таблице страниц (5 нс). Поскольку pTLB = 1 – pОП , то из условия требования среднего времени преобразования адреса за время не более 1 нс, можно записать следующее соотношение (1 – pОП ) * TTLB + pОП * TТС