운영체제 10. 가상 메모리 관리 (5) - Replacement Strategies for Variable Allocation

출처 : https://www.youtube.com/watch?v=ByQmerWj1bg&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=36

 

 

 

이번 시간에는 Variable allocation의 교체 기법들을 알아본다.

 

Variable allocation : 프로세스에게 할당해주는 메모리 공간의 크기가 가변적

 

 

Working Set (WS) algorithm

 

• 1968년 Denning이 제안
• Working set
  • Process가 특정 시점에 자주 참조되는 page들의 집합 -> locality
  • 최근 일정시간 동안(Δ) 참조된 page들의 집합
  • 시간에 따라 변함
  • W(t, Δ)
    • The working set of a process at time t
    • Time interval [t- Δ , t] 동안 참조된 page들의 집합
    • Δ : window size, system parameter

 

 

우리가 현재 시간이 t일 때, 특정 시점 t- Δ 부터 현재까지 참조한 page들을 묶어서 집합을 만들고, 해당 집합의 page들은 메모리에 유지한다.

우리가 바라봐야하는 영역,  t- Δ부터 t까지의 시간을 window라고 한다. window는 시간의 흐름에 따라 이동을 하게 되고, 그에따라 안에 있는 page들의 수도 변하게 된다.

 

window 안에는 최소 1개, 최대 Δ+1개(Δ 의 시간동안 참조하기 때문)의 page들이 참조될 수 있다. 

 

 

• Working set memory management
  • Locality에 기반을 둠
  • Working set을 메모리에 항상 유지
    • Page fault rate (thrashing) 감소. locality에 기반을 두었기 때문
    • 시스템 성능 향상
  • Window size(Δ)는 고정
    • Memory allocation은 가변
      • Memory Allocation이 고정 and Δ 가 가변이라면? = LRU 알고리즘 (MA : page frame 갯수는 고정, window 사이즈는 변함)
    • Δ 값이 성능을 결정 짓는 중요한 요소

 

 

• Window size( Δ )와 Working Set size(memory allocation)는 어떤 관계를 가지는가
  • window size가 증가하면 WS size도 증가한다. 더 큰 범위를 본다면 더 많은 page를 메모리에 유지하기 때문
  • 초반에는 window size를 조금만 늘려도 ws size가 급격히 증가하지만, 점점 증가하는 속도가 줄어들다가 어느 수준 이상이 되면 WS size가 커지지 않는 시점이 온다. 그래서 최대로 program size 만큼 유지가 된다.
  • 이런 흐름이 나타나는 이유는 locality 때문이다.

 

 

• Example : working set transition
  • loop는 총 3개가 존재한다.
  • loop-1 동안의 ws은 {p0, p1} 2개를 보고, loop-2 동안은 {p2, p3, p4} 3개, loop-3 동안은 {p6, p7} 2개를 본다.
  • 우리가 어떤 loop가 있다면, loop를 도는 동안 ws size는 얼마가 될 것인가. -> 증가한다.

 

 

• Working set transition 을 그래프로 나타내면 위 그림과 같다.
• WS-1, WS-2, ... 들을 loop-1, loop-2, ... 라고 했을 때, Working set이 loop에 필요한 만큼만 유지가 된다.
• loop에서 loop로 전환될 때, 일시적으로 할당된 page frame의 수(working set size)가 증가한다. 왜냐하면 넘어가는 동안 이전과 다음의 working set들이 둘 다 필요하기 때문
• 이 현상을 working set transition이라 한다.

 

 

• Working set 알고리즘 예시
  • window size Δ = 3, page의 수는 5개 (0, 1, 2, 3, 4)
  • 초기에 메모리에 담겨있는 page는 0, 3, 4 번 page
  • reference string ω = 2 2 3 1 2 4 2 4 0 3
  • Time 1 : [t- Δ , t] = [1-3, 1] = [-2, 1]에 봤던 page들을 memory에 유지시킨다. 그래서 working set은 0, 2, 3, 4번 page들 4개가 들어있게 된다.
  • Time 2 : [-1, 2]에 봤던 page들을 memory에 유지시킨다. 그래서 working set은 0, 2, 3번 page들 3개가 유지되고, page 4번은 메모리 밖으로 나오게 된다.
  • Time 3 : [0, 3]에 봤던 page들을 memory에 유지시킨다. 그래서 working set은 0, 2, 3번 page들 3개가 유지된다.
  • Time 4 : [1, 4]에 봤던 page들을 memory에 유지시킨다. 1번은 memory에 있지 않으므로 page fault가 발생하고 memory에 새롭게 적재된다. 그리고 page 0번은 밖으로 나오게 된다. 그래서 working set은 1, 2, 3번 page들 3개가 유지된다.
  • Time 5 : [2, 5]에 봤던 page들을 memory에 유지시킨다. 그래서 working set은 1, 2, 3번 page들 3개가 유지된다.
  • Time 6 : [3, 6]에 봤던 page들을 memory에 유지시킨다. 4번 page는 memory에 적재되어있지 않으므로 page fault가 발생하고 memory에 새롭게 적재된다. 그래서 working set은 1, 2, 3, 4 번 page들 4개가 유지된다.
  • Time 7 : [4, 7]에 봤던 page들을 memory에 유지시킨다. 3번 page는 memory 밖으로 나오게 된다. 그래서 working set은 1, 2, 4 번 page 3개가 유지된다.
  • Time 8 : [5, 8]에 봤던 page들을 memory에 유지시킨다. 1번 page는 memory 밖으로 나오게 된다. 그래서 working set은 2, 4 번 page 2개가 유지된다.
  • Time 9 : [6, 9]에 봤던 page들을 memory에 유지시킨다. 0번 page는 memory에 적재되어있지 않으므로 page fault가 발생하고 memory에 새롭게 적재된다. 그래서 working set은 0, 2, 4 번 page 3개가 유지된다.
  • Time 10 : [7, 10]에 봤던 page들을 memory에 유지시킨다. 3번 page는 memory에 적재되어있지 않으므로 page fault가 발생하고 memory에 새롭게 적재된다. 그래서 working set은 0, 2, 3, 4 번 page 4개가 유지된다.
  • 즉, working set size란 메모리에 할당된 memory frame의 수와 같다.

 

 

• Working set algorithm의 성능 평가
  • Page fault 수 외 다른 지표도 함께 봐야 함
  • Fixed allocation에서는 주어진 메모리 공간이 동일한 상태에서 page fault가 얼마나 적게 나왔는가를 판단기준으로 삼을 수 있다(다른 조건들이 동일하기 때문).
  • 하지만 variable allocation에서는 같은 알고리즘 일지라도할당하는 page 수에 따라 page fault가 다르다.
  • Example
    • Time interval [1, 10]
      • number of page fault = 5
      • 평균 할당 page frame 수 = 3.2
      • 따라서 page fault 수 뿐만 아니라 평균적으로 사용된 page frame의 수도 함께 봐야한다.
      • page fault를 처리하는 비용과 page를 memory에 유지하는 비용같은 정보들이 함께 주어져야 어떤 알고리즘이 더 좋은지를 판단할 수 있다.
    • 평가
      • 평균 3.2 개의 page frame을 할당 받은 상태에서 5번의 page fault가 발생

 

 

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

 

• 단점
  • Working set management overhead : 우리가 window를 이동시키면서 이전의 page들을 지속적으로 관찰하고 있어야 함
  • Residence set (상주 집합)을 page fault가 없더라도, 지속적으로 관리해야 함

 

 

• 할당된 window size와 page fault의 관계
  • window size가 크다는 뜻은 working set이 크다는 의미이다.
  • window size가 클수록, lifetime 또한 증가하게 된다. 하지만 그만큼 page 유지 비용이 증가하게 된다.
  • window size가 클수록, page fault rate는 감소하게 된다.
  • lifetime과 page fault rate는 상반되는 관계이다.
  • 따라서 우리는 window size를 적당한 크기로 만들어야 한다.

 

 

Page Fault Frequency (PFF) algorithm

 

working set 알고리즘의 overhead 문제를 해결하기 위해 page fault frequency 알고리즘이 등장한다.

• Page fault가 얼마나 자주 일어나는 지를 보고 메모리 할당을 변경하는 전략
• Residence set size를 page fault rate에 따라 결정
  • Low page fault rate (long inter-fault time)
    • Process에게 할당된 PF 수를 감소
  • High page fault rate (short inter-fault time)
    • Process에게 할당된 PF 수를 증가
  • 즉, page fault가 자주 일어나면 memory를 더주고, 안일어나면 memory를 뺏자
• Resident set 갱신 및 메모리 할당
  • Page fault가 발생시에만 수행
  • Low overhead

 

 

• Criteria for page fault rate 
  • IFT(Inter-Fault Time) > 𝜏 : Low page fault rate
  • IFT < 𝜏 : High page fault rate
  • 𝜏 : threshold value. page fault가 자주 일어나는가 아닌가에 대한 기준
    • System parameter

 

 

• Algorithm
  1. Page fault 발생 시, IFT 계산
     • IFT = t_c - t_c-1
       • _tc-1 : time of previous page fault. 이전에 page fault가 발생한 시간
       • _tc : time of current page fault. 현재 page fault가 발생한 시간
  2. IFT > 𝜏 (Low page fault rate) : page fault가 자주 일어나지 않음
     • Residence bit <- (t_c-1, t_c] 동안 참조된 page들 만 유지
     • 나머지 page들은 메모리에서 내림
       • 메모리 할당 (number of page frames) 유지 or 감소
  3. IFT ≤ 𝜏 (High page fault rate) : page fault가 자주 일어남
     • 기존 page들 유지
     • + 현재 참조된 page를 추가 적재
       • 메모리 할당 (number of page frames) 증가

 

 

• Example
  • 𝜏 = 2, 페이지의 수 = 5개 (0, 1, 2, 3, 4)
  • 최초에 메모리에 적재된 page는 0, 3, 4번 page
  • reference string ω = 2 2 3 1 2 4 2 4 0 3
  • Time 1 : page 2번을 적재해야되는데 memory에 적재되어있지 않아 page fault가 발생한다. 이전 시간 중 가장 최근에 page fault가 발생한 것은 time 0일 때 이므로, IFT = 1이된다. IFT ≤  𝜏 = High page fault rate이므로 원래 가지고 있던 page frame + 현재 새로운 page를 추가한다. memory에는 0, 2, 3, 4 번 page 4개가 적재되게 된다.
  • Time 2~3 : page 2, 3번은 이미 메모리에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 4 : page 1번을 적재해야하는데 memory에 적재되어있지 않아 page fault가 발생한다. 가장 최근에 page fault가 발생한 것은 time 1일 때 이므로, IFT = 4 - 1 = 3이 된다. IFT > 𝜏 = Low page fault rate이므로 메모리를 줄인다. 따라서 (1, 4]까지의 page만 적재하게 되어 메모리에는 1, 2, 3번 page 3개만 적재되게 된다.
  • Time 5 : page 2번은 이미 메모리에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 6 : page 4번을 적재해야하는데 memory에 적재되어있지 않아 page fault가 발생한다. 가장 최근에 page fault가 발생한 것은 time 4일 때 이므로, IFT = 6 - 4 = 2가 된다. IFT ≤ 𝜏 = High page fault rate이므로 메모리에 현재 page를 추가한다. memory에는 1, 2, 3, 4 번 page 4개가 적재된다.
  • Time 7 ~ 8 : page 2, 4 번은 이미 메모리에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 9 : page 0번을 적재해야하는데 memory에 적재되어있지 않아 page fault가 발생한다. 가장 최근에 page fault가 발생한 것은 time 6일 때 이므로, IFT = 9 - 6 = 3가 된다. IFT > 𝜏 = Low page fault rate이므로 메모리를 줄인다. (6, 9]까지의 page만 적재하게 되어 memory에는 0, 2, 4 번 page 3개가 적재된다.
  • Time 10 : page 3번을 적재해야하는데 memory에 적재되어있지 않아 page fault가 발생한다. 가장 최근에 page fault가 발생한 것은 time 9일 때 이므로, IFT = 10 - 9 = 1가 된다. IFT ≤ 𝜏 = High page fault rate이므로 메모리에 현재 page를 추가한다. memory에는 0, 2, 3, 4 번 page 4개가 적재된다.

 

 

• PFF 알고리즘의 성능 평가
  • Page fault 수 외 다른 지표도 함께 봐야 함
  • Example
    • Time interval [1, 10]
      • page fault의 수 = 5
      • 평균 할당 page frame 수 = 3.7
    • 평가
      • 평균 3.7개의 page frame을 할당 받은 상태에서 5번의 page fault 발생
      • 이전의 working set 알고리즘은 평균 3.2개의 page frame을 할당받은 상태에서 5번의 page fault가 발생했으므로 이번에는 working set 알고리즘이 좀 더 잘 동작했음
• 특징
  • 메모리 상태 변화가 page fault 발생 시에만 변함
    • working set 알고리즘보다 Low overhead

 

 

Variable MIN (VMIN) algorithm

 

• MIN 알고리즘처럼 optimal solution을 찾는 알고리즘
• Variable allocation 기반 교체 기법 중 optimal algorithm
  • 평균 메모리 할당량과 page fault 발생 횟수 모두 고려했을 때의 optimal
• 실현 불가능한 기법 (Unrealizable)
  • Page reference string을 미리 알고 있어야 함
  • 하지만 알고리즘 평가의 기준이 될 수 있음
• 기법
  • [t, t + Δ] 을 고려해서 교체할 page 선택

 

 

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

 

 

• VMIN 알고리즘 예시
  • Δ = 4, page의 수 = 5개 (0, 1, 2, 3, 4)
  • reference string ω = 2 2 3 1 2 4 2 4 0 3
  • Time 0 : page 3번이 참조된다. 현재 + 1부터 0 + 4 = Time 4까지 page 3번이 참조되는 것을 확인한다. Time 3에서 page 3번이 참조되므로 메모리에 적재한다.
  • Time 1 : page 2번이 참조된다. 현재 + 1부터 1 + 4 = Time 5까지 page 2번이 참조되는 것을 확인한다. Time 2에서 page 2번이 참조되므로 메모리에 적재한다.
  • Time 2 : Time (2, 6]까지 확인했을 때, Time 5에서 page 2를 참조하므로 메모리에 그대로 유지된다.
  • Time 3 : Time (3, 7]까지 확인했을 때, page 3번은 참조되지 않으므로 메모리에서 나온다.
  • Time 4 : Time (4, 8]까지 확인했을 때, page 1번은 참조되지 않으므로 메모리에 적재되자마자 나온다.
  • Time 5 : Time (5, 9]까지 확인했을 때, Time 7에서 page 2를 참조하므로 메모리에 그대로 유지된다.
  • Time 6 : Time (6, 10]까지 확인했을 때, Time 8에서 page 4를 참조하므로 메모리에 적재되게 된다.
  • Time 7 : Time (7, 10]까지 확인했을 때, page 2번은 참조되지 않으므로 메모리에서 나온다.
  • Time 8 : Time (8, 10]까지 확인했을 때, page 4번은 참조되지 않으므로 메모리에서 나온다.
  • Time 9 : Time (9, 10]까지 확인했을 때, page 0번은 참조되지 않으므로 메모리에 적재되자마자 나온다.
  • Time 10 : 맨마지막이므로 나오게 된다.
  • 평균적으로 유지하는 메모리의 수가 적어진 모습을 확인할 수 있다.

 

 

 

• VMIN 알고리즘 성능 평가
  • Page fault 수 외 다른 지표도 함께 봐야 함
  • Example
    • Time interval [1, 10]
      • page fault의 수 = 5
      • 평균 할당 page frame 수 = 1.6
    • 평가
      • 평균 1.6 개의 page frame을 할당받은 상태에서 5번의 page fault 발생
      • 이전 알고리즘들보다 동일한 page fault 수 + 더 적은 평균 할당 page frame 수를 가지므로 가장 우수한 성능을 보이는 것을 확인
  • 하지만 Window size( Δ )에 따라 성능이 달라질 수 있음. 그렇다면 Window size( Δ )를 얼마를 줘야 optimal이 될까?

 

 

• 최적 성능을 위한 Window size(Δ) 값은?
  • Δ = R / U
    • U : 한 번의 참조 시간 동안 page를 메모리에 유지하는 비용
    • R : page fault 발생 시 처리 비용
  • R > Δ * U, (Δ가 작으면)
    • page fault 처리 비용 > page 유지 비용
    • Window size(Δ)를 키우는 것이 유리
  • R < Δ * U, (Δ가 크면)
    • page fault 처리 비용 < page 유지 비용
    • Window size(Δ)를 줄이는 것이 유리