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
|
// -*- C++ -*-
//=============================================================================
/**
* @file FTRMFF_Basic_Algorithm.cpp
*
* $Id$
*
* @author Friedhelm Wolf (fwolf@dre.vanderbilt.edu)
*/
//=============================================================================
#include <sstream>
#include "FTRMFF_Basic.h"
#include "Task_Scheduler.h"
#include "Simple_Ranking.h"
FTRMFF_Basic::FTRMFF_Basic (CTT_Algorithm & ctt)
: ctt_ (ctt)
{
}
FTRMFF_Basic::~FTRMFF_Basic ()
{
}
FTRMFF_Output
FTRMFF_Basic::operator () (const FTRMFF_Input & input)
{
FTRMFF_Basic_Algorithm algorithm (input.processors,
input.backup_count,
ctt_);
FTRMFF_Output output;
output.schedule = algorithm (input.tasks);
output.unscheduled_tasks = algorithm.get_unschedulable ();
DBG_OUT (algorithm.schedule ());
return output;
}
FTRMFF_Basic_Algorithm::FTRMFF_Basic_Algorithm (
const PROCESSOR_LIST & processors,
unsigned int consistency_level,
CTT_Algorithm & ctt)
: schedule_ (create_schedule (processors)),
consistency_level_ (consistency_level),
ctt_ (ctt),
ranking_algorithm_ (new Simple_Ranking ())
{
}
FTRMFF_Basic_Algorithm::~FTRMFF_Basic_Algorithm ()
{
}
SCHEDULING_MAP
FTRMFF_Basic_Algorithm::operator () (const TASK_LIST & tasks)
{
// sort tasks based on their periods, which results in a priority
// ordered list since we do rate monotonic scheduling
TASK_LIST sorted_input = tasks;
std::sort (sorted_input.begin (),
sorted_input.end (),
PeriodComparison <Task> ());
for (TASK_LIST::iterator it = sorted_input.begin ();
it != sorted_input.end ();
++it)
{
// use a copy of the original schedule since we will modify it
SCHEDULE temp_schedule = schedule_;
Task_Scheduler scheduler (temp_schedule,
ctt_);
// create the right amount of backup replica tasks
TASK_LIST task_group = create_tasks (*it, consistency_level_);
// schedule the backup tasks of one application
SCHEDULE_RESULT_LIST results;
std::transform (task_group.begin (),
task_group.end (),
std::inserter (results,
results.begin ()),
scheduler);
// rank backups according to their wcrt
unsigned int scheduled_backups =
(*ranking_algorithm_) (results,
schedule_);
if (scheduled_backups < results.size ())
{
// could not schedule all backups
ScheduleProgress pg = {*it, 1 + scheduled_backups};
unschedulable_.push_back (pg);
continue;
}
// if we reach this code, we can add all tasks to the schedule
add_schedule_results (results, schedule_);
}
return transform_schedule (schedule_);
}
SCHEDULE_PROGRESS_LIST
FTRMFF_Basic_Algorithm::get_unschedulable ()
{
return unschedulable_;
}
const SCHEDULE &
FTRMFF_Basic_Algorithm::schedule () const
{
return schedule_;
}
|
