🐶 세그먼테이션(Segmentation)

💁 프로그램의 사용자 관점

🦏 세그먼테이션 하드웨어

• 논리 주소는 두 부분으로 구성 : segement-number, offset
• 세그먼트 테이블(segment table)
  • 사용자가 정의한 이차원 주소는 일차원의 실제 주소로 사상
  • 테이블의 각 항목
    • 세그먼트의 기준 (base) : 세그먼트의 시작 주소를 표시
    • 세그먼트 한계 (limit) : 세그먼트의 길이를 명시

🥑 페이징 (Paging)

페이징은 논리 주소 공간이 한 연속적인 공간에 다 모여 있어야 한다는 제약을 제거→프로세스는 물리 메모리에 빈 공간이 있으면 할당

• 기본 방법
  • 물리 메모리는 프레임(frame)이라 불리우는 같은 크기 블록으로 분할
  • 논리 메모리는 페이지(page)라 불리는 같은 크기의 블록으로 분할
  • 한 프로세스가 실행될 때 프로세스의 페이지는 보조 메모리로부터 메인 메모리 프레임으로 들어 감
  • 모든 자유 프레임 리스트들은 추적 관리
  • 논리 주소에서 물리 주소로 변환하는 페이지 테이블(page table) 필요
  • 내부 단편화

주소 변환 (Address Translation)

CPU에 의해 생성된 주소는 두 부분으로 분할

• 페이지 변호 (p)
  • 페이지 테이블을 액세스할 때 사용
  • 페이지 테이블에는 물리 메모리에서의 베이스 주소(base addresss)가 저장
• 페이지 변위 (d, offset)
  • 페이지 테이블의 베이스 주소에 페이지 변위를 더하면 물리 주소가 생성
• 예 : 논리 주소 공간의 크기가 2^m이고, 페이지가 2^n 크기라면 논리 주소의 상위 m-n 비트는 페이지 번호를 나타내고, 하위 n 비트는 페이지 변위를 나타냄

페이징- 내부 단편화 계산

내부 단편화 계산

• 페이지 크기 = 2048 바이트
• 프로세스 크기 = 72766 바이트 = 35페이지 + 1086 바이트
• 최악의 경우 단편화 = 1 프레임 - 1 바이트
• 평균 단편화 = 1/2 프레임 크기
• 프레임 크기가 작아지면 단편화 감소? 페이지 테이블 크기 증가
• 페이지 크기가 증가하는 추게 : 보통 2~8KB

자유 프레임 (Free Frame)

페이지 테이블 하드웨어 구현

• 페이지 테이블은 메인 메모리에 저장
  • 페이지 테이블 기준 레지스터(PTBR, Page-Table Base Register)가 페이지 테이블을 가리킴
  • 페이지 테이블 길이 레지스터(PTLR, Page-Table Length Register)가 페이지 테이블의 크기 표시
  • 매 데이터/명령 접근을 위해 두 번의 메모리 액세스를 요구 : 페이지테이블-데이터/명령
• 두 번의 메모리 접근 문제는 TLB(Translation Look-aside Buffer)라고 불리는 특수한 소형 하드웨어 캐시가 사용하여 해결
  • TLB는 매우 빠른 연관 메모리(associative memory)로 구성
  • TLB 내의 각 항목은 키(key)와 값(value)의 두 부분으로 구성

연관 메모리 (Associative Memory)

• TLB에서는 페이지 번호가 키가 되고, 프레임 번호가 값이 됨
  • 키가 주어지면 병렬로 검색
• 주소 변환 (A’, A’’)
  • A’가 TLB에 있으면 프레임 번호 가져옴
  • 없으면 페이지 테이블에서 프레임 번호 가져옴

실제 메모리 접근 시간 (Effective Memory Access time)

페이지 번호가 TLB에서 발견되는 비율은 적중률(hit ratio)

• 실제 메모리 접근 시간 예 (캐시 메모리 고려하지 않은 경우)
  - TLB 탐색 20 ns, 메모리 저근 100ns, TLB 적중률 80%
  - TLB 적중 시 데이터를 위한 메모리 접근
  - TLB 실패 시 페이지 테이블 메모리 접근, 데이터 메모리 접근
  

🚡 메모리 보호 (Memory Protection)

• 메모리 보호는 각 페이지에 붙어 있는 보호 비트(protection bit)에 의해 구현
• 페이지 테이블의 각 항목에는 유효/무효(valid/invalid) 비트 추가
  - 유효(valid) : 관련된 페이지가 프로세스의 합법적인 페이지임을 표시
  - 무효(invalid) : 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는단는 것을 표시
  

🍾 공유 페이지(Shared Page)

• 페이징의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 점
• 재집입 가능 코드(reentrant code 또는 pure code)라면 공유가 가능
  • 재진입 가능 코드는 수행하는 동안 절대로 (프로그램 내용이) 변하지 않는 코드
  • 따라서 두 개나 그 이상의 프로세스들이 동시에 같은 코드를 수행할 수 있음
• 공유되는 프로그램
  - 문서 편집기, 컴파일러, 윈도우 시스템, 실시간 라이브러리, DB 등
  

🍠 페이지 테이블의 구조 (Structure of the Page Table)

• 페이징 직접 적용 시 페이지 테이블 크기가 커짐
• 페이지 테이블을 구성하는 가장 일반적인 방법 : 계층적 페이징, 해시형 페이지 테이블, 역 페이지 테이블

계층적 페이징(Hierarchical Paging)

• 논리 주소 공간을 여러 단계의 페이지 테이블로 분할
  • ex) 두 단계 페이징 기법(two-level paging scheme)
• 두 단계 페이징 기법 예
  • 32비트 논리주소 공간, 4KB(2^12)페이지 크기의 시스템 논리주소
    • 20 비트 페이지 번호(2^20 항목), 4MB
  • 페이지 테이블도 페이지화되면 페이지 번호가 분할
    • 10비트 페이지 번호 (2^10 항목)
    • 10비트 페이지 변위 (2^10 항목)

해시형 페이지 테이블(Hashed Page Table)

• 주소 공간이 32 비트보다 커지면 해시형 페이지 테이블을 사용
  • 가상 페이지 번호가 해시 값이 되어 페이지 테이블 참고
  • 같은 위치로 해시되는 충돌(collution)인 경우를 위해 각 항목은 연결 리스트로 구성
• 해시형 페이지 테이블 동작
  • 가상 주소 공간으로부터 페이지 번호로 해싱
  • 해시형 페이지 테이블에서 연결 리스트를 따라가며 페이지 번호 비교
  • 일치하면 그에 대응하는 페이지 프레임 번호를 획득
• 64 비트 시스템에서는 변형된 클러스터 페이지 테이블 사용
  - 해시 페이지 테이블의 각 항목이 한 개의 페이지가 아닌 여러 페이지를 가리킴
  - 성긴(sparse) 주소 공간에 유용 (메모리 접근이 비연속적이고 전 주소 공간에 넓게 퍼진 경우)
  

역 페이지 테이블(Inverted Page Table)

• 지금까지 페이지 테이블은 페이지 마다 하나의 항목을 가짐
  • 페이지 테이블이 가상 주소에 대해 오름차순으로 정렬
  • 페이지 테이블의 크기가 커짐
• 역 페이지 테이블(inverted page table)
  - 메모리 프레임마다 한 항목씩을 할당
  - 논리 페이지마다 항목을 가지는 대신 물리 프레임이 대응되는 항목만 테이블에 저장하기 때문에 메모리에서 훨씬 작은 공간을 점유
  - 프레임에 다라 저장되어 있어 이 테이블에 대한 탐색 시간 필요
  - 주소 변환 시간이 길어짐
  - 이 시간을 줄이기 위하여, 페이지 테이블을 해시(hash)
  - 또한 최근에 사용된 항목들을 버리지 않고 TLB 연관 메모리에 저장
  

🦴참고

Operating System Concepts, 10th Ed.