Page Replacement Policy

페이지 교체 정책(Page Replacement Policy)은 가상 메모리 시스템에서 메모리가 꽉 찼을 때, 어떤 페이지를 제거하고 새 페이지를 물리 메모리에 적재할지 결정하는 방법이다. 이 정책은 시스템의 성능과 효율성에 중요한 영향을 미친다. 여러 페이지 교체 알고리즘이 있으며, 각기 다른 상황에 적합하다.

 

FIFO(Fist-In, Fist-Out)은 가장 오래 전에 메모리에 적재된 페이지를 먼저 교체한다. 구현이 간단하지만, 자주 사용되는 페이지를 교체할 위험이 있다.

page_references = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]  # 주어진 페이지 참조 시퀀스

frame_size = 3  # 프레임 크기

frames = []  # 현재 프레임 상태

page_faults = 0  # 페이지 폴트 수

fifo_table = []  # FIFO 표를 기록할 리스트

for page in page_references:

    # 페이지가 현재 프레임 내에 없으면 페이지 폴트 처리

    if page not in frames:

        page_faults += 1

        # 프레임이 가득 찼으면 가장 오래된 페이지 제거

        if len(frames) == frame_size:

            frames.pop(0)

        frames.append(page)

    # FIFO 표에 현재 프레임 상태 기록

    fifo_table.append(frames.copy())

# FIFO 표 결과와 페이지 폴트 수 반환

print(fifo_table, '페이지 폴트 수 :', page_faults)

 

#output : [[1], [1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 1], [4, 1, 2], [1, 2, 5], [1, 2, 5], [1, 2, 5], [2, 5, 3], [5, 3, 4], [5, 3, 4]] 페이지 폴트 수 : 9

 

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체한다. 최근 사용 패턴을 기반으로 효율적인 페이지 교체를 제공하지만, 구현이 복잡하다.

 

페이지 참조 시퀀스가 123412512345일 때:

1	1			예
2	1	2		예
3	1	2	3	예
4	2	3	4	예
1	3	4	1	예
2	4	1	2	예
5	1	2	5	예
1	2	5	1	예
2	5	1	2	예
3	1	2	3	예
4	2	3	4	예
5	3	4	5	예

 

LFU(Least Frequently Used)는 가장 적게 사용된 페이지를 교체한다. 사용 빈도를 기반으로 하지만, 최근 사용 패턴을 반영하지 못하는 단점이 있다.

 

NRU(Not Recently Used)는 페이지가 최근에 사용되었는지 여부를 기준으로 교체 대상을 결정한다. 각 페이지마다 참조 비트(reference bit)를 두어, 페이지가 접근되면 이 비트를 설정한다. 주기적으로 운영 체제는 이 비트를 클리어하여, 어떤 페이지가 최근에 사용되지 않았는지를 판단한다. 교체 시점에, 참조 비트가 클리어된 페이지(즉, 최근에 사용되지 않은 페이지) 중에서 교체 대상을 선택한다. NRU는 구현이 간단하고 효율적이지만, 최적의 페이지 교체를 보장하지는 않는다.

 

NFU(Not Frequently Used)는 각 페이지가 시스템 내에서 얼마나 자주 사용되었는지를 기준으로 교체 대상을 결정한다. 페이지마다 카운터를 두고, 시간이 지날 때마다 페이지가 참조되면 해당 페이지의 카운터를 증가시킨다. 교체가 필요할 때, 가장 카운터 값이 낮은 페이지(즉, 가장 자주 사용되지 않은 페이지)를 교체 대상으로 선택한다. NFU는 사용 빈도를 기반으로 하므로 시간이 지남에 따라 정확도가 높아지지만, 오랜 시간 동안 시스템에 머물렀던 페이지가 불이익을 받을 수 있다는 단점이 있다.

최적 페이지 교체 알고리즘(Optimal Page Replacement)는 미래에 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이상적인 알고리즘이지만, 실제 시스템에서는 미래의 접근 패턴을 예측할 수 없어 구현이 불가능하다.

 

Clock(Circular Queue)는 FIFO와 유사하되, 각 페이지에 사용 여부를 나타내는 플래그를 사용한다. '시계' 방식으로 순환하며, 사용되지 않은 페이지(플래그가 0인 페이지)를 찾아 교체한다. LRU의 근사 알고리즘으로, 구현이 비교적 간단하면서도 효과적이다.

 

페이지 참조 시퀀스가 123412512345일 때:

1	1			예
2	1	2		예
3	1	2	3	예
4	4	2	3	예
1	4	1	3	예
2	4	1	2	예
5	5	1	2	예
1	5	1	2	아니오
2	5	1	2	아니오
3	5	3	2	예
4	5	3	4	예
5	5	3	4	아니오

 

벨라디의 역설(Belady's Anomaly)은 페이지 교체 알고리즘에서 관찰될 수 있는 현상으로, 가상 메모리 시스템에서 물리 메모리의 프레임 수를 증가시킬 때, 예상과 달리 페이지 폴트의 수가 증가하는 상황을 말한다. 이 역설은 특히 FIFO(First-In, First-Out) 페이지 교체 알고리즘에서 두드러지게 나타난다.

 

일반적으로, 물리 메모리의 크기가 커지면 더 많은 페이지를 저장할 수 있게 되어 페이지 폴트의 수가 감소할 것으로 예상된다. 그러나 벨라디의 역설에서는 메모리 프레임의 수를 증가시키는 것이 오히려 페이지 폴트 수를 증가시킬 수 있음을 보여준다. 이 현상은 FIFO 알고리즘의 특성상, 메모리에 더 많은 페이지를 보관할 수 있게 되면서, 최근에 사용된 페이지가 아닌 오래된 페이지를 메모리에 유지하는 경향 때문에 발생한다.

 

벨라디의 역설은 모든 페이지 교체 알고리즘에서 발생하는 것은 아니다. LRU(Least Recently Used)나 OPT(Optimal Page Replacement) 같은 일부 알고리즘은 이러한 역설적인 상황을 겪지 않는다. 이 알고리즘들은 각각 최근에 가장 적게 사용된 페이지, 또는 미래에 가장 오랫동안 사용되지 않을 페이지를 교체함으로써 메모리 프레임의 수가 증가함에 따라 페이지 폴트 수가 감소하거나 최적화되는 경향을 보인다.

 

벨라디의 역설은 페이지 교체 전략을 설계하고 선택할 때 주의해야 할 중요한 이론적 관점을 제공한다. 이 역설을 통해 알 수 있는 교훈은 물리 메모리의 크기를 증가시킨다고 해서 항상 시스템의 성능이 향상되는 것은 아니라는 점이다. 따라서, 효과적인 메모리 관리 전략을 위해서는 적절한 페이지 교체 알고리즘의 선택이 중요하다.

 

교체 알고리즘이 FIFO이고 페이지 참조 시퀀스가 123412512345일 때:

 

page_references = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]  # 주어진 페이지 참조 시퀀스

frame_size = 3  # 프레임 크기

frames = []  # 현재 프레임 상태

page_faults = 0  # 페이지 폴트 수

fifo_table = []  # FIFO 표를 기록할 리스트

for page in page_references:

    # 페이지가 현재 프레임 내에 없으면 페이지 폴트 처리

    if page not in frames:

        page_faults += 1

        # 프레임이 가득 찼으면 가장 오래된 페이지 제거

        if len(frames) == frame_size:

            frames.pop(0)

        frames.append(page)

    # FIFO 표에 현재 프레임 상태 기록

    fifo_table.append(frames.copy())

# FIFO 표 결과와 페이지 폴트 수 반환

print(fifo_table, '페이지 폴트 수 :', page_faults)

 

output :

[[1], [1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 1], [4, 1, 2], [1, 2, 5], [1, 2, 5], [1, 2, 5], [2, 5, 3], [5, 3, 4], [5, 3, 4]] 페이지 폴트 수 : 9

 

프레임 크기가 3일 때, 페이지 폴트 수가 9개가 나온다. 

page_references = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]  # 주어진 페이지 참조 시퀀스

frame_size = 4  # 프레임 크기

frames = []  # 현재 프레임 상태

page_faults = 0  # 페이지 폴트 수

fifo_table = []  # FIFO 표를 기록할 리스트

for page in page_references:

    # 페이지가 현재 프레임 내에 없으면 페이지 폴트 처리

    if page not in frames:

        page_faults += 1

        # 프레임이 가득 찼으면 가장 오래된 페이지 제거

        if len(frames) == frame_size:

            frames.pop(0)

        frames.append(page)

    # FIFO 표에 현재 프레임 상태 기록

    fifo_table.append(frames.copy())

# FIFO 표 결과와 페이지 폴트 수 반환

print(fifo_table, '페이지 폴트 수 :', page_faults)

 

output : [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 1], [4, 5, 1, 2], [5, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5]] 페이지 폴트 수 : 10

 

프레임 크기를 4로 늘렸는데도 불구하고, 페이지 폴트 수가 10으로 더 늘어난 모습이다.