treecode

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소 (실제 사용 영역은 제한적)
  • Memory 사용량 감소
  • 빠른 응답 시간 (의미 있는 것을 더 올려놓기 때문)

페이지 테이블에는 valid-invalid bit가 있는데 물리 메모리에 페이지가 올라와 있는지를 체크해주는 역할을 한다. 물리 메모리 오른쪽의 그림은 swap area로 사용되지 않는 페이지를 backing store(Disk)에 두는 것인데 요청한 페이지가 물리 메모리에 없을 경우 Page Fault가 발생하고 swap area에서 페이지를 읽어온다.

page fault가 발생하면 MMU(메모리 주소 변환을 해주는 하드웨어)는 trap을 발생시키는데 이때 CPU가 현재 프로세스에서 운영체제로 넘어가고 page fault handler가 동작한다 .

page fault handler는 먼저 정상적인 메모리 요청인지 확인을 한 뒤 물리 메모리의 비어 있는 페이지 프레임을 찾고 없으면 replace 작업을 한다.

DIsk I/O 작업은 비교적 굉장히 오래 걸리기 때문에 프로세스를 block 상태로 만들고 I/O 작업이 끝나면 Invalid bit를 valid로 바꾸고 프로세스를 Ready Queue에 넣는다.

페이지 교체 알고리즘 (Replace Algorithm)

• Optimal Algorithm
  • 가장 먼 미래에 참조되는 페이지를 쫓아내는데 사실상 미래를 예측하기 어려워서 비현실적
  • 이상적인 케이스를 통해 다른 알고리즘과의 성능 비교를 위해 사용(upper bound)
• FIFO
  • FIFO Anomaly : 메모리 크기를 늘리면 page fault가 오히려 증가할 수 있다
• LRU (Least Recently Used)
  • 가장 오래전에 사용된 것을 교체 (들어온 것 기준 x)
  • 과거에 많이 참조가 되었더라도 가장 오래 전에 사용이 됐으면 교체가 되는 단점
  • 링크드 리스트로 구현을 해서 교체 시간 O(1)
• LFU (Least Frequently Used)
  • 참조 횟수가 가장 적은 페이지를 지움
  • 이제 막 참조가 시작된 페이지가 교체되어버리는 경우가 생기는 단점
  • heap 구조 O(log n)

가상 메모리 페이징 기법에서는 LRU, LFU 같은 알고리즘 적용이 어렵다. 왜냐하면 메모리 주소 변환 작업을 운영체제가 관여하지 않아서 언제 어떤 페이지가 참조되었고 얼마나 참조 되었는지 이런 부분을 체크하기 어렵기 때문이다.

Clock Algorithm

• 최근에 페이지가 참조가 되면 reference bit를 1로 설정 (하드웨어가 함)
• 운영체제는 reference bit가 1이면 0으로 바꾸고 그 다음 페이지 비트 검사
• reference bit가 0인 페이지를 만나면 교체
• 가장 오래 전에 참조된 페이지를 교체하진 않지만 LRU와 어느정도 비슷한 효과
• modified bit : 최근에 페이지가 변경되었는지 확인
• modified bit가 0이면 그냥 메모리에서 지우면 되는데 modified bit가 1이면 변경(write)이 있다는 것이므로 디스크에 수정된 내용을 반영

Thrashing

동시에 실행되는 프로그램이 증가하면 프로세스마다 할당되는 메모리가 부족해지고 최소한의 page frame을 할당받지 못해서 Page Fault가 증가하게 된다. 그러면 Disk I/O 작업으로 인해 CPU 이용률이 떨어지게 되는데 이때 운영체제는 CPU 이용률이 부족한 것을 멀티프로그래밍 개수를 늘려야겠다고 판단하는데 이러한 현상을 Thrashing이라 한다.

멀티 프로그래밍 개수를 조절하기 위해 Working-Set 모델이 있는데 working-set이란 특정 시간에 집중적으로 참조되는 page들의 집합으로 프로세스가 일정 시간동안 원활하게 수행되기 위해서 해당 페이지 집합을 전부 메모리에 올리는 것을 말한다. working-set이 보장이 안 되면 모든 프레임을 반납하고 swap-out(suspend) 시켜서 thrashing 현상을 방지할 수 있다.

페이지 단위가 너무 작으면 내부 단편화를 방지할 수 있지만 페이지 테이블 크기가 증가하고 Page Fault로 인한 Disk I/O가 많이 발생한다. 반면 페이지 단위가 클 경우 내부 단편화와 transfer 시간이 오래 걸리고 필요없는 정보까지 메모리에 올라오는 단점이 있다.

[참고]