[혼공학습단 9기] 혼.공.컴.운. - 14. 가상 메모리(필수미션 포함)

운영체제의 가장 핵심적인 두 역할: 프로세스 관리와 메모리 관리.지금까지 프로세스 관리 기법에 대해 알아봤으니 이제 메모리 관리 기법에 대해 알아보자. 

기본 미션

문제

 

1. 메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아써 보세요.

보기:최초 적합, 최적 적합, 최악 적합

• (1): 최초로 발견한 적재 가능한 빈 공간에 츠로세스를 배치하는 방식
• (2):프로세스가 적재되룻 있는 가장 큰 공간에프로세스를 배치하는 방식
• (3): 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

 

정답

 

1. 최초 적합
2. 최악 적합
3. 최적 적합

 

14-1 연속 메모리 할당

연속 메모리 할당: 프로세스에 연속적인 메모리 주소를 할당하는 것

스와핑

 

스와핑(swapping): 메모리에 적재된 프로세스들 중 현재 실행되지 않는 프로세스들을 임시로 보조기억장치 일부영역으로 쫓아내고, 그렇게 해서생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식. 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리보다 큰 경우에도 프로세스를 동시 실행할 수 있도록 해준다.

스왑 영역(swap space): 프로세스들이 쫓겨나는 보조기억장치의 일부 영역

스왑 아웃(swap-out): 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것

스왑 인(swap-in): 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것(스왑 아웃 되기 전의 물리주소와는 다른 주소에 적재될 수 있다.)

 

메모리 할당

 

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

 

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

 

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

 

외부 단편화

 

연속 메모리 할당은 메모리를 효율적으로 사용하는 방법이 아니다. 왜냐하면 외부 단편화(external fragmentation)라는 문제를 가지고 있기 때문이다.

 

프로세스들이 메모리에 연속적으로 할당되는 환경에서는 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생긴다. 이는 그 공간보다 큰 프로세스를 적재하기 어렵기 때문에 메모리 낭비로 이어진다. 이런 현상이 외부 단편화이다.

 

압축(compaction): 메모리 조각 모음이라고도 부른다. 메모리 내에 저장된 프로세스를 적당히 재배치해 여기저기 흩어진 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법이다. 외부 단편화를 해결할 수 있는 대표적인 방안이다. 그러나 압축 방식에는 여러 단점이 있다. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다. 이를 해결하는 방안이 다음 장에서 살펴볼 '페이징'이다.

 

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

 

프로세스를 메모리에 연속적으로 할당하는 방식은 두 가지 문제를 내포하고 있다. 한 가지는 앞선 절에서 다루었던 외부 단편화이고, 또 하나는 물리 메모리보다 큰 프로세스를 실행할 수 없다는 것이다.

가상 메모리(virtual memory): 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다.

페이징: 현대 대부분의 운영체제가 사용하는 가상 메모리 관리 기법. 물리 메모리보다 큰 프로세스를 실행할 수 있을 뿐만 아니라 외부 단편화 문제도 해결할 수 있다.

 

페이징이란

 

프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.

 

페이징을 사용하는 시스템에서는 스와핑을 할 때 페이지 단위로 스왑 아웃/스왑 인 된다. 메모리에 적재될 필요 없는 페이지들은 보조기억장치로 스왑 아웃되고, 실행에 필요한 페이지들은 메모리로 스왑 인 된다. 페이징 시스템에서는 페이지 아웃, 페이지 인 이라고 부르기도 한다.

 

프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재해 물리 메모리보다 더 큰 프로세스를 실행할 수 있도록 한다.

 

페이지 테이블

 

프로세스가 비록 물리 주소에 불연속적으로 배치되더라도 CPU가 바라보는 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 이용한다. 이를 통해 CPU가 순차적으로 명령어를 실행할 수 있도록 한다. 현제 어떤 페이지가 어떤 프레임에 할당되었는지를 알려준다.

 

프로세스마다 각각의 프로세스 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있다.

 

내부 단편화

 

모든 프로세스 크기가 페이지 크기의 배수는 아니기 때문에 메모리 낭비가 발생할 수 있는데, 이를 페이징 시스템에 발생하는 내부 단편화라고 한다. 가령 페이지 크기가 10KB인데, 프로세스의 크기가 108KB라고 하면 마지막 페이지에는 2KB만큼의 크기가 남는다. 내부 단편화를 적당히 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요하다.

 

페이지 테이블 베이스 레지스터(PTBR: Page Table Base Register): CPU 내에서 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다. 

 

TLB(Translation Lookaside Buffer): 페이지 테이블을 메모리에 두었을 때 메모리 접근 시간이 두 배로 늘어난다는 문제를 해결하기 위해 CPU 곁, 일반적으로 MMU 내에 두는 캐시 메모리. 참조 지역성(컴퓨터 프로그램이 일정 기간 동안 특정한 메모리 위치 집합에 접근하는 경향이 있는 현상)에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장한다.

 

TLB 히트: CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있는 경우. 이 경우에는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없다.

 

TLB 미스: 페이지 번호가 TLB에 없는 경우

 

페이징에서의 주소 변환

 

특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요하다.

 

페이지 번호: 접근하고자 하는 페이지 번호. 페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되어 있는지를 알 수 있다.

 

변위: 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보

 

논리 주소 <페이지 번호, 변위> 가 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위(같은 값)>로 변환된다.

 

페이지 테이블 엔트리

 

페이지 테이블 엔트리: 페이지 테이블의 각각의 행

 

유효 비트

 

현재 해당 페이지에 접근 가능한지 여부를 알려준다. 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 보조기억장치에 있다면 유효비트가 0이 된다.

 

페이지 폴트: CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 할 때 발생하는 예외(Exception)

 

보호 비트: 페이지 보호 기능을 위해 존재하는 비트. 이 비트가 0일 경우 이 페이지는 읽기만 가능한 페이지임을 나타내고, 1일 경우 읽고 쓰기가 모두 가능한 페이지임을 나타낸다. 세 개의 비트로 더 복잡하게 구현할 수도 있다.

 

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

 

수정 비트 = 더티 비트: 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려 준다. 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지임을 나타낸다. 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재한다.

 

페이징의 이점 - 쓰기 시 복사

 

부모 프로세스와 동일한 자식 프로세스가 생성되면 자식 프로세스로 하여금 부모 프로세스와 동일한 프레임을 가리킨다. 이로써 굳이 부모 프로세스의 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있다. 둘 중 하나가 페이지에 쓰기 작업을 하면 그 때 비로소 해당 페이지가 별도의 공간으로 복제되고, 각 프로세스는 자신의 고유한 페이지가 할당 된 프레임을 가리킨다. 이것이 쓰기 시 복사이다.

 

계층적 페이징

 

페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식. 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않도록 해 메모리 낭비를 막는 방식이다. 페이지 테이블을 여러 개의 페이지로 쪼개고, 이 페이지들을 가리키는 페이지 테이블을 둔다. 이렇게 하면 페이지 테이블들 중 몇 개는 보조기억장치에 있다가 참조해야 할 때가 있으면 그때 메모리에 적재하면 그만이다.

 

 

페이지 테이블의 계층이 늘어날수록 페이지 폴트가 발생했을 경우 메모리 참조 횟수가 많아지므로 계층이 많다고 해서 반드시 좋다고 볼 수는 없다.

 

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

요구 페이징, 페이지 교체 알고리즘, 프레임 할당 등 운영체제가 수많은 페이지를 어떻게 관리하는지 학습한다.

 

요구 페이징

 

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

 

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

 

순수 요구 페이징: 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행하는 방법. 첫 명령어부터 페이지 폴트가 계속 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어진다.

 

요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당을 해결해야 한다.

 

페이지 교체 알고리즘: 메모리가 가득 찼을 때 어떤 페이지를 내보낼 지 결정하는 알고리즘

 

페이지 교체 알고리즘

 

페이지 폴트 횟수가 적은 알고리즘이 좋은 알고리즘이며, 이는 페이지 참조열을 통해 알 수 있다. 페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미한다. (중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않는다.)

 

FIFO 페이지 교체 알고리즘

메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식이다.

아이디어와 구현이 간단하지만, 먼저 올라온 페이지라고 해서 항상 먼저 제거해서는 안 된다는 문제점이 있다.

 

2차 기회 페이지 교체 알고리즘

 

FIFO 페이지 교체 알고리즘을 개선한 것으로 기본적으로 원리는 같지만, 만일 페이지의 참조 비트가 1일 경우, 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정한다. 메모리에 가장 오래 머물렀어도 CPU가 한 번 접근한 적이 있기 때문에 한 번 더 기회를 주는 것이다.

 

최적 페이지 교체 알고리즘

 

CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘. 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하기 때문에, 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다. 

 

다만 실제 구현이 어렵다. 프로세스가 앞으로 메모리 어느 부분을 어떻게 참조할 지 미리 아는 것은 현실적으로 불가능에 가깝기 때문이다. 따라서 운영체제에 사용하기보다는, 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다.

 

LRU 페이지 교체 알고리즘

가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘.