Distributed monitor concurrency control

Details Distributed monitor concurrency control Distributed monitor concurrency control

1998-11-24

2003-09-16

Banankhah, Majid (Department: 2127)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S241000, C709S241000, C709S201000

Reexamination Certificate

active

06622155

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer hardware and software, and more particularly to a system for thread synchronization in a distributed computing environment wherein multiple threads of execution span across different computing platforms.
2. Description of the Prior Art
The logical progression of executed steps in a microprocessor is called a “thread” of execution. Simple computer systems have a single microprocessor and an operating system that allows only one active thread of execution. Thus, software will execute in a serial fashion, with each operation running sequentially after the termination of the previous operation. This type of operating system becomes inefficient when system resources halt to allow a long calculation to finish executing.
For example, suppose that certain calculations were being performed on batches of data that were input by a data entry operator. In a system with a single thread of execution, the data entry operator would have to pause while each calculation was finished on the previous batch of data. It would be more efficient if the data entry operator could continuously input the data while calculations on the previous batch of data were executing in the background. Such a system would require multiple threads of execution: a first thread to process the input from the operator, and a second thread to perform the calculations on the previous batch of data.
In the example above, a multithreading scheme would be fairly simple to devise because it is unlikely that the first and second threads would interfere with each other. Each thread would execute on its own stack independently of the other. This is often called “unsynchronized” multithreading.
In a computer with a single microprocessor, unsynchronized multithreading may be accomplished by time-multiplexing the microprocessor. This means that the microprocessor, or CPU, divides its time between two or more stacks such that all stacks make some progress over time, without having the stacks explicitly call each other. The first stack would wait while execution proceeded on the second stack, and vice versa. As used herein, the term “concurrent threads” means that two or more threads are in various stages of execution concurrently. Concurrent threads may be executing one at a time in a time multiplexing scheme. Alternatively, a computer with parallel processors may have concurrent threads executing simultaneously.
There are a number of known techniques for time-multiplexing, including “preemptive” and “non-preemptive” multitasking. In a preemptive multitasking scheme, the operating system allocates time among the threads. In a non-preemptive scheme, the active thread controls the time at which it relinquishes execution.
In general, there is no assurance that multiple threads of execution can run concurrently without interfering with each other. For example, two threads of execution may access the same location in memory to store intermediate results. In this scenario, the first thread may store a value to memory, followed by the second thread over-writing a different value to the same location in memory. Thus, when the first thread retrieves the value it will corrupt the calculation in unpredictable ways. Resources that may be shared among concurrent threads, such as memory, must be protected in a manner that prevents corruption between the threads.
The process of assuring that concurrent threads do not interfere with each other is called “thread synchronization.” Modern operating systems that allow multitasking operations have various tools to accomplish thread synchronization. Some examples include locks, monitors, and request servers.
Locks are relatively simple programming constructs that protect shared resources. A lock must be “acquired” by a thread of execution before that thread can access the shared resource. Prior to gaining control of the shared resource, the thread must show evidence that it has acquired the lock, or alternatively, the entire system must respect a convention in which threads without locks refrain from accessing the shared resource. In a simple system, the shared resource may only allow one lock to issue at any time, thus preventing any concurrent access to the resource.
Locks can be difficult to use in a layered or nested architecture because the lock evidence must be explicitly supplied to allow access to the shared resource. This presents a problem when a first thread acquires a lock, then waits for results from a second thread which also needs access to the same resource. This scenario can lead to a “deadlock” in which the first and second threads are each waiting for the other, as described in the following example:
Suppose a method or procedure called “foo( )” acquires a lock on resource “R.” Subsequently, “foo( )” calls “goo( )” which also tries to acquire a lock on the resource R. The attempt by “goo( )” to acquire the lock will fail even though “goo( )” is operating on behalf of “foo( ).” Thus, even when method “foo( ).” has a lock, it can deadlock a system by calling a second method “goo( )” if both methods need the same resource R. A higher level concept, called a “monitor,” provides a solution to this type of nesting problem.
Local “monitors” are a well known technique for thread synchronization. They are fairly easy to use and map well to object-oriented systems. In certain respects, a local monitor can be viewed as a programming construct in which a lock is assigned to a thread. In contrast, a simple lock (as described in the example above) is typically assigned to a shared resource. The local monitor is associated with the thread's section of code in which shared access is performed. Each local monitor comprises a queue and a lock. As a thread proceeds into a monitor, the thread will either be assigned a spot on the queue, or will be granted access to the resource while other threads wait on the queue. In this manner, a lock does not have to be passed from thread to thread.
Another technique for thread synchronization involves a “request server.” A separate computing platform constitutes the request server, and clients to this server are the individual threads of execution. The server creates individual (local) threads of execution to handle each request from a client. Thus, the problems associated with distributed system concurrency control are reduced to a local problem of concurrency control where well known techniques can be applied. One of the drawbacks of this approach is the large overhead required to generate a new thread for each client request.
Several U.S. Patents are directed to the problem of thread synchronization. For example, U.S. Pat. No. 5,341,491 discloses an apparatus and method for ensuring that lock requests are serviced in a multiprocessor system. According to the disclosure, a lock queue includes a plurality of registers pipelined together, wherein lock requests only enter the lock queue if they are refused access to a shared resource a predetermined number of times.
U.S. Pat. Nos. 5,636,376 and 5,675,798 disclose a system and method for selectively and contemporaneously monitoring processes in a multiprocessing server. A status utility selectively accesses information to determine the status of the individual multiple processes executing on the server workstation. The information is of a granularity to identify processes which are hung up on semaphores, message queues, or the like.
U.S. Pat. No. 5,590,335 discloses a process for analysis of deadlocks in an operating system. The process includes the step of searching for any thread stopped on a lock, and further for the thread that holds that lock, and further up the chain until a cycle is found. In this manner, the user can reconstruct the cycle determining the deadlock.
U.S. Pat. No. 5,590,326 discloses a shard data management scheme using shared data locks for multi-threading. In this scheme, different shared data identifiers are assigned to different threads, and different locks are set up for different shared data

Affiliated with

Also associated with

Rating

Distributed monitor concurrency control does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Distributed monitor concurrency control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed monitor concurrency control will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3044853