Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

Таблица 11.3

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

Таблица 11.4

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

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

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

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

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

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

T=0

…

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

…

T=T+1

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

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

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

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

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

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

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

Задание

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

Таблица 11.5

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

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

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

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

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

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

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

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

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

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

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

(RATBL) (PWTBL)

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

нет

KK’ Клинч

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

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

запросу

Выход

Рис. 12.1

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

Есть три процесса P₁, P₂, P₃ и ресурсы L₁, L₂, L₃, L₄, L₅.

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

RATBL

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

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

7) P₂ пытается обратиться к L₂ :

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

8) P₃ пытается обратиться к L₅: PWTBL

J=3, I=5,

I’=2,

K’=3,

K’=J  клинч

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 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 значениями.

Лабораторная работа №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].

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

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

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

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

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

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

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

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

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

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

1. Есть два процесса p₁ и p₂ и один ресурс R;

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

Задание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• простота,

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

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

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

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

• гибкость,

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

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

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

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

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

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

Задание

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

Характеристики

Список файлов лабораторной работы