Electrical computers and digital data processing systems: input/ – Access locking
Reexamination Certificate
1999-10-04
2002-11-05
Wong, Peter (Department: 2181)
Electrical computers and digital data processing systems: input/
Access locking
C710S220000, C710S240000
Reexamination Certificate
active
06477597
ABSTRACT:
FIELD OF THE INVENTION
The field of the invention is that of the allocation of the shared resources of a computer system to processes in such a way that a process can have exclusive allocation of a resource.
DESCRIPTION OF RELATED ART
In the prior art, a simple means is known that consists of placing a lock on a resource. An unlocked state of the lock allows the resource to be allocated to a process. A locked state prevents the resource from being allocated to the process. When a process needs to be allocated a resource, it accesses the state of this resource's lock by means of an atomic operation. An operation is considered atomic if the state of the lock cannot be modified by any other process between the start and the end of the operation. The atomic operation essentially consists of reading the state of the lock and setting it to the locked state. If at the start of operation, the state of the lock is unlocked, the resource can be allocated to the process in question. The locked state at the end of operation guarantees the exclusivity of the allocation to the process. In effect, another process performing an atomic operation on this lock reads a locked state at the start of operation, which prevents this resource from being allocated to it. The other process is then placed on standby until the resource is available, reiterating its atomic operation until it detects an unlocked state of the lock. The process in question returns the lock to the unlocked state when it no longer needs the resource.
This simple means is not entirely satisfactory for a large number of processes run in parallel in a large number of processors. In fact, if several processes need the same resource, the resource can only be allocated to one process, which has detected an unlocked state of the associated lock by means of its atomic operation. The moment the process holding the lock returns it to the unlocked state, a considerable number of processes run the risk of initiating atomic operations that have the consequence of occupying the system bus in an untimely way. The lock is generally resident in memory. In the case of a non-uniform access memory, the problem is amplified. A non-uniform access memory is a memory for which the access time varies as a function of the location of the processors relative to the location of the memory. It is noted that the atomic operations that have a shorter access time to the lock are privileged as compared to atomic operations that do not benefit from the shorter access time. This has a negative effect on the equitable allocation of the resource to the processes. In particular, the processes that benefit from a short access time run the risk of monopolizing the resource. Furthermore, the location of the valid state of the lock runs the risk of migrating uncontrollably within the memory.
One known solution consists of assigning a resource a token that can only be held by one process at any given time. When the process holding the token no longer needs the resource, it passes the token to one of the processes waiting for this resource. The problem is that of knowing what the process holding the token does if there is no process waiting for the resource. This requires independent management of the available tokens, which does not encourage simplicity.
SUMMARY OF THE INVENTION
The object of the invention is to provide a simple solution that eliminates the above-mentioned drawbacks of the prior art. The invention relates to a lock architecture for a computer system comprising several processors, such that each processor requesting a resource of the system takes control of said resource if a first lock state indicates that said resource is available and is placed on active standby if a second lock state indicates that said resource is busy. The architecture is characterized in that a lock is associated with a data structure that comprises:
a counter that indicates a number of processors that have requested said resource without having used it and then released it, the first lock state corresponding to a null value, the second lock state corresponding to a non-null value;
a first data item specific to said processor, switched from a first value to a second value by said processor detecting the second lock state;
at least one second data item specific to another processor, switched from a first value to a second value by said other processor detecting the second lock state;
so that the second value of the first data item places said processor on active standby until the first data item is set to the first value by said other processor releasing said resource,
so that said processor, having used said resource, sets the second data item to the first value if it detects that the second lock state exists after the release of said resource.
One notable advantage of the invention over the above-mentioned prior art is that a process seeking to be allocated a resource performs only one access to the counter at the instant it requests the resource. If the resource is available, the counter has the same effect as a conventional lock. If the resource is busy, the allocation of the resource is authorized on the initiative of the process that holds it. This has the effect of reducing the transactions in the system bus and making it possible to control the allocations of resources to the processes.
REFERENCES:
patent: 4435766 (1984-03-01), Haber et al.
patent: 4574350 (1986-03-01), Starr
patent: 5261108 (1993-11-01), Hayashi et al.
patent: 5548728 (1996-08-01), Danknick
patent: 5983015 (1999-11-01), Lee et al.
patent: 6178481 (2001-01-01), Krueger et al.
patent: WO 98 33119 (1998-07-01), None
“Fast Lock”, IBM Technical Disclosure Bulletin, vol. 31, No. 11, Apr. 1, 1989, pp. 136-141, XP000284976—entire document.
Sorace Jean-Dominique
Walehiane Nasr-Eddine
Bull S.A.
Kondracki Edward J.
Miles & Stockbridge P.C.
Vo Tim
Wong Peter
LandOfFree
Lock architecture for large scale system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lock architecture for large scale system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock architecture for large scale system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944305