[9-2] Paging and Swapping

[ Paging ]
Process의 physical address space를 non-contiguous하게 하는 것.
 
Contiguous Memory Allocation의 아래 2가지 문제를 극복할 수 있음.
1) External fragmentation
2) Associated need for compaction (Free hole들을 모아서 압축해야할 필요성)
 
[ Basic Method for Paging ]
physical memory를 fixed-sized blocks(frames)로 쪼개고,
logical memory 또한 same sized blocks(pages)로 쪼갠다.
 
이렇게하면 비연속적인 페이지 단위를 물리적 주소로 매핑해서 올릴 수 있게 된다.
→ 매핑은 운영체제가 한다 (완전히 분리된 logical address와 physical address)
 
CPU에 의해 생성된 모든 address는 2가지로 나뉜다.
- page number (p)
- page offset (d)

 
page table에서 page number에 해당하는 p에 접근, 거기에 적혀있는 f를 얻어
physical memory에 있는 frame인 f에 접근, f로부터 d만큼 떨어진 곳이 실제 저장된 physical memory의 주소
 
만약 process가 4개의 page를 쓰고 page하나의 절반이 남는다면 그게 Internal Fragmentation이 된다.
 
[ page와 frame의 size는 어떻게 정할까? ]
하드웨어에 의해 정해져 있다
 
page의 개수가 총 1024개라면, page number를 표현하는데 10bit가 필요,
page의 크기가 4Kb라면, page offset을 표현하는데 12(2^12 : 4096)bit가 필요
 
Context Switching이 일어날 때, Page Table도 reload 되어야 한다.
재진입했을 때, 페이지 테이블이 그대로라는 보장이 없으므로
→ 페이지 테이블은 크기가 크므로 각 process의 PCB내에 있는 register에 페이지 테이블에 대한 pointer가 저장되어야 한다.
 
[ PTBR(page table base register) ]
page table에 대한 pointer
page table은 main memory에 있는데, 결국 page table에 한 번 접근 후, 실제 데이터에 다시 접근해야 하므로 2번 접근해야 한다.
 
[ Translation Look-aside Buffer (TLB) ]
Page table에 대한 cache memory와 같은 역할 
TLB Hit된다면 필요한 page number가 TLB내에 있다는 뜻

 

** TLB Hit 됐다면 페이지 테이블에 대한 miss (page fault)는 발생할 수 없다. 왜냐면 TLB는 page table의 캐시이기 때문.

컴퓨터는 TLB → 캐시메모리 → Page Table 순으로 접근한다.
TLB에서 miss됐다면 MMU로 변환한다.

 
 
[ Memory Protection with Paging ]
Contiguous Memory Allocation에서는 base, limit register를 통해 확인하고, trap을 사용해서 Protection을 했었다.

valid - invalid bit : Page Table내에 valid/invalid 를 위한 bit를 각각 추가해서 접근 가능한지 확인한다.
invalid하다면 illegal하므로 trap 발생
 
[ Shared Pages ]
Read Only인 DLL의 경우, 매 번 각자의  address space에 복사해서 load한다면 낭비가될 수 있다.
중복되는 코드부분은 공유될 수 있다.
Physical Memory에 하나만 적재하고 논리적으로 copy해서 쓴다면 읽기만 하므로 멀티스레드 환경에서 유리함
 
[ Structuring the Page Table ]
Logical address space가 커져서 Page Table의 크기가 너무 크다면,
 
1) Hierarchical Paging
페이지 테이블에 대한 페이지 테이블을 만들자
 
2) Hashed Page Tables
Page Table이 아니라 Hash Table을 이용해서 Physical memory에 접근 해보자
 
3) Inverted Page Tables
프로세스에 대해 어떤 페이지인지 역으로 저장
→ pid에 대해 p와 d를 얻어 physical memory에 접근
 
 
[ Swapping ]
Physical memory보다 훨씬 큰 메모리도 존재 가능하지 않을까?
→ 동시에 실행할 수 있는 프로그램이 증가 함
 
현재 필요한 page만 불러들였다가, 필요없어지면 다시 메모리 밖(out of memory, SSD or HardDisk)으로 내보낸다
→ Swap in, Swap out : Swapping
 
Page 하나의 크기는 작으므로 Page단위로 Swapping을 하면 부담이 적어진다.
오늘날의 Paging은 Swapping을 가정하므로 Swap in, Swap out을 Page in, Page out으로 부른다.
 
Paging은 Virtual Memory와 매우 잘 맞음.