가상 메모리

‘운영체제와 정보기술의 원리’ 8장을 학습한 내용을 정리한 포스팅입니다

가상 메모리

가상 메모리

​ 운영체제는 프로그램이 자기 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원한다.

​ 이렇게 되면 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데 이러한 메모리 공간을 가상 메모리라고 부른다

운영체제는 어떤 식으로 프로세스에게 메모리를 할당 하는가?

• 모든 프로그램들에게 공평하게 같은 크기의 메모리를 할당하기 보다는 몇몇 프로그램들에게 집중적으로 메모리를 할당한 후 시간이 흐르면 이들에게서 메모리를 회수해서 다른 프로그램들에게 다시 집중적으로 할당하는 방식을 채택한다. 그 이유는 프로세스의 빠른 수행을 위해 프로그램마다 최소한 확보 해야하는 메모리의 크기가 존재하기 때문이다.
• 프로그램을 실행할 때 당장 수행해야 할 부분만 메모리에 올려놓고 나머지 부분은 스왑 영역에 내려놓고 필요할 때마다 메모리에 올라간 부분만 교체하는 방식을 사용한다
• 디스크의 스왑 영역이 사용될 수 있으므로 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 생각할 필요가 없어진다
• 프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 가상 메모리 기법은 요구 페이징 방식과 요구 세그멘테이션 방식으로 구현될 수 있다

요구 페이징 기법

• 프로세스를 구성하는 페이지 중에 당장 사용될 페이지만을 메모리에 올리는 방식을 말한다
  • 프로그램이 물리적 메모리의 용량 제약을 벗어날 수 있도록 하는 것이 주된 효용
• 메모리 사용량 감소, 프로세스 전체를 메모리에 올리는 데 드는 입출력 오버헤드 감소
• 유효-무효 비트를 두어 각 페이지가 메모리에 존재하는 지를 표시한다.

요구 페이징 기법의 페이지 부재 처리

CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 우리는 ‘페이지 부재’가 일어 났다고 한다

• CPU가 무효 페이지에 접근하면, MMU가 페이지 부재 트랩을 발생 -> CPU 제어권이 커널모드로 전환 -> 페이지 부재 루틴 실행

  페이지 부재 루틴

  1. 운영체제는 해당 페이지 접근이 적법한지를 체크 2. 적법하지 않은 경우 해당 프로세스 종료시키고, 적합한 경우 물리적 메모리에 비어 있는 프레임을 할당 받아 그 공간에 페이지를 읽어온다 3. 만약 비어 있는 프레임이 없다면 기존에 메모리를 사용하고 있는 페이지 중 하나를 스왑 아웃 시킨다 4. 물리적 메모리에 페이지를 읽어오는 과정은 I/O 과정이므로 다른 프로세스에게 CPU를 빼앗기고 blocked 된다 5. I/O가 완료되어 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정하고 봉쇄되었던 프로세스를 준비 큐로 이동 시킨다 6. 이 프로세스가 다시 CPU를 할당받으면 PCB에 저장해 두었던 값을 복원시켜 이전에 중단되었던 명령부터 실행을 재개한다

요구 페이징 기법의 성능

​ 요구 페이징에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도다

• 페이지 부재가 일어나면 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생하기 때문이다
• 페이지 부재 발생이 적을수록 요구 페이징의 성능은 향상될 수 있다
• 요청한 페이지를 참조하는 데 걸리는 유효 접근 시간으로 성능을 측정한다

페이지 교체

• 물리적 메모리에 빈 프레임이 존재하지 않을 시 메모리에 올라와 있는 페이지 중에 하나를 디스크로 쫒아내 메모리에 빈 공간을 확보하는 작업이 필요하다. 이것을 우리는 페이지 교체라고 한다
• 페이지 교체를 할 때에 어떠한 프레임에 있는 페이지를 쫒아낼 것인가를 결정하는 알고리즘을 교체 알고리즘이라고 한다
• 이 알고리즘은 페이지 부재율을 최소화하는 것이 목표다

교체 알고리즘

• 빌레드의 최적 알고리즘
  • 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫒아낸다
  • 미래에 페이지가 어떤 순서로 참조될지 미리 알고 있다는 전제 하에 알고리즘을 운영하므로 실제 시스템에서 온라인으로 사용할 수 없다 ( 오프라인 알고리즘 )
  • 어떠한 알고리즘 보다도 가장 적은 페이지 부재율을 보장하므로 다른 알고리즘의 성능에 대한 상한선을 제공한다

• FIFO 알고리즘
  • 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다
  • 물리적 메모리가 증가하더라도 페이지 부재가 증가할 수 있다 (이상 현상)

• LRU 알고리즘 (Least Recently Used)

  • 페이지 교체시 가장 오래 전에 참조가 이루어진 페이지를 내쫓는다

  

• LFU 알고리즘 (Least Frequently Used)

  • 페이지의 참조 횟수로 교체시킬 페이지를 결정한다. 즉 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적었던 페이지를 내쫓고 그 자리에 새로 참조될 페이지를 적재한다. 최저 참조 횟수를 가진 페이지가 여러 개 존재하는 경우에는 임의로 하나를 선정해 그 페이지를 내쫒는다
  • 페이지 참조 횟수를 계산하는 방식에 따라 Incache-LFU와 Perfect-LFU로 구현할 수 있다
    • Incache-LFU
      • 페이지가 물리적 메모리에 올라온 후부터 참조 횟수를 카운트 하는 방식이다. 따라서 페이지가 메모리에서 쫓겨났다가 다시 들어온 경우 참조 횟수는 1부터 새롭게 시작된다
    • Perfect-LFU
      • 메모리에 올라와 있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트한다
      • 페이지의 참조 횟수를 정확히 반영할 수 있지만 오버헤드가 상대적으로 더 크다

  

• 클럭 알고리즘

  • LRU 알고리즘과 LFU 알고리즘과는 달리 하드웨어적인 지원을 통해 동작한다(선정 속도가 빠르다)

  • LRU를 근사시킨 알고리즘으로 NUR(Not Used Recently), NRU(Not Recently Used) 알고리즘으로도 불린다

  • LRU 알고리즘이 가장 오래전에 참조된 페이지를 교체하는 것에 비해 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다

  • 대부분 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다

  • 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조 비트를 순차적으로 조사한다

  • 참조 비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다클럭 알고리즘은 참조 비트가 1인 페이지는 0으로 바꾼 후 그냥 지나가고 참조 비트가 0인 페이지는 교체한다

    

페이지 프레임의 할당

• 프로세스가 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지를 결정해야 한다
• 할당 알고리즘의 종류
  • 균등 할당 방식
    • 모든 프로세스에게 페이지 프레임을 균일하게 할당한다
  • 비례 할당 방식
    • 프로세스의 크기에 비례해 페이지 프레임을 할당하는 방식
  • 우선순위 할당 방식
    • 프로세시 중에서 당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분하여 전자 쪽에 더 많은 페이지 프레임을 할당하는 방식
• 할당 알고리즘만으로는 프로세스의 페이지 참조 특성을 제대로 반영하지 못할 수 있다. 현재 수행중인 프로세스의 수가 지나치게 많을 경우 프로세스당 할당되는 메모리량이 과도하게 적어질 수 있기 때문이다. 또한 반복문(loop)을 실행 중인 프로세스의 경우 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려놓는 것이 유리하다. 이와 같은 종합적인 상황을 고려해서 각 프로세스에 할당되는 페이지 프레임의 수를 결정할 필요가 있으며, 경우에 따라서는 일부 프로세스에게 메모리를 할당하지 않는 방식으로 나머지 프로세스들에게 최소한의 메모리 요구량을 충족시킬 수 있어야 한다

전역 교체와 지역 교체

• 전역 교체
  • 모든 페이지의 프레임이 교체 대상이 될 수 있는 방법
• 지역 교체
  • 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법

스레싱(Thrashing)

​ 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율이 크게 상승해 CPU 이용률 이 급격히 떨어질 수 있다. 이와 같은 현상을 스레싱이라고 부른다

• 스레싱이 발생 -> 운영체제는 메모리에 적재된 프로세스의 수(MPD)가 적다고 판단 -> 메모리에 더 많은 프로세스 적재

  -> 각 프로세스에 할당되는 메모리의 양이 급격히 감소 -> 페이지 부재 빈도수 증가 -> 무한 루프…

• 스레싱 발생을 방지하기 위해 MPD를 조절하는 알고리즘이 필요하다

MPD 조절 알고리즘

• 워킹셋 알고리즘
  • 프로세스는는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다. 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합이라고 한다
  • 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘을 워킹셋 알고리즘이라 한다
  • 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다. 그렇지 않을 경우에는 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃 시킨다
  • 워킹셋 윈도의 크기를 효과적으로 결정하는 것이 워킹셋 알고리즘의 핵심

• 페이지 부재 빈도 알고리즘
  • 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해 각 프로세스에 할당할 메모리량을 동적으로 조절한다
  • 어떤 프로세스의 페이지 부재율이 시스템에서 정해놓은 상한값을 넘게되면 이 프로세스에 할당된 프레임의 수가 부족하다는 것을 의미하므로 이 프로세스에게 프레임을 추가로 더 할당한다. 이 때, 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라와 있는 프로세스의 수를 조절한다.
  • 이런 방식으로 메모리 내에 존재하는 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높인다.

ref. 운영체제와 정보기술의 원리

ref. LFU, LRU Algorithm

ref. FIFO

ref. Thrashing

ref. 이미지