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

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

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

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

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

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

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

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

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

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

ati ? 1

i=1 Ti

(1).

Системы реального времени, удовлетворяющие этому условию, называют- ся поддающимися планированию пли планируемыми.

Пример: рассмотрим гибкую систему реального времени с тремя периоди- ческими сигналами с периодами в 100, 200 и 500 мс соответственно. Если на об- работку этих сигналов уходит 50, 30 и 100 мс соответственно, система является поддающейся планированию, поскольку 0,5 + 0,15 + 0,21. Даже при добавле- нии четвертого сигнала с периодом в 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:

eC11

e

C =eC21

C12

C22

…

…

C1m u

C

u

2m u

e…

e

…

…

… u

u

eCn1

Cn2

…

Cnm u

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

eR11

e

R =eR21

R12 R22

…

…

R1m u

R

u

2m u

e…

e

…

…

… u

u

eRn1

Rn2

…

Rnm u

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

n

aCij+ 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):

e0

e

C = e2

ee0

Ugrave;

.

u

Uacute;

1 2 0uu

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

n

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

i =1

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

e2

e

R = e1

ee2

Ugrave;

u

0 1 u.

1 0 0uu

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

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

e0 0 1 0u

e u

e2 0

e

Ugrave;

u

C = e2 0

0 1u, R = e1 0 1

0u, A=(2, 2, 2, 0).

ee0 0 0

0uu

ee0

0 0 0uu

Теперь можно предоставить требуемые ресурсы процессу 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) данные.

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 с.

Статьи к прочтению:

23. Причины возникновения взаимоблокировок.


Похожие статьи: