Linux0.96c/kernel/sched.c
/*
* linux/kernel/sched.c
*
* (C) 1991 Linus Torvalds
*/
/*
* 'sched.c' is the main kernel file. It contains scheduling primitives
* (sleep_on, wakeup, schedule etc) as well as a number of simple system
* call functions (type getpid(), which just extracts a field from
* current-task
*/
#include <linux/sched.h>
#include <linux/timer.h>
#include <linux/kernel.h>
#include <linux/sys.h>
#include <linux/fdreg.h>
#include <asm/system.h>
#include <asm/io.h>
#include <asm/segment.h>
#include <sys/time.h>
#include <signal.h>
#include <errno.h>
int need_resched = 0;
#define _S(nr) (1<<((nr)-1))
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))
static void show_task(int nr,struct task_struct * p)
{
int i,j = 4096-sizeof(struct task_struct);
printk("%d: pid=%d, state=%d, father=%d, child=%d, ",nr,p->pid,
p->state, p->p_pptr->pid, p->p_cptr ? p->p_cptr->pid : -1);
i=0;
while (i<j && !((char *)(p+1))[i])
i++;
printk("%d/%d chars free in kstack\n\r",i,j);
printk(" PC=%08X.", *(1019 + (unsigned long *) p));
if (p->p_ysptr || p->p_osptr)
printk(" Younger sib=%d, older sib=%d\n\r",
p->p_ysptr ? p->p_ysptr->pid : -1,
p->p_osptr ? p->p_osptr->pid : -1);
else
printk("\n\r");
}
void show_state(void)
{
int i;
printk("\rTask-info:\n\r");
for (i=0 ; i<NR_TASKS ; i++)
if (task[i])
show_task(i,task[i]);
}
#define LATCH (1193180/HZ)
extern void mem_use(void);
extern int timer_interrupt(void);
extern int system_call(void);
union task_union {
struct task_struct task;
char stack[PAGE_SIZE];
};
static union task_union init_task = {INIT_TASK, };
unsigned long volatile jiffies=0;
unsigned long startup_time=0;
int jiffies_offset = 0; /* # clock ticks to add to get "true
time". Should always be less than
1 second's worth. For time fanatics
who like to syncronize their machines
to WWV :-) */
struct task_struct *current = &(init_task.task);
struct task_struct *last_task_used_math = NULL;
struct task_struct * task[NR_TASKS] = {&(init_task.task), };
long user_stack [ PAGE_SIZE>>2 ] ;
struct {
long * a;
short b;
} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
/*
* 'math_state_restore()' saves the current math information in the
* old math state array, and gets the new ones from the current task
*/
void math_state_restore()
{
if (last_task_used_math == current)
return;
__asm__("fwait");
if (last_task_used_math) {
__asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
}
last_task_used_math=current;
if (current->used_math) {
__asm__("frstor %0"::"m" (current->tss.i387));
} else {
__asm__("fninit"::);
current->used_math=1;
}
}
/*
* 'schedule()' is the scheduler function. It's a very simple and nice
* scheduler: it's not perfect, but certainly works for most things.
* The one thing you might take a look at is the signal-handler code here.
*
* NOTE!! Task 0 is the 'idle' task, which gets called when no other
* tasks can run. It can not be killed, and it cannot sleep. The 'state'
* information in task[0] is never used.
*/
void schedule(void)
{
int i,next,c;
struct task_struct ** p;
/* check alarm, wake up any interruptible tasks that have got a signal */
need_resched = 0;
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) {
if ((*p)->timeout && (*p)->timeout < jiffies)
if ((*p)->state == TASK_INTERRUPTIBLE) {
(*p)->timeout = 0;
(*p)->state = TASK_RUNNING;
}
if (((*p)->signal & ~(*p)->blocked) &&
(*p)->state==TASK_INTERRUPTIBLE)
(*p)->state=TASK_RUNNING;
}
/* this is the scheduler proper: */
while (1) {
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
if (c) break;
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
}
switch_to(next);
}
int sys_pause(void)
{
unsigned long old_blocked;
unsigned long mask;
struct sigaction * sa = current->sigaction;
old_blocked = current->blocked;
for (mask=1 ; mask ; sa++,mask += mask)
if (sa->sa_handler == SIG_IGN)
current->blocked |= mask;
current->state = TASK_INTERRUPTIBLE;
schedule();
current->blocked = old_blocked;
return -EINTR;
}
/*
* wake_up doesn't wake up stopped processes - they have to be awakened
* with signals or similar.
*/
void wake_up(struct task_struct **p)
{
struct task_struct * wakeup_ptr, * tmp;
if (p && *p) {
wakeup_ptr = *p;
*p = NULL;
while (wakeup_ptr && wakeup_ptr != task[0]) {
if (wakeup_ptr->state == TASK_ZOMBIE)
printk("wake_up: TASK_ZOMBIE\n");
else if (wakeup_ptr->state != TASK_STOPPED) {
wakeup_ptr->state = TASK_RUNNING;
if (wakeup_ptr->counter > current->counter)
need_resched = 1;
}
tmp = wakeup_ptr->next_wait;
wakeup_ptr->next_wait = task[0];
wakeup_ptr = tmp;
}
}
}
static inline void __sleep_on(struct task_struct **p, int state)
{
unsigned int flags;
if (!p)
return;
if (current == task[0])
panic("task[0] trying to sleep");
__asm__("pushfl ; popl %0":"=r" (flags));
current->next_wait = *p;
task[0]->next_wait = NULL;
*p = current;
current->state = state;
sti();
schedule();
if (current->next_wait != task[0])
wake_up(p);
current->next_wait = NULL;
__asm__("pushl %0 ; popfl"::"r" (flags));
}
void interruptible_sleep_on(struct task_struct **p)
{
__sleep_on(p,TASK_INTERRUPTIBLE);
}
void sleep_on(struct task_struct **p)
{
__sleep_on(p,TASK_UNINTERRUPTIBLE);
}
/*
* OK, here are some floppy things that shouldn't be in the kernel
* proper. They are here because the floppy needs a timer, and this
* was the easiest way of doing it.
*/
static struct task_struct * wait_motor[4] = {NULL,NULL,NULL,NULL};
static int mon_timer[4]={0,0,0,0};
static int moff_timer[4]={0,0,0,0};
unsigned char current_DOR = 0x0C;
int ticks_to_floppy_on(unsigned int nr)
{
extern unsigned char selected;
unsigned char mask = 0x10 << nr;
if (nr>3)
panic("floppy_on: nr>3");
moff_timer[nr]=10000; /* 100 s = very big :-) */
cli(); /* use floppy_off to turn it off */
mask |= current_DOR;
if (!selected) {
mask &= 0xFC;
mask |= nr;
}
if (mask != current_DOR) {
outb(mask,FD_DOR);
if ((mask ^ current_DOR) & 0xf0)
mon_timer[nr] = HZ/2;
else if (mon_timer[nr] < 2)
mon_timer[nr] = 2;
current_DOR = mask;
}
sti();
return mon_timer[nr];
}
void floppy_off(unsigned int nr)
{
moff_timer[nr]=3*HZ;
}
void do_floppy_timer(void)
{
int i;
unsigned char mask = 0x10;
for (i=0 ; i<4 ; i++,mask <<= 1) {
if (!(mask & current_DOR))
continue;
if (mon_timer[i]) {
if (!--mon_timer[i])
wake_up(i+wait_motor);
} else if (!moff_timer[i]) {
current_DOR &= ~mask;
outb(current_DOR,FD_DOR);
} else
moff_timer[i]--;
}
}
#define TIME_REQUESTS 64
static struct timer_list {
long jiffies;
void (*fn)();
struct timer_list * next;
} timer_list[TIME_REQUESTS] = { { 0, NULL, NULL }, };
static struct timer_list * next_timer = NULL;
void add_timer(long jiffies, void (*fn)(void))
{
struct timer_list * p;
if (!fn)
return;
cli();
if (jiffies <= 0)
(fn)();
else {
for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
if (!p->fn)
break;
if (p >= timer_list + TIME_REQUESTS)
panic("No more time requests free");
p->fn = fn;
p->jiffies = jiffies;
p->next = next_timer;
next_timer = p;
while (p->next && p->next->jiffies < p->jiffies) {
p->jiffies -= p->next->jiffies;
fn = p->fn;
p->fn = p->next->fn;
p->next->fn = fn;
jiffies = p->jiffies;
p->jiffies = p->next->jiffies;
p->next->jiffies = jiffies;
p = p->next;
}
}
sti();
}
#define FSHIFT 11
#define FSCALE (1<<FSHIFT)
/*
* Constants for averages over 1, 5, and 15 minutes
* when sampling at 5 second intervals.
*/
static unsigned long cexp[3] = {
1884, /* 0.9200444146293232 * FSCALE, exp(-1/12) */
2014, /* 0.9834714538216174 * FSCALE, exp(-1/60) */
2037, /* 0.9944598480048967 * FSCALE, exp(-1/180) */
};
unsigned long averunnable[3] = { 0, }; /* fixed point numbers */
void update_avg(void)
{
int i, n=0;
struct task_struct **p;
for(p = &LAST_TASK; p > &FIRST_TASK; --p)
if (*p && ((*p)->state == TASK_RUNNING ||
(*p)->state == TASK_UNINTERRUPTIBLE))
++n;
for (i = 0; i < 3; ++i)
averunnable[i] = (cexp[i] * averunnable[i] +
n * FSCALE * (FSCALE - cexp[i])) >> FSHIFT;
}
unsigned long timer_active = 0;
struct timer_struct timer_table[32];
void do_timer(long cpl)
{
unsigned long mask;
struct timer_struct *tp = timer_table+0;
struct task_struct ** task_p;
static int avg_cnt = 0;
for (mask = 1 ; mask ; tp++,mask += mask) {
if (mask > timer_active)
break;
if (!(mask & timer_active))
continue;
if (tp->expires > jiffies)
continue;
timer_active &= ~mask;
tp->fn();
sti();
}
/* Update ITIMER_REAL for every task */
for (task_p = &LAST_TASK; task_p >= &FIRST_TASK; task_p--)
if (*task_p && (*task_p)->it_real_value
&& !(--(*task_p)->it_real_value)) {
send_sig(SIGALRM,*task_p,1);
(*task_p)->it_real_value = (*task_p)->it_real_incr;
need_resched = 1;
}
/* Update ITIMER_PROF for the current task */
if (current->it_prof_value && !(--current->it_prof_value)) {
current->it_prof_value = current->it_prof_incr;
send_sig(SIGPROF,current,1);
}
/* Update ITIMER_VIRT for current task if not in a system call */
if (cpl && current->it_virt_value && !(--current->it_virt_value)) {
current->it_virt_value = current->it_virt_incr;
send_sig(SIGVTALRM,current,1);
}
if (cpl)
current->utime++;
else
current->stime++;
if (next_timer) {
next_timer->jiffies--;
while (next_timer && next_timer->jiffies <= 0) {
void (*fn)(void);
fn = next_timer->fn;
next_timer->fn = NULL;
next_timer = next_timer->next;
(fn)();
}
}
if (current_DOR & 0xf0)
do_floppy_timer();
if (--avg_cnt < 0) {
avg_cnt = 500;
update_avg();
}
if ((--current->counter)<=0) {
current->counter=0;
need_resched = 1;
}
}
int sys_alarm(long seconds)
{
extern int _setitimer(int, struct itimerval *, struct itimerval *);
struct itimerval new, old;
new.it_interval.tv_sec = new.it_interval.tv_usec = 0;
new.it_value.tv_sec = seconds;
new.it_value.tv_usec = 0;
_setitimer(ITIMER_REAL, &new, &old);
return(old.it_value.tv_sec + (old.it_value.tv_usec / 1000000));
}
int sys_getpid(void)
{
return current->pid;
}
int sys_getppid(void)
{
return current->p_pptr->pid;
}
int sys_getuid(void)
{
return current->uid;
}
int sys_geteuid(void)
{
return current->euid;
}
int sys_getgid(void)
{
return current->gid;
}
int sys_getegid(void)
{
return current->egid;
}
int sys_nice(long increment)
{
if (increment < 0 && !suser())
return -EPERM;
if (increment >= current->priority)
increment = current->priority-1;
current->priority -= increment;
return 0;
}
void sched_init(void)
{
int i;
struct desc_struct * p;
if (sizeof(struct sigaction) != 16)
panic("Struct sigaction MUST be 16 bytes");
set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));
set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));
p = gdt+2+FIRST_TSS_ENTRY;
for(i=1 ; i<NR_TASKS ; i++) {
task[i] = NULL;
p->a=p->b=0;
p++;
p->a=p->b=0;
p++;
}
/* Clear NT, so that we won't have troubles with that later on */
__asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
ltr(0);
lldt(0);
outb_p(0x36,0x43); /* binary, mode 3, LSB/MSB, ch 0 */
outb_p(LATCH & 0xff , 0x40); /* LSB */
outb(LATCH >> 8 , 0x40); /* MSB */
set_intr_gate(0x20,&timer_interrupt);
outb(inb_p(0x21)&~0x01,0x21);
set_system_gate(0x80,&system_call);
}