VIII Международная студенческая научная конференция Студенческий научный форум - 2016

В качестве примера рассмотрим семафоры, мьютексы и мониторы.

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

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

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

Иногда используется упрощенная версия семафора, называемая мьютексом [1]. Мьютекс не способен считать, он может лишь управлять взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса проста и эффективна, что делает использование мьютексов особенно полезным в случае потоков, дей­ствующих только в пространстве пользователя. Мьютекс — переменная, которая может находиться в одном из двух состояний: блокированном или неблокированном. Поэтому для описания мьютекса требует­ся всего один бит, хотя чаще используется целая переменная, у которой 0 означает неблокированное состояние, а все остальные значения соответствуют блокирован­ному состоянию. Значение мьютекса устанавливается двумя процедурами. Если поток (или процесс) собирается войти в критическую область, он вызывает проце­дуру mutexlock. Если мьютекс не заблокирован (то есть вход в критическую область разрешен), запрос выполняется и вызывающий поток может попасть в критическую область [1, 2].

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

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

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

Чтобы упростить написание программ, в 1974 году Хоар  и Бринч Хансен предложили примитив синхронизации более высо­кого уровня, называемый монитором [1]. Монитор — набор процедур, переменных и дру­гих структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора.

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

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

Существует несколько языков программирования, поддерживающих мониторы, хотя и не всегда в соответ­ствии с моделью Хоара и Бринча Хансена. Один из таких языков — Java, объект­но-ориентированный язык, поддерживающий потоки на уровне пользователя и позволяющий группировать методы (процедуры) в классы. Добавление в описание метода ключевого слова synchronized гарантирует, что если хотя бы один поток на­чал выполнение этого метода, ни один другой поток не сможет выполнять другой синхронизированный метод из этого класса.

Мониторы являются структурным компонентом языка программиро­вания, и компилятор должен их распознавать и организовывать взаимное ис­ключение. В Pascal, С и многих других языках нет мониторов. В этих языках также нет и семафоров, но их легко добавить: нужно всего лишь присоединить к библиотеке две короткие программы, написанные на ассемблере и реализующие системные вызовы up и down. Компиляторы при этом не обязаны знать об их существовании. Разумеется, операционная система должна знать о се­мафорах, но даже если у вас операционная система с семафорами, вы можете пи­сать программы для нее на С или С++. Если же операционная система с мониторами, необходим язык со встроенными мониторами.

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

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

Список литературы

1.    Таненбаум Э., Бос Х. Современные операционные системы. – СПб.: Питер, 2015. – 1120 с. ISBN: 978-5-496-01395-6

2.    Бершадская Е.Г. Анализ технологий поддержки научных исследований // XXI век: итоги прошлого и проблемы настоящего плюс. 2015. № 3 (25). С. 11–17.