Memory Management(메모리 관리) 2 - 연속 할당

물리 메모리 할당

• 메모리는 일반적으로 두 영역으로 나뉘어 사용한다.
  • OS 상주 영역
    • interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역
    • 높은 주소 영역에 있다.

 

 

사용자 프로세스 영역의 할당 방법

Contiguous allocation(연속 할당)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

연속 할당 도식, 출처 - 운영체제(반효경)

외부 조각(external fragmentation) / 외부 단편화

분할(partition)의 크기가 작아 프로그램에 할당되지 못해 낭비되는 메모리 공간

 

내부 조각(Internal fragmentation) / 내부 단편화

프로그램에 할당되었지만 사용되지 않는 메모리 공간

 

 

고정 분할 할당(Fixed partition allocation)

• 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
• 분할의 크기가 모두 동일한 방식, 서로 다른 방식이 존재한다.
• 분할당 하나의 프로그램 적재
• 융통성이 없다.
  • 동시에 메모리에 적재되는 프로그램의 수가 고정됨
  • 최대 수행 가능 프로그램 크기 제한
• 내부 조각(단편화), 외부 조각(단편화) 발생

 

가변 분할 할당(Variable partition allocation)

• 프로그램의 크기를 고려해서 할당
• 분할의 크기, 개수가 동적으로 변함
• 기술적 관리 기법 필요
• 외부 조각(단편화)만 발생

 

Dynamic Storage-Allocation Problem(메모리 배치 문제)

가변 분할 할당(할당(Variable partition allocation) 방식에서 Size가 $n$인 요청을 만족하는 가장 적절한 hole을 찾는 문제

 

Hole

• 가용 메모리 공간
• 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
• 프로세스가 도착하면 수용가능한 hole을 할당
• 운영체제는 다음의 정보를 유지하고 있다.
  1. 할당 공간
  2. 가용 공간(hole)

어떤 프로세스도 점유하지 않는 회색 영역이 바로 Hole이다. 출처 - 운영체제(반효경)

First-fit(최초 적합)

• Size가 $n$ 이상인 것 중 최초로 찾아지는 hole에 할당하는 방식

Best-fit(최적 적합)

• Size가 $n$ 이상인 가장 작은 hole을 찾아서 할당하는 방식
• Hole들의 리스트가 크기 순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 함
• 많은 수의 아주 작은 hole들이 생성됨

Worst-fit(최악 적합)

• 가장 큰 hole에 할당하는 방식
• 역시 모든 리스트를 탐색해야 함
• 상대적으로 아주 큰 hole들이 생성됨

*First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐(실험적 결과)

 

Compaction

• 외부 조각(단편화) 문제를 해결하는 한 가지 방법
• 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 곳으로 몰아 큰 block을 만드는 것
• 매우 비용이 많이 드는 방법이다.
• 최소한의 메모리 이동으로 compaction하는 방법(매우 복잡한 문제)
• compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.

 

 

출처

반효경, "운영체제 2014-1", KOCW, http://www.kocw.net/home/cview.do?cid=3646706b4347ef09