क्या होता है जब स्मृति ब्लॉक के लिए अनुरोध होता है जो 2 की शक्ति नहीं है?

Question

मान लीजिए कि हम आकार n के स्मृति ब्लॉक के लिए एक malloc अनुरोध करते हैं जहां 2^के! = N के लिए 0> n। मॉलोक हमें उस अनुरोधित मेमोरी ब्लॉक के लिए स्थान देता है लेकिन पृष्ठ से बने रहने वाले बफर को कैसे नियंत्रित किया जाता है। मैंने पढ़ा है पृष्ठ आमतौर पर स्मृति की ब्लॉक हैं जो दो की शक्तियां हैं।

विकी राज्यों निम्नलिखित:

Like any method of memory allocation, the heap will become fragmented; that is, 
there will be sections of used and unused memory in the allocated 
space on the heap. A good allocator will attempt to find an unused area 
of already allocated memory to use before resorting to expanding the heap. 

तो मेरे सवाल है कि कैसे इस पर नज़र रखी है?

संपादित करें: malloc का उपयोग करते समय अप्रयुक्त स्मृति को ट्रैक किया जाता है?

Answer 1

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

यह कुछ सरल संभावनाओं से अधिक एक सिंहावलोकन है: http://www.osdcom.info/content/view/31/39/

यह विकिपीडिया प्रविष्टि के ऊपर एक सहित कई दिलचस्प लिंक, है: http://en.wikipedia.org/wiki/Dynamic_memory_allocation#Implementations

एक अंतिम टिप्पणी के रूप में, googling "malloc कार्यान्वयन" एक ढेर जाता (इरादा पेंच) मूल्यवान लिंक के।

Answer 2

यह कार्यान्वयन से कार्यान्वयन से बहुत भिन्न होता है। कुछ लोग अंतरिक्ष को बर्बाद करते हैं, कुछ उप-विभाजित पृष्ठों तक जब तक वे अनुरोधित आकार (या इसके करीब) प्राप्त नहीं करते हैं & सी।

आप जिज्ञासा से बाहर पूछ रहे हैं, तो मैं सुझाव है कि आप प्रश्न में लागू करने के लिए स्रोत कोड,

पढ़ें क्योंकि यह प्रदर्शन चिंताओं से, यह बेंचमार्क करने की कोशिश और देखो क्या होता।

Answer 3

एक मानक बीएसडी शैली स्मृति allocator मूल रूप से इस तरह काम करता है:

• यह कश्मीर < = 12 (उदाहरण के लिए) के लिए 2^कश्मीर आकार के लिए पूर्व आबंटित स्मृति ब्लॉक के एक लिंक्ड सूची रहता है।
• हकीकत में, किसी दिए गए के लिए प्रत्येक सूची अलग-अलग क्षेत्रों से स्मृति-ब्लॉक से बना है, नीचे देखें।
• एन बाइट्स के लिए एक मॉलोक अनुरोध एन ', निकटतम 2^के> = एन की गणना करके सर्विसेज किया जाता है, फिर के लिए सूची में पहले क्षेत्र को देखकर और फिर मुक्त- दिए गए क्षेत्र के लिए सूची।
• जब आकार 2^के लिए कोई प्री-आवंटित मेमोरी ब्लॉक नहीं है, तो क्षेत्र आवंटित किया जाता है, एक क्षेत्र निरंतर स्मृति का कुछ बड़ा टुकड़ा होता है, स्मृति का 4kB टुकड़ा कहता है। स्मृति का यह टुकड़ा तब टुकड़ों में कटा हुआ होता है जो 2^के बाइट्स होते हैं। निरंतर स्मृति क्षेत्र की शुरुआत में पुस्तक-रखरखाव की जानकारी होती है जैसे क्षेत्र के भीतर नि: शुल्क ब्लॉक की लिंक की गई सूची कहां मिलती है। बिटमैप का भी उपयोग किया जा सकता है, लेकिन एक लिंक्ड सूची में आमतौर पर बेहतर कैश व्यवहार होता है (आप चाहते हैं कि अगला आवंटित ब्लॉक पहले से ही कैश में मौजूद स्मृति को वापस कर दे)।
• क्षेत्रों का उपयोग करने का कारण यह है कि मुफ्त (पीटीआर) कुशलतापूर्वक कार्यान्वित किया जा सकता है। इस उदाहरण में पीआरटी & 0xfffff000 क्षेत्र की शुरुआत में इंगित करता है जिसमें पुस्तक-रखरखाव संरचनाएं होती हैं और मेमोरी ब्लॉक को क्षेत्र में वापस लिंक करना संभव बनाता है।
• बीएसडी आवंटक हमेशा मेमोरी ब्लॉक 2^के आकार में लौटकर अंतरिक्ष बर्बाद कर देगा, लेकिन यह मुक्त सूची रखने के लिए ब्लॉक की स्मृति का पुन: उपयोग कर सकता है, जो एक अच्छी संपत्ति है। इसके अलावा आवंटन तेजी से तेज है। ऊपर सामान्य विचार करने के लिए

संशोधन में शामिल हैं:

• बड़े आवंटन के लिए अनाम mmap का उपयोग करना। यह बड़े मॉलॉक्स को संभालने के लिए काम को कर्नेल में बदल देता है और इन मामलों में बहुत सारी स्मृति बर्बाद करने से बचाता है।
• मॉलोक के जीएनयू संस्करण में गैर-शक्ति-दो बाल्टी के लिए विशेष मामले हैं। बीएसडी आवंटक में निहित कुछ भी नहीं है जिसके लिए 2^के मेमोरी ब्लॉक लौटने की आवश्यकता है, केवल पूर्व परिभाषित बाल्टी आकार हैं। जीएनयू आवंटक में अधिक बाल्टी होती है और इस प्रकार कम जगह बर्बाद होती है।
• धागे के बीच स्मृति साझा करना एक मुश्किल विषय है। आवंटन के दौरान लॉक-विवाद एक महत्वपूर्ण विचार है, इसलिए उदाहरण के लिए जीएनयू आवंटक में उत्सुकता से अतिरिक्त क्षेत्रों को दिए गए बाल्टी आकार के लिए अलग-अलग धागे के लिए तैयार किया जाएगा यदि यह कभी आवंटन के दौरान लॉक-विवाद का सामना करता है।