अपनी खुद की अच्छी मेमोरी मैनेजर लिखना

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

सिद्धांत

विकी से: मेमोरी मैनेजर - एक कंप्यूटर प्रोग्राम (एप्लिकेशन और ऑपरेटिंग सिस्टम दोनों) का एक हिस्सा जो प्रोसेसर के एड्रेस स्पेस में दिए गए मेमोरी एरिया को शामिल करने के लिए रैम के आवंटन और रिलीज के लिए अनुरोध करता है या (कुछ कंप्यूटर आर्किटेक्चर के लिए) अनुरोध करता है।

मैं इस लेख को पढ़ना जारी रखने से पहले सुझाव भी देता हूं।

वाटरमार्क आवंटनकर्ता

ठीक है, शायद सभी आवंटनकर्ताओं में से सबसे सरल वॉटरमार्क एलोकेटर है। इसका सार लगभग निम्नलिखित है: पूरी मेमोरी को ब्लॉक में विभाजित किया गया है, ब्लॉक में एक हेडर है जिसमें यह और पिछले ब्लॉक का आकार है, ब्लॉक की स्थिति (व्यस्त / मुक्त), ब्लॉक के पते को जानकर, हम O (1) के लिए अगले और पिछले ब्लॉक का पता प्राप्त कर सकते हैं।

मेमोरी आवंटन

मेमोरी आवंटित करने के लिए, हमें बस ब्लॉकों के माध्यम से चलने की जरूरत है, और एक ब्लॉक की तलाश करें जिसका आकार आवंटन के लिए आवश्यक मेमोरी के आकार से अधिक या बराबर है। जैसा कि आप पहले ही समझ चुके हैं, O (N) का स्पर्शोन्मुख व्यवहार बुरा है।

मेमोरी रिलीज़

मेमोरी को फ्री करने के लिए, ब्लॉक की स्थिति को "फ्री" के रूप में सेट करना हमारे लिए पर्याप्त है - ओ (1) - सुपर!

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

लॉगरिदमिक एलोकेटर

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

यह तर्कसंगत है कि आपको एक साधारण पेड़ का उपयोग करने की आवश्यकता नहीं है, आपको स्व-संतुलन वाले पेड़, रेड-ब्लैक या एवीएल का उपयोग करने की आवश्यकता है। आप एक स्थिर सरणी में ब्लॉक ट्री स्टोर कर सकते हैं, या आप यह पता लगा सकते हैं कि इसे अलग तरीके से कैसे किया जाए।

वास्तव में, कोड:

char * malloc(size_t size) { if (!size) { return 0; } char * addr = 0; int i; for (i = 0; i < allocationAvlTree.size; ) { int r; node_t *n; n = &allocationAvlTree.nodes[i]; /* couldn't find it */ if (!n->key) { return NULL; } r = allocationAvlTree.cmp(n->key, size); if (r <= 0) { //We're lucky today. //Get memory block header alloc_t * block = (size_t)n->val - sizeof(alloc_t); //Set to used block->status = 1; //Set size block->size = size; alloc_t * next = (size_t)n->val + size; next->prev_size = size; next->status = 0; next->size = n->key - size - 16; avltree_remove(&allocationAvlTree, n->key, n->val); if (n->key - size - 16) avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t)); memset((size_t)block + sizeof(alloc_t), 0, block->size); block->signature = 0xDEADBEEF; unlockTaskSwitch(); return (size_t)block + sizeof(alloc_t); } else if (r > 0) i = __child_r(i); else assert(0); } return 0; } void free(void * mem) { if (!mem) return; //Get current alloc alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t)); if (alloc->signature != 0xDEADBEEF) return; alloc->status = 0; alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size); if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size) { //Merge blocks if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) { left->size += sizeof(alloc_t) + alloc->size; alloc = left; } else assert(0); } alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size; if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF) { if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t))) alloc->size += sizeof(alloc_t) + right->size; else assert(0); } avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t)); } 

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