โปรแกรม C++ สำหรับการจัดตารางเวลา Shortest Job First (SJF) แบบ Preemptive

โจทย์

กำหนดโปรเซส เวลา burst ของโปรเซสแต่ละตัว และ quantum limit งานคือหาและพิมพ์เวลารอ, เวลาตอบสนอง และค่าเฉลี่ยของแต่ละอย่าง โดยใช้วิธี Shortest Job First Scheduling แบบ preemptive

Shortest Job First Scheduling คืออะไร?

Shortest job first scheduling เป็นอัลกอริทึมการจัดตารางเวลางานหรือโปรเซสที่ปฏิบัติตามระเบียบ nonpreemptive scheduling ในนี้ scheduler เลือกโปรเซสจากคิวรอที่มีเวลาเสร็จสิ้นน้อยที่สุด และจัดสรร CPU ให้งานหรือโปรเซสนั้น SJF น่าพึงประสงค์กว่า FIFO เพราะ SJF มีประสิทธิภาพมากกว่า เนื่องจากลดเวลารอเฉลี่ย ซึ่งจะเพิ่ม throughput

SJF algorithm สามารถเป็น preemptive หรือ non-preemptive ได้ Preemptive scheduling ยังเรียกว่า shortest-remaining-time-first scheduling ในแนวทาง Preemptive โปรเซสใหม่เกิดขึ้นเมื่อมีโปรเซสกำลังทำงานอยู่ ถ้า burst time ของโปรเซสที่เพิ่งมาน้อยกว่า burst time ของโปรเซสที่กำลังทำงาน scheduler จะ preempt การทำงานของโปรเซสที่มี burst time น้อยกว่า

Turnaround time, waiting time และ completion time คืออะไร?

• Completion Time คือเวลาที่โปรเซสต้องใช้เพื่อให้เสร็จสิ้นการทำงาน

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

  Turnaround Time = การเสร็จสิ้นของโปรเซส - การส่งของโปรเซส

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

  Waiting Time = turnaround time - burst time

ตัวอย่าง

เราได้รับโปรเซส P1, P2, P3, P4 และ P5 ที่มี burst time และ arrival time ตามตารางด้านล่าง

เนื่องจาก arrival time ของ P1 เป็น 0 มันจะเป็นตัวแรกที่ถูกดำเนินการจนกว่าโปรเซสอื่นจะมาถึง เมื่อเวลา 1 โปรเซส P2 เข้ามา และ burst time ของ P2 น้อยกว่า P1 ดังนั้น scheduler จะส่ง CPU ให้โปรเซส P2 และต่อไป

ค่าเฉลี่ยเวลารอคำนวณจาก Gantt chart P1 รอ (0+4)=4, P2 รอ 1, P3 รอ 7, P4 รอ 3 และ P5 รอ 15 ดังนั้นค่าเฉลี่ยเวลารอจะเป็น -

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ประกาศโครงสร้าง Process
  ประกาศ pid, bt, art
ขั้นตอน 2 → ในฟังก์ชัน findTurnAroundTime(Process proc[], int n, int wt[], int tat[])
  วนลูป For i = 0 ถึง n และ i++
    ตั้งค่า tat[i] = proc[i].bt + wt[i]
ขั้นตอน 3 → ในฟังก์ชัน findWaitingTime(Process proc[], int n, int wt[])
  ประกาศ rt[n]
  วนลูป For i = 0 ถึง n และ i++
    ตั้งค่า rt[i] = proc[i].bt
    ตั้งค่า complete = 0, t = 0, minm = INT_MAX
    ตั้งค่า shortest = 0, finish_time
    ตั้งค่า bool check = false
    วนลูป While (complete != n)
      วนลูป For j = 0 ถึง n และ j++
        ถ้า (proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0 แล้ว
          ตั้งค่า minm = rt[j]
          ตั้งค่า shortest = j
          ตั้งค่า check = true
        จบถ้า
      จบวน
      ถ้า check == false แล้ว
        เพิ่ม t 1
        Continue
      จบถ้า
      ลดค่า rt[shortest] ลง 1
      ตั้งค่า minm = rt[shortest]
      ถ้า minm == 0 แล้ว
        ตั้งค่า minm = INT_MAX
      จบถ้า
      ถ้า rt[shortest] == 0 แล้ว
        เพิ่ม complete 1
        ตั้งค่า check = false
        ตั้งค่า finish_time = t + 1
        ตั้งค่า wt[shortest] = finish_time - proc[shortest].bt - proc[shortest].art
        ถ้า wt[shortest] < 0
          ตั้งค่า wt[shortest] = 0
        จบถ้า
        เพิ่ม t 1
      จบถ้า
    จบวน
ขั้นตอน 4 → ในฟังก์ชัน findavgTime(Process proc[], int n)
  ประกาศและตั้งค่า wt[n], tat[n], total_wt = 0, total_tat = 0
  เรียก findWaitingTime(proc, n, wt)
  เรียก findTurnAroundTime(proc, n, wt, tat)
  วนลูป For i = 0 ถึง n และ i++
    ตั้งค่า total_wt = total_wt + wt[i]
    ตั้งค่า total_tat = total_tat + tat[i]
    พิมพ์ proc[i].pid, proc[i].bt, wt[i], tat[i]
    พิมพ์ Average waiting time คือ total_wt / n
    พิมพ์ Average turn around time คือ total_tat / n
  จบวน
ขั้นตอน 5 → ในฟังก์ชัน int main()
  ประกาศและตั้งค่า Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } }
  ตั้งค่า n = sizeof(proc) / sizeof(proc[0])
  เรียก findavgTime(proc, n)
หยุด

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

#include <bits/stdc++.h>
using namespace std;
// โครงสร้างสำหรับทุกโปรเซส
struct Process {
  int pid; // Process ID
  int bt; // Burst Time
  int art; // Arrival Time
};
void findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) {
  for (int i = 0; i < n; i++)
    tat[i] = proc[i].bt + wt[i];
}
// เวลารอของทุกโปรเซส
void findWaitingTime(Process proc[], int n, int wt[]) {
  int rt[n];
  for (int i = 0; i < n; i++)
    rt[i] = proc[i].bt;
  int complete = 0, t = 0, minm = INT_MAX;
  int shortest = 0, finish_time;
  bool check = false;
  while (complete != n) {
    for (int j = 0; j < n; j++) {
      if ((proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0) {
        minm = rt[j];
        shortest = j;
        check = true;
      }
    }
    if (check == false) {
      t++;
      continue;
    }
    // ลดเวลาที่เหลือ
    rt[shortest]--;
    minm = rt[shortest];
    if (minm == 0)
      minm = INT_MAX;
    // ถ้าโปรเซสทำงานเสร็จสมบูรณ์
    if (rt[shortest] == 0) {
      complete++;
      check = false;
      finish_time = t + 1;
      // คำนวณเวลารอ
      wt[shortest] = finish_time - proc[shortest].bt - proc[shortest].art;
      if (wt[shortest] < 0)
        wt[shortest] = 0;
    }
    // เพิ่มเวลา
    t++;
  }
}
// ฟังก์ชันคำนวณเวลาเฉลี่ย
void findavgTime(Process proc[], int n) {
  int wt[n], tat[n], total_wt = 0, total_tat = 0;
  // ฟังก์ชันหาเวลารอของทุกโปรเซส
  findWaitingTime(proc, n, wt);
  // ฟังก์ชันหา turn around time สำหรับทุกโปรเซส
  findTurnAroundTime(proc, n, wt, tat);
  cout << "Processes " << " Burst time " << " Waiting time " << " Turn around time\n";
  for (int i = 0; i < n; i++) {
    total_wt = total_wt + wt[i];
    total_tat = total_tat + tat[i];
    cout << " " << proc[i].pid << "\t\t" << proc[i].bt << "\t\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;
}
// ฟังก์ชันหลัก
int main() {
  Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } };
  int n = sizeof(proc) / sizeof(proc[0]);
  findavgTime(proc, n);
  return 0;
}

ผลลัพธ์