Virtual Memory)
기존에는 프로세스가 실행되는 코드의 전체를 메모리에 로드해야 했다.
즉 이것은 메모리 용량보다 큰 프로그램은 실행시키지 못한다는 의미다.
만약에 게임의 용량이 40gb면 메모리에 한 번에 40gb를 올려놔야 실행 가능하다는 의미이다.
그런데 대부분 가정집 컴퓨터의 램은 8 ~ 32gb 사이이다. 그러나 우리는 100gb짜리 게임이나 영상파일도 실행 가능하다.
가상 메모리는 이러한 물리적 메모리 크기의 한계를 극복하기 위해서 나왔다.
프로세스를 실행할 때 필요한 부분만 일부 메모리에 로드하고 나머지는 디스크에 둔다.
결과적으로 메모리에 작은 양의 주소 공간만 있으면 충분히 프로세스 수행이 가능하고 더 많은 프로그램을 동시에 실행할 수 있게 된다.
이처럼 현재 필요한 page만 메모리에 올리는 것을 Demand Paging이라고 한다.
이는 CPU가 Virtual Address를 MMU에 전달하면 MMU에서 Physical Address를 Memory에 Mapping 한다.
MMU가 물리 주소를 매번 확인하기 위해 메모리를 왔다 갔다 해야 하는 과정을 좀 더 효율적으로 하게 하기 위해서 사용되는 것이 TLB이다.
TLB란 최근 물리 주소로 변환된 가상 주소 정보를 저장하여 페이지 정보를 캐시 할 수 있는 하드웨어다.
Demand Paging)
실제로 필요할 때 page를 메모리에 올린다.
CPU Utilization이 높아지고 더 많은 프로세스를 수용 가능하다.
Valid - Invalid Bit)
처음에 메모리의 모든 page를 invalid로 초기화한다. 만약 읽어드린 메모리가 사용되지 않은 주소 영역일 경우, 페이지가 물리적으로 메모리에 존재하지 않을 경우 address translation시에 invalid bit이라면 page falut가 발생한다.
Page Fault)
1. page table에 해당 reference가 valid or invalid 인지 확인한다.(user mode)
2. invalid 하면 Trap to OS(SW 인터럽트)가 된다.(user mode -> kernel mode)
3. free frame을 찾는다. (kernel mode) 없다면 victim page를 선택한다.
4. 운영체제는 참조된 page를 디스크에서 메모리로 로드한다. 이때 I/O 서비스에게 cpu를 뺏긴다 (kernel mode)
5. validation bit를 v로 바꾸고 table을 리셋한다. (kernel mode)
6. instruction을 재실행하면 process가 메모리에 접근이 가능하다. (kernel mode)
Page Replacement)
만약에 Free Frames가 없는 경우에는 어떻게 할까?
기존 할당하고 있던 page를 알고리즘에 맞게 교체해줘야 한다. 이때 해제되는 frame을 victim frame이라고 한다.
알고리즘을 사용하는 근본적인 이유는 lowest page fault rate를 달성하기 위해서다.
<Optimal Algorithm>
가장 먼 미래에 참조되는 page를 대체하는 방법으로 항상 최적의 결과를 보장한다.
다만 미래의 참조를 모두 알고 있어야 하므로 실제 사용은 어렵다.
Optimal Algorithm에 따라서 page fault가 6회 발생하고 이것이 최적이다.
<First In First Out>
선입선출 구조를 가진 방법이다. 평등하며, 구현이 쉽다. 다만 항상 필요한 page가 존재할 수 도 있는데 이럴 경우 효율이 크게 떨어진다.
특정 구간에서는 오히려 page fault가 늘어나는 경우도 있다.
<LRU Algorithm>
가장 오래전에 참조된 것을 지우는 방법이다.
optimal에 근접하며, Belady's Anomaly가 발생하지 않는다. 단점은 구현이 어렵고 접근되는 빈도를 고려하지 않는다.
<LFU Algorithm>
참조 횟수가 가장 적은 page를 지우는 방법이다.
LRU에 비해 장기적인 시간 규모를 보기 때문에 인기도를 반영할 수 있지만, 최근성은 반영하지 못한다.
최저 참조 횟수가 동일한 경우 임의로 page를 선정한다.
<Second Chance Algorithm>
LRU와 LFU는 실제로 paging system을 구현하는 것에 적합하지 않다.
메모리는 실시간으로 계속 갱신되기 때문에 참조한 지 오래되거나, 참조 횟수가 적은 페이지를 운영체제가 정확하게 알기 힘들다.
따라서 Second Chance Algorithm == Clock Algorithm을 사용하고 이는 LRU Approximation의 한 종류다.
최근에 참조되었는지 여부를 나타내는 Reference Bit이라는 정보를 사용한다.
Reference bit가 0인 것을 찾을 때까지 시계처럼 한 바퀴씩 포인터를 이동하다가 0인 것을 찾으면 해당 page를 교체하는 방식이다.
만약 Reference bit가 1인 page를 만나면 0으로 바꿔준다.
한 바퀴 되돌아와서도(Second Chance) 여전히 0이면 해당 page를 교체한다. 다시 bit가 1로 바뀌어있다면 그만큼 자주 사용되는 page라는 의미인 것이다.
이를 조금 더 개선한 방식으로 Enhanced Second Chance Algorithm이 있는데, 최근에 해당 page가 변경이 되었는지를 나타내는 Modified bit(dirty bit)가 추가된 것이다.
Modified bit가 1이라면 page가 변경되었기 때문에 교체를 하면 디스크에 해당 내용을 반영해야 한다. 즉, I/O 작업이 동반되므로 시간이 오래 걸린다.
따라서 "Reference bit == 0? → Modified bit == 0?" 순서로 우선순위를 가진다.
(레퍼런스, dirty bit) 순서로 존재하며 둘 다 (0,0) 일 경우 최근에 사용되지도 않고 수정되지도 않았다는 의미를 가지기 때문에 우선순위가 가장 낮고 따라서 교체하기에 최적의 page를 의미한다. 반대로 (1,1)의 경우 최근에 사용됐고 해당 page가 최근에 수정된 이력이 있는 것이기 때문에 우선순위가 가장 높다.
Allocation of Frames)
프로세스마다 얼마큼의 page frame을 해당해야 할지 생각해볼 필요가 있다.usable 한 frame의 총 양보다 많거나 적게 할당해서는 안되고 loop를 구성하는 page들은 한 번에 할당해야 page fault가 매 loop마다 발생하는 것을 방지할 수 있다.
page frame은 프로세스마다 균일하게 할당하거나 특정 기준에 따라 할당하는 방법으로 나뉜다.균일 = frame 수 / 프로세스 수특정 기준 = 프로세스의 크기 or 우선순위 등등..
page fault를 발생시켰을 때 대체될 frame 그룹에 따라 Global Replacement와 Local Replacement로 나뉜다.
Global Replacement: Replace 할 때 다른 프로세스에 할당된 frame을 빼앗아올 수 있다. 가장 흔하게 사용함
Local Replacement: 자신에게 할당된 frame 내에서 교체, 쉬는 메모리 사용이 불가능하기에 비효율적
Thrashing)
Thrashing은 프로세스가 원활한 수행에 필요한 최소한의 page frame을 할당받지 못해서, 실행보다 Swapping 하는데 더 많은 시간을 소모하는 현상이다.
page fault rate가 매우 높아지고 CPU 효율성이 낮아진다.
Thrashing이 발생하는 과정은 다음과 같다.
1. page가 부족하여 page fault가 증가한다.
2. Swapping(I/O) 작업이 증가하여 CPU 효율성(Utilization)이 감소한다.
3. OS는 Multiprogramming Degree를 높여야 한다고 판단하여 또 다른 프로세스를 시스템에 추가한다.
4. 프로세스당 할당된 page frame이 더욱 감소하여 page fault가 더 증가한다.
5. 프로세스는 Swapping으로 인해 매우 바빠져서 대부분의 시간에 CPU는 한가해진다.
Trashing Prevention)
Thrashing을 예방하기 위해서는 프로세스에게 frame을 필요한 만큼 많이 제공해야 한다.
그렇다면 어떻게 프로세스가 필요한 frame의 양을 알 수 있을까?
1. Working-Set Model
Working Set Model은 가능한 최대 Multiprogramming Degree를 유지하면서 Thrashing을 막는 방법이다.
Locality of reference(참조 지역성의 원리)는 프로세스가 특정 시간 동안 일정 장소를 집중적으로 참조하는 성질을 말한다.
이 Locality에 기반하여 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와있어야 하는 page들의 집합을 Working set이라고 한다.
Working set은 Working set window라는 고정된 page 참조 횟수(시간)로 구한다.
WSSi = working set size of process Pi
즉, 가장 최근 window에서 프로세스 Pi가 참조한 page의 총 개수라고 정의하자.
(만약 window의 크기가 너무 작다면 전체적인 locality를 다룰 수 없고, 너무 크다면 여러 locality를 포함하게 된다. 크기가 무한이라면 프로그램 전체를 포함할 것이다)
이때, ∑WSSi가 필요한 frame의 총 수가 되고, 이 값이 총 사용 가능한 frame의 수보다 더 크다면 Thrashing이 발생하게 된다.
따라서 운영체제가 지속적으로 각 프로세스의 Working set을 지켜보면서 충분한 frame을 할당해주고, ∑WSSi가 총 사용 가능한 frame 수보다 크다면 프로세스 중에서 하나를 종료시키고 해당 프로세스의 frame을 다른 프로세스들에게 할당해준다. 이를 통해 Multiprogramming Degree를 줄여준다.
2. PFF(Page-Fault Frequency) Scheme
PFF는 page fault의 상한 값과 하한 값을 두고, page fault rate가 상한 값을 넘으면 frame을 더 할당하고, 하한 값보다 낮아지면 할당된 frame 수를 줄이는 방법이다.
'Computer Science > 운영체제' 카테고리의 다른 글
| chapter 09. Main Memory (0) | 2022.06.04 |
|---|---|
| Chapter 08. Deadlocks (0) | 2022.06.03 |
| Chapter 07-2. Windows API (0) | 2022.06.02 |
| Chapter 07-1. Synchronization Examples (0) | 2022.06.02 |
| Chapter 06. Synchronization Tools (0) | 2022.06.01 |
