blob: 9ae919f7f8338a2f2ae846a93dd44e28d841077b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
// -*- C++ -*-
//=============================================================================
/**
* @file FTRMFF_Worstfit.cpp
*
* $Id$
*
* @author Friedhelm Wolf (fwolf@dre.vanderbilt.edu)
*/
//=============================================================================
#include "FTRMFF_Worstfit.h"
#include "RankedWCRT.h"
#include "Utilization_Ranking.h"
#include <algorithm>
FTRMFF_Worstfit::~FTRMFF_Worstfit ()
{
}
FTRMFF_Output
FTRMFF_Worstfit::operator () (const FTRMFF_Input & input)
{
FTRMFF_Worstfit_Algorithm algorithm (input.processors,
input.backup_count);
FTRMFF_Output output;
output.schedule = algorithm (input.tasks);
output.unscheduled_tasks = algorithm.get_unschedulable ();
DBG_OUT (algorithm.schedule ());
return output;
}
FTRMFF_Worstfit_Algorithm::FTRMFF_Worstfit_Algorithm (
const PROCESSOR_LIST & processors,
unsigned int consistency_level)
: FTRMFF_Algorithm_Impl (consistency_level),
schedule_ (create_schedule (processors))
{
}
FTRMFF_Worstfit_Algorithm::~FTRMFF_Worstfit_Algorithm ()
{
}
SCHEDULING_MAP
FTRMFF_Worstfit_Algorithm::operator () (const TASK_LIST & tasks)
{
// sort tasks according to their worst case response times
TASK_LIST sorted_tasks = tasks;
std::sort (sorted_tasks.begin (),
sorted_tasks.end (),
PeriodComparison <Task> ());
// for each task
for (TASK_LIST::const_iterator task_it = sorted_tasks.begin ();
task_it != sorted_tasks.end ();
++task_it)
{
// create a set of replicas
TASK_LIST replica_group = create_tasks (*task_it, consistency_level_);
// copy global schedule for per-task scheduling
SCHEDULE local_schedule = schedule_;
// initialize worst-case response time algorithm
RankedWCRT wcrt_algorithm (local_schedule,
consistency_level_);
// this data-structure will store result schedules
SCHEDULE_RESULT_LIST schedule_results;
// for each replica
for (TASK_LIST::iterator replica_it = replica_group.begin ();
replica_it != replica_group.end ();
++replica_it)
{
ScheduleResult best_result;
best_result.wcrt = -1.0;
// for each processor
for (SCHEDULE::iterator proc_it = local_schedule.begin ();
proc_it != local_schedule.end ();
++proc_it)
{
// calculate worst-case response time of replica on processor
TASK_LIST local_tasks = local_schedule[proc_it->first];
local_tasks.push_back (*task_it);
double wcrt = wcrt_algorithm (local_tasks);
// remember result with minimum worst-case response time
if ((best_result.wcrt < .0) || (wcrt < best_result.wcrt))
{
best_result.task = *task_it;
best_result.processor = proc_it->first;
best_result.wcrt = wcrt;
}
}
// use best schedule entry
schedule_results.push_back (best_result);
local_schedule.erase (best_result.processor);
}
// rank replicas based on the non-failure case response time
Utilization_Ranking ranking_algorithm;
unsigned int scheduled_replicas =
ranking_algorithm (schedule_results,
schedule_);
// if all tasks are schedulable
if (scheduled_replicas == schedule_results.size ())
{
// schedule all schedule entries for replicas
add_schedule_results (schedule_results, schedule_);
}
else
{
// if not add to unschedulable list
ScheduleProgress pg = {*task_it, scheduled_replicas};
unschedulable_.push_back (pg);
}
}
return transform_schedule (schedule_);
}
const SCHEDULE &
FTRMFF_Worstfit_Algorithm::schedule () const
{
return schedule_;
}
|
