ACE에서 우선순위 큐(Priority Queue) Programming

일반적인 큐(Queue)는 선입선출 구조입니다. 먼저 넣은 것이 먼저 나옵니다. 하지만 우선순위 큐(Priority Queue)는 Element에 우선순위를 부여해서 넣을 수 있고, 우선 순위에 의해 꺼내어 집니다. 여기에 설명이 잘 되어 있더군요.
  • 큐에 '무엇인가'를 넣을 수 있다. 여기에 숫자로 된 우선순위를 꼬리표로 해서 함께 넣는다.
  • 큐에서 가장 높은 우선순위의 꼬리표가 붙은 '무엇인가'를 꺼낼 수 있다.
  • 가장 높은 우선순위에 무엇이 있는지 볼 수 있다. (꺼내지 않는다)
ACE도 여러가지 컨테이너 클래스를 제공하지만 우선순위 큐는 없습니다. 하지만 ACE_Message_Queue를 사용하면 우선순위 큐의 효과를 볼 수 있습니다. ACE_Message_Queue에 대해서는 이 포스팅에서 설명하고 있으니 생략하겠습니다.

일반적인 Enqueue / Dequeue
block1 = new ACE_Message_Block(1);
block2 = new ACE_Message_Block(2);
block3 = new ACE_Message_Block(3);
queue.enqueue_tail(block1);
queue.enqueue_tail(block2);
queue.enqueue_tail(block3);
ACE_Message_Block* block = NULL;
while(queue.dequeue_head(block) != -1)
        ACE_DEBUG((LM_INFO,"Block Size(%d)\n", block->size()));

결과
Block Size(1)
Block Size(2)
Block Size(3)

우선순위를 이용한 Enqueue / Dequeue
block1 = new ACE_Message_Block(1);
block2 = new ACE_Message_Block(2);
block3 = new ACE_Message_Block(3);
block1->msg_priority(2);
block2->msg_priority(3);
block3->msg_priority(1);
queue.enqueue_prio(block1);
queue.enqueue_prio(block2);
queue.enqueue_prio(block3);
ACE_Message_Block* block = NULL;
while(queue.dequeue_prio(block) != -1)
        ACE_DEBUG((LM_INFO,"Block Size(%d) Priority(%d)\n", block->size(), block->msg_priority()));

결과
Block Size(3) Priority(1)
Block Size(1) Priority(2)
Block Size(2) Priority(3)
사이즈가 3인 블럭을 가장 나중에 넣었지만 우선순위가 1로 가장 높으므로 가장 먼저 나옵니다.

HalfNetwork에서 예약 전송 기능을 구현하기 위해 우선순위 큐가 필요했습니다. 나중에 넣더라도 먼저 전송되어야 하는 경우가 있어서 입니다.  아래 코드는 전송예약을 하는 부분 입니다.
void ReserveSend(ACE_Message_Block* block, u_int32 delay)
{
    block->msg_priority(GetTickCount()+delay);
    _reserve_queue->enqueue_prio(block);
}
msg_priority에 GetTickCount()+delay를 넣으면 가장 최근에 전송될 블럭이 높은 우선순위를 가지게 됩니다.
아래 코드는 큐를 체크해서 보내는 부분 입니다.
void SendReserveBlock()
{
    ACE_Time_Value wait_time(0, 0);
    ACE_Message_Block* reserve_block = NULL;
    if (-1 == _reserve_queue->peek_dequeue_head(reserve_block, &wait_time))
        return;
    if (reserve_block->msg_priority() > GetTickCount() )
        return;
    if (-1 == _reserve_queue->dequeue_prio(reserve_block, &wait_time))
        return;
    Send(reserve_block);
}
추가합니다. 위의 코드에 오류가 있습니다.
아래와 같이 수정되어야 합니다.
void SendReserveBlock()
{
    ACE_Time_Value wait_time(0, 0);
    ACE_Message_Block* reserve_block = NULL;
    if (-1 == _reserve_queue->dequeue_prio(reserve_block, &wait_time))
        return;
    if (reserve_block->msg_priority() > GetTickCount() )
    {
        _reserve_queue->enqueue_prio(reserve_block, &wait_time)
        return;
     }
    Send(reserve_block);
}
peek_dequeue_head() 메소드는 꺼내지 않고 가장 먼저 나올 블럭을 확인하는 기능인데, 우선순위까지 고려하지는 않습니다. 단순히 가장 먼저 넣은 블럭이 선택됩니다. 혼동할 소지가 많으므로 반드시 확인해야 합니다. 

핑백

  • flexible gameserver : 우선순위 작업큐 만들기 2009-12-07 18:00:12 #

    ... 가지죠. 이런 경우에 적용할 수 있는 방법입니다. 간단히 설명하면 기존 일반작업큐를 우선순위큐로 바꾸면됩니다. 우선순위큐에 대해서는 여기를 참조하시고 ACE에서는 ACE_Message_Queue가 우선순위큐 기능을 제공합니다. 다행히 지난번 작성한 예제에서 작업을 저장해주 ... more

덧글

  • im.fehead 2010/12/24 13:47 # 삭제 답글

    오옷. 소스보면서 이것 보니깐 이해가 빨라지네요.
    이런 좋은 기능이 숨어 있었군요~.
댓글 입력 영역