[OS] 공룡책_10 가상 메모리

10.1 배경

프로그램을 실행하기 위해 전체 프로세스를 메모리에 적재해야한다면 여러가지 비효율적인 부분들이 생긴다.

• 잘 사용하지 않는 코드, 데이터가 메모리 공간을 차지한다. (오류 처리 코드, 미리 선언된 배열 및 리스트)

• 메모리 크기보다 큰 프로그램을 실행할 수 없다.

이를 해결하기 위해 가상 메모리 개념을 도입한다.

가상 메모리

• 실제 물리 메모리 개념과 개발자의 논리 메모리 개념을 분리한다.

  • 물리 메모리는 페이지 프레임(page frame)들로 구성된다.
  • 메모리 관리 장치에 의해 논리적인 페이지에 물리적인 페이지를 할당한다.

• 메모리가 둘 또는 그 이상의 프로세스들에 의해 공유되는 것을 가능하게 한다.

10.2 요구 페이징 (Demand Paging)

실제로 메모리 할당이 필요할 때 논리 메모리를 물리 메모리에 적재함으로써 효율적으로 메모리를 사용하는 전략이다.

• 프로세스가 보조 메모리에 상주하는 사와핑을 사용하는 페이징 시스템과 유사하다.

10.2.1 기본 개념

기본적으로 유효/무효 비트를 페이지 테이블에 함께 저장하고 사용한다.

• 유효인 경우 해당 페이지가 메모리에 있음을 의미한다.
• 무효인 경우 해당 페이지가 보조저장장치에 없거나 가상 주소 공간상에 정의되지 않았음을 의미한다.

프로세스가 메모리에 올라와 있지 않은 페이지에 접근하려고 하면 운영체제는 페이지 폴트 트랩(page-fault trap)을 발생시킨다.

페이지 폴트 트랩

1. 무효한 페이지에 대한 참조라면 프로세스를 중단, 유효하지만 아직 메모리에 올라오지 않았다면 페이지를 보조 저장 장치로부터 가져온다.

2. 가용 프레임을 찾는다.

3. 새롭게 할당된 프레임에 페이지를 읽어들이고, 프로세스가 유지하는 내부 테이블을 수정한다.

요구 페이징을 위한 필수적인 요구 사항은 페이지 폴트 오류 처리 후에 명령어 처리를 정확히 같은 시점에서 다시 시작할 수 있어햐 한다는 것이다.

10.2.2 가용 프레임 리스트

페이지 폴트 발생 시 사용 가능한 프레임을 찾을 때 사용되는 자료구조이다.

운영체제는 일반적으로 zero-fill-on-demand라는 기법을 사용하여 프레임을 할당할 때 0으로 채워서 이전의 내용을 지우는 전략을 사용한다.

10.2.3 요구 페이징의 성능

요구 페이지는 시스템 성능에 큰 영향을 줄 수 있다.

실질 접근 시간

실질 접근 시간 =  (1-p) * ma + p * 페이지 폴트 소요 시간
*p = 페이지 폴트 확률, ma = 메모리 접근 시간

페이지 폴트 처리 시간에 큰 작업 요소는 다음과 같다.
1. 인터럽트 처리
2. 페이지 읽기
3. 프로세스 재시작

메모리 접근 시간에 비해 페이지 폴트 처리 시간이 더 영향이 크다.
따라서, 실제 접근 시간은 페이지 폴트율에 비례한다.

10.3 쓰기 시 복사

fork()시스템 콜을 호출할 때 요구 페이징 기법을 활용하여 메모리 사용 효율을 높인다.

• 부모 프로세스가 자식 프로세스를 생성할 때 기존에 메모리 자체를 모두 복사하는 것 대신에 부모 페이지를 당분간 함께 사용한다.

• 이후 둘 중 한 프로세스가 공유 페이지에 쓸 때 그 페이지의 복사본을 만들어 새로운 프레임을 할당하는 방식이다.

10.4 페이지 교체

물리 메모리는 한정적이다. 프레임(물리 메모리)이 모두 페이지(논리 메모리)에 할당된 상태에서 새로운 페이지가 메모리 할당을 요구한다면, 기존에 있던 페이지를 제거하고 교체해야한다.

이 상황에서 운영체제는 몇 가지 선택을 할 수 있지만 대부분의 운영체제는 스와핑과 페이지 교체를 결합한다.

10.4.1 기본적인 페이지 교체

페이지 폴트 서비스 루틴은 다음과 같다.

1. 보조저장장치에서 필요한 페이지의 위치를 알아낸다.
2. 빈 페이지 프레임을 찾는다.
   a. 있다면 해당 프레임을 사용한다.
   b. 없다면 희생될 프레임을 선정하기 위해 페이지 교체 알고리즘을 가동시킨다.
   c. 희생될 페이지를 보조저장장치에 기록하고(필요시), 관련 테이블을 수정한다.
3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정한다.
4. 프로세스를 진행한다.
   

• 기본적으로 필요한 페이지를 읽어오는데 한 번, 빈 프레임이 없는 경우 희생될 페이지를 결정한 후 해당 페이지를 저장하는데 한 번, 총 두번의 보조저장장치 접근이 필요하다.
  -> 변경 비트를 사용하여 최적화 한다.

변경 비트

• 각 페이지나 프레임은 그것과 관련된 변경비트를 하드웨어에 가진다.
• 페이지가 변경되면 변경비트를 설정한다.
• 페이지가 변경된 경우에만 페이지 희생 시 보조저장장치에 변경 내용을 저장한다.

요구페이징 시스템에서 고려해야 하는 두가지 사항은 프레임 할당(frame-allocation) 알고리즘과 페이지 교체(page-replacement) 알고리즘이다.

일반적으로 페이지 폴트 횟수를 적게 하는 것이 시스템 전체 성능을 향상시키는 방법이다.

10.4.2 FIFO 페이지 교체 (First-in First-out Page Replacement)

• 선입선출 알고리즘이다.
• 가장 간단하다
• 이해하기 쉽고 구현도 간단하다.

하지만 성능 향상에 좋지 않다.

Belady의 모순

FIFO의 문제점 중 하나이다.
상식적으로 할당된 프레임의 개수가 증가할수록 페이지폴트 횟수가 적어져야 한다.

• FIFO에서는 3개의 프레임 할당 시 9번, 4개의 프레임 할당 시 10번이 발생하는 모순이 존재한다.

10.4.3 최적 페이지 교체 (Optimal Page Replacement)

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 방법이다.

가장 이상적인 알고리즘이지만, 실제 구현은 어렵다.
프로세스가 앞으로 진행될 상황을 미리 알 수 없기 때문이다.

따라서 이 알고리즘은 다른 알고리즘 성능 판단의 기준으로 사용한다.

10.4.4 LRU 페이지 교체 (Least-Recently-used Page Replacement)

• 미래를 보는 것은 불가능하니, 과거를 통해 미래를 예측한다.
• 가장 오랜 기간동안 사용되지 않은 페이지를 교체하는 방법이다.

LRU 정책을 구현하기 위해서는 하드웨어의 지원이 필요하다.

• 계수기(counters): 페이지에 대한 참조가 일어날 때마다 사용 시간 필드에 마지막 참조 시간을 유지한다.
• 스택: 페이지가 참조될 때마다 페이지 번호를 스택의 최상단으로 위치시킨다. 가장 밑에 있는 페이지가 교체 대상이 되는 페이지다.

두 LRU 구현 방법 모두 하드웨어의 지원이 필요하다. 소프트웨어로 구현하기 위해 인터럽트를 사용하면 최소 10배 이상 메모리 참조 속도가 느려지고 시스템 성능을 저하시킨다.

10.4.5 LRU 근사 페이지 교체

LRU 페이지 교체에 필요한 하드웨어가 없는 시스템에서 참조비트를 이용해 근사하게 구현한다.

• 페이지마다 참조 비트를 유지하며, 페이지가 참조될 때 해당 비트를 업데이트 한다.

10.4.5.1 부가적 참조 비트 알고리즘 (Additional-Reference Bits Algorithm)

특정 주기마다 운영체제가 인터럽트를 걸어서 참조비트를 업데이트 한다.

• 참조비트를 8비트 정보의 최상위 비트로 이동시키고 나머지 비트들을 오른쪽으로 한 칸씩 이동시킨다.
• 이 정보값을 이용하여 가장 마지막으로 사용된 페이지, 더 많이 사용된 페이지에 대한 정보를 알아낸다.

10.4.5.2 2차 기회 알고리즘 (Second-Chance Algorithm)

FIFO에서 참조비트를 활용하여 기회를 주는 알고리즘이다.

• 참조비트가 0이면 페이지를 교체한다.
• 참조비트가 1이면 참조비트를 0으로 바꾸로 넘어간다.
  

10.4.5.2 개선된 2차 기회 알고리즘

참조비트와 함께 변경 비트를 이용하여 성능을 개선한다.
1. (0,0) 최근에 사용 X, 변경 X -> 교체하기 가장 좋은 페이지
2. (0,1) 최근에 사용 X, 변경 O -> 디스크에 변경 내용을 기록할 필요가 생긴다.
3. (1,0) 최근에 사용 O, 변경 X -> 다시 사용될 가능성이 높으므로 페이지 폴트 발생확률이 증가한다.
4. (1,1) 최근에 사용 O, 변경 O -> 페이지 교체에 적당하지 않다.

10.5 프레임의 할당 (Allocation of Frames)

교체할 페이지를 고르는 것과 더불어 중요한 문제로 어떤 프로세스에 얼마만큼의 프레임을 할당할 것인지 결정하는 알고리즘이 필요하다.

10.5.1 최소 할당 프레임 수 (Minimum Number of Frames)

최소 프레임 수는 아키텍처에 의해 결정된다.

• 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 폴트율은 증가하고 프로세스 실행이 늦어진다.
• 명령어 수행 중 페이지 폴트가 발생하면, 명령어는 재실행된다. -> 명령어가 참조하는 모든 페이지는 메모리에 올라와 있어야 한다.

명령어 실행에 필요한 최소 프레임도 할당되지 않는다면 프로세스 실행 자체가 불가능해진다.

10.5.2 할당 알고리즘 (Allocation Algorithms)

• 균등 할당
  - 모든 프로세스에 같은 크기의 프레임을 할당한다. (운영체제가 사용하는 프레임은 제외된다.)
  - 더 적은 프레임으로 작동하는 프로세스에 할당되는 경우 프레임 낭비가 발생한다.
• 비례할당
  - 각 프로세스의 크기 비율에 맞추어 할당한다.
  

10.5.3 전역 대 지역 할당 (Global Versus Local Allocation)

프레임 할당을 위해 경쟁하는 환경에서 페이지 교체 알고리즘은 크게 두가지 범주로 나뉜다.

• 전역교체(golbal replacement): 다른 프로세스에 속한 프레임을 포함에 모든 프레임을 대상으로 교체할 프레임을 찾는 경우

• 지역 교체(local replacement): 각 프로세스가 자신에게 할당된 프레임 중에서만 교체될 희생자를 선택한다.

10.6 스래싱 (Thrashing)

프로세스에 충분한 프레임이 할당되지 않는 경우, 페이지 폴트가 반복해서 일어난다. 이러한 과도한 페이징 작업을 스래싱(thrashing)이라고 부른다.

실제 실행보다 더 많은 시간을 페이징에 사용하고 있으면 스래싱이 발생했다고 한다.

10.6.1 스래싱의 원인

프로세스가 추가 프레임이 필요한 경우 전역 페이지 교체 알고리즘을 사용하여 다른 프로세스의 페이지 프레임을 가져온다.

이때 해당 프레임을 가져옴으로써 뺏긴 프로세스도 페이지 폴트가 반복적으로 발생하고 다른 프로세스의 프레임을 뺏는 악순환이 반복된다.

페이지 폴트 처리과정에서 CPU이용률은 떨어지고 CPU 스케줄러는 이용률을 높이기 위해 다중 프로그래밍 정도를 높인다.

지역교체 알고리즘을 사용할 수 있지만 문제가 완전히 해결되지는 않는다. 페이징하는 경우 페이징 장치 대기열이 길어지기 때문에 페이지 폴트 평균 서비스 시간이 늘어난다.

근본적인 문제를 해결하려면 페이지 폴트 자체를 줄여야한다.

한 가지 전략은 지역성 모델(locality model)을 기반으로 프로세스가 최소로 필요로 하는 프레임 수를 알아내고 그만큼은 할당해 주는 것이다.

• 프로세스가 실행될 때 항상 어떤 특정 지역에서만 메모리를 집중적으로 참조한다.

• 지역성을 포함하기에 충분한 프레임을 제공한다면 특정 지역에 해당하는 모든 페이지가 올라온 후, 그 지역이 변경되기 전까지 페이지 폴트를 발생시키지 않는다.

10.6.2 작업 집합 모델 (Working-Set Model)

• 운영체제가 특정 횟수만큼의 페이지 참조동안 참조한 페이지들을 작업집합이라고 부른다.
• 이 작업집합을 추적하여 각 프로세스에 작업 집합 크기에 맞는 충분한 프레임을 할당한다.

페이지 폴트율이 높아졌는데 그 프로세스에 줄 수 있는 가용프레임이 없으면, 한 프로세스를 선택하여 그 프로세스를 예비 저장장치로 스왑 아웃시켜야 한다.

현실적으로 스래싱과 그에 따른 스와핑은 성능에 큰 영향을 미친다. 이를 피하기 위한 현재 최선책은 모든 작업 집합을 동시에 메모리에 적재할 만큼 충분한 메모리를 제공하는 것이다.