우리 Stack과 Heap등을 살펴 보았듯이, Inter Process Communication을 제대로 하려면, Queue라는 자료구조의 개념을 잘 알아야 해요. 일단 Queue는 Stack과 달리, 먼저 넣은 놈이 꺼내면 먼저 나와요. Stack은 나중에 넣은 넘이 꺼내면 먼저 나오죠. 그래서 Queue라는 건 줄세우기인데요, 보통 FIFO라고 불려요. Software에서 사용하는 Data들은 대부분 이런 Queue라는 걸 이용해서 처리를 한답니다. 먼저 들어온 넘을 먼저 처리하는 게 순리상 정상인 게죠. Stack이 이상한 거에요. ㅋ 보통 Queue라는 건 대기행렬을 의미하는데요, 줄을 세우는 거라고 보시면 되요. 일종의 Buffer라는 의미인데요, 처리 할 녀석들을 줄 세워 놓고서 하나씩 꺼내서 처리하는 거라고 보시면 되지요. 뭐 구현방법에는 Ring buffer니 뭐니 해서 많이 있는데, 그건 자료구조 책들에게 넘기고요. IPC에 이용이 많이 되니까, 꼭 구현을 잘 찾아봐 두세요. 뭐 당연하겠지만, 이런 식인 거에요. - Stack에서는 push와 pop이라는 용어를 썼는데, Queue에서는 put과 get이라는 용어를 써요 -
Stack에서는
push (0x1);
push (0x2);
push (0x3);
pop (); /* 0x3이 나옵니다. */
pop (); /* 0x2가 나옵니다. */
pop (); /* 0x1이 나옵니다. */
이런식이었지만,
Queue에서는
put (0x1);
put (0x2);
put (0x3);
get () ; /* 0x1이 나옵니다. */
get () ; /* 0x2이 나옵니다. */
get () ; /* 0x3이 나옵니다. */
이런 식으로 먼저 들어간 넘이 먼저 나오죠. Queue를 잘 사용하는 방법에는 여러 가지가 있겠지만요, 요걸 잘 이용하면 제일 먼저 넣은 넘부터 시작해서 제일 마지막에 넣은 넘까지 순서대로 처리가능 하다는 거에욧. Queue를 구현하는 방법은 엄청나게 많아요. 배열을 이용할 수도 있고요, Linked List를 이용할 수도 있고요, 여러 가지 방법이 많은데, 여하튼 위와 같은 식으로 FIFO로 동작만 잘 하면 됩니다. ㅋ . 일단 배열을 이용한 Queue의 구현만 슬쩍 보고 넘어가시죠. 여기에서 front나, rear가 배열의 크기를 넘어 셨을 때의 예외 처리는 구찮아서 표시하지 않았으니까, 이 Code에 Bug가 있다고 항의 하시면 곤란-,.- 해요.
#define MAX 50
int Queue[MAX]; /* Queue */
int front = 0;
int rear = 0; /* Front와 Rear */
void Put(int); /* Data Put */
int Get(); /* Data Delete */
void main ()
{
Put(5);
Put(10);
Put(15);
Put(20);
Put(30);
/* 여기에서의 Queue안에 남은 결과는 5, 10, 15, 20, 30 */
Checkqueue();
ret = Get(); /* ret = 5 */
ret = Get(); /* ret = 10 */
ret = Get(); /* ret = 15 */
/* 여기에서의 Queue안에 남은 결과는 20, 30 */
Checkqueue();
ret = Get(); /* ret = 20 */
ret = Get(); /* ret = 30 */
/* 여기에서의 Queue안에 결과는 아무것도 남지 않음 */
Checkqueue();
}
void Put (int data)
{
Queue[rear++] = data;
}
int Get ()
{
int ret;
ret = Queue[Front++];
return ret;
}
void CheckQueue ()
{
int i;
for(i = Front ; i < Rear ; i++)
printf("%2d - ", Queue[i]);
}
여기에서 볼 수 있듯이, 이런 Queue는 front와 rear를 통해서 Slide Window 형식으로 Valid한 Data를 모아 놓고서 Data를 넣을 때는 rear쪽에 Data를 뺄 때는 front쪽에서 장난을 치는 형식이에요. 이런 건 overflow가 날 수 있으니까, 무한대로 쓰고 싶으면 Ring Buffer를 이용한 Queue도 많이 쓰는데, 그건 자료구조 책들 뒤져 보시면 엄청 나오니까, 일단 생략 하고요.
그리고, Linked List 요거도 잘 알아야 되는데, Linked List는 서로 다른 데이터 공간에 있어도 서로 Pointer 연결을 통해서 연결되는 자료 구조인데요, 이걸 이용하면 Pointer 연결을 통해서, 논리적인 순서를 줄 수 있는 장점이 있어요. Double Linked List를 예를 들면요,
A의 tail은 B를 가리키고요, B의 Tail은 C를 가리키고요. 이런 식으로 주르르륵 늘어 놓을 수 있고요, 역시나 반대로 B의 head는 A를 가리키고, C의 head는 B를 가리키는 형식으로 되어 있지요. 이렇게 되면 Headnode에서 주르륵 논리적 순서를 가지고 있겠죠. 순서를 줄 수 있다는 건 Queue랑 비슷한데요, Linked List는 자료를 처리할 때, insert나 delete가 아주 편리하답니다.
보시다시피원래C를가리키던 B의 tail을 E의 head에, 그리고원래 B를가리키던 C의 head를 E에연결해주시고, 나머지연결은순서에맞게재조정해주시면,
요렇게 간편하게 3분 요리로 삽입이 되는 거죠. 당연히 빼는 건 이것의 반대로 E를 빼낸 후에, B와 C의 head와 tail을 다시 맞춰주면 원상복구 되지요. 이런 Linked List는, 여러 가지 기능에 이용되는데, 그 예는 차차 보기로 하시지요. 한가지만 더 덧붙이자면, 이런 Linked List를 이용한 Queue의 구현이 RTOS Kernel에 많이 이용된다는 사실이에요. Queue를 Linked List를 이용해서 구현하게 되면, A-B-C 이런 식의 Data가 있을 때, out을 하면 계속 뒤쪽에 A-B-C-D 이런 식으로 덧붙이기가 가능하고요, 한 개의 Linked List를 더 운용하면 더 아름답게 쓸 수 있는데요. Free Queue라는 걸 두어서, A-B-C-D에서 get을 하면 A가 튀어 나올 텐데, 이 녀석을 Free Queue Linked List에 넣어 두는 거죠. Queue에 뭔가 넣고 싶을 때는 무조건 Free Queue에서 하나 get을 한 후에, 실제 Queue에다가 put을 하게 되는 형태인 거죠. 요런걸 잘 알아두면 엄청 Code를 만들거나 분석 할 때 엄청 편하다니까요.
친절한 임베디드 시스템 개발자 되기 강좌 글 전체 리스트 (링크) - 
댓글