Process Scheduling 1

Types of Process Scheduling

1. Long-term scheduling (job scheduler) : determines which programs are admitted to the system for processing
2. Medium-term scheduling (swapper) : the decision to add to the number of processes that are partially or fully in main memory
3. Short-term scheduling (CPU scheduler) : the decision as to which available process will be executed by the processor
4. I/O scheduling

 

Scheduling Algorithms

Scheduling Algorithms

• Selection function : determines which process, among ready processes, is selected next for execution
  • $w$ : time spent in system so far
  • $e$ : time spent in execution so far
  • $s$ : total service time required by the process (CPU burst time)
• Decision mode
  • Non-preemptive
  • Preemptive

 

First In, First Out; FIFO

• Selection Function : $Max[w]$ (가장 오래된 Process 선택)
• Decision mode : non-preemption
• Advantage : simplest scheduling policy
• Disadvantage
  • Performs much better for long processess than short ones
  • May suffer from the convoy effect (short process behind long process) -> Lower CPU utilization

Example of convoy effect

 

Shortest Process Next; SPN

• Selection function : $Min[s]$ (CPU burst time; Service time이 최소인 Process 선택)
• Decision mode : preemption (Shortest Remaining Time) or non-preemption
• Advantage 
  • Optimal : gives minimum average waiting time
  • Overall performance is significantly improved in terms of turnaround time
• Disadvantage
  • Possibility of starvation for longer processes
  • Impractical : need to estimate the length of the next CPU burst time

• use exponential averaging based on the length of previous CPU burst

Pseudo code of the exponential averaging

 

Shortest Remaining Time; SRT

• A preemptive version of SPN (SFJ)
• Selection function : $Min[s \ - \ e]$
• Decision mode : preemption
• Advantage : give superior turnaround time performance to SPN
• Disadvantage
  • Overhead can be high
  • Starvation may be possible

 

Round Robin; RR

• When time quantum is expired, change process
• Selection function : constant, the next ready job is selected on a FCFS basis
• Decision mode : preemption
• The principle design issue is the length of the time quantum

 

Highest Response Ratio Next; HRRN

• Response ratio : the ratio of turnaround time to actual service time (CPU burst time) $$ R \ = \ (Turnaround \ time; \ Waiting \ time \ + \ CPU \ burst \ time) \ / \ CPU \ burst \ time$$
• Selection function : $Max[(q \ + \ s) \ / \ s]$
• Decision mode : non-preemption
• Advantage : $(1 \ + \ q \ / \ s)$, $q$가 클수록 높은 priority를 부여하여 starvation을 해결
• Disadvantage : 여전히 $s$를 사용함; The expected service time must be estimated