操作系统实验报告2¶
实验材料¶
一、实验目的¶
本次实验的内容是在xv6系统的基础上实现彩票调度。为此，必须读懂源文件中关键部分的用法和对该系统的构成有所了解。同时，也应该理解彩票调度的原理。
二、实验内容¶
part1：理解彩票调度¶
首先，我们需要理解彩票调度的工作原理。下面的图片可以形象地理解彩票调度：
也就是说，彩票调度实际上是运用随机算法实现系统调度的一种方式。它根据每个进程在CPU中运行时间的不同，来给进程分配不同数量的彩票。接下来，操作系统会设定一个中奖号码，然后所有进程依据进程链表中的顺序来抽奖（彩票调度公平性的前提）。最后，谁先抽到这个号码，谁就获得CPU的执行权。
它的实现机制是这样的：
- 一种方式是利用彩票货币（ticket currency）的概念。这种方式允许拥有一组彩票的用户以他们喜欢的某种货币，将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。
eg：假设用户 A 和用户 B 每人拥有 100 张彩票。用户 A 有两个工作 A1 和 A2，他以自己的货币，给每个工作 500 张彩票（共 1000 张）。用户 B 只运行一个工作，给它 10 张彩票（总共 10 张）。操作系统将进行兑换，将 A1 和 A2 拥有的 A 的货币 500 张，兑换成全局货币 50 张。类似地，兑换给 B1 的 10 张彩票兑换成 100 张。然后会对全局彩票货币（共 200张）举行抽奖，决定哪个工作运行。
-
彩票转让，一个进程可以临时将自己的彩票交给另一个进程。
-
彩票通胀（ticket inflation）有时也很有用。利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。
当然，在本实验中，我们实现的彩票调度更为简单，只需要给每个进程分配全局彩票即可，不用关注彩票货币或是转让、通胀等概念。
而从原理上说，彩票调度也是科学的：
即使是进程间的彩票份额非常悬殊，彩票调度也能够很好地保证公平性。因为从概率上说，只要开奖次数趋近于无穷，那么一定所有的进程都会被运行。
当然，彩票调度也存在一些劣势，例如，它不能很好的适合 I/O（有论文研究过这个问题）。而另一个原因就是文中所提到的，票数分配问题没有确定的解决方式，比如你新打开了一个浏览器进程，那该给他分配多少票？票数少了，响应跟不上，票数多了，又会浪费 CPU 时间。
part2：关键源文件解读¶
理解完彩票调度的核心机制，我们就需要上手来实现彩票调度了。由于我们拿到的系统文件非常多而杂，因此按实验手册的思路去过一遍需要修改的文件是必要的。
实验手册中提到的文件包括：syscall.h、syscall.c、defs.h、proc.h、param.h、proc.c、sysproc.c、usys.S 、user.h 、Makefile文件。
syscall.h与syscall.c¶
syscall是能让操作系统去调用各种系统函数的文件。在这个文件中，系统调用函数们在头文件被宏定义为整数，然后在程序中被函数指针保存，并且通过syscall（）函数调用。
defs.h¶
这个头文件声明了关键文件的函数和结构体，其中包含了关键文件syscall.c和proc.c的声明。
param.h¶
这个头文件宏定义了一些常量，例如：#define NPROC 64 // maximum number of processes。
proc.h和proc.c¶
这两个文件是本次实验中最关键的两个文件。
首先是proc.h文件。这个文件中定义了几个后续实验中非常常用的结构体。一是proc：这个结构体刻画了进程的性质，关键性质包括state、pid等。二是cpu：这个结构体中的成员包括了proc结构体，这个成员指代正在cpu上运行的文件。三是context，这个是用于切换上下文。三者具体定义如下：
struct cpu {
uchar apicid; // Local APIC ID
struct context *scheduler; // swtch() here to enter scheduler
struct taskstate ts; // Used by x86 to find stack for interrupt
struct segdesc gdt[NSEGS]; // x86 global descriptor table
volatile uint started; // Has the CPU started?
int ncli; // Depth of pushcli nesting.
int intena; // Were interrupts enabled before pushcli?
struct proc *proc; // The process running on this cpu or null
};
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)
// new added
int in_use;
int ticket;
int ticks;
int tick;
};
struct context {
uint edi;
uint esi;
uint ebx;
uint ebp;
uint eip;
};
在这个文件中，还有一个比较关键的枚举procstate，用于描述进程的状态，包括：UNUSED, EMBRYO（萌芽：该任务结构体刚分配出去，几乎什么资源都还没分配给该进程）, SLEEPING, RUNNABLE, RUNNING, ZOMBIE。
接下来是proc.c文件。
这个文件是用于描述进程和cpu交互的文件，包括关键行为如fork函数，allocproc函数，scheduler函数等，是我们实现彩票调度程序的文件。
sysproc.c¶
这个文件主要定义了用户空间和内核空间交互的行为。例如，sys_settickets和sys_getpinfo函数就定义在这个文件中，它们大多是对输入的参数进行检查，然后调用proc.c中的真正内容。这个文件是为了把可能会出错的交互和真正的内核隔离。
usys.S：¶
预处理+汇编的文件，只要把在sysproc中新增的系统函数给放进去即可。这个文件的作用是把终端输入的命令解析为syscall（）能调用的形式。
user.h¶
定义了用户空间的行为。只需在这个文件中加入pstat结构体的定义即可。（我们在test系列文件中会用到ptsat结构体指针）
pstat.h、rand系列文件¶
这个文件是应该创建的文件，但是在添加代码中已经写好了。pstat文件定义了结构体pstat，这个结构体描述所有进程的信息，用数组的形式对每个进程的信息进行保存，包括inuse（该进程是否可用），ticket（进程票数），pid，tick（进程所用的时间片）。
part3：彩票调度实现过程¶
通读上述文件后，接下来按照实验手册给出的思路去实现彩票调度。
实现用户空间的testTicket.c、testProcInfo.c¶
在testTicket中，设置当前进程的票数。它接受一个整数参数作为命令行参数，并将其转换为票数。然后它使用 settickets() 系统调用来设置当前进程的票数为给定的值。主要作用是在用户空间调整进程的调度优先级。
这个实现很简单，用atoi(argv[1])就能够接收整数参数，同时settickets只有一个整数作参数。
int main(int argc, char *argv[])
{
// printf(1, "test_Ticket\n");
int number = atoi(argv[1]);
settickets(number);
while (1)
{
/* code */
/* just for delay */
}
exit();
}
在testProcinfo中，我们需要显示当前正在运行的进程的信息，包括进程ID、是否可运行、分配的彩票数和已累积的CPU时间片数（ticks）。它通过调用 getpinfo() 系统调用来获取进程信息，然后将其打印到标准输出。
这个文件也非常简单，仿照最终输出格式就可以得到需要的程序。getpinfo的参数是pstat*，因此我们在程序中需要定义一个pstat变量，然后得到相关程序。
int main(int argc, char *argv[])
{
int count = 0;
struct pstat ps;
getpinfo(&ps);
printf(1, "\n------------ Initially assigned Tickets = %d ----------\n", InitialTickets);
printf(1, "\nProcessID\tRunnable(0/1)\tTickets\t\tTicks\n");
for (int i = 0; i < NPROC; i++)
{
if (ps.pid[i] && ps.ticket[i] > 0)
{
printf(1, "%d\t\t%d\t\t%d\t\t%d\n", ps.pid[i], ps.inuse[i], ps.ticket[i], ps.tick[i]);
count += ps.tick[i];
}
}
printf(1, "\n------------------- Total Ticks = %d -----------------\n\n", count);
exit();
}
实现 settickets 系统调用¶
在test中调用了settickets，而我们还没有真正实现它。因此，我们需要在proc文件（描述系统与进程交互的文件）中书写这个函数。
首先，我们需要知道某个proc分得的票数是多少。在part1中我们曾提到彩票调度的劣势之一就是难以确定每个程序应该分得多少张票，因此事实上这里定义的票数来自于用户空间，即用户在输入命令行参数时就定义该进程的票数。而这个信息被保存在一个名为ptable的变量中。
插入对ptable的分析。在proc.c的开头就定义了ptable结构体变量，这个结构体包括ptable.lock和proc[NPROC]。前一个成员用于控制进程共享变量的统一（通俗地说，就是上锁），后一个数组变量类似一个进程链表，用于保存每个proc的信息（具体信息定义在结构体proc中）。
接下来开始给进程设置票数。
int settickets(int number)
{
struct proc *pr = myproc();
int pid = pr->pid;
acquire(&ptable.lock); // Find and assign the tickets to the process
struct proc *p;
for (p = ptable.proc; p < &ptable.proc[NPROC]; p++)
{
if (p->pid == pid)
{
p->ticket = number; // assigining alloted ticket for a process
release(&ptable.lock);
return 0;
}
}
release(&ptable.lock);
return 0;
}
-
首先，在proc.h中对struct proc进行修改，新增了in_use（进程是否可用），ticket（该进程的票数），ticks和tick。 同时，在这个文件中增加了一个setticket函数声明。
-
接下来进入proc.c。在include中先引入pstat.h（主要是为了引入数据结构pstat）和rand.h（在scheduler中使用）。
补充：在spinlock.c中存在一个acquire函数，这个函数负责获得锁。相应的，有一个release函数，负责释放锁。
-
进入setticket函数（形参为number）。首先，初始化一个proc指针pr作为一个新进程。然后立刻上锁。注意，此时的锁对象是ptable，这个结构体包含一个spinlock，以及一个porc结构体数组。通俗地说，ptable是所有进程的一个索引表。
-
接下来，再新建一个临时的proc指针p作为进程迭代的变量。进入一个for循环，这个循环检索所有的进程，如果遇到了本次新建的进程（用pid作为标准，但通俗地说，条件是p==pr），则把预设的票数传入这个进程p。
-
最后，释放这个锁。注意到在循环外也需要释放这个锁，防止因为没有找到对应pid而没有执行if，从而发生死锁。
接下来，为了在系统调用时也能有setticket函数，需要在sysproc中实现sys_settickets函数。
int sys_settickets(void)
{
int number;
argint(0, &number); // get prarmeters from user's space
if (number < 0)
return -1; // unsuccessful
else if (number == 0)
return settickets(InitialTickets); // default
else
{
return settickets(number);
}
}
注意到在这个函数中，我们需要使用argint函数去获得用户输入的参数。如果输入的数字小于0，创建不成功；输入为0，说明我们需要调用一个默认的参数InitialTickets（在param.h中声明，值为5）；输出为其他数字，则直接创建对应票数的数字。
实现 getpinfo 系统调用¶
在testpinfo文件中调用了getpinfo函数，因此沿用上述思路，仍然需要在proc.c中实现它。
int getpinfo(struct pstat *ps)
{
acquire(&ptable.lock);
struct proc *p;
int i = 0;
for (p = ptable.proc; p < &ptable.proc[NPROC]; p++)
{
ps->pid[i] = p->pid;
ps->inuse[i] = p->state != UNUSED;
ps->ticket[i] = p->ticket;
ps->tick[i] = p->tick;
i++;
}
release(&ptable.lock);
return 0;
}
这个思路很简单：
- 先上锁（ptable.lock），然后又定义一个proc指针p作为迭代变量。
- 然后根据ptable中的proc，给ps的各个进程的各结构成员赋值。
- 退出锁。
接下来进入sysproc.c文件：
int sys_getpinfo(void)
{
struct pstat *ps;
if (argptr(0, (char **)&ps, sizeof(struct pstat)) < 0)
return -1;
getpinfo(ps);
return 0;
}
- 在sys_getpinfo中，使用argptr获得用户空间传递的结构体指针ps。
- 调用getpinfo函数。
在创建和初始化进程时添加彩票信息¶
在开始修改前，对allocproc进行一些分析。
static struct proc*
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++;
/*new added*/
p->ticket = InitialTickets; // initially
p->tick = 0;
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;
}
通过源代码可以看出，这个函数实际上是在完成为新的proc分配内核栈等初始化行为。它是将任务结构体分配出去，但是还没有给这个进程分配资源（即彩票）。理解这个作用后，我们可以发现这个进程的proc只需要在初始化是加入票数信息即可。
- 进入proc.c函数，首先修改allocproc。这个函数是用来给proc分配空间的。只要在found板块中初始ticket和tick即可。
- 在fork函数中np的初始化过程中，加入ticket项。
调整调度算法¶
最关键的一步到了。现在，我们需要重写一个进程调度程序，将原本的轮换调度改为彩票调度。那么首先我们直接上源码。
void scheduler(void)
{
struct proc *p;
struct cpu *c = mycpu();
c->proc = 0;
for (;;)
{
sti(); // Enable interrupts on this processor.
long cur_total = 0;
acquire(&ptable.lock); // Loop over process table looking for process to run.
long total = getRunnableProcTickets() * 1LL;
long win_ticket = random_at_most(total); // from rand.c
for (p = ptable.proc; p < &ptable.proc[NPROC]; p++)
{
if (p->state == RUNNABLE)
cur_total += p->ticket;
else
continue;
if (cur_total > win_ticket) // winner process
{
// Switch to chosen process. It is the process's job to release ptable.lock and then reacquire it before jumping back to us.
c->proc = p;
switchuvm(p);
p->state = RUNNING;
// p->tick++;
int tick_start = ticks;
swtch(&(c->scheduler), p->context);
int tick_end = ticks;
p->tick += (tick_end - tick_start);
switchkvm();
// Process is done running for now. It should have changed its p->state before coming back.
c->proc = 0;
break;
}
else
continue;
}
release(&ptable.lock);
}
}
- 首先，初始化了两个结构体指针，即proc p和cpu c。其中，cpu结构体中含有proc结构体指针，表示正在cpu上执行的process。
- 然后进入一个退出条件在循环内部的for循环。
- 首先，使用sti()允许对这个处理器进行中断（即可以打破外层循环）。同时，初始化一个cur_total进行当前总票数的统计。再上锁。
- 接下来，使用 getRunnableProcTickets() 算出总票数，其中1LL是为了在运算中临时扩容。
- 通过随机库（rand.c）给出一个随机数，作为中奖的彩票。
- 接下来，把p作为迭代变量，对ptable.proc[]中的进程进行遍历。
- 如果p可以在准备运行的就绪状态（RUNNABLE），则使当前的总票数加上中奖的票数。否则跳过。注意状态一共有六种（UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE）
- 如果如果当前票数小于总票数，则continue；当前票数大于等于总票数，则该进程中奖，设置cpu当前运行的进程为p，然后用switchuvm（）使cpu转向当前进程。注意，我们是在进程中释放ptable.lock的锁，并在回到这个函数时再次获得它（就好像我们没有开过锁一样）。
- 调整p的状态为running，并且令tick_start=ticks（在trap.c中定义，描述总共进行的时间片）。然后用swtch切换上下文，使这个进程开始运行。（该操作在proc.h中定义proc时说明）
- 再次获得ticks（此时的ticks是执行了p之后的）为tick_end，此时相减，就能够获得p的时间片数目。（最初想要直接p->tick++，但是这样做显然忽略了一个进程可能会使用多个时间片的事实）
- 再次调用switchkvm()，使得p的状态在返回前被更改。
- 重置cpu的进程为0。并且让内层循环结束。
- 释放锁。
补充：在这个函数之中我们有调用一些新定义的函数和在上文中未解释的函数。我们来一一解释。
首先是这个 getRunnableProcTickets() 。它的源码如下：
int getRunnableProcTickets(void)
{
struct proc *p;
int total = 0;
for (p = ptable.proc; p < &ptable.proc[NPROC]; p++)
{
if (p->state == RUNNABLE)
{
total += p->ticket;
}
}
return total;
}
事实上，它的原理很简单，也就是把所有状态为可执行的所有进程给搜集出来，然后把它们的总票数相加。
再者是switchkvm()和swtch()和switchkvm()。这个函数的源码较为复杂，就不予展出了。事实上，为什么要在scheduler中调用这个函数，是因为在原本的scheduler函数中调用了它，我是仿照原函数的结构来书写新结构的。如：
// for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
// if(p->state != RUNNABLE)
// continue;
// // Switch to chosen process. It is the process's job
// // to release ptable.lock and then reacquire it
// // before jumping back to us.
// c->proc = p;
// switchuvm(p);
// p->state = RUNNING;
// 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;
// }
在原scheduler函数中，通过注释可知，我们用switchuvm函数来使用户空间的虚拟内存转入进程p中。同时，再用swtch函数来切换上下文。最后用switchkvm（）转入内核页表中，再进入响应的进程中。
其他文件修改¶
在syscall.h中，添加了SYS_yield\SYS_settickets\SYS_getpinfo三个函数的编号（宏定义形式）。
在syscall.c中，先在使用extern关键字的声明群中声明一系列函数（包括sys_yield等），然后再在后面的函数指针引用它们。
在defs.h中，添加新增的结构体pstat。
在param.h中，添加一个初始化常数InitialTickets，这个常数表示没有特殊说明，进程的票数都是5.
在usys.S中，添加SYSCALL（yield), SYSCALL(settickets), SYSCALL(getpinfo)等。
在user.h中，添加struct pstat和settickets与getpinfo两个函数（我们在彩票调度中新增的函数）。
在pstat.h中，定义了一个新的结构体pstat，这个结构体能够说明inuse（是否使用），ticket（每个进程的票数），pid，tick（每个进程所用的时间片数）。
至此，本次实验的框架大致完成。
三、使用环境¶
基于ubuntu虚拟机的xv6环境。
四、实验过程及结果¶
接下来，我们对整个实验的过程进行描述。
实验过程的解释¶
- 首先，我们在终端输入了testTicket 10&；
- 接下来，终端的“终端解释器”将会解释我们输入的命令，并把它拆分为可解释的几部分。然后这个部分将会传入操作系统内核；
- 在内核，我们进一步产生系统调用。具体到本实验中，就是在usys.S中获得系统调用号，然后开始执行syscall.c文件；
- syscall.c中我们执行syscall()函数，由于我们预先保存了一个函数指针数组，可以根据系统调用号进入sysproc中相应的函数，这里是sys_settickets函数；
- 接下来，在sysproc.c中的sys_settickets()对输入的number进行检查。如果number合法，我们就调用proc中的settickets()函数；
- 在settickets（）中，我们需要给关键的共享变量PTABLE上锁，使多个进程共享同一个数据。同时，我们在这个函数中遍历已有的进程， 从而将用户输入的票数（10）传给特定的进程。
- 最后，释放这个锁，然后退出函数。注意，在我们命令行的回车输入后，cpu就开始运行相应的进程，而这个过程后，scheduler（）函数触发，我们进一步进行彩票调度。
补充一点，在testTicket.c中，我们执行了一个不会结束的循环while（1）{}，这个函数保证进程不会结束，从而一直在调度池中。也因此，实际上这个程序除非清楚终端，否则不会停止运行。
实验结果¶
多次实验，每次的total ticks不同，每个进程的ticks也不同，并且ticks大致与分得的tickets成比例变化。这说明正确实现了随机化算法：彩票调度。
五、总结¶
通过本次实验，我收获了很多：
- 提高了对彩票调度原理的理解。曾经我认为彩票调度是所有进程随机获得很多不同的彩票号码，再让操作系统再随机抽取一个数字。但是现在我知道了彩票调度实际上契合了“均匀分布”的思想，即把所有进程排好序，然后分发不同数量的彩票（即认为不同进程占有不同长度的区间），最后选择一个区间内的数字，落在哪里，哪里就是可以调度的进程。
- 其次，深化了对操作系统理论知识的认知。例如，尽管一直知道内核空间和用户空间有别，但一个具体的操作系统是怎么实现的还是不太清楚。在这里，借助usys.S、syscall()、sysproc()、proc()四个文件，我形成了对系统调用过程的认知——终端到解释器，再到系统调用过程，并进入相应的系统调用函数，最后在内核中执行，并把输出结果仅有来时路径返回终端。
- 最后，提高了个人的工程作业的理解。在c语言的编程中，总是会把声明和结构体定义写在h头文件中，而把主体写在c文件中。再者，可以使用锁来同步代码。在多线程的编程当中，多个进程可能会调用同一个变量，那么这个变量的值就应该受到保护。而在c语言中，我们可以用spinlocks的方式来控制多个进程。