2023.04.13 - 찾아온 영업 종료의 위기 (부제: Paging)

안녕하세요, 운영체제 Short Quiz 2의 종료와 함께

제 블로그도 폐쇄 직전의 위기에 놓이게 되었습니다.

.

.

.

도대체 os술사에게 어떤 일이...?

근데 이게 방법을 하나도 모르겠어서 머리 쥐어뜯다가 틀린 게 아니라

검산도 5번을 하고.. 답이 5번 모두 똑같아서 주소변환 주소를 자신 있게 적었는데 틀린거라

어디서부터 잘못된 것인지 찾기 위해

오늘은 문제 풀이보다는 이번 Short Quiz 2의 범위였던 Paging에 대하여 정리를 해보려고 합니다.

 

---

 

Paging은 무엇일까?

 

Paging은 메모리 관리 기법 중 하나로

base-bound, Segment와 같은 메모리 관리 기법이 갖는

가변적인 크기 문제를 해결한 메모리 관리 기법입니다.

 

Paging은 Address Space(주소 공간)를

어떠한 숫자 값이나 가변적인 값을 갖는 논리적 세그먼트(예: Code, Heap, Stack)로 나누는 것이 아닌

Page라고 불리는 fixed-sized units으로 나누는 방법입니다.

VM의 주소 공간에서는 Page라고 말하며,

PM에서는 Frame, Page Frame 등으로 말합니다. 

 

일단, 결론부터 말씀 드리자면

Page라는 고정적인 단위를 갖기 때문에

외부 단편화(External Fragmentation) 현상이 발생하지 않는다는 특징을 가집니다.

 

그렇지만 Page 내부에서는 사용하지 않는 공간을 가질 수 있어

내부 단편화(Internal Fragmentation)은 발생 가능하다는 점을 인지해두면 좋습니다.

 

외부 단편화(External Fragmentation)
- partition 영역보다 할당하려는 프로그램의 크기가 커서 해당 영역을 사용할 수 없어 낭비되는 경우, 또는 해당 부분을 지칭

내부 단편화(Internal Fragmentation)
- partition에서 한 작업이 차지하고 남은 영역을 사용할 수 없는 경우, 또는 해당 부분을 지칭

 

아래 삽화를 통하여 예시와 함께 추가 설명을 드리도록 하겠습니다.

 

 

Figure 18.1은 64 bytes라는 아주 작은 크기의 주소 공간을 가정합니다.

Page 1개의 크기를 16 bytes로 둔다면 저희는 총 4개의 페이지를 얻을 수 있을 것입니다.

물리 메모리(메인 메모리)의 크기는 그보다 조금 더 큰 128 bytes라고 가정을 한다면

이 물리 메모리 공간은 128 / 16 = 8 이므로 총 8개의 frame으로 이루어져 있을 것입니다.

 

Figure 18.2에서는 0번 frame에는 운영체제를 위해 공간이 예약(reserved)되어 있고

2번 frame에는 Address Space(주소 공간)에서의 page 3번과 매핑이 되어 있는 것을 확인할 수 있습니다.

앞에서도 간단히 언급하였지만

base-bound, Segment 기법과 비교하여 여러 장점을 가지고 있습니다.

그중, 이전과 비교하여 가장 큰 개선 사항은 flexiblity(유연성)입니다.

 

예를 들어, OS가 우리의 Address Space 공간(64 bytes)을 8개의 프레임을 가진 물리 메모리에 배치하려는 경우,

OS는 Physical Memory에서 4개의 빈 프레임(16 * 4 = 64 bytes)을 찾으면 됩니다.

 

뒤에 이어서 말하겠지만 OS는 이를 위해서

빈 공간을 찾기 위한 리스트, free list와

페이지 -> 프레임 간 매핑 정보, 가상 페이지에 대한 물리 메모리 위치를 기록하기 위한 공간, page table이 필요합니다.

 

---

 

Page Table은 어디에 저장될까?

 

바로 앞에서 가상 페이지에 대한 물리 메모리 위치를 기록하기 위해,

다시 말하여 몇 번 Page가 몇 번 Frame과 매핑되어 있는 지를 저장해두는 자료 구조인 page table이 필요하다고 말했는데

 

그렇다면 page table도 어딘가에는 저장이 되어 있어야 할텐데 과연 어디일까요?

 

레지스터? HDD? Memory?

 

정답부터 말하자면 Page Table은 메인 메모리에 저장됩니다.

 

이유는 Segment Table이나 base-bound과 달리 Page Table은 매우 커질 수 있기 때문입니다.

 

예를 들어 4KB의 크기의 페이지를 갖는 32bits 주소 공간이 있다면,

이 가상 주소는 20비트의 VPN(Virtual Page Number)와 12비트의 Offset으로 구성됩니다.

 

20비트의 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변환의 개수가 2^20이라는 것을 의미하는데

페이지 테이블의 각 요소인 PTE(Page Table Entry)에 담긴 주소 변환 정보 및 추가 필요 정보가 4바이트의 크기를 갖는다면

 

각각의 페이지 테이블을 저장하기 위해서는 4MB가 필요하게 되는데 이는 상당히 큰 수치입니다.

 

만약 100개의 프로세스가 실행 중이라며 각 프로세스 별로 페이지 테이블을 저장해두어야 하므로 400MB라는 메모리를 필요하게 됩니다.

 

 

이러한 이유로, 페이지 테이블의 크기는 매우 크기 때문에 메인 메모리에 저장하게 되는 것입니다.

 

 

---

 

Page Table에는 무엇이 저장될까?

 

 

Page Table은 일종의 배열입니다.

 

저희는 배열을 말할 때, 주로 타입과 함께 말하죠?

int 타입의 배열, char 타입의 배열 등등...

 

이처럼 Page Table에 존재하는 원소의 타입은 PTE(Page Table Entry)입니다.

 

 

Page Table이 PTE가 담긴 배열인 것을 알게 되었으니

PTE가 어떻게 구성되어 있는지 알 필요가 있습니다.

 

위 사진을 통하여 알 수 있듯, PFN(Physical Frame Number)과 0-8에 위치한 여러 비트들로 구성됩니다.

 

PFN을 통해서 우리가 원하는 VPN이 실제 물리 주소 어디에 위치하는지 확인할 수 있습니다. 

또한, PTE에 존재하는 특수한 비트들 몇 개는 알아둘 필요가 있어 아래 표로 정리해보았습니다.

 

이름	역할
valid bit	시스템이 유효한 메모리 주소와 유효하지 않은 메모리 주소를 구별 가능하게 함
protection bit	페이지가 read, write, execute 가능한지 표시함
present bit	페이지가 메모리에 있는지 디스크에 있는지 표시함 (1 - 메모리 / 0 - 디스크)
dirty bit	페이지가 메모리에 들어온 뒤, 변경된 여부를 나타냄
reference bit	페이지가 접근 되었는지 여부를 나타냄

 

이는 다음 포스팅에서 다룰 Replacement Policy(교환 정책)과 밀접한 연관이 있기 때문에 알아두면 좋습니다.

 

---

 

Paging의 문제점?

메모리를 관리하기 위한 기법인 Paging의 큰 소개는 마무리가 되었는데요.

 

여러 매력적인 특징을 가진 Paging 기법이지만

안타깝게도 Paging 역시 해결해야 하는 문제점이 존재합니다.

 

앞서 말했던 Page Table의 크기가 매우 크다는 것을 문제점으로 말하였는데

어쩔 수 없이 Page Table을 메인 메모리에 두는 것으로 또 다른 문제점이 발생합니다.

 

 

그것은 바로 VPN -> PFN 으로 변환하기 위해서는 무조건 Memory Access를 동반한다는 점입니다.

 

이전에 명령어를 실행하기 위하여 Memory Access를 1번 했다고 가정을 하면

 

Paging을 사용할 경우에는 해당 명령어의 주소를 변환하기 위하여 Memory Access를 1번 한 뒤에

명령어 실행을 위한 Memory Access를 1번 더 해야하므로

 

이전보다 속도면에서 느릴 수 밖에 없다는 단점이 존재합니다. 

 

---

그럼 어카노

 

이러한 Paging의 단점을 개선하기 위하여 두 가지 방법을 추후에 소개하고자 합니다.

가볍게 소개하자면

 

1. Hybrid Paging - Segment와 Paging 기법을 적절히 섞어 사용한 새로운 기법입니다.

2. Multi Level Paging - Page Table를 위한 Page Directory라는 새로운 개념을 도입한 기법입니다.

 

.

.

.

.

 

그리고 운영체제 Short Quiz 2는 2번 멀티 레벨 페이징이었죠

 

 풀이 방법을 기대하셨을 여러분이지만

역량 부족으로 인하여 TLB Miss가 나버렸네요 < 딱콩

 

저 대신 풀이를 소개한 포스팅 글이 있으므로

관심 있으신 분은 참고하시면 좋을 거 같습니다 :)

 

https://alchemist-of-error.tistory.com/27

2023.4.13 소붕들의 학교에 몬스터의 등장이라