Apparatus and method for achieving reduced overhead mutual exclusion and maintaining coherency in a multiprocessor system utilizing execution history and thread monitoring
First Claim
1. A mutual-exclusion apparatus for maintaining data coherency while concurrently reading and updating a current generation data element stored in first sites of a memory of a computer, the mutual-exclusion apparatus comprising:
- a first thread controlling the reading of the current generation data element;
a second thread controlling the updating of the current generation data element and storing the updated data element in second sites as a next generation data element;
a thread activity monitor producing and storing in the memory, execution history data indicative of states of the first and second threads; and
an element processor processing the current and next generation data elements in response to the execution history data that indicate the first and second threads have one of entered a predetermined state and passed through the predetermined state.
2 Assignments
0 Petitions
Accused Products
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.
339 Citations
24 Claims
-
1. A mutual-exclusion apparatus for maintaining data coherency while concurrently reading and updating a current generation data element stored in first sites of a memory of a computer, the mutual-exclusion apparatus comprising:
-
a first thread controlling the reading of the current generation data element; a second thread controlling the updating of the current generation data element and storing the updated data element in second sites as a next generation data element; a thread activity monitor producing and storing in the memory, execution history data indicative of states of the first and second threads; and an element processor processing the current and next generation data elements in response to the execution history data that indicate the first and second threads have one of entered a predetermined state and passed through the predetermined state. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. In a computer system, a method for providing mutual-exclusion between current and next generation data elements, the next generation data element being formed by updating while concurrently reading the current generation data element stored in first memory sites of a computer, the mutual-exclusion method comprising the steps of:
-
reading under control of a first thread the current generation data element; updating under control of a second thread the current generation data element to form and store in second memory sites the next generation data element; monitoring the first and second threads to produce execution history data indicative of states of the first and second threads; and processing the current and next generation data elements in response to execution history data that indicate the first and second threads have one of entered a predetermined state and passed through the predetermined state. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification