[Company Logo Image]    

Home Feedback Contents Search

6.3 Lock Constructs
6.1 Node Model 6.2 ASM Model 6.3 Lock Constructs 6.4 Shared Memory 6.5 Distr. Memory 6.6 VPP Systems 6.7 OS View 

Back Home Up Next

6.3 Lock Constructs

Details of all important variations of the lock constructs of stress-flow will now be discussed. In actual implementation it was possible to include many different lock functionalities as options of the same universal construct, but, it is easier to explain the different logic functionalities as separate constructs.

 

FIG. 33: Diagram of single entry point FIFO lock

FIG. 33 shows single entry point FIFO lock. This is by far the most commonly used lock. It contains means to indicate if the lock is already reserved (has an owner), the FIFO and optionally built in or associated actual parameter storage area. The states this lock can be in are following: A. No owner and empty FIFO, B. An owner and empty FIFO, C. An owner and non-empty FIFO. In a practical implementation the FIFO is simply the queue of suspended tasks waiting for this lock and the owner a binary (True/False) flag and/or owner ID indicating if the owner already exists in case the FIFO is empty. If FIFO is non-empty there has to be a current owner. RESERVE command sent to this lock can either reserve the lock right-away if the lock had no owner at this moment, or it can result in placing the command sending task at the end of the FIFO and suspending it. RELAX command sent by current owner pops a suspended task from the front of the FIFO making it the owner or clears the ownership flag when the FIFO was empty. The SCHEDULE command simply sends the new task defined as pair (“Lock L”, “Sequence to Execute A”) to the Task Sending Interface (TSI).

Adding the WAIT RELAX command interface to this lock is very simple. All that this requires is “Wait ID” storage for ID of a single suspended task. WAIT RELAX command issued while the lock remained in its “non-relaxed” state would simply suspend the caller and store its ID. A RELAX command restores a task identified by a non-empty “Wait ID.”

Implementation of the “ordered” commands with regular FIFO lock shown on FIG. 33 requires placing a PRE-RESERVE element in the FIFO or, if FIFO is empty, taking ownership of the lock until DO-RESERVE is called and then subsequent RELAX. Normally, it is the suspended tasks that are placed in the FIFO, but with the PRE-RESERVE command, there is no suspended task to be placed there. Such construction of the FIFO lock therefore requires allocating some special structure/variable to be linked into the FIFO. The most natural location for it is the caller task stack. Such structure can therefore be allocated as part of the PRE-RESERVE command functionality, which later inserts this variable into the FIFO. This method has many advantages. There is no need to search for the PRE-RESERVE place in FIFO to issue the DO-RESERVE or UN-RESERVE commands because the FIFO element itself is directly accessible by the caller task on its stack. Also, with a compiler already supporting object-oriented mechanisms, the PRE-RESERVE and UN-RESERVE commands can be easily implemented as parts of the constructor and destructor of said structure allocated on the stack. 

 

FIG. 33A: Diagram of single entry point “last-only” lock

FIG. 33A shows single entry point “Last Only” lock. This lock is less commonly needed, but useful for some applications such as previously discussed electrical circuit emulation. The underlying idea is that when more one task tries to access the lock, only the most recent request past current owner is processed. This can be done one of two ways. The FIFO from FIG. 33 can be replaced with a single storage spot for one suspended task. When RESERVE command arrives, the previously stored task is “pushed out,” meaning: restored and made believe as if it actually executed its calling sequence. This involves setting the lock in the special state in which the SCHEDULE and optional WAIT RELAX commands from the pushed out task are ignored. Doing it exactly this way in situation where the lock stores the actual parameters would require being able to tell the “pushed out” task to not store the parameters or giving it a different area to store the parameters to in order to prevent corruption of parameters of currently running task. Another way of implementing “Last Only” scheme is keeping the FIFO as in FIG. 33 and storing incoming tasks as before, but having modified logic behind RESERVE command. In such a case RESERVE command would simply pop the previous element and push a new one.

Ordered commands are implemented on this lock in similar fashion as with the regular FIFO lock. In spite of the fact that there might be no FIFO here there still is a need to allocate the ordered element structure on the caller’s stack since the lock’s single slot now has to point to this structure. The FIFO solution will obviously need it as well.  

 

FIG. 33B: Diagram of the connector lock construct

FIG. 33B shows the diagram of the connector lock construct. Even though the connector construct is a container for references to other locks, it has the same interface as a single lock and could even be implemented in hardware same way as other type locks in computer architectures geared toward stress-flow. As previously explained, the idea behind the connector construct is to be able to build a configurable list of stress-flow atoms (or independent tasks) to run. Internally, this can be a linked-list or an array containing references to separate stress flow atoms. Each such reference must always include the lock reference and identification of sequence of instructions to run. A connector construct could be static with list of tasks built at compilation time or dynamic where the tasks are added and removed as needed. Apart from interface to dynamically add tasks to the list (optionally also remove), the interface of the connector lock to the user is same as interface of other type locks.

FIG. 33B shows a connector lock with three task definitions stored in it. The RESERVE command sent to the connector lock will attempt to reserve all locks of all tasks on the list together. If this is not possible, it will reserve none. One practical way to implement this construct is to loop through the list of tasks reserving their locks and let the loop be suspended by the first unavailable lock after first releasing all the successfully reserved other locks, if any.  Once the suspending lock becomes available, it will restore the connector lock’s loop – which will attempt to reserve all locks again. From the standpoint of the connector construct’s caller, this is still one RESERVE command.

Once the RESERVE command gets processed, the caller will proceed to the SCHEDULE command. Processing SCHEDULE command by the connector involves looping through the list and sending all tasks from the list to the Task Sending Interface.

Return value processing and corresponding WAIT RELAX command are rarely needed with connector constructs since trying to return a single value from many targets does not make much sense. The scheme can still be implemented by assuming that the returned value will be the random last value returned by one task from the list. In such case WAIT RELAX would stall the caller until all tasks in the list are sent RELAX command, thus stalling the caller until all tasks from the list send their RELAX commands.

The usefulness of the connector mechanism further shows advantages of passing parameters through lock structure rather than through stack. If the parameters are to be passed through stack(s), the caller has to allocate a new stack and store parameters on it. The connector in turn has to allocate a new stack for each task on the list and copy parameters to each of them. If parameters are to be passed through space allocated in the lock or with it, there is no need to allocate any stack, and a simple extension of the lock architecture can eliminate the need for copying the parameters in many cases by allowing a lock to receive a pointer to another lock storing the parameters rather than hosting parameters itself. Therefore, the connector lock or the first task on the list can be used to store the parameters and the other locks would be given a pointer to it.

To allow “ordered” calls, the connector mechanism can implement mechanisms for PRE-RESERVE commands in a way described with regular FIFO lock. This requires creating a number of PRE-RESERVE data structures on the caller stack or on in a specially allocated memory block. Both methods work fine, the second one is less efficient but easier to implement without writing special compiler code. PRE-RESERVE issued to the connector lock therefore loops through the tasks on the connector’s list, allocates the needed data structure for each of them and issues the PRE-RESERVE command to each of them. The other “ordered” command implementations likewise run similar loops.  

 

FIG. 33C: Diagram of the collector lock construct

FIG. 33C shows the diagram of one way of implementing the collector lock construct with three inputs. The idea behind the collector construct is to be able to merge two or more different independently running paths into one. A collector stress flow atom has one body and several headers where all of them have to be called before the sequence of instructions of the stress-flow atom/task gets executed. The collector lock is the internal way to implement such mechanism.

In order for this construct to work correctly in the normal situation of calls to separate headers coming at random moments, with possibly some paths generating many calls ahead of the others, it has to sort the incoming calls by header to which they correspond and by order in which they came. There are several ways to accomplish that. One way may involve indexing incoming calls (RESERVE requests) with the header number and inserting them inside the FIFO next to other calls from the same set. Another might involve building a special two-dimensional FIFO. FIG. 33C shows the method that was found to be superior, because it can be easily implemented out of existing constructs and because it totally eliminates any need for looping in order to insert new elements to the FIFO. FIG. 33C thus shows implementation of three header collector construct C. Locks C1, C2, and C3 are the standard, most common one input FIFO locks shown on FIG. 33. To the outside, it appears like three separate locks with standard previously discussed interface, to the associated sequence of instructions A it appears as a single lock. To make a call to first header, a calling task simply calls (Lock C1, Sequence of Instructions A) pair the same way it would call any other lock and sequence pair. To make a call to the second header, a calling task calls pair (Lock C2, Sequence A), and so on. This way the Task Sending and Task Receiving Interfaces always deal with generic pair of lock ID and sequence of instructions ID as task definitions while accomplishing variety of different functionalities. This not only greatly simplifies the whole system design, but also makes possible implementation of much of it in hardware.

Step by step, the tasks calling separate headers deal with the sub-locks of the collector exactly as if they were separate locks. RESERVE command either reserves the lock right away or it suspends the caller until it can reserve it. Once the lock is reserved, the caller writes the actual parameters and proceeds to the SCHEDULE command. If the lock-storage method of passing parameters is used, it is only natural that each sub-lock provides its own storage – since each header has different parameters and often of different layout and type. The SCHEDULE command sent to a specific sub-lock passes through it but does not go to the TSI – it gets processed through the common collector lock parts (circuitry). This common circuitry counts or otherwise remembers which sub-locks processed their SCHEDULE commands. If a newly received SCHEDULE commands is the last one, completing the whole set, it goes through thus sending the (Lock C, Sequence A) pair to the TSI. If it is not the last one, it only updates the state of the collector lock properly and otherwise gets ignored. If any of the calling tasks process their WAIT RELAX commands they get stalled until scheduled sequence A processes its RELAX command. Collector lock distributes the RELAX command it receives to all its sub-locks, releasing them simultaneously.

All “ordered” call functionality is accomplished by the collector lock’s individual sub-locks. No additional circuits or functionality has to be added to the common parts of the collector lock for the “ordered” calls to work.

A variation of the collector construct can use the “last-only” locks from FIG. 33A instead of FIFO locks from FIG. 33, thus creating “last-only” collector lock.  

 

FIG. 33D: Diagram of the “firstof” lock construct

FIG. 33D shows the diagram of one way of implementing the “firstof” lock construct with three inputs. The idea behind the “firstof” construct is to be able to merge two or more different independently running paths into one but in a different way than previously discussed regular “collector” lock. A “firstof” stress flow atom has one body and several headers where only one of them has to be called before the sequence of instructions of the stress-flow atom/task gets executed. The calls to the other headers within a set that already had one call go through are ignored. The “firstof” lock is the internal way to implement such mechanism.

In order for this construct to work correctly in the normal situation of calls to separate headers coming at random moments with possibly some paths generating many calls ahead of the others, it has to remember which headers (lock inputs) are falling behind and by how many steps, so a proper number of calls that did not make it as first can be ignored. FIG. 33D shows a method to implement three input “firstof” lock using regular one-input FIFO locks as sub-components connected to the special common circuitry in a way similar to previously discussed collector lock. The output of each sub-lock goes to special counter circuitry which counts how many calls a specific input/header has fallen behind. The sub-locks work exactly the same way as described with the previous collector lock. When a sub-lock outputs a task and its corresponding counter is zero, this means that the given call made it as first – it is allowed to pass to the TSI but before it does, it increments the counters of all the other sub-locks. When a sub-lock outputs a task and its corresponding counter is greater than zero, it is ignored (it does not get passed into the TSI), it only decrements its corresponding counter as to record the fact that a task to be ignored has been ignored.

All “ordered” call functionality is accomplished by the “firstof” lock’s individual sub-locks. No additional circuits or functionality has to be added to the common parts of the “firstof” lock for the “ordered” calls to work.

 

FIG. 33E: Diagram of the “cancelrest” lock construct

FIG. 33E shows the diagram of one way of implementing the “cancelrest” lock construct with three inputs. Functioning of this lock is very similar to the “firstof” lock. The only difference is that “cancelrest” cancels/kills the tasks that did not make it first instead of ignoring them. Such a feature is very useful in implementing redundant calculations and many other applications where the late paths may not come through at all. Safe termination of the unneeded tasks and corresponding releasing of unneeded resources also improves system performance. The “cancelrest” uses FIFO locks as sub-components just like the previously discussed locks, but needs a new “CANCEL” internal signal for canceling an incoming task. The functioning of this signal with FIFO lock is as follows: When an “occupied” lock receives this signal, the owner of the lock is terminated and the lock given equivalent of “RELAX” command. When the lock is unoccupied (which also means its FIFO is empty), a counter similar the one discussed with “firstof” is incremented. A lock reservation request that arrives when the counter is greater than zero results in terminating the task making the request. This is true of both RESERVE and “ordered” call PRE-RESERVE command. Please note that in almost every practical programming application of this scheme the counter gets used very rarely, meaning that the CANCEL command almost always finds an occupied lock. This is especially true of the “ordered” calls where the PRE-RESERVE commands are issued at the very beginning of the process that will result calling the “cancelrest” lock. Killing incoming tasks from within the lock is easy because through its core functionality, the lock already retrieves and operates on task handles or system level task access means in order to suspend and restore the task. Killing a task cannot however involve just stopping to execute it for good. It is necessary that a task gets to execute its destructor sequences, which are placed by the compiler at the end of each sequence of instructions by every object-oriented compiler. Killing a task therefore involves suspending it and then resuming it at the beginning of its destructor sequence. This way all necessary resource reference counters are properly updated, no longer needed memory released, and persistent stack(s) status properly updated in order for it to be released when last reference is destroyed. This scheme is much easier to implement than some mechanisms within prior-art compilers such as “try/throw/catch” compiler exception construct which create and process the destructor sequences in similar way.

Creating a “cancelrest” lock out of above described modified FIFO locks is straightforward as shown on FIG. 33E. The CANCEL inputs are marked CAN1, CAN2, and CAN3. An output signal from one sub-lock issues CANCEL requests to all other sub-locks and then is routed to the TSI. For example, when Lock R2 sends a task to its output, this causes sending CANCEL commands to locks R1 and R3, and then the task outputted by R2 is sent to the Task Sending Interface (TSI).

The Task Receiving Interfaces (TRI) and Task Sending Interfaces (TSI) are the remaining components of processing nodes of stress-flow to be described. One of the key benefits the architecture of stress-flow is the fact that TRIs and TSIs are the only components that vary in organization in diametrically different applications of stress-flow. The key varying element of different application is how much separated different processing nodes are or how they physically communicate with one another. The other components of the architecture of stress-flow – namely the processors executing sequences of instructions and locks used to initiate other tasks need not be aware of the interconnection details. In different applications, they may pass identifications of locks and of sequences of instructions to execute in application specific format, but the key issue is that only TRIs and TSIs actually process that information, allowing almost complete portability of software developed in the spirit of stress-flow.

Back Home Up Next
Send mail to info@stressflow.com with questions or comments.
Copyright © 2005-2010. All Rights Reserved. Patents Pending in Multiple Jurisdictions.
First published 03/29/06. Last modified: 06/25/10