Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа

Планирование в системах пакетной обработки информации

Алгоритмы без переключений (не вытесняющее планирование).

Общим свойством алгоритмов является отсутствие прерываний по тайме- ру: запущенная задача работает столько, сколько ей необходимо. Когда текущий процесс блокируется, запускается следующий в очереди, а когда блокировка снимается, процесс попадает в конец очереди.

«Первым пришел – первым обслужен»

Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают.

«Кратчайшая задача – первая»

Если в очереди есть несколько одинаково важных задач, планировщик вы- бирает первой самую короткую задачу.

Пример: В систему пакетной обработки поступило четыре задачи: 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 а + 3 b

+ 2 с + d)/4=13 мин. Очевидно, что вклад времени задачи, запущенной самой первой (задачи A) в среднее больше, чем интервалов времени всех остальных за- дач.

Запустим задачи в соответствии с алгоритмом «Кратчайшая задача – пер- вая» в следующей последовательности: C, B, D, A. Теперь значения оборотного времени составляют 2, 6, 10 и 18 мин соответственно, а среднее время равно 9 мин. Точно так же рассматривается система из любого количества задач.

Алгоритмы с переключениями

Циклическое планирование

Каждому процессу предоставляется некоторый интервал времени процес- сора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу. Если процесс блокируется или прекращает работу раньше, переход управления проис- ходит в этот момент.

Приоритетное планирование

Каждому процессу присваивается приоритет, и управление (в момент пла- нирования) передается готовому к работе процессу с самым высоким приорите- том.

2 Планирование периодических событий в системах реального времени

Внешние события, на которые система должка реагировать, называются периодическими если они возникают через регулярные интервалы времени. Воз- можно наличие нескольких периодических потоков событий, которые система должна обрабатывать. В зависимости от времени, затрачиваемого на обработку каждого из событий, может оказаться, что система не в состоянии своевременно обработать все события. Если в систему поступает т периодических событий, событие с номером i поступает с периодом T iсекунд, и на его обработку уходит ti секунд работы процессора, все потоки могут быть своевременно обработаны только при выполнении условия:

å 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).

Пусть т – это число классов ресурсов, причем в системе E 1 ресурсов клас-

са 1, Е2 ресурсов класса 2 и, в общем, Ej ресурсов класса j (где 1 £ j £ m ). Е =(E1,

E2,… Em) – это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии экземпляров каждого ресурса. Например, если класс 1

представляет собой накопители на гибких дисках, то Е 1=2 означает, что в систе- ме есть два дисковода.

В любой момент времени некоторые из ресурсов могут оказаться занятыми и, соответственно, недоступны. А =(A 1, A 2, … Am) – вектор доступных ресурсов, где Aj равно количеству экземпляров ресурса j, доступных в текущий момент (то есть не использующихся). Если оба накопителя на гибких дисках заняты, A 1 бу- дет равно 0. С – матрица текущего распределения, i -я строка в матрице С говорит о том, сколько представителей каждого класса ресурсов в данный момент ис- пользует процесс Pi.

Таким образом, Cij– это количество экземпляров ресурса j, которое зани- мает процесс Pi:

é C 11

ê

C =ê C 21

C 12

C 22

...

C 1 m ù

2 m ú

ê...

...

... ú

ë Cn 1

Cn 2

...

Cnm û

R – матрица запросов. Аналогично матрице С, Rij– это количество экзем- пляров ресурса j которые хочет получить процесс Рi.

é R 11

R =ê R 21

R 12 R 22

...

R 1 m ù

2 m ú

ê...

...

... ú

ë Rn 1

Rn 2

...

Rnm û

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

å Cij + Aj = Ej

i =1

(2).

Пример:

Пусть в системе четыре привода гибких дисков (E 1=4), два принтера (E 2=2), три сканера (E 3=3) и один привод оптических дисков (E 4=1): E =(4, 2, 3, 1). В определенный момент времени процесс P 1 использует один сканер (C 13=1), процесс P 2 – два накопителя на гибких дисках (C 21=2) и единственный привод оптических дисков (C 24=1), процесс P 3 использует один принтер (C 32=1) и

два сканера (C 33=2):

é0

C = ê2

êë0

Ugrave;

Uacute;

1 2 0úû

Согласно формуле (2), рассчитаем значения вектора свободных ресурсов:

Aj = Ej -å Cij, A =(2, 1, 0, 0).

i =1

Кроме того, для завершения работы каждому процессу требуется еще не- которое количество некоторых ресурсов:

é2

R = ê1

êë2

Ugrave;

0 1 ú.

1 0 0úû

Для нормального продолжения работы каждого процесса следует предо- ставить ему все требуемые ресурсы (не смотря на уже занятые). По окончании работы процесс высвободит все используемые ресурсы.

В нашем случае процессы P 1 и P 2 запрашивают ресурсы, свободных экзем- пляров которых в системе нет. Если операционная система предоставит все тре- буемые ресурсы процессу P 3, то по окончании его работы, за счет высвободив- шихся ресурсов ситуация будет выглядеть следующим образом:

é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úû

Теперь можно предоставить требуемые ресурсы процессу P 2, а по оконча- нии его работы – процессу P 1.

Так как существует последовательность предоставления ресурсов всем

процессам, приводящая к нормальному завершению всех процессов, то система не находится в состоянии взаимоблокировки.

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) данные.

2,0	+	0,9	+	0,8	+	0,3						= 4,0 мин
		0,9	+	0,8	+	0,3	+	0,9	+	,1		= 3,0 мин

				0,8	+	0,3	+	0,9				= 2,0 мин
						0,3	+	0,9	+	,1	+ 0,7	= 2,0 мин

A B C D

0 10 15 20 22 31,7 t,мин

Задача	Время запуска	Требуемое коли- чество минут ра- боты процессора
A	0:00
B	0:10
C	0:15
D	0:20

Рисунок 3 – Диаграмма работы параллельных процессов Таблица 3– Расписание запуска процессов

Таблица 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 с.