Параллельное программирование - взаимодействие между процессами.

Linux-admin.net.ru / Программирование в UNIX / Параллельное программирование - взаимодействие между процессами.

Параллельное программирование - взаимодействие между процессами.

Резюме:

Целью данной серии статей является ознакомление читателя с концепцией многозадачности и её реализацией в операционной системе 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 
#include 
#include 
#include 
#include 

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 
#include 
#include 
#include 
#include 
#include 

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 адресом, буду рад прочитать. Удачи!

Введение

Ключи SysV

Семафоры

Рекомендуемая литература