메모리 분할

메모리 관리 ⇒ 처리기에 의해 실행될 프로세스를 주기억장치로 가져오는 것
가상 메모리 기법을 사용하는 세그먼테이션이나 페이징과는 다르게 가상메모리를 사용하지 않는 기법들

고정분할

운영체제에서 주기억장치를 고정된 경계를 가지는 메모리 영역으로 구분

분할 크기

균등분할

한 프로세스의 크기가 분할의 크기보다 작거나 같음
문제점
- 프로그램의 파티션보다 클 수 있음 ⇒ 오버레이의 사용 필요성
- 주기억장치 이용이 매우 비효율적
- 내부단편화 ⇒ 비균등 분할을 통해 영향 줄이기

내부단편화(internal fragmentation) 적재되는 데이터가 파티션보다 작아 파티션 내부 공간의 낭비가 발생하는 현상

비균등 분할

내부단편화의 영향을 줄일 수 있음

고정 분할에서의 배치 알고리즘

균등 분할의 경우

사용 가능 파티션이 존재하기만 하면 프로세스는 해당 파티션으로 적재가 가능 ⇒ 모든 파티션들은 같은 크기이므로 어떤 파티션을 사용해도 차이 X
준비 상태에 있지 않은 프로세스가 모든 파티션을 차지하고 있다면 새로운 프로세스를 위한 공간을 만들기 위해 프로세스들 중 하나 스왑 아웃

비균등 분할의 경우

각 프로세스의 용량에 맞는 파티션을 할당해주는 방법(파티션 당 하나의 프로세스 큐)
- 각 파티션에 할당 예정인 스왑아웃된 프로세스들을 유지하는 스케줄링 큐 필요
- 장점 : 프로세스들이 항상 메모리의 낭비(내부 단편화)를 최소화시키는 파티션에 적재
- 단점: 해당 메모리의 크기에 맞는 프로세스가 없을 경우 쓰이지 않은 채로 방치되는 파티션 발생
단일 큐 사용
- 프로세스를 메모리에 적재할 시점에 사용가능한 파티션 중에서 프로세스를 적재할 수 있는 가장 작은 크기의 파티션이 선택됨
- 모든 파티션이 사용중일 경우 스와핑(스왑아웃)

비균등 분할의 단점
- 정해진 파티션 수에 의해 프로세스의 개수가 제한됨
- 파티션 크기가 고정되므로 크기가 작은 작업들은 공간을 비효율적으로 사용

동적 분할

- 고정분할 기법의 문제 해결을 위한 방법 - 파티션의 크기와 개수가 가변적 - 한 프로세스가 주기억장치로 적재될 때 정확히 요구된 크기만큼의 메모리만 할당 - 단점 - 외부 단편화: **'구멍'** 이 존재하여 사이사이 사용할 수 있는 메모리가 있음에도 불구하고 이어져있지 않아 메모리 단편화의 심화와 메모리 이용률 감소 => **메모리 집약(Memory Compaction)** 을 통해 해소.

메모리 집약(Memory Compaction) 프로세스가 사용하는 파티션을 이동시켜 각 파티션이 연속적이 되도록 인접하게 만들고 메모리의 모든 빈 공간이 하나의 블록이 되도록 만듦

배치 알고리즘

최초적합 <= 순환적합 <= 최적적합

최적적합(best-fit)
- 요청된 크기와 가장 근접한 크기의 메모리 선택
최초적합(first-fit)
- 메모리의 처음부터 검사해서 크기가 충분한 첫 번째 사용 가능한 메모리 블록 선택
순환적합(next-fit)
- 가장 최근에 배치되었던 메모리의 위치에서부터 검사를 시작해 크기가 충분한 다음 위치의 사용 가능한 메모리 블록을 선택

교체 알고리즘

모든 프로세스가 대기 상태이고 메모리 집약 후에도 추가의 프로세스를 생성하기 위한 충분한 메모리가 없을 경우 ⇒ 주기억장치에 있는 프로세스 중 하나를 스왑아웃시켜 준비상태의 새로운 프로세스나 준비-일시정지 상태의 프로세스가 들어올 공간을 만듦

버디(Buddy) 시스템

고정 및 동적 분할 기법의 단점
- 활성 프로세스 수 제한
- 프로세스와 파티션의 크기 차이가 크면 공간을 비효율적으로 사용 ⇒ 절충안적인 버디(Buddy) 시스템의 등장
메모리 블록은 $2^{k}, L \leq K \leq U$
$2^{L}$ = 할당된 가장 작은 크기의 블록
$2^{U}$ = 할당된 가장 큰 크기의 블록, 보통 할당 가능한 전체 메모리의 크기와 같음
요청된 크기 s가
- $2^{U - 1} < s \leq 2^{U - 1}$ 이라면 전체 블록 할당. 그렇지 않은 경우 $2^{U - 1}$ 크기의 두 개의 버디로 분할
- $2^{U - 2} < s \leq 2^{U - 1}$ 이라면 두 버디 중 하나를 할당. 그렇지 않은 경우 이 버디 중 하나를 다시 두 개로 나눔
- s 이상의 크기를 가진 가장 작은 버디가 만들어져 해당 요청에 할당이 이루어질 때까지 과정 반복
$2^{i}$ 인 구멍들의 리스트 유지
수정된 형태의 버디 시스템이 UNIX 커널 메모리 할당 방법으로 사용

위 그림과 같이 반씩 계속 메모리를 분할하고 적당한 크기까지 분할되면 해당 메모리에 할당하는 방식
트리로 표현하면 이런 식으로 이진트리가 만들어진다.
해당 트리는 B가 위의 예제에서 B가 해제되고 난 후의 상태인데, 보면 리프노드가 적어도 하나는 할당된 것을 볼 수 있다. 할당되지 않았을 경우 더 큰 블록으로 합쳐진다.

void get_hole(int i)
{
	if (i == (U+1))
		<실패>;
	if ( <i_list가 비었음> )
	{
		get_hole(i+1);
		<구멍을 두 개의 버디로 나눈다>
		<버디를 i_list에 포함시킨다>
	}
	<i_list의 첫 번쨰 구멍을 선택한다>
}

재배치

프로세스가 Swap in일 때 같은 주소에 배치하는 경우
- 고정 분할 기법 - 파티션 별 하나의 프로세스 큐 비균등 분할
  - 프로세스가 적재되어질 때 코드 안에 있던 메모리 참조를 위한 상대적인 주소들은 적재된 프로세스의 시작 주소를 기준으로 결정되는 주기억장치 내의 절대 주소로 바뀜
프로세스가 Swap in일 때 다른 주소에 배치되는 경우
- 균등분할
- 단일 큐를 쓰는 비균등 분할
- 동적 분할
프로세스가 Swap out되었다가 다시 Swap in하는 경우 각각 다른 위치에 적재될 수 있어 주소를 유형별로 구분
- 논리주소
  - 현재 데이터가 적재된 메모리와는 독립적인 메모리 위치에 대한 참조
- 상대주소
  - 논리 주소의 특별한 예
  - 주로 처리기의 한 레지스터 값으로부터 상대적인 위치를 의미하는 주소
- 물리주소
  - 주기억장치 내에서의 실제 위치
프로세스는 베이스 레지스터와 경계 레지스터에 의해 격리
- 베이스 레지스터
  - 프로세스가 실행 상태가 되면 프로세서의 특정 레지스터에 프로그램이 적재되어 있는 주기억장치의 시작주소가 적재되는 레지스터
- 경계 레지스터
  - 프로그램의 마지막 위치를 가리키는 레지스터
- 프로세스를 실행하는 동안 상대주소 사용 → 상대주소에 베이스 레지스터 값이 더해져 절대 주소로 변환 → 절대 주소가 경계 레지스터 값과 비교 → 주소가 경계범위 안에 있다면 명령 실행/그렇지 않다면 운영체제로 인터럽트 발생
- 다른 프로세스의 원하지 않은 접근으로부터 안전하게 보호 가능

🐢꾸준함의 미학

탐색기

운영체제_메모리 관리_메모리 분할(memory partitioning)