[OS/운영체제] 메인 메모리 (Main Memory) - (2)

Swapping

메인 메모리와 Backing Store 간 프로세스 교체

프로세스는 실행되기 위해선 반드시 메모리에 존재해야 한다. 하지만 프로세스는 일시적으로 메모리 밖의 Backing Store의 프로세스와 교체될 수 있다.

멀티프로그래밍 환경에서 RR CPU 스케줄링 알고리즘을 사용하는 상황을 예시로 들어보자.

만약 한 Time Quantum이 종료된다면, 종료된 프로세스와 다음 Time Quantum동안 실행될 프로세스가 교체될 것이다. 다음으로 실행될 프로세스를 메모리에 올리는 것이다.

이상적으로는 CPU 스케줄러가 CPU 스케줄을 변경할 때 일부 프로세스가 메모리에 저장되어 실행 준비가 될 정도로 프로세스를 빠르게 교체할 수 있다. (단, Time Quantum은 Swapping 간에 적절한 양의 컴퓨팅이 이루어질 수 있을 만큼 충분히 커야 한다.)

다양한 유형의 Swapping은 Priority 기반 스케줄링 알고리즘에 사용된다. 높은 우선도를 가진 프로세스가 도착한다면, 메모리 관리자는 비교적 낮은 우선도의 프로세스를 꺼내고(Swap out), 높은 우선도의 프로세스를 적재, 실행하게 된다. 높은 우선도의 프로세스가 실행을 마치면 낮은 우선도의 프로세스가 다시 실행을 계속한다. (Swapped in)

(Swap in, Swap out을 Roll in, Roll out이라고도 한다.)

 

메모리 할당 (Memory Allocation)

메모리를 할당하는 가장 단순한 방법은 메모리를 고정된 크기의 파티션(Partitions)으로 나누는 것이다. 각 파티션은 단 하나의 프로세스를 포함한다. 따라서, 멀티프로그래밍의 정도는 파티션의 개수에 따라 정해진다.

이러한 다중 파티션에서는 한 파티션이 free 상태라면 프로세스가 input queue에서 선택되어 이 free 파티션에 적재된다. 프로세스가 종료되면 파티션은 다시 다른 프로세스들이 사용 가능한 상태가 된다.

가변 파티션(Variable-Partition)에서 운영체제는 메모리의 어떤 부분이 사용 가능하고 어떤 부분이 이미 사용 중인지에 대한 테이블을 유지한다. 초기에는 모든 메모리가 사용자 프로세스에 대해 사용 가능하고, 이는 사용 가능한 하나의 큰 메모리 블록으로 간주된다. (이를 Hole이라 한다.) 결국 메모리는 여러 크기의 hole을 포함하는 것과 같다.

(즉, Hole은 free memory의 한 block이다.)

운영체제는 프로세스들의 메모리 요구량에 따라 어떤 프로세스가 어떤 사용가능한 메모리 공간에 할당될지 결정해야 한다. 만약 프로세스가 할당된다면, CPU 사용에 대해 다른 프로세스와 경쟁할 수 있을 것이다.

프로세스가 메모리를 요구할 때, 시스템은 그 프로세스에게 충분한 크기의 hole을 제공할 수 있도록 hole들을 검색한다. 만약 hole이 너무 크다면 hole을 두 부분으로 나누어 한 부분을 프로세스에 할당하고, 나머지 부분을 다시 사용 가능한 hole로 둔다. 이 때 만약 새 hole이 다른 hole과 인접해 있다면, 두 hole은 합쳐져 하나의 더 큰 hole이 된다.

시스템은 메모리를 기다리는 모든 프로세스들의 요구를 만족시킬 수 있는지 고려해야 할 것이다. 이 과정은 크기가 n인 요청을 사용 가능한 hole의 목록을 통해 어떻게 만족시킬지에 대한 Dynamic Storage Allocation Problem과도 같다.

최초 적합(First Fit) : 요구되는 메모리 크기보다 충분히 큰, 가장 처음 만나는 hole을 할당한다.

최적 적합(Best Fit) : 요구되는 메모리 크기보다 큰 hole들 중 가장 작은 크기의 hole을 할당한다.

최악 적합(Worst Fit) : 가장 큰 hole을 할당한다.

 

단편화 (Fragmentation)

외부 단편화

최초, 최적 적합 할당은 외부 단편화(External Fragmentation) 문제가 존재한다. 외부 단편화는 모두 합했을 때 요청을 만족할 크기는 갖지만, 연속되지 않은 메모리 공간을 말한다. 즉 다수의 작은 hole과도 같다.

전체 메모리 크기와 프로세스들의 평균 크기에 따라 단편화는 작은 문제가 될 수도 있고, 중대한 문제가 될 수도 있다. 통계적으로 최초 적합은 최적화를 거치고도 할당된 N개의 블록에 대해 0.5N 만큼의 단편화가 발생한다.

(이는 50-percent rule이라고 알려져 있다.)

외부 단편화를 해결하는 방법 중 하나로는 Compaction이 있다. 할당된 메모리를 재배치하여 작은 크기의 hole들을 한 데 모아 보다 큰 hole을 만드는 것이 목적이다. 하지만 메모리의 재배치가 실행 시간에 동적으로 동작할 경우에만 가능한 제한적인 방법이다.

다른 가능한 방법으로는 프로세스들의 논리적 주소공간을 비연속적(Noncontiguous)이 되도록 하여 사용 가능한 물리적 메모리 어디든 할당될 수 있도록 하는 것이다. 이를 위해 Paging, Segmentation 기법이 사용된다.

(다음 게시물에서 설명한다.)

 

내부 단편화

단편화는 외부적 뿐만 아니라 내부적으로도 발생할 수 있다. 18,464 바이트의 hole에 18,462 바이트만큼의 메모리를 요청하는 프로세스를 할당했을 때를 생각해보자. 남은 2바이트 크기의 hole은 테이블을 통해 추적되는(위에서 hole들은 사용 가능 여부를 테이블을 통해 유지한다고 하였다.) 오버헤드가 hole 자체보다 더 커지게 될 것이다.

 

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.