메모리 관리_Demand paging, Page replacement algorithms(FCFS, LRU, LRU Approximation(NRU), LFU, MFU)

Paging

 

Paging은 logical memory를 physical memory로 mapping 하는 여러 방법 중 하나입니다.

Logical memory를 같은 크기의 page로, physical memory를 page와 같은 크기의 frame으로 나눈 뒤 page를 특정 frame에 할당하여 이를 page table에 기록합니다. Page table의 크기는 매우 커서 main memory에 저장 해야 하는데, CPU가 명령을 수행할 때마다 메모리에 접근하기에는 overhead가 크므로 TLB(일종의 캐시)에 자주 참조될 것으로 예상되는 page에 대한 정보를 저장하여 사용합니다.

 

(Paging에 대한 자세한 설명을 읽어보고 싶으신 분은 여기로)

 

 

 

Demand Paging

그렇다면, 프로그램이 로드되어 프로세스가 만들어지자마자 logical memory의 모든 page가 physical memory에 할당되는 것일까요? 

그렇지 않습니다. 처음 프로세스가 만들어질 때는 logical memory와 page table만 만들어지고, 모든 데이터는 physical memory가 아닌 disk에 저장되어 있습니다.

 

 

CPU에서 특정 page를 참조하라는 명령이 수행되면, 제일 먼저 TLB에 page에 대한 frame number 정보가 있는지 확인합니다. Context switching이 일어날 때마다 TLB는 초기화 되므로 TLB는 텅텅 비어있을 것이고, TLB hit는 발생하지 않을 것입니다. 

이후, MMU는 page table에서 page의 frame number와 valid bit를 확인합니다. 모든 데이터는 disk에 존재하고, 아직 physical memory에 할당 되지 않았으므로 valid bit = 0이 되어 CPU는 self interrupt를 발생시킵니다. 운영체제는 interrupt를 분석하여 아, 아직 page가 physical memory에 할당되지 않았구나! 하고 page fault 상태를 알아냅니다. 운영체제는 disk에 있는 page를 free-frame(아직 사용되고 있지 않는 frame)에 올리고 page table의 valid bit 상태를 1로 수정합니다.

 

즉, Demand paging은 특정 page가 참조될 때(필요해질 때) page를 disk에서 free-frame으로 올리고, free-frame의 수가 부족해질 때 frame에서 disk로 내리는 방식으로, page-level의 swap이 일어납니다. 또한, Main memory는 disk의 cache 형태로 사용되게 됩니다.

 

 

Demand paging에서의 메모리 참조

Demand paging에서 일어나는 모든 메모리 참조 과정을 정리해보면,

 

 

1) TLB hit가 발생하는 경우: TLB에 page에 대한 frame number 정보가 있으면 바로 메모리에 접근합니다.

2) TLB miss가 발생하였으나, Page table에 frame number에 대한 정보가 있고 valid bit = 1 인 경우: PTE(Page Table Entry)를 TLB로 올립니다.

3) TLB miss가 발생하였고, Page table의 valid bit = 0 인 경우: CPU는 self interrupt를 발생시키고, 운영체제는 해당 interrupt가 protection fault인지, page fault인지 확인합니다. Protection fault라면 해당 프로세스를 종료시킵니다. Page fault라면 disk에 있는 page를 free-frame으로 올린 후 Page table의 valide bit를 1로 변경합니다.

 

 

 

Locality

Demanding page가 가능한 이유는 다음과 같은 locality에 있습니다.

 

1) Temporal locality: 최근에 참조된 데이터는 다시 참조될 가능성이 높습니다.

2) Spatial locality: 참조된 데이터의 인근 영역에 있는 데이터는 참조될 가능성이 높습니다.

 

만약, 명령어가 매번 새로운 page를 참조한다고 생각해본다면, 제한된 physical memory 내에서 계속 swap이 일어날 것이고, cpu utilization이 떨어질 것입니다. 현 운영체제에서 Demand paging을 유용하게 사용할 수 있는 이유는, 한번 참조된 메모리가 계속해서 참조되는 locality 특성 때문입니다.

 

 

 

Page replacement  Algorithms

Page fault가 발생했을 때, 운영체제는 disk에 있는 page를 physical memory로 로드시켜야 합니다. 그런데, 프로세스가 할당 받은 physical memory를 모두 사용하였다면, frame을 사용하고 있는 page 중 일부를 디스크로 내리고 새로운 page를 로드시켜야 합니다. 이를 Page replacement라고 하며, 어떠한 page를 내릴지 결정하는 알고리즘을 page replacement algorithms이라고 합니다.

 

Page replacement algorithm의 목표는 앞으로 발생할 page fault를 최소화 시키는 것입니다. 이를 위해서는 미래에 참조되지 않을 page를 내려야 하는데, 미래를 정확히 예측하는 것은 불가능 합니다. 따라서 time locality 개념을 활용하여 현재 시점으로 부터 가장 오래전에 사용된 page를 disk에서 내리게 됩니다.

 

그럼 하나씩 page replacement 알고리즘을 살펴보도록 하겠습니다.

 

 

FCFS

가장 오래전에 page-in 된 page를 victim으로 선정하는 방식입니다.

개념은 간단하나, Belady's Anomaly를 통해 나쁜 성능이 증명되었습니다. 일반적으로는 프로세스에 할당되는 frame 수가 증가하면, page fault의 발생 빈도가 낮아지는데, FIFO를 사용하는 경우 frame 수가 증가하여도 page fault가 증가하는 결과가 발견되었습니다.

 

 

LRU(Least Recently Used)

가장 최근에 사용되지 않은(가장 오래전에 참조된) page를 victim으로 선정하는 방식입니다.

 

 

1) Timestamp implementation

CPU에 clock register를 추가하고, 메모리(page)에 접근할 때마다 counter를 1 증가시켜 해당 값을 page table의 사용 시간 field에 복사하는 방식입니다. Page replacement가 일어날 때마다 Page table을 순회하여 clock 값이 가장 낮은 것을 victim으로 선정합니다.

 

 

2) Stack implementation

가장 최근에 참조된 page number가 stack의 top에 오도록 참조 순서를 기록하는 방식입니다. Page replacement가 일어날 때마다 stack의 가장 아래쪽에 있는 page를 victim으로 선정합니다. 

 

 

LRU Approximation algorithms

Timestamp와 Stack 구현 방식은 가장 간단하지만 overhead가 커 실제로 사용하지 않습니다. 대신, reference bit를 사용하여 특정 시점에서의 참조 여부를 표현합니다.

1) Reference bit가 0인 page를 victim으로 설정하기

Page table의 각 entry는 reference bit를 가지며, 이는 0으로 초기화 됩니다. 특정 Page가 참조되면 해당 page의 reference bit는 1로 변경되고, reference bit는 특정 주기마다 초기화됩니다. 즉, reference bit를 통해 주기별로 참조 여부를 기록하고, page replacement가 일어날 때마다 reference bit가 0인(최근에 참조가 되지 않은) page를 victim으로 선정할 수 있습니다.

 

그러나, 최신의 reference bit만 사용하면, reference bit가 0인 page들 중에서 어떤 것이 비교적 최근에 참조되었고 자주 참조되었는지 구분하기 어렵습니다. 이러한 문제는 Additional-Reference bits algorithm과 Second chance algorithm을 통해 보완할 수 있습니다.

 

 

2) Additional-Reference bits algorithm

Page 당 8 bit 크기의 reference bit를 사용하여 8개 주기에서의 참조 여부를 기록하는 방식입니다. 일정 주기마다 refernece bit을 오른쪽으로 shift 연산하고, 가장 왼쪽 비트에 가장 최근 시점의 참조 여부를 표기합니다. Reference bits의 정수값이 클 수록 최근에 접근 된 것이기 때문에, reference bits의 값이 가장 작은 page를 victim으로 선정합니다.

 

 

3) Second chance algorithm

FIFO를 기반으로 page를 순회하며, referece bit를 확인합니다. Reference bit가 1이라면 이를 0으로 바꾼 뒤 한번 더 기회를 주고 다른 victim을 찾습니다. 최초로 reference bit가 0인 page를 만났을 때 이를 victim으로 선정합니다.

 

 

4) NRU(Not Recently Used, Enhanced Second chance algorithm)

Page의 상태를 R(reference bit)와 M(modify bit)의 조합으로 나타내며, 

 

Class 0 (R = 0, M = 0)

Class 1 (R = 0, M = 1)

Class 2 (R = 1, M = 0)

Class 3 (R = 1, M = 1)

 

의 우선순위에 따라 먼저 victim으로 선정됩니다. Reference bit는 주기마다 초기화 되지만, Modify bit는 한번 1로 변경되면 값이 바뀌지 않습니다. 따라서 Modify bit는 값이 1이더라도 page에 값을 썼던 시점이 아주 오래 되었을 수도 있기 때문에 현재의 주기에서의 참조가 보장된 Class 2번을 Class 1번보다 늦게 victim으로 선정합니다.

 

LFU(Least Frequently Used)

가장 접근 횟수가 적은 page를 victim으로 선정하는 방식입니다.

 

MFU(Most Frequently Used)

가장 접근 횟수가 많은 page를 victim으로 선정하는 방식입니다.

 

 

 

Page replacement 유형

Page replacement는 대상 범위에 따라 두가지 방식으로 구분할 수 있으며 현재는 Local replacement를 사용합니다.

 

1) Global replacement: physical memory의 전체 frame을 대상으로 replacement를 수행하는 방식입니다.

2) Local replacement: 프로세스에 할당된 frame들을 대상으로 replacement를 수행하는 방식입니다. Frame들은 다음과 같은 3가지 기준으로 프로세스에게 할당 될 수 있습니다.

* Equal allocation: 모든 프로세스에게 동일하게 frame을 할당하는 방식

* Proportional allocation: 프로세스의 크기가 클수록 더 많은 frame을 할당하는 방식

* Priority-based allocation: 프로세스의 우선순위가 높을 수록 더 많은 frame을 할당하는 방식

 

 

 

Thrashing

일반적으로, 프로세스의 개수가 증가하면 cpu utilization은 높아집니다. 그러나, 프로세스의 수가 과도하게 많아지면 특정 시간 동안 필요한 총 메모리의 크기가 physical memory 크기보다 커지게 됩니다. 결과적으로 Page fault와 replacement가 빈번하게 발생하여 cpu utilization이 떨어지는데, 이를 Thrashing이라고 합니다.

 

 

I/O Interlock

Physical memory의 특정 영역이 pager replacement로 swap-out 않도록 막아놓는 것을 말합니다. 일반적으로 DMA(Direct Memory Access)를 위해 사용되는 메모리들을 잠굴 때 사용합니다.