14장 가상 메모리

14장 가상 메모리

프로세스 A가 A의 크기만큼 메모리 주소를 할당 받아서 연속적으로 배치되는데 이렇게 프로세스에 연속적인 메모리 공간을 할당하는 방식을 연속 메모리 할당 방식이라고 한다.

이와 같이 프로세스들을 메모리에 연속적으로 할당할 때 무엇을 고려해야하는지, 어떤 잠재적 문제가 있는지 알아보자!

---

14-1 연속 메모리 할당

스와핑

• 메모리에 적재된 프로세스들 중에서 현재 실행되지 않는 프로세스가 있을 수 있다.
  • 입출력 작업의 요구로 대기 상태가 된 프로세스. 오랫동안 사용되지 않은 프로세스
• 이러한 프로세스들을 임시로 보조기억 장치 일부 영역으로 쫓아내고 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식이다.
• 프로세스들이 쫓겨나는 보조기억장치의 일부 영역을 스왑 영역
• 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃
• 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인
  • 스왑 아웃되었던 프로세스가 다시 스왑 인 될 때는 스왑 아웃하기 전의 물리주소와는 다른주소로 적재될수있다.
• 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행 할 수 있다.

메모리 할당

• 프로세스는 메모리 내의 빈 공간에 적재되어야 한다.
• 메모리 공간이 여러 개 있다면 어디에 배치해야 할까?
• 메모리 공간에 프로세스를 연속적으로 할당하는 방식을 알아보자

1. 최초 적합

• 최초 적합 운영체제가 메모리 내의 빈공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그공간에 배치하는 방식이다.
• 발견하는 즉시 메모리를 할당하기 때문에 검색을 최소화하고 빠른 할당이 가능하다.

1. 최적 적합

• 최적 적합 운영체제가 빈 공간을 모두 검색한 후 적재될 수 있는 공간 중 가장 작은 공간에 배치하는 방식

1. 최악 적합

• 최악 적합은 운영체제가 빈 공간을 모두 검색한 후 적재될 수 있는 공간 중 가장 큰 공간에 배치하는 방식

외부 단편화

• 프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 메모리를 효율적으로 사용하는 방법이 아니다.
• 연속 메모리 할당은 외부 단편화라는 문제를 내포하고 있다.
• 프로세스들이 메모리에 연속적으로 할당되는 환경에서는 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈공간이 생긴다.
• 이때 이러한 빈공간들은 총 빈공간이 50mb이더라도 사이사이 30mb, 20mb 공간을 나눠 사용해야 하기 때문에 50mb 프로세스를 적재하기 어려운 상황을 초래하고 결국 메모리 낭비로 이어진다.
• 스와핑과 메모리 할당에도 외부 단편화가 발생한다.
• 외부 단편화를 해결할 수 있는 대표적인 방안은 압축하는 방법이 있다.
• 압축은 흩어져 있는 빈 공간들을 하나로 모으는 방식으로 작은 빈 공간들을 하나의 큰 빈공간으로 만드는 방법이다.
• 하지만 압축 방식은 단점이 있다.
  • 빈 공간을 하나로 모으는 동안 시스템을 중지해야하고 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며 어떻게 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다.
• 다른 해결 방안이 등장했는데 이것은 오늘날까지도 사용되는 가상 메모리 기법, 페이징 기법이다!

14-2 페이징을 통한 가상 메모리 관리

• 프로세스를 메모리에 연속적으로 할당하는 방식은 두가지 문제를 내포하고 있다.
  • 외부 단편화
  • 물리 메모리보다 큰 프로세스를 실행할 수 없다.
    • 4GB 메모리가 설치된 컴퓨터로는 4GB 이상의 프로그램을 실행할 수 없다.
• 가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다.
• 이를 가능하게 하는 가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있다.
• 현재 대부분의 운영체제가 사용하는 페이징 기법에 알아보자! 외부 단편화 문제도 해결가능하다.

페이징이란

• 메모리와 프로세스를 일정한 단위로 자르고 이를 메모리에 불연속적으로도 할당할 수만 있다면 외부 단편화는 발생하지 않는다.
• 이것이 페이징이다.
• 페이징은 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.
• 페이징에서도 스와핑을 사용하는데 프로세스 전체가 아닌 페이지 단위로 스왑 아웃/인이 된다.
• 페이징 시스템에서 스왑 아웃은 페이지 아웃, 스왑 인은 페이지 인이라고 부른다.
• 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다.
• 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만 메모리에 적재하고 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둬 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

페이지 테이블

• 여기서 문제! 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 ‘다음에 실행할 명령어 위치’를 찾기가 어려워진다.
• 이를 해결하기 위해 페이징 시스템은 비록 물리 주소(실제 메모리 내의 주소)가 불연속적으로 배치되더라도 논리 주소(CPU가 바라보는 주소) 는 연속적으로 배치되도록 페이징 테이블을 이용한다.
  • 페이지 테이블은 현재 어떤 페이지가 어떤 프레임에 할당되었는지 알려준다.
• 프로세스마다 각자의 프로세스 테이블이 있다.
• 프로세스들이 메모리에 분산되어 저장되어 있더라도 CPU는 논리 주소를 순차적으로 실행하면 된다.
• 프로세스마다 페이지 테이블들은 메모리에 적재되어 있습니다.
• CPU 내의 페이지 테이블 베이스 레지스터는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.
  • 프로세스 A가 실행될 때 PTBR은 프로세스 A의 페이지 테이블을 가리키고, CPU는 프로세스 A의 페이지 테이블을 통해 프로세스 A의 페이지가 적재된 프레임을 알 수 있다.
• 하지만 페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어난다는 문제가 있다.
• 메모리에 있는 페이지 테이블을 보기 위해 한 번, 그렇게 알게 된 프레임에 접근하기 위해 한 번 총 두 번의 메모리 접근이 필요하다.
• 이와 같은 문제를 해결하기 위해 CPU 곁에 TLB라는 페이지 테이블의 캐시 메모리를 둔다.
• TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장한다.
  • 참조 지역상에 근거해 주로 최근에 사용된 페이지 위주
• CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB 히트라고한다.
• 이 경우에는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없어 메모리 접근을 한 번만 하면된다.
  • 페이지 번호가 TBL에 없을 경우 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근할 수 밖에 없는데 이를 TLB 미스라고 한다.

페이징에서 주소 변환

• 하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있다. 그래서 특정 주소를 접근하기 위해는 두가지 정보가 필요하다.
  • 어떤 페이지 혹은 프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져있는지
• 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어져있다.
  • 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지 알기 위한 정보
• 논리 주소 <페이지 번호, 변위>는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>로 변환된다.

페이지 테이블 엔트리

• 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리라고 한다.
• 페이지 테이블 엔트리에는 페이지 번호, 프레임 번호 외에도 유효비트, 보호 비트, 참조 비트, 수정 비트가 있다.
• 유효비트는 현재 해당 페이지에 접근 가능한지 여부를 알려준다.
• 페이지 테이블에서 프레임 번호 다음으로 중요한 정보이다.
• 유효비트는 현재 페이지가 메모리에 적재되어 있는지 아니면 보조 기억 장치에 있는지를 알려준다.
• 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 페이지가 메모리에 적재되어 있지 않다면 유효 비트가 0이 된다.
• 만일 CPU가 유효비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 페이지 폴트 라는 예외가 발생한다.
• CPU가 페이지 폴트를 처리하는 과정은 하드웨어 인터럽트를 처리하는 과정과 유사하다.
  1. CPU는 기존의 작업 내용을 백업한다.
  2. 페이지 폴트 처리 루틴을 실행한다.
  3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해준다.
  4. 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근할 수 있게 된다.
• 보호비트는 페이지 보호 기능을 위해 존재하는 기능이다.
• 가령 비트가 0일 경우 이 페이지는 읽기만 가능한 페이지, 1일 경우 읽고 쓰기가 모두 가능한 페이지다.
• 읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 막아준다.
• 보호 비트는 세 개의 비트로 좀 더 복잡하게 구현할 수도있다.
  • 읽기r , 쓰기w, 실행 x의 조합으로 가령 보호 비트가 100 설정된 페이지는 r은 1, w와 x는 0이므로 이페이지는 읽기만 가능하다.
  • 보호 비트가 110으로 설정된 페이지의 경우 이 페이지는 읽고 쓰기만 가능하고 실행은 불가능하다.
  • 111로 설정된 페이지는 읽기,쓰기,실행이 모두 가능하다.
• 참조 비트는 CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다.
• 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지된다.
• 수정 비트 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줍니다.
• 더티 비트라고도 부른다.
• 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지(접근X읽기만 했던 페이지)임을 나타낸다.
• 수정 비트는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지 판단하기 위해 존재한다.
• CPU는 메모리를 읽기도 하지만 메모리에 값을 쓰기도 한다
  • 한 번도 수정된 적이 없는 페이지가 스왑 아웃될 경우 아무런 추가 작업 없이 새로 적재된 페이지로 덮어쓰기만 하면 된다. 어차피 똑같은 페이지가 보조 기억장치에 저장되어있기 때문이다.
  • CPU가 쓰기 작업을 수행한 페이지(수정 비트가 1인 페이지)의 경우 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용은 서로 다른 값을 갖게 된다.
  • 수정된 페이지가 스왑 아웃 될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야한다.
  • 이 작업이 필요한 페이지인지 아닌지를 판단하기 위해 페이지 테이블 엔트리에 수정 비트를 둔다.

14-3 페이지 교체와 프레임 할당

요구 페이징

요구 페이징이란?

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
• 즉, 실행에 요구되는 페이지만 적재하는 기법

요구 페이징의 기본적인 양상

1. CPU가 특정 페이지에 접근하는 명령어를 실행
2. 해당 페이지가 현재 메모리에 있을 경우 CPU는 페이지가 적재된 프레임에 접근
3. 해당 페이지가 현재 메모리에 없을 경우 페이지 폴트가 발생
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정
5. 다시 1번 수행

아무런 페이지도 메모리에 적재하지 않은 채 실행하면 어떻게 될까?

• 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하게 된다.
• 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어진다.
• 이를 순수 요구 페이징 기법이라고 한다.

요구 페이징 시스템이 안정적으로 작동하려면?

• 페이지 교체
  • 페이지를 적재하다보면 언젠가 메모리가 가득 차게 되는데, 이때는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야한다.
  • 어떤 페이지를 내보내는 것이 최선일지 결정하는 방법이 페이지 교체 알고리즘이다.

---

페이지 교체 알고리즘

좋은 페이지 교체 알고리즘은 무엇일까?

• 일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 알고리즘으로 평가한다.
• 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 속도가 느려지기 때문이다.
• 한 페이지 교체 알고리즘을 선택했을 때 페이지 폴트가 자주 발생하는 것은 보조기억장치로 보낼 페이지를 잘못 골랐다는 뜻이기 때문에 좋은 알고리즘이 아니다.
• 어떤 알고리즘을 통해 고른 페이지를 스왑 아웃시켜도 페이지 폴트가 자주 발생하지 않는다면 이는 컴퓨터의 성능 저하를 방지하는 좋은 알고리즘이다.
• 따라서 페이지 교체 알고리즘을 제대로 이해하기 위해서는 페이지 폴트 횟수를 알아야한다.
• 이는 페이지 참조열을 통해 알 수 있다.

페이지 참조열

• CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미
• ex) 아래와 같은 순서로 페이지에 접근했다고 가정
  • 2 2 2 3 5 5 5 3 3 7
  • 여기서 연속된 페이지를 생략한 페이지 열은
  • 2 3 5 3 7 이다.
• 연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다.

대표적인 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘

• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
• 아이디어와 구현이 간단하지만 단점도 있다.
• 실행 초기에 적재된 페이지 속에 프로그램 내내 사용될 내용을 포함하고 있다면 이는 먼저 적재되었다고 내쫓아서는 안되기 때문이다.

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
• 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지이므로, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘을 페이지 교체 알고리즘으로 삼는 것
• 앞으로 오랫동안 사용되지 않을 페이지를 예측하는 것이 어렵기 때문에 실제 구현이 어렵다.
• 따라서 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다.

LRU 페이지 교체 알고리즘

• 최적 페이지 교체 알고리즘과 비슷한 알고리즘
• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
• 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체

---

스레싱과 프레임 할당

• 페이지 폴트가 자주 발생하는 이유에는 나쁜 페이지 교체 알고리즘만 있는 것이 아니다.
• 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트는 자주 발생한다.(더 근본적인 이유)
• 극단적으로 프레임이 무한히 많은 컴퓨터 vs 프레임이 한 개 있는 컴퓨터
  • 전자는 페이지를 수용할 공간이 넉넉하여 모든 프르세스의 페이지가 메모리에 적재될 수 있어 페이지 폴트 발생 빈도가 적다.
  • 후자는 새로운 페이지를 참조할 때마다 페이지 폴트가 발생한다.
• 이처럼 페이지 폴트가 자주 발생하면 실행의 맥이 끊기고, 결과적으로 CPU의 이용률도 떨어진다.
• 이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스레싱이라고 한다.

스레싱이 발생하는 원인

• 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않기 때문
• 따라서 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하는 것이 중요하다.

프레임 할당 방식

• 균등 할당
  • 실행되는 프로세스들의 크기는 각각 다른데, 무작정 동일한 프레임 개수를 할당하는 것은 비합리적이기 때문에 권장하는 방법은 아니다.
• 세 개의 프로세스에 총 300개의 프레임을 할당할 수 있다면 각 프로세스에 100개의 프레임을 할당하는 방식
• 비례 할당
  • 프로세스의 크기가 크더라도 실행 시 많은 프레임이 필요하지 않은 경우와 프로세스의 크기가 작아도 실행해보니 많은 프레임을 필요로 하는 경우도 있기 때문에 완벽한 방식은 아니다.
• 크기가 상대적으로 큰 워드 프로세서와 상대적으로 작은 메모장이 동시에 실행된다면 워드 프로세서에 프레임을 더 많이 할당해주고, 메모장에는 상대적으로 적은 프레임을 할당하는 것

프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 뭐가 있을까?

• 작업 집합 모델
  • 작업 집합 모델 기반 프레임 할당 방식은 ‘프로세스가 일정 기간 동안 참조한 페이지 집합’을 기억하여 빈번한 페이지 교체를 방지하는 방법이다.
• 페이지 폴트 빈도
  • 페이지 폴트 빈도는 다음과 같은 가정에서 생겨난 아이디어이다.
    1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
    2. 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
  • 페이지 폴트 빈도 기반 프레임 할당 방식은 페이지 폴트율에 상한선과 하한선을 정하고, 이 범위 안에서만 프레임을 할당하는 방식이다.