The Mathematics of RSX A computer system is a finite-state machine governed by a set of basic principles. Successful programmers understand and apply these rules. Just as a mathematician intuitively uses fundamental axioms to develop complex theorems, knowledgable programmers intuitively solve complex problems using the fundamental axioms of the system they are programming. Different computer systems have different, albeit similar, sets of axioms. The basic rules often define a computer system's "personality". RSX is based on a simple set of axioms. The behavior of RSX for any set of events is completely predictable. Once you understand the rules, you can program RSX applications which provide the exact response for all conditions. This article states the axioms of RSX in blunt, simple statements. Once understood, these axioms can be combined to create the most efficient and effective application environment. Unless stated otherwise, the material applies to all flavors of RSX: RSX-11S, RSX-11M, and RSX-11M-Plus. Note, Micro/RSX is considered the same as RSX-11M-Plus in this presentation. RSX Components --- ---------- An RSX system consists of four components: a PDP-11, the RSX operating system, user programming, and external events. The PDP-11 component is simply a collection of various resources: a CPU, memory, and devices. The RSX operating system creates an environment for user programming to schedule and use the PDP-11 resources. User programming is what you add to an RSX system to take appropriate action to external events. External events are the real world: the clock ticking, people typing at terminals, and signals from sensors on assembly lines. PDP-11's come in all shapes and sizes. PDP-11 hardware varies in processor features, execution speed, memory addressing, I/O interfaces, disk drives, and a hundred other options. The RSX operating system provides a virtual interface which hides the hardware differences. A program reading a disk file does not care if the file is located on a RM05 attached to a Massbus controller on an PDP-11/70 or a RX01 connected to the Q-bus of an LSI-11/03. The RSX operating system is not just the low-core kernel executive but also includes sub-components such as device drivers, special tasks (F11ACP, MCR, DCL, SHF, TKTN, PMT, etc.) and run-time services (FCS, RMS). User programming usually takes the form of tasks. A task is the fundamental, executable program unit in RSX. Tasks have many common attributes. The most important attribute is task priority. Axiom #1: One instruction at a time. ----- --- --- ----------- -- - ----- The PDP-11 is capable of executing only one instruction at a time. If you have two or more events to service, you must chose which event is serviced first. The remaining axioms define how RSX decides which instruction to execute next. RSX is a very passive operating system. The CPU is only taken away from the current executing task because of an external event occured. Except for some special cases discussed in Axiom #7, these events are not self-generated by RSX. Axiom #2: Three CPU states: interrupt, fork, and user. ----- --- ----- --- ------- ---------- ----- --- ----- RSX defines three PDP-11 CPU states: interrupt, fork, and user. This section looks at each state and how transistions occur from one state to another. As stated above, a system may only be in one CPU state at a time. Operating systems use different mechanisms to serialize access to operating system data structures. RSX uses a very simple mechanism - executive processing cannot be interrupted by more executive or user processing until the current processing is complete. Any new executive processing is placed in a first-in, first-out fork list. Hence the name "fork state" means RSX executive processing. Interrupt state is processing results from a device interrupt. Both user and fork processing can be interrupted. Typically, the interrupt code blocks out other interrupts at the same or lower hardware priority. If the interrupt can be processed without changes to executive structures, the code saves the current registers, performs the needed processing, restores the saved context, and dismisses the interrupt. If the access to executive structures is needed, an entry in the fork list must be made and processing will resume at some later time. A typical event is when a device driver needs to finish the current I/O request. When the current executive processing finishes, RSX checks the fork queue to see if any more processing is needed as a result of device interrupts. If so, the first entry is dequeued and processed. RSX does not return to user state until the fork list is empty. All transistions from user state are caused by interrupt traps: either device interrupts or software trap instructions (EMT, TRAP, BPT, IOT). When a user program issues an RSX directive, the EMT 377 instructions traps directly to fork level. No executive synchronization is needed because control is coming directly from user state. The hardware CPU modes (kernel, supervisor, and user) are not essential to the CPU states. While RSX systems with memory management support uses the kernel mode, unmapped systems have the same CPU states without such support. Axiom #3: Two task states: blocked and unblocked. ----- --- --- ---- ------- ------- --- ---------- RSX only has two task states: blocked and non-blocked. A task is blocked if it is not ready to run. The time it takes a task to move from blocked to unblock state determines how long it will take to respond to an event. The non-blocked state has two distinct forms: normal and AST. Asynchronous System Traps (AST) is an RSX mechanism to interrupt the normal task processing and execute some code specific to the triggering event. AST's do nothing to affect task priorities. For example, if the executive queues an QIO completion AST to a task at priorty 50, a higher priority task normal code still execute first. A queued AST to a stopped task will also restore its priority so the task can compete for memory and execute the AST. Axiom #4: All resources are allocated by priority. ----- --- --- --------- --- --------- -- --------- Each PDP-11 resource has an associated queue which is managed by the RSX executive. The CPU queue is the list of active tasks in the system. Memory is requested by the memory wait queue maintained for each partition. I/O requests are queued to lists maintained on a per I/O controller basis. Regardless of the type of queue, items in a queue are ordered by task priority. The lower the requesting task priority, the further down the queue an entry is inserted. Entries at the same priority are inserted in a first-in, first-out order. Removal from an RSX queue is always from the front. The second entry in a queue means nothing until the first entry is satisfied. One exception to this axiom is RSX-11M-Plus disk seek optimization. But even in this case, optimization only occurs for I/O issued from tasks that are of equal priority. RSX does not decide a task's priority - you do. But once you tell RSX a task has a priority higher than anything else and the task requests a resource, the executive believes you and does everything it can to satisfy the request. Even at the expense of locking the system. While task priorities may range from 250 down to 1, the value itself is not critical. What counts is the relationship of the priority to all other tasks in the system. A high priority task will deliver the same response time at priority 250 or 10 as long as all other tasks are set below priority 10. Setting a task's priority in relationship to other tasks in the system is not complicated. One simple procedure is to visualize all tasks, including the Digital supplied tasks, in a pile on the floor. Then ask the retorical question "If all these tasks want to run, which one would I give the CPU?". The answer is taken from the pile and becomes the highest priority task in your system. Repeat the process until the pile is empty. There will be many cases when there is a group of tasks for which you cannot decide which is more important. These tasks should be placed at the same priority. Always keep the response you desire to external events in mind when setting task priorities. One important event/response class is command execution speed. If people are use to 0.1 second response time to editor commands, a 1 second delay is extremely disruptive. On the other hand, people expect task builds to take a long time. As a rule, editors and other interactive programs should be placed above CPU intensive tasks. If you try this exercise for your system, the answers may surprise you. It is possible you have a critical task more important than the task loader. Axiom #5: A task must be in memory to execute. ----- --- - ---- ---- -- -- ------ -- -------- Before user programming can respond to an external event, it must first be loaded into memory. Ideally, the task is already memory resident. If not, an unforeseen delay can occur before the event is serviced. A rule of thumb is tasks should already be in memory if an event needs to be serviced within one second. The entire purpose of the task loading logic is to bring the highest priority task out of memory into memory. The first task in the memory wait queue for a partition must be loaded into memory before any other entries in the queue are considered, even if lower priority tasks would fit into some available space. Not everything in memory can be moved out to bring a task into memory. Obviously, higher priority tasks are not swapped out. However, low priority may not necessarily be checkpointed. A task must be properly conditioned to be checkpointed: no outstanding unbuffered I/O, not fixed, and not disabled from checkpointing. In the last case, any task can lock itself in memory by simply having checkpointing disabled either when task built (/-CP), installed (/CKP=NO), or at runtime (DSCP$S directive). RSX requires a task to execute in order to exit, even if the task has never been loaded into memory. If a task was run and cannot get into memory, aborting the task does not solve the problem. In fact, because the MCR/DCL ABORT command raises a task's priority to 247, the problem almost always get worse because the stuck task is now placed at the front of the memory wait queue. If a system is not responsive to external events because tasks are not in memory, the solution is almost always to add memory to the system (upgrading the CPU if necessary). Memory is effectively free when compared to programming costs to work around the problem. Axiom #6: The highest priority task which wants to execute - executes. ----- -- --- ------- -------- ---- ----- ----- -- ------- - --------- RSX uses a very simple task scheduler. The list of active tasks is scanned from top to bottom. The CPU is given to the first task found which is in memory and not waiting on some event. This task keeps the CPU until it goes into a wait state or some event takes a higher priority task out of a wait state. Several ramifications of the scheduling algorithm should be noted. Unless a task is at priority 250, its execution may be interrupted at any point in time and the system context switched to a higher priority task. If your task does something to cause a higher priority task to execute, your task will not execute the next instruction. If your task does something to cause a lower priority task to execute, the lower priority task will not execute until your task does something to release the CPU. RSX reschedules from one task to another only if a significant event occurs. Many events fall into this classification: QIO completion, mark time completion, sending a message, and task exit. While most of these events may have an associated event flag, simple setting an event flag is not a significant event. If you are using global event flags to control task syncronization, you must declare an significant event (WSIG$) after setting an event flag (SETF$) to cause any task rescheduling. The RSX scheduling algorithm can be illustrated by the following sample programs. Task A sends a message to Task B and then stops itself (STOP$). Task B has AST's enabled for incoming messages. When the AST triggers, Task B receives the message, performs some local processing, and unstops the sending task. If task B priority is lower than task A, the sequence works. However, if Task B is higher priority the Task A, problems will result. When Task A issues its send, this causes a context switch to Task B. Task B's unstop of Task A has no effect because Task A has not yet stopped. Only after Task B enters its wait state does Task A execute its STOP$ directive, thereby hanging it up forever. Axiom #7: Round-robin, disk swapping are not exceptions to #5, 6. ----- --- ------------ ---- -------- --- --- ---------- -- --- -- In a strict timesharing system, a program will be given some execution time eventually. RSX has two scheduling features which give a psuedo timehsharing effect. But as will be seen, the previous axioms are still in effect. Round-robin scheduling only effects CPU allocation. Therefore, the algorithm only operates on tasks in memory. Round-robin scheduling works only on tasks at the same priority. No priority change is made. Rather round-robin scheduling reorders the position of tasks of equal priority in the active task list. This prevents a compute-bound task from blocking other tasks at the same priority just because of first-in, first-out queue ordering. When a round-robin interval expires, the executive scans the active task list for the first running task inside the round-robin scheduing range. This task's position in the active task list changed to be behind all other tasks at the same priority. The loop repeats for lower priorities. If task(s) at a higher priorities use all available CPU time, nothing will be available for lower tasks for any type of scheduling. If three infinite loop tasks are started at priority 51, all three tasks will get an equal portion of the CPU. However, no time will be available for task at priority 50 and below. Disk swapping affects only memory allocation. There is no effect on CPU or device priorities. The normal task priority and a special swapping increment is used to compute the priority a task uses to compete for memory. When a task is loaded into memory, the swapping increment is set to some constant selected at system generation. For each swapping interval, the executive decrements the swapping increment for all tasks in memory until the negative constant value is reached. A task out of memory always uses its normal priority. However the memory priority for task in memory is the sum of the normal priority and the swapping increment. If the system generation swapping interval default (5) is used, a task with a priority of 50 is initially loaded with an effective memory priority of 55. As time passes, the priority will decrement to 45. If a task at priority 50 is waiting to come into memory, this algorithm will causes the task in memory to become eligible for checkpointing when its priority reaches 49. Axiom #7: Wait (but don't stop). ----- --- ---- ---- ----- ------ There are two distinct forms of a blocked task: wait and stopped. A task waiting on some event retains its priority. A task stopped on some event has an effective priority of zero. This directly affects competition for memory. A waiting task can only be checkpointed by a higher priority task. A stopped task may be checkpointed by any task. When the task becomes non-blocked, it first must compete for memory before serving the event. As discussed in Axiom #5, it may no longer be possible to checkpoint lower priority tasks at such time. A queued AST to a stopped task will restore its priority so the task can compete for memory and execute just the AST. The task returns to stopped state when the AST is dismissed unless the AST takes some action to unblock the task. If a deterministic response is desired for an event, wait for it. Stop state should only be used when you do not care how long the response to the event takes. Axiom #8: If RSX gets in your way, turn it off. ----- --- -- --- ---- -- ---- ---- ---- -- ---- RSX is not a great raw performance system for moving vast quantities of data from point to point. If a PDP-11 will not collect data at the speed you need, there is no reason to believe RSX will do any better. However, if a PDP-11 has the raw speed you need, it is fairly simple to turn RSX off and do what you need to do. There is nothing wrong with spending 5 seconds at priority 7 if you are solving the application you bought RSX to solve. Several techniques are available to "turn RSX off". The technique you use will depend upon how close you need to get to the device data and interrupt - a few instructions, microseconds, milliseconds, or seconds. It costs RSX 10 to 20 instructions to deliver an interrupt to a loadable device driver. If this time is critical to you, the driver must be built into the executive. Such drivers need only to save and restore just the registers they use directly before dismissing the interrupt. Fast response also requires all resources be allocated and available before the interrupt happens. One good trick is to use machine resources not used by RSX. For instances, a device driver could setup to use the alternate register set on a PDP-11/70 class machine to avoid the need to save and restore registers for each interrupt. Fast response may also require special handling at the task level. One common problem is quickly processing a large quanitity of data. If the overhead of the memory management is too great, task context switching can be disabled (byte $CXDBL set non-zero). Now the task can directly manipulate the memory management registers and directly address any part of physical memory. Another common technique is to disable the clock interrupt, thus preventing any unexpected time-based events. Conclusion ---------- A major strength of the RSX operating system is its deterministic quality. The axioms we discussed define the character of the RSX system. They provide the elements by which you can understand and interpret responses RSX gives to external events. Just as a mathematician uses basic, fundamental relationships in the manipulation of variables to prove or disprove theorems, a skilled programmer uses the axioms of RSX to manipulate the variables within the RSX system to produce the desired outcome. Perhaps more important, the skilled programmer uses these axioms to understand and correct undesired responses to external events.