Abstract:
A method for efficiently updating as shared data structure in a multiprocessor environment comprises accessing a queue variable associated with time-based data events in the data structure. Information associated with the queue variable is used to determine the point of insertion of a new time-based data event. If a new time based data event is inserted, the data of the queue variable of a preceding time-based data event is altered to identify the new time-based data event. An embodiment employing a contention-free locking mechanism is also disclosed.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This application is related to the application of Muhammad Arshad entitled “Method For Locking A Shared Resource In A Multiprocessor System”, which application is assigned to the assignee of the present application, and is being filed concurrently herewith. 
    
    
     TECHNICAL FIELD 
     This invention relates to a system for accessing resources shared by a plurality of processors. More particularly, the invention relates to a method for efficiently accessing a shared memory in a multiple processor computing environment. 
     BACKGROUND OF THE INVENTION 
     A data “structure” refers to related data stored in a computer memory location. To enhance operating efficiency, a data structure may be “shared” by a plurality of processors which require the same information to perform various tasks. Synchronizing access to a shared data structure is a great challenge in designing software for computers with multiple processors, and is especially important whenever multiple processors attempt to update information in a data structure. Indeed, without synchronization, the performance of a system including a shared data structure is severely degraded. This is because when one processor performs a data structure update, it is common for the entire data structure to be inaccessible (or “locked”) to other processors. In other words, the non-updating processors must wait until the data structure is “unlocked” before the information contained in the structure can be accessed or updated. Another significant problem affecting the performance of a multiprocessor environment with shared resources is the inability of multiple processors to simultaneously perform updates on discrete data structure events without blocking each other. 
     Therefore, there is a need for an efficient, non-blocking operation for updating shared data structures while maintaining FIFO behavior in a multiprocessor environment. 
     SUMMARY OF THE INVENTION 
     This need is addressed and a technological advance is made in the art by the present invention which provides simultaneous, nonblocking access to shared data structures in a multiprocessor environment. More particularly, the present invention uses information contained in a queue variable to enable multiple processors to perform concurrent updates of discrete events in a shared data structure. 
     In one preferred embodiment, lock-free multiple processors access a common data structure by identifying and reading queue variables. The queue variable contains information relating to a specific data event in a data structure. More particularly, the queue variable identifies the time at which the data event occurs, the addresses of linked data subevents which occur concurrently and an address pointer for identifying the next time-based data event in the data structure. A processor accesses an address location of a queue variable and stores it in a first register. The address location of the queue variable is read from the processor&#39;s first register and is used to access the contents of the queue variable. The contents of the queue variable are stored in a second register of the processor. The second register is accessed to determine the time at which the data event associated with the queue variable occurs, and whether there is a subsequent event in the data structure. Each queue variable in a data structure is traversed until the processor finds the proper point in the data structure to insert a new time-based data event. When the point of insertion is found, the processor updates the queue variable of the preceding time based data event to point to the new time-based data event. The queue variable associated with the new time-based data event is updated to point to the next time-based data event (that is, the time-based data event which occurs immediately after the newly inserted time-based data event) in the data structure. Advantageously, multiple processors may concurrently update time-based data events without blocking each other. 
     In another preferred embodiment of the present invention, multiple processors use a contention-free locking mechanism to update a shared data structure. Similar to the previous embodiment, a processor accesses and assigns the address location of a queue variable in its first register. The queue variable address is used to access the information associated with the queue variable so it may be stored in the processor&#39;s second register. The data stored in the second register is read by the processor to determine the time at which the data event associated with the queue variable occurs, and whether there is a subsequent data event in the data structure. Each queue variable in a data structure is traversed by the processor until the position in the data structure at which the processor wishes to insert a new time-based data event is reached. The processor uses a locking mechanism to lock the data structure up to the point of insertion of the new time-based data event. Just prior to insertion of the new time-based data event, the processor determines whether it is still proper to insert the new data event at this position in the data structure. This query accounts for the possibility of another processor updating the data structure before the new time-based data event has been inserted. After successful insertion of the new time-based data event, the locking mechanism is released. Advantageously, the entire data structure need not be locked and the FIFO behavior of data structures updates is maintained by determining whether a new time-based data event is still proper in view of actions taken by other processors. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a simplified block diagram of an exemplary multiprocessor environment including a shared local memory in which the preferred embodiment of the present invention may be practiced; 
     FIG. 2 is a flow diagram illustrating the steps for concurrent, non-blocking modification of the data structure stored in the shared local memory shown in FIG. 1; 
     FIG. 3 is a flow diagram illustrating the steps for modifying the data structure stored in the shared local memory shown in FIG. 1 using a contention free locking mechanism; 
     FIG. 4 is a simplified block diagram of an exemplary multiprocessor environment including a local shared memory and a globally shared locking mechanism; and 
     FIG. 5 is a flow diagram illustrating the steps for acquiring the locking mechanism shown in FIG. 4; and 
     FIG. 6 is a flow diagram illustrating the steps for releasing the locking mechanism shown in FIG.  4 . 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 is a simplified block diagram illustrating a multiprocessor environment in which the preferred embodiment of the present invention may be practiced. Multiprocessor environment  100  is disposed in a computer system and comprises processors  102 ,  106 ,  110  and shared random access memory (RAM) module  120  which are linked by designated data links. In this embodiment, each processor includes a dual register memory for storing instructions and data relating to update operations. More particularly, processor  102  includes first register  104 A, second register  104 B and is linked to RAM module  120  via data link  103 . Similarly, processor  106  includes first register  108 A, second register  108 B and data link  107 . Processor  110  includes first register  11   2 A, second register  112 B and is linked to the RAM module via data link  113 . In the preferred embodiment, the first register in each processor stores address information identifying a particular time based data event. The second register stores data associated with the “queue” variable of the time based data event, as described below. 
     Local shared RAM module  120  stores data structures which are accessed by processors  102 ,  106  and  110  for performing various tasks. Although only three processors are shown in this particular environment, those skilled in the art will recognize that many more processors may be coupled to a local shared memory. Also, for purposes of clarity, only a single data structure  125  is shown within RAM module  120 . Operational shared memories may contain many more data structures. 
     Data structure  125  is comprised of four data events which occur at four discrete time periods. Each time-based data event occurs at a predefined time (e.g., T0, T1, T2 or T3) and is linked with a plurality of subevents which occur concurrently during the predefined time. More particularly, data event  130  occurs at time “T0” and has a linked list of a plurality of subevents (that is, subevents  131 ,  132  and  133 ) which occur simultaneously at time T0. Similarly, data event  140  occurs at time T 1  along with subevents  141  and  142 . Data event  150  occurs at time T2 along with subevent  151 . Data event  160  occurs at time T3 concurrently with subevents  161 ,  162 ,  163  and  164 . 
     Time based data events  130 ,  140 ,  150  and  160  include predetermined update variables which are accessed whenever modification of data structure  125  is attempted. More particularly, each time based data event includes a “queue” variable for identifying the temporal location of the data event, a pointer to the next time-based data event in the data structure and a pointer to the linked list of subevents associated with the data event. For example, the queue variable associated with data event  130  contains data identifying time T0, a pointer to the next data event (namely, data event  140 ) and a pointer to the linked list of subevents  131 ,  132  and  133 . In this embodiment, the queue variable is stored in a specified portion of each time based data event. More particularly time based data events  130 ,  140 ,  150  and  160  store their respective queue variables in data memory portions  135 ,  145 ,  155 , and  165 , respectively. 
     Shared RAM module  120  also includes a memory for retaining addresses of each data structure stored in the module and a queue variable relating to the first time based data event of each data structure. In this embodiment, “head” segment  123  stores its own address information in first register  127 , and a queue variable in second register  129 . During an update operation, head segment  123  is accessed prior to attempting insertion of a new time based data event or a new subevent in data structure  125 . 
     FIG. 2 is a flow diagram illustrating the steps performed in multiprocessor environment  100  for updating data structure  125 . For purposes of example, assume that processor  102  needs to update data structure  125  by inserting a new time based data event between existing time based data events  140  and  150 . In other words, a new time based data event occurring at time T12 must be inserted between the time based data events which now occur at times T1 and T2. In an alternative embodiment, processor  102  inserts a new subevent in a linked list associated with an existing time based data event. All embodiments use a non-blocking procedure (that is, multiple processors may update data structure  125  simultaneously as long as no two processors attempts to insert a new event in exactly the same place) which uses readily-available machine operations for updates. 
     The process begins in step  200  in which processor  102  writes the address location of head segment  123  in its first register  104 A. In this example, shared RAM module  120  only contains a single data structure (i.e., data structure  125 ). In alternative embodiments, processor  102  is initialized with information enabling it to access the register within head segment  123  relating to the data structure which it needs to update. The process continues to step  202  in which the processor reads the queue variable information stored in second register  129  and writes the data associated with the queue variable in its second register  104 B. The queue variable contains information which points to the first time based data event associated with data structure  125 . In some circumstances, there is no existing data structure for the processor to update. In those circumstances, the queue variable in head segment  123  indicates that there is no time based data event associated with the address location stored in the second register such that the processor may insert new time based data events without regard to existing time based data events. In this example, data structure  125  is populated with multiple time based data events such that processor  102  must perform updates which take into consideration existing data events. 
     The process continues to decision step  204  in which processor  102  determines whether there is a time base data event indicated by the queue value which is currently stored in its second register  104 B. In this example, the queue value stored in second register  104 B points to first time based data event  130  in data structure  120 . In those circumstances in which there are no time based data events stored in a data structure, the outcome of decision step  204  is a “NO” determination and the process continues to step  214  as described below. If the outcome of decision step  204  is a “YES” determination, the process continues to decision step  206  in which processor  102  determines if the time of the new event (that is, the event to be inserted by processor  102 ) occurs later than the time of the event which is identified by the information contained in the queue value stored in second register  104 B. In other words, processor  102  determines whether the new event occurs later in time than the time based data event identified by the queue value currently stored in second register  104 B. Recall that the queue value now stored in register  104 B was retrieved from head segment  123  and identifies first time based data event  130 . In this example, the new event is to be inserted between time based data events T1 and T2. Therefore, the outcome of decision step  206  is a “YES” determination and the process continues to step  208  in which processor  102  transfers the information currently stored in second register  104 B to first register  104 A. Processor  102  then uses the pointer stored in processor  104 A to access the next time based data event. The queue variable found in the next time based event is then read and copied to second register  104 B. In this example, processor  102  transfers the queue variable information from second register  104 B to first register  104 A. The queue variable information currently stored in first register  104 A points to memory  135  in first time based data element  130  in data structure  125 . The queue variable stored in memory  135  is read and assigned to second register  1   04 B in processor  102 . The process then returns to step  202  so that the procedure may be reiterated until the outcome of decision step  206  is a “NO” determination. A “NO” determination resulting from decision step  206  indicates that the processor has arrived at the point in data structure  125  at which the new time based data event no longer occurs later in time than the event currently identified by the queue variable stored in second register  104 B. In this example, a “NO” outcome from decision step  206  would indicate that second register  104 B of processor  102  stores the queue variable associated with second time based data event  140  which identifies third time based data event  150 . In other words, the new time based data event to b inserted does not occur later in time than third time based data event  150 . Receipt of a “NO” determination from decision step  206  requires the process to proceed to decision step  210  in which processor  102  determines whether the time of the new event to be inserted into the data structure occurs at the same time as the event identified in second register  104 B. In other words, in decision step  210 , processor  102  determines whether the new data event to be inserted into data structure  125  corresponds to an existing time based data event. If the outcome of decision step  210  is a “YES” determination, the process continues to step  212  in which the new event is inserted into the linked list of an existing time based event and the process ends in step  220 . In this example, however, processor  102  endeavors to insert a new time based data event in between existing time based data events  140  and  150  which occur at times T1 and T2, respectively. Therefore, the outcome of decision step  210  is a “NO” determination and the process continues to step  214  in which processor  102  updates the queue variable of the time based event to be inserted to point to the next time based event which immediately follows it. In this example, the queue variable of the new time based event T12 is updated to point to the next time based event occurring at time T2 (or time based data event  150 ). The process continues to step  216  in which processor  102  attempts to update the queue value currently associated with time based data event  140  (that is, the time based data event occurring immediately before the new time based data event) to point to the new time based data event occurring at time T12. The process continues to decision step  218  in which processor  102  determines whether the insertion of the new time based data event was successfully completed. If the outcome of decision step  218  is a “YES” determination, the process ends in step  220 . If the outcome of decision step  218  is a “NO” determination, the process returns to step  202  in which the procedure is reiterated until successful insertion of the new time based data event. The above-described procedure may be concurrently implemented by multiple processors for updating a single data structure. In other words, processors  102 ,  106  and  110  may simultaneously update data structure  125  so long as two processors do not attempt to enter a new time based data event in exactly the same place. Indeed, a non-successful insertion indicates that at least two processors are contending to insert a time based data event in exactly the same place, in which case one processor successfully updates the structure and the other retries. 
     FIG. 3 illustrates the steps performed in multiprocessor environment  100  in accordance with a protocol in which portions of a single data structure may be temporarily locked while updates occur. A substantial portion of this process is identical to the process described in FIG.  2 . Accordingly, the identical steps are not discussed in great detail. The process begins in step  300  in which processor  102  writes the address associated with head segment  123  to first register  104 A. In step  302 , processor  102  uses the address stored in first register  104 A to read and store the contents of the queue variable found in head segment  123  in second register  104 B. The process continues to decision step  304  in which processor  102  determines whether the queue variable stored in register  104 B has a pointer to a time based data event. If the outcome of decision step  304  is a “NO” determination, the process continues to step  314  described below. If the outcome of decision step  304  is a “YES” determination, the process continues to decision step  306  in which processor  102  determines whether the new event to be inserted into data structure  125  occurs at a later point in time than the time of the event identified by the queue variable stored in second register  104 B. If the outcome of decision step  306  is a “YES” determination, the process continues to step  308  in which processor  102  assigns the contents of second register  104 B to first register  104 A and uses the pointer now stored in first register  104 A to read and store the queue variable of the next data event in  104 B. The process then returns to step  302  for iteration until the processor arrives at the place in the data structure at which the time of the new event is no longer later than the time of the event currently associated with the queue variable stored in register  104 B. If the outcome of decision step  306  is a “NO” determination, the process continues to step  310  in which processor  102  determines whether the time of the new event to be inserted into data structure  125  is equal to the time of the event currently identified by the queue variables stored in second register  104 B. If the outcome of decision step  310  is a “YES” determination, processor  102  simply inserts the new event at the head of the linked list associated with the timed based event identified by the queue variables stored in second register  104 B. In other words, processor  102  inserts a sub-event in an existing time-based data event. If the outcome of decision step  310  is a “NO” determination, the process continues to step  314  in which processor  102  locks the time-based data event identified by the address stored in first register  104 A of processor  102  and the process ends in step  324 . The process continues to decision step  316  in which processor  102  determines whether the place in the data structure at which the new time-based data event is to be inserted is still proper. Decision step  316  accounts for those situations in which processor  102  is preceded by another processor which has inserted its new time-based data event at precisely the same position at which processor  102  wishes to insert its own new time-based data event. If the outcome of decision step  316  is a “NO” determination, processor  102  releases the lock in step  318  and the process returns to step  302  so that the procedure may be reiterated. If the outcome of decision step  316  is a “YES” determination, the process continues to step  320  in which processor  102  inserts the new time-based data event between the time-based data event identified by the address stored in first register  104 A and the time-based data event identified by the address of the pointer associated with the queue variable information stored in second register  104 B. The process continues to step  322  in which processor  102  releases the lock and the process ends in step  324 . Advantageously, the above-described process enables multiple processors to concurrently access and update data structure  125  as long as each processor attempts to insert new data events in discrete locations. 
     FIG. 4 is simplified block diagram of a multiprocessor environment which shares a locking mechanism. More particularly, multiprocessor environment  400  comprises processors  402 ,  404 ,  406  and  408  which are linked to local shared memory  410  via designated links  403 ,  405 ,  407  and  409 , respectively. Locally shared memory  410  is comprised of discrete memory segments which are associated with each of the processors in multiprocessor environment  400 . In this embodiment, discrete memory segment  412  is associated with processor  402  and includes successor variable  420 , spin variable  422  and register  423 . Similarly, data segment is associated with processors  404  and includes successor variable  424 , spin variable  426  and register  427 . Data segment  416  serves processor  406  and includes successor variable  428 , spin variable  430  and register  431 . Data segment  418  is associated with processor  408  and includes successor variable  432 , spin variable  434  and register  435 . Local shared memory  410  is interconnected to globally shared memory  440  via data link  441 . In this embodiment, data link  441  is also interconnected to each of the discrete data segments via a designated link. More particularly, data links  413 ,  415 ,  417  and  419  interconnect data segments  412 ,  414 ,  416  and  418 , respectively, to data link  441 . Global shared memory  440  includes locking mechanism  442  which is comprised of tail variable  444  and head variable  446 . In the preferred embodiment, tail variable  444  includes address information identifying the last processor in the queue waiting to acquire lock  442 . Head variable  446  includes pointer information for identifying a processor waiting to acquire lock  442 . If the lock is available, tail variable  444  points to the head variable and the value in head variable  446  indicates the lock is free. 
     Each data segment within local shared memory  410  includes information used by its associated processor for acquiring lock  442  in global shared memory  440 . A first variable called a “successor” variable identifies the processor, and can be modified to indicate that the processor is using or waiting for lock mechanism  442 . A second variable referred to as “spin” variable indicates that the processor associated with this variable is waiting to acquire lock  442 . 
     The steps required by a processor in multiprocessor environment  400  to acquire lock mechanism  442  is described in FIG.  5 . For purposes of example, assume processor  402  wishes to acquire locking mechanism  442  so that it may update a data structure (not shown). The processor begins in step  500  in which processor  402  initializes its successor variable  420  to indicate that locking mechanism  442  is busy. Simultaneously, processor  402  initializes spin variable  422  to indicate that the processor must wait in the event that locking mechanism  442  is occupied. The successor variable and the spin variable are initialized prior to acquiring locking mechanism  442  in the event that the lock is occupied as described below. The process continues to step  502  in which processor  402  reads the value of tail variable  444  of locking mechanism  442  and stores it in register  423 . Simultaneously, processor  402  writes the address of its successor variable  420  to tail variable  444 . In step  504 , processor  402  reads the data stored at the address identified in register  423  and writes the address associated with successor variable  420  and spin variable  422  at the address identified in register  423 . 
     The process continues to decision step  506  in which processor  402  determines whether the value read in previous step  504  indicates that the lock is free. If the outcome of decision step  506  is a “YES” determination, the process ends in step  510 . If the outcome of decision step  506  is a “NO” determination, the process continues to decision step  508  in which processor  402  reads spin variable  422  to determine whether the processor must wait for the lock. If the outcome of decision step  508  is a “YES” determination, step  508  is repeated until the outcome is a “NO” determination indicating that the waiting process has ended in step  510 . At the end of the waiting process, processor  402  has acquired locking mechanism  442 . 
     FIG. 6 is a flow diagram illustrating the steps performed by a processor in multiprocessor environment  400  when releasing locking mechanism  442 . For purposes of example, assume processor  402  is currently occupying locking mechanism  442 . The processor begins in decision step  600  in which processor  402  determines whether the address currently stored in the tail variable is equivalent to the address of its successor variable  420 . If the value of tail variable  444  is the same as the address of its successor variable  420 , processor  402  is at the end of the lock acquisition queue. If the outcome of decision step  600  is a “NO” determination, the processor continues to decision step  608  described below. If the outcome of decision step  600  is a “YES” determination, the process continues to step  602  in which processor  402  initializes head variable  446  to indicate that locking mechanism  442  is currently busy. In step  604 , the processor  402  reads the current value from tail variable  444  into register  423  and simultaneously writes the address of head variable  446  in tail variable  444 . In step  606 , processor  402  stores the address of head variable  446  at the location identified by the address in register  423 . 
     In decision step  608 , processor  402  determines whether its successor variable  420  has been updated. If the outcome of decision step  608  is a “NO” determination, the process continues until the outcome of the decision step is a “YES” determination. A “YES” determination causes the process to proceed to decision step  610  in which processor  402  determines whether successor variable  420  points to head variable  446 . If the outcome of decision step  610  is a “NO” determination, another processor is waiting to acquire the lock. The process continues to step  612  in which processor  402  passes the lock to the waiting process by using the address found in its successor variable to update the spin variable of the waiting processor. If the outcome of decision step  610  is a “YES” determination, the process continues to step  613  in which processor  402  reads the value from head variable  446  into register  423  and simultaneously writes a value into head variable  446  indicating the lock is free. Decision step  614  determines whether the value read from register  423  indicates the lock is busy (that is, the processor determines if it is the same value it initialized in step  602  to indicate a busy lock). If the outcome of decision step  614  is a “YES” determination, the process ends in step  616  and the lock is now free. If the outcome is a “NO” determination, the process continues to step  612  described above. Advantageously, locking mechanism  442  maintains the FIFO behavior of lock acquisition by exchange of information via the successor and spin variables using swap as the only atomic primitive. 
     Although the invention is described with respect to preferred embodiments, those skilled in the art may devise numerous other arrangements without departing from the scope of the invention.