메모리 배치 알고리즘

프로세스가 메인 메모리에 적재되기 전, 어떻게 mapping할 것인지 정하는 알고리즘
First-fit, Worst-fit, Best-fit이 있다.

First-fit

메모리의 처음부터 검사해서 크기가 충분한 첫번째 메모리를 준다

def first_fit(_memory,_size):
	for idx in range(len(_memory) - _size +1):
    	if all(_memory[i]==0 for i in range(idx,idx+_size)):
        	return idx
    return -1

Worst-fit

처음부터 끝까지 메모리 공간을 탐색하여 연속적으로 가장 많이 남은 공간의 메모리를 준다

Best-fit

처음부터 끝까지 메모리 공간을 탐색하여 요청된 크기와 가장 근접한 크기의 메모리를 준다

def best_fit(_memory,_size):
	best_index=-1
    min_size=float('inf') #최댓값으로 초기화
    
    for idx in range(len(_memory) - _size +1): #처음부터 끝까지 탐색
    	if all(_memory[i] =0 for i in rnage(idx,idx+_size)):
        #메모리가 들어갈 공간이 연속적으로 비었다면
        	current_size=0 #현재 적재된 사이즈는 0
            while idx+current_size<len(_memory) and _memory[idx+current_size]==0:
            #
            current_size+=1
            
            if current_size<min_size:
            	min_size = current_size
                best_index = idx
                
    return best_index

First-fit과 Best-fit은 성능이 비슷한데, 왜 First-fit이 주로 선호되는가?

First-fit은 처음부터 끝까지 메모리를 탐색할 필요가 없다. 즉, 성능이 비슷하다면 탐색 시간이 덜 걸리는 first fit이 선호된다. 구현도 쉽다!

Worst-fit은 왜 쓰는가?

성능은 최악이라는데, 왜 쓸까?
그 이유는 '다른 방법에 비해 남는 공간이 넉넉해져서'다.
즉, 가장 넓은 공간에 메모리를 할당하는 것이다 보니, 메모리를 할당해도 상대적으로 메모리가 널널하다.
즉, 연속적으로 비어있는 적당한 사이즈의 메모리들이 다른 방법에 비해 많아지는 기법이므로 사용한다.