OS for Beginner(3)

  가상 메모리에 관한 개념들에 대해 간단하게 알아보도록 하겠습니다. 여러 프로그램이 동시에 수행되는 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어서 사용한다. 따라서 운영체제는 어떤 프로그램에게 어느 정도의 메모리를 어떤식으로 할당할 것인지에 대해 결정해야 한다. 보통은 모든 프로그램에게 공평하게 메모리를 할당하기 보다는 몇몇 프로그램들에게 집중적으로 메모리를 할당한 후, 나중에 이들로부터 메모리를 회수해서 다른 프로그램들에게 다시 집중적으로 메모리를 할당하는 방식을 채택한다. -> 프로세스의 빠른 수행을 위하여 프로그램마다 최소한 확보해야 하는 메모리의 크기가 존재하기 때문이다. 

가상메모리는 프로세스 전체가 메모리내에 올라오지 않더라도 실행이 가능하도록 하는 기법이며 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.

 

  과거에는 실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 메모리 용량보다 큰 프로그램은 실행 시킬 수 없었다. 

현재 운영체제는 CPU에서 당장 수행 해야할 부분만을 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 채택한다. -> 메모리의 연장 공간으로 디스크의 스왑 영역이 사용될 수 있기 때문에 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 생각할 필요가 없어진다. 또한 더 많은 프로그램을 동시에 실행할 수 있게 된다. 이에따라 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다 

 

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

Demand Paing(요구 페이징)

  프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라 하며, 가상 메모리 시스템에서 많이 사용된다. 구체적으로 말하면 프로그램 실행시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식이다. 따라서 요구 페이징 기법은 특정 페이지에 대한 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다. 즉, 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다. -> 메모리 사용량 감소, 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 줄어든다. 물리적 메모리의 용량 제약 벗어난다 -> 물리적 메모리의 용량보다 큰 프로그램도 실행할 수 있다. 

  그리고 특정 프로세스를 구성하는 페이지 중에서 어떤 페이지가 메모리에 존재하고 어떤 페이지가 메모리에 존재하지 않는지 구별하기 위해 유효-무효비트(valid-invalid)비트를 두어 각 페이지가 메모리에 존재하는지 표시하게 된다.

페이지 교체

페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다. 이 경우 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 작업이 필요하다. 이것을 페이지 교체(page replacement)라고 한다. 

*페이지 부재: CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재가 발생했다고 한다. 페이지 교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 페이지 알고리즘이라고 한다. 이 알고리즘의 목표는 페이지 부재율을 최소화 하는 것. -> 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 디스크로 보내는 것이 성능을 향상 시킬 수 있다. 

페이지 교체 알고리즘

Goal: lowest page_fault rate

• FIFO 페이지 교체
• 최적 페이지 교체(Optimal Page Replacement)
• LRU 페이지 교체(LRU Page Replacement)
• MFU 페이지 교체(MFU Page Replacement)

FIFO 페이지 교체

가장 간단한 페이지 교체 알고리즘으로 FIFO(first-in first-out)의 흐름을 가진다. 즉, 물리 메모리에 먼저 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다는 것이다. 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기 때문에 비효율적인 상황이 발생할 수 있다. 예를들어, 가장 먼저 물리적 메모리에 들어온 페이지가 계속해서 많은 참조가 이루어진다 하더라도 FIFO알고리즘은 이 페이지를 내쫓게 되는 것이다.

• 장점: 이해하기도 쉽고, 프로그램하기도 쉽다
• 단점: 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.

최적 페이지 교체

페이지 부재율을 최소화 하기 위해서는 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내면 된다. 이러한 최적의 알고리즘을 빌레디의 최적 알고리즘이라 한다. 

• 장점: 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.
• 단점: Impossible to implement. Requires the knowledge of future. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문이다.

LRU 페이지 교체, LRU: Least-Recently-Used

페이지 교체 알고리즘의 성능 향상을 위해서는 향후 사용될 가능성이 낮은 페이지를 우선적으로 메모리에서 쫓아내는 것이 바람직하다. 최적 알고리즘의 근사 알고리즘으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.(Replace the page that has not been used for the longest time) 대체적으로 FIFO 알고리즘 보다 우수하고, OPT 알고리즘 보다는 그렇지 못한 모습을 보인다. 

• How to keep track of last page access? 마지막으로 참조된 페이지가 뭐고 가장 오랫동안 사용되지 않은 페이지를 어떻게 알아?
• 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교(stack, counter을 활용해서)해야하므로 운영시간적인 오버헤드가 발생한다. 

클럭 알고리즘

클럭 알고리즘은 LRU를 근사시킨 알고리즘이다. LRU알고리즘이 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이라면 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. 즉 최근에 참조되지 않은 페이를 교체 대상으로 선정한다는 측면에서 LRU와 유사하지만 교체되는 페이지의 참조시점이 가장 오래되었다는 것을 보장하지 못한다는 점에서 LRU를 근사시킨 알고리즘으로 볼 수 있다. 즉 클럭알고리즘은 최근에 참조되지 않은 페이지를 선정한다. 하지만 그 페이지가 가장 오랫동안 사용되지 않은 것인지는 보장하지 못한다. 

• 하드웨어적인 지원으로 동작하기 때문에 LRU보다 페이지의 관리가 훨씬 빠르고 효율적이다. 

아래 두 교체 방법은 Counting Algorithms. -> Keep a counter of the number of reference that have been made to each page. 참조 횟수를 파악해서 교체하는 알고리즘. 

LFU(Least Frequency Used) 페이지 교체

참조 횟수가 가장 적은 페이지를 교체하는 방법이다. (replace the page with the smallest count)활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘이다. 

최적 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다. 

MFU(Most Frequency Used) 페이지 교체

참조횟수가 가장 많은 페이지를 교체한다.(Replace the page with the largest count)