logo

أقصر الوقت المتبقي أولا (الوقائي SJF) جدولة الخوارزمية

يُطلق على الإصدار الوقائي من جدولة أقصر مهمة أولاً (SJF) اسم أقصر وقت متبقي أولاً (SRTF). في SRTF، يتم تحديد العملية ذات أقل وقت متبقي للانتهاء للتشغيل. تستمر عملية التشغيل حتى تنتهي أو تصل عملية جديدة مع وقت متبقي أقصر مما يضمن دائمًا حصول عملية الإنهاء الأسرع على الأولوية.

مثال على خوارزمية SJF:

السيناريو 1: العمليات بنفس وقت الوصول

مثال: خذ بعين الاعتبار الجدول التالي لوقت الوصول ووقت الاندفاع لثلاث عمليات P1 P2 و P3 .

عملية وقت الانفجار وقت الوصول
 ص1   6 مللي ثانية0 مللي ثانية
 ص2 8 مللي ثانية0 مللي ثانية
 P3 5 مللي ثانية0 مللي ثانية

التنفيذ خطوة بخطوة:



  1. الوقت 0-5 (ف3) : يعمل P3 لمدة 5 مللي ثانية (إجمالي الوقت المتبقي: 0 مللي ثانية) حيث أن لديه أقصر وقت متبقي.
  2. الوقت 5-11 (ف1) : يتم تشغيل P1 لمدة 6 مللي ثانية (إجمالي الوقت المتبقي: 0 مللي ثانية) حيث أن لديه أقصر وقت متبقي.
  3. الوقت 11-19 (ف2) : يتم تشغيل P2 لمدة 8 مللي ثانية (إجمالي الوقت المتبقي: 0 مللي ثانية) حيث أن لديه أقصر وقت متبقي.

مخطط جانت:


الانزياح الأحمر أوس

الآن دعونا نحسب المتوسط وقت الانتظار والاستدارة وقت:

كما نعلم

  • بدوره حول الوقت = وقت الانتهاء - وقت الوصول
  • وقت الانتظار = وقت الدوران – وقت الانفجار
عملية  

وقت الوصول

(في)

وقت الانفجار

حرف إلى int Java

(BT)

وقت الانتهاء (CT)وقت الدوران (TAT)وقت الانتظار (بالوزن)
 ص1  

6

1111-0 = 1111-6 = 5
 ص2

8

1919-0 = 1919-8 = 11
 P3

5

محاذاة الصور في CSS
55-0 = 55-5 = 0

الآن 

  • متوسط ​​وقت الدوران = (11 + 19 + 5)/3 = 11.6 مللي ثانية
  • متوسط ​​وقت الانتظار = (5 + 0 + 11 )/3 = 16/3 = 5.33 مللي ثانية

السيناريو 2: العمليات ذات أوقات وصول مختلفة

خذ بعين الاعتبار الجدول التالي لوقت الوصول ووقت الاندفاع لثلاث عمليات P1 P2 وP3.

عملية وقت الانفجار وقت الوصول
 ص1   6 مللي ثانية0 مللي ثانية
 ص2 3 مللي ثانية1 مللي ثانية
 P3 7 مللي ثانية2 مللي ثانية

التنفيذ خطوة بخطوة:

  1. الوقت 0-1 (ف1) : يتم تشغيل P1 لمدة 1 مللي ثانية (إجمالي الوقت المتبقي: 5 مللي ثانية) حيث أن لديه أقصر وقت متبقي.
  2. الوقت 1-4 (ف2) : يتم تشغيل P2 لمدة 3 مللي ثانية (إجمالي الوقت المتبقي: 0 مللي ثانية) حيث أن لديه أقصر وقت متبقي بين P1 وP2.
  3. الوقت 4-9 (ف1) : يتم تشغيل P1 لمدة 5 مللي ثانية (إجمالي الوقت المتبقي: 0 مللي ثانية) حيث أن لديه أقصر وقت متبقي بين P1 وP3.
  4. الوقت 9-16 (ف3) : يعمل P3 لمدة 7 مللي ثانية (إجمالي الوقت المتبقي: 0 مللي ثانية) حيث أن لديه أقصر وقت متبقي.

مخطط جانت:

الآن دعونا نحسب المتوسط وقت الانتظار والاستدارة وقت:

عملية  

وقت الوصول (AT)

مهم

وقت الانفجار (BT)

وقت الانتهاء (CT)وقت الدوران (TAT)وقت الانتظار (بالوزن)
 ص1  

المسلسل في postgres

6

99-0 = 99-6 = 3
 ص2

1

3

44-1 = 33-3 = 0
 P3

2

7

1616-2 = 1414-7 = 7
  • متوسط ​​وقت الدوران = (9 + 14 + 3)/3 = 8.6 مللي ثانية
  • متوسط ​​وقت الانتظار = (3 + 0 + 7 )/3 = 10/3 = 3.33 مللي ثانية

تنفيذ خوارزمية SRTF

الخطوة 1: إدخال عدد العمليات مع وقت الوصول ووقت الاندفاع.
الخطوة 2: تهيئة الأوقات المتبقية (أوقات الانفجار) الوقت الحالي = 0 والعدادات.
الخطوة 3: في كل مرة تقوم الوحدة بإضافة العمليات التي وصلت إلى قائمة الانتظار الجاهزة.
الخطوة 4: حدد العملية ذات أقصر وقت متبقي (استباق إذا وصلت عملية أقصر).
الخطوة 5: قم بتنفيذ العملية المحددة لوحدة واحدة لتقليل الوقت المتبقي وزيادة الوقت الحالي.
الخطوة 6: إذا اكتملت العملية:

  • وقت الاستجابة = وقت الانتهاء − وقت الوصول
  • وقت الانتظار = وقت الاستجابة − وقت الاندفاع

الخطوة 7: كرر الخطوات من 3 إلى 6 حتى تكتمل جميع العمليات.
الخطوة 8: حساب متوسط ​​وقت الانتظار ووقت الاستجابة.
الخطوة 9: عرض أوقات انتظار الانتهاء وأوقات الاستجابة لكل عملية مع المتوسطات.

تنفيذ الكود

برنامج تنفيذ أقصر وقت متبقي أولاً هو كما يلي:

C++
#include    #include  #include    using namespace std; struct Process {  int id arrivalTime burstTime remainingTime waitingTime turnaroundTime completionTime; }; int main() {  int n currentTime = 0 completed = 0;  cout << 'Enter number of processes: ';  cin >> n;  vector<Process> p(n);    for (int i = 0; i < n; i++) {  p[i].id = i + 1;  cin >> p[i].arrivalTime >> p[i].burstTime;  p[i].remainingTime = p[i].burstTime;  }  while (completed < n) {  int idx = -1;  for (int i = 0; i < n; i++) {  if (p[i].arrivalTime <= currentTime && p[i].remainingTime > 0 && (idx == -1 || p[i].remainingTime < p[idx].remainingTime)) {  idx = i;  }  }  if (idx != -1) {  p[idx].remainingTime--;  currentTime++;  if (p[idx].remainingTime == 0) {  p[idx].completionTime = currentTime;  p[idx].turnaroundTime = currentTime - p[idx].arrivalTime;  p[idx].waitingTime = p[idx].turnaroundTime - p[idx].burstTime;  completed++;  }  } else {  currentTime++;  }  }  double totalWT = 0 totalTAT = 0;  for (auto &proc : p) {  totalWT += proc.waitingTime;  totalTAT += proc.turnaroundTime;  cout << 'P' << proc.id << ' CT: ' << proc.completionTime << ' WT: ' << proc.waitingTime << ' TAT: ' << proc.turnaroundTime << endl;  }  cout << 'Avg WT: ' << totalWT / n << ' Avg TAT: ' << totalTAT / n << endl; } 
Java
import java.util.*; class Process {  int id arrivalTime burstTime remainingTime waitingTime turnaroundTime completionTime;  public Process(int id int arrivalTime int burstTime) {  this.id = id;  this.arrivalTime = arrivalTime;  this.burstTime = burstTime;  this.remainingTime = burstTime;  } } public class SRTF {  public static void main(String[] args) {  Scanner sc = new Scanner(System.in);  int n = sc.nextInt();  Process[] processes = new Process[n];    for (int i = 0; i < n; i++) {  int arrivalTime = sc.nextInt() burstTime = sc.nextInt();  processes[i] = new Process(i + 1 arrivalTime burstTime);  }  Arrays.sort(processes Comparator.comparingInt(p -> p.arrivalTime));  int currentTime = 0 completed = 0;  while (completed < n) {  int idx = -1;  for (int i = 0; i < n; i++) {  if (processes[i].arrivalTime <= currentTime && processes[i].remainingTime > 0 && (idx == -1 || processes[i].remainingTime < processes[idx].remainingTime)) {  idx = i;  }  }  if (idx != -1) {  processes[idx].remainingTime--;  currentTime++;  if (processes[idx].remainingTime == 0) {  processes[idx].completionTime = currentTime;  processes[idx].turnaroundTime = currentTime - processes[idx].arrivalTime;  processes[idx].waitingTime = processes[idx].turnaroundTime - processes[idx].burstTime;  completed++;  }  } else {  currentTime++;  }  }  double totalWT = 0 totalTAT = 0;  for (Process p : processes) {  totalWT += p.waitingTime;  totalTAT += p.turnaroundTime;  System.out.println('P' + p.id + ' CT: ' + p.completionTime + ' WT: ' + p.waitingTime + ' TAT: ' + p.turnaroundTime);  }  System.out.println('Avg WT: ' + totalWT / n + ' Avg TAT: ' + totalTAT / n);  } } 
Python
class Process: def __init__(self id arrival_time burst_time): self.id = id self.arrival_time = arrival_time self.burst_time = burst_time self.remaining_time = burst_time def srtf(processes): current_time completed = 0 0 while completed < len(processes): idx = -1 for i p in enumerate(processes): if p.arrival_time <= current_time and p.remaining_time > 0 and (idx == -1 or p.remaining_time < processes[idx].remaining_time): idx = i if idx != -1: processes[idx].remaining_time -= 1 current_time += 1 if processes[idx].remaining_time == 0: processes[idx].completion_time = current_time processes[idx].turnaround_time = current_time - processes[idx].arrival_time processes[idx].waiting_time = processes[idx].turnaround_time - processes[idx].burst_time completed += 1 else: current_time += 1 def print_results(processes): total_wt total_tat = 0 0 for p in processes: total_wt += p.waiting_time total_tat += p.turnaround_time print(f'P{p.id} CT: {p.completion_time} WT: {p.waiting_time} TAT: {p.turnaround_time}') print(f'Avg WT: {total_wt / len(processes)} Avg TAT: {total_tat / len(processes)}') n = int(input('Enter number of processes: ')) processes = [Process(i + 1 *map(int input(f'Enter arrival and burst time for P{i + 1}: ').split())) for i in range(n)] srtf(processes) print_results(processes) 

الإخراج
Enter number of processes: Avg WT: -nan Avg TAT: -nan 

مزايا صندوق الائتمان لإعادة إعمار سوريا الجدولة

  1. يقلل متوسط ​​وقت الانتظار : يعمل SRTF على تقليل متوسط ​​وقت الانتظار من خلال تحديد أولويات العمليات ذات أقصر وقت تنفيذ متبقي.
  2. فعالة للعمليات القصيرة : يتم إكمال العمليات الأقصر بشكل أسرع مما يؤدي إلى تحسين استجابة النظام بشكل عام.
  3. مثالية للأنظمة ذات الوقت الحرج : يضمن تنفيذ العمليات الحساسة للوقت بسرعة.

مساوئ صندوق الائتمان لإعادة إعمار سوريا الجدولة

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