📑 본 글은 반효경 교수님의 운영체제 강의를 듣고 정리한 글입니다.
요구 페이징
프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
유효-무효 비트를 사용한다
- 무효(invalid)란?
- 사용되지 않는 주소 영역인 경우
- 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 페이지의 유효-무효 비트가 무효 값으로 초기화된다.
- 특정 페이지가 참조되어 메모리에 적재되는 경우 해당 페이지의 유효-무효 비트가 유효 값으로 바뀐다.
- CPU 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재라고 한다.
요구 페이징의 페이지 부재 처리
- CPU가 무효 페이지에 접근하면 MMU가 trap을 발생한다. (page fault trap)
- CPU의 제어권이 커널 모드로 전환되고, 페이지 부재 처리 루틴이 호출되면서 다음과 같은 순서로 페이지 부재를 처리한다.
요구 페이징의 성능
- 페이지 부재의 발생 빈도가 성능에 가장 큰 영향을 미친다.
- 유효 접근 시간(요청한 페이지를 참조하는 데 걸리는 시간)
- (1 - P) x 메모리 접근 시간 + P x M
- 페이지 부재 발생 비율(P) → 0 ≤ P ≤ 1
- M (각종 오버헤드)
페이지 교체
페이지 부재가 발생하여 요청된 페이지를 디스크에서 메모리로 읽어오려고 하는데, 물리적 메모리에 빈 프레임이 없을 수 있다.
이 때 이미 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는데, 어떠한 페이지를 교체할지 결정하는 것을 페이지 교체라고 한다.
페이지 교체 알고리즘
- 페이지 교체를 할 때에 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 페이지 교체 알고리즘이라고 한다.
최적 페이지 교체 (Optimal Algorithm)
물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 알고리즘이다.
미래의 참조를 알아야 하므로 오프라인에서만 사용된다.
다른 알고리즘의 성능에 대한 상한선(upper bound)을 제공한다.
선입 선출 알고리즘 (FIFO Algorithm)
물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 알고리즘이다.
메모리를 증가하였음에도 페이지 부재가 오히려 늘어나는 현상(FIFO의 이상 현상)이 발생할 수 있다.
LRU (Least Recently Used) 알고리즘
가장 오래 전에 참조가 이루어진 페이지를 쫓아내는 알고리즘이다.
LFU (Least Frequently Used) 알고리즘
페이지의 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
장점
- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 페이지의 인기도를 좀 더 정확히 반영할 수 있다.
단점
- 참조 시점의 최근성을 반영하지 못한다.
- LRU보다 구현이 복잡하다.
클럭 알고리즘 (Clock Algorithm)
LRU의 근사 알고리즘이다.
- Second chance algorithm, NUR(Not Used Recently), NRU (Not Recently Used) 등으로 불린다.
- 참조 비트를 사용하여 교체 대상 페이지를 선정한다. (circular list)
- 참조 비트를 수정하는 작업은 OS가 아닌, 하드웨어가 수행한다.
- 참조 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.
페이지 프레임의 할당
각 프로세스에 얼마 만큼의 페이지 프레임을 할당할 것인가?
페이지 프레임 할당 알고리즘
- 균등 할당(Equal Allocation): 모든 프로세스에게 페이지 프레임을 균일하게 할당
- 비례 할당(Proportional Allocation): 프로세스의 크기에 따라 페이지 프레임을 비례하여 할당
- 우선순위 할당(Priority Allocation): 프로세스의 우선순위에 따라 페이지 프레임을 할당
전역 교체와 지역 교체
전역 교체
- 모든 페이지 프레임이 교체 대상이 될 수 있는 방법이다.
- 전체 메모리를 각 프로세스가 공유해서 사용하고, 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.
- FIFO, LRU, LFU 등의 알고리즘을 전역 교체로 사용할 수 있다.
지역 교체
- 자신에게 할당된 페이지 프레임 내에서만 교체한다.
- FIFO, LRU, LFU 등의 알고리즘을 지역 교체로 사용할 수 있다.
워킹셋 (Working-Set) 알고리즘
워킹셋 모델 (Working-Set Model)
참조의 지역성
- 프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다.
- 집중적으로 참조되는 해당 페이지의 집합을 지역셋(locality set)이라고 한다.
워킹셋 모델
- 지역성에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지의 집합을 워킹셋이라고 정의한다.
- 워킹셋 모델에서는 프로세스의 워킹셋 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 페이지 프레임을 반납 한 후 swap out한다. 해당 프로세스는 suspend 상태가 된다.
워킹셋 알고리즘
알고리즘 동작 과정
프로세스의 워킹셋 사이즈의 합이 페이지의 프레임 수보다 큰 경우
- 일부 프로세스를 swap out한 뒤, 남은 프로세스의 워킹셋을 우선적으로 충족하여 MPD를 줄인다.
워킹셋을 다 할당하고도 페이지 프레임이 남는 경우
- swap out되었던 프로세스에게 워킹셋을 할당하여 MPD를 높인다.
가상 메모리를 사용하는 이유
-
메모리에 확장성을 부여한다.
- 물리 메모리는 한정적이지만, 가상 메모리는 큰 공간으로 구성이 가능하다.
- 가상 메모리를 사용하면 실제 메인 메모리 장치가 아닌, 디스크를 부가적인 메모리 공간으로 활용할 수 있다.
-
모든 프로그램에 동일한 메모리 공간을 제공해 줄 수 있다.
- 개발자 입장에서 물리적 메모리가 아닌 OS가 제공하는 메모리 공간만 신경 쓰면 된다.
- 운영 체제가 동작하는 환경에서는 여러 가지 프로그램이 동시에 실행되므로 메모리 공간에 대한 관리가 필요하다.
-
메모리 할당과 관리에 효율적이다.
- 물리적으로 연속되지 않은 메모리라도 가상으로 연속적인 메모리 공간으로 사용이 가능하다.
-
메모리 보호 기능을 제공한다.
- 보안이나 안정성 측면에서 매우 중요한 기능이다.
- 각각의 프로세스는 별도의 메모리 공간을 점유하며, 다른 프로세스의 메모리 공간을 참조할 수 없다.
가상 메모리의 중요성
시스템에서 특정 애플리케이션이나 프로세스가 현재 가용한 물리 메모리보다 많은 양의 메모리를 요청할 수 있다.
이때 커널은 적은 빈도로 사용되는 메모리 페이지를 스왑 아웃해서 가용 메모리 공간을 확보한 뒤 이를 해당 프로세스에게 할당해 줌으로써 프로세스 실행이 가능하게 한다.
애플리케이션이 실행되기 시작할 때 초기화를 위해서만 필요하고 이후에는 사용되지 않는 메모리 페이지들은 시스템에 의해 스왑 아웃된다.
이로 인해 가용 가능한 메모리 공간은 다른 애플리케이션이나 디스크 캐시 용도로 활용된다.
