أقصر مهمة أولاً (SJF): مثال وقائي وغير وقائي

ما هو أقصر جدولة الوظيفة أولا؟

أقصر مهمة أولاً (SJF) هي خوارزمية يتم فيها اختيار العملية التي لها أقل وقت تنفيذ للتنفيذ التالي. يمكن أن تكون طريقة الجدولة هذه وقائية أو غير وقائية. فهو يقلل بشكل كبير من متوسط ​​وقت الانتظار للعمليات الأخرى التي تنتظر التنفيذ. الشكل الكامل لـ SJF هو أقصر وظيفة أولاً.

هناك نوعان أساسيان من أساليب SJF:

• SJF غير وقائية
• SJF الاستباقي

خصائص جدولة SJF

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

SJF غير وقائية

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

ضع في اعتبارك العمليات الخمس التالية، ولكل منها وقت انفجار ووقت وصول فريدين.

قائمة انتظار العملية	وقت الانفجار	وقت الوصول
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

الخطوة 0) عند الزمن = 0، يصل P4 ويبدأ التنفيذ.

الخطوة 1) عند الزمن = 1، تصل العملية P3. لكن العملية P4 لا تزال بحاجة إلى وحدتي تنفيذ لإكمالها. ستواصل التنفيذ.

الخطوة 2) في الوقت = 2، تصل العملية P1 وتتم إضافتها إلى قائمة انتظار الانتظار. سوف يستمر P4 في التنفيذ.

الخطوة 3) في الوقت = 3، ستنتهي العملية P4 من تنفيذها. تتم مقارنة وقت الاندفاع P3 وP1. يتم تنفيذ العملية P1 لأن وقت انفجارها أقل مقارنة بالعملية P3.

الخطوة 4) في الوقت = 4، تصل العملية P5 وتتم إضافتها إلى قائمة انتظار الانتظار. سوف يستمر P1 في التنفيذ.

الخطوة 5) في الوقت = 5، تصل العملية P2 وتتم إضافتها إلى قائمة انتظار الانتظار. سوف يستمر P1 في التنفيذ.

الخطوة 6) في الوقت = 9، ستنتهي العملية P1 من تنفيذها. تتم مقارنة وقت الاندفاع P3 وP5 وP2. يتم تنفيذ العملية P2 لأن وقت انفجارها هو الأقل.

الخطوة 7) عند الزمن = 10، يكون P2 قيد التنفيذ ويكون P3 و P5 في قائمة الانتظار.

الخطوة 8) في الوقت = 11، ستنتهي العملية P2 من تنفيذها. تتم مقارنة وقت الاندفاع P3 وP5. يتم تنفيذ العملية P5 لأن وقت انفجارها أقل.

الخطوة 9) في الوقت = 15، ستنتهي العملية P5 من تنفيذها.

الخطوة 10) في الوقت = 23، ستنتهي العملية P3 من تنفيذها.

الخطوة 11) لنحسب متوسط ​​وقت الانتظار للمثال أعلاه.

Wait time
P4 = 0 - 0 = 0
P1 = 3 - 2 = 1
P2 = 9 - 5 = 4
P5 = 11 - 4 = 7
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2

SJF الاستباقي

في جدولة SJF الاستباقية، تُوضع المهام في قائمة الانتظار الجاهزة فور وصولها. تبدأ العملية ذات أقصر وقت تنفيذ بالتنفيذ. إذا وصلت عملية أخرى ذات وقت تنفيذ أقصر، تُزال العملية الحالية أو تُقاطع من التنفيذ، وتُخصص دورة معالجة مركزية للمهمة الأقصر.

ضع في اعتبارك العمليات الخمس التالية:

قائمة انتظار العملية	وقت الانفجار	وقت الوصول
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

الخطوة 0) عند الزمن = 0، يصل P4 ويبدأ التنفيذ.

قائمة انتظار العملية	وقت الانفجار	وقت الوصول
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

الخطوة 1) عند الزمن = 1، تصل العملية P3. لكن العملية P4 لديها وقت تنفيذ أقصر، لذا ستواصل التنفيذ.

الخطوة 2) في الوقت = 2، تصل العملية P1 مع وقت الاندفاع = 6. وقت الاندفاع أكبر من زمن الاندفاع P4. وبالتالي، سيستمر P4 في التنفيذ.

الخطوة 3) في الوقت = 3، ستنتهي العملية P4 من تنفيذها. تتم مقارنة وقت الاندفاع P3 وP1. يتم تنفيذ العملية P1 لأن وقت انفجارها أقل.

الخطوة 4) في الوقت = 4، ستصل العملية P5. تتم مقارنة وقت الاندفاع P3 وP5 وP1. يتم تنفيذ العملية P5 لأن وقت انفجارها هو الأدنى. تم استباق العملية P1.

قائمة انتظار العملية	وقت الانفجار	وقت الوصول
P1	باقي 5 من 6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

الخطوة 5) عند الزمن = 5، ستصل العملية P2. تتم مقارنة أوقات التنفيذ للعمليات P1 وP2 وP3 وP5. تُنفذ العملية P2 لأن وقت تنفيذها هو الأقصر. تُقاطع العملية P5.

قائمة انتظار العملية	وقت الانفجار	وقت الوصول
P1	باقي 5 من 6	2
P2	2	5
P3	8	1
P4	3	0
P5	باقي 3 من 4	4

الخطوة 6) عند الزمن = 6، يتم تنفيذ P2.

الخطوة 7) عند الزمن 7، تنتهي العملية P2 من تنفيذها. تتم مقارنة زمن التنفيذ للعمليات P1 وP3 وP5. يتم تنفيذ العملية P5 لأن زمن تنفيذها أقصر.

قائمة انتظار العملية	وقت الانفجار	وقت الوصول
P1	باقي 5 من 6	2
P2	2	5
P3	8	1
P4	3	0
P5	باقي 3 من 4	4

الخطوة 8) عند الزمن 10، ستنتهي العملية P5 من تنفيذها. تتم مقارنة زمن التنفيذ للعمليتين P1 وP3. يتم تنفيذ العملية P1 لأن زمن تنفيذها أقصر.

الخطوة 9) عند الزمن 15، تنتهي العملية P1 من تنفيذها. تبقى العملية P3 فقط، وستبدأ هي التنفيذ.

الخطوة 10) عند الزمن = 23، ينهي البرنامج P3 تنفيذه.

الخطوة 11) لنحسب متوسط ​​وقت الانتظار للمثال أعلاه.

Wait time
P4 = 0 - 0 = 0
P1 = (3 - 2) + 6 = 7
P2 = 5 - 5 = 0
P5 = 4 - 4 + 2 = 2
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6

مزايا SJF

فيما يلي فوائد/مزايا استخدام طريقة SJF:

• يتم استخدام SJF بشكل متكرر للجدولة طويلة المدى.
• يقلل ذلك من متوسط ​​وقت الانتظار مقارنةً بخوارزمية FIFO (الأول في الأول خارج).
• تُعطي طريقة SJF أقل متوسط ​​وقت انتظار لمجموعة محددة من العمليات.
• وهو مناسب للمهام التي يتم تشغيلها على دفعات، حيث تكون أوقات التشغيل معروفة مسبقًا.
• بالنسبة لنظام الدفعات للجدولة طويلة المدى، يمكن الحصول على تقدير وقت الاندفاع من الوصف الوظيفي.
• بالنسبة للجدولة قصيرة المدى، نحتاج إلى التنبؤ بقيمة وقت الاندفاع التالي.
• من المحتمل أن يكون هذا هو الأمثل فيما يتعلق بمتوسط ​​وقت الاستجابة.

عيوب/سلبيات SJF

فيما يلي بعض عيوب/سلبيات خوارزمية SJF:

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

الأسئلة الشائعة