前驱图和程序执行
前趋图
前趋图(Precedence Graph) 是一个有向无循环图，可记为DAG，用于描述程序/进程之间执行的先后顺序。
图中每个结点可用来表示一个进程或程序段，结点间的有向边表示两个结点之间存在的偏序或前趋关系
如P1与 P2存在前趋关系，记作P1 -> P2，表示在P2开始执行之前P1必须完成，此时称P1是P2的直接前趋，P2是P1的直接后继。没有前趋的结点称为初始结点，没有后继的结点称为终止结点，每个结点还有一个重量，用于表示该结点所含有的程序量或程序的执行时间。
注意：前趋图中必须不存在循环
程序的顺序执行：
在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。 一道程序执行完后另一道才能开始
程序顺序执行的特征
顺序性：处理机的操作严格按照程序所规定的顺序执行。
封闭性：程序一旦开始执行，其计算结果不受外界因素的影响
-可再现性：程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关。
程序并发执行的特征
间断(异步)性：“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；
失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。
失去可再现性：失去封闭性 -> 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。并发程序执行的结果与其执行的相对速度有关，是不确定的
进程的描述
进程的定义与特征
进程的引入：为了使多道程序能够并发执行，且为了能对并发执行程序加以描述和控制,以提高资源利用率和系统效率。
进程的定义
进程是具有独立功能的程序关于某个数据集合在计算机系统中的一次执行过程。是系统进行资源分配和调度的一个单位
系统进行资源分配和调度的、一个可并发执行的独立单位。
进程是程序的一个实例，是程序的一次执行
进程和程序的比较
程序是静态的，在外存中，进程是动态的，在内存中
程序可长期保存；而进程是有生命周期的。
程序是指令的有序集合；而进程则是由程序、数据和进程控制块三部分组成。
进程和程序之间不是一一对应的：一个进程可以执行一个或多个程序，一个程序可以同时被多个进程执行。
进程是一个独立运行的单位，也是系统进行资源分配和调度的独立单位，能与其他进程并发执行；而程序不能并发执行。
进程的特征
结构特征：由程序段、数据段及进程控制块（PCB）三部分构成，总称“进程映像”。进程控制块(PCB) + 程序 + 数据 = 进程实体
动态性：进程的实质是程序的一次执行过程，因而是动态的；进程具有生命周期。
并发性：多个进程可以并发地执行。
独立性：独立运行，独立获得资源。
异步性：间断性。
进程的基本状态与转换
三种基本状态及其转换
一个进程从创建、运行至消亡的整个生命周期，可以用一组状态加以刻画。
一般来说,进程在执行过程中至少经历三种不同的进程状态：
运行态（running）：占有处理机正在运行。
就绪态（ready）：具备运行条件，等待系统分配处理机以便运行。
阻塞态（blocked）：不具备运行条件，正在等待某个事件的发生
三种基本状态的转换
创建状态和终止状态
创建状态:
为一个新进程创建PCB，并填写必要的管理信息；
分配必要的资源，再把该进程转入就绪状态并插入就绪队列
终止状态：
等待操作系统进行善后处理；
将其PCB清零，并将PCB空间返回系统
挂起操作和进程状态的转换
当该操作作用于某个进程时，该进程将被挂起，这意味这此时进程处于静止状态。
挂起操作的引入：
终端用户的请求
父进程请求
负荷调节的需要
操作系统的需要
若原本处于就绪状态，则挂起后不接受调度
阻塞变就绪需要释放资源，反过来就是请求资源
静止变活动需要激活，反之就是挂起
进程管理中的数据结构
OS中用于管理资源和控制进程的数据结构
OS管理的这些控制表一般可以分为以下四类：内存表、设备表、文件表和用于进程管理的进程表，进程表又称为PCB。
PCB的作用
PCB的作用：
为了便于系统描述和管理进程的运行，在os的核心位每个进程定义了一个数据结构—PCB作为进程实体的一部分
PCB记录了操作系统所需的，用于描述进程的当前情况以及管理进程运行的全部信息
PCB的作用是使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位
作为独立运行基本单位的标志。
当一个程序（含数据）配置了PCB后，就表示它已是一个能在多道程序环境下独立运行的、合法的基本单位了，即具有了取得OS服务的权利。
系统是通过PCB来感知进程的存在的。也就是说，PCB已成为进程存在于系统中的唯一标志。
实现间断性运行方式。
系统就可以将CPU现场信息保存在被中断进程的PCB中，供该进程再次被调度运行而须恢复CPU现场信息时使用。
提供进程管理所需要的信息。
在进程的整个生命期中，OS总是根据PCB来实施对进程的控制和管理的
提供进程调度所需要的信息。
实现与其他进程的同步与通信。
PCB中的信息
PCB中的信息：
进程标识符PID
进程标识符用于唯一地标志一个进程。一个进程通常有两种标识符。
外部标识符。为了方便用户（进程）对进程的访问
内部标识符。为了方便系统对进程的使用
处理机状态
处理机状态信息，也称为处理机的上下文，主要是由处理机的各种寄存器中的内容组成的。
通用寄存器，可被用户程序访问，用于暂存信息
指令计数器，其中存放了要访问的下一条指令的地址；
程序状态字寄存器，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；
用户栈指针寄存器，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放进程和系统的调用参数及调用地址。
进程调度信息
OS在进行进程调度时，必须了解进程的状态以及有关进程调度的信息，这些信息包括：
进程状态，指明进程的当前状态，作为进程调度和对换时的依据；
进程优先级，描述进程使用处理机的优先级别（用一个整数表示），优先级高的进程应优先获得处理机；
进程调度所需要的其他信息，如进程已等待CPU的时间总和、进程已执行时间总和等，它们与所采用的进程调度算法有关；
事件，指进程由执行状态转换为阻塞状态所等待发生的事件，即阻塞原因。
进程控制信息
进程控制信息是指用于进程控制所必需的信息，包括：
程序和数据的地址，即进程中程序和数据的内存或外存起始地址，便于再调度到该进程执行时，能从PCB中快速找到其程序和数据；
进程同步和通信机制，这是实现进程同步和进程通信时所必需的机制，如消息队列指针、信号量等，它们可能会全部或部分放在PCB中；
资源清单，在该清单中列出了进程在运行期间所需的全部资源（除CPU外）；
链接指针，它给出了本进程所在队列中的下一个进程的PCB的始址。
PCB的组成方式
线性方式。将系统中所有的PCB都组织在一张线性表中，将该表的起始地址存放在内存的一个专用区域中。该方式实现简单且开销小，但每次查找时都需要扫描整张表，因此适合进程数目不多的系统。
链接方式。通过PCB中的链接字，将具有相同状态的进程的PCB分别链接成一个队列。
索引方式。系统根据所有进程状态的不同，建立几张索引表，如就绪索引表、阻塞索引表等，并把各索引表在内存中的起始地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。
进程控制
进程控制是进程管理中最基本的功能，其负责创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、转换运行中进程的状态等，进程控制就是要实现进程状态转换
进程控制一般是由OS内核中的原语（原子性操作，一旦开始不能停止）实现的
OS内核主要功能
OS内核：
- 支撑功能
- 中断处理：最基本功能
- 时钟管理：
- 原语操作
- 资源管理功能
进程的创建
进程的层次结构：
在OS中，允许一个进程创建另一个进程，子进程可以继续创建其自己的子进程（即父进程的孙进程），由此便形成了进程的层次结构
引起进程创建的事件
用户登录：在分时系统中，若登录成功，则系统将会为该用户创建一个进程，并把它插入就绪队列中。
作业调度：在多道批处理系统中，当作业调度程序按一定的算法调度到某个（或某些）作业时，便会将它（们）装入内存、为它（们）创建进程，并把它（们）插入就绪队列中。
提供服务：当运行中的用户程序提出某种请求后，系统将专门创建一个进程来为用户提供其所需要的服务
应用请求：由用户进程自己创建新进程，以使新进程以同创建进程并发执行的方式完成特定任务。
操作系统发现要求创建新进程的事件后，调用进程创建原语Creat()创建新进程。
进程的创建过程：
申请空白PCB 为新进程分配资源 初始化进程控制块 将新进程插入就绪队列
进程的终止
引起进程终止的事件
（1）正常结束
（2）异常结束
（3）外界干预
终止过程：
①PCB集合中检索出该进程的PCB：并从该进程的PCB中读出该进程的状态
②若被终止进程正处于执行状态，立即剥夺CPU
③终止其所有子孙进程：以防止它们成为不可控的进程；
④将被终止的进程所拥有的全部资源，或归还给其父进程，或归还给系统；
⑤将被终止进程的PCB从所在队列（或链表）中移出：等待其他程序来搜集信息
进程的阻塞与唤醒
引起进程阻塞与唤醒的事件
向系统请求共享资源失败
等待某种操作的完成
新数据尚未到达
等待新任务的到达
阻塞过程：
调用阻塞原语block阻塞自己；
将PCB中的状态改为阻塞，并加入阻塞队列；
转调度程序进行重新调度
进程的唤醒：
调用wakeup原语唤醒等待该事件的进程
阻塞进程从等待该事件的阻塞队列中移出；
置进程状态为就绪态，将PCB插入到就绪队列中
进程的挂起与激活
进程的挂起过程：
当出现引起进程挂起的事件时，系统利用挂起原语suspend将指定进程或处于阻塞的进程挂起。
先检查被挂起进程的状态：
- 若处于活动就绪，则改为静止就绪
- 若处于活动阻塞，则改为静止阻塞；
- 若挂起的进程正在执行，则重新进行进程调度
进程的激活过程：
当发生激活进程的事件时，系统利用激活原语active将指定进程激活
激活原语先将进程从外存调入内存；
然后检查该进程的状态：
- 若为静止就绪，则改为活动就绪；
- 若处于静止阻塞，则改为活动阻塞
