算法设计（最长剩余时间优先（LRTF）CPU调度程序） _CPU调度算法

本文概述

C ++
Python3

先决条件–
【算法设计（最长剩余时间优先（LRTF）CPU调度程序）】CPU调度|最长剩余时间优先(LRTF)算法
我们给出了到达时间和爆发时间的一些过程, 我们必须找到完成时间(CT), 周转时间(TAT), 平均周转时间(Avg TAT), 等待时间(WT), 平均等待时间(AWT) )。
例子：考虑下表中四个进程P1, P2, P3和P4的到达时间和突发时间。

ProcessArrival timeBurst TimeP11 ms2 msP22 ms4 msP33 ms6 msp44 ms8 ms

甘特图将如下所示,

文章图片
由于可以通过甘特图直接确定完成时间(CT), 并且

Turn Around Time (TAT)= (Complition Time) - (Arival Time)Also, Waiting Time (WT)= (Turn Around Time) - (Burst Time)

因此,
输出如下：

Total Turn Around Time = 68 msSo, Average Turn Around Time = 68/4 = 17.00 msAnd, Total Waiting Time = 48 msSo, Average Waiting Time = 12.00 ms

算法–

第1步：创建一个包含所有必填字段的过程结构, 例如AT(到达时间), BT(突发时间), CT(完成时间), TAT(转身时间), WT(等待时间)。
第2步：根据AT排序；
步骤3：查找具有最大突发时间的过程, 并为每个单元执行。将总时间增加1, 并将该过程的突发时间减少1。
步骤4：当任何进程的BT剩余为0时, 则更新CT(该进程的完成时间CT将为该时间的总时间)。
第2步：在为每个过程计算CT之后, 找到TAT和WT。
(TAT = CT - AT) (WT= TAT - BT)

算法的实现–
C ++

#include < bits/stdc++.h> using namespace std; // creating a structure of a process struct process { int processno; int AT; int BT; // for backup purpose to print in last int BTbackup; int WT; int TAT; int CT; }; // creating a structe of 4 processes struct process p[4]; // variable to find the total time int totaltime = 0; int prefinaltotal = 0; // comparator function for sort() bool compare(process p1, process p2) { // compare the Arrival time of two processes return p1.AT < p2.AT; }// finding the largest Arrival Time among all the available // process at that time int findlargest( int at) { int max = 0, i; for (i = 0; i < 4; i++) { if (p[i].AT < = at) { if (p[i].BT > p[max].BT) max = i; } }// returning the index of the process having the largest BT return max; }// function to find the completion time of each process int findCT() {int index; int flag = 0; int i = p[0].AT; while (1) { if (i < = 4) { index = findlargest(i); }else index = findlargest(4); cout < < "Process executing at time " < < totaltime < < " is: P" < < index + 1 < < "\t" ; p[index].BT -= 1; totaltime += 1; i++; if (p[index].BT == 0) { p[index].CT = totaltime; cout < < " Process P" < < p[index].processno < < " is completed at " < < totaltime; } cout < < endl; // loop termination condition if (totaltime == prefinaltotal) break ; } }int main() {int i; // initializing the process number for (i = 0; i < 4; i++) { p[i].processno = i + 1; }// cout< < "arrival time of 4 processes : "; for (i = 0; i < 4; i++) // taking AT { p[i].AT = i + 1; }// cout< < " Burst time of 4 processes : "; for (i = 0; i < 4; i++) {// assigning {2, 4, 6, 8} as Burst Time to the processes // backup for displaying the output in last // calculating total required time for terminating // the function(). p[i].BT = 2 * (i + 1); p[i].BTbackup = p[i].BT; prefinaltotal += p[i].BT; }// displaying the process before executing cout < < "PNo\tAT\tBT\n" ; for (i = 0; i < 4; i++) { cout < < p[i].processno < < "\t" ; cout < < p[i].AT < < "\t" ; cout < < p[i].BT < < "\t" ; cout < < endl; } cout < < endl; // soritng process according to Arrival Time sort(p, p + 4, compare); // calculating initial time when execution starts totaltime += p[0].AT; // calculating to terminate loop prefinaltotal += p[0].AT; findCT(); int totalWT = 0; int totalTAT = 0; for (i = 0; i < 4; i++) { // since, TAT = CT - AT p[i].TAT = p[i].CT - p[i].AT; p[i].WT = p[i].TAT - p[i].BTbackup; // finding total waiting time totalWT += p[i].WT; // finding total turn around time totalTAT += p[i].TAT; }cout < < "After execution of all processes ... \n" ; // after all process executes cout < < "PNo\tAT\tBT\tCT\tTAT\tWT\n" ; for (i = 0; i < 4; i++) { cout < < p[i].processno < < "\t" ; cout < < p[i].AT < < "\t" ; cout < < p[i].BTbackup < < "\t" ; cout < < p[i].CT < < "\t" ; cout < < p[i].TAT < < "\t" ; cout < < p[i].WT < < "\t" ; cout < < endl; }cout < < endl; cout < < "Total TAT = " < < totalTAT < < endl; cout < < "Average TAT = " < < totalTAT / 4.0 < < endl; cout < < "Total WT = " < < totalWT < < endl; cout < < "Average WT = " < < totalWT / 4.0 < < endl; return 0; }

Python3

# Python3 program to implement # Longest Remaining Time First # creating a structure of 4 processes p = [] for i in range ( 4 ): p.append([ 0 , 0 , 0 , 0 , 0 , 0 , 0 ])# variable to find the total time totaltime = 0 prefinaltotal = 0# finding the largest Arrival Time # among all the available process # at that time def findlargest(at): max = 0 for i in range ( 4 ): if (p[i][ 1 ] < = at): if (p[i][ 2 ] > p[ max ][ 2 ]) : max = i # returning the index of the # process having the largest BT return max# function to find the completion # time of each process def findCT(totaltime): index = 0 flag = 0 i = p[ 0 ][ 1 ] while ( 1 ): if (i < = 4 ): index = findlargest(i) else : index = findlargest( 4 ) print ( "Process execute at time " , totaltime, end = " " ) print ( " is: P" , index + 1 , sep = " ", end = " ") p[index][ 2 ] - = 1 totaltime + = 1 i + = 1 if (p[index][ 2 ] = = 0 ): p[index][ 6 ] = totaltime print ( "Process P" , p[index][ 0 ], sep = " ", end = " ") print ( " is completed at " , totaltime, end = " " ) print ()# loop termination condition if (totaltime = = prefinaltotal): break# Driver code if __name__ = = "__main__" :# initializing the process number for i in range ( 4 ): p[i][ 0 ] = i + 1for i in range ( 4 ): # taking AT p[i][ 1 ] = i + 1for i in range ( 4 ): # assigning 2, 4, 6, 8 as Burst Time # to the processes backup for displaying # the output in last calculating total # required time for terminating the function(). p[i][ 2 ] = 2 * (i + 1 ) p[i][ 3 ] = p[i][ 2 ] prefinaltotal + = p[i][ 2 ] # displaying the process before executing print ( "PNo\tAT\tBT" )for i in range ( 4 ): print (p[i][ 0 ], "\t" , p[i][ 1 ], "\t" , p[i][ 2 ]) print ()# soritng process according to Arrival Time p = sorted (p, key = lambda p:p[ 1 ]) # calculating initial time when # execution starts totaltime + = p[ 0 ][ 1 ]# calculating to terminate loop prefinaltotal + = p[ 0 ][ 1 ] findCT(totaltime) totalWT = 0 totalTAT = 0 for i in range ( 4 ):# since, TAT = CT - AT p[i][ 5 ] = p[i][ 6 ] - p[i][ 1 ] p[i][ 4 ] = p[i][ 5 ] - p[i][ 3 ] # finding total waiting time totalWT + = p[i][ 4 ] # finding total turn around time totalTAT + = p[i][ 5 ] print ( "\nAfter execution of all processes ... " )# after all process executes print ( "PNo\tAT\tBT\tCT\tTAT\tWT" )for i in range ( 4 ): print (p[i][ 0 ], "\t" , p[i][ 1 ], "\t" , p[i][ 3 ], "\t" , end = " " ) print (p[i][ 6 ], "\t" , p[i][ 5 ], "\t" , p[i][ 4 ]) print () print ( "Total TAT = " , totalTAT) print ( "Average TAT = " , totalTAT / 4.0 ) print ( "Total WT = " , totalWT) print ( "Average WT = " , totalWT / 4.0 )# This code is contributed by # Shubham Singh(SHUBHAMSINGH10)

输出如下：

PNoATBT112224336448Process executing at time 1 is: P1Process executing at time 2 is: P2Process executing at time 3 is: P3Process executing at time 4 is: P4Process executing at time 5 is: P4Process executing at time 6 is: P4Process executing at time 7 is: P3Process executing at time 8 is: P4Process executing at time 9 is: P3Process executing at time 10 is: P4Process executing at time 11 is: P2Process executing at time 12 is: P3Process executing at time 13 is: P4Process executing at time 14 is: P2Process executing at time 15 is: P3Process executing at time 16 is: P4Process executing at time 17 is: P1Process P1 is completed at 18Process executing at time 18 is: P2Process P2 is completed at 19Process executing at time 19 is: P3Process P3 is completed at 20Process executing at time 20 is: P4Process P4 is completed at 21After execution of all processes ... PNoATBTCTTATWT11218171522419171333620171144821179Total TAT = 68Average TAT = 17Total WT = 48Average WT = 12