[OS 기초] Demanding Paging

# Demanding Paging

: 메모리 관리 매커니즘(MMU 매커니즘)을 사용해서 여러 프로세스가 시스템 메모리를 효율적으로 공유할 수 있도록 하는 기술

: 어떤 프로세스가 수행될 때, 집중되는 page들을 필요할 때 읽어들이기.

: 페이지가 요구될 때, 메모리에 불러오는 정책

* Principle of Locality(Locality of Reference)

: 프로그램이 가장 최근에 접근했던 데이터를 다시 접근하거나(Temporal Locality), 

최근에 참조했던 데이터 근처의 주소를 참조하는 경향이 있음(Spatial Locality)

* 90/10 Rule

: 불과 10%의 코드가 프로그램 총 수행시간의 90%를 차지함. (loop)

* Swap Device

: Physical Memory에 저장되지 못한 Page들을 저장하는 디스크의 공간

: 저장 단위인 file은 I/O시에 OS의 여러 기능이 동작해야하므로 굉장히 느리기 떄문에 File과 별도로 direct access가 가능한 low disk block.

: swap device가 가득찬 경우는 file을 swap 영역으로 사용할 수 있음

> Demand Paging의 Policy

: Physical Memory와 Swap Device 사이의 데이터 전송을 최소한으로 발생하도록 함

* Memory Access Latency

레지스터(1 사이클) < L1 캐시(수 사이클) < L2 캐시(수십 사이클) < Main Memory(수백 사이클) < Disk (수백만 사이클)

* Thrashing 

: 프로세스들이 사용하는 페이지들의 크기보다 사용이 가능한 물리 메모리의 크기가 작을 때, 사용하려고 swap-in하는 페이지들에 의해 앞으로 사용할 페이지가 swap-out되면서 반복적으로 Page Fault가 발생하는 현상

> page table entry가 virtual memory management를 지원하려면,

target 주소가 ram이 아닐때를 구분할 수 있는 flag가 필요. 

* Resident Bit 

: 대상 페이지가 물리 메모리에 있는지, 스왑디바이스에 있는지 구별해주는 플래그

> Virtual Memory 사용의 key!

: 값싼 Disk를 사용하여 비싼 메모리를 사용하는 것처럼 구현하여 사용하자.

> Demanding Paging 구현의 기술적 이슈

- Page Fault :  virtual address가 가리키는 page가 physical memory에 없어서 프로세그가 더 이상 진행할 수 없는 상태를 OS에게 알려주는 일종의 소프트웨어 인터럽트

* page fault handler : 인터럽트 서비스 루틴을 수행

<Page Fault Handling>

1. DMA Controller에게 해당 페이지의 주소를 전달

2. DMA Controller는 해당 페이지를 physical memory로 로드

3. DMA Controller의 작업이 끝나면 인터럽트 발생

4. OS는 page fault를 일으킨 프로세스의 수행을 재개

> Page Fault Handling이 다른 인터럽트 처리보다 어려운 경우

: 인터럽트는 수행중인 instruction에 의해 변화된 상태를 되돌렸다가 page fault 처리가 끝난 후 해당 instruction을 재개해야하기 때문

=> page fault 모든 수행에 일어날 수 있으므로 instruction 재개가 굉장히 어렵기 때문에 에외적으로 처리하게 됨 (virtual memory를 지원하기가 어려움)

* MOVE (SP)+, -(R2)

: SP가 가리키는 메모리 location의 값을 R2의 값을 하나 감소시킨후 copy하라.

* VAX의 경우는 애초부터 virtual memory를 지원하도록 설계하였는데 

CISC Instructiond은 restart가 어렵기 때문에 마이크로 코드로 다시 프로그램되어있으므로 마이크로 코드로 리버스 시킴(페이지폴트 발생시 인스트럭션 수행중의 변화시켰던 모든 레지스터 state를 복구하고 핸들링이 끝나면 다시 이전의 instruction이 restart되도록)

* 요즘은 RISC 방식으로 구현되며, RISC는 restartable하게 구현

> 정리

과거에는 프로그램이 수행될 떄, 프로그램과 관련한 모든 메모리가 전부 물리메모리에 있어야 하므로 비싼 메모리의 가격이 문제가 되었음.

비싼 메모리를 줄이고 싼 디스크를 swap device로 사용하는 virtual memory management라는 기술이 발전하였음.

Virual Memory Management는 virtual memory address를 physical memory address로 전환해주는 하드웨어인 MMU의 지원이 꼭 필요함

> HW 트렌드가 변화되면서 여러가지 대응해야 할 이슈

swap device를 쓸 수 없는 과거상황으로 돌아가는 경우

"스마트폰" 디스크가 없고  solid state disk(flash memory)를 secondary disk로 사용

flash memory는 ROM으로 Erase횟수가 제한이 있으므로 swap device로 사용할 경우 수명이 급격히 줄어들게 됨

> Demanding Paging은 페이지가 요구될 때 메모리에서 불러오므로 페이지가 요구되는 시점에 ram regident하지 않고 그 때 요청을 하게되면 page fault가 발생할 수 있으며 속도가 매우 느려질 수 있음 => 미리 예측하는 policy를 갖도록 하자!

* 이상적인 Page Selection Policies

:  앞으로 사용될 페이지를 미리 메인메모리로 가져와서 페이지 폴트가 발생하지 않도록 하는 방법

1. Demand paging : 

- pure demanding paging

- 프로세스가 시작할 때 메모리에 0개의 페이지로 시작하며, 엔트리 포인트에 들어갈 때 처음 인스트럭션부터 page fault가 발생하여 초반부에 엄청난 page fault가 일어나게 됨. 이후 충분한 페이지를 잡으면 원활하게 프로세스가 동작하게 됨.

- 가장 단순하지만, 프로세스가 생성되서 시작을 할 때 너무 오랜 시간이 소요됨.

2. Prepaging : 앞으로 사용될 페이지를 예측해서 미리 Main Memory로 로드하는 방법

- 한페이가 요청되면 인접한 페이지까지 로드

   => 효과적인 prepaging 방안 : Spatial Locality에 기반하여 page fault가 발생한 근처에 있는 페이지들을 Main Memory에 로드

3. Request Paging : 논리적으로 연관성이 있는 페이지들을 미리 Main Memory에 로드

- 과거에 사용했던 기법

- 예. Overay

=> 사용자가 결정해서 사용해야하는 불편함이 있음.

=> Working Set 대두!

> 여러가지 관점

1. 어떤 페이지를 언제 물리메모리로 불러올 것인지. Page selection policy

2. 스와핑 대상을 고르기. Page replacement policy

3. replacement를 수행할 때, 전체 프로세스들 중에서 고를지, 특정 그룹의 프로세스들에서 고를지. Page replacement style

4. page들을 어떤프로세스에게 page frame을 할당할때. Page placement style