root/kernel/sched.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. show_task
  2. show_state
  3. math_state_restore
  4. schedule
  5. sys_pause
  6. wake_one_task
  7. wake_up
  8. __sleep_on
  9. interruptible_sleep_on
  10. sleep_on
  11. ticks_to_floppy_on
  12. floppy_off
  13. do_floppy_timer
  14. add_timer
  15. count_active_tasks
  16. calc_load
  17. do_timer
  18. sys_alarm
  19. sys_getpid
  20. sys_getppid
  21. sys_getuid
  22. sys_geteuid
  23. sys_getgid
  24. sys_getegid
  25. sys_nice
  26. sched_init

   1 /*
   2  *  linux/kernel/sched.c
   3  *
   4  *  Copyright (C) 1991, 1992  Linus Torvalds
   5  */
   6 
   7 /*
   8  * 'sched.c' is the main kernel file. It contains scheduling primitives
   9  * (sleep_on, wakeup, schedule etc) as well as a number of simple system
  10  * call functions (type getpid(), which just extracts a field from
  11  * current-task
  12  */
  13 
  14 #define TIMER_IRQ 0
  15 
  16 #include <linux/signal.h>
  17 #include <linux/sched.h>
  18 #include <linux/timer.h>
  19 #include <linux/kernel.h>
  20 #include <linux/sys.h>
  21 #include <linux/fdreg.h>
  22 #include <linux/errno.h>
  23 #include <linux/time.h>
  24 #include <linux/ptrace.h>
  25 
  26 #include <asm/system.h>
  27 #include <asm/io.h>
  28 #include <asm/segment.h>
  29 
  30 int need_resched = 0;
  31 
  32 unsigned long * prof_buffer = NULL;
  33 unsigned long prof_len = 0;
  34 
  35 #define _S(nr) (1<<((nr)-1))
  36 #define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))
  37 
  38 static void show_task(int nr,struct task_struct * p)
     /* [previous][next][first][last][top][bottom][index][help] */
  39 {
  40         int i,j = 4096-sizeof(struct task_struct);
  41 
  42         printk("%d: pid=%d, state=%d, father=%d, child=%d, ",(p == current)?-nr:nr,p->pid,
  43                 p->state, p->p_pptr->pid, p->p_cptr ? p->p_cptr->pid : -1);
  44         i=0;
  45         while (i<j && !((char *)(p+1))[i])
  46                 i++;
  47         printk("%d/%d chars free in kstack\n\r",i,j);
  48         printk("   PC=%08X.", *(1019 + (unsigned long *) p));
  49         if (p->p_ysptr || p->p_osptr) 
  50                 printk("   Younger sib=%d, older sib=%d\n\r", 
  51                         p->p_ysptr ? p->p_ysptr->pid : -1,
  52                         p->p_osptr ? p->p_osptr->pid : -1);
  53         else
  54                 printk("\n\r");
  55 }
  56 
  57 void show_state(void)
     /* [previous][next][first][last][top][bottom][index][help] */
  58 {
  59         int i;
  60 
  61         printk("\rTask-info:\n\r");
  62         for (i=0 ; i<NR_TASKS ; i++)
  63                 if (task[i])
  64                         show_task(i,task[i]);
  65 }
  66 
  67 #define LATCH (1193180/HZ)
  68 
  69 extern void mem_use(void);
  70 
  71 extern int timer_interrupt(void);
  72 extern int system_call(void);
  73 
  74 union task_union {
  75         struct task_struct task;
  76         char stack[PAGE_SIZE];
  77 };
  78 
  79 static union task_union init_task = {INIT_TASK, };
  80 
  81 unsigned long volatile jiffies=0;
  82 unsigned long startup_time=0;
  83 int jiffies_offset = 0;         /* # clock ticks to add to get "true
  84                                    time".  Should always be less than
  85                                    1 second's worth.  For time fanatics
  86                                    who like to syncronize their machines
  87                                    to WWV :-) */
  88 
  89 struct task_struct *current = &(init_task.task);
  90 struct task_struct *last_task_used_math = NULL;
  91 
  92 struct task_struct * task[NR_TASKS] = {&(init_task.task), };
  93 
  94 long user_stack [ PAGE_SIZE>>2 ] ;
  95 
  96 struct {
  97         long * a;
  98         short b;
  99         } stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
 100 /*
 101  *  'math_state_restore()' saves the current math information in the
 102  * old math state array, and gets the new ones from the current task
 103  */
 104 void math_state_restore()
     /* [previous][next][first][last][top][bottom][index][help] */
 105 {
 106         if (last_task_used_math == current)
 107                 return;
 108         __asm__("fwait");
 109         if (last_task_used_math) {
 110                 __asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
 111         }
 112         last_task_used_math=current;
 113         if (current->used_math) {
 114                 __asm__("frstor %0"::"m" (current->tss.i387));
 115         } else {
 116                 __asm__("fninit"::);
 117                 current->used_math=1;
 118         }
 119 }
 120 
 121 /*
 122  *  'schedule()' is the scheduler function. It's a very simple and nice
 123  * scheduler: it's not perfect, but certainly works for most things.
 124  * The one thing you might take a look at is the signal-handler code here.
 125  *
 126  *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 127  * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 128  * information in task[0] is never used.
 129  */
 130 void schedule(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 131 {
 132         int i,next,c;
 133         struct task_struct ** p;
 134 
 135 /* check alarm, wake up any interruptible tasks that have got a signal */
 136 
 137         need_resched = 0;
 138         for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
 139                 if (*p) {
 140                         if ((*p)->timeout && (*p)->timeout < jiffies)
 141                                 if ((*p)->state == TASK_INTERRUPTIBLE) {
 142                                         (*p)->timeout = 0;
 143                                         wake_one_task(*p);
 144                                 }
 145                         if (((*p)->signal & ~(*p)->blocked) &&
 146                             (*p)->state==TASK_INTERRUPTIBLE)
 147                                 wake_one_task(*p);
 148                 }
 149 
 150 /* this is the scheduler proper: */
 151 
 152         while (1) {
 153                 c = -1;
 154                 next = 0;
 155                 i = NR_TASKS;
 156                 p = &task[NR_TASKS];
 157                 while (--i) {
 158                         if (!*--p)
 159                                 continue;
 160                         if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
 161                                 c = (*p)->counter, next = i;
 162                 }
 163                 if (c)
 164                         break;
 165                 for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
 166                         if (*p)
 167                                 (*p)->counter = ((*p)->counter >> 1) +
 168                                                 (*p)->priority;
 169         }
 170         sti();
 171         switch_to(next);
 172 }
 173 
 174 int sys_pause(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 175 {
 176         unsigned long old_blocked;
 177         unsigned long mask;
 178         struct sigaction * sa = current->sigaction;
 179 
 180         old_blocked = current->blocked;
 181         for (mask=1 ; mask ; sa++,mask += mask)
 182                 if (sa->sa_handler == SIG_IGN)
 183                         current->blocked |= mask;
 184         current->state = TASK_INTERRUPTIBLE;
 185         schedule();
 186         current->blocked = old_blocked;
 187         return -EINTR;
 188 }
 189 
 190 void wake_one_task(struct task_struct * p)
     /* [previous][next][first][last][top][bottom][index][help] */
 191 {
 192         p->state = TASK_RUNNING;
 193         if (p->counter > current->counter)
 194                 need_resched = 1;
 195 }
 196 
 197 /*
 198  * wake_up doesn't wake up stopped processes - they have to be awakened
 199  * with signals or similar.
 200  */
 201 void wake_up(struct wait_queue **q)
     /* [previous][next][first][last][top][bottom][index][help] */
 202 {
 203         struct wait_queue *tmp, *next;
 204         struct task_struct * p;
 205         unsigned long flags;
 206 
 207         if (!q || !(next = *q))
 208                 return;
 209         __asm__ __volatile__("pushfl ; popl %0 ; cli":"=r" (flags));
 210         do {
 211                 tmp = next;
 212                 next = tmp->next;
 213                 if (p = tmp->task) {
 214                         if (p->state == TASK_ZOMBIE)
 215                                 printk("wake_up: TASK_ZOMBIE\n");
 216                         else if (p->state != TASK_STOPPED) {
 217                                 p->state = TASK_RUNNING;
 218                                 if (p->counter > current->counter)
 219                                         need_resched = 1;
 220                         }
 221                 }
 222                 tmp->next = NULL;
 223         } while (next && next != *q);
 224         __asm__ __volatile__("pushl %0 ; popfl"::"r" (flags));
 225 }
 226 
 227 static inline void __sleep_on(struct wait_queue **p, int state)
     /* [previous][next][first][last][top][bottom][index][help] */
 228 {
 229         unsigned long flags;
 230 
 231         if (!p)
 232                 return;
 233         if (current == task[0])
 234                 panic("task[0] trying to sleep");
 235         if (current->wait.next)
 236                 printk("__sleep_on: wait->next exists\n");
 237         __asm__ __volatile__("pushfl ; popl %0 ; cli":"=r" (flags));
 238         current->state = state;
 239         add_wait_queue(p,&current->wait);
 240         sti();
 241         schedule();
 242         remove_wait_queue(p,&current->wait);
 243         __asm__("pushl %0 ; popfl"::"r" (flags));
 244 }
 245 
 246 void interruptible_sleep_on(struct wait_queue **p)
     /* [previous][next][first][last][top][bottom][index][help] */
 247 {
 248         __sleep_on(p,TASK_INTERRUPTIBLE);
 249 }
 250 
 251 void sleep_on(struct wait_queue **p)
     /* [previous][next][first][last][top][bottom][index][help] */
 252 {
 253         __sleep_on(p,TASK_UNINTERRUPTIBLE);
 254 }
 255 
 256 /*
 257  * OK, here are some floppy things that shouldn't be in the kernel
 258  * proper. They are here because the floppy needs a timer, and this
 259  * was the easiest way of doing it.
 260  */
 261 static struct wait_queue * wait_motor[4] = {NULL,NULL,NULL,NULL};
 262 static int  mon_timer[4]={0,0,0,0};
 263 static int moff_timer[4]={0,0,0,0};
 264 unsigned char current_DOR = 0x0C;
 265 
 266 int ticks_to_floppy_on(unsigned int nr)
     /* [previous][next][first][last][top][bottom][index][help] */
 267 {
 268         extern unsigned char selected;
 269         unsigned char mask = 0x10 << nr;
 270 
 271         if (nr>3)
 272                 panic("floppy_on: nr>3");
 273         moff_timer[nr]=10000;           /* 100 s = very big :-) */
 274         cli();                          /* use floppy_off to turn it off */
 275         mask |= current_DOR;
 276         if (!selected) {
 277                 mask &= 0xFC;
 278                 mask |= nr;
 279         }
 280         if (mask != current_DOR) {
 281                 outb(mask,FD_DOR);
 282                 if ((mask ^ current_DOR) & 0xf0)
 283                         mon_timer[nr] = HZ/2;
 284                 else if (mon_timer[nr] < 2)
 285                         mon_timer[nr] = 2;
 286                 current_DOR = mask;
 287         }
 288         sti();
 289         return mon_timer[nr];
 290 }
 291 
 292 void floppy_off(unsigned int nr)
     /* [previous][next][first][last][top][bottom][index][help] */
 293 {
 294         moff_timer[nr]=3*HZ;
 295 }
 296 
 297 void do_floppy_timer(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 298 {
 299         int i;
 300         unsigned char mask = 0x10;
 301 
 302         for (i=0 ; i<4 ; i++,mask <<= 1) {
 303                 if (!(mask & current_DOR))
 304                         continue;
 305                 if (mon_timer[i]) {
 306                         if (!--mon_timer[i])
 307                                 wake_up(i+wait_motor);
 308                 } else if (!moff_timer[i]) {
 309                         current_DOR &= ~mask;
 310                         outb(current_DOR,FD_DOR);
 311                 } else
 312                         moff_timer[i]--;
 313         }
 314 }
 315 
 316 #define TIME_REQUESTS 64
 317 
 318 static struct timer_list {
 319         long jiffies;
 320         void (*fn)();
 321         struct timer_list * next;
 322 } timer_list[TIME_REQUESTS] = { { 0, NULL, NULL }, };
 323 
 324 static struct timer_list * next_timer = NULL;
 325 
 326 void add_timer(long jiffies, void (*fn)(void))
     /* [previous][next][first][last][top][bottom][index][help] */
 327 {
 328         struct timer_list * p;
 329 
 330         if (!fn)
 331                 return;
 332         cli();
 333         if (jiffies <= 0)
 334                 (fn)();
 335         else {
 336                 for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
 337                         if (!p->fn)
 338                                 break;
 339                 if (p >= timer_list + TIME_REQUESTS)
 340                         panic("No more time requests free");
 341                 p->fn = fn;
 342                 p->jiffies = jiffies;
 343                 p->next = next_timer;
 344                 next_timer = p;
 345                 while (p->next && p->next->jiffies < p->jiffies) {
 346                         p->jiffies -= p->next->jiffies;
 347                         fn = p->fn;
 348                         p->fn = p->next->fn;
 349                         p->next->fn = fn;
 350                         jiffies = p->jiffies;
 351                         p->jiffies = p->next->jiffies;
 352                         p->next->jiffies = jiffies;
 353                         p = p->next;
 354                 }
 355         }
 356         sti();
 357 }
 358 
 359 unsigned long timer_active = 0;
 360 struct timer_struct timer_table[32];
 361 
 362 /*
 363  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
 364  * imply that avenrun[] is the standard name for this kind of thing.
 365  * Nothing else seems to be standardized: the fractional size etc
 366  * all seem to differ on different machines.
 367  */
 368 unsigned long avenrun[3] = { 0,0,0 };
 369 
 370 /*
 371  * Nr of active tasks - counted in fixed-point numbers
 372  */
 373 static unsigned long count_active_tasks(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 374 {
 375         struct task_struct **p;
 376         unsigned long nr = 0;
 377 
 378         for(p = &LAST_TASK; p > &FIRST_TASK; --p)
 379                 if (*p && (*p)->state == TASK_RUNNING)
 380                         nr += FIXED_1;
 381         return nr;
 382 }
 383 
 384 static inline void calc_load(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 385 {
 386         unsigned long active_tasks; /* fixed-point */
 387         static int count = LOAD_FREQ;
 388 
 389         if (count-- > 0)
 390                 return;
 391         count = LOAD_FREQ;
 392         active_tasks = count_active_tasks();
 393         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
 394         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
 395         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
 396 }
 397 
 398 /*
 399  * The int argument is really a (struct pt_regs *), in case the
 400  * interrupt wants to know from where it was called. The timer
 401  * irq uses this to decide if it should update the user or system
 402  * times.
 403  */
 404 static void do_timer(struct pt_regs * regs)
     /* [previous][next][first][last][top][bottom][index][help] */
 405 {
 406         unsigned long mask;
 407         struct timer_struct *tp = timer_table+0;
 408         struct task_struct ** task_p;
 409 
 410         jiffies++;
 411         calc_load();
 412         if ((VM_MASK & regs->eflags) || (3 & regs->cs)) {
 413                 current->utime++;
 414                 /* Update ITIMER_VIRT for current task if not in a system call */
 415                 if (current->it_virt_value && !(--current->it_virt_value)) {
 416                         current->it_virt_value = current->it_virt_incr;
 417                         send_sig(SIGVTALRM,current,1);
 418                 }
 419         } else {
 420                 current->stime++;
 421 #ifdef PROFILE_SHIFT
 422                 if (prof_buffer && current != task[0]) {
 423                         unsigned long eip = regs->eip;
 424                         eip >>= PROFILE_SHIFT;
 425                         if (eip < prof_len)
 426                                 prof_buffer[eip]++;
 427                 }
 428 #endif
 429         }
 430         if (current == task[0] || (--current->counter)<=0) {
 431                 current->counter=0;
 432                 need_resched = 1;
 433         }
 434         /* Update ITIMER_REAL for every task */
 435         for (task_p = &LAST_TASK; task_p >= &FIRST_TASK; task_p--)
 436                 if (*task_p && (*task_p)->it_real_value
 437                         && !(--(*task_p)->it_real_value)) {
 438                         send_sig(SIGALRM,*task_p,1);
 439                         (*task_p)->it_real_value = (*task_p)->it_real_incr;
 440                         need_resched = 1;
 441                 }
 442         /* Update ITIMER_PROF for the current task */
 443         if (current->it_prof_value && !(--current->it_prof_value)) {
 444                 current->it_prof_value = current->it_prof_incr;
 445                 send_sig(SIGPROF,current,1);
 446         }
 447         for (mask = 1 ; mask ; tp++,mask += mask) {
 448                 if (mask > timer_active)
 449                         break;
 450                 if (!(mask & timer_active))
 451                         continue;
 452                 if (tp->expires > jiffies)
 453                         continue;
 454                 timer_active &= ~mask;
 455                 tp->fn();
 456                 sti();
 457         }
 458         if (next_timer) {
 459                 next_timer->jiffies--;
 460                 while (next_timer && next_timer->jiffies <= 0) {
 461                         void (*fn)(void);
 462                         
 463                         fn = next_timer->fn;
 464                         next_timer->fn = NULL;
 465                         next_timer = next_timer->next;
 466                         (fn)();
 467                 }
 468         }
 469         if (current_DOR & 0xf0)
 470                 do_floppy_timer();
 471 }
 472 
 473 int sys_alarm(long seconds)
     /* [previous][next][first][last][top][bottom][index][help] */
 474 {
 475         extern int _setitimer(int, struct itimerval *, struct itimerval *);
 476         struct itimerval new, old;
 477 
 478         new.it_interval.tv_sec = new.it_interval.tv_usec = 0;
 479         new.it_value.tv_sec = seconds;
 480         new.it_value.tv_usec = 0;
 481         _setitimer(ITIMER_REAL, &new, &old);
 482         return(old.it_value.tv_sec + (old.it_value.tv_usec / 1000000));
 483 }
 484 
 485 int sys_getpid(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 486 {
 487         return current->pid;
 488 }
 489 
 490 int sys_getppid(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 491 {
 492         return current->p_pptr->pid;
 493 }
 494 
 495 int sys_getuid(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 496 {
 497         return current->uid;
 498 }
 499 
 500 int sys_geteuid(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 501 {
 502         return current->euid;
 503 }
 504 
 505 int sys_getgid(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 506 {
 507         return current->gid;
 508 }
 509 
 510 int sys_getegid(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 511 {
 512         return current->egid;
 513 }
 514 
 515 int sys_nice(long increment)
     /* [previous][next][first][last][top][bottom][index][help] */
 516 {
 517         if (increment < 0 && !suser())
 518                 return -EPERM;
 519         if (increment >= current->priority)
 520                 increment = current->priority-1;
 521         current->priority -= increment;
 522         return 0;
 523 }
 524 
 525 void sched_init(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 526 {
 527         int i;
 528         struct desc_struct * p;
 529 
 530         if (sizeof(struct sigaction) != 16)
 531                 panic("Struct sigaction MUST be 16 bytes");
 532         set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));
 533         set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));
 534         set_system_gate(0x80,&system_call);
 535         p = gdt+2+FIRST_TSS_ENTRY;
 536         for(i=1 ; i<NR_TASKS ; i++) {
 537                 task[i] = NULL;
 538                 p->a=p->b=0;
 539                 p++;
 540                 p->a=p->b=0;
 541                 p++;
 542         }
 543 /* Clear NT, so that we won't have troubles with that later on */
 544         __asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
 545         ltr(0);
 546         lldt(0);
 547         outb_p(0x36,0x43);              /* binary, mode 3, LSB/MSB, ch 0 */
 548         outb_p(LATCH & 0xff , 0x40);    /* LSB */
 549         outb(LATCH >> 8 , 0x40);        /* MSB */
 550         request_irq(TIMER_IRQ,(void (*)(int)) do_timer);
 551 }

/* [previous][next][first][last][top][bottom][index][help] */