달력 대기열

캘린더 대기열(CQ)은 우선순위 대기열(모든 요소가 관련 우선순위를 가지고 있고 대기열 제거 작업이 가장 높은 우선순위 요소를 제거하는 대기열)이다.인간이 날짜별로 미래의 사건을 주문할 때 사용하는 탁상 달력과 비슷하다.이산 이벤트 시뮬레이션에는 보류 중인 이벤트를 시간에 따라 정렬하는 미래 이벤트 리스트(FEL) 구조가 필요하다.이러한 시뮬레이터는 대기열 관리에 소요되는 시간이 상당할 수 있으므로 훌륭하고 효율적인 데이터 구조를 필요로 한다.(최적 버킷 크기의) 캘린더 대기열은 O(1) 평균 성능에 근접할 수 있다.캘린더 대기열은 버킷 대기열과 밀접하게 관련되어 있지만 검색 방법이나 동적 크기 조정 방법에서는 그것과 다르다.

실행

이론적으로, 버킷 대기열처럼, 캘린더 대기열은 연결된 목록들의 배열로 구성된다.때때로 배열의 각 인덱스를 버킷이라고도 한다.버킷의 너비가 지정되었으며 링크된 목록에는 타임스탬프가 해당 버킷에 매핑되는 이벤트가 저장되어 있다.탁상용 달력은 하루의 너비로 매일 365개의 양동이를 가지고 있다.각 배열 요소에는 해당 링크된 목록의 머리글인 포인터가 하나 포함되어 있다.배열 이름이 "월"인 경우, 월[11]은 해당 연도의 12개월에 예약된 이벤트 리스트에 대한 포인터(벡터 지수는 0부터 시작)이다.따라서 전체 달력은 12개의 포인터와 최대 12개의 링크된 목록 모음으로 구성된다.캘린더 대기열에서 FEL에서 이벤트의 enqueue(대기열의 추가) 및 dequeue(대기열에서 삭제)는 이벤트 시간을 기준으로 한다.

너비가 w인 버킷이 n개인 달력을 대기열에 넣으십시오.그런 다음 시간 t가 있는 이벤트의 enqueue는 버킷 t ${\displaystyle \frac{w}{}}$ ${\displaystyle \mathrm{mod}}$ ${\displaystyle n}$ ${\displaystyle {\frac {t}{w}\modn}$에서 작동하며,$$ 증가된 타임스탬프에 따라 버킷에서 스케줄링된 이벤트가 두 개 이상 있다.캘린더 대기열에서 이벤트를 삭제하기 위해 현재 연도 및 날짜를 추적한다.그런 다음 버킷 내에서 가장 이른 이벤트를 검색하여 대기열을 해제한다. (대조적으로 버킷 대기열은 첫 번째 비어 있지 않은 버킷에서 어떤 요소가 가장 빠른지 결정하지 않고 어떤 요소라도 반환할 뿐이다.)

일정관리 대기열 크기 조정 작업

대기열의 이벤트 수가 버킷 수보다 훨씬 작거나 훨씬 큰 경우, 효율적으로 작동하지 않는다.해결책은 대기열이 커지고 줄어들수록 버킷 수가 그에 상응해 증가하거나 줄어들 수 있도록 하는 것이다.크기 조정 작업을 단순화하기 위해 CQ의 Nb(버킷 수)를 2의 검정력($즉{\displaystyle }$, ${\displaystyle \mathrm{Nb}}$= ${\displaystyle {2n}^{}}${\$displaystyle Nb=2^{n})$으로 선택하는 경우가 많다.

버킷 수는 Ne(이벤트 수)가 각각 2Nb를 초과하거나 Nb/2 이하로 감소할 때마다 두 배 또는 반으로 줄어든다.Nb 크기가 조정되면 새로운 폭 w도 계산해야 한다.채택된 새로운 w는 현재 버킷 위치에서 시작하는 처음 수백 개의 이벤트로부터 이벤트 간 평균 시간 차이를 표본으로 추출하여 추정할 것이다.이후 새로운 일정관리 대기열이 작성되고 이전 일정관리의 모든 이벤트가 다시 수집된다.

참조

• Brown, R. (October 1988), "Calendar queues: a fast ${\displaystyle O(1)}$ priority queue implementation for the simulation event set problem", Communications of the ACM, 31 (10): 1220–1227, doi:10.1145/63039.63045
• Erickson, K. Bruce; Ladner, Richard E.; LaMarca, Anthony (2000), "Optimizing static calendar queues", ACM Transactions on Modeling and Computer Simulation, 10 (3): 179–214, doi:10.1145/361026.361028
• Fujimoto, Richard M. (October 1990), "Parallel discrete event simulation", Communications of the ACM, 33 (10): 30–53, doi:10.1145/84537.84545
• Tan, Kah Leong; Thng, Li-Jin, "SNOOPy Calendar Queue", 2000 Winter Simulation Conference Proceedings, IEEE, doi:10.1109/wsc.2000.899756