Операционные системы

Самостоятельная работа №3

Исследование методов синхронизации процессов и межпроцессных коммуникаций

Общие сведения

Если в ядрах операционных систем для однопроцессорных платформ взаимное исключение процессов может быть реализовано путём запрета прерываний на время исполнения критической секции, то в пользовательском режиме эта возможность недоступна. В системе, реализованной в лабораторной работе № 2, диспетчер сопрограмм срабатывает в обработчике сигналов. POSIX-системы позволяют пользовательскому процессу манипулировать маской блокируемых сигналов. То есть при входе в критическую секцию можно заблокировать сигнал таймера TIMER_SIGNAL, а при выходе — разблокировать. Тогда сопрограмма не будет вытеснена, пока она находится в критической секции (только если она сама явным образом не сделает yield).

Можно заранее подготовить маску, содержащую сигнал TIMER_SIGNAL, например, в процедуре start():

sigset_t block_sch;

void start(void) {
    ...
    sigemptyset(&block_sch);
    sigaddset(&block_sch, TIMER_SIGNAL);
    ...
}

void global_lock(sigset_t *old_sigset) {
    sigprocmask(SIG_BLOCK, &block_sch, old_sigset);
}

void global_unlock(sigset_t *old_sigset) {
    sigprocmask(SIG_SETMASK, old_sigset, NULL);
}

При блокировании сигнала имеет смысл сохранить предыдущую маску, чтобы восстанавливать её при выходе из критической секции:

    sigset_t oldset;
    global_lock(&oldset);
    /* критическая секция */
    global_unlock(&oldset);

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

Второй вариант реализации взаимного исключения — активное ожидание (спин-блокировка). Вводится некоторый флаг занятости ресурса, который проверяется перед тем, как войти в критический участок. Если флаг, который в начале устанавливается в состояние СВОБОДЕН, находится в состоянии СВОБОДЕН, то флаг переводится в состояние ЗАНЯТ, и сопрограмма входит в критический участок. При выходе из критического участка флаг устанавливается в состояние СВОБОДЕН. Если при подходе к критическому участку флаг оказывается в состоянии ЗАНЯТ, то сопрограмма начинает проверять состояние флага в цикле до тех пор пока флаг не будет установлен в состояние СВОБОДЕН другой сопрограммой. Операции установки и проверки флага должны выполняться атомарно. Различные платформы для этой цели предлагают специальные инструкции процессора (TSL — test and set lock, CMPXCHG — compare and exchange и т.п.).

У компилятора GCC есть набор встроенных функций, которые реализуют такие атомарные операции доступа к памяти специфическим для данной платформы способом: Built-in functions for atomic memory access.

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

void lock_spinlock(int *lock) {
    while (__sync_lock_test_and_set(lock, 1));
}

void unlock_spinlock(int *lock) {
    __sync_lock_release(lock);
}

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

volatile int mylock = 0;
    ...
    lock_spinlock(&mylock);
    /* критическая секция */
    unlock_spinlock(&mylock);

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

Кроме того, описанная выше реализация спин-блокировки не допускает вложенности, поскольку не хранит владельца спин-блокировки. То есть если сопрограмма, установившая флаг блокировки, повторно вызовет процедуру lock_spinlock(), она будет заблокирована «навечно».

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

Вариант А: Реализация методов синхронизации процессов с помощью семафоров

Цель работы: познакомиться с методами синхронизации процессов на основе семафоров.

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

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

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

Структурный тип для реализации семафора может быть описан следующим образом:

typedef struct {
    volatile int counter;
    descriptor_t *list;
    ...
} semaphore_t;

Для реализации очереди семафора можно использовать связный список или массив.

Методы работы с семафором будут включать в себя: инициализацию, P-операцию и V-операцию:

void sem_init(semaphore_t *sem, int init);
void sem_p(semaphore_t *sem);
void sem_v(semaphore_t *sem);

При инициализации семафора (sem_init) нужно задать значение счётчику и инициализировать очередь семафора.

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

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

Обратите внимание, что для активизации сопрограммы из очереди семафора недостаточно просто переместить её из очереди семафора в очередь готовых. Необходимо модифицировать процедуру yield(), чтобы переключение контекста шло именно на активизируемую сопрограмму:

void yield_to(descriptor_t *to);

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

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

Семафоры могут быть использованы не только для координации доступа к критическому ресурсу нескольких сопрограмм, но и для установления требуемой очередности прохождения сопрограммами определенных состояний. Пусть, например, необходимо, чтобы сопрограмма Р1 прошла через состояние, отмеченное меткой М_Р1, только после того, как сопрограмма Р2 пройдет через состояние, отмеченное меткой М_Р2. Для синхронизации сопрограмм в этом случае можно использовать семафор, инициализированный значением 0:

semaphore_t sem;
    ...
    sem_init(&sem, 0);
    ...

Если сопрограмма Р1 подойдет к метке М_Р1 раньше, чем сопрограмма Р2 подойдет к метке М_Р2, то она будет заблокирована в очереди семафора. Сопрограмма Р2, пройдя метку M_P2, выполнит операцию V и тем самым активизирует сопрограмму Р1.

Такая очерёдность бывает необходима в задачах «производитель-потребитель». В данном примере сопрограмма P1 — «потребитель», она должна дождаться, пока сопрограмма P2 «производитель» сгенерирует необходимые данные. Если эта очерёдность циклична, то потребуется ещё один семафор, блокирующий «производителя» до того момента, как P1 вычитает сгенерированные ранее данные.

semaphore_t R, W;
    ...
    sem_init(&R, 0);
    sem_init(&W, 0);
    ...

Задание 1: Реализуйте методы работы с семафором (ООП приветствуется, но не обязательно). Напишите демонстрационную программу, иллюстрирующую координацию доступа к критическому ресурсу с помощью реализованного семафора.

Задание 2: Напишите демонстрационную программу, иллюстрирующую синхронизацию прохождения процессов через определенные состояния с помощью реализованного объекта-семафора (à la «производитель-потребитель»).

Вариант B: Реализация методов буферизации сообщений

Цель работы: познакомиться с методом обмена сообщениями между процессами с помощью буфера.

Для информационного обмена между процессами используются механизмы сообщений. Реализация обмена сообщений может быть разной. Если операции чтения и записи сообщений синхронны, то такая стратегия реализации механизма сообщений называется «рандеву» (rendez-vous, точка встречи). Сообщение остаётся в простанстве процесса-отправителя. Процесс-отправитель приостанавливается до момента копирования сообщения процессом-получателем. Процесс-получатель может быть приостановлен, если сообщение ещё не готово, когда он обратился к очереди. Такой алгоритм обеспечивает синхронизацию операций чтения-записи сообщений и эквивалентен описанной выше задаче «производитель-потребитель».

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

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

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

Обычно буфер реализуется как кольцевая FIFO-очередь. Кроме собственно массива сообщений, буфер содержит очереди для синхронизация записи и чтения:

• очереди процессов, ждущих записи, когда буфер полон;
• очереди процессов, ждущих чтения, когда буфер пуст.

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

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

typedef struct {
    char data[MAX_BUF_SIZE];
    int sz;
    int r_pos;
    int w_pos;
    /* поля для хранения очередей процессов: */
    descriptor_t *list_r;
    descriptor_t *list_w;
    ...
} buffer_t;

void buf_init(buffer_t *buf) {
    /* инициализация буфера, его очередей */
    ...
}

void buf_put(buffer_t *buf, char c) {
    /* начало критической секции */
    if (buf->sz+1 == MAX_BUF_SIZE) {
        /* блокировать текущий процесс */
        ...
    }
    buf->sz++;
    buf->data[buf->w_pos] = c;
    buf->w_pos = (buf->w_pos+1) % MAX_BUF_SIZE;
    /* разблокировать один из процессов, ждущих чтения */
    ...
    /* конец критической секции */
}

char buf_get(buffer_t *buf) {
    char res;
    /* начало критической секции */
    if (buf->sz == 0) {
        /* блокировать текущий процесс */
        ...
    }
    buf->sz--;
    res = buf->data[buf->r_pos];
    buf->r_pos = (buf->r_pos+1) % MAX_BUF_SIZE;
    /* разблокировать один из процессов, ждущих записи */
    ...
    /* конец критической секции */
    return res;
}

Вариант C: Реализация очереди сообщений

Цель работы: познакомиться с методом взаимодействия процессов с помощью очередей сообщений.

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

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

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

Как и в случае буфера сообщений, мы имеем дело со сложным объектом, состоящим из очереди сообщений и двух очередей процессов (на отправку сообщения и на получение сообщения). Такой объект сам по себе является критическим ресурсом, требующим синхронизации доступа.

Запись сообщения включает в себя следующие действия:

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

Чтение сообщения включает в себя следующие действия:

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

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

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

Предусмотрите лимит на количество неполученных сообщений и реакцию системы на превышение этого лимита.

typedef struct {
    char* data; // очередь сообщений
    descriptor *list_r; // очередь процессов-получателей
    descriptor *list_w; // очередь процессов-отправителей
    ...
} msgque_t;

void msgque_init(msgque_t *que) {
    /* инициализация очереди сообщений и очередей процессов */
    ...
}

void msgque_put(msgque_t *que, char* str) {
    /* если превышен лимит неполученных сообщений, то ...? */
    /* поместить указатель на сообщение в очередь сообщений */
    /* заблокировать процесс-отправитель и активировать первый процесс-получатель из очереди (если есть) */
}

int msgque_get(msgque_t *que, char* buf, int buflen) {
    /* если очередь сообщений пуста, заблокировать процесс-получатель */
    /* вычислить длину очередного сообщения (она возвращается как результат функции) */
    /* скопировать сообщение в буфер получателя buf размером не более buflen — strncpy */
    /* активизировать соответствующий процесс-отправитель */
}