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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समकालिकता

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

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

• सूचक को पढ़ें / पता रजिस्टर को पढ़ें (रीड एड्रेस रजिस्टर)
• सूचक को लिखें / पता रजिस्टर को लिखें (राइट एड्रेस रजिस्टर )

स्थितिफ़्लैग

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

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

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

यह भी देखें

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

बाहरी संबंध

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