14-3 페이지 교체와 프레임 할당
요구 페이징
프로세스를 메모리에 적재할 때, 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만 메모리에 적재하는 기법을 요구 페이징 이라고 한다. 요구 페이징의 기본적인 양상은 다음과 같다.
- CPU가 특정 페이지에 접근하는 명령어 실행
- 해당 페이지가 메모리에 있는 경우(유효비트 = 1), 해당 프레임에 접근
- 해당 페이지가 메모리에 없는 경우(유효비트 = 0), 페이지 폴트 발생
- 페이지 폴트 처리 루틴을 통해 해당 페이지는 메모리에 적재되고, 유효비트는 1로 설정
- 다시 1번을 수행
당장 실행에 필요한 페이지를 적재하려고 할 때 메모리가 가득 차있을 경우, 페이지 교체 알고리즘 을 통해 쫓아낼 페이지를 결정한다.
페이지 교체 알고리즘
좋은 페이지 교체 알고리즘이란 페이지 폴트를 가장 적게 일으키는 알고리즘이다. 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 느려지기 때문이다.
페이지 폴트 횟수 는 페이지 참조열 을 통해 알 수 있다.
페이지 참조열이란, CPU가 참조하는 페이지들 중 연속되는 페이지를 생략한 페이지열을 의미한다.
ex) { 2 2 2 3 3 3 2 3 4 4 5 6 } - 페이지 참조열 : { 2 3 2 3 4 5 6 }
(1) FIFO 페이지 교체 알고리즘
- 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
(2) 2차 기회 페이지 교체 알고리즘
- 메모리에서 가장 오래 머물렀던 페이지의 참조 비트가 1일 경우, 당장 내쫓지 않고 참조 비트를 0으로 변경하고, 적재 시간을 현재 시간으로 설정
- 오래 머문 페이지 중 참조 비트가 0인 페이지를 내쫓음
(3) 최적 페이지 교체 알고리즘
- CPU에 의해 참조되는 횟수가 적은 페이지를 내쫓는 방식
- 가장 낮은 페이지 폴트율을 보장하는 알고리즘
- 앞으로 오랫동안 사용되지 않을 페이지를 예측하는 것은 어렵기 때문에 구현하기 어려운 방식
- 운영체제에서 사용하기보다는, 다른 페이지 교체 알고리즘의 성능을 평가하기 위한 목적으로 사용됨
(4) lRU 페이지 교체 알고리즘
- 가장 오랫동안 사용하지 않은 페이지를 교체
- 페이지마다 마지막으로 사용한 시간을 토대로 함
스래싱과 프레임 할당
페이지 폴트가 자주 발생하는 이유
- 나쁜 페이지 교체 알고리즘
- 적은 프레임 수
프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제는 스래싱 이라고 한다.
멀티프로그래밍의 정도 란 메모리에서 동시 실행되는 프로세스의 수를 의미한다.
멀리프로그래밍의 정도가 늘어난다고 해서 CPU의 이용률이 그만큼 증가하는 것은 아니다. 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 빈번히 발생하고, CPU의 이용률이 떨어지기 때문이다.
운영체제는 각 프로세스를 무리없이 실행하기 위해 쵯환의 프레임 수를 파악하고, 프로세스에게 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.
프레임 할당 방식
- 균등 할당
- 모든 프로세스에게 균등하게 프레임 제공
- 비례 할당
- 프로세스 크기에 비례하여 프레임 제공
–> 프로세스의 실행 과정은 고려하지 않고, 메모리의 크기만 고려한 방식이기 때문에 정적 할당 방식 이라고도 한다. 3. 작업 집합 모델 사용
- 작업 집합 이란 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
- 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지
- CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 페이지 교체는 빈번히 발생하지 않는다
- 작업 집합의 크기만큼만 프레임을 할당하는 방식
- 페이지 폴트 빈도 사용
- 페이지 폴트율에 상한선과 하한선을 설정하여 페이지 폴트율이 상한선보다 더 높아지면 프레임을 더 할당해주고, 페이지 폴트율이 하한선보다 더 낮아지 프레임을 회수
–> 프로세스의 실행을 보고 할당할 프로임 수를 결정하기 때문에 동적 할당 방식 이라고도 한다.