# CS 100 Lab 4: Concurrent Programming

For this lab you will be analyzing a number of different concurrent programs (each consisting of some initial values and the bodies of 2 or more threads) alongside their output. Assume that the bodies of the threads (the separate functions) run concurrently and non-deterministically. Most of the exercises will ask you to determine how they arrived at their output (which may be unexpected), and some may also ask you to make suggestions as to how to "fix" their behavior.

When explaining how they arrive at the given output, you may either sketch a diagram and/or outline the sequence in English (e.g., "First, t1 runs lines number W-X, then t2 runs line number Y-Z, etc.").

## Exercise 1

``````x = 0

1   def t1():
2       a = x
3       a = a + 5
4       x = a

5   def t2():
6       b = x
7       b = b + 10
8       x = b
``````
• After running the above two threads to completion, the value of `x` is 5 (we expect `x` to be 15). How is this possible?

## Exercise 2

``````x = 5
y = 10
z = 30
sum = 0

1   def t1():
2       val1 = sum + x
3       sum = val1

4   def t2():
5       val2 = sum + y
6       sum = val2

7   def t3():
8       val3 = sum + z
9       sum = val3
``````
• (Part 1) After running the above three threads to completion, the value of `sum` is 15 (we expect it to be 45). How is this possible?

• (Part 2) After running the above three threads to completion, the value of `sum` is 30 (we expect it to be 45). How is this possible?

## Exercise 3

``````x = 0
turn = ''

1   def t1():
2       turn = 't1'
3       while turn == 't2':
4           pass
5       a = x
6       a = a + 5
7       x = a
8       turn = 't2'

9   def t2():
10      turn = 't2'
11      while turn == 't1':
12          pass
13      b = x
14      b = b + 10
15      x = b
16      turn = 't1'
``````
• The idea behind this setup is that the two threads will both try to set `turn` to itself, but since only one thread will win and drop through the loop, the other will have to wait for the first to complete. After executing the above threads to completion, however, the value of `x` is 10 (we expect it to be 15). How is this possible?

## Exercise 4

``````s = ''
t1_state = 'Running'
t2_state = 'Waiting'

1   def t1():
2       for _ in range(5):
3           while t2_state == 'Running':
4               pass
5           t1_state = 'Running'
6           s = s + '@'
7           t1_state = 'Waiting'

8   def t2():
9       for _ in range(5):
10          while t1_state == 'Running':
11              pass
12          t2_state = 'Running'
13          s = s + '#'
14          t2_state = 'Waiting'
``````
• (Part 1) The goal of this setup is that the two threads will alternate between running the bodies of their `for` loops, resulting in the final value of `s` being a series of alternating `'@'` and `'#'` characters. Indeed, after executing the above threads to completion we find the value of `s` is `'@#@#@#@#@#'`. Explain how this happens.

• (Part 2) When we run the code again, however, the value of `s` is now `'@@@@@#####'`. How is this possible?

• (Part 3) Can you make changes to the code so that we will always get the desired behavior (i.e., so that the value of `s` at the end is always `'@#@#@#@#@#'`)? Note that you should not alter the loop structure nor add/remove/modify lines that change the variable `s`. Your changes should only affect how `t1_state` and `t2_state` are used.

## Submission

When you're done with your writeup, submit it as a PDF or plain text file.