Introduction

Next: Semaphores

Execution model

Exercise

Assuming that Bob is willing to follow simple instructions, is there any way you can guarantee that tomorrow you will eat lunch before Bob?

Come up with this scheme: Bob can only eat lunch after he gets confirmation from me. If I haven’t eaten lunch, he can’t either. If I have eaten lunch, the next time he calls, I will say he can eat lunch.

Shared variables

Concurrent writes

Exercise

Using this example:

# Thread A
x = 5
print(x)

# Thread B
x = 7

1. What path yields output 5 and final value 5?

If B runs to completion first, then A runs, it will print 5 and x will be 5.

2. What path yields output 7 and final value 7?

If A runs past the x = 5 line, then B runs, then A takes over, the print will be 7 with final value 7.

3. Is there a path that yields output 7 and final value 5? Can you prove it?

Because the print is blocked by the 5, there is only a way to get 7s and 5s, so no, this is not possible.

Concurrent updates

Exercise

Suppose that 100 threads run the following program concurrently:

for i in range(100):
    temp = count
    count = temp + 1

1. What is the largest possible value of count after all threads have completed?

Each thread is serialized, in which case, 100 threads increment a variable 100 times each, so 10000.

2. What is the smallest possible value?

The smallest possible value is 100. Each thread would read a stale value that is dropped by the next thread, so in effect it runs the loop once, which would get it up to 100.

Hint: The first question is easy; the second is not.

Mutual exclusion with messages

Exercise

Figure out a system of message passing (phone calls) that enforces these restraints. Assume there are no clocks, and you cannot predict when lunch will start or how long it will last. What is the minimum number of messages that is required?

You need two messages, one to confirm the start of lunch, one to confirm the end of lunch.