[week09] KOCW 운영체제(반효경교수님) - Virtual Memory 1

Virtual Memory 1

주소변환은 운영체제가 관여하지 않았는데, virtual memory 기법은 전적으로 운영체제가 관여한다.

Demand paging

실제로 필요할 때 page를 메모리에 올린다.

• I/O 양의 감소
• memory 사용량 감소
• 더 빠른 응답 시간
• 더 많은 사용자(프로그램) 수용

Vaild / Invalid bit의 사용

당장 필요한 A,C,F는 physical memory에 올라가 있고(valid), 그렇지 않은 부분은 backing store에 내려가 있다(invalid).

invalid의 의미

• 사용되지 않는 주소 영역인 경우
• 페이지가 물리적 메모리에 없는 경우

처음에는 모든 page entry가 invalid로 초기화

address translation(주소변환)시에 invalid bit이 set 되어있다면 “page fault” 가 일어남

• 사용자 프로세스가 해결하지 못하므로 운영체제에게 CPU 제어권이 넘어감(page fault trap이 걸림 - 일종의 software interrupt)

Page Fault steps

invalid page를 접근하면 MMU(주소변환해주는 hardware)가 trap을 발생시킴(page fault trap)

kernel mode로 들어가서 page fault handler가 invoke 됨

다음과 같은 순서로 page fault를 처리함

1. invaild reference?(잘못된 요청이 아닌지 확인)(ex: bad address, protection violation) 잘못된 요청이면 abort process로 종료
2. Get an empty page frame(없으면 뺏어온다 - replace).
3. 해당 page를 disk에서 memory로 읽어온다.
   1. disk I/O가 끝나기까지 이 프로세스는 CPU를 선점(preempt)당하고(blocked state) ready state의 가장 우선순위 높은 프로세스가 CPU를 가져감
   2. disk read가 끝나면 page tables entry 기록, vaild/invalid bit = “valid”
   3. ready queue에 process를 insert → dispatch later
4. 이 프로세스가 CPU를 잡고 다시 running
5. 중단되었던 instruction 재개

Performance of Demand Paging

page fault가 났을 때 disk로의 접근은 대단히 오래걸리는 작업이다. page fault가 얼마나 나느냐에 따라 메모리 접근시간이 크게 차이난다.

대부분의 경우 page fault가 나지 않는다(p = 0.0x) 그러나 page fault가 한번 나면 overhead가 매우매우 크다.

Free frame이 없는 경우

page replacement

• 어떤 frame을 빼앗아올지 결정해야 함
• 동일한 page가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있다.

replacement algorithm

• page-fault rate을 최소화하는 것이 목표
• 알고리즘의 평가
  • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사.
  • refrence string 예시 : 1,2,3,4,1,2,5,1,2,3,4,5 (page)

Page Replacement

Optimal Algorithm

MIN(OPT) : 미래에 무엇이 들어올지 다 알고있다고 가정한다.

가장 먼 미래에 참조되는 page를 replace한다.

이건 실제로는 쓰일 수 없고(미래를 예측할 수 없다) 다른 알고리즘의 성능에 대한 upper bound를 제공한다.

FIFO(First In First Out) Algorithm

FIFO : 먼저 들어온 것을 먼저 내쫓음

FIFO Anomaly : 메모리 frame을 늘려줬는데 성능이 더 나빠지는 경우가 발생할 수 있다.

LRU(Least Recently Used) Algorithm

미래를 아는 가장 합리적인 방법은 과거를 보는 것이다.

LRU: 가장 오래 전에 참조된 것을 지움

LFU(Least Frequently Used) Algorithm

LFU: 참조 횟수(reference count)가 가장 적은 page를 지움

최저 참조 횟수인 page가 여러개 있는 경우

• LFU 알고리즘 자체에서는 여러 page중 임의의 page를 지움
• 성능 향상을 위해 가장 오래 전에 참조된 page를 지우도록 구현도 가능

장점

• LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 더 정확히 반영가능

단점

• 참조 시점의 최근성을 반영하지 못함
• LRU보다 구현이 복잡함

LRU와 LFU 알고리즘 예제

LRU와 LFU 알고리즘의 구현

LRU는 한 줄로 줄세워서 linked list 형태로 구현 → O(1)

LFU는 heap 구조를 사용해서 tree 형태로 구현 → O(log n)