[Leonardo]
автор Leonardo Giordani
<leo.giordani(at)libero.it>
Об авторе:
Студент Политехнического Университета Милана, учится на факультете
телекоммуникационных технологий, работает сетевым администратором и
интересуется программированием (в основном на Ассемблере и C/C++). С
1999 практически постоянно работает в Linux/Unix.
Перевод на Русский:
Dmitry Martsynkevitch <ursa(at)zaba.ru>
Параллельное программирование -- взаимодействие между процессами.
[run in paralell]
Резюме:
Целью данной серии статей является ознакомление читателя с концепцией
многозадачности и её реализацией в операционной системе Linux. Начав с
теоретических основ, мы закончим написанием полноценной программы,
демонстрирующей взаимодействие между процессами, с простым, но
эффективным протоколом коммуникации.
Что необходимо знать для понимания данной статьи:
* Минимальные знания shell
* Основы языка C (синтаксис, циклы, библиотеки)
Также вам следует прочитать первую статью из этого цикла, поскольку
она является основой для данной: November 2002, article 272.
Ну вот и опять мы боремся с мультизадачностью в Linux. Как мы видели в
предыдущей статье, чтобы создать новый процесс, нужно всего несколько
строк в коде, так как операционная система берёт на себя
инициализацию, управление и распределение рабочего времени процесса,
созданного нами.
Это свойство системы является фундаментальным, это ``контроль
выполнения процессов'', контроль до такой степени, что процессы
исполняются в своих собственных адресных пространствах. Потеря
контроля над выполнением процесса приводит разработчика к проблеме
синхронизации, которую можно выразить следующим вопросом: как сделать
возможной совместную работу двух процессов?
На самом деле проблема несколько более сложная, чем может показаться:
это не только вопрос одновременной работы программ, но также и вопрос
одновременного использования одних данных, как для чтения, так и для
записи.
Поговорим о некоторых классических проблемах одновременного
использования данных; если два процесса одновременно читают один набор
данных, то это, очевидно, не создаёт проблем, и выполнение процессов
-- последовательное. Пусть теперь один процесс изменяет набор данных:
результат работы второго процесса будет зависеть от того, прочёл
процесс данные до или после их изменения. Например: у нас есть два
процесса "А" и "В" и целое число "d". Процесс А увеличивает d на
единицу, процесс В печатает значение d. Это можно записать на условном
языке так:
A { d->d+1 } & B { d->output }
здесь "&" означает одновременное выполнение процессов. Сначала может
быть выполнен процесс А,
(-) d = 5 (A) d = 6 (B) output = 6
а может и процесс В:
(-) d = 5 (B) output = 5 (A) d = 6
Сразу понятно, как важно уметь правильно обращаться с такими
ситуациями: риск противоречивости данных высок и неприемлем. Если вы
всё ещё недооцениваете эту проблему, представьте, что набор данных --
это ваш банковский счёт...
В предыдущей статье мы уже говорили о первом способе синхронизации ---
использовании функции waitpid(2), позволяющей процессу подождать
завершения другого процесса, работающего на том же наборе данных, и
только затем продолжить свою работу.
Очевидно, это не самый лучший способ: процесс вынужден простаивать в
ожидании завершения работы вторым процессом. Неприятность заключается
в том, что второй процесс может работать довольно долго, а общими
данными пользоваться весьма короткий промежуток времени. Таким
образом, нам необходимо увеличить "гранулированность" нашего
управления, т.е. управлять отдельными наборами данных. Решение данной
проблемы -- примитивы из стандартной библиотеки, известной как SysV
IPC (Взаимодействие процессов в System V).
Ключи SysV
Прежде чем перейти к самой теории одновременности, давайте
познакомимся с типичной SysV структурой: IPC ключами. IPC ключ -- это
число, однозначно идентифицирующее IPC структуру управления
(описывается ниже). Также ключ можно использовать для образования
универсальных идентификаторов, т.е. для организации не IPC структур.
Ключ создаётся функцией ftok(3).
key_t ftok(const char *pathname, int proj_id);
Для генерирования ключа ftok берёт имя существующего файла (pathname)
и идентификатор процесса (proj_id). Алгоритм построения ключа не
исключает возможности появления дубликатов, поэтому следует иметь
маленькую библиотеку, просматривающую уже созданные ключи и не
допускающую повторений.
Семафоры
Идею управления дорожным движением с помощью семафоров можно без
особых изменений перенести на управление доступом к данным. Семафор --
особая структура, содержащая число большее или равное нулю и
управляющая цепочкой процессов, ожидающих особого состояния на данном
семафоре. Хотя они и кажутся очень простыми, семафоры -- это очень
мощное средство, а потому, на самом деле, весьма сложное. Начнём, как
всегда, не рассматривая обработку ошибок: мы включим её в код, когда
будем писать более сложную программу.
Семафоры могут использоваться для контролирования доступа к ресурсам:
число в семафоре представляет собой количество процессов, которые
могут получить доступ к данным. Каждый раз, когда процесс обращается к
данным, значение в семафоре, должно быть уменьшено на единицу, и
увеличено, когда работа с данными будет прекращена. Если ресурс
эксклюзивный, то есть к данным должен иметь доступ только один
процесс, то начальное значение в семафоре следует установить единицей.
Семафоры можно использовать и для других целей, например для счётчика
ресурсов. В этом случае число в семафоре -- количество свободных
ресурсов (например количество свободных ячеек памяти).
Рассмотрим практическое применение семафоров. Пусть у нас есть буфер,
в который несколько процессов S1,...,Sn могут писать, и только один
процесс L может из него читать. Также операции нельзя выполнять
одновременно (в данный момент времени только один процесс должен
оперировать с буфером). Очевидно, что процессы Si могут писать всегда,
когда буфер не полон, а процесс L может читать, когда буфер не пуст.
Таким образом, нам необходимо три семафора: один управляет доступом к
буферу, а два других следят за числом элементов в нём.
Учитывая, что доступ к буферу должен быть эксклюзивным, первый семафор
будет бинарным (его значение будет нулём или единицей), в то время как
второй и третий будут принимать значения, зависящие от размера буфера.
Рассмотрим, как реализованы семафоры на C, в SysV. Создаёт семафор
функция semget(2)
int semget(key_t key, int nsems, int semflg);
здесь key -- IPC ключ, nsems -- число семафоров, которое мы хотим
создать, и semflg -- права доступа, закодированные в 12 бит: первые
три бита отвечают за режим создания, остальные девять -- права на
запись и чтение для пользователя, группы и остальных (заметьте
сходство с файловой системой в Unix). За более полной информацией
загляните в man страницы ipc(5). Как вы видите SysV создаёт сразу
несколько семафоров, что уменьшает код.
Давайте создадим наш первый семафор
#include <stdio.h>
#include <stdlib.h>
#include <linux/types.h>
#include <linux/ipc.h>
#include <linux/sem.h>
int main(void)
{
key_t key;
int semid;
key = ftok("/etc/fstab", getpid());
/* создать только один семафор: */
semid = semget(key, 1, 0666 | IPC_CREAT);
return 0;
}
Далее нам надо выяснить как управлять семафорами, и как удалять их.
Управление происходит с помощью функции semctl(2),
int semctl(int semid, int semnum, int cmd, ...)
которая выполняет действие cmd на наборе семафоров semid или (если
требуется командой) на одном семафоре с номером semnum. Мы расскажем о
свойствах это команды, когда станет необходимо, полный же список
свойств доступен на man страницах. В зависимости от команды, может
понадобится указать ещё один аргумент следующего типа:
union semun {
int val; /* значение для SETVAL */
struct semid_ds *buf; /* буферы для IPC_STAT, IPC_SET */
unsigned short *array; /* массивы для GETALL, SETALL */
/* часть, особенная для Linux: */
struct seminfo *__buf; /* буфер для IPC_INFO */
};
Чтобы изменить значение семафора, используют директиву SETVAL, новое
значение должно быть указано в semun; давайте модифицируем приведённую
выше программу, устанавливая в семафоре значение 1.
[...]
/* создать только один семафор */
semid = semget(key, 1, 0666 | IPC_CREAT);
/* в семафоре 0 установить значение 1 */
arg.val = 1;
semctl(semid, 0, SETVAL, arg);
[...]
Теперь необходимо удалить семафор, освобождая структуры,
использовавшиеся для управления им; это выполняет директива IPC_RMID.
Она удаляет семафор и посылает сообщение об этом всем процессам,
ожидающим доступа к ресурсу. Последний раз изменим программу:
[...]
/* в семафоре 0 установить значение 1 */
arg.val = 1;
semctl(semid, 0, SETVAL, arg);
/* удалить семафор */
semctl(semid, 0, IPC_RMID);
[...]
Как вы уже поняли, создание и управление структурами контроля за
параллельным выполнением программ достаточно просто, когда мы добавим
обработку ошибок, всё станет несколько более сложно, но только в
смысле сложности кода.
Использовать семафор можно с помощью процедуры semop(2),
int semop(int semid, struct sembuf *sops, unsigned nsops);
здесь semid -- идентификатор набора семафоров, sops -- массив,
содержащий операции, которые необходимо произвести, nsops -- число
этих операций. Каждая операция представляется структурой sembuf.
unsigned short sem_num; short sem_op; short sem_flg;
т.е номером семафора в множестве (sem_num), операцией (sem_op) и
флагом, устанавливающим режим ожидания; пусть пока он будет нулём.
Операции, которые мы можем указать, являются целыми числами и
подчиняются следующим правилам:
1. sem_op < 0
Если модуль значения в семафоре больше или равен модулю sem_op, то
sem_op добавляется к значению в семафоре (т.е. значение в семафоре
уменьшается). Если модуль sem_op больше, то процесс переходит в
спящий режим, пока не будет достаточно ресурсов.
2. sem_op = 0
Процесс спит пока значение в семафоре не достигнет нуля.
3. sem_op > 0
Значение sem_op добавляется к значению в семафоре, используемый
ресурс освобождается.
Следующая программа представляет пример использования семафоров,
реализуя предыдущий пример с буфером: мы создадим пять процессов W и
один процесс R. Процессы W будут пытаться получить доступ к ресурсу
(буферу), закрывая его через семафор, и, если буфер не полон, будут
класть в него элемент и освобождать ресурс. Процесс R будет закрывать
ресурс, брать из него элемент, если буфер не пуст, и разблокировать
ресурс.
Чтение и запись в буфер на самом деле ненастоящие: так происходит
потому, что, как обсуждалось в предыдущей статье, каждый процесс
выполняется в своём собственной области памяти и не может обращаться к
памяти другого процесса. Это делает настоящее управление буфером
шестью процессами невозможным, так как каждый процесс будет видеть
свою копию буфера. всё встанет на свои места, когда мы будем говорить
о разделяемой памяти, но давайте быть последовательными.
Почему нам нужно три семафора? Первый (с номером 0) действует как
замок к буферу, и его максимальное значение равно единице, остальные
два отвечают за переполнение и наличие элементов в буфере. Одним
семафором этого не добиться.
Потребность в двух семафорах связана с особенностью работы функции
semop. Если, например, процессы W уменьшают значение в семафоре,
отвечающем за свободное место в буфере, до нуля, то процесс R может
увеличивать это значение до бесконечности. Поэтому такой семафор не
может указывать на отсутствие элементов в буфере.
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <linux/types.h>
#include <linux/ipc.h>
#include <linux/sem.h>
Эти четыре строки -- действия, которые мы можем производить над
семафорами: первые две -- содержат по одному действия каждая, вторые
-- по две. Первое действие, lock_res, блокирует ресурс: оно уменьшает
значение первого (номер 0) семафора на единицу (если значение в
семафоре не нуль), а если ресурс уже занят, то процесс ждёт. Действие
rel_res аналогично lock_res, только значение в первом семафоре
увеличивается на единицу, т.е. убирается блокировка ресурса.
Действия push и pop несколько отличаются от первых: это массивы из
двух действий. Первое действие над семафором номер 1, второе -- над
семафором номер 2; одно увеличивает значение в семафоре, другое
уменьшает, но теперь процесс не будет ждать освобождения ресурса:
IPC_NOWAIT заставляет его продолжить работу, если ресурс заблокирован.
/* Установить в семафоре номер 0 (Контроллер ресурсов)
значение "1" */
arg.val = 1;
semctl(semid, 0, SETVAL, arg);
/* Установить в семафоре номер 1 (Контроллер свободного места)
значение длины буфера */
arg.val = atol(argv[1]);
semctl(semid, 1, SETVAL, arg);
/* Установить в семафоре номер 2 (Контроллер элементов в буфере)
значение "0" */
arg.val = 0;
semctl(semid, 2, SETVAL, arg);
Здесь мы инициализируем значения в семафорах: в первом -- единицей,
так как он контролирует доступ к ресурсу, во втором -- длиной буфера
(заданной в командной строке), в третьем -- нулём (т.е. числом
элементов в буфере).
/* Попытаться заблокировать ресурс (семафор номер 0) */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Уменьшить свободное место (семафор номер 1) /
Добавить элемент (семафор номер 2) */
if (semop(semid, &push, 2) != -1){
printf("---> Process:%dn", getpid());
}
else{
printf("---> Process:%d BUFFER FULLn", getpid());
}
/* Освободить ресурс */
semop(semid, &rel_res, 1);
Процесс W пытается заблокировать ресурс посредством действия lock_res;
как только это ему удаётся, он добавляет элемент в буфер посредством
действия push и выводит сообщение об этом на стандартный вывод. Если
операция не может быть произведена, процесс выводит сообщение о
заполнении буфера. В конце процесс освобождает ресурс.
/* Попытаться заблокировать ресурс (семафор номер 0) */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Увеличить свободное место (семафор номер 1) /
Взять элемент (семафор номер 2) */
if (semop(semid, &pop, 2) != -1){
printf("<--- Process:%dn", getpid());
}
else printf("<--- Process:%d BUFFER EMPTYn", getpid());
/* Отпустить ресурс */
semop(semid, &rel_res, 1);
Процесс R ведёт себя практически так же как и W процесс: блокирует
ресурс, производит действие pop, освобождает ресурс.
В следующей статье мы поговорим об очередях сообщений: другой
структуре для межпроцессового общения и синхронизации. Как всегда,
если вы пишете что-нибудь простое, используя информацию из этой
статьи, присылайте это мне, с вашим именем и e-mail адресом, буду рад
прочитать. Удачи!
Рекомендуемая литература
* Silberschatz, Galvin, Gagne, Operating System Concepts - Sixth
Edition, Wiley&Sons, 2001
* Tanenbaum, WoodHull, Operating Systems: Design and Implementation
- Second Edition, Prentice Hall, 2000
* Stallings, Operating Systems - Fourth Edition, Prentice Hall, 2002
* Bovet, Cesati, Understanding the Linux Kernel, O'Reilly, 2000
* The Linux Programmer's Guide:
http://www.tldp.org/LDP/lpg/index.html
* Linux Kernel 2.4 Internals
http://www.tldp.org/LDP/lki/lki-5.html
Vova
