TITLE	CLKCSS - SCHEDULING ALOGRITHM FOR NON-SWAPPING SYSTEMS
SUBTTL	T. HASTINGS/TH TS3.17 6 SEP 67 V001
XP	VOLKCS,001
		;PUT VERSION NUMBER IN GLOB LISTING AND LOADER STORAGE MAP


;SCHEDULING ALGORITHM IS:
;CALLED EVERY 60TH OF A SECOND WHEN CURRENT JOB IS USER MODE
;CALLED WHEN CURRENT JOB IS IN EXEC MODE AND:
;	1. JUST STARTED TO WAIT FOR IO
;	2. JUST STARTED TO WAIT FOR A BUSY SHARABLE DEVICE
;	3. RETURNING TO USER AFTER TYPING CONTROL C
;	4. RETURNING TO USER AFTER CLOCK TRIED TO INTERRUPT
;		CURRENT JOB WHILE IT WAS IN EXEC MODE
;	5. AND ERROR OCCURRED IN CURRENT JOB

;CALL:	SETOM TIMEF		;IF CLOCK HAS GONE OFF SINCE LAST CALL
;	PUSHJ PDP,NXTJOB
;	RETURN WITH NEXT JOB TO RUN IN AC ITEM

;INTIALIZE SCHEDULER(CALLED FROM IOINI1 BEFORE ALL OTHER
;	DEVICES ARE INITIALIZED)

INTERNAL NXTINI

NXTINI:	MOVSI TAC,-NQUEUE	;NO. OF QUEUES
	SETZM AVALTB(TAC)	;CLEAR SHARABLE DEVICE AVAILABLE FLAGS
	SETOM REQTAB(TAC)	;SET SHARABLE DEVICE REQUEST COUNT TO -1
				;IE NO JOB WAITING OR USING DEVICE
	AOBJN TAC,.-2		;OTHER DEVICE INITIALIZATION
	POPJ PDP,		;MAY CHOOSE TO SET REQUEST TO MORE
				;NEG. VALUE IF MORE THEN ON JOB CAN
				;USE DEVICE AT ONCE
INTERNAL NXTJOB
INTERNAL FTTRPSET,FTDISK
EXTERNAL JOB,TIMEF,JBTSTS,JOBMAX,JOBN,PJBSTS,CPOPJ,CHKSHF
ENTRY XCKCSS

T=TAC		;TEMPORARY
Q=TAC1		;QUEUE NO.
Q1=DEVDAT	;QUEUE NO. SHIFTED TO MATCHING POS. OF JBTSTS WORD
C=DAT		;COUNT OF JOB LEFT TO SCAN

XCKCSS:
NXTJOB:	PUSHJ PDP,CHKSHF	;SHUFFLE CORE IF NEEDED
	SETZM T
	SKIPN ITEM,JOB		;CURRENT JOB NO.. IS IT NULL JOB?
	JRST NXT0		;YES, DO NOT DECREMENT QUANTUM RUN TIME
	SKIPE TIMEF		;NO, IS THIS A CLOCK INTERRUPT CALL?
	SOSA T,JBTSTS(ITEM)	;YES, DECREMENT QUANTUM RUN TIME
				;IN JOB STATUS WORD
	SKIPA T,JBTSTS(ITEM)	;NO, JUST PICKUP STATUS WORD
	TRNE T,-1		;REDUCE TIME TO ZERO YET?
	JRST NXT1		;NO
	HRR T,RNQUNT		;YES, RESET FOR RUN QUEUE QUANTUM
NXT0:	SETOM RNAVAL		;FLAG TO SCAN RUN QUEUE FOR DIFFERENT JOB
NXT1:	HRRM T,JBTSTS(ITEM)	;STORE MODIFIED QUANTUM RUN TIME
	MOVEI Q,MAXQ		;HIGHEST PRIORITY QUEUE SCANNED FIRST
NXT2:	SKIPN AVALTB(Q)		;SHOULD THIS QUEUE BE SCANNED FOR A RUNABLE JOB?
NXT3:	SOJGE Q,NXT2		;NO, LOOK AT NEXT LOWEST PRIORITY QUEUE
	JUMPL Q,NXT7		;YES, LOOKED AT QUEUES NQUEUE-1..,0?
	MOVE Q1,Q		;MOVE QUEUE INDEX TO PROPER POS.
	ROT Q1,^D17-JWPOS	;TO MATCH JOB STATUS WORD
	MOVEI C,JOBMAX		;NO, SACN ALL JOBS(EXECEPT NULL JOB)
	AOSA ITEM,JOBP(Q)	;SCAN ALL OTHER JOBS IN THIS QUEUE FIRST

NXT4:	SETOM RNAVAL		;FLAG RUN QUEUE BEING SCANNED

NXT5:	CAIL ITEM,JOBN		;GREATER THEN HIGHEST JOB NO.?
	MOVEI ITEM,1		;YES, RESET TO 1(SKIP NULL JOB)
	HLRZ T,JBTSTS(ITEM)	;IS JOB RUNABLE?
	TRZ T,RUNMSK+CMWB	;MASK OUT JOB STATUS BITS WHICH DO NOT MATTER
	CAIN T,RUNABLE(Q1)	;ADD IN QUEUE NO. IN PROPER POSITION
	JRST NXT8		;YES, IT IS RUNABLE AND IS IN THIS QUEUE
NXT6:	SOJLE C,NXT3		;NO IT IS NOT, SCANNED ALL JOBS YET?
	AOJA ITEM,NXT5		;NO, LOOK AT NEXT JOB
;HERE IF NO JOBS FOUND TO RUN(Q=-1)

NXT7:	MOVEI C,JOBN		;SCAN ALL JOBS INCLUDING POSSIBLY NULL JOB
	MOVE ITEM,JOB		;STARTING WITH LAST JOB TO RUN
	SKIPN Q1,RNAVAL		;HAS RUN QUEUE(Q,Q1=7) BEEN SCANNED?
	AOJA Q,NXT4		;NO, FLAG THAT IS HAS AND SCAN RUN QUEUE(Q,Q1=2)
	SETZB ITEM,RNAVAL	;YES, CLEAR FLAG, SET NULL JOB TO RUN
	POPJ PDP,		;RETURN

NXT8:
IFN FTTRPSET,<
	EXTERNAL STOPTS
	MOVE T,STOPTS			;HAS A TRPSET UUO BEEN DONE FOR JOB1
					;WITH NON ZERO AC?
	CAIE ITEM,1			;IS THIS JOB 1?
	JUMPN T,NXT6			;KEEP LOOKING IF NOT JOB1 AND
					;STOPTS FLAG SET
>

	CAIE Q,TSQ		;IS THIS TTY WAIT SATISFIED Q?
	CAIN Q,WSQ		;IS THIS IO WAIT SATISFIED QUEUE?
	SOSGE AVALTB(Q)		;YES, DECREMENT COUNT OF JOBS WITH SATISFIED IO
	SETZM AVALTB(Q)		;NO, CLEAR AVAILABLE FLAG FOR THIS QUEUE
	MOVEM ITEM,JOBP(Q)	;SAVE JOB NUMBER FOR THIS QUEUE FOR NEXT TIME
	JUMPE Q,CPOPJ		;IS THIS RUN QUEUE?
	MOVEI T,RNQ		;NO, SET STATE CODE TO RUN
	DPB T,PJBSTS		;CLEAR WAIT CODE(SO HE WILL BE IN RUN QUEUE)
	MOVE T,QUANTS(Q)	;SET QUANTUM RUNNING TIME FOR QUEUE
	HRRM T,JBTSTS(ITEM)	;WHICH JOB HAS JUST LEFT
	POPJ    PDP,		;RETURN

INTERNAL FTCHECK,FTMONP

IFN FTCHECK+FTMONP,<
EXTERNAL JOBP,AVALTB,REQTAB,QUANTS

DEFINE X(A,B)
<	EXTERNAL A'AVAL,A'REQ,A'QUNT
	INTERNAL A'Q
	A'Q=ZZ
	ZZ=ZZ+1
>
	ZZ=0
	QUEUES
	LOC=ZZ
>

IFE FTCHECK+FTMONP,<
;APPROPRIATE ENTRY IS NON-ZERO WHEN SCHEDULER SHOULD LOOK
;AT THAT QUEUE TO FIND A JOB TO RUN
;WSAVAL CONTAINS THE NO. OF JOBS WITH IO WAIT SATISFIED(0=NONE)
;SIMILARLY FOR TSAVAL


DEFINE X(A,B)
<	INTERNAL A'AVAL,A'Q
	A'Q=.-AVALTB
		A'AVAL: 0
>

INTERNAL AVALTB

AVALTB: QUEUES		;GENERATE THE AVAL FLAGS
LOC=.-AVALTB
>

NQUEUE=LOC		;NO. OF QUEUES COUNTING RUN QUEUE
XP MAXQ,NQUEUE-1	;MAX STATE CODE WHICH HAS A QUEUE

;DEFINE STATE CODES WHICH DO NOT HAVE QUEUES ASSOCIATED WITH THEM


DEFINE X(A)
<	INTERNAL A'Q
	A'Q=LOC
	LOC=LOC+1
>

	CODES
IFE FTCHECK+FTMONP,<
;LAST JOB SCHEDULED FOR EACH QUEUE

JOBP:   REPEAT NQUEUE,<		EXP 1>

;SHARABLE DEVICE REQUEST TABLE(GENERAL;IZED FOR OTHER QUEUES TOO)
;CONTAINS THE NUMBER OF JOBS WAITING TO USE SHARABLE DEVICE
;WSREG AND RNREG ARE UNUSED

DEFINE X(A,B)
<	A'REQ:	0
	INTERNAL A'REQ
>

INTERNAL REQTAB

REQTAB: QUEUES

;QUANTUM RUNNING TIME FOR EACH QUEUE IN JIFFIES(CLOCK TICKS)

DEFINE X(A,B)
<	A'QUNT: EXP 2
	INTERNAL A'QUNT
>

QUANTS:	QUEUES
>
	END,