Deadlock is pretty dramatic, since it takes at least two processes and the resources they control out of commission permanently, or at least until one of the processes is killed and its resources taken away. No matter what you do, someone will be unhappy. It is unlikely that deadlock will go undetected for any significant amount of time, and the parties involved will know that there is a good chance some damage occurred, so they’ll check for errors.

Here’s another situation caused when you have two processes sharing resources. In this case the resource in question is a data collection (file or database). To illustrate the problem, let’s look at a situation near to all our hearts.

While this is a non-profit organization, that doesn’t mean that going here is free. You probably noticed that already. Whenever you register for a new course, the amount of money you owe the college goes up. Eventually your bill gets paid and the amount you owe goes down again. There are two processes (programs) running on the College’s computers that handle these matters. Let’s call then the Registrar process and the Bursar process. Let’s look at the Bursar process first, since it’s the one that makes your debt go down.

The Bursar process receives your checks (or funds transfers or piles of farm produce or whatever you use to pay your bills) and is supposed to deduct the value of your payment from the current balance recorded in your records in the student database. The student database is in a different computer (the database server) from the Bursar program, so the Bursar program asks for a copy of your balance and stores it in a temporary work space on its own computer while it is modifying the balance. When the new balance is calculated, the Bursar process sends back the new value to the database server with a request to use it to replace the outdated, higher value. In the algorithm below, an arrow (->) indicates that a value is copied into the variables to its right.

Bursar process

B1. Get student ID -> IDb

B2. Get payment -> PAYMT

B3. Get copy of BALANCE for IDb from database->

OLD_BALANCEb

B4. NEW_BALANCEb=OLD_BALANCEb- PAYMT

B5.Update BALANCE for IDb in database to value in

NEW_BALANCEb

B6. Print “You now owe “ , NEW_BALANCEb;

The Registrar process is similar, but it results in your debt going up. When you register for a class, the Registrar program receives the number of credits for which you are registering and multiplies that by the cost per credit hour (full time registrartion is different , but let’s pretend it’s not) to get the amount you should be charged for this term. Again, the student database is in a different computer (the database server) from the Registrar program, so the Registrar program asks for a copy of your balance and stores it in a temporary work space on its own computer while it is modifying the balance. When the new balance is calculated, the Registrar process sends back the new value to the database server with a request to use it to replace the outdated, higher value.

Registrar Process

R1. Get student ID -> IDr

R2. get credits registered for -> CREDITS

R3. CREDITS*1000.00 -> BILL

R4. Get copy of BALANCE for IDr from database->

OLD_BALANCEr

R5. NEW_BALANCEr=OLD_BALANCEr+BILL

R6. Update BALANCE for IDr in database to value in

NEW_BALANCEr

R7. Print “You now owe “ , NEW_BALANCEr;

If we look at those processes individually, they work. If we carry them out in order, the Bursar process followed by the Registrar process, like this:

they still work. You should run through the processes an convince yourself that they do work.

Now try each of these orders. For each, does the answer come out the same? If answers differ, which are right? If any answers are incorrect, what went wrong?

Sequence 1

Sequence 2

Sequence 3

Sequence 4

Sequence 5

R3

B5

You should have found that some of the sequences got different answers. This happened when the calculated new values from the two processes were updated in an unfortunate order – one of them overwrote the other. This is called the “Lost Update” problem.

One particularly troubling aspect of this problem is that both processes ended normally, even when there was an error. Nobody would have gotten an idea that there was a problem, so neither process would have reason to raise an error message or write something to an error log. How many of these errors will be made before anyone catches the fact that something is wrong?

Lost update problems are much less dramatic than deadlock but potentially very damaging. Imagine the results of such an error in a bank’s software or in a stock exchange’s trading programs. The loss of money, the headaches, the lawsuit, the loss of confidence in the system …

We’ll talk about fixes for this problem soon, but for now just think how you would go about dealing with it.