Алгоритм решения задачи «поставщик – потребитель» при использовании семафоров Дейкстры

P(S): пока S == 0 процесс  блокируется;  
S = S – 1;  
V(S): S = S + 1;

Эта запись означает следующее: при выполнении операции P над семафором S сначала  проверяется его значение. Если оно  больше 0, то из S вычитается 1. Если оно  меньше или равно 0, то процесс блокируется  до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При  выполнении операции V над семафором S к его значению просто прибавляется 1.

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

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

Возьмем три семафора empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появится информация.

 Семафор  empty будем использовать для организации  ожидания производителя при заполненном  буфере, а семафор mutex - для организации  взаимоисключения на критических  участках, которыми являются действия put_item и get_item (операции положить  информацию и взять информацию не могут пересекаться, так как тогда возникнет опасность искажения информации).

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

7.  Обход тупика. Алгоритм  банкира Дейкстры.

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

• предотвращение тупиков;
• обход тупиков;
• обнаружение тупиков;
• восстановление после тупиков.

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

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

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

  Цель  средств обнаружения тупиков  — установить сам факт возникновения  тупиковой ситуации, причем точно  определить те процессы и ресурсы, которые  оказались вовлеченными в данную тупиковую ситуацию. После того как все это сделано, данную тупиковую ситуацию в системе можно будет устранить.

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

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

  Хавендер (Hv68) показал, что возникновение тупика невозможно, если нарушено, хотя бы одно из указанных выше четырех необходимых условий. Он предложил следующую стратегию.

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

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

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

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

  Когда при описании алгоритма банкира  мы будем говорить о ресурсах, мы будем подразумевать ресурсы  одного и того же типа, однако этот алгоритм можно легко распространить на пулы ресурсов нескольких различных типов. Рассмотрим, например, проблему распределения  некоторого количества t идентичных лентопротяжных устройств.  

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

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

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

Предположим теперь, что работают n пользователей.

Пусть l(i) представляет текущее количество лентопротяжных устройств, выделенных i пользователю. Если, например, пользователю 5 выделены четыре устройства, то l(5)=4. Пусть т(i) — максимальная потребность пользователя i, так что если пользователь 3 имеет максимальную потребность в двух устройствах, то m(3)=2. Пусть c(t) — текущая потребность пользователя, равная его максимальной потребности минус текущее число выделенных ему ресурсов. Если, например, пользователь 7 имеет максимальную потребность в шести лентопротяжных устройствах, а текущее количество выделенных ему устройств составляет четыре, то мы получаем

с (7)=m (7) - 1(7)=6 - 4=2.

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

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

8. QNX

QNX — это операционная система реального времени для персональных компьютеров, позволяющая эффективно организовать распределенные вычисления. В системе реализована концепция связи между задачами на основе сообщений, посылаемых от одной задачи к другой, причем задачи эти могут решаться как на одном и том же компьютере, так и на разных, но связанных между собой локальной вычислительной сетью. Реальное время и концепция связи между процессами посредством сообщений оказывают решающее влияние и на разрабатываемое для операционной системы QNX программное обеспечение, и на программиста, стремящегося с максимальной выгодой использовать преимущества системы. Микроядро операционной системы QNX имеет объем всего в несколько десятков килобайтов (в одной из версий — 10 Кбайт, в другой — менее 32 Кбайт, хотя есть вариант и на 46 Кбайт), то есть это одно из самых маленьких ядер среди всех существующих операционных систем. В этом объеме помещаются:

механизм  передачи сообщений между процессами IPC (Inter Process Communication — взаимодействие между процессами);

 Редиректор (redirector) прерываний;     

 блок планирования выполнения задач (иначе говоря, диспетчер задач);   

 сетевой интерфейс для перенаправления сообщений (менеджер Net). Механизм IPC обеспечивает, пересылку сообщений между процессами и является одной из важнейших частей операционной системы, так как все взаимодействие между процессами, в том числе и системными, происходит через сообщения. Сообщение в операционной системе QNX — это последовательность байтов произвольной длины (0-65 535 байт) произвольного формата. Протокол обмена сообщениями может выглядеть, например, таким образом. Задача блокируется для ожидания сообщения. Другая задача посылает первой сообщение и при этом блокируется сама, ожидая ответа. Первая задача деблокируется, обрабатывает сообщение и отвечает, деблокируя вторую задачу.

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

Кроме того, становится меньше пересылок из памяти в память, что разгружает процессор. Особенностью процесса передачи сообщений является то, что в сети, состоящей из нескольких компьютеров, работающих под управлением QNX, сообщения могут прозрачно передаваться процессам, выполняющимся на любом из узлов. Определены в QNX еще и два дополнительных метода передачи сообщений — метод представителей (proxy) и метод сигналов (signal).

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