1 스케줄링 성능 평가 기준
평균 대기시간
- 대기시간 : 프로세스가 수행 완료까지 준비 큐에서 기다리는 시간
- 평균 대기시간 : 각 프로세스의 대기시간의 평균값
평균 반환시간
- 반환시간 : 프로세스 생성 시점부터 수행 완료 시점까지 소요시간
- 평균 반환시간 : 각 프로세스의 반환시간의 평균값
2 다양한 스케줄링 알고리즘
용어 정리
비선점 : 자원이 CPU를 사용하는 동안 반환하지 않는것.
비선점 스케줄링 : 자원이 일단 CPU를 할당받아 작업을 수행하면 작업이 끝날때까지 CPU를 사용할 수 있다.
선점 : 자원이 우선순위에 따라 CPU를 반환하는 것.
선점 스케줄링 : 어떤 자원이 CPU를 할당받아 작업을 수행하던 중이라도 우선순위에서 밀려나면 CPU를 반납하고 작업 큐로 돌아가야 한다.
문맥교환 : 프로세스가 사용중이던 CPU를 다른 프로세스에게 넘겨줄 때 이전의 프로세스 상태(문맥)을 보관하고 새로운 프로세스 상태를 적재하는 작업이다. 프로세스의 문맥은 그 프로세스의 PCB(프로세스 제어 블럭)에 기록된다.
오버헤드 : 문맥교환이 일어나는 동안 다른 작업을 할 수 없는데 그 시간을 일종의 오버헤드라고 할 수 있다.
2.1 FCFS(First-Come First-Served)
- 비선점 스케줄링 알고리즘
- 준비 큐 도착 순서에 따라 디스패치
장단점
- 장점
- 가장 간단한 스케줄링 방법
- 단점
- 짧은 프로세스가 긴 프로세스를 기다려야 되거나 중요한 프로세스가 나중에 수행될 수 있다.
- 프로세스 도착 순서에 따라 평균 반환시간이 달라진다. (효율 ↓)
2.2 SJF(Shortest Job First)
- 비선점 스케줄링 알고리즘
- 준비 큐에서 기다리는 프로세스 중 실행시간이 제일 짧다고 예상되는 것(실제로는 아닐 수 있음)을 먼저 디스패치
장단점
- 장점
- 일괄처리 환경에서 구현하기 쉽다.
- 단점
- 실행예정시간이 사용자의 추정치에 의존하기 때문에 실제로 먼저 처리할 작업의 CPU 시간을 알기 어렵다.
2.3 SRT(Shortest Remaining Time)
- 선점 스케줄링 알고리즘
- 실행이 끝날때까지 남은 예상 시간이 가장 짧은 프로세스를 먼저 디스패치
장단점
- 장점
- SJF보다 평균대기시간과 평균반환시간에서 효율적이다.
- 대화형 운영체제에 유용하다.
- 단점
- 각 프로세스의 실행시간을 추적해야 하고 선점을 위한 문맥교환이 일어나기 때문에 SJF보다 오버헤드가 크다.
2.4 RR(Round Robin)
- 선점 스케줄링 알고리즘
- 준비 큐에 도작한 순서대로 디스패치하고 정해진 시간 할당량에 의해 실행을 제한한다.
- 시간 할당량 안에 끝내지 못하면 준비 큐의 맨 뒤에 배치된다.
장단점
- 장점
- CPU를 독점하지 않고 공평하게 이용한다.
- 대화형 운영체제에 유용하다.
- 단점
- 시간 할당량이 너무 크면 FCFS 스케줄링과 같아진다
- 반대로 너무 작으면 문맥교환에 따른 오버헤드가 크게 증가한다.
2.5 HRN(Highest Response Ratio Next)
- 비선점 스케줄링 알고리즘
- 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
응답비율 = 대기시간/예상실행시간 + 1- 응답비율은 예상 실행시간에 반비례하고 대기시간에 비례한다.
장점
- SJF의 단점 보완
2.6 다단계 피드백 큐(Multilevel Feedback Queue)
- 선점 스케줄링 알고리즘
- I/O 중심 프로세스와 CPU 중심 프로세스 특성에 따라 서로 다른 시간 할당량을 부여한다.
- n개의 단계를 가지고 각 단계마다 하나의 큐가 존재한다.
- 단계가 커질수록 시간 할당량도 커진다.
스케줄링 방법
- 새로운 프로세스는 단계 1의 큐에서 FIFO(First In First Out) 순서에 따라 CPU를 점유한다.
- 입출력 이벤트가 발생하면 CPU를 양보하고 대기상태로 갔다가 다시 준비상태가 될때는 현재와 동일한 단계의 큐에 배치된다.
- 시간 할당량을 다 쓰고 작업을 못마친 경우에는 다음 단계의 큐로 이동해 배치된다.
- 마지막 단계에서는 RR 스케줄링 방식으로 동작한다.
- 단계 k의 큐에 있는 프로세스가 CPU를 할당 받으려면 단계 1부터 단계 k-1까지 모든 큐가 비어있어야 한다.
장점
- I/O 위주의 프로세스는 높은 우선권을 유지한다.
- 연산 위주의 CPU 중심 프로세스는 낮은 우선권에 긴 시간 할당량을 가진다.
적응적 다단계 피드백 큐 스케줄링
- 시간 할당량을 다 쓰기 전에 CPU를 반납하면 한단계 전의 큐로 이동해 배치된다.
- 연산 위주의 프로세스가 I/O 위주로 바뀌면 점점 작은 단계로 배치될 수 있다.
3 스케줄링 알고리즘 관계도
