Module 2: Process

Management - Chapt V
By Prof. Anand S Uppar
Professor & HOD
AI&ML Dept. SUIET Mukka
 Chapter 5: CPU Scheduling
 Basic Concepts
 Scheduling Criteria
 Scheduling Algorithms
 Thread Scheduling
 Multiple-Processor Scheduling
5.1 Basic Concepts
 In a single-processor system, only one process can run at a time; any others must wait until
the CPU is free and can be rescheduled.
 The objective of multiprogramming is to have some process rum1ing at all times, to maximize
CPU utilization
 A process is executed until it must wait, typically for the completion of some I/O request.
 In a simple computer system, the CPU then just sits idle. All this waiting time is wasted;
no useful work is accomplished.
 With multiprogramming, we try to use this time productively. Several processes are kept
in memory at one time.
 When one process has to wait, the operating system takes the CPU away from that
process and gives the CPU to another process. This pattern continues.
 Every time one process has to wait, another process can take over use of the CPU.
5.1.1 CPU-i/O Burst Cycle:

• The success of CPU scheduling depends on

an observed property of processes:
 process execution consists of a cycle of
CPU execution and I/0 wait.
 Processes alternate between these two
states.
 Process execution begins with a CPU
burst -> That is followed by an I/O burst,
-> which is followed by another CPU
burst, -> then another I/0 burst, and so
on.
 Eventually, the final CPU burst ends
with a system request to terminate
execution (Figure 5.1). Figure 5.1 Alternating sequence of CPU and 1/0 burst
• The durations of CPU bursts have been
measured extensively. Although they vary
greatly from process to process and from
computer to computer they tend to have a
frequency curve similar to that shown in
Figure 5.2.
• The curve is generally characterized as
exponential or hyperexponential, with a
large number of short CPU bursts and a
small number of long CPU bursts.
• An I/O-bound program typically has many
short CPU bursts.
• A CPU-bound program might have a few long
CPU bursts. This distribution can be
important in the selection of an appropriate
Figure 5.2 Histogram of CPU-burst durations
CPU-scheduling algorithm.
5.1.2 CPU Scheduler:

 Whenever the CPU becomes idle, the operating system must select one of the processes in the
ready queue to be executed. The selection process is carried out by the short-term scheduler
(or CPU scheduler).
 The scheduler selects a process from the processes in memory that are ready to execute and
allocates the CPU to that process.
 The ready queue is not necessarily a first-in, first-out (FIFO) queue.
 As we shall see when we consider the various scheduling algorithms, a ready queue can be
implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked list.
 Conceptually, however all the processes in the ready queue are lined up waiting for a chance to
run on the CPU.
 The records in the queues are generally “process control blocks (PCBs)” of the
processes.
5.1.3 Preemptive Scheduling :

 CPU-scheduling decisions may take place under the following four circumstances:

1. When a process switches from the running state to the waiting state (for example, as the
result of an I/0 request or an invocation of wait for the termination of one of the child
processes)

2. When a process switches from the running state to the ready state (for example, when an
interrupt occurs)

3. When a process switches from the waiting state to the ready state (for example, at
completion of I/0)

4. When a process terminates

 When scheduling takes place only under circumstances 1 and 4, we say that the scheduling
scheme is nonpreemptive or cooperative; otherwise, it is preemptive.
 In CPU scheduling, preemptive scheduling allows the operating system to interrupt a
running process and switch to another,
 Windows 95 introduced preemptive scheduling, and all subsequent versions of Windows
operating systems have used preemptive scheduling.
 The Mac OS X operating system for the Macintosh also uses preemptive scheduling;
previous versions of the Macintosh operating system relied on cooperative scheduling.
 In non-preemptive scheduling requires a process to complete its execution or voluntarily
relinquish the CPU before another process can run,
 Under nonpreemptive scheduling, once the CPU has been allocated to a process, the
process keeps the CPU until it releases the CPU either by terminating or by switching to the
waiting state.
 This scheduling method was used by Microsoft Windows 3.x
 Demerits of preemptive scheduling:
 Unfortunately, preemptive scheduling incurs a cost associated with access to shared data.
 Consider the case of two processes that share data. While one is updating the data, it is
preempted so that the second process can run.
 The second process then tries to read the data, which are in an inconsistent state.
 Preemption also affects the design of the operating-system kernel.
 During the processing of a system call, the kernel may be busy with an activity on behalf
of a process. Such activities may involve changing important kernel data (for instance, I/0
queues).
 What happens if the process is preempted in the middle of these changes and the kernel
(or the device driver) needs to read or modify the same structure? Chaos ensues.
 Certain operating systems, including most versions of UNIX, deal with this problem
by waiting either for a system call to complete or for an I/O block to take place
before doing a context switch.
 This scheme ensures that the kernel structure is simple, since the kernel will not
preempt a process while the kernel data structures are in an inconsistent state.
 Unfortunately, this kernel-execution model is a poor one for supporting real-time
computing and multiprocessing. Because interrupts can, by definition, occur at any
time, and because they cannot always be ignored by the kernel, the sections of
code affected by interrupts must be guarded from simultaneous use.
 The operating system needs to accept interrupts at almost all times; otherwise,
input might be lost or output overwritten. So that these sections of code are not
accessed concurrently by several processes, they disable interrupts at entry and
reenable interrupts at exit. It is important to note that sections of code that disable
interrupts do not occur very often and typically contain few instructions.
5.1.4 Dispatcher:

 Another component involved in the CPU-scheduling function is the dispatcher.

 Dispatcher module 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 dispatcher should be as fast as possible, since it is invoked during every process switch.
The time it takes for the dispatcher to stop one process and start another running is known as
the dispatch latency.
5.2 Scheduling Criteria

 Different CPU-scheduling algorithms have different properties, and the choice of a

particular algorithm may favor one class of processes over another.
 Many criteria have been suggested for comparing CPU-scheduling algorithms. Which
characteristics are used for comparison can make a substantial difference, The criteria
include the following:
 CPU utilization – keep the CPU as busy as possible. Conceptually, CPU utilization
can range from 0 to 100 percent. In a real system, it should range from 40 percent
(for a lightly loaded system) to 90 percent (for a heavily used system).
 Throughput – One measure of work is the number of processes that are
completed per time unit, For long processes, this rate may be one process per
hour; for short transactions, it may be ten processes per second.
 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/0.
 Waiting time – The CPU-scheduling algorithm does not affect the amount of time during
which a process executes or does I/0; it affects only the amount of time that a process
spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in
the ready queue.
 Response time – In an interactive system, turnaround time may not be the best criterion.
Often, a process can produce some output fairly early and can continue computing new
results while previous results are being output to the user. Thus, another measure is the
time from the submission of a request until the first response is produced. This
measure, called response time, is the time it takes to start responding, not the time it
takes to output the response.
5.3 Scheduling Algorithm
 Optimization criteria as follows:
 Max CPU utilization
 Max throughput
 Min turnaround time
 Min waiting time
 Min response time
Scheduling Algorithms are as follows:

 First Come, First Served Scheduling (FCFS)

 Shortest Job First Scheduling (SJF)

 Priority Scheduling

 Round Robin Scheduling

 Multilevel Queue Scheduling

 Multilevel Feedback Queue Scheduling

5.3.1 First-Come, First-Served (FCFS) Scheduling
 The simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling
algorithm.
 First Come First Served (FCFS) is a simple scheduling algorithm where processes are executed
in the order they arrive, following a FIFO (First-In, First-Out) queue, meaning the first process
to arrive is the first to be executed.
 With this scheme, the process that requests the CPU first is allocated the CPU first.
 The implementation of the FCFS policy is easily managed with a FIFO queue.
 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 running
process is then removed from the queue.
 Non-Preemptive: Once a process starts running, it continues until it finishes or voluntarily
relinquishes the CPU.
 Real-life example: Buying a movie ticket at a counter, where the first person in line gets served
first. (Queueing System)
FCFS Question 1:

Process Burst Time

P1 24
P2 3
P3 3

 Suppose that the processes arrive in the order: P1 , P2 , P3

The Gantt Chart for the schedule is:

P1 P2 P3

0 24 27 30

 Waiting time for P1 = 0; P2 = 24; P3 = 27

 Average waiting time: (0 + 24 + 27)/3 = 17

FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order:

P2 , P3 , P1

 The Gantt chart for the schedule is:

P2 P3 P1

0 3 6 30

 Waiting time for P1 = 6; P2 = 0; P3 = 3

 Average waiting time: (6 + 0 + 3)/3 = 3

 Much better than previous case
 Convoy effect - short process behind long process
 Consider one CPU-bound and many I/O-bound processes
 In addition, consider the performance of FCFS scheduling in a dynamic situation.
 Assume we have one CPU-bound process and many I/O-bound processes. As the processes flow
armmd the system, the following scenario may result.
 The CPU-bound process will get and hold the CPU. During this time, all the other processes will
finish their I/0 and will move into the ready queue, waiting for the CPU. While the processes wait
in the ready queue, the I/0 devices are idle.
 Eventually, the CPU-bound process finishes its CPU burst and moves to an I/0 device. All the I/O-
bound processes, which have short CPU bursts, execute quickly and move back to the I/0
queues. At this point, the CPU sits idle.
 The CPU-bound process will then move back to the ready queue and be allocated the CPU.
Again, all the I/0 processes end up waiting in the ready queue until the CPU-bound process is
done.
 There is a “convoy effect” as all the other processes wait for the one big process to get off
the CPU. This effect results in lower CPU and device utilization than might be possible if the
shorter processes were allowed to go first.
FCFS Question 2:
FCFS Question 3:
FCFS Question 3:

GANTT CHART:-
5.3.2 Shortest-Job-First (SJF) Scheduling

 Associate with each process the length of its next CPU burst
 Use these lengths to schedule the process with the shortest time

 SJF is optimal – gives minimum average waiting time for a given set of processes
 The difficulty is knowing the length of the next CPU request
 Could ask the user
SJF Q1 (non-preemptive):
Process Burst Time
P1 6
P2 8
P3 7
P4 3
 Non-Preemptive SJF scheduling Gantt chart:-

P4 P1 P3 P2

0 3 9 16 24

 Average Turn Around time (TAT)= (P1+P2+P3+P4) / 4

= ( 9+ 24+ 16+ 3)/4
= 13 ms
 Average waiting time = (P1+P2+P3+P4) / 4
= (3 + 16 + 9 + 0) / 4
= 7 ms
 Determining Length of Next CPU Burst
 Can only estimate the length – should be similar to the previous one
 Then pick process with shortest predicted next CPU burst

 Can be done by using the length of previous CPU bursts, using exponential averaging

1. t n actual length of n th CPU burst

2.  n 1 predictedvaluefor the next CPU burst
3.  , 0  1
4. Define:
 Commonly, α set to ½
 Preemptive version called shortest-remaining-time-first

 n 1  t n  1    n .
 Prediction of the Length of the Next CPU Burst
 Examples of Exponential Averaging

  =0
 n+1 = n
 Recent history does not count
  =1
 n+1 =  tn
 Only the actual last CPU burst counts
 If we expand the formula, we get:
n+1 =  tn+(1 - ) tn -1 + …
+(1 -  )j  tn -j + …
+(1 -  )n +1 0

 Since both  and (1 - ) are less than or equal to 1, each successive term has less
weight than its predecessor
Preemptive Shortest-remaining-time-first (SJF) Q1:
 Now we add the concepts of varying arrival times and preemption to the analysis

ProcessA arri Arrival TimeT Burst Time

P1 0 8
P2 1 4
P3 2 9
P4 3 5

 Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3

0 1 5 10 17 26
Preemptive Shortest-remaining-time-first (SJF) Q2:

Preemptive SJF Gantt Chart

5.3.3 Priority Scheduling:
 A priority number (integer) is associated with each process

 The CPU is allocated to the process with the highest priority (smallest integer  highest
priority)
 Preemptive
 Nonpreemptive

 SJF is priority scheduling where priority is the inverse of predicted next CPU burst time

 Problem  Starvation – low priority processes may never execute

 Solution  Aging – as time progresses increase the priority of the process

 Example of Priority Scheduling (Non-Preemptive):

ProcessA arri Burst TimeT Priority

P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
 Priority scheduling Gantt Chart:

P2 P5 P1 P3 P4

0 1 6 16 18 19
 Example of Priority Scheduling (Preemptive):

Priority scheduling Gantt Chart:

5.3.4 Round Robin (RR):

 Each process gets a small unit of CPU time (time quantum “q”), usually 10-100
milliseconds. After this time has elapsed, the process is preempted and added to the end of
the ready queue.
 If there are n processes in the ready queue and the time quantum is q, then each process
gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more
than (n-1)q time units.
 Timer interrupts every quantum to schedule next process
 Performance,
 q large  FIFO
 q small  q must be large with respect to context switch, otherwise overhead is too high
 Example of RR with Time Quantum (q)= 4
Process Burst Time
P1 24
P2 3
P3 3

 The Gantt chart is:

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

 Typically, higher average turnaround than SJF, but better response

 q should be large compared to context switch time
 q usually 10ms to 100ms, context switch < 10 micro sec
Time Quantum and Context Switch Time
Turnaround Time Varies With The Time Quantum

80% of CPU bursts should

be shorter than q
Average Turn Around Time = (17+18+9+9+16) / 5 = 13.8 ms
5.3.5 Multilevel Queue:-
 Ready queue is partitioned into separate queues, eg:
 foreground (interactive)
 background (batch)
 Process permanently in a given queue
 Each queue has its own scheduling algorithm:
 foreground – RR
 background – FCFS
 Scheduling must be done between the queues:
 Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of
starvation.
 Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its
processes; i.e., 80% to foreground in RR, 20% to background in FCFS
 A multilevel queue scheduling algorithm partitions the ready queue into several separate queues (Figure
5.6).
Figure 5.6: Multilevel Queue Scheduling
• An example of a multilevel queue scheduling algorithm with five queues, listed below in order of
priority:
• System processes
• Interactive processes
• Interactive editing processes
• Batch processes
• Student processes
• 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.
5.3.6 Multilevel Feedback Queue

 A process can move between the various queues; aging can be implemented this way
 Multilevel-feedback-queue scheduler defined by the following parameters:
 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 will enter when that process
needs service
Example of Multilevel Feedback Queue

 Three queues:

 Q0 – RR with time quantum 8 milliseconds

 Q1 – RR time quantum 16 milliseconds

 Q2 – FCFS

 Scheduling

 A new job enters queue Q0 which is served FCFS

 When it gains CPU, job receives 8 milliseconds

 If it does not finish in 8 milliseconds, job is moved to queue Q1

 At Q1 job is again served FCFS and receives 16 additional milliseconds

 If it still does not complete, it is preempted and moved to queue Q2

Figure 5.7: Multilevel Feedback Queues
5.4 Thread Scheduling

 Distinguishing between user-level and kernel-level threads

 On operating systems that support them, it is kernel-level threads-not processes-that are
being scheduled by the operating system.
 User-level threads are managed by a thread library, and the kernel is unaware of them.
 To run on a CPU, user-level threads must ultimately be mapped to an associated kernel-level
thread, although this mapping may be indirect and may use a lightweight process (LWP).
 In this section, we explore scheduling issues involving user-level and kernel-level threads and
offer specific examples of scheduling for Pthreads.
5.4.1 Contention Scope

 Many-to-one and many-to-many models, thread library schedules user-level threads to run on
LWP.
 Known as process-contention scope (PCS) since scheduling competition is within the
process.
 Typically done via priority set by programmer.

 Kernel thread scheduled onto available CPU is system-contention scope (SCS) –

competition among all threads in system, windows XP, Solaris, and Linux, schedule threads
using only SCS.
 5.4.2 Pthread Scheduling

 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
 The Pthread IPC provides two functions for getting-and setting-the contention scope policy:
 pthread_attr_setscope(pthread_attr_t *attr, int scope)
 pthread_attr_getscope(pthread_attr_t *attr, int *scope)
 The first parameter for both functions contains a pointer to the attribute set for the thread.
 The second parameter for the pthread_attr_setscope () function is passed either the
PTHREAD_SCOPE_SYSTEM or the PTHREAD_SCOPE_PROCESS value, indicating how the
contention scope is to be set.
 In the case of pthread_attr_getscope (), this second parameter contaiilS a pointer to an int value that is
set to the current value of the contention scope. If an error occurs, each of these functions returns a
non-zero value.
5.5 Multiple-Processor Scheduling

5.5.1 Approaches to Multiple-Processor Scheduling:

 CPU scheduling more complex when multiple CPUs are available
 Homogeneous processors within a multiprocessor (Processors are identical)
 Asymmetric multiprocessing – only one processor accesses the system data structures,
alleviating the need for data sharing
 Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in
common ready queue, or each has its own private queue of ready processes
 Currently, most common
5.5.2 Processor Affinity:
Criteria A: Consider what happens to cache memory when a process has been running on a
specific processor. The data most recently accessed by the process populate the cache for the
processor; and as a result, successive memory accesses by the process are often satisfied in cache
memory.

Criteria B: 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. This is known as processor affinity- (a process has an affinity
for the processor on which it is currently running)
 soft affinity
 hard affinity
 Processor affinity takes several forms,
 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.
 Here, it is possible for a process to migrate between processors.
 Some systems -such as Linux -also provide system calls that support hard affinity,
thereby allowing a process to specify that it is not to migrate to other processors.
 Solaris allows processes to be assigned to processor sets limiting which processes can
run on which CPUs. It also implements soft affinity.
• The main-memory architecture of a system can affect processor affinity issues.
• Figure 5.9 illustrates an architecture featuring non-uniform memory access (NUMA), in which a
CPU has faster access to some parts of main memory than to other parts.

Figure 5.9 NUMA and CPU scheduling.

• Typically, this occurs in systems containing combined CPU and memory boards.
• The CPUs on a board can access the memory on that board with less delay than they can
access memory on other boards in the system.
• If the operating system's CPU scheduler and memory-placement algorithms work together,
then a process that is assigned affinity to a particular CPU can be allocated memory on the
board where that CPU resides.
• Rather, the "solid lines" between sections of an operating system are frequently only "dotted
lines," with algorithms creating connections in ways aimed at optimizing performance and
reliability
5.5.3 Load Balancing
 On SMP systems, it is important to keep the workload balanced among all processors to fully
utilize the benefits of having more than one processor
 Otherwise, one or more processors may sit idle while other processors have high workloads,
along with lists of processes awaiting the CPU
 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.
Push and pull migration need not be mutually exclusive and are in fact often implemented in
parallel on load-balancing systems.
5.5.4 Multicore Processors
 Recent trend to place multiple processor cores on same physical chip
 Faster and consumes less power
 Multiple threads per core also growing
 Takes advantage of memory stall to make progress on another thread while memory
retrieve happens
 Multicore processors may complicate scheduling issues i.e. 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 cache miss as well)

Figure 5.10: Memory stall.

• To overcome this situation of memory stall, 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.
• Figure 5.11 illustrates a dual-threaded processor core on which the execution of thread 0 and the
execution of thread 1 are interleaved.
• From an operating-system perspective, each hardware thread appears as a logical processor that
is available to run a software thread. Thus, on a dual-threaded, dual-core system, four logical
processors are presented to the operating system.

Figure 5.11 Multithreaded multicore system.

5.5.5 Virtualization and Scheduling

 Virtualization software schedules multiple guests onto CPU(s)

 Each guest doing its own scheduling

 Not knowing it doesn’t own the CPUs
 Can result in poor response time
 Can effect time-of-day clocks in guests

 Can undo good scheduling algorithm efforts of guests