Assignment: Concurrent Programming, Part I

Every problem in this assignment requires concurrency. To write concurrent programs using semaphores, you'll use Python's standard library threading API. The easiest way to create a thread is to simply pass a Thread object the "target" function in which to start its execution. The following program shows how to create five separate threads that execute the method say_hello (with a different argument per thread).

from threading import Thread

def say_hello(id):
    print('hello from child', id)

for i in range(5):
    t = Thread(target=say_hello, args=[i])
    t.start()
    print('started thread', t.ident)

Output follows:

hello from child 0
started thread 4420612096
hello from child 1
started thread 4420612096
hello from child 2
started thread 4420612096
hello from child 3
started thread 4420612096
hello from child 4
started thread 4420612096

Note that the program exits only when all threads have terminated. This can be changed by configuring daemon threads, but you won't need them for this assignment.

It's also important to recognize that, due to the way in which threads are implemented in CPython (the "official" implementation of Python) threads will not actually exhibit parallelism, and instead be limited to running one at a time in the Python interpreter.

Due to the well known problems that can be caused by the accidental (or poorly planned) modification of global variables, Python doesn't allow assignment to global variables in non-global scopes without using the global keyword. Consider the following program:

count = 0

def foo():
    count += 1

foo()

When run, the following error is produced:

Traceback (most recent call last):
  File "./demo.py", line 6, in <module>
    foo()
  File "./demo.py", line 4, in foo
    count += 1
UnboundLocalError: local variable 'count' referenced before assignment

To get this to work, we would need to change foo as follows:

def foo():
    global count
    count += 1

But of course if foo were to be called from separate threads we would then need to protect it using a synchronization mechanism (e.g., a semaphore).

There are a number of synchronization mechanisms provided in the Python threading module, but we'll use only Semaphore objects. Creating a semaphore is performed in exactly the same way as demonstrated in the lecture slides. Unfortunately, the method names adopted by the Python library are acquire and release instead of wait and signal (we could create aliases for the latter, but won't bother). The following program demonstrates the use of semaphores to implement two-thread rendezvous, which was one of the first patterns we covered.

from threading import Thread, Semaphore
from time import sleep

aArrived = Semaphore(0)
bArrived = Semaphore(0)

def aBody():
    aArrived.release()
    print('a at rendezvous')
    bArrived.acquire()
    print('a past rendezvous')

def bBody():
    bArrived.release()
    print('b at rendezvous')
    aArrived.acquire()
    print('b past rendezvous')

tA = Thread(target=aBody)
tA.start()
sleep(1) # force thread A to block
tB = Thread(target=bBody)
tB.start()

Output follows:

a at rendezvous
b at rendezvous
b past rendezvous
a past rendezvous

Note that the program also demonstrates the use of sleep (in the time module) to insert some forced downtime in the main thread.

Some of the problems ask that you time your implementations for comparison. This is simple to do with the timeit module. The following program demonstrates how to use it to time the execution of a function that creates 10 threads and waits for them all to complete using Thread's join method.

from threading import Thread
from time import sleep
from timeit import Timer

def totime():
    ts = [Thread(target=thread_body, args=[0.1]) for i in range(10)]
    for t in ts: t.start()
    for t in ts: t.join()

def thread_body(n):
    sleep(n)

if __name__ == '__main__':
    timer = Timer(totime)
    print("Time: {:0.3f}s".format(timer.timeit(100)/100))

The output when run on my machine is:

Time: 0.104s

Note the following:

• the Timer constructor takes a (zero-argument) function to time
• the timeit method actually performs the timing, and takes as an argument the number of times to run the function to be timed; consequently, to come up with the time per run, it is necessary to divide by the same value (e.g., timer.timeit(100)/100)
• in order to measure how long it takes for all the threads spawned by the totime function to complete, it is necessary to call join on all the threads before returning

To make run-throughs (and corresponding output traces) of your concurrent programs more interesting, you will likely be injecting random sleeps at various points in your code. This will force threads to voluntarily yield control to each other at interesting places (where we might normally have to hope that the scheduler steps in and preempts them). The problem with using unpredictable random values, however, is that they make it harder for us to compare the results of one run to the next. If by chance a sequence of random numbers causes our threads to deadlock in one run, for instance, it's unlikely the same sequence would occur at the same time in the next run.

What we'd like is to be able to generate predictable sequences of random-ish numbers over and over again, to be replayed across runs. If you've already taken a course where basic number theory was covered, then you know this is a job for a pseudo-random number generator (PRNG). If this is a foreign concept to you, then do pay attention.

A PRNG generates values for us using a generator algorithm (which we won't discuss) and some initial state, typically known as a seed. A PRNG is necessarily a state machine, as each invocation returns a new pseudorandom value and requires that it track the new state (so to compute the next value). If a PRNG maintains k bits of state, then it is effectively capable of producing a sequence of \(2^k\) pseudorandom values, after which it will cycle back around to the beginning of the sequence.

Here's how we create and seed a PRNG in Python, using the random module.

import random
rng = random.Random()
rng.seed(100)

We can now obtain pseudorandom values:

print("Random float in range [0.0, 1.0):", rng.random())
print("Random int in range [0, 1000):   ", int(rng.random()*1000))
print("Random int in range [20, 30]:    ", rng.randint(20, 30))

Sample output follows:

Random float in range [0.0, 1.0): 0.1456692551041303
Random int in range [0, 1000):    454
Random int in range [20, 30]:     22

See http://docs.python.org/3/library/random.html for other methods supported by Random.

Perhaps more interestingly, we can produce the same sequence of pseudorandom values by re-seeding the PRNG:

rng = random.Random()
for i in range(5):
    rng.seed(100)
    print("Pass", i, ":", [rng.random() for _ in range(3)])

Output follows:

Pass 0 : [0.1456692551041303, 0.45492700451402135, 0.7707838056590222]
Pass 1 : [0.1456692551041303, 0.45492700451402135, 0.7707838056590222]
Pass 2 : [0.1456692551041303, 0.45492700451402135, 0.7707838056590222]
Pass 3 : [0.1456692551041303, 0.45492700451402135, 0.7707838056590222]
Pass 4 : [0.1456692551041303, 0.45492700451402135, 0.7707838056590222]

You'll use this pattern in your programs, typically by creating and seeding a PRNG, then proceeding to extract pseudorandom values from it, say, for use as arguments to sleep.

Take care that you only seed the PRNG once in your program (or once per thread – with differing seed values)! I've come across many a submission in the past where a PRNG was re-seeded with the same value on every iteration of a thread body/loop, effectively making it so the values produced are not at all random.

Down at the new IIT driving range, there are numerous tees at which golfers can be found practicing their swings. Each golfer will call for a bucket of N balls at a time, then proceed to swing at them one by one until empty, at which point he'll call for another bucket. When there are insufficient balls left in the central stash to satisfy a call for a bucket, all practice ceases and the retriever cart takes to the field to gather balls to replenish the supply.

Without synchronization in place, each golfer thread executes the following code:

# golfer
while True:
    stash -= N
    for i in range(0,N):
        balls_on_field += 1
        # simulate "swinging" here with random sleep

And the single retriever cart thread runs the following:

# cart
while True:
    stash += balls_on_field

Here are the synchronization rules:

• Golfers are allowed to swing concurrently.
• Golfers may not swing whilst the cart is out on the field.
• Golf balls are never lost (or gained)! They are either in the stash, on the field, or with a golfer.
• When the stash needs to be replenished, the cart thread has priority over golfers. I.e., golfers that are currently practicing will be interrupted after their current swing so the cart can head out.

Here is properly synchronized sample output for 3 golfers with an initial stash of 20 balls, and 5 balls per bucket:

$ python golfer.py 3 20 5
Golfer 0 calling for bucket
Golfer 0 got 5 balls; Stash = 15
Golfer 1 calling for bucket
Golfer 1 got 5 balls; Stash = 10
Golfer 1 hit ball 0
Golfer 2 calling for bucket
Golfer 2 got 5 balls; Stash = 5
Golfer 0 hit ball 0
Golfer 2 hit ball 0
Golfer 2 hit ball 1
Golfer 2 hit ball 2
Golfer 0 hit ball 1
Golfer 2 hit ball 3
Golfer 1 hit ball 1
Golfer 1 hit ball 2
Golfer 1 hit ball 3
Golfer 0 hit ball 2
Golfer 2 hit ball 4
Golfer 2 calling for bucket
Golfer 2 got 5 balls; Stash = 0
Golfer 2 hit ball 0
Golfer 1 hit ball 4
Golfer 1 calling for bucket
################################################################################
Stash = 0; Cart entering field
Cart done, gathered 14 balls; Stash = 14
################################################################################
Golfer 1 got 5 balls; Stash = 9
Golfer 1 hit ball 0
Golfer 2 hit ball 1
Golfer 0 hit ball 3
Golfer 2 hit ball 2
Golfer 0 hit ball 4
Golfer 2 hit ball 3
Golfer 0 calling for bucket
Golfer 0 got 5 balls; Stash = 4
Golfer 0 hit ball 0
Golfer 1 hit ball 1
Golfer 2 hit ball 4
Golfer 1 hit ball 2
Golfer 0 hit ball 1
Golfer 0 hit ball 2
Golfer 2 calling for bucket
################################################################################
Stash = 4; Cart entering field
Cart done, gathered 12 balls; Stash = 16
################################################################################
Golfer 2 got 5 balls; Stash = 11
Golfer 2 hit ball 0
Golfer 0 hit ball 3
Golfer 1 hit ball 3
Golfer 2 hit ball 1
Golfer 0 hit ball 4
...

Your simulation should allow the following items to be easily configurable:

• the initial size of the stash
• the number of balls per bucket (which determines (a) how many balls a golfer can hit before calling for another bucket and (b) when the cart needs to head out to the field)
• the number of golfer threads

You can assume the initial stash size is enough to satisfy all golfers concurrently.

At the Willowbrook ballroom they regularly run a "dance mixer" event, wherein N leaders line up on one side of the ballroom and M followers line up on the other. They pair up one by one then proceed to dance around the floor – after which they return to the end of their respective lines. This continues until the band leader decides it is time to switch dances and the pairing up of dancers is tapered off. When all dancers have made it off the dance floor and back to their respective lines, the music changes and the dancing begins again.

The system is to be simulated with the following threads:

1. The (single) band leader thread, which will execute the following unsynchronized code:

   for music in cycle(['waltz', 'tango', 'foxtrot']):
       start_music(music)
       end_music(music)
   

   Note that the band leader continually cycles through an arbitrary number of music styles. After the start_music call, couples may start forming and dancing on the floor. The end_music call may only be invoked when there are no couples on the floor (i.e., they have all lined back up). The code above uses cycle from itertools.

2. Leader threads, which will execute the following unsynchronized code:

   while True:
       enter_floor()
       dance()
       line_up()
   

3. Follower threads, which will execute the following unsynchronized code:

   while True:
       enter_floor()
       dance()
       line_up()
   

A leader is "paired up" with a follower by ensuring that they must both finish executing enter_floor before dancing. Upon dancing, the output should reflect which threads are actually paired up (see below). You may add parameters to the function calls above to help you achieve this. After dancing (concurrently), leaders and followers may line back up at their leisure.

Your code should allow for easy configuration of the number of leaders and followers, be starvation free, and allow for the maximum amount of concurrency. If necessary, you may wish to use the deque data structure employed previously in the MLFQ lab for communicating data between threads.

Sample output follows for a dance mixer with 2 leaders and 5 followers (the band leader is configured to change songs after every 5 seconds):

$ python mixer.py 2 5
** Band leader started playing waltz **
Follower 0 entering floor.
Leader 0 entering floor.
Leader 0 and Follower 0 are dancing.
Follower 1 entering floor.
Leader 1 entering floor.
Leader 1 and Follower 1 are dancing.
Leader 0 getting back in line.
Follower 2 entering floor.
Leader 0 entering floor.
Leader 0 and Follower 2 are dancing.
Leader 0 getting back in line.
Leader 0 entering floor.
Follower 3 entering floor.
Leader 0 and Follower 3 are dancing.
Follower 0 getting back in line.
Follower 1 getting back in line.
Leader 1 getting back in line.
Follower 2 getting back in line.
Follower 3 getting back in line.
Leader 0 getting back in line.
** Band leader stopped playing waltz **
** Band leader started playing tango **
Follower 4 entering floor.
Leader 1 entering floor.
Leader 1 and Follower 4 are dancing.
Leader 0 entering floor.
Follower 0 entering floor.
Leader 0 and Follower 0 are dancing.
Follower 4 getting back in line.
Leader 0 getting back in line.
Follower 1 entering floor.
Leader 0 entering floor.
Leader 0 and Follower 1 are dancing.
Leader 0 getting back in line.
Follower 0 getting back in line.
Leader 1 getting back in line.
Follower 1 getting back in line.
** Band leader stopped playing tango **
** Band leader started playing foxtrot **
Follower 2 entering floor.
Leader 0 entering floor.
Leader 0 and Follower 2 are dancing.
Leader 1 entering floor.
Follower 3 entering floor.
Leader 1 and Follower 3 are dancing.
Follower 3 getting back in line.
Leader 1 getting back in line.
Leader 0 getting back in line.
Follower 2 getting back in line.
** Band leader stopped playing foxtrot **
** Band leader started playing waltz **
...

For this problem you will implement and time different solutions to the dining philosophers problem. The solutions we discussed include:

1. The "footman" solution: where a single semaphore (a multiplex) limits the number of philosophers that can simultaneously "try" to dine.
2. The "left-handed philosopher" solution: where one of the philosophers attempts to pick up his left fork first (whilst all other philosophers start with their right).
3. The Tanenbaum solution: which has philosophers re-checking forks for neighboring, hungry philosophers.

The details/pseudo-code for each solution are in the lecture slides.

You are to craft a program that will apply each solution, in succession, to a specified number of philosophers and rounds of dining, then print out the amount of time to complete each simulation.

For instance, specifying 20 philosophers, with a requisite 1000 meals eaten by each, might produce the following results (times are made up):

$ python philosophers.py 20 1000
Running dining philosophers simulation: 20 philosophers, 1000 meals each
1. Footman solution, time elapsed:     32.1992s
2. Left-handed solution, time elapsed: 42.2290s
3. Tanenbaum's solution, time elapsed: 28.4939s

Each philosopher should eat/sleep for random amounts of time, but to be fair these durations should be consistent (i.e., generated using PRNGs with the same seed) across each algorithm.

After testing your solutions, discuss your results in a separate writeup. Are they what you expect? What accounts for the disparity in time elapsed for the different solutions?