[OS] Beyond Physical Memory

메커니즘

스왑 공간

디스크에 페이지들을 저장할 수 있는 일정 공간

 

캐시관리

캐시 미스 종류

• Compulsory Miss: 캐시가 비어 있어 그 항목을 처음 참조하기 때문에 발생
• Capacity Miss: 캐시의 공간이 다 차서 새로운 항목을 캐시에 넣기 위해 어떤 항목을 내보내야 할 때 발생
• Complict(Collision) Miss: 캐시의 같은 공간을 참조해야할 때 발생
• Coherence(Invalidation) Miss: 다른 프로세스가 메모리에 업데이트될 때 발생

매핑 방법

• Direct MApped Cache
• Set Associative Cache
• Fully Associative Cache

AMAT(평균 메모리 접근 시간)

= Tm + (Pmiss * Td)

• Tm: 메모리 접근 비용
• Td: 디스크 접근 비용
• Pmiss: 캐시에서 데이터를 못 찾을 확률(미스)

 

페이지 교체 정책

1. FIFO

먼저 들어온 페이지가 먼저 나간다.

• 성능 저하
• Belady’s anomaly(벨레이디의 모순)
  • Stack Property: N < N+1
  • 메모리(캐시, 페이지 프레임) 크기를 늘리면 Hit Rate이 증가해야 하나, 오히려 감소나는 경우

2. OPT

각 페이지들의 미래를 살펴보고 가장 먼 미래에 접근될 페이지를 내보낸다.

• 구현 불가능

3. LRU

과거 이력에 기반해서 가장 적은 빈도로 사용된 페이지를 교체

4. Random

페이지 무작위로 선택하여 교체

 

Workload

1. No-Locality Workload

• OPT > LRU = FIFO = RAND

2. 80-20 Workload

• 80%의 access가 20% 페이지에 몰리도록
• OPT > LRU > FIFO = RAND

3. Looping Workload

• acess pattern이 반복 1 2 3 … 1 2 3
• OPT > RAND > LRU = FIFO

 

LRU & Clock

• LRU를 구현하기 힘들고 구현하고 할 때 time stamp를 사용해야 한다.
• → 가장 오래된 것을 찾지말고 그냥 오래된 것을 찾아서 바꿔주자.
• → Clock Algorithm

Clock Algorithm

• use bit(reference bit): 0 or 1
  • use bit = 0이면 교체
  • use bit = 1이면 use bit = 0으로 clear 하고 다음 페이지로 넘어간다.
  • Disk I/O에서 물리메모리로 swap in한 경우, use bit = 1
  • clock 바늘이 지나가면 use bit = 0, 바늘이 다시 돌아올 때까지 access 되지 않으면 계속 0이므로 교체 대상
• clock 바늘은 use bit가 변경되면 바뀐다.
• use bit가 1로 바뀌는 것은 HW적으로 실행되고, use bit가 0으로 바뀌고 바늘이 도는 것은 커널에 의해 SW적으로 실행된다.

 

N’th Chance Algorithm

N번 더 기회를 주는 알고리즘

counter

• use bit = 0이면 counter 증가, count = N 이면 페이지 교체
• use bit = 1이면 use bit와 counter clear

dirty bit

• 0 or 1
• 한번이라도 메모리에 access 된 적 있으면 dirty bit = 1
• dirty =1이면 일단 지나간다.
• 모든 페이지가 dirty = 1이면 Disk I/O에 swap out 해줘야 한다.

 

Thrashing

Process가 많아 Physical meory가 모자라는 경우 발생

• 메모리와 Disk I/O 간의 swap이 많이 발생하여 CPU의 사용률 감소 → 느려짐
• Working Set
  • excution time t를 기점으로 델타만큼 access하고 있는 페이지의 집합
  • 델타를 적당한 값으로 설정
  • D < m(메모리의 working set)
  • D > m이면 Thrashing 다시 발생