20. Virtual Memory 2

이화여자대학교 반효경 교수님의 운영체제 강의 23강을 듣고 정리한 내용이다.

 

✏️ 다양한 캐싱 환경

✔️ 캐싱 기법

• 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식
• 가능하면 물리적 메모리에서 해결을 하고, page fault가 나면 처리 속도가 느린 backing store을 참조하는 것
• Paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용(LRU, LFU 사용 가능)

 ✔️ 캐시 운영의 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
• Buffer caching 이나 Web caching의 경우
  • $O(1)$에서 $O(log n)$정도까지 허용
• Paging system인 경우
  • page default인 경우에만 OS가 관여함
  • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
  • $O(1)$인 LRU의 list 조작조차 불가능

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

• Process A가 실행 중인 경우임
• Process A의 논리적인 메모리에서 매 순간마다 instruction을 읽어와서 실행을 함

---

✏️ 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으로 바꿈
• 한 바퀴 되돌아와서도(=second chance) 0이면 그 때는 replace 당함
• 자주 사용되는 페이지라면 second chance가 올 때 1

 

✔️ Clcok Algorithm의 개선

• Reference bit과 Modified bit(dirty bit)을 함꼐 사용
• Reference bit = 1 : 최근에 참조된 페이지
• Modified bit = 1 :최근에 변경된 페이지 (I/O를 동반하는 페이지)

---

✏️ Page Frame의 Allocation

✔️ Allocation Problem - 각 Process에 얼마만큼의 Page frame을 할당할 것인가?

✔️Allocation의 필요성

• 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조 - 명령어 수행을 위해 최소한 할당되어야 하는 Frame의 수가 있음
• Loop를 구성하는 Page들은 한꺼번에 allocate되는 것이 유리함 - 최소한의 allocation이 없으면 매 loop마다 page fault

 

✔️Allocation Scheme

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

---

✏️ Global vs. Local Replacement

✔️Global replacement

• Replace 시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다
• Process별 할당량을 조절하는 또 다른 방법
• FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
• Working set, PFF 알고리즘 사용

 

✔️Local replacement

• 자신에게 할당된 frame 내에서만 replacement
• FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영 시 

---

✏️ Thrasing

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

Thrasing Diagram

• 동시에 메모리에 올라가 있는 프로세스의 개수를 조정해 줘서, 메모리 확보를 하게끔

---

✏️ Working-Set Model

✔️Locality of reference

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다
• 집중적으로 참조되는 해당 페이지들의 집합을 locality set이라 함

 

✔️Working-set Model

• Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 페이지들의 집합을 Working Set이라 정의함
• Working Set 모델에서는 프로세스의 Working Set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 프레임을 반납한 후 swap out(suspend)
• Thrasing을 방지함
• Multiprogramming degree를 결정함

---

✏️ Working-Set Algorithm

✔️ Working set의 결정

• Working set window를 통해 알아냄
• Window size가 $\Delta$인 경우
  • 시각 $t_i$에서의 Working set WS ($t_i$) - Time interval [$t_i$, -$\Delta$, $t_i$] 사이에 참조된 서로 다른 페이지들의 집합
  • Working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림(즉, 참조된 후 $\Delta$ 시간 동안 해당 page를 메모리에 유지한 후 버림)

---

 ✏️ 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