[운영체제] 가상메모리

• 운영체제가 어떤 식으로 프로세스에게 메모리를 할당할 것인가
• 여러 프로그램이 동시에 수행되는 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어 사용
• 가상메모리(virtual memory) : 프로세스마다 각각 0번지로부터의 주소공간을 가지고 이들 공간 중 일부가 물리적 메모리에 적재되고(당장 수행해야 할 부분) 일부는 디스크의 스왑 영역에 존재하게 된다.
• 프로세스의 주소 공간을 메모리에 적재하는 방식에 따라 요구 페이징 방식과 요구 세그먼테이션 방식으로 구현될 수 있다.

1. 요구 페이징

• 요구 페이징 : 프로그램 실행 시 프로세스의 모든 페이지를 한 번에 메모리에 올리는 것이 아닌 당장 사용할 페이지만을 올리는 방식 → 특정 페이지에 대한 CPU의 요청이 들어온 후에야 해당 페이지를 메모리 적재
• 메모리 사용량이 감소하고 프로세스 전체를 메모리에 올림으로써 소요되었던 입출력 오버헤드도 줄어든다. (사용하지 않을 주소 영역에 대한 입출력때문에 응답시간 길어짐)

요구 페이징에서의 유효-무효 비트(valid-invalid bit)

• 유효-무효 비트 : 특정 프로세스 중에서 어떤 페이지가 메모리에 올라와 있고 어떤 페이지가 올라오지 않았는지 구별해주는 비트

유효값 : 특정 페이지가 참조되어 메모리에 적재되는 경우
무효값 : 메모리에 적재되었던 페이지가 디스크의 스왑 영역으로 쫓겨나거나 그 페이지가 속한 주소 영역을 프로세스가 사용하지 않을 때

• CPU가 참조하려는 페이지가 현재 메모리에 올라와있지 않은 경우를 페이지 부재(page fault)라 한다.

① 페이지 부재

• CPU가 무효 페이지에 접근하면 MMU(메모리 관리장치)는 페이지 부재 트랩을 발생시키고, CPU의 제어권이 커널모드로 전환되면서 OS의 페이지 부재 처리 루틴을 수행한다.

㉮ 부재 상태의 페이지를 메모리에 적재하기 앞서 해당 페이지에 대한 접근이 적절한지 OS에서 체크
㉯ 사용되지 않는 주소 영역의 페이지에 대한 접근이거나 해당 페이지에 대한 접근 권한 위반을 했다면 프로세스를 종료시킨다. (접근 권한 위반 : 읽기 전용 페이지에 대한 쓰기 접근)
㉰ 페이지에 대한 접근이 적절하다고 판명났다면 물리적 메모리에서 빈 프레임을 할당 받아 그 공간에 해당 페이지를 읽어오고, 빈 프레임이 없다면 메모리에 있는 기존 페이지들 중 하나를 스왑 아웃시킨다.
㉱ 페이지 부재를 발생시킨 프로세스는 입출력 요청을 한 것임으로 CPU를 빼앗기고 봉쇄 상태가 된다. 이 때 수행되던 CPU 레지스터 상태 및 프로그램 카운터 값은 PCB에 저장된다.
㉲ 디스크 입출력이 완료되어 인터럽트가 발생하면 해당 프로세스는 봉쇄 상태에서 벗어나 준비 큐로 이동하고, 다시 CPU를 할당받으면 PCB에 저장된 값을 불러와 중단되었던 명령으로부터 실행을 재개한다.

 

② 요구 페이지 성능

※ 유효 접근 시간(effective access time)

• 유효접근시간 = (1-P) * 메모리 접근시간 + P * (page fault가 일어났을 때 걸리는 시간)
• P : 페이지 부재 발생 비율
• page fault 일어났을 때 : 페이지 부재 발생 처리, 빈 프레임이 없을 경우 스왑 아웃, 요청된 페이지의 스왑 인, 프로세스 재시작 오버헤드
• 지역성의 원리 : 해당 값에 대한 스토리지가 자주 엑세스되는 특성 → 실제 페이지 부재 확률은 매우 낮다.
• HDD의 접근 시간이 매우 느리므로 swap device로 SSD 또는 저가 DRAM을 사용 가능하다.

---

2. 페이지 교체 (Page Replacement)

• 페이지 부재가 발생했을 경우 요청 페이지를 디스크로부터 메모리로 불러와야 하는데, 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
• 페이지 교체 : 위와 같은 상황에서 메모리에 올라온 페이지 하나를 내쫓아 빈 공간을 확보하는 작업
• 페이지 교체 알고리즘 : 어떤 페이지를 내쫓을지 결정하는 알고리즘
• 페이지 부재율을 최소화시켜야 하므로 가까운 미래에 참조될 가능성이 가장 낮은 페이지를 선택해야 한다.
• 주어진 페이지 참조열(참조되는 페이지들의 번호를 시간 순서에 따라 나열한 것)을 통해 페이지 부재율을 계산함으로써 페이지 교체 알고리즘의 성능을 평가할 수 있다.

① 최적 페이지 교체

• 페이지 교체 시 가장 먼 미래에 참조될 페이지를 내쫓는다.
• 빌레디의 최적 알고리즘(Belady's optimal algorithm) 또는 MIN, OPT 등의 이름으로 불린다.
• 미래에 어떤 페이지가 어떤 순서로 참조될지 미리 알고 있다는 전제 하에 알고리즘을 운영하므로 실제 시스템에서 온라인으로 사용될 수 있는 알고리즘이 아니다. → '오프라인 알고리즘'

② 선입선출 알고리즘(FIFO)

• 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.
• 페이지의 향후 참조 가능성을 생각하지 않고 들어온 순서대로 내쫓을 페이지를 선정하기 때문에 비효율적이다.

▷ FIFO anomaly (FIFO 이상현상, Belady's anomaly)

• 위의 그림에서 볼 수 있는 것처럼 물리적 메모리의 공간이 늘어났음에도(프레임 수) 페이지 부재의 수는 더 늘어난 이상 현상을 볼 수 있다.

③ LRU 알고리즘

• 시간지역성 : 메모리 페이지의 참조 성향 중 한 가지 성질로 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질
• LRU 알고리즘 : 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 내쫓는다.

④ LFU 알고리즘

• 페이지의 참조 횟수로 교체시킬 페이지 결정, 물리적 메모리 내 존재하는 페이지 중 과거에 가장 참조 횟수가 적었던 페이지를 내쫓는다.
• 페이지의 참조 횟수를 계산하는 방식에 따라 Incache-LFU 와 Perfect-LFU의 다른 방식으로 구현할 수 있다.

Incache-LFU : 페이지가 물리적 메모리에 올라온 후부터 참조 횟수를 카운트, 만약 메모리에서 쫓겨났다가 다시 들어왔다면 카운트는 1부터 다시 시작한다.
Perfect-LFU : 페이지의 과거 총 참조 횟수 카운트, 오버헤드가 상대적으로 더 크다.

• LRU 알고리즘과 비교했을 때 장기적인 시간 규모에서의 참조 성향을 고려한다는 장점이 있지만 시간에 따른 페이지 참조의 변화를 전혀 반영하지 못하고(시간지역성 고려 X), 구현이 복잡하다는 단점이 있다.

⑤ 클럭 알고리즘(Clock Algorithm)

• 위의 LRU 알고리즘과 LFU 알고리즘은 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교해야 하므로 시간적인 오버헤드가 발생한다.
• 클럭 알고리즘 : LRU를 근사시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘으로도 불린다. 하드웨어적인 지원을 통해 위에서 말한 운영 오버헤드를 줄였다.
• 최근에 참조되지 않은 페이지를 교체 대상으로 선정한다는 점에서 LRU와 비슷하지만, 그 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.

클럭 알고리즘

• 페이지 프레임들의 참조 비트(reference bit)를 순차적으로 조사한다. 참조 비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.
• 참조 비트가 1인 페이지는 0으로 바꾼 후 그냥 지나가고 참조 비트가 0이라면 교체한다.
• 시곗바늘이 한 바퀴 도는 동안 참조되지 않은 페이지는 교체 대상이 되는 것이다. 최근에 참조되지 않은 알고리즘을 메모리에 유지시켜 놓는다고 할 수 있음. (2차 기회 알고리즘으로도 불린다.)

---

3. 페이지 프레임의 할당

• 프로세스가 여러 개가 동시에 실행되는 상황에서 각 프로세스에 얼마의 메모리를 할당할 것인지를 정해야 한다.
• 할당 알고리즘(allocation algorithm)을 3개로 나눌 수 있음.

① 균등 할당

• 모든 프로세스에게 페이지 프레임을 균일하게 할당

② 비례 할당

• 프로세스의 크기에 비례해 페이지 프레임을 할당
• 프로세스의 크기를 고려한 균등 할당 방식

③ 우선순위 할당

• 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당
• 당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분해 전자 쪽에 더 많은 페이지 프레임을 할당한다.

• 위의 할당 알고리즘으로만은 프로세스의 페이지 참조 특성을 제대로 반영하지 못한다.
• CPU에서 명령을 수행할 때는 여러 페이지를 동시에 참조한다. (프로세스의 주소 공간 중 코드, 데이터 스택 등 각기 다른 영역을 참조) → 일정 수준 이상의 페이지 프레임을 프로세스에 할당해야 한다.
• 예시로 반복문을 구성하는 페이지는 한번에 메모리에 올려놓는 것이 유리한데, 이는 반복문에서 매 반복마다 페이지 부재가 적어도 한 번 이상 일어난다면 시스템의 성능이 현저히 저하되기 때문이다.

---

4. 전역교체와 지역교체

• 교체할 페이지를 선정할 때 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역교체와 지역교체로 구분할 수 있다.

※ 전역교체 (Global Replacement)

• 모든 페이지 프레임 (다른 프로세스 포함) 이 교체 대상이 될 수 있음
• 프로세스마다 메모리를 할당하는 것이 아니라 전체 메모리를 각 프로세스가 공유해서 사용하고, 교체 알고리즘에 근거해 각 프로세스에 할당되는 메모리 양이 가변적으로 변한다.

※ 지역교체 (Local Replacement)

• 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있음
• 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 한다.

---

5. 스레싱 (thrashing)

• 스레싱 : 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하여 페이지 부재율이 크게 상승하고 CPU 이용률이 급격히 떨어지는 현상
• 다중 프로그래밍의 정도(MPD) : 메모리에 동시에 올라가 있는 프로세스의 수

※ 스레싱이 발생하는 시나리오

스레싱의 발생

1. CPU의 이용률이 낮을 경우 운영체제에서는 메모리에 올라온 프로세스의 수가 적기 때문이라고 판단하게 된다.
2. CPU 이용률이 낮으면 OS에서는 메모리에 올라가는 프로세스의 수(MPD)를 늘린다.
3. MPD가 과도하게 높아지면 각 프로세스에 할당되는 메모리의 양이 지나치게 줄어든다. → 페이지 부재가 빈번하게 발생
4. 페이지 부재가 발생하면 I/O 작업으로 인해 CPU를 다른 프로세스에 이양, 하지만 다른 프로세스 역시 할당받은 메모리의 양이 적다면 또 다시 페이지 부재가 일어난다.
5. 시스템은 페이지 부재를 처리하느라 분주해지고 CPU 이용률은 낮아진다. 이 상황에서 OS는 MPD를 높이기 위해 또 다른 프로세스를 메모리에 추가한다.
6. 프로세스들은 계속해서 서로의 페이지를 교체하며 스왑 인과 스왑 아웃을 발생시키고 CPU는 대부분의 시간에 일을 하지 않게 되는 현상을 스레싱이라 한다.

• 스레싱이 발생하지 않도록 하면서 CPU 이용률을 최대한 높일 수 있도록 MPD를 조절하는 것이 중요하다.
• MPD를 적절히 조절해 CPU 이용률을 높이는 동시에 스레싱을 방지하는 방법에 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 있다.

① 워킹셋 알고리즘(working-set alogrithm)

프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있음
지역성 집합(locality set) : 이렇게 집중적으로 참조되는 페이지들의 집합

• 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘
• 워킹셋 : 프로세스가 일정시간동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
• 프로세스의 워킹셋을 구성하는 페이지들이 한번에 메모리에 올라갈 수 있을 상황에만 그 프로세스에게 메모리를 할당하고 그렇지 않다면 프로세스에 할당된 페이지 프레임들을 전부 반납시키고 그 프로세스의 주소 공간 전체를 스왑 아웃시킨다. (MPD를 조절하고 스레싱 방지)

② 페이지 부재 빈도 알고리즘(page-fault frequency algorithm)

• 프로세스의 페이지 부재율을 주기적으로 조사하고, 이 값에 근거해 각 프로세스에 할당할 메모리 양을 동적으로 조절
• 어떤 프로세스의 페이지 부재율이 시스템에서 정해놓은 상한값을 넘는다면, 이 프로세스에게 프레임을 추가로 할당, 이 때 할당할 프레임이 없다면 다른 프로세스를 스왑 아웃시켜 메모리에 올라간 프로세스의 수를 조절한다.
• 페이지 부재율이 하한값 아래로 떨어진다면 이 프로세스에 필요 이상으로 많은 프레임이 할당되었다고 판단할 수 있고 할당된 프레임의 수를 줄인다.
• 이러한 방식으로 메모리 내 모든 프로세스에 필요한 프레임을 다 할당했음에도 프레임이 남는다면, 스왑 아웃된 프로세스에게 프레임을 할당함으로써 MPD를 높인다.