지난 챕터에서 물리적 메모리의 주소 변환은 운영체제가 관여하지 않는다고 했는데 가상 메모리는 운영체제가 적극적으로 관여한다.

Demand Paging

Memory에 없는 Page의 Page Table

swap area(디스크)에 내려가 있는 경우에도 invalid bit으로 표시한다.

만약 주소 변환을 하러 갔는데 페이지 테이블에 없다면 "page fault"가 났다고 한다. 이 경우 cpu는 운영체제에게 넘어간다. 운영체제가 그 페이지를 페이지 테이블에 올린다.

Page Fault

Steps in Handling a Page Fault

Performance of Demand Paging

Free Frame이 없는 경우

Page Replacement

만약 메모리가 변경되었다면 쫓아내기전에 디스크에 써줘야 한다.

Optimal Algorithm

실제 시스템에서는 미래를 알기 어려우나, 여기서는 알고 있다고 가정을 한다.
이것보다 적게 page fault를 낼 수는 없다. 다른 알고리즘에 대한 성능의 upper bound를 제공한다.

FIFO (First In First Out) Algorithm

메모리 크기를 늘려줬는데 성능이 더 나빠지는 경우도 발생할 수 있다.

LRU (Least Recentrly Used) Algorithm

실제로 가장 많이 사용된다. 가장 덜 최근에 참조된 것을 쫓아낸다. FIFO와 헷갈리지 않아야하는게 페이지가 재사용되면 다시 최근게 되는거다.

LFU (Least Frequently Used) Algorithm

가장 덜 참조된 것을 쫓아낸다.

LRU와 LFU 알고리즘 예제

LRU 알고리즘 단점은 그 이전의 히스토리는 기억하지 않는다는 것이다. 1번이 LRU에서 쫓겨나지만 가장 많이 참조됐다. LFU는 반대의 단점이 있다.

LRU와 LFU 알고리즘의 구현

중요..!!

LRU는 시간 순서대로 줄세우기를 한다. 제일 위가 가장 오래전에 참조된 것이고, 가장 최근은 제일 밑이다. 만약 새로운 것이 참조되면 가장 밑으로 보내면 된다. 쫓아내야할 때는 가장 위에 것을 쫓아내면된다. 쫓아내는데 O(1)의 시간 복잡도를 보인다.

LFU는 힙으로 구현해야 한다. LRU는 한번만 참조돼도 그 페이지가 왕이다. 무조건 제일 하위에 보내면 되는데 LFU는 횟수 비교를 해야 한다.

다양한 캐슁 환경

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

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

만약 주소 반환을 했는데 해당 페이지가 메모리에 올라와있으면 운영체제가 개입하지 않고 그냥 가져온다. 만약 page fault가 나면 제어권이 운영체제에게 넘어가서 메모리에 올려놓는다.

운영체제는 가장 오래전에 참조된, 혹은 가장 덜 참조된 것을 정확히 모른다. 메모리에 있는 것은 cpu가 바로 가져오기 때문이다. 따라서 운영 시스템에서는 부적절한 알고리즘이다. web caching 등에서는 사용할 수 있다.

Clock Algorithm

LRU, LFU가 부적절하기 때문에 clock algorithm을 사용한다.

페이지가 참조가되면 reference bit을 1로 만들어준다. 1인 것은 0으로 만들어준다.

reference bit이 0이라는 것은 시계가 한바퀴 도는동안 참조가 없었다는 뜻이다. 한바퀴가 돌면서 참조가 안된 것을 쫓아낸다.

개선된 것은 modified bit(dirty bit)인데 변경되어으면 디스크에 쓰고 쫓아낸다. modified bit이 0이면 그냥 디스크에 안쓰고 바로 쫓아내면 된다.

Page Frame의 Allocation

프로그램마다 최소한의 페이지를 줘야 page fault가 덜난다.

Global vs. Local Replacement

Thrashing

Thrashing Diagram

프로그램마다 필요한 최소 메모리를 할당 받지 못해 cpu가 일하기보다 io에 시간을 더 많이 쓰게된다.

Working-Set Model

특정 시간에 집중적으로 사용되는 page들의 집합은 적어도 메모리에 한꺼번에 올라와이썽야 thrashing이 덜 일어난다. 만약 최소 양을 못채우면 그냥 통째로 반납하고 swap out한다.

Working-Set Algorithm

슬라이딩 윈도우처럼 움직이며 working-set을 메모리에 올려놓는다.

PFF (Page-Fault Frequency) Scheme

Page Size의 결정

페이지 사이즈가 너무 작아지면 페이지 테이블이 너무 커진다.

locality 활용성 측면에는 안좋다. 프로그램은 코드가 연달아 순차적으로 참조되기 때문에, page fault가 났다고 작은 하나만 올려 놓으면 비효율적이다.