Virtual Memory: 가상 메모리 (1/2)

프로그램이 실행되기 위해 그 프로세스의 주소 공간 전체가 메모리에 올라와 있어야 하는 것은 아니다. 운영체제는 cpu에서 당장 수행해야 하는 부분만을 메모리에 올려두고 나머지는 디스크의 스왑 영역(swap area)에 올려둔다. 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이러한 공간을 가상 메모리(virtual memeory)라고 부른다. 가상 메모리는 모든 프로세스가 가지고 있으며 이들 공간 중 일부는 물리적 메모리에 올라가고 일부는 디스크의 스왑 영역에서 준비하고 있는다. 

프로세스 주소 공간을 메모리로 적재하는 단위에 따라 가상 메모리 기법은 요구 페이징(demand paging)과 요구 세그먼테이션(demand segmentation)으로 나뉜다. 대부분 요구 페이징 기법을 사용하며, 요구 세그먼테이션 기법을 사용할 때는 하나의 세그먼트를 여러 개의 페이지로 나누어 사용하는 페이지드 세그먼테이션 기법을 사용하는 경우이다. 

 

1. 요구 페이징 demand paging

요구 페이징이란 실제로 필요할 때 page를 메모리에 올리는 것을 말한다. 따라서 특정 페이지에 대해 cpu의 요청이 들어온 후에야 해당 페이지를 메모리에 올린다. 당장 실행에 필요한 페이지만 메모리에 적재시키므로 i/o 양이 감소하며, memory 사용량이 감소하고 응답시간이 빠르며 프로세스 전체를 메모리에 올리는데 소요되는 입출력 오버헤드도 줄어든다. 또한 물리적 메모리의 용량 제약을 벗어나 더 많은 사용자(프로세스)를 메모리에 올릴 수 있다는 장점이 있다.  

* valid / invalid bit의 사용

valid / invalid bit란 어떤 페이지가 메모리에 존재하고 어떤 페이지가 존재하지 않는지 구분하기 위한 방안이다. 이 비트는 각 프로세스를 구성하는 모든 페이지에 대해서 존재해야 하므로 페이지 테이블의 각 항목별로 저장된다. 

invalid의 의미

 - 사용되지 않는 주소 영역인 경우

 - 페이지가 물리적 메모리에 없는 경우

처음에는 모든 page entry가 invalid로 초기화되어 있다. 그러나 특정 페이지가 참조되어 메모리에 올라가게 되면 invalid에서 valid 값으로 비트의 값이 변화한다. 그리고 메모리에 올라가 있다가 swap area로 쫓겨나가는 경우 valid 값에서 invalid 값으로 변한다. cpu가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 valid-invalid bit가 invalid로 세팅되어 있는 경우를 page fault(페이지 부재)가 일어났다고 표현한다.

 

<page fault>

invalid page를 접근하면 MMU(Memory Management System: 논리적 주소->물리적 주소로 매핑해주는 주소

변환을 담당하는 하드웨어)가 trap(page fault trap)을 발생시킨다. 그러면 cpu의 제어권이 커널모드로 바뀌며 운영체제가 cpu 제어권을 잡고 페이지 부재 처리루틴page fault 이 호출되어 페이지 부재를 처리한다. 

다음과 같은 순서로 운영체제는 page fault를 처리하게 된다.

1. invalid reference? (eg. bad address, protection violation접근 권한 위반) => abort process 해당 프로세스 종료

2. get an empty page frame (없으면 뺏어온다 : replacement -> swap out)

3. 해당 페이지를 disk에서 메모리로 읽어온다. 

  3-1. disk i/o가 끝나기까지 이 프로세스는 cpu를 preempt 당함(block) -> cpu 레지스터 상태 및 프로그램 카운터 값을 pcb에 저장해둠

  3-2. disk read가 끝나면 page table entry를 기록, valid-invalid bit를 valid로 바꾼다.

  3-3. ready queue에 process insert -> dispatch later

 4. 이 프로세스가 다시 cpu를 잡고 running

 5. 아까 중단되었던 intsrtuction을 재개함

 

<performance of Demand paging>

요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다. 페이지 부재가 일어나면 요청된 페이지를 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생하기 때문이다. 요구페이징의 성능은 다음과 같이 요청한 페이지를 참조하는데 걸리는 유효 접근시간으로 측정한다. 

(1-p)는 메모리에 페이지가 올라와있는 경우이다. p는 페이지 부재가 일어나는 비율인데 페이지 부재가 일어나면 메모리에 올라와있는 페이지 하나를 스왑아웃 시키고 스왑 영역에서 페이지를 메모리로 읽어오고 인터럽트 걸어서 프로세스가 실행을 재개할 수 있는 상태로 바꾸어주고 자기 차례가 되면 문맥 교환을 하여 cpu를 재획득 하는등 아주 오래 걸리고 오버헤드가 큰 작업이 이루어진다. 

 

2. 페이지 교체 page replacement

<free frame이 없는 경우>

페이징 기법은 논리적 메모리를 페이지 단위로 나누고, 물리적 메모리를 논리적 메모리의 페이지와 같은 크기인 frame으로 나눈다. 그런데 페이지가 새로 올라와야 하는데 물리적 메모리의 frame이 가득 차 있을 경우 어떤 프레임에 올라와 있는 페이지를 쫓아내야 한다. 

어떤 frame을 빼앗아올지(그러니까 그 frame에 올라와있는 페이지를 내쫓을지)결정해야하며, 당연히 곧바로 사용되지 않을 page를 쫓아내는게 좋다. 동일한 페이지가 여러번 메모리에서 쫓겨났다가 다시 들어올 수 있다. 

이러한 page replacement algorithm은 다음과 같은 종류가 있다.

1) optimal algorithm

2) FIFO

3) LRU Algorithm

4) LFU Algorithm

5) clock Algorithm 

알고리즘의 평가는 당연히 주어진 페이지 참조열refernece string에 대해 page fault를 얼마나 내는지가 기준이며 page fault rate를 최소화 하는 것이 목표이다. 

<page replacement의 예시>

0. cpu가 프로세스에서 instruction에 필요한 페이지를 참조하는데 페이지 테이블에서 invalid 상태임을 확인한다. -> page fault 

1. 물리적 메모리에서 쫓아낼 page를 골라서 디스크로 swap out 시킴

2. 디스크로 swap out된 페이지의 valid-invalid bit을 invalid로 바꿈

3. 들어가고 싶어하는 page 넣어줌

4, valid invalid bit을 valid로 바꿔준다.  

 

<Optimal Algorithm: 최적 페이지 교체 알고리즘>

4 frame exmaple, 총 6번의 page fault 발생한다.

 

가장 먼 미래에 참조되는 page를 replace. 미래를 전부 알고 하는 것이라 실제 사용은 하지 않는다. 오프라인 알고리즘이라고 부르며 가장 적은 page fault rate를 보장하므로 다른 알고리즘의 성능에 대한 상한선(upper bound)를 제공한다.

 

<FIFO(First In First Out) Algorithm: 선입선출 알고리즘>

 물리적 메모리에 가장 먼저 들어온 것을 가장 먼저 내쫓는다. FIFO 알고리즘은 페이지 프레임이 늘어난 경우에 오히려 페이지 부재율이 증가하는 경우가 있을 수 있는데 이러한 상황을 FIFO Anomaly(Belady's Anomaly)라고 한다. 더 많은 프레임이 적은 페이지 부재로 이어지지 않는다는 말이다. 

 

<LRU(Least Recently Used) Algorithm> 

가장 오래 전에 참조된 것을 지운다. 메모리 페이지의 참조 성향 중 중요한 한가지 성질로 시간지역성(temporal locality)라는 것이 있다. 이 성질은 최근에 참조한 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 의미한다. LRU 알고리즘은 이와 같은 성질을 활용하여 페이지 교체 시 가장 오래 전에 참조가 이루어진 페이지를 쫓아낸다.

 

<LFU(Least Frequently Used) Algorithm>

LFU 알고리즘은 참조 쵯수가 가장 낮은 페이지를 교체하는 페이지로 결정한다. 물리적 메모리에 올라와 있는 페이지 중 참조 회수(reference count)가 가장 적은 페이지를 지우는 것이다. 그런데 만약 참조 회수가 최소인 페이지가 여럿 있다면 어떻게 될까? LFU 알고리즘 자체에서는 그냥 무작위로 아무 페이지나 쫓아내지만 성능 향상을 위해서는 그 중 가장 오래 전에 참조된 페이지를 쫓아내는 것이 좋을 것이다. 

 

<LFU 알고리즘의 종류> 

Incache LFU Algorithm 

페이지가 물리적 메모리에 올라온 후부터의 참조 회수를 카운트한다. swap out 됐다가 다시 swap in 된 경우 그 때부터 1로 다시 셈

Perfect LFU Algorithm

메모리에 올라와 있는지의 여부와 상관 없이 그 페이지의 과거 총 참조 회수를 카운트한다. swap out 됐다가 다시 swap in 해도 1부터 다시 시작하는게 아니라 그 전의 참조회수 + 1이 되는 것이다. 참조회수를 정확히 반영 가능하지만 예전 기록까지 전부 보관해야 하므로 오버헤드가 상대적으로 크다고 볼 수 있다.

 

<LRU와 LFU 알고리즘의 구현>

 

<다양한 캐슁 환경>

캐슁 기법이란?

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

 - paging 시스템 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용한다.

 

* 캐슁 운영의 시간 제약

 - 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용이 불가하다. 

 - buffer caching 이나 web caching인 경우 시간 복잡도가 O(1)에서 O(log n)까지 허용된다.

 

* Paging System인 경우

 - page fault인 경우에만 os가 관여한다.

 - 페이지가 이미 메모리에 존재하는 경우 참조 시각 등의 정보를 os가 알 수 없다. (@@ 참고)

 - O(1)인 LRU의 list 조작조차 불가능하다.

 

@@ 주소 변환 했는데 페이지 테이블에 invalid라면 물리적 메모리에 없고 backing store에 있다. -> page fault

page fault가 발생하면 disk 접근 필요하다 -> i/o 필요하다 -> process A가 디스크에서 직접 읽어오는 작업을 할 수 없음(특권 명령) -> page fault trap -> CPU 제어권이 process A에서 운영체제로 넘어감 -> 운영체제가 disk에서 물리적 메모리로 올림 이 과정에서 남는 frame이 없다면 replace 과정이 일어날 수도 있다. LRU, LFU를 쓴다면 운영체제가 가장 접근 시간이 낮거나 가장 오래 전에 참조된 페이지를 알 수 있나? 알수 없다. 프로세스가 요청한 페이지가 이미 page table에 올라와 있는 경우 운영체제에게 cpu가 넘어가지 않음 하드웨어 적으로 주소 변환해서 cpu로 읽어들인다. 따라서 운영체제는 알수 없다. 따라서 Paging System에서 LRU, LFU는 사용이 불가하다. page fault 발생시(CPU 제어권이 운영체제로 넘어오면)에만 디스크에서 메모리에 올라온 시간을 알 수 있으며 이미 메모리에 페이지가 있으면 알 수 없음

 

<CLOCK Algorithm>

LRU와 LFU는 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교해야 하므로 알고리즘의 운영에 시간적인 오버헤드가 발생한다. clock 알고리즘은 하드웨어적인 지원을 통해 이와 같은 알고리즘의 오버헤드를 줄인 방식이다. 클럭 알고리즘은 LRU를 근사(approxination)시킨 알고리즘으로 여러 명칭으로 불린다. second chance algorithm, NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘이라는 명칭으로도 불린다.

클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. 최근에 참조되지 않은 페이지를 교체하는건 LRU와 비슷하지만 교체하는 페이지가 가장 오래 되지는 않았다는 점에서 LRU와 다르기 때문에 LRU 근사 알고리즘이라고 불리는 것이다. clock 알고리즘은 하드웨어적인 지원이 필요한데, 하드웨어는 reference bit(참조 비트)을 만들고(세팅하고) 운영체제는 reference bit이 0인거를 내쫓는다. reference bit이 1인거는 시계바늘이 한바퀴 돌 때 한번은 참조되었다는 말이고, 0이면 한번도 참조되지 않았다는 말이다. 참조비트는 각 프레임마다 하나씩 존재한다. 어쨋든 clock 알고리즘은 한 바퀴 돌면서 참조 비트가 1이면 0으로 바꾸며 0 인 페이지는 교체한다. 모든 페이지 프레임을 다 조사한 경우 첫 번쨰 페이지 프레임부터 조사 작업을 반복한다. 1인 페이지를 0으로 교체해도 페이지가 참조되면 다시 1로 바뀌기 마련인데, 한바퀴 돌고 와서도 0이라면 참조되지 않았다는 뜻이므로 교체 대상이 되는 것이다. 적어도 시곗바늘(포인터)이 한 바퀴를 도는데 소요되는 시간만큼 페이지를 메모리에 유지시켜둠으로써 페이지 부재율을 줄이도록 설계되었기 때문에 이 알고리즘을 second chance algorithm이라고 하는 것이다. 

 

<clock algorithm의 개선>

reference bit과 modified bit(dirty bit)을 함꼐 사용한다. 

reference bit = 1  => 최근에 참조된 페이지

modified bit(dirty bit) = 1  => 최근에 변경된 페이지 (i/o를 동반하는 page)