프로그램을 실행하면 프로그램 전체가 메모리에 로드되지만, 프로그램 전체가 사용되는 일은 드물고, 사용되더라도 동시에 필요한 경우는 더욱 없다. 이렇게 메모리에 일부만 있는 상태로도 프로그램을 구동할 수 있다는 점을 이용해 Virtual Memory를 구현할 수 있다.
Virtual Memory란?
이전 단원에서 메모리 관리를 효율적으로 하기 위해 CPU는 Logical(Virtual) Memory Address라는 가상의 메모리 주소를 사용하고, 이 주소를 실제 RAM의 주소인 Physical Memory에 매핑시켜 사용한다고 했다.
프로그램의 일부만 Physical Memory에 로드되어도 구동할 수 있다면, Virtual Memory가 Physical Memory의 크기와 같을 필요가 없다. Virtual Memory가 더 크더라도 그때그때 필요한 부분만 Physical Memory에 로드하고, 쓰이지 않는 부분은 Paging을 통해 디스크에 임시로 저장하면 된다. 이러면 개발자는 Physical Memory의 크기를 신경 쓰지 않아도 된다.
Virtual Address Space
Virtual Address Space는 프로세스가 어떻게 메모리에 저장되어 있는지 표현하는 가상의 주소이다.
Virtual Address는 0부터 max까지 연속된 주소로 나타나나 실제로 Physical Memory에서는 연속적인 주소가 아닐 수 있다.
Virtual Address와 Physical Address는 MMU가 매핑시켜준다.
프로세스가 Dynamic Memory Space가 더 필요하다고 하면, 추가 Frame을 할당해 주는 것이 아니라 우선은 새로운 Virtual Address 범위만 할당해 주고 필요한 경우에만 Physical Memory에 로드한다.
Shared Library
Shared Library를 사용할 때는 프로세스의 Virtual Address가 같은 Physical Address를 가리키는 방식으로 구현된다.
Copy-on-Write
UNIX에서는 fork()를 통해 Parent의 복제본 Child를 생성하고, 새 프로세스를 실행할 때는 fork에 이어 exec를 실행한다고 했다.
Child 프로세스가 Parent의 메모리와 같은 값을 읽기만 하는 경우에는 새 메모리 공간을 할당해 주는 것은 낭비이다.
Copy-on-Write 방식은 우선 fork가 실행되면 생성된 Child는 Parent의 메모리를 공유한다. 그리고 exec나 Memory Write 명령이 있는 경우 그때야 공유된 부분 중 Write 된 Page의 복사본을 할당해 준다. 이러면 Parent와 다른 Page만 따로 저장해 메모리를 절약할 수 있다.
Demand Paging
Virtual Memory는 Demanding Paging을 통해 적용된다.
Demanding Paging이란 프로세스 실행 도중 요청이 있을 때만 Page를 로드하는 것이다.
메모리가 꽉 찬 경우 Page Swapping을 통해 Page를 교체한다.
이러한 방식은
- 적은 I/O
- 적은 메모리 요구치
- 빠른 응답 속도
- 더 많은 사용자 수용 가능
이라는 장점이 있다.
Valid-Invalid Bit
Paging과 비슷하게 Valid-Invalid Bit를 도입하나, 단순히 메모리 보호의 목적이 아니다.
Valid -Invalid Bit를 통해 현재 Physical Memory에 해당 Page가 있는지(1) 확인하고, 없다면(0) Page Fault를 일으켜 다음 단계로 넘어간다.
Page Fault
- Page를 검색 했는데 Invalid Bit이 검출되면
- Trap으로 Page Fault가 일어난다.
- OS는 Page가 Disk에 있는지 확인한다.
- Disk에 없다면 Abort 한다.
- Disk에 있다면
- Physical Memory에서 빈 프레임을 찾아 Page를 로드한다.
- 로드한 정보에 맞게 Page Table을 수정하고
- 중단된 명령어를 다시 실행한다.
Performance of Demanding Page
Physical Memory에 Page가 없다면 6단계에 이르는 귀찮은 작업을 해야 한다.
Page Fault에 소요되는 시간인 Page Fault Time은 Page Fault 발생 시간, Swap In 시간, 명령어 재시작 시간 (+필요하다면 Swap Out 시간)이 포함된 긴 시간이다.
이 작업이 적게 일어날수록 Demanding Page의 성능이 향상된다.
Page Fault가 일어날 확률인 Page Fault Rate$0 \leq p \leq1$에 대해,
($p=0$이면 Page Fault가 없음,$p=1$이면 항상 Page Fault)
$EAT\,=\,(1\,-\,p)\times MemoryAccessTime\,+\,p\,\times\,PageFaultTime$
이다.
Frame이 늘어나면 Page Fault가 줄어든다. 그러나 일정 수치 아래로 내려가지 않는다.
Page Replacement
Physical Memory가 꽉 차면 필요한 Page를 로드하기 위해 사용 중이 아닌 다른 Page와 교체하는 Page Replacement를 수행해야 한다.
Page Replacement는 다음 단계로 진행된다.
- 디스크에서 필요한 Page를 찾는다.
- 빈 Frame을 찾는다.
- Frame이 있으면 사용한다.
- Frame이 없으면 Victim Frame을 선택한다.
- Victim Frame을 디스크에 적는다.
- 필요한 Page를 Victim Frame의 자리에 넣고, Page Table을 업데이트한다.
- 프로세스를 재개한다.
2-2에서 Victim Frame을 신중하게 고르지 않으면 자주 쓰이는 Page가 Physical Memory와 디스크를 계속해서 들락날락하며 Page Fault를 일으키는 참사가 일어날 수 있다.
Page Fault가 적게 일어나도록 하는 Page를 찾아 선정하는 알고리즘을 고려해야 한다.
알고리즘을 살펴보기 전에,
알고리즘을 Reference String을 통해 평가할 것이다.
Reference String은 프로세스가 필요한 Page이다.
1, 2, 4, 6, 1, 3위 Reference String은 프로세스가 1번->2번->4번->6번->1번->3번 페이지가 필요했다는 뜻이다.
FIFO Algorithm
FIFO는 먼저 Page Frame에 들어온 Page가 먼저 나가는 알고리즘이다.
Page Replacement가 필요할 때 Frame에서 가장 오래된 Page가 나간다.
쉽지만 항상 성능이 좋다고 할 수는 없다.
Belady's Anomaly
보통 Frame이 많아질수록 Page Fault가 줄어든다.
그러나 FIFO 알고리즘은 이상하게 Frame이 많아지면 Page Fault가 증가하는 구간이 존재하는데, 이걸 Belady's Anomaly라고 한다.
Optimal Algorithm
Optimal (Minimum) 알고리즘은 가장 오랫동안 사용되지 않을 Page를 교체하는 알고리즘이다.
가장 낮은 Page Fault Rate를 가진 가장 효율적인 알고리즘으로, Belady's Anomaly가 일어나는 경우가 없다.
그러나 상식적으로 오랫동안 사용되지 않을 Page를 알 수 없다.
미래를 예측할 수는 없기 때문에 Optimal 알고리즘은 Replacement 알고리즘의 평가 척도로만 사용된다.
Least Recently Used Algorithm
가장 오랫동안 사용되지 않은 Page를 교체한다.
자주 사용되는 Page면 최근에도 사용했을 것이고, 오랫동안 쓰지 않았다는 것은 자주 사용하지 않을 가능성이 높은 Page라는 뜻일 수도 있다.
상당히 괜찮은 성능을 보여준다.
그런데 사용되지 않은 기간을 어떻게 구분할까?
- Counter : Page Table의 최근에 사용된 시간(Clock)을 기록하고, 가장 작은 값을 대체한다.
- Stack : Stack을 구현하고, Page를 참조하면 Stack의 맨 위로 올린다. Stack 가장 아래 있는 값을 대체한다. (엄밀히 따지면 Stack 중간의 값이 참조되면 맨 위로 올라가므로 Stack은 아니다.)
- Reference Bit Algorithm : 모든 Page에 Reference Bit를 두고(0), 참조되면 1로 기록한다. Bit가 0인 Page 중 하나를 교체한다.
- Additional Reference Bit Algorithm : 8비트를 여러 개 사용한다. 제일 앞 비트에 참조 여부를 기록한다. 정기적으로 비트를 한 칸씩 밀어 8사이클 동안의 참조 로그를 기록하고 가장 작은 값을 가진 Page를 교체한다.
- Second Chance Algorithm : 로드된 Page의 정보를 Circular List로 저장하고, Reference Bit를 1로 설정한다. Page를 교체해야 하면 List를 순회하며 Page를 찾는데 1이면 0으로 바꾸고 다음 Page로 넘어간다. 0이면 교체한다.
- Enhanced Second Chance Algorithm : 비트를 2개 저장한다. (Used, Modified)로 사용과 수정 여부를 모두 고려한다.
Counting Base Algorithm
Page마다 Counter를 둬 사용 횟수를 기록한다.
- Least Frequently Used : 적게 사용한 Page를 교체한다. (여태까지 안 썼잖아)
- Most Frequently Used : 자주 사용한 Page를 교체한다. (이제는 안 쓰겠지)
Frame Allocation
프로세스에 무분별하게 메모리를 할당하다 보면 한 프로세스가 모든 메모리를 독점하거나, 특정 프로세스는 할당받지 못하는 등의 문제가 일어날 수 있다.
운영체제는 프로세스가 효율적으로 메모리를 활용하기 위해 프로세스에 할당하는 Frame의 수를 정한다.
프로세스에는 최소한의 Frame은 할당해야 한다. 할당된 Frame이 줄어들수록 Page Fault가 늘어나 성능이 감소하기 때문이다. 그리고 어느 정도의 Frame은 확보가 되어 하나의 Instruction 실행에 필요한 Page는 모두 로드할 수 있어야 Instruction 실행 중에 Page Fault가 발생하지 않는다. 이 최소 크기는 컴퓨터 아키텍처가 결정한다.
Frame Allocation Algorithm
- Equal Allocation : 쉽게 프로세스에 같은 수의 Frame을 할당해 준다. 100 Frame과 5 프로세스가 있으면 20개씩 할당한다.
- Proportional Allocation : 프로세스의 크기에 비례하게 할당해 준다.
- Priority Allocation : 프로세스의 우선순위에 비례하게 할당해 준다.
이런 전략은 Multiprogramming Level에 따라 달라진다.
Global vs Local Replacement
프로세스 P가 Page Fault를 일으켰다.
Frame 교체를 위해 Victim Frame을 선정해야 한다.
이때도 두 가지 전략이 있다.
- Global Replacement : Frame 전체에서 Victim Frame을 선정한다.
- 한 프로세스의 Page Fault Rate를 제어할 수가 없다.
- Throughput이 높고, 자주 쓰이는 방식이다.
- Local Replacement : 프로세스가 할당받은 Frame 중에서 Victim Frame을 선정한다.
Thrashing
프로세스가 최소한의 Frame도 확보하지 못하면 어떻게 될까?
프로세스가 충분한 Page를 확보하지 못한다면, (Global Replacement라는 가정하에) Page Fault Rate가 급격하게 증가한다.
프로세스가 실행보다 Swapping에 더 많은 시간을 쓰는 현상을 Thrashing이라고 한다.
실행 중인 프로세스가 증가할 수록 남아 있는 Frame이 줄어들면서 Thrashing이 자주 일어나게 된다.
Local Replacement가 Thrashing을 줄일 수는 있지만 완전히 해결하지는 못한다.
Locality
Thrashing을 막기 위해 프로세스가 필요한 만큼의 Frame은 할당해 줘야 한다. 그런데 프로세스가 몇 개의 Frame이 필요한 지는 어떻게 알까?
실제로 프로세스가 사용하는 Frame의 수를 분석해 보니 Locality라는 특성을 보였다.
즉, 특정 시간에 특정 범위의 메모리를 참조하는 성질이 있다.
이를 통해 특정 시간에 따라 사용하는 Page의 개수만큼(살짝 크게) Frame을 할당해 주면 된다는 결론이 도출된다.
Working Set Model
Working Set Model은 Locality를 전제로 한다.
Locality에 따르면 특정 시간에 주로 특정 범위의 메모리를 사용한다.
그러면 지금까지 $\Delta$시간 동안 사용된 Page는 프로세스가 특정 시간 동안 사용하는 Page라고 볼 수 있다.
$\delta$시간 동안 사용한 Page 개수만큼 할당해 주면 되지 않을까?
Working Set은 $\Delta$ 시간 동안 지금까지 사용한 Page의 집합이다.
$\Delta$가 너무 작으면 Locality가 잘릴 것이다.
$\Delta$가 너무 크면 여러 Locality가 포함될 것이다.
$\Delta=\infty$이면 전체 프로그램이다.
운영체제는 Working Set의 크기만큼 Frame을 할당해 준다.
Working Set의 크기보다 작으면 Thrashing이 일어난다.
Page-Fault Frequency Scheme
적당한 수준의 Page Fault Rate와 Frame 개수를 유지하는 방식이다.
Page Fault Rate의 적정 범위를 정하고 이 범위를 벗어나는지 관찰한다.
Page Fault가 너무 많으면 Frame이 부족한 것이므로 Frame을 더 할당해 준다.
Page Fault가 너무 적으면 Frame이 과하게 할당된 것이므로 Frame을 줄인다.