10. 요구 페이징, 페이지 교체, 페이지 교체 알고리즘

발표자: 박광수

요구 페이징(Demand Paging)

  • 요구되는(현재 필요한) 페이지만 메모리 상에 올려주는 것

Page table : 현재 읽으려는 페이지가 어디에 있는 지를 저장함

  • Valid bit (실제 적재 되어있는지를 체크하는 비트)

Page fault

페이지가 메모리에 올려지지 않은 상태. (페이지 부재)

page fault 발생 시 CPU에 interrupt 발생 → OS가 인터럽트 처리 루틴 실행 → 페이지 올림

→ Valid 상태로 바뀜 → 다시 페이지 읽음

유효 접근 시간

메모리의 영역이 얼마나 빠르게 읽혀 지는가 를 평균 낸 것

페이지 폴트 일어날 확률 (P : page fault rate)

  1. 페이지 폴트 없을 때 걸리는 시간 (Tm) - DRAM 200nsec

  2. 페이지 폴트 시 걸리는 시간 (p) - Seek time >> + rotational Delay + transfer time 8msec

주로 시간은 페이지 폴트 발생 시 걸림(HDD reading).

  • 페이지 폴트 발생은 매우 오래 걸리므로 최소화 하는게 좋음 (SSD는 상대적으로 빠름)

지역성 (Locality of Reference)

  • 메모리 접근은 시간, 공간적 지역성을 가짐

    • 실제 cpu는 비슷한 공간, 시간에서 읽을 가능성이 높다는 뜻.

  • 실제 페이지 부재 확률은 매우 낮음

    • Block 단위로 가져올 수 있기 때문 (필요한 수행에 대해)

다른방법

  • HHD 보다는 SSD 혹은 저가 DRAM 사용 : 발생 시 시간 최소화

페이지 교체 (Page Replacememt)

여러 프로그램 실행 시 요구 페이지가 가득 차게 됨

  • P1, P2, P3 동시 실행 P4가 들어갈 자리 없음

    1. Backing store로 하나 몰아냄 (Page Out) → Victim Page

    2. P4 적재 (Page In)

Victim Page : 어떤 페이지를 몰아낼 것인가?

ㄴ 내용을 HDD에 기록해야 하나?

ㄴ변경이 되지 않을 명령문은 Write 필요 없음

ㄴ CPU의 연산에 의해 바뀌면 Write

  • 가능하면 Write 안된 것을 빼는 것이 좋음 (I/O 시간 절약)

  • 1bit 추가 → modified bit ( V + M ) = dirty bit

  • 이 중 누가 Victim 일까?

    • Random

    • First in First Out (FIFO)

    → 페이지 교체 알고리즘

Page Reference String

  • (page num / displacement) → main memory 주소 (page)

    • EX) page 100byte → 1페이지 : 100~199 가져옴

    • CPU 주소 100 101 102 432 612 103 104 611 612…

      페이지 : 1 1 1 4 6 1 1 6 6

      prs : 1 4 6 1 6

      페이지 번호 중 연속되는 것을 지워 만들어진 열

페이지 교체 알고리즘

1.FIFO

메모리에 먼저 올라온 것을 Victim으로 삼음

이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록 하거나, 페이지가 올라온 순서를 큐(Queue)에 저장 하는 방식 등을 사용

장점

  • 가장 간편한 방법

  • 대부분 초기화 목적인 것들 (1번 실행) 이 있음

    ㄴ 이 후에 잘 쓰이지 않을 것이라 예상.

단점

  • 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험 있음 (Belady’s Anomoly)

2.OPT(Optimal)

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체

  • 가장 이상적인 알고리즘

  • 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다 (불가능 한 조건)

3. LRU(Least-Recentely Used)

가장 오래 사용되지 않은 페이지를 교체

장점

  • 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법

  • LRU 알고리즘은 많은 운영체제가 채택하는 알고리즘이며, 좋은 알고리즘이라고 평가

단점

  • 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생

Replacement 방식

Global replacement

  • 메모리 상의 모든 프로세스에서 Victim을 선택

Local replacement

  • 페이지가 요구되는 프로세스에서 Victim을 선택

- 메모리 사용 효율측면에서는 일반적으로 Global Replacement가 효율적임

계수-기반(Counting-Based) 페이지 교체

페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅

LFU(least-frequently-used)

참조 횟수가 가장 작은 페이지를 교체하는 알고리즘이다. 만약 교체 대상인 페이지가 여러 개 일 경우, LRU 알고 리즘을 따라 가장 오래 사용되지 않은 페이지로 교체한다.

LFU 알고리즘은 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있다. 앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문이다. 아래의 그림의 그 예시다.

초기에만 쓰인 7이 메모리에 잔존해 낭비가 일어난다

MFU(most-frequently-used)

LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다. 참조 횟수가 적은 페이지가 최 근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단이다.

LFU와 MFU는 실제 사용에 잘 쓰이지 않는다.

  • 구현에 상당한 비용이 들고,

  • 최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문이다.

프레임 할당

CPU utilization VS degree of multiprogramming

  • 프로세스 갯수가 많아질 수록 CPU 성능이 떨어지는 이유

Demand Paging 에 따른 저하가 발생

Threshing : I/O 시간 증가 → CPU 활동 멈춤(요구페이징 기간동안)

  • Threshing 은 Local replacement가 좋을 수 있음

  • 프로세스당 적절한 수의 메모리 할당 (프레임 할당)

    • 적절한 것은??

      정적인 방법 : 처음부터 프로세스 크기에 맞춰 할당

      equal allocation - 동일 할당 (1 : 1: 1)

      proportional allocation - 프로세스 크기에 따라 적절한 비율로 할당 (5:2:3)

      • 정적인 방식은 잘 사용하지 않는

      동적인 방법

      Working set model : 시간에 따라 주로 참조하는 페이지를 계산

      Page-Fault Frequency(PFF) : Page fault인 페이지 결함의 발생 비율을 측정하여 프레임을 할당

Previous9. 페이징, 세그멘테이션, 가상메모리Next11. 프레임 할당, 파일 할당

Last updated