가상 메모리

목차

가상 메모리

가상 메모리란?

• 가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 프로그램이 사용하는 주소 공간을 실제 물리적 메모리 크기와 무관하게 만들어주고 외부 단편화를 해결해주는 방법입니다. 
  • 이를 통해 물리적 메모리보다 큰 프로그램을 실행할 수 있게 하고, 메모리를 효율적으로 관리할 수 있도록 도와줍니다.
  • 대표적인 가상 메모리 기법으로는 대표적으로 페이징과 세그멘테이션이 있습니다.

가상 메모리가 필요하게 된 배경

• 프로그램이 CPU에서 실행되려면 실행에 당장 필요한 부분이 메모리에 올라와 있어야합니다.
  • 여러 프로그램이 동시에 수행되는 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나눠서 사용해야 합니다.
  • 따라서 운영체제는 어떤 프로그램에게 어느 정도의 메모리를 할당할 것인지 정해주어야 합니다.
• 초기 컴퓨터 시스템에서는 프로세스별로 프로세스 크기만큼 연속적으로 메모리 공간을 할당하는 방식인 연속 메모리 할당 방식과 스와핑을 이용하여 메모리에 프로세스를 할당하였습니다.
  • 연속 메모리 할당 방식
    • 프로세스 크기만큼 메모리 공간에서 연속적으로 할당하는 방식입니다.
    • 최초 적합(first fit), 최적 적합(best fit), 최악 적합(worst fit) 방식이 있습니다.
      • • 예시

          • 

        • 최초 적합(first fit)
          • 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식

          • 

        • 최적 적합(best fit)
          • 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식 

          • 

        • 최악 적합(worst fit)
          • 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식 

          • 

  • 스와핑(Swapping)
    • 보조기억장치의 일부 영역인 스왑 영역으로 현재 실행되지 않는 프로세스가 메모리에서 옮겨집니다. (스왑 아웃 : 스왑으로 나가다.) (메모리 → 스왑영역(보조기억장치))
    • 다시 프로세스가 실행될 때는 스왑영역에서 메모리로 옮겨옵니다. (스왑인 : 스왑에서 들어오다.) (스왑영역(보조기억장치) → 메모리)
    • 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들이 동시 실행이 가능합니다.
• 연속 메모리 할당 방식과 스와핑을 이용하여 메모리에 프로세스를 할당하는 방식은 메모리 한계나, 외부단편화 문제가 있습니다
  • 이러한 문제를 해결할 수 있는 방법이 가상 메모리 기법입니다.
  • 가상 메모리 관리 기법에는 대표적으로 페이징과 세그멘테이션이 있습니다.

메모리의 한계

• 연속 메모리 할당 방식이더라도 스와핑을 이용하면 여러 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에서도 프로세스들이 동시 실행이 가능했습니다.
• 하지만 여전히 단일 프로세스가 메모리 주소 공간의 크기보다 크다면 연속 메모리 할당 방식에서는 실행이 불가능합니다.

외부 단편화(external fragmentation)

• 연속 메모리 할당 방식은 프로세스들이 실행되고 종료되기를 반복하다 보면 메모리 사이사이에 빈 공간들이 생기게 됩니다.
• 이러한 빈 공간들은 분명 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래하고, 결국 메모리 낭비로 이어집니다. 이러한 현상을 외부 단편화라고 합니다.
  • 아래 예시를 보면 빈 공간이 있지만, 그 공간이 작아 다른 프로세스들을 적재하기 어려운 공간이 생겨나게 됩니다. 이러한 현상을 외부 단편화라고 합니다. 
  • 
• 외부 단편화를 해결하기 위한 방법으로 메모리를 압축하는 방법이 있습니다. (메모리 조각 모음이라고도 합니다.)
  • 메모리 내에 저장된 프로세스들을 재배치해서 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법입니다.
  • 하지만 이러한 방식은 압축할 때 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하면서 많은 단접이 있습니다.

페이징

• 가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 프로그램이 사용하는 주소 공간을 실제 물리적 메모리 크기와 무관하게 만들어주고 외부 단편화를 해결해 주는 방법이었습니다.
  
  • 연속 메모리 할당 방식에서 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문입니다.
• 페이징은 이러한 문제를 해결하기 위해 프로세스 메모리의 물리 주소 공간을 프레임(frame) 단위로 자르고, 프로세스의 논리 주소 공간을 페이지(page) 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법입니다. 이런 식으로 잘게 나눠주면 메모리 중간에 비어 있던 공간인 외부 단편화 문제를 해결할 수 있습니다.
  • 

페이징 예시

• 프로세스의 메모리 공간 분할 예시
  
  • 8GB의 주소 공간을 가지는 프로세스입니다. 페이지 크기는 4KB일 경우 아래와 같이 하나의 프로세스의 공간은 분할됩니다.
  • 실제 메모리 공간은 4GB이지만 실행하고자 하는 프로그램을 일부만 메모리에 적재하여(나머지는 보조기억장치의 스왑영역에 적재) 실제 메모리 공간보다 큰 프로세스를 실행할 수 있습니다. (유효비트가 1이면 실제 메모리에 올라간 것이고, 0이면 보조기억장치에 있는 상태입니다.)
  • 
    
    • 연속 메모리 할당 방식에서 사용했던 스와핑 방식을 페이징 방식에서는 프로세스전체가 스왑영역으로 넘어가는 것이 아닌 페이지 단위로 쪼개 현재 실행하지 않는 부분만 스왑영역으로 보냅니다.
    • 스왑인 : 스왑영역(보조기억장치) → 메모리
    • 스왑아웃 : 메모리 → 스왑영역(보조기억장치)
    • 페이징에서는 스왑인을 페이지인, 스왑아웃을 페이지아웃이라고 부르기도 합니다.

내부 단편화(internal fragmentation)

• 페이징을 통해 외부 단편화 문제를 해결할 수 있지만, 내부 단편화문제를 야기할 수 있습니다.
• 페이징은 프로세스의 논리 주소 공간을 일정한 크기 단위로 잘라서 진행합니다. 그런데 만약 페이지 크기는 4KB인데 프로세스의 크기가 110KB라고 한다면 110%4 = 2로 2KB가 남게 됩니다. 
  • 이런 식으로 남게 되는 공간을 내부 단편화라고 합니다.
• 내부단편화를 줄이기 위해서는 페이지크기를 더 잘게 쪼개는 방법이 있습니다. 하지만 이렇게 할 경우 문제는 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비됩니다. 그렇기에 내부 단편화를 적당히 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요합니다.
  • 리눅스 페이지 크기 알아내기

    • getconf PAGESIZE

페이지 테이블 읽어오기

• 위 예시처럼 프로세스마다 각자의 페이지 테이블을 가지고 있고, 해당 페이지 테이블엔 메모리에 적재되어 있습니다.
  • 페이지 테이블이 있는 주소는 CPU내의 페이지 테이블 베이스 레지스터(PTBR: Page Table Base Register)가 가리키고 있습니다. (각 프로세스의 PCB에 기록되었다가, 프로세스의 컨텍스트 스위칭이 일어날 때 다른 레지스터와 마찬가지로 함께 변경됩니다.)
• 하지만 단순히 메모리에만 저장할 경우 메모리 내의 프레임에 접근하기 위해서는 메모리를 총 2번 접근해야 해서 메모리 접근 시간이 두 배로 늘어나게 됩니다.
  • 메모리에 있는 페이지 테이블 보기 위해 메모리 접근 한번, 그렇게 알게 된 프레임에 접근하기 위해 다시 한번 총 2번 접근해야 합니다.
• 이러한 시간을 줄여주기 위해 CPU 곁에(일반적으로 MMU내에) 있는 TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둡니다.
  • TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장합니다. 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장합니다.
  • CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB 히트(TLB hit)라고 합니다. (이 경우에는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없습니다. 따라서 한 번만 메모리에 접근하면 됩니다.)
  • 하지만 만일 페이지 번호가 TLB에 없을 경우 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근해야 합니다. 이를 TLB 미스(TLB miss)라고 합니다.
  • 
• 여기서 한 가지 더 생각해봐야 할 점이 있습니다. 페이지 테이블의 크기는 생각보다 작지 않다는 것입니다. 이렇게 큰 테이블을 메모리에 두는 것은 큰 메모리 낭비가 될 수 있습니다. 따라서 프로세스를 이루는 모든 페이지 테이블 정보를 메모리에 유지하지 않을 수 있는 계층적 페이징(hierachical pageing) 방법이 등장했습니다.
  • 계층적 페이징 기법은 페이지 테이블을 여러 단계의 페이지를 두는 것입니다. (계층적 페이징은 이런 이유로 다단계 페이지 테이블 기법이라고도 합니다.)
  • 프로세스의 페이지 테이블을 프로세스의 논리적 주소를 페이지로 자르듯이 여러 페이지로 자르고, 바깥쪽에 페이지 테이블을 하나 더 두어 잘린 페이지 테이블의 페이지들을 가리키게 하는 방식입니다.
  • 마찬가지로 바깥쪽 테이블만 메모리에 저장해 두고 잘라진 테이블들은 보조기억장치에 저장해 두었다가 필요시에 꺼내서 사용하면 됩니다.
    • 
  • 단, 이런 식으로 계층이 많아질수록 메모리 참조 횟수가 많아지기 때문에 속도적인 측면에서는 성능이 하락할 수 있습니다.

페이징에서의 주소 변환

• 하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있습니다.(예를 들면 한 페이지 크기를 4KB라고 한다면 4KB=4x1024= 4096Byte로 총 4096개의 메모리 주소를 가지고 있습니다.) 따라서 특정 주소에 접근하기 위해서는 아래와 같은 두 가지 정보가 필요합니다.
  • 어떤 페이지 혹은 프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
• CPU 명령 예시
  • 프로세스 A의 페이지 2에서 10만큼 떨어진 주소에 접근할래!
  • 이럴 경우 페이지 2가 가리키는 물리주소 프레임 번호를 페이지 테이블을 통해 찾고 해당 프레임에서 10만큼의 변위를 가진 메모리 주소로 접근합니다.

페이징의 이점 - 쓰기 시 복사(COW : Copy On Write)

• 페이징은 외부 단편화를 해결한다는 점 이외에도 프로세스 간에 페이지를 고유할 수 있다는 이점이 있습니다.
• 멀티프로세스에서 프로세스를 fork 하여 동일한 프로세스가 두 개가 복제되면 코드 및 데이터 영역을 비롯한 모든 자원이 복제되어 메모리에 적재되어야 했습니다. (멀티프로세스는 자원을 공유하지 않기 때문입니다.)
  • 메모리 낭비
• 하지만 만약 부모 프로세스와 자식 프로세스가 메모리에 어떠한 데이터도 쓰지 않고 그저 읽기 작업만 이어나간다면  그냥 그대로 새롭게 메모리 할당을 할 필요 없이 해당 페이지를 그대로 가리키고 있으면 됩니다. 단지 부모 프로세스나 자식 프로세스 둘 중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지를 별도의 공간으로 복제하여 수정하면 됩니다. 
  • 이러한 작업을 통해 프로세스 생성 시간을 줄이는 것은 물론 메모리 공간 절약도 가능합니다.
  • 
  • (쓰기 작업 요청 시)
  • 

페이지 폴트(page fault)

• CPU가 유효 비트 0인 페이지로 접근하면 페이지 폴트(page fault)라는 예외(Exception)가 발생합니다.
  • 페이지 폴트가 발생하면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 속도가 느려집니다.
  • 따라서 페이지를 적절하게 메모리에 올려주는 것이 중요합니다. → 페이지 교체 알고리즘, 프레임 할당
• CPU가 페이지 폴트를 처리하는 과정은 하드웨어 인터럽트를 처리하는 과정과 유사합니다.
  • CPU는 기존의 작업 내역을 백업
  • 페이지 폴트 처리 루틴을 실행
  • 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
  • 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근가능

요구 페이징 (페이지 교체 알고리즘, 프레임 할당)

• 운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록 기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 하고, 프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야 합니다.
• 요구 페이징(demand paging)
  • 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법입니다. (이름 그대로 실행에 요구되는 페이지만 적재하는 기법입니다.)
  • 요구 페이징의 기본 양상
    • CPU가 특정 페이지에 접근하는 명령어 실행
    • 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근
    • 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생
    • 페이지 폴트 처리 루틴(해당 페이지를 메모리에 적재하고 유효비트를 1로 설정) 진행
    • 다시 CPU가 특정 페이지에 접근하는 명령어부터 반복하며 실행
  • 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당을 효율적으로 해줘야 합니다.
    • 페이지 교체 : 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠간 메모리가 가득 차게 됩니다. 이때 당장 실행에 필요한 페이지를 적재하기 위해서는 메모리에 적재된 페이지 중 일부를 보조기억장치로 내보내야 합니다. 이때 어떤 것을 내보내는 것이 최선일지 결정해줘야 합니다. (페이지 교체 알고리즘)
    • 프레임 할당 : 한정된 메모리 공간에서 프로세스별로 어떻게 프레임 공간을 할당해 줄지 정해야 합니다.
    • 결국 두 방법의 목적은 모두 페이지 폴트를 적게 발생하는 것이 목적입니다.
      • 페이지 폴트가 발생하면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 속도가 느려집니다.
      • 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱(thrashing)이라고 합니다.
        • 즉, 스래싱이란 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제입니다.
• 페이지 교체 알고리즘
  • 페이지 교체 알고리즘을 제대로 이해하기 위해서는 페이지 폴트 횟수를 알 수 있어야 합니다. 이때 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있습니다.
    • 페이지 참조열의 개념은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미합니다.
    • 예를 들어 CPU가 2 2 2 3 5 5 5 5 3 3 7과 같은 순서로 페이지에 접근했다고 하면 여기서 연속된 페이지를 생략한 페이지열, 다시 말해 2 3 5 3 7 이 페이지 참조열이 됩니다.
    • 페이지 참조열만 고려하는 이유는 중복된 페이지에 접근하는 행위는 페이지 폴트를 발생시키지 않기 때문입니다.
  • FIFO 페이지 교체 알고리즘
    • 가장 먼저 올라온 페이지부터 내쫓는 방식
    • 예시(프레임 3개, 참조열 : 2 3 1 3 5 2 3 4 2 3)
      • 
  • 최적 페이지 교체 알고리즘
    • CPU에 의해 참조되는 횟수를 고려하는 방식. 즉, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
    • 하지만 실제 구현이 어렵습니다. 앞으로 오랫동안 사용되지 않을 페이지를 예측하기란 어렵기 때문입니다. 따라서 이 자체를 운영체제에서 사용하기보다는, 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용됩니다. 
      • 즉, 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트의 하한선으로 간주하고, 최적 페이지 교체 알고리즘에 비해 얼마큼 페이지 폴트 회숫가 발생했느냐를 통해 페이지 교체 알고리즘을 평가
    • 예시(프레임 3개, 참조열 : 2 3 1 3 5 2 3 4 2 3)
      • 
  • LRU 페이지 교체 알고리즘 (Least Recently Used Page Replacement Algorithm)
    • 최적 페이지 교체 알고리즘(가장 오랫동안 사용되지 "않을" 페이지 교체)을 구현하기 어렵기 때문에 이와 비슷하게 가장 오랫동안 사용되지 "않은" 페이지를 교체하는 방식입니다. 
    • 예시(프레임 3개, 참조열 : 2 3 1 3 5 2 3 4 2 3)
      • 
• 프레임 할당
  • 프로세스가 사용할 수 있는 프레임 수가 적을 경우 페이지 폴트가 자주 발생하고 반대로 프로세스가 사용할 수 있는 프레임 수가 많으면 페이지 폴트 빈도는 감소합니다.
  • 즉, 프로세스의 수가 많아지게 되면 프로세스마다 할당할 수 있는 프레임수가 적어지기 때문에 페이지 폴트가 자주 발생하게 될 것입니다. 
    • 어느 정도의 멀티 프로세스의 수는 CPU 이용률을 증가하지만, 너무 많은 프로세스는 메모리를 많은 프로세스에게 나누어주다 보니 할당할 수 있는 프레임 수가 적어져 빈번한 페이지 폴트가 발생해 성능하락이 발생할 것입니다. (스래싱 상태(지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제))
    • 
  • 따라서 각 프로세스가 필요로 하는 최소한의 프레임 수를 보장하여 스래싱이 발생하지 않도록 해야 합니다.
  • 프레임 할당 방식
    • 정적 할당 방식(단순히 프로세스의 크기와 물리 메모리의 크기만 고려한 방식) 
      • 균등 할당(equal allocation)
        • 모든 프로세스에게 균등하게 프레임을 제공하는 방식
        • 세 개의 프로세스에게 총 300개의 프레임이 있을 때, 각 프로세스에게 100개의 프레임을 할당하는 방식(비효율적, 프로세스 크기를 고려하여 배분해야 효율적임)
      • 비례 할당(proportional allocation)
        • 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스 크기가 작으면 프레임을 적게 나눠주는 방식
        • 이 방법도 막상 효율적인 방식은 아닙니다. 프로세스의 크기가 크지만 막상 실행해 보니 많은 프레임이 필요하지 않을 수도 있습니다.
    • 동적 할당 방식(프로세스의 실행하는 과정에서 할당할 프레임 수를 결정하는 방식)
      • 작업 집합 모델(working set model)을 사용하는 방식
        • 프로세스가 일정 기간 동안 참조한 페이지 집합(작업 집합)을 기억해 최소 해당 작업 집합의 개수만큼의 페이지를 할당하여 빈번한 페이지 교체를 방지하는 방식입니다.
        • 보통 한 프로세스가 100개의 페이지로 이루어졌다고 해서 100개를 모두 고르게 참조하는 것이 아닌, 특정 시간 동안에는 몇몇 개의 페이지만을 집중적으로 참조하게 됩니다. 이를 이용하여 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 페이지 교체는 빈번하게 발생하지 않을 것입니다.
        • 예를 들어 CPU가 어떤 프로세스를 실행하는 동안 3초에 7개의 페이지를 집중적으로 참조했다면 운영체제는 그 프로세스를 위해 그 순간만큼만은 최소 7개의 프레임을 할당하면 됩니다.
        • 이때 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합(working set)이라고 합니다.
          • 
          • t1에서는 이 프로세스에게 최소 5개의 프레임을 할당해 주면 되고, t2에서는 최소 4개의 프레임을 할당해주면 됩니다.
      • 페이지 폴트 빈도(PFF : Page-Fault Frequency)를 사용하는 방식
        • 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있는 것이고, 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 가지고 있는 것입니다.
        • 이를 이용하여 적당한 프레임 수가 할당되는 페이지 폴트율의 상한선과 하한선을 정해 상한선을 넘어서면 프레임을 더 많이 할당해 주고, 하한선을 넘어가면 프레임을 회수하는 방식입니다.

세그멘테이션(segmentation)

• 세그멘테이션은 프로세스를 물리적 단위인 페이지가 아닌 논리적 단위인 세그먼트로 분할해서 메모리에 적재하는 방식입니다.
  • 돼지를 도축할 때, 페이징은 돼지를 같은 크기로 잘라서 보관하는 것이라면 세그멘테이션은 부위 별로 잘라서 보관하는 것입니다.
  • 예를 들면 코드, 데이터, 스택 등 논리적 구조로 분할하여 메모리에 적재합니다.
• 분할 방식을 제외하면 페이징과 세그멘테이션은 동일합니다. 세그멘테이션도 세그먼트 테이블을 가지고 있어 각 세그먼트의 시작 물리 주소를 통해 해당 세그먼트로 접근이 가능합니다.
  • 필요하지 않은 세그먼트들은 메모리에 로드되지 않고, 나중에 필요할때 보조기억장치에서 불러옵니다.
  • 세그먼트 그 크기 그대로 저장하기때문에 내부 단편화는 생기지 않지만 세그먼트 크기는 모두 다르므로 외부 단편화 문제가 생길수 있습니다.

출처

• 혼자 공부하는 컴퓨터 구조+운영체제