Process Management

Submitted By
Krishna Dev Thapa Magar
Introduction of Process
➢ A process can be thought of as program in execution.
➢ A process will need certain resources such as CPU time, memory, files and I/O devices to
accomplish its task.
➢ A process is the unit of work in modern time sharing system.
➢ System consists of collection of processes, OS processes to execute OS code and user processes
to execute user code.
➢ The OS is responsible for the following activities in connection with process management:
❑ The creation and deletion of both user and system processes.
❑ Scheduling of the processes
❑ Communication and deadlock handling for the processes
Program and process (Difference/imp)
➢ A process is basically the program in execution and is more than program code which is
sometimes known as text section.
➢ When we execute the program, it becomes a process which perform all task mentioned in the
program.
➢ So, process is just a instance of executing program including current value of program
counter(PC), register and variables.
➢ When a program is loaded into the memory and it becomes a process, it can be divided into 4
sections; stack, heap, text and data. The structure of process in the memory is shown in figure
below:
➢ The process stack contains temporary data such as functions parameters, local variables and written
address.
➢ Heap is dynamically allocated memory to a process during its run time.
➢ Data section contains the global and static variable .
➢ Text section contains program code.

➢ Program by itself is not a process.

➢ It is passive entity containing the collection of instruction stored in a disk where as process is the active
entity with program counter specifies the next instruction to be executed and set of associated
resources.
➢ Two process may be associated with same program. For instance several user may be running different
copies of mail program or same user may invokes many copies of browser program.
➢ Each of these are separate process although text section equivalent. The data, heap and stack section is
vary.

Following analogy (comparison) may help to make the difference clearer.

Scenario 1:
Computer Scientist is baking a birthday cake for his daughter.
❖ Computer scientist CPU
❖ Birthday cake recipe Program
❖ Ingredient Data
❖ Activity Process

❑ Reading the recipe

❑ Fetching the ingredient
❑ Baking the cake
Scenario 2:
Scientist’s son comes running in crying, saying that he has been stung by bee.
❖ Scientist records where he was in recipe (state of current process is saved)
❖ Read first aid book and material (another process fetched)
❖ Follow the first aid action (processor switch for new process)
❖ One completion of first aid, baking start again from where it was left.

Hence, from the above analogy process is activity of some kind which has program, input,
output and state. A single processor may be shared among several process with some
scheduling algorithm.

The process model

➢ Over years, OS designers evolve to make model that makes concurrency ( the ability of different
parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order,
without affecting the final outcome.)
➢ In this model, all the run able software on the computer including OS is organized into number of
sequential processes.
➢ A process is just an instance(order) of executing program counter, register and variables.
➢ Conceptually, each process has its own virtual CPU but in reality the real CPU switches back and
forth from process to process.
➢ To understand how the CPU switches from process to process, consider the four processes with
its own flow of control (i.e. its own logical program counter) and each one running independently
of the other ones.
➢ There is only one PC so when each process run its logical PC is loaded into real PC.
➢ When it is finished its turn in CPU, the physical program counter is saved in the processes, logical
program counter in memory.
➢ This same procedure is repeated for other process.
➢ In this way over along enough time interval, all the processes have made progress but at any
given time only one process is actually running.
➢ The overall concept is shown in the figure below:
Process state
➢ As a process executes, it changes state. The state of process is defined by current activity of that process.
➢ Each process may be in one of the following states:
❑ New: The process is being created.
❑ Running: Process is being executed. Only one process at a time. (assuming a single process or machine)
❑ Waiting: The process is waiting for some event to occur such as I/O completion or reception of a signal.
❑ Ready: The process is waiting to be assigned to the CPU. The list of process ordered based on priority.
❑ Terminated: The process has finished execution.

The state diagram corresponding to these state is presented in figure below:

 ✓ When job is admitted to the system corresponding process is created at new state and inserted at the
back of ready list.
✓ When CPU becomes available, the process is said to make a state transition from ready to running.
✓ To prevent any one process from monopolizing(controlling) the CPU, OS specify a time period for the
process. When the quantum(considerable) expire or interrupt to CPU makes state transition from
running to ready.
✓ When process requires an I/O operation before quantum expire or interrupt, the process voluntarily
requisites(thing that is necessary to achieve) the CPU and changed to the wait state i.e. running = wait.
✓ When I/O operation completes. The process makes the transition from wait state to ready state i.e.
wait=ready.
✓ When process finished execution it will terminated.

Note: Some book also define process state by defining 3-state.

Process state(imp)
➢ A process may be in one of three states. The following figure shows the state diagram showing the three
states.
➢ A process may be in
❑ Process blocks for input
❑ Scheduler picks another process
❑ Scheduler picks this process
❑ Input becomes available
➢ Running
❑ Running process is the process that is actually using the CPU at that time. Only one process can be
in running state at any one time(assuming a single processor machine).
➢ Ready
❑ A process that is ready is runnable but cannot get access to the CPU due to other process using it.
Any number of processes can be in ready state at the same time.
➢ Blocked
❑ A blocked process is unable to run until some external event has taken place. For example, it may
be waiting for data to be retrieved from a disk.

✓ The running process can either move to blocked state and ready state. Running process is moved to
blocked state when operating system discovers that process cannot continue right now i.e. when it need
to wait for an external event such as input from keyboard.
✓ Running process go to the ready state when scheduler allows other process to use the CPU.
✓ A ready process only move to a running state when scheduler decide to provide CPU to that process
✓ Blocked process can only move to a ready state when external event for which a process is waiting happens.

Implementation of process
➢ To implement the process model, the OS maintains a table called process table with one entry per process.
➢ Some author call these entries process control block (PCB).
➢ This entry contains information about process state including its program counter, memory allocation, status
of open files, its accounting and scheduling information and everything else about the process that must be
same when the process is switched from running to ready or blocked state so that it can be restarted later.

Process control block (PCB)

➢ The process must be saved when the process is switched from one state to another so that it can be restarted
later.
➢ The PCB is a data structure containing certain important information about process also called task control
block or process descriptor.
➢ Each process is representing in the OS by process control block.
➢ Different system will hold different information in the PCB. Thus, PCB is the data structure used to hold all the
information that a process need in order to restart from where it was left off when it moves from ready state
to running state.
➢ It contains many pieces of information associated with specific process including:
❑ Process state: The state may be new, ready, running, waiting and so on.
❑ Program counter: The program counter indicates the address of next instruction to be executed for this
process.
❑ CPU register: The register may vary in number and type depending on the computer architecture. Along
with program counter, state information of register must be saved when an interrupt occur to allow
the process to be continued correctly after ward.
❑ CPU scheduling information: This information includes a process priority, pointer to scheduling queues
and other scheduling parameter.
❑ Memory management information: This information may include information such as value of base and
limit registers, page table or segment table etc.
❑ Accounting information: This information may include the amount of CPU time taken by process, job or
process number, time at which process start etc.
❑ I/O status information: This information includes the list of I/O devices allocated to a process, a list of
open file etc.
❑ A PCB is shown in figure below:
❑ Following program shows how CPU switches from process to process.

Fig: Diagram showing CPU switches from process to state

Operation on process
➢ The process in most system can execute concurrently and they can be created and deleted dynamically.
➢ Thus, OS must provide the mechanism for process creation and termination.

➢ Process creation:
❑ There are four principle events that cause process to be created.
❖ System initialization
❖ Execution of process creation system call by running process
❖ User request to create a new process
❖ Initiation of batch job

❑ When an OS is booted, typically several processes are created.

❑ In addition to the process created at boot time, new processes can be created afterward as well.
❑ Often a running process will issue system calls to create one or more new processes to help it do its job.

❑ In interactive system, user can start a program by typing a command or clicking an icon.
❑ Taking either of these action start a new process and run the selected program in it.
❑ The last situation in which process are created applies only to batch system.
❑ When the OS decide that it has the resources to run another job in a batch it create a new process and
run the next job from input queue in it.

❑ The process may create several new process via. a create system call during the course of execution.
❑ The creating process is called parent process and new process are called children of that process.
❑ Each of these new process in turn may create other process, forming the tree of process or hierarchy of
the processes.
➢ Process termination
❑ After the process has been created, it starts running and does whatever its job is.
❑ Sooner or later the new process will terminate usually due to one of the following conditions:
❖ Normal exit
❖ Error exit
❖ Fatal exit
❖ Killed by other process
❑ The first reason for termination of the process is because they have done their work.
❑ The second reason for termination is that process discovers a fatal error.
❑ Third reason for termination is an error caused by the process due to the program bug. Eg: Referencing
non-existing memory, executing an illegal instruction etc.
❑ The fourth reason, the process might terminate is that process execute system call telling the OS to kill
some other process.
Threads
➢ Threads like process are mechanism to allow the program to do more than one thing at a time.
➢ Conceptually, a thread also called light weighted process exist within the process, is a basic unit of CPU
utilization.
➢ It consists of program counter, register set and stack to keep the track of which instruction to execute next,
to hold the current working variable and execution history respectively.
➢ The thread within the same process shares code section, data section and other OS resources such as open
file etc.

Multi-threading
➢ The term multi-threading is used to describe the situation of allowing multiple threads in the same process.
➢ All the threads in the same process shares same address process, global variables, set of open files etc.
➢ If a process has multiple threads of control it can perform more than one task at a time.
➢ The following figure illustrates the difference between single threaded and multi-threaded process.

Fig: Single threaded process Fig: Multi-threaded process

➢ When multi-threaded process is run on a single CPU system, the thread takes turn for running. The CPU
switches rapidly back and forth among the thread providing the illusion that thread running parallel.
➢ Many software package that run on modern desktop PC’s are multithreaded.
➢ An application typically is implemented as a separate process with several thread of control.
➢ For instance, the web browser might have one thread display image or text while other thread retrieves data
from the network.
➢ Most OS kernel are now multithreaded and each thread performs the specific task such as managing the
devices, interrupt handling etc.

➢ Different thread in the process are not independent as different process.

➢ All threads share same address space, global variables, same set of open files, child process and so on.
➢ The following table summarizes list of item per processes and per threads.

Per process items Per thread items

Address space Program counter

Global variable Register

Open files Stack

Child process State

Accounting information

➢ Fig: first column list some items shared by all threads in process
➢ The second column list some item provided to each thread
Benefits of multithreading
➢ Responsiveness
➢ Resource sharing
➢ Economy
➢ Scalability

The benefits of multithreading programming are:

➢ Responsiveness
❑ Multithreading and interactive application may allow a program to continue even if part of it is blocked.
❑ For instance, a multimedia threaded web browser could allow user interaction in one thread while an
image was being loaded in another thread.
➢ Resource sharing
❑ Threads share the memory and resources of the process to which they belong by default.
❑ The benefit of sharing code and data is that it allows an application to have several different thread of
activity within the same address space.
➢ Economy
❑ Threads share the resources of the process to which they belong. So, it is more economical to create
and context switch of the thread.
➢ Scalability
❑ The benefit of multithreading can be greatly increased in multiprocessor architecture, where thread
may be running in parallel on different processor.
❑ The single threaded process can only run on one processor regardless of how many processor are
available. Thus, multithreading on multiple CPU system increase parallelism.
Implementing threads
There are 2 main ways to implement a thread package:
➢ Implementing threads in user space
➢ Implementing threads in kernel space

➢ Implementing threads in user space

❑ The first method of implementing the thread is to put the thread package entirely in user space and
kernel knows nothing about them.
❑ With this approach threads are implemented by user level thread library.
❑ The implementation of thread in user space is illustrated by following figure:

fig: implementing thread in user space

➢ In this approach of thread implementation, the thread run on the top of run time system which is the
collection of procedure that manage threads.
➢ When the threads are implemented in user space, each process needs its own private thread table to keep
track of the thread in that process.
➢ A thread table contains thread program counter, thread stack pointer, thread register, thread state etc.

➢ Advantages:
❑ User level thread package can be implemented on an operating system that does not support
thread.
❑ Thread switching is faster because it does not require trapping to the kernel.
❑ They allow each process to have its own customized scheduling algorithm.

➢ Disadvantages:
❑ Allowing a thread to use blocking system call cause the entire process blocked.
❑ If a thread causes a page fault, the kernel not even knowing about the existence of threads,
naturally blocks the entire process until the disk I/O is complete even though other thread might be
run able.
❑ Within a process there are no clock interrupt, making it impossible to schedule the thread in the
fashion that takes turn.
❑ Lack of co-ordination between kernel and threads.
➢ Implementing threads kernel
❑ The second approach of implementing thread is to having the kernel know about thread and manage it,
no run time system is needed.
❑ The following figure illustrates the implementation of thread in kernel.

fig: implementing thread in kernel

❑ In this approach, there is no thread table in each process.

❑ Instead, the kernel has a thread table that keeps track of all threads in the system.
❑ When thread want to create a new thread or destroying an existing thread, it makes kernel call which
then does creation or destruction by updating the thread table.
❑ In this approach, the management of the thread is done by kernel not by user level thread library.
➢ Advantages:
❑ Blocking system call are not problem.
❑ If one thread in the process cause a page fault, kernel can run other runable thread within the
process while waiting for the required page to be brought into memory from the disk.
❑ Well co-ordination between kernel and threads.
❑ Specially good for application that frequently blocks.
➢ Disadvantages:
❑ Slower to create and manage thread because of the need for system call.
❑ Over head in the kernel since, kernel must manage and schedule thread as well as process.
User level threads VS kernel level threads
User level thread
❑ Thread management is done by user level thread library.
❑ Library provides the support for thread creation, scheduling and management of thread with no
support from the kernel.
❑ Fast to create and manage because does not require to trap the kernel.
❑ User level thread can run on any operating system.
❑ If kernel is single threaded, blocking system call will cause entire process to block.
Kernel level threads
❑ Thread management is done by kernel and there is no thread management code in application area.
❑ The kernel maintains context information for process as a whole and for individual thread within the
process.
❑ Kernel provide support for thread creation, scheduling and management of the thread.
❑ Kernel level threads are general slower to create and manage because they require trap in kernel/
❑ In case of kernel level thread, if one thread in the process is blocked, the kernel can schedule
another thread of the same process.
❖ User level thread have extremely low overhead, and can achieve high performance in computation.
On the other hand kernel level will guarantee multiprocessor access but the computing performance
is lower than user level due to load on the system. The synchronization and sharing resources
among threads are still less expensive than multi-process model, more expensive than user level
thread. So, user-level is better than kernel level thread.
Multithreading model (Three model of multithread) Imp
➢ Thread may be provided either at user level for user or at kernel level for kernel thread.
➢ User thread are managed without kernel support whereas kernel thread are supported and
managed directly by the operating system.
➢ Relation must exist between user thread and kernel threads.
➢ There are 3 common way of establishing such a relation called multithreading model.
❑ Many to one model
✓ The many to one model maps many user level threads to one kernel level thread.
✓ Because only one thread can access the kernel at a time, multiple thread are unable to
run in parallel on multiprocessor.
✓ If thread makes the blocking system call entire process is blocked.
❑ One to one model
✓ The one to one model maps each user thread to a kernel thread.
✓ It provides more concurrency than many to one model by allowing another thread when
thread makes blocking system call.
✓ It also allows multiple threads to run in parallel on multiprocessors.
✓ The only drawback of this model is that creating a user thread requires creating the
corresponding kernel thread.

❑ Many to many model

✓ The many to many model multiplex many user level threads to smaller or equal number of
kernel threads.
✓ In this model, developer can create as many user threads as necessary and the
corresponding kernel thread can run in parallel on a multiprocessor machine.
✓ In this model, when thread performs a blocking system call, the kernel can schedule
another thread for execution.
Thread usage (Why would anyone want to have thread within process?)
➢ There are several reasons for having threads within the process.
❑ The main reason for having threads is that in many application multiple activities are going at
once. Some of these may block from time to time. By decomposing such as application into
multiple sequential threads, the programming model becomes simpler.
❑ Since thread do not have their own address space, it is easier to create and destroy than
process.
❑ Thread switching has less overhead than process switching because thread have few
information attached to them.
❑ Finally, thread are useful on system with multiple CPU, where real parallelism is possible.

Assignments:
➢ Differentiate between process and thread.
➢ Why thread is necessary? In which circumstances user level thread is better than kernel level thread?
➢ Describe how multithreading improves performance over single threaded solution.
➢ Does window have the concept of process hierarchy? Explain.
➢ Differentiate between program and process.
Process Scheduling (Imp)
➢ The process scheduling is the activity of the process manager that handles the removal of running
process from the CPU and selection of another process on the basis of particular strategy.
➢ Process scheduling refers to which process is given control of the CPU and how long.

Scheduling queues
➢ The operating system maintains the following important process scheduling queue:
❑ Job queue
✓ This queue keeps all processes in the system.
❑ Ready queue
✓ This queue keeps a set of all processes residing in the main memory and are ready and
waiting to execute.
✓ A new process is initially put in the ready queue. It waits there until it is selected for
execution or dispatched.
❑ Device queue
✓ The list of processes waiting for particular I/O device is called a device queue.
✓ Each device has it’s own device queue.

Scheduler
➢ When a computer is multi-programmed, it frequently has multiple processes competing for the CPU
at the same time. This situation occurs whenever two or more of them are simultaneously in ready
state.
➢ If only one CPU is available the choice has to be made which process to run next. The part of
operating system that makes the choice is called the scheduler and algorithm it uses it called
scheduling algorithm.
Types of scheduler
➢ Long term scheduler
➢ Short term scheduler
➢ Medium scheduler

➢ Long term scheduler

❑ It is also called job scheduler.
❑ It decides which job or process are to be admitted to ready queue. In other word, it selects a
process from pool of processes and loads them into memory for execution.
❑ Thus it controls the number of processes in the memory i.e. degree of multiprogramming.
❑ It is important that the long term scheduler select good process mix of I/O bound and CPU
bound process.
❑ On some system, the long term scheduler may be absent.

➢ Short term scheduler

❑ It is also called CPU scheduler.
❑ It selects a process from ready queue and allocate the CPU to them.
❑ It makes a decision of which process to execute next.
❑ It’s main objective is to increase system performance in accordance with the chosen set of
criteria.

➢ Medium scheduler
❑ The key idea behind a medium-term scheduler is that some times it can be advantageous to
remove the process from memory and thus reduce the multiprogramming.
❑ Later the process can be reintroduce into memory, and it’s execution can be continued where
it left off. This scheme is called swapping.
❑ The process is swapped out and is later swapped in by the medium term scheduler.
Context switch
➢ Switching the CPU to another process requires performing a state save of the current process and
state restore of different process. This task is known as context switch.
➢ When context switch occurs, the kernel saves the context of the old process in it’s PCB and loads
the saved context of new process schedule to run.
➢ Context switch time is pure overhead, because the system does no useful work, while switching. It’s
speed varies from machine to machine, depending on the memory speed, the number of register
and the existence of special instruction etc.

Compute bound (CPU bound) VS I/O bound process (imp)

➢ The process execution consists of cycle of CPU execution and I/O wait called CPU-I/O burst cycle.
➢ Process execution begins with CPU burst that is followed by an I/O burst which is followed by
another CPU burst then another I/O burst and so on.
➢ The final CPU burst end with a system request to terminate execution.

➢ Some process spend most of their time in computing such processes are called compute bound or
CPU bound process. Compute bound process typically have long CPU burst and thus infrequent I/O
waits.
➢ An I/O bound process is one that spend more of it’s time doing I/O than it spend doing computation.
I/O bound processes have short CPU bursts and thus frequent I/O wait.
➢ In above figure(a) represents compute bound process and figure(b) represents I/O bound process.
When to schedule?
A key issue related to scheduling is when to make scheduling decisions. There are variety of situations in
which scheduling is needed. Some of these situation are:
➢ When a new process is created.
➢ When a process terminates (Running to terminate)
➢ When process blocks in I/O or for some other reason (running to wait)
➢ When an I/O interrupt occurs (waiting to ready)
➢ When quantum expire (running to ready)
Non-preemptive Vs preemptive scheduling

Non-preemptive
➢ Under non-preemptive scheduling, once a CPU has been allocated to a process, the process keeps
the CPU until it release the CP|U either by terminating or by switching to the waiting state.
➢ In other word, A non-preemption scheduling algorithm picks a process to run and then just lets it run
until it blocks or until it voluntarily release the CPU.
➢ In non-preemption scheduling short job are made to wait by longer job i.e. no priority.
➢ Useful in real time and batch system. Example: FCFS
➢ In non-preemption scheduling process cannot be interrupted during it’s execution.

Preemptive
➢ In contrast to non-preemptive scheduling, a preemptive scheduling algorithm picks a process and let
it run for maximum of some time. If it still running at the end of time interval, it is suspended and the
scheduler picks another process to run if one is available.
➢ During preemption scheduling requires having a clock interrupt. If no clock is available non-
preemptive scheduling is only option.
➢ Preemptive scheduling is useful in a system in which high priority process requires rapid attention.
➢ Useful in time sharing system for guarantying acceptable response time. Eg: Round robin scheduling
➢ In preemptive scheduling process can be interrupted during it’s execution.
Scheduling criteria
Different scheduling algorithms have different properties and the choice of particular algorithm may favor
one class of processes over another. Many criteria have been suggested for comparing scheduling
algorithms. The criteria include the following:

➢ CPU utilization
Keep the CPU as busy as possible
➢ Throughput
Number of processes that are complete per time unit
➢ Turn around time
The interval from the time of submission of process to time of completion.
➢ Waiting time
Amount of time that a process spend waiting in the ready queue. Sum of the period waiting in the
ready queue.
➢ Response time
Time from the submission of a request until the first response is produced. This response time is the
time it takes to start responding, not the time it takes to output the response.

It is desirable to maximize CPU utilization and throughput and to minimize turn around time, waiting time
and response time.
Categories of scheduling algorithm
In different environment different scheduling algorithm are needed. This situation arises because
different application areas have different goals. The scheduler optimized for one may not be optimal
for another area. Three environment worth distinguishing are:

Batch
In batch systems, there are no users impatiently waiting at terminal for a quick response. Consequently,
non-preemptive algorithms, or preemptive algorithms with long time periods for each process are
often acceptable. This approach reduces process switches and thus improves performance.
 Interactive
In an environment with interactive user, preemption is essential to keep one process from hogging the CPU
and denying service to others. Preemption is needed to prevent this behaviour.

Real time
In a real time system normally preemption is not needed because the processes know that they may not
run for long period of time and usually do their work and block quickly.

Scheduling criteria
Different scheduling to design a scheduling algorithm, it is necessary to have some idea of what the good
algorithm should do. Some goals depends on the environment (batch, interactive or real time) but there
are also some that are desirable in all cases.
➢ All system
Fairness: Giving each process a fair share of CPU
Policy enforcement: seeing that stated policy is carried out.
Balance: keeping all part of the system busy
➢ Batch system
Throughput: Maximize job per hour
Turnaround time: Minimize time between submission and termination
CPU utilization: keep the CPU busy all the time
➢ Interactive systems
Response time: respond to request quickly
Proportionally: meet user expectation
➢ Real time systems
Meeting deadline: avoid losing data
Predictability: avoid quality degradation in multimedia systems
Scheduling algorithms
➢ Process scheduling deals with problem of deciding which of the processes in the ready queue is to be
allocated the CPU.
➢ Algorithm used by the scheduler to select a process from a ready queue to run next is called scheduling
algorithm.
➢ There are many different process scheduling algorithm.

1. First come first served (FCFS) scheduling

➢ With this scheme, processes are scheduled in the order they arrive i.e. the process that request a CPU
first is allocated the CPU first.
➢ FCFS scheduling is non-preemptive i.e. once the CPU has been allocated to a process it runs to
completion.
➢ The implementation of FCFS policy is easily managed with a FIFO queue. When the process becomes
ready it is added to the tail of the queue and when CPU becomes free, the process at the head of
queue is removed, moved to a running state and allowed to use the CPU until it is completed.

➢ Problems of FCFS
❑ Average waiting time under FCFS policy is often quite long.
❑ No guarantee of good response time
❑ Not suitable for time sharing and interactive system, where each process get share of CPU at
regular interval.
❑ There is a convery effect as other process wait for the one big process to get of the CPU. This
effect results in lower CPU and device utilization.
➢ Advantage of FCFS
❑ It is easy to understand and equally easy to program.
❑ It is also fair, in the sense that allocating scarce resource to a people who are willing to stand on
line first is fair.
2. Shortest Job first (SJF) scheduling
➢ It is also non-preemption algorithm that assumes run time are known in advance.
➢ It selects a process with shortest burst time if CPU burst of two processes are same. FCFS scheduling is
used to break the tie.
➢ In this algorithm, the scheduling decision policies are based upon the CPU burst time.
➢ The SJF scheduling algorithm is provably optimal in that it gives the minimum average waiting time for
a given set of processes.
➢ Advantages
❑ Reduces the average waiting time over FCFS.
❑ Favour short jobs at the cost of long job.

➢ Problems
❑ We do not know the burst time of a process before it start.
❑ Although SJF is optimal it is difficult to implement.
❑ Not applicable in time sharing system.
3. Shortest remaining time next (SRTF)Scheduling
➢ It is the preemption version of shortest job first algorithm.
➢ With this algorithm, the scheduler always chooses the process whose remaining runtime is shortest.
➢ In this algorithm runtime of the process is known in advance.
➢ In this scheduling, when a new job arrives, the total time is compared to the current process’s
remaining time. If new job needs less time to finish than the current process, the current process is
suspended and new process is started.
➢ Advantages
❑ Low average waiting time than SJF.
❑ Useful in the time sharing system.

➢ Problems
❑ Very high overhead than SJF.
❑ Requires additional computation
❑ Favours short jobs, long job can be victims of starvation.
4. Round Robin (RR) Scheduling
➢ It is one of the oldest, simplest and most widely used scheduling algorithm.
➢ It is similar to FCFS scheduling, but preemption is added to enable the system to switch between the
processes.
➢ In this scheduling, each process is assigned a time interval called it’s quantum, during which it is
allowed to run. If the process is still running at the end of quantum, the running process is preempted
and new process is allowed to run. The preempted process is placed at the back of ready or run able
list. If the process is blocked or finished before the quantum has elapsed, the CPU switching is done.
➢ Round Robin is easy to implement. All the scheduler needs to do is maintain a list of runnable process.
When the process uses up its quantum it is put on the end of the list as in figure below:

➢ Advantages
❑ Round Robin is effective in time sharing system.
❑ Fair treatment of all processes
❑ Good response time for short processes.
❑ Low average waiting time when process length vary widely.

➢ Problems
❑ Performance depends on quantum size so care must be taken in choosing a quantum value.
❑ Processing overhead is there in handling clock interrupt.
❑ Throughput is low of time quantum is small.
Performance of RR scheduling
➢ The interesting issue with round robin is the length of the quantum.
➢ Switching from one process to another requires a certain amount of time.
➢ Setting the quantum too short causes too many processes switches and lower the CPU efficiency, but
setting it too long may cause poor response to short interactive requests.
➢ Large value of quantum may cause Round Robin behaves like FCFS policy.
➢ A quantum around 20-50 millisecond is reasonable for many general processes. The key idea for
choosing the optimal quantum size is that 80% of the CPU burst should be shorter than quantum.
5. Priority Scheduling
➢ In priority scheduling, a priority is associated with each process and the CPU is allocated to the process
with the highest priority.
➢ Equal priority process are scheduled in FCFS order.
➢ Priorities are generally indicated by some fixed range of number however there is no general
agreement on whether 0 is the highest or lowest priority. Some system use low number to represent
low priority and other use low number for higher priority.
➢ Priority scheduling can be either preemption or not preemption.
➢ In preemption priority scheduling, when a process arrives at the ready queue it’s priority is compared
with the priority of the currently running process and preempt the CPU if the priority of the newly
arrived process is higher than the priority of currently running process.
➢ A non-preemption priority scheduling does not preempt the concurrently running process until the
process does not complete or block i.e. no preemption is allowed in non-preemptive priority
scheduling.
Why priority scheduling?
➢ On a PC, there may be multiple processes some of them more important than others.
➢ For example, a process sending electronic mail in background should be assigned a lower priority
than a process displaying a video film on the screen in real time.
➢ So at that time there is a need of priority scheduling to execute the highest priority process first.
Problem in priority scheduling
➢ A major problem with priority scheduling is that some process may never run.
➢ There may always be higher priority job that get assigned the CPU. This is known as indefinite
blocking or starvation.
➢ In heavily loaded computer system, a steady steam of higher priority processes can prevent low
priority process from ever getting the CPU.
➢ On solution to the problem of indefinite blocking or starvation is, scheduler may decrease the
priority of currently running process at each clock tick.
➢ If the action cause its priority to drop below that of the next highest process, a process switch
occurs.
➢ Alternatively, each process may be assigned a maximum time quantum that is allowed to run.
➢ When this quantum is used up, the next highest priority process is given a chance to run.

Assigning a priority
➢ Priorities can be assigned dynamically (internally) or statically (externally) to the process.
➢ Priorities can be assigned dynamically by the system to achieve certain system goal.
➢ For example some processes are highly I/O bound and spend must of their time waiting for I/O to complete.
➢ Whenever such a process want CPU, it should be given the CPU immediately, to let it start it’s next I/O request, which
can then proceed in parallel with another process actually computing.
➢ Internally defined priorities use some measurable quantities to compute the priority of the process.
➢ For example, time limit, memory requirement, number of open files etc. have been used in computing priorities.
➢ External or statically priorities are set by criteria outside the operating system, such as importance of the process, the
type and amount of fund being paid for computer use and often political factor.
➢ For example on the military computer, processes started by generals might begin at priority 100, process started by
cornels at 90 and so on.
Multilevel queue scheduling

➢ A multilevel queue scheduling algorithm partitions the ready queue into several separate queues to
later for different process type.
➢ The process are permanently assigned to one queue, generally based on some property of the process.
➢ Each queue has its own scheduling algorithm. For example separate queue might be used for
interactive and batch processes and interactive process are scheduled by RR while batch processes are
scheduled by FCFS algorithms.
➢ The scheduler has to decide which queue to run. Either higher priority queue can be processed until
they are empty before the lower priority queue are executed or each queue can be given certain
amount CPU, which it can then schedule among its various processes.
Example

➢ Consider Multilevel queue scheduling algorithm with 5 queues.

➢ No process is batch queue could run unless the queue for system process, interactive process were all
empty.
➢ If an interactive process entered the ready queue while batch process was running, the batch process
will be preempted.
Multilevel feedback queue scheduling (MFQ)

➢ The multilevel feed back queue scheduling implements multilevel queues having the different priority
to each level and allows the process to move between the queues.
➢ If a process uses to much CPU time, it will be moved to lower priority queue.
➢ In addition, a process that waits too long in lower priority queue may be moved to higher priority
queue, to prevents starvation.

Example
➢ Consider a multilevel feedback queue scheduler with three queues numbered 0 to 2 with quantum size
8,12 and 32.
➢ The scheduler first executes all processes in queue 0. Only when queue 0 is empty it will execute
process in queue 1 and process in queue 2 executes only if queue 0 and queue 1 are empty. A process in
queue 1 will in turn be preempted by process arriving for queue 0.
➢ A process entering the ready queue is put in queue 0 and executes for 8 millisecond. If it does not finish
with in this time it moves to the tail of queue 1.
➢ If queue 0 is empty, the process at the head of queue 1 start execute with 16msec quantum. If it does
not complete it is preempted and put into queue 2.
➢ Process in queue 2 are run on an FCFS order but are run only when queues 0 and 1 are empty.
Parameter for defining Multilevel feedback queue scheduler
In general, a multilevel feedback queue scheduler is defined by the following parameters:
➢ Number of queue.
➢ The scheduling algorithm for each queue
➢ The method used to determine when to upgrade a process to a higher priority queue
➢ The method used to determine when to demote a process to lower priority queue.
➢ The method used to determine which queue process will enter when that process needs service.

Example
Consider the following set of processes with the length of CPU burst time given in millisecond

Process Burst Time Priority

P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
The process are assumed to have arrived in the order P1,P2………… all at time 0.
➢ Draw four Gantt chart illustrating the execution of these process using FCFS, SJF, a non preemptive
priority (a smaller priority number implies a higher priority) and RR scheduling (quantum 1)
➢ What is turn around time and waiting time of each process for each of the scheduling algorithm in part
a.
➢ Calculate average turn around time and average waiting time for each algorithm.
Interprocess communication and synchronization

Independent and cooperating processes

➢ Process executing concurrently in the operating system may be either independent processes or
cooperating processes.
➢ A process is independent if it cannot affect or be affected by the other processes executing in the
system. Any process that does not share data with any other process is independent.
➢ A process is cooperating if it can affect or be affected by the other process executing in the system
clearly any process that shares data with other processes is cooperating processes.

Why process cooperation?

There are several reasons for providing an environment that allows process cooperation:
➢ Information sharing
Since several user may be interested in the same piece of information (for instance a shared files), we
must provide environment to allow concurrent access to sub information.

➢ Computation speedup
If we want a particular task to run faster, we must break it into subtask, each of which will be
executing in parallel with the other.

➢ Modularity
We may want to construct the system in modular fashion, dividing the system functions into separate
processes.
➢ Convenience
Even an individual user may work on many task at the same time. For instance, a user may be editing,
printing and compiling in parallel.
Interprocess communication

➢ Interprocess communication(IPC) is the mechanism that allow a process to exchange data and
information. Cooperating process requires IPC to complete their task.
➢ There are two fundamental model of interprocess communication:
❑ Shared memory
❑ Message passing

❑ Shared memory
➢ In the shared memory model of IPC, a region of memory that is shared by cooperating process is
established.
➢ Process can exchange information by reading and writing data to the shared region in shared
memory model.
➢ Shared memory allows maximum speed and convenience of communication.
➢ Shared memory is faster than message passing, as message passing system are typically
implemented using system calls and thus requires the more time consuming task of kernel
intervention.
➢ The following figure depict shared memory interprocess communication model:
❑ Message passing
➢ In message passing model, communication takes place by means of message exchange between
the cooperating process i.e. message passing provides a mechanism to allow processes to
communicate without sharing the same address space and is particularly useful in distributed
environment, where the communicating processes may reside on different computers connected
by a network.
➢ Message passing facility provides at least two operations:
❖ Send (message)
❖ Receive (message)
➢ If a process P and Q want to communicate, they need to establish a communication link between
them and exchange message via send and receive.
Send (P, message) = Send message to process P
Receive (Q, message) = receive message from Q
➢ Message passing system are typically implemented using system call and thus requires a more
time consuming task of kernel intervention. The message passing communication model is
depicted by following figure:
Interprocess communication issues
Process frequently needs to communicate with other processes to complete their task. The
mechanism of passing information from one process to another process is called interprocess communication.

(Imp) There are three main issues related to IPC. They are:
➢ How one process can pass information to another process.
➢ How to make sure two or more processes do not get in each others way when engaging in shared
resources.
➢ How to maintain the proper sequence when dependencies are present.

• Give briefly at least three different ways of establishing interprocess communication.

Race condition (imp/ Definition and how is it avoided?)

➢ Situation where two or more processes are reading or waiting some shared data and the final result
depends on who runs precisely when, are called race condition.
➢ In other word, race condition is a situation where two or more processes read or writes some shared
data concurrently and final result depends on particular order in which the access takes place.

➢ To see how interprocess communication work in practice and how race condition arises.
➢ Lets us consider simple and common example: a print spooler
❑ When a process want to print a file, it enters the file name in spooler directory.
❑ Another process the printer daemon periodically checks to see if there are any files to be printed
and if there are, it prints them and removes their name from the directory.
❑ Consider the situation given in fig. below where ‘in’ point to the next free slot in the directory and
‘out’ point to the next file to be printed are two shared variables.
❑ Let process A and process B decide they want to queue a file for printing.
❑ Let process A reads ‘in’ i.e. 7 but before inserting the name of documents to be printed in index 7
clock interrupt occurs and CPU decide to schedule process B.
❑ Now, process B also reads ‘in’ and get 7. At this instance, both process think that next available
slot is 7.
❑ Process B now continues to run it stores the name of its file in slot 7 and update ‘in’ to be 8.
❑ After sometimes process A runs again, starting from the place it left off and it finds in=7 and write
its file name in slot 7, erasing the name that process B just put there and it update the value of ‘in’
to be 8.
❑ The printer daemon will not notice anything wrong but process B will never receive any output.
Situation like this are called race condition.
Possibility of race
➢ Many concurrent processes read the same data.
➢ One process reading and another process writing same data.
➢ Two or more processes writing same data.
Avoiding the Race condition (Solution of race condition)
➢ One way to prevent from race condition is to find some way to prohibit more than one process from
reading and writing the shared data at the same time i.e. we need mutual exclusion.
➢ (imp) Mutual exclusion is some way of making sure that if one process is using a shared variable or
shared file the other process will be excluded from doing the same thing.
Critical section / Critical region (Why execution of critical section is mutually exclusive?)
➢ Sometimes a process has to access shared memory or files that can lead to a race condition.
➢ The part of the process that access to shared variable, shared memory or shared file is called critical
region or critical section.
➢ One way to avoid race condition is not to allow two processes in their critical section at the same time
i.e. when one process is executing its critical section no other process is allowed to execute its critical
section. So, it avoid the race condition execution of critical section by the process is mutually exclusive.
Critical section problem (CSP)
➢ Critical section problem is to design a protocol so that no two processes are executing in their critical
section at the same time.
➢ In short, problem of avoiding a race condition is called critical section problem.
➢ Each process must request a permission to enter its critical section. The section of code implementing
this request is entry section and critical section is followed by exit section.
➢ The general structure of process is
while (true)
{
entry section
critical section
exit section
Remainder section
}
Good solution of race condition
➢ If we could arrange the process such that no two process were in their critical section at the same time,
we could avoid the race.
➢ Although this requirement avoid race condition, in fact to provide the good solution to the problem of
race condition we need 4 conditions to hold.
1. No two processes may be simultaneously inside their critical section (i.e. Mutual exclusion)
2. No assumption may be made about speed or number of CPU’s.
3. No process running outside its critical section may block other processes to enter its critical
section.
4. No process should have to wait forever to enter its critical section.
➢ In abstract sense, the behaviour we want is shown in figure below:

➢ Here, process A enters its critical region at time T1.

➢ At time T2, process B attempt to enter its critical region but fails because another process is already in
its critical region and we allow only one at a time.
➢ Consequently, B is suspended until time T3 when A leaves its critical region, allowing B to enter
immediately in its critical region and continue its execution.
Implementing mutual exclusion (solution of CSP)
➢ Mutual exclusion with busy waiting (hardware solution of achieving mutual exclusion)
❑ (imp) Continuously testing a variable until some value appear is called busy waiting.
❑ In other word, busy waiting means if the process is not allowed to enter its critical section, it sits in a
tight loop waiting for the condition to be made.
❑ This is obviously wasteful in terms of CPU uses.
❑ Various methods for achieving mutual exclusion with busy waiting are:
1. Disable interrupt
✓ The simplest solution to achieve a mutual exclusion is to have each process disable all
interrupts just after entering its critical section and re-enable them just before leaving it.
✓ By disabling the interrupt, the CPU will be unable to switch to other processes so this
guarantee that process can use shared variable of file without fear that any other process
intervenes.
✓ Problem:
❖ The approach is generally unattractive because it is unwise to give user process
power to turn off the interrupt.
❖ Suppose that one of them did it, and never turn them on again, this cause the end of
the system.
❖ Although disabling interrupt might seen a good solution its disadvantage
overshadow the advantage.

2. Lock variable
✓ Lock variable is a software solution to achieve mutual exclusion.
✓ It is the binary shared variable whose value is either 0 or 1. Initially, 0 is assigned to a lock
variable.
✓ When process want to enter its critical region, it first test the lock variable.
✓ If the lock is zero, the process set it to 1 and enter the critical region.
✓ If the lock is already 1, the process just waits until it become 0. Thus, a zero means no
process is in its critical region and 1 means that some process is in its critical region.
 While(lock !=0); //wait//
{
lock = 1;
critical section ();
lock = 0;
remainder section ();
}

✓ Problem
It again suffer from race condition.
❖ Suppose that one process read the lock and sees that it is zero but before it can set the
lock to 1, another process is schedule, runs and set the lock to 1.
❖ When the first process runs again it can also set the lock to 1 and two processes will be in
their critical section at the same time (i.e. lock variable violates mutual exclusion
condition)

3. Strict Alternation
✓ The third approach to critical section problem is strict alternation.
✓ In this approach, process share the common integer variable turn. If turn=0 then process P0 is
allowed to execute in its critical section, if turn = 1, process P1 is allowed to execute in its critical
section.
Process 0
while (true)
{
while (turn !=0); //wait//
critical section ();
turn = 1;
remainder section ();
}
Process 0
while (true)
{
while (turn !=0); //wait//
critical section ();
turn = 1;
remainder section ();
}

Process 1
while (true)
{
while (turn !=1); //wait//
critical section ();
turn = 0;
remainder section ();
}

✓ Assume the variable turn is initially set to zero and process P0 inspect turn and find that turn is 0
and it is allowed to enter its critical section.
✓ If process P1 tries to run, it will find that turn is zero and will have to wait until turn becomes 1.
✓ When process P0 exit its critical section it sets turn to 1 which allow the process P1 to enter its
critical region.
✓ Again, if process P0 tries to enter its critical section it will be blocked as turn is becomes to 0.
Hence, this approach preserve mutual exclusion condition.
✓ Problems:
❖ This approach has the problem of strict alternation.
❖ Consider the following sequence of event.
 ❖ Process 0 (P0) runs, enters its critical section and exit by setting turn to 1. Process P0 is
now in its non-critical section or remainder section. Assume this remainder section takes
long time.
❖ Process P1 which is much faster process now runs and once it has left its critical section
turn is set to 0.
❖ Process P1 executes its non-critical section very quickly and return on the top of the
procedure.
❖ The situation is now that process P0 is in its non-critical section and process P1 is waiting
for turn to be set to 1.
❖ From this observation we can see that strict alternation violates the condition “No process
running outside its critical section may block other processes.”

4. Peterson’s solution
✓ It is the solution to the mutual exclusion problem that does not require strict alternation but still
uses the idea of lock variable with the concept of taking turn.
✓ The Peterson’s solution consists of two procedure shown below:
# define FALSE 0
# define TRUE 1
# define N 2 /*number of process*/
int turn; /*whose turn is it */
int interested[n]; /*all values initially o(FALSE)*/
void enter_region (int process) /*process is 0 or 1*/
{

int other; /*number of other process*/

other = 1- process; /*the opposite of the process*/
interested[process] = TRUE; /*show that process is interested*/
Turn = Process; /*set flag*/
 while (turn==process&&interested[other]==TRUE); /*wait*/
}

void leave-region (int process) /*process who is leaving*/

{
interested[process]=FALSE; /*indicates departure from critical
region*/
}
✓ In this solution, before entering its critical section each process call enter region with its own
process number 0 or 1 as parameter. After it has finished its critical section, the process calls
leave region to indicate that it is done.
✓ Let us see how this solution works and preserve mutual exclusion.
✓ Initially neither process is in its critical section and array interested has all element set to false.
✓ Now, let process zero calls enter region. It indicates its interest and set turn to 0. Since process1
is not interested so process 0 enters its critical section immediately.
✓ If process 1 now makes a call to enter critical region it will wait until interested [0]=false, which is
only happen when process 0 calls leave region to exit the critical section.
✓ Problem:
❑ Difficult to program for N process system.

5. Test and set lock(TSL)

✓ To implement this solution of mutual exclusion problem, we need little help from hardware.
✓ The machine code or assembly instruction we require is test and set LOCK.
✓ The TSL instruction reads the content of memory word lock into registers and then store a non
zero value at the memory address LOCK. This whole operation is atomic i.e. no other process can
access that memory location until TSL instruction has finished.
✓ The following assembly code shows how we can make the use of TSL instruction to solve the
mutual exclusion problem.
enter_region;
TSL Register, Lock /*copy to register and set lock to 1*/
CMP Register, #0 /*was lock 0?*/
TNE enter_region /*if it was non zero, lock was set, so loop*/
RET /*return to caller i.e. entered in critical region*/

leave_region;
MOV lock, #0 /*store 0 in lock*/
RET /*return to caller i.e. leave critical region*/

❑ Assume again two process 0 and process 1. Assume initially LOCK is 0.

❑ Let process 0 calls enter region then TSL instruction copies LOCK to a register and set lock
to 1.
❑ The value of LOCK stored on register is then compared to zero if it is found to be non-zero
i.e. 1 the routine loops back to the top otherwise enter into the critical region.
❑ To leave the critical section process calls leave region and set the value of lock to 0 by MOV
instruction.
Comments on busy waiting (imp)
➢ Both Peterson’s solution and TSL solution solve the mutual exclusion problem. However, both of these
solution suffers from following two problems:
✓ Busy waiting problem
❖ If the process is not allowed to enter the critical section, it sits in a tight loop waiting for
the condition to be met. This is obviously wasteful in terms of CPU uses.
✓ Priority inversion problem
❖ Suppose we have two processes, one of high priority H and one of low priority L.
❖ If L is in its critical section when H becomes ready to run then L will be placed in ready
state so that H can be run.
❖ If H tries to enter its critical section then it will be blocked by L and H will simply sit in a
loop forever.
❖ This situation is referred to as priority inversion problem.
Alternatives of busy waiting
Sleep and wakeup
➢ One of the simplest solution to achieve mutual exclusion without busy waiting is the pair sleep and
wake up system call.
➢ Sleep and wakeup are interprocess communication primitives that block the process instead of
wasting the CPU time when they are not allowed to enter the critical section.
➢ Sleep is a system call that cause the caller to block until other process wakeup it.
➢ The wakeup call has one parameter, the process to be wakeup.
Producer consumer problem
➢ It is also known as bounded buffer problem.
➢ Two processes called producer and consumer share a common fixed size buffer.
➢ Producer put the information or item into the buffer and consumer takes it out.
➢ Problem arises when procedure want to put a new item in the buffer but it is already full.
➢ The solution for this problem is producer goes to sleep until consumer has removed one or more items
and wakeup it.
➢ Similarly, if the consumer want to remove an item from the buffer but sees that buffer is empty, it goes
to sleep until the producer puts something in the buffer and wakes up it.
➢ The code for both producer and consumer is shown below:

#define N 100 /*Number of slot in the buffer*/

int count=0; /*Number of items in the buffer*/
void producer(void)
{
int item;
while (TRUE)
{
item=Produce_item(); /*generate next item*/
if(count==N)sleep(); /*if the buffer is full go to sleep*/
insert_item(item); /*put the item in the buffer*/
count=count+1; /*increment count in the buffer*/
if (count==1)wakeup(consumer); /*was the buffer empty?*/
}
}
void consumer(void)
{
int item;
while(TRUE)
{
if(count==0)sleep(); /*if buffer is empty go to sleep*/
item=remove_item(); /*take item out of buffer*/
count=count-1; /*decrement count*/
if(count==N-1)wakeup(producer); /*was the buffer full*/
consume_item(item); /*print them*/
}
}
Problem on producer consumer using sleep and wakeup
This producer consumer problem using sleep and wakeup seems logically correct but there is the
problem. The following situation could arise:
➢ The buffer is empty and consumer just read the count to see if it is 0.
➢ Scheduler stops running the consumer and start running the producer. The producer places an item in
the buffer and increment count and wake up the consumer.
➢ In fact, consumer is not at sleep so wakeup signal is lost. When consumer next runs, it continues from
where it left off i.e. it finds value of count to zero and go to the sleep.
➢ As wakeup call has already been issued, the consumer will sleep forever.
➢ Sooner or later the producer will fill up the buffer and go to sleep. Hence, both process will sleep
forever i.e. no progress.
Semaphore (imp)

➢ The concept of semaphore was devised by Edger Dijkstra in 1965.

➢ Semaphore is an integer variable that is used to record number of wakeup’s that had been saved.
➢ Semaphore could have the value zero indicating that no wakeup’s were saved or some positive value if
one or more wakeup’s were pending.
➢ Semaphore has two operations: down and up
➢ The down operation on semaphore checks to see if the value is greater than zero. If so it decrements
the value(i.e. uses of one stored wakeup) and just continue. If the value is zero, the process is could to
sleep without completing down operation.
➢ The up operation increment the value of semaphore. If one or more processes were sleeping on that
semaphore then one of the process is chosen and allow to complete down.
➢ Checking and updating the semaphore is atomic action to avoid the race condition.

typedef int semaphore s

void down(s)
{
if(s>0)s- -
else sleep();
}
void up(s)
{
if(one or more process are sleeping on s)
one of them is processed
else
s++
}
Producer consumer problem using semaphore (imp)
Producer consumer problem can be solver using semaphore as below:
#define N 100
typedef int semaphore
semaphore Mutex = 1
semaphore empty = N
semaphore full = 0
void Producer(void)
{
int item;
while(TRUE)
{
item=produce item;
down(&empty);
down(&Mutex);
insert_item(item);
up(&Mutex);
up(&full);
}
}
void consumer(void)
{
int item;
while(TRUE)
{
down(&full);
down(&Mutex);
item=remove item();
up(&Mutex);
up(&empty);
consumer_item();
}
}
 ➢ This solution uses 3 semaphores:
1. Full: This is used for counting the number of slot that are full.
2. Empty: This is used for counting the number of slot that are empty.
3. Mutex: This is used to make sure that producer and consumer do not access the buffer at the
same time i.e. to make mutual exclusion.

➢ Full is initially zero, empty is initially equal to number of slot in the buffer i.e. N and Mutex is initially 1. If
each process does the down Mutex before entering its critical region and up just after leaving it,
mutual exclusion is guaranteed.
➢ This solution ensure that producer stops running when buffer is full and consumer stops running when
buffer is empty.

Use of semaphore
➢ To deal with n process critical section problem.
➢ To solve the synchronization problem
✓ For example: Two concurrently running processes P1 with statement S1 and P2 with statement
S2. Suppose we require that S2 must be executed after S1 has completed. This problem can be
implemented by using common semaphore synchronization initialized to 0 as
semaphore synchronize=0
P1:s1
up(synchronize)
P2:down(synchronize)
S2
Criticality using semaphore
➢ We should be too much careful about the order of down operation when we use the semaphore.
➢ For Eg: suppose that two downs in the producer’s code were reversed in order then mutex was
decremented before empty.
➢ If the buffer were completely full, the producer would block with mutex set to 0.
➢ Consequently, the next time the consumer tried to access the buffers, it would do a down on mutex
which is 0 and blocked too.
➢ Hence, both processes would block forever and no more work would be done and deadlock arises.
➢ So, using the semaphore by the programmer is critical.

Monitor
➢ Semaphore is very useful for solving critical section problem only if programmer use them properly. If
anyone process fails to proper use of semaphore cause the subtle error i.e. deadlock will be arises.
➢ To make it easier to write correct program, Brinch and Hoare purposed a higher level synchronization
primitive called a monitor.
➢ A monitor is a collection of procedure, variable and data structure that are grouped together in a
special kind of module or package.
➢ Process may call the procedure in a monitor whenever they want to but they cannot directly access
the monitors internal data structures.
➢ Monitor have an important property that only one process can be active in a monitor at any instant.
➢ Typically, when a process call a monitor procedure, the few instruction of producer will check to see if
any other process is currently active within the monitor. If so, the calling process will be suspended
until the other process has left the monitor. If no, other process is using the monitor, the calling
process may enter.
➢ The skeleton of producer consumer problem with monitor is given below:
Monitor Producer consumer
condition full, empty;
integer count;
Procedure insert(item : integer)
begin
if count = N then wait (full)
insert_item (item)
count = count+1
if count = 1 then signal (empty)
end:
function remove (item : integer)
begin
if count = 0 then wait (empty);
remove item (item)
count=count-1
if count = N-1 then signal (full)
end:
end monitor:
Producer producer
begin
while true do
begin
item=produce item;
[Link](item)
end
end;
Producer consumer
begin
while true do
begin
item = Producer [Link]
consumer item(item);
end
end;
Disadvantage

➢ Lack of implementation in most commonly used programming language like C and C++.
➢ Not applicable for distributed system consisting of multiple CPU’s with its own private memory
connected by LAN.

Message Passing

➢ When interprocess communication is needed in distributed environment, message passing is needed.

➢ This method of interprocess communication uses two primitives: send and receive system call.
➢ Send (destination, &message) send a message to a given destination.
➢ Receive (Source, &message) receive a message from given source.
➢ If no message is available, the receiver can blocked until one arises/arrives.

Design issues for message passing system

➢ Message passing system have many challenging problems and design issues that do not arise with
semaphore or monitors. Some issues are:
❑ Message can be lost by the network(solution for this is receiver can send special
acknowledgement message as soon as message has been received)
❑ Message is received correctly but acknowledgement back to the sender is lost
❑ Authenticate problem
❑ Performance is also issue when sender and receiver are on the same machine.
Producer consumer problem using message passing

➢ The producer consumer problem can be solved with message passing and no shared memory. The
solution using message passing is presented below:

#define N 10
void producer(void)
{
int item;
message m; /*message buffer*/
while (TRUE)
{
item=Produce_item();
receive(consumer, &m); /*wait for an empty to arrive*/
build_message(&m, item)
send(consumer, &m)
}
}
void consumer(void)
{
int item, I;
for ( I = 0; I < N; I++)
{
send(producer, &m) /*send N empty message*/
}
item=extract_item(&m)
send(producer, &m);
consume_item(item)
}
Classical IPC problem (Imp)

Dining philosopher problem

➢ This problem was posed by Dijkstra. The problem can be stated quite simply as follows:
❑ Five philosopher are sited around a circular table. Each philosopher has a plate of spaghetti and
philosopher needs two forks to eat it.
❑ Between each pair of plate there is one fork as shown in figure below:

❑ The life of philosopher consist of alternate period of eating and thinking.

❑ When philosopher gets hungry, philosopher tries to acquire left and right fork one at a time in
either order.
❑ If successful in acquiring two forks, philosopher eats and put down the fork on the table and
continue to think.
❑ The key question is can a program be written for each philosopher that does never get stuck.
i.e. no philosopher is waiting for fork forever.
Solution 1
❑ When a philosopher is hungry, it picks up the fork and wait for another fork, when get it, it
eats for a while and puts both for back to the table.
❑ Problem: Suppose that all 5 philosophers takes their left fork simultaneously. Then none will
be able to tale their right forks and there will be a deadlock.

Solution 2
❑ After taking the left fork the program checks for right fork, if it is not available the philosopher
puts down the left one, wait for sometime and repeat the whole process.
❑ Problem: With a little bit of bad luck, all the philosopher could start the process of picking left
fork simultaneously, seeing that their right fork is unavailable, putting down their left fork,
waiting sometime and picking up their left fork again simultaneously and so on forever. In this
case starvation occurs.(i.e. all program continue to run and definitely but fails to make any
progress)

Solution 3
❑ Using the binary semaphore Mutex. Before starting to acquire a fork philosopher would down
on Mutex, after placing the fork philosopher would do up Mutex.
❑ Problem: This solution is adequate (i.e. no deadlock and starvation is there) but not perfect i.e.
only one philosopher can be eating at any instant.
Solution 4 (write in exam)
❑ The perfect solution using semaphore for each philosopher is presented below:
#define N 5
#define LEFT(i)
#define RIGHT(i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef semaphore;
int state[N]
semaphore Mutex=1
semaphore S[N]
void philosopher(int i)
{
while (TRUE)
{
think();
takefork(i);
eat();
put_fork(i);
}
}
Void take_forks(int i)
{
down (&Mutex)
state[i]=HUNGRY
test[i];
up (&Mutex)
down (&S[i])
}
Void put_fork(i)
{
down (&Mutex);
state[i]=THINKING;
test(LEFT)
test(RIGHT)
up(Mutex)
}
Void test(i)
{
if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING)
{
state[i]=EATING;
up(&s[i])
}
}

❑ Here we use an array state to keep track of whether the philosopher is eating, thinking or
hungry. A philosopher may move in eating state if neither neighbor is eating.
❑ This solution uses an array of semaphore one per philosopher so hungry philosopher can block
if the needed forks are busy.
Sleeping Barber Problem
❑ Problem: The analogy is based on a hypothetical barber shop with one barber, one barber chair, and
n chairs for waiting for customers if there are any to sit on the chair.
➢ If there is no customers, then the barber sleeps in his own chair.
➢ When a customer arrives, he has to wake up the barber.
➢ If there are many customers and the barber is cutting a customer’s hair, then the remaining
customers either wait if there are empty chairs in the waiting room or they leave if no chairs
are empty.

Solution:
❑ It include three semaphores.
➢ First for customer, which counts the number of customers
presents in the waiting room (customer in the barber chair
is not included because he is not waiting).
➢ Second for barber, 0 or 1 is used to tell whether barber is
idle or working.
➢ Third mutex, is used to provide the mutual exclusion which
is required for the process to execute.
Algorithm

Barber {
while(true) {
down(Customers); /* waits for a customer (sleeps). */
down(Seats); /* mutex to protect the number of available seats.*/
FreeSeats++; /* a chair gets free.*/
up(Barber); /* bring customer for haircut.*/
up(Seats); /* release the mutex on the chair.*/

/* barber is cutting hair.*/

}
}
Customer {
while(true) {
down(Seats); /* protects seats so only 1 customer tries to sit in a chair if that's the case.*/

if(FreeSeats > 0) {
FreeSeats- -; /* sitting down.*/
up(Customers); /* notify the barber. */
up(Seats); /* release the lock */
down(Barber); /* wait in the waiting room if barber is busy. */
// customer is having hair cut
} else {
up(Seats); /* release the lock */
// customer leaves
}
}
}