Simple Linear Scheduling Algorithm
- Make a table of process IDs (P), shares (S), and working sets (WS)
- Make a list of permutations of processes
- Eliminate all permutations that are the same as another permutation reversed, cycled, or reversed and cycled
- Determine each permutation's time like so:
- Each Pi's runtime RTi is ≥ WSi-1 + WSi+1
- Make a table of each Pi's minimum RT, S, and RT/S
- To calculate a permutation's share length Λ:
- Find the Pi with the largest RTi / Si
- Λ = ⌈RTi / Si⌉
- The permutation's total runtime = Λ * ΣSi
- Choose the permutation with the lowest total runtime
- Let each Pi run for time Λ * Si in the order given by the permutation
Back to My Project