第二章进程的描述与控制
- 格式：ppt
- 大小：246.50 KB
- 文档页数：73
下载文档原格式
合集下载
2进程的描述和控制
第二单元进程的描述和控制1)进程为什么很重要？程序不能独立运行，作为资源分配和独立运行的单位是进程.操作系统的四大特征也都是基于进程形成的。
2)程序的顺序执行及其特征特性：顺序性，封闭性，可再现性。
3)前趋图直接前趋,直接后继,初始结点,终止结点,重量或权值4)程序的并发执行及其特征特性：间断性，失去封闭性，不可再现性。
5)为什么引入进程？程序的并发执行，失去了封闭性和再现性，程序无意义。
为了对并发执行的程序加以描述和控制，引入了“进程”6)进程的定义:进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位7)进程的特征:1）结构特征2 ）动态性3 ）并发性4 ）独立性5 ）异步性8)进程实体由程序段、数据段、进程控制块（PCB）构成。
9)进程与程序的主要区别:*程序是指令的集合，本身没有任何运行的含义，是一个静态概念；而进程是程序在处理机上的一次执行过程，是一个动态概念。
*程序的存在是永久的；而进程是有生命期的，它因创建而产生，因调度而执行，因缺少资源而暂停，因撤消而消亡。
* 程序仅是指令的有序集合；而进程则由程序段、数据段、进程控制块组成。
*进程与程序之间不是一一对应的，即同一程序可同时运行于若干个不同的数据集合上，它将属于不同的进程；而一个进程也可以执行多个程序。
10)进程的三种基本状态:运行、就绪和阻塞11)线程与进程的比较：［p77］调度的基本单位，并发性，拥有资源，独立性，系统开销，支持多处理机系统。
12)引起进程堵塞或被唤醒的事件：＊向系统亲求共享资源失败；＊等待某种操作的完成；＊新数据尚未到达；＊等待新任务的到达；13)进程控制：是进程管理中的最基本的功能，主要包括创建新进程，终止已完成的进程，将因发生异常情况而无法继续运行的进程置于堵塞状态，负责进程运行中的状态转换等功能。
14)引入挂起状态的原因终端用户的请求: 用户发现可疑处，要暂停。
父进程请求：父进程要挂起子进程负荷调节的需要系统负载过重操作系统的需要检查资源使用情况15)PCB的作用和特点PCB是操作系统中最重要的数据结构，是进程存在的唯一标志；13）PCB中的信息14）PCB的组织方式：链接方式、索引方式15）进程控制：系统态和用户态，原语（Primitive）16）信号量机制原子操作：wait(S)和signal(S)来访问。
第二章 进程的描述和控制
• 进程唤醒过程
– 当被阻塞进程所期待的事件出现时，如I/O完成 或其所期待的数据已经到达，则由有关进程(比 如，用完并释放了该I/O设备的进程)调用唤醒 原语wakeup( )，将等待该事件的进程唤醒。唤 醒原语执行的过程是：首先把被阻塞的进程从 等待该事件的阻塞队列中移出，将其PCB中的 现行状态由阻塞改为就绪，然后再将该PCB插 入到就绪队列中。
compete and/or cooperate
相互协作的进程(线程) 如何正确执行？
进程间通信
与时间有关的错误——例子1 • 飞机订票系统，两个终端，运行T1、T2进 程
T1: ... read(x); if x>=1 then x:=x-1; write(x); ...
T2: ... read(x); if x>=1 then x:=x-1; write(x); ...
• 处理器怎么知道当前是操作系统还是一般 用户程序在运行呢?
• 处理器状态
– 处理器状态标志: 管理状态（特权状态、系统 模式、特态或管态）和用户状态（目标状态、 用户模式、常态或目态)。处理器状态的转换。 – 处理器处于管理状态时，程序可以执行全部指 令，使用所有资源，具有改变处理器状态的能 力；处理器处于用户状态时，程序只能执行非 特权指令
• 特权指令与非特权指令
– 从资源管理和控制程序执行的角度出发，必须 把指令系统中的指令分作两部分：特权指令和 非特权指令。 – 特权指令是指只能提供给操作系统的核心程序 使用的指令，如启动I/O设备、设置时钟、控制 中断屏蔽位、清主存、建立存储键，加载PSW 等。
• 程序状态字寄存器
– 计算机如何知道当前处于何种工作状态？这时 能否执行特权指令？通常操作系统都引入程序 状态字PSW（Program Status Word）来区别 不同的处理器工作状态 – PSW用来控制指令执行顺序并保留和指示与程 序有关的系统状态，主要作用是实现程序状态 的保护和恢复 – 每个程序都有一个与其执行相关的PSW，每个 处理器都设置一个PSW寄存器。程序占有处理 器执行，它的PSW将占有PSW寄存器
操作系统第二章PPT课件
-
12
2.1.3 进程挂起
有挂起状态的进程转换图
创建 准许 就绪
激活 事件 发生
挂起
就绪 挂起
分派 超时
运行 准许
等待 事件
消失
(a) 带有一个挂起状态
创建
准许
准许
挂起
就绪， 挂起
事件 发生
阻塞 挂起
激活 挂起
激活
就绪
事件 发生 阻塞
分派 超时
运行
等待 事件
释放
-
消失
(b) 带有两个挂起状态
13
2.1.3 进程挂起
-
38
2.4.1 线程及其管理
2.线程的定义及特征
线程是进程内的一个相对独立的、可独立调度 和指派的执行单元。
线程具有以下性质：
• 线程是进程内的一个相对独立的可执行单元。
• 线程是操作系统中的基本调度单元 。
• 一个进程中至少应有一个线程 。
• 线程并不拥有资源，而是共享和使用包含它的 进程所拥有的所有资源。
• ③当运行中获取用户程序提出的某种请求后，OS可以 代用户程序产生进程以实现某种功能，使用户不必等 待。
• ④基于应用进程的需要，由已存在的进程产生另一个 进程，以便使新程序以并发运行方式完成特定任务。
-
5
2.1.1 进程产生和终止
2.进程终止 导致进程终止的事件大致有14种 ：正常 结束 、超时限制 、内存不足 、超界 、 保护错误 、算术错误 、超越时限 、I/O 失败 、非法指令 、特权指令 、错误使 用数据 、操作员或OS干预 、父进程终 止 、父进程需要 。
-
27
2.3.1 执行模式
大多数处理器都至少支持两种执行模式， 一种是同操作系统有关的模式，另一种则 是同用户程序有关的模式。较低特权模式 称为用户模式。较高特权模式指系统模式、 控制模式或内核模式。内核是操作系统中 最核心功能的集合。
操作系统第二章进程的描述与控制题目
操作系统第⼆章进程的描述与控制题⽬1-1. 下⾯对进程的描述中，错误的是。
A.进程是动态的概念B. 进程执⾏需要处理机C.进程是有⽣命周期的D. 进程是指令的集合【答案】D动态的，有⽣命周期的。
【解析】【解析】程序是指令的集合。
⽽进程是程序的⼀次执⾏，是动态的，有⽣命周期的。
1-2. 分配到必要的资源并获得处理机时的进程状态是 ()A. 就绪状态B. 执⾏状态C. 阻塞状态D. 撤消状态【答案】B【解析】分配到必要地资源获得处理机时的进程状态是执⾏状态。
1-3.程序的顺序执⾏通常在①的⼯作环境中，具有以下特征②。
程序的并发执⾏在③的⼯作环境中，具有如下特征④。
A. 单道程序B.多道程序C. 程序的可再现性D. 资源共享【答案】①A ②C ③B ④D。
【解析】程序的顺序执⾏通常在单道程序的⼯作环境中，具有程序结果的可再现性特征；程序的并发执⾏在多道程序的⼯作环境中，具有共享资源的特征。
1-4. 下列进程状态变化中，变化是不可能发⽣的A. 运⾏——就绪B.运⾏—— 等待C. 等待——运⾏D. 等待——就绪【答案】C【解析】当调度程序为某就绪状态的进程分配了处理机时，该进程便由就绪状态变为执⾏状态；正在执⾏的进程因等待发⽣某事件⽽⽆法执⾏时，该进程由执⾏状态变为等待状态；当处于等待状态的进程所等待的事件发⽣时，该进程由等待状态变为就绪状态；正在执⾏的进程如因时间⽚⽤完⽽暂停执⾏，该进程由执⾏状态变为就绪状态。
等待——运⾏不可能发⽣，就绪—— 等待不可能发⽣。
运⾏不可能发⽣，就绪唯⼀的双向箭头是运⾏运⾏——就绪，就绪——运⾏唯⼀的双向箭头是1-5. 当时，进程从执⾏状态转变为就绪状态。
A. 进程被调度程序选中B. 时间⽚到C. 等待某⼀事件D.等待的事件发⽣【答案】B。
【解析】正在执⾏的进程，如因时间⽚⽤完⽽暂停执⾏，则该进程由执⾏状态转变为就绪状态。
就绪——运⾏ C. 等待某⼀事件运⾏—— 阻塞 D.等待的事件发⽣等待——就绪A. 进程被调度程序选中，进程被调度程序选中，就绪1-6. 如果系统中有n个进程，则就绪队列中进程的个数最多为。
【操作系统】《计算机操作系统》汤小丹第2章进程的描述和控制
【操作系统】《计算机操作系统》汤⼩丹第2章进程的描述和控制博主：海底淤泥1.什么是前趋图？为什么要引⼊前趋图？ 前趋图：⼀个有向⽆循环图，它⽤于描述进程之间的先后顺序 作⽤：更好描述程序的顺序和并发执⾏情况2.试画出下⾯四条语句的前趋图S1:a=x+y S2:b=z+1 S3:c=a-b S4:w=c+1 S1->S3 S2->S3 S3->S43.为什么程序并发执⾏会产⽣间断特征？ 程序在并发执⾏时，由于它们共享系统资源，以及为完成同⼀项任务相互合作，⾄使在这些并发程序之间形成了相互制约的关系4.程序并发执⾏时为什么会失去封闭性和可再现性？ 失去封闭性：当系统存在着多个可以并发执⾏的程序时，系统中的各种资源将为它们所共享，⽽这些资源的状态也由这些程序来改变，导致其中任意程序运⾏时，其环境都必然会受到其他程序的影响。
失去可再现性：程序并发执⾏时，由于失去了封闭性，其计算结果必然将与并发程序的执⾏速度有关，从⽽使程序的执⾏失去了可再现性5.在操作系统中为什么要引⼊进程的概念？它会产⽣什么影响？ 为了使程序并发执⾏，并且可以对并发执⾏的程序加以描述和控制，⼈们引⼊了“进程”的概念。
影响：使程序并发执⾏，进程实体和其他进程实体并发执⾏6.试从动态性、并发性、和独⽴性上⽐较进程和线程 动态性：进程实体有⼀定⽣命期，是动态的；⽽程序是⼀组有序指令集合，并存放在某种介质上，其本⾝不具有活动意义，是静态的 并发性：进程可以并发执⾏，没有PCB的程序是不能并发执⾏的 独⽴性：进程实体是⼀个能独⽴运⾏，独⽴获得资源和独⽴接受调度的基本单位。
未建⽴PCB的程序不能作为⼀个独⽴的单位参与运⾏7.试说明PCB的作⽤具体表现在什么⽅⾯，为什么说PCB是进程存在的唯⼀标志？ PCB描述进程是基本情况和活动过程，进⽽控制和管理进程。
创建进程：创建进程实体的PCB 撤销进程：撤销进程实体的PCB8.PCB提供了进程管理和进程调度所需要的哪些信息？1.进程标识符2.处理机状态3.进程调度信息4.进程控制信息9.进程控制块的组织⽅式有哪⼏种？1.线性⽅式2.连接⽅式3.索引⽅式10.何谓操作系统内核？内核的主要功能是什么？ 通常将⼀些硬件紧密相关的模块、各种常⽤设备的驱动程序以及运⾏频率较⾼的模块，都安排在紧靠硬件的软件层次中，将它们常驻内存，被称为操作系统内核 功能：1.对重要软件进⾏保护，防⽌遭到其他程序的破坏 2.提⾼OS的运⾏效率11.试说明进程在三个基本状态之间转换的经典原因 就绪->执⾏：进程调度 执⾏->就绪：时间⽚完 执⾏->阻塞：I/O请求 阻塞->就绪：I/O完成12.为什么要引⼊挂起状态？该状态有哪些性质？ 原因：1.终端⽤户的需要 2.⽗进程的请求 3.负荷调节的需要 4.操作系统的需要 性质：1.若程序正在执⾏，将暂停执⾏ 2.若原本处于就绪状态，则该程序不接受调度13.在进⾏进程切换时，所要保存的处理机状态信息有哪些？1.通⽤寄存器2.指令计数器3.程序状态字PSW4.⽤户栈指针14.试说明引起进程创建的主要事件。
操作系统课件 第2章 进程
第二章 进 程 管 理
对于具有下述四条语句的程序段： S1: a∶=x+2 S2: b∶=y+4 S3: c∶=a+b S4: d∶=c+b 请画出前趋关系图。
S1 S3 S2 S4
第二章 进 程 管 理
2.2 程序并发执行时的特征
1) 间断性 相互制约性)－后面的模块等待前面的模块 间断性(相互制约性 － 相互制约性 传来的结果，然后才执行（如打印模块等待 计算模块完成）。走走停停。 2) 失去封闭性 ：多个程序共享系统中的各种资源， 因而这些资源的状态将由多个程序来改变， 致使程序的运行已失去了封闭性。 结果是一个程序运行时会受到另一个程序的 结果是 影响。 3) 不可再现性 ：程序在并发执行时，由于失去了封 闭性，也将导致失去其可再现性
第二பைடு நூலகம் 进 程 管 理
新进程
接纳
就绪 时间片完 I/O完成 进程调度
阻塞 I/O请求
执行
完成
结束
图 2-5 进程的三种基本状态及其转换
(教材讲5种)
第二章 进 程 管 理
作业调度
作业后备队列
阻塞队列
外存
进程就绪队列
一些 阻塞队列
内存
处理器 (CPU)
第二章 进 程 管 理
3.7五状态 五状态进程模型 五状态
第二章 进 程 管 理
3.4进程与程序的区别 进程与程序的区别
程序是静态的， 1)程序是静态的 进程是动态的; 是根本区别） 1)程序是静态的，进程是动态的;（是根本区别） 程序是有序代码的集合；进程是程序的执行。 程序是有序代码的集合；进程是程序的执行。 2)进程和程序不是一一对应的 2)进程和程序不是一一对应的 ; • 一个程序可对应多个进程 即多个进程可执行同一程序 ; 一个程序可对应多个进程,即多个进程可执行同一程序 • 一个进程可以执行一个或几个程序 3)进程是暂时的 程序的永久的：进程是一个状态变化的过程， 进程是暂时的， 3)进程是暂时的，程序的永久的：进程是一个状态变化的过程， 程序可长久保存。 程序可长久保存。 4)进程与程序的组成不同 进程的组成包括程序、 进程与程序的组成不同： 4)进程与程序的组成不同：进程的组成包括程序、数据和进程 控制块（即进程状态信息）。 控制块（即进程状态信息）。 5)进程具有创建其他进程的功能 而程序没有。 进程具有创建其他进程的功能， 5)进程具有创建其他进程的功能，而程序没有。
第二章、进程的描述与控制
第⼆章、进程的描述与控制第⼆章、进程的描述与控制2.1 前趋图和程序执⾏2.1.1 前趋图概念：所谓前趋图：指⼀个有向⽆循环图（DAG）,它⽤于描述进程之间执⾏的先后顺序。
2.1.2 程序顺序执⾏特征：顺序性封闭性：指程序在封闭的环境中运⾏，程序运⾏时独占全机资源，资源的状态只有本程序才能改变，程序⼀旦开始执⾏，其执⾏结果不受外界因素影响可再现性：只要条件相同还会得到相同的执⾏结果。
2.1.3 程序并发执⾏特征：间断性失去封闭性不可在现性2.2进程的描述2.2.1 进程的定义和特征定义为了使程序并发执⾏，并且可以对并发执⾏的程序加以描述和控制，⼈们引⼊了进程的概念。
为了使参与并发执⾏的每个程序都能独⽴运⾏，在操作系统中必须为之分配⼀个专门的数据结构，称为进程控制块（PCB）。
系统利⽤PCB 来描述进程的基本情况和活动过程，进⽽控制和管理进程。
因此进程的定义为：由程序段、相关的数据段和由程序段、相关的数据段和PCB三部分构成的进程实体。
⽐较典型的定义有：进程是程序的⼀次执⾏进程是⼀个程序及其数据在处理机上顺序执⾏时所发⽣的活动进程是具有独⽴功能的程序在⼀个数据结合上运⾏的过程，它是系统进⾏资源分配和调度的⼀个独⽴单位。
进程的特征动态性并发性独⽴性异步性2.2.2 进程的基本状态以及转换进程三种基本状态由于多个进程在并发执⾏时共享系统资源，致使他们在运⾏过程中呈现间断性的运⾏规律，所以进程在⽣命周期内可能具有不同状态。
⼀般⽽⾔，每个进程⾄少应处于以下三种基本状态：就绪（Ready）状态指进程已处于准备好运⾏的状态，即进程已分配到除CPU以外的所有必要资源后，只要再获得CPU就可以⽴即执⾏。
如果有多个就绪状态的进程。
就绪队列通常按照⼀定的策略排成⼀个队列，称该队列为就绪队列执⾏(Running)状态指进程已经获得CPU，其程序正在执⾏的状态。
在单处理机系统中，只有⼀个进程处于执⾏状态，⽽多处理机系统则有多个进程处于阻塞（Block）状态指正在执⾏的进程由于发⽣某事件（如I/O请求、申请缓冲区失败等）暂时⽆法继续执⾏时的状态，即进程的执⾏受到了阻塞。
计算机操作系统原理 第二章 进程描述与控制
13
两个并发程序方案
设有一台标准输入设备（键盘），和一台标准 输出设备（显示器或打印机），输入程序负责 从标准设备中读取一个字符，送缓冲区中。输 出程序从缓冲区中取数据，送标准设备输出。
14
两个并发程序方案
f
标准输入 （键盘）
输入程序 缓冲区 输出程序
g
标准输出 （打印机）
15
两个并发程序方案
6
前趋图
前趋图(Precedence Graph)是一个有向无循环图，记 为DAG(Directed Acyclic Graph)，用于描述进程之间执行 的前后关系。 结点：一个程序段或进程，乃至一条语句
有向边：偏序或前趋关系
把没有前趋的结点称为初始结点(Initial Node) 没有后继的结点称为终止结点(Final Node) 每个结点还具有一个重量(Weight)，用于表示该结点 所含有的程序量或结点的执行时间。
38
进程状态模型
进程状态转换
原状态 创建 OS根据作业控制请求； 分时系统用户登录； 进程产生子进程而创 建进程 转换后状态 运行 × 就绪 × 阻塞 × 终止 ×
创建
×
×
OS准备运 行新的进 程
×
×
（转下表）
39
进程状态模型
原状态 创建 运行 × 运行 × 转换后状态 就绪 超时；OS服务 请求；OS响应 具有更高优先 级的进程；进 程释放控制 阻塞 OS服务 请求； 资源请 求；事 件请求 终止 进程完 成，进 程夭折
2.5 进程同步 2.6 经典进程的同步问题 2.7 管程机制 2.8 进程通信
3
2.1 进程描述
2.1.1 程序的顺序执行 2.1.2 程序的并发执行 2.1.3 进程的定义
计算机操作系统(第四版)1-8章 课后答案(全)
第一章操作系统引论1.设计现代OS的主要目标是什么？答：方便性，开放性，有效性，可扩充性2.OS的作用可表现在哪几个方面？答：OS作为用户与计算机硬件系统之间的接口；OS作为计算机系统资的管理者；OS实现了对计算机资源的抽象。
3.为什么说操作系统实现了对计算机资源的抽象？答：OS首先在裸机上覆盖一层1/0设备管理软件，实现了对计算机硬件操作的第一层次抽象；在第一层软件上再覆盖文件管理软件，实现了对硬件资源操作的第二层次抽象。
0s通过在计算机硬件上安装多层系统软件，增强了系统功能，隐藏了对硬件操作的细节，由它们共同实现了对计算机资源的抽象。
4·说明推动分时系统形成和发展的主要动力是什么？答：主要动力是提高资源利用率和系统吞吐里，为了满足用户对人一机交互的需求和共享主机。
5.何谓脱机I/O和联机I/O？答：脱机1/0是指事先将装有用户程序和数据的纸带或卡片装入纸带输入机或卡片机，在外围机的控制下，把纸带或一片上的数据或程序输入到殖带上。
该方式下的输入输出由外围机控制完成，是在脱离主机的情况下进行的。
而耽机1/0方式是指程序和数据的輸入输出都是在主机的直接控制下进行的。
6.试说明推动分时系统形成和发展的主要动力是什么？答：推动分时系统形成和发展的主要动力是更好地满足用户的需要。
主要表现在：CPU的分时使用缩短了作业的平均周转时间；人机交互能力使用户能直接控制自己的作业；主机的共享使多用户能同时使用同一台计算机，独立地处理自己的作业。
7.实现分时系统的关键问题是什么？应如何解决？答：关键问题是当用户在自己的终端上键入命令时，系统应能及寸接收并及时处理该命令，在用户能接受的时采内将结果返回给用户。
解决方法：针对及时接收问题，可以在系统中设路多路卡，健主机能同时接收用户从各个终端上轮入的数据；为每个终端配路缓冲区，暂存用户捷入的命令或教据。
针对反时处理问题，应便所有的用户作业都直接进入内存，并且为每个作业分配一个时间片，允许作业只在自己的时间片内运行，这样在不长的时间内，能使每个作业都运行一次。
计算机操作系统第四版教案
(1) 用户独占全机，即一台计算机的全部资源由上机用 户所独占。
(2) CPU等待人工操作。当用户进行装带(卡)、卸带(卡) 等人工操作时，CPU及内存等资源是空闲的。
整理课件 13
第一章 操作系统引论
2. 脱机输入/输出(Off-Line I/O)方式 为了解决人机矛盾及CPU和I/O设备之间速度不匹配的矛 盾，20世纪50年代末出现了脱机I/O技术。该技术是事先将 装有用户程序和数据的纸带装入纸带输入机，在一台外围机 的控制下，把纸带(卡片)上的数据(程序)输入到磁带上。当 CPU需要这些程序和数据时，再从磁带上高速地调入内存。
整理课件 9
第一章 操作系统引论
图1-2 I/O软件隐藏了I/O操作实现的细节
整理课件 10
第一章 操作系统引论
1.1.3 推动操作系统发展的主要动力 1．不断提高计算机资源利用率 2. 方便用户 3. 器件的不断更新换代 4. 计算机体系结构的不断发展 5. 不断提出新的应用需求
整理课件 11
整理课件
2
第一章 操作系统引论
第一章 操作系统引论
1.1 操作系统的目标和作用 1.2 操作系统的发展过程 1.3 操作系统的基本特性 1.4 操作系统的主要功能 1.5 OS结构设计 习题
整理课件 3
第一章 操作系统引论
1.1 操作系统的目标和作用
操作系统的目标与应用环境有关。例如在查询系统中所 用的OS，希望能提供良好的人—机交互性；对于应用于工 业控制、武器控制以及多媒体环境下的OS，要求其具有实 时性；而对于微机上配置的OS，则更看重的是其使用的方 便性。
(1) 人—机交互。 (2) 共享主机。
整理课件 26
第一Байду номын сангаас 操作系统引论
(2) CPU等待人工操作。当用户进行装带(卡)、卸带(卡) 等人工操作时，CPU及内存等资源是空闲的。
整理课件 13
第一章 操作系统引论
2. 脱机输入/输出(Off-Line I/O)方式 为了解决人机矛盾及CPU和I/O设备之间速度不匹配的矛 盾，20世纪50年代末出现了脱机I/O技术。该技术是事先将 装有用户程序和数据的纸带装入纸带输入机，在一台外围机 的控制下，把纸带(卡片)上的数据(程序)输入到磁带上。当 CPU需要这些程序和数据时，再从磁带上高速地调入内存。
整理课件 9
第一章 操作系统引论
图1-2 I/O软件隐藏了I/O操作实现的细节
整理课件 10
第一章 操作系统引论
1.1.3 推动操作系统发展的主要动力 1．不断提高计算机资源利用率 2. 方便用户 3. 器件的不断更新换代 4. 计算机体系结构的不断发展 5. 不断提出新的应用需求
整理课件 11
整理课件
2
第一章 操作系统引论
第一章 操作系统引论
1.1 操作系统的目标和作用 1.2 操作系统的发展过程 1.3 操作系统的基本特性 1.4 操作系统的主要功能 1.5 OS结构设计 习题
整理课件 3
第一章 操作系统引论
1.1 操作系统的目标和作用
操作系统的目标与应用环境有关。例如在查询系统中所 用的OS，希望能提供良好的人—机交互性；对于应用于工 业控制、武器控制以及多媒体环境下的OS，要求其具有实 时性；而对于微机上配置的OS，则更看重的是其使用的方 便性。
(1) 人—机交互。 (2) 共享主机。
整理课件 26
第一Байду номын сангаас 操作系统引论
汤小丹计算机操作系统官方课件课件
24
第二章 进程的描述与控制
图2-6 进程的五种基本状态及转换
25
第二章 进程的描述与控制
2.2.3 挂起操作和进程状态的转换 1. 挂起操作的引入 引入挂起操作的原因，是基于系统和用户的如下需要： (1) 终端用户的需要。 (2) 父进程请求。 (3) 负荷调节的需要。 (4) 操作系统的需要。
21
第二章 进程的描述与控制
图2-5 进程的三种基本状态及其转换
22
第二章 进程的描述与控制
3. 创建状态和终止状态 1) 创建状态 如前所述，进程是由创建而产生。创建一个进程是个很 复杂的过程，一般要通过多个步骤才能完成：如首先由进程 申请一个空白PCB，并向PCB中填写用于控制和管理进程的 信息；然后为该进程分配运行时所必须的资源；最后，把该 进程转入就绪状态并插入就绪队列之中。但如果进程所需的 资源尚不能得到满足，比如系统尚无足够的内存使进程无法 装入其中，此时创建工作尚未完成，进程不能被调度运行， 于是把此时进程所处的状态称为创建状态。
27
第二章 进程的描述与控制
3. 引入挂起操作后五个进程状态的转换 如图2-8示出了增加了创创建和终止状态后，在进程状态转 换时，与图2-7所示的进程五状态转换相比较，要增加考虑 下面的几种情况： (1) NULL→创建： (2) 创建→活动就绪： (3) 创建→静止就绪： (4) 执行→终止：
23
第二章 进程的描述与控制
2) 终止状态 进程的终止也要通过两个步骤：首先，是等待操作系统 进行善后处理，最后将其PCB清零，并将PCB空间返还系统。 当一个进程到达了自然结束点，或是出现了无法克服的错误， 或是被操作系统所终结，或是被其他有终止权的进程所终结， 它将进入终止状态。进入终止态的进程以后不能再执行，但 在操作系统中依然保留一个记录，其中保存状态码和一些计 时统计数据，供其他进程收集。一旦其他进程完成了对其信 息的提取之后，操作系统将删除该进程，即将其PCB清零， 并将该空白PCB返还系统。图2-6示出了增加了创建状态和终 止状态后进程的五种状态及转换关系图。
第二章 进程的描述与控制
图2-6 进程的五种基本状态及转换
25
第二章 进程的描述与控制
2.2.3 挂起操作和进程状态的转换 1. 挂起操作的引入 引入挂起操作的原因，是基于系统和用户的如下需要： (1) 终端用户的需要。 (2) 父进程请求。 (3) 负荷调节的需要。 (4) 操作系统的需要。
21
第二章 进程的描述与控制
图2-5 进程的三种基本状态及其转换
22
第二章 进程的描述与控制
3. 创建状态和终止状态 1) 创建状态 如前所述，进程是由创建而产生。创建一个进程是个很 复杂的过程，一般要通过多个步骤才能完成：如首先由进程 申请一个空白PCB，并向PCB中填写用于控制和管理进程的 信息；然后为该进程分配运行时所必须的资源；最后，把该 进程转入就绪状态并插入就绪队列之中。但如果进程所需的 资源尚不能得到满足，比如系统尚无足够的内存使进程无法 装入其中，此时创建工作尚未完成，进程不能被调度运行， 于是把此时进程所处的状态称为创建状态。
27
第二章 进程的描述与控制
3. 引入挂起操作后五个进程状态的转换 如图2-8示出了增加了创创建和终止状态后，在进程状态转 换时，与图2-7所示的进程五状态转换相比较，要增加考虑 下面的几种情况： (1) NULL→创建： (2) 创建→活动就绪： (3) 创建→静止就绪： (4) 执行→终止：
23
第二章 进程的描述与控制
2) 终止状态 进程的终止也要通过两个步骤：首先，是等待操作系统 进行善后处理，最后将其PCB清零，并将PCB空间返还系统。 当一个进程到达了自然结束点，或是出现了无法克服的错误， 或是被操作系统所终结，或是被其他有终止权的进程所终结， 它将进入终止状态。进入终止态的进程以后不能再执行，但 在操作系统中依然保留一个记录，其中保存状态码和一些计 时统计数据，供其他进程收集。一旦其他进程完成了对其信 息的提取之后，操作系统将删除该进程，即将其PCB清零， 并将该空白PCB返还系统。图2-6示出了增加了创建状态和终 止状态后进程的五种状态及转换关系图。
操作系统第二章_dsf
•
•
如何协调各程序的执行顺序？
多个执行程序共享系统资源，程序之 间可能会相互影响，甚至影响输出结 果。 选择哪些、多少个程序进入内存执行？ 内存中的执行程序谁先执行？ 内存如何有效分配？
• • •
操作系统
第二章 进程的描述与控制
2.2 进程的描述
• 通常的程序不能参与并发执行，为了让程序 能并发执行，人们引入进程的概念对并发执行 的程序加以描述和控制。
操作系统
第二章 进程的描述与控制
顺序执行与并发执行特征对比
I1 I2
输入1
C2
输入2 计算1
输入3 计算2 输出2
输入4 计算3 输出3
C1
P1
P2
输出1
• 1. 2. 3.
操作系统
程序的顺序执行 顺序性 封闭性 可再现性
程序的并发执行 间断性 失去封闭性 不可再现性
第二章 进程的描述与控制
程序的并发执行引发的问题
应当注意，前趋图中必须不存在循环，但在图 2-2(b)中却有
着下述的前趋关系：S2→S3, S3→S2
操作பைடு நூலகம்统
第二章 进程的描述与控制
2.1.2 程序的顺序执行及其特征
– 程序：源代码程序、目标程序和可执行程序； 例如：sample.cpp sample.obj sample.exe – 程序执行：编辑、编译、链接、执行
I1 I2 I3 I4
C1
C2
C3
C4
P1
P2
P3
P4
•图 2-3 并发执行时的前趋图
操作系统 第二章 进程的描述与控制
在该例中存在下述前趋关系：
Ii→Ci，Ii→Ii+1, Ci→Pi, Ci→Ci+1，Pi→Pi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间， 可以并发执行。 对于具有下述四条语句的程序段： • • • •
•
如何协调各程序的执行顺序？
多个执行程序共享系统资源，程序之 间可能会相互影响，甚至影响输出结 果。 选择哪些、多少个程序进入内存执行？ 内存中的执行程序谁先执行？ 内存如何有效分配？
• • •
操作系统
第二章 进程的描述与控制
2.2 进程的描述
• 通常的程序不能参与并发执行，为了让程序 能并发执行，人们引入进程的概念对并发执行 的程序加以描述和控制。
操作系统
第二章 进程的描述与控制
顺序执行与并发执行特征对比
I1 I2
输入1
C2
输入2 计算1
输入3 计算2 输出2
输入4 计算3 输出3
C1
P1
P2
输出1
• 1. 2. 3.
操作系统
程序的顺序执行 顺序性 封闭性 可再现性
程序的并发执行 间断性 失去封闭性 不可再现性
第二章 进程的描述与控制
程序的并发执行引发的问题
应当注意，前趋图中必须不存在循环，但在图 2-2(b)中却有
着下述的前趋关系：S2→S3, S3→S2
操作பைடு நூலகம்统
第二章 进程的描述与控制
2.1.2 程序的顺序执行及其特征
– 程序：源代码程序、目标程序和可执行程序； 例如：sample.cpp sample.obj sample.exe – 程序执行：编辑、编译、链接、执行
I1 I2 I3 I4
C1
C2
C3
C4
P1
P2
P3
P4
•图 2-3 并发执行时的前趋图
操作系统 第二章 进程的描述与控制
在该例中存在下述前趋关系：
Ii→Ci，Ii→Ii+1, Ci→Pi, Ci→Ci+1，Pi→Pi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间， 可以并发执行。 对于具有下述四条语句的程序段： • • • •
第2章 进程的描述和控制
引 起 阻 塞 和 唤 醒 的 事 件
请求系统服务
启动某种操作
新数据尚未到 无新工作可做
• 进程阻塞过程 –正在执行的进程，发生上述事件时， 自身调用有关阻塞原语，进入等待队 列。进程的主动性行为。 –进程由运行态变为阻塞态 –引起处理机调度。 –例如UNIX:暂停一段时间sleep；暂停 并等待信号pause；等待子进程暂停或 终止wait。
1 2 3
• 顺序执行的特征： – 顺序性：按照程序结构所指定的次序 执行（可能有分支或循环） – 封闭性：独占全部资源，计算机的状 态只由于该程序的控制逻辑所决定， 结果不受外界因素的影响 – 可再现性：初始条件相同则结果相同。
2）程序的并发执行
• 引入并发执行的目的是为了提高资源利用率。 • 并发执行的特征（在不加入任何系统控制情况 下）： – 间断性：表现为“走走停停”，一个程序可 能走到中途停下来，失去原有的时序关系； – 失去封闭性：共享资源，受其他程序的控制 逻辑的影响。如：一个程序写到存储器中的 数据可能被另一个程序修改，失去原有的不 变特征。 – 失去可再现性：失去封闭性 －>失去可再现 性；外界环境在程序的两次执行期间发生变 化，失去原有的可重复特征。
执行指针 就绪队列指针
PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 PCB9 4 3 0 8
阻塞队列指针 空闲队列指针
7 9 0 0
索引方式
执行指针
PCB1 PCB2
PCB3
就绪表指针
PCB4 PCB5 PCB6
阻塞表指针
PCB7
2.2
进程控制
• 进程管理中最基本功能是进程控制 • 进程控制任务： – 进程的创建、终止、进程状态的转变等 • 进程控制一般由OS内核的原语（primitive）来 实现。 – 原语：由若干条指令构成的“原子操作 (atomic operation)”过程，作为一个整 体而不可分割－－要么全都完成，要么全 都不做。 – 许多系统调用是原语。但并不是所有的系 统调用都是原语
计算机进程的描述与控制思维导图
软件同步机制:都没有解决让权等待，而且部分方 法还会产生死锁的情况
关中断
利用Tes - n -Se 指令实现互斥
硬件同步机制
利用 w 指令实现进程互斥
整型信号量
由于整型信号量没有遵循让权等待原则，记录型 允许负数，即阻塞链表
记录型信号量
进程同步机制
进程同步
D型信号量
进程控制
理解: D型号量的w i 和 i n 仅能对信号施 以加1或减1操作，意味着每次只能对某类临界 资源进行一个单位的申请或释放。当一次需要N 个单位时，便要进行N次w i 操作，这显然是低 效的，甚至会增加死锁的概率。此外，在有些情
进程是竞争计算机资源的基本单位，程序不是 进程是程序在数据集上的一次执行
程序是构成进程的组成部分，一个程序可对应多 个进程，一个进程可包括多个程序
进程的运行目标是执行所对应的程序
从静态看，进程由程序、数据和进程控制块（ P B）组成
就绪状态 ea
进程的三种基本状态
执行状态 n n
阻塞状态 lo
进程的基本状态及转换
进程的阻塞与唤醒
互斥——竞争 同步——协作
间接相互制约关系 直接相互制约关系
un ac
进程的挂起与激活
两种形式的制约关系
临界资源
进入区 n ec i
临界区 i ic ec i 退出区 i ec i
分区
剩余区 m n
ec i
1.空闲让进
2.忙则等待 3.有限等待
同步机制应遵循的规则
4.让权等待
基本概念
三种基本状态的转换 创建状态和终止状态
五状态进程模型
注意
阻塞态->运行态和就绪态->阻塞态这二种状态 转换不可能发生
操作系统第二章习题
第二章进程的描述与控制1、在单用户单任务环境下，用户独占全机，此时机内资源的状态，只能由运行程序的操作加以改变，此时的程序执行具有封闭性和可在现性特征。
2、并发进程之间的相互制约，是由于他们共享资源和相互合作而产生的，因而导致程序在并发执行时具有间断性或异步性特征。
3、程序并发执行与顺序执行是相比产生了一些新特征，分别是间断性、失去封闭性和不可再现性。
4、引入进程的目的是使程序能正确地并发执行，以提高资源利用率和系统吞吐量，而引入线程的目的是减少并发执行的开销，提高程序执行的并发程度。
5、进程由进程控制块（PCB）、程序段和数据段组成，其中PCB是进城存在的唯一标志。
6、进程最基本的特征是动态性和并发性，除此之外，它还有独立特征和异步性特征。
7、由于进程的实质是程序的一次执行，故进程有动态性的基本特征，该特征还表现在进程由创建而产生，由调度而执行，由撤销而消亡，即进程具有一定的生命期。
8、引入进程带来的好处提高资源利用率和增加系统吞吐量。
9、当前正在执行的进程由于时间片用完而暂停执行时，该进程应转变为就绪状态；若因发生某种事件而不能继续执行时，应转为阻塞状态；若因终端用户的请求而暂停执行时，他应转为静止就绪状态。
10、用户为阻止进程继续运行，应利用挂起原语，若进程正在执行，应转变静止就绪状态，以后，若用户要恢复期运行，应利用激活原语，此时进程应转变为活动就绪状态。
11、系统中共有5个用户进程，且当前CPU在用户态下执行，则最多可有4个用户进程处于就绪状态，最多可有4个用户进程处于阻塞状态；若当前在核心态下执行，则最多可有4个用户进程处于就绪状态，最多可有5个用户进程处于阻塞状态。
12、为了防止OS本身及关键数据（如PCB等），遭受到应用程序有意或无意的破坏，通常也将处理机的执行状态分成用户态和系统态两种状态。
13、进程同步主要是对多个相关进程在执行次序上进行协调。
14、同步机制应遵循的准则有空闲让进、忙则等待、有限等待和让权等待。
计算机操作系统(第四版)汤小丹-期末复习知识点详尽汇总
具有作业调度和进程调度的调度队列模型子主题资源利用率：CPU利用率=CPU有效工作时间/CPU总工作时间平衡性：协调CPU和IO，使系统资源都经常处于忙碌状态策略强制执行高优先权优先，重要计算先来先服务短作业优先的优缺点实时调度的算法把内存中暂时不能运行的程序，或暂时不用的程序和数据换出到外存1.将逻辑地址的页号和页表长度进行比较，如果页号大于页表长度，发生越界中断2.如果小于页表长度，则页表始址+页号*位置得到物理块号3.物理块号*页面大小+页内地址=得到物理地址快表、联想寄存器、TLB1.将逻辑地址的页号与页表寄存器的页表长度进行比较，如果页号大于页表长度，越界中断1.将逻辑地址的段号和段表长度进行比较，如果段表长度<段号，产生越界中断请求分页的内存分配（请求调入软件）最小物理块的确定：作业正常运行所需要的最小物理块内存分配策略固定分配局部置换：只分可变分配局部置换：先分可变分配全局置换：没有内存，可换他人物理块分配算法：如何为不同的进程分配物理块预测页策略：预计不久之后会被访问的页优先调入内存，可一次调入多页，但是预测效率低下请求调页策略：需要的页面不在内存，发出请求，一次调入一页从打开文件表的表目删除直接-->物理地址哈希文件目录管理的要求1.实现按名存取2.允许文件重名3.提高检索速度4.文件共享基本信息类使用信息类为每一个用户建立一个单独的用户文件目录缺点用户相互隔离，无法合作创建者不用链接创建一个Link文件，存有共享文件的路径非创建者，连接到Link1.顺序访问容易消除了磁盘的外碎片，提高了外存的利用率（内碎片是消除不了的，因为每个盘块的大小固定）显式的“显”在哪里：链接文件各盘块的指针显式地存放在内存的一张链接表隐式的“隐”在哪里：下一个盘块号存在于上一个盘块中，而不是显示地放在外存有多少扇区，优点：支持直接访问优点大大加快了对大型文件的查找速度分配和回收：与内存的动态分区分配算法相同。
操作系统(第四版)期末复习总结
操作系统（第四版）期末复习总结第一章操作系统引论1、操作系统是什么？操作系统为用户完成所有“硬件相关，应用无关“的工作，以给用户方便、高效、安全的使用环境1.1、定义：操作系统是一个大型的程序系统，它负责计算机的全部软、硬件资源的分配、调度工作，控制并协调多个任务的活动，实现信息的存取和保护。
它提供用户接口，使用户获得良好的工作环境。
1.2、目标（1）、方便性：配置OS后计算机系统更容易使用（2）、有效性：改善资源利用率；提高系统吞吐量（3）、可扩充性：OSde结构（如层次化的结构：无结构发展->模快化结构->层次化结构->微内核结构）（4）、开放性：OS遵循世界标准范围。
1.3、作用：（1）、OS作为用户与计算机硬件系统之间的接口（API／CUI／GUI）即：OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统。
（２）、OS是计算机系统资源的管理者（处理机、存储器、I/O设备、文件）处理机管理是用于分配和控制处理机存储器管理是负责内存的分配与回收I/O设备管理是负责I/O设备的分配（回收）与操纵文件管理是用于实现文件的存取、共享和保护（3）、OS实现了对计算机资源的抽象（OS是扩充机/虚拟机）2、操作系统的发展过程2.1、未配置操作系统的计算机系统（40年代手工操作阶段）（1）、人工操作方式：用户独占全机，资源空闲浪费。
缺点：手工装卸、人工判断、手工修改与调试内存指令等造成CPU空闲；提前完成造成剩余预约时间内的CPU完全空闲；I/O设备的慢速与CPU的速度不匹配造成的CPU空闲等待时间（2）、脱机输入输出（Off-Line I/O）方式。
优点：减少了CPU的空闲时间提高了I/O速度2.2、单道批处理系统（50年代）（1）、解决问题：单道批处理系统是在解决人机矛盾和CPU与I/O设备速度不匹配矛盾的过程中形成的。
批处理系统旨在提高系统资源的利用率和系统的吞吐量。
（但单道批处理系统仍不能充分利用资源，故现在已很少用）单道批处理分为：联机批处理、脱机批处理联机批处理：CPU直接控制作业输入输出脱机批处理：由外围机控制作业输入输出（2）、缺点：系统资源利用率低（因为内存中只存在一道程序，I/O请求成功前CPU都处于空闲状态）（3）、特征自动性。
第二章 进程的描述与控制
第二章进程的描述与控制1. 以下有关进程的描述中,错误的是（） [单选题] *A 进程是动态的概念B 进程执行需要处理器C 进程是有生命周期的D 进程是指令的集合(正确答案)2. 以下关于进程的描述中,正确的是（） [单选题] *A 进程获得CPU运行是通过调度实现的(正确答案)B 优先级是进程调度的重要依据,一旦确定就不能改变C 在单CPU的系统中,任意时刻都有一个进程处于运行状态D 进程申请CPU得不到满足时,其状态变为阻塞3.以下关于进程的描述中,（）最不符合操作系统对进程的理解 [单选题] *A 进程是多个程序并行环境中的完整的程序(正确答案)B 进程可以由程序、数据和进程控制块描述C 线程是一种特殊的进程D 进程是程序在一个数据集合上运行的程序,是系统进行资源分配和调度的独立单位。
4. 一个进程是（） [单选题] *A 由处理器执行的一个程序B 一个独立的程序+数据集C PCB结构、程序和数据的组合(正确答案)D 一个独立的程序5. 并发进程是指（） [单选题] *A 可并行执行的进程B 可同一时刻执行的进程C 可同时执行的进程(正确答案)D 不可中断的进程6.在单处理器系统中实现并发技术后,（） [单选题] *A 各进程在某一时刻并行运行,CPU和I/O设备间并行工作B 各进程在一个时间内并行运行,CPU和I/O设备间串行工作C各进程在一个时间段内并行运行,CPU和I/O设备间并行工作(正确答案)D 各进程在某一个时刻并行运行,CPU和I/O设备间串行工作7.在多道程序设计环境下,操作系统分配资源以（）为基本单位 [单选题] *A 程序B 指令C 进程(正确答案)D 作业8. 分配到必要的资源并获得处理器时间的进程状态是（） [单选题] *A 就绪状态B 运行状态(正确答案)C 阻塞状态D 撤销状态9. 当一个进程处于这样的状态时,（）称为阻塞状态 [单选题] *A 它正等着输入一批数据(正确答案)B 它正等着进程调度C 它正等着分给它一个时间片D 它正等着进入内存10. 某个运行中的进程要申请打印机,它将变为（） [单选题] *A 就绪态B 阻塞态(正确答案)C 创建态D 撤销态11. 以下进程状态转换中,（）转换是不可能发生的。
cha2进程描述与控制
2. 进程的终止过程 找出被撤消进程的PCB→该进程若正在执行，则终止该进行的执行 →该进程若有子进程，则撤消其所有子进程→将该进程所拥有的全 部资源，归还给父进程或系统→将被撤消进程的PCB从所在队列 （或链表）中清除，放回到空闲PCB队列。
第二章 进程描述与控制
2.4.3 进程的阻塞与唤醒
1. 引起进程阻塞和唤醒的事件
2. 线程的概念
• 线程：进程中一个相对独立的执行流。 • 进程 /线程
转进程调度或返回
第二章 进程描述与控制
2.4.4 进程的挂起与激活
1. 进程的挂起 当出现了引起进程挂起的事件时，比如，用户进程请求将
自己挂起，或父进程请求将自己的某个子进程挂起， 系统将利
用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程是：首先检查被挂起进程的状态，若处于
第二章 进程描述与控制
2.4 进 程 控 制
2.4.1 进程的创建
A 进程控制就是对系统中的所有进程实施管理， 进程控制一般有原语来实现。 1. 进程图(Process Graph) B C 所谓原语是一种特殊的系统功能调用，它可 以完成一个特定的功能，其特点是原语执行 时不可被中断。
常用原语：
生活中的顺序与并发
例２：假设某人有３项工作要做，分别是烧水、做饭和打扫房 间，其中烧水耗时包括倒水１ｍ，烧水９ｍ，做饭耗时包括淘 米２ｍ，煮饭１８ｍ，打扫房间需要３０ｍ，分析顺序与并发 完成３项工作的时间
顺序：
（６０ｍ） １ ９ ２ 18 30
时间
倒水
烧水
淘米
煮饭
打扫房间
并发：
（３３ｍ）
倒水
１
淘米
烧水
chap2进程管理
end
S6
例题
设有一个作业由4个进程组成，这4个进程必须按下图所 示的次序运行，试用P、V操作表达4个进程的同步关系。 a
P2
P1
b
P3
c
P4
d
习题1
1. 在多进程的系统中，为了保证公共变量的完整性， 各进程应互斥地进入临界区。所谓临界区是指 （ ）。 A.一个缓冲区 B.一段数据区 C.同步机制 D.一 段程序 2. 如果多个进程共享系统资源或相互合作完成一个 共同的任务，则诸进程是以（ ）方式运行的。对 临界资源访问时采用（ ）方式，对于相互合作的 进程采用（ ）方式以协调各进程执行的（ ）。 A.共享 B.独立 C.互斥 D.同步 E. 次序 F. 次数 G.异步 3. 请阐述对于互斥临界区的管理要求。
问题思考：进程和程序的区别和联系？
区别： 1）进程是指令的有序集合，是静态的，进程是程序的执行，是 动态的。 2）进程的存在是暂时的，程序的存在是永久的。 3）进程的组成应包括程序和数据。除此之外，进程还应由记录 进程状态信息的“进程控制块”组成。
联系： 程序是构成进程的组成部分之一，一个进程的运行目标是 执行它所对应的程序。如果没有程序，进程就失去了其存在的 意义。从静态的角度看，进程由程序、数据和进程控制块三部 分组成。
创建进程(调用原语Create())的主要工作
向系统申请一个空闲的PCB。 分配资源，如内存。 给PCB的各数据项臵初值(进程名，状态，CPU信息，程序 计数器，栈指针，寄存器)——故调用创建原语的进程，必须提 供PCB的有关参数。 把新的PCB插入就绪队列。
课
堂 练 习
1、进程的定义是什么？它由哪几部分组成？它最少有哪 几种状态？ 答：进程是进程实体的一次执行过程。进程由程序、数据 和进程控制块组成。一个进程至少有就绪、执行和阻塞三种 状态。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
➢ 或表示为：Ｐ={P1, P2, P3, P4, P5, P6, P7, P8, P9} →={ (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7),(P5, P8), (P6, P8), (P7, P9), (P8, P9)}
➢ 应当注意，前趋图中必须不存在循环，但在上图(b)中却有着下述的前趋 关系：S2→S3, S3→S2
二、程序的顺序执行
➢1、程序的顺序执行 ➢2、程序顺序执行时的特征
1、程序的顺序执行
➢仅当前一操作(程序段)执行完后，才能执行 后继操作。例如，在进行计算时，总须先输 入用户的程序和数据，然后进行计算，最后 才能打印计算结果。
➢ 每个结点还具有一个重量(Weight)，用于表示该结点所含有 的程序量或结点的执行时间。
➢ 如：Ii→Ci→Pi和S1→S2→S3
DAG定义续
P2
P5
S1
P1
P3
P8
P9
P6
S2
P4
P7
(a) 具有九个结点的前趋图
S3
(b) 具有循环的有向图
➢ 对于上图(a)所示的前趋图， 存在下述前趋关系：P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9
2、Bernstein条件
➢1966年Bernstein首先提出了p1、p2并发执行 的条件，又称为Bernstein条件。
➢若两个程序p1、p2能满足下述条件，他们便 能并发执行，且具有可再现性。
R(p1)∧W(p2)∨R(p2)∧W(p1)∨W(p1)∧W(p2)=φ
3、程序并发执行的判定
➢ 例如，有四条语句：
I1
I2
I3
I4
S1
C1
P2
P3
(a) 并发执行时的前趋图
P4
(b) 四条语句的前躯关系
➢ 在上图(a) ▪ Ii→Ci，Ii→Ii+1, Ci→Pi, Ci→Ci+1，Pi→Pi+1 ▪ 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。
1、读、写集的概念
➢读集R(pi)={a1,a2,…,am}表示程序pi在执行期 间所要参考的所需参考的所有变量的集合。
➢写集W(pi)={b1,b2,…,bn}表示程序pi在执行期 间要改变的所有变量的集合。
➢如c:=a-b和w:=c+1两条语句，其读、写集分 别为：
▪ R(c:=a-b)={a,b} W(c:=a-b)={c} ▪ R(w:=c-1)={c} W(w:=c-1)={w}
• N:=N+1在Print(N)和N:=0之前，此时N的值分别为n+1, n+1, 0。 • N:=N+1在Print(N)和N:=0之后，此时得到的N值分别为n, 0, 1。 • N:=N+1在Print(N)和N:=0之间，此时的N值分别为n, n+1, 0。
四、程序并发执行的条件
➢1、读、写集的概念 ➢2、Bernstein条件 ➢3、程序并发执行的判定
▪ S1：a:=x+y
S1
▪ S2：b:=z+1
S3
S4
▪ S3：c:=a-b ▪ S4：w:=c+1
S2
➢ 利用Bernstein条件判定
▪ R(S1)={x,y} R(S2)={z} R(S3)={a,b} R(S4)={c} ▪ W(S1)={a} W(S2)={b} W(S3)={c} W(S4)={w} ▪ 容S4易不判能定并S发1执与行S2。可并发执行，而S1与S3、S2与S3、S3与 ▪ 考虑S1与S4能不能并发执行？
第二章 进程的描述与控制
➢2.1 前趋图和程序执行 ➢2.2 进程的描述 ➢2.3 进程控制 ➢2.4 线程的基本概念
2.1 前趋图和程序执行
➢一、前趋图的定义 ➢二、程序的顺序执行 ➢三、程序的并发执行 ➢四、程序并发执行的条件
一、前趋图的定义
➢ 前趋图(Precedence Graph)是一个有向无循环图，记为 DAG(Directed Acyclic Graph)，用于描述进程之间执行的前 后关系。图中的每个结点可用于描述一个程序段或进程，乃 至一条语句；结点间的有向边则用于表示两个结点之间存在 的偏序(Partial Order)或前趋关系(Precedence Relation)“→”。
➢ 利用前趋图判定
▪ 无前趋后继关系的两个节点可并发执行，如上图所示。
2.2 进程的描述
➢一、进程的定义与特征 ➢二、进程的基本状态 ➢三、进程的挂起状态 ➢四、进程控制块PCB
一、进程的定义与特征
➢1、进程的定义 ➢2、进程的特征
1、进程的定义
➢ 较典型的进程定义有：
▪ 进程是程序的一次执行。 ▪ 进程是可以和别的计算并发执行的计算。 ▪ 进程可定义为一个数据结构及能在其上进行操作的一个程序。 ▪ 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 ▪ 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配
➢ 对于具有下述四条语句的程序段，可用上图(b)表示。 ▪ S1：a:=x+2 ▪ S2：b:=y+4 ▪ S3：c:=a+b ▪ S4：d:=c+b
2、程序并发执行时的特征
➢1) 间断性 ➢2) 失去封闭性 ➢3) 不可再现性
▪ 例如，有两个循环程序A和B，它们共享一个变 量N。程序A每执行一次时，都要做N∶=N+1操 作；程序B每执行一次时， 都要执行Print(N)操 作，然后再将N置成“0”。程序A和B以不同的速 度运行。
➢ →={(Pi, Pj)|Pi must complete before Pj may start}, 如果(Pi, Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的 直接后继。在前趋图中，把没有前趋的结点称为初始结点 (Initial Node)，把没有后继的结点称为终止结点(Final Node)。
➢再如：
I1
C1
P1
I2
C2
P2
▪ S1：a:=x+y;
(a)程序的顺序执行
▪ S2：b:=a-5;
▪ S3：c:=b+1;
S1
S2
S3
(b)三条语句的顺序执行
2、程序顺序执行时的特征
➢⑴顺序性； ➢⑵封闭性； ➢⑶可再现性。
三、程序的并发执行
➢1、程序的并发执行 ➢2、程序并发执行时的特征
1、程序的并发执行
➢ 应当注意，前趋图中必须不存在循环，但在上图(b)中却有着下述的前趋 关系：S2→S3, S3→S2
二、程序的顺序执行
➢1、程序的顺序执行 ➢2、程序顺序执行时的特征
1、程序的顺序执行
➢仅当前一操作(程序段)执行完后，才能执行 后继操作。例如，在进行计算时，总须先输 入用户的程序和数据，然后进行计算，最后 才能打印计算结果。
➢ 每个结点还具有一个重量(Weight)，用于表示该结点所含有 的程序量或结点的执行时间。
➢ 如：Ii→Ci→Pi和S1→S2→S3
DAG定义续
P2
P5
S1
P1
P3
P8
P9
P6
S2
P4
P7
(a) 具有九个结点的前趋图
S3
(b) 具有循环的有向图
➢ 对于上图(a)所示的前趋图， 存在下述前趋关系：P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9
2、Bernstein条件
➢1966年Bernstein首先提出了p1、p2并发执行 的条件，又称为Bernstein条件。
➢若两个程序p1、p2能满足下述条件，他们便 能并发执行，且具有可再现性。
R(p1)∧W(p2)∨R(p2)∧W(p1)∨W(p1)∧W(p2)=φ
3、程序并发执行的判定
➢ 例如，有四条语句：
I1
I2
I3
I4
S1
C1
P2
P3
(a) 并发执行时的前趋图
P4
(b) 四条语句的前躯关系
➢ 在上图(a) ▪ Ii→Ci，Ii→Ii+1, Ci→Pi, Ci→Ci+1，Pi→Pi+1 ▪ 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。
1、读、写集的概念
➢读集R(pi)={a1,a2,…,am}表示程序pi在执行期 间所要参考的所需参考的所有变量的集合。
➢写集W(pi)={b1,b2,…,bn}表示程序pi在执行期 间要改变的所有变量的集合。
➢如c:=a-b和w:=c+1两条语句，其读、写集分 别为：
▪ R(c:=a-b)={a,b} W(c:=a-b)={c} ▪ R(w:=c-1)={c} W(w:=c-1)={w}
• N:=N+1在Print(N)和N:=0之前，此时N的值分别为n+1, n+1, 0。 • N:=N+1在Print(N)和N:=0之后，此时得到的N值分别为n, 0, 1。 • N:=N+1在Print(N)和N:=0之间，此时的N值分别为n, n+1, 0。
四、程序并发执行的条件
➢1、读、写集的概念 ➢2、Bernstein条件 ➢3、程序并发执行的判定
▪ S1：a:=x+y
S1
▪ S2：b:=z+1
S3
S4
▪ S3：c:=a-b ▪ S4：w:=c+1
S2
➢ 利用Bernstein条件判定
▪ R(S1)={x,y} R(S2)={z} R(S3)={a,b} R(S4)={c} ▪ W(S1)={a} W(S2)={b} W(S3)={c} W(S4)={w} ▪ 容S4易不判能定并S发1执与行S2。可并发执行，而S1与S3、S2与S3、S3与 ▪ 考虑S1与S4能不能并发执行？
第二章 进程的描述与控制
➢2.1 前趋图和程序执行 ➢2.2 进程的描述 ➢2.3 进程控制 ➢2.4 线程的基本概念
2.1 前趋图和程序执行
➢一、前趋图的定义 ➢二、程序的顺序执行 ➢三、程序的并发执行 ➢四、程序并发执行的条件
一、前趋图的定义
➢ 前趋图(Precedence Graph)是一个有向无循环图，记为 DAG(Directed Acyclic Graph)，用于描述进程之间执行的前 后关系。图中的每个结点可用于描述一个程序段或进程，乃 至一条语句；结点间的有向边则用于表示两个结点之间存在 的偏序(Partial Order)或前趋关系(Precedence Relation)“→”。
➢ 利用前趋图判定
▪ 无前趋后继关系的两个节点可并发执行，如上图所示。
2.2 进程的描述
➢一、进程的定义与特征 ➢二、进程的基本状态 ➢三、进程的挂起状态 ➢四、进程控制块PCB
一、进程的定义与特征
➢1、进程的定义 ➢2、进程的特征
1、进程的定义
➢ 较典型的进程定义有：
▪ 进程是程序的一次执行。 ▪ 进程是可以和别的计算并发执行的计算。 ▪ 进程可定义为一个数据结构及能在其上进行操作的一个程序。 ▪ 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 ▪ 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配
➢ 对于具有下述四条语句的程序段，可用上图(b)表示。 ▪ S1：a:=x+2 ▪ S2：b:=y+4 ▪ S3：c:=a+b ▪ S4：d:=c+b
2、程序并发执行时的特征
➢1) 间断性 ➢2) 失去封闭性 ➢3) 不可再现性
▪ 例如，有两个循环程序A和B，它们共享一个变 量N。程序A每执行一次时，都要做N∶=N+1操 作；程序B每执行一次时， 都要执行Print(N)操 作，然后再将N置成“0”。程序A和B以不同的速 度运行。
➢ →={(Pi, Pj)|Pi must complete before Pj may start}, 如果(Pi, Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的 直接后继。在前趋图中，把没有前趋的结点称为初始结点 (Initial Node)，把没有后继的结点称为终止结点(Final Node)。
➢再如：
I1
C1
P1
I2
C2
P2
▪ S1：a:=x+y;
(a)程序的顺序执行
▪ S2：b:=a-5;
▪ S3：c:=b+1;
S1
S2
S3
(b)三条语句的顺序执行
2、程序顺序执行时的特征
➢⑴顺序性； ➢⑵封闭性； ➢⑶可再现性。
三、程序的并发执行
➢1、程序的并发执行 ➢2、程序并发执行时的特征
1、程序的并发执行