사전 지식 일반 OS와 리얼타임 OS(RTOS) 선점형OS와 비선점형OS 프로세스의 생성과 소멸
우선순위 스케줄링 알고리즘
우선순위 스케줄링은
우선순위가 높은 프로세스 또는 스레드에게 CPU를 먼저 할당하는 방식이다.
즉, Ready 상태에 있는 작업들 중에서 우선순위가 가장 높은 작업이 먼저 선택된다.
다만 여기서 중요한 점은,
우선순위가 높다는 것이 단순히 CPU를 더 많이 받는다는 의미라기보다,
스케줄러가 다음 실행 대상을 고를 때 더 먼저 선택된다는 의미에 가깝다.
비선점형 우선순위 스케줄링
비선점형 방식에서는 현재 실행 중인 프로세스가 있다면,
더 높은 우선순위의 프로세스가 Ready 상태가 되더라도 바로 CPU를 빼앗지는 않는다.
현재 프로세스가 CPU를 양보하거나,
I/O 요청으로 Blocked 상태가 되거나,
작업을 종료한 뒤에야 다음 프로세스가 선택된다.
낮은 우선순위 프로세스 실행 중
↓
높은 우선순위 프로세스 Ready 상태 진입
↓
바로 전환되지는 않음
↓
현재 프로세스가 양보 / I/O / 종료
↓
높은 우선순위 프로세스 실행
선점형 우선순위 스케줄링
선점형 방식에서는 현재 실행 중인 프로세스보다
더 높은 우선순위의 프로세스가 Ready 상태가 되면,
운영체제가 현재 프로세스의 CPU 사용권을 회수하고 높은 우선순위 프로세스를 실행할 수 있다.
낮은 우선순위 프로세스 실행 중
↓
높은 우선순위 프로세스 Ready 상태 진입
↓
OS가 CPU 사용권 회수
↓
높은 우선순위 프로세스 실행
Windows는 선점형 우선순위 기반 스케줄링을 사용하고,
같은 우선순위의 실행 가능한 스레드들 사이에서는 라운드 로빈 방식으로 CPU 시간을 나눠준다.
기아 상태
우선순위 스케줄링의 대표적인 문제는 기아 상태다.
기아 상태란, 우선순위가 낮은 프로세스가 계속 Ready 상태에 있음에도
더 높은 우선순위의 프로세스들이 계속 등장해서 CPU를 거의 얻지 못하는 상황이다.
실제 시스템에서는 높은 우선순위 작업도 I/O로 인해 Blocked 상태가 될 수 있기 때문에 낮은 우선순위 작업이 실행될 기회가 생길 수 있다. 그러나 높은 우선순위 작업이 계속 Ready 상태로 존재하면 낮은 우선순위 작업은 CPU를 얻지 못하는 기아 상태에 빠질 수 있다.
Aging
Aging은 오래 기다린 프로세스의 우선순위를 점진적으로 높여주는 방식이다.
낮은 우선순위 프로세스가 Ready Queue에서 너무 오래 기다리면,
시간이 지남에 따라 우선순위를 올려 언젠가는 CPU를 할당받을 수 있게 한다.
낮은 우선순위 프로세스
↓Ready Queue에서 오래 대기
↓우선순위 점진적 상승
↓CPU 할당 기회 증가
라운드 로빈 스케줄링 알고리즘
라운드 로빈은 각 프로세스 또는 스레드에게
정해진 시간만큼 CPU를 할당하고, 시간이 끝나면 다음 작업에게 CPU를 넘기는 방식이다.
이때 정해진 시간 단위를 Time Slice 또는 Time Quantum이라고 한다.
Process A 실행
↓
Time Slice 만료 Process B 실행
↓
Time Slice 만료 Process C 실행
↓
Time Slice 만료 Process A 실행
라운드 로빈은 같은 우선순위를 가진 작업들 사이에서
CPU 사용 기회를 공평하게 나눠주기 위해 사용된다.
Time Slice가 긴 경우
Time Slice를 길게 잡으면 한 프로세스가 CPU를 오래 사용할 수 있다.
장점은 컨텍스트 스위칭 횟수가 줄어든다는 것이다.
하지만 단점은 다른 프로세스가 CPU를 얻기까지 오래 기다릴 수 있어
사용자 입력이나 짧은 작업에 대한 반응성이 떨어질 수 있다.
Time Slice가 길다→ 컨텍스트 스위칭 감소→ 오버헤드 감소→ 하지만 반응성 저하 가능
Time Slice가 짧은 경우
Time Slice를 짧게 잡으면 여러 프로세스가 자주 번갈아 실행된다.
장점은 응답성이 좋아질 수 있다는 것이다.
하지만 단점은 컨텍스트 스위칭이 자주 발생해서
CPU 시간이 실제 작업보다 전환 비용에 더 많이 쓰일 수 있다는 것이다.
Time Slice가 짧다→ 자주 교체됨→ 반응성 향상 가능→ 하지만 컨텍스트 스위칭 오버헤드 증가
스케줄러의 동작 시점
스케줄러는 CPU를 다음에 어떤 프로세스 또는 스레드에게 할당할지 결정하는 역할을 한다.
따라서 스케줄러는 현재 실행 흐름을 계속 유지할 수 없거나, 더 적절한 실행 대상이 생겼을 때 동작한다.
1. Time Slice가 만료되었을 때
라운드 로빈 관점에서는 각 프로세스 또는 스레드가 정해진 시간만큼만 CPU를 사용한다. Time Slice가 끝나면 타이머 인터럽트가 발생하고, 운영체제는 현재 작업을 계속 실행할지, 같은 우선순위의 다른 작업에게 CPU를 넘길지 결정한다.
2. 더 높은 우선순위의 작업이 Ready 상태가 되었을 때
우선순위 스케줄링 관점에서는 새로운 작업이 생성되거나, 블로킹되어 있던 작업이 깨어났을 때 스케줄러가 동작할 수 있다. ㅡ특히 선점형 우선순위 스케줄링에서는 현재 실행 중인 작업보다 더 높은 우선순위의 작업이 Ready 상태가 되면, 현재 작업을 중단하고 높은 우선순위 작업을 실행할 수 있다.
3. 현재 실행 중인 작업이 Blocked 상태가 되었을 때
현재 실행 중인 프로세스 또는 스레드가 I/O 요청, 락 대기, 이벤트 대기 등으로 인해 Blocked 상태가 되면 CPU를 더 이상 사용할 수 없다. 이 경우 운영체제는 Ready 상태에 있는 다른 작업을 선택해야 하므로 스케줄러가 동작한다.
4. 프로세스 또는 스레드가 종료되었을 때
현재 실행 중인 작업이 종료되면 더 이상 CPU를 사용할 대상이 아니므로, 운영체제는 다음 실행 대상을 선택해야 한다.따라서 작업 종료 시에도 스케줄러가 동작한다.
Priority Inversion
Priority Inversion은 직역하면 우선순위 역전이다. 하지만 실제 의미는 단순히 우선순위 값이 바뀐다는 뜻이 아니다.
높은 우선순위 작업이 낮은 우선순위 작업이 가진 자원 때문에 기다리게 되고, 그 사이에 중간 우선순위 작업이 실행되면서 높은 우선순위 작업이 간접적으로 밀리는 현상이다.
예시
A: 높은 우선순위
B: 중간 우선순위
C: 낮은 우선순위
C가 Mutex 점유
↓
A가 같은 Mutex 필요
↓
A는 C가 Mutex를 놓을 때까지 Blocked
↓
B는 A보다 우선순위가 낮지만 C보다 높음
↓
B가 실행됨
↓
C는 CPU를 얻지 못해서 Mutex를 해제하지 못함
↓
A는 계속 대기
결과적으로 가장 높은 우선순위인 A가,
직접적으로는 C 때문에 막혔고,
간접적으로는 B 때문에 더 오래 지연된다.
즉, 실행 결과만 보면:
A보다 우선순위가 낮은 B가 실행되고,A는 계속 기다리는 상황
이 발생한다.
해결 방법: Priority Inheritance
Priority Inversion을 완화하기 위한 대표적인 방법은 Priority Inheritance다.
Priority Inheritance는 낮은 우선순위 작업이 높은 우선순위 작업이 필요로 하는 자원을 가지고 있을 때,
일시적으로 낮은 우선순위 작업의 우선순위를 높여주는 방식이다.
C가 Mutex 점유
↓
A가 Mutex를 기다림
↓
C의 우선순위를 A 수준으로 임시 상승
↓
B보다 C가 먼저 실행됨
↓
C가 Mutex 해제
↓
A 실행 가능
↓
C의 우선순위 원래대로 복구
즉, C를 빨리 실행시켜 자원을 해제하게 만들고,
A가 더 이상 불필요하게 밀리지 않도록 한다.