LRTF Algorithm
The Longest Remaining time First(LRTF) scheduling is the preemptive version of Longest Job First(LJF)
scheduling. This scheduling algorithm is used by the operating system in order to schedule incoming
processes so that they can be executed in a systematic way. With this algorithm, the process having the
maximum remaining time is processed first. In this, we will check for the maximum remaining time after an
interval of time(say 1 unit) that is there another process having more Burst Time arrived up to that time.
Characteristics
- It is a CPU scheduling algorithm that is used to determine the process to be executed first among all
incoming processes in a systematic way.
- This algorithm follows the preemptive approach because in this CPU is allocated to any process only for
a fixed slice of time.
- In this algorithm, processes are selected on the basis of the highest burst time(the one with the
highest burst time is processed first) and this process runs till the fixed slice of time. After that,
the selection process takes place again.
- Due to the high value of the average waiting time, this algorithm is not optimal.
Advantages
- This algorithm is easy to implement and simple
- This algorithm is starvation-free because all processes get a fair share of CPU.
- All the processes get completed by the time the longest job reaches its completion.
Disadvantages
- With this algorithm, the average waiting time and turnaround time are too high, even if burst time is
less for each process.
- In this process with less burst time(smaller processes) need to wait for CPU in order to finish
processes with larger burst size.
- The valuable time of CPU is consumed by context switch; which can be utilized for the execution of
processes.
- Not an ideal technique for time-sharing systems.
- Because of its simplicity, FCFS is not very efficient.
Example
| Process |
Arrival Time |
Burst Time |
| P1 |
0 |
3 |
| P2 |
1 |
6 |
| P3 |
3 |
2 |
| P4 |
5 |
3 |
Working
- The First step is to sort the processes according to their Arrival time in increasing order
- The next step is to choose the process that least arrival time but having the most Burst Time. After
that process it for 1 unit. After one unit you need to check if up to that time of execution; any other
process is arrived or not
- Just repeat the above steps until the execution of all processes.
Gantt Chart
| P1 |
P2 |
P2 |
P2 |
P2 |
P4 |
P1 |
P2 |
P3 |
P4 |
P1 |
P2 |
P3 |
P4 |
| 0-1 |
1-2 |
2-3 |
3-4 |
4-5 |
5-6 |
6-7 |
7-8 |
8-9 |
9-10 |
10-11 |
11-12 |
12-13 |
13-14 |
Final Table
| process |
Arrival Time |
Burst Time |
Complition Time |
Turn Around Time |
Waiting Tme |
Response Time |
| P1 |
0 |
3 |
11 |
11 |
8 |
0 |
| P2 |
1 |
6 |
12 |
11 |
5 |
0 |
| P3 |
3 |
2 |
13 |
10 |
8 |
5 |
| P4 |
5 |
3 |
14 |
9 |
6 |
0 |