schedb

This document provides a detailed description, in assembly language, of the scheduling and swapping algorithms used in a PDP-10 operating system with a Burroughs disk. Dated 1969, it outlines the core logic for managing jobs, memory allocation, and disk I/O.

Key components and functions described include:

1. Scheduler (NXTJOR, SCHED):

   • Manages job time slices, decrementing a job's "quantum" and requeueing it if time expires or I/O is pending.
   • Prioritizes jobs, calling the "shuffler," "swapper," and "scheduler" routines as needed.
   • Determines which job to run next by searching through various queues, often based on a "scan table."

2. Queue Management (QCSS / QINI, QXFER, QSCAN, OFIX):

   • Defines the data structures for job queues as ring-structured, forward and backward linked lists.
   • QINI initializes all jobs into a "null queue."
   • QXFER handles the transfer of a job from a "source-Q" to a "destination-Q," often involving resetting its quantum time. This is a table-driven process.
   • QSCAN scans queues to identify jobs based on various criteria (e.g., job in core, I/O status).

3. Swapper (SWAP R / SWAP, SWAP0, SWAP1, CHGSWP, ZERSWP, XPAND, SWPSER):

   • Manages moving jobs or data segments between core memory and disk.
   • SWAP is the main entry, checking for the status of the "core shuffler" and the swapper itself, then attempting to find jobs to swap in or out.
   • Routines like SWAP0 and SWAP1 manage the actual process of swapping out low/high segments and swapping in high segments, including disk space allocation and updating core images.
   • CHGSWP handles changes in disk swapping space allocation and adjusts system virtual memory tallies.
   • ZERSWP deallocates disk space, returning it to the free pool.
   • XPAND sets conditions for jobs requiring more core memory, marking them for expansion.
   • SWPSER is the swapping interrupt service routine, handling disk I/O requests for swapping operations and managing fragmented disk blocks.

4. Configuration and Data Structures:

   • The system's behavior is highly configurable, with conditional assembly for different disk types (PDP-10 vs. PDP-6).
   • Extensive use of table-driven logic is evident, with various tables (OBITS, AVALTB, REQTAB, TTAB, PTTAB, QUANTUM TABLES, OSCAN) defining job status codes, device availability flags, queue transfer rules, and quantum times for different job states.

5. Initialization (NXTINI, QINI, SWPINI):

   • Specific routines are dedicated to initializing the scheduler (NXTINI), all job queues (QINI), and the swapper's internal data structures and availability tables (SWPINI) upon system startup.

In essence, this document provides the architectural and operational blueprint, written in low-level assembly code, for how jobs are scheduled, queued, and managed in memory (swapped in/out) within a specific early computing environment.