Multi-Level Page Table, Virtual Memory, Page Replacement Policy - 운영체제

Multi-Level Page Table

• 목표: 각 페이지 테이블이 연속적으로 할당되지 않도록 하는 목적
• 페이지 테이블을 페이징한다
  • 페이지 테이블을 계층적으로 생성한다
  • 상위 레벨은 페이지 디렉토리
  • 사용되는 페이지만 할당

Hierarchical Page Table

• logical address space를 multiple page table로 나눔
• 2-level의 경우
  • 32bit 주소 w/ 4KB 페이지
    • page number = 20 bits
    • offset = 12 bits
  • 페이지 테이블을 페이징 해야하니 페이지 넘버가 다음과 같이 또 나뉜다
    • 나누는 기준은 page size / page entry size = 4kb / 4b = 2^10 => 10 bits (inner page)
    • inner page = 10 bits
    • outer page = 20 - 10 = 10 bits

Hierarchical Page Table Example

• 64 bits address, memory = 2^64 bytes
• page size = 32kb, page table entry = 4bytes

1. 모든 페이지 테이블이 하나의 페이지 안에 들어가기 위한 레벨의 수
   • page offset = 15 bits
   • 한 페이지에 들어갈 수 있는 최대 페이지 테이블 엔트리 수 = 32kb / 4b = 2^13개 -> 13 bits
   • lv-1 pages: 10 | lv-2 pages:13 | lv-3 pages: 13 | lv-4 pages: 13 | page offset: 15 = 64 bits
   • 4개 level이 필요
2. 페이지 테이블을 저장하기 위해 필요한 최대 페이지 수
   • 1 + (2^10) + (2^10 x 2^13) + (2^10 x 2^13 x 2^13)
3. 메모리 액세스는 5번 필요

Virtual Memory

• os의 목표: 물리 메모리가 부족한 상황에도 프로세스가 실행될 수 있도록 만들기
  • 하나의 프로세스가 거대한 메모리 공간을 차지하는 상황
  • 여러 프로세스가 전체 메모리를 차지한 상황
• user code는 물리 메모리 공간과 독립적이어야 한다
• virtual memory: 더 많은 메모리가 있는 것처럼 속이기

• 프로그램을 가상 메모리에 올림 (다 올라간 척 한다)
• 프로그램 코드의 실제 사용하는 라이브러리만 물리 메모리에 올린다.
• 페이징 시 물리 메모리에 존재하지 않는 부분은 프로그램이 존재하는 저장장치 주소를 저장
  • present bit으로 이를 표시
  • miss -> page fault (OS가 trap 된다)
• 프로세스를 실행하다 물리 메모리에 올라오지 않은 라이브러리에 액세스한다
  • 이 시점에 물리 메모리에 해당 라이브러리를 올린다
  • 공간이 부족하면 Replacement
    • LRU

Virtual Memory Mechanism

• HW/OS가 주소 번역을 위해 작동
• HW가 vaddr를 TLB에서 탐색
• TLB Hit
  • page in phys mem
• TLB Miss
  • HW/OS가 페이지 테이블 탐색
  • page가 present => page in phys mem (가져온다)
• page fault (present bit = 0)
  • trap into OS (복잡해서 HW로는 제어하지 않음)
  • OS가 Victim Page 선정 후 교체
    • dirty bit이 설정되었으면 디스크에 쓰고 교체
    • 이를 기다리지 않기 위해 write buffer에 담아준다
  • OS가 reference된 페이지를 디스크에서 읽어온다
  • 페이지 테이블 업데이트 되고 present bit = 1
  • 프로세스가 다시 실행된다
    • 이 과정이 좀 복잡하다
    • page fault가 사용자에게 드러나지 않도록 한다
    • page fault는 명령어 실행 도중에 발생할 수 있다
      • Inst Fetch나 Data Load/Store 도중 발생
    • 하드웨어의 지원이 필요하다

        - 정확한 interrupt: page fault가 발생하기 전의 명령어는 끝까지 실행
        - fault 유발 이후 명령어는 page fault 이후 재실행

Demand Paging

• swapping 기능을 갖춘 페이징 시스템;
  • 모든 프로세스를 메모리로 swap하는 대신 필요한 페이지만 swap 하는 방식
  • lazy swapper라고 한다
  • pager라고도 한다
• Pure Demanding Paging
  • 극단적인 경우 프로그램 실행 시 어떤 페이지도 메모리에 올라가지 않을 수 있다
  • 이 사례를 pure demand paging이라고 한다
• 이점
  • I/O와 Memory가 적게 필요하다
  • 반응 속도가 빠르다
  • 사용자에게 더 친절
• 과정
  • 페이지가 필요 -> 참조한다
  • invalid 참조 -> abort; 메모리에 없으면 메모리로 가져온다

Valid-Invalid Bit = Present Bit (Valid Bit이랑 다른 거임 왜 이렇게 지은 거임 이름)

• 1: in-memory, 0: not-in-memory
• 0이면 참조 시 trap 걸리면서 page fault handler로 디스크에서 값 가져온다
  • valid bit이 0이면 정말 없는 거니까 abort
  • 아니면 디스크에서 가져오기

Performance of Demand Paging

• page fault rage: 0 <= p <= 1.0
  • 0는 page fault 없음, 1은 매번 page fault 발생
• Effective Access Time (EAT)
  • EAT = (1 - p) x mem access time + p x (page fault overhead + [swap page out] + swap page in + restart overhead)
• example 1:
  • mem acc time: 1 usec
  • 50% of page: dirty
  • swap page time = 10 msec = 10000 usec
  • restart overhead: 0
  • EAT = (1-p) x 1 + p x [swap-out(0.5 x 10000) + swap-in(1 x 10000)] = 1 + 14999p usec
• example 2:
  • mem acc time = 200 ns
  • avg page-fault service time = 8 ms
    • swap in and out + restart overhead
  • EAT = (1-p) x 200 + p x 8000000 = 200 + 7999800 p
  • p = 0.001이어도 8.1998 usec
  • 40배 정도 느려짐

Virtual Memory Policies

• page fault 수 줄이기
  • 디스크 읽기는 수 ms 사용
• OS는 두 가지 선택지가 있다
  • page selection
    • 언제 페이지를 메모리로 가지고 올 것인가?
  • page replacement
    • 어떤 페이지를 메모리에서 내보낼 것인가?

Page Selection

• Demand Paging: 페이지를 page fault에만 가져온다
  • 페이지가 메모리에 필요할 때까지 기다린다
  • 프로세스가 시작될 때 어떤 페이지도 메모리에 로드되지 않는다
  • 매번 새로운 페이지를 접근할 때마다 page fault 비용이 발생한다
• Prepaging: 페이지가 참조되기 전에 가져온다
  • OS가 이후 접근할 페이지를 예측하고 메모리에 먼저 가져온다
  • 몇몇 접근 패턴에 대해 유효 (sequential)
  • Unix의 madvise()와 같이 사용자가 OS에 힌트를 제공할 수 있음

Page Replacement

• 더이상 빈 페이지 프레임이 없는 경우 교체를 해야 한다
• 메모리에 있지만 사용되지 않는 페이지를 찾아 swap out 한다
• 선택된 페이지가 dirty bit 설정된 상태라면 디스크에 써준다

Page Replacement Steps

1. 디스크에서 가져올 페이지의 위치를 찾는다
2. 빈 프레임을 찾는다:
   1. 빈 프레임이 존재하면 그걸 사용한다
   2. 빈 프레임이 없다면 page replacement algorithm을 사용하여 victim frame을 선정한다
3. 빈 프레임에 요청 페이지를 읽어온다. 페이지와 프레임 테이블을 업데이트 한다.
4. 프로세스를 다시 시작한다.

Page Replacement Algorithm

• FIFO:
  • 처음 들어온 페이지를 먼저 내보낸다
  • 모든 페이지가 같은 중요도를 가진다, 구현이 쉬움 (circular buffer)
  • 몇몇 페이지는 지속적으로 사용될 가능성이 있음
  • 페이지 수를 늘렸더니 오히려 성능이 줄어드는 경우가 있음
    

    

• OPT:
  • 더이상 사용되지 않을 페이지를 완벽히 예측
  • 최소한의 page fault만 발생하는 이상적인 경우
  • 실제 상황에서 적용이 불가능하며, 측정을 위한 매트릭이 된다
    

    

• LRU:
  • 최근에 사용되지 않은 페이지를 선정
  • locality가 받침되면 OPT와 비슷한 성능
  • 구현이 어렵고, 어떤 페이지를 접근했는지 추적해야 한다
  • 모든 workload에서 잘 작동하는 건 아님
  • LRU는 접근 빈도는 고려하지 않음
    • LFU

Counting-Based Algorithm

• 카운터를 이용하여 각 페이지의 참조 횟수를 저장함
• Least Frequently Used(LFU)
  • 가장 count가 작은 페이지를 교체
  • 이후에도 쓰이지 않을 거라는 계산
• Most Frequently Used(MFU)
  • 앞으로 사용할 횟수까지 다 썼다는 계산

LRU Implementation

• counter implementation
  • 모든 페이지 테이블 엔트리가 카운터를 가지고, 매번 페이지가 참조될 때마다 clock을 복사해온다.
  • counter를 비교해서 가장 작은 값을 갖는 페이지를 바꾼다
  • 업데이트에는 부담 적음, 교체 시 모두 비교가 부담
    

    

• stack implementation
  • 페이지 넘버 스택을 doubly linked list 형태로 가진다
  • 페이지가 불릴 때마다 해당 참조된 페이지를 top으로 올린다
  • bottom을 제거한다
  • 업데이트에 부담, 교체에는 비용이 없음

LRU Approximation Algorithm

• reference bit algorithm
  • 각 페이지는 reference bit을 갖는다 (최초 0)
  • 페이지가 참조되면 reference bit을 1로 바꾼다 (하드웨어 이용)
  • ref bit이 0인 페이지를 제거한다
  • 정확한 순서는 모르지만 참조 되었는지는 확인할 수 있다
    

    

• additional reference bits algorithm (Reference Byte Algorithm)
  • reference bit을 멀티 비트로 확장한다.
  • 주기적으로 reference byte를 shift right한다. (MSB는 ref 시 1)
  • 이러한 8비트 쉬프트 레지스터는 지난 8번의 기록 동안 페이지 사용량을 나타내는 값이 된다
  • page fault 발생 시 8bit 값을 unsigned int로 비교하여 가장 작은 값을 갖는 LRU 페이지를 방출
    

    

    
    

    

• Second Changce (Clock) Algorithm
  • circular list를 사용하여 메모리에 로드된 페이지 관리
  • ref bit = 1 when loaded
  • value = 0 -> replace
  • value = 1 -> make it 0
  • victim pointer는 순차적으로 돈다 (like FIFO)
• Enhanced Second Chance Algorithm
  • reference bit과 modify bit을 모두 고려
  • 4개의 경우
    • (0, 0): no ref, no modified => best
    • (0, 1): no ref, but modified
    • (1, 0): ref, no modified
    • (1, 1): ref, modified
  • 페이지를 교체해야 할 경우 각 페이지가 어느 경우에 속하는지 파악하고 가장 먼저 마주친 첫 번째 페이지를 교체한다
  • circular queue를 여러 번 탐색해야 할 경우
    • case 1 -> 없네 -> case 2 -> 없네 -> ...

Allocation of Frames

• 고정된 크기의 free memory를 프로세스 어디에 할당해야 하는가?
  • 가능한 프레임의 수보다 많이 할당할 수는 없다
  • 반드시 최소 프레임 수보다는 많이 할당해야 한다
• 각 프로세스는 최소 페이지 수가 있다
  • Instruction Set Architecture에 정해져 있음
  • 명령어가 참조하는 모든 페이지를 담기 위해 충분한 프레임이 필요함
  • ex 1: 1-lv load 10은 2 프레임 필요
    • 명령어(code) 담길 메모리 1 프레임
    • 메모리 참조용 메모리 1 프레임
  • ex 2-1: 1-lv indirect addressing (load 10)은 3 프레임 필요
    • 10에 담고 있는 값을 load
    • load: 1, 10: 1, ref: 1
  • ex 2: PDP-11은 MV from, to 명령어를 제어하기 위해 6 프레임 필요
    • 명령어가 6바이트, 2 페이지로 확장 가능
    • from 제어를 위한 2 페이지
    • to 제어를 위한 2 페이지
• 두 개의 자주 사용되는 방식 - 동일 / 비례

Frame Allocation Algorithm

• Equal Allocation: 100 frames and 5 processes = 20개씩 할당
• Proportional Allocation: 프로세스 크기에 따라 할당
  • s_i: size of process p_i
  • S: 전체 프로세스의 크기
  • m: total num of frames
  • a_i: allocation for p_i = s_i / S * m
• 예시
  • m = 64
  • s_1 = 10
  • s_2 = 127
  • a_1 = 10 / 137 * 64 = 5
  • a_2 = 127 / 137 * 64 = 59
• MP(Multi Programming) level에 따라 각 프로세스의 할당 비율은 달라질 수 있다
  • MP level이 증가하면 각 프로세스는 몇 프레임 씩 모아 새로운 프로세스의 최소 프레임 수를 맞춰준다
  • MP level 감소하면 각 프로세스는 프레임 수 증가한다
  • Priority Allocation: proportional alloc scheme이 사이즈 대신 priority를 사용하여 비례적으로 프레임 할당

Global vs Local Replacement

• process p_i가 page fault 발생
  • 해당 프레임에서 교체할 것 찾음
  • 더 낮은 우선 순위를 가진 프로세스에서 교체할 것을 찾음
• Local Replacement
  • 각 프로세스는 자신이 현재 가장 사용되지 않는 프레임을 교체한다
• Global Replacement
  • 모든 프로세스의 프레임 중 하나 선택하여 교체
  • 자신의 page fault rate를 컨트롤 하기 힘들다 (다른 프로세스의 영향으로)
  • throughput이 나아진다
  • 일반적인 방식

Thrashing

• thrashing은 프로세스가 실제 실행보다 더많은 시간을 swap-in/out에 사용하는 것을 말함
• 초기 페이징 시스템에서, 페이지가 충분하지 않아 page-fault가 매우 자주 발생하던 상황
  • CPU 사용률 낮아진
  • OS가 멀티 프로그래밍