운영체제(7)-가상 메모리

책 <운영체제와 정보기술의 원리>, 반효경 을 읽고 정리한 내용입니다

운영체제(1) - 개요

운영체제(2) - 컴퓨터 시스템의 동작 원리

운영체제(3) - 인터럽트의 원리

운영체제(4) - 프로세스 관리

운영체제(5) - CPU스케줄링

운영체제(6) - 메모리 관리

프로그램이 실행되기 위해 프로세스의 주소공간 전체가 메모리에 적재되어야 하는 것은 아니다. 따라서 OS는 CPU에 당장 수행해야 할 부분만을 적재하고 그렇지 않은 부분은 디스크의 swap area에 내려놓았다가 필요해지면 교체하는 방식을 사용한다.

메모리의 연장 공간으로 디스크를 사용할 수 있기 때문에 프로그램 입장에서는 물리 메모리 크기에 대한 제약을 고려할 필요가 없어진다. 따라서 프로그램은 0번지부터 시작하는 자신만의 메모리 공간을 가질 수 있다.

가상 메모리는 프로세스마다 0번지부터의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리 메모리에 적재되고 일부는 디스크의 스왑 영역에 존재하게 된다.

주소 공간을 메모리에 적재하는 단위에 따라 가상 메모리 기법은 요구 페이징 방식과 요구 세그먼테이션 방식으로 구현될 수 있다. 대부분의 경우 요구 페이징 방식을 사용한다.

요구 페이징

프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라, 당장 사용될 페이지만을 메모리에 올리는 방식

특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다.

메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는 데 들었던 입출력 오버헤드도 줄어든다.

• 응답 시간의 단축
• 더 많은 프로세스의 수용

프로그램이 물리적 메모리의 용량 제약을 벗어날 수 있도록 한다.

유효-무효 비트를 두어 각 페이지가 메모리에 존재하는지를 표시하게 된다

• 무효 비트 : 페이지가 메모리에 없는 경우(페이지 부재), 페이지의 주소 영역을 프로세스가 사용하지 않으려는 경우
• 유효 비트 : 페이지가 메모리에 적재되어 있는 경우

요구 페이징의 페이지 부재 처리

1. CPU가 페이지 M을 참조한다
2. 페이지 테이블에서 페이지 M이 무효 상태(invailid) 임을 확인한다.
3. 페이지 부재 트랩이 발생한다.
4. 디스크에서 부재 페이지를 빈 프레임으로 적재하고 페이지 테이블을 업데이트한다.

요구 페이징의 성능

요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다.

• 요청한 페이지를 디스크로부터 메모리로 읽어오는 오버헤드가 크다

• 다음과 같은 유효 접근 시간으로 측정한다.

  (1-P) * 메모리 접근 시간 +
  P * (페이지 부재 발생 처리 오버헤드
  	+ 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드
  	+ 요청된 페이지의 스왑 인 오버헤드
  	+ 프로세스의 재시작 오버헤드 )
    	
  (P=0 :페이지 부재가 한번도 일어나지 않은 경우)
  

페이지 교체

페이지 부재가 발생했는데, 물리 메모리에 빈 프레임이 존재하지 않는다면 메모리에 적재되어 있는 페이지 중 하나를 swap out 해서 메모리에 빈 공간을 확보해야 한다. 이를 페이지 교체라 한다.

페이지 교체 시에 어떠한 프레임에 있는 페이지를 쫒아낼 것인가를 결정하는 알고리즘을 교체 알고리즘이라 한다.

• 페이지 부재율을 최소화해야 한다
• 가까운 미래에 참조될 가능성이 가능 적은 페이지 선택

최적 페이지 교체

Belady’s optimal page replacement

물리 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫒아내는 알고리즘.

미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제 하에 운영한다.

FIFO 알고리즘

First In First Out

물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫒는다.

비효율적인 상황 발생 가능

• 가장 먼저 올라온 페이지가 이후 많은 참조가 일어나도 해당 페이지를 내쫒는다.
• 물리 메모리를 증가해도 페이지 부재가 오히려 늘어나는 상황 발생 가능(FIFO anomaly)

LRU 알고리즘

시간 지역성 : 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질

Least Recently Used

시간 지역성을 활용하여 페이지 교체 시 가장 오래 전에 참조가 이루어진 페이지를 내쫒는다.

LFU 알고리즘

Least Frequently Used

물리 메모리 내에 존재하는 페이지 중 과거에 참조 횟수가 가장 적었던 페이지를 내쫒는다.

• Incache-LFU

  페이지가 물리 메모리에 올라온 후부터의 참조 횟수를 카운트

• Perfect-LFU

  페이지의 과거 총 참조 횟수를 카운트

LRU 알고리즘보다 오랜 시간 동안의 참조 기록을 반영할 수 있다.

• 시간에 따른 페이지 참조의 변화를 반영하지 못한다.

클럭 알고리즘

하드웨어의 지원을 통해 교체 알고리즘의 운영 오버헤드를 줄인 방식

최근에 참조되지 않은 페이지를 교체 대상으로 선정한다는 측면에서 LRU와 유사하지만, 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 못한다.

대부분의 시스템에서 클럭 알고리즘을 채택한다.

클럭 알고리즘은 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조 비트를 순차적으로 조사한다.

참조 비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 세팅된다.

참조 비트가 1인 페이지는 0으로 바꾼 후 지나가고, 참조 비트가 0인 페이지는 교체한다.

페이지 프레임의 할당

여러 프로세스가 수행될 때는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지를 결정해야 한다.

할당 알고리즘

• 균등 할당 : 모든 프로세스에게 페이지 프레임을 균일하게 할당
• 비례 할당 : 프로세스의 크기에 비례해 페이지 프레임을 할당
• 우선순위 할당 : 당장 CPU에서 실행될 프로세스에 많은 페이지 프레임을 할당

수행중인 프로세스의 수가 지나치게 많을 경우 프로세스당 할당되는 메모리양이 과도하게 적어질 수 있다.

CPU에서 명령을 실행할 때에는 일반적으로 여러 페이지를 동시에 참조한다.

프로세스를 수행하기 위해서는 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야 한다.

반복문을 실행중인 프로세스의 경우 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려놓는 것이 유리하다.

전역 교체와 지역 교체

전역 교체 방법은 모든 페이지 프레임이 교체 대상이 될 수 있는 방법

• 페이지 교체시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있는 방식
• 프로세스별 프레임 할당량을 스스로 조절
• LRU, LFU, 클럭 알고리즘을 전체 페이지 프레임을 대상으로 적용할 경우와 워킹셋, PFF알고리즘

지역 교체 방법은 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법.

• LRU, LFU 등의 알고리즘을 프로세스별로 독자적 운영할 때

스레싱

집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어지는 현상

발생 시나리오

1. OS는 CPU이용률이 낮으면 메모리에 올라와 있는 프로세스의 수가 적다고 판단한다.
2. OS는 메모리에 올라가는 프로세스의 수를 늘린다(MPD를 높이게 된다)
3. MPD가 과도하게 높아지면 각 프로세스에 할당되는 메모리 양이 지나치게 감소한다.
4. 각 프로세스들은 최소한의 페이지 프레임도 할당받지 못하는 상태가 된다.
5. 페이지 부재가 빈번히 발생한다.
6. 페이지 부재는 디스크 I/O 작업을 수반하므로 문맥 교환이 일어난다.
7. 문맥 교환을 통해 CPU를 잡은 프로세스도 메모리 양이 지나치게 적어 페이지 부재가 발생한다.
8. 준비 큐에 있는 모든 프로세스가 페이지 부재를 발생시킨다.
9. CPU 이용률은 급격히 떨어진다.
10. OS는 프로세스의 수가 적어서 CPU사용량이 떨어진다고 판단, 또 다른 프로세스를 메모리에 추가한다.

스레싱이 발생하지 않도록 하면서 CPU이용률을 최대한 높일 수 있도록 MPD를 조절하는 것이 중요.

워킹셋 알고리즘

지역성 집합 : 집중적으로 참조되는 페이지들의 집합

지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘

워킹셋 : 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합

워킹셋을 구성하는 페이지들이 한번에 메모리에 올라갈 수 있는 경우에만 해당 프로세스에 메모리를 할당한다.

그렇지 않으면, 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 주소 공간 전체를 디스크로 스왑 아웃.

MPD를 조절하고 스레싱을 방지한다.

페이지가 참조된 시간부터 $\Delta$시간 동안은 메모리에 유지하고, 그 시점이 지나면 메모리에서 지운다.

프로세스가 메모리를 많이 필요로 할 때는 많이 할당하고, 적게 필요로 할 때는 적게 할당하는 일종의 동적인 프레임 할당 기능

페이지 부재 빈도 알고리즘

PFF

어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해 놓은 상한값을 넘게 되면 이 프로세스에 할당된 프레임의 수가 보족하다는 것을 의미하므로, 이 프로세스에게 프레임을 추가로 더 할당한다.

모든 프로세스에 프레임을 할당한 뒤에도 프레임이 남으면 스왑 아웃된 프로세스에게 프레임을 할당한다.

CPU사용률을 높이고 스레싱을 방지한다.