[13] 운영체제 - Memory-2

안녕하세요.

저번 포스팅에서는 운영체제의 메모리 관리에 들어가기 전 알아야 할 메모리 주소에 관한 설명들과 

관련 용어들을 살펴보는 시간을 가졌는데요. 오늘은 본격적으로 운영체제가 메모리를 관리해주는 역할 중 하나인

메모리 할당에 관해 알아보도록 하겠습니다. 그럼 바로 시작해보도록 하겠습니다.

기본적으로 프로세스가 작업을 수행하려면 메모리에 올라가는 과정, 즉 운영체제에 의한 메모리 할당이 주어져야 합니다.

우리가 살펴볼 할당 방법은 3가지인데, 이 3 가지가 어떤 방법이며 문제점이 무엇이고 그 문제점을 해결하기 위해

어떤 방법이 나왔는지를  생각하면서 공부하시면 더욱 도움이 될 것입니다.

1. Continuous Memory Allocation  - 연속 할당

말 그대로 연속된 공간의 메모리를 프로세스에게 할당해주는 방법을 말합니다. 

이렇게 연속적으로 메모리를 할당해주면 프로세스마다 할당된 메모리 공간 사이에 할당되지 않은 빈 공간이 생기게 되는데요!

이를 Hole이라고 합니다. 즉 Hole은 현재 할당이 가능한 메모리 공간들을 말합니다.

연속된 메모리 공간을 할당해주는 방법에도 크게 세 가지 내부적인 방법이 존재합니다.

    1) First-Fit : 메모리 요청이 들어왔을 때 요청한 크기를 만족하는 Hole 중 가장 첫 번째 Hole을 할당

    2) Best-Fit : 메모리 요청이 들어왔을 때 요청한 크기를 만족하는 Hole 중 가장 작은 크기의 Hole을 할당

    3) Worst-Fit : Best-Fit과 반대로 요청한 크기를 만족하는 Hole 중 가장 큰 크기의 Hole을 할당

여기서 할당 크기는 프로세스가 필요로 하는 정확한 크기로도 할당이 가능하지만 그렇지 않은 경우도 많습니다.

왜냐하면 메모리를 할당해주는 단위가 Byte 단위가 아니라 시스템의 Block 단위이기 때문입니다. 

이 Block은 시스템마다 크기가 다릅니다.

예를 들어 어느 시스템에서 Block 단위가 1KByte 일 때 프로세스가 14.3KByte를 요청한다면

정확히 14.3KByte를 할당해주는 것이 아니라 블록 단위로 15Block 즉 15KByte를 할당해줍니다. 

이렇게 된다면 0.7KByte의 메모리 낭비가 일어나게 되는데요

이렇게 Block의 단위 할당으로 인해 요청하는 메모리 크기보다 큰 메모리를 할당해주어 메모리 낭비가 일어나는 것을 내부 단편화라 합니다.

내부 단편화가 있다면 외부 단편화도 존재할 텐데요!

외부 단편화는 메모리 공간을 연속적으로 할당해주는 데서 오는 문제입니다. 

예를 들어 메모리 공간이 총 100이고 현재 총 3 개의 프로세스에게 메모리 공간이 다음과 같이 할당되어 있다고 가정해봅시다.

A(10)

10

B(20)

10

C(20)

30

현재 여유 공간의 총합은 50이 됩니다. 이러한 상황에서 다른 프로세스가 메모리 공간 40을 요청한다면 할당을 해줄 수 있을까요? 할당해주지 못합니다.

왜냐하면 여유 공간의 총합은 50이지만 40의 연속된 공간이 존재하지 않기 때문입니다.

이처럼 메모리 여유 공간의 크기는 충분하지만 연속되어 있지 않아 할당해주지 못하는 문제를 외부 단편화라고 합니다. 그렇다면 이러한 외부 단편화를 해결하는 방법을 바로 알아보도록 하겠습니다.

첫 번째로 Compaction이라는 방법입니다. Compaction 이란 말 그대로 압축한다는 뜻입니다.

즉 할당된 메모리 공간들을 한쪽으로 모아 연속된 공간을 확보하는 것을 말합니다. 하지만 이러한 방법들은 실행 시간에 주소 바인딩이 일어나는 프로그램들만 가능하며 그렇지 않다면 압축되었을 때 잘못된 메모리 공간의 주소를 접근할 수 있습니다. 그러므로 Compaction 기법은 상당히 제한적입니다.

두 번째 방법은 애초에 메모리 공간을 연속되지 않게 할당해주는 방법입니다. 이 방법에는 크게 두 가지가 있습니다. 하나는 Paging (페이징), 다른 하나는 Segmentation(세그먼테이션) 기법입니다.

2. Paging

Paging 이란 언급했던 것과 같이 프로세스에게 메모리를 연속적으로 할당해주지 않는 방법 중 하나입니다.

그렇다면 어떻게 비연속적으로 메모리를 할당해줄까요?

Paging이라는 단어를 보면 어느 정도 유추할 수 있다시피 책의 목차를 보면 어떤 단원이 몇 페이지에 나와있는 것을 알아볼 수 있듯이 프로세스의 Logical Memory를 조각으로 나누어 그에 대응하는 Physical Memory 공간 조각이 어디에 위치하는지 목차와 같은 역할을 하는 Page Table에 저장을 합니다.

Logical Memory의 조각을 Page라 하고, Physical Memory의 조각을 Frame이라고 합니다.

여기서 중요한 것은 Page의 크기와 Frame의 크기가 같다는 것이고 Page Table의 인덱스 수는 Page의 수와 같습니다.

Paging

Page(0)은 Page Table의 0번째 인덱스에 대응되며 0번째 인덱스의 값이 1이므로 

Page(0)은 Physical Memory의 1번째 Frame에 올라가게 됩니다.

이러한 Page Table은 PCB에 저장되며 프로세스가 종료되면 같이 사라집니다.

Paging Address Translation

이러한 Paging 기법은 메모리의 연속적인 공간에 올라가지 않기 때문에 각각이 어느 위치에 올라가는지 

Page Table에 저장된 값으로 주소를 변환하여 원하는 위치에 접근해야 합니다.

Paging 기법을 통해 CPU에서 나온 Logical Address는 다음과 같은 명령어 구조를 갖고 있습니다.

Logical address의 공간은 2^m이며 Page size의 크기는 2^n

여기서 Page number는 몇 번째 Page 인지, 즉 몇 번째 Page Table 인덱스를 찾아 값을 가져와야 하는지를 나타내고 Page offset을 이해하기 위해서는 위에서 언급한 바와 같이 Page의 사이즈와 Frame의 사이즈가 같다는 것을 이해하셔야 합니다.

하나의 Page 안에서 시작점으로부터 d 만큼 떨어져 있는 위치의 Physical Memory 상의 위치는

대응하는 Frame의 시작점에서 d 만큼  떨어져 있는 곳에 올라가있게 됩니다.

이것이 가능한 것은 Page의 크기와 Frame의 크기가 같기 때문이고 위에서 언급한  offset이 바로 d입니다.

다음 그림을 보시면 더 쉽게 와 닿으실 것입니다.

Paging에 관하여 몇 가지 더 알아보도록 하겠습니다.

Page table을 사용하기 위해서는 Page table 역시 메모리에 올라가있어야 하는데요.

이때 Page Table Base Register는 Page table의 메모리 위에서의 시작 점을 의미하고

Page Table Length Register는 Page table의 크기를 나타내며 이 두 값으로 잘못된 주소 접근을 방지합니다.

Page Table이 메모리에 올라가 있기 때문에 데이터나 명령문에 접근하기 위해서는 두 번의 메모리 Access가 일어나게 되는데요

하나의 데이터나 명령문에 접근하기 위해 메모리에 여러 번 Access 하는 것은 비효율적이므로

이 문제를 해결하기 위해 나온 것이 바로 Translation Look-aside Buffers (TLB)입니다.

TLB

TLB는 일종의 캐시의 역할을 하는 레지스터로 역할이 비슷합니다.

메모리의 여러 번 Access를 막고자 Page table의 내용을 TLB에 저장하여 바로 메모리에 접근을 할 수 있게 합니다. 

시작은 비어있는 TLB로 Page table을 통해 메모리를 두 번 Access 하게 되지만 한번 Access된 Page table의 정보는 TLB에 저장되어 다음부터는 TLB를 통해 메모리에 바로 Access 하는 것을 가능하게 합니다.

또한 Logical Memory가 Page 단위로 나누어진다면 앞에서 다뤘던 내부 단편화 또한 일어나게 됩니다.

하지만 내부 단편화되어 비어있는 공간의 주소를 접근하는 것은 막아야 하기 때문에 Valid-Invalid Bit를 사용합니다. v는 허용된 범위의 Page table이고 i는 허용되지 않는 범위의 Page table입니다.

Valid-Invalid Bit

공통된 코드를 갖는 여러 프로세스들이 Page table을 가질 때도 중복의 문제가 발생하는데

공통된 코드를 공유하기 때문에 Page table 역시 같은 부분이 있는데요. 이럴 경우에는 공통된 Page table을 한 번만 메모리에 올리고 그것을 서로 다른 프로세스가 공유하면서 중복된 Page table을 공유하며 메모리 공간의 낭비를 막습니다.

이번 시간에는 여기까지 공부해보고 다음 시간에는 Page Table의 구조를 살펴보고 Paging을 마무리하고

Segmentation에 대해 공부해보도록 하겠습니다. 메모리가 많이 어렵네요! 그래도 최대한 열심히 포스팅해보도록 하겠습니다.

감사합니다.