COMP3891

Scheduler

Overview

Schedule is responsible for deciding which ready process to run next.

IO Bound + CPU Bound

IO-bound process:

• Spends most of its time waiting for IO to complete.
  • Small bursts of CPU to process IO and request next IO.

CPU-bound process:

• Spends most of its time computing.
• Time to completion largely determined by received CPU time.

We need a mix of CPU-bound and IO-bound processes to keep both CPU and IO systems busy.

Processes can go from CPU to IO bound (or vice versa) in different phases of execution.

Improving Responsiveness

• Running IO-bound process delays CPU-bound process by very little.
• Running CPU-bound process prior to an IO bound process delays the next IO request significantly.
  • No overlap of IO waiting with computation.
  • Results in device not as busy as possible.
• Favour IO-bound processes over CPU-bound processes.

When Is Scheduling Performed

• A new process.
  • Run the parent or the child.
• A process exits.
  • Who runs next?
• A process waits for IO.
  • Who runs next?
• A process blocks on a lock.
  • Who runs next? The lock holder?
• An IO interrupt occurs.
  • Who do we resume, the interrupted process or the process that was waiting?
• On a timer interrupt.

Goals of Scheduling Algorithms

• Fairness:
  • Give each process a fair share of the CPU.
• Policy enforcement:
  • What ever policy chosen, the scheduler should ensure it is carried out.
• Balance/Efficiency:
  • Try to keep all parts of the system busy.

Round Robin Scheduling

Round Robin scheduling is used in interactive scheduling.

• Each process is given a timeslice to run in.
• When the timeslice expires, the next process preempts the current process, and runs for its timeslice, and so on.
  • Preempted process is placed at end of queue.
• Implemented with:
  • A ready queue.
  • A regular timer interrupt.

Pros:

• Fair, easy to implement. Cons:
• Assumes all processes are equal.

Timeslice Considerations

Too short:

• Waste a lot of time switching between processes.

Too long:

• System is not responsive.

Priority-Based Scheduling

• Each process (or thread) is associated with a priority.
• Provides basic mechanism to influence scheduler decision.
  • Scheduler will always pick higher priority.
• Priorities can be defined internally or externally.
  • Internal: IO bound or CPU bound.
  • External: importance to user.
• Implemented with multiple queues for each priority, each having its own round robin.

Unix Scheduler

Two-level scheduler:

• High-level scheduler schedules processes between memory and disk.
• Low-level scheduler is CPU scheduler.
  • Based on multi-level queue structure with round robin at each level.

Priority Recalculations

Highest priority is scheduled.

• Priorities are recalculated once per second, and reinserted in appropriate queue.
  • Avoid starvation of low priority threads.
  • Penalise CPU-bound threads.

Priority = CPU_usage + nice + base (lower is higher priority).

• CPU_usage = number of clock ticks.
  • A process that spends a lot of CPU time is penalised.
  • This decays over time so that CPU bound background jobs do not suffer starvation.
• Base is a set of hardwired, negative values used to boost priority of IO bound system activities.

Multiprocessor Scheduling

Single Shared Ready Queue

Pros:

• Simple.
• Automatic load balancing.

Cons:

• Lock contention on ready queue can be a major bottleneck.
  • Due to frequent scheduling or many CPUs or both.
• Not all CPUs are equal.
  • Last CPU a process ran on is likely to have more related entries in the cache.

Affinity Scheduling

Affinity scheduling tries to run a process on the CPU it ran on last time.

Mutliple Queue SMP Scheduling.

• Each CPU has its own ready queue.
• Coarse-grained algorithm assigns processes to CPUs.
  • Defines their affinity, and roughly balances the load.
• Bottom-level fine-grained scheduler:
  • Is the frequently invoked scheduler (on blocking on IO, a lock, or exhausting a timeslice).
  • Runs on each CPU and selects from its own ready queue.
    • Ensures affinity.
  • If nothing is available from the local ready queue, it runs a process from another CPU’s ready queue rather than go ideal.
    • Work stealing.

Pros:

• No lock contention on per-CPU ready queues in the common case.
• Load balancing to avoid idle queues.
• Automatic affinity to a single CPU for more cache friendly behaviour.