이전 쳅터에서 물리적 주소로의 변환은 OS가 전혀 관여하지 않고 하드웨어가 해준다고 하였다. virtual memory기법은 전적으로 OS가 관리한다.
Demand Paging
실제로 필요할때 page를 메모리에 올리는것이다.
i/o양이 감소하고, 메모리 사용량 감소, 빠른응답시간, 더 많은 사용자 수용등의 장점이 있다.
Valid/InValid bit 사용
physical memory에 올라가 있는 page들은 valid 나머지들은 Backing store에 내려가 있기 때문에 invalid다.
그렇다면 invalid의 의미는 두가지가 있다.
- 아에 사용되지 않는주소, page table의 엔트리들은 logical memory의 주소공간만큼 똑같이 만들어 지기 때문에, 그림과 같이 G,H는 사용이 되지 않는 페이지라도, 7번까지 엔트리가 만들어지고 invalid로 표시한다.
- 1,3,4번은 사용이 되는 페이지지만 아직 올라오지 않아서 invalid로 표시를 하였다.
cpu가 논리주소를 주고 page table에서 page number에 해당하는 frame nubmer를 확인하려고 하니까 invalid bit으로 없다. 이런경우에는 page가 아직 backing store에서 안올라온거기 때문에, 이걸 backing store에서 physical memory로 올려줘야하는데 이러한 작업은 I/O이다. 그러므로 OS가 해줘야한다. 이때 page fault라는 현상이 발생한다.(요청한 페이지가 없는경우) 운영체제로 cpu가 자동적으로 넘어오게 된다.
Page Fault
invalid page를 접근하면 MMU가 trap을 발생시킨다. 그러면 운영체제로 CPU가 넘어가서 kernel mode로 들어가서 pagefault handler가 실행된다.
- 우선 bad address, protection violation같은 invalid refrence인지 확인하고 비정상적인 요청이면 abort시킨다.
- 정상적인 요청이라면 빈 page frame을 가져온다. 없으면 뺏어온다.
- 해당 페이지를 disk에서 memory로 읽어온다.
3-1. disk i/o는 매우 느리므로 이 프로세스는 disk i/o가 끝날때까지 preempt 당한다.(block)
3-2. disk read가 끝나면 page tables entry를 기록하고, valid/invalid bit을 valid로 변경한다.
3-3. ready queue에 process를 insert하고 - 이 프로세스가 cpu를 잡고 다시 running
- 아까 중단되었던 instruction을 재개한다.
그림을보면 참조를 하는데 i라서 backingstore에가서 가져오는 상황을 볼 수 있다.
performance of demand paging
pagefault 비율이 0에서 1이라고 p로 가정하면 대부분 0.98 이런식으로 page fault가 잘 발생하지 않는다.
(1-p)*memory access + p(os & hw page fault overhead + swap page out if needed + swap page in + os & hw restart overhead)
수식과 같이 만약 page fault가 발생하면 많은 시간이 소요됨을 확인 할 수 있다.
Free frame이 없는경우
page replacement가 필요하게 된다.
일단 victim을 선정하게 되면 backing store로 swap out한다. 여기서 만약 disk에 올라와서 write가 발생했다면 backing store로 가서 write로 써주고 swap해야한다.
그게 아니라 그냥 읽기만 했으면 그냥 phsycial memory에서 지워주기만 하면 된다.
그리고 쫒아낸놈은 invalid로 바꾸고, 새로 backing store에서 요구한 page를 들고와서 page table에 해당 frame번호와 valid bit으로 설정하면된다.
그럼 어떠놈을 쫒아내는게 제일 효율적일까?
Optimal Algorithm
일단 이건 이론적인 알고리즘이다. Optimal Algorithm이 가장 적은 page fault를 발생시킨다. 그럴수 있는 이유가, 여기서는 offline Algorithm으로 어떤 page참조가 들어올지 그 순서를 안다고 가정하고 page fault를 발생시키는 것이다.
즉 우리는 페이지 참조를 1,2,3,4,1,2,5,1.2.3.4,5 순서로 참조할 것이라고 알고, 가장 적은 페이지 fault를 발생시키기 위해서 가장 먼미래에 참조되는 page를 replace한다.
그래서 5번 페이지를 참조할 때 생긴 page fault경우에서 가장 먼 미래에 참조되는 4번 page를 쫒아내고 5번을 들인것이다.
실제로는 당연히 우리는 어떤 page를 참조할지 미래를 알지 못한다. 고로 이 알고리즘은 다른 알고리즘의 성능에 대한 upper bound를 제공한다. 즉 어떤 알고리즘을 가져오더라도 이 Optimal Algorithm을 넘어설수는 없다.
FIFO Algorithm
First In First Out 알고리즘
먼저 들어온걸 먼저 내쫒는다.
특징: frames를 늘릴수록 page fault가 더 많이 발생한다.(FIFO Anomaly)
LRU
Least Recently Used Algoritm
가장 오래전에 참조된걸 내쫒음
5번이 들어올때 가장 오래전에 참조된 3번을 쫒아낸다.
LFU
Least Frequently Used
참조 횟수가 가장 적은 페이지를 지운다.
최저 참조횟수인 page가 여러개 있으면 임의로 선정한다.
장단점
LRU처럼 직전 참조 시점만 보는것이 아니기 때문에 장기적인 시간규모를 반영하기 때문에 page의 인기도를 더 정확히 반영할 수 있다. 그러나 참조 시점의 최근성을 반영하지 못한다.
왜냐하면 이제 최근에 쫌 많이 슬슬 떠오르는 page들은 반영할 수 없기 때문이다.
LRU와 LFU 알고리즘의 구현
LRU는 간단하다 Linked List로 구현해서 만약 기존의 page가 참조되거나 새로운 페이지가 참조되거나 하면 그냥 무조건 최근에 참조한것이 왕이니까 MRU page쪽으로 이동시키면 된다.
그리고 만약 쫒아내야하면 그냥 tail쪽에 있는 마지막 page를 쫒아내버리면 된다. 이러면 O(1) complexity가 발생한다.
그러나 LFU는 좀다르다.
만약에 page를 참조하더라도, 그냥 LRU처럼 head앞부분에 위치하도록 구현이 안된다. 왜냐하면 자기 앞쪽에 있는애들을 하나하나 뒤져가면서 나보다 더 많은 참조가 일어났는지 안 일어 났는지 확인을 해가면서 앞으로 가야하기 때문이다.
최악의 경우 자기부터 head까지 전부 검사해야할지도 모른다.
O(n)컴플랙시티가 발생하므로 이건 LinkedList가 아니라 Heap으로 구현한다.
이러면 맨위에는 참조횟수가 제일 적은 페이지를 두고 밑으로 갈수록 참조횟수가 늘어나게 된다. 이렇게 되면 새로운 참조가 들어오게되면, 밑에 있는 모든 page들의 참조횟수를 linked List처럼 다 뒤지는것이 아닌, 자기 직계 자식하고만 비교를 하고 만약에 자기 직계자식보다 크다면 자리바꿈을 하면된다.
캐쉬 기법
한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다.
Paging System외에도 cache memory, buffer caching, Web caching등 다양한 분야에서 사용된다.
캐쉬 운영의 시간제약
교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리면 사용할 수 없다.
O(1)에서 O(logn)정도 까지 허용한다.
그렇다면 Paging System에서 LRU,LFU가 가능할까?
그림에서 cpu에서 ProcessA가 running중이라고 하자.
만약 주소변환을 했는데 page table에서 v라서 physical memory에 올라와 있다면 그냥 가져와서 쓰면된다. -> 이러한 과정에서는 앞에서 말했듯이 운영체제가 하는일이 없다.
반면에 processA가 주소변환을 실행했는데 invalid라서 backing store에서 가져와서 physical memory에 올려야하는 Page Fault가 발생하게 되면 Disk에 접근하고 I/O를 해야하므로 Page fault Trap이 발생하게 되고, processA로부터 운영체제가 넘어가고 운영체제가 Backing Store에서 원하는 Page를 가져와서 만약 Physical memory가 꽉 찼으면 누군가를 쫒아내고 올려야만 한다.
LRU알고리즘을 쓰면 가장 오래전에 참조된 페이지를 쫒아내야하는데 과연 OS가 가장 오래전에 참조된 페이지를 알아낼 수 있는가?
LFU 가장 적은 참조횟수를 가진 Page를 찾아내야 하는데 이걸 알아낼 수 있는가?
정답은 알아낼수 없다.
애초에 만약에 Physical 메모리에 올라가 있는 상태라면, OS가 관여하지 않기 때문에 언제 올렸는지, 몇번 참조되었는지 알지 못한다.
그리고 만약 없어서 운영체제로 넘어가면 이제 그때는 Backing store에서 memory로 올라온 시간을 알수 있다.
즉 OS는 반쪽짜리 정보만 가지고 있는것이다.
LinkedList나 Heap으로 구현된 LRU,LFU에서 메모리에 이미 올라와 있는 애들을 다시 참조하는경우는 운영체제가 이 링크를 끊어서 MMU page 앞쪽으로 올려보내는 과정을 하지 못한다.
결국 우리가 LFU,LRU등을 배웠지만, 결국 Paging System에서는 사용하지 못한다는것이다.
그래서 사용하는 알고리즘이 Clock Algorithm이다.
CLock Algorithm(second chance algorithm, NUR 알고리즘)
LRU의 근사 알고리즘이다.
사각형이 page frame들이다.
운영체제가 아닌 하드웨어가 만약에 page table에서 주소변환을 할때 만약 valid라서 이미 메모리에 올라와있다면 reference bit을 1로 바꿔준다. 이미 메모리에 존재하는 page에 대해서는 참조가 되면 page를 읽으면서 reference bit을 1로 바꿔주는것이다.
page fault가 발생해서 누군가를 쫒아내야할 때는 reference bit이 1이면 0으로 바꾸고 넘어가고 0이면 교체대상 페이지가 된다.
modified bit(dirty bit)을 추가로 둔다.
교체 대상 페이지가 되었는데 만약 modified bit이 0이면 backing sotre에서 physical memroy에 올리고난 뒤에 wirte가 발생하지 않았다는 뜻이다.
그런 페이지를 쫒아낼때는 어차피 카피본이 backing store에 존재하므로 그냥 쫒아내면된다.
반면에 modified bit이 1이면 physical memory에 올라온 이후로 적어도 1번은 write를 한것이므로 그런 페이지를 쫒아낼 때는 backing store에 바뀐 내용을 적용을 하고 쫒아내야한다.
Page Frame의 Allocation
- Equl allocation: 모든 프로세스에 똑같은 갯수를 할당
- Proportional allocation: 프로그램 크기에 비례해서 할당
- Priority allocation: 프로세스의 priority에 따라 다르게 할당
Global Replacement
내가 굳이 설정을 안해도 프로그램 크기가 크면 많이 쫒아내고, 다른건 덜 남아있으므로, Replacement를 하면서 자동적으로 조정이된다는 의미다.
FIFO, LRU,LFU등의 algorith을 사용할 수 도 있고, Woking set, PPF같은 알고리즘이있다.
Local Replacement
자신에게 할당된 frame내에서만 replacement를 하는것이다. FIFO,LRU,LFU등의 알고리즘을 사용한다.
Glocal Replacement는 다른 프로그램의 page를 쫒아낼 수도 있는것이고, Local replacement는 프로그램에 할당을 해놓은 다음에 새로운 page를 들여 오려면 자신에게 할당된 page를 쫒아내는 것이다.
결국 자신에게 할당된 frame 내의 apge를 쫒아내야하므로 여기서도 어떤놈을 쫒아내야할지 LRU,LFU알고리즘등을 사용하게 된다.
Thrashing
x축 - 지금 메모리에 올라와있는 프로그램의 갯수
y축 - CPU 사용률
만약에 프로그램이 1개만 있으면 CPU를 쓰다가 I/O를 하러가면 CPU는 놀아야한다.
그래서 CPU 사용률이 작다.
그런데 어느순간 CPU Utilization이 올라가다가 어느 지점부터 뚝 떨어지는 것을 볼 수 있다.
바로 Thrashing이 발생한 순간이다.
프로세스한테 page frame이 텍스트너무 적게 할당되면, page fault 비율이 높아진다.
한 프로세스가 page를 찾으로 갔는데 없어서 IO를 하러가고 또 다른 프로세스가 CPU를 받아서 page를 찾으러 갔는데 없어서 IO를 하러가고 이런 과정이 반복되다 보면
cpu가 계속 노는 상황이 발생한다.
그러면 어떠한 프로그램이 CPU를 잡더라도 전부 IO를 하러 가버리니까 CPU Utilization이 낮아지고, OS는 어? CPU가 계속 노네 하면서 다른 프로세스를 시스템에 계속 추가하게 되고, 그러면 또 프로세스 당 할당되는 frame 수가 더욱 감소하는 방식으로 진행된다.
Working-set Model
- Locality of reference
프로그램이 원활하게 수행되기 위해서 적당량의 frame을 할당 받아야만하고, 프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다.
Working-set
Locality에 기반하여서 프로세스가 일정시간동안 원활하게 수행되기 위해서 한꺼번에 메모리에 올라와 있어야하는 page들의 집합
만약에 workingSet을 마련하지 못하면 모든 frame을 반납한 후에 swap out한다.
Working-set Algorithm
Working set은 우리가 아 어느정도 frame을 메모리에 각 프로세스마다 올려놓아야 잘 수행할수 있을까? 우리가 이걸 알면 그냥 올려놓고 실행하면되는데 우리는 이걸 알지못한다.
그래서 미래를 예측하기 위해서 과거를 봐야한다고, 과거를 통해 추정할 수 밖에 없다.
과거 델타시간동안, 과거에 참조된 페이지들은 내쫒지 않는것이다.
이 델타시간이 working set window라고 한다.
그림을 보면 델타시간동안 참조된 페이지가 12567이므로 해당 페이지들을 메모리에 전부 올려놓을 수 있으면 올려놓고, 만약 전부 올려놓지 못한다면 전부다 disk로 swap out시키고 이 프로세스를 suspended시킨다.
이게 t1, t2시점마다 윈도우를 쭉 밀면서 가니까 working set이 바뀐다.
그래서 해당 working set에 속한 page는 메모리에 유지되고, 속하지 않는것은 버린다.
PFF-Page Fault Frequency
page fualt rate의 상한값과 하한값을 둔다.
프로그램마다 곡선의 가파른 값이 다르므로, page fualt rate이 상한값을 넘으면 frame을 더 할당하고 하한값 이하이면 할당 frame수를 줄인다.
Page Size의 결정
page size를 감소시키면 -> 페이지수가 증가하고 -> 페이지 테이블 크기가 증가한다. -> 페이지 안에서 안쓰는 부분들이 감소한다 -> 더 잘게 써니까 만약에 1이라는 페이지에서 0.5는 쓰고 0.5는 안쓰면, 0.5로 페이지를 썰게되면 안쓰는 공간이 줄어들게 된다. 메모리에 꼭필요한 정보들만 올라와 메모리 이용에 효율적이다. -> Locality 활용 측면에서 좋지 않다. -> Disk transfer의 효율성감소 -> 만약 잘게 썰면 썰수록, page fault가 많이 발생하니까, Disk에서 seek해서 올리는 과정을 반복해야한다. 그러나 Seek는 굉장히 오래 시간이 걸리므로, page fualt 날때마다 그때그때 seek하러가면 효율이 너무 떨어진다. -> 그래서 요즘은 page를 키우고있다.
