Exercise 10: Concurrency and Threading demonstration in Python

1. Find definitions for eight terms and concepts used in threaded programming:

1. Thread Synchronisation
Thread synchronization refers to the act of shielding against multithreading issues such as data- races, deadlocks and starvation. You have to determine properly the objects and methods to synchronize as failure to do so would lead to situations like deadlocks

2. Locks
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.

3. Deadlock
Deadlock is where the threads stop responding, each waiting for the other to complete

4. Semaphores
A semaphore is a protected variable or abstract data type that constitutes a classic method of controlling access by several processes to a common resource in a parallel programming environment. A semaphore generally takes one of two forms: binary and counting. A binary semaphore is a simple "true/false" (locked/unlocked) flag that controls access to a single resource. A counting semaphore is a counter for a set of available resources. Either semaphore type may be employed to prevent a race condition.

5. Mutex (mutual exclusion)
Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource. The critical section by itself is not a mechanism or algorithm for mutual exclusion. A program, process, or thread can have the critical section in it without any mechanism or algorithm which implements mutual exclusion.

6. Event
Events includes all sensor outputs or user actions (mouse clicks, key presses) or messages from other programs or threads.

7. Waitable timer
A waitable timer object is a synchronization object whose state is set to signaled when the specified due time arrives. There are two types of waitable timers that can be created: manual-reset and synchronization. A timer of either type can also be a periodic timer.



2. A simple demonstration of the threading module in Python (threaddemo.py) that uses both a lock and semaphore to control concurrency is by Ted Herman at the University of Iowa. The code and sample output below are worth a look. Report your findings.

threaddemo.py
# Create a bunch of threads, let each do some work, wait until all are done
import random
import threading
import time
# This takes about n/3 seconds to run (about n/3 clumps of tasks, times
# about 1 second per clump).
numtasks = 10
# no more than 3 of the 10 can run at once
# create a semaphore bounded up to 3
sema = threading.BoundedSemaphore(value=3)
# create a Read Lock
mutex = threading.RLock()
# running is a global variable to keep track
# of how many threads are running
running = 0
# the TestThread class is a subclass of threading.Thread,
# so it should supply the standard methods: run, ...
class TestThread(threading.Thread):
def run(self):
# tell python we access the global variable
global running
# introduce a random delay between 0 and 2
delay = random.random() * 2
print 'task', self.getName(), 'will run for', delay, 'sec'
# first, wait on the semaphore (limited to three threads)
sema.acquire()
# but only one of these three at a time should update
# the running variable
mutex.acquire()
running = running + 1
print running, 'tasks are running'
# release lock so another can update "running"
mutex.release()
# now sleep for a while (yawn....zzzzzzz)
time.sleep(delay)
# after wakeup, say we are done
print 'task', self.getName(), 'done'
# time to decrement "running"
mutex.acquire()
running = running - 1
print self.getName(), 'is finished.', running, 'tasks are running'
mutex.release()
# and finally, exit the group of three tasks
sema.release()
# main program: build and start all the threads
threads = []
# done in a function just for convenience
def starttasks():
for i in range(numtasks):
# show off Python's formatting feature
# by building a name for each thread
t = TestThread(name=""%i)
# add new name to list
threads.append(t)
# start thread
t.start()
starttasks()
print 'waiting for all tasks to complete'
# next statement waits for all threads to finish
for t in threads: t.join()
print 'all tasks done'


Here is the output window when you can run the threaddemo.py script:


PythonWin 2.3.2 (#49, Nov 13 2003, 10:34:54) [MSC v.1200 32 bit (Intel)] on win32.
Portions Copyright 1994-2001 Mark Hammond (mhammond@skippinet.com.au) - see 'Help/About PythonWin' for further copyright information.
>>> task will run for 0.120358615571 sec
1 tasks are running
task will run for 0.763990116379 sec
2 tasks are running
task will run for 0.207353153515 sec
3 tasks are running
task will run for 1.55806365714 sec
task will run for 0.776083733579 sec
task will run for 0.336440216469 sec
task will run for 1.55779500185 sec
task will run for 1.96896800957 sec
task will run for 1.57596561512 sec
task will run for 0.634052702735 sec
waiting for all tasks to complete
task done
is finished. 2 tasks are running
3 tasks are running
task done
is finished. 2 tasks are running
3 tasks are running
task done
is finished. 2 tasks are running
3 tasks are running
task done
is finished. 2 tasks are running
3 tasks are running
task done
is finished. 2 tasks are running
3 tasks are running
task done
is finished. 2 tasks are running
3 tasks are running
task done
is finished. 2 tasks are running
3 tasks are running
task done
is finished. 2 tasks are running
task done
is finished. 1 tasks are running
task done
is finished. 0 tasks are running
all tasks done

After examining the code and the output, I discovered that there are 10 threads (from 0 to 9) executed with no more than 3 tasks (controlled by semaphore) could run at the same time. Those threads are introduced with random delays (0-2 seconds) and the running variable is locked by the mutex until there are less than 3 tasks running and could release to other threads. The program ends until all threads are finished running.


Reference

C Sharp Corner. (2010). Multithreading Part 3: Thread Synchronization. Retrieved at 24 Apr, 2010, from http://www.c-sharpcorner.com/UploadFile/mmehta/Multithreading311162005045743AM/Multithreading3.aspx

Wikipedia. (2010). Semaphore (programming). Retrieved at 24 Apr, 2010, from http://en.wikipedia.org/wiki/Semaphore_(programming)

Wikipedia. (2010). Event-driven programming. Retrieved at 25 Apr, 2010, from http://en.wikipedia.org/wiki/Event-driven_programming

MSDN. (2010). Waitable Timer Object. Retrieved at 26 Apr, 2010, from http://msdn.microsoft.com/en-us/library/ms687012(VS.85).aspx

Wikipedia. (2010). Lock (computer science). Retrieved at 26 Apr, 2010, from http://en.wikipedia.org/wiki/Lock_(computer_science)