root/kernel/sched.c

/* */

DEFINITIONS

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

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

/* */