페이징 시스템(Paging System)

페이징 시스템(Paging System)

Paging : 커다란 크기의 작업을 고정된 일정한(동일한) 크기로 나누어 처리하는 방식입니다.
(번외, Segemetation : 메모리를 프로세스의 크기에 따라 잘라 넣는 방식(배치 정책 중 또 다른 정책))

 

(좌) 가상주소 -> 물리주소 변환 구조, (우) 실제 메모리에 맵핑되는 모습

- p : 가상 메모리의 page 번호
- d : p안에서 참조하는 위치(페이지 내부 주소; 변위; offset)
paging system에서 해당 프로세스에서 특정 가상 주소를 가지고 어떤 데이터에 접근하고자 하면, 
-> page table에 해당 가상 주소와 그 page번호(p)가 있는지 확인합니다.
-> page 번호가 있으면 이와 매핑된 첫 물리 주소(p')를 알아냅니다.
-> 그러면 페이지 처음부터 얼마 떨어진 위치인지를 알려주는 변위(d)를 더하면
-> p' + d가 실제 물리 주소가 됩니다.

 

용어 정리

Page	일정한 크기로 나우어진 고정된 크기의 블록입니다.
Frame	페이지에 대응하는 물리 메모리를 페이지와 같은 크기로 나눈 목록입니다.
Offset	페이지의 처음 위치에서 해당 주소까지의 거리입니다.
Page Number	Page Table의 Index 역할을 하는 번호입니다.
Page Frame Number	Page Table의 Index에 대응되는 물리 메모리의 시작주소를 가진 번호입니다.
Page Table	Page Number와 Page Frame Number가 맵핑되어있는 표입니다.
Page Directory	Two-level-Paging에서 먼저 큰 단위의 맵핑을 할 때 사용되는 블록입니다.
CR3	프로세스 구동시, 해당 프로세스의 페이지 데이블의 base주소가 별도의 레지스터에 저장됩니다. 별도의 레지스터에 저장된 것이 CR3입니다.

 

다중 단계 페이징 시스템

4GB의 프로세스를 모두 페이지로 나눈다면 이 중 당장 사용되지 않는 데이터까지 페이지로 만들어질 것이고 이러면 너무 많은 페이지로 나눠질 것이다. 이렇게 하지 말고 페이징 정보를 단계를 나누어 생성하면 필요없는 페이지는 생성하지 않고 공간 절약이 가능해진다. 

 

 

페이징 시스템과 공유 메모리(IPC)

어떤 경우에는 프로세스간 동일한 물리 주소를 가리키게 하여 공간 절약과 메모리 할당 시간을 절약 할 수도 있습니다.

만약 process A, B가 노란색 부분을 공유하고 있다면, 물리 메모리에는 page 주소변환시 해당 물리 주소만 같은 곳을 가리키게 하면 메모리를 추가로 쓰지 않아도 됩니다.

 

 

MMU와 TLB

TLB(Translation Lookaside Buffer)

페이지 정보 캐쉬

 

 

요구 페이징(Demand Paging or Demanding Paging)

위와 같은 paging system을 사용하면 프로세스에서 나눠진 page를 언제 물리 메모리에 올려놓을지에 대한 정책이 필요하다. 선행 페이징으로 하면 그냥 프로세스를 실행하자마다 page먼저 다 올려두는 것인데, 이것보다 실제로 필요할 때 page를 메모리에 올리는 것이 좋을 것이다.

 

용어 정리

Demand Paging	프로세스의 모든 데이터를 메모리로 적재하지 않고, 실행 중 필요한 시점에서만 메모리로 적재할 수 있게 해주는 것입니다.
Invalid	사용되지 않은 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우(valid와 반대) 처음에는 모든 page가 invalid로 초기화 되어있고, 이후 사용될 때마다 valid로 변합니다. address translation하는 경우는 invalid bit 이라면 page fault가 발생합니다.
page fault	어떤 페이지가 물리 메모리에 없을 때 발생하는 인터럽트로, page fault가 발생하면 운영체제가 해당 페이지를 물리 메모리에 올려줍니다.

 

 

 

페이지 교체 정책(Page Replcement Policy)

1) FIFO 알고리즘

가장 먼저 들어온 페이지를 내립니다.

2) OPT(OPTimal) 알고리즘

앞으로 가장 오랫동안 사용하지 않을 페이지를 내립니다.
(BUT, 미래에 어떤 페이지를 얼마나 사용할 것인지는 알 수 없으므로 일반 OS에서는 구현이 불가능합니다.)

3) LRU(Least Recently Used) 알고리즘

가장 오래전에 사용된 페이지를 내리자라는 아이디어입니다.
과거 기록을 기반으로 하는 알고리즘입니다.

4) LFU(Least Frequently Used) 알고리즘

가장 적게 사용된 페이지를 내리는 것 입니다.

5) NUR(Not Used Recently) 알고리즘

LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 내리자는 알고리즘입니다.
차이점 : 각 페이지마다 참조 여부를 나타내는 비트(R), 수정 여부를 나타내는 비트(M)을 두어서 (0, 0), (0, 1), (1, 0), (1, 1) 순으로 교체합니다.