|
Concurrent C is designed to extend C for parallel programming. Here, the designers of the language use it to write a real-time tty controller.
November 01, 1989
URL:http://www.drdobbs.com/cpp/concurrent-c-for-real-time-programming/184408233
Copyright © 1989, Dr. Dobb's Journal
Copyright © 1989, Dr. Dobb's Journal
Narain and William are the architects of Concurrent C and authors of The Concurrent C Programming Language (Silicon Press). They can be reached at AT&T Bell Labs, 600 Mountain Ave., Murray Hill, NJ 07974.
Concurrent C is an upward-compatible extension of C that provides parallel programming facilities with implementations available for several versions of the Unix system (that is, System V and BSD 4.2) on a variety of computers. Concurrent C has also been implemented on different kinds of multiprocessors such as a number of independent computers connected by a local area network (Ethernet).
A Concurrent C program is structured as a set of processes that interact with each other by sending messages. Messages are sent to and replies received from another process by calling transactions associated with the process. To avoid confusion with "database transactions," we'll use the term "transaction" to mean a Concurrent C process interaction. Transactions are like remote procedure calls with one important difference -- the receiving process can schedule acceptance of the calls. Transactions can be synchronous or asynchronous. Synchronous transactions implement the extended rendezvous concept (as in the Ada language): Two processes interact by first synchronizing, then exchanging information (bidirectional information transfer), and finally by continuing their individual activities. A process calling a synchronous transaction is forced to wait (unless it times out) until the called process accepts the transaction and performs the requested service. With asynchronous transactions, the caller does not wait for the called process to accept the transaction; instead the caller continues with other activities after issuing the transaction call. Information transfer in asynchronous transactions is unidirectional, from the calling process to the called process. Concurrent C, as a compile-time option, also works with C++.
Our objectives in enhancing C with concurrent programming facilities were to provide a tool for writing programs that run on genuinely parallel hardware and to provide a test bed for experimenting with distributed programming facilities. In this article, we'll describe Concurrent C and then use it to write a nontrivial real-time program (a tty controller). We assume that you are familiar with the C language, so we only describe the Concurrent C extensions to C.
Concurrent C extends C for parallel programming by providing facilities for specifying process types; creating processes; specifying the processor on which a process is to run; specifying, querying, and changing process priorities; synchronous transactions; asynchronous transactions; delays and time-outs; interrupt handling; waiting for a set of events such as transactions; accepting transactions in a user-specified order; process abortion; and collective termination.
To give you a flavor of Concurrent C, we'll show you the definition of a process that buffers messages (characters in this example). Producer processes (pi) call the buffer process to put messages in the buffer, and consumer processes (ci) call it to get messages from the buffer, as shown in Figure 1. A process definition in Concurrent C consists of a specification (or type) and a body. Example 1 shows the specification of the buffer process.
process spec buffer(int max)
{
trans void put (int c);
trans int get ();
};
The buffer process has two synchronous transactions: put and get. Characters are put into the buffer by calling put; if the buffer is full, a call to put will not be accepted. Transaction get is used to take characters from the buffer; if the buffer is empty, a call to get will not be accepted until a character is available.
The direction of information transfer is not dependent on which process makes the transaction call. In this example, the process calling transaction put sends characters to the buffer process while the process calling get gets characters from the buffer process.
Transactions put and get of the buffer process are synchronous in that the calling processes are blocked until the transaction call is accepted and executed. Transaction calls can be declared to be asynchronous (by using the keyword async instead of the transaction result type), in which case the calling process is not blocked. Asynchronous transaction calls do not return a result.
Synchronous transaction calls can be used for bidirectional information transfer: Arguments are used to send information to the called process and the transaction result is used to return information to the calling process. Synchronous transaction calls can also be used to synchronize execution.
The buffer process type can be used just like the predefined types to declare variables, function types, and so on; for instance, process buffer buf, b[10]. Example 2 shows the body of the buffer process that implements a circular buffer.
process body buffer (max)
{
int *buf; /*circular buffer of size max*/
int n = 0; /*number of chars in buffer*/
int in = 0; /*index of next empty slot*/
int out = 0; /*index of next character*/
char *malloc();
buf = (int*) malloc (max*sizeof (int));
for (;;)
select {
(n < max):
accept put (c)
buf [in] = c;
in = (in +1) % max;
n++;
or
(n > 0):
accept get()
treturn buf[out];
out = (out + 1) % max;
n--;
}
}
The buffer process allocates space for the buffer and then repeatedly executes a select statement that is used to wait for a set of alternative events. This statement has two alternatives, separated by the keyword or. Each alternative starts with a Boolean test and is followed by an accept statement. The Boolean test is called a "guard" and gives the conditions under which that alternative can be chosen. For example, the guard for the first alternative is true whenever the buffer process has space to store a character, and the guard for the second alternative is "true" whenever the buffer process has characters to give out. Transaction calls are accepted using the accept statement.
When the select statement is executed, it selects one alternative, executes all statements in that alternative, and skips the other alternative. For an accept alternative to be selected, its guard must be true and there must be a pending transaction call that satisfies the leading accept statement. If both alternatives are eligible, the select statement picks one randomly. If both guards are true but no transaction calls are waiting, the select statement waits for the first call of either type.
Initially the buffer is empty and only the first guard is true. Consequently, the select statement waits for a put transaction call to arrive and then executes the first alternative. The buffer process then loops back and executes the select statement again. Now both guards are true, so it waits for the next put or get transaction call to arrive.
Processes are created (instantiated) using the create operator; for example, buf = create buffer(1024). The create operator returns the process id of the newly created process. When creating a process, the processor on which the process is to run and the process priority can also be specified.
Processes communicate by means of transaction calls that have the form process-id.transaction-name(arguments). For example, character 'a' is sent to the buffer process with the transaction call buf.put('a') and is retrieved from the buffer process with the call c = buf.get( ). Transaction calls behave like function calls. For example, get returns the character taken from the buffer as a value of type char. In general, a transaction call is allowed wherever a function call is allowed.
Transaction calls can also be made using transaction pointers that encapsulate the process id and the transaction name as illustrated by the program segment in Example 3.
char c;
trans void (*tp) (int);
...
tp = buf.put;
...
(*tp) ('a');
Transaction pointers are similar to function pointers except that their declarations are prefixed by the keyword trans. Because a transaction pointer does not include the process type, a transaction pointer can refer to transactions of different process types, provided these transactions have the same parameter and return-value types.
Concurrent C also supports timed (synchronous) transaction calls that allow the calling p ocess to withdraw the transaction call if it is not accepted within the specified period.
As discussed earlier, transaction calls are accepted with the accept statement. By default, these calls are accepted in FIFO order. The order in which these calls are accepted can be changed with the by clause. The suchthat clause allows the selection of the transaction call to be based on the arguments of the transaction and on the state of the called process.
In general, a select statement can have an arbitrary number of alternatives, not just two alternatives as shown in the buffer example. The alternatives of the select statement can be used for accepting transaction calls, timing out, collective termination of all the processes leading to program termination, or execution of arbitrary Concurrent C statements. For any execution of the select statement, Boolean expressions can be used to mask out one or more of the alternatives.
Concurrent C allows transactions to be accepted in a user-specified order; thus the user can accept urgent transaction calls first. Specifically, transaction call acceptance can be based on the transaction name, the order in which transaction calls are received, transaction arguments, and the state of the called process.
Asynchronous message passing provides maximum flexibility because processes can compute and perform message sends and receives in parallel in any way they want. A process sending a message is not blocked until the receiver gets around to accepting the message; this allows the sender to attend to other, possibly critical, events. Asynchronous message passing is especially important in situations where the inter-process communication time is high (as in case of multiprocessors). Asynchronous message passing also allows pipelining of multiple messages from the same process and allows the receiving process to accept the messages in the most appropriate order.
Concurrent C provides facilities for specifying, querying, and changing process priorities. Process priorities are specified when creating a process, but the priority can be changed at any time. Processes that need to respond quickly to events such as interrupts, which need immediate attention, are given high priorities.
Concurrent C provides facilities for timed synchronous transaction calls. This allows a process to withdraw a transaction call if it has not been accepted within the specified period. A process can also time-out if a transaction call does not arrive within a specified period. Time-outs prevent a process from being blocked for an unduly long period.
An important aspect of real-time programming is interrupt handling. The implementation-dependent function c_associate is used to indicate that the specified interrupt should be converted to a call to the specified transaction. To avoid losing interrupts, it is important that they (the associated transactions) are handled quickly. Delay in handling interrupts can occur because of the overhead in converting the interrupt to a transaction call, the delay in scheduling the driver process, and the delay in accepting the call.
These items are implementation- and application-dependent. In many cases, by giving the interrupt handling process a high priority and designing this process to give preference to accepting interrupt transactions, interrupts can be handled within real-time constraints.
Suppose that you are writing the software for an embedded system -- one that runs on a dedicated microprocessor. Examples of embedded systems are an industrial process controller, a robot controller, or the control program for a VCR. Let's suppose a display terminal is connected to your system, and occasionally you want to write messages to that display and wait for the user to type a reply. Your program runs on a bare machine -- there is no operating system, so you have to write all the software for controlling the display.
First we'll give a simplified description of the device (alas, real devices are not this simple, but if you follow this example, you should have no trouble with real hardware). The device interface consists of two 8-bit registers, the input and output character buffers, and two flag bits, input-ready and output-ready. These are in the processor's memory and can be accessed like any other memory locations. Whenever the output-ready bit is on, the program can write a character into the output character register. The hardware then turns the output-ready bit off and sends the character to the display. When the character has been sent, the hardware turns the output-ready bit back on, and the software can write another character. At 9600 baud, it takes about 1 millisecond to output a character; at 1200 baud, it takes about 8.3 milliseconds. When the user types a character on the keyboard, the hardware places that character in the input character register and turns on the input-ready bit. The program can then read the character from the register. When that happens, the hardware turns off the input-ready bit until the user types the next character. Once the user has typed a character, our program must read that character from the input register before the user types another character; if not, the character will be lost.
The hardware also generates an input-ready interrupt when it turns the input-ready bit on, and an output-ready interrupt when it turns the output-ready bit on.
Note that the terminal is really two independent devices: A display for output and a keyboard for input. When the user types a character, the hardware does not automatically display that character on the screen. Instead, our software must "echo" that character to the display. Furthermore, most display devices have separate carriage return and line feed operations; when the user types Return, our software should send a carriage return and a line feed to the display. We would also like to give the user a few creature comforts: Backspace should erase the previous character, Ctrl-C (for example) should kill the line that the user has typed, Ctrl-S should stop output so the user can read the display, and Ctrl-Q should restart output.
The simple way to output characters to the display is to repeatedly test the output-ready bit until it's on, write the character to the output register, and repeat until all the characters are written. This is called "wait-loop" I/O. The disadvantage is that the system cannot do anything else until the output is complete. Sometimes this is acceptable, but usually it isn't. And even if wait-loop I/O is acceptable for output, it probably will not be for input -- the user types too slowly!
We need a solution that allows input from the keyboard and output to the display to overlap with other processing -- we need concurrent programming. The solution is to use several processes that form a subsystem of our program and provide display input and output services to the other processes in our program. For historical reasons, we'll call these processes the "TTY driver" subsystem.
Figure 2 illustrates the interaction between the processes. Characters typed by the user flow down on the left from the keyboard hardware to the ttyInput process, where they are taken by other processes in our program. Characters to be displayed flow up on the right from other processes to the ttyOutput process and then to the display hardware. Process ttyOutput handles output to the display, and process ttyInput is the input buffer process. These processes form the "client interface" to the TTY subsystem, while other processes ("clients") in the program call put of ttyOutput to send characters to the display, and call get of ttyInput to read characters typed on the keyboard. Processes ttyLine and ttyReader are internal processes (they interact only with other processes of the TTY subsystem) and will be described later. The specification of the TTY subsystem processes is shown in Listing One (page 100).
Characters are output by calling transaction put of ttyOutput; its arguments are the number of characters and a pointer to the start of the string. Transaction put queues the characters for output; the transaction returns before the characters are sent to the display. Transaction ready is called when an output-ready interrupt occurs, stop temporarily stops the output to the display, and start restarts the output. Process ttyOutput accepts put transaction calls even when the output is stopped; the characters are queued until output is resumed.
We require the processes that call transaction put to end a line with a carriage return and line-feed characters; this simplifies the ttyOutput process.
Process ttyInput is the input buffer process. The characters in this buffer have been "cooked:" They have been echoed to the display, backspace and line-kill processing have been performed, and so on. If characters are available in the buffer, transaction get returns the next character. If the buffer is empty and the argument is 1, then get waits for a character to arrive. If the argument is 0, then get returns -1 immediately. Thus get(0) is non-blocking. Transaction put inserts a character into the input buffer.
Any number of processes can output characters at the same time. Process ttyOutput guarantees that the characters written by one put transaction call will be printed together on the display. So if several processes output data at the same time, as long as each put transaction sends one line, the lines will be interleaved in an arbitrary fashion, but the characters in each line will stay together. If several processes try to get characters from ttyInput at the same time, they will get characters on a first-come, first-served basis. This is probably not what you want. We assume that the processes cooperate among themselves to ensure that only one process tries to read characters at a time -- usually this occurs naturally.
Process ttyReader is a simple buffer manager; it takes characters from the hardware input register as soon as the user types them, and saves them in a buffer. Transaction ready of this process is called when an input-ready interrupt occurs, and process ttyLine calls get to get characters from the buffer. The process ttyLine has no transactions; it gets characters from ttyReader, echoes them to ttyOutput, handles backspace and line-kills, and so on. When ttyLine gets a full line, it sends the characters in that line to the ttyInput process.
Function ttyReply (see Listing Two, page 100) illustrates how to use these processes. It first prints the msg argument on the display and then waits for the user to type a reply line, which the function saves in the reply argument. If the user does not type a reply within 30 seconds, the function prints a nasty message and starts over. This function uses the timed-transaction call
within 30 ? ttyIn.get(1) : -1
If the ttyIn process accepts the get transaction call within 30 seconds, the value of this expression is the value returned by the process. If the process does not accept the get transaction call, then the call is automatically withdrawn, the second expression (-1) is evaluated, and its value becomes that of the expression. So if the user types a character within 30 seconds, the function breaks out of the loop and reads the rest of the line. If not, the function prints a nasty message and repeats.
Function ttyInit (Listing Three, page 100) creates the TTY subsystem processes and saves their ids in global variables. Normally, main will call ttyInit when the program starts. Notice that we have specified priorities for some of the processes. If no priority is specified, a process is created with priority 0. Process ttyOutput is created with priority 1, so that when it is ready -- that is, when the display is ready for a character -- the ttyOutput process will be scheduled before the other processes. Process ttyReader is given priority 2 because it is even more important that we take a character from the input register as fast as possible.
Function c_associate arranges to call a transaction when an interrupt occurs. The first argument is a transaction pointer specifying the process and transaction to be called. The second argument specifies the interrupt. Listing Four, page 100, gives some definitions that are common to all of the processes in the TTY subsystem.
Process ttyReader (Listing Five, page 100) is a variant of the buffer manager in Example 2. It loops forever, waiting for either a ready or a get transaction. Transaction get takes a character from the buffer and returns it, just as in the buffer manager. Transaction ready is automatically called when the hardware generates an input-ready interrupt. ttyReader then calls the uartGetChar function (the hardware interface to the device is often called a Universal Asynchronous Receiver/Transmitter or UART) to get a character from the input register. If it is a start or stop character, the process calls the appropriate transaction of the ttyOutput process. Otherwise, if there is space in the buffer, the process saves the character; if not, it discards the character.
Note that when the buffer is full, we discard characters rather than not accepting ready transactions. We do this so that we can always accept a start character. Suppose that the user types a stop character and then continues typing. The ttyOutput process will eventually fill up its buffer and will not accept put transactions until output is restarted. Because ttyLine calls put to print the characters entered at the keyboard, ttyLine will eventually stop until output is restarted. Because ttyLine is the only process that takes characters from the ttyReader process' buffer, the ttyReader buffer will eventually fill up. At that point the system will be frozen until the user types a "start" character. If ttyReader stops accepting characters when its buffer is full, then the user could never type a start character, and the system would be deadlocked. That is why ttyReader always accepts characters typed by the user, even if it has to discard them.
Process ttyLine (Listing Six, page 100) maintains a buffer containing the line that the user is currently typing. ttyLine repeatedly gets a character from the ttyReader process, handles that character, and if the line is complete, sends the line to the ttyInput process and clears the buffer. For example, when given an "erase" character (backspace), the process outputs a backspace, blank, and backspace to erase the last character on the display, and then erases the last character in the line buffer.
The input processing is not sophisticated. For example, in many display drivers, a special character, such as backslash (\), indicates that the next character is to be treated as a regular character. ttyLine does not do that, but it would be relatively easy to add it. Adding this feature is a sequential programming problem, not a concurrent programming one. A concurrent programming language such as Concurrent C lets you turn a concurrent program problem into a set of sequential programming problems -- namely the processes -- that you can then solve independently.
Process ttyInput (Listing Seven, page 100) manages the input buffer. It is almost identical to the buffer process in Example 2. The only addition is a second accept statement for the get transaction. The guards on those two accept statements are mutually exclusive: The first guard is true only if the buffer has characters, the second is true only if the buffer is empty. The second accept statement has a suchthat clause that Concurrent C evaluates for each pending transaction call. If the expression is true (non zero), Concurrent C accepts that call; otherwise, Concurrent C holds the transaction call so that it can be accepted later. Thus if the buffer has characters, the process accepts a get transaction regardless of the value of the argument. When the buffer is empty, the process only accepts get transactions whose arguments are 0 -- that is, the non-locking get requests. Therefore ttyInput immediately accepts any get(0) transaction call; if the buffer has a character, the process returns it; otherwise, ttyInput returns -1. On the other hand, a get(1) call will only be accepted when the buffer has a character.
Process ttyOutput (Listing Eight, page 100) manages the output buffer. It repeatedly waits for one of four possible transaction calls and sends a character to the display if the display is ready, output has not been stopped, and there is a character in the buffer. Transaction ready is called when the device generates an output-ready interrupt. Function uartPutChar writes a character to the output register. Note how we use a suchthat clause with the put transaction to accept the call only if there is enough space in the buffer. Also note that the process accepts put calls even when output is stopped, as long as there is space in the buffer.
At press time, AT&T is planning to make Concurrent C a product that will be available in the near future. The reader interested in Concurrent C can call 1-800-828-UNIX to check on the availability of Concurrent C.
ANSI C. Draft Proposed American National Standard for Information Systems -- Programming Language C. 1988.
Cox, I.J. and N.H. Gehani. "Concurrent C and Robotics." 1987 IEEE Conference on Robotics and Automation, Raleigh, NC, 1987.
Dijkstra, E. W. "Cooperating Sequential Processes." In Programming Languages, edited by F. Genuys. Academic Press, San Diego, Calif., 1968.
Gehani, N.H. C: An Advanced Introduction (ANSI C Edition). Computer Science Press, Rockville, Maryland, 1988.
Gehani, N.H. 1988. "Message Passing: Synchronous vs. Asynchronous." Submitted for Publication.
Gehani, N.H. and W.D. Roome. "Rendezvous Facilities: Concurrent C and the Ada Language," IEEE Transactions on Software Engineering, vol. 14, no. 11, (November), pp. 1546-1553, 1988.
Gehani, N.H. and W.D. Roome. "Concurrent C++: Concurrent Programming With Class(es)." Software -- Practice & Experience, vol. 18, no. 12, pp. 1157-1177, 1988.
Gehani, N.H. and W.D. Roome. Concurrent C. Silicon Press, Summit, N.J., 1989.
Hoare, C.A.R. "Communicating Sequential Processes." CACM, vol. 21, no. 8 (August), pp. 666-677, 1978.
Kernighan, B.W. and D.M. Ritchie. The C Programming Language. Prentice-Hall, Englewood Cliffs, N.J., 1978.
Roome, W.D. The CTK: An Efficient Multi-Processor Kernel. AT&T Bell Laboratories, 1986.
Stroustrup, B. The C++ Programming Language. Addison Wesley, Reading, Mass., 1986.
_CONCURRENT C FOR REAL-TIME PROGRAMMING_ by N.H. Gehani and W.D. Roome
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.
process spec ttyOutput()
{
trans void put(int nc, char *pc);
trans async ready(), start(), stop();
};
process spec ttyInput()
{
trans void put(char c);
trans int get(int wait);
};
process spec ttyReader()
{
trans async ready();
trans char get();
};
process spec ttyLine();
process ttyInput ttyIn;
process ttyOutput ttyOut;
process ttyReader ttyRdr;
[LISTING TWO]
#include "concurrentc.h"
#include "tty.h"
void ttyReply(msg, reply)
char *msg, *reply;
{
int c;
char *nasty = "\r\nWAKE UP!\r\n";
while (1) {
ttyOut.put(strlen(msg), msg);
c = within 30 ? ttyIn.get(1) : -1;
if (c != -1)
break;
ttyOut.put(strlen(nasty), nasty);
}
while (c != '\n') {
*reply++ = c;
c = ttyIn.get(1);
}
*reply = '\0';
}
[LISTING THREE]
#include "concurrentc.h"
#include "tty.h"
void ttyInit()
{
ttyOut = create ttyOutput() priority(1);
c_associate(ttyOut.ready, 1/*DUM*//*PSoutput-ready-interruptPS*/);
ttyRdr = create ttyReader() priority(2);
c_associate(ttyRdr.ready, 2/*DUM*//*PSinput-ready-interruptPS*/);
ttyIn = create ttyInput();
create ttyLine();
}
[LISTING FOUR]
#define M_RdrBuff 2048
#define M_OutBuff 2048
#define M_InBuff 1024
#define M_LineLen 1024
#define StopChar 0x13 /* ctl-S */
#define StartChar 0x11 /* ctl-Q */
#define EraseChar '\b' /* backspace */
#define KillChar 0x03 /* ctl-C */
[LISTING FIVE]
#include "concurrentc.h"
#include "tty.h"
#include "defs.h"
process body ttyReader()
{
int n = 0, in = 0, out = 0;
char c, buff[M_RdrBuff];
while (1) {
select {
accept ready();
c = uartGetChar();
if (c == StartChar) {
ttyOut.start();
} else if (c == StopChar) {
ttyOut.stop();
} else if (n < M_RdrBuff) {
buff[in] = c;
in = (in + 1) % M_RdrBuff;
n++;
}
or (n > 0):
accept get()
treturn buff[out];
out = (out + 1) % M_RdrBuff;
n--;
}
}
}
[LISTING SIX]
#include "concurrentc.h"
#include "tty.h"
#include "defs.h"
process body ttyLine()
{
int n = 0, putline = 0, i;
char c, buff[M_LineLen];
while (1) {
switch (c = ttyRdr.get()) {
case EraseChar:
ttyOut.put(3, "\b \b");
if (n > 0)
--n;
break;
case KillChar:
if (n > 0)
ttyOut.put(2, "\r\n");
n = 0;
break;
case '\r':
case '\n':
ttyOut.put(2, "\r\n");
buff[n++] = '\n';
putline = 1;
break;
default:
ttyOut.put(1, &c);
buff[n++] = c;
if (n >= M_LineLen)
putline = 1;
break;
}
if (putline) {
for (i = 0; i < n; i++)
ttyIn.put(buff[i]);
putline = n = 0;
}
}
}
[LISTING SEVEN]
#include "concurrentc.h"
#include "tty.h"
#include "defs.h"
process body ttyInput()
{
int n = 0, in = 0, out = 0;
char buff[M_InBuff];
while (1) {
select {
(n < M_InBuff):
accept put(c)
buff[in] = c;
in = (in + 1) % M_RdrBuff;
n++;
or (n > 0):
accept get(wait)
treturn buff[out];
out = (out + 1) % M_RdrBuff;
n--;
or (n == 0):
accept get(wait) suchthat (!wait)
treturn -1;
}
}
}
[LISTING EIGHT]
#include "concurrentc.h"
#include "tty.h"
#include "defs.h"
process body ttyOutput()
{
int n = 0, in = 0, out = 0;
int running = 1, ttyrdy = 1, i;
char buff[M_OutBuff];
while (1) {
select {
accept start()
running = 1;
or accept stop()
running = 0;
or accept ready()
ttyrdy = 1;
or accept put(nc, pc) suchthat (n+nc <= M_OutBuff) {
for (i = 0; i < nc; i++) {
buff[in] = pc[i];
in = (in + 1) % M_OutBuff;
}
n += nc;
}
}
if (ttyrdy && running && n > 0) {
uartPutChar(buff[out]);
out = (out + 1) % M_OutBuff;
n--;
ttyrdy = 0;
}
}
}