Scheduling

Sheduling policy = discipline

Workload Assumptions

let us first make a number of simplifying assumptions about the processes running in the system, sometimes collectively called the workload.

• Assumptions are:
  1. Each job runs for the same amount of time.
  2. All jobs arrive at the same time.
  3. Once started, each job runs to completion.
  4. All jobs only use the CPU (i.e., they perform no I/O)
  5. The run-time of each job is known.

Scheduling Metric

• Turnaround time = Completion - Arrival.

  • Since we assume that all jobs arrive at the same time, T_Arrival = 0. Therefore, turnaround time = completion time.

• Fariness: Performane and fairness are often at odds in scheduling.

• FIFO

  • Convoy Effect: Short-time required process waits for the long-time process to be completed.

• Shorted Job First

  • Same convoy effect possible as the process (jobs) might be arrived differently; the shortest job arrives at the last, hence still need to wait.

• Shortest Time to Completion First (STCF)

  • Compare the remainer completion time whenever new job arrives, and pick the shortest one.
  • It is non-preemptive that the job can be stopped in the middle.

New scheduling metric: response time

Response Time = Firstrun - Arrival = Time gap between arrival and first run of job.
Can intuitively knows the policy such as STCF, FIFO has bad response time.

• Round Robin
  • Time slice/Scheduling quantum –> slice must be multiples of interrupt period.
  • If time slice too short –> context switch costs becomes significant.
  • In general, the fair policy like Round Robin do bad when the metric is turnaround time.

Incorporating IO

During the IO process, the current process will not use the CPU and in the wait state.
To avoid the waste of resource, scheduler utilizes the resource executing the other waiting jobs.