โปรแกรม C++ สำหรับ Priority Scheduling (การจัดตารางเวลาตามลำดับความสำคัญ)

โจทย์

เราได้รับจำนวน n โปรเซส คือ P1, P2, P3,.......,Pn พร้อม burst times และ priorities ที่เกี่ยวข้องกับแต่ละโปรเซส งานคือหา average waiting time, average turnaround time และลำดับการดำเนินการของโปรเซสโดยใช้ priority CPU scheduling algorithm

Waiting Time และ Turnaround Time คืออะไร?

Turnaround Time คือช่วงเวลาระหว่างการส่งโปรเซสและการเสร็จสิ้นของมัน

Turnaround Time = completion of a process - submission of a process

Waiting Time คือความแตกต่างระหว่าง turnaround time และ burst time

Waiting Time = turnaround time - burst time

Priority Scheduling คืออะไร?

ใน priority scheduling ทุกโปรเซสเกี่ยวข้องกับ priority ตั้งแต่ 0-10 โดย integer 0 แสดงลำดับความสำคัญต่ำสุด และ 10 แสดงลำดับความสำคัญสูงสุด Priorities สามารถกำหนดได้สองวิธี คือ internally และ externally นอกจากนี้ priority scheduling สามารถเป็น preemptive หรือ nonpreemptive ได้

ใน preemptive priority scheduling, scheduler จะ preempt CPU หาก priority ของโปรเซสที่เพิ่งมาสูงกว่า priority ของโปรเซสที่กำลังทำงานอยู่

ใน nonpreemptive priority scheduling, scheduler จะคิวโปรเซสใหม่ที่หัวของ ready queue

ข้อเสียของการใช้ priority scheduling algorithm คือ indefinite blocking หรือ starvation จะมี low priority process ที่อาจต้องรอไม่สิ้นสุดสำหรับทรัพยากรเนื่องจาก high priority process ซึ่งนำไปสู่ปัญหา starvation

ตัวอย่าง

สมมติมี 4 โปรเซส P1, P2, P3 และ P4 พร้อม burst time และ priorities ที่เกี่ยวข้อง โดย 0 แสดงลำดับความสำคัญต่ำสุด และ 10 แสดงลำดับความสำคัญสูงสุด

ลำดับการดำเนินการหลายโปรเซสจะถูกแทนด้วย Gantt chart ด้านล่าง

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → สร้างโครงสร้าง Process ด้วยตัวแปร pid, bt, priority
ขั้นตอน 2 → ในฟังก์ชัน bool compare(Process a, Process b)
  คืนค่า (a.priority > b.priority)
ขั้นตอน 3 → ในฟังก์ชัน waitingtime(Process pro[], int n, int wt[])
  ตั้งค่า wt[0] = 0
  วนลูป For i = 1 ถึง n และ i++
    ตั้งค่า wt[i] = pro[i-1].bt + wt[i-1]
  จบวน
ขั้นตอน 4 → ในฟังก์ชัน turnarround( Process pro[], int n, int wt[], int tat[])
  วนลูป For i = 0 ถึง n และ i++
    ตั้งค่า tat[i] = pro[i].bt + wt[i]
  จบวน
ขั้นตอน 5 → ในฟังก์ชัน avgtime(Process pro[], int n)
  ประกาศและเริ่มต้น wt[n], tat[n], total_wt = 0, total_tat = 0
  เรียกฟังก์ชัน waitingtime(pro, n, wt)
  เรียกฟังก์ชัน turnarround(pro, n, wt, tat)
  พิมพ์ "Processes, Burst time, Waiting time, Turn around time"
  วนลูป For i=0 ถึง n และ i++
    ตั้งค่า total_wt = total_wt + wt[i]
    ตั้งค่า total_tat = total_tat + tat[i]
  จบวน
  พิมพ์ค่า "Processes, Burst time, Waiting time, Turn around time"
  พิมพ์ Average waiting time, Average turn around time
ขั้นตอน 6 → ในฟังก์ชัน scheduling(Process pro[], int n)
  เรียกฟังก์ชัน sort(pro, pro + n, compare)
  วนลูป For i = 0 ถึง n และ i++
    พิมพ์ลำดับ
  จบวน
  เรียกฟังก์ชัน avgtime(pro, n)
ขั้นตอน 7 → ในฟังก์ชัน int main()
  ประกาศและเริ่มต้น Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}}
  ประกาศและเริ่มต้น n = sizeof pro / sizeof pro[0]
  เรียกฟังก์ชัน scheduling(pro, n)
หยุด

ตัวอย่างโค้ด C++

#include<bits/stdc++.h>
using namespace std;
struct Process {
  int pid; // Process ID
  int bt; // CPU Burst time required
  int priority; // Priority of this process
};
// เรียงโปรเซสตาม priority
bool compare(Process a, Process b) {
  return (a.priority > b.priority);
}
void waitingtime(Process pro[], int n, int wt[]) {
  // Initial waiting time for a process is 0
  wt[0] = 0;
  // คำนวณ waiting time
  for (int i = 1; i < n ; i++ )
    wt[i] = pro[i-1].bt + wt[i-1] ;
}
// ฟังก์ชันคำนวณ turn around time
void turnarround( Process pro[], int n, int wt[], int tat[]) {
  // คำนวณ turnaround time โดยบวก bt[i] + wt[i]
  for (int i = 0; i < n ; i++)
    tat[i] = pro[i].bt + wt[i];
}
// ฟังก์ชันคำนวณเวลาเฉลี่ย
void avgtime(Process pro[], int n) {
  int wt[n], tat[n], total_wt = 0, total_tat = 0;
  // ฟังก์ชันหาเวลารอของทุกโปรเซส
  waitingtime(pro, n, wt);
  // ฟังก์ชันหา turn around time สำหรับทุกโปรเซส
  turnarround(pro, n, wt, tat);
  // แสดงโปรเซสพร้อมรายละเอียดทั้งหมด
  cout << "\nProcesses "<< " Burst time " << " Waiting time " << " Turn around time\n";
  // คำนวณ total waiting time และ total turn around time
  for (int i=0; i<n; i++) {
    total_wt = total_wt + wt[i];
    total_tat = total_tat + tat[i];
    cout << " " << pro[i].pid << "\t\t" << pro[i].bt << "\t " << wt[i] << "\t\t " << tat[i] <<endl;
  }
  cout << "\nAverage waiting time = " << (float)total_wt / (float)n;
  cout << "\nAverage turn around time = " << (float)total_tat / (float)n;
}
void scheduling(Process pro[], int n) {
  // เรียงโปรเซสตาม priority
  sort(pro, pro + n, compare);
  cout<< "Order in which processes gets executed \n";
  for (int i = 0 ; i < n; i++)
    cout << pro[i].pid <<" " ;
  avgtime(pro, n);
}
// ฟังก์ชันหลัก
int main() {
  Process pro[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}};
  int n = sizeof pro / sizeof pro[0];
  scheduling(pro, n);
  return 0;
}

ผลลัพธ์

Order in which processes gets executed 1 3 2
Processes  Burst time  Waiting time  Turn around time
1            10         0              10
3            8          10             18
2            5          18             23
Average waiting time = 9.33333
Average turn around time = 17