Ещё что-то по лабораторным работам (SisPr10)

Посмотреть архив целиком

21



МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)










Кафедра 304







ЭЛЕМЕНТЫ ОПЕРАЦИОННЫХ СИСТЕМ ЭВМ

Лабораторные работы




Ю.А.Голубков















Москва, 2001





Лабораторная работа №10

АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ МУЛЬТИПРОГРАММНЫХ

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ


В данной лабораторной работе определение производительности мультипрограммной ВС с равномерным квантованием времени и учетом ввода-вывода будет рассмотрено по методу, описанному в работе Дрейка.

10.1. Анализ влияния параметров ВС на производительность


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

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

S0 - все процессы, кроме одного, находятся в состоянии готовности, один из них выполняется;

Si - i процессов находятся в состоянии ожидания ввода-вывода;

Snвсе n процессов ожидают завершения обмена, т.е. процессы блокированы, процессор простаивает.

Требуется оценить вероятность Pn пребывания системы в состоянии Sn.

Диаграмма состояний и переходов аналогична модели марковского процесса размножения-гибели приведена на рис.10.1.


а) запрос

на вв/выв


dt dt dt … dt


S0 S1 S2 Sn

dt 2dt 3dt ndt


завершение вв/выв


Рис. 10.1


Дуга перехода определена вероятностью этого перехода. Определим dt как вероятность блокировки обслуживаемого процесса вследствие выдачи им запроса на ввод-вывод к моменту следующего наблюдения (1/ - представляет средний интервал между запросами на ввод-вывод). Аналогично dt представляет вероятность завершения ввода-вывода к следующему моменту наблюдения (1/ - среднее время обслуживания запроса на ввод-вывод). Следует обратить внимание, что дуга перехода из S2 в S1 имеет вес 2dt. Это следует из предположения, что оба запроса на ввод-вывод независимо обслуживаются отдельными каналами и вероятность того, что к следующему моменту закончится выполнение хотя бы одного из запросов, равна


dt + dt = 2dt


По аналогии переходу из состояния i в (i-1) соответствует вероятность idt. Для систем без мультипрограммирования процент времени ожидания ввода-вывода

Для упрощения модели предполагается, что:

1) число переходов Si Si+1 равно числу переходов Si+1 Si (выполняется условие стационарности Pi,i+1 Pi= Pi+1,i Pi+1 ).

Отсюда имеем:

dt P0=dt P1

dt P1=2dt P2 (7.1)

. . .

dt Pn-1=ndt Pn


2) Сумма вероятностей по всем состояниям системы

Далее можно определить вероятность Pn пребывания системы в состоянии Sn (когда все процессы блокированы, а процессор простаивает).

Из приведенной системы (7.1) следует:






Так как

Поскольку

Отсюда имеем:

Из системы (7.2) имеем:

Используя выражение для P0, получим:

Тем самым можно построить таблицу для различных значений n и 0.1  0.95. Заметим, что  определяет коэффициент загрузки процессор – канал – УВВ.


10.2.Анализ влияния синхронизации на производительность ВС


Предполагается, что в системе используется n процессоров, где n1 (от 10 и больше). При работе мультипроцессорной системы следует различать два различных типа блокировок процессоров. Они различаются по тому, как используется процессор, обслуживающий прерванный процесс. Если при использовании семафоров для ожидания завершения обмена процессор освобождается и может обслуживать другой процесс, то в других случаях это не так. При использовании процессором команд типа TS (Text and Set) процессор вынужден непрерывно повторять цикл проверки байта блокировки ресурса до тех пор, пока он не будет сброшен в 0. Тем самым процессор «связывается» с ресурсом и не может использоваться до освобождения ресурса. Поэтому первый тип блокировки ресурса, при котором процессор может переключаться на обслуживание другого процесса, называется «освобождающей», а второй – «связывающей».

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

Пусть в ходе выполнения отдельного процесса интервалы времени между обращениями к базе данных подчиняются обратному экспоненциальному закону распределения с параметром 1/E (т.е. математическое ожидание интервала времени между обращениями равно Е). Пусть математическое ожидание продолжительности интервала блокировки процессора равно L. Тогда отношение L/(E+L) дает грубую оценку доли времени пребывания ресурса в состоянии блокировки в мультипрограммной системе с одним процессором, (блокировки процессора не происходит). В мультипроцессорной системе каждый процессор может быть в одном из состояний:

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

  2. заниматься обработкой ресурса, защитив его байтом блокировки на период времени, характеризуемый параметров 1/L;

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

Н



а рис.10.2 каждое состояние Si отвечает ситуации, когда i процессоров пытаются получить доступ к базе данных. Один из них работает с базой данных, остальные i-1 ожидают ее освобождения.



S0 S1 S2 Sn-1 Sn







Рис. 10.2


Вероятность перехода из состояния i в состояние i-1 за время dt равна (1/L)dt. Это означает, что время обработки процессором блокированного от посторонних воздействий базового ресурса не зависит от числа процессоров, ожидающих его освобождения. Вероятность перехода из состояния i в состояние i+1 на интервале dt равна (n-1)(1/E)dt. Это соответствует тому факту, что каждый из еще не заблокированных (n-i) процессоров может запрашивать доступ к блокированному ресурсу с вероятностью (1/E)dt. Повторяя рассуждения, приведенные ранее для стационарного процесса, получаем, что:

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

Из приведенных соотношений:

Задание 10.1.


Спроектировать программу для определения состояния простоя процессора и построить графики для n=115 c шагом 1 и двух значений 


бригады

1

2

3

4

5

6

7



0,1; 0,6

0,15; 0,65

0,2; 0,75

0,3; 0,8

0,4; 0,85

0,5; 0,95

0,25; 0,9



Задание 10.2.

Спроектировать программу для определения таблицы значений Eпр при варьировании параметров:

Число процессоров n=5,10,20,30,40,50 и (L/E) = 0.025, 0.05, 0.10, 0.20.


бригады

1

2

3

4

5

6

7

E/L

0,025

0,1

0,05

0,15

0,01

0,2

0,15

0,3

0,1

0,15

0,02

0,2

0,01

0,1













Лабораторная работа №11

Предотвращение тупиков по методу Дейкстры

(алгоритм банкира)



Тупиковой ситуации при распределении ресурсов ВС можно избежать, если рационально распределить ресурсы. Алгоритм Дейкстры имитирует действия банкира, который, располагая капиталом, выдает ссуды и принимает платежи. Его трансформация для процессов может быть представлена в такой форме.

Предположим, есть совокупность (пул) идентичных ресурсов в количестве t (например, НМЛ). Есть некоторое число процессов n. Пусть заранее известна максимальная потребность каждого процесса в ресурсе m(i), где i=1,..,n, необходимая ему для завершения. Ресурсы не выделяются процессу заранее до начала выполнения, а лишь по запросу в рамках текущего выполнения.

Пусть l(i) - текущее количество ресурса, уже выделенное процессу i, i=1,...,n, c(i) - текущая потребность, которая равна:


c(i) = m(i) - l(i), i=1,...,n.

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

.

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


Пример надежного состояния

В системе t=12. Число процессов n=3. Состояние системы определено таблицей 11.1.

Таблица 11.1

Процесс

Текущее выделение


Максимальная потребность

процесс 1

процесс 2

процесс 3


1

4

5


4

6

8

Резерв


2



В данном состоянии в резерве есть 2 единицы свободного ресурса. Если удовлетворить процесс 2, блокируя другие процессы, то он может завершить работу и освободить шесть единиц ресурса. Эти единицы ресурса можно отдать процессу 1 и процессу 3 для их завершения.

Пример ненадежного состояния системы приведен в таблице 11.2, где n=3, t=12.

Таблица 11.2

Процесс

Текущее выделение


Максимальная потребность

процесс 1

процесс 2

процесс 3


8

2

1


10

5

3

Резерв


1



Здесь в данный момент из 12 единиц ресурса 11 в работе, в резерве 1. Независимо от того, какой процесс запросит резервное устройство, нет гарантии, что все три процесса завершат работу.


Пример перехода системы из надежного в ненадежное состояние.

Если известно, что состояние надежное, то это не гарантирует, что все последующие надежные. Механизм распределения ресурсов должен анализировать все запросы до их удовлетворения. Пример: текущее состояние определено таблицей 11.3, а переход в ненадежное - таблицей 4. n=3, t=12.


Таблица 11.3

Процесс

Текущее выделение


Максимальная потребность

процесс 1

процесс 2

процесс 3


1

4

5


4

6

8

Резерв


2



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

Таблица 11.4

Процесс

Текущее выделение


Максимальная потребность

процесс 1

процесс 2

процесс 3


1

4

6


4

6

8

Резерв


1


Здесь получается, что ни один процесс не может завершиться, т.е. имеет место тупик.

Из приведенных рассуждений можно сделать следующие выводы:

1. Пусть есть n процессов: .

2. Для каждого процесса известны: максимальная потребность единиц ресурса m(i), где m(i)

3. Предполагается, что в момент T=0 все процессы начинаются одновременно и получают по единице ресурса, следовательно n Допускается, что процессы выполняются в режиме равномерного квантования. Это означает, что если истекает единица условного времени, то на долю каждого работавшего процесса приходится этого времени, где na - число фактически работающих процессов (активных), т.к. некоторые могли быть заблокированы.

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



T=0



FOR I=0 TO 10000 DO x=x+0,09111



T=T+1




Цикл FOR замедляет работу программы и позволяет отслеживать события, имитируемые программой.

5. Очевидно, что каждый процесс отражается строкой таблицы процессов:

маркер - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




Номер процесса

Активен или блокирован

m(i)

l(i) ci T(i)

Число получ.

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


времена


6. Очевидно, что вид программы представляет цикл относительно счетчика времени T, который определяет условную единицу времени. Если в рамках этой единицы было активно na процессов, то каждый получил 1/na квант и уменьшит свое Ti на 1/na квант. Если T(i) - становится равным 0, то процесс завершен, его ресурсы свободны и возвращаются в общий пул ресурса.

7. Пусть в некоторый момент T0 было активно na процессов, следовательно единицей времени для активных процессов будет 1/na единицы счетчика Т. После на квант они формируют свои запросы к пулу ресурсов.

8. Выделение ресурсов осуществляется на основе метода Дейкстры таким образом, чтобы система оставалась в надежном состоянии. Для этого необходимо просмотреть таблицу процессов. Пусть число активных процессов равно na . Для этих процессов определить величинуДалее требуется сравнить величину резерва A с . Если то можно удовлетворить все запросы. Если то удовлетворить их все нельзя. Очевидно требуется блокировать один или несколько процессов, оставляя активными те , для которых c(i) минимальные так, чтобы .

9. По истечении времени выполнения процесса, его ресурсы возвращаются в общий пул, т.е. А увеличивается на величину освобожденных ресурсов завершенных процессов. Следовательно, возможно добавить в число активных процессов хотя бы один из блокированных ранее. Для этого необходимо выбрать тот из них, у которого c(i) минимальное. Если позволяет резерв, то можно активизировать несколько процессов. Другой вариант: активизировать процессы, время завершения которых минимально.


Задание

Спроектировать программу, моделирующую выполнение конкурирующих n процессов в системе с t однородными ресурсами, определяемых значениями m(i), временем выполнения T(i). Предусмотреть вывод на экран состояние таблицы процессов через каждую единицу времени выполнения вплоть до полного завершения всех процессов.


Таблица 11.5

бригады

1

2

3

4

5

6

7

n

4

5

3

4

3

5

4

t

10

9

11

12

8

14

12

























Лабораторная работа №12

Обнаружение клинчей (дедлоков)

по методу Бенсуана-Мерфи


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

В основе метода Бенсуана-Мерфи используется следующий подход:

  1. произвольно нумеруются все ресурсы и так же произвольно нумеруются все процессы в системе (но однозначно);

  2. процессы используют программные блокировки при обращении к ресурсам;

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

Вид таблиц распределения и блокирования процессов приведен ниже.


Таблица 12.1 Таблица 12.2

Распределение ресурсов Блокированные процессы

(RATBL) (PWTBL)


номер

ресурса

номер процесса,

которому распределен ресурс


номер

процесса

номер ресурса,

которого ожидает

данный процесс

1



1


2



2


3



3










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

  2. при обработке запроса на уже занятый ресурс выполняется проверка на наличие клинча, согласно алгоритму распознавания клинча (см. рис. 12.1














Запрос от процесса J на

занятый ресурс I.


Пометить номер ресурса I в

PWTBL в строке с номером

процесса J



Использовать I в качестве сме-

щения в RATBL для определения

номера процесса K, который вла-

деет ресурсом


1

Использовать K в качестве сме- 2

щения в PWTBL




Ждет ли

процесс K освобождения нет

какого-либо ресурса I’?

Перевести J в состояние

ожидания (блокировки)

да


Использовать I’ как смещение в Выход

RATBL для поиска номера

блокирующего его процесса K’



K’=J?

нет

да

Конец RATBL? 2

нет

KK’ Клинч


  1. Вернуть J к состоянию,

предшествующему

запросу



Выход


Рис. 12.1



Рассмотрим следующий пример.

Есть три процесса P1, P2, P3 и ресурсы L1, L2, L3, L4, L5.

Последовательность действий:

RATBL



ресурсы

процессы

1)

P1 занимает L1

1

1

2)

P2 занимает L3

2

3

3)

P3 занимает L2

3

2

4)

P2 занимает L4

4

2

5)

P1 занимает L5

5

1


6) P1 обращается к L3; так как L3 занят, требуется проверка по описанному алгоритму; получаем J=1, I=3, K=2.

Процесс K не ждет никакого ресурса, I’ блокировать P1.

7) P2 пытается обратиться к L2 :

J=2, I=2, K=3, нет I’ блокировать P2.

8) P3 пытается обратиться к L5: PWTBL

J=3, I=5,

K=1,

процесс

ресурс

I’=3,

1

3

K’=2,

2

2

2 J, следует взять K=2,

3

5

I’=2,

K’=3,

K’=J клинч

сохранить состояние процесса

P3 для последующего восстановления.

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






















Лабораторная работа №13

Организация справочников


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

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



ключ

адрес записи




k1


ADLER









k2


DONOVAN







Индексная таблица для

записей


k3


MADNIN

















Предполагается, что k1 < k2 < ..., т.е. индексная таблица упорядочена по возрастанию ключей.

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

1. Большая часть записей попадает в файл при его создании, и записи располагаются в файле в отсортированной последовательности.

2. Количество добавляемых или уничтожаемых записей мало (менее 10%), что позволяет минимизировать использование областей переполнения.

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

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


Структура доступа ISAM


Главный индекс Вторичный индекс Область данных


A



ALFALL


ALF

запись

B



ALFALL




C






D






конец







ALM

запись











конец









Y






конец

Z






область переполнения

ключ адрес ключ адрес


Рис. 13.1


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


Справочники файлов

Абстрактное представление иерархической структуры справочника файлов приведено на рис.13.2. Здесь показан главный справочник, в котором содержится информация о пользователях с указанием места расположения справочников их файлов. Заметим, что MATH, доступный пользователю MADNICK, в его справочнике представлен ссылкой на справочник MATH. Нетрудно видеть, что файл 7 доступен из двух справочников по различным именам, а файл SIN - из разных справочников по одному имени. Это отражает проблематику создания справочников, где могут использоваться совместные файлы и файлы с различными именами, но совпадающие. Иерархическая структура справочника более подробно приведена на рис.3. Здесь базовый адрес ID1 в каждой строке содержит номера блоков внешней памяти (MD), которые выделены файлом, другим справочником или пустым. Заметим, что первая строка ID1 содержит указатель на начало базового справочника. Во второй строке ID1 отмечено, что главный справочник ID2, в котором зарегистрированы пользователи, находится в физическом блоке 1, а справочник пользователя DONOVAN содержится в физическом блоке 5, о чем свидетельствует строка ID11, а пользователя MADNICK в физическом блоке 9 (ID12). Содержимое этих справочников показано на рисунке 13.3. Следует заметить, что в справочнике MADNICK отмечены те строки базового справочника, которые содержат указатели на блоки, в которых размещаются соответствующие файлы. Здесь допускалось, что файл имеет размер блока.







Абстрактное представление иерархической структуры

справочника файлов

Главный справочник


DONOVAN


MADNICK






Справочник Donovan Справочник Madnick


MARILIN 3 MARILIN

ETHEL ETHEL

CONE XTAB

SIN 7 MATH

… …


8

  1. 6



SIN


SQRT




Справочник MATH


Рис. 13.2











Поуровневая иерархическая структура

справочника файлов




Базовый справочник файлов ID1 Главный справочник ID2




1 0 DONOVAN 11

2 1 madnick 12 (блок 1)

  1. 2 файл

  2. 3 (Donovan Marilin, …

  3. 6 (блок 2) Madnick Marilin)

6 12 …

7 10

8 15 Имя USER’а ID

9 11

10 4

11 5

12 9


ID номер

(номер блока

строки)



Справочник Справочник Справочник

MADNICK (ID12) DONOVAN (ID11) MATH MADNICK (ID5)


MARILIN 3 MARILIN 3 SIN 8

ETHEL 6 ETHEL 5 SQRT 9

XTAB 7 CONE 7

MATH 10 SIN 8 имя ID

(блок 5)

имя ID имя ID

(блок 9) (блок 4)



Рис. 13.3










Задание

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

1) ключи одинаковой длины и состоят из трех букв;

2) предполагается, что область данных ограничена (не более 100 записей) и область переполнения равна T;

3) диапазон ключей с одинаковой начальной буквой так же ограничен N значениями.


бригады

1

2

3

4

5

6

7

N

4

5

3

4

3

5

4

T

10

9

11

12

8

14

12













































Лабораторная работа №14

СЕМАФОРЫ И СИНХРОНИЗАЦИЯ ПРОЦЕССОВ


Семафор (semaphore) впервые введен в информатику Е. Дейкстрой. В простейшем случае семафор S представляет целочисленную переменную, принимающую неотрицательные значения. Над ней определены две атомарные операции (примитивы, которые нельзя прервать): V(S) и P(S).

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

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

Стандартно эти две операции поддерживаются ядром операционной системы.

Традиционное использование семафорных операций заключается в следующем. С каждым ресурсом связывается индивидуальный семафор. Предполагается, что ресурс может быть после своего освобождения повторно использован. Пусть процесс A обращается к семафору ресурса и запрашивает выполнение V(S) – операции ( хочет получить доступ к ресурсу). Если S был в нулевом состоянии, то он получит значение 1, и ресурс будет занят процессом А. Пусть через некоторое время процесс В обратится к тому же ресурсу с операцией V(S). Считаем, что семафор может иметь только два значения: 0 и 1.

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

Когда процесс А освобождает ресурс, он обращается с операцией P(S). После обнуления S выполняется функция SIGNAL, которая оповещает, что S=0. Следовательно, можно выбрать с помощью диспетчера очереди один из процессов, находящихся блокированных процессов, ожидающих ресурс. Он может повторить операцию V(S) и получить ресурс.

«Скелет» структуры данных, с помощью которых можно описать состояние большого числа ресурсов, разработан Вейдерманом (в 1971 г.). Каждый класс ресурсов требует минимум 3 компоненты:

  1. Опись, включающую число и идентификацию доступных единиц ресурсов.

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

  3. Диспетчер, ответственный за принятие решения, который запрос должен быть удовлетворен и когда.

В простейшем случае структура данных ресурса включает:

  1. семафор ресурса S;

  2. идентификатор ресурса ID[S];

  3. список доступности Avail[S];

список ожидающих процессов Waiters[S];

  1. точка входа в распределитель (диспетчер) Blocator[S].

Ссылка Avail[S] указывает на начало списка доступности или опись для семафора ресурса. Список в заголовке может содержать также указатели (точки входа) для двух стандартных программ. Одна – для вставки новых элементов (освобожденных ресурсов), другая – для удаления распределенных ресурсов.

Таким образом здесь предполагается, что список содержит несколько идентичных единиц ресурса. Список ожидающих процессов содержит все процессы, заблокированные на семафоре ресурса. Списки ожидания могут иметь различный вид. Запись о каждом процессе содержит его идентификатор и информацию о запросе на ресурс. В простейшем случае список содержит один элемент. Часто указатель на список в очереди Waiters[S] показывает на очередь (типа FIFO). Вид этой очереди содержит заголовок очереди с последующими элементами очереди.

Заголовок очереди:

  1. Точка входа в стандартную программу вставки – Insert[q];

  2. Точка входа в стандартную программу удаления – Remove[q];

  3. Первый элемент – First[q];

  4. Последний элемент – Last[q].

Элемент очереди представляется в виде:

  • идентификатор процесса – pi (часто указатель на дескриптор процесса);

  • элемент diдополнительные сведения о запросе;

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

В простейшем случае диспетчер процессов имеет форму – Allocator(r,k,L),

где k и L – это выходные параметры со значениями:

  1. k – число незаблокированных процессов, которым распределены ресурсы, k>0;

  2. L[i], i=1, … , k – список процессов, которым распределены ресурсы (определен, когда k>0);

  3. r – имя семафора ресурсов.

Исходные допущения:

  1. Есть два процесса p1 и p2 и один ресурс R;

  2. Процессы p1 и p2 обращаются к R раздельно. Обращение процессов к R и освобождение R моделируется пользователем с экрана в некоторой последовательности, определенной пользователем.


Задание.

Требуется разработать:

  1. примитивы V(S), P(S), SIGNA, WAIT, работающие в среде процессов p1 и p2;

  2. структуру данных ресурса R;

  3. структуру указателя описи ресурса;

  4. структуру очереди с ее заголовком;

  5. программу вставки в очередь Insert[q];

  6. программу удаления Remove[q];

  7. распределитель Allocator;

  8. построить программу динамического моделирования обращений к R от двух процессов p1 и p2.



Лабораторная работа №15

ИНТЕРПРЕТАТОР КОМАНДНОГО ЯЗЫКА (ИКЯ)


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

Командная система является полным набором модулей, структур данных и утверждений, которые определяют интерфейс между пользователем и системой. Важный аспект КЯ ОС – форма и содержание языка ответов, который сообщает информацию пользователю.

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

Критериями при проектировании КЯ ОС являются:

  • простота,

  • выразительность или краткость,

  • симметричность (команда должна работать для всех логически допустимых для нее типов данных),

  • легкость чтения,

  • обнаружение и предотвращение ошибок,

  • гибкость,

  • подтверждение, т.е. пользователь должен получать ответ на каждую команду.

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

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

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

Поэтому можно выделить специфический класс обращений к ИКЯ и реализовать его работу в предельно упрощенной форме. ИКЯ можно рассматривать как оболочку в виде циклической программы. В начальной стадии такая программа выводит системное приграшение (так называемый Prompt). Это некоторый спецсимвол типа >, $, . После нажатия клавиши ввода ИКЯ ведет поиск в области таблицы векторов прерывания и, обнаружив требуемый вектор, передает управление подпрограмме, реализующей данную команду. После ее исполнения она возвращает управление ИКЯ, который возвращается на свое начало.

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


Задание

Разработать программу ИКЯ для работы с таблицей вида:

Имя команды

Адрес размещения

ATTRIB


BACKUP


BREAK


CHDIR


CHKDSK


CLS


COMP


COPY


DATE


DEL


ECHO


FIND


LABEL


и т.д.




Случайные файлы

Файл
94942.rtf
71441.rtf
22454.rtf
123777.rtf
10-21.doc