تطوير نظام التشغيل المتماثل يونيكس - كومة (4)

في المقالة السابقة ، قمنا بتطبيق سجل نظام kernel. الآن حان الوقت لتنفيذ مدير ذاكرة ديناميكي.

جدول المحتويات

1. بناء نظام (جعل ، مجلس التعاون الخليجي ، الغاز). التمهيد الأولي (متعدد التمهيد). إطلاق (qemu). مكتبة C (strcpy ، memcpy ، strext).
2. مكتبة C (sprintf ، strcpy ، strcmp ، strtok ، va_list ...). بناء المكتبة في وضع kernel ووضع تطبيق المستخدم.
3. سجل نظام النواة. ذاكرة الفيديو الإخراج إلى المحطة (kprintf ، kpanic ، kassert).
4. الذاكرة الديناميكية ، الكومة (kmalloc ، kfree).
5. تنظيم الذاكرة والتعامل مع المقاطعة (GDT ، IDT ، PIC ، syscall). الاستثناءات.
6. الذاكرة الظاهرية (دليل الصفحة وجدول الصفحة).
7. العملية. المجدول. تعدد المهام. مكالمات النظام (القتل ، الخروج ، ملاحظة).
8. نظام ملفات kernel (initrd) ، قزم ، وداخله. مكالمات النظام (exec).
9. برامج تشغيل الأجهزة الشخصية. مكالمات النظام (ioctl ، fopen ، fread ، fwrite). مكتبة C (fopen ، fclose ، fprintf ، fscanf).
10. شل كبرنامج كامل للنواة.
11. وضع حماية المستخدم (ring3). قسم حالة المهمة (tss).

ذاكرة النواة الديناميكية. حفنة

سوف تبدو واجهة كومة kernel بالشكل التالي:

void *kmalloc(size_t size); void kfree(void *addr); 

نظرًا لعدم وجود أكوام حتى الآن ، يجب تخزين سجلات مناطق الذاكرة المشغولة والمجانية.
في مجموعة من الحجم المحدود. أصغر البعد ، وانخفاض قدرة كومة من قبل
شظايا صغيرة. على نظام Linux ، على سبيل المثال ، يتم تخزين العديد من هياكل kernel في حالة قابلة لإعادة الاستخدام
الذاكرة التي لا تغير الحجم عند إصدارها (لوح). لكننا ما زلنا بعيدين عن هذا ،
لأن التنمية هي عملية تكرارية.

أي عنصر ينوي أن يكون عنصرًا في قائمة منظمة عبر صفيف
المطلوبة لتنفيذ واجهة.

 struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed); 

لا توجد واجهات في C ، لكنها ليست هناك حاجة. نحن ببساطة نرمي مؤشر أي كائن إلى النوع struct slist_head_t * إذا كان هذا الكائن يبدو فعليًا مثل هذا:

 struct my_list_entry_t { struct slist_head_t list_head; ... } 

ولكن حتى تعرف الخوارزمية المعممة البعد الخاص بالصفيف الذي سيتم تخزين القائمة فيه
وحجم عنصرها ، العنصر الأول والأخير من القائمة وعنوان المصفوفة التي
يتم تخزين قائمة ، ستحتاج كل وظيفة من قائمة التشغيل إلى مؤشر آخر
إلى بنية تعريف القائمة:

 struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; }; 

سوف تبدو وظائف تشغيل القائمة كما يلي:

 struct slist_head_t *slist_insert_entry_after(struct slist_definition_t *list, struct slist_head_t *pos); struct slist_head_t *slist_insert_entry_before(struct slist_definition_t *list, struct slist_head_t *pos); void slist_delete_entry(struct slist_definition_t *list, struct slist_head_t *entry); 

إدراج خوارزمية الوظيفة:
العثور على فتحة الحرة في مجموعة.
املأه بعنصر جديد.
صحح مؤشرات عناصر القائمة المجاورة منطقياً (وليس ماديًا).
علامة الفتحة مشغول.
ضبط بداية ونهاية القائمة.

خوارزمية الوظيفة المراد إزالتها من القائمة:
صحح مؤشرات عناصر القائمة المجاورة منطقياً (وليس ماديًا).
ضبط بداية ونهاية القائمة.
وضع علامة الفتحة مجانًا.

يتم وصف الذاكرة الديناميكية بقائمة تحتوي على العناصر التالية:

 struct kheap_entry_t { struct slist_head_t list_head; /* should be at first */ size_t addr; /* physical address */ size_t size; /* memory block size */ bool is_buzy; /* whether block used */ } attribute(packed); 

يشبه الصفيف الذي يصف الذاكرة الديناميكية من هذه السجلات:

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES]; 

يبدو تعريف قائمة مناطق الذاكرة كما يلي:

 struct slist_definition_t kheap_list = { .head = null, .tail = null, .slot_size = sizeof(struct kheap_entry_t), .slots = KHEAP_MAX_ENTRIES, .base = (size_t)kheap_blocks}; 

لذلك ، لقد وصفنا الذاكرة الديناميكية. كل الذاكرة ضمن نطاق معين
ينقسم إلى كتل من حجم التعسفي ، كل منها يمكن أن تكون إما فارغة ،
إما مشغول. بالإضافة إلى ذلك ، يتم وصف كل كتلة بواسطة عنصر صفيف مع العلم is_valid = true ،
وهو عنصر القائمة.

الآن النظر في أبسط خوارزمية مخصص كومة الذاكرة المؤقتة (kmalloc):
إذا لم تكن هناك كتل مجانية ، فحدد كتلة جديدة بالحجم المطلوب (ولكن ليس أكثر من الحد الأقصى لحجم الكومة).

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

 /* * Api - Kernel memory alloc */ extern void* kmalloc(size_t size) { struct kheap_entry_t* current_data = null; struct slist_head_t* current = null; struct slist_head_t* head = kheap_list.head; assert(size > 0); /* try to use free block */ for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->is_buzy) { continue; } /* check size is not enough */ if (current_data->size < size) { /* try to ask contribution from free left sibling */ if (current->prev != null) { /* left sibling has found */ struct slist_head_t* sibling = current->prev; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether left sibling is free */ if (!sibling_data->is_buzy) { /* ask lack from left sibling */ size_t lack = size - current_data->size; sibling_data->size -= lack; current_data->addr -= lack; current_data->size += lack; assert(current_data->size == size); /* whether left sibling is collapsed */ if (sibling_data->size == 0) { slist_delete_entry(&kheap_list, sibling); } /* occupy block */ current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to extend borders */ if (current->next == null) { size_t heap_end_addr = current_data->addr + current_data->size; size_t lack = size - current_data->size; /* check free memory size is enought */ if (heap_end_addr + lack < KHEAP_END_ADDR) { /* occupy block */ current_data->size += lack; current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } } else { /* occupy block */ current_data->is_buzy = true; size_t surplus = current_data->size - size; bool is_sibling_bizy = false; /* try to contribute free right sibling */ if (current->next != null) { /* sibling has found */ struct slist_head_t* sibling = current->next; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether sibling is free */ is_sibling_bizy = sibling_data->is_buzy; if (!is_sibling_bizy) { /* give surplus to right sibling */ current_data->size -= surplus; sibling_data->addr -= surplus; sibling_data->size += surplus; assert(current_data->size == size); } } /* try to give surplus to new right sibling */ if (current->next == null || is_sibling_bizy) { { struct slist_head_t* new_sibling; new_sibling = slist_insert_entry_after(&kheap_list, current); struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)new_sibling->data; if (new_sibling != null) { /* give surplus to new right sibling */ assert((size_t)new_sibling == (size_t)sibling_data); current_data->size -= surplus; assert(current_data->size > 0); sibling_data->is_buzy = false; sibling_data->addr = current_data->addr + current_data->size; sibling_data->size = surplus; } } } assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to alloc new block */ size_t heap_end_addr = KHEAP_START_ADDR; /* calculate heap end address */ if (kheap_list.tail) { current = kheap_list.tail; current_data = (struct kheap_entry_t*)current->data; heap_end_addr = current_data->addr + current_data->size; } /* check free memory size is enought */ if (heap_end_addr + size >= KHEAP_END_ADDR) { abort("heap size exceeded\n"); } /* allocate new heap memory block */ struct slist_head_t* tail = kheap_list.tail; current = slist_insert_entry_after(&kheap_list, kheap_list.tail); current_data = (struct kheap_entry_t*)current->data; assert((size_t)current == (size_t)current_data); current_data->addr = heap_end_addr; current_data->size = size; current_data->is_buzy = true; assert(current->next == null); assert(current->prev == tail); assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; } 

ستكون خوارزمية الذاكرة الخالية متشابهة (kfree):
ابحث عن كتلة يبدأ عنوانها بالعنوان المراد تحريره. تأكد من أنه مشغول. اجعلها مجانية.

إذا كان هناك جار حر إلى اليمين أو اليسار لتوحيد معه في كتلة واحدة.

 /* * Api - Kernel memory free */ extern void kfree(void* addr) { struct slist_head_t* current = null; struct kheap_entry_t* current_data = null; struct slist_head_t* head = kheap_list.head; for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->addr == (size_t)addr && current_data->is_buzy) { struct slist_head_t* prev = current->prev; struct slist_head_t* next = current->next; struct kheap_entry_t* prev_data = prev != null ? (struct kheap_entry_t*)prev->data : null; struct kheap_entry_t* next_data = next != null ? (struct kheap_entry_t*)next->data : null; /* free block */ current_data->is_buzy = false; /* try to merge with free left sibling */ if (prev != null && !prev_data->is_buzy) { prev_data->size += current_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)current); } /* try to merge with free right sibling */ if (next != null && !next_data->is_buzy) { current_data->size += next_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)next); } return; } } abort("invalid address to free\n", addr); } 

هذا كل شيء. حتى في المرة القادمة!

مراجع

الآن ، افتح الفيديو التعليمي
ومشاهدة مستودع بوابة في وقت واحد (تحتاج إلى فرع الدرس 4)

مراجع

1. جيمس مولوي. لفة نظام التشغيل الخاص بك UNIX استنساخ.
2. الأسنان. مجمع ل DOS ، ويندوز ، يونيكس
3. كلاشينكوف. المجمع سهل!
4. Tanenbaum. أنظمة التشغيل. التنفيذ والتطوير.
5. روبرت لوف. نواة لينكس وصف عملية التطوير.