[JSCODE 운영체제 5주차] 가상 메모리

안녕하세요 dev_writer입니다. 이번에는 가상 메모리 기법에 대해 알아보겠습니다.
 

연속 메모리 할당

이전까지는 프로세스에게 메모리를 할당할 때, 프로세스의 크기만큼 메모리를 할당받아 여러 프로세스가 연속적으로 배치되는 방식이었습니다.

연속 메모리 할당의 구현 방법

연속 메모리 할당을 구현하는 방법은 크게 세 가지가 있습니다.

최초 적합 (first fit)

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식입니다.
• 검색이 최소화되며, 빠르게 할당할 수 있습니다.

최적 적합 (best fit)

• 운영체제가 빈 공간을 모두 검색해 본 뒤, 적재 가능한 가장 작은 공간에 배치하는 방식입니다.
• 남는 공간이 가장 작은 공간에 배치하기 때문에 가장 최적입니다. (그러나 최초 적합에 비해 시간이 더 걸리게 됩니다.)

최악 적합 (worst fit)

• 운영체제가 빈 공간을 모두 검색해 본 뒤, 적재 가능한 가장 큰 공간에 배치하는 방식입니다.
• 남는 공간이 가장 큰 공간에 배치하기 때문에 가장 아깝습니다.

 

연속 메모리 할당의 문제

이렇게 된다면 어떤 문제가 발생할 수 있을까요?
 
우선 프로세스를 연속적으로 배치하는 만큼, 만약 새로 필요한 프로세스의 크기보다 남은 메모리 공간이 작다면 아예 실행할 수 없을 것입니다.
 
또한 위의 그림에서 프로세스 2가 종료된다면 프로세스 2의 크기만큼만 여유 공간이 생기는데, 이때에도 새로 필요한 프로세스의 크기가 더 크다면 아예 실행할 수 없습니다.
 
이와 같은 현상을 외부 단편화 (External fragmentation) 문제라 합니다.
 

외부 단편화

외부 단편화 문제에 대해 더 알아보겠습니다.
 
프로세스 A, B, C, D가 있고, 각각 50MB, 30MB, 100MB, 20MB를 차지한다고 가정합니다. (즉, 메모리는 200MB)

편의를 위해 실제 용량에 맞게 프로세스 사이즈를 맞추진 않았습니다.

 
이때, 프로세스 B와 D가 실행이 끝나고 종료된다면 다음과 같이 유휴 공간이 50MB로 됩니다.

프로세스 B와 D가 종료될 경우 50MB의 공간이 남습니다.

 
그러나 이때 50MB의 프로세스를 적재할 수 없습니다. 빈 공간이 쪼개져있기 때문입니다.
 
이처럼 외부 단편화는 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상입니다.
 

해결법: 압축 (composition)

해결 방법으로는 압축을 이용하는 것이 있습니다.
 
압축이란, 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식입니다. 즉 위의 예시에서 있던 빈 공간을 한 공간으로 만들기 위해 프로세스들의 위치를 조정하는 것입니다.

압축을 통해 유휴 공간을 한 공간으로 모을 수 있습니다.

 
다만 작은 빈 공간들을 하나로 모으는 동안 시스템이 하던 일을 중지해야 하고, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어려운 문제가 있었습니다.
 
따라서 외부 단편화를 없앨 수 있는 다른 해결 방안들이 등장했고, 이것이 바로 가상 메모리 기법 (이 중 페이징 기법)입니다.
 

페이징을 통한 가상 메모리 관리

연속 메모리 할당은 외부 단편화가 발생할 수 있으며, 물리적 메모리보다 큰 프로세스는 실행이 불가능한 문제 또한 존재합니다.
 
가상 메모리는 외부 단편화를 해결하면서 동시에 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리적 메모리의 크기보다 더 큰 프로세스를 실행할 수 있도록 해 줍니다.
 
이를 위한 기술로는 페이징과 세그멘테이션이 있으며, 대부분의 운영체제는 페이징을 활용합니다.
 

페이징

페이징은 프로세스의 논리적 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리의 물리적 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법입니다.

사진 출처: https://goodmilktea.tistory.com/35

스와핑

페이징을 공부할 때 스와핑 (swapping)이 사용될 수 있는데요, 스와핑에 대해서도 알아보겠습니다.

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역 (스왑 영역)에 두고 (스왑 아웃), 그로 인해 생기게 된 빈 공간에 새로운 프로세스를 적재 (스왑 인)하는 과정입니다.
• 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고, 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법입니다.
• 이것을 통해 지금 당장 사용되지 않는 프로세스들을 메모리에서 없앰으로써 메모리를 더 효율적으로 사용할 수 있습니다.
• free, top 명령어 등을 통해 스왑 영역의 크기를 확인할 수 있습니다.

 

페이징에서의 스와핑

페이징에서의 스와핑은 아래 특징이 있습니다.

1. 페이징을 사용하는 시스템에서는 프로세스 전체가 스왑 아웃/스왑 인 되는 것이 아니라, 페이지 단위로 스왑 아웃/스왑 인 됩니다.
2. 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃되고, 실행에 필요한 페이지들은 메모리로 스왑 인이 됩니다.
3. 페이징 시스템에서의 스왑 아웃을 페이지 아웃, 스왑 인을 페이지 인이라 부르기도 합니다.
4. 페이징에서의 스와핑은, 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없음을 나타내기도 합니다. 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있습니다. 이를 통해 물리적 메모리보다 더 큰 프로세스를 실행할 수 있게 됩니다.

 

페이지 테이블

프로세스가 물리적 메모리에 불연속적으로 배치되어 있을 경우, CPU 입장에서는 이를 순차적으로 실행할 수 없습니다. 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 모두 알고 있는 것은 어렵기 때문입니다. (프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서는 '다음에 실행할 명령어 위치'를 알기 어려워집니다.)
 
이를 해결하기 위해 페이징 시스템은 프로세스가 비록 실제 메모리 내의 주소인 물리적 주소에 불연속적으로 배치되더라도, CPU가 바라보는 주소인 논리적 주소에는 연속적으로 배치되도록 페이지 테이블을 이용합니다.
 
페이지 테이블은 프로세스마다 가지고 있는데, 이는 프로세스마다 페이지가 있고, 그 페이지는 각기 다른 프레임에 할당될 수 있기 때문입니다.
 

내부 단편화

페이징은 내부 단편화 (Internal fragmentation) 문제를 야기할 수 있습니다.
 
프로세스를 페이지 단위로 분할할 때, 마지막 부분에서 한 페이지를 다 채우지 못할 수도 있습니다.
 
예시로 프로세스의 크기가 108KB일 때 페이지 크기가 10KB라면 마지막 부분에서 2KB가 비워져 있게 됩니다.
 
이러한 예시처럼, 보통 내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생합니다.
 

리눅스에서는 하나의 페이지 크기를 확인할 때 getconf PAGESIZE 명령어를 통해 확인할 수 있습니다.

리눅스를 포함한 일부 운영체제에서는 기본적으로 설정된 페이지 크기보다 더 큰 페이지도 일부 허용하는데, 이러한 페이지를 대형 페이지 (huge page)라고 합니다.
그러나 많은 전공서에서는 기본적으로 모든 페이지들의 크기는 일정하다고 설정합니다.

 

PTBR

페이징 시스템을 이용할 시 프로세스마다 페이지 테이블을 가지고 있다고 하였습니다.
 
이때, 이 페이지 테이블은 PTBR (페이지 테이블 베이스 레지스터)를 통해 프로세스의 페이지 테이블이 적재된 주소 (위치)를 확인할 수 있습니다. 즉, CPU는 PTBR을 통해 각 프로세스들의 페이지 테이블이 어디에 저장되어 있는지를 알 수 있습니다.

각 프로세스들의 페이지 테이블 정보들은 각 프로세스의 PCB에 기록됩니다. 그리고 프로세스의 문맥 교환이 일어날 때, 다른 레지스터처럼 변경됩니다.

 
그런데 페이지 테이블이 메모리에 있으면 메모리에 접근하는 시간이 두 배로 늘어나게 됩니다. 페이지 테이블을 참조하기 위해 메모리에 접근하고, 페이지를 참조하기 위해 다시 메모리에 접근하기 때문입니다.
 

TLB

위의 두 번 접근 문제를 해결하기 위해 TLB (Translation Lookaside Buffer)가 있습니다.
 
TLB는 CPU 곁에 두는 페이지 테이블의 캐시 메모리로써, 페이지 테이블의 일부를 가져와 저장합니다.

• TLB 히트는 CPU가 접근하려는 논리적 주소가 TLB에 있는 경우를 뜻합니다. 이때는 메모리에 한 번 접근하면 됩니다.
• TLB 미스는 CPU가 접근하려는 논리적 주소가 TLB에 없는 경우를 뜻합니다. 이때는 메모리에 두 번 접근해야 합니다.

 

페이징에서의 주소 변환

페이징을 사용하는 시스템에서 특정 주소로 접근하는 방법을 알아보겠습니다.
 
어떤 페이지/프레임에 접근하고 싶은지의 정보와, 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지의 정보를 알아야 합니다.
 
페이징 시스템에서의 논리적 주소는 페이지 번호 (page number)와 변위 (offset)로 이루어져 있습니다.
 
즉, <페이지 번호, 변위>로 이루어진 논리적 주소는 페이지 테이블을 통해 메모리의 <프레임 번호, 변위>로 변환됩니다.
 
논리적 주소의 변위와 물리적 주소의 변위는 서로 같은데, 이는 각 페이지의 크기와 각 프레임의 크기가 같기 때문입니다.

 
논리적 주소가 <5, 2>인 곳에 접근한다고 해 보겠습니다.
 
페이지 번호가 5인 곳을 페이지 테이블에서 조회하면 해당되는 프레임 번호는 1이 될 것이며, 변위가 2이기 때문에 1번 프레임이 위치한 주소값에서 2만큼 증가하면 10번지로 이동하게 됩니다.
 

페이지 테이블 엔트리

각 페이지 테이블의 한 행을 엔트리 (entry)라고 합니다.
 
엔트리에는 페이지 번호, 프레임 번호 말고도 추가적인 정보가 들어갈 수 있습니다.
 
유효 비트 (valid bit)
유효 비트는 현재 해당 페이지에 접근 가능한지 여부를 나타냅니다. 즉 메모리에 적재되어 있는지, 혹은 보조기억장치에 있는지를 나타냅니다.
 
만약 유효 비트가 0인 (메모리에 없는) 페이지에 접근하려고 한다면, 페이지 폴트 (page fault) 인터럽트가 발생합니다.

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

 
보호 비트 (protection bit)
보호 비트는 페이지 보호 기능을 위해 존재하는 비트입니다.
 
어떤 페이지는 읽기 전용으로만 해야 하고, 어떤 페이지는 읽기 및 쓰기가 가능한 페이지로 할 수 있을 것입니다. 또는 쓰기 전용으로 할 수도 있습니다.
 
참조 비트 (reference bit)
참조 비트는 CPU가 이 페이지에 접근한 적이 있는지의 여부를 알려줍니다.
 
수정 비트 (modified bit = 더티 (dirty) 비트)
수정 비트는 CPU가 이 페이지에 데이터를 쓴 적이 있는지의 여부를 알려줍니다.
 
수정 비트가 필요한 이유는 이 페이지가 메모리에서 사라질 때 보조기억장치에서 쓰기 작업을 해야 하는지를 판정하기 위해 필요합니다.
 
만약 CPU가 데이터를 작성하지 않았다면, 보조기억장치와 메모리에 있는 내용은 서로 같을 것입니다. 이렇게 한 번도 수정된 적 없는 페이지가 스왑 아웃될 경우에는 추가 작업 없이 새로 적재된 페이지로 덮어쓰기만 하면 됩니다.
 
그러나 CPU가 쓰기 작업을 한 경우는 두 내용이 서로 다르기 때문에 수정된 적이 있는 페이지가 스왑 아웃 될 경우에는 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 합니다.
 

쓰기 시 복사와 계층적 페이징

지금까지 페이징 기법이 무엇인지 알아보고, 외부 단편화 문제를 해결할 수 있는 것도 알아봤습니다.
 
그런데 페이징 기법은 외부 단편화 문제 말고도 다른 문제들을 해결할 수 있습니다.
 

쓰기 시 복사

대표적인 예로, 프로세스 간 페이지를 공유할 수 있습니다. 그리고 이것이 활용되는 예시가 쓰기 시 복사입니다.
 
이전에 배운 프로세스의 fork 명령어를 보면, 부모 프로세스가 자식 프로세스를 만들 때 사용하였습니다. 그리고 프로세스는 기본적으로 자원을 공유하지 않기 때문에, 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재되었습니다.
 
이 방식은 프로세스 생성 시간 지연을 불러오며, 메모리 낭비 또한 발생하게 됩니다.
 
그러나 이때 쓰기 시 복사를 사용하면, 부모 프로세스와 동일한 자식 프로세스가 복제되어 생성될 경우 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리키게 됩니다.
 
만약 부모 프로세스나 자식 프로세스가 페이지에 쓰기 작업을 수행하려고 한다면, 해당 페이지는 별도의 공간으로 복제됩니다.
 

계층적 페이징

프로세스 테이블의 크기는 생각보다 작지 않습니다. 프로세스의 크기가 커지면, 프로세스 테이블의 크기 또한 커지게 됩니다. 이때 프로세스를 이루는 모든 테이블 엔트리를 메모리에 두는 것은 큰 낭비이며, 때문에 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 방법을 찾게 되었습니다.
 
그것이 바로 계층적 페이징 (hierarchial paging)이며, 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식입니다.
 
계층적 페이징을 함으로써 모든 테이블을 항상 메모리에 유지할 필요가 없어졌으며, 페이지 테이블 중 몇 개는 보조기억장치에 있어도 무방합니다. (추후 해당 페이지 테이블을 참조해야 할 때가 있으면 그때 메모리에 적재하면 됩니다.)

다만, CPU와 가장 가까이 위치한 페이지 테이블 (Outer 페이지 테이블)은 항상 메모리에 유지해야 합니다.

 
계층적 페이지에서의 논리적 주소는 아래 사진처럼 구성되어 있습니다.

 
이것은 다음과 같이 접근할 수 있습니다.

1. 먼저 바깥 페이지 번호 (P1)을 통해 페이지 테이블의 페이지를 찾습니다.
2. 페이지 테이블의 페이지를 통해 프레임 번호 (P2)를 찾고, 변위 (d)를 더함으로써 물리적 주소를 얻습니다.

계층적 페이징은 2단계, 3단계 등으로 구성될 수 있으나, 단계가 너무 깊어진다면 메모리에 접근해야 하는 횟수가 많아지기에 무조건적으로 좋은 것은 아닙니다.
 

페이지 교체와 프레임 할당

페이징 기법을 활용하여 물리적 메모리보다 큰 프로세스를 실행할 수 있다고 했으나, 그럼에도 불구하고 물리적 메모리의 크기는 한정되어 있습니다. 따라서 한 번에 매우 많은 프로세스를 실행할 수는 없습니다.
 
그렇기 때문에 운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록 기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 하며 (페이지 교체), 프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당 (프레임 할당) 할 수 있게 해야 합니다.
 

요구 페이징 (demand paging)

요구 페이징이란, 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 방법을 뜻합니다.

1. CPU가 특정 페이지에 접근하는 명령어를 실행합니다.
2. 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우), CPU는 적재된 프레임에 접근합니다.
3. 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우), 페이지 폴트가 발생합니다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고, 유효 비트를 1로 설정합니다. (즉, 요구 페이징은 페이지가 필요할 때에만 메모리에 적재합니다.)
5. 다시 1번을 수행합니다.

 

순수 요구 페이징 (pure demand paging)

순수 요구 페이징은 아무런 페이지도 적재되어 있지 않은 채 실행부터 하도록 하는 것을 뜻합니다. 적재된 페이지가 없기 때문에 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 발생할 것이고, 실행에 필요한 페이지가 어느 정도 적재된 이후에는 그 빈도가 줄어들게 됩니다.
 

페이지 교체와 페이지 교체 알고리즘

요구 페이징을 계속 반복하다 보면, 물리적 메모리의 용량을 초과하게 될 수도 있습니다.
 
즉, 당장 실행에 필요한 페이지를 적재하다 보면 적재된 페이지 중 일부를 보조기억장치로 내보내야 합니다.
 
이때, 어떤 페이지를 내보낼지를 결정하는 것이 페이지 교체 알고리즘입니다.
 

어떤 것이 좋은 페이지 교체 알고리즘일까?

페이지 교체 알고리즘의 종류는 다양합니다. 좋은 페이지 교체 알고리즘은 페이지 폴트 횟수가 적을수록 좋은 알고리즘인데, 페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능이 저하되기 때문입니다.
 
페이지 교체를 했더니 이전보다 많은 페이지 폴트가 일어났다는 것은, 사용성이 더 높았던 페이지를 억지로 보조기억장치로 내보냈다는 것과 같은 의미입니다.
 

페이지 참조열 (page reference string)

페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지 열을 뜻합니다.
 
예시로, CPU가 2 2 2 3 5 5 5 3 3 7과 같은 순서로 페이지에 접근했다고 가정하면, 2 3 5 3 7이 페이지 참조열이 됩니다.
 
중복된 페이지를 생략한 이유는 페이지 폴트 처리 루틴이 끝난 뒤 다시 접근해서 페이지 폴트가 발생할 이유가 없기 때문입니다. 즉, 페이지 교체 알고리즘의 성능을 측정하는 데 관련이 없습니다.
 
아래 예시를 통해 페이지 교체 알고리즘들을 살펴보겠습니다. 페이지 교체에서 발생하는 페이지 폴트만 페이지 폴트로 간주합니다.
 

FIFO 페이지 교체 알고리즘

• 가장 단순한 방식입니다.
• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식입니다.

1. 2번 페이지를 참조합니다. 프레임에 2번 페이지가 적재됩니다.
2. 3번 페이지를 참조합니다. 프레임에 3번 페이지가 적재됩니다.
3. 1번 페이지를 참조합니다. 프레임에 1번 페이지가 적재됩니다.
4. 3번 페이지를 참조합니다. 메모리에 이미 있으므로 넘어갑니다.
5. 5번 페이지를 참조합니다. 현재 5번 페이지가 메모리에 없으므로 보조기억장치에서 5번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오래 머물렀던 2번 페이지를 내쫓아야 합니다.
6. 2번 페이지를 참조합니다. 현재 2번 페이지가 메모리에 없으므로 보조기억장치에서 2번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오래 머물렀던 3번 페이지를 내쫓아야 합니다.
7. 3번 페이지를 참조합니다. 현재 3번 페이지가 메모리에 없으므로 보조기억장치에서 3번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오래 머물렀던 1번 페이지를 내쫓아야 합니다.
8. 4번 페이지를 참조합니다. 현재 4번 페이지가 메모리에 없으므로 보조기억장치에서 4번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오래 머물렀던 5번 페이지를 내쫓아야 합니다.
9. 2번 페이지를 참조합니다. 이미 메모리에 있으므로 넘어갑니다.
10. 3번 페이지를 참조합니다. 이미 메모리에 있으므로 넘어갑니다.

FIFO 페이지 교체 알고리즘은 단점도 존재합니다. 프로그램 실행 초기에 잠깐 실행될 페이지지만, 프로그램 실행 내내 사용될 페이지라면 먼저 적재되었다고 내쫓아서는 안 됩니다.
 

2차 기회 (second-chance) 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘의 단점을 보완한 알고리즘입니다. 참조 비트를 두는데, 1이라면 CPU가 한 번 참조한 적이 있는 페이지, 0이라면 참조한 적이 없는 페이지입니다.
 
만약 CPU가 한 번 참조한 적이 있던 페이지라면 바로 내쫓지 않고, 적재된 시간을 현재 시간으로 설정하고 맨 끝으로 보내게 됩니다. 그런데 참조한 적이 없던 페이지라면 이 페이지를 내쫓게 됩니다.
 
기본적으로는 FIFO 페이지 교체 알고리즘의 원칙 (오래 머무른 것을 내쫓는 방식)을 따릅니다. 그런데 참조된 적이 있다면 기회를 한 번 더 주는 것입니다.

 
위와 같은 상황이 있다고 해 보겠습니다. 원래 FIFO 방식이라면 맨 왼쪽에 있는 페이지 3이 내쫓을 대상입니다.

 
그런데 2차 기회 페이지 교체 알고리즘에서는 참조 비트가 1이기 때문에 페이지 3의 적재 시간을 현재 시간으로 변경한 뒤 맨 뒤 (최근에 적재된 페이지)로 옮기게 됩니다.
 

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려합니다.
• 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지이며, 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지입니다.
• 즉, 최적 페이지 교체 알고리즘 (optional)은 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘입니다.
• 미래를 기준으로 판단하기 때문에 비현실적입니다.
• 다른 페이지 교체 알고리즘 성능을 위한 하한선으로 간주합니다.

 
페이지 참조열이 아까와 같이 2 3 1 3 5 2 3 4 2 3으로 이루어져 있다고 가정하면, 위 사진과 같습니다.

1. 2번 페이지를 참조합니다. 프레임에 2번 페이지가 적재됩니다.
2. 3번 페이지를 참조합니다. 프레임에 3번 페이지가 적재됩니다.
3. 1번 페이지를 참조합니다. 프레임에 1번 페이지가 적재됩니다.
4. 3번 페이지를 참조합니다. 메모리에 이미 있으므로 넘어갑니다.
5. 5번 페이지를 참조합니다. 현재 5번 페이지가 메모리에 없으므로 보조기억장치에서 5번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오랫동안 사용하지 않을 페이지를 보면 1번 페이지이므로 1번 페이지를 보조기억장치로 옮깁니다.
6. 2번 페이지를 참조합니다. 이미 메모리에 있으므로 넘어갑니다.
7. 3번 페이지를 참조합니다. 이미 메모리에 있으므로 넘어갑니다.
8. 4번 페이지를 참조합니다. 현재 4번 페이지가 메모리에 없으므로 보조기억장치에서 5번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오랫동안 사용하지 않을 페이지를 보면 5번 페이지이므로 5번 페이지를 보조기억장치로 옮깁니다.
9. 2번 페이지를 참조합니다. 이미 메모리에 있으므로 넘어갑니다.
10. 3번 페이지를 참조합니다. 이미 메모리에 있으므로 넘어갑니다.

 

LRU (Least-Recently-Used) 페이지 교체 알고리즘

최적 페이지 교체 알고리즘은 미래를 기준으로 판단했던 페이지 교체 알고리즘이고, LRU 페이지 교체 알고리즘은 과거를 기준으로 판단하는 페이지 교체 알고리즘입니다. 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라고 판단하는 것입니다.
 

 
페이지 참조열이 아까와 같이 2 3 1 3 5 2 3 4 2 3으로 이루어져 있다고 가정하면, 위 사진과 같습니다.

1. 2번 페이지를 참조합니다. 프레임에 2번 페이지가 적재됩니다.
2. 3번 페이지를 참조합니다. 프레임에 3번 페이지가 적재됩니다.
3. 1번 페이지를 참조합니다. 프레임에 1번 페이지가 적재됩니다.
4. 3번 페이지를 참조합니다. 메모리에 이미 있으므로 넘어갑니다.
5. 5번 페이지를 참조합니다. 현재 5번 페이지가 메모리에 없으므로 보조기억장치에서 5번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오래전에 사용했던 페이지가 2번 페이지이므로 2번 페이지를 보조기억장치로 옮깁니다.
6. 2번 페이지를 참조합니다. 현재 2번 페이지가 메모리에 없으므로 보조기억장치에서 2번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오래전에 사용했던 페이지가 1번 페이지이므로 1번 페이지를 보조기억장치로 옮깁니다.
7. 3번 페이지를 참조합니다. 메모리에 이미 있으므로 넘어갑니다.
8. 4번 페이지를 참조합니다. 현재 4번 페이지가 메모리에 없으므로 보조기억장치에서 4번 페이지를 가져옵니다. (페이지 폴트) 또한, 가장 오래전에 사용했던 페이지가 5번 페이지이므로 5번 페이지를 보조기억장치로 옮깁니다.
9. 2번 페이지를 참조합니다. 메모리에 이미 있으므로 넘어갑니다.
10. 3번 페이지를 참조합니다. 메모리에 이미 있으므로 넘어갑니다.

 

기타 페이지 교체 알고리즘

이 외에도 많은 페이지 교체 알고리즘이 있습니다. 이 알고리즘들을 모두 외우려고 하기보다는, 페이지 교체 알고리즘이 무엇인지, 페이지 교체는 왜 해야 하는지, 무엇이 좋은 페이지 교체 알고리즘인지를 생각하며 공부하는 것이 좋습니다.
 

스래싱 (thrashing)

페이지 폴트가 자주 발생하는 이유는 뭘까요?
 
나쁜 페이지 교체 알고리즘을 사용했을 때 일수도 있지만, 프로세스가 사용할 수 있는 프레임 자체가 적을 때에도 페이지 폴트가 자주 발생할 수 있습니다.
 
만약 프레임이 부족하면 페이지 폴트가 자주 발생할 수밖에 없습니다. 이는 곧 CPU의 이용률을 낮추는 효과를 가져오는데, 페이지 폴트가 자주 발생할수록 페이지 폴트를 해결하는 데 드는 시간이 증가되기 때문입니다.
 
이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 문제를 스래싱이라고 합니다.

출처: 혼자 공부하는 컴퓨터 하드웨어+운영체제

 
세로축은 CPU가 얼마나 일을 하고 있는지를 나타내며, 가로축은 멀티프로그래밍의 정도, 즉 동시에 실행되고 있는 프로세스의 수를 의미합니다.
 
동시에 실행되고 있는 프로세스의 수가 많다고 해서 CPU의 이용률이 높다는 것은 아닙니다. 어느 정도까지는 CPU가 일을 계속함으로써 효율이 올라간다고 할 수 있지만, 더 높아질 경우 CPU 이용률이 스래싱으로 인해 떨어짐을 보이고 있습니다.
 

발생 원인

근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문입니다. 그렇기 때문에 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고, 프로세스들에게 적절한 프레임을 할당해주어야 합니다.
 

프레임 할당 방식

스래싱을 해결하기 위해 프로세스들에게 프레임을 할당하는 방식은 크게 균등 할당과 비례 할당이 있습니다.

균등 할당과 비례 할당 방식은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리적 메모리의 크기만을 고려한 방식이라는 점에서 정적 할당 방식이라고도 합니다.

 

균등 할당 (equal allocation)

균등 할당은 가장 단순한 할당 방식으로써, 모든 프로세스들에게 균등하게 프레임을 할당하는 방식입니다.
 
그런데 만약 게임 프로세스와 메모장 프로세스를 예시로 들자면, 이 두 프로세스는 서로 필요로 하는 프레임의 수가 다를 것입니다. 이 점에서 낭비가 발생할 수도 있습니다.
 

비례 할당 (proportional allocation)

비례 할당은 프로세스의 크기를 고려하여, 프로세스 크기에 비례하여 프레임을 할당하는 방식입니다.
 
그런데 이 방식 또한 단점이 있습니다. 프로세스가 필요로 하는 프레임 수는 실행해봐야 압니다. 즉, 크기가 큰 프로세스인데 막상 실행해 보니 많은 프레임을 필요로 하지 않을 수도 있고, 그 반대일 수도 있습니다.
 
프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 작업 집합 모델 (working set model)을 사용하는 방식과, 페이지 폴트 빈도 (PFF, Page-Fault Frequency)를 사용하는 방식이 있습니다.

이 두 개 방식은 프로세스의 실행을 보고 할당할 프레임을 결정한다는 점에서 동적 할당 방식이라고도 합니다.

 
작업 집합 모델 (working set model)
스래싱이 발생하는 이유는 빈번한 페이지 교체 때문입니다. 그렇다면, CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 문제를 개선할 수 있을 것입니다.
 
작업 집합 모델을 구하려면 프로세스가 참조한 페이지와 시간 간격이 필요합니다.

출처: 혼자 공부하는 컴퓨터 하드웨어+운영체제

 
프로세스가 참조한 페이지가 아래와 같고, 시간 간격은 7이었다고 가정합니다.

출처: 혼자 공부하는 컴퓨터 하드웨어+운영체제

출처: 혼자 공부하는 컴퓨터 하드웨어+운영체제

 
페이지 폴트 빈도 (PFF)
페이지 폴트 빈도는 두 개의 가정에서 생겨난 아이디어입니다.

• 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임 수를 가지고 있다.
• 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임 수를 가지고 있다.

출처: 혼자 공부하는 컴퓨터 하드웨어+운영체제

 
가로축은 한 프로세스에 할당된 프레임의 수, 세로축은 페이지 폴트율의 비율을 의미합니다.
 
프로세스의 프레임 수가 매우 많다면 페이지 폴트율은 낮을 것입니다. (그만큼 여유가 있기 때문)
 
반대로, 프레임 수가 매우 적다면 페이지 폴트율은 높을 것입니다. (그만큼 부족하기 때문)
 

출처: 혼자 공부하는 컴퓨터 하드웨어+운영체제

 
임의의 상한선과 하한선을 그어, 페이지 폴트율의 척도를 구할 수 있습니다.
 
따라서 이 범위 안에서만 프레임을 할당하면 됩니다.