Linux教程

哈工大 操作系统 lab3 进程运行轨迹的跟踪与统计解答

本文主要是介绍哈工大 操作系统 lab3 进程运行轨迹的跟踪与统计解答，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

实验内容

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

本次实验包括如下内容：

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

实验手册：参考

实验过程

编写样本程序

所谓样本程序，就是一个生成各种进程的程序。我们的对0.11的修改把系统对它们的调度情况都记录到log文件中。在修改调度算法或调度参数后再运行完全一样的样本程序，可以检验调度算法的优劣。理论上，此程序可以在任何Unix/Linux上运行，所以建议在Ubuntu上调试通过后，再拷贝到0.11下运行。

process.c编写：

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#include <sys/times.h>
#include <sys/wait.h>

#define HZ	100

const int sum_time = 30;

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

int main(int argc, char * argv[])
{
    int num = sum_time / 2;
    pid_t pid;
	int i = 0;
    for (i = 0; i <= num; i++) {
        pid = fork();
        if (pid == 0) {
            cpuio_bound(sum_time, i, sum_time - i);
            return 0;
        } else if (pid > 0){
            printf ("the %d-th child process id: %d\n", i, pid);
        } else {
            printf ("fork error!");
        }
    }
    do {
        wait(NULL);
    } while (num--);
	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;
	}
}

log文件

操作系统启动后先要打开/var/process.log，然后在每个进程发生状态切换的时候向log文件内写入一条记录，其过程和用户态的应用程序没什么两样。然而，因为内核状态的存在，使过程中的很多细节变得完全不一样。

打开log文件

为了能尽早开始记录，应当在内核启动时就打开log文件。内核的入口是init/main.c中的main()。fork时会继承文件句柄，因此可以在进程0直接打开日志文件，这样子进程都拥有打开日志文件的句柄了。

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

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

写log文件

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

#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;
}

使用：

//向stdout打印正在运行的进程的ID
fprintk(1, "The ID of running process is %ld", current->pid); 

//向log文件输出
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'R', jiffies);

跟踪进程运行轨迹

jiffies，滴答

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

long volatile jiffies=0;

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

set_intr_gate(0x20,&timer_interrupt);

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

timer_interrupt:
    ……
    incl jiffies     #增加jiffies计数值
    ……

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

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

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

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

#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。

寻找状态切换点

有5个状态，分别是创建（N)、运行（R)、就绪（J)、睡眠（W)、退出（E)。

在 fork.c、sche.c、exit.c文件中添加相应的print语句即可。

关注state 改变的时机即可。

fork.c：

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)
{
	p = (struct task_struct *) get_free_page();
    ...
	p->state = TASK_UNINTERRUPTIBLE;
    ...
	p->start_time = jiffies;
	fprintk (3, "%ld\t%c\t%ld\n", p->pid, 'N', jiffies);
	...
    
	p->state = TASK_RUNNING;	/* do this last, just in case */
	fprintk (3, "%ld\t%c\t%ld\n", p->pid, 'J', jiffies);
	return last_pid;
}

sche.c：

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 |= (1<<(SIGALRM-1));
					(*p)->alarm = 0;
				}
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
			(*p)->state==TASK_INTERRUPTIBLE) {
				(*p)->state=TASK_RUNNING;
				fprintk(3, "%d\t%c\t%d\n", (*p)->pid, 'J', jiffies);
			}
		}

    /* this is the scheduler proper: */
    ...
    // NEXT IS NEXT PROCESS WILL RUN!
	if (task[next]->pid != current->pid) {
		if (current->state == TASK_RUNNING) {
			fprintk(3, "%d\t%c\t%d\n", current->pid, 'J', jiffies);
		}	
		fprintk(3, "%d\t%c\t%d\n", task[next]->pid, 'R', jiffies);
	}
	switch_to(next);
}

int sys_pause(void)
{
	current->state = TASK_INTERRUPTIBLE;
	if (current->pid != 0) {	
		fprintk(3, "%d\t%c\t%d\n", current->pid, 'W', jiffies);
	}
	schedule();
	return 0;
}

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;
	current->state = TASK_UNINTERRUPTIBLE;
	fprintk(3, "%d\t%c\t%d\n", current->pid, 'W', jiffies);
	schedule();
	if (tmp) {
		tmp->state=0;
		fprintk(3, "%d\t%c\t%d\n", tmp->pid, 'J', jiffies);
	}
}

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:	current->state = TASK_INTERRUPTIBLE;
	fprintk(3, "%d\t%c\t%d\n", current->pid, 'W', jiffies);
	schedule();
	if (*p && *p != current) {
		(**p).state=0;
		fprintk(3, "%d\t%c\t%d\n", (**p).pid, 'J', jiffies);
		goto repeat;
	}
	*p=NULL;
	if (tmp) {
		tmp->state=0;
		fprintk(3, "%d\t%c\t%d\n", tmp->pid, 'J', jiffies);
	}
}

void wake_up(struct task_struct **p)
{
	if (p && *p) {
		(**p).state=0;
		fprintk(3, "%d\t%c\t%d\n", (**p).pid, 'J', jiffies);
		*p=NULL;
	}
}

exit.c:

int do_exit(long code)
{
	int i;
	free_page_tables(get_base(current->ldt[1]),get_limit(0x0f));
	free_page_tables(get_base(current->ldt[2]),get_limit(0x17));
    ...
	current->state = TASK_ZOMBIE;
	fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'E', jiffies);
	schedule();
	return (-1);	/* just to suppress warnings */
}

int sys_waitpid(pid_t pid,unsigned long * stat_addr, int options)
{
    ...
	if (flag) {
		if (options & WNOHANG)
			return 0;
		current->state=TASK_INTERRUPTIBLE;
		fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies);
		schedule();
		if (!(current->signal &= ~(1<<(SIGCHLD-1))))
			goto repeat;
		else
			return -EINTR;
	}
	return -ECHILD;
}

修改时间片

对于时间片counter,由于时间片的初始化操作为：p->counter = p->priority
只与优先级priority有关，所以只需要修改priority即可在定义priority宏中修改即可

#define INIT_TASK \
    { 0,15,15,
// 上述三个值分别对应 state、counter 和 priority;

实验结果

把process.c放在linux0.11上编译运行，如下：

24c77f9cc5102dfce165ddea43dbb8c

a7391001b64bbcdc5b00dc6f428bba2

然后是获得log，把log从linux0.11中移出来即可。

image-20211219165814070

使用默认的分析程序对时间片为10、15、20的情况进行分析：

process-10.log:

Process   Turnaround   Waiting   CPU Burst   I/O Burst
      7         3383        88           0        3295
      8         4772      1481         100        3190
      9         6051      2770         200        3080
     10         7230      3960         300        2970
     11         8309      5049         400        2860
     12         9288      6038         500        2750
     13        10168      6927         600        2640
     14        10947      7716         700        2530
     15        11626      8406         800        2420
     16        12088      8905         900        2283
     17        12532      9394        1000        2137
     18        12875      9783        1100        1991
     19        13136     10072        1200        1863
     20        13297     10262        1300        1735
     21        13367     10351        1400        1616
     22        13356     10340        1500        1515
Average:    10151.56   6971.38

process-15.log:

Process   Turnaround   Waiting   CPU Burst   I/O Burst
      7         3403       238           0        3165
      8         4632      1481         100        3050
      9         5991      2841         200        2950
     10         7240      4090         300        2850
     11         8199      5064         400        2735
     12         9244      6108         500        2635
     13        10178      7042         600        2535
     14        10877      7747         700        2430
     15        11601      8476         800        2325
     16        12214      9095         900        2218
     17        12617      9529        1000        2087
     18        13014      9943        1100        1970
     19        13301     10248        1200        1853
     20        13442     10412        1300        1730
     21        13528     10511        1400        1616
     22        13516     10500        1500        1515
Average:    10187.31   7082.81
Throughout: 0.12/s

process-20.log:

Process   Turnaround   Waiting   CPU Burst   I/O Burst
      7         3913       313           0        3600
      8         5272      1691         100        3480
      9         6531      2970         200        3360
     10         7690      4150         300        3240
     11         8749      5229         400        3120
     12         9709      6208         500        3000
     13        10568      7087         600        2880
     14        11327      7867         700        2760
     15        11967      8546         800        2621
     16        12451      9125         900        2426
     17        12815      9604        1000        2210
     18        13117      9983        1100        2033
     19        13358     10264        1200        1894
     20        13498     10443        1300        1755
     21        13538     10522        1400        1616
     22        13517     10501        1500        1515
Average:    10501.25   7156.44
Throughout: 0.12/s

可以发现，时间片为10的时候平均周转时间和平均等待时间竟然是最短的！

linux还说这是个很好的调度函数呢。。（看来也不是太好。。。

但是，对时间片为10的情况仔细分析，可以发现：父进程没有一次性创建16子进程，另外的是时间片中断后创建的。

image-20211219170905633

image-20211219170923959

后续的进程新建的时间晚很多，这就拉低了平均数！！

时间片为15时，是一次性fork出的：

image-20211219171148971

时间片为20时也是一样：

image-20211219171220505

相较于20的时间片，15明显更优；若是考虑上时间片为10得拉到平均值效果，15的时间片其实也是更优的选择。

所以呢，时间片为15还是最佳的方案（创建少点进程，效果会更明显），linux老爷子还是做过相关实验的。。。

遇到的问题

如果有自己搭建环境做实验，然后linux崩了的（kernel panic ），可以尝试使用实验楼的环境，可能自己的环境是有问题的。

reference

[1] 实验指导书

这篇关于哈工大 操作系统 lab3 进程运行轨迹的跟踪与统计解答的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航