Virtual Memory(1)

Virtual Memory

: logical memory 와 physical memory를 분리

프로그램 실행을 위해서는 logical memory가 모두 physical memory에 올라와 있어야한다.

하지만 실제 주소 공간은 논리적 주소공간보다 작다.

효율적인 공간 사용을 위해 CPU 입장에서는 다 올린 것 처럼 보이도록 하고 실제로는 실행에 필요한 부분만 메모리에 올리는 방법이다.

 

Demand Paging

CPU가 접근하여 필요로 할 때 page를 memory에 올린다.

- I/O 발생이 줄어든다.

- 메모리 사용이 줄어든다.

- 응답 속도가 빨라진다.

 

vaild-invalid reference를 memory에 올리는 과정에 사용한다.

 

Lazy swapper

- page가 필요한 경우에만 swap을 한다. page를 다루기에 pager 이라고도 한다. 

 

Valid-Invalid Bit

Valid(v)

- 메모리에 있는 상태

Invalid

- illegal : 해당 프로세스의 주소 공간이 아닌 경우

- not-in-memory : 해당 페이지가 메모리에 업로드 되지 않은 경우

- obsolete : disk에서 업로드되었지만 실제 데이터가 updated 되어버린 경우

 

주소변환이 일어날 때 invalid 상태인 경우 "page fault" 라는 핸들러를 통해 다룬다.

valid-invalid bit 사용

Page Fault

invalid page에 대한 접근은 trap을 발생시킨다. (page fault trap)

 

[ page fault handler 처리 과정 ]

1. illegal reference인 경우 해당 프로세스를 중단한다.

2. memory에 없는 경우라면 빈 page frame을 찾는다. free frame이 없는 경우 replace 과정을 진행한다.

3. page를 해당 frame으로 읽어온다.

4. CPU가 프로세스에게 할당할 때 page fault trap은 종료된다.

5 . page fault를 발생시킨 명령어를 다시 재시작한다.

page fault 처리과정

Page replacement Algorithm

freeframe이 없는 경우 victim page를 선정하여 교체 과정을 진행해야 한다.

page fault를 최소화하여 replacement 과정이 이루어지도록 하는 것이 필요하다.

 

First-In-First-Out(FIFO) Algorithm

- frame에 먼저 들어온 순서대로 replace 과정을 진행하는 알고리즘이다.

- frame 개수가 늘어나는 경우 이론상 page fault가 줄어야 하지만 늘어나는 현상이 발생한다.(Belady's Anomaly)

FIFO Algorithm 예시

Optimal Algorithm

- 이론상 최적의 알고리즘으로 미래 예측이 가능해야한다. 실제로는 불가능하므로 다른 알고리즘 성능을 평가하기 위해 사용된다.

최적 알고리즘 예시

Least Recently Used Algorithm(LRU)

- 과거의 사용을 기반으로 미래를 예측한다는 의미

- 과거에 가장 적게 사용된 것은 미래에도 사용되지 않을것이라 판단하고 victim page로 선정한다.

- timestamp를 사용하여 각 page의 최근 사용시간을 확인하여 찾아낸다. -> timestamp(I/0) 와 최소값을 찾는 과정의 오버헤드가 크다!

LRU 예시

LRU Implementation Algorithms

: LRU의 timestamp 사용과 최솟값을 찾는 과정에 발생하는 오버헤드를 최소화하기 위해 사용하는 방식이다.

1) Counter implementation

- 정확한 시간은 필요없으니 상대적인 순서만 이용하기 위해 CPU counter를 사용하는 방식

2) Stack impementation

-double link 형식의 stack 구조를 사용하여 top에 최근 사용 page를 기록하는 방식 -> 자료구조 유지에 대한 오버헤드가 발생

 

LRU Approximation Algorithms

: 오버헤드를 최소화하며 LRU 처럼 동작하도록 하는 알고리즘

1) Reference bit

- 초기값을 0으로 설정하고 주기적으로 0으로 reset 해준다. (0인 경우 교체를 해준다.)

 

2) Additional-Reference-Bits Algorithm

- 주기적으로 오른쪽으로 한칸씩 이동해준다. bit 값이 큰 것이 사용이 많이 됨을 알 수 있다. -> 8비트 사용과 최솟값을 찾기 위한 오버헤드 발생

 

3) Second chance(clock) Algorithm

- 포인터를 사용하여 원형 큐를 사용한다.

- 포인터를 하나씩 이동하며 reference bit을 확인하고 1인 경우 0으로 바꾸고 0인 경우 replace를 한다.

- 기존의 자료구조,최솟값 찾는 알고리즘 등으로 인한 오버헤드가 사라진다.

- 원형구조로 사용되어 같은 reference bit가 0이어도 순서구분이 가능해진다.

clock 알고리즘 예시