[OS] Chapter 07. 메모리 관리

[OS] Chapter 07. 메모리 관리

누워서 보는 운영체제 이야기 - 김주균 교수님

---

▶ 메모리를 잘 관리하면 프로그램의 실행 성능을 높여 CPU의 효율적인 사용과 사용자에게의 빠른 응답성을 가능하게 하므로, 운영체제의 효과적인 메모리 관리는 당연히 요구되는 일

• 메모리: information을 저장할 수 있는 모든 object
• 넓은 의미에서의 메모리 - 캐시, 메인 메모리, 디스크(PC에서의 하드 역할을 더 큰 시스템에서 하는 것) 등
• 좁은 의미에서의 메모리 - 메인 메모리
• 7장에서는 좁은 의미의 메모리. 즉, 메인 메모리에 대해 다룰 것임

▶ 메모리의 구성 방식을 알아보고, 그 다음 주어진 구성과 연관하여 시스템의 성능을 고려한 관리 기법들을 차례로 알아볼 것
▶ 프로그램과 프로세스라는 말은 특별한 경우가 아닌 한 병용해서 사용할 것

• Process size: space의 크기를 가지고 정의함

▶ 이 장에서는 프로그램이 나눠지지 않고 전부, 그리고 연속적(Contiguous)으로 메모리에 적재되는 경우를 다룰 것

• 이런 방식은 시기적으로 오래되어 뒤떨어진 것들이지만 관리 기법의 발전 과정을 배우고, 이것을 바탕으로 더 좋은 기법을 생각해 내는데 유용함
• 실제로 거의 대부분의 시스템은 프로그램의 일부분이, 그것도 여러 개로 흩어져 메모리에 적재되어 실행되며 이 방식들의 설명은 다음장에서 할 것

 

# 7.1 메모리의 구성은?

▶ 메모리를 어떻게 구성할 것이냐의 문제는 어떻게 관리할 것이냐의 문제와 밀접하게 연관되어 있음
▶ 메모리의 구성과 관련하여 정해져야 할 것

1. 다중 프로그래밍의 정도(Multiprogramming Degree): 동시에 메모리에 저장되는 프로세스의 개수
2. 각 프로세스에게 얼마큼의 메모리를 줄 것인가? → 메모리 분할(Partition) 방식과 연계되어 있음. 한 분할 당 한 프로세스를 수용할 수 있으므로 메모리의 분할을 k개로 하면 다중 프로그래밍 정도가 최대 k가(모든 분할에 프로세스들이 적재되었을 경우)되는 것이며, 각 분할의 크기를 어떻게 하느냐에 따라 프로세스들에 부여되는 메모리 양을 같거나 다르게 할 수 있음
3. 메모리의 분할을 미리 해 두고 고정적으로 운영할 경우 고정(Fixed) 또는 정적(Static) 분할이라 하며, 미리 정해두지 않고 프로세스의 크기나 개수에 따라 변동시켜 나갈 때를 가변(Variable) 또는 동적(Dynamic) 분할이라 함 → 고정 분할의 경우에는, 각 프로세스가 들어 갈 분할을 지정하고 항상 그 분할로 적재할 것인지, 아니면 상황에 따라 다른 분할로의 적재도 가능하도록 할 것인지를 결정해야 함
4. 프로세스에게 메모리를 할당할 때 연속적으로 할 것인가 아니면 비연속적으로 할 것인가? → 이 장에서는 연속적 할당을 전제로 함

 

# 7.2 메모리의 관리는?

▶ 메모리 구성에 따라 효율적인 관리를 위한 기법
① 적재 기법(Fetch Strategy)

• 프로세스에게 언제 메모리를 할당해 줄 것인가 즉, 언제 프로세스 메모리에 적재할 것인가를 다루는 기법
• 요구(Demand) 적재: 적재의 요구가 있을 때 적재
• 예상(Anticipatory) 적재: 적재의 요구가 있을 것으로 예상하고 미리 적재
• 대부분의 시스템에서는 요구 적재를 채택하고 있음

② 배치 기법(Placement Strategy)

• 프로세스들을 메모리 공간의 어디에 적재할 것인가를 다루는 것
• 고정 분할의 경우: 지정된 분할로만 적재할지 아니면 분할을 달리해가며 적재될 수 있도록 할 것인지만 결졍
• 가변 분할의 경우: 몇 가지 적합(Fit) 기법이 있음 → 나중에 자세히 설명

③ 교체 기법(Replacement Strategy)

• 메모리 공간이 부족할 경우 새로 적재돼야 할 프로세스를 위해 이미 메모리에 있는 프로세스 중 어떤 것을 골라 디스크로 내보내고 그 공간을 확보할 것인가에 요구되는 기법

④ 할당 기법(Allocation Strategy)

• 프로세스에게 메모리 공간을 얼마 정도로 줄 것인가를 결정하는 것
• 이 장에서는 프로그램 전체를 수용할 수 있는 크기로 주는 것으로 가정함

 

# 7.3 단일 프로그래밍

▶ 단일 프로그래밍: 한 번에 하나의 프로세스만이 메모리에 적재되고 실행이 종료되면, 다음 프로세스가 적재되는 시스템
▶ 메모리의 크기가 적재할 프로그램의 크기보다 작은 문제점 발생 시 오버레이 사용

• 오버레이 : 프로그램의 일부분만을 먼저 적재하여 실행시킨 다음 나머지 부분들을 다시 적재하여 실행
• 수동적(Manual) 오버레이: 프로그램을 적당한 크기로 나누는 등의 부담이 사용자에게 있게 되는 오버레이

단일 프로그래밍과 메모리

▶ 프로그램 실행 중 커널 영역을 침범하지 못하도록 하는 보호 기법이 요구됨

• 경계 레지스터(Boundary Register): 커널과 프로그램의 경계 주소 값을 넣어두고, 프로그램이 실행되면서 참조하는 메모리 주소 값이 이 경계 값을 침범할 경우 트랩으로 실행을 중지시키면 될 것

▶ 단일 프로그래밍

• 빈 공간으로 남는 메모리는 물론 CPU와 다른 자원들의 낭비 또한 많아서 시스템 성능을 매우 떨어트리게 됨

 

# 7.4 고정 분할에서의 다중 프로그래밍

▶ 메모리를 여러 개의 분할로 나누어 놓고, 각 분할에는 하나의 프로세스만을 수용하도록 함으로써 다중 프로그래밍을 구현하는 방식
▶ 각 분할은 고정

고정 분할 다중 프로그래밍

▶ 프로그램들이 컴파일 될 때 주소지정이 이루어지는 경우

• 메모리 할당은 절대 로더(Absolute loader)에 의해 언제나 지정된 분할로 들어감
• 특정 분할로 쏠림 현상이 발생 → 메모리의 낭비

▶ 재배치 가능 코드로 컴파일하여 재배치 로더가 비어 있는 임의의 분할로 들어갈 수 있도록 함으로써 낭비를 줄일 수 있음
▶ 분할보다 프로그램이 더 큰 경우 → 오버레이 방법 사용
▶ 메모리의 보호

• 위의 그림처럼 두 개의 경계 레지스터를 사용하여 보호

▶ 메모리 단편화(Fragmentation) 문제

• 내부 단편화: 분할에서 프로세스가 차지하고 남는 공간 때문에 발생하는 낭비
• 외부 단편화: 분할의 크기가 프로세스의 크기보다 작아 프로세스를 수용할 수 없어서 생기는 메모리 낭비

▶ 장단점

• 관리가 쉬우며 오버헤드가 작다
• 다중 프로그래밍의 정도가 고정
• 단편화에 따른 메모리 낭비

 

# 7.5 가변 분할에서의 다중 프로그래밍

▶ 가변 분할

• 분할의 시기와 개수 그리고 크기가 사전에 정해진 바 없이, 프로세스를 수용할 때 그 크기만큼 메모리 공간을 할당해 줌
• 내부 단편화는 방지할 수 있지만 관리가 복잡해짐으로 해서 생기는 오버헤드는 감수해야 함
• 관리를 위해 사용중인 공간과 빈 공간들에 대한 정보가 필요: 테이블이나 리스트로 표현

▶ ex) 사용자 공간이 100MByte인 메모리에서(first fit 기법 사용)

1. 크기가 10MByte인 processA의 적재
2. 크기가 20MByte인 processB의 적재
3. 크기가 15MByte인 processC 적재
4. processC의 메모리 반납
5. processA의 메모리 반납
6. 크기가 50Mbyte인 processD의 적재
7. 크기가 10Mbyte인 processE의 적재
8. processB의 메모리 반납

가변 분할의 메모리 운영

반납되는 빈 공간들은 used에서 빠져 free로 추가되고, 프로세스의 적재를 위해서는
free를 탐색하여 요구되는 크기를 수용할 수 있는 노드를 찾아 그 크기만큼을 할당해 줌
할당 후 남은 만큼이 떼어준 노드의 크기가 됨으로써 free에서 이 노드의 크기는 줄어든 반면,
할당된 만큼의 크기를 가지는 노드가 used에 새로 추가됨

▶ 배치 기법: free 리스트에서 적재가 가능한 빈 공간을 찾을 때, 어떤 빈 공간을 할당해 줄 것인가?

• 최초적합(First-fit): free 리스트에서 처음부터 시작하여 요구한 크기를 만족시키는 제일 먼저 발견되는 공간을 할당
• 최적적합(Best-fit): free 리스트를 끝까지 탐색하여 요구하는 크기를 만족시키면서, 그 차이가 제일 작은 공간을 찾아 할당해 주는 방법
• 최악적합(Worst-fit): free 리스트를 끝까지 탐색하여 요구하는 크기를 만족시키면서, 그 차이가 제일 많이 차이나는 공간을 찾아 할당해주는 방법

▶ 세 가지 배치 기법의 비교 분석

• 최초 적합은 free 리스트에 대한 탐색을 중간에서 끝낼 수 있는 반면, 최적과 최악은 끝까지 탐색해야 하므로 시간적 부담이 큼
• 최초 적합에서는 할당 후 남은 크기가 어중간해서 사용되지 못하는 공간이 생길 수 있으나, 최적 적합에서는 큰 빈 공간을 그대로 유지 시킬 수 있음. 하지만, 최적 적합은 결과로 남는 크기는 매우 작을 것이고 이런 빈 공간들은 거의 활용되지 못함
• 홀(hole): 크기가 아주 작아서 실제로는 할당될 가능성이 희박하고 결과적으로 낭비되는 공간 → 외부 단편화의 대표적인 예
• 최악 할당은 홀의 발생을 억제할 수는 있는 반면, 큰 빈 공간을 확보하기 어려움
• 최초와 최적 적합이 최악에 비해 더 효율적이고, 최초가 최적보다 실행 속도가 빠르므로 최초 적합을 많이 사용
• 최초적합을 사용할 경우 시간이 지날수록 free 리스트의 앞부분부터 매우 작은 노드들(대부분 홀)이 등장하고 점점 탐색시간을 길게 만드는 현상이 발생할 수 있음
• next-fit: 위의 문제를 보완하기 위해 free 리스트를 순환구조로 한 다음, 할당이 가능한 노드가 선택될 때마다 헤더포인터를 이 노드 다음으로 옮기게 하는 방법

• 50% 규칙(50-percent Rule)
  • 가변 분할 방식으로 메모리의 관리를 오랫동안 한 후 리스트를 살펴보면 free 리스트에는 매우 많은 노드들이 있게 되고, 이 노드들은 대부분 홀이 되어 있을 것임.
  • 별로 크지 않은 프로세스들의 적재 요구조차 수용할 수 없는 상태가 되고 실제로 메모리의 1/3이 홀이되어 사용할 수 없게 되는 현상
  • 작은 빈 공간을 합쳐 더 큰 빈 공간을 만드는 작업이 요구됨

▶ 외부 단편화: 계속되는 할당과 회수로 인하여 메모리가 단편화되어 큰 프로세스를 적재할 수 없는 현상

• 해결책: 병합, 통합
• 인접한 빈 공간의 병합
• 빈 공간 전부의 통합

▶ 인접한(Adjacent) 빈 공간의 병합(Coalescing)

• 병합은 fit정책과 함께 생각할 수 있으며, 여기서는 first fit에 대한 이야기를 함
• 빈 공간으로 반납될 때 인접한 빈 공간이 있다면 이들을 합쳐 좀 더 큰 빈 공간을 만들어주는 방식
• 프로세스가 메모리를 반납할 때마다 실행되고, 인접한 공간이 비어 있지 않다면 병합하지 않음

▶ 빈 공간 전부의 통합(Compaction)

• 병합으로도 공간이 충분하지 않을 경우 사용
• 사용 중인 공간들을 메모리의 한쪽 편으로 밀착시켜 옮기고, 흝어져 있던 빈 공간들을 전부 합쳐 하나의 큰 빈 공간으로 만듬
• 병합과는 달리 사용 중인 공간의 위치 이동이 발생하며 이것은 메모리에 있는 모든 프로세스들의 주소 재배치를 의미하므로 상당한 시간을 요구
• 통합이 진행되는 동안은 모든 프로세스들의 실행이 중지되므로 시스템에 있는 자원들 역시 상당 부분 낭비될 것

▶ 버디 메모리 관리: 고정 분할과 가변 분할을 타협한 절충안

• 버디 시스템에서 메모리는 가변 분할과 마찬가지로 최초에 큰 빈 공간 하나로 시작
• 프로세스의 적재 요구가 있을 때 메모리는 요구한 크기보다 크되, 차이가 가장 작게 나는 2의 승수(power) 크기로 분할되어 할당되며, 같은 크기로 분할된 인접 공간을 버디라고 부름
• 미리 고정된 분할은 아니지만, 그렇다고 프로세스의 크기만큼 할당하는 가변 분할도 아니어서, 분할 내에 프로세스가 차지하고 남는 빈 공간인 내부 단편화가 발생은 하지만 고정 분할 때 보다는 많이 좋아질 수 있음
• 반납되는 빈 공간은 분할 시 정해졌던 자신의 버디가 빈 공간일 때 병합되어 크기를 2의 배수로 늘려나감

• 반납되는 빈 공간의 병합이 제대로 이루어지기 위해서는 자신의 버디가 누구인지를 아는 것이 중요
• 크기가 2^k이고 메모리의 시작주소가 x인 공간이 있을 때, 이 공간의 버디 주소 즉, 버디가 되는 공간의 메모리 시작 주소는 x mod 2^(k+1)의 결과 값이 0일 때는 x + 2^k 가 되며, 2^k일 때는 x - 2^k가 됨
• 버디로 관리하는 아이디어는 병렬 프로그래밍에서 활용될 수 있고, 실제로 이 아이디어를 보완하여 UNIX에서 커널에 할당되는 메모리를 관리할 때 사용하기도 함

▶ 다음장 예고

• 오늘날의 시스템은 PC와 같이 규모가 작은 경우에도 프로그램의 일부를, 그것도 비연속적으로 할당하여 실행하고 있음
• 다중 프로그래밍의 정도를 높여 결과적으로 시스템의 성능을 향상시킬 수 있으며, 아무리 큰 프로그램도 수용하여 실행시킬 수 있게됨