가상메모리는 무엇인가요?

메모리 관리의 목표와 기능

우리 모두 이제 프로세스가 메모리에 필요한 크기만큼 주소를 할당 받아 실행이 된다는 것을 알고 계실 것입니다. 또한 메모리의 크기가 무한하지 않기 때문에 메모리만을 이용해서는 실행할 수 있는 프로세스의 개수가 제한적이라는 것을 아실 것입니다.

그렇다면 메모리에 할당되는 프로세스는 어떤 방식으로 주소를 할당 받아서 메모리에 적재해야 하는 것일까요? 가장 먼저 생각해볼 수 있는 것은 메모리에 비어 있는 공간에 실행해야할 프로세스들을 순서대로 주소를 할당하는, 연속 메모리 할당 방법입니다.

실행하고자 하는 프로세스를 할당할 수 있는 메모리가 남아 있지 않을 경우 다음 프로세스를 실행 시키고자 하면 어떻게 해야 할까요? 이 경우 스와핑을 진행하여 프로세스를 실행 시킬 수 있습니다.

현재 메모리에 할당되어 있는 프로세스 중 현재 실행하지 않고 대기하는 프로세스가 있을 수 있습니다. 예를 들어, 입출력 작업의 요구로 대기 상태가 된 프로세스, 오랫 동안 사용되지 않은 프로세스들이 있을 수 있습니다. 이러한 프로세스들을 임시 보조기억장치로 일부 영역을 쫓아 내고 이로 인해 생긴 빈 메모리 공간에 다른 프로세스를 적재하여 실행하는 방법을 스와핑이라고 합니다.

메모리에 있는 프로세스의 일부를 보조 메모리로 이동 시키는 작업을 스와핑 아웃이라고 하고 프로세스에 다시 적재할 만한 공간이 생겼을 경우 보조 메모리에 있는 프로세스를 다시 메모리로 가져오는 작업을 스와핑 인이라고 합니다.

이러한 방법을 사용한다면 메모리의 남은 용량 보다 큰 작업 또한 동시 실행할 수 있습니다. 이렇게 프로세스를 적재하기 위해서는 프로세스를 할당 하는 방법 또한 중요합니다.

메모리의 할당 방법

할당하는 방식에는 선택할 수 있는 방법이 몇 가지 있습니다. 최초 적합은 프로세스에 할당이 가능한 빈 공간이 보인다면 즉시 그 공간에 프로세스를 할당하는 방법을 이야기 합니다. 최적 적합 프로세스의 공간을 탐색하고 적재하고자 하는 프로세스의 크기와 큰 차이가 없는 빈 공간에 프로세스를 적재하는 기법입니다. 최악 적합은 남아 있는 메모리의 공간 중 가장 큰 메모리 공간에 프로세스를 할당하는 방법을 이야기 합니다.

위의 할당 기법은 모두 상황에 맞게 적절하게 실행해야 합니다. 각가의 방법에 장단점이 존재하기 때문입니다.

최초 적합의 경우 할당 속도가 빠르다는 장점이 존재합니다. 처음 발견하는 공간에 바로 할당하기 때문에 검색 시간이 최소화 되기 때문입니다. 하지만 이 또한 공간 효율성이 좋지 못하다는 단점이 존재합니다. 최초 적합에 적합한 상황은 실시간 시스템과 같이 빠른 메모리 할당이 중요한 실시간 처리 시스템과 많은 프로세스를 빠르게 처리해야 하는 상황에서 효과적일 수 있습니다.

최적 적합은 메모리의 낭비를 최소화 할 수 있고 공간을 효율적으로 사용할 수 있다는 장점이 존재하지만 프로세스에 적재할 때마다 메모리 전체를 탐색하여 최적의 블록을 찾아야 하기 때문에 메모리를 할당하는데 시간이 걸린다는 단점이 존재합니다.

최적 적합의 경우 메모리의 공간을 효율적으로 사용이 가능하기 때문에 제한된 메모리환경, 임베디스 시스템 혹은 모바일 환경과 같이 메모리의 크기가 제한될 경우에는 다른 방법 보다 효율 적인 방법이라고 할 수 있습니다.

최악 적합은 외부 단편화의 크기를 감소 시킬 수 있다는 장점이 존재하지만 메모리 효율성이 저하되고 시간이 지날 수록 효율성이 더 크게 저하 된다는 문제가 있습니다. 최악 적합의 경우 메모리 재할당이 빈번한 경우, 사용 가능한 메모리가 충분한 경우에 사용하면 유용할 수 있습니다.

외부 단편화와 가상 메모리

지금까지 이야기한 연속 메모리 할당은 모두 외부 단편화가 발생할 수 있다는 단점이 존재합니다. 메모리에 적재 되어 있는 프로세스가 작업을 모두 끝내고 반환하는 메모리의 크기가 연속되지 않아 할당할 수 있는 메모리가 제한된다 문제가 있습니다. 예를 들어 메모리에 프로세스 2개가 작업을 모두 끝내고 70MB의 공간 여유가 생겼지만 이 공간이 만약 15MB, 25MB, 30MB로 나뉘어 있을 경우 다음에 적재할 프로세스의 크기가 70MB 여도 실행하지 못하는 문제가 발생합니다.

이렇게 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해서 메모리가 낭비가 되는 현상을 외부 단편화라고 정의 합니다.

이러한 문제를 해결할 수 있는 방법으로 메모리를 압축 방법이 있습니다. 이를 메모리 조각 모음이라고도 부릅니다. 압축은 빈 공간들을 하나로 모으는 방식으로 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 공간으로 만드는 작업을 의미합니다.

하지만 이 방법은 압축을 진행하는 동안에는 모든 작업을 중단시켜야 합니다. 메모리 조각 모음은 이미 메모리에 적재되어 있는 프로세스들의 주소를 변경해야 하는 작업을 수행해야 합니다. 이러한 작업 도중 해당 프로세스가 메모리를 참조할 경우에는 데이터 손상, 예상치 못한 에러가 발생할 수 있습니다.

메모리 조각 모음을 수행하는 동안에는 시스템의 안정성과 데이터 무결성을 보장하기 위해서 모든 작업을 중지한 후 작업을 수행해야 합니다.

연속 메모리 할당을 사용하는데 메모리 보다 큰 프로세스를 할당하려고 한다면 해당 프로세스는 메모리에 적재되어 실행이 될 수 있을까요? 그럴 수 없습니다. 이를 가능하게 하는 방법이 가상 메모리를 사용하는 것입니다.

가상 메모리란?

가상 메모리는 "특정 기계에서 실제로 사용 가능한 저장 리소스의 이상화된 추상화"를 제공하는 메모리 관리 시술로, 사용자에게 매우 큰 메모리가 있다는 환상을 만들어 냅니다.

가상 메모리의 주요 이점으로는 애플리케이션이 공유 메모리 공간을 관리할 필요가 없어지고, 프로세스 간에 라이브러리가 사용하는 메모리를 공유할 수 있으며, 메모리 격리로 인한 보안 강화, 그리고 페이징이나 세그먼테이션 기술을 사용하여 물리적으로 사용 가능한 것보다 개념적으로 더 많은 메모리를 사용할 수 있다는 점이 있습니다.

오늘 날의 운영체제들은 CPU의 주소 변환 하드웨어인 메모리 관리 장치, MMU 장치인 활용하여 가상 주소를 물리적 주소로 변환하는 장치를 활용하여 페이징을 수행하여 실제로 이용할 수 있는 메모리의 크기 보다 큰 작업들을 수행할 수 있게 되었습니다.

가상 메모리가 이러한 작업이 가능한 이유는 프로세스를 페이지의 단위로 분할하고 메모리의 주소들을 프레임이라는 단위로 나뉘어진 공간에 페이지를 할당하는 방법을 페이징이라고 합니다. 페이징을 사용할 경우 메모리에 프로세스들을 불연속적으로 나뉘어진 단위로 적재하기 때문에 메모리를 매우 효율적으로 사용할 수 있게 됩니다.

페이징

하나의 페이지, 혹은 프레임에는 여러 주소를 포괄하고 있습니다. 그렇기 때문에 특정 주소에 접근하기 위해서는 페이지, 프레임에는 아래와 같은 두 정보를 포함하고 있어야 합니다.

특정 페이지, 프레임을 가리키는 프레임 번호 혹은 페이지 번호
시작 주소로 부터 얼마나 떨어져 있는지에 대한 정보인 변위

위의 두 정보를 페이지에서 포함하고 있을 경우, <페이지 번호, 변위>는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>로 변환이 됩니다.

페이징은 외부 단편화 문제를 해결할 수 있지만 내부 단편화 문제가 발생할 수 있습니다. 이 문제는 모든 프로세스에 적합한 프레임의 크기를 찾기가 어렵다 문제로 인해서 발생합니다. 예를 들어 페이지의 크기는 10KB인데 페이지의 프로세스의 크기가 108KB일 경우 2KB의 크기가 남게 됩니다. 이러한 메모리 낭비를 내부 단편화라고 합니다.

가상 메모리 시스템에서 프레임의 크기는 페이지의 크기와 정확히 일치하도록 설계가 됩니다. 이러한 내부 단편화를 해결하기 위해 만약 페이지를 작은 페이지의로 나누게 된다면 어떻게 될까요? 내부 단편화의 크기 또한 작아질 것입니다. 하지만 페이지 테이블의 크기가 거지게 됩니다.

페이지 테이블의 크기가 커지게 되면 TLB 미스가 증가하게 될 확률이 높아집니다. 반대로 페이지의 크기를 크게 할 경우 페이지의 테이블의 크기가 줄어 TLB 효율성이 향상 되지만 내부 단편화가 커지기 때문에 상황에 맞는 적절한 단위로 나누는 것이 중요합니다.

앞서 스왑인, 스왑 아웃 방법에 대해서 이야기 했었습니다. 스왑인, 스왑 아웃은 프로세스의 메모리 전체를 보조 기억 장치에 이동 시켜 메모리를 효율적으로 사용하는 방법이었습니다. 페이징에도 이와 비슷한 방법이 존재합니다

페이징에서는 프로세스의 메모리 전체를 보조 기억 장치로 옮기는 것이 아닌 페이지 단위로 보조 기억 장치로 이동 시키는 작업을 페이지 아웃, 다시 가져오는 작업을 페이지 인 이라고 부릅니다.

페이지를 활용한 작업이 더욱 효과적인 이유는 프레임에 저장되어 있는 페이지 중 현재 사용하지 않는 일부 작업들을 보조 기억 장치로 이동시켜 메모리 공간 효율성을 이전 보다 더욱 효율적으로 사용할 수 있습니다. 기존에는 전체를 저장하였지만 특정 페이지만 이동 시킬 수 있기 때문에 더욱 효과적이라고 할 수 있습니다.

페이지 테이블

페이징을 이용할 경우 프로세스들을 불연속적으로 할당된다고 이야기 했습니다. 이렇게 불연속적으로 적재가 될 경우 페이지가 실제 어떤 프레임에 적재가 되어 있는지 MMU가 알기 어렵다는 문제가 있습니다. 이로 인해 MMU가 다음으로 실행해야 할 실제 작업의 주소를 알기가 어렵다는 문제가 생깁니다.

그래서 이 문제를 해결하기 위해서 페이지 테이블을 사용합니다. 페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표입니다. CPU로 하여금 페이지 테이블만을 보고도 페이지를 실행 시키기 위해서는 어떤 프레임을 봐야 하는 지를 알 수 있게 함으로 물리적 거리를 단축 시켜 실행 시간을 향상 시킬 수 있습니다.

또한 CPU는 페이지 테이블에 적혀 있는 페이지들을 순차적으로 실행하면 되기 때문에 불연속적으로 프레임에 담겨 있는 페이지를 실행 순서에 맞춰서 실행 시킬 수 있게 됩니다.

;

페이지 테이블 엔트리 : 페이지 테이블의 각 행들을 의미합니다.
페이지 번호, 프레임 번호 : 실제 페이지와 프레임을 가리키는 위치를 의미합니다.
유효 비트 : 현재 해당 페이지에 접근이 가능한지의 여부를 이진 숫자를 이용하여 표현합니다. 현재 페이지가 스왑 영역에 있지 않고 현재 메모리에 적재 되어 있는지 아닌지를 알려주는 비트입니다.
보호 비트 : 읽기(Read), 쓰기(Write), 실행(eXecute)를 나타내는 조합으로 구성이 되어 있으며 읽기, 쓰기, 실행의 권한의 조합을 나타내어 특정 작업을 수행하지 못하게, 권한을 제한할 수 있습니다.
참조 비트 : CPU가 읽거나 쓴 페이지는 참조비트가 1로 세팅되고, 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지됩니다.
수정 비트 : 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줍니다.

위의 정보들 중 중요한 정보에 대해서는 조금 더 자세하게 다루어 보겠습니다.

유효 비트는 페이지, 테이블 번호 다음으로 중요한 정보입니다. 만일 CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 어떻게 될까요? 이 경우 페이지 폴트(page fault) 라는 예외가 발생합니다. 이는 하드웨어에서 인터럽트가 발생했을 경우와 유사합니다.

CPU는 기존의 작업 내역을 백업합니다.
페이지 폴트 처리 루틴을 실행합니다.
페이지 처리 루틴은 원하는 페이지를 메모리에 가져온 뒤 유효 비트를 1로 변경해 줍니다.
페이지 폴트를 처리 했다면 이제 CPU는 해당 페이지에 접근할 수 있게 됩니다.

다음은 수정 비트입니다. 왜 해당 페이지가 수정 여부를 저장해야 하는 것일까요? 수정 비트는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재합니다.

CPU가 한 번도 접근하지 않았거나 읽기만 한 페이지의 경우 보조기억장치에 저장된 해당 페이지의 내용과 메모리에 저장된 페이지 내용은 모두 동일 합니다. 이럴 경우 스왑 아웃이 되면 데이터를 덮어쓰기만 하면됩니다.

하지만 CPU가 쓰기 작업을 수행해 보조기억 장치의 내용과 메모리에 저장된 페이지늬 내용이 다를 경우에는 스왑 아웃될 경우 보조기억장치에 기록하는 작업이 추가되어야 하기 때문에 수정 비트를 사용하는 것입니다.

프로세스마다 각자의 프로세스 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적제되어 있습니다. 그리고 CPU에는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있는 페이지 테이플 베이스 레지스터, 이하 PTBR을 갖고 있습니다.

그리고 앞 서 페이지 테이블은 메모리에 적재되어 있다는 이야기를 했습니다. 이는 CPU의 작업 속도에 비해 메모리 탐색 시간이 현저하게 느리다는 컴퓨터 아키텍처를 생각 했을 경우 효율적인 작업이라고 할 수 없습니다.

TLB

CPU와 메모리의 속도 차이로 인해서 CPU가 메모리의 작업을 기다리는 동안 수백 사이클을 낭비할 수 있습니다. 가상 주소를 물리적 주소로 변활 할 때 다음과 같은 과정이 필요합니다.

CPU는 페이지 테이블의 항목을 찾기 위해서 메모리에 접근합니다.
변환된 물리적 주소를 이용해 실제 데이터에 다시 접근합니다.

위에서 볼 수 있듯이 하나의 메모리 접근 명령이 실제로는 두 번의 메모리 접근을 필요로 하게 됩니다. 이 말은 메모리 접근 시간을 두 배로 증가 시킨다는 것을 의미합니다. 이를 해결하기 위해 물리적 거리를 줄인 TLB(Translation Lookaside Buffer) 라는 캐시 메모리를 CPU에 내부에 두어 문제를 해결하고자 했습니다.

TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장합니다. 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장합니다. CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히트라고 합니다. TLB에 없을 경우를 TLB 미스라고 합니다. 이로 인한 성능 향상은 아래와 같습니다.

TLB 히트(hit) 시: 1회 메모리 접근 (실제 데이터만)
TLB 미스(miss) 시: 2-5회 메모리 접근 (페이지 테이블 탐색 + 실제 데이터)

현대 시스템의 TLB 히트율은 일반적으로 98-99%입니다. 이는 대부분의 메모리 접근이 TLB를 통해 빠르게 처리된다는 의미입니다. 만약 TLB가 없다면, 메모리 접근 시간이 평균 2-5배 증가할 수 있으며, 이는 전체 시스템 성능에 심각한 영향을 미칠 것입니다.

페이지 교체와 프레임 할당

가상 메모리를 통해 작은 물리 메모리보다 큰 프로세스를 실행할 수 있다고 하더라도 여전히 물리 메모리의 크기는 한정이 되어 있다는 것은 변하지 않습니다. 그렇기 때문에 여전히 메모리에 어떤 자원들을 적재할 것이고 어떤 프로세스들은 보조 기억 장치로 잠시 이동 시켜야 하는지에 대한 의사 결정은 중요합니다.

그렇기 때문에 페이지를 효율적으로 교체하고 프레임을 할당하기 위한 여러가지 알고리즘이 존재합니다.가장 먼저 할당하는 방법에 대해서 이야기 해보겠습니다.

할당하기 위한 기법은 어찌 보면 당연하게 필요한 경우, 요구 했을 경우에 운영체제가 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징이라고 합니다. 메모리에 적재한다는 것은 페이징을 할당, 메모리가 실제로 몇개의 프레임을 사용할 수 있을지에 대한 제한을 설정한 후, 그 프레임에 맞게끔 페이지를 물리적 메모리의 프레임으로 이동시키는 작업입니다.

프레임 할당은 도서관에서 연구자에게 최대 5개의 책상을 이용할 수 있다고 정책을 정하는 것이고 메모리에 적재한다는 페이징 기법은 정해진 연구자가 규정에 맞춰 프로세스를 실행하기 위해서 책을 책상으로 가져오는, 메모리에 이동 시킨다는 것을 의미합니다.

요구페이징의 순서는 다음과 같습니다.

CPU가 특정 페이지에 대해서 접근하는 명령어를 실행한다.
페이지 테이블 내에서 해당 페이지에 관련한 정보를 확인한다.
해당 테이블의 유효 비트가 1인 경우 해당 페이지의 프레임 정보를 사용하여 물리적 메모리에 접근합니다.
해당 페이지의 유효 비트가 0인 경우 페이지 폴트 처리 루틴을 이용하여 해당 페이지의 유효 비트를 1로 전환 시킨다.
다시 처음 부터 실행한다.

이러한 페이징 할당 기법이 정상적으로 동작하기 위해서는 필연적으로 다음 두 가지를 해결해야 합니다. 하나는 페이지 교체이고, 다른 하나는 프레임 할당입니다. 페이징 시스템은 이 두 가지 메커니즘이 균형을 이룰 때 최적의 성능을 발휘합니다. 프레임 할당이 잘못되면 페이지 교체 알고리즘이 아무리 좋아도 성능이 저하될 수 있으며, 그 반대도 마찬가지입니다. 이러한 이유가 무엇일까요?

핵심은 메모리가 제한적인 용량을 갖고 있는 자원이라는 것입니다. 반면 모든 프로세스의 가상 주소 공간의 총합은 메모리보다 훨씬 클 수 있습니다. 이런 상황에서 필요한 작업은 어떻게 교체하여 공간을 확보할 것인지 판단하는 것이 중요할 것입니다.

페이지 교체 알고리즘

좋은 페이지 교체 알고리즘은 무엇일까요? 일반적으로 페이지 폴트를 적게 일으키는 알고리즘이 좋은 알고리즘이라고 평가합니다. 이러한 이유는 페이지 폴트가 발생하게 된다면 보조 기억장치로부터 필요한 페이지를 가지고 와야 하고 이는 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문입니다.

페이지 교체 알고리즘에서는 페이지 폴트가 중요하기 때문에 페이지 교체 알고리즘을 수행하기 위해서는 페이지 폴트 횟수를 알 수 있어야 합니다. 이러한 페이지 폴트 횟수는 페이지 참조열을 통해서 알 수 있습니다.

페이지 참조열의 개념은 간단합니다. CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미합니다.

CPU가 위와 같은 순서로 페이지에 접근 했을 경우 이에 대한 페이지 참조열은 아래와 같습니다.

위와 같이 연속된 페이지를 생략한 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생 시키지 않기 때문입니다. 페이지에 처음 접근할 때 해당 페이지가 물리적 메모리에 없다면 페이지 폴트가 발생합니다.

운영체제는 페이지 폴트가 발생하면 이 에러를 처리하기 위해 페이지 폴트 처리 루틴을 실행합니다. 페이지 폴트 처리 루틴의 주된 목표는 해당 페이지의 유효 비트가 0 인 경우 보조 기억 장치에 있는 페이지를 메모리로 가져오는 작업을 수행하는 것입니다.

그렇기 때문에 첫 번째 접근에 페이지 폴트가 발생하였을 경우 페이지 폴트 처리 루틴을 수행했기 때문에 두 번째부터 열 번째 접근에서는 CPU가 페이지 테이블을 확인하고 바로 메모리에 접근할 수 있기 때문에 폴트가 발생하지 않습니다.

그렇기 때문에 페이지 참조열을 작성할 경우 연속된 페이지를 생략한 채로 작성하는 것입니다. 앞으로 이야기할 페이지 교체 알고리즘들은 모두 페이지 참조열을 바탕으로 하기 때문에 페이지 참조열을 알고 있는 것은 중요합니다.

FIFO 페이지 교체 알고리즘

이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식입니다. 쉽게 말해 "오래 머물렀다면 나가라"는 알고리즘입니다. 이 알고리즘이 어떻게 작동하는지 아래의 페이지 참조열을 통해서 설명해보겠습니다.

위와 같은 순서로 페이지를 적재한다고 할 경우 총 4번의 페이지 폴트가 발생합니다.

이 방법은 좋지 않은 이유는 프로그램 실행 초기에 적재된 페이지 속에는 프로그램 실행 초기에 잠깐 실행되거나 이후에 잠깐 실행되다가 이후에 사용되지 않을 수 있기 때문에 좋지 않은 알고리즘입니다.

2차 기회 페이지 교체 알고리즘

이 알고리즘은 앞선 FIFO에서 먼저 적제되었다고 내쫓는 문제를 해결하기 위한 알고리즘입니다. 하지만 완벽히 해결하지는 못하고 어느 정도 개선한 알고리즘 입니다.

이 알고리즘도 기본적으로 가장 오래 적제된 페이지를 대상으로 내보낼 페이지를 선별합니다. 차이가 있다면 만일 페이지의 참조 비트가 1일 경우 해당 페이지는 사용 했었던 기록이 남아 있는 페이지인 것을 의미합니다. 그러므로 당장 쫓아내지 않고 참조 비트를 0으로 전환하고 전환된 시간을 기록하여 가장 최근에 적재된 페이지로 취급을 합니다.

위와 같은 페이지 참조열과 참조 비트 지닐 경우 3번 페이지의 경우 참조 비트가 1이기 때문에 참조 비트를 0으로 전환한 후 시간을 교체가 일어난 시간을 기록하여 다시 한 번 기회를 주는 알고리즘입니다.

최적 페이지 알고리즘

최적 페이지 알고리즘은 페이지의 사용 빈도를 기준으로 페이지 아웃을 진행하는 알고리즘입니다. 적제되어 있는 페이지 중 사용 빈도가 높다는 말은 그만큼 중요한 페이지라는 것과 동일합니다.

페이지 참조열이 위와 같이 기록되어 있다고 가정하겠습니다. 위의 페이지 참조열에서 페이지 폴트는 2번 발생합니다. 1번 프레임의 경우 사용 빈도가 낮으며 오래되었기 때문에 5번 프레임으로 교체가 이루어집니다. 이후 4번 프레임을 요청 했을 경우 5번 프레임의 빈도가 낮고 오래되었기 때문에 교체가 이루어집니다.

최적 페이지 빈도는 페이지 사용 빈도를 기준으로 작동하기 때문에 페이지 폴트 빈도는 다른 알고리즘에 비해 낮지만 실제 구현이 어렵다는 단점이 존재합니다. 왜냐하면 앞으로 오랫동안 사용되지 않을 페이지를 예측 하는 것은 현실적으로 불가능에 가깝기 때문입니다.

따라서 최적 페이지 교체 알고리즘은 운영체제에서 사용을 하기보다는 성능을 평가하기 위한 목적으로 사용 됩니다. 최적 페이지 교체 알고리즘에 비해서 얼만큼의 페이지 폴트 횟수가 발생하느냐를 통해 페이지 교체 알고리즘을 평가하기 위한 방법으로 사용합니다.

LRU 페이지 교체 알고리즘

LRU(Least Recently Used) 페이지 교체 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다. 앞서 최적 페이지 교체 알고리즘은 오랫동안 사용되지 않을 페이지를 교체하는 것이지만 LRU는 오랫동안 사용되지 않은 페이지를 교체하는 것입니다.

LRU 페이지 교체 알고리즘은 "최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것"이라는 아이디어를 토대로 만들어진 알고리즘입니다.

위의 예시를 기반으로 알고리즘을 적용할 경우 5번 프레임을 요청 했을 경우에 가장 오랫 동안 사용하지 않은 프레임은 2번 프레임이기 때문에 5번 프레임으로 교체가 됩니다. 이 후 오랫동안 사용하지 않은 프레임은 1 번이기 때문에 2번으로 교체가 됩니다.

스레싱과 프레임 할당

페이지 폴트가 자주 발생하는 이유에 나쁜 교체 알고리즘을 사용한 것만이 이유가 되지 않습니다. 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트는 자주 발생하게 됩니다. 극단적으로 프레임의 수가 무한히 많은 컴퓨터와 프레임이 하나인 컴퓨터를 비교하면 프레임이 하나인 프레임을 지닌 컴퓨터에서는 계속해서 페이지 폴트가 발생할 것입니다.

프레임이 부족하여 페이지 폴트가 자주 발생하면 결과적으로 CPU의 이용률 또한 떨어지게 됩니다. CPU가 쉴세 없이 프로세스를 실행해야 컴퓨터 전체의 생산성도 올라가는데 페이지 교체에 너무 많은 시간을 쏟으면 당연히 성능에도 큰 악영향이 있을 수 밖에 없습니다. 이처럼 프로세스가 실행되는 시간보다 프레임을 교체하는데 더 많은 시간이 소요되어 성능이 저하가 되는 문제를 스래싱이라고 정의합니다. 잦은 페이지 교체로 인해 생기는 CPU의 성능 저하

스레싱을 해결하기 위해서는 운영체제가 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 합니다.

프레임의 할당 방법 중 가장 먼저 이야기 할 것은 균등 할당입니다. 총 300개의 프레임을 할당할 수 있다면 각 프로세스에 100개의 프로세스를 할당하는 방식을 이야기 합니다. 하지만 짐작할 수 있듯, 이는 그리 권장할 방법이 아닙니다. 왜냐하면 실행되는 프로세스들의 크기는 각기 다른데, 동일한 프레임 개수를 할당하는 것은 비합리적이기 때문입니다.

이러한 문제로 인해서 등장한 것이 비례 할당입니다. 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스의 크기가 작은 경우 프레임을 적게 나눠주는 방식을 뜻합니다. 하지만 이 또한 완벽한 방식은 아닙니다. 이는 프로세스의 크기가 클지라도 막상 실행해 보니 많은 프레임을 필요로 하지 않은 경우도 있기 때문입니다. 반대로 프로세스의 크기가 작아도 실행해보니 많은 프레임을 필요로 하는 경우도 있기 때문입니다. 즉, 프로세스의 크기는 결국 실행해 봐야 아는 경우가 많다는 것입니다.

그래서 이후에 이야기 할 방법들은 프로세스를 실행해보고 할당할 프레임 수를 결정하는 동적 할당 방식입니다.

동적 할당 방식에 대해서 이야기 하기 위해서는 참조 지역성에 대해서 다시 이야기할 필요가 있습니다. 참조 지역성은 프로그램의 실행 과정에서 전체 주소 공간을 균등하게 접근하는 것이 아니라, 특정 시간에 주소 공간의 일부분만 집중적으로 참조하는 경향이 있습니다. 참조 지역성은 크게 3가지 유형으로 구분 됩니다.

시간적 지역성

시간적 지역성은 최근에 참조된 메모리 위치가 가까운 미래에 다시 참조될 가능성이 높다는 원리입니다. 예를 들어, 반복문 내의 변수는 짧은 시간 간격으로 여러 번 접근됩니다.

이 코드에서 sum 변수는 연속으로 짧은 시간안에 접근이 되기 때문에 첫 번째 접근 이후에는 이 변수가 캐시나 메모리에 남아 있어 빠르게 접근할 수 있습니다.

공간적 지역성

공간적 지역성은 특정 메모리 위치에 접근했을 때, 그 주변 메모리 위치들도 가까운 미래에 접근될 가능성이 높다는 원리입니다. 배열이나 연속된 메모리 구조의 순차적 접근이 대표적인 예시입니다.

순차적 지역성

순차적 지역성은 공간적 지역성의 특별한 경우로, 프로그램 실행이 일반적으로 순차적으로 진행되어 인접한 명령어들이 연속적으로 실행되는 경향을 의미합니다. 분기나 점프 명령이 없다면, 프로그램 카운터(PC)는 메모리 상에서 순차적으로 증가합니다.

참조 지역성이 중요한 이유

컴퓨터 시스템에서 메모리의 접근은 가장 큰 병목 현상 중 하나인데, 이는 CPU와 주메모리 사이의 속도차이가 매우 크기 때문입니다. 이 차이를 줄이기 위해 컴퓨터 구조는 캐시 메모리를 도입했는데, 참조 지역성의 원리가 캐시의 효과를 극대화하는 핵심 요소이기 때문입니다.

시간 지역성 덕분에 한 번 접근한 데이터를 캐시에 저장 해두면, 가까운 미래에 같은 데이터에 다시 접근할 때 느린 메모리가 아닌 빠른 캐시에서 데이터를 가져올 수 있습니다.

공간적 지역성을 활용하면 한 바이트만 가져오는 것이 아니라 "캐시 라인"이라는 더 큰 블록 단위로 데이터를 가져옵니다. 현재 필요한 데이터뿐만 아니라 인접한 데이터도 함께 가져와서 캐시에 저장하는 것입니다.

도서관에서 책을 읽는 상황을 생각해봅시다. 매번 책이 필요할 때마다 서가까지 가서 가져온다면(주 메모리 접근) 시간이 많이 걸립니다. 하지만 자주 참조하는 책들은 책상 위에 두고(캐시에 저장), 필요할 때마다 바로 볼 수 있다면 훨씬 효율적일 것입니다.

참조 지역성은 "어떤 책을 책상 위에 둘 것인가"를 결정하는 데 도움을 줍니다.

방금 읽은 책은 곧 다시 필요할 가능성이 높습니다 (시간적 지역성)
현재 읽고 있는 책과 관련된 다른 책들도 곧 필요할 가능성이 높습니다 (공간적 지역성)

이러한 원리로 책상 위에 적절한 책들을 유지함으로써 서가까지 왔다 갔다 하는 시간을 크게 줄일 수 있습니다. 컴퓨터 시스템에서도 마찬가지로, 참조 지역성 원리를 활용하여 캐시의 효율성을 높이고 전체 시스템 성능을 크게 향상시킬 수 있습니다.

작업 집합 모델

이제 다시 스레싱을 해결하기 위한 동적 페이지 할당 방법에 대해서 이야기 해보겠습니다. 앞서 참고 지역성에 대해 이야기한 것은 작업 집합 모델에 대해 이야기하기 위함이었습니다.

작업 집합은 프로세스가 특정 시간 간격(윈도우 크기 Δ) 동안 활발하게 참조하는 페이지들의 집합입니다. 만약 어떤 CPU가 어떤 프로세스를 실행하는 동안 3초에 일곱 개의 페이지를 집중적으로 참조했다면 운영체제는 그 프로세스를 위해 그 순간만큼은 7개의 프레임을 할당하면 페이지 교체가 빈번하게 발생하지 않을 수 있습니다.

작업 집합 모델을 이용하는 것은 CPU가 과거에 주로 참조한 페이지를 집합으로 구성하고 해당 작업 크기만큼 프레임을 할당할 경우 페이지 교체를 줄일 수 있다는 것입니다.

프로세스가 참조한 페이지가 위와 같고 시간 간격 Δt는 7이라고 가정할 경우 t1 에서 필요한 페이지 참조열은 {5, 6, 7}이고 작업 집합 모델에 따르면 필요한 프레임은 3개입니다.

페이지 폴트 발생 빈도

페이지 폴트의 발생 빈도를 기반으로 페이지 교체를 결정할 경우에는 아래와 같은 기준을 갖고 결정합니다.

페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있는 것이다.
페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있는 것이다.

만일 페이지 폴트율이 상한선보다 더 높다면 그 프로세스는 너무 적은 프레임이 할당되어 있는 것이므로 더 많은 프레임을 할당해주면 됩니다. 만약 하한성보다 낮은 경우에는 너무 많은 프레임이 할당 되어 있는 것이므로 프레임을 회수해주면 됩니다.

결론

가상메모리는 활성화 RAM, 주기억장치와 DASD, 보조 기억장치를 결합하여 넓은 범위의 연속적인 주소를 형성합니다.

가상화 메모리는 사용자에게 실제 메모리보다 더 큰 메모리를 가지고 있다는 환상을 만들어냅니다. 이를 수행하는 방법은 컴퓨터의 운영 체제는 CPU의 일부 중 하나인 MMU를 활용하여 가상의 주소를 물리적 주소로 매핑하여 프로세스나 태스크를 효율적으로 동시에 실행하기 위하여 메모리에 적재할 프로세스들을 관리하여 작업의 효율성을 높입니다.

질문

Q : 작업 집합 모델(Working Set Model)을 설명하고, 이 모델이 어떻게 프로세스에게 적절한 프레임 수를 할당하는 데 도움이 되는지 설명해 보세요.

Q : 가상 메모리에서 '스레싱(Thrashing)'이란 무엇이며, 참조 지역성과 어떤 관련이 있나요? 어떻게 방지할 수 있을까요?

Q : 가상 메모리와 물리적 메모리 사이의 주소 변환 과정을 상세히 설명하고, 다단계 페이지 테이블이 메모리 효율성에 어떤 영향을 미치는지 설명해 보세요.

Q : TLB(Translation Lookaside Buffer)의 역할을 설명하고, TLB가 없다면 시스템 성능에 어떤 영향을 미칠지 분석해 보세요.

Q : 애플리케이션이 메모리 부족 오류로 자주 중단된다고 가정해 보세요. 이 문제를 진단하고 해결하기 위해 어떤 단계를 밟을 것인지 설명해 보세요. 가상 메모리 관점에서 최적화할 수 있는 방안은 무엇인가요?

디버깅 도구의 활용, 운영체제의 관점에서 설명하는 것이 아닌 애플리케이션 레벨에서의 해결 방법을 이야기 할 수 있어야 한다.