xv6实现FIFO进程调度

整体方案

目标描述：xv6 增加先来先服务进程调度算法，与原有时间片轮转算法并存，并优先于时间片轮转，此外添加ps功能

进程调度原理及过程：
Xv6原有的进程调度算法非常简单
每个CPU初始化完毕后就载入proc.c中的scheduler函数开始进程调度，scheduler函数是个死循环，不停的通过内循环遍历所有进程状态，由于遍历的过程中可能会改变进程状态，所以，一次遍历的内循环外需要加锁保护，一旦scheduler函数发现有状态为RUNABLE的进程就调用swithuvm来载入这个进程段数据，并且把这个进程设置为RUNNING，调用swtch()来切换进程的内核态上下文，swtch()返回后就到了forkret()(创建新进程)或者sched()(运行中的切换，由yield,sleep,exit这种会导致进程切换的函数中调用的sched引起)，具体哪个函数要看swtch切换的进程上下文状态而定。
进程从swtch()返回后，要把scheduler()加的锁释放掉，然后返回到系统调用处，进入用户态运行。
如果是运行中发生切换，首先旧进程要让出CPU。
在trap.c文件里可以看到，一个进程从RUNNING变回RUNABLE是通过调用yeild()函数来强行让出CPU。
然后进程则会从用户态进入内核态的对应函数。获得进程列表锁，然后根据当前函数来设置运行状态，再调用sched()函数检查进程状态，检查完毕后，sched会调用swtch()把当前内核态切换到scheduler()中，继续上面的操作。
因此当多个进程共同存在时，每个进程执行一小片时间后就将CPU让给另一个进程。

我们添加了先来先服务FCFS调度算法，修改scheduler调度器，增加对进程创建时间的判断逻辑，即记录下创建时间最小的那个进程，当它没执行完，使它一直为当前进程，即状态一直为running，这便实现了FCFS。
同时我们为进程的数据结构添加了一个新属性flag，用于指定它是由FCFS调度还是由RR调度，以实现FCFS优先于RR执行，类似于Linux的普通进程与实时进程。

涉及的文件和关键数据结构

1. 为系统添加ps：
   1)在syscall.c里添加全局声明：

   extern int sys_cps(void); // PS
   
   static int (*syscalls[])(void) = {
   …
    [SYS_cps]     sys_cps, // PS
   …
   };

2)在syscall.h里添加系统调用号：

#define SYS_cps    22

3)在defs.h文件里添加函数调用接口:

int     cps(void);

4)同样在user.h里也加入，为用户调用：

int     cps(void);

5)usys.S文件里加入：

SYSCALL(cps)

6)在sysproc.c文件里加入：

int sys_cps(void)
{
  return cps(); 
}

7)再proc.c文件里加入cps函数

int cps(){
  struct proc *p;
  sti();
  acquire(&ptable.lock);
  cprintf("name \t pid \t state \t \n");
  for ( p = ptable.proc; p < &ptable.proc[NPROC]; p++)
  {
    if (p->state == SLEEPING)
    {
      cprintf("%s \t %d \t SLEEPING \t \n", p->name, p->pid);
    }
    else if (p->state == RUNNING)
    {
      cprintf("%s \t %d \t RUNNING \t \n", p->name, p->pid);
    }
    else if (p->state == RUNNABLE)
    {
      cprintf("%s \t %d \t RUNNABLE \t \n", p->name, p->pid);
    }
  }

  release(&ptable.lock);

  return 22;}

8)创建 ps.c 文件，此函数的作用是当用户在xv6中敲命令ps可以去调用cps()函数

#include “types.h”
#include “stat.h”
#include “user.h”
#include “fcntl.h”

int main(int argc, char const*argv[]){
cps();
exit();
}

9. 要想在xv6的命令行实现ps功能，必须在makefile设置去编译ps.c文件

   UPROGS=\
   	_cat\
   	_echo\
   	_forktest\
   	_grep\
   	_init\
   	_kill\
   	_ln\
   	_ls\
   	_mkdir\
   	_rm\
   	_sh\
   	_stressfs\
   	_usertests\
   	_wc\
   	_ps\ 
   	_zombie\
           _test\
           _testFF\
           _testRR\
           _testPR\

在makefile文件的此处也要修改

EXTRA=\
	mkfs.c ulib.c user.h cat.c echo.c forktest.c grep.c kill.c\
	ln.c ls.c mkdir.c rm.c stressfs.c usertests.c wc.c ps.c zombie.c\
	printf.c umalloc.c\
	README dot-bochsrc *.pl toc.* runoff runoff1 runoff.list\
	.gdbinit.tmpl gdbutil\

10. 编译make后运行xv6就可以在命令行执行ps命令了

2. 实现调度算法
   首先，类似于上面添加ps的过程，我们添加一个setflag的功能，用来指定进程采用的调度算法
   在syscall.c里添加全局声明：

   extern int sys_setflag(void); // PS
   
   static int (*syscalls[])(void) = {
   …
    [SYS_setflag]     sys_setflag, // PS
   …
   };

在syscall.h里添加系统调用号：

#define SYS_setflag    23

在user.h里加入用户调用：

void     cps(void);

usys.S文件里加入：

SYSCALL(setflag)

在sysproc.c文件里加入：

void sys_setflag(void)
{
  myproc()->flag = 1;
}

然后，打开proc.h文件，这里就是进程调度涉及到的非常关键的数据结构：

struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // Bottom of kernel stack for this process
  enum procstate state;        // Process state
  int pid;                     // Process ID
  struct proc *parent;         // Parent process
  struct trapframe *tf;        // Trap frame for current syscall
  struct context *context;     // swtch() here to run process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  uint ctime;                  // Process creation time  FCFS
  int flag;                   // to judge if FCFS
};

这便是进程的数据结构，我们添加

uint ctime;                  // Process creation time  FCFS
int flag;                   // to judge if FCFS

这两个成员，ctime用来记录进程创建时间，flag用来标记调度算法

接下来，在proc.c这个文件的这个函数里：

allocproc(void)
{
  struct proc *p;
  char *sp;

  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
    if(p->state == UNUSED)
      goto found;
  release(&ptable.lock);
  return 0;

found:
  p->state = EMBRYO;
  p->pid = nextpid++;
  p->flag = 0;
  p->ctime = ticks; // FCFS


  release(&ptable.lock);

  // Allocate kernel stack.
  if((p->kstack = kalloc()) == 0){
    p->state = UNUSED;
    return 0;
  }
  sp = p->kstack + KSTACKSIZE;

  // Leave room for trap frame.
  sp -= sizeof *p->tf;
  p->tf = (struct trapframe*)sp;

  // Set up new context to start executing at forkret,
  // which returns to trapret.
  sp -= 4;
  *(uint*)sp = (uint)trapret;

  sp -= sizeof *p->context;
  p->context = (struct context*)sp;
  memset(p->context, 0, sizeof *p->context);
  p->context->eip = (uint)forkret;

  return p;
}

在found：下面我们给每个进程的flag和ctime设定初始值。

最后，修改调度器算法如下：

void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  c->proc = 0;
  //cprintf("%d\n", 111);
  for(;;){
    // Enable interrupts on this processor.
    sti();

    // Loop over process table looking for process to run.
    acquire(&ptable.lock);
    struct proc *minP = 0;
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){

      if(p->state != RUNNABLE){continue;}

 	    // ignore init and sh processes from FCFS
      if(p->flag){
        //scheduling
        if(p->pid > 1){
         if (minP != 0){
          if(p->ctime < minP->ctime){minP = p;}
         }
         else {minP = p;}
        }
        if(minP != 0 && minP->state == RUNNABLE) {
         p = minP; 
         //cprintf("%d\n", minP->pid);
        }
      //find the minP as the target process
      }
      else{
      	if(minP != 0 && minP->state == RUNNABLE){
          p = minP;
        } 
      }
      //run new target process
      if (p!=0){
       //p = minP;//the process with the smallest creation time
       c->proc = p;
       switchuvm(p);
       p->state = RUNNING;
       //cprintf("%d\n", p->pid);
       swtch(&c->scheduler, p->context);
       switchkvm();
        // Process is done running for now.
        // It should have changed its p->state before coming back.
       c->proc = 0;
      }
    }
  release(&ptable.lock);

  }
}

最后，写一个测试函数testPR.c，并将其添加到makefile里编译为可执行文件，就大功告成了。

include "types.h"
#include "stat.h"
#include "user.h"

int main()
{
    int count, count2, processID, startTime = uptime();

    for (count = 0; count < 20; count++)
    {
        if (count<10)
        {
            processID = fork();
            if (!processID)
            {
                break;
            }
        }
        else
        {
            processID = fork();
            setflag();
            if (!processID)
            {
                break;
            }
        }


    }

    int primeCount = 0;
    
    for (count = 1; count <= 30000; count++)
    {
        for (count2 = 2; count2 < count; count2++)
        {
            if (!(count % count2))
            {
                break;
            }
        }
        
        if (count2 == count)
        {
            primeCount++;
        }
    }
    printf(1,"%d:%d\n",getpid(), primeCount);

    if (processID)
    {
        for (count = 0; count < 20; count++)
        {
            wait();
        }

        printf(1, "Total Elapsed Time: %d ms\n", uptime() - startTime);
    }

    exit();
}