第2章进程的描述与控制讲解.ppt

第二章　进程的描述与控制 重点 理解进程的含义 理解和掌握同步的概念 经典进程同步问题 难点 会写进程同步问题的算法 知识点 进程、线程、进程的特征、PCB、进程控制、进程状态转换、 进程同步、进程通信 2.1 前趋图和程序执行 2.1.1 前趋图 2.1.2 程序顺序执行 2.1.3 程序并发执行 2.1.1 前趋图(Precedence Graph) 定义 有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。 结点：表示程序段或进程，乃至一条语句； 有向边：表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“→” →={(Pi, Pj)|Pj 开始前 Pi 必须完成}, 若(Pi, Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，Pj是Pi的直接后继。没有前趋的结点称为初始结点(Initial Node)，没有后继的结点称为终止结点(Final Node)。每个结点有一个权值(Weight)，表示它所含有的程序量或执行时间。 2.1.1 前趋图 2.1.1 前趋图 注意：前趋图中必须不存在循环，但下图中却有着下述的前趋关系： S2→S3，S3→S2 2.1.2 程序顺序执行 程序的顺序执行 把一个应用程序分成若干个程序段，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一操作(程序段)执行完后，才能执行后继操作。 例，将可用户任务抽象为： 输入数据→处理数据→输出结果 2.1.2 程序顺序执行 执行实例 S1: a:=x+y； S2: b:=a-5； S3: c:=b+1； 其中，语句S2必须在语句S1之后(即a被赋值)才能执行；同样，语句S3也只能在b被赋值后才能执行。 2.1.2 程序顺序执行 程序顺序执行时的特征 顺序性 按照程序结构所指定的次序（可能有分支或循环） 封闭性 独占全部资源，计算机的状态只由该程序的控制逻辑所决定 可再现性 初始条件相同则结果相同。如：可通过空指令控制时间关系 2.1.3 程序并发执行 例 2.1.3 程序并发执行 例，对于具有下述四条语句的程序段 S1: a∶=x+2 S2: b∶=y+4 S3: c∶=a+b S4: d∶=c+b 2.1.3 程序并发执行 程序并发执行时的特征 间断(异步)性 走走停停，一个程序可能走到中途停下来，失去原有的时序关系； 失去封闭性 共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。 失去可再现性 失去封闭性 →失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征 2.1.3 程序并发执行 例，程序A和B，共享变量N，它们的功能如下： 2.1.3 程序并发执行 2.1.3 程序并发执行 并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。(没有考虑执行速度的影响。) 程序 P(i) 针对共享变量的读集和写集 R(i)和W(i) 条件：任意两个程序P(i)和P(j)，有： R(i)?W(j)=?; W(i)?R(j)= ?; W(i)?W(j)= ?; 前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。 2.1.3 程序并发执行 程序并发执行的条件 若两个程序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 2.1.3 程序并发执行 2.2 进程的描述 进程（Process） 描述性定义：计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程称之为进程。 如何理解进程概念？ 进程与程序有何差别？ 2.2 进程的描述 2.2 进程的描述 进程的核心思想 进程是某种类型的一个活动，它有程序、输入、输出和状态。 在分时操作系统中，单个CPU被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，转