Concurrency and Deadlock

Question 1

Problems with Concurrency

Answer 1

• The problem is simply sharing resources.
• Several threads/processes running at the same time.
• Using the same resources - accessing the same data
  structures/objects/devices
• Some resources can only be safely used by one thread at a time.
• e.g., readers accessing shared data while a writer is changing it
  or writers changing a resource simultaneously

Question 2

Race Concurrency

Answer 2

Any situation where the order of execution of threads can cause different results.

Question 3

Critical Sections

Answer 3

• A piece of code in which we only want one thread to be active at a time.
• Providing this is known as mutual exclusion.
• We need:
  1. a way of locking threads out of critical sections (should be as smallest possible)
  2. to guarantee threads are not kept waiting forever - starvation
• Starvation can be caused in different ways
• deadlock
• indefinite postponement - priority too low or just unlucky

Question 4

Software Solution

Answer 4

• We want something like this:
  lock
  critical section
  unlock
• We have a Boolean variable locked which is true if the critical section is being
  used by a thread. Initially locked is false.
• Simple lock procedure:
  while locked
  end
  locked = true
  And the unlock:
  locked = false

Question 5

Peterson’s Algorithm

Answer 5

• The two processes share two variables:
  flag = [false, false]
  # both false initially
  turn = 0
• turn indicates whose turn it is to enter the critical section
• flag[i] = true implies that process Pi is ready to enter the critical section
  lock: performed by thread i; j is the other thread
  flag[i] = true
  turn = j
  while (flag[j] && turn == j)
  end
  unlock: performed by thread i
  flag[i] = false

Question 6

Peterson’s Algorithm Properties

Answer 6

Two process solution
* Assume that the load and store machine-language instructions are atomic;
that is, cannot be interrupted
* Although useful for demonstrating an algorithm, Peterson’s Solution is not
guaranteed to work on modern architectures.
* To improve performance, processors and/or compilers may reorder
operations that have no dependencies

Question 7

Hardware Support

Answer 7

• Many systems provide hardware support for implementing the critical section code.
• Uniprocessors – could disable interrupts
• Currently running code would execute without preemption
• Generally, too inefficient on multiprocessor systems
• Operating systems using this not broadly scalable
• We will look at two forms of hardware support:
  1. Hardware instructions
  2. Atomic variables

Question 8

Hardware Instructions

Answer 8

testAndSet(lockVariable)
* returns the current value of the lockVariable
* and sets the lockVariable to true
* With this our lock can become
while (testAndSet(locked))
end
* unlock:
locked = false

Question 9

TEST-AND-SET

Answer 9

• Or equivalent atomic or indivisible instructions
• they appear uninterruptible - once started no other process can interfere until
  completed

Question 10

COMPARE-AND-SWAP

Answer 10

• There are 3 parameters for a CAS operation:
  1. A memory location V where value has to be replaced
  2. Old value A which was read by thread last time
  3. New value B which should be written over V

Question 11

CAS Properties

Answer 11

• CAS says - V should have the value A; if it does, put B there. i.e., the swap takes place only under this condition.
• Executed atomically - guarantees that the new value is calculated based on up-to-date information; if the value had been updated by another thread in the meantime, the write
  would fail.

Question 12

Atomic Variables

Answer 12

Provides atomic (uninterruptible) updates
on basic data types such as integers and booleans.

Question 13

Mutex Lock(Spinlock)

Answer 13

• Hardware solutions are complicated and generally inaccessible to application
  programmers
• OS designers build software tools to solve critical section problem
• Simplest is mutex lock
• Boolean variable indicating if lock is available or not
• Protect a critical section by
• First acquire() a lock
• Then release() the lock
• Calls to acquire() and release() must be atomic
• Usually implemented via hardware atomic instructions such as compare-and-swap.
• But this solution requires busy waiting

Question 14

Semaphore

Answer 14

Synchronization tool that provides more sophisticated ways for
processes to synchronize their activities.
* Semaphore S – integer variable (count of how many of a certain resource are available)
* Can only be accessed via two atomic operations
* wait() and signal()
* Originally called P() and V()(or POSIX wait and post).
* Definition of the wait() operation
wait(S) {
while (S < 1)
; // busy wait
S–;
}
* Definition of the signal() operation
signal(S) {
S++;
}
* To get a resource the thread calls wait() on the semaphore.
To return the resource the thread calls signal().
* With semaphores we can solve various synchronization problems

Question 15

Counting Semaphore

Answer 15

Integer value can range over an unrestricted domain

Question 16

Binary Semaphore

Answer 16

• Integer value can range only between 0 and 1
• Same as a mutex lock
• Can implement a counting semaphore S as a binary semaphore

Question 17

Implementing Semaphores

Answer 17

The suspend
operation places a process into a waiting queue associated with the
semaphore, and the state of the process is switched to the waiting state.
signal(S):
if anything waiting on S then
start the first process on the S queue
else
S = S + 1
wait(S):
if S < 1 then
put this process on the S queue
else
S = S - 1
another common alternative is:
signal(S):
S = S + 1
if S < 1 then
start the first process on the S queue
wait(S):
S = S - 1
if S < 0 then
put this process on the S queue

Question 18

Readers/Writer’s Problem

Answer 18

There are a number of threads. In order to ensure the integrity of the shared data being both read from and written to we need to allow:
* only one writer has access to the data at a time
* if a writer is active there must be no active readers
* if no writer is active there can be multiple readers

Question 19

Reader/Writer Problem Solutions

Answer 19

Three types of solutions:
1. writer preferred - waiting writers go before waiting readers
2. reader preferred – waiting readers go before waiting writers
3. neither preferred - try to treat readers and writers fairly (a simple queue is not good enough we want parallel readers whenever possible)
* Both 1 and 2 can lead to indefinite postponement.

Question 20

Monitors

Answer 20

An object which only allows one thread to
be executing inside it. It has:
* the shared resource - it can only be accessed by the monitor
* publicly accessible procedures - they do the work
* a queue to get in
* a scheduler - which thread gets access next
* local state - not visible externally except via access procedures
* initialization code
* condition variables

Question 21

Condition Variables

Answer 21

A condition variable is a queue which can hold threads. We have wait and signal operations
on condition variables.

conditionVariable.wait puts the current thread to sleep on the corresponding queue
conditionVariable.signal wakes up one thread from the queue (if there are any waiting)
* No internal state (or count) is kept of how many signals and waits there have been.
* Simpler than the similar instructions on semaphores.
* A signal with nothing waiting does nothing.
* A wait always puts a thread to sleep. So, avoids busy-waiting.

Question 22

Priority Inversion

Answer 22

• When you have priorities on processes and a locking mechanism you can get
  priority inversion.
• Lower priority processes with a lock can force higher priority processes to wait.
  But because they are low priority they may not run very frequently.
• Particularly important in real-time systems.
• Solved with priority inheritance

Question 23

Priority Inheritance

Answer 23

When a higher priority process blocks waiting
for a resource, the process with the resource is temporarily given the priority of the blocked process. The high priority process will now only wait during the critical section.

Question 24

Lock-Free Algorithms

Answer 24

• Another approach is to code so that we don’t need locks.
• This is difficult – use standard lock free libraries of stacks, queues,
  sets, etc.
• They usually rely on compare and swap type instructions

CAS(mem location, old value, new value)

Question 25

Livelock

Answer 25

An endless loop in program execution.
It occurs when a process repeats itself, because it continues to receive erroneous information.

Question 26

Rules of Concurrent Code

Answer 26

1. Don’t do it, if you can avoid it.
2. If you must do it, don’t share data across threads.
3. If you must share data across threads, don’t share mutable data.
4. If you must share mutable data across threads, synchronize access to that data.

Question 27

Takeaway

Answer 27

1. Assume that threads can be interleaved at any point. Protect all access to shared
   data with synchronization.
2. Do not require that threads be interleaved at some point. If you need guaranteed
   progression between different threads you must code it explicitly using
   synchronization.
3. Message passing is safer because of no shared state.
4. Most languages have libraries to help produce concurrent programs. Use them.