sorry but:
Параллельное программирование — взаимодействие между процессами.
Резюме:
Целью данной серии статей является ознакомление читателя с концепцией многозадачности и её реализацией в операционной системе 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) и флагом, устанавливающим режим ожидания; пусть пока он будет нулём. Операции, которые мы можем указать, являются целыми числами и подчиняются следующим правилам:
sem_op < 0
Если модуль значения в семафоре больше или равен модулю sem_op, то sem_op добавляется к значению в семафоре (т.е. значение в семафоре уменьшается). Если модуль sem_op больше, то процесс переходит в спящий режим, пока не будет достаточно ресурсов.
sem_op = 0
Процесс спит пока значение в семафоре не достигнет нуля.
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>
int main(int argc, char *argv[])
{
/* IPC */
pid_t pid;
key_t key;
int semid;
union semun arg;
struct sembuf lock_res = {0, -1, 0};
struct sembuf rel_res = {0, 1, 0};
struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT};
struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT};
/* Остальное */
int i;
if(argc < 2){
printf("Usage: bufdemo [dimensione]\n");
exit(0);
}
/* Семафоры */
key = ftok("/etc/fstab", getpid());
/* Создать набор из трёх семафоров */
semid = semget(key, 3, 0666 | IPC_CREAT);
/* Установить в семафоре номер 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);
/* Fork */
for (i = 0; i < 5; i++){
pid = fork();
if (!pid){
for (i = 0; i < 20; i++){
sleep(rand()%6);
/* Попытаться заблокировать ресурс (семафор номер 0) */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Уменьшить свободное место (семафор номер 1) /
Добавить элемент (семафор номер 2) */
if (semop(semid, &push, 2) != -1){
printf("---> Process:%d\n", getpid());
}
else{
printf("---> Process:%d BUFFER FULL\n", getpid());
}
/* Разблокировать ресурс */
semop(semid, &rel_res, 1);
}
exit(0);
}
}
for (i = 0;i < 100; i++){
sleep(rand()%3);
/* Попытаться заблокировать ресурс (семафор номер 0)*/
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Увеличить свободное место (семафор номер 1) /
Взять элемент (семафор номер 2) */
if (semop(semid, &pop, 2) != -1){
printf("<--- Process:%d\n", getpid());
}
else printf("<--- Process:%d BUFFER EMPTY\n", getpid());
/* Разблокировать ресурс */
semop(semid, &rel_res, 1);
}
/* Удалить семафоры */
semctl(semid, 0, IPC_RMID);
return 0;
}
Прокомментируем наиболее интересные части кода:
struct sembuf lock_res = {0, -1, 0};
struct sembuf rel_res = {0, 1, 0};
struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT};
struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT};
Эти четыре строки — действия, которые мы можем производить над семафорами: первые две — содержат по одному действия каждая, вторые — по две. Первое действие, 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:%d\n", getpid());
}
else{
printf("---> Process:%d BUFFER FULL\n", 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:%d\n", getpid());
}
else printf("<--- Process:%d BUFFER EMPTY\n", 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
Многопоточность в Unix
Похожие темы
Линейный вид
