Apparatus and method for achieving reduced overhead mutual exclusion and maintaining coherency in a multiprocessor system utilizing execution history and thread monitoring

• US 6,219,690 B1
• Filed: 11/01/1996
• Issued: 04/17/2001
• Est. Priority Date: 07/19/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Slingwine, John D., McKenney, Paul E.
• Primary Examiner(s): Banankhah, Majid
• Assistant Examiner(s): LAO, SUE X
• Application Number:
  US08/742,987
• Time in Patent Office: 1,628 Days
• Field of Search: 709/102, 709/107, 709/108, 709/100
• US Class Current: 718/102
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A substantially zero overhead mutual-exclusion apparatus and method (90, 120) is provided that allows concurrent reading and updating data while maintaining data coherency. That is, a data reading process executes the same sequence of instructions that would be executed if the data were never updated. Rather than depending exclusively on overhead-imposing locks, this mutual-exclusion mechanism tracks an execution history (138) of a thread (16, 112) to determine safe times for processing a current generation (108, 130, 131) of data updates while a next generation (110, 132, 133) of data updates is concurrently being saved. A thread is any locus of control, such as a processor. A summary of thread activity (106, 122) tracks which threads have passed through a quiescent state after the current generation of updates was started. When the last thread related to the current generation passes through a quiescent state, the summary of thread activity signals a callback processor (104, 124) that it is safe to end the current generation of updates. The callback processor then processes and erases all updates in the current generation. The next generation of updates then becomes the current generation of updates. The callback processor restarts the summary of thread activity and initiates a new next generation of updates. All data-updating threads pass through a quiescent state between the time they attempt to update data and the time the data are actually updated.

Claims

1. A method of using an updater thread to initiate a change in mode of operation of a computer system, the method comprising the following steps:

providing an updater thread that updates a shared data element;

with the updater thread;

setting a shared data element that other threads check to indicate to such threads a new mode of operation;

p1 using a summary of thread activity to determine when other threads that are responsive to the new mode of operation have passed through a quiescent state since the shared data element was set; and

continuing operation of the updater thread in the new mode after it is determined that the other threads have passed through a quiescent state, such other threads proceeding in operation without interruption from the updater thread; and

simultaneously performing the following steps with each of the other threads;

checking the shared data element without using mutual exclusion; and

continuing a thread'"'"'s execution in the mode of operation indicated by the shared data element.

2. The method of claim 1 including registering a callback that notifies the updater thread when the other threads have passed through a quiescent state.

3. A computer-readable medium for storing a computer program comprising instructions for executing the method of claim 1.

4. A computer system in accordance with the method of claim 1.

5. Apparatus for using an updater thread to initiate a change in mode of operation of a computer system, comprising:

means for providing an updater thread that updates a shared data element;

means for using the updater thread for;

setting a shared data element that other threads check to indicate to such threads a new mode of operation;

using a summary of thread activity to determine when other threads that are responsive to the new mode of operation have passed through a quiescent state since the shared data element was set; and

continuing operation of the updater thread in the new mode after it is determined that the other threads have passed through a quiescent state, such other threads proceeding in operation without interruption from the updater thread; and

means for simultaneously performing the following steps with each of the other threads;

checking the shared data element without using mutual exclusion; and

continuing a thread'"'"'s execution in the mode of operation indicated by the shared data element.

6. The apparatus of claim 5 including registering a callback that notifies the updater thread when the other threads have passed through a quiescent state.