Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-12-01
2004-02-24
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S241000
Reexamination Certificate
active
06697834
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital computer systems, and more particularly to systems and methods for facilitating the synchronization of access to variables and other resources which may be shared among a plurality of threads of execution in a digital computer system.
BACKGROUND OF THE INVENTION
Computers process programs in one or more threads. In a computer having a plurality of processors, a plurality of threads can be executed in parallel, with each processor executing a thread. If there are more threads than the number of processors, at least one of the processors will execute a plurality of threads generally in an interleaved basis in a plurality of successive time slots. In a uni-processor computer, that is, a computer having a single processor, the processor will also execute the threads generally in an interleaved basis in a plurality of time slots.
Typically in multi-threaded programs, a thread will use a mutual exclusion mechanisms to avoid interference from and data race conditions with other threads. As an example of the utility of a mutual exclusion mechanism, consider code along the lines of Code Segment 1, which depicts code for a thread comprising a routine “getTicket” in which the value of a variable “Ticket” is incremented:
Code Segment 1
(1)
Tock$getTicket
(2)
save %sp, −64, %sp
!! routine enter
(3)
prolog
(4)
ld
[%i0].ObjectLock, %10
!! get lock variable
(5)
call
mutex_enter
!! begin synchronization
(6)
mov
%10, %o0
(7)
ld
[%i0].Ticket, %o0
!! load variable “Ticket”
(8)
add
%o0, 1, %o0
!! increment variable
“Ticket”
(9)
st
%o0, [%i0].Ticket
!! store variable “Ticket”
(10)
call
mutex_exit
!! end synchronization
(11)
mov
%10, %o0
(12)
ret
!! routine exit
(13)
epilog
(14)
restore
In Code Segment 1, the code is illustratively in the SPARC instruction set (reference SPARC International, Inc [David L. Weaver and Tom Germond (eds)], The SPARC Architecture Manual Version 9 (Prentice-Hall, 1994)).
In Code Segment 1, the getTicket routine includes a “critical section” comprising lines (
7
) through (
9
) which are to be executed as an atomic “read-modify-write” operation to enable the value of the variable “Ticket” to be incremented. To ensure that the operation is performed in an atomic manner, without variable “Ticket” being accessed by another thread before the one thread has finished executing the critical section, the getTicket routine makes use of a “mutex” (“mutual exclusion”) mechanism to synchronize access to the variable “Ticket.” The mutual exclusion mechanism ensures that, while the thread which includes the getTicket routine is executing the routine, only that thread will be able to access and perform operations in connection with the variable Ticket. In particular, line (
5
) (“call mutex-enter”) initiates the synchronization and line (
10
) (“call mutex_exit”) terminates synchronization. The code in both of these lines represent calls to the operating system, which locks the variable “Ticket” for the thread which includes the getTicket routine in response to the mutex_enter call, and unlocks the variable “Ticket,” making it available to other threads, in response to the mutex_exit call. After the variable “Ticket” has been locked in response to the mutex_enter call, and before the variable “Ticket” is unlocked in response to the mutex_exit call, the getTicket routine enables the variable “Ticket” to be retrieved from the computer's memory and loaded into one of the processor's internal registers (line
7
), incremented (line
8
) and stored back into the computer's memory (line (
9
)).
The benefit of the synchronization will be clear from the following. If, for example, the thread's time slot ends after the variable “Ticket” has been retrieved from the memory and loaded into an internal register, and before the value as incremented by the getTicket routine has been stored in the memory, another thread retrieves the variable “Ticket,” increments its value by some amount and stores the value as incremented by that thread in the memory, when the thread (that is, the thread executing the getTicket routine) stores the value as incremented by it in the memory, it will over-write the value as stored by the other thread. Accordingly, the value of the variable “Ticket” as retrieved by the other thread will correspond to the original, non-incremented value, instead of the incremented value which presumably was the value that the other thread was to have processed. More important, however, is that, since the thread that is executing the getTicket routine has over-written the value as stored by the other thread, the value as processed by the other thread will not be reflected in subsequent processing operations. However, by synchronizing access to the variable “Ticket,” the thread which executes the getTicket routine can forbid the other thread from accessing the variable “Ticket” until after the value has been retrieved, incremented and stored in the memory, even if those operations occur in different time slots. This may delay operations by the other thread, since the other thread will need to wait until after the thread that is executing the getTicket routine has finished operating with the variable and ended synchronization, but it will ensure that the processing operations take place in the correct order.
However, use of synchronization primitives such as the “mutex_enter” and “mutex_exit” themselves incur some cost. Since the synchronization primitives require calls to the operating system kernel, they can result in relatively long processing times. U.S. patent application Ser. No. 09/174,278, filed Oct. 16, 1998, in the name of David Dice, et al., and entitled System And Method For Synchronizing Access To Shared Variables In A Virtual Machine In A Digital Computer System, and assigned to the assignee of the current convention, describes a wait-free synchronization arrangement for facilitating synchronization by enabling one thread to use a compare and swap instruction to detect when the value of a variable which may be accessed by multiple processes or threads has been changed by another thread while the one thread has been executing a critical section. While that arrangement can facilitate synchronization, it will be appreciated at one such compare and swap instruction will be used each variable requiring synchronization during execution of the critical section, and, if multiple variables require synchronization, then a corresponding number of compare and swap instruction will be used.
SUMMARY OF THE INVENTION
The invention provides a new and improved system and method for facilitating the synchronization of access to variables and other resources which may be shared among a plurality of threads of execution in a digital computer system.
In brief summary, the invention provides, in one embodiment, a mutual exclusion arrangement for use in connection with a computer. The computer is configured to execute at least one program having at least one thread in a series of time slots. The mutual exclusion arrangement includes, associated with the computer, a signal generator and, associated with the at least one thread, a signal handler. The signal generator is configured to generate a signal for provision to the at least one thread when the computer initiates processing of the at least one thread in one of the time slots. The signal handler is configured to, in response to the signal, determine whether the thread, when it begins execution in the time slot, will be executing a section of code that is to be executed in an atomic manner, and, if so, enable the thread to begin execution at a beginning of the section, and otherwise enable the thread to begin execution subsequent to previously-executed code.
The arrangement effectively provides a form of mutual exclusion, similar to that provided by the synchronization primitives such as mutex
Avellino Joseph E
Chapin & Huang LLC
Chapin, Esq. Barry W.
Sun Microsystems Inc.
Wiley David
LandOfFree
Mutual exculsion system and method for restarting critical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mutual exculsion system and method for restarting critical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mutual exculsion system and method for restarting critical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310010