Sri Devaraj Urs Educational Trust (R.

)
R. L. JALAPPA INSTITUTE OF TECHNOLOGY
(Approved by AICTE, New Delhi, Affiliated to VTU, Belagavi & Accredited by NAAC “A” Grade)
Kodigehalli, Doddaballapur- 561 203
Department of CS&E (Artificial Intelligence & Machine Learning)

Subject Code: BCS303

Subject Name: Operating Systems
Module Number: 02
Name of the Module: Multi-Threaded Programming and Process
Synchronization
Scheme: 2022
Prepared by
Manjunatha N
Assistant Professor
Institute Vision
To be a premier Institution by imparting quality Technical education, Professional Training
and Research.

Institute Mission
M1: To provide an outstanding Teaching, Learning and Research environment through
Innovative Practices in Quality Education.
M2: Develop Leaders with high level of Professionalism to have career in the Industry, Zeal
for Higher Education, focus on Entrepreneurial and Societal activities.

Department Vision
To empower the students with knowledge and skills to develop the competency in the field of
Artificial Intelligence and Machine Learning.

Department Mission
M1: To craft the students with Novel and Intellectual skills to capability in the field of
Artificial Intelligence and Machine Learning.
M2: To train the students to have Professional career in the field of AI and ML and zeal for
Higher Studies and Research.
 Sri Devaraj Urs Educational Trust (R.)
R. L. JALAPPA INSTITUTE OF TECHNOLOGY
(Approved by AICTE, New Delhi, Affiliated to VTU, Belagavi & Accredited by NAAC “A” Grade)
Kodigehalli, Doddaballapur- 561 203
Department of CS&E (Artificial Intelligence & Machine Learning)

PROGRAMME SPECIFIC OUTCOMES (PSOs)

PSO1: Students will have the ability to understand analyse and demonstrate the knowledge
of Human cognition, Artificial Intelligence, Machine Learning in terms of real world
problems to meet the challenges of future.

PSO2: Students will have the knowledge of software, Hardware, Algorithms, Modelling
Networking and Application Development.

PSO3: Students will have the ability to develop computational knowledge using Innovative
tools and techniques to solve problems in the areas related to Machine learning and Artificial
Intelligence.

PROGRAMME EDUCATIONAL OBJECTIVES (PEOs)

PEO1: Graduates will have Prospective careers in the field of AI and ML.

PEO2: Graduates will have good Leadership Qualities, Self Learning abilities and zeal for
higher studies and Research.

PEO3: Graduates will follow Ethical Practices and exhibit high level of professionalism by
participating and addressing Technical, Business and Environmental challenges.
 Outline
 MULTI-THREADED PROGRAMMING
 Overview
 Multithreading models
 Thread Libraries
 Threading issues
 Process Scheduling Basic concepts, Scheduling Criteria, Scheduling Algorithms
 Multiple-processor scheduling
 Thread scheduling
 Process Synchronization
 Synchronization
 The critical section problem
 Peterson’s solution
 Synchronization hardware
 Semaphores
 Classical problems of synchronization
 Monitors.

Department of Computer Science, RLJIT 4

 Multi threaded programming
 A thread is a basic unit of CPU utilization.
 It consists of
→ thread ID
→ PC
→ register-set and
→ stack.
 It shares with other threads belonging
to the same process its code-section &
data-section.
 A traditional (or heavy weight)
process has a single thread of control.
 A multi-threaded application have multiple threads within a single process, each
having their own program counter, stack and set of registers, but sharing common
code, data, and certain structures such as open files. Such process are called as
lightweight process.
 If a process has multiple threads of control, it can perform more than one task at
a time. Such a process is calledDepartment
multi-threaded process.
of Computer Science, RLJIT
5
 Multi threaded programming
1 Motivation
1)The software-packages that run on modern PCs are multithreaded.
An application is implemented as a separate process with several
threads of control.
For example: A word processor may have
→ first thread for displaying graphics
→ second thread for responding to keystrokes and
→ third thread for performing grammar checking.
2) In some situations, a single application may be required to perform several
similar tasks.
For example: A web-server may create a separate thread for each client
request. This allows the server to service several
concurrent requests.

Department of Computer Science, RLJIT 6

 Multi threaded programming
3) RPC servers are multithreaded. When a server receives a message, it
services the message using a separate thread. This allows the server to
service several concurrent requests.
4) Most OS kernels are multithreaded; Several threads operate in kernel, and
each thread performs a specific task, such as
→ managing devices or
→ interrupt handling.

Department of Computer Science, RLJIT 7

 Multi threaded programming
2 Benefits
1) Responsiveness - A program may be allowed to continue running even if
part of it is blocked. Thus, increasing responsiveness to the user.
2) Resource Sharing - By default threads share common code, data, and other
resources, which allows multiple tasks to be performed simultaneously in a
single address space.
3) Economy - Creating and managing threads is much faster than performing
the same tasks for processes. Context switching between threads takes less
time.
4) Utilization of Multiprocessor Architectures - In a multiprocessor
architecture, threads may be running in parallel on different processors.
Thus, parallelism will be increased.

Department of Computer Science, RLJIT 8

 Multi-Threading Models
Support for threads may be provided at either
1) The user level, for user threads or
2) By the kernel, for kernel threads.
User-threads are supported above the kernel and are managed without kernel
support.
Kernel-threads are supported and managed directly by the OS.
Three ways of establishing relationship between user-threads & kernel-threads:
3) Many-to-one model
4) One-to-one model and
5) Many-to-many model.

Department of Computer Science, RLJIT 9

 Multi-Threading Models
1. Many-to-One Model
Many user-level threads are mapped to one kernel thread

For example:
→ Solaris green threads
→ GNU portable threads.

Figure : Many-to-one model

Department of Computer Science, RLJIT 10

 Multi-Threading Models
2. One-to-One Model
Each user-level thread maps to kernel thread

For example:
→ Windows NT/XP/2000
→ Linux

Figure : One-to-one model

Department of Computer Science, RLJIT 11

 Multi-Threading Models
3. Many-to-Many Model
The many-to-many model multiplexes any number of user threads onto an equal
or smaller number of kernel threads, combining the best features of the one-to-
one and many-to-one models.
For example:
Windows NT/2000 with the Thread Fiber
package

Figure : Many-to-many model

Department of Computer Science, RLJIT 12
 Thread Libraries
 It provides the programmer with an API for the creation and management of
threads.
 Thread libraries may be implemented either in user space or in kernel space.
 There are three main thread libraries in use –
1. POSIX Pthreads –
 may be provided as either a user or kernel library, as an extension to the
POSIX standard.
 The POSIX standard ( IEEE 1003.1c ) defines the specification for
Pthreads, not the implementation.
 Pthreads are available on Solaris, Linux, Mac OSX, Tru64, and via
public domain shareware for Windows.
2. Win32 threads - provided as a kernel-level library on Windows systems.
3. Java threads - Java threads are managed by the JVM.

Department of Computer Science, RLJIT 13

 Threading Issues
1. fork() and exec() System-calls
 fork() is used to create a separate, duplicate process.
 If one thread in a program calls fork(), then
1) The new process can be a copy of the parent, with all the threads.
2) The new process is a copy of the single thread only (that invoked the
process).
 If a thread invokes the exec(), the program specified in the parameter to
exec() will replace the entire process including all threads.

Department of Computer Science, RLJIT 14

 Threading Issues
2. Thread Cancellation
 Terminating the thread before it has completed its task is called thread
cancellation. The thread to be cancelled is called target thread.
Example : Multiple threads required in loading a webpage is suddenly cancelled,
if the browser window is closed.
Thread cancellation occurs in two different cases:
1) Asynchronous cancellation: cancels the thread immediately.
2) Deferred cancellation: The target thread periodically checks whether it
should be terminated.

Department of Computer Science, RLJIT 15

 Threading Issues
3. Signal Handling
A signal is used to notify a process that a particular event has occurred.
All signals follow this pattern:
1) A signal is generated by the occurrence of a particular event.
2) A generated signal is delivered to a process.
3) Once delivered, the signal must be handled.
A signal can be invoked in 2 ways : synchronous or asynchronous.
Synchronous signal – signal delivered to the same program.
Example – illegal memory access, divide by zero error.
Asynchronous signal – signal is sent to another program. Example – Ctrl C

Department of Computer Science, RLJIT 16

 Threading Issues
In a single-threaded program, the signal is sent to the same thread. But, in
multithreaded environment, the signal is delivered in variety of ways, depending
on the type of signal –
 Deliver the signal to the thread, to which the signal applies.
 Deliver the signal to every threads in the process.
 Deliver the signal to certain threads in the process.
 Deliver the signal to specific thread, which receive all the signals.

A signal can be handled by one of the two ways –

Default signal handler - signal is handled by OS.
User-defined signal handler - User overwrites the OS handler.

Department of Computer Science, RLJIT 17

 Threading Issues
4. Thread Pools
The basic idea is to create a number of threads at process-start up and place the
threads into a pool (where they sit and wait for work).
Procedure:
 Threads are allocated from the pool when a request comes, and returned
to the pool when no longer needed(after the completion of request).
 When no threads are available in the pool, the process may have to wait
until one becomes available.

Department of Computer Science, RLJIT 18

 PROCESS SCHEDULING
Basic Concepts
 In a single-processor system, only one process can run at a time; other processes
must wait until the CPU is free.
 The objective of multiprogramming is to have some process running at all times
in processor, to maximize CPU utilization.

Department of Computer Science, RLJIT 19

 PROCESS SCHEDULING
CPU-I/O Burst Cycle
 Process execution consists of a cycle of
 CPU execution and
 I/O wait.
 The state of process under execution is called CPU
burst and the state of process under I/O request &
its handling is called I/O burst.
 Process execution begins with a CPU burst,
followed by an I/O burst, then another CPU burst,
etc…
 Finally, a CPU burst ends with a request to
terminate execution.

Figure : Alternating sequence of CPU and I/O bursts

Department of Computer Science, RLJIT 20
 PROCESS SCHEDULING
 CPU Scheduler or Short-term scheduler selects from among the processes
in ready queue, and allocates the CPU to one of them.
 A ready queue can be implemented as a FIFO queue, a priority queue, a tree,
or simply an unordered linked list.

Department of Computer Science, RLJIT 21

 PROCESS SCHEDULING
CPU Scheduling
Four situations under which CPU scheduling decisions take place:
1) When a process switches from the running state to the waiting state.
For example; I/O request.
2) When a process switches from the running state to the ready state.
For example: when an interrupt occurs.
3) When a process switches from the waiting state to the ready state.
For example: completion of I/O.
4) When a process terminates.
Scheduling under 1 and 4 is non-preemptive. Once the CPU has been allocated
to a process, the process keeps the CPU until it releases the CPU either
→ by terminating or
→ by switching to the waiting state.
Scheduling under 2 and 3 is preemptive. The process under execution, may be
released from the CPU, in the middle of execution due to some inconsistent state
Department of Computer Science, RLJIT
of the process. 22
 PROCESS SCHEDULING
Dispatcher
Using dispatcher, CPU selects the process from the short term scheduler.
or
Dispatcher module gives control of the CPU to the process selected by the short-
term scheduler.
 This involves:
 switching context
 switching to user mode
 jumping to the proper location in the user program to restart that program
 Dispatch latency – time it takes for the dispatcher to stop one process and
start another running

Department of Computer Science, RLJIT 23

 Scheduling Criteria
Criteria to compare CPU-scheduling algorithms:
 CPU utilization – keep the CPU as busy as possible
 Throughput – Number of processes that complete their execution per time
unit
 Turnaround time – amount of time to execute a particular process.
It can also be considered as the sum of the time periods spent waiting to get into
memory or ready queue, execution on CPU and executing input/output.
 Waiting time – amount of time a process has been waiting in the ready queue
 Response time – amount of time it takes from when a request was submitted
until the first response is produced, not output (for time-sharing
environment)
It is desirable to maximize CPU utilization and throughput and to minimize
turnaround time, waiting time, and response time.

Department of Computer Science, RLJIT 24

 Scheduling Algorithms
CPU scheduling deals with the problem of deciding which of the processes in the
ready-queue is to be allocated the CPU.
Following are some scheduling algorithms:
1. FCFS scheduling (First Come First Served)
2. Round Robin scheduling
3. SJF scheduling (Shortest Job First)
4. SRT scheduling (Shortest Remaining Time)
5. Priority scheduling
6. Multilevel Queue scheduling and
7. Multilevel Feedback Queue scheduling

Department of Computer Science, RLJIT 25

 First-Come, First-Served (FCFS) Scheduling
 First-Come-First-Served algorithm is the simplest scheduling algorithm. Processes are
dispatched according to their arrival time on the ready queue.
 This algorithm is always non preemptive, once a process is assigned to CPU, it runs to
completion. Suppose that the processes arrive in the
Example: order:
Process Burst Time P2 , P3 , P1
P1 24  The Gantt chart for the schedule is:
P2 3
P3 3 P2 P3 P1
 Suppose that the processes arrive in the 0 3 6 30
order: P1 , P2 , P3  Waiting time for P1 = 6; P2 = 0; P3 = 3
The Gantt Chart for the schedule is:
 Average waiting time: (6 + 0 + 3)/3 = 3
P1 P2 P3
 Much better than previous case
0 24 27 30  Convoy effect - short process behind long
 Waiting time for P = 0; P = 24; P = 27 process
1 2 3
Department  Science,
of Computer Consider
RLJIT one CPU-bound
26 and many I/O-
 Average waiting time: (0 + 24 + 27)/3 = 17
 First-Come, First-Served (FCFS) Scheduling
Advantage:
1) Code is simple to write & understand.
Disadvantages:
2) Convoy effect: All other processes wait for one big process to get off the
CPU.
3) Non-preemptive (a process keeps the CPU until it releases it).
4) Not good for time-sharing systems.
5) The average waiting time is generally not minimal.

Department of Computer Science, RLJIT 27

 Shortest-Job-First (SJF) Scheduling
 The CPU is assigned to the process that has the smallest next CPU
burst.
 If two processes have the same length CPU burst, FCFS scheduling is
used to break the tie.
 SJF algorithm may be either 1) non-preemptive or 2) preemptive.

Department of Computer Science, RLJIT 28

 Shortest-Job-First (SJF) Scheduling
1) Non preemptive SJF :The current process is allowed to finish its CPU
burst.
Example of SJF
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2

0 3 9 16 24

Average waiting time = (3 + 16 + 9 + 0) / 4 = 7

Department of Computer Science, RLJIT 29

 Shortest-Job-First (SJF) Scheduling
Example (preemptive SJF): Consider the following set of processes, with the
length of the CPU-burst time given in milliseconds.

Advantage:
1) The SJF is optimal, i.e. it
gives the minimum average
waiting time for a given set
of processes.
Disadvantage:
1) Determining the length of
the next CPU burst.

Department of Computer Science, RLJIT 30

 Priority Scheduling
 A priority is associated with each process.
 The CPU is allocated to the process with the highest priority. (smallest
integer = highest priority)
 Equal-priority processes are scheduled in FCFS order.
Priority scheduling can be either preemptive or nonpreemptive.
1) Preemptive: The CPU is preempted if the priority of the newly arrived
process is higher than the priority of the currently running process.
2) Non Preemptive: The new process is put at the head of the ready-
queue.
Advantage: 1) Higher priority processes can be executed first.
Disadvantage: 1) Indefinite blocking, where low-priority processes are left
waiting indefinitely for CPU.
Solution: Aging is a technique of increasing priority of processes that wait in
system for a long time.

Department of Computer Science, RLJIT 31

 Priority Scheduling
As an example, consider the following set of processes, assumed to have
arrived at time 0, in the order P1, P2, … , P5, with the length of the CPU
burst given in milliseconds:

Department of Computer Science, RLJIT 32

 Round-Robin Scheduling
 The Round-Robin (RR) scheduling algorithm is designed especially for
timesharing systems.
 It is similar to FCFS scheduling, but pre-emption is added to switch
between processes.
 A small unit of time, called a time quantum or time slice, is defined. A
time quantum is generally from 1 to 100 milliseconds.
 The ready queue is treated as a circular queue.
 The CPU scheduler goes around the ready queue, allocating the CPU to
each process for a time interval of up to 1 time quantum.

Department of Computer Science, RLJIT 33

 Round-Robin Scheduling
 CPU scheduler
1) Picks the first process from the ready-queue.
2) Sets a timer to interrupt after 1 time quantum and
3) Dispatches the process.
One of two things will then happen.
4) The process may have a CPU burst of less than 1 time quantum.
In this case, the process itself will release the CPU
voluntarily.
2) If the CPU burst of the currently running process is longer than 1 time
quantum, the timer will go off and will cause an interrupt to the OS.
The process will be put at the tail of the ready-queue.
Advantage:
5) Higher average turnaround than SJF.
Disadvantage:
1) Better response time than SJF.
Department of Computer Science, RLJIT 34
 Round-Robin Scheduling

Process Burst Time

P1 24
P2 3
P3 3

 The Gantt chart is:

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

Department of Computer Science, RLJIT 35

 Multilevel Queue Scheduling
 Ready queue is partitioned into separate queues:
 foreground (interactive)
 background (batch)

 Each queue has its own scheduling algorithm:

 foreground – RR
 background – FCFS
 Scheduling must be done between the queues:
 Fixed priority scheduling; (i.e., serve all from foreground then from
background).
 Time slice – each queue gets a certain amount of CPU time which it can
schedule amongst its processes; i.e., 80% to foreground in RR
 20% to background in FCFS

Department of Computer Science, RLJIT 36

 Multilevel Queue Scheduling

Figure : Multilevel queue scheduling

Department of Computer Science, RLJIT 37

 Multilevel Feedback Queue Scheduling
 A process can move between the various queues; aging can be
implemented this way.
 Multilevel-feedback-queue scheduler defined by the following
parameters:
 number of queues
 scheduling algorithms for each queue
 method used to determine when to upgrade a process
 method used to determine when to demote a process
 method used to determine which queue a process will enter when
that process needs service

Department of Computer Science, RLJIT 38

 Multilevel Feedback Queue Scheduling
 Three queues:
 Q0 – RR with time quantum 8
milliseconds
 Q1 – RR time quantum 16 milliseconds
 Q2 – FCFS

 Scheduling
 A new job enters queue Q0 which is served FCFS. When it
gains CPU, job receives 8 milliseconds. If it does not finish
in 8 milliseconds, job is moved to queue Q1.
 At Q1 job is again served FCFS and receives 16 additional
milliseconds. If it still does not complete, it is preempted
and moved to queue Q2.
Department of Computer Science, RLJIT 39
 Multiple-Processor Scheduling

If multiple CPUs are available, the scheduling problem becomes more complex.
Two approaches:
1) Asymmetric Multiprocessing :
The basic idea is:
i) A master server is a single processor responsible for all scheduling
decisions, I/O processing and other system activities.
ii) The other processors execute only user code.
Advantage: i) This is simple because only one processor accesses the system data
structures, reducing the need for data sharing.

2) Symmetric Multiprocessing :
The basic idea is:
iii) Each processor is self-scheduling.
iv) To do scheduling, the scheduler for each processor
i. Examines the ready-queue and
ii. Selects a process to execute.
Restriction: We must ensure that two processors do not choose the same process
and that processes are not lost from the queue.
Department of Computer Science, RLJIT 40
 Thread Scheduling

 On OSs, it is kernel-level threads but not processes that are being scheduled by
the OS.
 User-level threads are managed by a thread library, and the kernel is unaware of
them.
 To run on a CPU, user-level threads must be mapped to an associated kernel-
level thread.
Contention Scope
Two approaches:
1)Process-Contention scope(PCS):
 On systems implementing the many-to-one and many-to-many models, the
thread library schedules user-level threads to run on an available LWP.
 Competition for the CPU takes place among threads belonging to the same
process.
2)System-Contention scope (SCS):
 The process of deciding which kernel thread to schedule on the CPU.
 Competition for the CPU takes place among all threads in the system.
 Systems using the one-to-one model schedule threads using only SCS.
Department of Computer Science, RLJIT 41
 Thread Scheduling

Pthread Scheduling
Pthread API that allows specifying either PCS or SCS during thread creation.
Pthreads identifies the following contention scope values:

1) PTHREAD_SCOPE_PROCESS schedules threads using PCS scheduling.

2) PTHREAD-SCOPE_SYSTEM schedules threads using SCS scheduling.

Department of Computer Science, RLJIT 42

 Process Synchronization

 Since processes frequently needs to communicate with other processes

therefore, there is a need for a well- structured communication, without using
interrupts, among processes.
 Consider this execution interleaving with “counter = 5” initially:
T0: producer execute register1 = counter {register1 = 5}
T1: producer execute register1 = register1 + 1 {register1 = 6}
T2: consumer execute register2 = counter {register2 = 5}
T3: consumer execute register2 = register2 - 1 {register2 = 4}
T4: producer execute counter = register1 {counter = 6 }
T5: consumer execute counter= register2 {counter = 4}
 Several processes access and manipulate the same data concurrently and the
outcome of the execution depends on the particular order. This is called “Race
condition.”
 To guard against the race condition ensure only one process at a time can be
manipulating the variable or data. To make such a guarantee processes need to
be synchronized in some way.

Department of Computer Science, RLJIT 43

 Critical-Section Problem

System consisting of n processes{p0,p1,…pn-1}

Each process has a segment of code called a “critical section”.
Critical-section is a segment-of-code in which a process may be
→ changing common variables
→ updating a table or
→ writing a file.
 Each process has a critical-section in which the shared-data is accessed.
 General structure of a typical process has following :
1) Entry-section :Requests permission to enter the critical-section.
2) Critical-section :Mutually exclusive in time i.e. no other process can
execute in its critical-section.
3) Exit-section :Follows the critical-section.
4) Remainder-section

Department of Computer Science, RLJIT 44

 Critical-Section Problem

System consisting of n processes{p0,p1,…pn-1}

Each process has a segment of code called a “critical section”.
Critical-section is a segment-of-code in which a process may be
→ changing common variables do {
→ updating a table or entry section
→ writing a file. critical section
 Each process has a critical-section in exit section
which the shared-data is accessed.
remainder section
 General structure of a typical process
has following : }while (TRUE);
Figure : General structure of a typical process
1) Entry-section :Requests permission to enter the critical-section.
2) Critical-section :Mutually exclusive in time i.e. no other process can
execute in its critical-section.
3) Exit-section :Follows the critical-section.
Department of Computer Science, RLJIT 45
4) Remainder-section
 Critical-Section Problem
Problem statement:
“Ensure that when one process is executing in its critical-section, no
other process is to be allowed to execute in its critical-section”.

Critical section problem must satisfy the three Requirements:

1. Mutual Exclusion - If process Pi is executing in its critical section,
then no other processes can be executing in their critical sections.
2. Progress - If no process is executing in its critical section and there
exist some processes that wish to enter their critical section, then the
selection of the processes that will enter the critical section next
cannot be postponed indefinitely.
3. Bounded Waiting - there exists a bound or limit on the number of
times that other processes are allowed to enter their critical sections
after a process has made a request to enter its critical section and
before that request is granted.

Department of Computer Science, RLJIT 46

 Critical-Section Problem
Two approaches used to handle critical-sections:
1. Preemptive Kernels: Allows a process to be preempted while it is
running in kernel-mode.
2. Non-preemptive Kernels: Does not allow a process running in kernel-
mode to be preempted.

Department of Computer Science, RLJIT 47

 Peterson’s Solution
 Classic software-based solution to the critical-section problem known as
“Peterson’s solution”
 Assume that the LOAD and STORE instructions are atomic; that is, cannot
be interrupted.
 The two processes share two variables:
 int turn;
 Boolean flag[2]
 The variable turn indicates whose turn it is to enter the critical section.
 If turn==i, then process Pi is allowed to execute in its critical section.
 The flag array is used to indicate if a process is ready to enter the critical
section.
 Ex. if flag[i] is true implies that process P is ready to enter its critical
i
section.

Department of Computer Science, RLJIT 48

 Peterson’s Solution

do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = FALSE;
remainder section
} while (TRUE);

• Mutual Exclusion is preserved

• The progress requirement is satisfied.
• The bounded-waiting requirement is met.

Department of Computer Science, RLJIT 49

 Synchronization Hardware
Software-based solutions such as Peterson’s are not guaranteed to work on modern
computer architectures. Simple hardware instructions can be used effectively in
solving the critical section problem. These solutions are based on the locking —
that is, protecting critical regions through the use of locks.
1 Hardware based Solution for Critical-section Problem
A lock is a simple tool used to solve the critical-section problem.
Race conditions are prevented by following restriction (Figure ).
 A process must acquire a lock before entering a critical-section.
 The process releases the lock when it exits the critical-section‖.

Figure : Solution to the critical-section problem

Department of Computer Science,using
RLJIT locks
50
 Synchronization Hardware
2 Hardware instructions for solving critical-section problem
• Modern systems provide special hardware instructions
→ to test &set modify the content of a word atomically or
→ to swap the contents of 2 words atomically.
• Atomic-operation means an operation that completes in its entirety without
interruption.

Department of Computer Science, RLJIT

51
 Semaphores

A semaphore is a synchronization-tool.
A semaphore(S) is an integer-variable that is accessed only through 2 atomic-
operations:
1) wait() and 2) signal().
 Definition of wait() is as follows:

wait (S) {
while S <= 0
; // no-op
S--;
}

Definition of signal() is as follows:

signal (S) {
S++;
} Department of Computer Science, RLJIT
52
 Semaphore Usage

Counting Semaphore
 The value of a semaphore can range over an unrestricted domain

Binary Semaphore
 The value of a semaphore can range only between 0 and 1.
 On some systems, binary semaphores are known as mutex locks, as they
are locks that provide mutual-exclusion.

Department of Computer Science, RLJIT

53
 Classical problems of synchronization

1) Bounded-Buffer Problem
2) Readers and Writers Problem
3) Dining-Philosophers Problem

Department of Computer Science, RLJIT

54
 Classical problems of synchronization

1) Bounded-Buffer Problem :
 The bounded-buffer problem is related to the producer consumer problem.
 There is a pool of n buffers, each capable of holding one item.
Shared-data
int n;
seamaphore mutex = 1;
seamaphore empty = n;
seamaphore full = 0;
where,
mutex provides mutual-exclusion for accesses to the buffer-pool.

empty counts the number of empty buffers.

full counts the number of full buffers.
 The symmetry between the producer and the consumer.
The producer produces full buffers for the consumer.
The consumer produces empty buffers for the producer.

Department of Computer Science, RLJIT

55
 Classical problems of synchronization
 The structure of the producer process
do {
// produce an item in nextp
wait (empty);
wait (mutex);
// add the item to the buffer
signal (mutex);
signal (full);
} while (TRUE);

Department of Computer Science, RLJIT

56
Classical problems of synchronization

 The structure of the consumer process

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

Department of Computer Science, RLJIT

57
 Classical problems of synchronization
2. Readers and Writers Problem
A data set is shared among a number of concurrent processes.
 Readers are processes which want to only read the database (DB).
 Writers are processes which want to update (i.e. to read & write) the DB.
Problem:
 Obviously, if 2 readers can access the shared-DB simultaneously without any
problems.
 However, if a writer & other process (either a reader or a writer) access the
shared-DB simultaneously, problems may arise.
Solution:
 The writers must have exclusive access to the shared-DB while writing to the
DB.
Shared-data
semaphore mutex, wrt;
int readcount;
where,
 mutex is used to ensure mutual-exclusion when the variable readcount is updated.
 wrt is common to both reader and writer processes. wrt is used as a mutual-
exclusion semaphore for theDepartment
writers. of Computer
wrt Science,
is also used by the first/last reader that
RLJIT
58
 Classical problems of synchronization
3. The Dining-Philosophers Problem:
Problem statement:
 There are 5 philosophers with 5 chopsticks
(semaphores).
 A philosopher is either eating (with two chopsticks) or
thinking.
 The philosophers share a circular table (Figure ).
 The table has
→ a bowl of rice in the centre and
→ 5 single chopsticks.
 From time to time, a philosopher gets hungry and tries
to pick up the 2 chopsticks that are closest to her.
 A philosopher may pick up only one chopstick at a time.
 Obviously, she cannot pick up a chopstick that is already in the hand of a neighbor.

 When hungry philosopher has both her chopsticks at the same time, she eats
without releasing her chopsticks.
 When she is finished eating, sheDepartment
puts down both of her chopsticks
of Computer Science, RLJIT
and starts
59
 Classical problems of synchronization
Problem objective: To allocate several resources among several
processes in a deadlock-free & starvation-free manner.
Solution:
 Represent each chopstick with a semaphore (Figure ).
 philosopher tries to grab a chopstick by executing a wait() on the semaphore.
 The philosopher releases her chopsticks by executing the signal() on the
semaphores.
 This solution guarantees that no two neighbors are eating simultaneously.
 The structure of Philosopher i
do {
wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
Department of Computer Science, RLJIT
} while (TRUE); 60
 Questions???
1. Define Thread.
2. Explain Multithreading models. Also list and explain the benefits of multithreaded
programming.
3. Consider the following set of processes with CPU burst time (in ms).
Process Arrival time Burst time
P1 0 6
P2 1 3
P3 2 1
P4 3 4

Processes Arrival Time Burst Time Priority

(m sec) (m sec)
P1 0 10 4
P2 3 5 2
P3 3 6 6
4. Consider
P4 the following
5 set of processes
4 given
Department in tableScience,
of Computer 3 RLJIT 61