가상 메모리

이 글은 반효경 저 - "운영체제와 정보기술의 원리"를 공부하고 정리하여 작성하였습니다.

 

운영체제는 프로그램 실행 시 CPU에서 즉시 필요한 부분만 메모리에 로드하고, 나머지는 디스크의 스왑 영역에 저장하여 메모리 사용을 최적화한다.

프로그램 입장에선 물리적 메모리 크기에 대한 제약을 생각할 필요가 없고 자기 자신만이 메모리를 사용하는 것처럼 프로그램하는 것을 지원한다.

이렇게 되면 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소공간을 가정할 수 있는데 이를 가상메모리라 부른다.

 

1. 요구 페이징

• 프로그램 실행 시 프로세스에 당장 사용될 페이지만을 올리는 방식을 말함
• 요구 페이징은 특정 페이지에 대해 CPU의 요청이 들어온 후 해당 페이지를 메모리에 적재
• 요구 페이징 기법은 메모리 사용량이 감소하고 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 감소함.
• 이 방식은 응답시간을 단축시켜주고 시스템에 더 많은 프로세스를 수용하게 해줌
• 프로세스가 실행되는 동안 일부 페이지만 메모리에 올라가 있고 나머지는 디스크 스왑영역에 위치함.

• 요구 페이징에서는 유효-무효 비트를 두어 각 페이지가 메모리에 존재하는지 표시함
• 이 비트는 페이지 테이블의 각 항목별로 저장됨
• 이 비트는 특정 페이지가 참조되어 메모리에 적재된 경우 무효값에서 유효값으로 바뀜
• 그리고 디스크의 스왑영역으로 쫓겨날 때에는 다시 무효값으로 바뀜
• CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅된 경우를 페이지 부재(page fault)가 일어났다고 함.

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

• CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 MMU가 페이지 부재 트랩을 발생
• 이후 CPU 제어권이 커널모드로 전환되고 페이지 부재 처리루틴이 호출됨
  1. 부재 상태의 페이지를 메모리에 적재하기 앞서 페이지에 대한 접근이 적법인지를 확인
  2. 접근 권한 위반인 경우 종료시키고 적법한 경우 물리적 메모리에서 비어 있는 프레임을 할당받아 해당 페이지를 읽게 함.
     • 비어 있는 프레임이 없다면 기존 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아냄 (스왑 아웃)
  3. 디스크로부터 메모리에 적재하기까지 시간이 오래 걸리므로 페이지 부재를 발생시킨 프로세스는 CPU를 빼앗기고 봉쇄 상태가 됨
     • 현재까지 수행되던 CPU 레지스터 상태 및 프로그램 카운터값을 프로세스 제어블록에 저장함
  4. 디스크 입출력이 완료되어 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정하고 봉쇄되었던 프로세스를 준비 큐로 이동시킴
  5. 이 프로세스가 다시 CPU를 할당받으면 프로세스 제어블록에 저장했던 값을 복원시켜 이전 명령부터 실행을 재개

1.2. 요구 페이징의 성능

• 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도
  • 디스크로부터 메모리로 읽어오는 막대한 오버헤드를 발생시키기 때문
• 유효 접근시간 = (1-P) x 메모리 접근시간

• P x (페이지 부재 발생 처리 오버헤드 + 메모리에 빈 프레임 없는 경우 스왑 아웃 오버헤드 + 요청된 페이지의 스왑 인 오버헤드 + 프로세스의 재시작 오버헤드)

• P = 페이지 부재 발생 비율 (0 ≤ P ≤ 1)
• 페이지 부재가 없는 경우 메모리에만 접근하면 되고 페이지 부재가 발생하면 이와 같은 과정을 모두 거치게 된다.

 

2. 페이지 교체

• 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 함.
• 이때 물리적 메모리에선 빈 프레임이 존재하지 않을 수 있음
• 이경우 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내야 함
• 이 과정을 페이지 교체라고 하는데 어떻게 쫓아낼지를 결정하는 알고리즘을 교체 알고리즘이라 한다.
• 페이지 교체 알고리즘의 성능은 페이지 참조열에 대해 페이지 부재율을 계산함으로써 평가됨.

2.1. 최적 페이지 교체

• 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조되는 페이지를 내쫓으면 된다.
• 이 알고리즘은 미래의 페이지 순서를 다 알고 있다는 전제 하에 운영하므로 실제 시스템에선 못 쓰고 실제 알고리즘 성능에 대한 상한선을 제공

2.2. 선입선출 알고리즘

• 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓음
• 페이지의 향후 참조 가능성을 고려하지 않아 비효율적인 상황이 발생할 수 있음
• 페이지 프레임을 늘렸음에도 오히려 페이지 부재가 늘어나는 상황을 FIFO의 이상 현상이라 부름

2.3. LRU(Least Recently Used) 알고리즘

• 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 내쫓음
• 마지막 참조 시점이 가장 오래된 페이지를 교체

2.4. LFU(Least Frequently Used) 알고리즘

• 페이지의 참조 횟수로 교체시킬 페이지를 결정
• 물리적 메모리 내에 존재하는 페이지 중 과거에 참조 횟수가 가장 적었던 페이지를 쫓아내는 기법
• 페이지 참조 횟수를 계산하는 방식에 따라 나뉠 수 있음
• Incache-LFU
  • 페이지가 물리적 메모리에 올라온 후부터 참조 횟수를 카운트하는 방식
• Perfect-LFU
  • 그 페이지의 과거 총 참조 횟수를 카운트하는 방식
• LFU 알고리즘은 LRU 알고리즘보다 오랜 시간 동안의 참조 기록을 반영할 수 있음
• LFU는 시간에 따른 페이지 참조의 변화를 반영하지 못하고 LRU보다 구현이 복잡하단 단점이 있음

2.5. 클럭 알고리즘

• 클럭 알고리즘은 하드웨어 지원으로 알고리즘의 오버헤드를 줄인 방식
• LRU를 근사시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU라 불림
• 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체함
• 하드웨어 지원으로 훨씬 빠르고 효율적이며 대부분의 시스템에서 사용함
• 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트를 순차적으로 조사
• 참조 비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 존재하여 참조될 때 하드웨어에 의해 1로 자동 세팅
• 참조비트가 1인 페이지가 없는 경우 0으로 바꾼 후 지나가고 0인 페이지는 교체함
• 모든 페이지 프레임을 다 조사한 후 첫번째 페이지 프레임부터 조사 작업을 반복함
• 참조비트는 그 페이지가 참조되면 다시 1로 세팅되기 때문에 한 바퀴동안 쓰이지 않으면 교체됨
• 페이지가 한 번의 순환 동안 메모리에 유지되어 재사용 기회를 얻기 때문에 2차 기회 알고리즘으로도 알려져 있다

 

3. 페이지 프레임의 할당

• 시스템의 성능 향상을 위해서는 좀 더 효율적인 메모리 할당 방법이 필요
• 기본 할당 알고리즘으로 세 가지가 있다.
  1. 균등할당 방식: 모든 프로세스에게 페이지 프레임을 균일하게 할당
  2. 비례할당 방식: 프로세스 크기에 비례해 페이지 프레임을 할당
  3. 우선순위 할당 방식: 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당
• CPU에서 명령을 실행할 때는 일반적으로 여러 페이지를 동시에 참조
• 명령을 실행할 때 프로세스의 주소 공간 중 코드, 데이터, 스택 중 각기 다른 영역을 참조하기 때문
• 프로세스를 정상적으로 수행하기 위해선 일정 수준 이상의 페이지 프레임을 각 프로세스에 참조해야 함
• 반복문의 경우, 반복문 구성 페이지 수보다 적게 프레임을 할당할 경우, 페이지 부재가 반복되어 성능이 떨어짐

 

4. 전역교체와 지역교체

• 교체할 페이지를 선정할 때, 교체 대상 프레임 범위에 따라 전역교체와 지역교체로 나뉨
• 전역교체 방법
  • 모든 페이지 프레임이 대상
  • 전체 메모리를 각 프로세스가 공유해서 사용
  • 교체 알고리즘에 근거해 할당되는 메모리 양을 가변적으로 함.
  • LRU,LFU, 클럭 등 알고리즘을 물리적 메모리 내 전체 페이지 프레임을 대상으로 하는 경우 적용됨
• 지역교체 방법
  • 현재 프로세스에 할당된 프레임 내에서만 선정
  • 프로세스 별로 페이지 프레임을 할당하고 교체할 페이지도 그 프레임 내에서 선정
  • LRU, LFU 등의 알고리즘을 프로세스 별로 독자 운영할 경우 적용됨

 

5. 스레싱(thrashing)

• 프로세스 수행을 위한 최소한의 페이지 프레임을 할당 받지 못할 경우 문제가 발생
• 이 경우 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어짐
• 이와 같은 현상을 스레싱이라 함.
• 스레싱 발생 시나리오 (악순환)
  • 운영체제는 CPU 이용률이 낮은 경우를 메모리에 올라가 있는 프로세스 수가 적어서라고 판단함.
  • 준비 큐에 있는 프로세스를 계속 메모리에 올리려 함.
  • 그런데 CPU 이용률이 낮다는 것은 준비 큐가 비는 경우가 생긴다는 의미
  • 메모리에 올라와 있는 프로세스 수가 너무 적어 이들 프로세스가 모두 I/O 작업을 하면서 준비 큐가 비는 경우가 생겼다는 뜻
  • CPU 이용률이 낮으면 운영체제는 메모리에 올라가는 프로세스 수를 늘려버림
  • 그러면 각 프로세스에 할당되는 메모리 공간이 지나치게 적어짐
  • 각 프로세스는 페이지 부재를 또 발생시킴…
  • 이후 정해진 프로세스 수를 다 채우면 서로의 페이지를 교체하며 스왑 인-아웃을 지속적으로 발생시켜 오버헤드가 늘어남
• 이런 스레싱을 방지하기 위한 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 있음

※ MPD(Multi-Programming Degree, 다중프로그래밍의 정도): 메모리에 동시에 올라가 있는 프로세스의 수

5.1. 워킹셋 알고리즘

• 프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있고 참조되는 페이지 집합을 지역성 집합이라 함.
• 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 알고리즘을 말함.
• 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갔을 때에 유효하고 그렇지 않은 경우 할당된 페이지 프레임들을 모두 반납시키고 주소 공간 전체를 디스크로 스왑아웃시킴
• 한꺼번에 메모리에 올라갈 페이지들의 집합을 결정하기 위해 워킹셋 윈도우(Δ)를 사용함
• 윈도우의 크기가 Δ인 경우, 워킹셋 알고리즘은 시각 t1에서의 워킹셋 WS(t1)을 시간 간격 [t1-Δ,t1]사이에서 참조된 서로 다른 페이지들의 집합으로 정의
• 해당 시간 범위 내에 페이지들은 메모리에 유지하고 그렇지 않은 페이지들은 쫓아냄
• 즉, 페이지가 참조된 시점부터 Δ시간 동안은 메모리에 유지하고 그 시점이 지나면 메모리에서 지움
• 워킹셋 알고리즘은 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합 > 프레임의 수 인 경우 일부 프로세스를 스왑 아웃 시켜 남은 프로세스의 워킹셋이 모두 메모리에 올라가도록 함
• 반면 모두 할당한 후에도 프레임이 남을 경우, 스왑 아웃당했던 프로세스를 다시 메모리에 올려 워킹셋을 할당하여 MPD를 증가시킴
• Δ 가 너무 작으면, 지역성 집합을 수용하지 못할 수 있음
• Δ 가 너무 크면, MPD가 너무 감소해 CPU 이용률이 떨어짐

5.2. 페이지 부재 빈도 (Page Fault Frequency: PFF) 알고리즘

• 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해 프로세스에 할당할 메모리 양을 동적으로 조절함
• 시스템에서 미리 정해놓은 페이지 부재율 상한값을 넘기면 이 프로세스에 프레임을 추가 할당함.
• 추가할 빈 프레임이 없는 경우 일부 프로세스를 스왑 아웃시켜 확보함.
• 하한값 이하로 떨어질 경우 여유있다 생각하여 프레임을 감소시킴

 

자료

• 운영체제와 정보기술의 원리 (반효경 저, 2020.5)