I was thinking about the problem I was seeing, and I came up with a simple scenario to demonstrate the problem.
Computer is a Dual CPU system (single CPU system won't do, and more is unneeded to show the problem. Connect Every X is 0.0 Extra work is 0.1 Switch tasks is 10 minutes. Project A has multi CPU tasks that schedule all available CPUs. All other projects are single CPU tasks. Equal resource shares. Task 1 Project A: 500 hours run time (1000 hours CPU time). 510 hours till deadline. This task is going to be in EDF for the duration of the example. Task 2 Project B: 1 minute CPU time remaining. 10 hours till deadline. 50 hours CPU already done. Task 3 Project C: 2 minutes CPU time remaining. 20 hours till deadline. 50 hours CPU already done. Task 4 Project D: 2 minutes CPU time remaining. 30 hours till deadline. 50 hours CPU already done. Task 5 Project E: 2 minutes CPU time remaining. 40 hours till deadline. 50 hours CPU already done. Task 6 Project F: 2 minutes CPU time remaining. 50 hours till deadline. 50 hours CPU already done None of Task 2 through 6 is in deadline trouble at the start. 16 minutes before the deadline of Task 2, it becomes in danger of missing the deadline (RR). However, Task 1 is a multi CPU app, that is in deadline danger. No task switch is indicated. 11 minutes before the deadline of Task 2, it becomes in danger of missing the deadline (EDF). However, Task 1 is a multi CPU app, and is still in deadline danger. No task switch is indicated. Task 2 passes the deadline without getting any CPU time. It is still in deadline danger. 16 minutes before the deadline of Task 3, it becomes in danger of missing the deadline. Tasks 2 and 3 now get to run. 15 minutes before the deadline of Task 3, Task 2 completes. Task 3 still has 1 minute of CPU time remaining. Task 1 is in deadline danger and pre-empts Task 3. Task 2 is completed 9 hours, 45 minutes late. Upload takes a minute. It is reported 9 hours and 46 minutes late. 15 minutes before the deadline of Task 4, it becomes in danger of missing the deadline. Tasks 3 and 4 now get to run. 14 minutes before the deadline of Task 4, Task 3 completes. Task 4 still has 1 minute of CPU time remaining. Task 1 is in deadline danger and pre-empts Task 4. Task 3 is completed 9 hours, 46 minutes late. Upload takes a minute. It is reported 9 hours and 47 minutes late. 14 minutes before the deadline of Task 5, it becomes in danger of missing the deadline. Tasks 4 and 5 now get to run. 13 minutes before the deadline of Task 5, Task 4 completes. task 5 still has 1 minute of CPU time remaining. task 1 is in deadline danger and pre-empts task 5. Task 4 is completed 9 hours, 47 minutes late. Upload takes a minute. It is reported 9 hours and 48 minutes late. 13 minutes before the deadline of Task 6, it becomes in danger of missing the deadline. Tasks 5 and 6 now get to run. 12 minutes before the deadline of Task 6, Task 5 completes. Task 6 still has 1 minute of CPU time remaining. Task 1 is in deadline danger and preempts task 6. Task 5 is completed 9 hours 48 minutes late. Upload takes a minute. It is reported 9 hours and 49 minutes late. Task 6 will not get to run until Task 1 completes. It will complete 450 hours 6 minutes late. It will take 1 minute to upload. It will report 450 hours 7 minutes late. Tasks 6 will certainly be declared worthless by the project. Tasks 2 through 5 at least have a chance of not being declared worthless, but could very well be declared worthless if they were replacements. So somewhere between 50 and 250 hours of CPU time will be thrown out as worthless with the current code. Alternative: 16 minutes before the deadline of Task 2, it becomes in danger of missing the deadline (RR). Task 1 is pre-empted (note that the task pre-emption may wait till EDF miss is indicated with no problem). Task 2 and Task 3 are started. (It could be any of the other tasks). 15 minutes before the deadline of Task 2 it completes. Task 1 preempts Task 3. Task 3 has 1 minute remaining. Task 2 upload takes 1 minute. 14 minutes before Task 2 deadline it is reported. 15 minutes before the deadline of Task 3, it becomes in danger of missing the deadline (RR). Task 1 is pre-empted (note that the task pre-emption may wait till EDF miss is indicated with no problem). Task 3 and Task 4 are started. (It could be any of the other tasks). 14 minutes before the deadline of Task 3 it completes. Task 1 preempts Task 3. Task 3 has 1 minute remaining. Task 3 upload takes 1 minute. 14 minutes before Task 3 deadline it is reported. 14 minutes before the deadline of Task 4, it becomes in danger of missing the deadline (RR). Task 1 is pre-empted (note that the task pre-emption may wait till EDF miss is indicated with no problem). Task 4 and Task 5 are started. (It could be any of the other tasks). 13 minutes before the deadline of Task 4 it completes. Task 1 preempts Task 5. Task 5 has 1 minute remaining. Task 4 upload takes 1 minute. 13 minutes before Task 3 deadline it is reported. 13 minutes before the deadline of Task 5, it becomes in danger of missing the deadline (RR). Task 1 is pre-empted (note that the task pre-emption may wait till EDF miss is indicated with no problem). Task 5 and Task 6 are started. (It could be any of the other tasks). 12 minutes before the deadline of Task 5 it completes. Task 1 preempts Task 6. Task 6 has 1 minute remaining. Task 2 upload takes 1 minute. 14 minutes before Task 2 deadline it is reported. 12 minutes before the deadline of Task 6, it becomes in danger of missing the deadline (RR). Task 1 is pre-empted (note that the task pre-emption may wait till EDF miss is indicated with no problem). Task 6 is started. Note that there is under use of resources here unless there is yet another task with a longer deadline than task 1. However, the deadline for Task 6 is met instead of having it be reported 450 hours or so late. 11 minutes before the deadline of Task 6 it completes. Task 1 starts and resumes. Task 6 upload takes 1 minute. 10 minutes before Task 2 deadline it is reported. Task 1 continues to run alone till near the end of its report time. It will complete and report a few hours before its deadline. jm7 _______________________________________________ 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.
