REGISTER  |  SIGN IN
United States Patent4325120
Colley , ; et al.April 13, 1982
Title
Data processing system
Abstract
A data processor architecture wherein the processors recognize two basic types of objects, an object being a representation of related information maintained in a contiguously-addresed set of memory locations. The first type of object contains ordinary data, such as characters, integers, reals, etc. The second type of object contains a list of access descriptors. Each access descriptor provides information for locating and defining the extent of access to an object associated with that access descriptor. The processors recognize complex objects that are combinations of objects of the basic types. One such complex object (a context) defines an environment for execution of objects accessible to a given instance of a procedural operation. The dispatching of tasks to the processors is accomplished by hardware-controlled queuing mechanisms (dispatching-port objects) which allow multiple sets of processors to serve multiple, but independent sets of tasks. Communication between asynchronous tasks or processes is accomplished by related hardware-controlled queuing mechanisms (buffered-port objects) which allow messages to move between internal processes or input/output processes without the need for interrupts. A mechanism is provided which allows the processors to communicate with each other. This mechanism is used to reawaken an idle processor to alert the processor to the fact that a ready-to-run process at a dispatching port needs execution.
Inventors:Colley; Stephen R. (Aloha, OR), Cox; George W.  (Portland, OR), Rattner; Justin R.  (Aloha, OR), Swanson; Roger C.  (Portland, OR)
Assignee:Intel Corporation (Santa Clara, CA)
Appl. No.:971661
Filed:December 21, 1978
Current U.S. Class:711/202 711/221 
Field of Search:364/2MSFile,9MSFile
U.S. Patent Documents
3648253March 1972Mullery et al.
3787818January 1974Arnold et al.
3905023September 1975Perpiglia
4044334August 1977Bachman et al.
4047161September 1977Davis et al.
4060849N/ABrenvenu et al.
4071890January 1978Pandeya
4084224April 1978Appell et al.
4104718August 1978Poublan et al.
Primary Examiner: Springborn; Harvey E.
Attorney, Agent or Firm:Lamb; Owen L.
Claims

What is claimed is:
1. For use in a data processing system including at least one processor capable of executing an operation by means of an operator specified in an instruction, said operator including a class field specifying the operator class to which said operator belongs, said system having instruction objects defining an operation, and data objects, said objects stored in a memory which can be shared by a number of processors, an object-based access mechanism comprising:
means for decoding said instruction, said decoding means including means for decoding said class field specifying the operator class to which said operator belongs;
first means for registering first access information, said first access information providing information for locating a description (a first segment descriptor) of a first object (a data segment) stored in said memory, said first object being of a first basic type, said first object being a representation of related first information maintained in a contiguously-addressed set of memory locations;
second means for registering second access information, said second access information providing information for locating a description (a second segment descriptor) of a second object (an access list) stored in said memory, said second object being of a second basic type, said second object being a representation of related second information maintained in a contiguously-addressed set of memory locations;
said first type of object (said data segment) containing data scalar values;
said second type of object (said access list) containing access descriptors, at least one of said access descriptors providing information for locating said description of an object (said segment descriptor) and information for defining the extent of access to an object accessible through the use of said access descriptor and said segment descriptor;
each of said segment descriptors including a type field for indicating that the segment of said first or second type of object from which operands are obtainable for execution by said operator correspond to a particular one of said first or second types;
means for registering said segment decriptor type fields; and
third means connected to said instruction decoding means, to said first and said second means and to said segment descriptor type field registering means, responsive to said operator specified in said instruction, for accessing said memory, said third means including means for invoking said first means or said second means, to access said memory, upon the condition that said class field in said operator for specifying the operator class to which said operator belongs and said segment descriptor type field each indicate that the content of the segment accessible by said first or second means corresponds to said first type of object or said second type of object, respectively.

2. The combination in accordance with claim 1 wherein:
said third means includes means for developing a physical memory address of an item of information within an object from a logical address for said item of information.

3. The combination in accordance with claim 1 wherein said segment descriptors include a base address indicating the starting address of a segment and a length vector specifying the length of said segment.

4. The combination in accordance with claim 3 wherein:
said third means includes means for developing a physical memory address of an item of information within an object including means for adding the position (displacement) of an item of information within said segment to said base address of said segment.

5. The combination in accordance with claim 4 wherein:
said third means further comprises means for protecting memory areas including means for comparing said displacement and said length vector, and means responsive to said comparing means for indicating a fault if said displacement exceeds said length.

6. The combination in accordance with claim 3 further comprising:
means (a segment table) for storing the base address-and-length parameters (a segment descriptor) of all allocated and unallocated segments; and
fourth means connected to said third means means including means for fetching the parameters for a particular segment from said segment table;
whereby changing the base address of any segment or redefining the size of a segment can be performed by updating a single copy of the parameters describing said segment, as stored in said segment table.

7. The combination in accordance with claim 1, wherein said segment descriptors further include:
means for selectively indicating that the manipulation of data in said first type of object is permitted and for indicating that the manipulation of data in said second type of object is not permitted.

8. The combination in accordance with claim 1 wherein said access list comprises:
means for storing various types of access descriptors, including access-list access-descriptors for other access lists that are part of complex structures;
said access descriptors representing hardware-recognized objects and software-created system objects;
whereby a complex object may be structurally changed by manipulation of said various access descriptors in the access list corresponding to said object.

9. The combination in accordance with claim 8 wherein said access list includes an access descriptor providing access to a data segment containing data associated with said access list.

10. The combination in accordance with claim 8 including:
means in said processor for executing a move access descriptor operator to thereby move an access descriptor from a specified entry in a directly accessible access list to a specified entry in another directly accessible access list.

11. The combination in accordance with claim 8 including:
means in said processor for executing a move access descriptor indirect to thereby move an access descriptor from a specified entry in an indirectly accessible access list to a specified entry in another indirectly accessible access list.

12. The combination in accordance with claim 8 including:
means in said processor for executing a restrict rights operator to thereby restrict access of an operation to an object.

13. The combination in accordance with claim 8 including:
means in said processor for executing an amplify rights operator to thereby amplify access of an operation to an object.

14. For use with a memory shared by a number of processors, said memory having stored therein instruction objects defining an operation, and data objects, at least one of said processors comprising:
first means for registering first access information, said first access information providing access to a first processor-recognizable object (a domain);
second means for registering second access information, said second access information providing access to a second processor-recognizable object (a context);
third means for registering third access information, said third access information providing access to said instruction objects and said data objects;
said first processor-recognizable object (a domain) including said third access information (access descriptors) for providing access information for use by said third means in accessing said instruction objects and said data objects;
said second object (a context) including fourth access information (access descriptors) having encoded fields specifying the type and extent of access to said instruction objects and said data objects, said that for a process executing instructions (from said instruction objects) which reference a set of objects (either access lists or data segments) defined by said fourth access information in said second object, only those objects whose access descriptors appear in said second object are accessible and only in a manner specified by said encoded fields of said access descriptors in said second object;
said fourth access information in said second processor-recognizable object defining said set of objects (either access lists or data segments) accessible to the instructions of a given instance of an operation, said set of objects including said first processor-recognizable object, said fourth access information including therein said first access information to thereby provide information for use by said first accessing means in accessing said first object; and
fifth means connected to said first and second means, said fifth means including means for decoding said encoded fields of said access descriptors in said second object and for invoking said first means and said second means, to thereby access said memory and said instruction objects and said data objects stored in said memory in said manner specified by said encoded fields of said access descriptors in said second object.

15. The combination in accordance with claim 14 wherein said second object has associated therewith a message object, said combination further comprising:
means (an access descriptor) for providing access to said message object;
sixth means for registering sixth access information, said sixth access information providing access to a sixth processor-recognizable object (another context), and
means for communicating instances of operations by moving a message in said second object to said sixth object, the message being the access descriptor of the one of said objects that has been referenced with said descriptor.

16. The combination in accordance with claim 14 wherein said second object has associated therewith a nonbuffered port, said combination further comprising:
means (an access descriptor) for providing access to said nonbuffered port; and
means for inserting into said nonbuffered port an access descriptor for said context object.

17. The combination in accordance with claim 14 further comprising:
a create-context operator;
a call-context operator;
means responsive to said create-context operator for preparing and establishing an access environment in which the operation that is called by said call-context operator has access both to data on said first object and to access descriptors on said second object, said create-context operator including means for updating linkage information for operations entered and not yet returned from on said second object; and,
means for storing parameters onto a newly-created context, said context being the context for the operation called.

18. The combination in accordance with claim 17 further comprising;
means (return context operator) for reestablishing the environment for dynamic accessibility of the process environment object that existed before execution of said call-context operator.

19. The combination in accordance with claim 18 wherein said return-context operator means further includes means to return information to the reestablished dynamic environment, by means of a link access descriptor entry of the current context object.

20. The combination in accordance with claim 14 wherein said second object further includes means for supporting a program structure (coroutine) for enabling a number of context objects to be associated with each computational object.

21. The combination in accordance with claim 14 wherein said first object includes means for supporting a computationally complete access environment, said access environment including separate primary segments, one for each of a public, a private, and entry access list.

22. The combination in accordance with claim 21 wherein:
said public access list comprises a primary segment containing access descriptors for all objects available to another process environment including an access descriptor of a private access list;
said private access list comprises a primary segment containing the access descriptors for those objects that are only accessible when a process is operating within said process environment as a result of invoking one of the operations within said environment; and
said entry access list comprises the public access list for one of the process environments whose access descriptors are accessible in said first-mentioned process environments.

23. The combination in accordance with claim 21 wherein one of the access descriptors in said public access list is for an instruction segment to hold instructions of programmer-defined operations associated with said process environment.

24. The combination in accordance with claim 21 wherein one of the access descriptors in said public access list is the access descriptor of its private access list, the entry in said list appearing to be a null access descriptor when examined or selected from outside said process environment, whereby only by invoking one of the operations in the public part of said process environment does a process gain access to said public access list entry and thus access to the private access list of said process environment.

25. For use with a memory shared by a number of processors, said memory having allocatable memory locations, a processor comprising:
first means connectable to said memory for registering access information, said access information providing access to a plurality of objects stored in said memory;
second means for developing a physical memory address from a logical address reference to an object, in response to a request from a process running on said processor; and
third means connected to said first and second means for registering third access information providing access to a first processor-recognizable object for storing therein access information for describing in said memory a set of objects which an operation being executed can access, said third access information including encoded fields for specifying what kind of access is provided to said objects in said memory, such that said objects are accessible by said first means only in a way specified by said encoded fields.

26. The combination in accordance with claim 25 wherein, said memory has stored therein instruction objects defining an operation, and data objects, said combination further comprising:
means for accessing said instruction objects and data objects, said first object including access information (access descriptors) including encoded fields for specifying the type and extent of access to said objects, such that for a process executing instructions from said instruction objects which reference said set of objects, defined by said first object, only those objects whose access descriptors appear in said first object are accessible and only in a manner specified by said encoded fields.

27. The combination in accordance with claim 26 further comprising:
fourth means, connected to said first and second means, for registering fourth access information providing access to a second processor recognizable object defining said set of objects accessible to the instruction of a given instance of a procedural operation, said set of objects including said first processor-recognizable object, said second object being associated with said process running on said processor.

28. The combination in accordance with claim 27 further comprising:
means for storing the state of a computation associated with one of said instruction objects in said memory, said state representing a virtual processor, a virtual processor being defined for each process; and
means for associating one of said number of processors with said virtual processor;
whereby a ready-to-run process is paired with an available one of said processors.

29. The combination in accordance with claim 28 wherein the means for associating a physical processor with said virtual processor comprises;
queuing means (a dispatching port) for effecting the dispatching of processes for execution by one of said number of processors, said dispatching port means including executable process queuing means for queuing processes which have been sent for execution, and processor queuing means for queuing processors that are avaiable to receive a process for execution thereof.

30. The combination in accordance with claim 28 wherein a processor has access via a processor object to two communication segments, one for system wide communication (a global communication segment) and one for processor specific communication (a local communication segment); and,
processor control flags in said communiation segments,
whereby when set by a sending processor and later inspected by a target processor, specified functions are indicated in accordance with the setting of said control flags.

31. The combination in accordance with claim 28 wherein said means for associating a physical processor with a virtual processor includes:
means in a processor responsive to the detection of an alarm signal for suspending a process that said processor is currently executing; and
means for activating the execution of a process waiting at an alarm dispatching port specified by a port access descriptor.

32. The combination in accordance with claim 27 wherein said second object has associated therewith a message segment, said combination further comprising:
means (an access descriptor) for providing access to said message object;
fifth means for registering fifth access information, said fifth access information providing access to a fifth processor-recognizable object (another context), and
means for communicating between instances of operations by moving a message in said second object to said fourth object, the message being the access descriptor of said message object represented by said descriptor.

33. The combination in accordance with claim 27 wherein said second object has associated therewith a nonbuffered port, said combination further comprising:
means (an access descriptor) for referencing said nonbuffered port; and
means for inserting into said nonbuffered port an access descriptor for said context object.

34. The combination in accordance with claim 27 wherein said first object has associated with it access list means for referencing arbitrarily complex multisegment structures, said access list comprising:
means for storing various types of access descriptors, including access list access descriptors for other access lists that are part of said structures;
said access descriptors representing hardware recognized objects and software-created system objects;
whereby a complex object may be structurally changed by manipulation of said various access descriptors in the access list corresponding to said object.

35. The combination in accordance with claim 34 wherein said access list means includes an access descriptor referencing a data segment associated with said access list.

36. The combination in accordance with claim 34, further comprising:
a first mechanism for controlling the degree of movement of access descriptors; and,
a second mechanism for supporting an indirectly accessible list, including means for reading the access descriptor from a specified entry in the indirectly accessible access list, and means for writing said access descriptor onto said second object, whereby the object referenced by said means descriptor may be accessed directly.

37. The combination in accordance with claim 34 further comprising:
a first mechanism for controlling the degree of movement of access descriptors; and,
a second mechanism for supporting a directly accessible access list, including means for changing entries in the directly accessible access list, whereby an access descriptor may be removed from said second object, and said access descriptor may be written into a specified entry in said directly accessible access list.

38. The combination in accordance with claim 34 including:
means in a processor for executing a move access descriptor operator to thereby move an access descriptor from a specified entry in a directly accessible access list to a specified entry in another directly accessible access list.

39. The combination in accordance with claim 34 including:
means in a processor for executing a move access descriptor indirect to thereby move an access descriptor from a specified entry in an indirectly accessible access list to a specified entry in another indirectly accessible access list.

40. The combination in accordance with claim 34 including:
means in a processor for executing a restrict rights operator to thereby restrict access of an operation to an object.

41. The combination in accordance with claim 34 including:
means in a processor for executing an amplify rights operator to thereby amplify access of an operation to an object.

42. The combination in accordance with claim 27 further comprising means for parameter and result transmission, including a message segment associated with said second object; and
means for establishing an access environment in which an operation to be called has access to data in said message segment;
whereby any number of scalar parameters can be transmitted via said message segment.

43. The combination in accordance with claim 27 further comprising:
a create context operator;
a call-context operator;
means responsive to said create-context operator for preparing and establishing an access environment in which the operation that is called by said call-context operator has access both to data on said first object and to access descriptors on said second object, said create-context operator including means for updating linkage information for operations entered and not yet returned from on said second object; and,
means for storing parameters onto a newly-created context, said context being the context for the operation called.

44. The combination in accordance with claim 43 further comprising:
means (return context operator) for reestablishing the environment for dynamic accessibility of the context object that existed before execution of said call context operator.

45. The combination in accordance with claim 44 wherein said return context operator means further includes means to return information to the re-established dynamic environment, by means of a link access descriptor entry of the current context object.

46. The combination in accordance with claim 27 wherein said context object further includes means for supporting a program structure (coroutine) for enabling a number of context objects to be associated with each instruction object.

47. The combination in accordance with claim 27 wherein said second object includes means for supporting a computationally complete access environment, said access environment including separate primary segments, one for each of a public, a private, and entry access list.

48. The combination in accordance with claim 47 wherein:
said public access list comprises a primary segment containing access descriptors for all objects available to another process environment having an access descriptor for said other environment, including an access descriptor of a private access list;
said private access list comprises a primary segment containing the access descriptors for those objects that are only accessible when a process is operating within said environment as a result of invoking one of said operations; and
said entry access list comprises the public access list for one of the environments whose access descriptors are accessible in said first-mentioned environment.

49. The combination in accordance with claim 47 wherein one of the access descriptors in said public access list is for an instruction segment to hold instructions of programmer-defined operations associated with said environment.

50. The combination in accordance with claim 47 wherein one of the access descriptors in said public-access list is the access descriptor of its private-access list, the entry in said list appearing to be a null access descriptor when examined or selected from outside said environment, whereby only by invoking one of the operations in the public part of said process environment does a process gain access to said public-access-list entry and thus access to the private-access list of said process environment.

51. The combination in accordance with claim 25 wherein:
said means for maintaining an environment includes means for initating the creation by said object maintaining means of a first type of system object (a data segment) for containing data scal ar values, and a second type of system object (an access list) for containing access descriptors having parameters which define the type and extent of access to an object associated with an access descriptor, said combination further comprising,
means in said processor for allocating a data segment of said first or second type of system object in response to a request from said process running on said processor.

52. The combination in accordance with claim 51, wherein said processor further comprises:
means for selectively indicating that the manipulation of data in said first type of system object is permitted and
for indicating that the manipulation of data in said second type of system object is not permitted.

53. The combination in accordance with claim 51 wherein said parameters in said access descriptors include a base address indicating the starting address of a data segment and a length vector specifying the length of said segment.

54. The combination in accordance with claim 53 wherein said means in said processor for developing a physical memory address includes means for adding the position (displacement) of an item of data within said data segment to said base address of said data segment.

55. The combination in accordance with claim 54 further comprising:
means in said processor for protecting memory areas including means for comparing said displacement and said length vector, including means for indicating a fault if said displacement exceeds said length.

56. The combination in accordance with claim 53 further comprising:
means responsive to said allocating means (a segment table) for storing the base address and length parameters (a segment descriptor) of all allocated and unallocated data segments; and
wherein said address development means further includes means for fetching the parameters for a particular segment from said segment table;
whereby changing the base address of any segment or redefining the size of a segment can be performed by updating a single copy of the parameters describing said segment, as stored in said segment table.
Description
FIELD OF THE INVENTION

The invention relates to data processing systems, and more particularly to multiprocessing systems.

DESCRIPTION OF THE PRIOR ART

A multiprocessing system is able to execute simultaneously two or more computer programs or sequences of instructions. In a tightly-coupled multiprocessing system several processors may be connected to a single, shared memory. These systems multiplex numerous concurrent functions or tasks on one or more of the processors. Facilities must be provided for ensuring necessary isolation and communication between tasks, and for assigning available processors to tasks which are ready to be executed. Prior approaches have employed software, firmware, and hardware techniques.

Of the prior software techniques, there are the master-slave types of systems wherein one processor performs executive functions to allocate tasks to the other processors in the system (Mellen et al U.S. Pat. Nos. 3,530,438 and Barbour
3,984,817). There are also systems that utilize identical processors wherein none of them take on the role of the master. These systems utilize a central control wherein the software for task assignment is stored in memory (Driscoll U.S. Pat. Nos.
3,496,551 and Ochsner 3,348,210). Finally there are those systems wherein a special instruction is provided for implementing task assignment in each processor (Podvin U.S. Pat. Nos. 3,614,745 and Clark 3,725,864).

In Mellen et al U.S. Pat. No. 3,530,438 a multiprocessor is disclosed which has identical processors that can execute any task. An executive control program handles task scheduling by maintaining task priority lists of received requests. The requests are removed from the list and assigned to processors as they become available. When a processor finishes a task it interrogates the task table for a new assignment. The system relies on executive control programming to perform the task scheduling. The control program controls the generation of requests for tasks and the assignment of priorities to the requests, prioritizes the requests in tasks tables and controls the one-by-one removal of the requests from the task tables as processors become available to perform the tasks.

Barbour U.S. Pat. No. 3,984,817 provides for allocating resources in a data processor's memory to a plurality of programs based upon the activity level of each program. Each use of a program causes the activity queue of the used program to be given the highest activity state.

In Driscoll U.S. Pat. No. 3,496,551 task assignment is performed by a supervisory program which allocates tasks to different queues. A quota system established by the supervisory program allocates the various processors to the queues so that each queue is assured of a certain number of processors working on it. The quota system established for each queue causes a processor to step to the next queue in scanner sequence when a particular queue has its quota of processors working on it. In this manner the supervisory program attempts to maximize the efficiency of the system.

In Ochsner U.S. Pat. No. 3,348,210 a number of identical processors share a common store and execute tasks in parallel. When a processor completes one task, the last instruction in the task transfers control of the processor to a task assignment algorithm stored in a memory separate from the common store. This is an example of the type of multiprocessor wherein a processor relinquishes control to a central control unit which performs the task assignment function.

In Podvin U.S. Pat. No. 3,614,745 a special fork instruction is provided to initiate task switching. When a processor executes this instruction a fork status word is sent to a central control apparatus which handles resource management for the entire system. Status work queues are maintained for each type of fork instruction. The central control apparatus allocates available processors to cause them to take tasks from the queues and execute them. This patent represents an attempt to achieve optimum system efficiency by assigning resources dynamically as parallel tasks are executed. The technique necessitates that one of the processors take on the job of distributing tasks among other free processors.

In Clark U.S. Pat. No. 3,725,864 a plurality of input/output processors select an I/O task from a queue of tasks whenever the I/O processor is available. The I/O processor performs the I/O program up to a point in the program where it can be temporarily suspended. The program is then stored in a device queue which frees the I/O processor and makes it available to select another task from the task queue and thereby execute the I/O program associated with a new task. When the partially-performed task which was stored in the device queue is ready to be resumed, the specified device signals the I/O processors. Any one of them which is available responds to the signal, fetches the partially-performed task from the device queue, and resumes the previously-suspended I/O program. Self-scheduling of channel programs is done by a special enqueue command which is part of the channel program.

Techniques utilizing firmware use special-purpose microprogrammed controllers to perform the scheduling and dispatching functions.

Nadir U.S. Pat. No. 4,011,545 is an example. This patent discloses a multiprocessor system which uses a loop architecture. A number of processors are connected to a communication loop and are accessed through ports which are identified by unique addresses. Data and commands are received by means of time slots on the loop. The information is shifted into shift registers at the receiving processor. If the processor's address is found in the shifted data then operations are commenced. If the processor's address is not found, data are allowed to pass back onto the loop unchanged.

Of the hardware techniques in the prior art there are those that have task queues and utilize either scanners (Valassis U.S. Pat. No. 3,959,775) or a central control (Tucker U.S. Pat. No. 3,449,722) for allocating tasks among a number of processors by manipulating the queues. Other hardware techniques allocate time slots to each of the processors to thereby synchronize the processors with programs by either utilizing a synchronous bus technology (Anceau et al U.S. Pat. No. 4,015,242) or by dividing up the memory cycles between the processors (Brown U.S. Pat. No. 3,896,418).

Valassis et al U.S. Pat. No. 3,959,775 discloses a synchronous type of multiprocessor in which common control equipment called a bus assigner allocates the processors on either a priority basis or on a sequential basis by scanning the processors.

In Tucker U.S. Pat. No. 3,449,722 a common queue services a number of independent processors. All operations are under control of a central control portion which has access to the common queue. The central control thus selects the appropriate processor by examining the queue when a processor becomes free in order to find a request earmarked for the free processor.

Anceau et al U.S. Pat. No. 4,015,242 discloses a multiprocessor system which has one hardware main processor and several special processors for executing a number of programs. Task switching is controlled by software lists and a priority scheme. A group of flip-flops in a register indicates which processors are activated. A management logic includes means for examining the state of these flip-flops to perform the dispatching function. This patent is an example of recent techniques wherein the dispatching and scheduling functions are performed by special automatic microprogrammed logic.

Brown U.S. Pat. No. 3,896,418 is an example of still another synchronous approach to the handling of multiprocessors which share a common memory so that the processors can simultaneously execute separate programs. In Brown the fetch and execute cycles of each processor are synchronized such that while one processor is in a fetch cycle the other is in an execute cycle.

None of the prior art data processing systems take full advantage of recent advances in the state-of-the-art of very large-scale, integrated-circuit technology. Accordingly, the performance of these prior systems is low and programming to support multiprocessing is very complex.

With respect to the prior art software techniques discussed above, while they are capable of performing complex multiprocessing operations, they suffer from the high costs of control programming to support these operations.

The firmware techniques, while reducing somewhat the programming costs of the software techniques, lack flexibility and lack general-purpose application.

The hardware techniques of the prior art also lack flexibility by being able to handle only synchronous types of operations. They also lack the necessary hardware mechanisms to effectively communicate between various asynchronous operations without resort to costly control program support for such operations, for example, interrupts at the processor level.

It is therefore a primary object of the present invention to provide a new data processing apparatus which is fast and economical, and which is designed to efficently utilize large-scale, integrated-circuit technology.

It is a further object of this invention to provide an architectural structure which supports several levels of system performance, while preserving compatibility among systems.

It is also an object of this invention to provide a data processing apparatus which may be utilized in a tightly-coupled multiprocessing system, wherein one or more processors share a single memory space.

It is an object of this invention to provide a data processing system in which processor-level interrupts or service requests are not needed.

It is a further object of this invention to provide a data processing system structure which has the capability of increasing processing power by accommodating the addition of general-purpose and input/output processors without logical restrictions.

It is an object of this invention to provide a hardware mechanism for the isolation of and communication between tasks multiplexed to run concurrently on one or more processors, and to provide facilities to automatically assign available processors to ready-to-run tasks.

A still further object of the invention is to provide means whereby new tasks may be created, processed, and deleted under dynamic software control, and wherein shared hardware and software resources may be dynamically allocated, interlocked, and reclaimed.

BRIEF SUMMARY OF THE INVENTION

Briefly, the above objects are accomplished in accordance with the invention by providing an object-based access mechanism which is employed by processors within the system. An object is a representation of related information maintained in a contiguously-addressed set of memory locations. Two basic types of objects are recognized and distinguished by a processor. The first basic type (a data segment) contains ordinary data such as characters, integers, reals, etc. The second basic type (an access list) contains access descriptors. Each access descriptor provides information for locating and defining the extent of access to an object associated with that access descriptor. Processors construct complex objects by combinations of objects of the basic types. Mechanisms within the processor identify the types of complex objects and control their use.

One such complex object, a context, defines an environment made up of objects accessible to a given instance of a procedural operation. Processors recognize context objects and utilize them in process execution.

In accordance with an aspect of the invention, two other types of hardware recognizable objects, buffered communication ports and dispatching ports, are defined.

A buffered port is responsive to a currently-running process and provides the means for communication between processes. Each buffered port includes a dual-purpose queue for queuing messages which have been sent and for queuing processes that are waiting to receive a message.

Dispatching ports and buffered ports are utilized in the dispatching of ready-to-run processes for execution by an available processor. Each dispatching port includes separate queuing means for queuing processes sent from a buffered port for execution, and for queuing processors that are available to receive a process for execution thereof.

In accordance with another aspect of the invention, means capable of being activated by a process are provided for selectively queuing a process to either a buffered port or a dispatching port. This enables a process to be selectively communicated for service by either a processor or another process, whereby additional process interpretation may be interposed prior to the execution of a process by a processor.

In accordance with a further aspect of the invention, a value called a "deadline" is used in a dispatching port. This value is generated by a processor when it enqueues a process at a dispatching port, the process with the nearest deadline being placed at the head of the request queue. The processes on the request queue are thus ordered in priority by increasing deadlines. Since processors always remove processes from the head of the request queue, the processes with the nearest deadline are served first. Means are also provided whereby a process may queue itself for execution at some future time. In the event no processes become enqueued with either deadlines, an idle processor queued at the dispatching port automatically reschedules itself to the delayed process at the future time.

The present invention has the advantage that the need for a supervisory control program is eliminated. This is accomplished by providing the hardware dispatching port mechanism (by which a processor is able to perform a self-queuing function and thus wait at a dispatching port until a process to be executed arrives) in conjunction with the hardware buffered port mechanism (by which a processor is able to perform the interprocess communication function and thus delay or relay processes to dispatching ports for execution).

The present invention has the further advantage that the central control techniques of the prior art are not necessary as task assignment and interprocess communication is performed by the processors themselves. The disadvantages of master-slave types of systems are eliminated.

The present invention utilizes a resource control segment which contains fields of information called the delay period and the service period. This has the advantage of allowing processors to automatically control distribution of processing resources in accordance with policies initially set through software.

The present invention has the advantage over prior synchronous types of multiprocessor systems of being able to handle simultaneous synchronous or asynchronous operations by means of the unique buffered ports and dispatching ports.

The invention has the further advantage that the number of processors may be increased to obtain higher performance without having to provide new software for each new configuration. This is possible because each processor automatically assigns itself to a ready process or will wait for a process to be made ready by the activity on some other processor.

Another advantage of the invention is that modern programming languages are supported by the unique way the static component of a context is divided into a public access list and a private access list. All operations on a given extended type are made available via the public access list. Data hiding or object hiding is accomplished by means of the private access list.

The invention also has the advantage that by providing a segment table for storing the base address and segment descriptors, the updating of parameters describing a segment is performed by updating a single copy of the parameters.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing and other objects, features, and advantages of the invention will be apparent from the following detailed description of a prefered embodiment of the invention, as illustrated in the accompanying drawings wherein:

FIG. 1 is a functional block diagram illustrating the various components of the invention;

FIGS. 2A and 2B, taken together, are a block diagram of system objects for supporting object addressing and protection in the main memory shown in FIG. 1;

FIGS. 3A and 3B, taken together, are a block diagram of system objects making up an individual process environment, shown in FIG. 1;

FIGS. 4A and 4B, taken together, are a block diagram of system objects supporting interprocess communication, scheduling and dispatching of processes, and interprocessor communication, shown in FIG. 1;

FIG. 5 is a block schematic diagram of a computer system of a type in which the invention may be embodied;

FIG. 6 is a block schematic diagram of one of the processing units shown in FIG. 5;

FIG. 7 is a block schematic diagram of the instruction unit of FIG. 6;

FIG. 8 is a block schematic diagram of the execution unit of FIG. 6;

FIG. 9 is a clock timing diagram;

FIG. 10 is a timing diagram of a typical read cycle;

FIG. 11 is a timing diagram of a typical write cycle;

FIG. 12 is a timing diagram of a faulted access;

FIG. 13 is a timing diagram of microcode interrogate;

FIG. 14 is a timing diagram of self-check;

FIG. 15 is a timing diagram of true, alarm, and HERRIN lines; and

FIGS. 16A and 16B, taken together, are a block diagram of system objects supporting input/output operations.

TABLE OF CONTENTS

Description

Field of the Invention

Description of the Prior Art

Brief Summary of the Invention

Brief Description of the Drawings

Table of Contents

Introductory Description of the Invention

Object Creation, Addressing and Typing

Individual Process Environment

Intercontext Communication

Interprocess Communication

Dispatching Mechanism

Interprocessor Communication

Processor Types

PART 1. GENERALIZED DATA PROCESSOR ARCHITECTURE

1.0 Overall System

1.1 Segmented Addressing

1.2 Segment Types

1.3 Objects

1.4 Functional Hierarchy

1.5 Communication

1.6 Data Types, Operators, and Instructions

2.0 Information Structure

2.1 Memory

2.1.1 Logical Addressing

2.1.2 Physical Addressing

2.2 Data Formats

2.3 Data Representation

2.4 Data Positioning

2.5 Data Integrity

2.6 Operand Stacks

2.7 Instruction Segments

3.0 Generalized Data Processing

3.1 Computational Data Types

3.1.1 Character

3.1.2 Short Ordinal

3.1.3 Short Integer

3.1.4 Ordinal

3.1.5 Integer

3.1.6 Short Real

3.1.7 Real

3.1.8 Temporary Real

3.2 Instruction Composition

3.2.1 Types of References

3.2.2 Operators

3.2.3 Data References

3.2.3.1 Explicit Data References

3.2.3.2 Implicit Data References

3.3 Operand Stack Behavior

3.4 Sequential Instruction Execution

3.5 Branching

4.0 System Object Structures

4.1 Segments

4.1.1 Segment Tables and Segment Descriptors

4.1.2 System Types and Their Encodings

4.1.3 Segment Table Directories and Segment Tables

4.1.4 Temporary Segment Table Directory

4.2 Access Lists

4.2.1 Access Descriptors and Access Paths

4.2.1.1 Access Rights

4.2.1.2 Descriptor Control

4.2.2 Access List Access Rights

4.2.3 Null Access Descriptor

4.3 Data Segments

4.3.1 Data Segment Access Rights

4.3.2 Segment Table Segments

4.4 Domains

4.4.1 Public and Private Access Lists

4.5 Operations and Contexts

4.5.1 Context Objects

4.5.1.1 Instruction Segments

4.5.1.2 Context Control Segments

4.5.1.3 Operand Stacks

4.5.1.4 Entry Access List

4.6 Coroutines

4.6.1 Nonbuffered Communication Ports

4.7 Processes

4.7.1 Process Objects

4.7.1.1 Process Control Segments

4.7.1.2 Current Service and Buffered Ports

4.7.1.3 Segment Tables and Storage Resources

4.7.1.4 Trace, Notification, and Fault Buffered Ports

4.7.1.5 Fault Access Descriptor

4.7.2 Buffered Communication Ports

4.7.2.1 Buffered Port Control Segment

4.7.2.2 Service Ports

4.8 Processors

4.8.1 Processor Objects

4.8.1.1 Processor Self-Queuing

4.8.1.2 Processor Control Segments

4.8.1.3 Global Communication Segments

4.8.1.4 Current Process Objects

4.8.1.5 Current Segment Table Directories

4.8.1.6 Alarm Dispatching Ports

4.8.1.7 Diagnostic Dispatching Ports

4.8.1.8 Fault Access Descriptors and Fault Process Objects

4.8.2 Dispatching Ports

4.8.2.1 Dispatching Port Control Segment

4.8.2.2 Request and Service Queues

4.8.2.3 Deadlines

4.8.2.4 Preemption Ports

4.9 Storage

4.9.1 Free Segment Descriptor Lists

4.9.2 Storage Resource Control Segments

4.10 Transformers

4.11 Labels

4.11.1 Path Level Descriptors

4.11.2 Label Linkages

4.11.3 Label Objects

4.12 Processor Registers

5.0 Access Environment Manipulation and Communication

5.1 Access Environment Manipulation Mechanisms

5.1.1 General Access Descriptor Movement

5.1.2 Complex Object Manipulation

5.1.3 Type & Rights Application & Manipulation

5.1.4 Access Path Labeling & Traversal

5.1.5 Dynamic Segment & Path-Level Creation

5.1.5.1 Segment Descriptor Allocation

5.1.5.2 Storage Allocation

5.1.5.3 Path Level Creation

5.1.6 Access Path Inspection

5.1.7 Object Interlocking

5.2 Communication Mechanisms

5.2.1 Instruction-to-Instruction Communication

5.2.2 Context-to-Context Communication

5.2.2.1 Intradomain Context Creation

5.2.2.2 Interdomain Context Creation

5.2.2.3 Parameter and Result Transmission

5.2.2.4 Context Invocation

5.2.2.5 Context Return

5.2.3 Coroutine-to-Coroutine Communication

5.2.3.1 Coroutine Parameter Transmission

5.2.3.2 Coroutine Resumption/Suspension

5.2.4 Process-to-Process Communication

5.2.4.1 Process Parameter Transmission

5.2.4.2 Process Resumption/Suspension

5.2.4.3 Buffered Communication Ports and Dispatching Ports

5.2.5 Processor-to-Processor Communication

5.2.5.1 Interprocessor Communication Protocol

5.2.5.2 Processor Control Functions

5.3 Exception Handling

5.3.1 Notification

5.3.2 Fault Mechanism Data Structures

5.3.3 Context-Level Faults

5.3.3.1 Object Access Faults

5.3.3.2 Displacement Faults

5.3.3.3 Descriptor Control Faults

5.3.3.4 Computational Faults

5.3.3.5 Software Context Faults

5.3.4 Process-Level Faults

5.3.4.1 Reference Validity Faults

5.3.4.2 Restartable Suspended Operation Faults

5.3.4.3 Context Fault Failure Faults

5.3.4.4 Nonrestartable Faults

5.3.5 Processor-Level Faults

5.3.5.1 Process-Level Fault Failure Faults

5.3.5.2 Faults With a Process

5.3.5.3 uncorrectable Hardware Failures

5.3.6 Consistency Halts

5.4 Debugging Support

5.5 Initialization and Software-Controlled Reset

5.6 Alarm Handling

6.0 Floating Point Computation

6.1 Floating Point Model

6.2 Rounding Modes

6.3 Precision Control

6.4 Floating Point Exceptions

6.4.1 Invalid Operand

6.4.2 Overflow

6.4.3 Underflow

6.6.4 Divide by Zero

6.6.5 Domain Error

6.5 Floating Point Remainder Calculation

7.0 Generalized Data Processor Instructions

7.1 Class Field

7.2 Format Field

7.3 Reference Field

7.3.1 Data References

7.3.1.1 Segment Selector Component

7.3.1.2 Displacement Component

7.3.1.3 Scalar Data References

7.3.1.4 Static Vector Element Data References

7.3.1.5 Record Item Data References '7.3.1.6 Dynamic Vector Element Data References

7.3.2 Branch Reference

7.4 Op-Code Field

7.5 Instruction Interpretation

7.5.1 Physical Address Generation

7.5.1.1 Segment Selector Search

7.5.1.2 Access Descriptor Qualification

7.5.1.3 Directory Index Search

7.5.1.4 Segment Directory Register Reload

7.5.1.5 Segment Table Descriptor Qualification

7.5.1.6 Segment Descriptor Register Reload

7.5.1.7 Segment Descriptor Qualifications

7.5.1.8 Access right Qualification

7.5.1.9 Displacement Qualification

7.5.1.10 Altered Bit Update

7.5.2 Stack Interaction

7.5.3 Execution

8.0 Generalized Data Processor Operator Set

8.1 Character Operators

8.1.1 Character Move Operators

8.1.2 Character Logical Operators

8.1.3 Character Arithmetic Operators

8.1.4 Character Relational Operators

8.1.5 Character Conversion Operator

8.2 Short-Ordinal Operators

8.2.1 Short-Ordinal Move Operators

8.2.2 Short-Ordinal Logical Operators

8.2.3 Short-Ordinal Arithmetic Operators

8.2.4 Short-Ordinal Relational Operators

8.2.5 Short-Ordinal Conversion Operators

8.3 Short-Integer Operators

8.3.1 Short-Integer Move Operators

8.3.2 Short-Integer Arithmetic Operators

8.3.3 Short-Integer Relational Operators

8.3.4 Short-Integer Conversion Operators

8.4 Ordinal Operators

8.4.1 Ordinal Move Operators

8.4.2 Ordinal Logical Operators

8.4.3 Ordinal Arithmetic Operators

8.4.4 Ordinal Relational Operators

8.4.5 Ordinal Conversion Operators

8.5 Integer Operators

8.5.1 Integer Move Operators

8.5.2 Integer Arithmetic Operators

8.5.3 Integer Relational Operators

8.5.4 Integer Conversion Operators

8.6 Short-Real Operators

8.6.1 Short-Real Move Operators

8.6.2 Short-Real Arithmetic Operators

8.6.3 Short-Real Relational Operators

8.6.4 Short-Real Conversion Operators

8.7 Real Operators

8.7.1 Real Move Operators

8.7.2 Real Arithmetic Operators

8.7.3 Real Relational Operators

8.7.4 Real Conversion Operators

8.8 Temporary-Real Operators

8.8.1 Temporary-Real Move Operators

8.8.2 Temporary-Real Arithmetic Operators

8.8.3 Temporary-Real Relational Operators

8.8.4 Temporary-Real Conversion Operators

8.9 Access Environment Manipulation Operators

8.9.1 Access Descriptor Movement Operators

8.9.2 Type and Rights Manipulation Operators

8.9.3 Label Manipulation Operators

8.9.4 Segment Creation Operators

8.9.5 Access Path Inspection Operators

8.9.6 Object Interlocking

8.10 Branch Operators

8.10.1 Intrasegment Branch Operators

8.10.2 Intersegment Branch Operators

8.11 Communication Operators

8.11.1 Context Communication Operators

8.11.2 Coroutine Communication Operators

8.11.3 Process Communication Operators

8.11.4 Processor Communication Operators

Part 2. GENERALIZED DATA PROCESSOR AND SYSTEM INTERCONNECTIONS

9.0 Instruction Unit

9.1 General Operation

9.2 The Interchip Bus

9.3 The Microinstruction Bus

9.4 BP/F Lines

9.5 True and Done Lines

9.6 Interprocessor Communication

9.7 Instruction Unit Diagnostic Features

9.8 Initialization and Error Conditions

10.0 Execution Unit

10.1 General Operation

10.2 Clock and Special Lines

10.3 Address/Control/Data Lines

10.4 Functional Description

10.4.1 Data Manipulation Unit (DMU)

10.4.2 Control Unit (CU)

10.4.3 Reference Generation Unit (RGU)

10.4.4 Minor Circuit Blocks

11.0 Instruction Unit/Execution Unit Microinstruction Set

11.1 Memory and Operand Stack Access Microninstructions

11.2 Address Development Microinstructions

11.3 Data Manipulation Microinstructions

11.4 Floating Point Microinstructions

11.5 Communication Microinstructions

11.5.1 IP Manipulation Microinstructions

11.5.2 Segment Manipulation Microinstructions

11.5.3 Timer Control Microinstructions

11.5.4 Cache Management Microinstructions

11.6 Control Microinstructions

11.6.1 Instruction Unit Control Microinstructions

11.6.2 Instruction Unit/Execution Unit Control Microinstructions

11.6.3 Execution Unit Control Microinstructions

12.0 Summary of Instruction Unit/Execution Unit Operations

12.1 Three-Stage Pipeline

12.2 Stage One: Instruction Decoder (ID)

12.3 Stage Two: Microinstruction Sequencer (MIS)

12.4 Stage Three: Microinstruction Execution Unit (MEU)

12.5 Typical Processor Operation

Part 3. INPUT/OUTPUT ARCHITECTURE

13.0 Overall I/O System

13.1 Basic Structures and Facilities

13.2 Software Viewpoint

13.3 Data Transfer

13.3.1 Setup

13.3.2 Transfer

13.3.2.1 Synchronization

13.3.2.2 Termination

13.3.3. Cleanup

13.4 Beyond Data Transfer

13.5 Structural Overview

13.6 Supported Interfaces

14.0 Information Structure

14.1 Memory

14.1.1 Logical Addressing

14.1.2 Physical Addressing

14.2 Operand Formats

14.3 Operand Representation

14.4 Operand Positioning

14.5 Operand Integrity

14.6 Operand Stacks

14.7 Instruction Segments

14.8 Peripheral Interface Addressing

15.0 Input/Output Processing

15.1 Computational Data Types

15.1.1 Character

15.1.2 Short Ordinal

15.1.3 Short Integer

15.2 Environment Manipulation

15.3 Instruction Composition

15.3.1 Types of References

15.3.2 Operators

15.3.3 Data References

15.3.3.1 Explicit Data Reference

15.3.3.2 Stack References

15.3.4 Access Descriptor References

15.4 Operand Stack Behavior

15.5 Sequential Instruction Execution

15.6 Branching

16.0 Input/Output Object Structures

16.1 Segments

16.1.1 Input/Output Segments and Segment Descriptors

16.1.2 Peripheral Objects

16.1.2.1 Peripheral Control Segments

16.2 Operations and Contexts

16.3 Coroutines

16.4 Processes

16.4.1 Current-Event Ports

16.4.2 Event Ports

16.4.2.1 Event-Port Control Segments

16.4.2.2 Service Ports

16.5 Processors

16.5.1 Processor Objects

16.5.1.1 Interprocessor Messages

16.5.1.2 Request Interfaces

16.5.1.3 Event Lists

16.5.1.4 Event-Control Objects

16.5.1.5 Transfer-Control Objects

16.5.1.6 Bandwidth-Control Objects

16.6 Storage Resources, Transformers, and Labels

16.7 Processor Registers

17.0 Input/Output Facilities

17.1 Address Space Manipulation

17.2 Peripheral-to-Process Communication

17.2.1 Request Acceptance by a Transfer Controller

17.2.2 Request Acceptance by an Event Controller

17.3 Data Transfer

17.3.1 Block Transfer Operators

17.3.1.1 Block Data Transfer

17.3.2 Block Data Translation

17.3.3 Access Descriptor Transfer

17.3.3.1 Block Access Descriptor Transfer

17.3.4 Transfer Algorithms

17.4 Process-to-Process Communication

17.5 Processor-to-Processor Communication

17.6 Low-Level Initialization

18.0 Input/Output Processor Instructions

18.1 Op-Code Field

18.2 Reference Field

18.2.1 Data References

18.2.1.1 Explicit Data References

18.2.1.2 Stack References

18.2.1.3 Literals

18.2.1.4 Immediates

18.2.2 Access-Descriptor References

18.2.3 Branch References

18.3 Instruction Interpretation

18.4 Physical Address Generation

18.4.1 Execution

19.0 Input/Output Processor Operator Set

19.1 Character Operators

19.1.1 Character Movement Operators

19.1.2 Character Logical Operators

19.1.3 Character Arithmetic Operators

19.1.4 Character Relational Operators

B 19.1.5 Character Conversion Operators

19.2 Short-Ordinal Operators

19.2.1 Short-Ordinal Movement Operators

19.2.2 Short-Ordinal Logical Operators

19.2.3 Short-Ordinal Arithmetic Operators

19.2.4 Short-Ordinal Relational Operators

19.2.5 Short-Ordinal Conversion Operators

19.3 Short-Integer Operators

19.3.1 Short-Integer Movement Operators

19.3.2 Short-Integer Arithmetic Operators

19.3.3 Short-Integer Relational Operators

19.4 Access Environment Manipulation Operators

19.4.1 Access Descriptor Movement Operators

19.4.2 Type and Rights Manipulation Operators

19.4.3 Label Manipulation Operators

19.4.4 Segment Creation Operators

19.4.5 Access Path Inspection Operators

19.4.6 Object Interlocking Operators

19.5 Branch Operators

19.5.1 Intrasegment Branch Operators

19.5.2 Intersegment Branch Operators

19.6 Communication Operators

19.6.1 Context Communication Operators

19.6.2 Coroutine Communication Operators

19.6.3 Process Communication Operators

19.6.4 Processor Communication Operators

19.7 Block Transfer Operators

INTRODUCTORY DESCRIPTION OF THE INVENTION

Referring now to FIG. 1, the following introductory description broadly describes the various elements of the system in which the invention is embodied and provides an introduction to some of the terminology used throughout the following specification. FIG. 1 illustrates the various agents in the system and the mechanisms that they utilize. Arrows in the figure denote the following. The agent is located at the source of the arrow and the mechanism that the agent is using is located at the destination of the arrow. Two kinds of agents are shown, processes that are in a particular state, and the processors that the processes are executed on.

Object Creation, Addressing and Typing

All information within the system is represented by hardware-recognized, memory-resident, information structures called objects. There are two basic types of objects: data segments and access lists. Access lists control access to objects and data segments are used to contain data scalar values.

The system provides an object-creation mechanism (10) in hardware for supporting object creation dynamically. This mechanism is based upon a particular kind of object called a storage resource object, which describes the various areas of physical memory that are not currently allocated. By utilizing a specific set of hardware-supported algorithms, the mechanism performs, upon request, the allocation of data segments of either one of the two basic object types. Once a set of objects have been created, a given process running on a given processor may generate references to these objects. These references are mapped or developed into physical addresses for the main memory by means of a mechanism called the object-addressing, protection and typing mechanism (12). This mechanism provides the means by which any one reference to an object can be converted into a physical address for that object. This object-addressing mechanism makes use of what is called an access path to the object. For example, in a simple case, the access path is comprised of three levels. The first level employed in the development of the address is called an access descriptor which is contained within the type of object called an access list. Access descriptors describe the kind of access that the user of the access descriptor has to the object at the base of the access path. An access descriptor describes the kind of rights, for example, read rights or write rights, which define various kinds of access (depending upon the type of the object) that the holder of the access descriptor has for that object.

At the next level down the path to the object for which the reference was generated and the address is being developed, there are segment descriptors. The system employs a two-level segmented addressing space. That is, there are two levels of segment tables. The highest level segment table is called a segment table directory. In it are found segment descriptors for segment tables. An access descriptor contains two components that are used in selecting the segment descriptor to use in the address development. The first reference selects from the segment table directory the segment table in which the final segment descriptor should be found. The second reference selects out of that segment table the segment descriptor for the segment in question.

The segment descriptor for the object for which addresses are being developed contains information which locates that object in a physical memory, gives its length, gives various typing information about the object, and includes various memory management information (such as the count of the number of access paths to this object, information about whether the segment had been altered or referenced, etc.).

Individual Process Environment

Various process environments (14 and 16) are shown in FIG. 1. The current process access environment (18, 20) is shown at the front and the past history (22, 24) (process environments that are not currently invoked) is shown toward the back of the drawing. The instantaneous state of these process environments is illustrated and referred to as the current process image (26, 28). As described above, a process running on a processor generates references while the processor translates into a physical address using the object addressing, protection, and typing mechanism. A context object represents a process environment in which a particular instance of an operation can be executed. Over a period of time a process, which is the site for potential or parallel activity, may move between contexts in its execution.

A context object in the present system has four components. These four components are four access lists containing access descriptors. Given the sum total of the access descriptors in this environment one can tell exactly what kind of access that environment provides to the various objects for which there are access descriptors.

Intercontext Communication

Each one of the contexts as a minimum must contain access descriptors for all of those objects that the operation in that environment can access. One operation may need over a period of time to call another operation in order to support modular programming. Since the second operation may not be defined to work or operate in the same environment as the first operation, a mechanism is provided for transferring control from one environment (and the operation in it) to an operation in another environment. This mechanism is called the intercontext communication mechanism (30, 32 in FIG. 1). There are two kinds of intercontext communication. One kind supports downward call/upward return or call/return kinds of control transitions. The second kind is called nonhierarchical communication or coroutine communication. This kind of communication supports the hierarchical or asynchronous kinds of communication between contexts supported by the call/return mechanisms and supports synchronous control flow-patterns, such as encountered among coroutines. The program environments called contexts are retentive in nature. That is, they are not necessarily created immediately prior to or part of control flow entering them, and they are not immediately destroyed after or as part of control flow exiting from them. They have a longer lifetime than merely the control flow patterns that use them or traverse through them.

Contexts have a static component and a dynamic component. The static component of any context is made up of a two-component object called a domain. A domain refers to the domain of definition of the operation which is to execute within that context. The two components of a domain consist of a public access list and a private access list. This partitioning allows the domain to support the kinds of semantics called for by certain modern programming languages. In those terms, all the public operations of a given intended type are made available via the public access list while the hidden data or operations of the type are made available by means of the private access list.

The dynamic component of any context is called the context access list. The context access list provides an instance-specific, access descriptor working space. It is within this space that an instance of a particular operation defined within a given domain of definition does its dynamic access descriptor manipulation.

Another component which is dynamically selectable by a given context is what is called an entry access list. Any access list, for which a given context bears appropriate rights, can be selected and made a part of the current access environment by means of the entry access list.

Interprocess Communication

Two processes may need to communicate with each other but are scheduled, and thus run, in an asynchronous manner on one or more processors. A buffering mechanism, called the interprocess communication mechanism (34), is provided such that the timing differences between the two processes can be accommodated. Interprocess communication is supported by means of a hardware-recognizable object called a buffered communication port. The buffered communication port is a queueing mechanism wherein messages which one process wants to send to another process are queued and wherein processes which are waiting to receive a message are queued. These ports with their queueing ability thus provide the buffering needed to smooth out the asynchronous behavior of the two processes.

Dispatching Mechanism

Once a waiting process has received a message at a buffered port, the process is ready to run on one of a number of available processors (38, 40). The dispatching mechanism (36) provides a way for the process to be scheduled on a processor. The dispatching mechanism is a hardware mechanism which automatically does the scheduling and dispatching of ready-to-run processes in accordance with previously-set software parameters. In this way the dispatching mechanism enforces a previously-specified software scheduling policy or low-level scheduling policy on all of the processes within the system. If one were to simply assign a process to a processor with no control over how long that process should execute on the processor, then that process would run through completion on that processor. If the process were one that was never ending, the processor would be assigned to that process forever. The dispatching mechanism is provided so that software may specify how the processes are multiplexed over time with respect to the processors. The dispatching mechanism does not support preemptive forms of scheduling policies, but does support a family of what is referred to as relative-frequency scheduling policies. Two values are provided with every process when it is being queued at a dispatching port. The first is its maximum allowable delay and the second its maximum allowable service period. Using these two values, a range of relative-frequency based software scheduling policies are achieved from round robin to pure relative frequency.

Service period information is provided so that when a processor removes a process from a process queue or from a request queue in a dispatching port, the processor can tell how long software desires that this process be bound to the processor. This ensures that there are no runaway processes that tie up a processor forever. After a service period is over, the bond between a process and the processor is broken forces the dispatching mechanism to allow other processes to be assigned to a processor.

Interprocessor Communication

As previously described, the buffered port mechanism is utilized to bind a message to a process and the dispatching mechanism is utilized to schedule the process on an available processor. The processor with the message/process pair examines the appropriate dispatching port. If no processor is queued at that port, then the message/process pair is queued at the port to wait for an available processor. If there is a processor queued at the dispatching port awaiting the arrival of a service request (a message/process pair), then the processor that sent the message can bind the service request to the waiting processor. The interprocessor communication mechanism (42) is the means by which the requesting processor communicates to the waiting processor that it can begin executing the process which has been bound to it.

The interprocessor communication mechanism is also used to allow software running on one processor to ask another processor to perform certain diagnostic functions, such as performance of an initialization sequence, an alarm sequence, or a reset sequence. This allows the debugging of a processor within the system while the system is running.

Another use of the interprocessor communication mechanism is to communicate with a specific processor or broadcast to all processors within this system to thereby inform them that they should requalify certain information maintained on the processor about the address development mechanism.

The interprocessor communication mechanism is also used to support recovery from processors which have malfunctioned by causing these processors to stop functioning. The mechanism also supports reconfiguration so that processors can be inserted and removed from the system dynamically.

The interprocessor communication mechanism is structured as follows. Each processor has associated with it a local communication segment, stored in a common memory. The local communication segment is for processor-specific communication. Another segment, the global communication segment, is common to all processors, and is for system-wide communication.

Each communication segment has a field containing control flags. The flags are set by one processor and later inspected by another processor. The inspecting processor is instructed to perform a number of functions specified by the state of the control flags. A count field and a lock field are provided in all communication segments to interlock access to the communication mechanism.

Processor Types

Many types of processors are accommodated by the present system. Two types of processors are described in detail, Generalized Data Processors (GDP) and I/O Processors (IOP). A GDP functions within an address space and can only reference objects that are within that space. An IOP is able to reference objects in two different spaces and functions on the boundary between these two address spaces. The first address space is the same address space that the GDP uses. The other address space that any particular IOP uses is called an IO address space and is separate and does not intersect the GDP address space, i.e., the address spaces share no common addresses.

The main purpose of a GDP is to perform generalized computation over a wide spectrum of data types supported by this type of processor. The function of an IOP is more restricted with respect to the number of data types supported. The main purpose of an IOP is to transfer data between the two address spaces that it has access to and can reference. An example would be the transfering of data from an input device which exists in the I/O address space, into a data segment which exists in the GDP address space. Conversely data is transferred from a data segment in the GDP address space to an output device which exists in the I/O address space.

An IOP uses the same descriptor-controlled, segment-based address development mechanism as the GDP. The I/O operations also execute in a context-based environment similar to that provided for the GDP. An IOP uses the same interprocess communication mechanism and IOPs are selected for service via a dispatching mechanism which is similar to that described above. A similar interprocessor communication mechanism is utilized.

A different addressing mechanism must be employed for an IOP because there must be some way to tell that a segment being referenced is an I/O address space or is a GDP address space. There are also special considerations in referencing segments such as timing considerations dealing with a specific kind of device.

Special hardware is provided in an IOP to improve the performance of data transfer operations. This makes it possible to transfer blocks of data.

An IOP dispatches processes from a different dispatching port than a GDP. This avoids the necessity of having to examine processors queued at a particular dispatching port to find one of the correct type, i.e., a GDP or an IOP. To simplify the mechanism, GDPs in a system dispatch processes from one type of dispatching port. On the other hand, an IOP uses a different type of dispatching port, and not all of them have access to the same port. This is because not all of the IOPs have access to all I/O devices. Therefore, not all I/O processes, if they are to serve only their particular device, can be associated with any IOP. In general, out of a set of IOPs there will only be some small number which will have access to any particular I/O address space. For example, the number might be as small as one IOP to one peripheral device. On the other hand, it can also be the case that several IOPs will service several peripheral devices on one I/O bus which serves as one I/O address space. For this reason the mating of I/O processors to dispatching ports for I/O processes is as follows. All the IOPs that have access to one I/O address space (when in normal dispatching state) will dispatch I/O processes from one input/output process dispatching port.

PART 1. GENERALIZED DATA PROCESSOR ARCHITECTURE

1.0 OVERALL SYSTEM

1.1 SEGMENTED ADDRESSING

Refer now to FIGS. 2A and 2B. Segments (44) are the basis for all addressing and protection in the present system. Conceptually, a segment is simply a single, linear address space with a defined size or length. In practice, segments may exist in main memory and be associated with a starting or base address (46). To determine the actual physical address of an item of data within a segment, one simply adds the position of the item within the segment, called its displacement (48), to the segment's base address (46). To realize a simple, but important form of protection, one checks the displacement, before adding it to the base address to be sure that it does not exceed the defined length of the segment.

In conventional systems with segmented addressing, an effort is often made to keep the base addresses of segments apart from any displacements into them and to delay the formation of physical addresses until the last possible moment. When a physical address is needed, it is formed by adding the desired displacement to the base address as described above. The hope is that if these steps are taken, moving a segment will only require the updating of its base address. Unfortunately, in these systems nothing is ever done to prevent the base-address information from getting distributed throughout memory and in the processor's registers. This means that if a segment is moved, not simply one, but possibly hundreds of copies of its base address will have to be located and updated to reflect the change. Without extraordinary care on the part of the programmer, this process can be virtually impossible to carry out in a reasonable amount of time and in a reliable manner.

To avoid the problem of finding and updating a multitude of base addresses each time a segment is moved, the present system makes two fundamental improvements in segment-address management. First, it brings together all of the information about a segment (e.g., its current base address and length) and places that information in a segment table (50) along with the same information about all of the other segments in the system. Second, it requires that all references to a segment obtain the necessary base address and length information from this table. To change the base address of any segment, or to redefine its size, one simply changes its entry or segment descriptor (52, 54) in the segment table. Any reference to the segment will access the segment descriptor and obtain the correct and current base address (46) and length information (48).

Centralizing segment-address information is not, however, a complete solution to the problems associated with a segment-based addressing architecture. For example, it is often advantageous to be able to restrict the number of segments accessible to a given program to some artibrarily small set. With all of the segment information centralized, any program, whether it needs to or not, can find and address any segment in memory by simply indexing through the segment table. Centralizing the segment table can also lead to problems with the size of the index required to index through it. In the present system, the segment table can contain descriptors for over two million segments, implying a 21-bit segment table index for full access. If every operand address required that many bits to select the desired segment, in addition to a useful displacement size, instructions and programs would grow beyond all reason.

To eliminate the problems described above, the system provides a second level of address mapping above that provided by its segment table. Each independently-translated program unit or module is supplied at run-time with a list of segment numbers (i.e., indices for segment descriptors) for all the segments it may need to access during execution. The program selects a particular segment by specifying, as part of each operand's address in an instruction, an index into its list of accessible segments or its access list. Notice now that the index is known only to this particular program module because other modules have their own access lists and are thus able to use their own locally-known indices into them.

Since the only entries in a module's access list are for the segments it may need to access, the size of the index needed to select amongst them is, in general, much smaller than the total number of possible segments. This helps keep the local index small which in turn helps reduce the size of instructions and programs. At the same time, the access list limits the set of segments accessible to a program to exactly the set that it requires for its operation. This ability to restrict a program's accessibility, when combined with the ability to verify that displacements fall with the defined limits of segments, forms the foundation of the protection system of the present invention.

1.2 SEGMENT TYPES

Segments are used to hold all sorts of useful information in the system. For example, a segment is used to hold all of the information in the segment table (50). More precisely, a segment is used to represent the segment table's data structure in memory. In a similar way, a segment is also used to represent the access list of a program module. Segments, in fact, are used to hold data, instructions, and anything else that need a storage representation in the system.

With segments used to represent so many different things, it becomes apparent that being able to tell exactly what type of information a particular segment represents could be quite advantageous, especially from the point of view of protection. For example, if it was known that a particular segment were representing the segment table and a program inadvertently tried to execute its segment table data as instructions, the error could be detected and the program aborted before any damage might be done. Recognizing the usefulness of assigning types to segments, the system includes some additional information in each segment descriptor (52, 54). This information is used by a processor during execution to check the kind of access being made to the segment against what the segment's type definition (56) says it will allow. The type definition (56) includes both base-type and system-type information, described below. Any disagreement between the kind of access being made and the type definition causes an error.

There are two fundamental types of segments in the system. The first type is called the data segment and is used to represent almost every kind of data structure a programmer might choose to define, such as arrays, lists, and queues. It is also used to represent several important data structures that are hardware-recognized, such as the segment table. When a data segment is being used simply as that, a data segment, the base-type information (46) in its segment descriptor also indicates it's being used just as a data segment. If the segment is being used to represent some data structure that is recognized and used by the hardware, its base-type information again indicates that it is a data segment, but its system-type information (47) located next to the base type in its segment descriptor, indicates that the segment is being used for a special function. Examples of this two-level typing include data segments used to hold instructions (i.e., base type-data segment, system type-instruction segment) and data segments used as first-in, last-out stacks during arithmetic expression evaluation (i.e., base type-data segment, system type-operand stack).

The second fundamental type of segment in the system is the access list (AL). As mentioned above, an access list contains the indices for all of the segments accessible to a given program module. To guarantee that these indices are not manipulated, either accidentally or maliciously, by any program, access lists are absolutely inaccessible as data segments. The hardware simply will not operate on the information contained in an access list as data. The ability to preserve the absolute integrity of access lists is another fundamental concept in the protection system of the present invention.

Access lists, like data segments, can also be used to represent both programmer-defined and hardware-recognized information structures. Unlike data segments, however, access lists cannot represent structures of primitive data (e.g., integer arrays, character strings, etc.). Instead, the information structures they represent are collections or groupings of several entire segments. Since the segments referenced by an access list can be other access lists or data segments, they may be used to build arbitrarily complex, segment-based information structures. When an access list is used to represent a software interpreted, multisegment information structure, the base-type information in its segment descriptor indicates that it is an access list and that it has no other special function. When an access list is used to represent a multisegment structure with a hardware-recognized function, that function will be indicated by the system-type information in its segment descriptor. The following description, with reference to FIGS. 2A, 2B, 3A, 3B, 4A, and 4B, introduces a variety of these hardware-recognized, multisegment structures and describe their importance to the system architecture. Each system object shown in the figures is labeled as to its base type, i.e., base type=AL (access list) or base type=data (data segment). A more detailed description of system objects appears under the heading "System Object Structures."

1.3 OBJECTS

With the great variety of information structures that can be built from access lists and data segments, it soon becomes difficult to know each structure in detail. As a conceptual aid, it becomes easier to view each type of structure as a single amorphous entity or what is called an object. Once this view is taken, the apparent complexity of the many segment-based information structures used in the system is greatly diminished.

For every hardware-supported function in the system, from instruction execution to interprocess communication, there is a particular type of object, from a simple data segment to some arbitrarily complex network of access lists, data segments, and other objects, that is accessed and manipulated specifically by that function. In most cases, however, the programmer may completely ignore the internal organization of the object and yet remain confident that whenever an operator or function is applied to it, the object's type and structure will be verified by the hardware to be consistent with its definition and with the function specified.

Although the system makes many objects and their functions available to the programmer, it is often the case for the objects used by a given program that only a subset of the functions are actually required by the program. To allow for the specification of this subset, each entry in an access list is equipped with some additional information. When this information is combined with the type information available from the entry's associated segment descriptor, it defines the subjset of access rights available to the program for this object. This is why entries in an access list are called access descriptors. For not only do they describe which segment or object is accessible, but how it can be accessed as well.

Data segment access descriptors (i.e., access descriptors for data segments) are a good example of the kind of access control provided by access descriptors. If a data segment is being used just to hold data (i.e., no special hardware-recognized use is intended), the two essential access rights possible are read and write. An access descriptor for such a segment can indicate that its data can be read, can be written, can be read or written, or can be neither read nor written. If two different programs should happen to use the same segment in a cooperative manner, an access descriptor in an access list for one of the programs may allow only reading, while an access descriptor in an access list for the other program may allow the data in the segment to be both read and written.

Acces list access descriptors are also defined to have both read and write access rights, but the meaning of these rights differs considerably from that of the same rights applied to data segments. To be allowed to read an access list means to be able to copy or move any one of its access descriptors into another access list. Similarly, to be allowed to write an access list means to be able to replace one of the access descriptors in the list with another. Naturally, the integrity of the system protection system depends upon the absolute inability to do anything else to an access descriptor, such as altering the information inside of it.

As mentioned above, a variety of complex objects can be built from the two basic types of segments, data segments and access lists, and several of these object types are recognized by the system hardware. Most significantly for the hardware-recognized types, segment descriptors automatically identify a segment as to both its base type and its system type to the hardware. It becomes necessary, however, in more advanced software systems, to allow the programmer to define and distinguish new types of objects that are beyond the knowledge of the hardware. To support this requirement, the system provides a facility that lets the programmer extend the number of object types available to an almost infinite number. An object defined as a programmer extended type is identical to an object of a hardware-recognized type with one exception: access descriptors for the object are able to select both a segment access descriptor for the object and a programmer-defined type label. Since the hardware cannot do anything with an extended type object, other than recognize that it is such an object, it becomes necessary for the programmer to define the object's manipulations in software. Several basic mechanisms for simplifying this task are available. Among them are the ability to read an extended object's type label into a data segment and the ability to compare two such labels for equality. If the programmer insists that the hardware take greater precautions with an extended type object, the object can be hidden behind its label. Hiding an extended type in this manner will cause the hardware to insist on the presentation of the appropriate matching label before exposing the object. These facilities allow the programmer to provide, in software, many of the same kinds of checks provided by the hardware for recognized objects.

Many different labels can be applied to the same object, and the same label can be applied to many different objects. Since a labeled object behaves for the most part like any other kind of object, labeled objects themselves can be labeled. Logically speaking, each time a label is applied to an object, a new access path is created. The hardware guarantees that any access along this path will encounter the programmer-defined label. It the object is not hidden, the label can be bypassed, otherwise a matching label (i.e., a protected key) must be presented by the programmer in order to acces the object. Since paths are often formed hierarchically by applying a label to a previously-labeled object, paths are said to have levels of labeling. For this reason the hardware-recognized data structure used in segment tables to represent a level of labeling is known as a path level descriptor (see, for example, 60, 62 FIG. 2B).

As comprehensive as the system facilities are for the definition, identification, and manipulation of objects of all types, such facilities would not be complete without the availability of a flexible dynamic storage allocation mechanism. The allocation mechanism (77, FIG. 2B) provided by the system supports the instantaneous allocation of both storage and segment table space for new data segments and new access lists. The object typing and labeling facilities mentioned above permit the simple and direct construction of both hardware-recognized and programmer-defined object types.

1.4 FUNCTIONAL HIERARCHY

Refer now to FIGS. 3A and 3B. The system architecture is designed as a hierarchy of functional levels. At the lowest level of this hierarchy are the individual instruction fields consisting principally of operand references and operator codes. These fields may be combined to form a significant number of useful instructoons on a variety of primitive data types and structures. To define a complete procedural action or operation, as it is called in the present system, a sequence of instructions can be placed into a hardware-recognized object called an instruction segment (90). Only instructions obtained from such an object executable. Any attempt to execute instructions from some other type of object is considered a program error. Note that operations are not equivalent to instruction segments. This is because several instruction segments may be required to represent one operation, although no "operation object" type is defined to represent such a composite. The term operation is used in this specification to refer to an abstract operation object consisting logically of one or more instruction segments.

The next level in the system functional hierarchy defines a grouping or collection of operations. This grouping is usually based on the logical association of some set of operations for the manipulation of an object of some type. For example, a set of operations that would naturally be grouped together would be the set defined to manipulate an object of the type used to represent a dictionary. The set of operations might include procedural actions to look-up an entry in the dictionary, to insert a new entry, or to remove an old entry. Note that a group of operations defined in software to manipulate a particular type of object has an unmistakable resemblance to a set of operators defined in hardware to manipulate a primitive data type. The term operation is, in fact, intended to suggest the notion of a "software operator" which can be thought of as the software equivalent to a hardware operator.

The hardware object used to represent a logical grouping of operations is called a domain (92). While it is possible for a domain to represent nothing more than a collection of operations or, more precisely, access to a collection of operations, most of the time a domain will associate other objects with a set of operations as well. These objects usually contain the constants, variables, and access descriptors that are used in common by all of the domain's operations. For this reason, a domain is considered to be more than just a grouping, but rather an environment in which, along with various other objects, one of several possible operations can be accessed.

The environment provided by a domain is not, however, a sufficient one in which to execute an operation. Additional access must be provided. For example, many operations require parameters to be passed to them before they execute, and they need room for local variables and temporaries for use in expression evaluation. The environmental requirements of an executable operation simply go beyond the intended function of a domain object.

The key to building an environment in which an operation can execute is the creation of a hybrid access environment, combining the static properties of a domain with the dynamic aspects of an operation ready for execution. The hardware-recognized object that does just that is called a context (94). A context is an access environment (i.e., an access list) that is created prior to the execution of an operation and includes access to the domain in which the operation is defined. The context access list of a context includes working space for the access descriptors of local data segments, parameter objects, and the special object used for local expression evaluation, a first-in, last-out operand stack.

Once an operation is given a context in which to execute, it begins to exhibit more of the behavior usually ascribed to subroutines and procedures. For example, contexts (i.e., operations in contexts) are able to call and return to one another in subroutine fashion. The return link (96) for a calling context is conveniently stored in the context access list of the called context (94). Calling a context can, of course, produce significant changes in the access environment of a computation. Calling a context for an operation defined in the same domain as the caller only changes the environment's context specific components. The domain component remains the same. Calling a context for an operation defined in another domain changes all the components of a computation's access environment.

Being able to simply move from one context to another to experience such a complete change in access environments provides the system with another very useful form of protection. A domain can easily be defined with access to a particularly important block of information or data base. With that in place, the operations of the domain can be defined to manipulate the information in precisely the manner necessary to ensure its integrity. The only way then to access the information in the domain is to create a context for one of the operations in the domain and call it. The data base is completely protected against accidental or malicious modification. To even further enhance the information-hiding capability of a domain, the domain object (92) itself is designed to be partially hidden. If one domain has access to another domain, via an access descriptor for it, then from within a context for an operation defined within the former, only the objects found in the public access list (98) of the latter may be freely accessed. What remains hidden to the calling context is actually the other half of a two-part domain object called its private access list (100). The only way to access the objects found in a domain's private access list, is to transfer control to a context for one of its operations, in particular, to any context accessible via its public access list.

Should only access descriptors for instruction segments (108) be present in the domain's public access list (98), the calling context will find it necessary to first create a context for an operation to be called before calling it. Note that the hardware allows the dynamic construction of contexts for operation in domains different from the domain of the creating context without compromising the protective aspects of the created context or its domain. In other words, one context having access to another can only call it. The context access list of the called context and, therefore, its set of locally accessible objects, is not publicly accessible.

Normally, control (i.e., the locus of processing activity) moves from context to context in a hierarchical manner, as they call and return to one another much like subroutines. Occasionally, the need arises to transfer control between contexts in a more arbitrary manner including transferring from one context to another, and then to a third, and then back to the first again, in a cycle. (Note that this is not recursive control flow. That would involve creating a new context for each call of the same operation). Cyclic control flow means that that control actually resumes in the same context each time around the loop. Another more arbitrary control structure is the pipeline, where control enters and exits one context and then another, never to return again. To support these nonhierarchical control structures, contexts in the system are created prior to the time they receive control and are retained (i.e., not deallocated or reinitialized) after the time they relinquish control. That is why a context is not simply a procedure, in the ALGOL sense, which is defined to go into and out of existence at the same time it gains and gives up control. Contexts, of course, can be used to model procedural environments, as well as almost any other form of control and enviroment discipline, by explicitly creating and deleting contexts at the appropriate times. The term coroutine is used in this specification to refer to any context that operates in a nonhierarchical manner.

Refer now to FIGS. 4A and 4B. A sequential computational activity or process is characterized by a series of context and domain transitions resulting from transfers of control between contexts. Since more computational processes may exist than physical processors, the architecture provides a facility for automatically switching or multiplexing the available processors among ready-to-run processes. This is done by abstracting or virtualizing the notion of a processor. Physical processors may associate themselves, for a given period of time, with the virtual processor of a given computational process. When the physical processor disassociates itself from the virtual processor, the state of the computation is stored in memory as the state of the virtual processor. This allows for the convenient resumption of processing for that virtual processor whenever another physical processor of corresponding type is available. In the present system a different virtual processor is defined for each computational process, and so the terms virtual processor and process are used synonymously. In the remainder of this specification, however, the term process is used almost exclusively.

To maintain the state of the virtual processor associated with each independent process, the system makes use of another type of hardware-recognized object called a process object (140). In addition to the process state, this object contains information, previously stored there by software, that is used by the hardware of the system in an automatic allocation of processing resources and memory space. Another object, called a processor object (142), is assigned to each processor to maintain its state information and to determine the set of processes which it is to serve.

1.5 COMMUNICATION

Refer again to FIGS. 3A and 3B. A different communication mechanism is provided for the program objects at each level in the system architectural hierarchy. At the lowest level, communication between instructions takes place via commonly-accessible memory locations including last-in, first-out stacks for temporary scalar operands. The normal sequential flow-of-control from instruction to instruction can, of course, be altered by both unconditional and conditional branching. Because execution at this level is always sequential, no buffering or interlocking of instruction communication is required.

At the next level, communication between contexts, interacting conventionally as subroutines or procedures, is based on the transmission and reception of messages. Information to be transmitted is first assembled into a message object (102). If the information is simple scalar data, the message object is simply a single data segment. For the transmission of more complex information, the message object is instead an access list containing descriptors for other access lists, data segments, and objects. In all cases the message is treated as a single, but arbitrarily complex object. To transmit a message, the hardware simply moves the access descriptor (112) for the message object from the sending (caller's) context to the receiving one. Needless to say, this form of intercontext communication is fast, flexible, and extremely powerful.

When one context calls another hierarchically, in the manner of a subroutine or procedure, a return link (96) for the calling context is also passed to the called context as a separate argument message. The link, again in the form of an access descriptor, can be used by the called context (94) to return control along with a result message to the calling context (95) when desired. Significantly, the only difference between calling a context and returning to a context is that in the latter case no return link is supplied.

Messages also form the basis for communication between contexts that do not demand a strict call/return hierarchy. Unlike hierarchical context communication, however, nonhierarchical context or coroutine communication requires somewhat more selectivity over various potential callers. Whereas an ordinary context is subject to call by any one of its potential callers, a coroutine may dynamically choose to accept control and communication from only a subset of the coroutines which may call it. This selectivity is made possible by another type of hardware-recognized object called a nonbuffered communication port (104). In order to specify the particular port over which it desires to accept messages and obtain control, a coroutine suspends itself at that port whenever it transfers control and passes a message, via another nonbuffered port, to some other coroutine. From that point onward, the coroutine will only accept control and a message via the port at which it is suspended. Any other attempt to pass control and information to the coroutine, via any other nonbuffered port, is treated as an error. Despite the selectivity available, coroutine communication does not require any form of buffering or interlocking since coroutines, by definition, communicate with one another in a sequential manner.

Refer again to FIGS. 4A and 4B. At the topmost level in the functional hierarchy, the communication mechanism for potentially asynchronous sequential processes is fully buffered and interlocked. Both of these functions are provided by another type of hardware-recognized object called a buffer communication port (144). Since the relative speeds of independent processes are not predictable, the buffering provided by a port is rather extensive. Each buffered port provides two queues: one for messages that have been sent and one for processes that are waiting for messages to arrive. When one process sends a message to a port at which no other process is waiting, it simply places an access descriptor for the message in the port's message queue (150) and continues to execute. Sometime later, when another process attempts to receive a message at the same port, it immediately receives the message and continues to execute. If the receiving process does not find a message queued at the port, it places an access descriptor for its process object in the port's process queue. Sometime later, when a message arrives and the process is at the head of the port's process queue, the sending process removes the waiting process from the queue and makes it available for further execution.

In addition to providing the buffering and interlock required for asynchronous interprocess communication, buffered ports offer several other important capabilities. For example, by allowing more than one process to send messages through the same port and more than one process to receive messages through that same port, several identical processes, free to operate in parallel on several identical processors, may provide simultaneous service to a number of other client processes. This feature can be used effectively in advanced real-time systems to adjust and improve response time during peak-load periods. Since a process is free to receive at any port it can access, it may be arbitrarily selective in its processing of incoming-message traffic, much in the manner of a coroutine. A port may also be used in a simpler manner for supporting sophisticated forms of programmed mutual exclusion commonly found in resource management software. The ability of buffered ports to queue waiting processes, in addition to sent messages, completely eliminates the kind of busy waiting that would have a process endlessly testing or spinning on a lock bit to determine the arrival of a message. Certain hardware functions in the system do make use of spin locks, but special techniques are employed to avoid unnecessary memory contention during actual spin situations.

Logically, the assignment of processes to processors is supported by the same type of queued communication provided by buffered ports. That is, a process that is ready for further execution, is treated just like a message for one of possibly several receiving processors. To receive a process, a processor waits at a dispathing port (146) until a process arrives, just as a process might wait at a buffered port to receive a message. The logical equivalence of physical processors, virtual processors, and processes is clearly evident in this mechanism, for the system also permits one process to receive another process as a message. Although it is not able to directly execute the process, the receiving process may inspect, delay, or interpretively execute the received process before resending it as a message to a physical processor or perhaps some other process.

Normally, a process leaving the process queue of a buffered port is sent directly to a dispatching port for processor assignment. The particular dispatching port is specified by an access descriptor (148) in the buffered port itself. Should the buffered port not contain an access descriptor for another buffered port, the access descriptor for the process is sent there instead. This aspect of the system's communication facilities has significant practical consequences in operating system design. Through this mechanism software schedulers or other service processes can be interposed between hardware schedulers in a totally transparent manner.

The same type of interprocess communication described above is employed between the processes associated with general data processors and those associated with input/output processors. This is consistent with the asynchronous nature of input/output and eliminates the need for interrupts to the general data processors. All ordinary interrupts, direct memory access requests, etc. are handled by the input/output processors. After completing the necessary device service functions, the input/output processes communicate