Диаграмма очередей.

                На рисунке представлен общий вид диаграммы очередей.

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

Реализация

Алгоритм и реализация задания.

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

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

                Практически все действия при работе с программой автоматически заносятся в рапорт.

                При различных настройках системы некоторые поля и методы в объектах могут не использоваться.

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

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

                Краткое описание работы:

                После запуска программы в информационном окне описано стартовое состояние системы имитации. Изначально система располагает только процессором и памятью. После этого активной становится главная форма (Main Form). В ней отображается вся информация о условиях проведения эксперимента. Также из главной формы доступны: окно планировщика памяти (Memory Scheduler), окно планировщика процессора и ресурсов (Resources Scheduler), методы для создания новых процессов и ресурсов, элементы управления для генерации новых процессов, кнопка New Tact, при нажатии на которую происходит имитация работы вычислительной системы.

                Создание нового процесса возможно из всех основных форм программы. Создание процесса происходит по нажатию кнопок New Process Manual или New Process Random. При создании процесса вручную выводится окно в котором возможно заполнение основных полей нового процесса. Это же окно выводится при нажатии кнопки Edit Process в окнах планировщика памяти или ресурсов. Как отмечалось выше некоторые поля в процессе могут не использоваться. Это зависит от организации очередей к ресурсам.

                При создании нового ресурса (по нажатию кнопки New Resource) выводится окно в котором устанавливается имя ресурса (Number & Name) тип организации очереди (Queue Organization) к ресурсу и вариант вытеснения (Pulling). Любой из параметров в доступных ресурсах можно изменить в любое время по нажатии кнопки Edit Resource в окне планировщика ресурсов.

                В ходе выполнения эксперимента возможно удаление из системы любого процесса или ресурса (кроме процессора) по нажатию кнопок Delete Process или Delete Resource соответственно. Отметим что ресурс удаляется вместе с пользователями которые стоят в очереди к нему.

                Во время выполнения имитации (по нажатию кнопки New Tact) последовательно вызывается метод Execute в объектах планировщик ресурсов (ResourceScheduler) и планировщик процессора (CPUScheduler). Производится:

– упорядочение очередей всех ресурсов (ResourceQueue) в списке ресурсов (ResourceScheduler.ResourcesList) и очереди процессора (CPUScheduler.CPUQueue) в зависимости от типа организации очереди и варианта вытеснения.

– Проверка о простое ресурсов.

– Добавление у удаление процессов в очередь процессора.

– Проверка о простое процессора.

– Выполнение процесса стоящего во главе очереди процессора

– Удаление завершенных процессов из очереди процессора, из очередей всех ресурсов, из списка пользователей памяти (MemoryScheduler.MemoryUsers).

– Вывод соответствующих сообщений в окно информации (рапорт работы).

                Необходимо отметить следующие моменты:

– В работе использован не стандартный подход к организации структуры ресурс-очередь. Очередь (ResourceQueue) включает в себя ресурс (ResourceQueue.Resource) и список пользователей этого ресурса (ResourceQueue.UsersList).

– Все очереди с ресурсами находятся в списке ресурсов (ResourceScheduler.ResourcesList).

– Первый процесс в очереди ресурса является текущим пользователем этого ресурса (Resource.ResourceUser). Его состояние – готовый (Ready). состояние остальных процессов в очереди – состояние ожидания (Wait Condition).

– Первый процесс в очереди процессора является текущим пользователем процессора. Его состояние – исполняемый (Executable). состояние остальных процессов в очереди процессора – готовый (Ready).

– В очереди процессора находятся процессы которым нужен только процессор (Process.NeedResource=0) и только по одному (первому в списке пользователей ресурса) процессу из каждого ресурса.

                Рассмотрим реализацию основных компонентов.

                Прежде всего необходим мощный механизм для создания списков. Такой механизм реализован в классе – универсальный список указателей (TPList).

                Cписок состоит из узлов (PElement) в каждом из которых хранится запоминаемый указатель, указатели на предыдущий и последующий узлы.

                Класс включает в себя такие методы как:

– Добавить указатель в список (InsertOnTop).

– Удалить текущий указатель (DeleteOnTop).

– Перемещение по списку (CircleMove, MoveToFirst, MoveToLast).

– Взять указатель из списка (GetOnTop, GetFirst, GetLast, GetPrevious, GetFollowing).

– Проверка пустоты списка (Empty).

– Взять количества элементов списка (Quantity).

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

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

                Тактовый генератор (TTactGenerator) предназначен для генерации нового такта по которому происходит исполнение основных алгоритмов.

                Процесс (TProcess).

                Поля класса описаны в спецификации.

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

                Ресурс (TResource) имеет следующие поля:

– Имя ресурса и его номер (Name, Number).

– Пользователь ресурса (ResourceUser).

– Время использования ресурса (TotalIntervalUsed).

– Состояние ресурса (Busy).

                Очередь (TResourceQueue)

                Обращение к очереди происходит по указателю на неё. Очередь характеризуется флагом вытеснения (WithPulling) и вариантом организации (QueueOrganization). Очередь включает в себя ресурс (Resource) и список пользователей (UsersList). Мы можем вставить процесс в очередь (InsertUser), удалить процесс из очереди (RemoveUser) и проверить существование процесса в очереди (ExistUser).

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

                При вставке процесса в очередь происходит переход в конец списка пользователей, и новый процесс ставится последним. После этого производим упорядочение очереди. При удалении пользователя из очереди мы даем методу указатель на процесс который надо найти и удалить: организовываем цикл в котором проверяем всех пользователей ресурса. Если в списке находится искомый процесс, то он удаляется. после этого упорядочиваем очередь. Упорядочивание очереди состоит из:

– Если очередь пуста, то состояние ресурса – свободен.

– Иначе

– Состояние ресурса – занят.

– Если очередь упорядочена или очередь упорядочена по времени и осталось до упорядочения=0, то

– Если с вытеснением или интервал непрерывной работы у первого равен нулю (Process.IntervalOfUnceasingExecution), то сортировка списка по приоритету с первого элемента.

– Иначе сортировка со второго элемента.

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

                Класс – планировщик памяти (TMemoryScheduler).

                При создании планировщика памяти параметром является число – количество доступной памяти. Значение доступной памяти можно изменить в окне планировщика памяти при отсутствии пользователей памяти, в поле ввода Memory Available.

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

– Увеличиваем число поступивших процессов (NumberOfReceivededProcesses).

– Если количество свободной памяти (MemoryFree) >= длине рабочей области процесса (Process.WorkLength), то

– Если метод первого подходящего, то просматриваем свободные блоки памяти, и размещаем процесс в первом блоке подходящей длины.

– Если метод наиболее подходящего, то просматриваем свободные блоки памяти, и размещаем процесс в наименьшем блоке подходящей длины.

– Если метод наименее подходящего, то просматриваем свободные блоки памяти, и размещаем процесс в наибольшем блоке подходящей длины.

– Если метод дефрагментация, то дефрагментируем помять (уплотняем все процессы, пересчитываем адреса начала процессов в ОП). Перемещаемся в конец списка пользователей. Новый процесс становится последним.

– Если процесс разместился в памяти, то выводим сообщение. Устанавливаем адрес начала процесса (Process.StartAddress) в зависимости от места в памяти. Пересчитываем значения свободной и занятой памяти (MemoryUsed).

– Иначе увеличиваем число отвергнутых процессов (NumberOfRejectedProcesses). Выводим соответствующее сообщение.

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

                Класс планировщик ресурсов (TResourceScheduler).

                Включает в себя список ресурсов (ResourcesList).

                Метод вставить ресурс (InsertResource) заключается в вставке нового ресурса в список ресурсов.

                Метод удалить ресурс (RemoveResource) заключается в поиске в списке ресурсов ресурса с нужным номером, и при обнаружении удаление его из списка, уничтожение пользователей списке пользователей.

                Метод удалить пользователя (RemoveUser) заключается в поиске в списке ресурсов ресурса с нужным номером, и при обнаружении – удаление пользователя из списка пользователей к этому ресурсу.

                Метод вставить пользователя (InsertUser) заключается в поиске в списке ресурсов ресурса с нужным номером, и при обнаружении – вставить пользователя в список пользователей к этому ресурсу.

Спецификация

Unit UPList;

PElement = ^TElement; {Элемент списка с запоминаемым указателем}

TElement = record

Prestored : pointer; {Запоминаемый указатель}

Previous : PElement; {Указатель на предыдущий элемент списка}

Following : PElement; {Указатель на последующий элемент списка}

TPList = class(TObject) {Универсальный список элементов}

Element : PElement; {Элемент списка}

First : PElement; {Указатель на первый элемент}

OnTop : PElement; {Указатель на текущий элемент}

Last : PElement; {Указатель на последний элемент}

QuantityPtrs : integer; {Количество элементов}

Create; {Инициализация нового списка}

InsertOnTop(ToPrevious : boolean; Ptr : pointer); {Вставляем новый элемент}

DeleteOnTop(ToPrevious : boolean) : pointer; {Удаляем текущий элемент}

MoveToFirst; {Устанавливаем текущий на первый}

MoveToLast; {Устанавливаем текущий на последний}

CircleMove(ToPrevious : boolean); {Круговой сдвиг текущего к предыдущим или последующим}

GetFirst : pointer; {Взять первый указатель}

GetPrevious : pointer; {Взять предыдущий указатель}

GetOnTop : pointer; {Взять текущий указатель}

GetFollowing : pointer; {Взять последующий указатель}

GetLast : pointer; {Взять последний указатель}

Empty : boolean; {Проверка на пусто}

Quantity : integer; {Количество элементов}

FirstReach : boolean; {Проверка на достижение первого элемента}

LastReach : boolean; {Проверка на достижение последнего элемента}

Unit UTactGenerator;

TTactGenerator = class(TObject) {Таймер}

TactCounter : integer; {Счетчик таймера}

Create; {Создать таймер}

NewTact; {Увеличить таймер}

GetTactCounter : integer; {Взять значение таймера}

Unit UProcess;

PProcess = ^TProcess; {Указатель на процесс}

TProcess = class(TObject) {Процесс}

Name : string[32]; {Имя процесса}

NeedResource : integer; {Номер необходимого ресурса 0..more (0-CPU)}

WorkLength : 1..64; {Длина рабочей области}

StartAddress : integer; {Адрес начала рабочей области в ОП}

Priority : integer; {Приоритет 0-min}

IntervalOfUnceasingExecution : integer; {Интервал непрерывного выполнения}

FullIntervalOfExecution : integer; {Полный интервал выполнения}

IntervalBeforeTermination : integer; {Интервал оставшийся до завершения}

TerminateReason : integer; {Причина прекращения 1..more-обращение к ресурсам, 0-завершение процесса}

State : 0..2; {Состояние 0-выполняемый, 1-готовый, 2-в состоянии ижидания}

QuantumForRotation : integer; {Квант для круговорота}

QuantumBeforeRotation : integer; {Квант оставшийся до круговорота}

Create(Auto : boolean); {Инициализация процесса}

Destroy; override; {Уничтожение процесса}

GetName : string; {Получить имя}

GetNeedResource : integer; {Получить номер необходимого ресурса}

GetPriority : integer; {Получить приоритет}

GetIntervalBeforeTermination : integer; {Получить интервал оставшийся до завершения}

GetState : integer; {Получить состояние}

ShowInfo; {Вывести текущую информацию}

Unit UResource;

TResource = class(TObject) {Ресурс}

Name : string[32]; {Имя ресурса}

Number : integer; {Номер ресурса}

ResourceUser : PProcess; {Пользователь ресурса}

TotalIntervalUsed : integer; {Время использования ресурса}

Busy : boolean; {Занят}

Create; {Инициализация ресурса}

Destroy; override; {Уничтожение ресурса}

GetName : string; {Получить имя}

GetUser : PProcess; {Получить указатель на пользователя}

GetState : boolean; {Получить состояние}

ShowInfo; {Вывести текущую информацию}

Unit UResourceQueue;

PResourceQueue = ^TResourceQueue; {Указатель на очередь ресурса}

TResourceQueue = class(TObject) {Очередь ресурса}

Resource : TResource; {Ресурс}

WithPulling : boolean; {С вытеснением}

QueueOrganization : 0..4; {Организация очереди 0-упорядочена, 1-неупорядочена, 2-упорядочена через время, 3-круговорот, 4-эгоистический круговорот}

IntervalForRegularize : integer; {Интервал для упорядочения}

RemainForRegularize : integer; {Осталось до упорядочения}

UsersList : TPList; {Пользователи ресурса}

Create; {Инициализация новой очереди ресурса}

Destroy; override; {Уничтожение очереди ресурса}

InsertUser(NewPProcess : PProcess); {Добавить пользователя}

ExistUser(TempPProcess : PProcess) : boolean; {Проверка на существование пользователя}

RemoveUser(TempPProcess : PProcess); {Удалить пользователя}

Empty : boolean; {Проверка на пусто}

Regularize; {Упорядочить}

ShowInfo; {Вывести текущую информацию}

Unit UMemoryScheduler;

TMemoryScheduler = class(TObject) {Планировщик памяти}

MemoryAll : integer; {Общее количество памяти}

MemoryUsed : integer; {Количество используемой памяти}

MemoryFree : integer; {Количество свободной памяти}

MemorySharing : 0..3; {Методы распределения ОП 0-первого подходящего, 1-наиболее подходящего, 2-наименее подходящего, 3-дефрагментация}

FirstFreeAddress : integer; {Первый свободный адресс}

MemoryUsers : TPList; {Пользователи памяти}

Create(Memory : integer); {Инициализируем планировщик памяти}

MemoryDefragmentation; {Дефрагментировать память}

GetMemory(NewPProcess : PProcess) : boolean; {Выделить память}

FreeMemory(CurrentPProcess : PProcess); {Освободить память}

FindFirstFreeAddress; {Найти первый свободный адресс}

Unit UResourceScheduler;

TResourceScheduler = class(TObject) {Планировщик ресурсов}

NumberOfResources : integer; {Число ресурсов}

ResourcesList : TPList; {Список ресурсов}

Create; {Инициализируем планировщик ресурсов}

Execution; {Выполнение}

InsertResource(NewPResourceQueque : PResourceQueue); {Добавить ресурс}

RemoveResource(ResourceNumber : integer); {Удалить ресурс}

InsertUser(NewPProcess : PProcess); {Добавить пользователя}

RemoveUser(TempPProcess : PProcess); {Удалить пользователя}

FindResourceByNumber(ResourceNumber : integer) : PResourceQueue; {Поиск ресурса по номеру}

Empty : boolean; {Проверка на пусто}

Unit UCPUScheduler;

TCPUScheduler = class(TObject) {Планировщик CPU}

CPUQueue : PResourceQueue; {Очередь CPU}

Create; {Инициализируем планировщик CPU}

Execution; {Выполнение}

InsertUser(NewPProcess : PProcess); {Добавить пользователя}

RemoveUser(TempPProcess : PProcess); {Удалить пользователя}

ExistUser(TempPProcess : PProcess) : boolean; {Проверка на существование пользователя}

Empty : boolean; {Проверка на пусто}

Глобальные переменные в UFMain

ToPrevious = true;

ToFollowing = false;

Auto = true;

Manual = false;

MemoryAvailable : integer; {Памяти доступно}

NumberOfTerminatedProcesses : integer; (Число законченных процессов)

NumberOfReceivededProcesses : integer; (Число полученных процессов)

NumberOfRejectedProcesses : integer; {Число отвергнутых процессов }

AddToReport : boolean; {Флаг для добавления в рапорт}

MaxPriority : integer; {Максимальный приоритет}

FileName : string; {Имя файла}

StringVar : string; {Временная строковая переменная}

MemoryScheduler : TMemoryScheduler; {Планировщик памяти}

ResourceScheduler : TResourceScheduler; {Планировщик ресурсов}

CPUScheduler : TCPUScheduler; {Планировщик процессора}

TactGenerator : TTactGenerator; {Тактовый генератор}

Анализ интерфейса.