Week 14 - Chapter 17 - Multiple Concurrent Tasks

Theory

Concurrent Execution: What It Means

Concurrent execution means being able to run more than one program on a single machine or a single processor.

These seperate streams of execution are typically referred to by a variety of names:

Threads are a topic of discussion in this class, because their properties and functions can be nicely wrapped up into an object and treated as an ADT, as we shall soon see.

Page 702 in your book gives some concrete examples of where multi-threaded execution is used.

Types of Concurrent Execution

There are a variety of approaches to concurrent execution. The time that a thread gets to spend executing is called a Timeslice.

The Life Cycle of a Thread

The following list traces a thread through it's normal life span.

Synchronization and Shared Resources

Shared Resources

Often, two or more threads of execution need to use the same resource. In order to avoid undesirable effects, some means of synchronizing operations between threads needs to be in place.

The following are examples of shared resources:

Let's use the example of a linked list which has two threads working on it, one which adds nodes to the end of the list, and one which reads nodes at the front of the list, processes them, and deletes them from the front of the list. This kind of situation is typically referred to as a "producer / consumer" relationship.

You can probably already see the potential problem in this scenario: What happens when the producer isn't working as quickly as the consumer? It is entirely possible that the consumer would attempt to read and / or delete a node from the list when the list is completely empty! How does one prevent this from occurring? Answer: synchronization.

Synchronization

Most simply put, synchronization is the act of controlling access to a shared resource by only allowing one thread to work on it at a time. There are numerous methods for accomplishing this:

So, continuing with our previous example, the producer thread (the one that adds nodes to the list), can freely go about it's job without any interruption. It will, however, need to tell the consumer thread (the one reading / deleting nodes from a list), when it can and can't go about it's business. The producer thread would do this by testing if the list was empty, and if so, tell the consumer thread to wait. Likewise, after the producer thread has added a few nodes to the list, it would notify the consumer thread and wake it up. In addition, just before the consumer thread attempts to read / delete a node from the list, it should also test if it is empty and if so, put itself to sleep.

When Good Threads Go Bad

There are also some problems that can arise from using multiple threads.

Race Conditions

Using synchronization techniques is not only useful, it is often vital. If you do not synchronize access to data it can create a Race Condition. A Race Condition is defined as: "Anomolous behavior due to unexpected critical dependence on the relative timing of events." More simply put, a race condition is when two threads try to access a shared resource at the same time and end up damaging / corrupting the resource.

Let's say that in our previous example of the consumer / producer threads acting on the linked list, we did not regulate their access to the list, and just let them do whatever they wanted to the list, at any time. Well, it might work okay for a little while, but I guarantee you that sooner or later, Problems Will Happen. The consumer thread might try consuming when the list is empty, the producer might try linking a new node to a node that was just deleted, or some other thing.

Bottom line: Use synchronization to avoid race conditions.

On page 703 in your book in the section entitled "Ada Structures for Concurrent Programming" it describes a similar situation using an email program as an example; it call it the "readers / writes problem".

Deadlocks

There is one other noteworthy point that should be introduced: Deadlocks. Simply put, a deadlock is created when two or more threads are put to sleep and never woken up because each is waiting for one of the others to do something. This typically is a result of overuse of synchronization.

Continuing from our ongoing example above, let's say the consumer thread told the producer thread to wait while it is reading and deleting nodes--just to avoid any possible collisions that might occur with having both processes manipulating the data structure. With the producer thread put to sleep, it is no longer adding nodes to the linked list. Once the consumer thread gets done reading all the nodes in the list, it will likewise put itself to sleep and wait to be awoken by the producer thread when it has added some more nodes. The problem is, the producer thread is asleep and no longer producing nodes! Result: Both threads are asleep, nothing is getting done, and the program is locked up.

To avoid this unfortunate circumstance, you must be careful about when you tell your threads to go to sleep, and be sure to wake them up. Double-check your code and your logic, and step through the code in a debugger (or pepper the code with print statements if necessary). Another very good approach is to give your threads a timeout value, after which the threads will wake up. There really is no silver bullet here, you just have to be careful.

Priority Inversion

Priority Inversion as explaind on FOLDOC:

A phenomenon which can arise in a concurrent programming environment where a high priority task (H) is blocked by a low priority task (L), e.g. because L has locked some resource needed by H, and L then has to wait for a medium priority task (M). The net result is that H ends up waiting for M instead of the other way round - the priorities become inverted.

This can be a problem if, for example, M takes a long time, causing H to miss a deadline.

A possible cure is to have tasks inherit the maximum priority of any task that is waiting for them. In that case L temporarily becomes high priority until H can procede, thus preventing M from running in place of H.

Further Reading

If you are interested in finding more information on how concurrent execution / threading works, I would reccommend the following:

Ada Stuff

Ada Threads - Tasks

(p. 704) To begin, concurrent programming (implemented as "Tasks" in Ada) is one of the nicest things about the language. The implementation is very clean and straightforward. If you're still cringing from anything in any previous chapters, you can relax now and enjoy this stuff.

Tasks are introduced on page 704. Be sure to read the bulleted list on that same page which tells what a Task is and isn't and how it is similar to constructs you have already learned. The example program which follows is likewise instructive.

Note that tasks are started implicitly if no entry point is specified (more on entry points below).

The sample code on page 705-706 shows that you can decleare two instances of the same type of Task.

Timeslicing - The DELAY keyword

(p. 707) See the section entitled "Cooperating Tasks" that begins in the middle of page 707 and goes on to page 708. This is like a sleep() statement in C and simply allows the program to time-slice task execution a little more nicely.

Note that the DELAY keyword takes a single argument that is of type Standard.Duration (a subtype of Float).

Entry Points - The ACCEPT keyworkd

(p. 708) Look at the section that begins at the bottom of page 708 entitled "Controlling the Starting Order of Tasks", and continues until p. 710. Here you see how you can specify a kind of "label" that will prevent the thread from starting execution immediately, and wait until you call the ACCEPT label. The code example on page 709 is helpful.

The "gray-box" Syntax Summary for all this is on page 710-711.

Synchronization - The PROTECTED keyword

(p. 711-716) The way tasks are synchronized / blocked in Ada is via the PROTECTED keyword. (I realize this will trouble a lot of you C++ fans out there -- Take it like a man.) The section that describes it begins on page 711 and goes on through to page 716. It uses an example of drawing to the screen to demonstrate the need for synchronization.

The explanation gets a little long, but the sample code on p. 714-715 shows how you simply declare a "mini-package"-type thing that can contain non-reentrant methods. Again, note how clean and straightforward this implementation of synchronization is. I guess anybody can have a good day. This is an example of the 'Synchronization Objects' approach described above in the theory section.

The "gray-box" Syntax Summary for protection is on page 722.

Odds And Ends

The book also mentions a SELECT keyword. Don't worry about it.

Be sure to look at the Chapter Summary on p. 725-724.

Assignment 12

Write a program which contains two tasks that will act on a single, global, integer number.

Sample output follows:

	After adding 1 GlobalVar = 1
	After adding -1 GlobalVar = 0
	After adding 1 GlobalVar = 1
	After adding 1 GlobalVar = 2
	After adding 1 GlobalVar = 3
	After adding -1 GlobalVar = 2
	After adding 1 GlobalVar = 3
	After adding 1 GlobalVar = 4
	After adding 1 GlobalVar = 5
	After adding -1 GlobalVar = 4
	After adding 1 GlobalVar = 5
	After adding 1 GlobalVar = 6
	After adding 1 GlobalVar = 7
	After adding -1 GlobalVar = 6
	After adding -1 GlobalVar = 5

You could even use the same task declaration for both tasks and pass it the appropriate value for the DELAY statement as a parameter. In fact, I encourage you to code it this way.

You do not need any code in the body of the assn12 procedure; you can just type null;.

Note: If you want to see something cool, type "ps f" while your program is running; it will display a process tree that will show both threads of your program attached to the parent process.

Update: Sadly, I have leared that Tasks in the GNAT compiler on the Zonker server are broken. Your programs will compile, but if you try to run them, they will segfault. Since this is the case, please simply complete the program, get it to compile, and leave it for me to grade, I will just look at the source. This is very sad and I apologize for this inconvenience. The good news is, if you want to use the programs that come on the CD, they should work fine.

This (last!) assignment is due on December 5th, 2001, the night of the Final Exam!