United States Patent 15
`Zave
`
`(11)
`
`[45]
`
`Patent Number:
`
`Date of Patent:
`
`4,685,125
`Aug. 4, 1987
`
`[54] COMPUTER SYSTEM WITH TASKING
`
`Attorney, Agent, or Firm—Ronald D. Slusky
`
`Inventor: Derek A. Zave, Sea Bright, N.J.
`[75]
`[73] Assignees: American Telephone and Telegraph
`Company, New York, N.Y.; Bell
`Telephone Laboratories,
`Incorporated, Murray Hill, N.J.
`
`.
`
`[21] Appl. No.: 393,123
`
`[22] Filed:
`
`Jun, 28, 1982
`
`Inte Ch coc esac ceenearecnenenenseses GO06F 9/00
`[SE]
`[52] LS. Ch. ace ceeeceesceeeneeeeeeacteccnsectereesesenens 379/96
`[58] Field of Search ... 364/200 MS File, 900 MS File;
`379/96
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,220,990 9/1980 Alles... eee eesseseeeeoneoneeees 364/200
`3/1981 McColloughet al.
`. 364/200
`4,257,096
`
`.. 364/200
`3/1981) MOrann .....seee
`4,257,097
`
`.. 364/200
`4,318,173
`3/1982 Freedmanet al.
`.........000.. 364/200
`4,356,546 10/1982 Whiteside et al.
`4,419,728 12/1983 Larson... es eseeeeseetsenee 364/200
`4,430,707 2/1984 Kim oc eesstscesteenereencene 364/200
`
`OTHER PUBLICATIONS
`
`Sperry Univac Reference Series 1100 Executive System
`Programs Reference 2-1 to 2-26, 1981.
`Primary Examiner—Thomas M. Heckler
`Assistant Examiner—John G. Mills
`
`ABSTRACT
`[57]
`An integrated data processing and communication ser-
`vice is provided by a system which comprises a plural-
`ity of nodes interconnected via a packet-switched trans-
`port network. Each node includes a database processor
`and atleast one node processor, with a numberoftermi-
`nals and hosts being connected to thelatter via at least
`one front-end processor. Processes existing with each
`node processor are two types—application layer pro-
`cesses which perform “useful work” on behalf of the
`customers and the vendorof the service, and control
`layer processes, each of which manages, or provides
`some part of, the service itself. The processors are vir-
`tual memory processors and the program region of the
`virtual address space of each process includes both a
`process-specific image and shared image. The formeris
`weakly linked to the latter and providesit, via a set of
`primitives, with a number of communications process-
`ing services including file/database management, appli-
`cation program control, interprocess communications,
`station access and message services. Such services are
`also available fot use within the shared imageitself. The
`shared image also provides a numberof “supervisor”
`services including enforcementof a system ofprivileges
`for the primitives; memory allocation; condition han-
`dling; event services; and establishment and manage-
`ment of the tasking system.
`
`9 Claims, 21 Drawing Figures
`
`21
`
`a
`
`23
`
`1/0
`DEVICES
`
`al
`>
`
`29
`
`1/0
`DEVICES
`
`NODE 10 5
`TA} —--3}
`coy"
`aN
`= 23 =
`1/0
`DEVICES
`
`29
`
`ww
`DEVICES
`
`|)
`
`'
`
`!
`
`20
`
`2B
`
`NODE
`PROCESSOR
`2
`
`ue
`
`22
`
`5
`
`6
`
`NODE
`PROCESSOR
`
`24
`
`DATABASE
`PROCESSOR
`
`28
`
`SPARE
`PROCESSOR
`
`‘I
`
`
`
`
`FRONT END FRONT END|99
`
`PROCESSOR
`PROGESSOR
`
`
`
`TERMINALS|/(2 TERMINALS |/~
`
`
`
`HOSTS
`
`10b
`
`HOSTS
`
`l0b
`
`Google Exhibit 1042
`Google v. VirtaMove
`
`Google Exhibit 1042
`Google v. VirtaMove
`
`

`

`U.S. Patent Aug. 4, 1987
`
`Sheet 1 of 16
`
`4,685,125
`
`FIG.
`
`|
`
`TRANSPORT
`
`NETWORK
`
`

`

`Sheet 2 of 16
`
`4,685,125
`
`
`
`
`
`62
`
`ve
`
`
`
`GNILNOUJ
`
`U.S. Patent Aug, 4, 1987
`|O/IO/T
`oRfeesa=122[~@=12
`
`S391Aa0S30IN30
`
`YOSS3O0UdHoSS300Ud
`vs92asvaVIvG92
`DOISTWNIWYSLpo)7|STWNINUSL
`
`‘SIOIAS0SAVIAIG
`0/IO/Ti6244Ie
`
`401SISOHaolS1SOH
`
`405S300UdYOSSI00Ud
`
`JOONJQON
`
`
`
`40SSI00Ud
`
`|
`
`
`
`GNIINOYS
`
`Y0SS3004d
`
`
`
`
`

`

`U.S. Patent Aug, 4, 1987
`
`"Sheet 3 of16
`
`4,685,125
`
`NODE PROCESSOR 20
`
`3I
`
`BUS
`ADAPTER
`
`|
`
`
`(FIG. 2)
`OP 23
`TO P24
`(FIG. 2)
`
` FIG. 3
`
` 3T
`
`
`
`
`t
`
`y COMPUTER 40
`FIG. 4
`eS |
`
`44
`
`IMAGE
`REGION
`
`|rrr™~—‘“CSY
`_rr—‘“sSSCSsSY
`A DATA/ CONTROL
`|
`
`|si“‘t‘CSCSCsSOY
`B DATA / CONTROL
`DATconROL
`|t—“‘CSCSCsSY
`© DATA/ CONTROL
`_rs—‘—™SC—sOY
`OPERATING
`SYSTEM
`
`SYSTEM
`REGION
`
`
`
`
`
`
`
`

`

`U.S. Patent Aug, 4, 1987
`
`Sheet 4 of 16
`
`4,685,125
`
`wweuu
`Sof
`=1
`= a5—oa
`
`=
`
`
`
`VIRTUALADDRESSSPACEB
`
`VIRTUAL
`
`FIG.5
`
`>
`So
`OQ
`oS
`oe
`oS
`oS
`Qo
`
`ADDRESSSPACEA
`
`>
`oS
`
`Ss
`oS
`Ss
`oO
`as
`
`80000000
`
`

`

`U.S. Patent Aug. 4, 1987
`
`Sheet 5 of 16
`
`4,685,125
`
`vRTUAL MEMORY
`
`VIRTUAL ADDRESS
`SPACE. A
`
`F/G. 6
`
`PHYSICAL NENORY
`
`NAAN MENORY
`
`SPACE C
`
`
`
`"A" PAGE
`TABLES
`B
`
`73" PAGE
`[By TABLES
`| "G" PAGE
`|Bei
`
`
`VIRTUAL ADDRESS
`SPACE B
`00000000;
`00 00 02 00
`
`MAPPING
`MECHANISM
`63
`
`
`
`
`TABLES VIRTUAL ADDRESS
`
`

`

`U.S. Patent Aug. 4, 1987
`FIG. 7
`
`|
`
`Sheet6 of 16
`
`4,685,125
`
`FIG. 8
`
`SOFTWARE| HARDWARE
`CONTEXT|CONTEXT
`
`
`
`VIRTUAL
`
`ADDRESS
`
`SPACE
`
`
`
`FIG. (2
`|
`TASK
`30
`
`
`ScHEDULING TASK|[_TASK29+
`
`a>
`
`FIG. 13
`1303
`TASK CONTROL BLOCK
`
`
`
`
`*® ACTIVE BIT
`
`Prony|priority|TeeSE
`x WAKEUP REQUEST BIT
`
`
`1305
`1306
`STACK END
`1307
`*1308
`x * RESOURCE SUSPENSION BIT
`
`
`ROUTINE START
`
`
`
`
`130)
`
`1326
`
`QUEUE. LINKS
`
`FRAME POINTER
`
`STACK | POINTER
`
`

`

`icvi
`
`\o=
`
`4,685,125
`
`
`
`~~”
`
`(X45)5YasSNVULais
`
`
`
`
`
`
`SASSIOOUdYAAVTTOULNOO
`
`U.S. Patent Aug. 4, 1987
`
`NOILWONTddY6Old
`
`
`‘Idd¥.‘TIddV‘ldd¥
` WSsa0Hd
`S38800Ud
`
`
`
`

`

`U.S. Patent Aug. 4, 1987
`
`Sheet 8 of16 4,685,125
`
`FIG. 10
`
`VIRTUAL ADDRESS SPACE (NOT 10 SCALE)
`
`
`
`
`
`PROGRAM(PQ)REGION
`
` \oTHer~/——Sieg——”—————surervisopkJsuarep
`imace
`
`
`
`
`
`UNALLOCATED PAGE
`
`
`ENTRY VECTOR
`
`
`SUPERVISOR START UP MODULE
`
`
`
`INITIALIZATION AND TERMINATION SCRIPTS —
`
`
`
`
`
`
`
`
`
`
`
`
`
`LOG FILE OUTPUT SERVICES
`
`
`PROCESS CREATION SERVICE
`
`
`
`
`
`
`
`
`
`MISCELLANEOUS
`
`
`TASK CONTROL SERVICES
`
`EVENT CONTROL SERVICES
`
`CONDITION HANDLING ROUTINES
`
`INVENTORY CONTROL SERVICES
`
`PRIMATIVE ENTRY PROCESSING
`
`MEMORY ALLOCATION SERVICES
`
`UTILITY ROUTINES
`
`OPERATING SYSTEM INTERFACE ROUTINES
`
`SEQUENTIAL FILE 1/0 SERVICES
`
`BLOCK FILE I/0 SERVICES
`
`INITIALIZATION ROUTINES
`
`TERMINATION ROUTINES
`
`PRIMATIVE CODE
`
`SUBROUTINE CODE
`
`SUBSYSTEM TASKS
`
`APPLICATION PROCESS MANAGER
`
`

`

`U.S. Patent Aug, 4, 1987
`Sheet9 of16
`4,685,125
`
`
` 02 ALLOCATABLE MEMORY (MO)
`
` i104
`
`PROCESS- SPECIFIC IMAGE
`
`
` ALLOCATABLE MEMORY (M1)
`
`FIG. Il
`
`
`
`—___—____—USERAREA———-———__’
`
`
`
`
`
`
`
`
`
`UNUSED
`
`|
`
`USER STACK
`
`LAST PREALLOCATED TASK STACK
`LAST PREALLOCATED TASK CONTROL INFO
`
`IMAGE TASK STACK
`IMAGE TASK CONTROL INFO
`
`TASK N STACK
`
`TASK N CONTROL INFO
`
`MAIN TASK STACK
`
`MAIN TASK CONTROL INFO
`
`KERNEL, EXECUTIVE AND SUPERVISOR
`STACK AREAS , COMMAND
`INTERPRETER ETC.
`
`OPERATING SYSTEM
`
`Inl4
`
`IHS
`
`22
`
`1124
`
`1132
`
`1134
`
`i142
`
`144
`
`147
`
`1152
`
`
`
`
`
`
`ll2
`
`
`
`
`
`
`
`
`
`
`
`
`
`(SO)CONTROL(PI).REGION—————A____-7.PROGRAM(PO)REGION
`
`
`
`
`
`
`
`
`
`
`
`SYSTEMREGION
`
`

`

`U.S. Patent Aug. 4, 1987
`
`Sheet 10 of 16 4,685,125
`
`
`
`OSblSYSWLAYVIISENS
`
`
`
`SASENSSASNSSASEAS92¢l
`sASanS|~~——7]SASans
`£YSVLéYSVL|YSVL
`NWS,fobYSVL
`
`
`2pbltolNCoptSVLNIVH
`
`
`gbI9b!WAISASANS)1d1¥0S-NOILWZITVILINENOU
`
`
`YSVIyw|UIOVNYNSS300NdT1V9
`
`ONT1IaN3ISIech
`USOVNVN24]
`Tinvs302H
`el
`YSVLLov
`
`
`NOILVIYDSS3I00UdOVSY
`JOUNOSIYSUSVLTWNOIS1501aONVY3OVNYW
`
`
`
`
`JQOWYAdNSIYV7030
`
`SS300UdSLVNINYSL
`
`SAdALYSVLINIIIO
`Linvdadvadflbl
`
`{Ibl
`
`UIHOLYASIOUSVI
`
`ashi
`
`JOUNOSJY
`
`
`
`JONYHOaNW19a0
`
`
`
`YFTGNVHICON
`
`élbl
`
`GGb!
`
`gcol
`
`
`
`ANINYILIG:ONIULS
`
`
`
`YJOVNYWSSIO0Ud
`
`Sco
`
`
`
`YATONVHLIX3
`
`
`
`(3LVIN)SNSVL
`
`a7
`
`Schl
`
`NOULYZITVILINI
`
`b/Od
`
`SSIV0Ud_HSIMAVLSS
`
`JOONYAdASNI
`
`
`
`TWNUSINTAZETVILINI
`
`
`
`JYNLONYLSAYOWSA
`
`JINGSHOSGNY31V3YO
`
`YSVLNIVA
`
`YSHOLVdSIOLdwnr
`
` EMER
`ERDICE
`8!Od
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`Sa
`
`
`
`
`
`:FINLUSENSONYgeala--i|1X3INO9Yash2261©OSGIJYOLS
`3ALLINId|Wal:=.
`
`
`
`
`
`
`atltnonmanLXGINODY3SN1353000JALLIWINdINILNOYNUNLIY!20000SALLI
`
`~IMILNOYNYNLIYASVTIVONuALIYLSY02S1JNILNOYJIVALLOY|ONi2s1~~tHSt|NYALSY
`
`
`
`
`nunau7NunLu>|6261Tuws92styOVIS_NO
`in-N|ar
`44sn~~-_9ONIOIANSSSV-.w
`
`
`
`AldWaos7|ObSIanano.4444NgINLLNOY4344N8
`
`
`‘[Ys¥i
`;
`
` 061:GNSdSNS|ageYOuISWasiJIWAW
`
`
`
`C6GIlOGl¥SVLovatJZIGtP|lISI2061
`
`-a|NarOclaame
`SINIARWSNchKISHIaid
`
`;seTWLLINTJIWHINI9
`II0IGIDd
`
`JOHHAaSNIYOVLWIWILJ1VI00
`
`
`
`
`
`
`U.S. Patent Aug. 4, 1987
`
`0961
`
`
`
`
`
`SVLNIVASLVAILOV
`
`
`
`WsHolvasiaSV
`
`3VYINIO8061
`
`resi0G)
`
`S¥SWLAIVOOTIWAud
`
`
`
`LXGINOOJUVAQUVE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent Aug. 4, 1987
`
`Sheet 12 of 16 4,685,125
`
`069]aNLIXd
`
`NYALSYSS8191
`oS9I£G9lI1149S
`
`12091
`21919191
`Cangasns._—
`
`
`WSVLONITTIGJLVALLOV
`
`ONY_NSISIT3LV340
`-WVNO0UddV
`EDNNY
`JOVIO4t03dS
`
`SUS¥LONITTIE
`
`T1404JOVI
`-$5I00Nd_d¥N
`_t)=
`
`Ocbl
`
`
`
`1091Na9¥NVWN
`
`SSF00d
`
`YIHOLVdSIG YS¥L
`
`—™ld
`
`ww
`
`Trey
`
`i|
`
`
`
`'1(29h
`
`
`
`
`
`
`

`

`U.S. Patent Aug, 4, 1987
`
`Sheet 13 of 16 4,685,125
`
`
`
` NoILNO3x3ICONYash7ZlOld
`
`
`
`
`
`JOVATD1419IdS-SSIIOUd40NOILNOIXA
`
`
`
`
`
`4Q_NOWNOAXS
`
`
`
`4000INILNOYENS
`
`NaNLay
`
`Gail
`
`JQOWJONVHO
`
`YAdASOL
`
`
`
`
`
`INILNONANSO92!(JAILINTYd)
`
`
`
`
`
`ANILNOYYOLDIA
`
`NO1LN03X3AHAdNS
`3L714H09Is300H
`
`TW;
`
`
`
`OG/I3NILNOUaNS
`
`
`
`FNILNOYHOLDIA
`
`YOLOJATI)
`
`INILAOY
`
`
`
`WAISASONLLVY4d0
`
`OLJGOWSIONVHO
`
`
`ISYSTIVO-YAdNS
`SNILNOYFOIAYSS
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent Aug. 4, 1987
`
`Sheet 14 of 16 4,685,125
`
`FIG. 19
`
`190!
`
`SET DISPATCHER FLAG
`
`
`1902
`
`
`INCOMING BUFFER
`QUEUE EMPTY
` PRIORITY LEVEL
`
`NON - EMPTY
`
`1903 -
`ACTIVATE BUFFER TASK
`
`
`
`
`
`HYBERNATE PROCESS
`
`1912
`CLEAR BIT IN EMPTY
`QUEUE INDICATOR
`
`NON- EMPTY
`
`YES
`
`SINGLE
`TASK IN
`HIGHEST - PRIORITY
`
`YES
`
`StI
`
`914
`
`CLEAR ACTIVATION REQUEST BIT
`OF FIRST TASK IN QUEUE
`
`1916
`
`1922
`
`CLEAR DISPATCHER FLAG
`
`STORE TASK ID; TCB AND
`CONTROL AREA LOCATIONS
`
`1925
`
`LOAD STACK AND FRAME
`POINTER REGISTERS
`
`1926
`
`REI
`
`

`

`U.S. Patent Aug 4, 1987
`
`Sheet 15 of16 4,685,125
`
`FIG. 20
`
`FROM
`STEP
`1532
`
`,
`
`CHECKS
`OK
`1533
`
`2021.
`
`NO
`
`PRIMITIVE
`INDEX
`YES
`
`/
`
`2023
`
`OBTAIN RETURN LOCATION
`FOR ERROR MESSAGE
`
`‘
`
`.
`
`
`
`
`2022
`TERMINATE
`PROCESS
`
`‘
`
`NO
`
`:
`
`T0
`STEP
`1534
`NO
`
`2026
`
`2031
`
`2033
`
`2038
`
`ARGUMENT
`LIST READABLE
`
`THAN
`256 ARGUMENTS
`
`ib
`
`MBER OF
`ARGUMENTS COREG
`
` PROTECTION
`
`2041
`
`‘
`
`\
`
`CHECKS OK
`
`YES
`
`YES
`
`TO STEP
`1536
`
`

`

`U.S. Patent Aug, 4, 1987
`FIG. 2/
`
`Sheet 16 of 16 4,685,125
`
`ENTRY VECTOR 1002
`
`
`<fyas(o0d000¢0)Ye 00000000 >
`RET
`
`<ENTRY MASK FOR PRIMITIVE 00000001 >
`CHMS (00000001 )
`RET
`
`Ss
`
`VECTOR
`L-ROUTINES
`2tl0
`
`
`PBS ADDR FOR PRIMITIVE 00000000
`PBS ADDR FOR PRIMITIVE 00000001
`
`PROTECTION BYTE
`STREAM (PBS)
`POINTERS 2120
`
`
`
`
`
`
`UNITS 2140iBILLING
`
`
`
`
` <PRIVILEGE MASK FOR PRIMITIVE 00000000>
`
`<PRIVILEGE MASK FOR PRIMITIVE 00000001>
`
`
`
`< BILLING UNITS FOR PRIMITIVE 00000000>
`< BILLING UNITS FOR PRIMITIVE 00000001>
`
`
`
`<ADDR FOR PRIMITIVE 00000000 >
`
`
`
`< ADDR FOR PRIMITIVE 00000001 >
`
`
`PRIMITIVE
`ADDRESSES
`2150
`
`

`

`1
`
`4,685,125
`
`COMPUTER SYSTEM WITH TASKING
`
`BACKGROUND OF THE INVENTION
`
`Thepresent invention relates to data communication
`and -processing systems. In such systems,
`it
`is often
`useful to structure the program code executing within a
`process into so-called “tasks.” A task is a software en-
`tity having an associated body of program code which
`is executed whenever program control within the pro-
`cess is vested in that task. As execution within the pro-
`cess proceeds, program control, i.e., control of the com-
`puter, passes among the various tasks and whenever
`program control passes from a task,its so-called “con-
`text”—which defines the execution state of the task at
`that moment—is saved. Thus each task within a process
`comprises an “independent thread of control” whose
`execution can be resumed at any time by restoringits
`context to the central processing unit (CPU) of the
`computer.
`The order in which the tasks execute may be con-
`trolled, for example, by scheduling those of the tasks
`which are “runnable,”i.e., ready to run, at any given
`time in accordance with priorities preassigned to the
`tasks. Whenevera taskis “activated,” i.e., made runna-
`ble, it is placed in a queue associated with its priority
`level, and whenever execution ofthe currently running
`task,i.e., the one having program control, is suspended,
`control is passed—illustratively by a so-called task dis-
`patcher—tothefirst task in the nonempty queue having
`the highest priority.
`Amongthe advantagesof having a tasking capability
`is that it allows a software system to be designed with a
`great degree of modularity and permits the various
`functions performed within the system to be executed
`quite independently of one another. In particular, task-
`ing greatly simplifies program design and coding be-
`cause changes can be madein one part of a software
`system with little, if any effect, on any other part and
`because execution of the various functions to be per-
`formed is only required to be synchronized at specific
`points specified by the programmer. These are impor-
`tant considerations in the design of large software sys-
`tems.
`A further advantage oftasking is that a process does
`not necessarily have to suspend its execution when a
`particular activity within the process must be suspended
`to, for example, wait for an I/O or other operation to be
`completed. Rather, the process can suspend the particu-
`lar task that needs to wait for that operation and then
`continue executing by picking up the thread, ie., con-
`tinuing execution, of any one or more tasks that are then
`runnable. This approach not only speeds up program
`execution within the process, but helps to minimize the
`frequency with which control of the CPU is switched
`from one processto the next, whichis a time-consuming
`operation. Indeed, tasking is particularly advantageous
`in data communication-oriented systems because such
`systems engendera substantial numberof I/O and other
`wait-inducing operations.
`Thepresent invention is particularly useful in systems
`in which system-supplied software, structured into
`tasks, provides various services to the user soft-
`ware—hereinafter referred to as the process-specific
`image—via,
`for example, user-callable routines, or
`“primitives.” In such arrangements, it is desirable to
`have a way of integrating execution of the process-
`specific image with that of the system-supplied soft-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`30
`
`55
`
`65
`
`2
`ware.It is, for example, desirable to have a convenient
`mechanism for synchronizing the two. It is also desir-
`able for the system-supplied software to be able to take
`control of a process away from the process-specific
`image when it needs to, ¢.g., to expeditiously provide
`services which the process-specific image has
`re-
`quested.
`
`SUMMARYOF THE INVENTION
`
`In accordance with the invention, processes in a sys-
`tem of the above-described type include not only tasks
`which provide various services to the process-specific
`image by, for example, manipulating data associated
`with the image,butalso at least one task—referred to as
`the “image task” which manages executionof the proc-
`ess-specific image. In particular, the image task controls
`the vesting of program control in the process-specific
`image andit is via the image task that program control
`returns to the system-supplied software from the proc-
`ess-specific image. This approach advantageously pro-
`vides the above-mentioned integration in that execution
`of the process-specific image and execution of the sys-
`tem-supplied data communication and/or processing
`software are each controlied by tasks executing in a
`commontasking environment.
`In accordance with a feature of the invention, pro-
`gram control is temporarily taken from the process-
`specific image and vested in the image task wheneverat
`least particular tasks within the system-supplied soft-
`ware are activated as the result of an action of the proc-
`ess-specific image. A typical such action is the calling of
`a primitive that activates a task. This approach is advan-
`tageousin that, for example, it is guaranteed that before
`control is returned to the process-specific image, the
`image task can issue a so-called task break which gives
`all then-active tasks which have a higher priority than
`the image task an immediate opportunity to run. (The
`image task has the lowest priority of any task in the
`embodiment described herein so that all tasks activated
`as a result of an action of the process-specific image will
`run before control returns to the image task and thus to
`the process-specific image.) This feature of the inven-
`tion ensures, for example, that services requested by the
`process-specific image, e.g., via a primitive call, are
`provided expeditiously.
`In accordance with a furtherfeature ofthe invention,
`program control
`is taken from the process-specific
`image and vested in the image task wheneverthe proc-
`ess-specific image calls at least those primitives whose
`execution may make a task runnable. Such “task-
`activating” primitives thus execute in the image task
`rather than in the process-specific image. (Indeed, pro-
`gram control is vested in the image task in the embodi-
`ment described herein whenever the process-specific
`imagecalls any primitive.) This feature of the invention
`provides, for example, an advantageous way of syn-
`chronizing the execution of the process-specific image
`with the execution of primitive-activated tasks, as will
`be seen.
`In addition to primitives, various AST (interrupt)
`service routines may also activate tasks and, in accor-
`dance with a further feature of the invention, program
`control is vested in the imagetask nolater than the end
`of execution of any such routine, i.e., before program
`control is returned to the process-specific image. Thus
`any tasks made runnable by an ASTservice routine are,
`
`

`

`4,685,125
`
`4
`
`3
`again, assured of an immediate opportunity to run via an
`image-task-issued task break.
`The image task and the various aspects and features
`ofthe invention are described, for example, beginning in
`Sec. III.A.5 of the Detailed Description.
`BRIEF DESCRIPTION OF THE DRAWING
`
`In the drawing,
`FIG. 1 is a block diagram of a system in which the
`presenti invention is used;
`FIG. 2 is a block diagram of a node within the system
`of FIG. 1;
`FIG. 3 is a block diagram of a node processor within
`the node of FIG. 2;
`:
`FIG.4, presented as a pedagogicaid, is a block dia-
`gram of a typical multiprogrammed computer;
`FIG.5, presented as a pedagogic aid,illustrates the
`concept of virtual address space;
`FIG. 6, presented as a pedagogic aid,illustrates the
`hardware mechanism via which a virtual memory sys-
`tem is realized in a computer;
`FIG.7, presented as a pedagogicaid, showsthe three
`states in which processes within a multiprogrammed
`computer can exist;
`FIG.8, presented as a pedagogic aid, depicts a sym-
`bol used to represent a process within a virtual memory
`computer;
`_ “FIG. 9 depicts the virtual address spaces of so-called
`application and control
`layer processes which exist
`within the node processor;
`FIGS. 10 and 11, when arranged with the latter
`below the former, comprise a memory mapofan indi-
`vidual one of the virtual address spaces depicted in
`FIG.9;
`FIG.12 depicts tasks scheduling queues employed in
`a tasking system which operates within each process;
`FIG. 13 depicts a data structure, referred to as a task
`control block, which is used by the tasking system;
`FIGS. 14-17, when arranged as shown in FIG. 18,
`-depict the execution flow of an application process;
`FIG.19 is a flowchart depicting the execution flow of
`the task dispatcher shown in FIGS.14-16,
`FIG.20 is a flowchart depicting the execution flow of
`the primitive check step within the change mode han-
`dler shownin FIG. 18; and
`FIG. 21 is a memory mapofthe entry vector shown
`in FIG. 10.
`
`DETAILED DESCRIPTION
`
`TABLE OF CONTENTS
`
`I. SYSTEM HARDWARE
`A. Hardware Architecture
`1. System
`2. Node
`3. Processor
`B. Virtual Memory
`1, The Virtual Memory Space
`2. The Hardware Mechanism
`Il. SYSTEM SOFTWARE—ARCHITECTURE
`A. Processes
`1. The Process Concept
`2. Application and Control Layer Processes
`B. The Shared Image
`1. Processing Services & Subsystems; Primitives
`2. Primitive Calls; Subroutines
`3. Supervisor Services
`4. Overview of Shared Image Software Structure
`
`5
`
`10
`
`25
`
`wOQ
`
`35
`
`C. Tasking
`1. An Introduction
`2. Task Synchronization
`3. Task Control Blocks
`D. Processor Access Modes/Stack Areas
`Ill. SYSTEM SOFTWARE—EXECUTION FLOW
`A. Application Processes
`. Process Creation Scenario
`. Initial Execution
`. Main Task
`. Process Manager
`. Invention: The Image Task
`. Execution of Process-Specific Image
`. Process Termination
`B. Control Layer Processes
`C. Task Dispatcher
`D. Change Mode Handler
`IV. DETAILS OF SUPERVISOR SOFTWARE
`STRUCTURE
`
`SAUPWN
`
`1. SYSTEM HARDWARE
`
`I.A.1 Hardware Architecture—System
`FIG. 1 depicts a system which provides an integrated
`data processing and communications service (hereinaf-
`ter referred to as the “communications service” or,
`simply, the “service’’) to a plurality of customers. The
`system includes a numberof nodes 10 which are located
`on the premises of the vendor of the service. At the
`heart of each nodeare one or moredigital computers as
`described below (Sec. I.A.2). A plurality of data termi-
`nals 10¢ and host computers, or hosts, 105 are con-
`nected to nodes 10 via suitable data lines. Most of the
`terminals and hosts belong to the customers and are
`located on their premises. Some, however, belong to
`the vendor and are used, for example, for system man-
`agement. Nodes 10 communicate with each other via a
`packet switched transport network 15. The nodes are
`connected to the network via respective links 11 which
`carry data at 56 kb/s using a protocol which conforms
`to CCITT standard X.25. Various ones of the nodes
`may be dedicated to specific functions, such asbilling,
`service provisioning, maintenance, etc.
`The communications service provides the customers
`with a number of capabilities. These include time-
`shared execution of customer- and vendor-provided
`application programs stored within the nodes; storage
`of customer data in databases maintained within the
`nodes; support of customer-program-callable software
`“building blocks” that provide such services as editing,
`command interpreting, formsfacilities, and the like; a
`distributed processing capability wherein processes
`executing at various nodes can communicate on a time-
`critical basis with processes executing at other nodes;
`and a store-and-forward message service.
`LA.2 Hardware Architecture—Node
`
`60
`
`65
`
`FIG. 2 is a block diagram of an individual one of
`nodes 10. The node illustratively includes two node
`processors 20 and a database processor 26. Each of
`these processors is illustratively a Digital Equipment
`Corporation (DEC) VAX 11/780 computer running
`under
`the DEC-supplied VMS operating system.
`(DEC, VAX and VMSare trademarks of Digital
`Equipment Corporation.) The node further includes a
`spare VAX 11/780 processor 28 which can take the
`placeofeither the database processor orone of the node
`processors. Other ones of nodes 10 (FIG. 1) may have
`
`

`

`4,685,125
`
`3
`
`20
`
`25
`
`30
`
`35
`
`5
`6
`fewer or more than two nodeprocessors, depending on
`ing a CPU 41 and main memory 44. Three executable
`the anticipated processing demand. Communication
`machine language programs, or “images,” are shown as
`among the processorsis carried out via bus 25, which
`being resident in the image region of the main memory.
`illustratively is a DEC-supplied PCL (parallel commu-
`Program statements and data must be resident in main
`nication link) bus.
`memory in order to be acted on by CPU 41, and only
`Massstorage, e.g., disk, units 21 are associated with
`one image can actually be executed at any given time in
`each node processor and mass storage units 27 are asso-
`a computer which,like computer 40,has a single CPU.
`ciated with database processor 26. Mass storage units 27
`However, by having more than one imageresident in
`are dual ported with, and thus can be accessed by, spare
`main memory, another image is immediately available
`processor 28. Associated with each of the four proces-
`if, for example, the one that is currently running must
`sors are general purpose input/output (I/O), e.g., CRT,
`go into a “wait” state pending the occurrence of some
`terminal devices 29.
`“event,” such as the completion of an input/output
`Also associated with each node processoris at least
`(I/O) operation.
`one front-end processor 22 which provides an interface
`Memory 44 also has a data/control region andasys-
`15
`between the node processor, on the one hand,and asso-
`tem region. Within the former is a data/control area
`ciated ones of terminals 10a and hosts 10, on the other
`associated with each image in which are stored (a) data
`hand. Front-end processors 22 are, illustratively, IBM
`generated and used by the image and (b) stacks built
`Series/1 computers running under the IBM-supplied
`during its execution. The system region contains the
`RPS operating system. Each front-end processor com-
`operating system—an ensemble of machine language
`municates with its respective node processor using an
`code and data that provides (a) system management
`X.25 protocol. DEC-supplied firmware controlling a
`functions such as the scheduling and allocation of CPU
`DEC-supplied microprocessor 23 performs the DTE
`time among the various images and (b) so-called “sys-
`tem services” such as I/O services.
`role in Level 2 (the “link” level) of the protocol. An-
`other microprocessor 24 associated with each node
`The memory layout of memory 44 is typical of so-
`processorserves a similar function with respect to X.25
`called non-virtual memory storage systems in that the
`communications over link 11.
`entirety of each image and its data are stored in the
`The function of node processors 20 is to execute
`computer main memory and addresses referenced dur-
`programson behalf of the customers and the vendor. To
`ing execution of the imageare the physical addresses of
`this end, the mass storage units 21 associated with each
`storage located within the memory. By contrast, pro-
`processor are used primarily, if not exclusively, to sup-
`cessors 20, as previously noted, are virtual memory
`port the processing currently going on in that proces-
`machines. In a virtual memory system, main memory
`sor. Virtually all data, programs and otherfiles, both
`and auxiliary, e.g., disk, storage are combined to give
`those belonging to the customerand those belonging to
`the programmerthe illusion that the main memory is
`the vendor, are stored in a database contained within
`vastly larger than it actually is and that this so-called
`mass storage devices 27. The function ofthe latter is to
`“virtual” memory space is occupied by that program-
`manage the database andto provide the node processors
`mer’s image(s), the associated data and control—princi-
`with access to it.
`pally stack—information and the operating system. The
`way in whichthis illusion is effected will now be ex-
`plained.
`In a virtual memory system, a so-called virtual mem-
`ory space is associated with each image. FIG. 5, for
`example, depicts three virtual address spaces A, B, and
`C associated with respective images A, B and C. The
`virtual address space associated with an image is the
`array of storage locations which appearto be available
`in main memory. Each virtual storage location within a
`virtual address space has an associated 32-bit (8-hex-
`adecimal-digit) address. These are the addresses which
`are referenced by the image and manipulated by the
`CPU when the imageis executing. Note that the same
`virtual addresses refer to corresponding locations in
`each virtual address space.
`Each virtual address space is divided into program,
`control and system regions. The program region con-
`tains the image and its data and begins at the virtual
`storage
`location whose hexadecimal
`address
`is
`00000000. The control region starts at address 40000000
`and contains the control information associated with the
`image. The system region starts at 80000000 and con-
`tains the operating system.
`
`1A.3 Hardware Architecture—Processor
`
`FIG.3 is a block diagram ofan individual one of node
`processors 20: (Processors 20, 26 and 28 are substan-
`“> tially identical to one another. Thus, although the fol-
`lowing discussion focuses on node processors 20,
`it
`should be understood to apply to processors 26 and 28
`as well.)
`At the heart of processor 20 is its central processing
`unit (CPU) 31, which communicates over a high-speed
`synchronous bus 32 with main memory 34 via memory
`controller 33; with mass storage units 21 via bus adapter
`35 and bus 36; and with general purpose I/O devices 29
`via bus adapter 37 and bus 38. Processor 20 also in-
`cludes a console subsystem 37 which illustratively com-
`prises an operator’s console terminal, a microcomputer
`and a floppy disk unit. This subsystem serves as the
`operator interface with the processor and enables the
`operator to monitor the processor and controlit.
`Nodeprocessors 20 are virtual memory processors.
`An understanding of the concept ofvirtual memory will
`facilitate an understanding of the remainder of this de-
`tailed description. Accordingly, this concept will now
`be reviewed.
`
`40
`
`45
`
`60
`
`L.B.1 Virtual Memory—The Virtual Memory Space
`Webegin with a review of the concept of multipro-
`gramming. A multiprogrammed computer is one in
`which more than one program is stored, or “resident,”
`in the computer main memory at any one time. This is
`illustrated in FIG. 4, which depicts a computer 40 hav-
`
`65
`
`1.B.2 Virtual Memory—The Hardware Mechanism
`As shown in FIG.6, each virtual address spaceis
`divided into contiguous-byte segments referred to as
`pages. Illustratively, each page contains 512 bytes. The
`first six pages of address spaces A, B and C, denoted
`A}-Ag6, Bi-Bg and C;-C¢, respectively, are explicitly
`shownin FIG. 6. (All of these are, of course, program
`
`

`

`4,685,125
`
`7
`region pages.) The physical (as opposedto virtual) main
`memory of the computer,indicatedat 64,is also divided
`into 512-byte segments, referred to as page frames. Aux-
`iliary storage,
`indicated at 65,
`is also organized into
`512-byte segments, referred to as blocks. At any given
`time, only some of the pages of any given virtual ad-
`dress spaceare actually stored in physical memory. The
`rest of the virtual pages are held in auxiliary storage. A
`mapping mechanism within the computer, indicated at
`63, maintains so-called page tables for each address
`space via whichit keeps tracks of whether anyparticu-
`lar page is resident in main memoryor,alternatively, in
`auxiliary storage.
`Whena particularvirtual location is to be accessed by
`the CPU, the mapping mechanism determines whether
`the byte stored in the addressed virtual location (or,
`more accurately, the page which contains that byte) is
`then resident in physical main memory. Ifit is, the map-
`ping mechanism translates the virtual address of that
`location into the physical address of the main memory
`location where the byte is stored. That location is then
`accessed by the CPU and processing continues.
`If, on the other hand, the addressed byte is deter-
`mined to be in auxiliary storage, a so-called page fault
`occurs. This activates a paging mechanism,indicated at
`66, which causes the page containing that byte to be
`read, or “faulted” into main memory.(This is necessary
`because, as previously noted, only information in main
`. memory can be directly manipulated by the CPU.)
`_. Since the mapping mechanism essentially involves a
`’
`table look-up function, new pages faulted into main
`memorycanbeplaced in any available page frame. The
`process (defined below Sec. II.A.1) in which the image
`is executing can take up only so many page frames,
`referred to as the working set limit. If that limit has
`already been reached when a new pageis to be faulted
`into the workingset, the process mustrelinquish one of
`its pages—illustratively the one that wasleast-recently
`referenced. CPU processing resumes once the desired
`page has been faulted into main memory.
`» Advantageously, pages in different virtual memory
`spaces are readily mapped by the mapping mechanism
`to the same page frame in main memory at the same
`time,
`thus allowing the “sharing” of physical pages.
`Thus as seen in FIG. 6, pages Al, Bl and Cl areresi-
`dent in main memoryand share a page frame; the same
`is true for pages A2, B2 and C2. Other pages stored in
`main memory are pages A6, C3, C4 and C5. All other
`pagesare stored in auxiliary storage 65. Page sharing is
`used in the present system for the so-called “shared
`image” (Sec. II.B).
`There are several disadvantages to virtual memory
`system. Theserelate, principally, to the overhead atten-
`dantto its utilization and to the phenomenon knownas
`“thrashing”. In general, however, the disadvantages of
`virtual memory are greatly outweighed by the advan-
`tages. These include moreefficient use of main memory;
`the ability to easily accommodate large programs; the
`insulation of users from one another (resulting from the
`fact that each image has its own virtual address space);
`and the ease with which virtual memory space can be
`allocated.
`
`20
`
`55
`
`Il. SYSTEM SOFTWARE—ARCHITECTURE
`
`ILA.1 Processes—The Process Concept
`Webegin our discussion of the system software archi-
`tecture with the concept of a “process.” A processis the
`total environment in which an image executes and has
`
`65
`
`8
`three components: a virtual memory space, as already
`discussed, a software context and a hardware context.
`The software context includes such pieces of informa-
`tion as priorities and privileges allo