VirtualMemory.md

가상메모리

운영체제는 모든 프로그램들에 공평하게 같은 크기의 메모리를 할당하기 보다는 몇몇 프로그램들에게 집중적으로 메모리를 할당한 후, 시간이 흐르면 이들로부터 메모리르 회수해서 다른 프로그램들에게 다시 집중적으로 메모리를 할당하는 방식을 채택한다.

why?
프로세스의 빠른 수행을 위해 프로그램마다 최소한 확보해야 하는 메모리의 크기가 존재하기 떄문이다

• 가상메모리는 프로세스마다 각각 0번지부터의 주소 공간을 가지게 되며,
  이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑영역에 존재하게 된다.

• 가상메모리기법은 요구 페이징(demand paging) 방식과 요구 세그먼테이션(demand segmentation) 방식으로 구현된다.

요구 페이징 (demand paging)

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

장점)

• 필요한 페이지만을 메모리에 적재하기 떄문에 메모리 사용량이 감소한다.
• 프로세스 전체를 메모리에 올리는 입출력 오버헤드가 줄어든다.
• 응답시간을 단축시킬 수 있다.
• 시스템이 더 많은 프로세스를 실행 할 수 있다.
• 물리적 메모리의 용량 제약이 없다. 즉, 물리적 메모리의 용량보다 큰 프로그램을 실행할 수 있다.

특징)

• 메모리에 올라와 있지 않는 페이지는 디스크의 스왑 영역에 존재한다.

• 유효-무효 비트(valid-invalid bit)를 두어 각 페이지가 메모리에 존재하는지 표시한다.

  • 유효값 : 메모리에 존재
  • 무효값 : 스왑영역에 존재

• CPU가 참조혀려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 '페이지 부재 (page fault)' 라고 한다.

페이지 교체

페이지 부재가 발생 시, 요청된 페이지를 디스크에서 메모리로 읽어온다.

이때, 물리적 메모리에 빈 프레임이 존재하지 않을 경우 메모리에 올라와 있는 페이지 중 하나를 디스크로 보내서 메모리에 빈 공간을 확보하는 작업을 말한다.

1. 최적 페이지 교체 (OPT)

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체한다.

• 장점 : 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.
• 단점 : 구현의 어려움, 모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없다.

2. FIFO

먼저 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다.

• 장점 : 이해하기 쉽고, 프로그램하기도 쉽다.
• 단점 : 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다. 페이지를 저장할수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 Belady의 모순이 존재한다.

3. LRU

메모리 페이지의 참조 성향 중 중요한 성질 중 하나인 시간지역성이라는 것이 있다. 시간지역성이란 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 말한다.

LRU 알고리즘은 이와 같은 성질을 활용해서 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 교체한다.

• 즉, 마지막 참조 시점이 가장 오래된 페이지를 교체한다.
• FIFO 알고리즘보다 우수하고, OPT 알고리즘보다 그렇지 못한다.

4. LFU

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

• 어떤 프로세스가 특정 페이지를 집중적으로 사용하다가, 다른 기능을 사용하게 되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되는 단점이 있다.
• LRU 알고리즘보다 오랜 시간 동안의 참조 기록을 반영할수 있다는 장점이 있다.

5. MFU

참조 횟수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.

6. 클럭 알고리즘

하드웨어적인 지원을 통해 알고리즘의 운영 오버헤드를 줄인 방식으로 LRU를 근사시킨 알고리즘으로
NUR or NRU 알고리즘으로도 부른다.

LRU 알고리즘은 가장 오래전에 참조된 페이지를 교체하는 것에 비해
클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다.

• 클럭 알고리즘은 하드웨어적인 지원으로 동작하기 떄문에 LRU에 비해 페이지의 관리가 훨씬 빠르고 효율적으로 이루어진다.
• 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 사용한다.

스레싱 (thrashing)

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

• 스레싱 발생을 방지하는 방법에는 워킹셋 알고리즘과 페이지 부대 빈도 알고리즘이 있다.

워킹셋 알고리즘

집중적으로 참조되는 페이지들의 집합을 지역성 집합(locality set)이라고 하며,
워킹셋 알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이다.

• 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 워킹셋으로 정의한다.
• 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다.
• 그렇지 않을 경우에는 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃 시킨다.
• 즉, 워킹셋 알고리즘은 MPD 다중 (프로그래밍의 정도, Multi-programming Degree)를 조절하여 스레싱을 방지한다.

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

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

• 어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해놓은 상한값 (upper bound)를 넘게 되면 이 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 이 프로세스에게 프레임을 추가로 더 할당한다.

• 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라가 있는 프로세스의 수를 조절한다.

• 프로세스의 페이지 부재율이 하한값(lower bound) 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 겂으로 간주해 할당된 프레임의 수를 줄인다.