Processes

• Process Concept
• Process Scheduling
• Operations on Processes
• Cooperating Processes
• Interprocess Communication
• Communication in Client-Server
Systems
• Operations on processes
• Process Synchronization

Operating System Concepts

 Dual Mode Operating System
• In dual-mode operation, there are two
separate modes: monitor mode (also called
'system mode' and 'kernel mode')
• When system is executing user program, then
it will be in user mode
• When system is executing system program,
then it will be in monitor mode

Operating System Concepts

 Process Concept
An operating system executes a variety of programs:
 Batch system – jobs
 Time-shared systems – user programs or tasks
Textbook uses the terms job and process almost
interchangeably.
Process – a program in execution; process execution must
progress in sequential fashion.
A process includes:
 program counter
 stack
 data section
 text

Operating System Concepts

 Process State

As a process executes, it changes state

new: The process is being created.
running: Instructions are being executed.
waiting: The process is waiting for some event to
occur.
ready: The process is waiting to be assigned to a
process.
terminated: The process has finished execution.

Operating System Concepts

Diagram of Process State

Operating System Concepts

 Process Control Block (PCB)
Information associated with each process.
• Process state: It stores state of process (new, ready,
running, waiting, halted)
• Program counter : it indicates the address of next
instruction to be executed for this process.
• CPU registers: The registers are accumulators , index
registers , stack pointers , general purpose registers ,
condition code information. The actual type and
number is underlying machine architecture.
• When an interrupt occurs, the current state of the
process and the value in program counter must be
saved so that after serving the interrupt the process
can be resumed further.
• CPU scheduling information : It includes the priority of
the process, pointers to scheduling queues and other
scheduling parameters.
• Memory-management information : It includes the
information about the value of the base register and
limit registers, page tables or segment tables etc, which
is used during the memory management by the
operating system.
• Accounting information : It includes the amount of CPU
and real time used, time limits, job or process numbers
etc.
• I/O status information :It includes the list of I/O devices
allocated to the process, a list of open files on the disk.
Process Control Block (PCB)

Operating System Concepts

CPU Switch From Process to Process

Operating System Concepts

 Process Scheduling
Process scheduling is an essential part of a
Multiprogramming operating system. Such systems
allow more than one process to be loaded into the
executable memory at a time and loaded process
shares the CPU .
The aim of multiprogramming is that some process
must be in running state all the time so as to
maximize the CPU utilization.
The aim of time sharing is to switch the CPU among
processes so that users can get a feel that CPU is
working for each process at all the time.
To achieve these two aims the process scheduler is
used which selects an available process from the
ready processes.
 Process Scheduling Queues

Job queue – set of all processes in the system.

Ready queue – set of all processes residing in
main memory, ready and waiting to execute.
Usually it is implemented as linked list
Device queues – set of processes waiting for
an I/O device. Each device has its own queue.
Process migration between the various
queues.
Ready Queue And Various I/O Device Queues
• Process 3,14,6 are waiting for disk to become
free so are attached to disk unit 0 queue in
the same order as they appear.
• Process 5 is added to terminal unit 0 device as
it is waiting for that device to get released.
• When any of these devices will get free, the
first process added to that device will be
removed from respective device queue and
will be added to ready queue so that when its
turn and priority matches, it will get scheduled
to CPU.

Operating System Concepts

Representation of Process Scheduling
 Schedulers
Long-term scheduler (or job
scheduler) – selects which processes
should be brought into the ready
queue.
Short-term scheduler (or CPU
scheduler) – selects which process
should be executed next and allocates
CPU.
Addition of Medium Term Scheduling

Operating System Concepts

 Schedulers (Cont.)
Short-term scheduler is invoked very frequently
(milliseconds)  (must be fast).
Long-term scheduler is invoked very infrequently
(seconds, minutes)  (may be slow).
The long-term scheduler controls the degree of
multiprogramming.
Processes can be described as either:
I/O-bound process – spends more time doing I/O than
computations, many short CPU bursts.
CPU-bound process – spends more time doing
computations; few very long CPU bursts.
 int main()
{
int a,b,c;
c= a+b;
b= c;
a = b;
}CPU Bound process
 int main()
{
int a;
sf(“%d”,&a);
pf(“%d”,a);
pf(“hello”);
} I/O bound process
 Context Switch
When CPU switches to another process, the
system must save the state of the old process
and load the saved state for the new process.
Context-switch time is overhead; the system
does no useful work while switching.
Time dependent on hardware support.
 Process Creation
• Parent process create children processes,
which, in turn create other processes, forming
a tree of processes.
• Resource sharing
– Parent and children share all resources.
– Children share subset of parent’s resources.
– Parent and child share no resources.
• Execution
– Parent and children execute concurrently.
– Parent waits until children terminate.

Operating System Concepts

 Process Creation (Cont.)
• Address space
– Child duplicate of parent.
– Child has a program loaded into it.
• UNIX examples
– fork system call creates new process
– exec system call used after a fork to replace the
process’ memory space with a new program.

Operating System Concepts

• After a new child process is created, both
processes will execute the next instruction
following the fork() system call. A child
process uses the same pc(program counter),
same CPU registers, same open files which use
in the parent process.
• It takes no parameters and returns an integer
value. Below are different values returned by
fork().

Operating System Concepts

• It takes no parameters and returns an integer
value. Below are different values returned by
fork().
• Negative Value: creation of a child process
was unsuccessful.
Zero: Returned to the newly created child
process.
Positive value: Returned to parent or caller.
The value contains process ID of newly
created child process.

Operating System Concepts

Processes Tree on a UNIX System

Operating System Concepts

 Process Termination
Process executes last statement and asks the
operating system to decide it (exit).
Output data from child to parent (via wait).
Process’ resources are deallocated by operating
system.
Parent may terminate execution of children
processes (abort).
Child has exceeded allocated resources.
Task assigned to child is no longer required.
Parent is exiting.
Operating system does not allow child to continue if its parent
terminates.
Cascading termination.

Operating System Concepts

 Cooperating Processes
• Independent process cannot affect or cannot
be affected by the execution of another
process.
• Cooperating process can affect or be affected
by the execution of another process.
• Advantages of process cooperation
– Information sharing
– Computation speed-up
– Modularity
– Convenience

Operating System Concepts

Interprocess Communication (IPC)
Mechanism for processes to communicate and to
synchronize their actions.
Message passing system – processes communicate
with each other by means of message passing without
resorting to shared variables.
IPC facility provides two operations:
send(message) – message size fixed or variable
receive(message)
If P and Q wish to communicate, they need to:
establish a communication link between them
exchange messages via send/receive
Implementation of communication link
physical (e.g., shared memory, hardware bus)
logical (e.g., logical properties)

Operating System Concepts

 Direct Communication
• Processes must name each other explicitly:
– send (P, message) – send a message to process P
– receive(Q, message) – receive a message from
process Q
• Properties of communication link
– Links are established automatically.
– A link is associated with exactly one pair of
communicating processes.
– Between each pair there exists exactly one link.
– The link may be unidirectional, but is usually bi-
directional.

Operating System Concepts

 Indirect Communication
• Messages are directed and received from
mailboxes (also referred to as ports).
– Each mailbox has a unique id.
– Processes can communicate only if they share a
mailbox.
• Properties of communication link
– Link established only if processes share a common
mailbox
– A link may be associated with many processes.

Operating System Concepts

 Remote Procedure Calls
• Remote procedure call (RPC) abstracts procedure
calls between processes on networked systems.
• Stubs – client-side proxy for the actual procedure
on the server.
• The client-side stub locates the server and
marshalls the parameters.
• The server-side stub receives this message,
unpacks the marshalled parameters, and
performs the procedure on the server.

Operating System Concepts

 Remote Method Invocation
• Remote Method Invocation (RMI) is a Java
mechanism similar to RPCs.
• RMI allows a Java program on one machine
to invoke a method on a remote object.

Operating System Concepts

 Process Synchronization
• Process Synchronization means sharing
system resources by processes in a such a way
that, Concurrent access to shared data is
handled thereby minimizing the chance of
inconsistent data.
• E.g. ATM(one after another)
• Maintaining data consistency demands
mechanisms to ensure synchronized
execution of cooperating processes.

Operating System Concepts

• Co-operative Process- execution of one
process affected by another
e.g. two processes share memory, resources
buffer, code
• Independent Process- nothing common
between processes

Operating System Concepts

 Background
• Concurrent access to shared data may result
in data inconsistency.
• Maintaining data consistency requires
mechanisms to ensure the orderly execution
of cooperating processes.

Operating System Concepts

 int shared=5
P1 P2
1)X=shared (5) 5) Y=shared (5)
2)X++ (6) 6) Y- - (4)
3)Sleep(1) 7)sleep(1)
4)Shared=X(6) 8) shared=Y (4)
P1 and P2 are cooperating, as they are sharing
variable shared
Value of shared variable is in-consistent

Operating System Concepts

 Race Condition
• Race condition: The situation where several
processes access – and manipulate shared
data concurrently. The final value of the
shared data depends upon which process
finishes last.
• To prevent race conditions, concurrent
processes must be synchronized.

Operating System Concepts

 Bounded Buffer
Producer Consumer
{ {
while(true) while(true)
{ {
while(count==Buffer_size); while(count==0);
count++; count--;
buffer[in]=item; item= buffer[out];
in=(in+1)% out=(out-1)% Buffer_size;
Buffer_size; }
} }
}

Operating System Concepts

 Bounded Buffer
• The statements

counter++;
counter--;
must be performed atomically.
• Atomic operation means an operation that
completes in its entirety without interruption.

Operating System Concepts

 Bounded Buffer
• The statement “count++” may be implemented in
machine language as:
register1 = counter
register1 = register1 + 1
counter = register1

• The statement “count—” may be implemented as:

register2 = counter
register2 = register2 – 1
counter = register2

Operating System Concepts

 Bounded Buffer
• If both the producer and consumer attempt to
update the buffer concurrently, the assembly
language statements may get interleaved.
• Interleaving depends upon how the producer
and consumer processes are scheduled.

Operating System Concepts

 Bounded Buffer
• Assume counter is initially 5. One interleaving of
statements is:
producer: register1 = counter (register1 = 5)
producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = counter (register2 = 5)
consumer: register2 = register2 – 1 (register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter = 4)

• The value of count may be either 4 or 6, where the

correct result should be 5.

Operating System Concepts

 Critical Section
• Each process in the system has a segment of a code
called Critical section. Critical section is a section in
which processes may change variable, update the tables,
write a file etc. In this section shared data can be
accessed.
• No two processes are executing in their critical section at
a time. i.e. when one process is in its critical section, no
other process is to be allowed to execute in its critical
section.
• Critical section has three sections :
• Entry section: This is the section of code, implement a
request to enter in its critical section.

Operating System Concepts

• Exit section: The critical section may be followed
by and exit section. End of critical section.
• Remainder section: remaining code is reminder
section.
• Following diagram shows general structure of a
typical process Pi.

Operating System Concepts

The Critical-Section Problem

Operating System Concepts

 Solution to Critical-Section Problem
1. Mutual Exclusion. If process Pi is executing in its
critical section, then no other processes can be
executing in their critical sections.
2. Progress. If no process is in its critical section, and
if one or more process want to execute their
critical section then any one of these process
must be allowed to get into its critical section.
3. Bounded Waiting. A bound must exist on the
number of times that other processes are allowed
to enter their critical sections

Operating System Concepts

• Only 2 processes, P0 and P1
• General structure of process Pi (other process Pj)
do {
entry section
critical section
exit section
reminder section
} while (1);
• Processes may share some common variables to
synchronize their actions.

Operating System Concepts

• One problem with the lock implementation
shown here is the busy loop used to block
processes in the acquire phase.
• These types of locks are referred to as
spinlocks, because the CPU just sits and spins
while blocking the process.
• Spinlocks are wasteful of CPU cycles, and are a
really bad idea on single-CPU single-threaded
machines, because the spinlock blocks the
entire computer, and doesn't allow any other
process to release the lock.

Operating System Concepts

 Semaphores
• Semaphore S is an integer variable, changed or tested
only by one of two atomic access routines called P and
V (wait() and signal())
wait (S)
{while S≤ 0
; /*no operation*/
S--;
}
signal (S){ S++;}
The operations in both wait() and signal() Are atomic or
invisible i.e when one process modifies the
semaphore value no other process can simultaneously
modify that same semaphore value.
Operating System Concepts
 Semaphore Implementation
• Define a semaphore as a record
typedef struct Process {
int value;
struct process *List;
} semaphore;

• Assume two simple operations:

– block suspends the process that invokes it.
– wakeup(P) resumes the execution of a blocked
process P.

Operating System Concepts

 Implementation
• Semaphore operations now defined as
wait(S):
{S.value--;
if (S.value < 0) {
/*add this process to S.List;*/
block;
}}
signal(S):
{S.value++;
if (S.value <= 0) {
/*remove a process P from S. List ;*/
wakeup(P);
}}

Operating System Concepts

 Deadlock and Starvation
• Deadlock – two or more processes are waiting indefinitely for
an event that can be caused by only one of the waiting
processes.
• Let S and Q be two semaphores
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
Critical section
signal(S); signal(Q);
signal(Q) signal(S);
• Starvation – indefinite blocking. A process may never be
removed from the semaphore queue in which it is suspended.
Operating System Concepts
 Two Types of Semaphores
• Counting semaphore – integer value can range
over an unrestricted domain.
• Binary semaphore – integer value can range only
between 0 and 1; can be simpler to implement.
• Binary semaphores are the locks that provide
mutual exclusion and so also known as mutex
locks.
• Binary semaphores can be used to solve critical
section problem for multiple processes.
• The n processes share a semaphore, mutex which
is initialized to 1.
Operating System Concepts
do {
waiting(mutex);
/*critical section*/
signal (mutex);
/*remainder section*/
}
while(TRUE);

Operating System Concepts

• Counting semaphores are used to control
access to a given resource consisting of finite
number of instances.
• The semaphore is initialized to the number of
resources available.
• Each process performs a wait() operation, it
wishes to use a resource.
• When a process releases a resource, it
performs a signal() operation.

Operating System Concepts

• When all resources are in use, the count for
the semaphore goes to 0.
• Until count becomes greater than 1, all the
processes that wish to use a resource will be
blocked.

Operating System Concepts

 Classical Problems of Synchronization

• Bounded-Buffer Problem

• Readers and Writers Problem

• Dining-Philosophers Problem

Operating System Concepts

Bounded-Buffer Problem Producer Process

do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);

Operating System Concepts

Bounded-Buffer Problem Consumer Process

do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);

Operating System Concepts

 Readers-Writers Problem
• Shared data

semaphore mutex, wrt;

Initially

mutex = 1, wrt = 1, readcount = 0

Operating System Concepts

Readers-Writers Problem Writer Process

wait(wrt);
…
writing is performed
…
signal(wrt);

Operating System Concepts

Readers-Writers Problem Reader Process

wait(mutex);
readcount++;
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount--;
signal(mutex):

Operating System Concepts

 Dining-Philosophers Problem

• Shared data
semaphore chopstick[5];
Initially all values are 1
Operating System Concepts
• Five philosophers sit around a circular table. Each
philosopher spends his life alternatively thinking and
eating. In the centre of the table is a large plate of food. A
philosopher needs two chopsticks to eat a food. As there
are only 5 chopsticks available, one chopstick is placed
between each pair of philosophers and they agree that
each will only use the chopstick to his right and left.
• When he gets hungry, he picks up two chopsticks and eat
for a while. After a philosopher finishes eating he puts
down the chopsticks and starts to think.
• This problem is considered a classic synchronization
problem. It is a simple representation of the need to
allocate several resources among several processes in
deadlock free and starvation free manner.
Operating System Concepts
• Solution to the dining philosopher problem is with
semaphores.
i) A hungry philosophers executes wait() operation
to grab a chopsticks.
ii)After eating is finished, philosopher executes
signal() operation to release chopsticks.

Operating System Concepts

 Dining-Philosophers Problem
• Philosopher i:
do {
wait(chopstick[i])
wait(chopstick[(i+1) % 5])
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);

Operating System Concepts