Homework 10: Performance of Concurrent Programs
In this homework, we'll study the relative performance of several synchronization methods, first through a basic counter, and then in a concurrent hash table. Your template is available in
svn://bits.cs.uic.edu/cs361/pub/homeworks/hw10
Counter Synchronization
For this part, we revisit our old go-to problem of counting. The template contains a basic multi-threaded application
counter.c
, without synchronization, which produces an incorrect final count. Your job is to create several alternative implementations of the functions
init()
and
increment()
, using different techniques to ensure properly synchronized access to the counter. Copy
nosync.c
to create each of the implementations below.
- pthread_mutex.c - use the standard pthread mutex operations to synchronize access.
- semaphores.c - use standard pthread mutexes to synchronize access
- futex.c - use the Linux futex system call, together with the
CMPXCHG
assembly instruction, as shown in class to synchronize access
- atomicincrement.c - use the
LOCK INCL
assembly instruction to ensure atomic counter increments
For each implementation, note the mean runtime in a file called
counter_runtime.txt
.
Concurrent Data Structure
In this part, we study the performance impact of different synchronization strategies on a concurrent datastructure. The file
hashmap.c
contains a basic hash table implementation without synchronization, and
hashmain.c
contains an application that uses the hash table. Copy hashmap.c to new files named as below, and create concurrent hashtables using several synchronization methods.
- globallock.c - synchronize the basic hash table using a single global lock held for both the
get()
and put()
operations.
- optimistic.c - use atomic increments to track a global version number, implement get() with optimistic concurrency (no locking)
- finegrained.c - synchronize the basic hash table using 64 locks, distributed evenly over the 1024 hash buckets.
For each implementation, note the mean runtime in a file called
hashmap_runtime.txt
.
Turn-in instructions
Don't forget to
svn add
your files and
svn commit
, including the runtime files described above.
Topic revision: r2 - 2013-11-26 - 02:34:26 - Main.jakob