1 서론

OS 에서 메모리 계층 구조 관리를 담당하는 부분을 메모리 관리자(Memory Manager) 이라고 한다.

메모리 관리자의 역할:

1. 현재 사용중인 메모리 부분을 파악

2. 프로세스들이 메모리를 필요로 하면 할당

3. 프로세스들이 더이상 메모리를 사용하지 않으면 할당 해제

메모리 관리의 목적:

1. 프로그래밍에서 편리한 추상화를 제공해주고 (가상메모리 제공)

2. 경쟁 프로세스 간에 부족한 메모리 리소스를 할당하고 성능을 최대화(오버헤드 최소화)

이제 다양한 메모리 관리 기법에 대해 알아보겠다.

2 메모리 추상화가 없는 컴퓨터

프로그래머에게 제공되는 메모리 모델은 물리 메모리 그 자체이며 이 모델은 0 부터 물리 메모리 크기만큼 까지 주소를 갖는다.

메모리 추상화가 없는 환경에서는 두 개의 프로그램이 동시에 메모리에서 실행한다는 것은 불가능하다.

왜냐하면 한 프로그램이 어떤 주소에 새로운 값을 기록했을 때 동시에 다른 프로그램이 그 주소에 기록해둿던 데이터를 변경할 수도 있기 때문이다.

• 물리 메모리 설계 모델 3가지

컴퓨터 시스템이 이와 같은 방법으로 구성되어 있으면 대부분 한 순간에 하나의 프로세스만 동작하게 된다.

• 메모리 추상화가 없는 환경에서 여러 프로그램 실행

OS 가 해야할 일은:

1. 메모리에 존재하던 프로그램 이미지를 디스크 에 저장

2. 다음에 실행할 프로그램을 메모리 로 올리는 것

사실상 메모리에 한 순간에 하나의 프로그램이 존재하기만 하면 충돌을 방지할 수 있다.

특별한 하드웨어의 도움으로 프로그램 동시 실행을 가능하게 할 수 있다.

1. 메모리를 2KB 크기 블록들로 구분하고 각 블록은 4비트의 보호 키 를 갖는다.

• CPU 내부에는 특별한 레지스터가 있어 이 보호키 들을 저장한다.
• 또한 CPU의 PSW(Program Status Word) 에는 4비트 키가 유지된다.

2. 프로세스가 현재 PSW 의 키와 다른 보호 키 를 갖는 메모리 블록을 접근하려고 하면 시스템은 트랩을 발생시킨다.

• 키의 변경은 OS 에서만 가능하다

문제점

프로그램이 따로 따로 메모리에 적재되서 돌아갈 때는 문제가 없지만

동시에 메모리에 적재되어서 돌아가면 문제가 생긴다.

물리 메모리 그 자체로 프로그래밍 되어 있으므로 B 프로그램의 JMP 28 을 실행하면 A 프로그램의 ADD 명령으로 점프하는 엉뚱한 일이 발생한다.

해결방법

우리가 원하는 건 각 프로그램이 자신에게 속한 주소들만 적절하게 참조하는 것이다.

정적 재배치(Static Relocation) 기법을 사용해서 해결할 수 있다.

정적 재배치 란 프로그램이 메모리에 적재될 때 프로그램의 내용을 수정하는 것이다.

두번째 그림에서 B가 메모리 주소 16384 에 적재될 때 B가 참조하는 모든 주소에 16384를 더하면 해결할 수 있다.

따라서 JMP 28 을 - > JMP 28 + 16384로 주소를 바꾸면 잘 동작할 것이다.

그렇지만 복잡한 프로그램을 다룰 때는 이런 방법을 쓸 수가 없다.
(매번 주소를 더할 수 없기 때문)
보통 임베디드 시스템 에서 사용한다

3 메모리 추상화

앞서 알아봤듯이 물리 메모리를 직접 사용하는 것은 단점이 있다

1. 프로그램이 물리 메모리의 모든 주소를 접근할 수 있다면 사용자는 실수 또는 의도적으로 OS를 파괴할 수 있다.

2. 여러 프로그램들을 동시에 키는 것이 어려워진다.
   (서로의 메모리 영역을 침범할 수 있고, 이걸 해결하려면 프로그램이 참조하는 주소를 일일이 바꿔줘야 함)

메모리 추상화 를 사용해서 이런 문제를 해결하는 방법을 알아보자

• 주소 공간 개념

여러 프로그램들을 동시에 메모리에 적재하고 서로 간섭없이 실행하기 위해서는 보호 와 재배치 방법이 제공되어야 한다.

위에서는 보호 키 를 이용하여 보호를, 정적 재배치 를 이용하여 재배치를 제공하는걸 알아봤는데 이건 별로 효율적이지 못하다.

보호와 재배치를 제공하는 더 효과적인 방법은 주소 공간 이라는 메모리 추상화 를 사용하는 것이다.

주소 공간이란?

프로세스가 메모리를 접근할 때 사용하는 주소들의 집합으로 각 프로세스는 자신만의 주소 공간을 갖는다.
한 프로세스가 갖는 주소 공간은 다른 프로세스가 갖는 주소 공간과 독립 되어 있다.
(물론 원한다면 공유는 가능)

이제 각 프로세스들에게 서로 다른 주소 공간을 제공하는 방법들을 알아보자

• Base & Limit 레지스터

동적 재배치 방법 중의 한가지로 각 프로세스의 주소 공간을 물리 메모리의 서로 다른 공간으로 연속적으로 매핑하는 것이다.

이 방법을 위해 CPU 에서는 base 와 limit 이라는 이름의 특별한 하드웨어 레지스터를 사용한다.

프로그램은 비어있는 메모리 공간에 연속적으로 적재된다. 대신에 정적 재배치는 필요 없다.

• base 레지스터 에는 프로그램이 적재된 메모리 시작 위치를

• limit 레지스터 에는 프로그램의 크기가 저장된다.

프로세스가 메모리를 참조하면 CPU 하드웨어(MMU) 는 자동적으로 프로세스가 참조하려는 메모리 주소가 limit 레지스터의 값과 크거나 같은지 조사하고, 그렇다면 fault를, 아니라면 base 레지스터의 값에 그 주소를 더해서 실제 물리 메모리로 가서 해당하는 주소를 참조한다.

많은 구현에서 base와 limit 레지스터는 오직 OS 에서만 변경될 수 있도록 보호된다.

단점

모든 메모리 참조마다 덧셈과 비교 연산이 요구되어 시간이 걸릴 수 있다.

• 스와핑과 가상 메모리

실제 시스템에서 모든 프로세스들이 필요로 하는 메모리의 전체 크기는 시스템에 존재하는 실제 RAM 의 용량보다 크다.

즉, 모든 프로세스들을 메모리에 계속 적재하는 것은 사실상 불가능하다.

이를 해결하기 위해서 스와핑 과 가상 메모리 가 등장하였다.

• 스와핑

한 프로세스의 모든 이미지가 메모리로 적재되어 실행되다가 더 이상 실행하지 않을 경우 다시 디스크로 내려 보내는 방법이다.
따라서 현재 실행되고 있지 않은 프로세스는 메모리를 차지하지 않고 디스크에 존재하게 된다.

빈 공간에 프로세스 데이터를 쪼개서 저장하면 안되나 생각할 수 있지만 스와핑에서는 프로세스의 모든 이미지가 메모리로 적재된다.
(또한 쪼개지면 재배치 할 때 base limit 레지스터를 사용할 수 없다.)

쪼개서 저장하는건 나중에 가상메모리에서 살펴보겠다.

메모리 조각 모음(Memory compaction)

그림에서 스와핑을 하고 나면 메모리 안에 여러개의 빈 공간이 만들어지는데 퍼즐 맞추듯이 프로세스들의 위치를 이동하여 빈 공간을 하나로 합칠 수가 있다.

이것을 메모리 조각 모음 이라고 하는데 사실 시간이 많이 걸리기 때문에 잘 쓰이지 않는다.

프로세스 메모리 공간 할당

많은 프로그래밍 언어에서는 힙 공간에서 동적 메모리 할당과 같은 기능을 제공하며 프로세스의 크기가 실행 중에 증가하게 된다.

따라서 프로세스에게 메모리 공간을 할당할 때 여유공간을 주면 좋다.

• 여유 공간이 없다면 기존의 프로세스들을 이동시켜서 메모리 공간을 만들어 주거나 안쓰는 프로세스들을 스왑 아웃(디스크에 적재) 해서 빈 공간을 생성해줘야 한다.

• 위의 방법도 되지 않는 최악의 경우(메모리에 빈 공간도 없고 디스크의 스왑 공간도 가득 차 있는 경우) 새로 생성하려는 프로세스를 잠시 중단하거나 강제종료 시켜야 한다.

• 가용 메모리 공간 관리 - 비트맵 & 링크드 리스트

메모리가 동적으로 할당된다면 OS 는 메모리 공간의 어떤 부분이 사용중인지 관리하여야 한다.

이때 사용하는 대표적인 두가지 자료구조가 비트맵 과 링크드 리스트 이다.

비트맵을 이용한 관리

메모리를 여러 개의 할당 단위 로 나누어 관리한다.

각 할당 단위 마다 비트가 하나씩 대응하는데 0이면 사용 안하는거 고 1이면 사용중 인 것이다. (물론 반대로 설정해도 된다.)

비트맵 할당 단위의 크기 설정

만약 할당 단위가 작으면?

비트맵의 크기가 커진다. (할당 단위마다 0, 1 로 표기해야 하므로)

만약 할당 단위 가 1바이트 이면 8비트 마다 1비트가 필요(0, 1 로 표기) 하므로 8n 비트에 n 크기의 비트맵이 필요하게 되며 결국 전체 메모리의 1/9 (8 + 1) 가 비트맵으로 사용된다.

비트맵은 메모리안에 있으므로 메모리 공간을 너무 차지하면 프로세스가 들어갈 공간이 줄어든다

할당 단위가 커지면 반대로 비트맵의 크기는 작아진다.

그러나 만약 할당 단위 가 4KB 인데 프로세스가 4.001KB 이면?

일단 할당 단위가 4KB 이므로 8KB를 할당해 주어야 하는데 3.999KB는 낭비가 된다...

이렇게 프로세스 크기가 할당 단위의 정수배가 아니면 마지막 할당 단위의 일부 공간이 낭비될 수 있는 문제점(내부 단편화: internal fragmentation) 이 있다.

따라서

비트맵 크기는 메모리 크기 와 할당 단위의 크기 에 의해 결정되며 고정된 크기의 공간으로 메모리의 사용량을 관리하는 간단하면서도 효과적인 방법이다.
그러나, 프로세스가 k개의 할당 단위를 요구했을 때 메모리 관리자(MMU) 가 비트맵에서 연속적인 k개의 비트를 찾아야 한다.
이러한 비트맵 검색은 시간이 많이 걸린다...

링크드 리스트를 이용한 관리

링크드 리스트 역시 메모리에 존재한다.

종료될 때 빈 공간은 서로 합쳐줘야 한다.

링크드 리스트로 구현해도 비트맵 처럼 할당 단위에 따라 공간 낭비 문제 (internal fragmentation) 가 발생할 수 있다.

리스트 메모리 할당 알고리즘

First fit

MMU가 리스트를 처음부터 순서대로 검색하며 요청한 공간을 담을 수 있는 크기의 빈 공간이 발견되면 그 공간을 할당한다.

즉, 프로세스가 메모리 공간에 들어갈 수 만 있으면 바로 할당해준다.

따라서 검색을 최소한으로 하기 때문에 빠른 할당이 가능하다.

Next fit

First fit 과 유사하지만 공간을 할당해 주었을 때 그 위치를 기억해 둔다는 차이점이 있다.

나중에 또다른 새로운 할당을 위해 Next fit 알고리즘이 호출되면 지난번에 기억해 두었던 위치부터 검색을 시작한다.

(근데 First fit 에 비해 성능이 떨어진다는 분석이 있다.)

Best fit

리스트의 처음부터 끝까지 모든 엔트리들을 검색하여 요청한 크기에 가장 근접하게 큰 빈공간을 할당한다.

리스트 전체를 검색해야 하기 때문에 First fit 에 비해 느리고 놀랍게도 메모리 낭비 도 First fit, Next fit 보다 더 많은 것으로 분석되었다.

Worst fit

리스트의 처음부터 끝까지 모든 엔트리들을 검색하여 가능한 프로세스가 요구하는 메모리 크기에 맞도록 빈 공간을 할당하고 그 결과로 작은 빈 공간들(외부 단편: External fragmentation) 을 많이 생성한다.

항상 가장 큰 빈 공간을 할당해 준다. (할당되고 남은 빈 공간도 가능한 큰 공간이 되도록, 그래야 다른 프로세스를 거기에 껴 넣을 수 있도록)

근데 그리 좋은 것은 아니라고 분석되었다.

Quick fit

자주 요청되는 공통 크기의 메모리 공간들을 서로 다른 리스트로 관리한다.

예를 들어 n개의 엔트리를 갖는 테이블을 유지하며

테이블의 첫번째 엔트리는 4KB크기의 빈 공간들을 관리하는 리스트

테이블의 두번째 엔트리는 8KB크기의 빈 공간들을 관리하는 리스트...

이렇게 크기별로 나눠 놓는다.

장점

요청한 메모리 크기를 만족하는 빈 공간을 검색하는 것은 매우 빠르다.

빈 공간 크기별로 엔트리를 분류해 놓았기 때문에 그냥 찾아가서 할당해주면 되기 때문이다.

단점

프로세스가 종료하거나 스왑 아웃(메모리에서 나와서 디스크에 저장) 될 때, 이웃 엔트리를 찾고 통합이 가능한지 확인하는 것이 복잡해진다.
(왜냐하면 엔트리가 빈 공간 크기별로 따로 분리되서 관리되므로)

• Fragmentation problems

External fragmentation

프로세스 메모리 바깥의 빈 공간

메모리 구멍이 너무 작아서 다른 프로세스가 사용할 수 없다.
(만약 크기가 매우 작은 프로세스라면 사용가능 하겠지만 그런 프로세스가 있을까?)

Internal fragmentation

프로세스 메모리 안쪽의 빈 공간

다른 프로세스가 사용할 수 없는 빈 공간들

4 가상 메모리

최근에 나오는 프로그램들은 크기가 매우 커서 메모리에 다 들어갈 수가 없다.

따라서 메모리 크기보다 더 큰 응용을 실행할 수 있는 기법이 필요하다.

오버레이와 가상 메모리 기법이 있다.

• 오버레이

프로그래머가 프로그램을 여러 오버레이들로 분할해서 각각 메모리에 올려서 실행한다.

그러나 큰 프로그램을 작은 조각들로 분할하는 작업은 시간이 많이 걸리고 에러가 발생하기 쉽다.

• 가상 메모리(페이징)

가상 메모리란 보조기억장치(하드,SSD) 의 일부를 주기억장치(메모리) 처럼 사용해서 상대적으로 용량이 작은 메모리를 마치 큰 용량을 가진 하드처럼 사용하는 기법이다.

페이징의 기본적인 아이디어는 각 프로그램이 자신의 고유한 주소공간을 가지며 주소공간은 페이지 라고 불리는 동일한 크기의 조각들로 구성된다.

• 본질적으로 base-limit 레지스터 사용을 일반화 한 것으로 볼 수 있다.

각 페이지는 연속된 주소를 가지며 프로그램이 실행되면 페이지들을 물리 메모리에 매핑된다.

이때, 프로그램 실행을 위해서 모든 페이지들이 물리 메모리에 있어야 하는 건 아니다.

프로그램이 참조하는 주소는 가상 주소 라고 불리며 가상 주소 공간을 형성한다.

• 가상메모리를 사용하지 않는 컴퓨터에서는 가상 주소가 곧 물리 주소이다.

• 가상 메모리를 사용하는 컴퓨터에서는 MMU 에 의해 물리 주소로 매핑된다.

대부분의 CPU 칩은 MMU(Memory Management Unit) 를 포함하지만 그 둘은 서로 독립적이며 서로 다른 칩으로 존재할 수도 있다.

• 페이징 자세히

프로그램의 전체 이미지는 디스크 상에 존재하며 물리 메모리에는 현재 실행에 필요한 부분만 존재하게 된다.

가상 주소 공간 은 고정된 크기의 단위들로 구분되어 있는데 이 단위를 페이지 라 한다.
물리 메모리 상에 대응되는 단위는 페이지 프레임이라 한다.

페이지와 페이지 프레임의 크기는 같다.

메모리 과 디스크 간에 데이터의 이동 역시 페이지 단위로 이루어진다.

• 페이징 매핑 과정

프로그램이 다음과 같은 명령을 실행하면

MOV REG, 0

1. 이 명령은 가상 주소 0을 접근하며 이 주소는 MMU 로 전달된다.

2. MMU 는 이 주소가 페이지 0(0 ~ 4095) 에 속한 것을 계산하고 이 페이지 에 매핑 된 페이지 프레임 이 2번(8192 ~ 12287)임을 발견한다.

3. 가상 주소 0 은 물리 주소 8192 로 변환되고 이 물리 주소 가 메모리 버스에 실리게 된다.

• 메모리는 MMU 에 대해 전혀 모르며 단지 8192 주소에 대한 읽기 또는 쓰기 요청이 발생했음만을 안다.

프로그램이 매핑되지 않은 주소를 참조한다면? -> 페이지 폴트

위 그림을 보면 가상 메모리 공간에는 16 페이지 가 있고 물리 메모리 공간에는 8 페이지 프레임 이 있다.
따라서 매핑되지 못한 페이지들이 8페이지가 있다.

이렇게 매핑되지 못한 페이지들을 구분하기 위해 하드웨어적으로 present/absent 비트가 제공되며 이를 통해 어떤 페이지가 실제 물리 메모리에 존재하는지 파악할 수 있다.

만약 다음과 같은 명령을 프로그램이 실행한다고 해보자

MOV REG, 32780

32780 주소는 페이지 8의 12번째 바이트이다.(페이지 8번 주소: 32768 ~ 36864)

1. MMU 는 present/absent 비트 를 이용해 현재 페이지 8이 매핑되어 있지 않음을 확인하고 CPU 에게 트랩 을 발생시켜 OS에게 이것을 알리도록 한다.

• 이것을 페이지 폴트 라고 한다.

2. OS 는 페이지 프레임 중에서 적게 사용되고 있는 것을 골라 선택한 페이지 프레임의 내용을 디스크 에 기록한다.(이미 기록되어 있으면 과정 생략)

• 여기서 페이지 프레임을 1번이라고 가정해보자

3. 이후 참조하려는 페이지(8번)의 내용을 선택한 페이지 프레임(1번)에 적재하고 맵을 수정한 후, 트랩을 야기한 명령(MOV REG, 32780) 을 다시 실행한다.

4. 가상 주소 32780이 물리 주소 4108(4096 + 12)로 변환되어 실제 물리 메모리를 참조하게 된다.

• 페이지 테이블

페이지 테이블 은 OS에 의해 관리된다.

페이지 테이블 에는 해당 페이지 번호 에 대응되는 페이지 프레임 번호가 기록되어 있다.

페이지 번호 는 페이지 테이블 의 인덱스 로 쓰인다.

가상 주소를 물리 주소로 매핑하는 과정을 요약하면 다음과 같다.

1. 가상 주소를 페이지 번호(상위 비트)와 오프셋(하위 비트) 로 구분한다.

• 16비트 주소를 갖는 시스템에서 페이지 크기가 4KB(4*1024 = 2^12) 라면 상위 4비트는 페이지 번호로 사용되고 하위 12비트는 바이트 오프셋으로 사용된다.

2. 페이지 번호 를 인덱스로 이용해 페이지 테이블 에서 가상 주소에 대응되는 엔트리(페이지 프레임)를 찾는다.

페이지 테이블 엔트리 구조

페이지 프레임 번호

• 가상 주소를 물리 주소로 매핑하는 기능 담당

present/absent 비트

• 1이면 해당 페이지 테이블 엔트리가 유효, 페이지 프레임 번호 를 사용할 수 있음

• 0 이면 해당 엔트리에 대응되는 페이지가 물리 메모리에 존재하지 않은 상태, 페이지 폴트 발생

보호 비트

• 어떤 접근이 허용되어 있는지를 표시 (읽기, 쓰기, 실행)
• 가장 간단한 1비트 보호 비트의 경우 1일때 읽기만, 0일때 읽기/쓰기 모두 가능

더티 비트(수정 비트) & 참조 비트 : 페이지의 사용을 표현

더티 비트(수정 비트)

• 페이지의 내용이 변경되면 하드웨어는 자동적으로 더티 비트를 1로 설정, 해당 페이지 프레임은 교체될 때 그 내용이 디스크에 기록되어야 함

• 더티 비트가 0 이면 클린 상태 라고 하며, 해당 페이지 프레임 내용은 디스크에 쓰여질 필요 없이 새로운 내용으로 덮어쓰여저도 됨(유효한 내용이 이미 디스크에 존재하기 때문)

참조 비트

• 해당 페이지가 읽기 또는 쓰기로 접근되었을 때 설정된다.
• OS 가 페이지 폴트 처리를 위해 교체할 페이지 프레임을 선택할 때 이용된다.

캐시 무효화

• 해당 페이지가 캐싱될 수 있느지 여부를 나타냄

페이징 장점

물리 메모리 할당/해제가 쉽다

External fragmentation이 없다.

• 페이지 단위로 디스크에서 가져오므로 메모리에는 페이지 단위 크기 외의 빈 공간은 생기지 않을 것이다.
• 그러나 internal fragmentation 은 있다.

페이지를 디스크에서 읽고/쓰는 것이 쉽다.

페이징 단점

internal fragmentation이 있다.

• 페이지 단위 크기 내에서 남는 부분이 생길 수 있다.
• 예를 들어 페이지 크기가 4KB이고 17KB 프로그램을 메모리에 적재할 때 마지막 5번째 페이지에는 1KB만 저장되며, 3KB는 페이지 내부에 비어있는 상태이다.

메모리 참조를 2번 해야 된다.

• 페이지 테이블이 메모리에 존재하기 때문
• 페이지 테이블을 보고 또 다시 메모리를 봐야 한다.
• TLB로 해결

페이지 테이블유지하는 데 큰 메모리가 사용될 수도 있다.

• 만약 4KB 크기(2^12) 의 페이지 를 사용할 때, 32비트 시스템에서는 페이지 테이블 크기가 2^20 = 1,048,576 이 된다.

• 64비트 시스템에서는 더욱 커질 것...

• 다단계 페이지 테이블로 구성해서 해결

• TLB (Translation Lookaside Buffer)

대부분 페이지 테이블은 메모리 에 존재한다.

즉, 페이징을 사용한다면 메모리 참조가 최소 2번 이상 일어날 수 있다.

• 맨처음 테이블 참조하는 데 1번, 이후 페이지 테이블에서 구한 실제 물리 메모리 주소를 참조하는데 1번

이는 성능에 좋지 않아 해결법이 필요하다.

이때 컴퓨터 연구자들은 대부분의 프로그램들이 페이지 테이블 엔트리 중에서 일부만 자주 참조하고 나머지들은 드물게 참조한다는 경향이 있다는 것을 알아냈다.

이렇게 탄생하게 된 것이 TLB 이다.

TLB 는 작은 하드웨어 이며 페이지 테이블 참조 없이 가상 주소를 물리 주소로 매핑할 수 있게 한다.
일반적으로 MMU 안에 존재하며 적은 개수의 엔트리를 갖는다.
일종의 페이지 테이블을 위한 캐시 라고 생각하면 된다.

TLB 구조

TLB 동작

1. MMU는 주소 변환 시 요청한 가상 페이지 번호가 TLB에 있는지 검색, 이때 모든 TLB 엔트리를 동시에 검색한다.

2. 페이지가 존재하면 주소 변환 실행

3. 페이지가 존재하지 않으면 TLB miss 발생

• MMU는 페이지 테이블을 검색해서 해당되는 페이지 엔트리 찾음
• 찾은 페이지 엔트리를 TLB 테이블의 엔트리 하나와 교체
• 이후 이 페이지가 다시 참조된다면 TLB hit가 발생함.
• TLB 엔트리가 교체될 때 수정 비트는 페이지 테이블 에 기록

TLB 관리

과거에는 TLB의 관리와 TLB fault 에 관한 처리는 모두 MMU에 의해 처리됬었다.

최근의 RISC 시스템 은 TLB 엔트리의 관리를 OS(소프트웨어)가 한다.

• TLB miss 가 발생하면 MMU는 자신이 직접 처리하는 것이 아니라 OS 에게 TLB 결함 발생을 알린다.
• 그러면 OS 는 해당 페이지 테이블 을 검색하고, TLB에서 엔트리를 선택해 교체하고, 새로운 페이지 정보를 로드하고 결함을 발생한 명령어를 재실행 한다.
• 이 TLB miss는 overhead 가 TLB fault 보다 적어야 한다. fault 보다 miss 가 자주 일어나기 때문이다.

OS는 TLB와 페이지 테이블이 일관성을 유지하도록 해야 한다. (반드시는 아니다)

• OS가 PTE에서 보호 비트를 변경할 때 TLB에 있는 경우 PTE를 무효화해야 한다

프로세스 context switch 발생 시

• 각 프로세스에는 일반적으로 자체 페이지 테이블 이 있다.
  따라서 프로세스마다 TLB 테이블이 다르다

• context switch 발생 시 TLB의 모든 항목을 무효화 해야 한다!
  (플러시 TLB)
  이것은 프로세스 컨텍스트 전환이 비용이 많이 드는 이유이다.

TLB miss 발생되고 새 PTE(페이지 테이블 엔트리)가 로드되면 캐시된 PTE를 제거해야 한다

• 일반적으로 PTE 중에서 제일 오랫동안 access 가 안된 엔트리를 제거한다.

• 대용량 메모리를 위한 페이지 테이블

앞서 말한 페이징의 단점 중 페이지 테이블유지 하는 데 큰 메모리가 사용될 수도 있다. 를 해결하기 위한 방법 2가지를 알아보겠다.

• Multilevel Page Table

32비트 가상 주소가 10비트의 PT1 인덱스 필드, 10비트의 PT2 인덱스 필드, 12비트(4KB) 페이지 크기로 이루어져 있다.

그림에 PT1의 회색 부분은 유지되지 않은 페이지 테이블 엔트리들이고 present/absent 비트 가 0으로 되어 있다.

만약 여기 부분에 접근을 하면 페이지 폴트 가 발생한다.

그림의 예시는 32비트 시스템이지만 만약 64비트나 아니면 32 비트 시스템에서도 가상 주소를 쪼개서 여러개의 페이지 테이블을 만들 수도 있다. (유연성)

그러나 3단계 이상의 레벨이 존재하면 복잡도가 증가한다.

• Inverted Page Tables

32비트 시스템에서 다단계 페이지는 꽤 잘 돌아갔다. 근데 64비트로 넘어오면서 문제가 생겼다.

앞서 32비트 시스템에서 페이지 크기 4KB(2^12)일 때는 페이지 테이블의 엔트리 개수가 2^20 였다.

그러나 64 비트 시스템에서는 무려 페이지 테이블의 엔트리 개수가 2^52나 된다.

따라서 페이지 테이블의 크기가 너무 커지고, 유지하는 데 큰 메모리가 사용되어서 앞에서 말한 페이지 테이블유지하는 데 큰 메모리가 사용될 수도 있다. 라는 문제점을 해결할 수가 없다.

역 페이지 테이블 에서는 가상 주소 공간의 각 페이지마다 엔트리가 하나씩 존재하는 것이 아니라 물리 메모리의 각 페이지 프레임마다 하나의 엔트리가 존재한다.
각 엔트리에는 각 페이지 프레임에 어떤 프로세스의 페이지가 존재하는지에 대한 정보
(프로세스 번호 PID, 가상 페이지 번호 VPN) 이 있다.
이렇게 하면 64비트 가상 주소 공간일지라도 페이지 크기가 4KB 일 때, 메모리가 1GB 이면 2^30/2^12(페이지 크기) = 2^18 개의 엔트리만 생성된다.

장점

가상 주소 공간이 물리 주소 공간에 비해 상당히 클 경우 역 페이지 테이블은 주소 변환을 위한 메모리 공간의 사용을 크게 줄일 수 있다.

단점

가상-물리 주소 변환이 복잡해진다. 프로세스 n 이 가상 페이지 p 를 접근할 때 MMU는 역 페이지 테이블 전체 를 검색하여 해당되는 엔트리가 있는지 검사한다.

또한 이러한 검색 행위는 페이지 폴트 뿐만 아니라 메모리 참조 시 마다 발생한다.
따라서 시스템 성능을 저하시킬 수 있다.

해결방법: TLB 이용

TLB가 자주 접근하는 페이지들의 정보를 유지함으로써 주소 변환을 다단계 페이지 테이블 기법만큼 빠르게 할 수 있다.

그러나 TLB miss 시에는 여전히 역 페이지 테이블 검색을 해야 한다.

이때, 검색을 빠르게 하는 방법으로 가상 주소 기반으로 해쉬 테이블을 이용하는 방법이 있다.

해쉬 테이블이 물리 페이지 프레임 크기 만큼의 슬롯을 가지고 있다면 각 체인은 평균 하나의 엔트리를 가지게 되며 매핑 속도가 증가할 것이다.
페이지 프레임 번호가 발견되면 새로운 (가상, 물리) 정보는 TLB에 적재된다.

5 페이지 교체 알고리즘

페이지 폴트 가 발생하면 OS 는 새로 진입할 페이지를 위한 메모리 공간을 만들기 위해 이미 메모리에 존재하고 있는 페이지를 제거해야 한다.

만일 내보낼 페이지가 변경 되어 있다면 그 페이지의 내용은 디스크로 보내져 기록되어야 한다. (디스크와 동기화를 시켜야 함)

이때 내보낼 페이지를 선택해야 하는데 보통 자주 사용되지 않을 페이지를 고르는 것이 시스템 성능에 도움이 될 것이다.(페이지 폴트를 잘 발생시키지 않을 것이므로)

이제 내보낼 페이지를 선택하는 알고리즘들을 알아보자.

• 최적 페이지 교체 알고리즘

이 알고리즘은 최소한의 페이지 폴트를 발생하기 위해서 미래에 가장 늦게 참조되거나 참조가 더이상 안되는 페이지를 먼저 내보낸다.

그러나 이 알고리즘은 구현이 불가능한데 왜냐하면 OS 는 각 페이지들이 미래의 어느 시점에 참조될지 알 수 없기 때문이다.

앞에 SJF 스케줄링 알고리즘에서 어떤 프로세스가 가장 적은 수행시간을 갖는지 미리 알기 쉽지 않은것처럼 말이다.

• NRU(Not Recently Used)

가상 메모리를 지원하는 대부분의 컴퓨터는 각 페이지마다 OS가 페이지 사용 정보를 수집할 수 있는 2개의 비트를 유지한다.

• 참조(Refrenced bit)R 비트
  페이지가 참조될 때 마다 1로 설정

• 변경(Modified bit)M 비트
  페이지가 변경(수정)될 때 마다 1로 설정

비트의 설정은 하드웨어 가 담당한다.
일단 1로 설정되면 OS가 0으로 클리어할 때 까지 1로 유지한다.

구체적으로 프로세스가 시작할 때 OS는 그 프로세스 모든 페이지의 R, M 비트를 0으로 클리어 한다.

또한 최근에 참조된 페이지를 구별하기 위해 주기적으로(예를 들어 클록 인터럽트 마다) R 비트를 0으로 클리어한다.

페이지 폴트 가 발생하면 OS는 R, M 비트에 따라 페이지들을 4개의 클래스로 분류한다

• 클래스0: 참조되지 않았고, 수정되지 않음 R = 0, M = 0
• 클래스1: 참조되지 않았고, 수정되었음 R = 0, M = 1
• 클래스2: 참조되었고, 수정되지 않음 R = 1, M = 0
• 클래스3: 참조되었고, 수정되었음 R = 1, M = 1

클래스 0 으로 갈 수록 오래된 페이지이다.
따라서 NRU 알고리즘은 0,1,2,3 순서대로 페이지를 교체한다.

가장 오래 안쓰인 페이지를 내보내는 것이 페이지 폴트를 유발할 확률이 가장 적을 것이다.

• FIFO 알고리즘

들어온 순선대로 페이지를 제거후 교체해 나간다.

• Second-Chance 알고리즘

FIFO 알고리즘은 그냥 순서대로 교체해 버리므로 자주 참조되는 페이지를 교체할 수 있다는 문제가 있다.

따라서 R 비트 를 활용해서 자주 참조되는 페이지는 교체가 되지 않도록 하는 방법이 Second-Chance 알고리즘이다.

동작원리

• R이 0이면 그냥 교체
  가장 오래됬으며 최근에 사용되지 않은 페이지

• R이 1이면 이 페이지를 리스트의 맨 뒤로 옮기고 R비트를 0으로 클리어하며 적재시간도 현재시간으로 갱신
  마치 이 페이지가 최근에 적재된 것처럼 기회를 한번 더 주는 것
  나중에 참조가 안되서 R비트가 그대로 0이면 교체해버림

FIFO와 동작원리는 거의 유사하지만 R비트를 확인해서 참조가 된 페이지는 일단 교체 유예 를 해줌

만약 모든 페이지가 참조되었으면 FIFO랑 동작이 같음

그러나 페이지를 리스트에서 이동시켜야 하기 때문에 효율성은 떨어짐

• 클록 페이지 교체 알고리즘

Second-Chance 알고리즘 은 페이지를 리스트에서 이동시켜야 하기 때문에 동작 효율이 떨어질 수 있다.

따라서 리스트를 시계모양의 원형 리스트로 만들어 관리하면 효율이 증가할 것이다.

동작원리

• 화살표는 가장 오래된 페이지를 가리킨다.

• 페이지 폴트가 발생하면 화살표가 가리키는 페이지를 조사한다

  • 이때 가리키는 페이지의 R 비트가 0이면 페이지를 교체한다.

  • R 비트가 1이면 다시 0으로 클리어 하고 다음 페이지로 전진(시계 방향)하여 다음 페이지를 조사한다.
    이 과정은 R이 0인 페이지를 찾을 때 까지 반복된다.

그냥 위에 Second-Chance 알고리즘 의 리스트를 원형 리스트로 바꾼 것이다.

• NFU(Not Freqeuntly Used)

각 페이지 마다 소프트웨어 카운터를 유지, 0 을 초기값으로 갖는다.

클록 인터럽트 가 발생 할 때 마다 OS 는 메모리의 모든 페이지들을 검사하여 R비트의 값을 소프트웨어 카운터에 더함.

이 카운터들은 각 페이지들이 얼마나 자주 참조되었는지 알려 줌.

페이지 폴트 발생 시 가장 적은 카운터 값을 갖는(가장 적게 참조된) 페이지가 교체된다.

문제점
단순히 참조 횟수만 기록하기 때문에 언제 참조되었는지는 기록이 안되어있음

따라서 맨 처음에만 자주 참조되고 이후 긴 시간 동안 참조되지 않은 페이지가 교체되지 않고
최근에 한번 참조된 페이지(앞으로도 자주 참조될 유용한 페이지)가 교체될 수 있음

• Aging

클록 틱 마다 참조된 페이지를 나타냄

이후 페이지 폴트 발생 시 카운터 값이 가장 적은 페이지가 교체된다.

문제점
어떤 페이지가 먼저 참조되었는지 알 수 없다.

만약 그림의 (a)에서 페이지 폴트가 발생하면 1,3중 누굴 교체해야 할 지 모른다.

• 작업 집합 페이지 교체 알고리즘

순수한 형태의 페이징 시스템에서는 프로세스가 시작할 때 미리 메모리에 존재하는 페이지는 없다.
프로세스 는 자신이 필요한 대부분의 페이지를 폴트 를 통해 메모리로 올리게 되고 이후에는 비교적 적은 페이지 폴트 를 야기하며 실행된다.

이러한 전략을 요구 페이징(Demand Paging) 이라고 한다.

미리 페이지를 메모리에 적재하는 것이 아니라 필요할 때 적재하는 것이다.

대부분의 프로세스는 자신의 전체 주소 공간의 일부 페이지들을 집중적으로 참조하는 참조 지역성 을 보인다.

이때 프로세스가 현재 자주 참조하는 페이지들의 집합을 작업 집합(Working Set) 이라고 한다.

메모리에 접근할 때 페이지 폴트율이 높은 것을 threshing 이라고 한다.

작업 집합 모델

다중 프로그래밍 시스템에서 프로세스는 다른 프로세스들이 실행할 기회를 주기 위해 자주 디스크로 내려간다 (해당 프로세스들의 모든 페이지들이 메모리에서 제거)

이때, 다시 프로세스가 실행된다면 페이지 폴트 로 이 페이지들을 디스크에서 불러와야 한다. 따라서 시간이 걸린다.

많은 페이징 시스템은 프로세스의 작업 집합을 파악하고 이들을 프로세스가 시작하기 전에 메모리에 유지하기 위해 노력한다.

이러한 접근 방법을 작업 집합 모델(Working Set Model) 이라고 한다. 이 모델은 페이지 폴트 를 줄이는 것을 목표로 한다.

작업 집합 모델을 구현하기 위해서 OS 는 어떤 페이지들이 작업 집합에 속하는지 파악해야 한다. (또한 이 정보는 페이지 교체 알고리즘에도 사용될 수 있다.)

페이지 폴트가 발생했을 때, 메모리에 존재하는 페이지 중에서 작업 집합에 속하지 않는 것들을 찾아 교체하면 된다.

프로세스가 시작되어 실제로 사용한 CPU 시간을 각 프로세스의 현재 가상 시간 이라고 한다.

이러한 근사를 사용하면 한 프로세스의 작업 집합은 최근 τ 가상 시간 동안 참조된 페이지의 집합으로 정의된다.

작업 집합 알고리즘

기본 아이디어는 '현재 작업 집합에 포함되어 있지 않은 페이지를 교체하자' 는 것이다.

교체의 대상이 되는 것은 이미 메모리에 존재하는 페이지 이며 존재하지 않는 페이지들은 알고리즘의 고려 대상에서 제외된다.

페이지 테이블의 각 엔트리는 최소 두개의 키 정보를 유지한다

• Time of last use
• Reference Bit
  

알고리즘 동작

• M과 R 비트는 하드웨어가 관리한다.
• 매 클록 틱 마다 클록 인터럽트에 의해 소프트웨어적으로 R 비트는 주기적으로 클리어 된다.
• 페이지 폴트 가 발생하면 페이지 테이블을 검사하여 교체할 페이지를 선택한다.
• 현재 가상 시간 은 페이지 폴트 발생 후 R == 1 일 때 기록 되지만, 클록 인터럽트 마다 R == 1 일 때 도 기록될 수 있음

1. 우선 각 페이지 엔트리에서 R 비트를 검사

• 만약 R == 1 이면 현재 가상 시간을 엔트리의 Time of last use 필드에 기록 (페이지 폴트가 발생한 시각에 그 페이지가 사용 중이었음을 기록)
• 일반적으로 τ는 여러 클록 틱으로 구성된다

2. R == 0 이면 교체의 후보가 됨

• 이번 클록 틱이 발생한 간격에 참조되지 않았다는 의미
• 교체의 여부는 페이지의 age(현재 시간 - Time of last use) 에 따라 결정됨
• 만약 age > τ 이면 이 페이지는 작업 집합에 더이상 포함되어 있지 않다는 의미이며 새로운 페이지가 이것을 교체
• age ≤ τ 이면 이 페이지는 여전히 작업 집합에는 포함되어 있고 교체의 대상은 아님. 대신 가장 큰 age를 갖는 페이지를 기억해 둠
  • 전체 페이지 테이블을 검사한 이후 교체할 페이지를 찾지 못하면 R == 0 인 페이지 중에서 age가 가장 큰 페이지를 교체
  • 최악의 경우 모든 페이지의 R 이 1 이면 그냥 임의로 하나 교체해버림
  • 가능한 수정되지 않은 페이지를 교체하려 함

• WSClock 페이지 교체 알고리즘

기존의 작업 집합 페이지 교체 알고리즘은 페이지 폴트가 발생할 때 마다 교체할 페이지를 선택하기 위해 전체 페이지 테이블을 검색해야 한다는 것이다.

그렇다면 위에서 봤던 클록 알고리즘처럼 페이지 프레임들을 원형 리스트로 관리하면 일일이 전체 페이지 테이블을 찾아보지 않아도 될 것이다.

초기에 이 리스트는 비어 있다.
각 리스트 엔트리는 작업 집합 알고리즘에서도 사용하는 Time of last use 필드 , R비트 , M비트 를 갖는다.

알고리즘 동작

페이지 폴트 가 발생하면 화살표가 가리키는 페이지부터 검사한다.

• R == 1 이면

  1. 이 페이지는 최근 클록 틱 간격에서 참조된 것이므로 교체하지 않음
  2. Time of last use 를 현재 가상 시간 으로 변경 후, R을 0으로 설정하고 화살표를 다음 페이지(시계 방향)으로 전진하여 계속 검사
     

• R == 0 이면

  • age(현재 시간 - Time of last use) < τ 이면 넘어감

  • age(현재 시간 - Time of last use) > τ 이고 M == 0 이면(페이지 수정 안됨) 이 페이지 교체
    

  • age > τ 이고 M == 1 이면(페이지 수정됨) 이 페이지 내용 우선 디스크에 기록 후 다음 페이지 검사 계속.
    (프로세스 간 교체를 피하기 위해 이 페이지 내용의 디스크 쓰기를 스케줄링 한 후 다음 페이지 검사함)

클록의 화살표가 시작했던 위치로 다시 돌아왔을 때

두가지의 경우를 생각해 볼 수 있다.

1. 최소한 하나의 쓰기가 스케줄링 되어 있는 경우

• 교체할 페이지 하나를 발견했는데 M == 1 이라 디스크에 쓰고 있는 중임
• 화살표를 계속 전진시켜 M == 0 인 페이지(수정되지 않은 클린한 페이지)를 찾는다.
• 처음 발견한 M == 0 인 페이지를 교체한다.
  • 단 이 페이지는 가장 먼저 쓰기를 스케줄링 한 페이지가 아닐 수 있다. 디스크 드라이버가 최적화를 위해 쓰기 순서를 바꿨을 수도 있음.

2. 아무런 쓰기도 스케줄링 되어 있지 않은 경우

• 모든 페이지가 작업 집합에 속해있는 경우이다.
• 알고리즘은 M == 0 인 페이지 중에 하나를 교체할 페이지로 선택
• 만약 모든 페이지가 수정되었다면(클린 하다면) 현재 화살표가 가리키는 페이지 선택해서 디스크에 쓰고 교체함.

• 페이지 교체 알고리즘 요약

6 페이징 시스템의 설계 이슈

• 지역/전역 할당 정책

위에서 페이지 폴트 발생 시 교체할 페이지를 선택하는 여러 교체 알고리즘들을 알아보았다

이때, 서로 경쟁하는 프로세스들 간에 어떻게 메모리를 할당하는가?

메모리를 지역적/전역적 으로 할당하는 방법이 있다.

지역적 할당

각 프로세스에 고정된 비율의 메모리를 할당할 수 있다는 장점이 있다.

로컬 교체: 일부 프로세스는 잘 작동할 수 있지만 다른 프로세스는 작업 세트가 확장되거나 축소될 때 어려움을 겪을 수 있다.

전역적 할당

실행중인 프로세스들의 요구에 따라 동적으로 페이지를 할당할 수 있다는 장점이 있다.

글로벌 교체 : 하나의 프로세스가 나머지 프로세스를 망칠 수 있다.
위에 그림(c)를 보면 A가 B의 공간을 침범한다.

일반적으로 글로벌 알고리즘이 더 잘 작동한다.
각 프로세스에 할당된 프레임 수를 동적으로 결정해야 한다.

PFF(Page Fault Frequency) 알고리즘

많은 페이지 교체 알고리즘에서 할당된 페이지의 개수가 커지면 페이지 폴트율이 감소한다. 이것이 PFF 의 기본 아이디어 이다.

PFF 는 전역 알고리즘으로 각 프로세스에 대한 페이지 폴트 비율을 모니터링 한다.

• 페이지 폴트율을 측정하는 것은 간단한데, 초당 페이지 폴트 횟수를 세기만 하면 된다.

알고리즘 분류

FIFO, LRU 알고리즘 은 지역적일 수도 있고 전역적일 수도 있다.

반면에 Working Set 알고리즘 은 지역적이다.
각 프로세스와 관련 있어 프로세스 별로 적용되어야 한다.

• 부하 제어 (Load Control)

어느 프로세스에서 thrashing 이 많이 발생한다? 메모리가 부족하다는 이야기이다.

이를 해결하려면 일부 프로세스를 메모리에서 제거해야 한다: 스와핑
(사실 큰 메모리를 사는게 더 좋긴 한데)

• 페이지 크기

페이지 크기는 OS가 설정할 수 있다.

작은 페이지 크기

장점

• 페이지 크기가 작아지면 내부 단편화(internal fragmentation) 로 인한 낭비를 줄일 수 있어서 유연성이 증가한다.

단점

• 페이지 크기가 작아지면 더 많은 페이지가 생기고, 페이지 테이블 크기가 커진다.
• 페이지 폴트가 더 자주 일어날 수 있다.

큰 페이지 크기

위와 정 반대이다.

장점

• 페이지 크기가 커지면 페이지 테이블 크기가 작아진다.
• 디스크 접근 시간이 줄어든다(한번에 큰 페이지를 가져오므로)

단점

• 내부 단편화가 커져서 메모리 낭비가 생긴다.

• 명령어와 데이터 공간 분리

대부분의 컴퓨터는 프로그램과 데이터를 같은 주소 공간에 유지한다.

만약 메모리 크기가 작다면 분리된 주소 공간을 사용하는데 명령어와 데이터를 I(Instruction)-space, D(Data)-space 라고 불리는 서로 다른 주소 공간에 유지한다.

분리된 주소 공간을 사용하는 시스템에서 각 주소 공간은 서로 다른 페이지 테이블을 가지며, 가상주소를 물리주소로 변환하는 서로 독립적인 매핑 정보를 유지한다.

• 공유 페이지

대규모 다중 프로그래밍 시스템에서는 여러 사용자들이 동시에 같은 프로그램을 실행하는 경우가 흔히 있는 일이다.

이 경우 메모리에 같은 페이지를 두개 유지하는 것 보다는 페이지를 공유하는 것이 더 효율적이다.

• 이때 프로그램 텍스트 같은 읽기 전용 페이지만 공유 가능하다.
• 데이터는 공유될 수 없다.(프로세스들의 데이터는 다르므로)

그림에서 보면 2개의 프로세스가 하나의 페이지 프레임을 공유하고 있는데 만약 어느 한 프로세스가 종료 되어도 다른 프로세스가 여전히 페이지를 사용 중이므로 이들을 파악해서 해제하지 말아야 한다.

Copy-On-Write

write(쓰기) 발생 시 실제로 복사가 일어난다

UNIX 의 fork() 시스템 호출을 다시 생각해보자

부모 프로세스가 자식 프로세스를 생성할 때 자식 프로세스는 부모 프로세스의 주소 공간을 복사한다고 했는데 메모리를 그대로 복사해 가는 것이 아니고 페이지 테이블만 복사를 한다.

그럼 언제 메모리의 복사가 일어나느냐?

어느 한 프로세스가 데이터에 수정을 시도하면 READ ONLY 속성에 위반이 생기고 쓰려는 데이터가 저장된 페이지에 대한 복사가 발생하며 각 프로세스는 자신의 고유한 페이지를 가리키게 된다.

즉, 부모-자식이 서로 같은 페이지를 READ ONLY로 공유하고 있었는데 어느 한 프로세스가 수정이 되면 둘의 페이지가 달라지므로 수정되는 페이지를 복사를 해서 각 프로세스가 자신의 고유한 페이지를 가리키게 해야 한다.

이렇게 안하면 부모 프로세스 수정했더니 자식도 바뀌는 황당한 일이 벌어질 것

• 공유 라이브러리

최근 시스템에서는 많은 라이브러리가 사용된다. 따라서 프로세스마다 이 라이브러리를 계속 적재하는것은 메모리 낭비가 될 수 있다.

이 때 사용되는 방법이 공유 라이브러리 (또는 Dynamic Link Libraries: DLL) 이다.

공유 라이브러리는 프로그램이 메모리에 적재될 때 함께 적재되거나 소속 함수가 처음 호출될 때 적재된다.
만약 다른 프로그램이 이미 공유 라이브러리를 적재해 놓았다면 다시 적재할 필요가 없다. 이게 핵심이다.

C로 짜여진 두 프로그램을 상상해보자.

C 프로그램은 stdio 같은 기본 입출력 라이브러리등 많은 라이브러리가 있는데 매번 C 프로그램 실행할 때 마다 이걸 적재하면 메모리 낭비가 될 것이다.
따라서 공유 라이브러리를 사용하자는 아이디어 이다.

공유 라이브러리는 각각의 프로세스의 다른 주소공간에 매핑된다.

장점

공유 라이브러리의 함수가 갱신되면, 그것을 사용하는 프로그램을 다시 컴파일할 필요가 없다.
기존의 바이너리 파일이 잘 작동함

단점

공유 라이브러리는 각각의 프로세스의 다른 주소공간에 매핑된다.

이때, 라이브러리의 첫번째 함수의 역할이 내부주소로 분기하는 것이라 가정하면
라이브러리가 공유되기 때문에 서로 다른 프로세스에서 똑같은 주소로 분기하게 된다.
(위의 그림 참고)

• 파일 매핑

파일 자체를 가상 주소 공간에 매핑하는 것.
위에서 본 공유 라이브러리는 메모리 맵 파일 의 특별한 경우이다.

메모리 맵 파일은
프로세스가 시스템 호출 을 이용하여 파일을 자신의 가상 주소 공간에 매핑하는 것을 가능하게 한다.

만약 두개 이상의 프로세스가 동시에 같은 파일을 매핑하면 공유하는 효과를 낼 수 있다 (공유 라이브러리)

• 클리닝 정책

페이징의 적절한 동작을 위해서는 페이지 폴트 시 이용할 수 있는 페이지(빈 페이지)가 충분해야 한다. (그래야 새로운 페이지를 디스크로부터 적재하므로)

만약 모든 페이지 프레임들이 사용 중 or 변경되었다면 기존의 페이지가 디스크에 기록된 후 새로운 페이지를 적재해야 한다.

충분한 가용 페이지 프레임을 제공하기 위해 대부분의 페이징 시스템은 페이징 데몬 이라는 백그라운드 프로세스를 사용한다.

페이징 데몬 역할

• sleep 상태에 있다가 주기적으로 wake 해서 메모리 상태 검사

• 가용 페이지 프레임이 적다면 페이지 교체 알고리즘을 통해 페이지를 선택해 제거해서 가용 페이지 늘림

  • 만약 이 페이지가 변경되었으면 디스크에 기록

• 제거된 페이지의 내용이 (덮어쓰여지기 전에) 다시 필요해지면 가용 페이지 프레임 풀 에서 다시 꺼내 사용할 수 있다.

• 페이징 데몬은 모든 가용 프레임이 더티하지 않은 상태로 유지되도록 노력하고 급하게 디스크로 쓰려는 것을 방지함

7 구현 이슈

가상메모리 시스템의 공통적인 구현 이슈를 살펴보고 해결방안에 대해 정리하겠다.

• 페이징과 관련된 OS 작업

OS가 페이징과 관련된 작업을 하는 것은 크게 4가지의 경우이다.

1. 프로세스 생성

프로세스 생성 시 OS 는 프로그램과 데이터를 위해 얼마만큼의 공간을 할당해야 하는지 결정한다.

페이지 테이블을 만들고 초기화 한다.

스왑 공간은 반드시 할당 & 초기화 되어야 한다.

2. 프로세스 실행

MMU 는 새로운 프로세스를 위해 리셋된다.

TLB에 존재하던 기존 프로세스의 주소 변환 정보를 제거한다.

페이지 테이블에 대한 정보를 최신상태 (새로운 프로세스에 대한 정보) 로 만든다.

3. 페이지 폴트 발생 시

OS 는 폴트를 발생시킨 가상 주소를 파악하기 위해 하드웨어 레지스터를 읽는다.

교체할 페이지를 메모리에서 제거하고 필요한 페이지를 적재한다

프로그램 카운터를 페이지 폴트를 발생시킨 명령을 가리키도록 설정해서 다시 실행되도록 한다.
(너가 원하는 페이지 가져왔으니 다시 읽어라)

4. 프로세스 종료 시

OS 는 그 프로세스의 페이지 테이블, 페이지, 디스크 공간(프로세스의 페이지들이 스왑 아웃 되었을 때 존재하던 공간) 등을 반납한다.

• 페이지 폴트 처리

페이지 폴트를 처리하는 과정을 자세히 알아보겠다.

1. 하드웨어는 커널에게 트랩을 발생시킨다.

• 스택에 PC 저장

2. 어셈블리 코드 실행. 이 코드는 범용 레지스터 내용과 휘발성 정보를 저장해서 OS 가 트랩 처리 이후에 이들을 복구할 수 있도록 한다.

• 또한 이 코드는 OS 를 호출한다.

3. OS가 페이지 폴트를 인식하고 어떤 가상 주소인지 파악

• 일반적으로 가상 주소는 하드웨어 레지스터 에 있음
• 하드웨어에 없으면 OS 는 PC 를 이용해 명령어를 반입하고 분석함

4. OS가 주소 및 보호의 유효성을 확인(접근 권한이 있는가), 필요한 경우 교체할 페이지 프레임을 찾는다.

• 유효하지 않으면 프로세스에게 시그널 을 보내거나 종료 시킴
• 유효하면 가용 페이지 프레임 을 찾음, 없으면 페이지 교체 알고리즘 동작 -> 교체할 페이지 찾음

5. 교체를 위해 선택한 프레임이 변경되었다면 디스크에 쓰기

• 요청이 스케줄링 되고 context switch 가 발생, 다른 프로세스가 실행
• I/O 수행동안 해당 페이지 프레임을 busy 상태로 표시하여 다른 목적으로의 활용 금지함

6. 페이지 프레임의 상태가 clean 이 되면 OS 는 새로운 페이지를 디스크에서 가져와 적재함

7. 페이지 테이블 업데이트

• 5에서 busy 상태로 표시한 페이지 프레임을 다시 정상 으로 표시

8. 페이지 폴트를 발생시킨 명령어가 초기 실행되던 상태로 돌아감

• PC는 다시 이 명령의 위치를 가리켜서 재실행 하게 함

9. 페이지 폴트를 발생시킨 프로세스가 스케줄링 됨

• OS 는 2단계의 어셈블리 루틴으로 복귀

10. 어셈블리 루틴은 레지스터 및 다른 상태 정보를 복구하고 유저공간으로 복귀함

• 기존 프로그램이 결함 발생 안했던 것처럼 계속 실행된다.

• 명령 백업

(나중에 정리)

• 페이지 락

(나중에 정리)

• Backing Store (예비 저장장소)

페이지 교체 알고리즘에서 교체된 페이지들이 디스크 상의 어디에 저장되는지에 대해 자세히 알아보겠다.

Swap 파티션 사용

디스크 상에서 교체된 페이지를 위한 공간을 관리하는 가장 간단한 방법이다.

별도의 스왑 파티션을 사용해서 I/O 부하를 분산한다.

이떄 이러한 파티션의 관리를 위해 일반적인 파일 시스템 대신 파티션의 시작 주소에 상대적인 블록 번호로 전체 공간을 관리한다.

• 시스템이 부팅되면 스왑 파티션은 비어있는 상태가 되고 메모리에는 이를 관리하기 위한 자료구조가 생성

  • 가용 공간의 시작을 스왑 파티션의 시작주소로 함
  • 가용 공간의 크기는 전체 스왑 파티션의 크기로 설정된다.

• 메모리의 테이블과 스왑 파티션은 일대일 대응이다.

• 스왑 공간의 페이지들은 연속적으로 할당되어 있다.

  • 페이지는 스왑 공간에 순서대로 기록되며, 스왑 공간이 시작하는 위치만 알면 된다.

• 각 프로세스는 자신에게 할당된 스왑 공간 주소 (자신의 이미지의 일부가 스왑 파티션 어디에 저장되어 있는지) 에 대한 정보를 관리한다. 이 정보는 프로세스 테이블에 유지된다.

스왑 파티션 사용 기법은 프로세스의 크기가 실행 중 증가할 경우 문제가 될 수 있다.
따라서 텍스트, 데이터 및 스택을 위한 스왑 영역을 별도로 관리하는 것이 적절하다.

동적 할당

페이지 교체가 발생할 때 마다 스왑 공간을 각 페이지 별로 동적 할당하는 방법이다.

8 세그멘테이션

지금까지의 가상 메모리는 1차원적, 즉 가상 주소는 0부터 시작하여 특정 크기만큼 자라며 주소는 순차적으로 증가하였다.

하지만 2개 또는 그 이상의 분리된 가상 주소 공간 을 갖는 것이 하나의 주소 공간보다 편리한 경우가 많다.

• 하나의 주소 공간을 갖는 경우

아래와 같은 1차원 주소 공간은 테이블이 증가하면서 다른 공간과 충돌을 일으킬 수 있다.

시스템이 각 메모리 부분을 증가하거나 감소시키는 작업을 제공해 준다면 좋을 것이다.

• 세그먼트

위의 1차원 주소공간의 충돌을 방지하기 위해 시스템은 세그먼트 라고 부르는 여러 개의 서로 완전히 독립된 주소 공간들을 제공한다.

세그먼트 특성

• 각 세그먼트는 0부터 시스템에서 허용된 최대 크기까지 값의 선형 주소로 구성된다.

• 흔히 서로 다른 세그먼트는 서로 다른 크기를 갖는다.

• 세그먼트 크기는 실행중에 변할 수 있다.

  • 스택의 크기는 새로운 데이터가 추가될 때 증가하며 추가된 데이터가 삭제 시 감소한다.

• 한 세그먼트는 다른 세그먼트들에게 영향을 주지 않고 독립적으로 증가하거나 감소할 수 있다.

  • 특정 세그먼트에 존재하는 스택이 증가하고 싶으면 그냥 증가하면 된다.
  • 물론 세그먼트의 최대 크기 이상으로 증가할 수는 없다.

• 세그먼트는 프로그래머가 인식하고 있는 논리적인 객체이다.

• 세그먼트는 함수를 포함할 수도 있으며 배열, 스택, 변수들의 집합을 포함할 수도 있다.

세그먼트

세그먼트 머신에서 가상 주소는 <세그먼트 번호, 세그먼트 내부 주소(오프셋)> 으로 표현된다.

세그먼트 장점

• 증가하거나 감소하는 자료구조의 관리를 간단하게 한다.

  • 독립적인 주소 공간으로 나누어서 서로 충돌을 방지한다
  • 자유롭게 크기 조정이 가능하다.

• 컴파일된 함수들의 링킹 작업이 매우 단순해진다.

  • 프로그램을 구성하는 모든 함수들이 컴파일되고 링킹 완료 되면 N번째 세그먼트에 존재하는 함수의 호출은 (n,0) 주소로 하면 된다.
  • 주소 0 은 시작점이 된다.
  • 만약 n번째 세그먼트의 함수가 수정되고 다시 컴파일 되도 시작 주소가 바뀌지 않았기 때문에 다른 함수는 전혀 변경할 필요가 없다.

• 함수나 데이터를 여러 프로세스들이 공유하기 쉽다.

  • 공유 라이브러리가 대표적인 예이다.

• 서로 다른 세그먼트는 서로 다른 보호 모드를 가질 수 있다.

세그먼트 단점

• external fragmentation 이 발생할 수 있다.

  • 이를 해결하려면 메모리 조각모음 (compaction) 이 발생할 수 있다. 조각모음은 비용이 많이 든다...

• 세그먼트에 연속적인 메모리를 할당하는 데 비용이 많이 든다.

• 메모리는 전체 세그먼트에 할당된다.

• 세그먼트 vs 페이징

• 세그멘테이션 + 페이징

만일 세그먼트의 크기가 크다면 이를 모두 메모리에 적재하는것은 어렵다.

그렇다면 세그먼트에 페이징 개념을 도입하면 어떨까?

앞에서 봤던 2레벨 페이징과 거의 유사하게 동작한다.

다만 세그먼트는 사이즈가 있기 때문에 페이지 테이블 엔트리의 수가 사이즈에 따라 달라질 수 있다.

세그먼트 TLB

앞에 페이징에서 처럼 주소 변환에 시간이 오래 걸릴수 있다.

따라서 세그먼트 TLB를 사용해서 시간을 줄일 수 있다.

원하는 가상 주소가 TLB 에 있으면 여기에 있는 페이지 프레임 번호 를 이용해서 물리 주소를 한번에 계산한다.

따라서 세그먼트 테이블 과 세그먼트 페이지 테이블 을 참조할 필요가 없다.

세그멘테이션 + 페이징 장단점

장점
세그멘테이션의 장점 + 페이징의 장점 가짐

단점
내부 단편화(internal fregmetation) 존재

메모리 접근 오버헤드 (반드시 2레벨로 해야 함)