Детерминированное моделирование

Один из важных методов оценки называется аналитической оценкой. Аналитическая оценка на основании алгоритма и работы системы получает формулу или численное значение числа операций, которые выполняет алгоритм для этой работы.

Одним из типов аналитической оценки является детерминистическое моделирование. При этом методе оценивается конкретная предопределенная задача и определяются действия алгоритма для ее выполнения.

Например, пусть имеются 5 процессов, поступивших в момент времени 0:

Р₁ 10

Р₂ 29

Р₃ 3

Р₄ 7

Р₅ 12

Рассмотрим стратегии FCFS, SJF и RR (q =10). Какой из алгоритмов даст наименьшее значение времени ожидания?

В случае стратегии FCFS процессы выполнялись бы следующим образом (рис. 7.7):

P1	P2	P3	P4	P5

Рисунок 7.7 – Диаграмма Ганта для стратегии FCFS

Время ожидания равно 0 мс для процесса P₁, 10 мс для процесса P₂, 39 мс для процесса P₃, 42 мс для процесса P₄ и 49 мс для процесса P_5. Таким образом, среднее время ожидания равно (0+10+39+42+49)/5 = 28 мс.

В случае стратегии SJF процессы выполнялись бы следующим образом (рис. 7.8):

P3	P4	P1	P5	P2

Рисунок 7.8 – Диаграмма Ганта для стратегии SJF

Время ожидания равно 10 мс для процесса P₁, 32 мс для процесса P₂, 0 мс для процесса P₃, 3 мс для процесса P₄ и 20 мс для процесса P_5. Таким образом, среднее время ожидания равно (10+32+0+3+20)/5 = 13 мс.

В случае стратегии RR процессы выполнялись бы следующим образом (рис. 7.9):

P1	P2	P3	P4	P5	P2	P5	P2

Рисунок 7.9 – Диаграмма Ганта для стратегии RR

Время ожидания равно 0 мс для процесса P₁, 32 мс для процесса P₂, 20 мс для процесса P₃, 23 мс для процесса P₄ и 40 мс для процесса P_5. Таким образом, среднее время ожидания равно (0+32+20+23+40)/5 = 23 мс.

Таким образом, мы видим, что стратегия SJF дает наилучшее значение среднего времени ожидания.

Такое моделирование является простым и быстрым. Однако, оно дает оценки только для конкретного случая. Главное использование такого моделирования – описание алгоритмов и иллюстрация их примерами. Рассмотрение множества примеров позволяет выявить тенденции в поведении алгоритмов.

Однако такое моделирование слишком специфично и требует слишком много точных знаний, чтобы быть полезным.

Моделирование очередей

Процессы поступают в систему и завершаются в непредсказуемые моменты времени, поэтому не существует статического множества процессов, работающих в системе. Что, однако, может быть оценено, так это распределение процессорного времени и потребность процессов в непрерывной работе на процессоре. Эти интервалы могут быть измерены и аппроксимированы или просто оценены. Результатом является математическая функция, оценивающая потребность процессов в непрерывной работе на процессоре. В общем случае такое распределение является экспоненциальным и оценивается средним значением. В простейшем случае, если процессы поступают равномерно, может быть задана интенсивность их поступления. В каждом из этих случаев для большинства алгоритмов могут быть вычислены значения всех критериев.

Компьютерная система описывается как сеть серверов. У каждого сервера имеется своя очередь ожидающих процессов. Зная интенсивность поступления процессов и запросов, можно вычислить интересующие нас значения.

Например, пусть n – средняя длина очереди (исключая обслуживаемый процесс), w – среднее время ожидания в очереди, l - средняя интенсивность поступления новых процессов. Тогда за время w в систему поступит новых процессов.

Если система находится в устойчивом состоянии, то это число совпадает с длиной очереди:

.

Эта формула называется формулой Литтла. Она особенно полезна, так как справедлива для любого алгоритма планирования и любой интенсивности.

Можно использовать эту формулу для вычисления одного из значений, если известны остальные два.

Анализ очередей полезен для сравнения алгоритмов, но имеет ограничения. Классы распределений и алгоритмов слишком ограничены. Математика смешанных алгоритмов слишком сложна для работы с ней. Так, распределение часто является неравномерным. Для его математической трактовки требуется сделать ряд предположений, которые могут быть некорректными. Поэтому такие модели это лишь приближение к реальным системам. В итоге точность результатов спорна.

Имитация

Чтобы получить более точную оценку алгоритмов можно использовать имитацию. Она предусматривает создание программной модели компьютерной системы.

Программные структуры данных в такой модели представляют главные компоненты компьютерной системы. Кроме того, в эмуляторе имеется переменная, представляющая таймер. При увеличении этой переменной эмулятор модифицирует состояние системы, отражая деятельность устройств, процессов и планировщиков. По окончании работы модели выдается статистика.

Данные для имитации могут быть сгенерированы многими способами. Главный метод – использование генератора случайных чисел для генерации процессов, интервалов непрерывного использования процессора, запросов и т. п., в соответствии с возможным распределением. Распределение может быть выбрано математически (равномерное, экспоненциальное, Пуассона) или эмпирически, путем замеров в реальных системах.

Результат подобного моделирования может быть неточным, поскольку моделируется только частота событий, а не порядок их наступления. Чтобы избежать подобной неточности, для каждого процесса производится трассировка событий. Тогда одни и те же данные могут быть использованы для сравнения различных алгоритмов. Такой подход дает наиболее точные результаты, но достаточно труден в реализации.

 

Контрольные вопросы

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

2. Опишите различия между долгосрочным, среднесрочным и краткосрочным планировщиками.

3. Что означает термин «планирование без вытеснения»?

4. Что такое диспетчеризация?

5. Дано множество процессов со временем непрерывной работы на процессоре, заданным в миллисекундах. Процессы поступают в порядке Р₁, Р₂, Р₃, Р₄, Р₅ в момент времени 0.

Построить диаграммы Ганта, иллюстрирующие выполнение этих процессов с использованием стратегий FCFS, SJF, HPF (без вытеснения) и RR (величина кванта равна 1).

Какая из стратегий дает минимальное значение среднего времени ожидания и среднего времени оборота?

Процесс	Время	Приоритет
Р1
Р2
Р3
Р4
Р5

6. Приведите пример алгоритма планирования, в результате работы которого процесс, располагая всеми необходимыми ресурсами, может бесконечно долго находиться в системе, не имея возможности завершиться.

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

 

 

Взаимодействие процессов

Параллельно выполняемые процессы могут быть либо независимыми (independent processes) либо взаимодействующими (cooperating processes). Процесс является независимым, если он не влияет на выполнение других процессов в системе, а они в свою очередь не влияют на его выполнение. В противном случае процесс является взаимодействующим. Очевидно, что ни один процесс не может совместно использовать никакие данные с независимым процессом. С другой стороны, любые процессы, совместно использующие данные, являются взаимодействующими.

Существует несколько причин для предоставления средств взаимодействия процессов:

­ Совместное использование информации (information sharing). В связи с тем, что несколько пользователей могут интересоваться одной и той же информацией, необходимо предоставлять возможность параллельного доступа к этому типу ресурсов.

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

­ Модульность (modularity). Система может быть сконструирована с использованием модульного подхода, причем каждой системной функции соответствует отдельный процесс.

­ Удобство (convinience). Даже отдельный пользователь может выполнять несколько задач параллельно.

Для организации взаимодействия процессов операционная система должна предоставлять средства коммуникации между процессами (IPC – interprocess communication) и средства синхронизации их работы.

Существует две фундаментальных модели межпроцессного взаимодействия: разделяемая память (sharing memory) и передача сообщений (message passing). В первом случае выделяется область памяти достаточно большого размера, совместно используемая несколькими процессами. Процессы могут обмениваться информацией, читая и записывая данные в эту область. Во втором случае взаимодействие осуществляется за счет обмена сообщениями между процессами. Такая модель полезна при обмене небольшими объемами данных. Современные системы, как правило, поддерживают обе модели.