تعدد المهام Microkernel تطوير نظام التشغيل - المجدول

بعد أن تقرأ الخطوات الأساسية لكتابة نواة Hello World من سلسلة المقالات المتوفرة على Habré ، فقد حان الوقت للبدء في التطوير الجاد لأكثر الأدوات الأساسية: أداة تخصيص الكومة وجدولة.

مهم :
1. هذه السلسلة من الدروس للمبتدئين. الهدف هو تشكيل صورة شاملة للعالم. لفترة طويلة جدا كان لدي نظرية Tanenbaum في رأسي ولم أستطع ربطها بالممارسة. بالنسبة لأولئك الذين لديهم نفس الشيء - أهدي هذا المقال.
2. الكود هو أبسط وأغبى ، ولكن واضح قدر الإمكان. هدفي هو أن أعطيك تفهمًا حتى تتمكن من كتابة نواة خاصة بك ، أكثر برودة بكثير من ذلك.
3. سأنشر الريبو بمجرد أن أعتبره جاهزًا لمجموعة واسعة. أكتب جزءًا صغيرًا وأقوم بتصحيح وتصوير فيديو تعليمي. ليس لدي منتج نهائي.

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

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

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

دعنا نذهب!

تحتوي هذه المقالة على لقطة فيديو تعليمي في استوديو منزلي. إنه مخصص مباشرة للرمز.

دعنا نبدأ مع تطوير مدير الكومة.

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

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

 struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed); 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 kheap_entry_t { struct slist_head_t list_head; /* static (array placed) list */ 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 }; 

في بداية بنية kheap_entry_t هو slist_head_t ، والذي يسمح لك بإلقاء نوع سجل الكومة بشكل غير مؤلم على عنصر قائمة.

الآن النظر في أبسط خوارزمية مخصص كومة الذاكرة المؤقتة (kmalloc):

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

ستكون خوارزمية الذاكرة الخالية متشابهة (kfree):

1. ابحث عن كتلة يبدأ عنوانها بالعنوان المراد تحريره. تأكد من أنه مشغول. اجعلها مجانية.
2. إذا كان هناك جار حر إلى اليمين أو اليسار لتوحيد معه في كتلة واحدة.

سوف تركز المقالة التالية على تنفيذ خوارزمية الكومة.

دعنا نكتب أبسط جدولة. ستبدو المهمة هكذا:

 struct task_t { struct clist_head_t list_head; /* cyclic list */ u_short tid; /* task id */ struct gp_registers_t gp_registers; /* general purpose registers */ struct op_registers_t op_registers; /* other purpose registers */ struct flags_t flags; /* processor flags */ u_int time; /* time of task execution */ bool reschedule; /* whether task need to be rescheduled */ u_short status; /* task status */ int msg_count_in; /* count of incomming messages */ struct message_t msg_buff[TASK_MSG_BUFF_SIZE]; /* task message buffer */ void *kstack; /* kernel stack top */ void *ustack; /* user stack top */ } attribute(packed); struct clist_definition_t task_list = { .head = null, .slot_size = sizeof(struct task_t) }; 

نحن نعلم بالفعل كيفية تخصيص الذاكرة وبالتالي تنظيم المهام كقائمة رنين. لذلك ، من الأسهل القيام بالمهمة التالية بالنسبة للمهمة الحالية بالحالة المطلوبة (سنستخدم حالة TASK_RUNNING إذا تم تنفيذ المهمة). بادئ ذي بدء ، سوف نفترض أن جميع المهام يتم تنفيذها في حلقة حماية kernel (من الأسهل تصحيح برنامج الجدولة) والمتابعة باستخدام حزمة واحدة. في المستقبل سوف نقوم بربط TSS.

قمنا بتسوية المهام ، والآن التخطيط نفسه. إضافة معالج مؤقت إلى IDT وتمكين مقاطعة خط IRQ المطلوب في الموافقة المسبقة عن علم. من خلال مقاطعة المؤقت (وفي نهاية رمز تهيئة kernel) ، ننقل التحكم إلى المجدول ، ونمرر عنوان الإرجاع وعنوان السجلات المحفوظة مسبقًا من مقاطعة المؤقت:

 /* * Handle IRQ0 * void asm_ih_timer(unsigned long *addr) */ asm_ih_timer: cli pushal mov %esp,%ebp mov %ebp,%ebx pushl %ebx # &reg add $32,%ebx pushl %ebx # &ret addr call ih_timer mov %ebp,%esp popal sti iretl 

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

  /* save task state */ current_task->op_registers.eip = *ret_addr; current_task->op_registers.cs = *(u16 *)((size_t)ret_addr + 4); *(u32 *)(&current_task->flags) = *(u32 *)((size_t)ret_addr + 6) | 0x200; current_task->op_registers.u_esp = (size_t)ret_addr + 12; current_task->gp_registers.esp = current_task->op_registers.u_esp; memcpy(&current_task->gp_registers, (void *)reg_addr, sizeof(struct gp_registers_t)); 

نحن نأخذ عنوان الرصة للمهمة الجديدة ونشكل إطار إرجاع للأمر iret هناك. ثم نسميه وظيفة المجمّع لتبديل السياق.

  /* prepare context for the next task */ next_task->op_registers.u_esp -= 4; *(u32 *)(next_task->op_registers.u_esp) = (*(u16 *)(&next_task->flags)) | 0x200; next_task->op_registers.u_esp -= 4; *(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.cs; next_task->op_registers.u_esp -= 4; *(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.eip; next_task->gp_registers.esp = next_task->op_registers.u_esp; next_task->op_registers.u_esp -= sizeof(struct gp_registers_t); memcpy((void *)next_task->op_registers.u_esp, (void *)&next_task->gp_registers, sizeof(struct gp_registers_t)); /* update current task pointer */ current_task = next_task; /* run next task */ asm_switch_context(next_task->op_registers.u_esp); 

يبدو تبديل السياق نفسه كما يلي:

 # # Switch context # void asm_switch_context(u32 esp) # asm_switch_context: mov 4(%esp),%ebp # ebp = esp mov %ebp,%esp popal sti iretl 

المجدول جاهز.

انظر الكود الكامل في الفيديو التعليمي المرفق بالمقال. إنه لا يأخذ في الاعتبار المجدول فحسب ، ولكن أيضًا عملية تحميل وتجميع وتكوين IDT لأولئك الذين نسوا: