1 /* This file contains the scheduling policy for SCHED 2 * 3 * The entry points are: 4 * do_noquantum: Called on behalf of process' that run out of quantum 5 * do_start_scheduling Request to start scheduling a proc 6 * do_stop_scheduling Request to stop scheduling a proc 7 * do_nice Request to change the nice level on a proc 8 * init_scheduling Called from main.c to set up/prepare scheduling 9 */ 10 #include "sched.h" 11 #include "schedproc.h" 12 #include <assert.h> 13 #include <minix/com.h> 14 #include <machine/archtypes.h> 15 16 static unsigned balance_timeout; 17 18 #define BALANCE_TIMEOUT 5 /* how often to balance queues in seconds */ 19 20 static int schedule_process(struct schedproc * rmp, unsigned flags); 21 22 #define SCHEDULE_CHANGE_PRIO 0x1 23 #define SCHEDULE_CHANGE_QUANTUM 0x2 24 #define SCHEDULE_CHANGE_CPU 0x4 25 26 #define SCHEDULE_CHANGE_ALL ( \ 27 SCHEDULE_CHANGE_PRIO | \ 28 SCHEDULE_CHANGE_QUANTUM | \ 29 SCHEDULE_CHANGE_CPU \ 30 ) 31 32 #define schedule_process_local(p) \ 33 schedule_process(p, SCHEDULE_CHANGE_PRIO | SCHEDULE_CHANGE_QUANTUM) 34 #define schedule_process_migrate(p) \ 35 schedule_process(p, SCHEDULE_CHANGE_CPU) 36 37 #define CPU_DEAD -1 38 39 #define cpu_is_available(c) (cpu_proc[c] >= 0) 40 41 #define DEFAULT_USER_TIME_SLICE 200 42 43 /* processes created by RS are sysytem processes */ 44 #define is_system_proc(p) ((p)->parent == RS_PROC_NR) 45 46 static unsigned cpu_proc[CONFIG_MAX_CPUS]; 47 48 static void pick_cpu(struct schedproc * proc) 49 { 50 #ifdef CONFIG_SMP 51 unsigned cpu, c; 52 unsigned cpu_load = (unsigned) -1; 53 54 if (machine.processors_count == 1) { 55 proc->cpu = machine.bsp_id; 56 return; 57 } 58 59 /* schedule sysytem processes only on the boot cpu */ 60 if (is_system_proc(proc)) { 61 proc->cpu = machine.bsp_id; 62 return; 63 } 64 65 /* if no other cpu available, try BSP */ 66 cpu = machine.bsp_id; 67 for (c = 0; c < machine.processors_count; c++) { 68 /* skip dead cpus */ 69 if (!cpu_is_available(c)) 70 continue; 71 if (c != machine.bsp_id && cpu_load > cpu_proc[c]) { 72 cpu_load = cpu_proc[c]; 73 cpu = c; 74 } 75 } 76 proc->cpu = cpu; 77 cpu_proc[cpu]++; 78 #else 79 proc->cpu = 0; 80 #endif 81 } 82 83 /*===========================================================================* 84 * do_noquantum * 85 *===========================================================================*/ 86 87 int do_noquantum(message *m_ptr) 88 { 89 register struct schedproc *rmp; 90 int rv, proc_nr_n; 91 92 if (sched_isokendpt(m_ptr->m_source, &proc_nr_n) != OK) { 93 printf("SCHED: WARNING: got an invalid endpoint in OOQ msg %u.\n", 94 m_ptr->m_source); 95 return EBADEPT; 96 } 97 98 rmp = &schedproc[proc_nr_n]; 99 if (rmp->priority < MIN_USER_Q) { 100 rmp->priority += 1; /* lower priority */ 101 } 102 103 if ((rv = schedule_process_local(rmp)) != OK) { 104 return rv; 105 } 106 return OK; 107 } 108 109 /*===========================================================================* 110 * do_stop_scheduling * 111 *===========================================================================*/ 112 int do_stop_scheduling(message *m_ptr) 113 { 114 register struct schedproc *rmp; 115 int proc_nr_n; 116 117 /* check who can send you requests */ 118 if (!accept_message(m_ptr)) 119 return EPERM; 120 121 if (sched_isokendpt(m_ptr->m_lsys_sched_scheduling_stop.endpoint, 122 &proc_nr_n) != OK) { 123 printf("SCHED: WARNING: got an invalid endpoint in OOQ msg " 124 "%d\n", m_ptr->m_lsys_sched_scheduling_stop.endpoint); 125 return EBADEPT; 126 } 127 128 rmp = &schedproc[proc_nr_n]; 129 #ifdef CONFIG_SMP 130 cpu_proc[rmp->cpu]--; 131 #endif 132 rmp->flags = 0; /*&= ~IN_USE;*/ 133 134 return OK; 135 } 136 137 /*===========================================================================* 138 * do_start_scheduling * 139 *===========================================================================*/ 140 int do_start_scheduling(message *m_ptr) 141 { 142 register struct schedproc *rmp; 143 int rv, proc_nr_n, parent_nr_n; 144 145 /* we can handle two kinds of messages here */ 146 assert(m_ptr->m_type == SCHEDULING_START || 147 m_ptr->m_type == SCHEDULING_INHERIT); 148 149 /* check who can send you requests */ 150 if (!accept_message(m_ptr)) 151 return EPERM; 152 153 /* Resolve endpoint to proc slot. */ 154 if ((rv = sched_isemtyendpt(m_ptr->m_lsys_sched_scheduling_start.endpoint, 155 &proc_nr_n)) != OK) { 156 return rv; 157 } 158 rmp = &schedproc[proc_nr_n]; 159 160 /* Populate process slot */ 161 rmp->endpoint = m_ptr->m_lsys_sched_scheduling_start.endpoint; 162 rmp->parent = m_ptr->m_lsys_sched_scheduling_start.parent; 163 rmp->max_priority = m_ptr->m_lsys_sched_scheduling_start.maxprio; 164 if (rmp->max_priority >= NR_SCHED_QUEUES) { 165 return EINVAL; 166 } 167 168 /* Inherit current priority and time slice from parent. Since there 169 * is currently only one scheduler scheduling the whole system, this 170 * value is local and we assert that the parent endpoint is valid */ 171 if (rmp->endpoint == rmp->parent) { 172 /* We have a special case here for init, which is the first 173 process scheduled, and the parent of itself. */ 174 rmp->priority = USER_Q; 175 rmp->time_slice = DEFAULT_USER_TIME_SLICE; 176 177 /* 178 * Since kernel never changes the cpu of a process, all are 179 * started on the BSP and the userspace scheduling hasn't 180 * changed that yet either, we can be sure that BSP is the 181 * processor where the processes run now. 182 */ 183 #ifdef CONFIG_SMP 184 rmp->cpu = machine.bsp_id; 185 /* FIXME set the cpu mask */ 186 #endif 187 } 188 189 switch (m_ptr->m_type) { 190 191 case SCHEDULING_START: 192 /* We have a special case here for system processes, for which 193 * quanum and priority are set explicitly rather than inherited 194 * from the parent */ 195 rmp->priority = rmp->max_priority; 196 rmp->time_slice = m_ptr->m_lsys_sched_scheduling_start.quantum; 197 break; 198 199 case SCHEDULING_INHERIT: 200 /* Inherit current priority and time slice from parent. Since there 201 * is currently only one scheduler scheduling the whole system, this 202 * value is local and we assert that the parent endpoint is valid */ 203 if ((rv = sched_isokendpt(m_ptr->m_lsys_sched_scheduling_start.parent, 204 &parent_nr_n)) != OK) 205 return rv; 206 207 rmp->priority = schedproc[parent_nr_n].priority; 208 rmp->time_slice = schedproc[parent_nr_n].time_slice; 209 break; 210 211 default: 212 /* not reachable */ 213 assert(0); 214 } 215 216 /* Take over scheduling the process. The kernel reply message populates 217 * the processes current priority and its time slice */ 218 if ((rv = sys_schedctl(0, rmp->endpoint, 0, 0, 0)) != OK) { 219 printf("Sched: Error taking over scheduling for %d, kernel said %d\n", 220 rmp->endpoint, rv); 221 return rv; 222 } 223 rmp->flags = IN_USE; 224 225 /* Schedule the process, giving it some quantum */ 226 pick_cpu(rmp); 227 while ((rv = schedule_process(rmp, SCHEDULE_CHANGE_ALL)) == EBADCPU) { 228 /* don't try this CPU ever again */ 229 cpu_proc[rmp->cpu] = CPU_DEAD; 230 pick_cpu(rmp); 231 } 232 233 if (rv != OK) { 234 printf("Sched: Error while scheduling process, kernel replied %d\n", 235 rv); 236 return rv; 237 } 238 239 /* Mark ourselves as the new scheduler. 240 * By default, processes are scheduled by the parents scheduler. In case 241 * this scheduler would want to delegate scheduling to another 242 * scheduler, it could do so and then write the endpoint of that 243 * scheduler into the "scheduler" field. 244 */ 245 246 m_ptr->m_sched_lsys_scheduling_start.scheduler = SCHED_PROC_NR; 247 248 return OK; 249 } 250 251 /*===========================================================================* 252 * do_nice * 253 *===========================================================================*/ 254 int do_nice(message *m_ptr) 255 { 256 struct schedproc *rmp; 257 int rv; 258 int proc_nr_n; 259 unsigned new_q, old_q, old_max_q; 260 261 /* check who can send you requests */ 262 if (!accept_message(m_ptr)) 263 return EPERM; 264 265 if (sched_isokendpt(m_ptr->m_pm_sched_scheduling_set_nice.endpoint, &proc_nr_n) != OK) { 266 printf("SCHED: WARNING: got an invalid endpoint in OoQ msg " 267 "%d\n", m_ptr->m_pm_sched_scheduling_set_nice.endpoint); 268 return EBADEPT; 269 } 270 271 rmp = &schedproc[proc_nr_n]; 272 new_q = m_ptr->m_pm_sched_scheduling_set_nice.maxprio; 273 if (new_q >= NR_SCHED_QUEUES) { 274 return EINVAL; 275 } 276 277 /* Store old values, in case we need to roll back the changes */ 278 old_q = rmp->priority; 279 old_max_q = rmp->max_priority; 280 281 /* Update the proc entry and reschedule the process */ 282 rmp->max_priority = rmp->priority = new_q; 283 284 if ((rv = schedule_process_local(rmp)) != OK) { 285 /* Something went wrong when rescheduling the process, roll 286 * back the changes to proc struct */ 287 rmp->priority = old_q; 288 rmp->max_priority = old_max_q; 289 } 290 291 return rv; 292 } 293 294 /*===========================================================================* 295 * schedule_process * 296 *===========================================================================*/ 297 static int schedule_process(struct schedproc * rmp, unsigned flags) 298 { 299 int err; 300 int new_prio, new_quantum, new_cpu, niced; 301 302 pick_cpu(rmp); 303 304 if (flags & SCHEDULE_CHANGE_PRIO) 305 new_prio = rmp->priority; 306 else 307 new_prio = -1; 308 309 if (flags & SCHEDULE_CHANGE_QUANTUM) 310 new_quantum = rmp->time_slice; 311 else 312 new_quantum = -1; 313 314 if (flags & SCHEDULE_CHANGE_CPU) 315 new_cpu = rmp->cpu; 316 else 317 new_cpu = -1; 318 319 niced = (rmp->max_priority > USER_Q); 320 321 if ((err = sys_schedule(rmp->endpoint, new_prio, 322 new_quantum, new_cpu, niced)) != OK) { 323 printf("PM: An error occurred when trying to schedule %d: %d\n", 324 rmp->endpoint, err); 325 } 326 327 return err; 328 } 329 330 331 /*===========================================================================* 332 * init_scheduling * 333 *===========================================================================*/ 334 void init_scheduling(void) 335 { 336 int r; 337 338 balance_timeout = BALANCE_TIMEOUT * sys_hz(); 339 340 if ((r = sys_setalarm(balance_timeout, 0)) != OK) 341 panic("sys_setalarm failed: %d", r); 342 } 343 344 /*===========================================================================* 345 * balance_queues * 346 *===========================================================================*/ 347 348 /* This function in called every N ticks to rebalance the queues. The current 349 * scheduler bumps processes down one priority when ever they run out of 350 * quantum. This function will find all proccesses that have been bumped down, 351 * and pulls them back up. This default policy will soon be changed. 352 */ 353 void balance_queues(void) 354 { 355 struct schedproc *rmp; 356 int r, proc_nr; 357 358 for (proc_nr=0, rmp=schedproc; proc_nr < NR_PROCS; proc_nr++, rmp++) { 359 if (rmp->flags & IN_USE) { 360 if (rmp->priority > rmp->max_priority) { 361 rmp->priority -= 1; /* increase priority */ 362 schedule_process_local(rmp); 363 } 364 } 365 } 366 367 if ((r = sys_setalarm(balance_timeout, 0)) != OK) 368 panic("sys_setalarm failed: %d", r); 369 } 370