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
|
/*
* kernel/edf_common.c
*
* Common functions for EDF based scheduler.
*/
#include <linux/percpu.h>
#include <linux/sched.h>
#include <linux/list.h>
#include <linux/litmus.h>
#include <linux/sched_plugin.h>
#include <linux/sched_trace.h>
#include <linux/edf_common.h>
/* edf_higher_prio - returns true if first has a higher EDF priority
* than second. Deadline ties are broken by PID.
*
* first first must not be NULL and a real-time task.
* second may be NULL or a non-rt task.
*/
int edf_higher_prio(struct task_struct* first,
struct task_struct* second)
{
struct task_struct *first_task = first;
struct task_struct *second_task = second;
/* Check for inherited priorities. Change task
* used for comparison in such a case.
*/
if (first && first->rt_param.inh_task)
first_task = first->rt_param.inh_task;
if (second && second->rt_param.inh_task)
second_task = second->rt_param.inh_task;
return
/* does the second task exist and is it a real-time task? If
* not, the first task (which is a RT task) has higher
* priority.
*/
!second_task || !is_realtime(second_task) ||
/* is the deadline of the first task earlier?
* Then it has higher priority.
*/
earlier_deadline(first_task, second_task) ||
/* Do we have a deadline tie?
* Then break by PID.
*/
(get_deadline(first_task) == get_deadline(second_task) &&
(first_task->pid < second_task->pid ||
/* If the PIDs are the same then the task with the inherited
* priority wins.
*/
(first_task->pid == second_task->pid &&
!second->rt_param.inh_task)));
}
int edf_ready_order(struct list_head* a, struct list_head* b)
{
return edf_higher_prio(
list_entry(a, struct task_struct, rt_list),
list_entry(b, struct task_struct, rt_list));
}
void edf_release_at(struct task_struct *t, jiffie_t start)
{
t->rt_param.times.deadline = start;
edf_prepare_for_next_period(t);
t->rt_param.times.last_release = start;
set_rt_flags(t, RT_F_RUNNING);
}
void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched)
{
rt_domain_init(rt, resched, edf_ready_order);
}
void edf_prepare_for_next_period(struct task_struct *t)
{
BUG_ON(!t);
/* prepare next release */
t->rt_param.times.release = t->rt_param.times.deadline;
t->rt_param.times.deadline += get_rt_period(t);
t->rt_param.times.exec_time = 0;
/* update job sequence number */
t->rt_param.times.job_no++;
t->time_slice = get_exec_cost(t);
/* who uses this? statistics? */
t->first_time_slice = 0;
}
/* need_to_preempt - check whether the task t needs to be preempted
* call only with irqs disabled and with ready_lock acquired
* THIS DOES NOT TAKE NON-PREEMPTIVE SECTIONS INTO ACCOUNT!
*/
int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t)
{
/* we need the read lock for edf_ready_queue */
/* no need to preempt if there is nothing pending */
if (!ready_jobs_pending(rt))
return 0;
/* we need to reschedule if t doesn't exist */
if (!t)
return 1;
/* NOTE: We cannot check for non-preemptibility since we
* don't know what address space we're currently in.
*/
/* make sure to get non-rt stuff out of the way */
return !is_realtime(t) || edf_higher_prio(next_ready(rt), t);
}
/*
* Deactivate current task until the beginning of the next period.
*/
long edf_sleep_next_period(void)
{
/* Mark that we do not excute anymore */
set_rt_flags(current, RT_F_SLEEP);
/* call schedule, this will return when a new job arrives
* it also takes care of preparing for the next release
*/
schedule();
return 0;
}
|
