[OS] 페이지 교체 정책

운영체제에서 가상 메모리를 관리할 때, 물리 메모리(RAM)의 공간이 부족해지면 새로운 페이지를 가져오기 위해 기존에 있던 페이지를 몰아내야 합니다. 어떤 페이지를 몰아낼지 결정하는 알고리즘을 바로 페이지 교체 정책이라고 합니다.

각 정책은 페이지의 참조 기록을 기반으로 미래의 페이지 참조를 예측하여 페이지 교체 횟수를 최소화하는 것을 목표로 합니다.

페이지 폴트 발생: 프로세스가 실행 중에 참조하려는 페이지가 메모리에 없는 경우 페이지 폴트가 발생합니다.
교체 대상 선정: 페이지 교체 정책에 따라 교체 대상 페이지를 선정합니다.
페이지 교체: 선정된 페이지를 디스크로 내보내고(swapping out), 필요한 페이지를 디스크에서 가져와(swapping in) 메모리에 적재합니다.
프로세스 재개: 페이지 교체가 완료되면 프로세스의 실행을 재개합니다.

원리: 가장 먼저 메모리에 들어온 페이지를 가장 먼저 몰아내는 방식
특징: 구현이 간단하지만, 가장 오래된 페이지가 가장 자주 사용되는 페이지일 수도 있다는 단점이 있습니다.
Belady의 모순: 메모리 공간이 증가해도 페이지 교체 횟수가 증가하는 현상이 발생할 수 있습니다.
- 현재 메모리에 있는 페이지가 미래에 얼마나 중요하게 쓰일지를 전혀 고려하지 않기 때문에 발생
- LRU나 OPT 같은 알고리즘은 '스택 특성'을 가지고 있어 메모리가 늘어나면 성능이 무조건 같거나 좋아지지만, FIFO는 이 특성이 없어서 모순이 발생

참조 번호	7	0	1	2	0	3	0	4	2	3	0	3
프레임 1	7	7	7	2	2	2	2	4	4	4	0	0
프레임 2		0	0	0	0	3	3	3	2	2	2	2
프레임 3			1	1	1	1	0	0	0	3	3	3
상태	PF	PF	PF	PF	H	PF	PF	PF	PF	PF	PF	H

총 페이지 폴트: 10회

참조 번호	7	0	1	2	0	3	0	4	2	3	0	3
프레임 1	7	7	7	2	2	2	2	4	4	4	0	0
프레임 2		0	0	0	0	3	3	3	2	2	2	2
프레임 3			1	1	1	1	0	0	0	3	3	3
상태	PF	PF	PF	PF	H	PF	H	PF	PF	PF	PF	H

총 페이지 폴트: 9회

페이지가 참조될 때마다 시간을 기록하거나 순서를 바꿔줘야 하므로 FIFO보다 구현 비용이 큽니다.

원리: 참조 횟수가 가장 적은 페이지를 몰아내는 방식
특징: 자주 사용되는 페이지는 메모리에 유지될 가능성이 높지만, 참조 횟수가 초기에는 많았지만 나중에는 적어지는 페이지가 메모리에 계속 남아있을 수 있다는 단점이 있습니다.

참조 번호	7	0	1	2	0	3	0	4	2	3	0	3
프레임 1	7(1)	7(1)	7(1)	2(1)	2(1)	2(1)	2(1)	4(1)	2(2)	2(2)	2(2)	2(2)
프레임 2		0(1)	0(1)	0(1)	0(2)	0(2)	0(3)	0(3)	0(3)	0(3)	0(4)	0(4)
프레임 3			1(1)	1(1)	1(1)	3(1)	3(1)	3(1)	3(1)	3(2)	3(2)	3(3)
상태	PF	PF	PF	PF	H	PF	H	PF	PF	PF	H	H

총 페이지 폴트: 8회

장점: 자주 쓰이는 페이지를 확실하게 보존합니다.

단점: 초반에만 아주 많이 쓰이고 더 이상 안 쓰이는 페이지가 메모리를 계속 차지할 수 있습니다.

원리: 미래에 가장 오랫동안 사용되지 않을 페이지를 몰아내는 방식
특징: 이론적으로 가장 효율적인 방식이지만, 미래의 페이지 참조를 예측할 수 없기 때문에 실제로는 구현이 불가능합니다. 하지만 다른 알고리즘의 성능을 평가하는 기준으로 사용됩니다.

참조 번호	7	0	1	2	0	3	0	4	2	3	0	3
프레임 1	7	7	7	2	2	2	2	2	2	2	2	2
프레임 2		0	0	0	0	0	0	4	4	4	0	0
프레임 3			1	1	1	3	3	3	3	3	3	3
상태	PF	PF	PF	PF	H	PF	H	PF	H	H	PF	H

총 페이지 폴트: 7회

티스토리툴바