JSCODE 모의면접 스터디
운영체제 6기 5주차
목차
1. 요구 페이징
요구 페이징은 프로세스가 실행되는 동안 필요한 페이지만 메모리에 적재하고, 필요하지 않은 페이지는 디스크에 저장하여 메모리를 절약하는 기법이다.
요구 페이징 시스템이 안정적으로 작동하려면 두 가지를 해결해야 한다. => 페이지 교체와 프레임 할당
작동 원리
- CPU가 페이지에 접근하면 페이지 테이블의 유효 비트를 확인한다.
- 유효 비트가 1이면(해당 페이지가 메모리에 있음) CPU는 해당 프레임에 직접 접근한다.
- 유효 비트가 0이면(해당 페이지가 메모리에 없음) 페이지 폴트가 발생한다.
- 운영체제의 페이지 폴트 처리 루틴이 동작한다.
- 디스크에서 해당 페이지를 찾는다.
- 메모리의 빈 프레임에 페이지를 적재한다. (빈 프레임이 없다면 페이지 교체가 필요)
- 페이지 테이블의 유효 비트를 1로 설정한다.
- 페이지 폴트 처리가 완료되면 CPU는 다시 해당 페이지에 접근을 시도한다.
장점
- 실제 필요한 페이지만 메모리에 적재하므로 메모리 사용이 효율적임
- 물리적 메모리보다 큰 용량의 프로그램도 실행 가능
- 각 프로세스가 독립된 가상 주소 공간을 가지므로 프로세스 간 독립성이 보장됨
페이지 폴트 (페이지 부재, Page Fault)
페이지 폴트는 프로세스가 접근하려는 페이지가 물리 메모리에 존재하지 않을 때 발생하는 인터럽트이다.
프로세스가 특정 페이지를 참조할 때, 페이지 테이블의 해당 페이지 항의 유효 비트가 0이면 페이지 폴트가 발생한다.
페이지 폴트가 너무 자주 발생하면 디스크 I/O가 증가하여 시스템 성능이 크게 저하된다. 따라서 운영체제는 페이지 교체 알고리즘과 프레임 할당 정책을 통해 페이지 폴트의 발생을 최소화해야 한다.
2. 페이지 교체
페이지 폴트가 발생하면 요청된 페이지를 디스크에서 메모리로 가져와야 하는데, 이때 메모리에 빈 프레임이 없다면 기존 페이지 중 하나를 디스크의 스왑 영역으로 보내고 새로운 페이지를 해당 프레임에 적재해야 한다. 이를 페이지 교체라고 한다.
즉, 새로운 페이지를 메모리에 적재하기 위해 현재 메모리에 있는 페이지 중 하나를 디스크(스왑 영역)으로 보내는 것이다.
페이지 교체 알고리즘
페이지 교체 알고리즘은 교체할 페이지(희생 페이지, victim page)를 선정하는 알고리즘이다. 시스템 성능은 페이지 폴트 발생 빈도에 크게 영향을 받기 때문에, 앞으로 사용할 가능성이 적은 페이지를 희생 페이지로 선정하는 것이 중요하다.
페이지 참조열과 성능 평가
페이지 교체 알고리즘의 성능은 페이지 폴트 발생 횟수로 평가한다. 동일한 페이지 참조열(메모리 접근 순서)에 대해 페이지 폴트를 가장 적게 발생시키는 알고리즘이 좋은 알고리즘이다.
페이지 교체 알고리즘 종류
| 종류 | 알고리즘 | 특징 |
| 간단한 알고리즘 | 무작위 | 무작위로 대상 페이지를 선정하여 스왑 영역으로 보낸다. |
| FIFO | 처음 메모리에 올라온 페이지를 스왑 영역으로 보낸다. | |
| 이론적 알고리즘 | 최적 | 미래의 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다. |
| 최적 근접 알고리즘 | LRU | 시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보낸다. |
| LFU | 사용 빈도가 적은 페이지를 스왑 영역으로 보낸다. | |
| NUR | 최근에 사용한 적이 없는 페이지를 스왑 영역으로 보낸다. | |
| FIFO 변형 | FIFO 알고리즘을 변형하여 성능을 높인다. |
1. 무작위 페이지 교체 알고리즘
(Random Page Replacement Algorithm)
페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있는 방식으로, 대상 페이지(victim page)를 무작위로 선정하는 방식이다.
참조 지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정되기도 하여 알고리즘의 성능이 좋지 않다.
2. FIFO 페이지 교체 알고리즘
(First In First Out Page Replacement Algorithm)
시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 교체하는 방식이다.
큐를 사용하여 구현하며, 새로운 페이지는 큐의 맨 뒤에 추가되고 교체가 필요할 때(메모리가 꽉 차면)는 큐의 맨 앞 페이지가 스왑 영역으로 이동한다.
한계점
FIFO의 가장 큰 문제점은 페이지의 사용 빈도를 고려하지 않는다는 것이다. 메모리에 오래 있었더라도 자주 사용되는 페이지가 교체될 수 있어 시간의 지역성을 반영하지 못해 성능 저하의 원인이 된다. 이러한 한계를 개선한 것이 2차 기회 페이지 교체 알고리즘이다.
3. 최적 페이지 교체 알고리즘
(Optimal Page Replacement Algorithm)
최적 페이지 교체 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘이다. 메모리의 모든 페이지에 대해 다음 참조 시점을 미리 확인하여 가장 늦게 사용될 페이지를 교체 대상으로 선정한다.
이 알고리즘은 이론적으로 가장 좋은 성능을 보이지만, 미래의 페이지 참조를 예측하는 것이 불가능하여 실제로 구현할 수 없다. 따라서 이 알고리즘은 다른 교체 알고리즘의 성능을 평가하는 기준으로 사용되며, 이 알고리즘에서 발생하는 페이지 폴트 횟수를 하한선으로 삼아 다른 알고리즘의 성능을 평가한다.
최적 근접 알고리즘 (Optimal Approximation Algorithm)
최적 알고리즘을 현실적으로 구현하기 위해 과거의 데이터를 기반으로 미래를 예측하는 여러 알고리즘이 개발되었다. 이 알고리즘들은 최적 알고리즘에 근접한 성능을 보이면서도 실제 구현이 가능하다.
- LRU: 가장 오랫동안 사용되지 않은 페이지 교체
- LFU: 사용 빈도가 가장 낮은 페이지 교체
- NUR: 최근에 사용되지 않은 페이지 교체
4. LRU 페이지 교체 알고리즘
(Least Recently Used page replacement algorithm)
LRU 알고리즘 '최근 최소 사용 페이지 알고리즘'으로, 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다. 세 가지 구현 방식으로 나뉜다.
1. 페이지 접근 시간 기반 구현
LRU의 가장 기본적인 구현 방식으로, 각 페이지마다 마지막으로 접근한 시간을 기록하여 가장 오래된 접근 시간을 가진 페이지를 교체하는 방식이다. (접근: 읽기, 쓰기, 실행)
FIFO가 메모리 진입 시간을 기준으로 한다면, LRU는 실제 사용된 시간(마지막 접근 시간) 을 기준으로 한다.
일반적으로 FIFO보다 우수하고 최적 알고리즘보다는 약간 떨어지는 성능을 가진다.
2. 카운터 기반 구현
각 페이지마다 카운터를 두어 접근할 때마다 카운터 값을 갱신하는 방식이다. 교체가 필요한 시점에 가장 작은 카운터 값을 가진 페이지를 교체한다.
시간 기반 방식과 마찬가지로 카운터 값을 저장할 추가 메모리 공간이 필요하다.
3. 참조 비트 쉬프트 방식
각 페이지에 일정 크기의 참조 비트를 할당하고, 페이지 접근 시 맨 앞 비트를 1로 설정한 뒤 주기적으로 모든 비트를 오른쪽으로 한 칸씩 이동시키는 방식이다. 이를 통해 각 페이지의 최근 사용 여부를 비트 패턴으로 기록하게 되며, 최근에 접근할 페이지일수록 참조 비트값이 크고, 오래전에 접근한 페이지일수록 참조 비트값이 작아진다. 따라서 교체가 필요할 때는 가장 작은 참조 비트값을 가진 페이지(즉, 가장 오랫동안 접근하지 않은 페이지)를 선택한다.
LFU가 페이지의 총 접근 횟수를 기준으로 한다면, 이 방식은 페이지의 최근 접근 시점을 기준으로 하므로 LRU의 한 구현 방식으로 분류된다.
한계점
세 가지 구현 방식 모두 페이지의 접근 이력을 관리하기 위해 추가 메모리 공간이 필요하다. 이것은 전체 시스템의 메모리 효율성을 저하시킬 수 있다.
5. LFU 페이지 교체 알고리즘
(Least Frequently Used page replacement algorithm)
LFU 알고리즘은 '최소 빈도 사용 알고리즘'으로, 페이지에 올라온 페이지들의 사용 빈도(접근 횟수)를 기준으로 가장 적게 사용된 페이지를 교체하는 알고리즘이다.
각 페이지는 메모리에 처음 올라올 때 사용 빈도가 1로 시작함, 접근할 때마다 해당 값이 1씩 증가한다. 교체가 필요한 시점에는 사용 빈도가 가장 낮은 페이지를 선택하며, 만약 동일한 사용 빈도를 가진 페이지들이 있다면 가장 먼저 들어온 페이지를 교체한다.
LRU 가 최근 사용 시점을 기준으로 선정하는 것과 달리, LFU는 총 사용 횟수를 기준으로 한다. 두 알고리즘은 비슷한 수준의 성능을 보이며, 모두 FIFO 보다 우수한 성능을 제공한다.
한계점
LFU도 LRU와 마찬가지로 각 페이지의 접근 횟수를 저장하기 위한 추가 메모리 공간이 필요하다.
6. NUR 페이지 교체 알고리즘
(Not Used Recently page replacement algorithm)
NUR 알고리즘은 '최근 미사용 페이지 교체 알고리즘'으로, LRU와 LFU의 성능은 유지하면서 메모리 공간 낭비 문제를 해결한 알고리즘이다.
각 페이지는 참조 비트와 변경 비트 2개만을 사용하여 상태를 관리한다. 참조 비트는 페이지 접근(read/execute) 시 1이 되고, 변경 비트는 페이지 변경(write/append) 시 1이 된다. 초기 상태는 (0,0)이며, 각 비트의 조합에 따라 (0,0), (0,1), (1,0), (1,1)의 네 가지 상태가 가능하다.
교체 대상은 (참조 비트, 변경 비트) 상태에 따라 다음 우선순위로 선정된다.
1. (0,0): 접근도 변경도 없는 페이지
2. (0,1): 접근은 없고 변경만 있는 페이지
3. (1,0): 접근만 있고 변경은 없는 페이지
4. (1,1): 접근과 변경이 모두 있는 페이지
만약 모든 페이지가 (1,1) 상태가 되면 모든 비트를 (0,0)으로 초기화한다.
장점
페이지당 2비트만을 사용하여 LRU, LFU와 비슷한 성능을 내면서도 메모리 공간을 효율적으로 사용한다.
7. FIFO 변형 알고리즘
FIFO의 성능 개선을 위해 자주 사용되는 페이지를 고려하도록 변형한 알고리즘으로, 2차 기회 알고리즘과 시계 알고리즘이 있다.
1. 2차 기회 알고리즘 (Second Chance Algorithm)
FIFO를 기반으로 하되, 페이지 참조 시 해당 페이지를 큐의 맨 뒤로 이동시켜 추가 기회를 제공하는 알고리즘이다. 성능은 LRU, LFU, NUR 보다는 낮고 FIFO 보다는 높다. 큐 유지 비용이 높고, 중간의 페이지를 뒤로 이동하는 추가 작업이 필요하다는 단점이 있다.
2. 시계 알고리즘 (Clock Algorithm)
원형 큐와 포인터를 사용하여 구현되며, 각 페이지는 참조 비트를 가진다. 페이지가 참조될 때 해당 페이지의 참조 비트는 1이 되고, 포인터는 교체할 페이지를 찾을 때 시계 방향으로 이동한다. 포인터가 참조 비트가 1인 페이지를 가리키면, 해당 페이지의 참조 비트를 0으로 바꾸고 다음 페이지로 이동한다. 참조 비트가 0인 페이지를 만나면 그 페이지를 교체한다. NUR 보다 적은 추가 공간이 필요하지만, 알고리즘이 복잡하고 계산량이 많다는 단점이 있다.
차이점
2차 기회 알고리즘은 일반 큐를 사용하고 페이지를 뒤로 이동시키는 반면, 시계 알고리즘은 원형 큐를 사용하고 포인터만 이동시킨다. 시계 알고리즘은 참조 비트를 사용하여 페이지의 상태를 관리한다는 점에서도 차이가 있다.
3. 스레싱과 프레임 할당
페이지 폴트가 자주 발생하는 주요 원인
- 나쁜 페이지 교체 알고리즘
- 프로세스에 할당된 프레임 수 부족
스레싱 (thrashing)
스레싱은 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 현상이다. (작업이 멈춘 것 같은 상태)
동시에 실행되는 프로세스 수가 필요 이상으로 증가하면 각 프로세스들이 사용할 수 있는 프레임 수가 감소하기 때문에 페이지 폴트가 지나치게 빈번히 발생하고, 이에 따라 CPU 이용률이 떨어져 전체적인 성능이 저하된다.
스레싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다. 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.
프레임 할당 방식
실행 중인 여러 프로세스에 프레임을 얼마나 나누어주느냐(프레임 할당량)에 시스템 성능이 달라진다. 너무 적은 프레임을 할당하면 페이지 폴트가 빈번히 일어나고, 너무 많은 프레임을 할당하면 페이지 폴트는 줄지만 메모리를 낭비하여 시스템 성능이 낮아진다. 따라서 남아 있는 프레임을 실행 중인 프로세스에 적절히 나누어주는 정책이 필요하다.
프로세스에 프레임을 할당하는 방식은 정적 할당과 동적 할당으로 구분된다.
정적 할당 (static allocation)
정적 할당 방식은 프로세스 실행 초기에 프레임을 나누어준 후 그 크기를 고정하는 것으로, 균등 할당 방식과 비례 할당 방식이 있다.
균등 할당 (equal allocation)
균등 할당 방식은 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다.
크기가 큰 프로세스의 경우 필요한 만큼 프레임을 할당받지 못해 페이지 폴트가 빈번하게 발생하고, 크기가 작은 프로세스의 경우 메모리가 낭비된다.
비례 할당 (proportional allocation)
비례 할당 방식은 프로세스의 크기에 비례하여 프레임을 할당하는 방식이다.
프로세스 크기를 고려하지 않는 균등 할당보다 좀 더 현질적인 방식이지만 두 가지 문제가 있다.
- 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못함.
ex) 동영상 플레이어: 동영상 플레이어 프로그램 자체의 크기는 작지만 재생되는 동영상의 크기가 큼. 실행되는 동안 플레이어보다 몇 십 배 큰 메모리를 필요로 함. 이때 필요로 하는 프레임을 유동적으로 반영하지 못함. - 사용하지 않을 메모리를 처음부터 미리 확보하여 공간을 낭비함.
큰 프로세스를 실행하면서 당장 필요없는 프레임을 미리 할당하기 때문에 메모리가 낭비됨.
동적 할당 (dynamic allocation)
동적 할당 방식은 프로세스의 실행 중 변화하는 프레임 요구량을 반영하여 할당하는 방식으로, 작업 집합 모렏과 페이지 폴트 빈도를 사용한다.
작업 집합 모델 (working set model)
작업 집합 모델은 지역성 이론을 바탕으로, 최근 참조된 페이지들의 집합을 물리 메모리에 유지하는 방식이다. 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높다는 가정에서 출발한다.
- 작업 집합 크기: 물리 메모리에 유지할 페이지의 크기. 작업 집합에 들어갈 최대 페이지 수를 의미함. 얼마나 자주 작업 집합을 갱신할 것인지도 의미함. ex) 작업 집합 크기가 5라는 것은 페이지에 5번 접근할 때마다 작업 집합을 갱신한다는 의미.
- 작업 집합 윈도우: 작업 집합에 포함되는 페이지의 범위. 현재 시점에서 최대 어느 범위까지의 페이지를 살펴볼 것인가를 결정하는 것.
작업 집합 윈도우의 크기에 따라 프로세스의 실행 성능이 달라진다. 너무 크게 잡으면 필요없는 페이지가 메모리에 남아 다른 프로세스에 영향을 미치고, 너무 작게 잡으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스의 성능이 떨어진다.
페이지 폴트 빈도 (page fault frequency: PFF)
작업 집합 모델의 경우 충분한 페이지를 할당하지 않으면 작업 집합에 있는 페이지를 물리 메모리에 유지하기 힘들다. 어떤 프레임을 물리 메모리에 유지해야 하는지는 알 수 있지만 프로세스가 프레임을 얼마나 할당해야 하는지는 알 수 없다. 즉, 프로세스의 성능을 높이는 방법이지만 스레싱 문제를 해결하지 못한다. 이러한 프레임 할당량 결정 문제를 해결하기 위해 페이지 폴트 빈도를 활용한다.
페이지 폴트 빈도를 이용하는 것은 페이지 폴트 발생 비율을 기준으로 프로세스가 필요로 하는 페이지의 양을 동적으로 조절하는 방식이다. 페이지 폴트 횟수를 기록하여 페이지 폴트 비율을 계산한다.
페이지 폴트 비율의 상한선과 하한선을 설정하여, 페이지 폴트 비율이
- 상한선 초과: 프레임 부족으로 판단 → 프레임을 추가 할당
- 하한선 미만: 메모리가 낭비로 판단 → 할당한 프레임 회수
초기 페이지 할당량을 예측하기 어렵기 때문에, 프로세스를 실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절한다.
REF
'Study > 운영체제' 카테고리의 다른 글
| [운영체제] 가상 메모리 (1) - 기본 개념과 구현 방식 (0) | 2024.11.24 |
|---|---|
| [운영체제] 프로세스 동기화 (0) | 2024.11.19 |
| [운영체제] CPU 스케줄링 (0) | 2024.11.12 |
| [운영체제] 프로세스와 스레드 (0) | 2024.11.07 |
| [운영체제] 운영체제 개요 & 컴퓨터 시스템 동작원리 (0) | 2024.10.28 |
댓글