МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Московский Государственный институт электроники и математики

(Технический университет)

Кафедра Управление и информатика в технических системах

Методические указания

к лабораторной работе № 4

по курсу "Системное программное обеспечение"

Москва 2002

Составители:

УДК 681.3

Лабораторная работа №4: ознакомление с семафорами как средством синхронизации работы параллельных процессов ОС UNIX, с обменом данными между процессами через разделяемую память; приобретение знаний и навыков написания программ работы с конкурирующими процессами.

Методические указания к лабораторным работам являются составной частью учебно-методического комплекса по дисциплине “Системное программное обеспечение”, изучаемой студентами специальности 21.01 “Управление и информатика в технических системах”.

Каждая лабораторная работа выполняется в объеме 3 часов.

Цель лабораторной работы №4 состоит в изучении механизма взаимодействия процессов на основе разделяемой памяти, а также средств их синхронизации с использованием семафоров.

Пакет IPC (Interprocess communication) в версии V системы UNIX включает в себя три механизма. Механизм сообщений дает процессам возможность посылать другим процессам потоки сформатированных данных, механизм разделения памяти позволяет процессам совместно использовать отдельные части виртуального адресного пространства, а семафоры - синхронизировать свое выполнение с выполнением параллельных процессов. Несмотря на то, что они реализуются в виде отдельных блоков, им присущи общие свойства.

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

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

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

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

На сегодняшний день предложено большое количество различных систем синхронизации процессов. К ним относятся:

• блокировка памяти;
• семафоры;
• критические области;
• условные критические области;
• мониторы;
• исключающие области и т.д..

Один из способов синхронизации параллельных процессов - семафоры Дейкстры, реализованные в ОС UNIX.

1.3.1. Синхронизация процессов

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

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

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

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

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

Такие примитивы под названием P и V операции были предложены Дейкстрой в 1968 году. Эти операции могут выполняться только над специальными переменными, называемыми семафорами или семафорными переменными. Семафоры являются целыми величинами и первоначально были определены как принимающие только неотрицательные значения. Кроме того, если их использовать для решения задач взаимного исключения, то область их значений может быть ограничена лишь “0” или “1”. Однако в дальнейшем была показана важная область применения семафоров, принимающих любые целые положительные значения. Такие семафоры получили название “общих семафоров” в отличие от “двоичных семафоров”, используемых в задачах взаимного исключения. P и V операции являются единственными операциями, выполняемыми над семафорами. Иногда они называются семафорными операциями.

Дадим определение P и V операций в том виде, в котором они были предложены Дейкстрой.

операция с одним аргументом, который должен быть семафором.

1.3.2. Реализация семафоров

Системные вызовы для работы с семафорами содержатся в пакете IPC (подключаемый файл описаний - <sys/ipc.h>). Эти вызовы обеспечивают синхронизацию выполнения параллельных процессов, производя набор действий только над группой семафоров (средствами низкого уровня).

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

Семафор в System V состоит из следующих элементов:

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

Для создания набора семафоров и получения доступа к ним используется системная функция semget, для выполнения различных управляющих операций над набором - функция semctl, для работы со значениями семафоров - функция semop.

Механизм функционирования файловой системы и механизмы взаимодействия процессов имеют ряд общих черт. Системные функции типа “get” похожи на функции creat и open, функции типа “control” (ctl) предоставляют возможность удалять дескрипторы из системы, чем похожи на функцию unlink. Тем не менее, в механизмах взаимодействия процессов отсутствуют операции, аналогичные операциям, выполняемым системной функцией close. Следовательно, ядро не располагает сведениями о том, какие процессы используют механизм IPC, и, действительно, процессы могут прибегать к услугам этого механизма, если правильно “угадывают” соответствующий идентификатор и если у них имеются необходимые права доступа, даже если они не выполнили предварительно функцию типа “get”.

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

Вместо традиционных, получивших широкое распространение файлов механизмы взаимодействия процессов используют новое пространство имен, состоящее из ключей (keys). Расширить семантику ключей на всю сеть довольно трудно, поскольку на разных машинах ключи могут описывать различные объекты. Короче говоря, ключи в основном предназначены для использования в одномашинных системах. Имена файлов в большей степени подходят для распределенных систем. Использование ключей вместо имен файлов также свидетельствует о том, что средства взаимодействия процессов являются “вещью в себе”, полезной в специальных приложениях, но не имеющей тех возможностей, которыми обладают, например, каналы и файлы.

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

Системные вызовы для работы с разделяемой памятью в ОС UNIX

описаны в библиотеке <sys/shm.h>.

Функция shmget создает новую область разделяемой памяти или возвращает адрес уже существующей области, функция shmat логически присоединяет область к виртуальному адресному пространству процесса, функция shmdt отсоединяет ее, а функция shmctl позволяет получать информацию о состоянии разделяемой памяти и производить над ней операции.

Создание области разделяемой памяти или получение номера дескриптора существующей области:

где id - идентификатор области разделяемой памяти, key - номер области, size - объем области в байтах, flag - параметры создания и права доступа.

Ядро использует key для ведения поиска в таблице разделяемой памяти: если подходящая запись обнаружена и если разрешение на доступ имеется, ядро возвращает вызывающему процессу указанный в записи дескриптор. Если запись не найдена и пользователь установил флаг IPC_CREAT, указывающий на необходимость создания новой области, ядро проверяет нахождение размера области в установленных системой пределах и выделяет область.

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

Рисунок 1. Структуры данных, используемые при разделении памяти.

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

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

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

Отсоединение области разделяемой памяти от виртуального адресного пространства процесса:

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

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

Получение информации о состоянии области разделяемой памяти и установка параметров для нее:

Значение id (возвращаемое функцией shmget) идентифицирует запись таблицы разделяемой памяти, cmd определяет тип операции, а buf является адресом пользовательской структуры, хранящей информацию о состоянии области. Типы операций описываются списком определений в файле “sys/ipc.h”:

#define IPC_RMID 10 /* удалить идентификатор (область) */

#define IPC_SET 11 /* установить параметры */

#define IPC_STAT 12 /* получить параметры */

С помощью команды (флага) IPC_RMID можно удалить область id. Удаляя область разделяемой памяти, ядро освобождает соответствующую ей запись в таблице разделяемой памяти и просматривает таблицу областей: если область не была присоединена ни к одному из процессов, ядро освобождает запись таблицы и все выделенные области ресурсы. Если же область по-прежнему подключена к каким-то процессам (значение счетчика ссылок на нее больше 0), ядро только сбрасывает флаг, говорящий о том, что по завершении последнего связанного с нею процесса область не должна освобождаться. Процессы, уже использующие область разделяемой памяти, продолжают работать с ней, новые же процессы не могут присоединить ее. Когда все процессы отключат область, ядро освободит ее. Это похоже на то, как в файловой системе после разрыва связи с файлом процесс может вновь открыть его и продолжать с ним работу.

Системные вызовы для работы с семафорами в ОС UNIX описаны в

библиотеке <sys/sem.h>.

Создание набора семафоров и получение доступа к ним:

Рисунок 1. Структуры данных, используемые в работе над семафорами.

Установка или проверка значения семафора:

где semid - дескриптор, возвращаемый функцией semget, oplist - указатель на список операций, nsops - размер списка. Возвращаемое функцией значение является прежним значением семафора, над которым производилась операция. Каждый элемент списка операций имеет следующий формат (определение структуры sembuf в файле sys/sem.h):

где shortsem_num - номер семафора, идентифицирующий элемент массива семафоров, над которым выполняется операция; sem_op - код операции; sem_fl – флаги операции. Ядро считывает список операций oplist из адресного пространства задачи и проверяет корректность номеров семафоров, а также наличие у процесса необходимых разрешений на чтение и корректировку семафоров. Если таких разрешений не имеется, системная функция завершается неудачно (res = -1). Если ядру приходится приостанавливать свою работу при обращении к списку операций, оно возвращает семафорам их прежние значения и находится в состоянии приостанова до наступления ожидаемого события, после чего системная функция запускается вновь. Поскольку ядро хранит коды операций над семафорами в глобальном списке, оно вновь считывает этот список из пространства задачи, когда перезапускает системную функцию. Таким образом, операции выполняются комплексно - или все за один сеанс, или ни одной.

Каждая структура восстановления состоит из трех элементов - идентификатора семафора, его порядкового номера в наборе и установочного значения. Ядро выделяет структуры восстановления динамически, во время первого выполнения системной функции semop с установленным флагом SEM_UNDO. При последующих обращениях к функции с тем же флагом ядро просматривает структуры восстановления для процесса в поисках структуры с тем же самым идентификатором и порядковым номером семафора, что и в вызове функции. Если структура обнаружена, ядро вычитает значение произведенной над семафором операции из установочного значения. Таким образом, в структуре восстановления хранится результат вычитания суммы значений всех операций, произведенных над семафором, для которого установлен флаг SEM_UNDO.

Рисунок 2. Структуры восстановления семафоров

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

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

Выполнение управляющих операций над набором семафоров:

Параметр arg объявлен как объединение типов данных:

Ядро интерпретирует параметр arg в зависимости от значения параметра cmd, который может принимать следующие значения:

GETVAL - вернуть значение того семафора, на который указывает параметр num.

SETVAL - установить значение семафора, на который указывает параметр num, равным значению arg.val.

GETPID - вернуть идентификатор процесса, выполнявшего последним функцию semop по отношению к тому семафору, на который указывает параметр semnum.

GETNCNT - вернуть число процессов, ожидающих того момента, когда значение семафора станет положительным.

GETZCNT - вернуть число процессов, ожидающих того момента, когда значение семафора станет нулевым.

GETALL - вернуть значения всех семафоров в массиве arg.array.

SETALL - установить значения всех семафоров в соответствии с содержимым массива arg.array.

IPC_STAT - считать структуру заголовка семафора с идентификатором id в буфер arg.buf. Аргумент semnum игнорируется.

IPC_SET – запись структуры семафора из буфера arg.buf.

IPC_RMID - удалить семафоры, связанные с идентификатором id, из системы.

Если указана команда удаления IPC_RMID, ядро ведет поиск всех процессов, содержащих структуры восстановления для данного семафора, и удаляет соответствующие структуры из системы. Затем ядро инициализирует используемые семафором структуры данных и выводит из состояния приостанова все процессы, ожидающие наступления некоторого связанного с семафором события: когда процессы возобновляют свое выполнение, они обнаруживают, что идентификатор семафора больше не является корректным, и возвращают вызывающей программе ошибку. Если возвращаемое функцией число равно 0, то функция завершилась успешно, иначе (возвращаемое значение равно -1) произошла ошибка. Код ошибки хранится в переменной errno.

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

Первый процесс делает “паузу” (pause), предоставляя второму процессу возможность выполнения; когда первый процесс принимает сигнал, он удаляет область разделяемой памяти из системы.

Запись в разделяемую память и чтение из нее

/* удаление разделяемой памяти */

Чтение из разделяемой памяти данных, записанных первым

процессом

где lsid - это идентификатор семафора;75 - ключ пользовательского дескриптора (если он занят, система создаст свой); 1 - количество семафоров в массиве; IPC_CREAT - флаг для создания новой записи в таблице дескрипторов (описан с правами доступа 0777).

Для установки начального значения семафора используем структуру sem. В ней присваиваем значение:

то есть семафор открыт для пользования.

Завершающим шагом является инициализация массива (в данном случае массив состоит из одного элемента):

где lsid - идентификатор семафора (выделенная строка в дескрипторе); 1 - количество семафоров; SETALL - команда “установить все семафоры”; sem - указатель на структуру.

Устанавливаем флаг SEM_UNDO в структуре sop для работы с функцией semop (значение этого флага не меняется в процессе работы).

Функция p() описывается следующим образом:

{ sop.sem_num = 0; /* номер семафора */

В структуру sop заносится номер семафора, над которым будет произведена операция и значение самой операции (в данном случае это уменьшение значения на 1). Флаг был установлен заранее, поэтому функция в процессе всегда находится в ожидании свободного семафора. (Функция v() работает аналогично, но sop.sem_op = 1).

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

int semid; /* идентификатор семафора */

unsigned int count; /* количество семафоров */

pause(); /* приостанов до получения сигнала */

/* закрыть второй семафор */

/* открыть второй семафор */

/* открыть первый семафор */

Предположим, что пользователь исполняет данную программу (под именем a.out) три раза в следующем порядке:

Если программа вызывается без параметров, процесс создает набор семафоров из двух элементов и присваивает каждому семафору значение, равное 1. Затем процесс вызывает функцию pause() и приостанавливается для получения сигнала, после чего удаляет семафор из системы (cleanup).

При выполнении программы с параметром 'a' процесс (A) производит над семафорами в цикле четыре операции: он уменьшает на единицу значение семафора 0, то же самое делает с семафором 1, выполняет команду вывода на печать и вновь увеличивает значения семафоров 0 и 1. Если бы процесс попытался уменьшить значение семафора, равное 0, ему пришлось бы приостановиться, следовательно, семафор можно считать захваченным (недоступным для уменьшения). Поскольку исходные значения семафоров были равны 1 и поскольку к семафорам не было обращений со стороны других процессов, процесс A никогда не приостановится, а значения семафоров будут изменяться только между 1 и 0.

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

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

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

(а) После первой операции (б) После второй операции

(в) После третьей операции (г) После четвертой операции

Рисунок 3. Последовательность состояний списка структур восстановления

Ядро создает структуру восстановления всякий раз, когда процесс уменьшает значение семафора, а удаляет ее, когда процесс увеличивает значение семафора, поскольку установочное значение структуры равно 0. На Рис.3 показана последовательность состояний списка структур при выполнении программы с параметром 'a'. После первой операции процесс имеет одну структуру, состоящую из идентификатора semid, номера семафора, равного 0, и установочного значения, равного 1, а после второй операции появляется вторая структура с номером семафора, равным 1, и установочным значением, равным 1. Если процесс неожиданно завершается, ядро проходит по всем структурам и прибавляет к каждому семафору по единице, восстанавливая их значения в 0. В частном случае ядро уменьшает установочное значение для семафора 1 на третьей операции, в соответствии с увеличением значения самого семафора, и удаляет всю структуру целиком, поскольку установочное значение становится нулевым. После четвертой операции у процесса больше нет структур восстановления, поскольку все установочные значения стали нулевыми.

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