- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Взаимодействие процессов презентация
Содержание
- 1. Взаимодействие процессов
- 2. Общие сведения Нормальное функционирование процессов мультипрограммной ОС
- 3. Особенности взаимодействия Взаимодействие процессов может заранее планироваться
- 4. Причины взаимодействия Взаимодействие процессов обычно организуется
- 5. Обмен данными Взаимодействие процессов организуется с
- 6. Организация обмена данными
- 7. Средства обмена данными Порядок организации обмена данными
- 8. Категории средств обмена В большинстве современных операционных
- 9. Разделяемая память Под разделяемой памятью подразумевается область
- 10. Каналы связи Под каналом связи обычно подразумевают
- 11. Сообщения Сообщением называется структурированная порция данных, передаваемая
- 12. Сигналы Механизм сигналов предназначен для передачи информации
- 13. Порядок обмена данными Обмен данными между
- 14. Начало обмена Последовательность действий, которую необходимо выполнить
- 15. Инициализация обмена Под инициализацией обмена подразумевается некоторая
- 16. Прямая адресация При прямой адресации взаимодействующие процессы
- 17. Непрямая адресация Непрямой (косвенной) адресацией называется схема
- 18. Порядок обмена Порядок обмена, т.е. последовательность действий,
- 19. Информационная валентность Информационная валентность определяет число процессов,
- 20. Направленность Направленность определяет возможность передачи данных в
- 21. Порядок завершения связи Порядок завершения связи
- 22. Передача информации с помощью каналов связи
- 23. Модели передачи данных Для передачи данных по
- 24. Модель потока ввода-вывода С точки зрения ОС
- 25. Модель сообщений Операционная система полностью контролирует процесс
- 26. Буферизация Под буферизацией обычно понимают способность
- 27. Надежность линий связи Средство связи считается
- 28. Протокол связи При низкой надежности средства связи
- 29. Организация взаимодействия процессов в UNIX
- 30. Общие сведения Практически во все современные
- 31. Общие свойства механизмов IPC Несмотря на то,
- 32. Идентификация экземпляров средства связи Идентификация экземпляров средства
- 33. Работа с разделяемой памятью Работа разделяемой
- 34. Работа с разделяемой памятью Системный вызов
- 35. Сообщения Механизм сообщений обеспечивает обмен структурированными порциями
- 36. Очередь сообщений Каждая очередь сообщений имеет заголовок,
- 37. Системные вызовы для работы с сообщениями msgget(id, flag)
- 38. msgrcv(msqid, msg,count, type, flag) – извлечение процессом сообщения (получение
- 39. Сигналы Основным назначением механизма сигналов в
- 40. Обработка сигналов Посылка сигнала процессу выполняется путем
- 41. Системные вызовы для работы с сигналами Системные
- 42. Каналы Каналы являются наиболее употребительным средством связи
- 43. Неименованные каналы Для связи родственных процессов, обычно
- 44. Именованные каналы В тех случаях, когда процессы
- 45. Чтение и запись данных Чтение из канала
- 46. Семафоры Семафоры являются средством, позволяющим выполнить
- 47. Системные вызовы для работы с семафорами semget(id,count,flag)
- 48. Операции над семафорами Над семафорами допускаются
- 49. Конфликты и состояния состязания
- 50. Общие сведения Конфликтные ситуации при работе процессов
- 51. Пример конфликта В качестве примера рассмотрим упрощенную
- 52. Описание конфликта Пусть процессы A и B
- 53. Состояние состязания Конфликтом принято называть любое взаимодействие
- 54. Обработка состояния состязания Работа процессов с разделяемым
- 55. Взаимное исключение Взаимное исключение подразумевает, что некоторый
- 56. Критические области Параллельное выполнение процессов можно обеспечить,
- 57. Обработка критических областей Для корректной работы взаимодействующих
- 58. Условия корректности алгоритмов Условие асинхронного выполнения. В
- 59. Реализация взаимного исключения Для корректного решения задачи
- 60. Общая структура программы Общая структура участка программы,
- 61. Алгоритмы синхронизации процессов
- 62. Виды алгоритмов При организации межпроцессного взаимодействия используются
- 63. Запрет обработки прерываний Самое простое решение проблемы
- 64. Схема алгоритма
- 65. Взаимное исключение с активным ожиданием
- 66. Общие сведения В тех случаях, когда синхронизация
- 67. Алгоритмы с активным ожиданием Алгоритм с использованием
- 68. Алгоритм с использованием переменной блокировки Алгоритм
- 69. Схема алгоритма с использованием переменной блокировки
- 70. Комментарии Предположим, что некоторый процесс стремится попасть
- 71. Алгоритм с использованием указателя очередности Алгоритм
- 72. Схема алгоритма с использованием указателя очередности
- 73. Комментарии Предположим, что процесс 0 первым пытается
- 74. Алгоритм с использованием флагов готовности Недостаток
- 75. Схема
- 76. Комментарии Данный алгоритм обеспечивает взаимоисключение и позволяет
- 77. Алгоритм Петерсона Корректное решение проблемы организации
- 78. Схема алгоритма Петерсона
- 79. Комментарии. Условие взаимного исключения Выполнение условия
- 80. Комментарии. Условие взаимного исключения Если процессы
- 81. Комментарии. Условие прогресса Докажем выполнение условия
- 82. Комментарии. Условие ограниченного ожидания Докажем выполнение
- 83. Алгоритм «булочной» Алгоритм синхронизации для n
- 84. Описание реализации В программе используются два разделяемых
- 85. Схема алгоритма «булочной»
- 86. Комментарии Взаимное исключение обеспечивается за счет выполнения
- 87. Команда TS Наличие аппаратной поддержки взаимных
- 88. Описание реализации При использовании команды TS переменная
- 89. Схема пролога и эпилога
- 90. Комментарии Прежде чем попасть в критическую область,
- 91. Взаимное исключение с использованием примитивов взаимодействий
- 92. Недостатки алгоритмов с активным ожиданием Алгоритм Петерсона,
- 93. Общие сведения Для устранения проблем, возникающих в
- 94. Проблема производителя и потребителя Для демонстрации
- 95. Описание проблемы производителя и потребителя Если
- 96. Схема организации работы производителя и потребителя
- 97. Комментарии Не снижая общности применяемых методов решения
- 98. Семафоры. Определение Семафоры являются специализированным средством синхронизации
- 99. Общие сведения Переменные-семафоры могут быть применены для
- 100. Решение проблемы производителя и потребителя Для обмена
- 101. Схема решения
- 102. Комментарии В схеме решения задачи семафоры использовались
- 103. Мониторы. Определение Мониторами называются высокоуровневые средства синхронизации
- 104. Взаимное исключение и очередность При доступе к
- 105. Объявление монитора
- 106. Схема программы
- 107. Комментарии Взаимное исключение процессов обеспечивается выполнением требования,
- 108. Сообщения. Определение Под сообщением подразумевается порция
- 109. Общие сведения Сообщения могут применяться в качестве
- 110. Схема программы
- 111. Заключение Рассмотренные средства ОС позволяют выполнить
- 112. Взаимоблокировки
- 113. Разделяемые и закрепляемые ресурсы В зависимости от
- 114. Выгружаемые и невыгружаемые ресурсы Процессы во
- 115. Понятие взаимоблокировки Если ресурс недоступен, когда он
- 116. Условия взаимоблокировки Для возникновения ситуации взаимоблокировки
- 117. Моделирование взаимоблокировок Для моделирования взаимоблокировок, используются
- 118. Основные направления борьбы с тупиками Удовлетворительного
- 119. Страусовый алгоритм Самым простым подходом является страусовый
- 120. Обнаружение и устранение взаимоблокировок Решение проблемы
- 121. Выход из взаимоблокировки Восстановление при помощи принудительной
- 122. Исключение взаимоблокировок Основные алгоритмы, позволяющие динамически
- 123. Пример безопасного состояния Пусть в системе имеется
- 124. Пример небезопасного состояния Пусть в системе имеется
- 125. Алгоритм банкира Алгоритм планирования, позволяющий избегать
- 126. Нарушение условий возникновения взаимоблокировок Нарушение условия
- 127. Заключение Полное решение проблемы взаимоблокировок в ОС
Общие сведения Нормальное функционирование процессов мультипрограммной ОС возможно только при условии строгой изоляции выполняющихся программ друг от друга. Обособление программ обычно выполняется средствами ОС путем предотвращения взаимного доступа к областям памяти,
Слайд 2Общие сведения
Нормальное функционирование процессов мультипрограммной ОС возможно только при условии строгой
изоляции выполняющихся программ друг от друга.
Обособление программ обычно выполняется средствами ОС путем предотвращения взаимного доступа к областям памяти, выделенным для их работы.
Полная взаимная изоляция процессов невозможна, а при решении некоторых задач нецелесообразна, поэтому операционная система должна обладать средствами, позволяющими организовать их контролируемое взаимодействие.
Процессы называются взаимодействующими, если операции, выполняемые в рамках одних процессов, вызывают изменения в работе других процессов.
Взаимодействующие процессы могут исполняться псевдопараллельно на одном процессоре в рамках единой вычислительной системы или параллельно на разных процессорах, возможно входящих в состав разных вычислительных систем.
Обособление программ обычно выполняется средствами ОС путем предотвращения взаимного доступа к областям памяти, выделенным для их работы.
Полная взаимная изоляция процессов невозможна, а при решении некоторых задач нецелесообразна, поэтому операционная система должна обладать средствами, позволяющими организовать их контролируемое взаимодействие.
Процессы называются взаимодействующими, если операции, выполняемые в рамках одних процессов, вызывают изменения в работе других процессов.
Взаимодействующие процессы могут исполняться псевдопараллельно на одном процессоре в рамках единой вычислительной системы или параллельно на разных процессорах, возможно входящих в состав разных вычислительных систем.
Слайд 3Особенности взаимодействия
Взаимодействие процессов может заранее планироваться при разработке программ или возникать
случайно, например при одновременном обращении к ресурсам.
Под одновременным обращением к ресурсам подразумевается ситуация, в которой один из процессов в некоторый момент времени обращаться к ресурсу, еще используемому другим процессом.
В случае псевдопараллельного выполнения процессов в мультипрограммной системе ситуация одновременного обращения к ресурсам является следствием возможности приостановки выполнения любого процесса в произвольные моменты времени.
Если процесс, обратившийся к ресурсу, был приостановлен планировщиком из-за завершения кванта времени, не успев завершить работу с этим ресурсом, то вновь запущенный процесс также может обратиться к данному ресурсу.
Операция обращения к ресурсу не является атомарной.
Под одновременным обращением к ресурсам подразумевается ситуация, в которой один из процессов в некоторый момент времени обращаться к ресурсу, еще используемому другим процессом.
В случае псевдопараллельного выполнения процессов в мультипрограммной системе ситуация одновременного обращения к ресурсам является следствием возможности приостановки выполнения любого процесса в произвольные моменты времени.
Если процесс, обратившийся к ресурсу, был приостановлен планировщиком из-за завершения кванта времени, не успев завершить работу с этим ресурсом, то вновь запущенный процесс также может обратиться к данному ресурсу.
Операция обращения к ресурсу не является атомарной.
Слайд 4Причины взаимодействия
Взаимодействие процессов обычно организуется с целью улучшения характеристик работы
программной системы за счет частичной изоляции решения отдельных подзадач общей задачи.
К основным причинам и методам взаимодействия можно отнести:
Совместное использование данных. Различные процессы могут работать с едиными данными, используя их в произвольном порядке, например, с одной базой данных.
Передача данных. Данные последовательно передаются от одного процесса другому, что позволяет организовать их совместную работу. Примером может служить передача информации от текстового редактора в отладчик и обратно в интегрированной среде программирования.
Модульная организация программной системы. Если программная система состоит из совокупности автономных модулей и каждый модуль реализуется с помощью отдельного процесса, то согласованная работа системы обеспечивается путем обмена информацией между ее составляющими, обычно через специальный управляющий модуль. Примером может служить работа операционной системы с микроядром.
К основным причинам и методам взаимодействия можно отнести:
Совместное использование данных. Различные процессы могут работать с едиными данными, используя их в произвольном порядке, например, с одной базой данных.
Передача данных. Данные последовательно передаются от одного процесса другому, что позволяет организовать их совместную работу. Примером может служить передача информации от текстового редактора в отладчик и обратно в интегрированной среде программирования.
Модульная организация программной системы. Если программная система состоит из совокупности автономных модулей и каждый модуль реализуется с помощью отдельного процесса, то согласованная работа системы обеспечивается путем обмена информацией между ее составляющими, обычно через специальный управляющий модуль. Примером может служить работа операционной системы с микроядром.
Слайд 5Обмен данными
Взаимодействие процессов организуется с целью изменения поведения одного процесса
в ответ на операции, выполняемые другим процессом.
Обычно реализация взаимодействия подразумевает необходимость обмена информацией между процессами, что позволяет модифицировать их поведение на основе анализа принятых данных.
В связи с тем, что в мультипрограммной среде процессы обычно строго изолированы друг от друга, то для обеспечения корректного обмена данными требуются специальные средства и действия операционной системы.
Если деятельность процессов остается неизменной при любой принятой ими информации, то они не нуждаются во взаимодействии.
Таким образом организация обмена данными между процессами является основной проблемой, которую требуется решить для поддержки их взаимодействия.
Обычно реализация взаимодействия подразумевает необходимость обмена информацией между процессами, что позволяет модифицировать их поведение на основе анализа принятых данных.
В связи с тем, что в мультипрограммной среде процессы обычно строго изолированы друг от друга, то для обеспечения корректного обмена данными требуются специальные средства и действия операционной системы.
Если деятельность процессов остается неизменной при любой принятой ими информации, то они не нуждаются во взаимодействии.
Таким образом организация обмена данными между процессами является основной проблемой, которую требуется решить для поддержки их взаимодействия.
Слайд 7Средства обмена данными
Порядок организации обмена данными в значительной степени определяется особенностями
работы средств обмена данными, которые для этого используются.
Средства обмена различаются по следующим основным характеристикам:
порядок передачи данных (метод доступа к данным);
скорость и объем передаваемой информации;
надежности передачи данных.
Значения характеристик средств обмена обуславливают возможности их воздействия на поведение процессов.
Поскольку ОС обязана строго изолировать процессы друг от друга, то организация обмена данными всегда требует поддержки и контроля с ее стороны.
Конкретный набор средств, предоставляемых для решения задачи организации обмена, зависит от ее особенностей ОС.
Средства обмена выбираются программистом из числа поддерживаемых ОС с учетом специфики решаемых задач.
Средства обмена различаются по следующим основным характеристикам:
порядок передачи данных (метод доступа к данным);
скорость и объем передаваемой информации;
надежности передачи данных.
Значения характеристик средств обмена обуславливают возможности их воздействия на поведение процессов.
Поскольку ОС обязана строго изолировать процессы друг от друга, то организация обмена данными всегда требует поддержки и контроля с ее стороны.
Конкретный набор средств, предоставляемых для решения задачи организации обмена, зависит от ее особенностей ОС.
Средства обмена выбираются программистом из числа поддерживаемых ОС с учетом специфики решаемых задач.
Слайд 8Категории средств обмена
В большинстве современных операционных систем поддерживаются сходные средства обмена
данными, которые можно разделить на следующие основные категории:
разделяемая память;
каналы связи;
сообщения;
сигналы.
Средства обмена, принадлежащие одной категории, обладают сходными значениями характеристик вне зависимости от деталей их реализации в рамках конкретной операционной системы.
разделяемая память;
каналы связи;
сообщения;
сигналы.
Средства обмена, принадлежащие одной категории, обладают сходными значениями характеристик вне зависимости от деталей их реализации в рамках конкретной операционной системы.
Слайд 9Разделяемая память
Под разделяемой памятью подразумевается область основной памяти, которую операционная система
отображает в адресное пространство нескольких процессов.
Обработка данных, находящихся в разделяемой памяти, выполняется обычными средствами языков программирования, которые используются для работы с памятью.
Поддерживается произвольный порядок доступа к данным в режимах чтения и записи, что позволяет организовать обмен данными в двух направлениях.
Обеспечивается наивысшая скорость обмена данными и наибольшие объемы передачи данных.
Считается надежным средством передачи данных.
Разделяемую память могут использовать только процессы работающие в рамках одной вычислительной системы.
Обработка данных, находящихся в разделяемой памяти, выполняется обычными средствами языков программирования, которые используются для работы с памятью.
Поддерживается произвольный порядок доступа к данным в режимах чтения и записи, что позволяет организовать обмен данными в двух направлениях.
Обеспечивается наивысшая скорость обмена данными и наибольшие объемы передачи данных.
Считается надежным средством передачи данных.
Разделяемую память могут использовать только процессы работающие в рамках одной вычислительной системы.
Слайд 10Каналы связи
Под каналом связи обычно подразумевают линию связи, организованную для последовательной
передачи данных между процессами.
Управление работой каналов выполняется средствами операционной системы.
Передача или прием информации реализуется с помощью специальных системных вызовов, которые кроме собственно функции обмена поддерживают еще и функцию согласования работы процессов.
Канал обычно реализуется как однонаправленное средство связи, а объем и скорость передачи информации зависит от технических характеристик линии связи.
В рамках одной вычислительной системы для поддержки работы канала используется специальная область оперативной памяти (буфер). В этом случае канал считается надежным и быстрым средством обмена.
Если канал организован для связи между различными вычислительными системами, то его характеристики определяются качеством соответствующей линии связи.
Управление работой каналов выполняется средствами операционной системы.
Передача или прием информации реализуется с помощью специальных системных вызовов, которые кроме собственно функции обмена поддерживают еще и функцию согласования работы процессов.
Канал обычно реализуется как однонаправленное средство связи, а объем и скорость передачи информации зависит от технических характеристик линии связи.
В рамках одной вычислительной системы для поддержки работы канала используется специальная область оперативной памяти (буфер). В этом случае канал считается надежным и быстрым средством обмена.
Если канал организован для связи между различными вычислительными системами, то его характеристики определяются качеством соответствующей линии связи.
Слайд 11Сообщения
Сообщением называется структурированная порция данных, передаваемая от одного процесса другому за
один прием.
Обмен сообщениями между процессами поддерживается средствами операционной системы.
Для приема или передачи сообщений используются специальные системные вызовы, которые помимо обмена данными выполняют функцию согласования работы процессов.
Механизм сообщений может поддерживаться как в рамках одной вычислительной системы, так и в случае разных вычислительных систем.
Передача сообщений в рамках одной вычислительной системы реализуется на основе размещения в памяти структур данных, обеспечивающие временное хранение информации. В этом случае сообщения считаются надежным средством обмена.
Передача сообщений между разными вычислительными системами организуется на базе механизма каналов и имеет соответствующие характеристики.
Обмен сообщениями между процессами поддерживается средствами операционной системы.
Для приема или передачи сообщений используются специальные системные вызовы, которые помимо обмена данными выполняют функцию согласования работы процессов.
Механизм сообщений может поддерживаться как в рамках одной вычислительной системы, так и в случае разных вычислительных систем.
Передача сообщений в рамках одной вычислительной системы реализуется на основе размещения в памяти структур данных, обеспечивающие временное хранение информации. В этом случае сообщения считаются надежным средством обмена.
Передача сообщений между разными вычислительными системами организуется на базе механизма каналов и имеет соответствующие характеристики.
Слайд 12Сигналы
Механизм сигналов предназначен для передачи информации заинтересованному процессу от операционной системы
или другого процесса о наступлении некоторого события, произошедшего в вычислительной системе.
Операционная система преимущественно применяет сигналы для передачи процессу сведений об аппаратных прерываниях, имеющих к нему отношение.
Обычно сигнал обеспечивает передачу минимального объема данных (часто один бит).
Обмен сигналами поддерживается средствами операционной системы.
Для приема, передачи и организации обработки сигналов используются специальные системные вызовы.
Сигналы являются надежным средством обмена.
Операционная система преимущественно применяет сигналы для передачи процессу сведений об аппаратных прерываниях, имеющих к нему отношение.
Обычно сигнал обеспечивает передачу минимального объема данных (часто один бит).
Обмен сигналами поддерживается средствами операционной системы.
Для приема, передачи и организации обработки сигналов используются специальные системные вызовы.
Сигналы являются надежным средством обмена.
Слайд 13Порядок обмена данными
Обмен данными между несколькими процессами подразумевает необходимость выполнения
некоторой логической последовательности действий со стороны каждого из взаимодействующих процессов.
Конкретный набор действий определяется используемым механизмом обмена и в общем случае включает три этапа:
начало обмена;
собственно обмен данными;
завершение обмена.
Некоторые этапы являются общими для всех категорий средств обмена, в то время как другие этапы относятся только к отдельным категориям.
Конкретный набор действий определяется используемым механизмом обмена и в общем случае включает три этапа:
начало обмена;
собственно обмен данными;
завершение обмена.
Некоторые этапы являются общими для всех категорий средств обмена, в то время как другие этапы относятся только к отдельным категориям.
Слайд 14Начало обмена
Последовательность действий, которую необходимо выполнить для начала обмена, определяется двумя
взаимосвязанными особенностями, присущими некоторой категории средств обмена данными:
необходимостью выполнения процедуры инициализации обмена;
методами адресации средств связи, принадлежащих к данной категории.
необходимостью выполнения процедуры инициализации обмена;
методами адресации средств связи, принадлежащих к данной категории.
Слайд 15Инициализация обмена
Под инициализацией обмена подразумевается некоторая последовательность предварительных действий, выполнение которых
требуется для установления связи между процессами.
В большинстве ОС при использовании разделяемой памяти или канала связи требуется специальное обращение к операционной системе, позволяющее получить доступ к требуемой области памяти или линии связи.
Для передачи сигнала или сообщения от одного процесса к другому обычно не требуется никаких предварительных действий.
Часто необходимость инициализации обмена связана с методами адресации средств связи.
Под методом адресации средства связи подразумевается способ указания партнеров по взаимодействию процессами, которые используют данное средство.
Различаются два способа адресации:
прямая адресация;
непрямая адресация.
В большинстве ОС при использовании разделяемой памяти или канала связи требуется специальное обращение к операционной системе, позволяющее получить доступ к требуемой области памяти или линии связи.
Для передачи сигнала или сообщения от одного процесса к другому обычно не требуется никаких предварительных действий.
Часто необходимость инициализации обмена связана с методами адресации средств связи.
Под методом адресации средства связи подразумевается способ указания партнеров по взаимодействию процессами, которые используют данное средство.
Различаются два способа адресации:
прямая адресация;
непрямая адресация.
Слайд 16Прямая адресация
При прямой адресации взаимодействующие процессы при каждой операции обмена данными
должны явно указывать идентификатор, позволяющий определить процесс, которому информация предназначена или от которого она должна быть получена.
В зависимости от решаемой задачи прямая адресация реализуется в соответствии с одной из следующих схем:
симметричная прямая адресация – оба процесса, передающий и принимающий, задают имена партнеров, что делает невозможным несанкционированное включение в обмен третьего процесса;
асимметричная прямая адресация – один из взаимодействующих процессов указывает идентификатор своего партнера, а второй в качестве возможного партнера рассматривает любой процесс в системе.
При использовании прямой адресации связь между процессами в классической операционной системе устанавливается автоматически, без дополнительных инициализирующих действий и требует знания идентификаторов процессов, участвующих в обмене данными.
В зависимости от решаемой задачи прямая адресация реализуется в соответствии с одной из следующих схем:
симметричная прямая адресация – оба процесса, передающий и принимающий, задают имена партнеров, что делает невозможным несанкционированное включение в обмен третьего процесса;
асимметричная прямая адресация – один из взаимодействующих процессов указывает идентификатор своего партнера, а второй в качестве возможного партнера рассматривает любой процесс в системе.
При использовании прямой адресации связь между процессами в классической операционной системе устанавливается автоматически, без дополнительных инициализирующих действий и требует знания идентификаторов процессов, участвующих в обмене данными.
Слайд 17Непрямая адресация
Непрямой (косвенной) адресацией называется схема адресации в которой при обмене
информацией взаимодействующие процессы используют некоторый промежуточный объект, предназначенный для хранения данных.
При непрямой адресации передающий процесс указывает этого промежуточного объекта, в который и помещаются данные.
Промежуточный объект хранит данные до тех пор, пока они не будут изъяты каким-либо принимающим процессом, указавшим его адрес.
При непрямой адресации передающему и принимающему процессам не требуется сведений об идентификаторе партнера, а нужен только идентификатор промежуточного объекта, если он не является единственным и неповторимым в вычислительной системе для всех процессов.
При использовании непрямой адресации обычно требуется инициализация средства связи, связанная с необходимостью организации промежуточного объекта.
При непрямой адресации передающий процесс указывает этого промежуточного объекта, в который и помещаются данные.
Промежуточный объект хранит данные до тех пор, пока они не будут изъяты каким-либо принимающим процессом, указавшим его адрес.
При непрямой адресации передающему и принимающему процессам не требуется сведений об идентификаторе партнера, а нужен только идентификатор промежуточного объекта, если он не является единственным и неповторимым в вычислительной системе для всех процессов.
При использовании непрямой адресации обычно требуется инициализация средства связи, связанная с необходимостью организации промежуточного объекта.
Слайд 18Порядок обмена
Порядок обмена, т.е. последовательность действий, которую следует выполнить для корректной
передачи или приема данных, в основном определяется следующими характеристиками средств связи:
информационная валентность;
направленность.
информационная валентность;
направленность.
Слайд 19Информационная валентность
Информационная валентность определяет число процессов, которые могут быть одновременно ассоциированы
с конкретным средством связи, а также число одинаковых средств связи, которые могут быть задействованы для организации взаимодействия двух процессов.
При прямой адресации только одно заданное средство связи может быть задействовано для обмена данными между двумя процессами, и только эти два процесса могут быть ассоциированы с ним.
При непрямой адресации может существовать более двух процессов, использующих один и тот же объект для промежуточного хранения данных, и более одного объекта могут использоваться двумя процессами.
При прямой адресации только одно заданное средство связи может быть задействовано для обмена данными между двумя процессами, и только эти два процесса могут быть ассоциированы с ним.
При непрямой адресации может существовать более двух процессов, использующих один и тот же объект для промежуточного хранения данных, и более одного объекта могут использоваться двумя процессами.
Слайд 20Направленность
Направленность определяет возможность передачи данных в различных направлениях.
Средства связи могут
быть одно- или двунаправленные.
При однонаправленной связи каждый процесс может использовать данное средство связи либо только для приема информации, либо только для ее передачи.
При двунаправленной связи, каждый процесс, участвующий в обмене, может использовать средство связи и для приема, и для передачи данных.
В коммуникационных системах принято называть:
однонаправленную связь – симплексной;
двунаправленную связь с поочередной передачей информации в разных направлениях – полудуплексной;
двунаправленную связь с возможностью одновременной передачи информации в разных направлениях – дуплексной.
При однонаправленной связи каждый процесс может использовать данное средство связи либо только для приема информации, либо только для ее передачи.
При двунаправленной связи, каждый процесс, участвующий в обмене, может использовать средство связи и для приема, и для передачи данных.
В коммуникационных системах принято называть:
однонаправленную связь – симплексной;
двунаправленную связь с поочередной передачей информации в разных направлениях – полудуплексной;
двунаправленную связь с возможностью одновременной передачи информации в разных направлениях – дуплексной.
Слайд 21Порядок завершения связи
Порядок завершения связи определяется необходимостью выполнения процессом каких-либо
специальных действий по прекращению обмена.
Способы связи, которые не подразумевают инициализирующих действий, обычно не требуют действий для окончания взаимодействия.
Если установление связи требовало инициализации, то, как правило, при ее завершении необходимо выполнение операций, извещающих об этом ОС и партнеров по взаимодействию.
Согласованное прекращение взаимодействия процессов не влияет на корректность их дальнейшей работы.
Несогласованное окончание связи одним из взаимодействующих процессов, может привести к ситуации, в которой его партнеры, не завершившие общение, будут бесконечно ожидать получения данных и фактически окажутся заблокированными.
Способы связи, которые не подразумевают инициализирующих действий, обычно не требуют действий для окончания взаимодействия.
Если установление связи требовало инициализации, то, как правило, при ее завершении необходимо выполнение операций, извещающих об этом ОС и партнеров по взаимодействию.
Согласованное прекращение взаимодействия процессов не влияет на корректность их дальнейшей работы.
Несогласованное окончание связи одним из взаимодействующих процессов, может привести к ситуации, в которой его партнеры, не завершившие общение, будут бесконечно ожидать получения данных и фактически окажутся заблокированными.
Слайд 22Передача информации с помощью каналов связи
Каналы связи получили наибольшее распространение
среди средств связи процессов по следующим основным причинам:
операционная система обеспечивает набор базовых операций, требующихся для управления работой каналов связи, что облегчает их использование;
передача информации между процессами посредством каналов связи является в достаточной степени безопасной;
производительность каналов зависит от качества линии связи и, при организации линии в основной памяти, сравнима с производительностью разделяемой памяти;
линия связи может использоваться для связи процессов, функционирующих на различных компьютерах, что делает ее универсальным средством коммуникаций.
операционная система обеспечивает набор базовых операций, требующихся для управления работой каналов связи, что облегчает их использование;
передача информации между процессами посредством каналов связи является в достаточной степени безопасной;
производительность каналов зависит от качества линии связи и, при организации линии в основной памяти, сравнима с производительностью разделяемой памяти;
линия связи может использоваться для связи процессов, функционирующих на различных компьютерах, что делает ее универсальным средством коммуникаций.
Слайд 23Модели передачи данных
Для передачи данных по каналам связи используются две основных
модели организации данных:
поток ввода-вывода;
сообщения.
поток ввода-вывода;
сообщения.
Слайд 24Модель потока ввода-вывода
С точки зрения ОС передаваемые данные представляют собой неструктурированную
последовательность байт.
Операционная система не выполняет интерпретацию данных и не включает в передаваемую информацию никаких дополнительных служебных сведений.
ОС не предоставляет взаимодействующим процессам никакой сервисной информации, позволяющей определить характеристики данных.
Процесс, прочитавший данные, переданные по линии связи, в общем случае не имеет информации об их источниках и свойствах, если эти сведения не включались в передаваемый поток партнерами по взаимодействию.
Операционная система не следит за правильностью передачи данных.
Операционная система не выполняет интерпретацию данных и не включает в передаваемую информацию никаких дополнительных служебных сведений.
ОС не предоставляет взаимодействующим процессам никакой сервисной информации, позволяющей определить характеристики данных.
Процесс, прочитавший данные, переданные по линии связи, в общем случае не имеет информации об их источниках и свойствах, если эти сведения не включались в передаваемый поток партнерами по взаимодействию.
Операционная система не следит за правильностью передачи данных.
Слайд 25Модель сообщений
Операционная система полностью контролирует процесс обмена данными между процессами.
Передаваемые данные
структурируются путем разделения на отдельные порции – сообщения.
Начало и конец каждого сообщения обозначаются стандартными последовательностями байт, которые играют роль ограничителей и могут распознаваться модулями операционной системы, ответственными за передачу данных.
К каждому сообщению могут присоединяться служебные данные, содержащие указания на источник и приемник сообщения, а также его номер, размер, контрольные данные и другую вспомогательную информацию.
Сообщения могут иметь одинаковый фиксированный размер или переменную длину.
Модель сообщений дает возможность существенно увеличить надежность передачи данных.
Начало и конец каждого сообщения обозначаются стандартными последовательностями байт, которые играют роль ограничителей и могут распознаваться модулями операционной системы, ответственными за передачу данных.
К каждому сообщению могут присоединяться служебные данные, содержащие указания на источник и приемник сообщения, а также его номер, размер, контрольные данные и другую вспомогательную информацию.
Сообщения могут иметь одинаковый фиксированный размер или переменную длину.
Модель сообщений дает возможность существенно увеличить надежность передачи данных.
Слайд 26Буферизация
Под буферизацией обычно понимают способность линии связи временно сохранять информацию,
переданную одним процессом, до ее получения другим процессом или до помещения в промежуточный объект хранения данных.
Линии связи могут обладать или не обладать свойством буферизации. Обычно рассматриваются следующие три варианта:
буфер нулевой емкости или отсутствует – никакая информация не может сохраняться на линии связи и процесс может послать данные только если партнер подтвердит готовность к их приему;
буфер ограниченной емкости – линия связи может хранить фиксированный объем данных до момента получения их другим процессом, однако работа процесса-отправителя может приостанавливаться, если в буфере нет свободного пространства.
буфер неограниченной емкости – процесс, посылающий информацию, никогда не ждет окончания ее приема другим процессом.
При использовании канального средства связи с непрямой адресацией под емкостью буфера обычно понимается количество информации, которое может быть помещено в промежуточный объект для хранения данных.
Линии связи могут обладать или не обладать свойством буферизации. Обычно рассматриваются следующие три варианта:
буфер нулевой емкости или отсутствует – никакая информация не может сохраняться на линии связи и процесс может послать данные только если партнер подтвердит готовность к их приему;
буфер ограниченной емкости – линия связи может хранить фиксированный объем данных до момента получения их другим процессом, однако работа процесса-отправителя может приостанавливаться, если в буфере нет свободного пространства.
буфер неограниченной емкости – процесс, посылающий информацию, никогда не ждет окончания ее приема другим процессом.
При использовании канального средства связи с непрямой адресацией под емкостью буфера обычно понимается количество информации, которое может быть помещено в промежуточный объект для хранения данных.
Слайд 27Надежность линий связи
Средство связи считается надежным, если при обмене данными
выполняются следующие четыре условия:
не происходит потери информации;
не появляется лишней информации;
не происходит повреждения информации;
не нарушается порядок данных в процессе обмена.
К надежным средствам связи можно отнести все средства, для реализации которых используется основная память (разделяемую память, сообщения, сигналы и, в некоторых случаях, каналы).
В тех случаях, когда средство связи реализуется с помощью внешних устройств или линий связи, их надежность на физическом уровне не всегда может гарантироваться.
не происходит потери информации;
не появляется лишней информации;
не происходит повреждения информации;
не нарушается порядок данных в процессе обмена.
К надежным средствам связи можно отнести все средства, для реализации которых используется основная память (разделяемую память, сообщения, сигналы и, в некоторых случаях, каналы).
В тех случаях, когда средство связи реализуется с помощью внешних устройств или линий связи, их надежность на физическом уровне не всегда может гарантироваться.
Слайд 28Протокол связи
При низкой надежности средства связи ОС и взаимодействующие процессы должны
предпринимать действия, гарантирующие надежную передачу данных. Совокупность таких действий принято называть протоколом связи.
Наиболее просто реализуются протоколы обмена для линий связи, использующих модель сообщений.
Основные принципы протокола:
для каждого посланного сообщения, процесс, пославший данные, должен получить подтверждение о получении;
если подтверждение не получено, то данные считаются утерянными и сообщение посылается повторно;
при получении сообщения контролируется его правильность с помощью контрольных кодов и подтверждение о получении посылается только в случае, если данные не повреждены;
двойное получение одной и той же информации исключается путем нумерации сообщений.
Применение протоколов связи позволяет обеспечить надежную связь между взаимодействующими процессами даже если физическая линия связи не является надежной.
Наиболее просто реализуются протоколы обмена для линий связи, использующих модель сообщений.
Основные принципы протокола:
для каждого посланного сообщения, процесс, пославший данные, должен получить подтверждение о получении;
если подтверждение не получено, то данные считаются утерянными и сообщение посылается повторно;
при получении сообщения контролируется его правильность с помощью контрольных кодов и подтверждение о получении посылается только в случае, если данные не повреждены;
двойное получение одной и той же информации исключается путем нумерации сообщений.
Применение протоколов связи позволяет обеспечить надежную связь между взаимодействующими процессами даже если физическая линия связи не является надежной.
Слайд 30Общие сведения
Практически во все современные варианты операционной системы UNIX включен
следующий набор средств, обеспечивающий организацию взаимодействия процессов:
разделяемая память;
очереди сообщений;
сигналы;
каналы;
именованные каналы;
семафоры.
Разделяемую память, очереди сообщений и семафоры принято называть средствами UNIX System V IPC (Inter Process Communication).
UNIX System V IPC, а также каналы и сигналы стали фактическим стандартом средств взаимодействия процессов, который реализован практически во всех операционных системах.
разделяемая память;
очереди сообщений;
сигналы;
каналы;
именованные каналы;
семафоры.
Разделяемую память, очереди сообщений и семафоры принято называть средствами UNIX System V IPC (Inter Process Communication).
UNIX System V IPC, а также каналы и сигналы стали фактическим стандартом средств взаимодействия процессов, который реализован практически во всех операционных системах.
Слайд 31Общие свойства механизмов IPC
Несмотря на то, что все средства обеспечения взаимодействия
между процессами реализуются в виде отдельных механизмов, им присущи следующие общие свойства:
с каждым механизмом связана таблица, в записях которой описываются все его детали;
на каждый экземпляр средства связи отводится одна запись (строка) таблицы;
в каждой записи содержится числовой ключ, который представляет собой идентификатор экземпляра и используется для ссылок на соответствующий экземпляр средства связи;
в каждом механизме имеется системная функция типа «Get» (получить), используемая для создания новой или поиска существующей записи;
каждая запись включает поле (поля) данных, описывающее права доступа к ней и содержащее идентификаторы пользователя и группы для процесса, создавшего запись;
в каждой записи имеется информация, описывающая текущее состояние экземпляра.
с каждым механизмом связана таблица, в записях которой описываются все его детали;
на каждый экземпляр средства связи отводится одна запись (строка) таблицы;
в каждой записи содержится числовой ключ, который представляет собой идентификатор экземпляра и используется для ссылок на соответствующий экземпляр средства связи;
в каждом механизме имеется системная функция типа «Get» (получить), используемая для создания новой или поиска существующей записи;
каждая запись включает поле (поля) данных, описывающее права доступа к ней и содержащее идентификаторы пользователя и группы для процесса, создавшего запись;
в каждой записи имеется информация, описывающая текущее состояние экземпляра.
Слайд 32Идентификация экземпляров средства связи
Идентификация экземпляров средства связи IPC в прикладных программах
выполняется с помощью целочисленных идентификаторов, значение которых может быть получено с помощью системного вызова ftok, имеющего следующий формат:
ftok(filename, num),
где:
filename – полное имя некоторого файла, уже существующего в системе и доступного всем процессам, использующим данный экземпляр средства связи;
num – номер, позволяющий получать разные значения идентификаторов с помощью одного имени файла.
ftok(filename, num),
где:
filename – полное имя некоторого файла, уже существующего в системе и доступного всем процессам, использующим данный экземпляр средства связи;
num – номер, позволяющий получать разные значения идентификаторов с помощью одного имени файла.
Слайд 33Работа с разделяемой памятью
Работа разделяемой памяти обеспечивается путем выделения некоторой
области физической памяти, которая включается в адресное пространство каждого из взаимодействующих процессов.
Для выделения области, ее включения в адресное пространство процесса и освобождения области используются следующие системные вызовы IPC: shmget(), shmat() и shmdt().
Системный вызов shmget(id, size, shmflg) обеспечивает доступ к области разделяемой памяти с идентификатором id и размером size. Для этого:
в таблице разделяемых областей памяти выполняется поиск записи с указанным идентификатором id;
если запись не найдена, то создается новая область с размером size и соответствующая информация заносится в таблицу;
в случае успешного завершения, вызов возвращает дескриптор области shmid;
shmflg определяет права доступа к разделяемой области.
Для выделения области, ее включения в адресное пространство процесса и освобождения области используются следующие системные вызовы IPC: shmget(), shmat() и shmdt().
Системный вызов shmget(id, size, shmflg) обеспечивает доступ к области разделяемой памяти с идентификатором id и размером size. Для этого:
в таблице разделяемых областей памяти выполняется поиск записи с указанным идентификатором id;
если запись не найдена, то создается новая область с размером size и соответствующая информация заносится в таблицу;
в случае успешного завершения, вызов возвращает дескриптор области shmid;
shmflg определяет права доступа к разделяемой области.
Слайд 34Работа с разделяемой памятью
Системный вызов shmat(shmid, shmaddr, shmflg) включает область памяти в
адресное пространство текущего процесса.
Параметры системного вызова:
shmid является дескриптором, который вернул системный вызов shmget при создании области или при ее поиске по ключу;
shmaddr позволяет указать адрес начала разделяемой памяти в адресном пространстве процесса;
shmflg определяет режим доступа процесса к разделяемой памяти
Процесс должен иметь соответствующие права доступа к области. При нормальном завершении системный вызов возвращает адрес начала области памяти в адресном пространстве процесса.
Системный вызов shmdt(shmaddr) предназначен для исключения области разделяемой памяти из адресного пространства текущего процесса. Параметр shmaddr является адресом области разделяемой памяти, т.е. значением, которое вернул системный вызов shmat.
Параметры системного вызова:
shmid является дескриптором, который вернул системный вызов shmget при создании области или при ее поиске по ключу;
shmaddr позволяет указать адрес начала разделяемой памяти в адресном пространстве процесса;
shmflg определяет режим доступа процесса к разделяемой памяти
Процесс должен иметь соответствующие права доступа к области. При нормальном завершении системный вызов возвращает адрес начала области памяти в адресном пространстве процесса.
Системный вызов shmdt(shmaddr) предназначен для исключения области разделяемой памяти из адресного пространства текущего процесса. Параметр shmaddr является адресом области разделяемой памяти, т.е. значением, которое вернул системный вызов shmat.
Слайд 35Сообщения
Механизм сообщений обеспечивает обмен структурированными порциями данных между взаимодействующими процессами.
Для
реализации механизма операционная система организует связанный список (очередь), в которой сохраняются сообщения, переданные одним процессом, до их получения другим процессом.
Возможно использование нескольких независимых очередей для организации взаимодействия двух процессов, также несколько процессов могут использовать одну очередь для обмена сообщениями.
Очередь идентифицируется значением идентификатора, которое получается с помощью функции ftok.
Возможно использование нескольких независимых очередей для организации взаимодействия двух процессов, также несколько процессов могут использовать одну очередь для обмена сообщениями.
Очередь идентифицируется значением идентификатора, которое получается с помощью функции ftok.
Слайд 36Очередь сообщений
Каждая очередь сообщений имеет заголовок, использующийся для хранения вспомогательных данных,
и связанный список сообщений.
Заголовок содержит следующие основные поля:
идентификатор очереди;
права доступа;
указатели на первое и последнее сообщение в списке;
количество сообщений;
максимальная емкость списка в байтах;
идентификаторы процессов, пославших и принявших сообщения последними.
Заголовки всех очередей сообщений объединяются операционной системой в один массив.
Заголовок содержит следующие основные поля:
идентификатор очереди;
права доступа;
указатели на первое и последнее сообщение в списке;
количество сообщений;
максимальная емкость списка в байтах;
идентификаторы процессов, пославших и принявших сообщения последними.
Заголовки всех очередей сообщений объединяются операционной системой в один массив.
Слайд 37Системные вызовы для работы с сообщениями
msgget(id, flag) – возвращает дескриптор очереди msqid,
для идентификатора id, полученного функцией ftok. Параметр flag задает права доступа. При вызове функции msgget:
просматривается массив заголовков очередей сообщений в поисках существующей очереди с указанным идентификатором id;
если такой очереди нет, то создается новая очередь;
возвращается дескриптор msqid, соответствующий значению id.
msgsnd(msqid, msg, count, flag) – включает сообщение в конец очереди сообщений msqid (посылает сообщение). Здесь:
msqid – дескриптор очереди сообщений, которой вернула функция msgget;
msg – указатель на пользовательскую структуру данных, содержащую сообщение;
count – объем передаваемых данных;
flag – задает действие, выполняемое при переполнении очереди сообщений.
просматривается массив заголовков очередей сообщений в поисках существующей очереди с указанным идентификатором id;
если такой очереди нет, то создается новая очередь;
возвращается дескриптор msqid, соответствующий значению id.
msgsnd(msqid, msg, count, flag) – включает сообщение в конец очереди сообщений msqid (посылает сообщение). Здесь:
msqid – дескриптор очереди сообщений, которой вернула функция msgget;
msg – указатель на пользовательскую структуру данных, содержащую сообщение;
count – объем передаваемых данных;
flag – задает действие, выполняемое при переполнении очереди сообщений.
Слайд 38msgrcv(msqid, msg,count, type, flag) – извлечение процессом сообщения (получение сообщения) из головы очереди
сообщений msqid. Здесь:
msqid – дескриптор очереди сообщений;
msg – адрес пользовательской структуры данных, которая будет содержать полученное сообщение;
count – размер структуры msg;
type – тип считываемого сообщения;
flag – указывает действие системы в случае, если в очереди сообщений нет.
msqid – дескриптор очереди сообщений;
msg – адрес пользовательской структуры данных, которая будет содержать полученное сообщение;
count – размер структуры msg;
type – тип считываемого сообщения;
flag – указывает действие системы в случае, если в очереди сообщений нет.
Слайд 39Сигналы
Основным назначением механизма сигналов в UNIX является передача пользовательскому процессу
информации о прерываниях, которые могут быть полностью или частично обработаны в прикладной программе.
Поддерживается обмен сигналами между прикладными процессами, в этом случае механизм сигналов может использоваться для организации их взаимодействия.
Для поддержки механизма сигналов используются следующие элементы:
поле сигналов в записи таблицы процессов, содержащее по одному биту на каждый тип сигналов;
массив, содержащий адреса обработчиков сигналов (вектор сигналов), расположенный в пространстве процесса и содержащий по одному адресу на каждый тип сигналов.
Поддерживается обмен сигналами между прикладными процессами, в этом случае механизм сигналов может использоваться для организации их взаимодействия.
Для поддержки механизма сигналов используются следующие элементы:
поле сигналов в записи таблицы процессов, содержащее по одному биту на каждый тип сигналов;
массив, содержащий адреса обработчиков сигналов (вектор сигналов), расположенный в пространстве процесса и содержащий по одному адресу на каждый тип сигналов.
Слайд 40Обработка сигналов
Посылка сигнала процессу выполняется путем установки в асинхронном режиме в
единицу значения соответствующего бита поля сигналов в записи таблицы процессов.
Полученный процессом сигнал может быть проигнорирован или обработан.
Для сигнала может выполняться стандартная (обычно завершение процесса) или пользовательская обработка.
Обработка процессом полученного сигнала инициируется ядром в синхронном режиме. Для этого:
перед каждым переводом процесса из состояния «Выполняется в режиме ядра» в состояние «Выполняется в режиме задачи» проверяется состояние поля сигналов;
если обнаруживается, что какой-либо бит установлен в единицу, то вызывается на выполнение обработчик сигнала, адрес которого указан в соответствующем поле вектора сигналов;
если пользователь предусмотрел необходимость игнорирования сигнала, то никаких действий не выполняется.
Полученный процессом сигнал может быть проигнорирован или обработан.
Для сигнала может выполняться стандартная (обычно завершение процесса) или пользовательская обработка.
Обработка процессом полученного сигнала инициируется ядром в синхронном режиме. Для этого:
перед каждым переводом процесса из состояния «Выполняется в режиме ядра» в состояние «Выполняется в режиме задачи» проверяется состояние поля сигналов;
если обнаруживается, что какой-либо бит установлен в единицу, то вызывается на выполнение обработчик сигнала, адрес которого указан в соответствующем поле вектора сигналов;
если пользователь предусмотрел необходимость игнорирования сигнала, то никаких действий не выполняется.
Слайд 41Системные вызовы для работы с сигналами
Системные вызовы для работы с сигналами
обеспечивают передачу сигнала от одного прикладного процесса другому, а также позволяют переопределить обработчик сигналов для выполнения пользовательской обработки.
kill(PID, sig) – предназначен для посылки сигнала от одного прикладного процесса другому. Здесь:
PID – идентификатор процесса-приемника;
sig – целое число, задающее тип сигнала.
signal (sig, handler) – заменяет в векторе сигналов адрес стандартного обработчика сигналов для типа sig, на адрес пользовательского обработчика сигналов handler.
Пользовательский обработчик сигналов представляет собой подпрограмму, входящую в состав программы пользователя.
Вместо адреса пользовательского обработчика можно использовать специальное значение SIG_IGN, предписывающее игнорировать данный тип сигналов.
kill(PID, sig) – предназначен для посылки сигнала от одного прикладного процесса другому. Здесь:
PID – идентификатор процесса-приемника;
sig – целое число, задающее тип сигнала.
signal (sig, handler) – заменяет в векторе сигналов адрес стандартного обработчика сигналов для типа sig, на адрес пользовательского обработчика сигналов handler.
Пользовательский обработчик сигналов представляет собой подпрограмму, входящую в состав программы пользователя.
Вместо адреса пользовательского обработчика можно использовать специальное значение SIG_IGN, предписывающее игнорировать данный тип сигналов.
Слайд 42Каналы
Каналы являются наиболее употребительным средством связи между процессами, позволяющим организовать последовательный
симплексный обмен неструктурированными данными (потоковая модель передачи данных).
Каналы обеспечивают передачу достаточно больших объемов данных с высокой скоростью.
Каналы надежны и снабжены внутренними механизмами, обеспечивающими упорядоченный доступ процессов к передаваемой информации.
Канал представляют собой буфер который управляется средствами операционной системы.
В ранних версиях UNIX буфер поддерживался средствами файловой системы.
В современных операционных системах буфер организуется в памяти, однако модель передачи данных и интерфейс канала не изменились.
Каналы обеспечивают передачу достаточно больших объемов данных с высокой скоростью.
Каналы надежны и снабжены внутренними механизмами, обеспечивающими упорядоченный доступ процессов к передаваемой информации.
Канал представляют собой буфер который управляется средствами операционной системы.
В ранних версиях UNIX буфер поддерживался средствами файловой системы.
В современных операционных системах буфер организуется в памяти, однако модель передачи данных и интерфейс канала не изменились.
Слайд 43Неименованные каналы
Для связи родственных процессов, обычно родительского и дочернего, используются неименованные
каналы, которые часто называют просто каналами.
Неименованный канал создается с помощью системного вызова pipe(fd), где fd – массив из двух элементов fd[0] и fd[1].
Системный вызов возвращает вызвавшему процессу два файловых дескриптора fd[0] и fd[1], соответственно использующихся для чтения из канала и записи в канал.
Если в программе планируется чтение из канала, то дескриптор fd[1] необходимо закрыть.
Если в программе планируется запись в канал, то дескриптор fd[0] необходимо закрыть.
Передача дескрипторов от родительского процесса к дочернему осуществляется за счет наследование последним таблицы дескрипторов открытых файлов.
Неименованный канал создается с помощью системного вызова pipe(fd), где fd – массив из двух элементов fd[0] и fd[1].
Системный вызов возвращает вызвавшему процессу два файловых дескриптора fd[0] и fd[1], соответственно использующихся для чтения из канала и записи в канал.
Если в программе планируется чтение из канала, то дескриптор fd[1] необходимо закрыть.
Если в программе планируется запись в канал, то дескриптор fd[0] необходимо закрыть.
Передача дескрипторов от родительского процесса к дочернему осуществляется за счет наследование последним таблицы дескрипторов открытых файлов.
Слайд 44Именованные каналы
В тех случаях, когда процессы не связаны родственными отношениями, механизм
наследования дескрипторов не работает и для обмена данными используются именованные каналы, которые также называют FIFO.
Для создания именованного канала используется системный вызов mknod(filename,mode,0), который создает файл-метку типа FIFO с именем «filename» и правами доступа «mode».
Файл-метка может быть открыт процессами с помощью системного вызова open() для чтения или записи, однако реально соответствующие данные размещаются в буфере, находящемся в памяти ядра, а файл служит только для именования буфера.
Для создания именованного канала используется системный вызов mknod(filename,mode,0), который создает файл-метку типа FIFO с именем «filename» и правами доступа «mode».
Файл-метка может быть открыт процессами с помощью системного вызова open() для чтения или записи, однако реально соответствующие данные размещаются в буфере, находящемся в памяти ядра, а файл служит только для именования буфера.
Слайд 45Чтение и запись данных
Чтение из канала выполняется с помощью системного вызова
read, который предназначен для чтения файлов. При работе с каналом выполнение системного вызова read модифицируется следующим образом:
прочитанная информация удаляется из канала и не может быть прочитана повторно;
если процесс пытается прочесть больше данных, чем находится в канале, то выполняется только чтение имеющихся данных, а затем процесс блокируется, ожидая поступления новой порции информации, если существуют процессы, у которых канал открыт для записи.
Для записи в канал используется системный вызов write. При работе с каналом write блокирует записывающий процесс при переполнении буфера, если существуют процессы, у которых канал открыт для чтения.
Корректная работа механизма блокирования требует закрытия файловых дескрипторов канала, которые не используются в программе: при записи закрывается fd[0], а при чтении fd[1].
прочитанная информация удаляется из канала и не может быть прочитана повторно;
если процесс пытается прочесть больше данных, чем находится в канале, то выполняется только чтение имеющихся данных, а затем процесс блокируется, ожидая поступления новой порции информации, если существуют процессы, у которых канал открыт для записи.
Для записи в канал используется системный вызов write. При работе с каналом write блокирует записывающий процесс при переполнении буфера, если существуют процессы, у которых канал открыт для чтения.
Корректная работа механизма блокирования требует закрытия файловых дескрипторов канала, которые не используются в программе: при записи закрывается fd[0], а при чтении fd[1].
Слайд 46Семафоры
Семафоры являются средством, позволяющим выполнить синхронизацию взаимодействующих процессов.
Системные функции
работы с семафорами производят набор действий над группой семафоров.
Семафор представляет собой структуру данных, которая состоит из следующих элементов:
значение семафора;
идентификатор последнего из процессов, работавших с семафором;
количество процессов, ожидающих увеличения значения семафора;
количество процессов, ожидающих момента, когда значение семафора станет равным 0.
Семафор представляет собой структуру данных, которая состоит из следующих элементов:
значение семафора;
идентификатор последнего из процессов, работавших с семафором;
количество процессов, ожидающих увеличения значения семафора;
количество процессов, ожидающих момента, когда значение семафора станет равным 0.
Слайд 47Системные вызовы для работы с семафорами
semget(id,count,flag) – используется для создания набора
семафоров и получения доступа к ним. Здесь:
id – идентификатор, получаемый с помощью системного вызова ftok;
count – число семафоров в группе;
flag – права доступа.
semop(semid,oplist,countop) – выполняет операции с семафором. Здесь:
semid - дескриптор, возвращаемый функцией semget;
oplist - указатель на список операций;
countop – количество элементов списка операций.
Каждый элемент списка операций имеет следующий формат:
номер семафора, идентифицирующий элемент массива семафоров, над которым выполняется операция;
код операции;
флаги.
id – идентификатор, получаемый с помощью системного вызова ftok;
count – число семафоров в группе;
flag – права доступа.
semop(semid,oplist,countop) – выполняет операции с семафором. Здесь:
semid - дескриптор, возвращаемый функцией semget;
oplist - указатель на список операций;
countop – количество элементов списка операций.
Каждый элемент списка операций имеет следующий формат:
номер семафора, идентифицирующий элемент массива семафоров, над которым выполняется операция;
код операции;
флаги.
Слайд 48Операции над семафорами
Над семафорами допускаются три вида операций, определяемых значением
кода операции:
если величина кода операции положительна, то текущее значение семафора увеличивается на эту величину (А);
если величина кода операции равна нулю, то процесс блокируется до тех пор, пока текущее значение семафора не станет равным нулю (Z);
если величина кода операции отрицательна, то процесс блокируется до тех пор, пока текущее значение семафора не станет равным или большим этой величины, а затем значение семафора уменьшается на абсолютную величину кода операции (D).
Несколько процессов могут выполнять операции над одним семафором. Блокирование процессов на одном семафоре позволяет синхронизировать их работу.
Процесс, ожидающий изменения семафора, может быть выведен из этого состояния и при возникновении следующих ситуаций:
массив семафоров был удален из системы;
процесс получил сигнал, который должен быть обработан.
если величина кода операции положительна, то текущее значение семафора увеличивается на эту величину (А);
если величина кода операции равна нулю, то процесс блокируется до тех пор, пока текущее значение семафора не станет равным нулю (Z);
если величина кода операции отрицательна, то процесс блокируется до тех пор, пока текущее значение семафора не станет равным или большим этой величины, а затем значение семафора уменьшается на абсолютную величину кода операции (D).
Несколько процессов могут выполнять операции над одним семафором. Блокирование процессов на одном семафоре позволяет синхронизировать их работу.
Процесс, ожидающий изменения семафора, может быть выведен из этого состояния и при возникновении следующих ситуаций:
массив семафоров был удален из системы;
процесс получил сигнал, который должен быть обработан.
Слайд 50Общие сведения
Конфликтные ситуации при работе процессов обычно возникают в результате одновременного
обращения к совместно использующимся ресурсам.
К таким ресурсам можно отнести участки разделяемой памяти, файлы, системные структуры данных и т.д.
Часто появление конфликтов не планируется в соответствующих программах, поскольку процессы, вовлеченные во взаимодействие, не имеют информации друг о друге.
Одновременным обращением к ресурсу в случае псевдопараллельного выполнения процессов считается ситуация, в которой некоторый процесс получает доступ к ресурсу до того, как другой процесс завершил работу с этим ресурсом из-за приостановки планировщиком, вызванной прерыванием от системного таймера.
К таким ресурсам можно отнести участки разделяемой памяти, файлы, системные структуры данных и т.д.
Часто появление конфликтов не планируется в соответствующих программах, поскольку процессы, вовлеченные во взаимодействие, не имеют информации друг о друге.
Одновременным обращением к ресурсу в случае псевдопараллельного выполнения процессов считается ситуация, в которой некоторый процесс получает доступ к ресурсу до того, как другой процесс завершил работу с этим ресурсом из-за приостановки планировщиком, вызванной прерыванием от системного таймера.
Слайд 51Пример конфликта
В качестве примера рассмотрим упрощенную схему работы диспетчера печати.
Предположим, что
печать документа выполняется в следующем порядке:
процесс сохраняет документ в файле;
имя документа (файла) помещается в каталог диспетчера печати;
диспетчер печати, периодически проверяет наличие имен файлов в каталоге и, если имя обнаружено, печатает файл и удаляет его имя из каталога.
Предположим, что каталог диспетчера печати имеет следующую структуру:
каталог состоит из сегментов, пронумерованных 0, 1, 2 и т. д;
в каждом сегменте может храниться имя файла;
номер следующего свободного сегмента хранится в разделяемой переменной in.
процесс сохраняет документ в файле;
имя документа (файла) помещается в каталог диспетчера печати;
диспетчер печати, периодически проверяет наличие имен файлов в каталоге и, если имя обнаружено, печатает файл и удаляет его имя из каталога.
Предположим, что каталог диспетчера печати имеет следующую структуру:
каталог состоит из сегментов, пронумерованных 0, 1, 2 и т. д;
в каждом сегменте может храниться имя файла;
номер следующего свободного сегмента хранится в разделяемой переменной in.
Слайд 52Описание конфликта
Пусть процессы A и B выполняют следующую последовательность действий:
процесс A
считывает значение переменной in и сохраняет его в своей локальной переменной in_A;
процесс A приостанавливается из-за прерывания по таймеру и планировщик запускает процесс В;
процесс B считывает то же самое значение переменной in и сохраняет его в своей локальной переменной in_B.
процесс B сохраняет в каталоге имя файла и устанавливает in=in_B + 1.
запускается процесс A, который записывает имя файла в сегмент с номером in_A, удаляя имя файла, записанное процессом В.
значение переменной in устанавливается в in=in_A+1.
В результате выполнения указанной последовательности действий структура каталога программы печати не нарушена, но файл процесса B не будет напечатан.
процесс A приостанавливается из-за прерывания по таймеру и планировщик запускает процесс В;
процесс B считывает то же самое значение переменной in и сохраняет его в своей локальной переменной in_B.
процесс B сохраняет в каталоге имя файла и устанавливает in=in_B + 1.
запускается процесс A, который записывает имя файла в сегмент с номером in_A, удаляя имя файла, записанное процессом В.
значение переменной in устанавливается в in=in_A+1.
В результате выполнения указанной последовательности действий структура каталога программы печати не нарушена, но файл процесса B не будет напечатан.
Слайд 53Состояние состязания
Конфликтом принято называть любое взаимодействие процессов, приводящее к ошибкам в
их работе.
Источником конфликта является несогласованное одновременное обращение нескольких процессов к разделяемому ресурсу.
Для описания работы процессов с разделяемым ресурсом принято использовать понятие состояния состязания.
Состоянием состязания называется ситуация, которая может возникнуть при одновременном обращении нескольких процессов к одному и тому же ресурсу, такая, что конечный результат действий процессов оказывается потенциально некорректным, по крайней мере, для одного из них.
Исключение возможностей возникновения состояний состязания ведет к исключению конфликтов в работе взаимодействующих процессов.
Источником конфликта является несогласованное одновременное обращение нескольких процессов к разделяемому ресурсу.
Для описания работы процессов с разделяемым ресурсом принято использовать понятие состояния состязания.
Состоянием состязания называется ситуация, которая может возникнуть при одновременном обращении нескольких процессов к одному и тому же ресурсу, такая, что конечный результат действий процессов оказывается потенциально некорректным, по крайней мере, для одного из них.
Исключение возможностей возникновения состояний состязания ведет к исключению конфликтов в работе взаимодействующих процессов.
Слайд 54Обработка состояния состязания
Работа процессов с разделяемым ресурсом будет выполняться корректно только
в том случае, если они не будут попадать в состояния состязания.
Состояние состязания можно исключить путем запрета одновременного доступа нескольких процессов к разделяемым ресурсам.
Для реализации такого запрета каждый из взаимодействующих процессов перед обращением к ресурсу должен иметь возможность временно приостановить (блокировать) работу других процессов, стремящихся использовать данный ресурс.
Метод, использующий временное блокирование одним процессом доступа к совместно используемым ресурсам со стороны других процессов, принято называть взаимным исключением.
Состояние состязания можно исключить путем запрета одновременного доступа нескольких процессов к разделяемым ресурсам.
Для реализации такого запрета каждый из взаимодействующих процессов перед обращением к ресурсу должен иметь возможность временно приостановить (блокировать) работу других процессов, стремящихся использовать данный ресурс.
Метод, использующий временное блокирование одним процессом доступа к совместно используемым ресурсам со стороны других процессов, принято называть взаимным исключением.
Слайд 55Взаимное исключение
Взаимное исключение подразумевает, что некоторый процесс, первым обратившийся к разделяемым
ресурсам, получает их в монопольное владение до тех пор, пока он не закончит работу с этими ресурсами.
Никакой другой процесс не может в этот промежуток времени обратиться тем же ресурсам.
Взаимное исключение применяется во всех случаях, в которых существует потенциальная возможность возникновения состояния состязания.
Для реализации взаимного исключения требуется использование специальных средств и алгоритмов.
Алгоритмы и средства, обеспечивающие взаимное исключения должны:
предотвратить одновременное использование разделяемых ресурсов несколькими процессами;
обеспечить параллельное (псевдопараллельное) выполнение процессов в многозадачной среде.
Никакой другой процесс не может в этот промежуток времени обратиться тем же ресурсам.
Взаимное исключение применяется во всех случаях, в которых существует потенциальная возможность возникновения состояния состязания.
Для реализации взаимного исключения требуется использование специальных средств и алгоритмов.
Алгоритмы и средства, обеспечивающие взаимное исключения должны:
предотвратить одновременное использование разделяемых ресурсов несколькими процессами;
обеспечить параллельное (псевдопараллельное) выполнение процессов в многозадачной среде.
Слайд 56Критические области
Параллельное выполнение процессов можно обеспечить, если учесть, что в работе
каждого процесса можно выделить две фазы:
действия, не требующие обращения к разделяемым ресурсам и, соответственно, заведомо не приводящие к состояниям состязания;
действия, связанные с совместной обработкой ресурсов, которые могут привести к состоянию состязания.
Наличие указанных двух фаз позволяет разделить текст исполняемой программы на участки, содержащие обращения к совместно используемым данным, и участки, в которых работа с разделяемыми данными не выполняется.
Участки текста программы, обращающиеся к разделяемым ресурсам, принято называется критическими областями.
Организация взаимного исключения требуется только в критических областях процессов, а остальные части программ могут выполняться в произвольном порядке, как это происходит в случае невзаимодействующих процессов.
действия, не требующие обращения к разделяемым ресурсам и, соответственно, заведомо не приводящие к состояниям состязания;
действия, связанные с совместной обработкой ресурсов, которые могут привести к состоянию состязания.
Наличие указанных двух фаз позволяет разделить текст исполняемой программы на участки, содержащие обращения к совместно используемым данным, и участки, в которых работа с разделяемыми данными не выполняется.
Участки текста программы, обращающиеся к разделяемым ресурсам, принято называется критическими областями.
Организация взаимного исключения требуется только в критических областях процессов, а остальные части программ могут выполняться в произвольном порядке, как это происходит в случае невзаимодействующих процессов.
Слайд 57Обработка критических областей
Для корректной работы взаимодействующих процессов требуется обеспечить взаимное исключение
выполнения их критических областей, относящихся к одним ресурсам.
Взаимное исключение реализуется путем применения специальных средств программирования, структур данных и алгоритмов, обеспечивающих обработку критической области.
Критические области не должны содержать действий, которые не имеют непосредственного отношения к работе с разделяемым ресурсом, т.е. размер критической области должен быть минимальным.
Работа программы в критической области должна строиться на основе применения алгоритмов, гарантирующих корректную работу с разделяемыми ресурсами.
Взаимное исключение реализуется путем применения специальных средств программирования, структур данных и алгоритмов, обеспечивающих обработку критической области.
Критические области не должны содержать действий, которые не имеют непосредственного отношения к работе с разделяемым ресурсом, т.е. размер критической области должен быть минимальным.
Работа программы в критической области должна строиться на основе применения алгоритмов, гарантирующих корректную работу с разделяемыми ресурсами.
Слайд 58Условия корректности алгоритмов
Условие асинхронного выполнения. В алгоритме реализации взаимного исключения не
должно быть предположений о быстродействии процессов, что подразумевает невозможность предполагать одновременное или неодновременное выполнение определенных участков программ, выполняющихся в различных процессах.
Условие взаимного исключения. Совместное использование разделяемых ресурсов должно быть организованно таким образом, чтобы несколько процессов не могли одновременно выполнять свои критические области, относящихся к одним и тем же разделяемым данным.
Условие прогресса. Процесс, который не обращается к разделяемым ресурсам, не должен оказывать влияние на работу других процессов. Процесс, находящийся вне своей критической области, относящейся к некоторому ресурсу, и не стремящийся попасть в нее, не может блокировать другие процессы, работающие с тем же ресурсом.
Условие ограниченного ожидания. Не следует допускать возникновение ситуации, в которой процесс вечно ждет попадания в свою критическую область.
Условие взаимного исключения. Совместное использование разделяемых ресурсов должно быть организованно таким образом, чтобы несколько процессов не могли одновременно выполнять свои критические области, относящихся к одним и тем же разделяемым данным.
Условие прогресса. Процесс, который не обращается к разделяемым ресурсам, не должен оказывать влияние на работу других процессов. Процесс, находящийся вне своей критической области, относящейся к некоторому ресурсу, и не стремящийся попасть в нее, не может блокировать другие процессы, работающие с тем же ресурсом.
Условие ограниченного ожидания. Не следует допускать возникновение ситуации, в которой процесс вечно ждет попадания в свою критическую область.
Слайд 59Реализация взаимного исключения
Для корректного решения задачи взаимного исключения необходимо, чтобы каждый
из взаимодействующих процессов перед выполнением команд своей критической области мог приостановить выполнение других процессов, если они также стремятся попасть в свои критические области, относящихся к тем же разделяемым ресурсам.
Каждый процесс при входе в свою критическую область должен выполнить подготовительные действия (пролог), которые, с одной стороны, обеспечивают проверку возможности доступа к разделяемым данным и, с другой стороны, дают возможность их монопольного использования путем блокировке других процессов.
При выходе из критической области, соответственно должны выполняться действия, деблокирующие другие процессы (эпилог). При выполнении эпилога процесс должен обеспечить возобновление работы других процессов, приостановленных в ожидании возможности попадания в свои критические области.
Каждый процесс при входе в свою критическую область должен выполнить подготовительные действия (пролог), которые, с одной стороны, обеспечивают проверку возможности доступа к разделяемым данным и, с другой стороны, дают возможность их монопольного использования путем блокировке других процессов.
При выходе из критической области, соответственно должны выполняться действия, деблокирующие другие процессы (эпилог). При выполнении эпилога процесс должен обеспечить возобновление работы других процессов, приостановленных в ожидании возможности попадания в свои критические области.
Слайд 60Общая структура программы
Общая структура участка программы, предназначенного для реализации работы процесса
в критической области, в каждом из взаимодействующих процессов должна иметь следующий вид:
Для реализации работы процессов в критических областях используются различные средства и алгоритмы, которые могут требовать поддержки со стороны операционной системы, или целиком реализовываться на уровне пользователя.
Слайд 62Виды алгоритмов
При организации межпроцессного взаимодействия используются три основных разновидности алгоритмов:
запрет обработки
прерываний, который применяется модулями, входящими в состав ОС;
взаимное исключение с активным ожиданием, подразумевающее реализацию алгоритма в пространстве пользователя;
примитивы межпроцессных взаимодействий, представляющие собой средства, предоставляемые операционной системой программам пользователя для организации совместного доступа к ресурсам.
взаимное исключение с активным ожиданием, подразумевающее реализацию алгоритма в пространстве пользователя;
примитивы межпроцессных взаимодействий, представляющие собой средства, предоставляемые операционной системой программам пользователя для организации совместного доступа к ресурсам.
Слайд 63Запрет обработки прерываний
Самое простое решение проблемы взаимного исключения состоит в запрете
обработки всех прерываний перед входом процесса в критическую область и разрешении обработки прерываний после выходе из области.
Если работа процесса в критической области не может быть приостановлена, то ее выполнение может рассматриваться как атомарная операция и возникновение состояния состязания невозможно.
Основная проблема алгоритма – возможность возникновения аварийной ситуации, если запрет обработки прерываний реализован на уровне пользовательского процесса.
Запрет обработки прерываний может использоваться компонентами операционной системы при организации доступа к разделяемым системным ресурсам.
Если работа процесса в критической области не может быть приостановлена, то ее выполнение может рассматриваться как атомарная операция и возникновение состояния состязания невозможно.
Основная проблема алгоритма – возможность возникновения аварийной ситуации, если запрет обработки прерываний реализован на уровне пользовательского процесса.
Запрет обработки прерываний может использоваться компонентами операционной системы при организации доступа к разделяемым системным ресурсам.
Слайд 66Общие сведения
В тех случаях, когда синхронизация процессов выполняется без обращения к
операционной системе на уровне пользовательского процесса, используются алгоритмы, называемые алгоритмами с активным ожиданием.
В алгоритмах с активным ожиданием предполагается, что процесс определяет возможность входа в критическую область путем проверки значения, некоторой управляющей переменной (переменных).
Если процесс обнаруживает, что переменная имеет запрещающее значение, то он входит в цикл, в котором ожидает изменения этого значения на разрешающее.
Циклическая проверка управляющей переменной в ожидании разрешающего значения называется активным ожиданием.
Простейших алгоритмы с активным ожиданием не обеспечивают корректной организации взаимодействия процессов поскольку в них нарушаются условия корректности обработки критической области.
В алгоритмах с активным ожиданием предполагается, что процесс определяет возможность входа в критическую область путем проверки значения, некоторой управляющей переменной (переменных).
Если процесс обнаруживает, что переменная имеет запрещающее значение, то он входит в цикл, в котором ожидает изменения этого значения на разрешающее.
Циклическая проверка управляющей переменной в ожидании разрешающего значения называется активным ожиданием.
Простейших алгоритмы с активным ожиданием не обеспечивают корректной организации взаимодействия процессов поскольку в них нарушаются условия корректности обработки критической области.
Слайд 67Алгоритмы с активным ожиданием
Алгоритм с использованием переменной блокировки.
Алгоритм с использованием
указателя очередности.
Алгоритм с использованием флагов готовности.
Алгоритм Петерсона.
Алгоритм «булочной».
Алгоритмы, использующие команду TS.
Алгоритм с использованием флагов готовности.
Алгоритм Петерсона.
Алгоритм «булочной».
Алгоритмы, использующие команду TS.
Слайд 68Алгоритм с использованием переменной блокировки
Алгоритм основан на использовании разделяемой целой
переменной lock, значение которой проверяется процессами перед входом в критическую область и применяется для организации их блокировки.
Рассмотрим реализацию алгоритма на примере двух процессов.
Перед входом в критическую область, каждый процесс считывает значение lock:
если значение переменной равно 0, то процесс изменяет его на 1 и входит в критическую область;
если значение равно 1, то процесс ждет, пока оно сменится на 0.
Рассмотрим реализацию алгоритма на примере двух процессов.
Перед входом в критическую область, каждый процесс считывает значение lock:
если значение переменной равно 0, то процесс изменяет его на 1 и входит в критическую область;
если значение равно 1, то процесс ждет, пока оно сменится на 0.
Слайд 70Комментарии
Предположим, что некоторый процесс стремится попасть в свою критическую область и
считывает значение переменной блокировки.
Обнаружив, что значение равно 0, он выходит из цикла while.
Если выполнение этого процесса немедленно приостанавливается планировщиком, например, из-за прерывания от системного таймера, то значение переменной блокировки остается равным 0.
Если другой процесс, который обращается к тому же ресурсу, пытается войти в свою критическую область, то он обнаруживает нулевое значение lock, устанавливает его в единицу и приступает к выполнению своей критической области.
Если выполнение критической области данным процессом приостанавливается планировщиком, то для исполнения может быть снова выбран первый процесс.
После того, как первый процесс снова получит управление, он изменит значение переменной блокировки на 1 и приступит к выполнению своей критической области.
Таким образом, два процесса одновременно окажутся в своих критических областях, относящихся к одному ресурсу, и условие взаимного исключения будет нарушено.
Обнаружив, что значение равно 0, он выходит из цикла while.
Если выполнение этого процесса немедленно приостанавливается планировщиком, например, из-за прерывания от системного таймера, то значение переменной блокировки остается равным 0.
Если другой процесс, который обращается к тому же ресурсу, пытается войти в свою критическую область, то он обнаруживает нулевое значение lock, устанавливает его в единицу и приступает к выполнению своей критической области.
Если выполнение критической области данным процессом приостанавливается планировщиком, то для исполнения может быть снова выбран первый процесс.
После того, как первый процесс снова получит управление, он изменит значение переменной блокировки на 1 и приступит к выполнению своей критической области.
Таким образом, два процесса одновременно окажутся в своих критических областях, относящихся к одному ресурсу, и условие взаимного исключения будет нарушено.
Слайд 71Алгоритм с использованием указателя очередности
Алгоритм основан на использовании переменной, которая
не только обеспечивает блокировку процессов, но и указывает, какой процесс может войти в критическую область, определяя, таким образом, очередность доступа к разделяемым ресурсам.
Рассмотрим реализацию алгоритма на примере двух процессов.
Будем предполагать, что в каждой выполняемой программе определена целая переменная i, значением которой является номер процесса.
Не снижая общности, предположим, что процессам присвоены номера 0 и 1.
Для организации блокировки используется переменная turn, изначально равная 0, которая содержит номер процесса, который может войти в критическую область.
Рассмотрим реализацию алгоритма на примере двух процессов.
Будем предполагать, что в каждой выполняемой программе определена целая переменная i, значением которой является номер процесса.
Не снижая общности, предположим, что процессам присвоены номера 0 и 1.
Для организации блокировки используется переменная turn, изначально равная 0, которая содержит номер процесса, который может войти в критическую область.
Слайд 73Комментарии
Предположим, что процесс 0 первым пытается попасть в свою критическую область
и проверяет значение переменной turn.
Он считывает 0, сравнивает с собственным номером, который хранится в переменной i, и входит в критическую область.
Если процесс 1, после приостановки процесса 0, попытается попасть в свою критическую область, то он проверяет значение переменной, считывает 0 и после этого ожидает, когда значение станет равно 1.
Когда процесс 0 покидает свою критическую область, он изменяет значение переменной на 1, позволяя процессу 1 попасть в его критическую область.
При выходе из критической области процесс 1 меняет значение переменной turn на 0.
Фактически этот алгоритм требует строгого чередования при выполнении критических областей процессами.
Данный алгоритм нарушает условие прогресса, поскольку один процесс может быть блокирован другим, не находящимся в критической области и не стремящимся попасть в нее, если один процесс существенно медленнее другого.
Он считывает 0, сравнивает с собственным номером, который хранится в переменной i, и входит в критическую область.
Если процесс 1, после приостановки процесса 0, попытается попасть в свою критическую область, то он проверяет значение переменной, считывает 0 и после этого ожидает, когда значение станет равно 1.
Когда процесс 0 покидает свою критическую область, он изменяет значение переменной на 1, позволяя процессу 1 попасть в его критическую область.
При выходе из критической области процесс 1 меняет значение переменной turn на 0.
Фактически этот алгоритм требует строгого чередования при выполнении критических областей процессами.
Данный алгоритм нарушает условие прогресса, поскольку один процесс может быть блокирован другим, не находящимся в критической области и не стремящимся попасть в нее, если один процесс существенно медленнее другого.
Слайд 74Алгоритм с использованием флагов готовности
Недостаток предыдущего алгоритма заключается в том,
что процессы, пытающиеся войти в критическую область, не имеют информации о состоянии друг друга.
Для организации обмена информацией можно использовать разделяемый массив флагов ready из двух элементов, которые указывают на готовность входа процессов в свои критические области.
Рассмотрим реализацию алгоритма на примере двух процессов.
Когда i-й процесс готов войти в критическую область, он присваивает элементу массива ready[i] значение равное 1.
После выхода из критической области он сбрасывает это значение в 0.
Процесс не входит в критическую область, если другой процесс уже готов к входу в критическую область или находится в ней.
Для организации обмена информацией можно использовать разделяемый массив флагов ready из двух элементов, которые указывают на готовность входа процессов в свои критические области.
Рассмотрим реализацию алгоритма на примере двух процессов.
Когда i-й процесс готов войти в критическую область, он присваивает элементу массива ready[i] значение равное 1.
После выхода из критической области он сбрасывает это значение в 0.
Процесс не входит в критическую область, если другой процесс уже готов к входу в критическую область или находится в ней.
Слайд 76Комментарии
Данный алгоритм обеспечивает взаимоисключение и позволяет процессу, готовому к входу в
критическую область, войти в нее после завершения эпилога в другом процессе.
Алгоритм нарушает условие ограниченного ожидания:
пусть, например, после выполнения в процессе 0 присваивания ready[0]=1, он был приостановлен;
если будет выбран для выполнения процесс 1, то он также выполнит присваивание ready[1]=1;
после этого оба процесса будут бесконечно долго ожидать входа в критическую область, поскольку каждый из них блокирует выполнение критической области другого процесса.
Алгоритм нарушает условие ограниченного ожидания:
пусть, например, после выполнения в процессе 0 присваивания ready[0]=1, он был приостановлен;
если будет выбран для выполнения процесс 1, то он также выполнит присваивание ready[1]=1;
после этого оба процесса будут бесконечно долго ожидать входа в критическую область, поскольку каждый из них блокирует выполнение критической области другого процесса.
Слайд 77Алгоритм Петерсона
Корректное решение проблемы организации взаимодействия процессов возможно с помощью
алгоритма, который в 1981 предложил Петерсон.
В алгоритме Петерсона используется массив флагов готовности и переменная очередности.
При исполнении пролога процесс Pi устанавливает свой флаг готовности в единицу.
Затем он присваивает указателю очередности turn значение номера другого процесса, предлагая другому процессу приступить к выполнению его критической области.
Вход процесса в его критическую область блокируется только в случае, если одновременно установлены флаг готовности и номер очередности другого процесса.
Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу.
При этом одно из предложений всегда последует после другого. Тем самым работу в критической области продолжит процесс, которому было сделано последнее предложение.
В алгоритме Петерсона используется массив флагов готовности и переменная очередности.
При исполнении пролога процесс Pi устанавливает свой флаг готовности в единицу.
Затем он присваивает указателю очередности turn значение номера другого процесса, предлагая другому процессу приступить к выполнению его критической области.
Вход процесса в его критическую область блокируется только в случае, если одновременно установлены флаг готовности и номер очередности другого процесса.
Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу.
При этом одно из предложений всегда последует после другого. Тем самым работу в критической области продолжит процесс, которому было сделано последнее предложение.
Слайд 79Комментарии.
Условие взаимного исключения
Выполнение условия докажем методом от противного.
Пусть это
условие нарушено и оба процесса одновременно оказались внутри своих критических областей. В этом случае значения флагов готовности для обоих процессов совпадают и равны 1.
Процессы могут войти в критические области либо одновременно, либо поочередно выполняя цикл while.
Оба процесса не могут войти в критические области из состояния, когда они одновременно выполняли цикл while, по следующим причинам:
при выполнении процессами цикла значения turn и ready не изменяются;
процесс Pi может войти в критическую область, только в случае, когда ready[1 ‑ i]==0 или turn==i;
для обоих процессов флаги готовности равны 1, так как по предположению они оба находятся в критической области;
следовательно переменная turn одновременно имеет значения 0 и 1, что невозможно.
Процессы могут войти в критические области либо одновременно, либо поочередно выполняя цикл while.
Оба процесса не могут войти в критические области из состояния, когда они одновременно выполняли цикл while, по следующим причинам:
при выполнении процессами цикла значения turn и ready не изменяются;
процесс Pi может войти в критическую область, только в случае, когда ready[1 ‑ i]==0 или turn==i;
для обоих процессов флаги готовности равны 1, так как по предположению они оба находятся в критической области;
следовательно переменная turn одновременно имеет значения 0 и 1, что невозможно.
Слайд 80Комментарии.
Условие взаимного исключения
Если процессы не одновременно выполняли цикл while перед
входом в критическую область, то один из них первым войдет в нее.
Пусть процесс P0 первым вошел в свою критическую область.
Тогда процесс P1 должен был выполнить перед вхождением в цикл while, по крайней мере, один предваряющий оператор turn = 0.
Однако после этого он не может выйти из цикла while до окончания выполнения критической области процессом P0, так как при входе в цикл были установлены значения ready[0]==1 и turn==0, и эти значения не могут измениться до тех пор, пока процесс P0 не покинет свою критическую область.
Следовательно два процесса не могут одновременно выполнять свои критические области и алгоритм Петерсона обеспечивает взаимное исключение процессов.
Пусть процесс P0 первым вошел в свою критическую область.
Тогда процесс P1 должен был выполнить перед вхождением в цикл while, по крайней мере, один предваряющий оператор turn = 0.
Однако после этого он не может выйти из цикла while до окончания выполнения критической области процессом P0, так как при входе в цикл были установлены значения ready[0]==1 и turn==0, и эти значения не могут измениться до тех пор, пока процесс P0 не покинет свою критическую область.
Следовательно два процесса не могут одновременно выполнять свои критические области и алгоритм Петерсона обеспечивает взаимное исключение процессов.
Слайд 81Комментарии.
Условие прогресса
Докажем выполнение условия прогресса.
Рассмотрим, без ограничения общности, процесс
P0, который стремится попасть в свою критическую область и установил в единицу флаг готовности ready[0]==1.
Процесс P0 блокируется при выполнении цикла только при совместном выполнении условий ready[1]==1 и turn==1.
Если процесс P1 не стремиться к выполнению своей критической области, то ready[1]==0 и P0 попадет в свою критическую область. Таким образом, процесс не пытающийся попасть в свою критическую область не препятствует попаданию другого процесса в его критическую область.
Если процесс P1 готов к выполнению своей критической области, то перед входом в нее он устанавливает флаг готовности ready[1] == 1.
Переменная turn имеет значение 0 или 1, позволяя одному из процессов (P0 или P1) начать выполнение своей критической области.
Таким образом, вход процесса в его критическую область блокируется только в случае, если другой процесс выполняет свою критическую область или стремится попасть в нее.
Процесс P0 блокируется при выполнении цикла только при совместном выполнении условий ready[1]==1 и turn==1.
Если процесс P1 не стремиться к выполнению своей критической области, то ready[1]==0 и P0 попадет в свою критическую область. Таким образом, процесс не пытающийся попасть в свою критическую область не препятствует попаданию другого процесса в его критическую область.
Если процесс P1 готов к выполнению своей критической области, то перед входом в нее он устанавливает флаг готовности ready[1] == 1.
Переменная turn имеет значение 0 или 1, позволяя одному из процессов (P0 или P1) начать выполнение своей критической области.
Таким образом, вход процесса в его критическую область блокируется только в случае, если другой процесс выполняет свою критическую область или стремится попасть в нее.
Слайд 82Комментарии.
Условие ограниченного ожидания
Докажем выполнение условия ограниченного ожидания.
Процесс будет блокирован только
в том случае, когда другой процесс находится в своей критической области.
Например, если процесс P1 выполняет свою критическую область, то P0 блокируется, выполняя цикл, так как ready[1]==1 и turn==1.
Сразу после завершения выполнения критической области процессом P1, он сбросит свой флаг готовности ready[1] в значение 0 и процесс P0 завершит выполнение активного ожидания.
Таким образом, каждый процесс сможет начать исполнение своей критической области после не более чем одного выполнения другим процессом его критической области.
Например, если процесс P1 выполняет свою критическую область, то P0 блокируется, выполняя цикл, так как ready[1]==1 и turn==1.
Сразу после завершения выполнения критической области процессом P1, он сбросит свой флаг готовности ready[1] в значение 0 и процесс P0 завершит выполнение активного ожидания.
Таким образом, каждый процесс сможет начать исполнение своей критической области после не более чем одного выполнения другим процессом его критической области.
Удовлетворение условия асинхронного выполнения очевидно, поскольку в алгоритме не делалось предположений о скорости выполнения процессов.
Слайд 83Алгоритм «булочной»
Алгоритм синхронизации для n взаимодействующих процессов получил название алгоритм
«булочной».
Алгоритм предполагает, что все процессы, стремящиеся попасть в свои критические области, выстраиваются в очередь.
Каждый процесс перед входом в критическую область должен получить номер в очереди, который больше номеров, имеющихся у других процессов, уже находящихся в очереди.
В критическую область входит процесс с наименьшим номером.
Из-за неатомарности операции вычисления номера в очереди уникальность номеров не гарантируется.
Поскольку операционная система гарантирует, что все идентификаторы процессов уникальны, то пара, состоящая из неуникального номера в очереди и уникального идентификатора процесса, позволяет однозначно организовать очередь процессов.
В случае равенства номеров у двух или большего числа процессов первым обслуживается тот, который имеет меньшее значение идентификатора процесса.
Алгоритм предполагает, что все процессы, стремящиеся попасть в свои критические области, выстраиваются в очередь.
Каждый процесс перед входом в критическую область должен получить номер в очереди, который больше номеров, имеющихся у других процессов, уже находящихся в очереди.
В критическую область входит процесс с наименьшим номером.
Из-за неатомарности операции вычисления номера в очереди уникальность номеров не гарантируется.
Поскольку операционная система гарантирует, что все идентификаторы процессов уникальны, то пара, состоящая из неуникального номера в очереди и уникального идентификатора процесса, позволяет однозначно организовать очередь процессов.
В случае равенства номеров у двух или большего числа процессов первым обслуживается тот, который имеет меньшее значение идентификатора процесса.
Слайд 84Описание реализации
В программе используются два разделяемых массива: choosing, элементы которого могут
принимать значения false или true, и целочисленный массив номеров number.
Число элементов каждого массива больше или равно числу взаимодействующих процессов.
Элементы массива choosing устанавливаются процессами в значение true, если они находятся в состоянии выбора номера в очереди, противном случае они имеют значение false .
Элементы массива number сохраняют номер процесса в очереди, а значение 0 указывает, что процесс не находится в очереди. Изначально элементы этих массивов инициируются значениями false и 0 соответственно.
Модель программы, реализующей алгоритм «булочной» для процесса Pi использует следующие обозначения:
(a,b) < (c,d), если a < c или если a == c и b < d
max(a0, a1, ...., an-1) – это число k такое, что k > ai для i от 0 до n-1.
Число элементов каждого массива больше или равно числу взаимодействующих процессов.
Элементы массива choosing устанавливаются процессами в значение true, если они находятся в состоянии выбора номера в очереди, противном случае они имеют значение false .
Элементы массива number сохраняют номер процесса в очереди, а значение 0 указывает, что процесс не находится в очереди. Изначально элементы этих массивов инициируются значениями false и 0 соответственно.
Модель программы, реализующей алгоритм «булочной» для процесса Pi использует следующие обозначения:
(a,b) < (c,d), если a < c или если a == c и b < d
max(a0, a1, ...., an-1) – это число k такое, что k > ai для i от 0 до n-1.
Слайд 86Комментарии
Взаимное исключение обеспечивается за счет выполнения следующих требований:
процесс Pi ожидает завершения
процедуры выбора номера всех процессов, приступивших к ее выполнению, поскольку они могут получить меньший или равный номер;
процесс Pi не может войти в свою критическую область, если его номер в очереди не наименьший из существующих номеров процессов, находящихся в очереди;
процесс, преступивший к выбору номера после завершения выбора для процесса Pi , гарантированно получит больший номер в очереди.
Условие прогресса обеспечивается следующими факторами:
процесс, не находящийся в очереди, имеет нулевой номер (т.е. number[j]==0) и не может блокировать другой процесс;
процесс, находящийся в очереди (т.е. number[j]!=0), всегда участвует в определении очередности.
Выполнение условия ограниченного ожидания гарантируется тем, что процесс входит в критическую область после того, как другие процессы пройдут ее не более одного раза.
Выполнение условия асинхронного выполнения очевидно.
процесс Pi не может войти в свою критическую область, если его номер в очереди не наименьший из существующих номеров процессов, находящихся в очереди;
процесс, преступивший к выбору номера после завершения выбора для процесса Pi , гарантированно получит больший номер в очереди.
Условие прогресса обеспечивается следующими факторами:
процесс, не находящийся в очереди, имеет нулевой номер (т.е. number[j]==0) и не может блокировать другой процесс;
процесс, находящийся в очереди (т.е. number[j]!=0), всегда участвует в определении очередности.
Выполнение условия ограниченного ожидания гарантируется тем, что процесс входит в критическую область после того, как другие процессы пройдут ее не более одного раза.
Выполнение условия асинхронного выполнения очевидно.
Слайд 87Команда TS
Наличие аппаратной поддержки взаимных исключений позволяет упростить алгоритмы и
повысить их эффективность.
Многие вычислительные системы имеют специальные команды процессора, которые позволяют проверить и изменить значение машинного слова, выполняя эти действия как атомарные операции.
Примером такой команды может служить команда TS (Test and Set -проверить и установить).
Формат команды: TS register, lock.
Команда считывает содержимое lock переменной в регистр register, а в lock записывается значение 1.
Гарантируется, что операция считывания значения и записи единицы в переменную неделима.
Многие вычислительные системы имеют специальные команды процессора, которые позволяют проверить и изменить значение машинного слова, выполняя эти действия как атомарные операции.
Примером такой команды может служить команда TS (Test and Set -проверить и установить).
Формат команды: TS register, lock.
Команда считывает содержимое lock переменной в регистр register, а в lock записывается значение 1.
Гарантируется, что операция считывания значения и записи единицы в переменную неделима.
Слайд 88Описание реализации
При использовании команды TS переменная lock играет роль переменной блокировки.
Все
операции, связанные с ее переключением являются атомарными.
Процессы совместно используют переменную lock для синхронизации доступа к разделяемому ресурсу, выполняя следующие действия:
если значение lock равно 0, любой процесс может изменить его на 1 и обратиться к ресурсу;
если значение lock равно 1, процесс должен ожидать нулевого значения этой переменной;
при выходе из своей критической область процесс должен установить нулевое значение для lock.
Вход и выход из критической области с помощью команды TS можно реализовать с помощью двух подпрограмм, одна из которых (enter_region) выполняет пролог, требующийся для организации взаимного исключения, а другая (leave_region) эпилог.
Процессы совместно используют переменную lock для синхронизации доступа к разделяемому ресурсу, выполняя следующие действия:
если значение lock равно 0, любой процесс может изменить его на 1 и обратиться к ресурсу;
если значение lock равно 1, процесс должен ожидать нулевого значения этой переменной;
при выходе из своей критической область процесс должен установить нулевое значение для lock.
Вход и выход из критической области с помощью команды TS можно реализовать с помощью двух подпрограмм, одна из которых (enter_region) выполняет пролог, требующийся для организации взаимного исключения, а другая (leave_region) эпилог.
Слайд 90Комментарии
Прежде чем попасть в критическую область, процесс вызывает процедуру enter_region.
Если значение
lock было равно 1, то оно не изменяется и процесс выполняет активное ожидание до того момента, когда другой процесс не установит для lock нулевое значение.
Если значение lock равно 0, то команда TS:
устанавливает его в 1 и блокирует другие процессы;
ожидание не выполняется и процедура enter_region возвращает управление процессу, позволяя ему войти в критическую область.
По выходе из критической области:
процесс вызывает процедуру leave_region;
записывает 0 в переменную lock, устраняя блокировку других процессов.
Если значение lock равно 0, то команда TS:
устанавливает его в 1 и блокирует другие процессы;
ожидание не выполняется и процедура enter_region возвращает управление процессу, позволяя ему войти в критическую область.
По выходе из критической области:
процесс вызывает процедуру leave_region;
записывает 0 в переменную lock, устраняя блокировку других процессов.
Слайд 92Недостатки алгоритмов с активным ожиданием
Алгоритм Петерсона, алгоритм «булочной» и команда TS
дают корректное решение проблемы синхронизации, но обладают общим недостатком – использованием активного ожидания.
Активное ожидание не только бесцельно расходует время процессора, но может привести к более серьезным проблемам.
Одной из известных проблем активного ожидания является так называемая проблема инверсии приоритета:
пусть в системе выполняются два процесса: Н с высоким приоритетом и L с низким приоритетом, которые обращаются к разделяемым ресурсам;
процесс Н запускается немедленно, как только он оказывается в состоянии готовности;
пусть в момент, когда процесс L находится в критической области, процесс Н находится в состоянии готовности и пытается попасть в критическую область и попадает в состояние активного ожидания;
поскольку процессу L во время работы процесса Н никогда не будет предоставлено процессорное время, то у процесса L не будет возможности выйти из критической области, а процесс Н навсегда останется в цикле.
Активное ожидание не только бесцельно расходует время процессора, но может привести к более серьезным проблемам.
Одной из известных проблем активного ожидания является так называемая проблема инверсии приоритета:
пусть в системе выполняются два процесса: Н с высоким приоритетом и L с низким приоритетом, которые обращаются к разделяемым ресурсам;
процесс Н запускается немедленно, как только он оказывается в состоянии готовности;
пусть в момент, когда процесс L находится в критической области, процесс Н находится в состоянии готовности и пытается попасть в критическую область и попадает в состояние активного ожидания;
поскольку процессу L во время работы процесса Н никогда не будет предоставлено процессорное время, то у процесса L не будет возможности выйти из критической области, а процесс Н навсегда останется в цикле.
Слайд 93Общие сведения
Для устранения проблем, возникающих в алгоритмах с активным ожиданием, используются
механизмы синхронизации, использующие запрет обработки прерываний, и, соответственно, реализуемые на уровне ядра операционной системы.
Средства синхронизации, предоставляемые операционной системой, принято называть примитивами взаимодействий.
На базе использования примитивов взаимодействий обычно реализуются следующие три механизма:
семафоры;
мониторы;
сообщения.
Общим свойством примитивов является то, что операционная система гарантирует атомарность связанных с ними операций, а также организует при необходимости блокировку процессов (перевод в состояние ожидания) в случае запрета на вход в критическую область.
Средства синхронизации, предоставляемые операционной системой, принято называть примитивами взаимодействий.
На базе использования примитивов взаимодействий обычно реализуются следующие три механизма:
семафоры;
мониторы;
сообщения.
Общим свойством примитивов является то, что операционная система гарантирует атомарность связанных с ними операций, а также организует при необходимости блокировку процессов (перевод в состояние ожидания) в случае запрета на вход в критическую область.
Слайд 94Проблема производителя и потребителя
Для демонстрации работы примитивов в дальнейшем используется
классическая задача, называемая проблемой производителя и потребителя или проблемой ограниченного буфера.
Необходимость решения данной задачи часто возникает при организации взаимодействия процессов.
Проблема производителя и потребителя обычно формулируется следующим образом:
два процесса обмениваются данными, совместно используя буфер ограниченной емкости;
процесс-производитель (Producer), вырабатывает некоторые данные и помещает их в буфер;
процесс-потребитель (Consumer), считывает данные из буфера и использует их в своей работе.
Необходимость решения данной задачи часто возникает при организации взаимодействия процессов.
Проблема производителя и потребителя обычно формулируется следующим образом:
два процесса обмениваются данными, совместно используя буфер ограниченной емкости;
процесс-производитель (Producer), вырабатывает некоторые данные и помещает их в буфер;
процесс-потребитель (Consumer), считывает данные из буфера и использует их в своей работе.
Слайд 95Описание проблемы производителя и потребителя
Если производитель пытается поместить в буфер
очередную порцию данных и обнаруживает, что буфер полон, то для производителя решением является ожидание, пока потребитель полностью или частично не освободит буфер.
Если потребитель пытается забрать данные из буфера, а буфер пуст, он должен ожидать, пока производитель не поместит данные в буфер.
Потребитель не должен считывать из буфера очередную порцию данных, если производитель не успел полностью поместить ее в буфер, например из-за того, что его работа была приостановлена.
Решение задачи требует использования вспомогательных разделяемых переменных, которые используются для учета свободного и занятого пространства в буфере, а также для синхронизации работы процессов.
Наличие вспомогательных разделяемых переменных неизбежно приводит к возникновению состояний состязания.
Если потребитель пытается забрать данные из буфера, а буфер пуст, он должен ожидать, пока производитель не поместит данные в буфер.
Потребитель не должен считывать из буфера очередную порцию данных, если производитель не успел полностью поместить ее в буфер, например из-за того, что его работа была приостановлена.
Решение задачи требует использования вспомогательных разделяемых переменных, которые используются для учета свободного и занятого пространства в буфере, а также для синхронизации работы процессов.
Наличие вспомогательных разделяемых переменных неизбежно приводит к возникновению состояний состязания.
Слайд 97Комментарии
Не снижая общности применяемых методов решения проблемы в дальнейшем используется следующая
упрощенная модель работы производителя и потребителя:
производитель и потребитель выполняют бесконечные циклы;
в каждой итерации производитель вырабатывает некоторые данные, вызывая процедуру produce_item, а затем размещает их в буфере, используя процедуру put_item.
потребитель в каждой итерации извлекает данные из буфера с помощью процедуры get_item и использует их в своей работе, вызывая consume_item.
производитель и потребитель выполняют бесконечные циклы;
в каждой итерации производитель вырабатывает некоторые данные, вызывая процедуру produce_item, а затем размещает их в буфере, используя процедуру put_item.
потребитель в каждой итерации извлекает данные из буфера с помощью процедуры get_item и использует их в своей работе, вызывая consume_item.
Слайд 98Семафоры. Определение
Семафоры являются специализированным средством синхронизации выполнения процессов.
В соответствии с первоначальным
определением, данным Дейкстрой, семафор представляет собой целую переменную S, принимающую неотрицательные значения.
Доступ к этой переменной любого процесса, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: Up и Down.
Эти операции имеют следующее классическое определение:
Up (S) всегда увеличивает на 1 значение переменной S без выполнения каких-либо предварительных действий и проверки условий;
при выполнении операции Down (S) над семафором S проверяется его текущее значение;
если оно больше 0, то из S вычитается 1;
если оно равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1.
Доступ к этой переменной любого процесса, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: Up и Down.
Эти операции имеют следующее классическое определение:
Up (S) всегда увеличивает на 1 значение переменной S без выполнения каких-либо предварительных действий и проверки условий;
при выполнении операции Down (S) над семафором S проверяется его текущее значение;
если оно больше 0, то из S вычитается 1;
если оно равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1.
Слайд 99Общие сведения
Переменные-семафоры могут быть применены для решения различных задач организации взаимодействия
процессов.
В некоторых языках программирования они непосредственно введены в синтаксис языка, в других случаях применяются посредством использование системных вызовов.
В любом случае семафоры реализуются средствами ОС и соответствующая целая переменная S располагается внутри адресного пространства ядра операционной системы.
Атомарность операций Down и Up, обеспечивается ядром ОС, например путем запрета прерываний на время выполнения системных вызовов.
Если при выполнении операции Down заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным.
В некоторых языках программирования они непосредственно введены в синтаксис языка, в других случаях применяются посредством использование системных вызовов.
В любом случае семафоры реализуются средствами ОС и соответствующая целая переменная S располагается внутри адресного пространства ядра операционной системы.
Атомарность операций Down и Up, обеспечивается ядром ОС, например путем запрета прерываний на время выполнения системных вызовов.
Если при выполнении операции Down заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным.
Слайд 100Решение проблемы производителя и потребителя
Для обмена данными процессы используют буфер, который
состоит из N сегментов.
Взаимодействие процессов организуется с помощью трех семафоров с именами empty, full и mutex.
Текущим значением семафора empty является число пустых сегментов буфера. Если оно равно 0, то буфер полон и производитель блокируется. Начальное значение равно N.
Текущим значением семафор full является число полных сегментов буфера. Если оно равно 0, то буфер пуст и потребитель блокируется. Начальное значение равно 0.
Семафор mutex используется для организации взаимоисключения при выполнении доступа к буферу.
Критическими областями являются процедуры put_item и get_item (операции доступа к буферу не могут пересекаться, так как тогда возникнет опасность искажения данных).
Семафор mutex имеет два значения 0 и 1.
Взаимодействие процессов организуется с помощью трех семафоров с именами empty, full и mutex.
Текущим значением семафора empty является число пустых сегментов буфера. Если оно равно 0, то буфер полон и производитель блокируется. Начальное значение равно N.
Текущим значением семафор full является число полных сегментов буфера. Если оно равно 0, то буфер пуст и потребитель блокируется. Начальное значение равно 0.
Семафор mutex используется для организации взаимоисключения при выполнении доступа к буферу.
Критическими областями являются процедуры put_item и get_item (операции доступа к буферу не могут пересекаться, так как тогда возникнет опасность искажения данных).
Семафор mutex имеет два значения 0 и 1.
Слайд 102Комментарии
В схеме решения задачи семафоры использовались для организации взаимоисключения в критической
области и синхронизации скорости работы процессов.
Программирование с использованием семафоров требует повышенной осторожности, так как нарушение порядка их использования приводит к появлению ошибок, которые трудно искать и устранять.
Например, если установить неправильный порядок выполнения операций над семафорами, сначала выполняя Down для семафора mutex, а затем для семафоров full или empty, то взаимодействующие процессы могут попасть в ситуацию взаимной блокировки.
В программах с большим количеством семафоров трудно произвести анализ правильности их использования, а обычные способы отладки зачастую не дают результата, поскольку возникновение ошибок зависит от порядка чередования атомарных операций.
Программирование с использованием семафоров требует повышенной осторожности, так как нарушение порядка их использования приводит к появлению ошибок, которые трудно искать и устранять.
Например, если установить неправильный порядок выполнения операций над семафорами, сначала выполняя Down для семафора mutex, а затем для семафоров full или empty, то взаимодействующие процессы могут попасть в ситуацию взаимной блокировки.
В программах с большим количеством семафоров трудно произвести анализ правильности их использования, а обычные способы отладки зачастую не дают результата, поскольку возникновение ошибок зависит от порядка чередования атомарных операций.
Слайд 103Мониторы. Определение
Мониторами называются высокоуровневые средства синхронизации процессов, которые могут быть реализованы
в языках программирования высокого уровня.
Синхронизация процессов подразумевает поддержку взаимного исключения, а также организацию очередности доступа к критической области.
Мониторы могут быть реализованы в рамках концепции объектно-ориентированного программирования и включать поля, методы и блок инициализации внутренних переменных, который содержит операции, выполняющиеся только один раз при создании монитора или перед первым выполнением одного из его методов.
Реализация мониторов должна предусматривать, что только один процесс может быть активен внутри монитора, т.е. выполнять некоторый метод данного монитора и не блокироваться.
Синхронизация процессов подразумевает поддержку взаимного исключения, а также организацию очередности доступа к критической области.
Мониторы могут быть реализованы в рамках концепции объектно-ориентированного программирования и включать поля, методы и блок инициализации внутренних переменных, который содержит операции, выполняющиеся только один раз при создании монитора или перед первым выполнением одного из его методов.
Реализация мониторов должна предусматривать, что только один процесс может быть активен внутри монитора, т.е. выполнять некоторый метод данного монитора и не блокироваться.
Слайд 104Взаимное исключение и очередность
При доступе к критической области процессы должны использовать
соответствующие методы монитора. Это обеспечивает взаимное исключение, поскольку внутри монитора может быть активен только один процесс.
Для организации очередности процессов в мониторах предусматриваются специальные поля, называемые условными переменными, и соответствующие методы wait и signal, которые могут выполняться над этими полями:
если некоторый метод монитора не может выполняться, пока не наступит некоторое событие, он выполняет операцию wait над некоторой условной переменной;
соответствующий процесс блокируется и становится неактивным;
другой процесс получает возможность войти в монитор, т.е. приступить к выполнению одного из его методов;
если активный процесс генерирует событие, которое ожидает процесс выполнивший операцию wait, то он инициирует операцию signal над той же самой условной переменной;
в результате один из ранее заблокированных на этой переменной процессов становится активным.
Для организации очередности процессов в мониторах предусматриваются специальные поля, называемые условными переменными, и соответствующие методы wait и signal, которые могут выполняться над этими полями:
если некоторый метод монитора не может выполняться, пока не наступит некоторое событие, он выполняет операцию wait над некоторой условной переменной;
соответствующий процесс блокируется и становится неактивным;
другой процесс получает возможность войти в монитор, т.е. приступить к выполнению одного из его методов;
если активный процесс генерирует событие, которое ожидает процесс выполнивший операцию wait, то он инициирует операцию signal над той же самой условной переменной;
в результате один из ранее заблокированных на этой переменной процессов становится активным.
Слайд 107Комментарии
Взаимное исключение процессов обеспечивается выполнением требования, что внутри монитора может быть
активен только один процесс.
При выполнении метода signal для некоторой условной переменной, в мониторе может оказаться два процесса – разблокированный и выполнивший метод signal.
Для исключения такой ситуации метод signal должен предусматривать немедленный выход вызвавшего его процесса из монитора.
При выполнении метода signal для некоторой условной переменной, в мониторе может оказаться два процесса – разблокированный и выполнивший метод signal.
Для исключения такой ситуации метод signal должен предусматривать немедленный выход вызвавшего его процесса из монитора.
Слайд 108Сообщения. Определение
Под сообщением подразумевается порция структурированных данных, передаваемых средствами ОС
от одного процесса к другому.
Сообщения размещаются операционной системой во вспомогательную структуру данных, называемую очередью сообщений.
Для прямой и непрямой адресации достаточно двух примитивов, обеспечивающих передачу сообщений – send и receive.
В случае прямой адресации примитивы имеют следующий формат:
send(P, message) – послать сообщение message процессу P;
receive(Q, message) – получить сообщение message от процесса Q.
В случае непрямой адресации вместо P и Q указывается идентификатор промежуточного объекта хранения.
Сообщения размещаются операционной системой во вспомогательную структуру данных, называемую очередью сообщений.
Для прямой и непрямой адресации достаточно двух примитивов, обеспечивающих передачу сообщений – send и receive.
В случае прямой адресации примитивы имеют следующий формат:
send(P, message) – послать сообщение message процессу P;
receive(Q, message) – получить сообщение message от процесса Q.
В случае непрямой адресации вместо P и Q указывается идентификатор промежуточного объекта хранения.
Слайд 109Общие сведения
Сообщения могут применяться в качестве средства синхронизации процессов поскольку при
их реализации в рамках операционной системы предусмотрены внутренние механизмы, обеспечивающие:
взаимное исключение, гарантирующее невозможность чтения потребителем сообщения, запись которого производителем еще не завершена;
организацию очередности доступа процессов, подразумевающую блокировку процесса, пытающегося читать сообщение из пустой очереди а также процесса, пытающегося записать сообщение в полностью заполненную очередь.
Алгоритм решения проблемы производителя и потребителя с помощью сообщений основан на использовании ограниченного буфера, создаваемого перед началом работы программ:
буфер формируется потребителем в начале работы, путем посылки производителю N пустых сообщений;
производитель составляет сообщение и отсылает его потребителю;
потребитель, получив сообщение от производителя, извлекает его содержание и возвращает пустое сообщение.
взаимное исключение, гарантирующее невозможность чтения потребителем сообщения, запись которого производителем еще не завершена;
организацию очередности доступа процессов, подразумевающую блокировку процесса, пытающегося читать сообщение из пустой очереди а также процесса, пытающегося записать сообщение в полностью заполненную очередь.
Алгоритм решения проблемы производителя и потребителя с помощью сообщений основан на использовании ограниченного буфера, создаваемого перед началом работы программ:
буфер формируется потребителем в начале работы, путем посылки производителю N пустых сообщений;
производитель составляет сообщение и отсылает его потребителю;
потребитель, получив сообщение от производителя, извлекает его содержание и возвращает пустое сообщение.
Слайд 111Заключение
Рассмотренные средства ОС позволяют выполнить синхронизацию работы взаимодействующих процессов.
Любой из
примитивов позволяет реализовать остальные.
Слайд 113Разделяемые и закрепляемые ресурсы
В зависимости от метода организации доступа ресурсы можно
разделить на две категории: разделяемые и закрепляемые (выделенные).
К разделяемым относятся такие ресурсы, которые могут (условно) одновременно использоваться несколькими процессами, например, процессор, память, жесткие диски и т.д.
К закрепляемыми или выделенными ресурсам относятся такие ресурсы, которые должны отдаваться процессу в монопольное использование, например CD/DVD дисководы, принтеры и т.д.
Для монополизации ресурса он должен закрепляться за процессом средствами ОС.
Способность некоторого ресурса быть разделяемым в большей степени обусловлена порядком организации работы с этим ресурсом, а не его конструктивными особенностями, т.е. один и тот же ресурс может быть разделяемым в одной ОС и закрепляемым в другой.
К разделяемым относятся такие ресурсы, которые могут (условно) одновременно использоваться несколькими процессами, например, процессор, память, жесткие диски и т.д.
К закрепляемыми или выделенными ресурсам относятся такие ресурсы, которые должны отдаваться процессу в монопольное использование, например CD/DVD дисководы, принтеры и т.д.
Для монополизации ресурса он должен закрепляться за процессом средствами ОС.
Способность некоторого ресурса быть разделяемым в большей степени обусловлена порядком организации работы с этим ресурсом, а не его конструктивными особенностями, т.е. один и тот же ресурс может быть разделяемым в одной ОС и закрепляемым в другой.
Слайд 114Выгружаемые и невыгружаемые ресурсы
Процессы во время работы могут запрашивать и
освобождать требуемые ресурсы.
Если запрашиваемый ресурс занят, то возникает проблема перераспределения ресурсов между выполняющимися процессами.
Ресурс, который может быть забран у владеющего им процесса без нарушения его работоспособности и передан другому процессу, называется выгружаемым, например в многозадачных ОС к таким ресурсам относится процессор.
Ресурсы, которые нельзя забрать у владельца, не испортив результаты его работы, называются невыгружаемыми.
Разделение ресурсов на категории имеет смысл только в рамках конкретной операционной системы, например, если в системе не предусмотрено сохранение регистрового контекста процесса, то процессор будет невыгружаемым ресурсом.
Если запрашиваемый ресурс занят, то возникает проблема перераспределения ресурсов между выполняющимися процессами.
Ресурс, который может быть забран у владеющего им процесса без нарушения его работоспособности и передан другому процессу, называется выгружаемым, например в многозадачных ОС к таким ресурсам относится процессор.
Ресурсы, которые нельзя забрать у владельца, не испортив результаты его работы, называются невыгружаемыми.
Разделение ресурсов на категории имеет смысл только в рамках конкретной операционной системы, например, если в системе не предусмотрено сохранение регистрового контекста процесса, то процессор будет невыгружаемым ресурсом.
Слайд 115Понятие взаимоблокировки
Если ресурс недоступен, когда он требуется, и не может быть
перераспределен, то запрашивающий процесс должен ждать освобождения этого ресурса, оказываясь фактически в заблокированном состоянии.
В системе может быть несколько процессов, которым требуются одни и те же ресурсы.
Закрепление за процессами некоторых ресурсов может привести к ситуации, когда два или более процесса одновременно захватывают ресурсы, которые требуются каждому из них, причем ни один из них не имеет полный набор требуемых ресурсов.
В этом случае продолжение работы процессов невозможно и такая ситуация называется тупиком или взаимоблокировкой.
Взаимоблокировки обычно связаны с выделенными невыгружаемыми ресурсами.
Тупиковые ситуации, в которые вовлечены выгружаемые ресурсы, можно разрешить с помощью их перераспределения.
В системе может быть несколько процессов, которым требуются одни и те же ресурсы.
Закрепление за процессами некоторых ресурсов может привести к ситуации, когда два или более процесса одновременно захватывают ресурсы, которые требуются каждому из них, причем ни один из них не имеет полный набор требуемых ресурсов.
В этом случае продолжение работы процессов невозможно и такая ситуация называется тупиком или взаимоблокировкой.
Взаимоблокировки обычно связаны с выделенными невыгружаемыми ресурсами.
Тупиковые ситуации, в которые вовлечены выгружаемые ресурсы, можно разрешить с помощью их перераспределения.
Слайд 116Условия взаимоблокировки
Для возникновения ситуации взаимоблокировки должны выполняться четыре условия:
Условие взаимного
исключения: каждый ресурс в некоторый момент времени или отдан в монопольное использование ровно одному процессу или доступен.
Условие удержания и ожидания: процессы, которые в некоторый момент времени удерживают полученные ранее ресурсы, могут ожидать доступа к дополнительным ресурсам, закрепленным за другими процессам.
Условие отсутствия принудительной выгрузки ресурса: у процесса нельзя принудительно забрать ранее полученные ресурсы без нарушения его работоспособности.
Условие циклического ожидания: в системе должна существовать циклическая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Условие удержания и ожидания: процессы, которые в некоторый момент времени удерживают полученные ранее ресурсы, могут ожидать доступа к дополнительным ресурсам, закрепленным за другими процессам.
Условие отсутствия принудительной выгрузки ресурса: у процесса нельзя принудительно забрать ранее полученные ресурсы без нарушения его работоспособности.
Условие циклического ожидания: в системе должна существовать циклическая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Слайд 117Моделирование взаимоблокировок
Для моделирования взаимоблокировок, используются направленные графы, включающие два вида
узлов: процессы, обозначаемые кружками, и ресурсы, которые изображаются квадратами.
Ребро, направленное от ресурса к процессу, означает, что ресурс ранее был закреплен за процессом.
Ребро, направленное от процесса к ресурсу, означает, что процесс находится в состоянии ожидания доступа к этому ресурсу в данный момент блокирован.
Цикл в графе означает наличие взаимоблокировки, включающей процессы, ожидающие ресурсы и ресурсы, отданные в монопольное пользование процессам.
Ребро, направленное от ресурса к процессу, означает, что ресурс ранее был закреплен за процессом.
Ребро, направленное от процесса к ресурсу, означает, что процесс находится в состоянии ожидания доступа к этому ресурсу в данный момент блокирован.
Цикл в графе означает наличие взаимоблокировки, включающей процессы, ожидающие ресурсы и ресурсы, отданные в монопольное пользование процессам.
A
B
A
B
Запрос ресурса
Ресурс закреплен
Тупик
Слайд 118Основные направления борьбы с тупиками
Удовлетворительного решения проблемы взаимоблокировок в ОС
не существует в связи со сложностью данной задачи, обусловленной большим числом и разнообразием ресурсов, непредсказуемым и некорректным поведением пользователей и запущенных ими процессов.
Наиболее часто используются следующие основные направления борьбы с тупиками:
игнорирование данной проблемы (страусовый алгоритм);
обнаружение произошедших взаимоблокировок с последующим восстановлением работы системы;
динамическое избежание тупиков с помощью аккуратного распределения ресурсов;
предотвращение взаимоблокировок путем исключения возможности выполнения одного из условий, необходимых для их возникновения.
Наиболее часто используются следующие основные направления борьбы с тупиками:
игнорирование данной проблемы (страусовый алгоритм);
обнаружение произошедших взаимоблокировок с последующим восстановлением работы системы;
динамическое избежание тупиков с помощью аккуратного распределения ресурсов;
предотвращение взаимоблокировок путем исключения возможности выполнения одного из условий, необходимых для их возникновения.
Слайд 119Страусовый алгоритм
Самым простым подходом является страусовый алгоритм – игнорирование проблемы взаимоблокировок.
Основанием для его использования является:
борьба с взаимоблокировками требует значительных накладных расходов;
сбои в работе операционной системы, вызванные различными ошибками, могут возникать чаще чем взаимоблокировки;
одной из причин взаимоблокировок является дефицит ресурсов и с увеличением объема доступных ресурсов вероятность их возникновения снижается;
вероятность возникновения взаимоблокировок можно существенно понизить, если накладывать количественные ограничения на использование ресурсов каждым процессом.
В большинстве случаев не имеет смысла идти на снижение производительности системы для того, чтобы ликвидировать возможность взаимоблокировок .
Слайд 120Обнаружение и устранение взаимоблокировок
Решение проблемы обнаружения взаимоблокировок обычно сводится к
задаче поиска циклов в ориентированном графе.
При возникновении тупика:
строится граф, включающий все процессы и ресурсы;
выполняется поиск циклов в полученном графе;
составляется список процессов и ресурсов, участвующих в каждом цикле.
Выполняется попытка устранить взаимоблокировку.
Слайд 121Выход из взаимоблокировки
Восстановление при помощи принудительной выгрузки ресурса, т.е. у некоторого
процесса временно забирается ресурс, который требуется другому процессу, находящемуся в цикле.
Восстановление через откат с помощью созданной ранее контрольной точки.
Восстановление путем уничтожения процессов входящих в цикл, или удерживающих требуемые ресурсы.
Восстановление через откат с помощью созданной ранее контрольной точки.
Восстановление путем уничтожения процессов входящих в цикл, или удерживающих требуемые ресурсы.
Для выхода из взаимоблокировки используется один из следующих методов:
Слайд 122Исключение взаимоблокировок
Основные алгоритмы, позволяющие динамически предотвращать взаимоблокировки, базируются на концепции
безопасных состояний и используют информацию о наличии ресурсов и требованиях процессов.
Состояние считается безопасным, если оно не находится в тупике и существует некоторый порядок выделения ресурсов при котором каждый процесс может работать до завершения, даже если все процессы потребуют свое максимальное количество ресурсов.
Состояние считается безопасным, если оно не находится в тупике и существует некоторый порядок выделения ресурсов при котором каждый процесс может работать до завершения, даже если все процессы потребуют свое максимальное количество ресурсов.
Слайд 123Пример безопасного состояния
Пусть в системе имеется 10 экземпляров ресурса и три
процесса A, B C.
Известно максимальное количество ресурсов, требующееся каждому процессу, соответственно 9, 4 и 7.
Система находится в состоянии 1. Требуется проверить, является ли это состояние безопасным, т.е существует ли такая последовательность выделения ресурсов, что все процессы могут завершить свою работу.
Известно максимальное количество ресурсов, требующееся каждому процессу, соответственно 9, 4 и 7.
Система находится в состоянии 1. Требуется проверить, является ли это состояние безопасным, т.е существует ли такая последовательность выделения ресурсов, что все процессы могут завершить свою работу.
Слайд 124Пример небезопасного состояния
Пусть в системе имеется 10 экземпляров ресурса и три
процесса A, B C.
Максимальное количество ресурсов, требующееся каждому процессу, соответственно 9, 4 и 7.
Система находится в состоянии 1. Требуется проверить, останется ли это состояние безопасным после выделения процессу A одного экземпляра ресурса.
Максимальное количество ресурсов, требующееся каждому процессу, соответственно 9, 4 и 7.
Система находится в состоянии 1. Требуется проверить, останется ли это состояние безопасным после выделения процессу A одного экземпляра ресурса.
Слайд 125Алгоритм банкира
Алгоритм планирования, позволяющий избегать взаимоблокировок, носит название алгоритма банкира.
В рамках алгоритма проверяется, ведет ли выполнение каждого запроса к безопасному состоянию.
если выделение ресурса ведет к безопасному состоянию, то запрос удовлетворяется;
в противном случае запрос отклоняется.
На практике алгоритм банкира не применяется по следующим причинам:
обычно для процессов неизвестно максимальное количество ресурсов;
число процессов динамически изменяется, соответственно изменяются требования к объему ресурсов;
число ресурсов также может изменяться по разным причинам.
Слайд 126Нарушение условий возникновения взаимоблокировок
Нарушение условия взаимного исключения можно достичь, если
все устройства в системе будут разделяемые. Часто разделение реализуется путем закрепления устройства за одним управляющим процессом, который создает и обслуживает очередь запросов от других процессов.
Нарушение условия удержания и ожидания можно обеспечить:
если процесс будет запрашивать (и получать) все ресурсы до начала работы (исключается параллельная работа процессов, которым в разное время требуется одно устройство);
путем блокирования ресурсов в два этапа.
Нарушение условия отсутствия принудительной выгрузки ресурса обычно неприемлемо.
Нарушение условия циклического ожидания возможно, если ресурсы выделяются процессу упорядочено, например в порядке увеличения их номеров. Если процессу требуется ресурс с меньшим номером, чем у него уже есть, то он освобождает все ресурсы и пытается захватить их заново.
Нарушение условия удержания и ожидания можно обеспечить:
если процесс будет запрашивать (и получать) все ресурсы до начала работы (исключается параллельная работа процессов, которым в разное время требуется одно устройство);
путем блокирования ресурсов в два этапа.
Нарушение условия отсутствия принудительной выгрузки ресурса обычно неприемлемо.
Нарушение условия циклического ожидания возможно, если ресурсы выделяются процессу упорядочено, например в порядке увеличения их номеров. Если процессу требуется ресурс с меньшим номером, чем у него уже есть, то он освобождает все ресурсы и пытается захватить их заново.
Слайд 127Заключение
Полное решение проблемы взаимоблокировок в ОС возможно, однако не выполняется по
следующим причинам:
проблема не считается актуальной, поскольку взаимоблокировки возникают реже, чем другие сбой в системе;
алгоритмы решения проблемы слишком сложные и требуют наличия информации, которая обычно отсутствует;
большие накладные расходы, которые требуются для полного решения проблемы, снижают производительность ОС.
Основные методы борьбы с взаимоблокировками сводятся к уменьшению вероятности их возникновения за счет:
общего увеличения объема ресурсов;
ограничения числа ресурсов одного вида, выделяемых одному процессу;
организации разделения всех устройств, которые поддерживают такой режим работы.
проблема не считается актуальной, поскольку взаимоблокировки возникают реже, чем другие сбой в системе;
алгоритмы решения проблемы слишком сложные и требуют наличия информации, которая обычно отсутствует;
большие накладные расходы, которые требуются для полного решения проблемы, снижают производительность ОС.
Основные методы борьбы с взаимоблокировками сводятся к уменьшению вероятности их возникновения за счет:
общего увеличения объема ресурсов;
ограничения числа ресурсов одного вида, выделяемых одному процессу;
организации разделения всех устройств, которые поддерживают такой режим работы.
