Есть два типа объектов: A и B.
Объекты A выступают в качестве weak pointer. Объект типа A может указывать на объект типа B, а может никуда не указывать (NULL).
Объекты типа B хранят своё название (строка) и произвольные данные и имеют два состояния: не готов или готов. Если объект в состоянии готов, данные можно читать. Если объект в состоянии не готов, данные еще не вычислены.
Каждый объект типа B также хранит список объектов типа A, которые на него ссылаются.
Вся совокупность объектов B образует кэш. Имеется менеджер кэша, который хранит список всех объектов B. В произвольный момент времени менеджер кэша может удалить произвольное число объектов B, если сочтёт, что их «слишком много». Все объекты A, которые содержали указатель на удаленный объект, начинают содержать NULL.
Имеются сервисные потоки, которые подготавливают данные для объектов B и управляют кэшем.
Имеются потоки-клиенты, которые в стеке хранят _указатели_ на объекты A. (Один объект A может быть доступен нескольким потокам.)
Возможны следующие операции:
Для клиентских потоков:
void schedule_A(A *a, char * key);
Если объект B с ключём key имеется в кэше, ссылка на него будет помещена в A.
Если объекта нет в кэше, он будет создан, и ссылка на него будет помещена в A.
Объект B может быть в любом состоянии и изменить состояние с не готов на готов в любой момент времени.
data_t deref_A(A *a);
Если объект A не ссылается ни на один объект B, возвращает специальное значение NONE.
Если объект A ссылается на объект B, и данные в объекте B готовы, возвращает данные.
Если объект A ссылается на объект B, но данные в объекте B не готовы, текущий поток засыпает, пока не произойдёт одно из двух событий:
* Данные станут готовы. (Возвращает данные.)
* Объект A перестаёт ссылаться на какой-либо объект B (начинает ссылаться на NULL). (Возвращает NONE.)
Для сервисных потоков:
B * acquire_by_key_B(char * key);
Ищет объект в кэше и захватывает мьютекст на доступ к нему. (В общем случае возможны разные варианты функций выборки: acquire_oldest_B, acquire_oldest_not_ready_B и т.п.)
void validate_B(B *b);
Отмечает объект как готовый.
void drop_B(B *b);
Отмечает объект как удалённый.
void release_B(B * b);
Освобождает мьютекс на доступ к объекту.
Если объект отмечен как готовый, все клиентские потоки, которые ждали готовности объекта внутри функции deref_A(), просыпаются и возвращают значение.
Если объект отмечен как удалённый, все клиентские потоки, которые ждали готовности объекта внутри функции deref_A(), просыпаются и возвращают NONE, а занятая объектом память освобождается.
Если объект отмечен и как готовый, и как удалённый, флаг удаленный имеет приоритет. (Т.е. клиенты получают NONE.)
Задача:
Придумать алгоритм для указаного выше API, не содержащий race condition. В функциях deref_A(), validate_B(), drop_B() и release_B() алгоритм должен работать с per-object блокировками. То есть, если потоки оперируют непересекающимися наборами объектов, они не должны тормозить друг друга на точках синхронизации. (За исключением логики освобождения памяти внутри release_B(), где возможен глобальный мьютекс на куче.)
