Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1995-02-16
2003-01-14
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06507861
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the avoidance of deadlock in a multi-tasking environment and, more particularly, to a system and method for using interprocess communication to maximize background processing and avoid deadlock in a multi-threaded application running in a non-preemptive multi-tasking environment.
2. Discussion of Related Art
Computer application programs that utilize a “windows” environment are prevalent in today's market place. The use of windows allows a user to work in a multi-tasking environment in which several application programs may compete for a finite number of resources. Operating in a multi-tasking environment can create a number of problems, however.
For example, if an application program requests a resource, and if the resource is not available at that time, the application program enters a wait state. It may happen that the waiting application program will never again change state, because the resource it has requested is held by another waiting processes. This situation is called deadlock. To prevent deadlock, or recover from one if it occurs, the system may take some relatively extreme action, such as preemption of resources from one or more of the deadlocked application programs.
A set of processes is in a deadlock state when two or more processes in the set is waiting for an event that can only be caused by another process in the set. A deadlock situation can arise if and only if the following four conditions hold simultaneously in the system.
Mutual Exclusion. At least one resource is held in a nonshareable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.
Hold and Wait. There must exist a process that is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes.
No Preemption. Resources cannot be preempted. That is, a resource can only be released voluntarily by the process holding it, after the process has completed its task.
Cirular Weight. There must exist a set (p
0
, p
1
, . . . , p
n
) of waiting processes such that p
0
is waiting for a resource which is held by p
1
, p
1
is waiting for a resource which is held by p
2
, . . . , p
n-1
is waiting for a resource which is held by p
n
and p
n
is waiting for a resource which is held by p
0
.
All four conditions must hold for a deadlock to occur. By insuring that at least one of these conditions cannot hold, the occurrence of a deadlock can be prevented. For a more detailed description of the deadlock problem see Peterson J. and Siberschatz A., Operating System Concepts, Addison-Wesley Publishing Co., Inc. (1986).
In a windows environment, any application which consists of more than one component which voluntarily shares control of the processor risks starvation of all other components when any component has control of the processor. This situation results in poor background-processing performance in general, and can degenerate into deadlock when the component which has control requires input from another component. Deadlock occurs because the starved component is unable to run and provide the input, because the component which has control will not release until it receives this input from the starved component.
Microsoft® Windows provides a non-preemptive multi-tasking environment for running application programs. This means that several applications can share the processor in a sequential manner provided that each application is “well-behaved” and voluntarily gives up the processor periodically. The Microsoft® Windows operating system, for example, has no mechanism to detect or remedy deadlock or starvation situations that may arise if an application program is not well-behaved.
FIG. 1
is a conceptual representation of several application programs running in a Windows operating system (OS)
110
. The Windows operating system is a multi-tasking operating system. Multi-tasking means that more than one application program can run at a time. Non-preemptive means that once an application program, for example, application program A
120
is granted access by the Windows operating system
110
to the processor (not shown) it cannot be preempted by application programs B
130
, C
140
, or D
150
. Thus, while application program A
120
is running, all other application programs
130
,
140
,
150
are starved. Accepted Windows programming practices dictate that application programs
120
-
150
voluntarily give up access to the processor (i.e., the application program is well behaved). Thus, each application program receives a timeslice of time with the processor. A timeslice is a unit of time an operating system allows an application program to run. In a non-preemptive system, a timeslice has no pre-defined limit.
Once an application program
120
-
150
releases control of the processor, the Windows operating system
110
can then grant (schedule) another application program
120
-
150
access to the processor.
Some application programs provide their own internal non-preemptive multi-tasking through separate tasks, or threads within the application program. Note that a multi-tasker within an application program is similar to the multi-tasker found in the Windows operating system
110
. For example, one thread is responsible for accessing data on the disk, while another thread accesses data from the tape, and another thread interacts with the user to determine what operations to perform. The goal of this design is to provide quicker responses to user requests because the data is immediately available through “background” processing.
Threads have control of the processor during their timeslice, and communicate with other threads via message passing. This timeslicing between threads, and message passing between threads takes place within one application program
120
-
150
, during one Window operating system
110
timeslice.
The Windows operating system
110
provides application programs
120
-
150
with an interface to standard methods for communicating with the user, for example: dialog boxes, list boxes, scrollbars, edit controls, cursors, icons, etc. The user interface thread of an application program uses dialog boxes to obtain different types of information from the user. Dialog boxes as provided by the Windows application interface contain their own Windows message loop. A dialog box put up by an application program
120
-
150
is well-behaved, and yields to Windows software
110
allowing other application programs
120
-
150
to run. However, the message loop within the application program's dialog box receives all the Window software
110
messages for that particular application program. Thus, if the user interface thread of an application program places a dialog box on the screen, that dialog box will receive all messages for the application program, and no other threads within the application program are able to run until the dialog box is removed. This leads to starvation of other threads in the application program. No background processing is done by other threads in the application program while a dialog box has control, which can lead to deadlock.
For example, if the user wishes to print the contents of a tape directory, the user manager thread puts up a dialog box to allow the user to choose what to print, and to control the printing process. Once the user selects which directory to print, the user manager thread sends a request for each item in the directory to the tape manager thread. The tape manager thread would then return the name of each file to be printed. Due to the nature of a dialog box, the other threads within the application program will not run until the dialog box is removed. Thus, the tape manager thread will not receive a timeslice. With no timeslice, the tape manager thread cannot perform any background processing (such as reading the list of files from the tape). Since the dialog bo
Kiwimagi Gary G.
Nelson Ellen M.
Courtenay III St. John
Hewlett--Packard Company
LandOfFree
System and method for avoiding deadlock in a non-preemptive... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for avoiding deadlock in a non-preemptive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for avoiding deadlock in a non-preemptive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3048841