И оно, конечно же, существует. Показанное выше решение — это простая и наивная реализация указателей опасности, которую я привел, только чтобы объяснить идею. Первое, что можно сделать, — пожертвовать памятью ради быстродействия. Вместо того чтобы проверять каждый узел в списке освобождения при каждом обращении к pop(), мы вообще не будем пытаться освобождать узлы, пока их число в списке не превысит max_hazard_pointers. Тогда мы гарантированно сможем освободить хотя бы один узел. Но если просто ждать, пока в списке накопится max_hazard_pointers+1 узлов, то выиграем мы немного. После того как число узлов достигает max_hazard_pointers, мы будем пытаться освобождать их почти при каждом вызове pop(), так что проблема лишь немного отодвинулась во времени. Но если дождаться, пока в списке наберётся 2*max_hazard_pointers узлов, то мы гарантированно сможем освободить по крайней мере max_hazard_pointers узлов, и тогда следующую попытку нужно будет делать не раньше, чем через max_hazard_pointers обращений к pop(). Это уже гораздо лучше. Вместо того чтобы просматривать max_hazard_pointers узлов при каждом вызове pop() (и, возможно, ничего не освободить), мы проверяем 2*max_hazard_pointers через каждые max_hazard_pointers вызовов pop() и освобождаем не менее max_hazard_pointers. Получается, что в среднем мы проверяем два узла при каждом вызове pop(), и один из них точно освобождается.
Но и у этого решения есть недостаток (помимо увеличенного расхода памяти): теперь мы должны подсчитывать узлы в списке освобождения, то есть использовать атомарный счетчик, а, кроме того, за доступ к самому списку конкурируют несколько потоков. Если память позволяет, то можно предложить еще более эффективную схему освобождения: каждый поток хранит собственный список освобождения в поточно-локальной памяти. Тогда ни для счетчика, ни для доступа к списку не понадобятся атомарные переменные. Но в обмен придется выделить память для max_hazard_pointers * max_hazard_pointers узлов. Если поток завершается прежде, чем освобождены все его узлы, то оставшиеся можно перенести в глобальный список, как и раньше, а затем добавить в локальный список следующего потока, пожелавшего выполнить процедуру освобождения.
Еще один недостаток указателей опасности состоит в том, что они защищены патент пой заявкой, поданной IBM[13]. Если вы пишете программное обеспечение, которое будет применяться в стране, где эти патенты признаются, то придется получить соответствующую лицензию. Это проблема, общая для многих методов освобождения памяти без блокировок; поскольку в этой области ведутся активные исследования, крупные компании берут патенты всюду, где могут. Возможно, вы задаетесь вопросом, зачем я посвятил так много страниц описанию техники, которой многие не смогут воспользоваться. Что ж, вопрос не праздный. Во-первых, в некоторых случаях ей можно воспользоваться, не платя лицензионных отчислений. Например, если вы разрабатываете бесплатную программу на условиях лицензии GPL[14], то она может подпадать под заявление IBM об отказе от патентных притязаний[15]. Во-вторых — и это более существенно — объяснение техники помогает высветить вещи, о которых надо помнить при написании кода, свободного от блокировок, например, о плате за атомарные операции.
А существуют ли непатентованные методы освобождения памяти, применимые в программах без блокировок? К счастью, да. Один из них — подсчет ссылок.
В разделе 7.2.2 мы видели, что проблема удаления узлов сводится к задаче нахождения узлов, к которым еще обращаются потоки-читатели. Если бы можно было точно узнать, на какие узлы есть ссылки и когда количество ссылок обращается в нуль, то узлы можно было бы удалить. Указатели опасности решают эту проблему путем хранения списка используемых узлов, а механизм подсчета ссылок — путем хранения числа потоков, обращающихся к каждому узлу.
