운영체제(9) - Virtual Memory(2)

‘운영체제’를 공부하여 정리한 내용입니다.

4. Page Replacement

접근법

• 위에서 page fault trap이 발생하면, 디스크에서 page를 찾아서 메모리의 free frame(빈 프레임) 에 넣어주어야 한다고 언급했다.

  • 그렇다면 free frame이 없다면 어떻게 해야할까?

• 두 가지 접근이 있다.

  1. 페이징을 요청한 프로세스를 종료시킨다.
     • 이는 좋은 접근이 아니다.
     • 우리가 virtual memory를 구현한 이유는 한정된 물리 메모리 자원에서 많은 프로세스를 지원하기 위한 것이었고,
     • 사용자는 Logical memory에만 신경쓰고 이런 물리적인 paging에 대한 부분을 절대 신경쓰지 않을 수 있도록 해주어야 하기 때문이다.
     • 이 신경을 쓰지 않는다는 의미, 혹은 User로 부터 hiding한다고 표현하는 이 의미는 User가 이 시스템의 구체적인 Spec을 몰라도 인터페이스의 정의로 원하는 목적을 달성할 수 있도록 해주어야 한다는 의미이다.
     • 그렇기에 이 방법은 쓰지 않는것이 좋다. - 현재 쓰지 않을 확률이 높은 페이지를 swap-out 시킨다.
     • 이렇게 하면 일단 multiprogramming을 끌고 갈 수 있다.
     • 이 선택은 앞의 선택에 비해서 좀 더 본래의 목적을 잃지않고 동작하게 할 수 있다.

주의

• 기본적으로 pager가 page를 swap-out 시키는 작업이 있다는 것은, 디스크에 두 번 접근한다는 의미이다.
  1. Free frame을 만들기 위해 기존에 존재하는 page를 디스크로 옮기는 과정
  2. 만들어진 Free frame으로 적재할 page를 올릴 때.
• 하지만, 만약에 free frame을 만들기 위해서 swap out 시킬 page의 내용이 본래 디스크에 저장된 내용과 차이가 없다면, 디스크로 옮기지 않고 그저 frame에서 지우는 작업 만으로 swap out과 같은 효과를 낼 수 있다.
  • 이러한 상황을 하드웨어적으로 서포트하기 위해서 우리는 modify bit라는 것을 두고 page가 메모리에 적재된 이후 수정된 적이 있는지 없는지 확인할 수 있도록 한다.
    • modify bit == 0: 메인 메모리에서 Swap out하기로 한 페이지의 내용이 수정된적이 없다는 의미로 보조 기억장치에 있는 내용과 메모리에 올라가 있는 내용에는 차이가 없다. 따라서 그냥 메인 메모리에서 내용을 지우기만 하면 된다.
    • modify bit == 1: 메인 메모리에서 Swap out하기로 한 페이지의 내용을 보조 기억장치에 Backup해 두어야 한다.

해결해야 하는 문제

• Frame Allocation Algorithm
  • 동작시켜야 하는 여러 프로세스가 존재하는 경우, 각 프로세스에는 얼마나 많은 프레임을 할당해야 할지 결정해야 한다.

• Page Replacement Algorithm

  • 페이지 교체가 필요할 때마다 어떤 페이지를 교체해야 할지 결정해야 한다.
  • 단순히 생각해보면 앞으로 더이상 필요없을 가능성이 높은 페이지를 교체하는 것이 경제적이다.
  • Swap out된 페이지가 다시 필요해지면 다시 메모리로 올리는데에 비용이 드니까 말이다.
• 이 두 알고리즘을 개선시키기만 해도 전체적인 Demanding Paging 시스템의 퍼포먼스를 크게 올리는 것이 가능하다.

Page Replacement Algorithm

• 우선 상황을 분석하는 방법을 알아보자.

  • 프로세스가 참조하는 주소열이 다음과 같다고 생각하자.

    0100 0432 0101 0612 0102 0103 0104 0101 0611 0102 0103
    0104 0101 0610 0102 0103 0104 0101 0609 0102 0105
    

  • page offset이 100 byte를 표현한다면, 즉, page의 크기가 100byte라면, 이 열은 다음과 같은 순서로 page를 참조한다는 것을 알 수 있다.

    1 4 1 6 1 1 1 1 6 1 1
    1 1 6 1 1 1 1 6 1 1
    (위의 값을 100단위로 나누면 된다)
    

  • 이 때, page를 연속으로 참조하는 경우를 압축하여 표현하면 다음과 같은 순서로 Page를 참조한다는 것을 알 수 있다.

    1 4 1 6 1 6 1 6 1 6 1 (최종 page 참조 리스트)
    

• 우리가 가진 메인 메모리가 3개 이상의 frame을 가지고 있다.

  • 이 경우, 1, 4, 6 page가 pager를 통해 메인 메모리로 swap in이 될 때, 항상 free frame이 존재할 것이다.
  • 이 때는 각 페이지를 최초로 reference 하는 경우 한번씩, 총 3번의 page fault만 일어난다. (총 3개의 page 접근)
• 우리가 가진 메인 메모리가 1개의 frame을 가지고 있다.
  • 이 경우는 최초 page 참조를 포함해서, 이전과 다른 page에 접근할 때는 무조건 page fault가 일어난다.
  • 그래서 총 11번의 page fault가 일어난다. (바로 위에서 최종적로 정리한 page 참조 리스트 참고)

• 종류

  • FIFO Page Replacement

    • 가장 오랫동안 있었던 페이지를 swap out 시키는 것
    • 이는 조금만 생각해봐도 문제가 있는 것을 알 수 있다: 자주 사용되는 page는 빨리 메모리에 들어왔다고 해서 swap out시키면 안된다.
      • 그러면 후에 자주 참조되면서 계속 page fault가 일어나고, 결과적으로 지연을 더욱 증가시키는 결과를 낳는다.
      • 이렇게 Page Replacement로 오히려 퍼포먼스가 떨어지는 모순적인 상황을 Belady’s anomaly라고 부른다.

  • Optimal Page Replacement

    • 존재하는 모든 알고리즘 중에서 가장 낮은 page fault rate를 가진다.
    • 앞으로 가장 오랫동안 사용되지 않을 page를 찾아서 Replace하는 알고리즘이다.
      • 위에서 말한 문제점을 정확하게 해결한다.
    • 아쉽게도 이는 실제 문제에서는 사용하기가 매우 어렵다.
      • 앞으로 언제 사용될지에 대해서 파악해야 하는데 이는 실제 프로세스들의 동작 사이에서 짧은시간 안에 파악하는 것이 거의 불가능한 Task이기 때문이다.
    • 그래도 모든 공학이 그렇듯이, 우리는 이렇게 최적의 문제 해결방법을 안다면 이를 근사(approximate)하는 해결책을 찾아볼 수 있다.
      • 이 때, 근사하는 해결책은 실생활에 사용가능할 정도로 time complexity가 충분히 작아야 한다.

  • LRU page Replacement

    • LRU: Least-Recently-Used 알고리즘이다.

    • 위의 Optimal Algorithm과 비교하여 설명하면 다음과 같다.

      • Optimal Algorithm: 앞으로 오랫동안 참조하지 않을 page를 Swap out
      • LRU Algorithm: frame에 올라온 이후로 오랫동안 참조되지 않은 page를 Swap out
        • 프로세스의 동작은 기본적으로 특정 시간에는 특정 부분을 지속적으로 참조하다가 그 시간 구간을 넘어가면 더 이상 참조하지 않는 경우가 많다: Locality of reference
        • 참고: 운영체제(9) - Virtual Memory(1) - 2. Demand Paging - 연속적으로 실행되는 명령어가 계속 다른 page를 요구하는 경우는 어떠한가?
        • 이런 경험을 기반으로, 다음과 같은 Assumption을 할 수 있다: 이 때까지 오랫동안 참조되지 않은 page는 앞으로도 참조될 가능성이 작다고 판단하는 것이다.
    • 구현 방법
      • 간단하게는 각 frame에 대해서 계수기를 두고 가장 오랫동안 사용되지 않은 frame을 찾는 것이다.
        • 각 frame의 계수값을 비교하는 알고리즘이 필요하다.
      • Stack을 사용해서 매번 최근에 참조되는 frame을 stack의 꼭대기로 옮기는 것이다.
        • 이렇게 구현해두면, Stack의 바닥(Bottom)에 있는 frame은 언제나 가장 오래전에 참조된 frame인 것을 알 수 있다.
        • 이 때는 stack의 중간의 값을 빼는 알고리즘이 필요하고 주로 double linked list를 사용한다.
    • 문제점
      • 다만 이 작업은 매번 페이지가 참조될 때 일어나야 한다.
        • 이를 SW적으로 구현하면 너무 느려지기에 알맞지 않다.
        • HW로 서포트하기에는 비용이 들어간다.
      • 그래서 이를 온전히 지원하기 보다는 이를 또 한번 approximate한다.
        • 이번에는 최대한 사용 가능한 방식으로!
  • LRU Approximation page Replacement
    • 위의 방식을 온전하게 사용할 수 없기에 많은 OS는 위의 개념을 사용해서 Approximate한 방법을 사용한다.
      • Additional-Reference Bits Algorithm
        • 각 page가 저장된 frame이 reference bit라는 것을 가지고 있다고 생각하자
          1. OS가 메인메모리에 있는 모든 frame의 reference bit를 0으로 초기화한다.
          2. 프로세스가 돌면서 참조된 frame들은 reference bit가 1이 된다.
          3. 프로세스가 돌던 도중 일정 시간이 지나면 timer interrupt가 발생한다.
          4. 그리고 각 frame이 가진 reference register의 값을 1bit right shift한다.
          5. 그리고 각 frame이 가진 reference register의 MSB를 그 frame의 reference bit로 채운다.
          6. 그 후, 1번으로 돌아가고 이 과정을 반복한다.

             reference_register >> 1; // 이 때, reference register는 8bit register
             reference_register | b1000_0000; // b는 이진수를 의미하며, 이 식은 레지스터의 MSB를 1로 채우고 나머지 값은 유지한다는 의미이다.
             

        • 이 상황에서 page fault가 일어나면 각 frame의 reference register를 확인하고 부호가 없는 수를 기준으로 작은 수들 가운데서 희생할 frame(page)을 선택할 수 있게 된다.
        • 이 때, 부호가 없는 수를 기준으로 왜 작은 수를 선택해야 하는지는 스스로 생각해보자
      • Second-Chance Algorithm (& Enhanced version)
        • (추후 업데이트)
  • Counting-Based Page Replacement 및 다른 알고리즘
    • (추후 업데이트)

5. Allocation of Frame

• (추후 업데이트)

Global vs. Local Allocation

• 이건 중요한 내용이라 우선적으로 추가한다.

• Global Allocation이라는 의미는 Swap out 시킬 frame을 전체 프로세스에 할당된 frame에서 찾는 것이다.

• Local Allocation이라는 의미는 Swap out 시킬 frame을 현재 Swap in하고자 하는 page의 프로세스에게 할당된 frame 안에서 찾는 것이다.

  • 이렇게 되면 이 작업은 다른 프로세스의 동작에는 영향을 주지 않는다.

• 많은 OS에서는 Global Allocation 방식을 많이 사용한다.

  • 이유는 다음에 자세히 소개하겠다.

• 위에서 알고리즘을 소개할 때는 이 Allocation방식을 제대로 고려하지 않고 설명했다.

  • 그냥 Global Allocation이라고 생각하고 읽는 것이 잘 읽힐 것이다.
  • 그렇게 생각하면서 정리했다.

6. Thrashing

발생원인

• 만약 현재 메인 메모리에 올라와 있는 모든 page가 활발하게 참조되는 page들이라고 가정해보자.

  • 이 경우 특정 프로세스의 page가 Swap in할 때, 결과적으로 활발하게 참조되는 것들 중에서 하나를 swap out하게 된다.
  • 이 상황에는 결과적으로 얼마 시간이 지나지 않아 방금 swap out한 page때문에 page fault가 발생한다.
  • 그리고 이 상황은 아주 자주 일어나게 된다.

• 위와 같은 상황에는, paging작업이 과도하게 많이 일어난다.

  • 이런 과도한 paging 작업을 우리는 Thrashing이라고 부른다.

• 결과적으로 퍼포먼스를 심각하게 떨어뜨린다.

  • 가끔 컴퓨터를 사용하다가, 마우스가 갑자기 너무 느리게 움직이는 상황을 본 적이 있을 것이다.
  • 이 상황이 바로 Thrashing 상황일 가능성이 높다.

(NULL)

• (추후 업데이트)

해결 방안

• 최근의 OS는 이걸 억지로 해결하지 않는다.
  • Thrashing이 일어나고 있는것은 User가 가장 잘 알 수 있고, 이를 해결하는 방법은 결과적으로 필요없는 프로세스를 줄이는 것이 가장 직접적이기 때문이다.
  • 그래서 우리는 이 상황에는 작업관리자를 열고, 쓰지 않는 프로그램을 죽인다.