[운영체제] 페이지 교체 알고리즘(FIFO, OPT, LRU), 쓰레싱, working set

운영체제 관련 글 순서

- 프로세스란
- 쓰레드
- CPU 스케줄링
- 동기화 툴
- 동시성 제어 예제
- 데드락
- 주 메모리
- 페이징과 스와핑
- 가상 메모리와 디맨드 페이징
- 페이지 교체 알고리즘(FIFO, OPT, LRU), 쓰레싱, working set

 

 

Demand paging에서 고려해야할 사항

• frame-allocation algorithm: 각각의 프로세스마다 몇개의 프레임을 할당시켜줄 것인가
• page-replacement algorithm: 페이징 교체를 어떻게 할 것인가

 

페이징 교체 알고리즘(page-replacement algorithm)

 

 

앞의 글에서 page fault 시에 free frame을 찾아서 읽은 page를 할당해주는데,

메모리를 다 사용해서 free frame이 없다면 사용중인 메모리를 page out하고 할당 시켜야함.

이때 사용하는 것이 Page 교체 알고리즘

 

 

FIFO(First In First Out)

• 가장 먼저 온것을 교체하는 알고리즘

• 

• 가장 쉽지만 아래와 같은 문제점이 있다.
• Belady's Anomaly

• 

• 프레임을 늘릴수록 page fault가 적어져야하는데, 일부구간에서 늘어나는 현상

 

OPT(Optimal)

• 가장 늦게 쓰일 페이지랑 교체하는 알고리즘
• 미래의 정보를 알아야 사용할 수 있는 알고리즘
• 실제 사용하기보단, 적용할 알고리즘과 비교하여 성능 체크용으로 쓰인다.
•  

  

 

 

LRU(Least Recently Used)

• 최근에 가장 적게 사용된 것을 교체하는 알고리즘(제일 오랫동안 사용안한 것)
• 페이지별로 마지막에 사용한 시간을 기록
• 앞의 OPT가 미래의 정보로 예측해야하는거였다면, LRU는 과거의 정보를 통해서 예측하여 교체
• 
• LRU를 구현하기위한 방법
  • Counter(clock)
    • 페이지를 참조할때, CPU의 카운터를 copy하거나 시간을 copy한다.
    • 가장 적은 값을 가진 페이지를 교체
  • Stack
    
    • 들어오는 페이지들을 stack에 쌓아두다가, stack에 있는 페이지가 들어오면 기존에 있던걸 빼고 새로 위에 쌓는다.
    • stack이 다 찼는데 새로운 페이지가 들어오면, 가장 밑에 있는 페이지를 빼고 쌓는다.
    • stack은 사실 filo구조지만 그냥 쌓아간다는 의미에서 stack이라고 쓰인듯 하다.

    • 

      
      
      

 

LRU 근사치 알고리즘

• 참조비트(reference bit): 초기값 0. 페이지가 참조되면 1로, 교체되어 나가면 0으로 설정하는 비트.

• 참조 비트를 이용한 내부구현
  • Additional Reference Bits Algorithm
    • 참조 비트를 일정 시간 간격으로 기록하여 정수로 변환했을때 가장 낮은 정수값을 교체.
    • ex) 각 페이지별 8비트로 기록. 00110001
    • 새로운 참조가 들어오면 10011000 으로 됨.
  • Second-Chance Algorithm
    • reference bit를 사용하여 FIFO 알고리즘과 유사하게 실행하는 알고리즘.
    • 환형 큐를 통해 구현되며, FIFO 알고리즘에 의해 선택된 페이지의 참조비트가 0이면 교체. 1이면 0으로 변경하고 다음 순서 확인.(1번의 기회를 더 주는것)
    •  

      

    • 참조비트 + 수정비트를 통한 향상시킨 버전도 있다.

 

LFU (Least Frequently Used)

• 페이지가 사용된 횟수를 기록해 그 횟수가 가장 낮은 페이지를 교체

 

프레임 할당 알고리즘(frame-allocation algorithm)

프로세스마다 프레임을 어떻게 할당할것인가를 정하는 알고리즘

 

전략

• equal allocation vs proportional allocation: 공평하게 줄것인가, 사이즈가 큰 프로세스에게 더 많이 줄것인가.
• global vs local: 페이지 교체할때 page out을 본인 것중에 고를 것인가, 다른 것중에서 고를 것인가.
• 위와 같은 조건들을 선택하여 할당.

 

쓰레싱(Thrashing)

• 페이지 부재(page fault)가 높은 것을 의미
• 프로세스가 page in,out에대해서 바쁠때, 멀티프로그래밍 사용이 높아지면 높아질수록 cpu 사용량이 많아져야하는데, 일정부분 이상부턴 더 떨어짐
• 이러한 현상이 발생하는 이유
  • 운영체제는 CPU이용률을 감시하며, CPU이용률이 낮아지면 새로운 프로세스를 추가하여 멀티 프로그래밍의 정도를 높임.
  • 이때 전역 페이지 교체 알고리즘(global)을 통해 어떤 프로세스의 페이지인지 대한 고려없이 교체 수행
  • 교체당한 페이지들이 해당 프로세스에서 필요했던거라면 page fault 발생 후 다른 프로세스에서 프레임을 가져옴
  • 이때 프로세스들은 교체를 위해 페이징 장치를 사용할려고 대기하게 됨.
  • 대기과정에서 CPU이용률은 떨어지고, 높이기위해 새로운 프로세스를 추가하게 됨(악순환)
•  

  

 

Working-Set Model

• 쓰레싱을 해결하는 방법. 지역성(Locality)을 기반으로 메모리에 상주해둬서 page fault나 swap과정이 안일어나게 하는 방법.
• working set: 지역성을 기반으로 프로세스가 특정시점에 원할하게 수행하기 위해 메모리에 올라와있어야하는 page들의 집합(시점에 따라 변함)

• 

• window size(△)^[각주:1]를 지정해주고, 이를 바탕으로 working set을 구함.(△의 크기는 시스템이 정함)
• WS(working set)은 [t-△,t]까지의 집합.
• 이 바깥에 있는 것을 교체하게 함.
• 보다 자세한 참조는 https://youtu.be/ByQmerWj1bg

 

참조

주니온님의 인프런 운영체제강의(공룡책)

https://4legs-study.tistory.com/54(페이징 교체 알고리즘 참조)

[OS/운영체제] 페이지 교체 (Page Replacement) - (2)

https://jwprogramming.tistory.com/56(쓰레싱 참조)

Thrashing (쓰레싱)이란?

https://developyo.tistory.com/218(working set 참조)

[OS] 운영체제 10. Virtual Memory 2 : 페이지 할당, Global replacement, Thrashing, Thrashing 예방책

https://firecatlibrary.tistory.com/70(working set 참조)

[PintOS, Project 3] Virtual Memory Management - Variable Allocation and Consideration

 

https://kouzie.github.io/operatingsystem/%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%AC/#working-set-algorithm(working set 참조)

가상메모리

 

1. window(일정기간) 동안의 크기 [본문으로]