페이징 (Paging)

먼저 페이징이 필요한 배경을 이해해보자.
초기 컴퓨터 시스템에서는 프로그램 전체가 물리 메모리에 연속적으로 적재되어야 했다.
이는 두 가지 큰 문제를 발생시켰다:

큰 프로그램은 메모리에 적재하기 어려웠다.
메모리 단편화(fragmentation)가 심각했다.
이러한 문제를 해결하기 위해 페이징이 도입되었다.

페이징의 기본 개념은 프로그램의 논리적 주소 공간과 물리적 메모리를 동일한 크기의 작은 단위로 나누어 관리하는 것이다. 이때 논리적 주소 공간의 단위를 ‘페이지(page)‘라 하고, 물리적 메모리의 단위를 ‘프레임(frame)‘이라고 한다.

Paging — Source: https://www.geeksforgeeks.org/paging-in-operating-system/

페이징 시스템의 주요 구성 요소

페이지 테이블(Page Table):
- 각 프로세스마다 존재하며, 논리적 페이지 번호와 물리적 프레임 번호의 매핑 정보를 저장한다.
- 페이지 테이블 엔트리(PTE)에는 다음과 같은 정보가 포함된다:
  - Valid bit: 페이지가 물리 메모리에 있는지 여부
  - Protection bit: 읽기/쓰기/실행 권한
  - Modified bit (Dirty bit): 페이지 내용이 변경되었는지 여부
  - Referenced bit: 최근에 접근했는지 여부
주소 변환 과정:
1 2
논리적 주소 = 페이지 번호(p) + 오프셋(d) 물리적 주소 = 프레임 번호(f) × 페이지 크기 + 오프셋(d)
예를 들어, 페이지 크기가 4KB(2¹²)이고 32비트 주소 체계를 사용한다면:
- 상위 20비트는 페이지 번호
- 하위 12비트는 오프셋
  이 된다.

TLB(Translation Lookaside Buffer):
페이지 테이블 접근 시간을 줄이기 위한 캐시로, 최근에 사용된 페이지 테이블 엔트리를 저장한다.
주소 변환 과정은 다음과 같다:

1
2
3
4
5
6
1. CPU가 논리적 주소 생성
2. TLB 검색
3. TLB Hit: 바로 물리적 주소 변환
   TLB Miss: 페이지 테이블 접근 필요
4. 페이지 테이블에서 프레임 번호 확인
5. 물리적 주소로 변환하여 메모리 접근

다단계 페이지 테이블:
큰 주소 공간을 효율적으로 관리하기 위해 페이지 테이블을 여러 단계로 구성한다.
예를 들어 2단계 페이지 테이블의 경우:
1
논리적 주소 = 외부 페이지 번호 + 내부 페이지 번호 + 오프셋

페이지 부재 처리(Page Fault Handling):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def handle_page_fault(logical_address):
    if not is_valid_address(logical_address):
        raise SegmentationFault

    page_number = get_page_number(logical_address)

    if not has_free_frame():
        victim_page = select_victim_page()  # 페이지 교체 알고리즘 사용
        if is_dirty(victim_page):
            write_to_disk(victim_page)
        remove_page_table_entry(victim_page)

    free_frame = allocate_free_frame()
    load_page_from_disk(page_number, free_frame)
    update_page_table(page_number, free_frame)

    return restart_instruction()

페이지 부재(Page Fault)

페이지 부재(Page Fault)는 운영체제의 가상 메모리 관리에서 발생하는 중요한 이벤트로, 프로세스가 필요로 하는 페이지가 현재 물리 메모리에 존재하지 않을 때 발생한다.
이러한 상황은 디스크 I/O 작업을 유발하여 시스템 성능에 영향을 미칠 수 있다.

페이지 부재의 발생 과정

페이지 요청: 프로세스가 특정 메모리 주소에 접근하려고 한다.
페이지 테이블 확인: CPU는 해당 주소에 대한 페이지 테이블 엔트리를 확인한다.
부재 확인: 페이지 테이블 엔트리에 해당 페이지가 메모리에 없다고 표시되어 있으면 페이지 부재가 발생한다.
트랩 발생: CPU는 페이지 부재 트랩을 발생시켜 운영체제에 이 상황을 알린다.
운영체제 처리:
- 해당 페이지의 접근이 유효한지 확인한다.
- 유효하지 않다면, 프로세스를 종료한다.
- 유효하다면, 디스크에서 해당 페이지를 메모리로 로드한다.
페이지 로드:
- 메모리에 빈 프레임이 있으면 해당 프레임에 페이지를 로드한다.
- 빈 프레임이 없으면 페이지 교체 알고리즘을 통해 기존 페이지를 디스크로 스왑 아웃하고, 빈 프레임을 확보한 후 페이지를 로드한다.
페이지 테이블 갱신: 페이지 테이블을 업데이트하여 해당 페이지가 메모리에 있음을 표시한다.
프로세스 재개: 중단되었던 프로세스의 실행을 재개한다.

페이지 부재의 영향과 관리

성능 저하: 페이지 부재가 발생하면 디스크 I/O 작업이 필요하므로, 빈번한 페이지 부재는 시스템 성능을 저하시킬 수 있다.
스레싱(Thrashing): 페이지 부재율이 높아져 CPU 이용률이 급격히 떨어지는 현상을 말한다. 이는 프로세스들이 메모리보다 더 많은 페이지를 필요로 할 때 발생하며, 시스템의 효율성을 크게 저하시킨다.
페이지 교체 알고리즘: 효율적인 메모리 관리를 위해 다양한 페이지 교체 알고리즘이 사용됩니다. 예를 들어, FIFO(First In First Out), LRU(Least Recently Used), LFU(Least Frequently Used) 등이 있다. 이러한 알고리즘은 교체할 페이지를 선택하여 페이지 부재율을 최소화하는 데 도움을 준다.

페이징의 주요 특징

메모리 분할:
- 논리적 메모리(프로세스)를 동일한 크기의 페이지로 나눈다.
- 물리적 메모리를 동일한 크기의 프레임으로 나눈다.
주소 변환:
- 논리 주소를 물리 주소로 변환하기 위해 페이지 테이블을 사용한다.
- MMU(Memory Management Unit)가 주소 변환을 수행한다.
비연속적 할당:
- 프로세스의 페이지들은 물리 메모리의 여러 프레임에 분산되어 저장될 수 있다.
내부 단편화:
- 페이지 크기가 고정되어 있어 프로세스의 마지막 페이지에서 내부 단편화가 발생할 수 있다.

페이징의 작동 방식

프로세스가 메모리에 로드될 때, 운영체제는 프로세스를 페이지 단위로 나눈다.
각 페이지는 사용 가능한 메모리 프레임에 할당된다.
운영체제는 페이지 테이블을 생성하여 각 페이지와 해당 프레임 간의 매핑을 유지한다.
CPU가 메모리에 접근할 때, 논리 주소는 페이지 번호와 오프셋으로 나뉜다.
MMU는 페이지 테이블을 참조하여 페이지 번호를 프레임 번호로 변환한다.
프레임 번호와 오프셋을 조합하여 실제 물리 주소를 생성한다.

페이징의 장점

외부 단편화 제거: 메모리를 고정 크기로 관리하여 외부 단편화를 방지한다.
유연한 메모리 할당: 프로세스의 페이지들을 비연속적으로 할당할 수 있다.
메모리 보호: 페이지 단위로 접근 권한을 설정할 수 있어 보안성이 향상된다.
가상 메모리 지원: 실제 물리 메모리보다 큰 주소 공간을 제공할 수 있다.

페이징의 단점

내부 단편화: 페이지 크기가 고정되어 있어 마지막 페이지에서 낭비가 발생할 수 있다.
페이지 테이블 오버헤드: 큰 프로세스의 경우 페이지 테이블이 많은 메모리를 차지할 수 있다.
주소 변환 시간: 페이지 테이블 참조로 인한 추가적인 메모리 접근이 필요하다.