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

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