- •Введение
- •1. Основные понятия системного программного обеспечения
- •1.1. Понятия прикладного и системного программного обеспечения
- •1.2. Состав системного программного обеспечения
- •2. Состав и архитектура операционных систем
- •2.1. Состав операционных систем
- •2.2. Архитектура ос
- •3. Управление памятью
- •3.1. Функции ос по управлению памятью
- •3.2. Классификация методов распределения памяти
- •3.3. Распределение памяти без использования внешней памяти
- •3.4. Методы структуризации виртуальной памяти
- •4. Процессы и потоки
- •4.1. Концепция процессов и потоков
- •4.2. Многозадачность. Формы программной работы
- •4.3. Подсистема управления процессами и потоками
- •4.4. Создание процессов
- •4.5. Потоки и их модели
- •5. Планирование и синхронизация процессов и потоков
- •5.1. Виды планирования
- •5.2. Алгоритмы планирования потоков
- •5.3. Алгоритмы приоритетного планирования
- •5.4. Взаимоисключения
- •5.5. Семафоры
- •5.6. Тупики
- •6. Файловые системы
- •6.1. Цели и задачи файловой системы
- •6.2. Организация файлов и доступ к ним
- •6.3. Логическая организация файла
- •6.4. Каталоговые системы
- •6.5. Основные возможности файловой системы ntfs
- •6.6. Структура тома с файловой системой ntfs
- •6.7. Возможности ntfs по ограничению доступа к файлам и каталогам
- •7. Построение операционных систем
- •7.1. Принципы построения операционных систем
- •7.2. Построение интерфейсов операционных систем
- •7.3. Интерфейс прикладного программирования
- •7.4. Классификация системных вызовов
- •7.5. Интерфейс пользователя
- •8. Семейство операционных систем unix
- •8.1. Основные понятия системы unix
- •8.2. Операционная система Linux
- •Заключение
- •Библиографический список
- •Оглавление
5.5. Семафоры
Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра еще в 1965 году.
Механизм взаимоисключения может быть реализован с помощью семафоров: двоичных и считающих.
С семафором связаны инициализация и две операции:
P(s) - закрытие,
V(s) - открытие.
Двоичный семафор имеет два состояния - 0 и 1. Закрытый семафор находится в состоянии 0, открытый - в состоянии 1.
При инициализации семафора определяется его начальное состояние:
ИнициализацияСемафора(s, 1);
или
ИнициализацияСемафора(s, 0);
Операция P(s):
if s = 1
then s := 0 { закрыть семафор }
else блокировать обратившийся процесс по s;
установить на выполнение готовый процесс;
Операция V(s):
if список процессов, ожидающих s, не пуст
then деблокировать процесс, ожидающий S
else s := 1; { открыть семафор }
Критический участок окаймляется операциями P(s) и V(s). Таким образом, двоичный семафор обеспечивает логику работы с событием (Event).
Считающие семафоры полезны при выделении одиночного ресурса из общего пула.
При инициализации в s заносят количественный показатель объема ресурсов пула. P(s) вызывает уменьшение счетчика ресурса на единицу, а V(s) - увеличение счетчика на единицу, т.е.
операция P(s):
if s > 0
then s := s - 1
else ожидать на s;
операция V(s):
if список процессов, ожидающих s не пуст
then разрешить одному процессу работать
else s := s + 1;
Считающие семафоры реализованы в программном интерфейсе Windows. Их использование аналогично использованию событий и критических секций, т.е. семафор может быть в отмеченном или неотмеченном состоянии.
5.6. Тупики
Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. "Зависание" системы – это ситуация, когда один или более процессов оказываются в состоянии тупика..
Пример. В операционных системах тупики в большинстве случаев возникают в результате обычной конкуренции за обладание выделяемыми или закрепляемыми ресурсами (т.е. ресурсами, которые в каждый момент времени отводятся только одному пользователю и которые поэтому иногда называются ресурсами последовательного использования).
Пусть Процесс1 удерживает Ресурс1 и ожидает освобождения Ресурса2. Процесс2 удерживает Ресурс2 и ожидает освобождения Ресурса1. Каждый процесс ждет, чтобы другой процесс освободил нужный ему ресурс, причем каждый не освобождает свой ресурс до тех пор, пока другой не освободит свой ресурс и т.д. Такое состояние кругового ожидания характерно для систем в тупиковом состоянии (рис. 22).
Рис. 22. Пример тупиковой ситуации
Можно сформулировать четыре необходимых условия тупика.
Условие взаимоисключения: процессы требуют предоставления им права монопольного управления ресурсами, которые им выделяются.
Условие ожидания ресурсов: процессы удерживают ресурсы, уже выделенные им, ожидая выделения дополнительных ресурсов.
Условие неперераспределяемости: ресурсы нельзя отобрать у процессов, удерживающих их, пока эти ресурсы не будут использованы для завершения работы.
Условие кругового ожидания: существует кольцевая цепь процессов, удерживающих ресурсы, требующиеся следующему процессу цепи.
В исследованиях по проблеме тупиков можно выделить следующие основные направления:
– предотвращение тупиков;
– обход тупиков;
– обнаружение тупиков;
– восстановление после тупиков.
Предотвращение тупиков. При предотвращении тупиков целью является обеспечение условий, исключающих возможность возникновения тупиковых ситуаций. Такой подход является вполне корректным решением в том, что касается самого тупика, однако он часто приводит к нерациональному использованию ресурсов. Установлено, что тупик будет невозможен, при нарушении хотя бы одного из указанных выше необходимых условий.
Предлагается стратегия, включающая три принципа:
– каждый процесс должен запрашивать все требуемые ресурсы сразу и не начинаться, пока они не будут выделены;
– если процесс требует дополнительных ресурсов и получает отказ, он должен освободить все ресурсы и запросить потом всю совокупность ресурсов;
– введение линейной упорядоченности по типам ресурсов.
Все элементы этой стратегии имеют свои недостатки.
Обход тупиков. Используются алгоритмы, позволяющие обойти опасные участки при распределении ресурсов (алгоритмы Деккера, Питерсона, Дейкстры).
Обнаружение тупика – это установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в тупиковую ситуацию.
Алгоритмы обнаружения тупиков, как правило, применяются в системах, где выполняются первые три необходимые условия возникновения тупиковой ситуации. Эти алгоритмы затем определяют, не создался ли режим кругового ожидания. Таким образом, обнаружение тупика сводится к проверке наличия циклических запросов на ресурсы. Можно включать в ОС алгоритмы обнаружения, а можно положиться на оператора компьютера.
Восстановление после тупика – систему, оказавшуюся в тупике, необходимо вывести из него, нарушив одно или несколько условий его существования. Обычно это выполняется путем принудительного вывода некоторого процесса из системы, чтобы можно было использовать его ресурсы.
Самый целесообразный способ – это эффективный механизм приостановки/возобновления процесса.
Другой способ – создание контрольных точек (дампов памяти) и перезапуск.