08. 가상메모리

프로그램이 CPU에서 실행되려면 실행에 필요한 부분이 메모리에 올라와 있어야한다. 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어 사용하는데 어느 정도의 메모리를 할당할 것인가에 대한 문제를 해결할 필요가 있다.


운영체제는 공평하게 같은 크기의 메모리를 할당하기 보다 집중적으로 메모리를 할당하고 다시 메모리를 회수해 다른 프로그램에 메모리를 할당하는 방식을 선택한다.


프로그램이 실행되기 위해 그 프로세스의 주소 공간 전체가 메모리에 올라갈 필요는 없다. CPU에서 당장 수행해야 할 부분만 올려두고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓는다.
이렇게 되면 자기 자신만의 메모리 주소 공간을 가정할 수 있는데 이러한 메모리 공간을 가상메모리라고 한다.

가상메모리

: 프로세스마다 각각 0번지부터 주소공간을 가지게 되며, 이 공간 중 일부는 물리적 메모리에 적재되고, 일부는 디스크의 스왑 영역에 존재한다.
적재 방식으로는 요구 페이징과 요구 세그먼테이션이 있다.

요구 페이징

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

• 메모리 사용량이 감소
• 프로세스 전체를 메모리에 올리는데 소요되는 입출력 오버헤드도 줄인다.
• 응답시간 단축
• 시스템이 더 많은 프로세스를 수용
• 프로그램이 물리적 메모리의 용량 제약을 벗어날 수 있도록 한다.

유효-무효 비트

: 어떤 페이지가 메모리에 올라와 있는지 구별하기 위해 사용하고 페이지 테이블의 각 항목별로 저장된다.

CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 '페이지 부재'가 일어났다고 한다.

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

1. CPU가 무표 페이지에 접근시 주소 변환을 담당하는 하드웨어 MMU가 페이지 부재 트랩을 발생
2. CPU의 제어권이 커널모드로 전환
3. 운영체제의 페이지 부재 처리 루틴 호출되어 페이지 부재를 처리

→ 페이지를 메모리에 적재하기 전 해당 페이지에 대한 접근이 적합한지 먼저 확인

요청된 페이지를 디스크로 부터 메모리로 적재하는데 오랜 시간이 소요된다.
따라서 페이지 부재를 발생시킨 프로세스는 CPU를 뺏기고 봉쇄상태가 된다.
수행되던 CPU 레지스터 상태 및 프로그램 카운터 값을 프로세스 제어블록에 저장해 이 프로세스가 다시 CPU를 할당받을 때와 같은 상태에서 디스크로 부터 메모리를 적재한다.

적재 방법

1. 디스크 입출력이 완료되어 인터럽트 발생
2. 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정
3. 봉쇄되었던 프로세스를 준비큐로 이동
4. CPU를 할당받으면 프로세스 제어블록에 저장해두었던 값을 복원

요구 페이징의 성능

: 성능에 가장 큰 영향을 미치는 것은 페이지 부재의 발생 빈도이다.
유효 접근시간이 짧을 수록 요구 페이징 기법의 성능은 향상된다.

페이지 교체

: 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야한다.
이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
메모리에 올라와 있는 페이지 중 하나를 디스크로 쫒아내 메모리에 빈 공간을 확보하는 작업

• 교체 알고리즘 : 페이지 교체를 할 때 어떤 프레임에 있는 페이지를 쫒아낼 것인지 결정하는 알고리즘
  • 페이지 부재율 최소화 : 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택행 성능 향상
• 페이지 참조열 : 참조되는 페이지들의 번호를 시간 순서에 따라 나열

최적 페이지 교체(=MIN, OPT)

: 먼 미래에 참조될 페이지를 쫒아내는 방식

• 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하기 때문에 온라인으로 사용하는 알고리즘은 아니다.
  → 오프라인 알고리즘

선입선출 알고리즘

: 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫒는다.
페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫒을 대상을 선정하기 때문에 비효율적

• 물리적 메모리의 공간이 늘어나도 성능이 나빠질 수 있음
  → FIFO의 이상 현상

LRU 알고리즘

시간지역성

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

LFU 알고리즘

: 페이지의 참조 횟수로 교체시킬 페이지를 결정.
과거에 참조 횟수가 가장 적었던 페이지를 쫒아내고 그 자리에 새로 참조될 페이지를 적재한다.
최저 참조 횟수를 가진 페이지들 중에서도 상대적으로 더 오래전에 참조된 페이지를 쫒아내도록 구현하는 것이 효율적이다.

참조 횟수 계산 하는 방식

• Incache-LFU
  : 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트 하는 방식
  페이지가 메모리에서 쫒겨났다가 다시 들어온 경우 참조 횟수를 다시 1부터 카운트
• Perfect-LFU
  : 메모리에 올라와 있는지 여부와 상관없이 페이지의 총 참조 횟수를 카운트
  • 페이지의 참조 횟수를 정확히 반영할 수 있다는 장점
  • 메모리에서 쫒겨난 페이지의 참조 기록까지 모두 보관해야해 오버헤드가 상대적으로 더 큼

LFU 알고리즘 & LRU 알고리즘

• LFU 알고리즘
  : 오랜 시간 동안의 참조 기록을 반영할 수 있는 장점
• LRU 알고리즘
  : 시간에 따른 페이지 참조의 변화를 반영하고 LRU 보다 구현이 복잡하다는 단점이 있음

클럭 알고리즘(NUR-Not Used Recently, NRU-Not Recently Used)

: 하드웨어적인 지원을 통해 이와 같은 알고리즘의 운영 오버헤드를 줄인 방식.
오랫동안 참조되지 않은 페이지 중 하나를 교체.
하드웨어적인 지원으로 동작하기 때문에 LRU에 비해 페이지의 관리가 훨씬 빠르고 효율적으로 이뤄진다.

• 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트를 순차적으로 조사

참조비트

: 각 프레임마다 하나씩 존재하고 참조될 때 하드웨어에 의해 1로 자동 세팅된다.
참조비트가 1인 페이지는 0으로 바꾼 후 그냥 지나가고 참조비트가 0일 페이지는 교체

• 참조비트 정보는 시계방향으로 따라가며 조사
• 시곗바늘이 가리키는 페이지의 참조비트가 비트가 1인 경우 클럭 알고리즘은 참조비트를 0으로 바꾼 후 시곗바늘을 한 칸 진행시키고 참조비트가 0인 페이지를 찾으면 그 페이지를 교체

페이지 프레임의 할당

: 여러 프로세스가 수행될 때 메모리 공간을 할당하는 방법이 필요한데 이 때 할당 알고리즘이 사용된다.

할당 알고리즘

• 균등할당
  : 모든 프로세스에게 페이지 프레임을 균일하게 할당
• 비례할당
  : 프로세스의 크기에 비례해 페이지 프레임 할당
• 우선순위 할당
  : 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당

프로세스를 정상적으로 수행하기 위해 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야 한다.
반복문을 실행중이라면 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올리는 것이 유리하다.
프로세스에게 최소한으로 필요한 메모리의 양은 시간에 따라 다를 수 있다.

전역교체와 지역교체

• 전역교체
  : 모든 페이지 프레임이 교체 대상이 될 수 있는 방법
  • 교체 알고리즘에 근거해 할당되는 메모리 양이 가변적으로 변하는 방법
  • 페이지 교체 시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있는 방식
• 지역교체
  : 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법
  • 페이지 프레임을 미리 할당하는 것을 전제
  • 프로세스별로 페이지 프레임을 할당하고 교체할 페이지도 그 프로세스에게 할당되 ㄴ프레임 내에서 선정하게 되는 것
    → LRU,LFU를 독자적으로 운영할 때 지역교체 방법 사용

스레싱

: 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율이 크게 상승해 CPU 이용률이 떨어질 수 있는데 이것을 스레싱이라고 한다.

스레싱 발생 시나리오

1. CPU 이용률이 낮을 경우 운영체제는 MPD를 높이게 된다.
2. MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소된다.
3. 각 프로세스는 그들이 원할하게 수행되기 위해 필요한 최소한의 페이지 프레임도 할당받지 못하는 상태가 된다.
4. 페이지 부재가 발생하면 디스크 I/O 작업을 수반해 문맥교환을 통해 다른 프로세스에게 CPU가 이양된다.
5. 이때 다른 프로세스 역시 메모리 양이 적으면 페이지 부재가 발생한다.
6. 이것이 반복되어 준비 큐에 있는 모든 프로세스에 CPU가 할당되어도 페이지 부재를 발생시키면 스왑 인/아웃을 지속적으로 발생시켜 CPU는 대부분 시간에 일을 하지 않게 된다.

• MPD와 CPU 이용률의 상관관계
  

: 메모리 내에 존재하는 프로세스의 수를 증가시키면 CPU 이용률은 이에 비례해 증가된다. 한계치를 넘어서면 CPU 이용률이 급격히 떨어져 스레싱이 발생해 CPU이용률을 최대한 높일 수 있도록 MPD를 조절해야 한다.
CPU 이용률을 높이고 스레싱을 방지하는 방법에는 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 있다.

워킹셋 알고리즘

: 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘.
프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메로리에 올라와 있어야하는 페이지들의 집합을 워킹셋이라고 정의.
프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당

지역성 집합

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

• 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임 수보다 클 경우 일부 프로세스를 스왑아웃 시켜 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장

페이지 부재 빈도 알고리즘

: 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근그해 각 프로세스에 할당할 메모리 양을 동적으로 조절

• 미리 정해놓은 상한값을 넘게 되면 이 프로세스의 할당된 프레임 수가 부족하다고 판단해 이 프로세스에게 프레임을 추가로 할당
• 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임 수를 줄인다.
  → 이러한 원리로 MPD를 조절하면서 CPU이용률을 높이는 동시에 스레싱을 방지한다.