/*
* 2010-1-21
* 该文件时内核中有关任务调度的函数程序，其中包含基本函数sleep_on，
* wakeup，schedule等，以及一些简单的系统调用。同时将软盘的几个操作
* 函数也放置在这里。
*
* schedule函数首先对所有的任务检查，唤醒任何一个已经得到信号的任务，
* 具体的方法是针对任务数组中的每个任务，检查其警报定时值alarm。如果任务
* 的alarm已经超期（alarm < jiffies），则在它的信号位图中设置SIGALARM，然后
* 情书alarm值。jiffies是系统自从开机之后算起的滴答数。在scheed.h中定义，
* 如果进程信号的位图中除去被阻塞的信号之外还有其他信号，并且任务处于可
* 中断睡眠状态，则置任务为就绪状态。
* 随后是调度函数的核心处理，这部分代码根据进程时间片和优先权的调度机制，
* 来选择将要执行的程序。他首先是循环检查任务数组中的所有任务。根据每个就绪
* 任务剩余执行时间值counter中选取一个最大的，利用switch_to函数完成任务
* 转换。如果所有的就绪任务的该值都是0，则表示此刻所有任务的时间片都已运行完。
* 于是就根据任务的优先权值priority，重置每个任务的运行时间counter。在重新
* 循环检查所有的任务重的执行的时间片值。
* 另一个值得一说的是sleep_on函数，该函数虽短，却要比schedule函数难理解，
* 简单的讲，sleep_on函数主要的功能是当一个进程所请求的资源正在忙，或者是
* 不在内存中被切换出去，放在等待队列中等待一段时间。切换回来后在继续执行。
* 放入等待队列的方式是，利用了函数中的tmp指针为各个正在等待任务的联系。
* 还有一个函数interrupt_sleep_on，该函数的主要功能是在进程调度之前，把当前
* 任务设置为可中断等待状态，并在本任务被唤醒之后还需要查看队列上是否还有
* 后来的等待任务，如果有，先调度他们。
*
*/
/*
* 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/kernel.h>
#include <linux/sys.h>
#include <linux/fdreg.h> // 软驱头文件
#include <asm/system.h>
#include <asm/io.h>
#include <asm/segment.h> // 端操作头文件，定义端操作的汇编函数
#include <signal.h>
#define _S(nr) (1<<((nr)-1)) // 取nr（1-32）对应的位的二进制数值，取出的
// 并不是一位
// 定义除了SIGKILL和SIGSTOP之外，其他信号位全是阻塞的
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))
//----------------------------------------------------------------------
// show_task
// 显示任务号nr，pid，进程状态和内核堆栈空闲字节
void show_task(int nr,struct task_struct * p)
{
int i,j = 4096-sizeof(struct task_struct);
printk("%d: pid=%d, state=%d, ",nr,p->pid,p->state);
i=0;
while (i<j && !((char *)(p+1))[i])
i++;
printk("%d (of %d) chars free in kernel stack\n\r",i,j);
}
//---------------------------------------------------------------------
// show_stat
// 显示所有任务的信息
void show_stat(void)
{
int i;
for (i=0;i<NR_TASKS;i++)
if (task[i]) // task是一个指针数组，如果存在”任务“
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
{
// 定义任务联合(任务结构成员和stack 字符数组程序成员),联合体是共享内存的
struct task_struct task; // 因为一个任务数据结构与其堆栈放在同一内存页中，所以
char stack[PAGE_SIZE]; // 从堆栈段寄存器ss 可以获得其数据段选择符
};
static union task_union init_task = {INIT_TASK,}; // 定义初始任务数据
long volatile jiffies=0; // 定义开机以来时钟滴答数
long startup_time=0; // 开机时间
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 { // 该结果用于设置堆栈ss：esp
long * a;
short b;
} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
//---------------------------------------------------------------------
// math_state_restore
/*
* '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"); // 在发送协处理器指令之前首先发出wait指令
if (last_task_used_math) // 如果上个使用协处理器的进程存在
{
// 保存状态
__asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
}
last_task_used_math=current; // 现在last_task_used_math指向当前任务
if (current->used_math) // 如果当前的任务使用过协处理器
{
__asm__("frstor %0"::"m" (current->tss.i387));// 恢复状态
} else // 没有使用过协处理器
{
__asm__("fninit"::); // 初始化协处理器
current->used_math=1; // 设置使用协处理器标志
}
}
//--------------------------------------------------------------------
// schedule
/*
* '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
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) // 任务存在？
{
if ((*p)->alarm && (*p)->alarm < jiffies)
/*
* 下面是对(*p)->alarm < jiffies理解：
* 如果不调用alarm()函数，alarm的值就是0，但是调用了alarm函数
* 之后，比如说alarm(5),就是5秒后报警
*/
{
// 在位图信号中置位AIGALARM
(*p)->signal |= (1<<(SIGALRM-1));
// 将alarm值置位0
(*p)->alarm = 0;
}
// 如果信号位图中除被阻塞的信号外还有其他信号，即是该
// 进程申请的自愿被别的进程释放，或者是其他条件导致该
// 进程能够被执行，并且该任务处于的是可中断编程。linux
// 内核进程转换见文档<进程运行状态图.txt>。此时将该进程
// 进程状态置位就绪。
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
(*p)->state==TASK_INTERRUPTIBLE)
(*p)->state=TASK_RUNNING;
}
/* this is the scheduler proper: */
/* 这是调度的主要部分 */
while (1) // 循环，直到存在counter的值大于0
{
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
// 下面的代码是寻找最大counter值的进程。counter
// 值的含义见文档 <linux0.11task_struct中counter解释.txt>
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
if (c) break; // 如果进程存在。退出，去执行switch_to
// 否则更新counter值
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
}
switch_to(next);
}
//--------------------------------------------------------------------
// sys_pause
// 将当前任务设置为可中断，执行调度函数
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE;
schedule();
return 0;
}
//-------------------------------------------------------------------
// sleep_on
// struct task_struct **p是等待队列头指针
// 该函数就是首先将当前任务设置为TASK_UNINTERRUPTIBLE，并让睡眠队列
// 头指针指向当前任务，执行调度函数，直到有明确的唤醒时，该任务才重新
// 开始执行。
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p) // 无效指针
return;
if (current == &(init_task.task)) // 当前任务是0，死机
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
current->state = TASK_UNINTERRUPTIBLE; // 设置状态
schedule(); // 执行调度，直到明确的唤醒
// 肯能存在多个任务此时被唤醒，那么如果还存在等待任务
// if (tmp),则将状态设置为”就绪“
if (tmp)
tmp->state=0;
}
//--------------------------------------------------------------------------
// interruptible_sleep_on
// struct task_struct **p是等待队列对头
void interruptible_sleep_on(struct task_struct **p)
{
/*
* 首先需要明确的是TASK_INTERRUPTIBLE。它是指当进
* 程处于可中断等待状态时，系统不会调度该进行执行。
*/
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp=*p;
*p=current; // 保存该任务指针
repeat: current->state = TASK_INTERRUPTIBLE;
schedule();
if (*p && *p != current)
{
/*
* *p != current表示当前任务不是原来保存的任务，即是
* 有新的任务插入到等待队列中了。由于本任务是不可中断的
*，所以首先执行其他的任务
*/
(**p).state=0;
goto repeat;
}
/*
* 下面的代码错误，应该是*p = tmp，让队列头指针指向队列中其他任务
*/
*p=NULL;
// 原因同上。sleep_on
if (tmp)
tmp->state=0;
}
//----------------------------------------------------------------
// wake_up
// 唤醒任务p
void wake_up(struct task_struct **p)
{
if (p && *p)
{
(**p).state=0; // 置状态为可运行
*p=NULL;
}
}
/*
* 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.
*/
/*
* 由于软盘需要时钟，所以就将软盘的程序放到这里了
*/
// 利用下面的数组来存储的是马达运转或者是停止的滴答数，下列的
// 数组在函数do_floppy_timer中更新
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; // 数字输出寄存器（初值：允许dma和中断请求，启动fdc）
// oxoc -- 0000,1100
//----------------------------------------------------------------
// ticks_to_floppy_on
// 指定软盘到正常运转所需的滴答数
// nr -- 软盘驱动号，该函数返回的是滴答数
int ticks_to_floppy_on(unsigned int nr)
{
extern unsigned char selected; // 当前选中软盘号
// ox10 -- 0001, 0000
unsigned char mask = 0x10 << nr; // 所选软盘对应的数字输出
// 寄存器启动马达比特位
/*
* 数字输出端口（数字控制端口）是一个8位寄存器，它控制驱动器马达开启
* ，驱动器选择，启动和复位FDC，以及允许和禁止DMA及中断请求。
* FDC的主状态寄存器也是一个8位寄存器，用户反映软盘控制器FDC和软盘
* 驱动器FDD的基本状态。通常，在CPU想FDC发送命令之前或者是从FDC获得
* 操作结果之前，都要读取主状态寄存器的状态位，以判定当前的数据是否
* 准备就绪，以及确定数据的传输方向
*
*/
if (nr>3) // 最多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; // mask =
// 如果不是当前软驱，则首先复位其它软驱的选择位，然后置对应软驱选择位
if (!selected)
{
mask &= 0xFC; // 0xfc -- 1111,1100
mask |= nr;
}
if (mask != current_DOR) // 如果数字输出寄存器的当前值和要求不同
// 即是需要的状态还没有到达
{
outb(mask,FD_DOR); // 于是向FDC数字输出端口输出新值
if ((mask ^ current_DOR) & 0xf0) // 如果需要启动的马达还没有
// 启动，则置相应的软驱马达定
// 时器值（50个滴答数）
mon_timer[nr] = HZ/2;
else if (mon_timer[nr] < 2)
mon_timer[nr] = 2;
current_DOR = mask; // 更新数字输出寄存器的值current_DOR，即是反映
// 当前的状态
}
sti(); // 开中断
return mon_timer[nr];
}
//--------------------------------------------------------------
// floppy_on
// 等待指定软驱马达启动所需时间，启动时间
void floppy_on(unsigned int nr)
{
cli(); // 关中断
while (ticks_to_floppy_on(nr))// 还没有到时间？
sleep_on(nr+wait_motor); // 为不可中断睡眠状态并放在
// 等待马达运行队列中
sti(); // 开中断
}
//---------------------------------------------------------------
// floppy_off
// 初始化数组moff_timer，即是表示置相应软驱马达停转定时器（3秒）
void floppy_off(unsigned int nr)
{
moff_timer[nr]=3*HZ;
}
//----------------------------------------------------------------
// do_floppy_timer
// 软盘定时处理子程序。更新马达启动定时值和马达关闭停转计时值。该子程序
// 是在时钟定时中断被调用，因此每一个滴答（10ms）被嗲用一次，更新马达开启
// 或者是停止转动定时器值。如果在某一个马达停转时刻到达，那么则将数字输出
// 寄存器马达启动复位标志
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], * next_timer = NULL;
//----------------------------------------------------------------------
// add_timer
// 增加定时器。输入参数为指定的定时器的滴答数和相应的处理函数指针。
// jiffies -- 以10ms计时的滴答数
// *fn() -- 定时时间到达时执行函数
void add_timer(long jiffies, void (*fn)(void))
{
struct timer_list * p;
if (!fn) // 如果处理函数为空
return; // 退出
cli(); // 关中断
if (jiffies <= 0) // 定时器到达
(fn)(); // 执行函数fn
else { // 否则，从定时器数组中，找到一个空闲项，使用fn来标识
for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
if (!p->fn)
break;
// 当上面的循环结束时，可能存在p == timer_list + TIME_REQUESTS
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(); // 开中断
}
//------------------------------------------------------------------------
// do_timer
// 时钟中断处理函数，在/kernel/system_call.s中_timer_interrupt_中被调用
// 参数cpl是当前的特权级0或3，0标识在内核代码段运行
// 对于一个进程由于时间片用完，则进行内核任务切换。并进行及时更新工作
void do_timer(long cpl)
{
extern int beepcount; // 扬声器发声时间滴答数
extern void sysbeepstop(void); // 关闭扬声器
if (beepcount)
if (!--beepcount) // 如果扬声器计数次数到
sysbeepstop(); // 关闭发生器
if (cpl) // 如果实在内核程序，即是超级用户
current->utime++; // 超级用户时间增加
else
current->stime++; // 普通用户运行时间增加
// 如果有用户定时器存在的话，则将第一个定时器的值减去1，如果已经等于0
// 那么调用函数fn，并将函数指针置为空值，然后去掉该定时器。注意的是上述
// 链表已经排序，同时在寻找空闲结点时，是通过fn是否为空来判断的，所以
// 将fn置位null
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)();
}
}
// 如果当前软盘控制器FDC的数字输出寄存器马达启动位有置位，则执行相应的
// 软盘定时程序
if (current_DOR & 0xf0)
do_floppy_timer();
if ((--current->counter)>0) return; // 如果进程运行时间还没有完，退出
current->counter=0;
if (!cpl) return; // 超级用户程序，不依赖counter值来调度
schedule();
}
//----------------------------------------------------------------------
// sys_alarm
// 如果已经设置了alarm的值，那么返回的是旧值，如果没有设置返回0
int sys_alarm(long seconds)
{
int old = current->alarm;
if (old)
old = (old - jiffies) / HZ;
current->alarm = (seconds>0)?(jiffies+HZ*seconds):0;
return (old);
}
//-----------------------------------------------------------------------
// sys_getpid
// 取得当前的进程号
int sys_getpid(void)
{
return current->pid;
}
//----------------------------------------------------------------------
// sys_getppid
// 取得父进程进程号
int sys_getppid(void)
{
return current->father;
}
//-----------------------------------------------------------------------
// sys_getuid
// 取得用户号uid
int sys_getuid(void)
{
return current->uid;
}
//------------------------------------------------------------------------
// sys_geteuid
// 取得用户号euid
int sys_geteuid(void)
{
return current->euid;
}
//----------------------------------------------------------------------
// sys_getgid
// 取得组号gid
int sys_getgid(void)
{
return current->gid;
}
//----------------------------------------------------------------------
// sys_getegid
// 取得进程的egid，有关egid的解释，参见文档<Linux 关于SUID和SGID的解释.txt>
int sys_getegid(void)
{
return current->egid;
}
//--------------------------------------------------------------------
// sys_nice
// 改变进程优先级
int sys_nice(long increment)
{
if (current->priority-increment>0)
current->priority -= increment;
return 0;
}
//----------------------------------------------------------------------
// sched_init
// 调度程序初始化，即是初始化进程0，init
void sched_init(void)
{
int i;
struct desc_struct * p;
if (sizeof(struct sigaction) != 16) // sigaction中存放的是信号状态结构
panic("Struct sigaction MUST be 16 bytes");
// 设置初始任务（任务0）的任务状态描述符表和局部数据描述符表
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 */
/* nt标志置位的话，那么当前的中断任务执行iret命令时引起任务的切换 */
__asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
ltr(0); // 将任务0的tss加载到寄存器
lldt(0); // 将局部描述符表加载到局部描述符表寄存器
// 是将gdt和相应的ldt描述符的选择符加载到ldtr。只是明确的加载这一次
// 以后任务的ldt加载，是cpu根据tss中的ldt自动加载的
// 初始化8253定时器
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);
}
/*
* 下面解释linux的init进程的整体认识
* 1.在系统的启动阶段时，bootsect.s文件只是见将系统加载到内存中，内核都
* 没有加载完成，谈不上对于进程管理的影响。setup.s中加载了全局的gdtr，
* 但是此时的gdt只是为了让程序运行在保护模式下，没有什么作用。在setup.s
* 文件中设置的gdt的格式如下 ：
* -----------
* | 0 0 0 0 |
* -----------
* | code seg|
* ------------
* | data seg|
* -----------
* | ...... |
* 在head.s文件中还需要改写该gdt。经过该文件的修改后新生成的gdt如下：
* -----------
* | 0 0 0 0 |
* -----------
* | code |
* -----------
* | data |
* -----------
* | system | -- do not use in linux
* -----------
* | | -|
* ----------- |--剩下的各项是预留给其他任务，用于放置ldt和tss
* | | -|
*
* 在main.c文件中调用函数sched_init，此函数加载进程init。
* 加载init进程的ldt和tdd段
* |
* 由程序来执行加载ldt和tss段寄存器的任务
* |
* 即实现init进程的加载，即是手工创建的第一次进程。
* 此时的gdt大概上讲是：
* ----------
* | 0 0 0 0 |
* -----------
* | code |
* -----------
* | data |
* -----------
* | system |
* -----------
* | ldt0 |
* -----------
* | tss0 |
* -----------
* | ... |
* 此后，进程使用fork系统调用来产生新的进程，同时进程调度开始起作用。
*
*/
