7-4.[os] 다중 프로그래밍 환경에서의 메모리 할당

프로세스들의 크기가 달라 메모리를 어떻게 나누어 사용할 것인지가 가장 큰 문제

메모리 분할 방식

메모리 배치 정책: 메모리를 어떤 크기로 나눌 것인가
가변 분할 방식: 프로세스의 크기에 따라 메모리를 나누는 것이다.
고정 분할 방식: 프로세스의 크기와 상관없이 메모리를 같은 크기로 나누는 것이다

흰색 의자는 빈 의자

가변 분할 방식:
- 손님들이 앉고 싶은 자리에 앉을 수 있다
- 파티션으로 구분되지 않았기 때문에 함께 온 일행이 나란히 앉을 수 있다
- 관리가 복잡함
- ex) B팀의 3명이 식사를 마친 후 손님 4명이 온 경우 -> 4명이 나란히 앉을 수 있는 빈자리가 없기 때문에 10~13번에 앉아 있는 C팀이 옆으로 이동해야 4명을 나란히 앉힐 수 있다. -> 식사 도중 자리를 옮기는 것은 매우 불편한 일
고정 분할 방식:
- 파티션 단위로 배정
- 함께 온 일행이 분산해서 앉는다
- 손님들이 알아서 적당한 파티션에 앉으면 된다

메모리 분할 방식의 구현

가변 분할 방식:

프로세스의 크기에 맞게 메모리가 분할되므로 메모리의 영역이 각각 다르다 (17 ~ 40 KB 크기 다양함)
- = 연속 메모리 할당(contiguous memory allocation): 한 프로세스가 연속된 공간에 배치됨

고정 분할 방식:

프로세스의 크기에 상관없이 메모리가 같은 크기로 나뉘며, 큰 프로세스가 메모리에 올라오면 여러 조각으로 나뉘어 배치된다.
= 비연속 메모리 할당(noncontiguous memory allocation): 한 프로세스가 분산되어 배치됨

가변 분할 방식의 장점: 프로세스를 한 덩어리로 처리하여 하나의 프로세스를 연속된 공간에 배치

가변 분할 방식의 단점 : 가변 분할 방식은 메모리 관리가 복잡하다.

예시) 프로세스 B와 D가 작업을 마쳤다면 각각 18KB와 17KB의 빈 공간이 생긴다. 이때 19KB가 넘 는 프로세스가 메모리에 올라오려고 한다면 어떻게 될까? 빈 공간이 떨어져 있기 때문에 올라올 수 없다. 19KB가 넘는 프로세스를 실행하려면 비어 있는 공간을 하나로 합쳐야 하며, 이 과정에서 프로세스 C의 자리도 옮겨야 한다. 이처럼 가변 분할 방식은 메모리 통합 등의 부가적인 작업이 필요하므로 메모리 관리가 복잡하다.

고정 분할 방식의 장점: 고정 분할 방식에서는 메모리를 일정한 크기로 나누어 관리하기 때문에 메모리 관리가 수월하다. (가변 분할 방식의 메모리 통합 같은 부가적인 작업을 할 필요가 없다.)

고정 분할 방식의 단점: 쓸모없는 공간으로 인해 메모리 낭비가 발생할 수 있다. 즉 일정하게 나누어진 공간보다 작은 프로세스가 올라올 경우 메모리 낭비가 발생한다.

예시) 프로세스 B: 18KB, 프로세스 D: 17KB -> 메모리의 한 조각: 20KB에 배치하면 공간이 남음. 다른 프로세스가 사용할 수 없는 공간-> 메모리가 낭비

가변 분할 방식의 메모리 관리

의자: 메모리
손님: 프로세스

D팀 1 명과 A팀 3명이 식시를 마치고 나감
의자 5개가 비지만 4개가 나란히 비지 않아 H팀 4명에게 배정 못함
B팀과 C팀에게 오른쪽으로 한 자리씩 옮겨달라하면 문제가 해결?
식사 도중 자리를 옮겨달라고 부탁하긴 어려움
대기 중인 I팀 2명을 먼저 빈자리에 배정?
H팀이 오래 기다렸다고 양보 안 해줄 수도 있음
아사 현상: 인원이 많은 팀이 계속 자리를 배정받지 못하는 문제

B팀 2명과 F팀 1명이 식사를 마치고 나감
H팀 4명이 자리를 배정
5번, 8번, 13번, 16번 의자가 비어 있지만 I팀 2명은 대기

단편화

= 조각화
fragmentation
빈 영역이 있어도 서로 떨어져 있으면 프로세스를 배정하지 못해서
작은 조각들이 발생하는 현상

가변 분할 방식과 외부 단편화

프로세스 A, B, C, D, 표를 순서대로 배치
B와 D가 종료 -> 18KB와 17KB의 빈 공간
18KB보다 큰 프로세스가 들어오면 적당한 공간이 없어 메모리를 배정하지 못함

외부 단편화(external fragmentation):

가변 분할 방식에서 발생하는 작은 빈 공간
프로세스의 바깥쪽에 조각이 발생

해결:

메모리 배치 방식(memory placement strategy): 작은 조각이 발생하지 않도록 프로세스를 배치
조각 모음(defragmentation): 조각이 발생했을 때 작은 조각들을 모아서 하나의 큰 덩어리로 만드는 작업

메모리 배치 방식

최초 배치(first fit), 최적 배치(best fit), 최악 배치(worst fit), 버디 시스템(buddy system)

최초 배치:

최초 배치는 단편화를 고려하지 않는 것으로, 프로세스를 메모리의 빈 공간에 배치할 때 메모리에서 적재 가능한 공간을 순서대로 찾다가 첫 번째로 발견한 공간에 프로세스를 배치하는 방법

최적 배치:

최적 배치는 메모리의 빈 공간을 모두 확인한 후 적당한 크기 가운데 가장 작은 공간 에 프로세스를 배치하는 방법이다.
예시) D팀 2명이 7〜9번 의자 중 7번, 8번에 앉는다

최악 배치:

최적 배치와 정반대인 최악 배치는 빈 공간을 모두 확인한 후 가장 큰 공간에 프로세스를 배치하는 방법이다.
예시) D팀 2명이 11~16번의자중 11번, 12번에 앉는다

최초 배치 방식:

빈 공간을 찾아다닐 필요가 없다. 최적 배치 방식:
빈 공간을 모두 확인하는 부가적인 작업이 있지만 딱 맞는 공간을 찾을 경우 단편화가 일어나지 않는다
프로세스를 배치하고 남은 공간이 작아 쓸모없다 최악 배치 방식:
프로세스를 배치하고 남은 공간이 크기 때문에 쓸모있다
빈 공간의 크기가 클 때는 효과적이지만 빈 공간의 크기가 점점 줄어들면 최적 배치처 럼 작은 조각을 만들어냄

조각 모음

서로 떨어져 있는 여러 개의 빈 공간을 합치는 작업
단편화가 발생하면 이미 배치된 프로세스를 옆으로 옮겨 빈 공간들을 하나의 큰 덩어리로 만듦

프로세스를 중지시키고, 이동하고, 주소를 바꾸고, 다시 시작하는 작업
-> 많은 시간이 걸림
결론: 가변 분할 방식은 외부 단편화로 인해 조각 모음 같은 부가적인 작업이 필요하므로 메모리 관리가 복잡함

고정 분할 방식의 메모리 관리

페이징: 가상 메모리 시스템에서는 고정 분할 방식

프로세스 배치와 외부 단편화

다른 팀과 파티션을 공유하지 못하기 때문에 빈자리에 다른 팀이 앉을 수 없음 -> 대기자 8명
A팀 3명과 D 팀 1명이 식사를 마치고 나감
G 팀 2명과 H팀 4명이 자리를 배정

40KB -> 20KB & 20KB
30KB -> 20KB & 10KB(메모리에 공간없어서 스왑 영역으로 옮겨짐)

내부 단편화

internal fragmentation
일정한 크기로 나뉜 파티션 안쪽으로 작은 조각이 발생
일정하게 나뉜 메모리의 크기보다 작은 프로세스가 배치될 경우 낭비되는 공간이 생긴다
가변 분할 방식의 외부 단편화는 조각 모음으로 조정함
고정 분할 방식에서는 내부 단편화를 해결하기 위해 조각 모음을 할 수 없고 남는 공간을 다른 프로세스에 배정할 수도 없다
동일하게 분할되는 공간의 크기를 조절 -> 내부 단편화를 최소화
예시)
- 의자 1개씩 파티션으로 나눔 -> 내부 단편화가 발생하지 않지만 각 팀이 여 러 개로 분할되어 관리하기 어려움
- 의자 4개씩 파티션으로 나눔 -> 대부분의 손님이 같은 파티션에 앉을 수 있으나 내부 단편화가 급격하게 늘어나 낭비되는 공간이 생김

가변 분할 방식과 고정 분할 방식의 비교

버디시스템

가변 분할 방식의 단점인 외부 단편화를 완화하는 방법
버디 시스템은 가변 분할 방식이지만 고정 분할 방식과 유사한 점이 있다

버디 시스템의 작동 방식

프로세스의 크기에 맞게 메모리를 1/2로 잘라나가고 프로세스를 메모리에 배치한다.
나뉜 메모리의 각 구역에는 프로세스가 1개 만들어간다.
프로세스가 종료되면 주변의 빈 조각과 합쳐서 하나의 큰 덩어리를 만든다.

버디 시스템은 메모리를 분할할 때는 1/2로 나누고，프로세스가 종료될 때마다 주변을 살펴서 빈 구역을 하나로 합친다

손님이 A팀 3명, B팀 2명, C팀 2명일 때의 자리 배정
의자 16개를 1/2로 나누고 그 중 오른쪽을 다시 1/2로 나누어 A팀 3명을 9~11 번 의자에 앉힌다. - 맨 오른쪽의 의자 4개를 1/2로 나누어 B팀 2명을 13〜 14번 의자에 앉히고, 맨 오른쪽에 남은 의자 2개에는 C팀 2명을 앉힌다.

D팀 1명이 추가됨
왼쪽의 의자 8개를 1/2로 나누어 7번 의자를 앉힌다
E팀 4명, F팀 1명, G팀 2명, H팀 4명, I팀 2명이 추가됨

A팀 3명과 D팀 1명이 식사를 마치고 나감
버디 시스템에서는 9~12번 의자에 H팀 4명을 앉힐 수 있음
F팀 1 명이 나가면 7번과 8번 의자가 통합되어 하나의 구역이 됨
I팀 2명 앉음

버디 시스템의 특징

가변 분할 방식처럼 메모리가 프로세스 크기대로 나뉨
고정 분할 방식처럼 하나의 구역에 다른 프로세스가 들어갈 수 없음 (내부 단편화 12번 의자)
가변 분할 방식에서는 작은 조각이 큰 조각 사이사이에 있어 조각을 모으려면 큰 덩어리를 옮겨야 한다. 그러나 버디 시스템에서는 비슷한 크기의 조각이 서로 모여 있기 때문에 작은 조각을 통합하여 큰 조각을 만들기가 쉽다.
조각 모음을 하지 않아도 간단히 큰 덩어리를 만들 수 있다.
효율적인 공간 관리 측면에서 보면 고정 분할 방식과 버디 시스템은 비슷함
공간을 1/2로 나누어가면서 메모리를 배분하는 버디 시스템이 고정 분할 방식보다 복잡해서 고정 분할을 더 많이 씀