哈工大操作系统实验3进程运行轨迹的跟踪与统计

发表于 更新于 分类于 ， 阅读次数： 本文字数： 12k 阅读时长 ≈ 11 分钟

进程运行轨迹的跟踪与统计

实验内容

进程从创建（Linux 下调用 fork()）到结束的整个过程就是进程的生命期，进程在其生命期中的运行轨迹实际上就表现为进程状态的多次切换，如进程创建以后会成为就绪态；当该进程被调度以后会切换到运行态；在运行的过程中如果启动了一个文件读写操作，操作系统会将该进程切换到阻塞态（等待态）从而让出 CPU；当文件读写完毕以后，操作系统会在将其切换成就绪态，等待进程调度算法来调度该进程执行……

本次实验包括如下内容：

  • 基于模板 process.c 编写多进程的样本程序，实现如下功能： + 所有子进程都并行运行，每个子进程的实际运行时间一般不超过 30 秒； + 父进程向标准输出打印所有q子进程的 id，并在所有子进程都退出后才退出；
  • 在 Linux0.11 上实现进程运行轨迹的跟踪。 + 基本任务是在内核中维护一个日志文件 /var/process.log，把从操作系统启动到系统关机过程中所有进程的运行轨迹都记录在这一 log 文件中。
  • 在修改过的 0.11 上运行样本程序，通过分析 log 文件，统计该程序建立的所有进程的等待时间、完成时间（周转时间）和运行时间，然后计算平均等待时间，平均完成时间和吞吐量。可以自己编写统计程序，也可以使用 python 脚本程序—— stat_log.py（在 /home/teacher/ 目录下） ——进行统计。
  • 修改 0.11 进程调度的时间片，然后再运行同样的样本程序，统计同样的时间数据，和原有的情况对比，体会不同时间片带来的差异。

编写process.c 样本程序

process.c是样本程序的模板。它主要实现了一个函数：

1
2
3
4
5
6
7
8
9
/*
 * 此函数按照参数占用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时间，它可以调用：

1
cpuio_bound(10, 1, 0);  // 只要cpu_time>0，io_time=0，效果相同

以I/O为主要任务：

1
cpuio_bound(10, 0, 1);  // 只要cpu_time=0，io_time>0，效果相同

CPU和I/O各1秒钟轮回：

1
cpuio_bound(10, 1, 1);

较多的I/O，较少的CPU：

1
cpuio_bound(10, 1, 9);  // I/O时间是CPU时间的9倍

修改此模板，用fork()建立若干个同时运行的子进程，父进程等待所有子进程退出后才退出，每个子进程按照你的意愿做不同或相同的cpuio_bound()，从而完成一个个性化的样本程序。它可以用来检验有关log文件的修改是否正确，同时还是数据统计工作的基础。

wait()系统调用可以让父进程等待子进程的退出。

小技巧：

  1. 在Ubuntu下，top命令可以监视即时的进程状态。在top中，按u，再输入你的用户名，可以限定只显示以你的身份运行的进程，更方便观察。按h可得到帮助。
  2. 在Ubuntu下，ps命令可以显示当时各个进程的状态。“ps aux”会显示所有进程；“ps aux | grep xxxx”将只显示名为xxxx的进程。更详细的用法请问man。
  3. 在Linux 0.11下，按F1可以即时显示当前所有进程的状态。

process.c代码

struct tms 结构体

struct tms 结构体定义在 <sys/times.h> 头文件里，具体定义如下

1
2
3
4
5
6
7
8
9
/* Structure describing CPU time used by a process and its children.  */ 
struct tms 
  { 
    clock_t tms_utime ;          /* User CPU time.  用户程序 CPU 时间*/ 
    clock_t tms_stime ;          /* System CPU time. 系统调用所耗费的 CPU 时间 */ 

    clock_t tms_cutime ;         /* User CPU time of dead children. 已死掉子进程的 CPU 时间*/ 
    clock_t tms_cstime ;         /* System CPU time of dead children.  已死掉子进程所耗费的系统调用 CPU 时间*/ 
  };

数据类型 clock_t

关于该数据类型的定义如下：

1
2
3
#ifndef _CLOCK_T_DEFINED typedef long clock_t;
#define _CLOCK_T_DEFINED
#endif

在 time.h 文件中，还定义了一个常量 CLOCKS_PER_SEC ，它用来表示一秒钟会有多少个时钟计时单元，其定义如下：

1
#define CLOCKS_PER_SEC ((clock_t)1000)

下文就模拟cpu操作，定义 HZ=100，#define HZ 100内核的标准时间是jiffy,一个jiffy就是一个内部时钟周期,而内部时钟周期是由100HZ的频率所产生中的,也就是一个时钟滴答,间隔时间是10毫秒(ms).计算出来的时间也并非真实时间，而是时钟滴答次数，乘以10ms可以得到真正的时间: while ( ( (utime + stime) / HZ ) < cpu_time );

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <sys/times.h>

#include <stdlib.h>

#define HZ	100

void cpuio_bound(int last, int cpu_time, int io_time);

#define NR_PROC 5
int main(int argc, char * argv[])
{
	pid_t pid[NR_PROC];

    for(int i = 0; i < NR_PROC; i++) {
        pid_t cur_pid = fork();
        if(cur_pid == 0) { //子进程调用fork后，返回0
			cpuio_bound(2*(i+1), 0, 1);
			printf("the pid is %d, the father pid is %d.\n", getpid(), getppid());
			return 0; //退出子进程
        } else { //父进程返回的是子进程的pid
			pid[i] = cur_pid;
			printf("the %d child pid is %d\n", i, pid[i]);
		}
    }
	//循环创建子进程，然后在父进程利用wait()来等待子进程结束，然后父进程才退出。
    for(int i = 0; i < NR_PROC; i++){
		wait(&pid[i]);
	}
	
	printf("the parent is finished.\n");
	return 0;
}

/*
 * 此函数按照参数占用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
 * 所有时间的单位为秒
 */
void cpuio_bound(int last, int cpu_time, int io_time)
{
	struct tms start_time, current_time;
	clock_t utime, stime;
	int sleep_time;

	while (last > 0)
	{
		/* CPU Burst */
		times(&start_time);
		/* 其实只有t.tms_utime才是真正的CPU时间。但我们是在模拟一个
		 * 只在用户状态运行的CPU大户，就像“for(;;);”。所以把t.tms_stime
		 * 加上很合理。*/
		do
		{
			times(&current_time);
			utime = current_time.tms_utime - start_time.tms_utime;
			stime = current_time.tms_stime - start_time.tms_stime;
		} while ( ( (utime + stime) / HZ )  < cpu_time );
		last -= cpu_time;

		if (last <= 0 )
			break;

		/* IO Burst */
		/* 用sleep(1)模拟1秒钟的I/O操作 */
		sleep_time=0;
		while (sleep_time < io_time)
		{
			sleep(1);
			sleep_time++;
		}
		last -= sleep_time;
	}
}

写process.log文件

打开log文件

为了能尽早开始记录，应当在内核启动时就打开 log 文件

在 init()中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void init(void)
{
	int pid,i;
// ……
//加载文件系统
setup((void *) &drive_info);
// 打开/dev/tty0，建立文件描述符0和/dev/tty0的关联
(void) open("/dev/tty0",O_RDWR,0);
// 让文件描述符1也和/dev/tty0关联
(void) dup(0);
// 让文件描述符2也和/dev/tty0关联
(void) dup(0);
// ……
}

这段代码建立了文件描述符 0、1 和 2，它们分别就是 stdin、stdout 和 stderr。

可以把 log 文件的描述符关联到 3。文件系统初始化，描述符 0、1 和 2 关联之后，才能打开 log 文件，开始记录进程的运行轨迹。

为了能尽早访问log文件，我们要让上述工作在进程0中就完成。所以把这一段代码从init()移动到main()中，放在move_to_user_mode()之后（不能再靠前了），同时加上打开log文件的代码。修改后的main()如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
……
move_to_user_mode();

/***************添加开始***************/
setup((void *) &drive_info);
(void) open("/dev/tty0",O_RDWR,0);    //建立文件描述符0和/dev/tty0的关联
(void) dup(0);        //文件描述符1也和/dev/tty0关联
(void) dup(0);        //文件描述符2也和/dev/tty0关联
(void) open("/var/process.log",O_CREAT|O_TRUNC|O_WRONLY,0666);
/***************添加结束***************/

if (!fork()) {        /* we count on this going ok */
    init();
}
……

打开log文件的参数的含义是建立只写文件，如果文件已存在则清空已有内容。文件的权限是所有人可读可写。

这样，文件描述符0、1、2和3就在进程0中建立了。根据fork()的原理，进程1会继承这些文件描述符，所以init()中就不必再open()它们。此后所有新建的进程都是进程1的子孙，也会继承它们。但实际上，init()的后续代码和/bin/sh都会重新初始化它们。所以只有进程0和进程1的文件描述符肯定关联着log文件，这一点在接下来的写log中很重要。

写log文件

log文件将被用来记录进程的状态转移轨迹。所有的状态转移都是在内核进行的。在内核状态下，write()功能失效，其原理等同于《系统调用》实验中不能在内核状态调用printf()，只能调用printk()。编写可在内核调用的write()的难度较大，所以这里直接给出源码。它主要参考了printk()和sys_write()而写成的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <linux/sched.h>
#include <sys/stat.h>

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

    if (fd < 3)    /* 如果输出到stdout或stderr，直接调用sys_write即可 */
    {
        __asm__("push %%fs\n\t"
            "push %%ds\n\t"
            "pop %%fs\n\t"
            "pushl %0\n\t"
            "pushl $logbuf\n\t" /* 注意对于Windows环境来说，是_logbuf,下同 */
            "pushl %1\n\t"
            "call sys_write\n\t" /* 注意对于Windows环境来说，是_sys_write,下同 */
            "addl $8,%%esp\n\t"
            "popl %0\n\t"
            "pop %%fs"
            ::"r" (count),"r" (fd):"ax","cx","dx");
    }
    else    /* 假定>=3的描述符都与文件关联。事实上，还存在很多其它情况，这里并没有考虑。*/
    {
        if (!(file=task[0]->filp[fd]))    /* 从进程0的文件描述符表中得到文件句柄 */
            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;
}

因为和printk的功能近似，建议将此函数放入到kernel/printk.c中。fprintk()的使用方式类同与C标准库函数fprintf()，唯一的区别是第一个参数是文件描述符，而不是文件指针。例如：

1
2
fprintk(1, "The ID of running process is %ld", current->pid); //向stdout打印正在运行的进程的ID
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'R', jiffies); //向log文件输出

跟踪进程运行轨迹

jiffies，滴答

jiffies在kernel/sched.c文件中定义为一个全局变量：

1
long volatile jiffies=0;

它记录了从开机到当前时间的时钟中断发生次数。在kernel/sched.c文件中的sched_init()函数中，时钟中断处理函数被设置为：

1
set_intr_gate(0x20,&timer_interrupt);

而在kernel/system_call.s文件中将timer_interrupt定义为：

1
2
3
4
timer_interrupt:
    ……
    incl jiffies     #增加jiffies计数值
    ……

这说明jiffies表示从开机时到现在发生的时钟中断次数，这个数也被称为“滴答数”。

另外，在kernel/sched.c中的sched_init()中有下面的代码：

1
2
3
outb_p(0x36, 0x43); //设置8253模式
outb_p(LATCH&0xff, 0x40);
outb_p(LATCH>>8, 0x40);

这三条语句用来设置每次时钟中断的间隔，即为LATCH，而LATCH是定义在文件kernel/sched.c中的一个宏：

1
2
#define LATCH  (1193180/HZ)
#define HZ 100  //在include/linux/sched.h中

再加上PC机8253定时芯片的输入时钟频率为1.193180MHz，即1193180/每秒，LATCH=1193180/100，时钟每跳11931.8下产生一次时钟中断，即每1/100秒（10ms）产生一次时钟中断，所以jiffies实际上记录了从开机以来共经过了多少个10ms。

寻找状态切换点

必须找到所有发生进程状态切换的代码点，并在这些点添加适当的代码，来输出进程状态变化的情况到log文件中。此处要面对的情况比较复杂，需要对kernel下的fork.c、sched.c有通盘的了解，而exit.c也会涉及到。

第一个例子是看看如何记录一个进程生命期的开始，当然这个事件就是进程的创建函数fork()，由《系统调用》实验可知，fork()功能在内核中实现为sys_fork()，该“函数”在文件kernel/system_call.s中实现为：

1
2
3
4
5
6
7
8
9
10
sys_fork:
    call find_empty_process
    ……
    push %gs   //传递一些参数
    pushl %esi
    pushl %edi
    pushl %ebp
    pushl %eax
    call copy_process  //调用copy_process实现进程创建
    addl $20,%esp

修改fork.c

所以真正实现进程创建的函数是copy_process()，它在kernel/fork.c中定义为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int copy_process(int nr,……)
{
    struct task_struct *p;
    ……
    p = (struct task_struct *) get_free_page();  //获得一个task_struct结构体空间
    ……
    p->pid = last_pid;
    ……
    p->start_time = jiffies;    //设置start_time为jiffies
       ……
    p->state = TASK_RUNNING;    //设置进程状态为就绪。所有就绪进程的状态都是
                    //TASK_RUNNING(0），被全局变量current指向的
                    //是正在运行的进程。
    return last_pid;
}

因此要完成进程运行轨迹的记录就要在copy_process()中添加输出语句。这里要输出两种状态，分别是“N（新建）”和“J（就绪）”。

下面做出两处修改：

修改如下：

1
2
	p->start_time = jiffies;
fprintk(3,"%d\tN\t%d\n",p->pid,jiffies);  //新增进程创建
1
2
3
  //新增进程就绪
fprintk(3,"%d\tJ\t%d\n",p->pid,jiffies);
   return last_pid;

第二个例子是记录进入睡眠态的时间。sleep_on()和interruptible_sleep_on()让当前进程进入睡眠状态，这两个函数在kernel/sched.c文件中定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void sleep_on(struct task_struct **p)
{
    struct task_struct *tmp;
    ……
    tmp = *p;
    *p = current;  //仔细阅读，实际上是将current插入“等待队列”头部，tmp是原来的头部
    current->state = TASK_UNINTERRUPTIBLE; //切换到睡眠态
    schedule();  //让出CPU
    if (tmp)
        tmp->state=0;    //唤醒队列中的上一个（tmp）睡眠进程。0换作TASK_RUNNING更好
                //在记录进程被唤醒时一定要考虑到这种情况，实验者一定要注意!!!
}
/* 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();
    if (*p && *p != current) { //如果队列头进程和刚唤醒的进程current不是一个，说明从队列中间唤醒了一个进程，需要处理
        (**p).state=0;   //将队列头唤醒，并通过goto repeat让自己再去睡眠
        goto repeat;
    }
    *p=NULL;
    if (tmp)
        tmp->state=0;  //作用和sleep_on函数中的一样
}

相信实验者已经找到合适的地方插入记录进程从运行到睡眠的语句了。

总的来说，Linux 0.11支持四种进程状态的转移：就绪到运行、运行到就绪、运行到睡眠和睡眠到就绪，此外还有新建和退出两种情况。其中就绪与运行间的状态转移是通过schedule()（它亦是调度算法所在）完成的；运行到睡眠依靠的是 sleep_on() 和 interruptible_sleep_on() ，还有进程主动睡觉的系统调用 sys_pause() 和 sys_waitpid() ；睡眠到就绪的转移依靠的是wake_up()。所以只要在这些函数的适当位置插入适当的处理语句就能完成进程运行轨迹的全面跟踪了。如下所示：

修改sched.c文件

schedule：

1
2
3
(*p)->state==TASK_INTERRUPTIBLE)
	(*p)->state=TASK_RUNNING;
fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies);
1
2
3
4
5
6
7
8
//切换到相同的进程不输出
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);
	}

修改sys_pause函数

1
2
3
4
5
6
7
8
9
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;
}

修改sleep_on函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void sleep_on(struct task_struct **p)
{
    ...
	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函数同sleep_on

修改wake_up函数

1
2
3
4
5
6
7
8
9
10
11
void wake_up(struct task_struct **p)
{
	if (p && *p) {
		(**p).state=0;
		/*
		*修改--唤醒 最后进入等待序列的 进程
		*/
		fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies);
		*p=NULL;
	}
}

修改exit.c文件

当一个进程结束了运行或在半途中终止了运行，那么内核就需要释放该进程所占用的系统资源。这包括进程运行时打开的文件、申请的内存等。

当一个用户程序调用exit()系统调用时，就会执行内核函数do_exit()。该函数会首先释放进程代码段和数据段占用的内存页面，关闭进程打开着的所有文件，对进程使用的当前工作目录、根目录和运行程序的i节点进行同步操作。如果进程有子进程，则让init进程作为其所有子进程的父进程。如果进程是一个会话头进程并且有控制终端，则释放控制终端(如果按照实验的数据，此时就应该打印了)，并向属于该会话的所有进程发送挂断信号 SIGHUP，这通常会终止该会话中的所有进程。然后把进程状态置为僵死状态 TASK_ZOMBIE。并向其原父进程发送 SIGCHLD 信号，通知其某个子进程已经终止。最后 do_exit()调用调度函数去执行其他进程。由此可见在进程被终止时，它的任务数据结构仍然保留着。因为其父进程还需要使用其中的信息。

在子进程在执行期间，父进程通常使用wait()或 waitpid()函数等待其某个子进程终止。当等待的子进程被终止并处于僵死状态时，父进程就会把子进程运行所使用的时间累加到自己进程中。最终释放已终止子进程任务数据结构所占用的内存页面，并置空子进程在任务数组中占用的指针项。