OS_Contiguous Allocation(Fragmentation)

메모리 주소는 보통 두 가지 영역으로 나뉜다:

운영체제가 사용하는 영역 (보통 interrupt 벡터와 함께 더 낮은 주소를 갖게 된다), 그리고 User Process들이 사용하는 영역이다.

Interrupt 벡터는 interrupt가 발생했을 때, 그것을 처리하는 루틴을 저장하고 있다.

#Interrupt

 

'Contiguous'는 '연속적인'이라는 의미를 지닌다. 즉, 연속된 메모리 영역을 프로세스에 할당하는 것이 'Contiguous Allocation'이다. 

직관적으로는, 커다란 배열을 머릿속에 그려보면 될 것 같다.

Contiguous Allocation에는 크게 두 가지 방법이 있다.

#Partition Scheme and Fragmentation

1. Fixed Partition Scheme
   : 고정된 크기로 메모리를 나누어서 할당하는 방법
   >> 할당된 영역의 개수만큼만 멀티프로그래밍이 가능하다
   >> Internal Fragmentation(내부 단편화)가 발생한다. 내부 단편화는 고정된 크기로  할당된 영역이 프로세스가 필요한 공간보다 커서 메모리가 낭비되는 현상을 의미한다.
2. Variable Partition Scheme
   : 필요에 따라서 메모리를 나누어 할당한다.
   >> External Fragmentation(외부 단편화)가 발생한다. 외부 단편화는 여러 프로세스가 사용중인 메모리 사이사이에 있는 사용 가능한 공간의 총합은 충분하지만, 각각이 쪼개진 상태로 존재하여 할당이 불가능한 현상을 의미한다.

사용중인 두 메모리 공간 사이에 존재하는 메모리 공간을 'hole'이라고 표현한다. Hole에 메모리를 할당하는 방법으로는 다음과 같이 대표적으로 세 가지가 있다. 리스트 데이터구조를 통해 holes를 관리한다고 가정한다.

• First-fit
  : 공간이 충분한 hole을 찾은 즉시 할당.
• Best-fit
  : 리스트가 사이즈에 따라서 정렬된 것이 아니라면, 처음부터 끝까지 전부 search. 그 후, 남는 공간이 가장 작은 hole에 할당.
• Worst-fit
  : 리스트가 사이즈에 따라서 정렬된 것이 아니라면, 처음부터 끝까지 전부 search. 그 후, 남는 공간이 가장 큰 hole에 할당. (이런짓을 왜하지?)

결론은, PROBLEM: FRAGMENTATION

#SOLUTION: COMPACTION

External Fragmentation이 발생했을 때, 그에 대한 해결책으로 제시되는 방법이다.

간단히 말해서, 사용 가능한 메모리를 한 곳으로 모아서 재배치 시키는 것.

(단순한 예시로는, 모든 프로세스를 한 쪽 끝으로 이동시키고, 모든 hole을 다른 한 쪽 끝으로 이동시키는 알고리즘이 있다)

수행 가능 조건은 두 가지가 있다.

• Relocation이 Dynamic한 경우에만 가능
• Relocation이 Execution Time에 발생하는 경우에만 가능

Compaction을 솔루션으로 가장 먼저 소개했다. 왜냐면 간단하고 상대적으로 별로 안중요해서.

 

가장 중요하고, 가장 널리 쓰이는 해결책 중 하나인 'Paging'에 대한 개념은 따로 게시글을 정리해보겠다.

 

*오개념 지적 대환영*

#키워드 : (게시글이 있는 경우) 링크를 참고하시거나, 검색하면서 읽어주세요. 이해에 꼭 필요한 개념입니다.

 

해당 게시글은 Operating Systems: Three Easy Pieces(#혜성책), Operating System Concepts (#공룡책), 그리고 이 도서를 기반으로 한 학부 수업 자료를 참고하여 작성하였습니다.