Page 1 1 CS 5780 School of Computing University of Utah CS/ECE 6780/5780 Al Davis Today’s topics: • FIFO’s 6812 style • hopefully a review? 2 CS 5780 School of Computing University of Utah FIFO’s • Useful interface provide slack to decouple producer and consumer rates provides order preserving buffering » for the case where all produced values are important • alternative – single memory location – for the case when only the most recent value is needed circular queue is a useful buffered I/O interface » statically allocated global memory • aids in controlling memory footprint when resources are limited – e.g. as in your lab kits • can be shared by main and ISR’s – access must be carefully controlled to get it right howeverPage 2 3 CS 5780 School of Computing University of Utah Producer Consumer Examples 4 CS 5780 School of Computing University of Utah FIFO w/ Infinite MemoryPage 3 5 CS 5780 School of Computing University of Utah Basic Code Model • Not robust however What’s missing? 6 CS 5780 School of Computing University of Utah 2-pointer Finite FIFO InitializationPage 4 7 CS 5780 School of Computing University of Utah Atomicity Functions What is another way to do this? 8 CS 5780 School of Computing University of Utah Put for a 2-pointer Circular FIFO Is this correct?Page 5 9 CS 5780 School of Computing University of Utah Put Example Initially 10 CS 5780 School of Computing University of Utah Put ExamplePage 6 11 CS 5780 School of Computing University of Utah Put Example 12 CS 5780 School of Computing University of Utah Get for a 2-pointer Circular FIFOPage 7 13 CS 5780 School of Computing University of Utah 2-pointer vs. Counter FIFO’s • 2 pointer version implicit number of elements » how do you calculate how many values are in the queue? • Alternative is explicit store of current size 2-pointer counter FIFO » requires an extra variable – e.g. Size!» but has compensating advantages 14 CS 5780 School of Computing University of Utah Initialization of a 2-pointer Counter FIFOPage 8 15 CS 5780 School of Computing University of Utah Put Function 16 CS 5780 School of Computing University of Utah Get Function What advantages come from the Size variable?Page 9 17 CS 5780 School of Computing University of Utah Yet Another FIFO Option • First two options used pointers • Index FIFO accesses elements via array indices 18 CS 5780 School of Computing University of Utah Index FIFO Initialization Same basic idea but w/o pointer weirdnessPage 10 19 CS 5780 School of Computing University of Utah Index FIFO Put 20 CS 5780 School of Computing University of Utah Index FIFO GetPage 11 21 CS 5780 School of Computing University of Utah FIFO Dynamics 22 CS 5780 School of Computing University of Utah SCI Data Flow Graph w/ Two FIFOsPage 12 23 CS 5780 School of Computing University of Utah Concluding Remarks • Basic FIFO service decouple rate of production from rate of consumption ideal size depends on maximum slack between the rates • Cost some RAM utilization and a few CPU cycles note crtical section occupancy » if it’s longer the tp or tc then there is a problem • solution? • Real systems have FIFO’s everywhere main reason why this lecture had such a narrow focus what’s the fundamental reason for this? • FIFO’s are concurrent data structures touched by main + ISRs or threads • Writing correct concurrent data structures can be hard if done right then using them is
View Full Document
Unlocking...