The Cycle-free approach and the Willie Kernel constitute a new approach to software development which, when used by programmers with a sound understanding of the cycle-free concept as well as more established software engineering ideas, can dramatically reduce the number of subtle bugs in a broad class of software systems. The Cycle-free method introduces a discipline that leads programmers to produce software in which key design decisions are made explicit and, consequently, easier to review. The Willie Kernel enforces that discipline and makes it possible to guarantee that the software has a number of highly desirable properties. The result will be software that is much less likely to experience a broad class of failures.
Like all disciplines and tools, the Cycle-free method and Willie Kernel introduce some restrictions on the class of systems that can be built. However, the restrictions are relatively mild and the class of products that can be built this way is broad and of growing importance. Further, many of these restrictions are not fundamental to the Cycle-free approach; future research and development may weaken or eliminate them and thereby broaden the range of applicability for the approach.
Real-time and interactive software systems are notoriously failure-prone and untrustworthy. This is caused by the fact that programming errors can be very subtle; some bugs can “hide”, survive inspection and testing, and then surface when a customer runs a critical application. Most experienced programmers believe that it is impossible to produce software with the same high reliability and trustworthiness exhibited by products developed using older technologies. Any method that can consistently improve the reliability and trustworthiness of software is potentially of great commercial value.
I have been asked to review a new approach to ameliorating software reliability problems, the Cycle-free method, which is supported by a software component known as the Willie Kernel. This report summarizes the basic ideas and discusses both the strengths and limitations of the Cycle-free approach.
As part of my review I read the “Technical Objections” posted by the developers on their web site. Most of these objections seem to result from limited review and limited perspective. All that have some validity have been considered and discussed in this report.
In the early 70s, the issue of imposing a hierarchical structure on software was quite controversial. Leading researchers such as Dijkstra, Wirth and Brinch Hansen all suggested that good software must be hierarchically structured, but other, equally experienced, researchers and developers claimed that the restrictions implied were unrealistic and that practical software could not be built with such restrictions. This disagreement between highly intelligent experts led me to research the issue and resulted in a well known paper, “On a Buzzword, Hierarchical Structure” [1], which has been widely quoted, reprinted and cited. The point of that paper was that the experts were disagreeing because they were not talking about the same thing. There are many structures (ways of dividing software into components and relations between those components) that one can identify in any software product. Some of these structures should be restricted to be hierarchical, but others should not. The experts had different structures in mind. My paper surveyed the various structures that were then being discussed. It points out that, most of the structures should be hierarchical, but identified a few that should not be subject to that restriction.
The most important of the structures identified at that time has become known as the “uses hierarchy”. This was discussed at more length in a subsequent paper (Designing Software for Extension and Contraction) [2]. The components are individual programs (methods in today's terminology) and the relation in the structure was “uses”, where we can say that “A uses B” if A cannot perform its specified function unless a correct version of “B” is present (invocable). The second paper demonstrates how loops in this relation can (and should) be removed, to result in a hierarchical structure. These ideas, which were quite controversial when first introduced, are now broadly accepted and taught.
The Willie Kernel and “Cycle-Free” philosophy propose imposing a hierarchical restriction on a structure that was not one of those discussed 30 years ago, but is closely related to the “uses” structure. It proposes benefits of hierarchical structure that were not discussed at that time. I have retained my interest in these topics, and, to the best of my knowledge, these ideas have not appeared in the literature.
In the Cycle-free approach, there are two distinct mechanism that one program can use to initiate execution of another program. The “normal” way is a “call” or invocation, which passes parameters in the way that is usual in modern programming languages. The second approach is for a program to signal an event that is “handled” by another program. No parameters can be passed with an event, but the “handler” can call programs that will access data associated with the event.
In the Cycle-free approach, programs and data are organized into contexts. Usually, contexts correspond to what were called “critical sections” in some of the early literature. Contexts can be assigned to levels. A program in context A can call a program in context B only if A is at a higher level than B. This imposes a hierarchical or loop-free restriction that is close to, but not identical to, the uses structure that was discussed so much earlier. The hierarchical levels assigned for restricting the calls relation to a hierarchy are also used to determine priority. If A can call B, B will have a higher priority than A whenever both are waiting for a chance to be executed.
However, the Willie Kernel does more. We can define a relation, “has initiated”, between contexts. Context A has initiated Context B if either (a) one program in A has either called a program in B or (b) a program in B is handling an event that was signalled by a program in A. Unlike most of the structures discussed 30 years ago, this is a dynamic structure, i.e. it changes during system execution. The Willie kernel does not allow a program that has been initiated to be initiated again before the previously initiated execution has been completed. Instead, the request for the program is entered into a queue. When a program invocation is complete, the queues are serviced using a round-robin policy but respecting the context hierarchy, and a new invocation will begin. This imposes a hierarchical restriction on the dynamic “has initiated” relation. This is an absolutely unique contribution of the cycle-free approach. I have seen it in no other system, nor read of it in any other paper. It is important to note that the first hierarchical restriction applies only to the “calls” form of invocation, while the second restriction deals with both events and calls. Using the event mechanism one can cause the invocation of a program at a higher level, but only if it is not already active. If the program that the event would initiate is already active when the event is signalled, it will be allowed to complete execution before it is initiated again.
These mechanisms have some properties that I believe could be proven though I have not seen a mathematical proof in any of the literature. Mutual exclusion of operations within a context is guaranteed and it appears that one can guarantee that all queued events will eventually run, i.e. that there can be no starvation or deadlocks caused by these mechanisms as long as the system has computational resources adequate for the requirements. The phenomenon known as priority-inversion, in which a high priority action loses its high priority status because it calls a lower priority program, cannot occur. However, event handling may cause a phenomenon resembling priority inversion, in which a high priority task waits for the completion of something with lower priority. This can only happen if the lower level (higher priority) program cannot proceed until the event has been handled. As with the restrictions discussed in the 70s, these restrictions have benefits and impose limitations. We will see that the Cycle-free approach can eliminate many frequent causes of bugs in software systems, and result in improved reliability and shorter development times. The restrictions that it imposes will be important in certain circumstances and will be discussed as well.
Experience in the production of real-time systems has revealed that there are many different sources of bugs. Among them are:
It is important to recognize that all of these problems stem from a single source of bugs, human error. Human error will be with us as long as we have humans and no method, however clever can keep programmers from making errors. However, researchers and educators have found that imposing specific structural restrictions on program developers, and on the programs that they produce, can reduce the number of errors; further, the errors that remain become easier to find. This was the result of the big “structured programming” debates of the 60s and early 70s. The claims that structured programs would always be correct, were quickly disproven but most programming teachers have found that those who accept the restrictions implied by the term “structured programming” make fewer errors and their programs are far easier to correct or revise.
In the debate about “structured programming”, it was once believed that the restrictions would lead to fewer errors but might also exclude certain good programs. However, over the years, we have learned how to eliminate the unnecessary restrictions while maintaining the discipline and the benefits associated with the discipline.
If one examines the list of bug sources above, one will see that certain problems are ameliorated by the Cycle-free approach while others are not affected.
My expectation is that if the Cycle-free mechanism and discipline are made part of a sound software engineering process, one in which key decisions such as the division of data into contexts and the use of events are reviewed, the number of errors in the initial version of the software, the debugging time, and the overall development time will all be substantially reduced. This appears to have been the experience to-date and I would expect it to continue as long as there is proper supervision and review.
The Cycle-free approach, supported by the Willie Kernel has been proven to be practical. Experience at VSI has shown that there is a broad area of applicability. However, while restrictions bring clear advantages, all such methods restrict the class of systems that can be built. This section discusses those restrictions, most of which merely identify areas where further research and development might be able to extend the area of applicability.
Real-time systems can be divided into two categories: interactive systems, and hard-real-time systems. In interactive systems, we want quick response but small delays are accepted and even a greatly delayed response can be useful. In hard-real-time systems, there are clear deadlines, i.e. minimum (and maximum) response times. Responses that are either too early or too late are not useful. Hard-real-time systems are usually systems that communicate with physical devices and with other systems that will not wait for a response or acknowledgement. Research in the area of scheduling for real-time systems has revealed that priority based scheduling is not always adequate (and rarely optimal) for such applications. Deadline scheduling makes better use of resources and can guarantee that deadlines will be met. Such scheduling can sometimes be performed before run-time but it is more frequently used during the running of the system. More information can be found in [3].
The current Willie Kernel, with its reliance on FIFO queues and event scheduling, is not designed for systems that should use deadline scheduling, particularly pre-runtime deadline scheduling. In the increasingly common situation where processor time is not a scarce or restricting resource, systems based on the Cycle-free Willie kernel will work in most cases but the danger of rare failures under high- load conditions would be present. With the queue disciplines used in the kernel, it would be very difficult to be sure that all hard deadlines would be met.
In spite of these limitations, a Cycle-free approach would be my choice for a broad class of systems. The enthusiasm of the programmers who have used this approach is obvious and I believe that it is well justified. For applications without hard real-time deadlines, and with ample computational resources, the restrictions that I have identified are not important.
I also believe that extensions/modifications of the current approach could be introduced for use in hard-real-time systems, including systems where one is controlling a system with feedback coupling and there is a need for predictive algorithms.
The heart of the Cycle-free approach is a set of restrictions, i.e. things that one should not do. This is analogous to the situation when structured programming was equated with “go to” free programming. One could not have made money with a patent on this idea because one could not force people to use the “go to” by claiming that those who did not use that construct were in violation of a patent. The implications are that, however good the ideas may be, any investors who want to buy these ideas must think hard about how to package the idea so that one can earn with it.
The Willie Kernel is a mechanism that one can control, sell, and develop further. By itself, that is without good instruction or instructional documentation, it can be misused. If it is misused, and poor software is the result of that effort, it will quickly gain a reputation for not being worth very much and it then won't be worth very much. A few users saying, “We used this and it did not help” will start the industry looking elsewhere for solutions to its problems. This means that a good book, manuals and exact documentation of the package, should be part of the package. Moreover, one might consider, requiring a Simtrol review or certification before a product could be identified by the label “Cycle-free” or “Willie inside”. Cycle-free and Willie are intended to be methods of developing high quality products and you do not want low quality products circulating carrying the name.
The current W++ implementation using a C++ pre-processor base is also questionable because it would be quite easy to create a situation in which the methods and kernel did not appear to work properly. This was a good short- term tactic for exploring the ideas and demonstrating their value, but the lack of “protection” makes it a poor way to package the product. Extensions of (or relaxations of) Cycle-free If investments are to be made in this method and tool then there are some areas that are worth considering for the future.
The developers of the Cycle-free methods and supporting tools make some strong claims for their methods. Most of these claims are based on experience and justified, but there are a few overstatements made or implied in the literature sent to me and posted on the web. Such statements should be eliminated both to avoid potential liability and to avoid losing the interest of skeptics who will reject anything that claims to be a miracle-drug. Below are some items that caught my attention.
Anything that would make even a small improvement in programming practice for even a limited class of programs is obviously of great value. I see the Cycle-free and Willie ideas as capable of making a major improvement in programming practice for an important large class programs. It does not have to work miracles to be useful or a good investment. I believe that if the developers are careful to state exactly what the method can and cannot do, if they provide good instructional material, an inspection/approval service, and a solid (hard to defeat) implementation, these ideas can be a very valuable investment.