Concurrency

Question 1

Bit per critical section

Answer 1

• for each critical session keep a variable to indicated whether a process is present
• set it to 1 on entry, 0 on exit
• test if bit=0 before we enter

issues:
▪ Testing at 0 and setting equal to 1 is not an atomic operation
→ process can be interrupted between testing and setting the bit
▪ if CS is occupied, then constant checking is required → busy waiting

Question 2

List the different versions of Dekker’s algorithm and why they wouldn’t work

Answer 2

1) global variable ‘turn’ to indicate which process may use CS next
-> initialization will favor one process

2) Keep variable for each process and check whether the other process has the intention to enter
-> if interrupted after while loop: no mutual exclusion

3) = 2nd attempt + switching assignment and while lines
-> both processes flag at same time = stuck in while loop => deadlock

4) 3rd attempt + pause
-> waiting time is not bounded

Final Solution:
Single variable ‘turn’ to indicate which process will be courteous when in conflict.

Question 3

What are the overall properties of Dekker’s algorithm?

Answer 3

• Busy waiting occurs
• Priority for process that entered the critical section least recently
• Not trivial to generalize to n processes

Question 4

What is Peterson’s Algorithm?

Answer 4

• Announce desire to enter the CS
• Set the turn to the other process
• Verify whether P1 does not have intention or is in the CS

Question 5

How is Peterson’s Algorithm altered for n processes

Answer 5

• Assume each process crosses n-1 phases before reaching the CS
• use variables:
• Flag[i] = phase of Pi
• Turn[j]: which was the last process in phase j

Question 6

What are the characteristics of the hardware-base solutions?

Answer 6

• prohibit interrupts during critical section
  -> disadvantageous for large critical sections
• machine instruction support (spinlock)
  ▪ Test-and-set: bit per critical section
  ▪ Exchange: bolt=1 and for each process key=0, exchange from (key, bolt) to key=1
  ▪ Cons: busy waiting, no guarantees against starvation

Question 7

What is Semaphore?

Answer 7

It is hardware-base solution introduced by Dijkstra.

• wait-function:
  counter - 1 -> counter < 0? -> block process

-signal function:
counter + 1 -> counter < 0? -> oldest process unblocked

Question 8

What is the Producers/Consumers Problem?

Answer 8

• One or more processes produce data and write it to a buffer
• One process access this data by reading it from the buffer

Challenges:
- Can only take something if it’s there
- may take it only once
- each produced item must have a new place

Question 9

What is a binary semaphore?

Answer 9

◦ Counter (count) only accepts 0 or 1 as a value
▪ waitB(s): check if counter is 1, if so we lower it, otherwise we block it
▪ signalB(s): if no processes are blocked, then counter to one, otherwise unblock one process (oldest)
◦ Binary semaphores as powerful as counting semaphores

Question 10

How do you get mutual exclusion with a semaphore?

Answer 10

◦ Semaphore per CS
▪ Initializing semaphore with one
▪ Entering Critical Section → wait(s)
▪ Exit CS → signal(s)
◦ wait(s) and signal(s) operations cannot be interrupted or occur simultaneously by different processes

Question 11

What is the Readers/Writers problem?

Answer 11

◦ A number of readers want to read data (e.g. catalog), but the data can be modified by writers
◦ Readers
▪ Simultaneous access is allowed
▪ No writers allowed
◦ Writers
▪ A maximum of one writer is always active
▪ No readers may be active

Question 12

Look at the Readers/Writers problem through Semaphores

Answer 12

◦ How many readers are active?
▪ r.count: variable the number of readers
▪ semaphore x enforcing mutual exclusion for r.count
◦ Stop writers when readers are active
▪ wsem: prevents writers as long as there are readers, if r.count decreases to zero then signal(wsem)
◦ Stop readers when writer is active
▪ wsem: if r.count to one then wait(wsem)