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

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

НГТУ

Кафедра ВТ            

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

 

 

 

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

Группа: АМ-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 - "первым пришел - первым выбран на обслуживание".