keywords: 进程管理
进程是在现代操作系统保证执行并发，资源共享和用户随机的特点下，用来描述程序执行下的资源分配基本单位（进程用于描述资源分配的基本单位，这是功能而非定义）。 为了讨论进程管理，首先应该先对程序下定义。程序是有独立功能的，在时间次序上严格相继（上一条指令执行结束是下一条指令开始执行的充分必要条件）的指令集合，是一个静态的概念。程序具有顺序性，封闭性和可重复性的特征。与程序相对的，进程是一个动态执行过程，或者说程序在CPU上的执行活动被称为进程。进程在执行过程中动态地创建，并在调度执行中消亡。逻辑上，这种动态过程应该存在时间轴上的静态切片，系统中也对应应该存在描述进程存在的物理实体，或者说进程的静态描述（事实上也去是如此，任何动态在某一时间点上都应该存在静态切片，否则动态，或者说另外一个维度上的参数化，就不是well-defined）。进程的静态描述包括：进程控制块（PCB，掌握进程的状态，是系统掌握进程的唯一实体，部分或全部存于内存里），有关程序段和对该数据段进行操作的数据结构集合。
注意并发和并行的区别：并发是指在一段时间内同时执行，而并行是指在某一时间点上同时执行。并发实际上是CPU的分时行为，通过快速在时间上分片使得某一特定程序在其他程序执行没有结束前就开始执行。并行只有在有多个计算通道存在的情况下才能真实发生。（Recall: python 全局解释器锁）。
1 程序的并发执行
多个程序可以执行并发的条件是：任意程序的读和剩余程序的写的交集为空；任意程序的写和其余程序的写的交集为空（对同时读取是没有要求的，这里主要是考虑到并发执行过程中的随机性，Bernstein 1966）。竞争条件等概念可参考C++并发编程。
2 进程的描述 （PCB 和上下文）
进程是被PCB标识和描述的。PCB全部或部分地存在内存中，其记录了进程页表指针和CPU现场(Recall 陷阱处理机构)。除此之外，进程的静态描述除了当前时点的信息外（注意联系PCB中的信息和正文的关系， PCB中记录了进程的标识，控制信息，资源管理信息和CPU现场），还包括程序段和数据集的上下文，体现静态关联顺序。例如，在进程执行过程中，由于中断，等待和程序出错等原因导致进程中断时，操作系统需要记忆进程运行到了什么阶段；另外一个常见的情景是条用子程序。在等待子程序后，进程将返回何处执行，执行结果将放在何处都需要进行记忆。
已经执行过的进程指令和数据在相关寄存器和堆栈中的内容被称为上文，正在被执行的指令和数据在相关寄存器和堆栈中的内容被称为正文，在时间序列上将要被执行的指令和数据被称为进程的下文。
进程的上下文切换发生在不同进程而不是相同进程中（进程不能唤醒自己）。进程上下文切换总共包括三个部分，并涉及到三个进程。第一部分为转移被切换进程的正文部分至有关存储区（保存上文）；第二个进程是操作系统进行分配资源，选取新的进程，第三部分是将被切换线程的资源从相关存储器中取出，并送到相关寄存器和堆栈中，激活被选中的新进程。
3 进程的控制
原语就是原子类型的（不可分割的）语句。
进程控制就是使用一些工具来创建，撤销以及完成进程各状态间（5状态2队列）的转换，从而达到多进程高效率并发协调，实现资源共享的目的。
原语是指系统态下执行的具有特定功能的程序段。原语可以分为机器指令级原语（执行期间不准许间断），另一类是功能级原语（不能并发执行）。由于进程执行的随机性，操作系统中的进程控制程序段会被做成原语。
操作系统对进程的行为主要包括进程的创建，进程的撤销，进程的阻塞和唤醒。
进程可以由系统或者父进程创建，由父进程创建的子进程享有父进程所有的资源。进程撤销时，父进程需要检查子线程是否还有子线程，并撤销这些线程的资源。进程被创建后处于就绪状态，如果被调度（虽然教材中没有明确说明，但是我意识到调度特别指代从就绪状态到执行状态这一环节）系统选中则进入执行状态，如果未被系统选中则进入等待状态（存入进程的等待队列，进程归根到底可以用正文，上下文描述工作状态，并由进程控制块PCB唯一标识）。
进程自身可以在未达到特定条件的情况下自己阻塞自己，但不能自己唤醒自己（因为在等待过程中进程是以正文和上下文的形式储存的，不能执行）。进程的阻塞行为通过阻塞原语实现。一般的阻塞流程是：保留执行状态下的CPU现场，随后在PCB中将进程的状态设置为阻塞状态（等待状态）并加入等待队列，此后操作系统会再次转至进程调度（即从就绪队列中执行一个就绪状态下的进程，防止运算资源空转）。
进程的唤醒由操作系统的唤醒原语执行。进程可以被系统唤醒（recall 并发）或者被在某一时间发生时被操作系统唤醒，从等待队列中转移到就绪队列，随后等待调度程序或者直接返回值。
4 进程的互斥和实现
在现实开发中，Bernstein条件常容易被打破。定义不允许多个并发进程交叉执行的一段程序为临界部分，或者临界区域。对于公共对象的读写如果不是原子操作的，那么在读取或者写入中，为了保证程序的独立性和可重复性不被打破，必须阻塞一些程序，对并发执行速度造成进一步的制约(下减记为间接约束)。系统分配和注销相应共有资源的管理办法就是互斥。由用户程序执行开始的随机性可知，把临界区的各个过程按照不同的时间排列调用是不现实的。因此，有些硬件设施设置了test and set指令来解决互斥问题，但是一种更加节约资源的做法是使用信号量和P,V原语。
在共享资源的时候嵌套一层接口，设计访问该共享资源的流程为: P(semaphore) 读取数据 V(semaphore)。
信号量(semaphore)是一个能够反映共享资源状态的数值。在互斥锁的情境下，这个值被初始化为1。P原语是如下操作的集合（是原子的）：信息量 -= 1；如果信息量 $\ge 0$，调度程序将该进程设置为执行状态，并开始执行；如果信息量$< 0$，则该进程进入就绪队列，等待调度程序唤醒（在清华这本书上，有时候就绪队列和等待队列是替代使用的，稍微有些让人费解）。这样设计的结果是，只要有进程在使用资源，那么semaphore就不可能 = 1，即semaphore最大就是0。此时如果另有进程尝试调用该数据，只要经过P原语，semaphore数值就必定小于0。P原语起到了判断是否有进程在访问共享数据的作用，这也意味着P原语不能在用于唤醒别的进程，因为P原语不能判断进程是否已经调用共享数据结束。 V 原语是以下指令的集合：semaphore += 1， 如果semaphore $\le$ 0, 此时调度程序唤醒就绪队列中的一个进程，开始读取共享数据；如果semaphore $> 0$， 此时该进程返回调用处继续执行。
注意这种设计是结合了原语设计上的局限性构建的。可以想象，如果原语本身可以通过进程上的操作来实现，那么也不会存在竞争条件。事实上，原语是在硬件层面上的设计。
5 同步和生产者-消费者问题
上述的过程实际上是异步的（这里是指开始时间的随机性和运行时间的独立性），即各个进程之间的调用没有先后顺序上的要求：一个进程执行的充分必要条件不由任何在等待队列中的进程产生。如果两个（或多个）进程之间的发生顺序存在约束，例如一个进程需要另一个进程对数据修改完毕后再调用，此时进程必须不断检查另一个进程是否运行结束，此时会造成大量的资源浪费(这个共享资源已经被P, V原语封装过了)。这种异步环境下一组并发进程因直接制约而互发消息，互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。P,V原语同样可以用来实现进程同步，技巧就是用多个信号量交叉使用。同步问题可以抽象为producer-consumer problems。
Comments