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 P_i's runtime RT_i is ≥ WS_i-1 + WS_i+1
  • Make a table of each P_i's minimum RT, S, and RT/S
  • To calculate a permutation's share length Λ:
    • Find the P_i with the largest RT_i / S_i
    • Λ = ⌈RT_i / S_i⌉
  • The permutation's total runtime = Λ * ΣS_i
• Choose the permutation with the lowest total runtime
• Let each P_i run for time Λ * S_i in the order given by the permutation

Back to My Project