Методы борьбы с взаимоблокировками

1.1)

связь аппаратной части с программной, взаимодействие с пользователем.

1.3)

Поддержка многозадачности:

-однозадачные (например, MS-DOS, MSX) и

-многозадачные (OC EC, OS/2, UNIX, Windows 95).

Поддержка многопользовательского режима:

-однопользовательские (MS-DOS, Windows 3.x, ранние версии OS/2);

-многопользовательские (UNIX, Windows NT).

Поддержка многонитевости.

Многопроцессорная обработка

По назначению:

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

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

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

1.5)

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

Типовая структура ОС

Ядро – резидентная часть ОС, работающая в режиме супервизора. В ядре размещаются программы обработки прерываний и драйверы наиболее «ответственных» устройств. Это могут быть и физические, и виртуальные устройства. Например, в ядре могут располагаться драйверы файловой системы, ОЗУ. Обычно ядро работает в режиме физической адресации.

Следующие уровни структуры – динамически подгружаемые драйверы физических и виртуальных устройств. Это драйверы, добавление которых в систему возможно «на ходу» без перекомпоновки программ ОС. Они могут являться резидентными и нерезидентными, а также могут работать как в режиме супервизора, так и в пользовательском режиме.

2.1)

рождение, выполняющийся, ожидание, завершение(естественное, придудительное).

2.2)

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

Такие потоки называют также потоками выполнения (от англ. thread of execution); иногда называют «нитями» (буквальный перевод англ. thread) или неформально «тредами».

Типы реализации потоков

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

Достоинства и недостатки этого типа следующие: Недостатки

1.Отсутствие прерывания по таймеру внутри одного процесса

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

3.Сложность реализации

-Поток в пространстве ядра. Наряду с таблицей процессов в пространстве ядра имеется таблица потоков.

-«Волокна» (англ. fibers). Несколько потоков режима пользователя, исполняющихся в одном потоке режима ядра. Поток пространства ядра потребляет заметные ресурсы, в первую очередь физическую память и диапазон адресов режима ядра для стека режима ядра. Поэтому было введено понятие «волокна» — облегчённого потока, выполняемого исключительно в режиме пользователя. У каждого потока может быть несколько «волокон».

2.3)

Межпроцессное взаимодействие (англ. Inter-Process Communication, IPC) — набор способов обмена данными между множеством потоков в одном или более процессах

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

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

Семафоры

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году.

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

Операция up увеличивает значение семафора. Если с этим семафором связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой (например, случайным образом) и ему разрешается завершить свою операцию down. Таким образом, после операции up, примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так и останется равным 0, но число ожидающих процессов уменьшится на единицу. Операция увеличения значения семафора и активизации процесса тоже неделима. Ни один процесс не может быть блокирован во время выполнения операции up, как ни один процесс не мог быть блокирован во время выполнения операции wakeup в предыдущей модели.

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

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

Передача сообщений

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

Мьютекс — упрощенная версия семафора, которая может находиться в одном из двух состояний — блокированном или неблокированном.

2.4)

Проблема обедающих философов

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

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

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

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

Проблема читателей и писателей

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

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

Проблема спящего брадобрея

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

В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается — он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.

2.5)

Для всех ОС соблюдается следующие принципы планирования:

1 Предоставление каждому процессу справедливого (одинакового) количество процессорного времени.

2 Производится принудительное выполнение политики приоритетов выполняющихся процессов.

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

3.1)

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

Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.

Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).

Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).

Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы.

3.2)

Условия необходимые для взаимоблокировки:

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

2 Условие удержания и ожидания - процесс, удерживающий ресурс может запрашивать новые ресурсы.

3 Условие отсутствия принудительной выгрузки ресурса.

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

Методы борьбы с взаимоблокировками

Четыре стратегии избегания взаимоблокировок:

-Пренебрежением проблемой в целом (вдруг пронесет).

-Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется).

-Динамическое избежание тупиков.

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