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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
|
#!/usr/bin/env ruby
require 'optparse'
class Scheduler
def initialize()
@states = []
@tasks = []
end
def loadtasks(tasks)
@tasks = tasks
end
def printHeader()
print "i".ljust(4, ' ')
@tasks.length.times do |i|
print "T#{i.to_s()}".ljust(4, ' ')
end
@tasks.length.times do |i|
print "R#{i.to_s()}".ljust(4, ' ')
end
@tasks.length.times do |i|
print "D#{i.to_s()}".ljust(4, ' ')
end
puts
end
def printState(index, state)
print index.to_s().ljust(4, ' ')
@tasks.length.times do |i|
print state[:task] == i ? "|" : " "
print " "*3
end
state[:remain].each_with_index do |r, i|
print r.to_s().ljust(4, ' ')
end
@tasks.each do |task|
deadline = task[:deadline] - (index % task[:period])
print deadline.to_s().ljust(4, ' ')
end
puts
end
def nextTask(index)
choices = []
if @states.length.zero?
choices = @tasks.length.times.to_a
else
@states.last[:remain].each_with_index do |r, i|
choices << i if r > 0
end
end
if choices.length.zero?
return nil
elsif choices.length == 1
# If there is only one choice return that
return choices[0]
end
loop do
print "Next #{choices.to_s}:"
input = gets
if input == "\n" and @states.last
return @states.last[:task]
end
choice = Integer(input)
if choices.include?(choice)
return choice
end
end
end
def calcNextState(index)
curtask = nextTask(index)
new = {:task => curtask, :remain => []}
@tasks.each_with_index do |task, i|
# Check for deadline miss
intoperiod = index % task[:period]
if intoperiod >= task[:deadline] && @states.last[:remain][i] > 0
puts "Deadline missed in task #{i}"
exit
end
# Check if start of new period
if index % task[:period] == 0
new[:remain] << task[:complete]
else
new[:remain] << @states.last[:remain][i]
end
end
# Decrease the selected task
if curtask
new[:remain][curtask] -= 1 unless new[:remain][curtask].zero?
end
return new
end
def run(runtil=nil)
printHeader()
# Run LCM times
lcm = @tasks[0][:period]
@tasks.drop(1).each do |task|
lcm = task[:period].lcm(lcm)
end
(0..lcm).each do |i|
new = calcNextState(i)
@states << new
printState(i, new)
if runtil && new[:remain][runtil] == 0
break
end
end
end
end
def taskFromString(str)
fields = str.split(",")
if fields.length < 2
raise "#{str} does not contain enough fields"
end
# Run for each field
def parseField(f, default = 0)
return f == nil ? Integer(default) : Integer(f)
end
task = {
:period => parseField(fields[0]),
:complete => parseField(fields[1]),
:deadline => parseField(fields[2], fields[0])
}
return task
end
class FixedSched < Scheduler
alias_method :parent_init, :initialize
def initialize(priorities)
@priorities = priorities
parent_init
end
def nextTask(index)
@priorities.each do |taskid|
if !@states.last or @states.last[:remain][taskid] > 0
return taskid
end
end
return nil
end
end
class RmaSched < Scheduler
def nextTask(index)
smallestTask = nil
@tasks.each_with_index do |task, i|
if @states.last and @states.last[:remain][i] == 0
next
end
smallestTask = i if !smallestTask or task[:period] < @tasks[i][:period]
end
return smallestTask
end
end
options = {}
OptionParser.new do |opts|
opts.on("-f", "--taskfile FILE", "Load tasks from FILE") do |f|
options[:taskfile] = f
end
opts.on("--until-done TASK", "Run until TASK finishes") do |task|
options[:runtil] = Integer(task)
end
opts.on("--sched-rma", "Schedule using rma") do
options[:sched] = RmaSched.new()
end
opts.on("--sched-fixed PRIO", "Schedule using fixed priority list PRIO") do |prio|
prio = prio.split(",")
prio.map! {|p| Integer(p) }
options[:sched] = FixedSched.new(prio)
end
end.parse!
tasks = []
if options[:taskfile]
File.readlines(options[:taskfile]).each do |line|
tasks << taskFromString(line)
end
else
puts "T : period,completion time[,deadline]"
loop do
print "T#{ tasks.length }: "
input = gets
if !input or input.delete_suffix!("\n") == ""
break
end
tasks << taskFromString(input)
end
end
puts tasks.inspect
sch = nil
if options[:sched]
sch = options[:sched]
else
sch = Scheduler.new()
end
sch.loadtasks(tasks)
sch.run(options[:runtil])
|
