가상 메모리

Demand Paging

•

프로그램이 실행될 때 그 프로세스를 구성하는 주소공간의 페이지를 전부 메모리를 한꺼번에 올리는 게 아니라 demand paging 기법을 사용

•

요청이 됐을 때 메모리에 올린다.

•

IO 양의 감소

◦

프로그램을 구성하는 주소공간 중에서 실제로 빈번히 사용되는 부분은 지극히 제한적

◦

좋은 소프트웨어일수록 방어적인 코드가 대부분

◦

이런 방어적인 코드를 한번에 올리면 메모리 낭비

•

물리 메모리 사용량 감소

•

빠른 응답 시간

•

더 많은 프로그램 수용 가능

•

우측의 원통은 디스크(swap area)

•

valid/invalid bit 의 사용

◦

invalid

▪

사용되지 않는 주소 영역

▪

페이지가 물리적 메모리에 없는 경우

◦

처음에는 모든 page entry 가 invalid 로 초기화

◦

address translation 시 invalid bit 이 set 되어있으면 page fault

•

예시

◦

1번 페이지에 접근하려고 보니 page table 에서 invalid bit 이다. 그러면 이 페이지가 메모리에 없다는 뜻

◦

디스크에서 메모리로 올린다. → IO 작업 → 사용자 프로세스가 직접 못하는 일

◦

page fault

◦

그러면 CPU 는 운영 체제에 넘어간다.

◦

운영 체제는 fault 난 페이지를 메모리에 올린다.

page fault

•

invalid page 를 접근하면 MMU가 trap 을 발생시킴

•

kernel mode 로 들어가서 page fault handler 가 invoke 됨

•

page fault 처리 루틴

invalid reference 인지 확인(bad address, protection violation) → process 를 abort 한다.

비어있는 page frame 을 가져오고 빈 페이지가 없으면 쫓아내고 뺏어온다.

해당 페이지를 disk 에서 memory 로 읽어온다.

disk IO 가 끝나기까지 이 프로세스는 CPU 를 선점당함(block)

disk read 가 끝나면 page table entry 를 기록하고 valid 로 바꾼다.

ready queue 에 process 를 insert 한다.

•

emtry frame 이 없는 경우 page replacement 를 해야하고 replacement algorithm 으로 page fault rate 을 최소화한다.

Replace Algorithm

optimal algorithm

•

가장 먼 미래에 참조되는 page 를 replace

•

어떤 페이지가 참조될 지 안다는 가정이 있어야 한다.

•

그래서 실제로 적용하지는 못한다.

•

실제 시스템에서 사용하는 다른 알고리즘 성능에 대한 upper bound 를 제공한다.

FIFO algorithm

•

가장 먼저 들어온 것을 replace

•

메모리 크기를 늘리는데 성능이 나빠지는(fault 를 더 많이 냄) 특이점이 있다.

Least Recently Used algorithm

•

가장 오래 전에 참조된 것을 replace

Least Frequently Used algorithm

•

참조 횟수가 가장 적은 페이지를 replace

•

최저 참조 횟수가 여러개인 경우

◦

LUF 자체에서는 임의로 선정

◦

성능 향상을 위해 여러 페이지 중 PRU 알고리즘 구현 가능

•

장단점

◦

장기적인 시간 규모를 보기 때문에 page 의 인기도 반영

◦

최근성 반영 불가

◦

LRU 보다 구현이 복잡

LRU vs LFU

LRU 는 리스트로 구현한 경우 시간 복잡도가 O(1)

LFU 는 리스트로 구현하면 O(N) 시간 복잡도

LFU 를 힙으로 구현하면 O(logN)

CPU가 요청한 페이지 순서

1,1,1,1,2,2,3,3,2,4,5

•

LRU 는 가장 오래 전에 참조한 페이지를 삭제 - 1번 페이지(도둑질 예시)

•

LFU 는 가장 참조 횟수가 적은 페이지를 삭제 - 4번 페이지(도서관 책 대출 예시)

◦

간과하는 것은 시간에 따른 예측이 부족

다양한 캐싱 환경

•

캐싱 기법

◦

한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식

◦

paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용

•

캐시 운영의 시간 제약

◦

교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음 

•

사실 LRU, LFU 는 가상 메모리 페이징 기법에서 사용할 수 없다.

◦

LRU, LFU 등 이전 참조 내용을 저장하려면 해당 알고리즘 로직이 수행되어야 하는데, page 가 이미 메모리에 있는 경우에는 OS 가 CPU 제어권을 얻지 못해 해당 알고리즘 로직 수행을 할 수가 없다.

Clock algorithm

•

LRU 근사(approximation) 알고리즘

•

second chance algorithm, Not Used Recently 또는 Not Recently Used 등으로 불림

•

reference bit 을 사용한다. 페이지 참조가 발생하면 하드웨어에서 해당 페이지의 reference bit 을 1로 바꾼다.

•

0 의 의미는 시계 바늘이 한바퀴 도는 동안 참조가 없었다.

•

1 은 최소 한 번 참조가 있었다. 그래서 OS 가 내쫓을 페이지 찾을 때 1이면 0으로 바꾸고 다음으로 넘어감

•

modified bit(dirty bit) 을 함께 사용해서 참조 이외에도 변경 페이지에 대해서도 기록 저장

page frame allocation

•

각 프로세스에 얼마만큼의 page frame 을 할당할 것인가?

•

allocation 의 필요성

◦

메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시에 참조

◦

명령어 수행을 위해 최소한 할당되어야 하는 frame 의 수가 있음

◦

loop 를 구성하는 page 들은 한꺼번에 allocate 되어야 함

◦

최소한의 allocation 이 없으면 매 loop 마다 page fault

•

equal allocation: 모든 프로세스에 똑같은 갯수 할당

•

proportional allocation: 프로세스 크기에 비례하여 할당

•

priority allocation: 프로세스의 priority 에 따라 다르게 할당

global replacement

•

replace 시 다른 process 에 할당된 frame 을 빼앗을 수 있다.

•

process 별 할당량 조절 가능

•

working set, PFF 알고리즘

local replacement

•

자신에게 할당된 frame 내에서만 replacement

가상 메모리

Demand Paging

page fault

Replace Algorithm

optimal algorithm

FIFO algorithm

Least Recently Used algorithm

Least Frequently Used algorithm

LRU vs LFU

다양한 캐싱 환경

Clock algorithm

page frame allocation

global replacement

local replacement

Thrashing