Chapter 5 – Asynchronous Concurrent

Execution
Outline
5.1 Introduction
5.2 Mutual Exclusion
5.2.1 Java Multithreading Case Study
5.2.2 Critical Sections
5.2.3 Mutual Exclusion Primitives
5.3 Implementing Mutual Exclusion Primitives
5.4 Software Solutions to the Mutual Exclusion Problem
5.4.1 Dekker’s Algorithm
5.4.2 Peterson’s Algorithm
5.4.3 N-Thread Mutual Exclusion: Lamport’s Bakery Algorithm
5.5 Hardware Solutions to the Mutual Exclusion Problem
5.5.1 Disabling Interrupts
5.5.2 Test-and-Set Instruction
5.5.3 Swap Instruction

 2004 Deitel & Associates, Inc. All rights reserved.

 Chapter 5 – Asynchronous Concurrent
Execution
Outline (continued)
5.6 Semaphores
5.6.1 Mutual Exclusion with Semaphores
5.6.2 Thread Synchronization with Semaphores
5.6.3 Counting Semaphores
5.6.4 Implementing Semaphores

 2004 Deitel & Associates, Inc. All rights reserved.

 Objectives

• After reading this chapter, you should understand:

– the challenges of synchronizing concurrent processes and
threads.
– critical sections and the need for mutual exclusion.
– how to implement mutual exclusion primitives in software.
– hardware mutual exclusion primitives.
– semaphore usage and implementation.

 2004 Deitel & Associates, Inc. All rights reserved.

 5.1 Introduction

• Concurrent execution
– More than one thread exists in system at once
– Can execute independently or in cooperation
– Asynchronous execution
• Threads generally independent
• Must occasionally communicate or synchronize
• Complex and difficult to manage such interactions

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2 Mutual Exclusion

• Problem of two threads accessing data simultaneously

– Data can be put in inconsistent state
• Context switch can occur at anytime, such as before a thread
finishes modifying value
– Such data must be accessed in mutually exclusive way
• Only one thread allowed access at one time
• Others must wait until resource is unlocked
• Serialized access
• Must be managed such that wait time not unreasonable

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java

• Producer/Consumer relationship
– One thread creates data to store in shared object
– Second thread reads data from that object
• Large potential for data corruption if unsynchronized

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.1 Buffer interface used in producer/consumer examples.

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.2 Producer class represents the producer thread in a
producer/consumer relationship. (1 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.2 Producer class represents the producer thread in a
producer/consumer relationship. (2 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.2 Producer class represents the producer thread in a
producer/consumer relationship. (3 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.3 Consumer class represents the consumer thread in a
producer/consumer relationship. (1 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.3 Consumer class represents the consumer thread in a
producer/consumer relationship. (2 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.3 Consumer class represents the consumer thread in a
producer/consumer relationship. (3 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.4 UnsynchronizedBuffer class maintains the shared integer that is
accessed by a producer thread and a consumer thread via methods set and get. (1 of
2)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.4 UnsynchronizedBuffer class maintains the shared integer that is
accessed by a producer thread and a consumer thread via methods set and get. (2 of
2)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.5 SharedBuffer class enables threads to modify a
shared object without synchronization. (1 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.5 SharedBuffer class enables threads to modify a
shared object without synchronization. (2 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.5 SharedBuffer class enables threads to modify a
shared object without synchronization. (3 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.1 Java Multithreading Case Study, Part II:
A Producer/Consumer Relationship in Java
Figure 5.5 SharedBuffer class enables threads to modify a
shared object without synchronization. (4 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.2 Critical Sections

• Most code is safe to run concurrently

• Sections where shared data is modified must be
protected
– Known as critical sections
– Only one thread can be in its critical section at once
• Must be careful to avoid infinite loops and blocking inside a
critical section

 2004 Deitel & Associates, Inc. All rights reserved.

 5.2.3 Mutual Exclusion Primitives

• Indicate when critical data is about to be accessed

– Mechanisms are normally provided by programming language or
libraries
– Delimit beginning and end of critical section
• enterMutualExclusion
• exitMutualExclusion

 2004 Deitel & Associates, Inc. All rights reserved.

 5.3 Implementing Mutual Exclusion Primitives

• Common properties of mutual exclusion primitives

– Each mutual exclusion machine language instruction is executed
indivisibly
– Cannot make assumptions about relative speed of thread
execution
– Thread not in its critical section cannot block other threads from
entering their critical sections
– Thread may not be indefinitely postponed from entering its
critical section

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm

• First version of Dekker’s algorithm

– Succeeds in enforcing mutual exclusion
– Uses variable to control which thread can execute
– Constantly tests whether critical section is available
• Busy waiting
• Wastes significant processor time
– Problem known as lockstep synchronization
• Each thread can execute only in strict alternation

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.6 Mutual exclusion implementation – version 1 (1 of 2).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.6 Mutual exclusion implementation – version 1 (2 of 2).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm

• Second version
– Removes lockstep synchronization
– Violates mutual exclusion
• Thread could be preempted while updating flag variable
– Not an appropriate solution

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.7 Mutual exclusion implementation – version 2 (1 of 3).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.7 Mutual exclusion implementation – version 2 (2 of 3).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.7 Mutual exclusion implementation – version 2 (3 of 3).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm

• Third version
– Set critical section flag before entering critical section test
• Once again guarantees mutual exclusion
– Introduces possibility of deadlock
• Both threads could set flag simultaneously
• Neither would ever be able to break out of loop
– Not a solution to the mutual exclusion problem

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.8 Mutual exclusion implementation – version 3 (1 of 2).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.8 Mutual exclusion implementation – version 3 (2 of 2).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm

• Fourth version
– Sets flag to false for small periods of time to yield control
– Solves previous problems, introduces indefinite postponement
• Both threads could set flags to same values at same time
• Would require both threads to execute in tandem (unlikely but
possible)
– Unacceptable in mission- or business-critical systems

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.9 Mutual exclusion implementation – version 4 (1 of 4).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.9 Mutual exclusion implementation – version 4 (2 of 4).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.9 Mutual exclusion implementation – version 4 (3 of 4).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.9 Mutual exclusion implementation – version 4 (4 of 4).

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm

• Dekker’s Algorithm
– Proper solution
– Uses notion of favored threads to determine entry into critical
sections
• Resolves conflict over which thread should execute first
• Each thread temporarily unsets critical section request flag
• Favored status alternates between threads
– Guarantees mutual exclusion
– Avoids previous problems of deadlock, indefinite postponement

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.10 Dekker’s Algorithm for mutual exclusion. (1 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.10 Dekker’s Algorithm for mutual exclusion. (2 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.10 Dekker’s Algorithm for mutual exclusion. (3 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.1 Dekker’s Algorithm
Figure 5.10 Dekker’s Algorithm for mutual exclusion. (4 of 4)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.2 Peterson’s Algorithm

• Less complicated than Dekker’s Algorithm

– Still uses busy waiting, favored threads
– Requires fewer steps to perform mutual exclusion primitives
– Easier to demonstrate its correctness
– Does not exhibit indefinite postponement or deadlock

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.2 Peterson’s Algorithm
Figure 5.11 Peterson’s Algorithm for mutual exclusion. (1 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.2 Peterson’s Algorithm
Figure 5.11 Peterson’s Algorithm for mutual exclusion. (2 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.2 Peterson’s Algorithm
Figure 5.11 Peterson’s Algorithm for mutual exclusion. (3 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.3 N-Thread Mutual Exclusion:
Lamport’s Bakery Algorithm

• Applicable to any number of threads

– Creates a queue of waiting threads by distributing numbered
“tickets”
– Each thread executes when its ticket’s number is the lowest of all
threads
– Unlike Dekker’s and Peterson’s Algorithms, the Bakery
Algorithm works in multiprocessor systems and for n threads
– Relatively simple to understand due to its real-world analog

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.3 N-Thread Mutual Exclusion:
Lamport’s Bakery Algorithm
Figure 5.12 Lamport’s Bakery Algorithm. (1 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.3 N-Thread Mutual Exclusion:
Lamport’s Bakery Algorithm
Figure 5.12 Lamport’s Bakery Algorithm. (2 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.4.3 N-Thread Mutual Exclusion:
Lamport’s Bakery Algorithm
Figure 5.12 Lamport’s Bakery Algorithm. (3 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5 Hardware Solutions to the Mutual Exclusion Problem

• Implementing mutual exclusion in hardware

– Can improve performance
– Can decreased development time
• No need to implement complex software mutual exclusion
solutions like Lamport’s Algorithm

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.1 Disabling Interrupts

• Disabling interrupts
– Works only on uniprocessor systems
– Prevents the currently executing thread from being preempted
– Could result in deadlock
• For example, thread waiting for I/O event in critical section
– Technique is used rarely

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.2 Test-and-Set Instruction

• Use a machine-language instruction to ensure that

mutual exclusion primitives are performed indivisibly
– Such instructions are called atomic
– Machine-language instructions do not ensure mutual exclusion
alone—the software must properly use them
• For example, programmers must incorporate favored threads to
avoid indefinite postponement
– Used to simplify software algorithms rather than replace them
• Test-and-set instruction
– testAndSet(a, b) copies the value of b to a, then sets b to true
– Example of an atomic read-modify-write (RMW) cycle

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.2 Test-and-Set Instruction
Figure 5.13 testAndSet instruction for mutual exclusion. (1 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.2 Test-and-Set Instruction
Figure 5.13 testAndSet instruction for mutual exclusion. (2 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.2 Test-and-Set Instruction
Figure 5.13 testAndSet instruction for mutual exclusion. (3 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.3 Swap Instruction

• swap(a, b) exchanges the values of a and b

atomically
• Similar in functionality to test-and-set
– swap is more commonly implemented on multiple architectures

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.3 Swap Instruction
Figure 5.14 swap instruction for mutual exclusion. (1 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.3 Swap Instruction
Figure 5.14 swap instruction for mutual exclusion. (2 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.5.3 Swap Instruction
Figure 5.14 swap instruction for mutual exclusion. (3 of 3)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6 Semaphores

• Semaphores
– Software construct that can be used to enforce mutual exclusion
– Contains a protected variable
• Can be accessed only via wait and signal commands
• Also called P and V operations, respectively

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6.1 Mutual Exclusion with Semaphores

• Binary semaphore: allow only one thread in its

critical section at once
– Wait operation
• If no threads are waiting, allow thread into its critical section
• Decrement protected variable (to 0 in this case)
• Otherwise place in waiting queue
– Signal operation
• Indicate that thread is outside its critical section
• Increment protected variable (from 0 to 1)
• A waiting thread (if there is one) may now enter

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6.1 Mutual Exclusion with Semaphores
Figure 5.15 Mutual exclusion with semaphores.

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6.2 Thread Synchronization with Semaphores

• Semaphores can be used to notify other threads that

events have occurred
– Producer-consumer relationship
• Producer enters its critical section to produce value
• Consumer is blocked until producer finishes
• Consumer enters its critical section to read value
• Producer cannot update value until it is consumed
– Semaphores offer a clear, easy-to-implement solution to this
problem

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6.2 Thread Synchronization with Semaphores
Figure 5.16 Producer/consumer relationship implemented with semaphores. (1 of 2)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6.2 Thread Synchronization with Semaphores
Figure 5.16 Producer/consumer relationship implemented with semaphores. (2 of 2)

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6.3 Counting Semaphores

• Counting semaphores
– Initialized with values greater than one
– Can be used to control access to a pool of identical resources
• Decrement the semaphore’s counter when taking resource from
pool
• Increment the semaphore’s counter when returning it to pool
• If no resources are available, thread is blocked until a resource
becomes available

 2004 Deitel & Associates, Inc. All rights reserved.

 5.6.4 Implementing Semaphores

• Semaphores can be implemented at application or

kernel level
– Application level: typically implemented by busy waiting
• Inefficient
– Kernel implementations can avoid busy waiting
• Block waiting threads until they are ready
– Kernel implementations can disable interrupts
• Guarantee exclusive semaphore access
• Must be careful to avoid poor performance and deadlock
• Implementations for multiprocessor systems must use a more
sophisticated approach

 2004 Deitel & Associates, Inc. All rights reserved.