This started out as an appendix to a text that I wrote and used in the 1980's that applied Data Directed Design to developing Systems Software. A P P E N D I X D =================== R U L E S F O R C O O P E R A T I V E P R O C E S S E S ============================================================= The design technique for cooperative processes can be summarized with the following set of rules. Processes are designed as if each data flow is controlled by the standard operations defined in Chapter 2, '!' and '?'. If the calling program uses '!' to send data to the subroutine then the subroutine will use '?' to accept its data from the caller, and vice versa. When a process becomes a restartable routine, a data flow is implemented by calls to it that communicate the operation (new, old, end) plus any data to be transferred. Inside the subroutine the operations on the data flow are replaced by special "resume" or "transfer" operations. How to Make a Process Restart Itself Whenever It is Called 1. Add an extra variable (QS) to the process to keep track of where the process was. 2. Make sure that all data objects, especially QS, registers and locations, can be put in a safe place. This is called the state vector or SV. 3. Code each transfer to do the following set QS; save SV; exit 4. Put code that has the following effect at the entry to the subroutine: if operation<>new then begin reload SV; if operation = end then EOS:=true else EOS:=false; end else{operation=new} begin EOS:= false; create SV with QS equal to Q1 end; goto [QS]; Q1: 5. Other programs call the process as a subroutine whenever transfer is required. It has an operation and data as parameters. 6. If the subroutine returns data to the calling program there is also a Boolean parameter to signal the end of the data by becoming true when no more data is available. 7. Make sure that the calling routine can not interfere with the subroutine's data (SV). 8. Make sure that this data includes a place for recording the next place to start (QS) Particular Techniques - In Alphabetical Order of Language Type In the following, the name or number of the routine is represented by nn, the data flow by ff, and the operands of the !? by xx in the subroutine, and yy in the calling program. ASSEMBLER Knuth [] (Section 1.4.5.2) gic=ves a way of coding symetrical co-routines by adding a linking section of code. Here I give ways to code semi-co-routines -- where the subprogram or function manages and hides the restarting of the routine at the palce where it just stopped. Notation Location := #literal -- Place value in location Location := Location -- Copy location. Probably uses a register. [Address] -- content of address. CALL address -- call subroutine RETURN -- exit from subroutine pop, push -- stack operations on the runtime time stack. Try to keep the subroutines data in local storage, well away from any stacks and data used by other routines. If this is possible then they do not have to be moved when the routine transfers control. It is advisable to have three distinct entries rather than an operation code. The following code assumes a stack is used to handle subroutine calls. Data is being sent to program nn: Caller's operation Subroutine call ff!yy put yy in common area; CALL nn ff!new CALL nnN ff!end CALL nnE Place the following code at the start of the program: nnE: EOF := #1 nn: STACK:=SV; RETURN nnN: EOF := #0; CALL nnX Code each ff?xx as CALL nnX copy common area to xx At the end: nnX pop STACK into SV; RETURN Data is being accepted from the subroutine by the caller: Caller's operation Subroutine call ff?yy CALL nn; get yy from common area; ff?new?yy CALL nnN; get yy from common area; ff?end CALL nnE Place the following code at the start of the program: nnE: EOF := #1 nn: STACK:=SV; RETURN nnN: EOF := #0; Code each ff!xx by: copy xx to common area CALL nnX At the end: nnX: pop STACK into SV; RETURN BASIC. Code as line numbers nn00-nn99. Expect at least two subroutines to use the same variable in a catastrophic manner! Three entries: GOSUB nn00 new GOSUB nn01 data GOSUB nn02 end Subroutine nn00 Initialize saved QS and EOF = 0: if data being sent then exit nn01 Retrieve SV: ON QS+1 GOTO nn10, nnp0, nnq0,nnr0, etc. nnn2 EOF=-1: GOTO nn01 nn10 etc. . . .... QS=1: GOTO nn99 nnp0 . . .... QS=2: GOTO nn99 nnq0 . . nnoo QS=3: GOTO nn99 nnr0 . . . nn99 Save SV: RETURN If the SV is separated from all other data in the program, then it need not be saved. COBOL. See Jackson 75. FORTRAN Put the SV in a labeled COMMON block (Label as /nnSV/) that no other routine alters. Use the parameter IOP in the following calls to communicate the operation: new CALL N(1,DAT) old CALL N(2,DAT) end CALL N(3,DAT) Use IQS for the pointer to the restart point, and make sure it is in the common block. Use a computed GOTO in the form of GOTO (1001,1002,1003, etc.), IQS plus labels in a special sequence. The general form of the transfer code is: IQS=i RETURN 100i etc. PASCAL and C The normal approach requires flat code. In Pascal, the SV must be global. In C put SV in static storage. An alternative to flat code is to have two special procedures or functions written which can be called in the body of the procedure or function: RESTART( operation, SV ) TRANSFER( SV ). Where SV is a sufficiently large array to hold all the variables of the routine, and operation has one of three values of new, old, or endit. procedure TRANSFER ( var SV ); begin save all variables in SV; also pop stack frame of TRANSFER and subroutine (including PC) into SV exit normally end Procedure RESTART( operation, SV) begin if operation = new then initialize SV else if operation=endit then set EOF:=true; Reset variables and push SV values onto the stack again exit normally end; Under UNIX and C you can use pipes, but may wish to improve the performance of a pair of programs connect by a pipe (P1|P2). In a non-UNIX environment with the C language, you can get some of the benefits of UNIX as below. If you have a good macroprocessor, such as "M4", the code can be generated automatically. Each restartable function in C is now coded as follows: o All non-external variables must be defined after the first "{" as "static". o If the restartable function consumes data, then each suspension point in turn is coded as suspend(2), suspend(3), and so on up to suspend(n), where suspend(i) is {QS=i;return;Qi:;} o If the restartable function produces data, then use {QS=i;return(expr);Qi:;} for suspend(i). o At the start of the routine and after the declarations add: static int QS=1; if(opcode==NEW) QS=1; switch(QS) {case 1: goto Q1; case 2: goto Q2; ... case n: goto Qn;};Q1: --------------------Text added February 2008------------------- Duff's Device[http://www.csci.csusb.edu/dick/cs320/lab/09.html] makes the code simpler: o All non-external variables must be defined after the first "{" as "static". o If the restartable function consumes data, then each suspension point in turn is coded as suspend(2), suspend(3), and so on up to suspend(n), where suspend(i) is {QS=i;return; case i:;} o If the restartable function produces data, then use {QS=i; return(expr); case i:;} for suspend(i). o At the start of the routine and after the declarations add: static int QS=1; if(opcode==NEW) QS=1; switch(QS) {case 1: o At the end of the function add }//end switch Using the line numbers as values of QS makes the following macros work [Tatham00]. #define restartable int static QS=0; switch (QS){ case 0: #define resume(e) do{ QS=__LINE__; return e;\ case __LINE__:;} while(0) #define endrestartable } --------------------End Text added February 2008------------------- It is also possible to make part of the restartable functions SV visible to other functions without loss of information hiding, but with some loss of efficiency, by declaring a structure called name_SV for the function called name with one item for each visible value. Inside the body of the function the current values of the relevant values of variable are copied into the equivalent components of the external SV. Multithreading is also easy to achieve by creating a static or external data structure to hold data for all of the threads. An array would be ideal, as would be a file. Rules for Structure Inversion: 1. DON'T. 2. If you really must invert the structure, then draw a D-Chart. Mark and number each transfer or re-entry point. Add operations using QS. Determine large uninterrupted pieces of common code. Turn these into procedures. Draft code in one of the following forms: Structure Inversion with Respect to Output: case state of 1: produce data and save new state 2: produce data and save new state etc. end case Structure Inversion with Respect to Input - Version 1: case state of 1: if data is of type a then process type a and save state else if data is of type b then process type b and save state 2: if data is of type a then process type a and save state else if data is of type b then process type b and save state etc. end case Structure Inversion with Respect to Input - Version 2: case type of data of a: if state is 1 then ..... else if state is .... b: if state is 1 then ... else if state is 2 then.... etc. end case; Rule for Creating Table Driven Code: 1. Create table driven code only when the program has a few operations other than inputs. This will typically be a routine that checks input for correct syntax or a simple lexical analysis process. 2. Carry out the normal process for making the program into a restartable process: Put in QS and exit/re-entry points as normal. 3. Tabulate every possible path from each value of QS to another value value of QS - with a given input. Also list all the operations on each "transition". Code each transition. 4. Copy or create a general purpose procedure to carry out transitions and update QS. Rules for Parallel Inversion: 1. Use the normal design and implementation steps, as if there was a single process. 2. Select a data structure to hold the SV of the process and design a package of procedures to access that data. 3. A process may look at the SV of another process. It may not alter the state. The other process continues, unaware of what has happened. One way of visualizing this is that one process has a visible window through which other processes can see what has just happened without interfering with what they are looking at. Rules for Data Flow Diagrams: The Simple Case: When the Data Flow Diagram forms a Tree: 1.Choose any process as the main program. Do not choose a multi-threaded routine as the main program 2. Redraw the Data Flow Diagram with the main process at the top of a tree of processes. The upper ones call the lower ones. The Complicated Case When there exists at least one loop in the Data Flow Diagram, it is vital that later processes are delayed until all the data is ready for them. In general, a process may have to be held up because it needs data from one data flow, but is offered data from a different flow. The keys to implementing such Data Flow Diagrams are Queues, Files and Scheduling. 1. Break up the Data Flow Diagram into trees which are connected only by data stores and objects. 2. Convert each part (tree) into a restartable routines with I-O from queues and files. 3. Select a schedule that guarantees the correct behavior. 4. Design a special scheduler which calls the parts of the tree as sub-programs and uses queues to hold data until it is consumed.