[운영체제] 8. 가상 메모리

반효경 교수님의 "운영체제와 정보기술의 원리" 책을 학습하고 정리한 글입니다.

 

📌 가상 메모리 (Virtual Memory)

프로세스마다 물리적 메모리와 디스크 스왑 영역에 혼재하여 가지는 주소 공간

• 프로그램을 실행하기 위해 당장 수행할 부분을 메모리에 올려놓고, 그렇지 않은 부분은 디스크 스왑 영역에 내려 놓는다.

 

✍🏻 프로세스 주소 공간 메모리 적재 단위

• 요구 페이징 방식 (Demand paging)
• 요구 세그먼테이션 방식 (Demand segmentation)

대부분 요구 페이징 방식을 사용하며, 요구 세그먼테이션 방식은 대게 페이지드 세그먼테이션 기법을 사용하는 경우다. 즉, 세부 구현은 요구 페이징 기법 만이 사용된다고 볼 수 있다.

 

1. 요구 페이징

프로그램 실행 시 당장 사용될 페이지만을 메모리에 올리는 방식

• 특정 페이지에 대해 CPU 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다.
• 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는데 사용하는 입출력 오버헤드도 감소한다.
• 사용하지 않을 주소 영역에 대한 입출력을 수행하던 기존 방식에 비해 응답시간을 단축시킬 수 있다.
• 시스템이 더 많은 프로세스를 수용할 수 있도록 한다.
• 프로그램이 물리적 메모리의 용량 제약을 벗어날 수 있도록 한다.

 

가상 메모리 기법은 프로세스가 실행되는 동안 일부 페이지만 메모리에 올라와 있고, 나머지는 디스크의 스왑 영역에 존재한다. 이를 위해 프로세스의 어떤 페이지가 메모리에 존재하는지 구별하는 방법이 필요하다. 요구 페이징에서는 유효-무효 비트(valid-invalid bit)를 두어 각 페이지가 메모리에 존재하는지 표시하게 된다. 이 비트는 프로세스의 모든 페이지에 대해 존재해야 하므로, 페이지 테이블의 각 항목별로 저장한다.

 

📌 페이지 부재 (Page fault)

CPU가 참조하려는 페이지의 유효-무효 비트가 무효로 세팅되어 있는 경우

 

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

CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩을 발생시킨다. 그러면 CPU의 제어권이 커널모드로 전환되고, 운영체제의 페이지 부재 처리루틴을 호출하여 처리한다.

 

✍🏻 페이지 부재 처리루틴 과정

1. CPU가 페이지 N을 참조한다.
   • 해당 페이지에 대한 접근이 적법한지 먼저 확인한다.
   • 사용되지 않는 주소 영역에 속한 페이지에 접근하거나, 해당 페이지에 대한 접근 권한 위반을 했을 경우 해당 프로세스를 종료시킨다.
   • ex. 읽기전용 페이지에 대한 쓰기 접근 시도
2. 페이지 테이블에서 페이지 N이 무효 상태임을 확인한다.
3. 페이지 부재 트랩이 발생한다.
4. 디스크에서 부재 페이지를 빈 프레임으로 적재하고 페이지 테이블을 업데이트한다.
   • 물리적 메모리에 비어있는 프레임을 할당받아 그 공간에 해당 페이지를 읽어온다.
   • 만약 비어있는 프레임이 없다면 기존 메모리 페이지 중 하나를 스왑 아웃 시킨다.
   • 요청된 페이지를 디스크로부터 메모리에 적재하기까지는 오랜 시간이 소요되어 CPU를 빼앗기고 봉쇄 상태가 된다.
   • 디스크 입출력 완료 인터럽트가 발생하면 해당 페이지의 유효-무효 비트를 유효로 설정하고, 봉쇄된 프로세스를 준비 큐로 이동시키고 프로세스를 재개한다.

 

1-2. 요구 페이징 성능

요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다. 페이지 부재가 일어나면 페이지를 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생하기 때문이다. 즉, 페이지 부재가 적게 발생할수록 요구 페이징의 성능은 향상될 수 있다.

유효 접근시간(effective access time) 
= (1-P) * 메모리 접근 시간 
+ P * (페이지 부재 발생 처리 오버헤드
       + 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드
       + 요청된 페이지의 스왑 인 오버헤드
       + 프로세스의 재시작 오버헤드)

페이지 부재 발생비율(page fault rate) 0 <= P <= 1
P = 0 : 페이지 부재가 한 번도 일어나지 않은 경우
P = 1 : 모든 참조 요청에서 페이지 부재가 발생한 경우

 

2. 페이지 교체

📌 페이지 교체 (Page replacement)

메모리에 올라온 페이지 중 하나를 스왑 아웃하여 메모리에 빈 공간을 확보하는 작업

• 어떤 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 교체 알고리즘이 존재한다.
• 알고리즘의 목표는 페이지 부재율을 최소화하는 것이다. 그러므로 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 스왑 아웃하는 것이 성능을 향상시킬 수 있는 방안이다.
• 참조되는 페이지들의 번호를 시간 순서로 나열한 페이지 참조열(page reference string)에 대해 페이지 부재율을 계산함으로써 평가할 수 있다.

 

2-1. 최적 페이지 교체

페이지 부재율을 최소화하기 위해 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내면 된다. 이러한 최적의 알고리즘을 빌레디의 최적 알고리즘(Belady's optimal algorithm) 또는 MIN, OPT 등의 이름으로 부른다.

• 빌레디의 최적 알고리즘은 가장 먼 미래에 참조될 페이지를 선정하여 페이지 교체를 진행하게 된다.
• 이 알고리즘은 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전제 하에 알고리즘을 운영하므로 실제 시스템에서 온라인으로 사용할 수 있는 알고리즘은 아니다.
• 이에 따라 어떠한 알고리즘을 사용하는 경우보다도 가장 적은 페이지 부재율을 보장하므로 다른 알고리즘의 성능에 대한 상한선을 제공한다.

 

2-2. 선입선출 알고리즘

선입선출(FIFO, First-In First-Out) 알고리즘은 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.

• 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓아 비효율적일 수 있다.
• FIFO 알고리즘에서 메모리를 증가시켰음에도 불구하고 페이지 부재가 오히려 늘어나는 상황을 FIFO의 이상 현상(FIFO anomaly)라고 부른다.

 

2-3. LRU 알고리즘

메모리 페이지의 참조 성향 중 한 가지 성질로 시간 지역성(temporal locality)이 있는데, 최근 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 말한다. LRU(Least Recently Used) 알고리즘은 페이지 교체 시 가장 오래 전에 참조가 이루어진 페이지를 쫓아내는 방법이다. 즉, 마지막 참조 시점이 가장 오래된 페이지를 교체하는 것이다.

 

2-4. LFU 알고리즘

LFU(Least Frequency Used) 알고리즘은 페이지의 참조 횟수로 교체시킬 페이지를 결정한다.

• 과거에 참조 횟수가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재한다.
• 최저 참조 횟수를 가진 페이지가 여러 개 존재할 경우 임의로 하나를 선정해 그 페이지를 쫓아낸다.

 

✍🏻 페이지 참조 횟수를 계산하는 방식에 따른 분류

• Incache-LFU : 페이지가 물리적 메모리에 올라온 후부터 참조 횟수를 카운트하는 방식
• Perfect-LFU : 메모리에 올라와 있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트하는 방식
  • 페이지 참조 횟수를 정확히 반영할 수 있지만, 메모리에서 쫓겨난 페이지의 참조 기록까지 모두 보관하는 오버헤드 발생

 

✍🏻 LFU 알고리즘의 장단점

• 직전에 참조된 시점만을 반영하는 LRU 알고리즘보다 오랜 시간동안 참조 기록을 반영할 수 있다.
• 시간에 따른 페이지 참조의 변화를 반영하지 못하고, LRU보다 구현이 복잡하다.
• 만약 아주 과거에 여러 번 참조되었다는 이유로, 최근에 참조한 페이지보다 오래 남아 있을 수 있다.

 

2-5. 클럭 알고리즘

클럭 알고리즘(clock algorithm)은 하드웨어적인 지원을 통해 시간적인 알고리즘 운영 오버헤드를 줄인 방식이다.

• LRU/LFU 알고리즘은 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교하므로 알고리즘의 운영에 시간적인 오버헤드가 발생한다.
• LRU를 근사(approximation)시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘으로도 불린다.
• 하드웨어 지원으로 동작하여 LRU에 비해 페이지의 관리가 훨씬 빠르고 효율적으로 이루어진다.
• 따라서, 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다.

 

✍🏻 클럭 알고리즘 동작 원리

• 교체 대상 페이지를 찾기 위해 현재 올라와있는 페이지의 참조 비트 정보를 시계방향으로 따라가며 조사한다.
• 시계바늘이 가리키는 페이지의 참조비트가 1인 경우 참조비트를 0으로 바꾼 후 시계바늘을 한 칸 진행시키고, 참조비트가 0인 페이지를 찾으면 그 페이지를 교체한다.
• 한편, 참조비트는 그 페이지가 참조될 때 1로 자동 세팅되므로, 시계바늘이 한 바퀴 도는 동안 다시 참조되지 않을 경우 페이지를 교체하는 것이다.
• 자주 사용하는 페이지라면 시계바늘이 한 바퀴 도는 동안 참조비트가 1로 세팅되어 교체되지 않는다.

 

이 알고리즘은 최근에 참조가 일어나지 않은 페이지를 교체하는 알고리즘이라고 할 수 있다.

최소 시계바늘이 한 바퀴 도는데 소요되는 시간만큼 페이지를 메모리에 유지시킴으로써 페이지 부재율을 줄이도록 설계되었기 때문에 이 알고리즘을 2차 기회 알고리즘(second chance algorithm)이라고도 부른다.

 

3. 페이지 프레임의 할당

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

 

✍🏻 기본적인 할당 알고리즘(allocation algorithm) 세 가지

1. 균등 할당(equal allocation) : 모든 프로세스에게 페이지 프레임을 균일하게 할당
2. 비례 할당(proportional allocation) : 프로세스 크기에 비례해 페이지 프레임을 할당
   • 프로세스 크기가 모두 동일하지 않음을 고려한 균등할당 방식
3. 우선순위 할당(priority allocation) : 프로세스 우선순위에 따라 페이지 프레임을 다르게 할당
   • 당장 실행할 프로세스와 그러지 않은 프로세스를 구분하여 전자 쪽에 많은 페이지 프레임을 할당하는 방식

 

⇒ 이와 같은 할당 알고리즘만으로는 프로세스의 페이지 참조 특성을 제대로 반영하지 못할 우려가 있다.

• CPU에서 명령을 실행할 때 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하기 때문이다.
• 또한, 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려야, 매 반복마다 페이지 부재를 피할 수 있다.
• 이와 같은 종합적인 상황을 고려하여 각 프로세스에 할당하는 페이지 프레임 수를 결정해야 한다.

 

4. 전역교체와 지역교체

📌 전역교체 (Global replacement)

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

• 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법

📌 지역교체 (Local replacement)

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

• 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 한다.

 

5. 스레싱

프로세스의 원활한 실행을 위해서는 일정 수준 이상의 페이지 프레임을 할당해야 한다.

📌 스레싱 (Thrashing)

최소한의 페이지 프레임을 할당받지 못할 경우 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어지는 현상

 

✍🏻 스레싱이 발생하는 시나리오

운영체제는 CPU 이용률이 낮을 경우 메모리에 올라와 있는 프로세스 수가 적기 때문이라고 판단한다.

• 준비 큐에 프로세스가 단 하나라도 있으면 CPU는 쉬지 않고 일하지만,
• CPU 이용률이 낮다는 것은 준비 큐가 비는 경우가 발생한다는 것이다.
• 이는 메모리의 프로세스 수가 너무 적어 이들 모두가 I/O 작업으로 준비 큐가 비는 경우가 발생했다는 뜻이다.
• 따라서 CPU 이용률이 낮으면 운영체제는 메모리에 올라가는 프로세스 수를 늘리게 된다.
• 즉, CPU 이용률이 낮으면 운영체제는 MPD를 높이게 된다.
  • MPD (Multi-Programming Degree) : 다중 프로그래밍 정도
• 그런데 MPD를 과도하게 높이면 각 프로세스에 할당되는 메모리의 양이 지나치게 감소하게 된다.
• 이에 따라 각 프로세스는 그들이 원활하게 수행하기 위한 최소한의 페이지 프레임도 할당받지 못하는 상태가 되어 페이지 부재가 빈번히 발생하게 된다.
• 페이지 부재는 디스크 I/O 작업을 수반하므로, 문맥교환을 통해 다른 프로세스에게 CPU가 이양된다.
• CPU를 할당받은 프로세스도 할당받은 메모리 양이 지나치게 적으면 페이지 부재가 발생할 수 밖에 없다.

 

프로세스들은 서로 페이지를 교체하며 스왑 인과 스왑 아웃을 지속 발생시켜 CPU가 대부분 일하지 않는 스레싱이 발생하게 된다. 따라서 스레싱이 발생하지 않도록 하면서 CPU 이용률을 최대한 높일 수 있도록 MPD를 조절하는 방법이 크게 (1)워킹셋 알고리즘과 (2)페이지 부재 빈도 알고리즘이 있다.

 

5-1. 워킹셋 알고리즘

프로세스는 일정 시간동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다.

📌 지역성 집합 (locality set)

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

📌 워킹셋 알고리즘 (working-set algorithm)

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

📌 워킹셋 (working-set)

프로세스가 일정시간동안 원활히 수행하기 위해 한꺼번에 메모리에 올라가야 하는 페이지들의 집합

• 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다.
• 만약 그렇지 않을 경우 프로세스에게 할당한 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 스왑 아웃 시킨다.
• 이와 같은 방식으로 워킹셋 알고리즘은 MPD를 조절하고 스레싱을 방지하게 된다.

 

✍🏻 워킹셋을 구하는 방법

• 한꺼번에 메모리에 올라가야 할 페이지들의 집합을 결정하기 위해 워킹셋 윈도우(working-set window)를 사용한다.
• 윈도우 크기 Δ 및 시각 t에 따라 워킹셋은 시간 간격 사이에 참조된 서로 다른 페이지들의 집합으로 정의한다.
• 각 시점의 워킹셋에 포함된 페이지들은 메모리에 유지하고, 그렇지 않은 페이지들은 스왑 아웃 시킨다.
• 이는 달리 표현하면 참조된 시점부터 Δ 시간동안 메모리에 유지하고, 그 시점이 지나면 메모리에서 지워진다.

 

워킹셋 알고리즘은 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임의 수보다 클 경우 일부 프로세스를 스왑 아웃 시켜서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장한다. 이는 MPD를 줄이는 효과를 발생시킨다.

 

반면 프로세스들의 워킹셋을 모두 할당한 후에도 프레임이 남을 경우, 스왑 아웃 시켰던 프로세스를 다시 메모리에 올려 워킹셋을 할당함으로써 MPD를 증가시킨다.

 

이러한 방식으로 워킹셋 알고리즘은 CPU 이용률을 높게 유지하면서 MPD를 적절히 조절해 스레싱을 방지한다.

 

5-2. 페이지 부재 빈도 알고리즘

페이지 부재 빈도 알고리즘(PFF, Page Fault Frequency)은 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절하는 방식이다.

• 어떤 프로세스 페이지 부재율이 시스템에서 미리 정해놓은 상한값을 넘게 되면 이 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 이 프로세스에게 프레임을 추가로 더 할당한다.
• 이때 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라가 있는 프로세스의 수를 조절한다.
• 반면, 프로세스 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상의 프레임이 할당된 것으로 간주해 할당된 프레임 수를 줄인다.

 

이러한 원리로 MPD를 조절하면서 CPU 이용률을 높이는 동시에 스레싱을 방지한다.

 

참고자료

• 📚 운영체제와 정보기술의 원리 (반효경, 2020년 5월)