[OS] 가상 메모리

가상 메모리

• 운영체제는 프로그램이 물러적 메모리를 고려할 필요 없이 자기 자신만이 메모리를 사용하는 것처럼 가정해 피로그램하는 것을 지원한다. 이렇게 되면 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이러한 메모리 공간을 가상 메모리(virtual memory)라고 한다.

• 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 존재하게 된다.

• 프로세스의 주소 공간을 메모리에 적재하는 단위에 따라 가상메모리 기법은 요구 페이징(demand paging) 방식과 요구 세그먼테이션(demand segmentation) 방식으로 구현될 수 있다.

1.요구 페이징

• 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식이다.

• 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다.

• 당장 실행에 필요한 페이지만을 메모리에 적재하기 때문에 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 줄어든다.

• 기존 방식에 비해 응답시간을 단축시킬 수 있으며, 시스템이 더 많은 프로세스를 수용할 수 있게 해준다.

• 프로그램을 구성하는 페이지 중 일부만을 메모리에 적제하게 되므로 물리적 메모리의 용량보다 큰 프로그램도 실행할 수 있다.

• 유효-무효 비트(valid-invalid bit)를 두어 각 페이지가 메모리에 존재하는지 표시하게 된다. 모든 페이지에 대해 존재해야 하므로 페이지 테이블의 항목별로 저장된다.

  • 프로세스가 실행되기 전에는 모든 페이지의 유효-무효 비트가 무효값으로 초기화 되어있지만 특정 페이지가 참조되어 메모리에 적재되는 경우 유효값으로 바뀐다.
  • 메모리에 적재되어 있던 페이지가 디스크의 스왑 영역으로 쫒겨날 때에는 다시 무효값을 가진다.
  • 페이지 부재(page fault) : CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 말한다.

1) 요구 페이징의 페이지 부재 처리

• CPU가 무효 페이지에 접근하면 MMU가 페이지 부재 트랩(page fault trap)을 발생시키게 된다. 그러면 CPU의 제어권이 커널모드로 전환되고, 운영체제의 페이지 부재 처리루틴(page fault handler) 이 호출되어 다음과 같은 순서로 페이지 부재를 처리한다.

  (1) CPU가 페이지 N을 참조한다. (2) 페이지 테이블에서 페이지 N이 무효 상태임을 확인한다. (3) 페이지 부재 트랩이 발생한다. (4) 디스크에서 부재 페이지를 빈 프레임에 적재하고 페이지 테이블을 업데이트한다.

• 사용되지 않는 주소 영역에 속한 페이지에 접근하려 했거나 해당 페이지에 대한 접근 위반(protection violoation)을 했을 경우에는 해당 프로세스를 종료시킨다.

• 접근 위반의 예를 들면 읽기전용인 페이지에 대해 쓰기 접근 시도를 하는 것을 들 수 있다.

• 페이지에 대한 접근이 적법할 경우 물리적 메모리에서 비어 있는 프레임(free frame)을 할당받아 그 공간에 해당 페이지를 읽어온다.
• 그러나 메모리에 비어 있는 프레임이 없다면 기존에 올라와 있는 페이지 하나를 디스크로 보낸다(스왑 아웃).
• 페이지를 디스크->메모리로 적제하기에 오랜 시간이 소요되므로 해당 페이지의 프로세스는 봉쇄상태가 된다. 이때 CPU 레지스터 상태 및 프로그램 카운터 값을 프로세스의 PCB에 저장해서 나중에 CPU를 다시 할당받았을 때 정확히 같은 상태에서 다음 명령을 수행할 수 있도록 한다.
• 디스크 입출력이 완료되어 디스크에서 페이지를 메모리의 프레임에 적재를 하면 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정하고, 봉쇄되었던 프로세스를 준비 큐로 이동시킨다.
• 이 프로세스가 다시 CPU를 할당 받으면 이전에 PCB에 저장되었던 정보를 바탕으로 명령을 수행한다.

2) 요구 페이지의 성능

• 요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다.
• 페이지 부재로 인해 요청된 페이지를 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생하게 된다.

• 때문에 페이지 부재가 적게 발생할수록 페이지 성능이 향상될 수 있다.

• 요구 페이징이 성능은 다음과 같이 요청한 페이지를 참조하는 데 걸리는 유효 접근시간으로 측정한다.
  • 유효 접근시간(effective access time)
    = (1 - P) X 메모리 접근시간
    + P X (페이지 부재 발생 처리 오버헤드
    + 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드
    + 요청된 페이지의 스왑 인 오버헤드
    + 프로세스의 재시작 오버헤드)
    

2. 페이지 교체

• 물리적 메모리에 빈 프레임이 없을 경우 메모리에 올라와 있는 페이지 중 하나를 디스크로 스왑 아웃 시켜 메모리에 빈 공간을 확보하는 작업이 필요하다.

• 페이지 교체를 할 때에 어떤한 프레임에 있는 페이지를 쫒아낼 것인지 결정하는 것을 교체 알고리즘(replacement algorihtm)이라고 한다. 목표는 페이지 부재율을 최소화 하는 것이며 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 스왑 아웃시키는 것이 성능을 향상시킬 수 있는 방안이다.

• 페이지 참조열(page reference string)에 대해 페이지 부재율을 계산함으로써 평가할 수 있다.
• 페이지 참조열은 참조되는 페이지들의 번호를 시간 순서에 따라 나열한 것이다.
  예) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 해당 페이지가 메모리에 이미 올라와 있으면 “메모리에서 적중(hit)되었다.” 고 한다.

1) 최적 페이지 교체(Belady’s optimal algorithm)

• 페이지 부재율을 최소화하기 위해서는 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫒아내면 된다.
• 이 알고리즘은 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 이루어진다.
• 어떠한 알고리즘을 사용하는 경우보다도 가장 적은 페이지 부재율을 보장한다.

2) 선입 선출 알고리즘(First In First Out: FIFO)

• 페이지 교체시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 스왑 아웃시킨다.
• 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 스왑 아웃시키기 때문에 비효율 적인 상황이 발생할 수 있다.
  • 예) 가장 먼저 물리적 메모리에 들어온 페이지가 계속해서 많은 참조가 이루어진다 해도 이 페이지를 스왑 아웃시킨다.
• FIFO 이상 현상(FIFO anomaly) : 물리적 메모리의 공간이 늘어났음에도 FIFO 알고리즘에서 페이지 부재가 오히려 늘어나는 상황이다.

3) LRU(Least Recenlty Used) 알고리즘

• 페이지 교체시 가장 오래전에 참조가 이루어진 페이지를 스왑 아웃시킨다. 즉 마지막 참조 시점이 가장 오래된 페이지를 교체한다. 단, 직전에 참조된 시점만을 반영한다.
• 참고로 페이지가 이미 메모리에 올라와 와서 적중된 것도 페이지의 참조가 이루어진 것이다.
• 참조 횟수가 가장 많은 페이지라도 가장 마지막에 참조된 페이지라면 교체를 해버린다는 단점이 있다.

4) LFU(Least Frequently Used) 알고리즘

• 페이지의 참조 횟수로 교체시킬 페이지를 결정한다. 즉 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수(reference count)가 가장 적었던 페이지를 쫒아내고 그 자리에 새로 참조될 페이지를 적재한다.
• 최저 참조 횟수를 가진 페이지가 여러 개 존재하는 경우 상대적으로 더 오래전에 참조된 페이지를 쫒아내도록 구현하는 것이 효율적이다.

• 참조 횟수를 통해 장기적인 시간 규모에서의 참조 성향을 고려한다.

• 페이지의 참조 횟수를 계산하는 방식에 따라 Incache-LFU와 perfect-LFU 가 있다.
  • Incache-LFU : 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트 하는 방식이다. 페이지가 메모리에서 스왑 아웃되었다가 다시 스왑 인 된 경우 참조 횟수는 1 부터 새로 시작된다.
  • Perfect-LFU : Incache-LFU와는 다르게 그 페이지의 과거 총 참조 횟수를 카운트한다. 즉 스왑 아웃되었다가 다시 스왑 인 되어도 참조 횟수는 누적된다. 페이지의 참조횟수를 정확히 반영하는 장점이 있지만 메모리로 쫒겨난 페이지의 참조 기록까지 모두 보관하고 있어야 하므로 그 오버헤드가 상대적으로 더 크다.
• 장점 : LRU 알고리즘보다 오랜 시간 동안 참조 기록을 반영할 수 있다.
• 단점 : 시간에 따른 페이지 참조의 변화를 반영하지 못하고, LRU보다 구현이 복잡하다. 즉, 가장 참조 횟수가 적은 페이지이지만 가장 최근에 참조되어 앞으로도 참조가 자주 될 가능성이 있는 페이지를 내쫒을 수도 있다.

5) 클럭(clock) 알고리즘

• 하드웨어적인 지원을 통해 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지해야하는 알고리즘의 운영 오버헤드를 줄인 방식이다.
• 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. 즉, LRU와 비슷하지만, 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 못하므로 LRU를 근사시킨 알고리즘이다.

• 하드웨어적인 지원으로 동작하기 때문에 LRU에 비해 페이지의 관리가 훨씬 빠르고 효율적으로 이루어진다. 대부분의 시스템에서 사용된다.

• 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트(reference bit)를 순차적으로 조사한다.
• 참조 비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 ‘자동 세팅’된다.
• 클럭 알고리즘은 프레임들을 돌면서 참조 비트가 1인 페이지는 0으로, 0인 페이지는 교체된다. 이렇게 시계바늘처럼 계속 프레임들을 돌면서 반복한다.
• 자주 사용되는 페이지라면 시곗바늘이 한 바퀴 동는 동안 참조비트가 1로 세팅되어 교체되지 않는다.
• 최근에 참조가 일어나지 않은 페이지를 교체하는 알고리즘이라 할수 있다.
• 적어도 시곘바늘이 한바퀴를 도는 데 소요되는 시간만큼 페이지를 메모리에 유지시켜둠으로써 페이지 부재율을 줄이도록 설계되었기 때문에 2차 기회 알고리즘(seocond chance algorithm)이라고도 부른다.

3. 페이지 프레임의 할당

• 프로세스 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지를 결정해야 한다.
• 기본적인 할당 알고리즘(allocation algorithm)은 세가지로 나누어 볼수 있다.
  • 균등할당(equal allocation) : 모든 프로세스에게 페이지 프레임을 균등하게 할당한다.
  • 비례할당(proportional allocation) : 프로세스의 크기에 비례해 페이지 프레임을 할당한다. 프로세스의 크기가 모두 균일하지 않다는 점에 착안한 방식이다.
  • 우선순위 할당(priority allocation) : 프로세스 중 당장 CPU에서 실행될 프로세스에게 더 많은 페이지 프레임을 할당한다.
• 현재 수행중인 프로세스의 수가 지나치게 많을 경우 프로세스당 할당되는 메모리 양이 과도하게 적어질수 있다.
• 프로세스를 정상적으로 수행하기 위해서는 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에게 할당해야한다.
• 반복문을 구성하는 페이지의 수보다 적은 양의 프레임을 할당하면 매 반복(iteration)마다 적어도 한 번 이상의 페이지 부재가 발생해 시스템 성능이 현저히 떨어진다.
• 프로세스에게 최소한으로 필요한 메모리의 양은 시간에 따라 다를 수 있다.
• 경우에 따라서는 일부 프로세스에게 메모리를 할당하지 않는 방식으로 나머지 프로세스들에게 최소한의 메모리 요구량을 충족시킨다.

4. 전역교체와 지역교체

• 교체할 페이지를 선정할 때, 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 전역교체(global replacement)와 지역교체(local replacement)로 구분할 수 있다.
  • 전역 교체
    • 메모리상의 모든 페이지 프레임이 교체 대상이 될 수 있는 방법이다. 즉, 그 페이지가 어떤 프로세스에 속한 것인지는 고려하지 않는다.
    • 프로세스마다 메모리를 할당하는 것이 아니라 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변한다.
    • 페이지 교체 시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있는 방식이다.
  • 지역 교체
    • 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법이다.
    • 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 한다.
    • 교체할 페이지도 그 프로세스에게 할당된 프레임 내에서 선정하게 된다.

5. 스레싱(thrashing)

• 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율(page fault rate)이 크게 상승해 CPU 이용률(CPU utilization)이 급히 떨어질 수 있다. 이와 같은 현상을 스레싱라고 한다.

• 운영체제는 CPU의 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적기 때문이라고 판단한다. 따라서 메모리에 올라가는 프로세스의 수를 늘리게 된다.
• 메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도(Multi-Programming Degree : MPD)라고 한다.

• 즉, CPU 이용률이 낮을 경우 운영체제는 MPD를 높이게 된다. 그런데 MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소하게 된다. 그렇게 되면 각 프로세스는 최소한의 페이지 프레임도 할당받지 못하는 상태가 되어 페이지 부재가 빈번하게 발생하게 된다.

• 따라서 스레싱이 발생하지 않도록 하면서 CPU 이용률을 최대한 높일 수 있도록 MPD를 조절하는 것이 중요하다.

1) 워킹셋 알고리즘

• 프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다. 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합(locality set) 이라고 한다.
• 워킹셋 알고리즘은 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이다.
• 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 워킹셋(working set)이라고 한다.
• 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다.
• 그렇지 않을 경우 프로세스에게 할당된 페이지 프레임들을 모두 반납하고 프로세스의 주소공간 전체를 디스크로 전부 스왑 아웃된다.
• 한꺼번에 메모리에 올라가야 할 페이지들의 집합을 결정하기 위해 워킹셋 윈도우(working-set window)를 사용한다.
  • 윈도우 크기 △와 시각 Ti 일 경우, [ Ti - △, Ti ] 사이에 참조된 서로 다른 페이지들의 집합인 워킹셋 WS(Ti)로 정의한다.
  • Ti시점에 워킹셋에 포함된 페이지들은 메모리에 유지되고 그렇지 않은 페이지들은 메모리에서 쫒겨난다.

• 워킹셋 알고리즘은 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임 수보다 클 경우 일부 프로세스를 스왑 아웃시켜서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는는 것을 보장한다. 이는 MPD를 줄이는 효과를 발생시킨다.

• 프로세스들의 워킹셋을 모두 할당한 후에도 프레임이 남을 경우, 스왑 아웃되었던 프로세스를 다시 메모리에 올려서 워킹셋을 할당함으로써 MPD를 증가시킨다.
• 윈도우 △의 크기가 너무 작으면 지역성 집합이 커져서 이를 모두 수용하지 못할수가 있다.
• 반면 윈도우 △의 크기가 너무 크면 지역성 집합이 작아서 여러 규모의 지역성 집합을 수용할 수 있지만 MPD가 감소해 CPU이용률이 낮아질 우려가 있다.
• 워킹셋 알고리즘에서 시스템의 성능을 향상시키기 위해서는 프로세스들의 지역성 집합을 효과적으로 탐지할 수 있는 윈도우 크기 △를 결정하는 것이 중요하다.
• 워킹셋 알고리즘은 워킹셋이 많은 페이지들로 구성되어 메모리를 많이 필요로 할때에는 많이 할당한다.
• 반대로 워킹셋이 적은 페이지들로 구성되어 메모리를 적게 필요로 할때에는 적게 할당한다. 즉 동적인 프레임 할당 기능까지 수행한다.

2) 페이지 부재 빈도 알고리즘

• 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.

• 페이지 부재율이 시스템에서 미리 정해놓은 상한값(upper bound)을 넘게 되면 이 프로세스에 할당된 프레임의 수고 부족하다고 판단하여 프레임을 추가로 할당한다.
• 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑아웃시켜 메모리에 올라가 있는 프로세스의 수를 조절한다.
• 프로세스의 페이지 부재율이 하한값(lower bound)이하로 떨어지면 필요이상으로 많은 프레임이 할당된 것으로 판단해 할당된 프레임의 수를 줄인다.
• 이렇게 메모리에 존재하는 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남아 있는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높이고 CPU 이용률을 높여 스레싱을 방지한다.