 |
Description  |
|
|
RELATED
INVENTIONS
The present invention is related to the following inventions, all filed on May 6, 1985, and all assigned to the assignee of the present invention:
1. Title: Nested Contexts in a Virtual Single Machine
Inventors: Andrew Kun, Frank Kolnick, Bruce Mansfield
Ser. No.: 730,903, now abandoned
2. Title: Computer System With Data Residence Transparency and Data Access Transparency
Inventors: Andrew Kun, Frank Kolnick, Bruce Mansfield
Ser. No.: 730,929 (now abandoned) and Ser. No. 07/110,614 filed on Oct. 14, 1987 and now abandoned (continuation)
3. Title: Network Interface Module With Minimized Data Paths
Inventors: Bernhard Weisshaar, Michael Barnea
Ser. No.: 730,621, now U.S. Pat. No. 4,754,395
4. Title: Method of Inter-Process Communication in a Distributed Data Processing System
Inventors: Bernhard Weisshaar, Andrew Kun, Frank Kolnick, Bruce Mansfield
Ser. No.: 730,892, now U.S. Pat. No. 4,694,396
5. Title: Logical Ring in a Virtual Single Machine
Inventor: Andrew Kun, Frank Kolnick, Bruce Mansfield
Ser. No.: 730,923 (now abandoned) Ser. No. 183,469 filed on Apr. 13, 1988 and now U.S. Pat. No. 5,047,925 (continuation)
6. Title: Virtual Single Machine With Message-Like Hardware Interrupts and Processor Exceptions
Inventors: Andrew Kun, Frank Kolnick, Bruce Mansfield
Ser. No.: 730,922 now U.S. Pat. No. 4,835,685
The present invention is also related to the following inventions, all filed on even date herewith, and all assigned to the assignee of the present invention:
7. Title: Computer Human Interface Comprising User-Adjustable Window for Displaying or Printing Information
Inventor: Frank Kolnick
Ser. No.: 000,625 now abandoned
8. Title: Computer Human Interface With Multi-Application Display
Inventor: Frank Kolnick
Ser. No.: 000,620 now abandoned
9. Title: Self-Configuration of Nodes in a Distributed Message-Based Operating System
Inventor: Gabor Simor
Ser. No.: 000,621 now U.S. Pat. No. 5,165,018
10. Title: Process Traps in a Distributed Message-Based Operating System
Inventors: Gabor Simor
Ser. No.: 000,624 now abandoned
11. Title: Computer Human Interface With Multiple Independent Active Pictures and Windows
Inventor: Frank Kolnick
Ser. No.: 000,626, now abandoned
TECHNICAL FIELD
This invention relates generally to digital data processing, and, in particular, to a human interface system providing means for converting "real" input into virtual input, and means for converting virtual output into "real" output.
BACKGROUND OF THE INVENTION
It is known in the data processing arts to couple a wide assortment of input and output devices to a data processing system for the purpose of providing an appropriate human interface. Such devices may take the form of keyboards of varying
manufacture, "mice", touch-pads, joy-sticks, light pens, video screens, audio-visual signals, printers, etc.
Due to the wide variety of I/O devices which can be utilized in the human/computer interface, it would be very desirable to isolate the human interface software from specific device types. The I/O should be independent of any particular "real"
devices.
There is thus a need for a computer human interface which performs I/O operations in an abstract sense, independent of particular "real" devices.
BRIEF SUMMARY OF INVENTION
Accordingly, it is an object of the present invention to provide a data processing system having an improved human interface.
It is also an object of the present invention to provide an improved human interface system which performs input/output operations in an abstract sense, independent of any particular I/O devices.
It is another object of the present invention to provide an improved human interface system in which any type of "real" input and output devices may be employed, and in which I/O devices may be connected to and disconnected from the data
processing system without disrupting processing operations.
These and other objects are achieved in accordance with a preferred embodiment of the invention by providing a virtual input interface in a data processing system, such interface comprising means for accepting input from at least one physical
device, means for converting the physical device input into virtual input, and means responsive to the virtual input for performing processing operations upon the virtual input.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention is pointed out with particularity in the appended claims. However, other features of the invention will become more apparent and the invention will be best understood by referring to the following detailed description in
conjunction with the accompanying drawings in which:
FIG. 1 shows a representational illustration of a single network, distributed message-based data processing system of the type incorporating the present invention.
FIG. 2 shows a block diagram illustrating a multiple-network, distributed message-based data processing system of the type incorporating the present invention.
FIG. 3 shows an architectural model of a data processing system of the type incorporating the present invention.
FIG. 4 shows the relationship between software contexts and processes as they relate to the present invention.
FIG. 5 shows how messages may be sent between processes within nested contexts.
FIG. 6 shows a standard message format used in the distributed data processing system of the present invention.
FIG. 7 shows the relationship between pictures, views, and windows in the human interface of a data processing system of the type incorporating the present invention.
FIG. 8 shows a conceptual view of the different levels of human interface within a data processing system incorporating the present invention.
FIG. 9 illustrates the relationship between the basic human interface components in a typical working environment.
FIG. 10 shows the general structure of a complete picture element.
FIG. 11 shows the components of a typical screen as contained within the human interface system of the present invention.
FIG. 12 shows how the console manager operates upon virtual input to generate virtual output.
FIG. 13 shows how virtual input is handled by the console manager.
FIG. 14 shows how virtual input is handled by the picture manager.
OVERVIEW OF COMPUTER SYSTEM
The present invention can be implemented either in a single CPU data processing system or in a distributed data processing system that is, two or more data processing systems (each having at least one processor) which are capable of functioning
independently but which are so coupled as to send and receive messages to and from one another.
A Local Area Network (LAN) is an example of a distributed data processing system. A typical LAN comprises a number of autonomous data processing "nodes", each comprising at least a processor and memory. Each node is capable of conducting data
processing operations independently. In addition, each node is coupled (by appropriate means such as a twisted wire pair, coaxial cable, fiber optic cable, etc.) to a network of other nodes which may be, for example, a loop, star, tree, etc., depending
upon the design considerations.
With reference to FIG. 1, a distributed computer configuration is shown comprising multiple nodes 2-7 (nodes) loosely coupled by a local area network (LAN) 1. The number of nodes which may be connected to the network is arbitrary and depends
upon the user application. Each node comprises at least a processor and memory, as will be discussed in greater detail with reference to FIG. 2 below. In addition, each node may also include other units, such as a printer 8, operator display module
(ODM) 9, mass memory module 13, and other I/O device 10.
With reference now to FIG. 2, a multiple-network distributed computer configuration is shown. A first local area network LAN 1 comprises several nodes 2,4, and 7. LAN 1 is coupled to a second local area network LAN 2 by means of an Intelligent
Communications Module (ICM) 50. The Intelligent Communications Module provides a link between the LAN and other networks and/or remote processors (such as programmable controllers).
LAN 2 may comprise several nodes (not shown) and may operate under the same IAN protocol as that of the present invention, or it may operate under any of several commercially available protocols, such as Ethernet; MAP, the Manufacturing
Automation Protocol of General Motors Corp.; Systems Network Architecture (SNA) of International Business Machines, Inc.; SECS-II; etc. Each ICM 50 is programmable for carrying out one of the above-mentioned specific protocols. In addition, the basic
processing module of the node itself can be used as an intelligent peripheral controller (IPC) for specialized devices.
LAN 1 is additionally coupled to a third local area network LAN 3 via ICM 52. A process controller 55 is also coupled to LAN 1 via ICM 54.
A representative node N (7, FIG. 2) comprises a processor 24 which, in a preferred embodiment, is a processor from the Motorola 68000 family of processors. Each node further includes a read only memory (ROM) 28 and a random access memory (RAM)
26. In addition, each node includes a Network Interface Module (NIM) 21, which connects the node to the LAN, and a Bus Interface 29, which couples the node to additional devices within a node. While a minimal node is capable of supporting two
peripheral devices, such as an Operator Display Module (ODM) 41 and an I/O Module 44, additional devices (including additional processors, such as processor 27) can be provided within a node Other additional devices may comprise, for example, a printer
42, and a mass-storage module 43 which supports a hard disk and a back-up device (floppy disk or streaming tape drive).
The Operator Display Module 41 provides a keyboard and screen to enable an operator to input information and receive visual information.
While a single node may comprise all of the above units, in the typical user application individual nodes will normally be dedicated to specialized functions. For example, one or more mass storage nodes may be set up to function as data base
servers. There may also be several operator consoles and at least one node for generating hard-copy printed output. Either these same nodes, or separate dedicated nodes, may execute particular application programs.
The system is particularly designed to provide an integrated solution for office or factory automation, data acquisition, and other real-time applications. As such, it includes a full complement of services, such as a graphical output, windows,
menus, icons, dynamic displays, electronic mail, event recording, and file management. Software development features include compilers, a window-oriented editor, a debugger, and performance-monitoring tools.
LOCAL AREA NETWORK
The local area network, as depicted in either FIG. 1 or FIG. 2, ties the entire system together and makes possible the distributed virtual machine model described below. The LAN provides high throughput, guaranteed response, reliability, and low
entry cost. The LAN is also autonomous, in the sense that all system and applications software is unaware of its existence. For example, any Network Interface Module (e.g. NIM 21, FIG. 2) could be replaced without rewriting any software other than that
which directly drives it.
The LAN interconnection medium may be twisted-pair or coaxial cable. Two channels (logically, two distinct networks) may be provided for reliability and for increased throughput.
The LAN architecture is a logical ring, in which an electronic "token" is constantly passed from node to node at high speed. The current holder of the token may use it to send a "frame" of data or may pass it on to the next node in the ring.
The NIM only needs to know the logical address and status of its immediately succeeding neighbor. The NIM's responsibility is limited to detecting the failure of that neighbor or the inclusion of a new neighbor. In general, adjustment to failed or
newly added nodes is automatic.
The network interface maps directly into the processor's memory. Data exchange occurs through a dual-ported buffer pool which contains a linked list of pending "frames" Logical messages, which vary in length, are broken into fixed-size frames
for transmission and are reassembled by the receiving NIM. Frames are sequence-numbered for this purpose. If a frame is not acknowledged within a short period of time, it is retransmitted a number of times before being treated as a failure.
As described above with reference to FIG. 2, the LAN may be connected to other LAN's operating under the same LAN protocol via so-called "bridgeways", or it may be connected to other types of LAN's via "gateways".
SOFTWARE MODEL
The computer operating system of the present invention operates upon processes, messages, and contexts, as such terms are defined herein. Thus this operating system offers the programmer a hardware abstraction, rather than a data or control
abstraction.
A "process", as used within the present invention, is defined as a self-contained package of data and executable procedures which operate on that data, comparable to a "task" in other known systems. Within the present invention a process can be
thought of as comparable to a subroutine in terms of size, complexity, and the way it is used. The difference between processes and subroutines is that processes can be created and destroyed dynamically and can execute concurrently with their creator
and other "subroutines".
Within a process, as used in the present invention, the data is totally private and cannot be accessed from the outside, i.e., by other processes. Processes can therefore be used to implement "objects", "modules", or other higher-level data
abstractions. Each process executes sequentially. Concurrency is achieved through multiple processes, possibly executing on multiple processors.
Every process in the distributed data processing system of the present invention has a unique identifier (PID) by which it can be referenced. The PID is assigned by the system when the process is created, and it is used by the system to
physically locate the process.
Every process also has a non-unique, symbolic "name", which is a variable-length string of characters. In general, the name of a process is known system-wide. To restrict the scope of names, the present invention utilizes the concept of a
"context".
A "context" is simply a collection of related processes whose names are not known outside of the context. Contexts partition the name space into smaller, more manageable subsystems. They also "hide" names, ensuring that processes contained in
them do not unintentionally conflict with those in other contexts.
A process in one context cannot explicitly communicate with, and does not know about, processes inside other contexts. All interaction across context boundaries must be through a "context process", thus providing a degree of security. The
context process often acts as a switchboard for incoming messages, rerouting them to the appropriate sub-processes in its context.
A context process behaves like any other process and additionally has the property that any processes which it creates are known only to itself and to each other. Creation of the process constitutes definition of a new context with the same name
as the process.
Any process can create context processes. Each new context thus defined is completely contained inside the context in which it was created and therefore is shielded from outside reference. This "nesting" allows the name space to be structured
hierarchically to any desired depth.
Conceptually, the highest level in the hierarchy is the system itself, which encompasses all contexts. Nesting is used in top-down design to break a system into components or "layers", where each layer is more detailed than the preceding one.
This is analogous to breaking a task down into subroutines, and in fact many applications which are single tasks on known systems may translate to multiple processes in nested contexts.
A "message" is a buffer containing data which tells a process what to do and/or supplies it with information it needs to carry out its operation. Each message buffer can have a different length (up to 64 kilobytes). By convention, the first
field in the message buffer defines the type of message (e.g., "read", "print", "status", "event", etc.).
Messages are queued from one process to another by name or PID. Queuing avoids potential synchronization problems and is used instead of semaphores, monitors, etc. The sender of a message is free to continue after the message is sent. When the
receiver attempts to get a message, it will be suspended until one arrives if none are already waiting in its queue. Optionally, the sender can specify that it wants to wait for a reply and is suspended until that specific message arrives. Messages
from any other source are not dequeued until after that happens.
Within the present invention, messages are the only way for two processes to exchange data. There is no concept of a "global variable". Shared memory areas are not allowed, other than through processes which essentially "manage" each area by
means of messages. Messages are also the only form of dynamic memory that the system handles. A request to allocate memory therefore returns a block of memory which can be used locally by the process but can also be transmitted to another process.
The context nesting level determines the "scope of reference" when sending messages between processes by name. From a given process, a message may be sent to all processes at its own level (i.e., in the same context) and (optionally) to any
arbitrary higher level. The contexts are searched from the current context upward until a match is found. All processes with the given name at that level are then sent a copy of the message. A process may also send a message to itself or to its parent
(the context process) without knowing either name explicitly, permitting multiple instances of a process to exist in different contexts, with different names.
Sending messages by PID obviates the need for a name search and ignores context boundaries. This is the most efficient method of communicating.
Processes are referenced without regard to their physical location via a small set of message-passing primitives. As mentioned earlier, every process has both a unique system-generated identifier and a not necessarily unique name assigned by the
programmer. The identifier provides quick direct access, while the name has a limited scope and provides symbolic, indirect access.
With reference to FIG. 3, an architectural model of the present invention is shown. The bottom, or hardware, layer 63 comprises a number of processors 71-76, as described above. The processors 71-76 may exist physically within one or more
nodes. The top, or software, layer 60 illustrates a number of processes P1-P10 which send messages m1-m6 to each other. The middle layer 61, labelled "virtual machine", isolates the hardware from the software, and it allows programs to be written as if
they were going to be executed on a single processor. Conversely, programs can be distributed across multiple processors without having been explicitly designed for that purpose.
THE VIRTUAL MACHINE
As discussed earlier, a "process" is a self-contained package of data and executable procedures which operate on that data. The data is totally private and cannot be accessed by other processes. There is no concept of shared memory within the
present invention. Execution of a process is strictly sequential. Multiple processes execute concurrently and must be scheduled by the operating system. The processes can be re-entrant, in which case only one copy of the code is loaded even if
multiple instances are active.
Every process has a unique "process identifier number" (PID) by which it can be referenced. The PID is assigned by the system when the process is created and remains in effect until the process terminates. The PID assignment contains a
randomizing factor which guarantees that the PID will not be re-used in the near future. The contents of the PID are irrelevant to the programmer but are used by the virtual machine to physically locate the process. A PID may be thought of as a
"pointer" to a process.
Every process also has a "name" which is a variable-length string of characters assigned by the programmer. A name need not be unique, and this ambiguity may be used to add new services transparently and to aid in fault-tolerance.
FIG. 4 illustrates that the system-wide name space is partitioned into distinct subsets by means of "contexts" identified by reference numerals 90-92. A context is simply a collection of related processes whose names are not known outside of the
context. Context 90, for example, contains processes A, a, a, b, c, d, and e. Context 91 contains processes B, a, b, c, and f. And context 92 contains processes C, a, c, d, and x.
One particular process in each context, called the "context process", is known both within the context and within the immediately enclosing one (referred to as its "parent context"). In the example illustrated in FIG. 4, processes A-C are
context processes for contexts 90-92, respectively. The parent context of context 91 is context 90, and the parent context of context 92 is context 91. Conceptually, the context process is located on the boundary of the context and acts as a gate into
it.
Processes inside context 92 can reference any processes inside contexts 90 and 91 by name. However, processes in context 91 can only access processes in context 92 by going through the context process C. Processes in context 90 can only access
processes in context 92 by going through context processes B and C.
The function of the context process is to filter incoming messages and either reject them or reroute them to other processes in its context. Contexts may be nested, allowing a hierarchy of abstractions to be constructed. A context must reside
completely on one node. The entire system is treated as an all-encompassing context which is always present and which is the highest level in the hierarchy. In essence, contexts define localized protection domains and greatly reduce the chances of
unintentional naming conflicts.
If appropriate, a process inside one context can be "connected" to one inside another context by exchanging PID's, once contact has been established through one or the other of the context processes. Most process servers within the present
invention function that way. Initial access is by name. Once the desired function (such as a window or file) is "opened", the user process and the service communicate directly via PID's.
A "message" is a variable-length buffer (limited only by the processor's physical memory size) which carries information between processes. A header, inaccessible to the programmer, contains the destination name and the sender's PID. By
convention, the first field in a message is a null-terminated string which defines the type of message (e.g., "read", "status", etc.) Messages are queued to the receiving process when they are sent. Queuing ensures serial access and is used in
preference to semaphores, monitors, etc.
Messages provide the mechanism by which hardware transparency is achieved. A process located anywhere in the system may send a message to any other process anywhere else in the system (even on another processor) if it knows the process name.
This means that processes can be dynamically distributed across the system at any time to gain optimal throughput without changing the processes which reference them. Resolution of destinations is done by searching the process name space.
Transparency applies with some restrictions across bridgeways (i.e., the interfaces between LAN's operating under identical network protocols) and, in general, not at all across gateways (i.e., the interfaces between LAN's operating under
different network protocols) due to performance degradation. However, they could so operate, depending upon the required level of performance.
INTER-PROCESS COMMUNICATION
All inter-process communication is via messages. Consequently, most of the virtual machine primitives are concerned with processing messages. The virtual machine kernel primitives are the following:
ALLOC--requests allocation of a (message) buffer of a given size.
FREE--requests deallocation of a given message buffer.
PUT--end a message to a given destination (by name or PID).
GET--wait for and dequeue the next incoming message, optionally from a specific process (by PID).
FORWARD--pass a received message through to another process.
CALL--send a message, then wait for and dequeue the reply.
REPLY--send a message to the originator of a given message.
ANY.sub.-- MSG--returns "true" if the receive queue is not empty, else returns "false"; optionally, checks if any messages from a specific PID are queued.
To further describe the function of the kernel primitives, ALLOC handles all memory allocations. It returns a pointer to a buffer which can be used for local storage within the process or which can be sent to another process (via PUT, etc.).
ALLOC never "fails", but rather waits until enough memory is freed to satisfy the request.
The PUT primitive queues a message to another process. The sending process resumes execution as soon as the message is queued.
FORWARD is used to quickly reroute a message but maintain information about the original sender (whereas PUT always makes the sending process the originator of the message).
REPLY sends a message to the originator of a previously received message, rather than by name or PID.
CALL essentially implements remote subroutine invocations, causing the caller to suspend until the receiver executes a REPLY. Subsequently, the replied message is dequeued out of sequence, immediately upon arrival, and the caller resumes
execution.
The emphasis is on concurrency, so that as many processes as possible are executed in parallel. Hence neither PUT nor FORWARD waits for the message to be delivered. Conversely, GET suspends a process until a message arrives and dequeues it in
one operation. The ANY MSG primitive is provided so that a process may determine whether there is anything of interest in the queue before committing itself to a GET.
When a message is sent by name, the destination process must be found in the name space. The search path is determined by the nesting of the contexts in which the sending process resides. From a given process, a message can be sent to all
processes in its own context or (optionally) to those in any higher context. Refer to FIG. 5. The contexts are searched from the current one upward until a match is found or until the system context is reached. All processes with the same name in that
context are then queued a copy of the message.
For example, with reference to FIG. 5, assume that in context 141 process y sends a message to ALL processes by the name x. Process y first searches within its own context 141 but finds no process x. The process y searches within the next higher
context 131 (its parent context) but again finds no process x. Then process y searches within the next higher context 110 and finds a process x, identified by reference numeral 112. Since it is the only process x in context 110, it is the only recipient
of the message from process y.
If process a in context 131 sends a message to ALL processes by the name x, it first searches within its own context 131 and, finding no processes x there, it then searches within context 110 and finds process x.
Assume that process b in context 131 sends a message to ALL processes by the name A. It would find process A (111) in context 110, as well as process A (122) which is the context process for context 121.
A process may also send a message to itself or to its context process without knowing either name explicitly.
The concept of a "logical ring" (analogous to a LAN) allows a message to be sent to the NEXT process in the system with a given name. The message goes to exactly one process in the sender's context, if such a process exists. Otherwise the
parent context is searched.
The virtual machine guarantees that each NEXT transmission will reach a different process and that eventually a transmission will be sent to the logically "first" process (the one that sent the original message) in the ring, completing the loop.
In other words, all processes with the same name at the same level can communicate with each other without knowing how many there are or where they are located. The logical ring is essential for distributing services such as a data base. The ordering
of processes in the ring is not predictable.
For example, if process a (125) in context 121 sends a message to process a using the NEXT primitive, the search finds a first process a (124) in the same context 121. Process a (124) is marked as having received the message, and then process a
(124) sends the message on to the NEXT process a (123) in context 121. Process a (123) is marked as having received the message, and then it sends the message on to the NEXT process a, which is the original sender process a (125), which knows not to
send it further on, since it's been marked as having already received the message.
Sending messages directly by PID obviates the need for a name search and ignores context boundaries. This is known as the DIRECT mode of transmission and is the most efficient. For example, process A (111) sends a message in the DIRECT mode to
process y in context 141.
If a process sends a message in the LOCAL transmission mode, it sends it only to a process having the given name in the sender's own context.
In summary, including the DIRECT transmission mode, there are five transmission modes which can be used with the PUT, FORWARD, and CALL primitives:
ALL--to all processes with the given name in the first context which contains that name, starting with the sender's context and searching upwards through all parent contexts.
LOCAL--to all processes with the given name in the sender's context only.
NEXT--to the next process with the given name in the same context as the sender, if any; otherwise it searches upwards through all parent contexts until the name is found.
LEVEL--sends to "self" (the sending process) or to "context" (the context process corresponding to the sender's context); "self" cannot be used with CALL primitive.
DIRECT--sent by PID.
Messages are usually transmitted by queueing a pointer to the buffer containing the message. A message is only copied when there are multiple destinations or when the destination is on another node.
OPERATING SYSTEM
The operating system of the present invention consists of a kernel, which implements the primitives described above, plus a set of processes which provide process creation and termination, time management (set time, set alarm, etc.) and which
perform node start-up and configuration. Drivers for devices are also implemented as processes (EESP's), as described above. This allows both system services and device drivers to be added or replaced easily. The operating system also supports
swapping and paging, although both are invisible to applications software.
Unlike known distributed computer systems, that of the present invention does not use a distinct "name server" process to resolve names. Name searching is confined to the kernel, which has the advantage of being much faster.
A minimal bootstrap program resides permanently (in ROM) on every node, e.g. ROM 28 in node N of FIG. 2. The bootstrap program executes automatically when a node is powered up and begins by performing basic on-board diagnostics. It then
attempts to find and start an initial system code module. The module is sought on the first disk drive on the node, if any. If there isn't a disk, and the node is on the LAN, a message will be sent out requesting the module. Failing that, the required
software must be resident in ROM. The initialization program of the kernel sets up all of the kernel's internal tables and then calls a predefined entry point of the process.
In general, there exists a template file describing the initial software and hardware for each node in the system. The template defines a set of initial processes (usually one per service) which are scheduled immediately after the node start-up. These processes then start up their respective subsystems. A node configuration service on each node sends configuration messages to each subsystem when it is being initialized, informing it of the devices it owns. Thereafter, similar messages are sent
whenever a new device is added to the node or a device fails or is removed from the node.
Thus there is no well-defined meaning for "sy | | |
