요구 페이징

요구 페이징은 시스템 메모리를 보다 효율적, 응답 속도 향상을 높이기 위해 컴퓨터 운영 체제에서 사용되는 방법이다. 전체 프로세스를 한 번에 메모리에 로드하는 대신 요구 페이징은 프로세스에서 필요할 때(또는 "요구할 때") 페이지(메모리 블록)만 로드한다.

페이지 테이블 엔트리 구조

페이지 테이블은 가상 메모리를 관리하기 위해 컴퓨터 운영 체제에서 사용되는 데이터 구조이다. 가상 주소와 물리적 주소 간의 매핑을 저장한다. 가상 주소는 실행 중인 프로그램에서 사용하는 반면 물리적 주소는 실제 하드웨어 메모리를 나타낸다.

아래 그림은 페이지 테이블의 한 행을 의미하는 페이지 테이블(PTE)의 구성을 나타낸다.

• 프레임 번호: 가상 주소의 해당 페이지가 어느 프레임에 있는지 알려주는 자료구조이다.
  • 주소 필드(address field) 라고도 한다.
• 플래그 피트:
  • 접근 비트(access bit): 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려준다. 해당 메모리에 읽거나 실행 작업을 했다면 접근 비트가 1이 된다.
    • 참조 비트(reference bit) 라고도 한다.
  • 변경 비트(modified bit): 변경 비트는 페이지가 메모리에 올라온 후 데이터 변경이 있었는지 알려준다. 해당 메모리에 쓰기나 추가 작업을 했다면 변경 비트가 1이 된다.
    • 더티 비트(dirty bit) 라고도 한다.
  • 유효 비트(valid bit): 유효 비트는 페이지가 실제 메모리에 있는지를 나타낸다.
    • 현재 비트(present bit) 라고도 한다.
  • 읽기 비트(read bit), 쓰기 비트(write bit), 실행 비트(execute bit): 읽기 비트, 쓰기 비트, 실행 비트는 페이지에 대한 읽기 권한 쓰기 권한 실행 권한을 나타낸다. 읽기 권한이 없는 프로세스가 읽으려고 하거나 쓰기 권한이 없는 프로세스가 쓰려고 할 때 접근을 차단하는데 사용된다.
    • 접근 권한 비트(rights bit) 라고도 한다.

페이지 폴트(page fault)

페이지 폴트(page fault) 는 프로그램이 현재 물리 메모리에 없는 페이지에 액세스하려고 할 때 컴퓨터 시스템에서 발생하는 인터럽트 또는 예외이다. 그런 다음 운영 체제는 필요한 페이지를 보조 저장소(일반적으로 디스크)에서 물리 메모리로 로드하고, 프로그램은 실행을 계속할 수 있다. 페이지가 전혀 존재하지 않으면 운영 체제는 일반적으로 오류와 함께 프로그램을 종료한다.

페이지 교체 알고리즘

페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘이다.

페이지 교체 알고리즘은 다음과 같이 다양한 종류가 있다:

1. 랜덤 페이지 교체 알고리즘: 이 알고리즘은 메모리에서 무작위로 페이지를 선택하여 교체한다. 특별한 규칙 없이 수행되기 때문에 구현은 간단하지만 성능은 일반적으로 최상이 아니다.

2. FIFO (First In First Out) 알고리즘: 이 알고리즘은 가장 오래된 페이지부터 교체한다. 페이지는 큐에 저장되고, 가장 먼저 들어온 페이지가 가장 먼저 교체된다.
   

3. 최적 페이지 교체 알고리즘: 이 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이 알고리즘은 가장 낮은 페이지 결함률을 제공하지만, 미래의 페이지 요청을 알아야 하므로 실제 시스템에서는 구현이 불가능하다.
   

4. LRU (Least Recently Used) 알고리즘: 이 알고리즘은 가장 최근에 사용되지 않은 페이지부터 교체한다. LRU 페이지 교체 알고리즘은 페이지 접근 시간에 기반한 구현, 카운터에 기반한 구현, 참조 비트 시프트 방식으로 구현할 수 있으며 접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다는 단점이 있다.
   
   

5. LFU (Least Frequently Used) 알고리즘: 이 알고리즘은 가장 적게 사용된 페이지부터 교체한다. 각 페이지의 참조 횟수를 추적하고, 가장 적게 참조된 페이지를 교체한다. LFU 알고리즘도 LRU 알고리즘과 동일하게 낭비되는 메모리 공간이 많다는 단점이 있다.
   

6. NUR (Not Used Recently) 페이지 교체 알고리즘: 이 알고리즘은 최근에 사용되지 않은 페이지를 선택하여 교체하는 방법이다. 이 알고리즘은 두 가지 비트, 즉 참조 비트(Reference bit)와 변경 비트(Modified bit)를 사용하여 작동한다.

• 참조 비트: 페이지가 최근에 참조되었는지 여부를 나타낸다. 페이지가 참조되면 이 비트는 1로 설정되며, 그렇지 않으면 0으로 유지된다. 일정 시간 간격으로 이 비트는 0으로 재설정됩니다.

• 변경 비트: 페이지가 수정되었는지 (즉, 쓰기 작업이 수행되었는지) 여부를 나타낸다. 페이지가 수정되면 이 비트는 1로 설정되며, 그렇지 않으면 0으로 유지된다.

NUR 알고리즘은 이 두 비트를 이용하여 교체할 페이지를 선택한다. 알고리즘이 이 두 비트를 검사하고 다음 순서대로 페이지를 교체한다:

1. 참조 비트와 변경 비트 모두 0인 페이지 (즉, 최근에 참조되지도, 수정되지도 않은 페이지)
2. 참조 비트는 0이지만 변경 비트는 1인 페이지 (즉, 최근에 참조되지 않았지만, 수정된 페이지)
3. 참조 비트는 1이지만 변경 비트는 0인 페이지 (즉, 최근에 참조되었지만, 수정되지 않은 페이지)
4. 참조 비트와 변경 비트 모두 1인 페이지 (즉, 최근에 참조되고 수정된 페이지)
   

이 방식으로, NUR 알고리즘은 최근에 사용되지 않은 페이지를 우선적으로 교체하며, 동일한 조건의 페이지가 여러 개 있는 경우에는 수정되지 않은 페이지를 먼저 교체하려고 한다.

7. FIFO (First In First Out) 변형 알고리즘: FIFO 변형 알고리은 페이지 교체 알고리즘의 단점을 개선하기 위해 개발된 알고리즘이다. 대표적으로 두 가지 변형 알고리즘이 있다:

8. 2차 기회 페이지 교체 알고리즘 (Second Chance Page Replacement Algorithm): 이 알고리즘은 FIFO 알고리즘에 참조 비트를 추가한 변형이다. 페이지가 메모리에 처음 로드되면 참조 비트는 0으로 설정된다. 페이지가 참조되면 참조 비트는 1로 설정된다. 페이지를 교체해야 할 때, 알고리즘은 FIFO 순서로 페이지를 확인하지만, 참조 비트가 1로 설정된 페이지는 교체하지 않고, 대신 참조 비트를 0으로 재설정하고 페이지를 큐의 뒤로 이동시킨다. 참조 비트가 0인 페이지를 찾을 때까지 이 과정을 반복한다.
   

9. 시계 알고리즘 (Clock Algorithm): 이 알고리즘은 2차 기회 알고리즘의 변형으로, 큐 대신 시계 형태(원형 큐)의 자료구조를 사용하여 페이지를 관리한다. 페이지가 메모리에 로드되면 참조 비트는 0으로 설정되며, 페이지가 참조될 때마다 참조 비트는 1로 설정된다. 페이지 교체가 필요하면, 알고리즘은 "시계 바늘(포인터)"가 가리키는 페이지부터 확인을 시작한다. 만약 참조 비트가 1인 페이지를 만나면, 참조 비트를 0으로 재설정하고 "시계 바늘"을 다음 페이지로 이동시킨다. 참조 비트가 0인 페이지를 만나면 그 페이지를 교체한다. 이 알고리즘은 두 번째 기회 알고리즘보다 페이지 교체를 더 효율적으로 수행할 수 있다.
   
   

스레싱과 프레임 할당

스레싱(threshing): 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재(페이지 폴트)로 작업이 멈춘 것 같은 상태를 말한다.

프로그램의 수가 적을 때는 CPU 사용률이 계속 증가하다가 메모리가 꽉 차면 CPU가 작업하는 시간보다 스왑영역으로 페이지를 보내고 새로운 페이지를 메모리로 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 된다. 이러한 시점을 스레싱 발생 시점(threshing point)이라고 한다.

동시에 실행하는 프로그램의 수를 멀티프로그래밍 정도(degree of multiprogramming)이라고 한다.

물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦쳐진다. 하지만 물리메모리가 작업하는 데 충분한 크기가 되면 그 이후에는 물리 메모리 크기를 늘려도 작업 속도에 영향을 미치지 않는다.

스레싱과 프레임 할당

실행 중인 여러 프로세스에 프레임을 얼마나 나누어 주느냐에 따라 시스템의 성능이 달라진다.

1. 정적 할당(static allocation): 프로세스 실행 초기에 프레임을 나누어 준 후 그 크기를 고정
   • 균등 할당(equal allocation): 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당
     • 균등 할당 방식에서는 크기가 큰 프로세스의 경우 필요한 만큼 프레임을 할당 받지 못하기 때문에 페이지 부재(페이지 폴트)가 빈번하게 발생하고, 크기가 작은 프로세스의 경우 메모리가 낭비된다.

• 비례 할당(proportional allocation): 프로세스의 크기에 비례하여 프레임을 할당하는 방식
  - 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못한다.
  - 사용하지 않을 메모리를 처음부터 미리 확보하여 공간을 낭비한다.
  

정적 할당 방식은 프로세스를 실행하는 초기에 프레임을 할당하기 때문에 프로세스를 실행하는 동안 메모리 요구를 반영하지 못한다는 단점이 있다.

2. 동적 할당(dynamic allocation): 시시각각 변하는 요청을 수용하는 방식
   • 작업집합 모델(working set model): 지역성 이론을 바탕으로 하며, 가장 최근에 접근한 프레임이 이후에도 참조될 가능성이 높다는 가정에서 출발한다. 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고, 이 집합에 있는 페이지들을 물리 메모리에 유지하여 프로세스의 실행을 돕는다.
     • 작업집합 크기(working set size): 작업집합 모델에서 물리 메모리에 유지할 페이지의 크기, 잡업집합에 들어갈 최대 페이지 수
     • 작업집합 윈도우(working set window): 작업집합에 포함되는 페이지의 범위

페이지 부재(페이지 폴트) 빈도

페이지 부재 횟수를 기록하여 페이지 부재(페이지 폴트) 비율을 계산하는 방식

• 페이지 부재 상한선: 할당한 프레임이 적다는 의미로 프레임을 추가하여 늘린다.
• 페이지 부재 하한선: 메모리가 낭비된다는 의미로 할당한 프레임을 회수한다.

전역 교체와 지역 교체

• 전역 교체: 전체 프레임을 대상으로 교체 알고리즘을 적용
• 지역 교체: 현재 실행 중인 프로세스의 프레임을 대상으로 교체 알고리즘을 적용