17 / 24 · अवधारणा
FIFO का खाली, भरा और एक साथ स्थानांतरण व्यवहार
भरे स्थानों की संख्या को पॉइंटर से अलग रखें और सीमाओं पर push/pop स्पष्ट करें।
पाठ पढ़ना मुफ़्त है। प्रगति सेव करने के लिए नामांकन करें।
कतार स्वीकृति का क्रम बनाए रखती है
FIFO सबसे पहले सबसे पुराना स्वीकार किया आइटम देता है। उसका read pointer सबसे पुरानी प्रविष्टि और write pointer अगला भंडारण स्थान दर्शाता है। केवल समान पॉइंटर खाली और भरे में अंतर नहीं कर सकते, इसलिए यह डिज़ाइन भरे स्थानों की संख्या रखता है। गहराई चार में पॉइंटर को दो बिट चाहिए, लेकिन शून्य से चार दर्शाने के लिए count को तीन चाहिए। डेटा के साथ टैग रखें।
हमारे रजिस्टर वाले FIFO में खाली कतार से सीधे पार जाना नहीं होता। Output-valid, count>0 है और pop, output-valid AND output-ready है। Input-ready, count<depth OR pop है, जिससे भरी कतार अपना पहला आइटम देते समय प्रतिस्थापन स्वीकार कर सकती है। Push, input-valid AND input-ready है। अगला count, count+push-pop है। count बढ़ाने और घटाने के दो अलग असाइनमेंट एक साथ स्थानांतरण गलत संभाल सकते हैं; एक संयुक्त अपडेट या स्पष्ट मामले रखें।
| पुराना count | परिस्थितियाँ | push | pop | नया count |
|---|---|---|---|---|
| 0 | इनपुट और तैयार प्राप्तकर्ता | 1 | 0 | 1 |
| 1 | इनपुट और तैयार प्राप्तकर्ता | 1 | 1 | 1 |
| 4 | इनपुट और स्टॉल किया प्राप्तकर्ता | 0 | 0 | 4 |
| 4 | इनपुट और तैयार प्राप्तकर्ता | 1 | 1 | 4 |
केवल प्राप्तकर्ता तैयार होने से खाली कतार pop नहीं कर सकती। उसका नया इनपुट पहली बार अगले किनारे पर स्थानांतरित होता है। भरी कतार [A,B,C,D], A उपयोग करने और E स्वीकार करने पर [B,C,D,E] होती है और भरी रहती है। एक ही भौतिक स्थान पर पढ़ते और लिखते समय मूल मेमोरी का व्यवहार सत्यापित करें।
चार-स्थान FIFO। शुरुआत में खाली; पढ़ने और लिखने के पॉइंटर 0 हैं। खाली न होने पर pop स्वीकारती है। जगह उपलब्ध हो या उसी एज पर pop स्वीकारा जाए तो push स्वीकारती है।
दो की घात वाली गहराई में पॉइंटर बिट स्वाभाविक रूप से आरंभ पर लौटते हैं। गहराई तीन में स्थान दो से शून्य का स्पष्ट परिवर्तन चाहिए। वापसी, अंतिम आइटम निकालना और भरे में प्रतिस्थापन अलग परखें।
गहराई चार की खाली कतार प्राप्तकर्ता के पाँच-चक्र स्टॉल में केवल चार आइटम समा सकती है। पाँचवें इनपुट को प्रतीक्षा करनी चाहिए। जो स्रोत स्टॉल नहीं कर सकता उसे अधिक क्षमता या तय हानि नीति चाहिए। कोई सीमित FIFO स्थायी रूप से धीमी खपत नहीं सुधारता। 0≤count≤depth, accepted-delivered=count और टैग क्रम जाँचें; केवल गिनती से बदला क्रम नहीं पकड़ सकते।
खुद आज़माएँ
गहराई दो और कतार [tag3,tag4] में out-ready=1 के साथ tag5 इनपुट प्रस्तुत है। push, pop, अगला count और अगली कतार निकालें। कतार खाली होती तो क्या tag5 तुरंत pop करता?
व्याख्या पढ़ें
Pop=1 भरे होने पर भी input-ready उच्च करता है, इसलिए push=1। अगला count दो रहता है और कतार [tag4,tag5] होती है। खाली कतार में out-valid=0 है, इसलिए tag5 संग्रहीत होता है और बाद के किनारे तक pop नहीं कर सकता।