โปรแกรม C++ สำหรับ Shortest Job First (SJF) scheduling แบบ Non-preemptive

โจทย์

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

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

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

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

• Completion 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

ตัวอย่าง

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

เนื่องจาก burst time ของโปรเซส P4 น้อยที่สุดในหมู่ทั้งหมด มันจะได้รับ CPU ก่อน หลังจากนั้น P2 จะถูกจัดคิว ตามด้วย P1, P3 และ P5

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

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ในฟังก์ชัน swap(int *a, int *b)
  ตั้งค่า temp = *a
  ตั้งค่า *a = *b
  ตั้งค่า *b = temp
ขั้นตอน 2 → ในฟังก์ชัน arrangeArrival(int num, int mat[][3])
  วนลูป For i=0 ถึง num และ i++
    วนลูป For j=0 ถึง num-i-1 และ j++
      ถ้า mat[1][j] > mat[1][j+1] แล้ว
        สำหรับ k=0 ถึง 4 และ k++
          เรียกฟังก์ชัน swap(mat[k][j], mat[k][j+1])
ขั้นตอน 3 → ในฟังก์ชัน completionTime(int num, int mat[][3])
  ประกาศ temp, val
  ตั้งค่า mat[3][0] = mat[1][0] + mat[2][0]
  ตั้งค่า mat[5][0] = mat[3][0] - mat[1][0]
  ตั้งค่า mat[4][0] = mat[5][0] - mat[2][0]
  วนลูป For i=1 ถึง num และ i++
    ตั้งค่า temp = mat[3][i-1]
    ตั้งค่า low = mat[2][i]
    วนลูป For j=i ถึง num และ j++
      ถ้า temp >= mat[1][j] && low >= mat[2][j] แล้ว
        ตั้งค่า low = mat[2][j]
        ตั้งค่า val = j
        ตั้งค่า mat[3][val] = temp + mat[2][val]
        ตั้งค่า mat[5][val] = mat[3][val] - mat[1][val]
        ตั้งค่า mat[4][val] = mat[5][val] - mat[2][val]
        วนลูป For k=0 ถึง 5 และ k++
          เรียกฟังก์ชัน swap(mat[k][val], mat[k][i])
ขั้นตอน 4 → ในฟังก์ชัน int main()
  ประกาศและตั้งค่า num = 3, temp
  ประกาศและตั้งค่า mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4}
  พิมพ์ Process ID, Arrival Time, Burst Time
  วนลูป For i=0 ถึง num และ i++
    พิมพ์ค่า mat[0][i], mat[1][i], mat[2][i]
    เรียกฟังก์ชัน arrangeArrival(num, mat)
    เรียกฟังก์ชัน completionTime(num, mat)
    พิมพ์ Process ID, Arrival Time, Burst Time, Waiting Time, Turnaround Time
    วนลูป For i=0 ถึง num และ i++
      พิมพ์ค่า mat[0][i], mat[1][i], mat[2][i], mat[4][i], mat[5][i]
หยุด

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

// C++ program to implement Shortest Job first with Arrival Time
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
void arrangeArrival(int num, int mat[][3]) {
  for(int i=0; i<num; i++) {
    for(int j=0; j<num-i-1; j++) {
      if(mat[1][j] > mat[1][j+1]) {
        for(int k=0; k<5; k++) {
          swap(mat[k][j], mat[k][j+1]);
        }
      }
    }
  }
}
void completionTime(int num, int mat[][3]) {
  int temp, val;
  mat[3][0] = mat[1][0] + mat[2][0];
  mat[5][0] = mat[3][0] - mat[1][0];
  mat[4][0] = mat[5][0] - mat[2][0];
  for(int i=1; i<num; i++) {
    temp = mat[3][i-1];
    int low = mat[2][i];
    for(int j=i; j<num; j++) {
      if(temp >= mat[1][j] && low >= mat[2][j]) {
        low = mat[2][j];
        val = j;
      }
    }
    mat[3][val] = temp + mat[2][val];
    mat[5][val] = mat[3][val] - mat[1][val];
    mat[4][val] = mat[5][val] - mat[2][val];
    for(int k=0; k<6; k++) {
      swap(mat[k][val], mat[k][i]);
    }
  }
}
int main() {
  int num = 3, temp;
  int mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4};
  cout<<"Before Arrange...\n";
  cout<<"Process ID\tArrival Time\tBurst Time\n";
  for(int i=0; i<num; i++) {
    cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\n";
  }
  arrangeArrival(num, mat);
  completionTime(num, mat);
  cout<<"Final Result...\n";
  cout<<"Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n";
  for(int i=0; i<num; i++) {
    cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\t\t"<<mat[4][i]<<"\t\t"<<mat[5][i]<<"\n";
  }
}

ผลลัพธ์