[OS] 10. 가상 메모리 관리 - Replacement Strategies for Variable Allocation

Replacement Strategies

Variable allocation

• WS(Working Set) algorithm
• PFF(Page Fault Frequency) algorithm
• VMIN(Variable MIN) algorithm

 

Working Set (WS) algorithm

Denning이 1968년에 제안한 알고리즘

 

Working Set

• 지금 일할 때 필요한 집합
• 즉, Process가 특정 시점에 자주 참조하는(Locality반영) page들의 집합
• 최근 일정시간 동안(Δ(델타)) 참조된 page들의 집합
• 시간에 따라 변함
• W (t, Δ)
  • The working set of a process at time t
  • Time Interval [t - 델타, t] 동안 참조된 page들의 집합
  • Δ : Window size, System parameter

현재시간(t) 부터 t-Δ 를 묶어서 집합을 만든다.

이 집합을 메모리에 유지한다.

t부터 t-Δ까지의 영역을 window라고 부른다.

윈도우안의 참조한 페이지들을 유지하는 것 => working set 알고리즘

 

윈도우는 시간에 지남에 따라 변경이 될 것이고 안의 페이지들의 내용도 바뀐다.

(최소 1개 페이지, 최대 Δ+1개 페이지를 가지고 있다)

 

Working set memory management

• Locality에 기반을 둠
• Working set을 메모리에 항상 유지시킴
• page fault rate(trashing)감소함
• 시스템 성능이 증가함
• Window size(Δ)는 고정됨
  • Momory allocation은 가변
  • Δ(윈도우 사이즈) 값이 성능을 결정 짓는 중요한 요소

 

Window size VS Working Set size

어느 구간을 볼 것인가 ? VS 메모리 유지되는 사이즈(Memory allocation)

어떤 관계를 가질까?

처음에는 윈도우 사이즈를 조금 늘리면 워킹 셋 사이즈가 급격하게 늘어난다.

어느 구간에 돌입하면 완화

window사이즈가 어느 구간에 도달하게 되면 working set사이즈가 크게 커지지 않는다. 

이러한 경향을 보이는 이유는 Locality 때문이다.

프로그램들은 Locality를 가지고 있기 때문에 window size를 늘리면 급격하게 working set이 늘어남.

그런데 점차 윈도우 사이즈를 늘려도 보는 페이지는 한정적이기 때문에 크게 증가하지 않는 것..

(설명 보충 필요..)

 

Working Set Transition

루프가 3개 있다고 가정한다.

loop1은 working set은 2, loop2에 돌입하면 ws는 3개 마지막은 2개 라는 것을 예상할 수 있다.

loop1에서 2로 전환할 때 ws 사이즈는 증가할 것이다.

이 그래프는 해당 loop에서의 ws size를 그래프로 나타낸 것이다. 

이런 현상이 일어나는 것을 working set transition 이라하고 

working set transition 될 때 일시적으로 페이지 프레임 수 (메모리 할당 수) 가 증가하는 것을 확인할 수 있다.

 

WS 알고리즘을 살펴보자

Example

Δ=3, number of pages = 5 (0,1,2,3,4)

time=0일때 처음 페이지는 {0,3,4}

w(오메가) = 2 2 3 1 2 4 2 4 0 3

 

Time = 1일 때

[t-delta, t] 이므로 [1-3,1] = [-2,1]이다. 

즉, -2와 1사이에서 본 값들을 메모리에 저장한다. (T=1에서 0 - 2 3 4 확인)

이때, WS size = 4

 

Time = 2,

윈도우 상에 참고할 페이지는 3, 0 ,2 이므로 메모리에 올라간 page 4를 메모리에서 제외한다.

메모리에는 0, 2, 3 이 유지되어 있음

 

T=3,

이번에는 윈도우에서 참고할 페이지는 0,2,3 이기 때문에 메모리에 0, 2, 3 페이지가 올라가 있음

 

T = 4 면

제일마지막에 참고한 0을 메모리에서 제외하고 필요한 1페이지(2, 3, 1)를 메모리에 넣는다. 

 

T=6,

윈도우에 참고할 페이지가 1,2,3,4 이므로 메모리에 1,2,3,4 가 들어간 것을 확인 할 수 있다. 

 

즉, 윈도우를 통해 볼 수 있는 페이지들만 메모리에 유지 한다 (of frames allocated가 수시로 변함)

=> Working Set 알고리즘

 

성능평가(알고리즘이 잘 동작했는가)

• page fault가 5번 일어났다. 과연 좋은 알고리즘인가 쉽게 확인하기 어렵다.
• variable allocation system에서 page fault수 외 다른 지표도 살펴보고 판단해야 한다.
• 평균적으로 page frame을 몇개 가지고 있었는가, page fault을 처리하는 비용, page frame을 유지하는 비용을 알고 있어야 알고리즘의 성능을 평가 할 수 있다. 

 

Example)

• Time interval[1,10]
  • # of page fault = 5
  • 평균할당 page fram 수 = 3.2
• 평가: 평균 3.2개의 page frame을 할당 받은 상태에서 5번의 page frault발생

 

특성

• 적재되는 page가 없더라도, 메모리를 반납하는 page가 있을 수 있음
• 새로 적재되는 page가 있더라도, 교체되는 page가 없을 수 있음.

단점

• 윈도우를 지속적으로 보아야 함 => Working Set management overhead발생
• Residence set(상주 집합)을 page fault가 없더라도 지속적으로 관리해야 함.

 Mean number of frames allocated VS page fault rate

할당하는 윈도우 사이즈 VS page들의 life time(page fault rate)의 관계

WS size가 커질수록 lifetime이 길어지는데 이는 페이지 유지 비용의 증가를 의미한다. (마냥 크다고 좋은것이 아니다)

즉, window size, working set size를 적당히 만들어야 한다. 

Locality를 유지하기 위해 계속 지켜봐야한다 (Overhead가 발생) 단점이 있다.

 

이를 해결하는 방법이 제시됨

Page Fault Frequency (PFF) algorithm

Residence set size를 page fault rate에 따라 결정함.

• (WS에서는 page fault가 없어도 관리하였음 그러나 PFF는 page fault가 나면 관리를 한다)
• page fault가 잘 일어나지 않는다면 (long inter-fault time) 메모리를 줄인다.
  • process에게 할당된 PF수를 감소시킨다.
• page fault가 자주일어난다면 (short inter-fault time) 
  • Process에게 할당된 PF수를 증가시킨다. 

Resident set 갱신 및 메모리 할당

• page fault가 발생시에만 수행
• Low overhead

page fault 가 자주 발생하면 메모리를 더 주고, 그렇지 않으면 메모리를 회수하면 효율적으로 관리할 수 있다.

이때 page fault의 자주발생하는 기준은 다음과 같다.

 

Criteria for page fault rate

IFT > 𝜏: Low page fault rate (page fault 시간이 타우보다 짧다면 자주일어나지않음)
IFT < 𝜏: High page fault rate (page fault 시간이 타우보다 크다면 자주남)

𝜏: threshold value

 

스케쥴링은 다음과 같은상황에 발생됨

1) page fault 발생시, IFT계산

• IFT = t_c - t_c-1 (지금 page fault 일어난 시간 - 직전 page fault가 일어난 시간)

2) IFT >𝜏 (Low page fault rate)

• Residence set => (t_c-1, t_c] 동안 참조 된 page들만 메모리에 유지함
• 나머지 page들은 메모리에서 내림 (메모리할당 (#of page frames) 유지 or 감소)

3) IFT ≤𝜏 (High page fault rate)

• 기존 pages들 유지
• + 현재 참조된 page를 추가 적재 (메모리 할당(#of page frames)증가)

Example

• 𝜏=2, number of pages = 5 (0, 1, 2, 3,
• Initially pages {0, 3, 4} in the memory at time 0
• w = 2 2 3 1 2 4 2 4 0 3

 

page fault 가 일어났을 때 PFF 알고리즘 작동함

 

T = 1

IFT = 1-0 = 1, 𝜏=2 (𝜏>1) 이므로 page fault 가 자주 일어난다고 볼 수 있다. 

이때 page 수를 추가한다.

 

T = 4

IFT = 4-1 = 3 , 3>𝜏 이므로, page fault가 일어났고 low page fault rate이므로 페이지 수 없앤다.

(1,4] ​에 있는 페이지만 유지하게 된다.

0, 4가 메모리에서 제외된다.

 

T = 6

IFT = 6-4 = 2 = 𝜏 이므로 high fault rate이다.

 

T = 9

IFT = 9-6 = 3 > 𝜏, low page fault rate이므로 페이지 수 없앤다.

(6, 9]에서 유지된 페이지들만 메모리에 적재하고 나머지는 전부 없앤다. 

 

성능평가

• Page fault 수 외 다른 지표도 함께 봐야 함
• Example
  • Time interval [1, 10]
    • #of page fault = 5
    • 평균 할당 page frame 수 = 3.7
  • 평가: 평균 3.7개의 page frame을 할당 받은 상태에서 5번의 page fault 발생

특징

• 메모리 상태 변화가 page fault 발생시에만 변함 => Low overhead

Variable MIN (VMIN) algorithm

Variable allocation 기반 교체 기법 중 optimal algorithm

=> 평균 메모리 할당량과 page fault 발생 횟수 모두 고려했을 때의 Optiomal

• 실현 불가능한 기법(Unrealizable) : page reference string을 미리 알고 있어야 함

기법: [t, t+Δ]을 고려해서 교체할 page선택 (미래를 보고 결정)

 

Algorithm

• page r이 t 시간에 참조 되면, page r이 (t, t+Δ] 사이에 다시 참조되는지 확인
• 참조 된다면, page r을 유지
• 참조 안 된다면, page r을 메모리에서 내림

Example 

Δ=4, number of pages = 5 (0, 1, 2, 3,
w = 2 2 3 1 2 4 2 4 0 3

 

T = 0

(t, t+Δ] = (0,0+4] 이므로 page3은 t=3일때까지 참조하므로 유지한다. 

 

T = 1

(1,5] 에서 page 2를 참조하므로 유지한다. 

 

T = 2

(2,6]에서 page 2를 참조하므로 유지

 

T = 3

(3,7]사이에 page 3을 참조하지 않으므로 유지하지 않음

 

T = 4 이후에도 앞의 방법과 마찬가지로 알고리즘이 동작함.

 

성능평가

• page fault 수외 다른 지표도 함께 봐야함
• Example
  • Time interval [1,10]
    • #of page fault = 5
    • 평균 할당 page frame 수 = 1.6
    • 평가: 평균 1.6개의 page frame을 할당 받은 상태에서 5번의 page fault 발생

최적 성능을 위한 Δ 값은?

Δ = R / U

• U: 한번의 참조 시간 동안 page를 메모리에 유지하는 비용
• R: page fault 발생 시 처리 비용

R > Δ * U, (Δ 가 작으면) : 처리비용 > page 유지 비용

R < Δ * U, (Δ 가 크면) : page fault 처리 비용 < 유지 비용

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---