T H E U N I V E R S I TY O F M I C H I G A N Technical Report 19 Multiprogyramming in a Small-Systems Environment David L. Mills CUNCOMP-: esearch in Conversational Use of Computers E. H. Westervelt, Project Director OHA Project 07449 supported by: ADVANCED HESEARCH POJULCTS AGENCY DEPARTMENT Of DIEENS~ WASHINGTON, D.C. CUNaIACT NO. LA-49-083 OSA-3050 ARPA ORDER NO. 716 administered through: OFFICE OU RESEARCH ADMINISTRATIUN ANN ARBOR May 1969

ilultiprogramming in a Small-Systems Environment ABSTRACTI This report discusses multiprogramming systems architectures suitable for use with small machines of the PDP-8 class. Techniques for task and I/O device scheduling, storage and device allocation, butter and timer management and command language interpretation are discussed in detail. Illustrative implementation details are treely drawn from a tollow-on version of RAMP, a multiprogramming system now used in several appiicat ions involving process control, message switching and terminal contrcl.

This report was prepared using FORM AT, a computer program in MTS, the Michigan Terminal System. This program is described in: Berns, G. M., Description ot FPOiAT, a_TextProcessinq P roqram.L Comm. ACM, 12, 3 (March 1969), pp. 141-146. The text was entered to this program partly in punched-card rorm and partly directly from a typewriter terminal and was printed on an IBM 1403 printer equipped with a TN print train.

Multiprogramming in a Small-Systems Environment TABLE OF CONTEMLS 1. Introducti onIs.. * a..... a...l..........1 2. Operating Environment........................... *.2 3. basic Concejts and Definitions a ea *aaa.* vi.,,....5 4. LBasic System Architecture......... 4.. 8 4.1 Task-iime Operations..............11 4.2 Real-lime Operations................. 15 4.3 Input/Output Operations.......17 4.4 Storage Allocation...... le J a........21 4.5 Butfer Management..................... 23. Co mman d 0 perations..........................25 O. Special Operation s.................... * a. *.31 b.1 Device Allocation............................... 6.2 Input/Output Utilities........... 34 6.3 Interval Timer and Iiine-OO-Day Clock.............36 0.4 System Initialization arn Configuration.........39 7. Relerences.................. 41

Multiprogramming in a Small-Systems Environment 1 1. INi'ODUCTION This report describes further developments ot the RAMP system, a multiprogramming system designed for use in small machines ot the PDP-8 class tor operation in real-time processing envircnments. The old RIAMP systems, described in Reterences 1-4, have been used extensively in process control, message switching and terminal control environment s. The development of the new system, called nere simply "new RAMP," has resulted in a greatly enhanced tarougihput and a much more attractive inlterface to which speciai-purpose job-program subsystems can be attached. In addition, the new system incorForates a general storage allocation technique which provides both tor the dynamic loadiny of page-relocatable job-program subsystems and for the temporary storage ot ccntrcl in formatioln and I/O butifers. The concept of task, program, and real/task-time ~processing is given more precise definition in the new system; and the interface to device service routines is made mluch simpler and mole powerful. Fin ally, I/O message transmissions are accomplished in a record-oriented rather than a byte-oriented fashion, so that high-speed i/O devices can be efficiently connectea and soc that program loading can proceed directly to core memory lather than through an in termediate buf tfer. Althougih the primary implementation goal in the new RAMP systea was increascd throughput and flexibility as compared to the old system, the development of the new system has been different enlough trom the old that it is presented aere in_ totoi and familiarity wita the old system is not assumed requisite in tie exposition. Furthermore, althougn both the new and the old systems were coded for the PDP-8d tam ily of machines, the i nplementation techniques described here are obviously not restricted for use on this machine, but are appropriate for use on any "small" machine requiring 1/0 interrupts on a character-by-character Dasis. In fact, it will develop that many of the construction techniques are really special auaptations of those used in larger systems. 1. Iiltroduct ion

2 Multiprogramming in a Small-Systems Environment 2. OPERATING ENVIRONMENT Although the emphasis in this report is on general systems architecture and implementation techniques, the prinicipal interest is in multiprogramming systems for relatively small systems such as those intended for process control, message switching and terminal control applications. InI general the hardware architecture of the machine itself is assumed gyiven; and no special equipment is postulated especially for its use in a multiprogramming environment. The goal ot the presentation here is then a specification of attractive and useful system organizations which allow a general-purpose machine of very modest capabDlities to operate efficiently in a multiprogramming environment. ThrouyAout the subsequent discussion a hypothetical machine will be assumed whose characteristics are typical of a number or small general-purpose machines currently on the market. Obviously, some of the characteristics assumed are influenced uy certainly the most popular of these machines, ttfe PIP-6; and indeed, the particular implementation most often referenced invclves this machine. However, the impilementation techniques discussed are obviously not restricted to systems involving this particular machine. The hypotfetical machine considered here has a basic core memory Lank of perhaps 4K twelve- to sixteen-bit words. The supervisory system is expected to occupy perhaps a quarter to a nal of this. The various job-program subsystems, designed to perform the specialized processing uniquue to each application, occupy the remainder of the basic memory bank and perhaps additional add-on memory banks das well. Systems now in use involve PDP-8 systems of from one to tour 4K-word memory banks. The basic machine is assumed to include a rather fast central processing unit (CPU) of a limited instruction repetoire. As will be illustrated below, a slower CPU processing speed can be excnanged for a more sophisticated 1i/ structure, dependinJ or course on the application. An accumulator (AC) program counter (PC) and the various memory-bus registers are assumed inte gLal to the CPU of course; but extended arithmetic capability (high-speed multipliy/diviue) and index registers are not necessarily assumed availacle. An inLdi rect-addressing capability is requisite, as well as the logical operations of "and" and "one's co uiplemeInt" and the arithmetic operations of "adition" dnIa "'two's complement", or any equivalent set. A minl ial set of conditional-skip instructions, a branch instructioin ani subroutine-link instruction are necessary of course. These assumptiols defiIle a macnine which can be 2. Operating nvillronment

Multiprogramming in a Small-Systems Environment 3 argued is the smallest usetul machine larger than a Turing machine. Table 1 illustrates a comparison of a few currently-available machines in this class.. Word Mem Mem Inst Work Page Comments Size Size Cyc Cyc Regs Size Digital Equip. PDP- 8S 12 4096 8 42 1 128 serial PDP-8 12 4096 1.5 1.5 1 128 sup. PDP-8I PDP-7 18 4096 1.75 3.5 1 8192 sup. PDP-9 PDP-9 1 8 8 192 1.5 1.5 1 8 19;2 PDP-15 18 4096.8 - 2 4096 1 index In terdata Model 3 16 1024 2 - 16 32768 Data General NOVA 16 1024 6.5.5'4 256 2 index SEL 3 10 lb 4096 1.75 - Data Machines o20i 16 1024 1. 3. 6 3 2048 micropgm SDS Sigma 2 16 4096 - 8 256 Table 1. Ccmparison of Small Machines Trhe typical application or small multiprogramming systems envisioned here iIcludes a yood deal of I/O activity; aind indeed, the only significant activity performed by the system may be of this nature. Accordingly, tae specitication of the I/O intertace ot the hypothetical machine is crucial but ot necessity highly tailored to each lndividuai application. A typical specification will be assumea here; more detailed descriptions ot actual systems caIl be touna in the references at the end of this report. The hypothetical machine is assumed to contain tacilities for a program interrupt at a single priority level. ihat is, it the interrupt system ot the machine is enadled, thtten a simulated subroutine branch will be taken to a fixed location in memory when ani interrupt condition becomes pendiniig. A set ot instructions is assumed available to test each i/O ievice status and to initiate operations on tlese devices. The ul& ot all I/O data transters is z. Operating Environmeint

4 Multiprogramming in a Small-Systems Environment assumed to occur on a character-by-character basis, with an interrupt occuring for each character transferred. In some equipment data transfers can be performed on a cycle-steal basis; that is, directly to and from memory and an I/O device. A richer I/O hardware architecture, possibly including circuitry to resolve the priority and identifying code. oi the various interruption conditions, could very easily be added to the'hypothetical machine, but our main interest here is in the "barest-bones" architecture. 2. Operatin9 Environment

Multiprogramming in a Small-Systems Environment 5 3. BASIC CONCEPTS AND DEFINITIONS A _oqram is simply a ccllection of subroutines which operate upon a set ot data. Our interest here is in a system which includes several such Fpograms, each ot which may be executed in some sense independently of the others, but only one ot which is in actual control of the machine at any particular time. One of these programs, the supErvisorz is made responsible for the coordination of the various programs in the system and the operation of the scheduling alioritho which determines which of these will next be given control ot the machine. In general the supervisor is made responsible tor the coordination and the allocation of all ot the various system resources such as processing facilities, core storage and I/O devices. A tasi is d pLogram together with I/O device assignments and storage allocations which constitute a record of its physical state. In most RAMP systems the humDer and conliguration of the pFograms are usually fixed, although some of the systems can sustain dynamic loading operations. however, in all systems, the I/O device assignments and storage allocations can vary dynamically during operation, so that the existence oft a task can be considered synonymous with the existence of these assignments. As control is passed among the various tasks in the system, the state of each task is preserved in a special Dlock ot storage called the task ccntiol block (TCB) (see Figjure 1). Information stored in the TCB includes at least the instruction adaress at which the task was last suspended, annd resumably is the andress at which the task will be restarted when it is once again given control ot the macnine. ieyending upon the architecture of the particular system involved, other information stored in the TCB may include certain machine registers, I/O device assignments and storage allocation assignments. Obviously, the association ot a TCB to a program and the data it oFerates upon is highly arbitrary and can be nmaintained by pointers stored in the TCB itself. Thus there is considerable justirication, when describing multiprogramming systemS, to subordinate the usual concepts of program and data to that ot the task and its TCB, which reflects tile current state of the processor as seen by the prog ram. As each task is given contrcl by the supervisor, the machine state peculiar to that task is restored using the data stored in the TCB as of the last time that task was suspendco, and processing continues in the usual manner. 3. dasic COIncepts and Lefinltions

6 Multiprogramming in a Small-Systems Environment wnen processing of this task is temporarily suspended for some reason, possibly pending completion of a time-dependent operation, then the state of the machine is stored in the TCB and processing continues with the next task awaiting activation. Rescheduling of the suspended task is a function of the system architecture and depends upon whether the suspension was initiated upon request by the task or as the result of a hardware interrupt. I tLINK TO NEXT TCB I I LINK TO CALLING TCB J I INSTRUCTION ALLRESS I I I + DEVICE ~ABLE PCINTERS + i I + PARAMEIERS + Figure 1. Task Control Elock (TCB) Format The usual RAMP task-scheduling procedure consists of arranging the ICi3's of the system in a first-in-first-out ueaue and cnainin9 eacn TCB to the next in this queue. The task-scheduling process then considers each TCB in turn so tnat, if the task in control of the machine at a particular moment is consiaUEed tc have highest priority, then, when it is suspended, it can be considered to have lowest priority. [iany other retinements are possible to this scheme, some of waich are descriLed iIn the next secticn. i4ultiprogramming systems have traditionally been categorized as true multiprcgramming systems where processing oi a given tasK may continue indefinitely or until explicitly indicated by a call on the supervisor, perhaps as a rejuest for some I/O operation, and as timesharing systems, where processing of a given task continues until explicitly indicated or until a preset timeslice interval has expired. Once tne time-slice interval has expired, thle task is suspended and other tasks are )rocessed as required until the task in question is again re-activated by the supervisor, at which time it is again given its preset time slice. As can be seen here, apart 3. Jdsic COlceptS anId Definitions

Multiprogramming in a Small-Systems Environment 7 trom the details of task scheduling and the mechanism of timer interrupts, there is no fundamental difference between true multiprograimd ing systems and timesharing systems and no artificial distinctions will be drawn between them henceforth. In summary, in these introductory sections, the gross organization of the architecture of RAMP-like multiprogramming systems shouiA be apparent. In subsequent sections various implementation tecaniques will be discussed and examples presented. It suould be emphasized, however, that the exposition here does not attempt to describe detailed specifications or calling sequences of the various systems, but ratner to describe only the architectural cnaracteristics and primary functional components. 3. Basic Concepts and Definitions

8 Multiprogramming in a Small-Systems Environment 4. BASIC SYSTEM ARCHITECTURE In typical multiprogramming system operation an active task runs until an interrupt occurs or until a timedependent supervisor operation is requested by the task. In either case the supervisor is required to save the active registers and machine status in the TCB for that task and to schedule the next task to be activated. In the most general case involving timesharing ojerations there may be several'ueues maintained by the supervisor for the purpose of scheduling access to system resources such as I/O devices, bulk memory and Processing time; and the algorithm for tasksciieduling foilowing an interrupt may be exceedingly complex. in particular, the next task to be executed tollowiug an I/O interrupt may not be the task in which tne interrupt occured. In most large-scale multiprogramming and timesharing systems the programs themselves are constructed so as not to mooditry themselves during execution. In such systems ~everai tasks may share the same program and store the temporary information unique to each task in the TCB for tnat task. In a small system involving a machine with no index rcgister this type ot operation may be exceedingly awkward, since many of these machines typically store the return link tor a subroutine in the subroutine code itself. Accordingly, a modified view of the typical multiprogramming system is needed in which a particular task cannot be suspended until all of its state-dependent return links and index pointers have been saved in the TCB. in general, the philosophy inherent in the various RAMP systems has been to require the programming tunctions of each tasK to be responslDle for these operations and to indicate to the supervisor precisely those points at which a task-scheduiing operation can occur. As an implication of these architectural requirements, the 1/0 interrupt processor is required to explicitly schedule on the CPU ue ue those tasks wh.ich have become suspended awaiting the compietlon of some time-aependent operation, Only when the task in which the interrupt was taken becomes suspended as tile result ot all expiicit supervisor operation will the scheduled task become eligible for re-activation. This construction leads to a bimodal classification of processing as real-time in which only interrupts are serviced and tasks may be scheduled, and task-time in which normal task operations can occur. The real-time processors are assigned a reserved set ct temrorary storage locations and are designed to be activated by a hardware interrupt or subroutine call (with the interrupt system masked off) and to return airectly to the cailinj task-time routine. The 4. Basic System Architecture

Multiprogramming in a Small-Systems Environment 9 task-time processors share a reserved set of temporary storage locations disjoint from the real-time set, of course, and are designed to be activated by and return to the supervisor. In a IAMP system machine control is passed among the various TCB's in the CPU queue on a first-come-first-served basis. A particular task, once given control, is said to be active and will run until some time-dependent supervisor operation is requested, the completion of which presumably is predicated before execution can continue. At the time such an operation is requested, its TCB is placed on a special queue depending upon the type of operation requested. At this point the next task on the CPU queue is activated and control is passed to that tasK. Operation continues in this manner until scme task is interrupted to signal the completion or the operation. At this time control is passed to the reai-time processor responsible; and, tollowing its completion, the interrupted task is restarted from the point of interruption. The interruptprocessing subroutine invoked in such a manner has the responsibility or removing the TCB trom the special queue and sciedulinq it on the CPU queue. The TCB is now said to be in the penUinq state. When the pending task again becomes active, task-time processing of the.1/O operation can continue. Now an obvious refinement to this simple system model would allow certain subroutines to be shared among the various tasks. Such subroutines can contain references to parameters and temporaries residing in permanently-allocated scratch storage shared by all tasks in the system. If a task can De suspended in the sense of the preceding paragraph, then it may happen that some of these parameters and temporaries would have to De saved during the suspension interval while, presumably, other tasks may make use of them. In a RAMP system these parameters and temporaries can Dbe saved in tne TCB itself; but it is the program's responsibiliity to determine which to save in each case and to perform tne actual copying operations. Certain system conventions and utility sub utitines streamline this process, however, andi in such a way as to provide an inherently recursive construction. A dRAMP routine can be classitied by the way in which it can be snared by the various task invocations. At each point in the code a certain state of the invoking TCB, common temporary storage anu machine registers is assumed. If thls task state is independent of the state or the realtime system and the common scratch storage allocated to the real-time system, then the routine is said to be interruptable at that point, aindl presumably the hardware can 4. Basic System Architecture

10 Multiprogramming in a Small-Systems Environment be unmasked for real-time interrupts. A routine operates in the task-time state if it is interruptable at some point and in the real-time state if it is net. If the task state is independent or a prior use oa the routine by this or another task, the the routine is designated seritally-reusable at that point. If the task state is independent over a suspension interval during which the routine can be shared by another task, then the routine is designated re-entrable at that point. A tasK-time routine will never alter real-time temporaries or call real-time routines without first masking oft the interrupt system. It a task-time routine makes use at shared scratch storage to save information over a suspension interval, it is by necessity not re-entrable during that interval and cannot be entered by any other task. All temporary storage used by a re-entrable task must reside in the ICB for that task or in storage allocated by and belonging to that Farticular task invocation. Seriallyreusable routines t ypicaliy make use of large amounts of temporary stoLage which are impractical to replicate for each invocation separately. Routines that cannot obey even the serially-reusable criterion are only useful after a tresh program load, of course, and are not usually part of the multiprogramming system at all. Aithougin, in the current imFlemeatations, the basic LiAMP supervisory system contains cnly re-entrable routines, a practical job program can contain a collection of both serially-reusabie and re-entrable routines, depending upon frequency oz use, temporary storage requirements and other such factors. A mechanism must be provided tor each serially-reuasale routine to avoid entry by one task when it is D0ing used by another.. Mechanisms for this are described in the rererences listed at the end cf this report. D uLri ngl normal system o pera tion tasks are created, executed and destroyed routinely and often. In order to economize on the storage used by the various tasks, the TCB band parameter regions are dynamically allocated and released as each task is created and destrcyed. A task is created by an explicit sutroutine call, presumably on the part of another invoking task. The invoking task is here called the alotnher task, and each of her invoked tasks are called her ~dau ters._ As implied, a mother task can create any number ot daughter tasks whoise operations then proceed in parallel with those of the mother task. Optionally, however, the mother tas$ can initiate an explicit operation in such a manner that, once a daughter task has been created, the execution of the mottiler task is suspended and is restarted only when the oaugnter task has coFmpleted all processing. Sucn an operation cani be specified tor only one daughter 4. Bi3asic Systeum Architecture

Multiprogramming in a Small-Systems Environment 11 task at a time. These operations are also possible in other systems recently described. In summary, and before proceeding with a detailed description ot the various system operations and the construction of the various queues, the configuration of a RAMP system at any time during oFeration can be viewed as a collection ot ICB's one of which is in active control of the CPU. TCB's are scheduled on the various queues as the result of real-time interrupt processing or as a result of explicit supervisor operations. Routines can be shared between the various tasks in a limited fashion depending upon tneir use of common routines and scratch storage. Finally, and most importantly, a real-time interrupt operation is constrained to restart the interrupted task at the point of interruption and no task-switching operation is allowed as a result. 4. 1 Task-Time Opeerations In the absence of time-dependent events, execution of tasKs in a hAAE system is on a first-come-first-served basis, with control being passed to each task in turn one atter tne other. TCB's for tasks awaiting execution are held on the CPU__ueue and these are described as being in the endinj state. when a task-switching operation occurs, tne next TC6 on the CPU queue is removed from the queue and execution commences at the instruction address indicated by an entry in the TCB (see Figure 1). A task in this condition is described as bclnS in the active state. It is possible under certain condlitions when aln asynchronous attention is pending that a task be in both of these states at tihe same time, that is pending on the CPU queue and active in execution. Once a task becomes active its execution continues until one of tour events occurs: 1i The task terminates operations and returns control to either its mother task or to the system. The tormer behavior is possitle only if the mother task in question has initiated a WAIT operation (see below) tor the, active daughter task. The latter behavior occurs in all other cases. In any case, the task termination procedure causes the TCB storage claimed by the active task to be released. 2. The task creates a daughter task using the INSERT operation followed by a WAIT operation. This causes the executicn or the mother task to be sus ended pendiny completion of its daughter task activity. During the waiting interval the mother task is said to be in the dormant state. It is 4. Basic System Architecture

12 Multiprogramming in a Small-Systems Environment possible under certain circumstances that a task be in both the pending and the dormant states or in the active and dormant states at the same time. These situations can occur only when an asynchronous attention is pending. 3. The task encounters a temporary busy condition which is expected to last a long time compared to the instruction processing time but a short time compared to the CPU queue processing time. In such a situation a special BUSY or REQUE operation (see below) can be initiated, which results in the TCB being placed at the end of the CPU queue. When this TCB next becomes active due to normal task processing, the task is resumed at the current instruction address specified. 4. The task initiates an I/C operation on a device. In such a situation the TCB is placed on the appropriate _/0 Queue (see below) associated with the device. A task in this condition is described as being in the blocked state. Presumably an I/O interrupt will occur at some future time and the TCB will again be scheduled on the CPU queue. In the latter three of these tour cases, once the active task has been placed in the dormant, pending, or blocked state, the next task pending on the CPU queue is made active and processing continues in that task. In the first case, where the daughter task returns to its mother task, execution continues in tile mother task without interruption due to a task-switching operation, and in particular without placing the TCB of the mother task on the CPU queue. Where no mother task is waiting tor the active task in question, the active task aisappears entirely and the next task pending on the CPU queue is made active. Figure 2 illustrates a typical configuration of a RAMP system in which one task is in execution (active), some tasks are awaiting execution (pending), one is waiting for its daughter task to complete processing (dormant), and some are waiting tor the ccmpietion of an I/O operation (blocked). Ret Ierring to Figure 1, note that the first word in each TCB is always used as a pointer to the next TCB on some queue or other and that the second word is always either zero or a pointer to thne TCB of a mother task. The third word d s used as the instruction address at which executionl will re-commence when the task is again made active. with this organization note that a TCB may be claimed in only one queue at a time and tlat it may be waiting aor orly one daughter task at a time. Furthermore, no matter what the condition is that causes the task to 4. idSic System Architecture

Multiprogramming in a Small-Systems Environment 13 become active, execution can begin only at the current instruction address. Finally, the only ways a task can become active are either through the normal CPU queue processing or as a result ot a return from a daughter task. The fact that these two operations can be independent of each other will be important when the asynchronous attention operation is discussed below. +~....+ +-....+ +......% CPU Q — >1 X —+ > I — > X —+. >1 0 1 o 1 0 X —. —— + I 0 1 I I 1 1 1 1 1 PENDING PENDING 1 PENDING + _.....+ +____..+ +.....+ I/o Q — >1 X —+>....l O > + —— >1 0 1! 0 I I o i I o t I 1 1 1 1 BLOCKED BLOCKED DORMANT 101 0 1 ACTIVE Figure 2. RAME System Operation The various task-scheduling oFerations are implemented in the present RAMP systems as a collection of subroutines arnd entry points. Since these operations make heavy use of the dynamic storage allocation routines, which are constrained to operate in task-time, tasks can be created and destroyed only in task-time. However, a blocked TCB can De sciceduled on the CPU queue in real-time using a subroutine designed ror this purFose. In the present implementation all of the task-scheduling operations are contained o[n a single 128-word page or PDP-8 memory. In this implementation all TCB's must lie in a single core oDaik, which is declared by an assembly parameter. The operations provided are described below: INSELaT - A tasK-t.ime subroutine which allocates a TCB ot specifred lengtn, schedules it last on the CPU 4. Basic System Architecture

14 Multiprogramming in a Small-Systems Environment queue and presets the first three words as the CPU queue link, the return link and the initial instruction address (entry point) respectively. Both the CPU queue link and the return link are set to zero by this subroutine. If a WAIT operation is initiated following the INSERT operation, the return link is set as a pointer to the TCB which initiated the WAIT operation. Upon return from the INSERT subroutine an auto-index register is set as a pointer to the allocated TCB so that device table pointers and parameters can be easily copied. The length of the TCB requested is given upon entry to the subroutine. A special exit indicates that insufficient storage is available in which to ccnstruct a TCB of the requested length. CHAIN - A real-time subroutine which schedules the indicated TCB on the CPU queue. The calling sequence is designed to be convenient in cases where a TCB is to te removed from an I/0 queue and scheduled on the CPU queue. RETURN - A task-time entry point which causes the TCB of the calling task to be returned to the allocatable storage pocl and control to be passed to the mother task (if one exists) or to the next task on the CPU queue (it not). Return is made to the mother task without a task-switching operation, so that argument. can be returned to the mother task in common storage areas. A particular word is designated as the return code and may be used to transmit optional information to the mother task,. REQUE - A task-time entry point which causes the TCB of the calling task to be scheduled at the end of the CPU queue and await its turn next to be activated by the supervisor. This entry point is used when a system resource such as core storage temporarily cannot be acquired by a task, which by convention then retries after all pending tasks on the CPU queue have been activated. BUSY - A task-time subroutine (no return) which causes the sane action as the BEQUE operation except that the instruction address in the TCB is changed to point to the next word following the BUSY subroutilne call. DVLLTE - A task-time entry Fpint which simply causes the next TCB in the CPU queue to De scheduled 4. basic Systeum Architecture

Multiprogramming in a Small-Systems Environment 15 without affecting the TCB ot the calling task. This action is used after a task has been blocked on an 1/0 queue. Whenever a task is made active by the supervisor a switch is set so that the task can determine whether the entry was due to CPU queue processing or due to a return from a daughter task. The distinction is important in connection with the asynchronous attention (see below). Also, by convention, certain fields of the TCB are stored in reserved locations whenever a task is activated. Most commonly (but not necessarily) these are used as device table pointers for the assigned 1i/ devices. 4.2 Real-Time eOeratio ns By definiticn, real-time operaticns occur only when the system is disabled tor interrupts and are not subject to task-switching operations. The construction of the realtime system is therefore cc:pletely conventional and temporary storage allocations are straightforward. Most devices attachez to the various {AMP systems sustain transmission on a character-by-character basis, and generate an I/u interrupt for each character transmitted. A few devices sustain transmission on a block-trans fer basis, using the PDP-d three-cycle data break facility. Interrupts are generated by these devices following the block-transfer operation. An interrupt is taken by the CPU hardware when a device interruption condition becomes pending and the interrupt system is unmasked. The interrupt is taken as a rorced subroutine jump to location zero in memory, following which each device must be interrogated in turn to identify tne one requesting service. Following identification, the requesting device is serviced and the interruption condition is cleared at the device. If (as is not possible on the unmodified PDP-8) it were possible to selectively mask off interruption conditions at tne various I/0 devices, then the interrupt processor could be written An several levels, each higher level able to interrupt a iower level, and so forth. If interruption conditions must Le masked off frc scme devices but unmasked in others zor the purpose of establishing such a priority ranking, then the masking nardware must be built into each device separately. in one RAMP system intended for messageswitchlng applications, permissable device service delays have been contrclled in this manner and through careful design of the peripheral equipment. It has proved convenient in the various RAMP systems to construct the I/O interrupt system as a collection of device service rout inesL each of which services a given device 4. Basic System Architecture

16 Multiprogramming in a Small-Systems Environment operating with a given transmission protocol. A common subroutine, callecd the in te rrujt__ -identifier is held responsible for the identification of each device interrupt, storing status information trom the device, clearing the interruption condition at the uevice and finally calling the appropriate device service routine. These operations are driven by a set of delicately constructed interryup__ccntrol _iock (ICB) tables (see Figure 3), which are designed so that new devices car be added permanently or dynamically with minimum chanjes to the basic system. Using this nierarchy it is possible to assign transmission protocol routines ratner independently to the actual devices in the system. In this manner it is.ossible, at least in one system, to specify any of several ccmmunication protocols tfor use on a single transmission device. I SKIP/TEST 10' { i LINK TO NEXT 1Cb 1 I READ/CLEAR ICT I i DEVICE TALb EPCINTER I I DEV SEEV ROUT ENTRY; Figure 3. interrupt Contrcl BEiock (ICB) Format The structure of the ICB varies among the various systems, and deyends upon tile peculiarities ot the attached i/O equipment. In most systems involving only teletypewriter, paper tape anu "simple" control-unit intertaces, the ICB car take the form of Figure 3; but, in more complex systems involving nigh-performance control-unit interfaces, a much more complex structure has been aecessary. Fields in the ICB specify the device table pointer (see foilowing sec tionl) and the initial instruction address of tne device service routine. Upon entry to this routine, reserved locations in common scratch areas are set as pointers to control blocks assigned to the device. Using information found in these blocks, the routine performs the service indicated, perhaps invclving restarting the I/O device. Note that, using this hierarcny, the device service routine canl be called trom a tasK-time routine (after first masking otf the interrupt system or course) tor the Furpose 4. Basic System Architecture

Multiprogramming in a Small-Systems Environment 17 ot starting the I/O device. This operation has been dubbed thle "tweak" in the current vernacular. 4.3.__npg~ t OP u_ tOperations The general Fhilosophy of I/O processing in the RAMP systems has been to pertorm control and line-editing processes in real- time device service routines using preadliocated butters and a set of ccmmon buffer management routines. Most devices attached to the various systems provide data transmission on a character-by-character basis using an interrupt for every character transmitted. Accordingly, input real-time routines assemble characters serially from the the input device as the interrupts occur and place them in an input buffer, performing code conversion and line-editing operations during the process. dnen a record-ending character is recognized, the first TCB on the input queue is scheduled cn the CPU queue and the corresponding task becomes pending. This task may take the form of a traLnsission operation, which merely copies the record from one device to another, or a processing operation in which the record is interpreted as commands or data to the appropriate job program. While the task-time processing is going on characters may continue to arrive from the input device tor the next following record. In this manner several records may be stored in an input butter up to the capacity ot the buffer. The buftering operation required here calls for a carefully tailored set ot oufter management routines (see Section 4.5) using a cyclic type of buffer construction in wiich the buffer is allowed to "wrap around,," so to speak,:o that the next character put in the buffer following the one at the highest buttfer address will be at the lowest buffter address. To tacilitate these operations a standard bufter control block (BCB) is maintained for each cyclic buffer. The BCb for a butler is usually allocated and preset when storage for the buffter itself is allocated. Since most transmissi cn operations involve storage allocation in one form or another, a requirement exists to snow the size ot a particular record before transmission Degins. For input operations this is performed by the buftter management routines themselves such that the first word reau fron the buffer tor each record is the length of tne record itselt. It the input record is to be simply transmitted unaltered to an output device, then the address or its BCB is passed to the outfut device service routine, which then transmits the recrd ana disposes ot the input but ter as necessary. It the output record is generated by the systeml itself, rather than as a direct result of arln input recora, then the recoru size is coaputed by tne system 4. Basic System Architecture

18 Multiprogramming in a Small-Systems Environment prior to allocation of the buffer. Each I/0 device attached to the system is identified by a poLnter to the device tableL which contains a two-word entry consisting of a unit controlblock (UCB) and a device control block (DCB) pointer. These entries are initially zero. when the device is unattached or not-operational and are filled in when the device is enabled for operation (see Section 6.1). The UC3 contains, among other things, the use count and enable flags (in some systems), I/C queue headers, status words and switches, SCB's and sometimes the buffers themselves. The UCB storage is allocated only when the device is enabled; otherwise no claim is made on the aliocatable storage pool. The structure ot the UCB depends not only upon the particular system implementation, but upon the requirements of the individual device as well. Conventionally, however, the first three (and sometimes four) words ot the UCB are similarly structured as shown in Figure 4. For ease in dynamically enabling, disabling and recontiguring I/O devices, a special set of enable tables is established tor use by the system bootstrap and enable task. These tables establish for each device type (that is DCB) in the system the extent and preset values assigned to the UCB wnen the device is enabled. + A_ _.............. _...... _ + tI ENABLE CONTRCL 1 I ATTENTION I/O QUEUE I + _ _. _ _ _ _. _ _ _.... _.. _ _. _. __ _ + I READ I/O QUtUE WRITE I/O QUEUE + + —-—. —.-. —........... RI EC COUNT/REC SIZE I I TASK-TIME SWITCHES I + _., _ _ __._. _ _ _ _ _.......... + I REAL-TIME S1ITCHES I + iPARAME~EFS + I I Figure 4. Unit Control Block (UCB) 4. BasiC System Architecture

Multiprogramming in a Small-Systems Environment 19 The DCd (see Figure 5) contains, among other things, pointers to subroutines and state-transition tables used by the device service routines. The nature of the DCB information is Lead-only and can be shared by several devices which, nevertheless, are assigned separate UCB's. In the current implementations all UCB's must lie in a single core bank and all LCB's must lie in a single core bank. However, the device table, the UCB's and the DCB's can lie in difterent core banks as determined by an assembly parameter. I ASYNCH TWEAK ENTRY i I ASYNCH BLOCK EN16.Y J READ TWEAK ENTRY J I READ BLOCK ENTIY | I WRITE TWEAK ENTRY I I llWRITE BLOCK ENTEY I I CONEIGURATION TABLE I CONFIG hGUT ENIRY I fEgure 5. Device Control Block (DCB) Format The queue hiaders indicated in figure 4 are used by the system as neads of I/O gueues, and are assigned as the atte nt_ on0 input and output quueues respectively. If an input operation is pending at the device then the input queue is nonempty and siminiarly tor an output or an attention operation. An input operation is initiated by the READ tasK, with the location ot a BCB and the length of the record given when the READ task returns to its mother task. Each input queue then is a chain through tthe TCB's of one or more READ tasks, each of which is in the blocked state. Then a ecorud-ending condition is recognized, the first TCB in the input queue is scheduled on the CPU queue. When the READ task is activated it establishes the BCB pointer and computes the record count. Fiollowing return to the mother tasK calls can be mare on the system subroutine nDASC to fetch characters from the input butter. 4. BasLc jysteY Mchitecture

20 Multiprogramming in a Small-Syctems Environment An output operation is initiated by the WRITE task, with the location ot a BCS given as part of the WRITE task TCB. Each output queue then is a chain through the TCB of one or more WRITE tasks, each ot which is in the blocked state. When a record-ending condition is recognized the first TCB in the output queue is scheduled on the CPU queue.'ihen the WRITL task is re-activated, the buftter-release bit in the BCB is inspected. If it is set then the BCB and its buffer are returned to the allocatable storage Fool. In contrast to those tasks blocked on the input and output queues, those in the attention queue are not aecessarily in the blocKed state, but may be in either the active or dormant states. The TCB's in this queue are set up by an explicit subroutine call and remain in the queue until removed Eitner when an attention signal is recognized at the device or by an explicit subroutine call. A task whose TCB is placed in the attention queue may create daughter tasks, wait for th11eir ccmpletion, perform i/0 operations and in genLeral carry on all normal pLocessing not involving the pending state. when an attention signal is recognized by the device, the tirst TCB on the attention queue is scaedulec on the CPU queue and so becomes pending. The coding within the job program can De arranged so that a return from a daugnter task in the active state can be dif erentiated t~rom an entry initiated ftom the Fending state, so that the attention ccndition can truly be recognized as all asynchronous tdsk interrup;t. It is this type ot operation which causes those strange exceptional situations mnentionea in Section 4 involving a task being in two states simultaneously. Two attention queue opeLations are provided in the basic system: SETAIN - A task-time subroutine which links the TCB of tAe caller on the attention queue for the device indicated as the first device table pointer in the TCB (see Figure 1). CLRATN - A task-time subroutine which unlinks the TCB of the caller riom the attention queue for the device indicated as the first device table pointer (see F ig ure 1). A cpecial exit from this subroutine inaicates when the TCB is not on the attenrtion ue ue, in which case it must by deauction be pending on the CPU queue. Note that the attention <queue is constructed as a first-in-last-out queue, that is, a pushdown stack. Thus tne most recent 5ErATN call detines the TCB to ne scheduled upon the recojriltio n o an attention condition. Also note 4. Basic System Architecture

Multiprogramming in a Small-Systems Environment 21 that the inherent asynchronism between these operations and the device operations require the special exit indicated in the CLIATN subroutine. If CLRATN has been called and returns via this special exit, then an attention condition is pending on the CPU queue but has not yet been taken. The coding in the various job programs becomes rather interesting in such cases. In summary, the real-time and input/output systems are constructed of a collection of subroutines, each serving a number of devices of similar type and designed to be invoked by either the interrupt identifier or by a task-time routine. Each device attached to the system is assigned a device table entry, which contains pointers to the UCB and DCB waich contrcls and records status for the device. Each input real-time routine assembles and edits characters serially using a common set of tufter management routines and schedules a TCB on the CPU queue upon recognition of a record-ending y condition. Each output real-time routine transmits characters serially from its output buffer and schedules a TCB on the CPU queue upon recognition of the record-ending condition. 4.4 StoraQe Allocation it any subsystem can be identified as contributing the most to the capabilities of the RAMP multiprogramming systems, it most certainly would be the dynamic storage allocation subsystem. In the systems described here this subsystem is usea to allocate task control blocks, buffer control blocks, unit ccntrol blocks and the buttfers used both by I/O devices and sometimes tor program residence. the general technique is outlined here; refinements and generaiizations are immediately apparent. At any time during the operation of the system, storage is fragmented into many blocks, some belonging to a task or I/U device, and some representing allocatable free storage. Assume that the tirst word of each of the latter blocks contains the displacement (in words) to the next block rollowing, that is the total size of the block. Now construct a chains through all these blocks using the second word in each Llock. Tnhs chain is called the tre —ace thread and is maintained in order by increasing block size. when a blocK is allocated to a task or 1/O operation, all words in the block are available for use. It the tirst word in the Dlock (the size word) is altered, however, it must be restored before the block is returned to the freespace taread. The operation of dllocating a block to a requesting task or I/O operation then begins with a search along the 4. Basic System Architecture

22 Multiprogramming in a Smail-Systems Environment freespace thread for the smallest block just large enough to satisfy the request (see Figure 6). If such a block is tound, then it is unchained from the thread and split into two subblocks, the first of exactly the size requested and the second of a size equal to the actual size less the requested size. 1 f the second subblock is of nontrivial size, then it is immediately reinserted on the thread at the proper position depending upcn its size. I I(< — FREESP. THREAD 1 ~FREE I + — I I I + _ I I ALLOCATED I I I I + +->I 1 I FREE I I I 1 I t ALLOCATED I I + I I + I I 1 1 +.........-..... _ _ _ _ _ _ _ + Figure 6. Storage Allocation Operations The operation of returning a block to the freespace thread proceeds in three steps. In the first the thread is scanned to fina the block immediately preceding the block to ve ret urned, that is te >3Ioci a f fie ne-rt i2d r stcCWe address. If one is found, then it is removed from the thread and concatenated with the block to be returned. In the second step the thread is scanned in a similar manner tor the next following block, that is the one at the next n igher storage address. If one is found, then it is removed from the thread and concatenated with the block to be returned. in the third step the new block, which by construction here cannot be preceeded or followed by a block 4. Basic System Architecture

Multiprogramming in a Small-Systems Environment 23 on the treespace thread, is inserted on the thread at the proper position depending on its size. This technique is designed to minimize the tragme ntation of storage into many small blocks, no one of which may be large enough to satisfy a particular storage request. In the current implementation a set of routines of this type have been coded *in a single 128-word page of PDP-8 memory and execute in 0.3-2.0 milliseconds per allocate/deallocate cycle, assuming randomly distributed block sizes to 128. In the current implementation blocks can be allocated on any of several threads in any memory bank, although each thread is ccnstrained to lie entirely within one bank. Thus it is possible to maintain a number of freespace threads with scze threads entirely contained in olocks allocated trom cther treespace threads. These routines have been modified tc rLovide a storage-aligned allocation tor Eurposes or prcgram loading on page boundaries. 4.5 Butter Management Aithough device transal ssion in a HAMP system is specifieu on a record basis, most or the slcwer-speed devices must transmit data Col a character-by-character Dasis. furthermore, in the case ct input KeyDoard devices, the input data stream must te edited on a character-bycnaracter basis using special ccntoil characters emDedded in th1e input data stream itseif. These requirements are satistiea Dy a set or tufter management routines designed to present a unitorm intertace to the various device service routines in the system. These routines can De called directly in real-time ana, alter masking off tne interrupt system, in task time. Most burLers are structured as Cclic bufer 5 such that theI next cnaracter Flaced in the buffer after that character at the highest buffer address will be at the lowest Lutffer address. In those cases where the bufter and its butter contrcl block (BCB) are reallocated Detcre every record, this wrap around feature may not be used. Such butfers are called linear_ ouftersx although for purposes of stdandardization they are described in the same BCB tormat. At eaca call on these routines a single character is either Elaced in the buffer or removed from it or a single editing operation is performed. Upon exit trom any routine it nimay be determined whether the bufter has overflowed, unterilowed and, in some cases, whether this is first cnaracter or last character in the buffer or whetner an editing operation was successiul or not. Except in the case of those butiers used in editing cperations, the characters 4. Basic System Architecture

24 Multiprogramming in a Small-Systems Environment processed in a buffer are not interpreted in any way, so that the full twelve-bit word is available for transmission. in editing operations the high-crder (sign) bit is used to delimit an end-of-record condition. The remaining bits are not interpreted, however. All butter operations involve use of the buffer control block, which is either four cr five words in length as shown in Figure 7. The structure of the BCB permits its storage allocation disjoint from its buffer, although the allocation is in fact constrained to lie in the same core bank. The first word of the BCB contains a flag (W) indicating whether the bunter nas wrapped around, a bit (R) used to determine whnether the BCOB and its buffer can. be released following transmission and a field containing the maximum size of the bufter. The second word is a pointer to the last character put into the butffer (put pointer) and the taird word is a pointer to the last character fetched from the buffer (get pointer). The fourth word is the address of the first character in the bufter (begin pointer) and is used to reset either the put pcinter or the get pointer should the buffer wrap around. The structure of the BCB and its buffer differs slightly between those bufftters that are used in editing operations and those that are not. For editing operations an extra word is inserted at the beginning of each record. Tnis word contains the number or characters stored in the record and is computed automatically by the appropriate editing routines. The tiftn word in the BCB, used only during eaiting operations, is a Fointer to the first character in the current record. This word may be omitted from those BCB's not used in editing operations. Iw i h EUF.IER SIZE I + - + + ____ -..___. _ _-.. __ _ + I iPUT POINTER I I GET POINTEh I I bEGIN COINTEk j I f RECORD POINTE a I figure 7. bu~ter Control Block (BCB) 4. Basic System Architecture

Multiprogramming in a Small-Systems Environment 25 5. COMMAND OPERATIONS In almost all applications of the RAMP systems described herein some kind ot oRpeator control of the system is required. In very many ot these applications a rather delicate control of system parameters by relatively untrained operating personnel is anticipated. It seems 4uite typical that the command language interface is the most of ten- modi tied portion once the system becomes operational. For these reasons, the operational interaction segments or the RAMP systems have received a careful aevelopment so that an easily expandable modular construction coula be achieved at relatively low cost in system size and operating sFees. - The command lanqaq inteI te L (CLI) is the basic subsystem in which these operations are implemented and iill be described in these sections. Thie CLI is implemented as a task associated with an I/O device, cailea the commana sourcee which is allocated when tte CLI task is created. During operation, the basic system operational commands are assumea to originate via this device. from time to time commentary may be generated by the system, either as a result ct commands entered via the command source or as a result of exceptional conditions recognized within the system. This commentary is produced on an i/C device, callea the comman_ ssin_, which is assigned to tne CLI task on demand;i. In scme situations, nameLy tnose involving ccmmun ications store-and-torward operations, a third I/O device, called the cory__sink may be assigned on demand to the CLI as tile destination ot all non-command traftic generated by tile ccmanal source. with this organization, a number or CLI tasks can De outstanding at any particular time, each one assigned to a particuiar command source, some ot which possibly invoked by others. A special darguaent is In1cluaed inI the task control block (TCB) assigned each CLT task. Tnis argument is a set of parameter switches which determine, among other things, whe-tner tii aetault operation identitied with the command source is ccoR mode or command mode. If the detault mode is copy, then eacn input message originatinj via the command source is transmitted unaltered to the copy sink with tie roilowing exception: Each input message processed by the CLI is inspected for tne selection code assigned tuhe particular system, usually an USASCII SOB-letter sequence. If the selection code matches, thein tue message is processed by the CLI itselt and is not propagated to the copy sink. If the detault mode is command, then each message generated by tne commanai source is processeu Dy the CLI directly. A special CLI command is available to cause a particular message to appear at the copy sinK. 5. Commaid ORerations

i.6 Multiprogramming in a Small-Systems Environment A command operation is specified completely as a single record; commands are not normally continued on tollowing records. The syntax of a command is described recursively as a keyword followed by a list of operands which may taemselves be keywords with their own lists of operands. A command function is identified with each Keyword name; and the arguments to this functicn are Frovided by the list of operands, each of which is represented by a value. The command function itself produces a value, which may be used as an operand. There are two syntactic forms for these commands, the tree form and the bound form, which are distinguished only in the manner of separation of the operand-field elements. In the tree form the operand-field elements are separated trom one another and trom the keyword by one or more blanks and the operand field is terminated by an end-of-record character. In the bound form the operand-field elements are separated Dy special break characters, which are most often commas and equal signs, and tne operand field is terminated by a blank. Missing or defaulted operands in the free form are indicatea by special symbols or reserved names; missing operands in thie bound form are indicated simply by the juxtaposition of two break characters. in some systems spec ial operana-field ccnstructions are prescribed which require syntax specifications more ccmplex than these. Even 1i these cases the syntactic form assigned to the field, oc;e tie scan hias ternminated on that field, is still a Noi, the basic atomic element with which all commands are constructed is the keyword. A keyword can take the form of d sequence ot digits representing a numerical constant, a se q uence of letters designating eithier a sel f-detining constant or the name of a procedure which defines a value, rL d combinaticii of the twc. The value of a numeric constarn t is deteLmined directly from the sequence of digits usingy either binary, octal or decimal conversion algorithms. Phe value ot a letter string is determined by a table-lookup search, as is the entry point assigned to a procedure name. The values assigned to letter strings, the conversion radix used for digit strings and the various operand-format flags and privilege classes are stored in a tree structure called the keyword dictionar.- The basic operand-field scanner is a recursive subroutine called the keyword intierpreterl anu its operation is as follows: At a point in an operand rield scan a pointer to a keyword dictionary entry is maintained on a pushdown stack. This entrf establishees what torm of operand ield scan is allowed (diLgit string, letter strilng, self-defining constant or procedure name), whlat pzivilege class is reiluired to access 5. Command Opierations

Multiprogramming in a Small-Systems Environment 27 this keyword, what conversion radix to use in the conversion of digit strings and, finally, a pointer to another dictionary entry which establishes a list of letter-string names which are valid in the operand fields of this keyword. During the operand field scan numeric strings and selfie fining letter strings are converted and processed as tound. If a procedure name is found, then the entire process recurses and a new keyword dictionary pointer is established at thle entry corresponding to the procedure name. In this tashion the tree-structured keyword dictionary is interpreted as a function of the names of the various procedures occurring in the operand fields and the order ot their occurrence. Corresponding to each procedure name is a segment of code in ttle CLI itselt which iaplements the actual function required. These segments are usually small and consist of recursive calls on the Keyword interpreter, calls cn other system subroutines and references to system variables. It is clear trom this description that new commands can be added rather conveniently ana even that dictionary entries anda procedure segments can ue added and deleted "on the fly" during system operations invclving dynamic loading and overlay procedures. The ke word interpreter itself occupies about a page of zemory in the current implementation, while dictionary entries are turee or tour words in length and typical procedure segments are perhaps a dozen instructions. Vne Keyword interpreter calls upon the input formatting routine RDBCD (.see Section 6.2) tor all of its input text. The various proceUure segments otten make calls on the output formatting routines. TIhe tasK control block tor the CLI itself contains several parameters which establish among other things the identity of the command source, command sink and copy sink. Also included is a word containing several switches and small tields. The TCiU tor the CLI task is shown in Eigure The fail generality describte in the preceding paragraphs is niot needed in all the various systems, of course; and various subsets ot this general implementation are round among the severdl systems. In one particularly interesting variant an internal line-structured text file has beeii implemented in connection with a text-editor algebraic lan uage interpreter (Reterence 6). In this implementation commands can te entered into the text file via typical text-editing procedures and interpreted as a separate operation. This editing/interpreting function proved so compact and useful that it has been incorporated into ot ler systems, notably the data Concentrator (see l{eterernces 5, 7). In this fashion it is ipossible to D. ComIIand Operations

28 Multiprogramming in a Small-Systems Environment prescribe complex control procedures in a more compact form than in the basic machine language. I LINK TO NEXT TCE I LINK TO CALLING ICB + _..... _.. _. _ I _. _.. _. _. _. _ __ _ _ _ + I ENTRY POINT I CMD SOU DEV TBL ETB I CMi)D IN DEV TEL PTI f I CPY SIN DEV TBL PTR I FLAGS I PLIV CL JBANK I + __ _ _ ___ + ~__- --— _ +__ _.__ + Figure 7. Command Language Interpreter (CLI) TCB Structure Although not all the various bAMP systems have the same command repetoire and the same ccommand syntax, naturally, all nave certain bas.ic minimum capabilities, including those to display ana alter memory locations via the operator's console. Those systems including the time-of-day clock (see Section o.3) have the capability to set the time-of-day cell from the operator's console in nours:minutes:seconds format. Provisions are included in all systems including more than onle keyboard/teleprinter or high-s peed reader/punch to specity Which of these devices is to be used as the command source, command sink and copy sink in any particular operation. Some systems nave a complex hierarchy of commands to enable and disable input/output devices and to prescribe their operational characteristics as terminals to the system. Finally, those that include the text-file facility mentioned just above include provisions to test various conditions and branch among the lines of the textfile itself. A few ot the more interesting commands will be described below. All or these commands have been implemented in the Data Concentrator. DISiLAY - Dispiay in octal foLmat selected memory locations. This command causes a special task to be created which rtselr generates the output text. it moLe llocatioIns are rejuested than can be printed on one line (currently eight), then this task remains in opel ation until all lines have been generated. In such a case the display task 5. Comnmand Operations

Multiprogramming in a Small-Systems Environment 29 sets an attention interrupt (see Section 4.3) on the command source device. It an attention is received trom that device, the display task is terminated at the end of the current output line. ALTER - Alter seiectea memory locations using data entered in cctal rormat. PARAMETEi - Set deiauit parameters in the TCB ot the CLI task issuing this ccmmand. Using apprcpriate Keywords the commiana source, command sink and copy sink devices can be changed, as well as the privilege class and DISPLAY/ALTER core Lank. SET - Set system default parameters. Using appropriate keywords, the time-of-day clock, broadcast/signon messages and startuF/shutdown flags can be manipulated. TASK - Create a new CLi task with a TCB as specified. Using appropriate keywords the invoking CLI task may be specified to either continue or to wait for the ccmpletion ot the invoked CLI task. OFF- Oftline device. if the specified device is in tCe dit laoe stdte, (1n iace it in tVe ccftiie state. ON - Online device. If the specified device is in the offiine state, then Flace it in the available state. SENSE - Print on the command sink certain fields of the device tables and unit control blocks of the devices specified. ENABL - Lnable device (see Section b.1). Using appropriate keywords the device type and default operaticnal attrivutes can be estabiishea and the 1 J YDvo I1i L'L1 td Sk C3) D 23 cUiJ z -tC jip,.r continue or to wait for the coQmletionl ot the ENAbLE operation. DISAbLE - Disable device enat1ia by taie ENAiBLE command. HiALT - Transmit asynchronous HALT to device, placing it in the purge state (see Section 6.1).;OOSE - Transmit asynchronous attentilioni to device (see Sction 4.3). ECHO - Transmit tussaje rollowing (on tine same commuand 5. Commdnd Operations

30 Multiprogramming in a Small-Systems Environment linel to the device specified. BROADCAST - Transmit broadcast message to the devices specified. EDIT - Update the internal line tile at the line number specified using the message following (on the same command line). CONTROL - Establish new operational parameters for the devices specitied. 5. Command Ojerations

Multiprogyramming in a Small-Systems Environment 31 6. SPECIAL OPEBATIONS In some of the RAMP systems special supervisor operations have been iaplemented, scme of which have general application in other systems. These operations include very general device allocation ploceduLes, I/O utility routines, interval timer and time-of-day clock and system initialization and contiguration subsystems. New systems have been synthesized by picking and choosing among these subsystems, depending on the application of the particular new system, tor those subsystems which are useful. For the most part these subsystems are modular and can be added and deleted Tromi the basic system without materially disturbing other system compcnents. 6.1 Device Allocation Ln most or the operatingy AME systems the allocation and contiguration of I/O devices can be performed when the system is first initialized tollowing either a power-on reset or initial program load (see Section 6.3). In some systems however, in particular those intended for store-andforward operations, the aliccation and configuration operations may become quite complex and may involve the 3eneraticn of special proDe sequences tor device identification and the modification of device service routine characteristics "on the ly. " In such systems several characteristics are des irab le, among them the following: 1. Core storage ior control blocks, I/O queues, etc., should not be aiiocated if the device is not in use. 2. A device may te allocated to only one particular task, although any number or other tasks may use it. 3. if a device is allocated by a task, then that task is solely responsible for its deallocation. 4. A device should De madKed busy (for allocation purposes) when irst allocated to a task and marked non-busy cnly when all time-dependent discornect sequences have been completed. Somef of these cha rac teristics involve rat her interesti1n architectural requirements, which will be the topic or this section. As discusscu in Section 4.3, corresponding to each I/O iaevice dttacheui to the system is a two-word device table 6. Special op;erations

32 Multiprogramming in a Small-Systems Environment entry. One word of this entry points to a unit control block (UCB) which, presumably, is allocated only when the device is active. The other word of this entry points to a device control block (DCB), which is a fixed table of control information peculiar to the device type. Typically, a collection of devices such as teletypewriter terminals are assigned a contiguous block ot device table entries such that each teletypewriter is assigned a unique UCB and a common DCk. A device will be said to be in the available state if its DCB entry is zero, and without respect to its UCB entry, and in the reserved state otherwise (see Figure 9). A device can be switched between the available and the reserved state cnly when the UCB entry is zero, however. A device is switched from the available- to the reserved state prior to the configuration or of line operations, and is switched trom the reserved to the available state following the disconnect or online operations. All data transfer ana device control operations are ignored in the available state and behave as if the device were in tact nonexistent. DCB UCB ACI HLT USE set alloc bit bit cnt Available 0 x x x x Reserved 1 0 x x x Configuration 1 1 0 0 x Working 1 1 1 0 0 Busy 1 1 1 0 1 Purje 1 1 0 1 1 Disc nniect I 1 0 1 0 Figure 9. Device Allocation States Once a particular device has been switched trom the available to the reserved states, then a sequence of operations may be necessary before the device can be used in data-transter or control operations. These operations are pertormed by a special ENABLE task whose parameters are the device table pcinter and a DCB cinter tor the device type in question. An invoking task may issue a WAIT for the ENABLE task in which case a return cone indicates whether or not the operation was successful. Foilowing a successful ENABLE task completion the device may De reterenced for 6. Special Operations

Multiprogramming in a Small-Systems Environment 33 iEAD, WRITE and HALT oFeraticns (a SENSE operation is always valid in any state ). Interrupts are ignored in the reserved state. The ENABLE task proceeds Iy first allocating and presetting a UCB using informatlon tound in the configuration tables. Once the UCB has been allocated and preset the device is said to be in the confijg_ tion state, in whica interrupts will be seLviced and CTHL operations honored. READ or WhITE operations in this state will be reqiueued, however. Once in the configuration state a series of quite complicated operations may be performed which are designed to identity the type of terminal, it the device is connected to a data set, or to wake up and start a mechanical device, if the device is a printer or a card reader. During these operations the UCB may be deallocated and reallocated in different formats, timeouts may be initiated ana other tasks may be generated; but, in any case, if the ENABLE task terminates successfully, the UCB ann DCB entries have been stored correctly in the device taDle and the aevice has been placed in the workiaq state and is ready for use. If the operation terminates unsuccessfully, fcr instance due to a wrong-number call on a dlta set, the the ENABLL return code is set appropriately and the device is returned to the reserved state. Now, once the ENAELE tasK operation has been completed, the device is allocated to the task issuing the ENABLE, aithough it iiiay be used by any number of other tasks. By convention, a task which issues a number of READ or WRITE operaticns on the device tirst increments a use count in the Tirst word of the UrB for that device. When these READ/WRITE operations have teen concluded, this word is decremented. Ihis wcrd is aiso incremented if an interval timer operation is set on the device (see Svction 6.3) and decremented either when the timer operation is cleared or by a timer interrupt. These actions are done so that the device wiii not be disconnected until all pending timedependent operations have been terminated. A device can De discounected at any time by a HALT task operation. Tais task may be issued by any tasK at any time, either explicitly on the part ot an operator or internally due to a hardware maltunction detection (e.g. Data set oniiook indication). A HALT operation is also implied by a DISAJL tasK oFeration.'ciiowing the HALT operation the device is iet t in the pjur Ce state and any f urther operations, including interru t serlvice, are ignored with tile exception cr tne DISABL tasK operation. The HALT operation usuaily causes some cevice-dependent activity which results in a request f cr disccnnect. In the case of a uata set tlhe Terminal hieady control lead is dropped, causing 0. Special Operations

34 Multiprogramming in a Small-Systems Environment the data set to go on-hook. In the case of a System/360 interface operation a special sense bit is set indicating to the System/360 program that the job should be signed off. The device now remains in the purge state until the device service routine itself recognizes that disconnect has in fact been ettfcted. This condition, recognized by the device service routines themselves, causes the device to be placed in the disconnect state, in which all operations except DISAbL are ignored. The disconnect operation itself causes all tasks blocked on the attention, read and write 4ueues to be indiscriminantly scheduled pending on the CPU queue. Obviously the various task returns must be coded to recognize this pathology, since I/O operations may he only partially completed. The principal result of this violence is that the task which issued the ENAbLE, or one of its daughter tasks, receives an attention interrupt, which causes it to clear its current WAIT condition, usually by issuing a ATTN task on some device. Eventually, during the recovery procedure, the pathology is discovered on the dying device, which is still allocated to the task which issued the ENABLe. This task then by convention issues a DISABL task operation to disconnect the device from the system. Note that the issuance of the DISABL is not necessarily synchronous with the trauma of the device as it progresses through the purge state to the disconnect state; and, turthermore, the decrementing of the use count as the various operations pending at the device go "down the drain"i is asynchronous with both ot these operations. Therefore, unless the device is already in the disconnect state and the use count is zero, then the LISABL task itself is blocked on the attention queue of the device's UCB. Following satisfaction ot both ot these conditions tae DISABL task is scheduled pending on the CPU queue. In the final phase of DiSABL processing the UCB is deallocated and the dcevice is again placed in the reserved state. Following return to the invoking task the device can be placed in the available state and the invoking tasxk, now assured that all I/O responsibilities have been discharged, can continue its own operations. These rather complicated procedures are necessary in any system which allows I/O devices to be shared among several tasks, altiough the actual code involved is not as massive as might be suspected. The addition ot these teatures costs perhaps a page of code in the current implementation. t. Sp eca lU t to_ u e lia ios 6. Spec ial Operations

Multiprogramming in a Small-Systems Environment 35 In any system involving corversational interaction with an operator, a number of 1/U formatting routines are always necessar y. These routines provide for the charactersensitive recog nition and translation functions for the input operations and the translation functions and text generaticn tor the output operations. In the current RAMP i plementations a single input routine is provided which maps 8-bit USASCII characters into a 6-bit packed representation and determines whether the cnardcter is a digit, a letter, a special cnaracter or a control character. In some systems the assembly of letter strings as keyword names and conversion of digit strings as numeric constants is a function ot the keyword interpreter as driven by the keyword dictionary. In all command input operations the parity bit is suppressed and lower-case USASCiI characters are conveLted to their upper-case equivalents. Conversion of 12-bit binary words into digit strings in octal or decimal radix is p rovided by the special subrou tines PEOCT ann PRDEC. Leading zeros may be suppressed using PRDEC. Letter strings packed two six-bit characters per twelve-bit word binary word can be converted into 8-nit UAbCil strings by means of PRBCLD, which maps a single 1i-bit word, and PRCCM, which maps a vector preceeded Dy a count of the iumDer of 12-bit words. It the time-ofdiay routines (see Section 6. 3) aLe included in the system a subroutine PRCLK is available to print the time-of-day in tile hours: minlutes: seconds format. In one RAMP version all output text generated by these routines is assigned the correct evten- parity bit in I osition 8 of the USASCII character. In the otners this position is forced to a one bit. In order to print a comment or a line ot text, the system arcaltecture calls tor the creation of a WRi~E task control biock, a buffer contIol block and tihe buffer itself. A subroutine GTDEV is provided for this purpose, which derauits the output message to the command sink. This suoroutine creates the WRITE TCE, schedules the TLB oin the CPU iueue and sets the iCB pointer. The BCB is allocated as part of the TCB pardmeter regicn together with the buffer itselr. The butfer-release bit is not set in the BCB, since tne B b and its buffer are released automatically together witht the TCd when the WRITE task returns to its invoking tasK. Tne lengtn of the buffer is specified upon the call to GTDEV, wuich then returns in an auto-index register a pointer to the tufter. Characters may be storen uirectly in the bufier via the autc-index register or may be formatted a(n1 stored autoncatically usitng the output format routines descriDed anove. A call to C iiLF must be made to tinish G6. SpeciFi Oplerations

36 Multiprogramming in a Small-Systems Environment processing the BCS fields when all the text has been stored in the buffer. 6. 3 Interval Timer and Time-of-ajy Clock In very many applications of the systems discussed here, a need exists to determine the time of occurrence of an event or the time difference between two events. Most commonly, only the latter facility, called here an interval timer operation, is necessary. In real-time data logging systems a time-of-day clock operation is also necessary. In the typical small machine considered for RAMP application an interval timer is easily implemented either as a special I/O device or as a special cycle within -the CPU itself. In either inplementation a location in core memory is caused to increment every so often, usually in the 10-100 mS range.:When the count overflows an interrupt occurs which is then processed in the usual manner. The manner in which such a device can be incorporated into the RAMP system architecture to provide interval-timer and time-of-day facilities will be the topic of this section. Due to the inherent multiprogramming nature of a RAMP system, it is common that several independent logical timers are required at any given instant. Some of these timers are necessary tor task-time operations in which the task is to be blocked for a certain time interval, while others are necessary for real-time operations in device polling and control. Such an architecture has been implementea using a chain oi clock _control blocks (CCB) Isee Figure 10) which correspond to the set of logical timers in operation at every instant. These CCB's are linked in a CCB chain in a particular sequence as follows: consider the intervals assigned each of n logical timers t(1),t (2),...,t(n) and assume t (i) et (i+1) for all 1<i<n. Then the CCB's corresponding to t (),t(2),...,t(n) are chained in that order and the countdown interval in the (i+1) th CCB is preset to contain the value t(l+1)-t(i). Then each time a timer interrupt is taken, the first CCB entry in the chain is unlinked and a field in this entry is used as a branch address to a real-time processing routine. At this time the interruption condition is cleared and the countdown interval of the next CCB entry on the chain replaces the contents of the hardware timer. Processing continues in this manner until the chain tecomes empty, at which time the hardware timer is allowed to cycle through its full-period interval. A pre-constructed CCB entry requesting an interval of t basic timer stepIs can be entered in the CCB chain using the subroutine SETIM'P. This subroutine scans the current CCB chain and totals the cumulated expected countdown interval t(i) at the ith entry. if j is the index of the first entry 6. Special Operations

Multiprogramming in a Small-Systems Environment 37 in the chain such that t(j) >t, then the new CCB is linked between the (j-1)th entry and the jth entry, a new value tt(j-1) replaces the countdown interval of the (j-1)th entry and a new value t(j)-t replaces the countdown interval of the new entry. Obvious refinements are made if the new eltry is either the first or the last in the CCB chain. I LINK TO NEXT CCE I I COUNTDOWN INTERVAL I 1 INT ROUTINE ENTiY ] Flgure 10. Clcck Control Elock (CCB) Format An already existing entry in thie CCB chain can be deieteu troai the cniain using the subroutine CLRTIM. It j is tue index of the entry to te removed, then this subroutine will unlink it from the chain and link tne (j-1)th entry to the (j+l)th entry. Eacli entry In the chaiu starting with the (j+l)th then is corLected by adding to its countdown initervai the value associated with the jth entry. This rather simple and straightforward architecture is complicated by the tact tnda t the hardware timer can increment at any time, and in Farticular during either SETInE and CLRTIM processing. Timer service routine snarls in the present implementation are avoided by "freezingl" the timer oefore any change is madE to the CCB chain and "tnawing" it when the srocessing is complete. In the freeze operation tne countacwn interval of the first CCB entry is correctea by the elapsed time since the timer was last set; and the timer is reinitialized at zero. in the thaw operation any timer interrupt conditions, which may have DecoIrme pending due tc a timer increment, are serviced; and tne countdown interval of the first CCB entry replaces the t.imer contents. At certain points during the treeze/thaw operations when the timer is changed, a possitle timer increment may be Lost. This is because, in the simlle machlines considered h-ere, the timer can increment a ter the old contents have teen rea- out but before tne new contents have been read in. Even some iadrge macnines iike the System/360 Model 67 have sufferea at one time or another because this could happen. In tae Model 67 case the lifticulty has been avoided by using a core-to-core move operation that moves the old o. Special OjeLations

38 Multiprogramming in a Small-Systems Environment contents out of the timer and moves the new contents into the timer in one instruction. A special interlock circuit prevents a timer increment during the execution of this particular instruction. In the small machines considered here a timer increment during this sensitive sequence is impossible to detect unless it also causes an interrupt flag to be set. This latter condition is detected and properly processed in the current implementation. All subroutines which maintain the interval timer operation are contained in a single page of memory in the current implementation and are designed to be removable without affecting other system components (except the timeot-day clock - see below). In the current implementation all CCB's must lie in a particular memory bank defined as a system assembly parameter. It has been convenient in at least one RAMP system to implement some timer interrupt operations as a pseudo-receive or pseudo-transmit interrupt for a particular I/O device. In this system a device;ervice routine may request a timer interrupt which, when taken, appears as a character interrupt. However, using this construction it is necessary that the timer routines appear recursive to the real-time device service routines. This is accomplished by setting a flag in the timer-freeze operation and testing this flag in the interrupt identifier after the device service routine has been called. If the device service routine ever calls a timer service routine, tnen the interrupt identifier itself will perform the timerthaw operation, which m ay involve calling other device service routines. Special interfaces for tasK-time calls on the timer service routines accomplish this same function. A real-time or time-of-day clock is easy to implement, given the interval timer operation as described abcve. This is done in the tollowing manner: a 24-bit time-ol-day cell is maintainea in units of the tasic timer step relative to midnight. Each time a hardware interrupt is taken the countdown interval indicated in th'e first CCB entry is added to the time-ot-day cell. If the CCB chain is empty then the timer has completed one tull cycle, and the corresponding interval is added to the time-of-day cell. Each time the timer is frozen a quantity equal to the countdown interval of the first CCB entry minus the current timer value is added to the time-of-day cell. In this manner the time-ofday ceil is corrected each time the timer is updated. Subroutines are provided in the current implementation which set the time-of-day cell using values tor hours, minutes, seconds and hundredtls of seconds as entered via the command language interpreter. A subroutine PRCLK is available to print the time-cf-day in the format HH:',M:SS (Hil = hours, fiM = minutes, SS = seconds). All subroutines 6. Special iperations

Multiprogramming in a Small-Systems Environment 39 which maintain the time-ot-day clock are contained in a single paje in the current implementation and are so designed to be removable rom the basic system without affecting other system components. o.4_Y S__em Initialization and Configur ation It has been convenient for reasons of debugging ease and erLor recovery procedures to construct the RAMP systems in a self-initializing fashion. In ail systems, at initial program load, selected storage blocks (including the device table) are erased, storage a locatlon treespace chains are initialized and the CPU queue and CCB chain headers initialized. Then a number ot ENABLE tasks are generated and a task servicing the operator's console is created. All or these operations are table-driven so that changes can be easily reassemblea in the system. in the case of one of the systems intended for message store-and-lorward operations, the configuration following either an initial program load or a power-on restart is controlled by an inspection oa hardware conditions to determine which interfaces and line adapters are operationai, fcllowing which the operational devices are marked in the available state and certain ENABLE tasks are automatically generated to start the system. This system wakes up with two System/360 interfaces, the line-adapter scan controls, thle operator's console and a reserved Systela/3o0 intertace unit address in the working state, following which further configuration information can be entered either via the operator's console or via the System/360 interface. In particular, the interactive enhavior during the initial phase fcliowing connection of a terminal to the system can be programmed as a series of commands enteled in the internal line-tile (see Section 5). Jsing tnis file a cycle of inquiry/response can be elicited from the terminal user to determine special requirements prior to connec tion with the Systew/360. It is possible using this technique tc connect the terminal tc either or DOth System/360 interfaces in the case of a partitioned system where one system is running on one CPU and another on the other. in such cases the ccntrolling line-file is loaded directly into the system via the System/360 intertfces. In the case ot the cther RA P systems, the configuration following initial program iload is established simply by a prestored table. However, following a power-on reset the system is restarted at the point foliowing the power-ortf interrupt. All I/O devices are reset by tthe power-off conditicn of course; but, in these simple systems, tnls does not result in pathological behavior other than the 6. Special Operdtions

40 Multiprogramming in a Small-Systems Environment loss ot a character or two if a device operation was pending at the same time. The power-off interrupt and power-on reset operations can be supported only it the proper hardware option is installed in the PDP-8 of course. b. Specia Operations

Multiprogramming in a Small-Systems Environment 41 7. RJFEIENCES 1. /ills, D.L., A__ andom-Access Mujlte-Proqram System toL Lanqgue La boratoriesS Language Laboratory, University of Michigan, April 1965. 2. Mills, D.L., A Proposal or a CCmputer-Supervised RAMP System Language Laboratory, University of Michigan, May 1965.. Mills, u.L., RAMP: A Mu IltEiroram minq Sstem aor RealTime evce onr Concomp Project Memorandum 5, University of Michigan, May 1967. 4. Mills, D. L., Z/O_Extensions_toEAMP_ ConcomF Project Memorandum 11, University of Michigan, October 1967. J. M i ils, L.I., Th1e___t Da__ Conce ntratorx. Conco mp roject Technical Report 8, University ot Michigan, May 1968. Also in PEocedings ot University of Wisconsin Engineering Institute, December 1968, pp. 1-113. to Mills, D.L., RI_{AMPA_rc hitectue i_a Utility_ Caiculator Systiem Concomp Project Memorandum 24, say 1969. 7. ai1s, D.L. T.oRpcs i Computer CommunicationsSsteems Concomp Project Technical Repcrt 20, Mlay 1969. Also in ProceldinYs cl University of Michigan Engineering Summer Conterence, June 1969. d. Frantz, D.., Brender, h.F., and Foy, J.L., Jr., LOCCSSL A Multiroqrjn minj' mcitor for the DEC PVP-7 Concomp PLroect Technical Repor t 10, University of Michigan, Ncvember 1968. 9. Breanker, R. E., Erantz, D.., Foy, J.L., Jr., and Schunior, T.W., _Sjc iajl iZc Syst ____tem Software tor iate _ac tilnLC PDP-7 and__IBM _1 _c omurputersx Concomp Pro jec t Technical Heport 11, University of Miichigan, December 1968. 10. Jackson, J. h., An Executive System for __a_ C 339 Co2_aLut-er Display Termi na1L Concom- Project Technical Report 15, University ot Michigan, December 1968. 7. References

security Classification DOCUMENT CONTRCL DATA - R & Security iio..:...classi.ration of title:: O:,..:...'... - overall reortr is classof;ed 1. ORIGINATING ACTIVITY (Corporate author) 2a. DE0 RT SECURTY CLASSIFICATION THE UNIVERSITY OF MICHIGAN UN CLASSIFIED R2b. GROUP CONCOMP PROJECT 3. REPORT TITLE I MULTIPROGRAMMING IN A SMALL-SYSTEMS ENVIRONMENT I. D E C 4Th- - T TR P of re-oTr: 19nd inl.usive dates) TE BY0Wff"RzPORT' 19 5. AUTHOR(S) (First name, rrmiddie initial, last name) DAVID L. MILLS 1 4 ]. REF:)RT DATE ia. TOTAL NO. OF PAGES't-. No. CF REFS MAY 1969 43 10;38aX. CONTRACT OR GRANT NC. t 5a. ORIGINATOR'S REPORT NUMBER(S) DA-L2-083 OSA 3050' TECHNICAL REPORT 19 h. PROJECT NO. i I9b. OTHER REPORT NO(S) (Any other numbers that may be assigned S c. ~ this report) i d. 10. DISTRIBUTION STATEMENT Qualified requesters may obtain copies of this report from DDC. 1.'!.' EM':T,-'-RY N,-ES':2. SPONSORING MILITARY ACTIV:TY I | Advanced Research Projects Agency 13. ABSTRACT This report discusses multiprogramming systems architectures suitable for use with small machines of the PDP-8 class. Techniques for task and I/O device scheduling, storage and device allocation, buffer and timer management, and command language interpretation are discussed in detail. Illustrative details are freely drawn from a follow-on version of RAMP, a multiprogramming system now used in several applications involving process control, message switching, and terminal control. OD N OV 6571473 Security Classification

UNIVERSI OF MICHIGAN Security Classification 3 9015 03483 7149 14. 1 LINK A LINK B LINK C KEY WORDS K ROLE - WT ROLE WT ROL I mult iprogramming storage allocation device allocation supervisory system PDP-8