Carpe Diem

* First-Come-First-Served(FCFS)

- 비선점형(Non-preemptive)

- 가장 단순한 형태의 스케줄링 정책이며, FIFO(First-Input-First-Output)라고도 불린다.

- 짧은 프로세스보다는 긴 프로세스에 유리하다.

* Round-Robin(RR)

- 선점형(Preemptive)

- 시간 할당량(Time Slicing 또는 Time Quantum) 기법

- 모든 프로세스는 한 번에 정해진 시간 조각만큼만 실행 한 후 강제적으로 CPU를 빼앗는다.

* Shortest Process Next(SPN)

- 비선점형(Non-preemptive)

- 가장 짧은 프로세스를 먼저 수행

- 구현 불가능(각 프로세스가 요구하는 총 실행시간을 미리 알아야 함)

* Shortest Remaining Time(SRT)

- 선점형(Preemptive)

- 예상되는 남아 있는 실행시간이 가장 짧은 프로세스가 선택

* Highest Response Ratio Next(HRRN)

- 비선점형(Non-preemptive)

- 반환 시간(TAT) : 프로세스가 시스템에 진입한 후 대기한 시간과 실행한 시간을 모두 합쳐 결국 시스템 내에서 머문 총 시간을 의미한다.

실제 서비스 시간 대비 반환시간의 비율을 나타낸다.

- R(응답 비율) = ( time spent waiting(처리기를 기다리며 대기한 시간) + expected service time(예상되는 서비스 시간) ) / expected service time(예상되는 서비스 시간)

- 대기시간이 길어지면 R값이 커지기 때문에 스케줄러에게 보상 받는다.

- 계산시간이 복잡하고 증가면 이 알고지름의 시간 복잡성이 증가하여 오버헤드가 발생할 가능성이 크기 때문에 고려해야한다.

* 스케줄링 정책들의 비교 분석 *

<FCFS>

<RR q=1>

<RR q=4>

<SPN>

<SRT>

<HRRN>

<Feedback>

Chapter 9. Uniprocessor Scheduling

* 스케줄링의 목적

- 처리기가 다음에 실행할 프로세스를 선택하는 것

- 응답시간(Response time)

- 처리량(Throughput)

- 효율성(Processor efficiency)

* 스케줄링의 종류

- 장기 스케줄링(Long-Term Scheduling)

· 프로세스를 시스템으로 집입시킬지 여부를 결정

· 다중프로그래밍의 정도를 제어하는 역할

- 중기 스케줄링(Medium-Term Scheduling)

- 단기 스케줄링(Short-Term Scheduling)

· 디스패처(Dispatcher)

· CPU에 의해 실행될 다음 번 프로세스로 어떤 프로세스를 선택할지를 결정

· 자주 실행됨

* 단기 스케줄링 평가 기준들

· 사용자 중심의 성능 관련 평가 척도

- 반환 시간(Turnaround Time): 프로세스가 시스템으로 진입한 후부터 종료할 때까지 걸린 시간

- 응답시간(Response Time): 프로세스가 시스템에 요구를 한 후 이에 대한 시스템으로부터의 첫 번째 응답이 올 때까지의 시간

- 완료 기한(Deadline): 프로세스가 완료 되어야 하는 시점

· 사용자 중심의 기타 평가 척도

- 예측가능성(Predictability): 같은 작업이라면 실행 될 때마다 동일한 기간 동안 실행되어야 하고, 시스템의 부하 정도에 상관없이 동일한 비용으로 실행되어야 한다. 만일 실행할 때 마다 지나치게 차이가 난다면, 사용자들은 시스템을 신뢰하지 못하게 될 것이다.

· 시스템 중심의 성능 관련 평가 척도

- 처리량(Throughput): 단위시간 내에 실행을 완료 시킬 수 있는 프로세스의 수

- 처리 이용률(Processor utilization): 전체 시간 중에 처리기가 바쁘게 실행을 한 시간의 비율

· 시스템 중심의 기타 평가 척도

- 공정성(Fairness):

- 우선순위 부여(Enforcing Priority):

- 균형있는 자원 활용(Balancing Resources):

*　우선순위(Priorities)

- 스케줄러는 항상 높은 우선순위의 프로세스를 선택

- 문제점: 순수 우선순위 기반 스케줄링 방식에서 높은 우선순위의 프로세스가 계속적으로 생성되고 낮은 우선순위의 프로세스가 계속 CPU를 할당 받지 못해 기아(Starvation) 발생

* 결정 모드

- 비선점(Non-preemptive)

· 프로세스가 일단 실행 상태(Running State)에 진입하면 종료되거나 자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않는다.

- 선점(Preemptive)

· 현재 실행 중인 프로세스라고 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동된다.

· CPU를 빼앗을 수 있다.