Mesay Aschalew(MSc in Software Engineering)

CHAPTER ONE
INTRODUCTION TO OPERATING
SYSTEM
1 Operating System and System Programming
TOPICS
1.1 What is an operating system
1.2 History of operating systems

Engineering)
Mesay Aschalew(MSc in Software
1.3 The operating system zoo
1.4 Computer hardware review
1.5 Operating system concepts
1.6 System Calls
1.7 Operating system structure

2
INTRODUCTION
 Every general purpose computer consists of the
hardware, operating system, system programs

Engineering)
Mesay Aschalew(MSc in Software
and application programs.
 The hardware consists of memory, CPU, I/O
devices and storage devices.
 System programs consist of compilers, loaders,
editors OS etc.
 The application program consists of business
programs.
3
 Mesay Aschalew(MSc in Software
Engineering)
4
INTRODUCTION
WHAT IS AN OPERATING SYSTEM
 Operating system is a set of special programs
that run on a computer system that allow it to
work properly.

Engineering)
Mesay Aschalew(MSc in Software
 It a software program that acts as an
intermediately between a user of a computer and
the computer hardware.
 It performs basic tasks such as recognizing input
from the keyboard, keeping track of files and
directories on the disk, sending output to the
display screen and controlling peripheral devices.

5
WHAT IS AN OPERATING SYSTEM
 It is an extended machine
� Hides the messy details which must be performed
� Presents user with a virtual machine, easier to use
It is a resource manager

Engineering)
Mesay Aschalew(MSc in Software

� Each program gets time with the resource
� Each program gets space on the resource
 Where the operating system fits in

6
WHAT IS AN OPERATING SYSTEM
 A computer has two modes of operation
� User mode
� Kernel mode
 User mode

Engineering)
Mesay Aschalew(MSc in Software
� To run application programs and some system programs
� Not all instructions are available (privileged instructions such
as taking CPU time, halting the CPU, switching from user to
supervisor mode, etc.)
� The user has to issue system calls (interrupts) to use certain
instructions
 System (kernel) mode
� All instructions are available
� The two modes of operation have to be made available by the
hardware;
� old microprocessors do not have hardware protection.
7
WHAT IS AN OPERATING SYSTEM
 OS is software that runs in supervisory mode. It is
protected from the user tampering the hardware.
 Operating system is designed to perform two basic
functions:

Engineering)
Mesay Aschalew(MSc in Software
� It controls the allocation and use of computing system’s
resources among the various users and tasks.
� It provides an interface between the computer hardware
and the programmer that simplifies and makes feasible for
coding, creation, debugging of application programs.
 In generally, We can view operating system as:
� Resource manager: Manages and allocates hardware and
software resources
� Resource Scheduler: keeps track of the status of each
resource and decides who gets a resource, for how long
and when.
8
WHAT IS AN OPERATING SYSTEM
 Operating System responsible for:
� Control program that prevent both improper use of the resources by
programs and access conflicts.
� It makes that different programs and users running at the same time
do not interfere with each other.

Engineering)
Mesay Aschalew(MSc in Software
� It is also responsible for security, ensuring that unauthorized users do
not access the system.
� Extended machine that hides the messy details which must be
performed or presents a virtual machine to the user that is easier to
use.
� Resource management also includes multiplexing
(sharing resources) in two ways:
 Time multiplexing different programs or users take turns to use a
resource; e.g. CPU use by multiple processes, sharing the printer
 Space multiplexing: different programs or users get part of
resource; e.g. memory, disks
� Maintains fairness and efficiency
9
 HISTORY OF OPERATING SYSTEMS

 First Generation
� vacuum tubes(hardware)
� The earliest electronic digital computers had no operating

Engineering)
Mesay Aschalew(MSc in Software
systems.
� Machines of the time were so primitive that programs were
often entered one bit at time on rows of mechanical
switches (plug boards).
� Programming languages were unknown (not even
assembly languages). Operating systems were unheard of
.
� Programmer control directly all devices. CPU is under
utilization since it was idle most of the time due to slow
speed of I/O devices.
10
HISTORY OF OPERATING SYSTEMS
 Second Generation
� Transistors (hardware) batch systems(software)
� The General Motors Research Laboratories implemented the
first operating systems in early 1950's for their IBM 701.

Engineering)
Mesay Aschalew(MSc in Software
� The system of the time run one job at a time.
� These were called single-stream batch processing systems
because programs and data were submitted in groups or
batches.
� A device read programs written on punched cards
� In order to separate one batch program from the next one ,
control cards were inserted between the two program’s cards.
� Batch systems improved CPU utilization but the rate of
utilization remained very low.
� The interactivity that existed between the first generation
computers and the user disappeared with batch systems.
� Reduce setup time by batching similar jobs.
� Automatically transfers control from one job to another.
11
HISTORY OF OPERATING SYSTEMS

 Third Generation (1965-80)

� Ics (hardware) multiprogramming(software)
� It able to takes better advantage of the batch system by

Engineering)
Mesay Aschalew(MSc in Software
running several jobs at once. Each job is called a process.
� Features of Multiprogramming:
� Memory management: the system must allocate the
memory for several jobs.
� CPU Scheduling: The system must choose among several
jobs ready to run.
� Allocation of devices.

12
HISTORY OF OPERATING SYSTEMS

 Third Generation (1965-80)

� Operating systems designers developed the concept of
multiprogramming in which several jobs are in main
memory at once;

Engineering)
Mesay Aschalew(MSc in Software
� a processor is switched from job to job as needed to keep
several jobs advancing while keeping the peripheral
devices in use.
� For example, on the system with no multiprogramming,
when the current job paused to wait for other I/O operation
to complete, the CPU simply sat idle until the I/O finished.
� The solution for this problem that evolved was to partition
memory into several pieces, with a different job in each
partition. While one job was waiting for I/O to complete,
another job could be using the CPU.
13
HISTORY OF OPERATING SYSTEMS

 Third Generation (1965-80)

� Another major feature in third-generation operating system
was the technique called spooling (simultaneous
peripheral operations on line).

Engineering)
Mesay Aschalew(MSc in Software
� In spooling, a high-speed device like a disk interposed
between a running program and a low-speed device
involved with the program in input/output. Instead of
writing directly to a printer, for example, outputs are written
to the disk.
� Programs can run to completion faster, and other
programs can be initiated sooner when the printer
becomes available, the outputs may be printed.

14
HISTORY OF OPERATING SYSTEMS
 Third Generation (1965-80)
� Timesharing systems: Interactive Computing
 Another feature present in this generation was time-sharing technique,
 a variant of multiprogramming technique that have large number of

Engineering)
Mesay Aschalew(MSc in Software
simultaneous interactive users, in which each user has an on-line (i.e.,
directly connected) terminal.
 Most efficient for many users to share a large computer. Computer
system must respond quickly to user requests, otherwise user
productivity could suffer.
 The CPU is shared between several processes.
 Each process belongs to a user and I/O is to/from a separate terminal
for each user
� Parallel Systems : multiprocessor systems with more than
one CPU in close communication.
� Tightly coupled system-processors share memory and a
clock ; communication usually takes place through the
shared memory
15
HISTORY OF OPERATING SYSTEMS

 Fourth Generation
� With the development of LSI (Large Scale Integration)
circuits, chips, operating system entered in the system
entered in the personal computer and the workstation age.

Engineering)
Mesay Aschalew(MSc in Software
� PCs provide convenience over efficiency.
� Commercial software's started to be developed
� Distributed systems
 distribute the communication among several physical processors.
� Loosely coupled system
 each processor has its own local memory;
 processors communicate with one another through various
communication lines, such as high speed networks.

16
HISTORY OF OPERATING SYSTEMS

 Fourth Generation
� Real time systems
 Were originally used to control autonomous/Existing as an
independent entity/ systems such as satellites, robots and

Engineering)
Mesay Aschalew(MSc in Software
communication systems.
 It is one that must react to input and responds them quickly. It also has
well defined, fixed time constraint.

17
THE OPERATING SYSTEM ZOO/ TYPES OF
OPERATING SYSTEM

 Mainframe Operating Systems

� The operating systems for mainframes are heavily
oriented toward processing many jobs at once, most of

Engineering)
Mesay Aschalew(MSc in Software
which need prodigious amounts of VO
� They typically offer three kinds of services:
 Batch: system is one that processes routine jobs without any
interactive user present.
 Transaction processing: systems handle large numbers of small
requests, for example, check processing at a bank or airline
reservations.
 Timesharing: systems allow multiple remote users to run jobs on the
computer at once, such as querying a big database.
� An example mainframe operating system is OS/390
 Gradually being replaced by UNIX variants such as Linux.
18
THE OPERATING SYSTEM ZOO/ TYPES OF
OPERATING SYSTEM

 Server Operating Systems

� They run on servers, which are either very large personal
computers, workstations, or even mainframes.

Engineering)
Mesay Aschalew(MSc in Software
� They serve multiple users at once over a network and
allow the users to share hardware and software resources.
� Internet providers run many server machines to support
their customers and Websites use servers to store the
Web pages and handle the incoming requests.
� Typical server operating systems
 Solaris, FreeBSD, Linux and Windows Server

19
THE OPERATING SYSTEM ZOO/ TYPES OF
OPERATING SYSTEM

 Multiprocessor Operating Systems

� An increasingly common way to get major-league
computing power is to connect multiple CPUs into a single

Engineering)
Mesay Aschalew(MSc in Software
system.
� Depending on precisely how they are connected and what
is shared, these systems are called parallel computers,
multi computers, or multiprocessors.
� They need special operating systems, but often these are
variations on the server operating systems, with special
features for communication, connectivity, and consistency.
� Many popular operating systems, including Windows and
Linux, run on multiprocessors.
20
THE OPERATING SYSTEM ZOO/ TYPES OF
OPERATING SYSTEM

 Personal Computer Operating Systems

� Their job is to provide good support to a single user.

Engineering)
Mesay Aschalew(MSc in Software
� They are widely used for word processing, spreadsheets,
and Internet access.
� Common examples are Linux, FreeBSD, Windows Vista,
and the Macintosh operating system.
• Handheld Computer Operating Systems
� A handheld computer or PDA (Personal Digital Assistant)
is a small computer that fits in a shirt pocket and performs
a small number of functions, such as an electronic address
book and memo pad.
� Two of the most popular operating systems for handhelds
are Symbian OS and Palm OS 21
THE OPERATING SYSTEM ZOO/ TYPES OF
OPERATING SYSTEM

 Embedded Operating Systems

� Embedded systems run on the computers that control
devices that are not generally thought of as computers and

Engineering)
Mesay Aschalew(MSc in Software
which do not accept user-installed software.
� Typical examples are microwave ovens, TV sets, cars
� Systems such as QNX and VxWorks are popular in this
domain

22
THE OPERATING SYSTEM ZOO/ TYPES OF
OPERATING SYSTEM
• Sensor Node Operating Systems
� Networks of tiny sensor nodes are being deployed for
numerous purposes. (detect fires in forests, measure
temperature and precipitation for weather forecasting)

Engineering)
Mesay Aschalew(MSc in Software
� These nodes are tiny computers that communicate with each
other and with a base station using wireless communication.
� Each sensor node is a real computer, with a CPU, RAM,
ROM, and one or more environmental sensors.
� It runs a small, but real operating system, usually one that is
event driven, responding to external events or making
measurements periodically based on an internal clock.
� The operating system has to be small and simple because
the nodes have little RAM and battery lifetime is a major
issue.
� TinyOS is a well-known operating system for a sensor node.

23
THE OPERATING SYSTEM ZOO/ TYPES OF
OPERATING SYSTEM

• Real-Time Operating Systems

� These systems are characterized by having time as a key
parameter.

Engineering)
Mesay Aschalew(MSc in Software
� Often there are hard deadlines that must be met.
� These systems must provide absolute guarantees that a
certain action will occur by a certain time.
� Categorized as hard and soft real-time systems.
� An example of this type of real-time system is e-Cos.
• Smart Card Operating Systems
� The smallest operating systems run on smart cards, which
are credit card sized devices containing a CPU chip.
� Some of them can handle only a single function, such as
electronic payments, but others can handle multiple
functions on the same smart card. 24
COMPUTER HARDWARE REVIEW

 An operating system is intimately tied to the

hardware of the computer it runs on.

Engineering)
Mesay Aschalew(MSc in Software
 It extends the computer’s instruction set and
manages its hardware resources

Fig. Some of the components of a simple personal computer

25
COMPUTER HARDWARE REVIEW- PROCESSOR
 It fetches instructions from memory and executes
them.

Engineering)
Mesay Aschalew(MSc in Software
 The basic cycle of every CPU is to
� fetch the first instruction from memory,
� decode it to determine its type and operands,
� execute it, and
� then fetch, decode, and execute subsequent
instructions.
 The cycle is repeated until the program finishes. In
this way, programs are carried out.

26
COMPUTER HARDWARE REVIEW- PROCESSOR
 all CPUs contain some registers inside to hold key
variables and temporary results.

Engineering)
Mesay Aschalew(MSc in Software
� program counter, which contains the memory address
of the next instruction to be fetched.
� Another register is the stack pointer, which points to
the top of the current stack in memory
� Another register is the PSW (Program Status Word).
 This register contains the condition code bits, which are set by
comparison instructions, the CPU priority, the mode (user or
kernel), and various other control bits.

27
COMPUTER HARDWARE REVIEW- PROCESSOR
 Many modern CPUs have facilities for executing
more than one instruction at the same time.

Engineering)
Mesay Aschalew(MSc in Software
 For example, a CPU might have separate fetch,
decode, and execute units, so that while it is
executing instruction n, it could also be decoding
instruction n + 1 and fetching instruction n + 2.
 Such an organization is called a pipeline.

(a) A three-stage
pipeline
(b) A superscalar CPU

28
COMPUTER HARDWARE REVIEW- MEMORY
 The second major component in any computer is
the memory.

Engineering)
Mesay Aschalew(MSc in Software
 Ideally, a memory should be extremely fast (faster
than executing an instruction so that the CPU is not
held up by the memory)

29
COMPUTER HARDWARE REVIEW- MEMORY
 The top layer consists of the registers internal to the
CPU.

Engineering)
Mesay Aschalew(MSc in Software
 They are made of the same material as the CPU
and are thus just as fast as the CPU.
 Consequently, there is no delay in accessing them.
The storage capacity available in them is typically
32 × 32 bits on a 32-bit CPU and 64 × 64 bits on a
64-bit CPU.
 Less than 1 KB in both cases. Programs must
manage the registers (i.e., decide what to keep in
them) themselves, in software.
30
COMPUTER HARDWARE REVIEW- DISK
 At any given arm position, each of the heads can read
an annular region called a track.

Engineering)
Mesay Aschalew(MSc in Software
 , all the tracks for a given arm position form a cylinder.
 Many computers support a scheme known as virtual
memory
 Memory Re-mapping is done by a part of the CPU
called the MMU (Memory Management Unit)
 In a multiprogramming system, when switching from one
program to another, sometimes called a context
switch,
� it may be necessary to flush all modified blocks from the
cache and change the mapping registers in the MMU
31
 Mesay Aschalew(MSc in Software
Engineering)
32
DISK
REVIEW-
COMPUTER HARDWARE
COMPUTER HARDWARE REVIEW- I/O DEVICES
 The CPU and memory are not the only resources
that the operating system must manage.

Engineering)
Mesay Aschalew(MSc in Software
 I/O devices also interact heavily with the operating
system
 I/O devices generally consist of two parts:
� a controller and the device itself.
 The controller is a chip or a set of chips that
physically controls the device.
 It accepts commands from the operating system,
for example, to read data from the device, and
carries them out. 33
 COMPUTER HARDWARE REVIEW- I/O DEVICES
 The software that talks to a controller, giving it
commands and accepting responses, is called a
device driver.

Engineering)
Mesay Aschalew(MSc in Software
 DMA (Direct Memory Access) chip that can control
the flow of bits between memory and some controller
without constant CPU intervention.

34
(a) Steps in starting an I/O device and getting interrupt
(b) How the CPU is interrupted
 COMPUTER HARDWARE REVIEW- BUSES

Engineering)
Mesay Aschalew(MSc in Software
• This system has many buses (e.g., cache, memory, PCIe, PCI,
USB, SATA, and DMI(Direct Media Interface)), each with a
different transfer rate and function.
• The operating system must be aware of all of them for
configuration and management. 35
• The main bus is the PCIe(Peripheral Component Interconnect
Express) bus
COMPUTER HARDWARE REVIEW-
STRUCTURE OF A LARGE PENTIUM SYSTEM

Engineering)
Mesay Aschalew(MSc in Software
36
BOOTING THE COMPUTER
 Every PC contains a motherboard having a
program called the system BIOS (Basic Input
Output System)

Engineering)
Mesay Aschalew(MSc in Software
 The BIOS contains low-level I/O software, including
procedures to read the keyboard, write to the
screen, and do disk I/O, among other things.
 Nowadays, it is held in a flash RAM, which is non-
volatile but which can be updated by the operating
system when bugs are found in the BIOS.

37
 Mesay Aschalew(MSc in Software
Engineering)
38
BOOTING THE COMPUTER
OPERATING SYSTEM CONCEPTS
 Processes
 Address Spaces

Engineering)
Mesay Aschalew(MSc in Software
 File System
 Input/Output
 Protection
 The Shell

39
OPERATING SYSTEM CONCEPTS (1) -
PROCESSES
 A process is a program in execution
 Swapping of a process – Process table entry
 System calls to create and terminate processes
 System calls to allocate/deallocate memory
 System calls for communication - signals

40
OPERATING SYSTEM CONCEPTS (2) -
PROCESSES

 A process tree
� A created two child processes, B and C
� B created three child processes, D, E, and F

41
OPERATING SYSTEM CONCEPTS (3) -
DEADLOCKS

(a) A potential deadlock. (b) an actual deadlock.

42
OPERATING SYSTEM CONCEPTS (4) - FILES
 Present the programmer with nice, clean, abstract,
device-independent files.
 Concept of directory to group files together
 System calls to create/remove directories and
create/remove files. Hierarchies.
 Process trees != Directories
 A file can be specified by a path name: absolute (from
root), relative (from current working directory).

43
OPERATING SYSTEM CONCEPTS (5) - FILES

File system for a university department

44
OPERATING SYSTEM CONCEPTS (6) - FILES
 Protection of files and directories, e.g. UNIX the rwx bits: 9
bits (owner/group/others) rwxr-xr--
 File Descriptor: a number assigned to a file.
 Mounting file systems.
 Special files: block special files, character special files –
standard input (fd=0), standard output (fd=1), standard error
(fd=2).

45
OPERATING SYSTEM CONCEPTS (7) -
FILES

 Before mounting,
� files on floppy are inaccessible
 After mounting floppy on b,
� files on floppy are part of file hierarchy

46
OPERATING SYSTEM CONCEPTS (8) -
PIPES

Two processes connected by a pipe. Read/Write -

transparent for processes.

47
OPERATING SYSTEM CONCEPTS (8) -
SHELL
 The shell is a program that acts as an interface
between the user and the OS.
 Unix: several shells (e.g. csh, ksh).
 MSDOS: command prompt.
 Prompt, process, std input, output, creates processes.

48
SYSTEM CALLS
 operating systems have two main functions:
� providing abstractions to user programs and
� managing the computer’s resources

Engineering)
Mesay Aschalew(MSc in Software
 making a system call is like making a special kind of
procedure call, only system calls enter the kernel and
procedure calls do not.
 A system call is a mechanism used by programs to
request services from the operating system (OS).
 let us take a quick look at the read system call. As
mentioned above, it has three parameters:
� the first one specifying the file,
� the second one pointing to the buffer, and
49
� the third one giving the number of bytes to read.
 SYSTEM CALLS

Engineering)
Mesay Aschalew(MSc in Software
50

Figure. The 11 steps in making the system call read(fd, buffer, nbytes).
SYSTEM CALLS
 1. Process Control
 The following services are provided by Process
Control System calls that are used to control a

Engineering)
Mesay Aschalew(MSc in Software
process.
� To forcefully abort the process, simply end it normally.
� Execute a process after loading it into the main memory.
� Terminate the current process before starting a new
one.
� Wait for a process to complete running. Wait until a
specific event happens, then announce it once it has.
� Allocate memory to a process, then release the memory
if the process is terminated.
51
SYSTEM CALLS
 2. File Management
 The following services are provided by system call

Engineering)
Mesay Aschalew(MSc in Software
for file management:
� Making and erasing files
� Open the file, then close it.
� Write to a specific file, read from a specific file.
� To obtain a file's attribute and to change a file's attribute

52
SYSTEM CALLS
 3. Device Management
 The following services are offered by a system call that

Engineering)
Mesay Aschalew(MSc in Software
controls I/O devices:
� Devices might be needed while a process is running. such as
access to the file system, I/O devices, main memory, etc.
� As a result, it can ask for a device and then release it once
the task is complete.
� when a requested device is granted access by the process. It
is capable of reading, writing, and repositioning operations.
� In order to obtain or modify a specific device's attribute.
� To detach a device from the processor that is currently
executing a command, the call can be made.

53
SYSTEM CALLS
 4. Information Maintenance
Considering this, the services offered by this type of

Engineering)
Mesay Aschalew(MSc in Software
system call are:
 Obtain the system's time or date. Set the system's time or
date.
 Obtain system-related information. Configure the system data.
 Obtain the characteristics of a specific operating system
process. Alternatively, of a specific file on the system or on any
attached devices.
 Set the characteristics of a specific operating system process.
Alternatively, of a specific file on the system or on any attached
devices.

54
SYSTEM CALLS
 5. Communication
Such a system call facilitates the system's network

Engineering)
Mesay Aschalew(MSc in Software
connection.
� Open a fresh connection to send the data. After the
transmission is finished, disconnect from the
connection.
� On a particular connection, send a message. Obtain
communication from a specific connection.
� Identify and connect a specific remote device to the
network.
� Remove a specific remote computer or device from the
network.
55
SYSTEM CALLS
 System Calls for Process Management

Engineering)
Mesay Aschalew(MSc in Software
56
SYSTEM CALLS
 System Calls for Process Management

Engineering)
Mesay Aschalew(MSc in Software
57
SYSTEM CALLS
 System Calls for Process Management
 Some of the major POSIX system calls. The return

Engineering)
Mesay Aschalew(MSc in Software
code s is −1 if an error has occurred.
 The return codes are as follows: pid is a process id,
fd is a file descriptor, n is a byte count, position is
an offset within the file, and seconds is the elapsed
time.

58
SYSTEM CALLS
 Microsoft Windows System Call Table
(XP/2003/Vista/2008/7/2012/8/10) ([Link])

Engineering)
Mesay Aschalew(MSc in Software
59
SYSTEM CALLS
 Example of System Calls in Windows and Unix

Engineering)
Mesay Aschalew(MSc in Software
60
OPERATING SYSTEM STRUCTURE
 Monolithic Systems
 Layered Systems

Engineering)
Mesay Aschalew(MSc in Software
 Microkernels
 Client-Server Model
 Virtual Machines

61
OPERATING SYSTEM STRUCTURE
 Monolithic Systems
 in the monolithic approach the entire operating

Engineering)
Mesay Aschalew(MSc in Software
system runs as a single program in kernel mode
 This organization suggests a basic structure for the
operating system:
� 1. A main program that invokes the requested service
procedure.
� 2. A set of service procedures that carry out the system
calls.
� 3. A set of utility procedures that help the service
procedures.
62
OPERATING SYSTEM STRUCTURE
 Monolithic Systems
 In addition to the core operating system that is

Engineering)
Mesay Aschalew(MSc in Software
loaded when the computer is booted, many
operating systems support loadable extensions,
such as I/O device drivers and file systems.
 These components are loaded on demand. In UNIX
they are called shared libraries.
 In Windows they are called DLLs (Dynamic-Link
Libraries).

63
OPERATING SYSTEM STRUCTURE
 Monolithic Systems

Engineering)
Mesay Aschalew(MSc in Software
64
OPERATING SYSTEM STRUCTURE
 Layered Systems
 is to organize the operating system as a hierarchy

Engineering)
Mesay Aschalew(MSc in Software
of layers, each one constructed upon the one below
it.
 The system had six layers,

65
OPERATING SYSTEM STRUCTURE
 Microkernels
 Client-Server Model

Engineering)
Mesay Aschalew(MSc in Software
 Virtual Machines

66
 Mesay Aschalew(MSc in Software Engineering)
THANK YOU
67 Read for more : Modern Operating Systems (4th
Edition)
PROCESS MANAGEMENT AND INTER-
PROCESS COMMUNICATION
Chapter Two
 PROCESS CONCEPTS
 A question that arises in discussing operating systems
involves what to call all
 the CPU activities. A batch system executes jobs,
whereas a time-shared system has user’s programs, or
tasks.
 Even on a single-user system such as Microsoft
Windows, a user may be able to run several programs
at one time.
 In many respects, all these activities are similar, so we
call all of them processes.
• Process is a dynamic entity i.e. a program in execution.
• Process exist in a limited span of time.
• A process has object program, data, resources and the
status of the process on execution.
• A process is not a closed system; there is a communication
 PROGRAMS VS. PROCESS

Types of process
There are two types of process
1. Sequential process:
the execution sequence in sequential fashion, i.e. at any point in time
at most one instruction is executed.
2. Concurrent process
a) True concurrency: two or more processes executing at the
same time; it implies a need for more than one processor.
b) Apparent concurrency: switching from one process to the other.
In both cases if a snapshot of the system is taken, several processes
will be found in partial execution.
PROCESS CONCEPTS
 Process – a program in execution;
 Multiple parts
� The program code, also called text section
� Current activity including program counter, processor
registers
� Stack containing temporary data
 4 Function parameters, return addresses, local variables
� Data section containing global variables
� Heap containing memory dynamically allocated during
run time
PROCESS CONCEPTS
 Program is passive entity stored on disk
(executable file), process is active
� Program becomes process when executable file loaded
into memory
 Execution of program started via GUI mouse clicks,
command line entry of its name, etc
 One program can be several processes
� Consider multiple users executing the same program
PROCESS CREATION
There are four principal events which cause process to be
created
1. System initialization: when OS boots
� Some are foreground process that interact with users and
work for them.
� Others are background processes which have some
specific functions; e.g. process that check emails.
� Background processes are called daemons.

73
2. Execution of a process creation system call by a
running process (fork in Unix and creatProcess in
windows)
3. A user request to create a new process.
4. Initiation of a batch job (in large mainframes)

74
PROCESS TERMINATION
Events which cause process termination
1. Normal exit (voluntary): a process has finished execution.
2. Error exit (voluntary): a fatal error has occurred and a
process cannot continue; e.g. cc abc.c but the file doesn’t
exist.
3. Fatal error (involuntary): mostly due to program bug; e.g.
executing an illegal instruction, referencing non existing
memory, division by zero, …

75
4. Killed by another process (involuntary): the killer must
have an authorization (kill in Unix and terminate Process
in Windows)
 The operating system is responsible for the following
activities in relation to process management.
� Process creation and termination
� Process suspension and resumption
� Provision of mechanisms for
 Process synchronization
 Process communication

76
PROCESS STATE AND PROCESS STATE
TRANSITION
• As the process executes, it changes state.
 A process may be in one of the following states.

Figure: process in different state

� New State: The process being created.

� Running State: A process is said to be running if it has the
CPU, that is, process actually using the CPU at that particular
instant.
77
� Blocked (or waiting) State: A process is said to be blocked if
it is waiting for some event to happen such as an I/O
completion before it can proceed.
� A process is unable to run until some external event happens.

� Ready State: A process is said to be ready if it use a CPU if

one were available. A ready state process is runnable but
temporarily stopped running to let another process run.
� Terminated state: The process has finished execution.

78
 The three main state described as
follow

• Operating system maintains lists of ready and waiting

processes.

Ready List Waiting Lists P10

P1
Ordered P11 Unordered P9

P20 P4
.
.
. 79
.
.
.
PROCESS STATE TRANSITIONS
 There are four state transitions two of them caused by
the process scheduler.
 Process scheduler is a part of OS that decides which
process should get the CPU next.
1. Ready Running
� The assignment of the CPU to the first process on the ready
list is called dispatching and it is performed by a system
entity called dispatcher.
Dispatch (process_name):Ready Running

80
2. Running Ready
� A process may be stopped by a clock interrupt if it doesn’t
relinquish (release) the CPU before the allocated time
expires.
Timeout (process name):Running Ready

3. Running waiting
� During I/O a process voluntarily relinquishes the CPU.
Wait(process_name): Running waiting

4. Waiting Ready
� When I/O finishes
Wakeup(process_name): waiting Ready

81
IMPLEMENTATION OF PROCESSES
 The OS maintains a table (an array of structures),
called the Process Table or Process Control
Block.
 It enables an interrupted process to resume
normally.
 It is an area of memory containing all the relevant
information associated with each process.

82
 These may include
� Process state
� Program counter
� Stack pointer
� Value of CPU registers when the process is suspended.
� CPU scheduling information such as priority
� The area of memory used by the process(memory
management information)
� Accounting information: amount of CPU time used, time limits,
process no, etc.

83
� I/O status information: list of I/O devices such as tape derives
allocated for the process, a list of open files, etc.
� Pointer to the next process’s PCB

Pointer Process
State
Process number

Program counter

Register

Memory limits

List of open files

.
.
.
84
 The information is system dependent; e.g., there is an
entry “parent process” in UNIX but none in windows.
 All PCBs are linked to form a list, which is accessed by a
pointer in a central table.
 When a process changes state from ready to running, its
PCB is used by the OS to restart.
 The use of PCB will be shown later in Process
Scheduling.

85
THREADS
 A process has an address space (containing program
text and data) and a single thread of control, as well as
other resources such as open files, child processes,
accounting information, etc.
 The thread has a program counter, registers, and a stack
 Thread allows multiple executions to take place in the
same process environment, called multithreading.

86
� (a) Three processes each with one thread. (b) One
process with three threads.
• Each thread has a program counter, registers stack, and
state; but all threads of a process share address space,
global variables and other resources such as open files,
etc.

87
 The first column lists some items shared by all threads in a
process.
 The second one lists some items private to each thread.
 Threads are sometimes called light weight processes.
 Threads take turns in running

88
THREAD USAGE-WHY DO WE NEED
THREADS?

 E.g., a word processor has different parts; parts for

� Interacting with the user
� Formatting the page as soon as the changes are made
� Timed savings (for auto recovery)
� Spelling and grammar checking

89
Thread Example-web server

. .

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Web server code

(a) Dispatcher thread. (b) Worker thread.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Web server

• If page is not there, then thread blocks

• CPU does nothing while it waits for page
• Thread structure enables server to instantiate another
page and get something done

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Another way to do the same thing-finite
state machine

• If page is not there, use a non-blocking call

• When thread returns page send interrupt to CPU,
(signal)
• Causes process context switch (expensive)

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Three ways to build the server

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Reasons to use threads

• Enables parallelism (web server) with blocking system

calls
• Threads are faster to create and destroy then
processes
• Natural for multiple cores
• Easy programming model

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Threads are lightweight

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Threads are like processes

• Have same states

• Running
• Ready
• Blocked
• Have their own stacks –same as processes
• Stacks contain frames for (un-returned) procedure calls
• Local variables
• Return address to use when procedure comes back

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
How do threads work?

• Start with one thread in a process

• Thread contains (id, registers, attributes)
• Use library call to create new threads and to use threads
• Thread_create includes parameter indicating what procedure
to run
• Thread_exit causes thread to exit and disappear (can’t
schedule it)
• Thread_join Thread blocks until another thread finishes its
work
• Thread_yield
POSIX Threads (Pthreads)

Pthreads are IEEE Unix standard library calls

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
A Pthreads example-”Hello,world”

...

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Implementing Threads in User Space

(a) A user-level threads package. (b) A threads package managed

by the kernel.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Threads in user space-the good

• Thread table contains info about threads (program

counter, stack pointer...) so that run time system can
manage them
• If thread blocks, run time system stores thread info in
table and finds new thread to run.
• State save and scheduling are invoked faster then
kernel call (no trap, no cache flush)

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Threads in user space-the bad

• Can’t let thread execute system call which blocks

because it will block all of the other threads
• No elegant solution
• Hack system library to avoid blocking calls
• Could use select system calls-in some versions of
Unix which do same thing
• Threads don’t voluntarily give up CPU
• Could interrupt periodically to give control to run
time system
• Overhead of this solution is a problem…..

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Threads in kernel space-the good

• Kernel keeps same thread table as user table

• If thread blocks, kernel just picks another one
Not necessarily from same process!
• The bad-expensive to manage the threads in the
kernel and takes valuable kernel space

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Threads in kernel space-the bad

• Expensive to manage the threads in the kernel and

takes valuable kernel space
• How do we get the advantages of both approaches,
without the disadvantages?

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Hybrid approach
Multiplex user-level threads onto kernel level threads

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Hybrid

• Kernel is aware of kernel threads only

• User level threads are scheduled, created destroyed
independently of kernel thread
• Programmer determines how many user level and
how many kernel level threads to use

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Scheduler activations-Upcalls

• Want the run time system to switch threads when a

thread blocks
• Associate a virtual processor with each process
• Run time system allocates threads to virtual processors
• Kernel notifies the run time system that
• a thread has blocked
• passes info to RTS (thread id…)
• RTS schedules another thread

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Pop-Up Threads
(How to handle message arrivals in distributed systems)

Create a new thread when a message arrives

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Why pop ups?

• Could use thread which blocks on a receive

system call and processes messages when
they arrive
• Means that you have to restore the history of
the thread each time a message arrives
• Pop ups are entirely new-nothing to restore
• They are faster

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Adding threads to an OS-problems

• How do we implement variables which should be

global to a thread but not to the entire program?
• Example: Thread wants access to a file, Unix grants
access via global errno
• Race ensues-thread 1 can get the wrong permission
because thread 2 over-writes it

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Thread 1 gets the wrong permission

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Solution-Create private global variables

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
1. Simplifying the programming model since many
activities are going on at once.
2. They are easier to create and destroy than processes
since they don't have any resources attached to them
3. Performance improves by overlapping activities if there
is too much I/O
4. Real parallelism is possible if there are multiple CPUs
Note: implementation details are beyond the scope of the
course (distributed systems).

114
INTER-PROCESS COMMUNICATION
 Processes frequently need to communicate with other
processes.
 Processes may share a memory area or a file for
communication
 There are three issues related to IPC
1. How can one process pass information to another.
2. How can we make two or more processes don’t interfere
with each other when engaged in critical activities; e.g.,
getting the last 1MB of memory

115
3. Sequencing of events when dependency exist; e.g., one
process produces data and another process consumes it.
� These issues are also applied to threads; the first is easy for
thread since they share a common address space.
Race conditions
� Arises as a result of sharing some resources
� E.g. printer spooler
� When a process wants to print a file, it enters a file name on
a special spooler directory

116
� Another process, the printer daemon, periodically checks to
see if there are any files to be printed, and if there are it
prints them and removes from the directory.
� Recall the daemon is a process running in the back ground
and started automatically when the system is booted.
� Assume that the spooler directory has a large number of
slots, numbered 0,1,2,3,…,n, each capable of holding a file
name.

117
� There are two shared variables (shared by all processes)
� out-points to the next file to be printed
� in-points to the next free slot in the directory

118
 Then the following may happen
� Process A reads in and stores the value 7 in a local variable.
� A clock interrupt occurs and the CPU is switched to B.
� B also reads in and stores the value 7 in a local variable.
� It stores the name of its file in slot 7 and updates in to be 8.
� A runs again; it runs its file name in slot 7, erasing the file
name that B wrote.
� It updates in to be 8.

119
 The printer daemon will not notice this; but B will never
receive any output
 Situation like this, where two or more process are reading
and writing some shared data and the final result
depends on who runs precisely when are called race
conditions.

120
PROCESS SCHEDULING
• When a process is multi programmed, it frequently has multiple
processes competing for the CPU at the same time.
• If only one CPU is available a choice has to be made which
process to run next.
• Multiprogramming - aims to increase the output
• Time sharing - to allow all users use the CPU equally

121
SCHEDULING QUEUES
• As the process enters the system or when a running
process is interrupted, it is put into a ready queue
• There are also device queues(waiting queues), where each
device has its own device queue.
• All are generally stored in a queue(linked list), not
necessarily a FIFO queue.

122
SCHEDULING LEVELS
 Short-term (CPU scheduler)—selects from jobs
in memory those jobs that are ready to execute
and allocates the CPU to them.
 Medium-term—used especially with time-
sharing systems as an intermediate scheduling
level.
� A swapping scheme is implemented to remove
partially run programs from memory and reinstate
them later to continue where they left off.
 Long-term (job scheduler)—determines which
jobs are brought into memory for processing.

123
CONTEXT SWITCHING
 Switching the CPU to another process requires
saving the environment of the old process and
loading the saved environment of the new process.
This task is called context switching.
 Context switch time also called dispatch latency is
an overhead /is the wasted in the transition by the
OS/ and it depends on the hardware (1 to 100ms)
 It is sometimes a performance bottle neck.

124
125
SCHEDULING CRITERIA
 A good scheduling algorithm must ensure the following
� Fairness- make sure that each process gets its fair share of
the CPU.
� Efficiency (CPU utilization)- keep the CPU as busy as
possible.
� Response time- minimize the response time for interactive
users
� Turnaround time- minimize the time batch users must wait for
output.
� Throughput- maximize the number of process executed per a
unit of time.
 Some of these goals are contradictory (maintaining
fairness means an increase context switching that
decreasing efficiency)

126
PROCESS BEHAVIOR
 The success of CPU scheduling depends on the
following observed property of a process.
 Execution consists of a cycle of CPU execution and I/O
wait.
 Process alternates back and forth between these two
cycles.
 Process execution starts with CPU burst, followed by I/O
burst, followed by CPU burst then by another I/O wait
and so on.
 The last CPU burst will end with a system request to
terminate execution.

127
Process can be
� CPU bound: use the CPU intensively with little I/O (a)
� I/O bound: spend most of their time waiting for I/O (b)

128
SCHEDULING ALGORITHMS
 There are two types of scheduling algorithms

A. Preemptive- The OS can stop the running process even

though it has no I/O. most OSs are based on this.
(fairness and response time is good but less efficient)
B. Non preemptive- once the CPU has been allocated to a
process. It can be keep until it wants to release it either
by terminating or by requesting I/O.
� They are simple and easy.
� Efficient but not fair and response time is high

129
FIRST-COME-FIRST-SERVED SCHEDULING
(FCFSS)
 Basic Concept
� The process that requested the CPU first is allocated the CPU
and keeps it until it released it, either due to completion or
request of an I/O operation. The process that has been in the
ready queue the longest is selected for running.
� Its selection function is waiting time and it uses non
preemptive scheduling/decision mode
� Process execution begins with CPU burst, followed by an I/O
burst, followed by another CPU burst, then by another I/O
burst and so on.

130
Illustration
� Consider the following processes arrive at time 0
Process P1 P2 P3
CPU Burst/Service Time (in ms) 24 3 3
Case i. If they arrive in the order of P1, P2, P3
Process P1 P2 P3
Service Time (T-s) 24 3 3
Turn around time (T-r) 24 27 30
Response time 0 24 27
T-r/Ts 1 9 10
Average response time = (0+24+27)/3 = 17
Average turn around time = (24+27+30)/3=27
Throughput = 3/30= 1/10

131
Case ii. If they arrive in the order of P3, P2, P1
Process P3 P2 P1
Service Time (T-s) 3 3 24
Turn around time (T-r) 3 6 30
Response time 0 3 6
T-r/Ts 1 2 1.25
Average response time = (0+3+6)/3 = 3
Average turn around time = (3+6+30)/3=13
Throughput = 3/30= 1/10

132
 � Consider the following processes arrive at time 0, 1, 2, 3
respectively
Process P1 P2 P3 P4
Arrival Time (Ta) 0 1 2 3
Service Time (T-s) 1 100 1 100
Turn around time (T-r) 1 100 100 199
Response time 0 0 99 99
T-r/Ts 1 1 100 1.99
Average response time = (0+0+99+99)/4 = 49.5
Average turn around time =(1+100+100+199)/4=100
Throughput = 4/202

133
 Advantages
� It is the simplest of all non-preemptive scheduling algorithms: process
selection & maintenance of the queue is simple
� There is a minimum overhead and no starvation
� It is often combined with priority scheduling to provide efficiency
 Drawbacks
� Poor CPU and I/O utilization: CPU will be idle when a process is
blocked for some I/O operation
� Poor and unpredictable performance: it depends on the arrival of
processes
� Unfair CPU allocation: If a big process is executing, all other
processes will be forced to wait for a long time until the process
releases the CPU. It performs much better for long processes than
short ones

134
SHORTEST JOB FIRST SCHEDULING (SJFS)
Basic Concept
� Process with the shortest expected processing time (CPU
burst) is selected next
� Its selection function is execution time and it uses non
preemptive scheduling/decision mode
Illustration
Consider the following processes arrive at time 0
Process P1 P2 P3
CPU Burst (in ms) 24 3 3

135
SHORTEST JOB FIRST SCHEDULING (SJFS)
Basic Concept
� Process with the shortest expected processing time (CPU
burst) is selected next
� Its selection function is execution time and it uses non
preemptive scheduling/decision mode
Illustration
Consider the following processes arrive at time 0
Process P1 P2 P3
CPU Burst (in ms) 24 3 3

136
SHORTEST JOB FIRST SCHEDULING (SJFS)
Basic Concept
� Process with the shortest expected processing time (CPU
burst) is selected next
� Its selection function is execution time and it uses non
preemptive scheduling/decision mode
Illustration
Consider the following processes arrive at time 0
Process P1 P2 P3
CPU Burst (in ms) 24 3 3

137
Case i. FCFSS
Process P1 P2 P3
Turn around time 24 27 30
Response time 0 24 27
Average response time = (0+24+27)/3 = 17
Average turn around time = (24+27+30)/3=27
Throughput = 3/30
Case ii. SJFS
Process P3 P2 P1
Turn around time 3 6 30
Response time 0 3 6
Average response time = (0+3+6)/3 = 3
Average turn around time = (3+6+30)/3=13
Throughput = 3/30

138
 � Consider the following processes arrive at time 0, 2, 4, 6, 8
respectively
Process P1 P2 P3 P4 P5
Arrival Time (Ta) 0 2 4 6 8
Service Time (T-s) 3 6 4 5 2
Turn around time (T-r) 3 7 11 14 3
Response time 0 1 7 9 1
T-r/Ts 1 1.17 2.75 2.8 1.5
Average response time = (0+1+7+9+1)/5 = 3.6
Average turn around time = (3+7+11+14+3)/5=7.6
Throughput = 5/20

139
 Advantages
� It produces optimal average turn around time and average
response time
� There is a minimum overhead
 Drawbacks
� Starvation: some processes may not get the CPU at all as long
as there is a steady supply of shorter processes. It can be
modified by reducing the calculated average time of the process
by a constant for each allocation so that it will be eventually
move up to the next queue
� It is not desirable for a time-sharing or transaction processing
environment because of its lack of processing
� Variability of response time is increased, especially for longer
processes

140
 Difficulty with SJFS
� Figuring out the shortest process or the required processing
time of each process: one approach to is to
 Use aging: a technique of estimating the next value in a
series by taking the weighed average of the current
measured value and the previous estimate
 Estimate the next CPU burst based on the average of the
measured length of previous CPU burst
 Sn+1 = 1/n (T1 + T2 + T3 … Tn) where Ti is processor
execution time for the Ith instance and Si is predicted
value for the Ith instance
� Arrival of processes may not be simultaneous

141
SHORTEST REMAINING TIME SCHEDULING (SRTS)
 Basic Concept
� The process that has the shortest expected remaining process
time
� If a new process arrives with a shorter next CPU burst than
what is left of the currently executing process, the new process
gets the CPU
� Its selection function is remaining execution time and uses
preemptive decision mode

142
Illustration
Consider the following processes arrive at time 0, 2, 4, 6, 8
respectively
Process P1 P2 P3 P4 P5
Arrival Time (Ta) 0 2 4 6 8
Service Time (T-s) 3 6 4 5 2
Turn around time (T-r) 3 13 4 14 2
Response time 0 1 0 9 0
T-r/Ts 1 2.17 1 2.8 1
Average response time = (0+1+0+9+0)/5 = 2
Average turn around time = (3+13+4+14+2)/5=7.2
Throughput = 5/20

143
 Advantages
� It gives superior turnaround time performance to SJFS,
because a short job is given immediate preference to a running
longer process
 Drawbacks
� There is a risk of starvation of longer processes
� High overhead due to frequent process switch
 Difficulty with SRTN
� Figuring out required processing time of each process

144
ROUND ROBIN SCHEDULING (RRS)
 Basic Concept
� A small amount of time called a quantum or time slice is
defined. According to the quantum, a clock interrupt is
generated at periodic intervals. When the interrupt occurs, the
currently running process is placed in the ready queue, and
the next ready process is selected on a FCFS basis.
� The CPU is allocated to each process for a time interval of up
to one quantum. When a process finishes its quantum it is
added to the ready queue, when it is requesting I/O it is added
to the waiting queue
� The ready queue is treated as a circular queue
� Its selection function is based on quantum and it uses
preemptive decision mode

145
Illustration
Consider the following set of processes that arrive at time 0, with the
length of the CPU burst given in milliseconds:
Process Service Time (T-s)
P1 24
P2 3
P3 3
� If we use a time quantum of 4 milliseconds
� The Gantt chart would be

� The average waiting time is 17/3 = 5.66 milliseconds

146
 Features
� The oldest, simplest, fairest and most widely used preemptive
scheduling
� Reduces the penalty that short processes suffer with FCFS
 Drawbacks
� CPU-bound processes tend to receive unfair portion of CPU
time, which results in poor performance for I/O bound
processes
� It makes implicit assumption that all processes are equally
important. It does not take external factors into account
� Maximum overhead due to frequent process switch

147
Difficulty with RRS
� The length of the quantum should be decided carefully
 E.g.1 quantum =20ms, context switch =5ms, % of context
switch = 5/25 *100=20%
 Poor CPU utilization
 Good interactivity
 E.g.1 quantum =500ms, context switch =5ms, % of context
switch = 5/505 *100<1%
 Improved CPU utilization
 Poor interactivity
 Setting the quantum too short causes
 Poor CPU utilization
 Good interactivity
 Setting the quantum too long causes
 Improved CPU utilization
 Poor interactivity
 A quantum around 100ms is often reasonable compromise

148
PRIORITY SCHEDULING (PS)
 Basic Concept
� Each process is assigned a priority and the runnable process
with the highest priority is allowed to run i.e. a ready process
with highest priority is given the CPU.
� It is often convenient to group processes into priority classes
and use priority scheduling among the classes but round robin
scheduling within each class

149
Illustration
Consider the following processes arrive at time 0
Process P1 P2 P3 P4 P5
Priority 2 4 5 3 1
Service Time (T-s) 3 6 4 5 2
Turn around time (T-r) 18 10 4 15 20
Response time 15 4 0 10 18
T-r/Ts 6 1.67 1 3 10
Average response time = (0+15+4+10+18)/5 = 9.4
Average turn around time =(18+10+4+15+20)/5=13.4
Throughput = 5/20= 0.25

150
 � Consider the following priority classes
Processes type: Deans Heads Instructors Secretaries
Students
Priority: 5 4 3 2 1
 As long as there are runnable processes in priority level 5,
just run each one for one quantum, round robin fashion,
and never bother with lower priority classes
 If priorities are not adjusted occasionally, lower priority
classes may all starve to death

151
 Advantages
� It considers the fact that some processes are more important than others, i.e. it
takes external factors into account
 Drawbacks
� A high priority process may run indefinitely and it can prevent all other
processes from running. This creates starvation on other processes. There are
two possible solutions for this problem:
 Assigning a maximum quantum to each process
 Assigning priorities dynamically, i.e. avoid using static priorities
 Assigning a process a priority of 1/q where q is the fraction of the last quantum that is used

 A process that used only 2ms of its 100ms quantum would get a
priority of 50=1/2/100
 A process that used 50ms of its 100ms quantum would get a priority of
2=1/50/100
 Decreasing the priority of the currently running process at each clock tick

152
MULTILEVEL QUEUES SCHEDULING (MLQS)
• It is used for situations for which processes can be classified
into different groups
• System processes
• Interactive processes
• Batch processes
• The ready queue is partitioned into several separate queues
• Each processes is assigned to one queue permanently, based
on some property of the process such as memory size,
process priority, process type etc
• Each queue has its own scheduling algorithm: RRS, FCFSS,
SJFS, PS etc
• System processes…………. PS
• Interactive processes……… RRS
• Batch processes…………… FCFSS

153
� There must be some kind of scheduling between the queues
 Commonly implemented as fixed-priority preemptive scheduling,
i.e. system processes have absolute priority over the interactive
processes and interactive processes have absolute priority over the
batch processes. Lowest priority processes may be starved.

 Could also use a time slice algorithm where each queue gets a certain
amount of CPU time, which it can schedule among its processes.

154
MULTILEVEL FEED BACK QUEUES SCHEDULING
(MLFBQS)
� It allows processes to move between queues
� Multilevel-feedback-queue scheduler is 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

155
� There
are a number variations for this
scheduling scheme
 One of them is to perform scheduling based on
preemptive time quantum basis and a dynamic
priority mechanism:
 When a process first enters the system, it is placed in
RQ0. After its first execution, it is placed in RQ1. Each
subsequent time that it is preempted, it is demoted to the
next lower priority queue.
 It can be constant (q) or variable quantum preemption (q i
=2i).
 There is possibility of starvation of long processes

156
 To avoid starvation, processes may be separated with different CPU-
burst characteristics.
 If a process uses too much CPU time, it will be moved to lower priority
queue. This leaves I/O bound and interactive processes in the high
priority queue
 A process waiting too long in a lower priority queue may be moved to
a higher queue and this prevents starvation

157
DEADLOCKS
• Deadlock can occur when resources temporarily
granted exclusive access to resources.
• Resources could be of two types
• Preemptable- is the one that can be taken away
from the process without causing an ill effect. E.g.
memory
• Non-preemptable- is the one that cannot be taken
away from its current owner without causing the
computation to fail.
158 • Deadlocks involve in non-preemptable resources.
Defn :
 A set of processes is deadlocked if each process in the
set is waiting for an event that only another process in
the set can cause. But none of the processes can run,
release resources or be awakened.
� Usually the event is the release of the resource
� E.g., the system has two tape derives p1 and p2 each hold
one tape derive and each one needs another one to proceed.
 Sequence of events required to use a resource:
1. Request the resource.
2. Use the resource.
3. Release the resource.

159
CONDITIONS FOR DEADLOCK
The following four conditions must hold for there to be a
deadlock
1. Mutual exclusion condition-each resource is assigned to
exactly one process.
2. Hold and wait condition-process holding resources can
request additional resources.
3. No preemption condition-previously granted resources can't
be forcibly taken away; only the process can voluntarily
release resource.
4. Circular wait condition-there must be a circular chain of two
or more processes. Each of which is waiting for a resource
held by the next member of the chain.
� One mechanism of attacking deadlock is by trying to negate some
of the conditions-deadlock avoidance.

160
e.g. traffic deadlock

161
DEADLOCK MODELING (RESOURCE
ALLOCATION )
� The four conditions can be modeling using direct graph with
two kinds of nodes; process (circles) and resources (squares)

162
a) R is assigned to and currently held by A
b) B is requesting/waiting for S (B is blocked)
c) C and D are in deadlock over T and U (both are
blocked)
 If the graph contains no cycle=>no deadlock
 If the graph contains a cycle=>
� If one instance per resource type- deadlock
� If several instances per resource type-possibility of deadlock

163
DEALING WITH DEADLOCK PROBLEM
 In general there are four strategies of dealing with
deadlock problem
1. The Ostrich Approach Just ignore the deadlock
problem altogether.
� It is reasonable if
 Deadlock occur very rarely and the effects are not catastrophic.
 Cost of prevention is high.
� Unix and windows use this approach.
2. Deadlock Detection and Recovery
� Let them occur, detect them and take an action.
� The simplest case is when there is one instance of each
resource

164
� Example :assume a system with 7 processes (A-
G)and 6 resources (R-W)

� (a) A resource graph. (b) A cycle extracted from (a)

� There are many algorithms to detect deadlock

165
RECOVERY FROM DEADLOCK
� Once the deadlock is detected, what to do to recover
 Recovery through preemption
� Take away a resource from its current owner and give it to
another process
� But depends on the nature of resources
 Recovery through rollback
� If the processes are arranged to checkpoint periodically
� Checkpoint means writing the state (memory, resources
assigned, etc.) of a process into a file so that it can be
restarted later.
� Then rollback a process to a point in time before it acquire a
resource that is taken away.

166
 Recovery through killing processes
� Crudest but simplest way to break a deadlock
� Kill one of the processes in the deadlock: if not yet solved ,
continue killing a process until the deadlocked is broken.
� The process to be killed has to be selected carefully: it has to
be one that can be started safely from the beginning

167
DEADLOCK AVOIDANCE
 Avoid deadlock by careful resource scheduling.
 Requires that the system has some additional prior
information available.
 Simplest and most useful model requires that each
process declare the maximum number of resources of
each type that it may need.
 The deadlock avoidance algorithm dynamically examines
the resource allocation state to ensure that there can
never be a circular wait.
 Resource allocation state is defined by the number of
available and allocated resources, and the maximum
demands of the process.

168
DEADLOCK PREVENTION
 Prevent deadlock by resource scheduling so as to
negate at least one of the four conditions
 Attacking the mutual exclusion condition
 Attacking the hold and wait condition
 Attacking the no preemption condition
 Attacking the circular wait condition

169
REFERENCES
 Andrew Tanenbaum, Modern Operating Systems
,2nd Edition,
 William Stallings, operating Systems: Internals and
Design Principles,5th Edition,
 Abraham Silberschatz, P.B. Galvin and G. Gagne,
Operating Systems Concepts, 6th Edition

170
 QUESTIONS

?
171
1. Consider a set of three processes P1, P2 and P3 arriving in the order P1,
P2, P3 at
time instant 0 and having CPU burst times as shown below. Draw the Gantt
Chart
and calculate the average waiting time, average turnaround time and
average
response time using FCFS algorithm.

2. Given below are the arrival and burst times of four processes P1, P2, P3
and P4.
Draw the Gantt Chart using SJF preemptive and non-preemptive
scheduling and
calculate the average waiting time

3. Given below are the burst times of three processes P1, P2 and P3. Draw
the Gantt
Chart using RR scheduling and calculate the average waiting time,
average
turnaround time and average response time. Quantum = 5 ms.
4. Given below are the burst times of four processes P1, P2, P3 and P4.
Draw the
Gantt Chart using RR scheduling and calculate the average waiting time.
Quantum
= 20 ms.

5. Given below are the burst times and priorities of five processes P1, P2, P3,
P4 and
[Link] the Gantt Chart using priority scheduling and calculate the
average
waiting time, turnaround time and response time. (a smaller priority
number
implies a higher priority)

6. Consider the following set of processes P1, P2, P3, P4 (arriving in the
order P1,
P2,P3, P4) and their CPU burst times. Use FCFS and SJF algorithm to
draw the
Gantt Chart and to calculate the average waiting time, average turnaround
time
and average response time. Analyze the results.

7. Given below are the arrival and burst times of four processes P1, P2, P3
and P4.
Draw the Gantt Chart using FCFS, SJF preemptive, SJF non-preemptive
and RR
scheduling (Quantum = 4ms, no priority based pre-emption). Calculate
the
average waiting time, average turnaround time and average response time.
8. Given below are the burst times ad priorities of four five processes P1, P2,
P3, P4
andP5. The processes are assumed to have arrived in the order P1, P2, P3,
P4, P5,
all at time 0.

A. Draw four Gantt charts illustrating the execution of these processes using
FCFS,SJF, non preemptive priority (a smaller priority number implies a
higher
priority), and RR (quantum = 1) scheduling.
B. What is the turnaround time of each process for each of the scheduling
C. algorithms?
What is the waiting time of each process for each of the scheduling
algorithms?
D. Which of the schedules in part results in the minimal average waiting
time?
algorithms.
9. Find the mean turnaround time for the following data for each of the
A. Round Robin (Quantum = 2 minutes)
following
B. Priority Scheduling
C. First Come First Serve (In the order 10, 6, 2, 4
and 8)
D. [Link]
Estimated Jobfor
run times First
five batch jobs A through E: 10, 6, 2, 4 and 8 minutes.
Assume that they all have arrival time as 0. Their determined priorities are 3, 5,
2,1
and 4respectively with 5 being the highest priority.
10. burst
All 5 processes
time givenarrive at time 0, in the
in milliseconds. order given,
Consider FCFS,with
SJFtheand
length
RR of the
CPU-scheduling
(quantum = 10 ms) scheduling algorithms for this set of processes.
Calculate the
waiting time and find out which algorithm would give the minimum
average
waiting time.
11. Consider the following processes. Draw Gantt chart illustrating the
execution of
the given processes using Shortest Remaining Time Next scheduling
algorithm.
Calculate the Average waiting Time and Average Turnaround Time.

12. Consider the following set of processes P1, P2, P3, P4 and their CPU burst
times.
Using SJF algorithm, calculate average waiting time and average turnaround
time.
Process Burst Time(msecs)
P1 6
P2 8
P3 7
P4 3

13. Calculate the average waiting time with respective to preemptive

Shortest Job
First (SRT) Scheduling algorithm.