Вычислить номер виртуальной страницы и смещение для виртуальных адресов 1230005, 3274893 и 6055445, если размер страницы равен 4 Кбайт или 8 Кбайт

Требуется сравнить считывание файла через однопоточный и многопоточный файловые серверы. Получение запроса, его диспетчеризация и обработка занимают 15 миллисекунд при условии наличия данных в блочном кэше. В каждом третьем случае требуется обращение к диску, занимающее 75 миллисекунд, в течение которых поток находится в состоянии ожидания. Сколько запросов в секунду обработает однопоточный сервер? А многопоточный?

Рассмотрим, как выполняются запросы на однопоточном сервере:

Время выполнения 2х запросов = 0,105 с. Значит за секунду выполняется 2*(1\0,105)= 19 запросов.

Теперь рассмотрим случай, когда они выполняются на многопоточном сервере.

Если не считать первые 2 запроса, то на выполнение 2х запросов уходит 2*(1/0.075)=26 запросов.

Задача № 2

Запуска ожидают пять задач. Предполагаемое время их выполнения составляет 9, 6, 3, 5 и Х. В каком порядке их следует запустить, чтобы минимизировать среднее время отклика? (Ответ должен зависеть от Х).

Задача
Время выполнения					x

Чтобы минимизировать ср. время отклика надо выполнять задачи в порядке возрастания времени их выполнения (тогда за меньшее время будет выполняться большее число задач, хотя общее время выполнения не изменится).

Значит нужно вставить X чтобы не нарушить упорядоченности по возрастанию времени выполнения:

1) X<3: Порядок выполнения 5,3,4,2,1

2) 3<=X<5 Порядок выполнения3,5,4,2,1

3) 5<=x<6 Порядок выполнения 3,4,5,2,1

4) 6<=x<9 Порядок выполнения 3,4,2, 5,1

5) 9<=x Порядок выполнения 3,4,2,1,5

Задача № 3

Пять пакетных задач A, B, C, D, E поступают в однопроцессорный компьютер практически одновременно. Ожидаемое время их выполнения составляет 10, 6. 2. 4 и 8 мин. Их установленные приоритеты составляют 3, 5. 2, 1 и 4, причем 5 – высший приоритет. Определите среднее оборотное время для алгоритма приоритетного планирования (абсолютный и относительный приоритеты), пренебрегая временем, теряющемся при переключении между процессами.

Задача	a	B	C	D	e
Время выполения
Приоритета

Нарисуем схему их выполнения согласно приоритетам. B,e,a,c,d

Среднее время выполнения = (6+14+24+26+30)/5 = 20.

Среднее время выполнения = (10+16+24+26+30)/5=21,2

Задача № 4

В гибкую систему реального времени поступают четыре периодических сигнала с периодами 50, 100. 200. и 250 мс. На обработку каждого сигнала требуется 35, 20, 10 и Х времени центрального процессора. Требуется определить максимальное значение Х, при котором система остается поддающейся планированию.

Решение:

Период Т 50 100 200 250 Время выполнения t 35 20 10 Х Загрузка процессора каждой задачей – Bi = ti / Ti. Полная загрузка Btotal = СУММА (Bi). Для планирования необходимо, чтобы Btotal <=1. Таким образом, имеем уравнение: 35/50+20/100+10/200+Х/250 = 1, откуда Х = 12,5.

Задача № 5

В оперативной памяти центрального процессора может содержаться три программы. Эти программы простаивают в ожидании ввода-вывода одну треть времени. Какая часть времени процессора пропадает. Как изменится эта часть, если число программ удвоить?

Вероятность ввода вывода одной программы=1/3

Вероятность того, что все три программы находятся в ожидании ввода вывода=(1/3)в кубе. Следовательно пропадает (1/27) процессорного времени. Если число программ удвоить, то вероятность ввода вывода=(1/3)в шестой = 1/729. Столько времени CPU простаивает.

Задача 6.

Система устраняет свободные участки памяти с помощью уплотнения. Предположим, что множество свободных участков и множество сегментов данных распределены случайно, а время для чтения или записи 32-разрядного слова в памяти равно 10 нс. Сколько времени займет уплотнение 128 Мбайт памяти в худшем случае? Можно ли вывести зависимость (построить график) времени уплотнения от объема занятой памяти?

Построим график, отображающий возможные варианты соотношения свободной и занятой памяти. На оси абсцисс будем откладывать значение занятой памяти - e_з, а на оси ординат – свободной памяти – e_с. Тогда любой точке прямой АБ соответствует некоторый вариант соотношения свободной и занятой памяти. В точке А вся память занята и, следовательно, некуда перемещать, да и нет необходимости. В точке Б вся память свободна и нечего перемещать. Как видно на рис. 1, максимальный объем перемещаемых данных (64 Мбайт) соответствует точке В. Определим время уплотнения данных для этого случая. Для этого сначала найдем число слов, которое нужно считать и, соответственно записать в память в процессе уплотнения:

N_сл = 64 Мбайт / 4 байт = 64 * 2²⁰ / 2² = 2²⁴ слов.

По условию задачи время для чтения или записи 32-разрядного слова в памяти равно 10 нс. Следовательно, время перемещения в худшем случае (для передачи 64 Мбайт) будет равно:

T_макс = (t_сч + t_з ) * N_сл = (10 + 10) * 10^-9 * 2²⁴ = 335544320 * 10^-9 с = 33 мс

Задача № 7

Вычислить номер виртуальной страницы и смещение для виртуальных адресов 1230005, 3274893 и 6055445, если размер страницы равен 4 Кбайт или 8 Кбайт.

Решение:

N=A/E_стр (где N – номер виртуальной страницы, A – виртуальный адрес страницы, E_стр – размер страницы), (определяем целую часть от деления)

S=A - N*E(S- смещение)

E₁=4 Кб= 4096 байт

E₂=8Кб=8192 байт

N₁₁ = 1230005/ 4096 = 300

S₁₁=1230005-300*4096=1205

N₁₂ = 1230005/ 8192 = 150

S₁₂=1230005-150*8192=1205

N₂₁ = 3274893 / 4096 = 799

S₂₁=3274893 -799*4096=2189

N₂₂ = 3274893 / 8192 = 399

S₂₂=3274893 -399*8192=6285

N₃₁ = 6055445/ 4096 = 1478

S₃₁=6055445-1478*4096=1557

N₃₂ = 6055445/ 8192 = 739

S₃₂=6055445-739*8192=1557

Задача № 8

Объем пространства на диске, который должен быть доступен для хранения страниц, связан с максимальным количеством процессов N, количеством байтов в виртуальном адресном пространстве V и числом байтов в оперативной памяти R. Выведете формулу требований на дисковое пространство в худшем случае. Насколько эта величина реалистична?

Решение: (с семинара)

E=V*N-R, где

N- максимальное количество процессов
V-количество байтов в виртуальном адресном пространстве
R-число байтов в оперативной памяти
E-дисковое пространство

1) Для каждого процесса требуется ВАП размером V (все процессы «одинакового размера»)

(из интернета)

Введем дополнительную переменную n – число байт, требующихся одному процессу. Тогда требования на память выражаются как N*n Доступная память выражается как V+R В худшем случае R стремится к нулю, или хотя бы R <<N*n. Тогда требования на виртуальную память N*n=V+R (=0) V=N*n – т.е., фактически, все процессы будут располагаться в виртуальной памяти. Эта ситуация практически невозможна, т.к. если в операционной системе предусмотрено использование виртуальной памяти, то должно быть достаточное количество ресурсов.

Задача № 9

Считая, что команда выполняется за 10 нс, а страничное прерывание требует дополнительно N нс, напишите выражение для фактического времени выполнения команды с учетом того, что прерывания происходят каждые K команд программы.

Решение:

Пусть в одном цикле К команд. Тогда в 1 цикле происходит одно прерывание. Время выполнения цикла = K * 2 нс + N. Среднее время выполнения каждой команды = (время выполнения цикла / К) = 2нс + N/K. Фактическое время стремится к среднему.

Задача 10.

Компьютер имеет 32-разрядное адресное пространство и страницы размером 8 Кбайт. Таблица страниц целиком поддерживается аппаратно, на запись в ней отводится одно 32-разрядное слово. При запуске процесса таблица страниц копируется из памяти в аппаратуру, одно слово требует 10нс (во всех других источниках эта задача идет с 100нс, может быть у них опечатка, если да, то ответ будет 52,4%). Если каждый процесс работает в течение 100 мс(включая время загрузки таблицы страниц), какая доля времени процессора жертвуется на загрузку таблицы страниц?

При известном времени записи слова в аппаратуру для определения времени копирования таблицы страниц нужно знать число слов в таблице. Оно должно быть равно числу виртуальных страниц в виртуальном адресном пространстве. Размер виртуального адресного пространства E_в определяется разрядностью адреса, которая равна 32-м. Следовательно, E_в = 2³² байт. При заданном размере страницы E_стр = 8 Кбайт число виртуальных страниц N_стр = E_в / E_стр = 2³² / 2¹³ = 2¹⁹.

Теперь можно найти время копирования таблицы страниц в аппаратуру

T_коп = t _коп * N_стр = 10 * 2¹⁹ нс = 5242880 нс = 5,24 мс (здесь t _коп – время копирования одного слова). Так как процесс работает в течение 100 мс, то доля времени процессора, затрачиваемая на загрузку таблицы страниц будет равна

Δ = (T_коп / T_проц ) * 100 % = 5.24 / 100 * 100 % = 5,24 %

Задача № 11

Компьютер поддерживает 48-разрядные виртуальные адреса и 32-разрядные физические адреса. Размер страницы равен 8 Кбайт. Сколько требуется записей в таблице страниц и чему равен ее объе м?

Найдем число виртуальных страниц.

В самой таблице страницы хранятся только номера страниц. (чтобы лучше представить как выглядит таблица страниц откройте учебник олифера на стр. 179, приглядитесь к рисунку 5.12: посреди него таблица страниц. В ней хранится номер страницы + управляющие биты)

Размер страницы = 8 кб = 2^13 бит, след. в виртуальном адресе 13 бит выделено под смещение. Значит для хранения номера страницы нужно 19 бит. Поскольку вся информация хранится в байтах, то нам для хранения номера страницы требуется 3 байта (остальные биты пойдут под служебную информации)

Задача № 12

ОС использует алгоритм замещения страниц FIFO в системе с четырьмя страничными блоками и восемью страницами. Требуется определить, сколько страничных прерываний произойдет в системе для последовательности обращений 0172327103 при условии, что четыре страничных блока изначально пусты?

Задача № 13

ОС использует алгоритм замещения страниц LRU в системе с четырьмя страничными блоками и восемью страницами. Требуется определить, сколько страничных прерываний произойдет в системе для последовательности обращений 0172327103 при условии, что четыре страничных блока изначально пусты?

Задача № 14

В системе есть 4 процесса и 5 ресурсов, которые можно предоставить процессам. Текущее распределение ресурсов и максимальное их количество, необходимое процессам следующее: