가상 메모리(Virtual Memory)

안녕하세요 dely입니다:)

오늘은 가상 메모리(Virtual Memory)에 대해 정리해보겠습니다.

이전 포스팅에서 정리한 페이징 기법을 기반으로 메모리관리를 하는 것을 기반으로 합니다.

 

1. 요구 페이징(Demand Paging)

Demand Paging은 프로그램 전체를 메모리에 올리는 것이 아니라

요청받은 페이지가 있을 때 그 페이지만 메모리에 올리는 것을 말합니다

 

I/O 양이 감소되고, 메모리 사용량도 감소하여

더 빠른 응답시간과 더 많은 사용자를 받을 수 있게 됩니다.

 

논리메모리에서 물리메모리로 넘어갈 때 페이지 테이블을 통해

메모리 주소를 관리하게 되는데,

물리메모리에 올라간 페이지는 페이지 테이블(Page table)에서 valid로 설정하게 됩니다.

 

2. 페이지 부재(Page Fault)

만약 요청한 페이지가 invalid page라면 MMU가 trap을 발생시키게 됩니다.

이것을 page fault trap이라고 합니다.

Page Fault가 되면 cpu는 운영체제에게 넘어가게 됩니다.

 

커널모드로 가서 page fault handler가 발생되고,

주소가 잘못되었거나, 접근권한이 잘못되었는지 확인하여 만약 잘못되었다면 abort가 됩니다.

만약 아니라면 비어있는 페이지를 찾게 되고

빈 페이지가 없으면 기존의 페이지 중에서 하나를 뺏어오게 됩니다.(Page replacement)

그리고 해당 페이지를 disk에서 메모리로 읽어옵니다.

 

Disk I/O 시간은 매우 느리기 때문에 CPU는 다른 ready queue에 있는 프로세스를 실행하고,

이후 disk에서 페이지를 가져오게 되면 페이지 테이블에 올려두고 해당 위치 valid-invalid bit를 valid로 바꿉니다.

그리고 ready queue에서 기다리다가 CPU를 다시 얻어서 페이지 처리를 하게 됩니다.

 

3. 요구 페이징의 성능(Performance of Demand Paging)

Demand Paging의 성능은 Page Fault가 일어나는 비율에 따라 달라지게 됩니다.

메모리에 없을 때 Disk I/O를 해야하는데 그 시간이 매우 느리기 때문입니다.

성능을 계산하는 식은 다음과 같습니다.

 

 

4. 페이지 교체(Page replacement)

빈페이지가 없을 때 기존의 페이지 중에서 하나를 뺏어오게 되는데 이를 페이지 교체라고 합니다.

이 때 어떤 frame을 빼앗을지 결정하게 되는데, 이것을 해주는 알고리즘을 replacement algorithm이라고 합니다.

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

replacement algorithm의 종류는 다음과 같습니다.

 

  1) Optimal Algorithm

     미래에 참조되는 알고리즘을 미리 다 알고 있다는 가정하에 운영하는 알고리즘입니다.

     가장 먼 미래에 참조되는 page를 교체하게 됩니다.

     Optimal Algorithm은 Belady's optimal algorithm, MIN, OPT 등으로 불립니다.

 

  2) FIFO(First In First Out) Algorithm

      미래를 모른다는 가정하에 운영하는 알고리즘입니다.

      이 메모리의 특이한 점은 메모리 page frame을 늘려준다면 성능이 더 좋아질 것으로 예측이 되지만

      사실 fage fault가 더 증가하게 되어 성능이 나빠지게 됩니다.

      그래서 이러한 기이한 현상을 그대로 명명하여 FIFO Anomaly 또는 Belady's Anomaly라고 불립니다.

 

  3) LRU(Least Recently Used) Algorithm

     미래를 모른다는 가정하에 운영하는 알고리즘입니다.

     가장 오래전에 사용된 page를 교체하는 알고리즘입니다.

     LRU는 구현할 때 링크드리스트 형태로 일렬로 page를 나열하게 됩니다.

     그래서 새로운 page는 맨 아래에 넣고, 교체할 page는 맨 위에서 가져오기 때문에 따로 탐색을 하지 않아도 됩니다. O(1)

 

  4) LFU(Least Frequently Used) Algorithm

     미래를 모른다는 가정하에 운영하는 알고리즘입니다.     

     참조 횟수가 제일 적은 page를 교체하는 알고리즘입니다.

     만약 참조 횟수가 제일 적은 page가 여러 개라면 그 중에서 가장 오래전에 사용된 page를 교체하게 됩니다.

     LFU는 구현할 때 heap을 사용합니다.

     맨 위는 참조횟수가 적은 page, 아래로 갈수록 참조횟수가 많아집니다. O(log n)

 

  5) LRU vs LFU

     만약 매우 빈번하게 사용되었던 page가 최근에 몇 번 사용되지 않아 LRU 알고리즘에 의해 교체가 되거나

     앞으로 빈번하게 사용될 page이지만 현재 한번 사용되어 LFU 알고리즘에 의해 교체가 된다면 매우 비효율적일 수 있습니다.

 

5. 캐슁 기법

한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 이후 요청시 캐쉬로부터 직접 서비스하는 방식입니다.

paging과 buffer 시스템 둘 다 접근이 빠른 공간은 물리메모리입니다.

다만 paging에서는 느린 공간이 swap 영역이고, buffer에서는 느린공간이 file system이라는 차이가 있습니다.

 

6 Clock Algorithm

사실 앞에서 언급한 교체 알고리즘 LRU, LFU는 실제로는 사용할 수 없는 알고리즘입니다.

page table에 page를 올리고, 물리메모리가 접근하는 page가 비어있는 page인지 확인하는 것은

하드웨어에서 담당하는 일이기 때문에 알고리즘을 수행할 수 없습니다.(!!!)

 

그래서 실제 paging system에서 사용할 수 있는 알고리즘으로 Clock Algorithm이 있습니다.

이는 page가 사용되었는지, 아닌지만 0과 1로 확인할 수 있도록 하여

0인 page를 최근에 사용되지 않은 page로 판단하고 교체하게 됩니다.

 

시계바늘이 돌듯이 page를 돌면서 1인 page를 만나면 0으로 바꾸고

0인 페이지를 만나면 교체하게 됩니다.

사용된 page라고 bit 0을 1로 바꾸는 것은 하드웨어에서 하고,

1을 0으로 바꾸는 것은 운영체제가 교체할 페이지를 찾으며 바꾸게 됩니다.

 

7. 프레임의 할당(Allocation of Frame)

각 프로세스마다 효율적으로 운영하는데 필요한 최소한의 page가 있기 때문에

이를 고려하여 프로세스에게 얼마만큼의 page frame을 할당 할 것인지에 대한 문제입니다.

할당 방법들로는 여러가지가 있는데, 다음과 같습니다.

 

  1) Equal allocation : 모든 프로세스에 똑같은 갯수를 할당합니다.

  2) Proportional allocation : 프로세스 크기에 비례하여 할당합니다.

  3) Priority allocation : 프로세스의 우선순위에 따라 다르게 할당합니다.

 

8. Replacement

교체 방법에 대한 문제도 다음처럼 나누어 볼 수 있습니다.

  1) Global replacement : Replace 시 다른 process에 할당된 frame과 교체할 수 있습니다.

    다만 하나의 프로세스가 모두 독점할 수 있다는 단점과 보다 효율적이라는 장점을 갖고 있습니다.

  2) Local replacement : 자신에게 할당된 frame 내에서만 교체할 수 있습니다.

 

9. Thrashing

멀티프로그램의 정도와 CPU 이용률의 상관관계에서

프로그램의 갯수가 늘어남에 따라 CPU 이용률 또한 늘어나다가

어느순간 이용률이 떨어지게 되는 상황을 Trashing이라고 합니다.

 

Thrashing이 일어나는 이유는 매우 조금씩 page를 가지고 있기 때문에 page default가

매우 빈번하게 일어남에 따라 CPU 이용률이 떨어지기 때문입니다.

 

 

Thrashing을 막기 위한 방법은 다음과 같습니다.

 

  1)Working-Set Model

    Working-Set Model은 각 프로세스가 필요로 하는 최소한의 프레임 수를 보장해줍니다.

 

    프로세스는 특정 시간 동안 일정 위치만을 집중적으로 참조하는데,

    이 참조되는 page들의 집합을 locality set이라고 합니다.

    이에 따라 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을

    Working Set이라고 합니다.

 

    그래서 이 모델에서는 프로세스의 Working Set 전체가 메모리에 올라와 있어야 수행되고,

    그렇지 않을 경우에는 모든 frame을 반납한 후 swap out 됩니다.

 

    Working-Set 알고리즘은 과거 사용된 page들의 일정범위를 그대로 메모리에 유지하는 것입니다.

    즉, 일정 시간동안 해당 page를 메모리에 유지한 후 시간이 지나면 버리게 됩니다.

 

  2) PFF(Page-Fault Frequency)

    page default를 보다 직접적으로 조절하는 방법입니다.

    page default가 너무 높으면 그 프로세스가 더 많은 프레임을 필요로 한다는 것이고,

    page default가 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다는 것입니다.

 

    따라서 page default의 상한과 하한을 정해 놓고,

    직접적으로 프레임 수를 줄이고 늘리면서 Thrashing을 방지하고 조절할 수 있습니다.