요구 페이징
프로세스를 메모리에 적재할 때 처음부터 모든 페이진를 적재하지 않고
필요한 페이지만 메모리에 적재하는 기법실행에 요구되는 페이지만 적재하는 기법이다.
- CPU가 특정 페이지에 접근하는 명령어를 실행한다.
- 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근
- 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.
- 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
- 다시 1번을 수행한다.
순수 요구 페이징
아무런 페이지도 메모리에 적재한지 않은채 무작정 실행부터 하는 방식
첫 명령어를 실행하는 순간 부터 페이지 폴트가 계속 발생하게 되고
실행에 필요한 페이지가 어느 정도 적재된 이후 부터는 페이지 폴트 발생 빈도가 떨어진다.
요구 페이징은 프로세스가 시작될 때 일부 페이지를 미리 메모리에 로드한다.
페이지 교체 알고리즘
메모리에 적재된 알고리즘 중 보조 기억장치로 페이지 아웃 시킬
페이지를 선택하는 알고리즘
페이지 폴트를 적게 일으키는 알고리즘일수록
더 좋은 페이지 교체 알고리즘이라고 평가한다.
용어 정리
페이지 폴트 횟수
페이지 폴트가 일어난 횟수를 의미한다.
이는페이지 참조열에서 알 수 있다.
페이지 참조열
CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미한다.
만약 CPU 가
2 2 2 3 5 5 5 3 3 7순으로 접근했다면
페이지 참조열은2 3 5 3 7이 된다.
FIFO 페이지 교체 알고리즘 - First In First Out
메모리에 가장 먼저 올라온 페이지부터 페이지 아웃하는 방식
위 사진은 페이지 교체 에서 발생한 페이지 폴트만 간주한다.
초기 페이지 폴트는 간주하지 않는다.
구현이 간단하다.
프로그램 실행 내내 사용될 페이지일 경우
메모리에 먼저 적재되어되었다고 내쫓는 것은 옳지 않다.
2차 기회 페이지 교체 알고리즘
기본적으로 FIFO 방식이다.
만약 페이지 폴트가 발생한 경우 참조비트를 확인한다.
참조 비트가 1인 경우(CPU에 접근한 적이 있는 페이지) 당장 내쫓지 않고
참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정한다.
참조 비트 = 목숨 개수
최적 페이지 교체 알고리즘 - Optimal
앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘(미래)
미리 페이지 참조를 예측할 수 없기 때문에 사실상 불가능한 알고리즘이다.
주로 다른 페이지 교체 알고리즘을 평가하기 위한 수단으로 사용된다.
LRU 페이지 교체 알고리즘 - Least Recently Used
가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘(과거)
최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 가능성이 높다는 근거하에
만들어진 알고리즘
LFU 페이지 교체 알고리즘 - Least Frequently Used
참조 횟수가 가장 작은 페이지를 교체하는 알고리즘
MFU 페이지 교체 알고리즘 - Most Frequently used
참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
이때까지 많이 사용했으니 이제 안 쓸일거라고 생각
NUR 페이지 교체 알고리즘 - Not Used Recently
최근에 사용되지 않은 페이지를 선정해서 교체하는 방식이다.
이 페이지는 참조비트(R bit)와 수정비트(M bit)로 판단한다.
페이지 폴트가 발생하면 다음 우선 순서대로 페이지를 교체한다.
R=0, M=0인 페이지(최근에 참조되지도 수정되지도 않은 페이지)R=0, M=1인 페이지(최근에 참조되지 않았지만 수정된 페이지)R=1, M=0인 페이지(최근에 참조되었지만 수정되지 않은 페이지)R=1, M=1인 페이지(최근에 참조되고 수정된 페이지)
페이지 교체 알고리즘을 구분하는 두가지 방법
Global replacement
전역 교체 알고리즘에서는 모든 프로세스의 페이지 세트에서 페이지를 교체할 수 있다.
즉, 교체할 페이지는 시스템의 전체 메모리에서 선택된다.
이 방법은 메모리를 효율적으로 사용할 수 있지만, 프로세스 간에 페이지 공유가 가능하며,
하나의 프로세스가 시스템의 전체 메모리를 점유할 가능성이 있다.
Local replacement
로컬 교체 알고리즘에서는 현재 실행 중인 프로세스의 페이지 세트에서만 페이지를 교체한다.
즉, 교체할 페이지는 현재 프로세스의 페이지 프레임에서만 선택된다.
이 방법은 각 프로세스가 메모리를 공정하게 공유할 수 있지만,
메모리 활용도는 전역 교체에 비해 상대적으로 낮을 수 있다.
스래싱(Thrashing)
페이지 폴트가 발생하는 이유는 페이지 교체 알고리즘이 안좋아서도 있지만
프로세스가 사용할 수 있는 프레임 수가 적은 것도 있다. (메모리 공간의 부재)위 그림에서 오른쪽 프레임 구성은 새로운 페이지를 참조할때마다 페이지 폴트가 발생할 것이다.
결과적으로 CPU 이용률도 떨어지고 페이지 교체에 너무 많은 시간을 쏟으면 성능에도 좋지않다.
이 처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 문제를
스래싱(Thrashing)이라고 한다.
이 그래프는 동시에 실행되는 프로세스의 수(멀티프로그래밍의 정도)를 늘린다고 해서
CPU 이용률이 비례하는 것은 아니다라는 것을 보여준다.
멀티프로그래밍 정도를 과하게 늘리면 페이지 폴트가 빈번하게 발생한다.
이에 따라 스래싱이 발생하며, CPU 이용률이 저하되고 전체적인 성능이 떨어진다.
CPU의 성능이 좋더라고 하더라도 물리 메모리의 크기가 작으면 성능이 떨어지는 것도
프레임 수가 적기 때문에 스래싱이 발생하여 성능이 떨어지는 것이다.
따라서 운영체제는 최소한의 프레임 수를 파악하고
프로세스들에게 적절하게 프레임을 할당해 줄 수 있어야 한다.
프레임 할당 방식
정적 할당 방식
프로세스의 실행과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만 고려한 방식
균등 할당 방식
모든 프로세스들에게 같은 수의 프레임을 할당하는 방식
모든 프로세스의 크기를 모두 다른데
같은 수의 프레임을 할당하는 것은 비합리적이다.
부자들에게 세금을 더 받아야된다 라는 마인드인 것 같다.
비례 할당 방식
프로세스의 크기가 크면 프레임을 많이 할당하고
프로세스의 크기가 작으면 프레임을 적게 할당하는 방식
동적 할당 방식
프로세스의 크기가 크더라도 적은 프레임을 필요로 하는 경우도 있다.
이에 따라 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지를 보고 판단하는 방식
작업 집합 모델 기반 할당 방식
프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여
빈번한 페이지 교체를 방지(스래싱 방지)하는 방식예를 들어 어떤 프로세스가 3초동안 7개의 페이지가 필요했다면 최소 7개의 프레임을 할당한다.
페이지 폴트 빈도 기반 할당 방식
페이지 폴트율에 상한선과 하한선을 정하고 이 범위 안에서만 프레임을 할당하는 방식
각 프로세스별 페이지 폴트율이 상한선보다 크다는 의미는
너무 적은 프레임을 차지하고 있다는 의미이고하한선 보다 낮다는 의미는
너무 많은 프레임을 차지하고 있다는 의미이다.
따라서 기준 구간을(상한선, 하한선)을 정하고 그 구간에서 머무를 수 있도록 해야한다.
