CPU Scheduling

Dr. Noman Islam

Introduction

• Scheduling decision takes place when
• When a process switches from the running state to the waiting state (for example, as the result of an I/O request or an invocation of wait() for the termination of a child process)
• When a process switches from the running state to the ready state (for example, when an interrupt occurs)
• When a process switches from the waiting state to the ready state (for example, at completion of I/O)
• When a process terminates

Dispatcher

• The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following:
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program
• The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency.

Criteria

• CPU utilization. We want to keep the CPU as busy as possible
• Throughput. If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput
• Turnaround time. From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.

• Waiting time
• Response time
• It is desirable to maximize CPU utilization and throughput and to minimize turnaround time, waiting time, and response time
• In most cases, we optimize the average measure.
• Investigators have suggested that, for interactive systems (such as desktop systems), it is more important to minimize the variance in the response time than to minimize the average response time. A system with reasonable and predictable response time may be considered more desirable than a system that is faster on the average but is highly variable.

First-Come, First-Served Scheduling

• When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue

​

• The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2, and 27 milliseconds for process P3. Thus, the average waiting time is (0 + 24 + 27)/3 = 17 milliseconds
• If the processes arrive in the order P2, P3, P1 The average waiting time is now (6 + 0 + 3)/3 = 3 milliseconds
• Thus, the average waiting time under an FCFS policy is generally not minimal
• FCFS scheduling algorithm is nonpreemptive.
• Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.
• The FCFS algorithm is thus particularly troublesome for time-sharing systems, where it is important that each user get a share of the CPU at regular intervals

Shortest-Job-First Scheduling

• The waiting time is 3 milliseconds for process P1, 16 milliseconds for process P2, 9milliseconds for process P3, and 0 milliseconds for process P4.
• Thus, the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds

• The real difficulty with the SJF algorithm is knowing the length of the next CPU request.
• The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts
• The SJF algorithm can be either preemptive or nonpreemptive

Priority Scheduling

• Time limits, memory requirements, the number of open files, and the ratio of average I/O burst to average CPU burst have been used in computing priorities.
• External priorities are set by criteria outside the operating system, such as the importance of the process, the type and amount of funds being paid for computer use, the department sponsoring the work, and other, often political, factors.

• Priority scheduling can be either preemptive or nonpreemptive
• A major problem with priority scheduling algorithms is indefinite blocking, or starvation.
• A solution to the problem of indefinite blockage of low-priority processes is aging.
• Aging involves gradually increasing the priority of processes that wait in the system for a long time

Round-Robin Scheduling

• The round-robin (RR) scheduling algorithm is designed especially for timesharing systems
• A small unit of time, called a time quantum or time slice, is defined.
• The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process

​

Multilevel Queue Scheduling

• A multilevel queue scheduling algorithm partitions the ready queue into several separate queues
• The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process priority, or process type.
• Each queue has its own scheduling algorithm

​

Multilevel Feedback Queue Scheduling

• The multilevel feedback queue scheduling algorithm, in contrast, allows a process to move between queues
• The idea is to separate processes according to the characteristics of their CPU bursts.
• If a process uses too much CPU time, it will be moved to a lower-priority queue.
• This scheme leaves I/O-bound and interactive processes in the higher-priority queues.
• In addition, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue.
• This form of aging prevents starvation.

Multiprocessor scheduling

• One approach to CPU scheduling in a multiprocessor system has all scheduling decisions, I/O processing, and other system activities handled by a single processor—the master server.
• This asymmetric multiprocessing is simple because only one processor accesses the system data structures, reducing the need for data sharing.
• A second approach uses symmetric multiprocessing (SMP), where each processor is self-scheduling.
• All processes may be in a common ready queue, or each processor may have its own private queue of ready processes

Processor affinity

• Consider what happens to cache memory when a process has been running on a specific processor
• Now consider what happens if the process migrates to another processor.
• The contents of cache memory must be invalidated for the first processor, and the cache for the second processor must be repopulated.
• Because of the high cost of invalidating and repopulating caches, most SMP systems try to avoid migration of processes from one processor to another and instead attempt to keep a process running on the same processor

• When an operating system has a policy of attempting to keep a process running on the same processor—but not guaranteeing that it will do so—we have a situation known as soft affinity.
• In contrast, some systems provide system calls that support hard affinity, thereby allowing a process to specify a subset of processors on which it may run

Load balancing

• Load balancing attempts to keep the workload evenly distributed across all processors in an SMP system.
• There are two general approaches to load balancing: push migration and pull migration
• With push migration, a specific task periodically checks the load on each processor and—if it finds an imbalance—evenly distributes the load by moving (or pushing) processes from overloaded to idle or less-busy processors.
• Pull migration occurs when an idle processor pulls a waiting task from a busy processor.

Multi-core processors

• Researchers have discovered that when a processor accesses memory, it spends a significant amount of time waiting for the data to become available.
• This situation, known as a memory stall, may occur for various reasons, such as a cache miss (accessing data that are not in cache memory).
• To remedy this situation, many recent hardware designs have implemented multithreaded processor cores in which two (or more) hardware threads are assigned to each core.
• That way, if one thread stalls while waiting for memory, the core can switch to another thread

Real-time CPU scheduling

• Soft real-time systems provide no guarantee as to when a critical real-time process will be scheduled. They guarantee only that the process will be given preference over noncritical processes.
• Hard real-time systems have stricter requirements. A task must be serviced by its deadline; service after the deadline has expired is the same as no service at all.

Interrupt latency

• Interrupt latency refers to the period of time from the arrival of an interrupt at the CPU to the start of the routine that services the interrupt.
• When an interrupt occurs, the operating system must first complete the instruction it is executing and determine the type of interrupt that occurred.
• It must then save the state of the current process before servicing the interrupt using the specific interrupt service routine (ISR).
• The total time required to perform these tasks is the interrupt latency

Dispatch latency

• The amount of time required for the scheduling dispatcher to stop one process and start another is known as dispatch latency. Providing real-time tasks with immediate access to the CPU mandates that real-time operating systems minimize this latency as well.
• The most effective technique for keeping dispatch latency low is to provide preemptive kernels.

Priority based scheduling

• As a result, the scheduler for a real-time operating system must support a priority-based algorithm with preemption.
• If the scheduler also supports preemption, a process currently running on the CPU will be preempted if a higher-priority process becomes available to run.

​

Rate monotonic scheduling

• The rate-monotonic scheduling algorithm schedules periodic tasks using a static priority policy with preemption. If a lower-priority process is running and a higher-priority process becomes available to run, it will preempt the lower-priority process
• Upon entering the system, each periodic task is assigned a priority inversely based on its period.
• The shorter the period, the higher the priority; the longer the period, the lower the priority

Earliest-Deadline-First Scheduling

• Earliest-deadline-first (EDF) scheduling dynamically assigns priorities according to deadline.
• The earlier the deadline, the higher the priority; the later the deadline, the lower the priority

​

Proportional Share Scheduling

• Proportional share schedulers operate by allocating T shares among all applications.
• An application can receive N shares of time, thus ensuring that the application will have N/T of the total processor time.