Семафоры, мьютексы, атомарные операции и взаимоблокировки

Семафор Дейкстры

Семафор — целочисленная переменная, доступная только через две неделимые операции:

Неделимость обеспечивает ядро (или атомарные инструкции), а ожидание — без траты процессора: процесс спит.

Три шаблона

1. Взаимное исключение (S = 1)

sem_wait(&mutex);
/* критическая секция */
sem_post(&mutex);

2. Сигнализация (S = 0)

/* процесс A — ждёт события */        /* процесс B — сообщает */
sem_wait(&event);                      do_work();
use_result();                          sem_post(&event);

Неважно, кто придёт первым: если B успел сделать post раньше, A пройдёт wait без ожидания.

3. Производитель — потребитель (буфер на N ячеек)

sem_t empty;   /* = N: свободные ячейки */
sem_t full;    /* = 0: заполненные ячейки */
sem_t mutex;   /* = 1: доступ к буферу */

/* производитель */                   /* потребитель */
sem_wait(&empty);                      sem_wait(&full);
sem_wait(&mutex);                      sem_wait(&mutex);
put(item);                             item = get();
sem_post(&mutex);                      sem_post(&mutex);
sem_post(&full);                       sem_post(&empty);

Случай N = 1 — «почтовый ящик на одно письмо»: писатель кладёт, читатель забирает, писатель кладёт следующее. Именно такой шаблон нужен в задаче 8(б): каждый процесс кладёт пару (pid, ppid) в единственную ячейку Mem, родитель печатает её и освобождает ячейку.

POSIX-семафоры между процессами

Неименованный семафор живёт прямо в разделяемой памяти — достаточно добавить поле в структуру:

#include <semaphore.h>

typedef struct {
    int state;
    unsigned int counter;
    pid_t pid;
    pid_t ppid;
    sem_t full;      /* добавленные поля */
    sem_t empty;
} Mem;

Mem *mem = mmap(NULL, sizeof(Mem), PROT_READ | PROT_WRITE,
                MAP_SHARED | MAP_ANONYMOUS, -1, 0);
sem_init(&mem->empty, 1, 1);   /* pshared = 1: для процессов; значение 1 */
sem_init(&mem->full, 1, 0);
/* ... fork ... */
sem_destroy(&mem->full);

Второй аргумент sem_init — pshared: 0 — между потоками процесса, не 0 — между процессами (тогда семафор обязан лежать в разделяемой памяти).

Именованный семафор — для неродственных процессов:

sem_t *s = sem_open("/mysem", O_CREAT, 0600, 1);
sem_wait(s); /* ... */ sem_post(s);
sem_close(s);
sem_unlink("/mysem");

Компиляция: gcc prog.c -pthread.

Мьютексы

Мьютекс — замок с владельцем: открыть может только тот, кто закрыл. Для потоков:

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&m);
/* ... */
pthread_mutex_unlock(&m);

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

pthread_mutexattr_t a;
pthread_mutexattr_init(&a);
pthread_mutexattr_setpshared(&a, PTHREAD_PROCESS_SHARED);
pthread_mutex_init(&mem->mtx, &a);

К мьютексу добавляют условные переменные (pthread_cond_wait / pthread_cond_signal) — ждать, пока выполнится условие («ячейка свободна»).

Как это устроено: futex

В Linux семафоры и мьютексы построены на futex (fast userspace mutex): захват свободного замка — одна атомарная инструкция без входа в ядро; только если замок занят, процесс делает системный вызов futex(FUTEX_WAIT) и засыпает в ядре, а освобождающий вызывает futex(FUTEX_WAKE). Быстро в частом случае, без траты процессора в редком.

System V семафоры

Старый интерфейс: наборы семафоров, операции над несколькими сразу.

int id = semget(IPC_PRIVATE, 1, IPC_CREAT | 0600);
semctl(id, 0, SETVAL, 1);
struct sembuf p = {0, -1, 0}, v = {0, +1, 0};
semop(id, &p, 1);   /* P */
semop(id, &v, 1);   /* V */
semctl(id, 0, IPC_RMID);

Взаимоблокировки

Взаимоблокировка (deadlock) — группа процессов, каждый ждёт ресурс, удерживаемый другим.

/* процесс 1 */              /* процесс 2 */
sem_wait(&S1);                sem_wait(&S2);
sem_wait(&S2);  /* ждёт */    sem_wait(&S1);  /* ждёт */

Необходимые условия (Коффман): взаимное исключение, удержание и ожидание, отсутствие вытеснения, круговое ожидание. Нарушьте любое — взаимоблокировки не будет.

Итог

• Семафор: P уменьшает или усыпляет, V увеличивает и будит; начальное значение задаёт смысл (1 — мьютекс, 0 — сигнализация, N — пул).
• Между процессами: sem_init(&mem->s, 1, value) в разделяемой памяти, или sem_open; мьютекс с PTHREAD_PROCESS_SHARED.
• Производитель-потребитель на семафорах empty/full — шаблон для «почтового ящика» в задаче 8.
• Взаимоблокировка требует четырёх условий; проще всего нарушить круговое ожидание единым порядком захвата.