Method and apparatus for crash safe enforcement of mutually exclusive access to shared resources in a multitasking computer system

Claim 2

A computer system comprising: at least one processing unit; a plurality of shared resources, including a memory unit, accessible by said at least one processing unit; a plurality of semaphore records stored in said memory unit, each of said semaphore records associated with one of said plurality of shared resources, wherein each of said semaphore records comprises: a) availability indicia means for indicating whether the semaphore record is available, b) owner identification means for registering ownership of the semaphore record, and c) cleanup indicia for indicating whether the semaphore record is being evaluated by a cleanup routine; a plurality of processes executing on said plurality of processing units, said processes requesting and acquiring exclusive access to said plurality of shared resources by requesting and acquiring ownership of said semaphore records; and a plurality of semaphore access records stored in said memory unit, each of said semaphore access records associated with one of said plurality of processes, for identifying a semaphore record which said process associated with said semaphore access record wants to acquire ownership of; wherein said cleanup routine comprises means for determining whether a semaphore record is owned by a process that has crashed by using information in said semaphore records and said semaphore access records and means for resetting the availability indicia of a semaphore record when the semaphore record is owned by a process that has crashed.

Claim 3

The apparatus of claim 1 further comprising: means for storing identification of a semaphore record in a semaphore access record associated with a process before said process attempts to acquire said semaphore record; and means for storing identification of a process in the owner identification of a semaphore record after said process has acquired ownership of the semaphore record.

Claim 4

The apparatus of claim 1 further comprising: means for removing identification of a process from the owner identification of a semaphore record before said process releases ownership of said semaphore record; and means for removing identification of a semaphore record from a semaphore access record associated with a process after said process releases ownership of said semaphore record.

Claim 5

The apparatus of claim 1 further comprising: means for preventing a process from acquiring a semaphore record when said cleanup indicia of said semaphore record indicates that said semaphore record is being evaluated by said cleanup routine.

Claim 6

A crash safe system for enforcing mutually exclusive access to shared data in a computer system comprising: at least one processing unit; a memory unit connected to said at least one processing unit for storing a plurality of data structures and a semaphore access structure and a semaphore structure; a plurality of semaphore records, each associated with one of said plurality of data structures, comprising availability indicia for indicating whether said semaphore record is available, said semaphore records being stored in said semaphore structure in said memory unit; a plurality of semaphore access records stored in said semaphore access structure in said memory unit; a plurality of processes executing on said at least one processing unit, said processes requesting and acquiring exclusive access to said data structures by requesting and acquiring ownership of said semaphore records; means for maintaining an underestimate of semaphore ownership in said memory unit; and means for maintaining an overestimate of semaphore ownership in said memory unit; and cleanup means operating on said semaphore records and said semaphore access records for determining whether a semaphore record is owned by a process that has crashed by evaluating said underestimate of semaphore ownership and said overestimate of semaphore ownership and for resetting the availability indicia of a semaphore record when the semaphore record is owned by said process that has crashed.

Claim 7

A crash safe system for enforcing mutually exclusive access to shared data in a computer system comprising: at least one processing unit; a memory unit connected to said at least one processing unit for storing a plurality of data structures and a semaphore access structure and a semaphore structure; a plurality of semaphore records, each associated with one of said plurality of data structures, comprising availability indicia for indicating whether said semaphore record is available, said semaphore records being stored in said semaphore structure in said memory unit; a plurality of semaphore access records stored in said semaphore access structure in said memory unit; a plurality of processes executing on said at least one processing unit, said processes requesting and acquiring exclusive access to said data structures by requesting and acquiring ownership of said semaphore records; means for maintaining an underestimate of semaphore ownership in said memory unit; and means for maintaining an overestimate of semaphore ownership in said memory unit; and cleanup means operating on said semaphore records and said semaphore access records for determining whether a semaphore record is owned by a process that has crashed by evaluating said underestimate of semaphore ownership and said overestimate of semaphore ownership and for resetting the availability indicia of a semaphore record when the semaphore record is owned by said process that has crashed.

Claim 8

The apparatus of claim 5 wherein said means for maintaining an overestimate of semaphore ownership further comprises: means for storing in said memory unit an indication that a process wants to acquire a semaphore record, prior to said process requesting ownership of said semaphore record; and means for removing from said memory unit said indication that a process wants to acquire a semaphore record, subsequent to said process releasing ownership of said semaphore record.

Claim 9

The apparatus of claim 5 wherein said means for maintaining an underestimate of semaphore ownership further comprises: means for storing in said memory unit an identification of a process which owns a semaphore record, subsequent to said process acquiring ownership of said semaphore record; and means for removing from said memory unit said identification of a process which owns a semaphore record, prior to said process releasing ownership of said semaphore record.

Claim 10

The apparatus of claim 5 further comprising: means for terminating a process which has not progressed for at least a predetermined period of time.

Claim 11

The apparatus of claim 5 further comprising: a plurality of cleanup indicators stored in said memory unit for indicating whether said cleanup means is operating on said plurality of semaphore records.

Claim 12

The apparatus of claim 9 further comprising: means for preventing a process from acquiring ownership of a semaphore record when one of said plurality of cleanup indicator indicates that said cleanup means is operating on said semaphore record.

Claim 13

The apparatus of claim 5 further comprising: means for initiating said cleanup means when a semaphore record has been unavailable for at least a predetermined time period.

Claim 16

The method of claim 12 wherein said step of initiating the execution of a cleanup routine for a semaphore further comprises the step: initiating the execution of a cleanup routine for a semaphore when said semaphore has been unavailable for at least a predetermined time period.

Claim 17

The method of claim 12 wherein said first routine further comprises the steps: determining if said cleanup routine is being executed for a semaphore; and waiting for said cleanup routine to terminate before acquiring said semaphore whenever a cleanup routine is being executed for a semaphore.

Claim 18

The method of claim 12 wherein said cleanup routine comprises the steps: generating an overestimate set of processes which want to acquire the semaphore by employing means for maintaining an overestimate of semaphore ownership in said memory unit including means for storing in said memory unit an indication that a process wants to acquire a semaphore record, prior to said process requesting ownership of said semaphore record and means for removing from said memory unit said indication that a process wants to acquire a semaphore record, subsequent to said process releasing ownership of said semaphore record; removing a process from the overestimate set when said process no longer wants to acquire the semaphore or said process is dead; determining if the semaphore is held by a process when said overestimate set is empty; and recovering said resource associated with said semaphore and releasing said semaphore whenever said semaphore is held by a process when said overestimate set is empty.

Claim 19

The method of claim 15 wherein said cleanup routine further comprises the step: terminating a process which has not progressed for at least a predetermined period of time.

Claim 20

The method of claim 12 wherein said cleanup routine comprises the steps: determining if there is a registered owner of the semaphore and if the registered owner is a dead process; and if there is a registered owner of the semaphore and if the registered owner is a dead process, then recovering the resource associated with the semaphore and releasing the semaphore.

Claim 23

The method of claim 18 further comprising the step: preventing a process from acquiring a semaphore when said cleanup routine has been initiated for said semaphore.

Claim 24

The method of claim 18 further comprising the step of: terminating a process which has not progressed for at least a predetermined period of time.

Claim 25

The method of claim 18 further comprising the step: initiating execution of a cleanup routine for a semaphore when said semaphore has been unavailable for at least a predetermined time period.

Claim 26

The method of claim 21 further comprising the step: preventing a process from acquiring a semaphore when said cleanup routine has been initiated for said semaphore.

Claim 27

The method of claim 21 further comprising the step: terminating a process which has not progressed for at least a predetermined period of time.

Claim 28

A computer system, comprising: A) at least one processing unit; B) a plurality of shared resources accessible by each processing unit and including a memory unit; C) a plurality of semaphore records stored in said memory unit and containing an owner identification for registering ownership of the semaphore record; D) a plurality of processes executing on said processing unit(s), said processes requesting and acquiring exclusive access to said shared resources by requesting and acquiring ownership of said semaphore records; E) a plurality of semaphore access records stored in said memory unit, each of which is associated with one of said processes, for identifying a semaphore record which the process associated with said semaphore access record wants to acquire ownership of; F) means for maintaining an underestimate of semaphore ownership comprising: i) means for storing in said memory unit an identification of a process which owns a semaphore record, subsequent to said process acquiring ownership of said semaphore record; and ii) means for removing from said memory unit said identification of a process which owns a semaphore record, prior to said process releasing ownership of said semaphore record; G) means for maintaining an overestimate of semaphore ownership comprising: i) means for storing in said memory unit an indication that a process wants to acquire a semaphore record, prior to said process requesting ownership of said semaphore record; and ii) means for removing from said memory unit said indication that a process wants to acquire a semaphore record, subsequent to said process releasing ownership of said semaphore record; H) means for determining whether the underestimate obtained in F) matches the overestimate obtained in G); wherein each of said semaphore records is associated with one of said shared resources and comprises: A) availability indicia for indicating whether the semaphore record is available; and B) cleanup indicia for indicating whether the semaphore record is being evaluated by a cleanup means; wherein said cleanup means is activated when the underestimate obtained in F) does not match the overestimate obtained in G) and comprises: A) means for determining whether a semaphore record is owned by a process which has crashed by using said information in said semaphore records and said semaphore access records; and B) means for resetting the availability indicia of a semaphore record when the semaphore record is owned by a process that has crashed.

Claim 29

A computer system, comprising: A) at least one processing unit; B) a plurality of shared resources accessible by each processing unit and including a memory unit; C) a plurality of semaphore records stored in said memory unit and containing an owner identification for registering ownership of the semaphore record; D) a plurality of processes executing on said processing unit(s), said processes requesting and acquiring exclusive access to said shared resources by requesting and acquiring ownership of said semaphore records; E) a plurality of semaphore access records stored in said memory unit, each of which is associated with one of said processes, for identifying a semaphore record which the process associated with said semaphore access record wants to acquire ownership of; F) means for maintaining an underestimate of semaphore ownership comprising: i) means for storing in said memory unit an identification of a process which owns a semaphore record, subsequent to said process acquiring ownership of said semaphore record; and ii) means for removing from said memory unit said identification of a process which owns a semaphore record, prior to said process releasing ownership of said semaphore record; G) means for maintaining an overestimate of semaphore ownership comprising: i) means for storing in said memory unit an indication that a process wants to acquire a semaphore record, prior to said process requesting ownership of said semaphore record; and ii) means for removing from said memory unit said indication that a process wants to acquire a semaphore record, subsequent to said process releasing ownership of said semaphore record; H) means for determining whether the underestimate obtained in F) matches the overestimate obtained in G); wherein each of said semaphore records is associated with one of said shared resources and comprises: A) availability indicia for indicating whether the semaphore record is available; and B) cleanup indicia for indicating whether the semaphore record is being evaluated by a cleanup means; wherein said cleanup means is activated when the underestimate obtained in F) does not match the overestimate obtained in G) and comprises: A) means for determining whether a semaphore record is owned by a process which has crashed by using said information in said semaphore records and said semaphore access records; and B) means for resetting the availability indicia of a semaphore record when the semaphore record is owned by a process that has crashed.

Claim 30

A crash safe system for enforcing mutually exclusive access to shared data in a computer system comprising: A) at least one processing unit; B) a plurality of shared resources accessible by each processing unit and including a memory unit; C) a plurality of semaphore records stored in said memory unit and containing an owner identification for registering ownership of the semaphore record; D) a plurality of processes executing on said processing unit(s), said processes requesting and acquiring exclusive access to said shared resources by requesting and acquiring ownership of said semaphore records; E) a plurality of semaphore access records stored in said memory unit, each of which is associated with one of said processes, for identifying a semaphore record which the process associated with said semaphore access record wants to acquire ownership of; F) means for maintaining an underestimate of semaphore ownership comprising: i) means for storing in said memory unit an identification of a process which owns a semaphore record, subsequent to said process acquiring ownership of said semaphore record; and ii) means for removing from said memory unit said identification of a process which owns a semaphore record, prior to said process releasing ownership of said semaphore record; G) means for maintaining an overestimate of semaphore ownership comprising: i) means for storing in said memory unit an indication that a process wants to acquire a semaphore record, prior to said process requesting ownership of said semaphore record; and ii) means for removing from said memory unit said indication that a process wants to acquire a semaphore record, subsequent to said process releasing ownership of said semaphore record; H) means for determining whether the underestimate obtained in F) matches the overestimate obtained in G); wherein each of said semaphore records is associated with one of said shared resources and comprises: A) availability indicia for indicating whether the semaphore record is available; and B) cleanup indicia for indicating whether the semaphore record is being evaluated by a cleanup means; wherein said cleanup means is activated when the underestimate obtained in F) does not match the overestimate obtained in G) and comprises: A) means for determining whether a semaphore record is owned by a process which has crashed by using said information in said semaphore records and said semaphore access records; and B) means for resetting the availability indicia of a semaphore record when the semaphore record is owned by a process that has crashed.

Claim 31

A crash safe system for enforcing mutually exclusive access to shared data in a computer system comprising: A) at least one processing unit; B) a plurality of shared resources accessible by each processing unit and including a memory unit; C) a plurality of semaphore records stored in said memory unit and containing an owner identification for registering ownership of the semaphore record; D) a plurality of processes executing on said processing unit(s), said processes requesting and acquiring exclusive access to said shared resources by requesting and acquiring ownership of said semaphore records; E) a plurality of semaphore access records stored in said memory unit, each of which is associated with one of said processes, for identifying a semaphore record which the process associated with said semaphore access record wants to acquire ownership of; F) means for maintaining an underestimate of semaphore ownership comprising: i) means for storing in said memory unit an identification of a process which owns a semaphore record, subsequent to said process acquiring ownership of said semaphore record; and ii) means for removing from said memory unit said identification of a process which owns a semaphore record, prior to said process releasing ownership of said semaphore record; G) means for maintaining an overestimate of semaphore ownership comprising: i) means for storing in said memory unit an indication that a process wants to acquire a semaphore record, prior to said process requesting ownership of said semaphore record; and ii) means for removing from said memory unit said indication that a process wants to acquire a semaphore record, subsequent to said process releasing ownership of said semaphore record; H) means for determining whether the underestimate obtained in F) matches the overestimate obtained in G); wherein each of said semaphore records is associated with one of said shared resources and comprises: A) availability indicia for indicating whether the semaphore record is available; and B) cleanup indicia for indicating whether the semaphore record is being evaluated by a cleanup means; wherein said cleanup means is activated when the underestimate obtained in F) does not match the overestimate obtained in G) and comprises: A) means for determining whether a semaphore record is owned by a process which has crashed by using said information in said semaphore records and said semaphore access records; and B) means for resetting the availability indicia of a semaphore record when the semaphore record is owned by a process that has crashed.