여기서는 가상 메모리에 대해서 다뤄야 하기 때문에 간단하게 정리를 하고 들어가도록 합시다.

가상 메모리(virtual memory)는 컴퓨터 메모리 관리 기법 중 하나로, 프로그램에 실제 메모리보다 더 큰 메모리 공간을 제공하는 것처럼 보이게 하는 기술입니다.

가상 메모리 시스템은 물리 메모리(주 메모리)와 보조 저장 장치(예: 하드 드라이브)를 활용하여, 프로세스가 사용할 수 있는 메모리 공간을 확장합니다.

이를 통해 프로그램은 자신이 실제로 사용할 수 있는 "물리 메모리의 제약"을 넘어서는 데이터와 코드를 처리할 수 있게 됩니다.

가상 메모리의 주요 이점

1. 메모리 공간의 확장

• 가상 메모리는 프로그램에게 실제 물리 메모리보다 훨씬 더 큰 주소 공간을 제공합니다. 이로 인해 프로그램은 더 많은 데이터와 복잡한 처리 작업을 처리할 수 있게 됩니다.

2. 프로세스 간 메모리 보호

• 각 프로세스는 독립된 가상 주소 공간을 가집니다. 이는 한 프로세스가 다른 프로세스의 메모리 영역을 침범하는 것을 방지하여, 시스템의 안전성과 보안을 향상시킵니다.

3. 메모리의 효율적 사용

• 가상 메모리는 사용 중인 메모리 페이지만을 물리 메모리에 적재합니다. 이는 메모리를 보다 효율적으로 사용하게 하며, 필요하지 않는 페이지는 보조 저장 장치에 저장됩니다.

4. 프로그램 실행의 유연성

• 가상 메모리를 사용하면 여러 프로그램이 동시에 실행되는 멀티태스킹 환경에서 각 프로그램이 필요로 하는 메모리를 더 유연하게 할당받을 수 있습니다.

5. 스와핑 및 페이지 교체

• 프로세스의 작업 집합이 물리 메모리에 완전히 적합하지 않을 때, 운영 체제는 가장 적게 사용되는 메모리 페이지를 보조 저장 장치로 이동(스와핑)시킵니다. 이를 통해 물리 메모리를 더 효율적으로 사용할 수 있으며, 필요할 때 다시 물리 메모리로 페이지를 가져올 수 있습니다(페이지 교체).

6. 프로그램 동적 적재

• 가상 메모리 시스템은 프로그램의 일부분만 메모리에 적재하여 실행할 수 있게 함으로써, 프로그램의 시작 시간을 단축하고 메모리 사용을 최적화합니다.

1. 배경

실행 중인 코드는 반드시 물리 메모리에 있어야 한다는 것은 일견 필요하고 타당한 요구 조건으로 보이지만, 프로그램의 크기를 물리 메모리의 크기로 제한한다는 점 때문에 환영할만한 요구 조건은 아닙니다.

사실 실제 프로그램들을 살펴보면 많은 경우에 프로그램 전체가 한꺼번에 메모리에 늘 올라와 있어야 하는 것은 아닙니다.

예를 들어,

• 오류 상황을 처리하는 코드
• 배열, 리스트, 테이블 등에서 사용하지 않는 공간
• 프로그램 내의 어떤 옵션이나 기능

만일 프로그램을 일부분만 메모리에 올려놓고 실행할 수 있다면 다음과 같은 이점이 있습니다.

• 프로그램은 물리 메모리 크기에 대해 더는 제약받지 않게 된다. 사용자들은 매우 큰 가상 주소 공간을 가정하고 프로그램을 만들 수 있으므로, 프로그래밍 작업이 간단해진다.
• 각 프로그램이 더 작은 메모리를 차지하므로 다 많은 프로그램을 동시에 수행할 수 있게 된다. 이에 따라 응답 시간이 늘어나지 않으면서도 CPU 이용률(utilization)과 처리율(throughput)이 높아진다.
• 프로그램을 메모리에 올리고 스왑(swap)하는 데 필요한 I/O 회수가 줄어들기 때문에 프로그램들이 보다 빨리 실행됩니다.

가상 메모리는 실제의 물리 메모리 개념과 개발자의 논리 메모리 개념을 분리한 것입니다.

MMU는 이러한 논리 주소를 물리 주소로 바꿔주는 역할을 수행하면서 주소 변환 작업을 수행합니다.

메모리 내에서의 프로세스 가상 주소 공간을 확인해 보면 스택 영역과 힙 영역 사이에 빈 공간이 있는 것을 확인할 수 있습니다.

이는 스택 영역과 힙 영역이 동적 할당 메모리를 사용하기 때문입니다. 프로그램이 실행되면서 크기가 변하기 때문에 이를 위해 빈 공간이 존재하고 이렇게 공백을 포함하는 가상 주소 공간을 성간(sparse) 주소 공간이라고 합니다.

특히, 이러한 성간 주소 공간에는 "공유 라이브러리"가 올라가서 공유 페이지를 이용하여 메모리를 효율적으로 사용할 수 있습니다.

2. 요구 페이징

실행 프로그램을 보조저장장치에서 메모리로 어떻게 적재할 수 있을까?

가장 간단하게 떠올릴 수 있는 방식은 프로그램의 전부를 물리 메모리에 적재하는 것입니다.

하지만, 앞서 말했지만 이 방식을 메모리 크기의 제약을 받게됩니다.

다른 전략은 필요한 페이지만 적재하는 것입니다. 이 기법을 요구 페이지(demand paging)이라고 하며 가상 메모리 시스템에서 일반적으로 사용됩니다.

요구 페이지 가상 메모리를 사용하면 프로그램 실행 중 "필요할 때만" 페이지가 적재됩니다.

따라서 접근되지 않은 페이지는 물리 메모리로 적재되지 않습니다.

❗️ 중요 ❗️

추가적으로 필요한 개념을 정리하고 가겠습니다.

앞서 9장에서 페이지 테이블에 대한 언급은 많이 해놓았습니다. 중요한 점은 각 프로세스마다 페이지 테이블을 할당받는 다는 것이였습니다.

그렇다면, 여기서 요구 페이징 전략으로 동작한다고 했을 때 프로그램이 로드되고나서 적재되지 않는 데이터에 접근하려고 했을 때 응용 프로그램 수준에서는 어떠한 주소 값을 가지고 있으며, 이 데이터의 실제 저장 장소인 보조 저장 장치의 주소 값을 어떻게 알 수 있을까요?

여기서는 이 개념을 잡고 가야합니다.

먼저, 프로그램이 실행파일로 변환되면서 적재되는 과정을 다시 한번 떠올려 봅시다.

초기 원시 소스 코드는 오브젝트 파일로 컴파일 되고, 그것이 초기에 필요한 오브젝트 파일끼리 합쳐져 실행파일로 만들어 진다고 했습니다.

이것이 로더를 통해서 메모리에 올라가게 되는 것이였고, 필요한 경우 동적 로딩 혹은 동적 연결을 사용할 수 있었습니다.

또한 여기서 나온대로 프로그램에 대한 모든 내용을 메모리에 적재할 필요는 없으며, 필요한 부분만 우선적으로 메모리에 적재하면 됩니다.

여기서, 메모리에 적재한다는 말이 계속해서 나오는데 이것은 프로세스 관점에선 결국 페이지 테이블에 기록한다는 의미를 뜻하게 됩니다.

여기서 중요한 것은 로더를 통해서 메모리에 올라갈 때 로더가 "요구 페이징 전략"을 수행한다는 것이고, 데이터에 접근하는 모든 코드는 논리 주소는 가지고 있지만, 페이지 테이블에 기록되어 있을 수도 있고, 아닐 수도 있는 것입니다.

"요구 페이징 전략"을 사용하는 프로세스에서 로더의 역할을 봐보자.

로더의 역할

1. 실행 파일 로딩: 프로그램 실행 시, 로더는 실행 파일(.exe 파일, ELF 파일 등)을 메모리에 로드합니다. 이 과정에서 프로그램 코드와 데이터, 스택 등이 메모리 상에 할당되며, 초기화가 필요한 데이터는 이 단계에서 메모리로 로드됩니다.

2. 페이지 테이블 초기 설정: 로더는 프로그램의 각 세그먼트(코드, 데이터 등)에 대한 논리 주소 공간을 설정하고, 초기에 필요한 부분(예: 시작 부분의 코드, 글로벌 변수 등)을 메모리에 로드하며, 해당 논리 주소와 물리 주소(메모리의 위치) 사이의 매핑을 페이지 테이블에 기록합니다. 이때, 전체 프로그램을 메모리에 로드하지 않고, 실행에 필요한 부분만 로드하는 경우가 많습니다.

즉, 각 세그먼트들은 논리 주소 공간을 설정하고, 논리 주소를 할당받겠지만 데이터들이 메모리에 로드된 것과는 별개의 얘기라는 것입니다.

이러한 페이지(로드 되지 않은 데이터에 접근하는)는 페이지 테이블에 "유효하지 않음" 혹은 "아직 적재되지 않음" 식으로 표현되어 있습니다.

그렇다면 이것은 어떻게 적재되는 것일까요? 이 데이터가 저장되어 있는 보조 저장 장치의 주소는 어디에 있는 것일까요?

"아직 적재되지 않음" 데이터 처리 과정

1. 페이지 폴트 발생: 프로그램이 메모리에 아직 로드되지 않은 데이터에 접근하려고 하면 페이지 폴트가 발생합니다. 이때 프로세스의 논리 주소를 참조하여 해당 데이터에 접근하려고 시도합니다.
2. 보조 저장장치에서 데이터 위치 찾기:

• 운영 체제는 페이지 폴트를 처리하는 과정에서, 해당 논리 주소에 대응하는 데이터가 보조 저장장치에 어디에 저장되어 있는지를 찾아야 합니다. 이 정보는 "프로그램의 실행 파일" 또는 "해당 데이터에 대한 메타데이터" 내에 저장되어 있습니다.
• 예를 들어, 실행 파일 포맷(예: ELF 형식)은 프로그램의 코드와 데이터 세그먼트가 파일 내의 어디에 위치하는지에 대한 정보를 포함하고 있습니다. 운영 체제는 이 정보를 사용하여 "필요한 데이터의 실제 위치"를 결정합니다.

3. 데이터 로드 및 페이지 테이블 업데이트:

• 운영 체제는 보조 저장장치에서 해당 데이터를 찾아 메모리의 적절한 프레임으로 로드합니다. 그 후, 페이지 테이블은 업테이트하여 논리 주소와 새롭게 할당된 물리 주소(프레임 번호) 사이의 매핑을 설정합니다.

이러한 데이터 처리는 가상 메모리 관리자에 의해 자동으로 수행되며, 프로그램은 투명하게 데이터에 접근할 수 있습니다.

2.1 기본 개념

요구 페이징의 기본 개념은 "필요할 때만 페이지를 메모리에 적재하는 것"입니다.

결과적으로 프로세스가 실행되는 동안 일부 페이지는 메모리에 있고 일부는 보조저장장치에 있습니다.

따라서 이 둘을 구별하기 위해 어떤 형태로든 하드웨어 지원이 필요합니다.

유효 · 무효(valid-invalid) 비트 기법이 여기에 사용될 수 있습니다.

프로세스가 메모리에 올라와 있지 않은 페이지에 접근하려고 하면 어떠한 일이 발생할까요?

이때는 페이지 테이블 항목이 무효로 설정되어 있으므로 페이지 폴트 트랩(page-fault trap)을 발생시킵니다.

페이지 폴트를 처리하는 과정은 다음과 같습니다.

1. 프로세스에 대한 내부 테이블(internal table)[일반적으로 PCB와 함께 유지]을 검사해서 그 메모리 참조(reference)가 유효 · 무효인지를 알아냅니다.
2. 만약 무효한 페이지에 대한 참조라면 그 프로세스는 중단됩니다. 만약 유효한 참조인데 페이지가 아직 메모리에 올라오지 않았다면, 그것을 보조저장장치로부터 가져와야 합니다.
3. 빈 공간, 즉 가용 프레임(free frame)을 찾습니다 (예를 들면, 페이지 프레임 리스트에서 하나를 가져옴).
4. 보조저장장치에 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청합니다.
5. 보조저장장치 읽기가 끝나면, 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정합니다.
6. 트랩에 의해 중단되었던 명령어를 다시 수행합니다. 이제 프로세스는 마치 그 페이지가 항상 메모리에 있었던 것처럼 해당 페이지에 접근할 수 있습니다.

순수 요구 페이징(pure demand paging)은 어떤 페이지가 필요해지기 전에는 결코 그 페이지를 메모리로 적재하지 않는 방법입니다.

즉, 이 전략을 사용한다면 메모리에 페이지가 "하나도" 안 올라와 있는 상태에서 프로세스를 실행시키는 것입니다.

모든 프로그램은 참조의 지역성(locality of reference) 성질을 가지고 있어서 프로그램의 어느 한 특정 작은 부분만 한동안 집중적으로 참조하는데, 이러한 성질 떄문에 요구 페이징은 만족할만한 성능을 보입니다.

요구 페이징을 지원하기 위해 필요한 하드웨어는 페이징과 스와핑을 위한 하드웨어와 동일합니다.

• 페이지 테이블: 보호 비트(protection bit)들 특별한 값 또는 유효/무효 비트를 통해 특정 항목을 무효로 설정할 수 있어야 합니다.
• 보조저장장치(secondary memory): 메인 메모리에 없는 모든 페이지를 가지고 있다. 보통은 고성능의 디스크 또는 NVM 장치입니다. 이를 스왑 장치라고도 하며, 이 목적을 위해 사용하는 저장장치 영역을 스왑 공간(swap space)이라고 합니다.

요구 페이징을 위한 필수적인 요구 사항은 페이지 폴트 오류 처리 후에 명령어 처리를 다시 시작할 수 있어야 한다는 것입니다.

페이지 폴트가 발생하였을 때 프로세스 상태를 보관합니다.

• 레지스터들
• condition code
• instruction counter

문제는 명령어를 실행하는 단계의 도중에 발생하는 경우인데, 다음의 예시를 확인해 봅시다.

1. 명령어(ADD)를 인출(fetch)해서 해독
2. A를 인출
3. B를 인출
4. A와 B를 더한다.
5. 합을 C에 저장한다.

여기서 결과를 C에 기억시키려 할 때 페이지 폴트가 발생하면 C가 속한 페이지를 메모리로 가져오고, 페이지 테이블을 수정한 다음, 그 명령어를 "처음부터" 다시 시작합니다.

그러나 반복 작업이 그렇게 많지는 않으며(최대 한 개의 명령어의 수행), 페이지 폴트가 발생할 때에만 필요합니다.

한 명령어가 많은 기억 장소를 변경하는 것 일때에는 더욱 어려운 문제가 발생합니다.

예를 들면, 256바이트를 한 장소에서 다른 장소(서로 겹칠 수도 있음)로 이동시키는 명령어를 생각해 봅시다.

어느 블록이라도 페이지 경계(page boundary)에서 양쪽에 걸쳐 있으면 이동이 다 끝나지도 않은 상태에서 페이지 폴트가 발생할 수 있습니다.

더구나 원본 블록(source block)과 목적 블록(destination block)이 서로 겹쳐져 있는 경우에는 단순히 명령어를 다시 실행하는 것만으로 문제가 해결되지 않습니다.

이러한 문제는 두 가지 방법으로 해결할 수 있습니다.

마이크로코드를 사용한 겹치지 않는 부분 확인

마이크로코드를 사용하여 데이터 블록의 이동에 앞서 원본 블록과 목적지 블록 사이에 겹치는 부분이 있는지를 "먼저 확인"하는 방법입니다.

마이크로코드는 CPU 내부의 제어 로직에 의해 실행되는 매우 기본적인 명령어 세트로, CPU 동작을 세밀하게 제어할 수 있습니다.

• 작동 방식: 데이터 이동 명령어 실행에 앞서, 마이크로코드는 원본 블록과 목적지 블록의 주소 범위를 계산합니다. 이 계산을 통해 두 블록 사이에 겹치는 부분이 있는지 확인하고, 겹치는 부분이 발견되면 데이터 이동 방식을 조정하여 데이터
  무결성을 보장할 수 있습니다.

데이터 이동 방식을 조정할 때는 페이지 폴트를 발생시켜 미리 관계되는 페이지를 모두 적재한 후에 실행합니다.

임시 레지스터 사용

이 방법은 데이터를 직접 이동시키는 대신, 임시 레지스터를 활용하여 데이터를 안전하게 "중간 저장한 후 목적지에 전송"합니다.

• 작동 방식: 데이터 이동 명령어가 실행될 때, 시스템은 먼저 원본 블록의 데이터를 임시 레지스터로 복사합니다. 이렇게 임시 레지스터에 저장된 데이터는 다음 단계에서 목적지 블록으로 안전하게 이동될 수 있습니다. 이 방법은 원본 데이터가 목적지 데이터에 의해 덮어쓰여지는 것을 방지하여 데이터 무결성을 유지합니다.

2.2 가용 프레임 리스트

페이지 폴트를 해결하기 위해 대부분의 운영체제는 이러한 요청을 충족시키기 위해 사용하기 위한 가용 프레임 풀인 가용 프레임 리스트를 유지합니다.

운영 체제는 일반적으로 zero-fill-on-demand라는 기법을 사용하여 가용 프레임을 할당 합니다. Zero-fill-on-demand 프레임은 할당되기 전에 "0으로 모두 채워져" 이전 내용이 지워집니다.

가용 프레임 리스트는 가용 프레임의 요청이 들어올 때 마다 크기가 줄어듭니다. 어떤 시점에서, 리스트의 크기는 0으로 떨어지거나 특정 임계값 밑으로 떨어져미ㅕ, 이 시점에서 다시 채워져야 합니다.

2.3 요구 페이지 성능

요구 페이징은 컴퓨터 성능에 큰 영향을 줄 수 있습니다.

페이지 폴트가 발생하지 않는다면 실질 접근 시간은 메모리 접근 시간과 같습니다.

하지만, 페이지 폴트가 발생한다면 먼저 보조저장장치에서 해당 페이지를 읽은 다음 워드에 접근해야 합니다.

페이지 폴트는 다음과 같은 순서로 처리됩니다.

1. 운영체제에 트랩을 요청합니다.
2. 레지스터들과 프로세스 상태를 저장합니다.
3. 인터럽트 원인이 페이지 폴트임을 알아냅니다.
4. 페이지 참조가 유효한 것인지 확인하고, 보조저장장치에 있는 페이지의 위치를 알아냅니다.
5. 저장장치에 가용 프레임으로의 읽기 요구를 냅니다.
   a. 읽기 차례가 돌아오기까지 대기 큐에서 기다립니다.
   b. 디스크에서 찾는(seek) 시간과 회전 지연 시간동안 기다립니다.
   c. 가용 프레임으로 페이지 전송을 시작합니다.
6. 기다리는 동안에 CPU 코어는 다른 사용자에게 할당됩니다.
7. 저장장치가 다 읽었다고 인터럽트를 겁니다(I/O 완료).
8. 다른 프로세스의 레지스터들과 프로세스 상태를 저장합니다(6단계가 실행되었을 경우).
9. 인터럽트가 보조저장장치로부터 왔다는 것을 알아냅니다.
10. 새 페이지가 메모리에 올라왔다는 것을 페이지 테이블과 다른 테이블에 기록합니다.
11. CPU 코어가 자기 차례로 오기까지 다시 기다립니다.
12. CPU 차례가 오면 위에서 저장시켜 두었던 레지스터들, 프로세스 상태, 새로운 페이지 테이블을 복원시키고 인터럽트 되었던 명령어를 다시 실행합니다.

더 진행하기 전에 단계별로 짚고 넘어가야 할 부분만 살펴보겠습니다.

우선, 4번의 동작은 페이지 테이블의 각 엔트리에 저장되어 있는 유효/무효 비트를 통해서 페이지 참조가 유효한 것인지 확인할 수 있을 것입니다.

이후, 페이지 참조가 유효하지 않다면 실행 파일 혹은 메타데이터를 참조하여 페이지가 저장되어 있는 위치를 확인할 것입니다.

3번 동작 이후 페이지 참조를 확인하는 작업을 수행하는 것은 MMU라고 했습니다. 따라서, 4번부터는 다른 프로세스 혹은 스레드가 실행 될 수 있도록 Context Swithcing이 일어날 것입니다.

이후 I/O 작업이 완료되고 나서 인터럽트를 CPU가 읽는다면, 프로세스는 다시 실행 가능 상태로 놓이게 됩니다.

페이지 폴트 처리 시간은 다음 3개의 주요 작업 요소로 이루어져 있습니다.

1. 인터럽트의 처리
2. 페이지 읽기
3. 프로세스 재시작

이렇게 실제 접근 시간은 페이지 폴트율(page fault rate)에 비례한다는 것을 알 수 있습니다.

요구 페이징의 또 다른 특성 중 하나는 스왑 공간의 관리입니다.

스왑 공간에서의 디스크 I/O 속도는 일반적으로 파일 시스템의 입출력 보다 빠릅니다.

그 이유는 스왑 공간은 파일 시스템보다 "더 큰 블록"을 사용하기 때문이고, 또 스왑 공간과 입출력 할 때는 파일 찾기(lookup)나 간접 할당 방법 등은 사용하지 않기 때문입니다.

이러한 특성을 고려하여 생각할 수 있는 하나의 옵션은 프로세스 시작 시 전체 파일 이미지를 스왑 공간에 복사한 다음 스왑 공간에서 요구 페이징을 수행하는 것입니다. 이 방법의 단점은 프로그램 시작 시 "파일 이미지를 복사하는 것"입니다.

Linux와 Windows 등 많은 운영체제에서 실제로 사용하고 있는 방법은 프로그램을 처음 시작시킬 때에는 파일 시스템으로부터 요구 페이징을 처리하지만, 그 페이지들이 교체 될때는 스왑 공간에 페이지를 기록하는 것입니다.

어떤 시스템들은 실행 파일(binary file)을 스왑 공간에 넣지 않고 파일 시스템이 직접 페이지를 가져온 후, 페이지들의 교체가 필요하면 덮어쓴다고 합니다. 이렇게 동작할 경우 실제 보조저장장치에 저장되어있는 페이지는 수정되지 않기 때문에 추후에 원본 페이지가 필요하면 다시 읽어들일 수 있습니다.

이렇게 동작할 경우 스왑 공간의 크기를 줄일 수 있습니다.

하지만 파일과 관련 없는 페이지 즉, 익명(anonymous) 메모리 때문에 여전히 스왑 공간은 필요합니다.

3. 쓰기 시 복사

fork()는 부모 프로세스와 똑같은 자식 프로세스를 만들어 준다고 했습니다.

fork()를 사용 후 exec() 시스템 콜을 한다면, 부모로부터 복사해온 페이지들은 다 쓸모없는 것들이 되고 맙니다.

그래서 부모 페이지들을 다 복사해오는 대신 쓰기 시 복사(copy-on-write) 방식을 사용할 수 있습니다.

이 방식에서는 자식 프로세스가 시작할 때 부모의 페이지를 당분간 함께 사용하도록 합니다. 이때 공유되는 페이지를 쓰기 시 복사 페이지라고 표시합니다.

둘 중 한 프로세스가 공유 중인 페이지에 쓸 때 그 페이지의 복사본이 만들어진다는 의미입니다.

Linux, macOS 및 BSD UNIX를 포함한 몇 가지 UNIX 변동들은 fork() 이외에 vfork() (virtual memory fork)라는 시스템 콜을 제공합니다.

vfork()를 하면 부모 프로세스는 보류되고 자식이 부모의 주소 공간을 사용하게 됩니다.

vfork()는 쓰기 시 복사를 사용하지 않으므로, 자식이 부모 주소 공간의 페이지를 수정하게 되면 변경된 페이지가 재실행시 부모 프로세스에 그대로 보입니다.

vfork()는 자식이 만들어지자마자 exec()를 하는 경우를 위해 마련된 것입니다. 페이지가 전혀 복사되지 않으므로 vfork()는 매우 효율적이며 UNIX 명령어 해석기인 shell 구현 시에도 사용됩니다.

4. 페이지 교체

요구 페이징을 사용하게 되면서, 실제로 사용하는 페이지만 적재하게 되었고 가용 가능한 물리 프레임이 늘어나게 되면서 다중 프로그래밍 정도를 높일 수 있게 되었습니다.

하지만, 여기서 너무 높이게 될 경우에 메모리 과할당(over-allocating)이 발생합니다.

예를 들어서, 총 40개의 프레임이 있을 때 10개의 페이지 중 5개만을 사용하는 6개의 프로세스를 실행시키면, 10개의 프레임은 남겨놓고 높은 CPU 활용률과 처리율(throughput)을 얻을 수 있습니다.

그러나 특정 데이터 조합에 대해 이 프로세스들이 10페이지 모두를 사용해야 하는 상황이 발생한다면 60프레임을 필요로 하게 됩니다.

더욱이 시스템 메모리는 페이지 저장 용도 외에도, I/O를 위한 버퍼도 필요로 합니다.

결국 메모리 초과 할당은 가용 가능한 프레임 목록에 가용한 프레임이 "없을 때" 발생하는 것이고 이것을 위한 전략이 필요합니다.

가장 간단한 방법 중 하나는 프로세스를 종료하는 것이지만 이것은 요구 페이징의 사용 목적인 시스템의 활용률과 처리율을 올리기 위함에 맞지 않습니다.

다른 방법으로 표준 스와핑을 사용할 수 있지만, 전체 프로세스를 복사하는 오버헤드로 인해 더는 사용하지 않는다고 했습니다.

대부분의 운영체제는 페이징 스와핑과 페이지 교체를 결합하여 사용합니다.

4.1 기본적인 페이지 교체

페이지 폴트 서비스 루틴이 페이지 교체를 포함하게 된다면 다음과 같이 동작하게 됩니다.

1. 보조저장장치에서 필요한 페이지의 위치를 알아냅니다.
2. 빈 페이지 프레임을 찾아냅니다.
   a. 비어 있는 프레임이 있다면 그것을 사용합니다.
   b. 비어 있는 프레임이 없다면 희생될(victim) 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동시킵니다.
   c. 희생될 페이지를 보조저장장치에 기록하고(필요한 경우), 관련 테이블을 수정합니다.
3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정합니다.
4. 페이지 폴트가 발생한 시점에서부터 프로세스를 계속합니다.

여기서 희생될 페이지를 필요한 경우에 보조저장장치에 기록한다고 했는데, 하나의 예로 희생될 페이지가 읽기-전용(read-only)일 경우 보조저장장치에 그대로 남아있을 것이므로 굳이 기록할 필요가 없을 것입니다.

빈 프레임이 없는 경우에는 디스크를 두 번(프레임 비울 때, 읽어 들일 때) 접근해야 합니다.

이러한 오버헤드(overhead)는 변경 비트(modify bit 또는 dirty bit)를 사용해서 감소시킬 수 있습니다.

각 페이지나 프레임은 그것과 관련된 변경 비트를 하드웨어 가지게 됩니다.

변경 비트는 CPU가 페이지 내의 어떤 바이트라도 쓰게 되면 페이지가 변경되었음을 나타내기 위해 설정합니다.

변경 비트가 설정되어 있지 않다면 메모리로 읽혀 들어온 후 "변경되지 않았음"을 알 수 있습니다.

따라서, 보조저장장치상의 복사본이 변경되지 않았다면(예를 들면 다른 페이지에 의해) 메모리 페이지를 보조저장장치에 기록할 필요가 없습니다.

이러한 방법은 I/O 시간을 반으로 줄여줍니다.

요구 페이징 시스템은 두 가지 중요한 문제를 해결해야 하는데, 그것은 프레임 할당(frame-allocation) 알고리즘과 페이지 교체(page-replacement) 알고리즘입니다.

여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 할지 결정해야 합니다.

또한, 페이지 교체가 필요할 때마다 어떤 페이지를 교체해야 할지 결저앻야 합니다.

많은 페이지 교체 알고리즘이 존재하는데, 일반적으로는 페이지 폴트율이 가장 낮은 것을 선정합니다.

4.2 FIFO 페이지 교체

가장 간단한 페이지 교체 알고리즘은 FIFO(first-in first-out) 알고리즘입니다.

FIFO 교체 알고리즘은 어떤 페이지를 교체해야 할 때, 메모리에 올라온 지 가장 오래된 페이지를 내쫒습니다.

페이지가 올라온 시간을 페이지마다 기록해도 되고, 아니면 페이지들이 올라온 순서로 큐(FIFO queue)를 가지고 있어도 됩니다.

동작의 예시는 아래와 같습니다.

여기서 참조열은 페이지 번호라고 생각하면 되고, 페이지 프레임은 프로세스가 할당받는 프레임으로 3개를 할당받은 상태라는 것입니다.

이 방식의 가장 큰 문제는 할당해주는 프레임을 늘려준다고 해도, 페이지 폴트가 감소한다는 보장을 해주지 않는다는 것입니다.

예를 들어, 4개의 프레임을 할당했을 때 페이지 폴트가 10번 일어났는데, 3개의 프레임을 할당하면 페이지 폴트가 9번 일어날 수 있다는 것입니다.

이러한 현상을 Belady의 모순(Belady's anomaly)라고 부릅니다.

4.3 최적 페이지 교체

최적 교체 정책이란 모든 알고리즘보다 낮은 페이지 폴트율을 보이며 Belady의 모순이 발생하지 않습니다.

이러한 정책은 존재했고 OPT 또는 MIN으로 불렸습니다.

이것은 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것으로 동작합니다.

좋은 성능을 보여주지만, 이 알고리즘의 실제 구현은 어렵습니다.

왜냐하면, 이 방식은 프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아야 하기 때문입니다. (SJF CPU 스케줄링 알고리즘에서 발생한 현상)

4.4 LRU 페이지 교체

최적 알고리즘이 불가능하다면, 최적 알고리즘의 근사 알고리즘은 가능할 것입니다.

FIFO와 OPT 알고리즘의 결정적인 차이는 FIFO 알고리즘이 페이지가 메모리로 들어온 시간을 이용하는 데 비해 OPT 알고리즘은 페이지가 "사용될" 시간을 이용한다는 것입니다.

최근의 과거를 가까운 미래의 근사치로 본다면 가장 오랜 기간 동안 사용되지 않은 페이지를 교체할 수 있습니다.

이 기법이 least-recently-used(LRU) 알고리즘입니다.

LRU 알고리즘은 페이지마다 "마지막 사용 시간"을 유지합니다.

페이지 교체 시에 LRU는 가장 오랫동안 사용되지 않은 페이지를 선택합니다.

이 정책은 미래 대신 과거 시간에 대해 적용한 최적 교체 정책으로 생각할 수 있습니다.

LRU는 FIFO 알고리즘보다 훨씬 더 우수하다는 것을 위의 동작에서 확인할 수 있습니다.

LRU 정책은 페이지 교체 알고리즘으로 자주 사용되며 좋은 알고리즘으로 인정받고 있습니다.

문제는 "어떻게" 이 알고리즘을 구현하느냐 하는 것입니다.

LRU 페이지 교체 알고리즘은 하드웨어의 지원이 필요합니다. 프레임들을 최근 사용된 시간 순서로 파악할 수 있어야 하는 것입니다.

• 계수기(counters): 가장 간단한 방법으로, 각 페이지 항목마다 "사용 시간 필드"를 넣고 CPU에 논리적인 시계나 계수기를 추가합니다.
  • 메모리에 접근될 때마다 시간이 증가합니다.
  • 페이지에 대한 참조가 일어날 때마다 페이지의 사용 시간 필드에 시간 레지스터의 내용이 복사됩니다. 이렇게 각 페이지의 마지막 참조 "시간"을 유지할 수 있습니다.
  • 최종적으로 시간 값이 가장 작은 페이지가 교체됩니다.
• 스택(stack): LRU 교체 정책의 다른 구현 방법은 페이지 번호의 스택을 유지하는 방법입니다.
  • 일반적인 스택과 유사하게 동작하면 되지만, 꼭대기는 항상 가장 최근에 사용된 페이지가 오도록 합니다.
  • 이를 구현하기 위해서는 업데이트 작업이 필요하여 보통 double linked list로 구현합니다.
  • 내부 요소를 탐색하는 과정이 요구될 수 있습니다.
  • 매 갱신 시에는 약간 더 오버헤드가 크지만 교체가 일어날 경우 페이지를 탐색할 필요가 없게 됩니다.

LRU 방식은 최적 교체와 마찬가지로 Belady의 모순 현상을 야기하지 않습니다. 이러한 알고리즘들을 스택 알고리즘(stack alogrithm)이라고 부릅니다.

스택 알고리즘은 n개의 프레임에 수록되는 페이지의 집합이 항상 n + 1 개의 프레임에 수록되는 페이지의 집합의 부분집합이 되는 알고리즘입니다.

양쪽 LRU 구현 방법 모두 반드시 표준적인 TLB 레지스터 이상의 하드웨어 지원이 있어야 합니다. 계수기 값과 스택을 갱신하는 일을 메모리 참조때마다 수행되어야 합니다.

이러한 작업을 소프트웨어로 하기 위해 인터럽트를 사용한다면 최소 10배 이상 메모리 참조 속도가 느려지고 성능 저하로 이어집니다.

이러한 메모리 관리 오버헤드를 감당할 수 있는 시스템은 거의 없습니다.

4.5 LRU 근사 페이지 교체

LRU 페이지 교체 지원을 충분히 할 수 있는 하드웨어는 많지 않습니다.

그러나 많은 시스템은 참조 비트(reference bit)의 형태로 어느 정도 지원은 하고 있습니다.

페이지 참조가 있을 때마다 (페이지 내의 어떤 바이트라도 읽거나 쓸 때) 하드웨어가 그 페이지에 대한 참조 비트를 설정합니다. 참조 비트는 페이지 테이블에 있는 각 항목과 대응됩니다.

처음에 모든 참조 비트는 운영체제에 의해 0으로 채워집니다.

프로세스가 실행되면서 참조되는 페이지의 비트는 하드웨어가 1로 세팅합니다.

이를 통해서 페이지의 사용과 미사용을 알 수 있고 이러한 부가적인 정보가 많은 LRU 근사 알고리즘의 기본이 됩니다.

4.5.1 부가적 참조 비트 알고리즘

일정한 간격마다 참조 비트들을 기록함으로써 추가적인 선후 관계 정보를 얻을 수 있습니다.

각 페이지에 대해 8비트의 참조 비트를 할당합니다. 일정한 시간 간격마다 타이머 인터럽트(timer interrupt)를 걸어서 운영체제가 참조 비트를 8비트 정보의 최상위 비트로 이동시키고 나머지 비트들은 하나씩 오른쪽으로 이동시킵니다.

이 8비트 시프트 레지스터(shift register)는 가장 최근 8구간 동안의 그 페이지의 사용 기록을 담고 있습니다.

이 8비트 값을 정수로 생각하면 가장 작은 수를 작는 페이지가 LRU 페이지가 되고 이를 교체할 수 있습니다.

물론 사용하는 비트 수는 달라질 수 있고, 갱신을 가능한 가장 빠르게 하기 위한 크기가 선택됩니다.

극단적인 경우 0이 될 수 있고 이 경우 참조 비트만이 남게 되는데 이 알고리즘을 2차 기회 알고리즘이라고 합니다.

4.5.2 2차 기회 알고리즘

2차 기회 알고리즘은 기본은 FIFO 교체 알고리즘입니다.

그러나 페이지가 선택될 때마다 "참조 비트를 확인"합니다.

참조 비트가 0이면 페이지를 교체하고 1이면 다시 한번 기회를 주고 다음 FIFO 페이지로 넘어갑니다. 한 번 기회를 받게 되면 참조 비트는 해제되고 도착 시간이 현재 시각으로 재설정됩니다.

이에 따라 그 페이지는 다른 모든 페이지가 교체될 때 까지(또는 기회를 받을 때까지) 교체되지 않습니다.

따라서, 참조 비트가 계속 설정되어 있을 정도로 자주 사용되는 페이지는 전혀 교체되지 않을 것입니다.

2차 기회(때때로 클록으로 언급된) 알고리즘(second change algorithm)을 구현하는 하나의 방법은 순환 큐(circular queue)를 이용하는 것입니다.

4.5.3 개선된 2차 기회 알고리즘

2차 기회 알고리즘의 방식에서 사용하는 비트로 참조 비트와 변경 비트를 같이 사용하면 더 개선할 수 있습니다.

이 두 개의 비트를 조합하여 사용하면 다음 네 가지의 등급이 가능합니다.

1. (0, 0) 최근에 사용되지도 변경되지도 않은 경우 - 교체하기 가장 좋은 페이지
2. (0, 1) 최근에 사용되지는 않았지만 변경은 된 경우 - 이 페이지는 뺏어 오려면 디스크에 내용을 기록해야 하므로 교체에 적당하지 않습니다.
3. (1, 0) 최근에 사용은 되었으나 변경은 되지 않는 경우 - 이 페이지는 곧 다시 사용될 가능성이 높음.
4. (1, 1) 최근에 사용도 되었고 변경도 된 경우 - 아마 곧 다시 사용될 것이며 뺏으려면 역시 디스크에 그 내용을 먼저 기록해야 합니다.

페이지 교체가 필요할 때 알고리즘은 페이지가 어떤 등급에 속하는지 확인할 것입니다.

그 중 가장 낮은 등급을 가지면서 처음 만난 페이지를 교체합니다. 교체될 페이지를 찾기까지 여러 번 순환 큐를 검사할 수도 있다는 점에 주의해야 합니다.

이 알고리즘과 단순한 클록 알고리즘의 가장 큰 차이는 I/O 횟루를 줄이기 위해 페이지에 대해 우선순위를 준다는 것입니다.

4.6 계수-기반 페이지 교체

페이지 교체를 위해 사용되는 많은 다른 알고리즘이 있습니다.

현재까지 FIFO, 최적 교체(이상론), LRU, LRU 근사 알고리즘(시프트 레지스터 혹은 참조 비트, 변경 비트)가 있었습니다.

각 페이지를 참조할 때마다 계수를 하여 다음과 같은 두 가지 기법을 만들 수도 있습니다.

• LFU(least frequently used) 알고리즘: 이 알고리즘은 "참조 횟수"가 가장 낮은 페이지를 교체하는 방법입니다. 이러한 선택의 이유는 활발하게 사용되는 페이지는 큰 참조 횟수를 갖게 될 것이라는 점입니다.
  • 해당 방식의 가장 큰 오류는 초기 단계에서 집중적으로 많이 사용되다가 이후에 참조를 하지 않는 점을 고려하지 않았다는 것입니다.
  • 이를 위해서 해결하기 위해 일정한 시간마다 참조 횟수를 감소시킬 수 있습니다.
• MFU(most frequently used) 알고리즘: 이 알고리즘은 가장 참조 횟수를 가진 페이지가 가장 최근 참조된 것이고 앞으로 사용될 것이라는 판단에 근거한 것입니다.

이 두 알고리즘은 일반적으로 잘 쓰이지는 않습니다. 왜냐하면 이들 알고리즘을 구현하는 데는 상당히 비용이 많이 들고 OPT 페이지 교체 정책을 제대로 근사하지 못하기 때문입니다.

4.7 페이지-버퍼링 알고리즘

페이지 교체 알고리즘과 병행하여 여러 가지 버퍼링 기법이 사용될 수 있습니다.

한 가지 기법은 시스템들이 가용 프레임 여러 개를 풀(poll)로 가지고 있다가, 페이지 폴트가 발생하면 예전과 마찬가지로 교체될 페이지를 찾지만, 교체될 페이지의 내용을 기록하기 전에 가용 프레임에 새로운 페이지를 먼저 읽어 들이는 방법입니다.

이것이 무슨 말인가 하면,

이전에 가용 프레임 리스트에 대해서 언급을 했었고, 해당 리스트에 요소가 없을 때 "가용 가능한 프레임이 없음"으로 간주하여 페이지 교체 정책을 실시한다고 했습니다.

하지만, 가용 프레임 리스트를 항상 유지하면 어떻게 될까요? 즉, 프레임 요청이 들어왔을 때 빠르게 할당을 해줄 수 있을 것입니다.

그리고 이를 항상 유지하기 위해서 특정 하한선을 걸어두는 것입니다.

이 방법은 교체될 페이지가 복사하는 작업을 기다리지 않고 프로세스가 가능한 빨리 시작할 수 있도록 해줍니다.

이후에 교체될 페이지가 다 복사하고 나면 그 프레임이 가용 프레임 풀에 추가됩니다.

이 개념의 확장으로 변경된(modified) 페이지 리스트를 유지하는 방법이 있습니다.

페이징 장치가 아무런 일도 없게 되면 그때마다 변경된 페이지들을 차례로 보조저장장치에 쓴 후에, 페이지 변경 비트를 0으로 되돌려 놓습니다(reset).

이렇게 하면 나중에 페이지가 실제로 교체될 때 변경되지 않은(clean) 상태여서 쓰기 작업이 불필요할 가능성이 높아집니다.

추가적인 방법으로 가용 프레임 풀을 유지하면서 그 풀 속 각 프레임의 원래 임자 페이지가 누구였는지 메타데이터로 기록해두는 방법을 제안하고 있습니다.

4.8 응용(applications)과 페이지 교체

마지막으로 이러한 동작 방식 즉, 가상 메모리를 사용하지 않는 경우를 알아봅시다.

대표적인 예로 나름의 메모리 관리와 I/O 버퍼링을 수행하고 있는 데이터베이스입니다.

이러한 응용들은 범용적인 알고리즘을 구현해야 하는 운영체제와 비교하여 자신의 메모리와 저장장치 사용 방식을 더 잘 이해하고 있습니다.

또한 운영체제가 I/O를 버퍼링하고 응용 프로그램도 버퍼링한다면 하나의 I/O에 대해 메모리를 두 배로 사용하게 됩니다.

다른 예로, 데이터웨어하우스도 언급됩니다.

이러한 문제들 때문에, 몇몇 운영체제는 특별한 프로그램들에는 보조저장장치 파티션을 파일 시스템 구조가 아닌 단순한 논리적인 블록들의 순차적인 배열로써 사용할 수 있게 해주는 기능을 갖추고 있습니다.

이 배열은 종종 raw disk라고 블리며 여기에 대한 I/O는 raw I/O라는 용어을 사용합니다.

Raw I/O는 파일 시스템의 요구 페이징, 파일 잠금(locking), 선반입, 공간 할당, 디렉터리, 파일 이름 등의 모든 파일 시스템 서비스를 거치지 않습니다.

물론, 대부분의 응용은 정상적인 파일 시스템 서비스를 사용하는 것이 더 좋은 성능으로 동작합니다.

5. 프레임의 할당

여기서는 할당 문제에 대해서 다뤄봅시다.

각 프로세스에 몇 개의 프레임을 할당해줘야 하는 것일까요?

128개의 프레임을 가지는 간단한 시스템을 고려해 봅시다. 여기서 운영체제가 35개를 차지하고 나면 나머지 93프레임이 사용자 프로세스를 위해 남게 됩니다.

순수 요구 페이징 기법에서는 처음에 93프레임 모두가 가용 프레임 리스트(free frame list)에 들어가게 됩니다. 사용자 프로세스들이 실행을 시작하면 일련의 페이지 폴트를 발생시키게 됩니다.

가용 페이지가 전부 없어지면, 페이지 교체가 일어나게 되고 프로세스가 종료되면 프레임들은 가용 프레임 리스트로 반환될 것입니다.

앞서 언급했지만 가용 프레임 풀을 위해서 운영체제는 가용 프레임 리스트가 떨어지기 전에 "페이지 교체" 작업을 수행하며, 예비로 3개는 남겨두고자 합니다.

5.1 최소로 할당해야 할 프레임 수

최소한의 프레임은 할당해야만 하는 한 가지 이유는 성능과 관계됩니다.

각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 폴트율은 증가하고 프로세스 실행은 늦어지게 됩니다.

또한, 명령어 수행이 완료되기 전에 페이지 폴트가 발생하면 그 명령어를 재실행해야 합니다.

따라서 하나의 명령어가 참조되는 모든 페이지는 동시에 메모리에 올라와 있어야 그 명령어의 수행이 끝날 수가 있게 됩니다.

최소 프레임 수는 "컴퓨터 아키텍처"에 의해 정의됩니다.

예를 들어, 주어진 아키텍처에 대한 이동 명령이 일부 주소지정 모드에서 하나 이상의 워드를 포함하는 경우, 명령 자체는 두 프레임에 걸쳐있을 수 있습니다.

또한 두 피연산자가 각각 간접 참조일 수 있는 경우에는 총 6개 프레임이 필요합니다.

다른 예로서, Intel 32 및 64 비트 아키텍처의 이동 명령은 레지스터 사이에서 그리고 레지스터와 메모리 사이에서만 데이터를 이동할 수 있습니다.

메모리에서 메모리로 직접 이동을 허용하지 않으므로 프로세스에 필요한 최소 프레임 수를 제한합니다.

프로세스당 최소 프레임 수는 "아키텍처"에 의해 정의되는 반면, 최대 수는 "사용 가능한 물리 메모리 양"에 의해 정의됩니다.

5.2 할당 알고리즘

가장 간단한 방법은 모두에 같은 수의 프레임을 할당해주는 것입니다.

만약, n개의 프로세스가 가용 가능한 프레임 m개를 사용할 수 있다면 $m / n$만큼 사용할 수 있을 것입니다.

이러한 방법을 균등 할당(equal allocation)이라고 합니다.

또 다른 대안으로는 프로세스마다 그 크기가 다른다는 점을 고려한 것입니다.

즉, 프로세스의 크기의 합을 전부 합친 뒤에 합과 자신의 크기의 비율만큼 프레임을 할당받는 방식입니다.

이러한 방법은 비례 할당(proportional allocation)이라고 합니다.

이 두 방식은 모두 높은 우선순위의 프로세스와 낮은 우선순위의 프로세스를 동등하게 취급하고 있습니다.

비례 할당방식에서 우선순위의 조합을 사용하여 결정할 수도 있습니다.

5.3 전역 대 지역 할당

프레임을 할당하는 방법에는 또 다른 중요한 요소가 있는데, 프레임이 사용되는 범위입니다.

다수의 프로세스가 프레임 할당을 위해 경쟁하는 환경에서 페이지 교체 알고리즘은 크게 두 가지 범주로 나뉩니다.

• 전역 교체(global replacement)
• 지역 교체(local replacement)

전역 교체는 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 경우입니다.

지역 교체는 각 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 선택할 수 있는 경우입니다.

전역 교체 방법을 사용시 프로세스들이 가지고 있던 프레임 수가 바뀔 수 있지만, 지역 교체 방법을 사용시 프로세스들 가지고 있는 프레임 수에는 변경이 없습니다.

전역 교체 알고리즘의 한 가지 문제점은 프로세스의 메모리에 있는 페이지 집합이 해당 프로세스의 페이징 동작뿐만 아니라 다른 프로세스의 페이징 동작에도 영향을 받는다는 것입니다.

따라서, 동일한 프로세스도 그때그때 외부적 환경에 따라서 전혀 다르게 실행될 수 있습니다.

지역 교체 알고리즘에서는 이러한 현상이 발생하지 않지만, 잘 안쓰는 페이지 프레임이 있더라도 그것을 그대로 낭비할 수 있습니다.

일반적으로 전역 교체가 지역 교체 알고리즘보다 더 좋은 시스템 성능을 나타내며, 따라서 보다 더 많이 사용되는 방법입니다.

이제 전역 페이지 교체 정책을 구현하는 데 사용할 수 있는 전략 중 하나에 초점을 맞춥시다.

이 방식의 핵심적인 부분은 아래 두가지 입니다.

• 최대 임계값
• 최소 임계값

해당 전략은 특정 임계값 아래로 떨어지면 페이지 교체가 일어납니다.

이 전략은 새로운 쵸엉을 충족시키기에 충분한 여유 메모리가 항상 남아있도록 보장하려고 노력합니다.

전략의 목적은 가용 메모리 양을 최소 임계값 이상으로 유지하는 것입니다.

이 임계값 아래로 떨어지면 시스템의 모든 프로세스(일반적으로 커널 제외)에서 페이지를 회수하기 시작하는 커널 루틴이 촉발됩니다. 이러한 커널 루틴은 종종 리퍼(reaper)로 알려져 있습니다.

사용 가능한 메모리 양이 최대 임계값에 도달하면 리퍼 루틴이 일시 중지되며, 사용 가능한 메모리가 다시 최소 임계값 아래로 떨어지면 다시 시작됩니다.

커널 리퍼 루틴은 임의의 페이지 교체 알고리즘을 채택할 수 있지만, 일반적으로 LRU 근사 형태의 알고리즘을 사용합니다.

그러나 이 방식을 이용해서 최소 임계값 이상을 유지할 수 없는 경우 운영체제는 아마도 2차 기회 알고리즘을 중단하고 순수한 FIFO를 사용할 것입니다.

더 극단적인 또 다른 예는 Linux에서 발생합니다.

사용 가능한 메모리 양이 "매우" 낮은 수준으로 떨어지면 메모리-부족(out-of-memory, OOM) 킬러라고 하는 루틴이 종료할 프로세스를 선택하여 메모리를 회수합니다.

각 프로세스에는 OOM 점수라고 하는 것이 있으며, 점수가 높을수록 OOM 킬러 루틴에 의해 프로세스가 종료된 가능성이 커집니다.

5.4 비균등 메모리 접근

여러 개의 CPU를 가진 비균등 메모리 접근(NUMA) 에서는 가상메모리의 가정 중 하나인 모든 메인 메모리는 동등하게 접근된다는 가정이 성립하지 않습니다.

시스템의 CPU와 메모리의 연결 방식에 따라 성능의 차이를 불러올 것이고, 이러한 시스템은 각각 자신의 로컬 메모리가 있는 여러 CPU로 구성됩니다.

자신의 로컬 메모리는 빠르게 접근하지만 다른 로컬 메모리 접근은 이에 비해 다소 느릴 것입니다.

어느 페이지를 어느 프레임에 할당하는냐 하는 정책이 NUMA의 성능에 커다란 영향을 미칩니다.

여기서 목표는 프로세스가 실행 중인 CPU에 "가능한 가장 가까운" 메모리 프레임이 할당되도록 하는 것입니다. 즉, 최소 지연시간을 가진 프레임을 할당되면 됩니다.

NUMA를 고려하면 스케줄러는 프로세스가 "마지막으로 실행된" CPU를 추적해야만 합니다.

스케줄러는 각 프로세스를 직전에 실행된 CPU에 스케줄하고 가상 메모리 시스템은 스케줄 된 CPU와 가까운 프레임을 할당한다면, 그 결과 캐시 적중률이 높아지고 메모리 접근 시간이 감소하게 될 것입니다.

Linux에는 각 NUMA 노드에 대해 별도의 가용 프레임 리스트가 있습니다.

Solaris는 커널에서 **lgroups("locality groups")""를 만들어 유사하게 문제를 해결합니다.

각 lgroup은 CPU와 메모리를 모으고 해당 그룹의 각 CPU는 정의된 지연시간 간격 내에 그룹의 모든 메모리 액세스 할 수 있습니다.

⚡️ 주요 및 사소한 페이지 폴트 ⚡️

운영체제는 일반적으로 페이지 폴트를 두 가지 유형으로 구분합니다.

• 주요 페이지 폴트: 페이지가 참조되고 페이지가 메모리에 없을 때 발생합니다.
• 사소한 페이지 폴트: 프로세스에 페이지에 대한 논리적 매핑이 없지만 해당 페이지가 메모리에 있는 경우 발생합니다.

중대한 페이지 폴트를 서비스하려면 백업 저장장치에서 가용 프레임으로 원하는 페이지를 읽고 페이지 테이블을 갱신해야 합니다. 요구 페이징은 일반적으로 초기에 높은 비율의 주요 페이지 폴트를 발생시킵니다.

사소한 폴트는 두 가지 이유 중 하나 때문에 발생할 수 있습니다.

1. 프로세스는 메모리에 있는 "공유 라이브러리"를 참조할 수 있지만 프로세스는 페이지 테이블에 이에 대한 매핑이 없는 경우
2. 프로세스에서 페이지를 회수하여 가용 프레임 리스트에 넣고 페이지가 아직 0으로 채워지지 않은 채 다른 프로세스에 할당될 때 발생

1번의 경우 페이지 테이블만 갱신하면 됩니다.

2번과 같은 종류의 페이지 폴트가 발생하면 프레임이 가용 프레임 리스트에서 제거되고 프로세스에 다시 할당됩니다.

사소한 폴트는 주요 페이지 폴트를 해결하는 것보다 시간이 덜 걸립니다.

6. 스래싱

만약 프로세스에 "충분한" 프레임이 없는 경우, 즉 작업 집합의 페이지를 지원하는 데 필요한 최소 프레임도 없는 경우 어떤 일이 발생할까?

그 프로세스는 곧바로 페이지 폴트를 일으킬 것입니다. 반복해서 페이지 폴트가 발생하며 교체된 페이지는 다시 얼마 지나지 않아 읽어올 필요가 생깁니다.

이러한 과도한 페이징 작업을 스래싱(thrashing)이라고 부릅니다.

6.1 스래싱의 원인

왜 스레싱이 발생하는 것일까?

현재 CPU 이용률이 너무 낮아서 새로운 프로세스를 추가하여 다중 프로그램밍의 정도를 높이려고 한다고 가정해 봅시다.

이때 전역 페이지 교체 알고리즘을 사용하여 다른 프로세스로부터 프레임을 가져오게 될 것입니다.

그런데, 교체된 페이지들이 해당 프로세스에서 필요로 하는 것들이었다면 그 프로세스 역시 페이지 폴트를 발생시킬 것입니다.

빈번한 페이징이 발생할 것이고 이것은 CPU 이용률을 저하시키게 될 것입니다.

여기서 다중 프로그래밍 정도를 높이기 위해 또 프로세스를 추가한다면 결국 위의 매커니즘이 반복될 것입니다.

이러한 매커니즘에 의해 스래싱이 발생하게 됩니다.

위의 그림에서도 볼 수 있듯이 처음에는 다중 프로그래밍 정도가 높아짐에 따라 CPU 이용률이 계속해서 증가하지만, 다중 프로그래밍 정도가 어느 정도를 넘어서면 CPU 이용률이 급격하게 낮아지는 것을 확인할 수 있습니다.

지역 교체 알고리즘을 사용하면 스래싱의 영향을 제한할 수 있지만 문제가 완전히 해결되는 것은 아닙니다.

프로세스가 스래싱하는 경우 대부분 페이징 장치의 큐에서 기다리게 됩니다.

페이징 장치의 평균 대기열이 길어지기 때문에 페이지 폴트의 평균 서비스 시간이 늘어나게 되고, 스레싱되지 않은 프로세스에서도 실질 접근 시간이 증가하게 됩니다.

스레싱 현상을 방지하기 위해서는 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 합니다.

한 가지 전략은 프로세스 실행의 지역성 모델(locality model)을 이용하는 것입니다.

지역성 모델이란 프로세스가 실행될 때에는 "항상 어떤 특정한 지역에서만" 메모리를 집중적으로 참조함을 말합니다.

지역(locality)이란, 집중적으로 함께 참조되는 페이지들의 집합을 의미합니다.

실행중인 프로그램은 여러 개의 지역으로 구성되어 있고, 이 지역들은 서로 겹쳐질 수도 있습니다. 지역은 프로그램 구조나 그 자료구조에 의해 정의된다고 볼 수 있습니다.

지역 모델은 모든 프로그램이 이러한 메모리 참조 구조를 가질 것이라고 얘기하며, 캐싱 기법의 기본 원리이기도 합니다.

어떤 프로세스에 현재 지역성을 포함하기에 충분한 프레임을 제공해 준다고 하면, 현재 지역의 모든 페이지가 메모리로 올라갈 때까지만 페이지 폴트가 발생하고, 이후 발생하지 않을 것입니다.

하지만, 만약 이보다 더 적은 프레임을 할당하게 되면, 그 프로세스는 접근해야 하는 모든 페이지를 메모리에 유지할 수 없기 때문에 지속해서 페이지 폴트를 발생시키게 됩니다. 즉, 스레싱이 일어납니다.

6.2 작업 집합 모델

작업 집합 모델은 지역성을 토대로 하고 있습니다.

이 모델은 개념적으로 창(작업 집합 window)을 가지고 있는 것과 같습니다.

기본 아이디어는 최근 𝚫만큼의 페이지 참조를 관찰하겠다는 것입니다.

한 프로세스가 최근 𝚫번 페이지를 참조했다면 그 안에 들어있는 서로 다른 페이지들의 집합을 작업 집합이라고 부릅니다.

작업 집합의 정확도는 𝚫의 선택에 따라 좌우됩니다.

만약에 𝚫값이 너무 작으면 전체 지역을 포함하지 못할 것이고, 𝚫값이 너무 크면 여러 지역성을 과도하게 수용할 것입니다.

즉, 이 모델의 가장 중요한 요소는 이 집합의 크기입니다.

일단 𝚫 값을 선택하고 나면, 운영체제는 각 프로세스의 작업 집하을 감시하면서 각 프로세스에 작업 집합 크기에 맞는 충분한 프레임을 할당합니다.

이렇게 할당하고도 여분의 놀고 있는 프레임이 있다면 또 새로운 프로세스를 시작시킬 수 있습니다.

물론, 프로세스가 너무 많아져서 할당할 수 있는 임계값을 넘어섰다면 프로세스를 하나 선택해서 해당 프로세스의 프레임들을 배분할 수 있을 것입니다.

이러한 방법은 가능한 다중 프로그래밍의 정도를 유지하면서도 스래싱을 방지할 수 있게 해줍니다.

따라서 CPU의 이용률도 최적화됩니다.

이 모델의 어려운 점은 작업 집합을 추겆하는 일입니다.

작업 집합은 메모리 참조마다 한쪽에서는 새로운 페이지들이 추가되고 다른 쪽에서는 가장 오래된 참조부터 제외됩니다. 작업 집합 창 내의 어디에서라도 참조되는 페이지는 작업 집합에 속합니다.

6.3 페이지 폴트 처리

작업 집합 모델은 아주 성공적이며, 작업 집합에 대해 안다는 것은 선페이징(prepaging) 시에 유용하지만 스레싱을 조절하는 방법은 아무래도 좀 어색합니다.

페이지 폴트 빈도(PFF) 방식은 보다 더 직접적으로 스래싱을 조절합니다.

페이지 폴트율의 상한 하한을 정해 놓고, 만약 페이지 폴트율이 상한을 넘으면 그 프로레스에 프레임을 더 할당해 주고, 하한보다 낮아지면 그 프로세스의 프레임 수를 줄입니다.

이렇게 함으로써 직접적으로 부재율을 관찰하고 조절함으로써 스래싱을 방지할 수 있습니다.

7. 메모리 압축

페이징의 대안은 메모리 압축입니다.

메모리 압축은 시스템의 물리 메모리 사용을 최적화하는 기법 중 하나로, 메모리에 저장된 데이터를 압축하여 실제로 사용하는 메모리 공간을 줄이는 방법입니다.

메모리 압축의 기본 원리

메모리 압축은 메모리 내의 데이터를 압축하여 보다 적은 수의 페이지나 프레임을 사용해 데이터를 저장합니다. 이 과정에서 압축 알고리즘을 사용하여 데이터의 크기를 줄이며, 접근 시에는 압축을 해제하여 원래의 데이터를 복원합니다.

메모리 압축은 운영 체제의 메모리 관리자에 의해 투명하게 수행되며, 사용자나 응용 프로그램은 이 과정을 인지하지 못합니다.

메모리 압축의 장점

• 메모리 효율성 향상: 메모리 압축을 사용하면 물리 메모리의 효율적인 사용이 가능해져, 시스템의 메모리 문제를 완화할 수 있습니다.
• 성능 개선: 메모리 압축을 통해 더 많은 데이터를 메모리에 유지할 수 있게 되어, 디스크 I/O 작업을 줄이고 시스템의 전반적인 성능을 향상시킬 수 있습니다.

메모리 압축의 단점

• CPU 오버헤드: 데이터 압축 및 해제 과정에서 추가적인 CPU 자원이 필요하며, 이는 CPU 사용률을 증가시킬 수 있습니다.
• 압축 효율의 변동성: 압축 알고리즘의 효율성은 저장되는 데이터의 종류에 따라 크게 달라질 수 있습니다. 일부 데이터는 잘 압축되지 않을 수 있으며, 이 경우 메모리 압축의 이점이 줄어들 수 있습니다.

간단하게 예시로 보자면 다음과 같은 것입니다.

프레임 1: 데이터 A (4KB)
프레임 2: 데이터 B (4KB)
프레임 3: 데이터 C (4KB)
프레임 4: 데이터 D (4KB)

이렇게 할당하던 것을 압축 알고리즘을 사용하면 아래와 같이 할당해줄 수 있습니다.

프레임 1: 데이터 A + 데이터 B (압축됨)
프레임 2: 데이터 C + 데이터 D (압축됨)
프레임 3: 가용
프레임 4: 가용

앞서 언급했듯이 모바일 시스템은 일반적으로 표준 스와핑 또는 페이지 스와핑을 지원하지 않습니다.

따라서 메모리 압축은 Android 및 iOS를 포함한 대부분의 모바일 운영체제의 메모리 관리 전략의 핵심 부분입니다. 또한 Windows 10과 macOS는 모두 메모리 압축을 지원합니다.

macOS는 먼저 운영체제 버전 10.9에서 메모리 압축을 지원하여 사용 가능한 메모리가 부족할 때 LRU 페이지를 압축한 다음 문제가 해결되지 않으면 페이징을 합니다.

실제로 macOS에서 행한 성능 테스트에 따르면 메모리 압축이 SSD 보조저장장치를 사용한 페이징보다도 빠르다는 것을 알 수 있습니다.

8. 커널 메모리의 할당

커널 메모리는 보통 사용자 모드 프로세스에 할당해 주기 위한 페이지 리스트와는 별도의 메모리 풀에서 할당받습니다. 이렇게 하는 이유는 다음과 같습니다.

1. 커널은 다양한 크기의 자료구조를 위해 메모리를 할당받습니다.
   a. 이 자료구조들은 페이지 크기보다 작은 크기를 갖기도 합니다. 그 때문에 커널은 메모리를 조심스럽게 사용하여야 하고 단편화에 의한 낭비를 최소화하고자 합니다.
   b. 많은 운영체제가 커널 코드나 데이터를 페이징하지 않기 때문에 특히 더 중요합니다.
2. 사용자 모드 프로세스에 할당되는 페이지들은 물리 메모리상에서 굳이 연속된 것일 필요는 없습니다. 그러나 가상 메모리 인터페이스를 통하지 않고 물리 메모리에 직접 접근하는 특정 하드웨어 장치는 물리적으로 연속적인 메모리가 있어야 하는 경우가 있습니다.

8.1 버디 시스템

버디 시스템은 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로부터 메모리를 할당합니다.

메모리는 이 세그먼트로부터 2의 거듭제곱 할당기에 의해 2의 거듭제곱 단위로 할당됩니다(4KB, 8KB, 16KB 등등).

간단한 예로, 메모리 세그먼트의 크기가 초기에 256KB라고 가정하고 이것을 32KB 크기의 버디까지 나눠가보자.

버디 시스템의 이점 중 하나는 합병(coalescing)이라고 부르는 과정을 통해 서로 인접한 버디들이 손쉽게 하나의 큰 세그먼트로 합쳐질 수 있다는 점이빈다.

버디 시스템의 분명한 단점은 가장 가까운 2의 거듭제곱으로의 올림이 할당된 세그먼트 내의 내부 단편화를 가져온다는 것입니다.

8.2 슬랩 할당

슬랩(slab)은 하나 또는 그 이상의 연속된 페이지들로 구성됩니다.

캐시(cache)는 하나 혹은 그 이상의 슬랩들로 구성됩니다.

각 커널 자료구조마다 하나의 캐시가 존재합니다.

예를 들어 프로세스 디스크립터(descriptor)를 위한 캐시, 파일 객체를 위한 캐시, 세마포어를 위한 캐시 등이 존재합니다.

각 캐시는 커널 자료구조의 각 인스턴스에 해당하는 객체들로 채워져 있습니다.

슬랩 할당 알고리즘은 커널 객체를 저장하기 위해 캐시를 사용합니다. 캐시가 생성되면 처음에 free라고 표시된 몇 개의 객체들이 캐시에 할당됩니다.

캐시 내의 객체의 수는 "해당 슬랩의 크기"에 좌우됩니다.

Linux에서 슬랩은 다음과 같은 세 가지 상태 중 한 상태에 있게 됩니다.

1. Full. 슬랩 내의 모든 객체가 used로 표시됨
2. Empty. 슬랩 내의 모든 객체가 free로 표시됨
3. Partial. Used, free 객체가 섞여 있음

슬랩 할당기는 먼저 "partial 슬랩의 free 객체"를 이용해 요청을 처리하려고 시도합니다.

Partial 슬랩이 없다면 empty 슬랩으로부터 free 객체를 할당합니다.

Empty 슬랩도 없는 경우 새로운 슬랩이 연속된 물리 메모리에서 할당되어 캐시에 주어집니다. 객체는 슬랩에서 할당됩니다.

슬랩 할당기는 두 가지 주요 장점이 있습니다.

1. 단편화에 의해 낭비되는 메모리가 없다.
   a. 각 커널 자료구조가 그에 해당하는 캐시를 가지고 각 캐시는 그에 의해 처리되는 객체의 크기로 나누어진 덩어리들로 구성되므로 단편화는 문제가 되지 않는다.
   b. 즉, 커널이 메모리 할당을 요구할 때마다 슬랩 할당기는 정확히 필요한 만큼의 메모리만을 할당합니다.
2. 메모리 요청이 빠르게 처리됩니다. 따라서 슬랩 할당기는 할당과 해제가 빈번한 자료 구조 객체를 관리하는 데 특히 효율적이다.
   a. 메모리 할당과 해제는 상당히 소요되는 작업일 수 있다. 그러나 객체들이 미리 생성되어 있고 캐시에서 쉽게 할당할 수 있다.
   b. 더 나아가 커널이 특정 객체를 다 사용하고 해제하면 free로 표시된 상태로 캐시로 반환되어 다음 요구 시 즉시 할당 가능합니다.

9. 기타 고려 사항

페이징 시스템이 효과적으로 실행되기 위해서는 페이지 교체 알고리즘과 할당 정책이의 선택이 매우 중요하지만 그 외에도 고려해야 할 사항들이 많이 있습니다.

9.1 프리페이징

순수 요구 페이징의 명백한 특성은 프로세스가 시작될 때 많은 수의 페이지 폴트가 발생한다는 것입니다. 이 상황은 초기 지역성을 메모리로 가져오려고 시도한 결과입니다.

프리 페이징은 이러한 높은 수준의 초기 페이징을 방지하려는 시도입니다.

이 전략은 필요한 페이지의 일부 또는 전부를 한 번에 메모리에 가져오는 것입니다.

예를 들어 작업 집합을 사용하는 시스템에서는 프로세스마다 작업 집합에 속한 페이지 리스트들을 가지고 있습니다.

어떤 프로세스를 중단시켜야 한다면 (빈 페이지가 모자라서) 그 프로세스의 작업 집합을 기억하여 놓습니다. 추후 그 프로세스가 실행을 다시 시작할 때에는 그 프로세스가 재시작하기 전에 작업 집합을 모두 메모리에 올려 놓습니다.

물론 프리페이징으로 가져온 페이지가 사용되지 않을 수 있기 때문에 페이지 폴트를 줄인 비용이 불필요한 페이지를 프리페이징한 비용보다 큰지 비교해봐야 합니다.

어떤 페이지를 가져와야 하는지 명확하지 않기 때문에 실행 프로그램을 프리페이징하는 것은 어려울 수 있습니다. 파일은 보통 순차적으로 액세스 되기 때문에 파일 프리페이징은 더 확실합니다.

9.2 페이지 크기

페이지의 크기를 결정짓는 요소는 다음과 같은 것들이 있습니다.

1. 페이지 테이블 크기, 메모리 사용 효율
2. 페이지를 읽거나 쓰는 데 필요한 시간
3. 지역성
4. 페이지 폴트 횟수

1번의 경우 프로세스마다 각자의 페이지 테이블을 유지하기 때문에, 큰 페이지를 사용하는 것이 페이지 테이블 크기를 낮출 수 있습니다.

반면에 메모리 사용 효율 측면에서는 내부적 단편화를 최소화하기 위하여 작은 페이지의 크기가 더 좋습니다.

2번의 경우 작은 페이지를 사용할 경우 더 많은 I/O를 요구하게 되므로 시간이 더 오래 걸릴 수 있습니다. 따라서 시간적인 측면을 고려한다면 더 큰 페이지 크기가 효율적입니다.

3번의 경우 작은 페이지 크기를 갖는 경우 지역성이 향상되어 전체 I/O가 더 줄어들게 됩니다. 작은 페이지 시스템에서는 실제로 필요한 정보만을 선별하여 메모리로 가져오게 되어 정밀도(resolution)가 좋아진다고 볼 수 있습니다.

큰 페이지 시스템에서는 꼭 필요한 내용뿐 아니라 우연히 같은 페이지에 속하게 된 모든 정보도 함께 반입되므로 메모리 내용이 알차지 못하게 됩니다.

마지막으로 4번의 경우에는 페이지의 크기가 작다면 필요한 바이트 크기만큼 페이지 폴트가 발생하게 되므로 페이지 폴트 횟수를 줄이기 위해서는 큰 페이지가 좋습니다.

현재는 기본적으로 4KB를 기본 크기로 사용하고, 크기가 더 커지는 추세입니다.

이후, TLB Reach와 역 페이지 테이블, lock 그리고 운영체제의 예에 대해서 설명이 나오지만 생략하겠습니다.

참고한 자료

• 운영체제[공룡책]