This document is authored by Antti Huima, Heikki Saikkonen and Mikko Tiusanen.
SCHEMESTATION is an operating system concept that is being developed, currently unofficially, in the Laboratory of Information Processing Science at the Helsinki University of Technology.
This document specifies the SCHEMESTATION operating system to a certain detail. As the SCHEMESTATION project is still in its early phases, there are some areas that are not fully specified. These areas are denoted as such and plan for specifying them later is presented.
This document is intended to work as a reference document for the first prototype whose implementation is currently on its way.
The SCHEMESTATION operating system consists of a kernel system and an operating environment. The operating environment utilizes the kernel system. However, the kernel system is not dependent on the operating environment. For this reason it is convenient to describe the operating system keeping these two subsystems separated --- we start from the kernel system and proceed only afterwards to specify the operating environment.
Actually it could be possible to implement many different operating environments on the top of the kernel system. If any ambiguousness should arise, the operating environment specified here should be referred to as OE1.
The SCHEMESTATION OS is described here in quite abstract terms. This is intentional and is justified by the fact that the operating system is based on virtual machine architecture. (The term ``virtual machine architecture'' is overloaded and ambiguous. Here its meaning is that user-level processes are described as sequences of standard byte code instructions that do not necessarily correspond to the instruction set of any existing physical hardware and do not depend on the particular possibly electronical device running the operating system.) So it is not important to refer to hardware when specifying the OS. Any logical or physical device that implements the specification can be said to ``run'' the SCHEMESTATION OS, whether there is actually some kind of CPU or any physical hardware or not.
The purpose of the SCHEMESTATION OS is to make possible to run asynchronously executing agents that are able to communicate between anothers using message passing. Thus, using conventional terminology, the unit of execution in the SCHEMESTATION is an agent.
So, what is an agent? In the SCHEMESTATION we define an agent as a computational process that has the following features:
Every agent belongs to one domain. Domains are localities of execution. The domains are thightly linked to the identities of agents and the address system used to handle those identities, see below.
It is expected that domains often correspond to physical CPUs or workstations. Thus to give a concrete interpretation of the terms, an agent that is run as a process on a workstation's CPU probably belongs to the domain that consists of the CPU.
Domains have also identities and must be capable of intercommunicating.
To make it possible for the agents to communicate the agents must have addresses that can be used to reach them. In the SCHEMESTATION OS every domain forms a local address space. Every agent in a domain has in the domain at least one address from the domain's address space. The local addresses corresponding to an agent are collectively called the set of principal addresses of the agent.
To facilitate inter-domain communication, local addresses can also denote local addresses in other domains. For example, if there are two domains D1 and D2 and both contain one agent, A1 and A2, respectively, then A1 has some local address x in the domain D1 and A2 has some local address y in the domain D2. But this is not sufficient for enabling communication between A1 and A2 as A1 is not able to see the local address space of a non-local domain. Now it is possible that there is a local address z in the domain D1 that denotes the remote address (D2,y) (we use this notation thorough the document to denote remote addresses). Thus a local address z in the domain D1 maps to the local address y in the domain D2, which conveys the same meaning as saying that it denotes the remote address (D2,y). Of course some kind of interoperation between the two domains is needed in order to be able to create this remote reference to the address y.
The kernel system (KS) is the subpart of the operating system that implements agents and domains.
The memory model that is provided to ``normal'' ``user-level'' agents is that of a garbage-collected, list-structured, typed heap, cf. LISP. The actual kinds of data that the heap is able to store are defined elsewhere and may change should any need arise. Any object that can be stored in a heap is called a heap object.
Among others, the following must be heap objects: domain addresses, actor addresses, byte code instruction sequences and indices to byte code instruction sequences.
There exists a standard SCHEMESTATION virtual machine that is used to execute the programs of most agents. The virtual machine transforms execution contexts to execution contexts. An execution context consists of a heap, a byte code program, and an index to the program sequence. NOTE The actual virtual machine may contain for example some set of registers. These registers can be seen to belong conceptually to the heap, however.
The actual virtual machine is specified elsewhere. It must have operations to send and accept messages.
Any object that satisfies the following properties is considered an agent in the SCHEMESTATION:
If an agent additionally satisfies the following properties, it is called a common agent:
Non-common agents are processes that are not described using the SCHEMESTATION byte code but something else. Non-common agents can be divided into two sets:
The SCHEMESTATION kernel implementing agents are agents that are a part of the kernel implementation. For example, a domain scheduler that controls the execution of various agent can itself have an agent's interface and be able to send and receive heap objects as messages; and have a principal address in its own domain. External agents are agents that are incorporated into a SCHEMESTATION system from outside the system, for example external databases.
Every domain maintains a mapping that maps every possible local address to one of the following:
Addresses that map to a local agent are called the local agent's principal addresses. There may be more than one of those.
The format for a local address is specified. Any local address is a 256-bit bit string. The large address space is necessary due to the way security is implemented in the SCHEMESTATION. For the security purposes, also, it must be ensured that domains generate addresses for new agents using a strong pseudo-random number generator so that the probability to be able to guess an actor's address is very low (not much more than ).
Domains have addresses, too. A domain address is a 128-bit bit string. They need not to be generated randomly, and it is not expected that this would be the case.
The term local address refers here always to a 256-bit address in a domain's address space, the term domain address to a 128-bit domain address, and the term remote address to a combination of a domain address and a local address.
All agents are persistent unless noticed otherwise. The persistence is interpreted to mean the following: an agent is persistent if its local state is preserved over a time interval where the domain it belongs to is not functioning; for example, when the workstation running the domain is shut down. The local states of persistent agents are restored when the domain gets back to life. (Non-persistent agents do not have this property but cease to exist when a domain is shut down.)
The core of the kernel system consists of three persistent agents: a domain kernel agent, a scheduler agent and an address system agent. Note that these agents do not necessarily communicate between themselves using heap object messages but may have some implementation-dependent, more reasonable way to do that.
Every domain has exactly one domain kernel agent. It is a general interface to the kernel running the corresponding domain. The address of the domain kernel agent is fixed to be zero (256 zero bits).
Every domain has exactly one scheduler agent that controls the execution of common and non-common agents in the current domain. In particular, the scheduler controls the execution of byte code programs of common agents. The scheduler is an agent (probably a non-common one). The address of the scheduler is known by the domain kernel agent.
The address space of a domain is controlled by an address system agent. The same agent is also responsible for queueing messages that are waiting for to be delivered to their intended receivers. The address of the address system agent is known by the domain kernel agent.
There are two kinds of boot-ups for SCHEMESTATION domains: (1) the initial boot-up, and (2) system wake-up. During the initial boot-up, a domain that has not existed before is created. System wake-ups occur when a domain that has been temporarily freezed starts working again and the persistent agents stored continue execution from the point where they were left when the system went down.
When a new domain is created (for example, the SCHEMESTATION operating system is installed to a new workstation), the following happens:
The agents are able to communicate between themselves using asynchronous message passing.
The address system agent of a domain maintains a message queue for every active (used) address. When a local agent sends a message, the message is appended to the queue of the local address the agent specified.
Messages are removed from queues and passed forward when (1) a queue belongs to an address that denotes a local agent and the agent is capable of receiving a message, and (2) when a queue belongs to a remote address and it is possible to send messages to the remote domain via network.
A message consists of a local address and a heap object. When an agent receives a message, it receives only the heap object, not its own local address. When messages are passed in the network, the address of the receiving domain is put before the rest of the message. Note especially, that the local address of the sending agent is not present in the message. This must be obeyed, because otherwise the intended security of the operating system breaks immediately down.
There needs to be a standard way of representing non-linear heap objects in a linear form; this format is specified elsewhere.
A message sent to an address is delivered to it, if possible. Thus message passing is reliable so long as some components of the network do not break down in a way that makes it impossible to send messages forward.
No error messages are sent back to the sending agent if the message cannot reach its destination, however. If such error messages are needed, they need to be implemented on the top of the kernel system.
The following property applies to the relative order of sent and received messages: all messages sent by one agent to one address, whether local or remote, reach the agent the address denotes in the same order as they were sent [if the agent is reachable]. No global ordering is preserved, however.
It is up to the implementation to decide when to drop out messages that cannot be delivered to their destinations.
Messages that are sent to a local address that does not exist are silently ignored.
It is possible that messages that contain local addresses are sent between distinct domains (in fact, it is very probable). Now this means, that if nothing is done, the receiving agent will see in the message local addresses that refer to the address space of the sending agent, not the one of the receiving. This is of course not what is intended. For this reason when a message is received that has originated in a different domain, the following is done:
There can be exceptions to this rule. Certain messages must be transferred without this remapping. Such messages are called absolute address messages.
Local agents can be created and deleted by the local domain kernel agent. Other agents can request agent creation from the domain kernel agent.
A common agent ceases to exist when it executes the HALT instruction, or when the local domain kernel agent decides to remove it. All messages sent to an agent are discarded after its termination. NOTE This implies that the same address cannot be ever used twice. This should not be a problem with the large address space, however.
This section describes in abstract terms a subset of the messages that the domain kernel agent must be able to understand and send. The actual implementation of these messages depends on the heap structure chosen.
The internal security of a domain is based on the following principle:
The local address of any actor cannot be guessed if it is not known. Thus access control can be implemented in the terms of knowing (or not knowing) certain addresses. Message passing inside one domain can be considered secured from eavesdropping and tampering as long as the domain's kernel is trusted (and the physical hardware protected etc.)
However, this is not sufficient when inter-domain operations are considered. The operating environment OE1 specifies (1) the usage of strong cryptgraphy to protect inter-domain message passing and (2) cryptographic domain authentication and maintaing trust relationships between distinct domains to build a trusted environment of several domains.
The operating environment corresponds the rest of the SCHEMESTATION infrastructure that is built on the top of the kernel system.
For the purposes of being able to identify certain heap objects via symbolic names, the concepts of object identifiers and object servers are introduced.
An object identifier is a heap object that is used to specify another heap object. Object servers store objects and deliver them according to the requests they receive. Every object in the server is associated with one or more object identifiers.
Any object identifier is of the form
((name1 value ...) (name2 value ...) ...)
Object identifier templates are used to match object identifiers. Any object identifier is an object identifier template, and is called a simple object identifier template. Furthermore, if T1 ... Tn are object identifier templates, then the following are also:
(and T1 ... Tn) (or T1 ... Tn) (excluding T1 T2)
An object identifier template matches an object identifier if
The special rules mentioned are used to implement more advanced matching methods. The special rules may be bound to the field names. The following special rule is currently defined:
Object servers are agent that, upon request, deliver object identifiers and objects.
Any object server is able to run the following simple object server protocol (SOSP):
We mention, that it is possible that the object identifiers contain for example digital signatures of the objects they stand for. This is one of the reasons why the full object identifiers must be sent along with the objects being delivered.
An object server that mainly delivers remote agent addresses is called a name server.
In the OE1 it is possible that agents can migrate from one domain to another during their existence. This section specifies the mechanism used to implement the migration.
First, the two domains taking part in the migration process must decide together that the migration should take place indeed. This is done using some kernel-to-kernel protocol between the domains. Then the following happens.
Graphical terminals are needed in order to be able to communicate with the SCHEMESTATION environment.
OE1 terminals are individual domains that have a terminal controller agent in the address number 1.
Terminals are, however, very restricted as domains. In particular they do not need to support execution of common agents nor to support any persistence.
The domain addresses of terminals do not need to be constant over periods when the terminal is not used.
Every time a terminal facility starts to function, it boots ``from scratch''. The boot-up procedure goes as follows.
There may be different types of terminals and thus the messages used to communicate with them may wary. However, the following general messages are required to be supported:
Views are controlled in a way specific to the type of the terminal.
It must be possible to remove addresses from the set of memorized local addresses if the addresses are no longer used. Also, it must be possible for the domains to resolve sets of agents that are no longer properly functioning and that can be deleted in order to free system resources. It must also be possible to change the denotations of addresses in order to shorten address resolving indirection paths. In this chapter, the system used to reach these goals in the OE1 is described.
The following messages are used to control the address spaces and the address denotations:
The purpose of this message is to enable the receiving domain to change address pointers that point to the remote address (sending domain, local address) directly to the remote address that this remote address actually points to, such saving one level of indirection. Also, it enables the receiving domain to delete a bogus entry in its own address table that is only pointing to a non-existent entry in the remote domain's address table.
The following algorithm can be used to resolve address indirection paths between domains:
Every agent has zero or more owners, and every agent keeps track of its owners by itself. Owners are addresses.
Normally when an agent terminates it sends recursively termination requests to the agents that cannot function without it. For example, a text processor could have a distinct user interface agent, which has no real use if the text processor itself has already terminated.
However, due to software bugs or other system probles it is possible that unusable agents keep ``hanging around'' in the SCHEMESTATION environment. The following algorithm and protocol can be used to resolve, in such situations, whether or not an agent can be safely removed by commission from the domain's kernel agent:
Operating systems are most often ultimately used by humans. In order to control access to an operating system, some method of authorization must exist. Normally this method is some kind of user authentication via a terminal. This section describes the user authentication and authorization scheme used in the SCHEMESTATION.
There is no such thing as a user identity per se. Instead, there is a set of agents that can be utilized only via certain external authorization. These agents can be seen to somehow describe the user's identity.
An authorization agent is a special-purpose agent that has the following distinguished features:
There can be several methods for authentication. The security of authentication relies partly on the cryptographic protection of the inter-domain connections.
One of the authentication methods is RSA-based authentication. In this method, the authentication agent contains a public RSA key and other agents trying to get authorization try to show that the know the corresponding private RSA key. This message utilizes the following messages: