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