AMAZON multi-meters discounts AMAZON oscilloscope discounts
3. Processes
3.1 Nature
Events
The atomic (indivisible) element which characterizes a process is the event. The observed behavior of any process is considered to be a discrete sequence of events. Each event is idealized to be instantaneous. It is the accomplishment of an action in response to a single command of the process specification.
The alphabet of a process is the set of all events of which it is capable. For instance, the alphabet of a Turing Machine is simply {All defined modify events, move forward, move backward, halt}.
In order to be useful, a process must possess one special event in its alphabet… succeed Passage of this event means successful termination. The equivalent for the Turing Machine is halt.
Example process
Recall that a process is the behavior pattern of an object. This consists of a sequence of events which is conditionally dependent on both its initial state and communication with its environment. A process starts, runs and then terminates.
For an example of a process, consider an economy (Fig. 8). We here adopt an extremely naïve model. A number of supplier/manufacturer/consumer chains run concurrently without communicating with each other. Each supplier inputs raw materials and then outputs goods (perhaps refined raw materials or components) to a manufacturer from whom it also inputs money. A manufacturer simply inputs from its supplier and outputs goods to its customer, from whom it also inputs money. Part of the definition of this process, not rendered explicit in the diagram, is that it cannot output money until it is first input. The customer inputs goods, for which it pays, and then outputs waste. Another omission from the diagram is any hint of how the process or any of its subordinates terminate.
The alphabet of the process includes communication events between pairs of subordinates which cause update of its internal state. Input and output events for subordinates must be synchronized to form a communication transaction internal to the parent process. The effect is then to update the state of the parent.
Traces
The actual sequence of events observed is called a trace and will end with a special succeed event if the process terminates.
An example of a process is the behavior pattern of a vending machine which outputs different kinds of chocolate bar depending on the coin input. Its internal state is the number of each kind of chocolate bar. The process (behavior pattern) may be described as a procedure such as on the left below…
REPEAT
CASE input OF input 5p 5p: output small bar output small bar 10p: output big bar input 10p UNTIL FALSE output big bar input 10p output big bar
… An example trace start for the process is shown on the right above. It is just one possibility of many.
STOP and SKIP
Some special processes may be defined which are useful to the designer who must specify and verify a process. STOP starts but never terminates. Its presence indicates a fault in the design. It is possible to reveal the presence of a STOP using transformations of the specification. Any process which has a subordinate STOP will itself never terminate.
SKIP simply succeeds and thus terminates immediately. It is most useful in the development of a process specification. Substitution of SKIP for a section of code allows the remainder to be tested independently.
Fig. 8: Naïve process model of an economy
Recursion
Processes may sometimes possess a recursive definition. This means that they may be defined in terms of themselves. A very simple example of such a definition is that of a clock whose alphabet is simply composed of a single tick event, and never terminates.
This would be formally described by…
The initial event must always be specified and is called a guard. The idea is that the process is a solution of the equation. Equations may be manipulated rather like algebra. Mutual recursion is the name given to a definition specified as the solution of a set of simultaneous equations.
Primitive processes Primitive processes are the simplest things we need consider. In the process model there are just three primitive processes (in addition to STOP and SKIP)…
• Assignment
• Input
• Output
Assignment refers to the assignment of purely local state. In the process model of software there can be no global variables and no references to non-local variables whatsoever. All resources (e.g. a database) must either be distributed or belong solely to a single process.
Just as assignment is of a variable to an expression, output is of an expression and the corresponding input is of its value into a variable. The correspondence of assignment to input and output is no coincidence and shows that all computation may be regarded as communication, as we shall see.
Construct processes
Constructs may be employed to specify a process in terms of subordinates. The possibilities are as follows…
• Sequence
• Parallel
• Selection
• Iteration
The three possible means of process selection are by…
• Guard event
• Condition
• Expression value
Qualification may be required to determine the process selected by guard since it is possible that more than one choice may exist at the instant of selection. Thus the program must specify prioritization. In the absence of prioritization the process selection will be nondeterminate.
Iteration is terminated by a condition in the usual way.
3.2 Concurrency
Synchronization
Any pair of processes running in the same window of time are said to be concurrent (Fig. 11). Of interest are those processes which interact by communication.
Consider the economy example above. The manufacturer process is unable to send money to its supplier until it has first received money from its customer. As a result the supplier must wait idle until the manufacturer is ready and the transaction may proceed. This is what is meant by synchronization.
Communication is delayed until both parties are ready.
Of course, the constraint of payment before supply may result in the supplier delaying the sending of goods until payment has been received. In other words, the supplier will not be ready for that transaction until after the other has occurred.
Fig. 9: Dining philosophers problem
Deadlock
One of the most insidious problems which can occur with the specification of concurrent systems is that of deadlock. The classic example of this is the dining philosophers problem (Fig. 9).
A number of philosophers (say three) share a common dining room. Each has his own seat and fork and is right handed. They eat nothing but spaghetti which requires two forks with which to serve a helping. Being either stupid or utterly selfish, they are incapable of assisting each other and so must each make use of the fork of another or starve to death if all dine together. The problem is that they cannot all serve themselves at the same time [8]. If they do not talk to each other and reach agreement how can they avoid starvation? Each philosopher dining may be described as a process defined by the following procedure…
1. Input fork from left-hand neighbor (input fork)
2. Pick up own fork and eat (update state)
3. Give fork to neighbor (output fork)
4. Leave (succeed)
The philosophers come and go as they please and the dining system will work except when they start together! If they all start simultaneously, no-one will be able to commandeer their own fork. They will all STOP and never succeed. This situation is an example of deadlock.
One solution is to create a new process whose task it is simply never to allow a full table at any one time. This is an example of a monitor process which permits secure access to a shared resource. Although it prevents the philosophers from deadlocking (starving), it enforces a degree of sequentially which is obviously not maximally efficient.
[8. A similar situation has been used to illustrate the difference between heaven and hell.]
The same physical scenario is present in both. In hell they starve, in heaven they eat!
3.3 Communication
Successive processes
Communication is fundamental to computation. Computation may be regarded as purely assignment and communication at all levels, from hardware upwards.
In the purely procedural model of computation, and hence pure procedural programming languages, communication is rarely formalized. No concurrency is allowed since usually only a single processor is assumed available.
Communication is reduced to that between processes which run in sequence, i.e. successive processes. The only way in which they may communicate is by means of a shared variable called a buffer. Fig. 10 shows the relationship between successive processes and the variable they share which belongs to their mutual parent process.
The situation is like that in a market when a vendor is waiting for an expected customer who is to purchase his last item of stock. If the vendor knows the customer cannot arrive until he has already sold the rest of his stock, it is obviously secure and efficient for him to leave the purchase in an agreed location for the customer to collect. This is only secure if the agreed location is not known to anyone else. Leaving the purchase is equivalent to assigning a value to a buffer at the previously declared (agreed) location. The location and the data type form the protocol for the transaction (communication event).
This form of communication is said to be asynchronous because sending and receiving take place at different times. Rather than characterize processes as successive or concurrent it is sufficient, and arguably more meaningful, to simply relate them by whether their communication is asynchronous or synchronous. Communication between successive processes is asynchronous and uses a shared variable called a buffer.
Fig. 10: Communication between successive processes
Concurrent processes
Communication between concurrent processes is a different problem.
Fig. 11 illustrates communication between concurrent processes within their time window of overlap. The input and output events of receiver and sender processes respectively are synchronized to form a single event of their mutual parent. Communication between concurrent processes is synchronous and uses a channel.
Fig. 11: Communication between parallel processes
Communication, whether synchronous or asynchronous, may be categorized by the number of senders and receivers as follows…
• One-to-one
• One-to-many (broadcast)
• Many-to-one (multiplex)
It is enough to consider the simplest case of one-to-one communication where only two processes are involved. Once this can be achieved, so can one-to-many and many-to-one communication. The same criteria of security and efficiency apply but another difficulty arises in synchronization. One or other process may not be ready. For example our market vendor may be waiting to sell without a customer wanting to buy. The result is that he is idle which indicates inefficiency. The solution is for him to busy himself with something else and suspend the process of selling. In other words, each processor must be capable of scheduling multiple processes in order to be efficient.
Synchronous communication requires something which corresponds to the part played by the buffer in asynchronous communication. The mechanism required is called a channel and must also be agreed (declared) by both parties prior to any transaction. In our market analogy the channel used for a transaction is the method of payment. The vendor may not accept credit cards in which case…no transaction! The particular channel employed and the types of value passed form the channel protocol.
Input of a value is into a variable. Clearly, it will be hard work computing any given function if all that is possible is to relocate values, although the Turing Machine demonstrates that such is possible. The output primitive must be capable of sending the value of some function of state. The arguments of this function are therefore local variables. To summarize, a processor must be capable of…
• Assignment of state to a function of state
• Input of a value to state
• Output of a function of state
Further reading
Computers may be modeled as a network of processors running processes which communicate with each other and an environment which may be modeled in the same way. The process model of computation may be applied to the lowest level of computation even unto the level of the normally-open switch.
The model very briefly introduced here originates with [Hoare 78]. A full and fascinating account is given in [Hoare 85], which the reader is strongly recommended to read.
Exercises
Question one
i Protocols may be layered one above the other. For example natural language employs rules collectively called a syntax to determine the valid structure of symbols called words in each sentence. Part of this protocol is the rule that a sentence is a stream with EOT ".". Below that protocol lies another, part of which takes the form of a dictionary defining the valid structure of symbols called characters in each word.
If both writer and reader of this guide are regarded as processes, what is the protocol used in their communication?
ii Detail any other kinds of protocol you can think of, which are used for channels of communication in the everyday world.
Question two
i Summarize the instruction set of the (human) automaton discussed in Section 2.2.
ii Suggest an implementation of this automaton in Modula-2 or other structured procedural programming language.
Question three
Show how normally-open switches may be used to implement a NAND logic gate, which has output "1" unless both inputs are "1". Use only two switches.
Question four
i Describe an example, of your own, of a process where some of the subordinate processes run concurrently. Having done that, now describe an example where all the subordinate processes run successively.
ii A process is composed of four subordinate processes, A, B, C, D. The following communication paths must exist…
• A S B (asynchronous)
• B S D (synchronous)
• C S D (asynchronous)
• C S A (synchronous)
Two processors are available, which do not share memory but which possess physical (hardware) communication channels (one input and one output channel each). How must the processes be assigned to processors?
iii Is there any possibility of deadlock?
Related Articles -- Top of Page -- Home