In this assignment you will use priority queues to determine whether a given list of repeating hard-real-time jobs can be scheduled so that they complete by their required deadlines, and to output what the schedule actually is. In particular, you must implement a Earliest-deadline-first scheduler, and a jobs generator that will put new jobs on the heap to be scheduled.
The input to your scheduler will consist of a number n, followed by n lines of whitespace separated data in three columns: job name, time required, periodicity. The output should either be a valid shedule, indicating what jobs run at what time all the way until time MAXTIME = lcm(all the time periods), or it should be the job schedule until a job becomes unschedulable, followed by the word unschedulable. This looser spec allows you to produce output no matter whether a schedule is viable or not, which makes implementing this a lot easier. Sample I/O for schedulable list of tasks is:
3 T1 3 5 T2 2 7 T3 1 9
0 T1 finishing at 3 3 T2 finishing at 5 5 T3 finishing at 6 6 T1 finishing at 9 9 T2 finishing at 11 11 T1 finishing at 14 14 T3 finishing at 15 15 T1 finishing at 18 18 T2 finishing at 20 20 T1 finishing at 23 23 T3 finishing at 24 24 T2 finishing at 26 26 T1 finishing at 29 29 T2 finishing at 31 31 T1 finishing at 34 34 T3 finishing at 35 35 T1 finishing at 38 38 T2 finishing at 40 40 T3 finishing at 41 41 T1 finishing at 44 44 T2 finishing at 46 46 T1 finishing at 49 49 T3 finishing at 50 50 T1 finishing at 53 53 T2 finishing at 55 55 T1 finishing at 58 58 T3 finishing at 59 59 T2 finishing at 61 61 T1 finishing at 64 64 T2 finishing at 66 66 T1 finishing at 69 69 T3 finishing at 70 70 T1 finishing at 73 73 T2 finishing at 75 75 T1 finishing at 78 78 T3 finishing at 79 79 T2 finishing at 81 81 T1 finishing at 84 84 T3 finishing at 85 85 T1 finishing at 88 88 T2 finishing at 90 90 T1 finishing at 93 93 T2 finishing at 95 95 T3 finishing at 96 96 T1 finishing at 99 99 T2 finishing at 101 101 T1 finishing at 104 104 T3 finishing at 105 105 T1 finishing at 108 108 T2 finishing at 110 110 T1 finishing at 113 113 T3 finishing at 114 114 T2 finishing at 116 116 T1 finishing at 119 119 T3 finishing at 120 120 T1 finishing at 123 123 T2 finishing at 125 125 T1 finishing at 128 128 T2 finishing at 130 130 T3 finishing at 131 131 T1 finishing at 134 134 T2 finishing at 136 136 T1 finishing at 139 139 T3 finishing at 140 140 T1 finishing at 143 143 T2 finishing at 145 145 T1 finishing at 148 148 T3 finishing at 149 149 T2 finishing at 151 151 T1 finishing at 154 154 T2 finishing at 156 156 T1 finishing at 159 159 T3 finishing at 160 160 T1 finishing at 163 163 T2 finishing at 165 165 T1 finishing at 168 168 T3 finishing at 169 169 T2 finishing at 171 171 T1 finishing at 174 174 T3 finishing at 175 175 T1 finishing at 178 178 T2 finishing at 180 180 T1 finishing at 183 183 T3 finishing at 184 184 T2 finishing at 186 186 T1 finishing at 189 189 T2 finishing at 191 191 T1 finishing at 194 194 T3 finishing at 195 195 T1 finishing at 198 198 T2 finishing at 200 200 T1 finishing at 203 203 T3 finishing at 204 204 T2 finishing at 206 206 T1 finishing at 209 209 T3 finishing at 210 210 T1 finishing at 213 213 T2 finishing at 215 215 T1 finishing at 218 218 T2 finishing at 220 220 T3 finishing at 221 221 T1 finishing at 224 224 T2 finishing at 226 226 T1 finishing at 229 229 T3 finishing at 230 230 T1 finishing at 233 233 T2 finishing at 235 235 T1 finishing at 238 238 T3 finishing at 239 239 T2 finishing at 241 241 T1 finishing at 244 244 T3 finishing at 245 245 T1 finishing at 248 248 T2 finishing at 250 250 T1 finishing at 253 253 T2 finishing at 255 255 T1 finishing at 258 258 T3 finishing at 259 259 T2 finishing at 261 261 T1 finishing at 264 264 T3 finishing at 265 265 T1 finishing at 268 268 T2 finishing at 270 270 T1 finishing at 273 273 T3 finishing at 274 274 T2 finishing at 276 276 T1 finishing at 279 279 T3 finishing at 280 280 T1 finishing at 283 283 T2 finishing at 285 285 T1 finishing at 288 288 T2 finishing at 290 290 T1 finishing at 293 293 T3 finishing at 294 294 T2 finishing at 296 296 T1 finishing at 299 299 T3 finishing at 300 300 T1 finishing at 303 303 T2 finishing at 305 305 T1 finishing at 308 308 T3 finishing at 309 309 T2 finishing at 311 311 T1 finishing at 314
Sample I/O for an unschedulable problem might be:
4 T1 3 5 T2 2 7 T3 1 9 T4 1 11
0 T1 finishing at 3 3 T2 finishing at 5 5 T3 finishing at 6 6 T1 finishing at 9 9 T4 finishing at 10 10 T2 finishing at 12 12 T1 finishing at 15 15 T3 finishing at 16 16 T1 finishing at 19 19 T2 finishing at 21 21 T4 finishing at 22 22 T1 finishing at 25 25 T3 finishing at 26 26 T2 finishing at 28 Unschedulable
But the only important part is that the last line says "Unschedulable" when a list of jobs is, indeed, unschedulable.
To do this, you must maintain at least one heap - the heap of scheduled jobs with active deadlines. When a job becomes schedulable (that is, the current time has moved past the beginning of its period), you should put it in the priority queue of schedulable jobs. Whenever the queue of schedulable jobs is not empty, take the job with the soonest required completion time and schedule it. If it will complete in time, then increment the current time and move forwards.
Calculating the lcm of two numbers is easy, by the way. Here is sample code in python:
def gcd(a,b):
a,b = min(a,b), max(a,b)
if a == 0:
return b
else:
return gcd(a, b%a)
def lcm(x,y):
return x*y // gcd(x,y) # "//" is integer division in python