*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :)
메모리 관리의 계속해서 언급한 문제가 무엇인가?!!!!
바로 단편화(fragmented)이다...
가변 크기로 메모리를 분할하여 할당하는 방법인 segmentation도 단편화 문제...
그럼 고정된 크기로 메모리를 분할하여 사용하면 어떨까?
이 방법이 바로 페이징 Paging 이다.
이번 글에선 이 페이징에 대해 알아보자!
🧐 Paging이란
공간을 동일 크기의 조각으로 분할하는 방법이다.
이 fixed-size(고정된 크기)를 page라고 부른다.
아래 그림으로 살펴보자.
총 크기가 64byte로,
4개의 16byte page로 구성되어있다.
실제 physical memory와 연결하여 생각해보자.
아래 그림과 같이 생성된다.
페이징은 세그먼트와 다르게 스택의 커지는 방향 등을 고려할 필요가 없다.
프로세스의 주소 공간 사용 방식과 상관없이 효율적으로 주소 공간 개념을 지원하는 유연성을 갖고있다.
또한, 페이징은 비어있는 페이지만 찾으면 된다.
빈 공간 관리가 매우 단순하다.
비어있는 페이지에 대한 정보는 page table(페이지 테이블)이라는 자료 구조를 사용한다.
Page table은 프로세스 마다 각 가상 페이지에 대한 물리 메모리 위치를 기록한다.
가상 페이지의 주소 변환(address translation) 정보를 저장한다.
🧐 Address Translation (주소 변환)
Virtual address
- VPN(Virtual Page number) : Page table index
- Offset
위 두 가지로 구성되어 있다.
가상주소 공간이 64byte인 경우 가상주소는 6비트(2^6 = 64)가 필요하다.
페이지의 크기는 16byte로 총 4개이고, 4개의 페이지를 선택할 수 있도록 2비트 VPN을 갖는다.
나머지는 페이지 내에서 우리가 원하는 byte 위치를 나타내는 offset이다.
Virtual address가 21로 예를 들어보자.
21의 이진 형태는 010101이다.
VPN = 01(2) = 1
OFFSET = 0101(2) = 5
자 그럼 Virtual address를 address translation해보자
VPN은 address translation을 거쳐 PFN(Physical Frame Number)로 변환한다.
가상 페이지에 대한 물리 메모리 위치를 기록하는 Page table로 VPN과 PFN을 매핑할 수 있다.
Physical Address
- PFN(Physical Frame Number)
- offset
으로 구성되어 있다.
offset은 페이지 내에서 우리가 원하는 byte위치를 담기 때문에, 물리주소로 변환 시에도 변할 필요가 없다.
🧐 Page table
Page table의 구성
Page table을 linear page table, 단순한 배열의 형태로 생각해보자.
PFN을 찾기 위해 VPN으로 배열에서 해당 PTE(Page Table Entry)를 찾는다.
page table의 각 페이지 테이블 항목 (PTE, Page Table Entry)에 각각 어떤 정보가 있을까?
- Valid bit: 특정 변환의 유효 여부 표시
- Protection bit: 페이지의 Readable, Writable, Executable 표시
- Present bit: 페이지가 물리메모리에 있는지, 디스크에 있는지 (swapped out 되었는지) 표시
- Dirty bit: 메모리에 반입된 후 페이지 변경 여부 표시
- Reference bit(Accessed bit): 페이지가 접근되었는지 추척
Page table은 저장 위치
Page table이 메모리 상에 위치해있다고 생각하고 예를 들어보자.
4KB 크기의 page를 갖는 32bit의 주소 공간의 경우
virtual address는 20bit의 VPN과 12bit의 offset으로 구성된다.
20bit의 VPN은 OS가 관리해야하는 address 변환이 2^20이다.
page table의 각 페이지 테이블 항목 (PTE)가 4byte면,,,,
각 페이지 테이블을 위해 4MB = 2^20 entries * 4 Bytes per page table entry 가 필요하다.
많은 크기를 쓰게 된다... 프로세스 100개를 실행한다면 주소 변환을 위해 400MB가 필요하다.
Page table 크기가 메모리 상에서 너무 커서, 처리 속도가 저하될 수 있다.
이를 이해하기 위해 address translation 과정을 코드로 살펴보자.
// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
Virtual Address에서 VPN 부분을 가져온다.
위 그림의 경우
VPN_MASK = 110000
SHIFT = 4
VPN = 01
VPN 값으로 PTE를 찾고, PFN을 추출하고, 가상 주소와 오프셋을 연결하여 물리주소를 만든다.
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PFN << SHIFT) | OFFSET
OFFSET_MASK = 001111
마지막으로 하드웨어는 메모리에서 원하는 데이터를 가져와 eax 레지스터에 넣을 수 있다.
자, 전체 코드를 살펴보자
// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// Form the address of the page-table entry(PTE)
// PTBR(Process Table Base Register): CPU 내 프로세스 테이블 베이스 레지스터
PTEAddr = PTBR + (VPN * sizeof(PTE))
// Fetch the PTE
PTE = AccessMemory(PTEAddr)
// Check if process can access the page
if (PTE.Valid) == false
RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
RaiseException(PROTECTION_FAULT)
else
// Access is OK: form physical address and fetch it
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
Register = AccessMemory(PhysAddr)
여기서 우리는 또 문제를 발견할 수 있는데,
AccessMemory가 2번 있다. (페이지 테이블 참조, 페이지 참조)
= 먼저 페이지 테이블에서 변환 정보를 반입해야 하기 때문에,
반드시 한 번의 추가적인 메모리 참조가 필요하다.
메모리 참조는 비용이 비싸다.😭
더 자세히 페이징 했을 때 메모리 접근을 살펴보자.
우선 간단한 배열 접근 코드를 살펴보자
int array[1000];
...
for (i = 0; i < 1000; i++)
array[i] = 0;
자,,, 위 코드의 어셈블리 코드이다...
1024 movl $0x0,(%edi,%eax,4)
1028 incl %eax
1032 cmpl $0x03e8,%eax
1036 jne 1024
막막해보이지만...하나하나 보자. (힘내세요)
1024 movl $0x0,(%edi,%eax,4)- 0x0을 가상 메모리 주소로 옮긴다.
- 가상메모리 주소 = edi + eax*4
- edi: 배열의 시작 주소
- eax: 배열의 인덱스
- 4: 정수의 크기 4byte
1028 incl %eax- eax에 저장된 배열 인덱스 증가
1032 cmpl $0x03e8,%eax- eax값과 0x03e8(1000) 비교
1036 jne 1024- 비교 결과 두 값이 다르면 루프의 상단으로 분기
자 그럼 정수 배열이 아니라, 이번에는 페이지 테이블로 생각해보자.
위 그림에서 맨 위 그래프는 페이지 테이블 메모리 접근이다. 하나의 루프 당 다섯 번의 페이지 테이블을 접근한다.
페이징은 메모리를 고정 크기의 단위로 나눠서 외부 단편화가 없고,
allocate, free를 위해 free space를 찾을 필요가 없어 빠르지만,
내부 단편화가 생기고, 메모리 참조 오버헤드와 페이지 테이블 저장 공간이 많이 필요한 것의 문제가 있었다.
정말 쉽지 않다...
그래서 위 문제를 메모리 대신 캐시에 페이지 테이블을 보관하였는데....
이 방법은 다음 글에서 !!
'기본 > 운영체제' 카테고리의 다른 글
| [OS] CPU 가상화 (CPU Virtualization): 2. Limited Direct Execution: time sharing, context switch (1) | 2024.04.20 |
|---|---|
| [OS] CPU 가상화 (CPU Virtualization): 1. 프로세스란 (0) | 2024.04.20 |
| [OS] 메모리 가상화(Memory Virtualization): 4. Free-Space Management (0) | 2024.04.19 |
| [OS] 메모리 가상화 (Memory Virtualization): 3. Segmentation (1) | 2024.04.12 |
| [OS] 메모리 가상화 (Memory Virtualization): 2. Address translation (0) | 2024.04.11 |
