[CS] 운영체제 - 가상 메모리

두두·2023년 12월 5일
CSOS

Demand Paging

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

  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용

✅ 유효-무효 비트 사용

  • 무효(invalid)
    == 사용되지 않는 주소 영역인 경우
    == 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 페이지의 유효-무효 비트가 무효 값으로 초기화된다.
  • 특정 페이지가 참조되어 메모리에 적재되는 경우 해당 페이지의 유효-무효 비트가 유효 값으로 바뀐다.
  • CPU 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재라고 한다.



Page Fault

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

  • CPU가 무효 페이지에 접근하면 MMU가 trap을 발생한다. (page fault trap)
  • CPU의 제어권이 커널 모드로 전환되고, 페이지 부재 처리 루틴이 호출되면서 다음과 같은 순서로 페이지 부재를 처리한다.
  1. 해당 페이지에 대한 접근이 올바른가?
    사용되지 않는 주소 영역에 속한 페이지에 접근하려 했거나 해당 페이지에 대한 접근 권한 위반을 했을 경우 해당 프로세스를 종료한다.
  2. 물리적 메모리에 비어 있는 프레임을 할당 받는다.
    비어 있는 프레임이 없으면 기존에 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아낸다. (swap out)
  3. 해당 페이지를 디스크에서 메모리에 읽어온다.
    • 디스크 I/O가 끝나기까지 이 프로세스는 block 상태가 되어 CPU를 선점당한다.
      (현재까지 저장된 CPU 레지스터 상태 및 PC 값을 PCB에 저장해 둠.)
    • 디스크 읽기가 끝나면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정한다.
    • block 상태의 프로세스를 준비 큐로 이동시킨다.
  4. 이 프로세스가 CPU를 할당받으면 실행 상태로 바뀌면서 PCB에 저장해 두었던 값을 복원
  5. 중단되었던 명령부터 실행을 재개한다.



요구 페이징의 성능

페이지 부재의 발생 빈도가 성능에 가장 큰 영향을 미침.

유효 접근 시간(요청한 페이지를 참조하는 데 걸리는 시간)
(1 - P) x 메모리 접근 시간 + P x M

페이지 부재 발생 비율(P)

0 ≤ P ≤ 1

P = 0 : 페이지 부재가 한 번도 일어나지 않은 경우
P = 1 : 모든 참조 요청에서 페이지 부재가 발생한 경우

M : 각종 오버헤드

  • 페이지 부재 발생 처리 오버헤드

  • 메모리에 빈 프레임이 없는 경우 swap out 오버헤드

  • 요청된 페이지의 swap in 오버헤드

  • 프로세스의 재시작 오버헤드
    ➡️ 위 오버헤드의 총합




페이지 교체

페이지 부재가 발생하여 요청된 페이지를 디스크에서 메모리로 읽어오려고 하는데, 물리적 메모리에 빈 프레임이 없을 수 있다.
이때 이미 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는데,
어떠한 페이지를 교체할지 결정하는 것을 페이지 교체라고 한다.

아래부터 예시!


## 페이지 교체 알고리즘 페이지 교체를 할 때에 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 페이지 교체 알고리즘 이 알고리즘의 목표는 **페이지 부재율을 최소화**하는 것이다.

알고리즘 평가

주어진 페이지 참조열에 대해 부재율을 계산
페이지 참조열의 예시: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5


최적 페이지 교체 (Optimal Algorithm)

물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 알고리즘

  • 미래의 참조를 알아야 하므로 오프라인에서만 사용된다.
  • 다른 알고리즘의 성능에 대한 상한선(upper bound)을 제공한다.
  • 초기 4회는 물리적 메모리가 비어있으므로 불가피하게 페이지 부재가 발생한다.
  • 이후 1, 2는 물리적 메모리에 1, 2페이지가 있으므로 페이지 부재가 발생하지 않는다.
  • 페이지 5는 물리적 메모리에 없으므로 가장 먼 미래에 참조되는 페이지 4를 디스크로 쫓아낸다.
  • 위와 같은 방식을 반복한다.

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

물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 알고리즘

  • 메모리를 증가하였음에도 페이지 부재가 오히려 늘어나는 현상(FIFO의 이상 현상)이 발생할 수 있다.

LRU (Least Recently Used) 알고리즘

가장 오래 전에 참조가 이루어진 페이지를 쫓아내는 알고리즘

  • 초기 4회는 물리적 메모리가 비어있으므로 불가피하게 페이지 부재가 발생한다.
  • 이후 1, 2는 물리적 메모리에 1, 2페이지가 있으므로 페이지 부재가 발생하지 않는다.
  • 페이지 5는 물리적 메모리에 없으므로 가장 오래 전에 참조된 페이지 3을 디스크로 내쫓는다.
  • 위와 같은 방식을 반복한다.

LFU (Least Frequently Used) 알고리즘

페이지의 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘

  • 최저 참조 횟수인 페이지가 여러 개 있는 경우
    • LFU 알고리즘 자체에서는 여러 페이지 중 임의로 선정
    • 성능 향상을 위해 가장 오래 전에 참조된 페이지를 지우게 구현할 수 있음

장점

LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 페이지의 인기도를 좀 더 정확히 반영할 수 있다.

단점

참조 시점의 최근성을 반영하지 못한다.
LRU보다 구현이 복잡하다.


LRU vs LFU

구현 측면

  • LRU는 정렬된 LinkedList 방식으로 페이지를 교체할 때 가장 위에 있는 LRU 페이지를 교체하면 되고,
    특정 페이지가 참조되었을 때는 List의 맨 아래로 바로 보내면 되므로
    ✅ 구현이 간단
    ✅ 시간 복잡도가 O(1)
  • LFU는 페이지를 교체할 때는 가장 위에 있는 LFU 페이지를 교체하면 되지만,
    특정 페이지가 참조되었을 때는 자기 자신보다 아래에 있는 노드와 참조 횟수를 모두 비교해야 하므로
    ✅ 일반적인 List를 사용하면 시간 복잡도가 O(N)
    그래서 인접 노드 간의 참조 횟수를 빠르게 비교하기 위하여 Heap 자료 구조를 사용하며,
    ✅이것의 시간 복잡도는 O(log N)이 된다.



다양한 캐싱 환경

캐싱 기법

  • 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식
  • 페이징 시스템 외에도 캐시 메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용

캐시 운영의 시간 제약

  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 거리는 경우 실제 시스템에서 사용할 수 없음
  • 버퍼 캐싱이나 웹 캐싱의 경우 O(1)에서 O(log N)까지 허용한다.

페이징 시스템의 경우

  • 페이지 부재의 경우에만 OS가 관여
  • 페이지가 이미 메모리에 존재하는 경우 참조 시각 등의 정보를 OS가 알 수 없음
  • O(1)인 LRU의 List 조작조차 불가능



클럭 알고리즘 (Clock Algorithm)

개념 및 특징

  • LRU의 근사 알고리즘
  • Second chance algorithm/NUR(Not Used Recently), NRU (Not Recently Used) 등으로 불림
  • 참조 비트를 사용하여 교체 대상 페이지를 선정 (circular list)
  • 참조 비트를 수정하는 작업은 OS가 아닌, 하드웨어가 수행
  • 참조 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동

개선

  • 참조 비트와 수정 비트를 함께 사용
  • 참조 비트가 1이면 최근에 참조된 페이지이며, 수정 비트가 1이면 최근에 변경된 페이지를 뜻함

동작 과정

  • 각 사각형은 물리적 메모리에 있는 페이지 프레임을 뜻한다.
  • 페이지에 대해 어떤 페이지가 참조되어 CPU가 그 페이지를 사용하게 되면, 그 페이지에 참조 비트가 1로 세팅이 된다. (하드웨어가 하는 일)
  • OS는 포인터를 이동하면서 페이지의 참조 비트가 이미 1이면, 페이지를 쫓아내지 않고 참조 비트를 0으로 세팅한 후 다음 페이지의 참조 비트를 검사한다.
  • OS는 다시 포인터를 이동하다가 참조 비트가 0인 페이지를 찾으면, 해당 페이지를 쫓아낸다.
    • 참조 비트는 해당 페이지가 참조될 때 하드웨어가 1로 자동으로 세팅하므로 시계 바늘이 한 바퀴 돌아오는 동안에 다시 참조되지 않은 경우 그 페이지는 교체되는 것이다. 즉, A라는 페이지 프레임의 참조 비트를 0으로 바꾼 후, 다시 한 바퀴 돌아서 A 페이지 프레임의 참조 비트가 0이면 가장 오랫동안 참조가 일어나지 않은 페이지라고 판단하는 것이다.
  • 개선 클럭 알고리즘은 참조 비트 외에 수정 비트를 사용한다.
    • 수정 비트는 어떤 페이지가 쫓겨날 때, 이 페이지의 수정 비트가 0이면 backing store에서 물리적 메모리로 올라온 이후로 수정이 되지 않은 페이지이므로 바로 메모리에서 지워도 된다.
    • 하지만 수정 비트가 1이면 물리적 메모리로 올라온 이후로 상태의 수정이 일어난 페이지이므로 쫓겨나기 전에 backing store에 수정한 내용을 반영하고 메모리에서 지워야 한다.
    • 그래서 수정 비트가 1이면 디스크로 쫓겨나는 페이지의 수정된 내용을 반영하는 오버헤드가 발생하므로, 해당 페이지를 쫓아내지 않고 수정 비트를 0으로 바꾼다.



페이지 프레임의 할당

  • 각 프로세스에 얼마 만큼의 페이지 프레임을 할당할 것인가?

페이지 프레임 할당의 필요성

CPU에서 일반적으로 명령을 실행할 때는 여러 페이지를 동시에 참조하게 된다.
프로세스의 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하기 때문.

Loop를 구성하는 페이지들은 한꺼번에 프로세스에 할당되는 것이 유리하다.
최소한의 페이지 할당이 없으면 매 반복문마다 페이지 부재가 발생한다.

페이지 프레임 할당 알고리즘

  • 균등 할당(Equal Allocation):
    모든 프로세스에게 페이지 프레임을 균일하게 할당
  • 비례 할당(Proportional Allocation):
    프로세스의 크기에 따라 페이지 프레임을 비례하여 할당
  • 우선순위 할당(Priority Allocation):
    프로세스의 우선순위에 따라 페이지 프레임을 할당
    • 당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분 클럭 알고리즘 (Clock Algorithm)
      개념 및 특징
      LRU의 근사 알고리즘이다.
      Second chance algorithm, NUR(Not Used Recently), NRU (Not Recently Used) 등으로 불린다.
      참조 비트를 사용하여 교체 대상 페이지를 선정한다. (circular list)
      참조 비트를 수정하는 작업은 OS가 아닌, 하드웨어가 수행한다.
      참조 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.

개선
참조 비트와 수정 비트를 함께 사용한다.
참조 비트가 1이면 최근에 참조된 페이지이며, 수정 비트가 1이면 최근에 변경된 페이지를 뜻한다.

동작 과정
Untitled
각 사각형은 물리적 메모리에 있는 페이지 프레임을 뜻한다.
페이지에 대해 어떤 페이지가 참조되어 CPU가 그 페이지를 사용하게 되면, 그 페이지에 참조 비트가 1로 세팅이 된다. (하드웨어가 하는 일)
OS는 포인터를 이동하면서 페이지의 참조 비트가 이미 1이면, 페이지를 쫓아내지 않고 참조 비트를 0으로 세팅한 후 다음 페이지의 참조 비트를 검사한다.
OS는 다시 포인터를 이동하다가 참조 비트가 0인 페이지를 찾으면, 해당 페이지를 쫓아낸다.
참조 비트는 해당 페이지가 참조될 때 하드웨어가 1로 자동으로 세팅하므로 시계 바늘이 한 바퀴 돌아오는 동안에 다시 참조되지 않은 경우 그 페이지는 교체되는 것이다. 즉, A라는 페이지 프레임의 참조 비트를 0으로 바꾼 후, 다시 한 바퀴 돌아서 A 페이지 프레임의 참조 비트가 0이면 가장 오랫동안 참조가 일어나지 않은 페이지라고 판단하는 것이다.
개선 클럭 알고리즘은 참조 비트 외에 수정 비트를 사용한다.
수정 비트는 어떤 페이지가 쫓겨날 때, 이 페이지의 수정 비트가 0이면 backing store에서 물리적 메모리로 올라온 이후로 수정이 되지 않은 페이지이므로 바로 메모리에서 지워도 된다.
하지만 수정 비트가 1이면 물리적 메모리로 올라온 이후로 상태의 수정이 일어난 페이지이므로 쫓겨나기 전에 backing store에 수정한 내용을 반영하고 메모리에서 지워야 한다.
그래서 수정 비트가 1이면 디스크로 쫓겨나는 페이지의 수정된 내용을 반영하는 오버헤드가 발생하므로, 해당 페이지를 쫓아내지 않고 수정 비트를 0으로 바꾼다.

페이지 프레임의 할당
각 프로세스에 얼마 만큼의 페이지 프레임을 할당할 것인가?
페이지 프레임 할당의 필요성
CPU에서 일반적으로 명령을 실행할 때는 여러 페이지를 동시에 참조하게 된다.
프로세스의 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하기 때문.
Loop를 구성하는 페이지들은 한꺼번에 프로세스에 할당되는 것이 유리하다.
최소한의 페이지 할당이 없으면 매 반복문마다 페이지 부재가 발생한다.
페이지 프레임 할당 알고리즘
균등 할당(Equal Allocation): 모든 프로세스에게 페이지 프레임을 균일하게 할당
비례 할당(Proportional Allocation): 프로세스의 크기에 따라 페이지 프레임을 비례하여 할당
우선순위 할당(Priority Allocation): 프로세스의 우선순위에 따라 페이지 프레임을 할당
당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분

전역 교체와 지역 교체
전역 교체
모든 페이지 프레임이 교체 대상이 될 수 있는 방법이다.
전체 메모리를 각 프로세스가 공유해서 사용하고, 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.
페이지 교체 시 다른 프로세스의 프레임을 빼앗아 올 수 있으므로 프로세스별 프레임 할당량을 조절할 수 있게 된다.
FIFO, LRU, LFU 등의 알고리즘을 전역 교체로 사용할 수 있다.
Working set, PFF 알고리즘을 전역 교체로 사용할 수 있다.

지역 교체
자신에게 할당된 페이지 프레임 내에서만 교체한다.
FIFO, LRU, LFU 등의 알고리즘을 지역 교체로 사용할 수 있다.

스레싱
프로세스의 원활한 수행에 필요한 최소한 페이지 프레임 수를 할당 받지 못하면 페이지 부재율이 크게 상승하여 CPU 이용률이 떨어지는데, 이를 스레싱이라고 한다.
low throughput
스레싱이 발생하는 시나리오
OS는 CPU 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적다고 판단하여 메모리에 올라가는 프로세스를 늘린다. (CPU 이용률이 낮으면 MPD를 높인다.)
준비 큐에 프로세스가 단 하나라도 있으면 CPU는 그 프로세스를 실행하므로 쉬지 않고 일하게 되는데, CPU 이용률이 낮다는 것은 준비 큐가 비어있다는 것을 뜻한다.
메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도(MPD)라고 부른다.
MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소한다.
각 프로세스는 그들이 원활하게 수행되기 위해 필요한 최소한의 페이지 프레임도 할당 받지 못하므로 페이지 부재율이 급격히 증가한다.
페이지 부재가 발생하면 I/O 작업을 수반하므로 다른 프로세스에게 CPU가 넘어간다.
다른 프로세스 역시 페이지 부재가 발생하고 있어서 또 다른 프로세스에게 CPU가 넘어간다.
결국 준비 큐에 있는 모든 프로세스에게 CPU가 한 차례씩 할당 되었는데도 모든 프로세스가 다 페이지 부재를 발생하여 CPU의 이용률이 급격하게 떨어진다.
OS는 위 현상이 메모리에 MPD가 낮다고 판단하여 MPD를 높이려고 한다.
위 악순환이 계속 반복되는 상황을 스레싱이라고 부른다.



전역 교체 vs 지역 교체

전역 교체

모든 페이지 프레임이 교체 대상이 될 수 있는 방법이다.

  • 전체 메모리를 각 프로세스가 공유해서 사용하고, 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.
  • 페이지 교체 시 다른 프로세스의 프레임을 빼앗아 올 수 있으므로 프로세스별 프레임 할당량을 조절할 수 있게 된다.
  • FIFO, LRU, LFU 등의 알고리즘을 전역 교체로 사용할 수 있다.
  • Working set, PFF 알고리즘을 전역 교체로 사용할 수 있다.

지역 교체

자신에게 할당된 페이지 프레임 내에서만 교체한다.

  • FIFO, LRU, LFU 등의 알고리즘을 지역 교체로 사용할 수 있다.

스레싱

프로세스의 원활한 수행에 필요한 최소한 페이지 프레임 수를 할당 받지 못하면 페이지 부재율이 크게 상승하여 CPU 이용률이 떨어지는데, 이를 스레싱이라고 한다.

  • low throughput

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

  • OS는 CPU 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적다고 판단하여 메모리에 올라가는 프로세스를 늘린다. (CPU 이용률이 낮으면 MPD를 높인다.)
  • 준비 큐에 프로세스가 단 하나라도 있으면 CPU는 그 프로세스를 실행하므로 쉬지 않고 일하게 되는데, CPU 이용률이 낮다는 것은 준비 큐가 비어있다는 것을 뜻한다.
  • 메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도(MPD)라고 부른다.
  • MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소한다.
  • 각 프로세스는 그들이 원활하게 수행되기 위해 필요한 최소한의 페이지 프레임도 할당 받지 못하므로 페이지 부재율이 급격히 증가한다.
  • 페이지 부재가 발생하면 I/O 작업을 수반하므로 다른 프로세스에게 CPU가 넘어간다.
  • 다른 프로세스 역시 페이지 부재가 발생하고 있어서 또 다른 프로세스에게 CPU가 넘어간다.
  • 결국 준비 큐에 있는 모든 프로세스에게 CPU가 한 차례씩 할당 되었는데도 모든 프로세스가 다 페이지 부재를 발생하여 CPU의 이용률이 급격하게 떨어진다.
    OS는 위 현상이 메모리에 MPD가 낮다고 판단하여 MPD를 높이려고 한다.
    위 악순환이 계속 반복되는 상황을 스레싱이라고 부른다.
profile
두두
멋쟁이가 될테야
이전 포스트

[CS] 운영체제 - 메모리 관리

다음 포스트

[CS] 데이터베이스 - 릴레이션 정규화

0개의 댓글