servers/sched/schedule.c

   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 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(struct timer *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->SCHEDULING_ENDPOINT, &proc_nr_n) != OK) {
 125                 printf("SCHED: WARNING: got an invalid endpoint in OOQ msg "
 126                 "%ld\n", m_ptr->SCHEDULING_ENDPOINT);
 127                 return EBADEPT;
 128         }
 129
 130         rmp = &schedproc[proc_nr_n];
 131 #ifdef CONFIG_SMP
 132         cpu_proc[rmp->cpu]--;
 133 #endif
 134         rmp->flags = 0; /*&= ~IN_USE;*/
 135
 136         return OK;
 137 }
 138
 139 /*===========================================================================*
 140  *                              do_start_scheduling                          *
 141  *===========================================================================*/
 142 int do_start_scheduling(message *m_ptr)
 143 {
 144         register struct schedproc *rmp;
 145         int rv, proc_nr_n, parent_nr_n;
 146
 147         /* we can handle two kinds of messages here */
 148         assert(m_ptr->m_type == SCHEDULING_START ||
 149                 m_ptr->m_type == SCHEDULING_INHERIT);
 150
 151         /* check who can send you requests */
 152         if (!accept_message(m_ptr))
 153                 return EPERM;
 154
 155         /* Resolve endpoint to proc slot. */
 156         if ((rv = sched_isemtyendpt(m_ptr->SCHEDULING_ENDPOINT, &proc_nr_n))
 157                         != OK) {
 158                 return rv;
 159         }
 160         rmp = &schedproc[proc_nr_n];
 161
 162         /* Populate process slot */
 163         rmp->endpoint     = m_ptr->SCHEDULING_ENDPOINT;
 164         rmp->parent       = m_ptr->SCHEDULING_PARENT;
 165         rmp->max_priority = (unsigned) m_ptr->SCHEDULING_MAXPRIO;
 166         if (rmp->max_priority >= NR_SCHED_QUEUES) {
 167                 return EINVAL;
 168         }
 169
 170         /* Inherit current priority and time slice from parent. Since there
 171          * is currently only one scheduler scheduling the whole system, this
 172          * value is local and we assert that the parent endpoint is valid */
 173         if (rmp->endpoint == rmp->parent) {
 174                 /* We have a special case here for init, which is the first
 175                    process scheduled, and the parent of itself. */
 176                 rmp->priority   = USER_Q;
 177                 rmp->time_slice = DEFAULT_USER_TIME_SLICE;
 178
 179                 /*
 180                  * Since kernel never changes the cpu of a process, all are
 181                  * started on the BSP and the userspace scheduling hasn't
 182                  * changed that yet either, we can be sure that BSP is the
 183                  * processor where the processes run now.
 184                  */
 185 #ifdef CONFIG_SMP
 186                 rmp->cpu = machine.bsp_id;
 187                 /* FIXME set the cpu mask */
 188 #endif
 189         }
 190
 191         switch (m_ptr->m_type) {
 192
 193         case SCHEDULING_START:
 194                 /* We have a special case here for system processes, for which
 195                  * quanum and priority are set explicitly rather than inherited
 196                  * from the parent */
 197                 rmp->priority   = rmp->max_priority;
 198                 rmp->time_slice = (unsigned) m_ptr->SCHEDULING_QUANTUM;
 199                 break;
 200
 201         case SCHEDULING_INHERIT:
 202                 /* Inherit current priority and time slice from parent. Since there
 203                  * is currently only one scheduler scheduling the whole system, this
 204                  * value is local and we assert that the parent endpoint is valid */
 205                 if ((rv = sched_isokendpt(m_ptr->SCHEDULING_PARENT,
 206                                 &parent_nr_n)) != OK)
 207                         return rv;
 208
 209                 rmp->priority = schedproc[parent_nr_n].priority;
 210                 rmp->time_slice = schedproc[parent_nr_n].time_slice;
 211                 break;
 212
 213         default:
 214                 /* not reachable */
 215                 assert(0);
 216         }
 217
 218         /* Take over scheduling the process. The kernel reply message populates
 219          * the processes current priority and its time slice */
 220         if ((rv = sys_schedctl(0, rmp->endpoint, 0, 0, 0)) != OK) {
 221                 printf("Sched: Error taking over scheduling for %d, kernel said %d\n",
 222                         rmp->endpoint, rv);
 223                 return rv;
 224         }
 225         rmp->flags = IN_USE;
 226
 227         /* Schedule the process, giving it some quantum */
 228         pick_cpu(rmp);
 229         while ((rv = schedule_process(rmp, SCHEDULE_CHANGE_ALL)) == EBADCPU) {
 230                 /* don't try this CPU ever again */
 231                 cpu_proc[rmp->cpu] = CPU_DEAD;
 232                 pick_cpu(rmp);
 233         }
 234
 235         if (rv != OK) {
 236                 printf("Sched: Error while scheduling process, kernel replied %d\n",
 237                         rv);
 238                 return rv;
 239         }
 240
 241         /* Mark ourselves as the new scheduler.
 242          * By default, processes are scheduled by the parents scheduler. In case
 243          * this scheduler would want to delegate scheduling to another
 244          * scheduler, it could do so and then write the endpoint of that
 245          * scheduler into SCHEDULING_SCHEDULER
 246          */
 247
 248         m_ptr->SCHEDULING_SCHEDULER = SCHED_PROC_NR;
 249
 250         return OK;
 251 }
 252
 253 /*===========================================================================*
 254  *                              do_nice                                      *
 255  *===========================================================================*/
 256 int do_nice(message *m_ptr)
 257 {
 258         struct schedproc *rmp;
 259         int rv;
 260         int proc_nr_n;
 261         unsigned new_q, old_q, old_max_q;
 262
 263         /* check who can send you requests */
 264         if (!accept_message(m_ptr))
 265                 return EPERM;
 266
 267         if (sched_isokendpt(m_ptr->SCHEDULING_ENDPOINT, &proc_nr_n) != OK) {
 268                 printf("SCHED: WARNING: got an invalid endpoint in OOQ msg "
 269                 "%ld\n", m_ptr->SCHEDULING_ENDPOINT);
 270                 return EBADEPT;
 271         }
 272
 273         rmp = &schedproc[proc_nr_n];
 274         new_q = (unsigned) m_ptr->SCHEDULING_MAXPRIO;
 275         if (new_q >= NR_SCHED_QUEUES) {
 276                 return EINVAL;
 277         }
 278
 279         /* Store old values, in case we need to roll back the changes */
 280         old_q     = rmp->priority;
 281         old_max_q = rmp->max_priority;
 282
 283         /* Update the proc entry and reschedule the process */
 284         rmp->max_priority = rmp->priority = new_q;
 285
 286         if ((rv = schedule_process_local(rmp)) != OK) {
 287                 /* Something went wrong when rescheduling the process, roll
 288                  * back the changes to proc struct */
 289                 rmp->priority     = old_q;
 290                 rmp->max_priority = old_max_q;
 291         }
 292
 293         return rv;
 294 }
 295
 296 /*===========================================================================*
 297  *                              schedule_process                             *
 298  *===========================================================================*/
 299 static int schedule_process(struct schedproc * rmp, unsigned flags)
 300 {
 301         int err;
 302         int new_prio, new_quantum, new_cpu;
 303
 304         pick_cpu(rmp);
 305
 306         if (flags & SCHEDULE_CHANGE_PRIO)
 307                 new_prio = rmp->priority;
 308         else
 309                 new_prio = -1;
 310
 311         if (flags & SCHEDULE_CHANGE_QUANTUM)
 312                 new_quantum = rmp->time_slice;
 313         else
 314                 new_quantum = -1;
 315
 316         if (flags & SCHEDULE_CHANGE_CPU)
 317                 new_cpu = rmp->cpu;
 318         else
 319                 new_cpu = -1;
 320
 321         if ((err = sys_schedule(rmp->endpoint, new_prio,
 322                 new_quantum, new_cpu)) != 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  *                              start_scheduling                             *
 333  *===========================================================================*/
 334
 335 void init_scheduling(void)
 336 {
 337         balance_timeout = BALANCE_TIMEOUT * sys_hz();
 338         init_timer(&sched_timer);
 339         set_timer(&sched_timer, balance_timeout, balance_queues, 0);
 340 }
 341
 342 /*===========================================================================*
 343  *                              balance_queues                               *
 344  *===========================================================================*/
 345
 346 /* This function in called every 100 ticks to rebalance the queues. The current
 347  * scheduler bumps processes down one priority when ever they run out of
 348  * quantum. This function will find all proccesses that have been bumped down,
 349  * and pulls them back up. This default policy will soon be changed.
 350  */
 351 static void balance_queues(struct timer *tp)
 352 {
 353         struct schedproc *rmp;
 354         int proc_nr;
 355
 356         for (proc_nr=0, rmp=schedproc; proc_nr < NR_PROCS; proc_nr++, rmp++) {
 357                 if (rmp->flags & IN_USE) {
 358                         if (rmp->priority > rmp->max_priority) {
 359                                 rmp->priority -= 1; /* increase priority */
 360                                 schedule_process_local(rmp);
 361                         }
 362                 }
 363         }
 364
 365         set_timer(&sched_timer, balance_timeout, balance_queues, 0);
 366 }