Virtual Memory (2)

다양한 캐싱 환경

• 캐싱 기법
  • 한정된 빠른 공간 (캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식
  • Paging System 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용
• 캐시 운영의 시간 제약
  
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
  • Buffer caching이나 Web caching의 경우
    • O(1)에서 O(log n) 정도까지 허용
  • Paging System인 경우
    • page fault인 경우에만 OS가 관여함
    • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
    • O(1)의 LRU의 list 조작조차 불가능

---

LRU와 LFU 알고리즘의 구현

 

• LRU는 O(1)의 복잡도
  • 링크드 리스트로 구현된다
  • 참조된 것을 찾아서 제일 최신으로 갖다 놓으면 되므로 삭제와 추가에 O(1)만큼만 시간이 걸린다
• LFU는 O(log n)의 복잡도
  • 링크드 리스트로 구현되면 현재 메모리가 참조돼서 참조횟수가 +1이 된경우 다른 메모리의 횟수와 비교해야 되는데 이때 최악의 경우 O(n)만큼의 시간이 걸린다
  • 이 시간을 줄이기 위해 HEAP으로 구현을 하게 되는데 이렇게 되면 O(logN)만큼의 시간이 걸린다

---

Paging System에서 LRU, LFU 가능한가?

 

• 페이지 부재시에는 CPU 권한이 운영체제로 넘어가기때문에 이 정보만 알수 있지만 구현하는데 너무 부족한 정보이다
• 즉 페이징 시스템에서 LRU와 LRU는 무용지물이다. (Buffer caching 이나 Web Caching에서는 사용 가능)

---

Clock Algorithm (페이징 시스템에서 사용한다)

• Clock algorithm
  • LRU의 근사 (approximation) 알고리즘
  • 여러 명칭으로 불림
    • Second chance algorithm
    • NUR(Not Used Recently), NRU(Not Recently Used) - 운영체제는 어떤 것이 제일 오래 전에 사용되었는지 모르기 때문에 사용이 한번도 안된 것을 고른다
  • Reference bit을 사용해서 교체 대상 페이지를 선정(circular list)
  • Reference bit이 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
  • 포인터가 이동하는 중에 reference bit 1은 모두 0으로 바꿈
  • Reference bit이 0인 것을 찾으면 그 페이지를 교체
  • 한 바퀴 되돌아와서도 (=second chance) 0이면 그때에는 replace 당함
  • 자주 사용되는 페이지라면 second chance가 올 때 1
• Clock Algorithm의 개선 
  • reference bit 과 modified bit (dirty bit)을 함께 사용 - 하드웨어가 한다 
  •  reference bit = 1 : 최근에 참조된 페이지
  • modified bit = 1 : 최근에 변경된 페이지 / write (I/O 를 동반하는 페이지)

---

Page Frame의 Allocation

• 각 process에 page frame을 얼마나 할당할 것인가?!
• 너무 많이 할당 → 메모리에 동시에 올라간 프로세스가 적어서 일하지 않는 CPU가 생겨서 CPU 활용도가 떨어짐
• 넘 조금 할당 → 프로세스가 최소로 필요로 하는 frame 마저 충족을 못 시킨다

 

• Allocation Scheme
  • Equal Allocation : 모든 프로세스에게 똑같이 할당
  • Proportional Allocation : 프로세스 크기에 비례해서 할당
  • Priority Allocation : 프로세스의 priority에 따라 다르게 할당

---

Global vs Local replacement

• Global Replacement - 그때그때마다 경쟁해서 많이 가질수도, 적게 가질 수도 있움
  • Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다
  • Process 별 할당량을 조절하는 또 다른 방법
  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
  • Working set, PFF 알고리즘 사용
• Local Replacement - 몫을 미리 나누어주고 알아서 써라~
  • 자신에게 할당된 frame 내에서만 replacement
  • FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영

---

Thrashing

• Thrashing
  • 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
  • Page fault rate이 매우 높아짐
  • CPU utilization이 낮아짐
  • OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
  • 또 다른 프로세스가 시스템에 추가됨 (higher MPD)
  • 프로세스 당 할당된 frame의 수가 더욱 감소
  • 프로세스는 page의 swap in/out 으로 매우 바쁨
  • 대부분의 시간에 CPU는 한가함
  • low throughput

 

• 프로세스가 너무 많아지면 한 프로세스에게 할당된 페이지가 너무 적어져서 아주 조금을 돌리기 위해서도 페이지 부재가 발생한다

---

프로그램이 어느정도 메모리 확보를 해줄 수 있게 해주는 알고리즘

• Working Set algorithm
  • Localrity of reference
    • 적어도 프로그램들이 메모리에서 원활하게 실행되려면 어느정도의 메모리 페이지를 가지고 있어야 한다
    • 프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다
    • 집중적으로 참조되는 해당 Page들의 집합을 locality set 이라고 한다
  • Working set Model
    • 한꺼번에 메모리에 올라와 있어야하는 page들의 집합을 working set 이라고 정의
    • Working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고, 아니라면 모든 frame을 반납하고 디스크로 swap out (suspent)
    •  Thrashing을 방지
    • Multiprogramming degree를 결정함
  • Working set 의 결정
    • Working Set window를 통해 알아낸다
  • Working Set Algorithm
    • Process들의 working set size의 합이 page frame의 수보다 큰 경우
      • 일부 Process를 swap out 시켜 남은 process의 working set을 우선적으로 충족시켜 준다(MPD를 줄임)
    • Working set을 다 할당하고도 page frame이 남는 경우
      • swap out 되었던 프로세스에게 working set을 할당 (MPD를 키움)
  • Window size
    • Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야한다
    • 값이 너무 작으면 locality set을 모두 수용하지 못할 우려
    • 값이 크면 여러 규모의 locality set 수용
    • 값이 무한이면 전체 프로그램을 구성하는 page를 working set으로 간주

---

PFF (Page-Fault Frequency) Scheme

• page-fault rate의 상한값과 하한값을 둔다
  • Page-fault rate가 상한값을 넘으면 frame을 더 할당한다
  • Page-fault rate가 하한값 이하이면 할당 frame 수를 줄인다
• 빈 frame이 없으면 일부 프로세스를 swap out

---

Page Size의 결정

• Page Size를 감소시키면 
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • Internal fragmentation 감소 (사용안되는 부분)
  • Disk transfer 의 효율성 감소
    • Seek/rotation vs transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality  활용 측면에서는 좋지 않음
  • Trend 
    • Larger page size