FIFO Management; RS-232 I/O

When I worked at Quantum we often had several summer interns. When our schedules allowed I would offer my almost one-hour class covering both of these topics. They are presented together in much the same way as I presented them while working at Quantum.

FIFO Management and RS-232 I/O are covered together. As different as these subjects are they fit together well. First we talk about FIFOs generally.

Whether expressed or implied all FIFOs have 4 pointers. Here the pointers will use the names given them in the CDC 6000/Cyber 70 series computers. A few words have been changed from my CDC 6000 days to match better with today's thinking. In particular word addresses have been replaced by byte addresses.

The four pointers are...

First First byte address of buffer
In Address within buffer where next byte goes IN to the buffer
Out Address within buffer where next byte comes OUT from the buffer
Limit The last byte address+1 of the buffer

We show a 10-byte buffer occupying the address 1200 to 1209. At first (A) the buffer is new. Both in and out are equal (the buffer empty condition) and point to first. The green shaded boxes show empty space within the buffer. After 3 bytes are put into the buffer we have the pointers set as in (B). The grey boxes indicate the location is full. Next we remove 2 bytes giving (C). Then we put 7 more bytes into the buffer giving (D). Note that the in pointer has wrapped around to the top of the buffer. Lastly we put another byte in the buffer giving (E).

Notice the X in location 1201 in column E. This is a reminder that an attempt to store another byte would make a problem. If we did this both in and out would equal 1202. But in equal out is the buffer empty condition. It's better to accept this loss of one byte than to spend several bytes for flags to save that one. Also the code dealing with FIFOs becomes simpler.

None of this is Holy Writ. On one small computer my buffer was placed at 0x1200 to 0x12FF. In and out were 16-bit words. First and limit were not present as such. I could fetch and store using *in and *out (hardware indirect addressing.) When I needed to do in++ I simply incremented the low byte of the address. 0x12FF rolled over to 0x1200 without a special test.

For starters we will have two buffers. One for sending data, the other for receiving data. Be careful. It's easy to get the two confused because for the software on the other side of the interface our send and receive become receive and send.

The general rule we will follow is to always be in a position to receive data. We will split our data receive into physical and logical halves.

We get to our receive ISR when the RS-232 hardware has a byte for us. In general all we do is *in+++ where +++ indicates an increment end around. We then do whatever it takes to make the hardware happy and exit. Is that easy or what?

Alas, we may have a problem. What if there is no room in the buffer? Putting another byte in the buffer sets it to the empty condition and we have just lost everything. Not good. But what should one do? There are two answers that have to be taken together. (1) Our receive ISR is the wrong place to fix this problem. Therefore (2) the problem must not be allowed to happen. How this is assured is an overall system consideration.

In one application I had a 1000-byte buffer. When I got down to 100 bytes left I sent an X-off to my host. A few bytes later I stopped getting data. When I had 200 bytes of free space I sent an X-on and data flow resumed. Yet on other applications I just closed my eyes and put the byte into the buffer. Yes, the system was dead. But what could this ISR do about it? Keep it simple.

Next we cover the logical half of receiving. Here we are mostly doing return *out+++. Often this will be done in a subroutine that returns a byte in a register. What should this subroutine do if the buffer is empty? The answer depends on your application and its supporting code. Sometimes the only real solution is to loop burning CPU cycles until the data arrives. Other times your getData() function should relinquish control to your underlying operating system. (One small OS has a feature that allows a task to wait until something moves your out pointer.) Other times returning 0x00 or the carry flag or a PSW zero condition is reasonable.

Pointer and data must be updated in the correct order. This is always true in interruptible code and is good discipline in an ISR. In our getData() function the code should look something like this:

char getData() {
char temp;
if (in == out) {whatever;}
temp = *in; // The order here
in+++; // is important
return temp;
{

I have been reminded that the above C-line code fragment could produce code that might not work in certain cases. The first potential problem is that the temp = *in; and in+++; lines might be optimized out of order. Without specific statements to the contrary C is free to reorder stores. With simple microcontrollers this code is safe to use with an ISR on the same machine. (Unless your C compiler starts to get fancy.)

The other problem is hardware. Some hardware – perhaps with multiple processors – may cause the following to happen. Processor X stores A and B in that order. Processor Y reads B and A in that order. Yet Processor Y gets the new B and the old A.

One might do well to assure that whatever high level language you use does not reorder your stores. I would look at the generated code. But that’s just me. But since one can not write in+++ the tests required before the new in is stored should eliminate out of order stores. The second problem is between you and your hardware.

The order is important because whatever process is taking data out of the buffer is looking at "in" to see if there is data in the buffer. Update the pointer before storing the data and you run the risk of the other process getting the prior value of *in.

In the this section you also need to do data = *out before out+++. As long as both put and get are implemented in this way for any buffer it will work even if your get and put functions run in independent autonomous processors with shared memory. (But see note on that aubject in the prior section.) CDC 6000 SCOPE did exactly that.

As we did when receiving data we will start with the physical side of this process. We enter our ISR when the RS-232 hardware receiver is able to accept a byte. Mostly we simply move *out+++ into the data register and we are done. But what if our buffer was empty when we enter the ISR? Attempts to ignore this lead nowhere in a hurry. Exit the ISR and you come right back - often without ever executing any non ISR code.

There is a simple way around this. When our FIFO buffer is empty turn off the hardware interrupt on receiver empty. We take an extra interrupt when we have nothing to send but our ISR is fast and simple. Getting 11 interrupts to send 10 bytes should not be a problem.

The logical side of transmit is generally in a subroutine called something like putData(). That subroutine mostly does *in+++ = data. But AFTER it does that it has to [re]enable the hardware interrupt on receiver empty. Often this is nothing more than sending a byte to a register. If this is done when the interrupt is already enabled most hardware will do nothing because nothing has changed. (But you are going to read the docs, right?)

Then we have to decide what to do when the buffer is full. Here it would be really stupid to put another byte in the buffer making the buffer empty. So we won't do that. We have several choices. With a reasonable OS, putData() should wait until our physical I/O removes a byte. Or the code could just loop waiting for the physical I/O. It's even possible to return a status saying that the buffer is full.

Two topics, slightly intertwined. You are now qualified to do both. Quiz on Friday.