Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа
Планирование в системах пакетной обработки информации
Алгоритмы без переключений (не вытесняющее планирование).
Общим свойством алгоритмов является отсутствие прерываний по тайме- ру: запущенная задача работает столько, сколько ей необходимо. Когда текущий процесс блокируется, запускается следующий в очереди, а когда блокировка снимается, процесс попадает в конец очереди.
«Первым пришел – первым обслужен»
Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают.
«Кратчайшая задача – первая»
Если в очереди есть несколько одинаково важных задач, планировщик вы- бирает первой самую короткую задачу.
Пример: В систему пакетной обработки поступило четыре задачи: A, B, C и
D. Время центрального процессора, требуемое для полного выполнения этих за- дач составляет a=8, b=4, c=2 и d=4 мин соответственно. Предположим, что вре- мя, затрачиваемое системой на переключение контекста, пренебрежительно ма- ло. Алгоритм, применяемый в системе – «Первым пришел – первым обслужен». Если система запустит задачи в порядке A, B, C, D, оборотное время задачи A со- ставит 8 мин, B – 12 мин, С – 14 мин и D –18 мин. Оборотное время – статисти- чески усредненное время от момента получения задачи до момента ее выполне- ния. Первая задача выполняется за время a, вторая – за время а + b и т. д. Сред- нее оборотное время находится как среднее арифметическое из среднего оборот- ного времени каждой задачи. Среднее время в нашем случае составляет: (4а + 3b
+ 2с + d)/4=13 мин. Очевидно, что вклад времени задачи, запущенной самой первой (задачи A) в среднее больше, чем интервалов времени всех остальных за- дач.
Запустим задачи в соответствии с алгоритмом «Кратчайшая задача – пер- вая» в следующей последовательности: C, B, D, A. Теперь значения оборотного времени составляют 2, 6, 10 и 18 мин соответственно, а среднее время равно 9 мин. Точно так же рассматривается система из любого количества задач.
Алгоритмы с переключениями
Циклическое планирование
Каждому процессу предоставляется некоторый интервал времени процес- сора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу. Если процесс блокируется или прекращает работу раньше, переход управления проис- ходит в этот момент.
Приоритетное планирование
Каждому процессу присваивается приоритет, и управление (в момент пла- нирования) передается готовому к работе процессу с самым высоким приорите- том.
2 Планирование периодических событий в системах реального времени
Внешние события, на которые система должка реагировать, называются периодическими если они возникают через регулярные интервалы времени. Воз- можно наличие нескольких периодических потоков событий, которые система должна обрабатывать. В зависимости от времени, затрачиваемого на обработку каждого из событий, может оказаться, что система не в состоянии своевременно обработать все события. Если в систему поступает т периодических событий, событие с номером i поступает с периодом Tiсекунд, и на его обработку уходит tiсекунд работы процессора, все потоки могут быть своевременно обработаны только при выполнении условия:
m
åti £ 1
i=1 Ti
(1).
Системы реального времени, удовлетворяющие этому условию, называют- ся поддающимися планированию пли планируемыми.
Пример: рассмотрим гибкую систему реального времени с тремя периоди- ческими сигналами с периодами в 100, 200 и 500 мс соответственно. Если на об- работку этих сигналов уходит 50, 30 и 100 мс соответственно, система является поддающейся планированию, поскольку 0,5 + 0,15 + 0,2 < 1. Даже при добавле- нии четвертого сигнала с периодом в 1 с системой все равно можно будет управ- лять при помощи планирования, пока время обработки сигнала не будет превы- шать 150 мс. В этих расчетах существенным является предположение, что время переключения между процессами пренебрежимо мало.
3. Взаимоблокировки (тупики)
Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа
Когда в системе существует несколько экземпляров ресурсов каждого ти- па, для описания и обнаружения взаимоблокировок необходим матричный ме- тод.
Пусть в системе n процессов (Pi), от Р1, до Pn(1 £ i £ n ).
Пусть т – это число классов ресурсов, причем в системе E1 ресурсов клас-
са 1, Е2 ресурсов класса 2 и, в общем, Ej ресурсов класса j (где 1 £ j £ m ). Е=(E1,
E2,… Em) – это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии экземпляров каждого ресурса. Например, если класс 1
представляет собой накопители на гибких дисках, то Е1=2 означает, что в систе- ме есть два дисковода.
В любой момент времени некоторые из ресурсов могут оказаться занятыми и, соответственно, недоступны. А=(A1, A2, … Am) – вектор доступных ресурсов, где Ajравно количеству экземпляров ресурса j, доступных в текущий момент (то есть не использующихся). Если оба накопителя на гибких дисках заняты, A1 бу- дет равно 0. С – матрица текущего распределения, i-я строка в матрице С говорит о том, сколько представителей каждого класса ресурсов в данный момент ис- пользует процесс Pi.
Таким образом, Cij– это количество экземпляров ресурса j, которое зани- мает процесс Pi:
éC11
ê
C =êC21
C12
C22
...
...
C1m ù
|
2m ú
ê...
ê
...
...
... ú
ú
ëCn1
Cn2
...
Cnm û
R – матрица запросов. Аналогично матрице С, Rij– это количество экзем- пляров ресурса j которые хочет получить процесс Рi.
éR11
ê
R =êR21
R12 R22
...
...
R1m ù
|
2m ú
ê...
ê
...
...
... ú
ú
ëRn1
Rn2
...
Rnm û
Если сложить все экземпляры ресурса j, предоставленные процессам и до- ступные в данный момент, то в результате мы получим существующее в системе количество экземпляров этого класса ресурсов.
n
åCij+ Aj = Ej
i =1
(2).
Пример:
Пусть в системе четыре привода гибких дисков (E1=4), два принтера (E2=2), три сканера (E3=3) и один привод оптических дисков (E4=1): E=(4, 2, 3, 1). В определенный момент времени процесс P1 использует один сканер (C13=1), процесс P2 – два накопителя на гибких дисках (C21=2) и единственный привод оптических дисков (C24=1), процесс P3 использует один принтер (C32=1) и
два сканера (C33=2):
é0
|
êë0
Ugrave;
|
Uacute;
1 2 0úû
Согласно формуле (2), рассчитаем значения вектора свободных ресурсов:
n
Aj=Ej-åCij, A=(2, 1, 0, 0).
i =1
Кроме того, для завершения работы каждому процессу требуется еще не- которое количество некоторых ресурсов:
é2
|
êë2
Ugrave;
| |
|
1 0 0úû
Для нормального продолжения работы каждого процесса следует предо- ставить ему все требуемые ресурсы (не смотря на уже занятые). По окончании работы процесс высвободит все используемые ресурсы.
В нашем случае процессы P1 и P2 запрашивают ресурсы, свободных экзем- пляров которых в системе нет. Если операционная система предоставит все тре- буемые ресурсы процессу P3, то по окончании его работы, за счет высвободив- шихся ресурсов ситуация будет выглядеть следующим образом:
é0 0 1 0ù
ê ú
é2 0
ê
Ugrave;
ú
C = ê2 0
0 1ú, R = ê1 0 1
0ú, A=(2, 2, 2, 0).
êë0 0 0
0úû
êë0
0 0 0úû
Теперь можно предоставить требуемые ресурсы процессу P2, а по оконча- нии его работы – процессу P1.
Так как существует последовательность предоставления ресурсов всем
процессам, приводящая к нормальному завершению всех процессов, то система не находится в состоянии взаимоблокировки.
4. Моделирование взаимоблокировок
Холт показал, как взаимодействия между процессами и устройствами (ре- сурсами) могут быть смоделированы с использованием направленных графов. У графов имеется два вида узлов: процессы, показанные окружностями, и ресурсы, показанные квадратами (Рисунок 1). Направленное ребро, которое следует от уз- ла ресурса (квадрата) к узлу процесса (окружности), означает, что этот ресурс был ранее запрошен, получен и на данный момент удерживается (и использует- ся) этим процессом. На рисунке (Рисунок 1, а) ресурс R в данное время выделен процессу А.
Направленное ребро, идущее от процесса к ресурсу, означает, что процесс в данное время заблокирован в ожидании высвобождения этого ресурса. На ри- сунке (Рисунок 1, б) процесс В ожидает высвобождения ресурса S. На рисунке (Рисунок 1, в) мы наблюдаем взаимоблокировку: процесс С ожидает высвобож- дения ресурса U, который в данный момент удерживается процессом D. Процесс D не собирается высвобождать ресурс U, поскольку он ожидает высвобождения ресурса T, удерживаемого процессом С. Оба процесса находятся в состоянии вечного ожидания. Циклическая структура графа означает, что мы имеем дело с взаимоблокировкой, включившей процессы и ресурсы в цикл (предполагается, что в системе есть только один ресурс каждого типа). В данном примере полу- чился следующий цикл: C-T-D-U-C.
а б в
Рисунок 1. Графы распределения ресурсов: ресурс занят (а); запрос ресурса и блокировка (б); взаимоблокировка (в)
Ресурсные графы являются инструментом, позволяющим понять, приводит ли определенная последовательность запросов и возвратов ресурсов к взаимо- блокировке. ОС шаг за шагом осуществляет запросы и возвраты ресурсов, и по- сле каждого шага проверяет граф на наличие каких-либо циклов. Если образует- ся цикл, значит, возникла взаимоблокировка, а если нет, значит, нет и взаимо- блокировки. Хотя здесь рассматривался граф ресурсов, составленный для случая использования по одному ресурсу каждого типа, ресурсные графы также могут быть применены для обработки нескольких ресурсов одного и того же типа (Holt, 1972).
5. Моделирование многозадачности
При использовании многозадачности повышается эффективность загрузки центрального процессора. Так, если средний процесс выполняет вычисления только 20 % от того времени, которое он находится в памяти, а все остальное время ожидает завершения операций ввода-вывода, то при присутствии в памяти одновременно пяти процессов центральный процессор должен быть занят все время. Это предположение не совсем верно, поскольку оно рассматривает ситуа- цию, когда все пять процессов никогда не ожидают завершения операции ввода- вывода одновременно.
Более совершенная модель рассматривает эксплуатацию центрального про- цессора с точки зрения теории вероятности. Предположим, что процесс проводит часть р своего времени в ожидании завершения операции ввода-вывода. Если в памяти находится одновременно п процессов, вероятность того, что все п про- цессов ждут ввод-вывод (в этом случае центральный процессор будет бездей- ствовать), равна рn. Тогда степень загрузки центрального процессора S будет вы- ражаться формулой:
S = 1-рп (3).
Пример:
Рассмотрим загруженность процессора для случаев с пятью типами про- цессов (Рисунок 2).
 |
Рисунок 2 – значения степени загруженности центрального процессора
Из рисунка видно, что при наличии трех процессов (n=3) загруженность процессора составляет S=99,2% при p=20%; S=93,6% при p=40%; S=78,4% при р=60%, S=48,8% при р=80% и процессор загружен только на 27,1% при p=90%.
6. Анализ производительности многозадачных систем
Для анализа систем пакетной обработки рассмотрим компьютерный центр, в котором среднее время ожидания ввода-вывода задачами равно 80%. Ровно в полночь подаются на выполнение 4 задания (Рисунок 3). Первая задача, посту- пившая в 0 часов 0 минут, требует 4 мин работы процессора. Тогда при 80 % времени ожидания ввода-вывода, процесс работает только 20% времени (0,20) и за каждую минуту своего нахождения в памяти задача использует только 12 с (0,2 мин) времени процессора, даже если нет никаких других параллельных за- даний, также желающих занять процессор. Остальные 48 с процесс проводит в ожидании ввода-вывода. Таким образом, задача должна находиться в памяти по крайней мере 20 мин для того, чтобы процессор сделал работу, требующую на самом деле всего 4 мин. При этом все остальное время процессор простаивает.
С 0:00 до 0:10 в памяти находится целиком первая задача и выполняется половина работы (2 мин работы процессора). Когда в 0:10 поступает второе за- дание, загрузка процессора увеличивается с S=0,20 до S=0,36 (согласно формуле
3) вследствие более высокой степени многозадачности (Рисунок 3). Однако при циклическом планировании каждое задание получает для себя половину времени процессора, поэтому за каждую минуту нахождения в памяти выполняется часть задачи, требующая 0,18 (0,36/2) мин работы процессора. Заметим, что добавле- ние второй задачи обходится первой задаче всего в 10% ее производительности. Время использования процессора за минуту реального времени уменьшилось с 0,20 мин до 0,18 мин.
В 0:15 поступает третье задание. В этот момент для первой задачи про- цессор отработал 2,9 мин, для второй – 0,9 мин. Степень многозадачности теперь равна 3, S=0,49 и каждое задание получает для себя около 0,16 мин работы про- цессора за минуту реального времени. Тогда с 0:15 до 0:20 для каждого из трех заданий процессор работает по 0,8 мин. В 0:20 поступает четвертая задача. На рисунке (Рисунок 3) представлена полная последовательность событий. В табли- цах приведены все исходные (Таблица 3) и расчетные (таблица 4) данные.
|
0 10 15 20 22 31,7 t,мин
|
Таблица 4 – Данные о загруженности процессора
| Степень многозадачно- сти (n) | ||||
| Загруженность процес- сора (S) | 0,2 (20%) | 0,36 (36%) | 0,49 (49%) | 0,59 (59%) |
| Производительность одного процесса (S/n) | 0,2 | 0,18 | 0,16 | 0,15 |
С момента поступления последней задачи в систему, процессу А необхо- димо доработать 0,3 мин процессорного времени. При производительности од- ного процесса в системе с четырьмя процессами равной 0,15, для выработки сво- его времени процессу А необходимо находиться в системе ровно 2 минуты (до 0:22). С этого момента в системе останется только 3 процесса, и скорее других завершится процесс С в 0 часов 27,6 мин.
Последним в системе завершится процесс D в 0 часов 31,7 мин, проведя в ней, в общей сложности, 11,7 мин.
Учебно-методическое обеспечение дисциплины
Список обязательной литературы
1. Таненбаум, Э. Современные операционные системы / Эндрю Танен- баум. – СПб.: Питер, 2002. – 1040 с.
2. Гордеев, А.В. Операционные системы: Учебник для вузов / А.В. Гордеев. – СПб.: Питер, 2005. – 416 с.
3. Столлингс, В. Операционные системы // Вильям Столлингс. – М.: Вильямс, 2004. – 848 с.
4. Иртегов, Д. Введение в операционные системы / Д. В. Иртегов. — СПб, БХВ-Петербург, 2008. – 1040 с.
5. Дубаков, А.А. Операционные системы. Дистанционное обучение / А.А. Дубаков – Томск: ТПУ, 1999.
Список дополнительной литературы
5.Партыка, Т.Л. Операционные системы, среды и оболочки: Учебное пособие / Т.Л. Партыка, И.И. Попов. – М.: Форум: ИНФРА, 2003. – 400 с.
6.Таненбаум, Э. Операционные системы. Разработка и реализация / Эндрю Таненбаум, А. Вудхалл. – СПб.: Питер, 2007. – 704 с.
7.Александров, Е.К. Микропроцессор 80386: как он работает и как ра- ботают с ним: Учеб. пособие / Е.К. Алксандров, Ю.Л. Рудня, под. ред. проф. Д.В. Пузанкова. – СПб.: Эл-матор, 1994. – 274 с.
8.Соломон, Д. Внутреннее устройство Microsoft Windows 2000. Ма- стер-класс / Д. Соломон, М. Руссинович. – Пер. с англ. – СПб.: Пи- тер; М.: Издательско-торговый дом «Русская редакция», 2001. – 752 с.
10.Стивенс, У. UNIX: Взаимодействие процессов / У. Стивенс. – СПб.: Питер, 2002. – 576 с.