운영체제(8) - 가상 메모리

가상 메모리

  이전 글에서 실제 메모리에 대해 다뤘다. 이는 메모리 관리 방법을 토대로 제공하는 기술이며, 각 프로그램에 실제 메모리 주소가 아니라 '가상 메모리 주소'를 주는 방법이다. 이 가상 메모리는 사용자와 논리적 주소를 물리적으로 분리해서 사용자가 메인 메모리에서 용량을 초과하는 프로세스에 가상 메모리 주소를 지정해서 메모리를 제한 없이 사용할 수 있도록 한다. 프로그램 전체를 동시에 실행하는 것이 아니라 일부만 적재해도 실행 가능하도록 한다. 즉, 보다 큰 프로그램을 적은 메모리에서 처리할 수 있게 해준다. 프로세스의 코드와 데이터는 디스크에 저장하고, 실행영역만 메인 메모리에 유지한 상태로 필요할 때만 스왑 인 앤 아웃 과정을 거쳐 프로세스를 재할당한다. 이는 메인 메모리의 '제한된 용량'과 '중첩 사용 문제'를 해결한다.

 

  실제 메모리의 공간 제약 문제를 해결하기 위한 방안으로 중첩이 있었다. 허나 메모리에 프로그램의 일부만 적재하게 된다면 어떤 이점이 있을까?

1. 중첩을 고려할 필요가 없으므로 프로그래밍이 간단
2. 프로세서의 이용률과 처리율 향상

단점은 다음과 같다.

1. 메모리와 디스크 사이 이동률 증가, 스와핑 공간이 필요
2. 페이징 알고리즘과 요구 페이지 없을 때 처리방안 고안

단점을 해결하기 위해 프로세스가 참조하는 주소와 물리적 주소를 분리해야 한다.

 

 

가상 주소의 형태는 다음과 같다.

가상 주소

페이징 시스템에서 가상 주소는 가상 페이지 번호와 오프셋으로 구성된 V=p,d 형태가 된다. 예를 들어 32비트 가상 주소와 4kb 크기의 페이지를 사용하여 오프셋이 12비트(4kb)라고 하자. 가상 페이지 번호는 나머지 20비트를 사용하므로 프레임은 2^20개가 된다.

 

페이징 시스템에서 가상주소 변환

가상주소가 페이지 테이블 항목을 거쳐서 물리적 주소로 변환되는 과정이다.

 

요구 페이징

가상 메모리에서 많이 사용하는 메모리 관리 방법이다. 스와핑을 사용한 페이징 시스템과 비슷하다. 실행중인 요구 페이지만 메모리에 반입하여 프로세스의 모든 페이지를 메모리에 동시에 적재하지 낳는다. 

요구 페이징 개념도

요구 페이징의 페이지 테이블에서 페이지의 유효여부를 파악하기 위해 페이질 테이블에 타당, 비타당 비트를 추가한다. 이는 1이라면 페이지가 메인 메모리에 있다는 의미고, 0이면 디스크에 있어 아직 적재하지 않은 페이지란 의미다.

 

요구 페이징은 페이지부재를 유발하기도 한다. 페이지 부재란, 메모리에 적재되지 않은 페이지, 다시 말해 비타당 비트로 표시된 페이지에 액세스를 했을 때 발생하는 순간을 말한다. 페이지부재로 인한 트랩이 발생하면 제어권을 운영체제에 넘겨서 빈프레임을 찾고 페이지를 그 프레임에 적재한다.

페이지 부재가 발생한다면 메인 메모리에서 사용하지 않는 페이지를 없애 새로운 페이지로 바꾸는 이른바, 페이지 대치를 행한다.

페이지부재에 따른 대치 과정

페이지 대치 알고리즘

보통 프레임 수가 증가하면 페이지 부재가 감소한다. 다만 일정 수의 프레임 정도에서는 아무리 늘려도 부재가 일정하다.

 

• 선입선출 대치 알고리즘

메모리에 있는 페이지를 모두 큐에서 관리하는 가장 간단한 알고리즘이다. 큐의 헤드 부분, 즉 먼저 할당된 프레임을 희생시킨다. 큐의 크기는 사영가능 메모리의 프레임수와 같다.

선입선출 대치 알고리즘 실행의 예

이런 선입선출이 항상 성능이 좋은 것은 아니다. 프레임 수를 늘리면 부재는 줄어들기 마련이지만 선입선출 같은 경우엔 오히려 부재가 늘 수도 있다. 이처럼 프레임 증가가 페이부 부재 비율 증가로 이어지는 현상을 벨레디의 변이라고 한다.

• 최적 페이지 대치 알고리즘 OPT

모든 대치 알고리즘 중에서 가장 페이지 부재 비율이 낮다. 기본적으로 앞으로 가장 오랫동안 사용하지 않을 페이지를 대치하는 것이다.

최적 대치 알고리즘 실행의 예

페이지 부재가 발생한 4번을 보자.  프레임 안에는 1,2,3번의 페이지가 들어있고, 5 이후에 사용하지 않을 페이지는 3번이다. 따라서 3번를 5번과 대치한다.

• 최근 최소 사용 대치 알고리즘 LRU

가장 최근 페이지에 액세스했다는 것은 머지 않아 다시 할 가능성이 있다는 의미다. 그렇기에 과거 오랫동안 사용하지 않는 페이지를 대치한다는 것이다.

최근 최소 사용 대치 알고리즘 실행의 예

이런 LRU 알고리즘의 구현하는 2가지 방법이 있는데 카운터와 스택을 이용하는 것이다.

카운터(계수기)를 사용한 방법은 페이지 테이블 항목에 카운터필드를 덧붙여 페이지가 참조될 때마다 클록이 증가하도록 하는 것이다. 가장 낮은 카운터값의 페이지를 제거함으로써 대치하는 것이다.

스택을 이용한 방법은 페이지 번호를 스택에 넣어 관리하여 페이지가 참조될 때마다 페이지 번호를 스택의 top에 두어 결정하는 방법이다. top에 있으면 가장 최근에 사용한 페이지가 되고, bottom에 있으면 가장 오랫동안 사용했으므로 부재일 때 대치하도록 한다.

 

대부분의 LRU 알고리즘은 하드웨어에서 지원하지 않기 때문에 다른 알고리즘을 사용해야 하는데 그것이 최근 최소 사용 근접 알고리즘이다. 처음 모든 비트를 0으로 초기화하고, 페이지 참조가 행해질 때마다 관련 비트를 1로 변환하는 것이다. 저렴하게 구현 가능하여 상당수 시스템이 참조비트 형태를 지원한다.

• 참조비트 알고리즘

참조비트의 예

• 시계 알고리즘

가장 오랫동안 메인 메모리에 있던 페이지 중 자주 사용하는 페이지의 대치 방지.

시계 알고리즘의 예

• NUR not used recently 알고리즘

최근에 사용하지 않은 페이지를 교체한다. 이는 최근에 사용하지 않은 것은 가까운 미래에도 사용하지 않을 것이라 전망에서 나왔다.

• 최소 사용 빈도수 알고리즘 LFU

각 페이지마다 참조횟수를 카운트하고 이 수가 가장 작은 페이지를 대치하는 것이다. 프로세스가 초기에 한 페이지를 많이 사용할 땐 곤란하다.

• 최대 사용 빈도수 알고리즘 MFU

계수가 작은 페이지는 앞으로 사용할 확률이 높다고 가정해서 대치하지 않고, 가장 많이 사용한 페이지를 대치하는 방법이다.

• 페이지 버퍼링

선입선출처럼 성능이 떨어지는 것을 막기 위해 대치대상 페이지를 바로 교체하지 않고 잠시동안 메인메모리에 유지하는 것을 말한다.

 

균일 비례 프레임 할당 알고리즘

프레임을 적절히 할당하면 페이지 부재 횟수가 줄어든다. 그렇기에 균일 비례 프레임 알고리즘으로 자원낭비를 최소화할 수 있다. 균일 방법은 페이지 프레임을 낭비하거나 페이지 부재가 빈번할 수 있다. 하지만 이런 문제는 비례 할당 방법으로 해결가능하다. 

 

메모리를 관리하는 프로세스 적재정책

스래싱 Thrashing

페이지 교환이 계속해서 일어나는 현상이다. 모든 페이지를 실제로 사용하고 있다고 해도 지속적으로 스와핑을 해야 한다면 페이지 부재가 연속적으로 발생한다는 것이다. 이는 시스템 성능 낮추거나 축소를 야기한다. 따라서 프로세스 수행시간 보다 페이지 교환 시간이 더 길면 '스래싱을 하고 있다'라고 표현한다.

• 원인

새로운 프로세스가 늘어가면 너무 많은 다중 프로그래밍을 하게 되므로 계속 프레임을 뺏고 빼앗는 과정을 유지하게 된다. 결국 프로세서 스케줄러는 이용률을 더 올리려고 할 테고 다중 프로그래밍 강도 또한 높아질 것이다. 이때문에 실행은 점점 느려지게 되고 페이지 부재 발생으로 인해 이용률이 감소하는 스래싱이 발생하게 된다.

• 예방

작업 집합 모델과 지역 모델이 있다.

 

먼저 지역성에 대해 숙지하자. 지역성이란 실행중인 프로세스에서 나타나는 특성이다. 프로세스가 선호하는 어느 특정페이지만 집중적으로 참조하는 현상이다. 적은 데이터만 집중적으로 참조하다가 또 다른 작은 규모의 데이터 덩어리로 이동하는 경향이 있다.

지역성은 시간지역성, 공간지역성으로 나뉘는데,

시간지역성은 특정 자원들을 상대적으로 짧은 시간 안에 재사용하는 것을 의미한다.

공간지역성은 상대적으로 가까운 데이터요소를 사용한다는 것을 의미한다.

 

• 작업 집합 모델

페이지 부재를 가장 최소 비율로 유지하도록 최근 계산에서 필요한 메모리를 구하는 방법으로 제안된 모델이다. 프로세스가 많이 참조하는 페이지 집합을 메모리 공간에서 상주시켜서 빈번한 대치 현상을 줄인다.

다중 프로그래밍 정도를 높이면서 스래싱을 최소화할 수 있지만 과거의 참조가 미래의 참조를 보장하진 않는다. 게다가 작업 집합의 크기와 구성 페이지들은 시간이 경과하면 변한다.

 

• 페이지 부재 비율

페이지 부재가 발생할 때 높낮이를 파악하고 프레임수를 조절하는 직접적인 스래싱 예방 방법이다. 작업 집합 모델보다 오버헤드가 적다.

 

메모리 관리와 관련된 이슈

대치 범위를 어떻게 할 것인가?

할당된 프레임까지 고려할 것인가? 하는 물음이 있다. 모든 프로세스를 대치 범위에 두는 '전역 대치'와 개별적으로 제한한 범주에서만 하는 '지역 대치'가 있다.

 

프리페이징

처음에 많은 페이지 부재가 발생할 수 있다. 이를 방지하는 방법이다. 예상되는 모든 페이지를 사전에 모두 메모리 내로 가져오는 것이다. 다만 사용할 페이지를 잘못 결정하거나 많은 자원을 사용하면 요구 페이징 보다 성능이 떨어질 수 있다. 이를 방지하기 위한, 지역성에 기반한 경험적 알고리즘이 중요한 요소다.

 

페이지 크기

하드웨어 디자인에서 매우 중요한 요소다. 이에 따라서 페이지 테이블의 크기가 달라지기 때문이다. 페이지 크기를 감소시키면 페이지 수가 증가하고 테이블도 커진다. 메모리는 내부단편화를 최소화할 수 있는 작은 크기의 페이지가 이용에 용이하다. 다만 큰 페이지는 내부단편화가 증가하지만 디스크 입출력을 감소시킬 수 있고 무엇보다 페이지 부재 비율을 감소싴킬 수 있다.