Start-End Scheduling Algorithm
Choosing a permutation
- List all permutations of si's and ei'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 ei comes before its matching si
- Find the share length Λ for each remaining permutation
- Choose the permutation with the smallest Λ
Finding the share length
- Let Λ = ⌈ (ΣRIi + ΣROi) / ΣSi ⌉
- 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 si : Pi must be completely rolled in (except if it's always-active)
- To reach ei : Pi must have received Si * Λ CPU quanta, and Pi 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 Pi on the active list with the soonest ei, and let it run.
- Once a Pi has received Si * Λ 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 Pi's such that si is before all e's and ei is after all s's
- All marked P's are always-active
Back to My Project