李治军操作系统实验3——进程的运行轨迹的跟踪和统计教程
操作系统实验3——进程的运行轨迹的跟踪和统计
代码仓库
========================================================================
实验内容
记录所有进程的轨迹，并输出到 /var/process.log 。
//行为：新建(N)、进入就绪态(J)、进入运行态(R)、进入阻塞态(W)和退出(E)
//时间：系统的滴答时间(tick)
//pid | 行为 | 时间
12 N 1056
12 J 1057
4 W 1057
12 R 1057
13 N 1058
13 J 1059
14 N 1059
14 J 1060
15 N 1060
……
实验步骤
1.添加一个能够在内核中写入文件操作的函数，使在内核状态下也能对 /var/process.log 进行写操作。我们可以在kernel/printk.c中添加如下代码。
//kernel/printk.c:16
#include <linux/sched.h>
#include <sys/stat.h>
//kernel/printk.c:45
static char logbuf[1024];
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 < 3)
{
__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[0]->filp[fd]))
return 0;
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;
}
- -
2.修改/init/main.c，使 /var/process.log 能够记录下所有的轨迹。
原本加载文件系统和关联文件描述符在172行，也就是在fork完（进程0->进程1）调用的init()里。这样的话，process.log就记录不了进程0->进程1这一过程。
//init/main.c:138
if (!fork()) { /* we count on this going ok */
init();
//init/main.c:172 void init(void)
setup((void *) &drive_info); //加载文件系统
(void) open("/dev/tty0",O_RDWR,0); //打开/dev/tty0，建立文件描述符0和/dev/tty0的关联
(void) dup(0); //让文件描述符1也和/dev/tty0关联
(void) dup(0); //让文件描述符2也和/dev/tty0关联
所以我们可以把他们放到fork()之前。并添加以只写方式打开 /var/process.log 的语句，这样文件描述符3就关联到了 /var/process.log ，我们要写入 /var/process.log 也只需调用我们写好的fprintk(3,fmt,...)。
open()函数原型:static inline long open(const char * name, int mode, int flags)。
//init/main.c:138
setup((void *) &drive_info);
(void) open("/dev/tty0",O_RDWR,0);
(void) dup(0);
(void) dup(0);
(void) open("/var/process.log",O_CREAT|O_TRUNC|O_WRONLY,0666);
- -
3.记录进程轨迹。
很显然我们需要在有发生进程 新建(N) 、 进入就绪态(J) 、 进入运行态(R) 、进入阻塞态(W) 和 退出(E) 的地方调用我们写好的fprintk()函数，把进程的轨迹记录在 /var/process.log 。那么这些地方怎么去找到呢，有一个技巧就是，搜索一下 state 关键词，因为除了就绪态<->运行态的切换（state都是TASK\_RUNNING），其他所有行为都需要改变进程PCB里的进程状态（ state ）。
>>>kernel/fork.c<<<
3.1我们先来看一下kernel/fork.c。我们知道Linux系统创建新进程都是由进程0使用fork()系统调用创建而来的，我们在include/unistd.h中找到fork()系统调用功能号为2。
//include/unistd.h：61
#define __NR_exit 1
#define __NR_fork 2
#define __NR_read 3
并在include/linux/sys.h中找到fork()功能在内核中实际上由sys\_fork()函数来实现。
//include/linux/sys.h：74
fn_ptr sys_call_table[] = { sys_setup, sys_exit, sys_fork, ......
然后我们继续在kernel/system\_call.s中找到sys\_fork()函数。
#kernel/system_call.s:207
.align 2
sys_fork:
call find_empty_process
testl %eax,%eax
js 1f
push %gs
pushl %esi
pushl %edi
pushl %ebp
pushl %eax
call copy_process
addl $20,%esp
1: ret
我们发现了sys\_fork()函数先调用了find\_empty\_process()，而后压了很多值(函数参数)入栈再调用copy\_process()函数，这两个函数都在kernel/fork.c中实现。
int find\_empty\_process(void)的作用是返回一个不重复的新的进程号（pid）给新建的进程。
int copy\_process(int nr,long ebp,long edi,long esi,long gs,long none,long ebx,long ecx,long edx,long fs,long es,long ds,long eip,long cs,long eflags,long esp,long ss)主要完成的是进程的复制，以及新进程的初始化设置。
我们在kernel/fork.c中搜索 state 就可以在83行找到新建的进程状态被初始化成TASK\_UNINTERRUPTIBLE。新建的任务结构指针(PCB指针)p被放入任务数组nr[]中后，赶紧把状态设为TASK\_UNINTERRUPTIBLE，避免新进程还没新建完成就被切到。
//kernel/fork.c:78 copy_process()
p = (struct task_struct *) get_free_page();
if (!p)
return -EAGAIN;
task[nr] = p;
*p = *current; /* NOTE! this doesn't copy the supervisor stack */
p->state = TASK_UNINTERRUPTIBLE;
我们可以在kernel/fork.c的93行copy\_process()函数里添加一条调用fprintk()的语句，把进程的新建记录下来。
//kernel/fork.c:92 copy_process()
p->start_time = jiffies;
fprintk(3,"%d\tN\t%d\n",p->pid,jiffies);
p->tss.back_link = 0;
我们搜索下一个 state ，可以在kernel/fork.c的133找到状态被设为TASK\_RUNNING。新进程完成了新建，就可以把状态改为就绪态了。我们在这添加fprintk()，把新进程变成就绪态记录下来。
//kernel/fork.c:133 copy_process()
p->state = TASK_RUNNING; /* do this last, just in case */
fprintk(3,"%d\tJ\t%d\n",p->pid,jiffies);
>>>kernel/sched.c<<<
3.2接着我们来看比较复杂的一个文件kernel/sched.c，sched.c里主要是与进程调度管理有关的函数。
我们在kernel/sched.c中搜索 state ，并且有发生state改变的，第一个在120行schedule()函数里。schedule()函数主要是负责选择下一个要运行的进程。它首先使用一个for循环，从任务（进程）数组最后一个往前检查其报警定时值alarm。如果alarm < jiffier（定时值过期），则在它的信号位图中设置SIGALRM信号（闹钟信号），并清alarm值。如果进程的信号位图中除去被阻塞的信号外还有其他信号，并且任务（进程）处于可中断睡眠（TASK\_INTERRUPTIBLE），则把任务（进程）的状态state改为就绪态（TASK\_RUNNING）。需要这样做的原因是避免进程陷入无限期的等待。
信号是软件中断。很多比较重要的应用程序都需处理信号。信号提供了一种处理异步事件的方法，例如，终端用户键入中断键，会通过信号机制停止一个程序，或及早终止管道中下一个程序。
//kernel/sched.c:111 schedule()
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;
}
这里我们就可以添加fprintk()，记录下进程由可中断睡眠->就绪态的过程。
//kernel/sched.c:117 schedule()
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
(*p)->state==TASK_INTERRUPTIBLE)
{
(*p)->state=TASK_RUNNING;
fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies);
}
我们继续搜索包含 state ，并且有发生state改变的语句。在149行sys\_pause()函数里发现了它。sys\_pause()函数，看函数名，我们就可以大胆猜它是系统调用函数，事实也是如此。pause()系统调用主要作用就是改变当前进程的状态state为可中断等待(TASK\_INTERRUPTIBLE)，并调用schedule()执行进程调度。
//kernel/sched.c:147
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE;
schedule();
return 0;
}
所以我们也需要在这里添加fprintk()，记录下进程状态state变成可中断等待(TASK\_INTERRUPTIBLE)的过程。由于系统无事可做的时候，进程0会不停地调用sys\_pause()，以激活调度算法。所以我们可以这样写：
//kernel/sched.c:147
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE;
if(current->pid != 0)
fprintk(3,"%d\tW\t%d\n",current->pid,jiffies);
schedule();
return 0;
}
继续搜索，我们在166行和169行sleep\_on()函数里各发现一个有发生状态改变的语句。sleep\_on()函数主要是把当前进程的状态置为不可中断等待(TASK\_UNINTERRUPTIBLE)，并让等待队列的头指针指向它。
//kernel/sched.c:165 sleep_on()
*p = current;
current->state = TASK_UNINTERRUPTIBLE;
schedule();
if (tmp)
tmp->state=0;
我们在相应位置添加fprintk()。
//kernel/sched.c:166 sleep_on()
current->state = TASK_UNINTERRUPTIBLE;
fprintk(3,"%d\tW\t%d\n",current->pid,jiffies);
schedule();
if (tmp)
{
tmp->state=0;
fprintk(3,"%d\tJ\t%d\n",tmp->pid,jiffies);
}
继续搜索，在interruptible\_sleep\_on()函数里的186行，189行和194行发现目标。interruptible\_sleep\_on()函数与sleep\_on()类似，区别是当前进程会被置为可中断的等待状态（TASK\_INTERRUPTIBLE）。
//kernel/sched.c:186 interruptible_sleep_on()
repeat: current->state = TASK_INTERRUPTIBLE;
schedule();
if (*p && *p != current) {
(**p).state=0;
goto repeat;
}
*p=NULL;
if (tmp)
tmp->state=0;
在相应位置添加fprintk()。
//kernel/sched.c:186 interruptible_sleep_on()
repeat: current->state = TASK_INTERRUPTIBLE;
fprintk(3,"%d\tW\t%d\n",current->pid,jiffies);
schedule();
if (*p && *p != current) {
(**p).state=0;
fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies);
goto repeat;
}
*p=NULL;
if (tmp)
{
tmp->state=0;
fprintk(3,"%d\tJ\t%d\n",tmp->pid,jiffies);
}
继续搜索，在205行wake\_up()函数里发现目标。
//kernel/sched.c:204 wake_up()
if (p && *p) {
(**p).state=0;
*p=NULL;
}
在相应位置添加fprintk()。
//kernel/sched.c:204 wake_up()
if (p && *p) {
(**p).state=0;
fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies);
*p=NULL;
}
值得注意的是，我们之前提到，就绪态(J)和运行态(R)的state都是TASK\_RUNNING。所以我们如果要记录下就绪态(J)<->运行态(R)的过程，通过搜索 state 是行不通的。幸运的是这种切换只发生在schedule()里的switch\_to(next)。在调用switch\_to(next)之前，会先根据进程的时间片和优先权调度机制来选择随后要执行的进程task[next]。接下来我们来看switch\_to()发生了什么，switch\_to()被定义在include/linux/sched.h。
//include/linux/sched.h:173
#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__("cmpl %%ecx,current\n\t" \
"je 1f\n\t" \
"movw %%dx,%1\n\t" \
"xchgl %%ecx,current\n\t" \
"ljmp *%0\n\t" \
"cmpl %%ecx,last_task_used_math\n\t" \
"jne 1f\n\t" \
"clts\n" \
"1:" \
::"m" (*&__tmp.a),"m" (*&__tmp.b), \
"d" (_TSS(n)),"c" ((long) task[n])); \
}
switch\_to()首先会判断要切换到的进程是否就是当前进程，是的话就什么都不做了。所以我们可以在switch\_to()前这样写，确保process.log记录正确：
//kernel/sched.c:144 schedule()
if(current->pid != task[next] ->pid)
{
if(current->state == TASK_RUNNING)
fprintk(3,"%d\tJ\t%d\n",current->pid,jiffies);
fprintk(3,"%d\tR\t%d\n",task[next]->pid,jiffies);
}
switch_to(next);
>>>kernel/exit.c<<<
3.3我们接着来看一个与进程终止和推出有关的文件kernel/exit.c，我们一样搜索 state 关键词，并且找到state有发生改变的地方。在129行do\_exit()函数里发现了目标。程序退出处理函数do\_exit()是在exit系统调用的中断处理程序中被调用。它首先会释放当前进程的代码段和数据段所占内存页面。如果当前进程还有子进程，就将子进程的father置为1（init进程）。若子进程是僵死状态（TASK\_ZOMBIE），则向进程1发送子进程终止信号（SIGCHLD）。接着关闭当前进程打开的所有文件，释放使用的终端设备和协处理器设备。随后把当前进程置为僵死状态，并向父进程发送子进程终止信号SIGCHLD。最后让内核重新调度进程。
//kernel/exit.c:129 do_exit()
current->state = TASK_ZOMBIE;
current->exit_code = code;
在相应位置添加fprintk()。
//kernel/exit.c:129 do_exit()
current->state = TASK_ZOMBIE;
fprintk(3,"%d\tE\t%d\n",current->pid,jiffies);
current->exit_code = code;
继续搜索，在187行sys\_waitpid()函数里发现目标。系统调用waitpid()用于挂起当前进程，直到pid指定的子进程退出（终止），或者收到终止信号，或者需要调用一个信号句柄。
//kernel/exit.c:187 sys_waitpid()
current->state=TASK_INTERRUPTIBLE;
schedule();
在相应位置添加fprintk()。
//kernel/exit.c:187 sys_waitpid()
current->state=TASK_INTERRUPTIBLE;
fprintk(3,"%d\tW\t%d\n",current->pid,jiffies);
schedule();
3.4把process.c放到linux-0.11主目录下（/usr/root/）（可以使用挂载bochs虚拟机硬盘的方法）。编译修改后的linux-0.11，并运行。启动修改后的linux-0.11，使用gcc编译process.c并运行。执行sync确保所有缓存数据都存盘，关闭bochs虚拟机。再次挂载bochs虚拟机硬盘，把/var/process.log拷出来，并使用start\_log.py进行分析统计。
Usage: process.log [PID1] [PID2] ... [-x PID1 [PID2] ... ] [-m] [-g]
我们可以使用./stat\_log.py process.log -g 查看分析统计所有进程。
(Unit: tick)
Process Turnaround Waiting CPU Burst I/O Burst
0 10362 67 8 0
1 26 0 26 0
2 25 4 21 0
3 3004 0 4 2999
4 13600 86 2577 10937
5 3 0 2 0
6 270 0 269 0
7 53 0 52 0
8 100 0 99 0
9 27 0 26 0
......
- -
4.进程调度
我们前面做到schedule()里的switch(next)，说到switch(next)之前是先根据进程的时间片和优先权调度机制来选择随后要执行的进程task[next]。我们现在就来看这个随后要执行的进程task[next]是怎么被选出来的。
//kernel/sched.c:127 schedule()
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;
}
我们可以看到第2个while循环从任务数组的尾部开始往前查找状态state为就绪态（TASK\_RUNNING ）的任务（进程）中 counter 最大的做为下一个要执行的进程。counter为进程运行时间递减滴答计数，也就是counter大的进程运行时间就小。在创建新的进程时counter会被priority赋值，我们可以在kernel/fork.c中看到：
//kernel/fork.c:86 copy_process()
p->counter = p->priority;
那priority又等于什么呢？可以在sched.h中看到进程0的priority的值为15，而所有进程都由进程0fork而来，所以也都是15（没使用nice()系统调用）
//include/linux/sched.h:115
#define INIT_TASK \
/* state etc */ { 0,15,15, \
.....
如果这个进程（task[next]）的counter等于0，那就需要给所有任务（进程）重新计算一下counter：counter=counter/2+priority。然后重新找出counter值最大的进程，做为下一个要运行的进程。若此时找出的进程的counter值不等于0或等于-1（没有可运行的进程），那么就可以直接跳出循环去执行switch\_to(next)，切去下一个进程。