[OS] 메모리 계층구조, 단편화, First fit, Best fit, Worst fit

 

 

 

 

 

 

메모리에 대해서부터 알아봅시다

 

비유를 먼저 해볼까요?

음식 창고가 있습니다. 여러 종류의 음식들이 저장되어 있어요. 근데 집에서 너무 멀어서 매번 가져올 때마다 너무 힘들고 시간도 오래 걸립니다. 그래서 중간 정도 거리에 조금 작은 간이 창고를 하나 더 만들었습니다. 다양한 음식이 있지만 요즘 봄이라 봄철음식을 주로 해먹어서 관련된 것들 위주로 저장해 놓았습니다. 근데 요즘 봄철음식 중에서도 냉이국이랑 달래무침에 빠져서 거의 매일 먹습니다. 그러다보니 매번 이것들을 가지러 중간 창고에 가기가 귀찮아졌습니다. 그래서 집 안 냉장고에 냉이와 달래만 저장해 놓고 바로바로 꺼내먹게 되었습니다.

 

 

이 내용을 메모리로 바꿔서 얘기하면 다음과 같습니다.

저장 공간이 가장 큰 하드디스크(HDD)(또는 SSD, 보조기억장치) 가 있습니다. 여러 종류의 프로그램들이 저장되어 있어요. 그런데 CPU에서 멀고 데이터를 가져오는 속도가 느리고다보니 시간도 오래 걸립니다. 그래서 RAM(메인 메모리)을 하나 만들었습니다. 여러 프로그램이 있지만 요즘은 문서 정리 중이라 관련 프로그램(프로세스)들이 메인메모리에서 동작하고 있습니다. 특히 엑셀과 PPT는 매일 씁니다. 그래서 캐시 메모리에 엑샐과 PPT의 자주 쓰는 기능들을 저장해 놓았습니다.

 

 

메모리 계층구조로 보면 다음과 같습니다.

 

 

여기서 캐시메모리는 잠시 접어두고 메인메모리(RAM)에 대해서 한번 살펴볼까요?

우리가 프로그램을 사용하려면 RAM에 해당 프로그램이 프로세스로 동작하고 있어야 합니다. 위에서 말했던 엑셀을 예로 들면 CPU가 'RAM에 엑셀 실행되고 있니?' 하고 물어보고 있으면 바로 쓰고 없으면 보조기억장치에서 가져와서 실행시킵니다. 

 

 

 

이처럼 프로그램을 가져와서 메모리에 적재하고 다쓴건 내리고 다시 적재하고를 반복하다 보면 발생하는 문제가 있는데요, 그것을 단편화라고 합니다. 단편화는 두가지가 있습니다.

 

1. 내부 단편화 (Internal Fragmentation)

프로세스를 적재하고 보니 남은 공간이 너무 작아서 쓸 수 없어 메모리가 낭비되는 것을 내부 단편화라고 합니다.

 

2. 외부 단편화 (External Fragmentation)

메모리 전체로 봤을 때는 남은 공간이 충분한데 분할된 공간이라서 프로세스를 할당하지 못하는 것을 외부 단편화라고 합니다.

 

 

external fragmentation의 해결 방안
1) storage compaction(압축) : 주기적으로 삭제 공간을 회수하여 메모리 공간들을정리하는 방식 입니다. 비용이 많 이 들어 자주 쓸 수 없는 것이 단점입니다. 주로 정해진 주기에 따라서 실행 됩니다.
2) Coalescing(통합) : 단편화로 인해 쪼개진 공간들 중 인접한 공간들을 합쳐서 더 크게 만드는 방식입니다.
3) placement strategy (배치 전략) : 배치를 잘하는 방식을 사용하여 단편화의 발생 가능성을 최대한 줄이는 방식입니다. (best-fit, first-fit, worst-fit) 사실 시간이 지나면 어떤 방식을 쓰든 그게 그거인 경우가 대부분 입니다...
4) paging 기법 사용: 고정 길이 방식의 대표 유형

 

Internal fragmentation의 해결 방법
1) Segmentation(세그멘테이션) : 가변 길이 방식의 대표 유형
2) 메모리 풀 : 동적 할당의 방식 중 하나. 미리 필요한 만큼 할당 받아서 만들어 둔 다는 것이 동적 할당(즉흥적으로 만 들어짐)과 차이점 입니다.

 

https://jhnyang.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-OS-TLB%EC%9D%98-%EB%93%B1%EC%9E%A5-%ED%8E%98%EC%9D%B4%EC%A7%80-%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%84%B1%EB%8A%A5-%EB%AC%B8%EC%A0%9C%EC%99%80-%EA%B0%9C%EC%84%A0

 

 

 

방금 없으면 가져와서 실행시킨다고 했잖아요? 이렇게 프로그램을 가져와서 메인메모리에 할당하는 방법이 3가지가 있습니다.

맨 왼쪽처럼 메인메모리가 존재합니다. 파란색은 현재 동작하고 있는 프로세스입니다. 위쪽이 낮은 주소고 아래쪽이 큰 주소입니다. 저는 12KB짜리 용량을 가진 프로그램을 메모리에 동작시키고 싶습니다. 남은 공간을 보니 낮은 주소부터 6KB, 14KB, 19KB, 11KB, 13KB 네요. 이런 내용은 free storage list(빈 기억장치 리스트)에 의해 관리됩니다. 이제 여기서 어디에 적재할 것인지 3가지 방법이 나뉩니다.

 

1. First fit (최초적합)

 - free storage list 를 있는 그대로 순차적으로 보면서 들어갈 공간이 있으면 더이상 보지 않고 바로 적재하는 방법입니다.

 

2. Best fit (최적적합)

 - free storage list 를 크기(길이)가 작은 순으로 정렬시킵니다. 그 다음에 순차적으로 들어갈 공간을 보면서 가장 효율적인 곳을 찾는 방법입니다.

 

3. Worst fit (최악적합)

 - free storage list 를 크기가 큰 순으로 정렬시킵니다. 그리고 첫번째에 해당하는 가장 큰 곳에 적재하는 방법입니다.

 - 이 방법이 굳이 왜 생겼냐고 물으신다면, '12KB 프로세스를 남는 공간이 가장 큰 30KB 에 적재하면 나머지 18KB에 또 다른 프로세스를 적재할 수 있겠네?' 라는 컨셉에서 나온 것입니다.

 

이 세가지를 비교해보았다는데요 공간적, 시간적 효율을 보면 다음과 같습니다.

 - 공간 효율성 : Best fit > First fit > Worst fit
 - 시간 효율성 : First fit > Best fit = Worst fit

Best fit과 Worst fit 은 정렬이 들어가다 보니 아무래도 시간 효율성이 First fit 보다는 떨어집니다.

 

 

 

 

 

 

 

출처

 

https://www.youtube.com/watch?v=Lp5ARfO9RRg&ab_channel=%EC%BD%94%EB%94%A9%ED%95%98%EB%8A%94%EA%B1%B0%EB%8B%88

 

https://www.youtube.com/watch?v=u13qK7zKAdY&list=PLWeHDbEQ9ttRmJANzLmHWEdKFefsiThZz&index=11&ab_channel=%EC%9A%B0%EC%84%A0%EB%AF%B8

 

https://velog.io/@wordi/%ED%8F%AC%EC%9D%B8%ED%84%B0-%EB%B3%80%EC%88%98%EC%99%80-%EB%A9%94%EB%AA%A8%EB%A6%AC%EC%9D%98-%EA%B4%80%EA%B3%84

 

https://github.com/Mehul2205/MemoryAllocation

 

https://jhnyang.tistory.com/284

 

https://just-my-blog.tistory.com/37