[OS] Chapter 10. 가상 메모리

Table of Contents

운영체제와 정보기술의 원리 강의를 듣고 공부한 노트입니다.

요구 페이징 #

운영체제는 프로그램에서 당장 수행해야 할 부분만을 메모리에 올려놓고, 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지면 메모리에 올리가 있는 부분과 교체하는 방식을 사용한다.
이렇게 하면, 메모리의 연장 공간인 것처럼 디스크 스왑 영역을 사용할 수 있게 된다. 그래서 프로그램은 물리적 메모리의 크기 제약을 신경쓰지 않아도 되므로 각자 독자적인 메모리 주소 공간을 가질 수 있게 된다.
프로세스마다 가지고 있는 0번지부터 시작하는 메모리 주소 공간을 가상 메모리(virtual memory) 라고 한다.

프로세스의 이런 주소 공간을 어떤 단위로 메모리에 적재하는가에 따라 요구 페이징(demand paging) 과 요구 세그먼테이션(demand segmentation) 방식으로 나뉜다.
- 대부분 요구 페이징 방식을 사용한다.

요구 페이징(demand paging)
- 프로그램을 실행했을 때, 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라, 당장 사용될 페이지만을 올리는 방식이다.
장점
- 물리적 메모리 용량보다 더 큰 프로그램도 실행할 수 있다.
- 당장 사용할 페이지만 올리기 때문에 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는 데 드는 입출력 오버헤드도 감소한다.
- 사용되지 않을 주소 영역에 대한 입출력까지 수행하던 기존 방식에 비해 응답 시간을 단축시킬 수 있다.
- 또한 시스템이 더 많은 프로세스를 수용할 수 있게 해준다.

해당 페이지가 메모리에 존재하는지 표시하기 위해 유효-무효 비트(valid-invalid bit) 를 사용한다.
페이지 부재(page fault)
- CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아서 유효-무효 비트가 무효로 세팅되어 있는 경우이다.

페이지 부재를 처리하는 방식 #

Image Source

(1) CPU가 무효 페이지에 접근하면, (2) 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재트랩(page fault trap)을 발생시칸다.
CPU의 제어권이 커널 모드로 전환되고, 운영체제의 페이지 부재 처리루틴(page fault handler)이 호출된다.
(3, 4) 해당 페이지의 접근이 적법한 것으로 판명된 경우, 물리적 메모리에서 비어 있는 프레임을 할당 받아서 그 공간에 해당 페이지를 읽어온다.
- 만약 비어있는 프레임이 없다면, 기존에 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫒아낸다. (스왑 아웃; swap out)
- 페이지를 메모리로 적재하는데 오랜시간이 걸리므로 해당 프로세스는 CPU를 빼앗기고 봉쇄 상태가 된다.
- 현재까지 수행되던 CPU 레지스터 상태 및 프로그램 카운터 값은 프로세스 제어블록에 저장해 두어서 나중에 이 프로세스가 CPU를 할당 받으면 정확히 같은 상태에서 다음 명령을 수행할 수 있도록 한다.
(5) 디스크 입출력이 완료되어서 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정하고, 봉쇄되었던 프로세스를 준비 큐로 이동시킨다.
(6) 이 프로세스가 CPU를 할당 받으면 프로세스 제어블록에 저장해두었던 값을 복원시켜 이전에 중단되었던 명령(instruction)부터 실행을 재개한다.

요구 페이징의 성능 #

유효 접근시간 (effective access time)
- $ = (1 - P) \times $ 메모리 접근시간 $ + P \times ($ 페이지 부재 발생 처리 오버헤드 $+$ 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드 $+$ 요청된 페이지의 스왑 인 오버헤드 $+$ 프로세스의 재시작 오버헤드$)$
페이지 부재 발생비율(page fault rate)
- $ 0 \le P \le 1 $
- $ P = 0 : $ 페이지 부재가 한 번도 일어나지 않은 경우
- $ P = 1 : $ 모든 참조 요청에서 페이지 부재가 발생한 경우
요구 페이징의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다.
- $P = 0$이면, 즉 페이지 부재가 일어나지 않으면, 오로지 메모리 접근 시간만 소요된다.
- $P \ne 0$이면, 즉 페이지 부재가 일어나면, 많은 오버헤드가 필요하게 된다.

페이지 교체 #

Image Source

페이지 교체(page replacement)
- 페이지 부재가 발생했을 때 메모리에 빈 공간이 없으면, 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫒아내서 공간을 확보한다. 이것을 페이지 교체라고 한다.
페이지 교체 알고리즘
- 어떤 페이지를 쫒아낼 것인가를 결정하는 알고리즘이다.
- 이 알고리즘의 목표는 페이지 부재율을 최소화하는 것이다.
- 성능평가
  - 페이지 참조열(page reference string)에 대해 페이지 부재율을 계산함으로써 평가할 수 있다.
  - 해당 번호의 페이지가 메모리에 올라와 있으면 적중(hit), 없으면 부재가 발생했다고 한다.

(1) 최적 페이지 교체 #

Optimal Algorithm
빌레디의 최적 알고리즘(Belady’s optimal algorithm), MIN, OPT 등으로 불린다.
가장 먼 미래에 참조될 페이지를 먼저 교체하는 방법이다.
미래에 어떤 페이지가 어떤 순서로 참조될지 미리 알고있다는 전제하에 알고리즘을 운영하므로, 실제 온라인으로 사용할 수 있는 알고리즘이 아니다. 이런 알고리즘을 오프라인 알고리즘이라고 부른다.
어떤 경우라도 가장 적은 페이지 부재율을 보장하므로, 다른 알고리즘의 성능을 평가하는 상한선(upper bound)을 제공한다. 즉, 최적 알고리즘과 유사한 결과가 나오면 좋은 것이다.

(2) 선입선출 알고리즘 (FIFO) #

First In First Out
메모리에 가장 먼저 올라온 페이지를 먼저 교체하는 방법이다.
향후 참조 가능성을 생각하지 않기 때문에 비효율적인 상황이 발생할 수 있다.
- FIFO 이상 현상(FIFO anomaly)
  - 메모리를 증가시켰음에도 불구하고 페이지 부재가 오히려 늘어나는 상황

(3) LRU 알고리즘 #

Least Recently Used
가장 오래전에 참조한 페이지를 먼저 교체하는 방법이다.
최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높다는 성질인, 시간 지역성(temporal locality) 에 따른 방법이다.

(4) LFU 알고리즘 #

Least Frequently Used
과거에 참조 횟수(reference count)가 가장 적은 페이지를 먼저 교체하는 방법이다.
참조 횟수를 계산하는 방식에 따라…
- Incached-LFU
  - 페이지가 메모리에서 쫒겨났다가 다시 들어오면 참조 횟수가 1이된다.
- Perfect-LFU
  - 과거의 총 참조 횟수를 카운트한다.
  - 과거의 참조 기록을 모두 보관해야 하므로 오베헤드가 상대적으로 크다.

LRU의 경우에는 직전에 참조된 시점만을 반영하지만 LFU는 장기적인 시간 규모에서의 참조 성향을 고려한다.
- 참조열이 1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5와 같고 현재 5 페이지를 참조하기 위해 페이지 교체를 해야한다고 했을 때,
- LRU는 가장 오래전에 참조한 1을 내쫒는다. $O(1)$의 시간 복잡도가 걸린다.
- LFU는 가장 참조 횟수가 적은 4를 내쫒는다. 힙(heap)을 사용해서 $O(log n)$의 시간 복잡도가 걸린다.

캐쉬 운영의 시간 제약 #

캐슁 기법
- 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다.
- paging system(디스크의 스왑 영역의 페이지를 캐싱)외에도 cache memory, buffer caching(디스크의 파일 시스템의 파일의 블럭을 캐싱), web caching(지리적으로 멀리 떨어져있는 컴퓨터에서 웹서버에서 매번 읽어오지 않고 내 컴퓨터에 캐싱되어 있는 것을 읽어오는 것) 등 다양한 분야에서 사용된다.

교체 알고리즘은 캐쉬 운영의 시간 제약이 있다.
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.
- buffer caching이나 web caching의 경우에는
  - $O(1)$, $O(log n)$ 정도까지만 허용된다.
- paging system의 경우 제약 조건이 더 있다.
  - 페이지 부재가 발생한 경우에만, 트랩이 발생하고 제어권이 넘어가서 운영체제가 관리할 수 있게 된다.
  - 그래서 페이지가 이미 메모리에 존재하는 경우에는 운영체제가 참조 시각 등의 정보를 알 수 없다. 그래서 $O(1)$이더라도 LRU의 리스트(참조한 것들의 목록) 조작도 불가능하게 된다.
  - 그렇기 때문에 LRU, LFU는 사실 paging system에 적절한 알고리즘들은 아니다.

(5) 클럭 알고리즘(NUR) #

Not Used Recently
LRU, LFU 알고리즘은 페이지 참조 시각, 참조 횟수를 소프트웨어적으로 유지하고 비교하므로 오버헤드가 발생한다.
클럭 알고리즘은 이것을 하드웨어적으로 지원해서 훨씬 빠르고 효율적으로 이루어지게 한다.
대부분의 시스템에서 이 알고리즘을 채택한다.
LRU를 근사시킨 알고리즘이다.
- 최근에 참조되지 않은 페이지를 교체하는 것은 LRU와 동일하다.
- 하지만 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.

Image Source

각 프레임 마다 참조 비트(reference bit) 를 두어 사용한다.
- 해당 프레임의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.
- 교체 대상 페이지를 찾을 때는 1인 페이지는 0으로 만들고 지나가고, 0인 페이지를 만나면 교체한다.
- 즉, 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체하는 것이다.
modified bit(dirty bit) 를 둘 수도 있다.
- 참조 비트는 Read한 페이지라면, 이것은 최근에 Write로 변경된 페이지(I/O를 동반하는 페이지)를 1로 세팅한다.
- modified bit이 1인 페이지를 교체하려면 수정된 내용을 디스크에 쓰고 교체해야한다. 그래서 0인 페이지를 교체하는 것이 더 효율적이다.

할당량 #

각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인가?
- 예를 들어, 반복문을 실행 중인 프로세스의 경우 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려 놓는 것이 페이지 부재가 덜 발생한다.
- 혹은 명령을 실행할 때 프로세스의 주소 공간에서 코드, 데이터, 스택 등의 각기 다른 영역을 참조하기 때문에 적어도 일정 수준 이상의 프레임을 할당해야 한다.

할당 알고리즘
- 균등할당(equal allocation)
  - 모든 프로세스에게 균일하게 할당
- 비례할당(proportional allocation)
  - 프로세스 크기에 비례해서 할당
- 우선순위 할당(priority allocation)
  - 프로세스의 우선순위에 따라 할당

프레임의 범위 #

교체 대상이 될 프레임의 범위를 어떻게 정할 것인가?
전역교체(global replacement)
- 모든 프레임이 교체 대상이 된다.
- 교체할 프레임은 다른 프로세스에게 할당된 것일 수 있다. 즉, 페이지 교체 시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있는 방식이다. 다시 말하면, 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.
- 워킹 셋, PFF 알고리즘
지역교체(local replacement)
- 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있다.

스레싱 #

Image Source

스레싱(thrashing)
- 잦은 페이지 부재로 CPU 이용률이 급격히 저하되는 현상

프로세스의 원활한 수행을 위해 필요한 최소한의 페이지 만큼 메모리를 할당받지 못하면?
- 페이지 부재율이 높아진다.
- CPU 이용률(CPU utilization)이 낮아진다.
- 운영체제는 다중 프로그래밍의 정도(multi-programming degree; MPD; 메모리에 동시에 올라가 있는 프로세스의 수) 를 높인다.
- 또 다시 새로운 프로세스가 시스템에 추가된다. 그러면 프로세스 당 할당된 프레임의 수가 더욱 감소한다.
- 페이지 부재가 빈번히 발생하여, 프로세스들은 서로의 페이지를 교체하며 스왑 인과 스왑 아웃을 지속적으로 발생시킨다.
- 따라서 대부분의 시간에 CPU는 할일이 없게된다.

MPD를 적절히 조절해서, CPU 이용률을 높이는 동시에 스레싱 발생을 방지하는 방법
- (아래…)

(1) 워킹셋 알고리즘 #

참조의 지역성(locality of reference)
- 프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다.
지역성 집합(locality set)
- 집중적으로 참조되는 페이지들의 집합.

워킹셋 알고리즘(working-set algorithm)
- 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이다.
- 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 워킹셋(working-set) 이라고 정의한다.
- 이 워킹셋이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다.
- 그렇지 못한다면 할당된 모든 프레임을 반납하고 디스크로 스왑 아웃시킨다.

워킹셋을 결정하는 법
- 윈도우의 크기가 $\Delta$인 경우, 페이지가 참조된 시점부터 $\Delta$시간 동안은 메모리에 유지하고, 그 시점이 지나면 메모리에서 지워버린다.
- $t_i$ 시각에서의 워킹셋 $WS(t_i)$
- $=$ 시간간격 $[t_i - \Delta, t_i]$ 사이에 참조된 서로 다른 페이지들의 집합

(2) 페이지 부재 빈도 알고리즘 #

Image Source

페이지 부재 빈도 알고리즘(page-fault frequency scheme)
- 페이지 부재율의 상한값과 하한값을 두어서, 상한값을 넘기면 프레임을 추가로 할당하고, 하한값 이하로 떨어지면 프레임 수를 줄이는 방법이다.