Mutual exculsion system and method for restarting critical sections of code when preempted during a critical section

• US 6,697,834 B1
• Filed: 12/01/1999
• Issued: 02/24/2004
• Est. Priority Date: 12/01/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Dice, David A.
• Primary Examiner(s): Wiley, David
• Assistant Examiner(s): Avellino, Joseph E
• Application Number:
  US09/452,571
• Time in Patent Office: 1,546 Days
• Field of Search: 710/260, 709/100, 709/102, 709/107, 709/108
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A mutual exclusion arrangement is disclosed for use in connection with a computer, the computer being 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.

Claims

1. A mutual exclusion arrangement for use in connection with a computer, the computer being configured to execute at least one program having at least one thread in a series of time slots, the mutual exclusion arrangement comprising:

A. associated with said computer, an operating system including a signal generator configured to generate a signal, in response to detection of a non-restorable trap indicator being set by the at least one thread, for provision to said at least one thread when the computer initiates processing of said at least one thread in one of said time slots, the signal generator including;

the non-restorable trap indicator having a set condition and a clear condition,

a control module configured to, in response to the end of a time slot, enable the at least one thread to resume execution, the control module being further configured to, before enabling the at least one thread to resume execution, test the condition of the non-restorable trap indicator and, if it is in the set condition, trap, and

a trap handler configured to, in response to a trap by said control module, generate said signal; and

B. associated with said at least one thread, a signal handler configured to, in response to said 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 said section, and otherwise enable said thread to begin execution subsequent to previously-executed code.

2. A mutual exclusion arrangement as defined in claim 1 in which said program has a plurality of threads, the computer being configures to execute said threads in said time slots in an interleaved manner.

3. A mutual exclusion arrangement as defined in claim 2 in which the computer is configured to execute said threads in at most one series of time slots.

4. A mutual exclusion method of use in connection with a computer, the computer being configured to execute at least one program having at least one thread in a series of time slots, the mutual exclusion method comprising the steps of:

A. enabling said computer to generate a signal, in response to detection, by an operating system of the computer, of a non-restorable trap indicator being set, by the at least one thread, for provision to said at least one thread when the computer initiates processing of said at least one thread in one of said time slots;

B. enabling, by the at least one thread, said computer to condition the non-restorable trap indicator to a set condition;

C. before enabling the at last one thread to resume execution, test the condition of the non-restorable trap indicator, by the operating system of the computer, and, if it is in the set condition, trap;

D. in response to the trap, generate said signal;

E. following a return from said trap, transfer control to said at least one thread;

F. enabling said at least one thread to, in response to said 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, begin execution at a beginning of said section, and otherwise begin execution subsequent to previously-executed code.

5. A mutual exclusion method as defined in claim 4 in which said program has a plurality of threads, the computer being enabled to execute said threads in said time slots in an interleaved manner.

6. A mutual exclusion method as defined in claim 5 in which the computer is configured to execute said threads in at most one series of time slots.

7. A computer program product for use in connection with a computer to provide a mutual exclusion arrangement, the computer being configures to execute at least one program having at least one thread in a series of time slots, the computer program product comprising a machine readable medium having encoded thereon:

A. for association in connection with said computer, an operating system having a signal generator module configured to enable said computer to generate a signal, in response to detection of a non-restorable trap indicator being set by the at least one thread, for provision to said at least one thread when the computer initiates processing of said at least one thread in one of said time slots, the signal generator module including;

the non-restorable trap indicator module having a set condition and a clear condition,

a control module configured to enable said computer to, in response to the end of a time slot, enable the at least on thread to resume execution, the control module being further configured to enable said computer to, before enabling the at least one thread to resume execution, test the condition of the non-restorable trap indicator and, if it is in the set condition, trap,

a trap handler module configured to enable said computer to, in response to a trap by said control module, generate said signal; and

B. for association in connection with said at least one thread, a signal handler module configured enable said computer, in response to said signal, to 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 said section, and otherwise enable said thread to begin execution subsequent to previously-executed code.

8. A computer program product as defined in claim 7 in which said program has a plurality of threads, the computer being configured to execute said threads in said time slots in an interleaved manner.

9. A computer program product as defined in claim 8 in which the computer is configured to execute said threads in at most one series of time slots.

10. In a thread processed by a computer having an operating system separate from the thread, a method for recovering from a preemption comprising:

in a first time slot;

setting a state of a non-restorable trap indicator while executing, and

experiencing a preemption, provided by the operating system, while executing; and

in a second time slot;

receiving a signal from the operating system in response to detection, by the operating system, of the non-restorable trap indicator being set by the thread in the first-time slot, the signal indicating preemption of execution of the thread in the first time slot,

in response to receiving the signal, detecting if the preemption, experienced by the thread, occurred during execution of a critical section,

when detecting that the preemption, experienced by the thread, occurred during execution of a critical section, enabling the computer to resume execution of the thread at the beginning of the critical section, and

when detecting that the preemption, experienced by the thread, occurred during execution of a non-critical section, enabling the computer to resume execution of the thread at the last instruction completed prior to the preemption.

11. The method of claim 10 wherein the step of receiving further comprises calling a signal handler to handle the signal and wherein the step of detecting comprises detecting, by the signal handler, if the preemption, experienced by the thread, occurred during execution of a critical section.

12. In a computer having an operating system and a thread, separate from the operating system, a method for preempting and resuming execution of the thread comprising:

in a first time slot

executing the thread;

receiving, from the thread, setting of a non-restorable trap indicator associated with the computer;

receiving an interrupt indicating an end to the first time slot;

preempting execution of the thread in response to receiving the interrupt; and

in a second time-slot;

detecting setting of the non-restorable trap indicator by the thread in the first time slot;

transmitting a signal to the thread indicating preemption of execution of the thread in the first time slot;

resuming execution of the thread at the beginning of the critical section in response to the thread detecting, based upon the signal, that the preemption, experienced by the thread, occurred during execution of a critical section, and

resuming execution of the thread at the last instruction completed prior to the preemption in response to the thread detecting, based upon the signal, that the preemption, experienced by the thread, occurred during execution of a non-critical section.

13. The method of claim 12 wherein the step of preempting comprises, saving, by the operating system, a state of the thread within a memory associated with the computer.

14. The method of claim 12 further comprises:

trapping, by the operating system, in response detecting setting of the non-restorable trap indicator by the thread; and

calling a trap handler, by the computer, to generate a signal to the thread indicating preemption of execution of the thread in the first time slot.

15. A computerized device comprising:

at least one communications interface;

a processor; and

an interconnection mechanism coupling the at least one communications interface and the processor;

wherein the processor is configured to;

in a first time slot

execute a thread;

receive, from the thread, setting of a non-restorable trap indicator associated with the computer;

receive an interrupt indicating an end to the first time slot;

preempt execution of the thread in response to receiving the interrupt; and

in a second time slot;

detect setting of the non-restorable trap indicator by the thread in the first time slot;

transmit a signal to the thread indicating preemption of execution of the thread in the first time slot;

resume execution of the thread at the beginning of the critical section in response to the thread detecting, based upon the signal, that the preemption, experienced by the thread, occurred during execution of a critical section, and

resume execution of the thread at the last instruction completed prior to the preemption in response to the thread detecting, based upon the signal, that the preemption, experienced by the thread, occurred during execution of a non-critical section.