Мониторы в C с помощью семафоров

посмотри в PintOS http://www.stanford.edu/class/cs140/projects/pintos/pintos.tar.gz в src/threads/synch.c

Если C + POSIX, то что-то вроде такого:

#include <stdlib.h>
#include <pthread.h>

/* Monitor is an ADT with associated lock & condition variable. */
#define MONITOR(NAME, FIELDS)                           \
    struct NAME {                                       \
        pthread_mutex_t lock;                           \
        pthread_cond_t cond;                            \
        struct FIELDS fields;                           \
    };

#define MONITOR_INIT(NAME, VAR)                                      \
    struct NAME *(VAR) = malloc(sizeof(struct NAME));                \
    pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;                \
    pthread_cond_t cond = PTHREAD_COND_INITIALIZER;                  \
    (VAR)->lock = lock;                                              \
    (VAR)->cond = cond;

#define WITH_MONITOR_LOCK(VAR, BLOCK)           \
    pthread_mutex_lock(&(VAR)->lock);           \
    BLOCK                                       \
    pthread_mutex_unlock(&(VAR)->lock);

#define MONITOR_WAIT(VAR)                               \
    pthread_cond_wait(&(VAR)->cond, &(VAR)->lock);

#define MONITOR_WAKE(VAR)                       \
    pthread_cond_signal(&(VAR)->cond);

и потом:

MONITOR (
    account,
    {
        unsigned balance;
    }
)

struct account *account_create(unsigned balance)
{
    MONITOR_INIT(account, acc);
    acc->fields.balance = balance;
    return acc;
}

void account_withdraw(struct account *acc, unsigned amount)
{
    WITH_MONITOR_LOCK (
        acc,
        {
            while (amount > acc->fields.balance)
                MONITOR_WAIT(acc);
            
            acc->fields.balance -= amount;
        }
    )
}

void account_deposit(struct account *acc, unsigned amount)
{
    WITH_MONITOR_LOCK (
        acc,
        {
            acc->fields.balance += amount;
            MONITOR_WAKE(acc);
        }
    )
}

Т.е. добавление к структуре содержащей конкурентные данные блокировки (pthread_mutex_t) и condition variable (pthread_cond_t) вместе с правильным их использованием в методах изменяющих поля структуры реализует паттерн «монитор» в си. Подобный пример есть тут - http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html и в Qt-шной документации - http://doc.qt.nokia.com/qq/qq21-monitors.html

о спасибо, друзья! буду разбираться.

Ты только не пиши так, как quasimoto. За это могут и руки оторвать.

За это могут и руки оторвать.

Зато unlock не потеряешь.

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

if (condition)
	WITH_MONITOR_LOCK({code})

WITH_MONITOR_LOCK({code})

Не компилируется же:

error: macro "WITH_MONITOR_LOCK" requires 2 arguments, but only 1 given

ну и, видимо, там я плохие макросы написал - без фигурных скобочек внутри MONITOR_INIT и WITH_MONITOR_LOCK.

Понятно, что макросы с аргументами являющимися чем-то более сложным чем имена и простые выражения нужно использовать в ограниченном количестве (а то придётся запоминать особенности поведения каждого макроса), но тут имитацию shared/atomicly:

struct foo {
    shared some_type a;
};

struct bar {
    some_type a;
};

void f1(struct foo *x)
{
    // read from x->a is ok
    // write to x->a is wrong

    atomicly (x->a) {
        // write to x->a is ok
    }
}

void f2(shared struct bar *x);

void f3(struct bar *x)
{
    shared struct bar y;

    // wrong:
    f2(x);
    f3(y);

    // ok:
    f2(y);
    f3(x);

    // read from x and y is ok
    // write to x is ok
    // write to y is wrong

    // wrong:
    atomicly (x) { ... }

    // ok:
    atomicly (y) {
        // write to y is ok
    }
}

если t - тип, то shared t - тип, t != shared t, мутабельные операции с переменной типа shared t возможны только внутри блока atomicly. Пока STM нет в стандарте (хотя до трежов уже добрались) - приходится мимикрировать.

s/atomicly/atomically/g

приходится мимикрировать

Пиши лучше на чем-нибудь другом, только не на Си.

Пиши лучше на чем-нибудь другом, только не на Си.

А как бы ты написал? Просто каждый раз struct с полями pthread_mutex_t и pthread_cond_t, обычный код в функциях - pthread_mutex_lock; ...; pthread_mutex_unlock?

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

А как бы ты написал?

Я бы написал _функции_ {enter,exit}_monitor (насколько я помню семантику монитора, там нет операции wait, но если есть - это тоже функция).

А конструкцию «atomically» я бы даже не стал пытаться написать. Си язык довольно низкого уровня с убогими средствами расширения (на твои макросы смотреть нельзя без слез).

почему нельзя закрыть эту машинерию макросами, мониторы или shared/atomically

Можно. Но 1) ты явно не имеешь в этом опыта 2) даже с опытом получится всё равно убого (см. ядро), потому что препроцессор примитивен.

насколько я помню семантику монитора, там нет операции wait, но если есть - это тоже функция

Есть такие слайды - «Using Synchronization Primitives in C, C++, and Linux Kernel», там утверждается, что в user-space эмуляция мониторов сводится к использованию pthread_mutex_lock / pthread_mutex_unlock и pthread_cond_wait / pthread_cond_signal, pthread_cond_broadcast. В этом случае будет такая структура:

struct monitor {
    pthread_mutex_t lock;
    pthread_cond_t cond;
};

и набор функций-обвёрток над pthread_mutex_* и pthread_cond_*.

ты явно не имеешь в этом опыта

Т.е. никто принципиально не делает как-то так:

#define WITH_FOO(FOO, BLOCK)                    \
    {                                           \
        hold_foo(FOO);                          \
        BLOCK;                                  \
        release_foo(FOO);                       \
    }

WITH_FOO(foo, { ...; ...; ...; });

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

ну если так хочется макросов пописать, то хоть сделай их более-менее красивыми… типа:

#include <stdio.h>

#define atomically(x)   for (int tmp = lock(#x); tmp > -1; unlock(#x), tmp = -1)

int lock(const char *m) {
    return printf("mutex '%s' locked\n", m);
}

int unlock(const char *m) {
    return printf("mutex '%s' unlocked\n", m);
}

int main() {
    atomically (x)
        puts("x");

    atomically (y) {
        puts("y");
    }
}

правда, это годится только для С99+ или С++. (цикл, кстати, развернется уже при -О1.)

зы: это сферический пример в вакууме, не вздумайте копипастить as is :)

набор функций-обвёрток над pthread_mutex_* и pthread_cond_*.

Вот именно - набор функций-оберток. А ты зачем-то наделал макросов.

ты явно не имеешь в этом опыта

Т.е. никто принципиально не делает как-то так:

Я стараюсь этого не делать. Но, если уж делаю, то автоматически ставлю do {} while (0) и даже struct monitor *mon = (FOO);

WITH_FOO(FOO, BLOCK)

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

Я понимаю, что ты пытаешься сделать. Но ты пытаешься это делаешь в стиле Лиспа (или Питона, ха-ха). В Си это делается (если делается, что редко) pthread_cleanup_push(3) (там { в макросе).

Ещё раз то же самое:

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <pthread.h>

#define handle_error(en, msg)                            \
    do { errno = en; perror(msg); exit(EXIT_FAILURE); } while (0)

struct monitor {
    pthread_mutex_t lock;
    pthread_cond_t cond;
};

void monitor_init(struct monitor *m)
{
    pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
    pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

    m->lock = lock;
    m->cond = cond;
}

void monitor_lock(struct monitor *m)
{
    int s = pthread_mutex_lock(&m->lock);
    if (s != 0)
        handle_error(s, "pthread_mutex_lock");
}

void monitor_unlock(struct monitor *m)
{
    int s = pthread_mutex_unlock(&m->lock);
    if (s != 0)
        handle_error(s, "pthread_mutex_unlock");
}

void monitor_sleep(struct monitor *m)
{
    int s = pthread_cond_wait(&m->cond, &m->lock);
    if(s != 0)
        handle_error(s, "pthread_cond_wait");
}

void monitor_wake(struct monitor *m)
{
    int s = pthread_cond_signal(&m->cond);
    if(s != 0)
        handle_error(s, "pthread_cond_signal");
}

#define with_monitor_lock(m)                                            \
    for (int _i_ = (monitor_lock(m), 0); _i_ != 1; monitor_unlock(m), _i_ = 1)

/* Example. */

struct account {
    struct monitor monitor;
    unsigned balance;
};

void account_withdraw(struct account *acc, unsigned amount)
{
    with_monitor_lock (&acc->monitor) {
        while (amount > acc->balance)
            monitor_sleep(&acc->monitor);
        acc->balance -= amount;
    }
}

void account_deposit(struct account *acc, unsigned amount)
{
    with_monitor_lock (&acc->monitor) {
        acc->balance += amount;
        monitor_wake(&acc->monitor);
    }
}

// struct account acc;
// monitor_init(&acc.monitor);

> Ещё раз то же самое

извини, но вынужден согласится с tailgunner: «Пиши лучше на чем-нибудь другом, только не на Си.»

> handle_error(en, msg)
> errno = en; perror(msg);

> int s = pthread_mutex_lock(&m->lock);
> if (s != 0) handle_error(s, «pthread_mutex_lock»);

в линуксе большинство стандартных функций — врапперы над сисколами. эти системные вызовы возвращают результат типа [unsigned] long. последние, емнип, 4095 или 4096 значений для unsigned long (~0ul-409x...~0ul) (или -1…-409х для long, что одно и то же) считаются ошибкой. в этом случае врапперы присваивают положительное значение ошибки локальной для потока переменной errno и возвращают -1(!!!), иначе возвращают результат сискола (обычно 0). и не смотря на то, что pthread_* — не совсем чтоб врапперы системных вызовов, но и они работают по общим правилам (код ошибки пишут в errno и возвращают -1).

короче, я даже не представляю, что напечатает perror() при errno = -1, т.к. errno обычно может принимать только значения 0…409х %)

Это уже ближе к тому, что написал бы я (хотя handle_error должна быть функцией, и, конечно, с errno ты обращаешься неправильно). Ты учишься писать на Си?

С for прикольный трюк.

Насчёт handle_error - было утянуто из linux man-pages (man pthread_create, man pthread_cleanup_push и т.д.), там так:

#define handle_error_en(en, msg) \
    do { errno = en; perror(msg); exit(EXIT_FAILURE); } while (0)

// ...

    int s;

    s = pthread_create(&thr, NULL, thread_start, NULL);
    if (s != 0)
        handle_error_en(s, "pthread_create");

я даже не представляю, что напечатает perror() при errno = -1, т.к. errno обычно может принимать только значения 0…409х %)

Ну в стандарте написано, что errno имеет тип int, функции возвращающие номер ошибки (pthread_create, например) тоже возвращают int. Как-то не осознал проблему.

Ты учишься писать на Си?

Мне казалось, что я могу писать на си (и пишу), но раз такие траблы, то наверно не очень сносно :)

Макросов поменьше надо.

> было утянуто из linux man-pages

о_О действительно, прошу прощения. даже внимания не обращал, т.к. привык, что стандартные функции в случае ошибки возвращают -1 (или другое спец.значение, типа NULL) и записывают код ошибки в errno, а не сразу возвращают код ошибки, как сисколы…

Макросов поменьше надо.

А как обычно поступают, когда нужно, например, обойти дерево, выполняя на каждом узле некий код? Код обхода может быть длинным (десятки строк), скоп выполнения тоже может быть большим (с десяток переменных). Делать generic функцию обхода довольно неудобно (передавать указатель на функцию принимающую узел и void*, передавать void* в качестве указателя на скоп и применять функцию к узлу и скопу, плюс каждый раз готовить эти неудобные функции и скоп). В gcc можно сделать nested функцию, тем самым избавиться от передачи скопа через стек, но при этом код обхода будет дублироваться каждый раз. Ещё вариант - завернуть код обхода в макрос и передавать этому макросу аргументом блок (вида { ... }) который будет выполняться на узлах (правда, у макроса будут магические переменные и, видимо, всё равно нужна nested функция). Такое применение макросов допустимо?

А как обычно поступают, когда нужно, например, обойти дерево, выполняя на каждом узле некий код?

Обычно делают int (*)(void *node) или, как вариант, int (*)(void *ctx, void *node).

Код обхода может быть длинным (десятки строк), скоп выполнения тоже может быть большим (с десяток переменных)

Ты пытаешься писать на Си в стиле Лиспа или Хаскеля, это в лучшем случае выльется в уродливый код.

Такое применение макросов допустимо?

Есть неписаное правило: нет правил, которые нельзя нарушить, но для нарушения некоторых правил нужны очень веские причины. Так вот, MONITOR_INIT - это нарушение без всяких причин, WITH_MONITOR_LOCK - нарушение, которое того не стоило, with_monitor_lock - возможно, приемлимое нарушение.

как вариант, int (*)(void *ctx, void *node).

Тоже склоняюсь к такому варианту.

Ты пытаешься писать на Си в стиле Лиспа или Хаскеля, это в лучшем случае выльется в уродливый код.

Да, уже не первый раз натыкаюсь - вот был такой код http://www.linux.org.ru/forum/desktop/7252303?cid=7256063 (комментарий), т.е. код обхода использует скоп. Насколько я понимаю, чтобы провести декомпозицию, нужно сделать примерно так:

struct window {
    Display *display;
    Window window;
};

typedef void(window_setter)(struct window*, void*);

struct scope {
    pid_t pid;
    char *name;
    char *class;
    Atom atom; // initialized by XInternAtom
    // ...
};

void setter_wm_class_by_pid(struct window *w, void *scope);
// struct scope *scp = scope;

void traverse_windows(struct window *w, window_setter setter, void* scope);
// setter(w, scope);

void set_wm_class_by_pid(pid_t pid, char *name, char *class);
// open display
// build window
// build scope
// traverse_windows(win, &setter_wm_class_by_pid, scp)

т.е. уже не int (*)(void *ctx, void *node) а void(*)(void *ctx, void *node, setter_fun fun). setter_wm_class_by_pid ещё разбивается на pid_matcher и set_wm_class - только все функции требуют как минимум передачи структур window и scope.

стоит ли инлайнить его функции?

уже не int (*)(void *ctx, void *node) а void(*)(void *ctx, void *node, setter_fun fun)

fun можно включить в контекст. Вообще, всё что в Лиспе/Питоне/Хаскеле было бы локальными переменными, выносится в ctx, курсор становится node.

setter_wm_class_by_pid ещё разбивается на pid_matcher и set_wm_class

В примере по ссылке они не выделены в отдельные функции.

стоит ли инлайнить его функции?

Есть мнение, что инлайнинг на современных процессорах сильно переоценен :) Нужно или нет - другой вопрос, относящийся к API и ABI.

В примере по ссылке они не выделены в отдельные функции.

Да, там всё в одной main (аргументы через стек не таскаются, только в чужие функции), чисто процедурная схема такая:

set_wm_class(display, window, name, class)
  ^
  |
pid_matcher(display, window, name, class, atom, pid)
  ^
  |
[R]traverse_windows(display, window, name, class, atom, pid)
  ^
  |
set_wm_class_by_pid(name, class, pid)

после объединения node = display x window и ctx = name x class x atom x pid и абстрагирования traverse_windows и pid_matcher от кода (первая может делать всё что угодно при обходе, вторая делать всё что угодно при совпадении _NET_WM_PID) получается

set_wm_class(node, ctx)

node_setter(node, ctx)
  ^
  |
[G]pid_matcher(node, ctx, [F]node_setter)
  ^
  |
[G][R]traverse_windows(node, ctx, [F]node_setter)
  ^
  | node_setter = set_wm_class
  |
set_wm_class_by_pid(name, class, pid)

вроде понятней стало.

Собственно, display тоже можно в ctx отправить, тогда нужна только одна дополнительная структура.

fun можно включить в контекст.

Не включается, если traverse_windows / pid_matcher обощённые.

Не включается, если traverse_windows / pid_matcher обощённые.

Они у тебя меняются в процессе обхода дерева? Если нет, их тоже в ctx.

Под «обобщённой» функцией я имею ввиду, например, такую:

typedef void(setter)(Display*, Window, void*);

void traverse(Display *d, Window w, setter set, void* ctx)
{
    unsigned n, i;
    Window root, parent, *childs;

    set(d, w, ctx);

    if (0 != XQueryTree(d, w, &root, &parent, &childs, &n)) {
        for (i = 0; i < n; i++) {
            traverse(d, childs[i], set, ctx);
        }
        XFree(childs);
    }
}

т.е. traverse может обходить дочерние окна не зная ничего о set и ctx, он просто не может сделать ctx->set, потому что у него нет такой struct foo* к которой можно привести void *ctx.

Это может сделать только функция на которую указывает set:

void set_wm_class(Display *d, Window w, void* ctx)
{
    struct wm_class_ctx *x = ctx;
    // x->name
    // x->class
}

    // ...
    struct wm_class_ctx ctx = { ... };
    traverse(d, w, &set_wm_class, &ctx);
    // ...

Предполагается, что при обходе можно делать другие операции (не только set_wm_class), опирающееся на другие контексты (не только wm_class_ctx = name x class).

typedef void(setter)(Display*, Window, void*);

В Си уже можно сделать тип «функция», или ты не компилировал код?

void traverse(Display *d, Window w, setter set, void* ctx)
{
    unsigned n, i;
    Window root, parent, *childs;

    set(d, w, ctx);

    if (0 != XQueryTree(d, w, &root, &parent, &childs, &n)) {
        for (i = 0; i < n; i++) {
            traverse(d, childs[i], set, ctx);
            set(d, w, ctx); // внутри разбирается, следует ли ему что-то делать
        }
        XFree(childs);
    }
}

В Си уже можно сделать тип «функция», или ты не компилировал код?

-Wall -W -pedantic -std=c89 не жалуется.

А зачем переносить set в цикл? Нужно же для каждого w выполнить set, т.е. если в самом начале функции поместить - гарантированно будет для каждого (и левые childs туда не попадают).

не жалуется

clang и gcc. Там вроде должно быть typedef ...(*...)(...); но возможно можно опускать * при объявлении и & при адресации.