8주차. 가상메모리(1) _ Demanding Page + Page 교체 알고리즘 (FIFO, LRU, LFU)

Demanding Page

실제로 필요할 때, page를 메모리에 올리는 기법으로 아래와 같은 장점이 있다

• I/O 양의 감소
• Memory 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용

Vaild / Invalid bit의 사용

• invalid의 의미는?
  → 사용되지 않는 주소영역인 경우 (참고로 가상 메모리 대부분은 사용하지 않는 공간이다)
  → Page가 현재 물리적 메모리에 없는 경우 (Swap Area에 있는 경우일 것이다)
• 처음에는 모든 Page Entry가 invaild로 초기화 되어있다
• address translation 시에 invaild bit가 set되어 있으면?
  → "Page Fault"
• 즉, 현재 메모리에 올라와 있지 않은 것이므로, swap area에서 메모리에 올려야하는 것이고, 이는 I/O작업 이므로 Fage Fault를 발생시킨다.
  소프트웨어 인터럽트를 발생시켜서 OS에게 CPU 권한을 돌려주고, I/O 작업을 통해 swap area에서 데이터를 가져오게 된다.

Memory에 없는 Page의 Page Table

• 가상 메모리 공간을 보면 A~H까지 Page가 존재하는데, 실제로 사용되는 부분은 A~F Page이다.
• 이 중에서 0, 2, 5번인 A, C, F page만 Page Table에 적재가 되어있고, 그 부분만 vaild bit가 체크되어있으며 page 번호에 맞게 물리적 메모리에 적재된 frame 번호와 vaild bit가 쌍으로 존재하고 있다.
• 실제 물리적 메모리 공간도 page table과 동일하게 A, C, F page만 존재하고 있으며, A, C, F 뿐만 아니라 나머지 사용되는 page들은 Swap Area에 있는 것을 볼 수 있다.
• 메모리에 없는 page들은 page table이 invaild bit로 체크되어 있다.

→ 즉, 초기에 page table은 모두 invaild로 체크되어 있고 실제로 적재도 되어있지 않지만 해당 page를 사용하면 swap area에서 꺼내와서 적재를 하게 되고 page table에도 적재가 되면서 vaild bit를 갖게 된다.

Page Fault 및 과정

Page Table에 접근했는데 invaild bit일 경우 발생

1. invalid page를 접근하면 MMU가 trap을 발생시킨다. (page fault trap)
2. 그러면 Kernel Mode로 돌아가게 되고 page fault handler가 invoke된다.
3. page handler는 먼저 접근하는 주소에 대해서 bad address, protection violation인 경우인지 확인한다.
   • 잘못된 접근인 경우 ⇒ process를 abort시킨다.
     (주어진 메모리 주소 범위를 벗어난 접근, 권한이 부족한 경우, 사용하지 않는 공간인 경우 등이 있다)
   • 제대로된 접근인 경우 ⇒ 해당 page를 메모리에 올리기 위해 메모리에 page공간을 확보한다 (자리가 없다면 뺏는다)
4. swap area에 가서 원하는 memory를 읽어온다.
   이때, process는 그동안 preempt 당하고 block상태가 된다. 그동안 disk를 read하고 끝났다는 인터럽트가 발생하면 메모리에 읽어온 데이터를 메모리에 넣어놓고 page table의 invaild를 valid bit로 바꿔준다.
5. 프로세스는 다시 ready상태가 되어서 ready Queue에 들어가게되고 cpu를 다시 잡기위해 기다린다.
6. cpu가 다시 프로세스를 잡게되고, 메모리에 없어서 진행하지 못했던 instruction을 마저 실행하게 된다.

Demanding Page 기법의 성능

일반적으로 page를 요청했을 때 얼마나 자주 Paging fault가 일어나는지가 성능을 좌우한다. 보통 95%이상 page table에서 처리하게 된다.

Page Fault Rate: 0 ≤ p ≤ 1.0

p = 0 인 경우: page fault가 발생하지 않고 100% page table에서 처리

p = 1 인 경우: 모든 page 요청에 대해 page fault가 발생한 경우

 

Effective Access Time

= ( 1 - p ) * memory access time
+ p * (
OS & HW page fault overhead (Context switching 비용이 예상된다)
+ swap page out (올릴 메모리 공간이 없으면)
+ swap page in (메모리에 가져온 데이터 올림)
+ OS & HW restart overhead
)

---

Page Replacement Algorithm

물리적 메모리 공간에 Free frame이 없는 경우 Page 공간 확보를 위한 Page Replacement이 일어나는데 이를 최적으로 하기 위한 알고리즘

• 어떤 frame을 memory에서 빼앗아올지 결정해야 한다.
• 곧바로 사용되지 않을 page를 쫓아내야 한다.
• 동일한 페이지가 여러번 페이지에서 쫓겨나고 다시 들어올 수 있다.
• Page Fault Rate를 최소화 하는 것이 목표이다.

page replacement 발생 도식화

→ 희생당할 page를 swap area로 내쫓고 page table에 invaild bit로 바꾸고 필요한 page를 대신 넣어주고 valid bit로 바꿔준다.

Offline Optimal Algorithm

• 미래를 전부 안다고 가정하고 수행하는 알고리즘 방식.
• 현재 선택할 victim page를 미래를 참조해서 고른다.
• 다른 알고리즘의 성능에 대한 upper bound를 제공한다.
• Belady's Optimal algorithm, MIN, OPT라고 불린다.

optimal algorithm 방식 때 page fault 발생 표

위에서 1 ~ 4번까지는 page table에 없으므로 가져왔다가, 5번부터 자리가 없어서 제거할 page를 골라야하는데, 다음 수행 때 불릴 page를 확인해서 가장 늦게 불리는 4번 page를 제거하여 넣게 된다

FIFO Algorithm

• 먼저 들어온 page를 먼저 내쫓는 알고리즘 방식

FIFO Anomaly (특이점)

• More Frame ≠ Less Page Fault
• page를 보관해주는 frame공간을 더 늘려주는데도 오히려 Page Fault가 늘어나는 기이한 현상이 발생한다.

LRU (Least Recently Used) Algorithm

• 최근에 가장 적게 사용된, 즉 사용된지 가장 오래전 page를 쫓아내는 알고리즘 방식.

5번 page가 들어올때 방금까지 가장 적게 사용된 3번이 내쫓기고 그자리에 들어오게되는 모습이다.

FIFO는 최근에 사용되었든 말든 메모리에 먼저 들어온 순서로 내쫓는 것이고, LRU는 최근까지 가장 적게 사용된 것을 내쫓는 것이다.

LFU (Least Frequently Used) Algorithm

• 참조 횟수가 가장 적은 page를 쫓아내는 알고리즘 방식.
• 가장 적게 참조한 횟수가 동일한 page가 여러개 있으면 → LFU는 임의로 선정하지만, 성능향상을 위해 최근 참조가 적은 page를 고르는 방식으로 혼합할 수 있다.

LRU & LFU 알고리즘 비교

LRU 알고리즘 특징

• 해당 page가 얼마나 최근까지 참조되었는지는 알지만, 그 정도(횟수)를 알지는 못한다.

문제점

• 만약 1번 page가 100번 참조되고 이후에 2번 page가 한 번씩 참조되어도 자리가 없다면 100번 참조된 1번 페이지를 지우게 될 것이다.
• 따라서 빈도수는 확인하지 못하고, 최근 사용 여부만 확인한다.

 

LFU 알고리즘 특징

• 반대로, LFU는 해당 page가 얼마나 자주 참조되었는지는 알지만, 얼마나 최근에 참조된 것인지는 알지 못한다.

문제점

• 만약 1번 page가 1시간 전에 10번참조되고 이후 2번 page가 1분전에 9번 참조되었을지라도, 자리가 없다면 더 적게 참조된 1분전에 9번 참조된 2번 page를 지우게 된다.
• 따라서 최근에 사용됐는지 여부는 모르고, 빈도수만 확인한다.

 

LRU 알고리즘 구현

• 링크드 리스트 형태로 구성되어서 참조되는 알고리즘을 MRU page로 맨 앞으로 땡겨주게 된다.
• page가 사용 될 때 해당 page를 바로 접근해서 맨앞에 연결시켜 주면되고, 쫓아낼 때는 LRU에 있는 마지막 page를 쫓아내면 되므로 O(1)의 시간복잡도를 갖는다.

LFU 알고리즘 구현

• LFU도 똑같이 링크드 리스트처럼 한줄로 줄을 세우고 참조때마다 땡기면서 하면 좋을것 같지만 그렇게 할 수 없다.
• LRU는 참조가 되는 순간 가장 최근에 사용된 page로서 우선순위가 가장 높아지는 반면에, LFU는 사용 빈도를 기준으로 줄을 세워야 하므로 다른 Page의 참조 횟수를 비교해서 줄을 세워야한다. 따라서 LRU처럼 구현할 수가 없다.
• 따라서 Heap 구조로 만들게 된다. 가장 맨 위에 가장 적게 참조된 우선순위가 낮은 page를 놔두고 참조 횟수가 높아질 수록 밑으로 내려가게 한다. 이렇게 하므로서 맨위 노드가 맨 아래까지 logN번의 비교를 통해 내려가는 것이 가능하다.
  이때 Heap은 완전 이진 트리로 자식이 2개 있는 트리 모양이 된다.
• page가 사용되면 자신의 자식과 참조 횟수를 비교한다. 자신의 참조 횟수가 더 높다면 자식과 교환을 하고 자식 노드가 없을 때 까지 반복한다. 쫒아낼 때는 Heap의 루트 노드를 쫒아내게 된다. 루트를 다시 채울 때는 가장 아래 오른쪽 노드를 위로 올려서 완전 이진 트리를 재구성한다.