Александр Кручинин - Операционные системы

• Название: Операционные системы
• Автор: Александр Кручинин
• Жанр: Детская образовательная литература
• Год: 2009

Данное пособие содержит курс лекций по дисциплине «Операционные системы». Предназначено для студентов вузов, обучающихся по направлению «Информатика и вычислительная техника» специальности 230101 «Вычислительные машины, комплексы, системы и сети».

---

У каждого потока свой собственный стек. Стек (англ. stack – стопка) – структура данных с методом доступа к элементам LIFO (англ. Last In – First Out, «последним пришел – первым вышел») [14].

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

Таблица 2 – Элементы процесса, общие для потоков, и индивидуальные элементы потоков

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

• возможность совместного использования параллельными объектами адресного пространства и всех содержащихся в нём данных;

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

• увеличивается производительность.

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

Рисунок 12 – Пакет потоков в пространстве пользователя (а); пакет потоков, управляемый ядром (б)

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

2.3 Межпроцессное взаимодействие

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

• передача информации от одного процесса другому;

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

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

Эти же пункты, не считая первого, относятся и к потокам.

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

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

• два процесса не должны одновременно находиться в критических областях;

• в программе не должно быть предположений о скорости и количестве процессоров;

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

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

Рисунок 13 – Взаимное исключение с использованием критических областей

В абстрактном виде требуемое поведение процессов представлено на рисунке 13. Процесс А попадает в критическую область в момент времени T1. Чуть позже, в момент времени T2, процесс Б пытается попасть в критическую область, но ему это не удается, поскольку в критической области уже находится процесс А, а два процесса не должны одновременно находиться в критических областях. Поэтому процесс Б временно приостанавливается, до наступления момента времени T3, когда процесс А выходит из критической области. В момент времени T4 процесс Б также покидает критическую область, и происходит возвращение в исходное состояние, когда ни одного процесса в критической области не было.

2.3.1 Взаимное исключение с активным ожиданием

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

1 Запрещение прерывания

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

2 Переменные блокировки

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

3 Строгое чередование

Третий метод проиллюстрирован на листинге 1.

Листинг 1 – Решение проблемы критической области методом строгого чередования

Целая переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Здесь для того, чтобы 0-ой процесс вошел в область, turn должна быть равна 0, а 1-ой – turn равна 1.

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

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

4 Алгоритм Петерсона

В 1981 году датский математик Петерсон разработал простой алгоритм взаимного исключения, представленный на листинге 2 [17].

Листинг 2 – Решение Петерсона для взаимного исключения

Перед тем, как войти в критическую область процесс вызывает процедуру enter_region со своим номером в качестве параметра. После выхода из критической области процесс вызывает leav_region.

Исходно оба процесса находятся вне критических областей. Процесс 0 вызывает enter_region, задает элементы массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, процедура возвращается. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested[0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область.

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

5 Команда TSL

Это решение требует участия аппаратного обеспечения. Многие компьютеры имеют команду: TSL RX, LOCK.

(Test and Set Lock – проверить и заблокировать), которая действует следующим образом. В регистр RX считывается содержимое слова памяти LOCK, а в ячейке памяти LOCK сохраняется некоторое ненулевое значение. Операция считывания слова неделима. Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры, если они есть, не могли обратиться к памяти.