进程的描述及控制
前驱图和程序执行 Precedence Graph and Program Execution
前驱图 Precedence Graph
前趋图(Precedence Graph):一个有向无循环图 DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于表示一条语句、一个程序段等；结点间的有向边表示在两个结点之间存在的前趋关系。
初始结点(InitialNode) 前趋图中没有前趋的结点
终止结点(FinalNode) 前趋图中没有后继的结点
$$
\begin{align*}
& \rightarrow = {(P_i, P_j)|P_i \text{ must complete before } P_j \text{ may start}} \
& P_i \rightarrow P_j \text{ means } P_i \text{ is a direct predecessor of } P_j \text{ and } P_j \text{ is a direct successor of } P_i.
\end{align*}
$$
若一个程序由若干程序段（即操作）组成，而这些操作必须按照某种先后次序执行，这类执行过程就是程序的顺序执行。
程序执行 Program Execution
程序执行方式
- 顺序执行—单道批处理系统
- 并发执行–多道批处理系统
- 应用级并发是指若干应用程序的并发执行。
- 系统级并发是指操作系统自身软件的并发执行。
顺序执行
若一个程序由若干程序段（即操作）组成，而这些操作必须按照某种先后次序执行，这类执行过程就是程序的顺序执行
- 顺序性：处理机的操作严格按照程序所规定的顺序执行。
- 封闭性：程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因素影响。
- 可再现性：只要程序执行时的环境和初始条件相同，都将获得相同的结果。
并发执行的特征
- 间断性：由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系，导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。
- 失去封闭性：是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。
- 不可再现性：程序在并发执行时，由于失去了封闭性，导致不可再现性 。
进程的描述 Process
Definition,Features,Components,States
为什么引入进程?
并发执行：进程使得多个任务可以在同一时间段内交替执行，这种并发执行使得 CPU 可以在等待一个任务的 IO 操作完成时执行另一个任务，从而提高了系统的效率和吞吐量。
独立性：每个进程都有自己的私有地址空间，这意味着一个进程不能直接访问另一个进程的内存。这种内存保护机制有助于防止一个进程意外或恶意地干扰另一个进程。
简化编程模型：在没有进程的情况下，程序员必须手动管理多任务执行和资源分配。有了进程，这些任务就由操作系统自动处理，程序员可以专注于应用程序的逻辑。
资源管理：进程是资源分配和管理的基本单位。操作系统可以根据每个进程的需要和优先级分配资源，如 CPU 时间、内存空间等。
进程控制块 PCB
PCB 是操作系统中用于描述进程的一种数据结构，它是操作系统中最重要的数据结构之一。PCB 中包含了进程的所有信息，是操作系统对进程进行控制和管理的数据结构。它包含以下主要信息：
- 进程标识符信息
- 处理机的状态信息
- 进程的调度信息
- 进程控制信息
PCB 的主要信息
进程标识符 PID
进程标识符用于唯一地标识一个进程。一个进程通常有两种标识符：
- 内部标识符。为每一个进程赋予一个唯一的数字标识符，通常是进程的序号。设置内部标识符主要是为了方便操作系统使用。
- 外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户（进程）在访问该进程时使用。
处理机状态信息 Processor State Information
处理机状态信息主要是由处理机的各种寄存器的内容组成的。例如:
- 通用寄存器，又称为用户可视寄存器。
- 指令计数器 PC，其中存放了要访问的下一条指令的地址。
- 程序状态字 PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等
- 用户栈指针 SP，用于存放系统调用参数及调用地址。栈指针指向该栈的栈顶。
进程调度信息 Scheduling Information
在 PCB 中还存放一些与进程调度和进程对换有关的信息。
- 进程状态。指明进程的当前状态
- 进程优先级。
- 事件。是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。
- 其它信息。如：进程已等待 CPU 的时间总和、进程已执行的时间总和等；
可参考linux kernel sched.h task_struct结构
进程控制信息 Process Control Information
- 程序和数据的地址 进程的程序和数据所在的内存或外存地址。
- 进程同步和通信机制 实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等。
- 资源清单 进程所需的全部资源及已经分配到该进程的资源的清单；
- 链接指针 本队列下一个进程的 PCB 的首地址。
PCB 的组织方式
- 线性方式:把系统中所有的 PCB 都组织在一张线性表中。
- 链接方式:把具有同一状态的 PCB，用其中的链接指针链接成一个队列。(通常，可根据等待事件的不同，组织多个不同的阻塞队列,如等待打印机和等待内存等)
- 索引方式:相同状态的进程 PCB 组织在一张表格中，系统根据所有进程的状态建立几张索引表，系统分别记载各 PCB 表格的起始地址
因为进程的主要操作就是插入和删除，因此，链接方式使用更多一些
PCB 的作用
进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位(进程)。
在进程的整个生命期中，操作系统总是通过 PCB 对进程进行控制的。所以说，PCB 是进程存在的唯一标志。
OS 是根据 PCB 来对并发执行的进程进行控制和管理的，如：
进程创建：分配进程控制块
进程调度：保存和读取进程控制块
进程撤销：回收进程控制块
进程控制 Process Control
定义
进程控制 Process Control:操作系统的核心功能之一。包括进程的创建,终止,调度,状态转换,同步,通信等。进程控制一般是由 OS 内核中的一组原语来实现的。
原语 Primitive:操作系统内核或微核提供核外调用的过程或函数称为原语,其由若干条指令构成，用于完成特定功能的一段程序。原语在执行过程不允许被中断。
原子操作 Atom Operation：执行中不能被其它进程（线程）打断的操作就叫原子操作。当该次操作不能完成的时候，必须回到操作之前的状态，原子操作不可拆分。
内核 Kernel:计算机硬件的第一层扩充软件，为系统对进程控制、存储器管理等提供有效的机制。内核常驻内存，紧靠硬件，运行效率较高。在不同操作系统中，内核所包含的功能不尽相同，但一般应包含以下功能：
支撑功能:中断处理,时钟管理,原语操作
资源管理功能:进程管理,存储器管理,设备管理
进程的创建与终止
进程创建原语执行的操作:
- 申请空白 PCB。
- 为新进程分配资源。
- 初始化进程控制块。
- 初始化标识信息。
- 初始化处理机状态信息。使程序计数器指向程序的入口地址，使栈指针指向栈顶；
- 初始化处理机控制信息：进程的状态、优先级。
- 将新进程插入就绪队列，启动调度。
引起进程创建的主要事件
用户登录
作业调度
提供服务
应用请求
引起进程终止的事件
正常结束。
异常结束：
- 越界错误。
- 保护错。
- 非法指令。
- 特权指令错。
- 运行超时。
- 等待超时。
- 算术运算错、被 0 除：
- I/O 故障。
外界干预:外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。
- 操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；
- 父进程请求终止该进程；
- 当父进程终止时，OS 也将他的所有子孙进程终止。
进程的终止过程
- 根据被终止进程的 PID 找到它的 PCB，从中读出该进程的状态。
- 若被终止进程正处于执行状态，应立即终止该进程的执行，重新进行调度。
- 若该进程还有子孙进程，立即将其所有子孙进程终止。
- 将被终止进程所拥有的全部资源，归还给其父进程，或者归还给系统。
- 将被终止进程的 PCB 从所在队列中移出
进程的阻塞与唤醒 Block and Wakeup
引起进程阻塞的原因
- 请求系统服务。
- 启动某种操作：如 I/O 操作。
- 新数据尚未到达。
- 无新工作可做
进程阻塞的过程
处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语 block，使自己由运行态变为阻塞态。可见，进程的阻塞是进程自身的一种主动行为。
- 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语
block把自己阻塞；（阻塞是主动行为） - 把进程控制块中的现行状态由
running改为blocked，并将 PCB 插入阻塞队列； - 转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。
进程的唤醒过程
当被阻塞进程所期待的事件出现时，例如，当进程提出 I/O 请求时，进程会进入到阻塞状态，但是不能让这个进程一直处于阻塞状态，等到其 I/O 操作完成时，那么系统就要采用唤醒原语 wakeup 唤醒这个处于阻塞的进程，以使它继续执行。
- 当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该 I/O 设备的进程）调用唤醒原语
wakeup()，将等待该事件的进程唤醒。（唤醒是一种被动行为） - 唤醒原语的执行过程是：
把被阻塞的进程从等待该事件的阻塞队列中移出
将其 PCB 中的现行状态由阻塞改为就绪
将该 PCB 插入到就绪队列中等待 CPU 调度
进程的挂起与激活 Suspend and Active
当有引起进程挂起的事件，系统利用挂起原语suspend（）将指定进程或者处于阻塞状态的进程挂起。
当有发生激活进程的事件发生，若该进程在外存中已有足够的空间时，可将在外存上处于静止就绪的进程从外存调入内存，系统利用激活原语active()将指定进程激活
进程的挂起
当出现了引起进程挂起的事件时，系统将利用挂起原语suspend()将指定进程挂起或处于阻塞状态的进程挂起。（挂起是主动行为）
调用挂起原语的进程只能挂起自己或其子孙进程;内核的 sleep()函数是在挂起原语的基础上利用定时器实现的。
挂起原语的执行过程
- 检查将要被挂起的进程的状态
running：将该进程的 PCB 中的现行状态由running改为ready suspend,设置 CPU 调度标志为真；ready: PCB 中的现行状态由running改为ready suspend；blocked：将该进程的 PCB 中的现行状态由blocked改为blocked suspend； - 将被挂起进程的 PCB 复制到指定的内存区域。
- 若处于运行状态，则转向调度程序重新调度
Ex:请判断下列说法哪些的正确的？
- 进程可以由自己创建(❌,进程可以创建子进程,但不能自己创建自己)
- 进程可以由自己阻塞
- 进程可以由自己挂起
- 进程可以由自己激活
- 进程可以由自己唤醒
- 进程可以由自己撤消