[Jungle] Week10 Pintos_Project3_Virtual Memory: 페이징(Paging) / 페이지(Page) / 프레임(Frame) / 페이지 테이블(Page Table) / 해시 테이블(Hash Table)

페이징(Paging)

페이징은 가상 메모리 관리 기법 중 하나로, 프로세스의 주소 공간을 고정 크기의 블록인 페이지(Pages)로 분할하여 관리하는 방법이다. 각 페이지는 일정한 크기를 가지며, 물리 메모리의 프레임(Frame)에 매핑된다.

 

페이지 (Page)

: 페이지는 가상 주소 공간을 일정한 크기로 나눈 조각이다.

Pintos에서 페이지의 크기는 일반적으로 4KB이다. 프로세스의 가상 주소 공간은 여러 개의 페이지로 구성되며, 각 페이지는 물리적인 메모리에 저장될 수도 있고 디스크에 스왑될 수도 있다. 페이지는 프로세스의 논리적 주소와 물리적 메모리 주소 간의 매핑을 관리하는 데 사용된다.

 

 

프레임 (Frame)

: 프레임은 물리적인 메모리(RAM)에서 페이지가 저장되는 공간이다.

프레임은 페이지 테이블을 통해 페이지와 매핑된다. Pintos에서 프레임의 크기는 일반적으로 4KB로 설정된다. 물리적 메모리는 한정된 크기를 가지기 때문에, 프로세스의 페이지가 물리적 메모리에 모두 적재될 수 없는 경우 일부 페이지는 디스크로 스왑 된다. 스왑 된 페이지는 필요할 때 다시 물리적 메모리로 로드된다.

 

 

페이지 테이블(Page Table)

: 가상 주소의 각 페이지와 해당하는 물리 주소의 프레임 간의 매핑 정보를 저장하는 데이터 구조이다.

페이지 테이블은 프로세스마다 별도로 관리되며, 가상 주소의 페이지 번호를 물리 주소의 프레임 번호로 변환하는 역할을 한다.

 

 

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

: 페이지 테이블에 저장되는 각 매핑 정보를 의미한다.

일반적으로 페이지 테이블 엔트리에는 가상 페이지 번호와 해당하는 물리 프레임 번호, 그리고 기타 제어 비트 등의 정보가 포함된다.

 

 

---

 

[그림 1]

 

[그림 2]

위 [그림 1]에서 논리 주소 10번째인 k를 물리 주소로 mapping한다고 예를 들어보면,

논리 주소 10은 4bit로 1010이다.

이 중에서 앞의 두 수 10은 page number(page table에서 2번 index)를 가리키고 뒤의 두 수 10은 offset을 의미한다.

여기서 상위 2bit인 10 = 2 이므로 page table의 2번 index를 보면 그에 상응하는 물리 프레임 번호는 1이다.

 

 

그림 2

따라서 physical memory에서 1번 프레임을 보면 1번 프레임은 4번부터 시작하므로

1(프레임 번호) * 4(프레임의 크기) + 2(offset) = 6이 된다.

 

∴ k의 물리 주소는 6이다.

 

---

 

해시 테이블(Hash Table)

: 해시테이블은 데이터를 저장하는 자료구조 중 하나다. 효율적인 데이터 검색과 삽입을 위해 설계되었으며, 일반적으로 "키(Key)"와 "값(Value)"의 쌍으로 데이터를 저장한다. 키는 고유한 식별자로 사용되며, 해당 키에 대응하는 값을 테이블 내에 저장하거나 검색하는 데 사용된다.

 

해시 테이블은 내부적으로 배열(배열로 구성된 버킷 또는 슬롯)을 사용하여 데이터를 저장한다.

키를 해시 함수(Hash Function)에 적용하여 해시 코드(Hash Code)로 변환한 다음, 이 해시 코드를 인덱스로 사용하여 배열 내에 데이터를 저장한다. 이렇게 해시 함수를 통해 데이터가 저장될 위치를 결정하므로, 데이터의 검색 및 삽입에 필요한 시간을 상수 시간(O(1))에 근접하게 만들 수 있다.

 

 

 

해시 테이블의 주요 기능 및 특징

해시 테이블은 검색과 삽입 연산에서 뛰어난 성능을 보이는 자료 구조이다.

 

1. 검색(Search)

: 주어진 키를 사용하여 값을 검색한다. 해시 함수를 통해 키를 해시 코드로 변환하고, 이 코드를 인덱스로 사용하여 해당 위치의 값을 찾는다. 이 과정은 상수 시간(O(1))에 이루어진다.

 

2. 삽입(Insertion)

: 새로운 키-값 쌍을 해시 테이블에 추가한다. 삽입 작업도 해시 함수를 사용하여 적절한 위치에 데이터를 저장하므로, 평균적으로는 상수 시간(O(1))에 이루어진다.

 

3. 삭제(Deletion)

: 주어진 키를 가진 항목을 해시 테이블에서 삭제한다. 검색과 유사하게 해시 함수를 사용하여 항목을 찾고, 해당 위치에서 삭제 작업을 수행한다.

 

4. 충돌(Collision)

서로 다른 두 개의 키가 동일한 해시 코드를 가질 수 있는데, 이를 충돌이라고 한다. 충돌이 발생할 경우, 대부분의 해시 테이블은 충돌을 처리하기 위해 추가적인 메커니즘을 사용한다. 대표적인 충돌 해결 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing) 등이 있다.

 

해시 충돌을 해결하는 방법)

1) 체이닝(Chaining)

· 충돌이 발생한 버킷에 여러 개의 항목을 연결 리스트로 연결하여 저장하는 방법이다.

· 충돌이 발생하면 새로운 항목을 해당 버킷의 연결 리스트에 추가한다.

· 체이닝은 간단하고 효율적인 방법이지만, 추가적인 메모리 공간을 필요로 한다.

 

2) 개방 주소법(Open Addressing)

· 충돌이 발생한 버킷 이외의 다른 빈 버킷을 탐색하여 데이터를 저장하는 방법이다.

· 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해시(Double Hashing) 등이 주로 사용된다.

· 개방 주소법은 추가적인 메모리 공간을 필요로 하지 않지만, 충돌이 많이 발생하면 검색 성능이 저하될 수 있다.

 

3) 완전 해시 함수(Fully Hashed Tables)

· 충돌을 완전히 제거하기 위해 해시 함수를 사용하여 모든 항목을 해시 테이블의 서로 다른 버킷에 매핑하는 방법이다.

·  완전 해시 함수는 충돌이 전혀 없는 이상적인 상황을 만들 수 있지만, 구현이 복잡하고 추가적인 계산 비용이 들어갈 수 있다.

 

4) 기타 방법들

· 이중 해싱(Double Hashing), 재해싱(Rehashing), 동의어 해시(Synonymous Hashing), 분리 체이닝(Separate Chaining) 등 다양한 충돌 해결 방법들이 존재한다.

· 선택할 수 있는 방법은 해시 테이블의 크기, 데이터 성격, 충돌 확률 등에 따라 다를 수 있다.