Sergiu Ivanov wrote: > Is it possible to run only *parts* of the Hurd on separate computers, > that is, make the Hurd a kind of a network operating system. It most > probably sounds crazy, but I know that only a microkernel OS can do > something like that, so the Hurd may be appropriate :-) > > Sorry for being late with the idea :-( > > scolobb >
Apologies too for being late in posting this. Also apologies if this is the incorrect place for this. I'm not sure if this is the correct thread to post it to but I was thinking of posting it to threads which have been referred to in this thread. It also a bit "blue sky" (brainstorm). I've been working on a distributed scheduler for some time and after reading the papers by Walfield and Brinkman (see below) I've been wondering whether the work I've been doing could be used in the Hurd? What I've detailed so far in the work is more of a resource allocator than a scheduler. Below I've pasted the contents of an email I sent recently to a contact and I have written a a fairly detailed report. The report is at: /doc/reports/report01.txt http://bazaar.launchpad.net/~jason-cozens/eqp/trunk/files Best Wishes, Jason Cozens. ----------------------------------------------------------------------- N.H. Walfield, M. Brinkman "Improving Usability via Access Decomposition and Policy Refinement" 2007. http://www.walfield.org/papers /20070104-walfield-access-decomposition-policy-refinement.pdf N.H. Walfield, M. Brinkman "A Critique of the GNU Hurd Multi-server Operating System" 2007 http://www.walfield.org/papers /200707-walfield-critique-of-the-GNU-Hurd.pdf ------------------------------------------------------------------------ Reliable Computing - Main Objectives ------------------------------------ The major objective that I am working on is how to make general purpose operating systems more reliable. Reliability in this context is concerned with the ability to build component based systems whose emergent behaviours can be proved correct from formal models of the components. With reliability comes the ability to build larger systems more easily. I am investigating whether hardware isolation of processes can improve reliability. I have taken this hardware isolation to the limit and require that each "process" runs on its own isolated processor. By having each process run on its own processor the possibility for proving process behaviour correct becomes more tractable. It becomes easier to formally define the processor architecture and the environment in which a process runs. From this the formal proof of correctness of a process's behaviour may be possible. Added to this the architecture put forward below uses a very simple protocol for process creation scheduling and resource allocation whose behaviour including failures can be proved correct using "A Simple Broadcast Calculus" which I'm currently writing up. It's not enough to design a new architecture and expect it to be adopted. For the new architecture to find widespread use it must support current software and ideally current software development paradigms. The new architecture should implement a POSIX compliant API. The intention is that each fork()/exec*() process creation will result with a new process on its own processor. As time goes on the creation of processes within code can be optimised to the new kernel. To this end the architecture is based on microkernels such as MINIX 3. MINIX 3 has been used initially for clean and simple structure. The real target operating system is the GNU Hurd. Though reliability is a laudable goal in its own right, performance is also crucial. The design is based on that of microkernels and at present these are known to have poor performance compared to monolithic kernels such as linux due to issues such as a large number of context switches and issues with message passing. The new architecture would have no context switching and would have message passing as a primitive. Each process would have its own processor with its own address space communicating with other processes using concurrent messages. When a processor had nothing to do it would drop into a low power state waiting for an interrupt or other event to restart it. The objectives in design in order of importance are: 1. Reliability. 2. Ease of Software Migration. 3. Performance. Outline of Work so Far - Introduction to ROCK and EQP ----------------------------------------------------- This section is a high level overview of the work I've done so far. The main result of the work I have been doing so far is a kernel I call ROCK (Reliable Optimising Concurrent Kernel). The kernel is made up of a network of worker processors where each worker processor is tightly coupled to one or more QCells dedicated to the worker. A basic assumption of most OS design that processors have to be kept busy is questioned and instead it is assumed that there is an abundance of very simple processors (1000+) and communication is cheap. The worker processors (Processor 1, 2, etc.) communicate with each other using messages over the inter-processor communication (IPC) channels. This is fairly standard. The QCells (QCell 1, 2, etc.) communicate with each other using broadcast messages over the inter-qcell communication (IQC) channels. Each Processor / QCell coupling communicates using a private channel. The diagram below shows the case where each Processor has one QCell. IPC IQC Channels Channels +-------------+ +---------+ !/?---o Processor 1 o----o QCell 1 o---!/? | +-------------+ +---------+ | | | | +-------------+ +---------+ | !/?---o Processor 2 o----o QCell 2 o---!/? | +-------------+ +---------+ | | | | +-------------+ +---------+ | !/?---o Processor 3 o----o QCell 3 o---!/? | +-------------+ +---------+ | | | | +-------------+ +---------+ | !/?---o Processor 4 o----o QCell 4 o---!/? | +-------------+ +---------+ | | | | +-------------+ +---------+ | !/?---o Processor 5 o----o QCell 5 o---!/? | +-------------+ +---------+ | . . . . . . If we let { --- } represent a process slot on a processor and { p x } represent process x running on a processor the ROCK kernel in an unassigned state can be depicted as: { --- } { --- } { --- } { --- } { --- } +-----+ +-----+ +-----+ +-----+ +-----+ | P 1 | | P 2 | | P 3 | | P 4 | | P 5 | IPC o-----o-----o-----o-----o-----o-----o-----o-----o-----o... | | | | | +-----+ +-----+ +-----+ +-----+ +-----+ | Q 1 | | Q 2 | | Q 3 | | Q 4 | | Q 5 | +-----+ +-----+ +-----+ +-----+ +-----+ | | | | | IQC !/?---------!/?---------!/?---------!/?---------!/?..... The purpose of the QCells is to manage the allocation of processes to processors or more generally the allocation of resources. This is achieved by the QCells maintaining a shared token that manages an eager queue. An eager queue is based on the idea that every processor in the queue wants to find some work and will keep announcing its availability until it gets some. The protocol running on the IQC is an Eager Queue Protocol (EQP). This is a protocol that is designed to: * Be responsive - work requests should be actioned quickly. * Minimise collisions. * Minimise the last broadcast time for all processors. - This is so processors are "known" to be alive. * Provide state information on the network. - This allows processors to be switched on and off as the work load varies. - More generally it forms the basis for a feedback control system. * Provide fault tolerance. To illustrate the use of ROCK, the following diagram shows how it is hoped to fit ROCK into a MINIX 3 like microkernel architecture. +------------------------------------------------------------+ Layer 4. | User Process { p 4 } | +------------------------------------------------------------+ Layer 3. | Server Process { p 5 } | +------------------------------------------------------------+ Layer 2. | Device Drivers { p 3 } | +------------------------------------------------------------+ Layer 1. | { p 1 } { p 2 } | +------------------------------------------------------------+ +-----+ +-----+ +-----+ +-----+ +-----+ | P 1 | | P 2 | | P 3 | | P 4 | | P 5 | IPC o-----o-----o-----o-----o-----o-----o-----o-----o-----o... | | | | | +-----+ +-----+ +-----+ +-----+ +-----+ | Q 1 | | Q 2 | | Q 3 | | Q 4 | | Q 5 | +-----+ +-----+ +-----+ +-----+ +-----+ | | | | | IQC !/?---------!/?---------!/?---------!/?---------!/?..... In this architecture the virtual processor architecture of traditional posix operating systems is realised using "concrete-virtualisation". That is each process runs on a concrete processor but the network is virtualised the resource allocation of an eager queue protocol. Looking at the design of the kernel it meets the minimal design pioneered by Brinch Hansen's Nucleus (Hansen, 1970): 1. some mechanism for dealing with address spaces — this is required for managing memory protection; 2. some execution abstraction to manage CPU allocation 3. inter-process communication These are satisfied as follows: 1. Each process would have its own address space as it is running on its own processor. 2. The Eager Queue systems is a general resource allocation system and can allocate processors (CPUs) as well as other resources. 3. Message passing would be a primitive in the system in a similar way to Erlang (http://www.erlang.org/). The major difference to Nucleus is the creation of processes. Processes in ROCK are created by finding a free processor. Conceptually the system has similarities to Singularity (Fahndrich, Aiken, et al., 2006 and Hunt, Larus, 2007). However rather than "Rethinking the Software Stack" and implementing the isolation of processes using complex software, ROCK "Flattens the Software Stack". This gives the software developer a simple model akin to the programming model of real time and embedded systems. This model hopefully avoids much of the non-determinism of existing general purpose operating systems. Background Work --------------- This section summarises the work that I have completed so far. It is all publicly available and all code has been written under GPL v3.0. In January 2006 I started making some notes on eager queues on NovellForge, these are fairly brief and can be found at: http://developer.novell.com/wiki/index.php/OpenEd_-_Lab_4 In January 2007 I moved to SourceForge and explored writing a simulation in CS, I made some progress with this but it was slow. I also started some work on Broadcast Calculi which lead to "A Simple Broadcast Calculus". In February 2008 I moved to hosting the project in Launchpad. Since hosting the project here I have written a python simulation of an eager queue protocol and started work on an implementation using Erlang. So far in Erlang I have written a queue protocol. Motivation ---------- A general purpose operating system's main function is to share out the CPU amongst processes. A process is a program running on a virtual processor. The operating system implements the virtual processors for the processes. One of the major benefits of a general purpose operating system is that its virtual processor architecture is not static but can vary dynamically almost without limit. This is achieved by the ability for processes to create and destroy other processes. This functionality is also implemented by the operating system using functions such as fork, spawn, kill, etc. The operating system can be seen as having an unlimited pool of virtual processors which processes can use to create dynamically varying networks. The versatility of a general purpose operating system often comes at the cost of reliability and predictability largely stemming from the non-deterministic programming model that is a result of its design. The non-determinism arises from the multiprogramming model. The ordering of process execution is controlled by the operating system. A process is active only when it is in control of the program counter. In the simplest systems there is only one program counter. The operating system behaves as a largely unobservable and unpredictable adjudicator in a competition for the program counter. Though each process will control the program counter in a deterministic way the real time properties of the program counter and hence the processes are lost. This leads to non-deterministic program models such as threading. The complexities of programming models such as threading and the fact that in reality all processes are really running as one process in one address space leads to much of the unreliability of general purpose operating systems. Processes do not run in isolation but require to communicate with each other. As well as providing a pool of virtual processors an operating system needs to provide a communication mechanism between processes. This mechanism is called inter-process communication. Operating systems have become more powerful largely through hardware improvements that have permitted the continuation of the many processes running as one process model. Attempts to use more physical processors have often failed due to the lack of versatility in the resulting architectures. Is it possible to replace the pool of virtual processors with a pool of real processors without losing the versatility of the single process model? The implementation of such a system using a distributed resource allocation mechanism is the central aim of the work reported here. There are many ways of implementing the communication infrastructure. For example to create a dynamic network we can use local wireless communications. Different frequencies can be used by different process groups. Inter-process communications would have their own communication channels/frequencies. The major problem is how to manage the pool of processors. This can be implemented by doing away with the centralised scheduler and letting each processor manage itself. The problem is now really one of resource allocation rather than scheduling. So that the resource allocation is robust there needs to be no single point of failure. To maintain versatility the state of the resource allocation needs to be observable between the processors. To achieve this a set of broadcast based protocols is proposed called Eager Queue Protocols (EQP). The following hints at an equivalent to a fork() in such a system. pid = iqc.Request() ipc.Send(pid, program) EQP is then used in a new general purpose kernel called ROCK. ROCK - Robust Optimising Concurrent Kernel ------------------------------------------ ROCK uses EQP to replace the scheduling and process creation part of the kernel. If we consider MINIX 3 as an example of a microkernel it is possible to see where ROCK fits into a general purpose architecture. MINIX 3 is a clean implementation of a microkernel design and allows us to concentrate on what is in the "core" of the operating system. +------------------------------------------------------------+ Layer 4. | User Process | +------------------------------------------------------------+ Layer 3. | Server Process | +------------------------------------------------------------+ Layer 2. | Device Drivers | +------------------------------------------------------------+ Layer 1. | Kernel | System Task | Clock Task | +------------------------------------------------------------+ The layer we are looking at replacing is Layer 1, the Kernel. In Minix the kernel implements the following: * Manage Interrupts and Traps * Saving and Restoring Registers * Providing Services to the Next Layer * Scheduling * Messaging and Communication services In ROCK we are now running on multiple processors. Interrupts are handled by dedicated processors, there will be less need for Traps. Saving and Restoring registers will be required much less as each process will now be running on its own processor. Services to the next layer will need further consideration. Scheduling will be handled by EQP. Message and Communication services will be handled by each processor directly. The architecture now looks as follows: +------------------------------------------------------------+ Layer 4. | User Process | +------------------------------------------------------------+ Layer 3. | Server Process | +------------------------------------------------------------+ Layer 2. | Device Drivers | +------------------------------------------------------------+ Layer 1. | ROCK | +------------------------------------------------------------+ In the hadware we now have a network of Processor / QCell pairs (more generally there can be many QCells for a given processor). The QCells communicate over inter-qcell-channels whilst the processors communicate over inter-processor-channels. +----------------------------------------------------------... Layer 4. | User Process +----------------------------------------------------------... Layer 3. | Server Process { p 5 } +----------------------------------------------------------... Layer 2. | Device Drivers { p 3 } +----------------------------------------------------------... Layer 1. | { p 1 } { p 2 } { p 4 } +----------------------------------------------------------... +-----+ +-----+ +-----+ +-----+ +-----+ | P 1 | | P 2 | | P 3 | | P 4 | | P 5 | IPC o-----o-----o-----o-----o-----o-----o-----o-----o-----o... | | | | | +-----+ +-----+ +-----+ +-----+ +-----+ | Q 1 |<--->| Q 2 | | Q 3 | | Q 4 | | Q 5 | +-----+ +-----+ +-----+ +-----+ +-----+ | | | | | IQC !/?---------!/?---------!/?---------!/?---------!/?..... The QCells use an Eager Queue Protocol to communicate over the IQCs. EQP (Eager Queue Protocols) --------------------------- Eager Queue Protocols are simple protocols based around a small set of messages. A message consists of A Sender, an Action and an EQ data structure. The message is broadcast over an inter-qcell channel (IQC). There can be many IQCs and these can be created dynamically. Some will be short lived, while some IQCs will outlive the lives of individual processors. Taking iqc as an IQC, then a broadcast can be defined as follows (as seen by an observer of the channel). iqc.{Sender, Action, EQ} There are 6 Actions: * JOIN * UPDATE * EXIT * REQUEST * ACCEPT * DECLINE At its simplest the EQ data structure is simply a list of processors with the processors listed in the order of last broadcast with the most recent at the head of the list. For example in: [p2, p3, p1, p5, p9] p2 was the QCell that most recently broadcast. p9 was the lease recent broadcaster. More complex EQ data structures can be defined. The mechanics of an eager queue protocol are based on the following: * Multicast (broadcast) messaging * Heartbeat * Token Multicasts/Broadcasts are used so that all processors linked into an eager queue are constantly updated. Update messages are sent regularly (possibly at 10KHz or more) using a distributed heartbeat. This is so the system is responsive, that is requests can be satisfied quickly and new processors can join quickly and existing processors can exit quickly. In its quiet state observing an eager queue channel will result in the following sequence of Actions: wait -> UPDATE -> wait -> UPDATE -> wait -> UPDATE -> . . . The eager queue data structure forms a shared token that all QCells have. This has some similarities to the use of tokens in (Hansen, Jansen, et al., 2005). The token is used to establish who is next to broadcast, when requests can be made, who will accept a request and also to minimise collisions during requests and state changes. If we look at the complete sequence of UPDATE messages we would see something like: * wait * {p2, UPDATE, [p2, p3, p1, p5, p9]} * wait * {p9, UPDATE, [p9, p2, p3, p1, p5]} * wait * {p5, UPDATE, [p5, p9, p2, p3, p1]} * wait * {p1, UPDATE, [p1, p5, p9, p2, p3]} * wait * {p3, UPDATE, [p3, p1, p5, p9, p2]} * wait * {p2, UPDATE, [p2, p3, p1, p5, p9]} * . . . The UPDATE messages act as a synchronising pulse. All other messages will occur after an UPDATE. This is key to reducing collisions. Monitoring the IQC, message sequences will always be of the form: UPDATE -> MESSAGE* -> wait-> UPDATE -> MESSAGE* -> wait -> UPDATE... Where MESSAGE := JOIN | EXIT | REQUEST | ACCEPT | DECLINE The exact sequences of messages can be defined as a regular expression. This is the characteristic signature of an Eager Queue Protocol: (->wait->UPDATE((->REQUEST->DECLINE*->ACCEPT)|->JOIN|->EXIT)*)* An UPDATE will only ever occur after a quiet (wait) interval on the IQC. If a processor wants to REQUEST another processor, it does so by broadcasting a REQUEST after an UPDATE. The exact time it can broadcast the REQUEST is determined by its position in the eager queue. EQP dictates that a REQUEST must be followed by an ACCEPT or DECLINE. In the current EQP implementation the processor that must accept is the processor at the head of the queue, i.e. the most recent to broadcast (the choice of processor can be changed, e.g. to the processor that has been waiting longest etc.). * {UPDATE, [p2, p3, p1, p5, p9]} * {REQUEST(p99), [p2, p3, p1, p5, p9]} * {ACCEPT, [p3, p1, p5, p9]} In the current implementation when an ACCEPT happens the accepting processor is removed from the queue, this may also be changed so that the state of processors is kept in the queue, also in the current implementation the requesting processor does not have to be in the queue. Because the whole system has no hard handshakes processors need to be able to decline a REQUEST, for example when a processor is shutting down or just pulling out of the queue. If a processor declines then the next processor in line has to ACCEPT or DECLINE, this continues until the REQUEST is accepted or the system is exhausted. Exhaustion should be rare as it is assumed that there is a large number of available processors and processors switch on when the supply of available processors is low. * {UPDATE, [p2, p3, p1, p5, p9]} * {REQUEST(p99), [p2, p3, p1, p5, p9]} * {DECLINE, [p3, p1, p5, p9]} * {DECLINE, [p1, p5, p9]} * {ACCEPT, [p5, p9]} If we add requesting processors into the queue then collisions can be further avoided by allocating timeslots when requests can be made. The time slots can be as small as the signal detection time. |<- UPDATE ->|<- r1 ->|<- r2 ->| . . . |<- rn ->|<- JOIN/EXIT ->| If there are a large number of potential requesting processors rather than have n time-slots, e.g. |<- UPDATE ->|<- r1 ->|<- r2 ->| . . . |<- r16 ->|<- JOIN/EXIT ->| The transmission slots can be arranged in a square grid: |<- UPDATE ->|<- r1 ->|<- r2 ->|<- r3 ->|<- r4 ->|<- JOIN/EXIT ->| |<- r5 ->|<- r6 ->|<- r7 ->|<- r8 ->| |<- r9 ->|<- r10 ->|<- r11 ->|<- r12 ->| |<- r13 ->|<- r14 ->|<- r15 ->|<- r16 ->| If there is a collision in a time slot the column is flattened to resolve the collision: |<- UPDATE ->|<- ! ->|<- r1 ->|<- r5 ->|<- r9 ->|<- r13 ->|<- r2 ->| |<- ! ->| |<- r6 ->| |<- ! ->| |<- r10 ->| |<- ! ->| |<- r14 ->| The time slots can be tuned statistically based on the history of the channel. The JOIN and EXIT actions allow processors to join and exit an eager queue. * wait * {p2, UPDATE, [p2, p3, p1, p5, p9]} * {p1, EXIT, [p2, p3, p5, p9]} * {p99, JOIN, [p99, p2, p3, p5, p9]} * wait * {p9, UPDATE, [p9, p99, p2, p3, p5]} * ... The above has just outlined how an Eager Queue Protocol works. More detail can be found on the Launchpad EQP project site: * https://launchpad.net/eqp REFERENCES ---------- (Fahndrich, Aiken, et al., 2006) "Language Support for Fast and Reliable Message-based Communication in Singularity OS" Fahndrich, M., Aiken, M., Chris Hawblitzel, Orion Hodson, Galen Hunt, James R. Larus and Steven Levi. EuroSys06, April 18-21, 2006. (Hansen, 1970) "The nucleus of a multiprogramming system" Hansen, Per Brinch Communications of the ACM Volume 13 , Issue 4 (April 1970) Pages: 238 - 241 Year of Publication: 1970 ISSN:0001-0782 (Hansen, Jansen, et al., 2005) "RTnet: a distributed real-time protocol for broadcast-capable networks" Hanssen, F.; Jansen, P.G.; Scholten, H.; Mullender, S. Autonomic and Autonomous Systems and International Conference on Networking and Services, 2005. ICAS-ICNS 2005. Joint International Conference on Volume , Issue , 23-28 Oct. 2005 Page(s): 18 - 18 Digital Object Identifier 10.1109/ICAS-ICNS.2005.85 (Hunt, Larus, 2007) "Singularity: Rethinking the Software Stack" Hunt, Galen C., Larus, James R. Microsoft Research Labs, 2007. (Thomsen, 1989) "A calculus of higher order communicating systems" Thomsen, Bent Annual Symposium on Principles of Programming Languages Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages Austin, Texas, United States Pages: 143 - 154 Year of Publication: 1989 ISBN:0-89791-294-2
