xv6源码解析（四）——进程管理

01 进程管理

进程管理：添加了常见的IPC通信模块（共享内存、消息队列）；以进程上下文切换为基础，实现了时间片轮转调度算法；设计了自旋锁Spinlock，为用户进程提供互斥机制。

02 进程通信

共享内存

设计的简化版本的共享内存，远达不到Linux共享内存的通用程度,但也能将共享内存的核心思想体现出来。

简化后的限制包括：

（1）整个系统只有固定的若干个共享内存区

（2）进程不允许一个共享内存区反复映射到自己的虚存空间

（3）进程退出时自动解除共享映射

（4）共享内存作为进程最高端的空间从而避免与xv6原来的sbrk操作冲突

共享内存需要实现不同进程访问同一块物理内存，其核心机制是不同进程分配pte指向相同物理页帧（物理内存地址），从而使该页帧在不同进程中都是可见的

系统中一共有8个共享内存区，因此系统中每个共享内存使用一个引用计数来表明是否启用。

每个进程则使用一个8位掩码或者一个编号来指示其中一个区域，其中，shmkeymask用于记录本进程对这些共享内存区的启用情况，key用于指出一个共享内存区的编号，而i往往用作遍历这些内存区时的循环变量

实现步骤：

（1）首先需要定义一个sharemem结构体，里面的成员包括了引用计数、共享内存区间大小、本区间所映射的物理页帧。

（2）新增一个系统调用sharememoryget，用于指定获取8个共享内存区的哪一个，分配对应的物理内存，建立页表映射后返回该内存的虚拟地址。然后把共享内存映射到进程空间

• 若共享内存被映射过，直接返回退出。不允许共享内存在同一个进程被多次映射！！！
• 共享内存区还未创建，引用技术还为0，创建该内存区
• 已有对应的共享内存区，直接映射到进程空间即可

（3）进程退出时，接触共享内存区的映射，引用计数减一，解除页表映射。如果引用计数为0，还需要释放物理内存。

消息队列

（1）首先使用一个msg结构体描述一个消息，消息队列存储了消息msg，对应的key，引用数，所有消息队列构成一个链表。

（2）消息队列的实现涉及初始化、创建mqget和撤销消息队列、消息的发送msgsend和接收msgrecv。 5个步骤

• 初始化 需要将各个消息队列状态设置为空闲未使用，同时进行锁的初始化。若被使用，引用计数加1
• 创建消息队列 每个消息队列使用一个页的内存空间，各个消息都存储于该页的4kb空间内
• 发送消息需要指出哪个消息队列，消息缓冲区首地址以及消息长度三个参数。接收消息类似，也需要指出哪个消息队列，消息缓冲区首地址以及消息长度三个参数
• 引用计数为0时，回收内存

03 进程上下文切换

中断上下文切换

用户程序陷入到内核通过中断INT指令，在xv6中系统调用的号为64

操作系统在初始化的时候会建立IDT表以及GDT表

通过INT找到IDT中的项，通过IDT中的项找到GDT中的项，最后定位到代码。

在执行陷入指令的时候首先会到trapasm.S中的alltraps中，将trapframe存入到应用程序的内核栈中。将esp的地址存入栈中作为trap函数的输入，然后调用trap。注意trapframe中有的字段会自动存入，比如int指令会通过CPU存入ss,esp,eflags,cs,eip,errorcode,trapno。系统调用号存在寄存器eax中。应用程序在初始化的时候操作系统会为每个应用程序保留一个内核栈，其中TSS断记录内核栈的一些信息比如内核栈的入口地址esp0。

系统调用将返回值存入到寄存器eax中。返回的时候通过trapret将原来的状态返回。最后一条指令iret回到用户程序。

内核进程上下文切换

xv6在进程调度中主要通过切换context上下文结构进行的：

struct context {
  uint edi;
  uint esi;
  uint ebx;
  uint ebp;
  uint eip;
};
1
2
3
4
5
6
7

context保存着 被调用函数必须手动保存的寄存器的值，Intel规定以上寄存器发生过程调用时必须由被调用者保存，同时eip保存的被调用函数的返回地址，正常情况下c函数被调用时编译器会自动为其加上保存context的代码，xv6使用context切换来完成进程切换操作。

每个进程都有一个指向自己context结构的指针，当发生进程切换时，通过保存旧的context，然后将恢复另一个context来切换到另一个进程，swich汇编代码是所有进程切换的基础，旧进程调用swich时首先保存自己的context，然后将栈指针指向新的context，弹出恢复寄存器，当switch返回时返回的地址则是新的进程返回swich的代码，也就是说，进程总是调用swich来切换新进程，而swich从此并不会返回，只有当进程再次被调度时才能恢复到返回swich的“状态”，进程的状态总是被恢复在swich返回时状态。
在这里需要注意的是为什么context只保存部分寄存器的值，因为swich的操作总是让一个进程返回到调用swich应该返回的地方，也就是说，在调用swich之前，Intel的寄存器使用规范已经保证调用者保存寄存器能够被被调用的过程破坏，所以就算当切换到另一个进程时寄存器或许是旧进程的，但是对于新进程来说，它或者总是不会读取这些数据已经被破换的寄存器（Intel体系规定了寄存器使用惯例，所有编程人员都应该注意这个问题）。

04 进程调度

时间片轮转

xv6永远不会直接从一个进程的上下文切换到另一个进程的上下文，这些都是通过一个中间的内核线程实现的：内核调度器线程。具体如图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c8pvedk5-1668171607564)(https://image-1312312327.cos.ap-shanghai.myqcloud.com/20170123135047439)]

在前面讲过当进程用完它的CPU时间片时，时钟中断会调用yield函数来让出CPU给新的进程，yield调用sched函数，sched调用swich来切换都调度器线程：

调度器线程从进程表中找到一个就绪进程，并初始化进程运行环境，然后调用swich切换到新的进程：

  swtch(&proc->context, cpu->scheduler);
1

调度器线程从进程表中找到一个就绪进程，并初始化进程运行环境，然后调用swich切换到新的进程：

  swtch(&cpu->scheduler, p->context);
1

调度器线程仅仅是简单地进行轮转调度，一旦找到就绪线程便切换到新的线程。
调度器完整代码如下：

// Loop over process table looking for process to run.
acquire(&ptable.lock);
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.
  proc = p;
  switchuvm(p);
  p->state = RUNNING;
  swtch(&cpu->scheduler, p->context);
  switchkvm();

  // Process is done running for now.
  // It should have changed its p->state before coming back.
  proc = 0;
}
release(&ptable.lock);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

}
}

05 进程互斥、同步

自旋锁

因为xv6是多核操作系统，因此在进程唤醒睡眠的时候要加上自旋锁，保证在进程进程睡眠和唤醒进程时不会发生自旋锁拿不到的情况。

先贴上自旋锁的实现代码

// x86.h
static inline uint xchg(volatile uint *addr, uint newval) {  // 给某个地址赋值的原子操作
  uint result;

  asm volatile("lock; xchgl %0, %1" :
               "+m" (*addr), "=a" (result) :
               "1" (newval) :
               "cc");
  return result;
}

1
2
3
4
5
6
7
8
9
10
11

// spinlock.h
struct spinlock {
  uint locked;      
};

// spinlock.c
void acquire(struct spinlock *lk) {
  pushcli(); 
  if(holding(lk))
    panic("acquire");

  while(xchg(&lk->locked, 1) != 0)
    ;
  __sync_synchronize();  // 访存屏障，保证次序
}

void release(struct spinlock *lk) {
  if(!holding(lk))
    panic("release");

  lk->pcs[0] = 0;
  lk->cpu = 0;
  __sync_synchronize();
  asm volatile("movl $0, %0" : "+m" (lk->locked) : );
  popcli();
}

void pushcli(void) {
  int eflags;

  eflags = readeflags();
  cli();
  if(mycpu()->ncli == 0)
    mycpu()->intena = eflags & FL_IF;
  mycpu()->ncli += 1;
}

void popcli(void) {
  if(readeflags()&FL_IF)
    panic("popcli - interruptible");
  if(--mycpu()->ncli < 0)
    panic("popcli");
  if(mycpu()->ncli == 0 && mycpu()->intena)
    sti();
}

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

在自旋锁获取和释放中会出现pushcli()和popcli()的两个函数，这是为何？当然，这也是自旋锁的疑点，下面我来解释一下。

xv6是多核系统，要实现互斥，可以先关闭中断，然后获取自旋锁，这样临界区的代码的执行就不会被时钟中断所中断。

不可把关中断和获取自旋锁的顺序颠倒，因为如果当获取自旋锁在前时，某个内核线程获取了自旋锁，但是此时产生了时钟中断而被换下CPU，此时剩下所有的CPU都不会获得自旋锁，一直无限的while，产生死锁。

那cpu->ncli ++是为何？这是因为某个cpu可能持有不止一把锁，如空闲链表锁，进程描述符表锁等等，假设先获取锁a，后获取锁b，那么释放锁b的时候就会打开中断，但此时还持有锁a，然后又因为时钟中断被换下，又会让剩下的cpu无限的自旋……

所以我们希望直到持有的最后一把自旋锁被释放的时候，才开中断，这可以通过一个计数器ncli实现，但这还不够，当产生中断的时候会执行某个中断处理程序，在关中断之前可能这个中断处理程序在处理过程中，因此我们还应该把第一次锁的处理器中断情况记录下来，最后一次解锁的时候把中断状态恢复到最开始的状态

// proc.h
struct cpu {
  uchar apicid;                
  struct context *scheduler;  
  struct taskstate ts;         
  struct segdesc gdt[NSEGS];   
  volatile uint started;       
  int ncli;  // 记录锁的状态个数  
  int intena;  // 是否在pushcli之前开启了中断               
  struct proc *proc;           
};

1
2
3
4
5
6
7
8
9
10
11
12