Каким свойством в общем случае обладают мьютексы

07.01.2021
0
Главная › Какие свойства › Каким свойством в общем случае обладают мьютексы
Каким свойством в общем случае обладают мьютексы thumbnail

Попытка одновременного удаления двух узлов i и i + 1 приводит к сохранению узла i + 1.

Мью́текс (англ. mutex, от mutual exclusion — «взаимное исключение») — примитив синхронизации, обеспечивающий взаимное исключение исполнения критических участков кода[1]. Классический мьютекс отличается от двоичного семафора наличием эксклюзивного владельца, который и должен его освобождать (т.е. переводить в незаблокированное состояние)[2]. От спинлока мьютекс отличается передачей управления планировщику при невозможности захвата мьютекса[3]. Встречаются также блокировки чтения-записи, именуемые разделяемыми мьютексами и предоставляющие помимо эксклюзивной блокировки общую, позволяющую совместно владеть мьютексом, если нет эксклюзивного владельца[4].

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

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

Проблемы использования[править | править код]

Инверсия приоритетов[править | править код]

Инверсия приоритетов возникает, когда должен исполняться процесс с высоким приоритетом, но он блокируется по мьютексу, которым владеет процесс с низким приоритетом, и должен ожидать, пока процесс с низким приоритетом не разблокирует мьютекс. Классическим примером неограниченной инверсии приоритетов в системах реального времени является захват процессорного времени процессом со средним приоритетом, в результате чего процесс с низким приоритетом не может исполняться и не может разблокировать мьютекс[6].

Типовым решением проблемы является наследование приоритетов, при котором процесс, владеющий мьютексом наследует приоритет другого процесса, заблокированного по нему, если приоритет заблокированного процесса выше, чем у текущего[6].

Прикладное программирование[править | править код]

Мьютексы в Win32 API[править | править код]

Win32 API в Windows имеет две реализации мьютексов — собственно мьютексы, имеющие имена и доступные для использования между разными процессами[7], и критические секции, которые могут использоваться только в пределах одного процесса разными потоками[8]. Для каждого из этих двух типов мьютексов используются свои функции захвата и освобождения[9]. Критическая секция в Windows работает несколько быстрее и является более эффективной по сравнению с мьютексом и семафором, поскольку использует специфичную для процессора инструкцию test-and-set[8].

Мьютексы в POSIX[править | править код]

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

Функции пакета Pthreads для работы с мьютексами

ФункцияОписание
pthread_mutex_init()Создание мьютекса[11].
pthread_mutex_destroy()Уничтожение мьютекса[11].
pthread_mutex_lock()Перевод мьютекса в заблокированное состояние (захват мьютекса)[11].
pthread_mutex_trylock()Попытка перевода мьютекса в заблокированное состояние, и возврат ошибки в случае, если должна произойти блокировка потока из-за того, что у мьютекса уже есть владелец[11].
pthread_mutex_timedlock()Попытка перевода мьютекса в заблокированное состояние, и возврат ошибки в случае, если попытка не удалась до наступления указанного момента времени[12].
pthread_mutex_unlock()Перевод мьютекса в незаблокированное состояние (отпускание мьютекса)[11].

Для решения специализированных задач мьютексам могут задаваться различные атрибуты[11]. Через атрибуты с помощью функции pthread_mutexattr_settype() можно задать тип мьютекса, что повлияет на поведение функций захвата и освобождения мьютекса[13]. Мьютекс может быть одного из трёх типов[13]:

  • PTHREAD_MUTEX_NORMAL — при повтроной попытке захвата мьютекса владеющим потоком происходит взаимоблокировка[14];
  • PTHREAD_MUTEX_RECURSIVE — повторные захваты тем же потоком допустимы, ведётся подсчёт таких захватов[14];
  • PTHREAD_MUTEX_ERRORCHECK — попытка повторного захвата тем же потоком возвращает ошибку[14].

Мьютексы в языке Си[править | править код]

Стандарт С17 языка программирования Си определяет тип mtx_t[15] и набор функций для работы с ним[16], которые должны быть доступны, если макрос __STDC_NO_THREADS__ не был определён компилятором[15]. Семантика и свойства мьютексов в целом совпадают со стандартом POSIX, тип семафора определяется передачей комбинации флагов в функцию mtx_init()[17]:

  • mtx_plain — нет контроля повторного захвата тем же потоком[18];
  • mtx_recursive — повторные захваты тем же потоком допустимы, ведётся счётчик таких захватов[19];
  • mtx_timed — поддерживается захват мьютекса с возвращением ошибки по истечению указанного времени[19].

Возможность использования мьютексов через разделяемую память различными процессами в стандарте C17 не рассматривается.

Мьютексы в языке C++[править | править код]

Стандарт С++17 языка программирования C++ определяет 4 различных класса мьютексов[20]:

  • mutex — мьютекс без контроля повторного захвата тем же потоком[21];
  • recursive_mutex — повторные захваты тем же потоком допустимы, ведётся подсчёт таких захватов[22];
  • timed_mutex — нет контроля повторного захвата тем же потоком, поддерживается захват мьютекса с выбрасыванием исключительной ситуации по истечении указанного времени в случае неудачи[23];
  • recursive_timed_mutex — повторные захваты тем же потоком допустимы, ведётся подсчёт таких захватов, поддерживается захват мьютекса с выбрасыванием исключительной ситуации по истечении указанного времени в случае неудачи[24].

Библиотеки Boost дополнительно обеспечивает именованные и межпроцессные мьютексы, а также разделяемые мьютексы, которые позволяют захватывать мьютекс для совместного владения несколькими потоками только для чтения данных с запретом на эксклюзивную запись на время захвата блокировки, что по сути представляет из себя механизм блокировок чтения и записи[25].

Детали реализации[править | править код]

На уровне операционных систем[править | править код]

В общем случае мьютекс хранит в себе не только своё состояние, но и список заблокированных задач. Изменение состояния мьютекса может быть реализовано с помощью архитектурно-зависимых атомарных операций на уровне пользовательского кода, но по разблокированию мьютекса необходимо также возобновить исполнение других задач, которые были заблокированы по мьютексу. Для этих целей хорошо подходит более низкоуровневый примитив синхронизации — фьютекс, который реализуется на стороне операционной системы и берёт на себя функционал блокировки и разблокировки задач, позволяя в том числе создавать межпроцессовые мьютексы[26]. В частности, с помощью фьютекса мьютекс реализован в пакете Pthreads во многих дистрибутивах Linux[27].

В архитектурах x86 и x86_64[править | править код]

Простота мьютексов позволяет реализовать их в пространстве пользователя с помощью ассемблерной команды XCHG, которая может атомарно копировать значение мьютекса в регистр и одновременно выставлять значение мьютекса в 1 (предварительно записанное в тот же регистр). Нулевое значение мьютекса означает, что он находится в заблокированном состоянии, а единичное — в разблокированном. Значение из регистра может быть протестировано на 0, и в случае нулевого значения управление должно быть возвращено программе, что означает захват мьютекса, если же значение являлось ненулевым, то управление должно быть передано планировщику для возобновления работы другого потока с последующей повторной попыткой захвата мьютекса, что служит аналогом активной блокировки. Разблокировка мьютекса осуществляется сохранением в мьютексе значения 0 с помощью команды XCHG[28].

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

В архитектуре ARM[править | править код]

В архитектуре ARMv7 для синхронизации памяти между процессорами используются так называемые локальный и глобальный эксклюзивные мониторы, представляющие собой автоматы состояний, контролирующие атомарный доступ к ячейкам памяти[30][31]. Атомарное чтение ячейки памяти может осуществляться с помощью инструкции LDREX[32], а атомарная запись — через инструкцию STREX, которая также возвращает флаг успеха операции[33].

Алгоритм захвата мьютекса предполагает чтение его значения с помощью LDREX и проверку прочитанного значения на заблокированное состояние, что соответствует значению 1 переменной мьютекса. В случае, если мьютекс заблокирован, вызывается код ожидания освобождения блокировки. Если же мьютекс был в незаблокированном состоянии, то попытка блокировки может быть осуществлена с помощью инструкции эксклюзивной записи STREXNE. Если запись не удалась из-за того, что значение мьютекса изменилось, то алгоритм захвата повторяется с начала[34]. После захвата мьютекса выполняется инструкция DMB, обеспечивающую гарантию целостности памяти защищаемого мьютексом ресурса[35].

Перед освобождением мьютекса также вызывается инструкция DMB, после чего в переменную мьютекса записывается значение 0 с помощью инструкции STR, что означает перевод в разблокированное состояние. После разблокировки мьютекса должно произойти сигнализирование ожидающим задачам, если таковые есть, о том, что мьютекс был освобождён[34].

См. также[править | править код]

  • Многопоточность
  • Семафор
  • Фьютекс
  • Спин-блокировка

Примечания[править | править код]

  1. ↑ Таненбаум, 2011, 2.3.6. Мьютексы, с. 165.
  2. ↑ Олег Цилюрик. Инструменты программирования в ядре: Часть 73. Параллелизм и синхронизация. Блокировки. Часть 1. — www.ibm.com, 2013. — 13 августа. — Дата обращения: 12.06.2019.
  3. ↑ The Open Group Base Specifications Issue 7, 2018 edition, Rationale for System Interfaces, General Information (англ.).
  4. ↑ C++17, 2017, 33.4.3.4 Shared mutex types, p. 1373.
  5. ↑ Таненбаум, 2011, 2.3.6. Мьютексы, с. 165—166.
  6. ↑ 1 2 Steven Rostedt, Alex Shi. RT-mutex implementation design — The Linux Kernel documentation (англ.). The Linux Kernel documentation. The kernel development community (7 June 2017). Дата обращения: 16 июня 2020.
  7. ↑ Create Mutex. Дата обращения: 20 декабря 2010. Архивировано 14 февраля 2012 года.
  8. ↑ 1 2 Michael Satran, Drew Batchelor. Critical Section Objects (англ.). Documentation. Microsoft (31 May 2018). Дата обращения: 20 декабря 2010. Архивировано 14 февраля 2012 года.
  9. ↑ Michael Satran, Drew batchelor. Synchronization Functions – Win32 apps (англ.). Documentation. Microsoft (31 May 2018). Дата обращения: 18 июня 2020. Архивировано 18 июня 2020 года.
  10. ↑ Таненбаум, 2011, 2.3.6. Мьютексы, Мьютексы в Pthreads, с. 167.
  11. ↑ 1 2 3 4 5 6 7 Таненбаум, 2011, 2.3.6. Мьютексы, Мьютексы в Pthreads, с. 168.
  12. ↑ IEEE, The Open Group. pthread_mutex_timedlock (англ.). pubs.opengroup.org. The Open Group (2018). Дата обращения: 18 июня 2020. Архивировано 18 июня 2020 года.
  13. ↑ 1 2 IEEE, The Open Group. pthread_mutexattr_settype(3) (англ.). The Open Group Base Specifications Issue 7, 2018 edition. The Open Group (2018). Дата обращения: 20 декабря 2010. Архивировано 14 февраля 2012 года.
  14. ↑ 1 2 3 IEEE, The Open Group. pthread_mutex_lock (англ.). The Open Group Base Specifications Issue 7, 2018 edition. The Open Group (2018). Дата обращения: 17 июня 2020. Архивировано 17 июня 2020 года.
  15. ↑ 1 2 C17, 2017, 7.26 Threads <threads.h>, p. 274.
  16. ↑ C17, 2017, 7.26.4 Mutex functions, p. 277—279.
  17. ↑ C17, 2017, 7.26.4.2 The mtx_init function, p. 277—278.
  18. ↑ C17, 2017, 7.26.1 Introduction, p. 274.
  19. ↑ 1 2 C17, 2017, 7.26.1 Introduction, p. 275.
  20. ↑ C++17, 2017, 33.4.3.2 Mutex types, p. 1368.
  21. ↑ C++17, 2017, 33.4.3.2.1 Class mutex, p. 1369—1370.
  22. ↑ C++17, 2017, 33.4.3.2.2 Class recursive_mutex, p. 1370.
  23. ↑ C++17, 2017, 33.4.3.3 Timed mutex types, p. 1370—1371.
  24. ↑ C++17, 2017, 33.4.3.3.2 Class recursive_timed_mutex, p. 1372—1373.
  25. ↑ Synchronization mechanisms (англ.). Boost C++ Libraries 1.73.0. Дата обращения: 18 июня 2020. Архивировано 18 июня 2020 года.
  26. ↑ Ulrich Drepper. Futexes Are Tricky : [арх. 24.06.2020] : [PDF]. — Red Hat, Inc., 2005. — 11 December.
  27. ↑ Karim Yaghmour, Jon Masters, Gilad Ben-Yossef, Philippe Gerum. Building Embedded Linux Systems: Concepts, Techniques, Tricks, and Traps. — “O’Reilly Media, Inc.”, 2008. — С. 400. — 466 с. — ISBN 978-0-596-55505-4.
  28. ↑ Таненбаум, 2011, 2.3.6. Мьютексы, с. 166.
  29. ↑ Таненбаум, 2011, 2.3.6. Мьютексы, с. 166—167.
  30. ↑ ARM, 2009, 1.2.1 LDREX and STREX, p. 4.
  31. ↑ ARM, 2009, 1.2.2 Exclusive monitors, p. 5.
  32. ↑ ARM, 2009, 1.2.1 LDREX and STREX, LDREX, p. 4.
  33. ↑ ARM, 2009, 1.2.1 LDREX and STREX, STREX, p. 4.
  34. ↑ 1 2 ARM, 2009, 1.3.2 Implementing a mutex, p. 12—13.
  35. ↑ ARM, 2009, 1.2.3 Memory barriers, p. 8.

Литература[править | править код]

  • Эндрю С. Таненбаум. Современные операционные системы = Modern Operating Systems. — 3-е издание. — СПб: Питер : Издательский дом «Питер», 2011. — С. 165–170. — 1117 с. — (Классика computer science). — ISBN 9785459007572.
  • ARM. ARM Synchronization Primitives : Development Article : [англ.] : [арх. 20 мая 2020]. — 2009. — August. — 28 p.
  • SC22/WG14 working group. ISO/IEC 9899:2017 : Programming languages — C : Working document : [англ.]. — 2017. — P. 295—297. — 559 p.
  • SC22/WG14 working group. ISO/IEC 14882:2017 : Standard for Programming Language C++ : Working Draft : [англ.] : [арх. 18 июня 2020]. — 2017. — March. — P. 1368—1376. — 1608 p.

Источник

Введение

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

Для блокировки общих данных от одновременного доступа необходимо использовать объекты синхронизации.

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

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

Ниже рассматривается работа с мютексами в Windows и Unix, подобная идея может быть использована при работе с другими объектами синхронизации.

Эта идея является частным случаем методики «Выделение ресурса — есть инициализация (RAII)».

Создание, настройка и удаление мютекса

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

// класс-оболочка, создающий и удаляющий мютекс (Windows)
class CAutoMutex
{
  // дескриптор создаваемого мютекса
  HANDLE m_h_mutex;// запрет копирования
  CAutoMutex(const CAutoMutex&);
  CAutoMutex& operator=(const CAutoMutex&);
  
public:
  CAutoMutex()
  {
    m_h_mutex = CreateMutex(NULL, FALSE, NULL);
    assert(m_h_mutex);
  }
  
  ~CAutoMutex() { CloseHandle(m_h_mutex); }
  
  HANDLE get() { return m_h_mutex; }
};

* This source code was highlighted with Source Code Highlighter.

В Windows мютексы по умолчанию рекурсивные, а в Unix — нет. Если мютекс не является рекурсивным, то попытка захватить его два раза в одном потоке приведет к deadlock-у.
Чтобы в Unix создать рекурсивный мютекс, необходимо установить соответствующий флаг при инициализации. Соответствующий класс CAutoMutex выглядел бы так (проверки возвращаемых значений не показаны для компактности):

// класс-оболочка, создающий и удаляющий рекурсивный мютекс (Unix)
class CAutoMutex
{
  pthread_mutex_t m_mutex;

  CAutoMutex(

const CAutoMutex&);
  CAutoMutex& operator=(const CAutoMutex&);public:
  CAutoMutex()
  {
    pthread_mutexattr_t attr;
    pthread_mutexattr_init(&attr);
    pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
    pthread_mutex_init(&m_mutex, &attr);
    pthread_mutexattr_destroy(&attr);
  }
  ~CAutoMutex()
  {
    pthread_mutex_destroy(&m_mutex);
  }
  pthread_mutex_t& get()
  {
    return m_mutex;
  }
};* This source code was highlighted with Source Code Highlighter.

Захват и освобождение мютекса

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

// класс-оболочка, занимающий и освобождающий мютекс
class CMutexLock
{
  HANDLE m_mutex;// запрещаем копирование
  CMutexLock(const CMutexLock&);
  CMutexLock& operator=(const CMutexLock&);
public:
  // занимаем мютекс при конструировании объекта
  CMutexLock(HANDLE mutex): m_mutex(mutex)
  {
    const DWORD res = WaitForSingleObject(m_mutex, INFINITE);
    assert(res == WAIT_OBJECT_0);
  }
  // освобождаем мютекс при удалении объекта
  ~CMutexLock()
  {
    const BOOL res = ReleaseMutex(m_mutex);
    assert(res);
  }
};

* This source code was highlighted with Source Code Highlighter.

Для еще большего удобства объявим следующий макрос:

// макрос, занимающий мютекс до конца области действия
#define SCOPE_LOCK_MUTEX(hMutex) CMutexLock _tmp_mtx_capt(hMutex);

* This source code was highlighted with Source Code Highlighter.

Макрос позволяет не держать в голове имя класса CMutexLock и его пространство имен, а также не ломать голову каждый раз над названием создаваемого (например _tmp_mtx_capt) объекта.

Примеры использования

Рассмотрим примеры использования.

Для упрощения примера объявим мютекс и общие данные в глобальной области:

// автоматически создаваемый и удаляемый мютекс
static CAutoMutex g_mutex;// общие данные
static DWORD g_common_cnt = 0;
static DWORD g_common_cnt_ex = 0;

* This source code was highlighted with Source Code Highlighter.

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

void do_sth_1( ) throw()
{
  // …
  // мютекс не занят
  // …

  {
    

// занимаем мютекс
    SCOPE_LOCK_MUTEX(g_mutex.get());// изменяем общие данные
    g_common_cnt_ex = 0;
    g_common_cnt = 0;
    
    // здесь мютекс освобождается
  }
  
  // …
  // мютекс не занят
  // …
}

* This source code was highlighted with Source Code Highlighter.

Не правда ли, что функция do_sth_1() выглядит элегантнее, чем следующая? do_sth_1_eq:

void do_sth_1_eq( ) throw()
{
  // занимаем мютекс
  if (WaitForSingleObject(g_mutex.get(), INFINITE) == WAIT_OBJECT_0)
  {
    // изменяем общие данные
    g_common_cnt_ex = 0;
    g_common_cnt = 0;// надо не забыть освободить мютекс
    ReleaseMutex(g_mutex.get());
  }
  else
  {
    assert(0);
  }
}* This source code was highlighted with Source Code Highlighter.

В следующем примере точек выхода из функции три, но упоминание о мютексе только одно (объявление области блокировки мютекса):

// какое-то исключение
struct Ex {};// фунцкция, использующая общие данные
int do_sth_2( const int data ) throw (Ex)
{
  // …
  // мютекс не занят
  // …
  
  // занимаем мютекс на критическом участке
  SCOPE_LOCK_MUTEX(g_mutex.get());
  
  int rem = data % 3;
  
  if (rem == 1)
  {
    g_common_cnt_ex++;
    // мютекс автоматически освободится при выбросе исключения
    throw Ex();
  }
  else if (rem == 2)
  {
    // мютекс автоматически освободится при возврате
    g_common_cnt++;
    return 1;
  }
  
  // здесь мютекс автоматически освободится при возврате
  return 0;
}

* This source code was highlighted with Source Code Highlighter.

Примечание: я не сторонник использовать несколько return-ов в одной функции, просто пример от этого
становится чуть показательнее.
А если бы функция была длиннее и точек выброса исключений было бы с десяток? Без макроса нужно было поставить перед каждой из них ReleaseMutex(…), а ошибиться здесь можно очень легко.

Заключение

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

UPD: Первый класс CAutoMutex по ошибке не был написан, вместо него было повторное объявление второго класса CMutexLock. Исправлено.

UPD2: Убраны слова inline в объявлении методов внутри классов за ненадобностью.

UPD3: Был добавлен вариант класса CAutoMutex с рекурсивным мютексом для Unix.

UPD4: Перенесено в блог «C++»

Источник

Предыдущая статья
С какими продуктами лучше усваивается йод
Следующая статья
Какие продукты не рекомендуется беременным
© А какой продукт?