Лекция 8. Неблокирующая хеш-таблица

Андрей Гейн: Мы запускаем программы параллельно на нескольких процессорах. При этом нужно использовать блокировки, чтобы предохранить внутреннее состояние программы при одновременном доступе из разных потоков. Неблокирующие структуры данных решают эту проблему. Мы разберём, как сделать так, чтобы классическая хеш-таблица могла работать без блокировок. Субъективная сложность лекции — три теты из пяти. Содержание: 5:24 Блокирующие алгоритмы 8:32 Неблокирующие алгоритмы 13:02 Аппаратная поддержка, операции CAS и FAI 22:09 Реализация FAI через CAS 27:54 Хеш-таблица с закрытой адресацией 35:38 Неблокирующий сортированный односвязный список 40:57 Линеаризуемость и сериализуемость операций 44:17 Добавление и удаление элементов в списке 50:06 Конкурентное удаление и добавление, меченые указатели 55:38 Управление памятью в неблокирующих алгоритмах 59:30 Увеличение хеш-таблицы: алгоритм хэширования 1:10:44 Добавление и удаление элементов в хеш-таблице 1:14:35 Увеличение хеш-таблицы: инициализация указателей 1:17:01 Увеличение хеш-таблицы: выделение памяти 1:21:25 «Разворот» битового представления целого числа 1:27:22 Вопросы