Design  | SFC  |  NOS  |  Code |  Diary  | WWW |  Essay |  Cisco | [Home]

 

 

[Bill's Home Page]
[ Old page]

Essays

One of the best-known software errors occurred on 22 July 1962 when the Mariner I rocket had to be blown-up, after it followed an erratic path after it took off. It was caused by a single incorrect character in a FORTRAN statement for the motion equations.
In 1963, ANSI defined the 7-bit ASCII standard code for characters. At the same time IBM had developed the 8-bit EBCDIC code which allowed for up to 256 characters, rather than 128 characters for ASCII. It is thought that the 7-bit code was used for the standard as it was reckoned that eight holes in punched paper tape would weaken the tape. Thus the world has had to use the 7-bit ASCII standard, which is still popular in the days of global communications.
Key characters to remember are:
'A' 41h 0100 0001
'a' 61h 0110 0001
'0' 30h 0011 0000
LF 0Ah 0000 1010
CR 0Dh 0000 1101
Mastering Comput-ing, W.Buchanan, Palgrave

Isn't that interesting?

 


 


 

 

 

 

 

 

 

Process Deadlock: The Deadly Embrace

12 July 2001 WORK IN PROGRESS!

e've all seen deadlock occurring in real-life, special with automobiles. Figure 1 illustrates a typical case of deadlock. In this case two cars are blocking the junction (at A and D), and do not allow any of the other cars behind them to move. Unfortunately both automobiles cannot move as there are automobiles blocking their entry into the junction. The only way to clear the deadlock, apart from the two cars who are turning into the junctions to give up and go straight ahead, is for one of the automobiles which is blocking one of the junctions to reverse. Unfortunately, in this case, they cannot, as there are automobiles behind them. This is a deadly embrace. In resource terms, both of the car lanes of the main road has one of the junctions, and requires the other, but none of the car lanes can give their lane up.


Figure 1 Deadlock on a road junction (© billatnapier)


In process terms, resource deadlock occurs when Process 1 holds Resource A, and Process 2 holds Resource B, but Process 1 wants to gain access to Resource B, and vice-versa. Each process then waits for the other to yield their exclusive access to their resource. This is a deadly embrace. A typical problem can occur when data buffers can become full. For example a print spooler can be setup so that it must receive the full contents of a print file, before it will actually send it to the printer. If print buffer is receiving print data from several sources, it can fill up the buffer before any of the print jobs have completed. The only way round this problem would be to increase the data buffer size, which can be difficult.
The four conditions that must occur for deadlock to occur are:

Mutual exclusion condition. This is where processes get exclusive control of required resources, and will not yield the resource to any other process.

Wait for condition. This is where processes keep exclusive control of acquired re-sources while waiting for additional resources.

No pre-emption condition. This is where resources cannot be removed from the proc-esses which have gained them, until they have completed their access on them.

Circular wait condition. This is a circular chain of processes on which each process holds one or more resources that are requested by the next process in the chain.

In our example of deadlock in Figure 1 we can see that this passes all of these conditions. A car blocking the junction defines mutual exclusion, and since the cars cannot move away from the junction (in the deadlock case) there will be a condition for wait and pre-emption. As both automobile lanes are waiting for each other, we have a circular wait. Note that deadlock may occur very infrequently, but when it does occur it normally requires some form of user input, to try and recover the situation. In the case of the automobile deadlock, we would need someone to make directions as to the best plan to overcome the deadlock (possibly, a traffic policeman).

Deadlock avoidance
If possible processes should run without the problem of deadlock, as systems normally require a reboot to clear the problem. One of the best-known avoidance algorithms is the Banker Algorithm, which tries to avoid deadlock by estimating the amount of a given resource that processes are likely to require, in order to run completion. It is typically applied to define the amount of resources of the same type, but can be extended to resource pools with differing resource types. In our automobile deadlock, we could have applied the same principal, in that an automobile is not allow to turn to go into the junction, unless both junctions can be cleared. Thus if one automobile could not get into the junction, then the other automobile who wants to turn into the other junction would not be allow to enter the junction, and would have to proceed without turning into the junction. For example let's say that A is allowed to wait at the junction, while there is an automobile waiting at junction F. It will be allowed to do this, as deadlock will be avoided if there is no automobile turning at D. If this continues, but an automobile now request to turn into C, and its path is block, then it will not be allowed to do this as it can cause deadlock.

Chapter 6, Mastering Computing, W.Buchanan, Palgrave.

Comments on this essay

If you've got any comments on this essay (no matter if you agree or disagree with it), please send them to me using the form below.

Details

Name (Surname, First Name):

[Not required]

E-mail:


Your comment

 

Note your comments may be published to a comments pages, but none of your details will be added to the comment, just the date that it was sent. Thank you.