2024. 5. 30. 01:41ㆍCS/Operating System
1. Paging
페이징의 동작 과정을 알아보자.
먼저 피지컬한 메모리를 먼저 4KB 단위로 조각조각 쪼갠다. 그 조각 하나 하나를 프레임이라 한다. 물론 4KB가 아닐 수도 있다.
그리고 프로세스가 사용하는 가상 메모리도 4KB 단위로 쪼개고, 페이지라 부른다. 이 또한 4KB가 아닐 수 있다.
그리고 중간에 페이지 테이블을 만든다. 페이지 테이블은 프로세스별로 따로 만드는 것을 주의하자. TCB처럼 프로세스마다 페이지 테이블을 OS가 가지고 있다.
유저는 가상의 크고 연속적인 가상 메모리를 본다.
커널은 페이지 테이블을 보고 피지컬한 메모리로 접근한다.
- ex) Page 1 → Page table → Frame 11
페이지에 대해 좀 더 자세히 알아보자.
- 피지컬한 어드레스를 연속적으로 배치하지 않아도 된다.
- 가상의 주소에서 페이지는 붙어있지만, 피지컬한 메모리에 프레임은 다 붙어있지는 않다. 물론 한 프레임 내에서의 조각은 연속적이다.
- 피지컬한 메모리는 frames라 불리는 fixed-sized block으로 분할된다.
- 가상의 메모리는 pages로 분할되는데 frame과 page의 size는 같다.
- frame size는 하드웨어가 지원하기에 정해져 있고, page size는 OS가 선택하는 것이다.
- n개의 페이지로 프로그램을 실행시키려면, n개의 free frames를 찾고 프로그램을 load 해야 한다.
- 새로운 프로세스에게는 프레임을 할당해야 한다. 따라서 OS는 모든 빈 프레임의 정보를 유지하고 있다.
- 프로세스가 생성되면 페이지 테이블을 set up한다. 가상의 주소를 피지컬한 주소로 translate 하기 위해서이다.
프로세스 A의 메모리의 사용량이 늘어나면 A의 가상 어드레스 스페이스, Page Table A, 피지컬한 메모리를 모두 추가하면 된다.
꼭 기억해야할 점은 페이지 테이블은 OS가 관리하며 프로세스마다 하나씩 가지고 있다는 것이다! 프로세스가 끝나면 해당 페이지 테이블도 삭제하고, 프로세스가 사용하던 피지컬한 메모리도 빈 프레임으로 만든다.
유저의 관점에서 페이징
유저는 메모리를 0~N번까지의 연속적인 페이지로 본다.
- 이를 VAS(Virtual address space)라 한다.
실제 피지컬한 메모리는 연속되어 있지 않다.
- 당연하게도 페이지 테이블의 메모리 주소 매핑 정보는 유저 프로그램에서는 절대 접근할 수 없다.
Protection은 프로그램이 그 프로그램의 VAS 밖의 메모리를 참조할 수 없기에 제공된다.
a.out을 계속 실행시켜도 n의 주소가 똑같게 찍히는 이유가 뭘까?
→ 페이징을 사용하므로 프로그램은 메모리를 가상 주소로만 접근하기 때문이다.
Translating addresses
💡 참고) 32bit 머신에서 virtual address는 32bit이고 메모리의 어드레스 스페이스 하나의 크기는 1byte이다.
2^10 = 1 KB, 2^20 = 1 MB, 2^30 = 1GB이므로 32bit 머신에서 2^32개의 주소를 만들 수 있다. 또 주소 하나당 1byte만큼의 공간을 참조하고 있으므로 최대 4 GByte의 메모리를 참조할 수 있다. 그 말은 32bit 머신에서 수용할 수 있는 최대 메모리 크기가 4 GByte가 된다는 말이다!
주소를 번역하는 과정은 어떻게 될까? 가상 주소는 두 부분으로 이루어져 있다.
- 가상 주소는 두 부분으로 이루어져 있다.
<virtual page number :: offset> - 가상 주소를 번역하려고 페이지 테이블에 접근할 때 VPN을 인덱스로 사용한다.
- offset은 페이지 테이블을 거치지 않고, 번역 없이 그대로 피지컬한 주소에 사용한다. 페이지의 한 조각은 똑같은 크기의 프레임으로 매핑되므로 가상 주소의 offset은 물리 주소로 변환되어도 전혀 달라지지 않는다.
- 즉, <VPN::offset> → <PFN::offset, VPN → PFN>이다. FPN은 VPN으로 페이지 테이블에서 찾을 수 있다.
Page Tables
- 페이지 테이블은 OS에 의해 관리된다.
- VPN을 PFN으로 바꾸는 역할을 한다.
- 가상 address space에서 페이지 하나당 한 페이지 테이블 엔트리(PTE)를 가진다.
- one PTE per VPN
- 페이지 테이블은 배열로 사용하고, index로 VPN을 사용하기에 빠르게 PFN를 찾을 수 있다.
- CPU에 32bit address가 들어오면 VPN 값을 가지고 page table의 VPN index (위에서 VPN번째)를 찾아보면 PFN을 얻을 수 있다. 즉, PFN 값을 통해 피지컬 메모리에 접근하게 되고, 피지컬한 메모리에서 특정 프레임 PFN의 오프셋만큼 가면 내가 접근하려는 메모리 조각이 존재하는 것이다.
2. Paging example
- Virtual address : 32 bits (4G)
- Physical address : 20 bits (1M)
- Page size : 4 KB
이 상황에서 피지컬한 메모리가 얼마나 꽂혀있는지, VPN, offset, PFN, page table size, page table entry를 추측해 보자.
.
.
.
피지컬한 어드레스는 20bit만 사용한다고 했으므로 이 컴퓨터에는 피지컬한 메모리가 1MB 꽂혀있다는 뜻이다.
- 참고로 가상 메모리는 OS에서 정하기에 제한이 없지만 피지컬한 메모리는 얼마나 꽂느냐에 달려있다.
30bit를 꽂으면 1GB, 31bit를 꽂으면 2GB, 33bit를 꽂으면 8GB인데, 가상 주소가 32bit이기 때문에 33bit는 꽂을 필요가 없다.
페이지 size를 4KB로 정했다. 페이지 size가 4KB라는 말은 하나의 페이지가 2^12 byte의 데이터를 가지고 있다는 뜻이다. 여기서 주의해야 할 점이 32bit 머신의 어드레스 스페이스 한 칸의 크기가 1byte이다. 페이지가 1byte 단위로 데이터가 끊긴다는 것이다.
다시 돌아와서, 페이지 size가 2^12 byte이다. 그렇다면 offset은 12bit가 된다. 12bit의 offset으로 2^12개의 바이트를 식별할 수 있기 때문이다.
virtusl address가 32bit이므로 VPN은 20bit가 될 것이다.
offset이 정해지면서 VPN bit가 20bit로 정해졌다. 그렇다는 말은 가상 주소가 2^20개로 표현된다는 것이다. 따라서 페이지 테이블은 2^20개의 엔트리를 가지게 된다.
또, 정해진 offset을 물리주소에서도 똑같이 사용하므로 PFN도 정해진다. 물리주소가 20bit이므로 8bit가 되는 것이다.
PFN이 정해졌으므로 페이지 테이블 엔트리 size도 8bit가 된다.
이번에는 직접 주소를 번역해 보자.
00004AFE라는 가상 주소에 접근한다면 물리 주소는 어떻게 될까?
해당 가상 주소에서 VPN은 4, offset은 AFE가 된다. 페이지 테이블을 참조해 보니 VPN 4에 B6이 있는 것을 확인할 수 있다. 그리고 offset으로 물리 주소에 접근할 수 있다. 물리 주소는 B6AFE가 된다.
💡정리하자면, offset은 page size에 의해 정해지고 그에 따라 VPN, 페이지 테이블 엔트리의 수가 정해진다. 또, offset에 의해 PFN이 정해지고, 이는 페이지 테이블 엔트리 사이즈를 결정한다!
예시에서 피지컬한 어드레스가 30bit, Page size가 4KB일 때를 직접 해보자. 꼭 직접 해보자!
위의 테이블을 분석해 보면, 피지컬한 주소가 30bit이다. 따라서 피지컬한 메모리가 1GB 꽂혀있다는 사실을 알 수 있다.
또, FPN을 18bit 사용하기에 페이지 테이블 엔티티는 18bit가 된다.
Valid 비트를 하나 사용하는데, Valid bit로 해당 페이지가 유효한지 표시하는 것이다. 사실은 Valid bit 말고도 다른 정보들도 존재한다. 하나씩 알아보자.
3. Page Table Entries (PTEs)
페이지 테이블에는 프레임 넘버뿐 아니라 몇 가지 정보를 더 가지고 있다.
Valid
- 이 페이지 테이블 엔트리가 사용되고 있는지 아닌지를 나타낸다.
- OS는 프로세스가 해당 페이지를 사용하던 안 하던 해당 프로세스가 쓸 수 있는 만큼 다 만들어놓는다. 따라서 해당 페이지 테이블 엔트리가 사용되는지 아닌지, 혹은 유효한지 아닌지를 나타낸다.
- Valid bit가 0이라면 아직 사용된 적 없거나, 빈 공간 확보를 위해 페이지를 메모리로 내려보내고 빈 페이지로 두고 Valid bit를 0으로 세팅할 수도 있다.
- Valid가 1이라면 관련된 페이지는 유효하게 피지컬한 메모리에 들어있다는 의미가 된다.
- 0이라면 페이지 테이블에 들어있는 프레임이 메모리에 없다거나 빈 공간이라는 등의 방식으로 유효하지 않은 걸 나타낸다. 보통 스와핑 때문에 메모리에 존재하지 않는 경우이다.
Reference
- 참조가 일어났는지 아닌지를 나타낸다. 어떤 페이지에 대해 read 혹은 write를 하면 R값이 1이 된다.
- 초기에는 0으로 설정되고 프로세스가 해당 페이지에 액세스 하면 R이 1이 된다.
- 주기적으로 R값을 전체 0으로 세팅하기도 한다.
Modify
- R과 비슷한데 write가 일어났을 때만 체크된다.
- 해당 페이지를 읽기만 하면 R만 1이 되고 M은 여전히 0이다. 해당 페이지를 쓰면 둘 다 1이 된다.
- 페이지의 내용이 바뀌어서 dirty 한 상태인지 아닌지 알기 위해서 사용한다. 나중에 페이지 replacement algorithm에서 사용된다.
Protection (Prot bit)
- 이 페이지가 Read, Write, Execute가 가능한지 불가능한지 나타내기 위해 사용한다.
- 예를 들어 가상 메모리에서 코드 부분이 적힌 페이지는 Read, Execute가 가능해야 한다. 보통은 Write는 가능하면 안 된다.
- 데이터 영역, 힙 영역, 스택 영역의 페이지는 Read, Write가 다 가능해야 한다. 그런데 이 영역에선 코드가 없으므로 Execute가 가능해서는 안된다.
- Prot를 사용하는 이유는 특정 데이터에 대해 읽기만 가능하고 실행 불가능하게 세팅하는 등 보안을 위해서이다. 해킹 방식 중 스택에 코드를 넣고 실행시킬 수 있어서 해킹에 대한 보호도 포함된다.
- 상태가 3개이므로 2bit를 사용해야 한다.
- Read-only, Read-write, Execute-only의 세 상태를 지원한다.
- Prot bit로 메모리를 잘 보호할 수 있다. Prot bit만 잘 세팅하면 페이지별로 read가능/실행가능 과 같은 방식으로 보호할 수 있다.
4. 페이징 장단점
페이징 장점
- 피지컬한 메모리를 할당하기 굉장히 쉽다.
- 프로세스가 필요로 하는 메모리 전체를 다 피지컬한 메모리로 할당하는 방식이 아니라 페이지 테이블에 프레임 넘버만 적어주면 된다.
- OS는 사실 빈 프레임의 리스트를 유지하기에 거기서 하나 빼서 프로세스 페이지 테이블에 적어주면 끝이다.
- 고정된 크기로 프레임을 자르기에 external fragmentation이 생기지 않는다.
- 어떤 프로그램을 Page out 시키기 쉽다.
- 페이지 사이즈가 모두 동일하다. 따라서 메모리가 부족하다면 페이지 테이블에서 필요 없는 엔트리의 valid bit를 0으로 만들면, replacement 알고리즘에 의해 삭제된다.
- 페이지의 크기는 보통 disk block size의 배수로 설정된다.
- 프로텍션이 굉장히 쉽다. 코드 부분에 있는 실행 코드를 업데이트시키거나 스택 영역에 코드를 써서 실행시키는 등의 접근을 막을 수 있다.
- 페이지를 공유하기 쉽다. 여러 프로세스들끼리 공유하려는 프레임을 페이지 테이블 엔트리에 적어주면 끝이다.
페이징 단점
- internal fragmentation 문제를 가지고 있다.
- 페이지의 일부만 사용해서 나머지는 사용하지 않는 문제가 생겨도 페이지가 4KB라 그렇게 큰 문제가 되지는 않는다.
- 메모리를 액세스 하는데 시간적 오버헤드가 성능상 꽤 크다.
- 메모리에 있는 i라는 값을 액세스 하기 위해 페이지 테이블을 가서 i값의 프레임 넘버를 찾고, 피지컬 메모리에 가서 액세스해야 한다. 따라서 메모리에 두 번 접근해야 한다는 오버헤드가 발생한다. 레지스터에 액세스 하는 거에 비해 메모리에 액세스 하는 건 굉장히 느리므로 꽤나 큰 오버헤드이다.
- 이 문제는 TLB 하드웨어의 지원으로 해결할 수 있다.
- 굉장히 큰 페이지 테이블을 유지하는 메모리가 요구된다. 즉, 스페이스 오버헤드가 발생한다.
- 페이지 테이블을 프로세스가 쓰던 안 쓰던 많은 양의 엔트리를 준비해놔야 한다.
- 예를 들어, 32bit address space, 4KB page는 2^20의 PTE를 준비해놓아야 한다.
- 페이지당 4 bytes를 사용한다면 페이지 테이블의 크기는 4MB가 된다.
- 25개의 프로세스를 생각해 보면 100MB를 페이지 테이블로 사용해야 한다.
- 이렇게 미리 준비하는 이유는 배열의 형태를 사용하기 위해서이다. 배열의 index로 O(1)에 페이지 테이블에 접근할 수 있어서 매우 빠르기 때문이다. linked list로 구현한다면 space overhead는 해결되지만 index를 사용할 수 없어서 데이터를 찾는데 O(n) 시간으로 오래 걸린다.
- page the page tables, multi-level page tables, inverted page tables로 해결할 수 있다.