[系统运维]操作系统实验五 基于内核栈切换的进程切换(哈工大李治军)

实验5 基于内核栈切换的进程切换

实验目的

• 深入理解进程和进程切换的概念；
• 综合应用进程、CPU 管理、PCB、LDT、内核栈、内核态等知识解决实际问题；
• 开始建立系统认识。

实验内容

现在的 Linux 0.11 采用 TSS 和一条指令就能完成任务切换，虽然简单，但这指令的执行时间却很长，在实现任务切换时大概需要 200 多个时钟周期。

而通过堆栈实现任务切换可能要更快，而且采用堆栈的切换还可以使用指令流水的并行优化技术，同时又使得 CPU 的设计变得简单。所以无论是 Linux 还是 Windows，进程/线程的切换都没有使用 Intel 提供的这种 TSS 切换手段，而都是通过堆栈实现的。

本次实践项目就是将 Linux 0.11 中采用的 TSS 切换部分去掉，取而代之的是基于堆栈的切换程序。具体的说，就是将 Linux 0.11 中的 switch_to 实现去掉，写成一段基于堆栈切换的代码。

本次实验包括如下内容：

• 编写汇编程序 switch_to：
• 完成主体框架；
• 在主体框架下依次完成 PCB 切换、内核栈切换、LDT 切换等；
• 修改 fork()，由于是基于内核栈的切换，所以进程需要创建出能完成内核栈切换的样子。
• 修改 PCB，即 task_struct 结构，增加相应的内容域，同时处理由于修改了 task_struct 所造成的影响。
• 用修改后的 Linux 0.11 仍然可以启动、可以正常使用。

TSS 切换

在现在的 Linux 0.11 中，真正完成进程切换是依靠任务状态段（Task State Segment，简称 TSS）的切换来完成的。

具体的说，在设计“Intel 架构”（即 x86 系统结构）时，每个任务（进程或线程）都对应一个独立的 TSS，TSS 就是内存中的一个结构体，里面包含了几乎所有的 CPU 寄存器的映像。有一个任务寄存器（Task Register，简称 TR）指向当前进程对应的 TSS 结构体，所谓的 TSS 切换就将 CPU 中几乎所有的寄存器都复制到 TR 指向的那个 TSS 结构体中保存起来，同时找到一个目标 TSS，即要切换到的下一个进程对应的 TSS，将其中存放的寄存器映像“扣在” CPU 上，就完成了执行现场的切换，如下图所示。

Intel 架构不仅提供了 TSS 来实现任务切换，而且只要一条指令就能完成这样的切换，即图中的 ljmp 指令。

具体的工作过程是：

• （1）首先用 TR 中存取的段选择符在 GDT 表中找到当前 TSS 的内存位置，由于 TSS 是一个段，所以需要用段表中的一个描述符来表示这个段，和在系统启动时论述的内核代码段是一样的，那个段用 GDT 中的某个表项来描述，还记得是哪项吗？是 8 对应的第 1 项。此处的 TSS 也是用 GDT 中的某个表项描述，而 TR 寄存器是用来表示这个段用 GDT 表中的哪一项来描述，所以 TR 和 CS、DS 等寄存器的功能是完全类似的。
• （2）找到了当前的 TSS 段（就是一段内存区域）以后，将 CPU 中的寄存器映像存放到这段内存区域中，即拍了一个快照。
• （3）存放了当前进程的执行现场以后，接下来要找到目标进程的现场，并将其扣在 CPU 上，找目标 TSS 段的方法也是一样的，因为找段都要从一个描述符表中找，描述 TSS 的描述符放在 GDT 表中，所以找目标 TSS 段也要靠 GDT 表，当然只要给出目标 TSS 段对应的描述符在 GDT 表中存放的位置——段选择子就可以了，仔细想想系统启动时那条著名的 jmpi 0, 8 指令，这个段选择子就放在 ljmp 的参数中，实际上就 jmpi 0, 8 中的 8。
• （4）一旦将目标 TSS 中的全部寄存器映像扣在 CPU 上，就相当于切换到了目标进程的执行现场了，因为那里有目标进程停下时的 CS:EIP，所以此时就开始从目标进程停下时的那个 CS:EIP 处开始执行，现在目标进程就变成了当前进程，所以 TR 需要修改为目标 TSS 段在 GDT 表中的段描述符所在的位置，因为 TR 总是指向当前 TSS 段的段描述符所在的位置。

上面给出的这些工作都是一句长跳转指令 ljmp 段选择子:段内偏移，在段选择子指向的段描述符是 TSS 段时 CPU 解释执行的结果，所以基于 TSS 进行进程/线程切换的 switch_to 实际上就是一句 ljmp 指令：

#define switch_to(n) {
    struct{long a,b;} tmp;
    __asm__(
        "movw %%dx,%1"
        "ljmp %0" ::"m"(*&tmp.a), "m"(*&tmp.b), "d"(TSS(n)
    )
 }

#define FIRST_TSS_ENTRY 4

#define TSS(n) (((unsigned long) n) << 4) + (FIRST_TSS_ENTRY << 3))

GDT 表的结构如下图所示，所以第一个 TSS 表项，即 0 号进程的 TSS 表项在第 4 个位置上，4<<3，即 4 * 8，相当于 TSS 在 GDT 表中开始的位置，TSS（n）找到的是进程 n 的 TSS 位置，所以还要再加上 n<<4，即 n * 16，因为每个进程对应有 1 个 TSS 和 1 个 LDT，每个描述符的长度都是 8 个字节，所以是乘以 16，其中 LDT 的作用就是上面论述的那个映射表，关于这个表的详细论述要等到内存管理一章。TSS(n) = n * 16 + 4 * 8，得到就是进程 n（切换到的目标进程）的 TSS 选择子，将这个值放到 dx 寄存器中，并且又放置到结构体 tmp 中 32 位长整数 b 的前 16 位，现在 64 位 tmp 中的内容是前 32 位为空，这个 32 位数字是段内偏移，就是 jmpi 0, 8 中的 0；接下来的 16 位是 n * 16 + 4 * 8，这个数字是段选择子，就是 jmpi 0, 8 中的 8，再接下来的 16 位也为空。所以 swith_to 的核心实际上就是 ljmp 空, n*16+4*8，现在和前面给出的基于 TSS 的进程切换联系在一起了。

本次实验的内容

虽然用一条指令就能完成任务切换，但这指令的执行时间却很长，这条 ljmp 指令在实现任务切换时大概需要 200 多个时钟周期。而通过堆栈实现任务切换可能要更快，而且采用堆栈的切换还可以使用指令流水的并行优化技术，同时又使得 CPU 的设计变得简单。所以无论是 Linux 还是 Windows，进程/线程的切换都没有使用 Intel 提供的这种 TSS 切换手段，而都是通过堆栈实现的。

本次实践项目就是将 Linux 0.11 中采用的 TSS 切换部分去掉，取而代之的是基于堆栈的切换程序。具体的说，就是将 Linux 0.11 中的 switch_to 实现去掉，写成一段基于堆栈切换的代码。

在现在的 Linux 0.11 中，真正完成进程切换是依靠任务状态段（Task State Segment，简称 TSS）的切换来完成的。具体的说，在设计“Intel 架构”（即 x86 系统结构）时，每个任务（进程或线程）都对应一个独立的 TSS，TSS 就是内存中的一个结构体，里面包含了几乎所有的 CPU 寄存器的映像。有一个任务寄存器（Task Register，简称 TR）指向当前进程对应的 TSS 结构体，所谓的 TSS 切换就将 CPU 中几乎所有的寄存器都复制到 TR 指向的那个 TSS 结构体中保存起来，同时找到一个目标 TSS，即要切换到的下一个进程对应的 TSS，将其中存放的寄存器映像“扣在”CPU 上，就完成了执行现场的切换。

要实现基于内核栈的任务切换，主要完成如下三件工作：

• （1）重写 switch_to；
• （2）将重写的 switch_to 和 schedule() 函数接在一起；
• （3）修改现在的 fork()。

正式修改代码前小结

下面开始正式修改代码。其实主要就修改3个文件，但我不会按照每个文件一次性修改的顺序，而是按照实验逻辑，跳转修改，请保持清晰的逻辑。在截图的右下角有当前位置所在行数，注意观察不要修改错位置。

schedule 与 switch_to

目前 Linux 0.11 中工作的 schedule() 函数是首先找到下一个进程的数组位置 next，而这个 next 就是 GDT 中的 n，所以这个 next 是用来找到切换后目标 TSS 段的段描述符的，一旦获得了这个 next 值，直接调用上面剖析的那个宏展开 switch_to(next);就能完成如图 TSS 切换所示的切换了。

现在，我们不用 TSS 进行切换，而是采用切换内核栈的方式来完成进程切换，所以在新的 switch_to 中将用到当前进程的 PCB、目标进程的 PCB、当前进程的内核栈、目标进程的内核栈等信息。由于 Linux 0.11 进程的内核栈和该进程的 PCB 在同一页内存上（一块 4KB 大小的内存），其中 PCB 位于这页内存的低地址，栈位于这页内存的高地址；另外，由于当前进程的 PCB 是用一个全局变量 current 指向的，所以只要告诉新 switch_to()函数一个指向目标进程 PCB 的指针就可以了。同时还要将 next 也传递进去，虽然 TSS(next)不再需要了，但是 LDT(next)仍然是需要的，也就是说，现在每个进程不用有自己的 TSS 了，因为已经不采用 TSS 进程切换了，但是每个进程需要有自己的 LDT，地址分离地址还是必须要有的，而进程切换必然要涉及到 LDT 的切换。

综上所述，需要将目前的 schedule() 函数（在 kernel/sched.c 中）做稍许修改，即将下面的代码：

if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
    c = (*p)->counter, next = i;

//......

switch_to(next);

修改为：

if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
    c = (*p)->counter, next = i, pnext = *p;

//.......

switch_to(pnext,_LDT(next));

注意 pnext 是指向 pcb 的指针

struct tast_struct *pnext = &(init_task.task);

使用 switch_to 需要添加函数声明

extern long switch_to(struct task_struct *p, unsigned long address);

实现 switch_to

实现 switch_to 是本次实践项目中最重要的一部分。

由于要对内核栈进行精细的操作，所以需要用汇编代码来完成函数 switch_to 的编写。

这个函数依次主要完成如下功能：由于是 C 语言调用汇编，所以需要首先在汇编中处理栈帧，即处理 ebp 寄存器；接下来要取出表示下一个进程 PCB 的参数，并和 current 做一个比较，如果等于 current，则什么也不用做；如果不等于 current，就开始进程切换，依次完成 PCB 的切换、TSS 中的内核栈指针的重写、内核栈的切换、LDT 的切换以及 PC 指针（即 CS:EIP）的切换。

可以很明显的看出，该函数是基于TSS进行进程切换的(ljmp指令)，
现在要改写成基于堆栈(内核栈)切换的函数，就需要删除掉该语句，在include/linux/sched.h 文件，我们将它注释掉。

然后新的switch_to()函数将它作为一个系统调用函数，所以要将函数重写在汇编文件kernel/system_call.s:

.align 2
switch_to:
    //因为该汇编函数要在c语言中调用，所以要先在汇编中处理栈帧
	pushl %ebp
	movl %esp,%ebp
	pushl %ecx
	pushl %ebx
	pushl %eax

    //先得到目标进程的pcb，然后进行判断
    //如果目标进程的pcb(存放在ebp寄存器中) 等于   当前进程的pcb => 不需要进行切换，直接退出函数调用
    //如果目标进程的pcb(存放在ebp寄存器中) 不等于 当前进程的pcb => 需要进行切换，直接跳到下面去执行
	movl 8(%ebp),%ebx
	cmpl %ebx,current
	je 1f

    /** 执行到此处，就要进行真正的基于堆栈的进程切换了 */
	
        // PCB的切换
	movl %ebx,%eax
	xchgl %eax,current
	
	// TSS中内核栈指针的重写
	movl tss,%ecx
	addl $4096,%ebx
	movl %ebx,ESP0(%ecx)

	//切换内核栈
	movl %esp,KERNEL_STACK(%eax)
	movl 8(%ebp),%ebx
	movl KERNEL_STACK(%ebx),%esp

	//LDT的切换
	movl 12(%ebp),%ecx
	lldt %cx
	movl $0x17,%ecx
	mov %cx,%fs
	
	cmpl %eax,last_task_used_math
	jne 1f
	clts
	
	//在到子进程的内核栈开始工作了，接下来做的四次弹栈以及ret处理使用的都是子进程内核栈中的东西

1:	popl %eax
	popl %ebx
	popl %ecx
	popl %ebp
	ret

逐条解释基于堆栈切换的switch_to()函数四段核心代码:

// PCB的切换
movl %ebx,%eax
xchgl %eax,current

起始时eax寄存器保存了指向目标进程的指针，current指向了当前进程，
第一条指令执行完毕，使得ebx也指向了目标进程，
然后第二条指令开始执行，也就是将eax的值和current的值进行了交换，最终使得eax指向了当前进程，current就指向了目标进程(当前状态就发生了转移)

// TSS中内核栈指针的重写
movl tss,%ecx
addl $4096,%ebx
movl %ebx,ESP0(%ecx)

中断处理时需要寻找当前进程的内核栈，否则就不能从用户栈切到内核栈(中断处理没法完成)，
内核栈的寻找是借助当前进程TSS中存放的信息来完成的，(当然，当前进程的TSS还是通过TR寄存器在GDT全局描述符表中找到的)。

虽然此时不使用TSS进行进程切换了，但是Intel的中断处理机制还是要保持。
所以每个进程仍然需要一个TSS，操作系统需要有一个当前TSS。
这里采用的方案是让所有进程共用一个TSS(这里使用0号进程的TSS)，
因此需要定义一个全局指针变量tss(放在system_call.s中)来执行0号进程的TSS:
struct tss_struct * tss = &(init_task.task.tss);

此时唯一的tss的目的就是:在中断处理时，能够找到当前进程的内核栈的位置。

在内核栈指针重写指令中有宏定义ESP0，所以在上面需要提前定义好 ESP0 = 4，
(定义为4是因为TSS中内核栈指针ESP0就放在偏移为4的地方)
并且需要将: blocked=(33*16) => blocked=(33*16+4) 

• kernel/system_call.s 文件

  重写TSS中的内核栈指针

  ESP0 = 4
  KERNEL_STACK = 12
  
  state   = 0     # these are offsets into the task-struct.
  counter = 4
  priority = 8
  kernelstack = 12
  signal  = 16
  sigaction = 20      # MUST be 16 (=len of sigaction)
  blocked = (37*16)
  

  

• kernel/sched.c 文件

  struct tss_struct * tss = &(init_task.task.tss);
  

  

//切换内核栈
movl %esp,KERNEL_STACK(%eax)
movl 8(%ebp),%ebx
movl KERNEL_STACK(%ebx),%esp

第一行:将cpu寄存器esp的值，保存到当前进程pcb的eax寄存器中(保存当前进程执行信息)
第二行:获取目标进程的pcb放入ebx寄存器中
第三行:将ebx寄存器中的信息，也就是目标进程的信息，放入cpu寄存器esp中

但是之前的进程控制块(pcb)中是没有保存内核栈信息的寄存器的，所以需要在sched.h中的task_struct(也就是pcb)中添加kernelstack，
但是添加的位置就有讲究了，因为在某些汇编文件(主要是systen_call.s中)，有操作这个结构的硬编码，
一旦结构体信息改变，那这些硬编码也要跟着改变，
比如添加kernelstack在第一行，就需要改很多信息了，
但是添加到第四行就不需要改很多信息，所以这里将kernelstack放到第四行的位置：
struct task_struct {
/* these are hardcoded - don't touch */
	long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	long counter;
	long priority;
	/** add  kernelstack */
	long kernelstack;
    ...
}

改动位置及信息:
将
#define INIT_TASK \
/* state etc */	{ 0,15,15,\
/* signals */	0,{{},},0, \
...
改为:
#define INIT_TASK \
/* state etc */	{ 0,15,15, PAGE_SIZE+(long)&init_task,\
/* signals */	0,{{},},0, \
...

在执行上述切换内核栈的代码之前(也就是switch_to()函数前)，要设置栈的大小:KERNEL_STACK = 12
然后就执行上面的三行代码，就可以完成对内核栈的切换了。

• include/linux/sched.h 文件

  long kernelstack;
  

  

  由于这里将 PCB 结构体的定义改变了，所以在产生 0 号进程的 PCB 初始化时也要跟着一起变化， 需要修改 #define INIT_TASK，即在 PCB 的第四项中增加关于内核栈栈指针的初始化。代码如下：

  将
  #define INIT_TASK \
  /* state etc */	{ 0,15,15,\
  /* signals */	0,{{},},0, \
  ...
  改为:
  #define INIT_TASK \
  /* state etc */	{ 0,15,15, PAGE_SIZE+(long)&init_task,\
  /* signals */	0,{{},},0, \
  ...
  

  

• kernel/system_call.s

  KERNEL_STACK = 12
  

  

//LDT的切换
movl 12(%ebp),%ecx
lldt %cx
movl $0x17,%ecx
mov %cx,%fs

前两条语句的作用(切换LDT):
第一条:取出参数LDT(next)
第二条:完成对LDTR寄存器的修改

然后就是对PC指针(即CS:EIP)的切换:
后两条语句的含有就是重写设置段寄存器FS的值为0x17

补:FS的作用:通过FS操作系统才能访问进程的用户态内存。
这里LDT切换完成意味着切换到了新的用户态地址空间，所以需要重置FS。

修改fork()系统调用

现在需要将新建进程的用户栈、用户程序地址和其内核栈关联在一起，因为TSS没有做这样的关联fork()要求让父子进程共享用户代码、用户数据和用户堆栈虽然现在是使用内核栈完成任务的切换(基于堆栈的进程切换)，但是fork()的基本含义不应该发生变化。

综合分析:

修改以后的fork()要使得父子进程共享同一块内存空间、堆栈和数据代码块。

fork() 系统调用的代码放在 system_call.s 汇编文件中，先来看看已经写好的代码:

.align 2
sys_fork:
	call find_empty_process
	testl %eax,%eax
	js 1f
	push %gs
	pushl %esi
	pushl %edi
	pushl %ebp
	pushl %eax
	call copy_process//跳转到copy_process()函数
	addl $20,%esp
1:	ret

可以看到fork()函数的核心就是调用了 copy_process()，接下来去看copy_process()

copy_process()函数定义在kernel/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)
{
	struct task_struct *p;
	int i;
	struct file *f;

	p = (struct task_struct *) get_free_page();//用来完成申请一页内存空间作为子进程的PCB
	...

	/** 很容易看出来下面的部分就是基于tss进程切换机制时的代码，所以将此片段要注释掉

	p->tss.back_link = 0;
	p->tss.esp0 = PAGE_SIZE + (long) p;
	p->tss.ss0 = 0x10;
	...
	*/
	
	/** 然后这里要加上基于堆栈切换的代码(对frok的修改其实就是对子进程内核栈的初始化 */
	long *krnstack;
     krnstack = (long)(PAGE_SIZE +(long)p);//p指针加上页面大小就是子进程的内核栈位置，所以这句话就是krnstack指针指向子进程的内核栈

	//初始化内核栈(krnstack)中的内容:
	//下面的五句话可以完成对书上那个图(4.22)所示的关联效果(父子进程共有同一内存、堆栈和数据代码块)
	/*
	而且很容易可以看到，ss,esp,elags,cs,eip这些参数来自调用该函数的进程的内核栈中，
	也就是父进程的内核栈，所以下面的指令就是将父进程内核栈的前五个内容拷贝到了子进程的内核栈中
	*/
	*(--krnstack) = ss & 0xffff;
	*(--krnstack) = esp;
	*(--krnstack) = eflags;
	*(--krnstack) = cs & 0xffff;
	*(--krnstack) = eip;

    *(--krnstack) = ds & 0xffff;
    *(--krnstack) = es & 0xffff;
    *(--krnstack) = fs & 0xffff;
    *(--krnstack) = gs & 0xffff;
    *(--krnstack) = esi;
    *(--krnstack) = edi;
    *(--krnstack) = edx;
    
	*(--krnstack) = (long) first_return_kernel;//处理switch_to返回的位置

	*(--krnstack) = ebp;
	*(--krnstack) = ecx;
	*(--krnstack) = ebx;
	*(--krnstack) = 0;

	//把switch_to中要的东西存进去
	p->kernelstack = krnstack;
	...

• kernel/fork.c 文件

  注释tss进程切换片段

  

  添加代码

  	long *krnstack;
      krnstack = (long)(PAGE_SIZE +(long)p);
  
  	*(--krnstack) = ss & 0xffff;
  	*(--krnstack) = esp;
  	*(--krnstack) = eflags;
  	*(--krnstack) = cs & 0xffff;
  	*(--krnstack) = eip;
  
  	*(--krnstack) = ds & 0xffff;
      *(--krnstack) = es & 0xffff;
      *(--krnstack) = fs & 0xffff;
      *(--krnstack) = gs & 0xffff;
      *(--krnstack) = esi;
      *(--krnstack) = edi;
      *(--krnstack) = edx;
  
  	*(--krnstack) = (long) first_return_kernel;
  
  	*(--krnstack) = ebp;
  	*(--krnstack) = ecx;
  	*(--krnstack) = ebx;
  	*(--krnstack) = 0;
  
  	p->kernelstack = krnstack;
  

  

上面的first_return_kernel(系统调用)的工作:
"内核级线程切换五段论"中的最后一段切换，即完成用户栈和用户代码的切换，依靠的核心指令就是iret，当然在切换之前应该恢复一下执行现场，主要就是eax,ebx,ecx,edx,esi,gs,fs,es,ds这些寄存器的恢复，

要将first_return_kernel(属于系统调用，而且是一段汇编代码)写在kernel/system_call.s头文件里面：

首先需要将first_return_kernel设置在全局可见:

.globl switch_to,first_return_kernel

将具体的函数实现放在system_call.s头文件里面:

.align 2
first_return_kernel:
 popl %edx
 popl %edi
 popl %esi
 pop %gs
 pop %fs
 pop %es
 pop %ds
 iret

最后要记得是在 kernel/fork.c 文件里使用了 first_return_kernel 函数，所以要在该文件里添加外部函数声明

extern void first_return_kernel(void);

编译运行

天道酬勤

有些人不会写文章就不要发，参考的几篇全有错误，最后居然还能有运行成功的截图，你们编译怎么通过的？真牛！虽然我文章都是看的别人的，但我至少保证自己独立运行一遍，能保证运行通过。幸好最后碰到一位博主，看了他的文章自惭形秽。写的特别简洁但重点突出，有自己的理解。反观自己废话连篇，文章东拼西凑。

强烈推荐该博主哈工大-操作系统-HitOSlab-李治军-实验4-基于内核栈切换的进程切换_garbage_man的博客-CSDN博客

也可以看看这位博主的学习笔记，加深对线程了解操作系统学习笔记——用户级线程和核心级线程_garbage_man的博客-CSDN博客