Abstract:
In a multi-processor system in which several processors compete for exclusive use of a shared resource, a claimant processor asserts exclusive access to a resource by determining whether there exists a competing claim to exclusive access to said resource and then posting a claim to exclusive access to said resource. Following lapse of an interval, the claimant processor then determines whether there exists a competing claim to exclusive access to said resource. Depending on whether or not such a claim exists, the claimant processor then either takes control of the resource or makes another attempt after waiting.

Description:
TECHNICAL FIELD 
   This invention relates to multi-processor systems, and in particular, to management of competition between processors. 
   BACKGROUND 
   A data storage system can include several independent processors that cooperate to increase throughput of many tasks associated with data storage and retrieval. These processors typically communicate with each other by leaving messages in a shared memory. This shared memory is constantly available to the processors for reading and writing. 
   Certain tasks require that a processor use a particular system resource to the exclusion of other processors. When a processor is using such a system resource, it is useful to communicate to other processors that the system resource is busy. Conversely, when a processor is done using such a system resource, it is useful to communicate to other processors that the resource is now free. 
   One approach to providing such communication is to leave messages in the shared memory. However, because the memory is shared, it is possible for a race condition between processors to occur. In such cases, a processor may inadvertently overwrite a message. This can result in two processors attempting to use the same resource at the same time. 
   To avoid the possibility of having two processors overwrite each other&#39;s messages, it is possible to partition the shared memory and to allow a processor write-access to only its partition. However, as the number of processors increases, the amount of memory allocated to each processor decreases. This can result in a processor running short of memory even though considerable memory, which might be available were it not allocated to other processors, stands idle. 
   Another approach is to maintain a queue for each such resource. However, management of a queue consumes system overhead. It is therefore preferable to avoid such a solution whenever possible. 
   SUMMARY 
   The invention is based on the recognition that if a race condition arises between two processors claiming the same resource, the race condition will generally be manifested within a brief interval following the near-simultaneous assertion of a claim over that resource. By allowing this interval to pass before actually using the resource, the method of the invention significantly reduces the likelihood of a race condition between two processors. 
   A claimant processor asserts exclusive access to a resource by first determining whether there exists a competing claim to exclusive access to the resource and then posting a claim to exclusive access to the resource. Following lapse of an interval, the claimant processor then determines whether there exists a competing claim to exclusive access to the resource. 
   The determination of whether there exists a competing claim can include inspecting a data-storage location to determine whether exclusive access to the resource has already been claimed. In such a case, the presence of a release code at the data storage location determines whether the resource has been released by a competitor and is therefore available. 
   In one practice of the invention, the claimant processor posts a claim of exclusive access to the resource by replacing data at a data-storage location with a claim code indicating a claim to exclusive access to the resource. 
   After waiting a suitable interval, the claimant processor determines whether the posted a message still exists or whether it has been written over by a competing processor. The suitable interval is typically selected to on the basis of time associated with determining whether there exists a competing claim and posting a claim to exclusive access. 
   In an alternative practice of the invention, the claimant processor determines that there exists a competing claim to the resource and following lapse of a second interval, determining whether the competing claim continues to exist. This interval can then be selected on the basis of an expected usage time for the resource. Alternatively, the interval can be selected such that each processor in the multi-processor system has a different interval. 
   These and other features of the invention will be apparent from the following description and the accompanying figures, in which: 

   
     BRIEF DESCRIPTION OF THE FIGURES 
       FIG. 1  shows a representative multi-processor system for practice of the invention; and 
       FIG. 2  is a flow-chart illustrating a representative practice of the invention. 
   

   DETAILED DESCRIPTION 
   A system  10  incorporating the invention includes a claimant processor  12   a  and a plurality of competing processors  12   b–d . The claimant processor  12   a  is in communication with a claimant local memory  14   a  that is not accessible to the competing processors  12   b–d . The competing processors  12   b–d  are in communication with corresponding local memories  14   b–d  that are not accessible by the claimant processor  12   a . Both the claimant processor  12   a  and the competing processors  12   b–d  are also in communication with a shared memory  16 . This shared memory  16  is intended to be read from and written to by any processor. 
   Both the terms “competing processor” and “claimant processor” are logical terms that are used to described a processor carrying out a particular role in the context of this description. Each processor  12   a–d  can be a claimant processor and, from the point of view of another processor, a competing processor. There is no inherent structural difference between a claimant processor  12   a  and a competing processor  12   b–d.    
   The system  10  further includes one or more serially-shared resources  18  that can be accessed by the claimant processor  12   a  and by each of the competing processors  12   b–d . Such resources are referred to as “serially shared” because although any processor  12   a–d  can access that resource  18 , no two processors are permitted to access the resource  18  simultaneously. Each serially-shared resource  18  has a corresponding designated location  20  in the shared memory  16 . The data contained in this designated location  20  indicates the status of the serially-shared resource  18  with which it is associated. 
   The data contained in the designated location  20  can include a lock-word  22  that stores either a release code, which indicating that the resource  18  is free, or a claim code, which indicates that the resource  18  has been claimed for exclusive use by one of the processors  12   a–d . A claim code can also indicate the identity of the processor claiming that resource  18 . In one embodiment, each resource  18  is associated with a lock-word  22  made up of a four-byte word in shared memory. A first portion of the word is selected to enable a processor to identify the word as being a lock-word. A second portion of the word is selected to identify a particular processor associated with the lock-word. 
   The designated location  20  can also include a time-stamp  24  to indicate when the resource  18  was last used, and optionally, by which processor. Although a time-stamp  24  is not necessary, its presence is useful for diagnosing irregularities in system behavior. 
   When a claimant processor  12   a  requires access to a resource  18 , it first examines the lock-word  22  associated with that resource  18 . If the lock-word  22  contains the release code, the claimant processor  12   a  writes its claim code into the lock-word  22 , thereby establishing a latent claim over the resource  18 . Before taking control of the resource  18 , the claimant processor  12   a  executes a loop (to be described below) to reduce the possibility of a race condition between itself and a competing processor  12   b–d . If after execution of this loop the lock-word  22  still contains the claimant processor&#39;s claim code, then the latent claim is confirmed and the claimant processor  12   a  can safely access the resource  18 . Once the claimant processor  12   a  no longer needs the resource, it writes the release code into the lock-word  22  to indicate that the resource is once again free. 
   Referring now to  FIG. 2 , when a claimant processor requires access to a resource, it first determines whether that resource is free. To do so, the claimant processor reads the lock-word for that resource into its local memory and generates a claim code identifying itself. The claimant processor then compares the generated claim code with the lock-word (step  26 ). A lock-word that is identical to the generated claim code suggests that the claimant processor has already claimed the resource. Since this is inconsistent with the claimant processor seeking to claim the resource, an error is generated (step  27 ). 
   The claimant processor next sets a time-out value (step  28 ). The time-out value places an upper limit on how long the claimant processor will consider the activities of competing processors. If, after expiration of a time-out period, the lock-word still indicates that a competing processor has claimed the resource, the claimant processor usurps control of the resource from the competing processor. The provision of a time-out value is useful for avoiding an interminable wait resulting from, for example, a competing processor that fails before it has had a chance to write a release code into the lock-word. 
   The lock-word and the generated claim code may differ because the lock-word contains a release code indicating that the resource is free. In such a case, the claimant processor can claim the resource. However, the lock-word and the generated claim code can also differ because the lock-word contains a claim code generated by a competing processor. The claimant processor responds to this condition by making another attempt to claim the resource after waiting, for a reasonable period, for that resource to be freed. In rare cases, the lock-word and the claim code may differ because the lock-word has become corrupted. When this is the case, the processor posts an error. 
   If the lock-word contains a release code (step  30 ), the claimant processor asserts a claim over the resource by replacing the release code with its claim code (step  32 ). 
   In some cases, a race condition between the processor and a competing processor can arise. This can occur because of a brief interval, after a first processor has read the lock-word but before it has written its claim code into the lock-word. If a second processor were to read the lock-word during this brief interval, it would still see a release code in lock-word. The second processor would then proceed to assert a claim over the resource, not recognizing that the first processor is ahead of it. 
   To avoid the foregoing race condition, the claimant processor waits for the duration of a first interval (step  34 ). This first interval is selected to be greater than the time required for a processor to read from and write to the shared memory. By waiting for a first interval to elapse before proceeding, the claimant processor ensures that any competing processor will have had time to complete the process of asserting a claim for the resource. 
   Once the first interval has passed, the claimant processor then re-reads the lock-word to verify that the lock-word still contains its claim code (step  36 ). If the lock-word still contains the claim code, the claimant processor proceeds to use the shared resource (step  38 ). Once the claimant processor no longer requires the resource, it overwrites its claim code in the lock-word with a release code (step  40 ). 
   In one practice of the invention, just before the claimant processor writes a release code into the lock-word (step  40 ), it first verifies that its claim code is still in the lock-word. If it is not, an error has occurred and the claimant processor posts an error message. 
   As noted above, in some cases, the claimant processor may discover that the lock-word does not contain the release code. When this occurs, the claimant processor determines whether the lock-word contains a valid value (step  42 ). In addition to the release code, valid values for the lock-word include the claim codes for all the competing processors. Since there are only a finite number of competing processors, the test to identify valid values is not prohibitive. The claim codes for the competing processors can be provided in a known location in the shared memory, or they can be provided in the local memory of the claimant processor. 
   If the claimant processor determines that the lock-word contains an invalid value (step  42 ), it generates an error (step  44 ). In addition, since the lock-word does not contain a claim code for a competing processor, the resource is apparently not claimed by any competing processor. Hence there is no reason for the claimant processor to refrain from asserting control over the resource. Accordingly, the claimant processor proceeds to write its claim code over the invalid value in the lock-word (step  32 ) and to carry on as if the lock-word had originally contained the release code. 
   If the claimant processor does recognize a competing processor&#39;s claim code in the lock-word, it proceeds to wait for the duration of a second interval (step  46 ). Once the second interval has elapsed, the claimant processor determines whether the time-out value has been reached (step  48 ). If the time-out value has not been reached, the claimant processor makes another attempt to assert a claim over the resource by re-reading the lock-word (step  30 ) and proceeding as already described above. If the time-out value has been reached, the claimant processor usurps the shared resource by replacing the contents of the lock-word with its own claim code (step  50 ) and proceeding to use the shared resource (step  38 ). 
   In some cases, two processors may decide, at the substantially same time, to attempt to access the resource. If this occurs while the resource is claimed by a third processor, the two processors will execute the subsequent steps in the method almost in unison. This can result in a race condition between the two processors. 
   To avoid such a race condition, one practice of the invention provides for staggering the individual processors relative to each other by defining a different value of the second interval for each processor. The length of the second interval can be based on a percentage of the average usage time for the resource. For example, the second interval can be the sum of a base value and an offset value, the offset value being unique to each processor. Alternatively, the second interval can be the sum of a base value and a random number selected from a pre-defined interval. A suitable value for a base value is one on the order of fifty microseconds. 
   The system  10  shown in  FIG. 1  includes one shared resource and four processors competing for access to that resource. However, in the method described above, there is no inherent limit in the number of competing processors or the number of shared resources. A larger number of competing processors requires the definition of additional claim codes and additional second intervals. A larger number of shared resources can be accommodated by providing a separate designated region for each resource. 
   The system  10  is also shown as including local memories  14   a–d  associated with each processor  12   a–d . These local memories  14   a–d  are useful because the comparison between the generated code word and the lock-word can proceed more quickly if the lock-word is first copied into the claimant processor&#39;s local memory  14   a . However, the method described herein does not explicitly require a local memory.