Virtual Memory

메모리 활용을 높이는 방법

초기에는 프로세스의 명령어와 데이터가 실행되려면 프로세스 전체가 물리메모리에 있어야 했었다. 
프로세스 사이즈가 커지면서 메모리 활용에 문제가 생겼고, 이를 해결하려는 방법들이 나왔다.

1) Dynamic loading
시작에는 main routine만 메모리에 로드되어, 다른 routine들은 호출될 때만 메모리로 로드된다.
사용되지 않는 루틴들은 메모리로 로드되지 않아서 메모리 활용이 높아진다.
루틴을 로드할 때의 overhead 문제가 있다.

2) Dynamic linking
library의 linking을 load타임때 하지 않고 runtime 때 사용되면 stub가 library를 메모리로 로드하거나 이미 다른 프로세스에서 사용되어서 로드 되었으면 연결을 시켜준다.
여러 프로세스가 한 library를 공유할 수 있다.

3) Overlays
Dynamic loading과 비슷함. 
프로그래머가 overlay driver를 작성하여, overlay driver는 필요할 때 루틴을 메모리로 로드한다.

4) Swapping
메모리에 있던 프로세스를 디스크로 보내는 것.
나중에 다시 필요할 때 디스크로부터 불러온다.
swap하는 데 걸리는 시간은 전송시간이 큰 부분을 차지한다.

Virtual Memory

logical memory를 physical memory로부터 분리
실행중일 때, 메모리에 필요한 건 프로그램의 일부분이다.
그래서 일부분만 메모리에 올린다면  logical memory는 physical memory보다 훨씬 크게 할 수 있다.
프로그래머는 physical memory size를 걱정할 필요가 없다.

Demand Page

Virtual memory 구현하기위해 필요한 것.
Swapping은 전체 프로세스를 디스크로 옮기는 것인 반면
Demand paging은 프로세스를 page 단위로 나누고 필요한 page만 메모리로 옮겨서 처리하는 것.
Lazy swapper라고 불린다.
Pager는 필요한 페이지만 메모리에 불러온다.
page table 참조해서 페이지가 현재 메모리에 없으면 디스크에서 불러온다.
page table의 valid-invalid bit을 이용해서 해당 page가 메모리에 존재하는지 디스크에 존재하는지 알 수 있다.
valid-invalid bit가 0이라면, 메모리에 없을 가능성이 있어서 page fault 인터럽트 발생

page fault handling

page fault에는 2가지 경우가 있다.
OS가 PCB를 참조하여
1) 그 페이지 주소가 정상적인 범위가 아니어서 invalid 였다면 그 프로세스를 종료시킬 것이고
2)  단지 메모리에 없어서 그런거라면 메모리에 올려주고 vaild bit를 1로 바꿔준다. 그리고 다시 인터럽트된 명령어로 돌아가서 실행한다.

비어 있는 frame이 없을 때
메모리에서 안 쓰는 page를 찾아 디스크로 저장한다.

pure demand paging

실제로 그 페이지가 사용될 때까지 메모리에 올리지 않는다.
이 경우에 만약 명령어마다 한 페이지씩 요구하는 프로그램이 있다면
page fault가 많이 발생해서 성능이 엄청 안좋을 것이다.
locality of reference
다행히 프로그램은 메모리에서 일정 범위안에서만 참조하는 경향이 있다.

실제로 초기화할때 몇 개의 page를 미리 올려놓는다고 한다.

하여튼 성능을 높이려면 page fault의 최소화가 중요하다.

Copy-on-Write

fork()함수는 자식 프로세스를 생성한다.
부모의 주소공간을 카피한다.
부모와 동일한 코드를 실행하기 때문에 메모리를 또 할당할 필요없이 공유할 수 있다.
같은 page를 공유하게 된다.
만약 한 page에 쓰기를 한다면 그 page만 카피해서 새로 만들어준다. copy-on-write
수정이 필요한 page만 새로 만듦으로써 효율적인 메모리 사용이 가능하다.

새로운 page가 필요할 때 메모리에 어떻게 할당할 것인가?

Pool

보통 운영체제는 free pages를 담은 pool을 유지한다.
그래서 자식프로세스가 새로운 page가 필요할 때나 프로세스의 stack이나 heap 공간이 더 필요할 때 pool에서 꺼내 할당할 수있도록 한다.  zero-fill-on-demand 기법을 사용하여 할당되기 전에 그 page에 있던 내용을 다 지워준다.

Page Replacement

over-allocating
demand paging을 이용해서 메모리가 수용할 수 있는 양보다 많은 프로세스를 돌릴 수 있게 되었다.
하지만 어느순간 메모리가 수용할 수 있는 양보다 많은 페이지 요구가 일어날 수 있다.
페이지가 메모리에 없어서 page fault를 했는데 free frame이 없을 경우 어떻게 해야 할까?
프로세스를 하나 죽이는 것은 비효율적이다.
page replacement를 한다.

Basic page replacement

1. 디스크에서 필요한 page의 위치를 찾고
2. free frame 찾기
    2.a 있으면 할당
    2.b 메모리에서 희생될 프레임(victim frame)을 선택한다.
    2.c 디스크에 victim frame을 쓰고 page와 frame table을 변경한다.
3. 디스크에서 그 page를 freed frame에 올린다. page와 frame table을 변경한다.
4. user program을 다시 시작한다.

2번의 page 전송이 일어난다. victim page를 디스크에 저장하는 것, 원하는 페이지를 디스크에서 꺼내오는 것.
이걸 줄여볼 수없을까?

Modify bit(or dirty bit)

page가 수정되었으면 modify bit가 1이 된다.
page replacement할 때 modify bit가 0이면
디스크에 쓸 필요가 없다. page 전송이 한번으로 줄게된다.

disk I/O는 시간이 많이 걸린다.
modify bit로는 불충분하다.
disk I/O를 줄일 수 있는 방법이 필요하다. 즉, page fault가 덜 발생하도록 하는 algorithm이 필요하다. 각각의 프로세스에 얼마나 많은 frame을 할당할 것인지(frame-allocation algorithm)와 page replacement가 필요할 때 어떤 frame을 선택할 것인지(page-replacement algorithm)에 대해 효과적인 방법을 찾아야 한다.

Page replacement algorithms

First-In-First-Out(FIFO) algorithm
page가 교체될 때 가장 메모리에 먼저 들어갔던 page가 교체되는 것.

Belady's Anomaly

그 프로세스에 할당된 메모리가 늘어 났는데 page fault가 더 많이 발생하는 현상.
메모리가 늘어났다고 해서 꼭 좋아지는 것은 아님을 알 수 있다. 

Optimal page-replacement algorithm

향후에 참조될 확률이 제일 적은 page가 교체된다.
컴파일러가 도와주면 가능은 하겠지만
reference string을 미리 알아야 하므로 구현하기 어렵다.

Least Recently Used (LRU) algorithm

가장 오래전에 참조되었던 페이지가 교체된다.
프로그램의 지역성(locality) 때문에 효과적인 알고리즘이다. (프로그램이 참조하는 page가 몰려있다. 한번 참조했던 page는 또 참조될 가능성이 크다.)
구현은 어떻게 할까?
Counter나 Stack을 이용한다.
Counter
page table의 entry마다 counter를 가지고 있다.
페이지가 참조될 때 counter에는 참조된 시각을 기록한다.
가장 오래된 시각을 가지고 있는 페이지를 교체한다.
Stack
page number를 가진 스택이 있다.
page가 참조될 때마다, 스택에 있는 그 page number를 맨 위로 올린다. 
가장 아래 있는 page number가 LRU이다.
doubly linked list로 구현하면 성능향상에 도움이 된다.

OPT나 LRU는 Belady's anomaly 현상이 일어나지 않는다.
메모리 할당이 하나 늘어났을 때 들어있는 page number set이 늘어나기 전의 page number set을 포함하기 때문이다.

하지만 Stack이나 Counter방식은 하드웨어 지원이 필요하고, 매번 메모리 참조가 일어날때마다 clock field나 stack을 업데이트해야 하기 때문에 성능이 느려진다. 

LRU Approximation algorithm

많은 시스템이 reference bit 을 이용해 LRU 비슷한 알고리즘을 하드웨어로 지원해준다.

Additional-Reference-Bits Algorithm

각 페이지당 reference-bits로 8bit 를 가지고 있다. 이 8bit는 일정시간간격으로 오른쪽으로 한칸 시프트 된다. 맨 오른쪽 비트는 버려진다.
그 페이지가 참조되면 맨왼쪽 bit를 0에서 1로 바꿔준다.
가장 적게 사용된 page는 page중에 가장 작은 reference-bits를 가지고 있는 페이지다.
일정시간간격이 좁을 수록 LRU에 가까워진다.

Second-Chance Algorithm
 

reference-bit이 한개이다.
FIFO algorithm에 기반을 두었다.
꺼낸 페이지의 reference-bit이 0면 그 페이지가 교체된다.
reference-bit가 1이면, 이번엔 그냥 넘어간다. 대신에 0으로 바꿔주고 맨 뒤로 보낸다.
최악의 경우에는 모든 page의 reference-bit가 1이 될 경우이다. 이 때는 FIFO 알고리즘이 된다.

Counting Algorithm

각각의 페이지 참조수를 센다.

LFU (Least Frequently Used) Algorithm
가장 작은 count를 가진 page를 교체한다.
하지만 그 페이지가 초기에만 엄청 사용되고 그 뒤에는 전혀 사용되지 않는다면?

MFU (Most Frequently Used) Algorithm
가장 큰 count를 가진 페이지를 교체한다.
작은 count를 가진 page들이 아직 할 일이 있을 것이다라는 생각에.

Allocation of Frames
 

각각의 프로세스는 최소로 필요한 page수가 있어야 한다.
첫번째 이유는 performance 때문. 할당된 frame 수가 줄어들수록 page fault가 자주 발생하게 된다. 그리고 page fault가 발생하면 처리된 후에 실행중이었던 명령어가 다시 실행되어야 한다. 그래서 최소한 page fault 없이 한 명령어를 실행할 수 있는 프레임이 할당되어야 한다.
프로세스당 최소 프레임 수는 architecture에 의해 정해지고, 최대 프레임 수는 이용가능한 물리 메모리에 의해 정해진다.

할당 알고리즘
 

1. equal allocation
100개 frame과 5개 프로세스가 있으면 한 프로세스에게 20개씩 똑같이 주는 것.
2. proportional allocation
프로세스 사이즈에 비례하여 frame을 준다.
3. priority allocation
프로세스 우선순위에 비례하여 frame을 준다. 아니면 우선순위랑 사이즈 모두 고려해서 줄 수도 있고.

global vs. local allocation
 

여러개의 프로세스가 프레임들을 차지하고 있는 상황에서
페이지 교체할 때
global replacement은 모든 프레임에서 교체할 프레임을 선택하는 것.
local replacement은 자기 프로세스에서 교체할 프레임을 선택하는 것이다.
global replacement의 한가지 문제는 자신의 page-fault rate를 조절 할 수 없다는 점. 왜냐하면 자신의 paging 방식뿐만 아니라 다른 프로세스의 paging 방식에 영향을 받기 때문. 따라서 같은 프로세스의 수행시간이 때에 따라 다르게 나올 수 있다.
local allocation은 한 프로세스가 자신에게 할당된 pages를 잘 활용하지 못할 때, 다른 프로세스가 페이지를 얻는 것을 방해하는 셈이 된다. 그래서 global replacement가 시스템 처리율에 있어서 더 좋아서 더 많이 쓴다.

Thrashing
 

낮은 우선순위를 가진 프로세스의 프레임이 컴퓨터아키텍쳐에가 요구하는 최소 프레임수 아래로 떨어지면 그 프로세스가 가진 남아있는 페이지들을 디스크에 저장하고 (Swapped out) 할당된 프레임을 해제시켜야 한다.
충분한 프레임을 갖지 못한 프로세스는 page fault가 발생할 가능성이 높다.
process가 thrashing 하다는 것은 프로세스가 실행하는 것보다 paging에 더 많은 시간을 쓸 때를 말한다.

Thrashing이면 CPU utilization이 떨어진다.
Global replacement일 때, 프로세스가 다른 프로세스 프레임 뺏고, 다른 프로세스가 그 프레임 읽으려고 했는데 없어졌으니까 또 다른 프로세스 프레임 뺏고 하는 상황이 생길 수 있다. paging 해주는 장치가 바빠져서 프로세스들은 waiting 큐 대기해서 paging 장치를 사용하기를 오랫동안 기다려야 한다. waiting큐에 쌓일 수록 ready 큐에는 아무것도 없는 상황 발생. 그래서 CPU 활용률은 떨어지게 되는 셈.
CPU 스케쥴러가 cpu utilization이 떨어지는 것을 보고 멀티프로그래밍정도를 증가시킨다. 그러면 상황이 더 악화.
처리되는 프로세스 수가 많아질 수록 CPU utilization은 올라가다가 어느 순간 떨어진다. 이때가 Thrashing 상태이다.
Thrashing을 막기 위해서는 멀티프로그래밍 정도를 낮춰야 한다.
local replacement 알고리즘을 사용한다면 막을 수 있을까? 이 알고리즘 쓰면 한 프로세스가 thrashing 하더라도 다른 프로세스의 프레임을 뺏지 못할텐데..
그래도 완전한 해결책이 되지 못한다. 프로세스들이 thrashing에 빠지면, paging device를 위한 큐에서 대기하는 시간이 길어질거고 page fault 처리하는 시간도 길어진다. 그 결과 thrashing이 아닌 다른 프로세스들에 접근하는 시간도 길어지게 된다.

Thrashing을 막기위해서는 가능한 많은 프레임을 프로세스에게 주어야 한다. 하지만 얼마나 많은 프레임이 필요한지 어떻게 알까?
Working-set strategy방법을 쓴다. 이 방법은 프로세스 수행이 locality하게 된다는 것이 전제로 한다.
Locality model은 프로세스가 수행될 때 한 지역에서 다른지역으로 움직인다는 것이다. 한 지역은 함께 자주 사용되는 페이지들의 영역이다. 한 프로그램은 몇개의 localities가 있다.
Locality model에 의해 Thrashing을 해결하려면 한 프로세스에게 최소한 현재의 locality를 수용할 수 있는만큼 frame을 할당한다.

Working-set model

locality에 기반한 방법.
Δ : working-set window, 일정한 갯수의 페이지를 담는 창. 
창에 참조되는 새로운 page 번호가 계속 들어오고, 창 범위를 넘어간 오래된 page는 나간다.
윈도우 사이즈가 너무 작으면 locality를 반영할 수 없고, 클 수록 일부 locality를 반영할 수 있다. 창 사이즈가 무한대면 모든 locality 반영.
working set :가장 최근의 Δ에 있는 페이지들 집합.
한 프로세스의 working set의 크기를 D라고 하면 D는 그 프로세스가 필요한 프레임의 크기이다.

D가 현재 이용가능한 프레임보다 크면 Thrashing이고, 이 때는 페이지를 확보하기 위해 돌아가고 있는 프로세스 중에 하나를 중지시켜야 한다. 그래서 최소한 D만큼의 프레임은 있도록 한다.

D가 계속 변하기 때문에 메모리 할당 크기는 시간에 따라 달라지게 된다.

매번 참조되는 페이지랑 working-set이랑 비교하는 것은 비용이 많이 든다.
따라서 대략적인 방법을 이용한다.
일정 시간마다 타이머 인터럽트를 발생시킨다. 그래서 그 때의 Δ를 이용한다.
각각의 페이지마다 2bit의 과거의 참조 정보를 가지고 있다.
2bit의 과거참조정보는 인터럽트가 발생하면 왼쪽 시프트해서 오른쪽 bit가 0이 되고 
Δ에 해당 페이지가 있으면 그 페이지의 오른쪽 bit에 1을 넣는다.
2bit 중에 어느 하나라도 1이면 page는 working-set에 포함된다.
일정 시간 내에서 정확한 참조 발생 위치, 시간을 알 수 없기 때문에 정확하지는 않다.
과거정보를 기억하는 bit를 늘려주고 타이머 인터럽트 시간을 더 주기적으로 해주면 더 정확해지지만 비용이 많이 든다.

 

Page-fault frequency방법

한 프로세스의 page-fault 비율을 모니터링
page-fault 비율이 너무 높으면 프레임을 더 주고, 너무 낮으면 프레임을 뺏는다.

Memory Mapped Files

virtual address를 이용해서 file i/o를 메모리 접근 루틴으로 하는 방법.
파일을 메모리로 읽어와서 read(), write() 대신에 virtual address를 호출하는 방식으로 파일처리.

디스크에 있는 파일이랑 동기화가 바로 안된다.
close()하면 memomy-mapped data가 disk에 쓰여지고 virtual memory로부터 제거된다.

여러 프로세스가 같은 mapped 된 파일을 동시에 접근할 수 있다.
copy-on-write기능을 지원해야.
여러 프로셋가 쓸 경우 동기화문제도 다루어야 한다. 

Memory Mapped I/O

더 편리하게 I/O장치에 접근하기 위해 많은 컴퓨터아키텍쳐들은 memory mapped i/o를 제공한다.
각각의 I/O 컨트롤러는 CPU로부터 전송된 명령이나 데이터를 저장하는 레지스터를 가지고 있다.
이 레지스터들을 메모리로 매핑한다. 따라서 메모리 주소로 레지스터 값을 읽고 쓸 수 있다.
device register는 I/O port라고 불린다.
CPU는 이 I/O port를 통해 데이터를 전송하고 받는데,  
CPU가 memory mapped 된 i/o port로 데이터를 보내고 control register에 데이터 보냈다고 bit을 입력하면
device는 그 데이터(byte)를 받고 다음 데이터 보내라고 control register의 그 bit을 clear한다.
Programmed I/O 
CPU가 control register의 그 bit를 계속 감시하고 있는 것. device가 준비가 되었나 안되었나 계속 주시.
interrupt driven
CPU가 bit 감시안하고 그 시간에 다른 일하다가 인터럽트로 보고 받는 것.

중간정리
page management 큰그림

출처 : http://oslab.snu.ac.kr/course/2010_fall/os/lecture_note/2010-os-ch10nn.pdf

다른 고려사항들

Preparing
많이 참조될 만한 것을 미리 한번에 메모리로 다 가져온다.
pure demanding-paging은 시작할 때 많은 page fault 발생
프로세스가 중지되었을 때 working-set을 저장했다가 다시 시작할 때 working set을 불러오는 방법.

Page size selection
page size가 작으면 i/o 시간이 적게들고, internal fragmentation이 적다. page table size는 커진다.(table fragmentaion 문제)
page size가 크면 page fault 빈도가 줄어든다. 

TLB Reach
TLB의 hit-rate는 엔트리 수하고 관련되어 있다.
hit-rate를 높이려면 엔트리 수를 키워야 하는데, TLB를 구성하는데 이용되는 메모리가 비싸다.

hit-rate와 비슷한 평가요소인 TLB Reach
TLB로부터 접근할 수 있는 메모리 양(앤트리 수 * 페이지 사이즈)
성능이 가장 좋은 이상적인경우는 working set을 모두 cover할 수 있을 정도의 TLB Reach가 되는 것.
TLB Reach 크기를 늘일 수 있는 경우는 두가지.
page size가 크게 또는 다양한 size의 page를 제공
페이지 크기 크게 하면 in fragmentation이 생길 수 있다.
페이지 사이즈를 다양하게 하면 OS가 TLB를 관리 해야 한다.

I/O Interlock
메모리에서 쫓겨나면 안되는 페이지들을 locked한다.

Consider I/O
디바이스에서 파일을 카피하는데 이용되는 페이지들은 page replacement algorithm에 의해 선택되면 안된다.locked한다. 

참고사이트
http://oslab.snu.ac.kr/course/2010_fall/os/lecture_note/2010-os-ch10nn.pdf
http://bug7015.tistory.com/entry/Virtual-Memory-5-Working-Set-Model