운영체제#7 가상메모리

[yoonminsang]

8. 가상 메모리

• 프로그램이 실행되기 위해 그 프로세스의 주소 공간 전체가 메모리에 올라와 있어야 하는 것은 아니다. 당장 수행할 부분만 메모리에 올리고 나머지 부분은 드스크의 스왑영역에 내려놓았다가 다시 필요해지면 메모리에 올라와 있는 부분과 교체하는 방식을 사용한다. => 물리적 메모리 제약X
• 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이러한 메모리 공간을 가상메모리라고 부른다.
• 즉, 가상메모리는 프로세스마다 각각 0번지부터의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 존재하게 된다.

1. 요구 페이징

• 요구 페이징이란 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식을 말한다.
• 특정 프로세스를 구성하는 페이지 중에서 어떤 페이지가 메모리에 존재하고 어떤 페이지가 메모리에 존재하지 않는지 구별하기 위한 방안이 필요하다.
• 유효-무효 비트로 각 페이지가 메모리에 존재하는지 표시
• CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 page fault(페이지 부재)가 일어났다고 말한다.

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

• CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 page fault trap 발생

• CPU 제어권이 커널모드로 전환

• page fault handler(페이지 부재 처리루틴)이 호출되어 page fault를 처리

  • 접근이 적법한지 확인.
  • 적법하지 않으면 프로세스 종료
  • 물리적 메모리에서 비더있는 프레임을 할당받아 페이지를 읽어옴.
  • 비어있는 프레임이 없다면 메모리에 올라와있는 페이지 중 하나를 디스크로 쫓아냄.(스왑 아웃)
  • 메모리 적재에는 시간이 걸리기 때문에 page fault 발생시킨 프로세스는 CPU 빼앗기고 봉쇄상태. 현재 상태 PCB에 저장
  • 디스크 IO완료되어 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정, 봉쇄되어있던 프로세스를 준비큐로 이동. PCB 복원. 이전 instruction부터 실행

---

• 요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도다.

2. 페이지 교체

• page replacement(페이지 교체): 메모리에 올라와있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 것
• replacement algorithm(교체 알고리즘): 페이지 교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘. 목표는 페이지 부재율을 최소화하는 것. 그러므로 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 내쫓는 것이 성능을 향상시킬 수 있는 방안이다.
• 성능은 주어진 페이지 참조열(page reference string)에 대해 페이지 부재율을 계산함으로써 평가할 수 있다.

1. 최적 페이지 교체

• 이 알고리즘은 미래에 어떤 페이지가 어떤 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하므로 실제로 사용할 수 없다.
• 다만 다른 달고리즘에 대한 상한선을 제공한다.

2. 선입선출 알고리즘

• FIFO(First In First Out) 알고리즘은 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.
• 단순히 순서만 보다보니 비효율적인 상황이 발생할 수 있다.

3. LRU 알고리즘

• LRU(Least Recently Used) 알고리즘: 시간 지역성(temporal locality)를 활용해서 페이지 교체시 가장 오래전에 참조가 이루어진 페이지를 내쫓는다.
• 시간 지역성: 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성

4. LFU 알고리즘

• LFU(Least Frequently Used) 알고리즘: 페이지의 참조 횟수로 교체시킬 페이지를 결정. 최저 참조 횟수를 가진 페이지가 여러 개면 임의로 하나를 선정. 성능향상을 위해서는 더 오래전에 참조된 페이지를 쫓아내는게 효율적.
• 참조 횟수를 계산하는 방식에 따라 Incache-LFU, Perfect-LFU로 나눠짐
  • Incache-LFU: 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수 카운트. 쫓겨났다가 다시 들어오면 참조 횟수는 1로 초기화.
  • Perfect-LFU: 메모리와 상관없이 그 페이지의 과거 촘 참조 횟수 카운트. 참조 횟수를 정확히 아는게 장점이지만 모두 기록해야해서 오버헤드가 크다.
• LFU는 시간에 따른 페이지 참조의 변화를 반영하지 못하고, LRU모다 구현이 복잡하다는 단점이 있다.

5. 클럭 알고리즘

• 클럭 알고리즘(clock algorithm)은 하드웨어적인 지원을 통해 위와 같은 알고리즘의 운영 오버헤드를 줄였다.
• LRU를 근사시킨 알고리즘으로 NUR(not Used Recently), NRU(Not Recently Used) 알고리즘으로도 불린다.
• 클럭 아록리즘은 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트(reference bit)를 순차적으로 조사한다. 참조될때마다 하드웨어에 의해 1로 자동 세팅된다. 클럭 알고리즘은 1이면 0으로 바꾸고 0인 페이지는 교체한다.
• 간단히 말하면 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않는 페이지를 교체하는 것이다.
• 적어도 시곗바늘이 한 바퀴를 도는 데 소요되는 시간만큼 페이지를 메모리에 유지시켜둠으로써 페이지부재율을 줄이도록 설계되었기 때문에 이 알고리즘을 2차 기회 알고리즘(second change algorithm)이라고도 부른다.

3. 페이지 프레임의 할당

• 프로세스 여러 개가 동시에 수행되는 상황에서 각 프로세스에 얼만큼의 메모리 공간을 할당할 것인지 결정해야한다. 프로세스마다 페이지 프레임을 균등하게 할당할 수도 있지만 더 효율적인 메모리 할당 방법이 필요하다.

• 할당 알고리즘 세가지

1. 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 균등할당(equal allocation) 방식
2. 프로세스 크기에 비례해 페이지 프레임을 할당하는 비례할당(proportional allocation) 방식
3. 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당하는 우선순위 할당(priority allocation)

4. 전역교체와 지역교체

• 교체할 페이지를 선정할 때, 교체 대상이 될 프레임의 범위를 어떻게 설정하냐에 따라 전역 교체, 지역교체로 구분.
• 전역교체(global replacement): 모든 페이지 프레임이 교체 대상이 될 수 있다.
  • 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법
• 지역교체(local replacement): 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법
  • 페이지 프레임을 미리 할당함.

5. 스레싱

• 프로세스가 원할하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당받아야 한다. 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율(page fault rate)이 크게 상승해 CPU 이용률(utilization)이 급격히 떨어질 수 있다. 이 현상을 스레싱(thrashing)이라고 부른다.

스레싱 발생 예시

• CPU 이용률이 낮다: ready queue가 비는 경우가 발생한다.
• ready queue가 비는 경우: 모든 프로세스가 IO 작업을 한다.
• CPU 이용률이 낮으면 OS는 메모리에 올라가는 프로세스의 수를 늘린다.
• 다중 프로그래밍의 정도(Multi-Programming Degree:MPD): 메모리에 동시에 올라가 있는 프로세스의 수

정리

CPU 이용률이 낮다 => OS는 MPD를 높인다.

MPD가 과도하게 높아지면 => 각 프로세스에게 할당되는 메모리 양이 지나치게 감소한다. => 페이지 부재가 빈번하게 발생한다. => 디스크 IO 작업이 수반하므로 문맥교환을 통해 다른 프로세스에게 CPU가 이양된다. => 다른 프로세스도 할당받은 메모리가 적어서 페이지 부재가 발생한다. => 또 다른 프로세스에게 CPU가 할당된다. => 결국 ready queue에 있는 모든 프로세스에게 CPU가 한 차례씩 할당되었는데도 모든 프로세스가 다 페이지 부재를 발생시켜 시스템은 페이지 부재를 처리하느라 매우 분주해지고 CPU의 이용률은 급격히 떨어진다. => OS는 MPD를 높이기 위해 또 다른 프로세스를 메모리에 추가한다. => 프로세스당 할당된 프레임의 수가 더욱 감소하고 페이지 부재는 더욱 빈번하게 발생한다. => 페이지 교체, 스왑 인, 스왑 아웃이 지속적으로 발생하고, CPU는 거의 일하지 않는다.