В приведенных выше прототипах tree является структурой, которая указывает на корень дерева (вам нужно будет определить ее должным образом). Каждый элемент дерева содержит пару «ключ-значение». Кроме того, структура каждого элемента должна предусматривать мьютекс, который защищает этот элемент, позволяя использовать его только одному потоку в заданный момент времени. Реализация функций initialize(), add() и lookup() не должна вызвать затруднений. Операция delete() потребует немного больше усилий.

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

31. Потоки выполнения: потоковая безопасность и локальное хранилище

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

31.1. Потоковая безопасность (и новый взгляд на реентерабельность)

Функция считается потокобезопасной, если она может быть безопасно вызвана сразу из двух потоков. К этому можно подойти и с обратной стороны: если функция не является потокобезопасной, мы не можем вызывать ее из одного потока, пока она выполняется в другом. Следующую функцию (похожую на код из листинга 30.1), к примеру, нельзя назвать потокобезопасной:

static int glob = 0;

static void

incr(int loops)

{

int loc, j;

for (j = 0; j < loops; j++) {

loc = glob;

loc++;

glob = loc;

}

}

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

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

Более сложным решением является связывание мьютекса с разделяемой переменной. После этого нужно определить, какие участки функции являются критическими (в которых происходит доступ к разделяемой переменной), и затем закрывать/открывать мьютекс только при их выполнении. Это позволяет нескольким потокам одновременно выполнять одну и ту же функцию, действуя параллельно, за исключением тех моментов, когда разные потоки пытаются выполнить критический участок.

Функции, небезопасные для параллельного выполнения

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

Помимо исключений, представленных в табл. 31.1, стандарт SUSv3 имеет следующие уточнения.

• Функции ctermid() и tmpnam() могут не быть потокобезопасными, если им передается значение NULL.

• Функции wcrtomb() и wcsrtombs() могут не быть потокобезопасными, если их последний аргумент (ps) равен NULL.

Стандарт SUSv4 вносит такие изменения в табл. 31.1.

• Удалены функции ecvt(), fcvt(), gcvt(), gethostbyname() и gethostbyaddr(), поскольку они не попали в эту версию стандарта.

• Добавлены функции strsignal() и system(). Последняя не является реентерабельной, поскольку изменения действий сигналов, которые она должна выполнять, влияют на весь процесс в целом.

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

Таблица 31.1. Функции, которые могут не быть потокобезопасными согласно стандарту SUSv3

asctime()

fcvt()

getpwnam()

nl_langinfo()

basename()

ftw()

getpwuid()

ptsname()

catgets()

gcvt()

getservbyname()

putc_unlocked()

crypt()

getc_unlocked()

getservbyport()

putchar_unlocked()

ctime()

getchar_unlocked()

getservent()

putenv()

dbm_clearerr()

getdate()

getutxent()

pututxline()

dbm_close()