操作系统原理学习笔记（五）-程序执行与进程描述

操作系统原理学习笔记目录

这部分好多是手机打的（叉腰）。

第四篇没写，跳过了， 有空补上。

前趋图

前趋图(Precedence Graph)：描述程序执行先后顺序的有向无循环图，记为DAG(Directed Acyclic Graph)，图中每个结点表示一个进程或程序段，乃至一条语句。

偏序(Partial Order)/前驱关系(Precedence Relation)：结点间的有向边。

初始节点(Initial Node)：无前驱结点。

终止结点(Final Node)：无后继结点。

重量(Weight)：结点程序量或执行时间

顺序执行的特征

顺序性：严格按照程序所规定的顺序执行。

封闭性：程序执行后，只有本程序能改变它。

可再现性：只要程序执行时的环境和初始条件相同，则不论怎样运行程序，都不会改变其运行结果。

并发执行的特征

间断性：并发执行时，由于共享资源或相互合作，这些程序执行时可能因为其他程序的原因无法获得所需资源，这种相互制约导致并发程序具有“执行-暂停-执行”的间断性执行规律。

失去封闭性：资源共享导致资源状态可能会被改变，因此程序所在环境可能被其他程序影响。

不可再现性：如失去封闭性一般，共享的资源会被其他程序改变，以此产生的结果也会产生变化。

进程的定义

由于上条所述的并发执行三点特征，导致一般程序无法并行执行，因此，“进程”这个概念被引入。

进程控制块(Process Control Block, PCB)：用来描述进程基本情况与活动过程的专门的数据结构。

进程实体/进程映像：由程序段、相关数据与PCB组成。

进程是程序的一次动态执行过程。
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的特征

动态性：由创建而产生，由调度而执行，由撤销而消亡。

并发性：多个进程实体同存于内存中，能在一段时间内同时运行。

独立性：能独立运行、独立获得资源、独立接受调度的基本单位。

异步性：进程是按异步方式运行的，即以各自独立的、不可预知的速度运行。一般程序也是因此无法并行。

进程的三种基本状态

就绪(Ready)：分配好除CPU外的所有必要资源。按照特定策略（如优先级策略）排成就绪队列。

执行(Running)：已获得CPU资源，正在执行。对任一时刻，单处理机系统中只有一个执行状态的进程，而多处理机系统有多个。

阻塞(Blocked)：正在执行的进程由于发生某事件（I/O请求）暂时无法继续执行时的状态。根据不同阻塞原因，设置多个阻塞队列。阻塞后的资源会被进程调度，分配给另一个就绪进程。

基本状态的转换

创建状态与终止状态

创建过程：进程申请空白PCB，填写用于控制和管理进程的信息，然后分配所需资源，转为就绪状态并插入就绪队列中。

若资源不足，创建无法完成，进程不能被调度运行，此时的状态被称为创建状态。

终止状态：进程自然结束、出现无法克服的错误、被操作系统终结 或 被其他有终止权的进程终结，则进入终止状态。

终止过程：进入终止状态后不能再执行，相关进程与操作系统收集信息后，操作系统删除该进程，将PCB清零，返还PCB空间。

进入终止状态后不能再执行，相关进程与操作系统收集信息。

创建成功获得许可后进入就绪状态，执行完成并释放后进去终止状态。

题外话：Linux进程的五种状态

运行、中断、不可中断、僵死、停止。

挂起操作

终端用户发现程序运行时有可疑问题，希望暂停运行，便于研究与修改。

父进程希望挂起子进程，以便考察修改或协调。

负荷调节的需要。

操作系统的检查需求。

引入挂起原语操作后三个基本进程状态的转换

挂起原语：Suspend。

激活原语：Active。

就绪：Ready，活动就绪被挂起原语挂起后变为静止就绪，Readya变为Readys，再被激活原语激活后，又变为Readya。

阻塞：Blocked，同上，Blockeda与Blockeds，最后一个字母，a被激活原语激活，s表示被挂起原语挂起。

引入挂起操作后五个进程状态的转换

为了让表更加简洁，创建与终止的转换在下面先提出。

创建->活动就绪，系统资源足够分配该进程。

创建->静止就绪，受系统资源与性能要求限制，不分配给新建进程所需资源。

执行->终止：进程自然结束、出现无法克服的错误、被操作系统终结 或 被其他有终止权的进程终结，则进入终止状态。

OS中用于管理控制的数据结构

表征其实体，包含资源或进程的标识、描述、状态等信息及一批指针。

分为内存表、设备表、文件表与用于进程管理的进程表（PCB）。

进程控制块PCB的作用

作为独立运行基本单位的标志。

实现间断性运行方式，阻塞后可保存CPU现场信息，以便恢复CPU现场。

提供进程管理所需信息。

提供进程调度所需信息。

实验与其它进程同步与通信。

进程控制块中的信息

进程标识符：
外部标识符：方便用户对进程的访问。
内部标识符：方便系统对进程的使用。

处理机状态：包括通用寄存器（用户可视寄存器）、指令寄存器、程序状态字PS、用户栈指针。

进程调度信息：进程状态、进程优先级、进程调度其他所需信息、事件。

进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针。

进程控制块的组织方式

线性方式：将所有PCB都组织在一张线性表中，查找时需扫描整张表。

链接方式：具有相同状态进程的PCB分在同一队列，形成就绪队列、阻塞队列和空白队列等。

索引方式：根据进程状态的不同，建立不同索引表，例如就绪索引表、阻塞索引表等。