페이징 (Paging) - (1)

프로세스의 물리 주소 공간이 연속되지 않아도 되는 메모리 관리 기법

외부 단편화와 관련 압축의 필요성을 피할 수 있다.

 

1. 페이징 (Paging)

• 물리 메모리는 프레임(frame) 크기 블록으로 나누어진다.
• 논리 메모리는 페이지(page) 크기 블록으로 나누어진다.
• N개의 Page 프로그램이라면 적재 시 N개의 free frame이 필요하다.
• page table이 논리 주소에서 물리 주소로 변환시켜준다.
• page table은 각 프로세스 별로 생성된다.

(1) 논리 주소

• CPU에서 나오는 모든 주소는 페이지 번호(P)와 페이지 오프셋(d:offset) 두 개의 부분으로 나누어진다.

• 페이지 번호 (P)
  • 프로세스 페이지 테이블(page table)을 접근할 때 사용된다.
• 페이지 오프셋 (d)
  • 참조되는 frame 안에서의 위치
  • frame의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 된다.
• Example
  • Memory 32bits라 가정, page size : 4KB = 2^12 byte
    • 0~11 : Page offset
    • 12~31 : Page number => page 2^20개 존재 가능

(2) 논리 주소에서 물리 주소로 변환

• 페이지 번호 P를 추출하여 페이지 테이블의 인덱스로 사용한다.
• 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
• 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.

(3) Example

• Page size = 2,048 bytes
• Process size = 72,766 bytes = 35 Pages + 1,086 bytes
• Internal fragmentation : 2,048 - 1,086 = 962 bytes
  • 최악의 경우 Internal fragmentation = 1 frame - 1byte = 2,048 - 1 = 2,047 bytes
  • Page size를 줄이면 Internal fragmentaion가 줄어든다. 하지만 Page table의 크기가 커진다. table이 차지하는 공간의 낭비가 생긴다. 
• 보통 페이지의 크기는 4KB or 8KB

(4) 페이징의 가장 중요한 특징

• 메모리에 대한 프로그래머의 인식과 실제 내용이 서로 다르다는 것
• 프로그래머는 메모리가 하나의 연속적인 공간이며, 메모리에는 이 프로그램만 있다고 생각한다. (논리 주소)
• 실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램이 올라와 있다. (물리 주소)
• 논리 주소에서 물리 주소의 변환은 주소 변환 하드웨어에 의해 변환된다.

(5) 프레임 테이블(Frame table)

• 운영체제는 물리 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있다.
• 프레임 테이블(Frame table)에서 관리한다.
  • 각 프레임당 하나의 항목을 가지고 있다.
  • 프레임이 비어 있는지, 할당되었는지, 그리고 할당되었다면 어느 프로세스의 어느 페이지에 할당되었는지를 나타낸다.

 

2. TLB (Translation Look-Aside Buffer)

(1) TLB 사용 이유

• 페이지 테이블을 레지스터에 저장하는 경우 빠르게 접근할 수 있지만 큰 page table을 사용할 수 없다.
• 그러므로 페이지 테이블을 메인 메모리에 저장하고 페이지 테이블 기준 레지스터(page-table base register, PTBR)가 페이지 테이블의 주소 값을 가지고 있다.
  • 페이지 테이블 길이 레지스터 (Page-table length register, PTLR)
• 메인 메모리에 페이지 테이블을 저장하려면 Context-Switching 속도가 빨라지지만 메모리 access 시간이 느려질 수 있다.
• 페이지 번호 기준으로 PTBR 오프셋의 값을 사용해서 페이지 테이블의 항목을 찾는다. (첫 번째 메모리 access)
• 이렇게 얻은 프레임 번호와 페이지 오프셋을 결합하여 실제 주소에 접근한다. (두 번째 메모리 access)
• 메모리 접근 시간이 느려진다.
• 이러한 문제를 해결하기 위해 TLB를 사용한다.

(2) TLB (Translation Look-Aside Buffer)

소형 하드웨어 캐시로 빠른 연관 메모리(associative memory)로 구성

• 각 항목은 key와 value 두 부분으로 구성된다.
• CPU에서 논리 주소를 생성하면, MMU 해당 페이지 번호가 TLB에 있는지 확인한다.
  • 페이지 번호가 발견되면 해당 프레임을 즉시 알 수 있고, 메모리 접근에 사용된다.
  • 만약 페이지 번호가 없으면(TLB miss),  페이지 테이블을 접근하기 위해 메모리 참조를 한다.
    • 페이지 번호와 프레임 번호를 TLB에 추가하여 다음 참조에서 사용한다.
• TLB가 가득 차면, 기존 항목 중에서 교체될 항목을 선택한다.
• 몇몇 항목은 TLB에 고정(wired down) 하기도 한다. - 중요 커널 코드
• 각 항목에 ASID(address-space identifier)를 저장하여 어떤 프로세스에 속한 페이지인지 알려주어 프로세스의 정보를 보호하기 위해서 사용된다.
  • TLB에서 논리 주소를 변환할 때 현재 수행 중인 프로세스의 ASDI와 TLB 항목에 있는 ASID와 같은지 비교한다.

(3) 실질 메모리 접근 시간 (Effective memory access time, EAT)

• 적중률 (Hit ratio) : a
  • 접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율
• Main Memory access Time : 10ns
  • TLB hit시 메모리 접근 1번, TLB miss시 메모리 접근 2번
• Effective memory access time
  • a = 80%, EAT = 0.8*10 + 0.2*20 = 12 ns
  • a = 99%, EAT = 0.99*10 + 0.01*20 = 10.01 ns

 

3. 메모리 보호 (Memory Protection)

(1) Protection bits

• 페이지 환경에서 메모리 보호는 각 페이지에 붙어있는 보호 비트(protection bits)에 의해 구현된다.
• 각 비트는 이 페이지가 읽고, 쓰기 또는 읽기 전용임을 각각 정의할 수 있다.
• 만약 읽기 전용 페이지에 관해 쓰기를 시도하면 운영체제가 하드웨어로 trap을 걸어준다.

(2) Valid(v) or Invalid(i) Bit in Page Table

• 페이지 테이블의 각 엔트리에는 유효/무효(valid/invalid)라는 하나의 비트가 있다
  • 유효(valid)로 설정되면 관련된 페이지가 프로세스의 합법적인 페이지이다.
  • 무효(invalid)로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
• 위 그림에서 페이지 6,7에서 주소를 매핑하려고 시도하면, 비트가 무효로 설정된 것을 발견하여 트랩(invalid page reference)을 발생시킨다.

(3) 페이지 테이블 길이 레지스터 (Page table length register, PTLR)

• 프로세스가 제시한 주소가 유효한 범위 내에 있는 지를 확인하기 위해 모든 논리 주소 값이 PTLR 값과 비교된다.
• 이러한 검사에서 오류가 나타나면 트랩을 발생시킨다.

 

4. 공유 페이지 (Shared Pages)

• 페이징의 장점은 공통의 코드를 공유할 수 있다는 점이다.
• 코드가 재진입 코드(read-only)인 경우 위 그림과 같이 공유할 수 있다.
  • 표준 C 라이브러리 libc에 대한 페이지를 공유하는 세 가지 프로세스가 있다.
• 재진입 코드(read-only)는 자체 수정을 할 수 없는 코드로서 실행 중에는 절대 변경되지 않는다.