Методические указания к курсовой работe
(Раздел "Управление оперативной памятью")

 1. Указания к выполнению курсовой работы
 2. Методы управления страницами
  2.1. Базовые концепции метода управления страницами
  2.2. Методы управления страницами
  2.3. Модель рабочего набора страниц
  2.4. Проблемы управления страницами
 3. Проектирование системы управления страницами
 4. Базы данных для управления страницами
 5. Фазы данных для управления страницами
  5.1. Модуль обработки прерывания по таймеру
  5.2. Модуль обработки сбоя страницы.
  5.3. Модуль обработки таблиц страниц.
  5.4. Модуль постановки в очередь на ввод.
  5.5. Модуль обработки прерывания по обмену с диском.
  5.6. Модуль деактивизации (ошибка адресации).
  5.7. Модуль освобождения страницы.
  5.8. Менеджер страниц.

 Приложение

 °  Постановка задачи.
 °  Генерация задания.
 °  Варианты задания.
 °  Диаграмма очередей.
 °  Реализация.
  °  Алгоритм и реализация задания.
  °  Спецификация.
  °  Анализ интерфейса.

 Литература





1. УКАЗАНИЯ К ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ



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

  1. страничной;

  2. сегментной;

  3. сегментно - страничной организацией памяти.


Создать подсистему управления ОП в составе:

  °  база данных для управления ОП;

  °  таблица трансляции;

  °  таблица страниц (сегментов, сегментно - страничной организацией);

  °  менеджер страниц (сегментов, сегментно - страничной организации).

Определить рабочую область менеджера памяти.

Разработать алгоритмы обработки прерываний по обращению к ОП:

  4. прерывание по таймеру интервалов;

  5. прерывание по сбою страницы (сегмента, сегментно - страничной организации);

  6. прерывание по переполнению рабочего набора;


  7. прерывание по ошибке адресации;


  8. страничное (сегментное, сегментно - страничное) прерывание.

Курсовая работа должна содержать:

  °  Введение (постановку задачи).

  °  Теоретические основы управления памятью:

   °  анализ алгоритмов управления;

   °  обработка прерываний по обращению к ОП.

  °  обработчики прерываний.

  °  Менеджер памяти.

  °  Структуры таблиц и очередей.



Программа обработки прерываний должна содержать следующий набор операций.
  1. Прерывание по таймеру интервалов (см. модуль 1).
    1. Загрузка Т = В.
    2. Генерация прерывания по окончании работы.
    3. Циркуляция.
    4. Изменение рабочего набора.
    5. Деактивация.

  2. Страничный сбой (загрузка страниц в ОП) (см. модуль 2).
    1. Читать таймер интервалов.
    2. Проверить таблицу страниц.
    3. Отделить дескриптор страниц.
    4. Добавить дескриптор страницы.
    5. Сохранить таблицу карт.
    6. Деактивизировать.
    7. Поставить в очередь на ввод.

  3. Страничное прерывание (пересылка страницы с диска в ОП) (см. модули 4, 5).
    1. Загрузить дескриптор страницы.
    2. Установить элементы карты.
    3. Добавить процесс (i+1)
    4. Добавить дескриптор страницы.
    5. Удалить процесс (i).
    6. Поставить в очередь на ввод.

  4. Переполнение рабочего набора (см. модуль 7).
    1. Освободить страницу (отделить дескриптор).
    2. Удалить процесс (i).
    3. Добавить процесс (i + 1).
    4. Сохранить регистры (связь - вперед).
    5. Выбрать следующий процесс.
    6. Загрузить вектор состояния.

  5. Ошибка адресации (процесс аннулируется) (см. модуль 6).
    1. Освободить страницы процесса.










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

1. ЛАП < ФАП. В этом случае основной акцент делается на повышение эффективности использования памяти.

2. ЛАП = ФАП. Страничная организация служит не только для увеличения эффективности использования памяти, но и для расширения возможности разделенного использования процедур (т.е. несколькими пользователями). Возможно использование эффективного оверлейного механизма, реализованного аппаратно.

3. ЛАП > ФАП. Этот случай предполагает виртуальную память и дает наибольшие преимущества.

Мы будем рассматривать управление страницами применительно к последнему случаю. Выбор между случаями 1 и 2 обычно находится в зависимости от структуры Устройства Управления Памятью (УУП) и задач проектировщика операционной системы. Пользователь, располагая ЛАП из m страниц, будет иметь k страниц, отведенных под интерпретатор, и m - k страниц рабочего пространства. Описанный подход эффективен для системы с разделением времени.

Идентификация. Страницы и рамки страниц с набжают числовыми идентификаторами, устанавливаемыми по следующему правилу.

Пусть p есть размер страницы в словах (например, 512).

Пусть т есть размер основной памяти в словах, такой, что m=n*p по модулю 1024 есть 0; р по модулю 2К есть 0 и i*p=j*1024. Таким образом, основная память состоит из участков по 1К слов в каждом. Кроме этого, размер страницы есть степень числа 2, а 1К памяти содержит четное число страниц. Набор целых чисел 0, 1, 2,...,п-1 соответствует идентификаторам страничных рамок.

Пусть М есть размер программы пользователя в словах. Для размещения этой программы в памяти необходимо N страниц, так что М=N*p. Набор целых чисел от 0 до п-1 соответствует идентификаторам страниц пользователя. Заметим, что требование равенства нулю m по модулю р не является обязательным. Это означает, что программа пользователя не должна заполнять целиком все страницы. Последняя страница может быть заполнена лишь частично.

Используя двоичную арифметику, - представление страницы степенью числа 2 легко реализуемо. Фактически в большинстве машин имеются команды сдвига, делающие генерацию виртуального адреса очень простой операцией. Требование задания М кратным 1К является результатом стандартизации. В последнее время принято считать, что размер 8К, 16К и даже 64К более предпочтителен.

Конструкция виртуального адреса. Виртуальный адрес - это адрес логического пространства процесса пользователя (обычно для случая ЛАП >ФАП). Все ссылки к логическому пространству должны быть преобразованы в физический адрес основной памяти. Для этого системе необходимы идентификатор рамки страницы и смещение внутри нее. Система должна преобразовать виртуальный адрес в физический. Каждый виртуальный адрес есть пара (р, i), где р - номер страницы процесса пользователя, а i-индекс страницы (такой, что i<w, где w-размер страницы).

Предположим, что машина имеет 16-бит слово, позволяющее ей адресоваться к 64К слов. Если размер страницы составит 512 слов, то логическое адресное пространство будет состоять из 128 страниц. Для идентификатора р необходимо 7 бит, а для индекса 9 бит. Полное 16-бит слово будет иметь вид



Идентификатор - страницы индекс - слова


Отметим, что случай ЛАП<ФАП возможен, если устройство управления памятью обеспечивает размер слова, больший чем 18 бит. На ЭВМ серии PDP-11/70 ЛАП каждого пользователя ограничено 64К байт, в то время как УУП поддерживает 128К слов. В ЭВМ серии VAX-11/780 фирмы DEC адресное пространство каждого пользователя составляет 232, а максимальный физический размер основной памяти может достигать 16М байт. В ЭВМ серии VAX-11/780 используется 32-бит слово, имеющее следующую конструкцию:



31 30 ид виртуальной страницы байт в странице


где биты 31 и 30 имеют специальное назначение для;VAX/VMS;биты 29 - 9 адресуются к одной из 220страниц;биты 7 - 0 выбирают один из 512 байт в странице.

На ЭВМ, имеющей 16-бит размер слова, большой виртуальный адрес может быть составлен из двух слов. Он может иметь, например, такой вид:



Номер страницы
Байт в странице


Роль таблицы страниц. Одним из достоинств страничной организации является динамическое распределение страниц пользователя в любом месте памяти. Так, страница Р процесса

Рис. 1
Рис. 1Отображение страницы на основную память.
Виртуальный адрес = (р,i). Физический адрес - x = размер страницы + i.
Отрицательное значение идентификатора рамки страницы указывает на то,
что страница в данный момент отсутствует в памяти

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

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

Рис. 2

Рис. 2. Обобщенная процедура страничного обмена.
Блок # - это адрес рамки страницы в основной памяти (поэтому умножения на размер страницы не требуется)


Например, предположим, что УУП располагает пространством для 16 карт памяти, а каждая карта памяти содержит поля (элементы) для 64 страниц по 512 слов в каждой. Карта с номером 0 всегда принадлежит ядру операционной системы. Такой подход не может быть реализован для систем с большим объемом виртуальной памяти, так как стоимость УУП будет чрезмерно большой. В этом случае карта остается в основной памяти, а УУП управляет текущей картой пользователя с помощью указателей. На рис.2 приведена структура, соответствующая такой схеме.

По этой схеме УУП поддерживает список адресов таблиц для n пользователей. Аппаратно реализованный регистр служит для указания текущего пользователя, т.е. пользователя, чья таблица страниц является в настоящий момент активной. Элемент таблицы, содержащий карту пользователя (в УУП), загружается в аппаратный регистр базы таблицы страниц. Каждый адрес памяти содержит идентификатор страницы и индекс. Идентификатор страницы в комбинации с содержимым базового регистра таблицы страниц указывает на элемент таблицы страниц. Содержимым этого элемента является адрес рамки страницы в памяти. Добавляя индекс к адресу рамки страницы, мы получаем физический адрес.

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

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

1. БИТ-ПРИСУТСТВИЯ указывает, находится ли страница в данный момент в основной памяти.

2. БИТ(Ы)-АКТИВНОСТИ указывает на использование за последнее время данной страницы процедурами страничного обмена.

3. БИТ-ИЗМЕНЕНИЯ указывает на то, что содержимое страницы памяти изменялось (или не изменялось) с момента ее загрузки в память.

Наиболее важными из этих битов являются БИТ-ПРИСУТСТВИЯ и БИТ-ИЗМЕНЕНИЯ. Бит присутствия анализируется при каждой адресной ссылке программы пользователя. Равенство его нулю означает, что страница была удалена из памяти. Бит изменения определяет необходимость записи страницы на диск при ее замене в памяти. Единичное его значение означает, что в содержимом страницы были сделаны изменения, и, следовательно, она должна быть записана на диск. (Нулевое значение предполагает использование прежней копии.) В системах, в которых страницы инструкций (в противоположность страницам данных) являются реентерабельными, бит изменения никогда не устанавливается.








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

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

Методы замены. При рассмотрении методов замены мы считаем, что количество страниц, которое может быть загружено в память, значительно превосходит количество рамок страниц, необходимых для этого размещения. Пусть х- последовательность адресов страниц, т.е. страниц, к которым адресуется программа в ходе своего выполнения. Пусть x(t) есть страница, адресуемая в момент времени t. Строка w=x(1),х(2),x(3),...,х(М) часто называется строкой страничных ссылок. Пусть с есть число заполненных в настоящий момент страничных рамок в памяти. Тогда М(с,t) представляет собой текущую конфигурацию программы пользователя в памяти, а п(с, t)-число страниц в М(с, t).

Рассмотрим ссылку к текущей странице х(t). В зависимости от текущей конфигурации программы М (с, t) возможны три случая.

1. Пусть x(t) есть элемент М(с,t-1), т. е. текущая страница находится в памяти. Никаких изменений в памяти не производится, поэтому М(с,t-1)>M(c,t). Такая ситуация называется сменой страницы.

2. Предположим, что x(t) не принадлежит m (с, t - 1). Далее предположим, что m(с, t-1) меньше с; следовательно, память не заполнена до конца страницами программы. Тогда в память загружается текущая страница. В этом случае M(c, t - 1) Ux(t)> M(c, t) m(c,t -1) A+l>m(c,t). Такая ситуация называется сбоем страницы.

3. Предположим, что x(t) не принадлежит М(с,t-1) и что m(c,t-1)=с; следовательно, память полна и страницу необходимо заменить. Пусть y(t) есть удаляемая из памяти страница, выбранная алгоритмом замены. Тогда (M(c,t-1) удалить y(t)) Ux(t)>M(c,t). Хороший алгоритм замены старается минимизировать число обменов “диск - память”. В литературе был описан ряд возможных алгоритмов. Вот некоторые из них:

1. МИН - алгоритм, минимизирующий число страничных замен. При возникновении необходимости обмена МИН анализирует каждую страницу в M(c,t - 1) по отношению к ее дальнейшему появлению в М(с,t). Алгоритм МИН выбирает для замены ту страницу в M(c,t-1), ссылка к которой в будущей является наиболее отдаленной. Очевидно, что это весьма не практично, так как для МИН заранее необходимо точно знает о будущих ссылках в последовательности страниц. Такую информированность можно поддерживать применительно к относительно статичным программам. Так как полностью статических программ весьма мало, строка будущих ссылок в общем случае непредсказуема.

2. ПНИС - последний из недавно использованных, алгоритм замены, сходный с алгоритмом МИН, за исключением того, что он просматривает строку адресных ссылок в обратном направлении. Алгоритм ПНИС отыскивает в W страницу, последняя адресация к которой была наиболее давней и которая по-прежнему принадлежит к M(c,t-1), Исследования показали целесообразность использования алгоритмов ПНИС.

3. Еще один класс алгоритмов использует метод, при котором первая загруженная страница является и первой удаляемой (FIFO). Алгоритмы перемещают указатель по строке ссылок и удаляют страницу, следующую за указываемой. Этот алгоритм в худшем случае приближается к алгоритму с произвольной заменой страниц.








Предположим, что программа в момент времени t занимает m(t) страниц. Определим c(t1,t2) за интервал времени (t1, t2) как

T2

С(Т1,T2)=T2*SUM[M(T)*DT]

Т1

Это означает, что за интервал времени (t1, t2) с (t1, t2)представляет собой общее число страниц, занимаемых программой. Поскольку расходы на вычисления основываются главным образом на объеме и времени занятости используемой памяти, мы можем считать, что величина с(t1, t2)представляет собой грубую оценку стоимости выполнения программы, при которой ее работу еще можно считать эффективной. Интуитивно ощущаемое преимущество концепции рабочего набора заключается в возможности оценки различных стратегий управления страницами применительно к различным типам устройств внешней памяти. Эта концепция также удобна при разработке программ планирования; она позволяет организовывать эффективное и спользование системных ресурсов.

Принцип локальности. Пусть некоторая программа состоит из набора страниц N, а рабочий набор состоит в любой момент времени из подмножества страниц набора N. Принцип локальности предполагает, что содержание W медленно изменяется во времени. Это означает, что при выполнении программа в течение заданного интервала времени отдает предпочтение некоторому набору адресов из всего множества адресов своего логического адресного пространства. Если программа составлена с применением структурно-модульного принципа, то это позволяет провести анализ, показывающий, что в течение короткого интервала времени может быть выполнено ограниченное число инструкций. (Предположим, что программные модули занимают объем, меньший одной страницы, и содержат от 10 до 20 выполнимых инструкций. Если положить степень расширения равной 12:1, то можно увидеть, что большинство приведенных модулей уместится на одной странице объемом 256 слов. При скорости обработки, равной 1 мкс. на инструкцию, время выполнения модуля займет от 1 до 2 мс и составит значительный временной интервал для локального выполнения.) Для страницы i такой, что i<N, определим плотность адресных ссылок в виде

d(i, k) = вероятнь (x(k) = i)

где x(k) - это страница, к которой делаются ссылки за время k. Очевидно, что

0<=d(i,k)<=1, S d(i,k) = 1 при i= 1,...,т.

Пользуясь значениями d(i,k), можно составить список, упорядоченный по отношению к числу ссылок к моменту времени k. Ниже приведен пример такого списка L (для программ из 10 страниц):



Индекс

Страница

Ссылка, k1

Ссылка, k2

1 10 0 0
2 9 0 0
3 1 10 10
4 2 25 25
5 3 100 125
6 8 140 175
7 7 190 230
8 4 215 270
9 6 260 320
10 5 300 400


Рассмотрим приведенный список L. Как видно, для моментов времени k1 и k2 относительная упорядоченность списка не изменилась, и можно считать, что рабочий набор один и тот же. Предположим теперь, что к моменту k2 имеется следующая последовательность для индексов с 6-го по 8-й:



Индекс

Страница

Ссылка, k2

6 4 220
7 7 255
8 8 290


Относительная упорядоченность списка L за интервал (k1, k2) в данном случае изменилась. Это означает, что за интервал времени (А1,k2) рабочий набор изменился.
Принцип локальности предполагает, что за достаточно продолжительные временные интервалы (k1, k2) относительная упорядоченность L(k) будет оставаться той же самой или будет изменяться очень медленно. Непосредственно измерить значение d(i,k) довольно трудно, не менее затруднительно и предсказать его по наблюдениям. Однако определение рабочего набора дает возможность не беспокоиться об измерениях.

Определение рабочего набора. Рабочий набор w(k) для k-й адресной ссылки определяется как

w(k,h)=(I есть элемент N, такой, что I есть элемент W'),

где W' = x(k-h +l), ...,x(k) - строка ссылок страницы, h>=1 - “окно” (незанятый участок), i—индекс страницы.

Это означает, что содержимое w(k,h) - это открытый с одного конца участок длины h, определяемый строкой ссылок и оканчивающийся на x(k). В качестве примера рассмотрим последовательность страничных ссылок

k 0 1 2 3 4 5 6 7 8 9 10 11 12

Страница Р2 Р1 Р6 Р1 РЗ Р2 Р6 Р4 Р5 Р4 Р5 Р2 Р4

и последовательность страниц, упорядоченных по давности употребления;

Р4 Р2 Р5 Р6 РЗ Р1,

где Р4—позднейшая ссылка, а Р1—самая давняя. Рабочие наборы для различных h. (начиная с k = 12):



W(k,h)

H

Р4 1
P4 Р2 2
Р4 P2 P5 3-7


Предполагается, что рабочий набор содержит самые нужные страницы (т.е. те страницы, к которым в будущем предполагается осуществить наибольшее количество ссылок). В терминах d(i,k) [поскольку (для k=12) Р2—это элемент из w(k,7),а Р1 не есть элемент w(k,7)] ожидаем, что d(2,k) >= d(1,k). Задача выбора подходящего h будет рассмотрена ниже.

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

Для рабочего набора существует ряд важных характеристик. Предположим, что w(h) есть ожидаемый рабочий набор:

w(h) = ожидаемое значение [w(t,h)].

Свойства w(h).

1. Пусть h >= l, тогда 1 =< w(h) < min (n,h). Это означает, что рабочий набор программы всегда один и не может превышать величины свободного участка (“окна”) или общего числа страниц программы. Размер окна определяет число страниц, “просматриваемых” ссылками программы. Следовательно, в рабочем наборе может быть h страниц (h<M) или п страниц (т<Н).

2. w(h) < w(h+1). Это означает, что рабочий набор со временем расширяется, приближаясь к своему верхнему пределу.








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

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

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

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

Пробуксовка обязана своим возникновением не одному только поведению процесса, а слабому пониманию взаимодействия между поведением процесса, алгоритмами управления страницами и возможностями аппаратной части ЭВМ. Процессы, имеющие большие размеры, вмешиваются в работу друг друга, конкурируя между собой за доступ к ограниченному объему основной памяти. Некоторые алгоритмы, такие, как FIFO и ПНИС, вносят ощутимый вклад в подобную ситуацию, порождая глобальную конкуренцию среди всех процессов в памяти. Более того, нехватка основной памяти имеет свои серьезные последствия в увеличении вероятности существования недостающей страницы, принадлежащей любому процессу.

Концепция пробуксовки базируется на том эффекте, что система переходит от стабильного состояния эффективной работы к хаотическому перемещению страниц между внешним запоминающим устройством и основной памятью. Предположим, что процесс выполнялся в течение некоторого виртуального времени V. Предположим далее, что за это время вероятность т существования недостающей страницы была постоянной величиной. Предполагаемое число ожиданий страницы есть V*m, при этом каждое ожидание составляет время Т (время доступа к диску). Эффективность системы е(т) определится следующим образом:

e(m)=(истекшее виртуальное время)/((истекшее виртуальное время)+(общее время ожидания))

или символически

e(m)=1/(1+m*T),

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

d[e(m)]/dT = -T/(l+m*T)2.

Для небольших значений m и при t>>1 эффективность чувствительна к изменениям т. Эта чувствительность т к флюктуациям при больших Т и определяет пробуксовку.

Для демонстрации этого эффекта предлагает проделать теоретический эксперимент. Пусть имеется п+1 идентичных процессов, п из которых выполняются в основной памяти. Предположим, что каждый процесс имеет размер s, так что размер основной памяти есть M=n*s. Пусть то обозначает вероятность существования недостающей страницы, такую, что m0<<1, а е(т0) не намного меньше 1. В среднем имеется достаточно места для хранения недавно адресованных страниц каждого процесса. Число активных процессов определится в виде

p = n/(1+m0*T).

Введение (n+1) процесса увеличит вероятность существования недостающей страницы на некоторую величину d. Загрузка (n+1)-процесса дает значение d, равное 1/(n+1). Заметим, что в результате этого р уменьшится, так как

т0єx(1+р)*(m0+d).

Предположим, что T>>n>>1. Это означает, что время доступа очень велико и число процессов также велико. Показывает, что r>>m0. Действительно, в противном случае эффективность была бы e(m0)<<l, что противоречит предположению об п процессах. Соответствующее уменьшение активных процессов

p'=(n+1)/[T+(n+1)*m0p]

такое, что р'/р<<1.

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

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

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

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

Оптимальный размер страницы, сбалансированный между неиспользованным пространством (на последней странице) и недоступным пространством (согласно таблице страниц) вычисляется путем введения понятия стоимости потерь в пространстве памяти. Пусть c1 - стоимость потери слова в памяти из-за наличия таблицы, а c2 - стоимость потери слова из-за внутренней фрагментации. Тогда с=с1 / c2 если s<<p, то s0=(2ср1/2. Этот результат получается следующим способом. Пусть р есть ожидаемое значение переменной, описывающей величину программы, такое, что

р= ожидаемое значение [р]

Предположим, что программа использует n=p/s страниц и каждой странице соответствует слово в таблице страниц. Тогда стоимость одной страницы должна составить c1*p/s. При s<<p ожидаемая потеря на последней странице есть s/2, а ее стоимость составляет c2*s/2. Общая ожидаемая стоимость потерь составит ожидаемое значение

[C / s]=(p / s) * c1 + (s / 2)*c2.

Дифференцируя и находя минимум, получим формулу, приведенную выше.

Какой размер страницы является наиболее целесообразным? Большинство фирм, производящих ЭВМ, ограничивает проектировщика операционной системы, аппаратно реализуя функцию, определяющую размер страницы. Этот размер колеблется от 512 до 2048 слов. Установлено, что программы студентов содержат в среднем несколько тысяч слов, a s0 составляет около 50.

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








Для создания системы управления страницами проектировщику необходимо детально знать УУП и архитектуру системы в целом.

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

  • Что происходит во время загрузки страницы в память?
  • Как осуществляется контроль нескольких конкурирующих запросов на загрузку или освобождение страниц?
  • Какой эффект оказывает планирование ввода-вывода на обслуживание страничных запросов и общую производительность системы?

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

Ряд процессов находится в очереди на выполнение. При возникновении доступа к пространству основной памяти процессу с наивысшим приоритетом назначается квант времени q[i], и он помещается в очередь выполняющихся процессов. Эти процессы выполняются в течение времени В, таком, что В меньше или равно q[i]. По окончании В секунд выполнения процесс возвращается в очередь выполняющихся процессов. Из этой процедуры исключаются следующие ситуации:

  1. время выполнения t[i] процесса превосходит квант времени (t[i]>q[i]); при этом процесс помещается в очередь на выполнение, а его t[i] устанавливается в нуль;
  2. процесс блокируется на время выполнения запроса к системной службе;
  3. процесс завершил свое выполнение;
  4. произошел сбой страницы, на время обслуживания которого процесс приостанавливается, а после загрузки требуемой страницы помещается в очередь на выполнение;

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

Страницы загружаются или удаляются из памяти согласно алгоритму, поддерживающему рабочую область (разд. 2). Страницы загружаются в память по запросу процесса. Загруженная в память страница активизируется. Для каждой активной страницы в памяти имеется счетчик, регистрирующий рабочее время процесса, прошедшее с момента его последней ссылки к странице, счетчик сбрасывается в нуль при каждой ссылке к странице. Если за интервал времени В такой ссылки не произошло, то счетчик увеличивается на величину В. Когда значение счетчика превышает некоторую установленную величину J, страница освобождается, а рамка страницы становится доступной для следующего распределения. Доступные страницы могут находиться в следующих состояниях.

  1. Готовые для повторного распределения.

  2. В измененном состоянии, требующем для повторного использования страницы ее удаления из памяти.

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

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

Страница перестает быть активной и, следовательно, становится доступной, если к ней не производилось обращения в течение J секунд. Таким образом, либо она не является членом рабочего набора, либо процесс не находится в активном состоянии из-за окончания своего кванта времени, блокирования запросом к системной службе или выхода за границы рабочего набора в тот момент, когда доступные страницы отсутствуют. Итак, менеджер страницы управляет динамическими (т.е. имеющими переменный размер) рабочими наборами для каждой активной программы. Менеджер страниц распределяет их по двум очередям: “обменной” очереди и "доступной" очереди(так как страницы из нее не нуждаются в обмене). Если процесс адресуется к странице, которая была недавно удалена из его рабочего набора, то вероятность того, что эта страница еще находится в одной из очередей в памяти, достаточно велика. Если счетчик доступных страниц не равен нулю, требуемая страница может быть немедленно распределена процессу.

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

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








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

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

Таблицы трансляции. Таблицы трансляции обычно встроены в УУП. Устройства управления памятью различных фирм-производителей ЭВМ отличаются друг от друга. Таблицы трансляции большинства фирм содержат следующие регистры:



Мнемоника

Назначение

призн-актианости

 

призн-ссылки

призн-изменения

защита-записи


индекс-блока

Указывает на то, что страница в настоящий момент времени принадлежит рабочему набору процесса (возможно, и не находясь при этом в активном состоянии)


Указывает на то, что за интервал времени J к странице производилось обращение

Указывает на то, что страница модифицировалась процессом

Указывает на то, что страница защищена от возможного изменения ее содержимого

Указывает адрес физической страницы для виртуальной страницы в основной памяти



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

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

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

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



Мнемоника

Назначение

статус – страницы

защита - записи

призн – изменения


счетчик – использования


призн – блокировки


ид. – виртуальной - стр.

Диск. – адрес

призн. -запись – чтение

Характеризует текущее использование страницы (см. ниже).

Указывает на защиту страницы по записи после загрузки последней

Указывает на то, что содержимое страницы было изменено некоторым процессом


Указывает время, прошедшее с момента последней адресации к странице


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


Идентификатор виртуальной страницы в таблице карт

Адрес образца данной страницы на диске

Указывает на то, что элемент должен быть считан или записан на диск



Активная физическая страница может пребывать в четырех состояний, определенных полем СТАТУС - СТРАНИЦЫ. Соответствующие значения статуса.



Значение

Назначение

0

1

2

3

Страница активна

Страница находится в очереди на удаление

Страница недоступна (т.е. находится в режиме удаления или загрузки)

Страница доступна для выделения ее некоторому процессу



Страница может быть защищена от записи в нее информации процессом. В системах с реентерабельными программами страницы часто подразделяются на содержащие кодовые сегменты и содержащие сегменты данных. Все страницы, содержащие кодовые сегменты, имеют ПРИЗН-АКТИВНОСТН, установленный в единицу. ПРИЗН-ИЗМЕНЕНИЯ указывает те страницы, содержимое которых было изменено. Если необходимость присутствия страницы в рабочем наборе отпадает и ПРИЗН-ИЗМЕНЕНИЯ установлен в единицу, она переписывается на диск. ПРИЗН-БЛОКИРОВКИ устанавливается в том случае, если имеется необходимость постоянного присутствия данной страницы в основной памяти. Фактически блокированные страницы никогда не рассматриваются как кандидаты на удаление.

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

Рабочая область менеджера страниц. Для управления страницами менеджеру страниц необходимо рабочее пространство. Это пространство образуется из дополнительных элементов в Блоке Управления Процессом (БУП), а также пространством, отводимым для этого в БУП динамически. Ниже перечисленные элементы дополняют стандартный набор данных процесса:



Мнемоника

Примен

активн-время


квант


текущ-разм-раб-набора


прежний-разм-раб-набора


первая-вирт-стр


адрес-раб-набора

величина-интервала

Процессорное время, истекшее с момента начала работы процесса

Квант процессорного времени, отводимый данному процессу


Текущий размер рабочего набора, отводимого данному процессу

Размер рабочего набора к концу предыдущего активного периода


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

Адрес рабочего набора для данного процесса

Время, остающееся в текущем рабочем интервале



Величина АДРЕС-РАБ-НАБОРА определяет то место в БУП, где находится информация о текущих страницах рабочего набора. О каждой странице рабочего набора поддерживается следующая информация: идентификатор виртуальной страницы, адрес страницы на диске и признак защиты записи. Число элементов указывается в ТЕКУЩ-РАЗМ-РАБ-НА-БОРА.








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

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

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

Сбой страницы. Запрашиваемая страница в текущий момент отсутствует в памяти, поэтому процесс блокируется на время ее загрузки.

Переполнение рабочего набора. Число страниц, запрошенное процессом, превысило максимально разрешенное число страниц в его рабочем наборе, вследствие чего он помещается в очередь на выполнение.

Ошибка адресации. Была сделана ссылка по недопустимому адресу, вызвавшая прекращение работы процесса.

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

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

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

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

Если квант процессорного времени еще не исчерпан, процедура проверяет, есть ли время на то, чтобы модифицировать размер рабочего набора. ВРЕМЯ-РАБ-НАБОРА - это число рабочих периодов (обычно четное число), требуемое для вычисления рабочего набора. Число свободных страниц модифицируется в соответствии с произошедшими изменениями. Процесс затем помещается в очередь выполняющихся процессов, ожидая начала своего рабочего периода. Процедура ЦИРКУЛЯЦИЯ помещает процесс в очередь выполняющихся процессов согласно установленным критериям (т.е. приоритет, “первый поступивший первым обслуживается” и т.д.).

Обработка страничных сбоев. При обнаружении УУП прерывания по сбою страницы для загрузки требуемой страницы вызывается процедура СБОЙ-СТРАНИЦЫ. Поскольку эта страница отсутствует в таблицах трансляции, она, следовательно, не принадлежит рабочему набору и должна быть загружена в память. Размер рабочего набора увеличивается на единицу. Значение таймера интервалов сохраняется в рабочем пространстве процесса до того момента, пока страница не будет загружена в память. Это значение затем записывается в таймер интервалов, давая возможность процессу завершить свой рабочий период.








 PROCEDURE перерыв-по-таймеру-иитервалов [процесс]
  INCREMENT активн-время [процесс] ВУ рабоч-период
  SET рабоч-период ТО величина-интервала[процесс]
  IF активн-время[процесс]>=квант[процесс]
  ТНЕN
   деактивизировать (процесс, очередь-на-вып)
  ELSE
   IF активн-время [процесс] < (рабоч-период + время-раб-набора)
   THEN
    IF активн-время [процесс] > = время-раб-набора
    THEN
    прежний-разм-раб-набора — текущ-разм-раб-набора ->изменение-раб-набора
    INCREMENT число-своб-страннц BY изменение-раб-набора
   ENDIF
  ENDIF циркуляция [процесс]
 ENDIF
 ENDPROC

Процедура предполагает, что страница отсутствует в памяти. (Отметим, что в действительности страница может присутствовать в памяти в качестве члена предыдущего рабочего набора). Процедура ПРОВЕРИТЬ-ТАБЛИЦУ-СТРАНИЦ используется для выяснения того, находится ли страница физически в памяти.

Если УСПЕХ равен единице, то страница находится в памяти и располагается в одной из очередей менеджера страниц. Страница извлекается из очереди добавляется к списку страниц, образующих рабочий набор процесса. Дескриптор страницы устанавливается в активное состояние и сохраняется в таблице карт процесса. Если страница находилась в списке доступных страниц, переменные СЧЕТЧИК-ДОСТУПНЫХ-СТР и СЧЕТЧИК-НАЗНАЧЕННЫХ-СТР увеличиваются на единицу. СЧЕТЧИК-НАЗНАЧЕННЫХ-СТР содержит число реальных страниц, отведенных менеджеру страниц в противоположность страницам, отведенным различным пользовательским процессам.

Если УСПЕХ равен нулю, то это означает, что реальная страница отсутствует в памяти. Процедура проверяет, имеются ли еще страницы, отведенные менеджеру страниц. Если таких нет, страница для замены должна быть выбрана из текущего рабочего набора самого процесса. Процедура ПОГЛОТИТЬ (не описывается) выбирает соответствующую страницу, если выполняющийся процесс (исключая системный) — единственный. В противном случае процесс помещается в очередь для повторной обработки планировщиком, ожидая появления доступной страницы, освобожденной другим процессом. Запрашиваемая страница помещается в очередь на ввод на то время, пока процесс ожидает окончания ее загрузки в память, а соответствующие счетчики модифицируются.








PROCEDURE сбой-страницы (виртуальная-стр, реальная-стр)
CLEAR успех
INCREMENT текущ-размер-раб-набора [процесс]
читать-тайнер-интервалов() -> величина-интервала [процесс]
IF реальная-стр = 0
THEN проверить-таблицу-страниц (реальная-стр, виртуальная-стр, процесс, адрес-очереди) -> успех
ENDIF
IF успех = 1
THEN отделить-дескриптор-стр (реальная-стр, адрес-очереди, адрес-дескриптора-стр) DECREMENT счетчик-свободных-страниц
IF адрес-очереди =список-доступных-стр
THEN DECREMENT счетчик-доступп-стр
DECREMENT счетчик-назначенных-стр
ENDIF
добавить-дескриптор-стр (реальная-стр,список-процессов [процесс],адрес-дескриптора-стр)
SET 1 ТО призн-активност [адрес-буф-динам-трансляц]
сохр-карту(виртуальная-стр, адрес-буф-динам-трансляц)
ELSE IF счетчик-назначенных-стр =0
THEN IF счетчик [очередь-на-вып] = <0
THEN
поглотить (реальная-стр, список-процессов [процесс])
DECREMENT текущ-размер-раб-набора
ENDIF
ELSE деактивизировать(процесс, очередь-на-вып) ENDIF
поставить-в-очер-на-ввод (процесс, виртуальная-стр)
DECREMENT счетчик-назначенных-стр
DECREMENT счетчик-свободных-стр
ENDIF
ENDPROC

Проверка элементов таблицы страниц. Эта процедура, приведенная в модуле 3, просматривает таблицу страниц, проверяя, присутствует ли физически в памяти страница, указанная в таблице карт. Возможны два варианта.

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

2. В противном случае страница не принадлежит требуемой рабочей области и переменная УСПЕХ устанавливается в нуль.

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

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

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

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

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

Отметим также, что процедура ПОСТАВИТЬ-В-ОЧЕР-НА-ВВОД вызывает вспомогательную процедуру УДАЛИТЬ-СЛЕ-ДЫ. Эта процедура (не приводится) удаляет всю информацию из дескриптора физической страницы, которая могла оставаться от таблицы карт другого процесса. Мы создаем связь между физическими страницами и соответствующими им виртуальными страницами только с целью обеспечения наибольшей гибкости определения принадлежности страниц соответствующим процессам.

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








PROCEDURE проверить-таблицу-страниц(реальная-стр, вирт-стр, адр-очереди -> успех)
вирт-стр -> виртуальная-стр
адр-очереди ->очереди
загрузить-дескриптор-стр (реальная-стр, адрес-дескриптора-стр)
IF виpтуaльнaя-cтp<мaкc-числo-виpт-cтp [процесс]
THEN IF статус-страницы (адрес-дескриптора-стр) = 2
THEN IF виртуальная-стр — ид-виртуальной-стр [адрес-дескриптора-стр]
THEN IF процесс-ид-процесса [адрес-дескриптора-стр]
THEN
SET I TO успех
ELSE CLEAR успех ENDIF
ENDIF
ENDIF
ENDIF
IF успех = I
THEN IF статус-страницы [адрес-дескриптора-cтp] = 1
THEN SET список-обменных-стр TO адрес-очереди ELSE SET список-обменных-стр TO адрес-очереди ENDIF
ENDIF
ENDPROC

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

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

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

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








PROCEDURE поставить-в-очер-на-ввод(процесс, виртуальная-стр)
IFсчетчик-назначенных-стр= 0
THEN удалить-дескриптор-стр(реальная-стр, список-доступных-стр,адрес-дескриптора-стр) DECREMENT список-доступных-стр
ид-процесса (адрес-дескриптора-стр, процесс) -> адрес-процесса
ид-виртуальной-стр [адрес-дескриптора-стр] -> ид-вирстр
удaлить-следы(ид-виpcтp, адрес-процесса)
CLEAR статус-страницы [адрес-дескриптора-стр]
SET виртуальная-стр ТО ид-виртуальной-стр [адрес-дескриптора-стр]
сохр-защиту-записи (виртуальная-стр, процесс) -> защита-зaпиcи [адрес-дecкpиптopa-cтp]
CLEAR призн-изменения [адрес-дескриптора-стр]
CLEAR счетчик-использ [адрес-дескриптора-стр]
процесс-> ид-процесса [адрес-дескриптора-стр]
сохр-адр-на-диске (виртуальная-стр, процесс) -> диск-адрес[адрес-дескриптора-стр]
CLEAR призн-запись-чтепие [адрес-дескриптора-стр]
сохр-дескриптор-стр(реальная-стр, адрес-дескриптора-стр)
запрос-к-очереди(реальная-стр)
приостановить (процесс)
ELSE деактивизировать (процесс, очер-ожидапия-стр)
SET виртуальная-стр ТО требуемая-вирт-стр[процесс]
ENDIF
IF первая-стр[список-обменных-стр]=0
THEN удалить-дескриптор-стр(реальная-стр, список-обменных-стр, адрес-дескриптора-стр) SET 1 ТО призн-запись-чтение[адрес-дескриптора-стр]
сохр-дескриптор-стр (реальная-стр, адрес-дескриптора-стр)
запрос-к-очереди (реальная-стр)
ENDIF
ENDPROC







PROCEDURE прерывание-по-обмену-с-диском (режим-передачи-стр, яд- страницы, процесс)
сохр-регистры (процесс)
IF режим-передачи-стр-ввода-страницы
THEN загрузить-дескриптор-страницы (ид-страницы, адрес-дескриптора-стр)
установить-эленент-карты (ид-страницы, адрес-дескриптора-стр)
ид-процесса (адрес-дескриптора-стр) ->адрес-процесса
список-процессов [адрес-процесса] -> текущая-очередь
добавить-процесс(адрес-процесса, очередь-на-вып)
ENDIF
IF режим-передачи-стр = вывод-страницы
THEN дoбaвить-деcкpиnтop-cтp(ид-cтpaнцы, список-доступных-етр, адрес-дескриптора-стр) INCREMENT счетчик-доступных-стр
IF начало[список-ожидания-стр] =0
THEN удалить-процесс(текущ-процесс, список-ожидания-стр)
требуемая-вирт-стр[текущ-процесс] -> ид-вирстр
поставить-в-очер-на-ввод (текущ-процесс,ид-вирстр)
ENDIF
ENDIF
восстановить-регистры (процесс)
ENDPROC

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

Процедура, выполняющая эти операции, приведена в модуле 6. Для модификации размера рабочего набора процедура использует активное время самого процесса. Процедура ОСВО-БОДИТЬ-СТРАНИЦУ удаляет каждую страницу рабочего набора процесса из таблицы страниц и помещает ее в список доступных страниц или список обменных страниц. Процесс удаляется из очереди на выполнение и помещается в очередь, указанную вызывающей программой. Вектор состояния процесса (т.е. регистры и т.д.) сохраняется в БДП, а из очереди на выполнение извлекается следующий процесс и инициализируется. Отметим, что очередь реальных страниц, первоначально назначенных “деактивизированному” процессу, присваивается теперь новому процессу.

Освобождение страницы процесса. Реальная страница, принадлежащая процессу, может быть освобождена (т.е. изъята у него) по двум причинам:
1) процесс выведен из активного состояния;
2) страница “поглощается”, так как рабочий набор переполнен.

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

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

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

Программа, реализующая функции менеджера страниц, приведена в модуле 8. Она сканирует таблицу страниц в поиске тех находящихся в памяти страниц, обращения к которым не было в течение последних J секунд (т.е. таких, для которых: счетчик - использования больше или равен J). Любая найденная страница, удовлетворяющая этому условию, “отбирается” у владеющего ей процесса. Размер рабочего набора процесса уменьшается на единицу и страница освобождается. Затем менеджер страниц ищет в списке готовых к выполнению такие процессы, чей рабочий набор может быть размещен в памяти. Найденный процесс удаляется из списка, а его статус устанавливается в состояние "ожидание-страницы”. Первая страница, необходимая для инициализации выбранного процесса, помещается в очередь на ввод.








PROCEDURE деактивизировать (процесс, адрес-очереди)
активн-время [процесс] -> текущ-активн-вр
CLEAR активн-время [процесс]
список-процессов [процесс] -> текущая-очередь
IF текущ-активн-вр> =текущ-разм-раб-набора
THEN IF прежний-разм-раб-набора<текущ-разм-раб-набора[процесс]
THEN текущ-разм-раб-набора[процесс] -> прежний-разм-раб-набора [процесс]
ENDIF
ENDIF
CLEAR текущ-разм-раб-набора[процесс]
первая-стр (текущая-очередь) -> следующая-сти
WHILE следующая-стр = 0
DO следующая-стр -> ид-страницы
отделить-дескриптор-стр(ид-страницы, адрес-дескриптора-стр)
освободить-страницу(ид-страницы, адрес-дескриптора-стр)
связь-вперед(адрес-дескриптора-стр) -> следующая-стр
ENDDO
удалить-процесс (процесс, очередь-выполняющихся-проц)
добавить-процесс (процесс, адрес-очереди)
сохранить-вектор-сост (процесс)
выбрать-следующ-проц(процесс, очередь-выполняющихся-проц)
текущая-очередь -> список-процессов [процесс]
загрузить-вектор-сост (процесс)
установить-таймер-интервалов (величина-интервала [процесс])
ENDPROC







PROCEDURE освободить-страницу(ид-страницы, адрес-дескриптора-стр)
IF призн-иэменения [адрес-дескриптора-стр] = 1
THEN добавить-дескриптор-стр (ид-страницы, список-обменных-стр, адрес-дескриптора-стр)
ELSE добавить-дескриптор-стр (ид-страницы, список-доступн-стр, адрес-деосриптора-стр)
INCREMENT счетчик-доступных-стр
ENDIF
INCREMENT счетчик-назначепных-стр
INCREMENT счетчик-свободных-страниц
ENDPROC







PROCESS менеджер-страниц
FOR ид-страницы FROM 0 ТО макс-число-реальных-сто
DO загрузить-дескриптор-страницы(ид-страяицы, адрес-дескриптора-стр)
IF статус-страницы [адрес-дескриптора-стр] =0
THEN IF ид-процесса[адрес-дескриптора-стр] не блокирован
THEN INCREMENT счетчик-использования [адрес-дескриптора-стр]
IF счетчик-использования [адрес-дескриптора-стр]>= время-раб-набора
THEN ид-процесса[адрес-дескриптора-стр]-> адрес-процесса
INCREMENT текущ-разм-раб-набора [адрес-процесса]
список-процессов(адрес-процесса]-> текущая-очередь
отделить-дескриптор-стр(ид-страницы, текущая очередь, адрес-дескриптора-стр)
освободить-страницу(ид-страницы, адрес-дескриптора-стр)
ENDIF
сохранить-дескриптор-стр (ид-страннцы, адрес-дескриптора-стр)
ENDIF
ENDIF
ENDDO
CLEAR размер-раб-набора
CLEAR неудача
WHILE неудача =0
DO DECREMENT счетчик-своб-страниц BY размер-раб-набора
просмотр-очереди-на-вып(размер-раб-набора, неудача,адрес-процесса)
IF неудача = 0
THEN первый-запрос[адрес-процесса]->виртуальная-стр
отделить-процесс (адрес-процесса, очередь-на-вып)
поставить-в-очер-на-ввод(адрес-процесса, виртуальная-стр)
ENDIF
ENDDO
ENDPROCESS







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








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

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

  • генерация нового задания;
  • постановка задания в очередь для ожидания момента освобождения процессора;
  • выборка задания из очереди при освобождении процессора после обслуживания очередного задания.







Считается, что в распоряжении вычислительной системы имеется N байт оперативной памяти для размещения рабочей области процесса и M (1<=m<=3) ресурсов R1,R2,…,Rm, обращение к которым переводит процесс в состояние ожидания.

Каждый процесс характеризуется:
– именем;
– длиной рабочей области;
– интервалом непрерывного выполнения;
– причиной прекращения непрерывной работы (обращение к ресурсу или завершение работы);
– приоритетом.

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








В данной работе реализованы все ниже перечисленные варианты организации заданий.

Генерация нового задания (процесса) может происходить:
– в интерактивном режиме по запросу пользователя;
– автоматически системой как случайное событие.

Приоритет генерируется:
– случайным образом;
– устанавливается пользователем.

Размещение в ОП происходит одним из методов:
– первого подходящего;
– наиболее подходящего;
– наименее подходящего;
– дефрагментация.

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

Варианты организации очереди:
– упорядоченный список;
– неупорядоченный список;
– частично упорядоченный список и переупорядочивается через Т единиц времени;
– круговорот;
– эгоистический круговорот.

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

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

Варианты вытеснения:
– с вытеснением;
– без вытеснения.

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








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



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












Прежде всего о некоторых ограничениях. Количество процессов и ресурсов ограничено только количеством памяти на компьютере. Количество строк в окне 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; {Тактовый генератор}






Главная форма

Главная форма.



Кнопки:
New Process Manual –Открыть окно редактирования данных для нового процесса.
New Process Random – Создать новый процесс случайным образом.
New Resource – Открыть окно редактирования данных для нового ресурса.
Memory Scheduler – Открыть окно планировщика памяти.
CPU & Resource Scheduler – Открыть окно планировщика ресурсов.
New Tact – Выработать новый такт. Запуск системы имитации.
EXIT – Выход из программы.

Флажки:
Auto Generation For Priority – Включить режим авто генерации для приоритета.
Auto Generation For Process – Включить режим авто генерации для процесса.

Информационные поля:
Tact Counter – Счетчик тактов.
Number Of Resources – Число ресурсов в системе (кроме процессора).
Number Of Processes – Число процессов в системе.
Number Of Terminated Processes – Число законченных процессов.
Number Of Receiveded Processes – Число поступивших процессов.
Number Of Rejected Processes – Число отвергнутых процессов.
CPU Down Time – Время простоя процессора.
Report – Окно для вывода информации о всех действиях происходящих в системе.

Меню в Главной форме

Меню в Главной форме.



Exit – Выход из программы
Report – Работа с рапортом

Save – Сохранить рапорт
Save As … – Сохранить рапорт как …
About – О создателях

Редактирование данных процесса

Редактирование данных процесса.



Кнопка:
OK – Завершение редактирования данных процесса.

Поля ввода:
Name – Имя процесса.
Need Resource – Необходимый ресурс (в очередь к которому процесс станет).
Work Length – Длина рабочей области.
Priority – Приоритет.
Interval Of Unceasing Execution – Интервал непрерывного выполнения.
Full Interval Of Execution – Полный интервал выполнения.
Interval Before Termination – Интервал оставшийся до завершения.
Terminate Reason – Причина прекращения.
Quantum For Rotation – Квант для круговорота.
Quantum Before Rotation – Квант оставшийся до круговорота.

Информационные поля:
Start Address – Стартовый адрес в ОП.
State – Состояние.

Редактирование данных ресурса

Редактирование данных ресурса.<



Кнопка:
OK – Завершение редактирования данных ресурса.

Флажок:
With Pulling – Включить режим вытеснения. При круговороте вытеснение включено всегда.

Переключатель:
Queue Organization – Организация очереди.

Ranked List – Упорядоченный список.
UnRanked List – Неупорядоченный список.
Partly Ranked List – Частично упорядоченный список.
Rotation – Круговорот.
Selfish Rotation – Эгоистический круговорот.

Поля ввода:
Number & Name – номер и имя ресурса.
Interval For Regularize – Интервал для упорядочения. Поле активно если установлен частично упорядоченный список.

Информационное поле:
State – Состояние.

Планировщик памяти.



Кнопки:
To Previous – К предыдущему пользователю.
To Following – К последующему пользователю.
Info – Полная информация о текущем пользователе.
Delete Process – Удалить текущий процесс.
Edit Process – Открыть окно редактирования данных для текущего процесса.
New Process Manual – Открыть окно редактирования данных для нового процесса.
New Process Random – Создать новый процесс случайным образом.
Memory Defrag – Дефрагментировать память.
OK – Завершение редактирования данных ресурса.

Переключатель:
Memory Sharing – Распределение памяти.

First-Fit – Первого подходящего.
Best-Fit – Наиболее подходящего.
Worst-Fit – Наименее подходящего.
Defragmentation – Дефрагментация.

Поле ввода:
Memory Available – Памяти доступно. Поле активно если список пользователей памяти пуст.

Информационные поля:
Name – Имя процесса.
Need Resource – Необходимый ресурс (в очереди к которому процесс стоит).
State – Состояние.
Work Length – Длина рабочей области.
Start Address – Стартовый адрес в ОП.
Before Termination – Интервал оставшийся до завершения.
Number Memory User – Число пользователей памяти.
Memory All – Памяти всего.
Memory Used – Памяти использовано.
Memory Free – Памяти свободно.
Free Memory Blocks – Свободные блоки памяти.

Планировщик ресурсов

Планировщик ресурсов.



Кнопки:
To Previous – К предыдущему ресурсу.
To Following – К последующему ресурсу.
Info – Полная информация о текущем ресурсе.
Delete Resource – Удалить текущий ресурс.
Edit Resource – Открыть окно редактирования данных для текущего ресурса.
New Resource – Открыть окно редактирования данных для нового ресурса.
To Previous – К предыдущему пользователю текущего ресурса.
To Following – К последующему пользователю текущего ресурса.
Info – Полная информация о текущем пользователе.
Delete Process – Удалить текущий процесс.
Edit Process – Открыть окно редактирования данных для текущего процесса.
New Process Manual – Открыть окно редактирования данных для нового процесса.
New Process Random – Создать новый процесс случайным образом.
OK – Завершение редактирования данных ресурса.

Информационные поля:
Number & Name – Имя ресурса.
State – Состояние.
Pulling – Тип вытеснения.
Total Interval Used – Полное время использования ресурса.
Number Of Users – Число пользователей ресурса.
Queue Organization – Тип организации очереди.
Name – Имя процесса.
Priority – Приоритет.
State – Состояние.
Unceasing Execution – Интервал непрерывного выполнения.
Before Termination – Интервал оставшийся до завершения.
Need Resource – Необходимый ресурс (в очереди к которому процесс стоит).

 








  1. Кейслер С. Проектирование ОС. – М.: Мир, 1986. –680с., ил.
  2. Касаткин А.И. Управление ресурсами. – Минск: ВШ, 1991. –325с., ил.
  3. Кинг Д. Создание эффективного ПО. –М.: Мир, 1991. –325с., ил.
  4. Коршикова Л. А. и др. Многозадачная операционная система. Моделирование функций.
    Методические указания к лабораторным работам.- Новосибирск, НГТУ, 1998. -25с., ил.