Раздел 2 Процессы и потоки
Лекция №4
Функции ОС по управлению процессами и потоками:
Преимущества использования потоков:
Задания и волокна
Состояния потоков
Создание процессов
Создать процесс означает:
Идентификаторы, дескрипторы и контекст
Уничтожение процессов
Планирование и диспетчеризация потоков
Диспетчеризация
Моменты перепланировки
Лекция № 5
Планирование процессов
Алгоритмы планирования, основанные на квантовании
Алгоритмы планирования, основанные на приоритетах
Смешанный алгоритм планирования
Схема назначения приоритета потокам в Windows NT
Классы приоритетов процессов и приоритеты потоков Win32
Алгоритм планирования Linux
Очередь исполнения и массивы приоритетов в Linux
Алгоритмы планирования в ОС пакетной обработки информации
Планирование в интерактивных системах
4.Гарантированное планирование
5. Лотерейное планирование
6. Справедливое планирование
Планирование в системах реального времени
Алгоритм Лью - Лейланда
Лекция № 6
Межпроцессное взаимодействие
Гонки (взаимные состязания)
Способы реализации взаимного исключения
Семафоры Дейкстры
Решение классической задачи синхронизации «читатели – писатели» с помощью семафоров
Проблема обедающих философов
Официант
Иерархия ресурсов
Проблема спящего брадобрея
Проблема
Решение
Взаимные блокировки (тупики, клинчи, дедлоки)
Условия взаимоблокировки:
Моделирование взаимоблокировок
Стратегии при столкновении с взаимными блокировками
Обнаружение и устранение взаимоблокировок 1. Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
2. Обнаружение взаимоблокировки при наличии нескольких ресурсов каждого типа
Выход из взаимной блокировки
Динамическое избежание взаимоблокировок Траектории ресурсов
Опасные и безопасные состояния
Алгоритм банкира для одного вида ресурсов
Алгоритм банкира для несколько видов ресурсов
 Предотвращение условий, необходимых для взаимоблокировок
Системные средства синхронизации
Сигнал
Мониторы Хоара
Ждущие таймеры
Обмен данными между процессами и потоками
Каналы
2.42M
Category: programmingprogramming

Процессы и потоки

1. Раздел 2 Процессы и потоки

2. Лекция №4

Процессы и потоки

3. Функции ОС по управлению процессами и потоками:

1
• планирование процессов, т.е. распределение
процессорного времени между несколькими
одновременно выполняющимися в системе процессами
2
• создание и уничтожение процессов
3
• наделение процессов необходимыми системными
ресурсами
4
• реализация обмена данными между процессами;
5
• синхронизация процессов и потоков

4.

Процесс
- программа, находящаяся в стадии выполнения.
Потоки
возникли как средство распараллеливания вычислений в
рамках одного процесса.
Процесс рассматривается как заявка на
потребление всех видов ресурсов, кроме
одного – процессорного времени.
Процессорное время выделяется потокам.
В простейшем случае процесс состоит из
одного потока.

5.

6. Преимущества использования потоков:

+
• Создание потоков требует от ОС меньших
накладных расходов, чем при создании процессов
+
• Быстрота создания потока по сравнению с
процессом
+
• Потоки одного процесса могут взаимодействовать
не обращаясь к ОС, а используя общую память
+
• Повышение производительности программы

7. Задания и волокна

8. Состояния потоков

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

9.

Граф состояний потока
1. Поток выбран на выполнение
2. Поток ожидает завершения ввода/вывода
3. Ввод/вывод завершен (событие произошло)
4. Поток вытеснен планировщиком

10. Создание процессов

События, приводящие к созданию
процессов:
загрузка системы
работающий
процесс подает
системный вызов
на создание
процесса
запрос
пользователя на
создание процесса

11. Создать процесс означает:

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

12. Идентификаторы, дескрипторы и контекст

• Дескриптор процесса содержит такую информацию о процессе, которая необходима
ядру в течение всего жизненного цикла процесса независимо от того, находится он в
активном или пассивном состоянии. В дескрипторе прямо или косвенно содержится
информация о состоянии процесса, о расположении образа процесса в оперативной
памяти и на диске, о значении отдельных составляющих приоритета, глобальном
приоритете, об идентификаторе пользователя, создавшего процесс, о родственных
процессах и некоторая др. информация.
• Контекст процесса содержит менее оперативную, но более объемную часть
информации о процессе, необходимую для возобновления выполнения процесса с
прерванного места: содержимое регистров процессора, коды ошибок выполняемых
процессором системных вызовов, таблица открытых файлов, информация о
незавершенных операциях ввода/вывода и др.

13.

Структура сегмента TSS

14. Уничтожение процессов

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

15. Планирование и диспетчеризация потоков

Планирование
динамическое
(решения
принимаются во
время работы системы на
основе анализа текущей
ситуации)
статическое
(решения приняты заранее,
работа по расписанию)

16.

Диспетчеризация
это реализация найденного в результате планирования
решения, т.е.:
1
2
3
• сохранение контекста текущего потока
• загрузка контекста потока, выбранного
в результате планирования
• запуск нового потока на выполнение

17. Диспетчеризация

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

18. Моменты перепланировки

Планирование процессов
Алгоритмы планирования
невытесняющие
вытесняющие
активный поток выполняется до тех пор,
пока он сам, по собственной инициативе,
не отдаст управление ОС для того,
чтобы та выбрала из очереди другой
готовый к выполнению поток
решение о переключении
процессора с выполнения одного
потока на выполнение другого
потока принимается ОС, а не
активной задачей

19. Лекция № 5

Алгоритмы планирования, основанные
на квантовании
Квант – ограниченный непрерывный интервал
процессорного времени, который поочередно
предоставляется всем существующим в системе потокам.

20. Планирование процессов

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

21. Алгоритмы планирования, основанные на квантовании

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

22. Алгоритмы планирования, основанные на приоритетах

Смешанный алгоритм
планирования
Квантование +приоритеты

23.

Схема назначения приоритета
потокам в Windows NT
Уровни приоритета потоков.

24. Смешанный алгоритм планирования

Классы приоритетов процессов и приоритеты
потоков Win32

25. Схема назначения приоритета потокам в Windows NT

26. Классы приоритетов процессов и приоритеты потоков Win32

Алгоритм планирования Linux
В операционной системе Linux поддерживаются три класса потоков:
1. потоки реального времени, обслуживаемые по алгоритму FIFO;
2. потоки реального времени, обслуживаемые в порядке циклической
очереди;
• 3. потоки разделения времени.
Linux различает 140 уровней приоритета.
Потоки реального времени имеют приоритеты от 0 до 99, причем 0 –
самый высокий приоритет.
Обычному потоку ставится в соответствие уровень приоритета от 100 до
139.
Каждому уровню приоритета обычных потоков соответствует свое
значение длительности кванта времени.
Linux связывает с каждым потоком значение nice, которое определяет
статический приоритет каждого потока. По умолчанию он равен 0, но его
можно изменить при помощи системного вызова nice(value), где value
меняется от -20 до +19.

27.

Очередь исполнения и массивы приоритетов в Linux

28. Алгоритм планирования Linux

Алгоритмы планирования в ОС пакетной
обработки информации
1. "Первый пришел - первым обслужен" (FIFO)
+ Достоинства:
- простота;
- справедливость.
2. "Кратчайшая задача – первая»
Минимизирует среднее
оборотное время выполнения
задачи.
Оборотное время – время,
прошедшее от момента запуска
всего пакета на выполнение до
получения результата задачи.

29. Очередь исполнения и массивы приоритетов в Linux

Суть алгоритма: первой на выполнение запускается
самая короткая задача из пакета.
Задачи:
Время выполнения:
A
8 мин.
B
C
4 мин.
D
4 мин.
4 мин.

30. Алгоритмы планирования в ОС пакетной обработки информации

Достоинства:
Недостатки:
уменьшение оборотного
времени
справедливость
требуется превентивная
информация о времени
выполнения задач
длинный процесс, занявший
процессор, не пустит более новые
краткие процессы, которые пришли
позже.

31.

3. Наименьшее оставшееся время
выполнения
4. Трехуровневое планирование

32.

Планирование в интерактивных системах
Критерий
эффективности
пользователя.

удобство
работы
1. Циклическое планирование (квантование)
простота;
справедливость.
- слишком
малый квант
времени приводит к
частому переключению
процессов и снижению
производительности;
- слишком большой квант
может привести к
увеличению времени ответа
на интерактивный запрос.

33.

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

34. Планирование в интерактивных системах

3. Самый короткий процесс - следующий
4.Гарантированное планирование
Если в процессе работы в системе зарегистрировано n пользователей, то
вы получите 1/n от мощности центрального процессора. Аналогично
этому, в однопользовательской системе, имеющей n работающих
процессов, при прочих равных условиях каждый из них получит 1/п от
общего числа процессорных циклов.
Суть алгоритма
Необходимо отслеживать, сколько процессорного времени затрачено
на каждый процесс с момента его создания. Затем вычисляют
отношение времени, фактически полученного процессом к количеству
времени, на которое он имел право.
На выполнение выбирается процесс с наименьшим отношением,
который будет работать до тех пор, пока его соотношение не превысит
соотношение его ближайшего конкурента.

35.

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

36. 4.Гарантированное планирование

6. Справедливое планирование
Некоторые системы перед
планированием работы процесса берут
в расчет, кто является его владельцем. В
этой модели каждому пользователю
распределяется некоторая доля
процессорного времени и планировщик
выбирает процессы, соблюдая это
распределение. Таким образом, если
каждому из двух пользователей было
обещано по 50% процессорного
времени, то они его получат, независимо
от количества имеющихся у них
процессов.

37. 5. Лотерейное планирование

Планирование в системах реального времени
Критерий эффективности – способность системы
выдерживать заранее заданные интервалы времени
между запуском программы и получением результата
(реактивность системы).
Системы реального времени
жесткие
гибкие
несоблюдение временных
ограничений приводит к
катастрофическим последствиям
нарушения временного
графика нежелательны, но
допустимы

38. 6. Справедливое планирование

Внешние события
периодические – начиная с
момента первоначального запроса
все будущие моменты
возникновения задачи можно
определить заранее
спорадические - моменты
возникновения запросов
заранее неизвестны
Задачи
независимые
взаимосвязанные

39. Планирование в системах реального времени

Ti
pi
di
сi
- периодический набор задач
- периоды
- предельные сроки
- требования к времени выполнения
μ – коэффициент использования процессора
μi = с i / p i
Необходимое условие существования расписания:
μ =∑ сi / pi ≤ k,
где k - количество доступных процессоров.

40.

Алгоритм Лью - Лейланда
Классический алгоритм для жестких систем реального времени с одним процессором.
Алгоритм основан на следующих предположениях:
Запросы на выполнение всех задач набора, имеющих жесткие ограничения на время
реакции, являются периодическими.
Все задачи независимы.
Срок выполнения задачи равен ее периоду.
Максимальное время выполнения каждой задачи сi известно и постоянно.
Время переключения контекста можно игнорировать.
Максимальный суммарный коэффициент загрузки процессора ∑ сi / pi ≤ n(21/n -1), где n –
число задач.
Суть алгоритма: задача с самым коротким периодом получает
наивысший приоритет, задача с наибольшим периодом получает
наименьший приоритет.

41.

Лекция № 6
Синхронизация процессов и
потоков

42. Алгоритм Лью - Лейланда

Межпроцессное взаимодействие
согласование действий процессов
передача информации от одного процесса
другому
контроль над деятельностью процессов

43. Лекция № 6

Потребность в синхронизации
потоков возникает только в
мультипрограммной
операционной системе и связана с
совместным использованием
аппаратных и информационных
ресурсов вычислительной системы

44. Межпроцессное взаимодействие

Гонки (взаимные состязания)
Состязания (гонки)– ситуация, когда два или более потока обрабатывают разделяемые
данные и конечный результат зависит от соотношения скоростей потоков.
А
Б
В

45.

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

46. Гонки (взаимные состязания)

Способы реализации взаимного исключения
1. Запрет прерываний
2. Блокирующие переменные

47.

48. Способы реализации взаимного исключения

Семафоры Дейкстры
Семафоры – переменные, которые могут принимать целые
неотрицательные значения и используются для
синхронизации вычислительных процессов.
Для работы с семафорами определены два примитива:
V-операция (от голландского Verhogen – увеличить):
V(S): S=S+1 единым действием;
Р-операция (от голландского Proberen – проверить)
P(S): S=S-1 , если возможно; если это невозможно, то поток,
вызвавший P(S) переводится в состояние ожидания.

49.

Решение классической задачи синхронизации
«читатели – писатели» с помощью семафоров
буферный пул состоит из N буферов
e - число пустых буферов и f - число заполненных буферов

50. Семафоры Дейкстры

Проблема обедающих философов
Каждый философ может либо есть, либо
размышлять.
Подразумевается бесконечный запас спагетти.
Философ может есть только тогда, когда
держит две вилки — взятую справа и слева.
Каждый философ может взять ближайшую
вилку (если она доступна), или положить —
если он уже держит её. Взятие каждой вилки и
возвращение её на стол являются
раздельными действиями, которые должны
выполняться одно за другим.
Проблемы:
взаимная блокировка
ресурсное голодание
Необходимо разработать модель поведения, при котором ни один
из философов не будет голодать, то есть будет вечно чередовать
приём пищи и размышления.

51. Решение классической задачи синхронизации «читатели – писатели» с помощью семафоров

Официант
Добавим официанта возле стола. Философы должны дожидаться
разрешения официанта перед тем, как взять вилку. Поскольку официант
знает, сколько вилок используется в данный момент, он может принимать
решения относительно распределения вилок и тем самым предотвратить
взаимную блокировку философов. Если четыре вилки из пяти уже
используются, то следующий философ, запросивший вилку, вынужден будет
ждать разрешения официанта — которое не будет получено, пока вилка не
будет освобождена. Предполагается, что философ всегда пытается сначала
взять левую вилку, а потом — правую (или наоборот), что упрощает логику.
Чтобы показать, как это решение работает, предположим, что философы
обозначены от А до Д по часовой стрелке. Если философы А и В едят, то
заняты четыре вилки. Философ Б сидит между А и В, так что ему недоступна
ни одна из вилок. В то же время, философы Г и Д имеют доступ к одной
неиспользуемой вилке между ними. Предположим, что философ Г хочет
есть. Если он тут же берёт свободную вилку, то становится возможна
взаимная блокировка философов. Если вместо этого он спрашивает
разрешения у официанта, то тот просит его подождать — и можно быть
уверенным в том, что как только пара вилок освободится, то по крайней
мере один философ сможет взять две вилки. Таким образом, взаимная
блокировка становится невозможной.

52. Проблема обедающих философов

Иерархия ресурсов
Присвоим частичный порядок ресурсам и установим соглашение, что ресурсы
запрашиваются в указанном порядке, а возвращаются в обратном порядке. Пусть
ресурсы (вилки) будут пронумерованы от 1 до 5, и каждая рабочая единица
(философ) всегда берёт сначала вилку с наименьшим номером, а потом вилку с
наибольшим номером из двух доступных. Далее, философ кладёт сначала вилку
с бо́льшим номером, потом — с меньшим. В этом случае, если четыре из пяти
философов одновременно возьмут вилку с наименьшим номером, на столе
останется вилка с наибольшим возможным номером. Таким образом, пятый
философ не сможет взять ни одной вилки. Более того, только один философ
будет иметь доступ к вилке с наибольшим номером, так что он сможет есть двумя
вилками. Когда он закончит использовать вилки, он в первую очередь положит на
стол вилку с бо́льшим номером, потом — с меньшим, тем самым позволив
другому философу взять недостающую вилку и приступить к еде.
В то время, как иерархия ресурсов позволяет избежать взаимных блокировок,
данное решение не всегда является практичным, в особенности когда список
необходимых ресурсов неизвестен заранее. Например, если рабочая единица
удерживает ресурс 3 и 5 и решает, что ей необходим ресурс 2, то она должна
выпустить ресурс 5, затем 3, после этого завладеть ресурсом 2 и снова взять
ресурс 3 и 5.

53. Официант

Проблема спящего брадобрея

54. Иерархия ресурсов

Проблема
связана с тем фактом, что действия и парикмахера, и клиента
(проверка приёмной, вход в парикмахерскую, занятие места в
приёмной, и т. д.) занимают неизвестное количество времени и/или
могут происходить одновременно. Например, клиент может войти и
заметить, что парикмахер работает, тогда он идет в приёмную. Пока он
идет, парикмахер заканчивает стрижку, которую он делает и идет, чтобы
проверить приемную, причём делает это быстрее направляющегося
туда клиента. Так как в приёмной пока ещё никого нет (клиент ещё не
дошел), он возвращается к своему месту и спит. Парикмахер теперь
ждет клиента, а клиент ждет парикмахера. В другом примере два
клиента могут прибыть в то же самое время, когда в приемной есть
единственное свободное место. Они замечают, что парикмахер
работает, идут в приёмную, и оба пытаются занять единственный стул.

55. Проблема спящего брадобрея

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

56. Проблема

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

57. Решение

58. Взаимные блокировки (тупики, клинчи, дедлоки)

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

59.

60. Условия взаимоблокировки:

Моделирование взаимоблокировок

61.

процессы A, B, C
ресурсы R, S, T
А
Запросить R
Запросить S
Освободить R
Освободить S
B
Запросить S
Запросить T
Освободить S
Освободить T
C
Запросить T
Запросить R
Освободить T
Освободить R

62. Моделирование взаимоблокировок

63.

Стратегии при столкновении с взаимными
блокировками
1
2
3
4
• Пренебрежением проблемой в целом (страусовый
алгоритм)
• Обнаружение и восстановление
• Динамическое избежание тупиков
• Предотвращение с помощью опровержения хотя бы одного
условия, необходимого для возникновения тупика

64.

Обнаружение и устранение
взаимоблокировок
.
1 Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
Для каждого узла N в графе
выполняются следующие 5 шагов

65. Стратегии при столкновении с взаимными блокировками

2. Обнаружение взаимоблокировки при наличии
нескольких ресурсов каждого типа
m - число классов ресурсов
n - количество процессов, P1… Pn
E = (Е1, Е2, Е3 , …, Еm ) - вектор существующих ресурсов, где
Ei - количество ресурсов класса i,
• A = (A1, A2, A3 , …, Am ) - вектор доступных ресурсов,
Ai - количество доступных ресурсов класса i,
• С - матрица текущего распределения
R - матрица запросов

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

А= (2 2 2 0)
А= (4 2 2 1)

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

Когда следует искать тупики:
• Когда запрашивается очередной ресурс
• Периодически, через какой-то
определенный промежуток времени
• Когда загрузка процессора слишком
мала

68.

Выход из взаимной блокировки
1
2
3
• Восстановление при помощи
принудительной выгрузки ресурса
• Восстановление через откат
• Восстановление путем уничтожения
процесса

69.

Динамическое избежание
взаимоблокировок
Траектории ресурсов
А1 - запрос принтера процессом А,
А2 - запрос плоттера процессом А,
А3 - освобождение принтера процессом А,
А4 - освобождение плоттера процессом А
В1 - запрос плоттера процессом В,
В2 - запрос принтера процессом В,
В3 - освобождение плоттера процессом В,
В4 - освобождение принтера процессом В.

70. Выход из взаимной блокировки

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

71. Динамическое избежание взаимоблокировок Траектории ресурсов

Алгоритм банкира для одного вида ресурсов

72. Опасные и безопасные состояния

Алгоритм банкира для несколько видов
ресурсов
E=(6342) - существующие ресурсы,
P=(5322) - занятые ресурсы,
A=(1020) - доступные ресурсы

73. Алгоритм банкира для одного вида ресурсов

Предотвращение условий, необходимых для
взаимоблокировок
Взаимное
исключение
Удержание и
ожидание
Отсутствие
принудительной
выгрузки ресурса
Циклическое
ожидание
организовать
подкачку данных
запрашивать все
ресурсы на
начальной стадии
отбирать ресурсы
пронумеровать
ресурсы и
упорядочить

74. Алгоритм банкира для несколько видов ресурсов

Системные средства синхронизации
Системные семафоры;
мьютексы;
события;
таймеры;
файлы, процессы, потоки…
объекты ядра
ОС
Wait ( )
Set ( )
Windows NT
WaitForSingleObjekt ( )
WaitForMultipleObjekt ( )
SetEvent ( )
UNIX
sleep ( )
wakeup ( )
OS/2
DosSemWait ( )
DosSemSet ( )

75.  Предотвращение условий, необходимых для взаимоблокировок

• Мьютексы (от MUTual Exclusion взаимоисключения) – объекты ядра,
позволяют координировать взаимное
исключение доступа к разделяемому
ресурсу.
• Системные семафоры - принцип
действия мьютексов, но в них заложена
возможность подсчета ресурсов, что
позволяет заранее определенному числу
потоков одновременно войти в
синхронизуемый участок кода.

76. Системные средства синхронизации

События используются в качестве
сигналов о завершении какой-либо
операции.
События
с ручным сбросом
с автоматическим сбросом
(все потоки,ожидающие
наступления события, переходят
в состояние «готовность»
(как и в случае мьютекса, в
состояние «готовность»
переводится только один поток

77.

Сигнал
или виртуальное прерывание является сообщением,
которое система посылает процессу или один процесс
посылает другому.

78.

Мониторы Хоара
Монитор – это пассивный набор
разделяемых переменных и повторно
входимых процедур доступа к ним,
которыми процессы пользуются в
режиме разделения, причем в
каждый момент времени им может
пользоваться только один процесс.

79. Сигнал

Ждущие таймеры
Режим «ручного сброса»
таймер переходит в установленное состояние при
истечении заданной задержки и остается
установленным до тех пор, пока функция
SetWaitableTimer не задаст новую задержку
Ждущий
таймер
Режим «автоматического сброса»
таймер переходит в установленное состояние при
истечении заданной задержки и остается
установленным до первого успешного вызова
функции ожидания. Каждый раз при истечении
времени задержки разрешается выполнение лишь
одной нити
Режим интервального таймера, который
перезапускается с заданной задержкой после
каждого срабатывания объекта

80. Мониторы Хоара

Обмен данными между процессами и потоками
Конвейер (канал, pipe) – представляет собой буфер в оперативной
памяти, поддерживающий очередь байт по алгоритму FIFO.

81. Ждущие таймеры

Каналы
Каналы
Безымянные
каналы
позволяют обмениваться
данными только
родственным процессам
Именованные каналы
имеют имя, которое
является записью в каталоге
файловой системы ОС,
поэтому пригодны для
обмена данными между
двумя произвольными
процессами или потоками
этих процессов.

82. Обмен данными между процессами и потоками

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

83. Каналы

Сокеты

84.

Разделяемая память
Виртуальное
адресное
пространство
процесса 1
Виртуальное адресное
пространство
процесса 1
Виртуальное
адресное
пространство
процесса 2
Физическая
память
Физическая
память
Совместно
используе
мая
физическая
память
Виртуальное адресное
пространство
процесса 2
Файл
подкачки
загрузочный
модуль или
файл
данных
Совместно
используе
мая
физическа
я память
English     Русский Rules