Memory Management(메모리 관리) 3 - 페이징

Noncontiguous allocation(불연속 할당/ 분산 할당)

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음

Paging

• address binding이 복잡해짐
• 동일한 크기의 페이지로 프로세스를 나눠 메모리에 적재
• 내부 단편화 발생 가능

페이징 예시 도식, 출처 - 운영체제(반효경)

• 페이지 테이블에는 각 페이지가 물리 메모리에 몇 번 프레임에 있는지 원소로 기록되어 있다.
• 논리 주소는 페이지 넘버($p$)와 오프셋($d$)로 구성되어 있다.

Page Table의 구현

• 프로그램마다 페이지 테이블이 별도로 존재한다.
• 페이지 테이블은 메인 메모리에 상주한다.
  • 그래서 모든 메모리 접근 연산에는 2번의 Memory access가 필요하다.
    • 페이지 테이블 접근 1회
    • 실제 data / instruction 접근 1회
  • Page-table base register(PTBR)가 페이지 테이블 자체를 가리킴
  • Page-table length register(PTLR)가 테이블 크기를 보관한다.
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라고 불리는 고속의 lookup hardware cache를 사용한다.

TLB

TLB 페이징 도식, 출처 - 운영체제(반효경)

• 메모리 주소 변환을 위한 메인 메모리와 CPU 사이의 하드웨어다.
• 메인 메모리보다 접근 속도가 빠르다.
• 페이지 테이블의 전부를 저장하는 것이 아니라 빈번히 참조되는 페이지의 정보만 가지고 있다.
• TLB는 parallel search가 가능하다. (요청된 페이지 정보가 없을 수도 있기 떄문에 전체 탐색 비용을 줄이기 위해서)
• 프로세스마다 메모리 주소체계가 다르기 때문에 context switch 발생 시 flush된다.

 

 

Effective Access Time

• TLB 접근 시간 = $ε$
• 메모리 접근 시간 = $1$
• Hit ratio = $α$

실제 평균 메모리 접근 시간(Effective Access Time)은?
$EAT=(1+ε)α+(2+ε)(1-α)=2+ε-α$

 

Two-Level Page Table

Two-Level Page Table 도식, 출처 - 운영체제(반효경)

• 현대의 컴퓨터는 address space가 매우 큰 프로그램을 지원한다.
  • 32bit address 사용시 $2^{32}$(4G)의 주소 공간을 갖는다.
    • page size가 4K이면 1M개의 page table entry가 필요하다.
    • 각 page entry가 4B이면 프로세스당 4M의 페이지 테이블이 필요하다.
    • 그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다.
• page table 자체를 page로 구성하는 해결법이 바로 Two-Level Page Table이다.
• 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없다.)이다.
• NULL인 엔트리에 대한 inner page table이 메모리 상에 만들어지지 않기 때문에 공간을 상당히 절약할 수 있게 되는 것이다.

 

 

예시

2 Level Paging의 논리주소의 구성, 출처 - 운영체제(반효경)

2 Level Paging의 주소 변환 과정, 출처 - 운영체제(반효경)

• page offset - 한 페이지의 사이즈가 4KB이므로 Byte단위로 주소를 구분하기 위해서 $2^{12}$bit가 필요하다.
• inner page number - 한 페이지의 사이즈가 4KB이고 엔트리가 4B이므로 1K개 즉, $2^{10}$bit가 필요하다.
• outer page number - 나머지 $2^{10}$bit를 가지게 된다.

 

Multilevel Paging and Performance

• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 $100ns$, TLB 접근 시간이 $20ns$이고 TLB hit ratio가 98%인 경우
  • $EAT = 0.98 × 120 + 0.02 × 520 = 128ns$
  • 결과적으로 주소 변환을 위해 $28ns$만 소요된다.

 

Valid(v) / Invalid (i) Bit in a Page Table

페이지 테이블의 Valid/Invalid bit, 출처 - 운영체제(반효경)

• 페이지 테이블 엔트리에는 frame number외에도 사용되지 않는 영역을 체크하기 위한 valid-invalid bit가 존재한다.
• 이유는 테이블이라는 자료구조 특성상 인덱스로 접근하기 때문에 모든 엔트리가 있어야 하고 사용이 되지 않으면 invalid로 체크하는 것이다.
• valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)
• invalid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 없음을 뜻함 (접근 불허)
  • 프로세스가 그 주소 부분을 사용하지 않는 경우
  • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

 

Protection Bit

• page에 대한 접근 권한을 나타낸다 (read/write/read-only)
  • 예를 들어 code영역은 내용이 바뀌면 안되기 때문에 read-only로 보호한다.
• 다른 프로세스의 접근을 막는 것은 아니다.

 

Inverted Page Table Architecture

추후 정리

 

Shared Pages

추후 정리

 

출처

반효경, "운영체제 2014-1", KOCW, http://www.kocw.net/home/cview.do?cid=3646706b4347ef09