Взаимоблокировка процессов
Взаимодействие процессов
Совместно выполняемые процессы могут быть либо независимыми либо взаимодействующими. Взаимодействие процессов часто понимается в смысле взаимного обмена данными через общий буфер данных. Взаимодействие удобно рассматривать в схеме производитель – потребитель. Для взаимодействия процесса - производителя и процесса - потребителя создается совместный буфер, заполняемый этими процессами. Буфер имеет фиксированные размеры, и следовательно, процессы могут находиться в состоянии ожидания, когда:
1. Буфер заполнен – ожидает процесс – производитель;
2. Буфер пуст – ожидает процесс – потребитель.
Буфер может предоставляться и поддерживаться самой ОС, например с помощью средств межпроцессорной коммуникации, либо должен быть организован прикладным программистом. При этом оба процесса используют общий участок памяти.
Взаимодействие заключается в передаче данных между процессами или совместном использовании некоторых ресурсов и обычно реализуется с помощью таких механизмов как транспортеры, очереди, сигналы, семафоры.
Транспортеры (каналы). Являются средством взаимодействия родственных процессов, представляют собой область памяти, имеющую файловую организацию, для которой обеспечивается запись и считывание данных в транспортере. Реализуется очередь обслуживания. Порядок записи данных на транспортер неизменен, не допускается повторное считывание данных. Обмен данными происходит не непосредственно а через транспортер. Из вызвавшего процесса задается размер транспортера. Дочерние процессы могут использовать родительский транспортер.
Очереди. Эти механизмы могут обеспечить передачу или использование общих данных без перемещения данных, а с передачей элемента очереди, содержащего указатель данных, и объем массива данных. Очередь используется вместе с механизмом общей памяти. Элемент очереди может быть считан с уничтожением или без уничтожения этого элемента. Чтение элемента может осуществляться в соответствии с механизмом очереди или стека. Чтение элементов очереди осуществляет только создающий очереди процесс, все другие процессы могут только записать элементы в очередь. Создающий процесс может выполнить следующие действия над очередью: создание просмотр, чтение, закрытие. Записывающий процесс может осуществлять действия: открыть, записать, закрыть.
Имя очереди, которое присваивается создающим процессом, имеет вид полной спецификации файла. Ожидание элементов в очереди организуется с помощью семафора, сигнализирующего о записи элемента в очередь. Для работы с очередью определены такие дополнительные функции:
1. Определение количества элементов в очереди в текущий момент;
2. Очистка очереди создавшим его процессом.
Сигналы. Сигнал является механизмом передачи требования от одного процесса к другому на немедленное выполнение действия. Обработчик сигнала создается процессом и помещается в начале первого потока процесса. Является аналогом обработки прерывания. При передачи управления обработчику передается адрес возврата и тип принятого сигнала. Процесс посылающий сигнал типа «флаг», может передать дополнительную информацию обработчику сигнала. Характер выполняемых действий при возникновении сигнала: обработка системной ошибки при появлении сигнала, блокирование сигнала, передача управления подпрограмме.
Семафоры. Являются механизмами передачи сообщений от одного потока к другому о наступлении некоторого события. Различают семафоры системные и оперативной памяти. Семафоры оперативной памяти – двойное слово в памяти системы, его описатель – адрес места в памяти. Такие семафоры не создаются и не открываются, а устанавливаются в определенное состояние. Процессы, использующие семафоры оперативной памяти, должны иметь доступ к соответствующему сегменту памяти. ОС такие семафоры не обслуживает и не сообщает об их освобождении или захвате. ОС контролирует завершение каждого процесса, владеющего системным семафором, и освобождает его для процессов.
Если семафор освобождается всеми использующими его процессами то он удаляется из системы.
Управление семафором реализуется с помощью функция:
1. Установка семафора с целью сигнализации
2. Ожидание вызывающим потоком, пока семафор не будет выключен
3. Ожидания потоком выключения одного из нескольких семафоров
Стратегии планирования процессора
- Первый пришел – первый обслуживается, FCFS (first come first served). Является наиболее простой стратегией планирования процессоров и заключается в том, что процессор передается тому процессу, который раньше других его запросил.
Стратегии FCFS присущ «эффект конвоя». В том случае когда в компьютере имеется один большой процесс и несколько малых, то все процессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию. Т.о. «эффект конвоя» приводит к снижению загруженности как ЦП так и ПУ
- Стратегия «наиболее короткая работа выполняется первой», SJF-Shortest Job First. Является одним из методов борьбы с «эффектом конвоя», позволяет процессу из очереди выполниться первым. SJF часто применяется в долгосрочных планировщиках, обслуживающих пакетный режим.
- Приоритетное планирование. Эта стратегия предполагает, что каждому процессу приписывается приоритет, определяющий очередность предоставления ему ЦП. Обычно приоритет это целое положительное число находящееся в некотором диапазоне. Приоритеты назначаются исходя из совокупности внутренних и внешних по отношению ос факторов. Внутренние факторы: требование к памяти, количество открытых файлов, отношение среднего времени в/в к среднему времени использования ресурсов ЦП и т.д. Внешние факторы: важность процесса и т.д. Недостаток этой стратегии заключается в блокировании на неопределенное время низкоприоритетных процессов.
- Карусельная стратегия. RR Round Robin – применяется в системах разделения времени. Определяется отрезок времени названный квантом времени. Очередь готовых процессов рассматривается как кольцевая. Процессы циклически перемещаются по очереди, получая ЦП на время равное кванту. Новый процесс добавляется в хвост очереди. Если процесс не завершился в определенный ему квант времени, то его работа принудительно прерывается, и он перемещается в хвост очереди.
- Планирование с использованием многоуровневой очереди. Эта стратегия разработана для ситуации, когда процессы могут быть классифицированы на несколько групп, например часто процессы разделяют на две группы: интерактивные (процессы переднего плана) и пакетные (фоновые). Интерактивные и пакетные процессы имеют различные требования к краткосрочному планировщику, например по отношению ко времени отклика. Стратегия многоуровневой очереди разделяют очередь готовых процессов на несколько очередей, в каждой из которых находятся процессы с одинаковыми свойствами, и каждый из которых может планироваться индивидуальной стратегией, например RR стратегия для интерактивных процессов и FCFS для пакетных процессов. Взаимодействие очередей осуществляется по следующим правилам: ни один процесс с более низким приоритетом не может быть запущен, пока не выполнятся процессы во всех очередях с более высоким приоритетом. Работа процесса из очереди с более низким приоритетом может быть приостановлена, если в одной из очередей с более высоким приоритетом появился процесс.
- Использование многоуровневой очереди с обратными связями. Она предполагает, что процессы при определенных условиях могут перемещаться между очередями. Недостаток заключается в затратах времени на перемещение процессов из одной очереди в другую.
Взаимоблокировка процессов
Взаимоблокировка процессов может происходить, когда несколько процессов борются за один ресурс.
Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.
Выгружаемый ресурс- это ресурс который можно забрать у процесса без потери данных (например: память).
Невыгружаемый ресурс -это ресурс который нельзя забрать у процесса без потери данных (например: принтер).
Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы.