1. Объектно-ориентированный анализ предметной области

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

1. ОПИСАНИЕ СИСТЕМЫ В ТЕРМИНАХ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

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

Моделью очереди заявок может служить система массового обслуживания. Здесь ключевыми являются характеристики заявок. Часто различают заявки по их приоритету, т.е. по важности. Заявки высокого приоритета обслуживаются в первую очередь. Абсолютный приоритет дает право прервать обслуживание менее важной заявки и занять ее место в обслуживающем приборе. Вытесненная заявка либо теряется, либо поступает в очередь, где ждет дообслуживания. Иногда приходится возобновлять обслуживание вытесненной заявки с начала, а не продолжать с точки прерывания. Если заявка вытеснена на из буфера, она, естественно, теряется. Примером заявки с абсолютным приоритетом является судно, получившее пробоину и нуждающееся в срочной разгрузке. В вычислительных системах абсолютным приоритетом обладают команды оператора. Относительный приоритет дает право первоочередного занятия освободившегося прибора. Он дает право на вытеснение заявки из прибора или буфера. Абсолютный и относительные приоритеты различаются и моментом действия: абсолютный реализуется в момент поступления, а относительный - в момент освобождения прибора.

Различают фиксированные и динамические приоритеты. Фиксированные приоритеты чаще называют дисциплиной обслуживания. Дисциплина обслуживания задает порядок выбора из очереди в освободившийся прибор заявок одинакового приоритета. Нашей задачей является разработка программы, моделирующей работу многопроцессорной системы для четырех дисциплин обслуживания FIFO, LIFO, SJF, RR. Первые три алгоритма являются невытесняющими. RR является в данной системе вытесняющим алгоритмом, основанным на квантовании и приоритетах.

1. Дисциплины обслуживания

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

FIFO (First- in-First-Out)

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

LIFO (Last-In-Fist-Out)

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

SJF (Shortest Job First)

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

RR (Round Robin)

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