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

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

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

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

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

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

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

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

 

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

                                                                 Выполнил: студент группы СвСЗз-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). Для интерактивных программ важным показателем является время отклика или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу.

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

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

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

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

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

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