********************************
##이 글은 제가 공부하고 있는 책을 요약해놓은 것이므로 본문 내용만 봐선 이해가 어려울 수 있습니다.
목차
1. 요구 페이징
2. 페이지 교체
3. 페이지 프레임의 할당
4. 전역교체와 지역교체
5. 스레싱
********************************
메모리의 연장 공간으로 디스크의 스왑 영역이 사용될 수 있기 때문에 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 생각할 필요가 없어진다. 나아가 운영체제는 프로그램이 물리적 메모리를 고려할 필요 없이 자기 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원. 이렇게 되면 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이 메모리 공간을 가상 메모리(virtual memory)라고 부른다.
프로세스 주소 공간을 메모리로 적재하는 단위에 따라 가상메모리 기법은 2가지가 존재. 요구 페이징(demand paging) 방식과 요구 세그먼테이션(demand segmentation) 방식으로 구현될 수 있다. 대부분의 경우 요구 페이지 방식을 사용하며, 요구 세그먼테이션 방식은 페이지드 세그먼테이션 기법을 사용하는 경우에 쓰인다.
1. 요구 페이징
요구 페이징은 프로세스를 구성하는 페이지를 모두 메모리에 올리지 않고 당장 사용될 페이지만을 올리는 방식. 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재. 필요한 부분만 적재하여 쓰기 때문에 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 줄어든다. 이는 시스템이 더 많은 프로세스를 수용할 수 있게 해줌. 물리적 메모리의 용량보다 더 큰 프로그램도 실행이 가능해짐. 나머지는 디스크의 스왑 영역에 존재함. 이러한 시스템에서 어떤 페이지가 메모리에 존재하지 않는지 구별하기 위해 유효-무효 비트(valid-invalid bit)를 둔다. 이 비트는 각 프로세스를 구성하는 모든 페이지에 대해 존재해야 하므로 페이지 테이블의 각 항목별로 저장됨. 프로세스 실행 전엔 모든 페이지의 유효-무효 비트가 무효값으로 초기화되어 있지만, 특정 페이지가 참조되어 메모리에 적재되는 경우 유효값으로 바뀌게 됨. 적재되있던 페이지가 디스크의 스왑 영역에 쫓겨날 때는 다시 무효값을 가지게 됨. 유효-무효 비트값이 무효인 경우에는 페이지가 현재 메모리에 없는 경우일 수도 있지만, 그 페이지가 속한 주소 영역을 프로세스가 사용하지 않는 경우도 있다. CPU가 참조하려는 페이지가 현재 메모리에 올라와있지 않아 유효-무효가 비트가 무효값을 가지는 경우를 페이지 부재(page fault)가 일어났다고 말한다.
1) 요구 페이징의 페이지 부재 처리
CPU가 무효 페이지에 접근하면 주소변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩(page fault trap)을 발생시킴. 그러면 CPU 제어권이 커널모드로 전환되고, 운영체제의 페이지 부재 처리루틴이 호출되어 페이지 부재를 처리한다. 가장 먼저 해당 페이지 접근이 적법인지 체크한다. 사용되지 않는 주소 영역에 속한 페이지에 접근하거나 해당 페이지에 대한 접근 권한 위반(protection violation)을 했을 경우에는 해당 프로세스를 종료시킨다. 접근 권한 위반의 예로는 읽기 전용 페이지에 대해 쓰기 접근 시도를 하는 경우이다. 이후 물리적 메모리에서 비어있는 프레임을 할당받아 그 곳에 해당 페이지를 읽어온다. 비어 있는 프레임이 없다면 기존 페이지 중 하나를 디스크로 스왑 아웃한다. 한편 요청된 페이지를 디스크로부터 메모리로 적재하기까지 오랜 시간이 소요됨. 따라서 페이지 부재를 발생시킨 프로세스는 CPU를 빼앗기고 봉쇄 상태가 된다. 이때 CPU 레지스터 상태 및 프로그램 카운터값을 PCB에 저장해둠으로써 나중에 프로세스가 다시 CPU를 할당받을 경우에 같은 상태에서 명령을 수행할 수 있게 한다. 디스크 입출력이 완료되어 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정하고 봉쇄되었던 프로세스를 준비큐로 이동시킨다. 그러다 다시 CPU를 할당받으면 PCB에 있던 값을 복원시켜 중단되었던 명령부터 실행한다.
2) 요구 페이징의 성능
요구 페이징 기법의 성능에 가장 큰 영향을 주는 요소는 페이지 부재의 발생 빈도이다. 페이지 부재가 일어나면 요청된 페이지를 메모리로 읽어오는 막대한 오버헤드가 발생하기 때문. 요구 페이징 성능은 요청한 페이지를 참조하는 데 걸리는 유효 접근시간으로 측정한다. 유효 접근시간= (1-P)*메모리 접근시간 + P*(페이지 부재 발생처리 오버헤드 + 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드 + 요청된 페이지의 스왑 인 오버헤드 + 프로세스의 재시작 오버헤드). 이때 P는 0~1값을 가지며 페이지 부재 발생 비율이다. 스왑 영역에서 요청된 페이지를 메모리로 다 읽어왔으면 인터럽트를 통해 프로세스가 실행을 재개할 수 있는 상태로 바꾸어주고 자신의 차례가 되면 문맥교환을 통해 다시 CPU를 얻게 됨.
2. 페이지 교체
요청된 페이지를 디스크에서 메모리로 읽어올때 물리적 메모리에 빈 프레임이 없을 경우 메모리의 페이지 중 하나를 디스크로 쫓아내는 작업이 필요한데 이를 페이지 교체(page replacement)라고 한다. 어느 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 교체 알고리즘이라고 하는데 이 알고리즘의 목표는 페이지 부재율을 최소화하는 것이다. 알고리즘의 성능은 주어진 페이지 참조열(page reference string)에 대해 페이지 부재율을 계산함으로써 평가할 수 있음. 페이지 참조열은 참조되는 페이지들의 번호를 시간순으로 나열한 것.
1) 최적 페이지 교체
빌레디의 최적 알고리즘(Belady's optimal algorithm): 페이지 부재율을 최소화하기 위해 페이지 교체시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 것. 이 알고리즘은 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전제하에 사용하므로 실제 시스템에서 온라인으로 사용할 수 있는 알고리즘은 아니다. 따라서 이러한 알고리즘을 오프라인 알고리즘이라 부름. 빌레디의 오프라인 최적 알고리즘은 어떠한 알고리즘을 사용할 때보다도 가장 적은 페이지 부재율을 보장하므로 다른 알고리즘 성능에 대한 상한선(upper bound)를 제공한다.
2) 선입선출 알고리즘(first in, first out. FIFO)
페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다. 페이지의 향후 참조 가능성을 고려하지 않기때문에 비효율적인 상황이 발생할 수 있다. 그림을 참고하면 페이지 프레임이 3개인 경우 9번의 페이지 부재가 발생했으나 페이지 프레임이 4개인 경우 오히려 페이지 부재가 10개로 증가했다. FIFO 알고리즘에서 메모리를 증가시켰음에도 페이지 부재가 오히려 늘어난 상황을 FIFO의 이상 현상(FIFO anomaly)라고 부른다. 뒤의 LRU에선 이런 현상이 발생하지 않음.
3) LRU 알고리즘
메모리 페이지의 참조 성향 중 중요한 성질로 시간지역성(temporal locality)라는 것이 있다. 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 말함. LRU(Least Recently Used) 알고리즘은 이 같은 성질을 활용해서 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 쫓아냄. 즉 마지막 참조 시점이 가장 오래된 페이지를 교체.
4) LFU 알고리즘
LFU(least frequently used) 알고리즘은 페이지의 참조 횟수로 교체시킬 페이지를 결정. 물리적 메모리 내의 페이지 중 가장 참조 횟수가 적었던 페이지를 쫓아냄. 여러개인 경우 임의로 하나를 선정. LFU 알고리즘은 참조 횟수를 계산하는 방식에 따라 두가지로 나뉨. Incache-LFU는 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트. 페이지가 메모리에서 쫓겨났다가 돌아온 경우 다시 1부터 시작. Perfect-LFU는 메모리에 올라와있는지 여부에 상관없이 모든 참조 횟수를 카운트. Perfect-LFU는 페이지의 참조 횟수를 정확히 반영할 수 있다는 장점이 있지만, 메모리에서 쫓겨난 페이지의 참조기록까지 모두 갖고 있어야 해서 오버헤드가 큼.
LFU는 LRU보다 오랜시간 동안의 참조기록을 반영할 수있다는 장점이 있음. 하지만 LFU는 시간에 따른 페이지 참조의 변화를 반영하지 못하고 LRU보다 복잡하다는 장점이 있음.
5) 클럭 알고리즘
LRU와 LFU는 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교해야 해서 시간적 오버헤드가 발생. 클럭 알고리즘(clock algorithm)은 하드웨어적인 지원을 통해 이와 같은 알고리즘의 운영 오버헤드를 줄인 방식. LRU를 근사시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘으로도 불림. 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체. 즉 최근에 참조되지 않은 페이지를 교체 대상으로 선정하는 측면에서 LRU와 유사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다는 점에서 LRU를 근사시킨 알고리즘으로 볼 수 있다. 하지만 이 알고리즘은 하드웨어적인 지원으로 동작하기 때문에 페이지 관리가 훨씬 빠르고 효율적. 클럭 알고리즘은 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트를 순차적으로 조사. 참조비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 참조될때 하드웨어에 의해 1로 자동 세팅됨. 여기서 클럭 알고리즘은 참조비트가 1인 페이지는 0으로 바꾼 후 그냥 지나가고 참조비트가 0인 페이지는 교체한다. 모든 페이지 프레임을 다 조사한 경우 첫번째 프레임부터 다시 조사. 간단히 말해 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체하는 것이다. 자주 사용되는 페이지라면 시곗바늘이 한바퀴 도는 동안 참조비트가 1로 세팅되어 교체되지 않으므로 이 알고리즘은 최근에 참조가 일어나지 않은 페이지를 교체하는 알고리즘이라 할 수 있다.
3. 페이지 프레임의 할당
프로세스 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지 결정해야 함. 기본적인 할당 알고리즘은 세 가지로 나누어볼 수 있다.
균등할당(equal allocation) 방식: 모든 프로세스에게 페이지 프레임을 균일하게 할당
비례할당(proportional allocation) 방식: 프로세스 크기가 다르다는 점에 착안. 크기에 비례하여 페이지 프레임 할당.
우선순위 할당(priority allocation) 방식: 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당. 프로세스 중 당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분하여 전자에 더 많은 페이지 프레임을 할당.
할당 알고리즘만으로는 프로세스의 페이지 참조 특성을 반영하지 못할 우려가 있음. 수행 중인 프로세스의 수가 지나치게 많을 경우 프로세스당 할당되는 메모리 양이 과도하게 적어질 수 있기 때문. CPU에서 명령을 실행할 땐 프로세스의 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하기 때문에 여러 페이지를 동시에 참조하게 된다. 따라서 프로세스의 정상 수행을 위해서 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야 함. 또한 반복문을 수행 중인 프로세스의 경우 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려 놓는 것이 유리. 반복문을 구성하는 페이지 수보다 적은 양의 프레임을 할당한다면 매 반복마다 적어도 한 번 이상의 페이지 부재가 발생하기 때문.
4. 전역교체와 지역교체
교체할 페이지를 선정할 때, 교체 대상이 도리 프레임의 범위를 정하는 방법 2가지가 있다.
전역교체 방법(global replacement)는 모든 페이지 프레임이 교체 대상이 되는 것. 지역교체 방법(local replacement)는 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정. 지역교체 방법은 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 하지만 전역교체 방법은 프로세스마다 메모리를 할당하는 것이 아니라 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법.
LRU 알고리즘으로 전역교체를 한다면 물리적 메모리에 올라와 있는 페이지 중 가장 오래전에 참조된 페이지를 교체함. 이때 그 페이지가 어떤 프로세스인지 고려하지 않음. 즉 페이지 교체 시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있는 방식. 이는 프로세스별 프레임 할당량을 조절하는 또 다른 방법이 될 수 있음.
LRU, LFU, 클럭 등의 알고리즘을 물리적 메모리 내에 존재하는 전체 페이지 프레임들을 대상으로 적용하는 경우가 전역교체 방법이 됨. 반면 LRU, LFU 등의 알고리즘을 프로세스별로 독자적으로 운영할 때에는 지역교체 방법이 됨.
5. 스레싱
프로세스가 원활히 수행되기 위해선 일정 수준 이상의 페이지 프레임을 할당받아야 함. 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어질 수 있기 때문. 이와 같은 현상을 스레싱(thrashing)이라함.
<스레싱이 발생하는 시나리오>
운영체제는 CPU의 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적기 때문이라 판단. 준비 큐에 프로세스가 하나라도 있다면 CPU는 그걸 실행하므로 쉬지 않고 일하게 됨. 그러나 CPU 이용률이 낮다는 건 준비 큐가 비는 경우가 발생한다는 뜻. 이는 메모리에 올라와있는 프로세스 수가 너무 적어 이들 모두 I/O작업을 함으로써 준비 큐가 비는 경우가 발생했다는 뜻. 따라서 CPU 이용률이 낮으면 운영체제는 메모리에 올라가는 프로세스 수를 늘리게 됨. 메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도(Multi-programming Degree, MPD)라고 부름. 요약하자면 CPU 이용률이 낮을 경우 운영체제는 MPD를 높이게 됨. 근데 MPD가 과도하게 높아지면 각 프로세스에 할당되는 메모리양이 지나치게 감소. 그들의 원활한 수행이 방해됨. 최소한의 페이지 프레임도 할당받지 못하는 상태가 되어 페이지 부재가 빈번히 발생. 페이지 부재가 발생하면 디스크 I/O 작업을 수반하므로 문맥교환을 통해 다른 프로세스에게 CPU가 이양됨. 이때 다른 프로세스 역시 할당받은 메모리 양이 지나치게 적으면 페이지 부재가 발생. 그럼 또 다른 프로세스에게 CPU가 할당됨. 결국 준비 큐에 있는 모든 프로세스에게 CPU가 한차례씩 할당되었는데도 모든 프로세스가 페이지 부재를 발생시켜 시스템은 페이지 부재를 처리하느라 분주해지고 그에 따라 CPU 이용률을 급격히 떨어지게 됨. 이 상황에서 운영체제는 메모리에 올라와있는 프로세스 수가 적다고 판단하고 MPD를 높이기 위해 또 다른 프로세스를 메모리에 추가. 이로 인해 프로세스당 할당된 프레임 수가 더 적어져 페이지 부재는 더 빈번히 발생. 이 경우 프로세스들은 서로의 페이지를 교체하며 스왑 인과 스왑 아웃을 지속적으로 발생시키고 CPU는 대부분의 시간에 일을 하지 않게 된다. 이를 스레싱이라고 부른다. MPD와 CPU 이용률의 상관관계를 살펴보면 어느 정도까진 비례하다 한계치를 넘어서면 CPU이용률이 급격히 떨어지게 됨.
따라서 스레싱의 발생을 막으면서 CPU 이용률을 최대한 높일 수 있도록 MPD를 조절하는 것이 중요. 이러한 방법에는 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 존재.
1. 워킹셋 알고리즘(working-set algorithm)
프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있는데 이때 참조되는 페이지들의 집합을 지역성 집합(locality set)이라고 한다. 워킹셋 알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관련 알고리즘을 뜻함. 워킹셋 알고리즘에서는 프로세스가 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어햐 하는 페이지들의 집합을 워킹셋이라 정의하고, 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있을 경우에만 그 프로세스에게 메모리를 할당. 그렇지 않을 경우에는 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃시킴. 이같은 방법으로 MPD를 조절하고 스레싱을 방지함. 한꺼번에 올라가야 할 페이지들의 집합을 결정하기 위해 워킹셋 알고리즘은 워킹셋 윈도우(working-set window)를 사용. 윈도우 크기가 d인 경우, 워킹셋 알고리즘은 시각 t(i)에서의 워킹셋 WS(ti)을 시간 간격 [t(i)-d, t(i)]사이에 참조된 서로 다른 페이지들의 집합으로 정의. t(i)시점에 워킹셋에 포함된 페이지들은 메모리에 유지되고 그렇지 않은 페이지들은 메모리에서 쫓겨남. 즉 페이지가 참조된 시점부터 d 시간동안은 메모리에 유지, 그 시점이 지나면 메모리에서 지워버림.
워킹셋 알고리즘은 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임 수보다 클 경우 일부 프로세스를 스왑 아웃시켜서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장. 이는 MPD를 줄이는 효과를 발생. 반면 프로세스들의 워킹셋을 모두 할당한 후에도 프레임이 남을 경우 스왑 아웃되었던 프로세스를 다시 메모리에 올려서 워킹셋을 할당함으로써 MPD를 증가. 이러한 방식으로 MPD를 적절히 조절하여 스레싱 방지.
윈도우 d의 크기가 너무 작으면 지역성 집합을 모두 수용하지 못할 우려, 반면 너무 크면 여러 지역성 집합을 수용할 수 있는 반면 MPD가 감소해 CPU 이용률이 낮아질 우려가 있음.
2. 페이지 부재 빈도 알고리즘(Page Fault Frequency: PFF)
프로세스의 페이지 부재율을 주기적으로 조사, 이 값에 근거해 각 프로세스에 할당할 메모리 양을 동적으로 조절. 어떤 프로세스의 페이지 부재율이 시스템이 미리 정해놓은 상한값을 넘게 되면 이 프로세스에 할당된 프레임 수가 부족하다고 판단, 프로세스에게 프레임을 추가로 할당함. 이때 할당할 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라가 있는 프로세스 수를 조절. 반면 페이지 부재율이 하한값 이하로 떨어지면 프로세스에게 필요 이상의 많은 프레임이 할당된 것으로 간주, 할당된 프레임의 수를 줄임. 메모리 내에 존재하는 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높임. 이러한 원리로 MPD를 조절하며 CPU 이용률을 높이는 동시에 스레싱을 방지.
댓글