9. 운영체제 가상메모리

- 가상 메모리 -

 

메인 메모리의 크기가 한정되어 있으므로 물리적인 메모리 크기보다 크기가 큰 프로세스를 실행시킬 수 없다. 예로 100MB 메인 메모리에서 200MB 크기의 프로세스를 실행할 수 없게 되는 것이다. 그렇다면 메인 메모리보다 크기가 큰 프로세스를 실행시키고 싶으면 어떻게 해야 할까? 단순히 메인 메모리가 더 큰 컴퓨터를 사용해야하는가? 이런 방법은 매우 비효율적일 것이다. 그래서 나온 방법이 바로 가상 메모리이다.

프로세스의 모든 코드는 항상 필요한 것이 아니다. 오류 처리하는 부분이나 필요 없는 배열 부분은 실제로 프로세스가 잘 동작한다면 필요 없는 부분이 된다. 따라서 프로세스는 필요한 부분만 메모리에 올림으로써 메인 메모리에 올라가는 프로세스의 크기를 줄인다. 프로세스 이미지를 모두 메모리에 올릴 필요가 없는 것이다. 동적 적재와 비슷한 개념이라고 알 수 있다.

우선 우리가 실행을 시키고자 하는 프로세스들을 1.페이징 과정을 먼저 실행한다. 메인 메모리의 외부 단편화 문제를 해결하여 메모리 낭비를 줄이는 데 페이징을 사용하면 매우 효율적이기 때문이다. 따라서 페이징 과정을 거쳐 특정 단위인 페이지 단위로 프로세스를 자른다. 그러면 여기서 페이지들마다 필요한 부분과 필요 없는 부분으로 나눌 수 있다. 여기서 필요한 페이지만 메모리에 적재를 하면 많은 메모리의 낭비를 막고 우리가 필요한 프로세스들을 모두 메인 메모리에서 실행을 시킬 수 있게 되는 것이다. 이를 요구 페이징이라고 한다.

요구 페이징(Demand Paging)은 프로세스의 이미지를 backing store에 저장한다. backing store는 swap device로 하드웨어의 부분인데 페이지를 임시로 보관하는 공간이다. 프로세스는 페이지의 조합이기 때문에 필요한 페이지만 메모리에 올린다. 이를 요구되는 페이지만 메모리에 올린다는 의미로 요구 페이징이라고 부른다.

페이징 기법을 사용할 때 페이지 테이블이라는 부분을 놔두게 된다. MMU의 재배치 레지스터를 통해 논리 주소를 물리 주소로 바꾸어주는 주소 변환 과정을 거쳐 CPU가 프로세스는 연속적으로 할당되어져 있다고 속게 만드는 작업을 한다. 그런데 요구 페이징 기법을 사용하면 페이지가 메모리에 올라와있는 것도 있고 올라가지 않고 backing store에 보관되어 있는 것도 존재한다. 따라서 페이지 테이블을 작성할 때 이를 구분해줄 도구가 필요하다. 그래서 valid 비트 필드를 페이지 테이블에 추가한다. 1과 0의 값으로 메모리에 적재되어 있는지 없는지를 구분할 수 있다.

만약 오류가 발생한다면 오류를 제어할 수 있는 코드를 실행해야한다. CPU에서 해당 메모리를 가져오라고 논리 주소를 보냈는데 페이지 테이블에서 접근하려는 페이지가 메모리에 없다고 표시가 되어 있다. 이는 valid 비트 필드에 의해서 결정된다. 그러면 Backing store에서 해당 페이지를 가져와야한다. 이를 수행하기 위해서 CPU는 잠시 하는 일을 멈추고 운영체제가 나서서 Backing store를 뒤져 필요한 페이지를 메모리에 적재하게 된다. 그리고 valid 비트를 올라와 있다고 바꾸어준다. 이런 현상을 페이지 결함, 페이지 부재(Page Fault)라고 부른다.

요구 페이징을 할 때 두 가지의 종류가 있다. 처음부터 모든 페이지를 적재시키지 않고 CPU가 요구할 때 valid를 바꾸어 페이지를 적재하는 방법과 우선 필요할 것 같은 페이지를 적재시키고 필요할 때 다른 페이지를 적재시키는 방법이 있다. 전자는 pure demand paging이고 후자는 prepaging 기법이다. pure 기법을 사용하면 페이지를 요구할 때만 메모리에 적재하므로 메모리의 낭비는 매우 줄일 수 있다. 하지만 요구에 의해 앞선 페이지 부재의 현상을 처리 하려고 하면 많은 부담이 발생한다. 이에 반해 미리 올라와져 있는 prepaging은 처리하는 속도는 빠르겠지만 메모리가 낭비될 수 있도 있다.

---

- 가상 메모리2 -

유효 접근 시간이라는 것은 Effective Access Time으로 평균적으로 CPU가 요구할 때 메모리를 통해 읽혀지는 시간을 의미한다. 어떤 프로세스의 경우 메인 메모리에 올라와 있으면 바로 읽어서 시간일 짧을 것이고 어떤 프로세스의 경우 backing store에서 메인 메모리로 올려줘야 하는 경우 CPU도 중단시켜야하고 운영체제가 찾아서 올리는 과정까지 해서 시간이 많이 걸릴 것이다. 그래서 페이지 결함이 일어날 확률을 통해 유효 접근 시간을 구하게 된다.

유효 접근 시간을 수학적인 식으로 구하게 되면 다음과 같다.

Teff = (1-p)Tm + pTp

유효 접근 시간은 메모리에 존재하는 페이지와 메모리에 존재하지 않는 페이지의 접근 시간의 평균으로 구한다고 했다. p의 값은 페이지가 결함이 일어날 확률이다. 따라서 1-p는 페이지가 결함이 일어나지 않을 확률이다. Tm 값은 메인 메모리에서 바로 CPU가 실행할 수 있는 시간을 의미하고 Tp는 운영체제가 backing store인 하드디스크에서 페이지를 찾고 메모리에 올리고 실행시키는 시간을 의미한다. 정확하게 Tp는 seek time, rotational delay, transfer time으로 나눌 수 있다. 여기서 seek time인 하드디스크에서 찾아가는 시간으로 가장 오래 걸리는 부분을 차지한다. 당연히 Tp가 Tm에 비해 걸리는 시간이 많은 것이다. 따라서 각각의 확률에 시간을 곱한 후 더하게 되면 평균적으로 페이지를 접근하는데 걸리는 시간이 나오게 된다. Tp가 유효 접근 시간에 큰 영향을 끼치므로 페이지 결함을 줄여야 컴퓨터의 효율이 올라가게 된다.

지역성의 원리는 CPU가 참조하는 주소가 지역에 모여져 있다는 의미이다. 메모리 접근은 시간적, 공간적으로 지역성을 가진다. 시간적인 지역성은 한 번 읽었던 코드를 다시 읽을 확률이 높다는 것을 의미한다. 코드 중에는 while문이나 for문과 같이 같은 구간을 반복하는 명령이 존재하기 때문이다. 이 때 맨 처음에 페이지를 메인 메모리에 적재한 후에는 다시 적재할 필요가 없기 때문에 페이지 결함의 확률이 매우 낮다. 공간적인 지역성은 코드를 읽을 때 현재 코드의 주변에 있는 코드를 읽을 확률이 높다는 것을 의미한다. 페이지 결함이 일어나 하드디스크에서 페이지를 가져올 때 주변 코드들을 block 단위로 가져오게 되면 주변 코드를 읽을 확률이 높으니 다음의 페이지 결함의 확률이 낮아지는 것이다. 따라서 지역성의 원리에 의해 페이지 결함으로 인한 컴퓨터의 효율이 떨어지는 확률이 많이 낮아진다.

---

- 페이지 교체 알고리즘 -

 

알고리즘들은 그림의 예시를 통해 이해하면 더욱 빠르게 이해할 수 있을 것이다. 예시를 읽는 법을 보면 파란색의 경우는 페이지 결함이 일어난 경우가 되고 참조열은 Page reference string이라고 볼 수 있다. 프레임의 개수는 모두 3개만 존재하여 페이지는 3개의 프레임에 할당되게 되는 것이다.

첫 번째 알고리즘은 FIFO로 First-in First-Out이다. 메모리에 먼저 올라온 페이지를 먼저 내보낸다는 알고리즘이다. 따라서 victim page의 대상은 가장 먼저 메모리에 올라온 페이지가 되는 것이다. 이 방법은 가장 간단한 방법이다. 특히 초기화 코드에 대해서 적절한 방법이라고 할 수 있다. 초기화 코드는 처음에 프로세스가 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않기 때문에 메인 메모리에서 내려 보내도 괜찮다. 하지만 처음에 프로세스를 실행시키는데 무조건 필요하다. 따라서 FIFO의 방법을 사용하면 초기화 시켜준 후 가장 먼저 내려 보내지게 된다. 그러면 프레임의 수가 커질수록 페이지 결함은 어떻게 되겠는가? FIFO의 알고리즘은 프레임의 수가 적을수록 페이지 결함이 더 많이 일어나게 된다. 계속 교체를 해주어야하기 때문이다. 하지만 프레임의 수가 많아질수록 페이지 결함의 횟수는 감소하게 된다. 이를 Belady’s Anomaly라고 부른다.

두 번째 알고리즘은 OPT(Optimal) 이다. OPT 알고리즘은 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내려 보내는 알고리즘이다. 이름과 같게 가장 적절할 수 있는 알고리즘이라고 할 수 있다. 확실하게 앞의 FIFO에 비해서 페이지 결함이 일어날 횟수가 많이 감소하는 것을 알 수 있다. 하지만 Optimal의 경우 앞으로도 사용이 잘 되지 않을 것이라는 보장이 없으므로 미래를 알 수 없는 조건에 의해 실질적으로 수행하기에는 큰 어려움이 있다고 할 수 있다.

세 번째는 LRU 알고리즘은 Least-Recently-Used이다. LRU 알고리즘은 최근에 사용하지 않은 페이지를 가장 먼저 내려 보내는 알고리즘이다. 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 아이디어로부터 온 것이다. OPT의 경우에는 미래에 대한 예측이지만 LRU의 경우에는 과거를 보고 판단하므로 실질적으로 사용 가능한 알고리즘이라고 할 수 있다. 실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다고 할 수 있다. 비록 OPT 보단 페이지 결함이 더 일어날 수 있지만 실제로 사용할 수 있는 알고리즘 중에서는 좋은 방법 중 하나라고 할 수 있다.

교체하는 방식에는 Global 교체와 Local 교체로 두 가지의 방식이 존재한다. Global 교체는 메모리상의 모든 프로세스 페이지에 대해 교체를 하는 방식이고 Local 교체는 메모리상의 자기 프로세스 페이지에서만 교체를 하는 방식이다. 다중 프로그래밍의 경우 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있는데 따라서 다양한 프로세스의 페이지가 메모리에 존재하게 된다. 페이지를 교체할 때 앞의 다양한 알고리즘에 의해 victim page를 선정하게 되는데 선정하는 기준이 전체를 기준으로 하느냐 자기 프로세스의 페이지에서를 기준으로 하느냐에 대한 차이이다. 실제로 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 할 수 있다.

출처: http://copycode.tistory.com/122?category=740133 [ITstory]