Queue

#  큐의 구조 

그림1. 링크드 리스트로 구현한 큐의 구조

  큐도 스택과 마찬가지로 매우 직관적인 구조를 가진다. 한쪽에서는 삽입이, 반대쪽에서는 삭제가 이루어진다. 삽입과 삭제는 들어온 순서대로 이루어지며 먼저 도착한 데이터가 먼저 나가는 FIFO 구조를 가진다. 큐도 구현하기에 따라 배열로도, 리스트로도 구현할 수 있다. 이 글에서는 배열로 구현되어 있다. 스택과 다르게 배열로 구현한 쪽이 조금 더 복잡하다. 

 

 

 

#  순환 큐의 구현

그림2. 배열로 구현한 큐

 

  큐를 단순히 배열에 넣고 구현한다면 삭제를 한번 수행할 때 마다 모든 원소를 한 칸 움직이는 연산을 수행해야 하므로 비효율적이다. 그러므로 우리는 포인터를 움직이는 방식으로 삭제와 삽입을 구현해야 한다. 그러나 이 방식으로는 완전하게 큐를 구현할 수 없는데, 삽입과 삭제 연산이 일어나다 보면 Front, Rear 포인터의 위치가 매번 바뀌기 때문에 배열을 전부 사용할 수 없게 된다. Front의 위치는 첫 번째 위치를 가리키고 있고, Rear의 위치는 마지막 원소 + 1의 위치를 가리키고 있다.

 

 

그림3. 배열 구현의 문제점-1

 

  그림3에서 자세한 내용을 확인할 수 있다. 그림2로부터 deQueue 연산이 두 번 일어나 Element 3 위치가 큐의 새로운 Front가 되었는데, 이때 새로운 Element를 큐에 넣으려고 한다면 자리가 부족해 넣을 수 없다. (사실, Rear가 가리키고 있는 위치에 새로운 원소를 삽입할 수 있다. 그러나 enQueue 연산이 또 일어나게 될 경우, 원소를 넣을 자리를 마련할 수 없다.) 이 경우, 온전하게 Capacity를 사용할 수 없게 된다. 큐를 순환하게 만든다면 Rear 포인터가 배열의 마지막 부분을 가리키게 되어서 이 문제를 해결할 수 있다. 

 

그림4. 배열 구현의 문제점-2

 

  그림4에서 이 부분에 대한 해결책을 찾을 수 있다. Rear의 위치를 배열의 마지막 위치로 옮긴다면 다음 원소를 추가할 수 있을 것이다. 그러나 아직도 이 구조는 문제점을 가지고 있다.

 

그림5. 배열 구현의 문제점-3

 

  그림5는 그림4에서 enQueue 연산을 2번 더 수행 한 결과이다. 마지막 Element 8을 Rear 위치에 추가했고, Rear 포인터는 마지막 원소의 다음 위치를 가리키고 있다.

 

그림6. 배열 구현의 문제점-4

 

그림5와 그림6을 보면 포인터 만으로 큐가 비어있는지 다 찼는지 구별할 수 없다. 때문에 배열로 큐를 구현할때는 입력받은 Capacity보다 1 크게 배열을 할당하여 Rear와 Front 사이의 공간을 띄워주는 방식으로 구현한다. 

배열이 모두 비어있다면 Front와 Rear의 위치는 같을 것이고, 배열이 모두 찼다면 Front + 1이 Rear의 위치가 된다.

 

그림7. 완성된 큐의 모습.

 

링크드 리스트 방식으로 구현한다면 굳이 순환하는 구조를 만들지 않아도 큐를 이상적인 형태로 만들 수 있다. 또한 노드를 연결하는 방식으로 만든다면 모두 같은 타입이 저장되어야 하는 배열에 비해 사용하기 쉬운 여러 장점이 있을 것이다. 그러나 OS 관점에서 최대한 리소스를 적게 사용하여 최적화 하고 싶어 이 방법을 선택하였다. 그럼에도 링크드 리스트 방식은 장점이 많은 구조이기 때문에 추후에 코드를 추가하겠다. 링크드 리스트를 사용한 방식은 사용자 관점에서 사용하기에 편할 것이다.

 

 

#  큐 구조체

typedef struct tagCircularQueue
{
    int Capacity;
    int Front;
    int Rear;
    Node* Nodes;
} CircularQueue;

 

  큐의 구조체이다. Front와 Rear는 배열의 위치를 가리키는 index로 사용되었다. Capacity는 배열의 크기를 나타낸다. 배열로 선언한 스택도 같은 문제를 가지고 있지만, 배열은 한번 크기가 정해지면 바꿀 수 없다. 때문에 한번 선언할때 오버플로우가 나타나지 않도록 설정해야 하면서도 공간 낭비가 되지 않게 해야 한다.

 

 

#  큐의 함수

void        CQ_EnQueue(CircularQueue* Queue, ElementType Data);
ElementType CQ_DeQueue(CircularQueue* Queue);

 

  큐는 간단하면서도 필수적인 함수 2가지가 있다. 프로그래머가 이외에도 필요에 따라 is_empty, is_full, get_size등과 같은 함수를 추가로 선언할 수 있다. 

 

▶ enQueue Function

그림8. enQueue-1

 

Element 1과 2가 enQueue()에 의해 차례로 큐에 삽입된다. 새로운 원소 Element 3이 들어온다면 현재 Rear 위치에 Element 3이 삽입 되고, Rear 위치는 한 칸 왼쪽으로 옮겨지게 된다.

 

그림9. enQueue-2

 

새로운 Rear의 위치는 다음 원소가 들어올 장소를 가리키고 있다.

 

 

---

 

 

그림10. enQueue-3

 

만약 그림10과 같이 Front가 배열의 중간에 있고 새로운 원소 Element 3이 배열의 마지막 위치에 삽입된다면, Rear은 그림11 처럼 배열의 첫 부분을 가리켜야 한다.

 

그림11. enQueue-4

 

구현에 대한 부분은 페이지 마지막에 깃허브 주소에 올려놓았다. 

 

 

▶ deQueue Function

그림12. deQueue-1

 

deQueue의 경우도 enQueue와 비슷하게 구현된다. 그림12에서 deQueue 연산을 수행한다면 아래 그림과 같이 큐가 변형된다.

 

그림13. deQueue-2

 

 

※ Micro OS3 큐 활용

그림14. Micro C OS3에서의 큐 활용

 

  마이크로 os에서의 대표적으로 큐를 활용하는 방법이다. 그림14는 Task 또는 ISR(Interrupt Service Routine)이 또 다른 Task에 Post를 날리는 모습이다. 오른쪽에 있는 Task가 OSQPend 함수를 실행했을 때, Post 된 메시지가 없다면 메시지가 날라올때까지(Post 될 때까지) Pend List에서 기다리게 된다. 이때 왼쪽의 Task나 ISR에서 메시지를 큐에 OSQPost 함수 등으로 전달하면 큐에 메시지가 들어가게 되고, 오른쪽 Task는 메시지를 받는다. 

 

Task는 OSQPost 함수 이외에도 여러 함수를 사용해서 메시지를 보낼 수 있지만, ISR은 OSQPost 함수 하나만 호출할 수 있다. 이유는 ISR이 실행 중일 때 인터럽트가 꺼지는데, 그 시간을 최대한 줄이는 것이 목적이기 때문이다. Post 함수 이외의 함수들은 정밀한 시간을 보장하기 어렵다.

 

그림15. Deferred Post 방식

 

심지어 더욱 정밀한 시간을 보장하고 싶다면 deferred post 방식을 사용하기도 한다. 이 방법은 인터럽트 큐를 만들어서 ISR이 Task에 직접 Post를 날리는 것이 아니라 Int Q Task가 대신 큐에 들어온 순서대로 Post를 날린다. 

 

이 방법은 인터럽트가 꺼져 있는 시간을 줄여주어 좀 더 실시간 운영체제에 걸맞는 방식이라고 할 수 있겠다. 물론, 항상 그렇지만 이 방법이 direct post(ISR이 직접 Task에 Post를 날리는 방법)보다 우월한 것은 아니다. 구현이 조금 더 복잡하고 Task가 많지 않다면 오버헤드가 발생할 수 있다.

 

이런 메시지 큐 이외에도 세마포어와 결합하여 Synchronization, Flow control 이나 메모리 파티션을 이용한 메모리 전달 등등 무궁무진하게 많이 쓰인다.

 

 

▶ Synchronization - Bilateral Rendezvous

 

그림16. Bilateral Rendezvous

 

  세마포어와 마찬가지로 메시지 큐로도 Task간 Synchronization 할 수 있다. 두 Task를 동기화 하는 것이 목적이고, 한 Task가 일어났다면 timeout으로 pend list에서 빠져나오지 않는 한 상대방 Task에서 Post를 해줘야 빠져나올 수 있다. 주의할 점은 Bilateral Rendezvous는 무조건 Task끼리 일어난다. 왜냐하면 ISR 내부에 Pend 함수를 집어넣으면 RTOS의 실시간성이 사라지기 때문이다. 위에서 언급했듯 ISR은 Post 함수만 실행할 수 있다. 

 

 

▷ 큐 오버플로우 

  큐도 스택과 마찬가지로 오버플로우가 일어날 수 있다. 그림14에서 왼쪽 Task가 오른쪽 Task보다 우선 순위가 높을 경우, 오른쪽 Task에서 메시지를 처리하는 속도보다 왼쪽 Task의 메시지 전송 속도가 더 빠르다. 이런 경우에 정해진 메시지 큐의 용량을 초과하게 되면 메시지가 손실되는 문제가 발생한다. 이런 경우 Counting Semaphore를 적절히 사용해서 문제를 해결할 수 있다.

 

 

▶ Flow Control

그림16. Counting Semaphore를 활용한 Flow Control

 

  앞서 Task간의 우선순위에 따라서 큐 오버플로우가 발생할 수 있다고 했고, 이를 해결하기 위한 방안으로써 세마포어를 이용할 수 있다. 카운팅 세마포어를 사용하는데, 큐의 용량의 수와 동일하게 카운터를 설정한다. 최초 큐가 빈 상태에서 왼쪽 Task가 한번 씩 실행될 때마다 OSSemPend 이후 OSQPost 한다. 

 

Producer Task: 
Pend on Semaphore; 
Send message to message queue; 

Consumer Task: 
Wait for message from message queue; 
Signal the semaphore;

 

왼쪽 Task가 Producer Task, 오른쪽 Task가 Consumer Task이다. 

 

OSSemPend 함수는 카운터 값이 0보다 클 때 카운터 값을 감소하고 빠져나올 수 있으므로 메시지 큐의 수(용량) 만큼 메시지를 작성하고 나면 더 이상 Post할 수 없다. 메시지 큐가 꽉 찼다면 더 이상 왼쪽 Task에서 큐에 메시지를 보낼 수 없는 것이다. 이때 오른쪽 Task가 실행된다면 메시지를 하나 받고 세마포어를 하나 풀어주게 된다. 

 

 

▷ Message Queue와 Memory Partition

그림17. 메시지 큐와 메모리 파티션을 이용한 에러 메시지 값 저장

 

  메모리 파티션과 Flow control를 사용한다면 그림17처럼 애플리케이션을 만들 수 있다. 메시지 큐는 포인터를 저장할 수 있는 만큼의 공간을 가지고 있다. 위 그림은 이를 사용해서 Producer Task에서는 메모리 파티션으로 부터 얻어온 주소값 안에 에러 메시지를 저장하고, 그 주소값을 메시지 큐를 통해 Consumer Task로 보내고 있다. 이때, 카운팅 세마포어를 메시지 큐의 용량만큼 설정해둔다면 에러 메시지의 손실을 막을 수 있다.

 

#  큐 구현

  주절주절 뭔가 카테고리에 맞지 않게 장황하게 설명한 기분인데, 구현을 목표로 한 OS에서도 Flow Control이나 Synchronization과 같은 요소를 많이 사용할 예정이다. 특히 Task간 통신에 유용하게 쓸 수 있는 도구로써 잘 활용해 보겠다. 앞서 설명했던 내용중에 그림15는 목표로 만들 OS가 RTOS가 아니기 때문에 언젠가 시간이 난다면 구현하게 될 것 같다. 

 

https://github.com/seyoung4503/dataStructure

GitHub - seyoung4503/dataStructure: Data Structure with C code

큐의 구현에 대한 부분은 위의 깃허브에서 확인할 수 있다.