Алгоритмы и механизмы синхронизации процессов в операционных системах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
>
Рис. 4. Влияние относительных скоростей потоков на результат решения задачи
1.8 Проблема взаимного исключения
Хотя каждая задача в системе, как правило, выполняет какую-либо отдельную функцию, часто возникает необходимость в согласовании (синхронизации) действий, выполняемых различными задачами. В частности, такая синхронизация необходима, если требуется упорядочить доступ нескольких задач к разделяемому ресурсу.
Ресурс - это общий термин, описывающий физическое устройство или область памяти, которые могут запрашиваться для использования несколькими задачами. Если ресурс может быть использован одновременно несколькими задачами, то он называется разделяемым. Если в данный момент времени ресурс может быть использован только одной задачей, то он является неразделяемым. Неразделяемый ресурс называется критическим.
Неразделение ресурсов происходит по одной из следующих причин:
.Физическая природа ресурса делает невозможным его разделение: типичный пример - принтер: невозможно переключить его между печатью листов различных процессов.
2.Ресурс таков, что если он используется несколькими процессами одновременно, то действие одного процесса может взаимодействовать с действиями другого. Например, область памяти содержит переменные, доступные для более чем одного процесса: если один процесс проверяет переменные, в то время как другой модифицирует их, то результат будет непредсказуем и обычно гибелен. Неразделяемые ресурсы включают в себя большинство периферийных устройств, доступных для записи файлов, и области данных, являющихся предметом модификации.
Проблема взаимного исключения состоит в том, чтобы обеспечить доступ к неразделяемым ресурсам в некоторый момент времени только одному процессу. Способ взаимодействия, при котором во время обращения одной задачи к неразделяемому ресурсу всем другим задачам это запрещается, называется взаимоисключением. Неразделяемые ресурсы, будь то периферия, файлы или данные в памяти, могут быть защищены от одновременного доступа путем принятия предварительных мер от одновременного выполнения процессами участков программ, которые этот доступ осуществляют. Эти участки программ называются критическими секциями. Когда задача работает с неразделяемым ресурсом, то говорят, что она находится в своей критической секции (или в своем критическом участке). Взаимные исключения в использовании ресурсов эквивалентны взаимному исключению выполнения этих критических секций: если одна задача находится в своей критической секции, необходимо исключить возможность вхождения для всех других задач в их критические секции. Таким образом, критическая секция является частью процесса, которая должна выполняться без прерывания со стороны других процессов, в результате чего и происходит исключение одного процесса другим. Например, процессы могут быть взаимоисключающими от доступа к таблице данных, если все подпрограммы, читающие или обновляющие таблицу, написаны как критические секции так, что только одна подпрограмма может выполняться в данное время.
Когда какой-либо процесс находится в своем критическом участке, другие процессы могут, конечно, продолжать выполнение, но без входа в их критические участки. Когда процесс выходит из своего критического участка, то одному из остальных процессов, ожидающих входа в свои критические участки, должно быть разрешено продолжить работу (если в этот момент действительно есть процесс в состоянии ожидания).
Когда процесс находится в своем критическом участке, это его ко многому обязывает. В этом особом режиме процесс имеет исключительное право доступа к разделяемым данным, а всем остальным процессам, которым в то же самое время требуется доступ к этим данным, приходится ждать. Поэтому процессы должны как можно быстрее проходить свои критические участки и не должны в этот период блокироваться, так что критические участки необходимо кодировать очень тщательно (чтобы, например, не допустить возможности зацикливания внутри критического участка).
Если процесс, находящийся в своем критическом участке, завершается, либо естественным, либо аварийным путем, то операционная система при выполнении служебных функций по завершению процессов должна отменить режим взаимоисключения, с тем чтобы другие процессы получили возможность входить в свои критические участки.
Обеспечение взаимоисключения является одной из ключевых проблем параллельного программирования.
Механизмы взаимоисключения должны обеспечивать:
целостность структур разделяемых данных;
отсутствием взаимных блокировок задач;
отсутствие тупиков.
Две (или более) задачи находятся в состоянии взаимоблокировки, если одна задача удерживает ресурс, запрашиваемый другой задачей, в то время как ей самой требуется ресурс, удерживаемый этой другой задачей. Процесс находится в состоянии тупика, если он ожидает некоторого события, которое никогда не произойдет.
Одним из классических средств обеспечения целостности разделяемых данных при обращении к неразделяемому ресурсу является механизм семафоров. Семафоры не допускают выполнения некоторого участка кода несколькими задачами одновременно. Самый простой семафор - замок (lock) или mutex (от английского mutually exclusive, взаимоисключающий). Для того чтобы задача могла выполнить критический участок кода, она должна сначала захватить замок. После захвата замка задача в