准备工作
1.进程的状态有五种：新建（N），就绪或等待（J），睡眠或阻塞（W），运行（R），退出（E），其实还有个僵尸进程，这里先忽略
2.编写一个样本程序process.c,里面实现了一个函数
/*
* 此函数按照参数占用CPU和I/O时间
* last: 函数实际占用CPU和I/O的总时间，不含在就绪队列中的时间，>=0是必须的
* cpu_time: 一次连续占用CPU的时间，>=0是必须的
* io_time: 一次I/O消耗的时间，>=0是必须的
* 如果last > cpu_time + io_time，则往复多次占用CPU和I/O，直到总运行时间超过last为止
* 所有时间的单位为秒
*/
cpuio_bound(int last, int cpu_time, int io_time);
可以通过调用这个函数来创建自定义的进程，比如
// 比如一个进程如果要占用10秒的CPU时间，它可以调用：
cpuio_bound(, , );
// 只要cpu_time>0，io_time=0，效果相同
// 以I/O为主要任务：
cpuio_bound(, , );
// 只要cpu_time=0，io_time>0，效果相同
// CPU和I/O各1秒钟轮回：
cpuio_bound(, , );
// 较多的I/O，较少的CPU：
// I/O时间是CPU时间的9倍
cpuio_bound(, , );
为了获得Linux0.11里进程的状态切换，在Linux0.11里添加一个记录文件/var/provess.log
这个文件在内核启动时就被打开，所以我们要修改内核的入口函数init/main()
// ……
//加载文件系统
setup((void *) &drive_info); // 打开/dev/tty0，建立文件描述符0和/dev/tty0的关联
(void) open("/dev/tty0",O_RDWR,); // 让文件描述符1也和/dev/tty0关联
(void) dup(); // 让文件描述符2也和/dev/tty0关联
(void) dup(); // ……
这里启动了一些文件描述符(0=标准输入，1=标准输出，2=标准错误输出...)
可以把 log 文件的描述符关联到 3。文件系统初始化，描述符 0、1 和 2 关联之后，才能打开 log 文件，开始记录进程的运行轨迹。
为了能尽早访问 log 文件，我们要让上述工作在进程 0 中就完成。
所以把这一段代码从 init() 移动到 main() 中，放在 move_to_user_mode() 之后（不能再靠前了），同时加上打开 log 文件的代码。
//……
move_to_user_mode(); /***************添加开始***************/
setup((void *) &drive_info); // 建立文件描述符0和/dev/tty0的关联
(void) open("/dev/tty0",O_RDWR,); //文件描述符1也和/dev/tty0关联
(void) dup(); // 文件描述符2也和/dev/tty0关联
(void) dup();
//这是打开log的代码
(void) open("/var/process.log",O_CREAT|O_TRUNC|O_WRONLY,); /***************添加结束***************/ if (!fork()) { /* we count on this going ok */
init();
}
//……
3.写log文件
log 文件将被用来记录进程的状态转移轨迹。所有的状态转移都是在内核进行的。
在内核状态下，write() 功能失效，其原理等同于《系统调用》实验中不能在内核状态调用 printf()，只能调用 printk()。
所以修改kernel/printk.c，在里面新增一个函数fprintk()用来往log文件里写数据
#include "linux/sched.h"
#include "sys/stat.h" static char logbuf[];
int fprintk(int fd, const char *fmt, ...)
{
va_list args;
int count;
struct file * file;
struct m_inode * inode; va_start(args, fmt);
count=vsprintf(logbuf, fmt, args);
va_end(args);
/* 如果输出到stdout或stderr，直接调用sys_write即可 */
if (fd < )
{
__asm__("push %%fs\n\t"
"push %%ds\n\t"
"pop %%fs\n\t"
"pushl %0\n\t"
/* 注意对于Windows环境来说，是_logbuf,下同 */
"pushl $logbuf\n\t"
"pushl %1\n\t"
/* 注意对于Windows环境来说，是_sys_write,下同 */
"call sys_write\n\t"
"addl $8,%%esp\n\t"
"popl %0\n\t"
"pop %%fs"
::"r" (count),"r" (fd):"ax","cx","dx");
}
else
/* 假定>=3的描述符都与文件关联。事实上，还存在很多其它情况，这里并没有考虑。*/
{
/* 从进程0的文件描述符表中得到文件句柄 */
if (!(file=task[]->filp[fd]))
return ;
inode=file->f_inode; __asm__("push %%fs\n\t"
"push %%ds\n\t"
"pop %%fs\n\t"
"pushl %0\n\t"
"pushl $logbuf\n\t"
"pushl %1\n\t"
"pushl %2\n\t"
"call file_write\n\t"
"addl $12,%%esp\n\t"
"popl %0\n\t"
"pop %%fs"
::"r" (count),"r" (file),"r" (inode):"ax","cx","dx");
}
return count;
}
这个函数的使用方式
// 向stdout打印正在运行的进程的ID
fprintk(, "The ID of running process is %ld", current->pid); // 向log文件输出跟踪进程运行轨迹
fprintk(, "%ld\t%c\t%ld\n", current->pid, 'R', jiffies);
寻找切换点
然后需要找到进程状态进行切换的点，在那个位置进行信息输出来做到跟踪
那么进程状态的切换在以下几个文件内被实现
1.进程创建
这个事件就是进程的创建函数 fork()，由《系统调用》实验可知，fork() 功能在内核中实现为 sys_fork()，该“函数”在文件 kernel/system_call.s 中实现为：
sys_fork:
call find_empty_process
! ……
! 传递一些参数
push %gs
pushl %esi
pushl %edi
pushl %ebp
pushl %eax
! 调用 copy_process 实现进程创建
call copy_process
addl $,%esp
实际上是call copy_process函数
int copy_process(int nr,……)
{
struct task_struct *p;
// ……
// 获得一个 task_struct 结构体空间
p = (struct task_struct *) get_free_page();
// ……
p->pid = last_pid;
// ……
// 设置 start_time 为 jiffies
p->start_time = jiffies;
// ……
/* 设置进程状态为就绪。所有就绪进程的状态都是
TASK_RUNNING(0），被全局变量 current 指向的
是正在运行的进程。*/
p->state = TASK_RUNNING; fprintk(,"%ld\t%c\t%ld\n",p->pid,'N',jiffies);
fprintk(,"%ld\t%c\t%ld\n",p->pid,'J',jiffies); return last_pid;
}
2.运行->睡眠
sleep_on() 和 interruptible_sleep_on() 让当前进程进入睡眠状态，这两个函数在 kernel/sched.c 文件中定义如下：
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
// ……
tmp = *p;
// 仔细阅读，实际上是将 current 插入“等待队列”头部，tmp 是原来的头部
*p = current;
// 切换到睡眠态
current->state = TASK_UNINTERRUPTIBLE;
// 让出 CPU
schedule();
// 唤醒队列中的上一个（tmp）睡眠进程。0 换作 TASK_RUNNING 更好
// 在记录进程被唤醒时一定要考虑到这种情况，实验者一定要注意!!!
if (tmp)
tmp->state=;
}
/* TASK_UNINTERRUPTIBLE和TASK_INTERRUPTIBLE的区别在于不可中断的睡眠
* 只能由wake_up()显式唤醒，再由上面的 schedule()语句后的
*
* if (tmp) tmp->state=0;
*
* 依次唤醒，所以不可中断的睡眠进程一定是按严格从“队列”（一个依靠
* 放在进程内核栈中的指针变量tmp维护的队列）的首部进行唤醒。而对于可
* 中断的进程，除了用wake_up唤醒以外，也可以用信号（给进程发送一个信
* 号，实际上就是将进程PCB中维护的一个向量的某一位置位，进程需要在合
* 适的时候处理这一位。感兴趣的实验者可以阅读有关代码）来唤醒，如在
* schedule()中：
*
* for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
* if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
* (*p)->state==TASK_INTERRUPTIBLE)
* (*p)->state=TASK_RUNNING;//唤醒
*
* 就是当进程是可中断睡眠时，如果遇到一些信号就将其唤醒。这样的唤醒会
* 出现一个问题，那就是可能会唤醒等待队列中间的某个进程，此时这个链就
* 需要进行适当调整。interruptible_sleep_on和sleep_on函数的主要区别就
* 在这里。
*/
void interruptible_sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
…
tmp=*p;
*p=current;
repeat: current->state = TASK_INTERRUPTIBLE;
schedule();
// 如果队列头进程和刚唤醒的进程 current 不是一个，
// 说明从队列中间唤醒了一个进程，需要处理
if (*p && *p != current) {
// 将队列头唤醒，并通过 goto repeat 让自己再去睡眠
(**p).state=;
goto repeat;
}
*p=NULL;
//作用和 sleep_on 函数中的一样
if (tmp)
tmp->state=;
}
那么我们加上跟踪信息后就是
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp; if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
if(current->state != TASK_UNINTERRUPTIBLE){
fprintk(,"%ld\t%c\t%ld\n",(**p).pid,'W',jiffies);
}
current->state = TASK_UNINTERRUPTIBLE;
schedule();
if (tmp){
if(tmp->state!=){
fprintk(,"%ld\t%c\t%ld\n",tmp->pid,'J',jiffies);
}
tmp->state=;
}
}
void interruptible_sleep_on(struct task_struct **p)
{
struct task_struct *tmp; if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp=*p;
*p=current;
repeat:
if(current->state != TASK_INTERRUPTIBLE)
fprintk(,"%ld\t%c\t%ld\n",current->pid,'W',jiffies);
current->state = TASK_INTERRUPTIBLE;
schedule();
if (*p && *p != current) {
if((**p).state!=)
fprintk(,"%ld\t%c\t%ld\n",(**p).pid,'J',jiffies);
(**p).state=;
goto repeat;
}
*p=NULL;
if (tmp){
if(tmp->state!=){
fprintk(,"%ld\t%c\t%ld\n",tmp->pid,'J',jiffies);
}
tmp->state=;
}
}
int sys_pause(void)
{
if(current->state != TASK_INTERRUPTIBLE)
fprintk(,"%ld\t%c\t%ld\n",current->pid,'W',jiffies);
current->state = TASK_INTERRUPTIBLE;
schedule();
return ;
}
//waitpid函数
if (flag) {
if (options & WNOHANG)
return ;
if(current->state!=TASK_INTERRUPTIBLE)
fprintk(,"%ld\t%c\t%ld\n",current->pid,'W',jiffies);
current->state=TASK_INTERRUPTIBLE;
schedule();
if (!(current->signal &= ~(<<(SIGCHLD-))))
goto repeat;
else
return -EINTR;
}
3.就绪->运行：绝妙的调度函数！
void schedule(void)
{
int i,next,c;
struct task_struct ** p; /* check alarm, wake up any interruptible tasks that have got a signal */ for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) {
if ((*p)->alarm && (*p)->alarm < jiffies) {
(*p)->signal |= (<<(SIGALRM-));
(*p)->alarm = ;
}
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
(*p)->state==TASK_INTERRUPTIBLE){
fprintk(,"%ld\t%c\t%ld\n",(*p)->pid,'J',jiffies);
(*p)->state=TASK_RUNNING;
}
} /* this is the scheduler proper: */ while () {
c = -;
next = ;
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 >> ) +
(*p)->priority;
}
if(task[next]->pid!=current->pid){
if(current->state==TASK_RUNNING)
fprintk(,"%ld\t%c\t%ld\n",current->pid,'J',jiffies);//将当前状态设为就绪态后
fprintk(,"%ld\t%c\t%ld\n",task[next]->pid,'R',jiffies);//再将下一状态设为运行态
}
switch_to(next);
}
4.睡眠->就绪
void wake_up(struct task_struct **p)
{
if (p && *p) {
if((**p).state!=)
fprintk(,"%ld\t%c\t%ld\n",(**p).pid,'J',jiffies);
(**p).state=;
*p=NULL;
}
}
总的来说，Linux 0.11 支持四种进程状态的转移：
就绪到运行、运行到就绪、运行到睡眠和睡眠到就绪，此外还有新建和退出两种情况。
其中就绪与运行间的状态转移是通过 schedule()（它亦是调度算法所在）完成的；
运行到睡眠依靠的是 sleep_on() 和 interruptible_sleep_on()，还有进程主动睡觉的系统调用 sys_pause() 和 sys_waitpid()；
睡眠到就绪的转移依靠的是 wake_up()，还有用信号进行唤醒。
3.结果分析
N //进程1新建（init()）。此前是进程0建立和运行，但为什么没出现在log文件里？
J //新建后进入就绪队列
J //进程0从运行->就绪，让出CPU
R //进程1运行
N //进程1建立进程2。2会运行/etc/rc脚本，然后退出
J
W //进程1开始等待（等待进程2退出）
R //进程2运行
N //进程2建立进程3。3是/bin/sh建立的运行脚本的子进程
J
E //进程2不等进程3退出，就先走一步了
J //进程1此前在等待进程2退出，被阻塞。进程2退出后，重新进入就绪队列
R
N //进程1建立进程4，即shell
J
W //进程1等待shell退出（除非执行exit命令，否则shell不会退出）
R //进程3开始运行
W
R
N //进程5是shell建立的不知道做什么的进程
J
W
R
J
E //进程5很快退出
R
W //shell等待用户输入命令。
R //因为无事可做，所以进程0重出江湖
J //用户输入命令了，唤醒了shell
R
W
R
……
4.一些难点(重点分析)
1.运行态的父进程a建立子进程b，b经历完创建和就绪两态后，父进程就进入阻塞态(即进入了sleep_on函数)，然后cpu资源调度给子进程，在子进程释放资源或进入阻塞态前，父进程一直处于阻塞态
2.在sleep_on()函数中，当执行完调度函数返回时，说明这个进程已经处于就绪态了(处于睡眠态的进程不可能往下执行)
3.sleep_on()函数里有一条隐式等待队列，是通过递归压栈的方式实现的，tmp永远指向上一个被阻塞的进程，当sleep_on里的进程被唤醒后，就通过if(!tmp->statue)tmp->statue来让上一个被阻塞的进程进入就绪态
4.Linux0.11采用时间片轮转的进程调度算法，运行态的进程可能会因为时间片优先级低被其他就绪态的进程剥夺而进入就绪态，此时也要输出一下跟踪记录
5.运行和就绪态的进程公用一个宏标记TASK_RUNNING,进入睡眠态的进程分两种，一种是睡眠不可打断的，通过sleep_on进入的，被打上TASK_UNINTERRUPTIABLE,另一种可被信号唤醒，通过interruptible_sleep_on进入，被打上TASK_INTERUPTIBLE标记
6.可被信号唤醒的进程在调度算法中会被处理