Machine problem 3: Synchronization with Semaphores

Objectives

For this machine problem you will be writing some concurrent programs using Python's threading library, which includes a Semaphore class that you will use for synchronization.

Tutorial: concurrency in Python (and misc. APIs)

Threading

To write concurrent programs using semaphores, you'll use Python's standard library threading API. The easiest way to create a thread is pass a Thread object the "target" function in which to start its execution. The following program creates five threads that execute the function say_hello, each time with a different argument.

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

The program exits only when all threads have terminated. This can be changed by using daemon threads, but you won't need them for this machine problem.

Using global variables

To help prevent the accidental use of global variables, Python requires you to use the global keyword to explicitly identify them in non-global scopes. 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 fix this, we need to use global:

def foo():
    global count
    count += 1

Of course, if foo were to be called from separate threads we would need to protect it using a synchronization mechanism, e.g., the semaphore.

Using semaphores

There are several synchronization constructs provided in the Python threading module, but we'll use only Semaphore objects.

While creating and initializing a semaphore is performed in exactly the same way as demonstrated in the lecture slides, the method names adopted by the Python library are acquire and release instead of wait and signal. The following program implements two-thread rendezvous with semaphores:

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 uses sleep (in the time module) to insert some forced downtime in the main thread.

Timing

Some of the following problems require you to do some timing-based comparisons. This is fairly simple, using Python's timeit module. The following program uses timeit to time the execution of a function that creates 10 threads and waits for them all to complete:

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:

Pseudo-random numbers

To make run-throughs of your concurrent programs more interesting, you will likely inject random sleeps to prompt threads to yield control to each other. The problem with using unpredictable random values, however, is that they make it harder for us to compare the results of different runs.

What we really need is to be able to generate reproducible sequences of random numbers. 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).

A PRNG generates values for us using a generator algorithm and some initial state known as a seed. If we use the same seed, we get the same "random" 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 the documentation for other methods supported by Random.

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)!

Synchronization Problems

1. At the IIT Driving range (15 points)

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 hit 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, the golfer and retriever cart threads can be described as follows:

# golfer
while True:
    stash -= N                # call for bucket
    for i in range(0,N):      # for each ball in bucket,
        balls_on_field += 1   #   swing (maybe simulate with a random sleep)

# cart
while True:
    stash += balls_on_field   # collect balls and deposit in stash

You are to implement a properly synchronized simulation for this problem in Python using Semaphores, and -- if you wish -- the LightSwitch construct. A separate thread should be created for the cart and each golfer. Your simulation should allow the following items to be easily configurable:

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

Sample output for 3 golfers, an initial stash of 20, and 5 balls per bucket follows:

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 implementation should obey the following rules:

2. Dance mixer (15 points)

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.

You will simulate this by writing synchronization code for the following:

  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)
    

    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, 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.

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

** 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 **
...

3. Dining philosophers (15 points)

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 write 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, briefly discuss your results in a separate text file. Are they what you expect? What accounts for the disparity in time elapsed for the different solutions?

Submission

Your submission for this machine problem will consist of a single archive file (zip or tar.gz) submitted via Blackboard containing the following files:

All ".py" scripts should be runnable with the python command line interpreter.

Your code does not need to be over-documented, but if your implementation is particularly opaque or clever I ask that you include a few well-placed comments to help explain. An interview may be requested if I can't decipher your work.

Please do include instructions on how to run your code in a header comment atop each program file. Unless you specify otherwise, I will use the latest stable Python 3 interpreter to run your programs.