Replacement Algorithms in cache memory:-
direct mapping के लिए जहां मेमोरी के एक ब्लॉक के लिए केवल एक potential line है, कोई प्रतिस्थापन एल्गोरिदम आवश्यक नहीं है। companionship और set associative mapping के लिए, एक एल्गोरिथ्म की आवश्यकता होती है। इस point पर, हम एक सबसे आम substitution algorithm का description करेंगे, जिसे LRU एल्गोरिथम कहा जाता है। यह एल्गोरिथ्म समझने में आसान है और more advanced replacement algorithms को समझने के लिए एक nice background provide करता है। कई अन्य substitution algorithm का भी उपयोग किया जाता है जैसे: पहले पहले substitution algorithm में, random replacement algorithm इत्यादि।
Least Recently Used (LRU):-
Reference की locality के कारण, program आमतौर पर reasonable time के लिए local areas में रहते हैं। इसलिए इस बात की बहुत अधिक संभावना है कि जिन ब्लॉकों को हाल ही में referenced किया गया है, उन्हें जल्द ही फिर से referenced किया जाएगा। इसलिए, यह कैश मेमोरी में ब्लॉक को overwrite कर देता है जो बिना किसी reference के सबसे लंबे समय तक रहा है। उस ब्लॉक को कम से कम हाल ही में उपयोग किए गए ब्लॉक के रूप में जाना जाता है और तकनीक को कम से कम हाल ही में Substitution Algorithm Used (LRU) के रूप में जाना जाता है। इस method में, मुख्य मेमोरी में every page के साथ एक काउंटर जोड़ा जाता है और इसे समय के fixed interval पर 1 से बढ़ाया जाता है। जब किसी page का reference दिया जाता है, तो उसका काउंटर 0 पर सेट होता है। इस प्रकार, counter page की age बताता है। जब किसी page को हटाने की आवश्यकता होती है, तो highest counter वाला page हटा दिया जाता है।
टिप्पणियाँ
एक टिप्पणी भेजें