[운영체제] 메모리의 연속 할당 방식

연속할당

연속할당이란?

물리적 메모리의 한곳에 연속적으로 적재

고정 분할 방식

의미

물리적 메모리를 정해진 개수만큼의 영구적인 분할로 나누어두고 각 분할에 하나의 프로세스를 적재하는 방식

특징

• 동시에 메모리에 올릴 수 있는 프로그램의 수 고정.
• 하나의 분할 공간에는 하나의 프로세스만 들어갈 수 있으므로 다른 프로그램 들어갈 수 없다 → 메모리 낭비

문제점

1. 외부 단편화: 프로그램 크기보다 분할의 크기가 작은 경우 해당 분할이 비어있는 경우에도 프로그램 적재 못함
2. 내부 단편화: 프로그램 크기보다 분할의 크기가 큰 경우 해당 분할에 프로그램을 적재하고 남는 현상

가변 분할 방식

의미

메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식
→ 프로그램의 크기를 고려해서 메모리를 할당하고 이를 기술적으로 관리할 수 있는 기법이 필요

특징

• 프로세스에 맞게 메모리 공간을 사용하기 때문에 내부 조각 문제 발생 X.

문제점

1. 사용중인 프로세스가 종료되어 메모리에 새로운 프로세스를 올릴 메모리 공간이 충분하지 않을 경우 외부 조각 문제가 발생

2. 가변분할 방식은 어디 메모리 공간에 프로세스를 올려야 할지 결정해야하는 문제 존재! → 해결책: First-fit, Best-fit, Worst-fit

해결책

• 외부 조각 문제 해결책: 컴팩션, 집약
  • compaction (압축):  물리적 메모리 중에서 사용중인 메모리 공간을 한쪽으로 몰고 가용 공간을 확보하는 방법. 메모리를 효율적으로 사용할 수 있는 측면에서는 좋은 선택이지만 수행중인 프로세스의 메모리 주소 공간을 이동시켜야 하므로 비용이 매우 많이 든다. 
  • coalescing (집약): 남는 메모리들 하나의 큰 블럭으로 연결. 현재 위치의 메모리에서 단편화 메모리들 끼리 인접해 있는 경우 이를 하나의 큰 메모리로 만들어준다.
  • coalescing과 compaction의 차이는 메모리의 재배치가 일어나는가 아닌가에 의해 차이가 난다.
  • 위 두 가지 방법 모두 단편화 문제가 있었다. → 버디 시스템이 제안
    • 버디 시스템은 큰 버퍼들을 반복적으로 이등분하여 작은 버퍼들을 만들고, 가능할 때마다 인접한 빈 버퍼들을 합치는 과정을 반복한다. 나뉜 버퍼들 각각을 서로의 버디라고 칭한다.
    • 할당 요청이 들어오면, 메모리를 요청한 메모리보다 크거나 같아질때까지 이등분하기를 반복한다.
    • 예를 들면, 전체 메모리가 64KB고 들어온 요청은 8KB라면, 64KB를 32KB 두개로, 32KB를 16KB 두개로, 16KB를 8KB 두개로 쪼개어 알맞은 크기로 생성된 8KB의 버디에 들어온 요청을 할당한다.

압축

집약

• 동적 메모리 할당 문제 해결책
  • FIRST - FIT
    • 크기가 N이상인 가용 공간 중 가장 먼저 찾아지는 곳에 프로그램 할당. 가용 공간이 프로그램 크기보다 작으면 건너 뛰고, 그렇지 않은 공간이 최초로 발견되면 그 공간에 프로그램 올림. → 시간적 측면에서 효율적
  • BEST - FIT
    • 크기가 n이상인 가장 작은 가용공간 찾아 새로운 프로그램 할당. → 공간적 측면에서 효율적
  • WORST - FIT
    • 가용 공간 중에서 가장 크기가 큰 곳에 새로운 프로그램 할당. 모든 가용 공간 리스트 탐색해야하는 오버헤드 발생 가능.
  • NEXT - FIT
    • first Fit 에서 할당된 후 다음 빈홀부터 다시 검색.

FIRST FIT

BEST FIT

WORST FIT

질문

• worst-fit 은 언제 사용할 수 있을까요?
•  Fit 을 한 다음 남는 부분은 분할해서 나중에 할당하는데 다시 사용합니다.first fit 이나 best fit 은 남는 부분이 최소 할당 크기보다 작아서 사용할 수 없는 부분으로 남게될 가능성이 상대적으로 높은데, Worst fit은 그런 부분에서 유리하죠. 그래서 아예 딱 들어맞는 크기로 Best fit 이 되지 않으면 Worst fit 으로 가는 조합된 방법을 사용할 수도 있을 겁니다. 단 Best 든 Worst 든 모두 탐색이 필요하다는 단점이 생기죠.
• 성능이 가장 좋은 알고리즘은 무엇일까요?
• first-fit. best-fit은 메모리 효율에 그렇게 큰 차이가 없다.
  
  best-fit은 비교를 다해봐야하므로 알고리즘 적으로는 first-fit 성능이 더 우수하다.

참고

https://baebalja.tistory.com/416

[운영체제 11편] 메모리 할당 I(연속할당 방식)

https://matdongsane.tistory.com/29

메모리와, 연속 메모리 할당(contiguous memory allocation)

https://zangzangs.tistory.com/133

[OS] 메모리 연속할당 - 고정분할 방식과 가변분할 방식

https://jhnyang.tistory.com/284

[운영체제 OS] first-fit 최초적합, best-fit 최적적합, worst-fit 최악적합에 대해 알아보자!