SHUFL.MAC;2=SHUFL.MAC;1
\
-2,2
	.IDENT	/04.MB/
-60
;	MARTIN BRUNECKY 30-MAR-81
;		MB017 -- CORRECT SWAPPING ALGORITM TO PREVENT CYCKLIC SWAPPING
;			 PROVIDE OPTIONAL SHF TIME-OUT ON EXIT (DISABLED REQ.)
;			 TO DISABLE PLAIN SHF RUNS WHEN NOTHING TO DO
;			 PROVIDE MEMMORY COMPACTION ON MCR REQUEST (ALL PARS)
;			 (INVOKED BY MCR COMMAND >RUN $SHF)
;			 REPLACE SHUFFLING SCHEMA BY THE MORE EFFECTIVE ONE.
;			 OPTIONALLY REORDER PAR. WAITING QUEUE AND MOVE
;			 THE SMALLER TASK TO THE FRONT OF PRI LIST.
;
;
%
-73,77,/; MB017/
; ASSEMBLY CONFIGURATION CONDITIONALS
;
SHFOUT	=	1		;SHUFFLER TIME-OUT ON EXIT ((2**SHFOUT)/8 SEC)
SHFEFF	=	1		;EFFECTIVE SHUFFLING ONLY  (OVER 1/4 TASK SIZE)
SHFRWQ	=	1		;REORDER PAR.WAIT QUEUE IF CUR. TASK CAN'T FIT
   
;
; LOCAL DATA
;
MCRRQ:	.WORD	0		;MCR REQUESTED SHUFFLER RUN (0=NO)
TCBAD:	.BLKW	1		;SAVED ADDRESS OF WAITING TASK
PCBAD:	.BLKW	1		;ADDRESS OF DUMMY PCB (HOLE PCB)
SHPCB:	.BLKW	1		;SHUFFLED PAR. ORIGINAL PCB ADDR
TSKST:	.BLKW	1		;SAVED SHUFFLED TASK STATUS WORD
SWPAR:	.BLKW	1		;PARTITION WITH SWAPPING ACTIVE PCB ADDR.
WTTIC:	.BLKW	1		;TICKS TO WAIT FOR RESCHEDULING
-83,84,/; MB017/
CKPPRI:	.BLKB	1		;SWAPPED-OUT TASK'S PRIORITY
PPRI1:	.BLKB	1		;PARTITION PRIORITY (LINKED TASK)
PPRI5:	.BLKB	1		;PARTITION PRIORITY (CURRENT TASK)
	.EVEN
-102,103,/; MB017/
	MOV	$TKPS,R2	;PICK UP TICKS PER SECOND
	ASR	R2		;APPROXIMATE 1/2 SEC
	ASR	R2		;APPROXIMATE 1/4 SEC
	ASR	R2		;APPROXIMATE 1/8 SEC
	MOV	R2,WTTIC	;SAVE TICK COUNT FOR 1/8 SEC
	MOV	$TKTCB,R0	;POINT TO OUR TCB			; CS017
	CMP	$SHFPT,R0	;SHUFLER REQUESTED BY >RUN $SHF ?
	BEQ	5$		;EQ = NO, REQUEST FROM EXEC
	INCB	MCRRQ		;SET-UP MCR REQUEST FLAG
5$:	MOV	T.PCB(R0),R0	;POINT TO SHUFFLER PCB			; CS017
-119,122,/; MB017/
;
; SHUFFLER EXIT AND RESCHEDULE HANDLING
;
; IF SHF DEAD-TIME SELECTED, WE FIRST CLEAR EXEC SHF... POINTER AND
; STOP SELF FOR SPECIFIED TIME TO PREVENT IMMEDIATE REQUESTS.
; AFTER THIS TIME WE RESET THE POINTER, RELEASE POOL AND EXIT.
;

EXIT:	MOV	$TKTCB,R5	;POINT TO CURRENT TASK TCB
	MOV	#$CLKHD,R0	;POINT TO CLOCK QUEUE LISTHEAD
10$:	MOV	R0,R1		;SAVE POINTER TO PREVIOUS ENTRY
	MOV	(R0),R0		;POINT TO NEXT ENTRY IN LIST
	BEQ	20$		;IF EQ THERE IS NONE
	CMP	R0,CLKAD	;SHUFFLER CLOCK BLOCK?
	BNE	10$		;IF NE NO
	MOV	(R0),(R1)	;UNLINK CLOCK BLOCK
20$:	TST	RQSCH1		;RESCHEDULE REQUESTED?
	BNE	MKTIM		;IF NE YES
	.IIF NDF SHFOUT SHFOUT=0 ;IF UNDEFINED THEN ZERO
	.IF GT  SHFOUT		;SHUFFLER TIME-OUT ON EXIT REQUESTED
	TSTB	MCRRQ		;MCR REQUESTED SHF RUN ?
	BNE	40$		;NE = YES, EXIT IMMEDIATE
	CLR	$SHFPT		;DISABLE SHUFFLER REQUESTS
	.REPT	SHFOUT
	ASL	WTTIC		;SET WAIT COUNT TO 2**SHFOUT/8 SEC
	.ENDR
	CALL	MKTIM		;INSURE RESCHEDULING
	CALL	RETURN		;RETURN TO USER STATE
	.WORD	30$		;AT NEXT LINE
30$:	CALL	$SWSTK,INITL	;SWITCH BACK TO SYS.STACK
	MOV	$TKTCB,$SHFPT	;ENABLE SHUFFLER REQUESTS
	MOV	$TKTCB,R5	;POINT TO CURRENT TASK TCB
	.ENDC
40$:	MOV	CLKAD,R0	;POINT TO SHUFFLER CLOCK BLOCK
	CALL	$DECLK		;DEALLOCATE CLOCK BLOCK
	MOV	PCBAD,R0	;PICK UP PCB ADDRESS
	MOV	#P.LGTH,R1	;SET LENGTH OF BLOCK TO RELEASE
	CALL	$DEACB		;DEALLOCATE PCB
	CALLR	$DREXT		;EXIT

;
; THE SHUFFLER RESCHEDULES ITSELF BY PLACING A SPECIAL ENTRY IN THE
; CLOCK QUEUE WHICH CAUSES ITS STOP BIT TO BE CLEARED AFTER THE SPECI-
; FIED TIME INTERVAL, OR THE NEW SHF... REQUEST (SIG. EVENT ETC.).
;

MKTIM: 	MOV	#C.CSTP,R4	;CLEAR STOP BIT TYPE
	MOV	CLKAD,R0	;PICK UP ADDRESS OF CLOCK BLOCK
	CLR	R1		;CLEAR HIGH-ORDER TICKS
	MOV	WTTIC,R2	;SET-UP TICKS TO WAIT
	CALL	$CLINS		;INSERT ENTRY IN CLOCK QUEUE
	CALL	$STPCT		;STOP SELF FOR SPECIFIED TIME OR REQ.
	CALL	$DRDSE		;FORCE PROCESSOR REDISPATCHING
	RETURN
 
;									; CS017
; FIND A SYSTEM CONTROLLED PARTITION ELIGIBLE FOR SHUFFLING.
; IF NOT MCR REQUESTED SHF RUN, FIND ELIGIBLE TASK WAITING.
;									; CS017
-127,,/; MB017/
	CLR	SWPAR		;CLEAR PARTITION WITH SWAPPING ACTIVE
-134,,/; MB017/
	TSTB	MCRRQ		;MCR REQUESTED RUN?
	BNE	16$		;NE = YES, DON'T SEARCH ELIGIBLE TASK
-145,179,/; MB017/
; TASK IN IT'S WAIT QUEUE OR MCR-REQUESTED SHUFFLING.
;
; CHECKPOINT STOPPED TASKS, RESET LONG I/O BIT WHERE NO I/O IS PENDING
; IF CHECKPINTING IS ACTIVE, RESCHEDULE THIS PARTITION AND CHECK NEXT.
;
16$:	MOV	R0,TCBAD	;SAVE WAITING TASK TCB ADDR
	MOV	R5,R4		;COPY MAIN PARTITION PCB ADDR
18$:	MOV	P.SUB(R4),R4	;POINT TO NEXT SUBPARTITION
	BEQ	26$		;EQ = END OF SUBPAR SCAN
	BIT	#PS.COM!PS.NSF!PS.DRV,P.STAT(R4)  ;CAN IT MOVE ?
	BNE	18$		;NE = NO, CHECK NEXT ONE
	MOV	P.TCB(R4),R1	;POINT TO TASK TCB
	TSTB	T.IOC(R1)	;HAS IT ANY I/O PENDING ?
	BNE	22$		;NE = YES, DON'T CLEAR PS.LIO
	BIC	#PS.LIO,P.STAT(R4) ;CLEAR LONG I/O, IF SET-UP
22$:	BIT	#TS.CKR!TS.CKP!TS.OUT,T.STAT(R1) ;TASK ON THE WAY OUT ?
	BNE	24$		;NE = YES, MARK PAR. RESCHEDULE
	BIT	#T2.STP,T.ST2(R1) ;TASK STOPPED?
	BEQ	18$		;EQ = NO, TRY NEXT
	BIT	#T2.CHK!T2.CKD,T.ST2(R1) ;IS TASK CHECKPOINTABLE?
	BNE	18$		;NE = NO, TRY NEXT
	CALL	ICHKP		;INITIATE CHECKPOINT
24$:	MOV	R4,RQSCH	;MARK PARTITION RESCHEDULE
	BR	18$		;TRY NEXT PARTITION
26$:	TST	RQSCH		;PARTITION RESCHEDULE REQUIRED ?
	BNE	PASS1		;NE = YES
 
;
; CHECKPINTING COMPLETED, TRY TO FILL LOWER POSITIONED HOLES
; SHUFFLING THE BEST FITTING TASKS FROM ABOVE. THE FIRST TASK ABOVE HOLE
; SHUFFLE ONLY IF RELOCATION IS GREATER 1/4 OF IT'S SIZE.
;
 
	MOV	R5,R4		;COPY MAIN PARTITION PCB ADDR
	MOV	P.REL(R4),R0	;SET UP BASE OF INITIAL HOLE
30$:	CLR	R2		;CLEAR BEST FIT SIZE
	MOV	R4,R3		;SAVE PRIOR TO HOLE PCB ADDR
	MOV	P.SUB(R4),R4	;POINT TO NEXT SUBPARTITION
	BEQ	PASS2		;EQ = DONE, CHECK IF PASS2 REQ.
	MOV	P.REL(R4),R1	;GET PARTITION BASE
	SUB	R0,R1		;SUBTRACT BASE OF HOLE = H.SIZE
	BEQ	40$		;EQ = NO HOLE, SET-UP FOR NEXT
34$:	MOV	P.SUB(R4),R4	;POINT TO NEXT SUBPAR PCB
	BEQ	38$		;EQ = END, DONE
	CMP	P.BLKS(R4),R1	;PARTITION FIT TO OUR HOLE ?
	BGT	34$		;GT = NO, TRY NEXT
	BIT	#PS.COM!PS.NSF!PS.DRV!PS.LIO,P.STAT(R4) ;CAN IT MOVE ?
	BEQ	36$		;EQ = YES
	CMP	R5,SWPAR	;SWAPPING ACTIVE FOR MAIN PAR.?
	BEQ	38$		;EQ = STOP SHUFFLING AT THIS SUBPAR.
	BR	34$		;NE = TRY NEXT SUBPAR.
36$:	CMP	P.BLKS(R4),R2	;PAR.GREATER PREVIOUS BEST FIT?
	BLO	34$		;LO = NO, TRY NEXT
	MOV	P.BLKS(R4),R2	;SET-UP THE NEW BEST FIT
	MOV	R4,SHPCB	;SAVE SHUFFLABLE SUBPAR PCB
	BR	34$		;CHECK NEXT SUBPAR
38$:	MOV	SHPCB,R4	;RESET SHUFFLABLE SUBPAR PCB
	TST	R2		;ANY SHUFFLABLE SUBPAR FOUND ?
	BNE	50$		;NE = YES, SHUFFLE IT
	MOV	P.SUB(R3),R4	;POINT TO FIRST PAR. ABOVE HOLE
	BIT	#PS.COM!PS.NSF!PS.DRV!PS.LIO,P.STAT(R4) ;CAN IT MOVE ?
	BNE	40$		;NE = NO, SET-UP BASE OF NEW HOLE
	.IF DF 	SHFEFF		;EFFECTIVE SHUFFLING ONLY
	MOV	P.BLKS(R4),R2	;GET MOVABLE PARTITION SIZE
	ASR	R2		;DIVIDE TO 1/2
	ASR	R2		;DIVIDE TO 1/4
	CMP	R1,R2		;HOLE IS GREATER 1/4 OF PARTITION ?
	BHI	50$		;HI = YES, SHUFFLE IT
	.IFF
	BR	50$		;SHUFFLE IT
	.ENDC	;SHFEFF
40$:	MOV	P.REL(R4),R0	;SET-UP THE BASE OF NEW HOLE
	ADD	P.BLKS(R4),R0	;ABOVE CURRENT PARTITION
	BR	30$		;TRY TO FIND BEST FIT TASK
;
; PREPARE FOR SHUFFLING FOUND TASK TO DUMMY PARTITION (HOLE)
;
50$:	MOV	P.TCB(R4),R1	;POINT TO SHUFFLED TASK PCB
	ADD	#T.ST2,R1	;POINT TO IT'S STATUS WORD
	MOV	(R1),TSKST	;SAVE TASK'S STATUS
-187,,/; MB017/
	MOV	P.SUB(R3),R4	;POINT TO PAR. ABOVE HOLE
-198,244,/; MB017/
;
; END OF PCB SCAN
;
-278,278,/; MB017/
; SECTION BY INCREASING PRIORITY WEIGHTED BY THE SWAPPING PRIORITY
; (AND IF SAME THEN BY INCREASING PARTITION PRIORITY).
-285,288,/; MB017/
; IF THERE WILL MORE THAN ONE RESIDENT TASK WITH PRIORITY THE SAME 
; AS THE HIGHEST CHECKPOINTED ONE, THEIR SWAPPING PRIORITIES WILL BE
; FORCED TO +S$$WPR, AND PARTITION PRIORITY BYTE WILL BE DECREASED.
; THIS WILL SLOW DOWN THE SWAPPING PROCESS FOR SUCH GROUP BY NUMBER
; OF RESIDENT TASKS, REDUCING CHECKPOINTS AND SHUFFLING OVERHEAD.
;

TOPA1:	JMP	PASS1		;CARRY TO PASS1 TO CHECK NEXT PARTITION
PASS2:	TST	RQSCH		;ARE WE RESCHEDULING FOR THIS PARTITION?
	BNE	TOPA1		;IF NE YES - LOOK AT NEXT MAIN PCB	; CS017
	TST	MCRRQ		;MCR REQUESTED SHF RUN ?
	BNE	TOPA1		;NE = YES, DON'T SWAP
-293,293,/; MB017/
	BNE	35$		;NE = NEXT PCB EXISTS
.IIF NDF SHFRWQ BR  90$		;END OF LIST, NOTHING TO DO
.IIF  DF SHFRWQ JMP 112$	;END OF LIST, CHECK SMALLER TASKS
-303,,/; MB017/
	DECB	T.PRI(R5)	;AND REDUCE (TO CKP EARLIER THAN EXEC)
-309,309,/; MB017/
	BHI	41$		;IF HI NO, TAKE NEXT IN LIST 
	BLO	42$		;IF LO YES, INSERT IT
	MOV	T.PCB(R1),R4	;POINT TO OUR TASK'S PAR
	MOVB	P.PRI(R4),PPRI1 ;PICK UP IT'S PRIORITY
	MOV	T.PCB(R5),R4	;POINT TO CURRENT IN LIST PAR
	MOVB	P.PRI(R4),PPRI5 ;PICK UP IT'S PRIORITY
	MOV	TCBAD,R4	;RESET ADDRESS OF WAITING TASK'S TCB
	CMPB	PPRI5,PPRI1	;OUR TASK BELONG HERE?
	BHIS	41$		;IF HIS NO, TAKE NEXT IN LIST
-325,,/; MB017/
	MOVB	T.PRI(R1),CKPPRI ;SAVE CHECKPOINTED TASK'S PRIORITY
-338,,/; MB017/
	MOV	T.PCB(R1),R3	;POINT TO TASK'S PCB
	MOVB	T.PRI(R1),P.PRI(R3) ;RESET PARTITION PRIORITY
	MOV	P.MAIN(R3),SWPAR    ;MARK PAR. WITH SWAPPING ACTIVE
-344,,/; MB017/
	CMPB	CKPPRI,T.PRI(R1)    ;IS IT HIGHER SWAPPED OUT TASK'S ONE?
	BHI	85$		    ;GT = YES, SO NOTHING TO DO
	TSTB	P.PRI(R5)	    ;PARTITION PRIORITY NONZERO?
	BEQ	85$		    ;EQ = NO, ZERO (VERY OLD ONE)
	DECB	P.PRI(R5)	    ;INCREASE PARTITION AGE
	MOVB	#S$$WPR,H.SPRI(R3)  ;PREVENT THIS TASK FROM BEEING CKP'D
85$:				    ;BY JUST SWAPPED OUT TASK
-352,355,/; MB017/
	INCB	T.PRI(R1)	;TO ORIGINAL ONE
	RETURN			;
;
	.IF DF	SHFRWQ	
;
; CURRENT WAITING TASK CAN'T FIT. CHECK, IF THERE IS ANY SMALLER TASK
; WAITING AND ELIGIBLE AT THE SAME PRIORITY -
; MOVE SUCH TASK TO FRONT OF QUEUE AND TRY ALLOCATE PARTITION AGAIN.
;
112$:	MOV	P.MAIN(R2),R5	;RESTORE MAIN PCB POINTER
	MOV	R5,R4		;COPY IT
	ADD	#P.WAIT,R4	;POINT TO PAR. WAIT QUEUE
113$:	MOV	R4,R2		;SAVE THE POINTER
	MOV	(R4),R4		;POINT TO NEXT TASK WAITING
	BEQ	100$		;EQ = NO SUCH TASK
	CMP	R4,TCBAD	;OUR WAITING TASK FOUND?
	BNE	113$		;NE = NO
114$:	MOV	R4,R3		;SAVE PREVIOUS TCB POINTER
	MOV	(R4),R4		;POINT TO NEXT TASK WAITING
	BEQ	100$		;EQ = NO SUCH TASK
	CMPB	T.PRI(R4),T.PRI(R3) ;SAME PRIORITY ?
	BNE	100$		;NE = NO, END OF SCAN
	BIT	#T2.STP,T.ST2(R4) ;NEXT TASK STOPPED ?
	BEQ	115$		;EQ = NO, ELIGIBLE
	TST	T.ASTL(R4)	;STOPPED, BUT AST QUEUED ?
	BEQ	114$		;EQ = NO, TRY NEXT
115$:	MOV	T.PCB(R4),R1	;POINT TO NEXT TASK'S PCB
	MOV	TCBAD,R0	;POINT TO OUR  TASK'S TCB
	MOV	T.PCB(R0),R0	;POINT TO OUR  TASK'S PCB
	CMP	P.SIZE(R1),P.SIZE(R0) ;NEXT TASK IS SMALLER ?
	BHIS	114$		;HIS = NO, TRY NEXT
	MOV	(R4),(R3)	;UNLINK FOUND NEXT TASK
	MOV	(R2),(R4)	;AND INSERT IT
	MOV	R4,(R2)		;BEFORE OUR ONE
	CALLR	$NXTSK		;TRY TO ALLOCATE PAR. AGAIN
				;RETURN AT $SHUFL
	.ENDC

;
; SHUFFLE SELECTED TASK IN MEMORY (TO DUMMY PARTITION)
-373,373,/; MB017/
	MOV	P.TCB(R0),R1	;POINT TO SHUFFLED TASK'S TCB
	MOV	T.PCB(R1),R1	;GET ORIGINAL TASK'S PCB ADDR
	MOV	R1,SHPCB	;SAVE IT FOR LATER
-392,399,/; MB017/
	CMP	R0,R4		;DUMMY PARTITION PCB?
	BNE	130$		;IF NE NO
	MOV	P.SUB(R0),R4	;GET ADDRESS OF NEXT PCB
	MOV	R4,P.SUB(R3)	;REMOVE DUMMY PCB FROM LIST
	MOV	R0,R4		;POINT TO DUMMY PAR
	TST	R5		;RELOCATE TASK PARTITION?
	BNE	135$		;IF NE NO
	MOV	P.MAIN(R0),R4	;GET MAIN PARTITION PCB ADDR.
133$:	MOV	R4,R5		;SAVE ADDR OF PREVIOUS PCB
	MOV	P.SUB(R5),R4	;GET ADDR OF NEXT PCB
	CMP	SHPCB,R4	;SHUFFLED  PARTITION PCB?
	BNE	133$		;NE = NO, TRY NEXT
	MOV	P.SUB(R4),P.SUB(R5) ;UNLINK TASK PCB
	MOV	P.REL(R0),P.REL(R4) ;RELOCATE TASK IN MEM.
	MOV	P.SUB(R3),P.SUB(R4) ;MERGE TASK PCB TO
	MOV	R4,P.SUB(R3)	    ;PROPER SLOT IN LIST
135$:	MOV	P.TCB(R4),R1	;GET ADDRESS OF TASK TCB
-407,412,/; MB017/
	MOV	T.PCB-T.ST2(R1),R4 ;POINT TO TASK'S ORIGINAL PCB
	BIS	#PS.LIO,P.STAT(R4) ;SET LONG I/O BIT
138$:	CALL	RETURN		;RETURN TO USER STATE
	.WORD	$SHUFL		;
139$:	RETURN			;
140$:	MOV	P.MAIN(R4),R0	;GET ADDRESS OF MAIN PARTITION PCB
	TST	MCRRQ		;MCR REQUESTED SHF RUN?
	BNE	138$		;NE = YES
	CALLR	$NXTSK		;TRY TO ALLOCATE PARTITION AGAIN
;
;
/