Critical code processing management

Details Critical code processing management Critical code processing management

1998-12-16

2002-04-02

Von Buhr, Maria N. (Department: 2171)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C707S793000

Reexamination Certificate

active

06366946

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to electronic data processing software, and more specifically to processing highly contested critical areas of computer software.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawing hereto: Copyright© 1998, Microsoft Corporation, All Rights Reserved.
BACKGROUND OF THE INVENTION
Today many computer programs are intended to be run in multi-processor and/or multi-threaded environments. The advantages of such an environment include more efficient and faster execution of computer programs. This is due to the fact that multiple processors can perform tasks in parallel with one another, that is, the processors can work on multiple programs, or on multiple copies of the same program simultaneously.
There are times, however, when it is necessary to limit access to certain sections of computer programs to one process or thread at a time. A section of code that must be limited in this manner is what is known in the art as a “critical section”. Critical sections of code often serve as a gate keeper for controlling access to a particular resource or data structure. It is often the case that if multiple processes were allowed access to the critical section, a data structure will be corrupted or a deadlock situation will occur.
Previous systems have attempted to control access to critical sections through the use of an operating system provided semaphore having at least two states. A first state indicates that the section is free, that is, it is available for use by a process. A second state indicates that the critical section is currently in use. A process desiring to execute a critical section first checks the semaphore to see if any other process or thread is currently using the critical section. If another process is in the critical section, the process or thread blocks until the semaphore indicates the critical section is free. If no other process is using the critical section, the process or thread enters the critical section, and sets the semaphore to busy to keep other processes from entering until the current process is done with the critical section.
When a process or thread that was blocked by another process executing in the critical section becomes ready to run, a context switch typically occurs. A context switch is a sequence of instructions that are typically executed by an operating system that cause the system to switch execution from a current process to another process that is ready and waiting to run. In this case, the context switch is executed to allow the formerly blocked process to execute in the now free critical section.
Context switches are relatively expensive in terms of processor time. This is due to the fact that a relatively large amount of data must be manipulated in order to prepare the processor to run a different process or thread. In certain operating systems, context switches can take anywhere from 1000 to 10,000 instruction cycles to accomplish.
The table below illustrates a typical sequence in which two threads need to execute a critical section of code, and in which semaphores are used to control access to the critical section. The table shows the state of each process during their execution at four significant points in time labeled T1-T4.
TABLE 1
TIME
Thread 1
Thread 2
T1
Enters critical section
T2
Executes in critical section
Reaches critical section; waits.
T3
Leaves critical section
T4
Enters critical section
The period of time between T4 and T3, referred to as the “transition time”, can have a significant impact on the total throughput of processes and threads needing to execute the critical section. During the time period the operating system must block thread
2
until a processor becomes available to run the thread. Once a processor is available, the operating system must perform a context switch from whatever was running on the processor to thread
2
. Thus, the time period between T3 and T4 can be comparatively large. This makes the effective critical section execution time to be (T4-T1); that is, the critical section may be entered at most 1/(T4-T1) times per second.
In addition, the transition time may be large compared to (T3-T1), the actual amount of time spent inside the critical section. If there are many threads waiting for the critical section, i.e. the critical section is a highly contested critical section, then the transition time can be a dominant, limiting factor in overall throughput of the system.
Therefore, there is a need for a more efficient system for managing the processing of critical sections of a computer program.
SUMMARY
The above-identified problems, shortcomings and disadvantages with prior systems, as well as other problems, shortcoming and disadvantages, are solved by the present invention, which will be understood by reading and studying the specification and the drawings.
The system provides a highly efficient mechanism for processing critical sections of code. Executable units such as threads, processes, and fibers place data describing work to be performed by the critical section in a data packet. The data packets are collected in a list of packets. The first thread to enter the critical section of code executes all of the work units on the list, thereby executing at least some of the work units on behalf of other waiting threads.
The system provides for higher throughput and efficiency than previous systems, because the blocked threads tend to resume execution sooner, thereby reducing the transition time period.
The invention includes systems, methods, computers, and computer-readable media of varying scope. Besides the embodiments, advantages and aspects of the invention described here, the invention also includes other embodiments, advantages and aspects, as will become apparent by reading and studying the drawings and the following description.


REFERENCES:
patent: 5138713 (1992-08-01), Loten
patent: 5283896 (1994-02-01), Temmyo et al.
patent: 5289588 (1994-02-01), Song et al.
patent: 5504898 (1996-04-01), Klein
patent: 5515538 (1996-05-01), Kleiman
patent: 5630136 (1997-05-01), Davidson et al.
patent: 5742825 (1998-04-01), Mathur et al.
patent: 5832484 (1998-11-01), Sankaran et al.
patent: 5852731 (1998-12-01), Wang et al.
patent: 5948097 (1999-09-01), Glew et al.
patent: 5995998 (1999-11-01), Furlani et al.
patent: 6021425 (2000-02-01), Waldron, III et al.
patent: 6061709 (2000-05-01), Bronte
patent: 6006247 (2000-09-01), Browning et al.
patent: 6119115 (2000-09-01), Barr
patent: 6167423 (2000-12-01), Chopra et al.
patent: 6212542 (2001-04-01), Kahle et al.
patent: 6247025 (2001-06-01), Bacon

Affiliated with

Also associated with

Rating

Critical code processing management does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Critical code processing management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical code processing management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2873598