12일차 - Virtual Memory

지난 시간까지는 물리적 메모리에 프로세스를 올리는 방법과 논리적 주소를 물리적 주소로 바꾸는 방법에 대해 배웠다.

오늘은 프로세스가 실행되면 기본적으로 각각의 프로세스가 가지는 논리적 주소공간인 vritual memory에 대해 배웠다.

virtual memory에서 paging기법을 사용하면 어떻게 동작하는지에 대해 알 수 있었다.

 

 

 

1. Demand Paging

demand paging은 요청이 있는 경우에 해당 페이지를 메모리에 올리는 것이다.

demand paging을 사용하면 다음과 같은 장점이 존재한다.

① I/O양의 감소

② memory 사용량 감소

③ 빠른 응답 시간

④ 더 많은 사용자 수용

 

저번 시간에 page table에서 해당 page가 물리적 메모리에 있는지를 알려주기 위해 vaild/invaild bit를 사용한다고 했다.

invaild의 의미는 사용되지 않는 주소 영역인 경우이거나 페이지가 물리적 메모리에 없는 경우를 나타낸다.

처음 page table이 만들어지면 모든 page entry가 invaild로 초기화 되고

만약 주소 변환 요청이 들어왔을 때 해당 페이지가 invaild이면 "page fault"가 발생한다.

지금부터 page fault가 무엇인지 자세히 알아보자.

 

 

2. page fault

page fault는 invaild page에 접근하게 되면 MMU가 trap을 발생시키는 것이다.

page fault가 발생하면 CPU가 프로세스에서 운영체제로 넘어가 kernel mode가 된다.

page fault를 처리하기 위한 절차는 다음과 같다.

① 먼저, 요청한 주소 변환이 합당한 것인지를 판단한다.

예를 들어, 자신의 주소영역이 아닌 곳을 요청했거나 page violation같은 경우가 있다.

이러한 경우에는 다음 단계를 진행하지않고 프로세스를 중단시킨다.

② backing storage(swap storage)에서 물리적 메모리를 올리기 위해서는 물리적 메모리에 빈 공간이 있는지 확인한다.

(만약, 빈 공간이 없으면 빼았는다.)

③ 해당 페이지를 backing storage에서 물리적 메모리로 읽어온다.

- backing storage에서 페이지를 불러오는 것이 끝날 때까지 프로세스는 CPU를 preempt당하여 block상태가 된다.

- backing storage에서 페이지를 읽어오는 것이 끝나면 page table entry에서 vaild/invaild bit를 바꾼다.

- 프로세스가 CPU를 다시 선점하기 위해 ready queue에 프로세스를 넣는다.

④ 프로세스가 CPU를 잡고 다시 running

⑤ 그 전까지 수행하다가 중단되었던 instruction을 재개한다.

 

절차에서 2번을 보면 물리적 메모리에 빈 공간이 없으면 공간을 빼았는다고 했다.

아무거나 막 뺏으면 안되는 것은 당연할텐데 어떤 기준을으로 빼았게 되는 것일까?

 

 

3. Free frame이 없는 경우

위에서 말한 궁금증을 해결해보도록 하자.

빈 공간이 없을 때 페이지를 대체하는 작업이 필요하고 page replacement라고 한다.

page replacement는 어떤 frame을 빼앗아올지 결정해야하고 곧바로 사용하지 않는 page를 쫓아내지 않는 것이 좋다.

page replacement를 구현하기 위해서는 알고리즘이 필요하다.

replacement 알고리즘은 page-default rate를 최소화하는 것이 목표이다.

먼저, optimal algorithm에 대해 알아보자.

- optimal algorithm

optimal algorithm은 미래에 어떠한 page들이 참조되는지를 알고있다는 가정하에 만든 것이다.

실제 시스템에서는 미래를 알 수 없기 때문에 당연히 실제 시스템에서는 사용불가능하다.

어떠한 알고리즘을 쓰더라도 optimal algorithm보다 page default를 적게 낼 수 없다.

그래서 다른 알고리즘의 성능에 대한 upper bound를 제공한다.

 

그러면 실제로 사용되는 알고리즘을 알아보자.

- FIFO(First in first out) Algorithm

말 그대로 먼저 들어온 것을 먼저 내쫓는 것이다.

이 방법을 사용하면 메모리의 크기가 커질수록 성능이 좋아져야하는데 오히려 page default 수가 증가하여 성능이 나빠진다.

이러한 이유로 FIFO Anomaly(Belady's Anomaly)라는 용어가 생겻다.

 

- LRU(Least Recently Used) Algorithm

이 알고리즘은 가장 오래 전에 참조 된 것은 내쫓는 것이다.

 

- LFU(Least Frequently Uesd) Algorithm

이 알고리즘은 참조 횟수가 가장 적은 페이지를 지우는 것이다.

만약 최저 참조 횟수인 page가 여러 개인 경우는 어떻게 할까?

LFU 알고리즘 자체에서는 여러 page 중 랜덤으로 하나를 정해서 내쫓는다.

하지만 성능을 향상시키고 싶으면 가장 오래 전에 참조된 page를 내쫓게 구현하면 될 것이다.

 

 

4. Paging system에서 LRU, LFU가 가능한가?

page replacement를 구현하기 위한 알고리즘에 대해 배웠다.

과연 LRU와 LFU는 paging system에서 사용이 가능할까?

정답부터 말하면 불가능하다.

그 이유는 LRU나 LFU를 구현하기 위해서는 운영체제는 page가 언제 사용되었는지 알아야하고 몇 번 사용됐는지를 알아야한다.

하지만, page가 메모리에 올라가있으면 page에 접근할 때에는 하드웨어적으로만 구현되므로 운영체제에서는 알 방법이 없다.

현재 paging system에서 page replacement를 위해서는 clock Algorithm을 사용한다.

- clock Algorithm

clock algorithm은 LRU와 근사한 알고리즘으로 reference bit를 사용해서 교체 대상 페이지를 선정한다.

circular list에 메모리에 올라가 있는 page를 두고 마치 시계처럼 list를 둘러본다.

reference bitrk 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.

포인터가 이동하는 중에 reference bit가 1인 것이 있으면 0으로 바꾼다.

reference bit가 0인 것을 찾으면 해당 페이지는 교체 후보군에 속하게 되고 한 바퀴를 돌고나서도 0이면 그 때 replace 당한다.

만약 자주 사용되는 페이지라면 다시 포인터가 왔을 때 reference bit가 1이 되있을 것이다.

clock algorithm을 개선한 것은 reference bit와 modified bit(dirty bit)를 함께 사용하는 것이다.

reference bit가 1이면 최근에 참조된 페이지를 의미하고

modified bit가 1이면 최근에 페이지의 내용이 변경(write)된 페이지이다.

여기서 알아야 할 것은

page의 내용이 변경되었다면 물리적 메모리에서 쫓겨나서 backing storage에 page를 저장해두어야하는 I/O작업이 필요하다.

하지만, 내용 변경이 없었다면 page의 복사본이 backing sotrage에 존재하므로 그냥 삭제하기만 하면 된다.

이러한 논리를 알았다면 modified bit가 1인 page를 굳이 reaplace하지 않는 것이 효율적이다.