اكتب مدير الذاكرة الجيد الخاص بك

يوم جيد ، أيها القارئ. ربما تكون قد قرأت بالفعل مقالاتي السابقة ، وأنت تعلم أنني أكتب نظام التشغيل الخاص بي. اليوم سنتحدث ، وننظر في خوارزمية بسيطة وسريعة إلى حد ما لإدارة الذاكرة - يعد مدير الذاكرة جزءًا مهمًا من نظام التشغيل ، لأن العمل السريع والموثوق وغير المُهدر مع الذاكرة هو مفتاح نظام التشغيل الجيد.
كنت أبحث عن أفكار بسيطة وكافية للمدير في كل من Runet والمواقع باللغة الإنجليزية - ما زلت لا أستطيع العثور على أي مقالات جيدة حول أداة تخصيص كافية ، وليس O (N). حسنًا ، اليوم سننظر في فكرة أفضل لمدير الذاكرة ، وأضع الاستمرارية تحت قطة.

النظرية

من wiki: Memory manager - جزء من برنامج كمبيوتر (تطبيق ونظام تشغيل على حد سواء) يعالج طلبات تخصيص ذاكرة الوصول العشوائي (RAM) وإصدارها أو يطلب (بالنسبة إلى بعض هياكل الكمبيوتر) تضمين منطقة ذاكرة معينة في مساحة عنوان المعالج.

أقترح أيضًا قبل متابعة قراءة هذا المقال .

تخصيص Watermak

حسنًا ، من المحتمل أن يكون أبسط من بين كل التخصيصات هو تخصيص العلامة المائية. جوهرها هو ما يلي تقريبًا: يتم تقسيم الذاكرة بأكملها إلى كتل ، تحتوي الكتلة على رأس يحتوي على حجم هذا وكتلة سابقة ، وحالة الكتلة (مشغول / مجاني) ، ومعرفة عنوان الكتلة ، يمكننا الحصول على عنوان الكتلة التالية والسابقة لـ O (1).

تخصيص الذاكرة

لتخصيص الذاكرة ، نحتاج ببساطة إلى تشغيل الكتل ، والبحث عن كتلة يكون حجمها أكبر من أو يساوي حجم الذاكرة المطلوبة للتخصيص. كما فهمت بالفعل ، فإن السلوك المقارب لـ O (N) سيء.

الافراج عن الذاكرة

لتحرير الذاكرة ، يكفي أن نضبط حالة الكتلة على أنها "حرة" - O (1) - فائقة!

ولكن ، كما فهمت ، يمكن أن تبدأ الثقوب في تشكيل تجزئة كتلتين أو أكثر من التجزئة ، وعند إطلاقها ، يمكن عرض الكتل المجاورة ، وإذا كانت واحدة أو اثنتان حرتان ، فقم بدمجها في واحدة.

مخصص لوغاريتمي

نحن نعلم أننا بحاجة إلى البحث فقط بين الكتل المجانية. يعمل التشغيل فقط مجانًا على تحسين السرعة في المتوسط ​​مرتين ، لكنه لا يزال خطًا. حسنًا ، لماذا يجب أن نركض في جميع الكتل ، نبحث عن الحجم ، إذا كان يمكننا تنظيم شجرة من كتل مجانية! في البداية ، لدينا كتلة مجانية واحدة فقط ، ثم نضيف كتل مجانية إلى شجرة البحث الثنائية ، وسيكون المفتاح هو حجم الكتلة. وبالتالي ، من أجل تخصيص الذاكرة ، يكفي أن نجد كتلة في شجرة بحجمها أكبر من أو نحتاج إلى ما نحتاج إليه. نفعل ذلك بهدوء من أجل O (سجل N) ، فقط نزول الشجرة. علاوة على ذلك ، إما أن نقطع الكتلة إلى قسمين ، أو نعطيها بالكامل إلى الشخص الذي طلب الذاكرة. بعد ذلك ، نزيل الكتلة من الشجرة لـ O (1). وإذا لزم الأمر ، أدخل بقية الكتلة مرة أخرى خلف O (سجل N). للإفراج ، نحتاج فقط إلى إدراج الكتلة مرة أخرى ، ولا تنسى تجزئة.

من المنطقي ألا تحتاج إلى استخدام شجرة بسيطة ، أو تحتاج إلى استخدام شجرة ذاتية التوازن ، أو Red-Black أو AVL. يمكنك تخزين شجرة الكتلة في صفيف ثابت ، أو يمكنك معرفة كيفية القيام بذلك بشكل مختلف.

في الواقع ، الكود:

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)); } 

حظا سعيدا والاختراق الأخلاقي! أي نقد موضوعي أمر مرحب به ، والغرض من المقالة لا يعني القول بأنه نوع من التخصيص ، ولكن مجرد الحديث عن أداة تخصيص ستكون أفضل من التطبيقات الغبية للمخصصات البسيطة.