Patent Publication Number: US-5893156-A

Title: Lock control apparatus and method including controlling means for setting a lock variable status

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to a lock control apparatus and method, and more particularly to a lock control apparatus and method for a computer system, which includes a plurality of banks, each paired system of which has a plurality of store-in cache memories (SICs) which share a main memory. Each of the caches of the paired system is used by at least one central processing unit, respectively, and is connected to another cache of the paired system through a bus. 
     In a shared-memory multi-processor system, a plurality of processors share a main memory. In such a system, a certain processor must exclusively use data in a certain shared area of the main memory for a certain time period. For example, when the processor executes an operation of adding &#34;1&#34; to data in the certain shared area, during a sequence of processing conducted since data in the shared area is read out to add &#34;1&#34; until the data is again written in the shared area, other processors must be prohibited from accessing to that data. Without such prohibition, updating data and thus accessing updated data are not ensured. 
     In order to ensure exclusive access and thus to prohibit the other processors from accessing the data, a lock variable is typically used. In gaining access to the shared area of the main memory, the lock variable must be checked to confirm that the lock variable is not in a &#34;lock&#34; status. The lock variable check is conducted in accordance with a lock request, and when the lock variable is in an &#34;unlock&#34; status, then the lock variable is updated to the &#34;lock&#34; status. Then, access is permitted to a corresponding shared area. After the exclusive processing is finished, the lock variable is returned to the &#34;unlock&#34; status in accordance with an unlock request. Such control is called a &#34;lock control&#34;. 
     When a cache memory (e.g., a first cache memory) is provided in each processor, if an inconsistency occurs between the contents of the main memory and the contents of the cache memory, corresponding data in the cache memory must be invalidated. Such a processing is called &#34;cache consistency processing&#34;. 
     For example, when a certain processor rewrites the contents in the shared area from &#34;0&#34; to &#34;1&#34;, unless corresponding data in the cache memories of other processors is invalidated (e.g., nullified), the other processors unintentionally and erroneously read out old data, that is, &#34;0&#34;. Hence, that data is invalidated through the cache consistency processing so as to be &#34;flushed&#34; (e.g., removed) from the cache memory. Then, other processors read data in the main memory because of a cache &#34;miss&#34;, since the processors are capable of reading data after updating, that is, a &#34;1&#34;. 
     In this example, when a certain processor A acquires a &#34;lock&#34; in accordance with the lock request, all the cache consistency processing with respect to corresponding shared areas must be completed. Without the processing, a data updating operation which has been conducted with respect to the shared areas by other processors B is not ensured. 
     Hence, a conventional lock control apparatus has a request buffer which ensures an order of requests. A &#34;reply for lock&#34; (e.g., a lock reply) is stored in a last entry of the request buffer. 
     In the conventional lock control apparatus, when a lock is to be acquired in the secondary cache which has been divided into a plurality of banks, two conventional methods are used as described below. 
     In a first method, a processor issues lock requests to all banks concurrently until the processor acquires locks from all the banks. However, in this first method, when a plurality of processors issue a lock request to the same lock address, respectively, and when a different processor obtains a lock in each bank, an unlock request and a lock request must be repeated since each central processing unit releases the lock thus acquired once until it issues a lock request again and the lock succeeds in all the banks. This is cumbersome and problematic in that the time required for acquiring a lock at the time of lock conflict at the same address is increased. 
     In a second method, a processor issues a lock request to a certain bank. After acquisition of the lock, the processor issues cache consistency requests to all the banks. However, in this second method, a cache memory in the processor cannot be accessed until a reply to the cache consistency request is returned from all the banks. 
     That is, even though a result of a lock request is found in accordance with a lock reply from a certain secondary cache, because it cannot be ensured that the cache consistency processing for the shared area has been completed, a first cache cannot be accessed until a reply to a request for a cache consistency guarantee is returned from all the secondary caches. Hence, access to the shared area is delayed until replies to the request for the cache consistency guarantee are returned from all the banks of the secondary cache although the lock acquisition has been completed. 
     SUMMARY OF THE INVENTION 
     In view of the foregoing problem of the conventional system, an object of the present invention is to reduce the time required for accessing a shared area via a lock acquisition. 
     In a lock control apparatus and method according to a first aspect of the present invention, a lock status register stores a lock variable status with respect to each processor and to each memory bank, and the controller controls the lock variable status stored in the lock status register. If the lock variable status with respect to a certain memory bank indicates a lock acquisition status, the controller sets the lock variable status in other memory banks to the lock acquisition status. 
     With the unique and unobvious structure and method of the present invention, the time required for accessing a shared area is reduced as compared to the conventional systems described above. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above-mentioned and other objects, features and advantages of the present invention will become more apparent by reference to the following detailed description of the invention taken in conjunction with the accompanying drawings in which: 
     FIG. 1 is a block diagram showing a computer system to which the present invention is applied; 
     FIG. 2 is a block diagram showing a secondary cache 205 according to an embodiment of the present invention; 
     FIG. 3 is a block diagram showing a lock control apparatus 25 according to the embodiment of the present invention; 
     FIG. 4 is a diagram showing types of status of a lock variable in accordance with a first embodiment of the present invention; 
     FIG. 5 is a diagram showing operations for a LOCK request in accordance with the first embodiment of the present invention; 
     FIG. 6 is a diagram showing operations for a SETLS request in accordance with the first embodiment of the present invention; 
     FIG. 7 is a diagram showing operations for an UNLOCK request in accordance with the first embodiment of the present invention; 
     FIG. 8 is a diagram showing exemplary operations in accordance with the first embodiment of the present invention; 
     FIG. 9 is a diagram showing types of status of a lock variable in accordance with a second embodiment of the present invention; 
     FIG. 10 is a diagram showing operations for a LOCK request in accordance with the second embodiment of the present invention; 
     FIG. 11 is a diagram showing operations for a SETLS request in accordance with the second embodiment of the present invention; 
     FIG. 12 is a diagram showing operations for an UNLOCK request in accordance with the second embodiment of the present invention; 
     FIG. 13 is a diagram showing exemplary operations in accordance with the second embodiment of the present invention; 
     FIG. 14 is a diagram showing types of status of a lock variable in accordance with a third embodiment of the present invention; 
     FIG. 15 is a diagram showing operations for a LOCK request in accordance with the third embodiment of the present invention; 
     FIG. 16 is a diagram showing operations for a SETLS request in accordance with the third embodiment of the present invention; 
     FIG. 17 is a diagram showing operations for an UNLOCK request in accordance with the third embodiment of the present invention; and 
     FIG. 18 is a diagram showing exemplary operations in accordance with the third embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     A lock control apparatus and method in accordance with preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. 
     Referring to FIG. 1, a multi-processor system includes four processors 201 to 204, four secondary caches 205 to 208, and two main storages 211 and 212. Each processor 201 to 204 has a first cache therein. The processors 201 and 202 share the secondary caches 205 and 206, and the processors 203 and 204 share the secondary caches 207 and 208. The main storages 211 and 212 are divided into a plurality of banks (e.g., two) including banks A (213) and B (214). 
     Corresponding to the main storages 211 and 212, the secondary caches 205 and 206 are divided into the two banks, and the secondary caches 207 and 208 also are divided into the two banks. The secondary caches 205 and 207 are connected to the main storage 211 via a system bus 209, and the secondary caches 206 and 208 are connected to the main storage 212 via a system bus 210. 
     A bank of the two banks to be accessed, is determined according to a certain bit in a request address from the processors 201 to 204. Accordingly, when an address outputted from the processors 201 to 204 represents (e.g., corresponds to) bank A, the processors 201 and 202 access the main storage 211 through the secondary cache 205, while the processors 203 and 204 access the main storage 211 through the secondary cache 207. 
     Similarly, when an address outputted from the processors 201 to 204 represents (e.g., corresponds to) the bank B, the processors 201 and 202 access the main storage 212 through the secondary cache 206, while the processors 203 and 204 access the main storage 212 through the secondary cache 208. 
     The secondary caches 205 to 208 operate in accordance with a store-in protocol. In the store-in protocol, data written to the secondary cache (e.g., caches 205 through 208) is not written to the main storage (e.g., main storages 211 and 212) until a certain timing. 
     Further, each of the secondary caches 205 to 208 reads information in the other secondary cache coupled to its same (e.g., common) bus, through the respective system buses 209 and 210. 
     Referring to FIG. 2, the secondary cache 205 includes two input buffers 21 and 22 for receiving requests from the processors 201 and 202 via, for example, respective driving circuits (unreferenced) or directly therefrom, a selector 23 for selecting one of the requests from the input buffers 21 and 22 and from the system bus 209 via, for example, respective driving circuits (unreferenced) or directly therefrom, an address array 24 of the secondary cache, a lock control apparatus 25, two selectors 26 and 27 for selecting one of the requests from the lock control apparatus 25 and the selector 23, and two request buffers 28 and 29 for buffering requests from the selectors 26 and 27, respectively, in a &#34;first-in first-out&#34; (FIFO) manner. 
     According to a predetermined rule, the selector 23 selects one request of the three requests presented. For example, a &#34;round-robin&#34; scheme, in which requests are selected in rotation, may be employed. 
     The address array 24 comprises an array the same as that of the conventional cache memory, since the address array 24 stores tag addresses corresponding to each entry of a data memory (not shown). 
     The selectors 26 and 27 select an output of the lock control apparatus 25 when returning a reply for a lock request, and select an output of the selector 23 during the cache consistency control. 
     The secondary caches 206, 207, and 208 preferably have the same structure as the secondary cache 205 described above. 
     Referring to FIG. 3, the lock control apparatus 25 includes lock address registers 1 and 2 for storing an address of a lock variable with respect to a request selected by the selector 23. Lock status registers 5 and 6 store a status of the lock variable in the lock address registers 1 and 2, and lock address coincidence detection circuits 3 and 4 (each including, for example, a comparator and an AND gate, both of which are unreferenced) detect a coincidence between the address from the selector 23 and addresses stored in the lock address registers 1 and 2. A selector 7 selects one of the lock status stored in the lock status registers 5 and 6 according to the result of the lock address coincidence detection circuits 3 and 4. The lock address registers 1 and 2 each have a valid bit which indicates that the respective lock address register stores valid data. 
     The lock control apparatus 25 further includes processor number registers 9 and 10 for storing a specified number of each of the processors which issue a lock request, comparators 11 and 12 for detecting coincidence between the processor number outputted from the selector 23 and processor numbers stored in the processor number registers 9 and 10, a selector 13 for selecting one of the outputs of the comparators 11 and 12, and a control circuit 8 for controlling the lock address registers 1 and 2, the lock status registers 5 and 6, and the processor number registers 9 and 10. 
     Hereinbelow and referring to FIGS. 4-8, the operation of the lock control apparatus in accordance with the above-mentioned embodiment of the present invention will be described. In the description below, a secondary cache connected to a processor which issued a request, is called a &#34;local cache&#34;. 
     The lock status is modified by one of a LOCK request, a SETLS request, and an UNLOCK request as described below. 
     The LOCK request checks whether other processors have acquired a lock, and if none of the processors has acquired a lock, then the lock status is modified to the &#34;lock&#34; status. The SETLS request modifies the lock status of a bank, which has not been modified to the &#34;lock&#34; status in accordance with the LOCK request, to the &#34;lock&#34; status. The UNLOCK request updates the lock status of a bank, which has been modified to the &#34;lock&#34; status in accordance with the LOCK request or the SETLS request, to the &#34;unlock&#34; status. 
     Referring to FIG. 4, the lock variable has a status of a &#34;LCK&#34; and a &#34;ULS&#34;. The &#34;LCK&#34; indicates that a lock status of a processor connected to a selected secondary cache is the &#34;lock&#34; status, and that a lock status of other processors is the &#34;unlock&#34; status. The &#34;ULS&#34; indicates that a lock status of a processor connected to this secondary cache is the &#34;unlock&#34; status, and it is uncertain or unknown whether other processors have acquired locks. 
     Referring to FIG. 5, the leftmost column shows a lock status of the local cache, the center column shows a lock status of caches other than the local cache, and the rightmost column shows action taken for a LOCK request. 
     FIG. 5 is applied to both bank A and bank B simultaneously, because a processor issues LOCK requests to both banks. However, those banks A and B operate differently for modifying the lock variable status under the LOCK request. A row of &#34;BANK A:&#34; in FIG. 5 is applied only if an applied bank is bank A, and a row of &#34;BANK B:&#34; is applied only if an applied bank is bank B. 
     FIG. 5 is based on the premise that bank A is locked by a LOCK request. However, the locked bank may be bank B, or any bank determined by an address. 
     According to FIG. 5, when a lock variable status of the local cache is &#34;LCK&#34; and a processor number is different, the lock control apparatus returns a &#34;lock fail&#34; signal, since another processor has already acquired a lock. 
     When a lock variable status of the local cache is &#34;ULS&#34; and a lock status of caches other than the local cache is &#34;ULS&#34;, the lock control apparatus returns &#34;lock success&#34;, since no processors have acquired a lock. 
     Moreover, if the local cache is bank A, a lock variable status of the local cache becomes &#34;LCK&#34;, and a lock variable status of caches other than the local cache remains &#34;ULS&#34;. If the local cache is bank B, lock variable statuses of all the caches remain &#34;ULSI&#34;. 
     When a lock variable of a corresponding address is not registered in the local cache, the lock control apparatus operates almost the same as above. The only exceptions are that the lock control apparatus in the local cache (FIG. 3) registers a lock address to one of the lock address registers 1 and 2, validates a corresponding valid bit, and registers a processor number (e.g., a number of the processor issuing the lock request) to one of the corresponding processor number registers 9 and 10. 
     Referring to FIG. 6, the leftmost column shows a lock status of the local cache, the center column shows a lock status of caches other than the local cache, and the rightmost column shows action taken for a SETLS request. 
     According to FIG. 6, when a lock variable status of the local cache is &#34;ULS&#34; and a lock status of caches other than the local cache is &#34;ULS&#34;, a lock variable status of the local cache becomes &#34;LCK&#34;, and a lock variable status of caches other than the local cache remains &#34;ULS&#34;. 
     Referring to FIG. 7, the left column shows a lock status of the local cache, and the right column shows action taken for an UNLOCK request. 
     According to FIG. 7, when a lock variable status of the local cache is &#34;LCK&#34;, a lock variable status of the local cache becomes &#34;ULS&#34;. If the lock variable status of the local cache is &#34;ULS&#34;, or no entry, then no action is taken for the UNLOCK request because no lock to be &#34;unlocked&#34; exists. 
     Referring to FIG. 8, the operation of the lock control apparatus according to the first embodiment is described below. 
     First, assuming that all lock variable statuses are &#34;ULS&#34;, when the processor 201 issues a LOCK request, the lock control apparatus returns a &#34;lock success&#34; signal. By this LOCK request, the lock variable status of the secondary cache 205 is modified to &#34;LCK&#34; (FIG. 5). 
     Next, when the processor 201 issues a SETLS request, the lock variable status of the secondary cache 206 is modified to &#34;LCK&#34; (FIG. 6). Then, the processor 201 can access a shared area in the main storage 211. After the access, when the processor 201 issues an UNLOCK request, the lock variable statuses of the secondary caches 205 and 206 are modified to &#34;ULS&#34; (FIG. 7). 
     As is apparent from the above description, according to the first embodiment of the present invention, since the lock variable statuses of the secondary caches in all the banks are set to &#34;LCK&#34; by the SETLS request, the time required for accessing a shared area is reduced. 
     Hereinbelow and referring to FIGS. 9-13, the operation of the lock control apparatus in accordance with the second embodiment of the present invention will be described. The second embodiment is similar to the first embodiment but further includes a &#34;ULE&#34; status for the lock variable. 
     Referring to FIG. 9, the lock variable has a status of &#34;LCK&#34;, &#34;ULS&#34; or &#34;ULE&#34;. 
     The &#34;ULE&#34; indicates that a lock status of a processor connected to this secondary cache is the &#34;unlock&#34; status, and a lock status of other processors is also the &#34;unlock&#34; status. 
     Referring to FIG. 10, similarly to FIG. 5, the leftmost column shows a lock status of the local cache, the center column shows a lock status of caches other than the local cache, and the rightmost column shows the action taken for a LOCK request. 
     According to FIG. 10, when a lock variable status of the local cache is &#34;ULE&#34;, the lock control apparatus returns a &#34;lock success&#34; signal without checking other secondary caches. 
     Referring to FIG. 11, similarly to FIG. 6, the leftmost column shows a lock status of the local cache, the center column shows a lock status of caches other than the local cache, and the rightmost column shows the action taken for a SETLS request. 
     According to FIG. 11, when a lock variable status of the local cache is &#34;ULE&#34;, a lock variable status of the local cache becomes &#34;LCK&#34; without checking other secondary caches. 
     Referring to FIG. 12, similarly to FIG. 7, the left column shows a lock status of the local cache, and the right column shows the action taken for an UNLOCK request. 
     According to FIG. 12, when a lock variable status of the local cache is &#34;LCK&#34;, a lock variable status of the local cache becomes &#34;ULE&#34; upon issuance of an UNLOCK request, not &#34;ULS&#34; as in the first embodiment (e.g., FIG. 7). 
     Referring to FIG. 13, the lock control apparatus according to the second embodiment is described below. 
     First, assuming that all lock variable statuses are &#34;ULS&#34;, when the processor 201 issues a LOCK request, the lock control apparatus returns a &#34;lock success&#34; signal. By this LOCK request, the lock variable status of the secondary cache 205 is modified to &#34;LCK&#34;, and the lock variable status of the secondary cache 206 is modified to &#34;ULE&#34; (FIG. 10). 
     Next, when the processor 201 issues a SETLS request, the lock variable status of the secondary cache 206 is modified to &#34;LCK&#34; without checking the lock variable status of the secondary cache 208 (FIG. 11). Then, the processor 201 can access a shared area in the main storage 211. 
     After the access, when the processor 201 issues an UNLOCK request, the lock variable statuses of the secondary caches 205 and 206 are modified to &#34;ULE&#34; (FIG. 12). Thereafter, when the processor 201 issues a next LOCK request, the lock control apparatus returns a &#34;lock success&#34; signal without checking the lock variable status of the secondary caches 207 and 208 (FIG. 10). 
     As is apparent from the above description, according to the second embodiment of the present invention, since the lock variable status of &#34;ULE&#34; ensures that other processors do not acquire any locks, the time required for accessing a shared area is reduced even more than that in the first embodiment of the present invention. 
     Hereinbelow and referring to FIGS. 14-18, the operation of the lock control apparatus in accordance with the third embodiment of the present invention will be described. The third embodiment of the present invention is similar to the second embodiment, but further includes a lock variable status of &#34;ULL&#34;. 
     Referring to FIG. 14, the lock variable has a status of &#34;LCK&#34;, &#34;ULS&#34;, &#34;ULE&#34; or &#34;ULL&#34;. The &#34;ULL&#34; indicates that a lock status of a processor connected to the secondary cache is the &#34;unlock&#34; status, and a lock status of another processor is the &#34;lock&#34; status. 
     Referring to FIG. 15, similarly to FIG. 5, the leftmost column shows a lock status of the local cache, the center column shows a lock status of caches other than the local cache, and the rightmost column shows the action taken for a LOCK request. 
     According to FIG. 15, when a lock variable status of the local cache is &#34;ULL&#34;, the lock control apparatus returns a &#34;lock fail&#34; signal without checking other secondary caches. 
     Referring to FIG. 16, similarly to FIG. 6, the leftmost column shows a lock status of the local cache, the center column shows a lock status of caches other than the local cache, and the rightmost column shows the action taken for a SETLS request. 
     According to FIG. 16, when a lock variable status of the local cache is &#34;ULL&#34;, the SETLS request is not issued because &#34;ULL&#34; means that another processor has acquired a lock. 
     Referring to FIG. 17, similarly to FIG. 7, the left column shows a lock status of the local cache, and the right column shows action taken for an UNLOCK request. 
     According to FIG. 17, when a lock variable status of a cache other than the local cache is &#34;ULL&#34;, a lock variable status of a cache other than the local cache becomes &#34;ULS&#34; because a lock variable status of the local cache is modified to &#34;ULE&#34; from &#34;LCK&#34;. 
     Referring to FIG. 18, operation of the lock control apparatus according to the third embodiment is described below. 
     First, assuming that the lock variable statuses of the secondary cache 205, 206, 207, and 208 are &#34;ULE&#34;, &#34;ULE&#34;, &#34;ULS&#34;, and &#34;ULS&#34;, respectively, when the processor 201 issues a LOCK request, the lock control apparatus returns a &#34;lock success&#34; signal without checking the lock variable status of the secondary caches 207 and 208 (FIG. 15). By this LOCK request, the lock variable status of the secondary cache 205 is modified to &#34;LCK&#34; (FIG. 15). 
     Next, when the processor 201 issues a SETLS request, the lock variable status of the secondary cache 206 is modified to &#34;LCK&#34; without checking the lock variable status of the secondary cache 208 (FIG. 16). Then, the processor 201 can access a shared area in the main storage 211. 
     In this state, when the processor 203 issues a LOCK request, the lock control apparatus returns a &#34;lock fail&#34; signal (FIG. 15). By this LOCK request, the lock variable statuses of the secondary caches 207 and 208 are modified to &#34;ULL&#34; (FIG. 15). Thereafter, when the processors 203 and 204 issue a LOCK request, the lock control apparatus returns a &#34;lock fail&#34;, signal without checking other secondary caches (FIG. 15). 
     When the processor 201 issues an UNLOCK request, the lock variable statuses of the secondary caches 205 and 206 are modified to &#34;ULE&#34;, and the lock variable statuses of the secondary caches 207 and 208 are modified to &#34;ULS&#34; (FIG. 17). 
     As is apparent from the above description, according to the third embodiment of the present invention, since the lock variable status of &#34;ULL&#34; ensures that another processor acquires a lock, the time required for accessing a shared area is reduced even more than in the second embodiment of the present invention. 
     While the invention has been described in terms of several preferred embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.