[OS] Virtual Memory

여기서부터는 전 챕터의 Paging기법을 사용한다고 가정한다 (실제로도 그럼)

Demand Paging

■  Demand Paging

ㅡ> 프로세스의 페이지를 전부 메모리에 올리는게 아니라

ㅡ> 그 페이지가 요청됐을 때만 메모리에 올림

 

■ 

프로그램은 별에 별 상황에도 이상한 동작을 하지 않도록

방어적으로 만들기 때문에,

실제로는 거의 사용되지 않는 코드가 많다

그래서 메모리에 다 올리면 공간이 낭비된다

■ valid

ㅡ> 물리적 메모리에 올라 와 있는 경우

 

■  invalid

ㅡ> 물리적 메모리에 없고 swap area에 내려가있는 경우

 

■  G,H

ㅡ> 사용하지 않는 주소 영역

ㅡ> 테이블에서도 invalid

Page Fault

■ MMU

ㅡ> 주소 변환을 하는 하드웨어

 

■ Page Fault

ㅡ> 주소 요청을 했는데, 테이블에서 invalid로 되어있는 경우

ㅡ> MMU가 page fault trap을 건다

ㅡ> OS가 그 페이지를 swap area에서 물리적 메모리에 올리는 작업을 한다

 

■ Page Fault Handler

1. 잘못된 참조 확인 ㅡ> abort시킴

2. 빈 프레임 확보 ㅡ> 없으면 기존 페이지를 쫓아냄 (LRU, FIFO등 정책대로)

3. 디스크에서 메모리로 페이지 로드

▶ DISK I/O 하는동안 CPU 반납, 작업 끝나면 프로세스를 ready queue에 삽입

Demand Paging 성능

p = page falut 확률

 

 

• OS & HW Page Fault Overhead (페이지 폴트 핸들링 비용)
• [Swap out if needed] (기존 페이지를 스왑 아웃해야 할 경우)
• Swap in (디스크에서 새로운 페이지를 로드)
• OS & HW Restart Overhead (새로운 페이지가 로드된 후 재실행 비용)

 

Free Frame이 없는 경우

■ Reference String

ㅡ> 페이지가 참조된 순서

Page Replacement 

■ victim

ㅡ> 메모리에서 쫓겨날 희생양

 

■ OS가 하는 일

1. victim을 swap out

2. victim을 table에서 invalid로 변경

3. 필요한 페이지 swap it

4. 올린 페이지의 프레임 번호를 테이블에 적고 valid로 변경

알고리즘

Optimal Algorithm

■ 여기서는 미래에 참조되는 페이지를 미리 다 안다고 가정

ㅡ> 실제 시스템에선 미래를 몰라서, 이것을 offline algorithm이라고 부름

ㅡ> 성능의 상한선을 알아내기 위함

 

■ 작동 방식

ㅡ> 가장 먼 미래에 참조되는 페이지를 쫓아낸다

FIFO

■ FIFO

ㅡ> First In First Out

ㅡ> 먼저 들어온 것을 쫓아냄

 

■ 특이한 점

ㅡ> 보통 프레임 수를 늘리면 성능이 좋아져아 함

ㅡ> 근데 FIFO는 성능이 나빠지기도 함

LRU

■ LRU

ㅡ> Least Recently Used

ㅡ> 가장 오래전에 사용한 것을 쫓아냄

LFU

■ LFU

ㅡ> Least Frequently Used

ㅡ> 참조 횟수가 가장 적은 것을 쫓아냄

 

■ 참조 횟수가 동일한 경우

ㅡ> 성능 향상을 위해, 가장 오래 전에 참조된 page를 쫓아내게 구현할 수도 있다

LRU vs LFU

예제

구현

■ LRU

ㅡ> replacement가 필요할 때마다 페이지의 참조시간을 탐색해서 비교하면 엄청 느리다

ㅡ> 페이지가 참조될 때, 그것을 리스트의 가장 아래에 매달고(doubly linked list) , replacement가 필요할 때 가장 위의 것을 쫓아내는 방식이 빠르다 

ㅡ> 시간복잡도 O(1)

 

■ LFU

ㅡ> 리스트로 구현하면 O(n)

ㅡ> 참조횟수가 늘어나면, 밑에것과 비교해서 밑으로 내리는데, 참조횟수가 다 동일하면 맨 밑까지 비교하며 내려가는 경우도 있기 때문

ㅡ> heap으로 구현하면 O(log n)

ㅡ> 완전이진트리로 하면 높이가 log n이기 때문

다양한 캐슁 환경

■ 

replacement 알고리즘은 버추얼 메모리에만 쓰이는게 아니다

캐슁 기법을 쓰는 여러 환경에서 쓰인다

 

■  캐슁 기법

ㅡ> 한정된 빠른 공간에 자주 쓰이는 데이터를 올려서 성능을 최적화

 

■  시간 제약

ㅡ> 어떤 것을 쫓아낼지 결정하는데 너무 오랜시간을 쓰면 안된다

ㅡ> O(1) ~ O(log n)정도 까지만 허용

Paging System에서 LRU, LFU 가능한가? 

■ 페이징 시스템

메모리에 있는것이 참조될 때는 OS를 부르지 않고 

Page Fault가 발생할 때만 OS를 부르기 때문에

OS는 참조횟수를 알 수가 없다

그래서 위에서 말한 LRU LFU 알고리즘을 사용할 수 없다

ㅡ> 대신 Clock 알고리즘 사용

ㅡ> LRU 알고리즘을 근사시킨 알고리즘

Clock Algorithm

<여러가지 이름으로 불린다>

■ Second chance algorithm

ㅡ> 기회를 한번 더 준다는 뜻

■ clock algorithm

ㅡ> 시계처럼 운영된다는 뜻

■ NRU

ㅡ> 최근에 사용되지 않은 것을 쫓아 낸다는 뜻

■ 사각형

ㅡ> 페이지 프레임을 의미

 

■ reference bit

ㅡ> 페이지에 reference bit가 붙어있다

ㅡ> cpu가 페이지를 읽어오면 하드웨어가 그 페이지의 reference bit를 1로 세팅한다

 

■

페이지 replacement가 필요할 때

OS가 이 reference bit를 참고해서, 1이면 0으로 바꾸고 시계방향으로 다음것을 참조한다

0이 나올때까지 시계방향으로 진행한다

0이 나오면 그 페이지를 쫓아낸다

 

■ 근사 LRU

가장 오래된걸 쫓아내지는 못하지만

시계가 한바퀴 도는동안 참조되지 않은걸 좇아내서 비슷한 효과를 낸다

 

■ modified bit (dirty bit)

ㅡ> 그 페이지가 메모리에 있는동안 write가 되었으면 1로 세팅

ㅡ> 그 페이지를 쫓아낼때, modified bit가 0이면 그냥 내린다

ㅡ> 1이면 backing store에 수정된 내용을 반영한 뒤에 내린다

ㅡ> clock 알고리즘을 쓸때 modified bit가 0인거 위주로 내리면 더 빠르다

Page Frame의 Allocation

■

프로그램이 Page Fault 안내고 원활하게 실행되려면

일련의 페이지들이 같이 메모리에 올라와 있어야 한다.

그렇다고 한 프로그램의 페이지만 올라와도 비효율적이다.

 

■ 할당계획

ㅡ> Equal allocation : 누구는 많이 필요하고 누구는 적게 필요할 수 있어서 비효율일 수 있다

ㅡ> Propertional allocation : 같은 프로그램이어도 시간에 따라 필요로 하는 페이지 갯수가 다를 수 있어서 비효율일 수 있다

ㅡ> Priority allocation 

 

■ 미리 할당x

ㅡ>global replacement 알고리즘을 쓰다보면, 저절로 프로세스별 할달량이 조절이 되기도 한다

Global VS Local Replacement

■ Global

ㅡ> 다른 프로세스의 프레임 뺏어가며 replace

 

■ Local

ㅡ> 프로세스가 자기 프레임들 내에서 replace

[문제] Thrasing

■ Thrashing

ㅡ> Page fault 가 매우 빈번하게 발생하는 상황

실행 프로세스 갯수당 CPU 사용률 그래프

일반적으로 프로세스가 늘면 CPU도 많이 사용

 

임계점을 넘으면 Page Fault가 빈번해져서 CPU 사용률 급격히 하락 (thrashing)

 

해결책

ㅡ> Working Set 알고리즘

ㅡ> PFF

[해결] Global Replacement

Working-Set Model

■ locality set

ㅡ> 메모리에 올라와있어야 하는, 빈번히 이용되는 부분

 

■ working-set Model

ㅡ> working set = locality set

ㅡ> working set 전체를 한번에 메모리에 올릴 수 없다면, 일부라도 올리는게 아니라 전체를 swap out 해버린다

Working-Set Algorithm

■ window size

ㅡ> 델타시간

ㅡ> 이 시간동안 사용된 페이지를 working set으로 판단한다

PFF Scheme

■ PFF 

ㅡ> Page-Fault Frequency Scheme

 

■ Page-Fault rate를 본다

ㅡ> 상한선을 넘으면 frame 할당 ▶ 메모리 부족하면 프로세스 전체를 swap out

ㅡ> 하한선보다 내려가면 frame 뺏음

Page Size의 결정

Page size 감소시키면

ㅡ> 페이지 수 증가

ㅡ> 페이지 테이블 크기 증가

ㅡ> 내부조각 감소

ㅡ> 디스크 헤더가 왔다갔다 더 자주해서 효율성 감소

ㅡ> 꼭 필요한 부분만 올릴 수 있음

 

트랜드

ㅡ> page size 키움