Threads throw a monkey wrench
into the art of programming!
Given that we have multiple threads, we move on to their communication and coordination. Here we consider the coordination, and the requirement of synchronization. In many cases, multiple threads will manipulate a shared data structure. Indeed, at some point some threads must affect something shared, else they really are of no use to each other. A common problem is that without due care, the threads will trip over each other and wreck the common data structure with unsynchronized activity.
Threads are important and threads are hard. While a bug free single threaded program is difficult, a multithreaded program is much more difficult. While a single threaded program can be analysed using fairly basic logical arguments, the lack of a clear time ordering when considering multiple threads complicates things immensely. The example of thread synchronization we give on this page uses the Java programming language. Java brings thread programming to the programmer as a feature of the language. The syntax of the language, and some basic synchronization concepts, will allow programmers to reliably build thread-safe programs, that is, programs free of the sort of bugs cause by hectic and uncoordinated actions of multiple threads on a shared data structure.
/*
* ThreadStress
* author: burton rosenberg
* created: 9/2012
*
*/
class ThreadStress {
final static int N = 10 ;
final static int T = 300 ;
final static int P = 4 ;
final static int LISTER_DELAY = 5000 ;
static public void main( String [] args ){
LinkedListNode lln, llnr ;
boolean synced = false ;
int i ;
if (args.length==0) {
System.out.println("options: [sync|nosync]") ;
System.exit(0) ;
}
if ( args[0].equals("sync")) {
synced = true ;
}
// make a linked list
llnr = new LinkedListNode(0) ;
for (i=1; i<N; i++ ) {
llnr.insertAfter(new LinkedListNode(i)) ;
}
(new Thread(new ListListerThread(llnr,
LISTER_DELAY))).start() ;
if (synced ) {
ListModifierThreadSync lmts ;
for (i=0; i<P; i++) {
lmts = new ListModifierThreadSync(
llnr,1000*(i+1),T) ;
(new Thread(lmts)).start() ;
}
}
else {
ListModifierThread lmt ;
for (i=0; i<P; i++) {
lmt = new ListModifierThread(
llnr,1000*(i+1),T) ;
(new Thread(lmt)).start() ;
}
}
}
}
/*
* LinkedListNode
* author: burton rosenberg
* created: 9/2012
*
*/
class LinkedListNode {
LinkedListNode next ;
int data ;
LinkedListNode(int data) {
this.data = data ;
}
void insertAfter( LinkedListNode to_insert ) {
to_insert.next = next ;
next = to_insert ;
}
boolean removeFollowing( ) {
if (next==null) return false;
next = next.next ;
return true ;
}
LinkedListNode nodeAt( int i ) {
LinkedListNode lln = this ;
while (i>0) {
//if (lln==null) return null ;//live dangerously
i-- ;
lln = lln.next ;
}
return lln ;
}
int length() {
// using recursion
if (next==null) return 1 ;
return 1 + next.length() ;
}
}
/*
* ListListerThread
* author: burton rosenberg
* created: 9/2012
*
*/
/* Food for thought:
* does this code need to be synchronized?
*/
class ListListerThread implements Runnable {
int delay ;
LinkedListNode llnr ;
ListListerThread( LinkedListNode llnr, int delay ) {
this.llnr = llnr ;
this.delay = delay ;
}
public void run() {
while(true) {
LinkedListNode lln ;
lln = llnr ;
System.out.print("list: ") ;
while (lln!=null) {
System.out.print(lln.data+" ") ;
lln = lln.next ;
}
System.out.println() ;
try {
Thread.sleep(delay) ;
} catch (Exception e) { }
} // while
}
}
/*
* ListModifierThreadSync
* author: burton rosenberg
* created: 9/2012
*
*/
import java.util.Random;
class ListModifierThreadSync implements Runnable {
int delay = 2000 ;
LinkedListNode llnr ;
boolean mode = true ;
Random prg = new Random() ;
int id = 1000 ;
ListModifierThreadSync( LinkedListNode llnr,
int id, int delay ) {
this.llnr = llnr ;
this.delay = delay ;
this.id = id ;
}
public void run() {
LinkedListNode lln ;
int index ;
while(true) {
synchronized( llnr ) {
index = prg.nextInt(llnr.length()) ;
lln = llnr.nodeAt(index) ;
if (mode) { // insert
int d = id++ ;
LinkedListNode lln1 =
new LinkedListNode(d) ;
lln.insertAfter(lln1) ;
mode = false ;
}
else { // remove
if (lln.next!=null) {
int d = lln.next.data ;
lln.removeFollowing() ;
mode = true ;
}
}
} // synchronized
try {
// sleep releases lock
Thread.sleep(delay) ;
} catch (Exception e) { }
} // while
}
}
Consider multiple threads accessing a common linked list. Suppose the threads each have reason to insert items to the linked list, and remove items from the linked list. Also to scan the list, either for length or to process each element on the list.
A modification of a list entails a read-modify-write action that assumes that the decisions made on the basis of what was learned by the read are still sensible decisions when the thread writes it updates to the list. If there are multiple, uncoordinated threads modifying the linked list, this need not be the case.
Oh geez yes, a concrete example will help. But forestalling for a second the example — the thread will read the data structure and come to a decision on the actions it will take to modify the data structure. All actions can't be compatible with what was read, else there would be no reason to read the data structure. Assuming the data read was not gratuitous, the actions planned are specific for the data returned by the read. At the moment the thread acts on its decision in the data structure, it is possible that the values providing to the read have changed. It is possible that the actions decided as appropriate are no longer appropriate. They may even be damaging to the data structure.
Therein lies the problem.
The solution that is considered on this page is to permit only a single thread at a time to modify the linked list. In this way, the write will be appropriate to the linked list, because the linked list has not changed since the read. A way of assuring this is to place a lock on the linked list. In order to make modifications to the data structure, the thread must hold the lock, and only one thread can hold the lock at a time.
So we need the operating system to create for us things called locks, that can be associated with data structures, and which serialize threads so that they hold the lock only one at a time. Often the operating system will respond in principle, but not in detail. The operating system will provide synchronization primitives from which locks can be built. When one gets down to details, there are several variants of locks, and rather than commit to one sort, the operating system tries to provide primitives that work efficiently, and are flexible and powerful enough to build upon.
Java uses the operating system synchronization primitives to enhance the overall language and semantics of Java. Each object in Java has an associated lock, whether the programmer uses it or not. It is a property of the generic superclass of all objects, and is inherited by any object. A thread can take the lock by attempting to enter a block of code identified as synchronization block by some Java syntax, and provides the reference to the object. Of all the synchronization blocks referring to a give object, only one thread may run code in any of those blocks. When several thread contend to enter together, the Java runtime picks on and only one and lets it proceed. The other threads wait (generally sleep) for the chosen thread to leave the block.
The ThreadStress class is the main entry point. It builds a linked list out of nodes of type LinkedListNode, and uses a reference to the first element on the list as the handle for the list. The first element on the list will never be deleted, it is in effect the identifier of the list.
The LinkedListNode is a minimal implementation of a linked list. An instance of this class is a node in the linked list, with a next pointer and a data item.
The main thread spawns a single ListListerThread. For those not familiar with threads, Java provides a Thread class, which takes an instance of any object implementing Runnable. To implement Runnable, your class must have a public void run() method. An instance of a Thread class a start method which will launch a new thread running the code in this run method.
The ListListerThread object is instantiated with a reference to the linked list root. The loops between sleeping and walking the linked list starting at the root, printing its contents.
The main thread spawns multiple ListModifierThread or ListModifierThreadSync threads. If the main program was called to demonstrate the bad things that happen without synchronization, the threads are of class ListModifierThread; if the intent was to show the good thing that happens with synchronization, the threads are of the class ListModifierThreadSync.
To cut down on the size of the code listing, and to highlight the code that accomplishes the synchronization, the two classes ListModifierThread and ListModifierThreadSync are listed as one, with the differences in red. Removing all that is red removes the synchronization block, and does some incidental renaming because the class names are different.
These two classes extend Runnable, hence can be used to construct an object of type Thread that can be run. They are instantiated given a pointer to the root of the linked list, this is how they come to share the linked list. They are also given distinct starting numbers to identify the nodes that they create. The first thread creates nodes 1000, 1001, etc; the second 2000, 2001, etc; and so on.
The run method is an infinite loop that waits, then measures the length of the linked list and picks a random element from the linked list. It then either deletes the element following that chosen element, or inserts a new element after it. It alternates between inserting and deleting, so that on the whole the number of items on the list should vary only slightly.
I leave it to the reader to contemplate what can go wrong without the synchronization. Plenty can go wrong. The general idea is that the thread makes decisions for action on information which may not be current when the action is effectuated on the list. It is important to find as many specific examples of this happening in order to fully appreciate the problem.
Threads must not intrude upon each others action as they then modify the linked-list. Only one thread must be permitted this activity at a time, commencing with it reading the details of the linked list and ending with the write of modified data to the list. This is accomplished by adding to the ListModifierThread.run code a synchronization block.
The block synchronizes on root node of the linked list. This node, you remember, represents the linked list. Only one thread can be in this block at a time. This solves the problem.
Note that we leave the synchronization block to sleep. Never sleep holding a lock. The other threads cannot enter until the lock is released, and therefore until the thread returns from sleep. In many cases, a deadlock can occur in which the waiting threads cannot continue until the sleeping thread awakens; but the sleeping thread will not awaken until the waiting threads do something. Avoiding deadlock is an important consideration for thread programming.
Note that we synchronize on a common node, the root node. All the threads must synchronize on a common object. The root node was handy, but it does also represent that linked list, so it is a lock on the entire list. One can synchronize on individual nodes, but that is not the same thing, and will not be effective in this case.
Note that we do not synchronize the ListListerThread code. We could. We could add a synchronization block referencing the root node, just as in the ListModifierThread code. The reader is invited to think about this. The reader should consider:
Without synchronization, things definitely go wrong. If we run this code we get null pointer exceptions (which will crash the thread), and the linked list suddenly changes size. Here is the output when run in the two ways, synchronized and unsynchronized.
Note that The number of errors you get will vary. They did for me. This run was on OSX 10.7.5 with the Java Runtime as shown from the java -version command, see below. Although this run shows the problem quickly, later on my runs showed fewer errors, and the fan was running constantly. After reboot, the errors returned to the frequency shown.
On Ubuntu, Precise using IcedTea 6 1.11.4, I had to crank up the thread number to 16 and the sleep time down to 2 to get the threads to stumble. Even then, only at a rate of one every few minutes. I think this has to do with thread scheduling. The more genuine the parallelism seems, the more likely one is to have problems of parallelism.
hohokus-3:threadstress burt$ java -version
java version "1.6.0_35"
Java(TM) SE Runtime Environment (build 1.6.0_35-b10-428-11M3811)
Java HotSpot(TM) 64-Bit Server VM (build 20.10-b01-428, mixed mode)
hohokus-3:threadstress burt$ make run-nosync
java ThreadStress nosync
list: 0 9 8 7 6 5 4 3 2 1
list: 0 1011 4008 3010 2012 2010 2011 4010 1006 1012 3009 3011
Exception in thread "Thread-4" java.lang.NullPointerException
at ListModifierThread.run(ListModifierThread.java:39)
at java.lang.Thread.run(Thread.java:680)
list: 0 2024 4022 1021 2019 1020 1024 1022 2021 1023
list: 0 4033 2032 2031 2035 2030 1036 4034
list: 0 4046 1042 2046 1048 1043 2045 4045
list: 0 2052 1053 4055 2056 1061 1060 1058
list: 0 2068 4068 1073 2065
list: 0 1084 1081 4079 2076
list: 0 4088 4089 2090 1093 4087 1095 2087
list: 0 4101 1106 2100 1105 4098 2096
list: 0 2110 1111 1116 1118 4113 4112
list: 0 4124
list: 0 1137 2133 2135 1136
list: 0 2146 1149 4145 4144 2147 1146
Exception in thread "Thread-2" java.lang.NullPointerException
at ListModifierThread.run(ListModifierThread.java:39)
at java.lang.Thread.run(Thread.java:680)
list: 0 4155 2158 4156 4157 2157 2153 2156
list: 0 2164 2165 4157 4166 2166 2168
list: 0 2173 2179 4180 2178
Exception in thread "Thread-3" java.lang.NullPointerException
at ListModifierThread.run(ListModifierThread.java:39)
at java.lang.Thread.run(Thread.java:680)
list: 0 4189 4192 4191 4190
list: 0 4199 4201 4191
list: 0 4214 4212 4211 4213
list: 0 4222 4225 4223
^Cmake: *** [run-nosync] Error 130
hohokus-3:threadstress burt$ make run-sync
stating sync'ed
list: 0 9 8 7 6 5 4 3 2 1
list: 0 3022 2022 4022 1022 1018 3023 2021 1021 4018 4016 2019
list: 0 4044 2043 1044 2041 4047 4049 3037 1045 3043 2046 2045 2044
list: 0 4071 1063 2065 3070 3069 1066 2068 2067 3071 2066 1068
list: 0 1090 4094 3094 3093 4093 2089 2091 4092 3092 2087 2090 1087
list: 0 2113 3118 4113 1116 1112 1115 4117 2114 3117 1111 4118
list: 0 1140 4134 2135 3143 2133 1139 2137 4141 4140 3141 4139
list: 0 2152 2160 4166 3164 4164 3167 1162 2159 4165 1160 3165
list: 0 2174 1186 2181 3180 3185 3189 1187 2183 4189 4185
list: 0 2207 1210 2204 1209 3215 2206 4213 4211 1211 3214 3213
list: 0 1236 4233 2225 1230 3237 4237 3231 2228 4235 4236 3236 3239
^Cmake: *** [run-sync] Error 130
hohokus-3:threadstress burt$
Copyright 2012 burton rosenberg
Last modified: 30 sep 2012