가상 메모리 - 클락 알고리즘, 스레싱

가상 메모리

• 프로그램이 물리 메모리 크기에 의해 제약 받지 않도록 하기 위해, 프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능하도록 하는 기법
• CPU가 프로세스를 실행하다 어떠한 페이지를 읽어와야 할 경우
  • 프로세스에 존재하는 논리적 주소를 토대로 페이지 테이블을 확인
  • 만약 해당 엔트리가 valid하다면
    • 페이지가 물리 메모리에 올라와 있단 뜻으로 데이터를 읽어올 수 있음
  • 만약 해당 엔트리가 invalid하다면
    • 페이지가 물리 메모리에 올라와 있지 않다는 뜻으로 페이지를 디스크에서 읽어와 물리 메모리에 쓰는 작업이 필요
      • 여기서 만약 물리 메모리가 꽉차 있어 더이상 페이지를 추가할 공간이 없다면
        • 페이지 교체 알고리즘 필요

페이지 교체 알고리즘

Optimal, FIFO, LRU(Least Recently Used), LFU(Least Frequently Used), …

그런데… 정말로 Paging System에서 LRU와 LFU를 사용할 수 있을까?

• 주소 변환을 했을 때 해당하는 페이지가 이미 물리 메모리에 올라와 있다면?
  • 물리 메모리에서 직접 내용을 읽어 CPU로 가져감
  • 이러한 과정에서 운영체제는 하는 일이 없음 ⇒ 주소 변환은 하드웨어적으로 일어나는 일이기 때문에
• 주소 변환을 했을 때 해당하는 페이지가 물리 메모리에 없다면?(=Page Fault)
  • 디스크 접근(I/O)이 필요로 하기 때문에 Trap이 발생
  • CPU의 제어권이 프로세스 A로 부터 운영체제로 넘어감
  • 운영체제가 디스크에서 페이지를 읽어, 물리 메모리에 저장
  • 그 과정에서 만약 물리 메모리가 꽉 차있다면, 교체할 페이지를 찾아야되고 이 과정에서 페이지 교체 알고리즘 사용
  • 운영체제가 가장 오래전에 참조된 페이지, 가장 참조 횟수가 적은 페이지를 찾을 수 있는가?
    • 알 수 없다.
    • 프로세스가 요청한 페이지가 이미 물리 메모리에 올라와 있는 경우 운영체제에게 CPU가 넘어가지 않고 하드웨어적으로 주소 변환을 한 뒤 끝내버린다
    • 그렇다면 해당 페이지의 접근 시간을 운영체제가 알 수 없게 된다
    • Page Fault를 통해 CPU 제어권이 운영체제에게 넘어가야만, 페이지 접근 시간을 알 수 있다

• Page Fault가 난 상황에서는 운영 체제가 이런식으로 데이터를 조작해줌으로써 페이지 참조 상황을 업데이트할 수 있음
• 그렇지만 Page Fault가 나지 않는다면 CPU가 운영체제에게 넘어오지 않기 때문에 데이터를 변경할 수 없다
• 그렇기 때문에 어떤 페이지가 가장 최근에 참조되었는지, 어떤 페이지의 참조횟수가 많은지를 알 수 없다
• 즉, Paging System(=Virtual Memory System)에서는 사실 LRU, LFU 알고리즘을 사용할 수 없다
  • 대신 Buffer Caching이나 Web Caching에서는 사용할 수 있다

그렇다면 어떤 알고리즘을 사용하는가? - Clock Algorithm

• LRU의 근사 알고리즘
• Second Chance Algorithm, NUR(Not Used Recently), NRU(Not Recently Used)라고도 불림

• 주소 변환을 했을 때 해당하는 페이지가 이미 물리 메모리에 올라와 있다면?
  • 하드웨어가 해당 페이지에 접근을 할 때 마다, 페이지에 대한 Reference bit를 1로 세팅해줌으로써 참조되었다는 것을 표시
  • 이는 운영체제가 하는 것이 아니라 하드웨어가 하는 것!
• 주소 변환을 했을 때 해당하는 페이지가 물리 메모리에 없다면?(=Page Fault)
  • 하드웨어가 세팅해놓은 Reference bit를 참조
  • 만약 Reference bit가 1이라면 해당 bit를 0으로 바꾸고 다음 페이지로 넘어감
  • Reference bit가 0인 것을 찾을 때까지 반복

  → Reference bit가 0이라면 시계가 한바퀴 돌아오는 동안에 페이지에 대한 참조가 단 한번도 없었다는 것을 의미

  → 그렇기 때문에 Reference bit가 1이라면 최근에 참조 된 페이지라는 것을 보장

• Clock Algorithm의 개선
  • 페이지는 Read를 통해 참조될 수도 있지만 Write를 통해 참조될 수도 있음
  • 만약 Write 작업을 통해 변경된 페이지가 있다면 하드웨어가 modified bit를 1로 세팅
  • 이후 해당 페이지의 reference bit가 0이라 교체당할 때, modified bit를 확인함으로써 해당 페이지가 물리 메모리로 올라온 이후 변경된 적이 있는지를 확인
    • modified bit가 1이라면 물리 메모리에 올라 온 후 변경된 적이 있다는 것
    • 그렇다면 해당 페이지를 교체할 때 디스크에 변경 사항을 저장하고 제거해야하기 때문에 교체 비용이 더 비싸게 됨(=추가적인 I/O 비용이 수반)
    • 그렇다면 삭제하지 않고 넘어간 후 reference bit와 modified bit가 0인 페이지를 삭제
• 가장 오래전에 참조된 페이지를 교체하지는 못함, 즉 LRU와 완전히 동일하게 동작하지는 않음 그렇지만 어느정도 LRU와 비슷한 효과를 낼 수 있다

Thrashing

• 프로그램에 메모리가 적게 할당 되어, Page Fault가 빈번하게 일어나는 현상
• 각 프로그램에게 할당된 메모리가 적다 → 메모리에 올라와있는 프로그램의 수가 많다

• 프로그램이 처음에 하나만 실행된다면
  • CPU 이용률이 낮음 → 해당 프로그램이 I/O 작업을 하러 가면 CPU가 하는 작업이 없기 때문
• 그렇기 때문에 일반적으로 메모리에 프로그램이 올라갈 수록 CPU 이용률이 상승
• 그렇지만 특정 지점에 이르러서 갑자기 CPU 이용률이 급락하는데, 이러한 현상을 Thrashing 이라 한다
• 발생 이유
  • 프로세스가 원활하게 수행하기 위해 필요한 최소한의 page frame 수를 할당 받지 못함
  • Page Fault Rate가 매우 높아짐
  • 페이지 교체가 계속 이뤄지면서 I/O 작업 발생 → CPU 이용률 저하
  • 운영체제는 CPU 이용률이 적으니 프로그램을 더 올려야 된다고 판단
  • 또 다른 프로그램이 계속해서 추가
  • 이 악순환이 반복…
• 이를 막기 위해 degree of multiprogramming, 즉 프로그램의 개수를 조절해 줌으로써 프로그램이 어느정도 메모리 확보를 할 수 있게 해주어야 함

Working-Set Algorithm

• 프로그램들이 메모리에서 원활하게 수행되기 위해서는 어느 정도의 메모리 페이지를 가지고 있어야 함
• 프로세스들은 특정 시간동안 특정 장소만을 집중적으로 참조하는 경향이 있음(=시간, 공간 지역성)
• 이러한, 특정 시간에 집중적으로 참조되는 페이지들의 집합을 Working Set이라고 하자!
• 프로그램이 실행되기 위한 최소한의 Working Set이 존재하고, 만약 이 Working Set 전체가 메모리에 올라올 수 없는 상황이라면, 모든 frame을 반납하고 disk에 swap out 한다(=suspend 된다)
  • 예를 들어 디스코드를 실행하기 위한 Working Set의 사이즈가 5이고, 메모리는 지금 꽉차서 3개의 페이지 공간만 제공할 수 있다면, 디스코드는 실행되지 않는다.
• 이러한 과정을 통해 Multiprogramming degree를 조절한다.
• Working Set의 사이즈는 어떻게 알 수 있을까?

  • 과거를 통해 Working Set을 추정

    

  • 만약 window size가 10일 경우, 현재 시점부터 과거 10번째 참조된 페이지 까지는 프로그램의 Working Set이기 때문에 메모리에 올려놓아야 한다.
  • 그렇기 때문에 Working Set의 크기는 계속해서 변경됨
  • 이러한 방식은, 참조된 페이지를 특정 시간동안만 메모리에 유지한 후 버린다는 의미와 같음

Page Fault Frequency Algorithm

• 이 방식 또한 Multiprogramming degree를 조절하면서 Thrashing을 방지한다

• 현재 시점의 Page Fault, 각 프로그램의 Page Fault 수를 보면서 프로그램 당 페이지 수를 조절

  

• 일반적으로 프로그램에 할당되는 메모리가 커질수록 Page Fault 또한 줄어듦
• 각 프로그램마다 이러한 곡선의 가파른 정도가 다를 것
• 이러한 프로그램 마다, Page Fault가 일정 횟수 이상 발생하고 있다면 Working Set이 보장되어 있지 않는다고 판단해서 frame을 더 할당함
• 반면 어떤 프로그램은 Page Fault가 너무 발생하지 않는다면, 너무 과도한 메모리를 차지하고 있다고 판단해서 할당 frame 수를 줄임
• frame을 더 주어야 하는데 빈 frame을 없다면, 프로세스를 swap out 시킨다