[OS/운영체제] 메모리 할당

Contiguous allocation

1. 고정 분할 방식

이름 그대로 메모리를 분할해놓고, 프로그램이 분할된 메모리의 크기와 맞으면 할당하고 크기가 안맞으면 크기가 맞는곳에 할당을 하는 방식이다.

프로그램 A를 보면 분할 1의 크기에 맞기 때문에 할당할 수 있다. 하지만 프로그램 B를 보면 분할 2의 사이즈보다 크다. 그렇기 때문에 분할 2를 건너뛰고 프로그램A와 크기가 맞는 분할 3 메모리에 할당되게 된다. 이때 분할2번은 건너 뛰게 되는데 이를 "외부 조각"이라고 부른다. 분할 3 내부에서도 프로그램 B가 분할 3메모리를 다 채우지 못했는데, 채우지 못한 부분을 "내부 조각"이라고 부른다

보면 알겠지만 상당히 비효율적이고, 내부 조각, 외부 조각이 발생할 수 있다.

2. 가변 분할 방식

가변 분할 방식은 메모리에 차례대로 올리는 방식이다. 위의 그림에서 보면 처음 상황에서 프로그램 A, B, C를 메모리에 순서대로 할당한다. 하지만 프로그램 B가 실행 완료되고 프로그램 D를 실행하기 위해 메모리에 올리는 상황에서, 프로그램 B가 있던 자리에는 크기가 안맞기 때문에 프로그램 C바로 뒤에 할당된다. 이때 프로그램 B와 할당되어있지 않은 메모리를 외부조각이라고 부른다.

이 방식에서는 내부 조각은 생기지 않지만 외부 조각이 생길 수 있다.

Hole

위의 두개의 방법에서 외부 조각, 내부조각이라는 용어가 나왔다. 이 조각들은 메모리가 할당이 되지 않은, 즉 사용가능한 메모리의 공간이다. 이를 Hole이라고 부른다. 메모리에는 여러가지의 프로그램이 실행되고 완료되는 과정을 반복하기 때문에 메모리 곳곳에 이 Hole들이 생겨있다.

이제 효율적으로 Hole을 찾는 문제인 Dynamic Storage-Allocation Problem에 대해 알아보자

Dynamic Storage-Allocation Problem

가변 분할 방식에서 메모리에 사이즈가 n인 프로그램을 할당할 때 가장 효율적으로 할당할 수 있는 hole을 찾는 문제를 말한다. 여기에는 아래의 3가지 방법이 있다.

First-fit

• Hole의 크기가 n이상인 Hole 중에서 최초로 찾아지는 hole에 메모리를 할당하는 방법
• 가장 처음 찾아진 Hole에 프로그램을 그냥 할당하면 되기 때문에 Hole을 찾는데 오버헤드가 적게든다.
• 하지만 10짜리 프로그램을 100에 할당할 수 있기 때문에 메모리를 효율적으로 사용하는 방법은 아니다.

Best-fit

• 사이즈가 n 이상인 가장 작은 hole을 찾아서 할당하는 방법
• hole들의 사이즈가 담긴 list가 정렬되어있지 않은 경우 모든 list의 모든 hole을 탐색해야 하는데 시간이 든다.
• Hole을 찾는데 오버헤드가 발생하지만 메모리를 보다 효율적으로 관리할 수 있다.

Worst-fit

• hole의 크기가 가장 큰 hole에 프로그램을 할당하는 방법
• 당연히 이 방법은 비효율적으로 보인다. 10크기의 프로그램을 100짜리와 20짜리 메모리중 100에 넣는건데, 이렇게 되면 나중에 100짜리를 할당해야 하는 상황에서 못하기 때문에 당연히,,!

그럼 계속 생기는 Hole들을 어떻게 관리하지?

조그만 메모리에 계속해서 조그만 메모리를 넣으면 언젠가는 기아형태처럼 못쓰는 메모리가 생길 수도있다. 그리고 Hole 사이즈가 커도 프로그램 자체의 크기가 커버리면 못넣으니 이것도 똑같은 상황이다.

정리하자면, 메모리에 충분한 공간이 있어도 메모리가 연속되어 있지 않아 프로그램이 할당되지 못하는 문제를 External Fragmentation이라고 부른다. 그리고 이를 해결하는 방법을 아래에서 알아보자

1. Compaction

• 외부 단편화(External fragmentation)문제를 해결하는 방법이다.
• 사용중인 메모리 영역을 한군데로 몰고, Hole(외부 조각)들을 또 다른 곳으로 몰아서 큰 메모리 여분을 생성하는 방법이다.
• 메모리를 한군데로 몰려면 전체 메모리에 대한 Binding을 검사하고 재할당해야하기 때문에 오버헤드가 아주 큰 방법이다.

Compaction은 프로그램이 실행중에도 메모리의 주소를 변경할 수 있는 Runtime Binding이 지원되어야 가능한 방법이다.

2. Paging

Paging이란 프로그램의 논리적 주소를 페이지라는 일정한 단위로 잘라서 "페이지 테이블"을 통해 실제 메모리의 주소와 매핑하는 것을 말한다. 글이 너무 길어져서 하나의 포스팅으로 나눠서 작성했다! 

[OS/운영체제] Paging

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐