OS - Virtual Memory

본 글은 (KOCW) 운영체제, 이화여자대학교 반효경 교수님의 강의를 듣고 내용을 요약 및 정리했습니다.
스터디를 진행하는 것에 목적이 있으며, 자세한 사항은 여기를 참고하시면 됩니다.

---

요구 페이징 (Demand Paging)

• 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• 유효-무효 비트 사용
  • 무효(Invalid)의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 페이지의 유효-무효 비트가 무효 값으로 초기화 된다
    • 특정 페이지가 참조되어 메모리에 적재되는 경우 해당 페이지의 유효-무효 비트가 유효 값으로 바뀐다
  • CPU 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재라고 한다

 

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

 

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

1. 페이지 테이블 참조
2. Invalid 상태이면 Trap을 발생시킴
3. CPU의 제어권이 OS에 넘어가며 Backing store에 있는 페이지로 찾아감
4. 물리적인 메모리에 올림 / 빈 프레임이 없으면 쫓아내고 올림
5. 프레임 번호를 페이지 테이블에 업데이트

---

요구 페이징의 성능

• 페이지 부재의 발생 빈도가 성능에 가장 큰 영향을 미친다
• 유효 접근 시간(요청한 페이지를 참조하는 데 걸리는 시간)
  • (1-P) x 메모리 접근 시간 + P x M
  • 페이지 부재 발생 비율(P) -> 0<=P<=1
    • P = 0 페이지 부재가 한 번도 일어나지 않는 경우
    • P = 1 모든 참조 요청에서 페이지 부재가 발생한 경우
  • M (각종 오버헤드)
    • 페이지 부재 발생 처리 오버헤드
    • 메모리에 빈 프레임이 없는 경우 swap out 오버헤드
    • 요청된 페이지의 swap in 오버헤드
    • 프로세스의 재시작 오버헤드
    • 위 오버헤드의 총합을 뜻함

---

페이지 교체

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

 

페이지 교체 알고리즘

• 페이지 교체를 할 때에 어떠한 프레임에 있는 페이지를 쫓아낼 것인지를 결정하는 알고리즘을 페이지 교체 알고리즘
  • 페이지 부재율을 최소하 하는 것이 목적
  • 알고리즘의 평가
    • 주어진 페이지 참조열에 대해 부재율 계산
    • e.g 페이지 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

최적 페이지 교체 (Optimal Algorithm)

• 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 알고리즘
• 미래의 참조를 알아야 하므로 오프라인에서만 사용
• 다른 알고리즘의 성능에 대한 상한선(upper bound)을 제공한다

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

선입 선출 알고리즘

• 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 알고리즘
• 메모리를 증가하였음에도 페이지 부재가 오히려 늘어나는 현상(FIFO의 이상현상)이 발생할 수 있다

• 메모리 프레임을 늘렸음에도 페이지 부재가 늘어난 현상의 예

LRU(Least Recently Used) 알고리즘

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

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

LFU(Least Frequently Used) 알고리즘

• 페이지의 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘
• 최저 참조 횟수인 페이지가 여러 개 있는 경우
  • LFU 알고리즘 자체에서는 여러 페이지 중 임의로 선정
  • 성능 향상을 위해 가장 오래전에 참조된 페이지를 지우게 구현할 수 있음
• 장점
  • LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 페이지의 인기도를 좀 더 정확히 반영할 수 있음
• 단점
  • 참조 시점의 최근성을 반영하지 못함
  • LRU보다 구현이 복잡

LRU vs LFU

• 미래를 참조할 수 없기 때문에 미래에 계속 참조될 페이지인지 선택하기가 어려움

LRU와 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 조작조차 불가능하다

페이징 시스템에서 LRU, LFU가 가능한가?

• 프로세스 A가 CPU를 잡고 실행 중인 상태
  • 프로세스 A의 논리적 메모리에서 매 순간 명령어를 읽어와서 수행할 것
  • 이때 논리적 주소를 페이지 테이블을 통해서 물리적 주소로 변환하여 물리적 메모리에 있는 내용을 CPU로 읽어와야 한다
    • 만약, 주소 변환을 했는데 해당하는 페이지가 이미 물리적 메모리에 올라와 있다면 물리적 메모리를 그대로 읽으면 됨
    • 이러한 주소 변환과정은 모두 하드웨어가 담당하며 OS는 관여하지 않는다
• 만약, 변환하려는 논리적 메모리의 유효-무효 비트의 값이 invalid여서 페이지 부재가 발생했다면 디스크 접근을 필요로 함
  • 이때 I/O를 수행해야 하므로 trap이 발생하여 CPU의 제어권이 프로세스 A에서 OS로 넘어가게 된다
• OS가 디스크의 페이지 부재가 발생한 페이지를 물리적 메모리로 올리고, 그 과정에서 물리적 메모리의 페이지 하나를 쫓아내야 한다
  • 물리적 메모리의 빈 프레임이 있다면 바로 그 자리에 페이지를 올림
• 위의 일련의 과정을 수행하면서 LRU, LFU 알고리즘을 적용할 수 있을까?
  • 프로세스가 요청한 페이지가 메모리에 이미 올라와 있는 경우에는 CPU가 OS로 넘어가지 않는다
  • 페이지 부재가 발생하여 CPU 제어권이 OS로 넘어가므로 디스크에서 메모리로 페이지가 넘어오는 시간을 파악할 수 있음
  • 페이지 부재가 발생할 때만 페이지에 접근하는 정보를 알 수 있으므로 LRU, LFU 알고리즘은 페이징 시스템에서 사용할 수 없다(버퍼 캐싱, 웹 캐싱은 가능)

---

클럭 알고리즘

 

페이지 교체 알고리즘에서 사용되는

 

개념 및 특징

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

개선

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

동작 과정

• 각 사각형은 물리적 메모리에 있는 페이지 프레임을 뜻함
• 페이지에 대해 어떤 페이지가 참조되어 CPU가 그 페이지를 사용하게 되면, 그 페이지에 참조 비트가 1로 세팅이 됨(하드웨어가 함)
• OS는 포인터를 이동하면서 페이지의 참조 비트가 이미 1이면, 페이지를 쫓아내지 않고 참조 비트를 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를 높이려고 한다
  • 위 악순환이 계속 반복되는 상황을 스레싱이라고 부름

워킹셋(Working-Set) 알고리즘



워킹셋 모델(Working-Set Model)

• 참조의 지역성
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조
  • 집중적으로 참조되는 해당 페이지의 집합을 지역 셋(locality set)이라고 한다
• 워킹셋 모델
  • 지역성에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지의 집합을 워킹셋이라고 정의
  • 워킹셋 모델에서는 프로세스의 워킹셋 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 페이지 프레임을 반납한 후 swap out한다 해당 프로세스는 suspend 상태가 됨
    • 만약 워킹셋이 5개인데, 페이지 프레임을 공간에 3개 밖에 없다면, 해당 프로세스는 모든 페이지 프레임을 반납하고 디스크로 쫒겨남
  • MPD를 조절하여 스레싱을 방지

워킹셋 알고리즘

• 워킹셋의 결정
  • 워킹셋 윈도우를 통해 알아낸다.
  • 윈도우 사이즈가 Δ인 경우
    • 시각 Ti에서의 워킹셋 WS(Ti)
      • Time interval [Ti - Δ, Ti] 사이에 참조된 서로 다른 페이지들의 집합
    • 워킹셋에 속한 페이지는 메모리에 유지하고, 속하지 않은 것은 메모리에서 쫓아낸다. 즉, 참조된 후 Δ 시간동안 해당 페이지를 메모리에 유지한 후 쫓아 냄.
• 알고리즘 동작 과정
  • 프로세스의 워킹셋 사이즈의 합이 페이지의 프레임 수보다 큰 경우
    • 일부 프로세스를 swap out 한 뒤, 남은 프로세스의 워킹셋을 우선적으로 충족하여 MPD를 줄인다.
  • 워킹셋을 다 할당하고도 페이지 프레임이 남는 경우
    • swap out 되었던 프로세스에게 워킹셋을 할당하여 MPD를 높인다.
• 윈도우 사이즈 Δ
  • 워킹셋을 제대로 탐지하기 위해서는 윈도우 사이즈를 잘 결정해야 한다.
  • Δ 값이 너무 작으면 지역셋을 모두 수용하지 못할 수 있다.
  • Δ 값이 너무 크면 여러 규모의 지역셋을 수용할 수 있다.
  • Δ 값이 무한대이면 전체 프로그램을 구성하는 페이지를 워킹셋으로 간주한다.

워킹셋 알고리즘 예제

• Δ는 10인 상태라고 가정한다.
• t1일 때 프로세스의 워킹셋은 5개의 페이지로 구성되는 반면, t2일 때 프로세스의 워킹셋은 2개의 페이지로 구성된다.
• 이처럼 프로세스가 메모리를 많이 필요로 할 때에는 많이 할당하고, 적게 필요로 할 때에는 적게 할당하는 동적인 프레임 할당 기능을 수행한다.

PFF(Page-Fault Frequency) 알고리즘

• 페이지 부재 빈도 알고리즘은 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.
• 페이지 부재율의 상한 값과 하한값을 둔다.
  • 페이지 부재율의 상한 값을 넘으면 페이지 프레임을 더 할당한다.
  • 페이지 부재율의 하한값보다 낮으면 할당 페이지 프레임 수를 줄인다.
• 빈 페이지 프레임이 없으면 일부 프로세스를 swap out 한다.

 

페이지 사이즈의 결정

• 페이지 사이즈를 감소하면 어떻게 될까?
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • 내부 단편화 감소
  • Disk transfer의 효율성 감소
    • 한 번의 디스크 헤더 움직임으로 많은 양의 내용을 읽어오는 것이 좋은데, 페이지 사이즈가 적으면 그렇지 못한다.
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • 지역성의 활용 측면에서는 좋지 않음
• 최근에는 페이지 사이즈를 크게 가져 감

 

가상 메모리를 사용하는 이유?

• 메모리에 확장성을 부여한다.
  • 물리 메모리는 한정적이지만, 가상 메모리는 큰 공간으로 구성이 가능하다.
  • 가상 메모리를 사용하면 실제 메인 메모리 장치가 아닌, 디스크를 부가적인 메모리 공간으로 활용할 수 있다.
• 모든 프로그램에 동일한 메모리 공간을 제공해 줄 수 있다.
  • 개발자 입장에서 물리적 메모리가 아닌 OS가 제공하는 메모리 공간만 신경 쓰면 된다.
  • 운영 체제가 동작하는 환경에서는 여러 가지 프로그램이 동시에 실행되므로 메모리 공간에 대한 관리가 필요하다.
• 메모리 할당과 관리에 효율적이다.
  • 물리적으로 연속되지 않은 메모리라도 가상으로 연속적인 메모리 공간으로 사용이 가능하다.
• 메모리 보호 기능을 제공한다.
  • 보안이나 안정성 측면에서 매우 중요한 기능이다.
  • 각각의 프로세스는 별도의 메모리 공간을 점유하며, 다른 프로세스의 메모리 공간을 참조할 수 없다

가상 메모리의 중요성

• 가상 메모리는 메모리 사용량이 늘어남에 따라, 디스크의 일부를 마치 확장된 RAM처럼 사용할 수 있게 해 주는 기술이다.
• 커널은 실제 메모리에 올라와 있는 메모리 블록 중 당장 쓰이지 않는 것을 디스크에 저장하는데, 이를 통해 사용 가능한 메모리의 영역을 훨씬 늘릴 수 있게 된다. 디스크에 저장되어 있던 메모리 블록은 다시 필요하면 실제 메모리로 올려지며, 대신 다른 블록이 디스크로 내려가게 된다.
• 이러한 과정은 사용자에게 전혀 보이지 않고, 프로그램에게도 그저 많은 양의 메모리가 있는 것처럼 보일 뿐이어서 점유하고 있던 메모리가 디스크에 있는지 실제 메모리에 있는지 전혀 신경 쓸 필요가 없게 된다.
• 그러나, 하드 디스크를 읽고 쓰는 시간은 RAM보다 훨씬 느리기 때문에 프로그램의 실행은 그만큼 느려진다.
• 이때 가상 메모리로 쓰이는 하드 디스크의 영역을 스왑 영역(백킹스토어)라고 부른다.
• 메모리 스와핑은 두 가지 측면에서 중요하다.
  • 시스템에서 특정 애플리케이션이나 프로세스가 현재 가용한 물리 메모리보다 많은 양의 메모리를 요청할 수 있다. 이때 커널은 적은 빈도로 사용되는 메모리 페이지를 스왑 아웃해서 가용 메모리 공간을 확보한 뒤 이를 해당 프로세스에게 할당해 줌으로써 프로세스 실행이 가능하게 한다.
  • 애플리케이션이 실행되기 시작할 때 초기화를 위해서만 필요하고 이후에는 사용되지 않는 메모리 페이지들은 시스템에 의해 스왑 아웃된다. 이로 인해 가용 가능한 메모리 공간은 다른 애플리케이션이나 디스크 캐시 용도로 활용된다

---

• 가상 메모리란?
  • 가상 메모리가 가능한 이유?
    • 논리적 주소를 물리적 주소로 변환하고 필요한 페이지만 메모리에 올려 사용하면, 프로세스 전체가 메모리에 올라간 것처럼 사용할 수 있다
  • Page Fault가 발생했을 때 어떻게 처리하는지
    • Page Fault가 발생하면 우선 메모리 프레임에 빈 공간이 있는지 확인한 후 빈 공간이 존재한다면 backing store에서 메모리에 페이지를 올린다. 만약 프레임에 빈 공간이 없다면 프로세스를 swap out 하여 빈 공간을 만들며 페이지 교체 알고리즘을 통해 어떤 프로세스의 페이지를 swap out 할 것인지 선택하며 빈 공간에 필요한 페이지를 올린다
• 페이지 교체 알고리즘
  • LRU 알고리즘은 어떤 특성을 이용한 알고리즘?
    • 가장 마지막에 참조한 페이지를 swap out 하는 알고리즘
  • LRU 알고리즘을 구현한다면 어떻게?
    • LinkedList의 형태로 참조된 페이지를 맨 앞에 이어 넣으면서 맨 뒤의 페이지를 swap out 하면 O(1)에 해결할 수 있다
• Thrashing이란?
  • 프로세스의 원활한 수행에 필요한 최소한 페이지 프레임 수를 할당받지 못하면 페이지 부재율이 크게 상승하여 CPU 이용률이 떨어지는데, 이를 Thrashing이라고 한다
  • Thrashing 발생 시, 어떻게 완화할 수 있을까?
    • 지역성에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지의 집합 즉 워킹셋을 정의하고 워킹셋보다 적은 페이지만 올릴 수 있다면 해당 프로세스의 모든 페이지를 swap out 시켜버린다