实验四 内核线程管理-实验部分

目录

一、知识点

1.进程

1.1.进程定义

1.2.内存中的进程

1.3.进程的组成

1.4.进程的特点

1.5.进程与程序的联系

1.6.进程与程序的区别

2.进程控制块

2.1.进程控制块的使用

2.2.进程控制信息

2.3.进程控制块的组织

3.线程

3.1.为什么引入线程？

3.2.线程的基本概念

3.3.线程的优点和缺点

4.关于进程的3个实验

5.内核线程管理的目标

二、练习解答

1.内核线程管理实验解析

1.1.实验执行流程概述

1.2.设计关键数据结构 -- 进程控制块

1.2.1.进程ID

1.2.2.进程在调度过程中的状态信息

1.2.3.进程虚拟内存设置

1.2.4.进程切换

1.2.5.内核态进程上下文切换分析

1.2.6.用户态内核态中断栈切换分析

1.3.创建并执行内核线程

1.3.1.创建第0个内核线程idleproc

1.3.2.创建第1个内核线程initproc

1.3.3.调度并执行内核线程initproc

2.实验

2.1.练习1：分配并初始化一个进程控制块

2.2.练习2：为新创建的内核线程分配资源

2.3.练习3：阅读代码，理解proc_run函数和它调用的函数如何完成进程切换的

---

一、知识点

本章的知识点主要介绍进程相关的知识，除了介绍进程的主要知识点外，还介绍关于进程的3个实验。由于实验的内容比较多，不能一一全面介绍，因此在本文的第二章节介绍实验部分--内核线程管理。

1.进程

进程的知识点在我看来，他的内容分散，要点比较多。之所以是这样情况，我想进程的解释更多的偏向软件工程吧。

1.1.进程定义

进程是指具有一定独立功能的程序在一个数据集合上的一次动态执行过程。每一个进程都有它独立的main函数，独立的功能。每一个进程都在自己的内存空间执行，这个内存空间就是数据集合。每一个进程都在CPU上的一次动态执行，这个动态执行依靠的是进程在CPU上的并发执行。

1.2.内存中的进程

图1-1 内存中的进程

源代码经过编译链接形成可执行文件，这个可执行文件的每个汇编指令需要在CPU上进行一次动态执行，这个可执行文件需要存储到内存中。可执行程序存储在内存中的有代码段、数据段、堆栈段等。

1.3.进程的组成

进程包含了正在运行的一个程序的所有状态信息：

代码
数据
状态寄存器
        CPU状态CR0、指令指针IP
通用寄存器
        AX、BX、CX…
进程占用系统资源
        打开文件、已分配内存…

1.4.进程的特点

进程的特点：

动态性
    可动态地创建、结束进程
并发性
    进程可以被独立调度并占用处理机运行
独立性
    不同进程的工作不相互影响
制约性
    因访问共享数据/资源或进程间同步而产生制约

图1-2 进程执行的特点

1.5.进程与程序的联系

进程是操作系统处于执行状态程序的抽象
        程序 = 文件 (静态的可执行文件)
        进程 = 执行中的程序 = 程序 + 执行状态
同一个程序的多次执行过程对应为不同进程
        如命令“ls”的多次执行对应多个进程
进程执行需要的资源
        内存：保存代码和数据
        CPU：执行指令

1.6.进程与程序的区别

进程是动态的，程序是静态的
        程序是有序代码的集合
        进程是程序的执行，进程有核心态/用户态
进程是暂时的，程序的永久的
        进程是一个状态变化的过程
        程序可长久保存
进程与程序的组成不同
        进程的组成包括程序、数据和进程控制块

2.进程控制块

操作系统管理控制进程运行所用的信息集合。操作系统用PCB来描述进程的基本情况以及运行变化的过程；PCB是进程存在的唯一标志，每个进程都在操作系统中有一个对应的PCB。

2.1.进程控制块的使用

进程创建
        生成该进程的PCB
进程终止
        回收它的PCB
进程的组织管理
        通过对PCB的组织管理来实现

图2-1 进程控制块

在图2-1的进程控制块中，其中PID是进程的标志信息；PC/SP/其他集成器用于处理机现场保存；进程控制块的其他信息有堆栈、调度优先级、打开文件列表等。

2.2.进程控制信息

调度和状态信息
        调度进程和处理机使用情况
进程间通信信息
        进程间通信相关的各种标识
存储管理信息
        指向进程映像存储空间数据结构
进程所用资源
        进程使用的系统资源，如打开文件等
有关数据结构连接信息
        与PCB相关的进程队列

2.3.进程控制块的组织

进程控制块需要好的组织，以方便增加、删除、修改其中的进程控制块内容。有这样的几种方式对进程控制块进行组织，链表和索引表。

链表
    同一状态的进程其PCB成一链表，多个状态对应多个不同的链表
    各状态的进程形成不同的链表：就绪链表、阻塞链表
索引表
    同一状态的进程归入一个索引表（由索引指向PCB），多个状态对应多个不同的索引表
    各状态的进行形成不同的索引表：就绪索引表、阻塞索引表

图2-2 就绪列表VS索引列表

3.线程

3.1.为什么引入线程？

在许多的应用场景中，需要一类程序实体既能够并发执行，实体之间又能够共享数据。因此在进程内部增加一类实体，满足两个特性：实体之间可以并发执行；实体之间共享相同的地址空间。这个实体就是线程（Thread）。

3.2.线程的基本概念

线程是进程的一部分，描述指令流执行状态。它是进程中的指令执行流的最小单元，是CPU调度的基本单位。

进程的资源分配角色：进程由一组相关资源构成，包括地址空间（代码段、数据段）、打开的文件等各种资源
线程的处理机调度角色：线程描述在进程资源环境中的指令流执行状态。

图3-1 进程中的线程

图3-2 进程和线程的关系

3.3.线程的优点和缺点

线程的优点：

一个进程中可以同时存在多个线程
各个线程之间可以并发地执行
各个线程之间可以共享地址空间和文件等资源

线程的缺点：

一个线程崩溃，会导致其所属进程的所有线程崩溃

4.关于进程的3个实验

操作系统的进程管理设计复杂，涵盖的知识点和内容多，因此无法在一个实验中阐述清楚。对于进程的深入理解，涉及3个实验，1）内核线程管理；2）用户线程管理；3）进程调度。本报告重点阐述内核线程管理部分的实验，然而如果只是阐述内核线程管理部分，显然进程的体系阐述有所欠缺。因此在此之前重点介绍进程、进程控制块、线程的基本概念。

5.内核线程管理的目标

在未引入用户进程之前，从内核进程的整体流程视角出发，内核进程管理涉及如下目标：
1）内核线程的创建
2）内核线程的调度
3）内核线程的切换
4）内核线程的执行
内核线程的创建，主要解决如何为编译好的可执行程序创建进程控制块，以方便调度器调度。内核线程的调度器对若干个内核线程进行选择，选中其中一个线程，进行调度执行。当选中其中一个线程等待执行后，需要进行线程的上下文切换。进程上下文切换后，就需要进行线程的执行。
为了完成内核线程管理的目标，需要掌握实验的整体流程。除了整体流程，对于关键的数据结构（进程控制块）要进行设计，使得进程控制块能够满足进程的调度、切换、执行等场景。

二、练习解答

1.内核线程管理实验解析

根据第一章第4节的目标介绍，本节进行内核线程管理实验的详细解析。

1.1.实验执行流程概述

lab2和lab3完成了对内存的虚拟化，但整个控制流还是一条线串行执行。lab4将在此基础上进行CPU的虚拟化，即让ucore实现分时共享CPU，实现多条控制流能够并发执行。内核线程是一种特殊的进程，内核线程与用户进程的区别有两个：内核线程只运行在内核态而用户进程会在在用户态和内核态交替运行；所有内核线程直接使用共同的ucore内核内存空间，不需为每个内核线程维护单独的内存空间而用户进程需要维护各自的用户内存空间。从内存空间占用情况这个角度上看，我们可以把线程看作是一种共享内存空间的轻量级进程。在图1-7中，可以看出内核线程共享代码段、数据段、文件，但是他们具有独立的寄存器状态和栈，这些独立的寄存器状态和栈用来维持线程是最小的CPU执行单位。

图1-1 内核线程的概念

为了实现内核线程，需要设计管理线程的数据结构，即进程控制块（在这里也可叫做线程控制块）。如果要让内核线程运行，我们首先要创建内核线程对应的进程控制块，还需把这些进程控制块通过链表连在一起，便于随时进行插入，删除和查找操作等进程管理事务。这个链表就是进程控制块链表。然后在通过调度器（scheduler）来让不同的内核线程在不同的时间段占用CPU执行，实现对CPU的分时共享。
那lab4中是如何一步一步实现这个过程的呢？我们还是从lab4/kern/init/init.c中的kern_init函数入手分析。在kern_init函数中，当完成虚拟内存的初始化工作后，就调用了proc_init函数，这个函数完成了idleproc内核线程和initproc内核线程的创建或复制工作，这也是本次实验要完成的练习。idleproc内核线程的工作就是不停地查询，看是否有其他内核线程可以执行了，如果有，马上让调度器选择那个内核线程执行（请参考cpu_idle函数的实现）。所以idleproc内核线程是在ucore操作系统没有其他内核线程可执行的情况下才会被调用。接着就是调用kernel_thread函数来创建initproc内核线程。initproc内核线程的工作就是显示“HelloWorld”，表明自己存在且能正常工作了。在这里initproc是通过kernel_thread函数来创建user_main用户进程，用户进程在调度后显示“HelloWorld”，有关用户进程的管理放在实验5进行详细说明。
调度器会在特定的调度点上执行调度，完成进程切换。在lab4中，这个调度点就一处，即在cpu_idle函数中，此函数如果发现当前进程（也就是idleproc）的need_resched置为1（在初始化idleproc的进程控制块时就置为1了），则调用schedule函数，完成进程调度和进程切换。进程调度的过程其实比较简单，就是在进程控制块链表中查找到一个“合适”的内核线程，所谓“合适”就是指内核线程处于“PROC_RUNNABLE”状态。在接下来的switch_to函数(在后续有详细分析，有一定难度，需深入了解一下)完成具体的进程切换过程。一旦切换成功，那么initproc内核线程就可以通过显示字符串来表明本次实验成功。
接下来将主要介绍了进程创建所需的重要数据结构--进程控制块proc_struct，以及ucore创建并执行内核线程idleproc和initproc的两种不同方式，特别是创建initproc的方式将被延续到实验五中，扩展为创建用户进程的主要方式。另外，还初步涉及了进程调度（实验六涉及并会扩展）和进程切换内容。

1.2.设计关键数据结构 -- 进程控制块

在实验四中，进程管理信息用struct proc_struct表示，在kern/process/proc.h中定义如下：

struct proc_struct {
    enum proc_state state;                      // Process state
    int pid;                                    // Process ID
    int runs;                                   // the running times of Proces
    uintptr_t kstack;                           // Process kernel stack
    volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
    struct proc_struct *parent;                 // the parent process
    struct mm_struct *mm;                       // Process's memory management field
    struct context context;                     // Switch here to run process
    struct trapframe *tf;                       // Trap frame for current interrupt
    uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
    uint32_t flags;                             // Process flag
    char name[PROC_NAME_LEN + 1];               // Process name
    list_entry_t list_link;                     // Process link list 
    list_entry_t hash_link;                     // Process hash list
};

1.2.1.进程ID

pid：代表该进程的唯一ID

name[15+1]：代表进程的名字

图1-2 进程的PID

1.2.2.进程在调度过程中的状态信息

state：进程状态，睡眠状态，运行状态、僵尸状态

runs：进程被调度的次数记录

need_resched：进程需要被调度的标志

flags：进程标志位（预留）

图1-3 进程在调度过程中的状态信息

1.2.3.进程虚拟内存设置

kstack：每个线程都有一个内核栈，并且位于内核地址空间的不同位置。对于内核线程，该栈就是运行时的程序使用的栈；而对于普通进程，该栈是发生特权级改变的时候使保存被打断的硬件信息用的栈。uCore在创建进程时分配了2个连续的物理页（参见memlayout.h中KSTACKSIZE的定义）作为内核栈的空间。这个栈很小，所以内核中的代码应该尽可能的紧凑，并且避免在栈上分配大的数据结构，以免栈溢出，导致系统崩溃。kstack记录了分配给该进程/线程的内核栈的位置。主要作用有以下几点。1）首先，当内核准备从一个进程切换到另一个的时候，需要根据kstack的值正确的设置好tss（可以回顾一下在实验一中讲述的tss在中断处理过程中的作用），以便在进程切换以后再发生中断时能够使用正确的栈。2）其次，内核栈位于内核地址空间，并且是不共享的（每个线程都拥有自己的内核栈），因此不受到mm的管理，当进程退出的时候，内核能够根据kstack的值快速定位栈的位置并进行回收。

uCore的这种内核栈的设计借鉴的是linux的方法（但由于内存管理实现的差异，它实现的远不如linux的灵活），它使得每个线程的内核栈在不同的位置，这样从某种程度上方便调试，但同时也使得内核对栈溢出变得十分不敏感，因为一旦发生溢出，它极可能污染内核中其它的数据使得内核崩溃。如果能够通过页表，将所有进程的内核栈映射到固定的地址上去，能够避免这种问题，但又会使得进程切换过程中对栈的修改变得相当繁琐。感兴趣的同学可以参考linuxkernel的代码对此进行尝试。

cr3：cr3保存页表的物理地址，目的就是进程切换的时候方便直接使用lcr3实现页表切换，避免每次都根据mm来计算cr3。mm数据结构是用来实现用户空间的虚存管理的，但是内核线程没有用户空间，它执行的只是内核中的一小段代码（通常是一小段函数），所以它没有mm结构，也就是NULL。当某个进程是一个普通用户态进程的时候，PCB中的cr3就是mm中页表（pgdir）的物理地址；而当它是内核线程的时候，cr3等于boot_cr3。而boot_cr3指向了uCore启动时建立好的饿内核虚拟空间的页目录表首地址。

mm：内存管理的信息，包括内存映射列表、页表指针等。mm成员变量在lab3中用于虚存管理。但在实际OS中，内核线程常驻内存，不需要考虑swappage问题，在lab5中涉及到了用户进程，才考虑进程用户内存空间的swappage问题，mm才会发挥作用。所以在lab4中mm对于内核线程就没有用了，这样内核线程的proc_struct的成员变量*mm=0是合理的。mm里有个很重要的项pgdir，记录的是该进程使用的一级页表的物理地址。由于*mm=NULL，所以在proc_struct数据结构中需要有一个代替pgdir项来记录页表起始地址，这就是proc_struct数据结构中的cr3成员变量。

图1-4 进程虚拟内存设置

[进程的内存管理模块]

图1-5 进程的内存管理模块

该部分的内容具体的介绍在Lab3 虚拟内存管理中，在内核状态，不需要进程swap page，因此该结构无用。但是在用户进程管理中，需要进行swap page，此时就需要记录用户进程的可执行代码是在内存中还是在磁盘上。

1.2.4.进程切换

进程的切换是通过下图中进程控制块中的context结构体和trapframe结构体实现的。其中context完成在内核态进程的上下文切换，而trapframe通过中断返回的方式从内核态切换到用户态。

图1-6 进程切换

context：进程的上下文，用于进程切换（参见switch.S）。在uCore中，所有的进程在内核中也是相对独立的（例如独立的内核堆栈以及上下文等等）。使用context保存寄存器的目的就在于在内核态中能够进行上下文之间的切换。实际利用context进行上下文切换的函数是在kern/process/switch.S中定义switch_to。

内核态的进程上下文切换，由调度器触发，保存的是from的context信息，恢复的是to的context信息。这样完成一个进程的forkret(proc->tf)调用，切换到另外一个进程的forkret(proc->tf)调用。进程的forkret函数调用，与普通的函数调用区别在于不会返回函数调用栈。

图1-7 进程控制块中context

tf：中断帧的指针，总是指向内核栈的某个位置：当进程从用户空间跳到内核空间时，中断帧记录了进程在被中断前的状态。当内核需要跳回用户空间时，需要调整中断帧以恢复让进程继续执行的各寄存器值。除此之外，uCore内核允许嵌套中断。因此为了保证嵌套中断发生时tf总是能够指向当前的trapframe，uCore在内核栈上维护了tf的链，可以参考trap.c::trap。

在本实验中，内核线程idle_proc和初始化线程init_proc完成context上下文切换后，假设idle_proc向init_proc切换，此时CPU的有关寄存器恢复成to.context寄存器了。倒数第二条汇编指令“pushl 0(%eax)”其实把context中保存的下一个进程要执行的指令地址context.eip放到了堆栈顶（相当于将to.context.eip放入栈的函数返回值中），这样接下来执行最后一条指令“ret”时，会把栈顶的内容赋值给EIP寄存器，这样就切换到下一个进程执行了，即当前进程已经是下一个进程了，并开始执行了。

图1-7 进程控制块中trapframe

用户态应用程序主动触发中断或者被其他中断打扰，此时由CPU触发。发生的时机就是中断发生的时刻，保存的内容是下一条需要执行的指令位置CS\IP等，当前时刻的逻辑或者算术计算的通用状态（通用寄存器EAX,EBX,ECX等），保存的位置是内核堆栈中。

1.2.5.内核态进程上下文切换分析

参考《ucore内核态进程上下文切换关键代码分析》

1.2.6.用户态内核态中断栈切换分析

参考《X86中断栈执行过程分析》。

1.3.创建并执行内核线程

建立进程控制块（proc.c中的alloc_proc函数），现在就可以通过进程控制块来创建具体的进程/线程了。首先，考虑最简单的内核线程，它通常只是内核中的一小段代码或者函数，没有自己的“专属”空间。这是由于uCore OS启动后，已经对整个内核空间进行了管理，通过设置页表建立了内核虚拟空间（即boot_cr3指向的二级页表描述的空间）。所以uCore OS内核中的所有线程都不需要再建立各自的页表，只需共享这个内核虚拟空间就可以访问整个物理内存了。从这个角度看，内核线程被uCore OS内核这个大“内核进程”所管理。

1.3.1.创建第0个内核线程idleproc

在init.c::kern_init函数调用了proc.c::proc_init函数。proc_init函数启动了创建内核线程的步骤。首先当前的执行上下文（从kern_init启动至今）就可以看成是uCore内核（也可以看成是内核进程）中一个内核线程的上下文。为此，uCore通过给当前执行的上下文分配一个进程控制块以及对它进行相应的初始化，将其打造成第0个内核线程--idleproc。具体步骤如下：

首先调用alloc_proc函数来通过kmalloc函数获得proc_struct结构的一块内存块，作为第0个进程控制块。并把proc进行初始化（即把proc_struct中的各个成员变量清零）。但有些成员变量设置了特殊的值，比如：

proc->state = PROC_UNINIT; 设置进程为“初始”态
proc->pid = -1; 设置进程pid的未初始化值
proc->cr3 = boot_cr3; 使用内核页目录表的基址
...

上述三条语句中，第一条设置了进程的状态为“初始”态，这表示进程已经“出生”了，正在获取资源茁壮成长中；第二条语句设置了进程的pid为-1，这表示进程的“身份证号”还没有办好；第三条语句表明由于该内核线程在内核中运行，故采用为uCore内核已经建立的页表，即设置在uCore内核页表的起始地址boot_cr3。后续实验中可进一步看成所有内核线程的内核虚拟地址空间（也包括物理地址空间）是相同的。既然内核线程共用一个映射内核空间的页表，这表示内核空间对所有内核线程都是“可见”的，所以更加精确地说，这些内核线程都应该是从属于同一个唯一的“大内核进程”--uCore内核。

接下来，proc_init函数对idleproc内核线程进一步初始化：

idleproc->pid = 0;
idleproc->state = PROC_RUNNABLE;
idleproc->kstack = (uintptr_t)bootstack;
idleproc->need_resched = 1;
set_proc_name(idleproc, "idle");

需要注意前4条语句。第一条语句给了idleproc合法的身份证号--0，这名正言顺地表明了idleproc是第0个内核线程。通常可以通过pid的赋值来表示线程的创建和身份的确定。第二条语句改变了idleproc的状态，使得它从“出生”转到了“准备工作”，就差uCore调度它执行了。第三条语句设置了idleproc所使用的内核栈的起始地址。需要注意以后的其他线程的内核栈需要通过分配获得，因为uCore启动时设置的内核栈直接分配给idleproc使用了。第四条很重要，因为uCore希望当前CPU应该做更有用的工作，而不是运行idleproc这个“无所事事”的内核线程，所以把idleproc->need_resched设置为“1”，结合idleproc的执行主体--cpu_idle函数的实现，可以清楚看出如果当前idleproc在执行，则只要此标志设置成1，马上就调用schedule函数要求调度器切换其他进程执行。

1.3.2.创建第1个内核线程initproc

第0个内核线程主要工作是完成内核中各个子系统的初始化，然后就通过执行cpu_ilde函数开始过退休生活了。所以uCore接下来还需要创建其他进程来完成各种工作，但idleproc内核子线程自己不想做，于是就通过调用kernel_thread函数创建了一个内核线程init_main。在实验四中，这个子内核线程的工作就是输出一些字符串，然后就返回了。但在后续的实验中，init_main的工作就是创建特定的其他内核线程或者用户进程（实验五涉及）。下面我们来分析一下创建内核线程的函数kernel_thread：

int kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags)
{
	struct trapframe tf;
	memset(&tf, 0, sizeof(struct trapframe));
	tf.tf_cs = KERNEL_CS;
	tf.tf_ds = tf_struct.tf_es = tf_struct.tf_ss = KERNEL_DS;
	tf.tf_regs.reg_ebx = (uint32_t)fn;
	tf.tf_regs.reg_edx = (uint32_t)arg;
	tf.tf_eip = (uint32_t)kernel_thread_entry;
	return do_fork(clone_flags | CLONE_VM, 0, &tf);
}

注意，kernel_thread函数采用了局部变量tf来放置保存内核线程的临时中断帧，并把中断帧的指针传递给do_fork函数，而do_fork函数会调用copy_thread函数来在新创建的进程内核栈上专门给进程的中断帧分配一块空间，分配空间指的是下面的指令。

proc.c::copy_thread(){
proc->tf = (struct trapframe *)(proc->kstack + KSTACKSIZE) - 1;
}

给中断帧分配完空间后，就需要构造新进程的中断帧，具体过程是：首先给tf进行清零初始化，并设置中断帧的代码段和数据段为内核空间的段，这实际上说明了initproc内核线程在内核空间中执行。而initproc内核线程从哪里开始执行呢？tf.tf_eip指出了就是kernel_thread_entry（位于kern/process/entry.S中），构造新进程的中断帧代码具体如下：

int
kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {
    struct trapframe tf;
    memset(&tf, 0, sizeof(struct trapframe));
    tf.tf_cs = KERNEL_CS;
    tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;
    tf.tf_regs.reg_ebx = (uint32_t)fn;
    tf.tf_regs.reg_edx = (uint32_t)arg;
    tf.tf_eip = (uint32_t)kernel_thread_entry;
    return do_fork(clone_flags | CLONE_VM, 0, &tf);
}

kernel_thread_entry是entry.S中实现的汇编函数，它做的事情很简单：

kernel_thread_entry: # void kernel_thread(void)
pushl %edx # push arg
call *%ebx # call fn
pushl %eax # save the return value of fn(arg)
call do_exit # call do_exit to terminate current thread

从上可以看出，kernel_thread_entry函数主要为内核线程的主体fn函数做了一个准备开始和结束运行的“壳”，并把函数fn的参数arg（保存在edx寄存器中）压栈，然后调用fn函数，把函数返回值eax寄存器内容压栈，调用do_exit函数退出线程执行。

do_fork是创建线程的主要函数。下面我们来分析一下do_fork函数的实现（练习2）。do_fork函数主要做了以下6件事情：

• 分配并初始化进程控制块（alloc_proc函数）；
• 分配并初始化内核栈（setup_stack函数）；
• 根据clone_flag标志复制或共享进程内存管理结构（copy_mm函数）；
• 设置进程在内核（将来也包括用户态）正常运行和调度所需的中断帧和执行上下文（copy_thread函数）；
• 把设置好的进程控制块放入hash_list和proc_list两个全局进程链表中；
• 自此，进程已经准备好执行了，把进程状态设置为“就绪”态；
• 设置返回码为子进程的id号。

这里需要注意的是，如果上述前3步执行没有成功，则需要做对应的出错处理，把相关已经占有的内存释放掉。copy_mm函数目前只是把current->mm设置为NULL，这是由于目前在实验四中只能创建内核线程，proc->mm描述的是进程用户态空间的情况，所以目前mm还用不上。copy_thread函数做的事情比较多，代码如下：

static void
copy_thread(struct proc_struct *proc, uintptr_t esp, struct trapframe *tf) {
	//在内核堆栈的顶部设置中断帧大小的一块栈空间
	proc->tf = (struct trapframe *)(proc->kstack + KSTACKSIZE) - 1;
	*(proc->tf) = *tf; //拷贝在kernel_thread函数建立的临时中断帧的初始值
	proc->tf->tf_regs.reg_eax = 0;
	//设置子进程/线程执行完do_fork后的返回值
	proc->tf->tf_esp = esp; //设置中断帧中的栈指针esp
	proc->tf->tf_eflags |= FL_IF; //使能中断
	proc->context.eip = (uintptr_t)forkret;
	proc->context.esp = (uintptr_t)(proc->tf);
}

此函数首先在内核堆栈的顶部设置中断帧大小的一块栈空间，并在此空间中拷贝在kernel_thread函数建立的临时中断帧的初始值，并进一步设置中断帧中的栈指针esp和标志寄存器eflags，特别是eflags设置了FL_IF标志，这表示此内核线程在执行过程中，能响应中断，打断当前的执行。执行到这步后，此进程的中断帧就建立好了，对于initproc而言，它的中断帧如下所示：

//所在地址位置
initproc->tf= (proc->kstack+KSTACKSIZE) – sizeof (struct trapframe);
//具体内容
initproc->tf.tf_cs = KERNEL_CS;
initproc->tf.tf_ds = initproc->tf.tf_es = initproc->tf.tf_ss = KERNEL_DS;
initproc->tf.tf_regs.reg_ebx = (uint32_t)init_main;
initproc->tf.tf_regs.reg_edx = (uint32_t) ADDRESS of "Helloworld!!";
initproc->tf.tf_eip = (uint32_t)kernel_thread_entry;
initproc->tf.tf_regs.reg_eax = 0;
initproc->tf.tf_esp = esp;
initproc->tf.tf_eflags |= FL_IF;

设置好中断帧后，最后就是设置initproc的进程上下文，（processcontext，也称执行现场）了。只有设置好执行现场后，一旦uCore调度器选择了initproc执行，就需要根据initproc->context中保存的执行现场来恢复initproc的执行。这里设置了initproc的执行现场中主要的两个信息：上次停止执行时的下一条指令地址context.eip和上次停止执行时的堆栈地址context.esp。其实initproc还没有执行过，所以这其实就是initproc实际执行的第一条指令地址和堆栈指针。可以看出，由于initproc的中断帧占用了实际给initproc分配的栈空间的顶部，所以initproc就只能把栈顶指针context.esp设置在initproc的中断帧的起始位置。根据context.eip的赋值，可以知道initproc实际开始执行的地方在forkret函数（主要完成do_fork函数返回的处理工作）处。至此，initproc内核线程已经做好准备执行了。

1.3.3.调度并执行内核线程initproc

在uCore执行完proc_init函数后，就创建好了两个内核线程：idleproc和initproc，这时uCore当前的执行现场就是idleproc，等到执行到init函数的最后一个函数cpu_idle之前，uCore的所有初始化工作就结束了，idleproc将通过执行cpu_idle函数让出CPU，给其它内核线程执行，具体过程如下：

void
cpu_idle(void) {
	while (1) {
		if (current->need_resched) {
			schedule();
……

首先，判断当前内核线程idleproc的need_resched是否不为0，回顾前面“创建第一个内核线程idleproc”中的描述，proc_init函数在初始化idleproc中，就把idleproc->need_resched置为1了，所以会马上调用schedule函数找其他处于“就绪”态的进程执行。

uCore在实验四中只实现了一个最简单的FIFO调度器，其核心就是schedule函数。它的执行逻辑很简单：

设置当前内核线程current->need_resched为0；在proc_list队列中查找下一个处于“就绪”态的线程或进程next；找到这样的进程后，就调用proc_run函数，保存当前进程current的执行现场（进程上下文），恢复新进程的执行现场，完成进程切换。

至此，新的进程next就开始执行了。由于在proc10中只有两个内核线程，且idleproc要让出CPU给initproc执行，我们可以看到schedule函数通过查找proc_list进程队列，只能找到一个处于“就绪”态的initproc内核线程。并通过proc_run和进一步的switch_to函数完成两个执行现场的切换，具体流程如下：

• 让current指向next内核线程initproc；
• 设置任务状态段ts中特权态0下的栈顶指针esp0为next内核线程initproc的内核栈的栈顶，即next->kstack+KSTACKSIZE；
• 设置CR3寄存器的值为next内核线程initproc的页目录表起始地址next->cr3，这实际上是完成进程间的页表切换；
• 由switch_to函数完成具体的两个线程的执行现场切换，即切换各个寄存器，当switch_to函数执行完“ret”指令后，就切换到initproc执行了。

以上的4个流程代码如下：

proc_run(struct proc_struct *proc) {
    if (proc != current) {
        bool intr_flag;
        struct proc_struct *prev = current, *next = proc;
        local_intr_save(intr_flag);
        {
            current = proc;
            load_esp0(next->kstack + KSTACKSIZE);
            lcr3(next->cr3);
            switch_to(&(prev->context), &(next->context));
        }
        local_intr_restore(intr_flag);
    }
}

注意，在第二步设置任务状态段ts中特权态0下的栈顶指针esp0的目的是建立好内核线程或将来用户线程在执行特权态切换（从特权态0<-->特权态3，或从特权态3<-->特权态3）时能够正确定位处于特权态0时进程的内核栈的栈顶，而这个栈顶其实放了一个trapframe结构的内存空间。如果是在特权态3发生了中断/异常/系统调用，则CPU会从特权态3-->特权态0，且CPU从此栈顶（当前被打断进程的内核栈顶）开始压栈来保存被中断/异常/系统调用打断的用户态执行现场；如果是在特权态0发生了中断/异常/系统调用，则CPU会从从当前内核栈指针esp所指的位置开始压栈保存被中断/异常/系统调用打断的内核态执行现场。反之，当执行完对中断/异常/系统调用打断的处理后，最后会执行一个“iret”指令。在执行此指令之前，CPU的当前栈指针esp一定指向上次产生中断/异常/系统调用时CPU保存的被打断的指令地址CS和EIP，“iret”指令会根据ESP所指的保存的址CS和EIP恢复到上次被打断的地方继续执行在页表设置方面，由于idleproc和initproc都是共用一个内核页表boot_cr3，所以此时第三步其实没用，但考虑到以后的进程有各自的页表，其起始地址各不相同，只有完成页表切换，才能确保新的进程能够正常执行。

2.实验

2.1.练习1：分配并初始化一个进程控制块

alloc_proc函数（位于kern/process/proc.c中）负责分配并返回一个新的struct proc_struct结构，用于存储新建立的内核线程的管理信息。ucore需要对这个结构进行最基本的初始化，你需要完成这个初始化过程。

【提示】在alloc_proc函数的实现中，需要初始化的proc_struct结构中的成员变量至少包括：state/pid/runs/kstack/need_resched/parent/mm/context/tf/cr3/flags/name。

//由于是最简单的初始化，因此proc_struct初始化成最简单的状态。这种状态不能够被调度器调度，但是对内存进行了基本的初始化。
static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
    //LAB4:EXERCISE1 YOUR CODE
    /*
     * below fields in proc_struct need to be initialized
     *       enum proc_state state;                      // Process state
     *       int pid;                                    // Process ID
     *       int runs;                                   // the running times of Proces
     *       uintptr_t kstack;                           // Process kernel stack
     *       volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
     *       struct proc_struct *parent;                 // the parent process
     *       struct mm_struct *mm;                       // Process's memory management field
     *       struct context context;                     // Switch here to run process
     *       struct trapframe *tf;                       // Trap frame for current interrupt
     *       uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
     *       uint32_t flags;                             // Process flag
     *       char name[PROC_NAME_LEN + 1];               // Process name
     */
     	proc->state = PROC_UNINIT;
		proc->pid = -1;
		proc->runs = 0;
		proc->kstack = 0;
		proc->need_resched = 0;
		proc->parent = NULL;
		proc->mm = NULL;
		memset(&proc->context,0,sizeof(struct context));
		proc->tf = NULL;
		proc->cr3 = boot_cr3;
		proc->flags = 0;
		memset(&proc->name,0,sizeof(sizeof(char)*PROC_NAME_LEN));
		list_init(&proc->list_link);
		list_init(&proc->hash_link);
    }
    return proc;
}

请说明proc_struct中struct context context和struct trapframe *tf成员变量含义和在本实验中的作用是啥？（提示通过看代码和编程调试可以判断出来）？

struct context context用于内核状态完成进程的切换，这种切换采用的是改变栈顶元素和ret函数返回实现，具体参考第二章的1.2.5节内核态进程上下文切换分析。

struct trapframe *tf用于内核状态的中断执行完成后返回到之前的状态（存在两种，一种是内核状态，另一种是用户状态）。这种中断返回采用的是tf压栈（存在两种，一种是CPU自动压栈和切换栈，一种是内核程序压栈）和iret中断返回实现，具体参考1.2.6用户态内核态中断栈切换分析。

2.2.练习2：为新创建的内核线程分配资源

创建一个内核线程需要分配和设置好很多资源。kernel_thread函数通过调用do_fork函数完成具体内核线程的创建工作。do_kernel函数会调用alloc_proc函数来分配并初始化一个进程控制块，但alloc_proc只是找到了一小块内存用以记录进程的必要信息，并没有实际分配这些资源。ucore一般通过do_fork实际创建新的内核线程。do_fork的作用是，创建当前内核线程的一个副本，它们的执行上下文、代码、数据都一样，但是存储位置不同。在这个过程中，需要给新内核线程分配资源，并且复制原进程的状态。你需要完成在kern/process/proc.c中的do_fork函数中的处理过程。它的大致执行步骤包括：

1. 调用alloc_proc， 首先获得一块用户信息块。
2. 为进程分配一个内核栈。
3. 复制原进程的内存管理信息到新进程（ 但内核线程不必做此事）
4. 复制原进程上下文到新进程
5. 将新进程添加到进程列表
6. 唤醒新进程
7. 返回新进程号

int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    int ret = -E_NO_FREE_PROC;
    struct proc_struct *proc;
    if (nr_process >= MAX_PROCESS) {
        goto fork_out;
    }
    ret = -E_NO_MEM;
    //LAB4:EXERCISE2 YOUR CODE
    /*
     * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   alloc_proc:   create a proc struct and init fields (lab4:exercise1)
     *   setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
     *   copy_mm:      process "proc" duplicate OR share process "current"'s mm according clone_flags
     *                 if clone_flags & CLONE_VM, then "share" ; else "duplicate"
     *   copy_thread:  setup the trapframe on the  process's kernel stack top and
     *                 setup the kernel entry point and stack of process
     *   hash_proc:    add proc into proc hash_list
     *   get_pid:      alloc a unique pid for process
     *   wakeup_proc:  set proc->state = PROC_RUNNABLE
     * VARIABLES:
     *   proc_list:    the process set's list
     *   nr_process:   the number of process set
     */
 
    //    1. call alloc_proc to allocate a proc_struct
    proc = alloc_proc();
	if(NULL==proc)
	{
		goto fork_out;
	}
	//    2. call setup_kstack to allocate a kernel stack for child process
	if(setup_kstack(proc)!=0)
	{
		goto bad_fork_cleanup_kstack;
	}
    //    3. call copy_mm to dup OR share mm according clone_flag
    if(copy_mm(clone_flags,proc)!=0)
	{
		goto bad_fork_cleanup_proc;
	}
    //    4. call copy_thread to setup tf & context in proc_struct
    copy_thread(proc,stack,tf);
	//    5.1 set process unique id
	proc->parent = current;
	proc->pid = get_pid();
	//	5.2. insert proc_struct into hash_list && proc_list
	bool intr_flag;
	local_intr_save(intr_flag);
	{
		hash_proc(proc);
		list_add(&proc_list, &proc->list_link);
	}
	local_intr_restore(intr_flag);
	//    6. call wakeup_proc to make the new child process RUNNABLE
	wakeup_proc(proc);
	ret = proc->pid;
	
fork_out:
    return ret;
 
bad_fork_cleanup_kstack:
    put_kstack(proc);
bad_fork_cleanup_proc:
    kfree(proc);
    goto fork_out;
}

请说明ucore是否做到给每个新fork的线程一个唯一的id？请说明你的分析和理由。

// get_pid - alloc a unique pid for process
static int
get_pid(void) {
    static_assert(MAX_PID > MAX_PROCESS);
    struct proc_struct *proc;
    list_entry_t *list = &proc_list, *le;
    static int next_safe = MAX_PID, last_pid = MAX_PID;
    if (++ last_pid >= MAX_PID) {
        last_pid = 1;
        goto inside;
    }
    if (last_pid >= next_safe) {
    inside:
        next_safe = MAX_PID;
    repeat:
        le = list;
        while ((le = list_next(le)) != list) {
            proc = le2proc(le, list_link);
            if (proc->pid == last_pid) {
                if (++ last_pid >= next_safe) {
                    if (last_pid >= MAX_PID) {
                        last_pid = 1;
                    }
                    next_safe = MAX_PID;
                    goto repeat;
                }
            }
            else if (proc->pid > last_pid && next_safe > proc->pid) {
                next_safe = proc->pid;
            }
        }
    }
    return last_pid;
}

每次执行get_pid()函数，如果last_pid

每次执行get_pid()函数，如果last_pid>=next_safe，next_safe = MAX_PID，此时遍历整个proc_list，找到那个不在proc_list中的pid。这是怎么做到的？如果当前的proc->pid == last_pid，那么这个last_pid不是一个合适的pid，需要扩大next_safe = MAX_PID，继续重复搜索，保证last_pid与proc_list中每个pid都不重复（重复后会重新搜索）。如果proc->pid < last_pid，继续循环搜索。如果proc->pid > last_pid && next_safe > proc->pid可以变更成小的区间搜索[last_pid,next_safe=proc->pid]，这样简化搜索空间。这种搜索的算法，由于是暴力搜索，只要存在一个可用的pid，那么就能获得一个与proc_list中不一样的pid。

2.3.练习3：阅读代码，理解proc_run函数和它调用的函数如何完成进程切换的

请在实验报告中简要说明你对proc_run函数的分析。

详细见1.3.3节的内容，了解到基本的栈和页表切换情况。之后，详细参考1.2.5和1.2.6关于context的切换与中断帧的返回。

在本实验的执行过程中， 创建且运行了几个内核线程？两个，idleproc和initproc内核线程。

语句local_intr_save(intr_flag);....local_intr_restore(intr_flag);在这里有何作用？请说明理由。关闭CPU的中断响应，从而完成进行进程的切换，然后开启CPU的中断响应。这里采用原子操作保证进程切换的一次执行。