[운영체제와 정보기술의 원리] 8장 가상 메모리

현대의 시분할 시스템에서는 여러 프로세스가 동시에 메모리에 올라와있다.

다만 프로세스의 모든 주소영역을 올리는것이 아닌

실제로 수행에 필요한 부분만 메모리에 올라와있다. (그렇지 않은 부분은 백킹 스토어에 저장)

 

이로인해 프로세스는 메모리 공간의 제약없이 0번부터 시작하는 메모리 공간을 홀로 사용한다고 느낀다.

실제 물리적 공간과 달리 0번 부터 시작하는 프로세스의 독자적인 메모리 공간을 가상 메모리(논리적 메모리)라고 한다.

 

그렇다면 프로세스의 주소공간을 메모리에 어떤 단위로 적재할것인지를 결정해야한다.

• 요구 페이징(demand paging) : 대부분 이 방식을 사용.
• 요구 세그멘테이션(demand segmentation) : 사용하더라도 하나의 세그먼트를 여러개의 페이지로 나누는,
  페이지드 세그먼테이션 기법을 주로 사용.

✅요구 페이징

demand paging. 즉 필요할때 메모리에 올리겠다는 말이다.

현재 필요한 부분만 메모리에 올리기 때문에 메모리보다 큰 프로그램도 실행이 가능하고

일부만 올리기 때문에 프로세스 전체를 메모리에 올릴때의 오버헤드가 발생하지 않는다.

 

 

실제로 메모리에 최초 접근시 모든 페이지는 메모리에 올라와있지 않다.

이후 메모리에 접근할때 그때 메모리 공간으로 적재하는것이다.

구체적으로 메모리에 존재하지 않는지(페이지 폴트) 여부를 페이지 테이블 항목에 valid-invalid bit 로 표시한다.

이를 통해 페이지 폴트시 스왑 영역에서 가져올수 있다.

 

페이지 폴트

구체적으로 페이지 폴트시 처리 시나리오는 다음과 같다.

 

• 페이지 폴트 발생시 주소 변환을 담당하는 하드웨어 MMU가 페이지 부재 트랩(page fault trap)을 발생시킨다.
• 그러면 CPU의 제어권이 사용자 프로그램에서 OS로 넘어간다. 커널모드 진입.
• OS는 처리 루틴이 실행되는데 이때 옳바른 주소값 접근인지(다른 프로세스의 주소영역을 침범하진 않았나),
  해당 페이지에 대한 접근 권한이 있는지(read, write, read-only 등)를 먼저 검사한다.
• 적절한 접근이라고 판단하면 물리적 메모리의 프레임 하나를 할당시킨다.
• 만약 빈 프레임이 없다면 특정 프레임을 스왑 아웃시킨다. (어떤 기준으로 하는지는 이후에)
• 실제 물리 디스크에서 메모리로 페이지를 적재하는데는 오랜 시간이 걸린다.
  그래서 해당 프로세스는 block state로 진입한다.
• 입출력 과정이 끝나면 페이지 테이블에 valid bit를 활성화시키고 해당 프로세스를 다시 ready state로 진입시킨다.

요구 페이징 성능

페이지 폴트는 디스크에 접근하므로 굉장히 비싼 작업이다.

따라서 요구 페이징의 성능은 곧 페이지 폴트의 횟수를 줄이는것이다.

 

다음은 메모리에 접근할때의 성능 지표인 유효 접근시간이다.

여기서 P는 0~1 값으로 페이지 폴트가 발생할 확률이다.

 

페이지 폴트가 발생하지 않고 hit 했다면 단순히 메모리 접근시간만큼만 시간이 든다.

하지만 페이지 폴트시 처리 루틴, 스왑아웃, 스왑 인, 문맥교환 등 다양한 오버헤드가 발생한다.

즉 어떻게든 페이지 폴트 횟수를 줄여야한다.

 

✅페이지 교체 알고리즘

위에서 메모리에 프레임이 모두 사용중인데 페이지 폴트가 발생하면

특정 프레임을 스왑 아웃시켜야한다고 했다.

이를 페이지 교체(page replacement)라고 한다.

 

페이지 교체 과정은 페이지 폴트 과정과 거의 동일하다.

 

중요한것은 어떤 페이지를 교체할것인가. 즉 '어떤 페이지를 스왑 아웃시킬것인가' 이다.

이를 결정해주는것이 페이지 교체 알고리즘이다.

 

최적 페이지 교체

페이지 교체 알고리즘중 가장 이상적인 상황이다. 즉 상한선(upper bound)를 제공하는 알고리즘이다.

 

참조열 : 사용되는 페이지 번호 순서.

성능을 따질때 동일한 참조열에서 얼마나 페이지 폴트가 적게 일어나는가를 따진다.

 

• 옵티멀한 알고리즘 답게 방법은 미래를 예측하는것이다.
• 스왑 아웃 후보들 가운데 가장 늦게 참조될 페이지를 스왑 아웃시킨다.
• 하지만 실제로는 어떤 페이지가 참조될지 알 수 없기에 상한선 지표로 비교하는 알고리즘이다.

선입선출 알고리즘

가장 간단한 방법으로 선입선출(FIFO)으로 먼저 도착한 페이지를 쫓아낸다.

 

단순한 방식으로 인해 비효율적인 상황이 발생한다.

특정 페이지가 자주 참조되더라도 이와 상관없이 처음에 올라온 페이지가 먼저 나간다.

 

위 그림을 보면 페이지를 3개에서 페이지 폴트가 9번 발생해서

4개로 늘렸는데 이번엔 10번으로 오히려 늘었다. 이를 FIFO의 이상현상이라고 한다.

 

LRU(Least Recently Used)

페이지 교체 알고리즘의 중요한 지표중 하나는 시간 지역성(temporal locality)이다.

페이지가 참조되는 시간이 모여있다는 말이다.

 

LRU 알고리즘은 이러한 시간 지역성을 기반해,

페이지 폴트시 가장 오래전에 참조된 페이지가 나가게 된다.

 

위 그림의 예시에서는 총 8번의 페이지 폴트가 발생한다.

 

LFU(Least Frequently Used)

이번에는 빈도를 확인하는 알고리즘이다.

많이 참조된 페이지가 더 오래 살아남는다.

그래서 페이지 폴트시 가장 적게 참조된 페이지가 나가게된다.

 

LFU는 구현방식에 따라 2가지로 나뉜다.

• Incache-LFU : 스왑 인되면 참조 카운트가 1이 된다. 메모리에 있는 페이지만 횟수를 체크한다.
• Perfect-LFU : 스왑 아웃되도 참조 카운트를 유지한다. 모든 페이지의 카운트를 체크한다.

Perfect 방식은 모든 기록을 다 저장해 더 많은 통계치를 갖고있지만 그만큼 오버헤드가 크다.

 

LFU는 참조횟수만 카운트하기때문에 예전에 많이 참조된 페이지가 현재 사용되지 않더라도

스압 아웃되지 않고 살아남게된다.

 

클럭 알고리즘

LRU 알고리즘을 수정한 알고리즘이다.

그래서 NRU(Not Recently Used) 라고도 불린다.

 

하드웨어 자원을 사용하여 LRU에 비해 훨씬 빠르기 때문에,

대부분의 현대 시스템에서 페이지 교체 알고리즘으로 사용된다.

 

방법은 간단한다. 시계 바늘이 돌면서 1이면 0으로 바꾸고 0이면 스왑 아웃시킨다.

최근에 참조된 페이지는 살려두되, 바늘이 한바퀴 도는 동안 참조 되지 않은 페이지는 스왑 아웃된다.

 

프로세스마다 얼만큼의 페이지를 할당할것인가?

우리가 사용할 수 있는 페이지는 한정적이다.

그래서 이 한정적인 자원인 페이지를 프로세스마다 어떻게 할당할 것인가는 중요한 문제이다.

 

기본적으로 3가지 방식을 생각해볼 수 있다.

• 균등할당(eqaul allocation) : 프로세스마다 페이지를 동등하게 할당.
  프로세스의 크기를 고려하지 않아 작은 프로세스와 큰 프로세스가 동일한 페이지 갯수를 할당받는다.
• 비례할당(proportional allocation) : 프로세스 크기에 비례하여 할당.
  프로세스의 크기만큼만 적당하게 페이지를 할당받는다.
• 우선순위 할당(priority allocation) : 우선순위에 따라 페이지를 할당.
  CPU가 당장 필요한 페이지(실행중인 프로세스의 페이지)를 먼저 할당시킨다.

 

하지만 위와 같은 방식만으로는 페이지의 특성을 모두 고려하지 못한다.

• 현재 실행중인 프로세스가 많다면 프로세스당 할당받는 페이지 수가 급격하게 적어진다.
• 프로세스가 실행중일땐 주소영역에 다양한 부분을 참조하므로
  일정 수준 이상의 페이지가 할당됨을 보장해줘야한다.
• 반복문의 경우 지속적인 페이지 폴트가 발생할 수 있다.
  이럴때는 미리 페이지를 한꺼번에 메모리에 올려두는것이 유리하다.

즉 프로세스마다 페이지를 할당하는 문제는 각 특성을 고려해야한다.

 

전역 교체, 지역 교체

이번엔 페이지를 교체하는 방법에 대한 이야기다.

• 전역 교체 : 페이지 교체 대상이 전체 페이지. 물리적 메모리를 다같이 공공재로 사용.
  • 전체 메모리를 여러 프로세스가 공유하는 상황에서 전체 시스템 차원으로 메모리를 관리한다.
  • 메모리가 부족해지면 다른 프로세스의 페이지를 수거할수도 있다.
  • 앞서 살펴본 LRU, LFU, 클럭 등의 알고리즘을 전역 교체 방식으로 사용이 가능하다.
  • 일반적으로 전역 교체가 지역 교체보다 효율적. 
• 지역 교체 : 페이지 교체 대상이 해당 프로세스 한정. 프로세스마다 독자적인 페이지 프레임 운용.
  
  • 프로세스별로 침범할 수 없는 페이지 프레임을 갖고있다.
  • 그래서 페이지 프레임을 미리미리 할당해두고 사용한다.

 

✅스레싱

스레싱을 가단하게 표현하면 메모리에 프로세스가 너무 많아져 CPU 이용률이 급감하는 현상이다.

 

CPU는 고급 자원이므로 최대한 이용률을 높혀야한다.

이를 MPD(Multi-Programming Degree) 라고 부르는데, 메모리에 얼마나 많은 프로세스가 있는지를 나타내는 척도다.

 

 

스레싱이 발생하는 시나리오는 다음과 같다.

• MPD를 높히기 위해 OS는 계속해서 프로세스를 Ready Queue에 넣는다.
• Ready Queue에 프로세스가 증가하면 메모리는 한정되어 있으므로,
  각 프로세스마다 할당받을 수 있는 페이지 프레임이 적어진다.
• 프로세스가 실행되기 위해서 필요한 주소 영역이 모두 메모리에 있어야해서,
  페이지 프레임이 부족하면 페이지 폴트가 발생한다.
• 페이지 폴트는 일종의 디스크 I/O 작업이므로 해당 프로세스는 Block 상태가 된다.
• Block 상태가 된 프로세스가 증가되면 CPU 이용률이 감소한다.
• 다시 CPU 이용률을 높히기 위해 OS는 더 많은 프로세스를 Ready Queue에 넣어준다.
• 이제 모든 프로세스가 페이지 폴트로 문맥 교환이 반복 되며, CPU 사용률이 급감한다.(스레싱 발생)

 

그렇다면 스레싱은 어떻게 대응해야할까?

대표적으로 2가지 방식이 있다.

• 워킹셋 알고리즘(working-set) : 필요한 페이지 모음(워킹셋)을 보장하는 알고리즘.
• 페이지 부재 빈도 알고리즘(page-fault frequency)

 

워킹셋 알고리즘

프로세스가 실행되면 주소영역을 골고루 사용하지 않고, 한번에 특정 영역만을 사용한다.

이러한 페이지들의 집합을 지역성 집합(locality set)이라고 한다.

 

페이지들은 이러한 지역적인 특징이 있어서,

실행에 필요한 페이지들이 동시에 필요하다. 이러한 페이지 집합을 워킹셋이라고한다.

워킹셋 알고리즘은 워킹셋이 전부 메모리에 올라갈 수 있을때만 해당 프로세스를 메모리에 할당한다.

반대로 워킹셋이 전부 올라갈 수 없다면 해당 페이지들은 스왑아웃시킨다.

 

그렇다면 워킹셋의 크기는 어떻게 결정해야할까?

워킹셋은 특정 세타 시간동안 참조되는 페이지들의 집합이다.

위 그림에서와 같이 지역성이 낮을때는 워킹셋 크기가 커지고 지역성이 높을때는 워킹셋 크기가 작아진다.

 

이 집합의 크기가 너무 작게 되면 지역성 나타내는 페이지들은 모두 포함하지 못해

페이지 폴트율이 증가한다.

 

반대로 워킹셋이 너무 크면 지역성을 나타내지도 않는(잘 쓰이지도 않는) 페이지들도 모두 메모리에 올라온다.

그렇게되면 한 프로세스당 할당되는 메모리가 너무 커져서 MPD가 낮아진다.

 

그래서 워킹셋 크기가 너무 크지도 작지도 않게 세타 크기를 적절하게 조정해야한다.

 

페이지 부재 빈도 알고리즘

말그대로 해당 프로세스의 페이지 폴트율을 보고 페이지 수를 조정한다.

 

예를 들어 프로세스가 페이지 폴트가 너무 많이 발생하면 페이지가 부족함을 나타내므로,

더 많은 페이지를 할당시킨다.

 

반대로 페이지 폴트율이 너무 낮다면 해당 프로세스에게 너무 많은 페이지가 할당된것으로 판단해,

페이지 수를 줄인다.

 

• 구체적으로 프로세스마다 상한선(upper bound)와 하한선(lower bound)을 설정해,
  페이지 폴트율이 높다면 페이지 추가, 낮다면 페이지 수거하는 방식이다.
• 만약에 모든 프로세드들이 경계안에 정착한다면 새로운 프로세스를 추가해 MPD를 높힌다.
• 그러나 페이지의 지역성이 고려되지 않아, 불필요한 페이지들도 할당되어 메모리 낭비가 있다.