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

Министерство  образования и  науки российской федерации

ГОСУДАРСТВЕННОГО  ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕРВИСА” 
 

Кафедра «Информационный и электронный  сервис» 
 

КОНТРОЛЬНАЯ РАБОТА

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

по  дисциплине: “Системное программное обеспечение ” 
 

                                                                 Выполнил: студент группы СвСЗз-3

                                                   Михеева Евгения Олеговна 

                                                              Проверил: к.т.н., доц. Шляпкин А.В.

. 
 
 
 

Сызрань   2011

Содержание

Введение……………………………………………………………………………………4

1. Понятие процесса и задачи……………………………………………………………..5

2.“Гарантия обслуживания”……………………………………………………………....8

3. Регистр-указатель задачи TR………………………………………………………….11

4. Режимы управления вводом/выводом………………………………………………..13

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

 реального  времени………………………………………………………………………16

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

семафоров Дейкстры……………………………………………………………………..18

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

8. QNX .Сетевой протокол FLEET……………………………………………………....24

Заключение……………………………………………………………………………….29

Список  использованной литературы…………………………………………………...30 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.Понятие процесса и задачи 

Процессом называется программа (приложение) в стадии выполнения. Каждый процесс имеет свое адресное пространство и проходит через ряд дискретных состояний:

-       процесс находится в состоянии выполнения, если в данный момент ему выделен центральный процессор;

-       процесс находится в состоянии готовности, если он мог бы сразу использовать центральный процессор;

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

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

Действия  системы:

·          Система создает списки готовых к выполнению и заблокированных процессов.

·          Список готовых процессов упорядочен по приоритету, т.е. существует очередь готовых процессов.

·          Список заблокированных процессов не упорядочен.

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

Для повышения  гибкости управления процессами в некоторых  системах вводят два дополнительных состояния:

-       приостановлен-заблокирован;

-       приостановлен-готов.

С помощью  этих состояний процессы временно исключаются  из списков готовых и заблокированных  процессов. 

Переход процесса из одного состояния в другое:

1.     В систему поступает задание.

2.     Система создает соответствующий процесс.

3.     Система устанавливает процесс в список (очередь) готовых процессов в соответствии с выделенным приоритетом.

4.     Происходит продвижение в очереди путем выборки процессов на выполнение, т.е. запуск (перевод процесса из состояния готовности в состояние выполнения).

5.     Если процесс занимает ЦП больше кванта времени (временной интервал, который ОС устанавливает в таймере прерываний), то таймер вырабатывает сигнал прерывания, по которому управление передается ОС и процесс переводится в список готовых процессов.

6.     Если процессу требуется выполнение операции ввода/вывода, он освобождает ЦП и блокируется (единственная смена состояния, инициируемая самим процессом).

7.     Заблокированный процесс переходит в состояние готовности после наступления события.

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

Основные  операции над процессами:

• Создание.
• Уничтожение.
• Приостановка.
• Возобновление.
• Изменение приоритета.
• Блокировка.
• Пробуждение.
• Запуск.

Каждая  операция может включать ряд стадий. Например, создание процесса состоит из:

-       присвоения имени;

-       включения имени в список;

-       определения начального приоритета;

-       формирования РСВ;

-       выделения начальных ресурсов.

Процесс может породить новый процесс. В  этом случае первый процесс называется предком, а второй - потомком. Каждый процесс-потомок имеет только одного предка, однако процесс-предок может создать несколько потомков. 

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

Сразу после запуска процесса создается  одна задача - главная задача процесса.

Выполнение  процесса может параллельно двигаться по нескольким путям.

Каждый  путь оформляется в виде самостоятельной задачи. Именно поэтому задачи еще называют потоками - Thread.

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

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

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

2.Гарантия  обслуживания 

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

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

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

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

Гарантировать обслуживание можно следующими тремя  способами:

• выделять минимальную долю процессорного времени некоторому классу процессов, если, по крайней мере, один из них готов к исполнению. Например, можно отводить 20 % от каждых 10 мс процессам реального времени, 40. % От каждых 2с — интерактивным процессам и 10 % от каждых 5 мин — пакетным (фоновым) процессам;
• выделять минимальную долю процессорного времени некоторому конкретному процессу, если он готов к выполнению;
• выделять столько процессорного времени некоторому процессу, чтобы он мог выполнить свои вычисления к сроку.

Для сравнения  алгоритмов диспетчеризации обычно используются следующие критерии:

Использование (загрузка) центрального процессора (CPU utilization). В большинстве персональных систем средняя загрузка процессора не превышает 2-3 %, доходя в моменты выполнения сложных вычислений и до 100 %. В серверах, загрузка процессора колеблется в пределах 15-40 % для легко загруженного процессора и до 90-100 % — для сильно загруженного процессора.

• Пропускная способность (CPU throughput). Может измеряться количеством процессов, которые выполняются в единицу времени.
• Время оборота (turnaround time). Интервал от момента появления процесса во входной очереди до момента его завершения. Включает время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода/вывода.
• Время ожидания (waiting time). Под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов.
• Время отклика (response time). Для интерактивных программ важным показателем является время отклика или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу.

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

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

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

В случае использования мультипроцессорных систем применяются следующие методы повышения производительности системы:

• совместное  планирование, при котором все  потоки одного приложения (неблокированные) одновременно выбираются для выполнения процессорами и одновременно снимаются с них (для сокращения переключений контекста);

• планирование, при котором находящиеся в  критической секции задачи не прерываются, а активно ожидающие входа  в критическую секцию задачи не выбираются до тех пор, пока вход в секцию не освободится;
• планирование с учетом так называемых «советов» программы (во время ее выполнения).

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 — увеличивать). Классическое определение этих операций выглядит следующим образом: