[ 다단계 페이지 테이블 (Multi-Level Paging) ]
페이지 테이블은 다단계로도 사용할 수 있다.
4단계 페이지 테이블을 사용한다고 했을 때 메모리에 한 번 접근하려면 네 번의 주소변환과 한 번의 실제 데이터 접근을 해야 한다. (총 다섯 번 접근)
메모리에 접근하는 시간이 100ns 일 때 4단계 페이지 테이블을 사용하면 500ns가 걸린다.
하지만 주소 변환을 전담해 주는 일종의 캐시 메모리(TLB)를 통해 이루어지기 때문에 다단계 페이지 테이블을 사용하더라도 시간이 오래 걸리지 않는다.
TLB Hit Ratio가 98%이라고 할 때..
98%는 120ns(메모리 접근 100ns + TLB 접근 20ns)가 걸리고 2%는 520ns(메모리 접근 500ns + TLB 접근 20ns)가 걸리므로 총 128ns가 소요된다.
메모리 접근하는 데 걸리는 시간이 100ns인 것에 비하면 결과적으로 주소 변환을 위해서는 28ns만 사용한 것이다.
↓ 메모리 접근 시간 발행 글 ↓
2023.02.10 - [Operating System] - [운영체제] Memory Management 4 (불연속할당/Paging 기법)
[운영체제] Memory Management 4 (불연속할당/Paging 기법)
연속 할당 : 프로그램이 메모리에 올라갈 때 통째로 메모리에 올라가는 방식 불연속 할당 : 프로그램을 구성하는 주소 공간을 같은 크기의 페이지 단위로 잘게 쪼개서 페이지 단위로 메모리에
rannnneey.tistory.com
● Multilevel Paging and Performance
✓ Address Space가 더 커지면 다단계 페이지 테이블 필요
✓ 각 단계의 페이지 테이블이 메모리에 존재하므로 Logical Address의 TLB를 통해 메모리 접근 시간을 줄일 수 있음
✓ 4단계 페이지 테이블을 사용 시..
- 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고 TLB hit ratio가 98%인 경우
- Effective Memory Access Time = 0.98 * 120 + 0.02 * 520 = 128 nanoseconds.
- 결과적으로 주소 변환을 위해 28ns만 소요
● Valid(v), Invalid(i) Bit in a Page Table
Logical memory에 있는 페이지 개수만큼 페이지 테이블의 엔트리가 존재하며, 그 엔트리에는 물리적 주소 정보가 들어있다.
주소 정보만 들어있는 것은 아니고 Valid-Invalid bit라는 부가적인 bit가 페이지 테이블의 Entry마다 각각 저장이 된다.
Valid-Invalid Bit는 Frame number의 0이 의미가 있는 0인지 없는 0인지 구분하기 위해 사용된다.
Logical memory를 보면 Page가 5번까지 있다. Page 6과 Page 7은 사용되지 않는 페이지인데 페이지 테이블을 보면 6번과 7번 Entry가 존재한다.
테이블이라는 자료구조 특성상 인덱스로 접근해야 하기 때문에 프로그램에 주소 공간이 가질 수 있는 Maximum 크기만큼 페이지 테이블 Entry가 있어야 한다.
6번과 7번 페이지는 없지만 페이지 테이블 Entry는 만들어지고, 대신에 사용되지 않기 때문에 Valid-Invalid bit가 Invalid로 표시된다.
● Memory Protection
Proctection Bit는 연산에 관한 권한을 표시하기 위한 bit이다.
페이지 테이블은 프로세스마다 독립적으로 존재하기 때문에 본인의 페이지에 대해서만 주소 변환을 할 수 있다.
다른 프로세스가 페이지 테이블을 못 보게 하는 것은 아니고 어떤 연산에 대해 접근 권한이 있냐를 나타낸다.
코드가 저장된 페이지는 중간에 내용이 바뀌면 안 되고 원래 있는 내용을 CPU에 읽어서 Instruction을 실행하는 용도이기 때문에
Code는 Read Only로 해놓고 Data, Stack과 같은 페이지는 Read/Write 권한을 다 줘야 한다.
✓ Page Table의 각 Entry마다 아래의 bit를 둔다
✓ Protection bit : Page에 대한 접근 권한 (Read/Write/Read-Only)
✓ Valid-invalid bit
- Valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)
- invalid는 해당 주소의 Frame에 유효한 내용이 없음을 뜻함 (접근 불허)
✓ 유효한 내용이 없음이란..
- 프로세스가 그 주소 부분을 사용하지 않는 경우
- 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우
[ 역 페이지 테이블 (Inverted Page Table) ]
페이지 테이블 Entry가 100만 개 이상이 되면 페이지 테이블 자체가 메모리 공간을 많이 차지하게 된다.
Address Space가 허용하는 페이지 테이블의 Entry가 만들어져야 하고 프로세스마다 각각 주소 변환을 해야 하기 때문에 공간 Overhead가 크다.
이 Overhead를 막기 위한 방법이 Inverted Page Table이다.
원래의 페이지 테이블을 통한 주소 변환을 역발상으로 뒤집어 놓은 방법이다.
원래 페이지 테이블은 프로세스마다 존재한 반면에 Inverted Page Table은 시스템 안에 페이지 테이블이 딱 한 개 존재한다.
페이지 테이블의 Entry가 프로세스의 페이지 횟수만큼 존재하는 게 아니라 물리적 메모리 프레임 개수만큼 존재한다.
기존에는 주소 변환을 할 때, 페이지 번호를 보고 위에서부터 페이지 번호만큼 떨어진 Entry에 가서 주소 변환을 하는 방법을 사용했는데,
Inverted Page Table에서는 첫 번째 Entry에는 첫 번째 Page Frame에 들어갈 페이지 논리적 주소가 들어있고 두 번째 Entry에는 두 번째 Page Frame에 들어갈 페이지 논리적 주소가 들어있다.
즉, Page Frame의 f 번째 Entry에 가면 논리적 페이지 번호가 나오게 하는 게 Inverted Page Table이다.
원래 주소 변환을 하는 목적은 Logical Address를 Physical Address로 변환시키는 것이다.
근데 이 방식은 Physical Address를 보고 Logical Address를 바꿀 수 있는 Table이다. 어쨌든 우리는 논리 주소를 가지고 물리 주소를 알아내야 한다.
논리 주소에 해당하는 Page 번호 p가 물리적 메모리 어디에 올라가 있는지 알아내려면 페이지 테이블 Entry를 모두 찾아봐야 한다.
찾아서 해당하는 p가 나오면 해당 페이지는 물리적 메모리 f 번째 Frame에 올라가 있는 걸 알 수 있다.
또한, 논리적 페이지 번호만 저장하면 되는 게 아니라 페이지 번호 p가 어떤 프로세스의 p 번째 페이지인지 알 수 있는 Process ID도 함께 저장해야 한다.
논리 메모리는 프로그램마다 별도로 있기 때문에 f 번째 Frame에 올라가 있는 페이지가 어떤 프로세스의 p 번째 페이지를 나타내는지 알아야 하기 때문이다.
Inverted Page Table은 페이지 번호가 주어지면 페이지 테이블 Entry를 전체 검색해야지만 주소 검색이 가능하다.
이 방법은 공간은 줄일 수 있는데 시간적 Overhead가 크기 때문에 Entry를 병렬적으로 검색할 수 있도록 Associative Register를 사용한다.
CPU가 Logical Address (pid, p)를 주면 페이지 테이블에서 pid, p가 어디 있는지 검색하고, 그 위치로부터 위에서 몇 번째 Entry 인지 확인한다.
f 번째 Entry라고 한다면 해당 번호를 Page Frame 번호로 넣어주면 주소 변환이 끝나게 된다.
✓ Page Table이 매우 큰 이유
- 모든 Process 별로 Logical Address에 대응하는 모든 Page에 대해 Page Table Entry가 존재
- 대응하는 Page가 메모리에 있든 아니든 간에 Page Table에는 Entry로 존재
✓ Inverted Page Table
- Page Frame 하나 당 Page Table에 하나의 Entry를 둔 것 (System-Wide)
- 각 Page Table Entry는 각각의 물리적 메모리의 Page Frame이 담고 있는 내용 표시 (Process-ID, Process의 Logical Address)
단점 : 테이블 전체를 탐색해야 함
조치 : Associative Register 사용 (Expensive)
[ 공유 페이지 (Shared Page) ]
서로 다른 프로세스 P1, P2, P3가 있는데 이 프로그램들이 같은 코드를 갖고 프로그램을 돌린다고 하면 코드 부분은 같은 걸 써도 된다.(Shared code)
각각을 물리적 메모리에 별도로 올리는 게 아니라 Shared code는 하나의 물리적 메모리에 올리는 것이다.
공유할 수 있는 코드는 따로 올리는 게 아니라 같은 프레임으로 Mapping 해서 메모리에 한 Copy만 올릴 수 있다.
Shared code는 두 가지 조건을 만족해야 한다. Read Only로 Setting 해야 하고 동일한 Logical Address에 위치해야 한다.
컴파일되어 있는 코드 안에 Logical Address가 적혀있는데, 그 주소를 바꿀 수 없기 때문이다.
✓ Shared code
- Re-entrant Code (=Pure code)
- Read-Only로 하여 프로세스 간에 하나의 Code만 메모리에 올림 (eg. Text Editors, Compilers, Window Systems)
- Shared Code는 모든 프로세스의 Logical Address Space에서 동일한 위치에 있어야 함
✓ Private Code and Data
- 각 프로세스들은 독자적으로 메모리에 올림
- Private Data는 Logical Address Space의 아무 곳에 와도 무방
이전 발행글
2023.02.10 - [Operating System] - [운영체제] Memory Management 4 (불연속할당/Paging 기법)
[운영체제] Memory Management 4 (불연속할당/Paging 기법)
연속 할당 : 프로그램이 메모리에 올라갈 때 통째로 메모리에 올라가는 방식 불연속 할당 : 프로그램을 구성하는 주소 공간을 같은 크기의 페이지 단위로 잘게 쪼개서 페이지 단위로 메모리에
rannnneey.tistory.com
[운영체제] Memory Management 5 (불연속 할당, Paging 기법, Two-Level Page Table)
이전 발행글 2023.02.10 - [Operating System] - [운영체제] Memory Management 4 (불연속할당/Paging 기법) [운영체제] Memory Management 4 (불연속할당/Paging 기법) 연속 할당 : 프로그램이 메모리에 올라갈 때 통째로
rannnneey.tistory.com
