* Virtual Memory의 탄생
P1, P2, P3를 수행할 때에는 Swapping 기법으로 Process를 돌려가면서 모두 사용이 가능하다.
여기서 Disk가 들어가지면 이런 측면에서 Virtual memory가 나온 것은 아니다.
virtual memory의 탄생은 다음과 같은 문제를 해결하기 위해서 탄생했다.
Memory공간이 400이 필요한 프로세스를 300짜리 memory공간에서 어떻게 실행 할 것인가?
즉, 자신의 Memory보다 더 큰 공간이 필요한 프로세스를 어떻게 실행 시킬 것인가의 문제를 해결하는 것이다.
> 프로그램을 분할하여 사용하는 것만 Memory에 올리자!! 사용하지 않는 것은 DISK(Virtual Memory)에 저장하자!!
* Virtual memory
- 프로그램을 실행하는데 필요한 부분만 Memory에 upload시킨다.
- 위와 같은 이유로 Process의 Logical memory는 Physical memory보다 더 클 수 있다.
- 몇몇 프로세스가 메모리를 공유하기 쉽다.
- 쉽게 프로세스 생성이 가능하다.
> 위의 두 가지의 이야기는 다음과 같다. Parent process가 child process를 생성(프로세스 생성)시
같은 Physical memory를 가르키게한다. 만약 수정이 발생하면 그때서 그 부분만 복사를 실시한다.
즉, 프로세스가 생성될 때 메모리를 복사하는 것이 아니라 Write가 발생하면 그때 복사를 실시한다.
그림으로 살펴보면 다음과 같다.
- 동시에 사용가능한 프로그램이 증가한다.
- I/O가 적어진다.
- 구현법
ⓐ Demand Paging
ⓑ Demand Segmentation
* Demand Paging
- 실행에 필요한 Page를 Memory에 올린다.
- Disk의 특정위치에는 연속적으로 Process의 Page가 저장된다.
- 장점
> I/O가 적어진다.
> Memory 사용이 적어진다.
> 많은 사용자가 사용이 가능하다.
- Paging 요청을 받았을 때 Page가 Page Table에 없다면, OS는 다음의 판단을 해줘야 한다.
> 허가 되지 않는 요청인가?
> 단지 메모리에 페이지가 없는 것인가? 허가된 요청일 경우 Page table의 Validation bit을 이용하여
Memory에 있는지 없는지를 판단한다.
※ P : page number / F : Frame number
V : validation bit(Memory에 있는지 없는지 판단) / M : Modify bit(추후 설명)
* Page fault
- page가 memory에 없는 경우
1) Trap 발생
2) OS의 판단
2-1) 허가되지 않는 요청 > Abort
2-2) 허가는 됬지만 메모리에 Page가 없음 > 3)의 과정으로
3) Frame의 빈공간을 확보
4) Disk에 저장된 Page 정보를 Memory로 올린다.
5) Page Table에서 해당 Page의 Validation bit을 V로 변경하고, Frame번호를 기입한다.
6) Page fault가 발생한 실행문을 재시작한다.
(그림중요!)
- EAT = (1-p)memory access time + p(page fault overhead + page swap out + page swap in + restart overhead)
- Page Fault가 적게 발생해야지 EAT시간을 보상 받을 수 있다.
> 이는 Free Frame이 없을때 어떤 Frame을 교환 할 것인지를 판단하는 문제와 큰 연관이 있다.(Frame Replacement)
> 위의 경우 4. 과정에서 free frame이 없다면 victim frame을 선정하여 page swap out, in을 해야한다.
> 여기서 page swap out을 생략할 수 있는데 여기서 사용되는 bit가 modify bit(dirty bit)이다.
Frame 공간에 있는 Page를 Disk로 옮길 때, 실행의 효율을 위해서 modify bit을 두는 것이다
자료가 memory에서 수정이 있다면 modify bit을 1로 setting을 한다. Page가 Disk로 이동할때, modify bit이 0이면
Swap out 과정을 생략해 시간적 이점을 가져올 수 있다.
* Page And Frame Replacement Algorithm
- Algorithm의 성능은 Page number sequence(reference string)을 사용해서 시뮬레이션을 해본다.
ⓐ FIFO(First in First Out)
- 가정 먼저온 Frame을 바꿔준다.
ⓑ Optimal Algorithm
- Page fault 시점에서 가장 멀리서 Request하는 Page를 replace한다.
- Page fault가 minimal 하게 발생한다.
- But, 미래를 알 수 없기 때문에 현실적으로 불가능하다.
ⓒ Least Recently Used Algorithm(LRU)
- 가장예전에 사용된 것을 replace
- 최근에 사용한 Page > 다시사용될 경우가 많다.
- 구현법
> Using "Counter" : Page 마다 시간을 counter에 저장시킨다.
Page Swapping이 발생하면 counter가 가장 적은 값을 가진 Page를 replace한다.
> Using "Stack" : double link form으로 page번호를 stack에 저장한다.
page가 사용되면 stack의 top으로 이동시킨다.(stack의 bottom 값이 사라진다)
ⓓ LRU Approximation Algorithm
- LRU를 했을 때와 근접한 결과를 내는 알고리즘
- LRU Performance를 위해 HW의 도움을 받는다.
- 종류
1) Reference bit
> 최근에 사용되는 Page는 Reference bit이 1로 setting되어 저장
> 일정 주기마다 reference bit을 0으로 초기화 시킨다.
> 만약, Page table이 꽉차 있다면, reference bit이 0인 것을 replace한다.
2) Second-chance algorithm
> Reference bit에 시간적 조건을 가미한 것
> 최근에 사용되는 Page는 Reference bit이 1로 setting 되어 저장된다.
> Page Table에 victim pointer가 존재
> Page Fault가 났다면, Victim pointer 위치를 본다.
Victim pointer가 가르키는 reference bit이 0이면 replace, victim pointer가 가르키는 reference bit이 1이면
현재 reference bit을 0으로 변경한 뒤에 다음 위치를 탐색하면서 현 과정을 반복한다.
ⓔ Counting Algorithm
- Page마다 사용된 counter를 샌다.(Page가 호출될 때마다 counter를 올린다.)
- 종류
> LFU (Least Frequent used) : 가장 count가 낮은 것을 replace한다.
> MFU (Most Frequent Used) : 가장 count가 높은 것을 replace한다.
ex)
* Fixed Allocation
- Process당 몇개의 Frame을 줄 것인가?
ⓐ Equal allocation : 균등하게 분배를 하며, Frame buffer pool을 유지한다.
ⓑ Proportional allocation : process의 size에 비례해서 분배해준다.
ⓒ Priority allocation : Process의 우선순위에 따라서 분배해준다.
* Global vs Local Replacement
ⓐ Global Replacement
- 전체 Frame에서 하나를 replace
- 효용주의 : 하나의 프로세스 성능 저하가 전체 성능을 올릴 수 있음
- 예측하지 못한 결과가 나올수 있다.
ⓑ Local Replacement
- 자신이 사용하고 있는 Frame중 하나를 교환 실시
- Process 각각의 성능을 예측할 수 있다.
* Trashing : 메모리가 부족하여 지속적으로 Page fault가 발생하는 상황
- CPU 활용도가 낮아진다.
- CPU가 놀고 있기 때문에 Long term scheduler는 지속적으로 Process를 올린다.
ⓐ Locality model
- Process는 자신이 사용하는 지역을 할당받아 사용하며, 이 지역은 지속적으로 변경 가능하다.
- 어느 순간에 Process가 필요로 하는 Locality의 합이 Memory size보다 커질수 있다. > Trashing 발생
ⓑ Working-set model
- 특정 n개의 window size에 있는 Process의 집합
- 각각의 Process의 working set은 잘 변하지 않는다.
- Process working set의 총 합이 Memory 보다 크면 Trashing이 발생한다.
> OS가 판단하여 Trashing이 발생하면, Process를 멈추거나 내린다.
> 사용되는 Page의 reference bit을 1로 두고, 몇 초마다 window size에 있는 working set을 세고,
reference bit을 0으로 초기화한다. 이때 Trashing 여부 판단 가능
* Page Fault Frequency
- Frame수를 늘리거나 줄일 수 있다. ( Page Fault가 많으면 Frame도 증가, Page Fault가 적으면 Frame 감소)
- 새로운 function call, process call.. 등을 할때 Page Fault가 극격히 증가한다.