Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2001-07-06
2004-01-13
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S151000, C711S158000, C711S168000
Reexamination Certificate
active
06678802
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data processing systems, and more particularly to controlling access to resources available to such systems.
BACKGROUND OF THE INVENTION
Multiprocessing computer systems are commonplace. Where more than one process operates concurrently and has access to the same piece of shared data or resource, it is important that access restrictions are employed to ensure the integrity of that data. It is essential that valid data is always read and that updates to the data are correctly recorded. Without careful control, this could quite easily not be the case. If, for example, a process A is reading a bank account total in order to perform some arbitrary calculation, at the same time that a process B is updating the account total, then the calculation will most likely be performed using the old total and will therefore be incorrect. This is simply not acceptable.
It is common, therefore, to use locks to control access to a shared resource. A lock is typically allocated in either shared or exclusive mode. A process, in possession of a shared lock (e.g. a reader), may access the resource for which it holds the lock, alongside other processes also in possession of the shared lock. In other words, multiple readers may access the resource concurrently. When however a writing process (a writer) wishes to access the same resource, no other process must be accessing the data. The writer must therefore obtain an exclusive lock on the resource.
Shared/exclusive locks are frequently implemented using a simple count of the number of readers. The count is increased every time a new reader accesses the shared resource, and decremented when the reader relinquishes access. A writer may only access the resource when the reader count is at zero. This is because it is important that reading processes always view the most up-to-date information.
This method however, presents a number of problems. If one of the readers terminates abnormally, then it can be very difficult to adjust the count. If the count is not decremented properly then this can result in a writer waiting indefinitely for a process that is no longer accessing the resource.
Another problem relates to prioritising access to the resource. For example, if a resource already has one or more readers, should a writer or another reader be granted access when the current owner relinquishes access? With the above method, the choice depends upon whichever process gets there first. This can mean, for example, that a high priority writer is waiting unnecessarily on a low priority reader.
Both the above problems stem from the fact that insufficient information can be recorded about the readers. The dynamic nature of the number of readers, means that recording information is tricky. This method is therefore inefficient and lacks recoverability.
An alternative is to maintain a list of readers in a complex chain (linked list) structure. This solution can record appropriate information about each reader (such as a thread id and priority information) and is also recoverable. If, for example, a writer has been waiting for an exclusive lock on a resource for an excessively long a period of time, then the reader list can be traversed in order to check that the thread ids listed are still actively accessing the resource.
Unfortunately there is a significant performance overhead associated with the upkeep of such a structure. The number of readers in the list varies dynamically and thus storage allocation can become a problem. Further, it is necessary to lock the whole or a part of the structure before making a change to it. Deleting a reader also typically requires additional serialisation.
SUMMARY OF THE INVENTION
Accordingly, the invention provides a method for controlling access by a plurality of concurrently operating processes to a resource, said method comprising the steps of: allocating an area of storage and defining a pre-determined number of storage slots therein; responsive to a request by one of said processes for shared access to said resource, determining whether to allocate shared access, and if so, allocating said requesting process shared access, said step of allocating shared access comprising: acquiring one of said storage slots; and wherein said method further comprises: responsive to a request by one of said processes for exclusive access to said resource, determining whether to allocate exclusive access, and if so allocating said requesting process exclusive access, said step of allocating exclusive access comprising: acquiring all of said storage slots.
It should also be noted that although the terms multi-processing system and process are used throughout, this should also be taken to encompass threads which may run under the control of a process. Threads within one process may compete for access to a resource with threads from another process. However, threads within the same process may also compete for access to a resource. The invention is preferably aimed at controlling access to a resource in both such situations.
According to one embodiment, the step of determining whether shared access is to be allocated comprises selecting a storage slot and determining whether that storage slot is owned by another process (i.e. has been acquired by another process). Responsive to the slot not being owned by another process, the selected storage slot is acquired.
Alternatively, the step of determining whether shared access is to be allocated, comprises checking whether any one of a set of storage slots is unallocated and assuming that one is, an unallocated slot is acquired and shared access is allocated. The set of storage slots may comprise a part of the storage area, the whole storage area (i.e. slots 0 to n) or indeed, more than one pass of the storage area may be completed (e.g. 2
n
).
According to one embodiment, each process has at least one thread having a unique thread id. Each thread id is preferably unique not only within a process, but across all processes having access to the resource. A process indicates ownership of a storage slot by associating the thread id of the thread requesting access to the resource with the storage slot. (Ownership of a storage slot is exclusive and may not therefore be shared with another process.) A process also has priority information associated therewith.
In one embodiment, this priority information is used when allocating a process with shared access. Responsive to determining that a first storage slot is owned by another process, an action is performed based on the priority of the requesting process. If the requesting process has a low priority then the requesting process waits for the selected storage slot to be relinquished by the owning process and acquires the selected slot once this has occurred. If the requesting process has a high priority then storage slots continue to be selected until an unallocated storage slot is found and this unallocated slot is then acquired. Preferably no more than a predetermined number of storage slots are selected, and responsive to none of said selected storage slots being available, the requesting process waits for the last of the selected slots to be relinquished by an owning process. Once this last slot has been relinquished it is then acquired by the process requesting shared access.
According to one embodiment, an input queue is associated with at least one of the storage slots. When allocating shared access to the resource, if processes are queued on a selected storage slot, another storage slot is selected (e.g. either an unallocated slot or one without an associated queue). According to one embodiment, processes are queued according to their priority information. This may be used, for example, to move a high priority process to the head of a queue. This requires careful control to ensure that low priority requests do not wait indefinitely for access to the resource.
According to one embodiment, a process requesting shared access and having a low priority selects a storage slot from a first part of
Elmore Reba I.
Ohlandt Greeley Ruggiero & Perle L.L.P.
LandOfFree
Method and apparatus for controlling access by a plurality... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for controlling access by a plurality..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for controlling access by a plurality... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3219593