Threads throw a monkey wrench
into the art of programming!
There are virtual threads and hardware threads. A hardware thread is the actual ability to compute, and is the machinery in the CPU. There are a finite number of threads, provided by the manufacture of the CPU. The hardware elements to implement a thread include the instruction and stack pointers and the ALU registers
A virtual thread is an abstract construction that recapitulates a hardware thread, but can left to be just a potential for progress. For a virtual thread to actually make progress, a hardware thread has to be assigned to it, to carry out the instruction stream associated with the virtual thread.
The hardware threads my simulation a multiplicity of virtual threads proceeding simultaneously in parallel. Since threads are not necessary synchronized, nor must their progress be balanced, there is leeway in the requirement of simultaneity. Multiplexing several virtual threads onto a single hardware thread can be sufficiently simultaneous, since there is no counter argument to claiming that the pattern of activity of the threads when multiplexed onto a single hardward thread, where they sporadically making progress with interleaved periods of activity, is not how they would proceed, even if given an individual hardware thread for each virtual thread.
As a practical matter, the hardware threads must be frequently multiplexed to allow sufficiently balanced progress among all threads as a matter of efficiency, rather than correctness. If the threads have data dependencies across them, and they do not make balanced progress, the overall result might have no advantage of parallelism, and the scheduling mechanism cycles through the threads to identify which can make progress, and which are waiting on the progress of other threads.
Synchronization: When threads access a common data, or manipulate a common data structure, their actions must be coordinated. When a data structure changes state, i.e. a node is inserted into a linked list of nodes, the correctness of the data structure is temporarily disturbed. Typically this is not a problem, because the internal status of the change of state is not observed. I.e. the method that inserts the node assumes at it entry that the data structure is correct, and will assure on method exit that the data structure is correct. As no other thread exists, no other thread can witness any temporary incorrectness that exists during the run of the method.
However, if multiple threads are allowed simultaneous access to the data structure, they may observe it in an incorrect state. The simplest solution is to enforce mutual exclusion between threads for certain sections of code, called the critical sections, during which the state of the data structure might become incorrect. The pattern of mutual exclusion is one of the most fundamental in thread programming.
Locking: Mutual exclusion of critical sections are only needed when the operations are on the same data structure. The situation can be profitably recast as a lock on the data structure. Holding the lock is subject to mutual exclusion, providing safety, etc., for the data structure operations, but allowing for simultaneous progress when modifying different data structures.
This sort of lock might overstate what is necessary for correctness. A good example is the reader-writer pattern, a.k.a. advisory-mandatory locks. Readers of a data structure can proceed simultaneously, but writers must claim exclusive access. This is achieved by each reader taking a reader lock, which can be granted to multiple threads. A writer attempts to take a writer lock, which must wait until all reader locks are released, and there are no other writer lock granted, before the thread receives the lock and can proceed.
To prevent starvation of the writer, during the time the writer has requested the writer lock but not been granted the lock, no new reader locks are granted — reader lock requests are queued. The reader lock is also called an advisory lock, as its purpose is to advise on the user of the data structure, and the writer lock is called a mandatory lock as mandates the mutual exclusion.
Java Threads and Synchronization.
The Java language implements threads and locking on objects. A thread is created by wrapping and instance of a Thread object around any object that implements Runnable. An object implements Runnable if it has a method named run, that returns void, and takes no arguments. This creates a virtual thread set to run the run method once the start method is called on the thread object.
Each Java object has a unique mutual exclusion lock that can be requested by attempting to enter a synchronized block. The block references the object whose lock is being requested. The lock is released when the synchronization block is exited. There is a contention queue associated with each lock instance, and multiple simultaneous requests for the lock will result of all but one thread ending up on the contention queue. When a thread releases the lock, if the contention queue is not empty, a thread from the contention queue will granted the lock and will continue into the synchronization block.
Java locking furthermore implements a wait-notify semantic. A thread running with a held lock can call wait on itself. This will release the lock and place the thread on the wait queue. A thread running with a held lock can call notify (or notify-all) on itself, which will remove one (all) thread(s) from the wait queue and place the removed thread(s) on the contention queue. If nothing is waiting the notify (notify-all) does nothing (is lost).
/*
* 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() ;
}
}
We will use a writer lock on a problem in list reader writer. We will discuss the full reader-writer lock below.
Here is the code for the linked list, in particular the class for a node on the linked list.
The first node on the linked list will be a data-carrying node, but will represent the list, and be called the root-node. To create an empty linked list is to create its root-node. The first data node will be following this node.
This gives an unchanging reference for the linked list, as a reference to the list's root node. We will also lock the list by synchronizing on the referece to the root node.
/*
* 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
}
}
Here is the code for the reader. It is not synchronized — for the sake of simplicity we will take our chances. Also, an error on the reader is a bit different than an error on the writer. Messing up a critical race on the reader gives us a wrong view of the list, but does not harm the list.
This code is a good opportunity to demonstrate the specifics of Java threads. A Thread is a class, that wraps around a object that implements the Runnable interface. The creation of the Thread object is in the main code. This code here prepares the Runnable object to be used when instantiating the Thread object. A Thread object accepts a "start" message, that will schedule are ready an independent code, that will run the run method.
The run method is an infinite loop alternating sleeps and link list listing. The instantiation of the ListListerThread object is given the root node of the list, so it knows what to list. Note also, that to sleep a thread, the class method Thread.sleep() is called, and it is understood that the sleep is on the thread that called the method.
/*
* 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
}
}
Here is the code for the writer threads. There are actually two objects
defined, ListModifierThread and ListModifierThreadSync.
They are combined into one listing with the help of setting in emphasis the differences
between the two classes by words and syntax in red.
As this will be the code wrapped inside a Thread object, so that its run method can be started as an independently runnable thread, the objects implement Runnable. As with the reader code, the initialization takes a reference to the root node of the list to be written.
The run loop alternates between a sleeps a list modification. The modification alternates between a random insert and a random remove. The randomness is provided by choosing in integer, which because the index of the node to remove, or the index of the node just before the insertion.
The non-synced version will have the writer threads all going through the run code concurrently. It will be demonstrated how this corrupts the list, as the un-synchronized actions cannot provide a safe execution. The synced version encloses the critical section with the synchronized construct, providing as parameter an object that will be used for the lock. The construct guarantees mutually exclusive access on the lock. Therefore only one thread will be running inside the block at a time.
/*
* 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() ;
}
}
}
}
The main program creates a linked list, then creates a reader thread to list the list, and starts that thread.
It then creates and starts several writer threads. Depending on the value of the variable synced, it starts either the synced writer threads or the un-synced writer threads. This variable is modified between compiles.
The result is below, showing that the un-synced version has a number or errors, including a complete crash of threads for undefined references, and large gaps in list size, as the list is corrupted by concurrent access to the list.
The synchronized version, however, gives completely correct answers.
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$
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.
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.
Implementing a reader-writer lock in Java
The reader-write lock is associated with a ReaderWriter object. The ReaderWriter object has an instance variable advisory_count, initially zero. Reader threads must take the ReaderWriter lock and increment the advisory_count, then release the lock and continue into their critical section. At the end of the critical section the Reader decrements the advisory_count in an atomic fashion, and must not take the lock to do this.
Data Structure Invariant: The advisory_count advises on the number of threads that have taken the advisory lock.
The Writer threads must take the ReaderWriter lock then wait until the advisory_count is zero. Once zero, the method continues while holding the lock, to its critical section. That is, the entire critical section of the Writer thread is inside a synchronization block, including the prefacing loop that checks for advisory_count of zero before proceeding on into the block. (The Reader threads however enclose only the increment of advisory_count inside the synchronization block.)
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.