Bélády's anomaly
कंप्यूटर भंडारण में, बेलेडी की विसंगति वह घटना है जिसमें पृष्ठ फ्रेम की संख्या में वृद्धि के परिणामस्वरूप कुछ स्मृति अभिगम पैटर्न के लिए पृष्ठ दोषों की संख्या में वृद्धि होती है। यह घटना आमतौर पर फर्स्ट-इन-फर्स्ट-आउट (एफ. आई. एफ. ओ.) पेज रिप्लेसमेंट एल्गोरिदम का उपयोग करते समय अनुभव की जाती है। एफ. आई. एफ. ओ. में, पेज फ्रेम बढ़ने पर पेज फॉल्ट बढ़ भी सकता है और नहीं भी, लेकिन एल. आर. यू. जैसे इष्टतम और स्टैक-आधारित एल्गोरिदम में, जैसे-जैसे पेज फ्रेम बढ़ते हैं, पेज फॉल्ट कम होता जाता है। लास्लो बेलेडी ने 1969 में इसका प्रदर्शन किया। पृष्ठभूमि सामान्य कंप्यूटर स्मृति प्रबंधन में, जानकारी को विशिष्ट आकार के हिस्सों में लोड किया जाता है। प्रत्येक खंड को एक पृष्ठ के रूप में संदर्भित किया जाता है। मुख्य स्मृति एक समय में केवल सीमित संख्या में पृष्ठों को धारण कर सकती है। इसके लिए प्रत्येक पृष्ठ के लिए एक फ्रेम की आवश्यकता होती है जिसे यह लोड कर सकता है। एक पृष्ठ दोष तब होता है जब कोई पृष्ठ नहीं मिलता है, और इसे डिस्क से मेमोरी में लोड करने की आवश्यकता हो सकती है। जब कोई पृष्ठ दोष होता है और सभी फ्रेम उपयोग में होते हैं, तो नए पृष्ठ के लिए जगह बनाने के लिए एक को साफ़ किया जाना चाहिए। एक सरल एल्गोरिथ्म एफ. आई. एफ. ओ. हैः फ्रेम में जो भी पृष्ठ सबसे लंबा रहा है, उसे साफ़ कर दिया जाता है। जब तक बेलेडी की विसंगति का प्रदर्शन नहीं किया गया था, यह माना जाता था कि पृष्ठ फ्रेम की संख्या में वृद्धि के परिणामस्वरूप हमेशा समान संख्या में या कम पृष्ठ दोष होंगे। बेलेडी की विसंगति असीमित बेलेडी है, नेल्सन और शेडलर ने संदर्भ तारों का निर्माण किया जिसके लिए एफ. आई. एफ. ओ. पृष्ठ प्रतिस्थापन एल्गोरिथ्म ने एक छोटी स्मृति की तुलना में बड़ी स्मृति में लगभग दोगुने पृष्ठ दोष उत्पन्न किए और उन्होंने यह अनुमान तैयार किया कि 2 एक सामान्य बाध्य है। 2010 में, फोरनाई और इवानी ने दिखाया कि विसंगति वास्तव में असीमित है और कोई भी किसी भी मनमाने पृष्ठ दोष अनुपात के लिए एक संदर्भ स्ट्रिंग का निर्माण कर सकता है। संदर्भ बाहरी लिंक बेलेडी के 1969 के पेपरः एक पेजिंग मशीन में चलने वाले कुछ कार्यक्रमों की अंतरिक्ष-समय विशेषताओं में विसंगति एफ. आई. एफ. ओ विसंगति असीमित है। इंटरनेट समस्या समाधान प्रतियोगिता समाधान-समस्या एल-पुस्तकालय स्मृति प्रबंधन