운영체제와 정보기술의 원리 - CH8. 가상 메모리

다음은 반효경 교수님의 ‘운영체제와 정보기술의 원리’ CH8. 가상 메모리를 읽고 정리한 내용입니다 🙌

🌩 들어가기 전

• 시분할 환경에서는 여러 프로세스가 동시에 메모리에 올라와서 수행되기 때문에 어떤 메모리에 어느 정도의 메모리를 할당해야할지가 문제이다.
• 운영체제는 몇몀 프로그램에게 집중적으로 메모리를 할당하고 시간이 흐른다음 메모리를 회수하여 다른 프로그램에게 집중적으로 메모리를 할당하는 방식을 택한다.
  • 프로그램마다 프로세스를 빠르게 수행하기 위해서 확보해야하는 최소한의 메모리 크기가 있기 때문이다.
• 프로세스의 전체가 올라가는 것이 아니라 스왑 영역에 일부분은 내려놓기 때문에 프로세스 입장에서 물리 메모리 크기 제약은 생각하지 않게 된다.
• 또한 운영체제는 각 프로세스가 자기만 메모리에 올라간 것처럼 여겨질 수 있는 가장 메모리를 지원한다.
  • 각자의 주소 공간을 가정하여 모든 프로세스가 0번지부터 시작한다.
  • 일부는 스왑 영역에 일부는 메모리에 있다.
• 프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 가상메모리 기법은 요구 페이징 (demand paging) 방식과 요구 세그멘테이션 (demand segmentation) 으로 구현된다.
  • 대부분 요구 페이징을 사용하고 요구 세그먼테이션은 페이지드 세그먼테이션 기법을 사용하는 경우에 많이 사용한다.

🌩 1. 요구 페이징

• 당장 사용될 페이지만 메모리에 올리는 방식이다.
• 요구 페이징은 특정 페이지에 대한 CPU의 요청이 들어온 후에 페이지를 메모리에 적재한다.
• 장점
  • 메모리 사용량 감소
  • 프로세스 전체를 메모리에 올리는 입출력 오버헤드 감소
  • 사용하지 않을 주소 영역의 입출력은 안해도 되므로 응답시간 단축
  • 시스템이 더 많은 프로세스를 수용할 수 있도록 함
  • 프로그램이 물리적 메모리의 용량 제약에서 벗어남
• 어떤 페이지가 메모리에 존재하고 어떤 페이지가 메모리에 존재하지 않은지 구별이 필요하다.
  • 유효-무효 비트 (valid-invalid bit)를 두어 각 페이지가 메모리에 존재하는지 표시한다.
  • 페이지 테이블의 각 엔트리에 저장된다.
  • 프로세스 시작 전 모든 페이지의 유효-무효 비트는 무효값이다.
  • 특정 페이지가 참조되면 유효값으로 바뀌고 스왑 영역으로 쫓겨나면 다시 무효값이 된다.
• 유효-무효 비트는 페이지가 속한 영역을 프로세스가 사용하지 않는 경우도 표시한다.
• CPU 참조 페이지가 메모리에 올라와 있지 않아서 무효값인 경우를 페이지 부재 page fault 라고 한다.

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

• CPU가 무효 페이지에 접근하면 주소 변환 담당 하드웨어 MMU가 페이지 부재 트랩 page fault trap을 발생시킨다.
• 제어권이 커널모드로 전환되어 운영체제의 페이지 부재 처리루틴 page fulat handler가 호출되어 다음 순서로 페이지 부재를 처리한다.
  1. 해당 페이지에 대한 접근이 적법한지 체크
     • 사용되지 않는 주소 영역이거나 해당 페이지에 대한 접근 권한을 위반 protection violation한 경우 해당 프로세스를 종료
  2. 적법하다면 물리 메모리의 비어있는 프레임 frame을 할당받아 그 공간에 해당 페이지를 읽는다.
     • 비어있는 프레임이 없다면 기존에 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아낸다. (스왑 아웃)
• 페이지 부재로 페이지를 메모리에 적재하기까지 오랜 시간이 걸리기 때문에 페이지 부재 프로세스는 봉쇄 상태가 된다. (CPU 제어권이 없어진다)
  • CPU 레지스터 상태 및 카운터값을 PCB에 저장한다.
• 디스크 입출력이 완료되고 인터럽트가 발생하면 페이지 테이블의 페이지 유효-무효 비트를 유효로 설정하고 봉쇄 상태 프로세스를 준비큐로 옮긴다.

2) 요구 페이징의 성능

• 페이지 부재의 발생 빈도로 성능에 가장 큰 영향을 미친다.
• 페이지가 메모리에 있다면 메모리 접근 시간만 걸리지만 페이지 부재가 일어나면 많은 오버헤드가 동반된다.
  • 페이지 부재 발생 처리 오버헤드
  • 스왑 아웃 오버헤드
  • 수왑 인 오버헤드
  • 프로세스 재시작 오버헤드

🌩 2. 페이지 교체

• 물리 메모리에 빈 프레임이 존재하지 않는다면 올라와 있는 페이를 스왑 아웃 시켜야하는데 그것을 페이지 교체라고 한다. page replacement
• 어떤 페이지를 쫓아낼 것인지 교체 알고리즘 replacement algorithm으로 결정한다.
  • 페이지 부재를 최소화 하는 것이 알고리즘의 목표이다.
• 페이지 교체 알고리즘은 페이지 참조열 page reference string에 대한 페이지 부재율을 계산하여 평가한다.
• 페이지가 이미 메모리에 올라와 있으면 hit 아니면 페이지 부재이다.

1) 최적 페이지 교체

• 가장 먼 미래에 참조될 페이지를 쫓아내는 방법이다.
• 빌레디 최적 알고리즘, MIN, OPT, Belady’s optimal algorithm 라고 부른다.
• 미래에 어떤 페이지가 어떤 순서로 참조될지 미라 알고 있는 전제로 알고리즘을 운영하므로 실제 시스템에서 사용할 수 있는 알고리즘은 아니다. ⇒ 오프라인 알고리즘
• 빌레디 최적 알고리즘은 실제 시스템에 활용되기 보다 다른 알고리즘의 성능의 상한선을 제공한다.

2) 선입선출 알고리즘 FIFO

• 페이지 교체 시 물리 메모리에 가장 먼저 올라온 페이지를 우선 내쫓는다.
• 비효율적인 상황이 발생할 가능성이 있다. 물리 메모리 공간이 늘어나도 페이지 참조 순서에 따라서 성능이 더 나빠질 수도 있다.
• FIFO에서 물리 메모리 영역에 올라갔는데도 페이지 부재가 늘어난 상황을 FIFO 이상 현상 (FIFO anomaly)라고 한다.

3) LRU Least Recently Used

• 메모리 참조 성향 중 시간지역성 (temporal locality) 라는 것이 있다.
  • 최근 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질이다.
• 위 성질을 이용하여 페이지 교체 시 가장 오래전에 참조한 페이지를 쫓아낸다.

4) LFU Least Frequently Used

• 페이지 참조 횟수로 교체 페이지를 결정한다.
• 과거에 참조 횟수 reference count가 가장 적었던 페이지를 교체하도록 한다.
• 여러개의 페이지가 후보라면 그 중 하나를 임의로 선정하며 주로 상대적으로 오래 전에 참조된 페이지를 스왑 아웃한다.
• LFU의 페이지 참조 횟수 계산 방식
  1. Incache-LFU
     • 페이지가 물리 메모리에 올라온 후부터 참조 횟수를 카운트 한다.
     • 메모리에서 쫓겨났다가 다시 올라오면 참조 횟수를 1부터 시작한다.
  2. Perfect-LFU
     • 그 페이지의 과거 참조 횟수를 모두 카운ㅌ한다.
     • 정확하나 메모리에서 쫓겨난 페이지 참조 기록까지 보관해야하는 오버헤드가 있다.
• LFU는 LRU 보다 오랜 시간 동안의 참조 기록을 반영하고 장기적 시간 규모의 참조 성향을 고려한다.
• 하지만 LFU는 시간에 따른 페이지 참조 변화를 반영하지 못하며 구현이 LRU보다 복잡하다.

5) 클럭 알고리즘

• LRU, LFU 는 참조 시각, 참조 횟수를 소프트웨어적으로 유지하고 비교하므로 알고리즘 운영 비용이 발생한다.
• 클럭 알고리즘은 하드웨어의 지원으로 알고리즘의 운영 오버헤드를 줄인 것이다.
• 클럭 알고리즘은 LRU를 근사시킨 알고리즘으로 NUR Not Used Recently 또는 NRU Not recently Used 라고 불린다.
• 오래전에 참조된 페이지 중 하나를 교체하는데 가장 오래된 것은 보장할 수 없다.
• 하드웨어의 지원이 있기 때문에 LRU에 비해 페이지 관리가 빠르고 효율적이다.
  • 대부분이 클럭 알고리즘으로 페이지 교체 알고리즘을 사용한다.
• 클럭알고리즘은 페이지 프레임의 참조비트를 순차적으로 조사한다.
  • 참조비트는 각 프레임에 존재하며 해당 프레임의 페이지가 참조될 때 하드웨어로 1로 자동 세팅된다.
• 클럭 알고리즘은 참조비트가 1인 페이지를 0으로 바꾸고 지나간다. 참조비트가 0인 페이지는 교체한다.
  • 즉, 시간을 한바퀴 돌 동안 참조되지 않은 페이지들을 교체하는 것이다.
• 특정 클럭 주기동안 참조된 페이지를 메모리에 유지시켜둠으로 페이지 부재를 줄이기 때문에 2차 기회 알고리즘 second chance algorithm이라고 하기도 한다.

🌩 3. 페이지 프레임의 할당

• 어느 프로세스에게 얼만큼의 페이지 프레임을 할당할지 결정한다.
• 기본적인 할당 알고리즘 allocation algorithm은 다음 3가지 이다.
  1. 균등할당 equal allocation - 모든 프로세스에게 페이지 프레임을 균일하게 할당
  2. 비례할당 proportional allocation - 프로세스의 크기에 비례해 프레임 할당
  3. 우선순위 할당 priority allocation - 프로세스의 우선순위에 따라 프레임 할당
     • 당장 CPU에서 실행될 프로세스에게 더 많은 페이지 프레임을 할당
• 하지만 할당 알고리즘으로 프로세스 페이지 참조 특성을 제대로 반영하지 못할 수도 있다.
  • 현재 수행중인 프로세스가 지나치게 많으면 프로세스당 할당되는 메모리가 과도하게 적다.
  • 프로세스를 정상적으로 수행하려면 일정 수준 이상의 페이지 프레임을 각 프로세스에게 할당해야한다. (여러 프레임을 동시에 참조하기 때문이다. 코드, 데이터 영역 등등)
  • 반복문인 경우 관련 페이지를 한꺼번에 올리는 것이 성능에 좋다.
• 종합적으로 각 프로세스의 프레임 수를 결정할 필요가 있다.

🌩 4. 전역교체와 지역교체

• 교체 페이지를 결정할 때 교체 대상 프레임의 범위에 따라서 교체 방법을 전역교체 global replacement, 지역교체 local replacement로 구분한다.
• 전역 교체 - 모든 페이지 프레임이 교체 대상
  • 다른 프로세스에게 할당된 프레임도 빼앗을 수 있다.
  • 프로세스별 프레임 할당량이 조절될 수 있다.
• 지역 교체 - 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정
  • 지역 교체는 프로세스마다 프레임을 미리 할당한다.
  • LRU, LFU 알고리즘을 프로세스별로 독자적 운영하면 지역교체가 된다.

🌩 5. 스레싱 thrashing

• 프로세스가 원활하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당받아야한다.
  • 집중적으로 참조되는 페이지를 한꺼번에 적재하지 않으면 페이지 부재율이 높아진다.
  • 입출력이 많아지므로 CPU 이용률이 떨어진다.
  • 위 현상을 스레싱이라고 한다.
• 운영체제는 CPU 이용률이 낮다는 것은 메모리에 올라온 프로세스의 수가 적기 때문이라고 판단한다. 따라서 CPU 이용률이 떨어지면 운영체제는 메모리에 올라와 있는 프로세스 수를 늘린다.
• 다중 프로그래밍의 정도 Multi-programming Degree MPD 라고 부른다.
  • CPU 이용률이 낮으면 운영체제는 MPD를 높인다.
• 과도하게 MPD가 높아지면 각 프로세스에게 할당되는 메모리가 줄어들고 필요한 최소한 프레임 할당이 어렵다.
• 따라서 페이지 부재가 더 빈번하게 발생하게 되고 디스크 I/O 작업이 많이 일어나며서 문맥교환으로 다른 프로세스에게 CPU를 넘긴다.
• 반복되면서 CPU는 문맥교환과 페이지 부재 처리를 하느라 바빠지고 CPU이용률이 떨어지게 된다.
  • 그러면 또 운영체제는 메모리에 프로세스를 더욱 올려 상황을 악화시킨다.
• 이것을 방지하기 위해 MPD를 조절하는 알고리즘으로 1) 워킹셋 알고리즘 2) 페이지 부재 빈도 알고리즘이 있다.

1) 워킹셋 알고리즘 working-set algorithm

• 지역성 집합 locality set: 프로세스가 특정 주소 영역을 집중적으로 참조하는 경향
• 워킹셋 알고리즘은 이런 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장해주는 메모리 관리 알고리즘이다.
• 한꺼번에 메모리에 올라와야하는 페이지 집합을 working set으로 정의하여 한꺼번에 메모리에 올라갈 수 있을 때만 메모리를 할당한다.
  • 그렇지 않다면 프로세스에 할당된 페이지 프레임을 모두 반납시키고 프로세스 전체를 스왑아웃시킨다.
• 다중 프로그래밍의 정도를 조절하고 스레싱을 방지한다.
• 구현 방법
  • 한꺼번에 올라갈 워킹셋을 정의하기 위해 워킹셋 윈도우 working-set window를 사용한다.
  • 워킹셋 윈도우는 특정 시간동안 참조된 페이지의 중복제거된 집합이다. 그 시간 이후 워킹셋에 포함된 페이지만 메모리에 유지되고 아닌 페이지는 메모리에서 쫓겨난다.
  • 워킹셋의 크기의 합이 프레임의 수보다 크면 일부 프로세스를 스왑 아웃 시켜 프레임에 워킹셋이 모두 올라갈 수 있도록 보장한다.
    • MPD 를 줄인다.
  • 만일 프레임이 남으면 스왑 아웃 프로세스를 다시 메모리에 올려 워킹셋을 할당한다.
    • MPD를 증가시킨다.
  • 윈도우 크기의 결정이 중요하다.
    • 너무 작으면 지역성 집합 수용이 어렵댜.
    • 크면 MPD가 감소하여 CPU 이용률이 낮아질 수 잇다.

2) 페이지 부재 빈도 알고리즘 PFF page fault frequency

• 프로세스의 페이지 부재율을 주기적으로 조사하여 근거해 프로세스 할당 메모리를 동적으로 조절한다.
• 어떤 프로세스의 페이지 부재율이 시스템의 상한값을 넘으면 이 프로세스에게 할당된 프레임 수가 부족하다고 판단한다.
  • 프레임을 추가로 할당한다.
• 추가로 할당할 프레임이 없으면 일부 프로세스를 스왑 아웃시켜 프로세스의 수를 조절한다.
• 부재율이 하한값 이하로 떨어지면 지나치게 많은 프레임을 할당받은 것으로 간주하고 할당 프레임 수를 줄인다.
• 이렇게 다 조절 후 프레임이 남으면 스왑 아웃 프로세스에게 프레임을 할당한다.
  • MPD 증가