메모리 관리 Next-fit (다음적합기법)

OS 시간에 메모리 관리에 대하여 공부 하던 중에, 스케줄링 알고리즘 처럼 메모리도 효율적으로 관리할 수 있다는 얘기를 듣고 Next-fit (다음적합기법) 이라는 알고리즘에 대하여 공부하게 되었다.
공부하는 김에 정리하면서 하는 것이 좋을 거 같아 이렇게 Velog에 남긴다.

아마 많은 분들이 Best-fit, Worst-fit 등등을 알겠지만 오늘 내가 해볼 알고리즘은 익숙하지 않은 Next-fit을 소개해보려고 한다.

메모리 관리 기법

메인 메모리는 일반적으로 운영체제를 위한 영역(상주 모니터, 커널)과 함께 실행 중인 프로그램을 위한 영역으로 구분된다. 물론 다중 프로그래밍 시스템에의 사용자 영역을 여러 프로세스가 상주할 수 있도록 세분화 해야 한다. 이러한 세분화 작업은 운영체제에 의해 동적으로 이루어지는데 이 과정을 메모리 관리하고 한다. 컴퓨터의 핵심자원인 메모리의 효과적인 관리를 위한 메모리 할당 기법은 대표적으로는 3가지가 있는데 이는 First-fit , Worst-fit, Best-fit이 있다.

대표적인 메모리 할당 알고리즘

First-fit(최초 적합) : 최초로 할당받을 수 있는 크기의 공간에 무조건 할당된다.(위 또는 아래 부터)
Best-fit (최적 적합): 크기가 가장 근접한 공간에 할당된다.
Worst-fit (최악 적합) : 크기가 가장 많이 차이가 나는 공간에 할당된다.

근데 Next-fit은 뭐야?

Next-fit은 나도 이를 공부하기 전까지는 처음 들어보는 알고리즘 이였다. 현재 구글링을 해도 Next-fit에 관한 정보들은 많이 나와있지 않아 공부하는데 어려움을 느꼈다. 하지만 Next-fit은 Best-fit과 별 다를 것 없는 알고리즘이다.
하지만 차별점이 있다. 지금부터 알아보자.

왼쪽에 있는 Before Allocation을 보면 Allocation은 할당 , FreeBlock은 빈공간(즉, 들어갈 수 있는 자리),Possible New Allocation은 새로운 메모리가 들어오는 것 이다.

Next-fit은 가장 마지막에 들어온 공간에서 가장 적합한 곳을 찾아서 가는 것이다.

저곳의 예시처럼 가장 마지막에 들어온 Best-fit에 가장 근접하고 메모리 사이즈를 맞는 곳을 찾아가는 것이다.
다른 조건들과는 다르게 이번은 Next-fit은 2가지 조건이 있다.
바로 위치성과 적합성을 두가지 만족하는 것을 선택하는 것이다.
Best-fit과의 차별점은 Best-fit은 조건에서는 위치성이 가까운 순이라고 정확하게 명시가 되어 있다.

그래서 무슨 알고리즘이 가장 효율적?

First-fit 알고리즘이 가장 간단하며 최적이고 빠르다.
Next-fit 알고리즘은 First-fit 알고리즘 보다는 효율성이 떨어진다.
하지만 마지막 부분에 있는 Block에 프로세스를 Load하는 경향이 있다.
보통 메모리 공간에 끝에 있는 가장 큰 메모리를 짧은 시간내에 쪼개야 하기 때문에 효율이 더 드는 것이다.

참고자료

https://truemind5.blogspot.com/2017/05/14-1.html
https://cenenh.tistory.com/66