मार्क-कॉम्पैक्ट एल्गोरिदम
कंप्यूटर विज्ञान में, मार्क-कॉम्पैक्ट एल्गोरिथम एक प्रकार का गार्बेज कलेक्शन एल्गोरिदम है जिसका उपयोग पहुंच योग्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी की कॉपीिंग एल्गोरिदम का संयोजन माना जा सकता है। पहले, पहुंच योग्य वस्तुओं को चिह्नित किया जाता है, और फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) वस्तुओं को ढेर क्षेत्र की शुरुआत की ओर स्थानांतरित करता है। आधुनिक जेवीएम, माइक्रोसॉफ्ट के कॉमन लैंग्वेज रनटाइम और ग्लासगो हास्केल कंपाइलर द्वारा गार्बेज कलेक्शन को संकुचित किया जाता है।
एल्गोरिदम
हीप में लाइव ऑब्जेक्ट्स को मार्क-स्वीप एल्गोरिदम के समान ही चिह्नित करने के बाद, हीप अक्सर खंडित हो जाएगा। मार्क-कॉम्पैक्ट एल्गोरिदम का लक्ष्य जीवित वस्तुओं को मेमोरी में एक साथ स्थानांतरित करना है ताकि विखंडन समाप्त हो जाए। चुनौती सभी पॉइंटर्स को स्थानांतरित ऑब्जेक्ट्स में सही ढंग से अपडेट करना है, जिनमें से अधिकांश में कॉम्पैक्शन के बाद नए मेमोरी पते होंगे। पॉइंटर अपडेट को संभालने के विषय को विभिन्न विधियों से नियंत्रित किया जाता है।
तालिका-आधारित संघनन
टेबल-आधारित एल्गोरिदम का वर्णन पहली बार 1967 में हेडन और वाइट द्वारा किया गया था।[1] यह ढेर में जीवित वस्तुओं के सापेक्ष स्थान को संरक्षित करता है, और केवल एक स्थिर मात्रा में ओवरहेड की आवश्यकता होती है।
संघनन ढेर के नीचे (कम पते) से ऊपर (उच्च पते) की ओर बढ़ता है। जैसे ही जीवित (अर्थात, चिह्नित) वस्तुओं का सामना किया जाता है, उन्हें पहले उपलब्ध निम्न पते पर ले जाया जाता है, और स्थानांतरण जानकारी की ब्रेक तालिका में एक रिकॉर्ड जोड़ा जाता है। प्रत्येक लाइव ऑब्जेक्ट के लिए, ब्रेक टेबल में एक रिकॉर्ड में कॉम्पैक्शन से पहले ऑब्जेक्ट का मूल पता और कॉम्पैक्शन के बाद मूल पते और नए पते के बीच का अंतर शामिल होता है। ब्रेक टेबल को उस ढेर में संग्रहित किया जाता है जिसे संकुचित किया जा रहा है, लेकिन ऐसे क्षेत्र में जिसे अप्रयुक्त के रूप में चिह्नित किया गया है। यह सुनिश्चित करने के लिए कि संघनन हमेशा सफल होगा, ढेर में न्यूनतम ऑब्जेक्ट का आकार ब्रेक टेबल रिकॉर्ड से बड़ा या उसके समान होना चाहिए।
जैसे-जैसे संघनन बढ़ता है, स्थानांतरित वस्तुएं ढेर के नीचे की ओर कॉपी हो जाती हैं। अंततः किसी ऑब्जेक्ट को ब्रेक टेबल द्वारा घेरी गई जगह पर कॉपी करने की आवश्यकता होगी, जिसे अब कहीं और स्थानांतरित किया जाना चाहिए। ब्रेक टेबल की ये गतिविधियां, (लेखकों द्वारा टेबल को रोल करना कहा जाता है) के कारण स्थानांतरण रिकॉर्ड अव्यवस्थित हो जाते हैं, जिसके लिए संघनन पूरा होने के बाद ब्रेक टेबल को तुलना क्रमबद्ध करने की आवश्यकता होती है। ब्रेक टेबल को सॉर्ट करने की लागत बड़ा ओ अंकन (एन लॉग एन) है, जहां एन जीवित वस्तुओं की संख्या है जो मार्क चरण में पाए गए थे कलन विधि।
अंत में, ब्रेक टेबल रिलोकेशन रिकॉर्ड का उपयोग स्थानांतरित ऑब्जेक्ट के अंदर पॉइंटर फ़ील्ड को समायोजित करने के लिए किया जाता है। पॉइंटर्स के लिए लाइव ऑब्जेक्ट की जांच की जाती है, जिसे कुल रनिंग टाइम के लिए, यदि ब्रेक टेबल को सॉर्ट किया जाता है, तो ओ (लॉग एन) समय में एन आकार की सॉर्ट की गई ब्रेक टेबल में देखा जा सकता है। 'ओ(एन लॉग एन)। फिर पॉइंटर्स को स्थानांतरण तालिका में निर्दिष्ट राशि के अनुसार समायोजित किया जाता है।
एलआईएसपी 2 एल्गोरिथम
O(n log n) जटिलता से बचने के लिए, LISP 2 एल्गोरिदम ढेर के ऊपर से तीन अलग-अलग पासों का उपयोग करता है। इसके अलावा, ढेर वस्तुओं में एक अलग अग्रेषण सूचक स्लॉट होना चाहिए जिसका उपयोग कचरा संग्रहण के बाहर नहीं किया जाता है।
मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है:
- जीवित वस्तुओं के लिए अग्रेषण स्थान की गणना करें।
- एक फ्री और लाइव पॉइंटर का ट्रैक रखें और ढेर की शुरुआत में दोनों को इनिशियलाइज़ करें।
- यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट की ओर इशारा करता है, तो उस ऑब्जेक्ट के फॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार फ्री पॉइंटर को बढ़ाएं।
- लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं
- जब लाइव पॉइंटर ढेर के अंत तक पहुंच जाए तो समाप्त करें।
- सभी पॉइंटर्स को अपडेट करें
- प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं।
- वस्तुओं को स्थानांतरित करें
- प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं।
यह एल्गोरिदम ढेर के आकार पर O(n) है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का n केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण ढेर स्थान जैसा कि LISP2 एल्गोरिथ्म में है। हालाँकि, LISP2 एल्गोरिथ्म को लागू करना आसान है।
यह भी देखें
संदर्भ
- ↑ B. K. Haddon; W. M. Waite (August 1967). "A compaction procedure for variable-length storage elements" (PDF). Computer Journal. 10 (2): 162–165. doi:10.1093/comjnl/10.2.162.
