Unit-II

Chapter 1 - Process Concept

Process Scheduling
Process Scheduling is an OS task that schedules processes of different states
like ready, waiting, and running.

Process scheduling allows OS to allocate a time interval of CPU execution for

each process. Another important reason for using a process scheduling system is that
it keeps the CPU busy all the time. This allows us to get the minimum response time
for programs.

Process Scheduling Queues help you to maintain a distinct queue for each and
every process states and PCBs. All the process of the same execution state are placed
in the same queue. Therefore, whenever the state of a process is modified, its PCB
needs to be unlinked from its existing queue, which moves back to the new state
queue.

Three types of operating system queues are:

1. Job queue – It helps you to store all the processes in the system.
2. Ready queue – This type of queue helps you to set every process residing in the
main memory, which is ready and waiting to execute.

3. Device queues – It is a process that is blocked because of the absence of an I/O

device.

1|Page
 Process Scheduling Queues

In the above-given Diagram,

 Rectangle represents a queue.

 Circle denotes the resource

 Arrow indicates the flow of the process.

1. Every new process first put in the Ready queue .It waits in the ready queue
until it is finally processed for execution. Here, the new process is put in the
ready queue and wait until it is selected for execution or it is dispatched.

2. One of the processes is allocated the CPU and it is executing

3. The process should issue an I/O request

4. Then, it should be placed in the I/O queue.

5. The process should create a new sub process

6. The process should be waiting for its termination.

7. It should remove forcefully from the CPU, as a result interrupt. Once interrupt is
completed, it should be sent back to ready queue.

The two-state process models are:

 Running State
 Not Running State

Running
In the Operating system, whenever a new process is built, it is entered into the
system, which should be running.

Not Running
The process that are not running are kept in a queue, which is waiting for their
turn to execute. Each entry in the queue is a point to a specific process.

The important objectives of Process scheduling

 Maximize the number of interactive users within acceptable response

times.
 Achieve a balance between response and utilization.

 Avoid indefinite postponement and enforce priorities.

 It also should give reference to the processes holding the key resources.

A scheduler is a type of system software that allows you to handle process

scheduling.
2|Page
There are mainly three types of Process Schedulers:

1. Long Term Scheduler

2. Short Term Scheduler

3. Medium Term Scheduler

Long Term Scheduler

Long term scheduler is also known as a job scheduler. This scheduler regulates
the program and select process from the queue and loads them into memory for
execution. It also regulates the degree of multi-programming. The main goal of this
type of scheduler is to offer a balanced mix of jobs, like Processor, I/O jobs, that
allows managing multiprogramming.

Medium Term Scheduler

Medium-term scheduling is an important part of swapping. It enables you to
handle the swapped out-processes. In this scheduler, a running process can become
suspended, which makes an I/O request. A running process can become suspended if
it makes an I/O request. A suspended processes can’t make any progress towards
completion. In order to remove the process from memory and make space for other
processes, the suspended process should be moved to secondary storage.

Short Term Scheduler

Short term scheduling is also known as CPU scheduler. The main goal of this scheduler
is to boost the system performance according to set criteria. This helps you to select from a group of
processes that are ready to execute and allocates CPU to one of them. The dispatcher gives control of the
CPU to the process selected by the short term scheduler.

Long-Term Short-Term Medium-Term

Medium-term is also
Long term is also known Short term is also known as
called swapping
as a job scheduler CPU scheduler
scheduler.
It is either absent or This scheduler is an
It is insignificant in the time-
minimal in a time- element of Time-sharing
sharing order.
sharing system. systems.
Speed is the fastest
Speed is less compared
compared to the short-term
to the short term It offers medium speed.
and medium-term
scheduler.
scheduler.
Allow you to select
It only selects processes
processes from the loads It helps you to send
that is in a ready state of
and pool back into the process back to memory.
the execution.
memory
Offers full control Offers less control Reduce the level of
3|Page
 Long-Term Short-Term Medium-Term
multiprogramming.

Context Switching is a method to store/restore the state or of a CPU in PCB. So

that process execution can be resumed from the same point at a later time. The
context switching method is important for multitasking OS.

Operations on Processes
There are many operations that can be performed on processes. Some of these
are process creation, process preemption, process blocking, and process termination.

Process Creation

Processes need to be created in the system for different operations. This can be
done by the following events

 User request for process creation

 System initialization
 Execution of a process creation system call by a running process
 Batch job initialization

A process may be created by another process using fork(). The creating process
is called the parent process and the created process is the child process. A child
process can have only one parent but a parent process may have many children.
Both the parent and child processes have the same memory image, open files, and
environment strings. However, they have distinct address spaces.
A diagram that demonstrates process creation using fork() is as follows −

Process Preemption

4|Page
 An interrupt mechanism is used in preemption that suspends the process
executing currently and the next process to execute is determined by the short-term
scheduler. Preemption makes sure that all processes get some CPU time for
execution.

A diagram that demonstrates process preemption is as follows −

Process Blocking

The process is blocked if it is waiting for some event to occur. This event may
be I/O as the I/O events are executed in the main memory and don't require the
processor. After the event is complete, the process again goes to the ready state.
A diagram that demonstrates process blocking is as follows −

Process Termination

After the process has completed the execution of its last instruction, it is
terminated. The resources held by a process are released after it is terminated.
5|Page
 A child process can be terminated by its parent process if its task is no longer
relevant. The child process sends its status information to the parent process before
it terminates. Also, when a parent process is terminated, its child processes are
terminated as well as the child processes cannot run if the parent processes are
terminated.

Inter-Process Communication
A process can be of two types:
 Independent process.
 Co-operating process.

An independent process is not affected by the execution of other processes

while a co-operating process can be affected by other executing processes. Though
one can think that those processes, which are running independently, will execute
very efficiently, in reality, there are many situations when co-operative nature can
be utilized for increasing computational speed, convenience, and modularity. Inter-
process communication (IPC) is a mechanism that allows processes to communicate
with each other and synchronize their actions. The communication between these
processes can be seen as a method of co-operation between them. Processes can
communicate with each other through both:
1. Shared Memory
2. Message passing

The following figure shows a basic structure of communication between

processes via the shared memory method and via the message passing method

 
An operating system can implement both methods of communication. The
Communication between processes using shared memory requires processes to
share some variable, and it completely depends on how the programmer will

6|Page
implement it. One way of communication using shared memory can be imagined like
this: Suppose process1 and process2 are executing simultaneously, and they share
some resources or use some information from another process. Process1 generates
information about certain computations or resources being used and keeps it as a
record in shared memory. When process2 needs to use the shared information, it
will check in the record stored in shared memory and take note of the information
generated by process1 and act accordingly. Processes can use shared memory for
extracting information as a record from another process as well as for delivering any
specific information to other processes. 

Consider an example of communication between processes using the shared

memory method.
 
i) Shared Memory Method
Ex: Producer-Consumer problem 

There are two processes: Producer and Consumer. The producer produces
some items and the Consumer consumes that item. The two processes share a
common space or memory location known as a buffer where the item produced by
the Producer is stored and from which the Consumer consumes the item if needed.
There are two versions of this problem: the first one is known as the unbounded
buffer problem in which the Producer can keep on producing items and there is no
limit on the size of the buffer, the second one is known as the bounded buffer
problem in which the Producer can produce up to a certain number of items before it
starts waiting for Consumer to consume it. We will discuss the bounded buffer
problem. First, the Producer and the Consumer will share some common memory,
then the producer will start producing items. If the total produced item is equal to
the size of the buffer, the producer will wait to get it consumed by the Consumer.
Similarly, the consumer will first check for the availability of the item. If no item is
available, the Consumer will wait for the Producer to produce it. If there are items
available, Consumer will consume them.

The pseudo-code is provided below:

Shared Data between the two Processes 

#define buff_max 25
#define mod %
 
    struct item{
 
        // different member of the produced data
        // or consumed data   
        ---------
    }
     

7|Page
    // An array is needed for holding the items.
    // This is the shared place which will be 
    // access by both process  
    // item shared_buff [ buff_max ];
      
    // Two variables which will keep track of
    // the indexes of the items produced by producer
    // and consumer The free index points to
    // the next free index. The full index points to
    // the first full index.
    int free_index = 0;
    int full_index = 0;

Producer Process Code 

item nextProduced;
     
    while(1){
         
        // check if there is no space
        // for production.
        // if so keep waiting.
        while((free_index+1) mod buff_max == full_index);
         
        shared_buff[free_index] = nextProduced;
        free_index = (free_index + 1) mod buff_max;
    }

Consumer Process Code 

item nextConsumed;
         while(1){
                 // check if there is an available
        // item  for consumption.
        // if not keep on waiting for
        // get them produced.
        while((free_index == full_index);
         nextConsumed = shared_buff[full_index];
        full_index = (full_index + 1) mod buff_max;
    }

In the above code, the Producer will start producing again when the
(free_index+1) mod buff max will be free because if it it not free, this implies that
8|Page
there are still items that can be consumed by the Consumer so there is no need to
produce more. Similarly, if free index and full index point to the same index, this
implies that there are no items to consume.
 
ii) Messaging Passing Method

Now, We will start our discussion of the communication between processes via
message passing. In this method, processes communicate with each other without
using any kind of shared memory. If two processes p1 and p2 want to communicate
with each other, they proceed as follows:
 Establish a communication link (if a link already exists, no need to establish
it again.)
 Start exchanging messages using basic primitives.
We need at least two primitives: 
– send(message, destination) or send(message) 
– receive(message, host) or receive(message)
 

The message size can be of fixed size or of variable size. If it is of fixed size, it
is easy for an OS designer but complicated for a programmer and if it is of variable
size then it is easy for a programmer but complicated for the OS designer. A
standard message can have two parts: header and body. 
The header part is used for storing message type, destination id, source id,
message length, and control information. The control information contains
information like what to do if runs out of buffer space, sequence number, priority.
Generally, message is sent using FIFO style.

  

Message Passing through Communication Link.

9|Page
Direct and Indirect Communication link 

Now, We will start our discussion about the methods of implementing

communication links. While implementing the link, there are some questions that
need to be kept in mind like :
 
 
1. How are links established?
2. Can a link be associated with more than two processes?
3. How many links can there be between every pair of communicating
processes?
4. What is the capacity of a link? Is the size of a message that the
link can accommodate fixed or variable?
5. Is a link unidirectional or bi-directional?

A link has some capacity that determines the number of messages that can
reside in it temporarily for which every link has a queue associated with it which can
be of zero capacity, bounded capacity, or unbounded capacity. In zero capacity, the
sender waits until the receiver informs the sender that it has received the message.
In non-zero capacity cases, a process does not know whether a message has been
received or not after the send operation. For this, the sender must communicate
with the receiver explicitly. Implementation of the link depends on the situation, it
can be either a direct communication link or an in-directed communication link. 
Direct Communication links are implemented when the processes use a specific
process identifier for the communication, but it is hard to identify the sender ahead
of time. 

For example the print server. In-direct Communication is done via a shared mailbox
(port), which consists of a queue of messages. The sender keeps the message in
mailbox and the receiver picks them up.

 
Message Passing through Exchanging the Messages.

Synchronous and Asynchronous Message Passing: 

A process that is blocked is one that is waiting for some event, such as a
resource becoming available or the completion of an I/O operation. IPC is possible
between the processes on same computer as well as on the processes running on
different computer i.e. in networked/distributed system. In both cases, the process
may or may not be blocked while sending a message or attempting to receive a
message so message passing may be blocking or non-blocking. Blocking is
considered synchronous and blocking send means the sender will be blocked until
the message is received by receiver. Similarly, blocking receive has the receiver
block until a message is available. Non-blocking is considered  asynchronous and
Non-blocking send has the sender sends the message and continue. Similarly, Non-
blocking receive has the receiver receive a valid message or null. After a careful
10 | P a g e
analysis, we can come to a conclusion that for a sender it is more natural to be non-
blocking after message passing as there may be a need to send the message to
different processes. However, the sender expects acknowledgment from the receiver
in case the send fails. Similarly, it is more natural for a receiver to be blocking after
issuing the receive as the information from the received message may be used for
further execution. At the same time, if the message send keep on failing, the
receiver will have to wait indefinitely. That is why we also consider the other
possibility of message passing. There are basically three preferred combinations:
 
 Blocking send and blocking receive
 Non-blocking send and Non-blocking receive
 Non-blocking send and Blocking receive (Mostly used)

In Direct message passing, The process which wants to communicate must
explicitly name the recipient or sender of the communication. 
e.g. send(p1,message) means send the message to p1. 

Similarly, receive(p2,message) means to receive the message from p2. 

In this method of communication, the communication link gets established
automatically, which can be either unidirectional or bidirectional, but one link can be
used between one pair of the sender and receiver and one pair of sender and
receiver should not possess more than one pair of links. Symmetry and asymmetry
between sending and receiving can also be implemented i.e. either both processes
will name each other for sending and receiving the messages or only the sender will
name the receiver for sending the message and there is no need for the receiver for
naming the sender for receiving the message. The problem with this method of
communication is that if the name of one process changes, this method will not
work.

In Indirect message passing, processes use mailboxes (also referred to as

ports) for sending and receiving messages. Each mailbox has a unique id and
processes can communicate only if they share a mailbox. Link established only if
processes share a common mailbox and a single link can be associated with many
processes. Each pair of processes can share several communication links and these
links may be unidirectional or bi-directional. Suppose two processes want to
communicate through Indirect message passing, the required operations are: create
a mailbox, use this mailbox for sending and receiving messages, then destroy the
mailbox. The standard primitives used are: send(A, message) which means send the
message to mailbox A. The primitive for the receiving the message also works in the
same way e.g. received (A, message). There is a problem with this mailbox
implementation. Suppose there are more than two processes sharing the same
mailbox and suppose the process p1 sends a message to the mailbox, which process
will be the receiver? This can be solved by either enforcing that only two processes
can share a single mailbox or enforcing that only one process is allowed to execute
the receive at a given time or select any process randomly and notify the sender
about the receiver. A mailbox can be made private to a single sender/receiver pair
and can also be shared between multiple sender/receiver pairs. Port is an
implementation of such mailbox that can have multiple senders and a single
receiver. It is used in client/server applications (in this case the server is the
11 | P a g e
receiver). The port is owned by the receiving process and created by OS on the
request of the receiver process and can be destroyed either on request of the same
receiver processor when the receiver terminates itself. Enforcing that only one
process is allowed to execute the receive can be done using the concept of mutual
exclusion. Mutex mailbox is created which is shared by n process. The sender is
non-blocking and sends the message. The first process which executes the receive
will enter in the critical section and all other processes will be blocking and will wait.
Now, let’s discuss the Producer-Consumer problem using the message passing
concept. The producer places items (inside messages) in the mailbox and the
consumer can consume an item when at least one message present in the mailbox.
The code is given below:

Producer Code 
void Producer(void){
         
        int item;
        Message m;
         
        while(1){
             
            receive(Consumer, &m);
            item = produce();
            build_message(&m , item ) ;
            send(Consumer, &m);
        }
    }

Consumer Code 

void Consumer(void){
         
        int item;
        Message m;
         
        while(1){
             
            receive(Producer, &m);
            item = extracted_item();
            send(Producer, &m);
            consume_item(item);
        }
    }

Examples of IPC systems 

 
1. Posix : uses shared memory method.
2. Mach : uses message passing
12 | P a g e
 3. Windows XP : uses message passing using local procedural calls

Communication in client/server Systems:

Client/Server communication involves two components, namely a client and a

server. They are usually multiple clients in communication with a single server. The
clients send requests to the server and the server responds to the client requests.

There are three main methods to client/server communication. These are given
as follows −
1. sockets

2. Remote Procedure Calls

3. Pipes

Sockets are strategies that are used for communication between processes. It is

mainly used in client-server based systems. When two systems want to communicate

with each other, sockets are the endpoint on either end of the communicating

processes.

 A pair of processes communicating over a network employs a pair of

sockets-one for each process.

When two processes want to communicate, there needs to be a connection

between them and at each end of the connection each of this processes will employ a
socket each, so a pair of communicating processes over a network will employ a pair
of sockets one for each process.

 A socket is identified by an IP address concatenated with a port number.

Servers implementing specific services (such as TELNET, FTP, and HTTP)
listen to well-known ports.

For example,

 TELNET server is used for remote logging which listens to port 23

13 | P a g e
  FTP (File transfer protocol) is used for transferring files server listens to
port 21

 Web or Http (Hypertext transfer protocol) server listens to port 80

 A port number is going to identify each of the processes, services that are
going to be provided.

How does communication between these processes employing a pair of

sockets take place?

 The server waits for incoming client requests by listening to a specified

port. Once a request is received, the server accepts a connection from the
client socket to complete the connection.

In a Client-Server systems, the Client asks for information from the server and
the Server provides the information to the client. In order for the client to
communicate to the server and the server to communicate back to the Client, there
needs to be a connection between the Client and the Server.

In order to establish this connection, we are going to use sockets.

14 | P a g e
 Communication using Sockets

From the diagram above, The first part is the Host and the second part is the

Web server. The first part is the Client, the second part is the Server.

 The Client wants to request something from the server, the Server has
to fulfill the request by given whatever the Client asks from the Server. In
other, for this to occur, there must be a communication link between the
Server and the Client. The communication link is being established using
the concept of Socket which we defined earlier.

 From the first part of the diagram, a Client process is trying to establish
a connection between the Client and the Server. The host computer will
assign a port number to this process which wants to communicate with the
server.

 The IP address of the Host Computer from the diagram above

is [Link] a process that belongs to the Host computer wants to
communicate with the Web Server. For that to be possible, a specific port
number will be assigned by the Host computer to the Client process.
The IP address is then assigned a port number [Link]:1625:1625 A
port number is an arbitrary number greater than 1024. It is greater than

15 | P a g e
 1024 because the port numbers below 1024 are considered well known
and are used for implementing standard services.

 Similarly in part B (The webserver) the Web server has a socket. the
socket belongs to the process in the Web server that is going to
communicate with the Client process. It has an IP address and port
number [Link]:80

Port number 80 is less than 1024 because it’s the Web server and not the Client.
The Client is trying to access some services from the Server, Port number 80 belongs
to a standard service.

The packets that are traveling from the Client process to the Server process are
delivered appropriately based on the port numbers

If another process from the Host computer wants to communicate to the same
socket of the Web server, that process will again be assigned another socket. The
socket number will be a new number different from 1625 and greater than 1024

This is how communication between systems/processes takes place using

Sockets. This is another strategy that is used for communication between processes
and this is very specifically used for the Client-Server system.

The Sockets are specifically used only for the Client-Server based systems.

Remote Procedure Call or RPC

Remote Procedure Call or RPC is a powerful technique for constructing

distributed, client-server-based applications. It is also known as a function call or a
subroutine call. A remote procedure call is when a computer program causes a
procedure to execute in a different address space, coded as a local procedure call,
without the programmer explicitly stating the details for the remote interaction. The
programmer writes essentially the same code whether the subroutine is local to the
executing program or remote. This is a form of client-server interaction implemented
via a request-response message-passing system.

16 | P a g e
 The RPC model implies location transparency that calling procedures are
largely the same, whether local or remote. Usually, they are not identical, so that
local calls can be distinguished from remote calls. Remote calls are usually orders of
magnitude slower and less reliable than local calls, so distinguishing them is
important.

RPCs are a form of inter-process communication (IPC), in that different

processes have different address spaces. They have distinct virtual address spaces on
the same host machine, even though the physical address space is the same. While if
they are on different hosts, the physical address space is different.

How to Make a Remote Procedure Call

The calling environment is suspended, procedure parameters are transferred

across the network to the environment where the procedure is to execute, and the
procedure is executed there.

17 | P a g e
 When the procedure finishes and produces its results, it is transferred back to
the calling environment, where execution resumes as if returning from a regular
procedure call.

RPC is especially well suited for client-server interaction in which the flow of
control alternates between the caller and callee. Conceptually, the client and server
do not execute simultaneously; instead, the thread of execution jumps from the caller
to the callee and then back again

Pipes

Pipe is a communication medium between two or more related or interrelated

processes. It can be either within one process or a communication between the child
and the parent processes. Communication can also be multi-level such as
communication between the parent, the child and the grand-child, etc.
Communication is achieved by one process writing into the pipe and other reading
from the pipe. To achieve the pipe system call, create two files, one to write into the
file and another to read from the file.
Pipe mechanism can be viewed with a real-time scenario such as filling water
with the pipe into some container, say a bucket, and someone retrieving it, say with a
mug. The filling process is nothing but writing into the pipe and the reading process is
nothing but retrieving from the pipe. This implies that one output (water) is input for
the other (bucket).

18 | P a g e
#include<unistd.h>

int pipe(int pipedes[2]);

This system call would create a pipe for one-way communication i.e., it creates
two descriptors, first one is connected to read from the pipe and other one is
connected to write into the pipe.
Descriptor pipedes[0] is for reading and pipedes[1] is for writing. Whatever is
written into pipedes[1] can be read from pipedes[0].
This call would return zero on success and -1 in case of failure. To know the
cause of failure, check with errno variable or perror() function.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int open(const char *pathname, int flags);

int open(const char *pathname, int flags, mode_t mode);

Even though the basic operations for file are read and write, it is essential to
open the file before performing the operations and closing the file after completion of
the required operations. Usually, by default, 3 descriptors opened for every process,
which are used for input (standard input – stdin), output (standard output – stdout)
and error (standard error – stderr) having file descriptors 0, 1 and 2 respectively.
This system call would return a file descriptor used for further file operations of
read/write/seek (lseek). Usually file descriptors start from 3 and increase by one
number as the number of files open.
The arguments passed to open system call are pathname (relative or absolute
path), flags mentioning the purpose of opening file (say, opening for read,
O_RDONLY, to write, O_WRONLY, to read and write, O_RDWR, to append to the
existing file O_APPEND, to create file, if not exists with O_CREAT and so on) and the
required mode providing permissions of read/write/execute for user or
owner/group/others. Mode can be mentioned with symbols.
Read – 4, Write – 2 and Execute – 1.
For example: Octal value (starts with 0), 0764 implies owner has read, write
and execute permissions, group has read and write permissions, other has read
permissions. This can also be represented as S_IRWXU | S_IRGRP | S_IWGRP |
S_IROTH, which implies or operation of 0700|0040|0020|0004 → 0764.

19 | P a g e
 This system call, on success, returns the new file descriptor id and -1 in case of
error. The cause of error can be identified with errno variable or perror() function.

#include<unistd.h>

int close(int fd)

The above system call closing already opened file descriptor. This implies the
file is no longer in use and resources associated can be reused by any other process.
This system call returns zero on success and -1 in case of error. The cause of error
can be identified with errno variable or perror() function.

#include<unistd.h>

ssize_t read(int fd, void *buf, size_t count)

The above system call is to read from the specified file with arguments of file
descriptor fd, proper buffer with allocated memory (either static or dynamic) and the
size of buffer.
The file descriptor id is to identify the respective file, which is returned after
calling open() or pipe() system call. The file needs to be opened before reading from
the file. It automatically opens in case of calling pipe() system call.
This call would return the number of bytes read (or zero in case of encountering
the end of the file) on success and -1 in case of failure. The return bytes can be
smaller than the number of bytes requested, just in case no data is available or file is
closed. Proper error number is set in case of failure.
To know the cause of failure, check with errno variable or perror() function.

#include<unistd.h>

ssize_t write(int fd, void *buf, size_t count)

The above system call is to write to the specified file with arguments of the file
descriptor fd, a proper buffer with allocated memory (either static or dynamic) and
the size of buffer.
The file descriptor id is to identify the respective file, which is returned after
calling open() or pipe() system call.
The file needs to be opened before writing to the file. It automatically opens in
case of calling pipe() system call.
This call would return the number of bytes written (or zero in case nothing is
written) on success and -1 in case of failure. Proper error number is set in case of
failure.
To know the cause of failure, check with errno variable or perror() function.

Example program 1 − Program to write and read two messages using pipe.

20 | P a g e
Algorithm
Step 1 − Create a pipe.
Step 2 − Send a message to the pipe.
Step 3 − Retrieve the message from the pipe and write it to the standard output.
Step 4 − Send another message to the pipe.
Step 5 − Retrieve the message from the pipe and write it to the standard output.
Note − Retrieving messages can also be done after sending all messages.
Source Code: simplepipe.c

#include<stdio.h>
#include<unistd.h>

int main() {
int pipefds[2];
int returnstatus;
char writemessages[2][20]={"Hi", "Hello"};
char readmessage[20];
returnstatus = pipe(pipefds);

if (returnstatus == -1) {
printf("Unable to create pipe\n");
return 1;
}

printf("Writing to pipe - Message 1 is %s\n", writemessages[0]);

write(pipefds[1], writemessages[0], sizeof(writemessages[0]));
read(pipefds[0], readmessage, sizeof(readmessage));
printf("Reading from pipe – Message 1 is %s\n", readmessage);
printf("Writing to pipe - Message 2 is %s\n", writemessages[0]);
write(pipefds[1], writemessages[1], sizeof(writemessages[0]));
read(pipefds[0], readmessage, sizeof(readmessage));
printf("Reading from pipe – Message 2 is %s\n", readmessage);
return 0;
}

Execution Steps

Compilation
gcc -o simplepipe simplepipe.c

Execution/Output
Writing to pipe - Message 1 is Hi
Reading from pipe – Message 1 is Hi
Writing to pipe - Message 2 is Hi
Reading from pipe – Message 2 is Hell

21 | P a g e
Two-way Communication Using Pipes

Pipe communication is viewed as only one-way communication i.e., either the

parent process writes and the child process reads or vice-versa but not both.
However, what if both the parent and the child needs to write and read from the pipes
simultaneously, the solution is a two-way communication using pipes. Two pipes are
required to establish two-way communication.
Following are the steps to achieve two-way communication −
Step 1 − Create two pipes. First one is for the parent to write and child to read, say
as pipe1. Second one is for the child to write and parent to read, say as pipe2.
Step 2 − Create a child process.
Step 3 − Close unwanted ends as only one end is needed for each communication.
Step 4 − Close unwanted ends in the parent process, read end of pipe1 and write
end of pipe2.
Step 5 − Close the unwanted ends in the child process, write end of pipe1 and read
end of pipe2.
Step 6 − Perform the communication as required.

Sample program 1 − Achieving two-way communication using pipes.

Algorithm
Step 1 − Create pipe1 for the parent process to write and the child process to read.
Step 2 − Create pipe2 for the child process to write and the parent process to read.
Step 3 − Close the unwanted ends of the pipe from the parent and child side.
Step 4 − Parent process to write a message and child process to read and display on
the screen.

22 | P a g e
Step 5 − Child process to write a message and parent process to read and display on
the screen.
Source Code: twowayspipe.c

#include<stdio.h>
#include<unistd.h>

int main() {
int pipefds1[2], pipefds2[2];
int returnstatus1, returnstatus2;
int pid;
char pipe1writemessage[20] = "Hi";
char pipe2writemessage[20] = "Hello";
char readmessage[20];
returnstatus1 = pipe(pipefds1);

if (returnstatus1 == -1) {
printf("Unable to create pipe 1 \n");
return 1;
}
returnstatus2 = pipe(pipefds2);

if (returnstatus2 == -1) {
printf("Unable to create pipe 2 \n");
return 1;
}
pid = fork();

if (pid != 0) // Parent process {

close(pipefds1[0]); // Close the unwanted pipe1 read side
close(pipefds2[1]); // Close the unwanted pipe2 write side
printf("In Parent: Writing to pipe 1 – Message is %s\n", pipe1writemessage);
write(pipefds1[1], pipe1writemessage, sizeof(pipe1writemessage));
read(pipefds2[0], readmessage, sizeof(readmessage));
printf("In Parent: Reading from pipe 2 – Message is %s\n", readmessage);
} else { //child process
close(pipefds1[1]); // Close the unwanted pipe1 write side
close(pipefds2[0]); // Close the unwanted pipe2 read side
read(pipefds1[0], readmessage, sizeof(readmessage));
printf("In Child: Reading from pipe 1 – Message is %s\n", readmessage);
printf("In Child: Writing to pipe 2 – Message is %s\n", pipe2writemessage);
write(pipefds2[1], pipe2writemessage, sizeof(pipe2writemessage));
}
return 0;
}

Execution Steps

23 | P a g e
Compilation
gcc twowayspipe.c –o twowayspipe

Execution
In Parent: Writing to pipe 1 – Message is Hi
In Child: Reading from pipe 1 – Message is Hi
In Child: Writing to pipe 2 – Message is Hello
In Parent: Reading from pipe 2 – Message is Hello

24 | P a g e
 Chapter 2

Multithreaded Programming
Multithreading Models
Multi threading is a process of multiple threads executes at same time. Many
operating systems support kernel thread and user thread in a combined way.
Example of such system is Solaris.
Multi threading model are of three types. 
1. Many to many model.
2. Many to one model.
3. one to one model.
Many to Many Model 
In this model, we have multiple user threads multiplex to same or lesser
number of kernel level threads. Number of kernel level threads are specific to the
machine, advantage of this model is if a user thread is blocked we can schedule
others user thread to other kernel thread. Thus, System doesn’t block if a particular
thread is blocked. 
It is the best multi threading model.

Many to One Model 

In this model, we have multiple user threads mapped to one kernel thread. In
this model when a user thread makes a blocking system call entire process blocks.
As we have only one kernel thread and only one user thread can access kernel at a
time, so multiple threads are not able access multiprocessor at the same time. 
The thread management is done on the user level so it is more efficient.

25 | P a g e
One to One Model
In this model, one to one relationship between kernel and user thread. In this
model multiple thread can run on multiple processor. Problem with this model is that
creating a user thread requires the corresponding kernel thread. 
As each user thread is connected to different kernel , if any user thread makes
a blocking system call, the other user threads won’t be blocked.

Thread Libraries

A thread library provides the programmer an API for creating and managing
threads. There are two primary ways of implementing a thread library. The first
approach is to provide a library entirely in user space with no kernel support. All
code and data structures for the library exist in user space. This means that invoking
a function in the library results in a local function call in user space and not a system
call.

The second approach is to implement a kernel-level library supported directly

by the operating system. In this case, code and data structures for the library exist
in kernel space. Invoking a function in the API for the library typically results in a
system call to the kernel.

Three main thread libraries are in use today:

1. POSIX Pthreads,
2. Win32, and

3. Java Pthreads

The threads extension of the POSIX standard, may be provided as either a

user- or kernel-level library. The Win32 thread library is a kernel-level library
available on Windows systems. The Java thread API allows thread creation and
management directly in Java programs. However, because in most instances the JVM
is running on top of a host operating system, the Java thread API is typically
implemented using a thread library available on the host system. This means that on

26 | P a g e
Windows systems, Java threads are typically implemented using the Win32 API;
UNIX and Linux systems often use Pthreads.

We describe basic thread creation using these three thread libraries. We design
a multithreaded program that performs the summation of a non-negative integer in a
separate thread using the well-known summation function. For example, if N were 5,
this function would represent the summation from 0 to 5, which is 15. Each of the
three programs will be run with the upper bounds of the summation entered on the
command line; thus, if the user enters 8, the summation of the integer values from 0
to 8 will be output.

Pthreads
Pthreads refers to the POSIX standard (IEEE 1003.1c) defining an API for
thread creation and synchronization. This is a specification for thread behavior, not
an implementation. Operating system designers may implement the specification in
any way they wish. Numerous systems implement the Pthreads specification,
including Solaris, Linux, Mac OS X, and Tru64 UNIX. Shareware implementations are
available in the public domain for the various Windows operating systems as well. In
a Pthreads program, separate threads begin execution in a specified function,  this is
the runner () function. When this program begins, a single thread of control begins in
main().

After some initialization, main() creates a second thread that begins control in

the runner () function. Both threads share the global data sum. Let's look more
closely at this program. All Pthreads programs must include the pthread.h header
file. The statement pthreadjt 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. We set

27 | P a g e
the attributes in the function call pthread_attr_init C&attr). Because we did not
explicitly set any attributes, we use the default attributes provided. A separate
thread is created with the pthread_create () function call. In addition to passing the
thread identifier and the attributes for the thread, we also pass the name of the
function where the new thread will begin execution-—in this case, the runner ()
function. Last, we pass the integer parameter that was provided on the command
line, argv [1]. At this point, the program has two threads: the initial (or parent)
thread in main() and the summation (or child) thread performing the summation
operation in the runner () function. After creating the summation thread, the parent
thread will wait for it to complete by calling the pthread_join() function. The
summation thread will complete when it calls the function [Link]() . Once the
summation thread has returned, the parent thread will output the value of the
shared data sum.

Win32 Threads
The technique for creating threads using the Win32 thread library is similar to
the Pthreads technique in several ways. we must include the windows.h header file
when using the Win32 API. Just as in the Pthreads, data shared by the separate
threads—in this case, Sum—are declared globally (the DWORD data type is an
unsigned 32-bit integer. We also define the SummationO function that is to be
performed in a separate thread. This function is passed a pointer to a void, which
Win32 defines as LPVOID. The thread performing this function sets the global data
Sum to the value of the summation from 0 to the parameter passed to SummationO.

Threads are created in the Win32 API using the CreateThreadO function and—
just as in Pthreads—a set of attributes for the thread is passed to this function.
These attributes include security information, the size of the stack, and a flag that
can be set to indicate if the thread is to start in a suspended state. In this program,
we use the default values for these attributes (which do not initially set the thread to
a suspended state and instead make it eligible to be run by the CPU scheduler). Once
the summation thread is created, the parent must wait for it to complete before
outputting the value of Sum, as the value is set by the summation thread. Recall
that the Pthread program had the parent thread wait for the summation thread using
the pthread join() statement. We perform the equivalent of this in the Win32 API
using the WaitForSingleObject () function, which causes the creating thread to block
until the summation thread has exited.

Java Threads
Threads are the fundamental model of program execution in a Java program,
and the Java language and its API provide a rich set of features for the creation and
management of threads. All Java programs comprise at least a single thread, even a
28 | P a g e
simple Java program consisting of only a main() method runs as a single thread in
the JVM. There are two techniques for creating threads in a Java program. One
approach is to create a new class that is derived from the Thread class and to
override its run() method. An alternative—and more commonly used— technique is
to define a class that implements the Runnable interface.

The JVM and Host Operating System

The JVM is typically implemented on top of a host operating system. This setup
allows the JVM to bide the implementation details of the underlying operating system
and to provide a consistent, abstract environment that allows Java programs to
operate on any platform that supports- a JVM. The specification for the JVM does not
indicate how Java 'threads are to be mapped to the underlying operating system,
instead leaving that decision to the particular implementation of the JVM. For
example, the Windows XP operating system uses the one-to-one model; therefore,
each Java thread for a ' JVVI running on such a system maps to a kernel thread. On
operating systems that use the [Link]-to-many model.(such as Tru64 UNIX), a Java
thread is mapped according to the many-to-many model. Solaris ini tially
implemented the JVM using the many-to-one model (the green thre'adslibrary,'
mentioned-earlier). Later releases of the JVM were implemented using the many-to-
many model.

Beginning with Solaris 9, Java threads were mapped using the one-to-one
model. In addition, there may be a relationship between the Java thread library and-
the-thread library on the host operating system. For example, implementations of a.
JVM for the Windows family of operating systems might use the Win32 API when
creating Java threads; Linux and Solaris systems might use the Pthreads -APL

The Runnable interface is defined as follows: public interface Runnable { public

abstract void run(); When a class implements Runnable, it must define a run()
method. The code implementing the run() method is what runs as a separate
thread. Java version of a multithreaded program that determines the summation of a
non-negative integer. The Summation class implements the Runnable interface.
Thread creation is performed by creating an object instance of the Thread class and
passing the constructor a Runnable object. Creating a Thread object does not
specifically create the new thread; rather, it is the start () method that actually
creates the new thread. Calling the start () method for the new object does two
things:

1. It allocates memory and initializes a new thread in the JVM.

29 | P a g e
 2. It calls the run () method, making the thread eligible to be run by the
JVM. (Note that we never call the run() method directly. Rather, we call the
start () method, and it calls the run() method on our behalf.)

When the summation program runs, two threads are created by the JVM. The
first is the parent thread, which starts execution in the main() method. The second
thread is created when the start () method on the Thread object is invoked. This
child thread begins execution in the run () method of the Summation class. After
outputting the value of the summation, this thread terminates when it exits from its
run () method. Sharing of data between threads occurs easily in Win32 and
Pthreads, as shared data are simply declared globally.

As a pure object-oriented language, Java has no such notion of global data; if

two or more threads are to share data in a Java program, the sharing occurs by
passing reference to the shared object to the appropriate threads. In the Java
program shown in Figure 4.8, the main thread and the summation thread share the
the object instance of the Sum class. This shared object is referenced through the
appropriate getSum() and setSum() methods. (You might wonder why we don't use
an Integer object rather than designing a new sum class.

The reason is that the Integer class is immutable—that is, once its value is set,
it cannot change.) Recall that the parent threads in the Pthreads and Win32 libraries
use pthreacLjoin() and WaitForSingleObject() (respectively) to wait for the
summation threads to finish before proceeding. The join() method in Java provides
similar functionality. (Notice that join() can throw an InterruptedException, which we
choose to ignore.)

Threading Issues
There are several threading issues when we are in a multithreading
environment. They are

1. System Calls
2. Thread Cancellation

3. Signal Handling

4. Thread Pool

5. Thread Specific Data

30 | P a g e
1. fork() and exec() System Calls

The fork() and exec() are the system calls. The fork() call creates a duplicate
process of the process that invokes fork(). The new duplicate process is called child
process and process invoking the fork() is called the parent process. Both the parent
process and the child process continue their execution from the instruction that is just
after the fork().

Consider that a thread of the multithreaded program has invoked the fork(). So,
the fork() would create a new duplicate process. Here the issue is whether the new
duplicate process created by fork() will duplicate all the threads of the parent process
or the duplicate process would be single-threaded.

There are two versions of fork() in some of the UNIX systems. Either the fork()
can duplicate all the threads of the parent process in the child process or the fork()
would only duplicate that thread from parent process that has invoked it.

exec() system call when invoked replaces the program along with all its threads
with the program that is specified in the parameter to exec(). Typically the exec()
system call is lined up after the fork() system call.

Here the issue is if the exec() system call is lined up just after the fork() system
call then duplicating all the threads of parent process in the child process by fork() is
useless. As the exec() system call will replace the entire process with the process
provided to exec() in the parameter.

In such case, the version of fork() that duplicates only the thread that invoked
the fork() would be appropriate.

2. Thread cancellation

Termination of the thread in the middle of its execution it is termed as ‘thread

cancellation’. Consider that there is a multithreaded program which has let its
multiple threads to search through a database for some information. However, if one
of the thread returns with the desired result the remaining threads will be cancelled.
31 | P a g e
 Now a thread which we want to cancel is termed as target thread. Thread
cancellation can be performed in two ways:

Asynchronous Cancellation: In asynchronous cancellation, a thread is

employed to terminate the target thread instantly.

Deferred Cancellation: In deferred cancellation, the target thread is

scheduled to check itself at regular interval whether it can terminate itself or not.

The issue related to the target threads are listed below:

 What if the resources had been allotted to the cancel target thread?
 What if the target thread is terminated when it was updating the data,
it was sharing with some other thread.

Here the asynchronous cancellation of the thread where a thread immediately

cancels the target thread without checking whether it is holding any resources or not
creates troublesome.

In deferred cancellation, the thread that indicates the target thread about the
cancellation, the target thread crosschecks its flag in order to confirm that it should it
be cancelled immediately or not. The thread cancellation takes place where they can
be cancelled safely such points are termed as cancellation points by Pthreads.

3. Signal Handling

Signal handling is more convenient in the single-threaded program as the signal

would be directly forwarded to the process. But when it comes to multithreaded
program, the issue arrives to which thread of the program the signal should be
delivered.

Let’s say the signal would be delivered to:

 All the threads of the process.

 To some specific threads in a process.

 To the thread to which it applies

 Or you can assign a thread to receive all the signals.

How the signal would be delivered to the thread would be decided, depending
upon the type of generated signal. The generated signal can be classified into two
type’s synchronous signal and asynchronous signal.

Synchronous signals are forwarded to the same process that leads to the
generation of the signal. Asynchronous signals are generated by the event external to
the running process thus the running process receives the signals asynchronously.

32 | P a g e
 So if the signal is synchronous it would be delivered to the specific thread
causing the generation of the signal. If the signal is asynchronous it cannot be
specified to which thread of the multithreaded program it would be delivered. If the
asynchronous signal is notifying to terminate the process the signal would be
delivered to all the thread of the process.

The issue of an asynchronous signal is resolved up to some extent in most of the

multithreaded UNIX system. Here the thread is allowed to specify which signal it can
accept and which it cannot. However, the Window operating system does not support
the concept of the signal instead it uses asynchronous procedure call (ACP) which is
similar to the asynchronous signal of the UNIX system.

UNIX allows the thread to specify which signal it can accept and which it will not
whereas the ACP is forwarded to the specific thread.

4. Thread Pool

When a user requests for a webpage to the server, the server creates a
separate thread to service the request. Although the server also has some potential
issues. Consider if we do not have a bound on the number of actives thread in a
system and would create a new thread for every new request then it would finally
result in exhaustion of system resources.

We are also concerned about the time it will take to create a new thread. It
must not be that case that the time require to create a new thread is more than the
time required by the thread to service the request and then getting discarded as it
would result in wastage of CPU time.

The solution to this issue is the thread pool. The idea is to create a finite
amount of threads when the process starts. This collection of threads is referred to as
the thread pool. The threads stay in the thread pool and wait till they are assigned
any request to be serviced.

Whenever the request arrives at the server, it invokes a thread from the pool
and assigns it the request to be serviced. The thread completes its service and return
back to the pool and wait for the next request.

If the server receives a request and it does not find any thread in the thread
pool it waits for some or the other thread to become free and return to the pool. This
much better than creating a new thread each time a request arrives and convenient
for the system that cannot handle a large number of concurrent threads.

5. Thread Specific data

We all know the fact that the threads belonging to the same process share the
data of that process. Here the issue is what if each particular thread of the process

33 | P a g e
needs its own copy of data. So the specific data associated with the specific thread is
referred to as thread-specific data.

Consider a transaction processing system, here we can process each transaction

in a different thread. To determine each transaction uniquely we will associate a
unique identifier with it. Which will help the system to identify each transaction
uniquely.

As we are servicing each transaction in a separate thread. So we can use

thread-specific data to associate each thread to a specific transaction and its unique
id. Thread libraries such as Win32, Pthreads and Java support to thread-specific data.

So these are threading issues that occur in the multithreaded programming

environment. We have also seen how these issues can be resolved.

34 | P a g e
 Chapter-3
Process Scheduling
Basic Concepts of Process Scheduling
The process scheduling is the activity of the process manager that handles the
removal of the running process from the CPU and the selection of another process on
the basis of a particular strategy.
Process scheduling is an essential part of Multiprogramming operating systems.
Such operating systems allow more than one process to be loaded into the executable
memory at a time and the loaded process shares the CPU using time multiplexing.

Categories of Scheduling

There are two categories of scheduling:

1. Non-preemptive: Here the resource can’t be taken from a process until the
process completes execution. The switching of resources occurs when the
running process terminates and moves to a waiting state.
2. Preemptive: Here the OS allocates the resources to a process for a fixed
amount of time. During resource allocation, the process switches from running
state to ready state or from waiting state to ready state. This switching occurs
as the CPU may give priority to other processes and replace the process with
higher priority with the running process.

Process Scheduling Queues

The OS maintains all Process Control Blocks (PCBs) in Process Scheduling

Queues. The OS maintains a separate queue for each of the process states and PCBs
of all processes in the same execution state are placed in the same queue. When the
state of a process is changed, its PCB is unlinked from its current queue and moved
to its new state queue.
The Operating System maintains the following important process scheduling queues −
 Job queue − This queue keeps all the processes in the system.
 Ready queue − This queue keeps a set of all processes residing in main
memory, ready and waiting to execute. A new process is always put in this
queue.
 Device queues − The processes which are blocked due to unavailability of an
I/O device constitute this queue.

35 | P a g e
 The OS can use different policies to manage each queue (FIFO, Round Robin,
Priority, etc.). The OS scheduler determines how to move processes between the
ready and run queues which can only have one entry per processor core on the
system; in the above diagram, it has been merged with the CPU.
Scheduling Criteria

The different CPU scheduling algorithms have different properties and the

choice of a particular algorithm depends on various factors. Many criteria have been
suggested for comparing CPU scheduling algorithms. 

The criteria include the following: 

1. CPU utilization: The main objective of any CPU scheduling algorithm is to keep
the CPU as busy as possible. Theoretically, CPU utilization can range from 0 to 100
but in a real-time system, it varies from 40 to 90 percent depending on the load
upon the system. 

2. Throughput: A measure of the work done by the CPU is the number of

processes being executed and completed per unit of time. This is called
throughput. The throughput may vary depending on the length or duration of the
processes. 

3. Turnaround time: For a particular process, an important criterion is how long

it takes to execute that process. The time elapsed from the time of submission of
a process to the time of completion is known as the turnaround time. Turn-around
time is the sum of times spent waiting to get into memory, waiting in the ready
queue, executing in CPU, and waiting for I/O. The formula to calculate Turn
Around Time = Compilation Time – Arrival Time.

4. Waiting time: A scheduling algorithm does not affect the time required to
complete the process once it starts execution. It only affects the waiting time of a
process i.e. time spent by a process waiting in the ready queue. The formula for
calculating Waiting Time = Turnaround Time – Burst Time.

36 | P a g e
 5. Response time: In an interactive system, turn-around time is not the best
criterion. A process may produce some output fairly early and continue computing
new results while previous results are being output to the user. Thus another
criterion is the time taken from submission of the process of the request until the
first response is produced. This measure is called response time. The formula to
calculate Response Time = CPU Allocation Time(when the CPU was allocated for
the first) – Arrival Time

6. Completion time: The completion time is the time when the process stops
executing,  which means that the process has completed its burst time and is
completely executed.

7. Priority: If the operating system assigns priorities to processes, the scheduling

mechanism should favor the higher-priority processes.

8. Predictability: A given process always should run in about the same amount of
time under a similar system load.
 
There are various CPU Scheduling algorithms such as-  
 First Come First Served (FCFS)
 Shortest Job First (SJF)
 Longest Job First (LJF)
 Priority Scheduling
 Round Robin (RR)
 Shortest Remaining Time First (SRTF)
 Longest Remaining Time First (LRTF)

Scheduling Algorithms

CPU Scheduling is a process of determining which process will own CPU for
execution while another process is on hold. The main task of CPU scheduling is to
make sure that whenever the CPU remains idle, the OS at least select one of the
processes available in the ready queue for execution. The selection process will be
carried out by the CPU scheduler. It selects one of the processes in memory that are
ready for execution.

1. FCFS Scheduling Algorithms in OS (Operating System)

First come first serve (FCFS) scheduling algorithm simply schedules the jobs
according to their arrival time. The job which comes first in the ready queue will get
the CPU first. The lesser the arrival time of the job, the sooner will the job get the
CPU. FCFS scheduling may cause the problem of starvation if the burst time of the
first process is the longest among all the jobs.

Advantages of FCFS
37 | P a g e
 o Simple
o Easy
o First come, First serve

Disadvantages of FCFS

1. The scheduling method is non preemptive, the process will run to the
completion.
2. Due to the non-preemptive nature of the algorithm, the problem of starvation
may occur.
3. Although it is easy to implement, but it is poor in performance since the
average waiting time is higher as compare to other scheduling algorithms.

Example

Let's take an example of The FCFS scheduling algorithm. In the Following

schedule, there are 5 processes with process ID P0, P1, P2, P3 and P4. P0 arrives
at time 0, P1 at time 1, P2 at time 2, P3 arrives at time 3 and Process P4 arrives at
time 4 in the ready queue. The processes and their respective Arrival and Burst time
are given in the following table.

The Turnaround time and the waiting time are calculated by using the following
formula.

1. Turn Around Time = Completion Time - Arrival Time   
2. Waiting Time = Turnaround time - Burst Time   

The average waiting Time is determined by summing the respective waiting time of all the processes and
divided the sum by the total number of processes.

Process Arrival Burst Completion Turn Waiting

ID Time Time Time Around Time
Time

0 0 2 2 2 0

1 1 6 8 7 1

2 2 4 12 10 6

3 3 9 21 18 9

4 6 12 33 29 17

Avg Waiting Time=31/5

38 | P a g e
 (Gantt chart)

2. Shortest Job First (SJF) Scheduling

SJF scheduling algorithm, schedules the processes according to their burst time.

In SJF scheduling, the process with the lowest burst time, among the list of
available processes in the ready queue, is going to be scheduled next.

However, it is very difficult to predict the burst time needed for a process hence
this algorithm is very difficult to implement in the system.

Advantages of SJF

1. Maximum throughput
2. Minimum average waiting and turnaround time

Disadvantages of SJF

1. May suffer with the problem of starvation

2. It is not implementable because the exact Burst time for a process can't be
known in advance.

There are different techniques available by which, the CPU burst time of the
process can be determined.

Example

In the following example, there are five jobs named as P1, P2, P3, P4 and P5. Their
arrival time and burst time are given in the table below.

39 | P a g e
 PID Arrival Burst Completion Turn Around Waiting
Time Time Time Time Time

1 1 7 8 7 0

2 3 3 13 10 7

3 6 2 10 4 2

4 7 10 31 24 14

5 9 8 21 12 4

Since, No Process arrives at time 0 hence; there will be an empty slot in

the Gantt chart from time 0 to 1 (the time at which the first process arrives).

According to the algorithm, the OS schedules the process which is having the
lowest burst time among the available processes in the ready queue.

Till now, we have only one process in the ready queue hence the scheduler will
schedule this to the processor no matter what is its burst time.

This will be executed till 8 units of time. Till then we have three more processes
arrived in the ready queue hence the scheduler will choose the process with the
lowest burst time.

Among the processes given in the table, P3 will be executed next since it is
having the lowest burst time among all the available processes.

This is the procedure of shortest job first (SJF) scheduling algorithm.

         Avg Waiting Time = 27/5

40 | P a g e
3. Longest Job First Scheduling Algorithm
Longest Job First (LJF) scheduling comes under the category of the non-
preemptive scheduling algorithm. This algorithm mainly keeps the track of Burst
time of all processes that are available at the arrival time itself and then it will assign
the processor to the process having the longest burst time. In this algorithm, once a
process starts its execution then it cannot be interrupted in between its processing.
Any other process can be executed only after the assigned process has completed its
processing and has been terminated.

This scheduling is similar to the SJF scheduling algorithm. But, in this

scheduling algorithm, the priority is given to the process having the longest burst
time.

Although this scheduling algorithm is not considered to be an efficient way of

scheduling the processes because there are many drawbacks of it:

 The first one is the Convoy effect is displayed by it

 The second one is this algorithm has a very large average turn-around time and
average waiting time. Due to these two, the effectiveness of the system
decreases and processing becomes slow.

In a situation if two processes having the same burst time then the tie is broken
using FCFS i.e., the process that arrived first is processed first.

Let us take a look at the Procedure used in LJF scheduling:

 In the First step, the algorithm sort the processes according to the increasing
order of their Arrival Time.

 In the second step, it will choose the process having the highest Burst Time
among all the processes that have arrived till that time.

 After that, it will process it for its given burst time. The LJF also checks if any
other process arrives until this process completes its execution.

 last but not least it will Repeat all the above steps until all the processes are
executed.

Now its time to take a look at the example of LJF Scheduling:

Longest Job First Scheduling Example

41 | P a g e
 In the above example, four processes P1, P2, P3, P4 are given along with their
Burst time and arrival time.

Explanation

Let us understand the working of LJF in the Gantt chart given above;

1. At t = 0, there is one process that is available having 2 units of burst time. So,
select P1 and execute it for 2 ms.
2. At t = 2 i.e. after P1 gets executed, The Available Processes are P2, P3. As you
can see the burst time of P3 is more than P2. So, select P3 and execute it for
5ms.
3. At t = 7 i.e. after the execution of P3, the Available Processes are P2, P4. As
you can see the burst time of P4 is more than P2. So, select P4 and execute it
for 7ms.
4. Finally, after the completion of P4 execute the process P2 for 3 ms.

We can determine the completion time easily with the help of the Gantt chart. Let us
calculate the waiting time and turnaround time.

42 | P a g e
 Turn around
Time Waiting Time

Arrival Burst Completion Turn Around Waiting Time =

Process
Time Time Time Time = Turn Around
Completion Time – Burst
Time – Arrival Time
Time

P1 0 2 2 2-0=2 2-2=0

P2 1 3 17 17-1=16 16-3=13

P3 2 5 7 7-2=5 5-5=0

P4 3 7 14 14-3=11 11-7=4
Average waiting time is calculated by adding the waiting time of all processes and
then dividing them by no. of processes.

average waiting time = waiting for the time of all processes/ [Link] processes

average waiting time=0+13+0+4/4=17/4=4.25ms

Disadvantages of LJF Scheduling

 This algorithm leads to the reduction of processing speed due to which there is
a reduction in the efficiency and utilization of the system.
 Due to this algorithm, for a given set of processes, the average waiting time
and average turn-around time increase.
 This algorithm leads to the convoy effect.
 With this algorithm, there is a possibility that a short process may never get
executed and the system keeps on executing the long processes.
 Priority scheduling is a non-preemptive algorithm and one of the most common
scheduling algorithms in batch systems.
 Each process is assigned a priority. Process with highest priority is to be
executed first and so on.
 Processes with same priority are executed on first come first served basis.
 Priority can be decided based on memory requirements, time requirements or
any other resource requirement.
4. Priority Scheduling Algorithm
Given: Table of processes, and their Arrival time, Execution time, and priority. Here
we are considering 1 is the lowest priority.

43 | P a g e
 Process Arrival Time Execution Time Priority Service Time

P0 0 5 1 0

P1 1 3 2 11

P2 2 8 1 14

P3 3 6 3 5

Waiting time of each process is as follows −

Process Waiting Time

P0 0-0=0

P1 11 - 1 = 10

P2 14 - 2 = 12

P3 5-3=2

Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

5. Round Robin Scheduling

Round Robin(RR) scheduling algorithm is mainly designed for time-sharing

systems. This algorithm is similar to FCFS scheduling, but in Round Robin(RR)
scheduling, preemption is added which enables the system to switch between
processes.

44 | P a g e
  A fixed time is allotted to each process, called a quantum, for execution.

 Once a process is executed for the given time period that process is preempted
and another process executes for the given time period.

 Context switching is used to save states of preempted processes.

 This algorithm is simple and easy to implement and the most important is thing
is this algorithm is starvation-free as all processes get a fair share of CPU.

 It is important to note here that the length of time quantum is generally from
10 to 100 milliseconds in length.

Some important characteristics of the Round Robin(RR) Algorithm are as follows:

1. Round Robin Scheduling algorithm resides under the category of Preemptive

Algorithms.

2. This algorithm is one of the oldest, easiest, and fairest algorithm.

3. This Algorithm is a real-time algorithm because it responds to the event within

a specific time limit.

4. In this algorithm, the time slice should be the minimum that is assigned to a
specific task that needs to be processed. Though it may vary for different
operating systems.

5. This is a hybrid model and is clock-driven in nature.

6. This is a widely used scheduling method in the traditional operating system.

Important terms

1. Completion Time It is the time at which any process completes its execution.

45 | P a g e
 2. Turn Around Time This mainly indicates the time Difference between completion
time and arrival time. The Formula to calculate the same is: Turn Around Time
= Completion Time – Arrival Time
3. Waiting Time(W.T): It Indicates the time Difference between turn around
time and burst time. And is calculated as Waiting Time = Turn Around Time –
Burst Time

Let us now cover an example for the same:

In the above diagram, arrival time is not mentioned so it is taken as 0 for all
processes.

Note: If arrival time is not given for any problem statement then it is taken as 0 for
all processes; if it is given then the problem can be solved accordingly.

The value of time quantum in the above example is [Link] us now calculate the Turn around time and waiting
time for the above example :

Turn Around Time Waiting Time

Burst
Processes Turn Around Time = Waiting Time = Turn
Time
Completion Time – Around Time – Burst
Arrival Time Time

P1 21 32-0=32 32-21=11

46 | P a g e
 Turn Around Time Waiting Time
Burst
Processes Turn Around Time = Waiting Time = Turn
Time
Completion Time – Around Time – Burst
Arrival Time Time

P2 3 8-0=8 8-3=5

P3 6 21-0=21 21-6=15

P4 2 15-0=15 15-2=13
Average waiting time is calculated by adding the waiting time of all processes
and then dividing them by [Link] processes.

average waiting time = waiting time of all processes/ [Link] processes

average waiting time=11+5+15+13/4 = 44/4= 11ms

6. Shortest Remaining Time First (SRTF) Scheduling Algorithm

This Algorithm is the preemptive version of SJF scheduling. In SRTF, the

execution of the process can be stopped after certain amount of time. At the arrival of
every process, the short term scheduler schedules the process with the least
remaining burst time among the list of available processes and the running process.

Once all the processes are available in the ready queue, No preemption will be
done and the algorithm will work as SJF scheduling. The context of the process is
saved in the Process Control Block when the process is removed from the execution
and the next process is scheduled. This PCB is accessed on the next execution of this
process.

Example

In this Example, there are five jobs P1, P2, P3, P4, P5 and P6. Their arrival time and burst time are
given below in the table.

Process Arrival Burst Completion Turn Waiting Response

ID Time Time Time Around Time Time
Time

1 0 8 20 20 12 0

2 1 4 10 9 5 1

47 | P a g e
3 2 2 4 2 0 2

4 3 1 5 2 1 4

5 4 3 13 9 6 10

6 5 2 7 2 0 5

                    Avg Waiting Time = 24/6

The Gantt chart is prepared according to the arrival and burst time given in the table.

1. Since, at time 0, the only available process is P1 with CPU burst time 8. This is
the only available process in the list therefore it is scheduled.
2. The next process arrives at time unit 1. Since the algorithm we are using is
SRTF which is a preemptive one, the current execution is stopped and the
scheduler checks for the process with the least burst time.
Till now, there are two processes available in the ready queue. The OS has
executed P1 for one unit of time till now; the remaining burst time of P1 is 7
units. The burst time of Process P2 is 4 units. Hence Process P2 is scheduled on
the CPU according to the algorithm.
3. The next process P3 arrives at time unit 2. At this time, the execution of
process P3 is stopped and the process with the least remaining burst time is
searched. Since the process P3 has 2 unit of burst time hence it will be given
priority over others.
4. The Next Process P4 arrives at time unit 3. At this arrival, the scheduler will
stop the execution of P4 and check which process is having least burst time
among the available processes (P1, P2, P3 and P4). P1 and P2 are having the
remaining burst time 7 units and 3 units respectively.
48 | P a g e
 P3 and P4 are having the remaining burst time 1 unit each. Since, both are
equal hence the scheduling will be done according to their arrival time. P3
arrives earlier than P4 and therefore it will be scheduled again.
5. The Next Process P5 arrives at time unit 4. Till this time, the Process P3 has
completed its execution and it is no more in the list. The scheduler will compare
the remaining burst time of all the available processes. Since the burst time of
process P4 is 1 which is least among all hence this will be scheduled.
6. The Next Process P6 arrives at time unit 5, till this time, the Process P4 has
completed its execution. We have 4 available processes till now, that are P1 (7),
P2 (3), P5 (3) and P6 (2). The Burst time of P6 is the least among all hence P6
is scheduled. Since, now, all the processes are available hence the algorithm
will now work same as SJF. P6 will be executed till its completion and then the
process with the least remaining time will be scheduled.

Once all the processes arrive, No preemption is done and the algorithm will work as
SJF.

7. Longest Remaining Time First Scheduling Algorithm

The Longest Remaining time First(LRTF) scheduling is the preemptive version
of Longest Job First(LJF) scheduling. This scheduling algorithm is used by the
operating system in order to schedule incoming processes so that they can be
executed in a systematic way.

With this algorithm, the process having the maximum remaining time is
processed first. In this, we will check for the maximum remaining time after an
interval of time(say 1 unit) that is there another process having more Burst Time
arrived up to that time.

Let us now understand the procedure followed by the LRTF scheduling

algorithm;

Working of LRTF Scheduling

 The First step is to sort the processes according to their Arrival time in
increasing order
 The next step is to choose the process that least arrival time but having the
most Burst Time. After that process it for 1 unit. After one unit you need to
check if up to that time of execution; any other process is arrived or not
 Just repeat the above steps until the execution of all processes.

Characteristics of LRTF Scheduling

49 | P a g e
Given below are some of the characteristics of LRTF:

 It is a CPU scheduling algorithm that is used to determine the process to be

executed first among all incoming processes in a systematic way.
 This algorithm follows the preemptive approach because in this CPU is allocated
to any process only for a fixed slice of time.

 In this algorithm, processes are selected on the basis of the highest burst
time(the one with the highest burst time is processed first) and this process
runs till the fixed slice of time. After that, the selection process takes place
again.

 Due to the high value of the average waiting time, this algorithm is not optimal.

LRTF Scheduling Example

In the above example, four processes P1, P2, P3, P4 are given along with their
arrival time and burst time.

With the help of the Gantt chart let us calculate completion time, waiting time, and turn around time.

50 | P a g e
 Waiting
Turn around Time
Time
Waiting
Arrival Burst Completion Turn Around Time =
Process
Time time time Time = Turn
Completion Around
Time – Time –
Arrival Time Burst
Time

P1 0 3 11 11-0=11 11-3=8

P2 1 6 12 12-1=11 11-6=5

P3 3 2 13 13-2=11 13-2=11

P4 5 3 14 14-5=11 11-3=8
Average waiting time is calculated by adding the waiting time of all processes
and then dividing them by no. of processes.

average waiting time = waiting time of all processes/ [Link] processes

average waiting time=8+5+11+8/4 = 4ms

Advantages of LRTF

 This algorithm is easy to implement and simple

 This algorithm is starvation-free because all processes get a fair share of CPU.
 All the processes get completed by the time the longest job reaches its
completion.

Disadvantages of LRTF

 With this algorithm, the average waiting time and turnaround time are too high,
even if burst time is less for each process.
 In this process with less burst time(smaller processes) need to wait for CPU in
order to finish processes with larger burst size.
 The valuable time of CPU is consumed by context switch; which can be utilized
for the execution of processes.

Multiple Processors Scheduling

Multiple processor scheduling or multiprocessor scheduling focuses on designing

the system's scheduling function, which consists of more than one processor. Multiple
CPUs share the load (load sharing) in multiprocessor scheduling so that various
51 | P a g e
processes run simultaneously. In general, multiprocessor scheduling is complex as
compared to single processor scheduling. In the multiprocessor scheduling, there are
many processors, and they are identical, and we can run any process at any time.

The multiple CPUs in the system are in close communication, which shares a
common bus, memory, and other peripheral devices. So we can say that the system
is tightly coupled. These systems are used when we want to process a bulk amount of
data, and these systems are mainly used in satellite, weather forecasting, etc.

There are cases when the processors are identical, i.e., homogenous, in terms
of their functionality in multiple-processor scheduling. We can use any processor
available to run any process in the queue.

Multiprocessor systems may be heterogeneous (different kinds of CPUs)

or homogenous (the same CPU). There may be special scheduling constraints, such as
devices connected via a private bus to only one CPU.

There is no policy or rule which can be declared as the best scheduling solution
to a system with a single processor. Similarly, there is no best scheduling solution for
a system with multiple processors as well.

There are two approaches to multiple processor scheduling in the operating

system: Symmetric Multiprocessing and Asymmetric Multiprocessing.

1. Symmetric Multiprocessing: It is used where each processor is self-

scheduling. All processes may be in a common ready queue, or each processor
may have its private queue for ready processes. The scheduling proceeds
further by having the scheduler for each processor examine the ready queue
and select a process to execute.
2. Asymmetric Multiprocessing: It is used when all the scheduling decisions
and I/O processing are handled by a single processor called the Master Server.
The other processors execute only the user code. This is simple and reduces the

52 | P a g e
 need for data sharing, and this entire scenario is called Asymmetric
Multiprocessing.

Processor Affinity means a process has an affinity for the processor on which it is

currently running. When a process runs on a specific processor, there are certain
effects on the cache memory. The data most recently accessed by the process
populate the cache for the processor. As a result, successive memory access by the
process is often satisfied in the cache memory.

Now, suppose the process migrates to another processor. In that case, the
contents of the cache memory must be invalidated for the first processor, and the
cache for the second processor must be repopulated. Because of the high cost of
invalidating and repopulating caches, most SMP(symmetric multiprocessing) systems
try to avoid migrating processes from one processor to another and keep a process
running on the same processor. This is known as processor affinity. There are two
types of processor affinity, such as:

1. Soft Affinity: When an operating system has a policy of keeping a process

running on the same processor but not guaranteeing it will do so, this situation
is called soft affinity.
2. Hard Affinity: Hard Affinity allows a process to specify a subset of processors
on which it may run. Some Linux systems implement soft affinity and provide
system calls like sched_setaffinity() that also support hard affinity.

Load Balancing is the phenomenon that keeps the workload evenly distributed
across all processors in an SMP system. Load balancing is necessary only on systems
where each processor has its own private queue of a process that is eligible to
execute.

53 | P a g e
 Load balancing is unnecessary because it immediately extracts a runnable
process from the common run queue once a processor becomes idle. On SMP
(symmetric multiprocessing), it is important to keep the workload balanced among all
processors to utilize the benefits of having more than one processor fully. One or
more processors will sit idle while other processors have high workloads along with
lists of processors awaiting the CPU. There are two general approaches to load
balancing:

1. Push Migration: In push migration, a task routinely checks the load on each
processor. If it finds an imbalance, it evenly distributes the load on each
processor by moving the processes from overloaded to idle or less busy
processors.
2. Pull Migration:Pull Migration occurs when an idle processor pulls a waiting task
from a busy processor for its execution.

In multi-core processors, multiple processor cores are placed on the same physical
chip. Each core has a register set to maintain its architectural state and thus appears
to the operating system as a separate physical processor. SMP systems that use
multi-core processors are faster and consume less power than systems in which each
processor has its own physical chip.

Multi-core processors may complicate the scheduling problems. When the

processor accesses memory, it spends a significant amount of time waiting for the
data to become available. This situation is called a Memory stall. It occurs for various
reasons, such as cache miss, which is accessing the data that is not in the cache
memory.

In such cases, the processor can spend upto 50% of its time waiting for data to
become available from memory. To solve this problem, recent hardware designs have
implemented multithreaded processor cores in which two or more hardware threads
are assigned to each core. Therefore if one thread stalls while waiting for the
memory, the core can switch to another thread. There are two ways to multithread a
processor:
54 | P a g e
 1. Coarse-Grained Multithreading: A thread executes on a processor until a
long latency event such as a memory stall occurs in coarse-grained
multithreading. Because of the delay caused by the long latency event, the
processor must switch to another thread to begin execution. The cost of
switching between threads is high as the instruction pipeline must be
terminated before the other thread can begin execution on the processor core.
Once this new thread begins execution, it begins filling the pipeline with its
instructions.
2. Fine-Grained Multithreading: This multithreading switches between threads
at a much finer level, mainly at the boundary of an instruction cycle. The
architectural design of fine-grained systems includes logic for thread switching,
and as a result, the cost of switching between threads is small.

Symmetric Multiprocessors (SMP) is the third model. There is one copy of the
OS in memory in this model, but any central processing unit can run it. Now, when a
system call is made, the central processing unit on which the system call was made
traps the kernel and processed that system call. This model balances processes and
memory dynamically. This approach uses Symmetric Multiprocessing, where each
processor is self-scheduling.

The scheduling proceeds further by having the scheduler for each processor
examine the ready queue and select a process to execute. In this system, this is
possible that all the process may be in a common ready queue or each processor may
have its private queue for the ready process. There are mainly three sources of
contention that can be found in a multiprocessor operating system.

o Locking system: As we know that the resources are shared in the

multiprocessor system, there is a need to protect these resources for safe

55 | P a g e
 access among the multiple processors. The main purpose of the locking scheme
is to serialize access of the resources by the multiple processors.
o Shared data: When the multiple processors access the same data at the same
time, then there may be a chance of inconsistency of data, so to protect this,
we have to use some protocols or locking schemes.
o Cache coherence: It is the shared resource data that is stored in multiple local
caches. Suppose two clients have a cached copy of memory and one client
change the memory block. The other client could be left with an invalid cache
without notification of the change, so this conflict can be resolved by
maintaining a coherent view of the data.

In the multiprocessor model, there is a single data structure that keeps track of
the ready processes. In this model, one central processing unit works as a master and
another as a slave. All the processors are handled by a single processor, which is
called the master server.

The master server runs the operating system process, and the slave server runs
the user processes. The memory and input-output devices are shared among all the
processors, and all the processors are connected to a common bus. This system is
simple and reduces data sharing, so this system is called Asymmetric
multiprocessing.

In this type of multiple processor scheduling, even a single CPU system acts as

a multiple processor system. In a system with virtualization, the virtualization
presents one or more virtual CPUs to each of the virtual machines running on the
system. It then schedules the use of physical CPUs among the virtual machines.

o Most virtualized environments have one host operating system and many guest
operating systems, and the host operating system creates and manages the
virtual machines.
o Each virtual machine has a guest operating system installed, and applications
run within that guest.
o Each guest operating system may be assigned for specific use cases,
applications, or users, including time-sharing or real-time operation.

56 | P a g e
 o Any guest operating-system scheduling algorithm that assumes a certain
amount of progress in a given amount of time will be negatively impacted by
the virtualization.
o A time-sharing operating system tries to allot 100 milliseconds to each time
slice to give users a reasonable response time. A given 100 millisecond time
slice may take much more than 100 milliseconds of virtual CPU time. Depending
on how busy the system is, the time slice may take a second or more, which
results in a very poor response time for users logged into that virtual machine.
o The net effect of such scheduling layering is that individual virtualized operating
systems receive only a portion of the available CPU cycles, even though they
believe they are receiving all cycles and scheduling all of those cycles. The
time-of-day clocks in virtual machines are often incorrect because timers take
no longer to trigger than they would on dedicated CPUs.
o Virtualizations can thus undo the good scheduling algorithm efforts of the
operating systems within virtual machines.

Thread Scheduling

Every thread has a thread priority assigned to it. Threads created within the
common language runtime are initially assigned the priority of [Link].
Threads created outside the runtime retain the priority they had before they entered
the managed environment. You can get or set the priority of any thread with
the [Link] property.

Threads are scheduled for execution based on their priority. Even though
threads are executing within the runtime, all threads are assigned processor time
slices by the operating system. The details of the scheduling algorithm used to
determine the order in which threads are executed varies with each operating system.
Under some operating systems, the thread with the highest priority (of those threads
that can be executed) is always scheduled to run first. If multiple threads with the
same priority are all available, the scheduler cycles through the threads at that
priority, giving each thread a fixed time slice in which to execute. As long as a thread
with a higher priority is available to run, lower priority threads do not get to execute.
When there are no more runnable threads at a given priority, the scheduler moves to
the next lower priority and schedules the threads at that priority for execution. If a
higher priority thread becomes runnable, the lower priority thread is preempted and
the higher priority thread is allowed to execute once again. On top of all that, the
operating system can also adjust thread priorities dynamically as an application's user
interface is moved between foreground and background. Other operating systems
might choose to use a different scheduling algorithm.

57 | P a g e
 Chapter-4

Inter-process Communication
Race Conditions

Race Condition or Race Hazard is an undesirable situation of software,

electronics, or other systems. When the output of the system or program depends on
the sequence or timing of other uncontrolled events, this condition is called Race
[Link] condition occurs mainly in the logic circuits, distributed and
multithreaded software programs.

A race condition is categorized as either a critical or non-critical race condition.

The critical race conditions are those conditions that occur when the order of the
internal variable regulates the last state of the machine. On the other hand, the non-
critical race conditions are those conditions which occur when the order of internal
variables does not regulate the last state of the machine.

A race condition occurs in the software when the computer program depends on
the threads or processes of a program. In software, we cannot debug the race
condition because the final result is non-deterministic and based on the timing of
multiple threads.

Consider the following example to describe how the race condition occurs in the
process. Suppose two threads Thread 1 and Thread 2reduce the value of the global
integer variable by 2.

The following table shows the consecutive order of operations:

Thread 1 Thread 2 Integer value

10

Read the Value 10

Reduce the Value 10

Write the value by 2 8

Read the value 8

Reduce the Value by2 8

Write the value 6

In the above table, the final value is 6, as expected.

58 | P a g e
 However, if the operations of these two threads execute concurrently without
the concept of locking or synchronization, the outcome of the operations could be
wrong.

The alternative sequence of the operations is shown in the following scenario:

Thread 1 Thread 2 Integer

value

Read the Value 10

Read the value 10

Reduce the Value by 2 10

Reduce the Value by 2 10

Write the value 8

Write the value 8

In this scenario, the final value is 8 instead of 6. This happens because the
decrement operations of Thread 1 and Thread 2 are not mutually exclusive. Those
operations which cannot create interruptions while accessing some resources are
called mutually exclusive operations.

Critical Section Problem / Critical Region

The critical section is a code segment where the shared variables can be
accessed. An atomic action is required in a critical section i.e. only one process can
execute in its critical section at a time. All the other processes have to wait to
execute in their critical sections.
A diagram that demonstrates the critical section is as follows −

59 | P a g e
 In the above diagram, the entry section handles the entry into the critical
section. It acquires the resources needed for execution by the process. The exit
section handles the exit from the critical section. It releases the resources and also
informs the other processes that the critical section is free.
The critical section problem needs a solution to synchronize the different
processes. The solution to the critical section problem must satisfy the following
conditions −

 Mutual Exclusion
Mutual exclusion implies that only one process can be inside the critical section
at any time. If any other processes require the critical section, they must wait
until it is free.
 Progress
Progress means that if a process is not using the critical section, then it should
not stop any other process from accessing it. In other words, any process can
enter a critical section if it is free.
 Bounded Waiting
Bounded waiting means that each process must have a limited waiting time. Itt
should not wait endlessly to access the critical section.

and, as a result, remains in a tight loop constantly checking turn to see when it
changes to 1.
Busy waiting is the process of repeatedly testing a variable until a value arrives.
Typically, it
should be avoided because it uses much CPU time. Busy waiting is only employed
when there is

60 | P a g e
a solid anticipation that the wait will be brief. Using busy waiting, a lock is referred to
as a spin
lock. Turn is set to 1 when process 0 exits the crucial region to make room for
process 1 to enter.
With turn set to 0, let's assume that process 1 swiftly completes its critical region,
leaving both
processes in their noncritical regions. Process 0 now swiftly completes its whole loop,
leaving its
critical zone, and setting turn to 1.
 Both processes are currently operating in their noncritical zones as the turn
counter reads
1. Process 0 completes its noncritical region and abruptly returns to the top of its
loop.
Unfortunately, because it is turn 1 and process 1 is occupied with its noncritical zone,
it is
not allowed to access its critical region at this time.
 While loop, it remains stationary until process 1 sets turn to 0. To put it
another way, it is
not a good idea to switch off when one activity is significantly slower than the other.
 The above-mentioned requirement 3 is broken in this instance: A process that
is not in
process 0's vital zone is obstructing it. Returning to the spooler directory from before,
if
we now link the crucial region to reading and writing the spooler directory, process 0
would be prevented from printing more files because process 1 was engaged in
another
task.
 In fact, to implement this method, the two processes must rigidly alternate
when they
enter their essential zones, such as while spooling files. No one would be allowed to
spool two consecutively. While this approach does avoid all races, condition 3 is
broken,
making it a weak option for a solution

and, as a result, remains in a tight loop constantly checking turn to see when it
changes to 1.
Busy waiting is the process of repeatedly testing a variable until a value arrives.
Typically, it
should be avoided because it uses much CPU time. Busy waiting is only employed
when there is
a solid anticipation that the wait will be brief. Using busy waiting, a lock is referred to
as a spin
lock. Turn is set to 1 when process 0 exits the crucial region to make room for
process 1 to enter.
With turn set to 0, let's assume that process 1 swiftly completes its critical region,
leaving both
processes in their noncritical regions. Process 0 now swiftly completes its whole loop,
leaving its
critical zone, and setting turn to 1.
61 | P a g e
 Both processes are currently operating in their noncritical zones as the turn
counter reads
1. Process 0 completes its noncritical region and abruptly returns to the top of its
loop.
Unfortunately, because it is turn 1 and process 1 is occupied with its noncritical zone,
it is
not allowed to access its critical region at this time.
 While loop, it remains stationary until process 1 sets turn to 0. To put it
another way, it is
not a good idea to switch off when one activity is significantly slower than the other.
 The above-mentioned requirement 3 is broken in this instance: A process that
is not in
process 0's vital zone is obstructing it. Returning to the spooler directory from before,
if
we now link the crucial region to reading and writing the spooler directory, process 0
would be prevented from printing more files because process 1 was engaged in
another
task.
 In fact, to implement this method, the two processes must rigidly alternate
when they
enter their essential zones, such as while spooling files. No one would be allowed to
spool two consecutively. While this approach does avoid all races, condition 3 is
broken,
making it a weak option for a solution
and, as a result, remains in a tight loop constantly checking turn to see when it
changes to 1.
Busy waiting is the process of repeatedly testing a variable until a value arrives.
Typically, it
should be avoided because it uses much CPU time. Busy waiting is only employed
when there is
a solid anticipation that the wait will be brief. Using busy waiting, a lock is referred to
as a spin
lock. Turn is set to 1 when process 0 exits the crucial region to make room for
process 1 to enter.
With turn set to 0, let's assume that process 1 swiftly completes its critical region,
leaving both
processes in their noncritical regions. Process 0 now swiftly completes its whole loop,
leaving its
critical zone, and setting turn to 1.
 Both processes are currently operating in their noncritical zones as the turn
counter reads
1. Process 0 completes its noncritical region and abruptly returns to the top of its
loop.
Unfortunately, because it is turn 1 and process 1 is occupied with its noncritical zone,
it is
not allowed to access its critical region at this time.
 While loop, it remains stationary until process 1 sets turn to 0. To put it
another way, it is
not a good idea to switch off when one activity is significantly slower than the other.
62 | P a g e
 The above-mentioned requirement 3 is broken in this instance: A process that
is not in
process 0's vital zone is obstructing it. Returning to the spooler directory from before,
if
we now link the crucial region to reading and writing the spooler directory, process 0
would be prevented from printing more files because process 1 was engaged in
another
task.
 In fact, to implement this method, the two processes must rigidly alternate
when they
enter their essential zones, such as while spooling files. No one would be allowed to
spool two consecutively. While this approach does avoid all races, condition 3 is
broken,
making it a weak option for a solution
The easiest solution is to have every process turn off all interruptions as soon as it
enters its
critical region and turn them back on as soon as it leaves. No clock interrupts can
occur while
interrupts are disabled. After all, the CPU only switches between processes as a result
of clock or
other interrupts, and if interrupts are disabled, the CPU won't switch between
processes. As a
result, once interruptions are turned off, a process can update and inspect shared
memory without
worrying that another process will interfere. Given that it is dangerous to allow user
processes
the ability to disable interrupts, this strategy is generally undesirable. What if one of
them turned
them on, but never did so again? The system might be destroyed as a result. In
addition, if the
system has two or more CPUs and is a multiprocessor, disabling interrupts only
affects the CPU
that carried out the disable command
Mutual Exclusion with Busy Waiting

There are various proposals for achieving mutual exclusion, so that while one
process is busy updating shared memory in its critical region, no other process will
enter its critical region and cause trouble.

Disabling Interrupts

The simplest solution is to have each process disable all interrupts just after
entering its critical region and re-enable them just before leaving it. With interrupts
disabled, no clock interrupts can occur. The CPU is only switched from process to
process as a result of clock or other interrupts, after all, and with interrupts turned off
the CPU will not be switched to another process. Thus, once a process has disabled
interrupts, it can examine and update the shared memory without fear that any other
process will intervene.

63 | P a g e
 This approach is generally unattractive because it is unwise to give user
processes the power to turn off interrupts. Suppose that one of them did it and never
turned them on again? That could be the end of the system. Furthermore if the
system is a multiprocessor, with two or more CPUs, disabling interrupts affects only
the CPU that executed the disable instruction. The other ones will continue running
and can access the shared memory.

On the other hand, it is frequently convenient for the kernel itself to disable
interrupts for a few instructions while it is updating variables or lists. If an interrupt
occurred while the list of ready processes, for example, was in an inconsistent state,
race conditions could occur. The conclusion is: disabling interrupts is often a useful
technique within the operating system itself but is not appropriate as a general
mutual exclusion mechanism for user processes.

Lock Variables

As a second attempt, there is another option by a software solution. Consider

having a single, shared (lock) variable, initially 0. When a process wants to enter its
critical region, it first tests the lock. If the lock is 0, the process sets it to 1 and enters
the critical region. If the lock is already 1, the process just waits until it becomes 0.
Thus, a 0 means that no process is in its critical region and a 1 means that some
process is in its critical region.

Unfortunately, this idea contains exactly the same fatal flaw that we saw in the
spooler directory. Suppose that one process reads the lock and sees that it is 0.
Before it can set the lock to 1, another process is scheduled, runs, and sets the lock
to 1. When the first process runs again, it will also set the lock to 1, and two
processes will be in their critical regions at the same time.

Now we might think that we could get around this problem by first reading out
the lock value, then checking it again just before storing into it, but that really does
not help. The race now occurs if the second process modifies the lock just after the
first process has finished its second check.

Strict Alternation

A third approach to the mutual exclusion problem is shown in below Fig. This
program fragment, like nearly all the others in this book, is written in C. C was
chosen here because real operating systems are virtually always written in C (or
occasionally C++), but hardly ever in languages like Java, Modula 3, or Pascal. C is
powerful, efficient, and predictable, characteristics critical for writing operating
systems. Java, for example, is not predictable because it might run out of storage at
a critical moment and need to invoke the garbage collector at a most inopportune
time. This cannot happen in C because there is no garbage collection in C.

In below Fig, the integer variable turn, initially 0, keeps track of whose turn it is
to enter the critical region and examine or update the shared memory. Initially,
process 0 inspects turn, finds it to be 0, and enters its critical region. Process 1 also
finds it to be 0 and therefore sits in a tight loop continually testing turn to see when it
64 | P a g e
becomes 1. Continuously testing a variable until some value appears is called busy
waiting. It should usually be avoided, since it wastes CPU time. Only when there is a
reasonable expectation that the wait will be short is busy waiting used. A lock that
uses busy waiting is called a spin lock.

while (TRUE) { while (TRUE) {

while (turn != 0) /* loop */ ; while (turn != 1); /* loop */ ;

critical_region(); critical_region();

turn = 1; turn = 0;

noncritical_region(); noncritical_region();

} }

(a) (b)

Figure : A proposed solution to the critical region problem. (a) Process 0. (b) Process
1. In both cases, be sure to note the semicolons terminating the while statements.

When process 0 leaves the critical region, it sets turn to 1, to allow process 1 to

enter its critical region. Suppose that process 1 finishes its critical region quickly, so
both processes are in their noncritical regions, with turn set to 0. Now process 0
executes its whole loop quickly, exiting its critical region and setting turn to 1. At this
point turn is 1 and both processes are executing in their noncritical regions.

Suddenly, process 0 finishes its noncritical region and goes back to the top of
its loop. Unfortunately, it is not permitted to enter its critical region now,
because turn is 1 and process 1 is busy with its noncritical region. It hangs in
its while loop until process 1 sets turn to 0. Put differently, taking turns is not a good
idea when one of the processes is much slower than the other.

This situation violates condition 3 set out above: process 0 is being blocked by
a process not in its critical region. Going back to the spooler directory discussed
above, if we now associate the critical region with reading and writing the spooler
directory, process 0 would not be allowed to print another file because process 1 was
doing something else.

In fact, this solution requires that the two processes strictly alternate in
entering their critical regions, for example, in spooling files. Neither one would be
permitted to spool two in a row. While this algorithm does avoid all races, it is not
really a serious candidate as a solution because it violates condition 3.

Peterson’s Solution

By combining the idea of taking turns with the idea of lock variables and
warning variables, a Dutch mathematician, T. Dekker, was the first one to devise a
65 | P a g e
software solution to the mutual exclusion problem that does not require strict
alternation.

In 1981, G.L. Peterson discovered a much simpler way to achieve mutual

exclusion, thus rendering Dekker’s solution obsolete. This algorithm consists of two
procedures written in ANSI C, which means that function prototypes should be
supplied for all the functions defined and used.

Before using the shared variables (i.e., before entering its critical region), each
process calls enter_region with its own process number, 0 or 1, as parameter. This
call will cause it to wait, if need be, until it is safe to enter. After it has finished with
the shared variables, the process calls leave_region to indicate that it is done and to
allow the other process to enter, if it so desires.

Initially neither process is in its critical region. Now process 0

calls enter_region. It indicates its interest by setting its array element and
sets turn to 0. Since process 1 is not interested, enter_region returns immediately. If
process 1 now calls enter_region, it will hang there until interested[0] goes to FALSE,
an event that only happens when process 0 calls leave_region to exit the critical
region.

Now consider the case that both processes call enter_region almost

simultaneously. Both will store their process number in turn. Whichever store is done
last is the one that counts; the first one is overwritten and lost. Suppose that process
1 stores last, so turn is 1. When both processes come to the while statement, process
0 executes it zero times and enters its critical region. Process 1 loops and does not
enter its critical region until process 0 exits its critical region.

The TSL Instruction

There is a proposal that requires a little help from the hardware. Many
computers, especially those designed with multiple processors in mind, have an
instruction

TSL RX,LOCK

(Test and Set Lock) that works as follows. It reads the contents of the memory
word lock into register RX and then stores a nonzero value at the memory
address lock. The operations of reading the word and storing into it are guaranteed to
be indivisible—no other processor can access the memory word until the instruction is
finished. The CPU executing the TSL instruction locks the memory bus to prohibit
other CPUs from accessing memory until it is done.

To use the TSL instruction, we will use a shared variable, lock, to coordinate

access to shared memory. When lock is 0, any process may set it to 1 using
the TSL instruction and then read or write the shared memory. When it is done, the
process sets lock back to 0 using an ordinary move instruction.

66 | P a g e
 How can this instruction be used to prevent two processes from simultaneously
entering their critical regions? There a four-instruction subroutine in a fictitious (but
typical) assembly language is shown. The first instruction copies the old value
of lock to the register and then sets lock to 1. Then the old value is compared with 0.
If it is nonzero, the lock was already set, so the program just goes back to the
beginning and tests it again. Sooner or later it will become 0 (when the process
currently in its critical region is done with its critical region), and the subroutine
returns, with the lock set. Clearing the lock is simple. The program just stores a 0
in lock. No special instructions are needed.

One solution to the critical region problem is now straightforward. Before

entering its critical region, a process calls enter_region, which does busy waiting until
the lock is free; then it acquires the lock and returns. After the critical region the
process calls leave_region, which stores a 0 in lock. As with all solutions based on
critical regions, the processes must call enter_region and leave_region at the correct
times for the method to work. If a process cheats, the mutual exclusion will fail.

Sleep and Wake

(Producer Consumer problem)

Let us consider the basic model that is sleep and wake. Assume that we have
two system calls as sleep and wake. The process which calls sleep will get blocked
while the process which calls will get waked up.

There is a popular example called producer consumer problem which is the

most popular problem simulating sleep and wake mechanism.

The concept of sleep and wake is very simple. If the critical section is not empty
then the process will go and sleep. It will be waked up by the other process which is
currently executing inside the critical section so that the process can get inside the
critical section.

In producer consumer problem, let us say there are two processes, one process
writes something while the other process reads that. The process which is writing
something is called producer while the process which is reading is called consumer.

In order to read and write, both of them are usinga buffer. The code that
simulates the sleep and wake mechanism in terms of providing the solution to
producer consumer problem is shown below.

#define N 100 //maximum slots in buffer   
#define count=0 //items in the buffer   
void producer (void)   
{   
    int item;   

67 | P a g e
     while(True)  
    {  
        item = produce_item(); //producer produces an item   
        if(count == N) //if the buffer is full then the producer will sleep  
            Sleep();   
        insert_item (item); //the item is inserted into buffer  
        countcount=count+1;   
        if(count==1) //The producer will wake up the   
        //consumer if there is at least 1 item in the buffer   
        wake-up(consumer);  
    }  
}  
  
void consumer (void)  
{  
    int item;   
    while(True)  
    {  
        {     
            if(count == 0) //The consumer will sleep if the buffer is empty.   
            sleep();   
            item = remove_item();   
            countcount = count - 1;   
            if(count == N-1) //if there is at least one slot available in the buffer   
            //then the consumer will wake up producer  
            wake-up(producer);   
            consume_item(item); //the item is read by consumer.   
        }  
    }  
}  

The producer produces the item and inserts it into the buffer. The value of the
global variable count got increased at each insertion. If the buffer is filled completely
and no slot is available then the producer will sleep, otherwise it keep inserting.

68 | P a g e
 On the consumer's end, the value of count got decreased by 1 at each
consumption. If the buffer is empty at any point of time then the consumer will sleep
otherwise, it keeps consuming the items and decreasing the value of count by 1.

The consumer will be waked up by the producer if there is at least 1 item

available in the buffer which is to be consumed. The producer will be waked up by the
consumer if there is at least one slot available in the buffer so that the producer can
write that.

The problem arises in the case when the consumer got preempted just before it
was about to sleep. Now the consumer is neither sleeping nor consuming. Since the
producer is not aware of the fact that consumer is not actually sleeping therefore it
keep waking the consumer while the consumer is not responding since it is not
sleeping.

This leads to the wastage of system calls. When the consumer get scheduled
again, it will sleep because it was about to sleep when it was preempted.

The producer keep writing in the buffer and it got filled after some time. The
producer will also sleep at that time keeping in the mind that the consumer will wake
him up when there is a slot available in the buffer.

The consumer is also sleeping and not aware with the fact that the producer will
wake him up.

This is a kind of deadlock where neither producer nor consumer is active and
waiting for each other to wake them up. This is a serious problem which needs to be
addressed.

Using a flag bit to get rid of this problem

A flag bit can be used in order to get rid of this problem. The producer can set
the bit when it calls wake-up on the first time. When the consumer got scheduled, it
checks the bit.

The consumer will now get to know that the producer tried to wake him and
therefore it will not sleep and get into the ready state to consume whatever produced
by the producer.

This solution works for only one pair of producer and consumer, what if there
are n producers and n consumers. In that case, there is a need to maintain an integer
which can record how many wake-up calls have been made and how many consumers
need not sleep. This integer variable is called semaphore. We will discuss more about
semaphore later in detail.

Semaphores

In order to get rid of the problem of wasting the wake-up signals, Dijkstra
proposed an approach which involves storing all the wake-up calls. Dijkstra states
69 | P a g e
that, instead of giving the wake-up calls directly to the consumer, producer can store
the wake-up call in a variable. Any of the consumers can read it whenever it needs to
do so.

Semaphore is the variables which stores the entire wake up calls that are being
transferred from producer to consumer. It is a variable on which read, modify and
update happens automatically in kernel mode. Semaphore cannot be implemented in
the user mode because race condition may always arise when two or more processes
try to access the variable simultaneously. It always needs support from the operating
system to be implemented.

According to the demand of the situation, Semaphore can be divided into two
categories.

1. Counting Semaphore
2. Binary Semaphore or Mutex

Counting Semaphore

There are the scenarios in which more than one processes need to execute in
critical section simultaneously. However, counting semaphore can be used when we
need to have more than one process in the critical section at the same time.

The programming code of semaphore implementation is shown below which

includes the structure of semaphore and the logic using which the entry and the exit
can be performed in the critical section.

struct Semaphore  
{  
    int value; // processes that can enter in the critical section simultaneously.   
    queue type L; // L contains set of processes which get blocked   
}  
Down (Semaphore S)  
{  
    [Link] = [Link] -1; //semaphore's value will get decreased when a new   
    //process enter in the critical section   
    if ([Link]< 0)  
    {  
        put_process(PCB) in L; //if the value is negative then   
        //the process will get into the blocked state.  
        Sleep();   
    }  
70 | P a g e
     else  
        return;  
}  
up (Semaphore s)  
{  
    [Link] = [Link]+1; //semaphore value will get increased when   
    //it makes an exit from the critical section.   
    if([Link]<=0)  
    {  
        select a process from L; //if the value of semaphore is positive   
        //then wake one of the processes in the blocked queue.   
        wake-up();  
    }  
    }  
}  

In this mechanism, the entry and exit in the critical section are performed on
the basis of the value of counting semaphore. The value of counting semaphore at
any point of time indicates the maximum number of processes that can enter in the
critical section at the same time.

A process which wants to enter in the critical section first decrease the
semaphore value by 1 and then check whether it gets negative or not. If it gets
negative then the process is pushed in the list of blocked processes (i.e. q) otherwise
it gets enter in the critical section.

When a process exits from the critical section, it increases the counting
semaphore by 1 and then checks whether it is negative or zero. If it is negative then
that means that at least one process is waiting in the blocked state hence, to ensure
bounded waiting, the first process among the list of blocked processes will wake up
and gets enter in the critical section.

The processes in the blocked list will get waked in the order in which they slept.
If the value of counting semaphore is negative then it states the number of processes
in the blocked state while if it is positive then it states the number of slots available in
the critical section.

Binary Semaphore or Mutex

In counting semaphore, Mutual exclusion was not provided because we has the
set of processes which required to execute in the critical section simultaneously.
Binary Semaphore strictly provides mutual exclusion. Here, instead of having more

71 | P a g e
than 1 slots available in the critical section, we can only have at most 1 process in the
critical section. The semaphore can have only two values, 0 or 1.

Let's see the programming implementation of Binary Semaphore.

Struct Bsemaphore  
{  
    enum Value(0,1); //value is enumerated data type which can only have two 
values 0 or 1.  
    Queue type L;  
}  
/* L contains all PCBs corresponding to process Blocked while processing down 
operation unsuccessfully.   */   
Down (Bsemaphore S)   
{  
    if ([Link] == 1) // if a slot is available in the   
    //critical section then let the process enter in the queue.   
    {  
        [Link] = 0; // initialize the value to 0 so that no other process can read it 
as 
1.   
    }  
    else  
    {  
        put the process (PCB) in S.L; //if no slot is available   
        //then let the process wait in the blocked queue.   
        sleep();   
    }  
}  
Up (Bsemaphore S)   
{  
    if (S.L is empty) //an empty blocked processes list implies that no process   
    //has ever tried to get enter in the critical section.   
    {  
        [Link] =1;   

72 | P a g e
     }  
    else  
    {  
        Select a process from S.L;   
        Wakeup(); // if it is not empty then wake the first process of the blocked 
queue.   
    }   
}  

Monitors

Monitors are a programming language component that aids in the regulation of

shared data access. The Monitor is a package that contains shared data structures,
operations, and synchronization between concurrent procedure calls. Therefore, a
monitor is also known as a synchronization tool. Java, C#, Visual Basic, Ada, and
concurrent Euclid are among some of the languages that allow the use of monitors.
Processes operating outside the monitor can't access the monitor's internal variables,
but they can call the monitor's procedures.

For example, synchronization methods like the wait() and notify() constructs

are available in the Java programming language.

Syntax of monitor in OS

Monitor in os has a simple syntax similar to how we define a class, it is as

follows:

Monitor monitorName{
variables_declaration;
condition_variables;

procedure p1{ ... };

procedure p2{ ... };
...
procedure pn{ ... };

{
initializing_code;
}

Monitor in an operating system is simply a class containing

variable_declarations, condition_variables, various procedures (functions), and
an initializing_code block that is used for process synchronization.

73 | P a g e
Characteristics of Monitors in OS

A monitor in os has the following characteristics:

 We can only run one program at a time inside the monitor.

 Monitors in an operating system are defined as a group of methods and

fields that are combined with a special type of package in the os.

 A program cannot access the monitor's internal variable if it is running

outside the monitor. Although, a program can call the monitor's functions.

 Monitors were created to make synchronization problems less complicated.

 Monitors provide a high level of synchronization between processes.

Components of Monitor in an operating system

The monitor is made up of four primary parts:

1. Initialization: The code for initialization is included in the package, and

we just need it once when creating the monitors.

2. Private Data: It is a feature of the monitor in an operating system to

make the data private. It holds all of the monitor's secret data, which
includes private functions that may only be utilized within the monitor.
As a result, private fields and functions are not visible outside of the
monitor.

3. Monitor Procedure: Procedures or functions that can be invoked from

outside of the monitor are known as monitor procedures.

4. Monitor Entry Queue: Another important component of the monitor is

the Monitor Entry Queue. It contains all of the threads, which are
commonly referred to as procedures only.

Condition Variables

74 | P a g e
 There are two sorts of operations we can perform on the monitor's condition
variables:

1. Wait
2. Signal

Consider a condition variable (y) is declared in the monitor:

[Link](): The activity/process that applies the wait operation on a condition variable

will be suspended, and the suspended process is located in the condition variable's
block queue.

[Link](): If an activity/process applies the signal action on the condition variable,

then one of the blocked activity/processes in the monitor is given a chance to
execute.

Advantages of Monitor in OS

 Monitors offer the benefit of making concurrent or parallel programming easier

and less error-prone than semaphore-based solutions.

 It helps in process synchronization in the operating system.

 Monitors have built-in mutual exclusion.

 Monitors are easier to set up than semaphores.

 Monitors may be able to correct for the timing faults that semaphores cause.

Disadvantages of Monitor in OS

 Monitors must be implemented with the programming language.

 Monitor increases the compiler's workload.

 The monitor requires to understand what operating system features are

available for controlling crucial sections in the parallel procedures.

Conclusion

75 | P a g e
  Monitor in an operating system is one method for achieving process
synchronization.

 Monitors in OS offer the benefit of making concurrent or parallel programming

easier and less error-prone than semaphore-based solutions.

 The monitor is made up of four primary parts, Initialization, Private Data,

Monitor Procedure, and Monitor Entry Queue.

 wait() and signal() are two methods that we can use with the monitor's

condition variables.

Message Passing

Message Passing provides a mechanism to allow processes to communicate and

to synchronize their actions without sharing the same address space.
For example − chat programs on World Wide Web.
Now let us discuss the message passing step by step.
Step 1 − Message passing provides two operations which are as follows −
Send message
Receive message
Messages sent by a process can be either fixed or variable size.
Step 2 − For fixed size messages the system level implementation is straight
forward. It makes the task of programming more difficult.
Step 3 − The variable sized messages require a more system level implementation
but the programming task becomes simpler.
Step 4 − If process P1 and P2 want to communicate they need to send a message to
and receive a message from each other that means here a communication link exists
between them.
Step 5 − Methods for logically implementing a link and the send() and receive()
operations.
Given below is the structure of message passing technique −

76 | P a g e
Characteristics

The characteristics of Message passing model are as follows −

 Mainly the message passing is used for communication.

 It is used in distributed environments where the communicating processes

are present on remote machines which are connected with the help of a
network.

 Here no code is required because the message passing facility provides a

mechanism for communication and synchronization of actions that are
performed by the communicating processes.

 Message passing is a time consuming process because it is implemented

through kernel (system calls).

 It is useful for sharing small amounts of data so that conflicts need not
occur.

 In message passing the communication is slower when compared to

shared memory technique.

Barriers

In parallel computing, a barrier is a type of synchronization method. A barrier

for a group of threads or processes in the source code means any thread/process

77 | P a g e
must stop at this point and cannot proceed until all other threads/processes reach this
barrier.

Many collective routines and directive-based parallel languages impose implicit

barriers. For example, a parallel do loop in FORTRAN with OpenMP will not be allowed
to continue on any thread until the last iteration is completed. This is in case the
program relies on the result of the loop immediately after its completion. In message
passing, any global communication (such as reduction or scatter) may imply a
barrier.

Dynamic barriers

Classic barrier constructs define the set of participating processes/threads

statically. This is usually done either at program startup or when a barrier like the
Pthreads barrier is instantiated. This restricts the possible applications for which
barriers can be used.

To support more dynamic programming paradigms like fork/join parallelism,

the sets of participants have to be dynamic. Thus, the set of processes/threads
participating in a barrier operation needs to be able to change over time. X10*
introduced the concept of clocks for that purpose, which provide a dynamic barrier
semantic. Building on clocks, phasers have been proposed to add even more flexibility
to barrier synchronization. With phasers it is possible to express data dependencies
between the participating processes explicitly to avoid unnecessary over-
synchronization.

Processor and compiler barriers

Memory barrier is a class of instructions which cause a processor to enforce an

ordering constraint on memory operations issued before and after the barrier
instruction.

A barrier can also be a high-level programming language statement which

prevents the compiler from reordering other operations over the barrier statement
during optimization passes. Such statements can potentially generate processor
barrier instructions. Different classes of barrier exist and may apply to a specific set
of operations only.

Classical Problems of Synchronization / Classical IPC Problems

 
The classical problems of synchronization are as follows:
1. Bound-Buffer problem
78 | P a g e
 2. Sleeping barber problem
3. Dining Philosophers problem
4. Readers and writers problem

The Dining Philosophers Problem

The dining philosopher's problem is the classical problem of synchronization

which says that Five philosophers are sitting around a circular table and their job is to
think and eat alternatively. A bowl of noodles is placed at the center of the table
along with five chopsticks for each of the philosophers. To eat a philosopher needs
both their right and a left chopstick. A philosopher can only eat if both immediate left
and right chopsticks of the philosopher is available. In case if both immediate left and
right chopsticks of the philosopher are not available then the philosopher puts down
their (either left or right) chopstick and starts thinking again.

The dining philosopher demonstrates a large class of concurrency control

problems hence it's a classic synchronization problem.

Five Philosophers sitting around the table

Dining Philosophers Problem- Let's understand the Dining Philosophers Problem

with the below code, we have used fig 1 as a reference to make you understand the
problem exactly. The five Philosophers are represented as P0, P1, P2, P3, and P4 and
five chopsticks by C0, C1, C2, C3, and C4.

79 | P a g e
 Void Philosopher  
 {  
 while(1)  
  {  
   take_chopstick[i];  
   take_chopstick[ (i+1) % 5] ;  
   . .  
   . EATING THE NOODLE  
   .  
   put_chopstick[i] );  
   put_chopstick[ (i+1) % 5] ;  
   .  
   . THINKING  
  }  
}  

Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and

execute take_chopstick[i]; by doing this it holds C0 chopstick after that it
execute take_chopstick[ (i+1) % 5]; by doing this it holds C1 chopstick( since i =0,
therefore (0 + 1) % 5 = 1)

Similarly suppose now Philosopher P1 wants to eat, it will enter in Philosopher()

function, and execute take_chopstick[i]; by doing this it holds C1 chopstick after that
it execute take_chopstick[ (i+1) % 5]; by doing this it holds C2 chopstick( since i =1,
therefore (1 + 1) % 5 = 2)

80 | P a g e
 But Practically Chopstick C1 is not available as it has already been taken by
philosopher P0, hence the above code generates problems and produces race
condition.

The solution of the Dining Philosophers Problem

We use a semaphore to represent a chopstick and this truly acts as a solution of

the Dining Philosophers Problem. Wait and Signal operations will be used for the
solution of the Dining Philosophers Problem, for picking a chopstick wait operation can
be executed while for releasing a chopstick signal semaphore can be executed.

Semaphore: A semaphore is an integer variable in S, that apart from

initialization is accessed by only two standard atomic operations - wait and signal,
whose definitions are as follows:

1. wait( S )  
{  
while( S <= 0) ;  
S--;  
}  
  
2. signal( S )  
{  
S++;  
}  

From the above definitions of wait, it is clear that if the value of S <= 0 then it
will enter into an infinite loop(because of the semicolon; after while loop). Whereas
the job of the signal is to increment the value of S.

The structure of the chopstick is an array of a semaphore which is represented

as shown below -

semaphore C[5];  

Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized
to 1 as the chopsticks are on the table and not picked up by any of the philosophers.

Let us modify the above code of the Dining Philosopher Problem by using
semaphore operations wait and signal, the desired code looks like

void Philosopher  
 {  

81 | P a g e
  while(1)  
  {  
   Wait( take_chopstickC[i] );  
   Wait( take_chopstickC[(i+1) % 5] ) ;  
   . .  
   . EATING THE NOODLE  
   .  
   Signal( put_chopstickC[i] );  
   Signal( put_chopstickC[ (i+1) % 5] ) ;  
   .  
   . THINKING  
  }  
}  

In the above code, first wait operation is performed on take_chopstickC[i] and

take_chopstickC [ (i+1) % 5]. This shows philosopher i have picked up the chopsticks
from its left and right. The eating function is performed after that.

On completion of eating by philosopher i the, signal operation is performed on

take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows that the philosopher
i have eaten and put down both the left and right chopsticks. Finally, the philosopher
starts thinking again.

Let us understand how the above code is giving a solution to the dining
philosopher problem?

Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will

enter in Philosopher() function, and execute Wait( take_chopstickC[i] ); by doing this
it holds C0 chopstick and reduces semaphore C0 to 0, after that it execute 
Wait( take_chopstickC[(i+1) % 5] ); by doing this it holds C1 chopstick( since i =0,
therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0

Similarly, suppose now Philosopher P1 wants to eat, it will enter in

Philosopher() function, and execute Wait( take_chopstickC[i] ); by doing this it will
try to hold C1 chopstick but will not be able to do that, since the value of semaphore
C1 has already been set to 0 by philosopher P0, therefore it will enter into an infinite
loop because of which philosopher P1 will not be able to pick chopstick C1 whereas if
Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute 
Wait( take_chopstickC[i] ); by doing this it holds C2 chopstick and reduces
semaphore C2 to 0, after that, it executes Wait( take_chopstickC[(i+1) % 5] ); by
doing this it holds C3 chopstick( since i =2, therefore (2 + 1) % 5 = 3) and reduces
semaphore C3 to 0.

82 | P a g e
 Hence the above code is providing a solution to the dining philosopher problem,
A philosopher can only eat if both immediate left and right chopsticks of the
philosopher are available else philosopher needs to wait. Also at one go two
independent philosophers can eat simultaneously (i.e., philosopher P0 and P2, P1 and
P3 & P2 and P4 can eat simultaneously as all are the independent processes and they
are following the above constraint of dining philosopher problem)

The drawback of the above solution of the dining philosopher problem

From the above solution of the dining philosopher problem, we have proved
that no two neighboring philosophers can eat at the same point in time. The
drawback of the above solution is that this solution can lead to a deadlock condition.
This situation happens if all the philosophers pick their left chopstick at the same
time, which leads to the condition of deadlock and none of the philosophers can eat.

To avoid deadlock, some of the solutions are as follows -

o Maximum number of philosophers on the table should not be more than four, in
this case, chopstick C4 will be available for philosopher P3, so P3 will start
eating and after the finish of his eating procedure, he will put down his both the
chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1.
Now philosopher P2 which was holding chopstick C2 will also have chopstick C3
available, hence similarly, he will put down his chopstick after eating and enable
other philosophers to eat.
o A philosopher at an even position should pick the right chopstick and then the
left chopstick while a philosopher at an odd position should pick the left
chopstick and then the right chopstick.
o Only in case if both the chopsticks ( left and right ) are available at the same
time, only then a philosopher should be allowed to pick their chopsticks
o All the four starting philosophers ( P0, P1, P2, and P3) should pick the left
chopstick and then the right chopstick, whereas the last philosopher P4 should
pick the right chopstick and then the left chopstick. This will force P4 to hold his
right chopstick first since the right chopstick of P4 is C0, which is already held
by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which
P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence
philosopher P3 has both left C3 and right C4 chopstick available, therefore it will
start eating and will put down its both chopsticks once finishes and let others
eat which removes the problem of deadlock.

83 | P a g e
 The design of the problem was to illustrate the challenges of avoiding deadlock,
a deadlock state of a system is a state in which no progress of system is possible.
Consider a proposal where each philosopher is instructed to behave as follows:

o The philosopher is instructed to think till the left fork is available, when it is
available, hold it.
o The philosopher is instructed to think till the right fork is available, when it is
available, hold it.
o The philosopher is instructed to eat when both forks are available.
o then, put the right fork down first
o then, put the left fork down next
o repeat from the beginning.

Readers-Writers Problem

The readers-writers problem relates to an object such as a file that is shared

between multiple processes. Some of these processes are readers i.e. they only want
to read the data from the object and some of the processes are writers i.e. they want
to write into the object.
The readers-writers problem is used to manage synchronization so that there
are no problems with the object data. For example - If two readers access the object
at the same time there is no problem. However if two writers or a reader and writer
access the object at the same time, there may be problems.
To solve this situation, a writer should get exclusive access to an object i.e.
when a writer is accessing the object, no reader or writer may access it. However,
multiple readers can access the object at the same time.
This can be implemented using semaphores. The codes for the reader and
writer process in the reader-writer problem are given as follows −

Reader Process

The code that defines the reader process is given below –

wait (mutex);
rc ++;
if (rc == 1)
wait (wrt);
signal(mutex);
.
. READ THE OBJECT

84 | P a g e
.
wait(mutex);
rc --;
if (rc == 0)
signal (wrt);
signal(mutex);
In the above code, mutex and wrt are semaphores that are initialized to 1.
Also, rc is a variable that is initialized to 0. The mutex semaphore ensures mutual
exclusion and wrt handles the writing mechanism and is common to the reader and
writer process code.
The variable rc denotes the number of readers accessing the object. As soon as
rc becomes 1, wait operation is used on wrt. This means that a writer cannot access
the object anymore. After the read operation is done, rc is decremented. When re
becomes 0, signal operation is used on wrt. So a writer can access the object now.

Writer Process

The code that defines the writer process is given below:

wait(wrt);
.
. WRITE INTO THE OBJECT
.
signal(wrt);

If a writer wants to access the object, wait operation is performed on wrt. After
that no other writer can access the object. When a writer is done writing into the
object, signal operation is performed on wrt.

85 | P a g e