理解 Linux Kernel (4) - 任务调度

/* 来自 Linux0.11 init/main.c */
void main(void)	
{
    ...

	sched_init();       /* schedule, 顾名思义就是时间安排咯 */
    
    ...
	sti();
	move_to_user_mode();
	if (!fork()) {	
		init();
	}
	for(;;) pause();
}

/* 这里给出的是 Linux0.11 kernel/sched.c 经过预编译的函数(里面有一些内联汇编) */
void sched_init(void)
{
    int i;
    struct desc_struct * p;    /* 声明一个描述符指针 */

    if (sizeof(struct sigaction) != 16)
        panic("Struct sigaction MUST be 16 bytes");
    __asm__ (                           /* 这段是为了设置全局描述符表GDT的第4项，是一个 0 号任务(当前任务)的任务调用门*/
            "movw $104,%1\n\t" 
            "movw %%ax,%2\n\t" 
            "rorl $16,%%eax\n\t" 
            "movb %%al,%3\n\t" 
            "movb $" "0x89" ",%4\n\t" 
            "movb $0x00,%5\n\t" 
            "movb %%ah,%6\n\t" 
            "rorl $16,%%eax" 
            ::"a" (&(init_task.task.tss)), "m" (*(((char *) (gdt+4)))), "m" (*(((char *) (gdt+4))+2)), "m" (*(((char *) (gdt+4))+4)), "m" (*(((char *) (gdt+4))+5)), "m" (*(((char *) (gdt+4))+6)), "m" (*(((char *) (gdt+4))+7)) 
            );
    __asm__ (                           /* 这里设置全局描述符表的第5项，0号任务的局部描述符表基址选择符 */
            "movw $104,%1\n\t" 
            "movw %%ax,%2\n\t" 
            "rorl $16,%%eax\n\t" 
            "movb %%al,%3\n\t" 
            "movb $" "0x82" ",%4\n\t" 
            "movb $0x00,%5\n\t" 
            "movb %%ah,%6\n\t" 
            "rorl $16,%%eax" 
            ::"a" (&(init_task.task.ldt)), "m" (*(((char *) (gdt+(4 +1))))), "m" (*(((char *) (gdt+(4 +1)))+2)), "m" (*(((char *) (gdt+(4 +1)))+4)), "m" (*(((char *) (gdt+(4 +1)))+5)), "m" (*(((char *) (gdt+(4 +1)))+6)), "m" (*(((char *) (gdt+(4 +1)))+7)) 
            );
    p = gdt+2+4;        /* 描述符指针指向 GDT 第6项。因为前面已经占用了第4，5项。由内核占用了 0，1，2，3。*/
    for(i=1;i<64;i++) {         /* 循环 63 次，这是 Linux0.11 最大支持 64 个任务同时存在。当前任务已经占了一个任务了*/
        task[i] = ((void *) 0); /* 63个任务指针全部值为 NULL */
        p->a=p->b=0;            /* GDT 累积 126 项(126 * 8 字节)全部置为 0 。每个任务占用 GDT 两项，一为任务门，一为局部描述符表选择符*/
        p++;
        p->a=p->b=0;
        p++;
    }

    __asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
    __asm__("ltr %%ax"::"a" (((((unsigned long) 0)<<4)+(4<<3))));           /* load Task Register TR 记录当前任务门为 gdt 第4项 */
    __asm__("lldt %%ax"::"a" (((((unsigned long) 0)<<4)+((4 +1)<<3))));     /* load Local Descriptor Table Register LDTR 记录当前选择符为 gdt 第5项 */
    /* 给8253芯片编程，每 10ms 发起一次时钟中断(下面3行的工作) */
    __asm__ ("outb %%al,%%dx\n" "\tjmp 1f\n" "1:\tjmp 1f\n" "1:"::"a" (0x36),"d" (0x43));   
    __asm__ ("outb %%al,%%dx\n" "\tjmp 1f\n" "1:\tjmp 1f\n" "1:"::"a" ((1193180/100) & 0xff),"d" (0x40));
    __asm__ ("outb %%al,%%dx"::"a" ((1193180/100) >> 8),"d" (0x40));
    __asm__ ("movw %%dx,%%ax\n\t" "movw %0,%%dx\n\t" "movl %%eax,%1\n\t" "movl %%edx,%2" : : "i" ((short) (0x8000+(0<<13)+(14<<8))), "o" (*((char *) (&idt[0x20]))), "o" (*(4+(char *) (&idt[0x20]))), "d" ((char *) (&timer_interrupt)),"a" (0x00080000)); /* 在 IDT 中设置时钟中断描述符项，第32项为时钟中断*/
    __asm__ ("outb %%al,%%dx"::"a" (({ unsigned char _v; __asm__ volatile ("inb %%dx,%%al\n" "\tjmp 1f\n" "1:\tjmp 1f\n" "1:":"=a" (_v):"d" (0x21)); _v; })&~0x01),"d" (0x21)); /*重新设置时钟中断的可屏蔽属性，这样就可在调用 hlt 后被时钟中断唤醒 */
    __asm__ ("movw %%dx,%%ax\n\t" "movw %0,%%dx\n\t" "movl %%eax,%1\n\t" "movl %%edx,%2" : : "i" ((short) (0x8000+(3<<13)+(15<<8))), "o" (*((char *) (&idt[0x80]))), "o" (*(4+(char *) (&idt[0x80]))), "d" ((char *) (&system_call)),"a" (0x00080000)); /* 在 IDT 中设置系统中断，第128项为时钟中断 */
}

void do_timer(long cpl)     /* 这个 cpl 是上一小节获取的原任务正在执行的指令的特权级 */
{
    extern int beepcount;       /* 扬声器发声计数 */
    extern void sysbeepstop(void);  /* 关闭扬声器的函数声明 */

    if (beepcount)              /* 这段逻辑作用很不清晰，可能是富有年代感的产物 */
        if (!--beepcount)
            sysbeepstop();

    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 = ((void *) 0);
            next_timer = next_timer->next;
            (fn)();
        }
    }
    if (current_DOR & 0xf0)
        do_floppy_timer();
    if ((--current->counter)>0) return;     /* 分配给当前任务的时间片 -1 。如果不为0，那么直接退出时钟中断，让任务继续执行 */
    current->counter=0;     /* 否则，当前任务的时间片记为 0 */
    if (!cpl) return;       /* 如果当前任务正处于内核态(比如用户程序中使用了一些系统调用)，那么先让这个任务继续执行，避免任务切换引起的麻烦 */
    schedule();             /* 任务调用，决定下一个时间片的主人 */
}

struct task_struct {
	long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	long counter;
	long priority;
	long signal;
	struct sigaction sigaction[32];
	long blocked;	/* bitmap of masked signals */
/* various fields */
	int exit_code;
	unsigned long start_code,end_code,end_data,brk,start_stack;
	long pid,father,pgrp,session,leader;
	unsigned short uid,euid,suid;
	unsigned short gid,egid,sgid;
	long alarm;
	long utime,stime,cutime,cstime,start_time;
	unsigned short used_math;
/* file system info */
	int tty;		/* -1 if no tty, so it must be signed */
	unsigned short umask;
	struct m_inode * pwd;
	struct m_inode * root;
	struct m_inode * executable;
	unsigned long close_on_exec;
	struct file * filp[NR_OPEN];
/* ldt for this task 0 - zero 1 - cs 2 - ds&ss */
	struct desc_struct ldt[3];
/* tss for this task */
	struct tss_struct tss;
};

/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * 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 */
/* 检测 alarm (任务定时报警信号)，并唤醒可中断的任务来完成预定义的工作, 好像自己用得少，还不太了解 alarm(xxx) 的细节
 * 从任务 63 号开始(总共 64 个任务, 0~63) ，倒着遍历所有任务，检测 alarm 
 */
	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p) {
			if ((*p)->alarm && (*p)->alarm < jiffies) {
					(*p)->signal |= (1<<(SIGALRM-1));
					(*p)->alarm = 0;
				}
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
			(*p)->state==TASK_INTERRUPTIBLE)
				(*p)->state=TASK_RUNNING;
		}

/* this is the scheduler proper: */

	while (1) {
		c = -1;
		next = 0;
		i = NR_TASKS;   /* 这里的宏 NR_TASKS = 64 */
		p = &task[NR_TASKS];
		while (--i) {
			if (!*--p)
				continue;
            /* 选择任务状态为 就绪态，且 counter 值最大的任务号作为下一个占用 CPU 的任务
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c) 
				c = (*p)->counter, next = i;
		}
        /* 如果没有其它任务，那么 next = 0 ，即接下来占用 cpu 的任务就是 0号任务(0号任务一定存在，不能被 kill ) */
		if (c) break;
        /* 如果 1~63 号任务(不存在或不在就绪态)至少存在一个任务，且时间片都为 0 ，那么重新计算分配给每个任务的 counter 值 */
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
				(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
	}
    /* 将当前任务切换为 next ，然后就可以一切就绪，退出时钟中断，就变成新的占用cpu的任务来执行了 */
	switch_to(next);
}

    # 这段与上面一段指令是直接承接的
	movl	12(%esp), %eax
	xorl	%gs:20, %eax
	je	.L40
	call	___stack_chk_fail
.L40:
	addl	$24, %esp           # 这里返还这次 call 额外申请的内核栈空间
	.cfi_def_cfa_offset 8
	popl	%ebx                # 恢复进入 call 的时候暂存的 ebx
	.cfi_restore 3
	.cfi_def_cfa_offset 4
	ret                         # return 跳转回到当初调用的地方
	.cfi_endproc

	call	_schedule           # 原先调用 schedule() 的地方
.L93:
    # return 跳转回来，直接承接的指令
	addl	$8, %esp
	.cfi_def_cfa_offset 8
	popl	%ebx
	.cfi_restore 3
	.cfi_def_cfa_offset 4
	ret                         # 继续 return ，跳出 do_timer() 
	.cfi_endproc

    call _do_timer		# 'do_timer(long CPL)' does everything from
	addl $4,%esp		# task switching to accounting ...
	jmp ret_from_sys_call

ret_from_sys_call:
    # 这 3 行来判断是不是任务0，如果是就不进行信号量的处理了
	movl _current,%eax		# task[0] cannot have signals
	cmpl _task,%eax
	je 3f
    # 判断在发生时钟中断前，CS 表示的是不是 LDT 第 1 项 (局部变量表的代码段)
    # 否则 CS 就应该内核态代码段了，不进行信号量处理
	cmpw $0x0f,CS(%esp)		# was old code segment supervisor ?
	jne 3f
    # 判断在发生时钟中断前，SS 表示的是不是 LDT 第 2 项 (局部变量表的数据段)
    # 否则认为程序还处在内核态，不进行信号量处理
	cmpw $0x17,OLDSS(%esp)		# was stack segment = 0x17 ?
	jne 3f
    # 设置信号量 (不清楚，先挖个坑)
	movl signal(%eax),%ebx
	movl blocked(%eax),%ecx
	notl %ecx
	andl %ebx,%ecx
	bsfl %ecx,%ecx
	je 3f
	btrl %ecx,%ebx
	movl %ebx,signal(%eax)
	incl %ecx
	pushl %ecx
	call _do_signal
	popl %eax
3:	popl %eax
	popl %ebx
	popl %ecx
	popl %edx
	pop %fs
	pop %es
	pop %ds
	iret

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();
}

  __                    __                  
 / _| __ _ _ __   __ _ / _| ___ _ __   __ _ 
| |_ / _` | '_ \ / _` | |_ / _ \ '_ \ / _` |
|  _| (_| | | | | (_| |  _|  __/ | | | (_| |
|_|  \__,_|_| |_|\__, |_|  \___|_| |_|\__, |
                 |___/                |___/