Virtual Memory
Virtual Memory란?
Physical Memory와 Logical Memory를 구분해주는 것.
Logical Memory가 Physical Memory보다 훨씬 더 크기 때문에 실행에 필요한 부분만 메모리에 적재한다.
프로세스간 주소공간을 공유할 수 있게 해준다.
Physical Memory를 신경쓰지 않고 효율적인 프로세스를 생성할 수 있게 해준다.
다음과 방식을 통해서 Virtual Memory가 구현된다
Demand Paging
Data전체가 아닌 하드디스크에서 Data를 필요한 순간에만 Memory로 가져오는 것.
- 필요할 때에만 가져오기 때문에 I/O 입출력이 줄어든다.
- 메모리를 효율적으로 사용할 수 있다.
- 응답시간이 빨라진다.
- 더 많은 사용자를 수용할 수 있다.
Data가 필요할 때,
Data가 Memory에 있다면 그것을 사용한다.
잘못된 주소 (Invalid Referenc)라면 접근 자체를 Abort한다.
Memory에 없다면 Disk에서 Memory로 가져온다.
Valid-Invalid Bit
Page Table에 Valid-Invalid Bit를 추가하여 해당 Page가 Physical Memory에 있는지 확인한다.
Valid-Invalid Bit가 1 ⇒ 해당 Page가 Physical Memory에 존재한다.
Valid-Invalid Bit가 0 ⇒ 해당 Page가 Physical Memory에 존재하지 않는다.
Valid-Invalid Bit는 0으로 초기화된다.
Logical Memory를 Physical Memory로 변환할 때, Valid-Invalid Bit가 0이라면 Page Fault가 발생.
Page Fault
Physical Memory에 없는 Page에 접근하려고 할 때 Page Fault가 발생한다. (Trap)
Page Fault가 발생하면 Disk에서 해당 Page의 Data를 Physical Memory로 불러와야한다.
- 필요한 Page를 Page Table에서 찾는다. → Valid-Invalid Bit가 0이다 → Invalid
- Trap 발생 ‼️
- OS가 Disk에서 해당 데이터를 찾는다.
- 해당 데이터를 Physical Memory로 가져온다.
- Page Table을 Update한다.
- 해당 Page가 필요했던 Instruction을 다시 실행한다.
4번 과정에서, Physical Memory에 남는 공간, 즉 Free Frame이 없는 경우 Physical Memory에서 Disk로 특정 Frame을 Swap Out 하여 공간을 마련해야한다.
이때, 어떤 Frame을 내려보낼지를 결정하는 알고리즘 ⇒ Page Replacement Algorithm
성능적인 측면을 위해서 미래의 실행에 대해서 Page Fault를 최소화하는 Algorithm을 사용해야한다.
Performance of Demand Paging
Page Fault가 발생할 확률을 p라고 하자
p = 0 이면 Page Fault가 발생하지 않는다.
p = 1 이면 매번 Page를 참조할 때 마다 Swap 과정이 발생한다.
Effective Access Time(EAT) : Page 참조에 걸리는 시간.
EAT = ( 1-p ) * memory Access [ ⇒ Page Fault가 발생하지 않아 Memory에서 Page를 가져오는 경우 ]
➕ p ( page fault overhead + [swap page out] + [swap page in] + restart overhead )
⇒ Page Fault가 발생하여 Swap 과정이 발생.
Ex.
Memory Access에 걸리는 시간 = 1 microsecond
Physical Memory에 빈 공간이 있을 확률 = 50%
Swap Page Time = 10msec = 10,000 microsec
EAT = (1 - p) * 1 [ ⇒ Page Fault가 발생하지 않아 Memory에서 Page를 가져오는 경우 ]
➕ p * 15,000 ( 15,000 = Swap In만 하는 경우 + Swap In, Swap Out 둘다 하는 경우의 평균)
= 1 + 15,000p
p = 1%면 EAT = 151microsec
Page Replacement
요즘 Page Fault를 처리하는 Routine에 Page Replacement를 하는 알고리즘이 포함되어 있다.
Page가 변경된 적이 있는지를 기록하는 Modify Bit를 사용하여 Page Transfer시에 발생하는 Overhead를 감소시킬 수 있다.
Basic Page Replacement
- Disk에서 원하는 Page를 찾는다.
- Physical Memory에 빈 공간이 잇으면 사용 / 없으면 Page Replacement Algorithm을 사용하여 Victim(희생양)을 선택한다.
- Victim을 Swap Out하고, 원하는 Page를 Swap In 한 뒤 Page와 Page Table을 수정한다.
- Process를 다시 시작한다.
Page Replacement Algorithm
여러가지 Page Replacement Algorithm이 있다.
Page Fault 비율이 가장 낮은 알고리즘이 좋은 알고리즘이다.
임의의 Memory Reference를 하는 Reference String을 사용하여 알고리즘을 평가하고, 해당 Reference String에서의 Page Fault 숫자를 계산한다.
FIFO Algorithm
먼저 들어온 놈이 먼저 나간다.
reference string이 1,2,3,4,1,2,5,1,2,3,4,5라고 할 때
3Frame인 경우보다 4Frame인 경우에 Page Fault가 발생하게 된다.
이러한 사건을 Belady's Anomaly라고 한다. → Frame이 늘어났는데 Page Fault가 늘어나는 경우. (보통은 줄어듬.)
Optimal Algorithm
가장 나중에 사용되는 Page를 Replacement하는 것이 최고의 알고리즘이다.
Optimal Algorithm을 수행하기 위해서는 미래의 reference string을 알아야하므로 현실에는 적용하기 어렵다. 그렇다면 Optimal Algorithm을 어디에 사용할까?
→ 성능 비교를 위해 사용한다.
Least Recently Used (LRU) Algorithm
가장 오래전에 사용된 Page를 Replace하는 알고리즘이다.
이 알고리즘을 사용하기 위해서는 각각의 Page가 사용된 순서를 기록하는 Counter가 필요하다. 그리고 Page를 바꿔야 할 때, Counter를 참조하여 바꾼다.
Couting Algorithm
사용된 횟수를 Couting하는 알고리즘.
각각의 Page를 사용한 횟수를 Counter에 저장한다.
LFU(Least Frequently Used) Algorithm
가장 적게 사용된 Page를 Replace
MFU(Most Frequently Used) Algorithm
가장 많이 사용된 Page를 Replace
'Computer Science > OS' 카테고리의 다른 글
| 9강. 연습문제 (2) | 2023.12.05 |
|---|---|
| 8강. 연습문제 (1) | 2023.12.05 |
| Memory Management (2) (2) | 2023.12.04 |
| Memory Management (1) (1) | 2023.12.04 |
| 7강 연습문제 (0) | 2023.12.02 |