Virtual Memory

Demand Paging

실제로 필요할 때 page를 메모리에 올리는 것이다.
I/O, 메모리 사용량이 감소하고 빠른 응답시간과 더 많은 사용자를 수용할 수 있다.

valid/invalid bit을 사용한다.
invalid는 사용되지 않는 주소 영역인 경우와 페이지가 물리적 메모리에 없는 경우다.
처음에는 모든 페이지 엔트리가 invlid로 초기화된다.
주소변환 시에 invlid bit이 set되어 있으면 page fault를 발생시킨다.
page fault가 나면 CPU는 운영체제에게 넘어가게 된다.

page fault

page fault에 대한 처리 루틴은 다음과 같다.
invalid page에 접근하면 MMU가 트랩을 발생시킨다.
CPU가 운영체제로 넘어가서 page fault handler가 실행된다.
먼저 잘못된 요청인지를 확인한다.(주소가 잘못되거나 접근권한을 위반하거나)
빈 페이지를 획득하고 없다면 메모리공간을 확보하기위해 하나를 쫓아내고 획득한다.
페이지를 디스크에서 메모리로 읽어온다.
이 프로세스가 CPU를 잡고 다시 running한다.
아까 중단되었던 인스트럭션을 재개한다.

free frame이 없는 경우

page replacement

메모리에 빈 공간이 없는 경우에 어떤 frame을 뺏어올지 결정해야 한다.

Replacement Algorithm

page-fault rate를 최소화하는 것이 목표다.
page reference string에 대해 page fault를 얼마나 내는지 조사한다.
reference string의 예(1,2,3,4,1,2,5,1,2,3,4,5)

Optimal Algorithm

page-fault를 가장 적게하는 알고리즘이다.
가장 먼 미래에 참조되는 페이지를 재배치하며 4개의 프레임일 때 최소 6번의 page fault가 난다.
미래에 참조되는 페이지들(reference string)을 미리 다 안다고 가정하는 것이다.
그래서 실제 시스템에 사용할 수는 없고 다른 알고리즘의 성능에 대한 upper bound를 제공한다.

FIFO(First In First Out) Algorithm

먼저 들어온 것을 먼저 내쫓는다.

• FIFO Anomaly(Belady’s Anomaly)
  메모리 frame이 늘어난다고 해서 page fault가 줄어들지 않고 늘어날 수도 있다.

LRU(Least Recently Used) Algorithm

제일 오래전에 사용된 것을 쫓아낸다.

LFU(Least Frequently Used) Algorithm

참조횟수가 가장 적은 페이지를 쫓아낸다.

캐슁 환경

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

Clock Algorithm

paging system에서 LRU, LFU를 사용할 수는 없고 clock algorithm을 사용한다.

reference bit이 1인것을 시계방향으로 돌면서 0으로 바꾼다.
reference bit이 0이라는 것은 시계방향으로 한바퀴를 돌아오는 동안에 해당 페이지에 대한 참조가 없었다는 말이다.
reference bit이 1이라는 것은 적어도 한번의 참조는 있었다는 말이다.
하드웨어가 페이지들을 참조할 때 1로 만드는 역할을 하고 운영체제는 하드웨어가 만든 bit을 보면서 어떤것을 쫓아낼지 결정한다.
bit이 0인 것은 쫓아낸다.
bit이 1이면 0으로 만들고 한바퀴 되돌아 왔을 때 1이면 다시 기회를 준다.
한바퀴 되돌아 왔을 때 0이면 쫓아낸다.

reference bit(최근에 참조된 페이지)과 modified bit(최근에 변경된 페이지)을 함께 사용하는데 페이지를 쫓아낼 때 modified bit이 0이면 그냥 쫓아내면 되는데 1이면 메모리에 올라온 이후로 적어도 한번은 내용을 수정했기 때문에 backing store에 변경내용을 반영하고 쫓아내야 한다.
그래서 가능하면 modified bit이 1인 것 보다 0인것을 우선해서 쫓아내면 더 빠르다.

page frame의 allocation

명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있고 loop를 구성하는 page들이 최소한의 allocation이 없으면 loop마다 page fault가 발생하므로 각 프로세스에 얼만큼의 page frame을 할당할 것인지 정해야 한다.

thrashing

프로세스의 원할한 수행에 필요한 최소한의 page frame수를 할당받지 못한 경우에 발생한다.
메모리에 동시에 많은 수의 프로그램이 올라가게 되면 충분한 page frame을 확보하지 못해서 page fault가 지나치게 자주 발생하게 되고 CPU utilization이 낮아진다.

working set model

프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조하고 집중적으로 참조되는 page들의 집합을 locality set이라 한다.
locality에 기반해서 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 working set이라 한다.
working set전체가 메모리에 올라올 수 없는 경우에는 모든 frame을 반납한 후 스왑아웃된다(suspend).

page size의 결정

page size를 감소시키면 페이지 수가 증가하고 페이지 테이블 크기가 증가하며 내부조각이 감소하고 필요한 정보만 메모리에 올라와 효율적이다.
disk transfer의 효율성은 감소한다.