OS操作系统实验：xv6调度(RR, 优先级调度, 优先级队列） 实现和分析 Part 2- xv6 RR调度情况统计

Posted on | Post modified | In | | Visitors

上一篇： Part 1-xv6 调度代码讲解

TODO2： 统计RR调度情况

实现waitSch系统调用

todo2需要增加一个系统调用waitSch(int* rutime, int* retime, int* sltime)作为原来wait的扩展，除了执行原有功能以外，要将进程的运行时间、在等待队列中的时间和休眠时间输入到三个参数所代表的地址中。

首先我们将需要维护的数据结构定义在proc.h中：

1
2
3
4
5
6
7
8
9
10
11
struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // Bottom of kernel stack for this process
  ...
  
  uint ctime;                   // 创建时间
  uint rutime;                  // 处于RUNNING下的时间
  uint retime;                  // 处于ready状态下的时间
  uint sltime;                  // 处于Sleeping状态下的时间
};

然后，在proc.c中，也应该做出相关的修改。首先在进程被初始化的时候，应该将p->ctime设置为当时的时钟ticks，然后其他的几个变量应该初始化为0。考虑到第一个用户进程并不是由fork产生，我们将初始化放在allocproc中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
found:
  p->state = EMBRYO;
  p->pid = nextpid++;

														//modified here
  p->ctime = ticks;   //创建时间
  p->rutime = 0;      
  p->sltime = 0;
  p->retime = 0;

  release(&ptable.lock);

  // Allocate kernel stack.
  if((p->kstack = kalloc()) == 0){
    p->state = UNUSED;
    p->ctime = 0;     //分配错误的时候，要恢复为0.
    return 0;
  }

相应地，当进程结束，资源要被回收时，应该将这几个变量清空。我们不修改在exit中，因为此时这些进程运行的统计数据仍然要保留，直到父进程调用wait找到它，将它回收的时候，再把这些数据处理完清空。在wait中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 if(p->state == ZOMBIE){
        // Found one.
        pid = p->pid;
        kfree(p->kstack);
        p->kstack = 0;
        freevm(p->pgdir);
        p->pid = 0;
        p->parent = 0;
        p->name[0] = 0;
        p->killed = 0;
        												// modified
        p->ctime=0;
	    p->rutime=0;
	    p->retime=0;
	    p->sltime=0;
        												// end
        p->state = UNUSED;
        release(&ptable.lock);
        return pid;

接下来是实现waitSch，waitSch的大部分逻辑都和wait一样，不同的只是要先把p->rutime赋给*rutime，把p->retime赋给*retime, 以及p->sltime→*sltime，然后再把这些变量清空:

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
int 
waitSH(int* rutime, int* retime, int* sltime)
{
  struct proc *p;
  int havekids, pid;
  struct proc *curproc = myproc();
  
  acquire(&ptable.lock);
  for(;;){
    // Scan through table looking for exited children.
    havekids = 0;
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->parent != curproc)
        continue;
      havekids = 1;
      if(p->state == ZOMBIE){
        // Found one.
        pid = p->pid;
        kfree(p->kstack);
        p->kstack = 0;
        freevm(p->pgdir);
        p->pid = 0;
        p->parent = 0;
        p->name[0] = 0;
        p->killed = 0;
        																// modified
	    *rutime = p->rutime;
	    *sltime = p->sltime;
	    *retime = p->retime;
	    p->ctime=0;
	    p->rutime=0;
	    p->retime=0;
	    p->sltime=0;
        																// end
        p->state = UNUSED;
        release(&ptable.lock);
        return pid;
      }
    }

    // No point waiting if we don't have any children.
    if(!havekids || curproc->killed){
      release(&ptable.lock);
      return -1;
    }

    // Wait for children to exit.  (See wakeup1 call in proc_exit.)
    sleep(curproc, &ptable.lock);  //DOC: wait-sleep
  }

}

现在的问题是，如何动态地维护进程的运行时间、等待时间和休眠时间呢？

首先一个直观的思路是，在每一次进程状态变化的时候，例如由A→B，记录下这次状态转换的时间作为B状态的开始时间$t_{0}$, 等下一次再从B→C的时候，B的持续时间就加上这个时刻减去$t_{0}$. 但是这种方法实现起来非常复杂，首先进程状态转换可能在很多种情况下发生，每一次转换时，都要判断旧的状态和新的状态是什么，然后更新旧状态的持续时间，保存新状态的开始时间。这样代码会变得冗长而且容易出错，还需要为进程维护两倍的变量（对每一种状态，例如RUNNING, 至少需要维护最近一次RUNNING状态开始的时刻，以及累计运行时间）。

另一种思路是，在每一次收到时钟中断时，判断进程处于何种状态，为这种状态的持续时间加一。这样的计算是一种很粗糙的近似。这样计算，是假设进程会将这种状态维持一个时间片，在中间不发生状态的变换，并假设这种状态大概在时钟中断发生时开始。然而，在两个时钟中断之间，进程是很有可能调用sleep或wait进行休眠的，也有可能在下一个时钟中断到来之前，调度器就已经调度了另一个进程并将该进程唤醒，状态变为RUNNABLE，这样，中间的sleep阶段就没有被我们的计算捕捉到。不过因为进程一般是运行和等待的时间占大多数，sleep占比很少，运行和等待之间的切换又一般是通过时钟中断引发的yield, 所以这种近似还是可以接受的。

xv6 的时钟机制

xv6的时钟在timer.c中实现，每过100ms，硬件就会产生一个时钟中断。每个cpu都可以独立地接收时钟中断，并陷入中断处理。

在trap.c中定义了一个uint类型的变量ticks，每一次这个变量加一，代表系统的时钟往前走了一步。两个cpu收到时钟中断后，先后进入中断处理程序，为了让系统的时钟(ticks)能够真正在每次timer产生时钟中断的时候自增一，只在某一个固定的cpu收到中断时让ticks++, 因此xv6中每一次CPU0收到一个时钟中断，ticks就自增1：

1
2
3
4
5
6
7
8
9
10
11
switch(tf->trapno){
  case T_IRQ0 + IRQ_TIMER:     //收到了时钟中断
    if(cpuid() == 0){          //如果是cpu0收到了这个时钟中断，才将tick增加1；这样对于不同的cpu，时钟都是保持同步的，所有的cpu都会共用这个tick变量。
      acquire(&tickslock);       
      ticks++;
      wakeup(&ticks);
      release(&tickslock);
    }
    lapiceoi();
    cprintf("ashajh,time: %d, cpu: %d\n",ticks, cpuid());
    break;

编译这段代码，输出是：

这段输出中，每一次cpu id 为0时，对应的时钟比上一次printf增加一，而对于cpu1则不一定是这样。

如果我们要在每次时钟中断时判断进程的状态，也有两种思路。

第一个是，在时钟中断的时候，调用myproc先判断cpu上是否有进程在运行，如果有，则判断它的状态并更新变量。这种思路首先因为进程会在两个cpu上调度，而在cpu1上调度时，两次中断之间ticks不一定有增加，所以要增加一个lasttick保存上一次中断时ticks的值，如果这个值有改变，才会进行判断。但即使是添加了这个逻辑，这种方法也是错误的，因为如果myproc()能返回进程的PCB， 进程一定是处于RUNNING状态（否则它就不会被cpu调度了），这样我们无法知道进程何时在休眠或等待。

第二个思路是，在ticks++的时候，遍历整一个ptable表，对每个进程判断它是在何种状态，然后给变量+1.这样便可实现上面那种近似的算法。 在trap.c中作以下修改：

1
2
3
4
5
6
7
8
9
10
11
12
  switch(tf->trapno){
  case T_IRQ0 + IRQ_TIMER:
    if(cpuid() == 0){
      acquire(&tickslock);
      ticks++;
      									//modified
      update();                         //每一次ticks++时，更新进程状态变量
      wakeup(&ticks);
      release(&tickslock);
    }
    lapiceoi();
    break;

其中，判断进程状态并更新变量的函数在proc.c中实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void 
update()
{
    struct proc *p;
    acquire(&ptable.lock);    //对进程变量进行修改，要先获得ptable锁。
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    switch(p->state) {   //遍历整个表，判断进程状态
      case RUNNING:      //运行中
        p->rutime++;     //则运行时间增加一个时间片
        break;
      case SLEEPING:    //休眠中
        p->sltime++;     //休眠时间增加一个时间片
        break;
      case RUNNABLE:    //等待中
        p->retime++;    //等待时间增加一个时间片
        break;
      default: ;    // default，有ZOMBIE\EMBRYO\UNUSED，这些状态我们不关心
    }
  }
  release(&ptable.lock);  //释放锁
}

我们按照上次实验的步骤将waitSch包装成系统调用。 实现过程中比较重要的是，xv6syscall.c中系统调用函数的统一格式是返回值int, 不允许带参数。如果需要加入参数，则参数会被压入栈中，通过argint和argptr从栈上取出参数进行解析。在sysproc.c中包装waitSch如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int
sys_waitsch(void)
{
    int *rutime;
    int *retime; 
    int *sltime;
    int pid;
    rutime=retime=sltime=0;
    if(argptr(0, (char**)&rutime, sizeof(int)) < 0)
        return -1;
    if(argptr(1, (char**)&retime, sizeof(int)) < 0)
        return -1;
    if(argptr(2, (char**)&sltime, sizeof(int)) < 0)
        return -1;
    pid = waitSH(rutime, retime, sltime);
    if(pid!=-1)    //如果有子进程退出，打印出它的pid，运行时间、等待时间和休眠时间。
        cprintf("pid: %d, runtime:%d, ready time: %d, sleep time %d\n", pid, *rutime, *retime, *sltime);
    return pid;
}

在syscall.h以及系统调用表中，为waitSch增加系统调用号，并在user.h中定义接口。waitSch的实现已经完成。

编写RRsta.c 统计RR调度情况

编写RRsta.c， main函数接收一个命令行参数n, fork n个子进程进行相同的大规模计算，然后父进程调用waitSch，等待每个子进程的结束，并输出每个子进程的运行时间、等待时间和休眠时间。最后统计n个进程在RR（Round Robin）调度下的平均轮转时间。

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
#include "param.h"
#include "types.h"
#include "stat.h"
#include "user.h"
#include "fs.h"
#include "fcntl.h"
#include "syscall.h"
#include "traps.h"
#include "memlayout.h"

int stdout=1;
int main(int argc, char* argv[])
{
    int forknumber=atoi(argv[1]);   //命令行参数，为fork 子进程的个数
    int status;
    for(int i=0;i<forknumber;i++)    
    {
        status=fork();
        if(status==0){    //在子进程内status=pid=0
            for(int count=0;count<40; count++){  //执行相同的运算，主要是大规模乘、除法计算。
                printf(1," ");
                for(int k=0;k<1000000;k++){
                    int result=0;
                    for( int j=0; j<5000; j++){
                        result+=j*j;
                        result-=j*j;
                        result= result/j;
                        result=result*j;
                        result = result+result/j;
                    }
		    	}
            }
            
            exit();   //一定要注意exit，否则子进程也会执行上面的fork循环。
        }
    }
    int rutime;   //运行时间
    int retime;
    int sltime;
    int pid;      //子进程pid
    int sum=0; //周转时间总和
    while((pid = waitSch(&rutime,&retime,&sltime))!=-1){
        sum += rutime+retime+sltime;
    }
    printf(1,"average turn-around time of %d process is %d.\n", forknumber, sum/forknumber);
    exit();
}

将RRsta.c编译到qemu中，在shell中运行

1
2
3
4
make clean
make
make qemu
$ RRsta 10

得到输出：

image-20191115012022441

（实际上，手动计算平均周转时间的话会得到5.8， 但是xv6的printf并没有使用C的标准输出库，不支持输出浮点数，只能将小数省去了。

下一篇： Part 3： 优先级和动态多及反馈队列的实现、调度算法比较