Paging

- 각 시스템의 각 프로세스 별로 페이지 테이블(page table)이 있음

=> 32bit 주소 공간에 4KB(2의 12승, 4096 => 4k) page와 4byte page-table entry 가 있다고 가정하면 페이지 테이블 크기는 2의 32승(주소공간) / 2의 12승(페이지 크기) x 4byte(페이지 테이블 엔트리) = 4MByte

=> 페이지 테이블의 크기가 너무 커서 메모리 공간을 많이 사용하는걸 볼수있다

===> 그렇다면? 페이지 테이블을 작게 설정해보면 어떨까?

페이지 크기를 늘려서 페이지 테이블 크기를 줄여보자

=> 32bit 주소 공간에  16KB(2의 14승, 16384 => 16k) page와  4byte page-table entry 가 있다고 가정하면 페이지 테이블 크기는 2의 32승(주소공간) / 2의 14승(페이지 크기) x 4byte(페이지 테이블 엔트리) = 1MByte

==> 그러나 크기가 큰 page는 내부 단편화(internal fragmentation)를 일으킬수있음

=> 다음 그림을 보면 대부분의 page table이 사용되고 있지않다(invalid)

Paging and Segments (Hybrid Approach)

: 메모리 오버헤드를 줄이기 위함

- Segmentation

: virtual address space를 segment로 나눔, 각 segment는 가변길이를 가짐

- Paging

: 정해진 크기의 page로 segment를 나눔, 각 segment는 page table을 가짐, 각 segment track은 base(물리주소), limit(해당 segment의 page table)

=> base는 segment를 point하는 것이 아닌, 해당 segment의 페이지 테이블의 물리적 주소를 나타넴, bounds 레지스터는 page table 의 끝을 나타냄

각 프로세스는 3개의 page table 이 있음

=> 프로세스가 실행될때, 세그먼트 각각의 base register는 해당 세그먼트에 대한 선형(linear) 페이지 테이블의 물리적 주소를 포함

TLB miss

- 하드웨어는 segment bit(SN)를 이용하여 사용할 base, bound pair를 구분함

- 하드웨어는 그후 물리주소를 가져와서 VPN과 합쳐서 PTE 주소를 만듬

=> 문제점 : 크기가 크지만 거의 사용하지않는 heap 공간이 있으면, 여전히 page tabe 낭비가 발생 -> external fragmentation(외부 단편화)

Multi-level Page Tables

- 페이지 테이블을 페이지 크기의 단위로 나눔

- 전체 페이지 테이블이 invalid 하면, 그 페이지 테이블을 allocate하지않음

- valid 여부를 알기위하여 page directory 사용

page directory는 다수의 PDE(page directory entries)로 구성, PDE는 valid bit와 page frame number(PFN)로 구성됨

장점: 오로지 사용 중인 주소 공간의 양에 비례하여 페이지 테이블 공간만 할당함, OS가 새로운 페이지 테이블을 할당하거나 확장하기 용이해짐

단점 : time-space trade-off, 복잡함

(추가중)

---------------------------------------------------------------------------------------------------------------------------------------

Swapping

- 물리적 메모리가 충분하지 않을 때 동시에 실행되는 많은 대용량 주소 공간 지원
- 메모리 계층구조에 추가 레벨이 필요
- OS에는 현재 수요가 많지 않은 주소 공간의 일부를 숨길 수 있는 공간이 필요함.
- 일반적으로 하드 디스크 드라이브가 이 역할을 수행

메모리 계층 구조 ( Memory Hierarchy )

각 레이어는 위 레이어의 '백업 저장소' 역할을 함

Swap하는 법

Overlays
- 프로그래머가 필요에 따라 코드나 데이터를 메모리 안팎으로 수동으로 이동함
- OS의 특별한 지원 필요 없음
Process-level swapping
- 프로세스가 일시적으로 메모리에서 백업 저장소로 스왑됨
- 나중에 계속 실행하기 위해 메모리로 다시 가져옴
Page-level swapping
- 메모리에서 백업 저장소로 페이지 스왑( swap-out )
- 백업 저장소에서 메모리로 페이지 스왑( swap-in )

Swap 위치
- swap space : 페이지를 앞뒤로 이동하기 위해 예약된 디스크 공간

=> - 페이지를 앞뒤로 이동할 수 있도록 디스크에 약간의 free 공간 확보
=> - OS는 페이지 단위로 스왑 공간을 기억해야함

- 스왑 공간의 크기에 따라 사용 가능한 최대 메모리 페이지 수가 결정
- 블록 크기는 페이지 크기와 동일
- 전용 파티션 또는 파일 시스템의 파일일 수 있음

프로세스를 위한 하나의 큰 주소
- 함수를 호출하거나 데이터에 액세스하기 전에 항상 코드나 데이터를 메모리에 먼저 준비해야 함
- 스왑 공간을 추가하면 OS가 동시에 실행되는 여러 프로세스를 위한 대형 가상 메모리처럼 보이도록 지원할 수 있음(단일 프로세스)

Present Bit

디스크와의 페이지 교환을 지원하기 위해 시스템 상단에 일부 하드웨어를 추가
- 하드웨어가 PTE를 살펴볼 때 페이지가 실제 메모리에 있는지 없는지 확인 가능

The Page Fault
- 실제 메모리에 없는 페이지에 액세스하는 경우

=>
- 페이지가 존재하지 않고 디스크가 스왑된 경우, 페이지 오류를 처리하기 위해 OS는 페이지를 메모리로 스왑해야 함
- page-fault handler 라고 하는 특정 코드가 실행되며 페이지 오류를 처리해야함

- 디스크 주소 페이지의 PFN과 같은 데이터에 사용되는 PTE

==> 메모리가 가득 찼다면??

- OS는 새로 들어올 페이지를 위한 공간을 확보하기 위해 페이지를 페이지 밖으로 내보냄
- 내보내거나 교체할 페이지를 선택하는 프로세스를 page-replacement policy 라고 함

Page Fault Control Flow – Hardware

Page Fault Control Flow – Software

- OS는 곧 오류가 발생할 페이지가 상주할 물리적 프레임을 찾아야함.
- 해당 페이지가 없는 경우 대체 알고리즘이 실행될 때까지 기다렸다가 일부 페이지를 메모리에서 제거

When Replacements Really Occur

- OS는 메모리가 완전히 가득 찰 때까지 기다렸다가 다른 페이지를 위한 공간을 확보하기 위해 페이지를 교체

- Swap Daemon, Page Daemon
- 사용 가능한 LW 페이지 수가 적을 경우 메모리 여유 공간 확보를 담당하는 백그라운드 스레드가 실행됨
- 이 스레드는 사용 가능한 HW 페이지가 있을 때까지 페이지를 비움

swap하는 것
- 커널 코드 → 스왑되지 않음
- 커널 데이터 → 스왑되지 않음
- 사용자 프로세스의 페이지 테이블 → 스왑되지 않음
- 사용자 프로세스의 커널 스택 → 스왑되지 않음
- 사용자 코드 페이지 → 삭제됨
- 사용자 데이터 페이지 → 삭제 또는 스왑됨
- 사용자 힙/스택 페이지 → 스왑됨
- 사용자 프로세스에 매핑된 파일 → 삭제 또는 파일로 이동
시스템
- 페이지 캐시 페이지 → 삭제 또는 파일 시스템으로 이동

=> Page replacement policy 에 따라 퇴거할 페이지 선택