Operating system specification

Operating system specification

Document formatted by vherva at Fri Apr 24 11:23:49 1998 on the host schemestation. This document is produced by the SchemeStation project during the Tik-76.115 course.

1 Authors

This document is authored by Antti Huima, Heikki Saikkonen and Mikko Tiusanen.

2 Introduction

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.

2.1 Structure and scope of this specification

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.

3 Overview of the system

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.

3.1 Agents

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:

  • it is able to send messages to and to receive them from another agents
  • it has an identity
  • it has a local state
This ``definition'' is vague at best but serves the purposes of the overview. A more rigorous definition is given later in this document.

3.2 Domains

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.

3.3 Agent identities and addresses

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.

4 Kernel system

The kernel system (KS) is the subpart of the operating system that implements agents and domains.

4.1 Memory model: garbage-collected, list-structured, typed heap

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.

4.2 Virtual machine

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.

4.3 Agents

Any object that satisfies the following properties is considered an agent in the SCHEMESTATION:

  • It is able to send and receive heap objects as messages
  • It has a principal address in some domain

If an agent additionally satisfies the following properties, it is called a common agent:

  • It has a local state
  • There exists an execution context that fully describes the local state of the agent, not considering possible messages queued for reception (read: the agent executes SCHEMESTATION byte code)

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:

  • SCHEMESTATION kernel implementing agents
  • external agents

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.

4.4 Addresses

Every domain maintains a mapping that maps every possible local address to one of the following:

  1. a local agent
  2. a remote address of the form (DOMAIN, ADDRESS) where ADDRESS is local address in the [remote] domain DOMAIN
  3. unused

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.

4.5 Persistence

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.)

4.6 Functional parts of the kernel system

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.

4.6.1 Domain kernel agent

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).

4.6.2 Scheduler

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.

4.6.3 Address system

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.

4.7 System boot-ups

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.

4.7.1 Initial boot-up

When a new domain is created (for example, the SCHEMESTATION operating system is installed to a new workstation), the following happens:

  1. The three kernel agents are created.
  2. The address system agent generates addresses for itself and the scheduler and gives them to the domain kernel agent.
  3. The domain address of the new domain is got from outside and given to the address system agent.
  4. The scheduler tooks over the control of the domain.
  5. The kernel agents starts possibly needed other kernel implementing and external agents --- for example device drivers.
  6. The kernel agent starts required system services.

4.7.2 System wake-up

  1. The state of the kernel is recovered.
  2. The scheduler is started in a restricted mode that allows it to run only the kernel agents.
  3. The domain kernel agent re-spawns or delegates the re-spawning of certain required agents that are known to have existed but that are not persistent, for example device drivers.
  4. Scheduler switches to normal mode and continues execution.

4.8 Message passing

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.

4.8.1 The semantics of message passing

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.

4.8.2 Address transfer in inter-domain communications

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:

  1. The whole message is scanned and searched for addresses (this is possible, as the heap objects have explicit, tagged types). For every local address present in the message, a new local address in the domain of the receiver is allocated and mapped to the original local address in the sender's domain. The address in the message is changed to the newly created local address (in the receiver's domain).
  2. After all addresses have been processed in this fashion, the message is given to its recipient. This transformation is controlled by the address system agent.

    There can be exceptions to this rule. Certain messages must be transferred without this remapping. Such messages are called absolute address messages.

4.9 Creating and deleting agents

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.

4.10 Kernel agent interface

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.

CREATE(owner, spec)
Request the domain kernel agent to create a new agent that executes the program specified in spec; this argument could be for example the name of the program or the corresponding byte code sequence itself. When the agent is created the kernel agent responds the requesting agent with CHILD(...). The newly created agents gets the message WELCOME(...) as the first message if ever receives.

CHILD(address, spec)
The domain kernel agent informs another agent that a new agent with the specification spec has been created and has the address address.

This message is sent to a newly created agent. address is the agent's own local address.

This message is sent by the kernal domain agent to ask another agent to terminate cleanly. If the request is not honored, the kernel domain agent has of course the option to terminate the agent's execution without any questions.

This message is sent by a trusted agent to the kernel agent. The result is

4.11 Kernel system security

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.

5 The operating environment OE1

The operating environment corresponds the rest of the SCHEMESTATION infrastructure that is built on the top of the kernel system.

5.1 Object identifiers and object servers

For the purposes of being able to identify certain heap objects via symbolic names, the concepts of object identifiers and object servers are introduced.

5.1.1 Object identifiers and object templates

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 ...)

where names are strings and values arbitrary heap objects. Every name may appear in the identifier only once.

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

  1. The template is a simple template, and for every list (name value1 ... valueN) in the template there exists a list in the object identifier that is (name' value1' ... valueM') such that every object that appears in the list (value1 ... valueN) appears identically in the list (value1' ... valueM').
  2. The template matches the identifier using a special rule.
  3. The template is of the form (and T1 ... Tn), and all the subtemplates of the form match the object identifier.
  4. The template is of the form (and T1 ... Tn), and at least one of the subtemplates of the form matches the object identifier.
  5. The template is of the form (excluding T1 T2), and the object identifier matches the template T2 but not the template T1.

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:

  • A single integer value N can always be matched not only by the exact value of N, but also by (> M) for every M <= N, (< M) for every M >= N, and similarly for (<= M) and (>= M).

5.1.2 Object servers

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):

  1. Upon receiving the message QUERY(address, template), the server sends to the address address all the object identifiers that it knows, or a subset of them by its own discretion, or an error message if it wishes so.
  2. Upon receiving the message FETCH(address, template), the server sends to the address address the object that uniquely matches the template template, if any such object exists. Otherwise it chooses one of the objects matching template and sends it. If non exists an error message is sent. It is possible that the object server implements some heuristics to choose ``the best'' (for example, the newest) of the objects matching the template, but this is not a part of the protocol.
  3. Identifiers are sent using the message ID-LIST(list-of-ids) and objects using the message OBJECT(object-identifier, object), where object-identifier is the full identifier of the object sent.
  4. Error messages are sent using the message ERROR(object-explaining-the-error).

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.

5.1.3 Name servers

An object server that mainly delivers remote agent addresses is called a name server.

5.2 Agent migration

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.

  1. The sending domain freezes the execution of the agent to be migrated and begins to accumulate messages sent to the agent in its message queue, not delivering them further.
  2. The sending domain asks the target domain for the agent's new local address in the target domain. The target domain allocates a new local address and sends it back to the sending domain. In this special case, the address is not transformed to a new local address in the sending domain but is interpreted directly by the address system. The new address is stored for future use.
  3. The sending domain sends the execution context of the agent to the receiving domain. It is possible that the byte code instructions sequence is not sent verbatim but instead an object identifier is sent that allows the target domain to reconstruct the byte code sequence, using for example an object server.
  4. The receiving domain remaps the addresses in the execution context's heap in the same way as addresses in other messages are remapped.
  5. When the target domain has received the agent and initialized it, it notifies the sending domain about this.
  6. The sending domain then atomically remaps the agent's original local address to the new address in the remote domain, and sends the contents of the message queue this far to the remote domain. All message arriving after this has begun to the agent's original address are sent directly to the remote domain to the new address.
  7. The remote domain gets the messages the sending domain sent and puts them to the new message queue as first, delaying other possibly received messages after them.
  8. When all the messages have been received, the receiving domain starts to execute the agent.

5.3 OE1 terminals

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.

5.3.1 Terminal boot-up

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.

  • The terminal has a fixed, configurable remote agent address stored into a long-term store that denotes the owner of the terminal.
  • When the terminal starts, it creates a random address for controlling the terminal, and sends this random address with information about the terminal itself to the owner.
  • The owner then takes control over the terminal.

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:

Sent to the control address, this message transfers the configurable ownership of the terminal to the new address address.

Sent to the control address, this message causes the terminal to reboot immediately.

Sent to the control address, this message causes the terminal to shut itself down immediately.

Sent to the control address, this message causes a new view to be opened on the terminal. A new address is generated for controlling the view and this address is sent to address. Views are windows, virtual screens or whatever. It is possible that a new view cannot be allocated. Then an error message should be sent.

Sent to the address controlling a view, this causes the view to be removed.

Views are controlled in a way specific to the type of the terminal.

5.4 Agent and address bookkeeping; remapping of addresses

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.

5.4.1 Messages used

The following messages are used to control the address spaces and the address denotations:

REMAP-NOTIFICATION(local address, remap-specification)
This message is sent to a kernel domain agent of a domain. It is an absolute address message, i.e. the addresses contained in it must not be remapped when the message is received in the receiving domain. It tells that the sending domain has remapped its own local address local address to the denotation that is specified in remap-specification. remap-specification is one of the following:
  • remote address (a domain address and a local address)
  • ``delete''
If the specification is a remote address, then the sending domain has remapped its local address to the remote address specified. If it is ``delete'', then the local domain has invalidated the local address sent.

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.

DOMAIN-WATCH(local address, command)
This message is sent to a kernel domain agent of a domain. It is an absolute address message. It tells that the sending domain is interested in the receiving domain's local address local address and that the receiving domain should send appropriate REMAP-NOTIFICATIONs to the sending domain whenever the denotation of the address local address changes. Upon receiving this message, the receiving domain should send immediately a REMAP-NOTIFICATION back, giving the current denotation of the local address to the sender of the original message. This if command is ``watch''. command can be also ``forget'', in this case the semantics of the message is to remove the possible domain watch.
5.4.2 Address space resolving algorithm

The following algorithm can be used to resolve address indirection paths between domains:

  1. Whenever the denotation of a local address has changed, a REMAP-NOTIFICATION is sent to all domains interested.
  2. If the address is removed (the denotation changes to nothing) then all domain watches are removed.
  3. Whenever a remote address is added to the local address table, a domain watch is established in the remote domain. This also when the denotation of a local address changes to a new remote address. Domain watches are removed if remote addresses drop out from domain's address table.
  4. If the local agent a local address denotes terminates, the local address is removed.
  5. If a local address has not been referenced in a certain time interval, the address is flagged as suspicious.
  6. The heaps of local agents are scanned between certain intervals for suspicious addresses. Addresses that are suspicious, that do not exist in the local heaps and that have no domain watches are removed after a certain extra grace period.

5.4.3 Agent bookkeeping

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:

  1. An agent that has not received messages during a certain time interval is queried for its owners by the kernel, and an identifier that has been given to the agent when it has been created.
  2. The kernel tries to reach the owners, sending the identifier to them and asking whether or not this agent is still in use.
  3. If no owner responds, the agent is freezed.
  4. A freezed agent is not allowed to run. It can be deleted later after a grace period, migrated elsewhere or whatever the kernel decides to do with it. However, that an agent freezes may be due to network problems, and the grace period should be long enough that it is probable that the problems can be resolved. NOTE It is possible that the domain an agent belongs to is disconnected from a surrounding SCHEMESTATION environment for arbitrary times, for example, if the domain is a laptop computer. It must be possible to somehow inform the kernel about this ``controlled'' so that agents can stay freezed until the domain gets connected again.
  5. If at least one owner says that it is still used, the agent continues to live.
  6. Any owner address that is no longer interested is sent back to the agent, which should remove these addresses from the list of its owners.
  7. It the agent has no owners, or the number of its owners decreases to zero, the agent is immediately terminated.

5.5 User authorization

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.

5.5.1 User identity

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.

5.5.2 Authorization agents

An authorization agent is a special-purpose agent that has the following distinguished features:

  • Its address is public. The address can be found for example using a name server.
  • It possesses certain rights (addresses) to do things such as start new agents.
  • It implements some kind of authorization method.
  • It grants some subset of the rights it possesses to other agents that are able to authorize themselves properly.

5.5.3 Authorization methods

There can be several methods for authentication. The security of authentication relies partly on the cryptographic protection of the inter-domain connections. RSA authentication

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:

This message is sent to the authorization agent by an outsider. It requests the authorization agent to send an RSA challenge.
This message is used to deliver a new RSA challenge to an outsider agent trying to authorize itself.
RSA-RESPONSE(challenge, response)
This message is used to respond to an RSA challenge.
This message is sent by the authorization agent to the outsider if the RSA authorization succeeds. It gives the remote agent a proxy address that can be used to access a subset of the rights owned by the authorization agent.

© SchemeStation project 1997-1998 [Back to the document index]