[운영체제 기초] 가상 메모리

본 포스팅은 인프런의 개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제를 참조하여 작성한 글입니다.

연속 메모리 할당

우리는 지금까지 메모리 내에 프로세스들이 연속적으로 배치되는 상황을 가졍했다. 이렇게 프로세스에 연속적인 메모리 공간을 할당하는 방식을 연속 메모리 할당 이라고 한다. 그러면 프로세스들이 메모리에 연속적으로 할당할 때 무엇을 고려해야 하고 어떤 문제가 있는지 알아보자.

스와핑

메모리에 적재된 프로세스들 중에는 현재 실행되지 않는 프로세스가 있을 수 있다. 이렇게 현재 사용되지 않는 프로세스들을 보조 기억 장치 일부 영역(스왑 영역)으로 쫓아내고 그렇게 생긴 빈 공간에 새 프로세스를 적재하는 방식을 스와핑 이라고 한다. 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃 , 반대로 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인 이라고 한다.

스와핑의 장점으로는 실제 메모리 크기보다 더 필요한 프로세스들의 메모리 공간을 확보할 수 있다라는 것이다.

스왑 영역의 크기를 보고 싶다면 리눅스에서 free 혹은 top 명령어를 사용하면 된다.

메모리 할당

프로세스는 메모리 내의 빈 공간에 적재되어야 한다. 그러면 만약 빈 공간이 여러개라면 어떻게 할까? 이것을 어떻게 채우느냐에 따른 방식이 여러가지 존재한다.

• 최초 적합(first-fit)은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식을 말한다. 해당 방식은 검색을 최소화할 수 있으며 빠른 할당이 가능하다라는 장점을 가지고 있다.
• 최적 적합(best-fit)은 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 할당하는 방식이다.
• 최악 적합(worst-fit)은 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당하는 방식이다.

하지만 이렇게 연속 메모리 할당 방식에는 큰 문제가 존재한다. 바로 외부 단편화 이다. 사실 프로세스를 연속적으로 메모리에 할당하는 방식은 메모리를 효율적으로 사용하는 방법이 아니다. 예를 들어 사용자 영역이 200MB이고 크기가 50MB인 프로세스 A가 존재하고 30MB인 프로세스 B가 존재하고 100MB인 프로세스 C가 존재한다. 또한 20MB인 프로세스 D가 있다고 하자. 이렇게 프로세스 순서대로 메모리에 적재하면 딱 들어 맞는다. 하지만 중간에 프로세스 B와 프로세스 D가 종료되었다고 하자. 그러면 남은 공간은 50MB가 존재한다. 하지만 50MB가 필요한 프로세스를 배치시킬 수 없다. 빈 공간의 총합은 50MB이지만 어느 빈 공간에도 50MB 크기의 프로세스를 적재할 수 없는 것이다. 이렇게 연속 메모리 할당은 프로세스들이 실행되고 종료되길 반복하며 메모리 사이에 빈 공간이 발생한다. 이런 빈 공간이 프로세스를 할당하기 어려울 만큼 작아서 메모리가 낭비되는 것을 외부 단편화라고 한다.

외부 단편화의 해결 방법으로는 메모리 압축 방식이 존재한다. 여기저기 흩어진 빈 공간들은 하나로 모으는 방식을 말한다. 프로세스를 적당히 재배치시켜 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법이다. 하지만 이런 메모리 압축 방식에도 단점이 존재한다. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵기 때문이다.

이러한 이유로 메모리 압축 방식은 사용하지 않고 또 다른 해결 방식인 가상 메모리 기법, 페이징 방식을 사용한다.

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

연속 메모리 할당에는 2가지 문제점이 존재했다. 하나는 외부 단편화이고 하나는 물리 메모리 할당의 2가지 문제점이 존재했다. 이것을 우리는 가상 메모리 기법 중에 페이징 기법으로 해결을 할 수 있다. 가상 메모리 기법이란 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리보다 더 큰 프로세스를 실행할 수 있게 하는 기법이다. 해당 가상 메모리 기법에는 페이징 기법과 세그멘테이션 기법이 존재하는데 실제 많이 사용되는 페이징 기법에 대해 알아보자.

페이징이란

외부 단편화가 발생했던 근본적인 문제는 무엇이었을까? 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다. 만약 프로세스를 일정 크기로 자르고 이를 메모리에 불연속적으로 할당할 수 있었다면 어땠을까? 아마 외부 단편화가 적게 발생했을 것이다. 이렇게 프로세스의 논리 주소 공간을 페이지라는 일정 단위로 자르고 메모리의 물리 주소 공간을 프레임이라는 페이지와 동일한 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 기법을 페이징이라고 한다.

페이징에서도 스와핑처럼 개념이 적용된다. 프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 페이지 인, 페이지 아웃이 발생한다. 메모리에 적재될 필요가 없는 페이지들은 보조 기억장치로 페이지 아웃을 시키고 실행에 필요한 페이지들은 메모리에 페이지 인을 하는 식으로 이루어진다. 이렇게 하면 프로세스를 실행하기 위해 모든 페이지가 적재될 필요가 없다. 달리 말해 물리 메모리보다 더 큰 프로세스도 실행이 가능하게 되는 것이다.

페이지 테이블

하지만 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU는 알 길이 없다. 또한, 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 임장에서는 이를 순차 실행을 할 수 없다. 즉, CPU 입장에서 다음에 실행 할 명령어 위치를 찾기 어려워지는 것이다. 이것을 해소하기 위해 나온 것이 페이지 테이블이다. 페이지 테이블은 실제 메모리 내의 주소인 물리 주소에 불연속적으로 배치되더라도 CPU가 바라보는 주소인 논리 주소에는 연속적으로 배치되도록 하는 방법이다. 즉, 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표 역할을 한다. 예를들어, 페이지 0번, 1번, 2번이 각각 프레임 번호 3, 5, 2에 배치될 수 있다. 그러면 CPU가 바라보는 페이지 번호는 연속적이지만 불연속적인 프레임에 매핑이 되는 것이다.

물리적으로 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리주소는 연속적으로 보인다. CPU는 그저 논리 주소를 순차적으로 실행하면 될 뿐이다.

내부 단편화

하지만 이런 페이징 기법에는 또 다른 문제가 발생할 수도 있는데 그것이 바로 내부 단편화 문제이다. 내부 단편화란 하나의 페이지 크기보다 작은 크기로 발생하는 현상이다. 즉, 페이지 크기가 10KB, 프로세스 크기가 108KB라면 마지막에 2KB라는 내부 단편화가 발생한다.

대형 페이지: 일반적인 운영체제에는 기본적으로 설정된 페이지 크기로 아루어져 있다. 하지만 페이지 크기보다 더 큰 크기의 페이지도 일부 허용하며 메모리에 유지하는 경우도 존재하는데 기본적으로 설정된 페이지보다 큰 페이지를 대형 페이지라고 한다.

프로세스마다 각자의 페이지 테이블을 가지고 있고 각 프로세스의 페이지 테이블은 메모리에 적재되어 있다. 그리고 CPU 내의 페이지 테이블 베이스 레지스터 는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다. 즉, PTBR은 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.

그런데 이렇게 페이지 테이블을 메모리에 두면 문제가 발생한다. 메모리 접근 시간이 2배로 늘어난다는 점이다. 메모리에 있는 페이지 테이블을 보기 위해 한 번, 그렇게 알게 된 프레임에 접근하기 위해 한 번, 이렇게 총 2번의 메모리 접근이 필요하다. 그래서 이런 문제를 해결하기 위해 CPU 곁에 TLB라는 페이지 테이블의 캐시 메모리를 둔다. 실제 페이지 테이블의 자주 사용되는 일부를 가져와 저장을 해둔다. 그리고 CPU가 접근하려는 논리주소가 TLB에 있다면 TLB 히트라고 표현하고 CPU가 접근하려는 논리주소가 TLB에 없다면 TLB 미스가 발생한다.

페이징에서의 주소 변환

하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있다. 그렇기에 특정 주소에 접근하려면 아래의 정보들이 필요하다.

• 어떤 페이지 혹은 프레임에 접근하고 싶은지?
• 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지?

그렇게이 페이징 시스템에는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어져 있다. 이런 페이지 번호, 변위로 이루어진 논리 주소는 페이지 테이블을 통해 프레임 번호, 변위로 변환된다.

논리 주소의 변위와 물리 주소의 변위 값은 같다.

페이지 테이블 엔트리

페이지 테이블의 각각의 행을 페이지 테이블 엔트리(PTE)라고 한다. 우리가 배운 현재까지 PTE는 페이지 번호, 프레임 번호이다. 이 외에도 다른 것들이 있는데 이를 자세히 알아보자.

유효 비트 는 현재 해당 페이지에 접근 가능한지 여부를 뜻한다. 즉, 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 페이지가 메모리에 적재되어 있지 않다면 유효 비트가 0이 된다. 만일 CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 어떻게 될까? 이 경우 페이지 폴트 라는 예외가 발생한다. 페이지 폴트의 처리 과정은 아래와 같다.

• CPU는 기존의 작업을 백업한다.
• 페이지 폴트 처리 루틴을 실행한다.
• 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해준다.
• 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근할 수 있게 된다.

보호 비트 는 페이지 보호 기능을 위해 존재하는 비트이다. 해당 비트가 0이면 이 페이지는 읽기만 가능한 페이지임을 나타내고, 1일 경우 읽고 쓰기가 모두 가능한 페이지임을 나타내는 것이다. 보호 비트는 조금 더 세분화하게 R/W/X 총 3개의 비트로 세분화도 가능하다. R이 1일 경우는 읽기 전용, W는 쓰기 전용, X는 실행 전용이다.

참조 비트 는 CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다. 메모리에 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 적재 이후 한번도 읽거나 쓴 적이 없는 페이지는 0으로 유지된다.

수정 비트 는 CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부를 나타낸다. 흔히 더티 비트라고도 부른다. 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지를 나타낸다. 그러면 수정 비트는 왜 존재할까? 수정 비트는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재한다. 페이지 아웃이 발생할 때 보조기억장치에서도 쓰기 작업을 해야하는지 유무때문에 존재하는 것이라고 봐도 좋다. 만약 0이라면 보조기억장치 데이터를 변경할 필요가 없지만 1이라면 변경해야 하기 때문이다.

[추가] 쓰기 시 복사와 계층적 페이징

외부 단편화 문제를 해결한다는 점 이외에도 페이징이 제공하는 이점은 다양하다. 대표적인 것이 프로세스 간에 페이지를 공유할 수 있다는 점이다. 프로세스 간 페이지를 공유하는 사례로는 공유 라이브러리등도 있지만 대표적인 예시로 쓰기 시 복사 가 존재한다.

프로세스는 기본적으로 자원 공유를 못한다. 이론적인 fork 시스템 콜을 보면 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재한다. 이 때 프로세스 생성 시간의 지연이 발생하고 만약 부모 프로세스와 완전 동일한 놈이라면 메모리 낭비도 발생한다. 하지만 쓰기 시 복사 기법을 사용하면 부모 프로세스와 동일한 자식 프로세스가 복제되어 생성되면 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리키게 된다. 그리고 부모 프로세스든 자식 프로세스든 쓰기 작업이 없다면 이 상태를 유지하게 된다. 그런데 부모 프로세스나 자식 프로세스 둘 중 하나가 페이지에 쓰기 작업 수행 시 해당 페이지는 별도의 공간으로 복제된다. 이로써 프로세스 생성 시간도 절약을 하고 메모리 절약을 할 수 있다. 이것이 바로 쓰기 시 복사이다.

또한, 페이지 테이블의 크기는 생각보다 적지 않다. 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비이다. 그래서 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지 않을 방법이 고안되었다. 바로 계층적 페이징 혹은 다단계 페이지 테이블 이라고 한다. 해당 방식은 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식을 말한다. 이렇게 하면 페이지 테이블을 여러 페이지로 쪼개고 이 피에지를 가리키는 페이지 테이블(outer page table)을 두어서 이를 가리키게 한다.

이러면 모든 페이지 테이블을 항상 메모리에 둘 필요가 없어지며 CPU와 가장 가까이 위치한 outer page table만 항상 메모리에 유지해도 원하는 페이지만 가리키게 할 수 있다. 그래서 계층적 페이징을 사용하는 경우 CPU가 발생하는 논리 주소도 달라진다. 계층적 페이징을 사용하지 않을 경우 논리 주소는 변위와 페이지 번호로 구성되었다. 하지만 계층적 페이징을 이용하는 환경에서는 바깥 페이지 번호 + 안쪽 페이지 번호 + 변위로 구성된다. 바깥 페이지 번호에 해당하는 항목은 CPU와 근접한 곳에 위치한 outer page table 엔트리를 가리키고 안쪽 페이지 번호는 첫번째 페이지 테이블 바깥이 위치한 두번째 페이지 테이블, 즉 페이지 테이블의 페이지 번호를 가리킨다. 이러한 논리 주소를 토대로 주소 변환은 다음과 같다.

• 바깥 페이지 번호를 통해 페이지 테이블의 페이지를 찾기
• 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리주소 얻기

페이지 교체와 프레임 할당

가상 메모리 기법중에 페이징을 통해서 물리 메모리보다 더 큰 프로세스를 실행할 수 있지만 그럼에도 물리 메모리 크기는 한정되어 있다. 기존에 적재된 불필요한 페이지를 선별해 보조 기억 장치로 내보내고 프로세스들에게 적절한 수의 프레임을 할당해야 한다. (이후 작성 예정)