Вы читаете эту статью потому что скорее всего хотите понять, как устроен класс QMutex или вам просто интересна тема программирования без блокировок. Нет необходимости читать это, если вы просто хотите использовать QMutex в своем приложение. Я нашел реализацию QMutex интересной и хочу поделиться приобретенными знаниями.
Я хочу продемонстрировать и объяснить упрощенную версию существующего кода. Если же захочется посмотреть на рабочий код, просто загляните в исходники Qt. Эта статья поможет понять основную концепцию.
Для того, что бы лучше усвоить статью, надо знать основы программирования без блокировок. Если вам понятна ABA проблема и вы знаете, как сделать стек без блокировок, то проблем не будет. Если же нет, в качестве вступления можно прочитать мою предыдущую статью [перевод].
Основная мысль статьи взята с финальной части моего выступления на Qt Developer days 2011.
QMutex
Перед тем, как разбираться как что-то работает, необходимо понять, что это что-то делает. Ниже приведен основной интерфейс, который мы будем анализировать.
class QMutex {
public:
void lock();
void unlock();
bool tryLock();
private:
//...
};
Тут нет ничего сверхъестественного. Если же вы не догадываетесь, что делают эти функции, то можно почитать документацию QMutex.
Мотивы
Мы хотим, чтобы QMutex был как можно эффективнее. QMutex в Qt 4.8 уже намного быстрее, потому что он использует атомарные операции. Между Qt 4.8 и Qt 5 скорость мьютексов не изменилась. Но есть изменения со стороны памяти. Хочется, что бы QMutex использовал как можно меньше памяти, что бы можно было добавить побольше QMutex в объекты для более детальной блокировки.
sizeof(QMutex) == sizeof(void*)
Это условие в Qt 4 уже истинно. Но в Qt 4 есть множество скрытых затрат из-за идеологии pimpl, как и в любом классе Qt. Создавая QMutex в Qt 4 выделяется память и инициализируется объект QMutexPrivate, который в свою очередь, инициализирует платформозависимые примитивы. В итоге, у нас есть оверхед в 120 байт на каждый мьютекс и дополнительные инициализации/разрушения. В Qt 5 больше нет скрытых затрат на каждый мьютекс.
Другое улучшение — QMutex теперь простой тип данных (POD). Это плюс, потому что QMutex часто используют для блокировки глобальных ресурсов. И очевидно для этих целей используют глобальный мьютекс. Но, глобальные объекты все же следует избегать, особенно в библиотеках, потому что порядок инициализации не определен, и они замедляют запуск, даже если эта часть библиотеки не используется.
QMutex singletonMutex; // static global object !!! (OK only for POD)
MySingleton *MySingleton::self() {
QMutexLocker locker(&singletonMutex)
if(!m_self)
m_self = new MySingleton;
return m_self;
}
Такой код опасно использовать в Qt 4, потому что другой глобальный объект в другой единице компиляции может воспользоваться синглтоном, а мьютекс к этому моменту еще не создан.
Основные изменения QMutex в Qt 5 по сравнению с Qt 4.8
- QMutex использует намного меньше памяти.
- Создание и разрушение выполняется быстрее.
- Теперь можно использовать в качестве глобального объекта.
- Затраты на блокировкуразблокировку не изменились.
Обзор
class QMutex {
public:
// API ...
private:
QAtomicPointer<QMutexPrivate> d_ptr;
};
d_ptr всего лишь член класса. Хитрость в том, что он не всегда является указателем на существующий QMutexPrivate. Он может принимать особое занчение:
| Значение d_ptr | Смысл |
|---|---|
| 0x0 | Мьютекс разблокирован |
| 0x1 | Мьютекс заблокирован и нету других потоков, которые бы его ждали |
| Другой адрес | Указатель на существующий QMutexPrivate |
Наверное, всем знаком указатель на 0 (или 0x0) (еще встречается как NULL). 0x1 — это специальное значение, которое говорит, что мьютекс заблокирован.
Основная идея блокирования, попытаться атомарно изменить значение d_ptr с 0 на 1. Если операция завершилась успешно, поток забрал мьютекс, в противном случае надо ожидать его освобождения.
bool QMutex::tryLock() {
return d_ptr.testAndSetAcquire(0x0, 0x1);
}
void QMutex::lock() {
while(!d_ptr.testAndSetAcquire(0x0, 0x1)) {
// изменить значение d_ptr на QMutexPrivate и вызвать wait для него.
// … см. ниже
}
}
Функция bool QAtomicPointer::testAndSetAcquire(expected, newValue) изменит значение указателя на newValue только в том случае, если предыдущее значение равно expected и вернет true в случае успеха. Она атомарная: если другие потоки успеют изменить значение, то операция завершится неудачей и вернет false.
Разблокирование
Начнем с кода:
void QMutex::unlock() {
Q_ASSERT(d_ptr); // не может быть 0x0 потому что мьютекс заблокирован
QMutexPrivate *d = d_ptr.fetchAndStoreRelease(0x0);
if (d == 0x1)
return; // нет потоков, ожидающих мьютекс
d->wake(); // разбудить все потоки
d->deref();
}
Функция fetchAndStoreRelease атомарно изменит значение d_ptr на 0x0 и вернет предыдущее значение. Обмен атомарный: мы гарантированно получим предыдущее значение и ни один поток в этот момент не изменит значение d_ptr.
Возвращаемое значение не может быть 0, потому что наш мьютекс находится в заблокированном состоянии (поэтому мы и вызываем разблокирование). Если он был 0x1, то нет потоков, которые бы ждали освобождения мьютекса, а значит делать больше ничего не надо. В противном случае, мы получим указатель на QMutexPrivate, а потоки ждут мьютекс, поэтому мы должны разбудить все эти потоки. И они попытаются завладеть мьютексом снова. Пробуждение всех потоков — пустая трата времени, потому что только один сможет завладеть мьютексом. Настоящий код в Qt будит только один поток.
Можно так же заметить deref(). Она разыменует QMutexPrivate и в случае необходимости, освободит.
Управление памятью
В программировании без блокировок, управление памятью — это всегда отдельная сложная тема. Мы пользуемся техникой подсчета ссылок, что бы быть уверенными, что во время освобождения QMutexPrivate не используется одним из потоков.
Важно заметить, что QMutexPrivate никогда не удаляется. Взгляните на этот код:
d_ptr->ref().
Это не атомарная операция. Хотя сама функция ref() атомарна, есть и другие операции. Сначала считывается значение d_ptr, а адрес помещается в регистр. Но другой поток может освободить мьютекс и освободить QMutexPrivate до того, как ref() будет вызвана. В итоге, мы попытались бы получить доступ к уже освобожденной памяти.
QMutexPrivate никогда не удаляется. Вместо этого, он помещается в пулл для повторного использования (стек без блокировок). Мы считаем, что количество объектов QMutexPrivate мало. QMutexPrivate необходим только в том случае, если есть потоки, которые ждут освобождения мьютекса, соответственно их не может быть больше, чем количество потоков в приложении.
Так выглядит QMutexPrivate
class QMutexPrivate {
QAtomicInt refCount;
public:
bool ref() {
do {
int c = refCount;
if (c == 0) // нет ссылок на QMutexPrivate, а значит
return false; // он уже освобожден.
} while (!refCount.testAndSetAcquire(c, c + 1))
return true;
}
void deref() {
if (!refCount.deref())
release();
}
/* Освобождаем QMutexPrivate помещая его в глобальный стек без блокировок */
void release();
/*Достаем QMutexPrivate из глобального стека без блокировок
(или создаем новый, если стек пуст)
И убеждаемся, что он правильно инициализирован
refCount устанавливаем в 1
*/
static QMutexPrivate *allocate();
/* Блокируем, пока не разбудим.
Если wake уже была вызвана, сразу выходим из функции */
void wait();
/* Будим все ожидающие потоки. Все следующие вызовы wait()
будут возвращаться мгновенно */
void wake();
// ... платформозависимые данные
};
Блокирование
Теперь у нас достаточно информации, что бы взглянуть на реализацию блокирования.
void QMutex::lock() {
// Пытаемся атомарно изменить d_ptr с 0 на 1
while (!d_ptr.testAndSetAcquire(0x0, 0x1)) {
// Если не удалось, мьютекс занят другим
// поэтому надо ждать.
// Делаем локальную копию d_ptr что бы работать с
// указателем, который случайно не изменится за нашей спиной.
QMutexPrivate *copy = d_ptr;
// Очень вероятно, что d_ptr уже изменился в 0, пока мы копировали.
if (!copy) // В этом случае, мьютекс разблокирован,
continue; // поэтому можно попытаться завладеть им снова
if (copy == 0x1) {
// Пока еще нет QMutexPrivate, поэтому надо создать
copy = QMutexPrivate::allocate();
if (!d_ptr.testAndSetOrdered(0x1, copy)) {
// d_ptr уже не 0x1, а занчит мьютекс освободился или же
// дургой поток установил QMutexPrivate.
// в таком случае, освободим уже ненужный QMutexPrivate,
// и попробуем все снова.
copy->deref();
continue;
}
}
// Пробуем увеличить счетчик ссылок QMutexPrivate
if (!copy->ref()) // но если не удалось, значит уже он свободен,
continue; // а значит пробуем вновь.
// Сейчас вероятно QMutexPrivate уже освободился,
// но повторно используется в другом мьютексе.
// А значит, надо проверить что мы действительно храним
// ссылку на правильный мьютекс.
if (d != copy) {
d->deref();
continue;
}
// Здесь мы уже точно знаем, что у нас правильный QMutexPrivate и
// он уже не будет освобожден или изменен за нашей спиной.
// Можно ждать.
copy->wait();
// Мьютекс освобожден, можно освободить QMutexPrivate
copy->deref();
// и попробовать снова им завладеть.
}
}
Я надеюсь, что комментарии понятны.
К рабочему коду
Упрощенный код, приведенный выше, имеет определенные ограничения, которых лишена существующая реализация внутри Qt:
- QMutex может работать в рекурсивном режиме, с тем же API (реализация в Qt 5 поддерживает его, но затраты намного больше, чем у не рекурсивного мьютекса)
- Упрощенный код будит все потоки, ожидающие мьютекс, вместо того что бы будить только один. Это не оптимально, потому что только один поток сможет завладеть мьютексом.
- Несправедливость. В том смысле, что поток, который очень долго ждет мьютекса, может так его и не получить, в то время как два других потока будут постоянно забирать мьютекс.
- Существует QMutex::tryLock(int timeout), который ждет мьютекс определенное количество времени, если он заблокирован.
Этот код так же не используется в Linux. В Linux используются фьютексы, а d_ptr управляет ими.
Если интересно, то можно взглянуть на рабочий код: файлы qmutex.cpp, qmutex.h и qmutex_p.h доступны на Gitorious.
Автор: surik
