Лекция 4: Механизмы синхронизации, Тупики

Для повышения производительности вычислительных систем и облегчения задачи программистов существуют специальные механизмы синхронизации. Описание некоторых из них — семафоров Дейкстры, мониторов Хоара, очередей сообщений — приводится в этой лекции.

Рассмотренные в конце предыдущей лекции алгоритмы, хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок предполагает достаточно длительное вращение процесса в пустом цикле, то есть напрасную трату драгоценного времени процессора. Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования.

Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них — H — с высоким приоритетом, другой — L — с низким приоритетом. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритетный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все время своего CPU burst (если не появится процесс с еще большим приоритетом). Тогда в случае, если процесс L находится в своей критической секции, а процесс H, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс H не может войти в критическую область, находясь в цикле, а процесс L не получает управления, чтобы покинуть критический участок.

Для того чтобы не допустить возникновение подобных проблем, были разработаны различные механизмы синхронизации более высокого уровня. Описанию ряда из них — семафоров, мониторов и сообщений — и посвящена первая половина данной лекции.

Семафоры

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году.

Концепция семафоров

Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: P (от датского слова proberen — проверять) и V (от verhogen — увеличивать). Семафоры могут быть бинарными (только 0 или 1), либо счётными.

Классическое определение этих операций выглядит следующим образом:

P(S):
    пока `S == 0`, процесс блокируется;
    `S = S – 1`;

V(S):
    `S = S + 1`;

Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1. Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При выполнении операции V над семафором S к его значению просто прибавляется 1. В момент создания семафор может быть инициализирован любым неотрицательным значением.

Подобные переменные-семафоры могут с успехом применяться для решения различных задач организации взаимодействия процессов. В ряде языков программирования они были непосредственно введены в синтаксис языка (например, в ALGOL-68), в других случаях реализуются с помощью специальных системных вызовов. Соответствующая целая переменная располагается внутри адресного пространства ядра операционной системы. Операционная система обеспечивает атомарность операций P и V, используя, например, метод запрета прерываний на время выполнения соответствующих системных вызовов. Если при выполнении операции P заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным, например, FIFO.

Мьютекс - как подтип семафора

Мьютекс ( Mutual Exclusion ) — это механизм синхронизации, используемый в многопоточных программах для обеспечения взаимного исключения при доступе к разделяемым ресурсам: он гарантирует, что только один поток одновременно может войти в критическую секцию кода, защищая её от параллельного выполнения, что предотвращает гонки данных и несогласованность состояния. Работает как «ключ» — поток, получивший владение мьютексом через операцию lock, выполняет защищённый код, а другие потоки, пытающиеся захватить тот же мьютекс, блокируются до его освобождения через unlock; в отличие от семафора, мьютекс поддерживает владение (только захвативший его поток может его освободить) и чаще всего используется как бинарный примитив (состояния «занято»/«свободно»), что делает его идеальным для защиты отдельных ресурсов, таких как глобальные переменные или структуры данных. Мьютекс может принимать значения либо 0 либо 1.

Решение проблемы Producer-Consumer с помощью семафоров

Одной из типовых задач, требующих организации взаимодействия процессов, является задача producer-consumer (производитель-потребитель). Пусть два процесса обмениваются информацией через буфер ограниченного размера. Производитель закладывает информацию в буфер, а потребитель извлекает ее оттуда. На этом уровне деятельность потребителя и производителя можно описать следующим образом.

Producer:
    while(1) {
        produce_item;
        put_item;
    }

Consumer:
    while(1) {
        get_item;
        consume_item;
    }

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

Как можно реализовать эти условия с помощью семафоров? Возьмем три семафора: empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появится информация. Семафор empty будем использовать для организации ожидания производителя при заполненном буфере, а семафор mutex — для организации взаимоисключения на критических участках, которыми являются действия put_item и get_item (операции "положить информацию" и "взять информацию" не могут пересекаться, так как в этом случае возникнет опасность искажения информации). Тогда решение задачи на C-подобном языке выглядит так:

Semaphore mutex = 1;
Semaphore empty = N; /* где N – емкость буфера*/
Semaphore full = 0;

Producer:
    while(1) {
        produce_item;
        P(empty);
        P(mutex);
        put_item;
        V(mutex);
        V(full);
    }

Consumer:
    while(1) {
        P(full);
        P(mutex);
        get_item;
        V(mutex);
        V(empty);
        consume_item;
    }

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

INFO

Изучение семафоров в Linux

---

1. Введение В Linux используются два типа семафоров:

• POSIX-семафоры (современные, проще в использовании).
• System V семафоры (устаревшие, сложнее).

В этой практике мы сосредоточимся на POSIX-семафорах, так как они более интуитивны и широко применяются в современных приложениях.

---

2. Основные функции POSIX-семафоров

Функция	Назначение
sem_init()	Инициализация безымянного семафора.
sem_wait()	Уменьшает значение семафора (блокируется при 0).
sem_post()	Увеличивает значение семафора (разблокирует потоки).
sem_destroy()	Уничтожает безымянный семафор.
sem_open()	Создает/открывает именованный семафор.
sem_close()	Закрывает именованный семафор.
sem_unlink()	Удаляет именованный семафор из системы.

Важно:

• Для компиляции нужны флаги: -pthread (для потоков) и -lrt (для именованных семафоров).
• Имена именованных семафоров должны начинаться с / (например, /my_sem).

---

Пример 1: Безымянный семафор (синхронизация потоков)

Задача: Два потока увеличивают общую переменную counter. Защитить доступ к ней с помощью семафора.

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

sem_t sem;
int counter = 0;

void* increment(void* arg) {
    for (int i = 0; i < 100000; i++) {
        sem_wait(&sem); // Вход в критическую секцию
        counter++;
        sem_post(&sem); // Выход из критической секции
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;
    
    // Инициализация семафора (начальное значение = 1)
    sem_init(&sem, 0, 1);
    
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    
    sem_destroy(&sem);
    printf("Final counter value: %d\n", counter); // Должно быть 200000
    return 0;
}

Пояснение:

• sem_init(&sem, 0, 1) — создает безымянный семафор с начальным значением 1 (аналог мьютекса).
• sem_wait() блокирует поток, если значение семафора = 0. Уменьшает значение на 1.
• sem_post() увеличивает значение на 1, разрешая доступ другому потоку.

Компиляция:

gcc threads.c -o threads -pthread

Ошибки:

• Если забыть sem_init(), программа упадет с ошибкой Segmentation fault.
• Если не вызвать sem_destroy(), возможны утечки ресурсов.

---

Пример 2: Именованный семафор (синхронизация процессов)

Задача: Два процесса поочередно увеличивают счетчик в разделяемой памяти.

Процесс 1 (writer.c):

#include <semaphore.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>

int main() {
    int* counter = mmap(NULL, sizeof(int), PROT_READ | PROT_WRITE, 
                        MAP_SHARED | MAP_ANONYMOUS, -1, 0);
    *counter = 0;

    sem_t* sem = sem_open("/my_sem", O_CREAT, 0644, 1);
    if (sem == SEM_FAILED) {
        perror("sem_open");
        return 1;
    }

    for (int i = 0; i < 5; i++) {
        sem_wait(sem);
        (*counter)++;
        printf("Writer: counter = %d\n", *counter);
        sem_post(sem);
        sleep(1);
    }

    munmap(counter, sizeof(int));
    sem_close(sem);
    return 0;
}

Процесс 2 (reader.c):

#include <semaphore.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>

int main() {
    sem_t* sem = sem_open("/my_sem", 0); // Открыть существующий семафор
    if (sem == SEM_FAILED) {
        perror("sem_open");
        return 1;
    }

    for (int i = 0; i < 5; i++) {
        sem_wait(sem);
        printf("Reader: counter is accessed\n");
        sem_post(sem);
        sleep(1);
    }

    sem_close(sem);
    sem_unlink("/my_sem"); // Удалить семафор из системы
    return 0;
}

Как запустить:

1. Скомпилировать оба файла:

   gcc writer.c -o writer -pthread -lrt
   gcc reader.c -o reader -pthread -lrt

2. Запустить процессы в разных терминалах:

   ./writer  # В первом окне
   ./reader  # Во втором окне

Пояснение:

• sem_open("/my_sem", O_CREAT, 0644, 1) — создает именованный семафор.
• sem_unlink("/my_sem") удаляет семафор из системы после завершения работы. Без этого шага семафор останется в системе!

Ошибки:

• Если не вызвать sem_unlink(), семафор останется в /dev/shm и может мешать последующим запускам.
• Если процессы завершатся аварийно, используйте ipcs -s для просмотра "забытых" семафоров и ipcrm для их удаления.

Мониторы

Хотя решение задачи producer-consumer с помощью семафоров выглядит достаточно изящно, программирование с их использованием требует повышенной осторожности и внимания, чем отчасти напоминает программирование на языке Ассемблера. Допустим, что в рассмотренном примере мы случайно поменяли местами операции P, сначала выполнив операцию для семафора mutex, а уже затем для семафоров full и empty. Допустим теперь, что потребитель, войдя в свой критический участок (mutex сброшен), обнаруживает, что буфер пуст. Он блокируется и начинает ждать появления сообщений. Но производитель не может войти в критический участок для передачи информации, так как тот заблокирован потребителем. Получаем тупиковую ситуацию.

В сложных программах произвести анализ правильности использования семафоров с карандашом в руках становится очень непросто. В то же время обычные способы отладки программ зачастую не дают результата, поскольку возникновение ошибок зависит от interleaving атомарных операций, и ошибки могут быть трудновоспроизводимы. Для того чтобы облегчить работу программистов, в 1974 году Хоаром (Hoare) был предложен механизм еще более высокого уровня, чем семафоры, получивший название мониторов. Мы с вами рассмотрим конструкцию, несколько отличающуюся от оригинальной.

Мониторы представляют собой тип данных, который может быть с успехом внедрен в объектно-ориентированные языки программирования. Монитор обладает собственными переменными, определяющими его состояние. Значения этих переменных извне могут быть изменены только с помощью вызова функций-методов, принадлежащих монитору. В свою очередь, эти функции-методы могут использовать в работе только данные, находящиеся внутри монитора, и свои параметры. На абстрактном уровне можно описать структуру монитора следующим образом:

monitor monitor_name {
    описание внутренних переменных;

    void m1(...) {
        ...
    }

    void m2(...) {
        ...
    }

    ...

    void mn(...) {
        ...
    }

    {
        блок инициализации внутренних переменных;
    }
}

Здесь функции m1, ..., mn представляют собой функции-методы монитора, а блок инициализации внутренних переменных содержит операции, которые выполняются один и только один раз: при создании монитора или при самом первом вызове какой-либо функции-метода до ее исполнения.

Важной особенностью мониторов является то, что в любой момент времени только один процесс может быть активен, т. е. находиться в состоянии "готовность" или "исполнение", внутри данного монитора. Поскольку мониторы представляют собой особые конструкции языка программирования, компилятор может отличить вызов функции, принадлежащей монитору, от вызовов других функций и обработать его специальным образом, добавив к нему пролог и эпилог, реализующий взаимоисключение. Так как обязанность конструирования механизма взаимоисключений возложена на компилятор, а не на программиста, работа программиста при использовании мониторов существенно упрощается, а вероятность возникновения ошибок становится меньше.

Однако одних только взаимоисключений недостаточно для того, чтобы в полном объеме реализовать решение задач, возникающих при взаимодействии процессов. Нам нужны еще и средства организации очередности процессов, подобно семафорам full и empty в предыдущем примере. Для этого в мониторах было введено понятие условных переменных (condition variables), над которыми можно совершать две операции wait и signal, отчасти похожие на операции P и V над семафорами.

Если функция монитора не может выполняться дальше, пока не наступит некоторое событие, она выполняет операцию wait над какой-либо условной переменной. При этом процесс, выполнивший операцию wait, блокируется, становится неактивным, и другой процесс получает возможность войти в монитор. Когда ожидаемое событие происходит, другой процесс внутри функции-метода совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным. Если несколько процессов дожидались операции signal для этой переменной, то активным становится только один из них.

Что можно предпринять для того, чтобы у нас не оказалось двух процессов, разбудившего и пробужденного, одновременно активных внутри монитора? Хоар предложил, чтобы пробужденный процесс подавлял исполнение разбудившего процесса, пока он сам не покинет монитор. Несколько позже Хансен (Hansen) предложил другой механизм: разбудивший процесс покидает монитор немедленно после исполнения операции signal. Мы будем придерживаться подхода Хансена.

Необходимо отметить, что условные переменные, в отличие от семафоров Дейкстры, не умеют запоминать предысторию. Это означает, что операция signal всегда должна выполняться после операции wait. Если операция signal выполняется над условной переменной, с которой не связано ни одного заблокированного процесса, то информация о произошедшем событии будет утеряна. Следовательно, выполнение операции wait всегда будет приводить к блокированию процесса.

Давайте применим концепцию мониторов к решению задачи производитель-потребитель.

monitor ProducerConsumer {
    condition full, empty;
    int count;

    void put() {
        if (count == N) full.wait;
        put_item;
        count += 1;
        if (count == 1) empty.signal;
    }

    void get() {
        if (count == 0) empty.wait;
        get_item();
        count -= 1;
        if (count == N-1) full.signal;
    }

    {
        count = 0;
    }
}

Producer:
    while(1) {
        produce_item;
        ProducerConsumer.put();
    }

Consumer:
    while(1) {
        ProducerConsumer.get();
        consume_item;
    }

Легко убедиться, что приведенный пример действительно решает поставленную задачу.

Реализация мониторов требует разработки специальных языков программирования и компиляторов для них. Мониторы встречаются в таких языках, как параллельный Евклид, параллельный Паскаль, Java и т. д. Эмуляция мониторов с помощью системных вызовов для обычных широко используемых языков программирования не так проста, как эмуляция семафоров. Поэтому можно пользоваться еще одним механизмом со скрытыми взаимоисключениями, механизмом, о котором мы уже упоминали, — передачей сообщений.

INFO

Изучение мониторов Хоара в Linux

---

1. Введение

В Linux мониторы не реализованы напрямую, но их логику можно смоделировать с помощью мьютексов (pthread_mutex_t) и условных переменных (pthread_cond_t) из библиотеки pthread. Это позволяет создавать безопасные для многопоточного доступа структуры данных с четко определенными интерфейсами.

---

2. Основные компоненты монитора

Компонент	Назначение
Мьютекс	Обеспечивает взаимное исключение (только один поток в критической секции).
Условные переменные	Позволяют потокам ожидать выполнения условия (cond_wait) и сигнализировать о его изменении (cond_signal).
Инвариант монитора	Логическое условие, которое всегда истинно при входе/выходе из методов монитора (например, buffer_size >= 0).

Важно:

• Условные переменные не заменяют мьютекс — они работают в связке с ним.
• Проверка условия всегда делается в цикле while, а не через if, чтобы избежать ложных пробуждений.

---

3. Пример: Монитор для задачи "Производитель-Потребитель"

Код для наглядной демонстрации работы монитора Хоара

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h> // Для usleep()

// Глобальный мьютекс для синхронизации вывода (чтобы сообщения не перемешивались)
pthread_mutex_t print_mutex = PTHREAD_MUTEX_INITIALIZER;

typedef struct {
    int* buffer;
    int capacity;
    int count;
    int in;
    int out;
    pthread_mutex_t mutex;
    pthread_cond_t not_full;
    pthread_cond_t not_empty;
} MonitorBuffer;

void monitor_init(MonitorBuffer* buf, int capacity) {
    buf->buffer = malloc(capacity * sizeof(int));
    buf->capacity = capacity;
    buf->count = 0;
    buf->in = 0;
    buf->out = 0;
    pthread_mutex_init(&buf->mutex, NULL);
    pthread_cond_init(&buf->not_full, NULL);
    pthread_cond_init(&buf->not_empty, NULL);
}

void monitor_put(MonitorBuffer* buf, int item, long tid) {
    pthread_mutex_lock(&buf->mutex);
    
    // Отладка: вход в критическую секцию
    pthread_mutex_lock(&print_mutex);
    printf("[Thread %ld] ⛔ Пытается добавить %d (count=%d)\n", tid, item, buf->count);
    pthread_mutex_unlock(&print_mutex);

    while (buf->count == buf->capacity) {
        pthread_mutex_lock(&print_mutex);
        printf("[Thread %ld] ⚠️ Буфер полон! Ожидает not_full...\n", tid);
        pthread_mutex_unlock(&print_mutex);
        pthread_cond_wait(&buf->not_full, &buf->mutex);
    }

    // Добавление элемента
    buf->buffer[buf->in] = item;
    int current_in = buf->in;
    buf->in = (buf->in + 1) % buf->capacity;
    buf->count++;

    // Визуализация состояния буфера
    pthread_mutex_lock(&print_mutex);
    printf("[Thread %ld] ➕ Добавлен %d → buffer[%d] | count=%d | [", 
           tid, item, current_in, buf->count);
    for (int i = 0; i < buf->capacity; i++) {
        if (i >= buf->out && i < buf->out + buf->count) 
            printf(" %d ", buf->buffer[i % buf->capacity]);
        else 
            printf(" _ ");
    }
    printf(" ]\n");
    pthread_mutex_unlock(&print_mutex);

    pthread_cond_signal(&buf->not_empty);
    pthread_mutex_unlock(&buf->mutex);
}

int monitor_get(MonitorBuffer* buf, long tid) {
    pthread_mutex_lock(&buf->mutex);
    
    // Отладка: вход в критическую секцию
    pthread_mutex_lock(&print_mutex);
    printf("[Thread %ld] ⛔ Пытается извлечь (count=%d)\n", tid, buf->count);
    pthread_mutex_unlock(&print_mutex);

    while (buf->count == 0) {
        pthread_mutex_lock(&print_mutex);
        printf("[Thread %ld] ⚠️ Буфер пуст! Ожидает not_empty...\n", tid);
        pthread_mutex_unlock(&print_mutex);
        pthread_cond_wait(&buf->not_empty, &buf->mutex);
    }

    // Извлечение элемента
    int item = buf->buffer[buf->out];
    int current_out = buf->out;
    buf->out = (buf->out + 1) % buf->capacity;
    buf->count--;

    // Визуализация состояния буфера
    pthread_mutex_lock(&print_mutex);
    printf("[Thread %ld] ➖ Извлечен %d из buffer[%d] | count=%d | [", 
           tid, item, current_out, buf->count);
    for (int i = 0; i < buf->capacity; i++) {
        if (i >= buf->out && i < buf->out + buf->count) 
            printf(" %d ", buf->buffer[i % buf->capacity]);
        else 
            printf(" _ ");
    }
    printf(" ]\n");
    pthread_mutex_unlock(&print_mutex);

    pthread_cond_signal(&buf->not_full);
    pthread_mutex_unlock(&buf->mutex);
    return item;
}

void monitor_destroy(MonitorBuffer* buf) {
    free(buf->buffer);
    pthread_mutex_destroy(&buf->mutex);
    pthread_cond_destroy(&buf->not_full);
    pthread_cond_destroy(&buf->not_empty);
}

// Поток-производитель
void* producer(void* arg) {
    MonitorBuffer* buf = (MonitorBuffer*)arg;
    long tid = (long)pthread_self(); // Уникальный ID потока

    for (int i = 0; i < 5; i++) {
        usleep(rand() % 500000); // Случайная задержка (0.5 сек)
        monitor_put(buf, i, tid);
    }
    return NULL;
}

// Поток-потребитель
void* consumer(void* arg) {
    MonitorBuffer* buf = (MonitorBuffer*)arg;
    long tid = (long)pthread_self(); // Уникальный ID потока

    for (int i = 0; i < 5; i++) {
        usleep(rand() % 800000); // Случайная задержка (0.8 сек)
        monitor_get(buf, tid);
    }
    return NULL;
}

int main() {
    MonitorBuffer buf;
    monitor_init(&buf, 3); // Буфер на 3 элемента (для наглядности)

    pthread_t p1, p2, c1, c2;

    // Запускаем 2 производителя и 2 потребителя
    pthread_create(&p1, NULL, producer, &buf);
    pthread_create(&p2, NULL, producer, &buf);
    pthread_create(&c1, NULL, consumer, &buf);
    pthread_create(&c2, NULL, consumer, &buf);

    // Ждем завершения
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    pthread_join(c1, NULL);
    pthread_join(c2, NULL);

    monitor_destroy(&buf);
    return 0;
}

---

Как это работает на практике

1. Наглядная визуализация буфера:
   Каждая операция выводит текущее состояние буфера в формате:
   [ _ 1 2 ] — пустые слоты обозначены _, занятые — числами.

2. Отладочные сообщения:

   • ⛔ Пытается добавить... — вход в критическую секцию.
   • ⚠️ Буфер полон! Ожидает... — демонстрация блокировки.
   • ➕ Добавлен... / ➖ Извлечен... — успешная операция с отображением изменений.

3. Случайные задержки:
   usleep(rand() % ...) имитирует реальную нагрузку, заставляя потоки конкурировать за доступ к буферу.

4. Множество потоков:
   2 производителя и 2 потребителя показывают, как монитор корректно обрабатывает конкуренцию.

---

Пример вывода (упрощенный)

[Thread 140735825880832] ⛔ Пытается добавить 0 (count=0)
[Thread 140735825880832] ➕ Добавлен 0 → buffer[0] | count=1 | [ 0  _  _  ]
[Thread 140735731988224] ⛔ Пытается добавить 0 (count=1)
[Thread 140735731988224] ➕ Добавлен 0 → buffer[1] | count=2 | [ 0  0  _  ]
[Thread 140735638095616] ⛔ Пытается извлечь (count=2)
[Thread 140735638095616] ➖ Извлечен 0 из buffer[0] | count=1 | [ _  0  _  ]
[Thread 140735544203008] ⛔ Пытается добавить 0 (count=1)
[Thread 140735544203008] ➕ Добавлен 0 → buffer[2] | count=2 | [ _  0  0  ]
[Thread 140735544203008] ⛔ Пытается добавить 1 (count=2)
[Thread 140735544203008] ⚠️ Буфер полон! Ожидает not_full...
[Thread 140735638095616] ⛔ Пытается извлечь (count=2)
[Thread 140735638095616] ➖ Извлечен 0 из buffer[1] | count=1 | [ _  _  0  ]
[Thread 140735544203008] ➕ Добавлен 1 → buffer[0] | count=2 | [ 1  _  0  ]

---

Почему это эффективно для обучения?

• Видно блокировки: Сообщения ⚠️ Буфер полон/пуст показывают, когда потоки ждут.
• Состояние буфера всегда на виду: Студенты видят, как меняется count, in, out.
• Реалистичная конкуренция: Случайные задержки имитируют реальные условия.
• Исправлена критическая ошибка: В исходном коде был pthread_cond_attr_t вместо pthread_cond_t — теперь код работает корректно.

Компиляция и запуск:

gcc monitor_demo.c -o monitor_demo -pthread && ./monitor_demo

Сообщения

Для прямой и непрямой адресации достаточно двух примитивов, чтобы описать передачу сообщений по линии связи — send и receive. В случае прямой адресации мы будем обозначать их так:

• send(P, message) — послать сообщение message процессу P;
• receive(Q, message) — получить сообщение message от процесса Q.

В случае непрямой адресации мы будем обозначать их так:

• send(A, message) — послать сообщение message в почтовый ящик A;
• receive(A, message) — получить сообщение message из почтового ящика A.

Примитивы send и receive уже имеют скрытый от наших глаз механизм взаимоисключения. Более того, в большинстве систем они уже имеют и скрытый механизм блокировки при чтении из пустого буфера и при записи в полностью заполненный буфер. Реализация решения задачи producer-consumer для таких примитивов становится неприлично тривиальной. Надо отметить, что, несмотря на простоту использования, передача сообщений в пределах одного компьютера происходит существенно медленнее, чем работа с семафорами и мониторами.

INFO

Передача сообщений с прямой и непрямой адресацией в Linux

---

1. Введение
В Linux передача сообщений реализуется через очереди сообщений POSIX (mqueue), которые скрывают сложность синхронизации:

• Прямая адресация — отправка конкретному процессу (имя очереди включает PID получателя, например /queue_1234).
• Непрямая адресация — отправка в общий «почтовый ящик» (фиксированное имя, например /mailbox).
  Ключевое преимущество: примитивы mq_send/mq_receive автоматически блокируют потоки при заполнении очереди или её пустоте, что делает решение задачи «производитель-потребитель» тривиальным. Однако из-за копирования данных между процессами IPC-очереди работают медленнее, чем семафоры или мониторы.

---

2. Основные функции POSIX-очередей

Функция	Назначение
mq_open()	Создает/открывает очередь по имени (начинается с /).
mq_send()	Отправляет сообщение (блокируется при заполнении).
mq_receive()	Получает сообщение (блокируется при пустоте).
mq_close()	Закрывает дескриптор очереди.
mq_unlink()	Удаляет очередь из системы.

Важно:

• Для компиляции нужны флаги: -pthread -lrt.
• Максимальная длина имени очереди — 255 символов, например /my_queue.
• Сообщения имеют приоритет (по умолчанию 0), но в учебных целях будем игнорировать его.

---

3. Пример 1: Прямая адресация (отправка конкретному процессу)
Задача: Процесс-отправитель посылает число процессу-получателю, используя очередь с именем /queue_<PID_получателя>.

Получатель (receiver.c):

#include <mqueue.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define MAX_MSG_SIZE 256

int main() {
    char queue_name[64];
    snprintf(queue_name, sizeof(queue_name), "/queue_%d", getpid());
    
    // Создаем очередь с правами 0644
    mqd_t mq = mq_open(queue_name, O_CREAT | O_RDONLY, 0644, NULL);
    if (mq == -1) {
        perror("mq_open");
        exit(1);
    }

    printf("[Receiver] Ожидаю сообщение в очереди %s...\n", queue_name);
    
    char buffer[MAX_MSG_SIZE];
    unsigned int priority;
    ssize_t bytes = mq_receive(mq, buffer, MAX_MSG_SIZE, &priority);
    
    if (bytes > 0) {
        buffer[bytes] = '\0';
        printf("[Receiver] Получено: %s\n", buffer);
    }

    mq_close(mq);
    mq_unlink(queue_name); // Удаляем очередь после завершения
    return 0;
}

Отправитель (sender.c):

#include <mqueue.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_MSG_SIZE 256

int main(int argc, char* argv[]) {
    if (argc != 3) {
        printf("Использование: %s <PID_получателя> <сообщение>\n", argv[0]);
        exit(1);
    }

    char queue_name[64];
    snprintf(queue_name, sizeof(queue_name), "/queue_%s", argv[1]);
    
    mqd_t mq = mq_open(queue_name, O_WRONLY);
    if (mq == -1) {
        perror("mq_open (sender)");
        exit(1);
    }

    printf("[Sender] Отправляю '%s' в очередь %s\n", argv[2], queue_name);
    mq_send(mq, argv[2], strlen(argv[2]), 0); // Приоритет = 0
    
    mq_close(mq);
    return 0;
}

Как запустить:

1. Скомпилировать:

gcc receiver.c -o receiver -lrt
gcc sender.c -o sender -lrt

2. Запустить получатель:

./receiver  # Выведет PID, например 5678

3. В новом терминале отправить сообщение:

./sender 5678 "Hello from sender!"

Пояснение:

• Имя очереди динамически генерируется как /queue_<PID>, обеспечивая прямую адресацию.
• mq_receive блокируется до появления сообщения (реализовано «из коробки»).
• mq_unlink удаляет очередь после завершения, иначе она останется в /dev/mqueue.

---

4. Пример 2: Непрямая адресация (общий почтовый ящик)
Задача: Два производителя и два потребителя используют общую очередь /mailbox для обмена числами.

Код (common_mailbox.c):

#include <mqueue.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define QUEUE_NAME "/mailbox"
#define MAX_MSG 10
#define MAX_MSG_SIZE 32

// Глобальный мьютекс для синхронизации вывода
pthread_mutex_t print_mutex = PTHREAD_MUTEX_INITIALIZER;

void* producer(void* arg) {
    long id = (long)arg;
    mqd_t mq = mq_open(QUEUE_NAME, O_WRONLY);
    
    for (int i = 0; i < MAX_MSG; i++) {
        char msg[16];
        snprintf(msg, sizeof(msg), "Prod%d:%d", (int)id, i);
        
        pthread_mutex_lock(&print_mutex);
        printf("[Producer %ld] Отправляет '%s'\n", id, msg);
        pthread_mutex_unlock(&print_mutex);
        
        mq_send(mq, msg, strlen(msg), 0);
        usleep(rand() % 300000); // Случайная задержка
    }
    return NULL;
}

void* consumer(void* arg) {
    long id = (long)arg;
    mqd_t mq = mq_open(QUEUE_NAME, O_RDONLY);
    char buffer[MAX_MSG_SIZE];
    
    for (int i = 0; i < MAX_MSG; i++) {
        unsigned int priority;
        ssize_t bytes = mq_receive(mq, buffer, MAX_MSG_SIZE, &priority);
        
        if (bytes > 0) {
            buffer[bytes] = '\0';
            pthread_mutex_lock(&print_mutex);
            printf("[Consumer %ld] Получил '%s'\n", id, buffer);
            pthread_mutex_unlock(&print_mutex);
        }
        usleep(rand() % 500000);
    }
    return NULL;
}

int main() {
    // Создаем очередь с максимальным размером 20 сообщений
    struct mq_attr attr = { .mq_maxmsg = 20, .mq_msgsize = MAX_MSG_SIZE };
    mqd_t mq = mq_open(QUEUE_NAME, O_CREAT | O_RDWR, 0644, &attr);
    if (mq == -1) {
        perror("mq_open (main)");
        exit(1);
    }
    mq_close(mq);

    pthread_t prods[2], cons[2];
    
    // Запускаем производителей и потребителей
    for (long i = 0; i < 2; i++) {
        pthread_create(&prods[i], NULL, producer, (void*)i);
        pthread_create(&cons[i], NULL, consumer, (void*)i);
    }

    for (int i = 0; i < 2; i++) {
        pthread_join(prods[i], NULL);
        pthread_join(cons[i], NULL);
    }

    mq_unlink(QUEUE_NAME); // Удаляем очередь
    return 0;
}

Как запустить:

gcc common_mailbox.c -o mailbox -pthread -lrt && ./mailbox

Пример вывода:

[Producer 0] Отправляет 'Prod0:0'
[Producer 1] Отправляет 'Prod1:0'
[Consumer 0] Получил 'Prod0:0'
[Consumer 1] Получил 'Prod1:0'
[Producer 0] Отправляет 'Prod0:1'
[Consumer 0] Получил 'Prod0:1'

Пояснение:

• Все процессы используют общую очередь /mailbox (непрямая адресация).
• mq_maxmsg = 20 — очередь блокирует отправку при достижении 20 сообщений.
• Случайные задержки (usleep) демонстрируют, как процессы конкурируют за доступ.

Тупики

Ранее мы рассматривали способы синхронизации процессов, которые позволяют процессам успешно кооперироваться. Однако в некоторых случаях могут возникнуть непредвиденные затруднения. Предположим, что несколько процессов конкурируют за обладание конечным числом ресурсов. Если запрашиваемый процессом ресурс недоступен, ОС переводит данный процесс в состояние ожидания. В случае когда требуемый ресурс удерживается другим ожидающим процессом, первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком (deadlock). Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация, или "зависание системы", является следствием того, что один или более процессов находятся в состоянии тупика. Иногда подобные ситуации называют взаимоблокировками. В общем случае проблема тупиков эффективного решения не имеет.

Рассмотрим пример. Предположим, что два процесса осуществляют вывод с ленты на принтер. Один из них успел монополизировать ленту и претендует на принтер, а другой — наоборот. После этого оба процесса оказываются заблокированными в ожидании второго ресурса.

Пример тупиковой ситуации

Определение

Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества. Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества, и, следовательно, все процессы будут спать вместе.

Выше приведен пример взаимоблокировки, возникающей при работе с так называемыми выделенными устройствами. Тупики, однако, могут иметь место и в других ситуациях. Например, в системах управления базами данных записи могут быть локализованы процессами, чтобы избежать состояния гонок. В этом случае может получиться так, что один из процессов заблокировал записи, необходимые другому процессу, и наоборот. Таким образом, тупики могут иметь место как на аппаратных, так и на программных ресурсах.

Тупики также могут быть вызваны ошибками программирования. Например, процесс может напрасно ждать открытия семафора, потому что в некорректно написанном приложении эту операцию забыли предусмотреть. Другой причиной бесконечного ожидания может быть дискриминационная политика по отношению к некоторым процессам. Однако чаще всего событие, которого ждет процесс в тупиковой ситуации, — освобождение ресурса, поэтому в дальнейшем будут рассмотрены методы борьбы с тупиками ресурсного типа.

Ресурсами могут быть как устройства, так и данные. Некоторые ресурсы допускают разделение между процессами, то есть являются разделяемыми ресурсами. Например, память, процессор, диски коллективно используются процессами. Другие не допускают разделения, то есть являются выделенными, например лентопротяжное устройство. К взаимоблокировке может привести использование как выделенных, так и разделяемых ресурсов. Например, чтение с разделяемого диска может одновременно осуществляться несколькими процессами, тогда как запись предполагает исключительный доступ к данным на диске. Можно считать, что часть диска, куда происходит запись, выделена конкретному процессу. Поэтому в дальнейшем мы будем исходить из предположения, что тупики связаны с выделенными ресурсами, то есть тупики возникают, когда процессу предоставляется эксклюзивный доступ к устройствам, файлам и другим ресурсам.

Традиционная последовательность событий при работе с ресурсом состоит из запроса, использования и освобождения ресурса. Тип запроса зависит от природы ресурса и от ОС. Запрос может быть явным, например специальный вызов request, или неявным — open для открытия файла. Обычно, если ресурс занят и запрос отклонен, запрашивающий процесс переходит в состояние ожидания.

Далее во второй части лекции будут рассматриваться вопросы обнаружения, предотвращения, обхода тупиков и восстановления после тупиков. Как правило, борьба с тупиками — очень дорогостоящее мероприятие. Тем не менее для ряда систем, например для систем реального времени, иного выхода нет.

Условия возникновения тупиков

Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.
2. Условие удержания и ожидания (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.
3. Условие неперераспределяемости (No preemption). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.

Для образования тупика необходимым и достаточным является выполнение всех четырех условий.

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

Основные направления борьбы с тупиками

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

Итак, основные направления борьбы с тупиками:

• Игнорирование проблемы в целом
• Предотвращение тупиков
• Обнаружение тупиков
• Восстановление после тупиков

Игнорирование проблемы тупиков

Простейший подход — не замечать проблему тупиков. Для того чтобы принять такое решение, необходимо оценить вероятность возникновения взаимоблокировки и сравнить ее с вероятностью ущерба от других отказов аппаратного и программного обеспечения. Проектировщики обычно не желают жертвовать производительностью системы или удобством пользователей для внедрения сложных и дорогостоящих средств борьбы с тупиками.

Любая ОС, имеющая в ядре ряд массивов фиксированной размерности, потенциально страдает от тупиков, даже если они не обнаружены. Таблица открытых файлов, таблица процессов, фактически каждая таблица являются ограниченными ресурсами. Заполнение всех записей таблицы процессов может привести к тому, что очередной запрос на создание процесса может быть отклонен. При неблагоприятном стечении обстоятельств несколько процессов могут выдать такой запрос одновременно и оказаться в тупике. Следует ли отказываться от вызова CreateProcess, чтобы решить эту проблему?

Подход большинства популярных ОС (Unix, Windows и др.) состоит в том, чтобы игнорировать данную проблему в предположении, что маловероятный случайный тупик предпочтительнее, чем нелепые правила, заставляющие пользователей ограничивать число процессов, открытых файлов и т. п. Сталкиваясь с нежелательным выбором между строгостью и удобством, трудно найти решение, которое устраивало бы всех.

Способы предотвращения тупиков

Цель предотвращения тупиков — обеспечить условия, исключающие возможность возникновения тупиковых ситуаций. Большинство методов связано с предотвращением одного из условий возникновения взаимоблокировки.

Система, предоставляя ресурс в распоряжение процесса, должна принять решение, безопасно это или нет. Возникает вопрос: есть ли такой алгоритм, который помогает всегда избегать тупиков и делать правильный выбор. Ответ — да, мы можем избегать тупиков, но только если определенная информация известна заранее.

Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира

Можно избежать взаимоблокировки, если распределять ресурсы, придерживаясь определенных правил. Среди такого рода алгоритмов наиболее известен алгоритм банкира, предложенный Дейкстрой, который базируется на так называемых безопасных или надежных состояниях (safe state). Безопасное состояние — это такое состояние, для которого имеется по крайней мере одна последовательность событий, которая не приведет к взаимоблокировке. Модель алгоритма основана на действиях банкира, который, имея в наличии капитал, выдает кредиты.

Суть алгоритма состоит в следующем:

• Предположим, что у системы в наличии n устройств, например лент.
• ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.
• Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени.
• Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени.
• В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.

Рассмотрим пример надежного состояния для системы с 3 пользователями и 11 устройствами, где 9 устройств задействовано, а 2 имеется в резерве. Пусть текущая ситуация такова:

Пользователи	Максимальная потребность в ресурсах	Выделенное пользователям количество ресурсов
Первый	9	6
Второй	10	2
Третий	3	1

Пример надежного состояния для системы с 3 пользователями и 11 устройствами. В запасе ещё осталось 2 ресурса

Данное состояние надежно. Последующие действия системы могут быть таковы. Вначале удовлетворить запросы третьего пользователя, затем дождаться, когда он закончит работу и освободит свои три устройства. Затем можно обслужить первого и второго пользователей. То есть система удовлетворяет только те запросы, которые оставляют ее в надежном состоянии, и отклоняет остальные.

Термин "ненадежное состояние" не предполагает, что обязательно возникнут тупики. Он лишь говорит о том, что в случае неблагоприятной последовательности событий система может зайти в тупик.

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

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

Наличие таких жестких и зачастую неприемлемых требований может склонить разработчиков к выбору других решений проблемы взаимоблокировки.

Предотвращение тупиков за счет нарушения условий возникновения тупиков

В отсутствие информации о будущих запросах единственный способ избежать взаимоблокировки — добиться невыполнения хотя бы одного из условий раздела "Условия возникновения тупиков".

Нарушение условия взаимоисключения

В общем случае избежать взаимоисключений невозможно. Доступ к некоторым ресурсам должен быть исключительным. Тем не менее некоторые устройства удается обобществить. В качестве примера рассмотрим принтер. Известно, что пытаться осуществлять вывод на принтер могут несколько процессов. Во избежание хаоса организуют промежуточное формирование всех выходных данных процесса на диске, то есть разделяемом устройстве. Лишь один системный процесс, называемый сервисом или демоном (от англ. daemon) принтера, отвечающий за вывод документов на печать по мере освобождения принтера, реально с ним взаимодействует. Эта схема называется спулингом(spooling). Таким образом, принтер становится разделяемым устройством, и тупик для него устранен.

INFO

С сервисами (демонами) будет очень много работы в модуле: ПМ.02: Организация сетевого администрирования операционных систем.

К сожалению, не для всех устройств и не для всех данных можно организовать спулинг. Неприятным побочным следствием такой модели может быть потенциальная тупиковая ситуация из-за конкуренции за дисковое пространство для буфера спулинга. Тем не менее в той или иной форме эта идея применяется часто.

Нарушение условия удержания и ожидания (Hold and wait)

Условия удержания и ожидания ресурсов можно избежать, потребовав выполнения стратегии двухфазного захвата:

• В первой фазе процесс должен запрашивать все необходимые ему ресурсы сразу. До тех пор пока они не предоставлены, процесс не может продолжать выполнение.
• Если в первой фазе некоторые ресурсы, которые были нужны данному процессу, уже заняты другими процессами, он освобождает все ресурсы, которые были ему выделены, и пытается повторить первую фазу.

В известном смысле этот подход напоминает требование захвата всех ресурсов заранее. Естественно, что только специально организованные программы могут быть приостановлены в течение первой фазы и рестартованы впоследствии.

Таким образом, один из способов — заставить все процессы затребовать нужные им ресурсы перед выполнением ("все или ничего"). Если система в состоянии выделить процессу все необходимое, он может работать до завершения. Если хотя бы один из ресурсов занят, процесс будет ждать.

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

Нарушение принципа отсутствия перераспределения (No Preemption)

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

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

Весь вопрос в цене подобного решения, которая может быть слишком высокой, если необходимость отбирать ресурсы возникает часто.

Нарушение условия кругового ожидания

Трудно предложить разумную стратегию, чтобы избежать последнего условия из раздела "Условия возникновения тупиков" – циклического ожидания.

Один из способов – упорядочить ресурсы. Например, можно присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке их возрастания. Тогда круговое ожидание возникнуть не может. После последнего запроса и освобождения всех ресурсов можно разрешить процессу опять осуществить первый запрос. Очевидно, что практически невозможно найти порядок, который удовлетворит всех.

Один из немногих примеров упорядочивания ресурсов – создание иерархии спин-блокировок в Windows 2000. Спин-блокировка – простейший способ синхронизации.

Определение

Спин-блокировка — это состояние в многопоточных программах, при котором поток бесконечно повторяет проверку условия входа в критическую секцию (например, значение флага или состояния блокировки), не передавая управления планировщику, что приводит к полному использованию процессорного времени без реальной полезной работы. Такой подход, хотя и позволяет быстро реагировать на освобождение ресурса, может быть неэффективным, особенно на системах с ограниченным числом ядер, поскольку заблокированный поток продолжает "крутиться" в цикле, потребляя CPU. Спин-блокировки оправданы в случаях очень коротких задержек, когда накладные расходы на переключение контекста превышают затраты на ожидание в цикле.

Спин-блокировка может быть захвачена и освобождена процессом. Классическая тупиковая ситуация возникает, когда процесс P1 захватывает спин-блокировку S1 и претендует на спин-блокировку S2, а процесс P2 захватывает спин-блокировку S2 и хочет дополнительно захватить спин-блокировку S1. Чтобы этого избежать, все спин-блокировки помещаются в упорядоченный список. Захват может осуществляться только в порядке, указанном в списке.

Другой способ атаки условия кругового ожидания – действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один ресурс в каждый момент времени. Если нужен второй ресурс – освободи первый. Очевидно, что для многих процессов это неприемлемо.

Таким образом, технология предотвращения циклического ожидания, как правило, неэффективна и может без необходимости закрывать доступ к ресурсам.

Обнаружение тупиков

Обнаружение взаимоблокировки сводится к фиксации тупиковой ситуации и выявлению вовлеченных в нее процессов. Для этого производится проверка наличия циклического ожидания в случаях, когда выполнены первые три условия возникновения тупика. Методы обнаружения активно используют графы распределения ресурсов.

Рассмотрим модельную ситуацию:

• Процесс P1 ожидает ресурс R1.
• Процесс P2 удерживает ресурс R2 и ожидает ресурс R1.
• Процесс P3 удерживает ресурс R1 и ожидает ресурс R3.
• Процесс P4 ожидает ресурс R2.
• Процесс P5 удерживает ресурс R3 и ожидает ресурс R2.

Вопрос состоит в том, является ли данная ситуация тупиковой, и если да, то какие процессы в ней участвуют. Для ответа на этот вопрос можно сконструировать граф ресурсов. Из рисунка видно, что имеется цикл, моделирующий условие кругового ожидания, и что процессы P2, P3, P5, а может быть, и другие находятся в тупиковой ситуации.

Граф ресурсов - Изображение графа, показывающего цикл: P2 -> R1 -> P3 -> R3 -> P5 -> R2 -> P2

Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере.

Один из таких алгоритмов описан в Таненбаум, 2002, там же можно найти ссылки на другие алгоритмы. Существуют и другие способы обнаружения тупиков, применимые также в ситуациях, когда имеется несколько ресурсов каждого типа. Так в Дейтел, 1987 описан способ, называемый редукцией графа распределения ресурсов, а в Таненбаум, 2002 – матричный алгоритм.

Восстановление после тупиков

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

Сложность восстановления обусловлена рядом факторов:

• В большинстве систем нет достаточно эффективных средств, чтобы приостановить процесс, вывести его из системы и возобновить впоследствии с того места, где он был остановлен.
• Если даже такие средства есть, то их использование требует затрат и внимания оператора.
• Восстановление после тупика может потребовать значительных усилий.

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

По возможности лучше ликвидировать тот процесс, который может быть без ущерба возвращен к началу (такие процессы называются идемпотентными). Примером такого процесса может служить компиляция. С другой стороны, процесс, который изменяет содержимое базы данных, не всегда может быть корректно запущен повторно.

В некоторых случаях можно временно забрать ресурс у текущего владельца и передать его другому процессу. Возможность забрать ресурс у процесса, дать его другому процессу и затем без ущерба вернуть назад сильно зависит от природы ресурса. Подобное восстановление часто затруднительно, если не невозможно.

В ряде систем реализованы средства отката и перезапуска или рестарта с контрольной точки (сохранение состояния системы в какой-то момент времени). Если проектировщики системы знают, что тупик вероятен, они могут периодически организовывать для процессов контрольные точки. Иногда это приходится делать разработчикам прикладных программ.

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

Заключение

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

Проблема тупиков является прямым следствием конкурентного доступа к ограниченным ресурсам. Борьба с ней не имеет универсального решения и сводится к выбору одной из четырех стратегий: игнорирования, предотвращения, обнаружения или восстановления. Каждая из этих стратегий имеет свою цену, выражающуюся в потере производительности, удобства или даже результатов работы процессов. Тем ни менее, проектировщик системы должен выбрать подход, соразмерный серьезности последствий: для одних систем допустимо редкое зависание, в то время как для других (например, систем реального времени) необходимы строгие и дорогостоящие методы гарантии отсутствия тупиков.