Here is a short summary of this document.
SCHEMESTATION is a simulator for an experimental distributed operating system. The main features are transparent migration and inherent security. This simulator has implemented many concepts that will be used in the future operating systems.
The SCHEMESTATION project, spanning over eight months, moved forward like a clockwork; there was constant progress throughout the project with no bigger difficulties. The overall development process was highly parallel, thanks to the CVS configuration management software.
The project was a success. The fact that we were able to fulfill all the requirements set to the project confirms this.
The work was done following a two-round spiral development model instead of the pure waterfall from the course's template. This introduced some difficulties, but it was the key to our success. Due to the lack of human resources (we had only four team members) we minimized the project management bureaucracy.
The simulator could be used as a model for a "real" implementation on the top of bare hardware. Also, Just-In-Time (JIT) -bytecode compiler in addition to optimizing Scheme-to-bytecode compiler could enhance the performance of the system dramatically.
We had funding for a 1200-hour project; we consumed 1228 hours, which can be regarded as nothing short of a miracle, considering that we produced over 110.000 lines of code and documentation.
Overall, this course is definitely one of the most useful courses that are available for CS students at HUT, even though we "overenjoyed" it a bit.
The initial objective of the SCHEMESTATION project was (1) to evaluate the SCHEMESTATION concept via the means of implementing a prototype; (2) to research the agent based programming paradigm as the basis for development of modern operating systems, and (3) to establish a system on which students could experiment on distributed programming using the Scheme programming language.
The basis for this project was the SCHEMESTATION operating system concept defined in [Operating system specification]. In practice, the project involved implementing a working and functional simulation of the system on the top of a Unixtm system.
The initial objectives of the project did not involve any commercial means, and one could not expect this project to yield any completed commercial product. While this kind of smallish and humble project involving basic reseach might appear useless, we shall take the opportunity to compare our concept to some related projects.
It seems clear that the future of the operating systems will exhibit highly distributed computing, fault tolerance, location independence, and other natural needs that the present operating systems fail to satisfy.
Most of the current research projects seem to have taken the approach that computers merely provide services --- computing power, data storage, peripherals --- that the users can access without knowing for example in what exact location the computation takes place or the data gets stored. In other words, a single operating system controls perhaps several computers. This is what is meant by location independence and distributed computing. An advanced operating system can balance usage of the resources, so that all of the resources get used nearly optimally. This is often referred to as load balancing.
In the extreme, this kind of a model implies that the units of execution (traditionally a.k.a. processes --- agents in the SCHEMESTATION concept) and other data collections have no direct connection with the underlying platform whatsoever. Instead, the operating system may move them freely from one location to another. This may happen for example when the system's resources are inequally burdened. The moved object can be ignorant of its location and thereby about the movement.
We take as an example an interesting operating system research project from the Microsoft Corporation called Millennium.
According to the document Microsoft has published in the WWW, the status of Millennium is that the development team has merely outlined the concept for now. They have loosely described the requirements they have set on the forthcoming system. While the specifications published are not nearly as detailed as ours, it can already be concluded that many of the design choices are similar.
The major goals the Millennium team has established can be summarized to be
For those mentioned we have already implemented: seamless distribution (based on transparent migration), worldwide scalability, self-tunability. Also, our simulation provides an interface for the sophisticated security Scheme the SCHEMESTATION operating system concept introduces, and implements part of it. It was out of the scope of this project to explore the self-configuration, fault tolerance and resource controlling issues, partly due to the the lack of resources.
It has been a pleasure to work on such a sophisticated concept. Our project was not about just another standard project on web tools and providing "added value" for the customer through MS Back Office products and/or Lotus Notes.
It is exciting to think that these kind of ideas will be used in the mainstream operating systems within near future (five to ten years). It is left as an excercise to the reader to think how many of the hot web products of today will still be used then.
As an overall view of the project progress, it can be stated that the project moved towards its goal from start to finish, without ever looking back, not to mention stopping. That could be used as the frame of reference when considering the difficulties and successes we experienced on the way to the final success.
When the requirements of the project were considered, the inevitable truth of the amount of work required to complete the project came up. This was by far the biggest risk factor in the project: how could we do enough work to come up with all the pieces and then glue them together? It was decided then, that the only solution to this problem would be to try to do as much "real work" in the beginning of the project as possible. This was a very good decision! By delaying part of the specification and design of the upper layers while implementing the lower layers the project justified itself. We used extensive scheduling (see Project plan - SchemeStation) to the smallest detail to make sure of the continuous progress, and this proved to be a good solution when the time was a limited resource. By December 1997 we had a working Scheme programming environment, virtual machine, heap and networking co-operating. As a proof for that the project could be finished, this had a significant impact on the overall work morale.
We used internal two-round scheduling (spiral model, with two rounds) with miniature milestones (the course's phases restricted this a bit, but on the other hand provided additional milestones). The first round consisted of the lower layers of the system and this work was done during the first three phases of the course. The second round of the spiral consisted of the upper layers of the system (primarily Scheme-oriented coding after the infrastructure was done). Within a spiral round we did all the conventional phases of a project: specification, design, implementation and testing. This worked well, in spite of the fact that the course's template does not suite too well to this approach (it was clear that we could not get the message of using this methodology through to the project's management group, even though we mentioned it many times).
Due to the nature of this project, a research simulator for something not very well defined beforehand, there was a problem of no one controlling the project from the outside. There were few times when we could have used some encouragement from someone who could have seen where we were, instead of everyone suspecting if we were able to deliver anything at all (or speculating what was the "thing" that we were doing). But this was also our strength, as we could focus on the problems our own way, and make independent decisions (of course, with major issues we had meetings with our client and supervisor). The fact that there was little confidence in our abilities did increase the will to demonstrate that we knew what we were doing.
This project did demonstrate the fact that where there is vision, enthusiasm, people that are willing to work for fame and glory, and the people form a working team, there is the possibility of creating something that cannot be done otherwise with similar resources. We think that this project belongs to this category, and we are proud of what we have achieved.
We will now examine the results of the project in view of the project requirements that are found in Project requirements specification.
Project requirements specification defined eleven functionality requirements.
This requirement has been met.
There exist two separate applications that implement a network simulator and a domain simulator. The network simulator is capable of monitoring amounts of data transferred. Network topology can be changed interactively.
There is an extensive set of debug flags that can be toggled independently.
This is the fundamental functionality of the system.
This requirement has been met.
This requirement has been met.
There exists a SSDOC text terminal, with color, that can be used to interact with a SSDOC domain.
This requirement has been met.
This requirement has been met, though support is quite rudimentary. See Notes on Implementing the SchemeStation Security Paradigm in the SchemeStation Simulator.
This requirement has been met; whole domains are persistent.
This requirement has been met. Some example applications exist, including shell and some games. However, the current cross-compiler is too big to be ported into the simulator using only a reasonable amount of effort, and besides, it would run quite slow.
The system also meets the non-functional requirements specified in Project requirements specification. Hundreds of actors can be run in one domain and tens of communicating domains can be run concurrently. Naturally, the performance of the underlying system is reflected in the performance of the simulator. Documentation has been also provided as required. Failure situations are handled correctly. Especially user programs that execute illegal instruction sequences are immediately terminated. The system is portable and has been successfully ported to a 64-bit Alpha/OSF architecture from a 32-bit Intel/Linux platform.
Extensive usability tests have not been performed, except that we have had one second-year CS student use the system for a couple of days. The following are some quotes from her:
Using the system does not seem to be difficult. It should be possible to learn to use it quite fast. Starting new agents and communicating with them has "succeeded" quite well. Naturally, I had difficulties at the beginning, but many things became clear just after the beginning.It has been very interesting to use SCHEMESTATION, because it is something you don't see every day... So I cannot say it's hard to use, though it requires some time to get familiar with. But then it is fun!
The environment seems to be useful for several purposes. Scientific research --- why not. For an average student the environment is probably really nice if one wants an own sand-box where you can test all kinds of things, and you can learn quite a lot from that... I see no reasons why this system could not be used in some way for education purposes.
I think also that the project and the system can act as inspiration for others!
The quality plan (in Project requirements specification) gave the quality requirements that the project should met. The result system is able to fulfill all those requirements. The original quality plan was criticized of being a bit ambiguous --- but it is very difficult to state requirements for an operating system simulator. Here are the statements from Project requirements specification:
This requirement is assumedly met, though giving an exact measure is hard. There is an enforced coding policy followed throughout the system. The code is highly modularized; each code module consists of an implementation of a subsystem that cannot be considered too complex. The code is commented where necessary and documented.
This requirement has been certainly met. (This is the most visible part of the system.)
This requirement has been met. This is, however, something quite hard to measure; we approached this from the perspective of comparing some of our agent implementations to similar programs in other environments, and found out that this statement holds. The only real complexity comes from the fact that we did not have time to implement a compiler (and an editor) inside the SchemeStation; using the cross-compiler and interacting with the object server is required.
This requirement has been met. Particularly, on an Alpha platform it is very convenient to run multiple interactive agents interacting with a rudimentary windowing system, written completely in Scheme.
It must be noted that the term "practical" is somewhat arbitrary, especially in case of a simulator environment. The barebone VM system is quite fast, but the message passing schema did introduce a somewhat unexpected slowness to the system, as did the output of our compiler (not too optimised bytecode). The system was developed on a standard PC with Intel P166 and 64MB of memory. This hardware configuration should be considered as the lowest-level system, as it yields a usable SchemeStation. As the Digital Unix port was completed, it was observed that the 433MHz Digital Alpha workstation ran the SchemeStation very well, with almost 10-fold increase in performance (due to the internal 64-bit architecture of both the SchemeStation and the Alpha processor).
This requirement has been met via extensive documentation. All project members participated in the documentation process and all documents have been cross-checked between project members. We have been able to communicate the system design to the client.
This requirement has been met; see above.
Naturally, as the project is just being finished, experience about educational use is not yet available. We believe that this quality requirement has been met, however.
This requirement was met, given a particular interpretation for the phrase "most".
A higher-level aim of the project was to examine SCHEMESTATION concept as defined e.g. in Operating system specification. The following observations were made.
The concept itself works pretty well and could be very suitable as a basis of a real operating system. However, the current design has at least two problems that need to be addressed in future revisions.
The first problem is that every agent has only one address and that knowing an agent address is equal to having all access rights to the corresponding agent. This is not normally a problem due to the notion of using proxies. However, an anomalic situation follows when one considers messages that are used to request an agent to terminate. Naturally, also proxies need to respond to such messages, because otherwise proxies cannot be removed. But, if a proxy corresponds to a public service, then everyone is able to delete the proxy implementing the service, and thus deny the service from all users! This can be circumvented easily by using some secret information to identify "privileged" messages, but this is not necessary the best solution. Another way could be to have exactly two ports, a "standard" port and a "privileged" port, though it is hard to see why one could not then have actually more than two ports like in MACH and forget the proxies altogether.
The second problem is related to the semantics of message passing. In Operating system specification it is specified that the mutual ordering of messages sent by one agent to one address is preserved. This semantics does not work well with idea of dynamically changed the routes messages travel from one domain to another via address indirections, because changes in the indirections can break the ordering of messages. The cleanest and best solution is to remove the order-preserving semantics, which is a bit ad hoc anyway.
In the beginning of the project we adopted a ten-issue list that a good, successful project should follow.
The list introduces things that one should remember throughout the project -- it is not enough just to think them in the beginning.
Below, we have listed the issues. We have tried to explain how we understand the issue, and how we have managed to fullfil it in this project.
The objective is the reason why the project should be initiated in the first place. The objective of a project is not to implement an exciting system that can do a number of things. The objective of a system is to implement a system that has some kind of value; addresses a problem of a client --- in a word, does a task.
This was one of the most difficult issues to cherish. We had no commercial objectives. It was unclear (and still is) whether anybody will actually use this OS simulation for anything. The client appeared to have regrettably little interest in our project not only in the beginning of project, but throughout the project --- even though he had personally agreed to act as a client.
The intention was to provide something to the basic research of operating systems, distributed programming and the agent paradigm. Also, we hoped that the end product might be used for example in teaching agent programming using Scheme language in the CS laboratory of HUT.
Considering this, setting the objective and furthermore, reaching it, was hard. Still, we were able to set goals for the project as an instrument of learning project working methods, group work and programming. All of us have learnt tremendously on all of these areas during this project. After all, this was just another course. Having completed it certainly has a lot of value in the future. In this sense, we have definetely reached our objective.
In the beginning this was not easy, since the system we aimed to implement was not defined on paper but just in the thoughts of the principal designer. We had the requirements definition, but still it soon got clear that we had to write these thoughts down in detail. This was done by the principal designer Antti Huima, and after this, we have had no problems with the project outline. The project outlining was also affected by the decision to use two-phased spiral development model, which allowed us to postpone some of the design issues; in both phases the outline was defined from the beginning, but as the second phase did not start until December 1997, the full project outline was not defined until January 1998. However, this proved to be an excellent choice of work decomposition.
We knew from the very beginning that this project was going to take a lot of work. We knew, that it might well prove impossible to accomplish. It was doubtful, whether the members could find the time for it.
Judging afterwards from the used resource, the actual usage appears almost surprisingly modest. There have not been any major drawbacks or problems that would have needed considerable additional resources.
This is partly due to the tabula rasa situation the project originates from --- there existed nothing beforehand, that our product should comply to. Due to this, we faced no surprises from outside of our own artifacts. Still, it is incredible how little actual difficulties tampered our project.
The initial work amount estimates were based on the amount of hours the course is credited: 200 hours / person, which makes it a 800 hour project. However, this was considered way too low, and we increased it to 1000 hours and reserved funding for a 1200 hour project. This last estimate was quite accurate, we exceeded it only a few hours.
For this kind of project that is not mainly the only task of the worker, it is, if possible, even harder to estimate when certain modules get completed. This issue was addressed with two different approaches. First, we decided to put heavy early emphasis on the project workload, and the 2-round spiral model aided us in this. The framework, on which the whole project relied upon was finished before the 3rd phase deadline (december 1997). Second issue was to add internal milestones to each of the project's phases so that there was clear supervision of the progress of the project. These internal milestones would have enabled us to "press the panic button" in case of fatal delays.
However, the scheduling was a success; most milestones and deadlines were met with no or little difficulties. We had problems with the heap module almost throughout the project, but fortunately it did not affect the scheduling as the problems were fixed on the way to completing other things.
There should be a project plan that is not only created beforehand, but also maintained and updated throughout the project.
We have made a project plan that has been followed quite strictly. We have had just minor changes to make in it, but they have nevertheless been made.
The project management in this project had to be minimized in order for the project to be successfully completed. The minimization proved to be fairly effective, and the completion of the project is also a proof of successful project management.
During each phase, we tried to set our internal milestone so that action could have been taken in order to take control of a realized risk. We discussed the probable risks during our meetings and tried to identify the most threatening. Fortunately, it was not necessary to take any actions as there were no major realized risks during the project.
Change control was in an ambivalent state during the first round of our spiral mode development. There were lots of open questions, but there was no reason to address them before the start of the second round. Overall, there were surprisingly little change introduced to the plans and design that was originally made.
Measuring the completeness of the project was something that was taken as a serious issue from the beginning. It is one of the reasons we used the 2-round spiral model in the development, as we could divide the work into two distinct pieces. A more fine-grained approach was used within the rounds; we had set five (5) internal milestones as measuring points and this level of accuracy proved to be detailed enough for our purposes.
Things being the way they are, we consider acceptance testing consisting more of the project reaching its goals as of the statement of the client. In this sense, the project should be fairly acceptable.
We have already had a post-mortem session for the project (it was held 17th April 1998). Many beneficial things came up, including some listed here. The project can be considered as having been gracefully finished.
As the size of the project was known beforehand (and that there were only four members in the group), we made the decision to try to minimize the bureaucracy and try to reduce the working set of the project management methods to something practical. Things we decided to include were:
The things we intentionally left out:
Our feeling is that using a minimized project (and process) management method set is possible, but it does introduce new risks (which in our case did not materialize). The overall process becomes more dynamic and more unstable, so the control has to be much more immediate (short reaction time). One other thing that we discovered was that even if there is a special tool for doing something, the mere existance of the tool does not justify the function that the tool is for --- we had our own bug report tool and also could have used the bug report tool of the course - net result: no systematic bug reports were made.
The question of authority (or the lack of authority) was truly an issue for this project. It is problematic due to the fact that the project members are individual students, and there is no way to make them do anything except by encouragement and motivation: this leads to the authority solution of lead-by-example. We had two crisis points which resulted from the fact that the task we were carrying out was huge, and did not always seem to progress no matter how hard we worked. These situations could have been handled more efficiently (read: sooner, faster) if there would have been some kind of real authority to appeal to.
The significance of assigning exact tasks and supervising the progress was clearly evident. Weekly tasks are simply not done, if there is no direct control over the progress of the tasks. There was twice a situation (few months apart) where "relaxed" task definitions were given, with very unsatisfactory results.
The need for continuous supervision and project control clearly implies that given enough resources (we did not have any to spare), a dedicated project manager (with some additional secondary tasks) would be the right way to go.
The biggest obstacle we encountered during the project was how to communicate our status and progress to the management. And we partly failed, at least it is our impression. This communication problem was due to lack of human resources, there would have been need for a full-time process and documentation manager. The process manager could have laid out detailed plans for each phase for the management, and the documentation manager would have kept the structure of documentation in order. As we did not have these additional resources, the picture of the overall process might have been distorted so that the management was not enough convinced of our progress, at least from our perspective.
There were some minor problems worth mentioning concerning the project management:
Here are some comments extracted from above and our project's post-mortem session:
From the beginning, the SCHEMESTATION project has been looking forward and to the future. The biggest reason for implementing the simulator was to evaluate the SCHEMESTATION concept; this goal was met more than well. This being said, it is clear that possibilities for future work are plentiful. We discuss here some directions.
Next generation of a SCHEMESTATION system could be implemented as a stand-alone operating system on "bare hardware". A convenient way to do so could be to use existing parts of available free kernels, e.g. Linux, FreeBSD, NetBSD or Mach, or to use e.g. the Flux OSKit. This would be a very fascinating project, because several basic operating system components should be modified to work best for a SCHEMESTATION domain. For example, garbage collectors interacting with virtual memory systems exist. Moreover, efficiency gain with a JIT compiler would be probably tremendous.
Either the simulated system or a stand-alone implementation could be accompanied with a just-in-time compiler that transformed byte code instruction sequences to native instruction sequences prior to execution.
The current byte code layout is very normal, mimicking the instruction sets found from real CPUs. However, other compact representations for compiled code exists that can be e.g. tree-based. Such representations can achieve better space utilization and include more information for a JIT compiler to gain also in efficiency.
The current SCHEMESTATION cross-compiler, distributed with the simulator, is not good at optimizing and produces quite inefficient code. A new compiler could be designed. However, this does not seem as interesting project as the previous ones as good Scheme compilers exist already and there exists a lot of experience with regard to optimizing compilers.
Considering the estimates per tasks reinforces the fact that we were quite accurate when the first resource estimates were made: all those tasks that were possible to estimate, were estimated correctly. The overruns are mainly in programming and documenting, and some of the unexpected programming has resulted in unexpected testing.
Overall, we consider the resource usage a success, despite of the 22% resource overrun.
The workload has been fairly consistent, and it has been surprisingly equally divided between team members. In this perspective, the scheduling and resource allocation has worked very well.
The individual numbers can be seen from the progress reports. Here is a summary table of the resource usage:
| SchemeStation | PS | +/- | MÄ | +/- | SU | +/- | P1 | +/- | P2 | +/- | LU | +/- | Total | +/- | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Lectures | 11 | 0 | 0 | -8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 11 | -8 | |
| Studying | 9 | 0 | 13 | 4 | 6 | -10 | 0 | -8 | 0 | 0 | 0 | 0 | 28 | -14 | |
| Meetings | 32 | 0 | 30 | -10 | 26 | 0 | 26 | 0 | 30 | 4 | 32 | 16 | 176 | 10 | |
| Project management | 11 | 1 | 13 | 0 | 9 | -3 | 6 | -4 | 6 | 2 | 8 | 3 | 53 | -1 | |
| Design | 0 | 0 | 52 | 8 | 21 | -10 | 21 | 9 | 8 | -4 | 0 | 0 | 102 | 3 | |
| Programming | 0 | 0 | 85 | 5 | 50 | -10 | 73 | 33 | 111 | 79 | 66 | 26 | 385 | 133 | |
| Testing | 0 | 0 | 0 | 0 | 26 | -6 | 68 | 13 | 23 | -9 | 71 | 40 | 188 | 38 | |
| Documenting | 29 | 0 | 9 | 1 | 44 | 12 | 74 | 42 | 31 | -1 | 69 | 29 | 256 | 83 | |
| Maintenance | 17 | 0 | 3 | 1 | 4 | 1 | 3 | 0 | 0 | -3 | 2 | 0 | 29 | -1 | |
| Total | 109 | 1 | 205 | 1 | 186 | -26 | 271 | 85 | 209 | 68 | 248 | 105 | 1228 | 234 |
| PS | MÄ | SU | P1 | P2 | LU | Total | |
|---|---|---|---|---|---|---|---|
| Ville | 30 | 61 | 49 | 80 | 61 | 63 | 344 |
| Petteri | 34 | 51 | 46 | 70 | 49 | 65 | 315 |
| Antti | 32 | 53 | 36 | 98 | 56 | 64 | 339 |
| Jari | 13 | 40 | 55 | 23 | 43 | 56 | 230 |
| 109 | 205 | 186 | 271 | 209 | 248 |
The project plan was done with a 1000-hour schedule in mind, with an additional financial reserve for 200 hours more. We exceeded our budget by 28 hours, which is a cost of 28h*250mk/h = 7000mk. As the original budget was 300.000mk, this overrun is negligible. During the project our development machine's network card had to be replaced, introducing an expense of 150mk; the total sum is therefore 307.150mk, where the only real world cost is the 150mk for the new network card. We consider the project a success in this aspect as well.
| Item | Sum |
|---|---|
| Work | 250mk/h*1228h=307.000mk |
| Miscellaneous | 150mk |
| Total | 307.150mk |
When the idea of implementing the SCHEMESTATION as the course project was considered, the fact arose that it was to be a research project (with its own compiler, virtual machine, networking subsystem, etc, which would all have qualified as individual projects) instead of an implementation project (GUI and database). This put us into a not too favorable position from the beginning, as the comparison to other projects was difficult.
However, we did some minor detours on the way just to make sure that we were taken seriously. One of them was surely in testing, where we had to promise (well, at least that was the impression we had) a little too extensive formal tests for pieces which would have been implicitly tested during integration. However, we did even those tests, and the product is that much more reliable due to that, even with the fact that no additional bugs were found.
The course itself can be considered to be good -- there is a template which can be followed, or the project teams can operate with their own methods. The auditing sessions force the projects to have milestones, but these do not necessarily fit very well to the projects' internal schedules. However, this can be considered something from the "real world", and in the end they provide means to encourage and motivate the team.
We experienced the importance of a good client communications from a somewhat reverse point from normal --- we consider normal as something where the client has always something to say to some seemingly unimportant issues and not being able to decide what is wanted in the end.
The effort of more than seven months is now over. During the project, every member of our development team has probably learned a lot. Working first time as a project manager, I myself gained lots of insights into practical management of software projects and could probably do better next time.
I think that the current project is yet another proof of the fact that the following guidelines can never be followed too strictly:
Nowadays people do not like to say a good word of themselves as it is considered boasting and a sign of self-exclamation. However, ancient Egyptians did that quite a lot, especially in tomb writings. At this point I would like to follow them and say: Yes, I did a lot of work. And, yes, it was worth of it --- SCHEMESTATION runs now! I am not sure that every member of our team can join me in these words. [Ville Herva didn't consider the results worth of the efforts.] Thanks for you all!
Antti Huima
Project Manager & Principal Designer
William J. Bolosky, Richard P. Draves, Robert P. Fitzgerald, Christopher W. Fraser, Michael B. Jones, Todd B. Knoblock, and Rick Rashid. Operating System Directions for the Next Millennium. Position paper, January 1997.
W. Clinger, J. Rees: Revised Report on the Algorithmic Language Scheme, November 1991
Abelsson, Sussman: The Structure and Interpretation of Computer Programs, 2nd ed. MIT-Press, 1996