shortest remaining time srt - TarisMajor/5143-OpSystems GitHub Wiki
Shortest Remaining Time (SRT), also known as Shortest Remaining Time First (SRTF), is a preemptive CPU scheduling algorithm. It is an extension of the Shortest Job Next (SJN) algorithm, but with preemption. The primary objective of SRT scheduling is to minimize the average waiting time and improve overall system performance by dynamically adjusting to the remaining execution times of processes.
- Preemptive Nature: SRT is inherently preemptive. If a new process arrives with a shorter remaining time than the currently running process, the CPU is preempted and allocated to the new process.
- Dynamic Adjustment: The algorithm continuously monitors the remaining execution times of processes and makes scheduling decisions based on these times.
- Optimal Average Waiting Time: By always selecting the process with the shortest remaining time, SRT aims to minimize the average waiting time for all processes.
- Minimized Average Waiting Time: SRT minimizes the total waiting time for all processes by preemptively allocating the CPU to the process with the shortest remaining time.
- Efficient Utilization: The algorithm ensures that the CPU is utilized efficiently by focusing on processes that can complete quickly.
- Improved Responsiveness: SRT provides better responsiveness, especially for short processes, as they are prioritized and executed quickly.
- High Context Switching Overhead: Frequent preemptions and context switches can introduce significant overhead, affecting overall system performance.
- Complex Implementation: Implementing SRT requires sophisticated algorithms to continuously monitor and compare the remaining times of processes, making it more complex than non-preemptive scheduling algorithms.
- Starvation Risk: Longer processes may experience starvation if shorter processes keep arriving, as the CPU is continually allocated to shorter jobs.
- Real-Time Systems: Suitable for real-time systems where minimizing waiting time and improving responsiveness are critical.
- Interactive Systems: Effective in interactive environments where user tasks vary in duration and require quick response times.
- Batch Processing Systems: Ideal for batch processing systems where the execution times of processes can be estimated accurately.
Consider four processes with the following burst times:
- Process P1: Burst Time = 8 units
- Process P2: Burst Time = 4 units
- Process P3: Burst Time = 9 units
- Process P4: Burst Time = 5 units
Assume that processes arrive at different times:
- P1 arrives at time 0
- P2 arrives at time 1
- P3 arrives at time 2
- P4 arrives at time 3
The SRT schedule would be:
- P1 starts at time 0 (remaining time 8 units)
- P2 arrives at time 1 (remaining time 4 units) - P1 is preempted
- P2 runs from time 1 to 5 (completes)
- P1 resumes at time 5 (remaining time 7 units)
- P4 arrives at time 3 (remaining time 5 units) - P1 is preempted
- P4 runs from time 3 to 8 (remaining time 0, completes)
- P3 arrives at time 2 (remaining time 9 units)
- P1 resumes at time 8 (remaining time 7 units)
- P1 runs from time 8 to 15 (remaining time 0, completes)
- P3 runs from time 15 to 24 (remaining time 0, completes)
The average waiting time can be calculated by summing the waiting times of all processes and dividing by the number of processes.