Принципы поддержки нескольких операционных сред.

Задача:

выполнить под управлением одной операционной системы задачи, разработанные в разных ОС.

Реализация:

1. Приложение в своей среде через собственный API обращается к транслятору, который преобразует API данной среды в API базовой ОС и далее выполняется с использованием данной аппаратной платформы.

API (OC2)

транслятор

пользовательский

привилегированный

2. Базовая ОС содержит трансляторы, которые находятся в ядре. API каждой операционной среды обрабатывается соответствующим транслятором и выполняется на данной платформе.

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

		OC4

Третий вариант более надежный, но более медленный.

Вспомогательные модули ОС.

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

Вспомогательные модули, как правило, разделяются на:

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

2. Системные обрабатывающие программы – редакторы, сетевые средства, системы программирования.

3. Обеспечение безопасности.

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

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

Основные компоненты ОС

Основные компоненты ОС
IPL	Ядро	Вспомогательные модули	Общесистемное ПО
	программа NIP	-средства управления файловой системой
	-управление потоками и процессами
	-управление памятью	-средства поддержки и восстановления после сбоев
	-управление вводом, выводом
	-сетевые средства	-средства оптимизации
	-загрузчик
	-средства службы времени	-встроенные средства системы программирования
	-обработчики прерываний
	-API

Процессы и потоки.

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

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

2. Диспетчирование, переключение управления из одного готового процесса на другой (краткосрочная задача, касается непосредственно организации вычислительного процесса).

Создание процесса.

Основные способы создания процесса:

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

2. Выполнение системного запроса на создание процесса (например, в Windows – CreateProcess). Управляет созданием процесса и запуском в его рамках нужного модуля.

3. Запрос пользователя на создание процесса – выполняется из программы с передачей необходимых параметров в процесс, как правило, параметры передаются списком, адрес которого находится в одном из регистров или стеке при начале работы модуля (в ОС Windows порядка 100 функций по управлению процессами).

4. Инициирование пакетного задания – в этом случае в ОС такого типа существуют так называемые макрокоманды, по которым ос или пользователь может создать процессы следующих типов:

- Самостоятельный процесс (макрокоманда ATTACH) – выполняется как отдельная программа, не зависящая от программы-родительницы.

- Создать процесс, выполнить и вернуться в порождающий модуль в точку после вызова процесса (макрокоманда LINK).

- Создать процесс, но не выполнять (макрокоманда LOAD). Например, загрузка каких-нибудь таблиц.

Завершение процесса.

Как правило, процесс завершается в следующих случаях:

1) Штатный выход – после окончания выполнения модуля процесс сообщает ОС о том, что он закончил работу (в Windows ExitProcess).

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

3) Ошибка при выполнении процесса: деление на 0, недопустимая операция, обращение к недействительному адресу и т.п.

4) Уничтожение процесса другим процессом; как правило, осуществляется при выполнении системного вызова (в Windows – TerminateProcess) у процесса-киллера должны быть соответствующие полномочия.

Состояния процесса.

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

1) Выполняющийся – процессу передано управление и он выполняется (предоставлен процессор) – runing.

2) Готовый к выполнению – процесс временно приостановлен, находится в очереди за ресурсом, ждет предоставления процессора(находится в очереди к диспетчеру) – ready.

3) Заблокированный – ожидает завершения какого-то события – locked. Возможная схема реализации:

mov ECB, x'0'

read <файл> , ECB

wait ECB

...

...

...

ECB dc x'0'

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

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

1 - данные о состоянии процесса

-регистры процесса

-счетчик команд

-слово состояния программы

-указатель стека

-приоритет

-идентификатор процесса

-принадлежность процесса (родительский, дочерний)

-время начала выполнения процесса

-использование процессорного времени

-адреса полученных сигналов

2 - данные о памяти процесса

-указатель на таблицу сегментов

-указатель на таблицу страниц

-адреса процесса

-размер выделенной оперативной памяти

-и др.

3 - состояние ввода-вывода процесса (файловой системы)

-текущий каталог

-дескрипторы открытых файлов

-и др.

Как правило, в любой ос поддерживается так называемая, основная управляющая таблица. Каждый элемент таблицы содержит некоторый адрес. Адреса заносятся в таблицу, как правило, на этапе NIP. Эти адреса, в свою очередь, являются ссылками на другие таблицы, кроме того, основная таблица, как правило, содержится в резидентной части ядра по фиксированному адресу для данной ОС и имеет название, например, MCT – main control table, CVT – control vector table и аналогично. Как правило, таблица не подвергается страничному обмену, то есть, она всегда в ОП. В ряде случаев, адрес таблицы могут определить умелые руки по контексту ее названия в дампе оперативной памяти.

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

Потоки.

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

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

Для учета состояния потоков ведутся таблицы, основные значения элементов таблицы следующие:

1) Данные процесса:

-адресное пространство

-глобальные переменные

-открытые файлы

-список дочерних процессов

-обработчики сигналов и аварийных ситуаций

-учет используемых ресурсов

-и другие.

2) Данные потока:

-идентификатор потока

-счетчик команд

-значения регистров

-стек

-адрес потока

-содержимое области сохранения

-другие.

Данные процесса используют все потоки процесса, данные потока индивидуальны для каждого потока.

Состояния потока:

1) Выполняемый.

2) Заблокированный.

3) Готовый к выполнению.

Запуск (создание) потоков, как правило, осуществляется из процесса (в Windows – Thread_Create).

Завершение потока, как правило, осуществляется по процедуре выхода или завершения в процессе(Thread_Exit). Как правило, существует несколько опций по управлению запуском и завершение потоков. Опции указываются в API конкретных ОС. Использование потоков позволяет получить следующие преимущества:

1) Исключить блокировку процесса в случае его однопоточного режима. Пример: если текстовый редактор делать в одном потоке, то обработка входной команды и её выполнение может осуществляться с задержкой, которая не позволит обработать следующую введенную команду. Если делать редактор двухпоточным, первый поток без задержки обрабатывает входные команды, формирует очередь выполнения команд для второго потока, который их выполняет (например, заменяет букву "о" на букву "е" во всем документе - первая команда, меняет шрифт - вторая). Если бы был один поток, то обработку следующей команды надо было бы проводить после редактирования.

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

3) Повысить эффективность вычислительного процесса в целом, разнесением быстрых вычислений и медленных операций (ввода-вывода) по различным потокам.

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

п о т о к и

п о т о к и

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

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

В случае построения ОС по принципу доменов, автономные потоки могут находиться и на различных станциях сети.

Взаимодействие процессов, потоков.

В литературе это называется термином IPC(interprocess communication).

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

1) Передача информации от одного процесса другому.

2) Распределение ресурсов между процессами.

3) Согласование действий процессов над ресурсами.

Второй и третий пункт относятся и к потокам. Пункт 1 для потоков решается просто, так как у них общее адресное пространство и ресурсы.

Взаимоисключение.

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

Рассмотрим, например (рисунок 2.3), программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл "заказов" другие программы. Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой для определенности предположим равным 4. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, в следствие исчерпания кванта). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в четвертую позицию имя своего файла и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию 4, поверх имени файла процесса S.

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

Исключение состояния состязания может быть выполнено, если соблюсти 4 условия:

1) Два процесса одновременно не должны выполнять коды критической секции.

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

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

4) Обработка ситуаций, выполнение кода критической секции не должно строиться на основе предположений о скорости процесса и о количестве процессов.

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

1) Запретом прерываний - осуществляется установкой соответствующих флажков в маске прерываний.

2) Использование переменных блокировки (если процесс хочет перейти в критическую область, процесс считывает значение переменной блокировки; если она равна 0, он меняет её на 1 и заходит, при выходе меняет обратно. Если равна 1 – ждет).

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

4) Использование алгоритма петерсона. принцип действия – использование двух процедур – enter_region, leave_region.

5) Использование команды TSL (test ... log): в ячейке lock заранее устанавливается значение не равное нулю. по команде TSL RX<B,D> (<B,D> – lock) в регистр RX считывается значение ячейки lock. При этом блокируется шина памяти таким образом, что никакой другой процесс не может обратиться к ОП.

6) Использование семафоров. Предложено Декстрой. В качестве семафора вводится переменная, которая может быть >=0. Используются две операции над семафором: down и up. Когда процесс хочет выполнить критическую секцию, он выполняет команду down и сравнивает значение с 0. Если 0 – переходит в ожидание и ждет пока не станет >0. Если >0, down уменьшает значение семафора и возвращает управление процессу для входа в критическую секцию. При выходе из критической секции выполняется команда up, которая увеличивает значение семафора на единицу. Если есть процессы, которые зациклились на команде down, выбирается 1 из них и выполняется. При этом, по down значение уменьшается на 1. Все процессы, манипулирующие семафором выполняются с запретом прерываний.

7) Использованием mutex-ов – упрощенных моделей семафоров – переменных, которые могут находиться в 2 состояниях: блокированном и неблокированном. Если процесс входит в критическую область, он блокирует mutex. При выходе – разблокирует. Механизм сходен с пунктом 4, но отличается тем, что, если не удается войти в критическую область, управление передается другому процессу.

8) Применение мониторов. Монитор представляет собой программный модуль, основными характеристиками которого являются:

-локальные переменные монитора доступны только его процедурам

-процесс входит в монитор путем вызова одной из его процедур

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

Различают:

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

cwait(s) - приостановка процесса S по условию C

csignal(s) - возобновление процесса S по условию C

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

9) Передача сообщений между процессами. Как правило, осуществляются с помощью процедур send и receive. в качестве параметров указывается источник и получатель сообщения и адрес, по которому находится сообщение. При передаче сообщений решаются следующие 3 основные задачи:

-определение протокола передачи и порядок получения подтверждения

-аутентификация сообщения

-способ передачи сообщения

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

-блокирующее отправление, блокирующее получение – в этом случае и отправитель и получатель блокируются до тех пор, пока получение переданного сообщения не будет подтверждено

-неблокирующее отправление, блокирующее получение – источник продолжает работу, получатель блокируется

-неблокирующее отправление, неблокирующее получение – не блокируются

Адресация сообщений может быть прямой и косвенной:

-прямая – в send идентификатор процесса получателя, в receive - адрес отправителя

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

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

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

Взаимоблокировки.

Взаимоблокировки(DeadLock) – ситуация, когда при конкуренции за ресурсы возникает блокировка всех процессов. Условия возникновения взаимоблокировок:

1) Взаимоисключение.

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

3) Отсутствие перераспределения (ресурс не может быть принудительно оторван у удерживающего процесса).

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

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

1) Предотвращение 3-х первых условий - косвенный метод.

2) Предотвращение 4-го условия – прямой метод.

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

Проблемы:

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

2) Все ресурсы сразу становятся недоступны всем остальным процессам.

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

Циклическое ожидание можно избежать путем упорядочивания типов ресурсов. То есть, если процесс запросил ресурс R, то он может получить ресурс, согласно упорядочиванию ресурса типа R.

Например, пусть ресурсы имеют индексы R_j и Ri, причем, i<j. Предположим, что процессы А и В взаимно заблокированы. А захватил ресурс Ri и запрашивает ресурс Rj, процесс В захватил Rj и запрашивает Ri. В случае упорядочивания ресурсов эта ситуация невозможна, так как должно одновременно выполняться i<j и и j<i.

Устранение взаимоблокировок.

Способы:

1. Не запускать процесс, если его запросы могут привести к взаимоблокировками.

2. Не удовлетворять запросы процесса к ресурсам, если это может вызвать взаимоблокировку.

Например: запрет запуска процесса. Рассмотрим систему из n процессов и m ресурсов. Ресурсы в системе R₁, R₂… R_m i-того типа . Доступные ресурсы: V₁, V₂… V_m* i-того типа. Запросы к ресурсам:

C₁₁ C₁₂.. C_1m

C₂₁ C₂₂.. C2m

….

C_n1 C_n2.. C_nm

где C_nm – запрос процесса n к ресурсу m.

Распределение ресурсов:

A₁₁ A₁₂.. A_1m

A₂₁ A₂₂.. A_2m

….

A_n1 A_n2.. A_nm

где A_nm – ресурс n выделен процессу m.

При этом должны выполняться соотношения:

1.

2. – k-ый запрос требует меньшее количество ресурса, чем его общее значение.

3. – к-й процесс не может получить ресурсов больше, чем им затребовано.

Новый процесс P_n+1 запускается, если

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

3. Запрет выделения ресурса известен так же как «алгоритм банкира» (Декстра, 1996 год). В этом алгоритме вводятся понятия: состояние (state) и безопасное состояние (save state).

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

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

Безопасное состояние – состояние, когда имеется хоть одна возможность выполнить всю последовательность процессов до их завершения, в противном случае, состояние называется опасным.

Рассмотрим пример:

В системе имеется 4 процесса и 3 ресурса. Вектор ресурсов:

R1	R2	R3

Первоначально распределение ресурсов по процессам проведено в следующем виде: матрица распределения ресурсов:

	R2	R3	R4
P1
P2
P3
P4

матрица запросов к ресурсам:

	R2	R3	R4
P1
P2
P3
P4

вектор доступности:

R1	R2	R3

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

	R2	R3	R4
P1
P2
P3
P4

матрица запросов к ресурсам:

	R2	R3	R4
P1
P2
P3
P4

вектор доступности:

R1	R2	R3

Теперь может выполниться P₁, P₂ или P₄. Пусть первым из них выполнится P₁.Тогда:

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

	R2	R3	R4
P1
P2
P3
P4

матрица запросов к ресурсам:

	R2	R3	R4
P1
P2
P3
P4

вектор доступности:

R1	R2	R3

Пусть следующим будет P₃.Тогда:

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

	R2	R3	R4
P1
P2
P3
P4

матрица запросов к ресурсам:

	R2	R3	R4
P1
P2
P3
P4

вектор доступности:

R1	R2	R3

Для выполнения P₄ имеются все необходимые ресурсы.

Рассмотрим опасное состояние:

вектор ресурсов:

R1	R2	R3

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

	R2	R3	R4
P1
P2
P3
P4

матрица запросов к ресурсам:

	R2	R3	R4
P1
P2
P3
P4

вектор доступности:

R1	R2	R3

Пусть процесс P₁ делает запрос на дополнительный единичный ресурс R₁ и R₃. Состояние системы будет следующим:

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

	R2	R3	R4
P1
P2
P3
P4

матрица запросов к ресурсам:

	R2	R3	R4
P1
P2
P3
P4

вектор доступности:

R1	R2	R3

Состояние опасно, так как каждому процессу требуется ресурс R₁, а его уже нет. Однако это состояние не является взаимоблокировкой, но может привести к ней. Если вернуть единичный ресурс R₁ и единичный ресурс R₃, состояние снова станет безопасным. Таким образом, стратегия устранение взаимоблокировок – предвидение этого состояние и устранение его.

Обнаружение взаимоблокировок.

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

Восстановление взаимоблокировок.

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

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

Голодание.

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

Пример: имеется принтер в системе, выбор процесса для предоставления принтера осуществляется по минимальной длине файла. В этом случае, процесс с длинным файлом для печати будет долго ждать.(голодать)

Алгоритмы планирования и диспетчирования.

Планирование.

Алгоритмы разделяются в зависимости от операционной среды:

-среда пакетной обработки

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

-система реального времени

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

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

2. Контроль выполнения принятой политики распределения ресурсов.

3. Обеспечение пропорциональной занятости всех ресурсов.

Для систем пакетной обработки:

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

2. Минимизация времени ожидания на решение отдельных задач (оборотное время).

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

Для интерактивных систем:

1. Быстрое время отклика на запрос пользователя.

2. Эффективное предоставление времени ЦП всем пользователям.

Для систем реального времени:

1. Обеспечение выполнения заданий к сроку.

2. Обеспечение качества решения при выполнении графика.

Для систем пакетной обработки:

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

1. Первым пришел, первым обслужил