운영체제 (15) - 다양한 Caching 환경

Caching 기법

• 한정된 빠른 공간( = Cache)에다가 요청된 데이터를 저장해 두었다가 후속 요청서 캐쉬로부터 직접 서비스하는 방식
• paging system외에도 Cache memory, buffer caching, Web caching등 다양한 분야에서 사용

Caching에서는 시간 제약이 있다. 왜냐하면 더 빠르자고 쓰는 건데 이게 오래걸리면 어불성설이기 때문이다

• Buffer caching이나 Web caching의 경우 ... O(1)에서 O( log n )정도까지 허용
• Paging system의 경우...
  • Page fault인 경우에만 OS가 관여함
  • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
  • O(1)인 LRU의 리스트 조작조차 불가능하

Paging System에선 Clock Algorithm 사용

 

• LRU의 근사 알고리즘
• 운영체제는 가장 오래 전에 참조된 페이지를 알 수 없으므로, 대신 최근에 사용되지 않은 페이지를 쫓아낸다.
• 시계바늘이 이동하면서 알고리즘이 동작하는 방식이라서 이렇게 부른다
• NUR ( Not Used Recently) 또는 NRU ( Not Recently Used)라고도 불린다
• reference bit이 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.
• 포인터를 이동하는 중 reference bit 1은 모두 0으로 바꾼다.
• reference bit이 0인 것을 찾으면 그 페이지를 교체한다.

 

Page Frame의 Allocation

• Allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가???
• Allocation의 필요성
  • Loop를 구성하는 page들은 한꺼번에 allocate 되는것이 유리함, 최소한의 allocation이 없으면 매 loop마다 page fault
  • 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시참조, 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음

Allocation Scheme

• Equal allocation : 모든 프로세스에 똑같은 갯수 할당
• Proportional allocation : 프로세스 크기에 비례하여 할당
• Priority allocation : 프로세스의 priority에 따라 다르게 할당

 

Global VS Local Replacement

1. Global replacement
   • Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다
   • process별 할당량을 조절하는 또 다른 방법임
   • EX) Working Set, PFF 알고리즘 사용
2. Local replacement
   • 자신에게 할당된 frame 내에서만 replacement
   • FIFO, LRU, LFU 등의 알고리즘을 process별로 운영

Thrashing

• 페이지 부재율(Page fault)이 증가하여 CPU 이용율이 급격하게 떨어지는 현상
• 프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
• page fault rate이 매우 높아짐
• Cpu utilization이 낮아짐 -> OS는 MPD( multi programming Degree) 높이는 판단
• 대부분의 시간에 CPU는 한가함
• Low throughput
• 해결방안으로는 Working - Set Model과 PFF (Page Fault Frequency)가 있다

 

Working - Set Model

• Locality of reference
  • 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함
• Working - Set Model
  • Locality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working set이라 정의함
  • Thrashing을 방지함
  • Multi Programming degree를 결정함
• Working Set의 결정
  • Working set window를 통해 알아냄
  • Window size가 A인 경우.... 시각 ti 에서의 Working Set WS(ti)는 Time interval [ti - ti+A] 사이에 참조된 서로 다른페이지들의 집합
  • Working set에 속한 page는 메모리에 유지, 속하지 않은 것을 버림
  • 즉, 참조된 후 A 시간 동안 해당 page를 메모리에 유지한 후 버림

PFF( Page - Fault Frequency) scheme

• page fault rate이 상한값을 넘으면 frame을 더 할당, 하한값 이하이면 할당 frame 수를 줄인다
• 빈 frame이 없으면 일부 프로세스를 Swap out

Page size의 결정

• page size를 감소시키면
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • Internal fragmentation (내부 간편화) 감소
  • Disk transfer의 효율성 감소 -> seek / rotation vs transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 -> Locality의 활용 측면에서는 좋지 않음
• 요즘 Trend는 Larger page size

이 포스팅은 이화여대에서 무료로제공하는 반효경님의 운영체제강의를 수강하며 정리한 내용입니다.

필자가 잘 이해하지 못해서 잘못된 내용이 있을 수 있으므로 주의바라며, 발견되면 알려주시면 감사하겠습니다.

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

운영체제