algorithm
ऑनलाइन एल्गोरिदम

टिप्पणियों

पेजिंग (ऑनलाइन कैशिंग)

प्रस्तावना

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

टिप्पणी अनुभाग के सूत्रों में इस विषय के लिए उपयोग की जाने वाली आधार सामग्री और आगे पढ़ने के लिए अतिरिक्त जानकारी शामिल है। इसके अलावा आपको वहां के उदाहरणों के लिए पूर्ण स्रोत कोड मिलेंगे। कृपया ध्यान दें कि उदाहरण के लिए स्रोत कोड को अधिक पठनीय और छोटा करने के लिए यह त्रुटि से निपटने जैसी चीजों से परहेज करता है आदि। यह कुछ विशिष्ट भाषा विशेषताओं पर भी गुजरता है जो उदाहरण की स्पष्टता को अस्पष्ट करेगा जैसे कि उन्नत पुस्तकालयों आदि का व्यापक उपयोग।

पेजिंग

पेजिंग समस्या सीमित स्थान की सीमा से उत्पन्न होती है। मान लेते हैं कि हमारे कैश C में k पृष्ठ हैं। अब हम m पेज रिक्वेस्ट के एक क्रम को संसाधित करना चाहते हैं, जिसे संसाधित होने से पहले कैश में रखा जाना चाहिए। बेशक अगर m<=k तो हम सिर्फ सभी तत्वों को कैश में रखते हैं और यह काम करेगा, लेकिन आमतौर पर m>>k ।

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

इस समस्या के लिए कई रणनीतियाँ हैं, आइए कुछ पर नजर डालते हैं:

1. पहले में, पहले बाहर (फीफो) : सबसे पुराना पेज बेदखल हो जाता है
2. अंतिम में, पहले बाहर (LIFO) : सबसे नया पृष्ठ निष्कासित हो जाता है
3. हाल ही में उपयोग किए गए कम से कम (LRU) : एविक्ट पेज जिसका हाल ही में सबसे अधिक उपयोग किया गया था
4. कम से कम अक्सर उपयोग किया जाने वाला (LFU) : कम से कम बार अनुरोध किया गया पृष्ठ निकालें
5. सबसे लंबी दूरी तय करना (LFD) : भविष्य में सबसे दूर तक कैश नहीं होने का सबूत पेज।
6. पूर्ण होने पर फ्लश करें (FWF) : कैश मिस होते ही कैश को पूरा करें

इस समस्या से निपटने के दो तरीके हैं:

1. ऑफ़लाइन : पृष्ठ अनुरोधों का क्रम समय से पहले जाना जाता है
2. ऑनलाइन : पृष्ठ अनुरोधों का क्रम समय से पहले ज्ञात नहीं है

ऑफ़लाइन दृष्टिकोण

पहले दृष्टिकोण के लिए विषय लालची तकनीक के अनुप्रयोग देखें । यह तीसरा उदाहरण है ऑफ़लाइन कैशिंग ऊपर से पहले पांच रणनीतियों पर विचार करता है और आपको निम्नलिखित के लिए एक अच्छा प्रवेश बिंदु देता है।

उदाहरण कार्यक्रम एफडब्ल्यूएफ रणनीति के साथ बढ़ाया गया था:

class FWF : public Strategy {
public:
    FWF() : Strategy("FWF")
    {
    }

    int apply(int requestIndex) override
    {
        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            // after first empty page all others have to be empty
            else if(cache[i] == emptyPage)
                return i;
        }

        // no free pages
        return 0;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {

        // no pages free -> miss -> clear cache
        if(cacheMiss && cachePos == 0)
        {
            for(int i = 1; i < cacheSize; ++i)
                cache[i] = emptyPage;
        }
    }
};

पूर्ण सोर्सकोड यहां उपलब्ध है । यदि हम विषय से उदाहरण का पुन: उपयोग करते हैं, तो हमें निम्न आउटपुट मिलते हैं:

Strategy: FWF

Cache initial: (a,b,c)

Request cache 0 cache 1 cache 2 cache miss
  a       a       b       c
  a       a       b       c
  d       d       X       X       x
  e       d       e       X
  b       d       e       b
  b       d       e       b
  a       a       X       X       x
  c       a       c       X
  f       a       c       f
  d       d       X       X       x
  e       d       e       X
  a       d       e       a
  f       f       X       X       x
  b       f       b       X
  e       f       b       e
  c       c       X       X       x

Total cache misses: 5

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

ऑनलाइन दृष्टिकोण

अब हम पेजिंग की ऑनलाइन समस्या से संपर्क करना चाहते हैं। लेकिन पहले हमें यह समझने की जरूरत है कि यह कैसे करना है। जाहिर है कि एक ऑनलाइन एल्गोरिथ्म इष्टतम ऑफ़लाइन एल्गोरिथ्म से बेहतर नहीं हो सकता है। लेकिन यह कितना बुरा है? हमें उस प्रश्न का उत्तर देने के लिए औपचारिक परिभाषाएँ चाहिए:

परिभाषा 1.1: एक अनुकूलन समस्या Π उदाहरणों Σ _Π का एक सेट के होते हैं। हर मामले _σ∈Σ Π के लिए वहाँ समाधान का एक सेट Ζ _σ और एक उद्देश्य समारोह च _σ है: _{Ζ σ} → ℜ ≥0 जो प्रदान करती है हर समाधान के लिए वास्तविक मूल्य apositive।
हम कहते हैं कि ऑप्ट (say) एक इष्टतम समाधान का मान है, A (is) समस्या के लिए एक एल्गोरिथ्म A का समाधान है for और w _A (σ) = f _σ (A (σ)) का मान।

परिभाषा 1.2: एक ऑनलाइन एल्गोरिथ्म A में कम से कम समस्या के लिए et में r if 1 का एक प्रतिस्पर्धात्मक अनुपात है , अगर इसके साथ कोई निरंतर algorithm है

w _A (σ) = f _σ (A ())) ⋅ r σ OPT (σ) + σ

सभी उदाहरणों _σ∈Σ Π के लिए। A को r- प्रतिस्पर्धी ऑनलाइन एल्गोरिथम कहा जाता है। सम है

w _A (σ) ⋅ r (OPT (σ)

सभी उदाहरणों के लिए _Π A तो A को कड़ाई से r- प्रतिस्पर्धी ऑनलाइन एल्गोरिथ्म कहा जाता है।

तो सवाल यह है कि एक इष्टतम ऑफ़लाइन एल्गोरिथ्म की तुलना में हमारा ऑनलाइन एल्गोरिथ्म कितना प्रतिस्पर्धी है। अपनी प्रसिद्ध पुस्तक में एलन बोरोडिन और रैन एल-यानिव ने ऑनलाइन पेजिंग स्थिति का वर्णन करने के लिए एक और परिदृश्य का उपयोग किया:

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

एल्गोरिदम को चिह्नित करना

इसके बजाय अलग एल्गोरिदम अंकन बुलाया पेजिंग समस्या के लिए एक विशेष ऑनलाइन एल्गोरिथ्म परिवार पर आइए नज़र हर एल्गोरिथ्म का विश्लेषण करने, के।

Let = (, ₁ , ..., an _p ) हमारी समस्या के लिए एक उदाहरण है और k हमारे कैश आकार, into को चरणों में विभाजित किया जा सकता है:

• चरण 1 शुरू से ही σ का अधिकतम परिणाम है जब तक कि अधिकतम k अलग-अलग पृष्ठों का अनुरोध नहीं किया जाता है
• चरण I σ 2, pase i-1 के अंत से ence की अधिकतम संख्या है, जब तक कि अधिकतम k विभिन्न पृष्ठों का अनुरोध नहीं किया जाता है

उदाहरण के लिए k = 3 के साथ:

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

प्रस्ताव 1.3: एलआरयू और एफडब्ल्यूएफ एल्गोरिथ्म को चिह्नित कर रहे हैं।

प्रमाण: प्रत्येक चरण की शुरुआत में (पहले एक को छोड़कर) एफडब्ल्यूएफ में कैश मिस होता है और कैशे को साफ़ करता है। इसका मतलब है कि हमारे पास खाली पृष्ठ हैं। प्रत्येक चरण में अनुरोधित अधिकतम पृष्ठ अलग-अलग होते हैं, इसलिए चरण के दौरान अब निष्कासन होगा। तो एफडब्ल्यूएफ एक अंकन एल्गोरिथ्म है।
मान लें कि LRU एक अंकन एल्गोरिथ्म नहीं है। फिर एक उदाहरण है σ जहां LRU चरण I में एक चिह्नित पृष्ठ x निकाला गया है। चरण मैं में σ _टी अनुरोध जहां x बेदखल कर रहा है। चूँकि x अंकित है, इसलिए पहले चरण में x के लिए for _{t *} होना चाहिए, इसलिए t * <t। T * x के बाद caches सबसे नया पेज है, इसलिए t _{t t * + 1} के अनुक्रम में निकाले जाने के लिए, ..., request _t को x विभिन्न पृष्ठों से कम से कम k अनुरोध करना होगा। इसका मतलब है कि चरण मैंने कम से कम k + 1 अलग-अलग पृष्ठों का अनुरोध किया है जो कि चरण परिभाषा के विपरीत है। इसलिए LRU को एक अंकन एल्गोरिथम होना चाहिए।

प्रस्ताव 1.4: प्रत्येक अंकन एल्गोरिथ्म कड़ाई से के-प्रतिस्पर्धी है ।

प्रमाण: पेजिंग समस्या के लिए एक उदाहरण है और σ के लिए चरणों की संख्या l करें। क्या l = 1 तब प्रत्येक अंकन एल्गोरिथम इष्टतम है और इष्टतम ऑफ़लाइन एल्गोरिथ्म बेहतर नहीं हो सकता है।
हम मान लेते हैं l 2. प्रत्येक अंकन एल्गोरिथ्म की लागत, उदाहरण के लिए, ⋅ l with k के साथ ऊपर से बंधा हुआ है क्योंकि हर चरण में एक अंकन एल्गोरिथ्म एक चिह्नित पृष्ठ को निकाले बिना k पृष्ठों से अधिक नहीं निकाल सकता है।
अब हम यह दिखाने का प्रयास करते हैं कि इष्टतम ऑफ़लाइन एल्गोरिथ्म पहले चरण में +, k के लिए कम से कम k + l-2 पृष्ठों और पिछले एक को छोड़कर प्रत्येक निम्नलिखित चरण के लिए कम से कम एक प्रदर्शित करता है। प्रमाण के लिए σ के बाद के एल -2 को परिभाषित करने की सुविधा देता है। बाद में sequ {1, ..., l-2} चरण I + 1 की दूसरी स्थिति से शुरू होता है और चरण i + 2 की पहली स्थिति के साथ समाप्त होता है।
आज्ञा देना x पहले चरण का पृष्ठ i + 1 है। बाद की शुरुआत में मैं पेज एक्स पर और अधिकतम k-1 विभिन्न पृष्ठों में इष्टतम ऑफ़लाइन एल्गोरिदम कैश में। बाद में मैं k पृष्ठ x से भिन्न अनुरोध करता हूं, इसलिए इष्टतम ऑफ़लाइन एल्गोरिथ्म को प्रत्येक बाद के लिए कम से कम एक पृष्ठ को निकालना होगा। चूंकि चरण 1 की शुरुआत में कैश अभी भी खाली है, पहले चरण के दौरान इष्टतम ऑफ़लाइन एल्गोरिथ्म k निष्कासन का कारण बनता है। जो दिखाता है

w _A (≤) ⋅ l⋅k k (k + l-2) k (OPT (σ) σ k

कोरोलरी 1.5: LRU और FWF कड़ाई से प्रतिस्पर्धात्मक हैं ।

आबकारी: दिखाओ कि FIFO कोई अंकन एल्गोरिथ्म नहीं है, लेकिन कड़ाई से प्रतिस्पर्धी है ।

क्या कोई निरंतर आर नहीं है जिसके लिए एक ऑनलाइन एल्गोरिथ्म ए-प्रतिस्पर्धी है, हम ए को प्रतिस्पर्धी नहीं कहते हैं

प्रस्ताव 1.6: एलएफयू और एलआईएफओ प्रतिस्पर्धी नहीं हैं।

प्रमाण: of 2 को एक स्थिर, k cache 2 कैश आकार दें। अलग-अलग कैश पेज 1, ..., k + 1 को nubered हैं। हम निम्नलिखित अनुक्रम को देखते हैं:

पहला पेज 1 पेज 2 की तुलना में एल बार और इतने पर अनुरोध किया गया है। अंत में, पृष्ठ k और k + 1 के लिए वैकल्पिक एल (एल -1) हैं।
LFU और LIFO 1-k पेज के साथ अपने कैश को भरते हैं। जब पृष्ठ k + 1 का अनुरोध किया जाता है तो पृष्ठ k को निकाल दिया जाता है और इसके विपरीत। इसका अर्थ है कि बाद के प्रत्येक अनुरोध (k, k + 1) ^{l-1 में} एक पृष्ठ दिखाया गया है। इसके अलावा, उनके पेज -1 (के -1) के पहली बार उपयोग के लिए के -1 कैश मिस हैं। इसलिए LFU और LIFO सटीक k-1 + 2 (l-1) पृष्ठ निकालते हैं।
अब हमें यह दिखाना चाहिए कि प्रत्येक स्थिर for और प्रत्येक स्थिर r exists 1 के लिए एक l मौजूद है

जो के बराबर है

इस असमानता को पूरा करने के लिए आपको बस एल पर्याप्त बड़ा चुनना होगा। इसलिए LFU और LIFO प्रतिस्पर्धी नहीं हैं।

प्रस्ताव 1.7: r <k के साथ पेजिंग के लिए कोई r- प्रतिस्पर्धात्मक निर्धारक ऑनलाइन एल्गोरिथ्म नहीं है।

इस अंतिम प्रस्ताव का प्रमाण लंबा है और इस कथन पर आधारित है कि LFD एक इष्टतम ऑफ़लाइन एल्गोरिथम है। इच्छुक पाठक इसे बोरोडिन और एल-यानिव की पुस्तक में देख सकते हैं (नीचे स्रोत देखें)।

सवाल यह है कि क्या हम बेहतर कर सकते थे। उसके लिए, हमें नियतात्मक दृष्टिकोण को पीछे छोड़ना होगा और अपने एल्गोरिथ्म को यादृच्छिक बनाना शुरू करना होगा। जाहिर है, अगर यह यादृच्छिक है तो अपने एल्गोरिथ्म को दंडित करने के लिए विरोधी के लिए बहुत कठिन है।

रैंडमाइज्ड पेजिंग की चर्चा अगले उदाहरणों में से एक में की जाएगी ...