. . SCHEDULING PRIMITIVES . . JOHN WALKER APRIL 1972 . . . (C) Copyright 1972 John Walker . . This software is in the public domain . AXR$ DEFUNCT$ FANG LIT$ 1 . . THE FOLLOWING PARAMETERS CONFIGURE THE SCHEDULER BY . SELECTING THOSE ROUTINES WHICH ARE NEEDED BY THE USER. . PMAYN EQU ; ONE IF 'PMAY' IS NEEDED 0 . IRN EQU ; ONE IF INSERT / REMOVE NEEDED 1 . PUSHN EQU ; ONE IF PUSH NEEDED 0 . BBN EQU ; ONE IF PUT / GET NEEDED 1 . FEN EQU ; ONE IF FORK / EXIT NEEDED 1 . ACTN EQU ; ONE IF ACTIVITY NAMING IN TSQ MODE 1 . SWL EQU ; ONE IF SWL'S WANTED IN TSQ MODE 1 . . THE PARAMETER 'DYNQ' SHOULD BE SET NONZERO IF THE SUBROUTINE . 'INITQ' IS NEEDED TO DYNAMICALLY INITIALISE AN INSERT / REMOVE . QUEUE. . DYNQ EQU ; ONE TO GENERATE INITQ 1 . . THE PARAMETER 'DYNPVQ' SHOULD BE SET NONZERO IF THE SUBROUTINE . 'INITPVQ' IS NEEDED TO DYNAMICALLY INITIALISE A P/V QUEUE. . DYNPVQ EQU ; ONE TO GENERATE INITPVQ 1 . . THE PARAMETER 'DYNBB' SHOULD BE SET NONZERO IF THE SUBROUTINE . 'INITBB' IS NEEDED TO DYNAMICALLY INITIALISE A BOUNDED BUFFER. . SETTING THIS PARAMETER NONZERO ALSO CAUSES THE GENERATION . OF 'INITQ' AND 'INITPVQ' REGARDLESS OF THE VALUE OF THE TAGS . 'DYNQ' AND 'DYNPVQ' ABOVE. . DYNBB EQU ; ONE TO GENERATE INITBB, INITQ, INITPVQ 1 . . ACTNAM EQU ACTN++(TSQ=0) SWLUSE EQU SWL++(TSQ=0) . . DATA FORMATS . . ON SWLUSE . . ACTIVITY SWITCHLIST ENTRY . PHNAME EQUF QL ACTIVITY NAME PHL EQU QL+1 ACTIVITY SWL LENGTH . OFF SWLUSE . . CLEAR TEST AND SET INSTRUCTION . P PROC *1 CTS* NAME 0 DO TSQ=0 , SZ,S1 P(1,1),P(1,2) DO TSQ , C$TS P(1,1),P(1,2) END /. . . P AND V FUNCTIONS . . . DIJKSTRA P FUNCTION . . . LA,U A0,<QUEUE> . LMJ X11,P . <RETURN> X5 DESTROYED . P* TS QHEAD,A0 LOCK THE QUEUE LX X5,QN,A0 LOAD QUEUE COUNT ANX,U X5,1 BACK UP THE COUNT SX X5,QN,A0 REPLACE THE COUNT IN THE QUEUE TN X5 DO WE NEED TO DEACTIVATE HIM ? J PDONE NO. SKIP DEACTIVATION ON TSQ=0 LX X5,QHL,A0 LOAD BACK LINK OF QUEUE SX X5,QHL,X4 PUT INTO BACK LINK OF ACTIVITY SX X4,QFL,X5 CHAIN ACTIVITY TO LAST ACTIVITY SA A0,QFL,X4 CHAIN HEAD TO NEW ACTIVITY SX X4,QHL,A0 MAKE THE NEW ACTIVITY LAST ON QUEUE CTS QHEAD,A0 RELEASE PROTECTION ON QUEUE HEAD SCHDACT* DACT$ . DEACTIVATE PROCESS OFF ON TSQ C$TSQ QHEAD,A0 WAIT FOR C$TSA OFF J 0,X11 RETURN AFTER ACTIVATION . PDONE CTS QHEAD,A0 UNLOCK THE QUEUE J 0,X11 RETURN . . . DIJKSTRA V FUNCTION . . LA,U A0,<QUEUE> . LMJ X11,V . <RETURN> X5 DESTROYED; X6 IFF NOT TSQ. . V* TS QHEAD,A0 LOCK THE QUEUE HEAD LX X5,QN,A0 LOAD QUEUE COUNT AX,U X5,1 COUNT IT UP SX X5,QN,A0 UPDATE QUEUE COUNT ANX,U X5,1 BACK UP THE COUNT TN X5 DID WE WAKE UP AN ACTIVITY ? J VDONE NO. SKIP THIS STUFF ON TSQ=0 LX X5,QFL,A0 GET FIRST WAITING PROCESS LX X6,QFL,X5 GET NEXT WAITING PROCESS SX X6,QFL,A0 CHAIN NEXT TO HEAD SA A0,QHL,X6 POINT NEW FIRST ONE TO HEAD SA A0,X6 SAVE A0 LA A0,PHNAME,X5 LOAD PROCESS HEADER NAME ACT$ . ACTIVATE THE PROCESS LA A0,X6 RESTORE NAME OFF ON TSQ C$TSA QHEAD,A0 ACTIVATE THE FIRST ONE. J 0,X11 RETURN. OFF VDONE CTS QHEAD,A0 UNLOCK THE QUEUE J 0,X11 RETURN /. . . CONDITIONAL P FUNCTION . . LA,U A0,<QUEUE> . LMJ X11,PMAY . <FAILED RETURN> (YOU DON'T GO TO SLEEP) . <NORMAL RETURN> . ON PMAYN PMAY$* TS QHEAD,A0 LOCK THE QUEUE LX X5,QN,A0 LOAD THE COUNT ANX,U X5,1 COUNT IT DOWN TP X5 IS IT POSITIVE OR ZERO ? J PMAYF NO. IT FAILED SX X5,QN,A0 STORE OUT DECREMENTED COUNT CTS QHEAD,A0 UNLOCK THE QUEUE J 1,X11 RETURN TO NORMAL RETURN . PMAYF CTS QHEAD,A0 UNLOCK THE QUEUE J 0,X11 TAKE FAILED RETURN OFF PMAYN /. . . QUEUE MANIPULATION PRIMITIVES . . QUEUE INSERT . . LA,U A0,<QUEUE> . LA,U A1,<DATA> . LMJ X11,INSERT . <RETURN> X5 DESTROYED . ON IRN++BBN INSERT* TS QHEAD,A0 LOCK THE QUEUE LX X5,QHL,A0 X5 = LAST BUFFER ON QUEUE SX X5,QHL,A1 POINT NEW ONE TO LAST SA A1,QFL,X5 SET FORWARD LINK OF LAST ONE SA A0,QFL,A1 POINT NEW ONE TO HEAD SA A1,QHL,A0 POINT HEAD TO NEW ONE CTS QHEAD,A0 UNLOCK THE QUEUE J 0,X11 RETURN . . . QUEUE REMOVE . . LA,U A0,<QUEUE> . LMJ X11,REMOVE . <RETURN> A1 = DATA . X5 DESTROYED . REMOVE* TS QHEAD,A0 LOCK THE QUEUE LA A1,QFL,A0 LOAD FIRST ALLOCATED PACKET LX X5,QFL,A1 GET NEXT BUFFER SX X5,QFL,A0 POINT HEAD TO IT SA A0,QHL,X5 POINT IT BACK TO HEAD CTS QHEAD,A0 UNLOCK THE HEAD J 0,X11 RETURN OFF IRN++BBN . . . QUEUE PUSH (INSERT AT HEAD) . . LA,U A0,<QUEUE> . LA,U A1,<DATA> . LMJ X11,PUSH . <RETURN> X5 DESTROYED . ON PUSHN PUSH* TS QHEAD,A0 LOCK QUEUE LINKS LX X5,QFL,A0 LOAD LINK TO FIRST DATA ITEM SX X5,QFL,A1 ATTACH FORWARD CHAIN TO NEW ITEM SA A1,QHL,X5 POINT BACKPOINTER TO NEW ITEM SA A0,QHL,A1 SET BACKPOINTER OF NEW ITEM TO HEAD SA A1,QFL,A0 MAKE NEW ITEM FIRST ON QUEUE CTS QHEAD,A0 UNLOCK QUEUE LINKS J 0,X11 RETURN TO CALLER OFF PUSHN /. . . BOUNDED BUFFER OPERATIONS . . PUT ONTO BOUNDED BUFFER . . LA,U A0,<BOUNDED BUFFER> . LA,U A1,<DATA> . LMJ A3,PUT . <RETURN> X11, X5 DESTROYED . ON BBN PUT* AA,U A0,QL*2 POINT TO 'QUEUE NOT FULL' LXI X11,A3 SAVE RETURN. P . P 'QUEUE NOT FULL' ANA,U A0,QL*2 POINT TO DATA QUEUE INSERT . INSERT DATUM ON QUEUE AA,U A0,QL POINT TO QUEUE NOT EMPTY V . V 'QUEUE NOT EMPTY' ANA,U A0,QL POINT BACK TO BEGINNING L A3,X11 RETURN IN UPPER(A3) SSL A3,18 PUT IT SOMEWHERE USEFUL. J 0,A3 RETURN . . BOUNDED BUFFER ITEM GET . . LA,U A0,<BOUNDED BUFFER> . LMJ A3,GET . <RETURN> A1 = <DATA> . X11, X5 DESTROYED . GET* AA,U A0,QL POINT TO QUEUE NOT EMPTY LXI X11,A3 SAVE RETURN. P . P 'QUEUE NOT EMPTY' ANA,U A0,QL BACK UP TO DATA QUEUE REMOVE . REMOVE THE ITEM FROM THE QUEUE AA,U A0,QL*2 POINT TO QUEUE NOT FULL V . V 'QUEUE NOT FULL' ANA,U A0,QL*2 BACK UP TO HEAD OF BOUNDED BUFFER L A3,X11 RETURN IS IN INCREMENT. SSL A3,18 MOVE IT DOWN. J 0,A3 RETURN OFF BBN /. . . CREATE / DESTROY ACTIVITY . . CREATE A NEW ACTIVITY . . LA,U A1,<ENTRY POINT> . LMJ X11,FORK . ON FEN FORK* FORK$ FSETUP,1 GET A NEW ACTIVITY J 0,X11 RETURN . FSETUP . ON SWLUSE BGET PHL ALLOCATE A PROCESS HEADER. LX,U X4,,A0 LOAD RUNNING SWITCHLIST POINTER OFF SWLUSE ON ACTNAM la a0,uactn load unique activity name cell aa,u a0,1 increment it sa a0,uactn update unique activity name NAME$ . ATTACH A NAME TO THE ACTIVITY ON SWLUSE SA A0,PHNAME,X4 SET ACTIVITY NAME IN SWL OFF SWLUSE OFF ACTNAM J 0,A1 ENTER NEW ACTIVITY . . TERMINATE ACTIVITY . . THE SWITCHLIST IS RELEASED BY THIS ROUTINE . EXIT*. ON SWLUSE BRELP X4 RELEASE THE SWITCH LIST. OFF SWLUSE EXIT$ . BYE ! . OFF FEN /. . . DYNAMIC QUEUE INITIALISATION . . . INITIALISE AN INSERT / REMOVE QUEUE . . LA,U A0,<QUEUE> . LMJ X11,INITQ . <RETURN> A1 DESTROYED . ON DYNQ++DYNBB INITQ* SA A0,QFL,A0 POINT FORWARD LINK TO QUEUE SA A0,QHL,A0 POINT BACK LINK TO QUEUE ON TSQ=0 SZ QHEAD,A0 CLEAR TEST AND SET ON QUEUE HEAD OFF TSQ=0 ON TSQ LA A1,(T$CELL 0) LOAD A TEST AND SET CELL SA A1,QHEAD,A0 INITIALISE THE QUEUE HEAD OFF TSQ J 0,X11 RETURN TO CALLER OFF DYNQ++DYNBB . . . INITIALISE A P/V QUEUE . . LA,U A1,<COUNT> . LA,U A0,<QUEUE> . LMJ X11,INITPVQ . <RETURN> . ON DYNPVQ++DYNBB INITPVQ* SA A1,QN,A0 SET COUNT IN QUEUE ON TSQ=0 SZ,H1 QHEAD,A0 CLEAR TEST AND SET SA A0,QFL,A0 LINK FORWARD LINK TO QUEUE SA A0,QHL,A0 LINK BACK LINK TO QUEUE OFF TSQ=0 ON TSQ LA A1,(T$CELL 0) LOAD A TEST AND SET CELL SA A1,QHEAD,A0 SET CELL IN QUEUE HEAD LA A1,QN,A0 RELOAD ORIGINAL COUNT OFF TSQ J 0,X11 RETURN TO CALLER OFF DYNPVQ++DYNBB . . . INITIALISE A BOUNDED BUFFER . . LA,U A1,<COUNT> COUNT FOR NOT FULL QUEUE . LA,U A0,<BUFFER> . LMJ X11,INITBB . <RETURN> H1(X11), A1 DESTROYED . ON DYNBB INITBB* LXI,U X11,,X11 SAVE ORIGINAL CALL ADDRESS AA,U A0,QL+QPL ADVANCE TO NOT FULL QUEUE INITPVQ . INITIALISE THE NOT FULL P/V QUEUE ANA,U A0,QPL BACK UP TO THE NOT EMPTY QUEUE LA,U A1 CLEAR COUNT FOR NOT EMPTY QUEUE INITPVQ . INITIALISE THE NOT EMPTY P/V QUEUE ANA,U A0,QL BACK UP TO DATA QUEUE AT BEGINNING LXM,U X11 CLEAR MODIFIER OF X11 NOP 0,,*X11 RESTORE ORIGINAL CALL ADDRESS J INITQ GO INITIALISE THE DATA QUEUE OFF DYNBB END