요구 페이징, 페이지 교체

요구 페이징이란?

프로그램 실행 시작 시 프로그램 전체를 물리 메모리에 적재하는 대신, 초기에 필요한 페이지만 메모리에 적재하는 방식.

 

특정 페이지에 대해 cpu의 요청이 들어온 후 해당 페이지를 메모리에 적재.

당장 실행에 필요한 페이지만을 메모리에 적재하기 때문에 메모리 사용량이 감소

프로세스 전체를 메모리에 적재하는 입출력 오버헤드도 감소

 

요구 페이징 기법에서는 유효/무효 비트 (valid/ invalid bit)를 두어 각 페이지가 메모리에 존재하는지 표시

 

valid : 페이지가 메모리에 있는 상태
invalid : 페이지가 스왑 공간에 있는 상태

---

페이지 폴트 과정 & 스와핑 과정

아래 글 참고

https://leah-only.tistory.com/8

메모리 관리 - 가상 메모리(Virtual Memory)

 

---

페이지 교체 알고리즘

페이지 교체가 언제 발생하는가?

초기에 필요한 페이지들만 메인 메모리에 적재되어 있고 프로세스 동작 중 페이지 폴트가 발생하면 원하는 페이지를 하드디스크의 swap device에서 가져온다. 

하지만 메인 메모리가 모두 사용중이라 원하는 페이지를 메인 메모리에 적재하지 못한다면 페이지 교체가 발생

 

페이지 폴트가 발생해 요청된 페이지를 디스크에서 메모리로 가져올 때 메인 메모리 공간이 부족한 경우 메모리에 올라와 있는 페이지를 디스크로 옮겨서 메모리 공간을 확보 (스와핑)

---

FIFO (First In First Out)

• 메모리에 들어온 페이지 중 가장 오래된 페이지를 교체
• 간단하고 초기화 코드에 적절한 방법
• 페이지가 올라온 순서를 큐(Queue) 로 관리 

OPT (Optimal Page Replacement) - 최적 페이지 교체

• 앞으로 가장 오랫동안 사용되지 않을 페이지 교체 
• 프로세스가 앞으로 사용할 페이지를 미리 알아야해서 구현 불가능
• 연구, 테스트 목적으로 주로 사용

LFU (Last Frequently Used)

• 가장 참조 횟수가 작은 (사용 빈도가 적은) 페이지 교체

MFU (Most Frequently Used)

• 가장 참조 횟수가 많은 (사용 빈도가 많은) 페이지 교체 

LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지 교체
• OPT 알고리즘 방식과 비슷한 효과를 낼 수 있는 방법
• OPT 알고리즘보다 페이지 교체 횟수가 높지만 FIFO보다 효율적
• 페이지 정보를 Stack으로 관리 (최근 사용한 페이지를 스택의 top으로 이동)

NUR (Not Used Recently)

• LRU와 유사한 알고리즘으로, 각 페이지가 최근에 참조되었는지 여부를 활용
• 일명 clock 알고리즘이라고 하며 0과 1을 가진 비트를 둔다 (1 : 최근 참조 / 0 : 참조 X)
  • 시계방향으로 돌면서 0을 찾고 0을 찾은 순간 해당 페이지가 교체 대상이 됨

---

메모리가 고갈되면 일어나는 현상

• 메모리가 고갈되었지만, 프로세스를 실행해야 하기 때문에 Swap이 활발해진다
• CPU 이용률이 하락하면 OS는 CPU 이용률이 낮으므로 오히려 프로세스를 추가하게 되는 현상
• 이를 해소하지 못하면 Out Of Memory 상태로 판단해 중요도가 낮은 프로세스를 강제 종료시킨다. 

→ 이 현상을 쓰레싱(Thrashing) 이라고 한다. 

---

CS 로드맵 참조 : https://github.com/devSquad-study/2023-CS-Study