Having disassembled part of JS QDOS many years ago to get an idea of exactly how it worked, I jotted down an algorithm of how the scheduler performed its task. Thought some readers might find the following interesting.
The scheduler is the part of the operating system which controls the executing and scheduling of all the jobs in the machine. It is normally called every time a frame interrupt occurs (approx every 1/50th second), or indirectly after other certain operating system routines have been used (Traps). Apart from switching the processor from the current job to the next deserving processor time (based on priority) it also deals with waiting input/output. Since this function makes the system more efficient I'll explain it in more detail.
To save a job wasting time (ie, using a whole processor time slice of 20mS) for things like; waiting for the user to press a key (input), or to send a byte to SER (eg, output to printer) QDOS allows a job to be suspended and its waiting input/output attempted by the scheduler. To do this, every time a job requests an input/output operation to be done (through a previously opened channel), the job is required to specify a 'timeout' for the operation. Each time the scheduler attempts the jobs input/output it decrements this timeout according to the number of frame interrupts that (may) have occured since the last attempt. If it never gets done in the time allocated it returns its request as incomplete, otherwise the operation is done and (in both cases) the job is released from suspension so that it can continue. As a frame interrupt normally occurs every 20mS this timeout figure thus specifies how long in 1/50ths of a second it has to do the operation. Instead of giving a finite timeout most jobs usually give -1, which means wait until the operation is done else wait forever.
For example the SuperBASIC function INKEY$ requires a timeout to be specified, this is used direclty in the call to get a key from a channel opened to the device 'con'. Eg, a$=INKEY$(50) means wait for upto 1 second for a key to be pressed else return, (incomplete in this case returns an empty string). Thus using -1 means wait forever if no key pressed. Since infinite timeouts in jobs can cause a job to be suspended forever if they never can do the input or output operation, SuperBASIC has a special key to force an abort for any of its input/output operations ie, the 'break' key CTRL SPACE.
If we could likewise specify timeouts on PRINTing in SuperBASIC (like other jobs can) we could write programs (or compile them) such that it would be possible to detect when we have been unable to print to our buried job windows. eg, "here's the answer you wanted, but if I find I'm buried (ie, times out incomplete) I'll tell you later when I'm not buried, but in the meantime I'll get on with something else rather than wait idly by in suspension".
The scheduler also performs some other housekeeping tasks on the computer ie, flash the cursor, service any SER transmit, and any other tasks that may be linked in to be done when the scheduler is run. For example, a task could be set up to release the buffer memory used after a previously closed output channel's data has all been sent to the device, or any other (User mode) task a job might like to link in to be done periodically rather than depend on the job being in a position to do it.
The scheduler decides which job is next in line for the processor by looking at information stored in the header added to each job currently in the machine (including SuperBASIC). The jobs registers (ie, the CPU state for that job) are stored in this header whilst the job is waiting for its slice of processor time.
Along with other parameters in the job header, which are used by the job control routines of QDOS, are the four which the scheduler inspects and updates in turn for each job to find out which job merits control of the processor next :
Name | Description |
---|---|
JB.PRIOR | This holds the jobs current running total of 'priority' points. Whosever is the highest after the job table has been scanned has the processor next. (The job who had the processor last automatically has this reset to 1 beforehand). |
JB.PRINC | This is the actual job priority. This gets set as required either when a job is started (defaults to 32 if started by SuperBASIC) or it can be changed whilst the job is running (ie, MT.PRIOR or Toolkit 2 command SPJOB). A priority of 0 means the job is inactive (not the same as suspended, whereby the priority setting is retained). It is used as the priority increment; each time the scheduler scans for the next job it adds this figure to JB.PRIOR (JB.PRIOR never exceeds 255). |
JB.STAT | The status of this particular job. It can have the
following values; 0 not suspended >0 delay time to reactivation -1 suspended -2 waiting for another job to complete A job can be suspended for a finite time if required (ie, made idle). The timeout until reactivation, which is stored here (as does the timeout for waiting input/output), gets decremented for each frame interrupt until it reaches 0. Only jobs with a JB.STAT of 0 are considered eligible for 'next' job. Jobs at -1 are either waiting forever for their input/output or have been suspended indefinitely (ie, MT.SUSJB), -2 means this job has been suspended until another has finished (ie, like EXEC_W from SuperBASIC). |
JB.HOLD | Location to be cleared when this job is released from suspension (equals 0 if not required). This can be used, if required, to let another job know when this job has timed out of suspension. |
Another parameter taken into account when the scheduler is run is the system variable SV.POLLM, this figure is incremented every time a frame interrupt is serviced. The scheduler uses the value of this variable to decrement any positive value found in a job's JB.STAT (SV.POLLM is reset to zero once used). Because the scheduler is normally run every time a frame interrupt occurs SV.POLLM usually has the value 1, but occasions may arise when a frame interrupt doesn't automatically call the scheduler, this is if the frame interrupt occured whilst the processor was in Supervisor mode (ie, an atomic action). Thus when the scheduler may finally get called SV.POLLM ensures that any job in (finite) suspension gets timed out correctly, the 'missed' frame interrupts having been stored in SV.POLLM. Of course it doesn't stop frame interrupts getting missed when interrupts are turned off ie, for FLP access, network driver etc!
The process the scheduler goes through whenever it is called can now be illustrated by the following algorithm;
Entry; Frame interrupt in User mode, or After certain non-atomic TRAP calls If current job's JB.PRIOR <> 0 THEN JB.PRIOR = 1 Save current jobs registers in its header D3 = SV.POLLM (* re-entry point, see below) SV.POLLM = 0 Increment SV.RAND (psuedo random number) Do scheduler linked list; (1) flash cursor (2) do any SER transmit (3) do any waiting input/output (ie, scan the channel table) (4) do any other externally linked in tasks Set D1 = 0 (highest JB.PRIOR found so far) Set D0 = -2 (to indicate if no 'next' job found)
Now a search for the next possible job is done by interrogating each job's header. The job table is searched from the entry of the (last) current job +1 to the end of the table, and then from the start of the table back upto the entry for the last job.
REPeat for each valid job in table IF JB.PRINC = 0 (inactive) THEN ignore, look at next job. IF JB.STAT < 0 (suspended) THEN ignore, look at next job. IF JB.STAT > 0 (waiting I/O or idle) JB.STAT = JB.STAT - D3 (ie, old SV.POLLM) IF JB.STAT > 0 THEN ignore, look at next job JB.STAT = 0 (in case overshot out-of-time) IF JB.HOLD <> 0 THEN clear location pointed to by JB.HOLD END IF IF JB.PRIOR = 0 (ie, when MT.PRIOR done) JB.PRIOR = 1 ELSE JB.PRIOR = JB.PRIOR + JB.PRINC IF JB.PRIOR > 255 THEN JB.PRIOR = 255 IF JB.PRIOR > D1 D1 = JB.PRIOR D0 = this job header location END IF END IF END REPeat for each valid job in table
After the job table has been scanned the next job is deemed to be the one pointed to by D0 which has the (first found) highest accumulated priority (D1). The jobs registers are then unloaded from job header and put back into the processor and control handed to the job until the next frame interrupt.
If no suitable job is found (D0=-2) then the scheduler is re entered (at *) until one is found. Although this might appear unlikely, ie, no job wants a slice of processor time, in fact it happens quite often. Most jobs spend their time waiting for the user! (ie, the scheduler is doing their pending input/output attempts whilst JB.STAT >0 and the job has a channel open with pending action). It reminds of the time when logging off a computer terminal used to generate the report; "You have been logged on 2 hours 47 minutes and you have used 11.31 seconds of processor time"!
The following simple SuperBASIC program illustrates how assigning different priorities to jobs affects how much processor time is apportioned to each, you may be surprised at the results. For example, it is better to assign two competing jobs priorities of 2 and 64, rather than 8 and 127 respectively, if you wish give one job more precedence over the other.
At the prompt for each of the five example jobs input a priority of between 0 and 127 (ENTER alone =0, ie, to represent an inactive or suspended job). Change the value used in the INKEY$ function (line 230) to speed up/slow down the update rate (0-25). Notice some low priority jobs hardly get a look-in on the processor until quite a time has elapsed, their low priority increment takes quite a time to build up their job merit. After an erratic start the percentage figures should settle down to reflect the long term proportion of processor time assigned to the job (use CTRL F5, as usual, to momentarily freeze the display if necessary).
The SuperBASIC program mimics quite closely what actually happens on a JS QDOS machine (standard QL or with SGC/GC). Some of the behaviour was so unexpected at first I didn't believe it until I ran some machine code tasks specially written to confirm it. For example if you only have two active jobs running with priorities a factor of two apart (eg, 64/32, 16/8 etc) then they end up both getting half the total processor time slices each. If one priority is changed by just 1 (ie, priorities 65 and 32) then the ratio becomes the expected 2:1 (approx). Once other jobs become active (at the same time), this behaviour (of 64/32 etc) changes to reflect the true priority spread.
The Minerva scheduler appears to have a slightly different action. Although it still exhibits the same effect as mentioned above it doesn't drop off when you have, say, five jobs with priorities; 1,2,4,8 and 16 (or similar). The SuperBASIC program shows that in this case (as with a real JS with SGC/GC), the lowest two jobs get the same amount of processor time (ie, approx 6%,6%,13%,25% and 50% respectively). With Minerva the time is apportioned as you would expect; 3%,6%,13%,26% and 52%.
If there is any interest I can detail the simple machine code jobs I used (tasks with definable priorities) in another article. I have yet to get around to delving into Minerva's background priorities and the SMSQ's scheduler with its definable IO_PRIORITY (retry loading for waiting input/output).
Note that any jobs waiting for input/ouput on a real machine are effectively suspended (ie, SuperBASIC waiting at cursor).
100 ch%=FOPEN('con') : PAPER#ch%;4 : INK#ch%;0 : BORDER#ch%;8,4 110 DIM jp%(4),ap%(4),jx%(4) 120 REPeat main 130 CLS#ch% : t%=0 : c%=-1 140 FOR n=0 TO 4 150 INPUT#ch%;'Job '&n&' priority :'!a$ 160 IF a$='' THEN jp%(n)=0 : ELSE jp%(n)=a$ 170 ap%(n)=1 : jx%(n)=0 180 END FOR n 190 CLS#ch% : PRINT#ch%;'Job Priority','Processor time'\\ 200 FOR n=0 TO 4 : PRINT#ch%;' ';n,jp%(n)\\ 210 PRINT#ch%\\'Press ESCape to STOP, any other key to re run' 220 REPeat show 230 a$=INKEY$(10) : IF CODE(a$)=27 THEN CLOSE#ch% : STOP 240 IF CODE(a$) THEN EXIT show : ELSE t%=t%+1 250 AT#ch%;0,34 : PRINT#ch%;t% : h%=0 : j%=-1 : p=1 260 FOR n=c%+1 TO 4, 0 TO c% 270 IF jp%(n) 280 ap%(n)=ap%(n)+jp%(n) : IF ap%(n)>255 THEN ap%(n)=255 290 IF ap%(n)>h% THEN h%=ap%(n) : j%=n 300 END IF 310 END FOR n 320 IF j%>-1 330 jx%(j%)=jx%(j%)+1 : c%=j% : ap%(c%)=1 340 p=0 : FOR n=0 TO 4 : p=p+jx%(n) 350 END IF 360 FOR n=0 TO 4 370 z=100*jx%(n)/p : z%=INT(z*2) : y%=20+n*20 380 AT#ch%;n*2+2,15 : PRINT#ch%;FDEC$(z,6,2);'%' 390 BLOCK#ch%;z%,10,140,y%,7 400 BLOCK#ch%;200-z%,10,140+z%,y%,0 410 END FOR n 420 END REPeat show 430 END REPeat mainBack to QDOS Internals