Поделиться через

Переблокируемые единые связанные списки

  • Статья

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

Списки SList легко реализовать и использовать в 32-разрядном коде. Однако реализовать их в 64-разрядном коде сложно, так как объем данных, которыми обмениваются собственные примитивы обмена с блокировкой, не вдвое превышает размер адреса, как в 32-разрядном коде. Таким образом, списки SList позволяют переносить высокопроизводительные масштабируемые алгоритмы в Windows.

Windows 8. Начиная с Windows 8 для 64-разрядного кода, например InterlockedCompare64Exchange128, доступны соответствующие собственные примитивы для обмена.

Приложения могут использовать списки SList, вызывая функцию InitializeSListHead для инициализации заголовка списка. Чтобы вставить элементы в список, используйте функцию InterlockedPushEntrySList . Чтобы удалить элементы из списка, используйте функцию InterlockedPopEntrySList .

Все элементы списка должны быть выровнены по границе MEMORY_ALLOCATION_ALIGNMENT . Несровненные элементы могут привести к непредсказуемым результатам. См . _aligned_malloc.

Пример см. в разделе Использование единых связанных списков.

В следующей таблице перечислены функции SList.

Функция Описание
InitializeSListHead Инициализирует заголовок отдельно связанного списка.
InterlockedFlushsList Очищает весь список элементов в отдельно связанном списке.
InterlockedPopEntrySList Удаляет элемент из передней части списка, связанного по отдельности.
InterlockedPushEntrySList Вставляет элемент в начало единого связанного списка.
InterlockedPushListSList Вставляет одинный связанный список в начало другого списка, связанного по отдельности.
InterlockedPushListsListEx Вставляет одинный связанный список в начало другого списка, связанного по отдельности. Эта версия метода не использует соглашение о вызовах __fastcall .
RtlFirstEntrySList Извлекает первую запись в отдельно связанном списке.
QueryDepthSList Извлекает количество записей в указанном по отдельности связанном списке.