큐의 정의 - FIFO ( First In, First Out )
- 1. 자료의 추가는 뒤(rear)에서, 자료의 삭제는 앞(front)에서
리스트형 자료구조의 특별한 예라고 생각하면 된다.
자료구조의 양쪽 끝에서만 추가, 삭제 동작이 가능.
자료구조의 중간에서는 추가나 삭제, 읽기가 불가.
한쪽끝에서는 추가만, 다른 한쪽 끝에서는 삭제만으로 구별된 동작.
위 구별된 동작은 동시발생 가능.
- 2. 선입선출(FIFO)
이벤트가 발생한 순서대로 줄을 세우는 구조(쉽게 말해 선착순)
이후 줄의 맨 앞에서부터 줄의 끝까지 순서대로 하나씩 꺼내 쓰는 구조
결과적으로 자료구조에 도착한 순서대로 꺼내가는 것을 보장
- 3. LILO(Last in Last out)이라고도 불림.
주변의 예로, 은행창구의 번호표나 프린터의 인쇄물 출력 등을 꼽을 수 있다.
stream적인 특성을 갖고, 일정 시간동안 일정한 처리량을 보장한다.
큐는 일정한 공간이 있음!
큐의 응용 사례
큐를 응용한 사례로는 크게 스케쥴러와 메시지 시스템을 들 수 있다.
- 1. 운영체제의 스케쥴러
자원의 할당과 회수를 하는 스케쥴러 역할을 큐가 할 수 있다.
자원관리자의 역할로써, 운영체제의 첫번째 목적이라고도 할 수 있다.
메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가,
그 순서를 결정하는 것이 자원의 효율적인 사용에 있고,
가장 단순한 형태의 스케쥴링 정책이 선입선처리(first come first served), 즉 큐라고 볼 수 있겠다.
- 2. 메시징 시스템
윈도우 운영체제에서 동작하는 어플리케이션(이하 앱)들은 메시지를 기반으로 한다.
키보드, 마우스 등의 입력 신호 또한 메시지이고, 이 또한 시스템 큐로 입력되어 처리를 기다린다.
생각해보면 우리가 키보드로 타이핑하는 글자 순서대로 입력처리가 되지 않는가?
FIFO의 쉬운 예라고 할 수 있겠다.
앱 또한 자신만의 메세지 저장소로 앱큐를 하나씩 갖는다.
언급한 시스템큐, 앱큐 들은 메시지를 생산하고 소비하는 주체가 다르고,
서로 방해받지 않기 위해 메시지를 투입하고 꺼내 쓰는 방향을 구별한다.
이때, 메세지의 전달자 역할을 큐가 할 수 있고, 이 때의 큐를 버퍼(Buffer)라고 한다.
흔히 우리가 동영상 끊길때 버퍼링 얘기가 이때 나오는 얘기가 아닌가 싶다.
여러 대의 컴퓨터에서 분산 동작하는 메시징 시스템으로 카프카(Kafka)가 있다고 한다.
큐의 설계 요구사항
- <요구사항 분석>
수집 , 도출된 요구사항이 타당한지 , 다른 요구사항과 상충하는지 등 검토
기술적인 난제는 없는지 구현 가능한 방법은 있는지를 따짐
기능적인 관점과 더불어 성능 , 안정성 , 보안 , 준법 등의 문제는 없는지 조사
- <요구사항 도출>
자료의 개수가 한정된 리스트이고, 추가/삭제가 양 끝에서 독립적으로 발생한다.
리스트에 자료가 가득 차면 추가가 불가능하고, 비어있을때는 삭제가 불가능할것이다.
리스트에 먼저 추가된 자료가 먼저 삭제되어야 할 것이다.
- <요구사항 결과>
순차자료구조인 배열을 응용해 요구사항을 구현가능.
배열의 첨자를 통해 자료의 추가/삭제 위치 제어해야할것.
연결자료구조인 연결리스트를 응용해 역시 요구사항 구현가능.
데이터 노드의 링크필드를 이용해야 할것.
자료노드의 개수는 양의 정수로, OOM(out of memory)가 발생하지 않도록 개수를 한정해야 할 것이고,
배열과 연결리스트의 성능은 비교 시험이 필요할 것이다.
마지막으로, FIFO의 구현을 위해 자료에 대한 임의접근을 통제해야 할 것이다.
한양대학교 빅데이터융합학과 김경환 교수님의 강의 내용을 발췌하였음을 알립니다.