《操作系统设计与实现》第2章进程.

《操作系统设计与实现》第2章进程

第2章进程 2.1 进程介绍 2.2 进程间通信 2.3 经典IPC问题 2.4 进程调度

2.1.1 进程模型历史发展具体发展概述进程概念从无到有，从简单到复杂 “进程”产生的根本原因：OS更好的管理CPU资源
进程管理从静态到动态、从单一到多样具体发展概述第一代计算机：真空管和插板（没有进程概念）第二代计算机：晶体管和批处理系统（静态单一进程）第三代计算机：集成电路和多道程序（静态多道进程）近代发展：分时、分布式、网络OS（动态多道进程）

2.1.1 进程模型多道程序设计与进程管理计算机中程序运行模式的发展历程程序运行模式的特征顺序执行模式：单道程序独占CPU和其他资源
多道程序设计：并发模式下的OS设计与实现程序运行模式的特征顺序执行模式顺序性、封闭性、独占性、确定性（结果可再现性）并发执行模式并发性、间断性、共享性、不确定性、独立性和制约性问题1：并发与并行的区别是什么？问题2：如何计算并发环境下的计算机工作效率？

计算机用来干什么? 计算机是用来帮助我们解决问题的机器! int main(int argc, char* argv[]) {
int i , to, sum = 0; to = atoi(argv[1]); for(i=1; i<=to; i++) sum = sum + i; } printf(“%d”, sum);

执行程序是计算机的基本任务怎么样让程序执行起来? 源代码代码段： mov ax, [100] mov bx, [104]
int main(int argc, char* argv[]) { int i , to, sum = 0; to = atoi(argv[1]); for(i=1; i<=to; i++) sum = sum + i; } printf(“%d”, sum); 源代码代码段： mov ax, [100] mov bx, [104] add ax, bx …… 可执行程序 (在磁盘上，没有输出结果) 程序在内存中运行代码段数据段栈(参数等) 寄存器组处理器

程序执行的细节代码段： PC mov ax, [100] IR ax mov ax, [100] mov bx, [104]
add ax, bx …… 100: //sum 104: // i PC mov ax, [100] IR ax

程序执行的细节代码段： mov bx, [104] IR PC ax bx 1 mov ax, [100] mov bx, [104]
add ax, bx …… 100: //sum 104: // i mov bx, [104] IR PC ax bx 1

程序执行的细节程序执行的关键在于PC的设定! 代码段： PC add ax, bx IR 1 ax bx 1 mov ax, [100]
mov bx, [104] add ax, bx …… 100: //sum 104: // i PC add ax, bx IR 1 ax bx 1 程序执行的关键在于PC的设定!

计算机中只有一个程序在执行吗? 5.7105 : 1 这是一个应不应该有的问题。 0.015/107 0.859/103
fprintf用一条其他计算语句代替 int main(int argc, char* argv[]) { int i , to, *fp, sum = 0; to = atoi(argv[1]); for(i=1; i<=to; i++) sum = sum + i; fprintf(fp,“%d”, sum); } 0.015/107 有fprintf 0.859/103 5.7105 : 1

计算机系统的基本特征 CPU的速度相比其他设备要快的多! sum 一个直观想法就是将CPU让出来 sum
(等待文件输出) 一个直观想法就是将CPU让出来 sum (等待文件输出) 其他程序 (等待) 计算机同时在执行多个程序(交替执行)!

一个程序 vs. 多个程序 A B A B 一次一个程序：多个程序：一次一个程序多个程序 CPU利用率 40/80=50%
DEV1 CPU DEV2 CPU A 一次一个程序： 10 15 20 30 40 DEV 1 CPU DEV2 CPU DEV2 B 50 60 65 70 80 A CPU DEV1 CPU DEV2 CPU 多个程序： 10 15 20 25 30 35 40 45 B DEV1 CPU DEV2 CPU DEV2 一次一个程序多个程序 CPU利用率 40/80=50% 40/45=89% DEV1利用率 15/80=18.75% 15/45=33% DEV2利用率 25/80=31.25% 25/45=56%

2.1.1 进程模型并行与并发的概念差别并行（Parallel）并发（Concurrency）同一时刻，两个事物均处于活动状态
示例：CPU中的超流水线设计和超标量设计并发（Concurrency）宏观上存在并行特征，微观上存在顺序性同一时刻，只有一个事物处于活动状态示例：分时操作系统中多个程序的同时运行

2.1.1 进程模型并发所带来的设计难题共享性带来的问题：如何调度或分配资源？间断性和不确定性带来的问题：如何保证互斥？
最大限度的保证系统运行效率：谁首先获得资源？最大限度的保证系统运行安全：死锁情况的预防间断性和不确定性带来的问题：如何保证互斥？互斥问题示例：见下页图经典IPC问题：进程管理的重点间断性和独立性带来的问题：如何调度和保护？每个程序运行时都感觉不到间断：上下文切换复杂应用带来的问题：如何进行通信？多个程序间可动态交换信息：进程通信机制

2.1.1 进程模型并发所带来的设计难题 Get、Copy、Put为三个并发的程序 F、G为保存多条数据的缓冲区，S、T为临时缓冲区
三个程序顺序执行，可将F的值经过S、T保存到G中正常情况下，不存在任何问题但是程序运行顺序发生变化时，结果可能出错

2.1.1 进程模型并发所带来的设计难题 F S T G 初始状态 3，4，5 2 1，2 分析程序运行顺 G、C、P 4，5
1，2，3 正确 G、P、C 1，2，2 错误 C、P、G C、G、P P、C、G P、G、C

并发并发：一个CPU上交替的“同时”执行多个程序并发是指同时出发，交替执行(和并行不同) 时间切换 PC PC 程序1 程序2
mov ax, [100] mov bx, [104] add ax, bx …… 程序1 mov ax, 10 mov bx, 10 程序2 PC PC

并发需要切换执行现场! 切换 PC PC 切换 PC 程序1 ax 1 bx PC 程序2 ax 10 bx PC 内存
mov ax, [100] mov bx, [104] add ax, bx …… 程序1 mov ax, 10 mov bx, 10 程序2 切换 PC PC 程序1 程序1 程序1 程序2 程序2 切换 PC 程序1 ax 1 bx PC 程序2 ax 10 bx PC CPU 物理CPU 内存

为什么引入进程? 程序2 ax 10 bx PC 程序的概念不够用了! 在执行过程中才能知道
放在磁盘上的程序怎么可能知道现场呢? 程序2 ax 10 bx PC 程序的概念不够用了! 磁盘上的程序怎么可能知道传递的参数呢? 磁盘上的程序怎么可能知道……? 在执行过程中才能知道需要一个能描述执行过程中的程序的概念。进程应运而生！当一个非常重要的事物没法用现有的概念清晰表述时，就会产生新的概念

2.1.1 进程模型何谓进程（Process）进程的概念是60年代初首先由麻省理工学院的MULTICS系统和IBM公司的CTSS/360系统引入的。描述性定义：计算机上所有可运行的软件，通常包括操作系统、被组织成若干顺序进程，这种运行的过程简称进程（processes）一个进程就是一个正在执行的程序，包括程序计数器、寄存器和变量的当前值。

2.1.1 进程模型对每一个进程而言，都有独立的计数器和CPU时间操作系统维护一个程序计数器，在进程间切换
操作系统实现分时，任意时刻只有一个进程运行

2.1.1 进程模型进程与程序有何差别？做饭进程洗衣进程程序阅读菜谱阅读洗衣机手册程序输入准备原料准备衣服、洗衣粉输入
分时切换运行烹制菜肴运行设定参数，洗衣服饭菜输出干净衣服输出做饭进程洗衣进程

2.1.1 进程模型进程与程序有何差别？程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序是静态的，进程是动态的。程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。

2.1.1 进程模型进程与程序有何差别？进程更能真实地描述并发，而程序不能；进程是有程序和数据、进程控制块三部分组成的；
进程具有创建其他进程的功能，而程序没有；同一程序同时运行于若干数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程。

2.1.1 进程模型进程的核心思想进程是某种类型的一个活动，它有程序、输入、输出和状态。在分时操作系统中，单个处理器被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。

2.1.2 进程的创建与终止进程创建的四个主要原因（page 41）举例系统初始化正在运行的一个进程执行了创建进程的系统调用
用户请求创建一个进程批处理作业的初始化举例 UNIX：fork、execve； Windows：CreateProcess；新进程都是由一个已存在的进程执行一个用于进程创建的系统调用而创建的；

2.1.2 进程的创建与终止进程终止的四个主要原因（page 42）正常退出（自愿）出错退出（自愿）严重错误（非自愿）
Exit（UNIX）、ExitProcess（Windows）出错退出（自愿）严重错误（非自愿）被其他进程杀死（非自愿） Kill （UNIX）、TerminateProcess （Windows）

阻塞态：等待外部事件发生，无法占用CPU 就绪态：可运行，但其他进程正在占用CPU，所有被暂时挂起
2.1.5 进程的状态进程状态进程的三种状态运行态：正在占用CPU运行程序阻塞态：等待外部事件发生，无法占用CPU 就绪态：可运行，但其他进程正在占用CPU，所有被暂时挂起

停止其他进程运行后，运行该进程占用CPU
2.1.5 进程的状态进程状态运行态变为就绪态强制终止某进程的运行（系统原因）运行态变为阻塞态运行进程等待外部事件发生（自身原因）阻塞态变为就绪态外部事件已经发生，可准备运行就绪态变为运行态停止其他进程运行后，运行该进程占用CPU

2.1.5 进程的状态进程状态转换示意图运行态阻塞态就绪态进程状态 OS决定由哪个进程占用CPU，进程调度状态转换：
进程等待外部事件，阻塞 OS决定由哪个进程占用CPU，进程调度阻塞态就绪态进程就绪，可以运行

2.1.5 进程的状态问题1：为什么不能从阻塞态变为运行态呢？问题2：为什么不能从就绪态变为阻塞态呢？答案：
三种状态的变换体现了OS的资源管理作用进程的核心思想在于运行——CPU资源的分配，进程调度——公平和效率

2.1.5 进程的实现单个进程的管理多个进程的管理进程之间的通信进程的创建、删除：静态与动态概念的差别。
进程管理单个进程的管理进程的创建、删除：静态与动态概念的差别。多个进程的管理树状进程集合：父进程和子进程进程的调度：保持CPU效率的关键进程之间的通信最简单：两个进程之间如何传递信息？中级：如何保持进程之间的互斥？高级：如何维系进程之间的依赖关系？

（1）单个进程的管理管理的内容实现的方式创建数据结构、填充各种必要信息。维护进程的状态变化。保持进程运行期间的数据完整和程序有效。
进程管理管理的内容创建数据结构、填充各种必要信息。维护进程的状态变化。保持进程运行期间的数据完整和程序有效。退出进程，清空历史信息、释放各种资源。实现的方式 Page 44 （5——10分钟）

（2）多个进程的管理管理的内容父进程与子进程的概念——树状结构（UNIX）。所有进程地位相同，句柄（WINDOWS）
进程管理管理的内容父进程与子进程的概念——树状结构（UNIX）。所有进程地位相同，句柄（WINDOWS）进程与线程的概念——用户态与核心态的差别。 CPU资源的分配：进程调度数据的共享与传递进程通信

2.1.7 线程进程是操作系统中进行保护和资源分配的基本单位。它具有：
一个虚拟地址空间，用来容纳进程的映像；对处理器、其他(通信的)进程、文件和I/O资源等的存取保护机制。线程是操作系统进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。线程是进程的组成部分，每个进程内允许包含多个并发执行的实体（控制流），这就是多线程。

2.1.7 线程进程与线程的差别-1 进程与线程的属性差别进程：有独立、完整的数据结构，调度、运行过程中系统开销较大
线程：从属于某个进程，与进程共享地址空间，只需保存状态、堆栈、寄存器进程和线程本质差别：多个进程的地址空间相互独立，多个线程却可以公用地址空间引入线程概念的优点以及实现过程考虑进程模型与线程模型：进程模型是单一、顺序的编程模式；线程模型则是多道、并行线程模型的实现：早期OS实现了“内核进程＋用户线程”，现代OS实现“内核线程机制”

2.1.7 线程进程与线程的差别-1 单线程改变为多线程时需要考虑哪些问题？
全局变量：多线程模型对全局变量的访问存在互斥同步问题，需认真解决库函数调用：并行调用库函数时可能发生错误，需要仔细分析库函数特性信号传递：OS内核如何将信号直接传递给某个线程？堆栈管理：每个线程都有自己的堆栈，多线程模型需要调整堆栈管理策略实现过程考虑：OS支持“内核管理线程”的方式，提倡更高并行程度的程序设计理念

2.2 进程间通信进程间的关系进程间通信需要考虑三方面的内容：完全无关（异步）：不同进程间无任何关联
2.2 进程间通信进程间的关系完全无关（异步）：不同进程间无任何关联使用共享数据（互斥）：应有效保护各个进程的正确运行存在先后顺序（同步）：应保证进程运行顺序的正确进程间通信需要考虑三方面的内容：一个进程如何向另一个进程传送信息; 必须要保证两个或多个进程在涉及临界区活动时不会彼此影响; 当存在依赖关系时确定适当的次序。

2.2.1 竞争条件概念的引入（竞争条件）两个或者多个进程读写共享数据，而运行结果取决于进程运行时的精确时序，则这种情况称之为竞争条件
Spooler目录问题（互斥）概念的引入（竞争条件）两个或者多个进程读写共享数据，而运行结果取决于进程运行时的精确时序，则这种情况称之为竞争条件当竞争条件存在时，进程处理结果可能失效甚至发生错误

2.2.1 竞争条件 ….. abc.doc xyz.doc 123.doc 4 5 6 7 Out=4 In=7 Spooler
see page 48 进程A读到In的值为7, 将它存在一个局部变量Next-free-slot中; 时钟中断发生，进程A中止，切换到进程B运行; 进程B也读In, 同样得到7, 将要打印的文件名存入7号槽，并将In的值更新为8, 进程B会认为它的工作结束；进程A接着从上次中止的地方再次运行，检查变量next-free-slot，发现其值为7，于是将打印文件名存入7号槽，并将In的值更新为8；进程B永远不会打印。 ….. abc.doc xyz.doc 123.doc 4 5 6 7 Out=4 In=7 Spooler Process A Process B

进程A读到In的值为7, 将它存在一个局部变量Next-free-slot中; 时钟中断发生，进程A中止，切换到进程B运行; 进程B也读In, 同样得到7, 将要打印的文件名存入7号槽，并将In的值更新为8, 进程B会认为它的工作结束；进程A接着从上次中止的地方再次运行，检查变量next-free-slot，发现其值为7，于是将打印文件名存入7号槽，并将In的值更新为8；进程B永远不会打印。 ….. abc.doc xyz.doc 123.doc 4 5 6 7 Process A Out=4 In=7 Spooler Process B

进程A读到In的值为7, 将它存在一个局部变量Next-free-slot中; 时钟中断发生，进程A中止，切换到进程B运行; 进程B也读In, 同样得到7, 将要打印的文件名存入7号槽，并将In的值更新为8, 进程B会认为它的工作结束；进程A接着从上次中止的地方再次运行，检查变量next-free-slot，发现其值为7，于是将打印文件名存入7号槽，并将In的值更新为8；进程B永远不会打印。 ….. abc.doc xyz.doc 123.doc 4 5 6 7 Process B Out=4 In=7 Spooler Process A

进程A读到In的值为7, 将它存在一个局部变量Next-free-slot中; 时钟中断发生，进程A中止，切换到进程B运行; 进程B也读In, 同样得到7, 将要打印的文件名存入7号槽，并将In的值更新为8, 进程B会认为它的工作结束；进程A接着从上次中止的地方再次运行，检查变量next-free-slot，发现其值为7，于是将打印文件名存入7号槽，并将In的值更新为8；进程B永远不会打印。 ….. abc.doc xyz.doc 123.doc 4 5 6 7 Process B Out=4 In=7 Spooler Process A new.doc In=8

2.2.1 竞争条件 ….. abc.doc xyz.doc 123.doc 4 5 6 7 Out=4 Spooler cover.pdf
进程A读到In的值为7, 将它存在一个局部变量Next-free-slot中; 时钟中断发生，进程A中止，切换到进程B运行; 进程B也读In, 同样得到7, 将要打印的文件名存入7号槽，并将In的值更新为8, 进程B会认为它的工作结束；进程A接着从上次中止的地方再次运行，检查变量next-free-slot，发现其值为7，于是将打印文件名存入7号槽，并将In的值更新为8；进程B永远不会打印。 ….. abc.doc xyz.doc 123.doc 4 5 6 7 Out=4 Spooler Process A cover.pdf In=8 Process B

“司机－售票员”问题（同步）问题分析两个独立进程如何保持同步？现实应用中存在大量的类似实例司机进程 While(True) {
启动公车；驾驶公车；停止公车； } 售票员进程 While(True) { 关车门；卖车票；开车门； } 正确运行过程 While(True) { （司机）启动公车；（售票员）关车门；（司机）驾驶公车；（售票员）卖车票（司机）停止公车；（售票员）开车门； } 问题分析两个独立进程如何保持同步？现实应用中存在大量的类似实例

2.2.2 临界区临界区：假如两个或更多的进程需要访问一个不可共享的资源，在执行过程中，每个进程都发送或接收数据。我们把这类资源称作临界资源，使用临界资源的那一部分程序称作成程序的临界区。互斥：以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。(避免多个进程访问同一个临界区)

怎么解决？如何保证防止竞争条件，同时保证使用共享数据的并发进程能够正确和高效地进行操作。需要满足以下四个条件：任何两个进程不能同时处于临界区不应对CPU的速度和数目做任何假设临界区外的进程不得阻塞其他进程不得使进程在临界区外无休止地等待

使用临界区实现的互斥进程A于T1时刻进入临界区进程B于T2时刻试图进入临界区，被阻塞进程A于T3时刻离开临界区，进程B立即进入临界区

经典IPC机制 2.2.3 忙等待模型（只解决互斥问题） 2.2.4 睡眠和唤醒模型（互斥与同步） 2.2.5 信号量 2.2.6 互斥
进程进入临界区时进行严格的检查 2.2.4 睡眠和唤醒模型（互斥与同步）通过改变进程的状态来实现互斥和同步 2.2.5 信号量 P（Up，Signal）、V（down，Wait）原子性操作 2.2.6 互斥 2.2.7 管程基于编译器的程序控制 2.2.8 消息传递模型以公共的通信机制来控制进程状态变化，实现同步和互斥

2.2.3 忙等待形式的互斥模型思想四种实现互斥的方案：设定一个变量，标识临界区的状态
互斥进程均检查这个变量，只有当其满足条件时方可进入临界区四种实现互斥的方案：关闭中断（Disabling Interrupts）锁变量（Lock Variables）严格交替法（Strict Alternation） Peterson解决方案（Peterson's Solution）在这些方案中，当一个进程在临界区中更新共享内存时，其他进程将不会进入其临界区，也不会带来任何麻烦。

关闭中断（Disabling Interrupts）
Close_INT; Critical_region(); Open_INT; 进程B Close_INT; Critical_region(); Open_INT; 具体实现：每个进程进入临界区后先关中断，在离开之前再开中断。缺点：把关中断的权利交给了用户进程是不明智的。当一个进程关中断之后不再打开中断，系统可能会因此终止。如系统有多个共享内存的处理器，则关中断仅仅对执行指令的CPU有效，其他CPU仍将继续运行，并可以访问共享内存

锁变量（Lock Variables）对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开的，则该进程进入; 如果关闭着的，则该进程不能进入。进程进入临界区后锁上这把锁，当它出来后再打开这把锁。但依然存在矛盾，跟Spooler目录一样。 Process 1 临界区锁 Process 2

但依然存在矛盾，跟Spooler目录一样。
锁变量（Lock Variables）对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开的，则该进程进入; 如果关闭着的，则该进程不能进入。进程进入临界区后锁上这把锁，当它出来后再打开这把锁。但依然存在矛盾，跟Spooler目录一样。 Process 1 临界区临界区锁 1 Process 2

锁变量（Lock Variables）对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开的，则该进程进入; 如果关闭着的，则该进程不能进入。进程进入临界区后锁上这把锁，当它出来后再打开这把锁。但依然存在矛盾，跟Spooler目录一样。 Process 1 临界区 Process 1 锁 Process 2

锁变量（Lock Variables）对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开的，则该进程进入; 如果关闭着的，则该进程不能进入。进程进入临界区后锁上这把锁，当它出来后再打开这把锁。但依然存在矛盾，跟Spooler目录一样。 Process 1 临界区锁 Process 2

严格交替法（Strict Alternation）
严格轮换法是指几个进程轮换进入临界区，且顺序不能紊乱。初始值：turn=0 While ( TRUE ) { while ( turn !=0 ); /*wait*/ critical_region ( ) ; turn=1; noncritical_region ( ) ; } While ( TRUE ) { while ( turn !=1 ); /*wait*/ critical_region ( ) ; turn=0; noncritical_region ( ) ; } 忙等待：进程不断地读turn的值，并没有做任何有意义的事，浪费了CPU的资源。

这种情况违反了条件3：临界区外的进程不得阻塞其他进程！
违反条件3 异常: （此时虽然不会竞争，但浪费了资源）如果进程A的非临界区很快能执行完，而进程B的非临界区却非常慢，则会： turn=1 turn=0 while ( turn !=0 ); A B t 这种情况违反了条件3：临界区外的进程不得阻塞其他进程！

Peterson解决方案（Peterson's Solution）
荷兰数学家T. Dekker将轮换法和锁变量的思想相结合，提出了一个不需要严格轮换的软件互斥解法。在1981年，G. L Peterson提出了一种简单的多的互斥算法。这使得Dekker解决方案不在有任何意义。该算法由两个 ANSI C写的过程组成。 ANSI C要求为所定义和使用的所有函数提供函数原型，为了PPT能放下，在后面例子将不给出函数原型。

两个进程的Peterson算法初始值为false Boolean flag[2]: 数组元素 int turn; Void P0 ( )
{ while(true) flag[0]= true; turn=0; while(flag[1]&&turn==0); /*wait*/ /*critical area*/ flag[0]=false; /*noncritical area*/ } flag [0] flag [1] 初始值为false Void P1 ( ) { while (true) flag[1]= true; turn=1; while(flag[0]&&turn==1); /*wait*/ /*critical area*/ flag[1]=false; /*noncritical area*/ }

硬件手段 ( TSL----test and set lock )
指令：TSL RX, LOCK //测试并上锁工作原理如下:它将一个存储器字读到寄存器中，然后在该内存地址上存一个非零值。读数和写数操作保证是不可分割的（原子操作），即该指令结束之前其他处理机均不允许访问该存储器字。原子操作：这种操作在运行的过程中，是不能也不允许被打断的，它是操作的最底层的部分，是不可分割的，称其为原子操作。

Enter_region: tsl register , lock //copy LOCK to register and set LOCK to 1 cmp register, # //was LOCK zero? jne enter_region //if it was non zero, LOCK was set, so loop ret //return to caller; critical region entered Leave_region: move lock, # //store a 0 in LOCK ret //return to caller 进程在进入临界区之前先调用enter_region。这将导致忙等待，直到锁空闲为止。进程从临界区返回时它调用leave_region，把锁置为0

硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现"让权等待" 可能"饥饿"：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上可能死锁

2.2.4 睡眠和唤醒对于Peterson和TSL问题，都能够很好地实现互斥，但也都同时存在问题：解决的途径就是引入新的概念：睡眠唤醒
忙等待，浪费CPU的资源。进程的优先级有差别：当有两个进程，A、B， A的优先级高，处于就绪状态，而此时，B在临界区内，由于优先级低，故无法被调度，也就无法离开临界区，那A就只能够在临界区外等待。（优先级反转问题 priority inversion problem）解决的途径就是引入新的概念：睡眠唤醒

2.2.4 睡眠和唤醒模型思想 OS提供系统调用原语（Atomic Action），改变进程状态
无法进入临界区的进程转为阻塞态，条件满足则被唤醒可有效克服忙等待造成的资源浪费更重要的优点：可同时实现同步与互斥操作系统原语设计 Sleep()：调用该原语的进程将变为阻塞态，即挂起 Wakeup(ID)：该原语将唤醒ID标识的进程原语使用思想进入临界区前检查竞争条件，如不满足则睡眠离开临界区后唤醒互斥进程

2.2.4 睡眠和唤醒阅读P53生产者-消费者问题（有界缓冲区问题）问题描述：一个有限空间的共享缓冲区，负责存放货物
生产者向缓冲区中放物品，缓冲区满则不能放消费者从缓冲区中拿物品，缓冲区空则不能拿

2.2.4 睡眠和唤醒解决生产者-消费者问题＃define N 100 int lock ＝ 0 int count = 0
Producer进程 While(TRUE) { Produce-Item(); If(count == N) sleep(); Enter-item(); count = count + 1 if(count == 1) wakeup(consumer); } Comsumer进程 While(TRUE) { if(count == 0) sleep(); Remove-Item(); count = count - 1 if(count == N-1) wakeup(producer); Consume-item(); } 参考P53

2.2.4 睡眠和唤醒潜在的竞争条件 Comsumer进程 … … … … … ＃define N 100 if(count == 0)
int lock ＝ 0 int count = 0 考虑另外一种引起竞争条件的情况？参见P54 发生进程调度，导致C进程并未进行Sleep Producer进程 … … … … wakeup(consumer); P进程认为C在睡眠，试图唤醒C，wakeup信号丢失 Comsumer进程 sleep(); 由于错过了Wakeup信号，C进入了睡眠状态 Producer进程 … … … … P进程一直运行下去，填满缓冲区后也睡眠了 Producer进程 sleep()；

2.2.4 睡眠和唤醒产生原因：发给一个未睡眠进程的唤醒信号被丢失了快速弥补方法：增加唤醒等待位，以解决互斥问题方法分析
count的访问未加限制，形成竞争条件快速弥补方法：增加唤醒等待位，以解决互斥问题当向一个清醒的进程发送一个唤醒信号时，将该位置位。随后，当进程要睡眠时，如果唤醒位为1，则将该位置0，而进程仍然保持清醒方法分析较忙等待更进一步，有效节省CPU资源存在竞争条件，需要额外处理当互斥进程数增加时，方法有效性下降

2.2.5 信号量基本概念核心思想 E. W. Dijkstra于1965年提出Probern和Verhogen原语
信号量（semaphore）：表示累积的睡眠或者唤醒操作 0表示没有积累下来唤醒操作 >0表示有一个或者多个被积累下来的唤醒操作 Down与Up原语（P/V、S/W原语）-- P( )操作, V( )操作核心思想引入新的数据结构定义：信号量利用信号量，提供更为复杂的原语级操作从根本上解决“潜在竞争条件”问题可以方便的推广到一般情况，适用于多进程的互斥与同步

2.2.5 信号量信号量与Down/Up原语对于一种互斥或者同步关系，用一个整型变量来描述
当信号量大于0时，说明“环境安全”，可继续运行当信号量小于0时，说明“互斥等待”，只能阻塞推广到一般情况，信号量可解决复杂的同步互斥问题 struct semaphore { int value; //记录资源的个数 PCB *queue； //记录阻塞在该信号量上的进程的队列 } Down(semaphore s); //消费资源 Up(semaphore s); //产生资源 Down(s) { s.value--; if(s.value < 0) sleep(s.queue); } Up(s) { s.value++; if(s <= 0) wakeup(s.queue); }

2.2.5 信号量分析生产者-消费者问题互斥关系分析任何时刻，只能有一个进程在缓冲区中操作
引入互斥信号量（二进制信号量，binary semaphores）信号量为0，表明已有进程进入临界区；同步关系分析对于“生产者”而言，缓冲区满则应等待引入同步信号量“empty”，为0表示缓冲区满对于“消费者”而言，缓冲区空则应等待引入同步信号量“full”，为0表示缓冲区空

2.2.5 信号量解决生产者-消费者问题 Producer进程 int item; While(TRUE) {
Produce-Item(&item); down(&empty); down(&mutex); Enter-item(item); up(&mutex); up(&full); } Comsumer进程 int item; While(TRUE) { down(&full); down(&mutex); Remove-item(&item) up(&mutex); up(&empty); Consume-item(item); } ＃define N 100 typedef int semph semph mutex = 1; semph empty = N; semph full = 0; 思考1：mutex和empty两个信号量之间有什么区别吗？思考2：多信号量的操作顺序有要求吗？-死锁的产生

2.2.5 信号量最基本互斥机制的实现 int mutex = 1 进程A while(TRUE) {
nocritical_region(); Down(mutex); critical_region(); Up(mutex); } 进程B while(TRUE) { nocritical_region(); Down(mutex); critical_region(); Up(mutex); }

2.2.5 信号量同步与互斥问题互斥信号量同步信号量概念差别——互斥与同步（并发的两个要素） mutex：防止多个进程同时进入临界区
empty和full：保证事件发生的顺序缓冲区满时，Producer停止运行缓冲区空时，Consumer停止运行概念差别——互斥与同步（并发的两个要素）互斥：保护临界区，防止多个进程同时进入同步：保证进程运行的顺序合理

2.2.6 互斥如果不需要信号量的计数能力，可以使用信号量的简化版本，称为互斥。互斥仅仅适用于管理共享资源或一小段代码。
互斥处于两种状态：解锁和加锁。当一个进程需要进入临界区，调用mutex_lock；如果互斥是解锁的，则调用成功，并进入临界区。如果互斥已经加锁，调用者阻塞，直到临界区中的进程完成操作并调用mutex_unlock。

2.2.6 互斥注意与TSL的区别！

2.2.7 管程操作系统设计中引入了信号量以后，互斥实现起来似乎很容易，果真是这样吗？答案是否定的！优点分析
进程通信操作系统设计中引入了信号量以后，互斥实现起来似乎很容易，果真是这样吗？答案是否定的！优点分析彻底解决忙等待弊端，提高OS的管理层次可实现复杂的同步与互斥情况，特别是多进程间通信可最大限度的保证并发效率缺点分析实现机制复杂，互斥和同步关系分析困难存在死锁陷阱（page 57），需要谨慎小心严密的设计在分布式系统中，多个CPU、局域网，上述原语将失效信号量太低级，而管程只能在少数几个编程语言中使用

2.2.7 管程一种高级的同步原语——管程（monitor）死锁的危险核心思想方法分析
一旦信号量的处理代码发生错误，则会引起进程死锁（page57）核心思想实现一种包含过程、变量、数据结构的独立模块任何时刻，只能有一个活跃进程在管程内由编译器提供支持，有效地实现进程间的互斥方法分析优点：实现了进程互斥的自动化

2.2.7 管程 Page 57、 58、 59 管程和信号量的缺点：使用管程，需要一种带有管程的语言，在少数几种编程语言以外无法使用。
对于一个具有多个CPU、各CPU拥有自己的私有内存、由一个局域网相连的分布式系统，这些原语（信号量）将失效。因此，还需要其他方案！！！

2.2.8 消息传递模型思想设计要点提供Send和Receive原语，用来传递消息进程通过发送和接收消息来实现互斥与同步
进程通信模型思想提供Send和Receive原语，用来传递消息进程通过发送和接收消息来实现互斥与同步重要的优点：不仅实现了同步，还能够传送大容量信息设计要点如何保证消息传递中不丢失？（ACK机制-acknowledgement message - TCP）如何命名进程，使得其地址唯一(身份认证-authentication) 如何规范消息格式，降低处理时间(性能、消息的大小）

2.2.8 消息传递解决生产者-消费者问题＃define N 100 Producer进程 int item; message m;
While(TRUE) { Produce-Item(&item); recieve(consumer,&m); build-message(&m,item); send(consumer,&m); } Comsumer进程 int item,i; message m; for(i = 0; i < N; i++) send(producer,&m); While(TRUE) { receive(producer,&m); extract-item(&m,&item); send(producer,&m); Consume-item(item); }

2.2.8 消息传递消息传递模型的改进方法信箱机制去掉缓冲的信箱机制（会和，rendezvous) 管道概念建立固定数量消息的信箱
进程通信消息传递模型的改进方法信箱机制建立固定数量消息的信箱当发送接收消息时，读取信箱而不是进程的地址去掉缓冲的信箱机制（会和，rendezvous) 接收者直接从发送者的消息中拷贝信息节省内存空间，但是降低了灵活性，类似“严格轮转法” 管道概念与信箱效果等价，但是管道不限定消息边界（一次可以读写消息的大小）

其他经典IPC问题哲学家进餐问题多进程同步问题的建模读者－写者问题数据库互斥访问问题的建模理发师睡觉问题
CS模式进程同步问题的建模

哲学家就餐问题问题描述五个哲学家坐在圆桌前，每人一份炒饭每个哲学家两侧各有一支筷子哲学家处于吃饭和思考两种状态

哲学家就餐问题的直观解法思考1：这样的解法有何问题？ (page 63) 思考2：对左右的叉子是否可用进行验证，这样的修改有何优缺点？
哲学家进程 #define N void philosopher(int i) { While(TRUE) think()； take_forks(i); take_forks((i + 1) % N); eat(); put_forks(i); put_forks((i + 1) % N); } 思考1：这样的解法有何问题？ (page 63) 思考2：对左右的叉子是否可用进行验证，这样的修改有何优缺点？思考3：需要引入几个信号量才能实现最优化的解法呢？

哲学家就餐问题的信号量解法互斥关系分析同步关系分析特殊情况考虑筷子：同一时刻只能有一个哲学家拿起筷子
就餐：只有获得两个筷子后才能进餐特殊情况考虑死锁：如果每个哲学家都拿起一只筷子，都饿死饥饿：page 63 第二段并行程度：五只筷子允许两人同时进餐

哲学家就餐问题的信号量解法 #define N 5 #define LEFT (i + N – 1) % N
#define RIGHT (i + 1) % N #define THINKING 0 #define HUNGRY 1 #define EATING 2 typedef int semaphore int state[N]; semaphore mutex = 1; semaphore s[N];//初始为0 哲学家进程 void philosopher(int i) { While(TRUE){ think()； take_forks(i); eat(); put_forks(i);} } 取叉子函数 void take_forks (int i) { down(&mutex); state[i] = HUNGRY; test(i); up(&mutex); down(&s[i]); }

哲学家就餐问题的信号量解法放叉子函数 void put_forks (int i) { down(&mutex);
state[i] = THINKING; test(LEFT(i)); test(RIGHT(i)); up(&mutex); } Test函数 void test (int i) { if((state[i] == HUNGRY) && (state[LEFT(i)] ！= EATING) && (state[RIGHT(i)] != EATING)) state[i] = EATING; up(&s[i]); }

读者-写者问题问题描述写者向数据区放数据，读者从数据区获取数据多个读者可同时读取数据多个写者不能同时写数据
读者和写者的控制策略变化多端

读者－写者问题的信号量解法互斥关系分析读者和写者不能同时进入共享数据区多个写者不能同时进入共享数据区多个读者可以同时进入共享数据区
同步关系分析读者进入缓冲区，写者必须等待写者进入缓冲区，读者必须等待读者优先：一旦有读者进入，则后续读者均可进入合理顺序：读者在先来的写者之后写者优先：只要有写者等待，则后续读者必须等待

读者优先的信号量解法 V(write); rcount--; if(rcount == 0) V(write);
typedef int semph semph mutex = 1; semph write = 1; int rcount = 0; Reader进程 While(TRUE) { P(mutex); rcount++; if(rcount == 1) P(write); V(mutex); Read_Action(); rcount--; if(rcount == 0) V(write); } Writer进程 While(TRUE) { P(Write); Write_Action(); V(write); }

读者优先的信号量解法 typedef int semph semph rmutex = 1; semph wmutex = 1
semph write = 1; semph concur = 1; int rcount = 0; int wcount = 0; Reader进程 While(TRUE) { P(concur); P(rmutex); rcount++; if(rcount == 1) P(write); V(rmutex); V(concur); Read_Action(); P(mutex); rcount--; if(rcount == 0) V(write); V(mutex); } Writer进程 While(TRUE) { P(wmutex); wcount++; if(wcount == 1) P(concur); V(wmutex); P(Write); Write_Action(); V(write); wcount--; if(wcount == 0) V(concur); }

睡觉的理发师问题问题: 理发店有一名理发师，一把理发椅，n把供客户等待的椅子。如果没有客户，理发师坐在理发椅上睡觉。
当一个客户到来时，将理发师唤醒，为其理发。当理发师正在为客户理发时，另外的客户到达，则他们坐在椅子上等待。

睡觉的理发师问题的信号量解法互斥关系分析同步关系分析信号量设计理发椅上只能有一位顾客等待座位是有限缓冲区
只要存在顾客，理发师就不能睡觉信号量设计互斥信号量：实现对“等待顾客数”的互斥同步信号量1：理发师“睡眠”和“工作”的同步同步信号量2：等待顾客与等待座位的同步

睡觉的理发师问题的信号量解法 barber进程 While(TRUE) { P(customer); P(mutex);
#define CHAIRS N typedef int semph semph customer = 0; semph barer = 0; semph mutex = 1; int waiting = 0; barber进程 While(TRUE) { P(customer); P(mutex); waiting = waiting – 1; V(barbers); V(mutex); cut_hair(); } customer进程 While(TRUE) { P(mutex); if(waiting < CHAIRS) waiting += 1; V(customer); V(mutex); P(barber); } else

什么是调度算法当计算机是多道程序设计系统时，通常会有多个进程竞争CPU。当多个进程处于就绪状态而只有一个CPU时，操作系统就必须决定先运行哪一个进程。操作系统中做出这种决定的部分称为调度器（scheduler），它使用的算法称为调度算法（scheduling algorithm）。许多进程调度的处理方式对进程和线程都适用。

什么时候调度调度有可能在很多情况下发生。当一个进程退出时。当一个进程在I/O或者信号量上阻塞时。另外还有其他三种情况：
当一个新进程创建时。当一个I/O中断发生时。当一个时钟中断发生时。

非抢占式进程调度、抢占式进程调度非抢占式调度算法：
当把处理机分配给某进程后，便让该进程一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。实现简单，系统开销小，常用于批处理系统不利于处理紧急任务实时、分时系统不宜采用

非抢占式进程调度、抢占式进程调度抢占式调度算法:
允许调度程序根据某种原则（时间片、优先权、短进程优先），停止正在执行的进程，而将处理机重新分配给另一进程。有利于处理紧急任务实时与分时系统中常采用

调度的类型(scheduling) 按照调度的层次按照调度的时间周期按照OS的分类调度的类型

按照调度的层次一个作业从提交开始，往往要经历三级调度：高级调度、低级调度、中级调度。（1）高级调度（长程/作业/宏观调度）
主要任务：从外存后备队列中选择作业进入就绪队列或挂起就绪。在批处理系统中，大多配有作业调度在分时系统及实时系统中，一般不配置作业调度执行频率很低，通常为几分钟一次，甚至更久。

高级调度需解决的问题高级调度允许多少作业同时在内存中运行，它控制着多道程序的“道或度”。
若作业太多，则可能会影响系统的服务质量（如周转时间太长）若作业太少，又将导致系统资源利用率和吞吐量的下降。因此，应根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度。应将哪些作业从外存调入内存，将取决于调度算法（先来先服务、短作业优先等）。

按照调度的层次（2）中级调度（中程/交换调度）主要任务：在内存和外存对换区之间按照给定的原则和策略选择进程对换。
解决内存紧张问题，从而提高内存的利用率和系统吞吐量常用于分时系统或具有虚拟存储器的系统中

按照调度的层次（3）低级调度（短程/CPU/进程/微观调度）主要任务：从就绪队列中选择一个进程来执行并分配处理机。
低级调度是操作系统中最基本的调度调度频率非常高，一般几十毫秒一次常采用非抢占（非剥夺）方式和抢占（剥夺）方式两种

按照调度的层次（3）低级调度（短程/CPU/进程/微观调度）主要任务：从就绪队列中选择一个进程来执行并分配处理机。引起进程调度的因素：
进程正常终止或异常终止正在执行的进程因某种原因而阻塞在引入时间片的系统中，时间片用完在抢占调度方式中，就绪队列中某进程的优先权变得比当前正执行的进程高

按照调度的时间周期长期(long-term)：将进程投入"允许执行"进程缓冲池中，或送到"退出"进程缓冲池中。进程状态：New－>Ready suspend, Running －>Exit 中期(medium-term)：将进程的部分或全部加载到内存中。进程状态：Ready <－>Ready suspend, Blocked <－>Blocked suspend 短期(short-term)：选择哪个进程在处理机上执行。进程状态： Ready <－>Running I/O调度：选择哪个I/O等待进程，使其请求可以被空闲的I/O设备进行处理。

按照OS的分类不同的环境需要不同的调度算法。不同的应用领域有不同的目标。批处理
应用场合：大中型主机集中计算，如工程计算、理论计算（流体力学）交互式通常没有专门的作业调度实时

调度的性能准则在一个操作系统的设计中，应如何选择调度方式和算法，在很大程度上取决于操作系统的类型及其目标，选择调度方式和算法可以从两个方面分析考虑：从用户方面来考虑从系统角度来考虑

调度的性能准则 1. 面向用户的调度性能准则周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待－－批处理系统平均周转时间T 响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间－－分时系统截止时间：开始截止时间和完成截止时间－－实时系统，与周转时间有些相似。公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。

调度的性能准则 2.面向系统的调度性能准则系统吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系－－批处理系统
平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时处理机利用率高：－－大中型主机各类资源平衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配－－大中型主机

调度算法的目标所有系统 Page68页批处理系统公平——给每个进程公平的CPU份额策略强制执行——执行所规定的策略
平衡——保持系统所有部分都忙碌批处理系统吞吐量——最大化每小时作业数周转时间——最小化从提交到完成的时间间隔 CPU利用率——保持CPU始终忙碌 Page68页

调度算法的目标交互式系统实时系统响应时间——快速响应请求均衡性——满足所有用户的需求满足截止时间——避免丢失数据
可预测性——在多媒体系统中避免失真

调度算法进程调度的核心问题就是采用什么样的算法将处理机分配给进程，常用的进程调度算法有： NEXT: 实时系统中的调度先来先服务调度算法
短作业/进程优先调度算法时间片轮转调度算法优先权调度算法高响应比优先调度算法多级队列调度算法多级反馈队列调度算法 NEXT: 实时系统中的调度

（1）先来先服务调度算法FCFS 基本思想:按照进程进入就绪队列的先后次序来分配处理机。一般采用非剥夺的调度方式。 Example: 进程名到达时间服务时间 A B C D 该调度的Gantt图为: 平均周转时间:((1-0)+(101-1)+(102-2)+(202-3)）/4=100 平均等待时间:((0-0)+(1-1)+(101-2)+(102-3))/4 = 49.5 D B C A

（1）先来先服务调度算法FCFS A B D C 改变到达顺序: 进程名到达时间服务时间 A 0 1 B 1 100 D 2 100
改变到达顺序: 进程名到达时间服务时间 A B D C 该调度的Gantt图为: 平均周转时间:（(1-0)+(101-1)+(202-3)+(201-2)）/4=124.25 平均等待时间: ((0-0)+(1-1)+(201-3)+(101-2))/4 = 74.25 A B D C 周转T 100 124.25 等待T 49.5 74.25

（1）先来先服务调度算法FCFS FCFS调度算法存在的问题返回
从表面上，先来先服务于所有作业是公平的，即按照它们到来的先后次序进程服务。但若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。所以，现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。返回

（2）短作业/进程优先调度算法SJF/SPF
用于作业调度主要任务：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。短进程优先调度算法（SPF）用于进程调度主要任务：从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。可采用抢占（剥夺）或者非抢占（非剥夺）调度方式。

SJ（P）F ——非抢占式 0 1 2 3 101 102 202 A B C D 到达顺序: 进程名到达时间服务时间 A 0 1
到达顺序: 进程名到达时间服务时间 A B D C 该调度的Gantt图为: 平均周转时间:((1-0)+(101-1)+(102-3)+(202-2))/4=100 平均等待时间: ((0-0)+(1-1)+(101-3)+(102-2))/4 = 49.5 A B C D FCFS SPF 周转T 124.25 100 等待T 74.25 49.5

SJ（P）F ——抢占式 0 1 2 3 4 102 202 A B C D 到达顺序: 进程名到达时间服务时间 A 0 1
到达顺序: 进程名到达时间服务时间 A B D C 该调度的Gantt图为: 平均周转时间：((1-0)+(102-1)+(4-3)+(202-2)）/4=75.75 平均等待时间：((0-0)+(4-3)+(3-3)+(102-2))/4 = 25.25 A B C D FCFS SPF-非 SPF-抢周转T 124.25 100 75.75 等待T 74.25 49.5 25.25

SJF/SPF调度的优缺点优点：缺点：故SJ(P)F算法虽然是优化的，但在CPU调度中很难实现。返回
1）能有效降低作业的平均等待时间 2）提高吞吐量 3）能有效缩短进程的周转时间缺点： 1）对长作业不利 2）没有考虑作业的紧迫程度 3）作业执行时间、剩余时间仅为估计*；故SJ(P)F算法虽然是优化的，但在CPU调度中很难实现。返回

（3）时间片轮转调度算法RR 时间片轮转法：系统将所有原就绪进程按FCFS的原则，排成一个队列，依次调度，把CPU分配给队首进程，并令其执行一个时间片/CPU时间，通常为10-100ms。时间片用完后，该进程将被抢占并插入就绪队列末尾。特点：应用于分时OS 保证及时响应用户的请求，是早期采用的一种调度算法进入90年代后，广泛采用多级反馈队列调度算法。

（3）时间片轮转调度算法RR 注：（1）保证了就绪队列中的所有进程在给定的时间内，均能获得一时间片来执行，即系统在给定的时间内，响应所有用户的请求。（2）若进程的执行时间少于时间片，则自愿释放CPU （3）时间片的影响：调度算法（太长---FCFS）上下文切换（太短---上下文切换频繁，如下页）平均周转时间

（3）时间片轮转调度算法RR 短时间片增加上下文切换频率

（3）时间片轮转调度算法RR 周转时间随时间片变化

（3）时间片轮转调度算法RR 例(1) EG：进程到达时间服务时间 P1 0.0 7 P2 2.0 4 P3 4.0 1
平均周转时间=((15-0)+(12-2)+(6-4)+(16-5))/4=9.5 平均等待时间=( )/4 = 5.5 P1 P2 P4 P3

（3）时间片轮转调度算法RR 例(2) EG：进程到达时间服务时间 P1 0.0 7 P2 2.0 4 P3 4.0 1
平均周转时间=((12-0)+(8-2)+(9-4)+(16-5))/4=8.5 平均等待时间=( )/4 = 4.5 P1 P2 P4 P3 FCFS 非抢占SPF 抢占SPF RR-1 RR-4 平均周转时间 8.75 8 7 9.5 8.5 平均等待时间 4.75 4 3 5.5 4.5 返回

（4）优先权调度算法非抢占式优先权算法：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成/因发生某事件而放弃处理机时，系统方可重新分配处理机。抢占式优先权算法：系统把处理机分配给就绪队列中优先机最高的进程，使之执行。但在其执行期间，只要出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。

（4）优先权调度算法非抢占式优先权算法—例 EG：进程到达时间服务时间优先权 P1 0.0 7 3 P2 2.0 4 2
Gantt图平均周转时间=((7-0)+(15-2)+(16-4)+(11-5))/4=8.5 平均等待时间=( )/4 = 5.5 P1 P2 P4 P3 FCFS SJF-非 SJF-抢 RR-4 优-非平均周转时间 8.75 8 4 8.5 9.5 平均等待时间 4.75 3 4.5 5.5

（4）优先权调度算法抢占式优先权算法—例 EG：进程到达时间服务时间优先权 P1 0.0 7 3 P2 2.0 4 2
Gantt图平均周转时间=((11-0)+(9-2)+(16-4)+(8-5))/4=8.25 平均等待时间=( )/4 = 5.25 P1 P2 P4 P3 FCFS SJF-非 SJF-抢 RR-4 优-非优-抢平均周转时间 8.75 8 4 8.5 9.5 8.25 平均等待时间 4.75 3 4.5 5.5 5.25

优先权的类型静态优先权动态优先权返回优先权在创建进程时确定在进程的整个运行期间保持不变一般用一整数表示，小表优先级高
在进程的运行期间会发生变化返回

（5）高响应比优先权调度算法基本思想：把CPU分配给就绪队列中响应比最高的进程。优先权的变化为返回为响应比。注：
1)如等待时间相同,则要求服务时间愈短,其优先权愈高---SPF. 2)如要求服务时间相同,优先权决定于等待时间---FCFS。 3)对长作业,若等待时间足够长，优先权也高，也能获得CPU。返回

（6）多级队列调度算法基本思想: 根据作业的性质或类型，将就绪队列划分为若干个独立的队列，每个作业固定地分属一个队列。每个队列采用一种调度算法，不同的队列可以采用不同的调度算法。如：交互型作业设置一队列------时间片轮转调度算法批处理作业设置一队列------FCFS调度算法前台[交互式]------RR 后台[批处理]------优先权、SPF或 FCFS 返回

（7）多级反馈队列调度算法基本思想：目前公认的一种较好的进程调度算法。多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合和发展
通过动态调整进程优先级和时间片大小，不必事先估计进程的执行时间，多级反馈队列可兼顾多方面的系统目标目前公认的一种较好的进程调度算法。

（7）多级反馈队列调度算法返回实现思想设置多个就绪队列，并为每个队列赋予不同的优先级。队列1的优先级最高，其余队列逐个降低。
就绪队列1 就绪队列2 就绪队列n CPU 完成返回设置多个就绪队列，并为每个队列赋予不同的优先级。队列1的优先级最高，其余队列逐个降低。每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。当一个新进程进入系统时，首先将它放入队列1的末尾，按FCFS等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列2的末尾，按FCFS再次等待调度，如此下去，进入队列n按RR算法调度执行。仅当队列1为空时，才调度队列2中的进程运行。若队列i中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行。原进程转移至下一队列。

实时系统中的调度在一个实时系统中，时间起着非常重要的作用，即每一个实时进程或任务都有一个时间约束要求。
如：在何时之前必须开始做，在何时之前必须完成等等。在一个实时应用系统，可能有多个实时进程或任务，每个实时任务都有其时间约束，所以需一种新的调度算法来合理地安排这些实时任务的执行次序，使它们能满足各个实时任务的的时间约束条件-----实时调度。满足实时任务各自时间约束条件的调度称为实时调度。

（1）实现实时调度的基本条件提供必要的调度信息（就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级）
系统处理能力强（限制条件：决定系统是否可调度，否则减少C 单机: （m-实时任务数目，ci—每次处理时间，pi—周期时间）多机: （N—处理机数目，ci—每次处理时间，pi—周期时间）采用抢占式的调度机制具有快速切换机制

（2）实时调度算法的分类按实时任务性质（即对时间约束强弱程度）按调度方式硬实时调度：必须满足任务截止期要求，错过可能导致严重后果。
软实时调度算法：期望满足任务截止期要求，错过一般可容忍。按调度方式非抢占式调度算法（如下图所示）非抢占式轮转调度算法：用于工业生产的群控系统中。非抢占式优先调度算法：用于有一定时间要求的实时控制系统之中。抢占式调度算法（如下图所示）按抢占发生的时间基于时钟中断抢占的优先权调度算法立即抢占的优先权调度算法

（2）实时调度算法的分类实时进程调度（a）非抢占轮转调度（c）基于时钟中断抢占的优先权抢占调度（d）立即抢占的优先权调度
进程n 实时进程进程1 进程2 实时进程要求调度调度实时进程运行调度时间（a）非抢占轮转调度实时进程要求调度时钟中断到来时调度调度时间当前进程实时进程（c）基于时钟中断抢占的优先权抢占调度实时进程要求调度实时进程抢占当前进程，并立即执行调度时间当前进程实时进程（d）立即抢占的优先权调度实时进程要求调度当前进程运行完成调度时间当前进程实时进程（b）非抢占优先权调度

（2）实时调度算法的分类与实时调度相关的几个概念就绪时间：实时任务产生并可以开始处理的时间。开始截止时间：实时任务最迟开始处理的时间。
处理时间：实时任务处理所需要的处理机的时间。完成截止时间：实时任务最迟完成时间。发生周期：周期性实时任务的发生间隔时间。优先级：实时任务相对紧廹程序。

（3）常用的几种实时调度算法最早截止时间优先算法（EDF算法）
该算法是根据任务的开始截止时间来确定任务的优先级。开始截止时间越早，其优先级越高。就绪队列中任务按其截止时间排列，队首任务先分配处理机。如： 2 4 3 1 开始截止时间任务执行任务到达

（3）常用的几种实时调度算法最低松弛度优先算法（LLF算法）该算法是根据任务紧急（或松弛）的程序，来确定任务的优先级。
任务的紧急度越高，其优先级越高，并使之优先执行。该算法主要采用抢占调度方式，其调度也即具有完成截止时间的周期性实时任务的调度。例：在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行，执行时间为25ms。其最低松弛度优先算法调度如下：

最低松弛度优先算法（LLF算法）某时刻的松弛度计算：松弛度=必须完成时间-其本身的运行时间-当前时间优先调度松弛度小的任务
A8 A7 A6 A5 A4 A3 A2 A1 160 140 120 100 80 60 40 20 B3 B2 B1 A和B任务每次必须完成的时间某时刻的松弛度计算：松弛度=必须完成时间-其本身的运行时间-当前时间优先调度松弛度小的任务利用最低松弛度优先算法调度情况 80 70 60 50 40 30 20 10 B2(15) B1(20) A1(10) A2(10) B1(5) A3(10) A4(10) B2(10) t t t t4 t t t t8

UNIX中进程的调度 UNIX是单纯的分时系统，无作业调度，只设置有中级调度和低级调度。常采用的是多级反馈队列轮转调度。引起进程调度的原因
时钟中断处理程序对调度标志runrun的重新置位。系统执行了wait、exit及sleep等系统调用后。进程执行完系统调用从核心态返回到用户态时，出现了更高优先级的进程。调度算法动态优先数轮转调度算法进程优先级的分类核心优先级（分为可中断和不可中断）用户优先级（分成n+1级，0级最高）进程优先级的计算

作业 Linux, Windows和UNIX的进程调度比较与分析?

Thanks for your time! Questions & Answers

《操作系统设计与实现》第2章进程.

Similar presentations

Presentation on theme: "《操作系统设计与实现》第2章进程."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

《操作系统设计与实现》 第2章 进程.

Similar presentations

Presentation on theme: "《操作系统设计与实现》 第2章 进程."— Presentation transcript:

Similar presentations

About project

反馈

《操作系统设计与实现》第2章进程.

Presentation on theme: "《操作系统设计与实现》第2章进程."— Presentation transcript: