반응형
스케줄링 성능 평가 기준
- 스케줄링 알고리즘의 성능을 평가하는 데 평균 대기시간과 평균 반환시간이 이용된다.
- 평균 대기시간 : 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균값
- 평균 반환시간 : 각 프로세스가 생성된 시점부터 수행 완료된 시점까지의 소요시간의 평균값
FCFS(First-Come First-Served) 스케줄링
- 먼저 들어온 순서대로 나간다.
- 큐를 활용하는 스케줄링이며 가장 단순한 방법이다.
- FCFS 스케줄링은 비선점 방법이다.
- 프로세스는 준비 큐에 도착한 순서에 따라 디스패치 된다.
- 단점
- FCFS 스케줄링 알고리즘은 겉보기엔 공정하지만, 짧은 작업이 긴 작업을 기다리게 되거나 중요한 프로세스가 나중에 수행될 수 있는 등의 단점이 존재한다. → 대화식 시스템에는 적합하지 않다.
- 도착 순서에 따라 평균 반환시간이 크게 변한다.
- FCFS 스케줄링은 단독적으로 사용하지 않고 주로 다른 방법과 결합하여 사용되고 있다.
SJF(Shortest Job First) 스케줄링
- 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 프로세스를 먼저 디스패치하여 실행한다.
- 비선점 방식이다.
- 일괄처리 환경에서 구현하기 쉬운 알고리즘이며 실행할 프로세스의 CPU 소요시간이 미리 주어진다.
- 단점
- 실행 예정 시간의 길이를 사용자의 추정치에 의존한다. → 실제로는 먼저 처리할 작업의 CPU 시간을 예상할 수 없음.
- 대화형 시스템에서는 사용되지 않는다.
SRT(Shortest Remaining Time) 스케줄링
- SJF의 선점 알고리즘 버전
- 새로 들어온 프로세스를 포함하여 실행이 끝날 때까지 남은 시간의 추정치가 가장 짧은 프로세스를 먼저 디스패치하여 실행한다.
- 대화형 운영체제에 유용하다.
- SJF보다 평균 대기시간이나 평균 반환시간에서 더 효율적이다.
- 단점
- 선점을 위한 문맥 교환도 해야하므로 SJF보다 오버헤드가 크다. (사실 선점형 알고리즘은 모두 이 문제를 가지고 있다.)
- SRT가 빠르긴 하지만, 일반적인 운영체제에서는 그러한 장점이 문맥 교환하는 시간으로 장점이 사라지게 되어 SRT와 SJF의 정확한 비교는 문맥 교환에 요구되는 시간을 고려하여 평가해야 한다.
RR(Round Robin) 스케줄링
- RR 스케줄링은 대화형 시스템에서 사용된다.
- 선점 스케줄링 방식이다.
- 프로세스가 도착한 순서대로 프로세스를 디스패치 하지만, 정해진 시간 할당량에 의해 실행을 제한한다.
- 즉 시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 한다.
- CPU를 독점하지 않고 공평하게 사용할 수 있게 된다.
- 성능은 평균 CPU 소요시간에 대한 시간 간격의 길이에 따라 달라진다.
- 간격이 너무 큰 경우 : FCFS 정도로 성능이 낮아짐
- 간격이 너무 좁은 경우 : 잦은 문맥 교환이 작업 수행을 방해하여 오버헤드가 크게 증가
- 가장 적절한 시간 간격은 시스템 형태에 달려있다.
- 대화형 환경에서 사용자가 간단한 요청을 한 경우라면 시스템은 빠른 응답시간을 요구한다.
- 일괄처리 시스템이라면 응답시간은 중요하지 않고 오버헤드가 중요한 요인이 된다.
- 적절한 시간을 결정하는 일반적인 두 가지 규칙
- 80%의 CPU 사이클을 처리할 수 있도록 한다.
- 한 번의 문맥 교환에 걸리는 시간보다 100배 정도는 길어야 한다.
HRN(== HRRN, Highest Response Ratio Next) 스케줄링
- 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치하여 실행한다.
- 비선점 스케줄링 알고리즘이다.
- 예상 실행시간이 짧을수록, 대기시간이 길수록 응답비율이 커진다.
- SJF 스케줄링의 단점을 보완한 스케줄링 알고리즘이다.
- SJF에서는 예상 실행 시간이 긴 프로세스가 먼저 들어왔더라도 이후에 실행시간이 짧은 프로세스가 계속해서 들어오면 우선순위에서 계속 밀리지만, HRN 스케줄링은 실행시간이 긴 프로세스라 하더라도 대기시간이 길어지면 응답비율도 커져서 자기보다 실행시간이 짧은 프로세스가 들어오더라도 우선순위에서 밀리지 않을 수 있다.
다단계 피드백 큐 스케줄링
- 선점 스케줄링 방식이다.
- 입출력 중심인 프로세스와 CPU 중심인 프로세스의 특성에 따라 서로 다른 시간 할당량을 부여한다.
- n개의 단계가 있는 경우, 각 단계마다 하나씩의 큐가 존재한다.
- 단계 k는 단계k+1에 피드백을 주며, 단계가 커질수록 시간 할당량은 커지는 형태로 구성된다.
- 단계 1의 큐에 들어간 후 큐에 도착한 순서대로 프로세스들이 처리되다가 자신의 차례가 되면 해당 프로세스는 디스패치되어 단계 1의 시간 할당량만큼 실행된다.
- 할당량보다 짧은 시간에 프로세스가 끝나면 완료가 되고, 입출력 같은 이벤트가 발생하면 CPU를 양보하고 대기상태로 갔다가 다시 준비상태가 될 때에는 현재와 동일한 단계의 큐에 배치된다.
- 시간 할당량을 다 썼지만 프로세스가 종료되지 못했다면 다음 단계의 큐로 이동된다.
- 각 단계는 RR 로빈 스케줄링 방식으로 동작한다.
- 단계 k의 큐에 있는 프로세스가 CPU를 할당받으려면 단계 1부터 단계 k-1까지 모든 큐가 비어 있어야 한다.
- 단계가 커질수록 CPU를 할당받는 빈도는 줄어들 수 있다.
- 대신 단계가 커질수록 시간 할당량도 커지므로, 단계가 커질수록 한 번 CPU를 할당받으면 더 오랜 시간을 실행할 수 있다.
- 결국 연산 위주의 프로세스는 점점 단계가 커지고, 입출력 위주의 프로세스는 시간 할당량보다 짧은 실행이 유지되어 앞부분의 단계를 유지하게 된다.
- 다단계 피드백 큐 스케줄링의 변형으로 적응적 스케줄링 기법을 적용할 수 있다.
- 프로세스의 유동적 상태 변화에 적응한다는 의미, 기본적으로 동일한 프로세스는 마지막에 있었던 단계의 큐로 배치가 되고 한 번 단계가 커지면 반대로 돌아가진 못하지만, 적응적 기법에서는 시간 할당량을 다 쓰기 전에 CPU를 반납하는 경우 하나 작은 단계의 큐로 되돌아 갈 수 있는 방법을 제공한다.
- 연산 위주의 작업을 하던 프로세스는 큰 단계에 배치, 이후 프로세스의 성격이 입출력 위주로 바뀐다면 점점 작은 단계로 배치될 수 있다.
반응형