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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3.Микропроцессоры i80x86 TR (Task Register)

TR (Task Register) - это 16-разрядный системный регистр,  который хранит селектор дескриптора  TSS текущей задачи. Этот регистр  также имеет теневую 64-разрядную  компоненту, используемую только  самим процессором, в которой  хранится содержимое дескриптора  TSS текущей задачи - это повышает  производительность процессора.  
        Когда происходит переключение со старой задачи на новую, процессор помещает в TSS новой задачи в поле Link содержимое регистра TR и таким образом обеспечивает связь в со старой задачей. После загрузки значений из TSS новой задачи, в регистр TR процессор записывает селектор дескриптора TSS этой новой задачи.  
        Для загрузки значения в регистр TR используется команда LTR, единственным операндом которой служит 16-разрядный регистр общего назначения или переменная в памяти. Для чтения значения из этого регистра используется команда STR, которая также имеет один операнд - 16-разрядный регистр общего назначения или переменную в памяти.  
        Команда LTR относится к привилегированным командам - она может выполняться только на нулевом уровне привилегий. Команду STR можно выполнить на любом уровне привилегий, так что любая программа или задача может прочитать значение этого регистра. Это может показаться странным - процессор позволяет прикладным задачам считывать "конфиденциальную" информацию - селектор дескриптора TSS, однако, на самом деле, информации значение TR программе не даёт, потому что в этом регистре находится селектор дескриптора TSS текущей задачи и задача ничего с этим сделать не сможет - переключения на саму себя запрещены.  

       Регистр TR имеет, в основном, два применения:

 

16-разрядный  регистр задачи (Task Register, TR) указывает на дескриптор в глобальной таблице дескрипторов, который позволяет получить доступ к дескриптору сегмента состояния задачи (Task State Segment, TSS) — информационной структуре, которую поддерживает микропроцессор для управления задачами; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. Режимы ввода вывода 

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

     Любые операции ввода-вывода являются привилегированными и выполняются только под управление ОС. Для этого в большинстве  процессоров организуется режим  супервизора (выполнение команд ввода-вывода разрешено) и пользователя (выполнение команд ввода-вывода запрещено, а попытка  ввода-вывода продолжает исключительную ситуацию).

     Устройства  ввода-вывода (УВВ) делятся на разделяемые (посредством механизма прямого  доступа НМД, CD-ROM) и неразделяемые (посредством механизма последовательного  доступа принтер, НМЛ).

     Роль  ОС в общении задач с УВВ  определяется тремя причинами:

– необходимость  разрешения конфликтов между задачами, которые обращаются к УВВ;

– необходимость  более эффективного использования  ресурсов (например, чтение данных с  жесткого диска в последовательности, которая дает минимальное перемещение  головок);

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

     Супервизор  ввода-вывода (компонент ОС, отвечающий за управление вводом-выводом) выполняет  следующие задачи:

– получение  запросов ввода-вывода от прикладных задач  и программных модулей ОС и  проверяет их на корректность;

– планирование ввода-вывода (определение очерёдности  предоставления ресурсов);

– инициация  операций ввода-вывода (передачу управления соответственному драйверу);

– приём  сигналов прерываний от УВВ, их идентификация  и передача управления соответствующей  программе обработки прерываний;

– передача сообщений об ошибках;

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

Существует  два режима ввода-вывода: обмен с опросом готовности и обмен по прерываниям. Общая структура управления вводом-выводом представлена на рис. 23.

  

Рис. 1. Управление вводом-выводом

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

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

 «проверить  наличие сигнала готовности». 

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

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

Еще одним  способом организации управления операциями обмена являются использование вытесняющей мультизадачности (например, Windows NT). При этом драйвер печати через параллельный порт работает в режиме опроса готовности, что даёт стопроцентную загрузку ЦП, а вытесняющая мультизадачность время от времени прерывает процесс управления печатью и передаёт процессор другим задачам.    
 
 
 
 
 
 
 
 
 

5. Основные требования, предъявляемые к операционным системам реального времени.

ОСРВ  должна быть многозадачной (или  многопоточной).  
Программное обеспечение СРВ представляет собой фиксированный набор заранее разработанных модулей, а выбор программы на выполнение осуществляется по прерываниям (исходя из текущего состояния объекта) или в соответствии с расписанием плановых работ. Подробнее о планировании ОСРВ в главе 4 данного пособия.

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

Должен  существовать механизм наследования приоритетов.  
В многозадачной СРВ необходимость разделения ресурсов, комбинация приоритетов потоков могут привести к таким проблемам, как инверсия приоритетов (priority inversion) и смертельный захват (deadlock) . 
Инверсия приоритетов – это ситуация, в которой, управление получает не та ветвь исполнения, которая должна была бы получить из соображений приоритетности, а другая, с более низким приоритетом, в результате нарушается детерминированность и прогнозируемость системы.  
Для примера рассмотрим систему с 3 потоками управления: Т1, Т2, Т3 , причём их приоритеты: T1 < T2 < T3 . Пусть потоки активируются по некоторым событиям в следующей временной последовательности: T1, T2, T3 . Если T1 захватывает некоторый монопольный ресурс, который требуется так же и T3 , и не успевает освободить его до активации Т2 , то происходит следующее:  

1.   - T1 не выполняется, потому, что он вытеснен T2 (в виду приоритетности);
2. - T3 не выполняется, потому, что ожидает ресурс, захваченный T1 ;

  - T2 выполняется ... вплоть до бесконечно долго.

Но  T2 в данном примере не является потоком, подлежащим немедленному исполнению. Самый высокоприоритетный - T3 , его назначение – своевременная реакция на событие, оно не только не обработается в гарантированное время, но и вообще гарантировано не обработается.  
Чтобы устранить такие инверсии, ОСРВ должна допускать наследование приоритета: нужно динамически повысить приоритет блокирующего потока ( Т1 в рассмотренном примере) до значения максимального приоритета всех тех потоков, которые ожидают освобождения заблокированного ресурса ( Т3 в рассмотренном примере). После освобождения ресурса тут же вернуть приоритет к его исходному статическому уровню. При этом «задерживающий всех» поток быстро пройдет критическую секцию на максимальном приоритете тех, кого он «задерживает». Наследование означает, что блокирующий ресурс поток наследует приоритет потока, который он блокирует.

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

Поведение ОСРВ должно быть Предсказуемо.  
Поведение ОС должно быть известно и достаточно точно прогнозируемо. Времена в

ыполнения системных  вызовов, временные характеристики поведения системы в 

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

6. Семафоры. Задача производитель – потребитель

Одним из первых механизмов, предложенных для  синхронизации поведения процессов, стали семафоры, концепцию которых  описал Дейкстра (Dijkstra) в 1965 году.

Семафор представляет собой целую переменную, принимающую  неотрицательные значения, доступ любого процесса к которой, за исключением  момента ее инициализации, может  осуществляться только через две  атомарные операции: P (от датского слова proberen — проверять) и V (от verhogen — увеличивать). Классическое определение этих операций выглядит следующим образом: