chapter

3
Processes and Threads

The process concept helps to explain, understand and organize execution of programs
in an OS. A process is an execution of a program. The emphasis on 'an' implies
that several processes may represent executions of the same program. This situation
arises when several executions of a program are initiated, each with its own data.
and when a program that is coded using concurrent programming techniques is in
execution.
A programmer uses processes to achieve execution of programs in a sequential
or concurrent manner as desired. An OS uses processes to organize execution of
programs. Use of the process concept enables an OS to execute both sequential and
concurrent programs equally easily.
We discuss two views of processes in this Chapter: the programmer view, and the
OS view. In the programmer viewwe discuss how concurrent processes are created
and how they interact with one another to meet a common goal. In the OS view we
discuss how an OS creates processes, how it keeps track ofprocess states, andhow
it uses the process state information to organize execution of programs.
A thread is an execution of a program that uses the environment of a process,
that is, its code, data and resources. If many threads use the environment of the same
process, they share its code, data and resources. An OS uses this fact to reduce its
overhead while switching between such threads.
3.1 PROCESSES AND PROGRAMS

A programis a passive entity that does not perform any actions by itself: it has
to be executed to realize the actions specified in it. Aprocess is an execution of a
program; it actually performs the actions specified in aprogram. An operating system
considers processes as entities for scheduling. This is how it realizes execution of
user programs.
 Processes and Threads 85

To understand what is a process, let us discuss how the OS executes a program.

Program P shown in Figure 3.I(a) contains declarations of a fileinfo and a variable
item, and statements that read values from info, use them to perform some calcu
lations, and print a result before coming to a halt. During execution, instructions of
this program use values in its data arca andthe stack to perform the intended caicu
lations. Figure 3.1(b) shows an abstract view of its execution. The instructions, data
and stack of program Pconstitute itsaddress space. To realize execution of P, the OS
allocates memory to accommodate P's address space, allocates a printer to print its
results, sets up an arrangement through which P can access file info, and schedules
P for execution. The CPU is shown as a dashed box because it is not always execut
ing instructions of P; the OS shares the CPUbetween execution of P and executions
of other programs.
Program P
file info;
int item; Address space
open (info, "read"); of P
while not info
end-of-file (info) Instructions,
data area and
read (info, item); Printer
stack of P
CPU:
print
stop;

(a) (b)

Fig, 3.1 A program and an abstract view of its execution

Table 3.1shows two kinds of relationships that can exist between processes and
programs. A one-to-one relationship exists when a single execution of asequen
tial program is in progress. The programn consistsS of a main program and a set of
functions. During ts execution, control flows between the main program and the
functions according to the logic of the program. The OS is not aware of the existence
of functions. Hence execution of the program constitutes a single process. A many
to-one relationship would exist between many processes and this program if several
executions of the program are inprogress at the same time.
Table 3.1 Relationships between processes and programs

Relationship Examples
One-to-One A single execution of a sequential program
Many-to-one Many simultaneous executions ofa program,
Execution of a concurrent program
86 Operating Systems

Most programming languages contain features for concurrent programning.

During execution, aprogram coded using these features informs the OS about its
parts that are to be executed concurrently. The OS considers each of these execu
tions as a process. Hence the processes have a many-t0-one relationship with the
program. We callsuch a program aconcurrent program. Processes that co-exist in
the system at some time are called concurrent processes. Concurrent processes have
opportunities to interact with oneanother during their execution.
Child processes The OS initiates an execution of a program by creating aprocess
for it. This is called the main process for the execution. The main process may create
other processes, which become its child processes. A child process may itself create
other processes, and so on. All these processes form a tree with the main process as
itsroot. Example 3.I illustrates creation of child processes.
Example 3.1 The real time data logging application of Section 2.7 receives data sam
ples from a satellite at the rate of 10000 samples per second and stores them on a disk.
We assume that each sample arriving from the satellite is put into a special regis
ter of the computer. The primary process of the application, which we will call the
data loggerprocess, has to perform the following three functions:
1. Copy the sample from the special register into memory.
2. Write the sample into a disk file.
[Link] some housekeeping operations., e.g., copy some selected fields of the
incoming samples into another file used for statistical analysis.
It creates three child processes, leading to the process tree shown in Figure 3.2(a).
As shown in Figure 3.2(b), copy_sample copies the sample from the register into a
memory area named buffer area which can hold, say, 50 samples. disk _write writes a
sample from bufferareainto a disk file. housekeeping performs housekeeping opera
tions. Arrival
of a new sample is defined as an interrupt in the application, and a
programmer defined interrupt routine is associated with this interrupt. The OS exe
cutes this routine whenever a newsample arrives. It activates copy sample.
Execution of the three processes can overlap as follows: copy _samplecan copy a sam
ple into bufferarea, disk write can write a previous sample to the disk, and house
keeping can copy fields from samples already stored on disk for statistical analysis.
This arrangement provides a smaller worst-case response time of the
if these functions were to be executed application than
sequentially. So long as buffer area has some
Iree space, only copy sample has to complete before the next sample
other processes can be executed later. This possibility is arrives. The
highest priority to exploited by assigning he
copy sample.
Table 3.2describes three advantages of creating child
speed-up. higher priority for critical functions and protectionprocessescomputauon
of the parent process
from malfunctioning of child processes. The third
tion. When a software system has to invoke an advantage needs some explana
untrusted
Itselt against errors in the program. It can achieve this by program, it must proteCl
execute the program. If an error arises during its execution,creating a child process to
the OS would abort the
child prOCeSs. Thus, the parent process would not be
affected by the error. The OS
 Processes and Threads 87

register

copy.
sample
buffer area
disk.
data logger write

house
\keeping)
copy_sample disk _write housekeeping
(a) (b)

Fig. 3.2 Real time application of Section 2.7: (a) Process tree, (b) Processes

Table 3.2 Advantages of child processes

Advantage Explanation
Computation Creation of multiple processes in an application provides
speed-up multi-tasking. Its benefits are similar to those of multipro
gramming; it enables the OS tointerleave execution of /O
bound and CPU-bound processes in an application, thereby
providing computation speed-up.
Priority for A child process created to perform a critical function in an
critical functions application may be assigned a higher priority than other
functions. Such priority assignments may help the OS to
meet real-time requirements of an application.
Protecting parent The OS cancels a child process if an error arises during its
process from errors execution. This action does not affect the parent process.

command processor uses this feature to advantage. It creates a new process to exe
cute a user program. This way the command processor does not come to any harm
even if the program malfunctions.

3.2 PROGRAMMER VIEW OF PROCESSES

execution of
In the programmer view, processes are a means to achieve concurrent
a program. The main process of a concurrent program creates child processes. It
should assign appropriate priorities to them to either achieve computation speed-up
or to execute some functions at a high priority as desired (see Section 3.1). The
92 Operating Systems
obtainedHby
concurrency-when concurrency is employed, speed-up is over-
through
one process with CPU activities of other processes, wheror.
lapping /O activities
when parallelism of
is employed, CPU and I/O activities in one prOcess can overlap
proceSses.
with the CPUand /O activities of other coneus
processes are used as the model of execution of programs, both
When
parallelism depend on there being sufficient work for the OS to perfor
rency and of execution of programs, called
In Section 3.4, we introduce an alternative model
not only on availability of suff.
threads, where concurrency and parallelism dependmodel of threads implemented in
cient amount of work to perform, but also on the
the OS.

3.3 OS VIEW OF PROCESSES

program. To realize
In the operating system's view, a process is an execution of a
CPU, and termj
this view, the OS creates processes, schedules them for use of the
nates them. As discussed earlier in Sections [Link] and 2.6.2, to performscheduling
an operating system must know which processes require the CPUat any moment.
So, the key to realizing the operating system's view of processes is to monitor all
processes and know what each process is doing at any moment of timewhether
executing on the CPU, waiting for the CPU to be allocated to it, waiting for an IO
operation to complete, or waiting to be swapped into memory. The operating sys
tem uses the notion of process state to keep track of what a process is doing at any
moment.
In this section, we discuss the notion of process state, different statesofa process,
and the arrangements used by the operating system tomaintain information about the
state of a process. We do not discuss scheduling in this chapter; it is discussed later
in Chapter 4.
3.3.1 BackgroundExecution of Programs
When a process, 1.¬., an execution of a program, is scheduled. the CPUexecutes
instructions in the program. When the CPU is tobe switched to some other process,
the kernel saves the state of the [Link] state is loaded back into the CPUwhen the
process is scheduled again. This view leads to the following definition of a procesS.

Definition 3.1 (Process) A process is comprised of six components:

(id, code, data, stack, resources, CPUstate)
where id is a unique name/id assigned to the program execution,
code is the program code,
datais the data and files used in the program's execution,
resources is the set of resources allocated by the OS,
stack contains parameters of functions and procedures called, and their
return addresses,
 Processes and Threads 93

CPU state is comprised of contents of the PSW fields and the CPU
registers.
As described in Section 2.1.1. the CPUstate contains information like
of the instruction to be executed next, the condition code, which is address
alsocalled/lags.
and contents of CPU registers. The CPUstate changes as the
program execution
procceds. The code, data and stack of the process constitute itsaddress space.
3.3.2 Controlling Processes
A process is a program execution. Hence following Def. 3.1, a process has the five
components process id, code, data, stack, and CPU state. The process uses the CPU
when it 1s scheduled. It also uses other resources. These include system
resources
1ke memory and user-created resources like files. The OS has to maintain informa
tion about all these features of a
process.
The OS view of a process consists of two
parts:
" Code and data areas of the process, including its stack, and resources
allocated
to it

Information concerning program execution.

Figure 3.4 shows the arrangement used to control a process. It consists of a
process environment and the process control block (PCB). The id of a process is
used to access its process environment and PCB. This arrangement enables different
OS modules to access process-related data conveniently and efficiently.

memory resource file

info info pointers
process id
process state
register values
code data stack pc value

Process environment Process control block

(PCB)
Fig. 3.4 OS view of a process

Process environment Also called the process context, the process environment
contains the address space of a process, i.e., its code, data, and stack, and all infor
mation necessary for accessing and controlling resources allocated to the process.
The OS creates a process environment by allocating memory to the process, loading
the process code in the allocated memory and setting up itsdata space. The OS also
94 Operating Systems

puts in information concerning access to resources allocated to the process, and its
nteraction with other processes and with the OS.
Table 3.4 deseribcs components of he process environment. Contents of the
proccss cnvironment change during exccution of a prOceSs duc to actions like fle
open and close, and dynamic creation and destruction of data by the process.
Table 3.4 Components ot the pocOSs environment

Process environment
Process environment consistsof the code and data of the process and all information
necessary for operationof the process.
Component Description
Code and data Code of the program, including its functions and proce
dures, and its data, including the stack.
Memory allocation Information concerning memory areas allocated to the
information process. This information is used to implement memory
accesses made by the process.
Status of file process Pointers to files opened by the process, and current pos0
Ing activities tions in the files
Process interaction All information necessary to control interactions of the
information process with other processes, e.g., interprocess meSsages,
signal handlers, ids of parent and child processes.
Resource information Information concerning resources allocated to a process.
Miscellaneous infor Miscellaneous information needed for interaction of a pro
mation cess with the OS.

Process control block (PCB) The process control block is a kernel data structure
that contains information concerning the first and fifth component of Def. 3.1, that
is, process id and CPUstate. Details of the PCB are described in Section 3.3.4.
The kernel uses three fundamental functions to control processes:
1. Scheduling: Select the process to be executed next on the CPU.
2. Dispatching: Set up execution of the selected process on the CPU.
3. Context save: Save information concerning a running process when its
execu
tion is suspended.
The scheduling function selects a process based on the scheduling policy in force.
Dispatching involves setting up the environment of the selected process, and loading
information into the CPUso that CPUbegins (or resumes) execution of instructions
in the process code. The context save function performs
housekeeping whenever a
process releases the CPU or is preempted. It saves information concerning the CPU
state and the process environment so that execution of the process may be
resumed
sometime in future. Effectively, context save is the converse of the dispatching tunc
tion.
 Processes and Threads 95

Event

Context save

Event handling

Scheduling

Dispatching
Fig. 3.5 Fundamental functions to control processes

The schematic in Figure 3.5 illustrates use of these functions by the kernel when
an event occurs. Occurrence of an event invokes the context save function and an
appropriate event processing routine. The event processing actions may activate
some processes, hence the scheduling function is invoked to select a process and
the dispatching function transfers control to the selected process.

3.3.3 Process States and Transitions

The notion of process state is introduced to simplify control of processes by the
operating system.

Definition 3.2 (Process state) The process state is an indicator of the nature of the
Current activity in aprocess.
Table 3.5 describes four fundamental process states. A process is in theblocked
state if it has made a resource request to the kernel and the request is yet to be
granted, or if it wishes to wait until some event occurs. The process enters theready
state when the request is granted or the event occurs, and it enters therunningstate
when it is dispatched. The process enters the terminated state when its execution
completes or when it is terminated by the OS for [ome reason.
A conventional computer system contains one CPU, so at most one process can
be in the running state. Any number of processes can however exist in the blocked,
ready and terminated states. An OS may define more process states to simplify its
Own functioning or to support additional functionalities like swapping.
Process state transitions A state transition for a process P, is a change in its state.
A state transition is caused by the occurrence of some event in the system. When a
process P, in the running state makes an /O request, it has toenter the blocked state
until its LVO operation completes. Atthe end of the I/O operation P,'s state changes
from blocked to ready. Similar state changes occur when a process makes some
96 Operating Systems

Table 3.5 Fundamental process states

State Description
Running A CPUiscurrently executing instructions in theprocess code.
Blocked The process has to wait untila resource request made by it is granted.
or it wishes to wait until a specific event occurs. A CPU should not
be allocated to it until its wait is complete.
Ready The process wishes to use the CPUto continue its operation; how
ever, it has not been scheduled.
Terminated The operation of the process. i.e., the execution of the program rep
resented by it, has completed normally, or the OS has aborted it.

request that cannot be satisfied by the OS straightaway. The process state changes to
blocked when the request is made, i.e., when the request event Occurs, and changes
toready when the request is satisfied. Aready process becomes running when the
CPUis allocated to it. A running process becomesready when it is preempted either
because ahigher priorityprocess becomes ready or because its time slice elapses (see
Sections [Link] and 2.6).
Figure 3.6 shows the fundamental state transitions for a process. Table 3.6 sum
marizes causes of state transitions. A new process is put in the ready state after all
resources required by it have been allocated. It may enter the running, blocked and
ready states a number of times due to events described in Table 3.6. Eventually
enters the terminated state.

Running completion Termi

nated

resource or
dispatching, wait request
preemption
new
procesS Ready Blocked
resource granted
or wait completed
Fig, 3.6 Fundamental state transitions for a process

Example 3.3 Consider the time sharing system of Example 2.12, which uses a
slice of 10 msec. It contains two programs P and P.. P, has a CPU burst oftinie1
msec followed by an VO operation that lasts for 100 msec, while P has a CPU burst
of 30 msec followed by an I/O operation that lasts for 60 msec.
Execution of >i
and P2 was described in Figure 2.2 1and Table 2.13. For simplicity, we
assume thal
processes created to execute programs P and P> are themselves called P and P2.
 Processes and Threads 97

Tahle3.6 Causes of fundamental state transitions for a process

State transition Deseription

ready rning The prOcCSs 0s dispatched. CPU starts or resumes execution
of its instructions
blocked ’ ready A request made by the process is satisfied or an event for
which it was waiting occurs.
runing ’ ready The process is preempted because the OS decides to schedule
soMe other process. This transition occurs either because a
higher priority process becomes ready, or because the time
slice of the process elapses.
running The program being executed makes a system call to indicate
blocked that it wishes to wait until some resource request made by
it is satisfied, or until a specific event occurs in the system.
Five major causes of blocking are:
Process requests an I/O operation
ProcesS requests memory or some other resource
" Process wishes to wait for a specified interval of time
" Process waits for message from another process
" Process wishes to wait for some action by another process

running ’ Execution of the program is completed or terminated. Five

terminated primary reasons for process termination are as follows:
" Self-termination: The program being executed
either
completes its task or realizes that it cannot execute mean
ingfully and makes 'terminate me' system call. Examples
and
of the latter condition are incorrect or inconsistent data,
inability to access data in a desired manner, e.g., incorrect
file access privileges.
'terminate
" Termination by a parent: A process makes a finds
P, when it
P system call to terminate a child process
the execution of the child process is no longer necessary or
achieved by the parent
meaningful. (The same effect can be
process and the
sending a 'terminate now' signal to the child call.)
system
child process making a 'terminate me' may limit the
" Exceeding resource
utilization.: An OS
consume. A prOcess exceed
resources that a process may
terminated by the kernel.
ing a resource limit would be execution: The kernelcan
" Abnormal conditions during
condition arises in the program
cels a process if an abnormal
of an invalid instruction, exe
being executed, e.g., execution arithmetic conditions like
instruction,
cution of a privileged violation, etc.
overflow, memory protection kernel
with other processes: The pro
" Incorrect inte raction incorrect interaction with other
may cancel a process for involved in a deadlock.
cesses,e.g., if a process gets
98 Operating Systems

respectively. Actual execution of programs proceeds as follows: Table 3.7 illustrates

the state transitions in the system. System operation starts with both processes in read.
state at time 0. The scheduler selects process P; for execution and changes its state to
rnming. At 10msec, P is preempted and P2 is scheduled, so Pi'sstate is changed to
ready and P's state is changed to running. P gets blocked at 25 msec because of an
/O operation. At 35 msec, P is preempted because its time slice elapses, however it
is scheduled again since no other process is in the ready state. P's VO operation is
completed at 125 msec, so its state is changed to ready. The scheduler selects it for
execution,hence its state is further changed to running.
Table 3.7 State transitions in atime sharing system

New state
Time Event Remarks P P
P is scheduled running ready
10 P ispreempted P isscheduled ready running
20 P is preempted P is scheduled running ready
25 P starts /O P is scheduled blocked running
35 P is preempted blocked ready
P is scheduled blocked running
45 PP starts I/O blocked blocked
125 VOinterrupt P, becomes ready ready blocked
P is scheduled running blocked

[Link] Suspended Processes

In addition to the four fundamental process states described in Table 3.5. an OS
uses a fifth state called suspend state for a process that is not to be considered for
scheduling. The state of such a process is changed to ready or blocked when its
operation is to be resumed. The suspend state differs from the blocked state in that
the reason for suspension is external to the activity in the process, while the reason
for blocking is internal to its own activity. Two typical causes of suspension are:
" A process is moved out of memory, i.e., it is swapped out.
" The user who initiated a processspecifies that a process should not besched
uled until some condition is satisfied.
The process state is an abstract notion defined by an OS designer and used by
the kernel to simplify control of processes. A kernel may use a singlesuspend stale
and use some auxiliary information to decide whether a process in the suspend Slat
should enter the ready state or the blocked state when itsoperation is to be resumed.
Alternatively, the kernel may split the suspend state into a number of states depending
on the cause of suspension. This approach simpliñes specification of state transitions
into andout of a suspend state.
We restrict the discussion of suspended processes to swapped proCesses and u
two suspend states called ready swapped and blocked swapped. Accordingty, Fig
ure 3.7 shows process states and state transitions. Transitions from the ready to reaa)
 Processes and Threads 99

Swapped state and blocked to blocked swapped state are caused by a swap-out action.
The reverse transitions take place when these processes are
swapped back int0 the
memory. The blocked swapped ’ ready swapped transition takes place if the request
for which the process was waiting is granted even while the
state, for example if a resource for which it was blocked isprocess
is ina suspended
granted to it. However,
the process continues to be swapped out. When it is
swapped back into the memory,
its state would change to ready and it would compete with other
the CPU's attention. ready processes for

completion Termi
Running nated

resource or
dispatching, wait request
preemption
new
Ready resource granted
process
or wait completed Blocked

Swap Swap Swap swap

out in out in

Ready resource granted /Blocked

\Swapped or wait completed\swapped

Fig. 3.7 Process states and state transitions using two swapped states

3.3.4 Process Control Block

The processcontrol block (PCB) contains all information pertaining toa process that
is used in controlling its operation--such as its id, priority, state, PSW and contents
of CPU registersas also information used in accessing resources and implementing
communication with other processes. Table 3.8 describes fields of the PCB data
structure.
The priority and state information is used by the scheduler. It passes the id of the
selected process to the dispatcher. For a process that is not in therunning state, the
PSW and CPUregisters fields together contain a snapshot of the CPUwhen it was
last released by the process, i.e., they hold contents of the various control and data
registers of the CPUwhen the process got blocked or was preempted. Execution of
the process can be resumed by simply loading this information from its PCB into the
100 Operating Systems

Table 3.8 Fields of the Process Control Block (PCB)

PCB field Contents

Process id The unique id assigned to the process at its creation.
Child and These ids are used for process synchronization, typically for a
parent ids process to check whether a child process has terminated.
Priority The prioity is typically a numeric value. A process is assigned
a priority at its creation. Priority may change during the life of
a process depending on its nature (whether CPU-bound or I/0
bound), its age and the resources consumed by it (typically CPU
time).
Process state The current state of the process.
PSW This is a snapshot, ie., an image, of the PSW when the CPU
was last voluntarily released by the process or was last preempted
by the kernel. Loading this snapshot back into the PSW would
resume execution of the program. (See Fig. 2.3 for fields of the
PSW.)
CPUregisters Contents of the registers when the CPUwas last released by the
process or last preempted by the kernel.
Event For a process in the blocked state, this fieldcontains information
information concerming the event for which the process is waiting. When an
event occurs, the kernel uses this information to identify the pro
cess that awaits the event and changes its state from blocked to
ready.
Signal Information concerning locations of signal handlers (see Sec
information tion 3.6.4).
PCB pointer This field is used to form a list of PCBs. The kernel maintains
several lists of PCBs, e.g., a list of PCBs of ready processes, a list
of PCBs of blocked processes, etc.

[Link] action would be performed the next time this process is to be dispatched.
The event information field of the PCB plays an important role in effecting appro
priate state transitions in the system. Consider a process P, that is blocked on an VO
operation. The event information field in P's PCB indicates the id of the device, say
device d, on which the VO operation is being performed. When the IO operation
on device d completes, the kernel must find the process that awaits that event and
change its state to ready. eventinformation field of P;'sPCB indicates that it awaits
the end of VO on device d, so the kernel concludes that the state of P, should be
changed from blocked to ready.

3.3.5 Context Save, Scheduling and Dispatching

The context save function performs housekeeping whenever aprocess releases he
CPUor is preempted. It involves saving the PSW and CPUregisters in appropriate
 Processes and Threads 101

fields of the PCB of the process, and also saving

environment (see Section 3.3.2). It also marks theinformation
state
concerning its process
of the process asready. An
event processing action nmay later change the state
The scheduling function uses the process state toblocked.
areadv process for execution. I information from PCBs to select
changes
its id to the dispatching function. The
the state of the process toready and passes
of the selected process and loads dispatching function sets up the environment
of its PCB into the CPU. information from thePSW and CPUregisters fields

Example 3.4 An OS contains 2 processes P and P2,

than P. Let P½ be blocked on an /Ooperation and letwithP be
P having a higher priority
actions take place when the /O completion event occurs for therunning.
I/O
The following
operation of P2:
[Link] context save function is performed for P, and its state is
changed to ready.
2. The L/O completion event is processed and the state of P is
changed from
blocked to ready.
3. Scheduling is performed. is selected because it is the highest priority ready
process.
4. P, is dispatched.

Process switching Functions 1,3 and 4 of Example 3.4 collectively perform switch
ing between processes P and P. Switching between processes also occurs when a
running process gets blocked due to a request or gets preempted. An event does not
lead to switching between processes if occurrence of the event either causes a state
transition for a lower priority process, or does not cause any state transition (e.g., if
the event is caused by a request that is satisfied straightaway). In the former case, the
scheduling function selects the interrupted process itself for dispatching. In the latter
case, scheduling need not be performed at all; after event processing, control can be
given to the dispatcher, which would simply dispatch the interrupted process.
Switching between processes is more than saving the CPUstate of one process
and loading CPUstate of another process. The process environment needs to be
switched as well. Saving and loading of memory management information is an
expensive part of process switching, particularly when virtual memory is used. Some
switching over
computer systems provide special instructions to reduce the processregisters. We use
CPU
head, e.g.. an instruction that saves or loads the PSW and all
information that needs to be
the term state information of a process to refer to all the switching overhead depends
saved and restored during process switching. Process
on the size of this information.
well. The newly scheduled
Process switching has some indirect overhead as
space in the cache, hence it performs
process does not have any part of its address operation
poorly until it builds sufficient information in the cache. Virtual memory
buffers do not contain any information
isalso poorer initially because translation
relevant to the newly scheduled process.
6 Operating Systems
action is not performed if'the resource can bc allocated straightaway. In this. Case, the
interrupted process is simply dispatched again. When a process releases aresource,
released
an wnblock action is performed ie' some other process Is waiting lor the
source, followed by scheduling and dispatching because the unblocked process ma.
resource. Again, schedl:
have a higher priority than the process that released the
the event.
is skipped if no process is unblocked due to
THREADS

Use of processes to provide concurrency within an application Incurs high process

switching overhead (see Section 3.3.5). Threads provide a low cost method of imple.
menting concurrency that is suitable for certainkinds of applications.
Process switching overhead has two components:
. Executionrelated overhead: A processis defined as an execution of a program.
Hence, while switching between processes, the CPU state of the running pro
cess has to be saved and the CPUstate of a new process has to be loaded in the
CPU. This overhead is unavoidable.
Resource use related overhead: As discussed in Section 3.3, theprocess envi
ronment contains information concerning resources allocated to aprocess and
its interaction with other processes. It leads to a large size of process state
information,which adds to the process switching overhead.
Switching overhead can be reduced by eliminating the resource related overhead
in some situations. Consider the context save, scheduling and dispatching functions
depicted in Figure 3.5 and discussed in Section 3.3.5. Occurrence of an event may
result in switchingfrom execution of a running process P, to execution of some other
process P;. If both P, and P; belong to the same application, they share the code, data
and resources; their state information differs only in the values contained in CPU
registers and stacks. Much of the saving and loading of process state information
while switching from P; to P, is thus redundant. This feature is exploited to achieve
areduction in switching overhead. The notion of a thread is used for this purpose.
Definition 3.3 (Thread) Athread is aprogram execution that uses the resources fa
process.

Since a thread is a program execution, it has its own stack and CPUstate (see
Def. 3.1). We use the phrases 'thread(s) of a process' and 'parent process of a threa
to describethe relationship between a thread and the process whose environment
uses. Threads of the same process share code, data and resources with one anoui
The process abstraction continues lo be used as before except that processes typically
have distinct code anddata parts.
Figure [Link] depicts the relationship between threads and processes. Process?i
has three hreads represented by he wavy lines. The kenel allocates a stack a
 Processes and Threads 107

Threads
Process
P
Stacks
memory resource fi le
info info p0inters

code data stack

Environment of
Environment of Thread control
process P; process P PCB
blocks (TCBS)
(a) (b)

Fig. 3.11 Threads in process P: (a) concept, (b) implementation

a thread control block (TCB)to each thread. The threads execute within the envi
ronment of P;. The OS is aware of this fact, so it saves only the CPUstate and the
stack pointer while switching between threads of the same process. In most com
puter systems, the stack pointer is maintained in a CPU register, hence only the CPU
state needs to be switched. Use of threads effectively splits the process state into two
parts- -resource state remains with the process while execution state is associated
with athread. The cost of concurrency within the environment of aprocess is now
merely replication of the execution state for each thread. The resource state is not
replicated.
Thread states and state transitions Barring the difference that threads do not have
resources allocated to them, threads and processes are analogous. Hence thread states
state transi
and thread state transitions are analogous to process states and process
process
tions, When a thread is created, it is put in the ready state because its parent when
enters the running state
already has the necessary resources allocated to it. It
state because of resource requests, be
it is scheduled. It does not enter the blocked state
does not make any resorce requests; however, it can enter the blocked
cause it example, if threads were used
requirements. For
because of process synchronization Example 3.1, thread disk write would
data logging application of
in the real time data samples exist in bufer area.
have to enter the blocked state if no
application process can create many threads to execute
Advantages of threads An many
to see the advantages of this scenario over creation of
its code. It is interesting code. The fundamental advantage is that of low
application another thread of the same
processes to execute the CPU from one thread to
overhead while switchingthe switched only while switching between threads of
is
process. The resource state
different processes. within a process. It can provide computa
concurrency
Use of threads provides
 108 Operating Systerms
speed-up-if one thread of aprocess blocks on an I/Ooperation, the CPI
tion
be switched to another thread of the same process. Use of threads can also simplify
the design and coding of applications that need to perform Concurrent servicing of
or a banking system
requests. For example, in an airline reservation system OS would schedule th
thread can be created to handle each new request. The
complex logic to ach:
threads to provide concurrency. This arrangement obviates
concurrent processing of requests.
soms
Creation of many processes within the application code can achieve the
effect. However, there is one significant difference. Concurrent activities, whether
processes or threads, have to communicate or synchronize with one another. When
these activities are implemented by processes, communication or synchronization
involves the kernel. Processes have to make system calls to indicate their com
munication or synchronization requirements to the kernel. However, threads of a
process share their data space. Hence they can communicate or synchronize using
shared memory, thereby eliminating expensive system calls. Therefore in the real
time application of Example 3.1, it would be preferable to use threads to implement
functions 1and 2, which share the buffer area.
Table 3.9 summarizes the advantages ofthreads. As discussed in Example 3.1, an
application can create many threads to obtain concurrency and simplify its function
ing. Threads can be assigned specific functions. They can also be created to perform
concurrent servicing of requests received by a server, e.g., in an airline reservation
system or abanking system. In such cases, threads would execute the same function.

Table 3.9 Advantages of threads

Advantage Explanation
Low overhead Thread state consists only of the state of a
Resource allocation state and communication state computation.
is not a part
of thread state, which leads to low switching
Speed-up overhead.
Concurrency within a process can be realized by creating many
threads in it. This technique can speed up execution of an appli
cation on both uniprocessors and
Efficient multiprocessors.
Threads of a process can communicate with one another
communication through shared data space, thus avoiding the overhead of sys
tem calls forcommunication.
Coding for use of threads Threads should ensure
(see Section 3.2.1). Correctness ofcorrectness
of data sharing and
synchronization
facet. Functions or subroutines that use data sharing also has anouiC
static or global data to carry values d
ner suCcessive activations produce
because the concurrent invocations incorrect results when invoked concurrenti
effectively perform data sharing without muo
 Processes and Threads 109

Cxclusion. Such routines are said to be thread unsafe. An

threads must be coded in a thread safe manner and must invoke application that uses
thread safe library. routines only from a
Signal handling requires spccial attention in a multi-threaded
that the kernel permits a process to specify signal handlers application. Recall
(see Section 3.6.4). When
several threads arecreated in a process, which thread should handle a
are several possibilities. The kernel may select one of the signal? There
threads for
Thischoice can be made either statically, e.g., either the first or the lastsignal handling.
in the prOcess, or dynamically, e.g., the highest priority thread created
thread.
kemel may permit an application to specify which thread should Altematively, the
any timne. handle signals at
A synchronous signal arises due to the activity in a thread, so it is best that
the
thread itself handles it. Ideally, each thread should be able to specify which syn
chronous signals it is interested in handling. However, to provide this feature, the
kernel would have to replicate the signal handling arrangement of
Figure 3.11
each thread, so few operating systems provide it. An asynchronous signal can for be
handled by any thread in a process. To ensure prompt attention to the condition that
caused the signal, the highest priority thread should handle such a signal.
Implementation of threads Threads are implemented in different ways. The main
difference is in how much the kernel and the application program know about the
threads. These differences lead to different implications for overhead and concur
rency in an application program.
In this Section we discuss three methods of implementing threads. These are:
" Kernel-level threads
User-level threads
Hybrid threads
Experimental studies have shown that switching between kernel-level threads of a
process is over 10 times faster than switching between processes, and switching
between user-level threads isover 100 tímes faster than switching between processes.
Kernel-ievel threads provide better parallelism and speed-up in amultiprocessor sys
tem.

3.4.1 Kernel-Level Threads

A kernel-level thread is implemented by the kernel. Hence creation andtermination
of kernel-level threads, and checking their status, is performed through system calls
analogous to those discussed in Section 3.2. Figure 3.12 shows a schematic of how
the kernel handles kernel-level threads. When aprocesS makes a create hread sys
tem call, the kernel assigns an id to it, and allocates a thread control block (TCB).
The TCB contains a pointer to the PCB of the process.
When an event occurs, the kernel saves the CPU state of the interrupted thread
in its TCB. After event handling, the scheduler considers TCBs of all threads and
 110 Operating Systems

P PCB
PCB
W

Thread control blocks

Scheduler

Selected TCB

Fig. 3.12 Scheduling of kernel-level threads

selects one ready thread; the dispatcher uses the PCB pointer in its TCB to check if
the selected thread belongs to a different process than the interrupted thread. If so,
itsaves the context of the process to which the interrupted thread belongs, and loads
the context of the process to which the selected thread belongs. It then dispatches the
selected thread. Actions to save and load the prOcess context are unnecessary if both
threads belong to the same process. This feature reduces the switching overhead.
Advantages and disadvantages of kernel-level threads A kernel-level thread is like
a process except that it has a smaller amount of state information, i.e., it has a
"thinner state. This similarity between threads and processes is
convenient for
programmers-programming for threads is no different from programming for pro
cesses. In a multiprocessor system, kernel-level threads provide parallelism (see
Section 3.2.2), i.e., several threads belonging to a process can be
scheduled simul
laneously, which is not possible using the user-level threads described in the next
section,so it provides better computation speed-up than user-level
However, handling threads like processes has its disadvantagesthreads.
too. Switching
between threads is performed by the kernel as a result of
incurs the overhead of event handling even if the event handling. Hence i
interrupted thread and the selected
thread belong to the same process. This feature limits
Overhead. the savings in the switchlng

3.4.2 User-Level Threads

User-level threads are implemented by athread library., which is

of a process. The library sets up the linked to the code
thread implementation arrangement show
 Processes and Threads 111

Figure 3.||(b) without involving the kernel, andinterleaves operation of threads in

the process. Thus, the kernel is not aware of presence of user-level threads in a
process; it sees only the process. The scheduler considers PCBs and selects a ready
process: the dispatcher dispatches it. Most OSs implement the pthreads application
progran interface providecd in the IEEE Posix standard in this manner.
An overview of creation and operation of threads is as follows: A process invokes
the library function create_thread to create anew thread. The library function cre
ates a TCB for the new thread and starts considering the new thread for 'schedul
ing'. When the thread in the running state invokes a library function to synchronize
its functioning with other threads, the library function performs scheduling' and
Switches to another thread of the process. This amounts to a thread switch. Thus, the
kernel is oblivious to switching between threads; it believes that the process is Con
tinuously in operation. If the thread library cannot find a ready thread in the process.
it makes a 'block me' system call. The kernel now blocks the process. The process
will be unblocked when some event activates one of its threads and will resume exe
cution of the thread library function,which will perform 'scheduling' and switch to
execution of the newly activated thread.

Scheduling of user-level threads Figure 3.13 is a schematic diagram of scheduling

of user-level threads. The thread library code is a part of each process. It performs
'scheduling' to select a thread, and organizes its execution. We view this operation
as mapping of the TCB of the selected thread into the PCB of the process.

P P

Thread control blocks

Mapping pertormed
by threads library
Process control blocks

Scheduler

Selected PCB

Fig. 3.13 Scheduling of user-level threads

The thread library uses information in the TCBs to decide which thread should
 112 Operating Systems

operate at any time. To dispatch' the thread, the CPU state of the thread
become the CPU state of the process, and the process stack pointer
should
to the thread's stack. Since the thrcad library is a part of a process, the
shoulpointd
in the non-privileged mode. Hence athread cannot be dispatched by CPU is
information into the PSW; the thread library has to use non-privilegedloading new
to change PSW contents, so it loads the address of the thread's stack into
address register, and executes a branch instruction to transfer control tothe
thAstack instructions
instruction of the thread. The next example illustrates interesting situations
scheduling of user-level threads. during
Example 3.6 Figure 3.14 illustrates how the thread library manages three threads in
aprocess P. The codes N, Rand Bin the TCBs represent the states running. Tead
and blocked, respectively. Process P is in the running state and the thread library
is executing. It dispatches thread hË. Process P; is preempted sometime later by the
kernel. Figure 3.14 (a) illustrates states of the threads and of process P;. Thread h
is in the running state, and process P; is in the ready state. Thread h| would resume
its operation when process P, is scheduled next. The line from hË's TCB to P's PCB
indicates that hË's TCB is currently mapped into P,'s PCB. This fact is important for
the dispatching and context save actions of the thread library.
hË hT h3 hË h2 h3 hË h2 h3 hË hy h3
P P P P

TCBs NR B NRB| RNBh B

PCB
of P Ready Running Running Blocked
ds

(a) (b) (c) (d)

Fig. 3.14 Actions of the thread library (N,R,B indicate running, ready and blocked)

Thread h is in the ready state in Figure 3.14(a), so its TCB contains the code h
Thread h3 awaits a synchronization action by hi, so it is in the blocked state.
TCB contains the code B, and hË to indicate that it is avwaiting an event that
synchronization action by hË. Figure 3.14(b) shows the situation when the kenis
dispatches P; and changes its state to running.
The thread library overlaps operation of threads using the timer. When thread hi W
'scheduled', it would have requested an interrupt after a smallinterval of time. wen
the timer interrupt occurs, it gets control through the event handling routine oI
 Processes and Threads 113

kernel for timer interrupts, and decides to preempt h1. So it saves the CPUstate in
h's TCB, and 'schedules' hT. Hence the state codes in the TCBs of hË and h2 change
to Rand N, respectively (Figure 3. 14(c)). Note that thread scheduling performed by
the threadlibrary is invisible to the kerncl. Al through these events, the kernel sees
process P, in the running state.
Auser thread should not make a blocking system call; however, let us see what would
happen if h2 made a system call to initiate an /O operation on device dz, which is a
blocking system call. The kernel would change the state of process P, to blocked and
note that it is blocked due to an l/O operation on device dz (Figure 3.14(d). Sometime
after the /O operation completes, the kernel would schedule process P, and operation
of h2 would resume. Note that the state code in hz's TCB remains N, signifying the
running state, all through its /O operation!

Advantages and disadvantages of user-level threads Thread synchronization and

scheduling is implemented by the thread library. This arrangement avoids the over
head of a system call for communication and synchronization between threads, so
the thread switching overhead is smaller than in kernel-level threads. This arrange
ment also enables each process to use a scheduling policy that best suits its nature.
A process implementing a real time application may use priority-based scheduling
of itsthreads to meet its response requirements, whereas a process implementing a
multi-threaded server may perform round-robin scheduling of its threads.
Managing threads without involving the kernel also has a few drawbacks. First,
the kernel does not know the distinction between a thread and a process, so if a thread
were to block in a system call, the kernel would block its parent process. In effect,
all threads of the process would get blocked until the cause of the blocking was
removed-In Figure 3.14 (d) of Example 3.6, thread hË cannot be scheduled even
though it is in the ready state because thread h, made a blocking system call. Hence
threads must not make system calls that can lead to blocking. To facilitate this, an OS
would have to make available anonblocking version of each system call that would
otherwise lead to blocking of a process. Second, since the kernel schedules a process
and the thread library schedules the threads within a process, at most one thread of
a process can be in operation at any time. Thus, user-level threads cannot provide
parallelism (see Section 3.2.2), and the concurrency provided by them is seriously
impaired if a thread makes a system call that leads to blocking.
34.3 Hybrid Thread Models
A hybrid thread model has both user-level threads and kernel-level threads and a
method of associating user-level threads with kernel-level threads. Different meth
ods of associating user- and kernel-level threads provide different combinations of
the low switching overhead of user-level threads and the high concurrency and paral
lelism of kernel-level threads. In the following, we describe three such methods and
their properties.
Figure 3.15illustrates methods of associating user-level threads with kernel-level
 chapter
4

Scheduling
Thescheduling policy used in an operating system influences user service, eficient
use of resources and system performance. Scheduling policies use the fundamen
tal techniques of preemption, reordering of requests and variation of time slice to
achieve their goals. We discuss how these techniques are used in classical non
preemptive and preemptive scheduling policies.
An operating system has to adapt its functioning to the availability of resources
in the system; it uses a combination of three schedulers called long-term, medium
term and short-term schedulers for this purpose. An important issue in practical
scheduling is fairness in user service. We discuss how operating systems incorporate
fairness by dynamically varying the priority of a process. We also study scheduling
in a real time environment.
Performance analysis of scheduling policies is important for tuning the pertor
mance of a scheduling policy and for comparing alternative policies. We discuss
important elements of performance analysis.
4.1 PRELIMINARIES

Scheduling is the activity of selecting the next request to be serviced by a server. A

scheduling policy determines the quality of service provided to users. It also influ
ences the performance of a computer system. In Sections 2.5.3. 1 and 2.6.2, we dis
cussed the scheduling policies used in multiprogramming and time sharing systems,
respectively, and saw how the lechniques of preemption, assignment of priorities to
processes, and time slicing are used to achieve the desired combination of user ser
vice and system performance. In this Chapter, we discuss features and properties of
many other scheduling policies.
 148 Operating Systems

keep increasing as it waits to get scheduled until its

priority exceeds the
all other pending requests. Athis time. it would get scheduled. This priority o
called aging of requests. technique
4.2 NON-PREEMPTIVE SCHEDULING POLICIES

In non-preemptive scheduling, a server always processes a scheduled request 10

Com
pletion. Thus preemption of a request as shown in Figure 4. 1I never oCcurs. Schedul.
ing isperformed only when processing of the previously schcduled request gets co
pleted. Non-preemptive scheduling is attractive due to its simplicity--it is not ne
sary to maintain a distinction between an unserviced request and a partially servie
One.

Since preemption is not used, the scheduler depends on reordering of

requestthre:s
to achieve an improvement in user service or system performance. We discuss
non-preemptive scheduling policies in this Section:
" FCFS scheduling
" Shortest request next (SRN) scheduling
" Highest response ratio next (HRN) scheduling.
We use the five processes shown in Table 4.2 to discuss the operation and perfor
mance of various scheduling policies. For simplicity we assume that aprocess does
not perform any IOoperations.
Table 4.2 Processes for scheduling

Process P Pp P, P4 Ps
Arrival time 2 3 5
Service time 3 3 2 5 3

FCES scheduling Requests are scheduled in the order in which they arrive m
the system. The list of pending requests is organized as a queue. The sCheuu
always schedules the first request in the list. An example of FCFS scheduling
batch processing system in which jobs are ordered according to their arrival times
(or arbitrarily if their arrival times are identical), and results of a job are releasedto
a user immediately on completion of a job. Example 4.1 illustrates operation ofan
FCFS scheduler.

Example4.l Top half of Figure 4.2 shows the scheduling decisions perforned by thí
FCFS policy for the processes of Table 4.2, Left half of Table 4.3 summar1zeS
formance of the FCFS scheduler. The Completed column shows id of the completed
process and its turn around time (ta) and weighted turn around ((w). Note that consid-
erable variation exists in the weighted turn arounds. This variation would have been
larger if processes suffering large turn around times were short, e.g.. the weightedturn
 Scheduling 149

around of P, would have been large if its execution requirement was I.0 second or 0.5
seconds. Mean ta and w(i.e., ta and w) are shown below the table.

P
First-come
first-served P
(FCFS) PA
Ps

P
Shortest P
request next P
(SRN) P4
Ps

5 10 15

Fig. 4.2 Scheduling using FCFS and SRN policies

Table 4.3 Performance of FCFS and SRN scheduling

FCFS SRN
Completed Processes Sche Completed Processes Sche
Time id ta W in system duled id ta in system duled
P {Pi} P
P 3 1.00 {e, Ps} P2 P 3 1.00 {P, P} P
P 2 1.00 (P, Pa} P
6 P 4 1.33 {P3,Pa} P3
P 2.50 {Pa} PA P 6 2.00 {Pa} PA
13 P 1.60 {Ps} Ps P 8 1.60 {Ps} Ps
16 P 7 2.33 P 2.33 {}
ia = 5.40 seconds ta= 5.20 seconds
W= 1.75 W= 1.59

Example 4.1 shows that wide disparity exists in the service received by requests
in FCFS scheduling. From this, onecan conclude that short requests (processesPs
and P;) may suffer high weighted turn arounds, i.e., poorer service, compared to
other requests (process P). In a batch processing system, jobs in the batch may
be re-ordered to reduce turn around times and weighted turn arounds of individual
jobs. However this would not reduce the spread of turn around times or increase the
throughput.
Shortest request next (SRN) scheduling The SRN scheduler always schedules the
50 Operating Systenns
requests. Thus, arcquest remains pending until all shorter
shortest of arrived
have been serviced.
Example 4.2 The bottom half of Figure 4.2 shows the scheduling decisions per-
requests
formed by the SRN policy forthe processes of Table 4.2. The right half of Table 4.3
summarizes pertormance of the SRN scheduler. The mean turn around and the mean
weighted turn around are better than in FCFS scheduling because short requests tend
to receive smaller turn around times and weighted turn arounds than in FCFS schedul.
weighted turn are
ing. This degrades the service to long requests however their
donot increase much because their service times are large. The throughput is hiok
than in FCFS scheduling except at the end of the schedule, where it is identical
It is dificult to implement the SRN policy in practice because service times of
processes are not known apriori. Many systems expect users toprovide estimates of
service times of processes. However, results obtained using such data are erratic if
users do not possess sufficient experience in estimating service times. Dependence
on user estimates also leaves the system open to abuse or manipulation, as users
might try to obtain better service by specifying low values for service times of their
processes. Another practical aspect where SRN scheduling does not fare wellis in
the service offered to long processes. A steady stream of short processes arriving in
the system can deny CPUto long processes indefinitely. This is starvation.
Highest Response Ratio Next (HRN) The HRN policy computes the response
ratios of all processes in the system according to Eq. (4.1) and selects the process
with the highest response ratio.

Time since arrival + Service time of the prOceSS

Response ratio = (4.1)
Service time of the process
The response ratio of a newly arrived process is 1. It keeps
rate (1/ service time) as it waits to be serviced; the increasing at ue
increases more rapidly than that of a long process, response ratio of ashort proces
1or scheduling. However, the response ratio of a so shorter processes are lao
long process eventually beco
large enough for the process to get scheduled. This
to the
technique of aging discussed earlier in Sectionfeature provides an effect sii not
4.1.3, so long processes do
[Link] next example
illustrates this property.
Example 4.3 Figure 4.3 summarizes operation of the HRN
five processes Pi PI5. By the time process P| completes, scheduling
processespolcy
Pi2 and
o.. P3
have arrived. P12 has a
larger response ratio than P13, so it is scheduled next. When
It completes,Pi3 hasa higher
after P3, has an even response ratio than before: however, P4, which ar
is scheduled. When P14higher response ratio because it is a shorter process, shorter
so P4
completes, Pi3 has a
process Pis because it has spent a lot of time higher ratio than the
waiting. response
whereas P1s has just arrived.
Hence P3 is scheduled now.
process because it has waited Thus, a long process gets scheduled ahead of ashort
longer.
 Scheduling 151

Process Pu Pi2 P3 P4 P1s

Arrival time 3 8
Service time 3 3 5 2

Completed process Response ratios ofprocesses

Time id ta PI P2 P3 Pi4 Pis Scheduled
1.00 Pu
6
Pl 3 1.00 1.33 1.00 Pi2
8
P2 4 1.33 1.60 2.00 P14
P4 4 2.00 2.00 1.00 Pi3
13 P13 10 2.00 2.67
16
Pis
P1s 2.67

ia= 5.8 seconds

W=1.80

Pu
Pi2
P3
Pi4
Ps

10 15 time
Fig. 4.3 Operation of highest response ratio (HRN) policy

4.3 PREEMPTIVE SCHEDULING POLICIES

In preemptive scheduling, the server can be switched to the processing of a new

request before completing the current request. The preempted request is put back
intothe list of pending requests (see Figure 4.1). Its servicing would be resumed
when it is scheduled again. Thus, a request may have to be scheduled many times
before it completes. In Chapter 2 we saw the preemptive scheduling policies used in
multiprogramming and time sharing operating systems.
We discuss four preemptive scheduling policies in this section:
" Round-robin scheduling with time slicing (RR)
Least completed next (LCN) scheduling
" Shortest time to go (STG) scheduling
" Highest response-rationext (HRN)scheduling.
Figure 4.4 shows the scheduling decisions made by these preemptive scheduling
decisions
policies when an OS executes the processes of Table 4.2 if scheduling
operations. Table 4.4
are made every second and a process does not perform VO
summarizes the operation of preemptive scheduling policies. Table 4.5 summarizes
the performance of these policies.
 152 Operating Systems

P
Round-robin P:
(RR)
P
PA
Ps

Least P
completed next P.
P:
(LCN) P
Ps

P
Shortest
time to go
(STG) P
P

5 10 15
Fig. 4.4 Scheduling using preemptive scheduling policies

Round-Robin scheduling Round-robin (RR) scheduling with time slicing is aime:

at providing fair service to all requests. Time slicing is
used to limit the amount a
CPUtimne a process may use when scheduled. A request is
preempted if the time slic
elapses. This policy maintains the weighted turn arounds of processes
equal to the number of active processes in the systen. approximate
to the nature of Variations may arise only 0u
processes, e.g., an I/O-bound process may lag
processes in its use of the CPU. The RR policy does not fare wellbehind CPU-DOU
in terms of sysiu
performance indices like throughput since it treats all processes alike and docs
give a favored treatment to short processes.
of RR scheduling. Example 4.4 illustrates the perton
Example 4.4 The left part of Table 4.4 summarizes operation of the RR scheduler
with = 1for the five processes shown in Table 4.2. The scheduler makes scheduling
decisions every second. The column Processes shows the queue of processes inhe
system. The scheduler simply selects the first process for scheduling. Therunning
process is preempted when the time slice elapses. It is now put at the end of the
queue. It is assumed that a new process admitted into the system at the same instant
is put into the
queue before the
preempted
Theturn around times and weighted [Link] the processes are as showninthe
turn arounds
leftmost part of Table 4.5. The Ccolumn shows completion times. The turn around
times and weighted turn arounds are inferior compared to non-preemptive policies
This is so because the CPU time is divided among many processes dueto timeslicing
It can be seen that processes P, P, and PA, which arrive at around the sametine
receive wejghred
approximately equal weighted turn arounds. P3 recejves the worst w
 Scheduling 153

Table 4.4 Operation of preemptive scheduling policies

Round-robin Least completed next Shortest time to go

(RR) (LCN) (STG)
Sche Sche Sche
Time Processes duled Processes duled Processes duled
P P P:0 P P:3 P
P P P:l P P:2 P
P,P P P:2. P:0 P P1:l.P:3 P
4
Pi,P3,P2 P P:2,P2:1.P:0 P P:3,P3:2 P;
P3.P Py:2.P:1,Ps:1 P P:3,P:1 P3
[Link],P, P:2.P):2.P:1,P:0 P P:3.P:5 P
P4.P3, P2 P P:2.P:2.P:1.P:1 P P:2.P:5
PB,[Link] P P:2.P:2,P4:1 P P:1.P:5 P
P».P4
Pa Ps
P
PA
P:2.P:2.P4:2
P:2,P4:2,Ps:0 Ps
P P:5
P4:[Link]
P4
Ps
10 Ps.P P P:2,P4:2,.P_:1 Ps Ps:4,Ps:2 Ps
11 P4,Ps P Py:2,P4:2,Ps:2 P P:[Link]:l Ps
12 Ps,P4 P Pa:2,Ps:2 P4 Pa:4 PA
13 Ps. Ps P P4:3,Ps:2 Ps Pa:3 Pa
14 Ps, Pa P P4:3 P: P4:2 P4
15 P4 P. P:4 P P4:1 PA
16

turn around because three processes exist in the system through most of its life. P
receives the best weighted turn around since no other process exists in the system
during the early part of P,'s execution. Thus weighted turm arounds depend on the
load in the system.
Effectiveness of RR scheduling depends on two factors: choice ofô. the time
slice, and nature of processes in the system. As discussed in Chapter 2, if a system
contains n processes and each request by a process consumes exaclyð seconds, the
response time (r) for a request is
n=n X (o + Þ) (4.2)
where o is the scheduling overhead per scheduling decision. Since all processes
requests--the
may not be active at all times-some will be blocked for I/O or other
response time will be governed by the number of active processes rather than byn.
Twoother factors that can affect rt are the variation in CPUtime required by different
requests, and the relationship between Ó and the CPUtime required by a request. Eq.
(4.2) assumes that each request consumes exactlyð seconds and produces a response.
more than
If a request needs more CPU time than ò, then it will have to be scheduled
ofð, rt
once before it can produce a response. Therefore, in certain regions of valuesfact.
4.5 illustrates this
for a request may increase even as Óis reduced. Example
 154 Operating Systems

Table 4.5 Performance of preemptive scheduling policies (C: Completion time of process)

Round-robin Leastconmpleted Shortest time

(RR) next (LCN) to go(STG)
Process C ta C ta C ta

P 4 1.33 3.00 3 1.00

o
P2 2.33 12 10 3.33 6 2.00
P3 2.50 7 4 2.00 5 1.00
P4 16 11 2.20 16 11 2.20 16 11 2.20
Ps 15 6 2.00 14 5 1.67 12 3 1.00

ta = 6.6 Seconds ta =7.8Seconds ta = 5.0 Seconds

W=2.07 W=2.40 W= 1.44

Example 4.5 An OS contains 10 identical processes that were initiated at the same
time. Each process contains 15 identical requests, and each
request
msec of CPUtime. A request is followed by an I/O operation that consumes 20
msec. The system consumes 2 msec in CPUscheduling. For d>20 consumes
10
msec, the first
request by the first process receives a response time of 22 msec and the first request
by the last process receives a response time of 220
msec, so the average response
time is 121 msec. A subsequent request by any
10 x (2+ 20) 10 msec = 210msec since the process process receives a response time of
spends 10 msec in an VO wail
before making the next request. For d= 10 msec, a request would be
10 msec. When scheduled again, it would execute for 10 preempted ater
msec and produce results, so
the response time for the first process is
= 10 x (2 + 10) +(2 + 10)=132
msec
and that for the last process is
= 10 x (2+ 10)+ 10 x (2+
10)= 240 msec.
A subsequent request receives a response time of 10 x
(2+
230 msec. Figure 4.5 illustrates the variation of average 10) + 10time
response x (2+I0)
to second and
subsequent requests for different values of 8. Table 4.6 summarizes performancet
the system for different values of . As expected, the overhead is higher forsmaller
values of 8.
Policies using resource consumption
information
Policies using resource consumption information aim at eliminatin8 some problems
of preemptive policies discussed so far, e.g. poor weighted turn arounds ofshort prë
cesses and starvation of long processes. We discuss the following three scheduling
policies:
1. Least Completed Next
2. Shortest Time to Go (LCN) scheduling
3. Response Ratio
(STG) scheduling
scheduling.
 Scheduling 155

0.3
Response
time
(secs)
0.2

0.1 +

5 10 15 20 25
Time slice (msec) ’
Fig. 4.5 Variation of average response time with time slice

Table 4.6 Performance of RR scheduling for different values of &

Time slice 5 msec 10msec 15 msec 20 msec

Average rn for first request (msec) 248.5 186 208.5 121
Average rt for subsequent request (msec) 270 230 230 210
Number of scheduling decisions 600 300 300 150
Schedule length (msec) 4200 3600 3600 3300
Overhead (percent) 29 17 17 9

Least completed next (LCN) The LCN policy schedules the process that has con
sumed the least amount of CPU time. Thus, the nature of a process, whether CPU
bound or VO-bound, and CPU time requirement of a process do not influence its
progress inthe system. All processes make approximately equal progress in terms of
the CPU time consumed by them, so short processes are guaranteed to finish ahead
of long processes. However, this policy has the familiar drawback of starving long
processes of CPU attention. It also neglectsexisting processes if new processes keep
arriving in the system. So even not-so-long processes tend to suffer starvation or
larger turn around times.
Example 4.6 Operation of the LCNscheduling policy for the five processes shown in
Table 4.2 is summarized in the middle part of Table 4.4. The scheduling information
used by the policy consists of a pair (process id,CPU time consumed. We use the
notation P,:j, where P is aprocess id and t, is the CPU time consumed by it, to denote
this informaion in the column Processes. The scheduler analyses this information and
selects the process that has consumed the least amount of CPUtime. In case of a tie,
selects a process that has not been serviced for a longer period of time.
The turn aroundtimes and weighted turn arounds of the processes are shown in the
second part of Table 4.5. Processing of P,P and P4 is delayed because new processes
156 Operating Systems
before these processes can
arrive in the system and obtain CPU service

system because no new processes

arrive.
service during the latter
progress. Process Py catches up in terms ofLCN
provides poorer
half of
turn around
make furhe
fits ie in te
STG
weighted turm arounds than those provided by RR and
policies (see imes an
and 4.7) because it favors newly arriving processes over
system. e.g.. it tavors P; over P,P; and Ps
over Pa. Examples4A
existin8 processes In he

Shortest time to go (STG) The STG policy is a preemptive version of the

policy. Aprocess is scheduled when its remaining procesSing requirements areSkYth
smallest in the system. The STGpolicy favors a process that is nearing
iTespective of the CPUtime already consumed by it. Thus, along process complneann:
etion
completion may be favored over short processes entering thc system. The long n
cess would finish first, thus improving its weighted turn around, however this
affect tum around times and weighted turn arounds of several short processes in th
System. On the other hand, long processes have problems receiving service in eatl
phases of their operation, so favored service to long processes nearing compleio
may not avoid starvation of long processes.

Example 4.7 The right part of Table 4.4 summarizes performance of the STG schedul.
ing policy for the five processes shown in Table 4.2. The scheduling information usd
by the policy consists of a pair (process id, CPU time needed for completion).We use
the notation P:tj, where P is a process id and t; is the CPU time needed by it for
completion, to denote this information in the column Processes. The scheduler uses
this information for selecting the process that requires the least amount of CPU time
for completion. In case of a tie, it selects a process that has not been serviced for a
longer period of time.
The third part of Table 4.5 shows the turn around times and weighted turn aroundS
of the processes. Note that processes P,P and Ps obtain good turn around timts
and weighted turn arounds. In fact the turn around times and weighted turn around
of all processes other than Pa are better than those provided by the LCN policyHenc ($e
Example 4.6). This is so because their service times are shorter than that of P4.
executionoc
superior service received by them is at the cost of neglecting PA, whose
not even begin until P; is complete. This neglect of long processes canwerebe sen
toariveal
starkly if another process P% with CPUtime requirement of 6seconds aroundtime
t= l second. Its execution would begin only after P4 completes; its turn
and weighted turn around would be 21 seconds and 3.5, respectively.
4.4 SCHEDULING IN PRACTICE
4.4.1 Long, Medium and Short-term Scheduling system
user-centric and thu
An operating system has to provide a suitable combination of user
requests
singl
centric features. It also has to adapt to the nature and number of A
resources. Therc
are expected to arise in its environment, andtothe availability of Concerns.
scheduler and a single scheduling policy cannot address all itscalled thelong-enn
fore, an OS uses an arrangement consisting of three schedulers
 Scheduling 175

4.6 SCHEDULINGIN UNIX

Process states and stale transitions used in Unix have been described in Section 3.5.1.
A Unix process is in one of three modes at any moment:
1. Kemel non-interruptible mode
2. Kemel interruptible mode
3. User mode.
Kemel non-interruptible mode processes enjoy the highest priorities, while user mode
processes have the lowest priorities. The logic behind this priority structure is as fol
lows: A process in the kernel mode has many OS resources allocated to it. If it is
allowed to run at a high priority, it will release these resources sooner. Processes in
the kernelmode that do not hold many OS resources are put in the kernel interruptible
mode.

Event addresses A process that is blocked on an event is said to sleep on it. Unix
uses an interesting arrangement to activate processes sleeping on an event. Instead of
ECBs (see Section 3.3.6), it uses the notion of an event address. A set of addresses
is reserved in the kernel for this purpose. Every event is mapped into one of these
addresses. When a process wishes to sleep on an event, address of the event is com
puted using a special procedure. The state of the process is changed to blocked and
the address of the event is put in its process structure. This address serves as the
description of the event awaited by the process. When an event occurs, the kernel
computes its event address and activates allprocesses sleeping on it.
This arrangement has one drawback-it incurs unnecessary overhead in some
siuations. Several processes may sleep on the same event. The kernel activates all
of them when the event occurs. The processes must themselves decide whether all
of them should resume their execution or only some of them should. For example,
when several processes sleeping due to data access synchronization are activated.
onlyone process should gain access to the data and other activated processes should
goback to sleep. The method of mapping events into addresses adds to this problem.
Ahashing scheme is used for mapping, hence twoor more events may map into the
same event address. Now occurrence of any one of these events would activate al
processes sleeping on all these events. Only some processes sleeping on the correct
event should resume their execution. Allother processes should go back to sleep.
Process priorities Unix is a pure time sharing operating system, so it uses the
round-robin scheduling policy. However, in a departure from pure round-robin, it
dynamically varies the priorities of processes and performs round-robin only for pro
cesses with identical priority. Thus, in essence, it uses multilevel adaptive schedul
ing. The reasons for dynamic variation of process priorities are explained in the
following.
AUser process executes in the user mode when it executes its own code. It
enters the kernel mode when it startsexecuting the kernel code due to an interrupt
178 Operating Systems

whcn processes perform l/0

Operation of aUnix-like scheduling policy
Table 4.13

P P P4 Ps Sche
P
P PT P. T P T P T | duled
Time
0.0 60 0 P
1.0 60
90 30 P
2.0 90
105 45 60 0 P
3.0 45 60
82 22 90 30 60 0 P3
3.1 82 22 90 30 60 6 Pi
4.0 76 30 6
98 38 75 15 63 3
4.1 98 38 75 15 63 9 P2
5.0 38 69 0
79 19 94 34 64 4 60 0 P4
6.0 19 34 4 60
69 9 77 17 62 2 90 30 P3

group. Since the effective priority is the inverse of the priority value computed by
the above equation, the priority of aprocess reduces even when other processes of is
group receive CPU time. Example 4.16 illustrates operation of a fair share scheduler.
Example 4.16 Table 4. 14 depicts scheduling of the processes of Table 4.2 by a Unik
like fair share scheduler. Fields P, T and G contain process priority, CPU time cor
sumed by a process and CPU time consumed by a group of processes, respectively.
Two process groups exist. The first group contains processes P,P,B and Ps, W
the second group contains process P4 all by itself. As expected, process P4 reei
a favored treatment when compared to other processes. In fact, in the period I=5t0
I= 15, it receives every alternate time slice. Processes P2, Ps and Ps suffer because
they belong to the same process group. These facts are reflected in the turn around
times and weightedturn arounds of the processes, which are as shown in Table 4.15.
4.7 SCHEDULING IN LINUX
Linux supports both real time and non-real time applications. Accordingly, ithas
two classes of processes. The real time processes have static priorities between 0and
100, where Ois the highest priority. Real time processes can be scheduled intwo
ways: FIFO or round-robin within each priority level. The kernel associates a lag
with each process to indicate how it
shouldpriorities
Non-real time processes have lower be scheduled.
than all real time processes;their
priorities are dynamic and have numerical values between -20 and 19, where -20
is the highest priority. Effectively, the kernel has (100 + 40) priority levels. Tostart
 Scheduling 179

Table 4.14 Opcration of lair share scheduling

P P Pa Ps Sche
Time P C G C G P C G P C G P C duled
60 0 0 0 P
120 30 30 30 30 30 P
150 45 45 105 0 45 45 45 P
134 22 52 142 30 52 112 0 52 52 P
127 11 56 131 15 56 146 30 56 56 P
58 125 7 58 133 15 58 60 0 0 58
6
PA
29 92 3 29 96 7 29 120 30 30 29 P
7 44 135 31 44 107 3 44 90 15 15 44 P
22 97 15 22 83 1 22 134 37 37 82 0 22 Ps
41 108 7 41 101 0 41 96 18 18 131 30 41 PA
10 20 83 3 20 80 0 20 138 39 39 95 15 20 P
11 40 101 1 40 40 98 19 19 107 7 40 P4
12 20 80 0 20 20 138 39 39 83 3 20 P.
13 40 40 40 98 19 19 101 1 40 P
14 20 20 20 39 80 0 20 Ps
15 40 40 40 19 130 30 40 Ps
16

Table 4.15 Performance of fair share scheduling

Process P Pp P, P4 Ps
Completion time 5 13 14 16
Turn around time 9
Weighted turn around 1.67 3.67 4.00 1.80 2.33

Mean turn around time (ia) 8.0 seconds

Mean weighted turn around ( w) = 2.69

with, each non-real time process has the priority 0. The priority can be varied by the
process itself through the nice or setpriority system calls. However, special privileges
are needed to increase the priority through thenice system call, so processes typically
use this call to lower their priorities when they wish to be nice to other processes.
In addition to such priority variation, the kernel varies the priority of a process to
reflect itsWO-bound or CPU-bound nature. To implement this, the kernel maintains
information about how much CPU time the process has used recently and for how
long it was in the blocked state, and adds a bonus between 5 and-5 to the nice value
of the process. Thus, a highly interactive process would have an effective priority ot
nice -5, while a CPU-bound process would have an effective priority of nice+5,
Due to the multilevel priority structure, the linux kernelorganizes its scheduling
Operating Systems

data as shown in Figure 4. || of Section 4.4.5. Thus, cach priority level

of ready processCs associated with it. To limit the scheduling overhead,
has a lis
a scheduler sehematic analogous to Figure 3.10. Thus, scheduling is not Linux Uses
alter every event handling action. I is performned when the currently executing performed
pro-
cess has to block due to a system call, or when the need resched flag has
by anevent bandling action. This is done while handling expiery of the timebecns set
or while handling an event that activates a higher priority process than the
Cxecuting one. currently
Non-real time processes are scheduled using the notion of a time slice: howeve.
the Linux notion of time slice is different from the notion described in earljer chan
lers. Thc Linux time slice is actually atime quantum that a process can use
over a
periodof time in accordance with its priority. Linux uses time slices in the range
10 mscc to 200 mscc. Contrary to the description in earlier chapters, a
high priority
process has a larger time slice. This does not affect response times in Linux because.
as described above, high priority prOcesses are
interactive in nature.
The Linux scheduler uses two lists of processes, an active list
list. Both lists are ordered by priorities of and an exhausted
processes and use the data structure
described earlier. The scheduler schedules a process from the active list, which uses
time from its time slice. When its time slice is
list. Schedulers in Linux kernel 2.5 and exhausted, it is put into the exhausted
carlier
tation loop when the active list became empty. kernels executed a priority recompu
The loop computed a new time slice
for each process based on its dynamic priority. At the
were transferred to the active list and normal end of the loop, all processes
The Linux 2.6 kernel uses a new
scheduling operation was resumed.
scheduler that
better with the number of processes and CPUs. Theincurs less overhead and scales
scheduler spreads the priority
recomputation overhead throughout the scheduler's operation,
it in the rather than
lumping
recomputation
Cess when the
loop. It achieves this by recomputing the
priority of a pro
process exhausts its time slice and gets moved to the
When the active list becomes empty, the exhausted list.
and exhausted lists. scheduler merely interchanges the ac
The scheduler scalability is ensurcd in
indicate whether the list of processes for two ways. The scheduler has a bit na~
the scheduler tests the a priority level is
empty. When invoked.
sclects the first processflags
of the process lists in the order of reducing priority, and
in
incurs ascheduling overheadthethatfirSt proccdure
Occupied process list it finds. This processes:
docs not depend on the number of ready
it depends only on the
This scheduling is callednumber of scheduling levels,
O(1), i.e., order 1, hence it is bound by a Constant.
kernels used a scheduling. Schedulers in older Linux
synchronization
ditions when many CPUs werelock on the active list of processes to avoid raceactive con-

lists on a per-CPU basis, supported. The Linux 2.6 kernel maintains

which eliminates the associated
delays. This arrangement also synchronization lock and
every time it is scheduled:; it ensures that a process is executed by the Same CPU
helps toensure better cache hit
ratios.