[Programming] FIFO Algorithm, FIFO와 QUEUE의 차이점

FIFO Algorithm

---

FIFO란 First Input First Output의 줄임말로 한국에서는 선입선출로 알려져 있다. (필자는 FIFO라고 표현할 것이다.)

FIFO는 말 그대로 제일 처음 입력된 데이터가 제일 처음으로 내보내진다라는 의미를 가지고 있다. 즉, 새로운 데이터가 저장되거나 입력되면 오래된 데이터를 내보내고 새로운 데이터가 저장되는 방식이 FIFO인 셈이다. FIFO에 대해서는 이번 포스트에서 처음 알게 된 BRO들도 있겠지만 사실 프로그래밍을 공부하다 보면 많이 접할 수 있는 기초 알고리즘 방식 중에 하나가 바로 FIFO이다. 그렇기에 어느 정도 BRO들이 대략적으로 FIFO에 대해서 알고 있지만 유의할 점이 있다. FIFO는 하나의 data structure가 아니라 data struture의 method인 것이다.

FIFO와 QUEUE는 다른 것이다.

많은 BRO들이 FIFO와 QUEUE(큐)가 동일한 것으로 생각하지만 사실상 동일한 것은 아니다. QUEUE는 Data Structure의 한 종류이고 큐에서 사용하는 방식이 바로 FIFO인 것이다. 그렇다보니 QUEUE에서 사용되는 방식이 FIFO이고, FIFO = QUEUE라고 외워서 공부하면 문제가 생긴다.  왜냐하면 큐와 FIFO를 동일시하여 생각해오다가 다른 곳에서 FIFO를 활용하여 구성했다는 내용을 보면 여기서부터가 이해가 되지 않는 멘붕에 빠지게 되기 때문이다. 이번 포스트에서는 FIFO를 사용한 큐(QUEUE)와 정보처리기사에서 출제되는 FIFO 알고리즘을 이용한 페이지 교체를 통해 FIFO에 대해서 살펴볼 것이다.

FIFO 알고리즘을 사용한 QUEUE(큐)

QUEUE는 줄이라는 사전적 의미로 FIFO 방식을 채택한 자료구조(Data Structure)이다.

(큐에 대해서 궁금한 Bro는 댓글에 남겨주거나 필자에게 따로 연락을 주면 큐에 대한 추가적인 포스트를 올리도록 하겠다.)

FIFO가 한국말로 선입선출이라고 하듯이 큐에서도 FIFO 방식이 적용되어 Front 부분에서는 삭제(Delete)가 이루어지며 반대쪽인 Rear부분에서는 삽입(Insert)가 이루어진다. QUEUE(큐)에서 Input 되는 과정을 Enqueue라고 하며, Output 되는 과정을 Dequeue라고 하며, 아래의 그림을 통해 쉽게 이해할 수 있다.

Enqueue

 

Dequeue

따라서 FIFO 알고리즘을 이용한 큐의 경우에는 유통기한이 정해져 있는 상품에 대한 재고 관리를 할때도 사용할 수 있으며, 은행에서 대기표를 받고 기다리는 과정 역시 QUEUE를 활용해서 프로그래밍이 가능하다. 

FIFO 알고리즘 페이지 교체

정보처리기사에서 출제되는 페이지 교체에서도 FIFO 알고리즘을 활용하고 있다. 오래된 데이터가 내보내지고 새로운 데이터가 들어온다는 점에서는 큐 부분과 동일하지만 방법에 있어서는 조금 다르다. 페이지 교체는 Page Faults(페이지 부재)가 발생했을 때 어떤 방법으로 대처를 할 것인지에 대해서 결정하는 방법이다. 페이지 교체 방법은 어떤 알고리즘을 선택해서 적용하느냐에 따라 다르며, 이번 포스트에서는 FIFO 기법을 적용한 페이지 교체 방법을 살펴보도록 하겠다.

FIFO 알고리즘을 사용한 페이지 교체는 기존에 없던 새로운 페이지가 들어왔을때 가장 오래된 페이지를 교체하는 방법이다. 그렇다 보니 모든 페이지가 주기억장치에서 저장될 때마다 얼마나 저장되어 있었는지를 기억해야 한다. 큐와 차이점은 이 부분에 있는데, 큐는 줄로 표기되어 첫 번째 부분이 삭제되고 뒤에 부분에 새로운 데이터가 삽입되는 반면에 FIFO 알고리즘을 사용한 페이지 교체에서는 오래된 페이지가 삭제되고 오래된 페이지가 있었던 곳에 새로운 페이지로 교체된다. 아래의 그림을 살펴보면 이해하기가 수월하다.

FIFO 알고리즘 페이지 교체

 

In Conclusion,

결과적으로 FIFO는 하나의 특정한 Data Structure가 아닌 알고리즘 또는 Method이다. 따라서 FIFO의 특징을 활용해서 다양한 곳에서 사용될 수 있다는 점을 유의하여 기억해야 한다.