फ्रैगमेंटेशन-प्रतिरोधी माइक्रोकंट्रोलर हीप एल्गोरिदम

Question

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

मेरे आवश्यकताएँ:

स्पीड निश्चित रूप से मायने रखता है, लेकिन एक उच्च माध्यमिक चिंता का विषय है।

-निर्धारण निर्धारण निर्धारण महत्वपूर्ण नहीं है - कोड के किसी भी भाग को निर्धारित करने वाले सबसे बुरे मामले के समय की अपनी आवंटन विधि की आवश्यकता होती है।

- मुख्य आवश्यकता विखंडन प्रतिरक्षा है। डिवाइस एक लुआ स्क्रिप्ट इंजन चला रहा है, जिसमें आवंटन आकारों की एक श्रृंखला की आवश्यकता होगी (32 बाइट ब्लॉक पर भारी)। मुख्य आवश्यकता यह है कि इस डिवाइस के लिए एक अनुपयोगी स्थिति में अपने ढेर को मंथन किए बिना लंबे समय तक चलने के लिए।

इसके अलावा नोट:

के लिए इस संदर्भ में, हम एक कॉर्टेक्स-एम और PIC32 भागों के बारे में, 128K से लेकर स्मृति और 16MB या स्मृति (निचले सिरे पर ध्यान देने के साथ) बात कर रहे हैं।

- मैं कंपाइलर के ढेर का उपयोग नहीं करना चाहता क्योंकि 1) मैं सभी कंपाइलरों में लगातार प्रदर्शन करना चाहता हूं और 2) उनके कार्यान्वयन आमतौर पर बहुत सरल होते हैं और विखंडन के लिए समान या बदतर होते हैं।

- लूडा कोड आधार के कारण दोहरे अप्रत्यक्ष विकल्प बाहर हैं जो मैं मूल रूप से परिवर्तित और पुन: वैध नहीं करना चाहता हूं।

मेरे इष्ट दृष्टिकोण इस प्रकार अब तक:

1) एक द्विआधारी साथी संभाजक है, और (स्मृति के उपयोग दक्षता बलिदान 2 आकार के एक शक्ति से आगे निकलने)। - यह होगा (जैसा कि मैं समझता हूं) प्रत्येक ऑर्डर/बिन के लिए एक बाइनरी पेड़ की आवश्यकता होती है ताकि रीचिंग के लिए तेज़ दोस्त-ब्लॉक लुकअप के लिए मेमोरी एड्रेस द्वारा क्रमबद्ध मुक्त नोड्स को स्टोर किया जा सके।

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

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

-दोनों एल्गोरिदम को ऊंचाई-संतुलित बाइनरी पेड़ कोड की आवश्यकता होती है।

-Algorithm 2 में दो की शक्ति तक गोल करके स्मृति बर्बाद करने की आवश्यकता नहीं है।

- किसी भी मामले में, मेरे पास शायद इस आकार या छोटे ब्लॉक को ऑफ-लोड ब्लॉक करने के लिए नेस्टेड बिट फ़ील्ड द्वारा आवंटित 32-बाइट ब्लॉक का एक निश्चित बैंक होगा, जो बाह्य विखंडन के प्रति प्रतिरोधी होगा।

मेरे सवाल:

-Is वहाँ किसी भी कारण है कि दृष्टिकोण 1 दृष्टिकोण 2 से विखंडन के लिए और अधिक प्रतिरक्षा हो सकता है?

-क्या कोई विकल्प है कि मुझे याद आ रही है कि आवश्यकताओं को फिट कर सकते हैं?

Answer 1

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

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

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

Answer 2

आप ले सकते हैं एक आप की तरह किसी भी उद्देश्य के लिए मेरे आशीर्वाद के साथ http://www.mcdowella.demon.co.uk/buddy.html पर बडी प्रणाली संभाजक (असली के लिए इस्तेमाल कभी नहीं),। लेकिन मुझे नहीं लगता कि आपको एक समस्या है जिसे आसानी से स्मृति आवंटक में प्लग करके हल किया जाता है। लंबी संसाधन वाली उच्च अखंडता प्रणाली जिनके बारे में मैं परिचित हूं, अनुमानित संसाधन उपयोग है, प्रत्येक संसाधन के लिए 30+ पृष्ठ दस्तावेज़ों में वर्णित है (ज्यादातर सीपीयू और आई/ओ बस बैंडविड्थ - स्मृति आसान है क्योंकि वे हर बार स्टार्टअप पर उसी राशि आवंटित करते हैं और फिर कभी नहीं)।

आपके मामले में सामान्य चालों में से कोई भी नहीं - स्थैतिक आवंटन, मुफ्त सूचियां, ढेर पर आवंटन, काम पर दिखाया जा सकता है - कम से कम जैसा कि हमें बताया गया है - आपके पास एक लूआ है जो पृष्ठभूमि में घूमने के लिए तैयार है कौन जानता है कि रन टाइम पर क्या होता है - क्या होगा यदि यह सिर्फ एक लूप में हो जाता है जब तक यह खत्म नहीं हो जाता है?

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