Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Программирование под Unix/Linux > mutex/condition_variable как работают изнутри?

Автор: boostcoder 31.8.2011, 14:36

всем доброго дня.
подскажите, как мьютекс к примеру, работает изнутри? при локе он устанавливает в шедулере какой-то флаг, при повторном локе которого, шедулер перестает обрабатывать все остальные потоки?
мьютексы/переменные_состояния - объекты ядра?

спасибо.

Добавлено @ 14:37
зы
если бы кто-то сориентировал ссылками на исходники ядра с интересующими моментами, был бы невероятно признателен smile

Автор: newbee 31.8.2011, 14:54

/usr/src/linux/Documentation/mutex-design.txt

Читай в самом конце, там и отсылки к исходникам.

Автор: azesmcar 31.8.2011, 15:31

Цитата(boostcoder @ 31.8.2011, 14:36

)

как мьютекс к примеру, работает изнутри?

Есть разные алгоритмы, не думаю, что ОС обязывается себя использовать какой-то конкретный.
Можешь посмотреть для примера http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D0%B5%D1%82%D0%B5%D1%80%D1%81%D0%BE%D0%BD%D0%B0, http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%BA%D0%BA%D0%B5%D1%80%D0%B0,
Если задаешься такими вопросами, то пора читать http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916.

Автор: boostcoder 31.8.2011, 16:30

Цитата(newbee @ 31.8.2011, 14:54

)

/usr/src/linux/Documentation/mutex-design.txt

вот он: http://git.kernel.org/?p=linux/kernel/git/stable/linux-2.6.38.y.git;a=blob;f=Documentation/mutex-design.txt;h=38c10fd7f4110448facd7089b985c4776d264d85;hb=HEAD.
http://git.kernel.org/?p=linux/kernel/git/stable/linux-2.6.38.y.git;a=blob;f=include/linux/mutex.h;h=94b48bd40dd735f77963fcd31797d32bb68b3379;hb=HEAD.
http://git.kernel.org/?p=linux/kernel/git/stable/linux-2.6.38.y.git;a=blob;f=kernel/mutex.c;h=a5889fb28ecff33eaf5fae64c9d2a50ca03cb2f7;hb=HEAD.
нужно разбираться...

но из декларации "struct mutex;" некоторые моменты понятны.

Код


/*
 * Simple, straightforward mutexes with strict semantics:
 *
 * - only one task can hold the mutex at a time
 * - only the owner can unlock the mutex
 * - multiple unlocks are not permitted
 * - recursive locking is not permitted
 * - a mutex object must be initialized via the API
 * - a mutex object must not be initialized via memset or copying
 * - task may not exit with mutex held
 * - memory areas where held locks reside must not be freed
 * - held mutexes must not be reinitialized
 * - mutexes may not be used in hardware or software interrupt
 *   contexts such as tasklets and timers
 *
 * These semantics are fully enforced when DEBUG_MUTEXES is
 * enabled. Furthermore, besides enforcing the above rules, the mutex
 * debugging code also implements a number of additional features
 * that make lock debugging easier and faster:
 *
 * - uses symbolic names of mutexes, whenever they are printed in debug output
 * - point-of-acquire tracking, symbolic lookup of function names
 * - list of all locks held in the system, printout of them
 * - owner tracking
 * - detects self-recursing locks and prints out all relevant info
 * - detects multi-task circular deadlocks and prints out all affected
 *   locks and tasks (and only those tasks)
 */
struct mutex {
    /* 1: unlocked, 0: locked, negative: locked, possible waiters */
    atomic_t        count;
    spinlock_t        wait_lock;
    struct list_head    wait_list;
#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_SMP)
    struct thread_info    *owner;
#endif
#ifdef CONFIG_DEBUG_MUTEXES
    const char        *name;
    void            *magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
    struct lockdep_map    dep_map;
#endif
};

Добавлено через 4 минуты и 17 секунд

Цитата(azesmcar @ 31.8.2011, 15:31

)

Можешь посмотреть для примера Алгоритм Петерсона, Деккера

по описанию, довольно простые алгоритмы..

Автор: azesmcar 31.8.2011, 18:34

Цитата(boostcoder @ 31.8.2011, 16:30

)

по описанию, довольно простые алгоритмы..

Это для двух потоков.

Автор: null56 5.9.2011, 00:21

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

до самой структуры ты уже добрался (удалю отладочные поля)

Код


  48struct mutex {
  49        /* 1: unlocked, 0: locked, negative: locked, possible waiters */
  50        atomic_t                count;    // ключ занятости
  51        spinlock_t              wait_lock;    
  52        struct list_head        wait_list;    // ожидающие задачи освобождения
  63};

итого всего три поля:
типы atomic_t - платформозависимые, вот код для х86
http://lxr.linux.no/#linux+v3.0.4/arch/x86/include/asm/atomic.h

операции с типами spinlock, в случае однопроцессорной системы и без возможности вытеснения ядра, вообще по идее ничего не должны делать, в противном
случае имеют место платформозависимые ассемблерные вставки для работы с этими типами
вот основные интерфейсы
http://lxr.linux.no/#linux+v3.0.4/include/linux/spinlock.h
для х86 в многопроцессорной системе, попытка завладеть спинлоком, ВРОДЕ БЫ, сводилась к асмовской вставке, где в бесконечном цикле осуществлялась операция проверить-изменить переменную

далее основные методы
создание - ничего интересного, лишь инициализация

Код


  39void
  40__mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)
  41{
  42        atomic_set(&lock->count, 1);
  43        spin_lock_init(&lock->wait_lock);
  44        INIT_LIST_HEAD(&lock->wait_list);
  46
  48}

блокировка

Код


  83void __sched mutex_lock(struct mutex *lock)
  84{
  85        might_sleep();
  86        /*
  87         * The locking fastpath is the 1->0 transition from
  88         * 'unlocked' into 'locked' state.
  89         */
  90        __mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath);
  91        mutex_set_owner(lock);
  92}

тут интерес вызывает __mutex_fast_lock, которая в случае занятости мьютекса (count) дергает другую функцию __mutex_lock_slowpath
http://lxr.linux.no/#linux+v3.0.4/arch/x86/include/asm/mutex_32.h#L24
вот код __mutex_lock_slowpath
http://lxr.linux.no/#linux+v3.0.4/kernel/mutex.c#L401
которая вызывает другую функцию блокировки __mutex_lock_common
http://lxr.linux.no/#linux+v3.0.4/kernel/mutex.c#L133
если убрать из нее различные примочки времени компиляции, то ключевыми тут будут
- запрет вытесняемости
http://lxr.linux.no/#linux+v3.0.4/kernel/mutex.c#L140
- далее добавление в очередь ожидания, повторная попытка завладеть мьютексом, спать если мьютекс по прежнему занят (schedule)
http://lxr.linux.no/#linux+v3.0.4/kernel/mutex.c#L204
- ну и выход из очереди
http://lxr.linux.no/linux+v3.0.4/kernel/mutex.c#L251
напоминаю: переменная current хранит адрес структуры текущего процесса/потока
Итог: если мьютекс заблокирован, то в в список ожидающих задач (поле wait_list) добавляется текущая и управление передается планировщику

освобождение мьютекса
http://lxr.linux.no/#linux+v3.0.4/kernel/mutex.c#L110
опять ключевым является вызов функции fastpath_unlock
http://lxr.linux.no/#linux+v3.0.4/arch/x86/include/asm/mutex_32.h#L73
которая в случае обнаружения ожидающих задач (по значению count) дергает __mutex_unlock_common_slowpath
http://lxr.linux.no/#linux+v3.0.4/kernel/mutex.c#L309
которая пробуждает первый ожидающий в очереди процесс/поток
http://lxr.linux.no/#linux+v3.0.4/kernel/mutex.c#L326

по поводу флагов, если судить по тем исходникам, что я привел, в структуре thread_info поле state принимает значение TASK_UNINTERRUPTIBLE
видимо это что - то значит для планировщика smile

, что именно я не вникал
http://lxr.linux.no/#linux+v3.0.4/include/linux/sched.h#L172

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

Автор: boostcoder 5.9.2011, 00:33

null56, спасибо. понял. все в тему!