# 세그먼테이션과 페이징

\


## 세그먼테이션(Segmentation)

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2\&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FncZxS%2FbtrZIt3yGF2%2Fb3ZbXZ3G8tZ12KabVw0vB1%2Fimg.png)

* 페이징에서처럼 논리 메모리와 물리 메모리를 같은 크기의 블록이 아닌, 서로 다른 크기의 논리적 단위인 세그먼트(Segment)로 분할하는 가상 메모리 기법
* 프로세스가 사용하는 다양한 논리적 단위(예: 코드, 전역 변수, 힙, 스택, 라이브러리 등)를 별도의 세그먼트로 관리함
  * 각 세그먼트는 논리적으로 분리되어 있으며, 서로 다른 크기를 가질 수 있음
* 로더(loader)는 프로그램을 메모리로 로드할 때 이러한 세그먼트들을 처리하고, 각 세그먼트에 번호를 할당하며 메모리에 비연속적으로 세그먼트를 적재함
* 페이징 방법과 유사하지만 페이지 테이블이 아닌 세그먼트 테이블이 존재하며, 세그먼트 테이블에는 세그먼트번호, 세그먼트의 시작주소(base), 프로세스의 크기(limit)가 저장되어 있음
  * 세그먼트 테이블의 엔트리는 세그먼트의 기준(`limit`)과 세그먼트 상한(`base`)을 가지고 있음
    * `limit` : 세그먼트의 시작 주소
    * `base` : 세그먼트의 길이
  * 세그먼테이션 테이블을 조회할 때, 세그먼트 offset(d)가 0과 세그먼트 크기 사이의 값이여야 하고, 그렇지 않으면 트랩(세그먼테이션 폴트)가 발생함

\


### 세그먼테이션의 장단점

* 장점
  * 내부 단편화 해결: 논리적 단위에 맞추어 메모리를 할당하기 때문에 할당된 공간보다 프로세스가 더 작아서 생기는 내부단편화가 발생하지 않음
  * 논리적 구조 반영: 프로그램의 논리적 단위를 메모리에 직접 반영한다. 프로그램이 사용하는 코드, 데이터, 스택 등을 별도의 세그먼트로 관리할 수 있음
  * 세그먼트 동적 크기: 각 세그먼트는 서로 다른 크기를 가질 수 있음으로써 다양한 메모리 요구사항에 유연하게 대응할 수 있음
* 단점
  * 외부 단편화 존재: 가변 크기의 세그먼트를 사용하기 때문에 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되면 여전히 외부 단편화 문제는 발생함
  * 스왑 아웃될 때 다양한 크기의 세그먼트를 스왑 영역에서 미리 확보해야줘야 함

\


### 세그먼테이션 폴트

![](https://www.computerhope.com/jargon/s/segfault.jpg)

* 세그멘테이션 오류는 프로그램이 허용되지 않은 메모리 영역에 접근을 시도하거나, 허용되지 않은 방법으로 메모리 영역에 접근을 시도할 경우 발생한다.
* 세그먼테이션 경고가 발생하는 조건이나 그것을 사용자에게 알려주는 방법은 운영 체제에 따라 다르다.
  * C 언어에서 발생할 수 있는 세그먼테이션 오류 코드는 [링크](https://ko.wikipedia.org/wiki/%EC%84%B8%EA%B7%B8%EB%A9%98%ED%85%8C%EC%9D%B4%EC%85%98_%EC%98%A4%EB%A5%98#%EC%98%88%EC%A0%9C)를 참고해보자.

\
\


## 페이징(Paging)

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2\&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FCJLvZ%2FbtrZK2p6Xdj%2FKcdk1b7EF2R9fjlR9oPC60%2Fimg.png)

* 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 가상 메모리 관리 기법으로, 프로세스의 논리 주소 공간을 고정된 크기로 쪼개어 빈자리에 할당하는 것
* 물리 메모리는 Frame 이라는 고정 크기로 분리되고, 논리 메모리(프로세스가 점유하는)는 페이지라 불리는 고정 크기의 블록으로 분리되어 페이지를 프레임에 할당함
  * `프레임`: 물리 메모리를 고정된 블록 사이즈로 분할한 것
  * `페이지`: 논리 메모리를 프레임과 같은 크기로 분할한 것
* 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 프레임에 적절히 배치됨
* 개별 페이지의 순서와는 관계없이 페이지번호와 프레임번호를 매핑시켜주는 page table 존재

\


### 페이지 크기

* 프레임 사이즈와 같이 하드웨어에 의해 정의된다.
* 대부분 페이지 크기는 2의 지수승이고, 4KB\~1GB 사이이다.

> 논리 주소 공간 = 2^m, 페이지 크기 = 2^n 일 때, Page number 개수는 2^(m-n)가 생기고, Page Offset 수는 2^n 생긴다.

\


### 페이지 장단점

* 장점
  * 외부 단편화 해결: 페이지를 적용함으로써 연속적인 메모리 할당에서 발생했던 외부 단편화를 해결할 수 있다.
  * 논리 주소 공간: 논리 주소 공간과 물리 주소 공간을 분리함으로써 물리 메모리의 크기보다 더 큰 주소 공간을 가질 수 있다.
* 단점
  * 내부 단편화 존재: 프로세스가 사용하는 메모리가 페이지 크기의 정확한 배수가 아닐 경우, 마지막 페이지의 일부 공간이 사용되지 않고 낭비될 수 있다.

\
\


## 페이지 테이블

![](https://miro.medium.com/v2/resize:fit:533/1*-SDSBsaYzc7TaGhZhAf26A.jpeg)

* 가상 주소 공간을 실제 물리적 메모리 공간에 매핑(mapping)하는 데 사용된다.
* 즉, 프로세스의 페이지는 페이지 테이블을 통해 매핑된 프레임으로 접근하여 논리 주소를 물리 주소로 변환된다.
* 페이지 테이블의 각 엔트리는 하나의 페이지 매핑을 나타낸다.
  * 이 엔트리는 프레임 번호와 함께 다양한 제어 비트(ex: 접근 권한, 수정 여부, 존재 여부(valid / invalid bit)) 등을 포함할 수 있다.
* [페이지 크기에 따른 페이지 테이블 크기 변화 참고](../undefined#페이지-개수와-크기는-trade-off-관계)

\


> 주소 공간이 너무 커지면 페이지 테이블 자체가 커지는 이슈가 발생하는데 모든 페이지 테이블을 메모리에 할당하는 것 자체가 문제가 될 수 있다.\
> 이때, 페이지 테이블 구조를 변경하여 페이지 테이블을 관리할 수 있다.

\


### 1. 계층적 페이지 테이블(Hierarchical page table)

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2\&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbRRszQ%2Fbtryeu9h164%2F0HlCdW2GhtF8VjBDcXDvU1%2Fimg.png)

* 현대 컴퓨터는 매우 큰 주소 공간(2^32 \~ 2^64)을 가지고, 이러한 환경에서는 페이지 테이블의 크기도 상당히 커지게 됨
  * 32비트 논리 주소 공간을 가진 시스템에서 페이지 크기가 4KB(2^12)라면, 페이지 테이블은 100만(2^20 = 2^32 / 2^12) 개 이상의 항목으로 구성됨
  * 각 항목은 다시 4KB로 구성되기 때문에 각 프로세스는 페이지 테이블만을 위해서도 4MB의 공간이 필요하게 됨
* 이러한 경우 모든 페이지 테이블을 메인 메모리에 연속적으로 할당하기에는 상당한 무리가 있음
* 따라서 기존에 프로세스 하나당 하나의 Page table을 사용하던 것을 여러 개로 나누어 사용하는 방식으로 해결할 수 있음
  * 페이지 테이블을 여러 개의 테이블로 분리하여 계층화함

\


#### ✔️ 2단계 페이지 테이블 기법(Two Level Page Table)

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2\&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbJnEVV%2Fbtryg4wpjrd%2Fqq9KlEtHRnzltBgscqAFiK%2Fimg.png)\


* 페이지 테이블 자체가 다시 페이징 하게 하는 방법
*   안쪽 페이지 테이블은 존재하는 주소 공간에 대해서만 생성이 되고 프로세스는 전체 페이지 테이블을 들고 있는게 아니라 안쪽 페이지 테이블만 들고 있음으로써 메모리를 절약할 수 있음

    ![](https://images.velog.io/images/lcy960729/post/a960139c-a114-44ee-9081-aaca6b1f4e05/image.png)

    * p1은 바깥 페이지 테이블의 인덱스이고 p2는 안쪽 페이지 테이블의 인덱스임

\


#### ✔️ 64 bit 운영체제에서의 Hierarchical Page Table

* 64비트 운영체제에서는 p1의 크기가 페이지의 크기 4KB 기준 64bit(2^64) / 4KB(2^12) = 2^52 항목으로 구성될 것이다.
* 이때 2단계 페이지 테이블을 사용하게 되면 바깥쪽 페이지 테이블(p1)의 크기가 2^42 항목을 가지게 되고, 2^44바이트(16,384GB)로 구성될 것이다.
* 이렇게 큰 바깥쪽 테이블을 피하기 위해서는 바깥 페이지 테이블을 작게 나누는 것이고, 총 7단계 페이징이 적합하다.

\


#### ✔️ Hierarchical Page Table의 효율 

* 만약에 TLB가 20ns의 시간초 hit ratio가 98% 메모리 접근 시간이 100ns에 5단계 페이지 테이블이라면 0.98 \* 20 + 0.02 \* (100 \* 6 + 20) = 32ns가 걸린다.
* 페이지 테이블만 사용하게 된다면 엄청난 시간이 소모되는 거지만 TLB를 함께 사용하게 된다면 아주 불합리한 시간이 소모되진 않는다.

\


### 2. 해시 페이지 테이블(Hashed page table)

> 주소 공간이 32비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 사용함

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2\&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb3oGXB%2FbtrYEj0F18l%2FWT5fR7tJkun9clz9U4vs21%2Fimg.png)

* 해시 페이지 테이블은 Page number에 해시 함수를 적용한 값을 바탕으로 Hash table의 entry를 참조함
  * 이때 해시 함수를 적용한 값이 동일한 Entry에 대해서는 충돌(collision)이 발생함
  * 이를 해결하기 위해 Hash page table의 Entry는 `Linked list` 자료구조를 사용함
* 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있고, 해시 원소는 세 개의 필드(`가상 페이지 번호`, `매핑되는 페이지의 프레임 번호`, `다음 원소 포인터`)를 가지고 있음

\


#### 해시 페이지 테이블 동작 과정(알고리즘)

1. 주소 공간으로부터 Page number가 오면 Page number를 해싱함
2. 해싱한 값을 바탕으로 Hash table의 연결리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교하여 일치하는 원소를 찾음
3. 일치되면 그에 대응하는 프레임번호를 가져와 물리 주소를 얻음
   * 일치하지 않으면 연결 리스트의 그 다음 포인터로 2번을 반복함

\


#### 클러스터 페이지 테이블

* 64비트 시스템에서 유용하도록 변형된 해시 테이블 기법이 제안되었고, 해시 테이블과 비슷한 클러스터 페이지 테이블을 사용함
* 해시 페이지 테이블의 각 항목은 한 개의 페이지만 가리키지만, 클러스터 페이지 테이블의 각 항목은 여러 페이지를 가리킴
* 메모리 액세스가 비연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우에 유용함

\


### 3. 역페이지 테이블(Inverted page table)

> 페이지 테이블의 문제는 한 프로세스 당 하나의 페이지 테이블만 가지고 있어야 하기 때문에 사용되지 않는 페이지가 있더라도 페이지의 최대 개수만큼 page table enrty를 가지고 있어야 한다는 문제점이 존재함. 이러한 문제를 해결하기 위해 역페이지 테이블이 등장함

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2\&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbFG2WV%2FbtrymGm46Ik%2FqikkpANguHmiG3hlmklrck%2Fimg.png)

* 메모리에 하나의 고정 크기 페이지 테이블만 두는 방법으로, 페이지 테이블 대신에 inverted 페이지 테이블을 사용함
* 메모리 프레임마다 엔트리를 가지고 엔트리는 아래 요소로 구성됨
  * 프레임에 올라와 있는 페이지 주소
  * 페이지를 소유하고 있는 프로세스의 ID(PID)
* 시스템에서 하나의 페이지 테이블만 존재하고, 테이블 내 각 항목은 메모리 한 프레임을 가리킴

\
\


### Ref

* [세그먼테이션 폴트 참고](https://ko.wikipedia.org/wiki/%EC%84%B8%EA%B7%B8%EB%A9%98%ED%85%8C%EC%9D%B4%EC%85%98_%EC%98%A4%EB%A5%98)
* [\[OS\] 메인 메모리(4) - 페이지 테이블의 구조(Structure of the Page Table)](https://dkswnkk.tistory.com/465)
