WikiSort.ru - Не сортированное

Изменение элемента в списке

Рассмотрим для примера, как произвести изменение элемента в односвязный список с применением данного механизма синхронизации.

Роль глобального указателя будет выполнять в данном случае указатель на первый элемент. Писателю придётся создать копию всего списка, обновить интересующий его элемент, а затем атомарно обновить глобальный указатель так, чтобы он указывал на первый элемент нового списка. Все читатели, обратившиеся к списку до его обновления, продолжат работать со старой копией, которая останется неизменной. Новые читатели получат доступ уже к новой копии.

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

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

Освобождение памяти

После создания нового элемента и обновления указателя старая копия элемента всё ещё остаётся в памяти, и её нельзя удалить, пока все читатели, имеющие к ней доступ, не разблокируют её. Для этого можно воспользоваться блокирующими механизмами синхронизации. Альтернативным вариантом является учёт того факта, что чтение является критической секцией. Тогда поток-писатель системным вызовом планирует себя поочерёдно после каждого из потоков-читателей. В этом случае все читатели гарантировано пройдут через переключение контекста и значит завершат использование ссылки на устаревшую версию структуры данных.

Чтение в критической области

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