Диспетчеризация пассажирских перевозок

        Новосибирский  государственный технический университет

НГТУ

Кафедра ВТ            

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                 Курсовая работа

по дисциплине «Системное программное обеспечение»

раздел «Организация вычислительных процессов»

 

 

 

 

 

 

 

 

Факультет: АВТ

Группа: АМ-015

Студент: Акулов Е.О.

Преподаватель: Коршикова Л. А.

 

 

 

 

 

 

 

 

 

 

 

 

 

Новосибирск, 2003г

                                                 Содержание

Введение в предметную область                                                               3

1. Диспетчеризация задач                                                                          4

1.1 Теоретические основы  диспетчеризации                                      4

1.2 Исходные данные  и временные диаграммы диспетчеризации   8

1.3 Временная диаграмма  планирования верхнего уровня               11

1.4 Выводы                                                                                             12    

 

2. Синхронизация процессов                                                                     13

2.1 Теоретическое положение  управления процессами                    13

2.2 Исходная таблица семафорных  операций                                    18

2.3 Временная диаграмма семафорных  операций                             19

2.4 Временная диаграмма диспетчеризации  задач                            20

2.5 Анализ ситуаций и выводы                                                            22

Заключение                                                                                                 23

Список литературы                                                                                    24

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение в предметную область

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

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

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

 

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

 

 

        

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Диспетчеризация задач

1.1 Теоретические основы диспетчеризации

 Общие сведения о диспетчеризации.

       Планирование распределения процессора производится на нескольких

уровнях. Один из них - средний  уровень планирования -

диспетчеризация.  На этом уровне диспетчер задач (планировщик

процессов) выбирает одну задачу из числа готовых к выполнению и

предоставляет ей процессор.  Каждая задача занимает процессор

относительно малое  время (как правило, недостаточное  для выполнения

задачи), затем диспетчирирование  повторяется, процессор выделяется

другой задаче. Диспетчер  принимает текущие решения в  динамике

сложившейся конкретной обстановки.

    Таким образом,  цели диспетчирирования задач следующие:

     - распределение  центрального процессора в динамике  в соответствии

       с  критериями;

     - эффективная  отработка алгоритмов управления  задачами.

     - сбалансированное использование ресурсов.

     - баланс  между временем ответа и коэффициентом  использования ресурсов.

 

Итак: диспетчер - это программа, которая выбирает задачи (процессы)

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

передает их на обработку центральному процессору.

 Модель "Диспетчеризация задач".

                                     

                    

 

 

 

 

    Рис.1. Структурная схема модели

    Описание модели.

 

    Выделено три  основных блока ЭВМ:

 

    - генератор ( GEN );

    - супервизор ( SV );

    - центральный  процессор ( CPU ).

 

Взаимодействие этих блоков и обеспечивает обработку  задач (процессов).

 

 

Замечание: в модели ведется  отсчет времени относительно модельного времени

   главных часов  ( TM ). Наряду с ТМ вводятся понятия:

 

    TSV   - время работы SV;

    TGEN  - время работы GEN;

    TCPU  - время работы CPU над проблемной задачей (квант времени);

    TTGEN - квант времени, по истечении которого блок генератора

   должен вступить  в работу;

    OST   - остаток от кванта времени, отпущенного процессору

  для работы над  задачей. ( ВРемя ДОРаботки)

 

Блоком GEN формируются основные параметры задачи: номер задачи,

приоритет, трудоемкость, время поступления в систему  следующей

задачи. Эти параметры формируются, исходя из максимально заданных

значений входных величин  генератора случайных чисел. Блок

генератора вступает в работу по истечении TTGEN, при этом текущая

работа прерывается  и возобновляется после постановки вновь

поступившей задачи в  очередь на обработку.

 

             Блок SV выполняет роль диспетчера задач.

                     Порядок работы модели.

1. Супервизор ожидает  поступления в систему хотя-бы  одной задачи.

2. После поступления  задачи в систему ей выделяется  квант

   процессорного времени. По истечении которого вновь будет запущен

   супервизор.

3. При очередном запуске  супервизора происходит вызов  планировщика

   заданий.

4. Пункты 2 и 3 повторяются  до тех пор, пока задача не  отработает

   отведенное ей  время целиком.

 

5. Через некоторые промежутки времени запускается генератор новой

   задачи. При этом  происходит запоминание текущего  состояния

   системы. Генерация  новой задачи. Вызов планировщика  заданий.

   Возврат в запомненное  состояние.

6. Весь процесс повторяется  пока не будут выполнены все задачи.

    Оценка качества обслуживания очереди задач.

 

   Выбор заявок  из очереди производится по  правилу, которое называется

дисциплиной обслуживания. Обслуживание заявок в общем случае носит

стохастический характер, т.е. время обслуживания t обсл.(TR) различное.

    На основе  системы массового обслуживания  время пребывания задачи

в системе определяется как составляющая времени ожидания и времени

обслуживания (трудоемкости).

 

  Предъявляются следующие  требования:

  а) для всех задач  время ожидания (tож - TO) должно быть равномерным;

  б) трудоемкость (TR) дисциплины обслуживания должна быть минимальной.

 

    Дисциплины диспетчеризации задач.

 

    1.FIFO - "первым пришел - первым выбран на обслуживание".

             Время обслуживания заявки равно ее трудоемкости.

    2.LIFO - "последним пришел - первым выбран на обслуживание".

     Время обработки  самой последней задачи аналогично FIFO.

    3.RR   - "круговорот". Отличается от FIFO лишь временем обслуживания:

     каждая заявка получает определенный квант времени (одинаковый

     для всех).

    4.PRT  - выбор заявок на обслуживание по приоритету. Более приоритетной

     заявке соответствует  меньшее число.

    5.RAND - случайный выбор заявки из очереди.

    6.SJF  - выбор заявки на обслуживание с минимальной трудоемкостью.

 

    О качестве дисциплины  можно судить по среднему времени  обслуживания

(STO).

    Из теории очередей  известна зависимость TO от TR (времени ожидания

от времени обслуживания задачи). Она представлена на рис.2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

    Рис.2.График качества  обслуживания

 

    w - среднее время ожидания (STO);

   V - средняя длительность заявок.

 

    Следующим  параметром качества обслуживания (кроме STO, TR, TO) является

параметр загрузки процессора ZCP. Он зависит от дисциплин диспетчеризации

и выражается в процентном отношении:

 

    ZCP=100*(STR/TM) , где

 

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

    TM - модельное время. (имеется ввиду время выполнения всех

 задач. Т начала 1ой задачи - Т окончания последней. )

 

 

1.2 Исходные данные и  временные диаграммы диспетчеризации

Табл№1 Задачи диспетчеризации

 

№Задачи	PRT	T
1	24	77
2	15	61
3	64	11
4	70	29
5	44	63
6	17	23
7	61	8
8	31	29
9	48	12
10	38	58

 

Протокол работы системы:

 

0 Стартовал супервизор

0 Поступила задача N1

10 Запустилась задача N1

25 Завершена задача N1

25 Стартовал супервизор

25 Поступила задача N 2

35 Запустилась задача N1

40 Завершена задача N1

40 Стартовал супервизор

40 Поступила задача N 3

50 Запустилась задача N1

55 Завершена задача N1

55 Стартовал супервизор

55 Поступила задача N 4

65 Запустилась задача N1

73 Завершена задача N1

73 Стартовал супервизор

73 Поступила задача N 5

83 Запустилась задача N1

96 Завершена задача N1

96 Стартовал супервизор

96 Поступила задача N 6

106 Запустилась задача N1

107 Завершена задача N1

107 Стартовал супервизор

107 Поступила задача N 7

117 Запустилась задача N1

132 Завершена задача N1

132 Стартовал супервизор

132 Поступила задача N 8

142 Запустилась задача N1

157 Завершена задача N1

157 Стартовал супервизор

157 Задача N1 вышла из системы

167 Запустилась задача N2

170 Завершена задача N2

170 Стартовал супервизор

170 Поступила задача N 9

180 Запустилась задача N2

195 Завершена задача N2

195 Стартовал супервизор

195 Поступила задача N 10

205 Запустилась задача N2

254 Завершена задача N2

254 Стартовал супервизор

254 Задача N2 вышла из системы

264 Запустилась задача N3

275 Завершена задача N3

275 Стартовал супервизор

275 Задача N3 вышла из системы

285 Запустилась задача N4

314 Завершена задача N4

314 Стартовал супервизор

314 Задача N4 вышла из системы

324 Запустилась задача N5

387 Завершена задача N5

387 Стартовал супервизор

387 Завершена задача N5

397 Запустилась задача N6

420 Завершена задача N6

420 Стартовал супервизор

420 Задача N6 вышла из системы

430 Запустилась задача N7

438 Завершена задача N7

438 Стартовал супервизор

438 Задача N7 вышла из системы

448 Запустилась задача N8

477 Завершена задача N8

477 Стартовал супервизор

477 Задача N8 вышла из системы

487 Запустилась задача N9

499 Завершена задача N9

499 Стартовал супервизор

499 Задача N9 вышла из системы

509 Запустилась задача N10

567 Завершена задача N10

567 Стартовал супервизор

567 Задача N10 вышла из системы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.3 Временная диаграмма  диспетчеризации задач

 

1.3 Временная диаграмма планирования  верхнего уровня

 

Рис. 4 Временная диаграмма планирования верхнего уровня по FIFO для

однопрограммного режима.

 

 

 

 

 

1.4 Выводы

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

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Синхронизация процессов

2.1 Теоретическое положение управления процессами

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

Состояние процессов

В многозадачной (многопроцессной) системе процесс может находиться в одном из трех основных состояний:

- ВЫПОЛНЕНИЕ - активное  состояние процесса, во время  которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

- ОЖИДАНИЕ - пассивное  состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

- ГОТОВНОСТЬ - также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

В ходе жизненного цикла  каждый процесс переходит из одного состояния в другое в соответствии с алгоритмом планирования процессов, реализуемым в данной операционной системе. Типичный граф состояний процесса показан на рисунке 1.

В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ - несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

 

 

Рис.5. Граф состояний  процесса в многозадачной среде 

 Проблема синхронизации

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

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

Критическая секция

Важным понятием синхронизации  процессов является понятие "критическая  секция" программы (CS). Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Простейший способ обеспечить взаимное исключение - позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.

 Синхронизация  процессов на основе семафорных  
операций

Для устранения активного  ожидания процесса CPU  может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 12 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

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

V(S) : переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S) : уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

 

В частном случае, когда  семафор S может принимать только значения 0 и 1, он превращается в блокирующую  переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

Рассмотрим использование  семафоров для взаимоисключения процессов.

Двоичный семафор

 С каждым семафором  связывается список процессов,  ожидающих разрешения пройти  семафор.

ОС может выполнить  три действия над процессами:

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 6. Временная диаграмма для двоичного семафора (S)

 

Замечание: все CS должны быть одинаковы по длительности, поэтому чтобы упростить временные диаграммы здесь и далее применено сокращение -                           

           До момента t₁ ресурс был не занят. В момент t₁ процесс Pr1, выполняет операцию P(S) и входит в критический участок (CS).

В момент t₂ процесс Pr2 выполняет операцию P(S) – занять ресурс, это приводит к изменению: S = -1 – означает, что Pr2 в состоянии блокирования.

В момент t₃ – конец критического участка для процесса Pr1. Выполняется операция V(S) – освободить, это приводит к увеличению значения S на единицу (т.е. S=0). Для процесса блокированного (Pr2) это сигнал на разблокировку и предоставления ему ресурса.

В момент t₄ процесс Pr2 освобождает ресурс, выполняется операция V(S), которая изменяет значение S на 1 (т.е. S=1).

Достоинство синхронизации  на основе семафорных операций – отсутствие активного ожидания представления ресурса.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 7. Временная диаграмма для двоичного семафора (семафоры - S1 и S2)

 

Б – блокировано, СS1 и CS2 – критические участки 1 и 2, идентифицированные семафорами S1 и S2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2 Исходная таблица семафорных  операций

Табл.№ 2  Таблица семафорных операций.

Шаг	Модельное время	Семафорные операции	РЕСУРС	ПРИЧИНА	Владелец
1	3	p(w)	winchester	a1 takes	нет
2	7	p(f)	flop	a2 takes	нет
3	31	v(f)	flop	a2 frees	a2
4	32	v(w)	winchester	a1 frees	a1
5	33	p(w)	winchester	a6 takes	нет
6	40	p(w)	winchester	a5 waiting a6	a6
7	53	v(w)	winchester	a6 frees/a5 takes	a6
8	83	v(w)	winchester	a5 frees	a5
9	100	p(p)	printer	a1 takes	нет
10	105	p(f)	flop	a8 takes	нет
11	133	v(p)	printer	a1 frees	a1
12	144	v(f)	flop	a8 frees	a8
13	176	p(f)	flop	a1 takes	нет
14	179	p(w)	winchester	a7 takes	нет
15	182	p(w)	winchester	a6 waiting a7	a7
16	200	v(f)	flop	a1 frees	a1
17	200	v(w)	winchester	a7 frees/a6 takes	a7
18	204	p(w)	winchester	a4 waiting a6	a6
19	209	p(t)	tty	a5 takes	нет
20	209	p(w)	winchester	a3 waiting a6	a6
21	237	v(w)	winchester	a6 frees/a4 takes	a6
22	258	v(w)	winchester	a4 frees/a3 takes	a4
23	277	v(w)	winchester	a3 frees	a3
24	288	p(t)	tty	a4 waiting a5	a5
25	343	p(w)	winchester	a5 takes	нет
26	349	p(f)	flop	a3 takes	нет
27	384	v(f)	flop	a3 frees	a3
28	384	v(w)	winchester	a5 frees	a5
29	390	p(p)	printer	a7 takes	Нет
30	394	p(f)	flop	a5 takes	Нет
31	398	p(w)	winchester	a1 takes	Нет
32	402	p(w)	winchester	a3 waiting a1	a1
33	417	v(w)	winchester	a1 frees/a3 takes	a1
34	421	v(f)	flop	a5 frees	a5
35	435	v(t)	tty	a5 frees/a4 takes	a5
36	437	v(w)	winchester	a3 frees	a3
37	443	p(p)	printer	a4 waiting a7	a7
38	446	p(p)	printer	a3 waiting a7	a7
39	460	p(t)	tty	a1 waiting a4	a4
40	462	p(p)	printer	a5 waiting a7	a7