[운영체제] 비연속할당(Noncontiguous allocation) - 페이징(Paging)

목차

• 🤔  페이징(Paging)이란?
• 🙉  페이지 테이블(Page table)과 주소 변환
• 🙈  페이징의 문제점
  • 내부 단편화(Internal fragmentation)
  • 페이지 테이블의 크기

🤔  페이징(Paging)이란?

기존 Segmentation과 Contiguous allocation의 경우, 남은 메모리 총량이 충분해도 작은 Hole들을 활용하지 못하는 외부 단편화 문제가 있었습니다.
특히, First-fit의 경우 50% rule에 의해 메모리의 1/3이 낭비되는 문제가 발생하기도 하였습니다.
이러한 문제들의 공통적인 특징은 가변 분할이었습니다.
프로세스마다, 세그먼트마다 크기가 각기 다르다보니 메모리에는 각기 다른 Hole들이 발생하였고, 이러한 Hole들은 대부분 낭비된다는 문제였습니다.

그래서 등장한 개념이 고정 분할과 페이징입니다.
고정 분할은 하나의 프로세스나 세그먼트를 고정된 크기로 나누는 방식을 의미합니다.
반면, 페이징(Paging)은 고정 할당 기법을 사용하며 프로세스를 일정한, 고정된 크기로 잘게 나누어 메모리에 적재하는 메모리 할당 기법입니다.
즉, 논리 주소 공간과 물리 주소 공간을 동일한 크기로 나누어 사용한다면 자투리 공간이 발생하지 않을 것이라는 관점에서 접근한 방식입니다.

'Paging'

위 그림처럼 프로세스와 물리 메모리를 동일한 크기로 나누어 놓으니, 어떠한 프로세스든 블럭처럼 동일한 규격에 맞추어 할당할 수 있기 때문에, 외부 단편화가 사라지게 됩니다.
조금 더 자세히 살펴보자면, Page는 논리 주소를 일정한 크기로 나누어 놓은 것이며, Frame은 물리 메모리를 일정한 크기로 나누어 놓은 것입니다.
즉 Page의 크기는 Frame의 크기와 동일하며, 결국엔 Page를 Frame이라는 공간에 끼워넣는 방식입니다.

'Paging 방식에서 Logical address의 구조'

Paging에서는 논리 주소가 Page number와 Page offset으로 나뉘어집니다.
Page number는 수많은 페이지들을 구분하기 위한 용도로 사용되며, Page offset은 해당 페이지에서 얼마만큼 떨어져 있는가를 나타냅니다.
얼마만큼 떨어진지 표현할 수 있다는 것은 Offset이 한 페이지의 크기를 의미하기도 한다는 것입니다.
32-bit 운영체제는 대부분 Page의 크기가 4KB이며, 64-bit 운영체제는 8KB를 많이 사용합니다.

따라서, 32-bit 운영체제 환경에서 논리 주소는 32bits로 표현할 수 있으며, page offset은 12bits가 됩니다.(4KB = 2^12)
나머지 20bits는 Page number를 표현하기 위해 사용되는데 2^20=1M 이므로 페이지의 개수는 총 100만개까지 있을 수 있다는 것을 의미합니다.
다시 말해, page number는 페이지의 최대 개수, page offset은 페이지의 크기를 의미합니다.

🙉 페이지 테이블(Page table)과 주소 변환

Segmentation과 마찬가지로 Paging도 프로세스마다 페이지 테이블이 메모리에 존재합니다.
Page table의 각 Entry에는 논리 주소에 대한 사상(mapping) 정보를 지니고 있습니다.
그렇기 때문에, Paging 기법에서는 주소를 변환할 때 반드시 Page table을 참조합니다.

'Page table을 사용한 address translation'

우선, CPU에서 논리 주소를 만들어냅니다.
위에서 설명했듯이, Paging에서 논리 주소는 Page number(p)와 Page offset(d)으로 이루어 집니다.

MMU는 메모리에서 Page table을 참조하여, Page number를 바탕으로 논리 주소의 사상 정보를 얻습니다.
Page entry에는 Frame number(f)에 대한 정보가 있으며, 이를 그대로 물리 주소의 상위 비트로 가져옵니다.
Offset은 논리 주소에 있는 Page offset을 그대로 가져옵니다.
그 이유는 Page와 Frame의 크기가 동일하기 때문에 한 페이지 내에서 떨어져 있는 거리는 프레임에서 떨어져 있는 거리와도 동일하기 때문입니다.

🙈  페이징의 문제점

이렇게만 살펴보면 Paging은 정말 완벽한 메모리 할당 기법이라는 생각이 듭니다.
이를 조금씩 변형해가면서 지금까지도 사용되고 있을 정도입니다.

그러나, Paging에도 몇가지 문제점이 존재합니다.

내부 단편화(Internal fragmentation)

만약 한 프로세스의 크기가 100KB라고 가정해보겠습니다.
이 때, 32-bit 운영체제를 사용하고 있어 페이지의 크기는 12KB입니다.

그럼 해당 프로세스가 할당받아야 하는 Frame의 개수는 100KB / 12KB = 8.333...개입니다.
문제는 프레임의 크기는 고정되어 있기 때문에 나머지 0.333... 만큼만 공간을 할당할 수는 없다는 것입니다.
결과적으로 0.666... 만큼의 빈 공간이 생기더라도 Frame을 9개만큼 할당해야 합니다.

External fragmentation은 프로세스를 할당하고 나서 해당 프로세스가 할당된 공간 외부의 빈 공간을 활용하지 못했던 것이라면, Internal fragmentation은 할당받은 Frame 내부의 빈 공간을 활용하지 못하는 문제입니다.

내부 단편화(Internal fragmentation)는 프로세스를 고정된 크기로 나누어 메모리에 할당했을 때, Frame 내부에 빈 공간이 발생하여 메모리가 낭비되는 현상이다.

최악의 경우, Frame의 크기가 4KB인데 이 중에 1byte만 사용되면 나머지 Frame 내부 공간이 엄청나게 낭비가 됩니다.
하지만 이런 경우는 매우 드물고, 평균적으로 한 Segment당 나머지 Page들은 모두 꽉 채워서 할당되고, 1개의 Frame 50% 정도만 낭비된다고 합니다.
그렇기 때문에, 외부 단편화에 비하면 낭비되는 공간이 매우 미미하여 아직까지도 유용하게 사용되고 있습니다.

페이지 테이블의 크기

내부 단편화보다 큰 문제는 Page table의 크기입니다.
32-bit 운영체제에서 논리 주소가 32bits일 때, Page의 크기(겸 Offset)는 4KB이므로 12bits 만큼을 차지하고 있다고 하였습니다.
나머지 20bits는 Page number를 표현하는 데에 사용되며, 2^20은 1M이므로 약 백만이라는 어마어마한 수치를 자랑합니다.
그렇다는 것은 프로세스 1개당 존재하는 Page table의 entry 또한 100만개씩 존재한다는 것입니다.

Page entry에는 논리 주소 mapping에 관한 여러 정보를 담을 수 있지만, 주소 변환을 위한 최소한의 정보인 Frame number만 포함하고 있다고 가정해보겠습니다.
Frame number를 Integer로 표현한다면 Page entry 하나당 크기는 4-Byte가 됩니다.
이런 Entry들이 100만개가 있으면 프로세스 하나를 실행할 때마다 메모리에 4MB 크기의 Page table이 적재될 것입니다.
4MB가 그리 크지 않아보일 수 있지만, 지금 당장 작업 관리자에서 프로세스 개수를 확인해보면 필자의 경우 223개의 프로세스들이 병렬-병행 실행되고 있습니다.

4MB * 223 = 892MB

모두 계산해보니, 결코 적은 수치가 아님을 알 수 있습니다.
그럼 Paging은 비효율적인 메모리 할당 기법일까요?
그렇지 않습니다.
Page table의 크기에 대한 문제점을 해결하기 위한 다양한 table이 등장합니다.

다음 포스팅에서는 Page table의 크기를 해결하기 위해 등장한 계층적 페이지 테이블(Hierarchical Page Table), 해시 페이지 테이블(Hashed Page Table), 역페이지 테이블(Inverted Page Table)에 대해 알아보겠습니다.

 

github : https://github.com/tmdgh1592

tmdgh1592 - Overview