State machine design is a technique of viewing a mechanical, electrical, or software system as a process which is driven between quiescent "states" (in which it waits for something to happen) by external events, or "stimuli."
State machine design is predicated upon the existence of a "process." In classic state machine designs for software systems, "process" has a specific connotation expressed by various operating systems as "process", "task," "program execution" or some similar term. It means simply that the sequence of instructions comprising the software system have been assigned the resources necessary for existence (such as memory allocation, stack allocation, process identification, etc.), execution (priority, process control block, etc.), and access to operating system services (file descriptors, message buffers, etc.). With these resources the software system can arrange to enter a quiescent state, to be scheduled upon the occurrence of some stimulus, and to maintain its existence over the duration of events.
In contrast to processes, interrupt handlers are executed at the request of the associated devices. The device itself generates a hardware signal which literally interrupts the computer and causes control to be transferred to the interrupt handler. The interrupt handler has the responsibility of determining the cause of the interrupt, of performing appropriate action to service the interrupt, and then restoring control to the interrupted process. Traditionally, interrupt handlers are viewed as being small, short-lived, and repeatedly invoked at random intervals. In fact, many operating systems place severe restrictions on the amount of time which an interrupt handler may consume in the servicing of an interrupt and permit the handler almost no access to operating system services.
Compared to interrupt handlers, processes tend to be long-lived, large, and to have only a single invocation. They have been favored for device supervision because they are single threaded, have a more permanent existence, have access to system resources (particularly memory and stack space), and have full access to operating system services.
To the very limited extent that state machine designs have been used for the supervision of devices attached to a computer, the approach has been to write a simple interrupt handler which arranges to signal events to some program which actually provides supervision for the device control. This scheme has some immediate advantages:
1) the interrupt handler provides little device control, an advantage since it is invoked asynchronously by the device itself; PA1 2) the program providing the supervision runs as a process with full access to operating system services and resources; and PA1 3) the process provides supervision, an advantage since it generally possesses a more well defined execution sequence. PA1 1) As device controllers become more sophisticated: PA1 2) In many instances this scheme is too slow to respond to critical events; and PA1 3) It is difficult for the supervising process to obtain pertinent status information since it is scheduled sometime after the interrupt occurs. PA1 1) the definition of a "state;" PA1 2) a mechanism for initializing the state machine; PA1 3) the association of each stimulus with that portion of the software system designated to handle it for current state; PA1 4) a mechanism for progression from one state to another; PA1 5) the definition of a "nested state;" PA1 6) a mechanism for calling a nested state; and PA1 7) a mechanism for returning from a nested state to the calling state.
However, the many problems with this traditional approach are:
a) an increasing amount of information needs to be communicated between the interrupt handler and the supervising process; PA2 b) an increasing amount of CPU overhead is consumed by the scheduling of the supervising process; and PA2 c) control of multiple devices by a single device controller is becoming prolific resulting in another layer of supervising processes.
Thus, there is a need in the art for such a system which responds in real time to stimuli and asynchronous demands. This system must be capable of functioning without the benefit of those resources normally provided by an operating system and must be reduced to practice in a manner consistent with those constraints placed on interrupt handlers by operating systems, including constraints on computer CPU time and stack memory usage.
There is a further need in the art for a system which will allow for computer control of several processes, all working concurrently, and all requiring constant monitoring and corrections.
There is a still further need in the art for a system of controlling external systems, such as motors, which must be coordinated but which operate independently from each other and which require control monitoring.