- 多道程序设计和进程的引出

早期计算机运行程序时只能一次运行一个程序，而且所有的系统资源（如CPU、内存和IO设备等）都由该程序单独使用，在该程序运行完之前其他程序无法运行，这就是单道程序设计。

单道程序系统的内存中除了操作系统这个内核程序之外，只有一个用户程序在内存中。其缺点时浪费资源且程序运行效率低（因为是程序间串行）。

在单道程序系统的内存中，只存放了1个用户程序的程序段（即程序的代码、机器指令，位于内存的低地址区域）和数据段（如变量、常量等，也包括栈数据，位于高地址区域）。CPU的控制器取指令就是从程序段取指令，读取数据是从数据段取到的数据。

 

多道程序设计允许内存中存放多道程序，它们在操作系统的调度下交替的在CPU上运行从而实现程序的并发，提高了程序执行的效率和资源利用率。

此时产生了一个问题，由于计算机中有多道程序，因此内存中保存了多个程序的程序段和数据段，操作系统如何才能找到各个程序程序段和数据段的位置？计算机里的设备分配给不同的程序，如何知道哪些设备被哪些程序占用？CPU运行一个程序A运行到一半就切换到另一个程序，程序A的CPU环境或者说它的运行状态和进度存放到哪里？

为此，操作系统为每一个要投入运行的程序设置了一个PCB（进程控制块）的结构来保存上述的程序控制信息。由此，也引出了进程的概念，多道程序设计中程序的并发执行就是通过进程实现的。

 

- 进程概念

进程是程序的一次执行过程，是系统进行资源分配和调度的单位。

 

进程和程序的区别在于(从动态性、异步性和独立性来答)：

1. 程序是静态的，本质是一段保存在磁盘的代码或者可执行文件；进程是程序的一次执行过程，是动态的，具有生命周期，并且会切换状态。

2.进程能够作为独立运行和申请资源（如CPU）的单位，进程可以并发交替运行，而程序（作为一堆代码）不能独立运行。进程能分配到CPU、内存和IO设备等资源，而程序（作为一堆代码）不能被分配资源。

3. 程序和进程可以不一一对应，一个程序可以被多个进程共用，程序只是进程的代码段；

 

- 进程的组成

一个进程实体（进程映像）由数据段、程序段和PCB三部分组成，它们离散的存储在内存中。程序段和数据段描述进程的静态属性；包含进程状态和对资源的占用以及运行信息的进程控制块（PCB）描述其动态属性。

 

数据段保存了进程运行时用到的、产生的运算数据，如全局变量、局部变量（函数中的参数和中间变量等）、宏定义的常量等。

程序段保存了进程的代码，或者说程序被编译后的机器指令。

之所以要区分程序段和数据段，而非将程序和数据混在一个段内保存在内存中是因为他们需要不同的操作系统权限（指读写执行权限），其中操作系统会给予程序段读和执行的权限，通常不需要写权限。数据段需要读写权限，而不应该被执行。

因此程序和数据分开保存是为了在内存中隔离进程的这两类信息，避免造成不安全的行为，而且分开也有利于代码共享。

 

PCB保存了所有操作系统管理和控制该进程所需的控制信息，如下所示。

PS：CPU相关信息又称为“CPU环境”、“现场保护区”、“运行现场”。

 

所谓创建进程实质上是创建进程实体中的PCB，撤销进程实质上是撤销进程实体中的PCB。

PCB是进程的唯一标识。

PS：严格来说，进程和进程实体不一样，进程实体是静态的，进程是动态的，但大多数情况下我们可以认为进程实体就是进程，因此说“一个进程由数据段、程序段和PCB三部分组成”也没错。

以前一直以为进程就是PCB，进程的数据段和代码段以及其他控制信息都是放在PCB内部的。然而进程的数据段、程序段和PCB这3个部分是离散的分布在内存中的，PCB只是保存了该进程数据段和程序段的指针和长度。

 

在UNIX系统中，PCB由proc和user两个结构实现。proc结构常驻内存的核心空间，user结构是proc结构的扩充部分。当进程不在运行状态时，核心不会对user结构信息查询和修改，因此此时user结构可能被换到外存。

 

- 进程的特征

下面的这些特性也是和程序不同的地方：

动态性：进程是程序的一次执行过程，是会发生状态变化，有生命周期的。

并发性：内存中有多个进程实体，进程可以并发运行。

独立性：进程能独立获得资源，独立接收调度，程序不行。

异步性：各进程的运行不会一贯到底，而是一不可预知的速度推进，所以操作系统要提供进程同步机制来解决异步问题。

结构性：进程是由结构的，由程序段、数据段和PCB三部分组成。

 

- 进程基本状态和状态的转换

运行状态：当前进程已经分配到CPU的状态。处于这种状态的进程数不会大于计算机CPU的个数。

就绪状态：进程已具备运行条件和所有所需资源但唯独没有分配到CPU的状态，一旦CPU空闲，该进程就有机会获得CPU控制权进入运行状态。

阻塞状态：进程因等待某种事件而暂时不能运行的状态（如等待某个输入或输出、等待其他进程发来的信号等）。即使CPU空闲也无法获取其控制权。

新建状态：进程正在被创建，操作系统正为进程分配资源 和 初始化PCB的状态。

终止状态：进程完成自己任务正常终止或遇到错误被迫终止或人工干预终止时，操作系统正回收进程的资源，撤销PCB过程的状态。

 

新建->就绪：当就绪队列能容纳新建进程，操作系统就把一个新建状态的进程移到就绪队列，此时变为就绪状态。但这个数量是有限的，因为每个进程都会占用一定的内存和打开文件以及IO设备等资源。

就绪->运行：就绪状态的进程分配到CPU后即可变为运行状态。

运行->阻塞：因等待某一事件发生放弃占用CPU并被放到阻塞队列就变成了阻塞状态。不同阻塞原因对应不同阻塞队列。

阻塞->就绪：处于阻塞的进程所等待的事件发生了。进程会从阻塞队列放到就绪队列，和就绪队列中的其他进程竞争CPU。

运行->就绪：当进程用完本次分配的时间片就会让出CPU，进程放回就绪队列。

运行->终止：进程完成自己工作或发生异常时终止或人工干预而终止会变为终止状态。终止状态的进程会暂留在系统中以便父进程收集有关信息如CPU使用时间等，最后由父进程将其从系统撤销。

 

 

- 进程的组织

进程的组织研究的是进程之间如何归类和存放以便系统管理和调度。分为链接方式和索引方式。

 

链接方式

现代UNIX系统的进程队列采用链接方式组织而成的，可以理解为一个进程队列其实就是一个链表，链表中的节点就是PCB，向后指针是下一个PCB的地址并存在本PCB中。

各个进程按不同状态（就绪、阻塞）会被分为不同队列中（就绪和阻塞队列），而就绪状态的进程也会根据优先级不同分到不同的多个就绪队列中，阻塞状态的进程也会按不同阻塞原因被放到多个阻塞队列中。

 

 

索引方式

有些系统是以索引表的方式记录不同状态的PCB（阻塞状态的进程放到阻塞索引表中，就绪的进程放到就绪表中），我们可以理解为一个索引表就是一个数组，每个数组元素记录的是PCB的地址。

- 进程控制

进程控制是指操作系统创建进程，撤销进程 和 控制进程在不同状态间转换。

进程在不同状态间转换上一节已经介绍过，本节重点介绍的是操作系统如何实现进程控制（如何实现进程在不同状态转换）不发生错误？

举一个例子：

PCB保存了进程的状态，假设用变量state表示，1为就绪状态，2为阻塞状态。

假如处于阻塞状态的进程2，它等待的事件发生了，负责进程控制的内核程序至少需要做这样两件事：

1. 将PCB2的 state 设为 1

2. 将PCB2从阻塞队列放到就绪队列

 

假设内核完成步骤1的时候，有另外一个优先级更高的中断到来，CPU转而执行另一个内核程序。此时该进程就处于一种错误状态：该进程的状态已经是就绪状态，但它的PCB还在阻塞队列中。

 

因此，进程控制（即进程状态转换）的过程中可能涉及多个步骤多个指令，而这些指令是不可分割，不可被中断的。

为了保证进程控制过程不被中断，操作系统使用原语实现进程控制，原语就是具有原子性的，不会被中断的指令集合。

具体的做法是在进程控制涉及的指令前后加上 关中断指令 和 开中断指令。执行了关中断指令之后，CPU不处理任何中断信号，直到执行完开中断之后，CPU才会处理这个中断信号。关中断指令 和 开中断指令之间的临界区代码就是原语代码。

 

 

关中断指令 和 开中断指令的权限非常大，是只能在核心态下执行的特权指令，因此关中断和开中断之间的原语也只能运行在核心态。这也是为什么进程切换需要变态的原因之一。

如果用户程序能够执行关中断和开中断指令，那么假如有一个用户程序执行了关中断指令后，不执行开中断指令，该用户进程就永远不会被中断，会一直占有CPU资源，这是不被允许的。

 

和进程控制相关的原语包括以下：

1. 创建原语（OS创建一个进程时使用的原语）

包括：为新进程分配所需资源 + 初始化PCB + 将PCB插入就绪队列

引发进程创建的事件：用户登录（创建一个shell进程）、作业调度（新作业放入内存，会为新作业创建一个进程）、某些系统调用 和 应用程序请求创建子进程。

2. 撤销原语（OS撤销一个进程使用的原语）

包括：从对应队列移除PCB + 终止所有子进程 + 将该进程拥有的资源归还父进程或操作系统 + 删除PCB

如果撤销的进程正在运行，立刻剥夺CPU，将CPU分配给其他进程。

引发进程终止的事件：正常结束（exit系统调用）、异常结束（代码报错）、外界干预（ctrl+c）

 

3. 阻塞和唤醒原语（进程因等待某事件发生引起阻塞时执行的原语）

阻塞原语包括：保护进程运行现场，将PCB状态置为阻塞态，让出CPU + 将PCB放入对应事件的阻塞队列。

唤醒原语相反。

引发阻塞的事件：等待系统分配资源、IO操作、等待其他进程的信号。

引发唤醒的事件：等待的事件发生。

 

4.切换原语（操作系统切换另一个进程运行所需要执行的原语）

包括：将进程A的运行现场存入PCB，状态改为就绪态，PCB移入就绪队列 + 选择就绪队列中另一个进程B执行，更新其状态为运行态，根据PCB恢复B的运行环境。

引发切换的事件：时间片用完、进程终止、进程阻塞、有更高优先级的进程到达等等（进程状态转换图的每一个箭头都是引发进程切换运行的原因）。

 

无论是哪个进程控制原语，无非做3类事情：

1、更新PCB的信息（包括修改进程状态、保存/恢复CPU环境）；

2、将PCB移到合适的队列；

3、分配资源给该进程/回收该进程资源；

 

 

 

 

===============  补充知识  ===============

 

- 进程组成的真相

1、一个进程的逻辑空间大小取决于系统能寻址的范围，对于32位系统上的进程，无论计算机的物理内存是2G还是1G，这些进程都认为自己拥有2^32=4G的内存空间（逻辑空间），并且进程认为逻辑空间内的所有段的段内信息都是连续存储的。

系统中有多少个进程就意味着系统中有多少个图中这样的进程逻辑空间。

2、进程将自己的4G的逻辑空间分为用户空间和内核空间分别用来存放系统的数据和用户的数据。只有CPU处于内核态时才可以访问内核空间，这样隔离用户数据和系统数据是为了保证两种数据互不干扰，系统稳定。

3、在用户空间，进程按自身内容种类分为不同的段，每个种类的内容放在不同的段内。进程将自己的逻辑空间分为以下几个段：

- 程序段：保存程序代码编译后的机器指令集合；

- 数据段：保存程序的已初始化静态变量和全局变量。

- BSS段：保存程序的未初始化的全局变量或者静态变量（即已声明未赋值的全局变量）

- 堆区 (Heap) : 存储编译期间占用内存大小位置的变量，这样的变量采用动态内存分配。

- 栈区 (Stack) : 进程用户空间栈，由编译器自动分配释放，存放函数的参数值、局部变量的值等。

- 内存映射文件段(Memory Mapping Segment)：进程可以将文件的全部或部分内容映射到该进程逻辑空间的mmap段中，使得访问文件内的内容就向访问内存一样容易。

注意：

静态变量和全局变量的生命周期是进程的整个生命周期，直到进程结束才释放。编译器编译程序的时候就知道有多少静态变量和全局变量，它们占多少空间，而且在程序运行时不会再增长。因此图中BSS段和Data段是大小固定的。

4、进程认为逻辑空间内的所有段的段内信息都是连续存储的，而且每个段在逻辑空间的位置是规定好的，栈放在逻辑空间的低位地址并向下增长，堆放在逻辑空间的较高位地址并向上增长，而BBS段、Data段和Text段则放在堆之下更高地址的区域。

但实际上每个段在装入物理内存时会被分为单位更小的页，成千上万个页被离散的存在物理内存的各个地方，操作系统可不管某个页是栈的页还是堆的页，操作系统想把它放在物理内存的高地址区就放在高地址区，想放在低地址区就放在低地址区。而这一切对用户进程都是透明的，进程仍然以为自己的各个段还是连续的，实际上段内的逻辑地址是连续的，但每个页的物理地址却是离散的。

 

进程的栈

进程逻辑空间中的栈用于存放进程运行过程中函数调用的实参、局部变量和函数返回地址（即调用函数后下一个指令的地址）。

PS：也有很多文章和书籍把进程的栈叫做堆栈，但它其实是栈，和堆没有关系。

进程栈的特性：

1、栈和堆是动态增长的，栈通常向下增长，因此栈的起始地址（栈顶）在高位，逐步向低位增长。

2、每调用一个函数时，进程会创建一个栈帧（栈的节点），栈帧存放了函数的实参、局部变量、函数返回地址以及前一个栈帧的高位逻辑地址（称为栈帧基地址指针EBP），因此进程栈在逻辑上是一个链表结构。函数执行过程中，该函数的栈帧本身也会增长。

调用函数时，进程将栈帧压入栈中。函数执行完毕，将栈顶的栈帧弹出栈。弹出操作并非要删除栈顶栈帧，而只需将栈顶指针指向前一个栈帧的起始地址即可。

函数返回值通过一个特殊的寄存器返回给调用方，但这个值不会存在堆栈的栈帧中。

我们常见的程序报错信息起始是通过每个栈帧的向前指针追踪整个堆栈的。

相比于直接将代码写在主函数中，而非将代码封装在函数中调用，后者会更慢，因为函数调用过程中必须将局部变量、返回地址和函数参数压栈，数据从寄存器移到内存会使函数调用略慢。

3、当栈不断增长到堆的内存区域时会发生堆栈溢出，导致程序崩溃。

4、堆栈由编译器进行管理，栈帧的释放也由编译器负责，无需用户程序自己显式释放。

此外，内核空间中存在一个内核栈用来保存内核进程运行时的函数信息，CPU从用户态切换到内核态时，会将栈指针寄存器的值，即用户栈的栈顶指针暂存到PCB，并将内核栈的指针覆盖到栈指针寄存器上。

 

进程的堆

进程的堆用于动态内存分配，即存放编译时大小未知的变量。和能够自动释放的栈不同，堆由用户进程自行管理，堆内的变量需要显式释放（free指令），否则该变量会一直存在于内存中，一直不释放会造成内存泄漏。

堆占据逻辑空间的绝大部分，用户程序可以使用malloc/new申请堆中的连续存储单元（申请的是逻辑空间的内存），例如申请一个长度为100的整型数组（当然，装入物理内存后该数组占据的页可能是离散的，它只是在逻辑空间连续而已）。

int main()
{
    char* p = (char*) malloc(233);
    free(p);
    return 0;
}

很多时候函数内申请一块内存空间存储一个变量，该变量的实际值保存在堆中，而变量的指针保存在该函数对应的栈帧内。

用户进程申请内存空间需要进行系统调用，为了避免每次申请都发生系统调用，用户进程初次调用申请空间的库函数时，会发生系统调用，系统会分配一块较大的空间给用户进程，之后用户进程每次申请空间则直接从这块大空间中分配，直到这块大空间用完才会再向系统申请。

 

 

- 进程的谱系

操作系统的所有进程是由init进程衍生而来的，所有进程可被视作init进程的后代，这些进程的创建关系是一个树形结构。

新进程的创建由 fork() 和 exec() 这两个系统调用实现：

fork() 会创建一个和父进程完全相同的新进程，包括分配给进程的资源（文件，IO设备）、进程的内存数据、进程的运行现场 和 进程状态等。

区分父子进程的唯一方法是fork的返回值（返回进程ID），父进程的fork返回值是子进程的PID，子进程的fork返回值是0。

实际上，为了节省内存空间和节省创建新进程的时间开销，刚fork出来的进程和父进程共享相同的内存（包括代码和数据），只有在子进程对数据作出修改时才会对要修改的数据进行拷贝，这种技术叫做写时拷贝（COW）。

如果一个进程想要创建一个和自己完全不一样的用于执行其他程序的进程则可以使用fork配合exec。

 

我们可以通过下面的两张图比对一下fork和exec的正确使用方式。

fork的使用方式

 

 

exec的使用方式（fork之后，让子进程执行foo程序，相当于子进程变成了foo进程）

假设父进程是一个写满数据的黑板，在不使用COW的情况下，fork类似于拿一块和父进程一样大的黑板，往新黑板上抄父进程的内容，然后在这些内容的一小部分上作出修改。exec类似于拿一块和父进程一样大的黑板，往新黑板上抄父进程的内容之后，又把新黑板擦掉转而写上foo进程的内容。

 

当子进程执行exit()退出后，父进程需要调用wait(子进程pid) ，wait会做一些事情如 等待子进程运行完正常退出，回收子进程等，因此子进程exit后不会马上被撤销，而是会变成僵尸进程。正常情况下，子进程作为僵尸进程的时间会很短，因为父进程会调用wait()，而如果父进程在回收这个状态码前已经退出，则init进程也会回收和释放该子进程。这点了解即可。

 

下面就是一个僵尸子进程：

int main(void)){
    pid = fork();
    
    // 子进程内
    if (pid == 0){
        printf("child exit\n");
        exit(1);
    }
    // wait(pid);  等待子进程完成
    
    // 父进程内
    while(1){
        sleep(1);
    }
}