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
|
/*
* kernel/fifo_common.c
*
* Fifo helper functions. Could one day be a FIFO plugin if someone
* is interested.
*
* The current FIFO implementaion automatically chops Linux tasks into
* smaller jobs by assigning a fixed time slice. Once that time slice expires,
* it is treated as a new job release (that is queued in the back).
*
* The result is that it provides FIFO properties on a job level and round-robin
* on a task level if the tasks execute continuously.
*/
#include <asm/uaccess.h>
#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/fifo_common.h>
/* This function is defined in sched.c. We need access it for
* indirect switching.
*/
void __activate_task(struct task_struct *p, runqueue_t *rq);
void fifo_domain_init(fifo_domain_t* fifo, unsigned int exec_budget)
{
INIT_LIST_HEAD(&fifo->queue);
atomic_set(&fifo->count, 0);
fifo->time_slice = exec_budget;
fifo->lock = SPIN_LOCK_UNLOCKED;
}
void fifo_add(fifo_domain_t* fifo, struct task_struct* task)
{
unsigned long flags;
spin_lock_irqsave(&fifo->lock, flags);
list_add_tail(&task->run_list, &fifo->queue);
atomic_inc(&fifo->count);
spin_unlock_irqrestore(&fifo->lock, flags);
}
void lifo_add(fifo_domain_t* fifo, struct task_struct* task)
{
unsigned long flags;
spin_lock_irqsave(&fifo->lock, flags);
list_add(&task->run_list, &fifo->queue);
atomic_inc(&fifo->count);
spin_unlock_irqrestore(&fifo->lock, flags);
}
/* This is a best-effort attempt at maintaining FIFO order.
* If we re-add a task comming from a preemption, it should go to
* the front as it arived early than the other queued tasks.
* Of course, this is not guaranteed to work correctly. Right now,
* it is only used for best-effort jobs, so it doesn't really matter
* all that much. A correct implementation would have to maintain
* arrival times and perform cross-processor preemptions...
*/
void fifo_enqueue(fifo_domain_t* fifo, struct task_struct* task)
{
task->array = NULL;
if (!task->time_slice) {
task->time_slice = fifo->time_slice;
sched_trace_job_release(task);
fifo_add(fifo, task);
} else
lifo_add(fifo, task);
}
struct task_struct* __fifo_take(fifo_domain_t* fifo)
{
struct task_struct * task = NULL;
if (atomic_read(&fifo->count)) {
BUG_ON(list_empty(&fifo->queue));
task = list_entry(fifo->queue.next, struct task_struct,
run_list);
list_del(fifo->queue.next);
atomic_dec(&fifo->count);
}
return task;
}
struct task_struct* fifo_take(fifo_domain_t* fifo)
{
unsigned long flags;
struct task_struct* t;
spin_lock_irqsave(&fifo->lock, flags);
t = __fifo_take(fifo);
spin_unlock_irqrestore(&fifo->lock, flags);
return t;
}
struct task_struct* fifo_take_rq(fifo_domain_t* fifo, runqueue_t* rq, int cpu)
{
struct task_struct *task = fifo_take(fifo);
if (task) {
set_task_cpu(task, cpu);
__activate_task(task, rq);
}
return task;
}
|
