फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)

एक फीफो कतार का प्रतिनिधित्व

कंप्यूटिंग और सिस्टम सिद्धांत में, फीफो फर्स्ट इन, फर्स्ट आउट (द फर्स्ट इन द फर्स्ट आउट) के लिए एक संक्षिप्त शब्द होता है, डेटा संरचना (अक्सर, विशेष रूप से डेटा बफर) के हेरफेर को व्यवस्थित करने के लिए एक विधि होती है जहां सबसे पुराना (पहला) ) प्रविष्टि, या कतार के प्रमुख (डेटा संरचना), को पहले संसाधित करता है।

इस तरह की प्रोसेसिंग पहले आओ, पहले पाओ (एफसीएफएस ) के आधार पर कतार क्षेत्र में लोगों की सेवा करने के अनुरूप होती है, यानी उसी क्रम में जिसमें वे कतार की पूंछ पर होते हैं।

एफसीएफएस फीफो निर्धारण (कंप्यूटिंग) एल्गोरिथम के लिए शब्दजाल शब्द भी होता है, जो प्रत्येक प्रक्रिया को सेंट्रल प्रोसेसिंग यूनिट (सीपीयू) समय में उस क्रम में देता है जिसमें इसकी मांग की जाती है। एफआईएफओ का विपरीत है एलआईएफओ (कंप्यूटिंग), लास्ट-इन-फर्स्ट-आउट, जहां सबसे कम उम्र की प्रविष्टि या स्टैक के शीर्ष को पहले संसाधित किया जाता है। एक प्राथमिकता कतार न तो एफआईएफओ या एलआईएफओ है, जोकि अस्थायी रूप से या डिफ़ॉल्ट रूप से समान व्यवहार अपना सकती है। कतारबद्ध सिद्धांत डेटा संरचनाओं को संसाधित करने के साथ-साथ सख्त-एफआईएफओ कतारों के बीच इंटरेक्शन के लिए इन विधियों को सम्मलित करता है।

कंप्यूटर विज्ञान

एनक्यू और डीक्यू ऑपरेशंस के साथ एक फीफो कतार का प्रतिनिधित्व।

आवेदन के आधार पर, एक एफआईएफओ को हार्डवेयर शिफ्ट रजिस्टर के रूप में या विभिन्न मेमोरी संरचनाओं का उपयोग करके, आमतौर पर एक परिपत्र बफर या एक प्रकार की सूची (सार डेटा प्रकार) के रूप में लागू करता है। अमूर्त डेटा संरचना के बारे में सूचना के लिए, कतार (डेटा संरचना) को देखें। एफआईएफओ कतार के अधिकांश सॉफ़्टवेयर कार्यान्वयन थ्रेड सुरक्षित नहीं होते हैं और डेटा संरचना श्रृंखला को एक समय में केवल एक थ्रेड द्वारा हेरफेर कि जाता है, यह सत्यापित करने के लिए लॉकिंग प्रणाली की आवश्यकता होती है।

निम्न कोड एक लिंक की गई सूची एफआईएफओ सी ++ भाषा के कार्यान्वयन को दिखाता है। व्यवहार में, लोकप्रिय यूनिक्स सिस्टम सी एसवाईएस /क्यू एच मैक्रोज़ या सी ++ मानक टेम्पलेट लाइब्रेरी एसटीडी::लिस्ट टेम्प्लेट सहित कई सूची कार्यान्वयन में मौजूद होती हैं, जो डेटा संरचना को स्क्रैच से लागू करने की आवश्यकता से बचते हैं।

कंप्यूटिंग वातावरण में पाइप और फिल्टर का समर्थन किया जाता है। इंटरप्रोसेस संचार के लिए पाइप-एंड-फिल्टर मॉडल, एक एफआईएफओ नामित पाइप का दूसरा नाम होता है।

डिस्क नियंत्रक एफआईएफओ को आई/ओ शेड्यूलिंग एल्गोरिथम के रूप में उपयोग करते हैं जिससे की डिस्क इनपुट/आउटपुट आई/ओ अनुरोधों को सेवा देने का क्रम निर्धारित करता है, जहां इसे एफसीएफएस इनिशियलिज़्म द्वारा भी जाना जाता है जैसा कि पहले सीपीयू शेड्यूलिंग के लिए उल्लेखित किया गया था।

संगणक संजाल में उपयोग किए जाने वाले संचार नेटवर्क ब्रिज, प्रसार बदलना और नेटवर्क राउटर अपने अगले गंतव्य के मार्ग में डेटा पैकेट रखने के लिए एफआईएफओ का उपयोग करते हैं। सामान्यतः प्रति नेटवर्क कनेक्शन में कम से कम एक एफआईएफओ संरचना का उपयोग किया जाता है। कुछ डिवाइस एक साथ और स्वतंत्र रूप से विभिन्न प्रकार की सूचनाओं को कतारबद्ध करने के लिए कई एफआईएफओ की सुविधा देते हैं।

इलेक्ट्रॉनिक्स

एक फीफो अनुसूची

हार्डवेयर और सॉफ्टवेयर के बीच बफरिंग और प्रवाह नियंत्रण के लिए सामान्यतः एफआईएफओ का उपयोग इलेक्ट्रानिक्स परिपथ में किया जाता है। अपने हार्डवेयर रूप में, एक एफआईएफओ में मुख्य रूप से पठन और लेखन सूचक (कंप्यूटर प्रोग्रामिंग), भंडारण और नियंत्रण तर्क का एक समूह होता है। स्टोरेज स्थिर रैंडम एक्सेस मेमोरी (SRAM), फ्लिप-फ्लॉप (इलेक्ट्रॉनिक्स), लैचेस या स्टोरेज के कोई अन्य उपयुक्त रूप हो सकते है। गैर-तुच्छ आकार के एफआईएफओ के लिए, एक दोहरे पोर्ट एस रैम का सामान्यतः उपयोग किया जाता है, जहां एक पोर्ट लिखने के लिए और दूसरा पढ़ने के लिए समर्पित होता है।

इलेक्ट्रॉनिक्स में लागू किया गया पहला ज्ञात एफआईएफओ 1969 में फेयरचाइल्ड सेमीकंडक्टर में पीटर अल्फके द्वारा किया गया था। पिटर अल्फ्के बाद में Xilinx में निदेशक थे।

समकालिकता

एक तुल्यकालिक फीफो एक फीफो है जहां पढ़ने और लिखने दोनों के लिए एक ही घड़ी का उपयोग किया जाता है। एक अतुल्यकालिक फीफो पढ़ने और लिखने के लिए अलग-अलग घड़ियों का उपयोग करता है और वे मेटास्टेबिलिटी अभिप्रायो को प्रस्तुत करते हैं। अतुल्यकालिक फीफो का एक सामान्य कार्यान्वयन विश्वसनीय फ़्लैग निर्माण सुनिश्चित करने के लिए पढ़ने और लिखने के संकेतकों के लिए एक ग्रे कोड (या किसी इकाई दूरी कोड) का उपयोग करता है। फ़्लैग जनरेशन से संबंधित एक और नोट यह है कि अतुल्यकालिक एफआईएफओ कार्यान्वयन के लिए फ़्लैग उत्पन्न करने के लिए आवश्यक रूप से एक अंकगणित संकेतक का उपयोग किया जाता है। इसके विपरीत, सिंक्रोनस फीफो कार्यान्वयन में झंडे उत्पन्न करने के लिए या तो एक लीक बकेट दृष्टिकोण या सूचक अंकगणित का उपयोग करता है।

एक हार्डवेयर एफआईएफओ का उपयोग तुल्यकालन उद्देश्यों के लिए किया जाता है। इसे अक्सर एक गोलाकार कतार के रूप में कार्यान्वित किया जाता है, और इस प्रकार दो पॉइंटर (कंप्यूटर प्रोग्रामिंग) होते हैं:

• सूचक पढ़ें / पता रजिस्टर पढ़ें
• सूचक लिखें / पता रजिस्टर लिखें

स्थिति झंडे

फीफो स्थिति झंडे के उदाहरणों में शामिल हैं: पूर्ण, खाली, लगभग भरा हुआ और लगभग खाली। जब रीड एड्रेस रजिस्टर राइट एड्रेस रजिस्टर तक पहुंचता है तो एक एफआईएफओ खाली होता है। एक एफआईएफओ तब भर जाता है जब राइट एड्रेस रजिस्टर रीड एड्रेस रजिस्टर तक पहुँच जाता है। पढ़ने और लिखने के पते प्रारंभ में पहले मेमोरी स्थान पर होते हैं और एफआईएफओ कतार खाली होती है।

दोनों ही मामलों में, पढ़ने और लिखने के पते बराबर होते हैं। दो स्थितियों के बीच अंतर करने के लिए, एक सरल और मजबूत समाधान प्रत्येक पढ़ने और लिखने के पते के लिए एक अतिरिक्त अंश को जोड़ता है जो हर बार पता इन्वर्ट होने पर उलटा होता है। इस सेट अप के साथ, असंबद्धता शर्तें होती हैं:

• जब रीड एड्रेस रजिस्टर राइट एड्रेस रजिस्टर के बराबर होता है, तो एफआईएफओ खाली होता है।
• जब पढ़ने और लिखने के पते के रजिस्टर केवल अतिरिक्त सबसे महत्वपूर्ण बिट में भिन्न होते है और बाकी समान होते हैं, तो एफआईएफओ भरा होता है।

यह भी देखें

• फीफो और लाइफो लेखा
• जब तक
• कतारबद्ध सिद्धांत

बाहरी संबंध

• Cummings et al., Simulation and Synthesis Techniques for Asynchronous एफआईएफओ Design with Asynchronous Pointer Comparisons, SNUG San Jose 2002