23.07.13 최초 작성
23.12.11 내용 추가(Page Table Entry, Hierarchical Page Table)

1. Memory Mangement

메모리는 cpu가 직접 접근할 수 있는 유일한 저장장치이다. 프로그램을 실행시키기 위해 메인 메모리에 코드와 변수가 올라가있어야 하고 각 프로세스는 고유의 주소가 필요하다.
하지만 일반적으로 메모리는 비용적으로 비싸기 때문에 효율적으로 관리하는 것이 필요하다. 이를 위해 운영체제는 다음과 같은 기능을 제공한다.

• 프로세스에게 메모리 할당 / 재할당
• 프로세스에게 메모리의 '물리적으로 연속된' / '분할된' 주소 제공
• 파편화 관리 및 캐싱

1.1 Address in Computer

주소는 메모리 상의 위치를 나타내며 물리/논리적 주소, 절대/상대 주소 등 다양한 형태가 있다.
1. 물리 주소(Physical Address)
실제 메모리의 주소. cpu는 물리 주소를 취급해 코드/데이터에 접근한다.
2. 논리 주소, 가상 주소(Logical Address, Virtual Address)
cpu가 생성하는 주소. MMU에 의해 물리 주소로 변환된다.

프로세스는 고유한 논리 주소를 가지고 있고 이를 물리 주소에 매핑해준다.

1.2 Fixed Partition

운영체제는 메모리를 몇 개의 구역으로 나누고 프로세스가 메모리 할당을 요청하면 나눈 구역 중 하나를 할당해 준다. 이 작업을 MMU가 실시하며 매핑 정보를 저장한다. 메모리에 저장한 정보를 접근할 때 기준 주소인 Base Register의 값을 논리 주소에 더해 접근할 수 있다.
적용하기 쉽고 Context Switching이 빠르다는 장점이 있지만 파티션 사이즈가 가장 큰 사이즈로 고정되기 때문에 메모리 낭비가 있을 수 있다.(Internal Fragmentation)

1.3 Varialbe Partition

Fixed Partition을 개선한 방법으로 Partition의 크기를 유동적으로 조정할 수 있다. OS는 프로세스가 요구하는 메모리 크기를 가늠해 메모리를 할당한다.
하지만 할당과 해제를 반복하다 보면 External Fragmentation이 발생하게 되어 활용하지 못하는 공간이 발생하게 된다.

2. Segmentation

파티션을 활용한 할당은 효율적인 관리가 힘들기 때문에 하나의 프로세스가 가진 연속적인 메모리 공간을 나눠서 관리하기 시작했다.
코드, 데이터, 힙, 스택 영역을 메모리에 연속적으로 저장하는 것이 아닌 분리해서 저장한다. 사용자나 프로세스는 메모리를 사이즈 조절 가능한 segment의 모음으로 본다.
각 프로세스는 고유의 Segment Table을 가지고 이 정보는 STBR(Segment Table Base Register)에 저장된다.
이 방법(테이블)을 활용하면 주소 공간의 확장과 각 segment를 보호하기 용이해진다. 하지만 각 영역을 더 작게 나누는 방법이 어렵다.

2.1 Fragmentation

메모리 공간이 조각화되어 사용되지 못하는 현상

• 외부 단편화 (internal fragmentation) : 할당되지 않은 메모리가 조각난 상황
  
• 내부 단편화 (internal fragmentation) : 할당된 메모리 내에 사용되지 않는 공간이 존재하는 현상

3. Paging

• 메모리를 일정 크기로 나누어(Frame) 프로세스가 요청한 크기의 공간이 있으면 할당하는 방식
• 논리 메모리는 Page라는 단위로, 물리 메모리는 Frame단위로 나눠짐 (4kB ~ 16kB 크기)
• 메모리와 논리 메모리는 Page Table을 통해 매핑 정보를 저장하며 이로 인해 프로세스의 정보를 연속적으로 저장하지 않아도 됨
• 내부 단편화 문제가 존재

3.1 Page Table

• 각 프로세스는 Page Table이 존재하며 PTBR(Page Table Base Register)가 Page Table을 가리킨다.

• OS는 유휴 프레임을 관리해 프로세스가 요청 시 해당 프레임을 할당하고 페이지 테이블을 구성해 페이지와 프레임을 매핑 함
  

• 가상 주소 정보를 나타내는 비트를 Page Table을 통해 물리 주소로 변환

• Page Table에 VPN(Virtual Page Number)주소에 저장되어 있는 PFN(Physical Frame Number)값을 통해 가상 주소를 물리 주소로 변환

3.1.1 Page Table Entry

• V (Valid) bit : 해당 가상 페이지의 유효 여부 (가상 주소가 접근할 때마다 테스트)
• R (Reference) bit : 해당 가상 페이지가 최근 접근 되었는지 여부
• M (Modify) bit : 해당 가상 페이지에 쓰기가 발생했는지 여부
• P (Protection) bit : 해당 가상 페이지의 접근 권한 (읽기, 쓰기, 실행 가능)
• Page Frame Number : 해당 가상 페이지에 연결 물리 프레임

3.2 Buddy System Allocator

때때로 시스템은 물리적으로 연속적인(Physicially Contiguous) 공간을 필요로 할 때가 있다. 따라서 Externel Fragmentation을 줄일 방법이 필요하게 되었다.
물리 메모리에 할당할 때마다 저장하고자 하는 데이터의 크기를 확인하고 적합한 크기가 될 때 까지 Segment를 반으로 나눠 저장함.

3.3 Hierarchical Page Table (Multi level Page Table)

• 테이블(Outer Page Table Page)에 하위 테이블을 두어 페이지를 계층적으로 관리하는 방법
• Page Table Entry를 효율적으로 관리 가능
• Sparse Address Space를 효과적으로 관리할 수 있고 물리 메모리를 페이지만으로 잘 관리할 수 있으며 External Fragmentation이 발생하지 않음. 하지만 일반 Linear Page Table보다는 복잡하다.
• 장점
  • 공간 효율적인 페이지 테이블 구조 제공
  • 모든 할당을 Page단위로 가능하게 해 외부 단편화를 막음
  • 구조가 간단해 cpu가 빠르게 참조 가능
• 단점
  • TLB Miss 발생 시 다수의 메모리 참조 발생
  • 선형 구조에 비해 복잡함

4. TLB(Translation Look-aside Buffer)

Hierarchical Page Table을 사용 시 메모리 접근 횟수가 많아져 전체적인 성능이 나빠진다. 이 점을 보완하기 위해 지역성의 원리에 기초해 성능을 개선하고자 하는 방법이 TLB이다.
하드웨어로 구성되어 있으며 사용한 값을 TLB에 저장하고 주소를 다시 불러와야 할 일이 있을 때 TLB를 참조함.

• 링크