في هذا البرنامج التعليمي، سوف نتعلم مفهومًا مهمًا في خوارزميات جدولة عمليات وحدة المعالجة المركزية. اسم المفهوم المهم هو 'من يأتي أولاً يخدم أولاً'. هذه هي الخوارزمية الأساسية التي يجب على كل طالب أن يتعلمها لفهم جميع أساسيات خوارزميات جدولة عمليات وحدة المعالجة المركزية.
يمهد مبدأ 'من يأتي أولاً يخدم أولاً' الطريق لفهم الخوارزميات الأخرى. قد يكون لهذه الخوارزمية عيوب كثيرة. لكن هذه العيوب خلقت خوارزميات جديدة وفعالة للغاية. لذلك، تقع على عاتقنا مسؤولية التعرف على خوارزميات جدولة عمليات وحدة المعالجة المركزية (من يأتي أولاً يخدم أولاً).
اختصارات هامة
- وحدة المعالجة المركزية - - -> وحدة المعالجة المركزية
- FCFS - - -> من يأتي أولاً يخدم أولاً
- في - - -> وقت الوصول
- BT - - -> وقت الانفجار
- WT - - -> وقت الانتظار
- TAT - - -> وقت الدوران
- CT - - -> وقت الانتهاء
- FIFO - - -> أولًا ما يدخل أولاً يخرج أولاً
الخدمة بأسبقية الوصول
خوارزمية جدولة وحدة المعالجة المركزية التي تأتي أولاً تخدم أولاً والتي تُعرف قريبًا باسم FCFS هي الخوارزمية الأولى لخوارزمية جدولة عملية وحدة المعالجة المركزية. في خوارزمية من يأتي أولاً يخدم أولاً، ما نقوم به هو السماح للعملية بالتنفيذ بطريقة خطية.
وهذا يعني أن أي عملية تدخل إلى العملية التي تدخل قائمة الانتظار الجاهزة أولاً يتم تنفيذها أولاً. يوضح هذا أن خوارزمية من يأتي أولاً يخدم أولاً تتبع مبدأ الوارد أولاً يخرج أولاً (FIFO).
يمكن تنفيذ خوارزمية من يأتي أولاً يخدم أولاً بطريقة وقائية وغير وقائية. قبل الخوض في الأمثلة، دعونا نفهم ما هو النهج الوقائي وغير الوقائي في جدولة عملية وحدة المعالجة المركزية.
النهج الوقائي
في هذا المثال من الجدولة الوقائية للعملية، يقوم نظام التشغيل بتخصيص الموارد لعملية ما لفترة زمنية محددة مسبقًا. تنتقل العملية من حالة التشغيل إلى حالة الاستعداد أو من حالة الانتظار إلى حالة الاستعداد أثناء تخصيص الموارد. يحدث هذا التبديل لأن وحدة المعالجة المركزية قد تقوم بتعيين أسبقية للعمليات الأخرى وتستبدل العملية النشطة حاليًا بالعملية ذات الأولوية الأعلى.
النهج غير الوقائي
في هذه الحالة الخاصة بجدولة العمليات غير الوقائية، لا يمكن سحب المورد من العملية قبل انتهاء تشغيل العملية. عند انتهاء عملية قيد التشغيل والانتقال إلى حالة الانتظار، يتم تبديل الموارد.
تأثير القافلة في من يأتي أولاً يخدم أولاً (FCFS)
تأثير القافلة هو ظاهرة تحدث في خوارزمية الجدولة المسماة 'من يأتي أولاً يخدم أولاً' (FCFS). تحدث خوارزمية جدولة من يأتي أولاً يخدم أولاً بطريقة غير وقائية.
الطريقة غير الوقائية تعني أنه إذا تم بدء تنفيذ عملية أو مهمة، فيجب على نظام التشغيل إكمال العملية أو المهمة الخاصة به. حتى تصبح العملية أو الوظيفة صفرًا، لا تبدأ العملية أو الوظيفة الجديدة أو التالية في تنفيذها. تعريف الجدولة غير الوقائية من حيث نظام التشغيل يعني أن وحدة المعالجة المركزية (CPU) ستكون مخصصة بالكامل حتى نهاية العملية أو بدء المهمة أولاً ولا يتم تنفيذ العملية أو الوظيفة الجديدة إلا بعد الانتهاء من العملية القديمة أو وظيفة.
قد تكون هناك بعض الحالات التي قد تتسبب في قيام وحدة المعالجة المركزية (CPU) بتخصيص الكثير من الوقت. وذلك لأنه في خوارزمية من يأتي أولاً يخدم أولاً النهج غير الوقائي، يتم اختيار العمليات أو الوظائف بترتيب تسلسلي. ونتيجة لذلك، فإن المهام أو العمليات الأقصر وراء العمليات الأكبر أو الوظائف تستغرق وقتًا طويلاً لإكمال تنفيذها. ونتيجة لذلك، فإن وقت الانتظار، ووقت الدوران، ووقت الانتهاء مرتفع جدًا.
لذلك، نظرًا لأن العملية الأولى كبيرة أو أن وقت الانتهاء طويل جدًا، فقد حدث تأثير القافلة في خوارزمية من يأتي أولاً يخدم أولاً.
لنفترض أن المهمة الأطول تستغرق وقتًا لا نهائيًا لإكمالها. ثم، يجب على العمليات المتبقية الانتظار لنفس الوقت اللانهائي. بسبب تأثير القافلة الذي خلقته المهمة الأطول، يزداد تجويع عمليات الانتظار بسرعة كبيرة. هذا هو أكبر عيب في جدولة عمليات وحدة المعالجة المركزية FCFS.
خصائص جدولة عملية وحدة المعالجة المركزية FCFS
خصائص جدولة عملية وحدة المعالجة المركزية FCFS هي:
- التنفيذ بسيط.
- لا يسبب أي إصابات أثناء الاستخدام
- وهي تتبنى استراتيجية غير وقائية ووقائية.
- يقوم بتشغيل كل إجراء بالترتيب الذي تم تلقيه به.
- يتم استخدام وقت الوصول كمعيار لاختيار الإجراءات.
مزايا جدولة عملية وحدة المعالجة المركزية FCFS
مزايا جدولة عملية وحدة المعالجة المركزية FCFS هي:
- من أجل تخصيص العمليات، فإنه يستخدم قائمة الانتظار أول ما يدخل أولاً يخرج.
- تتميز عملية جدولة وحدة المعالجة المركزية FCFS بأنها عملية مباشرة وسهلة التنفيذ.
- في حالة الجدولة الوقائية لحالة FCFS، لا توجد فرصة لتجويع العملية.
- نظرًا لعدم وجود اعتبار لأولوية العملية، فهي خوارزمية عادلة.
عيوب جدولة عملية وحدة المعالجة المركزية FCFS
عيوب جدولة عملية وحدة المعالجة المركزية FCFS هي:
- تتمتع خوارزمية جدولة وحدة المعالجة المركزية FCFS بوقت انتظار طويل
- تفضل جدولة وحدة المعالجة المركزية FCFS وحدة المعالجة المركزية على عمليات الإدخال أو الإخراج
- في FCFS هناك فرصة لحدوث تأثير القافلة
- ونظرًا لأن FCFS أسلوب مباشر جدًا، فإنه غالبًا ما لا يكون فعالًا جدًا. وتسير فترات الانتظار الممتدة جنبًا إلى جنب مع هذا. يتم ترك جميع الطلبات الأخرى في وضع الخمول إذا كانت وحدة المعالجة المركزية مشغولة بمعالجة أمر واحد يستغرق وقتًا طويلاً.
مشاكل في خوارزمية جدولة وحدة المعالجة المركزية 'من يأتي أولاً يخدم أولاً'.
مثال
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
النهج غير الوقائي
الآن، دعونا نحل هذه المشكلة بمساعدة خوارزمية الجدولة المسماة 'من يأتي أولاً يخدم أولاً بطريقة غير وقائية'.
مخطط جانت للمثال 1 أعلاه هو:
وقت الدوران = وقت الانتهاء - وقت الوصول
وقت الانتظار = وقت الدوران - وقت الانفجار
حل السؤال أعلاه مثال 1
| نعم / لا | معرف العمليه | وقت الوصول | وقت الانفجار | وقت الانتهاء | الفترة الزمنية | وقت الانتظار | |
|---|---|---|---|---|---|---|---|
| 1 | ص 1 | أ | 0 | 9 | 9 | 9 | 0 |
| 2 | ص 2 | ب | 1 | 3 | 12 | أحد عشر | 8 |
| 3 | ص 3 | ج | 1 | 2 | 14 | 13 | أحد عشر |
| 4 | ص 4 | د | 1 | 4 | 18 | 17 | 13 |
| 5 | ص 5 | و | 2 | 3 | واحد وعشرين | 19 | 16 |
| 6 | ص 6 | F | 3 | 2 | 23 | عشرين | 18 |
متوسط وقت الانتهاء هو:
متوسط CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
متوسط CT = 97/6
متوسط CT = 16.16667
متوسط وقت الانتظار هو:
متوسط الوزن = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
متوسط الوزن = 66/6
متوسط الوزن = 11
متوسط وقت الدوران هو:
متوسط التات = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
متوسط تات = 89/6
متوسط تات = 14.83334
هذه هي الطريقة التي يتم بها حل مشكلة FCFS بطريقة غير وقائية.
الآن، دعونا نفهم كيف يمكن حلها من خلال النهج الوقائي
النهج الوقائي
الآن، دعونا نحل هذه المشكلة بمساعدة خوارزمية الجدولة المسماة 'من يأتي أولاً يخدم أولاً في النهج الوقائي'.
pvr الشكل الكامل
في النهج الوقائي، نبحث عن أفضل عملية متاحة
مخطط جانت للمثال 1 أعلاه هو:
| نعم / لا | معرف العمليه | وقت الوصول | وقت الانفجار | وقت الانتهاء | الفترة الزمنية | وقت الانتظار | |
|---|---|---|---|---|---|---|---|
| 1 | ص 1 | أ | 0 | 9 | 23 | 23 | 14 |
| 2 | ص 2 | ب | 1 | 3 | 8 | 7 | 4 |
| 3 | ص 3 | ج | 1 | 2 | 3 | 2 | 0 |
| 4 | ص 4 | د | 1 | 4 | خمسة عشر | 14 | 10 |
| 5 | ص 5 | و | 2 | 3 | أحد عشر | 9 | 7 |
| 6 | ص 6 | F | 3 | 2 | 5 | 2 | 0 |
| التالي → ← السابق للتخلص من مشكلة إهدار إشارات الاستيقاظ، اقترح ديكسترا طريقة تتضمن تخزين جميع نداءات الاستيقاظ. يذكر ديكسترا أنه بدلاً من إعطاء نداءات التنبيه مباشرة إلى المستهلك، يمكن للمنتج تخزين نداء التنبيه في متغير. يمكن لأي من المستهلكين قراءتها عندما يحتاج إلى ذلك. الإشارة هي المتغيرات التي تخزن جميع مكالمات التنبيه التي يتم نقلها من المنتج إلى المستهلك. وهو متغير تتم فيه القراءة والتعديل والتحديث تلقائيًا في وضع kernel. لا يمكن تنفيذ الإشارة في وضع المستخدم لأن حالة السباق قد تنشأ دائمًا عندما تحاول عمليتان أو أكثر الوصول إلى المتغير في وقت واحد. يحتاج دائمًا إلى دعم من نظام التشغيل ليتم تنفيذه. وفقا لمتطلبات الوضع، يمكن تقسيم الإشارة إلى فئتين.
وسوف نناقش كل واحد بالتفصيل. |