diff options
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/DynSched.cpp | 580 | ||||
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/DynSched.h | 45 | ||||
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/DynSched.i | 12 | ||||
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/SchedEntry.cpp | 74 | ||||
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/SchedEntry.h | 21 | ||||
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/SchedEntry.i | 23 | ||||
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.cpp | 373 | ||||
| -rw-r--r-- | TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.h | 60 |
8 files changed, 935 insertions, 253 deletions
diff --git a/TAO/orbsvcs/orbsvcs/Sched/DynSched.cpp b/TAO/orbsvcs/orbsvcs/Sched/DynSched.cpp index 20a30804b33..95b19655431 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/DynSched.cpp +++ b/TAO/orbsvcs/orbsvcs/Sched/DynSched.cpp @@ -16,8 +16,8 @@ // // ============================================================================ -#include <math.h> -#include <float.h> +#include "math.h" +#include "float.h" #include "ace/Sched_Params.h" #include "DynSched.h" @@ -138,6 +138,7 @@ ACE_Scheduler::ACE_Scheduler () , thread_delineators_ (0) , ordered_thread_dispatch_entries_ (0) , dispatch_entries_ (0) + , expanded_dispatches_ (0) , ordered_dispatch_entries_ (0) , dispatch_entry_count_ (0) , threads_ (0) @@ -158,7 +159,8 @@ ACE_Scheduler::ACE_Scheduler () , minimum_guaranteed_priority_queue_ (-1) , timeline_ (0) , up_to_date_ (0) - + , min_dispatch_id_ (0) + , max_dispatch_id_ (0) { } @@ -440,6 +442,24 @@ ACE_Scheduler::reset () dispatch_entries_ = 0; } + if (expanded_dispatches_) + { + // free all the dispatch entries in the list, then the list itself + ACE_Unbounded_Set_Iterator <Dispatch_Entry *> expanded_iter (*expanded_dispatches_); + Dispatch_Entry **expanded_entry = 0; + for (expanded_iter.first (); ! expanded_iter.done (); + expanded_iter.advance (), expanded_entry = 0) + { + if ((expanded_iter.next (expanded_entry) != 0) && + (expanded_entry) && (*expanded_entry)) + { + delete (*expanded_entry); + } + } + delete expanded_dispatches_; + expanded_dispatches_ = 0; + } + delete [] ordered_dispatch_entries_; ordered_dispatch_entries_ = 0; @@ -478,6 +498,8 @@ ACE_Scheduler::reset () ACE_Scheduler::status_t ACE_Scheduler::schedule (void) { + status_t temp_status = SUCCEEDED; + ACE_Guard<LOCK> ace_mon (lock_); if (up_to_date_) @@ -538,16 +560,25 @@ ACE_Scheduler::schedule (void) // generate the scheduling timeline over the total frame size if ((status_ == SUCCEEDED) || (status_ == ST_UTILIZATION_BOUND_EXCEEDED)) { - status_ = create_timeline (); + temp_status = create_timeline (); + } + + if (temp_status != SUCCEEDED) + { + status_ = temp_status; } // store the timeline to a file if one was given if ((timeline_filename_ != 0) && ((status_ == SUCCEEDED) || (status_ == ST_UTILIZATION_BOUND_EXCEEDED))) { - status_ = output_timeline (timeline_filename_, 0); + temp_status = output_timeline (timeline_filename_, 0); } + if (temp_status != SUCCEEDED) + { + status_ = temp_status; + } // if a valid schedule was not generated, clean up from the attempt switch (status_) @@ -597,16 +628,31 @@ ACE_Scheduler::schedule (void) ACE_Scheduler::status_t ACE_Scheduler::propagate_dispatches () { + u_long i; + frame_size_ = 1; + // iterate through the ordered_task_entries_ array in order // from highest DFS finishing time to lowest, so that every // calling dispatch is accessed before those it calls: // the dispatches propagate top down through the call DAG - for (u_int i = 0; i < tasks (); ++i) + for (i = 0; i < tasks (); ++i) { if (ordered_task_entries_ [i]->merge_dispatches (*dispatch_entries_) < 0) { return ST_UNKNOWN_TASK; } + + if (ordered_task_entries_ [i]->effective_period () > 0) + { + frame_size_ = + minimum_frame_size (frame_size_, + ordered_task_entries_ [i]->effective_period ()); + } + else + { + return ST_UNKNOWN_TASK; + } + } return SUCCEEDED; @@ -615,15 +661,9 @@ ACE_Scheduler::propagate_dispatches () // threads throughout the call graph - ACE_Scheduler::status_t ACE_Scheduler::calculate_utilization_params (void) { - status_t status = SUCCEEDED; - - frame_size_ = - ordered_dispatch_entries_ [0]->task_entry ().effective_period (); - critical_set_frame_size_ = 0; utilization_ = 0.0; critical_set_utilization_ = 0.0; @@ -634,12 +674,8 @@ ACE_Scheduler::calculate_utilization_params (void) minimum_guaranteed_priority_queue_ = -1; // iterate through ordered task entries, calculating frame size, utilization - for (u_int i = 1; i < dispatch_entry_count_; ++i) + for (u_int i = 0; i < dispatch_entry_count_; ++i) { - // hold the effective period of the task entry to which the dispatch refers - Period period = - ordered_dispatch_entries_ [i]->task_entry ().effective_period (); - // if we've just finished examining another priority level if (minimum_priority_queue_ != ordered_dispatch_entries_ [i]->priority ()) { @@ -651,39 +687,37 @@ ACE_Scheduler::calculate_utilization_params (void) } // only consider computation times of dispatches on OPERATION descriptors - if (ordered_dispatch_entries_ [i]->task_entry ().info_type () == - RtecScheduler::OPERATION) + if ((ordered_dispatch_entries_ [i]->task_entry ().info_type () == + RtecScheduler::OPERATION) && + (ordered_dispatch_entries_ [i]->task_entry ().effective_period () > 0)) { utilization_ += ACE_static_cast(double, ordered_dispatch_entries_ [i]-> task_entry ().rt_info ()-> worst_case_execution_time) / - ACE_static_cast(double, period); - - } + ACE_static_cast(double, + ordered_dispatch_entries_ [i]-> + task_entry ().effective_period ()); - if (period) - { - // grow frame size by new factors that are not in gcd of the - // frame size and the newly considered entry's effective period - frame_size_ = - minimum_frame_size (frame_size_, period); } } // update parameters for the lowest priority level update_priority_level_params (); - return status; + // if the critical set is schedulable, return success + return (1.0 - critical_set_utilization_ > DBL_EPSILON) + ? SUCCEEDED : ST_UTILIZATION_BOUND_EXCEEDED; } + void ACE_Scheduler::update_priority_level_params () { - // if we've just finished examining the lowest critical priority level - if (minimum_priority_queue_ == minimum_critical_priority ()) + // if we've just finished examining a critical priority level + if (minimum_priority_queue_ <= minimum_critical_priority ()) { // update the information about the critical set critical_set_frame_size_ = frame_size_; @@ -1073,101 +1107,138 @@ ACE_Scheduler::schedule_dispatches (void) ACE_Scheduler::status_t ACE_Scheduler::create_timeline () { + // queue of previously scheduled entries that need to be rescheduled + ACE_Unbounded_Queue <Dispatch_Entry *> reschedule_queue; + + status_t status = SUCCEEDED; ACE_NEW_RETURN(timeline_, ACE_Ordered_MultiSet <TimeLine_Entry_Link>, + ST_VIRTUAL_MEMORY_EXHAUSTED); + + ACE_NEW_RETURN(expanded_dispatches_, ACE_Unbounded_Set <Dispatch_Entry *>, ST_VIRTUAL_MEMORY_EXHAUSTED); - for (u_int i = 0; i < dispatch_entry_count_; ++i) + // start with the id of the first entry in the array + min_dispatch_id_ = ordered_dispatch_entries_[0]->dispatch_id (); + max_dispatch_id_ = ordered_dispatch_entries_[0]->dispatch_id (); + + for (u_long i = 0; i < dispatch_entry_count_; ++i) { + // update the minimal and maximal id values for the schedule + if (ordered_dispatch_entries_[i]->dispatch_id () < min_dispatch_id_) + { + min_dispatch_id_ = ordered_dispatch_entries_[i]->dispatch_id (); + } + if (ordered_dispatch_entries_[i]->dispatch_id () > max_dispatch_id_) + { + max_dispatch_id_ = ordered_dispatch_entries_[i]->dispatch_id (); + } + // only put OPERATION dispatches into the timeline. if (ordered_dispatch_entries_[i]->task_entry().info_type () != RtecScheduler::OPERATION) { continue; } - - // timeline entries cover the execution time of the dispatch - u_long remaining_time = - ordered_dispatch_entries_[i]->task_entry().rt_info ()-> - worst_case_execution_time; - - // initialize last stop time to beginning of frame - u_long last_stop = 0; + // schedule the current dispatch entry into the timeline + status = schedule_timeline_entry (*(ordered_dispatch_entries_[i]), + reschedule_queue); + if (status != SUCCEEDED) + { + break; + } - TimeLine_Entry *last_entry = 0; - TimeLine_Entry *current_entry = 0; - ACE_Ordered_MultiSet_Iterator <TimeLine_Entry_Link> iter (*timeline_); - for (iter.first (); (remaining_time > 0) && (iter.done () == 0); - iter.advance ()) + // iterate through the set of dispatch entries that need to be rescheduled + Dispatch_Entry *rescheduled_entry; + while (reschedule_queue.is_empty () == 0) { - TimeLine_Entry_Link *link; - if ((iter.next (link) == 0) || (! link)) + + if (reschedule_queue.dequeue_head (rescheduled_entry) < 0) { - return ST_BAD_INTERNAL_POINTER; + status = ST_UNKNOWN_TASK; + break; } - - // if there's room, schedule a new timeline entry for the dispatch - if (link->entry ().start() > last_stop) + + status = schedule_timeline_entry (*rescheduled_entry, reschedule_queue); + if (status != SUCCEEDED) { - ACE_NEW_RETURN ( - current_entry, - TimeLine_Entry ( - *(ordered_dispatch_entries_[i]), - last_stop, - (((remaining_time + last_stop) < link->entry ().start()) - ? (remaining_time + last_stop) : link->entry ().start()), - 0, last_entry), - ST_VIRTUAL_MEMORY_EXHAUSTED); - - // patch up the pointers within the list of entries for this dispatch - if (last_entry) - { - last_entry->next (current_entry); - } - last_entry = current_entry; - - timeline_->insert(TimeLine_Entry_Link(*current_entry)); - - // update the remaining time and last stop values - remaining_time -= ((remaining_time < (link->entry ().start() - last_stop)) - ? remaining_time : (link->entry ().start() - last_stop)); - } + break; + } + } + if (status != SUCCEEDED) + { + break; + } - // update the last stop time - last_stop = link->entry ().stop (); - } - // if there is still dispatch time remaining, and we've - // reached the end of the list, insert what's left - if (remaining_time > 0) + // schedule additional dispatcheds of the entry + // over the total frame size into the timeline + u_long current_frame_offset = 0; + u_long task_period = + ordered_dispatch_entries_[i]->task_entry ().effective_period (); + for (current_frame_offset = task_period; + current_frame_offset < frame_size_; + current_frame_offset += task_period) { + Dispatch_Entry *new_dispatch_entry; + + // create a new dispatch entry at the current sub-frame offset ACE_NEW_RETURN ( - current_entry, - TimeLine_Entry ( - *(ordered_dispatch_entries_[i]), - last_stop, - remaining_time + last_stop, - 0, last_entry), + new_dispatch_entry, + Dispatch_Entry (ordered_dispatch_entries_[i]->arrival () + + current_frame_offset, + ordered_dispatch_entries_[i]->deadline () + + current_frame_offset, + ordered_dispatch_entries_[i]->priority (), + ordered_dispatch_entries_[i]->task_entry (), + ordered_dispatch_entries_[i]), ST_VIRTUAL_MEMORY_EXHAUSTED); - - // patch up the pointers within the list of entries for this dispatch - if (last_entry) + + // add the new dispatch entry to the set of expanded dispatches + expanded_dispatches_->insert (new_dispatch_entry); + + // schedule the new dispatch entry into the timeline + status = schedule_timeline_entry (*new_dispatch_entry, reschedule_queue); + if (status != SUCCEEDED) { - last_entry->next (current_entry); + break; } - timeline_->insert(TimeLine_Entry_Link(*current_entry)); + while (reschedule_queue.is_empty () == 0) + { + + if (reschedule_queue.dequeue_head (rescheduled_entry) < 0) + { + status = ST_UNKNOWN_TASK; + break; + } + status = schedule_timeline_entry (*rescheduled_entry, reschedule_queue); + if (status != SUCCEEDED) + { + break; + } + } + if (status != SUCCEEDED) + { + break; + } } + if (status != SUCCEEDED) + { + break; + } } - return SUCCEEDED; + return status; } // Create a timeline. + + ACE_Scheduler::status_t -ACE_Scheduler::output_dispatch_timeline (const char *filename) +ACE_Scheduler::output_dispatch_priorities (const char *filename) { status_t status = UNABLE_TO_OPEN_SCHEDULE_FILE; @@ -1175,37 +1246,96 @@ ACE_Scheduler::output_dispatch_timeline (const char *filename) FILE *file = ACE_OS::fopen (filename, "w"); if (file) { - status = output_dispatch_timeline (file); + status = output_dispatch_priorities (file); fclose (file); } return status; } + ACE_Scheduler::status_t -ACE_Scheduler::output_dispatch_timeline (FILE *file) +ACE_Scheduler::output_dispatch_priorities (FILE *file) { + + u_long dispatch_count = 0; + u_long i = 0; + for (i = 0; i < dispatch_entry_count_; ++i) + { + dispatch_count += frame_size_ / ordered_dispatch_entries_[i]->task_entry ().effective_period (); + } + if (ACE_OS::fprintf ( file, "\n\nSCHEDULING RESULTS:\n\n" - "Number of dispatches: %u\n" - "Number of threads: %u\n" - "Number of tasks: %u\n" - "Scheduler Status: [%d] %s\n" - "Total Frame Size: %lu nsec (%lf Hz)\n" - "Critical Set Frame Size: %lu nsec (%lf Hz)\n" - "Utilization: %lf\n" - "Critical Set Utilization: %lf\n" - "Minimum Priority Queue: %ld\n" - "Minimum Guaranteed Priority Queue: %ld\n\n\n" - "DISPATCH TIMELINE:\n\n" - " dispatch dynamic static arrival deadline start stop execution\n" - "operation ID priority subpriority subpriority (nsec) (nsec) (nsec) (nsec) time (nsec)\n" - "--------- -------- -------- ----------- ----------- ------- -------- ----- ------ -----------\n\n", - dispatch_entry_count_, threads_, tasks_, status_, + "Number of dispatches: %3u\n" + "Number of threads: %3u\n" + "Number of tasks: %3u\n" + "Scheduler Status: [%d] %s\n" + "Total Frame Size: %lu nsec (%lf Hz)\n" + "Critical Set Frame Size: %lu nsec (%lf Hz)\n" + "Utilization: %lf\n" + "Critical Set Utilization: %lf\n" + "Minimum Priority Queue: %3ld\n" + "Minimum Guaranteed Priority Queue: %3ld\n" + "Minimum Critical Priority: %3ld\n\n\n" + + "DISPATCH PRIORITIES:\n\n" + " (critical \n" + " instant) \n" + " dispatch dynamic static \n" + "operation ID priority subpriority subpriority\n" + "--------- -------- -------- ----------- -----------\n", + dispatch_count, threads_, tasks_, status_, status_message(status_), frame_size_, (double) (10000000.0 / ((double) frame_size_)), critical_set_frame_size_, (double) (10000000.0 / ((double) critical_set_frame_size_)), utilization_, critical_set_utilization_, minimum_priority_queue_, - minimum_guaranteed_priority_queue_) < 0) + minimum_guaranteed_priority_queue_, minimum_critical_priority ()) < 0) + + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } + + for (i = 0; i < dispatch_entry_count_; ++i) + { + if (ACE_OS::fprintf (file, "%-11s %8lu %8lu %11lu %11lu\n", + ordered_dispatch_entries_[i]->task_entry ().rt_info ()->entry_point, + ordered_dispatch_entries_[i]->dispatch_id (), + ordered_dispatch_entries_[i]->priority (), + ordered_dispatch_entries_[i]->dynamic_subpriority (), + ordered_dispatch_entries_[i]->static_subpriority ()) < 0) + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } + } + + return SUCCEEDED; +} + + +ACE_Scheduler::status_t +ACE_Scheduler::output_dispatch_timeline (const char *filename) +{ + status_t status = UNABLE_TO_OPEN_SCHEDULE_FILE; + + // open the file + FILE *file = ACE_OS::fopen (filename, "w"); + if (file) + { + status = output_dispatch_timeline (file); + fclose (file); + } + + return status; +} + +ACE_Scheduler::status_t +ACE_Scheduler::output_dispatch_timeline (FILE *file) +{ + if (ACE_OS::fprintf ( + file, "\n\nDISPATCH TIMELINE:\n\n" + " dispatch arrival deadline start stop execution latency laxity\n" + "operation ID (nsec) (nsec) (nsec) (nsec) time (nsec) (nsec) (nsec)\n" + "--------- ----------- ------- -------- ----- ------ ----------- ------- ------\n") < 0) { return UNABLE_TO_WRITE_SCHEDULE_FILE; } @@ -1222,7 +1352,7 @@ ACE_Scheduler::output_dispatch_timeline (FILE *file) return ST_BAD_INTERNAL_POINTER; } - // for each timeline entry that starts a new dispatch + // for each timeline entry that starts a dispatch if (link->entry ().prev () == 0) { // find the last time slice for the dispatch @@ -1230,28 +1360,54 @@ ACE_Scheduler::output_dispatch_timeline (FILE *file) while (last_entry->next ()) { last_entry = last_entry->next (); - } + } - if (ACE_OS::fprintf ( - file, "%-9s %8lu %8lu %11lu %11lu %7lu %8lu %8lu %8lu %10lu\n", - link->entry ().dispatch_entry ().task_entry ().rt_info ()-> - entry_point, - link->entry ().dispatch_entry ().dispatch_id (), - link->entry ().dispatch_entry ().priority (), - link->entry ().dispatch_entry ().dynamic_subpriority (), - link->entry ().dispatch_entry ().static_subpriority (), - link->entry ().dispatch_entry ().arrival (), - link->entry ().dispatch_entry ().deadline (), - link->entry ().start (), last_entry->stop (), - link->entry ().dispatch_entry ().task_entry ().rt_info ()-> - worst_case_execution_time) < 0) + if (link->entry ().dispatch_entry ().original_dispatch ()) + { + if (ACE_OS::fprintf ( + file, "%-11s [%4lu] %4lu %7lu %8lu %8lu %10lu %11lu %10ld %10ld\n", + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + entry_point, + link->entry ().dispatch_entry ().original_dispatch ()->dispatch_id (), + link->entry ().dispatch_entry ().dispatch_id (), + link->entry ().arrival (), + link->entry ().deadline (), + link->entry ().start (), last_entry->stop (), + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + worst_case_execution_time, + last_entry->stop () - link->entry ().arrival () - + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + worst_case_execution_time, + link->entry ().deadline () - last_entry->stop ()) < 0) + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } + } + else { - return UNABLE_TO_WRITE_SCHEDULE_FILE; + if (ACE_OS::fprintf ( + file, "%-11s %11lu %7lu %8lu %8lu %10lu %11lu %10ld %10ld\n", + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + entry_point, + link->entry ().dispatch_entry ().dispatch_id (), + link->entry ().arrival (), + link->entry ().deadline (), + link->entry ().start (), last_entry->stop (), + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + worst_case_execution_time, + last_entry->stop () - link->entry ().arrival () - + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + worst_case_execution_time, + link->entry ().deadline () - last_entry->stop ()) < 0) + + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } } } } - + return SUCCEEDED; } // this prints the entire set of timeline outputs to the specified file @@ -1277,9 +1433,9 @@ ACE_Scheduler::output_preemption_timeline (FILE *file) { if (ACE_OS::fprintf ( file, "\n\nPREEMPTION TIMELINE:\n\n" - " start stop\n" - "operation dispatch id (nsec) (nsec)\n" - "--------- ----------- ------ ------\n\n") < 0) + " dispatch start stop \n" + "operation ID (nsec) (nsec)\n" + "--------- ----------- ------ ------\n") < 0) { return UNABLE_TO_WRITE_SCHEDULE_FILE; } @@ -1294,21 +1450,155 @@ ACE_Scheduler::output_preemption_timeline (FILE *file) return ST_BAD_INTERNAL_POINTER; } - if (ACE_OS::fprintf ( - file, "%-9s %11lu %8lu %8lu\n", - link->entry ().dispatch_entry ().task_entry ().rt_info ()-> - entry_point, - link->entry ().dispatch_entry ().dispatch_id (), - link->entry ().start (), - link->entry ().stop ()) < 0) + if (link->entry ().dispatch_entry ().original_dispatch ()) { - return UNABLE_TO_WRITE_SCHEDULE_FILE; + if (ACE_OS::fprintf ( + file, "%-9s [%4lu] %4lu %8lu %8lu\n", + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + entry_point, + link->entry ().dispatch_entry ().original_dispatch ()->dispatch_id (), + link->entry ().dispatch_entry ().dispatch_id (), + link->entry ().start (), + link->entry ().stop ()) < 0) + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } + } + else + { + if (ACE_OS::fprintf ( + file, "%-9s %11lu %8lu %8lu\n", + link->entry ().dispatch_entry ().task_entry ().rt_info ()-> + entry_point, + link->entry ().dispatch_entry ().dispatch_id (), + link->entry ().start (), + link->entry ().stop ()) < 0) + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } } } return SUCCEEDED; } - // this prints the entire set of timeline outputs to the specified file + + +ACE_Scheduler::status_t +ACE_Scheduler::output_viewer_timeline (const char *filename) +{ + status_t status = UNABLE_TO_OPEN_SCHEDULE_FILE; + + // open the file + FILE *file = ACE_OS::fopen (filename, "w"); + if (file) + { + status = output_dispatch_timeline (file); + fclose (file); + } + + return status; +} + +ACE_Scheduler::status_t +ACE_Scheduler::output_viewer_timeline (FILE *file) +{ + if (ACE_OS::fprintf ( + file, "\n\nVIEWER TIMELINE:\n\n" + " arrival deadline completion execution \n" + "operation utilization overhead (nsec) (nsec) time (nsec) time (nsec)\n" + "--------- ----------- -------- ------- -------- ----------- -----------\n") < 0) + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } + + // iterate through timeline, picking out dispatches in chronological + // order of operation completion time + int entries_remain = 1; + u_long accumulated_execution = 0; + u_long current_accumulated_execution = 0; + u_long last_completion = 0; + u_long current_completion = 0; + TimeLine_Entry *current_entry = 0; + TimeLine_Entry *current_last_entry = 0; + + while (entries_remain) + { + last_completion = current_completion; + + accumulated_execution = 0; + current_accumulated_execution = 0; + current_completion = 0; + current_entry = 0; + current_last_entry = 0; + + ACE_Ordered_MultiSet_Iterator <TimeLine_Entry_Link> iter (*timeline_); + for (iter.first (); iter.done () == 0; iter.advance ()) + { + TimeLine_Entry_Link *link; + if ((iter.next (link) == 0) || (! link)) + { + return ST_BAD_INTERNAL_POINTER; + } + + accumulated_execution += link->entry ().stop () - + link->entry ().start (); + + // for each timeline entry that starts a dispatch + if (link->entry ().prev () == 0) + { + // find the last time slice for the dispatch + TimeLine_Entry *last_entry = &(link->entry ()); + while (last_entry->next ()) + { + last_entry = last_entry->next (); + } + + if ((last_entry->stop () > last_completion) && + ((last_entry->stop () < current_completion) || + (current_completion == 0))) + { + current_completion = last_entry->stop (); + current_entry = &(link->entry ()); + current_last_entry = last_entry; + } + } + + // save the accumulated execution if we're at + // the last entry for the current dispatch + if (current_last_entry == &(link->entry ())) + { + current_accumulated_execution = accumulated_execution; + } + } + + // if we found another entry, print it (otherwise we're done) + if (current_entry) + { + if (ACE_OS::fprintf ( + file, "%-11s %9lf %9lf %8lu %8lu %11lu %11lu\n", + current_entry->dispatch_entry ().task_entry ().rt_info ()-> + entry_point, + (double) (((double) current_accumulated_execution) / + ((double) current_completion)), + 0.0, + current_entry->arrival (), + current_entry->deadline (), + current_last_entry->stop (), + current_entry->dispatch_entry ().task_entry ().rt_info ()-> + worst_case_execution_time) < 0) + { + return UNABLE_TO_WRITE_SCHEDULE_FILE; + } + } + else + { + entries_remain = 0; + } + } + + return SUCCEEDED; +} + ACE_Scheduler::status_t ACE_Scheduler::output_timeline (const char *filename, const char *heading) @@ -1342,6 +1632,11 @@ ACE_Scheduler::output_timeline (const char *filename, const char *heading) if (status == SUCCEEDED) { + status = output_dispatch_priorities (file); + } + + if (status == SUCCEEDED) + { status = output_dispatch_timeline (file); } @@ -1350,6 +1645,11 @@ ACE_Scheduler::output_timeline (const char *filename, const char *heading) status = output_preemption_timeline (file); } + if (status == SUCCEEDED) + { + status = output_viewer_timeline (file); + } + if (file) { fclose (file); diff --git a/TAO/orbsvcs/orbsvcs/Sched/DynSched.h b/TAO/orbsvcs/orbsvcs/Sched/DynSched.h index 999c5b41d65..b88a6829196 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/DynSched.h +++ b/TAO/orbsvcs/orbsvcs/Sched/DynSched.h @@ -30,7 +30,7 @@ class TAO_ORBSVCS_Export ACE_Scheduler // = TITLE - // Thread scheduler interface. + // dispatch scheduling interface. // // = DESCRIPTION // This abstract base class provides the majority of the @@ -171,6 +171,7 @@ public: status_t output_timeline (const char *filename, const char *heading); // this prints the entire set of timeline outputs to the specified file + // = Access a thread priority. // TBD - put this back in, but with dynamic subpriority as well as static // int priority (const handle_t handle, @@ -222,6 +223,10 @@ public: static void export(RT_Info*, FILE* file); static void export(RT_Info&, FILE* file); + // accessors for the minimal and maximal dispatch entry id in the schedule + u_long min_dispatch_id () const; + u_long max_dispatch_id () const; + protected: //////////////////////////////// @@ -264,12 +269,17 @@ protected: virtual status_t assign_priorities (Dispatch_Entry **dispatches, u_int count) = 0; - // = assign priorities to the sorted dispatches + // = assign priorities to the sorted dispatches virtual status_t assign_subpriorities (Dispatch_Entry **dispatches, u_int count) = 0; - // = assign dynamic and static sub-priorities to the sorted dispatches + // = assign dynamic and static sub-priorities to the sorted dispatches + virtual status_t + schedule_timeline_entry (Dispatch_Entry &dispatch_entry, + ACE_Unbounded_Queue <Dispatch_Entry *> + &reschedule_queue) = 0; + // = schedule a dispatch entry into the timeline being created //////////////////////////// // protected data members // @@ -303,6 +313,10 @@ protected: ACE_Unbounded_Set <Dispatch_Entry *> *dispatch_entries_; // the set of dispatch entries + ACE_Unbounded_Set <Dispatch_Entry *> *expanded_dispatches_; + // expanded set of dispatch entries (all dispatch entries produced by + // expanding sub-frames to the total frame size during timeline creation) + Dispatch_Entry **ordered_dispatch_entries_; // An array of pointers to dispatch entries. It is // sorted by the schedule_dispatches method. @@ -313,6 +327,9 @@ protected: u_int threads_; // the number of dispatch entries in the schedule + ACE_Ordered_MultiSet <TimeLine_Entry_Link> *timeline_; + // Ordered MultiSet of timeline entries. + private: /////////////////////////////// @@ -343,11 +360,19 @@ private: status_t output_dispatch_timeline (const char *filename); status_t output_dispatch_timeline (FILE *file); - // this prints the entire set of timeline outputs to the specified file + // this prints a dispatch timeline to the specified file status_t output_preemption_timeline (const char *filename); status_t output_preemption_timeline (FILE *file); - // this prints the entire set of timeline outputs to the specified file + // this prints a preemption timeline to the specified file + + status_t output_viewer_timeline (const char *filename); + status_t output_viewer_timeline (FILE *file); + // this prints a scheduling viewer timeline to the specified file + + status_t output_dispatch_priorities (const char *filename); + status_t output_dispatch_priorities (FILE *file); + // this prints the scheduling parameters and assigned priorities to the specified file // = Set up the task entry data structures status_t setup_task_entries (void); @@ -385,7 +410,7 @@ private: // propagate the dispatch information from the // threads throughout the call graph - status_t calculate_utilization_params (void); + status_t calculate_utilization_params (); // calculate utilization, frame size, etc. // the following functions are not implememented @@ -447,12 +472,14 @@ private: // the maximum priority dispatch queue is always 0, -1 indicates none can // be guaranteed. - ACE_Ordered_MultiSet <TimeLine_Entry_Link> *timeline_; - // Ordered MultiSet of timeline entries. - u_int up_to_date_; // indicates whether the a valid schedule has been generated since the last // relevant change (addition, alteration or removal of an RT_Info, etc.) + + u_long min_dispatch_id_; + + u_long max_dispatch_id_; + }; #if defined (__ACE_INLINE__) diff --git a/TAO/orbsvcs/orbsvcs/Sched/DynSched.i b/TAO/orbsvcs/orbsvcs/Sched/DynSched.i index 0ff202db2c0..32e3e859983 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/DynSched.i +++ b/TAO/orbsvcs/orbsvcs/Sched/DynSched.i @@ -96,5 +96,17 @@ ACE_Scheduler::status (const status_t new_status) status_ = new_status; } +ACE_INLINE u_long +ACE_Scheduler::min_dispatch_id () const +{ + return min_dispatch_id_; +} + +ACE_INLINE u_long +ACE_Scheduler::max_dispatch_id () const +{ + return max_dispatch_id_; +} + // EOF diff --git a/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.cpp b/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.cpp index d0ee3222ce3..503ef93719b 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.cpp +++ b/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.cpp @@ -178,6 +178,7 @@ Task_Entry::merge_dispatches (ACE_Unbounded_Set <Dispatch_Entry *> &dispatch_ent } + // prohibit calls of the given type: currently used to enforce // the notion that two-way calls to disjunctive or conjunctive // RT_Infos do not have any defined meaning, and thus should be @@ -432,36 +433,35 @@ Task_Entry::reframe ( return -1; } - // use an empty ordered multiset for subsequent sub-frame dispatches - // (the set already holds all dispatches the 0th sub-frame) + // make a shallow copy of the set in a new ordered + // multiset using the Dispatch_Entry_Link smart pointers ACE_Ordered_MultiSet <Dispatch_Entry_Link> new_set; + ACE_Ordered_MultiSet_Iterator <Dispatch_Entry_Link> new_iter (new_set); + ACE_Ordered_MultiSet_Iterator <Dispatch_Entry_Link> set_iter (set); - // merge the old set with its old period into the new (empty) - // set with the new period, starting after the 0th sub-frame: - // this puts all dispatches after the 0th sub-frame of the new period - // in the new set, and leaves all dispatches in the 0th sub-frame of - // the new period in the old set. - u_long temp_period = new_period; - int result = merge_frames (dispatch_entries, owner, new_set, set, - temp_period, set_period, 1, 1); - - // if the period changed during the merge, or an error was returned, bail out - if ((temp_period != new_period) || result == -1) + for (set_iter.first (); set_iter.done () == 0; set_iter.advance ()) { - return -1; + Dispatch_Entry_Link *link; + if (set_iter.next (link) == 0) + { + return -1; + } + + if (new_set.insert (*link, new_iter) < 0) + { + return -1; + } } - // now, update the period for the set, and merge the - // new set into the old set, over the same period - set_period = new_period; - result = merge_frames (dispatch_entries, owner, set, - new_set, set_period, set_period); + // do a deep copy merge back into the set using the new period and starting + // after the 0th sub-frame: this puts all dispatches after the 0th + // sub-frame of the new period into the set, and leaves existing dispatches + // in the 0th sub-frame of the new period in the set as well. + int result = merge_frames (dispatch_entries, owner, set, + new_set, new_period, set_period, 1, 1); - // if the period changed during the merge, return an error - if (set_period != new_period) - { - result = -1; - } + // update the set's period to be the new frame + set_period = new_period; return result; } @@ -497,11 +497,11 @@ Task_Entry::merge_frames ( // do virutal iteration over the source set in the new frame, // adding adjusted dispatch entries to the destination + Dispatch_Proxy_Iterator src_iter (src, src_period, dest_period, + number_of_calls, + starting_dest_sub_frame); - for (Dispatch_Proxy_Iterator src_iter (src, src_period, dest_period, - number_of_calls, - starting_dest_sub_frame); - src_iter.done () == 0; src_iter.advance ()) + for (src_iter.first (starting_dest_sub_frame); src_iter.done () == 0; src_iter.advance ()) { // Policy: disjunctively dispatched operations get their deadline and @@ -568,8 +568,9 @@ Dispatch_Entry::Dispatch_Id Dispatch_Entry::next_id_ = 0; Dispatch_Entry::Dispatch_Entry ( Time arrival, Time deadline, - Preemption_Priority priority, - Task_Entry &task_entry) + Preemption_Priority priority, + Task_Entry &task_entry, + Dispatch_Entry *original_dispatch) : priority_ (priority) , OS_priority_ (0) @@ -578,6 +579,7 @@ Dispatch_Entry::Dispatch_Entry ( , arrival_ (arrival) , deadline_ (deadline) , task_entry_ (task_entry) + , original_dispatch_ (original_dispatch) { // obtain, increment the next id dispatch_id_ = next_id_++; @@ -591,6 +593,7 @@ Dispatch_Entry::Dispatch_Entry (const Dispatch_Entry &d) , arrival_ (d.arrival_) , deadline_ (d.deadline_) , task_entry_ (d.task_entry_) + , original_dispatch_ (d.original_dispatch_) { // obtain, increment the next id dispatch_id_ = next_id_++; @@ -653,8 +656,8 @@ Dispatch_Entry_Link::Dispatch_Entry_Link ( // Class Dispatch_Proxy_Iterator // /////////////////////////////////// -Dispatch_Proxy_Iterator::Dispatch_Proxy_Iterator - (ACE_Ordered_MultiSet <Dispatch_Entry_Link> set, +Dispatch_Proxy_Iterator::Dispatch_Proxy_Iterator + (ACE_Ordered_MultiSet <Dispatch_Entry_Link> &set, u_long actual_frame_size, u_long virtual_frame_size, u_long number_of_calls, @@ -666,14 +669,14 @@ Dispatch_Proxy_Iterator::Dispatch_Proxy_Iterator , current_frame_offset_ (actual_frame_size * starting_sub_frame) , iter_ (set) { - first (); + first (starting_sub_frame); } // ctor int Dispatch_Proxy_Iterator::first (u_int sub_frame) { - if (actual_frame_size_ * (sub_frame + 1) >= virtual_frame_size_) + if (actual_frame_size_ * (sub_frame) >= virtual_frame_size_) { // can not position the virtual iterator // in the given range: do nothing @@ -846,11 +849,14 @@ Dispatch_Proxy_Iterator::priority () const // time slice constructor TimeLine_Entry::TimeLine_Entry (Dispatch_Entry &dispatch_entry, u_long start, u_long stop, + u_long arrival, u_long deadline, TimeLine_Entry *next, TimeLine_Entry *prev) : dispatch_entry_ (dispatch_entry) , start_ (start) , stop_ (stop) + , arrival_ (arrival) + , deadline_ (deadline) , next_ (next) , prev_ (prev) { diff --git a/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.h b/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.h index 64b087c44f8..c6887cfaea8 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.h +++ b/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.h @@ -275,7 +275,8 @@ public: Dispatch_Entry (Time arrival, Time deadline, Preemption_Priority priority, - Task_Entry &task_entry); + Task_Entry &task_entry, + Dispatch_Entry *original_dispatch = 0); // copy ctor Dispatch_Entry (const Dispatch_Entry &d); @@ -313,6 +314,8 @@ public: // instead of a class member function int operator < (const Dispatch_Entry &d) const; + // accessor for pointer to original dispatch + Dispatch_Entry *original_dispatch (); private: // TBD - add reference counting to Dispatch Entry class, @@ -346,6 +349,10 @@ private: // stores the id of the related task entry Task_Entry &task_entry_; + // stores a pointer to the original dispatch entry if this + // is a dispatch generated by expanding the original frame + Dispatch_Entry *original_dispatch_; + }; class TAO_ORBSVCS_Export Dispatch_Entry_Link @@ -415,7 +422,7 @@ public: typedef RtecScheduler::Info_Type Info_Type; typedef RtecScheduler::Dependency_Type Dependency_Type; - Dispatch_Proxy_Iterator (ACE_Ordered_MultiSet <Dispatch_Entry_Link> set, + Dispatch_Proxy_Iterator (ACE_Ordered_MultiSet <Dispatch_Entry_Link> &set, u_long actual_frame_size, u_long virtual_frame_size, u_long number_of_calls_ = 1, @@ -505,6 +512,8 @@ public: TimeLine_Entry (Dispatch_Entry &dispatch_entry, u_long start, u_long stop, + u_long arrival, + u_long deadline, TimeLine_Entry *next = 0, TimeLine_Entry *prev = 0); @@ -514,6 +523,8 @@ public: // accessors for time slice start and stop times (100 nanoseconds) u_long start () const; u_long stop () const; + u_long arrival () const; + u_long deadline () const; // accessor and mutator for next and prev slices for this dispatch TimeLine_Entry *next (void) const; @@ -528,9 +539,11 @@ private: // the dispatch entry to which the time slice corresponds Dispatch_Entry &dispatch_entry_; - // priority time slice start and stop times (100 nanoseconds) - u_long start_; + // priority time slice times (100 nanoseconds) + u_long start_; u_long stop_; + u_long arrival_; + u_long deadline_; // next and previous priority time slices for this dispatch entry TimeLine_Entry *next_; diff --git a/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.i b/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.i index 690f7c33f33..58255004fb5 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.i +++ b/TAO/orbsvcs/orbsvcs/Sched/SchedEntry.i @@ -247,6 +247,14 @@ Dispatch_Entry::task_entry () const } +// accessor for pointer to original dispatch +Dispatch_Entry * +Dispatch_Entry::original_dispatch () +{ + return original_dispatch_; +} + + /////////////////////////////// // Class Dispatch_Entry_Link // /////////////////////////////// @@ -310,6 +318,21 @@ TimeLine_Entry::stop () const return stop_; } +// accessor for time slice stop time (100 nanoseconds) +ACE_INLINE u_long +TimeLine_Entry::arrival () const +{ + return arrival_; +} + +// accessor for time slice stop time (100 nanoseconds) +ACE_INLINE u_long +TimeLine_Entry::deadline () const +{ + return deadline_; +} + + // accessor for next slice for this dispatch ACE_INLINE TimeLine_Entry * TimeLine_Entry::next (void) const diff --git a/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.cpp b/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.cpp index 8460a689eea..63a45837a22 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.cpp +++ b/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.cpp @@ -16,8 +16,8 @@ // // ============================================================================ -#include <math.h> -#include <float.h> +#include "math.h" +#include "float.h" #include "ace/Sched_Params.h" @@ -156,48 +156,51 @@ ACE_Scheduler::status_t ACE_Strategy_Scheduler::assign_subpriorities (Dispatch_Entry **dispatches, u_int count) { - // start both subpriority counts at 0, set these values in - // the first entry, and increment the static subpriority count - Sub_Priority dynamic_subpriorities = 0; - Sub_Priority static_subpriorities = 0; - dispatches[0]->dynamic_subpriority (dynamic_subpriorities); - dispatches[0]->static_subpriority (static_subpriorities++); - - + // start subpriority levels and element counts at 1, set level values in + // the first entry, increment the static subpriority level, + Sub_Priority dynamic_subpriority_level = 0; + Sub_Priority static_subpriority_level = 0; + u_int dynamic_subpriority_elements = 1; + u_int static_subpriority_elements = 1; + dispatches[0]->dynamic_subpriority (dynamic_subpriority_level); + dispatches[0]->static_subpriority (static_subpriority_level++); + + u_int i,j; // traverse ordered dispatch entry array, assigning priority // (array is sorted from highest to lowest priority) - for (u_int i = 1; i < count; ++i) + for (i = 1; i < count; ++i) { switch (strategy_.priority_comp (*(dispatches[i-1]), *(dispatches[i]))) { case -1: // the current entry is at lower priority than the previous { - // fill in the high to low subpriority values by subtracting the - // previously assigned subpriorities from the total number of - // subpriorities - int j; - for (j = 1; j <= dynamic_subpriorities; ++j) + // fill in the high to low dynamic subpriority values by subtracting + // the previously assigned subpriority value of each of element in the + // current priority level from the value of last subpriority level + for (j = 1; j <= dynamic_subpriority_elements; ++j) { dispatches[i - j]-> - dynamic_subpriority (dynamic_subpriorities - + dynamic_subpriority (dynamic_subpriority_level - dispatches[i - j]-> dynamic_subpriority ()); } - for (j = 1; j <= static_subpriorities; ++j) + for (j = 1; j <= static_subpriority_elements; ++j) { dispatches[i - j]-> - static_subpriority (static_subpriorities - + static_subpriority (static_subpriority_level - dispatches[i - j]-> - static_subpriority ()); + static_subpriority () - 1); } // reset the subpriority counters, set these values in the // current entry, and increment the static subpriority counter - dynamic_subpriorities = 0; - static_subpriorities = 0; - dispatches[i]->dynamic_subpriority (dynamic_subpriorities); - dispatches[i]->static_subpriority (static_subpriorities++); + dynamic_subpriority_elements = 1; + static_subpriority_elements = 1; + dynamic_subpriority_level = 0; + static_subpriority_level = 0; + dispatches[i]->dynamic_subpriority (dynamic_subpriority_level); + dispatches[i]->static_subpriority (static_subpriority_level++); break; } @@ -209,28 +212,17 @@ ACE_Strategy_Scheduler::assign_subpriorities (Dispatch_Entry **dispatches, *(dispatches[i]))) { case -1: // the current entry is at lower dynamic subpriority - { - // increment dynamic subpriority counter - ++dynamic_subpriorities; - - // fill in the high to low static subpriority values by - // subtracting the previously assigned subpriorities from - // the total number of subpriorities - for (int j = 1; j <= static_subpriorities; ++j) - { - dispatches[i - j]-> - static_subpriority (static_subpriorities - - dispatches[i - j]-> - static_subpriority ()); - } - // reset the static subpriority counter, set this value in the - // current entry, and increment the static subpriority counter - static_subpriorities = 0; - dispatches[i]->static_subpriority (static_subpriorities++); + // increment dynamic subpriority level + ++dynamic_subpriority_level; + // update the static subpriority as well: this avoids problems + // with non-determinism if due to run-time conditions, two + // dispatches line up with identical dynamic subpriority that + // were considered different with respect to the critical instant + dispatches[i]->static_subpriority (static_subpriority_level++); + static_subpriority_elements++; break; - } case 0: // still at the same dynamic subpriority level @@ -242,10 +234,13 @@ ACE_Strategy_Scheduler::assign_subpriorities (Dispatch_Entry **dispatches, case 0: // assign and then increment the static subpriority: even if - // still at the same static subpriority level as far as the - // scheduling strategy is concerned, assign a new one - // anyway, to give a completely deterministic schedule - dispatches[i]->static_subpriority (static_subpriorities++); + // still at the same dynamic or static subpriority level as + // far as the scheduling strategy is concerned, assign a new + // one anyway, to give a completely deterministic schedule + // even if the dynamic subpriorities happen to align due to + // run-time variation + dispatches[i]->static_subpriority (static_subpriority_level++); + static_subpriority_elements++; break; default: // should never reach here: something *bad* has happened @@ -273,7 +268,8 @@ ACE_Strategy_Scheduler::assign_subpriorities (Dispatch_Entry **dispatches, ACE_Scheduler::ST_INVALID_PRIORITY_ORDERING); } - dispatches[i]->dynamic_subpriority (dynamic_subpriorities); + dispatches[i]->dynamic_subpriority (dynamic_subpriority_level); + dynamic_subpriority_elements++; break; default: // should never reach here: something *bad* has happened @@ -288,6 +284,22 @@ ACE_Strategy_Scheduler::assign_subpriorities (Dispatch_Entry **dispatches, } } + // fill in the high to low subpriority values for the last priority + // level by subtracting the previously assigned subpriorities from + // the total number of subpriorities + for (j = 1; j <= dynamic_subpriority_elements; ++j) + { + dispatches[i - j]-> + dynamic_subpriority (dynamic_subpriority_level - + dispatches[i - j]->dynamic_subpriority ()); + } + for (j = 1; j <= static_subpriority_elements; ++j) + { + dispatches[i - j]-> + static_subpriority (static_subpriority_level - + dispatches[i - j]->static_subpriority () - 1); + } + return ACE_Scheduler::SUCCEEDED; } @@ -300,6 +312,169 @@ ACE_Strategy_Scheduler::minimum_critical_priority () // = determine the minimum critical priority number +ACE_Scheduler::status_t +ACE_Strategy_Scheduler::schedule_timeline_entry ( + Dispatch_Entry &dispatch_entry, + ACE_Unbounded_Queue <Dispatch_Entry *> &reschedule_queue) +{ + status_t status = SUCCEEDED; + + // timeline entries cover the execution time of the dispatch + u_long remaining_time = + dispatch_entry.task_entry().rt_info ()->worst_case_execution_time; + + // initialize last stop time to arrival time of the dispatch + u_long last_stop = dispatch_entry.arrival (); + + TimeLine_Entry *last_entry = 0; + TimeLine_Entry *current_entry = 0; + ACE_Ordered_MultiSet_Iterator <TimeLine_Entry_Link> iter (*timeline_); + for (iter.first (); (remaining_time > 0) && (iter.done () == 0); + iter.advance ()) + { + TimeLine_Entry_Link *link; + if ((iter.next (link) == 0) || (! link)) + { + return ST_BAD_INTERNAL_POINTER; + } + + // for each entry already in the timeline that is the first one for a + // dispatch, and has lower dynamic subpriority and does not have greater + // static priority, and starts in the period in which the new entry would + // execute, then advance the iterator to the next timeline entry + // having a different dispatch entry (if there is such), add its dispatch + // entry to the reschedule set, remove all TimeLine_Entry_Links that + // correspond to that dispatch entry, and delete all its TimeLine_Entry + // objects as well. NOTE: 0 is highest priority, 1 next, etc. + while ((iter.done () == 0) && + (link->entry ().start() < last_stop + remaining_time) && + (link->entry ().start() >= last_stop) && + (link->entry ().prev () == 0) && + (link->entry ().dispatch_entry().priority () >= + dispatch_entry.priority ()) && + (strategy_.dynamic_subpriority (dispatch_entry, link->entry ().start ()) > + strategy_.dynamic_subpriority (link->entry ().dispatch_entry (), + link->entry ().start ()))) + { + // point to the dispatch entry whose timeline entries will be removed and + // rescheduled, and to the timeline entry heading the bilinked list of + // timeline entries to be removed + Dispatch_Entry *removed_dispatch_entry + = &(link->entry ().dispatch_entry()); + TimeLine_Entry *remove_entry = & (link->entry ()); + + // put the dispatch entry into the set of entries that will be + // rescheduled at the end of this method (tail recursively) + reschedule_queue.enqueue_tail (removed_dispatch_entry); + + // advance the iterator to the next timeline entry (if there is one) + // that is not for the dispatch entry being removed + while (iter.done () == 0) + { + // point to the current link + if ((iter.next (link) == 0) || (! link)) + { + return ST_BAD_INTERNAL_POINTER; + } + + // advance until a different dispatch entry is found, + // or we run off the end of the timeline + if (&(link->entry ().dispatch_entry ()) == + removed_dispatch_entry) + { + iter.advance (); + } + else + { + break; + } + } + + // remove entries corresponding to the rescheduled + // dispatch from the timeline and destroy them + TimeLine_Entry *next_remove_entry = 0; + while (remove_entry) + { + next_remove_entry = remove_entry->next (); + + timeline_->remove (TimeLine_Entry_Link (*remove_entry)); + delete remove_entry; + + remove_entry = next_remove_entry; + } + } + + // exit the outer loop if there are no more entries in the timeline + if (iter.done () != 0) + { + break; + } + + // if there's room, schedule a new timeline entry for the dispatch + if (link->entry ().start() > last_stop) + { + ACE_NEW_RETURN ( + current_entry, + TimeLine_Entry ( + dispatch_entry, + last_stop, + (((remaining_time + last_stop) < link->entry ().start()) + ? (remaining_time + last_stop) : link->entry ().start()), + dispatch_entry.arrival (), + dispatch_entry.deadline (), + 0, last_entry), + ST_VIRTUAL_MEMORY_EXHAUSTED); + + // patch up the pointers within the list of entries for this dispatch + if (last_entry) + { + last_entry->next (current_entry); + } + last_entry = current_entry; + + timeline_->insert(TimeLine_Entry_Link(*current_entry)); + + // update the remaining time and last stop values + remaining_time -= ((remaining_time < (link->entry ().start() - last_stop)) + ? remaining_time : (link->entry ().start() - last_stop)); + } + + // update the last stop time + if (last_stop < link->entry ().stop ()) + { + last_stop = link->entry ().stop (); + } + } + + // if there is still dispatch time remaining, and we've + // reached the end of the list, insert what's left + if (remaining_time > 0) + { + ACE_NEW_RETURN ( + current_entry, + TimeLine_Entry ( + dispatch_entry, + last_stop, + remaining_time + last_stop, + dispatch_entry.arrival (), + dispatch_entry.deadline (), + 0, last_entry), + ST_VIRTUAL_MEMORY_EXHAUSTED); + + // patch up the pointers within the list of entries for this dispatch + if (last_entry) + { + last_entry->next (current_entry); + } + + timeline_->insert(TimeLine_Entry_Link(*current_entry)); + } + + return status; +} + + + //////////////////////////////////////////////////////////////////// // class template ACE_Strategy_Scheduler_Factory member functions // //////////////////////////////////////////////////////////////////// @@ -394,11 +569,6 @@ ACE_Scheduler_Strategy::static_subpriority_comp ( } else { - // should never get here: all entries should be ordered by finishing time - ACE_ERROR ((LM_ERROR, - "minimal ordering failure for tasks \"%s\" and \"%s\".\n", - first_entry.task_entry ().rt_info ()->entry_point, - second_entry.task_entry ().rt_info ()->entry_point)); return 0; } } @@ -482,6 +652,23 @@ ACE_MUF_Scheduler_Strategy::~ACE_MUF_Scheduler_Strategy () } // = virtual dtor +long +ACE_MUF_Scheduler_Strategy::dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time) +{ + long laxity = + entry.deadline () - current_time - + entry.task_entry ().rt_info ()->worst_case_execution_time; + + return (laxity > 0) ? LONG_MAX - laxity : laxity; +} + // = returns a dynamic subpriority value for the given entry and the + // current time: if the operation has non-negative laxity, then the + // value is positive, and a lower laxity gives a higher dynamic + // subpriority; if the operation has negative laxity, the value + // is the (negative) laxity value + + int ACE_MUF_Scheduler_Strategy::dynamic_subpriority_comp (const Dispatch_Entry &first_entry, @@ -489,11 +676,11 @@ ACE_MUF_Scheduler_Strategy::dynamic_subpriority_comp { // order by descending dynamic priority according to ascending laxity u_long laxity1 = - first_entry.deadline () - + first_entry.deadline () - first_entry.arrival () - first_entry.task_entry ().rt_info ()->worst_case_execution_time; u_long laxity2 = - second_entry.deadline () - + second_entry.deadline () - first_entry.arrival () - second_entry.task_entry ().rt_info ()->worst_case_execution_time; @@ -529,7 +716,7 @@ ACE_MUF_Scheduler_Strategy::minimum_critical_priority () { return minimum_critical_priority_; } - // = returns 0 for minimum critical priority number + // = returns minimum critical priority number ///////////////////////////////////////////////////////////////////////// // class ACE_RMS_Scheduler_Strategy static data member initializations // @@ -590,7 +777,7 @@ ACE_RMS_Scheduler_Strategy::sort ( ACE_RMS_Scheduler_Strategy::ACE_RMS_Scheduler_Strategy ( ACE_Scheduler::Preemption_Priority minimum_critical_priority) - :ACE_Scheduler_Strategy (0) + :ACE_Scheduler_Strategy (minimum_critical_priority) { } // = default ctor @@ -600,6 +787,14 @@ ACE_RMS_Scheduler_Strategy::~ACE_RMS_Scheduler_Strategy () } // = virtual dtor +long +ACE_RMS_Scheduler_Strategy::dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time) +{ + return 0; +} + // = all entries have the same dynamic subpriority value + int ACE_RMS_Scheduler_Strategy::dynamic_subpriority_comp (const Dispatch_Entry &first_entry, @@ -621,6 +816,13 @@ ACE_RMS_Scheduler_Strategy::sort_function (void *arg1, void *arg2) // comparison function to pass to qsort +ACE_Scheduler::Preemption_Priority +ACE_RMS_Scheduler_Strategy::minimum_critical_priority () +{ + return minimum_critical_priority_; +} + // = returns minimum critical priority number + ///////////////////////////////////////////////////////////////////////// // class ACE_MLF_Scheduler_Strategy static data member initializations // ///////////////////////////////////////////////////////////////////////// @@ -676,6 +878,19 @@ ACE_MLF_Scheduler_Strategy::~ACE_MLF_Scheduler_Strategy () // = virtual dtor +long +ACE_MLF_Scheduler_Strategy::dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time) +{ + long laxity = + entry.deadline () - current_time - + entry.task_entry ().rt_info ()->worst_case_execution_time; + + return (laxity > 0) ? LONG_MAX - laxity : laxity; +} + // = returns a dynamic subpriority value for the given entry and the + // current time relative to its arrival + int ACE_MLF_Scheduler_Strategy::dynamic_subpriority_comp (const Dispatch_Entry &first_entry, @@ -684,11 +899,11 @@ ACE_MLF_Scheduler_Strategy::dynamic_subpriority_comp // order by laxity (ascending) // order by descending dynamic priority according to ascending laxity u_long laxity1 = - first_entry.deadline () - + first_entry.deadline () - first_entry.arrival () - first_entry.task_entry ().rt_info ()->worst_case_execution_time; u_long laxity2 = - second_entry.deadline () - + second_entry.deadline () - first_entry.arrival () - second_entry.task_entry ().rt_info ()->worst_case_execution_time; if (laxity1 < laxity2) @@ -774,17 +989,30 @@ ACE_EDF_Scheduler_Strategy::~ACE_EDF_Scheduler_Strategy () } // = virtual dtor +long +ACE_EDF_Scheduler_Strategy::dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time) +{ + long time_to_deadline = entry.deadline () - current_time; + return (time_to_deadline > 0) + ? LONG_MAX - time_to_deadline : time_to_deadline; +} + // = returns a dynamic subpriority value for the given entry and the + // current time relative to its arrival + int ACE_EDF_Scheduler_Strategy::dynamic_subpriority_comp (const Dispatch_Entry &first_entry, const Dispatch_Entry &second_entry) { // order by dispatchable interval (ascending) - if (first_entry.deadline () < second_entry.deadline ()) + if (first_entry.deadline () - first_entry.arrival () < + second_entry.deadline () - first_entry.arrival ()) { return -1; } - else if (first_entry.deadline () > second_entry.deadline ()) + else if (first_entry.deadline () - first_entry.arrival () > + second_entry.deadline () - first_entry.arrival ()) { return 1; } @@ -897,6 +1125,25 @@ ACE_RMS_Dyn_Scheduler_Strategy::~ACE_RMS_Dyn_Scheduler_Strategy () } // = virtual dtor +long +ACE_RMS_Dyn_Scheduler_Strategy::dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time) +{ + if (entry.task_entry ().rt_info ()->criticality < + RtecScheduler::HIGH_CRITICALITY) + { + long laxity = + entry.deadline () - current_time - + entry.task_entry ().rt_info ()->worst_case_execution_time; + + return (laxity > 0) ? LONG_MAX - laxity : laxity; + } + + return 0; +} + // = returns a dynamic subpriority value for the given entry and the + // current time relative to its arrival + int ACE_RMS_Dyn_Scheduler_Strategy::dynamic_subpriority_comp (const Dispatch_Entry &first_entry, @@ -918,11 +1165,11 @@ ACE_RMS_Dyn_Scheduler_Strategy::dynamic_subpriority_comp // for VERY_LOW_CRITICALITY, LOW_CRITICALITY and MEDIUM_CRITICALITY, // order second by laxity (ascending) u_long laxity1 = - first_entry.deadline () - + first_entry.deadline () - first_entry.arrival () - first_entry.task_entry ().rt_info ()->worst_case_execution_time; u_long laxity2 = - second_entry.deadline () - + second_entry.deadline () - first_entry.arrival () - second_entry.task_entry ().rt_info ()->worst_case_execution_time; if (laxity1 < laxity2) diff --git a/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.h b/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.h index a57a821cf1a..8a6bb2f3b15 100644 --- a/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.h +++ b/TAO/orbsvcs/orbsvcs/Sched/Strategy_Scheduler.h @@ -60,6 +60,11 @@ public: private: + virtual status_t schedule_timeline_entry (Dispatch_Entry &dispatch_entry, + ACE_Unbounded_Queue <Dispatch_Entry *> + &reschedule_queue); + // = schedules a dispatch entry into the timeline being created + virtual status_t sort_dispatches (Dispatch_Entry **dispatches, u_int count); // = sets up the schedule in the order generated by the strategy @@ -134,6 +139,11 @@ public: // is greater in the order, 0 if they are equivalent, or 1 if the // second Dispatch_Entry is greater in the order + virtual long dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time) = 0; + // = returns a dynamic subpriority value + // for the given timeline entry at the current time + virtual int static_subpriority_comp (const Dispatch_Entry &first_entry, const Dispatch_Entry &second_entry); // = provide a lowest level ordering based first on importance (descending), @@ -194,6 +204,14 @@ public: protected: + virtual long dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time); + // = returns a dynamic subpriority value at the current time for + // the given timeline entry: if the operation has + // non-negative laxity, then the value is positive, and a lower + // laxity gives a higher dynamic subpriority; if the operation + // has negative laxity, the value is the (negative) laxity value + virtual int dynamic_subpriority_comp ( const Dispatch_Entry &first_entry, const Dispatch_Entry &second_entry); @@ -240,8 +258,16 @@ public: u_int count); // = sort the dispatch entry link pointer array in descending RMS (rate) order + virtual ACE_Scheduler::Preemption_Priority minimum_critical_priority (); + // = determine the minimum critical priority number + protected: + virtual long dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time); + // = just returns 0: all operations have + // the same dynamic subpriority value + virtual int dynamic_subpriority_comp (const Dispatch_Entry &first_entry, const Dispatch_Entry &second_entry); @@ -291,6 +317,14 @@ public: protected: + virtual long dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time); + // = returns a dynamic subpriority value at the current time for + // the given timeline entry: if the operation has + // non-negative laxity, then the value is positive, and a lower + // laxity gives a higher dynamic subpriority; if the operation + // has negative laxity, the value is the (negative) laxity value + virtual int dynamic_subpriority_comp (const Dispatch_Entry &first_entry, const Dispatch_Entry &second_entry); @@ -338,6 +372,15 @@ public: protected: + virtual long dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time); + // = returns a dynamic subpriority value at the current time for the + // given timeline entry: if the operation has non-negative + // time to deadline, then value is positive, and a shorter time to + // deadline gives a higher dynamic subpriority; if the operation has a + // negative time to deadline, the value is (negative) time to deadline + + virtual int dynamic_subpriority_comp (const Dispatch_Entry &first_entry, const Dispatch_Entry &second_entry); @@ -385,8 +428,22 @@ public: u_int count); // = sort the dispatch entry pointer array in descending priority order + virtual ACE_Scheduler::Preemption_Priority minimum_critical_priority (); + // = determine the minimum critical priority number + protected: + virtual long dynamic_subpriority (Dispatch_Entry &entry, + u_long current_time); + // = returns a dynamic subpriority value at the current time for the + // given timeline entry: if the operation is in the + // critical set, the dynamic subpriority value is always 0; if the + // operation is non-critical and has non-negative laxity, then the + // dynamic subpriority value is positive, and a lower laxity gives a + // higher dynamic subpriority if the operation is non-critical and has + // negative laxity, the value is the (negative) laxity value + + virtual int dynamic_subpriority_comp (const Dispatch_Entry &first_entry, const Dispatch_Entry &second_entry); @@ -397,9 +454,6 @@ protected: // 0 if they're equivalent, or 1 if the second Dispatch_Entry is greater // in the order. - virtual ACE_Scheduler::Preemption_Priority minimum_critical_priority (); - // = determine the minimum critical priority number - private: static int sort_function (void *arg1, void *arg2); |