- 세그먼테이션의 문제점을 해결하기 위해 페이지를 사용하여
어떻게 메모리를 가상화할 수 있을까?
- 시간과 공간 오버헤드를 최소로 하면서
잘 동작하게 만들기 위해 어떤 방법을 사용할까?
페이징
- 프로세스의 주소 공간을 고정 크기의 단위로 나눈다. 이 각각의 고정 크기를
페이지(page)라고 부른다.
페이징의 장점
- 이전 방식(세그먼테이션)에 비해 가장 중요한 개선은
유연성이다. 주소 공간을 사용하는 방식과 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다.(예를 들어, 힙과 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 대한 가정을 하지 않아도 된다.
- 또 다른 장점은
단순함이다. 운영체제가 64바이트 주소 공간을 8페이지 물리 메모리에 배치하기를 원할 때, 운영체제는 비어 있는 네 개의 페이지만 찾으면 된다.
페이지 테이블(page table)
- 주소 공간의 각 가상페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스마다 페이지 테이블(page table)이라는 자료 구조를 유지한다.
- 페이지 테이블의 주요 역할은 주소 공간의 가상 페이지 주소 변환(address translation) 정보를 저장하는 것이다. 즉, 각 페이지가 저장된 물리 메모리의 위치가 어디인지 알려준다.
- 프로세스마다 페이지 테이블이 존재(전체 프로세스가 하나의 페이지 테이블을 가지는 구조, 역 페이지 테이블도 있음)해야 한다. 다른 프로세스를 실행해야 한다면 이 프로세스를 위한 다른 페이지 테이블이 필요하다. 새 프로세스의 가상 페이지는 다른 물리 페이지에 존재하기 때문이다.
가상 주소의 변환
- 작은 주소 공간(64바이트)을 가진 프로세스가 다음 메모리 접근을 수행한다고 가정하자. 한 페이지의 크기는 16바이트로 가정한다.
movl <virtual address, 21>, %eax
- 프로세스가 가상 주소를 생성하면 운영체제와 하드웨어가 의미있는 물리 주소로 변환한다.
- 가상 주소를
가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋 2개의 구성 요소로 분할한다.
- 가상 주소 “21”을 이진 형식으로 변환하면 “010101”을 얻는다. 따라서 가상 주소 “21”은 가상 페이지 “01”의 5번째 바이트이다.
- 이 가상 페이지 번호를 가지고 페이지 테이블의 인덱스로 사용하여 가상 페이지 1이 어느 물리 프레임에 저장되어 있는지 찾을 수 있다.
- 위의 페이지 테이블에서 물리 프레임 번호(physical frame number, PFN or PPN)은 7이다. 즉, VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있다.
페이지 테이블은 어디에 저장될까?
- 4KB 크기의 페이지를 갖는 32비트 주소 공간을 상상해보자. 이 가상 주소는 20비트 VPN과 12비트 오프셋으로 구성된다.
- 20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변환의 개수가 2의 20승이라는 것을 의미한다. 즉, 페이지 테이블 항목(page table entry, PTE)마다 4바이트가 필요하다고 가정하면, 각 페이지 테이블을 저장하기 위해서 4MB의 메모리가 필요하게 된다.
- 페이지 테이블이 매우 크기 때문에 현재 실행 중인 프로세스의 페이지 테이블을
MMU안에 저장하지 않을 것이다.
- 각 프로세스의 페이지 테이블은
메모리에 저장된다.
페이지 테이블에는 무엇이 있을까?
- 페이지 테이블의 가장 간단한 형태는
선형 페이지 테이블(linear page table)이다.
- 1. 운영체제는 원하는 물리 프레임 번호(PFN)을 찾기 위하여
- 2. 가상 페이지 번호(VPN)로 배열의 항목에 접근하고
- 3. 그 항목의 페이지 테이블 항목(PTE)을 검색한다.
1. Valid bit
- 특정 변환의 유효 여부를 나타낸다. 할당되지 않은 주소 공간을 표현하기 위해 반드시 필요하다.
- 예를 들어, 프로그램이 실행을 시작할 때 코드와 힙이 주소 공간의 한쪽에 있고, 반대쪽은 스택이 차지하고 있다. 그 사이의 모든 공간은 무효(invalid)로 표시하고, 프로세스가 그런 메모리를 접근하려고 하면 운영체제에 트랩을 발생시킨다.
2. Protection bit
- 페이지를 읽을 수 있는지, 쓸 수 있는지, 또는 실행될 수 있는지 표시한다.
3. Present bit
- 페이지가 물리 메모리에 있는지 혹은 디스크에 있는지(즉, 스왑아웃 되었는지) 표시한다.
4. Dirty bit
- 메모리에 반입된 후 페이지가 변경되었는지 여부를 표시한다.
5. Reference bit
- 페이지가 접근되었는지 추적하기 위해 사용된다. 이는 페이지를 교체할 때 매우 중요한 정보다.
페이징: 너무 느림
- 가상 주소 21에 접근한다고 했을 떄, 하드웨어는 현재 실행 중인 프로세스의 페이지 테이블의 위치를 알아야 한다. 당분간 하나의 페이지 테이블 베이스 레지스터(page table base register)가 페이지 테이블의 시작 주소(물리 주소)를 저장한다고 가정한다.
- 가상 주소에서 VPN을 추출한다.
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
- VPN_AMSK는 0x30(0b110000)으로 설정되어 전체 가상 주소에서 VPN비트만 골라낸다.
- SHIFT는 4로 설정되고(오프셋 비트 수), 올바른 정수 가상 페이지 번호를 형성하기 위해 VPN 비트를 오른쪽으로 이동시킨다. 가상 주소 21(010101)을 마스킹하면 (010000)되고, 우리가 원하는 가상 페이지 1로 변환한다. 이 값을 페이지 테이블 베이스 레지스터가 가리키는 PTE배열에 대한 인덱스로 사용한다.
- PTE의 위치를 찾는다.
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))
- PTE반입
PTE = AccessMemory(PTEAddr)
- 프로세스가 페이지에 접근할 수 없다면 예외 발생시키고, 접근할 수 있다면 물리 주소 만들고 가져온다.
if (PTE.valid == False)
RaiseException(SEGMENTATION_FAULT);
else if (CanAccess(PTE.ProtectionBits) == false)
RaiseException(PROTECTION_FAULT);
else
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
Register = AccessMemory(PhysAddr)
- PFN을 SHIFT만큼 왼쪽으로 쉬프트하고 오프셋과 논리적 연산을 OR 연산을 하여 최종 주소를 형성한다.
- 여기서 알 수 있듯이, 모든 메모리 참조에 대해 먼저 페이지 테이블 변환 정보를 반입해야 하기에 반드시
한 번의 추가적인 메모리 참조가 필요하다. 이 경우 프로세스는 2배 이상 느려진다.
메모리 트레이스
int array[1000];
...
for (i = 0; i < 1000; i++)
array[i] = 0;
- 해당 코드를 디스어셈블(disassemble)하여 어떻게 메모리 접근을 하는지 알아보자.
1 0x1024 movl $0x0,(%edi, %eax, 4)
2 0x1028 incl %eax
3 0x102c cmpl $0x03e8, %eax
4 0x1030 jne 0x1024
- 값 0($0x0)을 가상 메모리 주소로 옮긴다. 0 값이 저장될 가상 메모리 주소는 %edi의 값을 %eax의 4배에다 더해서 계산된다. %edi는 배열의 시작 주소를 저장하고, %eax는 배열 인덱스(i)를 저장한다.
- %eax에 저장된 배열 인덱스를 증가시킨다.
- %eax의 값과 16진수 0x03e8 또는 십진수 1000을 비교한다.
- 비교 결과 아직 두 값이 같지 않다면 루프의 상단으로 다시 분기한다.
- 프로그램이 실행되면, 각 명령어 반입 시에 메모리가
두 번참조한다. 명령어 위치를 파악하기 위해 페이지 테이블 접근 한 번, 명령어 자체에 한 번. movl 명령어는 배열 자체에 접근이 필요하다.
- 루프당 10번의 메모리 접근이 존재한다. 네 번의 반입과 한 번의 메모리 갱신, 그리고 이러한 반입과 갱신을 위한 주소 변환을 위한 총 다섯 번의 페이지 테이블 접근이다.
