第三章 进程管理 本章重点： 进程的定义、特征、进程控制的基本概念。 进程PCB基本结构，作用及进程的状态及转换。

Presentation on theme: "第三章 进程管理 本章重点： 进程的定义、特征、进程控制的基本概念。 进程PCB基本结构，作用及进程的状态及转换。"— Presentation transcript:

1 第三章 进程管理 本章重点： 进程的定义、特征、进程控制的基本概念。 进程PCB基本结构，作用及进程的状态及转换。
第三章 进程管理 本章重点： 进程的定义、特征、进程控制的基本概念。 进程PCB基本结构，作用及进程的状态及转换。 进程同步与互斥的基本概念和解决方法。 几个经典的进程同步与互斥问题及算法 。 进程通信的类型及实现方法 线程的基本概念及状态。 难点： 进程的同步与互斥

2 进程的基本概念 进程的描述 进程的状态及其转换 进程控制 进程互斥 进程同步 进程通信 线程 小结

3 3.1进程的概念 一、程序的顺序执行与特征 1.程序：完成一定功能的、按前后顺序执行的指令集合，它可以分成若干指令串。 2.程序的执行过程：
① 输入数据 ② 计算 ③ 输出结果 S1: a=51 S2: b=a*5 I C P S4: d=a+b*b+c*2 S3: c=a+b Repeat IR M[pc] pc pc+1 Execute （instruction IR） Until CPU Halt 3.程序的顺序执行：一个具有独立功能的程序独占处理机 直至最终结束的过程称为程序的顺序执行。

4 4.程序顺序执行的特征： （1）顺序性：每一个操作都必须在上一个操作完成之后开始 内：语句之间、指令之间 外：程序之间 （2）封闭性：资源独占，只有运行的程序能够改变资源状态，每个程序的执行不会受到外部因素的影响。 （3）可再现性：只要程序的运行环境及输入条件相同，输出结果肯定相同。

5 二、前趋图 前趋图（Directed Acyclic Graph）： 是一个有向非循环图，图中每个节点可以表示一条语句，一个程序或进程，节点之间的有向边表示节点之间的前趋关系（Precedence Relation）或半序关系（Partial Order） “→” ={ （Pi，Pj） |Pj必须在Pi完成之后开始执行｝ 如果：（Pi，Pj）∈ →，则， Pi → Pj Pi称为Pj的直接前趋，Pj称为Pi的直接后继。 如果：Pi → Pk → …… → Pj Pi称为Pj的前趋，Pj称为Pi的后继。 没有前趋的节点称为初始节点 。 没有后继的节点称为终止节点。

6 S1: a=51 １ S2: b=a*5 S3: c=a+6 S4: d=b*b+c*2 ２ ３ Ｓ１ ４ ５ Ｓ２ Ｓ３ ６ Ｓ４

7 １ ２ ３ 该图是否为前趋图？为什么？ ４ ５ ６

8 Ｓ１ 该图是否为前趋图？为什么？ Ｓ２ Ｓ３ Ｓ４

9 三、多道程序的并发执行与特征 。 1．多道程序并发执行的逻辑分析 Ii Ci Pi 但对于多个程序，并不一定存在关系： Pi → Ii+1 可以：第一个程序的输入结束并开始计算时，第二个程序的输入工作开始进行，从而第一个计算和第二个输入可以并行进行。

10 I1 C1 I2 P1 C2 I3 p2 C3 I4 P3 Ii → Ci Ci → Pi Ii → Ii+1 Pi → Pi+1

11 2．多道程序并发执行的系统实现 处理器的主要功能是执行驻留在内存中的指令，为了提高效率，处理器可以同时执行多道程序。对于处理器而言，对全部指令的执行是按一定顺序进行的，这个顺序的改变是通过改变程序计数器（PC）或称为指令指示器(IP)的值来完成的。

12 例：程序A的起始地址为51200，共12条指令；程序B的起始地址为81920，共4条指令，其中第4条指令包括I/O指令；程序C的起始地址为194560，共12条指令；分派程序的起始地址为20480，共6条指令；三个程序以及分派程序均在内存，操作系统每次执行6条用 户程序指令后就会自动终止当前用户程序，转去执行分派程序。每条指令需要一个指令周期，则程序的执行过程如下：

13 超时 20480 20481 20482 20483 20484 20485 194560 194561 194562 194563 194564 194565 超时 20480 20481 20482 20483 20484 20485 81920 81921 81922 81923 I/O请求

14 3．多道程序并发执行的定义 并发执行：为了增强计算机系统的处理能力和提高资源的利用率所采用的一种同时操作技术。使若干进程都处于已经开始执行和尚未执行完成的状态。 多道程序的并发执行分两种情况: 多道程序系统的程序执行环境变化引起的多道程序的并发执行（多道程序系统环境下，各道程序在逻辑上独立，具备了执行的条件）。 在某道程序的几个程序段中，包含着一部分可以同时执行或顺序颠倒执行的代码。

15 4.多道程序并发执行的特征： （1）失去了封闭性：多道程序相互影响。 （2）间断性：程序并发执行时，由于（a）它们共享软、硬件资源(b)程序之间相互合作完成一项共同任务，因而使程序之间相互制约。这种制约导致并发程序具有“执行-暂停-执行”这种间断活动的特点。 （3）独立性：系统把每个程序作为一个独立单位来进行分配，并发程序在运行过程中，既然是作为一个独立的运行实体，它也必然具有作为一个单位去获得资源的独立性。 （4）随机性：有可能失去可再现性，由于公用变量的存在，使程序由于微观上的执行顺序不同而产生不同的结果。

16 四、Bernstain条件 。 程序的不可再现性是绝对不允许的，为此，应采取 某种措施使并发程序保持其可再现性。 Si、Sj:程序段或语句。 R（Si）：Si所涉及的读变量的集合。 W（Si）：Si所涉及的写变量的集合。 Si与Sj可并发执行的条件： ① R（Si）∩W（Sj）=Φ ② R（Sj）∩W（Si）=Φ ③ W（Sj）∩W（Si）=Φ 同时成立

17 不能并发！！！ 例： S1: C=X+Y+Z S2:D=C+X R(S1)={X,Y,Z} R(S2)={C,X} W(S1)={C}
W(S2)={D} S1：x=x1+x2 S2：y=x1*x2 S3：z=(x+y)/2 S4：w=z+5 S5：m=w+1 S6：m=m+1

18 五、进程的定义 进程：一个具有独立功能的程序对某个数据集合在处 理机上的一次执行过程。它是操作系统进行资源分配 的基本单位。 操作系统所应满足的主要要求都与进程有关： 操作系统必须能够同时执行多个进程以最大限度地利用处理器，并为每个进程提供合适的响应时间。 操作系统必须按一定的策略为进程分配资源并避免死锁。 操作系统应支持进程间的通信并能创建用户进程。 操作系统的主要职责就是控制进程的执行。

19 六、进程的特征 动态性：进程是程序的一次执行过程。因此，动态特征是进程的最重要特征 并发性：只有建立了进程的程序才能并发执行，引入进程的目的就是为了使它所对应的程序和其他进程并发执行，以提高系统资源的利用率。 独立性：每个进程都有各自独立的功能。进程是一个能独立运行的单位，也就是竞争计算机资源和进行处理机调度的基本单位。 异步性（相互制约性）：由于进程之间的相互制约，使其具有执行的间断性。既：进程按各自独立的不可预知的速度向前推进。 结构特征：每个进程都配有一个PCB，每个进程都有程序段、数据段和PCB三部分组成。

20 七、进程与程序的比较 状 态 存在 方式 所需 资源 并发 性 包含关系 生命 期短 内存、外 存、CPU 进程包 含程序 进程 动 有 程序不 包含进程 程序 静 永久 外存 无

21 3.2进程的描述——PCB 进程包括：程序段、数据段、PCB
1.描述信息： 进程标识符（PID）或进程名：用来唯一标识进程。 用户标识符（UID）或用户名：进程所属用户，利于进行资源共享和信息保护。 家族信息（Family）：进程所属家族，即：进程的父进程和子进程等。 处理机状态（CPU）：处理机的各种寄存器的内容，包括：通用寄存器（用户可视寄存器）、指令计数器、程序状态字、用户栈指针。

22 2.控制信息 进程的状态（Status）：进程所处的状态，就绪，运行，等待。 进程优先级（Priority）：处理机调度的依据，其值取决于进程执行的紧迫程度以及进程占用CPU的时间，占据内存时间、占据其他资源等情况 记时信息（TIME）：记录进程等待CPU的时间、已占有CPU的时间等以及使用其他资源的时间 程序和数据的起始地址（Start）：进程所对应的程序的起始地址。 通信信息（ Communication）：该进程在运行过程中与其他进程交换信息的情况。消息队列指针、信号量等

23 占内存大小，位置（RAM）及其管理用数据结构。
外存交换区位置（SWAP） 共享区位置，大小（SHARE） 外设情况（DEVICE） 打开文件情况（FILE） PCB指针（PCBPtr） 进程控制块PCB是系统感知进程存在的唯一标志。 系统对进程的各种操作通过对PCB的操作实现。

24 执行指针 就绪队列指针 阻塞队列指针 空闲队列指针
三、进程组织：不同系统组织方式不同：链接、索引 执行指针 就绪队列指针 阻塞队列指针 空闲队列指针 PCB1 4 PCB2 3 PCB3 0 PCB4 8 PCB5 PCB6 7 PCB7 9 PCB8 0 PCB9 … 四、存在区 ：PCB的常用部分常驻内存系统区，其他部分放在外存。

25 3.3进程的状态及其转换 一、进程的基本状态 就绪状态（READY）：进程获得除处理机以外的所 有资源，等待处理机。
2. 运行状态（RUNNING）：进程正在占有处理机，其对应的程序正在处理机上运行。单处理机系统中，只能有一个进程处于运行状态。 3.等待状态/阻塞状态（WAITING/BLOCKED）：进程正在等待某件事情的发生无法继续运行下去而放弃处理机。 4. 创建/初始（NEW）：进程刚刚创建，还没有被处理机提交到可运行进程队列中。 5. 终止（EXIT）：进程已正常或异常结束，被OS从可运行进程队列中释放出来

26 二、进程的状态转换： 1．三种状态的进程状态转换图 进程调度 创建 终止 就绪 运行 时间片到 I/O完成 I/O请求 阻塞

27 2．五种状态的进程状态转换图 初始 进程调度 准许 就绪 运行 完成 时间片到 I/O完成 I/O请求 阻塞 终止

28 3．具有挂起状态的进程状态转换图 初始 运行 激活 挂起 终止 静止 阻塞 进程调度 准许 活动 就绪 时间片到 完成 挂起 等待的事情发生
等待某件事情 激活 静止 就绪 活动 阻塞 挂起 终止 等待的事情发生 挂起 静止 阻塞 激活

29 3．进程状态间转换关系表 原状态 转换后状态 创建 运行 就绪 阻塞 终止
OS根据作业控制请求，分时系统用户登录，进程创建子进程 × OS准备运行新进程 时间片到，OS响应更高优先级的进程 OS服务请求，资源请求，事件请求。 进程完成 进程夭折 被分派程序选中 被父进程终止 事件发生 说明：一般的操作系统为了管理方便，根据等待的事件设置多个阻塞队列，将等待不同事件的进程放在不同的等待队列中。

30 3.4进程控制 进程控制：系统使用一些具有特定功能的程序来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程、高效率、并发执行和协调、实现资源共享的目的。 进程控制是通过原语来实现。 原语：用于完成某种特定功能的不可分割的一段程序。 原语的实现是通过关中断来实现的。 实现进程控制的程序段被称作进程控制原语。

31 一、内核： 1.什么是内核? 在设计OS时把一些与硬件紧密相关的模块或运行频率较高的模块以及被许多模块所公用的一些基本操作，安排在靠近硬件的层次中，并使他们常驻内存，以提高OS的运行效能，通常把这部分叫OS的内核。

32 2.内核的基本功能： ⑴中断处理: 在OS中，中断处理既是内核最基本功能也是 整个OS赖以活动的基础，在内核中对中断进 行”有限的处理”然后便转去相关的进程继续 处理。应该说OS的重要活动最终都将依赖于 中断的进程调度、设备驱动、系统调用等等。 进程的建立与撤消 进程状态的转换 ⑵进程管理 : 进程调度 控制进程的并发执行 ⑶资源管理中的基本操作： 如：时钟管理、I/O管理\文件系统的管理等（设备驱动程序、例程处理程序等）

33 二、原语： 1.创建原语 进程的层次结构 创建方式有两种： （1）系统程序创建： （2）父进程创建： 0＃ 0＃ 1＃ 960＃ 508＃
503＃ 502＃ 501＃ 0＃ 1＃

34 引起进程创建的事件 （1）用户登录 （2）作业调度 （3）提供服务：例如，用户程序提出打印服务请求 （4）应用请求：用户程序建立键盘输入程序完成自身需要的数据输入任务。这种情况是由用户程序自己建立子进程。 创建原语的功能： 从系统中申请一第PCB表，为进程分配资源，填PCB表，其中状态为”就绪状态”，把PCB插入到就绪队列中。

35 开始 查PCB链表 无 有空PCB吗？ 有 失败 取一个PCB，获得该PCB的PID 为进程分配资源 填入入口参数 置“就绪”状态，入就绪队列 将PID挂入其家族链 返回

36 2.撤销原语 撤消时机： 该进程完成了所有的任务而正常结束 由于错误而导致非正常结束 地址越界：访问其它进程的存储区 保护错：进程试图访问不允许访问的资源 非法指令：程序试图执行一条不存在的指令 特权指令错：用户进程试图执行OS指令 运行超时：进程的执行时间超过了指定最大值。 等待超时：等待某件事时间超过了规定的最大值 算术运算错：被零除 I/O故障 外界干预 祖先进程撤消某个子进程 父进程终止 操作员或操作系统干预

37 2.撤销原语 功能：将该进程的所有子进程撤消，然后撤消本进程，将进程占有的所有资源收回后，把PCB收回，挂到空PCB链表上。

38 入口 查进程PCB链表或进程家族 无 有此PCB吗？ 处理子进程 错误处理 有 该PCB有 子进程吗？ 有 无 释放该进程所占资源 释放PCB结构 返回

39 3.阻塞原语 引起阻塞的事件： 请求系统服务：正在执行的进程请求操作系统提供服务，操作系统不能立即满足进程要求。 启动某种操作：进程启动某种操作且必须等该操作完成后进程才能继续运行。 新数据尚未到达：进程运行时需要处理的数据还未送达。 无新工作可以做：具有一定功能的进程完成某任务后，没有新任务布置下来。

40 功能：中断处理机，保护现场，状态由“执行”改为“等待”，将PCB从运行状态转到WQ中。
阻塞原语是进程等待某件事情的发生，而该事情又不具备发生条件时，进程自己调用阻塞原语将自己阻塞起来。 入口 保护当前进程的CPU现场 置该进程状态为“WAIT” 被阻塞进程入等待队列 转进程调度

41 4.唤醒原语 功能：状态由“等待”改为“就绪”，将PCB从等待队列中插入RQ中。 等待该事件的进程将被唤醒，由系统进程唤醒或由其他进程唤醒。 入口 从等待队列中摘下被唤醒进程 置该进程状态为“READY” 被阻塞进程入就绪队列 转进程调度或返回

42 3.5进程互斥 3.5.1 资源共享所引起的制约 一、并发进程之间的基本关系 1.互斥：不允许两个以上的并发进程同时使用某种资源
2.同步：是指对多个相关进程在执行次序上的协调。 用于保证这种关系的机制称为进程同步机制。 例： 互斥的进程之间无逻辑关系， 同步的进程之间有逻辑关系。 无论同步还是互斥，进程间都有一种制约关系。“该走就走，该停就停”。 互斥的进程之间存在着间接制约关系：进程—资源—进程 同步的进程之间存在着直接制约关系。 OS的核心任务就是解决进程的同步与互斥。

43 二、临界区CS（Critical Section）
1.临界资源CR（Critical Resources）：一次只允许一个进程访问的资源，等一个进程完全用完后，另一个进程才能使用。 如：打印机、变量、堆栈指针、队列指针 X=X+1000 500 x LOAD A，X ADDI A，1000 STORE A，X X=X-100 LOAD A，X MINUS A，100 STORE A，X 临界区：每个进程中访问临界资源的代码段。

44 申请区 临界区 退出区 临界区的使用规则： 空闲让进：当CS为空时，必须允许要求进入CS的进程进入CS以有效利用资源。 忙则等待：当某进程处于CS时，其它想进入者必须等待，以保证互斥使用CS。 有限等待：对要求进入CS的进程，应在有限时间内使之进入，避免“死等” 让权等待：对于等待进入CS的进程，必须释放处理机，避免“忙等”

45 三、两个任务的解决方案 1 turn Turn=0? Turn=1? 取球 取球 打球 打球 Turn=1 Turn=0 离开 离开

46 Flag[0] 1 Flag[1] FLAG[1]=T FLAG[0]=T 取球 取球 打球 打球 FLAG[0]=F FLAG[1]=F
FLAG[1]=T FLAG[0]=T FLAG[1]=T? FLAG[0]=T? 取球 取球 打球 打球 FLAG[0]=F FLAG[1]=F 离开 离开

47 三、两个任务的解决方案 有没有更好的方案？

48 三、两个任务的解决方案 任务描述: (Worker Thread) public class Worker extends Thread{
public Worker(String n,int i, MutualExclusion s){ name=n; id=i; shared=s; } public void run(){ while (true){ shared.enteringCriticalSection(id); System.out.println(name+”is in CS”); MutualExclusion.criticalSection(); shared.leavingCriticalSection(id); System.out.println(name+”is out of CS”); MutualExclusion.nonCriticalSection(); } } private String name; private int id; private MutualExclusion shared;}

49 MutualExclusion abstract class
public abstract class MutualExclusion{ public static void criticalSection (){ try{ Thread.sleep((int) (Math.random()*TIME)); } catch(InterruptedException e){} public static void nonCriticalSection (){ catch(InterruptedException e){ } public abstract void enteringCriticalSection(int t); public abstract void leavingCriticalSection(int t); public static final int TURN_0=0; public static final int TURN_1=1; public static final int TIME=3000;}

50 TestAlgorithm class public class TestAlgorithm{ public static void main (String args[]){ MutualExclusion alg=new Algorithm_1(); Worker first=new Worker(“Runner 0”,0,alg); Worker second=new Worker(“Runner 1”,1,alg); first.start(); second.start(); }

51 1.Algorithm 1 public class Algorithm_1 extends MutualExclusion{ public Algorithm_1(){ turn=TURN_0; } public void enteringCriticalSection(int t){ while (turn!=t){ Thread.yield(); } public void leavingCriticalSection(int t){ turn=1-t; private volatile int turn;

52 2.Algorithm 2 Algorithm 1的问题是只记录允许哪些进程进入临界区，没记录关于进程目前所处状态的信息，解决办法： 用boolean[] flag=new boolean[2]代替变量turn Flag[i]=true表示进程i准备进入临界区

53 public class Algorithm_2 extends MutualExclusion{
public Algorithm_2(){ flag[0]=false; flag[1]=false； } public void enteringCriticalSection(int t){ int other； other = 1-t； flag[t]=true； while (（flag[other]==true)) Thread.yield(); public void leavingCriticalSection(int t){ flag[t]=false; Private volatile boolean[] flag=new boolean[2];}

54 3.Algorithm 3 Algorithm 2的问题是只记录关于进程目前所处状态的信息，解决办法： 用boolean[] flag=new boolean[2] 和变量turn一起控制并发过程。 Flag[i]=true表示进程i准备进入临界区

55 public class Algorithm_3 extends MutualExclusion{
public Algorithm_3(){ flag[0]=false; flag[1]=false； turn=TURN_0; } public void enteringCriticalSection(int t){ int other； other = 1-t； flag[t]=true； turn=other； while (（flag[other]==true) && (turn==other)) Thread.yield(); public void leavingCriticalSection(int t){ flag[t]=false; Private volatile int turn; Private volatile boolean[] flag=new boolean[2]}

56 3.5.2 互斥的加锁实现 1.实现原理 当并发进程申请进入临界区时首先测试临界区是否是上锁的，如果锁上了，就等待； 否则，上锁，进入临界区。 当某个进程进入临界区之后，将临界区锁上，直到他退出临界区为止。

57 3.实现代码： 设控制临界区的锁变量为：Lock，初始为FALSE Lock =FALSE表示临界区可用， Lock =TRUE表示临界区不可用。 加锁 TS（lock） { TS ← lock lock ←TRUE } 解锁 unlock（ Lock ） Lock ←FALSE

58 PA A: While TS（Lock）DO SKIP; CS unlock（Lock） GOTO A PB B: While TS（Lock）DO SKIP; CS unlock（Lock） GOTO B PC C: While TS（Lock）DO SKIP; CS unlock（Lock） GOTO C

59 4.加锁机制存在的问题 循环等待造成资源浪费 对于同步问题灵活性不够 可能造成不公平

60 3.5.3 信号量和P、V操作 1.信号量（ Semaphore） （1）信号量是一个整型变量 （2）与一个资源有关 （3）只能进行P操作和V操作（初始化除外） 3.V操作：释放资源 2. P操作：申请资源 V(S:Semaphore) { s=s +1 ; if (s<=0) { R(s); /*唤醒原语*/ } P(S:Semaphore) { s=s –1 ; if (s<0) { w(s); /*阻塞原语*/ } P、V操作本身都是原语操作

61 3.5.4 信号量解决互斥关系 例：SP=1 打印机 P1 P(SP) 使用打印机 V（SP） P3 P(SP) 使用打印机 V（SP） P2 P(SP) 使用打印机 V（SP） 临界区不是原语可以被中断。

62 5台打印机怎么办？ 信号量S值的含义： （1）S〉0表示可用资源数 （2）S<0 |S|表示等待的进程数 （3）S=0表示无可用资源，无等待进程

63 3.6进程同步 一、信号量解决同步关系 关门 公共汽车 售票员 司机 S1 P（S1） V（S1） 开车 卖票 S2 停车 P（S2） 开门

64 二、前趋图问题。 P11 P2 P3 P5 P6 P4 S1 S3 S2 S4 S5 S6 S7

65 P1; V(S1); V(S2); V(S3); P(S1); P2; V(S4); P(S2) ; P3; V(S5); P(S3); P4; V(S6); P(S4); P(S5); P5; V(S7); P(S7); P(S6); P6;

66 三、经典的同步互斥问题 1.生产者与消费者问题 生产者生产产品，消费者消费产品，二者共享缓冲区

67 (1). buffer为队列，有界，大小为n 队列有两个指针in 和out，in被所有的生产者使用， out所有的消费者使用。

68 Mutex1：所有的生产者互斥使用in指针；
Mutex2：所有的消费者互斥使用out指针。 同步信号量：Empty=n ; full=0 LP: 生产一个产品； LC: P(full); Buffer P(empty); P(mutex2); P(mutex1); item =Buffer[out]; Buffer[in]=item; out=(out+1) mod n; In=(in+1) mod n; V(mutex2); V(mutex1); V(empty); V(full); out in 消费一个产品； Goto LP; Goto Lc;

69 (2). buffer为堆栈，有界，大小为n 堆栈有一个指针top，被所有的生产者和所有的消费者 使用。

70 Mutex：所有的生产者和消费者互斥使用top指针；
同步信号量：Empty=n ; full=0 LP: 生产一个产品； LC: P(full); Buffer P(empty); P(mutex); P(mutex); top=top-1； Buffer[top]=item; item =Buffer[top]; top=top+1 V(mutex); V(mutex); V(empty); V(full); top 消费一个产品； Goto LP; Goto Lc;

71 (3). buffer为队列，无界 队列有两个指针in 和out，in被所有的生产者使用， out所有的消费者使用。

72 Mutex1：所有的生产者互斥使用in指针；
Mutex2：所有的消费者互斥使用out指针。 同步信号量：full=0 LP: 生产一个产品； LC: P(full); Buffer P(mutex1); P(mutex2); item =Buffer[out]; Buffer[in]=item; out=out+1; In=in+1 V(mutex1); V(mutex2); V(full); out in 消费一个产品； Goto LP; Goto Lc;

73 (4). buffer为堆栈，无界 堆栈有一个指针top，被所有的生产者和所有的消费者 使用。

74 Mutex：所有的生产者和消费者互斥使用top指针；
同步信号量：full=0 LP: 生产一个产品； LC: P(full); Buffer P(mutex); P(mutex); top=top-1； Buffer[top]=item; item =Buffer[top]; top=top+1 V(mutex); V(mutex); V(full); top 消费一个产品； Goto LP; Goto Lc;

75 2.读者-写者问题 m个读者，n个写者，读者可以同时读，读写不能同时进行，写写不能同时进行 No！！ 今晚有课 明天放假 后天停水 Certainly！ Reading May I Write？ May I Read？

76 No！！ 今晚有课 明天放假 后天停水 元旦 No！！ Writing May I Read？ May I Write？ 进入 写 离开 进入 读 离开 如何解决同步与互斥？

77 if(readcount==0) P(mutexw); if(readcount==0) V(mutexw);
Readcount=0;mutextr=1; Mutexw=1; 读者： 写者： P(mutextr); if(readcount==0) P(mutexw); P(mutexw); 写； Readcount=readcount+1; V(mutexr); V(mutexw); 读； P(mutextr); Readcount=readcount-1; if(readcount==0) V(mutexw); V(mutexr); 走;

78 四、同步互斥问题实例 1. I-C-P问题 I是输入进程负责输入数据，C是计算进程，负责进行计算；P是打印进程负责打印结果；Buffer1大小为m ，被I与C共享； Buffer2大小为n，被 C与P共享；buffer1和buffer2均为队列，有界。

79 2.产品配套问题 A产品和B产品是配套产品 ，要求： nA-nB≤y ，nB-nA≤x ，开始时：A和B数量均为0。如何实现A，B产品的生产过程。 几个信号量？初值分别为多少？ 开始时：A已有m个，B已有n个。怎么办？ 几个同步？几个互斥？ Sa =y Sb =x A 产品 P(Sb); P(Sa); 生产一个A； 生产一个B； V（Sa）; V（Sb）;

80 3.吃水果 桌上有一空盘子，允许存放一只水果，爸爸可向盘子中放苹果或橘子，儿子专吃盘子中的橘子，女儿专吃盘子中的苹果，规定当盘子空时一次只能放一只水果，请用P，V操作实现爸爸、儿子、女儿三个并发进程的同步。 几个信号量？初值分别为多少？ 几个同步？几个互斥？ 我要橘子 儿子 女儿 我要苹果 爸爸

81 三个进程互斥使用一个包含N（N>0）个单元的缓冲区，P1每次用produce()生成一个正整数并用put()送入缓冲区的某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数； P3每次用geteven()从缓冲区中取出一个偶数并用counteven()统计偶数个数；请用信号量机制实现三个进程的同步与互斥，并说明所定义的信号量的含义，

82 3.7进程通信 一、 引入 进程通信：在进程间传输数据。 根据通信内容分类： 低级通信：传送控制信号的通信，例如：P,V操作
高级通信 ：用户可直接利用操作系统提供的一组通信命令高效地在进程间传送大量数据 二、在单机系统中的几种进程通信方式： 1.主从式： 特点： （1）主进程可自由使用从进程的资源和数据 （2）从进程的动作受主进程的控制 （3）主进程和从进程的关系是固定的 典型实例：终端控制进程和终端进程

83 2.会话式：通信进程双方分别称为使用进程和服务进程，使用进程调用服务进程提供的服务
特点： （1）使用进程在使用服务进程所提供的服务之前必须得到服务进程的许可。 （2）服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成 （3）使用进程和服务进程在进行通信时有固定连接关系 典型实例：用户进程与磁盘管理进程之间的通信

84 3.消息或邮箱机制：无论接受进程是否已准备好接受消息，发送进程都将把所要发送的消息送入缓冲区或邮箱。
消息组成 发送进程 接收进程 操作 数据 特点： （1）只要存在空缓冲区或邮箱，发送进程就可以发送消息。 （2）发送进程和接受进程之间无直接连接关系，接受进程可能在收到某个发送进程发来的消息之后，又转去接收另一个发送进程发来的消息。 （3）发送进程和接收进程之间存在缓冲区或邮箱 缓冲区或邮箱结构： P1 P2

85 4.共享存储器系统：不要求数据移动。相互通信的进程共享某些数据结构或共享存储区，进程之间通过这些空间进行通信，包括以下两种类型：
基于共享数据结构的通信方式：要求进行通信的各个进程共用某些数据结构以实现进程间的数据交换，例如：生产者-消费者问题的缓冲区 基于共享存储区的通信方式：在存储器中划出一块共享存储区，诸进程可通过对共享存储区中数据的读或写来实现通信。 进程在通信前，先向系统申请获得共享存储区中的一个分区，并指定该分区的关键字；若系统已经给其他进程分配了这样的分区，则将该分区的描述符返回给申请者，然后，由申请者把获得的共享存储区链接到本进程上，连接之后，便可以像读写普通存储器一样读写共享区。

86 三、消息缓冲机制 发送进程在自己的内存空间设置发送区，把消息填入其中，然后用发送过程发送消息。接收进程在接收消息之前先在自己的内存空间中设置接收区，然后接收消息。 缓冲区为公用缓冲区，因此发送者和接收者之间需要实现对消息缓冲区的互斥使用。 发送进程把消息写入缓冲区和把消息挂入消息队列时，应禁止其他进程对该缓冲区消息队列的访问；接收进程正从消息队列取消息时，应禁止其他进程对该队列的访问。 缓冲区中无消息时，接收进程不能接收任何消息

87 三、消息缓冲机制 公用信号量mutex为控制对缓冲区访问的互斥信号量，Mutex=1 S为接收进程的私用信号量，表示等待接收的消息数 S=0 用send 、receive 原语实现进程通信

88 Send（m） 向系统申请一个消息缓冲区 P(mutex) 将发送区消息m送入新申请的消息缓冲区 把消息缓冲区插入到接收进程的消息队列中 V(mutex) V(S)

89 Receive(n) P（S） P（mutex） 从消息队列中取出一个消息n 把消息拷贝到指定的接收区中 归还消息缓冲区给系统 V(mutex)

90 四、管道通信 无名管道为建立管道的进程及其子孙提供一条比特流方式 传送消息的通信管道，逻辑上是管道文件，物理上由高速 缓存构成，很少启动外设 发送进程利用系统调用write(fd[1],buf,size)把buf中长度为size字符的消息送入管道入口fd[1] 接收进程利用系统调用read(fd[0],buf,size)从管道出口fd[0]读出size字符的消息送入buf中 Unix用系统调用pipe建立管道 Int fd[2]； Pipe（fd）

91 例： #include<stdio.h> Main(){ Int fd[2]； char buf[50],s[50]; Pipe（fd）; while((x=fork())==-1); if(x==0) { sprintf(buf,”This is an example\n”); write(fd[1],buf,50); exit(0); } else{ wait(0); read(fd[0],s,50); printf(“%s”,s); }}

92 3.8线程的概念 线程及其管理 目的：引入线程的目的是提高系统的并行性，改善资源 利用率、提高系统吞吐量，较好的支持对称多处理器以
适应多任务情况下提高处理速度和系统性能的要求。 定义：线程是进程内的一个相对独立的、可独立调度和 指派的执行单元。 线程叫做轻型进程（Light-weight Process）， 进程叫做重型进程（Heavy-weight Process）。

93 性质： 线程是进程内的一个相对独立的可执行单元。 线程是操作系统内的基本调度单元，线程中包含调度 所需要的信息。 一个进程中至少有一个线程，可以有多个线程。 线程并不拥有资源，而是共享和使用包含它的进程所 拥有的资源，因此需要多线程之间的通信机制 线程在必要时可以创建自己的线程，有自己的生命期 和状态变化 线程是处理机调度的基本单位 同一进程内的多个线程之间也可以并发执行 进程切换需要保留大量的现场信息，系统开销大；线程 切换只需要保存和设置少量的寄存器内容，因此开销小 同一进程的线程共享进程的地址空间，因此多线程之间 的同步与通信比较容易实现，甚至无需操作系统内核干预

94 状态 ： 就绪：具备运行条件，等待分配CPU 。 运行：在CPU上运行 阻塞：等待某个事件发生。 说明： 线程中不具有挂起状态（挂起将资源调入外存， 而线程不管理资源） 多线程的进程的状态，若一个线程阻塞时并不阻塞整个 进程，该进程中的其他线程依然可以参与调度 线程用TCB(Thread Control Block)描述数据结构

95 二、多线程的实现： 多线程机制：操作系统支持一个进程内执行多个线程的 能力。MS-DOS支持一个用户进程和一个线程；UNIX支 持多个用户进程，但一个进程只有一个线程；JAVA运行 引擎支持一个进程多个线程；NT、Solaris、Mach支持 多进程多线程。 线程实现 用户级线程：informix数据库。由用户应用程序建立， 用户应用程序对线程进行调度和管理，操作系统内核 不知道用户级进程的存在。（MS-DOS, UNIX） 优点：线程开关的时空开销小于内核级；线程调度算 法与操作系统调度算法无关；适用于任何操作系统， 因为与操作系统内核无关。

96 内核级线程：Mach。所有线程的创建、调度、管理
全部由操作系统内核负责。 优点：内核可调度一个进程中的多个线程，使其同时 在多个处理器上并行运行；进程中一个进程阻塞时其 他进程可继续调度；内核本身也可以以线程方式实现。 二者：Solaris 内核支持多线程的建立、调度与管理，系统中提供 线程库，允许用户应用程序建立、调度和管理用户级 线程。

97 三、进程与线程的关系 线程：进程 描述 例 1：1 n：１ １：n m：n 每个进程的执行就是一个线程 每个进程定义一个地址空间并动态拥有资源；同一进程可产生多个线程并运行。 一个线程可以在多个进程间转移 包含１：n和n：１的性质 UNIX System V OS/2, MVS, MACH Ra TRIX

98 四、SMP（Symmetrical Multiple Processor）
按照多处理器之间的通信方式可将多处理器系统分为 两种类型： 共享存储器多处理器系统：多个处理器共享 一个存储器中的程序和数据。 分布式存储器系统：每个处理器有自己的专用存 储器，计算机之间的通信通过专用线路或网络。 一般集群（CLUSTERS）为此类系统 SMP特点： 系统中有多个处理器， 每个处理器共享一个存储器。

99 3．9 小结 多个程序并发执行与特征 ：失去了封闭性、间断性、独立性、随机性 Bernstain条件
单个进程顺序执行与特征：顺序性 、封闭性 、可再现性 多个程序并发执行与特征 ：失去了封闭性、间断性、独立性、随机性 Bernstain条件 进程定义、特征（动态、并发、独立、异步、结构）、进程与程序关系（状态、存在、资源、包含、并发） 进程状态及转换 进程描述PCB（作用、内容） 进程控制：概念、内核、内核的功能

100 3．10 小结（续） 进程的同步与互斥 临界区、临界资源、CS使用规则 同步与互斥 信号量解决同步、互斥 进程通信方式 线程的基本概念