(Updated September 19, 2021)
This project examines the finer details of multi-programmed environments and the problems they introduce. You will be working with threads, locks, critical sections and reviewing key aspects of how operating systems manage some details while leaving some to the programmer to handle.
This is to be done using your Ubuntu Linux virtual machine.
Learning outcomes
- Threaded execution models.
- Java Threads and synchronization.
- C Threads and synchronization.
- Understanding locking.
- Understanding critical sections.
Overview
Threads are a useful extension to the application model. They allow for a single process to have multiple portions executing simultaneously while only occupying one process space. In other words, there is one process and multiple threads.
Traditionally, if we wanted to have multiple portions of a program running simultaneously, we would create additional processes using the fork() system call in C on Linux. But, this creates a new process (using the current running program as a blueprint) and that means a new address space. One idea behind threads is to share the address space, not necessarily create a new one.
If you have not already done so, you should read the chapter on threads.
The Atomicity-Violation bugs and the locks section are exellent additional bits when proceeding with this discovery project.
Now, we will present two thread models:
- Java Threads
- Linux Pthreads
Further we will introduce two forms of locking:
- Synchronized methods (synchronized statements are left to the reader to research)
- Pthread mutexes (mutual exclusion locks)
Java Threads
Java allows us to create threads at will by passing an object that implements Runnable to a Thread object. It is actually quite easy to implement.
Things to note in these Java examples are:
- We intentionally sleep (
sleepMe())to simulate going into an I/O mode. - The
Counterclass is used to create the shared object. - The threads are created using the
IncrementItandDecrementItclasses.
Preparing the Software
Install the OpenJDK software in your Ubuntu VM using:
sudo apt update sudo apt install openjdk-11-jdk-headless
Then using gedit or another editor, copy and paste the following code into two separate files. Compile each on the command line with:
javac ThreadInterference.java javac ThreadSafe.java
public class ThreadInterference {
static Counter shared;
// intentionally implement some extra time
static void sleepMe() {
try {
Thread.sleep((int)Math.random()*600);
} catch (InterruptedException e) {
threadMessage("Oh drat!");
}
}
//Display a message, preceded by the name of the current thread
static void threadMessage(String message) {
String threadName = Thread.currentThread().getName();
System.out.format("%s: %s%n", threadName, message);
}
// Inner class that will be manipulated by threads.
static class Counter {
private int c = 0;
public void increment() {
int t = c;
sleepMe();
c = t + 1;
}
public void decrement() {
int t = c;
sleepMe();
c = t - 1;
}
public int value() {
return c;
}
}
// Thread to do 500 increments of shared Counter.
private static class IncrementIt implements Runnable {
public void run() {
for (int i = 0; i < 500; i++) {
//threadMessage("Incrementing!");
shared.increment();
}
}
}
// Thread to do 500 decrements of shared Counter.
private static class DecrementIt implements Runnable {
public void run() {
for (int i = 0; i < 500; i++) {
//threadMessage("Decrementing!");
shared.decrement();
}
}
}
public static void main(String[] args) throws InterruptedException{
int count=0;
for (int x = 0; x < 1000; x++) {
shared = new Counter();
// Start the threads!
Thread i = new Thread(new IncrementIt());
i.start();
Thread d = new Thread(new DecrementIt());
d.start();
// Wait for them to complete!
i.join();
d.join();
// What was the final counter value? It should be zero.
//threadMessage("shared is " + shared.value());
count += (shared.value() == 0) ? 0 : 1;
}
threadMessage("The shared value was not zero " + count + " out of 1000 times.");
}
}
Java program that intentionally demonstrates thread interference.
Now this next bit of code has a subtle change to make it thread safe. To do this we add the synchronized modifier to the method declarations of the class being shared between the two threads.
This allows us to say that those methods are all mutually exclusive and therefor causes the Java runtime to lock the whole object while in one of those methods. Hence, the object being locked means that any thread desiring access to the object will block until the lock is freed.
synchronized.public class ThreadSafe {
static Counter shared;
// intentionally implement some extra time
static void sleepMe() {
try {
Thread.sleep((int)Math.random()*600);
} catch (InterruptedException e) {
threadMessage("Oh drat!");
}
}
//Display a message, preceded by the name of the current thread
static void threadMessage(String message) {
String threadName = Thread.currentThread().getName();
System.out.format("%s: %s%n", threadName, message);
}
// Inner class that will be manipulated by threads.
static class Counter {
private int c = 0;
public synchronized void increment() {
int t = c;
sleepMe();
c = t + 1;
}
public synchronized void decrement() {
int t = c;
sleepMe();
c = t - 1;
}
public synchronized int value() {
return c;
}
}
// Thread to do 500 increments of shared Counter.
private static class IncrementIt implements Runnable {
public void run() {
for (int i = 0; i < 500; i++) {
//threadMessage("Incrementing!");
shared.increment();
}
}
}
// Thread to do 500 decrements of shared Counter.
private static class DecrementIt implements Runnable {
public void run() {
for (int i = 0; i < 500; i++) {
//threadMessage("Decrementing!");
shared.decrement();
}
}
}
public static void main(String[] args) throws InterruptedException{
int count=0;
for (int x = 0; x < 1000; x++) {
shared = new Counter();
// Start the threads!
Thread i = new Thread(new IncrementIt());
i.start();
Thread d = new Thread(new DecrementIt());
d.start();
// Wait for them to complete!
i.join();
d.join();
// What was the final counter value? It should be zero.
//threadMessage("shared is " + shared.value());
count += (shared.value() == 0) ? 0 : 1;
}
threadMessage("The shared value was not zero " + count + " out of 1000 times.");
}
}
Java program that is thread-safe.
The Discovery
Run each program multiple times using:
java ThreadInterference
AND
java ThreadSafe
The threads will be created and allowed to make changes to a new object for 1000 iterations. Note that the thread safe version will always return zero for the shared value (the correct answer!). The other will return various values (very, very incorrect ones if they are not zero!). This demonstrates that critical sections exist and that they need special treatment.
The solution is to mark the methods that will be manipulating the shared value. By making them synchronized (lines 24, 30 and 36) we guarantee that the methods will not interfere with each other by making the class block any other threads that try to run those synchronized methods.
This form of locking is only one way to handle race conditions within critical sections. The next set of examples will show how we can do it in C while a bit closer to the OS and the hardware.
Threads in C
Now we look at a threading model that is directly in line with the operating system. The Pthreads model was introduced with the POSIX standard and are actually called POSIX Threads or Pthreads for short. Any POSIX compliant operating system will likely have Pthreads available.
Things to note in these C examples are:
- We have a sleep function(
sleep_me()) to simulate going into an I/O mode - but is unused by default. - The
sharedglobal variable is used to create the shared space. - The threads are created using the
increment_sharedanddecrement_sharedfunctions as entry points of the thread. - The second implementation uses a Pthread mutex to synchronize access to the shared space.
Preparing the Software
The build-essential meta-package is likely already installed for you, but just in case you can install it using:
sudo apt install build-essential
Then using gedit or another editor, copy and paste the following code into two separate files. Compile each on the command line with:
gcc -o thread-int -pthread thread-int.c gcc -o thread-safe -pthread thread-safe.c
sleep_me() function is commented out. Testing has shown it was not necessary to introduce intentional sleeps to show how preemption impacted the shared value.#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
int shared = 0;
void sleep_me() {
struct timespec t, left;
t.tv_sec = 0;
t.tv_nsec = 5000;
if (nanosleep(&t, &left) < 0)
printf("error");
}
void *increment_shared( void* m ) {
for (int x = 0; x < 500; x++) {
int t = shared;
t = t + 10;
shared = t;
//sleep_me();
}
return NULL;
}
void *decrement_shared( void* m ) {
for (int x = 0; x < 500; x++) {
int t = shared;
t = t - 10;
shared = t;
//sleep_me();
}
return NULL;
}
int main(void) {
pthread_t thread1, thread2;
int iret1, iret2, count=0;
/* Create separate threads pointing to their respective functions */
for (int x = 0; x < 1000; x++) {
shared = 0;
iret1 = pthread_create( &thread1, NULL, increment_shared, NULL);
iret2 = pthread_create( &thread2, NULL, decrement_shared, NULL);
/* Wait till threads are complete before we allow main to continue. */
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);
count += (shared == 0) ? 0 : 1;
}
printf("Shared was not zero %d out of 1000 times.\n", count);
exit(0);
}
Now this next bit of code adds a mutex to make it thread safe.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
int shared = 0;
pthread_mutex_t shared_mutex = PTHREAD_MUTEX_INITIALIZER;
void sleep_me() {
struct timespec t, left;
t.tv_sec = 0;
t.tv_nsec = 5000;
if (nanosleep(&t, &left) < 0)
printf("error");
}
void *increment_shared( void* m ) {
for (int x = 0; x < 600; x++) {
pthread_mutex_lock(&shared_mutex);
int t = shared;
t = t + 10;
shared = t;
//sleep_me();
pthread_mutex_unlock(&shared_mutex);
}
return NULL;
}
void *decrement_shared( void* m ) {
for (int x = 0; x < 600; x++) {
pthread_mutex_lock(&shared_mutex);
int t = shared;
t = t - 10;
shared = t;
//sleep_me();
pthread_mutex_unlock(&shared_mutex);
}
return NULL;
}
int main(void) {
pthread_t thread1, thread2;
int iret1, iret2, count=0;
pthread_mutex_init(&shared_mutex, NULL);
/* Create separate threads pointing to their respective functions */
for (int x = 0; x < 1000; x++) {
shared = 0;
iret1 = pthread_create( &thread1, NULL, increment_shared, NULL);
iret2 = pthread_create( &thread2, NULL, decrement_shared, NULL);
/* Wait till threads are complete before we allow main to continue. */
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);
count += (shared == 0) ? 0 : 1;
}
pthread_mutex_destroy(&shared_mutex);
printf("Shared was not zero %d out of 1000 times.\n", count);
exit(0);
}
Run each program multiple times using:
./thread-int
AND
./thread-safe
The threads will be created and allowed to make changes to a new object for 1000 iterations. Note that the thread safe version will always return zero for the shared value (the correct answer!). The other will return various values (very, very incorrect ones if they are not zero!). This demonstrates that critical sections exist and that they need special treatment.
The solution is to use mutexes to lock the section of code that will be manipulating the shared value. By making the threads block and wait for the mutex we guarantee that the methods will not interfere with each other.
Conclusion
At this point you have experienced a couple of ways we control program flow to allow multiple threads to run in the same address space while manipulating a shared value.
You likely may have a few unanswered question and this is normal. No one masters multi-threading without a good deal of practice in writing applications that make use of them. If you have any further questions or need additional clarification on some of details, please reach out to your instructor who may also update this document for future students.