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

ArticleCategory:

AuthorImage:

TranslationInfo:

original in it: Leonardo Giordani

it to en: Leonardo Giordani

en to ru Dmitry Martsynkevitch

AboutTheAuthor:

Студент Политехнического Университета Милана, учится на факультете телекоммуникационных технологий, работает сетевым администратором и интересуется программированием (в основном на Ассемблере и C/C++). С 1999 практически постоянно работает в Linux/Unix.

Abstract:

Что необходимо знать для понимания данной статьи:

• Минимальные знания shell
• Основы языка C (синтаксис, циклы, библиотеки)

ArticleIllustration:

ArticleBody:

Введение

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

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

Поговорим о некоторых классических проблемах одновременного использования данных; если два процесса одновременно читают один набор данных, то это, очевидно, не создаёт проблем, и выполнение процессов — последовательное. Пусть теперь один процесс изменяет набор данных: результат работы второго процесса будет зависеть от того, прочёл процесс данные до или после их изменения. Например: у нас есть два процесса "А" и "В" и целое число "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

key_t ftok(const char *pathname, int proj_id);

Семафоры

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

Семафоры можно использовать и для других целей, например для счётчика ресурсов. В этом случае число в семафоре — количество свободных ресурсов (например количество свободных ячеек памяти).

Рассмотрим практическое применение семафоров. Пусть у нас есть буфер, в который несколько процессов S1,...,Sn могут писать, и только один процесс L может из него читать. Также операции нельзя выполнять одновременно (в данный момент времени только один процесс должен оперировать с буфером). Очевидно, что процессы Si могут писать всегда, когда буфер не полон, а процесс L может читать, когда буфер не пуст. Таким образом, нам необходимо три семафора: один управляет доступом к буферу, а два других следят за числом элементов в нём.

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

Рассмотрим, как реализованы семафоры на C, в SysV. Создаёт семафор функция semget(2)

int semget(key_t key, int nsems, int semflg);

Давайте создадим наш первый семафор

#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;
}

int semctl(int semid, int semnum, int cmd, ...)

union semun {
 int val;                  /* значение для SETVAL */
 struct semid_ds *buf;     /* буферы для  IPC_STAT, IPC_SET */
 unsigned short *array;    /* массивы для GETALL, SETALL */
                           /* часть, особенная для Linux: */
 struct seminfo *__buf;    /* буфер для IPC_INFO */
};

[...]

  /* создать только один семафор */
  semid = semget(key, 1, 0666 | IPC_CREAT);

  /* в семафоре 0 установить значение 1 */
  arg.val = 1;
  semctl(semid, 0, SETVAL, arg);

[...]

[...]

  /* в семафоре 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);

unsigned short sem_num; short sem_op; short sem_flg;

1. sem_op < 0
   Если модуль значения в семафоре больше или равен модулю sem_op, то sem_op добавляется к значению в семафоре (т.е. значение в семафоре уменьшается). Если модуль sem_op больше, то процесс переходит в спящий режим, пока не будет достаточно ресурсов.
2. sem_op = 0
   Процесс спит пока значение в семафоре не достигнет нуля.
3. sem_op > 0
   Значение sem_op добавляется к значению в семафоре, используемый ресурс освобождается.

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

Почему нам нужно три семафора? Первый (с номером 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};

Действия 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);

/* Попытаться заблокировать ресурс (семафор номер 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);

В следующей статье мы поговорим об очередях сообщений: другой структуре для межпроцессового общения и синхронизации. Как всегда, если вы пишете что-нибудь простое, используя информацию из этой статьи, присылайте это мне, с вашим именем и 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