공부하는 개발 블로그

가상 메모리: 각 프로세스는 0번지에서 시작하는 고유의 주소 공간을 가짐.

8.1 요구 페이징

당장 사용할 페이지만 메모리에 올림.

입출력 시간이 단축 -> 응답시간 단축. 더 많은 프로세스 처리.

적은 메모리 필요.

페이지 부재(page fault): 페이지가 메모리에 없다.

1) page fault 처리

(1) MMU(Memory Management Unit)이 page fault trap 발생

(2) CPU으 제어권이 커널모드로 전환. page fault 처리 루틴 호출

(3) 페이지에 대한 접근이 적법한지 체크: 사용되지 않는 주소 영역? 접근 권한이 있는가?

(4) 물리 프레임에서 비어있는 프레임을 할당받아 메모리를 읽어옴

(5) 빈 프레임 없으면 swap out and swap in. 디스크 작업은 오래 걸리므로 page fault가 발생한 프로세스는 CPU를 빼앗기고 봉쇄 상태가 됨. PCB에 CPU 레지스터 상태 및 프로그램 카운터 값 저장.

(6) 디스크 입출력 완료 -> 인터럽트 -> 유효 비트로 설정 -> 봉쇄된 프로세스를 준비큐로 이동.

2) 요구 페이징의 성능

page fault의 발생 빈도에 따라 성능이 결정됨.

EAT(effective access time):

p는 page fulat rate

(1-p) * 메모리 접근 시간 + p*(page fualt 처리 오버헤드 + swap out 오버헤드 + swap in 오버헤드 + 프로세스 재시작 오버헤드)

8.2. 페이지 교체

page fault율을 최소화하는 알고리즘이 목표

1) 빌레디의 오프라인 최적 알고리즘

가장 먼 미래에 참조되는 페이지를 swap out.

페이지가 참조되는 순서를 알고 있다는 가정. 이론적. 알고리즘 성능의 상하선 제공.

2) FIFO

가장 먼저 올라왔던 페이지를 먼저 swap out.

FIFO 이상현상(FIFO anomal): 메모리를 증가시켰음에도 오히려 page fault 증가

3) LRU(Least Recently Used)

시간 지역성(temporal locality) 이용.

가장 오래 전에 참조가 이루어진 페이지를 swap out.

4) LFU(Least Frequently Used)

페이지 참조 횟수가 가장 적은 페이지 swap out.

Incache-LFU: 페이지가 물리 메모리에 올라온 순간부터 1. swap out-in 되면 1부터 다시 시작.

Perfect-LFU: 누적 참조 횟수.

참조 횟수를 저장하는 오버헤드

5) clock algorithm(=second chance algorithm, NUR, NRU: Not Used Recently)

LRU를 근사한 알고리즘.

오랫동안 참조되지 않은 페이지 중 하나 swap out.

하드웨어 지원으로 동작 -> 빠름. 대부분 사용

페이지가 참조될때마다 참조 비트 1로 set

참조비트가 1인 경우 0으로 set.(-> 한 바퀴 돌때까지 0인 페이지를 못 발견한 경우를 위함)

참조 비트가 0인 페이지를 발견하면 교체.

8.3 페이지 프레임의 할당

1)균등 할당

2) 비례 할당(proportional allocation): 프로세스의 크기에 비례하여 할당.

3) 우선순위 할당(priority allocation): 당장 CPU에서 실행될 프로세스에 더 많은 페이지 프레임 할당.

프로세스별로 최소한으로 필요한 메모리 양, 반복문 여부 등을 고려해야 더 효율적

8.4 전역 교체와 지역 교체

전역 교체: 교체 범위가 메모리 전체

지역 교체: 같은 프로세스 안의 페이지 중에서 교체

8.5 스레싱(thrashing)

page fault가 크게 상승해 CPU 이용률이 떨어지는 현상

MPD(Multi-Programming Degree): 메모리에 동시에 올라간 프로세스의 수

MPD가 낮은 경우 CPU는 더 많은 프로세스를 메모리에 올림.

그런데 너무 많은 프로세스가 올라가면, page fault 증가 -> 디스크 I/O : 시스템은 page fault 처리에 분주, CPU 이용률 감소.

=> 운영체제는 메모리 상의 프로세스가 적다고 판단하고 프로세스를 더 올림. -> page fault 더 증가. 악순환

1) 워킹셋 알고리즘(working-set algorithm)

지역성이 있는 집합(locality set)을 메모리에 동시에 올라갈 수 있도록 하는 알고리즘.

working-set: 프로세스가 일정 시간 동안 원할히 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 페이지들의 집합.

working-set의 모든 페이지가 메모리에 올라갈 수 있는 경우에만 적재. 아니면 swap out.

workng-set window: delta

working-set: 시각 t에서 시간간격 [t-delta, t] 사이에 참조된 서로 다른 페이지의 집합. 페이지가 참조된 시점으로부터 delta시간 동안은 메모리에 유지되고, 그 시점이 지나면 swap out.

working-set의 크기의 합이 메모리보다 크면 일부 swap out

working-set window의 크기가 중요.

너무 작으면: 지역성 집합 수용 X

너무 크면: MPD감소 -> CPU 이용률 낮아짐.

working-set의 크기는 시간의 흐름에 따라 변함. 동적 프레임 할당의 기능까지 수행.

2) 페이지 부재 빈도 알고리즘(page-fault frquency algorithm)

프로세스별 page fault 비율을 조사해서,

시스템에서 정한 상한보다 높은 경우, 추가 프레임 할당. 추가할 빈 프레임이 없으면 일부 프로세스 swap out

시스템에서 정한 하한보다 작은 경우, 프레임 수를 줄인다.