Asymmetric coherency protection

• US 7,424,496 B1
• Filed: 03/20/2002
• Issued: 09/09/2008
• Est. Priority Date: 03/20/2002
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Pardo, Ilan
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US10/103,415
• Time in Patent Office: 2,365 Days
• Field of Search: 707/2, 707/8, 707/103.B, 707200-204, 707/101, 709/225, 709/226, 711141-143
• US Class Current: 1/1
• CPC Class Codes: G06F 9/30101 Special purpose registers
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

Prior to updating a database entry, an update task invalidates a valid indicator (e.g., a bit) associated with the database entry. The update task waits for any other tasks (e.g., user tasks) that are accessing the database entry to complete their processing. In particular, a synchronization register holds a synchronization entry (e.g., a bit) for each user task that is created by a micro controller. The update task sets each synchronization entry of the synchronization register to a first value. As each user task completes its processing, the synchronization entry associated with the user task in the synchronization register is set to a second value (e.g., the synchronization bit is reset). The update task monitors the synchronization register, and, when each synchronization entry has been set to the second value, the update task performs its update of the database entry.

Claims

1. A process for updating a database entry in a computer storage, the process comprising operations of:

invalidating the database entry by changing a valid indicator which indicates whether the database entry is valid, the valid indicator being changed from a value which indicates that the database entry is valid to a value which indicates that the database entry is invalid;

obtaining an indication that one or more first tasks have completed one or more first processing operations after invalidating the database entry, wherein in each first processing operation, the one or more first tasks do not access the database entry without first checking the valid indicator to ascertain that the database entry is valid, and wherein in at least one first processing operation, the one or more first tasks are operable to check the valid indicator before invalidating the database entry but to finish reading the database entry after the database entry has been invalidated in the operation of invalidating the database entry; and

updating the database entry when said indication has been obtained.

2. The process of claim 1 wherein obtaining said indication comprises writing a first value to a computer storage location;

and obtaining an indication that the first value has been changed to a second value in said storage location.

3. The process of claim 2 wherein the first value is changed to the second value in response to the one or more first tasks completing the one or more first processing operations.

4. The process of claim 1 wherein invalidating the valid indicator, obtaining said indication, and updating the database entry are performed by one or more second tasks.

5. The process of claim 1 wherein the one or more first tasks are a plurality of the first tasks.

6. A computer system, comprising:

a memory to store software instructions; and

processor to execute the software instructions to perform a process for updating a database entry, the process comprising operations of;

invalidating the database entry by changing a valid indicator which indicates whether the database entry is valid, the valid indicator being changed from a value which indicates that the database entry is valid to a value which indicates that the database entry is invalid;

obtaining an indication that one or more first tasks have completed one or more first processing operations after invalidating the database entry, wherein in each first processing operation, the one or more first tasks do not access the database entry without first checking the valid indicator to ascertain that the database entry is valid, and wherein in at least one first processing operation, the one or more first tasks are operable to check the valid indicator before invalidating the database entry but to finish reading the database entry after the database entry has been invalidated in the operation of invalidating the database entry; and

updating the database entry when said indication has been obtained.

7. The system of claim 6 wherein obtaining said indication comprises:

writing a first value to computer storage location; and

obtaining an indication that the first value has been changed to a second value in said storage location.

8. The system of claim 7, wherein the first value is changed to the second value in response to one or more of the first tasks completing one or more of the first processing operations.

9. The system of claim 6, wherein invalidating the valid indicator, obtaining said indication, and updating the database entry is performed by one or more second tasks.

10. A computer implemented method for updating a database entry in computer storage, wherein the method comprising operations of:

invalidating the database entry by changing a valid indicator which indicates whether the database entry is valid, the valid indicator being changed from a value which indicates that the database entry is valid to a value which indicates that the database entry is invalid;

obtaining an indication that one or more first tasks have completed one or more first processing operations after invalidating the database entry, wherein in each first processing operation, the one or more first tasks do not access the database entry without first checking the valid indicator to ascertain that the database entry is valid, and wherein in at least one first processing operation, the one or more first tasks are operable to check the valid indicator before invalidating the database entry but to finish reading database entry after the database entry has been invalidated in the operation of invalidating the database entry; and

updating the database entry when said indication has been obtained.

11. A computer implemented process for updating a database entry in a computer storage medium, the process comprising at least two iterations, wherein each iteration comprising operations of:

determining if the database entry is valid;

if the database entry is valid, then;

(1) invalidating the database entry by writing a value to a valid indicator which indicates whether the database entry is valid;

(2) obtaining an indication that one or more first tasks have completed one or more first processing operations after the operation of invalidating the database entry, wherein in each first processing operation, the one or more first tasks do not access the database entry without first checking the valid indicator to ascertain that the database entry is valid, wherein in at least one first processing operation, the one or more first tasks are operable to check the valid indicator before the operation of invalidating the database entry but to finish reading the database entry after the database entry has been invalidated;

(3) updating the database entry when said indication has been obtained; and

if the database entry is invalid, then updating the database entry but omitting the operation of obtaining an indication and the operation of invalidating the data base entry for the database entry, wherein in at least one of the iterations establishes that the database entry associated with the at least one of the iterations is valid; and

in at least another one of the iteration establishes that the database entry associated with the at least the other one of the iteration is invalid.

12. A computer program product that includes a computer readable storage medium usable by a processor, the medium having stored thereon a sequences of instructions which, when executed by said processor, causes said processor to execute a process for updating a database entry, the process comprising at least two iterations, wherein each iteration comprising operations of:

determining if the database entry is valid;

if the database entry is valid, then;

(1) invalidating the database entry by writing a value to a valid indicator which indicates whether the database entry is valid;

(2) obtaining an indication that one or more first tasks have completed one or more first processing operations after the operation of invalidating the database entry, wherein in each first processing operation, the one or more first tasks do not access the database entry without first checking the valid indicator to ascertain that the database entry is valid, wherein in at least one first processing operation, the one or more first tasks are operable to check the valid indicator before the operation of invalidating the database entry but to finish reading the database entry after the database entry has been invalidated;

(3) updating the database entry when said indication has been obtained; and

if the database entry is invalid, then updating the database entry but omitting the operation of obtaining an indication and the operation of invalidating the data base entry for the database entry, wherein in at least one of the iterations establishes that the database entry associated with the at least one of the iterations is valid; and

in at least another one of the iteration establishes that the database entry associated with the at least the other one of the iteration is invalid.

13. The computer readable storage medium of claim 12 wherein the operation of updating the database entry is accompanied by validating the database entry.

14. A method for updating a database entry in a computer storage medium, the method comprising at least two iterations, wherein each iteration comprising operations of:

determining if the database entry is valid;

if the database entry is valid, then;

(1) invalidating the database entry by writing a value to a valid indicator which indicates whether the database entry is valid;

(2) obtaining an indication that one or more first tasks have completed one or more first processing operations after the operation of invalidating the database entry, wherein in each first processing operation, the one or more first tasks do not access the database entry without first checking the valid indicator to ascertain that the database entry is valid, wherein in at least one first processing operation, the one or more first tasks are operable to check the valid indicator before the operation of invalidating the database entry but to finish reading the database entry after the database entry has been invalidated;

(3) updating the database entry when said indication has been obtained; and

if the database entry is invalid, then updating the database entry but omitting the operation of obtaining an indication and the operation of invalidating the data base entry for the database entry, wherein in at least one of the iterations establishes that the database entry associated with the at least one of the iterations is valid; and

in at least another one of the iteration establishes that the database entry associated with the at least the other one of the iteration is invalid.

15. The method of claim 14 wherein the operation of updating the database entry is accompanied by validating the database entry.

16. The method of claim 14 wherein each first task processes network data units, and accesses the database to process the network data units.