Exam 2 (Concurrency and Deadlocks)

Question 1

Why do we need synchronization?

Answer 1

Activities share resources, and it’s important to coordinate their progress.

Question 2

What type of coordination is this: John and Mary are printing 10 page documents on the same printer. We don’t want their pages to interleave!

Answer 2

Exclusion

Question 3

What type of coordination is this: John and Mary are sharing a bank account. John deposits $10. Mary should be allowed to withdraw only after this deposit.

Answer 3

Ordering

Question 4

Types of shared resources

Answer 4

Physical (terminal, disk, network, …) or Logical (files, sockets, memory, …)

Question 5

What is mutual exclusion?

Answer 5

Think of race conditions… If two threads are accessing the same array, we need to block one from executing while the other is executing to avoid a race condition.

Question 6

What is a critical section?

Answer 6

The set of instructions where race conditioning could occur, in the event of an array it would be Load, Add, Store.

Question 7

Implementing Mutex: Disable Interrupts

Answer 7

Stops scheduling other threads. It’s easy to implement, but we don’t want to give that much power to users, it doesn’t work on a multiprocessor, and disables multiprogramming even when there is no critical section access.

Question 8

Implementing Mutex: Problem with Software Solutions

Answer 8

We can have a variable to indicate a thread accessing the critical section, but this has a race condition too so it doesn’t really work!

Question 9

Implementing Mutex: What we want

Answer 9

Mutual exclusion (correctness), Granting access to a critical section if not being used (progress), no process should have to wait forever (bounded waiting).

Question 10

Implementing Mutex: Strict Alternation

Answer 10

Uses a variable to indicate turns. Seems to work, but requires threads to alternate, and doesn’t meet the progress requirement. We can fix this by having an array of “flags”, but both can set their flags to true and wait indefinitely.

Question 11

Implementing Mutex: Peterson’s Algorithm

Answer 11

Each algorithm has two variables, for flag and turn. If flag is true, a process wants to enter Critical Section. This is allowed to happen when the other process doesn’t want to enter, or if the process has priority.

Question 12

Implementing Mutex: Multiple Thread Solution

Answer 12

Use the Bakery Algorithm. Every thread has a unique id, like tickets in a bakery. They are serviced in increasing tickets, and need to use some kind of tie breaker.

Question 13

Implementing Mutex: Specialized Instructions

Answer 13

Functions are still atomic, we can use Bool Test&Set or Swap. Parameters are passed by reference.

Question 14

Test&Set

Answer 14

Have a boolean indicating TRUE before entering the critical section, and then set it to FALSE when finished. Machine instruction will end execution.

Question 15

Swap

Answer 15

Swaps a key and the lock. When exiting the CS, lock becomes false.

Question 16

Spinning vs Blocking

Answer 16

Blocking can make it so that we can make sure we don’t unnecessarily occupy CPU cycles. It’s the job of the process changing the condition to move the process from blocked to ready.

Question 17

Example of Blocking Implementations

Answer 17

Mutex_Lock and Mutex_Unlock from pthread library - remember P1

Question 18

C_wait and C_signal

Answer 18

Used to implement synchronization on a multithreaded processor. A thread blocked on C_wait will return when another performs a C_signal. C_wait will have to be inside a mutex_lock.

Question 19

Semaphores

Answer 19

A data type which we can use P and V on, P is analogous to waiting, V is analogous to signaling. A Semaphore will have a count that is incremented on a V call and decremented on a P call. We will block the Semaphore if the count is negative.

Question 20

Bounded Buffer problem

Answer 20

A queue of finite size implemented as an array, which could cause race conditions when accessed by multiple threads. Also, need to wait when appending to buffer when it is full or removing when empty.

Question 21

Readers-Writers Problem

Answer 21

There’s a database with many readers and writers. When a reader is accessing it, there could be other readers. When a writer is accessing, there can’t be any other reader or writer.

Question 22

Dining Philosophers Problem

Answer 22

Philosophers alternate between thinking and eating, when eating they need both chopsticks, but a philosopher can only pick up one at a time. After eating, the philosopher puts down both chopsticks. This problem can lead to a DEADLOCK.

Question 23

Deadlocks

Answer 23

A set of processes is deadlocked when each process in the set is waiting for an event that only another process in the set can cause.

Question 24

Potential Deadlock Events

Answer 24

Waiting for a critical section, waiting for a condition to change, waiting for a physical resource.

Question 25

Conditions for a deadlock

Answer 25

Mutual exclusion, Hold and wait, No preemption, Circular wait.

Question 26

Hold and wait

Answer 26

A process needs to be holding at least one resource and waiting for at least one resource held by another.

Question 27

Circular wait

Answer 27

A set of processes must exist so that P1 waits on P2, P2 on P3, etc…

Question 28

Resource Allocation Graph

Answer 28

Vertices are processes and resources, edges are assignments and requests. For every resource, there can be many instances, and a requesting process can be granted if any of them are available.

Question 29

Handling Deadlocks

Answer 29

We could ignore them, detect and recover, avoid them, or prevent them.

Question 30

Deadlock Prevention

Answer 30

We can configure this at Hold and Wait, where at most one resource can be held/requested at any time; and ensure all requests are made at the same time. We could also use circular wait, and make sure requests are made in increasing or decreasing order, and make sure we are never holding a lower numbered resource when requesting a higher numbered one.

Question 31

Deadlock Avoidance

Answer 31

Avoid an action that leads to a deadlock, make sure we only transition from one safe state to another. Conservative approach.

Question 32

Safe State

Answer 32

Calculate allocable resources and required resources by a sequence of processes to determine if the state is safe. This is called a reduction sequence.

Question 33

Unsafe State

Answer 33

If there are less free units of a resource than number of processes in a sequence, the transition to that state will not occur by design.

Question 34

Banker’s Algorithm for Deadlock Avoidance

Answer 34

When a request is made, we check to see if there is at least one sequence of moves that can lead to a safe state, If one does not exist, we make the request wait.

Question 35

Deadlock Detection and Recovery

Answer 35

If there is only one instance of each resource, then a cycle in the allocation graph is sufficient to detect a deadlock.

Question 36

What to do when we detect a deadlock?

Answer 36

Preempt the resources, kill the processes, and checkpoint processes periodically, returning to the previous checkpoint on detection.