CS1253 – OPERATING SYSTEMS

UNIT I – PROCESSES AND THREADS

Introduction To Operating Systems- Review Of Computer
Organization- Operating System Structures- System Calls- System Programs- System Structure -
Virtual Machines- Processes- Process Concept- Process Scheduling- Operations On Processes–
Cooperating Processes- Interprocess Communication- Communication In Client Server Systems-
Case Study- IPC In Linux –Threads -Multithreading Models -Threading Issues -Case Study-
Pthreads Library.

1.1 INTRODUCTION TO OPERATING SYSTEMS

OPERATING SYSTEM
An Operating System is a program that manages the computer hardware and
act as an intermediary between a computer user and the computer hardware. An Operating
System must be efficient and convenient to use. Eg: MS-DOS, MS-WINDOWS, UNIX, LINUX.

COMPONENTS OF COMPUTER SYSTEM

A Computer System can be divided into four components
1) Hardware
2) Application Programs
3) Operating System
4) Users
1) Hardware
It is the physical parts of a computer like CPU, Memory, I/O devices etc
2) Application Programs
It is a collection of programs that define the ways in which these resources are used
to solve the computing problems of the user..
Eg: Word Processors, Spreadsheets, Compilers and Web Browsers.

Fig: Abstract view of a computer system

3) Operating System
It is a program that controls and co-ordinates the use of hardware among the various
application programs for the various users.
An OS provides an environment to execute other programs. OS alone is of no use.
An OS is also called as resource allocator, control program and kernel. The OS manages
and allocates resources like CPU time, memory space, file storage space, I/O devices.
A control program controls the execution of user programs and operations of I/O
devices to prevent errors and improper use of the computer.
An OS usually called the kernel is the one program running at all times on the computer.
4) Users
Users are the people who use computer systems for their applications.

EVOLUTION (OR) TYPES OF OPERATING SYSTEM

1) Mainframe System
Batch System
Multiprogrammed (or) Multiuser System
Time Sharing System
2) Desktop System
3) Multiprocessor System
4) Distributed System
5) Clustered System
6) Real Time System
7) Handheld System
1) MAINFRAME SYSTEM
First computer used to tackle many commercial and scientific applications.
Eg: Batch System, Multiprogrammed System and Time Sharing System.
a) Batch System
Used in early computers.
Little (or) no interaction between user and computer.
Input devices- card readers and tape drives. Output devices- line printers, punched
cards and tape drives.
The user prepared a job which consists of program, data and control information
and submitted it to computer operator. After sometime the output is obtained.
The job was usually in the form of punched cards.
To speed up processing, operators grouped together jobs with similar needs called
batch and the computer would run each batch. The output from each job would
be sent back to the programmer. Fig: Memory Layout for a Simple Batch System

Operating
System

User Program
Area
 The major task of Batch System was to transfer control automatically from one
job to the next. The Operating System was always resident in memory.
In Batch System, the CPU is often idle because the speed of I/O devices are slower
Disk technology allowed OS to keep all jobs on a disk,rather than in a card reader.
The OS perform job scheduling(FIFO) to use resources and perform tasks efficiently

b) Multiprogrammed (or) Multiuser System

In a multiprogrammed OS, two or more programs are in memory at the
same time, sharing the same processor.
Multiprogramming increases CPU utilization by organizing jobs, so that the
CPU always has one job to execute ie) it is always busy.
In a non multiprogrammed system, the CPU is often idle.
In a multiprogrammed system, the OS picks up and executes one of the jobs in
main memory. When that job needs to wait, the CPU is switched to another job.
The first job finishes waiting and gets the CPU back. As long as atleast one job
needs to wait, the CPU is never idle.

Operating
System
Job 1
Job 2
Job 3
Job 4
Fig: Memory Layout for a Multiprogramming System

All the jobs that enter the system are kept in the job pool. From the job pool, the
OS brought some jobs into main memory.
Number of jobs kept in main memory is usually smaller than in job pool.
If several jobs are ready to be brought into memory, and if there is not enough room for
all of them, then the system must choose among them. It is known as JOB scheduling.
If several jobs in main memory are ready to run at the same time, the system must choose
among them. It is known as CPU scheduling.

c) Time Sharing (or) Multitasking System

In Time Sharing system, the CPU executes multiple jobs by switching among
them, but the switches occur so frequently that the users can interact with each
program while it is running.
Multiprogrammed and Batch system did not provide user interaction. But time
sharing system provides user interaction with the computer.
 An interactive (or) hands- on computer system provides direct communication
between the user and the system.
A time shared OS uses CPU scheduling and multiprogramming.
As the system switches rapidly from one user to the next, each user is given the
impression that the entire system is dedicated to her use, eventhough it is being
shared among many users.
A time shared OS allows many users to share the computer simultaneously
and also only a little CPU time is needed for each user. The response time may be
within 1 second.
To obtain a reasonable response time, jobs may have to be swapped in and out
of main memory to the disk. For this, Virtual Memory method is used.
Virtual Memory is a technique that allows the execution of a job that may not
be completely in memory.ie) the programs can be larger than physical memory.

2) DESKTOP (OR) PC SYSTEM

Personal Computers used in 1970’s failed to protect an operating system from user programs.
Personal Computer System were neither multiuser nor multitasking. PC is also
called microcomputer.
Desktop system is suitable for maximizing user convenience and responsiveness.
Eg: MS-DOS, MS WINDOWS, UNIX, LINUX, APPLE MACINTOSH.
Desktop system provides a graphical user interface by means of icons to open a
window that contains information for the respective icon. Eg: Windows 95,98,NT.
Apple Macintosh OS includes virtual memory, multitasking and advanced features.
LINUX and UNIX OS has become popular recently.
File protection is not necessary for a PC. But when a PC is connected over the
network, the file protection is necessary.
Due to the lack of file protection, the malicious programs(worm or virus) can destroy
data on systems like MS- DOS and Macintosh OS.

3) MULTIPROCESSOR (OR) PARALLEL (OR)TIGHTLY COUPLED SYSTEM

Multiprocessing means multiple CPU’s can be used to perform more than one job at
the same time.
Multiprocessor system (parallel or tightly coupled system) have more than one
processor sharing the common bus, clock, memory and peripheral devices.
ADVANTAGE
Increased Throughput
More work can be done in less time by using many CPU’s.
Economy of scale
By sharing peripherals, storage and power supplies, multiprocessor system
can save more money than many single processor systems.
 Increased Reliability
Since the work is shared by many processor, the failure of one processor
may not halt the system but slow it down ie) the remaining processors share the
work of the failed processor.
The ability of a computer system to continue functioning even after the failure of a
hardware component is called graceful degradation. Systems designed for graceful
degradation are also called fault tolerant.
TYPES OF MULTIPROCESSOR SYSTEM
a) Symmetric Multiprocessing(SMP)
 In SMP, each processor runs an identical copy of the operating system and
they communicate with one another as needed.
 All processors are peers ie) no master – slave relationship exists between
processors. Eg: Windows NT, LINUX, Digital UNIX.

Fig: Symmetric Multiprocessing Architecture

 ADVANTAGE
Many processes can run simultaneously without affecting the performance.
 DISADVANTAGE
 Though it improves performance, I/O must be controlled to ensure
that the data reach the appropriate processor.
 Since the CPU’s are separate, one CPU is sitting idle while another is
overloaded.
b) Asymmetric Multiprocessing
 In ASMP, each processor is assigned a specific task. There exists a master –
slave relationship between processors.
 A master processor controls the system. Other processors either look to the
master for instruction or have predefined tasks.
Eg: SUNOS Version4.
4) DISTRIBUTED SYSTEM
Distributed System is a collection of physically separate computer system that are
networked together to provide users with access to various resources.
Distributed System depends on networking for their functionality. Network is the
communication path between two or more systems.
Networks are classified based on the distance between nodes, protocols used and the
transport media.
Local Area Network(LAN) exists within a room, a floor or a building.
Wide Area Network(WAN) exists between buildings, cities or countries.
Metropolitan Area Network(MAN) link buildings within a city.
Small Area Network(SAN) exists over a short distance of several feet.Eg: Bluetooth.
TCP/IP, ATM and other protocols are used. The transmission media such as copper
wires, fiber cables, wireless(satellite), microwave dishes and radios are used.
Distributed file system provide access control and locking to files to ensure no
conflicting operations occur. This type of service is known as Distributed Lock Manager.
Reasons for distributed system are resource sharing, computation speedup, reliability
and communication.
TYPES OF DISTRIBUTED SYSTEM
1) Client Server System
It is a centralized system, that acts as a server system to satisfy requests
generated by client system.

Fig: General Structure of a Client Server System

a) Compute Server System
Clients can send requests to server, to perform an action. The server
executes the action and sends back results to the client.
b) File Server System
Client can create, update, read and delete files.
2) Peer to Peer System
It consists of a collection of processors that do not share memory or a
clock. Instead each processor has its own local memory.
The processors communicate with one another through high speed buses
or telephone lines. These systems are usually referred to as loosely
coupled or distributed system.
Network operating system is an OS that provides file sharing across the
network and e-mail.
5) CLUSTERED SYSTEM
Clustered system gathered multiple CPU’s to perform a specific task.
It provides high availability ie) fault tolerance property.
Each node can monitor one or more nodes. If any of the machines/ nodes fails, the
monitoring node take care of it.
TYPES OF CLUSTERED SYSTEM
1) Symmetric Clustering
Two (or) more hosts are running and monitoring each other. Since it
makes use of all the available hardware, it is efficient.
2) Asymmetric Clustering
One machine is in hot standby mode, while the other is running the applications.
The hot standby machine does nothing but monitor the active server. If
that machine fails, the hot standby host becomes the active server.
3) Parallel Cluster
It allow multiple hosts to access same data on shared storage.
Eg: Oracle Parallel Server.

6) REAL TIME SYSTEM

It is a special purpose operating system that is often used as a control device in a
dedicated application.
It is used in real time applications. Eg: Systems that control scientific
experiments, medical imaging system, industrial control and flight control etc.
A real time system has well defined and fixed time constraints. Processing must
be done within the defined constraints or the system will fail.
It functions correctly only if it returns the correct result within its time constraints.
TYPES OF REAL TIME SYSTEM
1) Hard Real Time System
2) Soft Real Time System

Hard Real Time System Soft Real Time System

It guarantees that critical tasks be completed A critical real time task gets priority over
on time. ie) All delays in the system must be other tasks, and retains that priority until it
bounded(predictable) completes. Delays need to be bounded
It is used for the applications whose It is used for the applications whose
requirements must be met at all times. ie) It requirements may be met and need not be
is dedicated to real time applications. met. ie) It is not a dedicated system.
It conflicts with the operation of Time Sharing It can be mixed with other types of system.
System and the two cannot be mixed.
It is used in industrial control, flight control It is used in multimedia and advanced
and robotics. scientific projects (undersea exploration)
Read Only Memory(ROM), a non volatile Secondary Storage and virtual storage is
storage is used . used here.
7) HANDHELD SYSTEM
It includes Personal Digital Assistant(PDA) such as Palm Pilots (or) Cellular
telephones with connectivity to a network such as the internet.
Developers of Handheld System and applications face many problems
1) Since it is small in size, it has small amount of memory, small display
screen and slow processor.
2) Since memory size is very small, memory has to be managed effectively.
ie) once the memory is not in use, it has to be returned to the memory manager.
3) Faster processors require more power. It requires larger battery that has to
be replaced more frequently.
4) Since the display screen is very small, e-mail/ web pages must be condensed
onto smaller displays. So that web clipping is displayed on the handheld device.
5) Some cellphones use wireless technology such as Bluetooth. To download
data to these devices, one first download the data to a PC and then to PDA.
However the limitations in the functionality of PDA’s are balanced by their
convenience and portability.

1.3 OPERATING SYSTEM STRUCTURES

1.3.1 SYSTEM CALLS
System Calls provide the interface between a Process and the Operating System.
A System Call is generally considered as a software interrupt Eg:UNIX System Calls
System Calls are generally available as assembly language instructions.
Languages like C, C++, Perl have been defined to replace assembly language.
A program to read data from one file and copy to another file is considered as an
example for the usage of System Calls.
System Calls Parameter Passing
Three methods are used to pass parameters to the Operating System.
1) Pass the parameters in registers.
2) Parameters are stored in a block or table in memory and the address of
the block is passed as a parameter in a register.
 3) Parameters can be placed/ pushed onto the stack by the program and
popped from the stack by the OS.
TYPES OF SYSTEM CALLS
System Calls can be classified into five types
1) Process control
2) File Management
3) Device Management
4) Information Maintenance
5) Communication
1) Process Control
System Calls needed are
1) end, abort : Terminates a running process either normally(end) or
abnormally(abort).
2) load, execute: Load the new process into memory and execute the
loaded process.
3) create process: Create a new process or job.
4) terminate process: Terminate the created process.
5) get process attributes: Used to get process attributes such as process
id, process state, program counter, registers and memory limits.
6) set process attributes: Used to set the attributes of a process.
7) wait time: Process may need to wait for a certain amount of time for
another process to finish their execution.
8) wait event: Process may need to wait for a specific event to occur.
9) signal event: Used to signal the process when that event has occurred.
Debugging a program is also provided by system calls.
Single Tasking System: MS-DOS. In this system, terminate and
stay resident system call is used.
Multitasking System: Free BSD. In this system, fork, exec and exit
system calls are used.
2) File Management
System Calls needed are
1) create file, delete file: Create a new file. Delete a file.
2) open, close: Open a file to read or write. Close a file.
3) read, write, reposition: Read data from an opened file. Write data to
an opened file. Rewind or skip data in a file.
4) get file attributes: Used to get file attributes such as file name, file
type, protection codes and accounting information.
5) set file attributes: Used to set the attributes of a file.
3) Device Management
System Calls needed are
1) request device : If there are multiple users, the user must request the
device and make use of it.
2) release device: After finishing, the user must release the device.
3) read, write and reposition: Once the device has been allocated, the
user can read, write and reposition the device.
4) get device attributes, set device attributes
5) logically attach or detach devices
4) Information Maintenance
System calls needed are
1) get time or date, set time or date
2) get system data, set system data
3) get process, file or device attributes
4) set process, file or device attributes
The operating system keeps information about all its processes.
System calls are used for transferring information between the
user program and the OS.
5) Communication
System calls needed are
1) create, delete connection
2) open, close connection
3) send, receive messages
4) read, write messages
5) get host id, get process id
6) attach or detach devices
7) transfer status information
There are two methods of communication
1) Message passing model
2) Shared memory model
1) Message Passing Model
Information is exchanged through interprocess communication facility.
Before communication can take place, a connection must be opened.
Name of the other communicator must be known.
Each computer in a network has a host name. Similarly each process
has a process name which is translated into an identifier. This
translation is done by get hostid and get processid system calls.
Advantage:
It is useful when smaller numbers of data need to be exchanged.
It is easier to implement than shared memory.
 a) Message Passing b) Shared memory
2) Shared Memory Model
The processes use map memory system calls to access memory
owned by other processes.
Normally, operating system tries to prevent one process from
accessing another process memory.
In this model, the processes may exchange information by reading
and writing data in these shared areas.
The processes are responsible for ensuring that they are not writing to
same location simultaneously.
Advantage
It allows maximum speed and convenience of communication.
Disadvantage
It creates problem in the area of protection and synchronization
1.3.2 SYSTEM PROGRAMS
 System Programs provide a convenient environment for program development and execution.
 System programs can be divided into
1) File management
2) Status information
3) File modification
4) Programming language support
5) Program loading and execution
6) Communication
Some system programs are simply user interfaces to system calls.
1) File management:
These programs create, delete, copy, rename, print, dump, list and generally manipulate
files and directories.
2) Status information:
Status information includes date, time, amount of available memory or disk space,
number of users etc.
That information is then formatted and is printed to the terminal or output device or file.
3) File modification :
Text Editors are used to create and modify the content of files stored on disk or tape.
 4) Programming language support:
Compilers, Assemblers, Interpreters and Debuggers for programming languages(such
as C, C++, Java, Visual Basic) must be provided to the user.
5) Program loading and execution:
Once a program is assembled or compiled, it must be loaded into memory to be executed.
The system must provide absolute loaders, relocatable loaders, linkage editors, overlay
loaders and debugging system for either high level or machine level language.
6) Communication:
This program provide the mechanism for creating virtual connections among
processes, users and computer systems.
It allows users to send messages to one another’s screen, browse web pages, send
e-mail messages, log in remotely, transfer files etc.
Application Programs:
Programs that solve common problems or perform common operations are known
as System Utilities (or) Application Programs.
Eg: Web browser, Word processor, Spreadsheet, Database system, Compilers, Games

1.3.3 SYSTEM STRUCTURE

A common approach to design an operating system is to partition the task into small components.
Operating System consists of different components. These components are interconnected
and melded into a kernel.
For designing the system different types of structures are used.
1) Simple Structure
2) Layered Approach.
1) Simple Structure
Small, simple and limited systems that do not have a well defined structure.
Eg: MS- DOS
It provides the most functionality in least space because of the limited hardware.
UNIX is another system that provides limited hardware functionality. It consists
of two parts: the kernel and the system programs.
The kernel is further separated into a series of interfaces and device drivers. The
kernel provides file system, CPU scheduling, memory management through system calls.
System calls define the API to UNIX. The set of system programs commonly available
defines the user interface.
a) MS- DOS LAYER STRUCTURE b) UNIX SYSTEM STRUCTURE

2) Layered Approach
The operating system is divided into a number of layers (levels), each built on top of lower
layers. The bottom layer (layer 0), is the hardware; the highest (layer N) is the user
interface.
An OS layer M is the encapsulation of data and the operations. ie) abstract object.
It is better than MS-DOS structure since direct user access to lower level functions
are not allowed.
Advantage
1) With modularity, each higher level layer uses functions (operations) and services
of only lower-level layers.
2) It simplifies debugging and system verification.
Disadvantage
1) It involves the careful definition of the layers, because a layer can use only those
layers below it.
2) It is less efficient than other types.

Fig: An operating System layer

3) Microkernels
As the UNIX operating system expanded, the kernel become large and difficult to manage.
The microkernel approach structures the operating system by removing all nonessentials
components from the kernel and implementing them as system and user level programs.
Microkernel provides minimal process and memory management and communication
facility.
The main function of the microkernel is to provide a communication facility
Communication is provided by message passing.
The benefits of the microkernel approach include the ease of extending the operating
system ie) All new services are added to user space.
The microkernel provides more security and reliability.
Tru64 UNIX (DIGITAL UNIX), QNX OS based upon the microkernel approach.
Windows NT uses a hybrid structure. Windows NT is designed to run WIN32, OS/2 and
POSIX applications. It consists of a server and client program that runs in user space for
each application type. The Kernel coordinates the message passing between client and
server applications.

Fig: Windows NT client server architecture

1.3.4 VIRTUAL MACHINES

A Computer System is made up of layers. The hardware is the lowest layer. The kernel is at
the next level uses the hardware instructions to create system calls. The system programs
above the kernel use either system calls or hardware instructions.
The application programs view everything under them in the hierarchy. This layered approach
is used in virtual machine.
CPU scheduling and virtual memory techniques can create the appearance that a program has
its own processor with its own(virtual) memory. Spooling and file system can provide
virtual card readers and virtual line printers.
Each process is provided with a (virtual) copy of the underlying computer.
A major difficulty with the virtual machine involves disk systems.
Suppose that the physical machine has three disk drives but wants to support seven virtual
machines. It cannot allocate a disk drive to each virtual machine.
The solution is to provide virtual disks named minidisks which are identical in all respects
except size.
IMPLEMENTATION
The Physical machine consists of two modes: User mode and monitor mode. The virtual
machine software can run in monitor mode and virtual machine can run in user mode.
Similarly the virtual machine has two modes: virtual user mode and virtual monitor mode.
Both run in a physical user mode.
 A transfer from user mode to monitor mode on a real machine must also cause a transfer
from virtual user mode to a virtual monitor mode on a virtual machine.

a) Non virtual machine b) Virtual machine

When a system call is made by a program running on a virtual machine, in virtual user mode, it
will cause a transfer to the virtual monitor in the real machine.
When the virtual machine monitor gains control, it can change the register contents and
program counter for the virtual machine and then restart the virtual machine.
BENEFITS
Virtual machine provides security by completely protecting system resources.
It allows system development to be done without disrupting normal system operation.
Virtual machine supports research and development of operating system.
The operating system runs on and controls the entire machine. Therefore, the control system
must be stopped and taken out of use while changes are made and tested. This period is
commonly called system development time.
Virtual machine solves the problem of system development time.
Java
Java is a popular object oriented language introduced by Sun Microsystems
A Java program consists of one or more classes. For each Java class, the Java compiler
produces a bytecode output file (.class)
The Java virtual machine consists of a class loader, class verifier and Java interpreter.
The class loader loads .class files from both the Java program and the Java API. The class
verifier checks that the class file is valid Java bytecode. The Java interpreter is a software or
just- in-time compiler that converts bytecodes into machine language.
The JVM also manages memory by performing garbage collection ie) reclaiming memory
from objects no longer in use and returning it to the system.

Fig: Java Virtual Machine

1.4 PROCESSES
1.4.1 Process Concept
A Process is a program in execution. A process is an active entity.
A Process contains program code, which is sometimes known as text section. It also includes
program counter, contents of the processor’s registers, process stack which contains
temporary data and a data section which contains global variables.
A program by itself is not a process. A program is a passive entity such as the contents
of a file stored on disk. A process is an active entity with a program counter specifying
the next instruction to execute and a set of resources.
1.4.2 Process State
As a process executes, it changes state. The state of a process is defined by the current
activity of that process.

Fig: Diagram of Process State

New: The process is being created.
Running: Instructions are being executed.
Waiting: The process is waiting for some event to occur (such as an I/O operation or
reception of a signal)
Ready: The process is waiting to be assigned to a processor.
Terminated: The process has finished execution.
Only one process can be running on any processor at any time, although many
processes may be ready and waiting.
1.4.3 Process Control Block
All information about a process is maintained in Process Table or Process Control Block(PCB)
Each process is represented in the operating System by a Process Control Block(PCB).

Fig: Process Control Block

 Process State:
The state may be new, ready, running, waiting, halted etc.
Program Counter:
The counter indicates the address of the next instruction to be executed.
CPU Registers:
It includes accumulators, index registers, stack pointers, general purpose registers and
condition code information.
CPU Scheduling Information:
It includes a process priority, pointers to scheduling queues and other scheduling parameters.
Memory Management Information:
It includes the value of the base and limit registers, the page tables or segment tables.

Fig: CPU switch from process to process

Accounting Information:
This includes the amount of CPU and time limits, account numbers, job or process numbers
I/O Status information:
This includes the list of I/O devices allocated, a list of open files etc.
1.4.4 Threads
Thread is a flow of control within a process.
A process is considered as a single thread of a execution.
Single thread of control allows the process to perform only one task at a time. Eg: While
typing characters in the MS WORD, it is not possible to check the spelling simultaneously.
If a process has multiple threads allows to perform more than one task at a time, it is
called multithreading.
1.4.5 Process Scheduling
The objective of multiprogramming is to have some process running at all times, so as
to maximize CPU utilization.
A uniprocessor system can have only one running process. If more processes exist, the
rest must wait until the CPU is free and can be rescheduled.
1) Scheduling Queues
As processes enter the system, they are put into a job queue.
The processes that are residing in main memory and are ready and waiting to execute
are kept on a ready queue.
A Ready Queue header contains a pointer to the first and final PCBs in the list.
Each PCB contains a pointer field that points to the next PCB in the ready queue.
The list of processes waiting for the particular I/O device is called a device queue.
Each device has its own device queue.

Fig: Ready Queue and I/O Device Queues

A common representation of process scheduling is a queueing diagram. Each

rectangular box represents a queue. Two types of queues are present: the Ready queue
and I/O device queue.
The circles represent the resources and the arrows indicate the flow of processes in the system.

Fig: Queueing diagram representation of process scheduling

 A new process is initially put in the ready queue. It waits in the ready queue until it is
selected for execution (or dispatched).
Once the process is assigned to CPU and is executing, one of several events could occur
1) The process could issue an I/O request and then placed in an I/O queue.
2) The process could create a new subprocess and wait for its termination.
3) The process could be removed from the CPU, as a result of an interrupt and be put
back in the ready queue
2) Schedulers
The operating system must select processes from various scheduling queues. The
selection process is carried out by the scheduler.
Schedulers are of three types
a) Long term scheduler
b) Short term scheduler
c) Medium term scheduler
a) Long term scheduler
It is also called job scheduler.
Long term scheduler selects processes from job pool and loads them into memory for
execution.
The long term scheduler executes much less frequently, since there may be time
between the creation of new processes.
The long term scheduler also controls the degree of multiprogramming, the number of
processes in memory.
The long term scheduler should select a good process mix of I/O bound and CPU
bound process. An I/O bound process spends more of its time doing I/O than it spends
doing computation. A CPU bound process using more of its time doing computation
than an I/O bound process.
b) Short term scheduler
It is also called CPU scheduler.
The short term scheduler selects processes from main memory that are ready to execte
and allocates the CPU to one of them.
The short term scheduler must select a new process fot the CPU frequently ie) it must
be fast, because the process may execute for only a few milliseconds before waiting for
an I/O request.
c) Medium term scheduler
Medium term scheduler performs swapping process.
The medium term scheduler, removes processes from memory thus reduces the
degree of multiprogramming. At some later time, the process can be reintroduced
into memory and its execution can be continued where it left off. This scheme is
called swapping. Fig: Medium Term Scheduler
3) Context switch
Switching the CPU to another process requires saving the state of the old process and
loading the saved state for the new process. This task is known as a context switch.
The context of a process is represented in the PCB of a process. It includes the value of
the CPU registers, the process state and memory management information.
Context switch time is pure overhead because the system does no useful work while switching.
A Context Switch simply requires changing the pointer to the current register set.

1.4.6 Operations On Processes

The processes in the system can execute concurrently, and they must be created and
deleted dynamically.
1) Process Creation
A process may create several new processes using create process system call during
execution.
The creating process is called a parent process whereas the new processes are called
the children of that process.
Each of these new processes may in turn create other processes, forming a tree of
processes.

Fig: A tree of processes in a UNIX system.

A process will need certain resources to accomplish its task.
When a process creates a subprocess, that subprocess obtain its resources directly from
the operating system or it use the parent resources.
When a process is created, it obtains initialization data(or input) from the parent process.
When a process creates a new process, two possibilities exist in its execution.
1) The process continues to execute concurrently with its children.
2) The process waits until some or all of its children have terminated.
Two possibilities in terms of the address space of new process
1) The child process is a duplicate of the parent process.
2) The child process has a program loaded into it.
In UNIX, each process is identified by its process identifier (pid) which is a unique integer.
A new process is created by the fork system call ie) The parent creates a child process
using this call.
 The child process (new process) consists of a copy of address space of the parent
process.
The fork system call returns zero (value of pid) for the child (new) process and process
id of the child (non zero) for the parent process.
The execlp system call is used by the child process to replace its address space with
the UNIX command /bin/ls.
The parent waits for the child process to complete with the wait system call.
When the child process completes, the parent process terminates using the exit system call.

#include<stdio.h>
#include<stdlib.h>
#include<sys/types.h>
void main(int argc,char *argv[])
{
int pid;
pid=fork();
if(pid<0)
{
fprintf(stderr,”Fork failed”);
exit(-1);
}
else if(pid==0)
{
execlp(“/bin/ls”,”ls”,NULL);
}
else
{
wait(NULL);
printf(“Child Completed”);
exit(0);
}
}
Fig: C Program forking a separate process
2) Process Termination
A process terminates when it finishes executing using the exit system call.
The process may return data (output) to its parent process through wait system call.
All the process resources including physical and virtual memory, open files, I/O buffers
are deallocated by the OS.
The parent process that is to be terminated can terminate another process using abort
system call. So the parent must know the identities of its children for termination.
A parent may terminate the execution of its children for various reasons
1) The child has exceeded its usage of some of the resources that has been allocated.
2) The task assigned to the child is no longer required.
3) If a parent terminates, then all of its children must also be terminated. This
phenomenon is referred to as cascading termination.
1.4.7 Cooperating Processes
The concurrent processes may be either independent or cooperating processes.
A process is independent if it cannot affect or be affected by the other processes
executing in the system. Eg: Process that does not share data.
A process is cooperating if it can affect or be affected by the other processes executing
in the system. Eg: Process that shares data.
Process cooperation is needed for various reasons
1) Information Sharing
Concurrent access is allowed for accessing same types of resources.
2) Computation Speedup
If we want a particular task to run faster, we must break it into subtasks, each will
be executing in parallel.
3) Modularity
Process cooperation is needed for dividing the system functions into separate
processes or threads.
4) Convenience
An individual user may have many tasks to done at one time. Eg: Editing, compiling
Producer Consumer problem
It is the best example for co-operating processes.
A producer process produces information that is consumed by a consumer process.
We need a buffer of items that can be filled by the producer and emptied by the
consumer.
The producer and the consumer must be synchronized so that the consumer does
not try to consume an item that has not yet been produced.
The unbounded buffer producer consumer problem places no practical limit on buffer size.
The consumer may have to wait for new items, but the producer can always produce new items
The bounded buffer producer consumer problem assumes a fixed buffer size. The consumer
must wait if the buffer is empty and the producer must wait if the buffer is full.
The buffer may either be provided by the operating system through interprocess
communication facility or by using shared memory.
Let us consider a shared memory solution to the bounded buffer problem.
The producer and consumer processes share the following variables
#define BUFFER_SIZE 10
typedef struct
{
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
The shared buffer is implemented as a circular array with two pointers in and out.
 The variable in points to the next free position in the buffer and out points to the first
full position in the buffer. The buffer is empty when in==out.The buffer is full when
((in+1)%BUFFERSIZE)==out.
The producer process has a local variable nextProduced in which the new item to be
produced is stored.
item nextProduced;
while (1)
{
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
The consumer process has a local variable nextConsumed in which the item to be
consumed is stored.
item nextConsumed;
while (1)
{
while (in == out)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
1.4.8 Interprocess Communication
IPC is a set of methods that allow processes to communicate and to synchronize their
actions without sharing the same address space.
Co-operating processes communicate with each other using a buffer pool.
Buffer pool is provided by the operating system for the co operating processes through
interprocess communication facility(IPC)
IPC is mainly useful in a distributed environment. ie) network.
Eg: chat program used on the WWW.
1) Message Passing System
It allow process to communicate with one another without using shared data.
An IPC facility provide atleast two operations: send(message) and receive(message)
If processes P and Q want to communicate, acommunication link must exist between
them. This link can be
a) Physical Link:
Shared Memory, hardware bus, network.
b)Logical Link: 1) Direct/Indirect communication. 4) Send by copy /reference
2) Symmetric /Asymmetric communication
3) Automatic /Explicit Buffering 5) Fixed /variable sized messages.
2) Naming:
Processes that want to communicate must have a way to refer to each other.They can
use either direct or indirect communication.
a) Direct communication:
With direct communication, each process that wants to communicate must clearly
name the receiver or sender of the communication.
i) Symmetric Addressing:
Both the sender and the receiver processes must name the other to communicate.
send and receive primitives are defined as
1) send(p,message) send a message to p
2) receive(q,message) receive a message from process q.
A communication link has the following properties
1) A link is established automatically
2) A link is associated with exactly two processes.
3) Exactly one link exists between each pair of processes.
ii) Asymmetric Addressing:
Only the sender names the receiver, the receiver is not required to name the sender.
send and receive primitives are defined as
1) send(p,message) send a message to process p.
2) receive(id,message) receive a message from any process; the variable id is set
to the name of the process.
b) Indirect Communication:
The messages are sent to and received from mailboxes or posts.
A mailbox is an object into which messages can be placed and removed by processes.
Each mailbox has a unique identification. Two processes can communicate only if they
share a mailbox.
send and receive primitives are defined as follows.
1) send(A,message) send a message to mailbox A.
2) receive(A,message) receive a message from mailbox A.
A communication link has the following properties
1) A link is established between a pair of processes only if both have a shared mailbox.
2) A link may be associated with more than two processes.
3)a number of different links may exist between each pair of processes.
The operating system must provide a mechanism for the process.
1) create a new mailbox.
2) send and receive messages through the mailbox.
3) delete a mailbox.
The process that creates a mailbox is the mailbox’s owner.
3) Synchronization
Communication between processes takes place by calls to send and receive primitives.
Message passing may be either blocking or non-blocking- also known as
synchronous and asynchronous
send and receive primitives may be either blocking or non-blocking.
1) Blocking send: The sending process is blocked until the message is received by the
receiving process.
2)Non-blocking send: The sending process sends message and continues its operation.
3) Blocking receive: The receiver blocks until a message is available.
4) Non- blocking receive: The receiver retrieves either a valid message or a null.
4) Buffering
Messages exchanged by processes reside in a temporary queue (or) buffer.
A queue can be implemented in three ways
1) Zero Capacity (or) No Buffering:
 The queue has maximum length zero ie) it cannot have any messages waiting
in it. The sender must block until the receiver receives the message.
2) Bounded Capacity (or) Automatic Buffering
 The queue has finite length n. ie) atmost n messages can reside in it. If the
queue is not full, the sender can continue execution without waiting. If the
queue is full, the sender must block until space is available in the queue.
3) Unbounded Capacity (or) Automatic Buffering
 The queue has infinite length ie) any number of messages can reside in it.
The sender never blocks.
5) An Example: Mach
Mach is an example of a message based operating system.
In Mach OS, the communication is carried out by messages. Messages are sent to and
received from mailboxes, called ports.
System calls used are
1) msg_send: Sends a message to a mailbox.
2) msg_receive: Receives a message from mailbox.
3) msg_rpc: To execute remote procedure call.
4) port_allocate: creates a new mailbox and allocates space for its messages.
5) port_status: returns the number of messages in the given mailbox.
The messages are queued in FIFO (First In First Out) order.
1.5 THREADS
A thread is a flow of control (or) single sequence stream within a process. A thread
sometimes called a lightweight process(LWP) is a basic unit of CPU utilization.
It comprises a thread ID, a program counter, a register set and a stack.
It shares code section, data section and other resources such as open files and signals
with other threads belonging to the same process.
A traditional( or heavy weight process) has a single thread of control.
 If a process has multiple threads, it can do more than one task at a time, it is called
multithreading.

a) Single Threaded b) Multithreaded

1.5.1 Motivation
Many software packages are multithreaded. Eg: Web browser, Word processor.
In some situations, a single application may be required to perform several similar
tasks. For eg: a busy web server may have several clients requesting the same resources.
For that, the server acts as a single process that accepts requests. To service that request it
creates a separate process. Otherwise the server would create a thread to accept requests.
Another thread is created to service that requests. It is more efficient.
1.5.2 Benefits
1) Responsiveness
Multithreading allow a program to continue running even if part of it is blocked, thereby
increasing responsiveness to the user.
2) Resource sharing
Threads share the memory and the resources of the process to which they belong.
3) Economy
Allocating memory and resources for thread creation is cheap, since threads share
resources of the process to which they belong
4) Utilization of multiprocessor architecture
Multithreading benefits can be greatly increased in a multiprocessor architecture
1.5.3 User and Kernel threads
Threads may be provided at either the user level, for user threads, or by the kernel for
kernel threads.
a) User Threads
User threads are implemented by a thread library at the user level.
The library provides support for thread creation ,scheduling and management with no
support from the kernel.
Thread creation and scheduling are done in user space.
 User level threads are fast to create and manage.
If any user level thread performing a blocking system call will cause the entire process
to block, even if other threads are run.
Eg: POSIX Pthreads, Mach C threads, Solaries 2 UI-threads.
b) Kernel Threads
Kernel threads are supported directly by the operating system.
The kernel performs thread creation, scheduling and management in kernel space.
Kernel threads are slower to create and manage than user threads.
If a thread performs a blocking system call, the kernel can schedule another thread in
the application for execution.
Eg: Windows NT, Windows 2000, Solaris2, BeOS and Tru64Unix.
Java threads are created and managed by the Java Virtual Machine(JVM)

1.6 MULTITHREADING MODELS

Three types of multithreading models are
1) Many to one model
2) One to one model
3) Many to many model
1.6.1 Many to one model
The many to one model maps many user level threads to one kernel thread.
Thread management is done in user space, so it is efficient.
But the entire process will block if a thread makes a blocking system call. ie) true
concurrency is not gained.
Since only one thread can access the kernel at a time, multiple threads are unable to
run in parallel on multiprocessors.
Eg: Green threads in Solaris 2 and user level thread used this model.

a) Many to one model b) One to one model c) Many to Many model

1.6.2 One to One Model
The one to one model maps each user thread to a kernel thread.
It provides more concurrency by allowing another thread to run when a thread makes a
blocking system call.
It also allows multiple threads to run in parallel on multiprocessors.
The only drawback is that creating a user thread requires creating the corresponding
kernel thread.
Eg: Windows NT, Windows 2000, OS/2 use this model
1.6.3 Many to Many model
The Many to Many model multiplexes many user level threads to a smaller (or) equal
number of kernel threads.
In Many to Many model, true concurrency is gained and the developer is allowed to
create many threads in an application.
Also, when a thread performs a blocking system call, the kernel can schedule another
thread for execution.
Eg: Solaris2, IRIX, HP-UX, Tru64 Unix support this model.

1.7 THREADING ISSUES

Some of the issues considered with multithreaded programs are
1) The fork and exec system calls
2) Cancellation
3) Signal Handling
4) Thread Pools
5) Thread Specific Data
1) The fork and exec system calls
The fork system call is used to create a separate duplicate process.
If one thread in a program calls fork, it duplicates all threads (or) only the thread that
invoked the fork system call.
If a thread invokes the exec system call, the program specified in the parameter to
exec will replace the entire process including all threads.
If exec is called immediately after forking, then duplicating all threads is
unnecessary. In this instance duplicating only the calling thread is appropriate.
2) Cancellation
Thread cancellation is the task of terminating a thread before it has completed.
For eg: When a user presses a stop button on a web browser, the thread loading the web
page is cancelled.
A thread that is to be cancelled is often referred to as the target thread.
Thread cancellation may occur in two different situations
1) Asynchronous Cancellation
One thread immediately terminates the target thread.
 2) Deferred Cancellation
The target thread can periodically check if it should terminate, allowing the target
thread an opportunity to terminate itself in an orderly manner.
Deferred cancellation allows a thread to check if it should be cancelled at a point
when it can safely be cancelled. Pthread refers to such points as cancellation points.
3) Signal Handling
A signal is used to notify a process that a particular event has occurred.
A signal may be received either synchronously or asynchronously.
All signals follow the same pattern
1) A signal is generated by the occurrence of a particular event.
2) A generated signal is delivered to a process
3) Once delivered the signal must be handled.
An example of a synchronous signal includes an illegal memory access or division by zero.
When a signal is generated by an event external to a running process, that process
receives the signal asynchronously. Eg: Terminating a process with keystrokes
(control+c) or having a timer expire.
Every signal must be handled by two possible handlers
1) A default signal handler
2) A user defined signal handler
The following options exist for delivering a signal
a) Deliver the signal to the thread to which the signal applies
b) Deliver the signal to every thread in the process
c) Deliver the signal to certain threads in the process
d) Assign a specific thread to receive all signals for the process.
4) Thread Pools
A number of threads can be created at process startup and place them into a pool,
where they sit and wait for work.
When a server receives a request, it awakens a thread from this pool –if one is
available passing it the request to service. Once the thread completes its service, it
returns to the pool awaiting more work. If the pool contains no available thread, the
server waits until one becomes free.
The benefits of thread pools are
1) It is usually faster to service a request with an existing thread than creating a thread.
2) A thread pool limits the number of threads that exist at any one point.
5) Thread Specific Data
Threads belonging to a process share the data of the process.
However each thread might need its own copy of certain data in some circumstances.
Such data is called thread specific data.
1.8 Pthreads Library
Pthread refers to the POSIX standard defining an API for thread creation and synchronization.
Solaris2 and windows OS does not support Pthreads.
Pthread API is an example of a user level thread library.
Program Explanation
The program creates a separate thread that determines the summation of a non negative integer.
In a Pthread program separate threads begin execution in a specified function. When the
runner function begins, a single thread of control begins in main. After some
initialization, main creates a second thread that begins control in a runner function.
All Pthread programs must include the pthread.h header file.
The statement pthread_t tid declares the identifier for the thread we will create.
Each thread has a set of attributes including stack size and scheduling information.
The pthread_attr_t attr declaration represents the attributes for the thread.
A separate thread is created with a pthread_create function call. In addition to passing
the thread, the thread identifier and the attributes for the thread, we also pass the name of
the function.
Lastly we pass the integer parameter that was provided on the command line, argv[1].
The program has two threads:
The initial threads in main and the thread performing the summation in the
runner function.
After creating the second thread, the main thread will wait for the runner thread to
complete by calling the pthread_join function.
The runner thread will complete when it calls the function pthread.
#include<pthread.h>
#include<stdio.h> pthread_create(&tid,&attr,runner,arv[1]);
int sum; pthread_join(tid,NULL);
main(int argc,char *argv[]) printf(“sum=%d\n”,sum); }
{ void *runner(void *param) {
pthread_t tid; int upper=atoi(param);
pthread_attr_t attr; int i;
if(argc!=2) sum=0;
{ if(upper>0)
fprintf(stderr,”usage:a.out<integer value>\n”); for(i=1;i<=upper;i++) {
exit(); sum=sum+i; }
} pthread_exit(0);
if(atoi(argv[1]<0) }
{
fprintf(stderr,”%d must be <=0\n”,atoi(argv[1]));
exit();
}
pthread_attr_t(&attr); Fig: Multithreaded C Program using the Pthread library.