세그먼테이션과 페이지.md

세그먼테이션과 페이징

세그먼테이션(Segmentation)

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

세그먼테이션의 장단점

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

세그먼테이션 폴트

• 세그멘테이션 오류는 프로그램이 허용되지 않은 메모리 영역에 접근을 시도하거나, 허용되지 않은 방법으로 메모리 영역에 접근을 시도할 경우 발생한다.
• 세그먼테이션 경고가 발생하는 조건이나 그것을 사용자에게 알려주는 방법은 운영 체제에 따라 다르다.
  • C 언어에서 발생할 수 있는 세그먼테이션 오류 코드는 링크를 참고해보자.

페이징(Paging)

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

페이지 크기

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

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

페이지 장단점

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

페이지 테이블

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

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

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

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

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

• 페이지 테이블 자체가 다시 페이징 하게 하는 방법

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

  
  • 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비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 사용함

• 해시 페이지 테이블은 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를 가지고 있어야 한다는 문제점이 존재함. 이러한 문제를 해결하기 위해 역페이지 테이블이 등장함

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

Ref

• 세그먼테이션 폴트 참고
• [OS] 메인 메모리(4) - 페이지 테이블의 구조(Structure of the Page Table)