Scheduling Policy (discipline)
• Workload Assumption
- 모든 작업시간은 동일
- 모든 작업은 동시에 도착
- 각 작업은 시작되면 완료될 때까지 실행됨
- 모든 작업은 CPU만 사용 (입출력 수행 X)
- 각 작업의 실행시간을 알고 있음
• Scheduling Metrics
» Turnaround time (반환시간)
반환시간은 성능 측면에서의 평가기준
Tturnaround = Tcompletion - Tarrival
이때, 모든 작업은 동시에 도착한다고 가정했으므로
Tturnaround = 0∴ Tturnaround = Tcompletion (추후 가정을 수정)
» Fairness (공정성)
Scheduling에 있어서 성능과 공정성은 서로 상충되는 목표
Jain's Fairness Index등에 의해 평가가능
(서적 The Art of Computer Systems Performance Analysis, Raj Jain 참고)
» Response time (응답시간)
시스템이 상호작용을 원활히 하기 위한 성능
작업이 도착할 때부터 처음 스케줄 될 때까지 걸리는 시간
Tresponse = Tfirstrun - Tarrival
아래의 STCF류의 정책들은 반환시간은 훌륭하지만, 응답 시간과 상호작용 측면은 안좋은 방법이다.
• FIFO (First in, First out)
FIFO(First in, First out), FCFS(First come, First served)
» Covey effect
위 그림과 같이 실행시간이 짧은 프로세스들이 긴 실행시간의 프로세스 종료를 기다리는 현상
평균 반환 시간을 악화시킨다.
• SJF (Shortest Job First)
가정 2 '모든 작업은 동시에 도착' 이 없다면 아래와 같은 문제가 발생
• STCF (Shortest Time-to-Completion First)
STCF (Shortest Time-to-Completion First), PSJF(Preemtive Shortest Job First)
SJF의 문제를 해결하기 위해 가정 3 '각 작업은 시작되면 완료될 때까지 실행됨'을 완화
시스템에 새로운 프로세스가 들어오면 스케줄러는 남은 작업과 새로운 작업 중 남은 실행시간이 제일 적은 프로세스를 스케줄한다.
반환 시간은 훌륭하지만 응답시간은 안좋다.
» Preemptive Scheduler
Preemtive Scheduler
각 작업이 종료될 때까지 계속 실행
Non-preemptive Scheduler
다른 프로세스 실행을 위해 필요하면 문맥교환을 수행하며, 현재 프로세스를 중단, 다른 프로세스를 재개 또는 시작함
• RR(Round-Robin) Scheduling
RR(Round-Robin) Scheduling, Time slicing
일정시간 동안 실행 후 실행 큐의 다음 작업으로 전환
작업이 실행되는 시간을 time slice 또는 scheduling quantum이라고 함
RR과 같이 공정한 policy, 작은 시간단위로 모든 프로세스에게 CPU를 분배하는 정책은 반환시간 같은 평가기준에선 성능이 나쁘다.
» Time slice
time slice는 타이머 인터럽트 주기의 배수여야 함
time slice가 짧아지면 RR의 응답시간은 좋아지지만, 너무 짧아지면 문맥 교환 비용이 전체 성능에 미치는 영향이 커짐
문맥교환 비용을 상쇄할 수 있을만큼 길어야하지만, 너무 길면 안 된다.
• I/O 작업을 고려
시스템 활용도 즉, 전반적인 사용성과 효율성을 향상 하기위해선 연산을 중첩되게 실행해야 함
» 효율성
입출력 작업을 요청 시, 실행중인 프로세스는 입출력 완료까지 CPU를 사용하지 않음
효율성을 위해 스케줄러는 다음에 할 작업을 결정해야함
» 사용성
또한, 각각의 cpu burst를 독립된 하나의 작업으로 간주하면 스케줄러는 대화형 프로세스 (interactive process)가 더 자주, 유리하게 실행되는것을 보장함
Related Knowledge
• Workload
시스템에서 작동중인 프로세스들, 프로세스들이 하는 작업들의 특징(소요시간, I/O호출)등을 총칭
.jpg)