운영체제

---

Swapping 정책

• 빈 메모리 공간이 부족하면

  • OS는 메모리 압박을 해소하기 위해 다른 페이지들을 강제적으로 swap out해 사용중인 페이지들을 위한 공간을 확보한다

• OS는 어떤 기준으로 내보낼 페이지들을 선택하는가?

  • victim 페이지는 교체 정책에 의해 결정된다
    • FIFO
    • 랜덤
    • LRU(least recently used)

어떤 정책이 좋고 나쁘고는 없음, 상황에 따라..

캐시 관리

교체정책의 목표

• 캐시 미스의 횟수를 최소화 하는 것

AMAT

• 캐시 히트, 미스 횟수를 알면 계산이 가능함
  • 메모리를 접근하는 비용, 디스크를 접근하는 비용을 알아야함
• 메모리에 정상적으로 있는 경우 + fault로 인해 디스크에서 접근하는 경우
• 메모리에서 데이터를 접근하는 비용은 항상 존재
  • but 메모리에서 못찾는다면 디스크로부터 가져오는 비용을 추가로 지급해야함

hit rate 계산

• 히트 횟수 / (히트 횟수 + 미스 횟수)

AMAT = (히트 비율 메모리 접근 비용) + (미스 비율 디스크 접근 비용)
EAT = 주소를 찾기위한 메모리로의 접근

ex

메모리 접근 시간 = 100ns  디스크 접근 시간 = 10 ms

case 1 

hit rate = 90% miss rate = 10 %

AMAT = (90/100*100ns) + (10/100*10ms) = 90ns + 1ms = 1.00009ms

case 2

hit rate = 99.9% miss rate = 0.1 %

AMAT = (999/1000*100ns) + (1/1000*10ms) = 10.us


2가 1보다 백배 빠르다

ms : 밀리초 0.001 = 10^(-3)초

㎲ : 마이크로초 0.000001초 = 10^(-6)초

㎱: 나노초 0.000000001초 = 10^(-9)초

미스가 발생하면 AMAT에 큰 영향을 끼친다

캐시 미스 종류

• Cold-start miss(compulsory miss)
  • 캐시가 비어있어서 일어남
• Capacity miss
  • 캐시의 공간이 다 차서 새로운 항목을 캐시에 넣기 위해 어떤 항목을 내보낼때 발생
• Conflict miss
  • 디스크의 서로다른 공간이 메모리에 같은 공간을 사용하기때문에 같은 공간을 사용하는 데이터가 비켜!! 할 떄 일어나는 미스
  • set associative때문에 발생
  • 페이지 캐시는 fully associative라 발생하지 않음
    • 특별히 메모리에 저장되는 공간을 지정하지 않음

최적 교체 정책

• 가장 먼 미래에 사용되는 페이지를 버리자
  • 그치만 미래를 모르니 불가
    • 다른 정책과 단순 비교를 위해 제안한 것
      • 최적 교체와 hit rate가 비슷하면 좋은 것

FIFO

• 시스템에 페이지가 들어오면 큐에 삽입
• 교체를 해야할 경우 큐의 테일에 있는 페이지(제일 처음 들어온)가 내보내짐
• 구현하기 쉬움
• 페이지의 중요도를 판단할 수 없음
  • 어떠한 페이지가 여러차례 접근되더라도 메모리에 먼저 들어왔으므로 내보낸다

FIFO 문제점

Belady's anomaly

• 캐시의 크기가 커지면 hit rate가 올라갈 것이라 예측하지만, FIFO에선 아닌 케이스가 존재한다
• FIFO는 stack property를 가지고 있지 않다
  • stack property: 캐시크기가 N+1로 증가하면 캐시 크기 N일때의 내용을 포함한다

random

• 메모리 압박이 있을 때 페이지를 무작위로 선택하여 교체한다
  • 구현하기 쉽지만 내보낼 페이지를 제대로 선택하지 않음
  • 오직 운에 의존
• 큐에 있는 페이지중 아무거나 골라 교체한다

때때로 랜덤은 최적기법 만큼 좋은 성능을 보임

• 성능은 그때 그때 달라짐

LRU

Using History

미래 예측을 위해 과거 사용 이력을 활용

• Recency(최근성)
  • 더 최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높다
  • LRU
• Frequency(빈도수)
  • 한 페이지가 여러차례 접근되었따면, 가치가 있기 때문에 교체되면 안된다
  • LFU

LRU

• 제일 오래전에 사용했던 페이지를 교체한다
• history를 통해 미래를 예측한다
  • 시간 locality의 이점을 활용한다
• 어떠한 페이지가 최근 사용되면 큐의 헤드에 위치하게 된다(제일 최근 쓰인 곳)
  • 즉 큐의 위치가 계속 조정이 된다
• 교체가 필요하면 큐의 테일, 제일 전에 쓰인 페이지를 교체한다

LRU 문제점

• LRU 페이지를 추적해야 한다
  • 모든 메모리 액세스에 작업이 요구된다
    • 큐 갱신, 누가 젤 먼저 사용되었는지..
  • LRU 페이지를 찾기 위해 큰 페이지 목록 검색 필요
    • 교체 대상 페이지를 찾기 위해

=> 성능을 저하한다

해결법

• 하드웨어의 도움을 받는다
  • 그치만 LRU 교체 페이지를 찾는데 걸리는 시간을 해결 못한다

LRU와 비슷한 정책을 사용!

LRU 정책 근사하기

• Reference bit(use bit)
  • 페이지가 사용되면, 하드웨어는 bit를 1로 설정
  • reference 비트는 오직 OS에 의해서만 clear됨
    • 하드웨어는 clear 불가

=> LRU에 가깝게 구현을 위해 어떻게 usebit을 활용??

• clock 알고리즘
  • 시스템의 모든 페이지들이 환형 리스트를 구성
    • 시계 바늘이 페이지를 가리킨다고 가정
  • victim 페이지를 찾기위해 page들의 reference bit을 확인
    • 1이라면 교체대상이 아님
      • 비트를 0으로 설정
      • 다음 페이지로 이동
    • 0이라면 교체
  • 비트가 0인것을 찾아 계속 작동함
    • 최악의 경우 모든 페이지들이 사용되어서 한바퀴 다 돌수도..

완벽하진 않지만 유사하게 작동함

Dirty pages(갱신된 페이지) 고려

• 하드웨어는 modified bit(dirty bit)을 포함한다
  • 페이지가 변경되어 dirty 상태가 되었따면 페이지를 evict하려면 디스크에 다시 써야한다
    • 페이지의 변경내용을 다시 기록해야하기 떄문에 추가 비용이 발생한다
  • 페이지가 변경되지 않았다면 eviction은 free다

교체 알고리즘에서 페이지 수정 여부를 고려하여 교체 대상을 선택
ex

clock에서 교체 대상을 선택할 때 사용되지 않은 상태, 깨끗한 페이지를 먼저 찾음
만약 이러한 페이지가 없다면 수정되었지만 한동안 사용되지 않은 페이지 선택

워크로드에 따른 성능 비교

그림은 책 참고..

locality가 없는 워크로드

• 접근되는 페이지들의 집합에서 페이지가 무작위로 참조된다 결론
  1. 워크로드에 지역성이 없다면 어떠한 정책을 써도 상관이 없다
     • 히트 rate는 캐시의 크기에 의해 결정이 된다
  2. 캐시가 충분히 커서 모든 워크로드를 다 포함 가능하다면 어떠한 정책을 써도 괜찮다
  3. 최적기법이 제일 성능이 좋다
     • 미래를 알면 제일 좋다

80-20 워크로드

20% 페이지들(인기 있는)에서 80%의 참조가 일어나고 나머지 80%페이지(비인기)들에서 20%의 참조가 일어난다

• Exhibits locality
  • 80%의 접근은 20%의 페이지가 만든다

결론

• LRU가 랜덤, FIFO와 비교해 좋다
  • 인기 있는 페이지들이 과거에 빈번히 참조되기 떄문에
• LRU의 과거 정보가 완벽하지는 않다
  • 최적이 LRU보다 좋은 성능을 보이니

순환 형 워크로드

• 50개의 페이지를 순차적으로 참조한다

결론

• 랜덤 기법이 제일 좋다
  • 워크로드의 반복으로 인해 먼저 들어온, 오래 전에 접근한 페이지들이 나가게 되니

clock 기법을 사용한 80-20 워크로드

• 교체할때 페이지들을 랜덤하게 검사
  • reference bit가 1로 설정되어 있는 페이지들을 만나면 비트를 0으로 설정
  • reference bit가 0으로 설정된 페이지를 만나면 해당 페이지를 교체 대상으로 선정

결론

• LRU만큼은 아니지만 hitory를 사용하지 않는 것과 비교하면 괜찮은 성능을 보임

그래서... 더 많은 자원을 써야하는 기법이 있는데 성능차이가 조금만 남.
근데 miss에서 비용이 너무 많이 추가된다? 그럼 더 많은 자원을 사용해야지
근데 별로 차이 안난다? 그럼 그냥 성능 안좋은거 사용해~

Prefetching

• OS는 언제 페이지를 메모리로 불러들일지 결정해야 한다
• Os는 어떤 페이지가 곧 사용될 것이라는 것을 예상할 수 있어, 미리 메모리로 읽어온다
• P가 메모리에 탑재되면 P+1이 접근될 확률이 높으니 P와 P+1을 같이 탑재

Clustering(Grouping)

• 기록해야할 페이지들을 메모리에 모은후, 한번에 디스크에 기록한다
  • 효율적이다
    • 디스크는 여러개의 작은 크기 요청을 처리하는 것 보다 하나의 큰 요청을 더 효율적으로 처리할 수 있기 떄문

Thrashing

• 메모리 사용 요구가 감당 불가할 정도로 많고, 실행중인 프로세스가 요구하는 메모리가 실제 메모리를 넘을때는 어떻게 하는가?
  • 시스템은 끊임없이 페이징하고 캐시 사용 이익을 잃는다

해결법

• admission control(진입 제어)
  • 다수의 프로세스가 존재할 때 일부 프로세스의 실행을 중지시킴
    • 많은 일을 하는 것 보다 제대로 적은 일을 하는 것
    • working set을 메모리보다 줄인다
    • working set: 프로세스가 실행 중에 일정시간 동안 사용하는 페이지들의 집합
• Out of memory killer
  • 많은 메모리를 요구하는 프로세스를 골라 죽인다