• About WordPress
    • WordPress.org
    • Documentation
    • Support
    • Feedback
  • Log In
  • Register
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment
Cuitutorial
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment

Operating System

Home » Blog » Shortest Remaining Time Algorithm in Operating system

Shortest Remaining Time Algorithm in Operating system

  • Posted by saqib
  • Categories Operating System
  • Date December 18, 2022
  • Comments 0 comment

Shortest Remaining Time Algorithm in Operating system

  • Shortest remaining time is the preemptive algorithm.
  • The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion.
  • In interactive systems where the necessary CPU time is unknown, SRT implementation is impossible.
  • It is frequently used in batch environments where shorter processes must be prioritized.

In SRTF, the execution of the process can be stopped after certain amount of time. At the arrival of every process, the short term scheduler schedules the process with the least remaining burst time among the list of available processes and the running process.

Once all the processes are available in the ready queue, No preemption will be done and the algorithm will work as SJF scheduling. The context of the process is saved in the Process Control Block when the process is removed from the execution and the next process is scheduled. This PCB is accessed on the next execution of this process.

In this Example, there are five jobs P1, P2, P3, P4, P5 and P6. Their arrival time and burst time are given below in the table.

Process ID Arrival Time Burst Time Completion Time Turn Around Time Waiting Time Response Time
1 0 8 20 20 12 0
2 1 4 10 9 5 1
3 2 2 4 2 0 2
4 3 1 5 2 1 4
5 4 3 13 9 6 10
6 5 2 7 2 0 5

Avg Waiting Time = 24/6

Chart is prepared according to the arrival and burst time given in the table.

  1. Since, at time 0, the only available process is P1 with CPU burst time 8. This is the only available process in the list therefore it is scheduled.
  2. The next process arrives at time unit 1. Since the algorithm we are using is SRTF which is a preemptive one, the current execution is stopped and the scheduler checks for the process with the least burst time.
    Till now, there are two processes available in the ready queue. The OS has executed P1 for one unit of time till now; the remaining burst time of P1 is 7 units. The burst time of Process P2 is 4 units. Hence Process P2 is scheduled on the CPU according to the algorithm.
  3. The next process P3 arrives at time unit 2. At this time, the execution of process P3 is stopped and the process with the least remaining burst time is searched. Since the process P3 has 2 unit of burst time hence it will be given priority over others.
  4. The Next Process P4 arrives at time unit 3. At this arrival, the scheduler will stop the execution of P4 and check which process is having least burst time among the available processes (P1, P2, P3 and P4). P1 and P2 are having the remaining burst time 7 units and 3 units respectively.

P3 and P4 are having the remaining burst time 1 unit each. Since, both are equal hence the scheduling will be done according to their arrival time. P3 arrives earlier than P4 and therefore it will be scheduled again.

  1. The Next Process P5 arrives at time unit 4. Till this time, the Process P3 has completed its execution and it is no more in the list. The scheduler will compare the remaining burst time of all the available processes. Since the burst time of process P4 is 1 which is least among all hence this will be scheduled.
  2. The Next Process P6 arrives at time unit 5, till this time, the Process P4 has completed its execution. We have 4 available processes till now, that are P1 (7), P2 (3), P5 (3) and P6 (2). The Burst time of P6 is the least among all hence P6 is scheduled. Since, now, all the processes are available hence the algorithm will now work same as SJF. P6 will be executed till its completion and then the process with the least remaining time will be scheduled.

Once all the processes arrive, No preemption is done and the algorithm will work as SJF.

Let’s discuss the question asked in GATE 2011 on SRTF.

Q. Given the arrival time and burst time of 3 jobs in the table below. Calculate the Average waiting time of the system.

Process ID Arrival Time Burst Time Completion Time Turn Around Time Waiting Time
1 0 9 13 13 4
2 1 4 5 4 0
3 2 9 22 20 11

There are three jobs P1, P2 and P3. P1 arrives at time unit 0; it will be scheduled first for the time until the next process arrives. P2 arrives at 1 unit of time. Its burst time is 4 units which is least among the jobs in the queue. Hence it will be scheduled next.

At time 2, P3 will arrive with burst time 9. Since remaining burst time of P2 is 3 units which are least among the available jobs. Hence the processor will continue its execution till its completion. Because all the jobs have been arrived so no preemption will be done now and all the jobs will be executed till the completion according to SJF.

  • Share:
author avatar
saqib

Previous post

Priority Based Scheduling Algorithm in Operating system
December 18, 2022

Next post

List view Builder in Flutter
December 20, 2022

You may also like

Aging in operating system
6 January, 2023

Aging in operating system In Operating systems, Aging is a scheduling technique used to avoid Starvation. Fixed priority scheduling is a scheduling discipline in which tasks queued for utilizing a system resource is assigned each priority. A task with a …

Starvation in operating system
6 January, 2023

Starvation in operating system It is a problem when the low-priority process gets jammed for a long duration of time because of high-priority requests being executed. A stream of high-priority requests stops the low-priority process from obtaining the processor or …

Dead Lock in operating system
3 January, 2023

Dead Lock in operating system A Deadlock is a situation where each of the computer process waits for a resource which is being assigned to some another process. In this situation, none of the process gets executed since the resource …

Leave A Reply Cancel reply

You must be logged in to post a comment.

admin@cuitutorial.com
Facebook-f Twitter Youtube Linkedin Instagram Stack-overflow Pinterest Github Quora Whatsapp
Courses
  • All Courses
  • Past Paper
  • Final year projects
  • Interview Questions
  • Contact
Important Pages
  • Privacy Policy
  • Terms of Service
  • Cookie Policy
Links
  • University Events
  • Team
Education & learning platform for All Computer science subjects
Final year projects
Past Paper
Interview questions
Programming, C/C++, Asp.net/MVC. Android, MySql, Jquery, Ajax, javascript, Php, Html5, Bootstrap4.
NTS, GAT, PPSC, FPSC

Copyright © 2021 | Cuitutorial