МИНОБРНАУКИ РОССИИ
__________________________
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина)
________________________________________________________
В. В. СИДЕЛЬНИКОВ В. В. ШИРОКОВ
СРЕДСТВА СИНХРОНИЗАЦИИ МНОГОЗАДАЧНЫХ ПРИЛОЖЕНИЙ. МОНИТОР ХОАРА
Учебно-методическое пособие
Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ»
2019
1
УДК 004.451(07)
ББК З973-018я7
С34
Сидельников В. В., Широков В. В.
С34 Средства синхронизации многозадачных приложений. Монитор Хоара: учеб.-метод. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2019. 44 с.
ISBN 978-5-7629-2412-2
Описываются средства синхронизации многозадачных приложений в виде, предложенном в работах Дейкстры и Хоара. Особое внимание уделяется монитору, детально рассматриваются способы передачи управления при работе с условной переменной, определяемые как «семантика Хоара» и «семантика Mesa».
Также рассматриваются примеры современной реализации механизмов синхронизации – монитора в языке программирования Java, семафоров, мьютексов и условных переменных в рамках программного интерфейса POSIX-совместимых операционных систем. Приводятся примеры использования описанных механизмов при решении конкретных задач синхронизации.
Предназначено для подготовки бакалавров по направлению 09.03.02 «Информационные системы и технологии» и специалистов по направлению 090301.65 «Компьютерная безопасность».
УДК 004.451(07)
ББК З973-018я7
Рецензент канд. техн. наук Ф. Р. Гальяно Сизаско (АО СПИИРАН НТБВТ).
Утверждено редакционно-издательским советом университета
в качестве учебно-методического пособия
ISBN 978-5-7629-2412-2 |
© СПбГЭТУ «ЛЭТИ», 2019 |
2
1. МНОГОЗАДАЧНОСТЬ И СИНХРОНИЗАЦИЯ
Практически на всех современных компьютерах возможно одновременное выполнение нескольких программ. Такой «параллелизм» может обеспечиваться как на «логическом» уровне, за счет разделения времени процессора, так и за счет «физического» распределения вычислений на многопроцессорной платформе. При этом как в первом, так и во втором случае управляет таким распараллеливанием операционная система.
Абстрагируясь в дальнейшем от конкретной реализации, будем считать, что имеется некоторая вычислительная машина, управление в которой и поддержка параллельного выполнения нескольких программ осуществляются операционной системой.
При таком параллелизме программа, написанная на некотором языке программирования и скомпилированная в машинное представление, обрастает атрибутами, необходимыми операционной системе для управления ее выполнением, и термин «программа» уже не вполне соответствует той сущности, с которой операционная система имеет дело.
Чаще всего для подобного определения используются термины «процесс» или «поток», которые происходят из представлений UNIXподобных операционных систем, определяют конструкции, существенно отличающиеся друг от друга, и отражают специфику реализации. Здесь же в дальнейшем хотелось бы использовать термин, который, с одной стороны, корректно отражал бы положение вещей, а с другой – был бы достаточно общим. Не вдаваясь далее в анализ терминологических особенностей и для избежания путаницы в определениях, там, где не затрагиваются особенности реализации, будем использовать термин задача, а под многозадачностью будем понимать возможность выполнения нескольких задач параллельно во времени.
При любом способе реализации многозадачности необходимо наличие механизмов, обеспечивающих согласование выполнения задач во времени, их
синхронизацию. Например, одна из задач измеряет значения температуры, другая – обрабатывает эти значения. Понятно, что обрабатывать надо после того, как измерили. Или две задачи изменяют значение одного данного, и делать это одновременно крайне нежелательно. Да и чтение такого данного должно быть упорядочено во времени для того, чтобы каждая задача имела возможность получать актуальное значение. Таким образом, под
3
синхронизацией задач (или участков их кода) понимается согласование их выполнения во времени, и для обеспечения такого согласования при разработке многозадачных приложений необходимы соответствующие механизмы.
Вопросами синхронизации занимались такие ученые, как Эдсгером Дейкстра, Бринч Хансен и Чарлз Хоар, которые по праву считаются основоположниками не только в этой области, но и в других областях программирования. Предложенные ими методы легли в основу механизмов, которые в настоящее время реализуются в операционных системах. Однако некоторые аспекты первоначальных идей по тем или иным причинам остались не реализованными и, возможно, еще привлекут внимание будущих разработчиков.
Далее будут рассмотрены механизмы синхронизации в том виде, как они были предложены их разработчиками, а затем так, как они реализуются в современных операционных системах.
В ряде примеров, иллюстрирующих многозадачное выполнение, будем использовать запись следующего вида:
Parbegin P1; P2; . . . Pn Parend,
где подразумевается, что действия Pi, заключенные в «операторные скобки» Parbegin ... Parend, выполняются параллельно во времени до тех пор, пока не завершится самое длительное из них.
2. СЕМАФОРЫ И МЬЮТЕКСЫ
Наиболее распространенной проблемой синхронизации является вопрос обеспечения взаимного исключения. Если несколько задач используют некоторый разделяемый ими ресурс (например, некоторое данное), то в каждый момент времени доступ к этому ресурсу должна иметь только одна из них. Обычно участок кода, обеспечивающий доступ к разделяемому ресурсу, называют критической секцией или критическим участком. В свое время предлагалось большое количество алгоритмов, позволяющих решить задачу взаимного исключения. Однако естественным пожеланием было иметь некий общий механизм, который можно было использовать при разработке многозадачных приложений. В 1968 г. голландским ученым Эдсгером Дейкстрой была опубликована работа «Взаимодействующие последовательные процессы», в которой он предложил механизм семафоров, предполагающий наличие переменной S – двоичного семафора, способной
4
принимать только 2 значения – «0» или «1». Над такой переменной (семафором) допускались две операции – P(S) и V(S):
P(S):
if (S = 0) then wait(S = 1); S := 0;
V(S):
S := 1;
Задача, которая выполняет операцию P(S) при значении S = 1, «захватывает» семафор и выполняется дальше, установив S в «0». Таким образом, другая задача, выполняющая P(S), будет приостановлена, т. е. будет
блокироваться действием wait и ставиться в очередь заблокированных задач,
связанную с данным семафором. Такая очередь всегда будет создаваться при создании семафора. Заблокированная задача будет находиться в очереди до тех пор, пока некоторая другая задача не выполнит операцию V(S). Операция V(S), устанавливая S := 1, выбирает из очереди первую заблокированную задачу и обеспечивает продолжение ее выполнения с действия, следующего за операцией wait. Дисциплиной обслуживания очереди заблокированных задач в таком случае является FIFO.
Важным условием относительно P- и V-операций является то, что они должны быть неделимыми, т. е. одновременное их выполнение более чем одной задачей невозможно.
В реальной ситуации эти механизмы реализуются в ядре операционной системы, и задача продолжает выполняться не сразу после вызова V(S) – заблокированная задача из очереди заблокированных задач на семафоре S поступает в очередь готовых к выполнению задач операционной системы, и момент возобновления ее активности определяется дисциплиной диспетчеризации операционной системы.
Нетрудно убедиться, что представленный механизм позволяет решить задачу взаимного исключения. Пусть имеется приложение, cостоящее из n задач Ri, каждая из который включает в себя критическую секцию CSi, код которой работает с некоторым ресурсом, разделяемым всеми задачами. Если заключать CSi в «операторные скобки» P(S)–V(S), как показано ниже, то взаимное исключение будет обеспечено.
S : ДвоичныйСемафор;
Ri : loop
Начало_I;
5