O第2章进程管理

2020-03-01 214浏览

1.操作系统原理 Principle of Operating System 精品课程第 2 章进程管理 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 进程的引入进程的描述与控制线程进程同步经典进程同步问题进程通信死锁问题 Windows 进程管理本章主要内容
2.操作系统原理 Principle of Operating System 2.1 精品课程进程的引入 2.1.1 程序的顺序执行与并发执行 2.1.2 进程的概念 2.1.3 进程的状态 2.1.4 进程的管理 2019年 5月 14日
3.操作系统原理 Principle of Operating System 精品课程 1 ．程序的顺序执行程序的顺序执行是指必须严格地按照某种次序逐个地执行，即只有当一个操作结束后，才能开始后继操作。 2019年 5月 14日
4.操作系统原理 Principle of Operating System 程序顺序执行的特征  执行的顺序性  环境的封闭性  结果的确定性  过程的可再现性 2019年 5月 14日精品课程
5.操作系统原理 Principle of Operating System 精品课程 2 ．程序的并发执行操作系统中引入并发程序设计技术后，程序的执行不再是顺序的，一个程序未执行完而另一个程序已投入运行，程序外部的顺序特性消失，程序与程序的执行不再一一对应。 2019年 5月 14日
6.操作系统原理 Principle of Operating System 程序段的并发执行 2019年 5月 14日精品课程
7.操作系统原理 Principle of Operating System 程序并发执行的特征  执行的间断性  环境的不封闭性  结果的不确定性  过程的不可再现性 2019年 5月 14日精品课程
8.操作系统原理 Principle of Operating System 2.1 2.1.1 2.1.2 2.1.3 2.1.4 2019年 5月 14日精品课程进程的引入程序的顺序执行与并发执行进程的概念进程的状态进程的管理
9.操作系统原理 Principle of Operating System 精品课程 1 ．进程的定义进程的多种定义中能反映进程实质的定义有： 是程序的一次执行。 计算机中正在运行的程序的一个实例。 可以分配给处理机并由处理机执行的一个实体。 是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。 2019年 5月 14日
10.操作系统原理 Principle of Operating System 精品课程 2 ．进程的类型从操作系统角度，可将进程分为系统进程和用户进程两大类。 系统进程系统进程属于操作系统的一部分，它们运行操作系统程序，完成操作系统的某些功能，也被称作守护（ daemon ）进程 2019年 5月 14日
11.操作系统原理 Principle of Operating System 精品课程  用户进程用户进程运行用户程序，直接为用户服务。所谓“用户程序”，不一定是用户自己编写的程序，在操作系统之上运行的所有应用程序都被称作用户进程。 2019年 5月 14日
12.操作系统原理 Principle of Operating System 3 ．进程的特征 动态性 共享性 独立性 并发性 异步性 结构性 2019年 5月 14日精品课程
13.操作系统原理 Principle of Operating System 精品课程 4 ．进程和程序的关系 进程是动态的，程序是静态的 进程是暂时的，程序是永久的 进程与程序的组成不同 一个程序可以对应多个进程，但一个进程只能对应一个程序段 2019年 5月 14日
14.操作系统原理 Principle of Operating System 2.1 2.1.1 2.1.2 2.1.3 2.1.4 2019年 5月 14日精品课程进程的引入程序的顺序执行与并发执行进程的概念进程的状态进程的管理
15.操作系统原理 Principle of Operating System 1 ．三状态进程模型等待条件满足 2019年 5月 14日精品课程
16.操作系统原理 Principle of Operating System 2 ．五状态进程模型等待条件满足 2019年 5月 14日精品课程
17.操作系统原理 Principle of Operating System 3 ．挂起状态进程模型（Ⅰ）单挂起状态进程模型 2019年 5月 14日精品课程
18.操作系统原理 Principle of Operating System 3 ．挂起状态进程模型（Ⅱ）双挂起状态进程模型 2019年 5月 14日精品课程
19.操作系统原理 Principle of Operating System 精品课程 2.1 进程的引入 2.1.1 2.1.2 2.1.3 2.1.4 2019年 5月 14日程序的顺序执行与并发执行进程的概念进程的状态进程的管理
20.操作系统原理 Principle of Operating System 精品课程在操作系统中同时存在多个进程，它们又对应着不同的或相同的程序段以及进程运行所需的各种独立的、共享的系统资源。因此进程管理的功能有以下几个方面： 进程的控制 进程的同步 进程的通信 进程的调度 进程的安全 2019年 5月 14日
21.操作系统原理 Principle of Operating System 第 2 章进程管理 2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题精品课程
22.操作系统原理 Principle of Operating System 2.2 进程的描述与控制 2.2.1 进程的描述 2.2.2 进程的控制 2019年 5月 14日精品课程
23.操作系统原理 Principle of Operating System 精品课程进程的静态描述由三部分组成：进程控制块、有关程序段和与该程序段相关的数据结构集合。 2019年 5月 14日
24.操作系统原理 Principle of Operating System 精品课程 1 ．进程控制块 PCB PCB 有时也称为进程描述块（ Process Descriptor Block ），是系统为描述进程而设计的一种数据结构。—个进程只有一个 PCB ， PCB 是进程存在与否的唯一标记，一个进程的 PCB 结构都是全部或部分常驻内存的。 PCB 基本内容：标识信息、现场信息、控制信息 2019年 5月 14日
25.操作系统原理 Principle of Operating System 精品课程进程控制块的主要作用有：  标识进程的存在。系统创建进程时，就为之创建一个 PCB ；进程结束时，系统又回收其 PCB ，进程便随之消亡。  为系统控制和管理进程提供所需的一切信息。 2019年 5月 14日
26.操作系统原理 Principle of Operating System 精品课程 2 ． PCB 的组织方式在一个系统中，通常可拥有数十个、数百个甚至上千个 PCB 。为了有效地进行进程管理，系统必须对进程进行合理的组织。 顺序表定义一个 PCB 结构数组。这种方式不区分进程状态，将所有 PCB 连续地存放在内存区中。 2019年 5月 14日
27.操作系统原理 Principle of Operating System 精品课程 索引表系统根据进程的状态，分别为具有相同状态的 PCB 建立一张索引表。通常， PCB 表采用静态存储分配方案，定义为 PCB 结构数组；各种索引表采用动态存储分配方案，索引表中存入相应 PCB 数组元素的下标值。 2019年 5月 14日
28.操作系统原理 Principle of Operating System 精品课程 链表系统根据 PCB 的状态，把相同状态的 PCB 链接成一个 PCB 链表队列，这样，可形成就绪进程队列、阻塞进程队列等。对就绪进程队列，可根据其优先级的不同，将优先级高的 PCB 排在前面。此外，系统也可以根据阻塞原因的不同，形成等待各种外设 I/O 操作完成的队列、等待各种事件发生的队列。 2019年 5月 14日
29.操作系统原理 Principle of Operating System 精品课程 3 ．进程上下文进程上下文是进程执行活动全过程的静态描述。它包括系统中与执行该进程有关的各种寄存器的值，进程段在经过编译之后形成的机器指令代码集（或称正文段）、数据集及各种堆栈值和 PCB 结构。 2019年 5月 14日
30.操作系统原理 Principle of Operating System 精品课程 4 ．进程空间每一个进程都有自己的地址空间，该空间称为进程空间或虚空间，进程空间又划分为用户空间和系统空间两部分。用户程序在用户空间执行，操作系统内核程序则在进程的系统空间内执行。 2019年 5月 14日
31.操作系统原理 Principle of Operating System 2.2 进程的描述与控制 2.2.1 进程的描述 2.2.2 进程的控制 2019年 5月 14日精品课程
32.操作系统原理 Principle of Operating System 精品课程进程控制，是指系统使用一些具有特定功能的程序段来创建进程、撤消进程以及完成进程各状态间的转换。这些程序段是机器指令的延伸，由若干条机器指令构成，用以完成特定功能，且在管态下执行，执行过程中是不可分割的，不允许被中断，并且它是顺序执行的（不允许并发），我们把这样的程序段叫作原语。 2019年 5月 14日
33.操作系统原理 Principle of Operating System 用于进程控制的原语有： 创建原语 撤销原语 阻塞原语 唤醒原语 挂起原语和激活原语 2019年 5月 14日精品课程
34.操作系统原理 Principle of Operating System 第 2 章进程管理 2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题精品课程
35.操作系统原理 Principle of Operating System 2.3 线程 2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程 2.3.5 线程的描述与控制 2019年 5月 14日精品课程
36.操作系统原理 Principle of Operating System 精品课程 1 ．线程的定义线程的定义情况与进程类似，存在多种不同的提法： 线程是进程内的一个执行单元。 线程是进程内的一个可调度实体。 线程是程序（或进程）中相对独立的一个控制流序列。 2019年 5月 14日
37.操作系统原理 Principle of Operating System 精品课程 2 ．多线程多线程是指操作系统支持的一个进程中执行多个线程的能力，这些线程共享该进程资源，驻留在相同的地址空间中，共享数据和文件。如果一个线程修改了存储空间中的一项数据，其它线程访问该数据项时就获得了改变之后的结果。如果一个进程以只读方式打开了一个文件，同一进程中的其它线程也能从该文件中读数据。 2019年 5月 14日
38.操作系统原理 Principle of Operating System 精品课程单线程进程 ( 模型 ) 用户地址空间进程控制块用户堆栈进程控制块用户堆栈用户地址空间系统堆栈系统堆栈进程 2019年 5月 14日管理者执行序列
39.操作系统原理精品课程 Principle of Operating System 多线程进程模型多线程进程模型进程控制块用户地址空间 2019年 5月 14日线程 1 线程 N 线程控制块线程控制块用户堆栈用户堆栈系统堆栈系统堆栈
40.操作系统原理 Principle of Operating System 精品课程 3 ．进程与线程的比较线程具有许多传统进程所具有的特征，故又称为轻型进程（ Light-Weight Process ）或进程元；而传统的进程称为重型进程（ Heavy-Weight Process ），它相当于只有一个线程的任务。 2019年 5月 14日
41.操作系统原理 Principle of Operating System 可以从以下几个角度来比较进程和线程： 调度切换。 并发性。 地址空间资源。 通信关系。 系统资源的拥有。 系统开销 2019年 5月 14日精品课程
42.操作系统原理 Principle of Operating System 2.3 线程 2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程 2.3.5 线程的描述与控制 2019年 5月 14日精品课程
43.操作系统原理 Principle of Operating System 精品课程与进程类似，线程也有生命周期，也存在各种状态。它的主要状态有运行、就绪和阻塞。正在运行的线程拥有 CPU 并且是活跃的，被阻塞的线程等待某个事件的发生或等待其它线程来释放它，就绪线程可被调度执行。由于线程不是资源的拥有单位，挂起状态对线程没有意义。所以，线程的状态转换类似于进程的三态模型。与线程级状态变化有关的基本操作原语主要有四个，分别是创建原语、阻塞原语、解除阻塞原语和终止原语。 2019年 5月 14日
44.操作系统原理 Principle of Operating System 2.3 线程 2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程 2.3.5 线程的描述与控制 2019年 5月 14日兰州理工大学计算机与通信学院精品课程
45.操作系统原理 Principle of Operating System 精品课程教材图 2-8 显示了执行两个对不同主机的远程过程调用（ RPC ）获得的组合结果。在单线程环境中，这两个结果是顺序获得的，故程序要依次等待每一个服务器的响应。如用各自的线程执行 RPC 以获得调用结果的方法重写程序，性能就获得实质性的提高。当然，如果这个程序是在单处理机的环境下执行，调用请求是串行地发出的，结果的处理也是串行地进行的。 2019年 5月 14日兰州理工大学计算机与通信学院
46.操作系统原理 2019年 5月 14日 Principle of Operating System 精品课程
47.操作系统原理 Principle of Operating System 2.3 线程 2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程 2.3.5 线程的描述与控制 2019年 5月 14日精品课程
48.操作系统原理 Principle of Operating System 精品课程线程在有的系统中，实现的是用户级线程（ ULT ， User-Level-Threads ），这种线程不依赖于内核。而另一些系统（如 Mach 和 OS ／ 2 操作系统）实现的是内核级线程（ KLT ， Kernel-LevelThreads ），这种线程依赖于内核。也有一些系统如 Solaris 操作系统，则提供了混合式线程，同时支持这两种类型的线程。 2019年 5月 14日
49.操作系统原理 Principle of Operating System 精品课程 1 ．内核级线程在纯 KLT 机构中，所有的线程管理工作是由内核完成的。内核专门提供了一个 KLT 应用程序设计接口（ API ），供开发者使用。 KLT 方法的主要优点是内核能同时调度一个进程中的多个线程在多处理机上运行。同时，如果进程中的一个线程被阻塞，内核能调度同一进程中的其它线程，也可以运行其它进程中的线程。 KLT 方法的另一优点是内核本身也用多线程技术实现，从而能提高系统的执行效率和速度。 KLT 方法的主要缺点是应用程序的线程在目态运行，而线程调度和管理又在内核实现，所以在同一进程内将控制从一个线程转换到另一个线程时需要用户态——内核态——用户态的 2019年 5月 14日兰州理工大学计算机与通信学院切换。
50.操作系统原理 Principle of Operating System 精品课程 2 ．用户级线程在纯 ULT 机构中，管理线程的所有工作是由应用程序来完成的，系统内核并不能感觉到这类线程的存在，所以从内核角度考虑，就是按正常的方式管理，即单线程进程，这种方法的一个明显优点是，用户级线程库可以在不支持线程的操作系统上实现。与 KLT 相比， ULT 有以下特点： 线程间的切换不需要核心态特权。 调度程序是面向特定应用系统的。 ULT 能在任何操作系统上运行 2019 年 5月 14日。
51.操作系统原理 Principle of Operating System 精品课程 3 ．混合式线程在采用混合式线程的系统中，内核支持 KLT 多线程的建立、调度和管理。同时也提供线程库，允链链用程序建立、链链链链度和管理链 ULT 。混合式线程中，一个应用程序中的多个线程能同链在多链链链链理机上并行链链链链链链行，且阻塞一个链链链链链链链链程链链并不需要阻塞整个链链程，若链链链链计得当，混合式多链链链链链链链链链程机链制能够结合两者的优点，舍弃它们的缺点。 2019年 5月 14日
52.操作系统原理 2019年 5月 14日 Principle of Operating System 精品课程
53.操作系统原理 Principle of Operating System 2.3 线程 2.3.1 线程的引入 2.3.2 线程的状态 2.3.3 线程的并发执行 2.3.4 用户级线程和内核级线程 2.3.5 线程的描述与控制 2019年 5月 14日精品课程
54.操作系统原理 Principle of Operating System 精品课程 1 ．线程的描述支持线程的操作系统中也要为线程设计一种数据结构 ——线程控制块（ Thread Control Block ， TCB ）来标志线程的存在，即每当创建一个新线程时，便要为该线程分配一个 TCB 。不同的操作系统，线程的结构不尽相同，一般包含系统对于线程进行管理所需要的全部信息。不过 TCB 的内容一般较少。 TCB 中的主要信息有：线程标识、程序计数器及状态寄存器等寄存器组、若干堆栈、私用存储器等。 TCB 可能属于操作系统空间，也可能属于用户进程空间，是由线 2019 年 5月 14日程的实现方式决定的。
55.操作系统原理 Principle of Operating System 精品课程 2 ．线程的控制类似于进程控制，线程也具有线程控制模块、同步协调机构以及时钟控制等。线程控制包括了对线程执行环境的控制和状态转换的控制，也具有线程创建、调度、阻塞、唤醒及撤销。进程内各线程的并发执行由同步协调机制完成，可直接在进程局部空间内实现线程通信。线程的存在与消亡也通过线程控制块 TCB 体现出来。 2019年 5月 14日
56.操作系统原理 Principle of Operating System 第 2 章进程管理 2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题精品课程
57.操作系统原理 2.4 Principle of Operating System 进程同步 2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步 2.4.4 多处理机同步 2019年 5月 14日精品课程
58.操作系统原理 Principle of Operating System 精品课程 1 ．进程间的相互关系在多道程序环境中，同一时刻可能有多个进程在计算机中运行。它们之间存在着两种关系： 竞争系统中彼此无关的进程在运行过程中并不知道对方的存在，而且也不受其它进程执行的影响，但是一个进程的执行可能会影响到同其竞争资源的其他进程。进程互斥（ mutual exclusion ）是解决进程间资源竞争关系（间接制约关系）的手段，指若干个共享某一资源的进程并发执行时，任何时刻只允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。 2019年 5月 14日
59.操作系统原理 Principle of Operating System 精品课程例 2-1 、有两个进程 P1 、 P2 ，它们都要使用打印机，如果让它们随意使用，那么就有可能出现这种情况， P1 打印几行接着 P2 再打印几行，打印结果混在一起，很难区分，既使能够区分，也要将各自输出结果从打印纸上剪下来，再用浆糊粘接起来。解决这一问题的办法是，不允许一台打印机让两个进程同时使用，应在一个进程用完后再让另一进程使用。 2019年 5月 14日
60.操作系统原理 合作。 Principle of Operating System 精品课程某些进程为了完成同一任务分工合作，由于合作的每一个链链程都是独立地以不可链链链链链链链链链链知的速度推链链链链链链，链链就需要相互合链链链链链作的进程在某些合作点上协调各自的工作。当合作进程中的一个到达合作点后，在尚未得到其它合作进程发来的消息或信号之前应阻塞自己，直到其合作进程发来协调信号或消息后才能被链醒。链链进程同步（ synchronization ）是解决链程链链链合作链链链系（直接制约关系）的手段，指两个或两个以上进程基于某个条件来链链链它链链的活链链链。一个链链链链程的链链链行依链链链于另一个合作链链链链链进程的消息或信号，当一个进程没有得到来自于另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒。 2019年 5月 14日
61.操作系统原理 Principle of Operating System 精品课程例 2-2 、在一辆公共汽车上，司机和售票员各行其职，独立工作。司机负责开车和到站停车，售票员负责售票和开、关车门。但两者需要密切配合、协调一致。即当司机驾驶的车辆到站并把车辆停稳后，售票员才能打开车门，让乘客上、下车，然后关好车门，这时司机继续开车行驶。 2019年 5月 14日
62.操作系统原理 Principle of Operating System 精品课程 2 ．临界资源和临界区一次只能允许一个进程访问的共享资源称为临界资源。每个进程访问临界资源的那段程序称为临界区（ Critical Section ），简称 CS 区。只有让使用临界资源的进程互斥地进入临界区，才能保证某一进程单独地使用临界资源。并发进程进入相关临界区执行应遵循如下四个准则： 一次至多只允许一个进程进入临界区。 不能让一个进程无限期地在临界区内执行。 不能强迫一个进程无限地等待进入它的临界区。 2019 年 5月 14日 不能假定处理机的速度和限制处理机的数量，也即公平竞
63.操作系统原理 Principle of Operating System 精品课程例 2-3 、某游艺场设置了一个自动计数系统，用一个计数器 count 指示在场的人数。当有一个人进入时，由进程 Pin 实现计数器加 1 ；当有一个人退出时，由进程 pout 实现计数器减 1 。两个进程的程序段如下： void pin(int count){ int R1 ； R1 ＝ count ； R1++ ； count ＝ R1 ； } 2019年 5月 14日 void pout(int count){ int R2 ； R2 ＝ count ； R2-- ； count ＝ R2 ； }
64.操作系统原理 2.4 Principle of Operating System 进程同步 2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步 2.4.4 多处理机同步 2019年 5月 14日精品课程
65.操作系统原理 Principle of Operating System 精品课程 1 ．加锁机制设想有一个共享变量（锁变量） W ，锁有两种状态： w ＝ 0 表示锁已打开，此时临界区内没有进程； W ＝ 1 表示锁被关闭，此时已有某个进程进入临界区。用原语来实现，其中加锁原语用 LOCK （ W ）表示，可描述为：测试 W ，若 W ＝ 1 ，表示资源正在使用，继续反复测试；若 W ＝ 0 ，置 W ＝ l （加链）。链链开锁原语用 UNLOCK （ W ）表示，可描述为： W=0 ； 2019年 5月 14日
66.操作系统原理 Principle of Operating System 精品课程 2 ．信号量机制信号量是一种控制链程互斥和同步的链链链链链链链链链量。从物理意义链链链链链链上理解，信号量的值对应着相应资源的使用情况，当它的值大于 0 链，表示当前可用链链源的数量；当它的链链链链链链链链链链小于 0 时，表示已无可用资源，其绝对值表示等待使用该资源的进程个数，即在该信号量队列上排队的进程数，也就是说，每一个信号量有一个等待队列。对信号量的操作，只允许初始化和执行两个标准的原语 —— P 、 V 原语，或者称为 P 、 V 操作，没有任何其它方法可以链链链和操作信号量。链链链链链链 2019年 5月 14日
67.操作系统原理 Principle of Operating System 精品课程 信号量按其用途可分为两种： ⑴ 公用信号量，用来链系一链链链链无链链链程，每个链链链链程均可在此信号量上执行 P 和 V 操作。初值常常为 1 ，常用于实现并发进程的互斥。 ⑵ 私有信号量，用来链系一链链链链合作链链链程，链链链允链此信号量的拥有进程执行 P 操作，而其合作进程可在其上执行 V 操作。初值常常为 0 或正整数，多用于并发进程同步。 2019年 5月 14日
68.操作系统原理 Principle of Operating System 精品课程 信号量按其取值可分为两种： ⑴ 二元信号量，仅允许取值为 0 和 1 ，主要用于解决进程互斥问题。 ⑵ 一般信号量，允许取值为整数，主要用于解决进程同步问题。 2019年 5月 14日
69.操作系统原理 Principle of Operating System 精品课程 ⑴ 整型信号量设 S 为一个整型变量，除初始化外，仅能通过 P 、 V 原语来访问它，这时 P 操作原语和 V 操作原语定义如下： P （ S ）：当信号量 S 大于 0 时（有可用资源）， S 减 1 ，否则调用 P （ S ）的进程等待直到信号量 S 大于 0 。 V （ S ）：把信号量 S 加 1 。 P 、 V 操作原语描述如下： P （ S ）： while(S<=0) do null operation; S-- ； V （ S ）： S++ ； 2019年 5月 14日
70.操作系统原理 ⑵ 链链型 Principle of Operating System 精品课程信号量 typedef struct semaphore { int value; // 信号量值 , 通常是一个具有非负初值的整型变量 struct pcb *list; // 信号量队列指针 , 初始状态为空 }; void P(semaphore &s) { void V(semaphore &s) { s.value--; s.value++; if(s.value<0) if(s.value<=0) 2019年 5月 14日
71.操作系统原理 Principle of Operating System 精品课程从信号量和 P 、 V 操作的定义可以获得如下推论：推论 1 ：若信号量 S 链正链链，链链链链等于在阻塞链链链链链链程之前链链链链 S 可执信号量链链行的 P 操作数，也就是说，该值等于信号量 S 所代表的实际还可以使用的物理资源数。推论 2 ：若信号量 S 为负值，则其绝对值等于排列在等待该信号量 S 的队列之中的进程个数，恰好等于对信号量 S 链行 P 操作而被阻塞并进入信号量 S 等待队列的进程数。推论 3 ：通常， P 操作意味着申请资源； V 操作相当于释放资源。 2019年 5月 14日
72.操作系统原理 Principle of Operating System 精品课程 ⑶ 二元信号量设 S 为一个记录型数据结构，其中一个分量为整型量 value ，它仅能取值 0 和 1 ，另一个分量为信号量队列 queue 。 ⑷ 利用链链链型信号量链链链链链链链程之链链链的互斥链链引入一个公用信号量 mutex ，它也称为互斥信号量，其初值为 1 ，表示无进程进入临界区。任何欲进入临界区执行的进程，必须先对互斥信号量 mutex 执行 P 操作，即使 mutex 值减 1 ，若减 1 后 mutex 值为 0 ，表示临界资源空闲，执行 P 操作进程可以进入临界区执行；若 mutex 减 1 后的值为负，说明已有进程占有临界资源，执行 P 操作进程必须等待，直到临界资源空闲为止。正在临界区执行的进程，完成临界区操作后，通过执行 V 操作，使 mutex 值加 1 ，表示释放临界资源。 2019年 5月 14日
73.操作系统原理 Principle of Operating System 其算法描述如下： semaphore mutex ＝ 1 ； { P(mutex) ；链界区； V(mutex) ；其余操作； } 2019年 5月 14日精品课程
74.操作系统原理 Principle of Operating System 精品课程例如，对于并发进程 pin 和 pout 中 count 的操作用 P 、 V 原语可描述如下： semaphore mutex ＝ 1 ； pin ： P(mutex); pout ： P(mutex); R1 ＝ count ； R2 ＝ count ； R1++ ； R2-- ； count ＝ R1 ； count ＝ R2 ； V(mutex); V(mutex); 2019年 5月 14日
75.操作系统原理 Principle of Operating System 精品课程用 P 、 V 操作实现进程互斥时应注意： ① 在每个程序中用于实现互斥的 P （ mutex ）和 V （ mute x ）必须成对出现，即先执行 P 操作进入临界区；后执行 V 操作退出临界区。 ② 互斥信号量 mutex 的初值一般为 l 。例 2-4 、设一民航航班售票系统有 n 个售票处。每个售票处通过终端访问系统中的公用数据区，假定用公共数据区中的一些单元 A[k](k ＝ 1 ， 2 ，… ) 分别存放某月某日某次航班的现有票数。设 Pl ， P2 ，…， Pn 表示各售票处的处理进程， Rl ， R2 ，…， Rn 表示各进程执行时所用的工作单元。 2019年 5月 14日
76.操作系统原理 Principle of Operating System 精品课程 ⑸ 利用记录型信号量实现进程之间的同步为了解决进程的同步问题，同样也可以引入信号量机制。若用信号量实现两进程同步，通常设立与进程有关的私用信号量。例 2-5 两个进程 A 、 B 对一个单缓冲区 buf 进行操作，其过程是：只要单缓冲区空， A 进程就向其中送数，若单缓冲区满则等待。只要单缓冲区不空， B 进程就从中取数，若单缓冲区空则等待。 A 进程和 B 进程对单缓冲区的使用关系如图所示。 2019年 5月 14日
77.操作系统原理 Principle of Operating System 单缓冲区的操作 2019年 5月 14日精品课程
78.操作系统原理 Principle of Operating System semaphore sa ＝ 0 ， sb ＝ 0 ； pa ( ) pb ( ) do { do { while(sa==0) { while(sb) { ( 送数到缓冲区 ) P(sb) ； V(sb) ； ( 从缓冲区取数 ) P(sa) ； V(sa) ； ( 其他操作 ) ( 其他操作 ) } }while(1); 2019年 5月 14日 } }while(1); 精品课程
79.操作系统原理 Principle of Operating System 精品课程例如，用信号量实现司机和售票员的同步。设 S1 和 S2 分别为司机和售票员的私用信号量，初值均为 0 ，则司机和售票员的同步过程描述如下： semaphore S1=0; S2=0 ；司机进程：售票员进程： do{ do{ 正常行车；售票；到站停车； P(S2) V(S2) ；开车门； P(S1) ；关车门；开链链； V(S1) ； }while(1); }while(1); 2019年 5月 14日
80.操作系统原理 Principle of Operating System 精品课程例 2-6 桌上有一个空盘子，只允许放一个水果。爸爸可以向盘中放苹果，也可以向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一个水果，请用 P 、 V 操作实现爸爸、儿子、女儿三个“并发进程”的同步。分析：这是一个明显的同步问题，也称为生产者和消费者问题。爸爸可以向盘子中放入两类水果：橘子、苹果；然后儿子、女儿每人可以消费其中的一种水果。爸爸是生产者，子女是消费者，也就是只有爸爸放入水果，子女才能消费水果；只有子女消费完水果，爸爸才能再次放入水果。 2019年 5月 14日
81.操作系统原理 Principle of Operating System 精品课程设 empty 、 orange 和 apple 分别为爸爸、儿子和女儿的私用信号量。 empty 表示盘子是否为空，其含义是爸爸是否可以开始放入水果，初值为 1 表示可以放； orange 表示盘中是否有橘子，其含义是儿子是否可以开始取橘子，其初值为 0 表示不能取橘子； apple 表示盘中是否有苹果，其含义是女儿是否可以开始取苹果，其初值为 0 表示不能取苹果。则爸爸、儿子和女儿的同步过程描述如下： semaphore empty=1, orange=apple=0; 2019年 5月 14日
82.操作系统原理 Principle of Operating System 父链链链程：链儿子进程：女儿进程： do{ do{ do{ P(empty); P(orange); P(apple); 精品课程将水果放入链链中；链从盘中取出橘子；从盘中取出苹果； if ( 放入的是橘子 ) V(empty); V(empty); V(orange); 吃橘子；吃苹果； else V(apple); }while(1); }while(1); }while(1); 2019年 5月 14日
83.操作系统原理 Principle of Operating System 精品课程用 P 、 V 操作实现同步时应注意： 分析进程间的制约关系，确定信号量种类。在保持进程间有正确同步关系的情况下，哪个进程应先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。 信号量的初值与相应资源的数量有关，也与 P 、 V 操作在程序代码中出现的位置有关。 同一信号量的 P 、 V 操作要“成对”出现，但它们分别在不同的进程代码中。 2019年 5月 14日
84.操作系统原理 Principle of Operating System 精品课程 ⑹ 信号量集信号量集是指同时需要多个资源时的信号量操作。 ①AND 型信号量集 AND 型信号量集是指同时需要多种资源且每种资源都需占用一个时的信号量操作。用一个原语申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配。我们称 AND 型信号量集 P 原语为 Swait （ Simultaneous Wait ）， V 原语为 Ssignal （ Simultaneous Signal ）。在 Swait 中，各个信号量的次序并不重要，虽然这会对进程归入哪个阻塞队列产生影响，但由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会出现死锁。 2019年 5月 14日
85.操作系统原理 Principle of Operating System 精品课程 Swait 和 Ssignal 函数可以描述如下： Swait （ s1,s2,…… ， s n） { while(1) { if(s1>=1 && s2>=1 ……&& sn>=1) for(i=1;i<=n;i++) --si; else { 调用进程进入第一个小于 1 信号量的等待链列；阻塞调用进程； } 2019年 5月 14日 } } Ssignal （ s1,s2,…… ， sn ） { for(i=1;i<=n;i++) {++si; { 从等待队列中取出进程 p ； if( 进程 p 通过 Swait 中的测试) 进程 p 进入就绪队列； else 进程 p 进入某等待队列； }
86.操作系统原理 Principle of Operating System 精品课程 ② 一般信号量集一般信号量集是指同时需要多种资源，每种资源被占用的数目不同，而且可分配的资源还存在一个临界值时的信号量处理。由于一次需要 n 个某类临界资源，如果通过 n 次 P 原语操作申请这 n 个临界资源，那么操作效率很低，并可能出现死锁，一般信号量集的基本思路就是在 AND 型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。进程多信号量 si 的测试值为 ti （表示信号量的判断条件，要求 si≥ti ，即当资源数量低于 ti 时，便不予分配），申请第 i 类资源数为 di ，对应的 P 、 V 原语格式为： Swait （ s1,t1,d1,…… ， sn, tn,dn ）； Ssignal （ s1,t1,d1,…… ， sn, tn,dn ）； 2019年 5月 14日
87.操作系统原理 Principle of Operating System 精品课程 3 ．管程机制基本思想是把信号量及其操作原语封装在一个对象内部。也就是说，将共享资源及能够对共享资源进行的所有操作集中在一个模块中。可把“管程”定义为关于共享资源的数据结构和能为并发进程在该数据结构上执行的一组操作，这组操作能使进程同步和改变管程中的数据。管程的结构 2019年 5月 14日
88.操作系统原理 Principle of Operating System 精品课程管程的特性： ⑴ 局部于管程内的数据结构只能被管程内的过程所访问；反之，局部于管程内的过程只能访问该管程内的数据结构。 ⑵ 进程要想进入管程，必须调用管程内的某个过程； ⑶ 一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程可用。管程实现进程同步时，需引入若干条件变量ci 及相关的两个操作原语： Wait 和 Signal 。 Wait(ci) ：若链链求服链链链没有链链链足，链链链将链链程阻塞在链ci链的等待队列上链 Signal(ci) ：恢复执行前应先唤醒在条件 ci 上执行 Wait 而阻塞的那个链链程。如链链果存在几个这样的进程，则从中挑选一个；如果没有这种进程，则什么也不做。 2019年 5月 14日
89.操作系统原理 2.4 Principle of Operating System 进程同步 2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步 2.4.4 多处理机同步 2019年 5月 14日精品课程
90.操作系统原理 Principle of Operating System 精品课程一个进程中的所有线程共享相同的地址空间和其它资源，在同一个进程内，一个线程对资源的改变会影响其它线程的环境，因此必须同步各个线程的活动，使它们之间不会互相干扰或破坏数据结构。通常线程的同步技术与进程的同步技术相同，可以采用解决进程同步的技术来实现线程的同步。 2019年 5月 14日
91.操作系统原理 2.4 Principle of Operating System 进程同步 2.4.1 进程同步的基本概念 2.4.2 进程同步的解决方法 2.4.3 线程同步 2.4.4 多处理机同步 2019年 5月 14日精品课程
92.操作系统原理 Principle of Operating System 精品课程在多处理机系统中，进程和 CPU 之间的关系由多对一变为多对多，因此并发控制变得更为复杂。在多处理机的计算机中，都有下面一条指令： TSL RX, LOCK 称为测试并加锁指令，它的功能是将一个内存中的字“锁 LOCK” 读到寄存器 RX 中，然后在该内存地址上存放一个非零值。为了在多 CPU 环境中实现互斥，需要硬件进一步的支持，即 TSL 指令必须首先锁住总线（即“锁总线”），阻止其它的 CPU 访问，然后进行共享内存的读写操作，再解除总 2019年 5月 14日线。
93.操作系统原理 Principle of Operating System 第 2 章进程管理 2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题精品课程
94.操作系统原理 2.5 Principle of Operating System 经典进程同步问题 2.5.1 生产者——消费者问题 2.5.2 哲学家进餐问题 2.5.3 读者——写者问题 2019年 5月 14日精品课程
95.操作系统原理 Principle of Operating System 精品课程生产者——消费者问题是用于解决一群生产者和消费者之间的进程互斥和进程同步问题。生产者进程可以是计算进程、发送进程等；而消费者进程可以是打印进程、接收进程等等。生产者——消费者问题可以描述为由—些不确定数目的生产者和消费者进程及—个有限的共享缓冲区所构成的系统。生产者进程不断地向共享缓冲区写入数据（即生产数据），而消费者进程从共享缓冲区中读出数据（即消费数据）。 2019年 5月 14日
96.操作系统原理 Principle of Operating System 精品课程要求：①生产者不应覆盖—个满的缓冲区；②消费者不应使用一个空的缓冲区；③生产者消费者必须按一种互斥的方式访问缓冲区。 1 ．用记录型信号量解决生产者和消费者问题可设置三个信号量： full 和 empty 为两个同步信号量，其中 full 表示有数据的缓冲块数目，初值为 0 ； empty 表示空的缓冲块数目，初值为 N ； mutex 用于访问缓冲区时的互斥，初值为 1 。实际上， full 和 empty 之间存在如下关系： full+empty=N 2019年 5月 14日
97.操作系统原理 Principle of Operating System 精品课程 producer i(i=1,2,……) consumer j (j=1,2,……) do { do { 生产数据 ; P （ full ） ; P （ empty ） ; P （ mutex ） ; P （ mutex ） ; 从共享缓冲区读出数据 ; 向共享缓冲区写入数据 ; V （ mutex ） ; V （ mutex ） ; V （ empty ） ; V （ full ） ; 消费数据 ; }while(1); 2019年 5月 14日 }while(1);
98.操作系统原理 Principle of Operating System 精品课程 2 ．用 AND 型信号量集解决生产者和消费者问题用 AND 型信号量集解决生产者和消费者问题，即用 Swait 和 Ssignal 函数来代替 P 、 V 操作。 producer i(i=1,2,……) consumer j(j=1,2,……) do { do { 生产数据 ; Swait （ full,mutex ） ; Swait （ empty,mutex ） ; 从共享缓冲区读出数据 ; 向共享缓冲区写入数据 ; Ssignal （ mutex,empty ） ; Ssignal （ mutex,full ） ; 消费数据 ; }while(1); }while(1); 2019年 5月 14日
99.操作系统原理 2.5 Principle of Operating System 经典进程同步问题 2.5.1 生产者——消费者问题 2.5.2 哲学家进餐问题 2.5.3 读者——写者问题 2019年 5月 14日精品课程
100.操作系统原理 Principle of Operating System 精品课程哲学家用餐问题也是一个典型的同步问题，是由 Dijkstra 提出并解决。该问题是描述五位哲学家围坐在一个圆桌旁，每位就餐者需要两把叉子，但桌上只提供了 5 把，在每个相邻座位间都放有一把。为了吃到东西，每个哲学家必须拿起他左、右两侧的叉子。他们的活动规律都是一样的，即思考、吃饭、思考……。叉子是这个问题中的临界资源，在一段时间内只允许一个哲学家使用，即每把叉子都必须互斥使用。设 5 个哲学家对应 5 个进程 p0 ， P1 ，……， p4 ， 5 把叉子对应 5 个资源 R0 ， R1 ，…， R4 。进程 pi 左边的叉子为 Ri ，右边的叉子为 R(i+1) ，而进程 P4 左边的叉子为 R4 ，右边的叉子为 R0 。 2019年 5月 14日
101.操作系统原理 2019年 5月 14日 Principle of Operating System 精品课程
102.操作系统原理 Principle of Operating System 精品课程 1 ．用记录型信号量解决哲学家用餐问题 semaphore fork[5]={1,1,1,1,1}; 进程 pi （ i=0,…,4 ） do{ 思考； P(fork[i]); P(fork[i+1] %5); 用餐； V(fork[i]); V(fork[i+1] % 5); }while(1); ？ 2019年 5月 14日问题？解决方案
103.操作系统原理 Principle of Operating System 精品课程 2 ．用 AND 型信号量集解决哲学家用餐问题在哲学家用餐问题中，由于每位哲学家要申请两个临界资源（两把叉子），故可用 AND 型信号量集来解决。进程 pi （ i=0,…,4 ） do{ 思考； Swait(fork[i] ,fork[i+1] % 5); 用餐； Ssignal(fork[i],fork[i+1] % 5); }while(1); 2019年 5月 14日
104.操作系统原理 2.5 Principle of Operating System 经典进程同步问题 2.5.1 生产者——消费者问题 2.5.2 哲学家进餐问题 2.5.3 读者——写者问题 2019年 5月 14日精品课程
105.操作系统原理 Principle of Operating System 精品课程一个数据对象（比如一个文件或记录）若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求修改它，我们把那些只想读的进程称之为 “读者 ”；而把要求修改的进程称为 “写者 ”。显然，所有读者和写者共享一个文件（或一组数据）时要协调工作，要求： ① 读者进程只要求读该对象的内容，且多个读者可同时对文件执行读操作； ② 写者进程则要求修改它，某一时刻只允许一个写者进程往文件中写信息； ③ 任一写者进程在完成写操作之前不允许其它读者或写者工作； ④ 写者进程执行写操作前，应让所有的写者和读者进程退出。 2019年 5月 14日
106.操作系统原理 Principle of Operating System 精品课程 1 ．用记录型信号量解决读者与写者问题可设置两个信号量： rwmutex 用于实现一个写者与其它读者／写者互斥地访问共享数据；由于多个读者可同时对共享数据或文件执行读操作，所以需设置 read_count 计数器，用以记录正在读共享数据时的读者数，因 read_count 是所有读者的共享变量，对它的修改操作必须互斥进行，设 r 信号量用于读者互斥地访问 read_count 。 rwmutex 、 r 的初值均为 1 ， read_count 的初值为 0 ，即有： semaphore rwmutex=1,r=1; int read_count=0; 2019年 5月 14日
107.Principle of Operating System 操作系统原理读者进程 read i (i=1,2,……) do{ P(r); read_count=read_count+1; 写者进程 write j (j=1,2, ……) if(read_count==1) P(rwmutex); do{ V(r); P(rwmutex); 读数据；写文件； P(r); read_count=read_count-1; if(read_count==0) V(rwmutex); V(r); }while(1); 2019年 5月 14日精品课程 V(rwmutex); }while(1);
108.操作系统原理 Principle of Operating System 精品课程当有进程在读而使一个请求写的进程阻塞时，如果仍有进程不断地请求读则写进程将被长期地推迟运行。但在实际系统中往往希望让写者优先。即当有进程在读文件时，如果有进程请求写，那么新的读者被拒绝，待现有读者完成读操作后立即让写者运行，只当无写者工作时才让读者工作。下面是写者优先的程序。其中信号量 rwmutex 用于实现一个写者与其它读者／写者互斥地访问共享数据，初值为 1 ，另一信号量 rn ，初值为 n ，表示系统中最多有 n 个进程可同时进行读操作： semaphore rwmutex=1; semaphore rn=n; 2019年 5月 14日
109.操作系统原理 Principle of Operating System 精品课程读者进程 read i (i=1,2, 写者进程 write j (j=1,2,……) ……,n) do{ do{ P(rwmutex); P(rn); P(rwmutex); for(k=1;k<=n;k++) P(rn); V(rwmutex); 写文件；读数据； for(k=1;k<=n;k++) V(rn); }while(1); V(rn); V(rwmutex); }while(1); 2019年 5月 14日
110.操作系统原理 Principle of Operating System 精品课程 2 ．用 AND 信号量集解决读者与写者问题引入信号量 S ，其初值为 n ，通过执行 Swait(S,1,1) 操作，来控制读者的数目，每当有一个读者进入时，都要先执行 Swait(S,1,1) 操作，使 S 的值减 1 。当有 n 个读者进入后， S 变为 0 ，第 n+1 个读者要进入读时，会因 Swait(S,1,1) 操读者进程 read i (i=1,2, 写者进程 write j (j=1,2,……) 作失败而被阻塞。 ……,n) do{ do{ Swait(mx,1,1,S,n,0); Swait(S,1,1); 写数据； Swait(mx,1,0); Ssignal （ mx, 1 ）；读数据； Ssignal （ S,1 ）； }while(1); 2019年 5月 14日 }while(1);
111.操作系统原理 Principle of Operating System 第 2 章进程管理 2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题精品课程
112.操作系统原理 2.6 Principle of Operating System 进程通信 2.6.1 信号通信机制 2.6.2 共享文件通信机制 2.6.3 共享存储器通信机制 2.6.4 消息传递通信机制 2019年 5月 14日精品课程
113.操作系统原理 Principle of Operating System 精品课程进程通信 IPC （ Inter Process Communication ）是完成进程之间的信息交换。进程间交换信息的方式很多，根据通信实施的方式和数据存取的方式，进程通信方式可归结为信号通信方式、共享存储器方式、消息传递方式和共享文件方式。信号（ signal ）机制又称软中断，是一种进程之间进行通信的简单通信机制，通过发送一个特定信号来通知进程某个异常事件发生，并进行适当处理。信号不但能从一个内核发给一个进程，也能由一个进程发给同组的另一个进程或多个进程，一个信号的发送是指把它送到指定进程的 PCB 中的软中断域的某一位，在进程被唤醒继续运行时，或者在进程准备从系统调用请求返回时，处理信号。 2019年 5月 14日
114.操作系统原理 2.6 Principle of Operating System 进程通信 2.6.1 信号通信机制 2.6.2 共享文件通信机制 2.6.3 共享存储器通信机制 2.6.4 消息传递通信机制 2019年 5月 14日精品课程
115.操作系统原理 Principle of Operating System 精品课程利用一个打开的共享文件连接两个相互通信的进程。在操作系统中，这种共享文件方式也被称为管道通信。管道通信是发送进程和接收进程之间通过一个管道交流信息，管道是单向的，发送进程视管道为输出文件，即向管道写入数据，接收进程视管道为输入文件，即从中读取数据。先写入的必定先读出，即管道通信的工作是单向的并以先进先出为顺序。管道的实质是一个共享文件，数据以自然字符流的方式写入和读出，是无界的，不以消息为单位，可进行大批量数据交换，利用外存来进行数据通信，因此，管道通信基本上可以借助于文件系链原有的机制来链链链链链链链链链，包括管道文件的建立、链链链链链链链链链链打开、关闭、读写等等。 2019年 5月 14日
116.操作系统原理 Principle of Operating System 精品课程发送进程和接收进程之间相互合作时，必须做到以下几点： ⑴ 一个进程正在使用某个管道写入或读出数据时，另一个进程必须等待，即管道文件是一个临界资源，双方必须互斥访问。 ⑵ 发送进程和接收进程必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送和接收信息。这时会发出 SIGPIPE 信号通知进程。 ⑶ 发送进程和接收进程之间，必须实现同步。 ⑷ 进程在关闭管道的读出或写入端时，应唤醒等待写或读此管道的进程。 2019年 5月 14日
117.操作系统原理 2.6 Principle of Operating System 进程通信 2.6.1 信号通信机制 2.6.2 共享文件通信机制 2.6.3 共享存储器通信机制 2.6.4 消息传递通信机制 2019年 5月 14日精品课程
118.操作系统原理 Principle of Operating System 精品课程通过共享数据结构或共享存储区。共享数据结构是系统为保证进程正常运行而设置的专门机制，利用某个专门数据结构存放进程间需要交换的数据；共享存储区是在内存中分配一片专门的空间作为共享区域，需要进行通信的各个进程把共享存储区附加到自己的地址空间中，然后就像正常操作一样对共享区中的数据进行读或写。 2019年 5月 14日
119.操作系统原理 2.6 Principle of Operating System 进程通信 2.6.1 信号通信机制 2.6.2 共享文件通信机制 2.6.3 共享存储器通信机制 2.6.4 消息传递通信机制 2019年 5月 14日精品课程
120.操作系统原理 Principle of Operating System 精品课程 1 ．消息的概念消息是指进程之间以不连续的成组方式发送的信息，由消息头和消息体组成。在消息传递通信机制中，至少需要提供两条高级通信原语 send 和 receive ，前者向一个给定的目标发送一条信息，后者则从一个给定的源接收一条信息。 2 ．直接通信直接通信方式通过消息缓冲区实现通信，企图发送或接收消息的每个进程必须指出消息发给谁或从谁那里接收消息，用 send 原语和 receive 原语来实现进程之间的直接通信。 2019年 5月 14日
121.操作系统原理 Principle of Operating System 精品课程 ⑴ send （发送消息）原语 send （ P ，消息）发送原语是把消息发送到接收进程 P 存放消息的缓冲区。其工作原理是：首先调用“寻找目标进程的 PCB” 程序查找接收进程 P 的 PCB ，如果接收进程存在，申请一个存放消息的缓冲区，消息缓冲区为空时，接收此消息的进程因等待此消息的到来而处于阻寒状态，则唤醒此进程，并把消息的内容、发送原语的进程名和消息等复制到预先申请的存放消息的缓冲区，且将存放消息的缓冲区连接到接收进程的 PCB 上；如果接收进程不存在，则由系统给出一个“哑”回答；最后控制返回到发送消息的进程继续执行，或转入进程调度程序重新分配处理机。如果消息缓冲区已满，则返回到非同步错误处理程序入口进行特殊处理。 2019年 5月 14日
122.操作系统原理 Principle of Operating System 精品课程 ⑵ receive （接收消息）原语 receive （ Q ，消息）接收原语用来读取进程 Q 的消息，接收进程读取消息之前，在自己的空间中确定一个接收区。把消息缓冲区中的消息内容、消息长度以及发送进程的名字都读取到接收区并释放消息缓冲区，如果没有消息可读取，则阻塞接收进程，直至消息发送来为止。至此，接收消息的工作结束，返回到接收进程，接收进程继续执行。 2019年 5月 14日
123.操作系统原理 Principle of Operating System 精品课程 3 ．间接通信通过信箱（ mailbox ）实现通信，信箱是一种公共的存储区，作为通信的一种中间实体。在逻辑上信箱由信箱头和信箱体组成，每个信箱有自己唯一的标识符。其中信箱头指出信箱容量、信箱格式、存放信件位置的指针等；信箱体用来存放信件，包含若干个信格，每个格可容纳一封信。 2019年 5月 14日
124.操作系统原理 Principle of Operating System 精品课程 ⑴ send （发送消息）原语 send （ A ，信件）发送原语是把一封信件（消息）传送到信箱 A 。如果指定的信箱未满，则将信件送入信箱中，并唤醒等待该信箱中信件的进程；否则，发送信件者被置成等待信箱的阻塞状态。 ⑵ receive （接收消息）原语 receive （ A ，信件）接收原语用来从信箱 A 接收一封信件（消息）。如果指定信箱中有信，则取出一封信，并唤醒等待信箱的进程；否则，接收信件者被置成等待信箱中信件的阻塞状态。 2019年 5月 14日
125.操作系统原理 Principle of Operating System 4 ．消息传递实现的若干问题 信箱容量问题 链于链多链链程与信箱相链链链链链链的信件接收链链链链链 信箱的所有权问题 信件的格式问题及其它相关问题 通信链程的同步链链链链链链 2019年 5月 14日精品课程
126.操作系统原理 Principle of Operating System 第 2 章进程管理 2.1 进程的引入 2.2 进程的描述与控制 2.3 线程 2.4 进程同步 2.5 经典进程同步问题 2.6 进程通信 2.7 死锁问题精品课程
127.操作系统原理 2.7 Principle of Operating System 死锁问题 2.7.1 死锁的形成与定义 2.7.2 死锁的预防 2.7.3 死锁的避免 2.7.4 死锁的检测与恢复 2.7.5 鸵鸟算法 2.7.6 一种综合的死锁策略 2.7.7 饥饿与活锁 2019年 5月 14日精品课程
128.操作系统原理 Principle of Operating System 精品课程计算机系统的各种软、硬件资源都由操作系统进行管理和分配。让并发进程在执行过程中根据各自的需要而动态的申请、占有和释放有限的系统资源，正是操作系统为了尽可能地提高资源利用率而采取的管理和分配技术。但是，如果操作系统对资源的分配不当，可能会出现若干个进程相互之间都无休止的等待对方释放自己所需资源的状态，这是系统的一种致命状态——死锁状 2019年 5月 14日态。
129.操作系统原理 Principle of Operating System 精品课程 1 ．死锁的形成（原因）例 2-7 、设某系统中有两个并发进程 P 和 Q ，它们都要申请共享资源 R1 和 R2 ，共享资源 R1 和 R2 均有 1 个。若两进程按下列的次序申请和释放资源：进程 P 申请资源 R1 申请资源 R2 释放资源R1 释放资源 R2 2019年 5月 14日进程 Q 申请资源 R2 申请资源 R1 释放资源 R2 释放资源 R1
130.操作系统原理 Principle of Operating System 精品课程例 2-8 若系统中有 m=5 个同类资源被 n=5 个进程共享，当每个进程要求 ki （ i=1 ， 2 ，…， 5 ）个资源时，此处假设 ki=2 。如果为每个进程轮流分配资源，则每个进程在获得一个资源后，系统中的资源都已分配完；于是在第二轮分配时，各进程都由于等待资源而处于阻塞状态，从而导致了死锁。产生死锁现象的原因主要有以下两个方面： ⑴ 系统资源不足。 ⑵ 进程推进的顺序不合理。产生死锁的根本原因就是共享资源。 2019年 5月 14日
131.操作系统原理 Principle of Operating System 精品课程 2 ．死锁的定义一般地，若系统中存在一组并发进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又都在等待该组进程中另一些进程所占用的资源，从而使该组进程都停止往前推进而陷入永久的等待状态。这种情况下，我们就说系统出现了 “ 死锁 ” ，或者说该组进程处于 “死锁”状态。 2019年 5月 14日
132.操作系统原理 Principle of Operating System 精品课程 3 ．死锁的必要条件 1971 年 Coffiman 总结出了系统产生死锁四个必要条件：的互斥条件（ mutual exclusion ）、申请与保持条件（ hold and wait ）、不剥夺条件（ no preemption ）、循环等待条件（ circular wait ）例 2-9 系统中有两类资源 R1 、 R2 和 4 个进程 P1 、 P2 、 P3 、 P4 ，其中每类资源的个数为 2 。资源申请情况为：进程 P3 、 P4 各分配一个 R2 类资源，进程 P1 、 P2 各分配一个 R1 类资源，同时 P1 又申请一个 R2 类资源， P3 又申请一个 R1 类资源。分析在这种情况下是否会发生死锁。 2019年 5月 14日
133.操作系统原理 Principle of Operating System 精品课程 4 ．死锁的判定操作系统中每一时刻的状态可利用进程——资源分配图 PRAG （ Process Resource Allocation Graph ）来描述，如图 2-18 、 2-19 所示，通常用方框代表某类资源，方框中的一个小圆圈代表该类资源中的一个资源，所以方框中的小圆圈的个数表示了系统中该类资源的个数。大圆圈则表示进程。方框结点和进程结点间的有向边代表进程对资源的请求和资源的分配情况，其中资源结点 Rj 到进程结点 Pi 的一条有向边表示一个 Rj 类资源分配给进程 Pi ； Pi 结点到 Rj 结点的有向边则表示进程 Pi 申请一个 Rj 类资源。 2019年 5月 14日
134.操作系统原理 Principle of Operating System 精品课程死锁的判定方法如下： ⑴ 如果不出现任何环，则此时系统内不存在死锁； ⑵ 如果出现了环，且处于此环中的每类资源均只有一个实体时，有环就出现死锁，此时，环是系统存在死锁的充分必要条件： ⑶ 如果系统资源分配图中出现了环，但处于此环中的每类资源的个数不全为 1 ，则环的存在只是产生死锁的必要条件而不是充分条件。 2019年 5月 14日
135.操作系统原理 2.7 Principle of Operating System 死锁问题 2.7.1 死锁的形成与定义 2.7.2 死锁的预防 2.7.3 死锁的避免 2.7.4 死锁的检测与恢复 2.7.5 鸵鸟算法 2.7.6 一种综合的死锁策略 2.7.7 饥饿与活锁 2019年 5月 14日精品课程
136.操作系统原理 Principle of Operating System 精品课程 1 ．预先静态分配策略预先静态分配策略是指进程必须在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的所有资源请求并把资源分配给进程后，该进程才能执行。无疑所有并发执行的进程要求的资源总和不能超过系统拥有的资源总数。采用静态分配后，进程在执行过程中不再申请新的资源，所以不可能出现占有了某些资源后再等待另一些资源的情况，既破坏了死锁的第二个必要条件（申请与保持条件）的出现，而第四个必要条件（循环等待条件）也就自然不会成立，从而预防了死锁的发生。 2019年 5月 14日
137.操作系统原理 Principle of Operating System 精品课程例 2-10 、—个系统包括一个投影仪和一个打印机设备及两个进程 Pi 和 Pj ，两个进程均需要申请投影仪和打印机资源才能起作用。进程按以下的顺序提出资源请求： ⑴ 进程 Pi 请求投影仪； ⑵ 进程 Pj 请求打印机； ⑶ 进程 Pi 请求打印机； ⑷ 进程 Pj 请求投影仪。 2019年 5月 14日
138.操作系统原理 Principle of Operating System 精品课程 2 ．层次分配策略层次分配策略是将系统中的所有资源分成多个层次，每个层次链出一个链链链号： L1 ， L2 ，…， Ln ，每一层中可有几类资源。进程在申请资源时，当得到某一层的一个资源后，它只能再申请较高一层的资源，或者它要想再申请该层中的另一个资源时，必须先释放该层中已拥有的资源；进程要释放资源时，如果要释放某一层的一个资源，必须先释放所拥有的较高层的所有资源。 2019年 5月 14日
139.操作系统原理 Principle of Operating System 精品课程例 2-11 、在例 2-10 中，设层次编号打印机＞投影仪，请求⑴和⑵使得投影仪和打印机分别分配给 Pi 和 Pj ，请求⑶ 满足有效限制，但由于打印机无法分配而使进程 Pi 处于阻塞状态。请求 ⑷ 由于违反了有效限制而会被拒绝。这意味着进程 Pj 若提出这一请求将被终止。则此时进程 Pj 拥有的资源——打印机将被释放，从而唤醒进程 Pi 继续运行，从而防止了死锁的发生。 2019年 5月 14日
140.操作系统原理 Principle of Operating System 精品课程 3 ．剥夺式分配策略剥夺式分配资源策略可阻止产生死锁的第三个必要条件的出现，指当一个进程申请资源得不到满足时，可以从另一个占有该类资源的进程那里去抢夺资源；这意味着，一个进程已获得的资源在运行过程中可被剥夺，从而破坏了“非剥夺式分配”这一必要条件，预防了死锁的发生。 2019年 5月 14日
141.操作系统原理 2.7 Principle of Operating System 死锁问题 2.7.1 死锁的形成与定义 2.7.2 死锁的预防 2.7.3 死锁的避免 2.7.4 死锁的检测与恢复 2.7.5 鸵鸟算法 2.7.6 一种综合的死锁策略 2.7.7 饥饿与活锁 2019年 5月 14日精品课程
142.操作系统原理 Principle of Operating System 精品课程死锁避免允许三个必要条件的发生，但通过明智的选择，确保永远不会到达死锁点。安全状态（ safe ）的概念：如果系统中所有进程能够按照某种次序依次地进行完，则称系统处于安全状态。两种避免死锁的方法： ⑴ 如果一个进程的请求会导致死锁，则不启动该进程—— 进程启动拒绝。 ⑵ 如果一个进程增加资源的请求会导致死锁，则不允许此次资源分配——资源分配拒绝。 2019年 5月 14日
143.操作系统原理 Principle of Operating System 精品课程 1 ．进程启动拒绝如果一个新进程（第 n+1 个进程）的资源需求会导致死锁，则拒绝启动这个新进程。也就是说，只有所有当前进程的最大请求量加上新的进程请求可以满足时，才会启动该进程。 2019年 5月 14日
144.操作系统原理 Principle of Operating System 精品课程假设系统中有 n 个链程、链链 m 类资源，则定义以下数据结构：每种链源链链链数向量：链链链 R= （ R1 ， R2 ，…， Rm ）系链中每链链链链链源尚可供分配的链链链链链链链链源链链数向量：链链链 V= （ V1 ， V2 ，…， Vm ）  c）的  c源 jc（ 1..m  请求矩阵，即最大需求进程 i （ 1..n ）对资 c  c  c  C  矩链链：      进程 i （ 1..n ： 2019年 5月 14日 11 12 1m 21 22 2m   c n1 cn2  a 11 a 12 a a ）已占有 A  21 资22源     a n1 a n 2   c nm   a 1m    a 2 m j （ 1..m ）的矩阵，即分配矩阵     a nm 
145.操作系统原理 Principle of Operating System 从中可得以下关系： ⑴ 对所有的资源 j 有： R j Vj   a ij n i 1 ⑵ 对所有的 i ， j 有： c ij R j ⑶ 对所有的 i ， j 有： a c ij ij 2019年 5月 14日精品课程
146.操作系统原理 Principle of Operating System 精品课程一个死锁避免策略：如果一个新进程（第 n+1 个进程）的资源需求会导致死锁，则拒绝启动这个新进程。仅当对所有的 j 有： n R j c( n 1) j   cij i 1 成立时才启动一个新进程 Pn+1 。 2019年 5月 14日
147.操作系统原理 Principle of Operating System 精品课程 2 ．资源分配拒绝 Dijkstra 提出的银行家算法算法描述如下：假设一个银行家拥有的资金总量为∑，被 n 个客户共享。银行家对客户提出下列约束条件： ⑴ 每个客户必须预先说明自己所要求的最大资金量； ⑵ 每个客户每次提出部分资金的申请并获得分配； ⑶ 如果银行满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还银行。 2019年 5月 14日
148.操作系统原理 Principle of Operating System 精品课程 ⑴ 基本思想银行家算法的基本思想是当一个新的进程进入系统时，它将告诉系统其所需要的每种资源的最大数目，这个数目决不应该超过系统中资源的总数。当一个用户申请一组资源时，系统需判断这些资源的分配是否使系统仍处于安全状态，若是则进行分配，否则它必须等待，直到其它链程链链放足链链链链的链链源。链 2019年 5月 14日
149.操作系统原理 Principle of Operating System 精品课程 ⑵ 使用的数据结构每种资源总数向量 R 、未分配给进程的每种资源总数向量 V 、最大需求矩阵 C 和分配矩阵 A 。 ⑶ 银行家算法进程 Pi 发出对第 j 类资源的请求（ Requesti j ）时，系统将执行如下的资源分配算法： ① 申请量超过最大需求时出错；否则转步骤②； 2019年 5月 14日
150.操作系统原理 Principle of Operating System 精品课程 ② 申请量超过目前系统拥有的可分配量时则阻塞该进程，否则转步骤③； ③ 系统对进程 Pi 发出的资源请求做试探性的分配，相应的数据结构作如下的修改，然后转步骤④； aij=aij+Requestij; vj= vj-Requestij; ④ 做安全性检查，如果安全则承认试分配，否则撤销试分配，相应的数据结构作如下的修改，同时阻塞进程 Pi 。 aij=aij-Requestij; 2019年 5月 14日 vj= vj+Requestij;
151.操作系统原理 Principle of Operating System 精品课程安全性检查算法： ① 初始化 Finish[1..n]=false; ② 寻找满足以下条件的进程 Pi ： Finish[i]==false 且 Vj≥cij-aij ；如果不存在，则转步骤④； ③Finish[i]=true;Vj=Vj+aij; 转步骤②； ④ 如果对所有的 i 有 Finish[i]=true ，则系统处于安全状态，否则处于不安全状态。 2019年 5月 14日
152.操作系统原理 Principle of Operating System 精品课程例 2-12 设系统中有五个进程 {P0,P1,P2,P3,P4} ，三类资源 {A,B,C}, 对应的每类资源总数为 :R=(5,10,7) ，在时刻 T0 的系统状态如下： C= 2 0 2 3 2019年 5月 14日 5 7 3 3 2 9 2 A= 2 2 4 3 0 0 1 0 1 0 0 2 0 3 2 2 1 0 2
153.操作系统原理 Principle of Operating System 精品课程（ 1 ）在 T1 时刻，进程 P1 申请资源 (0,1,2) （ 2 ）在 T2 时刻，进程 P4 请求资源 (3,3,0) （ 3 ）在 T3 时刻，进程 P0 的资源请求 (2,0,0) 2019年 5月 14日
154.操作系统原理 2.7 Principle of Operating System 死锁问题 2.7.1 死锁的形成与定义 2.7.2 死锁的预防 2.7.3 死锁的避免 2.7.4 死锁的检测与恢复 2.7.5 鸵鸟算法 2.7.6 一种综合的死锁策略 2.7.7 饥饿与活锁 2019年 5月 14日精品课程
155.操作系统原理 Principle of Operating System 精品课程 1 ．死锁的检测最常用的检测死锁的方法是对进程资源分配图（ PRAG ）链行化链链链链。死锁定理当且仅当系统某状态 S 所对应的资源分配图是不可完全化简的，则称 S 是死锁状态，而不可化简的那些进程即是死锁进程。反之，若状态 S 对应的资源分配图是可完全化简的，则状态 S 是安全的。 2019年 5月 14日
156.操作系统原理 Principle of Operating System 资源分配图的一个例子 R1 R2 ．． P1 P2 ．． 2019年 5月 14日 P3 R3 精品课程
157.操作系统原理 Principle of Operating System 资源分配图的另一个例子 R1 P2 2019年 5月 14日 P1 P3 R2 P4 精品课程
158.操作系统原理 Principle of Operating System 精品课程 ⑴ 使用银行家算法检测  定义系统中每类资源尚可供分配的资源总数向量 V  将最大需求矩阵 C 中为 0 的行向量所对应的进程 Pi 记入集合 L ， L=L∪Pi ；  从进程集合中查找 Requestij≤V 的进程，做如下处理：化简进程资源分配图，并释放资源，将该进程并入集合 L ； 2019年 5月 14日
159.操作系统原理 Principle of Operating System 精品课程  重复③，若没有再满足条件的进程，而集合 L 中没有包括所有进程，则表明目前的系统状态对应的进程资源分配图是不可完全化简的，因此，该状态将发生死锁；否则，状态是安全的。 ⑵ 传递闭包算法首先把进程使用和等待资源的情况用一个状态矩阵 S 来表示，然后用 warshall 的传递闭包算法来检测系统是否有死锁发生。 2019年 5月 14日
160.操作系统原理 Principle of Operating System 2 ．死锁的恢复 撤销进程法 剥夺资源法 进程回退法 2019年 5月 14日精品课程
161.操作系统原理 2.7 Principle of Operating System 死锁问题 2.7.1 死锁的形成与定义 2.7.2 死锁的预防 2.7.3 死锁的避免 2.7.4 死锁的检测与恢复 2.7.5 鸵鸟算法 2.7.6 一种综合的死锁策略 2.7.7 饥饿与活锁 2019年 5月 14日精品课程
162.操作系统原理 Principle of Operating System 精品课程 “ 鸵鸟算法” 是模仿鸵鸟遇到危险时将头埋在沙子里的传说而得名，就是当死锁发生时，假装什么也没有发生，也就是说，象鸵鸟一样对死锁视而不见。而当死锁影响到系统的正常运行时，就手工干预——重新启动。 2019年 5月 14日
163.操作系统原理 2.7 Principle of Operating System 死锁问题 2.7.1 死锁的形成与定义 2.7.2 死锁的预防 2.7.3 死锁的避免 2.7.4 死锁的检测与恢复 2.7.5 鸵鸟算法 2.7.6 一种综合的死锁策略 2.7.7 饥饿与活锁 2019年 5月 14日精品课程
164.操作系统原理 Principle of Operating System 精品课程 HOWA73 提出了一种方法： ⑴ 把资源分成几种不同类型； ⑵ 为了预防在资源类之间由于循环等待产生死锁，可使用前面定义的链次分配策略；链链链链链链 ⑶ 在一个资源类中，使用该类资源最适合的算法。 2019年 5月 14日
165.操作系统原理 2.7 Principle of Operating System 死锁问题 2.7.1 死锁的形成与定义 2.7.2 死锁的预防 2.7.3 死锁的避免 2.7.4 死锁的检测与恢复 2.7.5 鸵鸟算法 2.7.6 一种综合的死锁策略 2.7.7 饥饿与活锁 2019年 5月 14日精品课程
166.操作系统原理 Principle of Operating System 精品课程当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿（ starvation ）。当饥饿到一定程度的进程所赋予的任务及时完成也不再具有实际意义时称该进程被饿死（ starve to death ）。在忙式等待条件下发生的饥饿，称为活锁。 2019年 5月 14日
167.操作系统原理 Principle of Operating System 谢谢 ! 2019年 5月 14日兰州理工大学计算机与通信学院精品课程