Лекции.Орг


Поиск:




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

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

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

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

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

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

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

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

 

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

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

Пусть т – это число классов ресурсов, причем в системе 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

ê

CC 21


C 12

C 22


...

...


C 1 m ù

C
ú

2 m ú


ê...

ê


...


...


... ú

ú


ë Cn 1


Cn 2


...


Cnm û


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


é R 11

ê

R =ê R 21


R 12 R 22


...

...


R 1 m ù

R
ú

2 m ú


ê...

ê


...


...


... ú

ú


ë Rn 1


Rn 2


...


Rnm û


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

n


å 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), рассчитаем значения вектора свободных ресурсов:

n

Aj = EjCij, 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


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

 



<== предыдущая лекция | следующая лекция ==>
Местное самоуправление — форма народовластия | прохождения производственной практики
Поделиться с друзьями:


Дата добавления: 2017-03-12; Мы поможем в написании ваших работ!; просмотров: 568 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Студенческая общага - это место, где меня научили готовить 20 блюд из макарон и 40 из доширака. А майонез - это вообще десерт. © Неизвестно
==> читать все изречения...

962 - | 917 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.