OS_12_Page Replacement

📢 Page fault가 많다 → 메모리가 부족 → Process가 많다.

1. Page Replacement

1) Over-Allocation of Memory

• Suppose that
  • We have 40 frames
  • Processes 10 page를 필요로함
  • Processes는 실제로 5 page를 사용함
  • 우리는 4개의 프로세스를 demand paging없이 run할 수 있음.
  • 우리는 8개의 프로세스를 demand paging을 통해 run가능.
    • Over-allocion of memory
    • Increased level of multiprogramming
• It is possible that
  • 어떤 프로세스가 갑자기 10개의 페이지를 사용하려고 한다.
  • Page fault가 발생한다면, system은 더 이상 사용가능한 프레임이 없다는 것을 확인한다.

2) Basic Page Replacement

1. disk에서 필요한 page의 위치를 찾는다.
2. victim frame을 찾는다.
   1. using a page replacement algorithm
3. disk에서 필요한 페이지를 새로운 빈 프레임에 읽어온다.
4. page와 frame table을 업데이트한다.
5. process를 재 시작.

• 2 page transfers → doubles EAT
  • Swapping out the victim page
  • Swapping in the desired page

Page Replacement

a) Page Replacement Algorithms

• 알고리즘을 평가하기 위해서는
  • 특정한 메모리 참조 문자열 (string of memory references)를 사용
    • reference string
  • 해당 string의 page fault의 수를 계산한다.
• Example
  • Memory address sequence
    • 0100, 0232, 0301, 0412, 0102, 0203, 0504, …
  • Reference string = page number sequence
    • 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

b) First-In-First-Out(FIFO) Algorithm

• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 3 frames (3 pages can be in memory at a time)

• 9 번의 page faults with 3 frames

• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• 4 frames (4 pages can be in memory at a time)

• 10번의 page faults with 4 frames

  • Belady’s Anomaly (page fault가 frame이 늘었지만 오히려 늘어남)

    

    FIFO Illustrating Belady’s Anomaly

일반적인 목표 → 그래서 FIFO를 사용하지 않는다.

c) Optimal Algorithm

• 오랜 기간동안 사용되지 않은 page를 대체한다. (현 시점으로 부터 오랫동안 사용하지 않는 걸 제거)
• 4 frames example

• 현재는 6 page faluts
• 하지만 이 알고리즘은 reference string에 대해서 미래 정보를 필요로 한다.
• 그래서 보통 비교 연구에만 사용된다? → 다른 페이지 교체 알고리즘과 성능을 비교

2. LRU Implementations

1) Least Recently Used(LRU) Algorithm

• FIFO uses
  • page가 메모리에 적재된 시간을 사용하여 교체를 결정한다.
• OPT uses
  • page가 사용될 시간을 사용하여 교체 결정
    • 미래에 벌어질 일을 모르니까 구현이 어렵다.
• LRU (Least Recently Used) uses
  • 가장 최근에 사용된 정보를 사용하여 교체를 결정한다.
  • 가장 오랫동안 사용되지 않은 page를 선택한다.
  • 이는 프로그램이 locality of reference를 가지고 있다는 가정을 기반으로 한다.
  • 가장 최근의 과거를 미래의 근사치로 활용하여 교체 대상을 선택
  • 이는 최적의 backward-looking algorithm
• 4 frames example

• 8개의 page faults (10, 6 사이)

2) Locality and LRU Performance

• Locality of reference는 프로세서가 짧은 시간 동안 반복적으로 동일한 일련의 메모리 위치에 접근하는 경향을 말한다.
  • 2개의 기본적인 reference locality - temporal and spatital locality
  • Temporal locality는 짧은 시간 동안 특정 데이터나 리소스를 재사용 하는 것을 의미한다.
  • Spatial locality는 상대적으로 가까운 저장 위치에서 데이터 요소를 사용하는 것을 의미한다.
• LRU는 temporal locality에 기반으로 한다.
  • Optimal을 뒤집으면 LRU, 시간적인 대칭 관계 그래서 성능이 좋음
  • 최근에 참조한 것을 또 참조할 가능성이 높다. 이는 프로그램의 특징

3) LRU Implementation

• Counters
  • 각 페이지 항목마다 counter를 가지고 있다. (time-of-use)
  • 해당 항목을 통해 페이지에 접근할 때마다 현재 clock value를 counter에 복사한다.
  • 가장 작은 시간 값을 가진 page를 교체한다.
• Stack
  • page numbers의 stack을 유지한다 (order-of-reference)
  • page가 참조될 때마다 스택의 맨 위로 이동한다.
    • Top → 가장 최근에 사용된 페이지
    • Bottom → 가장 오랫동안 사용되지 않은 페이지
  • double linked list로 구현하는 것이 가장 좋음.

Stack Implementation

• LRU 구현은 hardware의 도움 없이는 실현 불가능하다.
  • clock fields나 stack의 업데이트는 모든 메모리 참조마다 수행되어야한다.
  • 모든 참조에 대해서 interrupt를 사용한다면, 성능이 매우 저하될 것이다.
• 몇몇 컴퓨터 시스템은 충분한 하드웨어 지원을 제공하지 않는다.

4) LRU Approximation Algorithms

• Reference bit
  • 많은 시스템은 reference bit의 형태로 일부 도움을 제공한다.
  • 각 페이지와 연관된 비트를 가지고 있으며, 초기에는 0이다.
  • page가 참조될때, bit는 하드웨어에 의해 1로 설정된다.
  • 0인 페이지가 존재한다면 대체한다.
    • 하지만 순서를 알 수 없다.
• Additional-Reference-Bits
  • 각 페이지에 대해서 8-bit byte를 유지한다.
  • 정기적인 간격 (100 milisec), 마다 OS는 reference bit를 shift한다.
  • 10000000 → 01000000 → 10100000 → 11010100
  • 11000000은 01110111보다 더 최근에 사용되었다.
    • 값이 작은 것을 쫓아낸다 → 더 늦게 사용된 것이기 때문에
• LRU는 어차피 optimal하지 않기 때문에 대략적으로 구현한다.
• Second chance
  • FIFO algorithm + reference bit
  • reference bit가 필요하다.
  • reference bit value가 0이면, page를 대체한다.
  • reference bit value가 1이라면
    • reference bit를 0으로 설정
    • page를 메모리에 유지한다.
    • 다음 FIFO page로 이동한다.
  • 모든 값이 1인 최악이 경우에는
    • algorithm이 FIFO로 변한다.
  • 즉, FIFO로 진행하는데 reference-bit가 1이면 안쫓아내고, 0으로 바꾼다.
    • 1번만 봐주는 느낌

2번째 그림의 0을 victim으로 설정, 중간에 만나는 1을 0으로 바꿈

5) Counting Algorithms

• 각 페이지에 대한 참조 횟수를 counter로 유지한다.
• LFU(Least Frequently Used) Algorithm
  • 가장 작은 count를 가진 page를 교체한다.
  • 가장 활발하게 사용되는 페이지에 우선순위를 부여한다.
• MFU(Most Frequently Used) Algorithm
  • 가장 큰 count를 가진 page를 교체한다.
  • 이는 가장 최근에 메모리에 올라온 페이지가 아직 사용되지 않았을 가능성이 높다는 가정에 기초한다.
• 둘 다 일반적으로 사용되지 않음.
  • 페이지 참조 횟수를 정확하게 추적하는 것이 복잡하고 오버헤드가 크기 때문에, 또한 경우에 따라 무엇이 더 좋은지 다르다.