OSTEP Chapter 21 Homework

Problem 1

변환을 하기 전에 매개변수가 주어졌을 때 선형 페이지 테이블이 크기를 변경하는 방법을 연구하기 위해 시뮬레이터를 사용해 보자. 매개변수가 바뀜에 따라 선형 페이지 테이블의 크기를 계산하시오. 추천하는 입력은 아래와 같다. -v 플래그를 사용하여 얼마나 많은 페이지 테이블 항목이 채워지는지 알 수 있다.
먼저, 주소 공간이 커짐에 따라 선형 페이지 테이블 크기의 변화를 이해하기 위하여 :

paging−linear−translate.py −P 1K −a 1m −p 512m −v −n 0
paging−linear−translate.py −P 1K −a 2m −p 512m −v −n 0
paging−linear−translate.py −P 1K −a 4m −p 512m −v −n 0

그런 다음 페이지 크기가 커짐에 따라 선형 페이지 테이블 크기의 변화를 이해하기 위하여 :

paging−linear−translate.py −P 1k −a 1m −p 512m −v −n 0
paging−linear−translate.py −P 2k −a 1m −p 512m −v −n 0
paging−linear−translate.py −P 4k −a 1m −p 512m −v −n 0

어느 것 하나라도 실행하기 전에 예상 경향에 대해 생각해 보라. 주소 공간이 커지면 페이지 테이블 크기는 어떻게 변하는가? 페이지 크기가 커지는 경우는? 일반적으로 큰 페이지 크기를 사용하면 안 되는 이유는 무엇인가?

페이지 크기가 일정할 때 주소 공간이 커지면 할당되는 페이지의 개수가 늘어나므로 페이지 테이블의 크기도 함께 커진다. 주소 공간의 크기가 일정할 때 페이지 크기가 커지면 할당되는 페이지의 개수가 줄어드므로 페이지 테이블의 크기도 함께 작아진다. 하지만 페이지의 크기를 크게 설정할수록 내부 단편화(Internal Fragmentation) 문제가 심각해진다. 그러므로 일반적으로 페이지 크기는 너무 크게 사용하면 안 된다.

Problem 2

자 이제 변환을 해 보자. 몇 가지 작은 예부터 시작해서 -u 플래그를 사용하여 주소 공간에 할당된 페이지 개수를 변경해 보라. 예를 들면 :

paging−linear−translate.py −P 1k −a 16k −p 32K −v −u 0
paging−linear−translate.py −P 1k −a 16k −p 32K −v −u 25
paging−linear−translate.py −P 1k −a 16k −p 32K −v −u 50
paging−linear−translate.py −P 1k −a 16k −p 32K −v −u 75
paging−linear−translate.py −P 1k −a 16k −p 32K −v −u 100

각 주소 공간에 할당된 페이지의 비율을 높인다면 어떤 일이 벌어지는가?

각 주소 공간에 할당된 페이지의 비율을 높일수록 임의로 생성된 주소가 유효할 확률이 높아진다. -u 옵션에 전달하는 비율이 즉 주소 공간 내 임의의 주소가 유효할 확률이다.

Problem 3

그러면 몇 가지 무작위 배정을 시도하자. 몇 가지 다른 (그리고 때로는 정말 어이 없는) 주소 공간 매개변수를 사용해 보라 :

paging−linear−translate.py −P 8 −a 32 −p 1024 −v −s 1
paging−linear−translate.py −P 8K −a 32k −p 1m −v −s 2
paging−linear−translate.py −P 1m −a 256m −p 512m −v −s 3

이 조합 중 어느 조합이 비현실적인가? 이유는?

가장 비현실적인 것은 3번 옵션으로, 물리적 메모리의 크기에 비해 페이지 크기가 너무 크다. 클 경우 앞서 서술한 바와 같이 심각한 내부 단편화 문제가 발생할 수 있다. 보통 현대 운영체제의 페이지 크기는 4KB 정도로 설정된다.

하지만 1번 옵션처럼 페이지 크기가 너무 작아도 페이지 테이블의 크기가 그만큼 커지므로 비현실적이다. 선형 페이지 테이블 방식에서 가상 주소 공간의 크기가 4GB, 페이지 크기가 8B, 페이지 테이블 엔트리 크기가 1B라고 가정하면 페이지 테이블 유지를 위해 약 5억 개의 엔트리가 필요하다.

하지만 모든 옵션이 공통적으로 물리 메모리 크기에 비해 가상 주소 공간의 크기가 너무 작기 때문에 메모리 가상화를 통해 물리 메모리 크기보다 더 큰 공간을 활용할 수 있다는 장점이 퇴색된다.

Problem 4

다른 문제를 시험해 보기 위해 프로그램을 사용하라. 프로그램이 더 이상 작동하지 않는 제약을 찾을 수 있는가? 예를 들어, 만약 주소 공간의 크기가 물리 메모리보다 크다면 어떤 일이 벌어지는가?

우선 물리적으로 동시에 물리 메모리보다 큰 메모리 공간이 사용될 수는 없다. 현대 운영체제에서 물리 메모리보다 큰 공간을 사용하는 것 같은 가상화를 제공할 수 있는 이유는 페이지 교체 메커니즘 덕분이다. Virtual Page는 Physical Frame과 일대일 대응되고 만약 모든 페이지가 대응되어 있는 상황에서 추가적인 페이지가 필요하다면 페이지 교체 알고리즘에 의해 희생할 페이지를 선정하고 해당 페이지와 스왑하게 된다.

그리고 가상 주소 공간의 크기보다 페이지 크기가 큰 경우도 문제가 된다. 가상 주소는 VPN, Offset의 두 부분으로 나뉘고 가상 주소 공간의 크기에 따라 가상 주소를 표현할 비트의 개수가 정해진다. 만약 가상 주소 공간의 크기가 4K라면 이를 표현하기 위해 12비트가 필요한데, 페이지 크기가 8K라면 페이지를 표현하기 위해서는 최소 13비트가 필요하게 된다. 이를 수학적 불능 상태라고 한다.

마지막으로 가상 주소 공간의 크기에 비해 페이지 크기가 매우 작을 경우에도 프로그램은 작동 불가능하다. 앞서 살펴본 것과 같이 선형 페이지 테이블 방식에서 가상 주소 공간에 할당되는 페이지들은 각각 페이지 테이블의 엔트리로 관리되어야 하는데 이러한 엔트리가 너무 많아져서 물리적 메모리의 크기를 초과하게 될 수 있다.