Background of the Invention
The present invention relates to controlling processor access to resources which must be exclusively accessed in a multiprocessor environment.
Systems of multiple processors often share common resources, such as records in memory, specialized registers, indicators, etc. Such systems normally require a mechanism whereby a given processor can indicate the need to temporarily reserve or "block" a resource from use or modification by other processors. This locking insures exclusive access to that resource for the given processor.
For example, a given processor may need to make a number of individual modifications to a data structure in a memory to bring that data structure from one valid state to another. A lock can be used to indicate to other processors during modification of the data structure that the data structure should not be accessed. This mechanism requires that processors obey a policy in which the state of a lock is inspected before the associated resource is accessed. The process of inspecting a lock, and setting it to the locked state if found to be presently unlocked, must be done "atomically" i.e. without any intervening operations from other processors, and is conventionally called a "read.sub.-- modify-write" operation. This atomicity is required to insure that no more than one processor at a time "owns" a given lock.
A processor seeking exclusive use of a resource typically will issue a read command having the address of a lock indicator associated with that resource. The contents of the addressed lock indicator are put on an address/data bus to be read by the seeking processor. Simultaneously, a mechanism, typically suspension of bus usage, is invoked to temporarily suspend access to the addressed resource by all other processors.
The seeking processor inspects the lock indicator data it reads on the address/data bus to determine the locked/unlocked status of the resource of interest. If, according to the contents of the lock indicator, the resource is indicated to be locked, then the seeking processor must presently release the address/data bus and may re-examine the lock indicator at a later time. Alternatively, if, according to the contents of the lock indicator, the resource is indicated to be unlocked, then the seeking processor modifies the lock indicator contents with a write command communicated over the address/data bus to indicate that the resource is reserved for exclusive access by the seeking processor. The processor is now said to have "acquired" the lock. The seeking processor, now as the locking processor, can exclusively process or modify the data in the now locked resource as needed.
When the locking processor no longer needs exclusive access to the resource, it will issue a write command directed to the resource's associated lock indicator to clear the lock indication. This is called "relinquishing" the lock. Now the resource is available for access by other processors, or can be locked for exclusive access by another processor executing the process detailed above.
Summary of the Invention
The present invention reduces address/data bus usage by eliminating suspension of bus usage for lock inspection and acquisition and increases resource locking protocol compatibility within a heterogeneous processing environment. A locked/unlocked indication is maintained in a lock register associated with a given resource, and the permission of a processor to access the resource is indicated by the contents of the lock register. A lock register is inspected and, if unlocked, the lock is acquired with a simple read operation. A lock can be relinquished only by the locking procesor, and is done with a simple write operation.
A given processor (P1-PN) is identified by a unique ID vector (G1-GN). These vectors are used by the mechanism which arbitrates bus usage in the multiprocessor system to identify processors, and in the present invention to indicate both that a resource is locked and to indicate the locking processor. An unlocked state is identified by another vector (G.O slashed.). By convention, processors will not access a resource requiring exclusive access until an inquiry of the associated lock register returns the G.O slashed. vector. This protocol is employed throughout the present invention.
Locking of a given resource is achieved by an inquiring processor addressing a single read command to a lock register associated with that resource. Upon this inquiry, a lock register controller recognizes the addressed lock register and latches the reading processor's ID vector. At the same time (i.e., before the next bus usage), the lock register controller reads the addressed lock register and returns its contents on the address/data bus to indicate the locked/unlocked status of the resource. If the value returned is an ID vector associated with another processor, then the associated resource is considered to be already locked and the reading processor accordingly interprets this vector data as meaning that the indicated other processor "owns" the resource. The reading processor now goes on to other tasks or tries again.
If the value returned is the unlocked status vector, the processor interprets this as an indication that the resource was not owned, and also that it now exclusively owns the resource. At the same time (i.e., before the next bus usage), the lock register controller writes the ID vector of the inquiring processor (from the lock register controller latch) into the lock register. This establishes exclusive ownership of the resource by that inquiring processor. Thus subsequent inquiry directed to that same lock register by another processor will return the node ID of the inquiring (now locking) processor, and the other processor will likewise go on to other tasks.
The locking processor indicates its desire to terminate exclusive access to a resource by addressing the associated lock register with a simple write command. In response, the lock register controller having latched the locking (now unlocking) processor's ID vector when the write operation began, fetches the contents of the lock register. The controller writes the unlocked status vector (G.O slashed.) into that lock register to unlock that locked resource only if the latched vector and fetched vector match, thereby insuring that only the processor that locked the resource can unlock it.
The present invention eliminates the need for an atomic read.sub.-- modify-write lock/unlock operation to be performed upon the lock register data structure. In a typical read.sub.-- modify-write operation, the contents of a particular lock register are read and evaluated by a processor, and then the processor (if the particular lock register is unlocked) writes a "lock" command to that lock register (with bus suspension during the evaluation process) to lock access to the resource associated with that lock register. The present invention uses only a simple read or write command for resource locking or unlocking in conjunction with the disclosed apparatus. The present invention thus advantageously reduces usage (and suspensions of usage) of the address/data bus.
Other advantages and features will become apparent from the following description of the preferred embodiment and from the claims.
Brief Description of the Drawings
FIG. 1 is a block diagram of a preferred embodiment of the invention.
FIG. 2 is a map of a lock register array as part of a memory store.
FIG. 3 is a flow chart showing the acquisition of exclusive access by setting a resource lock in practice of the present invention.
FIG. 4 is a flow chart showing releasing of exclusive access to a resource in practice of the present invention.
FIG. 5 (a,b) is a comparison of a prior art read.sub.-- modify-write operation versus the present invention.
FIG. 6 is a diagram of a doubly mapped lock register array in practice of the present invention.
Description of a Preferred Embodiment
In a preferred embodiment of the present invention, any one of several processors may (in turn) acquire exclusive access to a given resource (such as to a memory record) by issuing a read command and may release exclusive access by issuing a write command, such as in the manner summarized above. Each processor, P1-PN, is assigned a unique node ID vector G1-GN. The status vector (G.O slashed.) corresponds to none of the processors P1-PN, and is used to indicate an unlocked resource. The ID vectors are used by a lock register controller to indicate the locked/unlocked status of a lock register which is associated, by a predetermined convention, with a given resource. A lock register controller controls an array of lock registers which may be an array of storage registers distinct from any other system memory, or an area in system memory specifically partitioned for use as a lock register array. The lock register controller may be incorporated on a single substrate with a memory controller which controls access to system memory.
In the embodiment of FIG. 1, processors P1, P2 . . . PN, are coupled via request lines 61, 63 . . . 65 to a bus arbiter 74. Bus arbiter 74 determines which processor is to have access to the data bus 68 and issues that processor's node ID on the grant bus 72. The processor whose node ID appears on the grant bus is thus granted access to the address/data bus 68 and may now address and access various resources, such as a record in memory 80 via memory controller 75. (The method of bus arbitration used by bus arbiter 74 is a matter of computer design outside of the present inquiry; the present invention is directed to actions of a processor after it has been awarded bus access by arbiter 74.)
Permission to access a resource such as a record in memory 80 is indicated to an inquiring (reading) processor via lock register controller 76 according to the contents of the particular lock register of array 78 assigned to the sought resource. Controller 76 is preferably provided with a latch for storing the node ID of a processor accessing the lock register array from grant bus 72.
An illustrative relationship between lock registers and memory records in practice of the present invention is shown in FIG. 2. In this example, memory 80 includes 100 records and 100 lock registers, the latter constituting a lock register array 78. Each memory record (1-100) consists in this example of 10 consecutive locations within the overall range of addresses 000-999 (e.g., record 1 corresponds to locations 000-009, etc.). The lock registers are established at locations 1000-1099. Now lock register address 1000 corresponds to record 1, lock register address 1001 corresponds to record 2, etc.
Any one of these 100 records (as a resource) might be read and modified by any given processor. To avoid corruption from concurrent modification by several processors, the present locking mechanism is employed. Hence, before accessing a given record, the contents of a lock register associated with the given record are read by the inquiring processor. If the lock register contains a node ID vector (G1-GN), then by convention, the record associated with that register has been locked by the processor associated with that vector, and the inquiring processor respects this condition by going on to other tasks or retrying to obtain access later.
If the lock register contains the unlocked status vector (G.O slashed.), then by convention, this is interpreted by an inquiring processor that it has locked an unlocked resource associated with that lock register. Upon such inquiry, the lock register controller writes the node ID vector of the inquiring processor into the lock register to indicate that the inquiring processor has acquired exclusive access to the record. In particular, the lock register controller latches the grant ID from the grant bus when the read begins, then outputs on the address/data bus the contents of the addressed lock register, and conditionally stores the ID of the inquiring processor into the addressed lock register as the prior contents are placed onto the bus. This is done within the time frame of a normal procesor read operation.
A vector returned from the lock register other than G.O slashed. indicates to the inquiring processor that the resource is locked by another processor and also the identity of the locking processor. If the resource is locked by a processor other than the inquiring processor, then lock register controller 76 does not modify the contents of the addressed lock register.
The lock is released within the time frame of a normal write routine by the processor issuing a write command (which may specify (G.O slashed.) as the data to be written) to the lock controller. The lock register controller latches the processor's ID vector from the grant bus 72, recognizes the address, fetches the contents of the addressed lock register and compares these contents to the processor's node ID vector. In the case where the node ID matches the value stored in the lock register, the lock register controller causes the addressed lock register to be written with G.O slashed.; otherwise, the register contents are not changed. This insures that only the proper locking processor relinquishes a lock.
In one preferred embodiment, the lock register controller writes into the lock register whatever data is issued by the processor as part of its write command, and assumes all processors will by convention supply G.O slashed. as that data. In another preferred embodiment, the lock register controller writes the G.O slashed. vector into the addressed lock register regardless of the actual vector data issued by the processor with such write commands (and therefore the write data is not latched by the controller).
In operation of the embodiment of FIG. 1, an inquiring processor seeking exclusive access to a resource (such as a record in memory 80) issues a request by putting on the data bus 68 a read command addressed to the lock register in array 78 associated with the resource of interest (such as a record in memory 80). The lock register controller 76 decodes the address and fetches the data (indicative of locked/unlocked status) stored in the associated lock register and puts this data (G.O slashed. or one of G1-GN) on the data bus 68. The inquiring processor reads the vector data and immediately knows the status of the resource of interest and can immediately begin operation upon the contents of the locked resource if G.O slashed. is the read vector data. At the same time, the lock register controller having latched the contents of the grant bus 72 indicative of the inquiring processor's node ID, then writes this into the addressed lock register to "set" the lock (if G.O slashed. has been fetched by the lock register controller from the lock register). If G.O slashed. is not read on the data bus, then the inquiring processor knows that it has been denied access to the resource.
In the case where the node ID of a processor issuing a write command to a lock register (to release exclusive access) matches the value stored in the lock register, then the lock register controller clears the lock by writing G.O slashed. into the addressed lock register. In the case that the writing processor's node ID does not match the value stored in the addressed lock register, then that processor cannot rightfully clear the lock, and accordingly, the lock register controller performs no modification of the addressed lock register. In one preferred embodiment of the invention, the lock register controller simply ignores inappropriate write commands. In an alternative preferred embodiment, the lock register controller flags an error condition to report that a processor unconventionally attempted to modify a lock.
FIGS. 3 and 4 are flow charts showing acquisition and relinquishment of a lock, respectively. In FIG. 3, access to the data bus is granted by the bus arbiter and the designated processor then puts the address of a lock register associated with a sought resource on the data bus (block 30). Now the lock register controller reads the address and puts the contents of the addressed lock register onto the data bus (block 32). If the value is not G.O slashed., indicating an already locked resource, then this loop is complete (block 34). If the value is G.O slashed., then the lock register controller puts the node ID of the inquiring processor in the addressed lock register (block 36), and then the routine is complete. The inquiring processor has now acquired exclusive access to the sought resource, and can proceed accordingly.
As shown in FIG. 4, to relinquish a lock, access to the data bus is granted by the bus arbiter and the processor having the lock issues a write (G.O slashed.) to the lock register associated with the locked resource (block 40). The lock register controller recognizes the address, latches the data (G.O slashed.) and fetches the contents of the addressed lock register (block 42). The controller tests for a match of the node ID vector (from grant bus 72) of the processor issuing the write and the vector fetched from the addressed lock register (block 44). If the vectors do not match, then no changes are made in the lock register since the inquiring processor does not own that resource, and the controller cancels the write (block 46). But if the ID'match, then the controller writes G.O slashed. into the lock register (block 48) and the exclusive access is thus terminated.
The present invention reduces data bus usage and suspensions. As shown in FIG. 5a, a prior art read.sub.-- modify-write locking mechanism requires a combination of bus usage and suspension of usage for three time intervals 1, 2, 3 in order to set a lock. First, a read command is issued by the inquiring processor and the contents of the addressed lock register are read by the inquiring processor (interval 1: bus usage). Next, if not indicative of locked status, the lock register contents state is modified to indicate locked status (interval 2: bus suspension). Finally, the modified contents statement is written back to the lock register to lock access to the sought resource (interval 3: bus usage).
As shown in FIG. 5b, the new resource locking mechanism of the present invention uses only one time interval of data bus time for a processor to lock a resource with a simple read operation (interval 1: bus usage). The lock register controller returns the unlocked indicator as read data to the inquiring processor within this interval and then writes the inquiring processor's node ID in the addressed lock register. As a result, bus usage is reduced and suspensions are avoided. The present invention is equally as efficient in releasing a lock, merely requiring addressing a write statement to the appropriate lock register.
In a preferred embodiment of the invention, for a given set of lock registers, the lock register controller associates two addresses with each register. As shown in the example of FIG. 6, two areas of illustrative memory 89 are respectively identified as the "read-write" segment 93 (here assigned addresses 200-299) and the "lock/unlock" segment 94 (here assigned addresses 300-399). The lock/unlock segment 94 can be used for the general locking/unlocking operations discussed above. The read-write segment 93 can be used to load a lock register or to inspect the state of a register without causing modification; this type of access would typically be used for initialization, diagnosis, or controlling access given to "restricted" nodes.
For example, a "trusted processor" may have the ability to change the state, i.e. ownership, of a lock it does not itself own. This ability becomes important if, for example, a processor which owns the lock becomes disabled and can not release the lock. Without the capability of some other processor being able to change the state of the resource to unlocked, no other processor could acquire the resource, even though the processor which originally locked the resource is nolonger functioning. Further, the ability of a "trusted processor" to inspect a lock without changing the state of the system or to unconditionally modify a lock is important for the diagnosis of system malfunctions and for the resolution of deadlock situations between processors maintaining locks.
The present invention has several advantages, including:
(1) Since locks may be tested and conditionally acquired with simple operations, these operations can be executed much more expeditiously than conventional read.sub.-- modify-write methods. Bus usage and suspension is reduced.
(2) Since this technique uses conventional memory read (and write) operations to perform lock testing, acquisition and release, it is not dependent on any particular processor's mechanism for performing read.sub.-- modify-write operations, i.e., no special operation or signalling is required to be implemented by processors to use this feature. Hence, this technique is applicable to a variety of processor types, and to heterogeneous mixtures of processors in a multiprocessor system.
(3) Since the value used to indicate that a processor "owns" a lock is that processor's own node ID vector, and lock registers can be benignly read via the read-write segment 93, it is possible to get a system-wide picture of which processors have locked the various resources in a system without changing that picture. This aids diagnosis of system deadlocks, etc.
Other embodiments are within the following claims.