Movatterモバイル変換
[0]ホーム
[RFC Home] [TEXT|PDF|HTML] [Tracker] [IPR] [Info page]
UNKNOWN
Network Working Group James E. WhiteRequest for Comments: 708 Augmentation Research Center Elements of a Distributed Programming System January 5, 1976James E. WhiteAugmentation Research Center Stanford Research Institute Menlo Park, California 94025 (415) 326-6200 X2960This paper suggests some extensions to the simple Procedure Call Protocoldescribed in a previous paper (27197). By expanding the procedure callmodel and standardizing other common forms of inter-process interaction,such extensions would provide the applications programmer with an evenmore powerful distributed programming system.The work reported here was supported by the Advanced Research ProjectsAgency of the Department of Defense, and by the Rome Air DevelopmentCenter of the Air Force.This paper will be submitted to publication in the Journal of ComputerLanguages.
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System INTRODUCTIONIn a companion paper [i], the author proposes a simple protocol andsoftware framework that would facilitate the construction of distributedsystems within a resource-sharing computer network by enabling distantprocesses to communicate with one another at the procedure call level.Although of great utility even in its present form, this rudimentary"distributed programming system (DPS)" supports only the most fundamentalaspects of remote procedure calling. In particular, it permits thecaller to identify the remote procedure to be called, supply thenecessary arguments, determine the outcome of the procedure, and recoverits results. The present paper extends this simple procedure call modeland standardizes other common forms of process interaction to providea more powerful and comprehensive distributed programming system. Theparticular extensions proposed in this paper serve hopefully to reveal theDPS concept's potential, and are offered not as dogma but rather asstimulus for further research.The first section of this paper summarizes the basic distributedprogramming system derived in [1]. The second section describes thegeneral strategy to be followed in extending it. The third and longestsection identifies and explores some of the aspects of process interactionthat are sufficiently common to warrant standardization, and suggestsmethods for incorporating them in the DPS model. REVIEWING THE BASIC SYSTEMThe distributed programming system derived in [1] assumes the existenceof and is built upon a network-wide "inter-process communication (IPC)"facility. As depicted in Figure 1, DPS consists of a high-level model ofcomputer processes and a simple, application-independent "procedurecall protocol (PCP)" that implements the model by regulating the dialogbetween two processes interconnected by means of an IPC communication"channel." DPS is implemented by an installation-provided "run-timeenvironment (RTE)," which is link loaded with (or otherwise madeavailable to) each applications program. -1-
Network Working Group James E. WhiteRequests for Comments: 708 Elements of a Distributed Programming System Reviewing the Basic SystemThe ModelThe procedure call model (hereafter termed the Model) views a process as acollection of remotely callable subroutines or "procedures." Each procedureis invoked by name, can be supplied a list of arguments, and returns to itscaller both a boolean outcome, indicating whether it succeeded or failed,and a list of results. The Model permits the process at either end of theIPC channel to invoke procedures in its neighbor, and further permits aprocess to accept two or more procedure calls for concurrent execution.The arguments and results of procedures are modeled from a small set ofprimitive "data types," listed below: LIST: A list is an ordered sequence of N data objects called "elements" (here and throughout these descriptions, N is confined to the range [0, 2**15-1]). A LIST may contain other LISTs as elements, and can therefore be employed to construct arbitrarily complex, composite arguments or results. CHARSTR: A character string is an ordered sequence of N ASCII characters, and conveniently models a variety of textual entities, from short user names to whole paragraphs of text. BITSTR: A bit string is an ordered sequence of N bits and, therefore, provides a means for representing arbitrary binary data (for example, the contents of a word of memory). INTEGER: An integer is a fixed-point number in the range [-2**31, 2**31-1], and conveniently models various kinds of numerical data, including time intervals, distances, and so on. INDEX: An index is an integer in the range [1, 2**15-1]. As its name and value range suggest, an INDEX can be used to address a particular bit of character within a string, or element within a list. Furthermore, many of the protocol extensions to be proposed in this paper will employ INDEXES as handles for objects within the DPS environment (for example, processes and channels). BOOLEAN: A boolean represents a single bit of information and has either the value true or false. EMPTY: An empty is a valueless place holder within a LIST of parameter list. -2-
Network Working Group James E. WhiteRequests for Comments: 708 Elements of a Distributed Programming System Reviewing the Basic SystemThe ProtocolThe procedure call protocol (hereafter terms the Protocol), whichimplements the Model, defines a "transmission format" (like those suggestedinAppendix A) for each of the seven data types listed above, andrequires that parameters be encoded in that format whenever they aretransported between processes.The Protocol also specified the inter-process messages by which remoteprocedures are invoked. These messages can be described symbolically asfollows: message-type=CALL [tid] procedure-name arguments message-type=RETURN tid outcome resultsThe first message invokes the procedure whose NAME is specified using theARGUMENTS provided. The second is returned in eventual response to thefirst and reports the OUTCOME and RESULTS of the completed procedure.Whenever OUTCOME indicates that a procedure has failed, the procedure'sRESULTS are required to be an error number and diagnostic message, theformer to help the invoking program determine what to do next, thelatter for possible presentation to the user. The presence of anoptional "transaction identifier (TID)" in the CALL message constitutesa request by the caller for an acknowledging RETURN message echoing theidentifier.Although data types and their transmission formats serve primarily asvehicles for representing the arguments and results of remote procedures,they can just as readily and effectively be employed to represent themessages by which those parameters are transmitted. The Protocol,therefore, represents each of the two messages described above as a PCPdata object, namely, a LIST whose first element is an INDEX messagetype. The following concise statement of the Protocol results: LIST (CALL, tid, procedure, arguments) INDEX=1 [INDEX] CHARSTR LIST LIST (RETURN, tid, outcome, results) INDEX=2 INDEX BOOLEAN LISTHere and in subsequent protocol descriptions, elements enclosed in squarebrackets are optional (that is, may be EMPTY). The RESULTS of anunsuccessful procedure would be represented as follows: LIST (error, diagnostic) INDEX CHARSTR -3-
Network Working Group James E. WhiteRequests for Comments: 708 Elements of a Distributed Programming System Reviewing the Basic SystemThe Run-Time EnvironmentThe run-time environment (hereafter termed the environment) interfaces theapplications program to a remote process via an IPC channel. In doing so,it provides the applications program with a collection of "primitives,"implemented either as subroutines or system calls, that the applicationsprogram can employ to manipulate the remote process to which the channelconnects it. The environment implements these primitives by sendingand receiving various protocol messages via the channel.In its present rudimentary form, the Protocol enables the environment tomake a single, remote procedure calling primitive like the followingavailable to the applications program: CALLPROCEDURE (procedure, arguments -> outcome, results) CHARSTR LIST BOOLEAN LISTThis primitive invokes the indicated remote PROCEDURE using the ARGUMENTSprovided and returns its OUTCOME and RESULTS. While this primitiveblocks the invoking applications program until the remote procedurereturns, a variant that simply initiates the call and allows theapplications program to collect the outcome and results in a secondoperation can also be provided.Since the interface between the environment and the applications programis machine- and possibly even language-dependent, environment-providedprimitives can only be described in this paper symbolically. AlthoughPCP data types provide a convenient vehicle for describing theirarguments and results are therefore used for that purpose above andthroughout the paper, such parameters will normally be transmittedbetween the environment and the applications program in some internalformat. BOOTSTRAPPING THE NEW PROTOCOL FUNCTIONSSince the Protocol already provides a mechanism for invoking arbitraryremote procedures, the Model extensions to be proposed in this paperwill be implemented whenever possible as procedures, rather than asadditional messages. Unlike applications procedures, these special"system procedures" will be called and implemented by run-time environments,rather than by the applications programs they serve. Although inaccessibleto the remote applications program via the normal environment-providedremote procedure calling primitive, system procedures will enable theenvironment to implement and offer new primitives to its applicationsprogram. -4-
Network Working Group James E. WhiteRequests for Comments: 708 Elements of a Distributed Programming System Bootstrapping the New Protocol FunctionsThe calling sequences of many of these new primitives will closelycorrespond to those of the remote system procedures by which they areimplemented. Other primitives will be more complex and require for theirimplementation calls to several system procedures, possibly in differentprocesses. Besides describing the Protocol additions required by variousModel extensions proposed, the author will, throughout this paper, suggestcalling sequences for the new primitives that become available to theapplications program. -5-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model SOME POSSIBLE EXTENSIONS TO THE MODEL1. Creating Remote ProcessesBefore a program in one machine can use resources in another, it must eithercreate a new process in the remote machine, or gain access to an existingone. In either case, the local process must establish an IPC channel to aresident dispatching process within the remote system, specify the programto be started or contacted. and identify itself so that its access to theprogram can be established and billing carried out. After these preliminarysteps have been accomplished, the requested process assumes responsibilityfor the IPC channel and substantive communication begins.The manner in which the environment carries out the above scenario islargely dictated by the IPC facility upon which the distributed system isbased. If the IPC facility itself provides single primitive thataccomplishes the entire task, then the environment need only invoke thatprimitive. If, on the other hand, it only provides a mechanism by whichthe environment can establish a channel to the remote dispatcher, as isthe case within the ARPA computer Network (the ARPANET), then the Protocolitself must contain provisions for naming the program to be run andpresenting the required credential.Adding to the Protocol the following system procedure enables the localenvironment to provide the remote dispatcher with the necessary informationin this latter case: INIPROCESS (program, credential) CHARSTR LIST (user, password, account) CHARSTR CHARSTR CHARSTRIts arguments include the name of the applications PROGRAM to be run; andthe USER name, PASSWORD, and ACCOUNT of the local user to whom its use isto be billed.This new procedure effectively adds to the Model the notion of "creation," and enables the environment to offer the following primitivesto its applications program: CRTPROCESS (computer, program, credential -> ph) CHARSTR CHARSTR (as above) INDEX DELPROCESS (ph) INDEX -6-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Creating Remote ProcessesThe first primitive creates a new process or establishes contact with anexisting one by first creating a channel to the dispatcher within theindicated COMPUTER and then invoking the remote system procedure INIPROCESSwith the specified PROGRAM name and CREDENTIALS as arguments. The primitivereturns a "process handle PH" by which the applications program can refer tothe newly created process in subsequent dialog with the local environmentby the IPC facility, an index into a table within the environment, or anythingelse the environment's implementor may find convenient.The second primitive "deletes" the previously created process whose handlePH is specified by simply deleting the IPC channel to the remote process andreclaiming any internal table space that may have been allocated to theprocess.2. Introducing Processes to One AnotherThe simplest distributed systems begin with a single process that creates,via the CRTPROCESS primitive described above, one or more "inferior"processes whose resources it requires. Some or all of these inferiors mayin turn require other remote resources and so create interiors of theirown. This creative activity can proceed, in principle, to arbitrary depth.The distributed system is thus a tree structure whose nodes are processesand whose branches are IPC channels.Although a distributed system can include an arbitrarily large number ofprocesses, each process is cognizant of only the process that created itand those it itself creates, that is, its parent and sons. The radiuswithin which a process can access the resources of the tree is thusartificially small. This limited sharing range, which prevents theconvenient implementation of many distributed systems, can be overcomeby extending the Model to permit an arbitrarily complex network ofcommunication paths to be superimposed upon the process tree.One of the many ways by which the Protocol can provide for such communicationpaths is to permit one process to "introduce" and thereby make known to oneanother any two processes it itself knows (for example, two of its sons,or its parent and son). Once introduced, the two processes would be ableto invoke one another's procedures with the same freedom the introducingprocess enjoys. They could also introduce one another to other processes,and so create even longer communication paths. -7-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Introducing Processes to One Another2.1 Introductions Within a Homogeneous EnvironmentProvided one remains within a "homogeneous environment" (that is, the domainof a single IPC facility), the introduction of two processes requires littlemore than the formation of an IPC channel between them. Adding to theProtocol the following system procedures, which manipulate IPC "ports,"enables the run-time environment of the process performing the introductionto negotiate such a channel: ALOPORT (-> ph, COMPUTER, PORT) INDEX CHARSTR any CNNPORT (ph, computer, port) INDEX CHARSTR any DCNPORT (ph) INDEXThe detailed calling sequences for these procedures are dictated by the IPCfacility that underlies the distributed system. Those above are thereforeonly representative of what may be required within any particular network,but are only slightly less complicated than those required, for example,within the ARPANET.To create the channel, the introducing process' run-time environmentallocates a PORT in each target process via ALOPORT, and then instructseach process via CNNPORT to connect its port to the other's via the IPCfacility. The process handle PH returned by ALOPORT serves as a handleboth initially for the allocated port, and then later for the process towhich the attached channel provides access. To "separate" the two processes,the introducing process' environment need only invoke the DCNPORT procedurein each process, thereby dissolving the channel, releasing the associatedports, and deallocating the process handles.Armed with these three new system procedures, the environment can providethe following new primitives to its applications program: ITDPROCESS (ph1, ph2 -> ph12, PH21, ih) INDEX INDEX INDEX INDEX INDEX SEPPROCESS (ih) INDEX -8-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Introducing Process to One AnotherThe first primitive introduces the two processes whose handles PH1 and PH2are specified. Each handle may designate either a son, in which case thehandle is one returned by CRTPROCESS; the parent process, for which aspecial handle (for example, 1) must always be defined; or a previouslyintroduced process, in which case the handle is one obtained in a previousinvocation of ITDPROCESS.ITDPROCESS returns handles PH12 and PH21 by which the two processes willknow one another, as well as an "introduction handle IH" that the applicationsprogram can later employ to separate the two processes via SEPPROCESS. Theapplications program initiating the introduction assumes responsibility forcommunicating to each introduced applications program its handle for theother.2.2 Introductions Within a Heterogeneous EnvironmentWhile their interconnection via an IPC channel is sufficient to introducetwo processes to one another, in a heterogeneous environment the creationof such a channel is impossible. Suppose, as depicted in Figure 2, thatprocesses P1 and P2 (in computers C1 and C2, respectively) are interconnectedwithin a distributed system by means of a network IPC facility. Assumefurther that P2 attaches to the system another process P3 in a minicomputerM that although attached to C2 is not formally a part of the network. Withthis configuration, it is impossible for P2 to introduce processes P1 and P3to one another by simply establishing an IPC channel between them, sincethey are not within the domain of a single IPC facility.One way of overcoming this problem is to extend the Model to embrace thenotion of a composite or "logical channel" composed of two or more physical(that is, IPC) channels. A message transmitted by process P1 via the logicalchannel to Pn (n=3 in the example above) would be relayed over successivephysical channels by the environments of intermediate processes P2 throughPn-1. Although more expensive than physical channels, since each messagemust traverse at least two physical channels and be handled by all theenvironments along the way, logical channels would nevertheless enableprocesses that could not otherwise do so to access one another's resources.Since the relaying of messages is a responsibility of the environment, theapplications program need never be aware of it. -9-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Introducing Processes to One AnotherAs depicted in Figure 3, a logical channel would consist of table entriesmaintained by the environment of each process P1 through Pn, plus theenvironment to forward messages that arrive with a "routing code" addressingthe local table entry. Each table entry would contain process handles forthe two adjacent processes, as well as the routing code recognized by each.To communicate a message to its distant neighbor, the source process (sayP1) would transmit it via its IPC channel to P2, with a routing codeaddressing the appropriate table entry within P2. Upon receipt of themessage, P2 would locate its table entry via the routing code, update themessage with the routing code recognized by P3, and forward the messageto P3. Eventually the message would reach its final destination, Pn.Adding to the Protocol the following system procedures enables theenvironment to construct a logical channel like that described above: CRTROUTE (mycode, oldcode -> code, ph) INDEX [INDEX] INDEX INDEX DELROUTE (yourcode) INDEXThe simplest logical channel (n=3) is created by P2, which invokes CRTROUTEin both P1 and P3, specifying in each case the routing code MYCODE it hasassigned to its segment of the logical channel, and receiving in returnthe routing CODES and process handles PHs assigned by the two processes.OLDCODE is not required in this simple case and is therefore EMPTY.More complicated logical channels (n>3) are required when one or bothof the processes to be introduced is already linked, by a logical channel,to the process performing the introduction. In such cases, a portion ofthe new channel to be constructed must replicate the existing channel, andhence the routing code OLDCODE for the table entry that represents thatchannel within the target process is specified as an additional argumentof the system procedure. The target process must call CRTROUTE recursivelyin the adjacent process to replicate the rest of the model channel. -10-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Introducing Processes to One AnotherThe process Pi that creates a logical channel assumes responsibility forinsuring that it is eventually dismantled. It deletes the logical channelby invoking DELROUTE in Pi-1 and Pi+1, each of which propagates the calltoward its end of the channel.3. Controlling Access to Local ResourcesThe process introduction primitive proposed above effectively permitsaccess to a process to be transmitted from one process to another. Anyprocess P2 that already possesses a handle to a process P1 can obtain ahandle for use by a third process P3. Once P1 and P3 have been introduced,P3 can freely call procedures in P1 (and vice versa).Although a process can, by aborting the ALOPORT system procedure, preventits introduction to another process and so restrict the set of processesthat gain access to it, finer access controls may sometimes be required.A process may, for example, house two separate resources, one of whichis to be made available only to its parent (for example), and the otherto any process to which the parent introduces it. Before such a strategycan be conveniently implemented, the Model must be extended to permitaccess controls to be independently applied to individual resources withina single process.Although a single procedure can be considered a resource, it is more practical and convenient to conceive of larger, composite resourcesconsisting of a number of related procedures. A simple data basemanagement module containing procedures for creating, deleting, assigningvalues to, reading, and searching for data objects exemplifies suchcomposite resources. Although each procedure is useless in isolating, thewhole family of procedures provides a meaningful service. Such "package"of logically related procedures might thus be the most reasonable objectof the finer access controls to be defined.Access controls can be applied to packages by requiring that a processfirst "open" and obtain a handle for a remote package before it may callany of the procedures it contains. When the process attempts to openthe package, its right to do so can be verified and the attempt aborted ifnecessary. Challenging the open attempt would, of course, be less expensivethan challenging every procedure call. The opening of a package would alsoprovide a convenient time for package-dependent state information to beinitialized. -11-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Controlling Access to Local ResourcesAdding to the Protocol the following pair of system procedures enables theenvironment to open and close packages within another process. Forefficiency, these procedures manipulate an arbitrary number of packagesin a single transaction. OPNPACKAGE (packages -> pkhs) LISTofCHARSTRs LISTofINDEXs CLSPACKAGE (pkhs) (as above)The first procedure opens and returns "package handles PKHS" for thespecified PACKAGES; the second closes one or more packages and releasesthe handles PKHS previously obtained for them.Besides incorporating these two new system procedures, the Protocol mustfurther require that a package handle accompany the procedure name in everyCALL message (an EMPTY handle perhaps designating a system procedure). Notethat this requirement has the side effect of making the package the domainwithin which procedure names must be unique.The system procedures described above enable the environment to makeavailable to its applications program, primitives that have callingsequences similar to those of the corresponding system procedures butwhich accept the process handle of the target process as an additionalargument. Their implementation requires only that the environmentidentify the remote process from its internal tables and invoke OPNPACKAGEor CLSPACKAGE in that process.4. Standardizing Access to Global VariablesConventional systems often maintain global "variables" that can be accessedby modules throughout the system. Such variables are typically manipulatedusing primitives of the form: (1) Return the current value of V. (2) Replace the current contents of V with a new value.These primitives are either provided as language constructs or implementedby specialized procedures. The former approach encourages uniformtreatment of all variables within the system.Those distributed systems that maintain remotely-accessible variables mustalso select a strategy for implementing the required access primitives.While such primitives can, of course, be implemented as specialized -12-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Standardizing Access to Global Variablesapplications procedures, adding to the Protocol the following new systemprocedures insures a uniform run-time access mechanism: RDVARIABLE (pkh, variable -> value) INDEX CHARSTR any WRVARIABLE (pkh, variable, value) INDEX CHARSTR anyThese procedures effectively define variables as named data objects modeledfrom PCP data types, and suggest that they be clustered in packages withrelated procedures. The system procedures return and specify, respectively,the VALUE of the VARIABLE whose name and package handle PKH are specified.These new procedures enable the environment to make available its applicationsprogram, primitives that have calling sequences similar to those of thecorresponding system procedures but which accept the process handle of thetarget process as an additional argument. These primitives provide a basisupon which a suitably modified compiler can reestablish the compile-timeuniformity that characterizes the manipulation of variables in conventionalprogramming environments. Their implementation requires only that the localenvironment identify the remote process from its internal tables and invokeRDVARIABLE or WRVARIABLE in that process.Most variables will restrict the range of data types and values that may beassigned to them; some may even be read-only. But because they are modeledusing PCP data types, their values can, in principle, be arbitrarily complex(for example, a LIST of LISTS) and the programmer may sometimes wish tomanipulate only a single element of the variable (or, if the element isitself a LIST, just one of its elements; and so on, to arbitrary depth).Adding the following argument to their calling sequences extends the systemprocedures proposed above to optionally manipulate a single element of avariable's composite value: substructure (LISTofINDEXs)At successive levels of the value's tree structure, the INDEX of the desiredelement is identified; the resulting list of indices identifies theSUBSTRUCTURE whose value is to be returned or replaced. -13-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Routing Parameters Between Procedures5. Routing Parameters Between ProceduresIn conventional programming systems, the results of procedures are used in avariety of ways, depending upon the context of the calls made upon them. Aresult may, for example: (1) Provide the basis for a branch decision within the calling program. (2) Become an argument to a subsequent procedure call. (3) Be ignored and thus effectively discarded.At run-time, the knowledge of a result's intended use usually lies solelywithin the calling program, which examines the results, passes it to asecond procedure, or ignores it as it chooses.In a distributed system, the transportation of results from callee to caller,carried out by means of one of more inter-process messages, can be anexpensive operation, especially when the results are large. Data movementcan be reduced in Cases 2 and 3 above by extending the Model to permit theintended disposition of each procedure result to be made known in advanceto the callee's environment. In Case 2, provided both callees residewithin the same process, the result can be held at its source and laterlocally supplied to the next procedure. In Case 3, the result can bediscarded at its source (perhaps not even computed), rather than sent anddiscarded at its destination.5.1 Specifying Parameters IndirectlyVariables offer potential for the eliminating the inefficiencies involved inCase 2 above by providing a place within the callees' process where resultsgenerated by one procedure can be held until required by another. TheProtocol can be extended to permit variables to be used in this way byallowing the caller of any procedure to include optional "argument- andresult-list mask" like the following as additional parameters of the CALLmessage: parameter list mask [LIST variable, ...)] [CHARSTR]A parameter list mask would permit each parameter to be transmitted eitherdirectly, via the parameter list, or indirectly via a VARIABLE within thecallee's process. Thus each element of the mask specifies how the callee's -14-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Routing Parameters Between Proceduresenvironment is to obtain or dispose of the corresponding parameter. To supplythe result of one procedure as an argument to another, the caller need onlythen appropriately set corresponding elements of the result and argumentlist masks in the first and second calls, respectively. The result listmask should be ignored if the procedure fails, and the error number anddiagnostic message returned directly to the caller.5.2 Providing Scratch Variables for Parameter RoutingAlthough each applications program could provide variables for use as describedabove, a more economical approach is to extend the Model to permit special"scratch variables," maintained by the environment without assistance fromits applications program, to be created and deleted as necessary at run-time.Adding to the Protocol the following pair of system procedures enables thelocal environment to create and delete such variables in a remote process: CRTVARIABLE (variable, value) CHARSTR any DELVARIABLE (variable) CHARSTRThese procedures create and delete the specified VARIABLE, respectively.CRTVARIABLE also assigns an initial VALUE to the newly-created variable.These new procedures enable the environment to make available to itsapplications program, primitives that have calling sequences similar tothose of the corresponding system procedures but which accept the processhandle of the target process as an additional argument. Their implementationrequired only that the environment identify the remote process from itsinternal tables and invoke CRTVARIABLE or DELVARIABLE in that process.5.3 Discarding ResultsThe inefficiencies that result in Case 3 above are conveniently eliminatedby allowing the caller to identify via the result list mask (for example,via a zero-length CHARSTR) that a result will be ignored and therefore neednot be returned to the caller. -15-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Supporting a Richer Spectrum of Control Transfers6. Supporting a Richer Spectrum of Control TransfersAs currently defined by the Model, a procedure call is a simple two-stagedialog in which the caller first describes the operation it wishes performedand the callee, after performing the operation, reports its outcome.Although this simple dialog form is sufficient to conveniently implementa large class of distributed systems, more complex forms are sometimesrequired. The Model can be extended to admit a variety of more powerfuldialog forms, of which the four described below are examples.6.1 Transferring Control Between Caller and CalleeMany conventional programming systems permit caller and callee to exchangecontrol any number of times before the callee returns. Such "coroutinelinkages" provide a means, for example, by which the callee can obtainhelp with a problem that it has encountered or deliver the results of onesuboperation and obtain the arguments for the next.Adding to the Protocol the following system procedure, whose invocationrelinquishes control of another, previously initiated procedure, enablesthe environment to effect a coroutine linkage between caller and callee: TAKEPROCEDURE (tid, yourtid, parameters) INDEX BOOLEAN LISTIts arguments include the identifier TID of the affected transaction, anindication YOURTID of from whose name space the identifier was assigned(that is, whether the process relinquishing control is the caller or callee),and PARAMETERS provided by the procedure surrendering control. By exploitingan existing provision of the Protocol (that is, by declining acknowledgmentof its calls to TAKEPROCEDURE) the invoking environment can effect thecontrol transfer with a single inter-process message.The addition of this new procedure to the Protocol enables the environmentto provide the following new primitive to its applications program: LINKPROCEDURE (tid, arguments -> outcome, results) INDEX LIST [BOOLEAN] LIST -16-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Supporting a Richer Spectrum of Control TransfersThis primitive assumes that the CALLPROCEDURE primitive is also modified toreturn the pertinent transaction identifier should the callee initiate acoroutine linkage rather than return. Invocation of LINKPROCEDURE thencontinues the dialog by supplying ARGUMENTS and returning control to the remoteprocedure, and then awaiting the next transfer of control and the RESULTS thataccompany it. If the remote procedure then returns, rather than initiatinganother coroutine linkage, the primitive reports its OUTCOME and invalidatesthe transaction identifier.While this primitive blocks the applications program until the remoterprocedure relinquishes control, a variant that simply initiates the coroutinelinkage and allows the applications program to collect the outcome andresults in a second operation can also be provided.6.2 Signaling the Caller/CalleeA monolog is often more appropriate than the dialog initiated by a coroutinelinkage. The caller or callee might wish, for example, to report an event ithas detected or send large parameters piecemeal to minimize bufferingrequirements. Since no return parameters are required in such cases, theinitiating procedure need only "signal" its partner, while retaining controlof the call.Adding to the Protocol the following system procedure extends the Model tosupport signals and enables the environment to transmit parameters to orfrom another, previously initiated procedure without relinquishing controlof the call: SGNLPROCEDURE (tid, yourtid, parameters) INDEX BOOLEAN LISTLike the TAKEPROCEDURE procedure already described, its arguments includethe identifier TID of the affected transaction, an indication YOURTID offrom whose name space the identifier was assigned, and the PARAMETERSthemselves.This new procedure enables the environment to make available to itsapplications program a primitive that has a calling sequence similar to thatof the system procedure but which does not require YOURTID as an argument.Its implementation requires only that the environment identify the remoteprocess via its internal tables and invoke SGNLPROCEDURE in that process. -17-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Supporting a Richer Spectrum of Control TransfersBy requesting the acknowledgment of each call to SGNLPROCEDURE and, ifnecessary, delaying subsequent calls affecting the same transaction untilthe acknowledgment arrives, the invoking environment effects a crude form offlow control and so prevents the remote process' buffers from being overrun.6.3 Soliciting Help from SuperiorsAs in conventional programming systems, remotely callable procedures withina distributed system will sometimes call upon others to carry out portionsof their task. Each procedure along the "thread of control" resulting fromsuch nested calls is, in a sense, responsible to not only its immediate callerbut also to all those procedures that lie above it along the control thread.To properly discharge its responsibilities, a procedure must sometimescommunicate with these "superiors."Occasionally a procedure reaches a point in its execution beyond which itcannot proceed without external assistance. It might, for example, requireadditional resources or further direction from the human user upon whosebehalf it is executing. Before reaching this impasse, the procedure mayhave invested considerable real and/or processing time that will be lostif it aborts.Adding to the Protocol the following system procedure minimizes suchinefficiencies by enabling the environment to solicit help from a callee'ssuperiors: HELPPROCEDURE (tid, number, information -> solution) INDEX INDEX any anyIts arguments include the identifier TID of the affected transaction (thedirection of the control transfer being implicit in this case), a NUMBERidentifying the problem encountered, and arbitrary supplementaryINFORMATION.The primitive that this new procedure enables the environment to provideits applications program has an identical calling sequence. Its implementationrequires only that the environment identify the remote process from itsinternal tables and invoke HELPPROCEDURE in that process.The search for help begins with invocation of HELPPROCEDURE in the caller'senvironment. If the caller understands the problem (that is, recognizes -18-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming Model Supporting a Richer Spectrum of Control Transfersits number) and is able to solve it, HELPPROCEDURE will simply return whateverSOLUTION information the caller provides. Otherwise, HELPPROCEDURE must givethe next superior an opportunity to respond by calling itself recursively inthat process. The search terminates as soon as a superior responds positivelyor when the end of the control thread is reached. In the latter case, each ofthe nested HELPPROCEDURE procedures returns unsuccessfully to indicate to itscaller that the search failed.6.4 Reporting an Event to SuperiorsA procedure sometimes witnesses or causes an event of which its superiorsshould be made aware (for example, the start or completion of some majorstep in the procedure's execution). Adding to the Protocol the followingsystem procedure enables the environment to notify a callee's superiors of anarbitrary event: NOTEPROCEDURE (tid, number, information) INDEX INDEX anyLike HELPPROCEDURE, its arguments include the identifier TID of thetransaction it affects, a NUMBER identifying the event being reports, andarbitrary supplementary INFORMATION.The primitive that this new procedure enables the environment to provide itsapplications program has an identical calling sequence. Its implementationrequires only that the environment identify the remote process from itsinternal tables and invoke NOTEPROCEDURE in that process.By requesting acknowledgment of each call to NOTEPROCEDURE and, if necessary,delaying subsequent calls that affect that transaction until the acknowledgmentarrives, the invoking environment effects a crude form of flow control and soprevents the remote process' buffers from being overrun.Notification of the procedure's superiors begins with invocation ofNOTEPROCEDURE in the caller's process and works its way recursively up thethread of control until the top is reached. -19-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Some Possible Extensions to the Model Aborting Executing Procedures7. Aborting Executing ProceduresConventional systems that accept commands from the user sometimes permit himto cancel an executing command issued inadvertently or with erroneousparameters, or one for whose completion he cannot wait. This ability isparticularly important when the command (for example, one that compiles asource file) has a significant execution time. In a distributed system, theexecution of such a command may involve the invocation of one or more remoteprocedures. Its cancellation, therefore, requires the abortion of anyoutstanding remote procedure calls.Adding to the Protocol the following system procedure provides the basisfor a command cancellation facility by enabling the environment to abortanother, previously invoked procedure: ABRTPROCEDURE (tid) INDEXIts sole argument is the identified TID of the transaction it affects.The primitive that this new procedure enables the environment to makeavailable to the applications program has an identical calling sequence.Its implementation requires only that the local environment identify theremote process from its internal tables and invoke ABRTPROCEDURE in thatprocess. -20-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Conclusions CONCLUSIONThe EXPANDED Protocol and Model that result from the extensions proposed inthe present paper are summarized in Appendixes B and C, respectively.Needless to say, many additional forms and aspects of process interaction,of whichAppendix D suggests a few, remain to be explored. Nevertheless,the primitives already made available by the run-time environment providethe applications programmer with a powerful and coherent set of tools forconstructing distributed systems. -21-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming System Acknowledgments ACKNOWLEDGMENTSMany individuals within both SRI's Augmentation Research Center (ARC) and thelarger ARPANET community have contributed their time and ideas to thedevelopment of the Protocol and Model described in this and its companionpaper. The contributions of the following individuals are expresslyacknowledged: Dick Watson, Jon Postel, Charles Irby, Ken Victor, Dave Maynard,Larry Garlick of ARC; and Bob Thomas and Rick Schantz of Bolt, Beranek andNewman, Inc.ARC has been working toward a high-level framework for network-baseddistributed systems for a number of years now [2]. The particular Protocoland Model result from research begun by ARC in July of 1974. This researchincluded developing the Model; designing and documenting, and implementinga prototype run-time environment for a particular machine [4, 5], specificallya PDP-10 running the Tenex operating system developed by Bolt, Beranek andNewman, Inc. [6]. Three design iterations were carried out during a 12-monthperiod and the resulting specification implemented for Tenex. The Tenex RTEprovides a superset of the capabilities proposed in this paper.The work reported here was supported by the Advanced Research Project Agencyof the Department of Defense, and by the Rome Air Development Center of theAir Force. -22-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming SystemAppendix A: Transmission Formats for PCP Data Objects APPENDIX A TRANSMISSION FORMATS FOR PCP DATA OBJECTSData objects must be encoded in a standard transmission format before they canbe sent from one process to another via the Protocol. An effective strategyis to define several formats and select the most appropriate one at run-time,adding to the Protocol a mechanism for format negotiation. Format negotiationwould be another responsibility of the environment and could thus be madecompletely invisible to the applications program.Suggested below are two transmission formats. The first is a 36-bit binaryformat for use between 36-bit machines, the second an 8-bit binary, "universal"format for use between dissimilar machines. Data objects are fully typed ineach format to enable the environment to automatically decode and internalizeincoming parameters should it be desired to provide this service to theapplications program.PCPB36, For Use Between 36-Bit Machines Bits 0-13 Unused (zero) Bits 14-17 Data type EMPTY =1 INTEGER=4 LIST=7 BOOLEAN=2 BITSTR =5 INDEX -3 CHARSTR=6 Bits 18-20 Unused (zero) Bits 21-35 Value or length N EMPTY unused (zero) BOOLEAN 14 zero-bits + 1-bit value (TRUE=1/FALSE=0) INDEX unsigned value INTEGER unused (zero) BITSTR unsigned bit count N CHARSTR unsigned character count N LIST unsigned element count N Bits 36- Value EMPTY unused (nonexistent) BOOLEAN unused (nonexistent) INDEX unused (nonexistent) INTEGER two's complement full-word value BITSTR bit string + zero padding to word boundary CHARSTR ASCII string + zero padding to word boundary LIST element data objects -23-
Network Working James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming SystemAppendix A: Transmission Formats for PCP Data ObjectsPCPB8, For Use Between Dissimilar Machines Byte 0 Data type EMPTY =1 INTEGER=4 LIST=7 BOOLEAN=2 BITSTR =5 INDEX =3 CHARSTR=6 Bytes 1- Value EMPTY unused (nonexistent) BOOLEAN 7 zero-bits + 1-bit value (TRUE=1/FALSE=0 INDEX 2 byte unsigned value INTEGER 4-type two's complement value BITSTR 2-byte unsigned bit count N + bit string + zero padding to byte boundary CHARSTR 2-byte unsigned character count N + ASCII string LIST 2-byte element count N + element data objects -24-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming SystemAppendix B: The Expanded Procedure Call Protocol APPENDIX B THE EXPANDED PROCEDURE CALL PROTOCOLThe Protocol that results from the extensions proposed in this paper issummarized below. The reader should note the concise syntactic descriptionmade possible by the underlying notion of PCP data types.Parameter list masks have been included not only as additional parametersof the CALL message, as proposed in the paper, but as arguments of theTAKEPROCEDURE and SGNLPROCEDURE system procedures as well. Throughout theProtocol description, "MASK" is shorthand for: [LIST (variable [CHARSTR], ...)]Messages LIST (route INDEX, opcode INDEX CALL=1, tid [INDEX], pkh [INDEX], procedure CHARSTR, arguments LIST, argumentlistmask MASK, resultlistmask MASK) LIST (route INDEX, opcode INDEX RETURN=2, tid INDEX, outcome BOOLEAN, results LIST) If OUTCOME is FALSE RESULTS is LIST (error INDEX, diagnostic CHARSTR)Process-Related System Procedures INIPROCESS (program CHARSTR, credentials LIST (error CHARSTR, password CHARSTR, account CHARSTR)) ALOPORT (-> ph INDEX, computer CHARSTR, port) CNNPORT (ph INDEX, computer CHARSTR, port) DCNPORT (ph INDEX) CRTROUTE (mycode INDEX, oldcode [INDEX] -> code INDEX, ph INDEX) DELROUTE (yourcode INDEX)Package-Related System Procedures OPNPACKAGE (packages LISTofCHARSTRs -> pkhs LISTofINDEXs) CLSPACKAGE (pkhs LISTofINDEXs) -25-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed Programming SystemAppendix B: The Expanded Procedure Call ProtocolVariable-Related System Procedures CRTVARIABLE (variable CHARSTR, value) DELVARIABLE (variable CHARSTR) RDVARIABLE (pkh INDEX, variable CHARSTR, substructure [LISTofINDEXs] -> value)Procedure-Related System Procedures TAKEPROCEDURE (tid INDEX, yourtid BOOLEAN, parameters LIST, argumentlistmask MASK, resultlistmask MASK) SGNLPROCEDURE (tid INDEX, yourtid BOOLEAN, parameters LIST, parameterlistmask MASK) HELPPROCEDURE (tid INDEX, number INDEX, information -> solution) NOTEPROCEDURE (tid INDEX, number INDEX, information) ABRTPROCEDURE (tid INDEX) -26-
Network Working Group James E. WhiteRequest for Comments: 708 Elements of a Distributed ProgrammingAppendix C: Summary of RTE Primitives APPENDIX C SUMMARY OF RTE PRIMITIVESThe DPS primitives made available to the applications program as a result ofthe Model extensions proposed in this paper are summarized below.Collectively, they provide the applications programmer with a powerfuland coherent set of tools for constructing distributed systems. Some ofthe primitives (for example, CRTPROCESS and DELPROCESS) are necessary elementsfor a "network operating system (NOS)," into which DPS may itself one dayevolve. CRTPROCESS (computer, program, credentials -> PH) DELPROCESS (ph) ITDPROCESS (ph1, ph2 -> ph12, ph21, ih) SEPPROCESS (ih)Packages OPNPACKAGE (ph, packages -> pkhs) CLSPACKAGE (ph, pkhs)Variables CRTVARIABLE (ph, variable, value) DELVARIABLE (ph, variable) RDVARIABLE (ph, pkh, variable, substructure -> value) WRTVARIABLE (ph, pkh, variable, substructure, value)Procedures CALLPROCEDURE (ph, pkh, procedure, arguments, argumentlistmask, resultlistmask, -> outcome, results, tid) LINKPROCEDURE (tid, arguments, argumentlistmask, resultlistmask, -> outcome, results) SGNLPROCEDURE (tid, parameters, parameterlistmask) HELPPROCEDURE (tid, number, information -> solution) NOTEPROCEDURE (tid, number, information) ABRTPROCEDURE (tid) -27-
Network Working Group Elements of a Distributed Programming SystemRequest for Comments: 708Appendix D: Additional Areas for Investigation APPENDIX D ADDITIONAL AREAS FOR INVESTIGATIONAlthough the expanded distributed programming system developed in this paperand summarized in the previous appendix is already very powerful, manyadditional aspects of process interaction remain, of course, to be explored.Among the additional facilities that the Protocol must eventually enable theenvironment to provide are mechanisms for: (1) Queuing procedure calls for long periods of time (for example, days). (2) Broadcasting requests to groups of processes. (3) Subcontracting work to other processes (without remaining a middleman). (4) Supporting brief or infrequent inter-process exchanges with minimal startup overhead. (5) Recovering from and restarting after system errors. -28-
Network Working Group Elements of a Distributed Programming SystemRequest for Comments: 708 References REFERENCES1. White, J. E., "A High-Level Framework for Network-Based Resource Sharing," submitted for publication in the AFIPS Conference Proceedings of the 1976 National Computer Conference.2. Watson, R. W., Some Thoughts on System Design to Facilitate Resource Sharing, ARPA Network Working Group Request for Comments 592, Augmentation Research Center, Stanford Research Institute, Menlo Park, California, November 20, 1973 (SRI-ARC Catalog Item 20391).3. White, J. E., DPS-10 Version 2.5 Implementor's Guide, Augmentation Research Center, Stanford Research Institute, Menlo Park, California, August 15, 1975 (SRI-ARC Catalog Item 26282).4. White, J. E., DPS-10 Version 2.5 Programmer's Guide, Augmentation Research Center, Stanford Research Institute, Menlo Park, California, August 13, 1975 (SRI-ARC Catalog Item 26271).5. White, J. E., DPS-10 Version 2.5 Source Code, Augmentation Research Center, Stanford Research Institute, Menlo Park, California, August 13, 1975 (SRI-ARC Catalog Item 26267).6. Bobrow, D. G., Burchfiel, J. D., Murphy, D. L., Tomlinson, R. S., "TENEX, a paged Time Sharing System for the PDP-10," Communications of the ACM, Vol. 15, No. 3, pp. 135-143, March 1972. -29-
Network Working Group Elements of a Distributed Programming SystemRequest for Comments: 708 Figure List FIGURE LISTFig. 1 Interfacing distant applications programs via their run-time environments and an IPC channel.Fig. 2 Two processes that can only be introduced via a logical channel.Fig. 3 A logical channel. -30-
[8]ページ先頭