교체 기법(OS)

Replacement strategies

한 프로세스의 메모리 공간이 다 차있는 경우 어떻게 교체해야 하는가 ?

• Fiexed allocation
• Variable allocation

Locality

• 프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상
• 가정

  • PagingSystem, Pagesize=1000words(1000줄), Machine instruction size = 1word, 주소 지정은 word단위, 프로그램은 4번 page에 coutiguous allocation 됨, n = 1000
    
  • 참조하는 페이지는 4 6 7 8 9 페이지 총 5개 페이지만 참조한다 ➡ 지역성

📌 Fiexed allocation

각 프로세스에게 고정된 Pageframe(메모리상의 공간)을 할당

Min Algorithm (OPT algorithm)

• Minimize page fault frequency (Optimal) (증명됨.proved)
  • 페이지 폴트 수를 최소화
• 앞으로 가장 오랫동안 참조되지 않을 page를 교체(Tie-breaking rule: page 번호가 가장 큰/작은 페이지 교체)
  • 어떤 페이지를 읽을 지 확정할 수 없음(Page reference string을 미리 알아야함) ➡ 실현 불가능 기법
• 교체 기법의 성능 평가 도구로 사용됨(평가할때는 미리 알고 있기 때문에 최적의 기준)
• Example ➡ Notion

Random Algorithm

무작위로 교체할 page 할당

• Low overhead, No policy (오버헤드가 적고, 규칙이 없음)
• 성능 평가 도구

FIFO Algorithm

가장 오래된 page를 교체

• Page가 적재 된 시간을 기억하고 있어야 함
• 자주 사용되는 page가 교체될 가능성이 높음 ➡ 지역성 고려❌
• FIFO anomaly(Belay's anomaly) 이상현상 발생
  • FIFO 알고리즘의 경우 더 많은 page frame을 할당 받음에도 불구하고 page fault 수가 증가하는 경구가 있음
• Example ➡ Notion

✅ LRU(Least Recently Used) Algorithm

• 가장 오랫동안 참조되지 않은 page를 교체
• Page 참조 시 마다 시간을 기록해야 함
• Locality에 기반을 둔 교체 기법 (시간)
• MIN algorithm에 근접한 성능을 보여줌
• 실제로 가장 많이 활용되는 기법
• 단점
• 참조 시 마다 시간을 기록해야함 (Overhead)
  • 간소화된 정보 수집으로 해소(시간대신, 순서만 기록)
• Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault 수가 급격히 증가함
  • 예) loop를 위한 |Ref.string| = 4/할당된 page frame이 3개인 경우
    (3개 pf가 계속 page fault가 되버림)
  • Allocation 기법에서 해결 하면 됨. pf를 4개로 늘리면 됨

✅ LFU(Least Frequently Used) Algorithm

• 가장 참조 횟수가 적은 Page를 교체
• Page 참조 시 마다, 참조 횟수를 누적 시켜야 함
• Locality 활용, LRU 대비 적은 overhead
• 단점
  • 최근 적재된 참조될 가능성이 높은 page가 교체 될 가능성이 있음
  • 참조 횟수 누적에 따른 overhead
• Example ➡ Notion

✅ NUR(Not Used Recently) Algorithm

• LRU approximation scheme (LRU보다 적은 overhead로 비슷한 성능 달성 목적, LRU 간략화)
• Bit vector 사용
  • Reference bit vector(r), Update bit vector (m)
  • 주기적으로 r이 초기화가 됨
• 교체 순서
  1. (r, m) = (0, 0)
  2. (r, m) = (0, 1)
  3. (r, m) = (1, 0)
  4. (r, m) = (1, 1)
     ➡ 최근에 참조된 (r==1) 것은 2순위가 되고, m이 0인 경우를 가장 먼저 교체(업데이트가 된 것은 write-back이 필요하기 때문에)
• 단점
  • 최근 적재된 참조될 가능성이 높은 page가 교체 될 가능성이 있음
  • 참조 횟수 누적에 따른 overhead

Clock Algorithm (NUR 유사)

• IBM VM/370 OS
• Reference bit 사용함 (but 주기적인 초기화 없음)
• Page frame들을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 page 결정. 시침이 지나갈 때 초기화
• r = 0인 경우 교체 page로 결정
• r = 1인 경우, reference bit 초기화 후 pointer 이동
  ➡ FIFO와 유사하게 먼저 적재된 page가 교체될 가능성이 높음
• LRU, NUR 과 유사 (locality 사용)
• example ➡ notion

Second Chance Algorithm

• Clock algorithm과 유사
• Update bit(m) 도 함께 고려함 (but 주기적인 초기화 없음)
  • 현재 가리키고 있는 paged의 (r, m)을 확인
  • (0,0) : 교체 page로 결정
  • (0,1) : ➡ (0,0) 후 write-back(cleaning) list에 추가(요청) 후 이동
  • (1,0) : ➡ (0,0) 후 이동
  • (1,1) : ➡ (0,1) 후 이동

Other Alogrithms

• Additioinal-referrence-bits alogrithm
  • LRU 유사, 여러개의 reference bit를 가짐
• MRU (Most Recently Used) algorithm
  • LRU와 정반대 기법, 가장 최근에 참조된 페이지를 교체
• MFU(Most Frequently Used) algorithm
  • LFU와 정반대 기법, 참조가 가장 많은 페이지를 교체

📌 Variable allocation

Page frame 수가 가변적임

✅Working Set (WS) algorithm

• Process가 특정 시점에 자주 참조하는 page들의 집합 ➡ Locality
• 최근 일정 시간동안(Δ) 참조된 page들의 집합
• 시간에 따라 Working Set이 변함
• W(t,Δ)
  • t : 현재 시간
  • Δ : window size (window = 봐야하는)
  • [t-Δ ~ t] 시간(window) 동안 참조된 page들의 집합
• Working set을 메모리에 항상 유지
  • page fault rate(thrashing)이 감소 ➡ 시스템 성능 향상
• Window size(Δ)는 고정
  • Memory allocation은 가변
  • Δ 값이 성능을 결정 짓는 중요한 요소가 됨
• Locality 때문에 window size를 최대로 늘려도 working set사이즈는 적게 증가함
• Working set Transition
  • loop(ws)에서 loop(ws)로 전환될 때 일시적으로 Working set size가 증가함
    ws1과 ws2 둘 다 필요하기 때문에
• Example ➡ Notion
  • 현재 window size 만큼 볼 수 있는 페이지만 메모리에 유지 한다
• 성능 평가
  • Page fault 수 외 다른 지표도 함께 봐야 함
  • Example
    • Time interval [1, 10], 10초 동안
    • page fault 수 = 5, 평균 할당 page frame 수 = 3.2
  • 평가
    • 평균 3.2개의 page frame을 할당 받은 상태에서
      5번의 page fault 발생
• 특성
  • 적재되는 page가 없더라도 메모리를 반납하는 page가 있을 수 있음
  • 새로 적재 되는 page가 있더라도, 교체 되는 page가 없을 수 있음
• 단점
  • 지속적으로 관찰해야 함 ➡ Working set management overhead
  • Residence set(상주 집합)을 Page fault가 없더라도, 지속적으로 관리해야 함
• window size와 life-time(page fault rate)의 관계
  • window size가 커지면 life-time이 커지므로 page fault 확률이 올라감

✅Page Fault Frequency (PFF) algorithm

• Residence set size(메모리 유지 크기)를 page fault rate(발생 빈도)에 따라 결정
  • Low page fault rate (long inter-fault time)
    • Process에게 할당된 PF 수를 감소시킴
  • HIigh page fault rate (short inter-fault time)
    • Process에게 할당된 PF 수를 증가시킴
• Resident set 갱신 및 메모리 할당
  • Page fault가 발생시에만 수행한다 ➡ 오버헤드가 적음
• Criteria for page fault rate
  • IFT > τ : page fault rate가 낮다 (inter-fault time)
  • IFT <= τ : page fault rate가 높다.
  • τ : threshold value (기준), System parameter(우리가 정함)
• Algorithm
  1) Page fault 발생시, IFT를 계산 해준다.
  • IFT = 지금 pf 발생시간 - 전 pf 발생 시간
  2) IFT > τ (Low page fault rate)
  • Residence set ⬅ (직전시간 - 현재시간] 동안 참조 된 page들만 유지
  • 나머지 page들은 메모리에서 내림 ➡ 메모리할당 유지 or 감소
  3) IFT <= τ (High page fault rate)
  • 기존 pages들은 유지하고 현재 참조된 page를 추가 적재한다
    ➡ 메모리할당 증가
• Example ➡ Notion
• 특징
  • 메모리 상태 변화가 page fault발생 시에만 변하므로 오버헤드가 적음

✅Variable MIN (VMIN) algorithm

• Variable allocation 기반 교체 기법 중 optimal algorithm
  • 평균 메모리 할당량과 page fault 발생 횟수 모두 고려했을 때의 optimal
  • Variable allocation 기법의 성능 평가 도구
• 기법 : 현재시간 +Δ시간을 고려해서 교체할 page 선택
• Algorithm
  • Page r이 t 시간에 참조 되면, (t,t+Δ]시간 사이에 다시 참조되는지 확인
    ➡ 다시 참조 되면 page r을 유지, 참조 안되면 메모리에서 내림

---

https://youtu.be/EdTtGv9w2sA [Course] Operating System (CPA310) - 운영체제 강의. HPC Lab. KOREATEC