clkcss

This document is an assembly language listing (MACRO, V36, 1969) for CLKCSS, a scheduling algorithm designed for non-swapping operating systems by Digital Equipment Corp. (DEC).

The scheduler's primary function is to determine and return the next job to run. It is invoked under specific conditions:

• Periodically (time-slicing): Every 1/60th of a second when the current job is in user mode.
• Event-driven: When the current job is in executive mode and:
  • Begins waiting for I/O or a busy sharable device.
  • Returns to user mode after a Control-C interrupt or a clock interrupt.
  • Encounters an error.

Key components and operations include:

• NXTINI (Initialization): Sets up core scheduler data structures, including a fixed number of job queues (NQUEUE), flags for available devices (AVALTB), and device request counts (REQTAB).

• NXTJOB (Main Scheduling Routine): This routine is responsible for the actual job selection. It performs operations such as:

  • Checking if core needs reordering (CHKSHF).
  • Managing job quantum run times (decrementing and resetting).
  • Scanning priority queues to find runnable jobs, starting with the highest priority.
  • Handling jobs that become runnable after satisfying I/O or device waits (e.g., TTY waits, sharable device waits) by clearing relevant flags and updating their state.
  • If no runnable job is found, it may return a "null job."

• Data Structures: The algorithm extensively uses tables like AVALTB (to track available jobs for various wait types), REQTAB (for sharable device requests), and QUANTS (to define the quantum running time for each job queue).

In essence, CLKCSS implements a combination of time-sliced and event-driven scheduling to efficiently manage job execution and resource allocation in a fixed-memory, non-swapping environment by actively monitoring job states and prioritizing tasks.