进程的基本概念

程序：一个在时间上严格按先后次序操作实现算法功能的指令序列，程序本身是静态的。
进程：

• 描述性定义：计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程称之为进程。
• 另一种定义是：可并发执行的程序在一个数据集合上的执行过程。

程序执行有固定的时序

特征：顺序性、封闭性、可再现性

• 顺序性：处理机的操作严格按规定顺序执行
• 封闭性：程序执行时，独占系统资源
• 可再现性：当初始条件相同时，程序多次执行的结果相同

程序的并发执行

多个程序的并发执行（可能性分析）

特征

• 间断性：程序在并发执行时，形成了相互制约关系。相互制约将导致并发程序具有“执行—暂停—执行”这种间断性的活动规律
• 失去封闭性：主要由共享资源引起，系统中的资源供多个程序共享，致使程序的运行失去了封闭性
• 不可再现性：并发程序对资源的共享与竞争，又会导致程序执行环境与运行速度的改变，从而可能产生程序运行结果不唯一问题。

再现性问题：

• 若两个程序P1和P2满足下述条件，便能并发执行且有可再现性：
  R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2) = { }
  “读集” R ( Pi ) 为程序 Pi 在执行期间所需参考的所有变量的集合。
  “写集” W ( Pi )为程序 Pi 在执行期间所需改变的所有变量的集合。
  例如：S1: a := x + y
  S2: b := z + 1
  S3: c := a - b
  S4: d := c + 1

进程与程序的关系

数据结构=程序+数据+PCB
程序与进程不是一一对应关系

进程与程序的区别

• 进程和程序的区别
• 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制
• 进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存
• 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）
• 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序

进程的核心思想

• 进程是某种类型的一个活动，它有程序、输入、输出和状态。
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
• 在分时操作系统中，单个CPU被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。

进程特征

• 动态性：进程具有动态的地址空间（数量和内容），地址空间上包括：
  • 代码（指令执行和CPU状态的改变）
  • 数据（变量的生成和赋值）
  • 系统控制信息（进程控制块的建立和系统收回）
• 独立性：各进程的地址空间相互独立，除非采用进程间通信手段；
• 并发性：多个进程实体同存于内存中，且能在一段时间内同时运行；引入进程实体的目的就是并发执行
• 异步性：各进程按各自独立的、不可预知的速度向前推进
• 进程的结构性：程序段、数据段和PCB；程序文件中通常也划分了代码段和数据段，进程的创建与撤消就是PCB的创建与撤消

进程的状态及转换

两状态进程模型

• 运行（Running）
• 非运行（Not-running）
  

进程的三种基本状态

• 就绪(Ready)状态  
  • 可运行，已获得除CPU外的所需资源，等待分配CPU
  • 一个系统中多个处于就绪状态的进程排成就绪队列
• 运行(Running)状态  
  • 占用CPU运行；处于此状态的进程的数目<=CPU的数目
  • 没有其它进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）
• 阻塞(Blocked)状态  
  • 等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行
  • 通常阻塞进程也排成一个阻塞队列

进程的五态模型

新增的两个状态：

• 创建状态  
  • 进程刚建立，还未进入就绪队列。
• 终止状态  
  • 进程已（正常或异常）结束，已从就绪队列中移出，但尚未撤销。
  • 暂留，以便其他进程收集该进程的有关信息。
    

进程的挂起

• 这个问题的出现是由于进程优先级的引入，一些低优先级进程可能等待较长时间，从而被对换至外存。这样做的目的是：
  • 提高处理机效率：就绪进程表为空时，要提交新进程，以提高处理机效率；
  • 为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张
  • 用于调试：在调试时，挂起被调试进程（从而对其地址空间进行读写）

引起进程挂起的原因有以下几种

• 终端用户的请求 ：当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时将自己的程序静止下来

• 父进程请求 ：父进程需要考查和修改子进程

• 负荷调节的需要 ：在实时系统中为了调整工作负荷可将不重要的进程挂起

• 操作系统的需要：如检查运行中的资源使用情况

• 挂起（Suspend）：进程从内存转到外存

  • 就绪挂起：活动就绪到静止就绪，当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程
  • 阻塞挂起：活动阻塞到静止阻塞，无进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程
  • 运行到就绪挂起：对抢占式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态

• 激活（Activate）：进程从外存转到内存

  • 就绪激活：静止就绪到活动就绪，没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换；
  • 阻塞激活：静止阻塞到活动阻塞，当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程激活；

• 事件出现(Event Occurs) ：进程等待的事件出现，如：操作完成、申请成功等；

• 可能的情况有：

  • 阻塞到就绪：针对内存进程的事件出现；
  • 阻塞挂起到就绪挂起：针对外存进程的事件出现；

• 收容(Admit)：收容一个新进程，进入就绪状态或就绪挂起状态。进入就绪挂起的原因是系统希望保持一个大的就绪进程表（挂起和非挂起）；
  

进程控制块PCB

PCB是进程实体的一部分，是OS中最重要的数据结构

进程的组成

• 进程控制块PCB
• 程序段
• 数据段
• 堆栈

CB的作用

• 引入PCB的作用：就是使程序能成为独立运行的单位，并可和其他进程并发执行。

进程控制块PCB的内容

• 进程描述信息

  • 进程名
  • 进程标识符
  • 用户名

• 处理机状态信息

  • 通用寄存器
  • 指令计数器
  • 程序状态字寄存器
  • 栈指针

• 进程调度信息

  • 进程状态
  • 进程优先级
  • 运行统计信息。
  • 进程阻塞原因。

• 进程控制和资源占有量信息

  • 程序入口地址
  • 程序的外存地址
  • 进程同步及通信机制
  • 资源占有信息
  • 链接指针

进程控制块PCB的组织

PCB链接方式：把具有同一状态的PCB用其中的链接字链接成一个队列，可以形成就绪队列、若干个阻塞队列和空白队列

PCB的组织

• 索引:索引方式 系统根据所有进程的状态建立几张索引表，如就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在专用单元中。索引表中记录的是PCB在PCB表中的地地址

• 进程控制的职责是对系统中全部进程实施有效管理，包括
  • 创建新进程
  • 终止已结束进程
  • 终止由于某事件而无法运行下去的进程
  • 负责进程的状态转换
• 这些功能一般由操作系统的内核实现，操作系统的内核是基于硬件的第一次扩充。把与硬件紧密相关的模块、运行频率较高的模块及一些公用的基本操作安排在靠近硬件的软件层次中，并常驻内存，以提高系统运行效率。

这些进程控制功能是通过执行各种原语实现的！

进程切换

进程上下文
（1）系统级上下文。操作系统内核进程使用的进程上下文信息集合，主要包括PCB与逻辑地址到物理地址转换的核心数据结构，如段表、页表及核心栈等。
（2）寄存器上下文。CPU中所有寄存器的信息集合，如通用寄存器、指令寄存器、程序状态字寄存器和栈指针等。
（3）用户级上下文。用户进程访问和修改的进程上下文信息集合，主要包括进程的程序段、数据段、用户栈和共享存储区。

进程切换的时机
（1）中断。中断发生时，操作系统保存当前运行进程（称为旧进程）的现场信息，调度新进程运行。
（2）异常。当CPU在一条指令执行时，检查到有一个或多个预定义的条件或错误产生时就会产生异常，这时，终止当前运行进程的执行，CPU转去执行异常处理程序。
（3）系统调用。系统调用是对操作系统服务的一种显式请求。阻塞型系统调用发生时，则当前运行进程被阻塞，此时CPU转去执行进程调度程序。

进程上下文切换
（1）当前运行进程被中断时保存其CPU现场信息。
（2）对被中断的当前运行进程进行PCB更新，包括改变进程状态和其他 相关信息。
（3）将被中断的当前运行进程的PCB移入适当的队列（时间片到则移入就绪队列，因某事件阻塞则移入相应的阻塞队列）。
（4）由进程调度程序调度选中另一个就绪进程，为其设置执行的上下文环境并对其PCB进行更新。
（5）修改新进程的地址空间，更新新进程的内存管理信息。
（6）恢复被选中进程最后一次进程上下文切换时所保存的CPU现场信息。

进程控制原语

进程家族树

• 描述了进程的家族关系
• 子进程可继承父的资源，撤消时应归还给父进程，父的撤消会撤消全部子进程。

进程的创建

引起进程创建的事件

• 用户登录
• 新作业进入系统
• 提供服务
• 应用请求

创建原语要做的工作

• 申请空白PCB
• 为进程分配资源
• 初始化PCB
  • 初始化进程描述信息
  • 初始化处理机状态信息
  • 初始化进程控制信息
• 将新进程插入就绪队列

进程创建

• 在进程控制块表中获取一个空的记录
• 填入被建立进程的信息：
  该进程的程序段地址
  初始状态（就绪状态）
  该进程的数据区域的指针
  该进程的父进程名称等
• 然后将新建立的进程插入到就绪状态的进程队列中
  进程建立并不影响调用者的状态，调用者只是在执行自己的程序时，完成了一个调用命令，接着继续进行后续的工作

注意：进程建立以后并不是立即投入运行，而是进入就绪队列。这是因为被建立进程的父进程并没有安排进程运行的资格。被建立进程的运行靠进程调度来实现

进程的撤销

引起进程撤消的事件

• 进程正常结束
• 进程异常结束
• 外界干预

撤消原语要做的工作

• 查找撤消进程的PCB
• 若进程处于执行状态，终止之，并进行进程调度
• 若有子孙，予以终止
• 归还资源
• 从所在队列移出

异常结束：在进程运行期间，由于出现某些错误和故障而迫使进程终止。

• 越界错误 这是指程序所访问的存储区，已越出该进程的区域
• 保护错 进程试图访问一不允许访问的资源或文件，或者以不适当的方式进行访问，如进程试图去写一个只读文件
• 非法指令 程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令
• 特权指令错 用户进程试图去执行一条只允许OS执行的指令
• 运行超时 进程的执行时间超过了指定的最大值；
• 等待超时 进程等待某事件的时间， 超过了规定的最大值
• 算术运算错 进程试图去执行一个被禁止的运算，如被0除；
• I/O故障 这是指在I/O过程中发生了错误等

外界干预：外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行
操作员或操作系统干预 由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程
父进程请求 由于父进程具有终止自己的任何子孙进程的权利， 因而当父进程提出请求时，系统将终止该进程；
父进程终止 当父进程终止时，OS也将他的所有子孙进程终止

进程的阻塞与唤醒

引起进程阻塞的事件

• 请求系统服务
• 启动某种操作
• 数据尚未到达
• 无新工作可做

阻塞原语要做的工作

• 停止进程的执行
• 将进程插入阻塞队列，改变进程在PCB中的状态
• 重新调度

唤醒原语要做的工作

• 将进程从阻塞队列解下
• 将进程插入就绪队列
• 改变进程在PCB中的状态

引起进程阻塞和唤醒的事件

• 请求系统服务
  如请求打印机时，若已被其他进程占用，此时只能阻塞，等其他进程释放后再将请求进程唤醒
• 启动某种操作
  当进程启动某种操作后，如果该进程必须在该操作完成后才能继续执行，则必须先使进程阻塞，以等待该操作完成。如启动I/O设备
• 新数据尚未到达
  对于相互合作的进程，如果一个进程需要另一合作进程提供的数据，则在数据到达之前只能阻塞
• 无新工作可做
  系统中的一些特殊功能进程，在完成了任务之后，等待新任务到来。如系统中的发送进程

进程阻塞过程

• 正在执行的进程，当发现上述某事件时，因无法继续执行，进程便通过调用阻塞原语block()把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为
• 进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列
• 若系统中设置了因不同事件而阻塞的多个阻塞队列，则将本进程插入到具有相同事件的阻塞(等待)队列
• 调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境

进程唤醒过程

• 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup( )，将等待该事件的进程唤醒
• 唤醒原语执行的过程是
  • 把被阻塞的进程从等待该事件的阻塞队列中移出
  • 将其PCB中的现行状态由阻塞改为就绪
  • 将该PCB插入到就绪队列中

进程等待

在进程的运行过程中，如果申请某一种条件而没有被满足，进程不得不中止当前的运行，进程等待原语就会被激活

进程唤醒

• 进程的唤醒
  当等待所需资源或者条件的进程有机会获得所等待的资源或条件时，该进程就可以从等待状态变为就绪状态
  这种状态的改变需要其他进程的帮助
  具体做法是运行中的进程调用进程
  唤醒原语
  唤醒原语找到对应条件的等待队列
  从等待队列中取下一个进程
  将进程状态从等待状态变为就绪状态
  插入到就绪队列中
  直到所有的进程都被处理完毕
  调用唤醒原语的进程继续执行
  

进程的挂起与激活

• 进程的挂起过程
  • 由进程自己或其父进程调suspend原语完成，将该进程PCB移到指定区域，注意状态的改变，有可能要重新调度。
• 进程的激活过程。
  • active原语（如在外存，调入内存，改变状态，根据情况看是否调度，如抢先或非抢先）。
• 阻塞、唤醒一般由OS实现，而挂起与激活可由用户干预。

挂起原语要做的工作

• 检查被挂起进程的状态
• 如进程处于就绪状态，将进程从就绪状态变为就绪挂起状态
• 如进程处于阻塞状态，将进程从阻塞状态变为阻塞挂起状态
• 如进程正在运行，将进程变为就绪挂起状态，并重新调度

激活原语要做的工作

• 检查被激活进程的状态
• 如进程处于就绪挂起状态，将进程从就绪挂起状态变为就绪状态
• 如进程处于阻塞挂起状态，将进程从阻塞挂起状态变为阻塞状态
• 若系统为抢占式系统，则进行进程调度