[OS] 04. 가상 메모리 관리

(1) 개요

▶ Virtual Memory

• 사용자(Process)는 실제 주소 공간의 크기에 구애받지 않고 보다 큰 가상 주소 공간상에서 프로그램을 수행 가능하게 한다.
• 가상 메모리는 하나의 프로세스 전체가 한 번에 주기억장치 내에 존재하지 않고 일부만 있어도 수행되는 방법을 제공한다.
• 주기억장치보다 크기가 큰 프로세스 수행을 가능하게 한다.
• Virtual Memory : 가상 주소 공간을 가진다. (V.M이 클수록 성능은 저하되고, 디스크 상에 존재한다.)
• Main Memory : 실제 주소 공간을 가진다.
• OS는 V.M과 M.M 전체를 하나의 메모리로 인식한다.
  • 전체 메모리는 가상 메모리를 포함한다.
  • 가상 메모리가 추가 되어 많은 프로세스를 수행 가능하게 한다.
• CPU 입장에서는 V.M(디스크)를 물리적으로 직접 접근할 수 없다.
  • 전체 메모리는 가상 메모리를 포함하므로 CPU는 가상 메모리의 주소를 보고 프로세스를 수행시킨다.
  • 그러나, 가상 메모리는 CPU가 접근할 수 없기 때문에 OS는 재빨리 해당 프로세스를 실제 메모리로 이동시키고, 동적 주소 변환을 통해 CPU가 수행하고 있는 가상 메모리 주소를 실제 메모리 주소로 변환시켜 프로세스를 수행하게 한다.

 

▶ Dynamic Address Translation

• 프로세스가 수행될 때 가상주소가 실제주소로 변환되는 메커니즘이다.
  • 프로세스가 가상 메모리에서 참조하는 주소를 Virtual Address라고 하며, 실제 메모리에서 이용할 수 있는 주소를 Real Address라고 한다.
• 인위적 연속성 : 가상주소 공간상의 연속된 주소들이 실기억 공간에서 반드시 연속적일 필요가 없다.

중간에 매핑 테이블(사상 테이블)이 주소를 매핑시켜주는 역할을 하는데, OS가 주소를 기억하고 있어 이 주소를 CPU에게 알려준다. 그리고 프로세를 여러 개의 block으로 나누는 것이 효율성이 좋다.

 

• 동적 주소 변환에서는 Block Mapping 기법을 사용한다.
  • 어느 정도 크기를 가진 블록 단위로 가상주소에서 실제주소로 프로그램이 이동하게 되는 것을 말한다.
  • 가상주소에 위치한 프로그램의 실제주소로 Mapping을 byte단위로 수행한다면 매핑 테이블의 사이즈가 증가해 비효율적이다.
  • 블록 사상 기법에서는 블록의 크기를 기준으로 Paging과 Segment 방법으로 나눈다.

 

(2) Paging

• 동일한 크기의 블록을 이용하여 가상주소와 실제 주소를 매핑한다.
• 이들 블록을 Page라고 하고, Page들로 가상 메모리를 구성한다.
• 가상 주소를 순서쌍 v=(p,d)로 표현한다.
  • p는 가상 메모리 내에서 참조될 항목이 속해 있는 페이지 번호이다.
  • d는 페이지 p내에서 참조될 항목이 위치하고 있는 곳의 변위(offset)이다.
• 가상 주소는 Page Mapping Table(페이지 사상 테이블)을 통해 실제 주소를 계산한다.
  • 동적 주소 변환 이후 주기억장치의 실제 주소인 v=p'+d를 구한다.
• 페이지 사상 테이블은 Page Residence Bit(페이지 존재 비트)를 가진다.
  • M.M내에 페이지가 존재할 때 '1', 존재하지 않을 때 '0'으로 표시한다.

 

1. Direct Mapping

• 주기억장치에 저장되어 있는 페이지 사상 테이블을 이용하여 동적 주소 변환을 수행한다.
• 페이지 사상 테이블의 시작주소는 페이지 사상 테이블 시작 레지스터(OS가 저장)에 보관되어 있다.
• 페이지 사상 테이블 내의 내용 참조(읽기)는 한 번의 주기억장치 Cycle Time(주기 시간)내에 수행된다.

  

직접 사상에서의 페이지 사상 테이블은 페이지 번호를 순차적으로 검색한다.

 

2. Associative Mapping

• 별도의 Associative Memory(연관 기억장치-H/W)를 이용하여 페이지 사상 테이블 전체를 관리한다.
• 연관 기억장치는 병렬 검색이 가능하나 고가의 메모리이다.
• 입력되는 내용을 통하여 직접적으로 메모리의 내용 검색이 가능하다.
• 직접 사상 방법의 주소 기반 검색보다 훨씬 빠른 검색이 가능하다.

직접 사상은 페이지 번호를 순차적으로 검색했지만 연관 사상은 한번에 검색해서 속도가 빠르다.

 

3. Associative/Direct Mapping

• 연관 사상 및 직접 사상의 장점을 살릴 수 있는 복합 주소 변환 기법이다.
• 페이지 사상 테이블이 주기억장치와 연관기억장치에 나눠져서 관리된다.
• 가장 최근에 참조된 페이지는 조만간 다시 사용되기 쉽다는 사실을 이용한다.
• 연관기억장치에 페이지 사상 테이블의 전체 항목 중 가장 최근에 참조된 일부 페이지 정보를 저장한다.

가상 주소를 연관 페이지 사상 테이블에서 찾고, 없으면 직접 사상 테이블에서 찾는다.

 

4. Share in Paging System

• 다중 프로그래밍 환경에서 공유가 가능한 페이지를 공유한다.
  • Ex) 여러 사용자가 동일 프로그램 이용 시에 프로그램 자체를 위한 페이지는 공유하여 사용하지만, 각 사용자가 이용하는 데이터를 위한 페이지는 별도로 사용한다.

 

 

5. Page Size

• 페이지의 크기를 결정하는데 있어 고려해야 할 사항 (다양하게 고려해야 함)
• 페이지 크기가 작을수록 프로세스가 *메모리 내의 작업세트(working set)를 확보하는데 도움
  • 그러나, 페이지 크기가 작으면 작을수록 페이지 사상 테이블의 크기가 증가하여 메모리가 낭비됨
• 페이지 크기가 클수록 프로그램 실행 중 가상 메모리로의 입출력 전송 횟수를 줄일 수 있음
  • 그러나, 페이지 크기가 크게 되면 참조되지 않을 많은 정보들까지 주기억장치로 옮겨지게 되어 메모리의 낭비를 초래할 수 있음

*working set : 실행중인 프로세스가 자주 참조하는 페이지들의 집합

 

Page fetch(반입) Method

• Demand Paging 기법 : 실행 중인 프로세스에 의하여 명백히 참조되는 프로세스만이 가상 메모리로부터 메인 메모리(주기억장치)로 적재된다.
• anticipatory paging 기법 : OS가 예측하여 주기억장치에 여유가 있을 때 사용될 것이라고 예상되는 페이지들을 미리 적재한다.

 

(3) Segmentation

• 서로 다른 크기의 블록을 이용하여 이동하는 방법으로 프로그램을 고정 크기 단위(Page)로 분할하는 것이 아닌 논리적으로 관련이 있는 *단위(Segment)로 분할한다.
• 이들 블록을 Segment라고 하고 Segment들로 가상 메모리를 구성한다.
• 가상 주소는 v=(s,d)로 표현된다.
  • s는 세그먼트 번호이고 d는 변위이다.

*Segment : 논리적 단위가 되는 프로그램 모듈이나 자료 구조

 

1. Direct Mapping

• 페이징 기법과 동일하게 직접, 연관, 연관/직접 사상 방법은 다 같다.

페이징 기법과 다른 점은 추가적으로 크기 정보를 가지고 있다는 것이다.

 

2. Segment Mapping Table

• 존재 비트 : 해당 세그먼트가 주기억장치에 존재하는지 여부
• 보조기억 장치 주소 : 세그먼트의 가상 메모리 주소
• 세그먼트 길이 : 세그먼트 기법에만 있고 페이징 기법에는 없다.(이것만 다르고 다 동일함)
• 세그먼트의 시작 주소 : 세그먼트의 실제 메모리 주소

 

3. Share Segment in Segmentation System

• 페이징 시스템과 다르게 세그멘테이션 시스템은 하나의 세그먼트만 공유한다.

 

(4) Segmentation/Paging 혼용 기법

• 가변적인 세그먼트가 너무 커서 주기억장치에 적재할 수 없는 문제 발생 시 해결 방법이다.
• 너무 큰 세그먼트를 정수 배의 페이지로 다시 분할한다.
• 가상 주소는 v=(s,p,d)로 표현한다.
  • s는 세그먼트 번호, p는 페이지 번호, d는 변위이다.
• 연관/직접 사상을 이용한 동적 주소 변환 방법이 있다.

 

(5) Page Replacement Algorithm

새로이 적재될 페이지를 위한 메인 메모리 공간을 확보하기 위해 현재 메인 메모리를 차지하고 있는 페이지들 중 어떤 페이지를 선택하여 가상 메모리 공간으로 보낼 것인가를 결정하는 기법이다.

 

1. FIFO(First In First Out)

• 가장 먼저 메인 메모리에 들어와있는 페이지를 교체시키는 방법으로 가장 간단한 알고리즘이다.
• 하지만 가장 안 좋은 알고리즘으로, 실제로는 쓰이지 않는다.

프로세스에 할당된 주기억장치 내의 페이지 프레임 수를 3개로 가정한다.
여기서 발생한 총 *Page Fault회수는 15번이다.

 

*Page Fault(페이지 부재) : 페이지가 호출되었을 때 메인 메모리에 없는 경우를 뜻한다. 페이지 부재가 적은 것이 좋다.

 

✓ FIFO anomaly(모순) or Belady

• 어떤 페이지 호출에서는 프로세스에 할당된 페이지 프레임의 수가 증가될 때 현실적으로 페이지 부재가 더 증가하는 모순이 발생한다.
• 상식적으로 프레임이 증가하면 페이지 부재가 감소해야 하는데 실제로는 프레임이 증가하면 페이지 부재도 증가한다.

 

2. Optimal Replacement

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체시키는 방법이다.
• 최소의 페이지 부재율을 가지는 알고리즘으로 FIFO의 모순을 피할 수 있다.
• 그러나 이 방법은 페이지 호출 순서에 대한 모든 상황을 사전에 미리 파악하고 있어야 하기 때문에 비현실적이고, 실제 구현이 어려워 쓰이지 않는다.

발생된 총 페이지 부재 회수는 9번이다.

 

3. Least Recently Used(LRU)

• 한 프로세스에서 사용되는 각 페이지마다 타임-스탬프용 카운터나 스택을 두어 현시점에서 가장 오래 전에 사용된 페이지(CPU가 수행된 것)를 제거하는 방법이다.('최근에 사용된 페이지는 제거 안 하겠다'라는 의미.)
• 페이지 사용시간을 기록하기 위해 카운터나 스택의 사용이 필요하다.
• 실제로 많이 쓰고 있지만 구현이 어렵다.

발생된 총 페이지 부재 회수는 12번이다.

 

4. Second Chance

• 오랫동안 주기억장치에 있던 페이지 중에서 자주 사용되는 페이지의 교체를 방지하기 위한 방법으로 FIFO 기법 단점을 보완했다.
• 각 페이지마다 참조 비트를 두고, FIFO 기법을 이용하여 페이지 교체를 수행한다.
  • 참조 비트가 '0'일 경우 해당 페이지를 교체(가상기억장치로 이동)한다.
  • 참조 비트가 '1'일 경우 참조 비트를 '0'으로 만들고 FIFO 리스트의 맨 마지막으로 이동시킨다.
• 교체 대상이 되기 전에 참조 비트를 검사하여 1일 경우에 한번의 기회를 더 부여하기 때문에 '2차 기회' 알고리즘이라고 한다.

 

5. Least Frequently Used(LFU)

• LRU 알고리즘과 유사한 방법으로 각 페이지의 사용이 얼마나 집중적으로 되었는가에 관심을 가지고, 가장 적게 사용되거나 집중적이 아닌 페이지가 대체된다.
• 가장 참조 횟수가 적은 페이지를 교체한다.(사용할 확률이 적어서)

 

6. Not Recently Used(NRU=NUR)

• 최근에 사용되지 않은 페이지는 가까운 미래에 사용되지 않는 경향에 따라 그것들을 참조되는 페이지와 교체시킨다.
• LRU와 유사하나, 구현비용이 낮다.(클럭이나 스택 구현 필요 없음)
• 두 개의 비트를 이용한다.(참조 비트 + 변형 비트) : 11, 10, 01, 00
• 비트에서 숫자가 큰 페이지를 오래 유지한다.

 

(6) Thrashing

다중 프로그래밍에서 하나의 프로세스는 실행을 위해 몇 개의 페이지 프레임을 할당받는다.(Ex:프로세스별 균등 할당, 비례 할당)

 

▶ Thrashing

프로세스를 수행하는데 있어서, 페이지 부재가 계속적으로 발생되어 프로세스가 수행되는 시간보다 페이지 교체에 소비되는 시간이 더 많아지는 경우를 말한다. (메모리가 부족해서)

스래싱을 방지하려면 한 프로세스가 효율적인 수행을 위하여 제공 받아야 할 페이지 프레임의 수를 알아야 한다.

 

✓ 해결방법

구역성 : '프로세스가 기억장치 내의 모든 정보를 균일하게 참조하는 것이 아니라 국부적인 부분만을 집중적으로 참조한다'라는 의미이다. 이러한 구역성을 통하여 페이지 프레임 수를 예측할 수있다.

• 시간 구역성(Temporal Locality) : 최근에 참조된 기억장소가 가까운 장래에도 계속 참조된 가능성이 높음을 의미한다.
  Ex) 순환(looping), 서브루틴, 스택, counting & totaling에 사용되는 변수
• 공간 구역성(Spatial Locality) : 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조되는 경향이 있음을 의미한다.
  Ex) 배열 수행, 순차 코드의 실행(Sequential Code Execution), 프로그래머들이 관련된 변수를 근처에 선언하는 경향이 있다.

 

▶ Working Set(작업 세트)

• 프로세스에 의해 자주 참조되는 페이지들의 집합체를 의미한다.
• 수행 중인 프로세스가 주기억장치 내에 작업세트를 잘 유지하고 있다면, 효율적으로 수행된다.

 

▶ 페이지 부재율

• 주기억장치에 프로세스와 수행에 필요로 하는 페이지가 없는 비율을 말한다.
  • 부재율이 높으면, 그 프로세스가 더 많은 페이지 프레임을 필요로 한다.
  • 부재율이 낮으면, 그 프로세스가 너무 많은 페이지 프레임을 가지고 있다.
• 페이지 부재율의 상한과 하한을 이용하여 페이지 프레임을 동적으로 변경한다.