4. 메모리 관리

10. 가상 메모리

9 단원에서 배운 메모리 관리 전략의 공통 목표: 동시에 최대한 많은 프로세스를 메모리에 올려서 다중프로그래밍을 가능케 하기. 근데 프로세스 전체가 메모리에 올라가야 실행이 가능했음.

가상 메모리를 통해 프로세스가 전부 다 메모리에 안 올라가있어도 실행이 가능하게 해줄 수 있음. 이러면 프로그램이 물리 메모리보다 클 수 있다는 장점이 있음. 게다가 가상 메모리가 주기억장치를 엄청나게 거대한, 균일한 배열 형태의 기억장치로 간주해서 프로그래머의 시선으로 보는 논리 메모리와 물리 메모리를 구분지어줌. 이러면 프로그래머가 메모리 공간이 얼마나 남았는지 신경 쓰지 않게 해준다는 장점이 있음. 또한 프로세스가 파일과 라이브러리를 서로 공유하게 할 수 있으며, 공유 메모리도 구현 가능함. 추가적으로 효율적인 프로세스 생성 메커니즘도 제공함. 가상 메모리가 구현하기가 쉬운 건 아니지만 대충 사용할 경우 성능이 좀 많이 떨어짐.

단원 목표

• 가상 메모리의 정의 및 장점
• 요구 페이징을 통해 페이지가 메모리에 적재되는 방법
• FIFO, 최적, LRU 페이지 교체 알고리듬 적용
• 실행 중인 프로세스 집합의 의미와 프로그램 지역성과의 연관성
• Linux, Windows 10, Solaris가 가상 메모리 관리하는 법
• C 프로그래밍 언어로 가상 메모리 관리자 시뮬레이션 설계

10.1 배경

9 단원에서의 메모리 관리 알고리듬이 필요한 이유는 이거 하나 때문임: 실행 중인 명령어는 반드시 물리 메모리에 있어야 하기 때문. 당연히 제일 간단한 방법은 그냥 가상 주소 공간을 전부 물리 메모리에 올려버리는 것임. 동적 링크로 좀 이 제약사항을 완화시킬 순 있겠지만, 이건 사용할 때 특별히 조심해야하고, 프로그래머가 추가적으로 일을 좀 해줘야함.

이게 명령어를 물리 메모리에 올리는게 필요해보이고 당연해보이긴 한데, 프로그램의 크기를 물리 메모리에 맞춰야하니까 좀 불편하긴 함. 실제로 보면 생각보다 프로그램을 전부 다 메모리에 올릴 필요가 없기도 함. 예를 들어:

• 프로그램을 작성할 때 오류 상황 처리할 코드를 작성해야할 때가 있음. 물론 실무에서는 거의 발생 안할 수도 있어 아예 실행이 안 될 수도 있음.
• 배열, 리스트, 테이블은 보통 실제 필요한 것보다 더 많이 메모리를 잡곤 함. 배열 안에 원소가 겨우 열 몇 개 밖에 없어도 100 개 씩 잡고 그럼.
• 프로그램의 특정 옵션이나 기능이 거의 사용이 안 될 수도 있음. 예를 들어 대한민국 정부에서 예산안 제대로 공정하게 책정하는 기능은 언제부턴가 안 쓰지 않았음? ㅋ

이런 경우가 발생하는데도 불구하고 프로그램 전부를 메모리에 올려야한다? 이거 선 넘거든요.

프로그램 일부만 올려도 되면:

• 프로그램이 더 이상 실제 물리 메모리에 의해 제약을 받지 않아도 됨. 사실상 매우 거대한 가상 주소 공간에 넣을 프로그램도 작성할 수 있게 되어 프로그래밍이 간단해짐.
• 물리 메모리를 실제로 덜 먹을테니까 동시에 프로그램을 더 많이 실행할 수 있으므로 CPU 효용과 처리율도 높아지면서도 응답 시간이나 턴어라운드 시간이 늘어나지도 않음.
• 프로그램의 일부를 메모리에 적재하거나 스왑하는데 필요한 입출력이 적어지므로 프로그램이 더 빠르게 돌 것임.

즉, 프로그램을 일부만 올릴 수 있게 되면 시스템 뿐만 아니라 사용자에게도 좋음.

가상 메모리 virtual memory는 개발자가 인식하는 논리 메모리를 실제 물리 메모리와 구분하는 것으로 시작함. 이러면 실제 물리 메모리가 얼마 밖에 없어도 프로그래머는 매우 거대한 가상 메모리를 보고 있는 것처럼 해줄 수 있음:

이러면 가상 메모리 덕분에 프로그래머가 남은 물리 메모리량 걱정 안해도 돼서 프로그래밍 자체에만 집중할 수 있게 해줘서 좋음.

프로세스의 가상 주소 공간 virtual address space이란 프로세스가 메모리에 저장되는 논리적(가상의) 시점으로 보는 것임. 보통 이 시각으로 보게 되면 프로세스가 어떤 논리 주소(0이라든가)에서 시작하고, 연속 메모리에 존재하게 될 것임:

9 단원에서 배웠지만, 물리 메모리는 페이지 프레임으로 구성되어있어 프로세스에 할당된 물리 페이지 프레임은 연속되지 않았을 수도 있음. 이건 메모리 관리 장치(MMU)가 논리 페이지를 메모리 내의 물리 페이지 프레임으로 매핑해줌.

위의 그림을 보면 알겠지만 프로그램에서 동적 메모리 할당을 할 때마다 힙이 위로 증가를 하는 형태임. 스택도 마찬가지로 연속해서 함수 호출을 하면 메모리 아래로 내려가는 형태임. 힙과 스택 사이의 빈 공간(구멍)이 가상 주소 공간의 일부긴 하지만 실제 물리 페이지가 없는 상태임. 나중에 스택이나 힙이 커질 때 실제로 물리 페이지를 필요로 하게 됨. 이런 구멍을 갖는 가상 물리 공간을 성긴 sparse 주소 공간이라 부름. 성긴 주소 공간을 사용하면 나중에 프로그램 실행 도중에 스택이나 힙 영역이 커지거나 라이브러리(혹은 다른 공유 개체)를 동적으로 링킹할 때 구멍을 채워줄 수 있다는 장점이 있음.

논리 메모리와 물리 메모리를 구분해준다는 점 말고도 가상 메모리를 사용하게 되면 둘 이상의 프로세스 간 페이지 공유(9.3.4 절)를 통해 파일이나 메모리를 공유할 수 있게 됨. 이러면 이런 이득이 있음:

• 표준 C 라이브러리와 같은 시스템 라이브러리를 여러 프로세스가 공유할 수 있음. 공유 개체를 가상 주소 공간에 매핑해주면 됨. 각 프로세스 입장에선 해당 라이브러리가 마치 자기 가상 주소 공간 안에 있다고 착각하게 되지만, 실제로는 모든 프로세스가 공유하는 물리 메모리에 있는 것임. 일반적으로 라이브러리는 자신과 링킹된 프로세스들의 공간에 읽기 전용으로 매핑이 됨.
  
• 위와 비슷하게 프로세스는 메모리를 공유할 수 있음. 3 단원에서 봤듯이 두 개 이상의 프로세스는 공유 메모리로 통신 가능. 가상 메모리를 사용하면 한 프로세스에서 다른 프로세스가 공유할 수 있는 메모리를 생성할 수 있게 됨. 이 영역을 공유하는 프로세스들도 이 영역을 마치 자기네 가상 주소 공간 안이라고 간주하지만, 실제로는 메모리 내의 물리 페이지는 공유된 형태임. 위의 그림과 유사하다고 생각하면 됨.
• 페이지는 fork() 시스템 호출로 프로세스 생성 시 공유할 수 있어 프로세스 생성이 빨라짐.

나중에 가상 메모리의 다른 장점들을 알아보도록 하고, 우선 요구 페이징으로 가상 메모리 구현법 알아보러 ㄱㄱ.

10.2 요구 페이징

실행할 프로그램을 보조 기억 장치에서 메모리로 올리는 방법 중 하나는 프로그램 전체를 프로그램 실행 시에 물리 메모리에 올리는 건데, 위에서도 언급했듯 프로그램 전체가 필요하지 않을 수도 있음. 사용자가 선택할 수 있는 부분이 많은 프로그램의 경우 사용자가 선택하지 않은 옵션도 포함한모든 옵션을 메모리에 올리게 되버림...

다른 방법은 필요한 페이지만 올리는 것으로, 이걸 요구 페이징 demand paging이라 부르고, 가상 메모리 시스템에서 일반적으로 사용하는 방법임. 이러면 프로그램 실행 중에 추가적인 페이지를 요구할 때만 페이지를 적재해줌. 즉, 접근하지 않은 페이지는 절대로 메모리에 올라갈 일이 없음. 요구 페이징 시스템은 스와핑을 통한 페이징 시스템(9.5.2 절)이랑 유사함. 여기선 프로세스를 보조 메모리(일반적으로 HDD나 NVM 장치 등)에 올렸음. 요구 페이징을 통해 가상 메모리의 대표적인 장점 중 하나를 구현할 수 있음—필요할 때만 프로그램의 부분을 적재하니 메모리를 더 효율적으로 사용할 수 있음.

10.2.1 기본 개념

요구 페이징의 기본 개념은 위에서도 언급했듯 필요할 때만 페이지를 메모리에 올리는 것임. 즉, 실행 중인 부분이 메모리에 올라가있다면, 나머지 부분은 보조 기억 장치에 있다는 뜻이므로, 이 둘을 구분할 수 있게 하드웨어 단에서 지원해줘야함. 9.3.3 절에서 언급했던 유부호 비트 스킴을 여기에 적용하면 됨. 근데 이번엔 비트가 설정된 상태, 즉 유효한 상태는 연관된 페이지가 합법인 페이지이면서 메모리 위에 있다는 의미로 사용하고, 비트가 설정되지 않았을 때, 즉 무효 상태는 페이지가 유효하지 않거나(즉, 프로세스의 가상 주소 공간에 속하지 않음) 유효하긴 한데, 현재 보조 기억 장치 안에 있다는 의미로 사용함. 메모리에 올린 페이지 테이블 엔트리는 기존과 같지만, 현지 메모리에 없는 페이지는 엔트리에 단순히 무효하다고 표기만 해주면 됨. 다음 그림 참고(무효하다고 표기한 페이지를 프로세스가 절대 접근하지 않는다면 아무 효과가 없음을 알 수 있음):

프로세스가 메모리에 없는 페이지에 접근하려고 하면 페이지 부재 page fault가 발생하게 됨. 페이징 하드웨어 입장에서는 주소를 변환할 때 페이지 테이블을 참고해서 보는데, 무효 비트가 설정되어있으니 운영체제에 트랩을 보낼 것임. 운영체제 입장에서는 페이지를 메모리에서 불러와야하는데 실패했으니까 트랩이 발생한 것임. 이런 페이지 부재를 처리하는 법은 생각보다 단순함:

1. 이 프로세스의 내부 테이블(프로세스 제어 블록이랑 같이 저장되어있곤 함)을 확인해서 해당 참조의 메모리 접근의 유무효 여부를 판단.
2. 만약 무효한 참조라면 프로세스 종료. 유효하지만 페이지를 아직 불러온게 아니었다면 이제 이걸 메모리에 올리면 됨.
3. 올릴 수 있는 프레임을 찾음(사용 가능한 프레임 목록에서 하나 가져오는 식으로).
4. 올려야할 페이지를 새롭게 할당한 프레임에 읽어올 보조 기억 장치 연산을 스케줄링해줌.
5. 기억 장치에서 다 읽어오면 이제 페이지가 메모리에 올라갔다는 걸 알려줘야하니까 프로세스랑 같이 저장해뒀던 내부 테이블이랑 페이지 테이블을 수정해줌.
6. 트랩에 의해 인터럽트됐던 명령어 다시 재시작해줌. 마치 페이지가 처음부터 메모리에 존재했던 것 마냥 돌 것임.

극단적인 경우에는 애초에 메모리에 페이지 단 한 개도 없이 프로세스를 실행해줄 수도 있음. 운영체제가 명령어 포인터를 프로세스의 첫번째 명령어로 설정해줄텐데, 이게 애초에 메모리에 없을테니 마로 페이지 부재가 발생할 것임. 이걸 메모리에 올려줘야 계속 실행이 될 것임. 이런 스킴을 순수 요구 페이징 pure demand paging 스킴이라고 함. 필요하기 전까지는 절대로 메모리에 올리지 않는 것임.

이론적으로 보면 몇몇 프로그램은 명령어 실행할 때마다 메모리에서 여러 페이지에 접근할 수도 있음(명령어 하나는 페이지용, 데이터는 여러 개), 즉 명령어마다 페이지 부재가 여러 번 발생할 수도 있음. 이러면 시스템 성능이 매우 떨어짐. 다행히도 실제 실행 중인 프로세스 분석해보니 이런 경우는 거의 일어나지 않음. 프로그램은 10.6.1 절에서 언급할 참조의 지역성 locality of reference을 갖는 경향이 있어 요구 페이징할 때 성능이 괜찮게 나옴.

요구 페이징을 지원하려면 하드웨어가 페이징과 스와핑과 동일한 부분을 지원해줘야함:

• 페이지 테이블. 이 테이블로 유무효 비트나 특수한 보호 비트 값으로 엔트리를 무효로 만들 수 있음.
• 보조 기억 장치. 현재 주기억장치에 아직 안 올라간 페이지를 갖고 있음. 보조기억장치는 주로 고속 디스크나 NVM 장치임. 스왑 장치라고도 부르며, 이 용도로 사용하는 저장 공간을 스왑 공간 swap space이라 부름. 스왑 공간 할당은 11 단원에서 다룸.

요구 페이징 구현할 때의 핵심은 그 어떠한 명령어더라도 페이지 부재 이후에 이걸 재시작할 수 있게 해야한다는 점임. 페이지 부재가 발생하면 프로세스 인터럽트해서 상태(레지스터, 조건 코드, 명령어 카운터)를 저장하니까 필요한 페이지가 이제 메모리에 올라가서 접근 가능하면 정확히 같은 위치에서 프로세스가 다시 재실행되어야 함. 대부분의 경우 이 조건을 맞추는 건 생각보다 쉬움. 페이지 부재는 어디서나 일어날 수 있음. 명령어 추출 시에 페이지 부재가 발생하면 명령어를 다시 추출하면 되는 것이고, 피연산자를 추출할 때 발생하면 명령어를 다시 추출하고 해독해서 피연산자를 다시 가져오면 되는 것임.

최악의 경우를 예시로 보자면, A의 내용물을 B에 더해 C에 저장하는 ADD라는 주소 세 개짜리 명령어를 보면 됨:

1. 명령어 추출 및 해독 (ADD)
2. A 추출
3. B 추출
4. A와 B 더하기
5. 합 C에 저장

C에 저장할 때 페이지 부재날 경우(C가 속한 페이지가 메모리에 없어서) 해당 페이지를 다시 가져오고, 페이지 테이블 수정하고, 명령어 다시 실행하면 됨. 그러면 명령어 다시 추출하고 해독하고, 피연산자 두 개 다시 추출하고, 둘이 다시 더해주면 됨. 뭐 어차피 다시 해야할 일이 많지는 않고(하나의 완성된 명령어보단 적음) 반복이 오로지 페이지 부재가 발생할 때만 발생함.

주된 어려움은 한 명령어가 여러 다른 위치를 수정할 때 발생함. 예를 들어 IBM System 360/370 MVC (문자 옮기기) 명령어를 보면, 한 위치에서 다른 위치로(곂칠 수도 있음) 256 바이트를 옮길 수 있음. 둘 중(복사할 원본과 복사할 곳) 어느 블록이든 페이지의 영역을 넘을 경우 옮기는 도중 페이지 부재가 발생할 것임. 게다가 두 블록이 겹칠 경우 원본 블록이 수정되버려서 명령어 재시작 자체가 불가할 수도 있음.

이건 두 가지 방법으로 수정 가능함. 초소형 코드가 연산을 하고 두 블록의 끝부분까지 접근을 시도하는 것임. 페이지 부재가 만약 발생할 것 같으면 수정되기 전에 이 단계에서 발생할 것임. 페이지 부재가 발생하지 않을 거라는 것을 알면 옮길 수 있게 되는 것임. 다른 방법으로는 임시 레지스터로 뒤짚어 쓴 위치의 값을 잠깐 저장해두는 것임. 페이지 부재가 발생하면 트랩이 발생하기 전에 메모리에 기존 값을 다시 덮어 씌워주어 명령어 재시작이 가능하도록 해줌.

이건 이미 존재하는 아키텍처에 페이징을 추가해서 요구 페이징을 구현할 때 발생하는 유일한 문제는 아니지만, 몇가지를 우선 소개를 한 것임. 페이징은 컴퓨터 시스템에서 CPU와 메모리 사이에 추가가 되는 것임. 즉, 프로세스에게 완전히 투명해야함. 그러므로 사람들이 모든 시스템에 페이징을 추가할 수 있다고 생각할 수도 있음. 물론 요구 페이징이 필요한 환경이 아니라서 페이지 부재가 곧 실제 오류를 뜻하는 환경이라면 맞는 말이지만, 페이지 부재가 추가적인 페이지를 메모리로 올려주고 재시작해달라는 의미도 포함하는 환경이라면 틀린 말이 됨.

10.2.2 사용 가능한 프레임 목록

페이지 부재 발생 시 운영체제는 반드시 필요한 페이지를 보조 기억 장치에서 주기억장치로 올려줘야함. 페이지 부재 해결을 위해 대부분의 운영체제에서는 사용 가능한 프레임 목록 free-frame list을 갖고 있음. 이 목록은 위의 문제에 대한 요구사항을 만족하는 사용 가능한 프레임들이 있는 창고임(사용 가능한 프레임들은 프로세스의 스택이나 힙 영역이 확장할 때 반드시 할당이 되어야 함):

운영체제에서는 보통 필요시 0으로 채우기 zero-fill-on-demand 기법으로 사용 가능한 프레임을 할당해줌. 필요시 0으로 채워진 프레임은 할당되기 전에 "0으로 초기화"되어 기존 내용물이 다 지워짐. (재할당하기 전에 프레임의 기존 내용물을 치우지 않았을 때 발생할 수 있는 잠재적인 보안 문제를 생각하면...)

시스템이 시작하면 모든 사용 가능한 메모리를 사용 가능한 프레임 목록에 넣어줌. 사용 가능한 프레임에 대한 요청을 받을 때마다(예를 들어 요구 페이징 등으로) 사용 가능한 프레임 목록의 크기가 줄어듦. 언젠가는 목록의 크기가 0이 되거나 특정 기준점보다 낮아져 다시 재할당을 해줘야할 수도 있음. 이런 부분은 10.4 절에서 다룸.

10.2.3 요구 페이징의 성능

요구 페이징은 컴퓨터 시스템에 성능에 상당한 영향을 줄 수도 있음. 그 이유를 알려면 우선 요구 페이징된 메모리의 유효 접근 시간 effective access time을 알아봐야함. 메모리 접근 시간을 ma라 표기할 때, 이게 10 나노초라고 가정. 페이지 부재가 없다면 유효 접근 시간은 메모리 접근 시간과 동일함. 하지만 페이지 부재 발생시 우선 이에 대한 페이지를 보조 기억 장치에서 읽어오고, 필요한 워드에 접근해야함.

p가 페이지 부재 발생 확률(0 ≤ p ≤ 1)이라 하면 p가 0에 거의 가까울 것이라고 생각할 수 있음. 즉, 페이지 부재가 얼마 발생 안 할 것임. 효과 접근 시간 곧

효과 접근 시간 = (1 - p) × ma + p × 페이지 부재 시간

이 됨.

효과 접근 시간 계산하려면 페이지 부재에 얼마나 시간이 오래 걸리는지를 알아야 함. 페이지 부재가 발생하면 다음과 같이 진행이 됨:

1. 운영체제에 트랩
2. 레지스터와 프로세스 상태 저장
3. 인터럽트가 페이지 부재임을 확인
4. 페이지 참조가 불법이므로 보조 기억 장치에서 페이지의 위치 찾기
5. 기억 장치에서 사용 가능한 프레임으로 읽기 전송
   1. 읽기 요청이 서비스될 때까지 큐에서 대기
   2. 장치를 찾을 때까지 and/or 지연 속도 동안 대기
   3. 페이지를 사용 가능한 프레임으로 전송
6. 대기하는 동안 CPU 코어를 다른 프로세스에 할당
7. 기억 장치 입출력 하위시스템으로부터 인터럽트 수신(입출력 완료)
8. 다른 프로세스의 레지스터와 프로세스 상태 저장 (6을 수행했을 시)
9. 인터럽트가 보조 기억 장치로부터 왔음을 인식
10. 필요한 페이지가 이제 메모리에 올라갔으므로 페이지 테이블 및 다른 테이블 갱신
11. CPU 코어가 이 프로세스에 할당될 때까지 대기
12. 레지스터, 프로세스 상태와 새 페이지 테이블을 복구해주고 인터럽트 됐던 명령어 재개

위의 단계 중 몇 단계는 언제나 발생하는 건 아님.

여튼 어떤 경우든 페이지 부재 서비스 시간에 제일 큰 부분을 차지하는 건 세 부분임:

1. 페이지 부재 인터럽트 서비스
2. 페이지 읽기
3. 프로세스 재시작하기

코딩을 꼼꼼히만 해주면 첫번째랑 세번째는 몇백 명령어로 줄일 수 있음. 각각 1에서 100 ms가 걸릴 수 있음. HDD를 페이징 장치로 사용할 경우 페이지 교체 시간이 거의 8 ms가 걸림. (통상적인 하드디스크는 일반적으로 레이턴시가 3 ms고, 찾는데에는 5 ms, 전송은 0.05 ms가 걸림. 그러므로 총 페이징 시간은 하드웨어 시간과 소프트웨어 시간 포함해서 약 8 ms임.) 또한 장치 서비스 시간만 지금 논하고 있는 것임. 만약 장치에 프로세스가 줄 서서 대기하고 있으면 이 큐에서 대기하는 시간도 포함해야하니 더 느려짐.

평균 페이지 부재 서브시 시간이 8 ms이고, 메모리 접근 시간이 200 ns 정도 되니 효과 접근 시간을 ns로 표현하면:

효과 접근 시간 = (1 - p) × (200) + p (8 밀리초)
                    = (1 - p) × 200 + p × 8,000,000
                    = 200 + 7,999,800 × p

즉, 효과 접근 시간은 페이지 부재율 page-fault rate에 직접적으로 비례함. 1,000 번 중 한 번 페이지 부재가 발생하면 효과 접근 시간은 8.2 ms임. 요구 페이지하나 때문에 40이라는 계수만큼 컴퓨터가 느려짐. 성능 저하를 10% 미만으로 줄이려면 페이지 부재율을 다음 수준으로 낮춰야함:

220 > 200 + 7,999,800 × p
20 > 7,999,800 × p
p < 0.0000025

즉, 페이징에 의해 발생하는 성능 저하를 받아들일 만한 수준으로 낮추려면 399,990 번 중 한 번 페이지 부재가 발생하는 수준으로 낮춰야함. 즉, 결국 요구 페이징 시스템에서 페이지 부재율을 최대한 낮추는 게 제일 핵심임. 그게 아니라면 효과 접근 시간이 증가해서 프로세스 실행 시간을 상당히 느리게 만듦.

추가적으로 스왑 공간의 전체적인 처리법과 사용법도 봐야함. 파일 시스템에 비해 스왑 공간에서 발생하는 입출력이 일반적으로 더 빠름. 스왑 공간은 훨씬 더 큰 블록으로 할당이 되어있으며 파일 룩업이나 간접 할당 방법을 사용하지 않았기 때문임 (11 단원). 시스템이 더 나은 페이징 처리율을 얻는 방법은 프로세스 시작시 파일 이미지 전체를 스왑 공간에 복사해오고, 스왑 공간에서 요구 페이징을 처리하는 것임. 당연히 이 방법을 사용하면 프로그램 시작시 파일 이미지를 복사해온다는 단점이 있긴 함. 다른 방법으로는 실제 Linux나 Windows와 같은 여러 운영체제에서 사용하는 방법인데, 초기엔 파일 시스템에서 페이지를 요구하다가 교체하면서 이 페이지를 스왑 공간에 써주는 것임. 이 방법을 통해 필요한 페이지만 파일 시스템에서 읽어옴을 보장할 뿐만 아니라 이후에 발생하는 모든 페이징이 스왑 공간에서 발생함을 보장함.

몇몇 시스템에서는 이진 실행 파일을 요구 페이징할 때 사용할 스왑 공간의 크기를 제한하기도 함. 이런 파일을 위한 요구 페이징은 파일 시스템에서 직접 갖고 오도록 하는 것. 하지만 페이지 교체가 호출될 경우 이 프레임은 단순히 덮어 써주고(어차피 수정 안 되니까) 필요할 때마다 파일 시스템에서 페이지를 읽어오기만 하면 됨. 이 방법을 통해 파일 시스템 자체가 보조 저장소가 됨. 하지만 파일과 연관된 페이지(익명 메모리 anonymous라 부름)는 반드시 스왑 공간을 써야함; 이러한 페이지로는 프로세스의 스택이나 힙 등이 있음. 이 방법이 좋은 타협안이라고 생각이 되어져 Linux와 BSD UNIX 등 여러 시스템에서 사용함.

10.3 작성시 복사

10.2 절에서 처음 명령어를 가진 페이지에서 요구 페이징을 해주어 빠르게 프로세스를 실행시키는 법을 보았음. 허나 fork() 시스템 호출을 통한 프로세스 생성의 경우 초기에 페이지 공유(9.3.4 절)과 유사한 기법으로 요구 페이징을 생략할 수도 있음. 이 기법을 통해 빠르게 프로세스를 생성하고 새롭게 생성된 프로세스에 할다알 페이지의 수를 최소화해줄 수 있음.

fork() 시스템 호출은 자신의 부모의 복사본인 자식 프로세스를 생성해주었음. 원래 fork()는 부모의 주소 공간을 복사, 즉 부모의 페이지를 복사해서 자식에게 주었음. 그러나 대부분의 자식 프로세스가 생성 즉시 exec() 시스템 호출을 하기 때문에 부모의 주소 공간을 복사하는게 딱히 필요 없을 수도 있음. 대신 부모와 자식 프로세스가 초기에는 같은 페이지를 공유하는 작성시 복사 copy-on-write 기법을 사용하면 됨. 이런 공유 페이지는 작성시 복사 페이지로 표기를 해둠. 즉, 父子 중 하나가 공유 페이지에 쓰기를 시작하면 공유 페이지의 복사본이 생성된다는 뜻임. 다음 그림을 보면 프로세스 1이 페이지 C를 수정하기 전과 후의 물리 메모리를 볼 수 있음.

자식 프로세스가 스택 부분을 포함하는 작성시 복사 페이지를 수정한다고 가정. 그러면 운영체제가 우선 사용 가능한 프레임 목록에서 프레임 하나를 가져와 이 페이지의 복사본을 만들어주고 자식 프로세스의 주소 공간에 매핑해줌. 자식 프로세스는 부모 프로세스의 페이지 말고 복사한 페이지를 수정하게 됨. 당연히 복사 중 쓰기 기법을 사용하면 둘 중 누군가가 수정한 페이지만 복사가 되고, 나머지는 복사되지 않음. 그리고 당연히 작성시 복사라고 표기된 애들만 수정 가능함. 수정 불가능한(실행 가능한 코드를 포함하는 페이지)도 부모와 자식 간에 공유가 나으함. 작성시 복사는 Windows, Linux, macOS 등의 여러 운영체제에서 일반적으로 사용하는 기법임.

Linux, macOS, BSD UNIX 등을 포함한 여러 UNIX 변형에서는 fork() 시스템 호출을 변형한 vfork()(가상 메모리 포크 virtual memory fork)를 제공함. vfork()는 fork() + 작성시 쓰기와 다르게 작동함. vfork()를 하면 부모 프로세스를 중단시키고 자식 프로세스가 부모 프로세스의 주소 공간을 사용함. vfork()는 작성시 복사를 안쓰기에 자식 프로세스가 부모 주소 공산의 페이지에 수정을 가할 경우 반드시 부모 프로세스가 재개될 때 이걸 알려줘야함. 그러므로 vfork()를 사용하려면 자식 프로세스가 부모의 주소 공간을 수정하지 않는다는 보장이 있어야 쓸 수 있음. 애초에 vfork()는 자식 프로세스가 생성 직후 exec()을 호출한다는 상황에 맞는 용도로 사용하도록 설계되었음. 복사가 발생하지 않으므로 vfork()은 상당히 효율적인 프로세스 생성 방법이며, 가끔 UNIX 명령줄 쉘 인터페이스 구현할 때 사용함.

10.4 페이지 교체

페이지 부재율 언급할 때 각 페이지는 처음 참조될 때 최대 한 번만 부재가 발생한다고 가정했음. 근데 사실 이게 팩트가 아님. 만약 페이지 열 개인 프로세스가 절반만 사용할 경우 요구 페이징은 절대 사용하지 않을 나머지 다섯 페이지를 적재하지 않도록 해주어 입출력 요구를 줄여줌. 또한 다중프로그래밍의 차수도 두 배나 늘 것임. 그러므로 프레임이 40 개라면 원래는 네 개만 돌릴 수 있는데 여덟 프로세스나 돌릴 수 있음.

이렇게 다중프로그래밍의 차수가 증가하면 우리는 메모리를 과다할당 over-allocating하고 있는 것임. 만약 원래 페이지 열 개가 필요한데 실제로는 다섯 페이지만 사용하는 프로세스가 여섯 개가 현재 실행 중이라면, 더 높은 CPU 효용과 처리율을 갖게 되며 프레임 열 개를 앞으로 더 쓸 수 있음. 근데, 갑자기 어느 순간 이 프로세스들이 전부 동시에 뭔가를 해야하는데, 그게 나머지 다섯 프레임을 전부 필요할 수도 있음. 즉, 최대 프레임 수는 40인데 갑자기 60개가 필요할 수도 있음.

게다가 시스템 메모리가 프로그램 페이지만 저장하는 것도 아님. 입출력을 위한 버퍼도 메모리 엄청 잡아 먹음. 이러면 메모리 배치 알고리듬에 상당한 압박을 주게 됨. 입출력과 프로그램 페이지에 얼마나 메모리를 할당해주느냐는 생각보다 처리하게 빡센 문제임. 어떤 시스템에서는 입출력 버퍼에 고정된 비율만큼의 메모리를 할당해주기도 하고, 또 어떤 시스템에서는 프로세스와 입출력 하위시스템이 서로 시스템 메모리를 두고 경쟁하게 만들기도 함. 14.6 절에서 입출력 버퍼와 가상 메모리 기법 간의 밀접한 관계를 설명함.

메모리 과다할당의 경우 다음과 같음. 프로세스 실행 중에 페이지 부재가 발생하면 운영체제가 해당 페이지가 보조 기억 장치에 있는 지를 확인할 것임. 근데 보니까 사용 가능한 프레임 목록에 사용 가능한 프레임이 없는 거임. 다음 그림에서처럼 말임. 이 그림에서는 사용 가능한 프레임이 없다는 걸 물음표로 표현했습니다:

여기서부턴 운영체제에게 여러 선택지가 주어짐. 프로세스를 종료시킬 수도 물론 있겠지만, 애초에 요구 페이징의 의도는 컴퓨터 시스템의 효용과 처리율을 높이려는 것임. 사용자는 이게 페이징된 시스템에서 프로세스가 실행 중이라는 걸 몰라야함. 페이징은 사용자에게 논리적으로 투명해야함. 그러니 종료시키는 건 우선 말도 안되는 선택지임.

대신 사용할 수 있는 방법으로는 표준 스와핑을 사용해서 프로세스를 스왑 아웃해주어 해당 프로세스가 사용하는 프레임을 사용 가능하게 해주어 다중프로그래밍의 단계를 낮춰줄 수 있음. 근데 9.5 절에서 언급했듯, 표준 스와핑은 프로세스 전체를 메모리와 스왑 공간 간에 복사할 때 발생하는 부담 때문에 이제 대부분의 운영체제에서 사용하지 않음. 대부분의 운영체제는 이제 페이지 스와핑을 페이지 교체 page replacement와 결부하여 사용함.

10.4.1 기본 페이지 교체

페이지 교체는 다음과 같이 진행됨. 사용 가능한 프레임이 없으면 우선 현재 사용하지 않는 프레임을 찾아 사용 가능하게 만들어줌. 사용 가능하게 만드려주면 우선 그 프레임의 내용물을 스왑 공간에 작성해주고 해당 페이지가 더 이상 메모리에 없음을 표기해주기 위해 페이지 테이블(및 다른 테이블들 포함)도 갱신해줌:

이제 프레임 하나 비었으니까 페이지 부재가 발생한 페이지를 저장할 공간이 생겼음. 페이지 교체 해주려면 페이지 부재 서비스 루틴에 페이지 교체를 추가해주면 됨:

1. 보조 기억 장치에서 필요한 페이지의 위치를 찾음
2. 사용 가능한 프레임 찾음
   1. 사용 가능한 프레임이 있으면 그거 쓰고
   2. 없으면 페이지 교체 알고리듬으로 피해자 프레임 victim frame을 정함
   3. 피해자 프레임을 보조 기억 장치에 작성해줌(필요시); 페이지와 프레임 테이블을 이에 따라 갱신해줌
3. 필요한 페이지를 새롭게 사용 가능해진 프레임에 읽어옴; 페이지와 프레임 테이블 갱신.
4. 페이지 부재 발생했던 프로세스에서 다시 재개

즉, 사용 가능한 프레임이 없을 경우 페이지 이동이 두 번(페이징 아웃, 페이징 인 각각 한 번씩)이 발생함. 즉 페이지 부재 서비스 시간이 두 배가 되어 효과 접근 시간도 증가하게 됨.

이 부담을 수정 비트 modify bit(혹은 흠집 비트 dirty bit)로 줄여줄 수 있음. 즉, 각 페이지나 프레임에 하드웨어적으로 수정 비트를 넣어주는 것임. 즉, 어떤 페이지에 무슨 바이트가 작성이 되면 수정 비트가 설정이 되어 페이지가 수정이 된 상태임을 나타내는 것임. 즉 페이지 교체를 하려고 할 경우 우선 페이지의 수정 비트를 확인해봄. 비트가 설정 되어있다면 페이지가 보조 기억 장치로부터 읽어왔을 것이므로 페이지가 수정되었음을 알 수 잇음 .이러면 페이지를 기억장치에 작성해줘야함. 만약 수정 비트가 설정되어있지 않다면 페이지가 메모리로 읽어졌을 것이므로 수정되어있지 않을 것임. 이러면 메모리 페이지를 기억장치로 작성할 필요가 없음; 이미 존재할테니까. 이건 읽기 전용 페이지에도 적용가능(이진 코드 페이지 등). 이런 페이지들은 수정이 불가능하니까 필요할 경우 무시해도 됨. 이러면 페이지 부재 서비스하는데 걸리는 시간을 상당히 줄여줌. 만약 페이지가 수정되지 않은 상태라면 입출력 시간을 절반으로 줄여주니까.

페이지 교체는 요구 페이징의 기본임. 이걸로 가상 메모리와 물리 메모리의 분리를 완성시키는 것임. 이걸로 물리 메모리가 적은 프로그래머에게 훨씬 많은 가상 메모리를 제공할 수 있음. 요구 페이징 없으면 가상 메모리가 물리 메모리에 매핑이 될 거고, 이 두 주소는 서로 달라질 수도 있음. 대신 프로세스의 모든 페이지는 물리 메모리에 있어야할 것임. 요구 페이징하면 가상 주소 공간은 더 이상 물리 메모리에 의해 제약을 받지 않음. 만약 20 페이지짜리 프로세스가 있다고 할 때 요구 페이징을 사용해서 열 개만 써도 되고, 필요시 사용 가능한 프레임을 찾는 교체 알고리듬 사용한다고 가정. 수정을 했던 페이지를 교체한다면 그 내용물을 보조 기억 장치로 복사해줌. 나중에 해당 페이지를 참조하면 페이지 부재가 날 것이며, 페이지가 다시 메모리로 올라갈 것이고, 이때 다른 프로세스의 페이지를 교체해줄 수도 있음.

요구 페이징을 구현할 땐 프레임 할당 알고리듬 frame-allocation algorithm과 페이지 교체 알고리듬 page-replacement algorithm 두 가지를 구현해줘야함. 즉, 메모리에 프로세스가 여러 개라면 각 프로세스마다 프레임을 얼마나 할당할지, 그리고 페이지 교체를 해야할 때 교체할 프레임은 어떻게 선택할지 등을 결정해야함. 보조 기억 장치의 입출력이 워낙 비싼 연산이다보니 적합한 알고리듬을 선택을 해야함. 요구 페이징 기법의 성능이 조금만 개선돼도 전체 시스템 성능은 상당히 좋아질 수도 있음.

여러 페이지 교체 알고리듬이 있음. 운영체제마다 자기만의 교체 스킴이 있을 수도 있음. 그래서 어떤 알고리듬을 선택할지에 대해서는 일반적으로 페이지 부재율이 가장 낮은 걸 기준으로 봄.

우선 알고리듬을 평가할 땐 특정 연속된 메모리 참조에서 돌려보고 페이지 부재가 얼마나 발생했는지를 측정함. 여기서 이 연속된 메모리 참조를 참조 연속 reference string이라 부름. 이건 인공적으로 만들어주거나(무작위수 생성기 등으로) 주어진 시스템을 추적해서 각 메모리 참조의 주소를 기록하는 식으로도 만들 수 있음. 후자의 경우 상당히 큰 수(초당 백반 주소 순으로)의 자료를 생성하게 됨. 자료량을 줄이려면 두 가지 사실을 사용하면 됨.

우선 주어진 페이지 크기(페이지 크기는 주로 하드웨어나 시스템에 의해 고정된 크기임)에서 전체 주소보다는 페이지 수만 고려하면 됨. 두번째로는 참조 페이지 p가 있을 때 즉시 뒤따르는 페이지 p에 대한 모든 참조는 절대로 페이지 부재를 야기하지 않는다는 것임. 페이지 p는 처음 참조할 때 메모리에 있을테니, 바로 즉시 다음에 참조를 할 경우 부재가 발생하지 않음.

예를 들어 특정 프로세스를 추적했을 때 다음과 같이 주소가 순서대로 기록되어있다고 가정:

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103,
0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105

페이지당 100바이트일 경우 이 순서는 다음 참조 연속으로 줄일 수 있음:

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

특정 참조 연속에 어떤 페이지 교체 알고리듬을 적용했을 때의 페이지 부재 수를 알아보려면 사용 가능한 페이지 프레임의 수도 알아야함. 당연히 사용 가능한 프레임의 수가 증가할 수록 페이지 부재 수도 줄어들 것임. 위와 같은 참조 연속의 경우 세 개 이상의 프레임을 가질 경우 각 페이지마다 처음 호출할 때 부재가 세 번 발생해서 총 부재가 세 번 발생할 것임. 반대로 사용 가능한 프레임이 하나 밖에 없다면 참조할 때마다 교체가 발생할 것이므로 부재가 총 11 번 발생함. 일반적으로 아래 그림과 같은 곡선을 얻을 것임:

프레임의 수가 증가할 수록 페이지 부재율도 어떤 적은 수준까지 떨어짐. 당연히 물리 메모리를 더 많이 사용하라는 뜻임. 물리 메모리 더 추가하면 페이지의 수도 증가하니까.

다음은 여러 페이지 교체 알고리듬을 소개할 것임. 이때 공통적으로 다음 참조 연속을 사용할 것임

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

이때 메모리는 총 세 프레임임.

10.4.2 FIFO 페이지 교체

가장 간단한 페이지 교체 알고리듬, 선입선출(FIFO) 알고리듬. 각 페이지가 메모리에 올라간 시간 순으로 FIFO 교체하는 것임. 페이지 교체해야할 때가 오면 가장 오래된 페이지를 선택하는 것임. 참고로 페이지가 올라갈 때 시간을 반드시 기록해줘야하는 건 아님. 메모리 안에 있는 페이지를 갖고 있는 FIFO 큐를 만들어주면 됨. 나중에 교체할 때 큐의 머리부분에 있는 페이지를 교체해주면 되고, 메모리에 페이지 올라가면 큐의 꼬리부분에 넣어주면 됨.

예시 참조 연속으로 보자면, 우선 세 프레임은 처음엔 빈 상태일 것임. 첫 세 참조는 (7, 0, 1)를 보면 페이지 부재에 의해 해당 프레임들이 빈 프레임에 올려질 것임. 다음 참조 (2)에 의해 페이지 7이 제일 처음으로 올려졌으니 교체당함. 다음 참조는 0인데, 0은 이미 메모리에 있으므로 부재가 발생하지 않음. 다음은 3이므로 페이지 0이 교체 당함. 근데 또 다음 참조는 0이므로 부재가 발생함. 이제 페이지 1이 0으로 교체당함. 이후엔 다음 그림과 같이 계속 진행이 될 것임:

부재가 일어날 때마다 페이지가 어떻게 바뀌는지 그림으로 한 번에 볼 수 있음. 총 15 번의 부재가 발생함.

FIFO 페이지 교체 알고리듬은 이해하기도 쉽고 구현하기도 쉬움. 근데 성능이 언제나 좋진 않음. 교체 당한 페이지가 한참 전에 초기화할 때 사용했던 모듈이라 더 이상 필요하지 않을 수도 있지만, 반대로 자주 사용하기 때문에 처음부터 초기화를 해줬던 메모리를 담고 있는 페이지일 수도 있음.

우리가 현재 사용 중인 페이지를 교체해준다 하더라도 제대로 돌긴 함. 현재 사용 중인 페이지를 교체해줘도 바로 다음 번에 또 부재가 발생해서 해당 페이지를 다시 갖고 오겠지. 물론 다른 페이지를 또 교체해주겠지만. 그러므로 잘못 교체했다가는 페이지 부재율이 높아져 프로세스 실행 시간이 느려짐. 그런다고 해서 잘못된 실행을 야기하지는 않음.

FIFO 페이지 교체의 문제점을 보려면 다음 참조 연속을 예시로 들면 됨:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

위의 참조 연속을 여러 프레임 수에 대해 적용했을 때의 페이지 부재 수를 정리한 그래프임:

보면 알듯이 프레임 네 개짜리에서 발생하는 부재 수(10 번)가 프레임 세 개짜리에서 발생하는 부재 수(9 번)보다 더 큼. 이런 예측 불가한 결과를 벨라디의 변이 Belady's anomaly이라 부름: 어떤 페이지 교체 알고리듬이 주어졌을 때, 할당 가능한 프레임 수가 증가할 때 페이지 부재율이 오히려 증가할 수 있다는 것임. 누구나 메모리를 증가시키면 성능이 좋아질 거라고 하지만, 초기 연구에 의하면 이게 언제나 참은 아니라는 것을 알 수 있음. 그 결과로 벨라디의 변이이 나온 것임.

10.4.3 최적 페이지 교체

벨라디의 변이 덕분에 최적 페이지 교체 알고리듬 optimal page-replacement algorithm을 개발하게 됨. 모든 알고리듬 중 페이지 부재율이 제일 낮으며 벨라디의 변이가 발생하지 않음. 이런 알고리듬을 OPT 혹은 MIN이라고 부르곤 했음. 그냥 다음과 같음:

가장 오랜 기간 동안 사용하지 않은 페이지를 교체

이러면 고정된 프레임 수에서 가장 낮은 페이지 부재율을 보장함.

우리 예시로 예를 들어보면 최적 페이지 교체 알고리듬 사용시 페이지 부재가 아홉 번 발생함:

처음 세 참조에 의해 부재가 발생해 세 빈 프레임을 전부 채우게 됨. 다음엔 페이지 2가 페이지 7과 교체됨. 페이지 7이 18 참조까지 사용되지 않을 거고, 페이지 0은 5 참조부터 사용될거고, 페이지 1은 14 참조부터 사용될테니까. 페이지 3 참조하면 이제 다음으로 제일 참조가 늦는 페이지 1이 교체당할 것임. 페이지 부재가 아홉 번만 발생하니 15 번 발생했던 FIFO 알고리듬보다는 확실히 나음. (처음 세 번 발생한 공통 부재를 무시한다면 최적 교체가 FIFO 교체보다 두 배나 더 성능이 좋음.) 그 어떤 교체 방법을 써도 아홉 번보다 적게 할 수는 없음.

근데 최적 페이지 교체 알고리듬은 구현하기가 어려움. 앞으로 참조 순서가 어떻게 될지를 미리 알아야하니까. (이거 5.3.2 절의 SJF CPU 스케줄링 알고리듬과 유사한 상황임.) 결과적으로 최적 알고리듬은 오로지 비교할 때만 사용함. 예를 들어 어떤 새로운 알고리듬이 최적은 아니더라도 최악의 경우 최적 알고리듬의 12.3%의 성능을 내고, 평균적으로는 4.7%다 등을 판단할 때 사용함.

10.4.4 LRU 페이지 교체

최적 알고리듬이 현실적으로 불가능하다면 최대한 최적에 근사하는게 좋을 것임. FIFO와 OPT 알고리듬의 차이는(과거를 보냐 미래를 보냐 말고) FIFO 알고리듬은 페이지를 메모리에 올릴 때의 시간을 사용한다는 것이고, OPT 알고리듬은 페이지가 올라갈 시간을 사용한다는 것임. 만약 가장 최근 과거로 미래를 근사할 수 있다면 가장 오랜 기간동안 사용하지 않은 페이지를 교체해줄 수 있음. 이게 바로 최소 최근 사용 알고리듬 least recently used (LRU) algorithm임.

LRU 알고리듬에서 사용하는 시간은 각 페이지가 언제 최근 사용됐느냐임. 페이지를 교체할 때 LRU는 가장 오랜 기간 동안 사용하지 않은 페이지를 선택함. 이걸 과거를 바라보는 최적 페이지 교체 알고리듬이라고 생각하면 됨. (흥미롭게도 SR이 참조 연속 S의 역순이라고 한다면 S에 OPT 알고리듬을 적용했을 때의 페이지 부재율이 SR에 OPT 알고리듬을 적용했을 때의 페이지 부재율과 동일함. 마찬가지로 SR이 참조 연속 S의 역순이라고 한다면 S에 LRU 알고리듬을 적용했을 때의 페이지 부재율이 SR에 LRU 알고리듬을 적용했을 때의 페이지 부재율과 동일함.)

LRU 교체를 예시 참조 연속에 적용할 경우 다음과 같음:

LRU 알고리듬은 총 12 번의 페이지 부재가 발생함. 처음 다섯번의 부재는 최적 교체와 동일함. 근데 페이지 4를 참조하면 LRU 교체의 입장에서는 메모리의 세 프레임 중 페이지 2가 가장 최근에 덜 사용되었으므로 페이지 2가 앞으로 사용될지에 대한 정보 없이 페이지 2를 교체함. 다음엔 페이지 2에 대한 부재가 발생해 메모리의 세 페이지 중 가장 최근에 덜 사용한 페이지 3을 교체함. 이런 문제가 있음에도 LRU 교체는 FIFO 교체보다 세 번이나 덜 부재가 발생함.

LRU 정책은 좋은 알고리듬으로 평가받아 제일 자주 사용되는 페이지 교체 알고리듬임. 근데 여기서 제일 큰 문제는 그래서 어떻게 LRU를 구현하느냐임. LRU 페이지 교체 알고리듬은 하드웨어로부터 추가적인 지원이 좀 필요할 수도 있음. 여기서 문제되는게 바로 가장 최근에 사용한 시간에 따른 프레임 순서를 어떻게 정의하느냐임. 두 가지 방법이 있음:

• 카운터 counter. 가장 간단하게 보면 각 페이지 테이블 엔트리에 사용한 시간 값을 추가해주어 CPU에 가상 시계나 카운터를 더해주는 것임. 메모리 참조할 때마다 해당 시계의 값을 증가시켜주는 것임. 페이지를 참조할 때마다 시계 레지스터의 값을 페이지 테이블 엔트리의 사용한 시간란에 복사해주는 것임. 이렇게 하면 각 페이지별로 가장 마지막에 참조한 "시간"을 언제가 알 수 있게 됨. 이 스킴을 적용하면 페이지 테이블에서 각 메모리 접근 때마다 LRU인 페이지를 찾아 메모리를 작성하게 됨(페이지 테이블의 사용한 시간란에). 페이지 테이블이 변하면(CPU 스케줄링에 의해) 시간들도 마찬가지로 처리해줘야함. 시간값이 오버플로우 날 수도 있으니 주의.
• 스택 stack. 페이지 수의 스택으로 LRU 교체 구현 가능. 페이지 참조할 때마다 스택에서 제거한 다음 가장 위에 올려놓는 것임. 이러면 가장 최근에 사용한 페이지는 언제나 스택의 맨 위에 존재하며, 최근에 가장 덜 사용한 페이지는 언제나 맨 밑에 있음:
  
  엔트리를 스택 중간에서 빼줘야하기에 머리 포인터와 꼬리 포인터를 갖는 이중 연결 리스트로 구현하는 것이 좋음. 페이지를 중간에서 빼고 맨 위에 올려넣을 때 최악의 경우 포인터 여섯 개를 바꿔야할 수도 있음. 각 갱신에 드는 비용이 좀 비싼 편이지만, 교체 당시에 탐색을 할 필요가 없음. 그냥 스택의 맨 밑에 있는 꼬리 포인터가 LRU 페이지임. 이건 특히 소프트웨어나 LRU 교체를 초소형 코드로 구현할 때 적합함.

최적 교체처럼 LRU 교체도 벨라디의 변이가 발생하지 않음. 둘 다 스택 알고리듬 stack algorithm이라는 벨라디의 변이가 발생하지 않는 페이지 교체 알고리듬의 한 유형에 속함. 스택 알고리듬이란 n 개의 프레임을 갖는 메모리에 속한 페이지 집합이 언제나 n + 1 프레임을 갖는 메모리의 페이지 집합의 부분 집합이기에 그런 것임. LRU 교체의 시선에서 메모리의 페이지 집합은 n 개의 최다 사용 페이지이므로 메모리에 계속 있었다는 것임.

참고로 TLB 레지스터 표준을 넘는 하드웨어 지원 없이는 LRU 교체 구현은 불가능함. 시간란이나 스택은 매 메모리 참조마다 갱신이 됨. 이때 갱신할 때마다 인터럽트를 발생시킨다면 최소한 10 배만큼 메모리 참조가 느려져 모든 프로세스를 10 배만큼 느리게 만듦. 메모리 관리할 때 이 정도의 부담은 그 어떠한 시스템도 포용할 수가 없음.

10.4.5. LRU-근사 페이지 교체

실제 LRU 페이지 교체를 하드웨어적으로 충분히 지원해주는 컴퓨터 시스템이 그리 많지 않음. 심지어 아예 하드웨어 지원을 안해서 다른 페이지 교체 알고리듬(FIFO 알고리듬)을 사용해야하는 시스템도 있음. 대부분의 시스템의 경우엔 참조 비트 reference bit를 통해 일종의 지원을 해줌. 하드웨어에서 페이지가 참조될 때(페이지에 아무 바이트나 읽거나 쓸 때) 해당 페이지의 참조 비트를 설정을 해줌. 참조 비트는 페이지 테이블의 각 엔트리에 있음.

초기엔 운영체제가 모든 비트를 (0으로) 비워줌. 프로세스가 실행되면서 하드웨어가 참조된 페이지의 비트를 (1로) 설정해줌. 나중에 시간이 좀 지나면 어떤 페이지가 사용된 페이지고 어떤 페이지가 사용되지 않은 페이지인지를 참조 비트를 통해 알 수 있을 것임. 물론 사용 순서는 모름. 이런 정보가 LRU 교체를 근사하는 페이지 교체 알고리듬의 기본이 됨.

10.4.5.1. 추가 참조 비트 알고리듬

생략

10.4.5.2. 이차 기회 알고리듬

이차 기회 교체의 기본 알고리듬은 FIFO 교체 알고리듬임. 처음에 페이지를 선택할 때 참조 비트를 확인해서 값이 0이라면 이 페이지를 교체해주지만, 만약 1이라면 이 페이지에 한 번 더 기회를 줘서 살려주고, 다음 FIFO 페이지로 넘어감. 페이지에게 한 번 더 기회를 준다는 건, 참조 비트를 비워주고, 도착 시간을 현재 시간으로 재설정해준다는 의미임. 즉, 한 번 더 기회를 맏은 페이지는 다른 페이지가 교체되지 않는 한(혹은 기회를 한 번 더 받거나) 교체를 당할 것이라는 뜻임. 반대로 자주 사용되는 페이지여서 참조 비트가 계속 설정되어있다면 교체 당하지 않을 것임.

이차 기회 알고리듬(시계 clock 알고리듬이라 부르기도)을 구현하는 방법 중 하나는 원형 큐임. 다음으로 교체할 페이지를 가리키는 포인터(시계의 침)가 있음. 프레임이 필요할 때 포인터가 참조 비트가 0인 페이지를 찾을 때까지 진행하는 것임. 진행하면서 참조 비트를 지워줌:

교체할 페이지를 찾았다면 해당 페이지를 교체하고 새 페이지를 교체해준 페이지의 위치에 넣어줌. 최악의 경우 모든 비트가 설정되어있어 포인터가 전체 큐를 순환하면서 각 페이지에게 기회를 한 번 더 주는 형태가 됨. 교체할 페이지를 찾을 때까지 계속 돌면서 참조 비트를 지워주는 것임. 만약 모든 비트가 설정된 상태라면 이차 기회 교체는 결국 FIFO 교체와 동일해짐.

10.4.5.3. 개량 이차 기회 알고리듬

생략

10.4.6. 카운팅 기반 페이지 교체

각 페이지에 참조된 횟수를 기록하는 카운터를 줄 수 있음.

• 최소 사용 빈도 least frequently used (LFU) 페이지 교체 알고리듬의 경우 카운팅 값이 제일 작은 페이지를 교체함. 가장 자주 사용한 페이지가 보통 참조 값이 제일 크니까. 문제가 있다면, 프로세스 초기에는 정말 자주 사용되는 프로세스가 나중 가서는 사용을 아예 안할 경우가 있음. 초기에 미리 카운팅 값 부풀려놔서 나중에 사용 안하더라도 계속 메모리에 남아있는 것임. 이를 해결할 수 있는 방법은 정기적으로 어떤 간격마다 카운트를 오른쪽으로 1비트만큼 쉬프트를 해주어 지수적으로 평균 사용 카운트를 줄여주는 것임.
• 최다 사용 빈도 most frequently used (MFU) 페이지 교체 알고리듬은 카운트가 적은 페이지는 그저 방금 초기화가 되어서 아직 자주 사용한게 아니라는 생각에서 나온 것임.

당연하겠지만 MFU나 LFU 교체가 그리 일반적인 알고리듬이 아님. 구현하는 법도 비쌀 뿐더라 OPT 교체를 그리 잘 근사하는 것도 아님.

10.4.7. 페이지 버퍼링 알고리듬

생략

10.4.8. 어플리케이션과 페이지 교체

생략

10.5. 프레임 할당

여러 프로세스 간 고정된 크기만큼의 비어있는 메모리를 어떻게 할당? 사용 가능한 프레임이 93 개고 프로세스가 두 개가 있다면, 각 프로세스에게 얼마나 프레임을 줘야함?

예를 들어 시스템에 프레임이 128개가 있다고 할 때, 운영체제가 35 개를 먹어서 프레임 93 개가 에 있다고 가정. 순수 요구 페이징을 사용할 경우 93 번의 페이지를 사용 가능한 프레임 목록에 전부 넣을 것임. 나중에 사용자 프로세스가 실행되면서 페이지 부재가 발생할 것임. 첫 93 개의 페이지 부재를 통해 사용 가능한 프레임 목록에 있는 모든 프레임을 갖고 올 것임. 이제 목록이 비어있으니 페이지 교체 알고리듬으로 메모리에 이미 올라간 93 개의 페이지 중에서 어떤 걸 94 번째 페이지와 교체할 지를 결정. 나중에 프로세스 종료되면 93 프레임을 다시 사용 가능한 프레임 목록에 돌려줘야함.

이 간단한 전략에는 여러 변형을 줄 수 있음. 운영체제가 버퍼와 테이블 공간을 사용 가능한 프레임 목록으로부터 할당 받게 해줄 수도 있음. 운영체제가 이 공간을 사용하지 않을 경우 이 공간을 사용자 페이징에 갖다 쓸 수도 있음. 즉, 페이지 부재가 발생하면 페이지가 할당 받을 사용 가능한 프레임이 발생할 것임. 페이지 스왑이 발생할 때 교체를 선택해서 사용자 프로세스가 계속해서 실행 중일 때 기억 장치에 써줄 수 있음. 다른 변형도 가능하지만 기본 전략은 간단함: 사용자 프로세스는 사용 가능한 프레임 아무거나 할당받음.

10.5.1. 최소 프레임 수

여기서 사용하려는 프레임 할당 전략은 여러 부분에서 제한되어있음. 예를 들어 (페이지 공유를 사용하지 않는 한) 사용 가능한 프레임 수를 초과해서 할당을 할 수 없음. 또한 최소한의 프레임만을 할당해야함. 여기서는 후자를 볼 것.

최소한의 프레임만 할당하는 이유 중 하나는 성능임. 당연히 각 프로세스에 할당할 프레임 수가 줄어들면 페이지 부재율이 증가하므로 프로세스 실행이 느려짐. 게다가 페이지 부재는 명령어가 완료되기 전에 발생하기에 명령어도 재시작했어야 했음. 결국 임의의 한 명령어가 참조할 여러 페이지를 가질 수 있는 충분한 수의 프레임을 갖고 있어야함.

예를 들어 우리가 사용할 기계에선 모든 메모리 참조 명령어가 오로지 한 메모리 주소만 참조가 가능하다고 가정. 이 경우 명령어 참조할 때 프레임 최소 하나, 메모리 참조할 때 프레임 하나가 필요함. 만약 1단계 간접 주소가 가능하다면(예를 들어 프레임 16에 대해 load 명령어가 프레임 0의 주소를 의미하는데, 이게 프레임 23에 대한 간접 참조일 경우) 페이징이 최소 프로세스 당 프레임이 세 개가 필요함. (프레임 두 개면 어떤 일이 벌어지겠음?)

최소 프레임 수는 컴퓨터 아키텍처에 의해 정해짐. 예를 들어 만약 어떤 한 아키텍처의 이동 명령어가 어떤 주소 모드에 대해서 하나 이상의 워드가 필요하다면 명령어 자체가 프레임 두 개를 사용해야할 수도 있음. 게다가 여기서 사용할 두 피연산자가 간접 참조일 수도 있으니 총 여섯 개의 프레임이 필요함. 또다른 예시로는 Intel 32 및 64 비트 아키텍처에서의 이동 명령어의 경우 자료를 오로지 레지스터와 레지스터로, 그리고 레지스터와 메모리 간에만 가능하게 되어있어 메모리에서 메모리 이동을 허가하지 않아 프로세스 당 필요한 프레임 수를 제한해줌.

프로세스의 최소 프레임 수가 아키텍처에 의해 결정된다면, 최대 프레임 수는 사용 가능한 물리 메모리의 용량에 의해 결정됨. 아직도 그 사이에 프레임을 얼마나 할당할 것이느냐라는 중요한 질문이 남아있음.