Swapping

Swapping: Mechanisms

Swapping: Policies

Goal of Cache Management

• to minimize the number of cache misses.
• the average memory access time(AMAT)

The Optimal Replacement Policy

• Lead to the fewest number of misses overall.
  • Replace the page that will be accessed furthest in the future.
  • Result in the fewest-possible cache misses.
• Serve only as a comparison point, to know how close we are to perfect.

프로그램이 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1 순서대로 페이지들에 접근할 때

캐시는 처음에 비어있는 상태로 시작하기 때문에 처음 세번의 접근은 미스이다. (최초 시작 미스 cold-start miss or 강제 미스 compulsory miss)

그 다음에 페이지 0과 1을 참조하면 캐시에서 히트된다.

Optimal Replacement Policy는 캐시에 현재 탑재되어 있는 각 페이지들을 미리 본다. (3 이후에 바로 0이 히트, 그 다음 1이 히트)

2와 3을 교체(미스)

...

미래는 일반적으로 알 수 없으므로
범용 운영체제에서는 Optimal Replacement Policy의 구현은 불가능

Optimal Replacement Policy은 비교기준으로만 사용

A Simple Policy: FIFO

• Pages were placed in a queue when they enter the system.
• When a replacement occurs, the page on the tail of the queue(the “First-in” pages) is evicted.
  • It is simple to implement, but can’t determine the importance of blocks

Another Simple Policy: Random

• Picks a random page to replace under memory pressure.
  • It doesn’t really try to be too intelligent in picking which blocks to evict.
  • Random does depends entirely upon how lucky Random gets in its choice.
    
    Sometimes, Random is as good as optimal, achieving 6 hits on the example trace.

Using History

• Learn on the past and use history.

  • Two type of historical information

• recency : The more recently a page has been accessed, the more likely it will be accessed again
  Algorithms: LRU (Least Recently Used)

• frequency: If a page has been accessed many times, It should not be replcaed as it clearly has some value
  Algorithms: LFU (Least Frequently Used)

Using History : LRU

• Replace the least-recently-used page.
  

LRU가 Optimal Replacement Policy와 같은 정도 수준의 성능을 얻을 수 있는 최고의 결과를 보여준다.

이와 반대되는 Most-Frequently-Used와 Most-Recently-Used와 같은 알고리즘도 존재하지만 대부분의 경우 잘 동작하지 않는다.
(대부분의 프로그램들에서 관찰되는 지역성 접근 특성을 사용하지 않고 오히려 무시하기 때문)

Workroad Example (워크로드에 따른 성능 비교)

The No-Locality Workload

• Each reference is to a random page within the set of accessed pages.
  • Workload accesses 100 unique pages over time.
  • Choosing the next page to refer to at random

워크로드에 지역성이 없다면 어느 정책을 사용하든 상관이 없다.
(LRU, FIFO, Random 모두 동일한 성능을 보이며, Hit rate는 캐시의 크기에 의해서 결정된다.)

The 80-20 Workload

p Exhibits locality: 80% of the reference are made to 20% of the page
p The remaining 20% of the reference are made to the remaining 80% of the
pages.

Approximating LRU: Clock Algorithm

• Require hardware support: a use bit
  • Whenever a page is referenced, the use bit is set by hardware to 1.
  • Hardware never clears the bit, though; that is the responsibility of the OS (하드웨어는 비트를 지우지 않는다.)
• Clock Algorithm
  • All pages of the system arranges in a circular list.
  • A clock hand points to some particular page to begin with.
  • The algorithm continues until it finds a use bit that is set to 0.

page마다 use bit을 사용 (0 or 1)
1 -> 페이지 P는 최근에 사용되었으므로 교체 X
0 ->

완벽한 LRU보다 좋은 성능을 보이지는 않지만 과거 정보를 고려하지 않는 다른 기법들에 비해서 성능이 더 좋고 LRU보다 Simple함.

Workload with Clock Algorithm

• Clock algorithm doesn’t do as well as perfect LRU, it does better then
  approach that don’t consider history at all.

Considering Dirty Pages

갱신된 페이지(Dirty Pages)의 고려

• The hardware includes a modified bit (= dirty bit)
  • Page has been modified and is thus dirty, it must be written back to disk to evict it.
  • Page has not been modified, the eviction is free.

Other VM Policies

페이지 교체 정책만이 VM 시스템이 채택하는 유일한 정책은 아니다.
페이지 정책이 가장 중요한 정책이기는 하다!

페이지 선택 정책
요구 페이징

Prefetching

선반입

• The OS guesses that a page is about to be used, and thus bring it in ahead of time.

Clustering, Grouping

• Collect a number of pending writes together in memory and write them to disk in one write.
  • Perform a single large write more efficiently than many small ones.

한번에 한 페이지씩 디스크에 쓸 수 있지만, 많은 시스템은 기록해야 할 페이지들을 메모리에 모은 후, 한번에(효율적으로) 디스크에 기록한다.

Thrashing

메모리 사용 요구가 감당할 수 없을 만큼 많고, 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우에 시스템은 끊임없이 페이징을 한다.

• Memory is oversubscribed and the memory demands of the set of running processes exceeds the available physical memory.
  • Decide not to run a subset of processes.
  • Reduced set of processes working sets fit in memory.
    

Summary

• Swapping: use part of disk as memory
  Replacement policy (Optimal not realistic)
• Practical
  • LRU, LFU, RANDOM, FIFO

LRU 구현 어려움, 나머지 알고리즘 구현

• Approximation to LRU: Clock
• Making the disk IO in larger unit
  • Clustering
  • Grouping
  • prefetching