Paging - 정의, Method, Page table, Fragmentation, Frame table, Hadrware support, Memory Protection, Shared code

Paging

Paging

Definition : Contiguous allocation과 달리 비연속적으로 저장되는 기법으로 Page라는 block을 사용하여 allocation 하는 방법

- Logical memory는 page로, Physical memory는 frame이라는 단위로 나눠준다.

- Program을 로드할 때, N개의 page 사이즈를 필요한 프로그램이라면 사용가능한 N개의 프레임이 있어야 한다.

- Logical memory를 Physical memory로 변경하기 위해 Page Table을 사용 한다.

- 정해진 크기의 Page와 Frame을 사용하기 때문에 Internal Fragmentation이 발생할 수 있다. 그러나 비연속적으로 할당하기 때문에 External Fragmentation은 발생하지 않는다.

다음과 같이 Logical Memory의 Page와 Physical Memory의 Frame이 매치되어 할당된다. Page Table에는 page number와 frame number가 Mapping되어 저장되어 있다.

Paging method

1) Page Number(p) : Physical memory로 변환시키기 위해 Page Table에 저장되는 index로 사용된다. 각 Page별로 Physical Memory에서의 시작주소를 가지고 있다.

2) Page Offset(d) : 시작주소와 합쳐져 Physical memory로 변환된다.

2^m만큼의 메모리가 사용된다고 치면 Page numer와 offset은 다음과 같이 나눠진다.

예를 들어, Page가 4KB라고 하면 2^12 -> page offset은 12개 page number는 20개를 사용한다

- Address Translation : Page number를 통해 Page table에서 Frame number를 찾고 Frame number에 page의 크기를 곱해 시작 주소를 구하고, 이 값에 Offset을 더해주어 Physical address를 찾는다.

Paging Fragmentation

1) External Fragmentation

- 비연속적으로 저장되기 때문에 External Fragmentation은 발생하지 않는다.

2) Intenal Fragmentation

- Page와 Frame의 크기가 정해져있기때문에 Process의 크기가 프레임 크기에 맞게 들어가지 않게되면 남는 부분이 생겨 Internal Fragmentation이 발생한다

- Page의 크기가 작게하면 Internal fragmentation을 줄일 수 있다. 하지만 page table의 entry가 커지고 overhead가 커질 수 있기 때문에 적당한 size를 가지게 해야한다는 어려운 점이 있다.

-> 그래서 요즘에는 page는 4KB~8KB를 기본으로 가지고 있다.

Frame table

- Page를 할당하기 위해 OS는 Frame table을 가지고 있다.

- Frame table에는 비어있는 프레임, 사용중인 프레임, 총 프레임 등 여러 정보를 가지고 있다.

Hadrware support

1) Register 사용(Paging)

- Page table은 main memory에 존재하고 있다.

- Page-Table Base Register(PTBR) : Page table을 가리키는 포인터라고 할 수 있다.

- Page-Table Length Register(PTLR) : Page table의 size를 나타낸다.

- Main memory에 있는 Page Table에 접근하고 Data를 Physical Memory에 올리는 접근, 두번 접근을 해야 하기 때문에 성능이 떨어질 수 있다.

2) Translation Look-aside Buffer(TLB)

- Register 사용 시 접근을 두번해야한다는 단점을 극복하기 위해 빠른 look up이 가능한 associative memory, TLB로 Hardware cache를 이용하는 방법이다.

- Page Table을 검색하기 전에 Cahce에 있는 TLB를 먼저 확인함으로써 TLB에서 발견된다면 Main Memory에 존재하는 Page table을 검색하지 않고 한번의 look up으로 해결할 수 있다.

- TLB 중 일부는 address-space identifier(ASID)를 사용하여 고유한 process id를 저장하여 Protection을 한다.

- TLB는 Page Table의 일부를 저장한 것이기 때문에 TLB Hit가 높아질수록 성능이 좋아진다.

- 성능 분석

① Associative Lookup : ε time unit

② HIT Ratio : TLB에서 일치하는 Page를 찾는 비율(α)

③ Memory cycle : 1 microsecond

④ Effective Access Time(EAT)

- EAT = (1+ε)α + (2+ε)(1-α) = 2+ε-α

(1+ε) : TLB Hit로 메모리 접근이 1번일 때

(2+ε) : TLB Miss로 메모리 접근이 2번일 때

Memory Protection

- 각 Frame마다 protection bit를 만들어 Memory Protection을 한다.

- Page Table에 있는 모든 entry에 valid-invalid bit를 생성한다.

-> valid : Logical memory에 page가 존재한다는 의미로, 올바른 페이지를 말한다

-> invalid : Logical memory에 page가 존재하지 않는다는 의미로, 잘못된 접근을 말한다.

- PTLR을 사용하여 올바른 주소인지 확인한다.

Shared Code <-> Private code and data

1) Shared Code

- 프로세스 간 공유하고 있는 Read-only 코드를 의미한다.

- 같은 frame이 각기 다른 logical page에 mapping될 수도 있다.

2) Private code and data

- 각각의 프로세스는 분할된 code,data를 가지고 있다.

- Private code와 data는 Logical address space의 어떤 곳이나 위치할 수 있다.