[운영체제] 10강 - 페이지 교체 알고리즘

✅ 1. 페이지 교체 알고리즘

(1) 페이징 기법 - 교체 알고리즘의 필요성

• 페이징 기법: 가상 메모리를 페이지 단위(동일한 크기의 블록)로 나누어 관리하는 기법을 의미함.
• 교체 알고리즘의 필요성: 페이징 기법에서 모든 페이지 프레임이 사용되고 있을 경우, 새로 적재되어야 할 페이지를 위해서 적절한 교체 대상을 결정해줘야함.
• 즉, 위의 예시를 보면 가상 메모리의 c 라는 페이지를 페이지 프레임에 적재할 때 메모리에 공간이 부족할 경우 교체 대상을 페이지에서 선택하는데, e' 을 선택한다고 가정하고, 해당 페이지를 가상 메모리는 보조기억장치에 있으므로, 해당 가상 메모리(보조기억장치)에 보관을 하게 되며, 이후 c 페이지를 메모리에 적재하는 원리임.
• 결론: 페이지 교체 알고리즘은 페이지 프레임이 가득찬 경우 등에 따라서 기존 페이지를 빼고 다른 페이지를 넣는 과정임.

(2) 교체 대상 선택

• 교체 대상 선택: 교체 대상을 선택하는 기준을 의미한다.
• (1) 최적화의 원칙: 앞으로 가장 오랫동안 사용되지 않을 페이지를 기준으로 교체 대상으로 선택해서 교체를 진행하는 것임. 즉, 페이지 중에서 가장 나중에 실행 될 페이지를 기준으로 교체를 진행하는 것임.
• 이론적으로 최적이지만 미래를 예측할 수 없어 실현이 불가능함.
• (2) 선택을 위한 기본 정책: 대체적으로 좋은 결론은 내리면서, 오버헤드가 가급적 적은 방법을 선택한다는 정책상에서 페이지 교체대상을 선택하는 방법을 의미한다.

• 교체 제외 페이지: 페이지 프레임 내의 모든 페이지는 교체 대상이 되면 안되기 때문에, 교체 제외 페이지가 존재함.
• 페이징을 위한 커널 코드 영역: 페이징을 도와주는 커널 코드 영역이 페이지 단위로 돌아가기 때문에 교체 제외 대상이어야함.
• 보조기억장치 드라이버 영역: 언제 보조기억장치를 쓸지 모르기 때문에 드라이버 영역은 교체 제외 페이지여야함.
• 시간을 맞춰 동작해야 하는 코드 영역: 적정 시간마다 동작하는 코드를 교체 대상으로 하면 문제가 발생 할 수 있음.
• 입출력장치를 위한 데이터 버퍼 영역 등

(3) 페이지 교체 알고리즘 - 종류

• 적절한 대상중에서 페이지를 교체해야 하는 상황에 교체 대상을 선택하는 방법에 따라서 페이지 교체 알고리즘이 나뉨.

(4) 페이지 교체 알고리즘 - FIFO 페이지 교체

• FIFO 페이지 교체: 페이지 프레임에 가장 먼저 메모리 공간을 할당 받은 페이지를 가장 먼저 선택하여 교체하는 방식임.
• 즉, 메모리 내에 가장 오래 있었던 페이지를 선택하여 교체하는 방식이며, FIFO Queue 를 이용하여 구현이 됨.

• 단점: 먼저 들어온 페이지를 먼저 교체 대상으로만 보기 때문에, 가장 많이 쓰이는 페이지가 뭔지 모를 수 있어 많이 쓰이는 페이지가 교체 될 가능성이 존재함.
• Belady의 이상현상: 메모리를 늘리면 페이지 부재가 줄어들 것이라 예상할 수 있지만, 특정 상황에서는 오히려 그 반대의 결과가 나타나기도 하는데, 이러한 현상을 Belady의 이상현상이라고 말함.

• 쉽게 말해, FIFO 메모리 교체 알고리즘을 사용할 경우, 프레임 수를 늘렸음에도 불구하고 페이지 부재 횟수가 오히려 증가하는 현상이 발생하는데, 이를 발견자의 이름을 따서 Belady의 이상현상이라고 부름.
• 결론: FIFO 페이지 교체 알고리즘은 현대적인 범용 운영체제에서는 그대로 사용하는 경우가 거의 없음.

(5) 페이지 교체 알고리즘 - LRU 페이지 교체

• LRU 페이지 교체: Least Recently Used = 최근에 가장 적게 사용한 페이지를 교체 대상으로 보는 알고리즘임.
• 즉, 메모리 내에서 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 방식으로 볼 수 있음.
• 국부성: CPU가 데이터를 처리할 때 메모리의 모든 곳을 무작위로 뒤지는 게 아니라, 방금 썼던 곳이나 그 근처를 다시 찾을 확률이 압도적으로 높다는 관찰 결과를 의미함. 즉,   "최근의 상황이 가까운 미래에 대한 좋은 척도" 를 의미함.
• 시간 국부성: 한 번 참조된 데이터는 가까운 시일 내에 또 참조될 가능성이 높다는 성질을 의미함.
• 공간 국부성: 특정 데이터 근처에 있는 데이터들이 연속적으로 참조될 가능성이 높다는 성질을 의미함.
• 결론: 이러한 국부성을 활용한 방식이 LRU 페이지 교체 알고리즘인것임.
• 구현 방법: 참조시각 또는 리스트를 이용하는 두 가지 구현 방법이 존재함.

• 참조시각을 이용한 구현: 각 페이지가 참조될 때마다 그때의 시각을 테이블에 기록하는 방식이다.
• 만약 교체가 필요한 경우(페이지 프레임 공간이 부족한 경우) 참조시각이 가장 오래된 페이지를 선택하여 교체를 진행함.

• 리스트를 이용한 구현: 페이지가 참조될 때마다 참조되는 페이지는 리스트의 제일 선두로 옮기게 되며, 구조가 결국 참조시각이 제일 오래된 페이지는 리스트의 끝에 몰리게 됨.
• 즉, 페이지 프레임이 가득차서 교체가 필요한 경우 리스트의 끝에 있는 페이지를 선택하여 교체가 되는 원리임.

• LRU 페이지 교체 장점: Belady의 이상현상이 발생하지 않으며, 국부성이 존재하기 때문에 최적화 원칙에 근사한 선택 가능
• LRU 페이지 교체 단점: 국부성이 맞지 않는 상황도 존재 할 수 있으며, 참조시간을 이용해서 구현한다고 가정하면 참조 할 때마다 참조 시간을 업데이트 해주거나 시간이 제일 적은 교체 대상을 찾는 것들이 결국엔 막대한 오버헤드가 될 수 있음.
• 결론: 막대한 오버헤드로 인해 실제로 사용하기엔 무리가 있음.

(6) 페이지 교체 알고리즘 - LFU 페이지 교체

• LFU 페이지 교체: 앞서 LRU 페이지 교체 알고리즘은 참조 시간이 제일 오래 된 것이 결국 많이 쓰이지 않았다는걸로 판단 기준을 내려서 교체 대상으로 보는 것이지만, LFU 페이지 교체 알고리즘은 메모리 내에서 참조된 횟수를 기준으로 횟수가 가장 적은 페이지가 결국 많이 쓰이지 않는 페이지로 판단 기준을 내려서 교체 대상으로 보는 방식임.
• 구현: 참조횟수 자체를 카운트 하는 방식이며, 해당 횟수를 판단 기준으로 교체 대상을 파악함.

• 단점1: 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성이 높으며, 이것은 결국 중요한 페이지가 들어왔을 때 판단 기준을 참조횟수로 보기 때문에 중요한 페이지 또한 교체될 가능성이 높음.
• 단점2: 위와 반대로 초기에 매우 많이 사용된 후가 되면, 매우 많은 참조횟수 카운터를 가지는데 이 페이지가 더 이상 사용되지 않을 경우에도 참조횟수가 많기 때문에 계속 페이지 프레임을 점유 할 가능성이 높음. 즉, 교체 가능성이 낮아짐.
• 단점3: 참조 할 때마다 해당 페이지의 카운트를 늘려주고, 교체 대상을 찾을 때마다 카운트 최솟값을 찾아야 하기 때문에 막대상 오버헤드가 발생할 수 있음.
• 결론: 얘도 실제로 쓰기엔 무리가 있음.

(7) 페이지 교체 알고리즘 - 2차 기회 페이지 교체

• 2차 기회 페이지 교체: 참조 비트가 0이면서 메모리 내에 가장 오래 있었던 페이지를 선택하여 교체하는 방식임.
• 또한, 각 페이지가 메모리에 적재될 때는 참조 비트 0 으로 시작하며, 적재된 상태에서 추가로 참조되면 참조 비트가 1이 됨.

• 참조할 페이지가 페이지 프레임에 있는 경우: 큐 위치 변화 없이 참조 비트만 1로 설정을 함.
• 참조할 페이지가 페이지 프레임에 없는 경우 - 빈 페이지 프레임이 있는 경우: 페이지를 적재해주고, 큐에 추가를 한 뒤 참조 비트는 0으로 설정을 해둠.
• 참조할 페이지가 페이지 프레임에 없는 경우 - 빈 페이지 프레임이 없는 경우: 큐의 선두 항목(가장 오래된 페이지)을 꺼내 참조 비트를 파악 한 뒤, 만약 1이면 0으로 바꿔  큐의 뒤에 추가를 진행하며, 이후 꺼내고 넣고를 반복하면서 만약 페이지 참조 비트가 0인 경우를 만나게 되면 교체 대상으로 선택하여 교체를 하는 방식임.
• 즉, 2차 기회 페이지 교체 알고리즘은 페이지 프레임에 적재된 페이지는 처음 참조 비트 0인 상태를 가지는데 페이지 프레임에 있는 상태에서 한 번더 참조를 당하게 되면 참조 비트 1이 되게 되는데, 이 참조 비트가 결국 교체 대상 과정에서 비트 1을 0으로 바꾸면서 한 번더 기회를 얻어서 큐 입구 부분에 재적재가 되는 것임.
• ** 또한, 2차 기회 페이지 교체를 구현하는 방식은 큐, 변형된 원형 큐 방식이 존재함. **

• 변형된 원형 큐를 이용한 구현: 원형 큐에 특정 포인터가 추가 된 구조로 구현이 되며, 처음 빈 페이지 프레임으로 시작 할 때 페이지가 들어오게 되면 참조 비트 0으로 페이지 프레임에 적재가 되며, 포인터는 페이지 프레임 다음 빈 칸을 가리키게 된다.
• 이후, 큐에 존재하는 페이지가 또 참조가 된 경우 참조 비트를 1로 올려주게 되며, 페이지 프레임에 페이지가 많이 들어와 꽉 차게 된다면, 포인터는 큐의 제일 선두를 가리키는 모습이 될 수 밖에 없음.
• 꽉 찬 경우 포인터가 한 칸씩 넘어가며, 교체 대상을 찾게 되는데, 이때 참조 비트 1인 페이지는 0으로 바뀌며 한 번더 기회를 얻어 스킵이 되며, 0인 참조비트를 발견 할 시 교체 대상이 되어 교체가 됨.

---

✅ 2. 프로세스별 페이지 집합관리

(1) 프로세스별 페이지 집합

• 프로세스별 페이지 집합: 각 프로세스가 원할하게 실행되기 위해 메모리(RAM)에 실제로 유지하고 있는 페이지들의 묶음을 의미하며, 각 프로세스가 사용할 수 있는 "페이지 프레임" 의 개수에 따라 이 집합의 크기가 결정이됨.
• 쉽게 말해, 프로세스 하나의 관점으로 여러 페이지가 분산되어 저장된 페이지 프레임의 개수가 곧 집합이 되는 것임.
• 집합의 크기가 작을수록 시스템 처리량 증대: 프로세스별(페이지) 집합(페이지 프레임 개수)이 작을수록 여러 프로세스를 많이 올려서 처리를 할 수 있기 때문에 처리량이 증대된다는 의미임.
• 하지만, 각 프로세스별 적은 수의 페이지가 페이지 프레임에 적재되기 때문에 각 프로세스의 다음 코드나 데이터(페이지)에서의 페이지 부재가 빈번하게 발생해서 성능이 저하 될 수 있음.
• 집합의 크기가 클수록 프로세스별 페이지 부재는 감소: 프로세스별(페이지) 집합(페이지 프레임 개수)이 클수록 여러 프로세스를 많이 올릴수 없지만, 대신 프로세스당 집합(페이지 프레임 개수)이 크기 때문에 페이지 부재가 감소 될 수 있음.

(2) 워킹 세트 알고리즘

• 각 프로세스가 사용할 수 있는 페이지 프레임 개수를 관리하기 위한 알고리즘이다.
• 페이지 단위는 같지만, 페이지 프레임 개수는 프로세스마다 다를 수 있음. 누구는 더 많고 누구는 더 적고 이런 느낌

• 워킹 세트: 지금 이 프로세스가 원활하게 실행되기 위해 필요한 페이지들의 집합 (최근에 자주 사용한 페이지 묶음)
• 워킹 세트 알고리즘: 지금 실제로 필요로 하는 페이지 집합만 메모리에 유지하도록 관리하는 기법을 의미한다.
• 쉽게 말해, 최근에 사용된 페이지들은 앞으로도 사용할 가능성이 높다는 가정을 이용한다는 의미이다.
• 프로세스의 워킹세트: t(4) 에서 t(4) 를 포함한 직전 델타(3) 시간 동안 참조한 페이지의 집합을 가지고, 해당 페이지들은 메모리에 유지를 시켜줌.

• 워킹 세트 특징: 프로세스가 수행됨에 따라 그 프로세스의 워킹 세트는 변할 수 있으며 워킹 세트의 크기도 달라질 수 있음.
• 워킹 세트 알고리즘의 원칙: 프로세스의 워킹 세트를 메모리에 유지시키는 것이라고 볼 수 있음.
• 워킹 세트를 메모리에 유지하지 않으면 쓰래싱 유발 가능성이 있음.
• 쓰래싱: 쉽게 말해, 프로세스가 실제 작업은 거의 못 하고, 페이지 교체만 계속하는 상태를 의미함.
• 반복문을 예를 들면, A B C D 를 반복해서 수행 할 때, 페이지 프레임 3개만 받았다고 가정하면 A B C 수행하고 A 버리고 D 넣고 B 버리고 A 넣고 이런식으로 페이지 폴트가 반복 되는데 이러한 현상을 쓰래싱이라고 함.
• 해결하기 위해서는 페이지 프레임을 4개를 할당받아 주는 것이며, 이게 결국 워킹 세트를 잘 유지시켜주는 것과 같음.

• 즉, 프로세스마다 워킹 세트 크기에 맞게 페이지 프레임 개수를 조절해줘야함.

(3) 워킹 세트 알고리즘 - 문제점

• 과거를 통해 미래를 예측하는 것이 정확하지 않기 때문에 워킹 세트를 정확히 알아내고 계속 업데이트하는 것이 현실적으로 어려울 수 있음.
• 그렇기 때문에 워킹 세트 윈도 크기인 델타의 최적값을 알기 어려우며 이 역시 변화할 수 있다는 문제가 있음.

(4) PFF 알고리즘

• PFF 알고리즘: 페이지 폴트 발생 빈도를 보고, 메모리를 더 줄지/늘릴지 결정하는 방식
• 즉, 프로세스에 할당할 메모리(프레임 수)를 조절하는 알고리즘임.
• 목적: 쓰래싱 방지

• 즉, PFF는 기준값(임계치) 2개인 상한선과 하산선을 두고, 필요한 페이지가 메모리에 부족하다면 워킹셋 유지가 안되는 것이므로, 프레임을 더 주고(메모리 증가), 페이지 폴트가 너무 적다면 메모리를 과하게 사용 중이라 판단해 프레임(메모리)을 줄임
• 장점: 부재가 발생 할 때 마다 PFF 알고리즘이 수행돼 오버헤드가 워킹 세트보다 적다는 장점이 있음.

(5) 정리

• 워킹세트 알고리즘 & PFF: 둘 다 결국 페이지 폴트 폭증(스래싱) 문제를 막기 위해서 고안된 방법임.
• 워킹세트 알고리즘: 최근 일정 시간동안 참조된 페이지 집합을 메모리에 유지를 하는 방식이며, 필요한 페이지를 미리 유지해서 페이지 폴트를 감소시키며, 프로세스가 안정적으로 실행되도록 보장함. (시간 기반)
• PFF: 페이지 폴트 발생 빈도를 기준으로 메모리 할당을 조절하는 방식이며, 페이지 폴트 많고 적음에 따라서 프로세스에게 페이지 프레임을 더 할당하거나 제거를 진행함. (빈도 기반)