एम्बेडेड सिस्टम के लिए एक अच्छा सी मेमोरी आवंटक क्या है?

Question

मेरे पास एक सिंगल थ्रेडेड, एम्बेडेड एप्लीकेशन है जो बहुत सारे छोटे और छोटे ब्लॉक (32-64 बी) आवंटित करता है और हटा देता है। एक कैश आधारित आवंटक के लिए सही परिदृश्य। और हालांकि मैं एक लिखने की कोशिश कर सकता था, यह संभवतः समय की बर्बादी होगी, और कुछ समाधान के रूप में परीक्षण और ट्यून नहीं किया जाएगा जो पहले से ही सामने की तरफ है।

तो इस परिदृश्य के लिए मैं सबसे अच्छा आवंटक क्या उपयोग कर सकता हूं?

नोट: मैं सिस्टम में लूआ वर्चुअल मशीन का उपयोग कर रहा हूं (जो आवंटन के 80 +% का अपराधी है), इसलिए मैं आवंटन प्रदर्शन बढ़ाने के लिए स्टैक आवंटन का उपयोग करने के लिए अपने कोड को त्रिकोणीय रूप से दोबारा नहीं कर सकता।

Answer 1

मैंने हाल ही में इस विषय पर कुछ शोध किया है, क्योंकि हमें स्मृति विखंडन के साथ कोई समस्या थी। अंत में हमने जीएनयू libc के कार्यान्वयन के साथ रहने का फैसला किया, और जहां आवश्यक हो वहां कुछ एप्लिकेशन-स्तर मेमोरी पूल जोड़ें। ऐसे अन्य आवंटक थे जिनके पास बेहतर विखंडन व्यवहार था, लेकिन हम वैश्विक स्तर पर मॉलोक को प्रतिस्थापित करने के लिए पर्याप्त आरामदायक नहीं थे। जीएनयू के पीछे एक लंबे इतिहास का लाभ है।

आपके मामले में यह उचित लगता है; मानते हुए कि आप वीएम को ठीक नहीं कर सकते हैं, उन छोटे आवंटन बहुत अपमानजनक हैं। मुझे नहीं पता कि आपका पूरा वातावरण क्या है, लेकिन आप कॉल को केवल वीएम पर मॉलोक/रीलोक/फ्री पर लपेटने पर विचार कर सकते हैं ताकि आप इसे छोटे पूल के लिए डिज़ाइन किए गए हैंडलर पर पास कर सकें।

Answer 2

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

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

प्रत्येक बफर के सामने एक सूचक होगा जो बफर को मुफ्त सूची में चेन करने के लिए उपयोग किया जाएगा। जब 100 बफर आवंटित किए गए थे, तो प्रत्येक बफर को मुफ्त सूची में एक साथ जोड़ा जाएगा। जब बफर उपयोग में था, तो सूचक को शून्य पर सेट किया जाएगा। हमने बफर के "ब्लॉक" की एक सूची भी बनाए रखी, ताकि हम प्रत्येक वास्तविक malloc'd बफर पर मुफ्त() को कॉल करके एक सरल सफाई कर सकें।

गतिशील बफर आकार के प्रबंधन के लिए, हमने बफर के आकार को बताते हुए प्रत्येक बफर की शुरुआत में एक size_t चर भी जोड़ा। इसका उपयोग यह पता लगाने के लिए किया गया था कि किस बफर ब्लॉक को बफर को वापस मुक्त करने के लिए वापस रखा गया था। हमारे पास malloc() और free() के लिए प्रतिस्थापन दिनचर्या थीं जो बफर आकार प्राप्त करने के लिए पॉइंटर अंकगणित करती थीं और फिर बफर को मुफ्त सूची में डाल देती थीं। हमने यह भी सीमा तय की कि हम कितने बफर प्रबंधित करते हैं। इस सीमा से बड़े बफर बस malloc'd थे और उपयोगकर्ता को पास कर दिया गया। हमारे द्वारा प्रबंधित संरचनाओं के लिए, हमने आवंटन और विशिष्ट संरचनाओं को मुक्त करने के लिए रैपर रूटीन बनाए।

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

Answer 3

हालांकि यह कुछ समय बाद मैंने यह पूछा था, मेरा अंतिम समाधान लोकी के छोटे ऑब्जेक्टएलोकेटर का उपयोग करना था, यह बहुत अच्छा काम करता था। सभी ओएस कॉलों से छुटकारा पा लिया और एम्बेडेड उपकरणों के लिए मेरे लुआ इंजन के प्रदर्शन में सुधार किया। बहुत अच्छा और सरल, और लगभग 5 मिनट के लायक काम!

Answer 4

version 5.1, Luacreating new states पर सेट होने के लिए custom allocator को अनुमति देने की अनुमति है।

Answer 5

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

Answer 6

मैंने 'बाइनरी दोस्त' प्रणाली का उपयोग vxworks के तहत अच्छे प्रभाव के लिए किया है। असल में, आप अपने अनुरोध को पकड़ने के लिए दो आकार के ब्लॉक की छोटी शक्ति प्राप्त करने के लिए आधे में ब्लॉक काटकर अपने ढेर का हिस्सा निकालते हैं, और जब ब्लॉक मुक्त होते हैं, तो आप विखंडन को कम करने के लिए एक साथ ब्लॉक को मर्ज करने के लिए पेड़ को पार कर सकते हैं। एक Google खोज आपको आवश्यक सभी जानकारी को बदलनी चाहिए।

Answer 7

मैं थोड़ा पार्टी के लिए देर हो रही है, लेकिन मैं सिर्फ मैं हाल ही में पाया जाता है और परीक्षण किया है एम्बेडेड प्रणाली के लिए बहुत ही कुशल स्मृति allocator साझा करना चाहते हैं: https://github.com/dimonomid/umm_malloc

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

मुझे डिफ़ॉल्ट आवंटक के साथ विखंडन से गंभीरता से पीटा गया था: मेरी परियोजना अक्सर कई बाइट्स से कई सैकड़ों बाइट्स तक विभिन्न आकारों के ब्लॉक आवंटित करती है, और कभी-कभी मुझे 'स्मृति से बाहर' त्रुटि का सामना करना पड़ता है। मेरे पीआईसी 32 डिवाइस में कुल 32 के रैम है, और ढेर के लिए 8192 बाइट्स का उपयोग किया जाता है। विशेष पल में 5K से अधिक मुक्त मेमोरी है, लेकिन विखंडन के कारण डिफ़ॉल्ट आवंटक में लगभग 700 बाइट्स की अधिकतम गैर-खंडित मेमोरी ब्लॉक है। यह बहुत बुरा है, इसलिए मैंने अधिक कुशल समाधान की तलाश करने का फैसला किया।

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

लेकिन इस बार, मैं भाग्यशाली हूँ: http://hempeldesigngroup.com/embedded/stories/memorymanager/

मैं मुक्त स्मृति की 5K के साथ इस स्मृति allocator की कोशिश की तो बिल्कुल एक ही स्थिति में, यह एक से अधिक 3800 बाइट्स ब्लॉक: मैं इस एक मिल गया है ! यह मेरे लिए इतना अविश्वसनीय था (700 बाइट्स की तुलना में), और मैंने कड़ी मेहनत की: डिवाइस ने 30 घंटे से अधिक समय तक काम किया। कोई स्मृति रिसाव नहीं है, सबकुछ काम करता है क्योंकि इसे काम करना चाहिए। मुझे फ्रीआरटीओएस रिपोजिटरी में यह आवंटन भी मिला: http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg=1041#, और यह तथ्य umm_malloc की स्थिरता का एक अतिरिक्त सबूत है। तो मैंने पूरी तरह से umm_malloc पर स्विच किया, और मैं इसके साथ काफी खुश हूं।

मुझे बस इसे थोड़ा बदलना पड़ा: मैक्रो UMM_TEST_MAIN परिभाषित नहीं होने पर कॉन्फ़िगरेशन थोड़ा गड़बड़ था, इसलिए, मैंने जिथब रिपोजिटरी बनाई है (लिंक इस पोस्ट के शीर्ष पर है)। अब, उपयोगकर्ता निर्भर विन्यास अलग फ़ाइल umm_malloc_cfg में संग्रहीत है।एच

मुझे इस आवंटक में लागू एल्गोरिदम में गहराई से नहीं मिला है, लेकिन इसमें एल्गोरिदम का बहुत विस्तृत स्पष्टीकरण है, इसलिए रुचि रखने वाला कोई भी व्यक्ति umm_malloc.c फ़ाइल के शीर्ष पर देख सकता है। कम से कम, "बिनिंग" दृष्टिकोण को कम विखंडन में बड़ा लाभ देना चाहिए: http://g.oswego.edu/dl/html/malloc.html

मेरा मानना ​​है कि माइक्रोकंट्रोलर के लिए कुशल स्मृति आवंटक की आवश्यकता वाले किसी भी व्यक्ति को कम से कम इसे आजमाएं।

Answer 8

मैं एक सी मेमोरी आवंटक लिख रहा हूं जिसे टिनिमम कहा जाता है जिसका उद्देश्य ढेर को डिफ्रैगमेंट करने और स्मृति का पुन: उपयोग करने में सक्षम होना है। इसे देखें:

https://github.com/vitiral/tinymem

नोट: इस परियोजना जंग कार्यान्वयन पर काम करने के लिए बंद कर दिया गया:

https://github.com/vitiral/defrag-rs

इसके अलावा, मैं नहीं umm_malloc के पहले सुना था। दुर्भाग्यवश, यह विखंडन से निपटने में सक्षम नहीं प्रतीत होता है, लेकिन यह निश्चित रूप से उपयोगी दिखता है। मुझे इसे देखना होगा।