Singly 및 두 배로 연결된 목록

아티클
06/15/2023

Singly 연결된 목록

운영 체제는 SINGLE_LIST_ENTRY 구조를 사용하는 singly 연결된 목록에 대한 기본 제공 지원을 제공합니다. 적절하게 연결된 목록은 목록 헤드와 일부 목록 항목으로 구성됩니다. (목록이 비어 있는 경우 목록 항목 수는 0입니다.) 각 목록 항목은 SINGLE_LIST_ENTRY 구조로 표시됩니다. 목록 헤드는 SINGLE_LIST_ENTRY 구조로도 표시됩니다.

각 SINGLE_LIST_ENTRY 구조체에는 다른 SINGLE_LIST_ENTRY 구조를 가리키는 Next 멤버가 포함됩니다. 목록 헤드를 나타내는 SINGLE_LIST_ENTRY 구조에서 다음 멤버는 목록의 첫 번째 항목을 가리키거나 목록이 비어 있는 경우 NULL입니다. 목록의 항목을 나타내는 SINGLE_LIST_ENTRY 구조에서 다음 멤버는 목록의 다음 항목을 가리키거나 이 항목이 목록의 마지막 항목인 경우 NULL입니다.

연결된 목록을 조작하는 루틴은 목록 헤드를 나타내는 SINGLE_LIST_ENTRY 대한 포인터를 사용합니다. 작업 후 목록의 첫 번째 항목을 가리키도록 Next 포인터를 업데이트합니다.

ListHead 변수가 목록 헤드를 나타내는 SINGLE_LIST_ENTRY 구조체에 대한 포인터라고 가정합니다. 드라이버는 다음과 같이 ListHead 를 조작합니다.

목록을 빈 목록으로 초기화하려면 ListHead-Next>를 NULL로 설정합니다.
목록에 새 항목을 추가하려면 새 항목을 나타내는 SINGLE_LIST_ENTRY 할당한 다음 PushEntryList 를 호출하여 목록의 시작 부분에 항목을 추가합니다.
PopEntryList를 사용하여 목록에서 첫 번째 항목을 팝합니다.

SINGLE_LIST_ENTRY 자체에는 Next 멤버만 있습니다. 목록에 사용자 고유의 데이터를 저장하려면 다음과 같이 SINGLE_LIST_ENTRY 목록 항목을 설명하는 구조체의 멤버로 포함시켰습니다.

typedef struct {
  // driver-defined members
  .
  .
  .
  SINGLE_LIST_ENTRY SingleListEntry;
 
  // other driver-defined members
  .
  .
  .
} XXX_ENTRY;

목록에 새 항목을 추가하려면 XXX_ENTRY 구조를 할당한 다음 , SingleListEntry 멤버에 대한 포인터를 PushEntryList에 전달합니다. 포인터를 SINGLE_LIST_ENTRY 다시 XXX_ENTRY 변환하려면 CONTAINING_RECORD 사용합니다. 다음은 연결된 목록에서 드라이버 정의 항목을 삽입하고 제거하는 루틴의 예입니다.

typedef struct {
  PVOID DriverData1;
  SINGLE_LIST_ENTRY SingleListEntry;
  ULONG DriverData2;
} XXX_ENTRY, *PXXX_ENTRY;

void
PushXxxEntry(PSINGLE_LIST_ENTRY ListHead, PXXX_ENTRY Entry)
{
    PushEntryList(ListHead, &(Entry->SingleListEntry));
}

PXXX_ENTRY
PopXxxEntry(PSINGLE_LIST_ENTRY ListHead)
{
    PSINGLE_LIST_ENTRY SingleListEntry;
    SingleListEntry = PopEntryList(ListHead);
    return CONTAINING_RECORD(SingleListEntry, XXX_ENTRY, SingleListEntry);
}

또한 시스템은 목록 작업의 원자성 버전인 ExInterlockedPopEntryList 및 ExInterlockedPushEntryList를 제공합니다. 각각은 추가 스핀 잠금 매개 변수를 사용합니다. 루틴은 목록을 업데이트하기 전에 스핀 잠금을 획득한 다음, 작업이 완료된 후 루틴이 스핀 잠금을 해제합니다. 잠금이 유지되는 동안 인터럽트는 사용하지 않도록 설정됩니다. 목록의 각 작업은 동일한 스핀 잠금을 사용하여 목록의 각 작업이 다른 모든 작업과 동기화되도록 해야 합니다. 이러한 ExInterlockedXxx목록 루틴에서만 스핀 잠금을 사용해야 합니다. 다른 용도로는 스핀 잠금을 사용하지 마세요. 드라이버는 여러 목록에 동일한 잠금을 사용할 수 있지만, 이 동작은 잠금 경합을 증가하므로 드라이버는 이를 피해야 합니다.

예를 들어 ExInterlockedPopEntryList 및 ExInterlockedPushEntryList 루틴은 IRQL = PASSIVE_LEVEL 실행 중인 드라이버 스레드와 DIRQL에서 실행되는 ISR을 통해 Singly 연결된 목록의 공유를 지원할 수 있습니다. 이러한 루틴은 스핀 잠금이 유지되면 인터럽트 사용 안 함. 따라서 ISR 및 드라이버 스레드는 교착 상태의 위험 없이 이러한 ExInterlockedXxx목록 루틴에 대한 호출에서 동일한 스핀 잠금을 안전하게 사용할 수 있습니다.

동일한 목록에 있는 목록 작업의 원자성 및 비원자 버전에 대한 호출을 혼합하지 마세요. 원자성 및 비원자 버전이 동일한 목록에서 동시에 실행되는 경우 데이터 구조가 손상되고 컴퓨터가 응답하지 않거나 버그 검사(즉, 크래시)될 수 있습니다. (목록 작업의 원자성 및 비원자 버전에 대한 호출을 혼합하는 대신 비원자성 루틴을 호출하는 동안에는 스핀 잠금을 획득할 수 없습니다. 이러한 방식으로 스핀 잠금을 사용하는 것은 지원되지 않으며 여전히 목록 손상이 발생할 수 있습니다.)

또한 시스템은 더 효율적인 원자성 연결 목록의 대체 구현을 제공합니다. 자세한 내용은 시퀀싱된 Singly 연결된 목록을 참조하세요.

이중 연결된 목록

운영 체제는 LIST_ENTRY 구조를 사용하는 두 배로 연결된 목록에 대한 기본 제공 지원을 제공합니다. 이중으로 연결된 목록은 목록 헤드와 일부 목록 항목으로 구성됩니다. (목록이 비어 있는 경우 목록 항목 수는 0입니다.) 각 목록 항목은 LIST_ENTRY 구조로 표시됩니다. 목록 헤드는 LIST_ENTRY 구조로도 표시됩니다.

각 LIST_ENTRY 구조체에는 Flink 멤버와 Blink 멤버가 포함됩니다. 두 멤버 모두 LIST_ENTRY 구조체에 대한 포인터입니다.

목록 헤드를 나타내는 LIST_ENTRY 구조에서 Flink 멤버는 목록의 첫 번째 항목을 가리키고 Blink 멤버는 목록의 마지막 항목을 가리킵니다. 목록이 비어 있으면 목록 헤드의 Flink 및 Blink 가 목록 헤드 자체를 가리킵니다.

목록의 항목을 나타내는 LIST_ENTRY 구조에서 Flink 멤버는 목록의 다음 항목을 가리키고 Blink 멤버는 목록의 이전 항목을 가리킵니다. (항목이 목록의 마지막 항목인 경우 Flink 는 목록 헤드를 가리킵니다. 마찬가지로 항목이 목록의 첫 번째 항목인 경우 Blink 는 목록 헤드를 가리킵니다.)

이러한 규칙은 언뜻 보기에 놀라운 것처럼 보일 수 있지만 조건부 코드 분기 없이 목록 삽입 및 제거 작업을 구현할 수 있습니다.

이중으로 연결된 목록을 조작하는 루틴은 목록 헤드를 나타내는 LIST_ENTRY 대한 포인터를 사용합니다. 이러한 루틴은 목록 머리의 Flink 및 Blink 멤버를 업데이트하여 이러한 멤버가 결과 목록의 첫 번째 및 마지막 항목을 가리키도록 합니다.

ListHead 변수가 목록 헤드를 나타내는 LIST_ENTRY 구조체에 대한 포인터라고 가정합니다. 드라이버는 다음과 같이 ListHead 를 조작합니다.

목록을 빈 목록으로 초기화하려면 ListHead-Flink 및 ListHead-Blink>> 를 초기화하는 InitializeListHead를 사용하여 ListHead를 가리킵니다.
목록의 맨 앞에 새 항목을 삽입하려면 새 항목을 나타내는 LIST_ENTRY 할당한 다음 InsertHeadList 를 호출하여 목록의 시작 부분에 항목을 삽입합니다.
목록의 꼬리에 새 항목을 추가하려면 새 항목을 나타내는 LIST_ENTRY 할당한 다음 InsertTailList 를 호출하여 목록 끝에 항목을 삽입합니다.
목록에서 첫 번째 항목을 제거하려면 RemoveHeadList를 사용합니다. 목록에서 제거된 항목에 대한 포인터를 반환하거나 목록이 비어 있는 경우 ListHead 에 대한 포인터를 반환합니다.
목록에서 마지막 항목을 제거하려면 RemoveTailList를 사용합니다. 목록에서 제거된 항목에 대한 포인터를 반환하거나 목록이 비어 있는 경우 ListHead 에 대한 포인터를 반환합니다.
목록에서 지정된 항목을 제거하려면 RemoveEntryList를 사용합니다.
검사 목록이 비어 있는지 확인하려면 IsListEmpty를 사용합니다.
목록을 다른 목록의 꼬리에 추가하려면 AppendTailList를 사용합니다.

LIST_ENTRY 자체에는 Blink 및 Flink 멤버만 있습니다. 목록에 사용자 고유의 데이터를 저장하려면 다음과 같이 목록 항목을 설명하는 구조체의 멤버로 LIST_ENTRY 포함합니다.

typedef struct {
  // driver-defined members
  .
  .
  .
  LIST_ENTRY ListEntry;
 
  // other driver-defined members.
  .
  .
  .
} XXX_ENTRY;

목록에 새 항목을 추가하려면 XXX_ENTRY 구조를 할당한 다음 ListEntry 멤버에 대한 포인터를 InsertHeadList 또는 InsertTailList에 전달합니다. 포인터를 LIST_ENTRY 다시 XXX_ENTRY 변환하려면 CONTAINING_RECORD 사용합니다. 이 기술의 예는 Singly 연결된 목록을 사용하여 위의 Singly 연결된 목록을 참조하세요.

또한 시스템은 목록 작업의 원자성 버전인 ExInterlockedInsertHeadList, ExInterlockedInsertTailList 및 ExInterlockedRemoveHeadList를 제공합니다. ( RemoveTailList 또는 RemoveEntryList의 원자성 버전은 없습니다.) 각 루틴은 추가 스핀 잠금 매개 변수를 사용합니다. 루틴은 목록을 업데이트하기 전에 스핀 잠금을 획득한 다음 작업이 완료된 후 스핀 잠금을 해제합니다. 잠금이 유지되는 동안 인터럽트는 사용하지 않도록 설정됩니다. 목록의 각 작업은 동일한 스핀 잠금을 사용하여 목록의 이러한 각 작업이 서로 동기화되도록 해야 합니다. 이러한 ExInterlockedXxx목록 루틴에서만 스핀 잠금을 사용해야 합니다. 다른 용도로는 스핀 잠금을 사용하지 마세요. 드라이버는 여러 목록에 동일한 잠금을 사용할 수 있지만, 이 동작은 잠금 경합을 증가하므로 드라이버는 이를 피해야 합니다.

예를 들어 ExInterlockedInsertHeadList, ExInterlockedInsertTailList 및 ExInterlockedRemoveHeadList 루틴은 IRQL = PASSIVE_LEVEL 실행 중인 드라이버 스레드와 DIRQL에서 실행되는 ISR을 통해 이중으로 연결된 목록의 공유를 지원할 수 있습니다. 이러한 루틴은 스핀 잠금이 유지되면 인터럽트 사용 안 함. 따라서 ISR 및 드라이버 스레드는 교착 상태의 위험 없이 이러한 ExInterlockedXxx목록 루틴에 대한 호출에서 동일한 스핀 잠금을 안전하게 사용할 수 있습니다.

동일한 목록에 있는 목록 작업의 원자성 및 비원자 버전에 대한 호출을 혼합하지 마세요. 원자성 및 비원자 버전이 동일한 목록에서 동시에 실행되는 경우 데이터 구조가 손상되어 컴퓨터가 응답하지 않거나 버그 검사(즉, 크래시)될 수 있습니다. (목록 작업의 원자성 및 비원자 버전에 대한 호출을 혼합하지 않도록 비원자성 루틴을 호출하는 동안 스핀 잠금을 획득할 수 없습니다. 이러한 방식으로 스핀 잠금을 사용하는 것은 지원되지 않으며 여전히 목록 손상이 발생할 수 있습니다.)

시퀀싱된 Singly 연결된 목록

시퀀싱된 Singly 연결된 목록은 원자성 연산을 지원하는 Singly 연결된 목록의 구현입니다. Singly 연결된 목록에 설명된 Singly 연결된 목록을 구현하는 것보다 원자성 작업에 더 효율적입니다.

SLIST_HEADER 구조는 시퀀싱된 singly 연결된 목록의 헤드를 설명하는 데 사용되고 SLIST_ENTRY 목록의 항목을 설명하는 데 사용됩니다.

드라이버는 다음과 같이 목록을 조작합니다.

SLIST_HEADER 구조를 초기화하려면 ExInitializeSListHead를 사용합니다.
목록에 새 항목을 추가하려면 새 항목을 나타내는 SLIST_ENTRY 할당한 다음 ExInterlockedPushEntrySList 를 호출하여 목록의 시작 부분에 항목을 추가합니다.
ExInterlockedPopEntrySList를 사용하여 목록에서 첫 번째 항목을 팝합니다.
목록을 완전히 지우려면 ExInterlockedFlushSList를 사용합니다.
목록의 항목 수를 확인하려면 ExQueryDepthSList를 사용합니다.

SLIST_ENTRY 그 자체로 Next 멤버만 있습니다. 목록에 사용자 고유의 데이터를 저장하려면 다음과 같이 목록 항목을 설명하는 구조체의 멤버로 SLIST_ENTRY 포함합니다.

typedef struct 
{
  // driver-defined members
  .
  .
  .
  SLIST_ENTRY SListEntry;
  // other driver-defined members
  .
  .
  .

} XXX_ENTRY;

목록에 새 항목을 추가하려면 XXX_ENTRY 구조를 할당한 다음 SListEntry 멤버에 대한 포인터를 ExInterlockedPushEntrySList에 전달합니다. 포인터를 SLIST_ENTRY 다시 XXX_ENTRY 변환하려면 CONTAINING_RECORD 사용합니다. 이 기술의 예는 시퀀싱이 아닌 Singly 연결된 목록을 사용하여 Singly 연결된 목록을 참조하세요.

경고 64비트 Microsoft Windows 운영 체제의 경우 SLIST_ENTRY 구조는 16 바이트 정렬되어야 합니다.

Windows XP 이상 버전의 Windows는 Windows 2000에서 사용할 수 없는 시퀀싱된 연결 목록 함수의 최적화된 버전을 제공합니다. 드라이버가 이러한 함수를 사용하고 Windows 2000에서도 실행해야 하는 경우 드라이버는 다음과 같이 _WIN2K_COMPAT_SLIST_USAGE 플래그를 정의해야 합니다.

#define _WIN2K_COMPAT_SLIST_USAGE

x86 기반 프로세서의 경우 이 플래그를 사용하면 컴파일러가 Windows 2000과 호환되는 시퀀싱된 연결 목록 함수 버전을 사용합니다.

다음을 통해 공유

Singly 및 두 배로 연결된 목록

Singly 연결된 목록

이중 연결된 목록

시퀀싱된 Singly 연결된 목록

피드백

추가 리소스