[Algorithms] Replacement Algorithms: FIFO

Replacement Algorithms: FIFO

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# Replacement algorithms

컴퓨터 메모리를 관리하는 과정에서 새로운 page를 저장해야 한다고 했을 때 기존에 있던 page와 교체하여 stack 되어야 한다.

이 과정에서 우리는 어떤 방식으로 Page를 저장하여 메모리를 효율적으로 사용할 지에 대해서 컴퓨터에게 알려주어야 한다.

이때 필요한 것이 바로 Replacement algorithms 또는 Page replacement algorithms이라고 부른다.

---

# FIFO

알고리즘의 기초이자 개발자라면 누구나 알고 있는 대표적인 알고리즘이 FIFO(First in Frist out)이다.

FIFO에 대한 구체적인 설명은 생략하고 페이지 교체 알고리즘 관점에서 FIFO를 살펴보도록 하자.

FIFO의 경우가 대표적인 replacement algorithms이다.

FIFO는 First in frist out이라는 의미답게 가장 오래된 페이지를 새로운 페이지로 교체하는 알고리즘이다.

그렇다 보니 제일 먼저 Stack 된 페이지와 새로운 페이지를 교체할 뿐 다른 조건은 포함되지 않는다.

예를 들어, 제일 오래된 페이지가 지속적으로 자주 사용이 되더라도 제일 오래된 페이지라면 교체되어 버릴 뿐이다.

그렇다 보니 효율성 면에서는 Optimal이나 LRU 알고리즘보다는 떨어질 수 있다.

다만 FIFO가 대표적인 교체 알고리즘이라고 하는 이유는 가장 오랫동안 사용되어 왔으면서 간단하게 이루어진 알고리즘이기 때문이다.

다른 알고리즘들에 비해 작동 방식이 매우 Simple하기 때문에 구현하는 과정도 어렵지 않다.

여기서 유의할 점은 제일 오래된 페이지와 새로운 페이지가 교체될 뿐 오랫동안 사용 안된 페이지가 교체되는 건 아니라는 것이다.

---

# FIFO Example

페이지 교체가 되는 FIFO 예시를 살펴보도록 하자.

이번 FIFO 예제에서는 set 2개 만을 사용하여 살펴볼 예정이다.

set이 많아지게 되면 그만큼 나눠지는 경우가 많아지고 교체되는 경우가 줄어든다.

예제에서는 메모리가 16이지만 table은 6개로만 작성하였다.

실제로 할때는 16개로 만들어줘야 한다.

#Conditions
Suppose that
Memory: 16
Cache : 8
Mapping: 4 way set

#Examples
7,2,8,5,7,9,0,8,2,1,14,3,6,12,10

예제에서 주어진 조건을 토대로 FIFO 알고리즘으로 페이지를 교체해줄 예정이다.

또한 4개 set씩 2개의 set으로 구분하여 페이지를 Stack 해줄 것이다.

우선은 새롭게 교체해줄 페이지가 나올 때까지 반복 작업을 해주면 아래와 같은 결과가 도출된다.

2
8
0
14
7
5
9
1

# Examples
7,2,8,5,7,9,0,8,2,1,14, 3,6,12,10
M,M,M,M,H,M,M,H,H,M,M ,

14까지는 교체될 페이지가 없기 때문에 위와 같은 결과가 나온다.

M은 Miss를 나타내고 H는 Hit을 나타낸다.

Miss는 기존에 없던 페이지를 Stack했다는 의미이며 H는 기존에 해당 페이지가 있기에 Hit이라고 표현한다.

한마디로 페이지 교체 없이 반복 작업이 되면 효율성을 높일 수 있다.

그럼 이제 페이지 교체가 이루어지는 부분을 살펴보도록 하자.

2	6
8	8
0	0
14	14
7	3
5	5
9	9
1	1

# Examples
7,2,8,5,7,9,0,8,2,1,14,3,6, 12,10
M,M,M,M,H,M,M,H,H,M,M ,M,M,

위의 테이블에서 보면, 3과 6이 페이지 교체가 이루어졌음을 알 수 있다.

따라서 3과 6도 M이며, 기존에 다른 페이지는 그대로 Stack 되어 있다.

Set을 0과 1로 나누어졌기 때문에 3과 6은 같은 Memory block 라인에 있을 수 있다.

이제 12와 10을 살펴보도록 하자.

2	6	6	6
8	8	12	12
0	0	0	10
14	14	14	14
7	3
5	5
9	9
1	1

# Examples
7,2,8,5,7,9,0,8,2,1,14,3,6,12,10
M,M,M,M,H,M,M,H,H,M,M ,M,M,M ,M

12의 경우 첫번째 6은 교체되었기 때문에 2번째 오래된 8과 교체가 이루어진다.

10의 경우는 세번째 오래된 0과 교체가 이루어진다.

12와 10은 같은 set이기 때문에 두 번의 계산 과정이 이루어진다.

 

---