David Fugelso has a B.S. in computer science from the University of New Mexico and has seven years of experience in software engineering. Mike Michnovicz has an M.S. in electrical engineering from the University of New Mexico and has seven years of experience in systems integration and embedded systems. The authors may be reached at Titan/Spectron P.O. Box 9254, Albuquerque NM, 87119-9254 or via e-mail on Compuserve at 72460,741.
Titan/Spectron has developed a real-time system called DIAL, for DIfferential Absorption Lidar. It is used for the remote detection of hydrocarbon gasses such as methane, ethane, and propane. The DIAL technique measures the atmospheric absorption of a laser beam to sense the presence of gasses. It does so by measuring and comparing the return signals of laser pulses at two different wavelengths to locate specific gasses. This system makes six lidar measurements at a continuous rate of 10Hz. The program collects lidar measurements, writes them to disk, performs the DIAL calculations, and displays the results. The first two of these functions have real-time requirements, but the calculation and display function does not since data is saved and can be processed later.
DIAL is based on a real-time UNIX system that uses System V inter-process communication facilities for synchronizing concurrent tasks and sharing data. The algorithm has one producer and two consumer tasks. It uses a bounded buffer technique implemented with System V message queues and shared memory.
The system acquires data from six digitizer channels, each sampling at 20 million samples per second over a period of 20 microseconds. The digitizer has a resolution of 12 bits. Two bytes store and transfer each sample, so the host computer must read, write, and process 4,800 bytes (400 x 2 x 6) per pulse. The 4,800 bytes of data collected from the six lidar measurements is referred to as a frame. At 10Hz, the data acquisition system must have a minimum continuous throughput of 48 Kbytes/sec.
The host machine for this system is a 386-based computer with an AT bus running LynxOS, a real-time UNIX operating system, from Lynx Real-Time Systems. (See the sidebar on real-time operating systems.) The system includes a 370Mb hard drive connected to the AT via a SCSI interface. It transfers from the digitizer to the host via an IEEE-488 bus (also known as a GPIB). The system's IEEE- 488 controller uses direct memory access (DMA) to place data into host memory.
Algorithm Description
Data acquisition work is split among three tasks: one producer task and two consumer tasks. A fourth task, the task synchronization module (TSM), synchronizes the activities of the working tasks. The producer task reads data over the IEEE-488 from the digitizer. The first consumer task writes data to disk; the second performs the DIAL calculation and graphically displays the data. The read task is the most critical; if it misses a trigger, digitizer data will be lost. The write task is less critical than the read task since frame buffers can be written at any time; however, the write task cannot get systematically behind. The graphics task, on the other hand, may lag behind real-time and is allowed to miss data.After receiving an external trigger event, the TSM task initiates the data acquisition process by locating an unused buffer and sending the buffer to the producer task. The producer task reads the data and sends the buffer to the first consumer task, which writes the data to disk and sends the buffer to the second consumer task. When that task is finished, it releases the buffer.
Tasks pass buffers via four System V message queues: the available queue, the read queue, the write queue, and the graph queue. The actual buffers are not copied among the tasks. Rather, the tasks pass messages containing indexes to buffers located in shared memory. The TSM task creates these messages, each containing an index or "key" for a buffer, and places them in the proper queue. An index can be thought of as a key because each message is unique and corresponds to exactly one buffer. This message queue mechanism provides mutual exclusion among accesses to the shared memory and also provides task synchronization.
Implementation
The short program in Listing 1 starts the four data acquisition tasks. In the DIAL Lidar program, this task contains the user interface. The listing illustrates how the UNIX fork() call starts separate tasks. fork() makes an identical copy of the calling program with a new process ID. fork() returns a zero to the new task that is the child process, and returns the process ID of the child to the parent process.Listing 2 is the header file included by the four data acquisition tasks. The header file defines a semaphore, message queue, shared memory indexes (keys), the message structure, frame buffer size, number of buffers, the priorities of the tasks, and other miscellaneous values. The keys for semaphores, message queues, and shared memory allow the separate tasks to access the same system resources.
The message structure contains two elements. The operating system requires and uses a message type field to differentiate between types of messages. Because all of the messages in this program are similar, type is not used. The second element is the frame buffer index or key to a contiguous segment of shared memory.
Tasks run at different priorities. The TSM task has the highest priority since it must execute when an external event arrives. The read task has the second highest priority since the data must be acquired in a specific time frame. The write task has the next highest priority since the write to disk is critical but finite delays are acceptable. The lowest priority is assigned to the graph task. It essentially uses whatever CPU time is left over from the other tasks.
Listing 3 is the TSM task, lidar_acq.c. As noted earlier, the TSM task synchronizes the activities of the other tasks. After setting its own priority and performing some initialization, the task creates unique messages for each frame buffer and places each message in the available queue.
The TSM task then waits for the other tasks to finish loading and initializing. This is accomplished by three waits for the "alive" semaphore. These waits are necessary because the TSM task starts the external data acquisition process. If the other tasks are not ready, the acquisition process will break down. LynxOS provides an alternative form of the System V implementation of the semaphore, which the program uses here. sem_get() works similar to the System V semget() but uses a string key instead of an integer key. sem_signal() and sem_wait() replace the complicated System V function semop().
Once the other processes have checked in, the TSM task writes to the trigger device the number of 400 micro-second cycles between triggers (count) and the number of triggers to generate (int_count). The trigger device is a custom device with an external clock developed to handle the intricate triggering of the lasers. (See the sidebar on developing device drivers for real-time UNIX.)
The task then waits for the external trigger by reading the trigger "file." After receiving a trigger signal, the TSM task looks for a free buffer on the available queue through the msgrcv() system call. By making the call with the flag IPC_NOWAIT, the program instructs msgrcv() to return immediately whether a message is in the queue or not. If a buffer is available, the program places it into the read queue. Otherwise, the TSM task must free a buffer from another task. Since the calculate and graph process is not a critical part of the system, the program places all buffers in the graph message queue also in the available queue (using msgrcv() with the IPC_NOWAIT flag in a loop until the graph queue is empty). If still no buffers are available, the program has encountered a fatal error. (It has missed data.)
After receiving all external events, the TSM task terminates the data acquisition session by placing a quit message on the read queue. The task then waits for messages for all of the frame buffers to be placed on the available queue, followed by the quit message. If then deletes all the semaphores, message queues, and shared memory resources. This allows the work tasks to complete any remaining processing.
Listing 4 presents the producer task, lidar_read.c. This task synchronizes activities through the system call msgrcv() acting on the read message queue. It sends the parameter NOFLAGS to the routine, causing the task to pause until a message is placed in the read queue. Once the system has acquired data and placed it in shared memory, the task places a message in the write message queue.
Not shown here is the code that initializes, reads, and closes the IEEE-488 device. It was omitted partly to save space in this presentation. Digitizer device commands also vary among manufacturers. The code is somewhat messy because manufacturers support several types of digitizers.
Listing 5 shows the first consumer task, lidar_write.c. The task's structure is similar to that of the read task. The task waits for a message to be placed in the write queue. After receiving the message, the task writes a frame buffer and places the message in the graph message queue.
LynxOS provides a system service that allows the use of contiguous disk files. Using contiguous disk files speeds up I/O because the disk head does not have to move as much. Moreover, the system knows to bypass the disk cache. The program creates such a file with the mkcontig() system call, which requires a maximum file lenghth parameter. The program then opens the file and access it using standard system calls. A contiguous file imposes one additional constraint - data must be written in 512-byte chunks. Although each frame contains only 4,800 bytes, the program thus writes 5,120 bytes (ten 512-byte blocks) to disk. In the actual application, this extra 320 bytes is used to store ancillary information about each frame, such as pulse energies and absorption coefficients.
Listing 6 shows the second consumer, lidar_graph.c. Again, the code is structured the same as the two preceding tasks. When the task is finished processing a buffer, it places the buffer on the available message queue.
The second consumer performs DIAL calculations. It can display up to six graphs using X Window library calls. For brevity, the listing omits the calculation and graphics code. In its place is a CPU delay function, which gives an example of using UNIX signals.
Performance
Running at 10Hz, the system has 100 msec to acquire the data for each pulse. Of this, the producer task takes between 20 and 40 msec (depending on the digitizer) of real time to transfer 4,800 bytes of data over the IEEE-488 bus. This time includes the time it takes the digitizer to acquire a waveform and the overhead to initiate the transfer. Since the transfer uses DMA, CPU usage is much smaller (less than 10 msec).The first consumer task completes the write to disk in 10 msec real time and uses less than 0.7 msec of CPU time. (Without the use of contiguous disk files, the write time triples.)
The second consumer task can take between 0 and 200 mseconds depending on which graphics option is selected. Some processing options cannot be performed in real time. The display will lag behind data acquisition, causing the program to periodically dump the graphics message queue, resulting in time gaps in the display data. The number of buffers allocated affects both the length of the gaps and the time between gaps. Using ten buffers and assuming a calculation and display time of 100 mseconds/buffer, you can see that the graph queue will be dumped every 5.8 seconds:
Display Time / (Total CPU time/cycle - 0.1 s) * Nbuffers * 0.1 sWhen the program dumps the graph queue, the gap length will be 900 msec, because the program removes nine frame buffers (Nbuffers - 1) from the graph queue.The other factors that have an impact system performance are the control statements, context switches, and message queue overhead. Of these, only the message queue overhead has significant impact. The time to send and receive a message is approximately 0.3 msec, so with four transfers per frame, 1.2 msec are used for synchronization.
Conclusion
I have presented a flexible and easy-to-implement solution for the producer/two consumer data acquisition problem. The LynxOS operating system provides the real-time environment and the facilities to easily develop real-time programs.
References
"Real-Time Data Acquisition," Mike Bunnel and Mitch Bunnel, Dr. Dobbs Journal, June 1989 pp. 36-44."Unix Interprocess Communication," William J. Freda, The C Users Journal, November 1990, Vol. 8 No. 11, pp. 49-61.
Concurrent Programming, Fundamental Techniques for Real-Time and Parallel Software Design, Tom Axford, Wiley & Sons, West Sussex, England.