Start-End Scheduling Algorithm

Choosing a permutation

• List all permutations of s_i's and e_i's, with one s and one e for each process
• Eliminate all permutations where:
  • At any time, the sum of WS's of active P's won't fit in memory
  • Any e_i comes before its matching s_i
• Find the share length Λ for each remaining permutation
• Choose the permutation with the smallest Λ

Finding the share length

• Let Λ = ⌈ (ΣRI_i + ΣRO_i) / ΣS_i ⌉
• Try creating a schedule using this Λ
• If the attempt fails, double Λ and try again
• If the attempt succeeds, do a binary search between the last two checked Λ's for the smallest successful Λ

Creating the schedule

• Find the set of always-active processes. Mark them as always-active, and put them on the active list. Always-active processes do not need to be rolled in and out.
• Devote all resources (both memory and CPU) to reaching the next s or e as quickly as possible
  • To reach s_i : P_i must be completely rolled in (except if it's always-active)
  • To reach e_i : P_i must have received S_i * Λ CPU quanta, and P_i must be completely rolled out (except if it's always-active)
• If at any time the CPU is not busy with the previous step, choose the P_i on the active list with the soonest e_i, and let it run.
• Once a P_i has received S_i * Λ CPU quanta, take it off the active list.
• If at any point the CPU is left idle and there's nothing on the active list that can run, the schedule has failed for the given Λ

Finding the always-active processes

• Mark all P_i's such that s_i is before all e's and e_i is after all s's
• All marked P's are always-active

Back to My Project