FIFO Dynamics
As you recall, the FIFO passes the data from the producer to the consumer. In general, the rates at which data are produced and consumed can vary dynamically. Humans do not enter data into a keyboard at a constant rate.
Even printers require more time to print color graphics versus black and white text. Let tp be the time (in sec) between calls to PutFifo, and rp be the arrival rate (producer rate in bytes/sec) into the system. Similarly, let tg be the time (in sec) between calls to GetFifo, and rg be the service rate (consumerrate in bytes/sec) out of the system.
rg=1/tg
rp=1/tp
If the minimum time between calls to PutFifo is greater than the maximum time between calls to GetFifo,
min tp > max tg
the other hand, if the time between calls to PutFifo becomes less than the time between calls to GetFifo because either
• the arrival rate temporarily increases
• the service rate temporarily decreases
then information will be collected in the FIFO. For example, a person might type very fast for a while followed by long pause. The FIFO could be used to capture without loss all the data as it comes in very fast. Clearly on average the system must be able to process the data (the consumer thread) at least as fast as the average rate at which the data arrives (producer thread). If the average producer rate is larger than the average consumer rate
rp > rg
then the FIFO will eventually overflow no matter how large the FIFO. If the producer rate is temporarily high, and that causes the FIFO to become full, then this problem can be solved by increasing the FIFO size.
There is fundamental difference between an empty error and a full error. Consider the application of using a FIFO between your computer and its printer. This is a good idea because the computer can temporarily generate data to be printed at a very high rate followed by long pauses. The printer is like a
turtle. It can print at a slow but steady rate (e.g., 10 characters/sec.) The computer will put a byte into the FIFO that it wants printed. The printer will get a byte out of the FIFO when it is ready to print another character. A full error occurs when the computer calls PutFifo at too fast a rate. A full error is serious,
because if ignored data will be lost. On the other hand, an empty error occurs when the printer is ready to print but the computer has nothing in mind. An empty error is not serious, because in this case the printer just sits there doing nothing.
Wednesday, January 13, 2010
Two pointer/counter FIFO implementation
Two pointer/counter FIFO implementation
The other method to determine if a FIFO is empty or full is to implement a counter. In the following code, Size contains the number of bytes currently stored in the FIFO.
The advantage of implementing the counter is that FIFO 1/4 full and 3/4 full conditions are easier to implement. If you were studying the behavior of a system it might be informative to measure the current Size as a function of time.
/* Pointer,counter implementation of the FIFO */
#define FifoSize 10 /* Number of 8 bit data in the Fifo */
char *PutPt; /* Pointer of where to put next */
char *GetPt; /* Pointer of where to get next */
unsigned char Size; /* Number of elements currently in the FIFO */
/* FIFO is empty if Size=0 */
/* FIFO is full if Size=FifoSize */
char Fifo[FifoSize]; /* The statically allocated fifo data */
void InitFifo(void) { char SaveSP;
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
PutPt=GetPt=&Fifo[0]; /* Empty when Size==0 */
Size=0;
asm(" ldaa %SaveSP\n tap"); /* end critical section */
}
int PutFifo (char data) { char SaveSP;
if (Size == FifoSize ) {
return(0);} /* Failed, fifo was full */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
Size++;
*(PutPt++)=data; /* put data into fifo */
if (PutPt == &Fifo[FifoSize]) PutPt = &Fifo[0]; /* Wrap */
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); /* Successful */
}
}
int GetFifo (char *datapt) { char SaveSP;
if (Size == 0 ){
return(0);} /* Empty if Size=0 */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
*datapt=*(GetPt++); Size--;
if (GetPt == &Fifo[FifoSize]) GetPt = &Fifo[0];
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); }
}
Program 5.18. C language routines to implement a two pointer with counter FIFO.
To check for FIFO full, the above PutFifo routine simply compares Size to the maximum allowed
value. If the FIFO is already full then the routine is exited without saving the data. With this
implementation a FIFO with 10 allocated bytes can actually hold 10 data points.
To check for FIFO empty, the following GetFifo routine simply checks to see if Size equals 0.
If Size is zero at the start of the routine, then GetFifo returns with the "empty" condition signified.
The other method to determine if a FIFO is empty or full is to implement a counter. In the following code, Size contains the number of bytes currently stored in the FIFO.
The advantage of implementing the counter is that FIFO 1/4 full and 3/4 full conditions are easier to implement. If you were studying the behavior of a system it might be informative to measure the current Size as a function of time.
/* Pointer,counter implementation of the FIFO */
#define FifoSize 10 /* Number of 8 bit data in the Fifo */
char *PutPt; /* Pointer of where to put next */
char *GetPt; /* Pointer of where to get next */
unsigned char Size; /* Number of elements currently in the FIFO */
/* FIFO is empty if Size=0 */
/* FIFO is full if Size=FifoSize */
char Fifo[FifoSize]; /* The statically allocated fifo data */
void InitFifo(void) { char SaveSP;
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
PutPt=GetPt=&Fifo[0]; /* Empty when Size==0 */
Size=0;
asm(" ldaa %SaveSP\n tap"); /* end critical section */
}
int PutFifo (char data) { char SaveSP;
if (Size == FifoSize ) {
return(0);} /* Failed, fifo was full */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
Size++;
*(PutPt++)=data; /* put data into fifo */
if (PutPt == &Fifo[FifoSize]) PutPt = &Fifo[0]; /* Wrap */
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); /* Successful */
}
}
int GetFifo (char *datapt) { char SaveSP;
if (Size == 0 ){
return(0);} /* Empty if Size=0 */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
*datapt=*(GetPt++); Size--;
if (GetPt == &Fifo[FifoSize]) GetPt = &Fifo[0];
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); }
}
Program 5.18. C language routines to implement a two pointer with counter FIFO.
To check for FIFO full, the above PutFifo routine simply compares Size to the maximum allowed
value. If the FIFO is already full then the routine is exited without saving the data. With this
implementation a FIFO with 10 allocated bytes can actually hold 10 data points.
To check for FIFO empty, the following GetFifo routine simply checks to see if Size equals 0.
If Size is zero at the start of the routine, then GetFifo returns with the "empty" condition signified.
First In First Out Queue
Introduction to FIFO’s
As we saw earlier, the first in first out circular queue (FIFO) is quite useful for implementing a buffered I/O interface. It can be used for both buffered input and buffered output. The order preserving data structure temporarily saves data created by the source (producer) before it is processed by the sink (consumer). The class of FIFO’s studied in this section will be statically allocated global structures.
Because they are global variables, it means they will exist permanently and can be carefully shared by more than one program. The advantage of using a FIFO structure for a data flow problem is that we can decouple the producer and consumer threads. Without the FIFO we would have to produce 1 piece of data, then
process it, produce another piece of data, then process it. With the FIFO, the producer thread can continue to produce data without having to wait for the consumer to finish processing the previous data. This decoupling can significantly improve system performance.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used
when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the
DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the
printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
As we saw earlier, the first in first out circular queue (FIFO) is quite useful for implementing a buffered I/O interface. It can be used for both buffered input and buffered output. The order preserving data structure temporarily saves data created by the source (producer) before it is processed by the sink (consumer). The class of FIFO’s studied in this section will be statically allocated global structures.
Because they are global variables, it means they will exist permanently and can be carefully shared by more than one program. The advantage of using a FIFO structure for a data flow problem is that we can decouple the producer and consumer threads. Without the FIFO we would have to produce 1 piece of data, then
process it, produce another piece of data, then process it. With the FIFO, the producer thread can continue to produce data without having to wait for the consumer to finish processing the previous data. This decoupling can significantly improve system performance.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used
when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the
DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the
printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
When to use interrupts
When to use interrupts
The following factors should be considered when deciding the most appropriate mechanism to synchronize hardware and software. One should not always use gadfly because one is too lazy tO implement the complexities of interrupts. On the other hand, one should not always use interrupts because they are fun and exciting.
isition&control
The following factors should be considered when deciding the most appropriate mechanism to synchronize hardware and software. One should not always use gadfly because one is too lazy tO implement the complexities of interrupts. On the other hand, one should not always use interrupts because they are fun and exciting.
isition&control
Interrupt Service Routines
The interrupt service routine (ISR) is the software module that is executed when the hardware requests an interrupt. From the last section, we see that there may be one large ISR that handles all requests (polled interrupts), or many small ISR's specific for each potential source of interrupt (vectored interrupts). The design of the interrupt service routine requires careful consideration of many factors that will be discussed in this chapter. When an interrupt is requested (and the device is armed and the I bit is one), the microcomputer will service an interrupt:
1) the execution of the main program is suspended (the current instruction is finished),
2) the interrupt service routine, or background thread is executed,
3) the main program is resumed when the interrupt service routine executes iret .
When the microcomputer accepts an interrupt request, it will automatically save the execution state of the main thread by pushing all its registers on the stack. After the ISR provides the necessary service it will execute a iret instruction. This instruction pulls the registers from the stack, which returns control to the main program. Execution of the main program will then continue with the exact stack and register values that existed before the interrupt. Although interrupt handlers can allocate, access then deallocate local variables, parameter passing between threads must be implemented using global memory variables. Global variables are also equired if an interrupt thread wishes to pass information to itself, e.g., from one interrupt instance to another. The execution of the main program is called the foreground thread, and the executions of interrupt service routines are called background threads.
Interrupt definition
Interrupt definition
An interrupt is the automatic transfer of software execution in response to hardware that is asynchronous with the current software execution. The hardware can either be an external I/O device (like a keyboard or printer) or an internal event (like an op code fault, or a periodic timer.) When the hardware needs service (busy to done state transition) it will request an interrupt. A thread is defined as the path of
action of software as it executes. The execution of the interrupt service routine is called a background thread. This thread is created by the hardware interrupt request and is killed when the interrupt service routine executes the iret instruction. A new thread is created for each interrupt request. It is important to consider each individual request as a separate thread because local variables and registers used in the interrupt service routine are unique and separate from one interrupt event to the next. In a multithreaded system we consider the threads as cooperating to perform an overall task. Consequently we will develop ways for the threads to communicat and synchronize with each other. Most embedded systems have a single common overall goal. On the other hand general-purpose computers can have multiple unrelated functions to perform. A process is also defined as the action of software as it executes. The difference is processes do not necessarily cooperate towards a common shared goal. The software has dynamic control over aspects of the interrupt request sequence. First, each potential interrupt source has a separate arm bit that the software can activate or deactivate. The software will set the arm bits for those devices it wishes to accept interrupts from, and will deactivate the arm bits
within those devices from which interrupts are not to be allowed. In other words it uses the arm bits to individually select which devices will and which devices will not request interrupts. The second aspect that the software controls is the interrupt enable bit, I, which is in the status register (SR). The software can
enable all armed interrupts by setting I=1 (sti), or it can disable all interrupts by setting I=0 (cli). The disabled interrupt state (I=0) does not dismiss the interrupt requests, rather it postpones them until a later time, when the software deems it convenient to handle the requests. We will pay special attention to these
enable/disable software actions. In particular we will need to disable interrupts when executing nonreentrant code but disabling interrupts will have the effect of increasing the response time of software. There are two general methods with which we configure external hardware so that it can request an interrupt. The first method is a shared negative logic level-active request like IRQ . All the devices
that need to request interrupts have an open collector negative logic interrupt request line. The hardware requests service by pulling the interrupt request IRQ line low. The line over the IRQ signifies negative logic. In other words, an interrupt is requested when IRQ is zero. Because the request lines are open
collector, a pull up resistor is needed to make IRQ high when no devices need service.
Normally these interrupt requests share the same interrupt vector. This means whichever device requests an
interrupt, the same interrupt service routine is executed. Therefore the interrupt service routine must first
determine which device requested the interrupt.
The original IBM-PC had only 8 dedicated edge-triggered interrupt lines, and the current PC I/O bus only has 15. This small number can be a serious limitation in a computer system with many I/O devices.
Observation: Microcomputer systems running in expanded mode often use shared negative logic
level-active interrupts for their external I/O devices.
Observation: Microcomputer systems running in single chip mode often use dedicated edgetriggered
interrupts for their I/O devices.
Observation: The number of interrupting devices on a system using dedicated edge-triggered
interrupts is limited when compared to a system using shared negative logic level-active interrupts.
Observation: Most Motorola microcomputers support both shared negative logic and dedicated edge-triggered interrupts.
An interrupt is the automatic transfer of software execution in response to hardware that is asynchronous with the current software execution. The hardware can either be an external I/O device (like a keyboard or printer) or an internal event (like an op code fault, or a periodic timer.) When the hardware needs service (busy to done state transition) it will request an interrupt. A thread is defined as the path of
action of software as it executes. The execution of the interrupt service routine is called a background thread. This thread is created by the hardware interrupt request and is killed when the interrupt service routine executes the iret instruction. A new thread is created for each interrupt request. It is important to consider each individual request as a separate thread because local variables and registers used in the interrupt service routine are unique and separate from one interrupt event to the next. In a multithreaded system we consider the threads as cooperating to perform an overall task. Consequently we will develop ways for the threads to communicat and synchronize with each other. Most embedded systems have a single common overall goal. On the other hand general-purpose computers can have multiple unrelated functions to perform. A process is also defined as the action of software as it executes. The difference is processes do not necessarily cooperate towards a common shared goal. The software has dynamic control over aspects of the interrupt request sequence. First, each potential interrupt source has a separate arm bit that the software can activate or deactivate. The software will set the arm bits for those devices it wishes to accept interrupts from, and will deactivate the arm bits
within those devices from which interrupts are not to be allowed. In other words it uses the arm bits to individually select which devices will and which devices will not request interrupts. The second aspect that the software controls is the interrupt enable bit, I, which is in the status register (SR). The software can
enable all armed interrupts by setting I=1 (sti), or it can disable all interrupts by setting I=0 (cli). The disabled interrupt state (I=0) does not dismiss the interrupt requests, rather it postpones them until a later time, when the software deems it convenient to handle the requests. We will pay special attention to these
enable/disable software actions. In particular we will need to disable interrupts when executing nonreentrant code but disabling interrupts will have the effect of increasing the response time of software. There are two general methods with which we configure external hardware so that it can request an interrupt. The first method is a shared negative logic level-active request like IRQ . All the devices
that need to request interrupts have an open collector negative logic interrupt request line. The hardware requests service by pulling the interrupt request IRQ line low. The line over the IRQ signifies negative logic. In other words, an interrupt is requested when IRQ is zero. Because the request lines are open
collector, a pull up resistor is needed to make IRQ high when no devices need service.
Normally these interrupt requests share the same interrupt vector. This means whichever device requests an
interrupt, the same interrupt service routine is executed. Therefore the interrupt service routine must first
determine which device requested the interrupt.
The original IBM-PC had only 8 dedicated edge-triggered interrupt lines, and the current PC I/O bus only has 15. This small number can be a serious limitation in a computer system with many I/O devices.
Observation: Microcomputer systems running in expanded mode often use shared negative logic
level-active interrupts for their external I/O devices.
Observation: Microcomputer systems running in single chip mode often use dedicated edgetriggered
interrupts for their I/O devices.
Observation: The number of interrupting devices on a system using dedicated edge-triggered
interrupts is limited when compared to a system using shared negative logic level-active interrupts.
Observation: Most Motorola microcomputers support both shared negative logic and dedicated edge-triggered interrupts.
Subscribe to:
Posts (Atom)