CPU Scheduling: Concepts and Dispatcher

Basic Concepts

• Multiprogramming helps in achieving maximum CPU utilization.
• The CPU–I/O Burst Cycle dictates that process execution comprises a cycle of CPU execution and I/O wait.
• A CPU burst gets followed by an I/O burst.
• The CPU burst distribution is a central concern.

CPU Scheduler

• Short-term scheduler picks processes from the ready queue, allocating the CPU
• The queue can be ordered in various ways
• CPU scheduling decisions occur when a process switches from:
• Running to waiting state
• Running to ready state
• Waiting to ready state
• Termination
• Nonpreemptive scheduling applies under conditions 1 and 4.
• Preemptive scheduling encompasses all other scheduling scenarios.
• Preemptive scheduling should consider access to shared data, preemption in kernel mode and interrupts during critical OS activities.

Dispatcher

• The dispatcher module grants CPU control to a process chosen by the short-term scheduler, involving:
• Switching context
• Switching to user mode
• Jumping to the user program's proper location to restart
• Dispatch latency refers to the time the dispatcher takes to halt one process and initiate another.

Scheduling Criteria

• CPU utilization should be maximized.
• Throughput is the number of processes completing execution per unit of time.
• Turnaround time measures the time to execute a process.
• Waiting time represents the time a process waits in the ready queue.
• Response time is the time from request submission until the first response, not output, in a time-sharing environment.

Scheduling Algorithm Optimization Criteria

• Maximize CPU Utilization
• Maximize Throughput
• Minimize Turnaround time
• Minimize Waiting time
• Minimize Response time

First-Come, First-Served (FCFS) Scheduling

• Processes arriving in the order P1, P2, P3 have burst times of 24, 3, and 3, respectively.
• With FCFS, the Gantt Chart shows P1 executing first, then P2, concluding with P3.
• The waiting time for P1 = 0, P2 = 24, P3 = 27.
• Average waiting time equals 17.
• When processes arrive in the order P2, P3, P1 with the Gantt chart showing P2, then P3, and lastly P1.
• Waiting times are P1 = 6, P2 = 0, P3 = 3 resulting in an average waiting time of 3, which is better than the previous case.
• The convoy effect describes a short process stuck behind a long process.
• Consider one CPU-bound process and several I/O-bound processes.

Shortest-Job-First (SJF) Scheduling

• Each process is associated with its next CPU burst length.
• These lengths schedule processes with the shortest time.
• SJF is optimal because it gives the minimum average waiting time for a given set of processes.
• Knowing the next CPU request length poses a challenge.
• It could be gotten from the user

Determining Length of Next CPU Burst

• Estimation of the length is done because it should be similar to the previous one.

• The process is picked with the shortest predicted CPU burst.

• This estimation estimates the length of previous CPU bursts, using exponential averaging.

• Formula variables are:

  • 𝑡𝑛 = actual length of 𝑛th CPU burst
  • 𝜏𝑛+1 = predicted value for the next CPU burst
  • 𝛼, where 0 ≤ 𝛼 ≤ 1
  • Definition: 〖𝜏〗_(𝑛+1)=𝛼𝑡_𝑛+(1−𝛼) 𝜏_𝑛

• Commonly, 𝛼 is set to ½.

• The preemptive version gets called the shortest-remaining-time-first

Priority Scheduling

• Each process associates with a priority number, an integer
• The CPU assigns the process with the highest piriorty, the smallest integer is the highest priority
• Preemptive
• Nonpreemptive
• SJF scheduling where priority is the inverse of predicted next CPU burst time.
• The problem is Starvation, where low priority processes may never get to execute.
• The solution is Aging, where time progresses so the priority of the process increases.

Round Robin (RR)

• Each process receives a small unit of CPU time known as a time quantum, usually 10-100 milliseconds.
• After the specified time, the process is preempted and then added to the ready queue's end.
• In a ready queue of n processes with a time quantum of q, every process obtains 1/n of the CPU time in q time unit chunks at once.
• No process waits for more than (n-1)q time units.
• Timer interrupts every quantum to schedule the next process.
• performance varies on quantum size.
• Large quantum become FIFO
• Small quantum should be relative so context switch or overhead is too high

Multilevel Queue

• The ready queue partitions into separate queues, such as foreground (interactive) and background (batch) queues.
• A process exists permanently in a given queue.
• Each queue uses its own scheduling algorithm:
• RR for the forground
• FCFS for the background
• Scheduling must happen between queues with:
• Fixed priority scheduling where all from foreground served from background, can cause starvation
• Time slice where each queue is reserved specific amounts of CPU time. I.e 80% foreground in RR, or 20% background in FCFS.

Multilevel Feedback Queue

• A process may transition between various queues, enabling the implementation of aging.
• It defines the scheduler by parameters, such as
• Number of queues
• Scheduling algorithms for each queue
• Method used to determine when to upgrade a process
• Method used to determine when to demote a process
• Method used to determine which queue a process enters when it needs service.

Thread Scheduling

• User-level and kernel-level threads are differentiated.
• Threads get scheduled, not processes, when threads are supported.
• Thread libraries schedule user-level threads on LWP with many-to-one and many-to-many models.
• Process-contention scope (PCS) is known for scheduling contention within the process.
• Programmer sets priority.
• Kernel threads scheduled on available CPU have system-contention scope (SCS), which includes competition among all threads in the system.

Pthread Scheduling

• The API allows specifying either PCS or SCS during thread creation.
• PTHREAD_SCOPE_PROCESS schedules threads using PCS scheduling.
• PTHREAD_SCOPE_SYSTEM schedules threads using SCS scheduling.
• Can be limited by OS – Linux and Mac OS X only allow PTHREAD_SCOPE_SYSTEM.

Multiple-Processor Scheduling

• CPU scheduling becomes intricate with multiple CPUs.
• Homogeneous processors exist within a multiprocessor system.
• Asymmetric multiprocessing sees only one processor accessing system data structures, reducing data sharing needs.
• Symmetric multiprocessing (SMP) means each processor self-schedules processes in a common ready queue or owns a private ready queue,which is common.
• The Processor displays affinity to the processor on which it is currently running.
  • Soft affinity
  • Hard affinity
  • Variations including processor sets

Multiple-Processor Scheduling – Load Balancing

• For effective SMP, maintain efficiency and load CPUs adequately.
• Load balancing strives for equitable workload distribution.
• Push migration is a periodic task checking processor load and shifting tasks from an overloaded CPU to others.
• Pull migration involves idle processors pulling waiting tasks from a busy processor.

Multicore Processors

• Recent trends place multiple processor cores on a physical chip.
• Faster and consumes less power.
• Multiple threads per core occurs.
• Uses memory stall to advance another thread while memory retrieve happens.

Real-Time CPU Scheduling

• presents challenges.
• Soft real-time systems provide no guarantees when to schedule a critical real-time process
• Hard real-time systems need the task to be serviced by its deadline.
• Two types of latencies affect performance which are:
• Interrupt latency, which is the time from interrupt arrival to the start of a routine.
• Dispatch latency, which is the time used by the scheduler to take current process off CPU and switch to another.

Priority-Based Scheduling

• Scheduler must support preemptive, priority-based scheduling for real-time
  • Only guarantees soft real-time
• The scheduler must assist meet deadlines for hard real-time
• Process have new characteristics, which is periodic and requires CPU at consistent intervals, such as:
  • Processing time t, deadline d, period p
  • 0 ≤ t ≤ d ≤ p
  • Rate of periodic task is 1/p

Virtualization and Scheduling

• Virtualization software schedules multiple gusts onto the CPU(s)
• Each guest does its own scheduling not knowing that it doesn't own the CPUs
• This may result in poor response time or effect the time-of-day cloacks in the quests
• This can undo good scheduling algorithm efforts of quests

Rate Montonic Scheduling

• A priority is assigned based on the inverse of its period
• Short periods = higher priority;
• Longer periods = lower priority
• P1 is assigned a higher priority than P2.

Earliest Deadline First (EDF) Scheduling

• Priorities are assigned according to the deadlines.
• The higher of the prioritites: the earlier the deadline
• The lewer of the priorities: the later the deadline

Proportional Share Scheduling

• T shares are allocated amongst processes in the system.
• An application gets N shares, where N < T
• This ensures the application receives N / T of the total processor time

POSIX Real-Time Scheduling

• POSIX.1b represents the standard.
• The API offers functions for overseeing real-time threads.
• It defines a few organizing classes for real-time threads:
• SCHED_FIFO schedules threads using a FCFS strategy with a FIFO queue and has no time-slicing for threads of equal priority.
• SCHED_RR has similarities to SCHED_FIFO but time-slicing occurs for the threads that are of equal priority.
• A couple of functions get defined for gaining and setting scheduling policy:
  • pthread_attr_getsched_policy(pthread_attr_t *attr, int *policy)
  • pthread_attr_setsched_policy(pthread_attr_t *attr, int policy)

Linux Scheduling through Version 2.5

• Prior to version 2.5, the kernel ran a variation of the UNIX scheduling algorithm
• Version 2.5 now has a new time of O(1) scheduling using: -Preemptive, priority based
• Two priority ranges: time-sharing and real-time
• Real-time rangers from 0 to 99 and a "nice" value from 100 to 140
• Mapped into global with numerically priority with numerically lower values indication higher priority
• Higher priority gets larger q
• Task can run-able if the time is left in its slice (active)
• If their is not time left (expired), then not run-able until all other tasks use their slices
• All run-able tasks are tracked in per-CPU runqueue data structure using:
  • Two priority arrays (active, expired)
  • Tasks are indexed by priority
  • Arrays are exchanged when no more active
• Worked fine but poor response times for interactive processes

Linux Scheduling in Version 2.6.23 +

• There is a Completely Fair Scheduler (CFS).
• For scheduling there are classes
• Each has specific priority
• Scheduler picks highest priority class in highest scheduling classses
• Rater than based fixed time allotments, time is based on proportion of CPU
• This has 2 scheduling addable classes as so:
• default
• real-time
• Quantum gets calculate based on "nice" value from -20 to +19
• A lower value has a higher priority
• Calculates targer latency: time of interval during the task at least once
• Target latency can increase if saying the number of active tasks increases
• The CFS scheduler maintains task with its virtual run time in variable vruntime
• decay factor based on priority. This allows lower priority to have higher decay rate
• Has a normal default priority and yields a virtual run time = actual run time
• To decide the next task to run, scheduler picks task with lowest virtual run time

Windows Scheduling

• Uses priority-based preemptive scheduling
• Highest-priority thread is runs
• The dispatcher is scheduler
• Thred runs until blocks, uses time slice, or is has been preempted by ahigher-priority thread
• Real-time threads get to preempt non-real-time ones
• Their is a 32-level priority scheme
• Variable class goes from 1-15, where real-time class goes from 16 - 31
• Priority 0 is the meomory management thread
• Has a queue per each priority
• If no run-able thread runs idle

Windows Priority Classes

• The Win32 API identifies several priority classes to which a process can belong:
• REALTIME_PRIORITY_CLASS, HIGH_PRIORITY_CLASS
• ABOVE_NORMAL_PRIORITY_CLASS,NORMAL_PRIORITY_CLASS
• BELOW_NORMAL_PRIORITY_CLASS, IDLE_PRIORITY_CLASS
• All are variable except REALTIME
• A thread can have in a given class with relative priority as:
• TIME_CRITICAL, HIGHEST, ABOVE_NORMAL, NORMAL, BELOW_NORMAL, LOWEST, IDLE
• Priority and class with the relative give numeric priority
• has a base priority, where it is normal within the class.
• If quantum expires, the priority is lowered, never below the base.

Evaluation for Deterministic evaluation

• For each algorithm, minimum average waiting time gets calculated
• Is simple and fats, but requires exact numbers for input and applies only to those inputs
• FCS is 28ms
• Non-preemptive SFJ is 13ms
• RR is 23ms

Queueing Models

• Describes processes arrival and the CPU and I/O bursts probabilistically
• Commonly exponential and described by range
• Computes average throughput, utilization, waiting time, etc
• Describes the computer system as network of servers, each is a queue waiting processes
• knowing rates of arrivals and services
• Can computes utilization, average queue length, average wait time, and others

Little’s Formula

• Has different variables, where
• n is the average queue length λ is the average arrival rate into queue W is the average waiting time in queue
• In a steady state, processes must equal the amount arriving equal: n = λ x W
• This can vary when distribution is algorithm and arrival distribution
• The following example shows if the process goes at 7 averages and has 14 processes queue then it takes 2 seconds per process

Simulations

• Simulation of cueing can be limited
• Programmed is better in models such as:
• Programmed model of computer system
• Clock is a variable
• Statistics gathered that indicates algorithm performance
• There are different variables:
  • Random number generator based on possibilities
  • Distributions as mathematically define or empirically
  • Has trace tapes,which is a recorded sequence of real events in systems

Implementation

• Accurancy is bad in simulations
• Just implement new scheduler and test in real systems
  • High cost, high risk
  • Environments change
• Flexible schedulers exist
• Flexible changed can modify the priorities
• Enviorments are varied