[email protected] wrote: > I was thinking about the problem I was seeing, and I came up with a simple > scenario to demonstrate the problem. > ...
The underlying problem is that bin-packing (or multiprocessor scheduling) is NP-complete. EDF is non-optimal in some cases on multiprocessors. No matter what scheduling policy we use (short of exponential-time exhaustive search) there will be scenarios where it misses deadlines that could be met by some other schedule. This problem exists whether or not there are multi-CPU jobs. In the example you give, suppose we reach the point where we have a multi-CPU job and a 1-CPU both in deadline trouble. Things work out better if we run the 1-CPU job. But how do we know this? What policy says so? If there is such a policy, how do we know it doesn't fail disastrously in other scenarios? _______________________________________________ boinc_dev mailing list [email protected] http://lists.ssl.berkeley.edu/mailman/listinfo/boinc_dev To unsubscribe, visit the above URL and (near bottom of page) enter your email address.
