8장 가상메모리
서론
프로그램이 실행되려면 필요한 부분이 메모리에 적재되어야 한다.
현대의 시분할 환경에서는 모든 프로그램이 올라갈 수는 없으므로 어떤 프로그램에게 어느 정도의 메모리를 할당할 것인지에 대한 문제가 발생한다.
운영체제는 몇몇 프로그램들에게 집중적으로 메모리를 할당한 후, 시간이 흐른 뒤 회수하여 다른 프로그램들에게 다시 집중적으로 할당해준다.
왜냐하면, 프로세스의 빠른 수행을 위해 프로그램마다 최소한 확보해야 하는 메모리의 크기가 존재하기 때문이다.
프로세스의 주소 공간을 메모리에 적재하는 단위에 따라 가상메모리 기법은 요구 페이징(demand paging) 방식과 요구 세그멘테이션(demand segmentation) 방식으로 구분한다.
대부분의 경우 요구 페이징 기법을 사용하며, 요구 세그멘테이션 방식은 페이지드 세그멘테이션 기법을 사용하는 경우에만 사용한다.
요구 페이징
프로그램 실행 시 CPU가 요청하는, 당장 필요한 페이지만 메모리에 적재하는 방식이다.
나머지 페이지들은 디스크의 스왑 영역에 존재하게 되며, 어떤 페이지가 메모리에 존재하고 스왑 영역에 존재하는지 구분하기 위해서 요구 페이징에서는 유효-무효 비트(valid-invalid bit)를 두어 각 페이지가 메모리에 존재하는지 표시한다.
프로세스 실행 전에는 값이 무효로 되어있으며, 특정 페이지가 참조되어 메모리에 적재되면 유효로 바뀌고 다시 스왑 영역으로 쫒겨나면 무효로 바뀐다.
여기서 값이 무효인 경우는 페이지가 현재 메모리에 없는 경우일 수 있지만 경우에 따라서는 그 페이지가 속한 주소 영역을 프로세스가 사용하지 않는 경우도 있다.
CPU가 참조하려는 페이지가 현재 메모리에 적재되어 있지 않아 비트값이 무효인 경우를 페이지 부재(page fault) 라고 한다.
페이지 부재를 처리하는 방식은 다음과 같다.
CPU가 무효 페이지에 접근하면 하드웨어인 MMU(논리적 주소를 물리적 주소로 매핑하는 하드웨어 장치)가 페이지 부재 트랩을 발동시킨다.
CPU 제어권이 커널로 넘어가고 페이지 부재 처리루틴이 호출되어 처리한다.
즉, 부재 상태의 페이지를 메모리에 적재하기 전에 운영체제가 해당 페이지에 대한 접근이 적법한지 먼저 체크한다.
적법하다면 물리적 메모리의 비어있는 프레임을 할당받아 그 공간에 해당 페이지를 읽어온다.
메모리가 부족하다면 기존에 메모리에 있던 페이지 중 하나를 스왑아웃시킨다.
요청된 페이지를 디스크로부터 메모리로 적재하기까지는 오래걸리므로 페이지 부재를 발생시킨 프로세스는 봉쇄상태가 된다.
즉, 문맥교환으로 인한 오버헤드가 발생한다.
요구 페이징 기법의 성능은 페이지 부재의 발생 빈도에 따라 결정되며, 요청한 페이지를 참조하는데 걸리는 유효 접근시간으로 측정한다.
유효 접근시간은 오버헤드가 많을수록 값이 커진다.
위에 써있듯이 페이지 부재가 일어나 봉쇄상태가 되면 문맥교환이 발생하므로 많은 오버헤드가 필요하게 된다.
발생하는 오버헤드에는 페이지 부재 발생 처리 오버헤드, 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드, 요청된 페이지의 스왑 인 오버헤드, 프로세스의 재시작 오버헤드가 있다.
유효 접근시간이 짧을수록 요구 페이징 기법의 성능은 향상된다.
페이지 교체
페이지 교체는 한 마디로 스왑아웃 시키는 과정이라고 보면 된다.
빈 프레임이 없다면 현재 메모리에 있는 페이지 중 하나를 골라서 디스크로 스왑아웃 시킨 뒤 필요한 페이지를 적재해야 한다.
이 과정을 페이지 교체(page replacement)라 하며, 페이지 교체에서 사용하는 교체 알고리즘의 목표는 페이지 부재율 최소화 하는 것이다.
따라서 가까운 미래에 참조될 가능성이 가장 적은 페이지를 내쫒아야 한다.
그러한 페이지를 결정하는 알고리즘은 다음과 같다.
대부분의 시스템에서는 클럭 알고리즘을 교체 알고리즘으로 채택한다.
- 최적 페이지 교체
- 빌레디의 최적 알고리즘
- 위에서 말한대로 가까운 미래에 참조될 가능성이 가장 적은 페이지를 쫒아내는 알고리즘
- 이 알고리즘은 전제가 미래에 어떤 페이지가 참조될지 미리 알고있어야 한다
- 따라서 이 알고리즘을 오프라인 알고리즘이라 한다.
- 실제 시스템에서 사용은 불가하며, 어느 알고리즘보다 페이지 부재율이 가장 적음을 보장하는 알고리즘으로 다른 알고리즘들의 상한선을 제공한다.
- 이 알고리즘과 비슷한 페이지 부재율을 가지는 알고리즘이 나온다면 더 이상 그 시스템을 위한 교체 알고리즘을 연구할 필요가 없음을 시사한다.
- 선입선출
- 빈 프레임이 없다면 들어온 순서대로 스왑아웃 시키는 알고리즘
- 들어온 순서대로 선정하기 때문에 비효율적인 상황이 발생할 수 있다.
- 물리적 메모리 공간 (프레임 개수)가 늘어나더라도 오히려 성능이 나빠지는 경우가 발생할 수 있다.
- FIFO 알고리즘에서 메모리를 증가시켰음에도 불구하고 페이지 부재가 늘어나는 상황을 FIFO 이상 현상 (FIFO anomaly)라고 부른다.
- LRU 알고리즘에서는 FIFO anomaly 현상이 발생하지 않는다.
- LRU 알고리즘 (Least Recently Used)
- 페이지 교체 시 가장 오래전에 참조된 페이지를 내쫒는 알고리즘
- 즉, 마지막 참조 시점이 가장 오래된 페이지를 교체하는 것이다.
- LFU 알고리즘 (Least Frequently Used)
- 현재 적재된 페이지 중 페이지의 이전까지의 참조 횟수가 가장 적은 페이지를 내쫒는 알고리즘
- 최저 참조 횟수가 같은 페이지가 있다면 그 중 하나를 선택, 효율적으로 구현하려면 그 중에서도 오래전에 참조된 페이지를 쫒아낸다.
- 참조 횟수를 계산하는 방식에 따라 구분,
Incache-LFU,Perfect-LFU로 구분한다.Incache-LFU는 물리적 메모리에 올라온 후부터의 참조 횟수를 계산한다.- 메모리에 올라왔다가 스왑 아웃됬다가 다시 올라오면 참조 횟수를 다시 1부터 계산한다.
Perfect-LFU는 과거 총 횟수를 카운트한다.- 과거 참조 횟수까지 정확히 반영 가능한 장점이 있으나, 그 횟수를 모두 저장해야 하므로 오버헤드가 발생하는 단점이 있다.
- LRU보다 오랜 시간 동안의 참조 횟수를 반영하는 장점이 있으나, 구현이 더 복잡하고 시간에 따른 페이지 참조의 변화를 반영하지 못하는 단점이 있다.
- 클럭 알고리즘
- LRU 알고리즘과 유사하게 오랫동안 참조되지 않은 페이지 중 하나를 스왑아웃시킨다.
- 즉, 가장 오랫동안 참조되지 않은 페이지를 쫒아내는 것은 아니라는 말이다.
- 하드웨어의 도움을 받아서 처리하므로 빠르고 효율적이다.
- 프레임마다 참조 비트가 존재하는데, 페이지가 참조되면 값이 1로 자동 세팅된다.
- 참조 비트를 순차적으로 조사하여 값이 1인 페이지는 0으로 설정하고 교체하지 않고 넘어가고, 값이 0인 페이지를 교체한다.
- 모든 페이지를 조사했다면 다시 첫 페이지부터 조사를 하여 0인 페이지를 교체한다.
- 시곗바늘이 한 바퀴 도는 시간만큼 페이지를 메모리에 유지시킴으로써 페이지 부재율을 줄이도록 설계되어서 이 알고리즘을 2차 기회 알고리즘이라고도 한다.
페이지 프레임의 할당
여러 개의 프로세스에게 얼만큼의 메모리 공간을 할당할지 결정해야 한다.
기본적인 할당 알고리즘으로 균등할당 방식 (equal allocation)과 프로세스의 크기에 따른 비례할당 방식 (proportional allocation), 프로세스의 우선순위에 따른 우선순위 할당 방식 (priority allocation)이 있다.
단, 이런 할당 알고리즘만으로는 페이지 참조 특성을 반영하지 못할 우려가 있다.
따라서 종합적인 상황을 고려해서 각 프로세스에 할당되는 페이지 프레임의 수를 결정해야 하고, 경우에 따라서는 일부 프로세스에게 메모리를 할당하지 않는 방식으로 나머지 프로세스들에게 최소한의 메모리 요구량을 충족시킬 수 있어야 한다.
전역교체와 지역교체
페이지 교체에서 배운 것은 알고리즘으로, 교체 방법에 대해서는 전역 교체와 지역 교체가 있다.
전역 교체는 물리적 메모리에 있는 모든 프로세스들의 페이지를 대상으로 교체 대상을 선정하는 것이다.
지역 교체는 현재 수행 중인 프로세스 내에서 교체 대상 페이지를 선정하는 것이다.
예를 들어, LRU 알고리즘의 경우에 전역 교체 방법을 쓴다면 물리적 메모리에 올라와 있는 모든 페이지 중 가장 오래전에 참조된 페이지를 교체한다.
지역교체는 프로세스별로 페이지 프레임을 할당하고, 교체할 페이지도 그 프로세스에게 할당된 프레임 내에서 선정하게 되는 것으로 LRU, LFU 등의 알고리즘을 프로세스별로 독자적으로 운영할 때 가능하다.
스레싱
프로세스가 정상적으로 수행되려면 일정 수준의 페이지 프레임을 할당받아야 한다.
그렇지 못한다면 페이지 부재율이 크게 상승해서 CPU의 이용률을 크게 낮추게 되는데 이를 스레싱(thrashing)이라 한다.
정확히 얘기하면 다음과 같다.
운영체제는 CPU 이용률이 낮아지면 메모리에 프로세스를 추가하여 CPU의 이용률을 높이고자 한다.
메모리에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도(Multi-Programming Degree, MPD)라고 한다.
즉, 운영체제는 CPU 이용률이 낮아지면 MPD를 높인다.
이 MPD 값이 과도하게 올라가버리면 프로세스 당 할당해줄 수 있는 페이지 프레임이 줄어들게 되는데, 이렇게 되면 정상적으로 수행하기 위해 필요한 일정 수준의 페이지 프레임을 할당받지 못하는 상황에 직면하게 된다.
즉, 페이지 부재율이 증가를 하게 되는데, 페이지 부재가 발생하면 프로세스가 봉쇄 상태에 들어가게 된다.
근데, 다른 프로세스들도 일정 수준의 프레임을 못받아서 계속해서 페이지 부재가 발생하게 되므로 이는 곧 CPU 이용률의 하락으로 이어진다. (핵심)
근데 운영체제 입장에서는 이를 보고 CPU 이용률이 낮아졌으니까 메모리에 프로세스를 추가하게 되므로 딜레마에 빠지게 된다.
이러한 현상을 스레싱이라고 하는 것이다.
이 현상을 방지하기 위해 워킹셋 알고리즘(working-set algorithm)과 페이지 부재 빈도 알고리즘(page-fault frequency scheme)이 있다.
- 워킹셋 알고리즘
- 프로세스가 일정 시간동안 집중적으로 참조하는 주소 영역을 지역성 집합이라고 한다.
- 워킹셋 알고리즘은 이러한 지역성 집합(워킹셋)이 한꺼번에 올라갈 수 있는 프로세스에게만 메모리를 할당해주는 알고리즘이다.
- 즉, 프로세스가 일정 시간 동안 원할히 수행되는 것을 보장하는 매모리 관리 알고리즘이다.
- 그렇지 못한 경우엔, 프로세스에게 할당된 페이지들을 모두 반납시키고 프로세스의 주소 공간 전체를 스왑아웃시킨다.
- 이러한 방법으로 MPD를 조절하고 스레싱을 방지한다.
- 페이지 부재 빈도 알고리즘
- 페이지의 부재율을 주기적으로 조사하여 이 값에 근거해 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.
- 프로세스의 부재율이 미리 정해놓은 상한값을 넘는다면 프레임을 추가적으로 할당해준다.
- 반대로 하한값 이하로 떨어지면 프레임을 스왑아웃시켜서 조절한다.
- 이런식으로 메모리 내에 존재하는 프로세스의 수를 조절하고 CPU 이용률을 높이는 동시에 스레싱을 방지한다.