[OS/운영체제] 페이지 교체 (Page Replacement) - (1)

페이지 교체 (Page Replacement)

페이지 결함률(Page Fault rate)에 대해 언급할 때, 우리는 각 페이지 결함이 최대 한 번, 그 페이지가 참조되었을 때 발생한다고 가정했지만 이는 엄격히 말해서는 정확하지 않은 표현이다.

만약 열 개의 페이지를 가진 프로세스가 실제로는 그 중 절반을 사용한다면, 요구 페이징은 사용되지 않을 5개의 페이지를 적재하는 데 필요한 입출력을 저장해야 한다. 만약 40개의 프레임이 존재한다면, 실제로는 해당 프로세스를 8개까지 실행시킬 수 있지만 4개밖에 실행시키지 못하는 것이다.

우리는 멀티프로그래밍의 정도를 높이고자 할 때, 메모리를 초과 할당(Over-Allocating)한다. 현재 페이지 10개 크기이지만 실제로는 5개의 페이지만 사용하고 있는 6개의 프로세스가 돌아가고 있다면, 각 프로세스당 5개의 프레임만을 사용하도록 하고(총 30개), 나머지 10개의 프레임으로 높은 CPU 사용률과 Thoughput을 얻을 수 있을 것이다.

하지만 이 프로세스들이 갑자기 10개의 페이지 모두를 사용하고 싶어 한다면, 총 40개의 프레임이 존재하지만 60개의 프레임이 필요하게 된다. 거기다 시스템 메모리는 프로그램에 사용되는 페이지 뿐만 아니라 입출력을 위한 버퍼 또한 상당한 양의 메모리를 차지한다.

페이지 교체의 필요성

사용자 프로세스가 실행되는 동안, 페이지 결함이 발생한다. 그림에서 운영체제는 디스크에서 요구되는 페이지를 찾았지만, 그 페이지에 대해 빈 프레임을 찾으려 하니 현재 모든 프레임이 사용 중인 상태이다. 이 시점에서 운영체제에게는 몇 가지 선택지가 있다.

우선 해당 사용자의 프로세스를 종료시킬 수 있을 것이다. 하지만 요구 페이징은 운영체제의 시스템 사용률을 향상시키기 위한 목적을 갖고 있다. 사용자들은 자신들의 프로세스가 페이징 시스템에서 돌아가고 있음을 몰라야 한다. 따라서 이는 최선의 선택이 아니다.

또 다른 방법은운영체제는 프로세스를 교체함으로써 멀티프로그래밍의 수준을 조금 포기하고(낮추고) 모든 프레임을 자유롭게 하는 것이다. 이는 특정 상황에서 좋은 선택지이며, 이 중 가장 일반적인 해결책인 페이지 교체에 대해 설명한다.

 

Basic Page Replacement

페이지 교체는 만약 빈 프레임이 존재하지 않는다면, 현재 사용 중인 프레임을 찾아 비우는(free) 것이다. 우리는 프레임의 내용을 swap space에 쓰고, 프레임에 해당하는 페이지가 더 이상 메모리에 존재하지 않도록 페이지 테이블(과 다른 테이블 모두)을 갱신하여 프레임을 비울 수 있다. 

이렇게 비워진 프레임은 페이지 결함이 발생한 다른 프로세스가 사용하도록 할 수 있다. 페이지 결함이 발생했을 때, 페이지 교체 방식이 포함된 과정은 다음과 같다.

페이지 교체

① 디스크에서 원하는 페이지를 찾는다.

② 빈 프레임을 찾는다.

 - 만약 빈 프레임이 존재한다면, 그것을 사용한다.

 - 만약 빈 프레임이 존재하지 않는다면, 페이지 교체 알고리즘을 통해 Victim Frame을 선택한다.

 - Victim Frame의 내용을 디스크에 쓰고, 그에 따라 페이지, 프레임 테이블을 수정한다. (그림의 1, 2번에 해당)

③ 원하는 페이지를 새로 비운 프레임에 올린다. 그에 따라 페이지, 프레임 테이블을 수정한다. (그림의 3, 4번에 해당)

④ 페이지 결함이 발생한 프로세스를 다시 시작한다.

 

만약 빈 프레임이 존재하지 않는다면, 두 개의 페이지(in, out) 전송이 필요하다. 이는 페이지 결함의 해결 시간을 증가시키고, 따라서 유효 접근 시간 또한 증가하게 된다.

이러한 오버헤드를 감소시키기 위해 Modify bit(또는, Dirty bit)을 사용한다. 이 기법을 사용하면 각 페이지나 프레임은 하드웨어에 Modify bit을 갖게 되는데, 하드웨어에 의해 설정된 페이지의 Modify bit은 그 페이지가 수정되었음을 나타낸다.

교체를 위한 페이지(Victim Page)를 선택했을 때, 그 페이지의 Modify bit을 확인한다. 만약 bit가 설정되어 있다면(true), 그 페이지는 디스크로부터 읽힌 후 수정되었음을 알 수 있다. 이 때는 반드시 그 페이지를 디스크에 써야 한다. (수정된 내용을 저장하기 위해) 만약 bit가 설정되어 있지 않다면(false), 디스크에서 읽힌 후 수정되지 않은 페이지임을 의미하므로 디스크에 그 페이지를 쓸 필요가 없다.

단, 디스크에 페이지의 복사본이 없다면 변경 여부와 상관없이 디스크에 써야 한다. 또한, 읽기 전용 페이지는 디스크로 다시 옮길 필요가 없다. (can discard)

 

Frame-Allocation Algorithm : 한 프로세스에 할당할 프레임의 수를 결정하는 알고리즘

Page-Replacement Algorithm : 빈 프레임이 존재하지 않을 때, Victim Frame을 선택하는 알고리즘

참조 문자열(Reference String) : 페이지 교체 알고리즘을 평가할 때, 어떠한 메인 메모리 참조들에 대해 페이지 결함 수를 계산하여 그 수를 비교한다. 이 때, 일련의 메인 메모리의 참조를 참조 문자열이라 한다.

참조 문자열 7, 0, 1, 2, 0, 3, 0은 이 번호 순서대로 페이지를 참조했다는 의미이다. (번호는 참조되는 페이지 번호)

 

 

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.