محاضرة نظم التشغيل السادسة PDF

‫نظم التشغيل‬ ‫المحاضرة السادسة‬ ‫محتويات المحاضرة السابقة‪:‬‬ ‫‪ ‬مفهوم المهمة‪.‬‬ ‫‪ ‬حاالت المهمة‪.‬‬ ‫‪ ‬كتلة تحكم المهمات‪.‬‬ ‫محتويات المحاضرة السادسة‪:‬‬ ‫جدولة المهام‬ ‫‪‬‬ ‫خوارزميات الجدولة وانواعها‬ ‫‪‬‬ ‫امثلة للخوارزميات‬ ‫‪‬‬...

‫نظم التشغيل‬ ‫المحاضرة السادسة‬ ‫محتويات المحاضرة السابقة‪:‬‬ ‫‪ ‬مفهوم المهمة‪.‬‬ ‫‪ ‬حاالت المهمة‪.‬‬ ‫‪ ‬كتلة تحكم المهمات‪.‬‬ ‫محتويات المحاضرة السادسة‪:‬‬ ‫جدولة المهام‬ ‫‪‬‬ ‫خوارزميات الجدولة وانواعها‬ ‫‪‬‬ ‫امثلة للخوارزميات‬ ‫‪‬‬  ‫جدولة المهام ‪Process Scheduling‬‬ ‫ان البرمجة المتعددة تستخدم لزيادة كفاءة النظام عندما تكون‬ ‫هنالك مهمة قد توقفت عن التنفيذ فى إنتظار متطلبات‬ ‫إدخال‪/‬إخراج ‪.‬فتدخل مهمة اخرى بدال عنها للتنفيذ ‪.‬‬ ‫السؤال ‪ :‬كيف يتم إختيار هذه المهمة من مجموعة‬ ‫مهمات اخرى؟‬ ‫االجابة ‪ :‬سياسة الجدولة هى التى تحل هذا اإلشكال مع مراعاة‬ ‫عدة مقاييس ومن هذه المقاييس شائعة االستخدام ‪:‬‬ ‫‪.1‬إستخدام المعالج ‪ :‬وهو الزمن الفعلى إلستخدام المعالج‬  ‫جدولة المهام ‪Process Scheduling‬‬ ‫‪.2‬الطاقة اإلنتاجية ‪ :‬هى عدد المهمات التى يمكن للنظام‬ ‫تنفيذها فى فترة زمنية محددة (اى معدل المهام التى انجزت)‪.‬‬ ‫‪.3‬الزمن الكلى ‪ :‬وهو الزمن أو الفترة الزمنية الذى تقضيه‬ ‫المهمة فى النظام منذ انشائها وحتى نهاية تنفيذها وهو يتناسب‬ ‫عكسيًا مع اإلنتاجية‪.‬‬ ‫‪.4‬زمن اإلستجابة ‪ :‬هو الزمن المستغرق بين استالم الطلب‬ ‫وحتى ظهور النتائج ‪.‬‬ ‫‪.5‬زمن اإلنتظار ‪ :‬هو متوسط الفترة الزمنية التى تقضيها‬ ‫المهمة فى اإلنتظار ‪.‬‬  ‫خوارزميات الجدولة‬ ‫هى خوارزميات تكتب لتوضيح كيفية دخول المهمات الى‬ ‫وحدة المعالجة المركزية وعادة ماتستخدم العالقات الرياضية‬ ‫لتحديد زمن الدخول وزمن المعالجة‪.‬وهنالك بعض‬ ‫‪CPU utilization‬‬ ‫جعل المعالج مشغوال قدر اإلمكان‬ ‫المصطلحات التى تستخدمها مثل ‪:‬‬ ‫‪Throughput‬‬ ‫عدد المهمات التى يكتمل تنفيذها لكل وحدة‬ ‫زمنية‬ ‫‪Turnaround Time‬‬ ‫كمية الوقت االزم لتنفيذ مهمة معينة‬ ‫‪Time waiting‬‬ ‫كمية الوقت التى تظل فيها المهمة فى‬ ‫وقت االستعداد الى ان يتم تنفيذها‬ ‫‪Burst Time‬‬ ‫هو الوقت الذى يستغرقه المعالج لالنتهاء‬ ‫من المهمة‬  ‫خوارزميات الجدولة‬ ‫خوارزمية القادم أوًال يخدم أوًال‪FCFS: First Come First(.‬‬ ‫‪.1‬‬ ‫‪)Served‬‬ ‫خوارزمية العمل األقصر أوًال ‪)SJF: Shortest Job First(.‬‬ ‫‪.2‬‬ ‫الخوارزمية الدورانية ‪)RR: Round Robin(.‬‬ ‫‪.3‬‬ ‫خوارزمية األفضلية ‪)Priority(.‬‬ ‫‪.4‬‬ ‫ملحوظة ‪ :‬كل هذه الخوارزميات تستخدم مخطط للرسم لتوضيح‬ ‫جدولة العمليات يسمى مخطط الـ‪. Gantt‬‬  ‫خوارزمية القادم أوًال يخدم أوًال‬ ‫(‪)FCFS: First Come First Served‬‬ ‫تعتمد على فكرة المهمة التى تصل اوال تنفذ اوال وتسمى‬ ‫ ‬ ‫ايضا‬ ‫(‪ )first in first out‬حيث يكون هنالك صف للمهمات الجاهزة‬ ‫للتنفيذ ‪.‬‬ ‫عندما ينتهى المعالج من تنفيذ مهمة فيتم حذفها ‪ ،‬ثم اختيار‬ ‫ ‬ ‫المهمة التالية من صف االنتظار حيث يتم اختيارها من اول‬ ‫الصف والتى يمكن ان تكون استغرقت اطول وقت إنتظار ‪.‬‬ ‫ميزة الخوارزمية انها تقوم بتنفيذ العمليات او المهام‬ ‫ ‬ ‫بالترتيب فى حالة المهام الصغيرة‪ ،‬ولكن عيبها عندما‬  ‫مثال (‪:)1‬‬ ‫اذا كان لدينا مهمات وصلت بالترتيب فى صف اإلنتظار كما فى‬ ‫الجدول ونريد تنفيذها حسب خوارزميات القادم اوال يخدم اوال‬ ‫احسب االتى ‪:‬‬ ‫متوسط زمن االنتظار( ‪)waiting time‬‬ ‫‪.1‬‬ ‫متوسط زمن االكتمال(‪)completion time‬‬ ‫‪.2‬‬ ‫متوسط زمن االنتظار اذا كان ترتيب الوصول عكسى كالتالى‬ ‫‪.3‬‬ ‫(‪ p3‬ثم ‪ p2‬ثم ‪ )p1‬ثم وضح الفرق بين المتوسطين‪.‬‬ ‫الحل ‪:‬‬  ‫مواصلة حل‪...‬مثال (‪)1‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫المقارنة ‪:‬نالحظ ان وقت االنتظار قل كثيرا عن السابق بمعنى‬ ‫اذا كانت هنالك مهمة تحتاج لوقت طويل ثم جاءت بعدها اخرى‬ ‫تحتاج لوقت قصير فإنها تضطر الى االنتظار اال ان ينتهى‬ ‫المعالج‪.‬‬  ‫خوارزمية العمل األقصر أوًال‬ ‫‪)SJF: Shortest Job First(.‬‬ ‫تعتمد على فكرة ان يتم اختيار المهمة التى تحتاج لزمن تنفيذ‬ ‫ ‬ ‫اقصر (اى الزمن المقدر إلنجازها اقل مقارنة ببقية المهمات‬ ‫الموجودة فى صف اإلنتظار)‪.‬‬ ‫ميزة هذه الطريقة أنها تعطى أفضلية للمهمات الصغيرة على‬ ‫ ‬ ‫حساب المهمات الكبيرة‪ ،‬وعيبها تظهر (مشكلة المجاعة‬ ‫‪: )Starvation‬وهى تعنى أن هنالك مهمة قد التنفذ إطالقًا ‪.‬‬ ‫تنقسم هذه الخوارزمية الى نوعين ‪:‬‬ ‫ ‬ ‫غير قابلة للتوقف (‪. )non preemptive‬‬ ‫‪.1‬‬ ‫قابلة للتوقف (‪. )preemptive‬‬ ‫‪.2‬‬  ‫النوع االول ‪ :‬غير قابلة للتوقف (‪non‬‬ ‫‪)preemptive‬‬ ‫فى هذا النوع عند قدوم عدد من المهمات التى التأخذ وقتا‬ ‫طويًال اى اقل وقت‪ ،‬ولكن عند قدوم مهمة جديدة وكان‬ ‫الوقت الالزم لمعالجتها اقل من التى مع المعالج فإنه يتم‬ ‫تجاهلها ويكمل المعالج عمله الى ان ينتهى ‪.‬‬ ‫النوع الثانى ‪ :‬قابلة للتوقف‬ ‫(‪)preemptive‬‬ ‫نفس الطريقة السابقة ولكن الفرق هو عند قدوم مهمة ما‬ ‫وكان الوقت الالزم لمعالجتها اقل من التى فى المعالج فإن‬  ‫مثال (‪:)2‬‬ ‫اذا كان لدينا ‪ 4‬مهمات قادمات للمعالج‪ ،‬مستخدما خوارزمية‬ ‫العمل االقصر اوال‪.‬‬ ‫ارسم مخطط ‪ Gantt‬ليوضح كيفية تنفيذها اذا كان يعمل‬ ‫‪.1‬‬ ‫بإستخدام النوع غير قابل للتوقف ‪.‬‬ ‫زمن المعالجة‬ ‫الوصول طريقة ‪.‬‬ ‫زمن‬ ‫االنتظار لكل‬ ‫المهمة‬ ‫متوسط زمن‬ ‫احسب‬ ‫‪.2‬‬ ‫‪7‬‬ ‫‪0‬‬ ‫‪p1‬‬ ‫‪4‬‬ ‫‪2‬‬ ‫‪p2‬‬ ‫‪1‬‬ ‫‪4‬‬ ‫‪p3‬‬ ‫‪4‬‬ ‫‪5‬‬ ‫‪p4‬‬  ‫الحل ‪:‬‬ ‫اوال ‪ :‬باستخدام النوع غير القابلة للتوقف‬ ‫ المخطط ‪Gantt‬‬ ‫متوسط زمن االنتظار‬ ‫ ‬ ‫ملى ثانية ‪)0+6+3+7(/4 =4‬‬ ‫الخوارزمية الدورانية (‪)RR: Round Robin‬‬ ‫تستخدم مفهوم المشاركة الزمنية حيث تعمل بمبدأ‬ ‫ ‬ ‫‪ ، FIFO‬حيث تعطى لكل مهمة فترة زمنية معينة‬ ‫(‪)quantum‬فإذا لم يتم إنجازها فى هذه الفترة فإنه يتم‬ ‫ايقافها ليبدأ فى تنفيذ المهمة التالية لها فى صف اإلنتظار‪.‬‬ ‫وتوضع المهمة التى إنجزت فى اخر صف اإلنتظار ‪.‬‬ ‫عيبها ‪ :‬يجب ان تكون الفترة الزمنية الممنوحة لكل‬ ‫ ‬ ‫مهمة مناسبة ألنها اذا كانت كبيرة لكل المهمات فإن ‪RR‬‬ ‫تتحول لـ‪ ، FIFO‬واذا كانت قصيرة تكثر عمليات التبديل‬  ‫مثال (‪: )3‬‬ ‫اذا كانت لدينا ‪ 3‬مهمات كما فى الجدول التالى ‪ ،‬قم‬ ‫بجدولتهم بإستخدام الخوارزمية الدورانية ‪ RR‬ثم‪:‬‬ ‫‪.1‬أرسم مخطط ‪Gantt‬‬ ‫‪.2‬وضح كيفية تنفيذها اذا كان ‪ quantum = 4‬لكل مهمة‬ ‫‪.3‬متوسط زمن االنتظار‬  ‫الحل‬ ‫‪.‬المخطط ‪Gantt‬‬  ‫خوارزمية األفضلية (‪)Priority‬‬ ‫هى خوارزمية لمعالجة نقاط الضعف ‪ ،‬حيث تتطلب‬ ‫ ‬ ‫تخصيص مقدار اولوية لكل مهمة ‪.‬‬ ‫حيث يتم تنفيذ العملية التى تحتوى على ذات االولوية‬ ‫ ‬ ‫االعلى (اقل رقم) ‪ ،‬يعنى اذا كان لدينا مهمة باولوية ‪5‬‬ ‫ومهمة اخرى باولوية ‪ ، 7‬فسوف يتم تنفيذ االولوية التى‬ ‫تحتوى على اولوية اقل وهى ‪ 5‬قبل المهمة ‪. 7‬‬  ‫مثال (‪:)4‬‬ ‫اذا كانت لدينا ‪ 5‬عمليات داخل المعالج قم بجدولتهم‬ ‫باستخدام االولوية كما فى الجدول التالى ‪:‬‬ ‫ارسم مخطط ‪ Gantt‬ليوضح كيفية تنفيذها‬ ‫‪.1‬‬ ‫احسب متوسط زمن اإلنتظار‬ ‫‪.2‬‬  ‫الحل ‪:‬‬ ‫‪.‬مخطط ‪Gantt‬‬ ‫‪.‬متوسط زمن اإلنتظار‬ ‫ملى ثانية ‪)6+0+16+18+1(/5 =8.2‬‬ ?? !THANK S