Chapter 07 메모리 관리

프로그램이 실행되기 위해서는 메모리에 올라와 있어야 한다.

따라서 메모리를 잘 관리하면 프로그램 실행 성능을 높여

CPU의 효율적인 사용과 사용자에게의 빠른 응답성을 가능하게 하므로 효과적인 메모리 관리는 중요하다.

 

<핵심 내용>

: 디스크(보조기억장치)에 있는 많은 프로그램 중 몇 개를 메모리의 어디에 어떻게 적재할 것인가!

(데이터의 저장이 목적인 큰 용량의 보조기억장치에 반해,

메모리는 실행될 프로그램을 위한 적재 장소로서 그 크기가 디스크보다는 매우 작다.)

- 메모리의 구성 방식

- 주어진 구성과 연관하여 시스템의 성능을 고려한 관리 기법들

 

메모리의 구성?

메모리의 구성과 메모리의 관리는 밀접한 연관이 있다.

다시 말해, 메모리를 관리하기 위한 기법은 그 대상이 되는 메모리의 구조에 의존적이어서

일단 구성이 정해지면 그것에 맞는 적절한 관리 기법이 검토되는 것이다.

 

<메모리 구성과 관련해 정해져야 할 것들>

▶ 다중 프로그래밍의 정도(Multiprogramming Degree)

= 동시에 메모리에 저장되는 프로세스의 개수

: 단일 프로그래밍 vs 다중 프로그래밍

▶ 각 프로세스에게 얼만큼의 메모리를 줄 것인가? ㅡ 메모리의 분할(Partition) 방식과 연계

: 한 분할 당 한 프로세스를 수용할 수 있으므로 메모리의 분할을 k개로 하면

다중 프로그래밍의 정도가 최대 k가 되는 것이며,

각 분할의 크기를 어떻게 하느냐에 따라 프로세스들에 부여되는 메모리 양을 같거나 다르게 할 수 있다.

▶ 각 분할의 크기를 어떻게 하느냐? ㅡ 고정(Fixed) 또는 정적(Static) 분할 vs 가변(Variable) 또는 동적(Dynamic) 분할

ㄴ고정 분할: 각 프로세스가 들어 갈 분할을 지정하고 항상 그 분할로 적재할 것인지,

                    아니면 상황에 따라 다른 분할로의 적재도 가능하도록 할 것인지를 결정.

                    (프로세스가 시스템에 있는 동안 몇 번에 걸쳐 메모리와 디스크 사이를 오갈 수 있기에,

                    그때마다 다른 분할로의 적재 가능성도 염두해 두어야 한다.)

▶ 프로세스에게 메모리를 할당할 때 연속적 vs 비연속적(Non-contigunous)으로 할 것인가?

ㅡ 이 장에서는 연속적 할당을 전제로 할 것이며, 비연속적의 경우 다음 장에서 자세하게 설명한다.

 

프로세스와 프로그램?

- 프로세스: 실행하고자 하는 내용을 담고 있는 프로그램 + 정상적 실행을 위해 시스템으로부터 제공받아야 하는 제반 환경

- 프로그램: 프로세스를 형성하는 한 축을 담당.(실행 때 필요한 데이터를 자연스레 포함)

cf. 저장장치 관점에서의 프로세스 크기 = 프로그램 크기

: 디스크와 메모리 같은 저장 장치와 프로세스 사이의 문제를 다루는 부분에서는

  저장이나 적재 그리고 그에 따른 주소의 문제가 가장 큰 관심사가 되고,

  이것은 실행 환경보다는 프로그램의 크기나 구성에 훨씬 집중한다는 말이다. 

 

메모리의 관리?

<주어진 메모리 구성에 따라 효율적 관리를 하기 위한 기법들>

■ 적재 기법 (Fetch Strategy)

: 프로세스에게 언제 메모리를 할당해 줄 것인가.(언제 프로세스를 메모리에 적재할 것인가.)

1) 요구(Demand) 적재: 적재의 요구가 있을 때 적재 ㅡ* 대부분 이 방법 사용

2) 예상(Anticipatory) 적재: 적재의 요구가 있을 것으로 예상하고 미리 적재

 

■ 배치 기법 (Placement Strategy)

: 프로세스들을 메모리 공간의 어디에 적재할 것인가

- 고정 분할의 경우는 위에서 말한 대로 지정된 분할로만 적재할지

  아니면 분할을 달리해가며 적재될 수 있도록 할 것인지만 결정하면 된다.

- 가변 분할의 경우에는 몇 가지 적합(Fit) 기법이 있다. (추후에 자세히 설명)

 

■ 교체 기법 (Replacement Strategy)

: 메모리 공간이 부족할 경우 새로 적재돼야 할 프로세스를 위해

이미 메모리에 있는 프로세스 중 어떤 것을 골라 디스크로 내보내고 그 공간을 확보할 것인가 (9장)

 

■ 할당 기법 (Allocation Strategy)

: 프로세스에게 메모리 공간을 얼마 정도로 줄 것인가를 결정 (8,9장)

* 이 장에서는 프로그램 전체를 수용할 수 있는 크기로 주는 것으로 가정한다.

 

메모리의 각 구성에 따른 관리 기법들을 단순한 것부터 차례로, 시스템의 성능을 생각하면서 살펴보자.

 

단일 프로그래밍

 : 한 번에 하나의 프로세스만이 메모리에 적재되고 실행이 종료되면, 다음 프로세스가 적재되는 시스템

-> 메모리에서 커널이 차지하는 공간을 제외한 나머지 전부가 하나의 프로세스에게 주어지게 되므로,

    프로세스가 차지하고 남은 공간은 종료할 때까지 낭비될 것임.

(관리의 측면에서는, 분할과 배치, 할당 등에서 해 줄 일이 별로 없어 매우 단순한 시스템이기는 하나)

 

예상되는 몇 가지 문제들

1) 메모리의 크기가 적재할 프로그램의 크기보다 작을 경우

→ 프로그램의 일부분만을 먼저 적재하여 실행시킨 다음,

    나머지 부분들을 다시 적재하여 실행을 이어가는 오버레이(Overlay) 방식을 사용

2) 프로그램의 실행 중 커널 영역을 침범하지 못하도록 하는 보호 기법 요구

= 실행 중인 프로그램이 커널 영역에 속하는 주소에

   쓰기와 같은 명령을 함으로써 운영체제를 손상시킬 가능성을 방지하여야 함

→ 프로그램이 실행되면서 참조하는 메모리 주소값이

    커널과 프로그램의 경계 값을 침범하는 경우 트랩으로 실행을 중지시킴.

 

=> 단일 프로그래밍은 빈 공간으로 남는 메모리는 물론 CPU와 다른 자원들의 낭비 또한 많아서

     시스템의 성능을 매우 떨어트리게 되므로 다중 프로그래밍이 사실상 필수이다.

 

고정 분할에서의 다중 프로그래밍

: 메모리를 여러 개의 분할로 나누어 놓고,

  각 분할에는 하나의 프로세스만을 수용하도록 함으로써 다중 프로그래밍을 구현하는 방식.

- 이미 정해진 분할을 고정이므로 크기와 개수가 변하지 않고,

  이때의 다중 프로그래밍 정도의 최대치는 분할의 개수와 같다.

 

>장점

- 관리의 쉽고 편리함

 

> 단점

1) 다양한 상황에 유연하게(Flexible) 대처하지 못함

* 분할의 크기를 모두 같게 하면 프로세스들에게 같은 크기의 메모리를 주게 되고,

  현실적으로 프로세스들의 크기가 다양할 것을 예상해보면 분할의 크기 역시 다양하게 해 둘수록 더 유연해 보이나,

  유연함(Flexibility)은 복잡도(Complexity)를 동반할 수 밖에 없다.

 

2) 특정 분할로의 쏠림 현상이 발생할 때, 비어있으나 활용되지 못하는 다른 분할들의 낭비 발생

: 프로그램들이 컴파일 될 때 주소지정이 이루어지는 경우,

  메모리의 할당은 절대(Absolute)로더에 의해 언제나 지정된 분할로 들어가게 된다. (항상 메모리의 같은 위치로)

= Address binding이 미리 되어버리면, 매우 간단하고 빨리 끝나버리지만

  실제로 메모리에서 보면 언제나 지정된 분할로만 들어가야 한다.

-> 재배치(Relocatable) 가능 코드로 컴파일 하여 재배지 로더가 비어 있는

    어느 분할로도 들어갈 수 있도록 해주어 메모리 낭비 줄일 것.

 

3) 가장 큰 분할보다 더 큰 프로그램의 수용 문제

-> 오버레이 방법으로만 해결 가능.

 

4) 메모리의 보호: 여러 사용자가 있기에 단일 프로그래밍보다 좀 더 주의 요구.

- 사용자와 커널 사이뿐 아니라 사용자와 사용자 사이에도 침범하지 못하도록!

-> 분할 사이의 경계는 분할할 때 이미 알려질 것이므로, 실행 중인 프로세스가 자리한 분할의 아래, 위 경계를 두 개의 경계 레지스터에 기록하여 실행 도중 참조하는 메모리 주소가 이 값들을 벗어나지 않는다면 계속 실행이 되도록 한다.

 

5) 메모리 공간의 단편화(Fragmentation) 

- 내부(Internal) 단편화: 이미 고정된 크기로 정해져 있는 분할 내에 프로세스를 수용하고 남는 공간들의 낭비 (필연적)

- 외부(External) 단편화: 분할의 크기가 워낙 작아 프로세스들을 수용하지 못해, 분할이 통째로 낭비되는 현상 (경우에 따라)

 

=> 고정 분할은 관리가 쉬운만큼 오버헤드도 적지만, 다중 프로그래밍 정도를 상황에 따라 더 늘릴 수 없고,

단편화로 인한 메모리의 낭비를 겪을 수밖에 없다. 이 문제의 해결 방법은 프로세스의 크기만큼

그때그때 메모리를 할당해 주는 가변 분할 방법이다.

 

장단점 정리

1. 관리가 쉬우며 오버헤드가 작다.

2. 다중 프로그래밍의 정도가 고정

3. 단편화에 따른 메모리 낭비

 

가변 분할에서의 다중 프로그래밍

: 분할의 시기와 개수 그리고 크기가 사전에 정해진 바 없이, 프로세스를 수용할 때 그 크기만큼 메모리 공간을 할당해준다.

- 상황에 따라 다중 프로그래밍 정도 조절 가능

- 내부 단편화 방지 가능

- but, 관리가 복잡해지므로 인해 생기는 오버헤드 발생

 

가변 분할의 관리를 위해서는...

- 메모리에서 사용 중인 공간과 빈 공간들에 대한 정보 필요

(테이블이나 리스트와 같은 자료구조로 표현)

- 리스트에서 각 공간들을 나타내는 노드(Node)들에는 리스트의 운영을 위해,

  사용 중일 경우 사용자 프로세스 이름과 공간의 크기, 다음 노드에 대한 포인터 등의 정보를 가짐.

 

<배치기법>
: free를 탐색해 적재가 가능한 빈 공간을 찾을 때 어떤 노드를 선택할 것인가

■ 최초적합(First-fit)

: free 리스트의 첫 노드부터 시작하여, 제일 먼저 발견되는, 요구되는 크기보다 더 큰 빈 공간을 가지는 노드에서 할당해 주고 탐색을 마치는 방법. 이때 free에서 해당 노드에 대한 크기 조정과 used에서의 새 노드 추가가 필요하다.

- 시간적 부담小 (free 리스트에 대한 탐색을 중간에서 끝낼 수 있기에)

- 할당 후 남는 빈 공간이 어중간해 사용되지 못하는 노드가 생길 수 있음.

 

■ 최적적합(Best-fit)

: free 리스트를 끝까지 탐색하여 요구되는 크기보다 더 크되, 그 차이가 제일 작은 노드를 찾아 할당해주는 방법

- 시간적 부담大

- 가장 들어맞는 노드를 찾음으로써 큰 빈 공간을 가지는 노드들을 그대로 유지시킬 수 있음.
(= 할당 후 남는 빈 공간이 어중간한 크기가 되지 않도록 하여 이후의 비교적 큰 크기의 적재 요구에 대비함)

- 결과로 남는 크기가 매우 작아, 빈 공간들은 이후 적재에 거의 활용되지 못함

* 홀(Hole)(=메모리 낭비)

: 빈 공간이기는 하지만, 크기가 아주 작아서 실제로는 할당될 가능성이 희박하고 결과적으로 낭비되는 공간

    ㄴ 외부 단편화(External Fragmentation)의 대표적인 예

 

■ 최악적합(Worst-fit) (최적적합의 단점 역발상)

: free 리스트를 끝까지 탐색하여 요구되는 크기보다 더 크되, 그 차이가 제일 많이 나는 노드를 찾아 할당해주는 방법

- 시간적 부담大

- 할당 후 남는 크기도 비교적 큰 빈 공간이 되도록 하여 이후의 적재 요구에 대비

- 홀의 발생을 억제할 수 있지만, 큰 빈 공간을 확보하기 어려움

 

~> 최적적합과 최악적합은 리스트 끝까지 찾아야 하기에 탐색시간이 오래 걸린다는 단점有

 

=> (효율성) 최초적합 > 최적적합 > 최악적합

* 대부분의 경우 최초가 최적보다 실행 속도가 빠르므로, 최초적합을 사용하면 된다.

ㄴ <최초적합의 문제점>

: 시간이 지날수록 free 리스트의 앞부분부터 매우 작은 노드들이 등장하고 점점 탐색 시간↑.

→ <보완> next-fit 방법

: free 리스트를 순환(Circular) 구조로 한 다음, 할당이 가능한 노드가 선택될 때마다 헤더포인터를 이 노드의 다음으로 옮기게 하는 방법

 

- free 리스트 내 매우 많은 노드들 + 대부분 홀 상태

= 실제로는 빈 공간이 많음에도 대부분 홀이기에 별로 크지 않은 프로세스의 적재 요구조차 수용할 수 없게 됨.

~ 50% 규칙 (50-percent Rule)

 

*   외부 단편화 (+Hole)

: 계속되는 할당과 회수로 인하여 메모리가 단편화되어 큰 프로세스를 적재할 수 없는 현상

해결책 > 병합, 통합

 

<작은 빈 공간을 합쳐 더 큰 빈 공간을 만드는 작업 방식(2)>

■ 인접한(Adjacent) 빈 공간의 병합(Coalescing)

: 빈 공간으로 반납될 때 인접한 빈 공간이 있다면 이들을 합쳐 좀 더 큰 빈 공간을 만들어주는 방식

- 프로세스가 메모리를 반납할 때마다 실행되고, 인접한 공간이 비어 있지 않다면 병합하지 않는다.

 

■ 빈 공간 전부의 통합(Compaction)

: 사용 중인 공간들을 메모리의 한쪽 편으로 밀착시켜 옮기고, 흩어져 있던 빈 공간들을 전부 합쳐 하나의 빈 공간으로 만드는 방식

- 병합과는 달리 사용 중인 공간의 위치 이동이 발생하며,

  이것은 메모리에 있는 모든 프로세스들의 주소 재배치를 의미하므로 상당한 시간을 요구함

- 통합이 진행되는 동안 모든 프로세스들의 실행이 중지되므로 시스템에 있는 자원들 역시 상당 부분 낭비됨

 

고정도 가변도 아닌 버디 시스템

: 메모리 관리에서 고정 분할과 가변 분할을 타협한 절충안으로, 이름하여 버디(Buddy) 메모리 관리라 한다.

 

<버디 시스템>

- 가변 분할과 마찬가지로 최초에 큰 빈 공간 하나로 시작

- 프로세스의 적재 요구가 있을 때 메모리는 요구한 크기보다 크되,

  차이가 가장 작게 나는 2의 승수(Power) 크기로 분할되어 할당되며,

  이때 같은 크기로 분할된 인접 공간을 버디라 한다.

- 분할 내에 프로세스가 차지하고 남는 빈 공간인 내부 단편화가 발생은 하지만,

  고정 분할 때보다는 많이 좋아질 수 있다.

(반납되는 빈 공간은 분할 시 정해졌던 자신의 버디가 빈 공간일 때 병합되어 크기를 2의 배수로 늘려나감)

* 반납되는 빈 공간의 병합이 제대로 이루어지기 위해서는 자신의 버디가 누구인지를 아는 것이 중요하다.

(나와 같은 크기의 빈 공간이 위와 아래에 인접해 있다면, 둘 중 하나만의 나의 버디가 되는 것!)

ㄴ 버디 주소(버디가 되는 공간의 메모리 시작주소)

    if (x mod 2^(k+1) == 0) : 버디 주소 = x+2^k

    else if (x mod 2^(k+1) == 1) : 버디 주소 = x-2^k

 

- 버디 시스템은 고정과 가변의 절충으로서, 그 자체가 메모리 관리 기법으로 사용되기에는 여전히 부족하다.

- 하지만, 버디로 관리하는 아이디어는 병렬 프로그래밍이나 UNIX에서 커널에 할달되는 메모리를 관리할 때 사용하기도 한다.

 

-------------------------------------------------------------------------------------------------------

 

▶ 이번 장 내용: 프로그램의 전부가 연속적으로 할당되는 경우의 메모리 관리 (단순 ~ 다중 프로그래밍 가능)

▶ 다음 장 내용: 프로그램의 일부를 비연속적으로 할당하여 실행하는 내용

(→ 다중 프로그래밍의 정도를 높여 결과적으로 시스템의 성능을 향상시킬 수 있고,

      아무리 큰 프로그램도 수용하여 실행시킬 수 있음.)