Scheduling algorithms in parallel computing strive to produce as good schedules as possible, yet slack is not an unusual occurrence in multiprocessor schedules. Slack refers here to the difference of the earliest and the latest possible execution start time of an available task, when a processor is available. Knowing the total slack in a schedule is an interesting indicator as it shows flexibility that is in a schedule. Slack is prominently used in slack reclamation algorithms, which attempt to save energy by using slack in combination with dynamic voltage and frequency scaling (DVFS) to slow down task execution. Such an approach is based on the premise that common task schedules have significant slack. But is that true? There is no wide knowledge or study analysing the amount and characteristic of slack in schedules of typical parallel programs.

In this paper we first investigate how slack can be identified and maximised in a given schedule. This uses existing slack reclamation algorithms, but none of them maximises slack in general. We propose a new slack reclamation algorithm, called Maximal-Antichain. Subsequently, we propose a methodology to investigate slack in schedules produced by list scheduling and cluster scheduling and undertake an extensive experimental study to examine the amount and characteristic of slack in multiprocessor schedules. We analyse the produced schedules, distinguishing between slack, idle time, and unused processors. Our findings show Maximal-Antichain identifies more slack than existing algorithms. The results also inform under which conditions slack reclamation algorithms can be efficient and when it is better to simply use less processors instead.