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

2021年3月12日12:56:58 发表评论 360 次浏览

## 本文概述

CPU调度|最长剩余时间优先(LRTF)算法

``````Process   Arrival time   Burst Time
P1            1 ms          2 ms
P2            2 ms          4 ms
P3            3 ms          6 ms
p4            4 ms          8 ms``````

``````Turn Around Time (TAT)
= (Complition Time) - (Arival Time)

Also, Waiting Time (WT)
= (Turn Around Time) - (Burst Time)``````

``````Total Turn Around Time = 68 ms
So, Average Turn Around Time = 68/4 = 17.00 ms

And, Total Waiting Time = 48 ms
So, 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;

// 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.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.AT;

// calculating to terminate loop
prefinaltotal += p.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 + 1

for i in range ( 4 ): # taking AT
p[i][ 1 ] = i + 1

for 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)``````

``````PNo    AT    BT
1    1    2
2    2    4
3    3    6
4    4    8

Process executing at time 1 is: P1
Process executing at time 2 is: P2
Process executing at time 3 is: P3
Process executing at time 4 is: P4
Process executing at time 5 is: P4
Process executing at time 6 is: P4
Process executing at time 7 is: P3
Process executing at time 8 is: P4
Process executing at time 9 is: P3
Process executing at time 10 is: P4
Process executing at time 11 is: P2
Process executing at time 12 is: P3
Process executing at time 13 is: P4
Process executing at time 14 is: P2
Process executing at time 15 is: P3
Process executing at time 16 is: P4
Process executing at time 17 is: P1     Process P1 is completed at 18
Process executing at time 18 is: P2     Process P2 is completed at 19
Process executing at time 19 is: P3     Process P3 is completed at 20
Process executing at time 20 is: P4     Process P4 is completed at 21
After execution of all processes ...
PNo    AT    BT    CT    TAT    WT
1    1    2    18    17    15
2    2    4    19    17    13
3    3    6    20    17    11
4    4    8    21    17    9

Total TAT = 68
Average TAT = 17
Total WT = 48
Average WT = 12`````` 