1. Project Introduction

본 프로젝트는 실제 메모리의 크기에 비해 프로그램들의 메모리 요구량이 더욱 크기 때문에 프로그램 수행 시 모든 명령어와 데이터가 메모리에 할당될 수 없기 때문에 메모리 상황에 따라 필요한 부분만 메모리에 할당해서 수행해야 한다. 이를 가능하게 해주는 개념이 가상 메모리 (Virtual Memory)이다.

따라서 이번 프로젝트에서는 라운드로빈 스케줄링을 기반으로 하여 프로세스가 10개의 가상메모리 주소(Virtual address)를 할당받아 MMU(Memory Management Unit)을 통해 실제 메모리의 주소로 변환해서 매핑 및 데이터에 접근한다. 이때, 메인 메모리는 하드디스크의 Cache 역할을 수행하게 된다.

모든 프로그램은 프로세서에서 제공하는 최대 주소 공간만큼의 논리적 가상 메모리가 있고 프로그램이 전체 메모리를 다 사용 할 수 있다고 가정한다. (32bit 주소 => 4 GB 메모리)

2. Project Goals

이번 프로젝트에서는 가상메모리를 사용하는 이유에 대해 알아보고, 가상 접근 주소로부터 물리 메모리를 매핑 하는 방법에 대해 살펴보는 것을 목표로 한다.

또한, 각종 페이징 기법의 개념을 이해하고, 직접 물리 메모리 주소를 계산하고 매핑 함으로써 올바른 값을 도출하는지를 확인한다. 마지막으로 페이징 기법에 따른 전체 flow와 구조를 파악하여 Logic에 맞게 프로젝트를 구현하는 것이 본 프로젝트의 목적이다.

3. Concepts used in CPU simulation

1) 가상메모리(Virtual Memory)

1-1) 가상메모리란?

모든 프로세스는 자신만의 가상 주소 공간을 가진다. 32비트/64비트 프로세스는 각 비트 수에 맞게 최대 4GB/16GB의 주소 공간을 가진다. 따라서 특정 프로세스 내에서 쓰레드가 수행될 때 해당 쓰레드는 프로세스가 소유하고 있는 메모리에 대해서만 접근이 가능하다. 즉, 가상 메모리는 프로세스의 logical memory와 physical memory를 분리하기 위해 생겨난 것이라 할 수 있다. 이를 이용하여, logical memory가 physical memory보다 커지는 것을 가능하도록 할 수 있다.

1-2) 왜 가상메모리를 사용할까?

1-3) 프로세스 가상 주소 공간의 분할

각 프로세스의 가상 주소 공간은 분할되어 있으며, 각각의 분할 공간을 파티션(partition) 이라 한다. 32비트 프로세스는 4GB의 가상 주소 공간을 가질 수 있다.

하지만, 사용자는 가상의 주소 공간 4GB를 모두 사용할 수 있는 것은 아니고, 약 2GB밖에 사용하지 못 한다.

이유는 32비트 주소 공간이 다음과 같이 분할되어 있기 때문이다.

 Null 포인터 할당 파티션 : 0x00000000 ~ 0x0000FFFF

 유저 모드 파티션 : 0x00010000 ~ 0x7FFEFFFF

 64KB 접근 금지 파티션 : 0x7FFF0000 ~ 0x7FFFFFF

 커널 모드 파티션 : 0x80000000 ~ 0xFFFFFFFF

• Null 포인터 할당 파티션
  프로그래머가 NULL 포인터 할당 연산을 수행할 경우를 대비하기 위해 준비된 영역이다. 만일 프로세스의 특정 쓰레드가 이 파티션에 대해 읽거나 쓰기를 시도하게 되면 접근 위반(access violation)이 발생한다.

• 유저모드 파티션
  프로세스의 주소 공간 내에서 유일하게 자유롭게 활용될 수 있는 파티션이다.
  0x00010000 ~ 0x7FFEFFFF의 범위이므로, 2047MB의 크기이다.

2) 페이지 테이블과 엔트리(Page table & Entry)

2-1) 페이지 테이블(Page Table)

가상 메모리를 사용하는 운영 체제에서 개별 프로세스는 자신만의 가상 주소 공간을 가지고 있다. 32비트 프로세스는 0x0000:0000에서 0xFFFF:FFFF까지 표현될 수 있기에 4GB 크기의 주소 공간을, 각 프로세스들의 가상 메모리는 물리 메모리의 각기 다른 영역에 분산되어 로드되거나, page-out 되어 disk에만 저장될 수 있다.

프로세스가 특정 메모리에 접근하기 위해서 OS는 프로세스의 가상 주소를 시스템의 물리 메모리 주소로 변환해 주어야 한다. 페이지 테이블은 가상 주소와 물리 메모리 주소의 매핑 테이블이며, 개별 매핑 데이터는 Page-Table-Entry(PTE)라 한다.

페이지 테이블은 프로세스마다 하나씩 존재하게 되며, 메인 메모리 (RAM)에 상주하게 된다. 즉, 많은 프로세스가 구동될수록, 페이지 테이블로 인한 메인 메모리 사용이 커짐을 의미한다.

2-2) 페이지 테이블 엔트리(Page Table Entry)

프레임 테이블은 어느 프레임이 매핑 되어 있는지에 대한 정보를 들고 있다.

페이지 테이블의 엔트리는 가상 주소의 페이지와 물리 메모리 프레임간의 매핑 정보를 들고 있다. 다음과 같은 부가 정보들을 포함한다.

 valid bit (present bit)

 access bit

 dirty bit (modified bit)

 process ID information

① Valid bit

Page 단위의 메모리는 페이징 파일(디스크 파일)에서 물리 메모리로 page-in 될 수 있고, 물리 메모리로부터 페이징 파일(디스크 파일)로 page-out 될 수 있다.
위 페이지 테이블의 정보 중 valid bit는 이 page가 물리 메모리에 있는지 여부를 나타내는데 사용된다.

② Access bit

Page replacement alogorithm에 사용되며, 해당 페이지에 대한 접근이 있었는지에 대해 기록한다.

③ Dirty bit

Dirty bit는 가상 메모리 관리 시스템의 성능을 향상시키는 데 중요한 역할을 수행한다. 어떤 page가 물리 메모리로 page-in 된 이후, 내용이 전혀 달라진 게 없다면 이 page가 추후 paging file로 page-out 될 때, 달라진 게 없으므로 내용을 다시 복사하지 않아도 되게 된다. 그와 반대로 page-in 된 이후 내용이 달라진 것이 있다면, page-out 될 때 반드시 해당 내용을 paging file에 써야 할 것이다. 이 과정에서 page-out 되기까지 해당 page의 내용이 변경 되었는지를 기록하는 것이 dirty bit 이다. 만약, 이 dirty bit 이 없었다면, 모든 page-out 과정에서 page data copy가 발생할 것이고, 이는 불필요한 성능 하락을 발생시킨다.

④ Process ID information

가상 메모리 관리 시스템은 어떤 페이지가 어느 프로세스와 연관이 있는지 알고 있어야 한다. 가상 주소는 프로세스별로 독립적이므로, 주소가 같다고 해서 같은 메모리를 가리키는 것은 아니다.
페이지 테이블은 여러 프로세스가 요청한 가상 메모리 주소에 대해 정보를 각기 저장시킬 수 있어야 한다.

2-3) 페이지 테이블 종류

페이지 테이블은 다음과 같은 종류가 있다.

 Inverted

 Multi-level

 Virtualized

 Nested

이 중 x86 이 사용하는 것은 Multi-level 방식이라고 한다. 만약 Single-level 즉, 하나의 page table로 4GB의 주소 공간을 표현하기 위해선 2 ^ 20개의 Page Table Entry(PTE)가 필요하다. (4GB / 4KB(1 page size) = 2 ^ 32 / 2 ^ 12 = 2 ^ 20)

2 ^ 20개면 1024 * 1024개의 PTE 정보를 가져야 하는데, 이 때의 페이지 테이블의 크기가 너무 커져서, 2 or 3 level paging을 하게 된다.

2-4) 페이지 테이블 구조(Page Table Structure)

 Hierarchical paging

 Hash Page Tables

 Inverted Page Table

① 계층적 페이징(Hierarchical paging)

• 32비트 컴퓨터에선 페이지 테이블은 4MB정도로 크다.
• 페이지 테이블을 작은 조각으로 나눈다. 페이지 테이블 자체가 다시 페이지 화 되는 것.
  
• p1은 Outer Page Table의 Index, p2는 Inner Page Table의 변위, d는 페이지의 Offeset
  
• 페이지의 접근 시간이 늘어나는 단점이 있다.

② 해시 페이지 테이블(Hash Page Tables)

해시 테이블에 각 항목은 연결리스트를 가지고 있으며, 충돌을 일으켜서 이곳으로 해시되는 원소들이 연결된다. 각 원소는 가상 페이지번호, 사상되는 페이지 프레임 번호, 연결 리스트 상의 다음 원소 포인터를 가진다.

알고리즘 : 가상 주소 공간에서 페이지 번호가 오면 그것을 해싱함수에 의해 해싱 한다.
-> 페이지 테이블에서 연결리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교 한다.
-> 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리주소를 얻고, 일치하지 않으면 다음 원소로 이동하여 반복.

③ 역 페이지 테이블(Inverted Page Table)

• 보통 프로세스 마다 각자 하나씩 페이지 테이블을 가짐 -> 프로세스 전체가 공통으로 사용하는 페이지 테이블, 가상 주소에는 프로세스ID와 페이지 주소를 가지고 있다.
• 메모리공간을 작게 사용한다.
• 주소변환 시간이 더 오래 걸린다.