Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-12-27
2004-11-23
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06823337
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the field of computer system data access protection.
2. Background Information
Collections of data called databases are well known. Computer systems which can be used by multiple users are also well known. Database programs provide fast and efficient access to records in a database. To properly handle the distribution and retrieval of the data, data processing systems often include database management programs. These programs provide easy access to database information.
One common configuration of a database is one that is made up of various tables with each table containing rows and columns of information. The information stored across one row in the table would make up one record and the fields of the record would be the columns in the table. In other words, the table would contain rows of individual records and columns of record fields. Because one record may contain more than one field of information, the information of the field would make up the columns of the database table. Other database configurations are found in the art.
Database management programs often must support multiple users and should enable each user to access the same table concurrently. However, when more than one user on a multi-user system attempts to access a database, problems may arise. If one user is reading from the database, while another user is writing to the database, the data integrity of the data read by the first user is suspect. If two users are attempting to write data to the database, what is actually written is unpredictable and so data integrity is suspect. To minimize these and other data integrity problems, locking schemes have been implemented, wherein only one user at a time was allowed to access the database.
Locking a database meant that, whenever a user was reading from or writing to the database, only that user was allowed to access that database, while all other users were locked out. Thus, the problem of one user writing data to a database while another prior user is reading the same data from the database was eliminated. The problem of two users simultaneously writing to a database was also eliminated.
However, locking created system bottlenecks which severely impacted overall system performance, even in a small system with a small number of users. A single user could monopolize a database by gaining access and holding it locked. Other users were forced to wait for access until that first single user released the lock on the database. After the first user released the lock, a second user was free to gain access to the database and monopolize it just as the first user had. That time spent idly waiting was unproductive, wasted and, therefore, impaired system performance. For a larger system with a large number of users attempting to access the same database, the effective result was the same regardless of whether a single user was monopolizing the database. That was because even if no single user attempted to monopolize a single database, the aggregate time spent by all of the users attempting to access the database meant that each user spent a significant amount of time idly waiting for a turn in accessing the database.
In order to address this locking problem and to improve multi-user system performance by reducing the amount of time each user spent waiting for the same database, locks were distinguished based on the type of user access to the database. Thus locks were distinguished as read locks or write locks. A user having a read lock merely prevented another user from writing to the database, while allowing other users to obtain read locks and, concurrently, to read from the same database. A user having a write lock excluded all access by other users until the user having the write lock released the write lock. A system having read locks and write locks to achieve concurrency is also known as “several readers and one writer” system.
The above-described practice of protecting shared data tables involves allowing either multiple concurrent readers of the data, or at most one writer with no readers. However, a problem with this practice is that changing the table (writing) can be expensive because it blocks readers during the updates. In a multi-processing environment with numerous CPUs (central processing units), modifying performance critical shared data tables can become a bottleneck adversely affecting system performance.
Therefore, data access could be made more efficient and the bottleneck problems in the prior art overcome by an improved data access method.
SUMMARY OF THE INVENTION
It is, therefore, a principal object of the invention to provide a method for a one writer, multiple readers, shared data table concurrent access.
It is another object of the invention to provide a method and apparatus that solves the above mentioned problems so that one writer and multiple readers, can share a data table through concurrent access.
These and other objects of the present invention are accomplished by the method and apparatus disclosed herein.
According to an aspect of the invention, at most one writer is allowed to be updating a shared data table while multiple readers are using the same table.
According to an aspect of the invention, there are three data elements used. The first of these is a serialization mechanism, e.g., a semaphore (in the case of an IBM AS/400, an “SLIC QuGate object”). This mechanism is used to ensure at most one writer is modifying the shared data. Readers do not use this serialization at all. The second of these is a table/array of elements. Each element of the table must be able to be updated atomically by a processor with a load or store instruction. The third of these is an atomic, integer counter that indicates how many shared data elements are contained in the table.
According to an aspect of the invention, inserting a new element into the shared unsorted data table by a writer includes locking the table, wherein other writers are prevented from writing to the table, putting the new element at the end of the table, incrementing the counter, thereby making the new element visible to all readers, and unlocking the table.
According to an aspect of the invention, removing an element at a position in the shared unsorted data table by a writer includes locking the table, copying the table so that the element to be removed is at the end of the table, decrementing the counter, and unlocking the table.
According to an aspect of the invention, reading from the shared data table by a reader includes looping through all elements of the table, loading and caching each element of the table, and read-only processing each element of the table.
These and other aspects of the invention will become apparent from the detailed description set forth below.
REFERENCES:
patent: 5544345 (1996-08-01), Carpenter et al.
patent: 5561794 (1996-10-01), Fortier
patent: 5737536 (1998-04-01), Herrmann et al.
patent: 5822588 (1998-10-01), Sterling et al.
patent: 5890161 (1999-03-01), Helland et al.
patent: 6023706 (2000-02-01), Schmuck et al.
Y. Edmund Lien et al., International Conference on Management of Data and Symposium on Principles of database Systems. Session: Consistency, Concurrency, and crash recovery. Publisher ACM Press New York, USA, p. 9-14, 1978.*
Gray et al., Modern Languages and Microsoft's Component Object Model. Communication of the ACM, May 1998/vol. 41. No. 5.
Armstrong Troy David
Lucke Kyle Alan
International Business Machines - Corporation
Lynt Christopher H.
Metjahic Safet
Nguyen Cindy
Payne Leslie J.
LandOfFree
One writer, multiple readers, shared data table concurrent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with One writer, multiple readers, shared data table concurrent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and One writer, multiple readers, shared data table concurrent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300947