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

Все известные средства для решения проблемы взаимного исключения основа­ны на использовании специально введенных аппаратных возможностей, к кото­рым относятся блокировка памяти, специальные команды типа «проверка и ус­тановка» и управление системой прерываний, позволяющее организовать такие механизмы, как семафорные операции, мониторы, почтовые ящики и др. С по­мощью перечисленных средств можно разрабатывать взаимодействующие про­цессы, при исполнении которых будут корректно решаться все задачи, связан­ные с проблемой критических интервалов. Рассмотрим эти средства в порядке их появления, а значит, по мере их усложнения, перехода к функциям операци­онной системы и увеличения предоставляемых ими удобств для пользователя. При этом будем опираться на далеко не новую, но все же еще достаточно акту­альную работу Дейкстры¹ [28].

Использование блокировки памяти

при синхронизации параллельных процессов

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

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

1 На наш взгляд, эта работа Дейкстры очень полезна с методической точки зрения. Она по­зволяет понять наиболее тонкие моменты в этой проблематике.

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

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

' Проблема кажется легко решаемой, если потребовать, чтобы процессы ПР1 и ПР2 входили в свои критические интервалы попеременно. Для этого одна общая пе­ременная может хранить указатель того, чья очередь войти в критическую сек­цию. Текст такого решения на языке, близком к Pascal, приведен в листинге 6.1.

Листинг 6.1. Первый вариант попытки реализации взаимного исключения