Deadlocks

Consider sequential programs of the form:

Request resource A
Request resource B
Perform action using A and B
Release resource B
Release resource A

A particular program might use a printer (resource A) and a file (resource B) in order to print the file.

If several such programs P1,P2,P3 ... operate at the same time, then the first one to execute will block the others until the resources are released, and the programs will execute in turn. There will be no problem. It makes no difference whether a uni-processor or a multi-processor system is used, as it's the allocation of the resources which determines the order of execution.

Note, however, that programmers are, in general, not constrained to write programs in a particular way, or even if there are guidelines, then some may differ from the guidelines. A variant of the previous program may be:

Request resource B
Request resource A
Perform action using A and B
Release resource A
Release resource B

The resources A and B are the same as in the previous example – not simply dummy variables, as otherwise the programs are identical.

As before, if there are several such programs, Q1,Q2,Q3 which run at the same time using resources as before, there will be no problem.

However, if several of the Ps are set to run at the same time as several of the Qs, then a deadlock condition can arise. Note that the deadlock need not arise, but may.

P: Request resource A
Q: Request resource B
Q: Request resource A (blocked by P)
P: Request resource B (blocked by Q)
...

Now neither P nor Q can proceed¹.

This is one kind of example where programs may demonstrate incompatibility.

Interface incompatibility

Another example of a different kind would be where one software component provides service to another. The incompatibility could be as simple as a change in the order of parameters between the software component requesting service, and the component providing the service. This would be a kind of interface incompatibility. This might be considered a bug, but could be very hard to detect in some systems. Some interface incompatibilities can easily be detected during the build stage, particularly for strongly typed systems, others may be hard to find and may only be detected at run time, while others may be almost impossible to detect without a detailed program analysis.

Consider the following example:

 Component P calls component Q with parameters x and y. For this example, y may be an integer.

 Q returns f(x) which is desired and never zero, and ignores y.

A variant of Q, Q' has similar behaviour, with the following differences:

 if y = 100, then Q' does not terminate.

If P never calls Q with y set to 100, then using Q' instead is a compatible computation. However if P calls Q with y set to 100, then using Q' instead will lead to a non-terminating computation.

If we assume further that f(x) has a numeric value, then component Q'' defined as:

 Q'' behaves as Q except that
 if y = 100 then Q'' does not terminate
 if y = 101 then Q'' returns 0.9 * f(x)
 if y = 102 then Q'' returns a random value
 if y = 103 then Q'' returns 0.

may cause problem behaviour. If P now calls Q'' with = 101, then the results of the computation will be incorrect, but may not cause a program failure. If P calls Q'' with y = 102 then the results are unpredictable, and failure may arise, possibly due to divide by zero or other errors such as arithmetic overflow. If P calls Q'' with y= 103 then in the event that P uses the result in a division operation, then a divide by zero failure may occur.

This example shows how one program P1 may be always compatible with another Q1, but that there can be constructed other programs Q1' and Q1'' such that P1 and Q1' are sometimes incompatible, and P1 and Q1'' are always incompatible.

Performance incompatibility

Sometimes programs P and Q can be running on the same computer, and the presence of one will inhibit the performance of the other. This can particularly happen where the computer uses virtual memory. The result may be that disk thrashing occurs, and one or both programs will have significantly reduced performance. This form of incompatibility can occur if P and Q are intended to cooperate, but can also occur if P and Q are completely unrelated but just happen to run at the same time. An example might be if P is a program which produces large output files, which happen to be stored in main memory, and Q is an anti-virus program which scans many files on the hard disk. If a memory cache is used for virtual memory, then it is possible for the two programs to interact adversely and the performance of each will be drastically reduced.

For some programs P and Q their performance compatibility may depend on the environment in which they are run. They may be substantially incompatible if they are run on a computer with limited main memory, yet it may be possible to run them satisfactorily on a machine with more memory. Some programs may be performance incompatible in almost any environment.