Abstract:
The present invention discloses a Locking Protocol using Dynamic Locks and Dynamic Shared Memory which provides a method whereby a designated critical section monitors object status through employment of counters attached to the object=s definition that will increment and decrement during reading and writing.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to databases and more specifically, to real time database systems or software that allows multithreading, multitasking and concurrency, of multiple users performing reading and writing over the database or shared public data section. 
     The present invention provides a method whereby a designated critical section monitors object status through employment of counters attached to the object&#39;s definition that will increment and decrement during reading and writing. 
     In essence all threads are readers whether a thread is a reader thread or a writer thread since writer threads must read first. Therefore, while the present invention provides for a reader thread and a writer thread, basically there are only reader threads that can be converted into reader/writer threads without creating a new thread once the reader/writer thread has acquired all the objects for updating whereupon those database sections are locked and updated as opposed to locking the whole database. 
     As aforementioned, the method assumes that all threads are reader threads and those threads that update the database will store those changes in a buffer or cache memory until the end of the transaction or API called then the changes will be committed to the source database. 
     This method not only prevents deadlocks since no reader can become a writer until all of the required object are obtained but should prove to be more resource efficient since only those parts of the database being updated are locked as opposed to locking sections of or the entire database. 
     In addition, the current methodology of listing and acquiring object lock in some numerical order to prevent deadlocks using traditional locking primitive doesn&#39;t work in a database environment where the object identifier is a customizable variable that is indeterminate until runtime. The method of the present invention requires no application processing to order object for locking. This means that the order of acquiring lock by object could be completely random. 
     In general, there are two kinds of threads, reader and writer, which will both be reading the database until the changes need to be committed. At that time the thread, which is ready to commit its changes, will try to convert the reader lock over all its objects that need to be updated into writer lock atomically, this means that only if the thread is able to convert all its reader lock into writer lock over every single object at once will it commit its changes. Otherwise, it won&#39;t lock any object to write or read and will wait for the next object to be released by other threads and try again. 
     The present invention also provides that all reader locks must be converted into writer locks atomically to preserve the integrity of the database, whereby all the changes will take place simultaneously so that other users will read the changes regardless if multiple objects were updated. 
     The present invention provides a global critical section that is used to protect the counters, hereinafter referred to as “m-read”, “m-writer”, “m-lock” and “m-threads waiting&#39;, which inclusively represent the stats of any object or resource. 
     In operation, the “m-read” value indicates how many threads are reading the object. Considering that the “m-writer” can only have a value of zero or one due to the requirement that only one thread can be writing or updating at any given time, “m-writer” indicates whether or not the object is being updated at any given time. Two fields comprise m-lock, “m_numberObjectsAssigned” and “m-eventHandle”. The field “m_numberObjectsAssigned” represents how many objects are sharing this lock “m_lock” in the protocol code it is used to find out when to recycle the lock handle “m-lock” and “m-eventHandle” is an event handler used to synchronize the threads. The event handler is used to initiate a thread wait state when needed and will be signaled by the reader group release and writer group release functions when they are finished with the object or resource. 
     2. Description of the Prior Art 
     There are other methods designed for database concurrent updating. Typical of these is U.S. Pat. No. 4,648,036 issued to Gallant on Mar. 3, 1987. 
     Another patent was issued to Mohan, et al. on Jan. 4, 1994 as U.S. Pat. No. 5,276,835. Yet another U.S. Pat. No. 5,452,450 was issued to Delory on Sep. 19, 1995 and still yet another was issued on Nov. 21, 1995 to Okada as U.S. Pat. No. 5,469,567. 
     Another patent was issued to Slingwine, et al. on Mar. 4, 1997 as U.S. Pat. No. 5,608,893. Yet another U.S. Pat. No. 6,363,387 was issued to Ponnekanti, et al. on Mar. 26, 2002. Another was issued to Landresse on Apr. 9, 2002 as U.S. Pat. No. 6,370,528 and still yet another was issued on Aug. 12, 2003 to Ponnekanti as U.S. Pat. No. 6,606,626. 
     Another patent was issued to Houston, et al. on Jan. 17, 2006 as U.S. Pat. No. 6,988,105. Yet another Canadian Patent No. CA2429154 was issued to Mullins on May 23, 2002. Another was issued to Ghukasyan on Dec. 12, 2002 as International Patent Application No. WO 02/099700 and still yet another was issued on May 5, 2004 to Nixon, et al. as U.K. Patent No. GB2394816. 
     A method of performing update transactions in a database system to preserve consistent logical data states at all times. Each changeable data entry in the database is associated with an individual code field. When no update transaction is in progress, every code field is set to a first value. An update transaction is begun by changing a system state parameter from a NON-UPDATE to an UPDATE state. During the UPDATE state, the code fields of data entries to be added are marked with a second value and then inserted into the database. Code fields of entries to be deleted are marked with a third value. When this is complete, the system state parameter is set to a POST-UPDATE state. All code fields are then returned to the first value at which time the system is returned to the NON-UPDATE state. During the UPDATE state, all queries are given access to entries with first and third code field value. Conversely during the POST-UPDATE state, queries are allowed access only to entries with first and second code field values. 
     A method of controlling entry of a block of data is used with a high-speed cache which is shared by a plurality of independently-operating computer systems in a multi-system data sharing complex. Each computer system has access both to the high-speed cache and to lower-speed, upper-level storage for obtaining and storing data. Management logic in the high-speed cache assures that the block of data entered into the cache will not be overwritten by an earlier version of the block of data obtained from the upper-level storage. 
     A database network management method ensures consistency of modifications to data in a network of databases comprising a relational database which constitutes a reference database and at least one further database accessible in real time. The data of the relational database is duplicated at least in part in the further databases accessible in real time. To enable an application process to modify data in all of the database network, the method is as follows: (1) A data modification request in the SQL language is sent from the application process to a pool of server processes of a relational database management system, (2) a server process is assigned to the request for the duration of its processing, (3) the modification request in the dynamic SQL language is sent from the server process pool to a relational database management system and the request is executed, (4) the further databases in accessible in real time to which the modification request relates are determined, (5) the request is transferred to the further databases in a form compatible with a management system of each further database concerned, and (6) the modification request is executed in each further database concerned. 
     The present invention is an improved database system for reducing the wait time for database processing programs. This data system provides for the input/output of blocks of data in excess of the capacity of the buffer pool assigned to the database processing program. When a database processing program tries to refer to the same block as one already under update processing by another database processing program or tries to update the same block as one already under update processing by another data processing program, the system allows a reference or update without placing the database processing system in the waiting state. 
     A substantially zero overhead mutual-exclusion apparatus and method ( 90 ,  120 ) is provided that allows concurrent reading and updating data while maintaining data coherency. That is, a data reading process executes the same sequence of instructions that would be executed if the data were never updated. Rather than depending exclusively on overhead-imposing locks, this mutual-exclusion mechanism tracks an execution history ( 138 ) of a thread ( 16 ,  112 ) to determine safe times for processing a current generation ( 108 ,  130 ,  131 ) of data updates while a next generation ( 110 ,  132 ,  133 ) of data updates is concurrently being saved. A thread is any locus of control, such as a processor. A summary of thread activity ( 106 ,  122 ) tracks which threads have passed through a quiescent state after the current generation of updates was started. When the last thread related to the current generation passes through a quiescent state, the summary of thread activity signals a callback processor ( 104 ,  124 ) that it is safe to end the current generation of updates. The callback processor then processes and erases all updates in the current generation. The next generation of updates then becomes the current generation of updates. The callback processor restarts the summary of thread activity and initiates a new next generation of updates. All data-updating threads pass through a quiescent state between the time they attempt to update data and the time the data are actually updated. 
     A Client/Server Database System with improved methods for enhancing concurrency using a “row update” bit and deferred locking is described. Data rows in the system are designed to include ROW_DELETE and ROW_UPDATE status bits. When a transaction updates a row, it sets the ROW_UPDATE bit. When a transaction inserts a row, neither the ROW_UPDATE nor the ROW_DELETE status bits are set. When a transaction deletes a row, it sets the ROW_DELETE bit but the contents of the data row are left intact. Methods are described for processing database transactions (e.g., in response to SQL queries) using these status bits or flags, together with deferred locking techniques, in a manner that reduces locking overhead and increase concurrency. The approach provides a particular performance advantage over systems that employ row-level locking. 
     A method is provided in a multi-processing system where multiple user programs can operate concurrently and simultaneously to access a series of database access methods which hold multiple buffer units. Thus, there can operate simultaneously a series of Write operations to the buffer units which copy the buffer information into specialized file structures followed by a parallel series of Input/Output completion operations which test the results of the copy operations followed by parallel and simultaneous writing to the file structures of the storage control information necessary to maintain their physical integrity. 
     A Client/Server Database System with an enhanced Lock Manager for improving concurrency is described. The system tracks information about database columns that are updated in the Lock Manager, in addition to the exclusive lock on the data row (in case of data row locking) or data page (in case of data page locking). In particular, a new field, lrcolumns, is added to the system&#39;s record lock data structure to track which columns have been modified. When an exclusive lock is requested on a row of the table being updated in the update statement, the Lock Manager sets the value of lrcolumns. In the context of an exclusive lock that was acquired to update one or more columns of a data row, if an exclusive lock was used only to insert or delete (but not update) the data row, the lrcolumns field would be set to 0. Similarly, the lrcolumns field is 0 for locks that are not exclusive locks (e.g., shared locks). With the Lock Manager enhancement of storing information about updated columns, scan (i.e., database scan operation) can skip a row (i.e., does not block for a lock on the row) if at least one of the sargs that the row does not qualify is on a column that was not updated by the updater. The approach avoids a lot of unnecessary blocking, thereby improving concurrency significantly. 
     A method and system for updating a database structure. The database structure includes a dynamically changing list of control documents. A control document specifies tasks to be performed on the database structure. An agent finds an approved control document on the list such as by looking into a view of control documents. Processing the approved control document includes causing an execution of at least one task on the approved control document. Execution of such a task includes updating of the database structure, and may be implemented by the agent that found the control document or by another agent called by the agent. 
     The present invention provides a system and method for dynamic object-driven database manipulation and mapping system ( 3 A) which relates in general to correlating or translating one type of database to another type of database or to an object programming application. Correlating or translating involves relational to object translation, object to object translation, relational to relational, or a combination of the above. Thus, the present invention is directed to dynamic mapping of databases to selected objects. Also provided are systems and methods that optionally include caching components ( 3 A,  51 ), security features ( 303 ), data migration facilities, and components for reading, writing, interpreting and manipulating XML and XMI data files ( 7 ,  51 ,  52 ,  8 ). 
     A dynamic database management system ( FIG. 1 ) includes a data dictionary ( 101 ), a data importer ( 102 ) and a query front-end ( 103 ). The data importer automatically imports data from an input file into a database, while adding new tables for new attributes as necessary, and updating parameters and folders tables in the data dictionary accordingly, so that end-users may access the imported data by database queries through the query front-end. 
     Multiple clients are given concurrent access to a database component stored on a database by a server which has a shared cache. The cache has a memory store coupled to the database that holds a copy of the database component. The memory store has a store gate that controls access to the store. The clients when accessing the memory store do so with their own client thread each of which includes a server component that communicates with the store gate and the client with respect to the database component. The database server may include a notify thread that detects changes to the database component and notifies the memory store gate of the change. The store gate may then notify the client server components which then notify the clients which are accessing the changed database component. The database server may include a lock manager which causes the memory store gate to prevent writes to the memory store by all but one of the clients when the one client is writing to the memory store. 
     While these systems may be suitable for the purposes for which they were designed, they would not be as suitable for the purposes of the present invention, as hereinafter described. 
     SUMMARY OF THE PRESENT INVENTION 
     A primary object of the present invention is to provide means for synchronizing multiple threads reading and writing to a database. 
     Another object of the present invention is to provide means whereby multiple threads concurrently accessing a database can not be deadlocked. 
     Yet another object of the present invention is to provide a method wherein an object&#39;s definition has a pair of counters and a lock indicator that are used in conjunction with computer software instructions for controlling object updating. 
     Still yet another object of the present invention is to provide a method wherein the updated objects are retained in a buffer. 
     Another object of the present invention is to provide a critical section that is used to protect said counters which represent the stats of any object or resource. 
     Yet another object of the present invention is to solve the problem where the objects to be updated change dynamically at runtime. 
     Still yet another object of the present invention is to provide a mechanism wherein the memory overhead for each object is very small, therein helping programmers to build more granular and distributed database systems and increasing concurrency into the database. 
     Additional objects of the present invention will appear as the description proceeds. 
     The present invention overcomes the shortcomings of the prior art by providing a method whereby a designated critical section monitors object status through employment of counters attached to the object&#39;s definition that will increment and decrement during reading and writing operations. 
     The foregoing and other objects and advantages will appear from the description to follow. In the description reference is made to the accompanying drawings, which forms a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. These embodiments will be described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that structural changes may be made without departing from the scope of the invention. In the accompanying drawings, like reference characters designate the same or similar parts throughout the several views. 
     The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is best defined by the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING FIGURES 
       In order that the invention may be more fully understood, it will now be described, by way of example, with reference to the accompanying drawing in which: 
         FIG. 1  a block diagram of the present invention&#39;s method of updating utilizing dynamic locks and dynamic objects; 
         FIG. 2  is a flow chart of the present invention&#39;s method for changing reader threads into writer threads; 
         FIG. 3  is a block diagram of the functions utilized by the present invention to dynamically update using dynamic locks and dynamic objects; 
         FIG. 4 , shown is a block diagram of the present invention&#39;s reader lock; 
         FIG. 5  is a flow chart depicting the reader group release function of the present invention; 
         FIG. 6  is a flow chart depicting the writer group lock function of the present invention; 
         FIG. 7  is a block diagram of the present invention&#39;s method of utilizing a writer group release; 
         FIG. 8  is an example implementation of the method for the present invention&#39;s basic definitions utilizing C programming; 
         FIG. 9  is an example implementation of the method for the present invention&#39;s reader lock function utilizing C programming; 
         FIG. 10  is an example implementation of the method for the present invention&#39;s reader group release function utilizing C programming; 
         FIGS. 11A through 11C  is an example implementation of the method for the present invention&#39;s writer group lock function utilizing C programming; and 
         FIG. 12  is an example implementation of the method for the present invention&#39;s writer group release function utilizing C programming. 
     
    
    
     While certain novel features of this invention have been shown and described and are pointed out in the annexed claims, the invention is not intended to be limited to the details above, since it will be understood that various omissions, modifications, substitutions and changes in the forms and details of the device illustrated and its operation can be made by those skilled in the art without departing in any way from the spirit of the present invention. 
     Without further analysis, the foregoing will so fully reveal the gist of the present invention that others can, by applying current knowledge, readily adapt it for various applications without omitting features that fairly constitute essential characteristics of the generic or specific aspects of this invention. 
     DESCRIPTION OF THE REFERENCED NUMERALS 
     Turning now descriptively to the drawings, in which similar reference characters denote similar elements throughout the several views, the figures illustrate the Safety Check Latch Apparatus of the present invention. With regard to the reference numerals used, the following numbering is used throughout the various drawing figures.
           10  Method and System for a Locking Protocol using Dynamic Locks and Dynamic Shared Memory     12  critical section     14  process protocol changing reader threads into writer threads     16  functional implementation of  10       18  reader lock     20  reader group release     22  writer group lock     24  writer group release     26  data definition code example     28  reader lock code example     30  reader group release code example     32  writer group lock code example     34  writer group release code example       

     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The following discussion describes in detail one embodiment of the invention. This discussion should not be construed, however, as limiting the invention to those particular embodiments, practitioners skilled in the art will recognize numerous other embodiments as well. For definition of the complete scope of the invention, the reader is directed to appended claims. 
     Referring to  FIG. 1 , shown is a block diagram of the present invention&#39;s method of updating utilizing dynamic locks and dynamic objects. The process protocol for updating utilizing dynamic locks and dynamic objects of the present invention  10 , shown in Step S 1 , mandates that each user thread runs as a reader thread, in Step S 2 , whereupon each reader thread acquires reader locks object by object, shown in Step S 3 , and that each reader thread stores changes in a temporary storage, such as a buffer as shown in Step S 4 . In Step S 5 , if all reader locks are secured then said reader locks are atomically converted into writer locks, then, in Step  6 , all changes and calculation are committed to the database and all writer locks are released, as shown in Step S 7 . 
     Referring to  FIG. 2 , shown is a flow chart of the present invention&#39;s method for changing reader threads into writer threads. The process protocol for changing reader threads into writer threads  14  is determined by the need for changes to be committed to the resource, as illustrated in Step S 10 , whereupon the process critical section  12  converts the reader lock for all objects into writer locks simultaneously, as shown in Step S 12 , and in Step S 14 , if the conversion is completely successful, the changes are committed to the database, in Step S 16  and the thread releases all reader and write lock, as shown in Step S 18 . In Step S 20 , if the thread could not convert reader lock into writer lock for all objects then no writer locks are created and the thread exits the critical section and waits for the next object to be released by other threads, in Step S 22  and reenters the critical section  12  with Step S 12 . 
     Referring to  FIG. 3 , shown is a block diagram of the functions utilized by the present invention to dynamically update using dynamic locks and dynamic objects. The method and system of the present invention  10  provides functions  16  for dynamically updating a resource using dynamic locks and dynamic objects. Each of the functions are illustrated in the accompanying drawings in flowchart and illustrative code example. The functions are comprised of a reader lock  18 , shown in flowchart as  FIG. 4  and illustrated in code in  FIG. 9 . Reader group release  20 , shown in flowchart as  FIG. 5  and illustrated in code in  FIG. 10 . Writer group lock  22 , shown in flowchart as  FIG. 6  and illustrated in code in  FIGS. 11A ,  11 B and  11 C and writer group release  24 , shown in flowchart as  FIG. 7  and illustrated in code in  FIG. 12 . 
     Referring to  FIG. 4 , shown is a block diagram of the present invention&#39;s reader lock. The reader lock  18  provides that the reader thread acquires the critical section in Step S 100 . In Step S 102 , if no thread is ready to write to the object then in Step S 104 , the reader thread acquires reader lock to the object and, in Step S 106 , the reader thread release the critical section  12  and the object is returned locked for reading, as shown in Step S 108 . If any thread, in Step S 102  is ready to write the object and is not currently writing the object, Step S 110 , processing continues with Step S 104  or the object is being written wherethen in Step S 112  the reader thread releases the critical section  12 , and waits for the object to be released by the writer thread, as shown in Step S 114 , and attempts to acquire the critical section, shown in Step S 100 . 
     Referring to  FIG. 5 , shown is a flow chart depicting the reader group release function of the present invention. The reader lock release  20  provides that the reader thread acquires the critical section  12  in Step S 200 . In Step S 202 , the thread gets the next object in the array for lock release and releases the object reader lock, Step S 204 . In step S 206 , if other threads are waiting for this object and no other threads are waiting for this object, the thread waiting is woken up. In Step S 210 , if no other threads are waiting for this object, no lock is assigned to the object in Step S 212 . In Step S 214 , if no other threads are waiting for this lock, the lock is put back in the reusable lock list. In Step S 218 , if there are other objects in the array to be released processing continues with Step S 202  otherwise the thread releases the critical section, as shown in Step S 220 . 
     Referring to  FIG. 6 , shown is a flow chart depicting the writer group lock function of the present invention. The writer group lock  22  provides that the thread acquires the critical section  12  in Step S 300 . In Step S 302 , the thread gets the next object in the array for reader lock release and releases the object reader lock for every object in the array and assigns lock to every object in the array, Step S 304 . If any object is not ready for update, Step S 306 , then in Step S 314 , the thread releases the critical section and waits in Step S 316  for the next object ready for update whereupon, in Step S 318 , the thread acquires the critical section and processing continues with Step S 304 . In Step S 306 , if all objects in the array are ready to be updated, the thread acquires written locks over every object in the array, as shown in Step S 308 , Whereupon, in Step S 310 , the critical section is released and the thread returns the objects ready to be updated, Step S 312 . 
     Referring to  FIG. 7 , shown is a block diagram of the present invention&#39;s method of utilizing a writer group release. The writer group release  24  provides that the thread acquires the critical section  12  in Step S 400 . In Step S 402 , the thread releases the object writer lock. In step S 404 , if any thread is waiting for this object, the thread waiting is woken up. In Step S 408 , if no other threads are waiting for this lock, clean up object lock, step S 410 . In Step S 412 , if no other writer threads are using the object lock, the lock is released back to the lock list, as shown in Step S 414 . If there are other objects in the array to be released, Step S 416 , processing continues with Step S 402  otherwise the thread releases the critical section, as shown in Step S 418 . 
     Referring to  FIG. 8 , shown is an example implementation of the method for the present invention&#39;s basic definitions utilizing C programming. For illustrative purposes, an implementation of the object data definitions  26  are illustrated with the foreknowledge that other programming languages may be employed with similar results. 
     Referring to  FIG. 9 , shown is an example implementation of the method for the present invention&#39;s reader lock function utilizing C programming. For illustrative purposes, an implementation of the reader lock function  18  is illustrated in code  28  with the foreknowledge that other programming languages may be employed with similar results. 
     Referring to  FIG. 10 , shown is an example implementation of the method for the present invention&#39;s reader group release function utilizing C programming. For illustrative purposes, an implementation of the reader group release function  20  is illustrated in code  30  with the foreknowledge that other programming languages may be employed with similar results. 
     Referring to  FIGS. 11A through 11C , shown is an example implementation of the method for the present invention&#39;s writer group lock function utilizing C programming. For illustrative purposes, an implementation of the writer group lock function  22  is illustrated in code  32  with the foreknowledge that other programming languages may be employed with similar results. 
     Referring to  FIG. 12 , shown is an example implementation of the method for the present invention&#39;s writer group release function utilizing C programming. For illustrative purposes, an implementation of the reader lock function  24  is illustrated in code  34  with the foreknowledge that other programming languages may be employed with similar results. 
     While certain novel features of this invention have been shown and described and are pointed out in the annexed claims, the invention is not intended to be limited to the details above, since it will be understood that various omissions, modifications, substitutions and changes in the forms and details of the device illustrated and its operation can be made by those skilled in the art without departing in any way from the spirit of the present invention. 
     Without further analysis, the foregoing will so fully reveal the gist of the present invention that others can, by applying current knowledge, readily adapt it for various applications without omitting features that fairly constitute essential characteristics of the generic or specific aspects of this invention.