操作系统课件-孟庆昌

《操作系统课件-孟庆昌》由会员分享，可在线阅读，更多相关《操作系统课件-孟庆昌（477页珍藏版）》请在金锄头文库上搜索。

1、第1章操作系统引论2021/3/111n参考书：n操作系统精髓与设计原理第五版n William Stalling 著n 操作系统原理与设计n 曹先彬 陈兰香 编n操作系统第二版n 孟庆昌 牛欣源 编2021/3/112本章内容提要计算机硬件结构 什么是操作系统操作系统概念 操作系统的主要功能 操作系统的地位 操作系统的发展历程操作系统的类型操作系统的特征操作系统结构设计2021/3/1131.1计算机硬件结构 n计算机系统计算机系统是由硬件和软件组成的 硬件是软件建立与活动的基础 软件是对硬件进行管理和功能扩充进行管理和功能扩充 n计算机硬件结构 由五大功能部件组成，即：运算器、控制器、存储

2、器、输运算器、控制器、存储器、输入设备和输出设备。入设备和输出设备。它们经由系统总线连接在一起，实现彼此通信。2021/3/114现代计算机硬件结构 2021/3/1151.1.1 处理器CPU工作的基本周期是： 提取指令，译码分析，执行指令提取指令，译码分析，执行指令 每个CPU可以执行的指令集是专用的所有CPU都包含某些寄存器通用寄存器 专用寄存器 程序计数器栈指针 PSW（程序状态字）两种两种处理机执行状态处理机执行状态 核心态 用户态2021/3/1161.1.2 存储器n寄存器n高速缓存 n内存n磁盘n磁带2021/3/1171.1.3 I/O设备通常由控制器和设备本身两部分组成n控

3、制器n设备 设备驱动程序2021/3/1181.1.4 总线总线分类总线分类n数据总线n地址总线n控制总线2021/3/1191.2 什么是操作系统1.2.1 操作系统概念1操作系统作为扩展机器 把硬件细节与程序员隔离开，隐藏了底层硬件的特性 功能更强、使用更方便 2操作系统作为资源管理器n监视各种资源，随时记录它们的状态；n实施某种策略以决定谁获得资源，何时获得，获得多少；n分配资源供需求者使用；n回收资源，以便再分配。3. 操作系统的用户观点和系统观点 2021/3/1110定义定义： 操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用

4、户与计算机之间的接口。2021/3/1111 操作系统是系统软件 基本职能是控制和管理系统内各种资源，有效地组织多道程序的运行提供众多服务，方便用户使用，扩充硬件功能 2021/3/11121.2.2 操作系统的主要功能1存储管理 内存分配 地址映射 内存保护 内存扩充2021/3/11131.2.2 操作系统的主要功能2作业和进程管理 作业和进程调度 进程控制 进程通信2021/3/11141.2.2 操作系统的主要功能3设备管理 缓冲区管理 设备分配 设备驱动 设备无关性2021/3/11151.2.2 操作系统的主要功能4 4文件管理功能文件管理功能 文件存储空间的管理 文件操作的一般管

5、理 目录管理 文件的读/写管理和存取控制2021/3/11161.2.2 操作系统的主要功能5 5用户接口用户接口程序接口命令行接口图形用户接口（GUI） 2021/3/11171.2.3 操作系统的地位 计算机系统的层次关系2021/3/1118n简言之简言之，软件软件是计算机执行的程序n软件通常可分为三大类 应用软件 支撑软件 系统软件n操作系统是裸机之上的第1层软件，它只在核心态模式下运行。n通常把经过软件扩充功能后的机器称为“虚拟机”2021/3/11191.3 操作系统的发展历程 1.3.1 操作系统的形成 1手工操作阶段 2早期批处理阶段 早期联机批处理 早期脱机批处理 3多道批处

6、理系统2021/3/1120多道批处理系统2021/3/1121多道程序设计： 在内存中同时存放多道程序，在管理程序的控制下交替地执行。这些作业共享CPU和系统中的其他资源。 并发：多道程序在CPU上交替运行 系统吞吐量： 在一段给定的时间内，计算机所能完成的总工作量。2021/3/1122 1.3.2 操作系统的发展2021/3/11231.3.3 推动操作系统发展的动力n 硬件技术更新n 应用需求扩大2021/3/11241.4 操作系统的类型n5大基本类型 批处理系统 分时系统 实时系统 网络系统 分布式系统 2021/3/11251.4.1 批处理系统1作业n是用户定义的、由计算机完成

7、的工作单位。它通常包括一组计算机程序、文件和对操作系统的控制语句。n作业步 由作业控制语句明确标识的计算机程序的执行过程 2021/3/11262工作流程多道批处理系统中的作业流程 2021/3/1127批处理系统3.特点 多道多道：系统在内存中存放多个作业，并且在外存上还保存大量的后备作业。 成批：成批：系统按批次调度作业，而在系统运行过程中不允许用户和机器之间发生交互作用。n批处理系统的主要优点优点： 系统资源利用率高 系统吞吐量大n明显缺点缺点： 用户作业的等待时间长 没有交互能力2021/3/11281.4.2 分时系统1 1分时概念和分时系统的实现方法分时概念和分时系统的实现方法n分

8、时：广义上，是指对时间的共享。 在分时系统中，分时主要是指若干并发程序对CPU时间的共享n并行：是指在同一时刻有两个或两个以上的活动发生。n时间片2021/3/1129分时系统 2分时系统的特征和优点n 基本特征 同时性 交互性 独立性 及时性n主要优点 人机交互友好 应用方便 资源共享2021/3/11301.4.3 实时系统1实时系统的引入实时系统的引入n实时系统 具有实时特性，能够支持实时控制系统工作的操作系统。 重要特征：对时间有严格限制和要求 n三种典型应用形式 过程控制系统 信息查询系统 事务处理系统2021/3/11312 2实时系统与分时系统的差别实时系统与分时系统的差别n 交

9、互性n 实时性n 可靠性2021/3/1132 实时系统3 3实现方式实现方式 硬式实时系统 对时间严格约束 软式实时系统 对时间限制稍弱一些2021/3/11331.4.4 网络操作系统1计算机网络的特征 分布性 自治性 互连性 可见性 2021/3/11342网络操作系统 服务器 客户机 网络操作系统实现网络通信、资源共享和保护， 以及提供网络服务和网络接口等 本地操作系统完成本地资源的管理和服务功能 客户-服务器模式 Sun公司的NFSNovell公司的Netware 5.0Microsoft公司的Windows NT Server 4.0IBM公司的LAN Server 4.0SCO公

10、司的UNIX Ware 7.1自由软件Linux 2021/3/11353网络操作系统的特性n接口一致性 n资源透明性 n操作可靠性 n处理自主性 n执行并行性 2021/3/11361.4.5 分布式操作系统n分布式系统特点 透明性 灵活性 可靠性 高性能 可扩充性 2021/3/11371.4.6 其他操作系统1.个人机系统 Windows XP、Windows Vista、UNIX、Linux 2.多处理器系统 对称多处理（SMP）系统 增加吞吐量 提高性能/价格比 提高可靠性 3嵌入式系统 2021/3/11381.5 1.5 操作系统的特征操作系统的特征（1 1）并发并发 两个或多个

11、活动在同一给定的时间间隔中进行。两个或多个活动在同一给定的时间间隔中进行。（2 2）共享共享 计算机系统中的资源被多个进程所共用。计算机系统中的资源被多个进程所共用。（3 3）不确定性不确定性 系统中各种事件发生顺序的不可预测性。系统中各种事件发生顺序的不可预测性。2021/3/11391.6 操作系统结构设计1.6.1 整体系统 任意调用，耦合紧密， 实现的效率高 结构关系不清晰， 系统的可靠性降低 模块调用示意图2021/3/11401.6.2 层次式系统THE操作系统的层次结构具有整体系统的长处新优点结构关系清晰，提高系统的可靠性、可移植性和可维护性。 2021/3/11411.6.3

12、虚拟机结构带CMS的VM/370结构通过共享物理机器资源来实现主要优点 同时运行多个操作系统 系统安全,有效地保护系统资源 提供良好的工作环境 组建虚拟网络 2021/3/1142 1.6.4 客户-服务器系统客户-服务器系统模型 微内核微内核 2021/3/1143 客户-服务器系统适于在分布式系统中应用 分布式系统中的客户-服务器模型 2021/3/1144 第2章 进程和线程2021/3/1145本章内容提要n 进程概念 n进程的状态和组成n进程管理 n线程 n进程的同步和通信 n经典进程同步问题 n管程 n进程通信 2021/3/11462.1 进程概念2.1.1 多道程序设计 1顺序

13、程序活动的特点 顺序性 封闭性 可再现性 2多道程序设计 程序并发执行 提高系统资源利用率 增加作业吞吐量 2021/3/1147 多道程序设计 3 3程序并发执行的特征程序并发执行的特征 失去封闭性 程序与计算不再一一对应 并发程序在执行期间相互制约2021/3/11482.1.2 2.1.2 进程概念进程概念 1 1进程概念的引入进程概念的引入 多道程序并发执行所引发的一系列新情况2021/3/11492 2进程概念进程概念进程最根本的属性是动态性和并发性n进程定义：程序在并发环境中的执行过程n进程和程序的进程和程序的区别区别 （1 1）动态性）动态性 （2 2）并发性）并发性 （3 3）

14、非对应性）非对应性 （4 4）异步性）异步性2021/3/1150 进程概念进程概念 3 3进程的基本特征进程的基本特征 （1）动态性 （2）并发性 （3）调度性2021/3/11512.2 进程的状态和组成2.2.1 进程的状态及其转换 1 1进程的基本状态进程的基本状态 运行状态（Running） 就绪状态（Ready） 阻塞状态（Blocked）2021/3/1152 进程的5种基本状态及其转换2021/3/11532进程状态的转换 （1）新建就绪（2）就绪运行（3）运行阻塞（4）阻塞就绪（5）运行就绪（6）运行终止2021/3/11542.2.2 进程描述1进程映像 进程映像通常就由程

15、序、数据集合、栈和PCB等4部分组成 进程映像模型2021/3/1155 进程描述2进程控制块的组成n进程控制块（PCB） 也称进程描述块（Process Descriptor），它是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统对进程施行识别和控制的依据。2021/3/1156 进程描述进程控制块应包含的主要内容：n进程名n特征信息n进程状态信息n调度优先权n通信信息n现场保护区n资源需求n进程实体信息n族系关系n其他信息2021/3/1157 进程描述3进程控制块的作用n每个进程有惟一的进程控制块n操作系统根据PCB对进程实施控制和管理n进程的动

16、态、并发等特征是利用PCB表现出来的nPCB是进程存在的唯一标识 2021/3/11582.2.3 进程队列1线性方式 PCB线性队列示意图 2021/3/1159 进程队列2链接方式PCB链接队列示意图2021/3/1160 PCB索引结构示意图 3索引方式进程队列2021/3/11612.3 进 程 管 理2.3.1 进程图 进程图（Process Graph）是描述进程族系关系的有向树 进程创建的层次关系2021/3/11622.3.2 进程创建引发创建进程的事件：n调度新作业n用户登录 n操作系统提供特定服务 n派生新进程 2021/3/1163 进程创建创建新进程时要执行创建进程的系

17、统调用（如UNIX/Linux系统中的fork）其主要操作过程有如下四步： （1）申请一个空闲的PCB （2）为新进程分配资源 （3）将新进程的PCB初始化 （4）将新进程加到就绪队列中2021/3/1164#include #include #include int main(int argc,char *argv)int pid; pid = fork(); /* 创建一个子进程*/if (pid 0) /* 出现错误。进程ID号不可能小于0 */fprintf(stderr, Fork Failed); /* 输出出错消息Fork Failed */exit(-1); /* 程序终止，返

18、回码-1*/ else if (pid = 0) /* 下面是子进程执行*/ execlp( /bin/ls, ls,NULL); /* 执行目录/bin下面的ls命令*/ else /* 下面是父进程执行*/ wait(NULL); /* 父进程等待子进程完成*/ printf( Child Complete ); /* 输出子进程完成的信息*/ exit(0); /* 终止*/ 2021/3/11652.3.3 2.3.3 进程终止进程终止导致进程终止的三种情况： n正常终止n异常终止n外部干扰2021/3/1166 进程终止进程终止终止进程的主要操作过程如下：n找到指定进程的PCBn终止

19、该进程的运行n回收该进程所占用的全部资源n终止其所有子孙进程，回收它们所占用的全部资源。n将被终止进程的PCB从原来队列中摘走2021/3/11672.3.4进程阻塞进程阻塞的过程如下：n立即停止当前进程的执行n现行进程的CPU现场保存n现行状态由“运行”改为“阻塞”n转到进程调度程序2021/3/11682.3.5 进程唤醒 唤醒原语执行过程如下：n把阻塞进程从相应的阻塞队列中摘下n将现行状态改为就绪状态，然后把该进程插入就绪队列中n如果被唤醒的进程比当前运行进程的优先级更高，则设置重新调度标志2021/3/11692.4 线程2.4.1 线程概念n现代操作系统中，进程只作为资源拥有者，而调

20、度和运行的属性赋予新的实体线程。n线程（Thread）是进程中实施调度和分派的基本单位2021/3/1170 线程概念1线程的组成每 个 线 程 有 一 个thread结构，即线程控制块，用于保存自己私有的信息，主要由以下 4个基本部分组成：n一个唯一的线程标识符 n一组寄存器 n两个栈指针 n一个私有存储区 thread结构示意图2021/3/1171 线程的组成n线程必须在某个进程内执行n一个进程可以包含一个线程或多个线程单线程和多线程的进程模型2021/3/11722线程的状态n运行状态n就绪状态 n阻塞状态n终止状态2021/3/11733线程的管理n 线程创建n 线程终止n 线程等待

21、n 线程让权2021/3/11744线程和进程的关系 一个进程可以有多个线程，但至少要有一个线程；而一个线程只能在一个进程的地址空间内活动。 资源分配给进程，同一进程的所有线程共享该进程的所有资源。 处理机分配给线程，即真正在处理机上运行的是线程。 线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。2021/3/11755引入线程的好处 易于调度 提高并发性 开销少 利于充分发挥多处理器的功能2021/3/11762.4.2线程的实现在用户空间实现 优点：切换速度快；调度算法可专用 ；可运行在任何操作系统上 缺点：阻塞问题；多处理器利用问题 在核心空间实现 优点：克服

22、了用户级线程方式的两个主要缺陷；本身也可以是多线程的 缺点：控制转移开销大 组合方式 2021/3/11772.5 进程的同步和通信进程间的相互关系主要分为如下三种形式： 互斥竞争同一资源而发生相互制约 同步协同完成一项任务 通信交换信息 2021/3/11782.5.1 进程的同步与互斥1 1同步同步 同步进程通过共享资源来协调活动，在执行时间的次序上有一定约束。虽然彼此不直接知道对方的名字，但知道对方的存在和作用。在协调动作的情况下，多个进程可以共同完成一项任务。2021/3/11792 2互斥互斥n在逻辑上这两个进程本来完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。n它们的运

23、行不具有时间次序的特征2021/3/1180n互斥示例 假定进程Pa负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。 打印机分配表（初始情况） 打印机分配表（出错情况） 打印机编号 分配标识 用户名 用户定义的设备名 01MengPRINT1021LiuOUTPUT打印机编号 分配标识用户名用户定义的设备名011021LiuOUTPUT2021/3/1181n竞争条件竞争条件（Race Condition） 两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序。2021/3/11822.5.2 临界资源和临界区1临界资源

24、和临界区n临界资源（Critical Resource） 一次仅允许一个进程使用的共享资源n临界区（Critical Section），简称CS区 在每个进程中访问临界资源的那段程序2021/3/11832进程的一般结构 典型进程的一般结构 2021/3/11843 3临界区进入准则临界区进入准则 单独进入 独占该区 限时退出 主动让权进程A和进程B互斥使用临界区的过程2021/3/11852.5.3 互斥实现方式1利用硬件方法解决进程互斥问题 禁止中断 进入临界区之后立即关闭所有的中断 专用机器指令 TSL（Test and Set Lock，即测试并上锁）的指令：TSL RX，LOCK 汇

25、编代码示例 enter_region: TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET leave_region: MOVE LOCK,#0 RET 2021/3/11862原语n是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomic action），即一个操作中的所有动作要么全做，要么全不做。n执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。2021/3/11873利用软件方法解决进程互斥问题 可为每类临界区设置一把锁，该锁有打开和关闭两种状态。n 关锁原语lock (W)

26、: while (W=1); W=1;n 开锁原语unlock (W): w=0;2021/3/1188 进程进程A A lock(W);lock(W);打印信息打印信息S; S; CSCS区区 unlock(W);unlock(W); 进程进程B B lock(W);lock(W);打印信息打印信息S; S; CSCS区区 unlock(W);unlock(W);用锁实现进程互斥设系统中有一台打印机，有两个进程A和B都要使用它，以变量W表示锁，预先把它的值置为0。 2021/3/11892.5.4 2.5.4 信号量信号量1整型信号量nP操作最初源于荷兰语proberen，表示测试；V操作源

27、于荷兰语verhogen，表示增加。n在有些书上将P操作称做wait或者DOWN操作，将V操作称做signal或者UP操作。n对信号量的操作有以下限制： 信号量可以初始化为一个非负值。 只能由P和V两个操作来访问信号量。 2021/3/1190 整型信号量nP和V操作都是原语n伪代码形式 P(S) V(S) while(S0); S+; S-; n实现互斥的伪代码形式 do P(mutex); 临界区 V(mutex); 其他代码区 while(1); 2021/3/1191 信号量信号量2 2结构型信号量结构型信号量n结构型信号量又称计数信号量计数信号量，简称信号量 n一般是由两个成员组成的

28、数据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。 typedef struct int value; struct PCB *list; semaphore;2021/3/1192 结构型信号量结构型信号量信号量的值与相应资源的使用情况有关信号量的一般结构及PCB队列 2021/3/1193对信号量的操作有如下严格限制：n信号量可以赋初值，且初值为非负数。 n在使用过程中，信号量的值可以修改，但只能由P和V操作来访问，不允许通过其他方式来查看或操纵信号量。 结构型信号量结构型信号量2021/3/1194nP、V操作的定义 void P(semaphore S) v

29、oid V(semaphore S) S.value-; S.value+； if(S.value0) if (S.value=0) 把这个进程加到S.list队列； 从S.list队列中移走进程Q； block( )； wakeup(Q)； 在具体实现时应注意，P, V操作都应作为一个整体实施，不允许分割或相互穿插执行 结构型信号量结构型信号量2021/3/1195 结构型结构型 信号量信号量3二值信号量 一种特例，它的值只能在0和1之间选择typedef struct enumfalse,truevalue; /*枚举量*/ struct PCB *list;B_semaphore;voi

30、d P_B(B_semaphore S) if (S.value=true) S.value=false; else 把该进程放入S.list队列; block( ); void V_B(B_semaphore S) if(S.list=NULL) S.value=true; else 从S.list队列中移走进程Q; wakeup(Q); 2021/3/11962.5.5 信号量的一般应用1用信号量实现进程互斥 打印机分配表的互斥使用 Pa: Pb: P(mutex) P(mutex) 分配打印机 释放打印机 （读写分配表） （读写分配表） V(mutex) V(mutex) 2021/3/

31、1197 用信号量实现进程互斥利用信号量实现互斥的一般模型是： 进程P1 进程P2 进程Pn P(mutex); P(mutex); P(mutex); 临界区 临界区 临界区 V(mutex); V(mutex); V(mutex); 2021/3/1198 用信号量实现进程互斥注意点：注意点： 在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。 互斥信号量mutex的初值一般为1。2021/3/11992用信号量实现进程简单同步 对缓冲区的同步使用问题 简单供者和用者对缓冲区的使用关系2021/3/11100 用信号量实现进

32、程简单同步n供者和用者间要交换两个消息： 缓冲区空 缓冲区满n设置两个信号量： S1表示缓冲区是否空（0表示不空，1表示空）。 S2表示缓冲区是否满（0表示不满，1表示满）。 规定S1和S2的初值分别为1和02021/3/11101用信号量实现进程简单同步 供者进程 用者进程 L1: P(S1) L2: 启动读卡机 P(S2) ; 从缓冲区取出信息 收到输入结束中断 V(S1); V(S2); 加工并且存盘 goto L1; goto L2;2021/3/11102用信号量实现进程简单同步用P和V操作实现同步时应注意如下三点： 分析进程间的制约关系，确定信号量种类。 信号量的初值与相应资源的数

33、量有关，也与P, V操作在程序代码中出现的位置有关。 同一信号量的P, V操作要“成对”出现，但是，它们分别出现在不同的进程代码中。2021/3/111032.6 经典进程同步问题1生产者-消费者问题n生产者:能产生并释放资源的进程n消费者:单纯使用（消耗）资源的进程n问题表述 一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等统称为产品）送入缓冲区，消费者进程从中取出产品。 假定缓冲区共有N个，不妨把它们设想成一个环形缓冲池。2021/3/11104 生产者-消费者问题生产者-消费者问题环形缓冲池它们应满足如下同步条件： 任一时刻所有生

34、产者存放产品的单元数不能超过缓冲区的总容量（N）。 所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。2021/3/11105 生产者-消费者问题设缓冲区的编号为0N-1，in和out分别是生产者进程和消费者进程使用的指针，指向下面可用的缓冲区，初值都是0。设置三个信号量： nfull：表示放有产品的缓冲区数，其初值为0。nempty：表示可供使用的缓冲区数，其初值为N。nmutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。2021/3/11106 生产者-消费者问题生产者进程Producer： 消费者进程Consumer： while(

35、TRUE) while(TRUE) P(empty); P(full); P(mutex); P(mutex); 产品送往buffer(in); 从buffer(out)中取出产品； in=(in+1)mod N; out=(out+1)mod N; /*以N为模*/ /*以N为模*/ V(mutex); V(mutex); V(full); V(empty); 2021/3/111072读者-写者问题 读者-写者问题也是一个著名的进程互斥访问有限资源的同步问题。例如，一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写。允许多个进程同时读该数据库，但是在任何时候如果有一个进程写（即

36、修改）数据库，那么就不允许其他进程访问它 既不允许写，也不允许读。2021/3/11108 读者-写者问题 信号量设置： 读互斥信号量rmutex 初值为1 写互斥信号量wmutex 初值为1 rmutex：读者互斥地访问readcount wmutex：保证一个写者与其他读者/写者互斥地访问共享资源读计数器readcount，整型变量，初值为0。2021/3/11109 读者-写者问题 读者读者ReadersReaders while(TRUE) P(rmutex); readcount=readcount+1; if(readcount=1) P(wmutex); V(rmutex); 执

37、行读操作 P(rmutex); readcount=readcount-1; if(readcount=0) V(wmutex); V(rmutex); 使用读取的数据 写者写者WritersWriters while(TRUE) while(TRUE) P(wmutex); P(wmutex); 执行写操作执行写操作 V(wmutex); V(wmutex); 这个算法隐含读者的优先级高于写者这个算法隐含读者的优先级高于写者2021/3/111103哲学家进餐问题五位哲学家围坐在一张圆桌旁进餐，每人面前有一只碗，各碗之间分别有一根筷子。每位哲学家在用两根筷子夹面条吃饭前独自进行思考，感到饥饿

38、时便试图占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能强行从邻座手中拿过筷子，而且必须用两根筷子进餐；餐毕，要把筷子放回原处并继续思考问题。 哲学家进餐问题2021/3/11111 哲学家进餐问题=#define N 5#define LEFT (i-1)%N#define RIGHT (i+1)%N#define THINKING 0#define HUNGRY 1#define EATING 2 typedef struct /* 定义结构型信号量 */ int value; struct PCB *list; semaphore; int stateN; semaphore m

39、utex=1; /* 互斥进入临界区 */ semaphore sN; /* 每位哲学家一个信号量 */2021/3/11112 哲学家进餐问题void philosopher(int i) while(TRUE) think(); /* 哲学家在思考问题哲学家在思考问题 */ take_chopstick(i); /* 拿到两根筷子或者等待拿到两根筷子或者等待 */ eat(); /* 进餐进餐 */ put_chopstick(i); /* 把筷子放回原处把筷子放回原处 */ void take_chopstick(int i) P(mutex); statei=HUNGRY; test(

40、i); /* 试图拿两根筷子试图拿两根筷子 */ V(mutex); P(si);2021/3/11113 哲学家进餐问题void put_chopstick(int i) P(mutex); statei=THINKING; test(LEFT); /* 查看左邻，现在能否进餐查看左邻，现在能否进餐 */ test(RIGHT); /* 查看右邻，现在能否进餐查看右邻，现在能否进餐 */ V(mutex); void test(int i) if(statei=HUNGRY & stateLEFT!=EATING & stateRIGHT!=EATING) statei=EATING; V

41、(si ); =2021/3/11114打瞌睡的理发师4 4打瞌睡的理发师问题打瞌睡的理发师问题理理发发店店有有一一名名理理发发师师，一一把把理理发发椅椅和和几几把把座座椅椅，等等待待理理发发者者可可坐坐在在上上面面。如如果果没没有有顾顾客客到到来来，理理发发师师就就坐坐在在理理发发椅椅上上打打盹盹。当当顾顾客客到到来来时时，就就唤唤醒醒理理发发师师。如如果果顾顾客客到到来来时时理理发发师师正正在在理理发发，该该顾顾客客就就坐坐在在椅椅子子上上排排队队；如如果果满满座座了了，他他就就离离开开这这个个理理发发店，到别处去理发。店，到别处去理发。 2021/3/11115 打瞌睡的理发师问题打瞌睡

42、的理发师问题理发师和每位顾客都分别是一个进程 =#define CHAIRS 5typedef struct int value; struct PCB *list; semaphore;semaphore customers=0;semaphore barbers=0;semaphore mutex=1;int waiting=0;2021/3/11116 void barber(void) while(TRUE) P(customers); /*如果没有顾客，则理发师打瞌睡*/ P(mutex); /*互斥进入临界区*/ waiting-; V(barbers); /*一个理发师准备理发*

43、/ V(mutex); /*退出临界区*/ cut_hair(); /*理发（在临界区之外）*/ 打瞌睡的理发师问题打瞌睡的理发师问题2021/3/11117 打瞌睡的理发师问题打瞌睡的理发师问题 void customer(void) P(mutex); /*互斥进入临界区*/ if(waitingCHAIRS) waiting+; V(customers); /*若有必要，唤醒理发师*/ V(mutex); /*退出临界区*/ P(barbers); /*如果理发师正忙着，则顾客打瞌睡*/ get_haircut(); else V(mutex); /*店里人满了，不等了*/2021/3/

44、111182.7 管 程n管程：一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。n由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成。管程的结构2021/3/11119 管 程管程具有以下三个特性：管程具有以下三个特性： 管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问。 进程要想进入管程，必须调用管程内的某个过程。 一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。2021/3/11120 管 程

45、实现互斥是由编译程序完成为解决同步问题，引入两个条件变量x和y： condition x , y;n操作原语wait(x)：挂起等待条件x的调用进程，释放相应的管程，以便供其他进程使用。n操作原语signal(x)：恢复执行先前因在条件x上执行wait而挂起的那个进程。n管程的职责与信号量的职责不同。带条件变量的管程结构 2021/3/111212.8 进 程 通 信n进程通信进程间的信息交换n低级进程通信n高级进程通信 共享存储器方式：在内存中分配一片空间作为共享存储区 消息传递方式：以消息（Message）为单位在进程间进行数据交换 直接通信方式 间接通信方式 管道文件方式：写者向管道文件

46、中写入数据；读者从该文件中读出数据2021/3/111222.8.1 消息传递系统n允许进程彼此进行通信，而不必借助于共享数据n提供两个原语（系统调用 ） send和receive： send (destination, message) receive (source, message)2021/3/11123 消息传递系统 n消息传送系统设计 涉及同步、寻址、格式和排队规则等多项问题 同步 寻址 直接通信方式 对称寻址 ；非对称寻址 间接通信方式 信箱 公用信箱 共享信箱 私有信箱2021/3/11124消息传送系统设计消息格式 取决于消息机制的目标和 在什么系统上运行 排队规则 先进先出

47、 优先权法 接收方挑选一般消息格式 2021/3/11125 消息传递系统用消息传递方式解决生产者-消费者问题 #define N 100 /* 缓冲区个数 */ void producer(void) int item; message m; /* 消息缓冲区 */ while (TRUE) item=produce_item()； /* 生成一些数据放入缓冲区 */ receive(consumer,&m); /* 等待一条空消息到达 */ build_message(&m,item); /* 构造一条可供发送的消息 */ send(consumer,&m);/* 向消费者发送一个数据项

48、*/ void consumer(void) int item,i; message m; for (i=0;iN;i+) send(producer,&m); /* 发送N条空消息 */ while (TRUE) receive(producer,&m); /* 接收一条包含数据的消息 */ item=extract_item(&m); /* 从消息中提取数据项 */ send(producer,&m); /* 发回空消息作为应答 */ consume_item(item); /* 使用数据项进行操作 */ 2021/3/111262.8.2 客户-服务器系统中的通信1socketn好像一条

49、通信线两端的接插口n一对进程通过网络进行通信要用一对socket，每个进程一个。n三个要素： 网络地址表明一个socket用于哪种网络 连接类型表明网络通信所遵循的模式，主要分为“有连接”和“无连接”模式。 网络规程表明具体网络的规程。一般来说，网络地址和连接类型结合在一起就基本上确定了适用的规程。 socket通信流程 2021/3/11127 2远程过程调用n远程过程调用（Remote Procedure Call, RPC）是远程服务的一种最常见的形式。n远程过程调用的思想： 允许程序调用另外机器上的过程n远程过程调用的具体步骤 2021/3/11128第3章 死 锁 2021/3/11

50、129本章内容提要n n资源资源n n死锁概念死锁概念n n死锁的预防死锁的预防n n死锁的避免死锁的避免n n死锁的检测和恢复死锁的检测和恢复n n处理死锁的综合方式处理死锁的综合方式2021/3/111303.1 资源3.1.1 资源使用模式 申请 使用 释放2021/3/111313.1.2 可剥夺资源与不可剥夺资源按占有方式划分：按占有方式划分： 可剥夺资源可剥夺资源 当该资源被某进程拥有后，其它进程仍可以把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。 不可剥夺资源不可剥夺资源 该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则会引起

51、相关计算的失效。如光盘刻录机。 死锁和不可剥夺资源有关 按其它方式划分按其它方式划分2021/3/111323.2 死锁概念 3.2.1 什么是死锁 1死锁示例汽车过窄桥时的冲突在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁 2021/3/11133 2死锁定义n死锁 是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。n计算机系统产生死锁的根本原因就是资源有限且操作不当n死锁的危害 系统瘫痪 资源浪费 2021/3/11134 什么是死锁 有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。 进程A 进程B 申请并占用R

52、 申请并占用S 申请并占用S 申请并占用R 释放R 释放S 释放S 释放R 2021/3/11135 什么是死锁进程推进顺序对引发死锁的影响2021/3/111363.2.2 死锁的条件产生死锁的4个必要条件 1互斥条件 2占有且等待条件 3不可抢占条件 4循环等待条件只要有一个必要条件不满足，则死锁就可以排除。2021/3/111373.2.3 资源分配图1资源分配图的构成n由结对组成： G = (V, E) V是顶点的集合，E是边的集合。 顶点集合可分为两部分： P=p1, p2, , pn 由系统中所有活动进程组成 R=r1, r2, , rm 由系统中全部资源类型组成n有向边pi rj

53、称为申请边 有向边rj pi 称为赋给边n在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。2021/3/111382资源分配图示例（1）集合P, R和E如下： P=p1, p2, p3 R=r1, r2, r3, r4 E=p1r1, p2r3, r1p2, r2p2, r2p1, r3p3（2）资源数量 分别为1，2，1，3（3）进程状态 该图不含环路，没有死锁 资源分配图示例2021/3/111393 3环路与死锁环路与死锁 如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。2021/3/11140 环路与死锁 有死锁的资源分配图有死锁的资源分配图有环路但无死锁的

54、资源分配图有环路但无死锁的资源分配图 如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。 资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。2021/3/111413.2.4 处理死锁的方法利用某些协议预防或避免死锁，保证系统不会进入死锁状态。允许系统进入死锁状态，然后设法发现并克服它。完全忽略这个问题，好像系统中从来也不会出现死锁。2021/3/111423.3 死锁的预防3.3.1 3.3.1 破坏互斥条件破坏互斥条件3.3.2 3.3.2 破坏占有且等待条件破坏占有且等待条件 预分资源策略静态分配 “空手”申请资源策略不占有资源时才可以申请资源 存在以下4

55、个主要缺点 不可预测 利用率低 降低并发性 “饥饿” 现象2021/3/111433.3.3 破坏非抢占条件n隐式抢占方式 n抢占等待者资源2021/3/111443.3.4 破坏循环等待条件资源有序分配策略 资源编号 设R=r1, r2, , rm，表示一组资源 定义一对一的函数F：RN，N是一组自然数。 如：F（磁带机）= 1，F（磁盘机）= 5，F（打印机）= 12 依序分配 约定：所有进程对资源的申请严格按照序号递增的次序进行。2021/3/11145 破坏循环等待条件先弃大，再取小 一个进程申请资源rj，它应释放所有满足F(ri)F(rj) 关系的资源ri 这两种办法都是可行的，都可

56、排除环路等待条件 优点：资源利用率和系统吞吐量都有很大提高缺点：资源请求受限，合理编号困难，增加系统开销。暂不使用的资源也需提前申请，增加资源占用时间。 2021/3/111463.4 死锁的避免排除死锁的动态策略。关键是确定资源分配的安全性 3.4.1 安全状态n在当前分配状态下，进程的安全序列P1, P2, Pn是： 若对于每一个进程Pi（1in），它需要的附加资源可被系统中当前可用资源与所有进程Pj（ ji）当前占有资源之和所满足，则P1, P2, Pn为一个安全序列。 这时系统处于安全状态。存在安全序列时一定不会有死锁发生 死锁是不安全状态中的特例 2021/3/11147 安全状态n

57、 n安全状态示意安全状态示意设系统中共有设系统中共有1010台磁带机，有三个进程台磁带机，有三个进程p p1, 1, p p2 2和和p p3 3，分别拥有，分别拥有3 3台、台、2 2台和台和2 2台磁台磁带机，而它们各自的最大需求分别是带机，而它们各自的最大需求分别是9 9台、台、4 4台和台和7 7台磁带机。此时，系统已分台磁带机。此时，系统已分配了配了7 7台磁带机，还有台磁带机，还有3 3台空闲。下表给出三个进程在不同时刻占有资源及向台空闲。下表给出三个进程在不同时刻占有资源及向前推进的情况。前推进的情况。时 刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P

58、2进程P3T03229473T13429471T2302975T3307970T430097T59001T6000102021/3/11148 不安全状态示意时刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P2进程P3T03229473T14229472T24429470T3402974n若不按照安全序列分配资源，则系统可能会由安全状态转换为不安全状态 2021/3/11149 死锁的避免 死锁状态是不安全状态。 如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。 如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此

59、时资源利用率会下降。2021/3/111503.4.2 资源分配图算法n资源类 单体资源类 多体资源类n单体资源类的资源分配图 除申请边和赋给边之外，还要有一种称为“要求边”的新边。要求边 pi rj表示进程pi能够申请资源rj，有时用虚线表示。资源分配图示例处于不安全状态的资源分配图处于不安全状态的资源分配图2021/3/111513.4.3 银行家算法n“银行家算法”（Bankers Algorithm）针对多体资源类 n设计思想： 当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。2021/3/1115

60、2银行家算法银行家算法数据结构数据结构令n表示系统中进程的数目，m表示资源分类数。 Available是一个长度为m的向量，它表示每类资源可用的数量。Available j=k，表示rj类资源可用的数量是k。 Max是一个nm矩阵，它表示每个进程对资源的最大需求。Maxi, j=k，表示进程pi至多可申请k个rj类资源单位。 Allocation是一个nm矩阵，它表示当前分给每个进程的资源数目。Allocation i, j=k，表示进程pi当前分到k个rj类资源。 Need是一个nm矩阵，它表示每个进程还缺少多少资源。Need i, j=k，表示进程pi尚需k个rj类资源才能完成其任务。 记

61、号：令X和Y表示长度为n的向量 可以把矩阵Allocation和Need中的每一行当做一个向量，并分别写成Allocationi和Needi。Allocationi表示当前分给进程pi的资源。2021/3/111531资源分配算法n令Requesti表示进程pi的申请向量。Requestij= k，表示进程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列动作： 若RequestiNeedi，表示出错， 如果RequestiAvailable，则pi等待。 假设系统把申请的资源分给进程pi，则应对有关数据结构进行修改： Available：= Available Requesti A

62、llocationi：= Allocationi + Requesti Needi：= Needi Requesti 系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程pi 的此次申请；否则，若新状态是不安全的，则pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成之前的情况。2021/3/111542 2安全性算法安全性算法 令Work和Finish分别表示长度为m和n的向量，最初，置Work：= Available，Finishi：=false，i=1, 2, n。 搜寻满足下列条件的i值： Finishi=false，且NeediWork。 若没有

63、找到，则转向。 修改数据值： Work：=Work+ Allocationi（pi释放所占的全部资源） Finishi=true 转向。 若Finishi=true对所有i都成立（任一进程都可能是pi），则系统处于安全状态；否则，系统处于不安全状态。2021/3/111553算法应用示例假定系统中有4个进程A, B, C, D和三类资源R1, R2和R3，各自的数量分别为9, 3和6个单位。进程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420T T0 0时刻

64、资源分配表（时刻资源分配表（安全安全 ）资源情况2021/3/11156（1）T0时刻是安全的 存在一个安全序列B, A, C, D 资源 情况WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723trueC723103211934trueD934420002936true进程T T0 0时刻的安全序列时刻的安全序列2021/3/11157（2）进程A请求资源 进程A发出请求Request（1, 0, 1） 资源情况进 程MaxAllocationNeedAvai

65、lableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系统进入不安全的状态 不能为进程A分配所申请的资源 为进程为进程A A分配资源后的有关数据分配资源后的有关数据2021/3/11158 银行家算法n优点： 限制条件少 资源利用程度提高 n缺点： 难以保证进程数固定不变 未考虑实时进程快速响应 增加了系统开销 2021/3/111593.5 死锁的检测和恢复 死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程

66、从死锁状态中解脱出来。2021/3/111603.5.1 3.5.1 对单体资源类的死锁检测对单体资源类的死锁检测等待图等待图资源分配图的变形资源分配图的变形 从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的资源分配图和对应的等待图2021/3/111613.5.2 对多体资源类的死锁检测采用若干随时间变化的数据结构，与银行家算法相似 Available是一个长度为m的向量 Allocation是一个nm的矩阵 Request是一个nm的矩阵，Requesti, j=k，表示进程pi正申请k个rj类资源 仍把矩阵Allocation和Request的行作为向量对待，并分别表示为A

67、llocationi和Requesti 2021/3/11162 对多体资源类的死锁检测检测算法 简单地调查尚待完成的各个进程所有可能的分配序列 令Work和Finish分别表示长度为m和n的向量，初始化 Work：=Available；对于i=1, 2, n 如果Allocationi0，则Finishi：=false；否则Finishi：=true。 寻找一个下标i，它应满足条件： Finishi=false且RequestiWork 若找不到这样的i，则转到。 修改数据值： Work：=Work+Allocationi Finishi=true 转向。 若存在某些i（1in），Finis

68、hi=false，则系统处于死锁状态。此外，若Finishi=false，则进程pi处于死锁环中。2021/3/11163 对多体资源类的死锁检测n设系统中有5个进程p1, p2, p3, p4和p5，有3类资源R1, R2和R3 ，每类资源的个数分别为7, 2, 6。 AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202p3303000p4211100p5002002死锁检测示例资源分配情况死锁检测示例资源分配情况可以找到序列可以找到序列 p p1 1, , p p3 3, , p p4 4, , p p2 2, ,

69、p p5 5 ，对于所有的，对于所有的i i都有都有FinishFinishi i=true=true，系统在系统在T T0 0时刻没有死锁。时刻没有死锁。资源情况进程2021/3/11164假定，进程p3现在申请一个单位的R3资源AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202000p3303001p4211100p5002002 由于对所有i=1, 2, 5，Allocationi0，所以Finishi=false。 p p3 3申请一个单位的申请一个单位的R R3 3资源后的资源分配数据资源后的资源分配数据资源

70、情况进程2021/3/111653.5.3 从死锁中恢复1通过抢占资源实现恢复 临时性地把资源从当前占有它的进程那里拿过来，分给另外某些进程，直至死锁环路被打破。2通过回退执行实现恢复n由系统管理员做出安排，定期对系统中各个进程进行检查，并将检查点的有关信息（如进程状态、资源状态等）写入文件。n当检测到死锁时，就让某个占有必要资源的进程回退到它取得另外某个资源之前的一个检查点。回退过程所释放的资源分配给一个死锁进程，然后重新启动运行。n系统中应保存一系列检查点的文件。n要确定这个进程后退多远。n还有一种“全体”回退方式2021/3/111663 3通过杀掉进程实现恢复通过杀掉进程实现恢复n终止

71、所有的死锁进程。n一次终止一个进程，直至消除死锁环路。2021/3/111673.5.4 “3.5.4 “饥饿饥饿”状态状态n在某些策略下，系统会出现这样一种情况：在可以预计的时间内，某个或某些进程永远得不到完成工作的机会，因为它们所需的资源总是被别的进程占有或抢占。这种状况称做“饥饿”或者“饿死”（Starvation）。n饥饿不同于死锁2021/3/111683.6 处理死锁的综合方式n把以前介绍的基本方法组合起来，使得系统中各级资源都以最优的方式加以利用。n对待死锁问题除以上三种最基本的方法外，还有第四种方法，即采取“鸵鸟政策” 完全忽略死锁问题。2021/3/11169 操作系统处理死

72、锁的三种方法比较资源分配策略死锁预防死锁避免死锁检测和恢复很保守；对资源不做调配使用介于预防和检测方法之间，安全状态下才分配非常开放；申请资源就分配，但定期检测死锁采用的不同方式一次性分配所有资源抢占式分配资源资源编号，按序分配至少应找出一个安全序列定期调用检测算法，查看是否出现死锁主要优点适用于执行单一突发活动的进程不需要抢占适用于资源状态便于保存和恢复的情况由于系统设计时已解决问题，不需要运行时计算不需要抢占从来不延误进程的开始执行便于联机处理主要缺点效率低延误进程的开始执行抢占动作比实际需要的次数更多易出现环路重启不允许增加对资源的申请必须知道以后对资源的申请情况进程可能被阻塞很长时期丧

73、失固有的抢占性2021/3/11170第4章 调 度2021/3/11171本章内容提要n调度类型 n作业调度 n进程调度 n调度准则 n调度算法 n线程调度n多处理器调度 n实时调度 nUNIX/Linux进程调度 n中断处理 n信号机制 2021/3/111724.1 调 度 类 型n按调度层次进行分类：高级调度、中级调度和低级调度高级调度 又称作业调度或长期调度 中级调度 又称中期调度低级调度 又称进程调度或短期调度 作业三级调度示意图 2021/3/111734.2 作业调度4.2.1 作业状态 提交状态 后备状态 执行状态 完成状态2021/3/111744.2.2 作业控制块和作业

74、调度的功能1作业控制块JCB系统为每个作业设置了一个作业控制块（JCB） 它记录该作业的有关信息JCB是作业在系统中存在的标志 作 业 名XXX资源要求预估的运算时间最迟完成时间要求的内存量要求外设类型、台数要求的文件量和输出量 资源使用情况进入系统时间开始运行时间已经运行时间内存地址外设台号 类型级别控制方式作业类型优先级 状态 后备/执行/完成 2021/3/111752. 作业调度的功能记录系统中各个作业的情况 按照某种调度算法从后备作业队列中挑选作业 为选中的作业分配内存和外设等资源 为选中的作业建立相应的进程，并把该进程放入就绪队列中 作业结束后进行善后处理工作设计目标是最大限度地发

75、挥各种资源的利用率和保持系统内各种活动的充分并行 2021/3/111763常用作业调度算法n先来先服务法（First-Come First-Served）n短作业优先法（Shortest Job First）n最短剩余时间优先法（Shortest Remaining Time Next）2021/3/111774.3 进 程 调 度4.3.1 进程调度的功能（1）保存现场（2）挑选进程（3）恢复现场2021/3/111784.3.2 进程调度的时机 创建进程 进程终止 等待事件 中断发生 运行到时2021/3/111794.3.3 进程调度的基本方式1非抢占方式（Nonpreemptive）

76、2抢占方式（Preemptive）2021/3/111804.3.4 交互式系统中常用的调度算法n轮转法n优先级法n多级队列法n短进程优先法n高响应比优先法n多级反馈队列法n公平共享法等2021/3/111814.3.5 两级调度模型n作业调度是宏观调度n进程调度是微观调度两级调度简化队列图二者的基本区别是它们执行的频率不同2021/3/111824.4 调度准则4.4.1 影响调度算法选择的主要因素 设计目标 公平性 均衡性 统筹兼顾 优先级 开销 2021/3/111834.4.2 调度性能评价准则1CPU利用率2吞吐量3周转时间 周转时间：从作业提交到作业完成的时间间隔 T Ti i=

77、= t tcici t tsisi tsi表示作业i的提交时间，亦即作业i到达系统的时间；tci表示作业i的完成时间 平均周转时间 2021/3/11184 周转时间 带权周转时间W W = T为周转时间，R为实际运行时间平均带权周转时间就绪等待时间 响应时间 2021/3/111854.5 调 度 算 法 4.5.1 4.5.1 先来先服务法先来先服务法 （First Come, First-Served, FCFS） n设有三个作业，编号分别为1, 2, 3。各作业分别对应一个进程。各作业依次到达，相差一个时间单位。先来先服务调度算法示意图2021/3/11186FCFS调度算法性能指标作

78、 业到达时间运行时间开始时间完成时间周转时间带权周转时间102402424 1213242726 8.67323273028 9.33 平均周转时间T=26 平均带权周转时间W=6.33 先来先服务法 比较有利于长作业（进程），而不利于短作业（进程） 容易实现，但效率较低 2021/3/11187n所谓作业的长短是指作业要求运行时间的多少。当分派CPU时，SJF算法就把CPU优先分给最短的作业。n示例： 一组作业同时提交到系统4.5.2 短作业优先法（Shortest-Job-First，SJF） 作 业运行时间16293843表4-2 一组作业列表作业执行顺序2021/3/11188 短作业

79、优先法n采用短作业优先法在实现上有困难。n这种算法的一个缺点是对长作业很不利。短作业优先法执行情况对于一组给定的作业来说，短作业优先法能够提高系统的吞吐量，并能给出最小的平均等待时间。 2021/3/111894.5.3 最短剩余时间优先法（Shortest Remaining Time First, SRTF） n当新进程加入就绪队列时，如果它需要的运行时间比当前运行的进程所需的剩余时间还短，则执行切换。进 程到达时间运行时间108214329435最短剩余时间优先法调度结果进程列表2021/3/111904.5.4 优先级法从就绪队列中选出优先级最高的进程，让它在CPU上运行。 非抢占式优

80、先级法 抢占式优先级法n优先级确定：优先级确定：可由系统内部定义或由外部指定n确定进程优先级的方式静态与动态 静态方式 静态优先级静态优先级是在创建进程时就确定下来的，而且在进程的整个运行期间保持不变。 优先数标示优先级的整数 本书采用“优先数小、优先级高”的表示方式 动态方式 优先级随着进程的推进而不断改变2021/3/11191 优先级法设有如下一组进程，它们都在时刻0到达，依次为p1, p2 , p5，各自的运行时间和优先数如下表所示。进 程运行时间优先数P1103P211P324P415P552优先级调度算法执行顺序2021/3/111924.5.5 轮转法n时间片轮转法（Round-

81、Robin, RR）主要用于分时系统n时间片是一个小的时间单位，通常为10100 ms数量级n示例：4个进程A，B，C和D依次（同时）进入就绪队列，分别需要运行12, 5, 3，6个时间单位 轮转法q=1和q=4时进程运行情况2021/3/11193 轮转法RR调度算法的性能指标到达时间进程名到达时间运行时间开始时间完成时间周转时间带权周转时间时间片q =1A012026262.17B05117173.4C03211113.67D06320203.33平均周转时间T=18.5 平均带权周转时间 W=3.14 时间片q =4A012026262.17B05420204C03811113.67D0

82、61122223.67平均周转时间 T=19.75 平均带权周转时间 W=3.38 2021/3/11194 轮转法进程的周转时间也依赖于时间片的大小。有4个进程p1p4，各自的运行时间分别为6，3，1，7个时间单位 平均周转时间随时间片的变化2021/3/11195 轮转法时间片的长短通常由以下四个因素确定： 系统的响应时间 就绪队列进程的数目 进程的转换时间 CPU运行指令速度2021/3/111964.5.6 多级队列法n多级队列（Multilevel Queue）调度算法 把就绪队列划分成几个单独的队列，永久性地把各个进程分别链入不同的队列中，每个队列都有自己的调度算法。多级队列调度多

83、级队列调度2021/3/111974.5.7 多级反馈队列法多级反馈队列调度算法 系统中设置多个就绪队列，每个队列对应一个优先级。 各就绪队列中进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大。 新进程进入系统后，先放入第1个队列的末尾。 系统先运行第1个队列中的进程这种调度算法基于抢占式，使用动态优先级机制。2021/3/111984.5.8 高响应比优先法n高响应比优先法（Highest Response Ratio First, HRRF）是一种非抢占方式。它为每个进程计算一个响应比RR： w是进程等待处理机所用的时间 s是进程要求的服务时间 事前测量方式 2021/

84、3/111994.5.9 4.5.9 公平共享法公平共享法n系统为每个用户分配一定比例的CPU时间，然后按照这个比例在各用户之间挑选相应的进程。2021/3/112004.5.10 几种常用调度算法的比较n三个量的含义 w 至今在系统中用于等待和执行所花费的时间e 至今在CPU上执行用去的时间。s 进程所需的总体运行时间（包括e）2021/3/11201 比较项目算法FCFSRRSJFSRTFHRRFMFQ选择依据maxw常量minsmins-emax(w+s)/s)见4.5.7节调度方式非抢占式抢占式（按时间片）非抢占式抢占式（进程到达时）非抢占式抢占式（按时间片）吞吐量不突出如果时间片太小

85、，可能变低高高高不突出响应时间可能很高，特别在进程执行时间有很大变化时对于短进程提供良好的响应时间对于短作业（进程）提供良好的响应时间提供良好的响应时间提供良好的响应时间不突出开销最小低可能高可能高可能高可能高的作用不利于短作业（进程）和I/O繁忙型作业（进程）公平对待不利于长作业（进程）不利于长进程良好的均衡可能偏爱I/O繁忙型作业（进程）“饥饿”问题无无可能可能无可能几种常用调度算法的比较几种常用调度算法的比较2021/3/112024.6 线 程 调 度1 1用户级线程用户级线程n核心不负责线程的调度。核心只为进程提供服务，即从就绪队列中挑选一个进程（例如A），为它分配一个时间片，然后由

86、进程A内部的线程调度程序决定让A的哪一个线程（如A1）运行。2核心级线程n由核心调度线程2021/3/11203 线 程 调 度用户级线程可能的调度 核心级线程可能的调度二者主要区别 性能 挂起 2021/3/112044.7 多处理器调度4.7.1 多处理器系统的类型n三种类型（1）松散耦合多处理器系统（或称集群系统）（2）主从多处理器系统（3）紧密耦合多处理器系统2021/3/112054.7.2 多处理器调度方法多处理器调度包括如下三个相关的方面： 给处理器分配进程，即把进程加到某个处理器所对应 的就绪队列中。 在单个处理器上是否使用多道程序技术。 实际分派进程。可以采用转锁（Spin

87、Lock）方式实现互斥多处理器系统中线程调度通常有如下4种方式（1）负载共享 （2）成组调度（3）专用处理器分配 （4）动态调度 2021/3/112064.8 实 时 调 度 4.8.1 实时任务类型n硬实时任务（Hard Real-time Task） 软实时任务（Soft Real-time Task）n周期性任务 非周期性任务n可调度测试公式 系统中有m个周期性任务，其中任务i出现的周期为Pi，处理所需的CPU时间为Ci，那么系统能处理这个任务流的条件是 1 2021/3/112074.8.2 实时调度算法1优先级随速率单调的调度算法优先级随速率单调的调度（Rate Monotonic

88、 Scheduling，RMS）是针对可抢占的周期性进程采用的经典静态实时调度算法 2最早截止时间优先调度算法 最早截止时间优先调度算法（Earliest Deadline First，EDF）是流行的动态实时调度算法 2021/3/112084.9 UNIX/Linux进程调度4.9.1 UNIX进程调度n采用多级反馈队列轮转法 n进程调度时机 调用sleep程序 进程终止 进程从系统调用返回到用户态时，但它并不是最适宜运行的进程 核心处理完中断后，进程回到用户态，但存在更适宜运行的进程 2021/3/11209 UNIX进程调度n进程调度是由swtch程序实现的 swtch( ) whil

89、e（没有进程被选中执行） for （所有在就绪队列中的进程） 选出优先级最高且在内存的一个进程； if（没有合适进程可以执行） 机器作空转； /*当中断发生后，使机器摆脱空转状态*/ 从就绪队列中移走该选中进程； 恢复选中进程的现场，令其投入运行；2021/3/11210 UNIX进程调度进程优先级的级别示意图 用户优先级类和核心优先级类 2021/3/112114.9.2 Linux进程调度调度方式抢占式优先级调度策略三种不同的调度策略 SCHED_FIFO适合于短实时进程 SCHED_RR对应“时间片轮转法”，适合于每次运行需要较长时间的实时进程。 SCHED_OTHER是传统的UNIX调

90、度策略，适合于交互式的分时进程。 系统中规定，实时进程的优先级高于其他类型进程的优先级。另外，时间配额及nice值不影响实时进程的优先级。2021/3/11212 Linux进程调度调度时机 当前进程调用系统调用nanosleep( )或pause( ) 进程终止 在时钟中断处理程序执行过程中，发现当前进程连续运行的时间过长 当唤醒一个睡眠进程 一个进程通过执行系统调用来改变调度策略或者降低自身的优先级调度算法 比较简单。基本上继承了UNIX的以优先级为基础的调度 2021/3/112134.10 中 断 处 理4.10.1 中断概述 1中断的概念 中断 中断源 中断请求 断点 2中断系统的作

91、用 提高主机的利用率 及时进行事故处理 实现分时操作 实现实时操作 方便程序调试中断概念示意图 2021/3/11214 中断概述3中断类型n按中断事件来源划分中断 中断由CPU以外的事件引起 异常（Exception）来自CPU内部的事件或程序执行中的事件引起的过程 出错 陷入 2021/3/112154.10.2 中断的处理过程 1中断的硬件结构硬件级的中断结构与过程 2021/3/112162中断响应n中断响应由硬件实施 中止当前程序的执行； 保存原程序的断点信息（主要是程序计数器PC和程序状态寄存器PS的内容）； 转到相应的处理程序。 中断向量 示意性中断向量表中中 断断 号号中断中断

92、处理程序理程序中中 断断 号号中断中断处理程序理程序0 clockintr3 devintr1 diskintr4 softintr2 ttyintr5 otherintr2021/3/112173中断处理n中断处理由软件（中断处理程序）进行相应处理n中断处理过程 保存被中断程序的现场 集中式保存 分散式保存 分析中断原因 转入相应处理程序进行处理 恢复被中断程序现场（即中断返回） 选取可以立即执行的进程 恢复工作现场2021/3/11218中断处理的一般过程 中断处理 2021/3/112194.10.3 中断优先级和多重中断1中断优先级 中断级 中断优先级 2中断屏蔽n中断屏蔽和中断禁止

93、n中断屏蔽的作用 延迟或禁止对某些中断的响应 协调中断响应与中断处理的关系 防止同类中断的相互干扰n中断屏蔽的方式 2021/3/112203多重中断 n顺序处理方式n嵌套处理方式 多重中断的控制转移 2021/3/112214.11 信号机制4.11.1 信号机制概念 1信号的概念利用信号机制实现进程间通信的过程 2021/3/112222信号与中断机制的异同n信号机制与中断机制的相似之处 二者在概念上是一致的 二者都是“异步”的 二者在实现上都采用“向量表”的方式 都有屏蔽的手段n信号机制与中断机制的差别 实现机制 向量表和处理程序所在空间 检测和响应 的时机 2021/3/112234.

94、11.2 信号的分类、产生和传送1信号分类信 号 号 码符 号 表 示含 义1SIGHUP进程被挂起2SIGINT用户在键盘上按下Delete键或Ctrl+C3SIGQUIT用户在键盘上按下Quit(Ctrl+)键4SIGILL非法指令5SIGTRAP断点或跟踪指令6SIGIOTIOT指令7SIGEMTEMT指令8SIGEPE浮点运算溢出9SIGKILL要求终止该进程10SIGBUS总线超时11SIGSEGV段违例12SIGSYS系统调用错13SIGPIPEpipe文件只有写进程，没有读进程14SIGALRM报警信号15SIGTERM软件终止信号16SIGUSER1用户定义信号117SIGUS

95、ER2用户定义信号218SIGCLD子进程终止19SIGPWR电源故障UNIX S_5的信号分类及其含义 2021/3/112242信号的产生和传送有关信号的内部结构 2021/3/112254.11.3 信号的处理方式u_signali的值信号的处理方式零进程终止自己非零奇数忽略该信号非零偶数其值为用户空间处理程序的入口地址2021/3/112264.11.4 信号的检测和处理 n检测信号的时机n信号处理 信号的检测与处理流程图 2021/3/11227 第5章 存储管理2021/3/11228本章内容提要引言分区法分页技术分段技术段页式技术虚拟存储器请求分页技术页面置换算法内存块的分配和抖

96、动问题请求分段技术 Linux系统的存储管理2021/3/112295.1 引 言n内存（Main Memory或Primary Memory或Real Memory）也称主存，是指CPU能直接存取指令和数据的存储器。内存在计算机系统中的地位5.1.1 用户程序的地址空间2021/3/11230 用户程序的主要处理阶段主要处理阶段 编辑 编译 连接 装入 运行有关概念 装入程序 相对地址或逻辑地址 绝对地址或物理地址 程序装入内存的方式 绝对装入方式 可重定位装入方式 动态运行时装入方式 2021/3/112315.1.2 重定位n逻辑地址空间（简称地址空间） 由程序中逻辑地址组成的地址范围n

97、内存空间（也称物理空间或绝对空间） 由内存中一系列存储单元所限定的地址范围n重定位 程序和数据装入内存时，需对目标程序中的地址进行修改。这种把逻辑地址转变为内存物理地址的过程称作重定位n重定位方式 静态重定位 动态重定位2021/3/112321静态重定位 目标程序装入内存时进行地址变换 程序装入内存时的情况 静态重定位示意图 优点 :无需增加硬件地址转换机构 主要缺点 :位置“钉死”；不便共享2021/3/112332动态重定位 程序执行期间进行重定位动态重定位示意图主要优点：位置可变，不必连续 ；易于共享 主要缺点 ：需要附加硬件支持 ；软件算法比较复杂 2021/3/112345.1.3

98、 对换技术对换两个进程示意图 多道程序对换技术示例 2021/3/112355.2 分区法n分区分配是为支持多道程序运行而设计的一种最简单的存储管理方式。5.2.1 固定分区法n分区个数固定不变，大小固定不变n划分分区方式： 等分方式 差分方式 2021/3/11236 固定分区法 固定分区管理示意图 分区说明表 优点：管理方式简单，所需操作系统软件和处理开销都小缺点 ：内存空间利用率不高，碎片严重； 活动进程数目受限； 无法预知所需内存大小 2021/3/112375.2.2 动态分区法1分区的分配MVT的内存分配和进程调度情况 操作系统内部设置一个 内存登记表 2021/3/11238 动

99、态分区法2数据结构常用的数据结构形式： （1）空闲分区表（2）空闲分区链n使用链指针把所有的空闲分区链接成一条链 2021/3/112393分配算法（1）最先适应算法n空闲表是按地址地址排列的（即空闲块地址小的，在表中的序号也小）。（2）最佳适应算法n空闲表是以空闲分区的大小为序、按增量形式排列的，即小块在前，大块在后。（3）循环适应算法n最先适应算法的变种。它不从空闲表的开头查找，而从上次找到的可用分区的下一个空闲分区开始查找，从中选择满足大小要求的第一个空闲分区。 2021/3/11240 分配算法三种算法分配16KB空闲分区之前和之后的内存配置情况 2021/3/112414. 碎片问题

100、n“碎片”或“零头”： 内存中这种容量太小、无法利用的小分区n内部碎片： 在一个分区内部出现的碎片（即被浪费的空间），如固定分区法会产生内部碎片。n外部碎片： 在所有分区之外新增的碎片2021/3/112425.2.3 可重定位分区分配1紧缩n紧缩（或拼凑） n可重定位分区法n紧缩时机释放所占分区时分配进程分区时 可重定位分区的紧缩示意图 2021/3/112432动态重定位的实现过程n动态重定位经常用硬件实现n硬件支持 基址寄存器 限长寄存器动态重定位的实现过程 2021/3/112443. 可重定位分区法的优缺点优点： 可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率

101、。缺点： 紧缩花费了大量CPU时间 当进程大于整个空闲区时，仍要浪费一定的内存 进程的存储区内可能放有从未使用的信息 进程之间无法对信息共享2021/3/112455.3 分页技术5.3.1 分页存储管理的基本概念（1）逻辑空间分页（2）内存空间分块 内存块或页框（3）逻辑地址表示分页技术的地址结构示意图 给定的逻辑地址是A，页面的大小为L，则页号p和页内地址d可按下式求得 p = INT(A/L) , d = A MOD L式中，INT是向下整除的函数，MOD是取余函数。 2021/3/11246 分页存储管理的基本概念（4）内存分配原则以块为单位 每个页面对应一个内存块 内存块可不连续分页

102、存储管理系统示意图 2021/3/11247（5）页表实现从页号到物理块号的地址映射分页存储管理的基本概念2021/3/11248（6）内存块表n整个系统有一个内存块表。每个内存块在内存块表中占一项，表明该块当前空闲还是已分出去了。分页存储管理的基本概念2021/3/112495.3.2 分页系统中的地址映射分页系统的地址转换机构每个进程平均有半个页面的内部碎片每个进程平均有半个页面的内部碎片2021/3/112505.3.3 页面尺寸折中方案设进程的平均大小为s字节，页面尺寸为p字节，每个页表项占e字节。那么，每个进程需要的页数大约为s/p， 占用 s . e /p 字节的页表空间。每个进程

103、的内部碎片平均为p/2。因此，由页表和内部碎片带来的总开销是：总开销= 2021/3/112515.3.4 硬件支持n由硬件实现页表的方式有多种，最简单的方式是由一组专门的寄存器来实现。 n通常将页表保存在内存中，由一个页表基址寄存器PTBR指向该页表。整个系统只有一个PTBR。 带来存取速度下降的矛盾n联想存储器，也称快表（或Translation Lookaside Buffer, TLB）。快表每项包括键号和值两部分，键号是当前进程正在使用的某个页面号，值是该页面所对应的物理块号。2021/3/11252利用快表实现地址转换示例 硬件支持命中率 在快表中成功找到指定页号的次数占总搜索次数

104、的百分比 2021/3/112535.3.5 保护方式（1）利用页表本身进行保护（2）设置存取控制位（3）设置合法标志2021/3/112545.3.6 页表的构造1多级页表大多数现代计算机系统都支持非常大的逻辑地址空间，如232 264。在这种情况下，只用一级页表会使页表变得非常大。n一种方法是利用两级页表，即把页表本身也分页。 两级页表地址结构示意图 2021/3/11255两级页表结构示意图 多级页表2021/3/11256两级页表结构的地址转换多级页表2021/3/11257三级页表地址结构示意图 多级页表 2散列页表（Hashed Page Table）以页号作为参数形成散列值。散列

105、表中每一项有一个链表，它把有相同散列值的元素链接起来。每个链表元素由三部分组成： 页号 对应的内存块号 指向链表中下一个元素的指针2021/3/11258 散列页表散列页表构成及地址转换过程 2021/3/112593倒置页表n它是按内存块号排序的，每个内存块占有一个表项。每个表项包括存放在该内存块中页面的虚拟页号和拥有该页面的进程标识符。倒置页表构成及地址转换过程 2021/3/112605.3.7 页面共享可可再再入入代代码码（或或纯纯码码）：在在其其执执行行过过程程中中本本身身不不做做任任何何修修改改的的代代码码，通通常常由指令和常数组成由指令和常数组成三个进程共享大小为三个页面的编辑器

106、的情况，每个进程都有自己的私有数据页。 页面共享示例 2021/3/112615.4 分段技术5.4.1 分段存储管理的基本概念分段地址空间1分段分段段是一组逻辑信息的集合。每段都有自己的名字、长度。段号2021/3/112622程序的地址结构n逻辑地址要用两个成分来表示： 段号s和段内地址d 进程的逻辑地址空间是二维的分段技术地址结构示意图 2021/3/112633内存分配n内存以段为单位进行分配，每段单独占用一块连续的内存分区。各分区的大小由对应段的大小决定。4段表和段表地址寄存器n系统为每个进程建立一个段映射表，简称“段表”。每个段在段表中占有一项，段表项中包含段号、段长和段起始地址（

107、又称“基址”）等。n系统还要建立一个段表地址寄存器。它有两部分： 该段表在内存的起始地址 该段表的长度。2021/3/112645分页和分段的主要区别 页是信息的物理单位 段是信息的逻辑单位 页的大小是由系统确定的 段的长度因段而异 分页的进程地址空间是一维的 分段的进程地址空间是二维的 分页系统很难实现过程和数据的分离 分段系统却可以很容易实现这些功能2021/3/112655.4.2 地址转换分段地址转换过程 2021/3/112665.4.3 段的共享和保护1段的共享n共享是在段一级实现的，任何共享信息可以单独成为一段。n也可以只共享部分程序。分段系统中段的共享 2021/3/11267

108、2段的保护n段的保护措施包括以下三种： 存取控制 段表本身可起保护作用 表项中设置该段的长度限制 段长 段表地址寄存器中有段表长度的信息 保护环 2021/3/112685.5 段页式技术5.5.1 段页式存储管理的基本原理 等分内存 地址空间分段 段内分页 逻辑地址结构 内存分配 段表、页表和 段表地址寄存器 段页式存储逻辑地址结构示意图 2021/3/112695.5.2 地址转换过程段页式系统的地址转换机构 2021/3/112705.6 虚拟存储器5.6.1 虚拟存储器的概念n进程在执行之前要全部装入内存，这种限制是不合理的。 程序中往往含有不会被执行的代码 分配的内存空间会大于它们的

109、实际需要 一个程序的某些选项和特性可能很少使用n程序的执行过程也显示出局部性n按需分别调入内存会带来两点好处： 用户编制程序时不必考虑内存容量的限制 在一定容量的内存中就可同时装入更多的进程2021/3/11271n虚拟存储器（Virtual Memory） 用户能作为可编址内存对待的虚拟存储空间，它使用户逻辑存储器 与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址空间。n实现虚拟存储技术的物质基础 二级存储器结构 动态地址转换机构（DAT）n虚拟存储器实质上是把用户地址空间和实际的存储空间区分开来。n它主要受到两方面的限制： 指令中表示地址的字长 外存的容量虚拟存储器的

110、概念2021/3/112725.6.2 虚拟存储器的特征 虚拟扩充 部分装入 离散分配 多次对换 2021/3/112735.7 请求分页技术5.7.1 请求分页存储管理的基本思想n是在单纯分页技术基础上发展起来的n二者的根本区别在于请求分页提供虚拟存储器。n基本思想是： 当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入内存。n为了标示进程的页面是否已在内存，在每个页表项中增加一个标志位。 2021/3/112745.7.2 硬件支持及缺页处理1页表机制n页表项通常包含下列5种信息：典型的页表表项示意图 2021/3/112752缺页中断机构指令

111、执行步骤与缺页中断处理过程 2021/3/112765.7.3 请求分页技术的性能n缺页率p：表示缺页中断的概率（0p1） 等于缺页次数与全部访问内存次数之比n有效存取时间可表示为： 有效存取时间= (1-p)ma + p缺页处理时间2021/3/11277n缺页导致以下一系列动作（设当前进程为A）： 捕俘进入操作系统 保存进程A的各个寄存器和进程状态信息 确定该中断是缺页引起的 检查对该页的访问是合法的，并确定该页在磁盘上的地址 把该页从盘上读到空闲内存块中，其中包括在设备队列中等待，直至该请求得到服务；等待盘寻道以及潜在时间；把该页传送到空闲内存块。 在等待盘I/O完成时，把CPU分给其他

112、进程（如进程B） 盘I/O完成，发出盘中断 保存进程B的用户寄存器和进程状态 确定该中断来自磁盘 调整页表和其他表格，标明所需页已放入内存 进程A就绪，等待分配CPU 调度到进程A，则恢复它的各寄存器、进程状态和新的页表，然后重新执行前面被中断的指令。请求分页技术的性能2021/3/11278n缺页中断处理所花费的时间主要有以下三部分： 处理缺页中断的时间 调入该页的时间 重新启动该进程的时间n将页面从盘上读到内存所花费的时间包括： 磁盘寻道时间（即磁头从当前磁道移至指定磁道所用的时间） 旋转延迟时间（即磁头从当前位置落到指定扇区开头所用的时间） 数据传输时间 典型磁盘的旋转延迟时间约为8 m

113、s，寻道时间约为15 ms，传输时间是1 ms。 请求分页技术的性能2021/3/112795.8 页面置换算法5.8.1 页面置换1页面置换过程页面置换过程 2021/3/112802页面走向n抖动 频繁地更换页面,以致系统的大部分时间花费在页面的调度和传输上。 n尽量避免系统“抖动” n存储访问序列也叫页面走向 对于给定的页面大小，仅考虑其页号，不关心完整的地址。 如果当前对页面p进行了访问，那么，马上又对该页访问就不会缺页。这样连续出现的同一页号就简化为一个页号。 如下地址序列（用十进制数表示）： 0100，0432，0101，0612，0102，0103，0104，0101，0611，

114、0102， 0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105 若每页100个字节，则页面走向简化为： 1，4，1，6，1，6，1，6，1，6，12021/3/11281n一般来说，随着可用块数的增加，缺页数将减少。缺页量与内存块数关系图统一采用下述页面走向： 7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1 并且假定每个作业只有三个内存块可供使用。页面走向2021/3/112825.8.2 先进先出法（FIFO）n总是淘汰在内

115、存中停留时间最长（年龄最老）的一页，即先进入内存的页，先被换出。FIFO页面置换序列 总共有15次缺页 2021/3/11283n优点：容易理解，方便程序设计。n缺点： 性能并不很好，效率不高 存在Belady异常现象，即缺页率随内存块增加而增加关于一个页面走向的FIFO淘汰算法的缺页曲线先进先出（FIFO）法 2021/3/112845.8.3 最佳置换法（OPT）n最佳置换算法（Optimal Replacement, OPT）其实质是：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。 保证有最小缺页率 OPT算法在实现上有困难最佳页面置

116、换序列 仅出现9次缺页中断 2021/3/112855.8.4 最近最少使用置换法（LRU）n以“最近的过去”作为“不久将来”的近似n实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。最近最少使用算法页面置换序列 产生12次缺页 2021/3/11286LRU算法需要实际硬件的支持。实现时的问题是：怎样确定最后访问以来所经历时间的顺序。有以下两种可行的办法： 计数器 栈最近最少使用置换法利用栈记录目前访问最多的页面示例 2021/3/112875.8.5 第二次机会置换法（SCR）n第二次机会置换法（Second Chance Page Replacement, SC

117、R）是对FIFO算法的改进 避免把经常使用的页面置换出去。n当选择某一页面置换时，就检查最老页面的引用位：如果是0，就立即淘汰该页；如果该引用位是1，就给它第二次机会。第二次机会法示例 2021/3/112885.8.6 时钟置换法（Clock）简单时钟置换法该算法又称最近未使用置换法（Not Recently Used, NRU）改进的时钟置换法 在页表项中设置两个状态位： 引用位和修改位 时钟置换法示意图 2021/3/112895.8.7 最少使用置换法（LFU） n最少使用（Least Frequently Used，LFU）页面置换算法是基于访问计数的页面置换法。n为每个页面设置一个

118、软件计数器n将每页的引用位R的值加到对应的计数器上。发生缺页时，淘汰其计数值最小的页。n老化（Aging）算法2021/3/112905.8.8 页面缓冲算法 n页面缓冲算法（Page Buffering）是对FIFO简单置换算法的改进。该算法维护两个链表：一个是空闲页链表，另一个是修改页链表。 n当发生缺页时，按照FIFO算法选取一个淘汰页，并不是抛弃它，而是把它放入两个链表中的一个。如果该页未被修改，就放入空闲页链表中；否则，把它放入修改页链表中。n驻留集：进程在内存映像的集合 2021/3/112915.9 内存块的分配和抖动问题5.9.1 内存块的分配 1最少内存块数n分给每个进程的最

119、少内存块数是指保证进程正常运行所需的最少内存块数，它是由指令集结构决定的。 2内存块的分配 固定分配策略分配给进程的内存块数是固定的，且在最初装入时（即进程创建时）确定块数。 可变分配策略允许分给进程的内存块数随进程的活动而改变。2021/3/11292页面置换范围 全局置换允许一个进程从全体存储块的集合中选取淘汰块，尽管该块当前分配给其他进程，还是能强行占用。 局部置换是每个进程只能从分给它的一组内存块中选择淘汰块。局部置换可与固定分配策略相结合局部置换可与可变分配策略相结合 全局置换只能与可变分配策略相结合 内存块的分配2021/3/112933分配算法（1）等分法内存块按进程平分 （2）

120、比例法 设进程pi的地址空间大小为si，则总地址空间为 S=si 若可用块的总数是m，则分给进程pi的块数是 ai m . si /S（3）优先权法给高优先级进程分配较多内存 2021/3/112945.9.2 抖动问题n整个系统的页面替换非常频繁，以致大部分机器时间都用在来回进行的页面调度上，只有一小部分时间用于进程的实际运算。这种局面称为系统“抖动（Thrashing）”。1产生抖动的原因内存 不足多道程序度高CPU的利用率太低 CPU利用率与多道程序度之间的关系2021/3/112952防止抖动的方法 采用局部置换策略 利用工作集策略防止抖动 挂起某些进程 采用缺页频度法（Page Fa

121、ult Frequency, PFF）缺页频度的上限和下限 2021/3/112963工作集 测试表明，虚拟存储系统的有效操作依赖于程序中访问的局部化程度。 （1）局部性模型n时间局部化是指一旦某条指令或数据被访问过，它往往很快又被再次访问。n空间局部化是指一旦某个位置被访问过，它附近的位置也可能很快要用到。（2）工作集模型n工作集，就是一个进程在某一小段时间内访问页面的集合。工作集模型 2021/3/11297存储访问的局部性工作集 2021/3/11298工作集依赖于程序的行为，并且其大小与的取值有关。 每个进程的工作集大小为WSSi，那么工作集 D就是系统中全部（n个）进程对内存块的总请

122、求量。如果请求值D大于可用内存块的总量m(Dm)，将出现抖动。4工作集页面置换法 基本思想是找出一个不在工作集中的页面，把它淘汰。 工作集页面置换算法的工作过程 2021/3/112995.10 请求分段技术5.10.1 请求分段存储管理的硬件支持n各段表项中要增加一位，以表明该段的存在状态。n还要增加另外一些控制位,如： 修改位 保护位 共享位2021/3/113005.10.2 动态链接和链接中断处理1动态链接n动态链接： 仅当用到某个分段时才对它进行链接，从而避免不必要的链接。n间接编址 n间接字 n链接故障指示位 直接编址与间接编址示意图 2021/3/113012链接中断处理段的动态

123、链接示意图 2021/3/113025.11 Linux系统的存储管理5.11.1 Linux的多级页表结构Linux进程的虚拟存储空间2021/3/11303LinuxLinux系统采用三级页表的方式系统采用三级页表的方式对于i386来说，CPU只支持两级模型。Linux的多级页表结构2021/3/113045.11.2 内存页的分配与释放空闲内存的组织示意图 Linux系统采用位图和链表两种方法来管理内存页 2021/3/113055.11.3 内存交换n由内核的交换守护进程kswapd完成内存交换 为页面换出做好准备 写入交换设备或者回收一些内存页n为了决定是否回收一些内存页，系统设置两

124、个量，分别表示上限值和下限值。 n交换守护进程将用以下三种办法减少系统正在使用的内存页数： 减少缓冲区和页高速缓存的大小。 把共享内存页换到交换文件，从而释放物理内存。 将页面换出物理内存或者直接将它们抛弃。 2021/3/11306 第6章 文 件 系 统 2021/3/11307本章内容提要本章内容提要n概述n文件系统的功能和结构n目录结构和目录查询n文件和目录操作n文件系统的实现n管道文件n文件系统的可靠性2021/3/113086.1 概述6.1.1 文件及其分类 1文件n通常存放在外存（如磁盘、磁带）上，可以作为一个独立单位存放和实施相应的操作（如打开、关闭、读、写等）。 2文件类型

125、 文件分类方法 （1）按用途分类 系统文件 库文件 用户文件2021/3/11309（2）按文件中的数据形式分类 源文件 目标文件 可执行文件（3）按存取权限分类 只读文件 读写文件 可执行文件（3）按存取权限分类 只读文件 读写文件 可执行文件（4）按保存时间分类 临时文件 永久文件文件类型2021/3/11310（5）在UNIX/Linux和MS-DOS系统中，按文件的内部构造和处理方式分类 普通文件 由表示程序、数据或文本的字符串构成，内部没有固定的结构。 目录文件 由下属文件的目录项构成的文件。 特别文件 特指各种外部设备。 特别文件分为字符特别文件和块特别文件。 普通文件通常分为AS

126、CII文件和二进制文件。 ASCII文件由只包含ASCII字符的正文行组成，每个正文行以回车符或换行符终止，各行的长度可以不同。ASCII文件又称文本文件。 二进制文件所包含的每个字节可能有256(28)种值。 通常可执行的二进制文件都有内部结构。 存档文件是二进制文件的另一示例。文件类型2021/3/11311文件类型 可执行文件和存档文件内部结构示意图 2021/3/113126.1.2 6.1.2 文件命名文件命名n用户对文件也是“按名存取”的。n不同系统对文件的命名规则是不同的。n很多操作系统支持的文件名都由两部分构成：文件名和扩展名，二者间用圆点分开。2021/3/11313常见文件

127、扩展名及其含义扩 展 名文 件 类 型含 义exe，com，bin可执行文件可以运行的机器语言程序obj，o 目标文件编译过的、尚未连接的机器语言程序c，cc，java，pas，asm，a源文件用各种语言编写的源代码bat，sh批文件由命令解释程序处理的命令txt，doc文本文件文本数据、文档wp，tex，rrf，doc字处理文档文件各种字处理器格式的文件lib，a，so，dll库文件供程序员使用的例程库arc，zip，tar打印或视图文件以打印或可视格式保存的ASCI I码文件或二进制文件arc，zip，tar存档文件相关文件组成一个文件（有时压缩）进行存档或存储mpeg，mov，rm多媒体

128、文件包含声音或A/V信息的二进制文件6.1.2 文件命名2021/3/113146.1.3 文件属性n文件属性:描述文件特征的属性 可能用到的文件属性属 性含 义属 性含 义保护谁能访问该文件，以何种方式访问临时标志0表示正常，1表示进程结束时删除文件口令访问该文件所需口令锁标志0表示开锁，非0表示上锁创建者文件创建者的标识记录长度一个记录的字节数文件主当前文件主关键字位置每个记录中关键字偏移只读标志0表示读/写，1表示只读关键字长度关键字字段中字节数隐藏标志0表示正常，1表示不在列表中显示创建时间创建文件的日期和时间系统标志0表示一般文件，1表示系统文件最后存取时间最后存取文件的日期和时间存

129、档标志0表示已经后备，1表示需要后备最后修改时间最后修改文件的日期和时间ASCI I/二进制标志0表示ASCI I文件，1表示二进制文件当前长度文件字节数随机存取标志0表示只能顺序存取，1表示随机存取最大长度文件允许最大字节数2021/3/113156.1.4 文件存取方法1顺序存取方法顺序存取定长记录文件示意图 对定长记录文件，有 rpi+1= rpi + l2021/3/11316n对变长记录文件 rpi+1= rpi + li li是第i个记录的长度。顺序存取变长记录文件示意图 顺序存取方法2021/3/113172随机存取方法n随机存取文件方式允许以任意顺序读取文件中的字节或记录。随机

130、存取定长记录文件示意图 随机存取文件方式允许以任意顺序读取文件中的字节或记录 先要设置读/写指针的当前位置 随机方式下读/写文件等操作都以块号为参数 2021/3/113183其他存取方法n通常采用索引表组织方式直接存取变长记录文件的索引表结构对于大型文件，建立二级索引，即主索引文件包含的项是指向次索引文件 的指针，次索引文件包含的项才是指向实际数据项的指针。 2021/3/113196.1.5 文件结构1无结构文件 无结构文件是指文件内部不再划分记录，是由一组相关信息组成的有序字符流，即流式文件。三种文件结构示意图 2021/3/113202有结构文件 有结构文件又称记录式文件。它在逻辑上可

131、被看成一组连续记录的集合，即文件是由若干相关记录组成，且对每个记录编上号码 定长记录文件。 变长记录文件。3树形文件 这种结构的文件由一棵记录树构成，各个记录的长度可以不同。2021/3/113216.2 文件系统的功能和结构6.2.1 文件系统的功能n文件管理系统，简称文件系统。n操作系统中负责操纵和管理文件的一整套设施，它实现文件的共享和保护，方便用户“按名存取”。 n一般来说，文件系统应具备以下5种功能： 文件管理。 目录管理。 文件存储空间管理。 文件的共享和保护。 提供方便的接口。 看待文件系统有不同的观点，主要是用户观点（即外部使用观点）和系统观点（即内部设计观点）。 2021/3

132、/113226.2.2 文件系统的结构文件系统的层次结构2021/3/113236.3.1 文件控制块和文件目录1文件控制块n在文件系统内部，给每个文件惟一地设置一个文件控制块。n通常由下列信息项组成： 文件名 文件类型 位置 大小 保护信息 使用计数 时间6.3 目录结构和目录查询2021/3/113242文件目录n为了加快对文件的检索，往往将文件控制块集中在一起进行管理。这种文件控制块的有序集合称为文件目录。文件控制块就是其中的目录项。完全由目录项构成的文件称为目录文件。MS-DOS目录项示意图 UNIX目录项示意图 2021/3/113256.3.2 单级目录结构n在这种组织方式下，全部

133、文件都登记在同一目录中。单级目录结构示意图 优点：简单，能够实现按名存取。缺点： 查找速度慢 不允许重名 不便于共享 2021/3/113266.3.3 二级目录结构二级目录结构示意图 优点：不同用户可有相同的文件名； 提高了检索目录的速度； 不同用户可用不同的文件名访问系统中同一文件。缺点: 这种结构仍不利于文件共享。2021/3/113276.3.4 树形目录结构1树形目录 从根目录开始，一层一层地扩展下去，形成一个树形层次结构，每个目录的直接上一级目录称做该目录的父目录，而它的直接下一级目录称做子目录。树形目录结构示意图 2021/3/113282路径名 绝对路径名 又称全路径名，是指从

134、根目录开始到达所要查找文件的路径名。 ( root )/usr/ml/prog/f1.c 相对路径名 当前目录（又称工作目录） 主目录 绝对路径名从根目录开始书写，如： /usr/ml/prog/f1.c 相对路径名是从当前目录的下级开始书写，如当前目录是/usr/ml，则有： prog/f1.c 文件的层次和隶属关系很清晰，便于实现不同级别的存取保护和文件系统的动态装卸。 但是，在上述纯树形目录结构中，只能在用户级对文件进行临时共享。2021/3/113296.3.5 非循环图目录结构n它允许一个文件或目录在多个父目录中占有项目，但并不构成环路。n这种结构方式叫做链接（Link）。n文件共享

135、通过两种链接方式实现：允许目录项链接到任一表示文件目录的节点上；只允许链接到表示普通文件的叶节点上。 非循环图目录结构示意图 2021/3/113306.3.6 目录查询方法 1线性检索法 又称顺序检索法 线性检索法简单易行，但是速度慢。2散列法 散列法需要有目录文件和散列表，每个散列值是由文件名计算出来的，并且散列表项中有指向线性表中文件名的指针。这种方法利用线性表存放目录项（与线性法相同），利用散列数据结构进行检索。 简便，减少了目录查询时间 需要预防冲突问题 即两个文件名有相同的散列值。 主要困难是它有固定的大小，并且散列函数也依赖该大小。 2021/3/113316.4.1 文件操作

136、1创建文件create 2删除文件delete 3打开文件open 4关闭文件close 5读文件read 6写文件write 7附加文件append 8读写定位seek 9取文件属性get_attributes 10置文件属性set_attributes 11重新命名文件rename6.4 文件和目录操作2021/3/113326.4.2 目录操作 1创建目录create 2删除目录delete 3打开目录opendir 4关闭目录closedir 5读目录readdir 6重新命名目录rename 7链接文件link 8解除链接unlink2021/3/113336.5 文件系统的实现6.

137、5.1 文件系统的格式 1文件系统的不同含义 功能定义：在操作系统内部（通常在内核中）用来对文件进行控制和管理的一套机制及其实现。 具体实现和应用：文件系统指存储介质按照一种特定的文件格式加以构造。 2文件系统的格式 硬盘分区 通过对硬盘分区，多个操作系统可以共存于同一个硬盘中。 当系统中硬盘容量较大时，使用分区可以提高硬盘的访问效率。 在不同分区上安装不同的操作系统，能够方便管理和维护。2021/3/11334一般文件系统格式 一般文件系统格式示意图 2021/3/113356.5.2 文件存储分配n文件的物理组织涉及一个文件在存储设备上是如何放置的。它和文件的存取方法有密切关系，另外也取决

138、于存储设备的物理特性。n文件的存储分配涉及以下三个问题： 当创建新文件时，是否一次性为该文件分配所需的最大空间？ 为文件分配的空间可以是一个或多个连续的单位。 分配文件空间时应采用的单位有多大？ 为了记录分配给各个文件的连续单位的情况，应该使用哪种形式的数据结构或表格？2021/3/113361连续分配文件连续分配示意图 2021/3/11337n采用连续分配方法可把逻辑文件中的信息顺序地存放到一组邻接的物理盘块中，这样形成的物理文件称为连续文件（或顺序文件）。 优点：在顺序存取时速度较快，一次可以存取多个盘块，改进了I/O性能；也很容易直接存取文件中的任意一块。 缺点： 要求建立文件时就确定

139、它的长度，依此来分配相应的存储空间，这往往很难实现。 它不便于文件的动态扩充。 可能出现外部碎片。实现连续盘块分配的策略 最先适应算法 最佳适应算法 最近适应算法连续分配 2021/3/113382链接分配n把一个逻辑上连续的文件分散存放在不同的物理块中，这些物理块不要求连续，也不必规则排列。 文件链接分配示意图 2021/3/11339n这种物理结构形式的文件称做链接文件或串连文件。n采用链接分配不会产生磁盘的外部碎片n文件可以动态增长n不需要紧缩磁盘空间n带来以下三个新的问题： 一般仅适于对信息的顺序访问，而不利于对文件的随机存取。 每个物理块上增加一个链接字 可靠性链接分配 2021/3

140、/11340nFAT表出现在每个磁盘分区开头的扇区中，每个盘块在表中占一项。每个盘块在表中占一项，表的序号是物理盘块号，每个表项中存放链接下一盘块的指针。这样，FAT表就被用做链表。 链接分配文件分配表（FAT）示意图 2021/3/113413索引分配除了具备链接文件的优点外，还克服了它的缺点。它可以方便地进行随机存取。这种组织形式需要增加索引表带来的空间开销。 存取文件的速度受影响。文件索引分配示意图 2021/3/113424多重索引文件分配UNIX的多重索引文件结构示意图 这种方法具有一般索引文件的优点，但也存在着间接索引需要多次访盘而影响速度的缺点。 直接块 间接块 2021/3/1

141、13436.5.3 空闲存储空间的管理1空闲空间表法 （1）空闲空间表空闲空间表示例 2021/3/11344（2）空闲块分配（3）空闲块回收 特别适于存放连续文件 若存储空间有大量的小空闲区时，检索效率降低。 会产生外存的外部碎片，造成磁盘空间的浪费。 空闲空间表法2021/3/113452空闲块链接法易于实现但其工作效率低这种方法与串连文件结构有相似之处，只是链上的盘块都是空闲块而已。 空闲块链接法示意图 2021/3/113463位示图（Bit Map）法n它利用一串二进位值反映磁盘空间的分配情况，也称位向量（Bit Vector）法n设下列盘块是空闲的： 2, 3, 4, 5, 8,

142、9, 10, 11, 12, 13, 17, 18, 25, 26, 27, 则位示图向量是： 0011110011111100011000000111n块号的计算公式如下： 字长“0”值字数 + 首位“1”的偏移2021/3/113474空闲块成组链接法（1）空闲块成组链接空闲块成组链接法分配过程示例 （2）空闲块分配（3）空闲块释放2021/3/113486.6 管道文件如：$ who | wc -l 5n一个管道线就是连接两个进程的一个打开文件。一个进程向该文件写入信息，另一个进程从该文件中读出信息，由系统自动处理二者间的同步、调度和缓冲。npipe文件允许两个进程按先入先出（FIFO）

143、的方式传送数据，而它们可以彼此不知道对方的存在。n创建pipe文件可有两种方式：无名管道文件 有名管道文件 管道文件机制示意图 2021/3/113496.7 文件系统的可靠性文件系统受到破坏所造成的损失往往比计算机自身受到破坏的损失还大 造成数据丢失或数据损坏的原因有多种6.7.1 磁盘坏块管理 硬件方案是在磁盘的一个扇区上记载坏块清单。 软件方案需要用户或文件系统仔细地构造一个文件，它包含全部坏块2021/3/113506.7.2 后备1备份介质 目前比较常用的备份介质有软盘、磁带、光盘和硬盘等2备份策略（1）完全备份 也称简单备份，即每隔一定时间就对系统做一次全面备份。（2）增量备份 在

144、这种备份策略中，首先进行一次完全备份，然后每隔一个较短的时间段进行一次备份，但仅仅备份在这段时间间隔内修改过的数据。（3）更新备份 增量备份是备份当天更改的数据，而更新备份是备份从上次进行完全备份后至今更改的全部数据文件。2021/3/113513备份工具 在UNIX，Linux系统中，备份软件有tar, cpio, dump等n物理转储 从磁盘上第0块开始，把所有的盘块按照顺序写到磁带上；当复制完最后一块时，转储结束。n逻辑转储 从一个或多个指定的目录开始，递归地转储自某个日期以来被修改过的所有文件和目录。2021/3/113526.7.3 文件系统和一致性1盘块一致性检查 检查程序建立两个

145、表格，即使用表和空闲表。盘块一致性检查示例 2021/3/113532文件一致性检查n从根目录开始，沿目录树递归向下查找。对于每个目录中的每个文件，其I节点对应的计数器值加1。当检查完毕后，得到一个以I节点号为下标的列表，说明每个文件包含在多少个目录中。然后，把这些数目与存放在I节点中的链接计数进行比较。如果文件系统保持一致性，那么两个值相同；否则，出现两种错误，即I节点中的链接计数太大或太小。 2021/3/11354第7章 输入/输出管理 2021/3/11355本章内容提要nI/O管理概述n设备分配nI/O软件层次n磁盘调度和管理2021/3/113567.1 I/O管理概述 7.1.1

146、 I/O设备分类和标识1设备分类 可以从不同角度对外部设备进行分类，按照工作特性可把它们分成存储设备和输入/输出设备两大类。（1）存储设备 它们是计算机用来存储信息的主要设备。（2）输入/输出设备 输入设备是计算机用来接收来自外部世界信息的设备 输出设备是将计算机加工处理好的信息送向外部世界的设备 n还可以从其他角度对设备进行分类。例如：按传输速率的快慢n按设备的共享属性分类，分为独占设备、共享设备和虚拟设备2021/3/11357 I/O设备分类和标识2设备标识n系统按某种原则为每台设备分配惟一的号码，用做硬件（设备控制器）区分和识别设备的代号，称做设备绝对号（或绝对地址）。n操作系统为每类

147、设备规定了一个编号，称做设备类型号。如在UNIX系统中，设备类型号称做主设备号。n设备相对号，是用户自己规定的所用同类设备中的第几台。2021/3/113587.1.2 I/O系统结构不同规模的计算机系统，其I/O系统结构存在差异。在大多数微型机和小型机中，都使用总线I/O系统结构总线I/O系统结构示意图 2021/3/113597.1.3 设备控制器nI/O设备一般由机械和电子两部分组成n电子部分称做设备控制器或适配器n操作系统总是通过设备控制器实施对设备的控制和操作n控制器是可编址的设备1控制器接口n设备控制器有两个方向的接口： 与主机之间的系统接口 与设备驱动电路之间的低层次接口2021

148、/3/113602控制器功能 实现主机和设备之间的通信控制，进行端口地址译码。 把计算机的数字信号转换成机械部分能够识别的模拟信号，或者反过来。 实现数据的缓冲。 接收主机发来的控制命令。 将设备和控制器当前所处的状态提供给主机。2021/3/113613存储器映像I/On为了实现与CPU通信，每个控制器都有几个寄存器: 控制寄存器 状态寄存器 数据寄存器 除控制寄存器外，很多设备还有数据缓冲区。nCPU与控制寄存器和设备数据缓冲区的基本通信方式: 为每个控制寄存器分配一个I/O端口号 把所有控制寄存器映像到存储器空间存储器映像I/O（Memory-Mapped I/O）。内存和I/O地址空间

149、的三种映像方式 2021/3/113627.1.4 I/O系统的控制方式1程序控制直接传递方式2程序查询方式3中断控制方式 其基本工作过程是： CPU发出启动I/O设备的指令 I/O控制器启动并控制I/O设备的工作 I/O控制器向CPU发送一个中断信号 CPU将控制传送给中断处理程序 中断处理程序执行相应的处理工作 CPU恢复对被中断任务的处理工作2021/3/113634直接存储器访问方式（1）DMA控制方式的引入 为减少CPU被中断的次数，提高CPU的工作效率，增加数据传输安全（2）DMA的传送操作DMA传送操作过程 2021/3/113645独立通道方式（1）通道的引入n为使CPU摆脱繁

150、忙的I/O事务，现代大、中型计算机都设置了专门处理I/O操作的机构，这就是通道。n通道程序由通道执行的指令组成。（2）通道类型 字节多路通道 它以字节作为信息输送单位，服务于多台低速I/O设备。 选择通道。 它在同一时间里只能为一台设备服务，主要用于连接高速外部设备。 成组多路通道 它结合字节多路通道分时操作和选择通道高速传送的优点，广泛用于连接高速和中速设备。6I/O处理器方式2021/3/113657.1.5 I/O管理的功能1I/O软件的主要目标（1）与设备无关 （也称设备独立性）n用户程序应与实际使用的物理设备无关，由操作系统考虑因为实际设备不同而需要使用不同的设备驱动程序等问题。n用

151、户编写程序时一般不再使用物理设备，而使用虚拟设备，由操作系统实现虚实对应 。n sort output（2）统一命名（3）层次结构（4）效率高2021/3/113662I/O管理的主要功能 （1）监视设备状态 （2）进行设备分配 （3）完成I/O操作 （4）缓冲管理与地址转换2021/3/113677.2 设备分配7.2.1 与设备分配相关的因素 （1）I/O设备的固有属性 （2）系统所采用的分配算法 （3）设备分配应防止死锁发生 （4）用户程序与实际使用的物理设备无关2021/3/113687.2.2 设备分配技术1按使用性质对设备分类 （1）独占设备n独占设备是不能同时共用的设备，即在一段

152、时间内，该设备只允许一个进程独占。 （2）共享设备n共享设备是可由若干进程同时共用的设备。 （3）虚拟设备n虚拟设备是利用某种技术把独占设备改造成可由多个进程共用的设备。2021/3/113692设备分配技术 （1）独占分配 把独占设备固定地分配给一个进程，直至该进程完成I/O操作并且释放它为止。 （2）共享分配 由若干进程共用同一设备 （3）虚拟分配 利用共享设备去实现独占设备的功能，从而使独占设备“感觉上”成为可共享的、快速的I/O设备。2021/3/113707.2.3 设备分配算法 （1）先来先服务 （2）优先级高的优先服务2021/3/113717.2.4 SPOOLing系统n早期

153、设备分配的虚拟技术是脱机方式 利用外围计算机专门负责I/O工作 n解决了慢速外设与快速主机的匹配问题n存在如下缺点： 需要人工干预，产生人工错误的机会多，且效率低； 周转时间慢； 无法实现优先级调度。2021/3/11372 SPOOLing系统用常驻内存的进程去模拟一台外围机 SPOOLing系统一般分为4个部分 ： 存输入部分 取输入部分 存输出部分 取输出部分SPOOLing系统工作原理示意图 2021/3/11373n上述4个部分的工作可由输入进程IN和输出进程OUT完成 IN进程负责存输入和取输入工作 OUT进程负责存输出和取输出工作nSPOOLing可使一个作业的输入/输出与其他作

154、业的计算重叠起来进行nSPOOLing提供了非常重要的数据结构 作业池n付出不少代价 占用大量的内存作为外设之间传送信息用的缓冲区，它所用的表格也占用不少内存空间； 占用大量磁盘空间作为输入井和输出井； 增加了系统的复杂性。 SPOOLing系统2021/3/113747.3 I/O软件层次I/O软件系统的层次7.3.1 中断处理程序2021/3/113757.3.2 设备驱动程序1设备驱动程序的功能 接受来自上层、与设备无关软件的抽象读写请求，并且将该I/O请求排在请求队列的队尾，同时还要检查I/O请求的合法性（如参数是否合法）。 取出请求队列中队首请求，且将相应设备分配给它。 向该设备控制

155、器发送命令，启动该设备工作，完成指定的I/O操作。 处理来自设备的中断。2021/3/113762设备驱动程序在系统中的位置通常，设备驱动程序与设备类型是一一对应的。主设备号表示设备类型，而次设备号表示该类型的一个设备。设备驱动程序层的目的是对核心I/O子系统隐藏设备控制器的差别 设备驱动程序在系统中的逻辑位置示意图 2021/3/113773设备驱动程序的特点 驱动程序的主要作用是实现请求I/O的进程与设备控制器之间的通信 驱动程序与设备特性密切相关 驱动程序可以动态安装或加载 驱动程序与I/O控制方式相关 驱动程序与硬件密切相关 不允许驱动程序使用系统调用2021/3/113784设备驱动

156、程序的框架 （1）设备驱动程序与外界的接口 驱动程序与操作系统内核的接口 驱动程序与系统引导的接口 驱动程序与设备的接口（2）设备驱动程序的组成 驱动程序的注册与注销 设备的打开与释放 设备的读/写操作 设备的控制操作 设备的中断和轮询处理2021/3/113797.3.3 与设备无关的操作系统I/O软件与设备无关的操作系统I/O软件的功能示意图 2021/3/113801设备驱动程序的统一接口 新的驱动程序遵循驱动程序接口的约定 I/O设备如何命名 保护问题2缓冲技术 （1）缓冲技术的引入 缓冲的基本思想 主要目的是： 缓解CPU与I/O设备间速度不匹配的矛盾。 提高它们之间的并行性。 减少

157、对CPU的中断次数，放宽CPU对中断响应时间的要求。 （2）缓冲区的设置 单缓冲。适宜数据到达率与离去率相差很大的情况 双缓冲。适宜信息的输入和输出速率相同（或相差不大）的情况2021/3/11381缓冲区的设置 双缓冲工作示例 多缓冲为了解决阵发性I/O的速度不匹配问题，可以设立多个缓冲区。2021/3/113823出错报告n根据错误产生的原因，可把I/O错误分为两类： 程序设计错误 实际I/O错误。4分配和释放独占设备 处理请求的简单办法是让进程直接打开设备特别文件 另一种办法是设立专门机制，负责独占设备的申请和释放 5提供与设备无关的块大小 不同磁盘的扇区大小可能不同。通过这部分软件的作

158、用，可隐藏这些差异，向高层提供统一的盘块大小。2021/3/113837.3.4 用户级I/O软件n多数I/O软件都在操作系统中，用户空间中也有一小部分。通常，它们以库函数形式出现。n用户空间中另一个重要的I/O软件是SPOOLing系统。2021/3/113847.4 磁盘调度和管理硬盘结构示意图磁盘的结构2021/3/113857.4.1 磁盘调度1磁盘存取时间 寻道时间:是指系统把磁头移到相应的磁道或柱面上所用时间； 旋转延迟时间：是指一旦磁头到达指定磁道、必须等待所需要的扇区转到读/写头下所用的延迟时间； 传输时间：是指信息实际在盘和内存之间进行传送所花费的时间。 一次磁盘服务的总时间

159、就是这三者之和 n减少平均寻道时间就可以显著地改善系统性能。2021/3/113862磁盘调度算法（1）先来先服务法（First-Come, First-Served，FCFS）先来先服务调度算法示例设磁头最初在53道上 总共移动了640个磁道 有一个请求磁盘服务的队列，要访问的磁道分别是 98，183，37，122，14，124，65，672021/3/11387最短寻道时间优先调度算法示例（2）最短寻道时间优先法（Shortest Seek Time First， SSTF）当前磁头在53道上 请求访问磁道序列：98，183，37，122，14，124，65，67磁头共移动了236个磁道

160、2021/3/11388扫描调度算法示例（3）扫描法（SCAN）请求访问磁道序列： 98，183，37，122，14，124，65，67磁头最初在53道上。正向0道方向移动 2021/3/11389（4）巡回扫描法（C-SCAN）巡回扫描调度算法示例请求访问磁道序列： 98，183，37，122，14，124，65，67磁头最初在53道上，正向右方移动2021/3/11390（5）寻查法（LOOK）LOOK算法也称“电梯”算法请求访问磁道序列： 98，183，37，122，14，124，65，67磁头最初在53道上，正向0道方向移动电梯调度算法示例 2021/3/113913磁盘调度算法的选择

161、 选最佳方案与多种因素有关: 任何调度算法的性能都依赖于I/O请求的数量和类型 文件的物理存放方式对磁盘请求有很大影响 目录和索引块的位置对I/O请求队列有重要影响 旋转延迟时间的影响2021/3/113927.4.2 磁盘管理1磁盘格式化n 低级格式化或物理格式化（1）格式化后扇区的格式n低级格式化按照规定的格式为每个扇区填充控制信息。n一般来说，扇区格式由三部分组成，即扇区头、数据区（通常为512 B）和扇区尾（2）磁盘分区和逻辑格式化n第一步是分区，即把磁盘分成一个或多个柱面组。n第二步工作是逻辑格式化,即建立文件系统。 2021/3/11393MS-DOS的磁盘布局2引导块结构整个引导

162、程序保存在称做引导块的分区中，该分区在盘上的位置是固定的，通常在起始扇区。 2021/3/113943坏块处理 （1）坏块的产生n一类是“天生”的,即厂家生产时该盘就存在瑕疵，如磁层有缺陷。n另一类是“继发”的,即在使用过程中因外界干扰或故障而造成的磁层损坏。 （2）处理坏块的方式 控制器处理方式替代方式n直接替代方式：是对磁道上的扇区依次编号，在最后留出备用扇区。n绕过坏块方式：是当发现坏块时，就绕过它，即不为它编号，接着从后面的扇区继续编号。 操作系统处理方式 操作系统首先通过读盘上的坏块表或亲自检测整个磁盘，获取坏块信息。一旦操作系统知道哪个扇区坏了，它就构建重映像表。 （3）后备问题

163、（4）其他磁盘故障 2021/3/11395第8章用户接口服务 2021/3/113968.1 用户接口的发展n计算机软件平台 n早期操作系统对外提供的接口很简陋，功能也单一，包括脱机的作业控制语言（或命令）和联机的键盘操作命令。n在分时系统出现后 ,不仅为程序员提供编程服务的系统调用，而且提供功能强大的命令行接口。在一维空间运行。 n图形用户接口（常称做图形界面），它是二维空间界面。n现在有不少游戏软件在三维硬件显示卡的支持下实现三维动画效果。 2021/3/113978.2 系统调用 8.2.1 系统调用和库函数1系统调用 系统调用是操作系统提供的、与用户程序之间的接口，也就是操作系统提供

164、给程序员的接口。它一般位于操作系统核心的最高层。n从感觉上系统调用类似于过程调用，都由程序代码构成，使用方式相同调用时传送参数。n两者有实质差别：过程调用只能在用户态下运行，不能进入核心态；而系统调用可以实现从用户态到核心态的转变。n系统调用可分为5个类别：进程控制、文件管理、设备管理、信息维护和通信。 2021/3/113982库函数n它们本身并不属于操作系统的内核部分，而且运行在用户态下。n库函数涉及文件管理、状态信息、文件修改、程序设计语言的支持、程序装入和执行、通信等方面内容。nUNIX/Linux系统中系统调用与库函数之间的关系 2021/3/113998.2.2 系统调用使用方式n

165、在UNIX/Linux系统中，系统调用和库函数都是以C函数的形式提供给用户的，它有类型、名称、参数，并且要标明相应的文件包含。nopen系统调用可以打开一个指定文件，其函数原型说明如下 #include #include #include int open(const char *path, int oflags);不同的系统调用所需要的头文件（又称前导文件）是不同的。【例8.1】本程序利用fork( )创建子进程，利用getpid( )和getppid( )分别获得进程的PID和父进程PID，使用sleep( )将相关进程挂起几秒钟。2021/3/11400n/*proc1.c演示有关进程操

166、作*/n#include n#include n#include n#include nint main(int argc,char *argv)nn pid_t pid,old_ppid,new_ppid;n pid_t child,parent;n parent=getpid(); /*获得本进程的PID*/n if(child=fork()0)n fprintf(stderr,%s:fork of child failed:%sn,argv0,strerror(errno);n exit(1);n n else if(child=0) /*此时是子进程被调度运行*/n old_ppid=

167、getppid();n sleep(2);n new_ppid=getppid();n n else n sleep(1);n exit(0); /*父进程退出*/n n /*下面仅子进程运行*/n printf(Original parent:%dn,parent);n printf(Child:%dn,getpid();n printf(Childs old ppid:%dn,old_ppid);n printf(Childs new ppid:%dn,new_ppid);n exit(0);n系统调用使用方式2021/3/114018.2.3 系统调用的处理方式1一般处理方式n不同版本的

168、UNIX系统提供的系统调用的数目不同 n实现它们的汇编代码形式通常都以trap指令开头（在Linux系统中是通过中断指令“INT 0X80”实现的）ntrap指令的一般格式是： trap xx 参数1 参数2 当CPU执行到trap指令时，产生陷入事件。所有的陷入事件有一个总的服务程序，即陷入总控程序。系统调用处理函数根据trap指令后面的系统调用号去查系统调用入口表，然后转入各个具体的系统调用处理程序。2021/3/11402参 数 个 数 标 志 处 理 程 序 注 释 01nosys 0=indir 11rexit 1=exit 01fork 2=fork 30read 3=read 3

169、0write 4=write 30open 5=open 10close 6=close 系统调用入口表sysent结构 一般处理方式 系统调用号就是入口表的下标。如: trap 4 参数1 参数2 参数32021/3/114032系统调用实现过程示例2021/3/114048.3 命令行接口8.3.1 命令的一般使用方式 1 常用shell种类nBourne shell（简写sh）nC shell（简写csh）nBourne Again Shell（简写bash）nKorn shell（简写ksh） 2shell命令的一般格式 命令名 选项 参数1 参数2 例如， cp f file1.c

170、myfile.c2021/3/11405n使用shell命令时，应注意:（1）命令名必须是小写的英文字母 （2）一般格式中由方括号括起来的部分是可选的（3）选项是对命令的特别定义，以“-”开始，多个选项可用“-”连起来（4）参数提供命令运行的信息或命令执行过程中所使用的文件名（5）如果命令行中没有提供参数，命令将从标准输入文件（即键盘）上接收数据，输出结果显示在标准输出文件（即显示器）上，而错误信息则显示在标准错误输出文件（即显示器）上。（6）命令在正常执行后返回一个0值，表示执行成功;而非0值表示失败。（7）UNIX/Linux操作系统的联机帮助对每个命令的准确语法都做了说明。shell命令

171、的一般格式2021/3/114068.3.2 命令解释程序1实现方式n命令解释程序的基本功能是接收用户输入的命令，然后解释并且执行。n它不是操作系统的内核部分n实现命令的常见方式 （1）内置方式：命令解释程序本身就包含执行该命令的代码 （2）外置方式：每条外置命令都对应专门的系统程序，通常以可执行文件的形式存放在磁盘上。 外置命令是通过创建子进程，并在子进程的空间中执行的。2021/3/114072shell基本工作原理shell命令基本执行过程及父子进程之间的关系示意图 2021/3/114088.3.3 shell程序设计nshell不仅作为命令解释程序出现，它还是一种高级程序设计语言【例

172、8.2】 由三条简单命令组成的shell程序（文件名为ex1）。$ cat ex1datepwdcd .2021/3/11409【例8.3】 带有控制结构的shell程序（文件名为ex2）。$ cat ex2#!/bin/bash# If no arguments, then listing the current directory.# Otherwise, listing each subdirectory.if test $# = 0then ls .else for i do ls -l $i | grep d donefishell程序设计2021/3/114108.4 图形用户界面

173、 8.4.1 图形界面简介 1菜单红旗Linux的菜单示例 2图标2021/3/114113窗口红旗Linux的窗口示例 2021/3/114128.4.2 X Window系统nX Window的体系结构包括两部分：客户-服务器模型和X协议。1客户-服务器模型X Window系统的客户-服务器模型 X客户客户是使用系统窗口功能的一些应用程序 X服务器服务器也称作显示管理器，是控制实际显示设备和输入设备的程序。 2021/3/11413n典型的X客户程序有以下两种:（1）窗口管理器。它是决定窗口外观的一种客户进程，具有改变窗口的大小或位置，将窗口缩成图标，重新安排窗口在堆栈中的位置等功能。（2

174、）桌面系统。它是一个客户进程，控制桌面图标和目录的出现位置、桌面和目录菜单的内容，以及控制在桌面图标、目录和菜单上进行鼠标操作所产生的效果。2X协议 X协议是一个抽象的应用服务协议，不包括对底层硬件的访问和控制，它包括了终端的输入请求和对X服务程序发出的屏幕输出命令。 X协议是X服务程序和X客户应用程序进行通信的途径。 X协议是建立在一些常用的传输协议之上。X Window系统2021/3/11414n从用户的角度看，X Window是由两个不同的X部分组成的：应用程序接口和窗口管理器：X Window系统应用程序接口与窗口管理器的关系 2021/3/114153应用程序接口（API）X Wi

175、ndow编程可用的API2021/3/114164GNOME桌面系统n目前，Linux系统主要采用两种桌面系统环境KDE和GNOME。nGNOME是GNU网络对象模型环境（GNU Network Object Model Environment）的缩写，它是GNU项目的一部分，是完全开放源代码的自由软件。5KDE桌面系统主要有以下特点： 通过图形用户界面可以完全实现对环境的配置 桌面上提供了一个更安全的删除文件用的垃圾箱 通过鼠标安装其他文件系统，如CD ROM 用菜单控制终端窗口的滚动、字体、颜色和尺寸大小 实现网络透明存取 完全支持鼠标的拖放操作（Drag-and-Drop） 提供帮助文件

176、浏览器（Help View） 提供一套应用程序和上下文相关的帮助文档 提供会话管理程序（Session Manager）2021/3/11417第9章嵌入式操作系统2021/3/11418本章内容提要n嵌入式系统概述 n嵌入式操作系统概述 n实时内核及其实现 n实例简介CLinux 2021/3/114199.1 嵌入式系统概述n嵌入式系统是以应用为中心、以计算机技术为基础的，其软、硬件可裁剪，适用于对功能、可靠性、成本、体积、功耗等有严格要求的专用计算机系统。特 征嵌入式系统通用计算机系统外观独特，面向应用，各不相同具有台式机、笔记本等标准外观结构组成面向应用的嵌入式微处理器，总线和外部接口

177、多集成在处理器内部。软件与硬件紧密集成在一起通用处理器、标准总线和外设。软件和硬件相对独立安装和卸载运行方式基于固定硬件，自动运行，不可修改用户可以任意选择运行或修改生成后再运行开发平台采用交叉开发方式，开发平台一般采用通用计算机开发平台是通用计算机二次开发性一般不能再做编程开发应用程序可重新编制应用程序固定。应用软件与操作系统整合一体，在系统中运行多种多样，与操作系统相互独立嵌入式系统和通用计算机系统的比较 2021/3/114209.2 嵌入式操作系统概述9.2.1 嵌入式软件系统的体系结构嵌入式软件系统的体系结构示意图 2021/3/114219.2.2 嵌入式操作系统1基本功能与分类n

178、嵌入式内核是操作系统的核心基础和必备部分，其他部分要根据嵌入式系统的需要来确定。n最大特点就是可定制性，即能够提供对内核的配置或裁剪功能，可以根据应用需要有选择地提供或不提供某些功能，以减少系统开销。n可以从不同角度对它进行分类 2021/3/114222发展历史（1）无操作系统阶段n主要特点是：系统结构和功能相对单一，处理效率较低，存储容量较小，几乎没有用户接口。（2）简单操作系统阶段n主要特点是：出现了大量高可靠、低功耗的嵌入式CPU（如Power PC等），并得到迅速发展。（3）实时操作系统阶段n主要特点是：操作系统的实时性得到了很大改善，已经能够运行在各种不同类型的微处理器上，具有高度

179、的模块化和扩展性。（4）面向Internet阶段n主要特点是：与网络密切结合，大大方便用户使用，系统功能更强，提高安全保护措施。2021/3/114233操作系统选择n硬件平台的选择中最重要的是处理器选择，其主要因素包括：处理性能、技术指标、功耗、软件支持等。n软件平台选择的关键点是操作系统的选择。n需考虑的关键点有以下几个：所提供的开发工具（如编译器、调试器等）、可移植性、内存要求、可裁剪性、是否提供硬件驱动程序、实时性能等。当然，还要选择合适的编程语言以及集成开发环境。n嵌入式系统应用开发的过程嵌入式系统开发流程 2021/3/114249.3 实时内核及其实现9.3.1 任务管理与调度1

180、任务n任务是一个独立的执行线程，可以与其他的并发任务竞争处理器时间。 2构建任务模型 n在任务模型中，管理用户程序时，是把整个应用看成是一个进程；进行处理时，则将该应用划分为多个任务。3任务的组成 代码 数据 堆栈2021/3/114254任务的属性n与任务相关的参数是任务属性n包括任务优先级（Priority）、周期（Period）、计算时间（Computation Time）、就绪时间（Ready Time），截止时间（Deadline）等n截止时间可分为硬截止时间（Hard Deadline）和软截止时间（Soft Deadline）5任务管理n可以通过创建、删除、挂起、解挂、设置优先级

181、等操作对任务进行管理。 n任务是动态实体，可以处于以下合法状态之一：睡眠、就绪、运行、等待。6任务的调度算法n多采用基于静态优先级的可抢占式调度2021/3/114269.3.2 中断和时间管理1中断n在大多数嵌入式处理器体系结构中都提供中断机制 2时间管理模块 n时间管理模块用一个统一的方式来解决，提供定时中断，实现延时和超时控制。3中断管理功能4时间管理功能n提供定时中断，即时钟节拍；n提供日历时间，负责与时间相关的任务管理工作；n提供软定时器的管理功能。2021/3/114279.3.3 任务的同步和通信n嵌入式系统中使用任务原语实现任务的同步和通信。1信号量n在实时操作系统中，信号量可

182、以是一个二值信号量或一个计数信号量2事件n在嵌入式实时内核中，事件是一种表明预先定义的系统状况已经发生的机制。n一个或多个事件构成一个事件集。n一个事件标志组一般由两部分组成：标志位 ，任务列表3消息n任务间的通信方式可分为直接通信和间接通信 直接通信方式是指在通信过程中，双方必须明确地知道彼此的存在。 间接通信方式是指在通信过程中，通信双方不需要指出消息的来源或去向，而通过中间机制进行发送和接收。 邮箱和消息队列 2021/3/114284管道 n嵌入式系统的管道提供一个简单数据流，当管道空时，阻塞读的任务；当管道为满时，阻塞写的任务。5异步信号n异步信号机制也称软中断机制，异步信号又称软中

183、断信号。n需要处理异步信号的任务由两部分组成：一个是与异步信号无关的任务主体，另一个是ASR（异步信号服务例程）。n一个ASR对应于一个任务。n对异步信号的主要操作包括： 安装异步信号处理例程 发送异步信号到任务2021/3/114296共享内存n实现任务间通信最常用的方法是使用共享数据结构，尤其是当所有任务都在同一地址空间的条件下。 7任务间的耦合度 n在嵌入式多任务系统中，任务间的耦合程度是不一样的。8任务优先级反转高优先级任务需要等待低优先级任务释放资源的现象，称作优先级反转（Priority Inversion）。2021/3/114309.3.4 内存管理n嵌入式系统对内存管理的普遍

184、要求是最小的碎片、最小的管理负载和确定的分配时间。n通常不采用虚拟存储管理，而采用静态内存分配和动态内存分配。1需考虑因素（1）内存管理方式应简捷（2）一般不使用虚拟存储技术（3）内存保护可以有两种方式。一种是平面内存模式，另一种是内存保护方式： 防止地址越界 防止操作越权2内存管理模式 静态分配模式 动态分配模式 2021/3/114313存储区管理n常用的嵌入式内存管理方式有定长存储区和可变长存储区两种n对分区的操作：创建/删除分区、获得/释放内存块、获取分区ID、获取当前创建的分区数、获取当前所有分区的ID、获取分区信息。4内存保护n一般嵌入式系统采用内存管理单元MMU提供的内存保护功能

185、。n其保护方式是：如果一个MMU处在嵌入式系统中，则物理地址按页寻址；每个内存页有一组相关的属性，包括：该页是否含有代码或数据；该页是否可读、可写、可执行；该页的CPU访问模式是特权指令模式，还是非特权指令模式。2021/3/114329.3.5 I/O管理n通常，设计一个嵌入式系统的目的就是专门用来控制某些设备，并适应该设备的特殊需求。n嵌入式I/O系统主要由I/O设备、相关设备驱动程序、I/O子系统组成。nI/O设备分为字符设备和块设备n每个I/O设备都有一个负责完成简单读/写操作的驱动程序，并为用户程序提供一个有关自身属性的I/O应用编程接口。nI/O子系统定义一组标准的I/O操作函数，

186、所有I/O设备驱动程序都支持这个函数集合。2021/3/114339.4 实例简介CLinuxnCLinux表示Micro-Control-Linux，意指“针对微控制领域而设计的Linux系统”。1CLinux系统架构CLinux系统架构 CLinux操作系统主要由三个基本部分组成：引导程序、CLinux内核（由内存管理、进程管理和中断处理等构成）和文件系统。 2021/3/114342内存管理n它无法使用虚拟存储管理技术及其相应的内存保护技术。实际上，CLinux采用实存管理策略。nCLinux仍然采用分页存储管理技术。n因为系统不含MMU，所以无法使用磁盘交换空间。3文件系统nCLinu

187、x系统多采用Romfs文件系统，它是一种相对简单、占用空间较少的文件系统。nRomfs是只读的文件系统，禁止写操作。4多进程管理n实际上，CLinux所有的进程管理都通过vfork实现。5Clinux的实时性讨论nCLinux本身并不支持特定的实时性应用n通过相应的修改，可以提供基于内核空间和用户空间的硬实时和软实时的系统调用（如RT-Linux或RTAI系统）。2021/3/11435第10章分布式操作系统 2021/3/11436本章内容提要n分布式系统概述n分布式操作系统概述n分布式系统的实现通信问题进程管理死锁问题文件系统中间件2021/3/1143710.1 分布式系统概述10.1.

188、1 分布式系统概述1分布式系统特征n分布式系统是多个处理机通过通信线路互连而构成的松散耦合系统，它对用户是透明的。n一般认为，分布式系统应具有以下四个特征： 分布性 自治性 并行性 全局性2021/3/1143810.1.2 分布式系统的优点（1）资源共享（2）加快计算速度（3）可靠性高（4）方便快捷的通信缺点 主要是可用软件不足，系统软件、编程语言、应用程序以及开发工具都相对很少；还存在通信网络饱和或信息丢失以及网络安全问题，方便的数据共享同时意味着机密数据容易被窃取。2021/3/1143910.2 分布式操作系统概述10.2.1 分布式操作系统简介n分布式操作系统是配置在分布式系统上的共

189、用操作系统。n用户利用透明的方式访问系统内的远程资源，即用户访问远程资源的方式和访问本地资源相同。n它有如下三个基本功能： 进程管理 通信管理 资源管理2021/3/1144010.2.2 4种多机系统的比较n多处理器系统（Multiprocessor Systems）每个节点只有一个CPU，所有外部设备都是共享的共享同一个内存，彼此紧密地耦合在一起整个系统共享同一操作系统n多计算机系统（Multicomputer Systems） 每个节点除CPU外，还有本地内存和网卡，有时也有用于分页的硬盘 多计算机的各个节点运行同样的操作系统 整个系统共享同一个文件系统，且是集中式管理方式n网络系统（N

190、etwork Systems） 每个节点是一个完整的计算机，不仅有CPU、内存，还有完整的一组设备 各节点上有本地操作系统，其上加上网络软件，构成网络操作系统n分布式系统（Distributed Systems） 分布式系统有很多特征与网络系统相同 分布式系统是虚拟的单机系统，通常各节点上运行统一的操作系统，利用消息机制实现通信，具备数据迁移、计算迁移和进程迁移等功能。2021/3/1144110.2.3 分布式系统的设计目标1透明性 分布式系统的一个重要特征是系统的分布性对用户是完全透明的 可在两个层次上实现透明性:对用户隐藏分布性;系统对程序透明 类 别 含 义位置透明性软硬件资源分布在各

191、处，而用户不清楚资源的确切位置迁移透明性资源可以随意移动，而不必改变它们的名字复制透明性系统可以任意复制文件或其他资源，用户不清楚多个副本存在并发透明性多个用户可以自动共享资源，彼此不会注意对方的存在并行透明性任务被并行地执行，而用户并不知道（理论上要靠编译器、运行系统及操作系统三者的共同支持，目前尚无法实现这一点）分布式系统不同种类的透明性 2021/3/11442分布式系统的设计目标2灵活性n分布式操作系统的内核模型有两种:单内核模型和微内核模型单内核模型基本上是在现有的集中式操作系统上附加一些网络设施，再集成一些远程服务。微内核模型是一种新式结构。微内核是操作系统的极小核心。它将各种操作

192、系统共同需要的核心功能提炼出来，形成微内核的基本功能。 所有其他的系统服务都通过微内核之外的服务器实现。 分布式操作系统的两种内核模型 2021/3/114433可靠性 可靠性涉及的方面包括可用性（Availability）、安全性和容错性。 可用性表示系统可以正常工作的时间比例 安全性指文件和其他资源必须受到保护，防止未授权使用。 容错性指在一定限度内对故障的容忍程度。4高性能 性能指标包括多个方面，如执行速度、响应时间、吞吐量、系统利用率、网络通信能力，等等。 通信是影响分布式系统性能的基本问题5可扩展性 扩展可分为水平扩展和垂直扩展n水平扩展指添加或移去客户工作站，对系统性能影响很小n垂

193、直扩展指移植到更大的或更快的服务器或多服务器上。2021/3/1144410.3 分布式系统的实现10.3.1 通信问题n在分布式系统中没有共享内存，通过传递消息实现通信。n本质上，协议就是规定通信如何进行的一系列规则，在广域分布式系统中这些协议划分为多个层次，每一层都有自己的目标和规则。n基于局域网的系统通常采用客户-服务器模型n针对客户-服务器模型中通信要做大量输入/输出的缺陷 ，提供了远程过程调用（RPC）方法。n组通信方式 2021/3/1144510.3.2 进程管理1进程迁移（1）数据迁移（Data Migration）n整体传送是把文件整体地从节点B传送到节点An部分传送仅把用户

194、当前需要的那部分文件从节点B传送到节点A（2）计算迁移（Computation Migration）n在某些情况下，传送计算比传送数据更有效。（3）进程迁移（Process Migration）n进程迁移是计算迁移的逻辑延伸。当一个进程被提交执行时，并不一定始终都在同一节点上运行，整个进程（或者其中一部分）可能在不同的节点上执行。n采用进程迁移方式可使各节点的工作负载均衡；加速计算，减少整个进程的周转时间；提高硬件适宜性和软件适宜性；提高远程大量数据访问的效率。n有隐式和显式两种技术可用于进程迁移2021/3/114462同步问题 时钟同步 系统中的时钟并不需要绝对同步 事件排序 对系统中所发

195、生的事件进行排序n前趋关系 若A和B是两个相关事件，并且A在B之前发生，则有前趋关系AB。n并发事件 如果两个事件A和B彼此没有前趋关系，即A不先于B，B也不先于A，则称这两个事件为并发事件。 唯一重要的是，任何关心两个并发事件的进程都认可某个次序。n逻辑时钟 表示在进程内部各事件发生先后顺序的惟一记数值。n一个事件的时间戳就是该事件的逻辑时钟值。2021/3/114473互斥问题（1）集中式算法 其基本思想是：在系统的所有活动进程中选择一个进程作为协调者（即运行在最高网址的机器上的某个进程），由协调者负责对临界区进行管理。 优点：能够实现互斥，不会出现饥饿现象，且易于实现。 缺点：协调者是单

196、点失效，会使整个系统瘫痪； 大型系统中单一的协调者会成为系统性能的瓶颈。（2）分布式算法 其思想是：进程想进入临界区时，就建立并发送消息；得到许可，就可以进入临界区。退出临界区时，发送OK消息，并从队列中删除这些进程。 优点：弥补集中式算法的不足。 缺点：比集中式算法更慢、更复杂，代价也更高。（3）令牌环算法 令牌本身是一种特定格式的报文。进程持有令牌，便能进入临界区。 能够正确地实现进程互斥，而且不会出现饥饿现象；但也存在令牌丢失和进程失效两个问题。 2021/3/1144810.3.3 死锁问题在分布式系统中从不使用死锁避免方法，也很难实现预防。所以普遍使用死锁检测和恢复方法。分布式系统所

197、采用的死锁检测算法的基本原理与集中式系统相同 2021/3/1144910.3.4 文件系统1文件传送n文件传送分成上传/下载模式和远程存取模式两种类型。分布式系统文件传送的两种类型 2021/3/114502目录结构n层次文件系统n设计分布式文件系统的一个关键问题是，所有机器（和进程）的目录层次结构视图是否完全相同。n与之密切相关的一个问题是，是否有一个全局根目录，即所有机器都以它作为根。3命名透明性n透明性有两种形式 位置透明性和位置无关性。4文件共享语义n当多个用户共享同一文件时，必须精确定义读/写语义，以免出现歧义问题。n对所有操作按绝对时间排序，返回值总是最近的一个，这种模式称做顺序

198、一致性。n如果进程A修改了某个文件，当A关闭该文件时，它把副本发送给服务器，以后进程执行读操作时就得到新值。这种语义规则称做会话语义。2021/3/1145110.3.5 中间件中间件在分布式系统中的位置示意图 中间件中间件中间件中间件1中间件概念2021/3/114522中间件结构中间件在客户-服务器结构中的作用示意图 中间件中间件2021/3/11453第11章 安全性与保护机制 2021/3/11454本章内容提要 安全性概述 常见的安全性攻击一般性安全机制 保护机制2021/3/1145511.1 安全性概述11.1.1 信息安全问题n信息安全涉及众多方面，主要包括： 计算机安全 网络

199、安全11.1.2 安全环境“安全性（Security）”和“保护（Protection）”1对安全的威胁 数据保密所关注的问题是为保密数据保守秘密。 数据完整性表示在未经主人许可的情况下，未授权用户不能修改任何数据。 系统可用性意味着任何人不能干扰系统的正常工作。 2021/3/114562对安全的攻击表非法入侵包括两种类型：被动入侵者和主动入侵者。入侵者通常分为以下4种类型： 非技术用户偶然探听 内部人员窥探 窃取钱财 商业或军事间谍另一类安全灾害是病毒（Virus） 病毒是一段程序，它可以复制自身，通常都具有破坏性。 3偶然数据丢失造成数据丢失的原因有如下三类：自然灾害 硬件或软件出错 人

200、为故障 安全环境2021/3/1145711.2 常见的安全性攻击11.2.1 常见的攻击点 信息残留 系统漏洞 骗取用户密码 系统调用非法 修改操作系统结构 冒险尝试 人为安全因素2021/3/1145811.2.2 网络威胁对用户身份的仿冒 信息流监视 篡改网络上的信息 对发出的信息予以否认 授权威胁 活动天窗 拒绝服务 非法使用 信息泄露 物理入侵完整性侵犯特洛伊木马 对信息进行重发2021/3/1145911.2.3 计算机病毒计算机系统面临的另一类严重挑战就是计算机病毒 计算机病毒是一个程序片段，它能攻击合法的程序，使之受到感染。计算机病毒可对计算机系统实施攻击，操作系统、编译系统、

201、数据库管理系统和计算机网络等都会受到病毒的侵害。1Internet莫里斯蠕虫n蠕虫包含引导程序和蠕虫本体两个程序。2计算机病毒的特征 病毒程序是人为编制的软件，具有短小精悍的突出特点。 病毒可以隐藏在可执行程序或数据文件中。 可传播性，具有强再生机制。反映了病毒程序最本质的特征。 可潜伏性，具有依附于其他媒体寄生的能力。 病毒可在一定条件下被激活，从而对系统造成危害。2021/3/114603计算机病毒的传播方式 如附在一般的游戏、广告或电子邮件的后面4对付病毒的常用方法 购买、安装正版软件。 不要随意打开未知用户发来的邮件。 安装杀毒软件，定期或不定期地运行杀毒工具，并及时升级杀毒软件的版本

202、。 及时下载操作系统的补丁软件包。 系统重新安装之前，最好将整个硬盘重新格式化，包括重新格式化引导区。 为文件和目录设置最低权限。2021/3/1146111.3 一般性安全机制11.3.1 安全措施 物理层 人员层 网络层 操作系统层2021/3/1146211.3.2 一般性安全机制国际标准化组织ISO对开放系统互连（OSI）的安全体系结构制定了基本参考模型（ISO 7498-2）。1身份鉴别2访问控制3数据加密4数据完整性5数字签名6防重发7审计机制2021/3/1146311.4 保护机制11.4.1 保护域n计算机系统是进程和对象的集合体。n能够执行的操作取决于对象。n进程只能访问被

203、授权使用的资源,遵循“需者方知（need-to-know）”原则。2021/3/114641域结构n域是对的集合，每个对标记一个对象和一个可执行操作的子集，允许执行的操作称做权限。n例如，域D定义为，那么在域D上执行的进程对文件F可读可写，除此之外，它不能对F执行任何其他操作。有三个保护域的系统示例 2021/3/11465n进程和域之间的联系可以是静态联系或动态联系。n进程在运行的不同阶段对资源的使用方式不同。n域可以用以下多种方式实现： 每个用户可以是一个域。 每个进程可以是一个域。 每个过程可以是一个域。域结构2021/3/11466n利用由组成的对，建立一张包括所有对象（文件，包括表示

204、I/O设备的特别文件等）的完整的访问表，并列出这些对象是否可以读、写或执行。3存取矩阵n把对象与域的对应关系抽象地想象为一个矩阵，矩阵的行表示域，列表示对象，每个方块列出其权限。 2UNIX保护域存取矩阵示意图 把域作为对象的存取矩阵示意图 2021/3/1146711.4.2 存取控制表n按列存储技术中，每个对象与一个有序表关联，其中列出可以访问该对象的所有域以及怎样访问。这张表称做存取控制表（Access Control List, ACL）。使用存取控制表管理文件的存取示意图 2021/3/1146811.4.3 权力n对存取矩阵按行分割是实施简化的另一种方法。采用这种方法时，对每个进程

205、都赋予一张它能够访问的对象表，以及每个对象允许进行的操作（域），该表称做权力表（Capability List），其中每一项称做权力。进程及其权力表示例2021/3/11469n常见的保护权力表的方法有以下三种： 为每个内存字设置一个额外（特征）位 在操作系统内部保存权力表。 在用户空间中保存权力表，但是管理权力采用加密形式，用户不能随意改动它们。n存取控制表和权力表方式各有长处和不足： 权力表的效率很高；对于存取控制表ACL，必须进行搜索，这可能要花较长时间。 ACL允许有选择地撤销权限，而权力表方式则不行。 如果一个对象被删除，但其权力未被删除，或者权力被删除而对象未被删除，都会产生问题。

206、采用存取控制表ACL方式不会出现此类问题。 权力 2021/3/1147011.4.4 可信系统1. 可信计算基n可信计算基TCB（Trusted Computing Base）是由硬件和软件构成的，是可信系统的心脏部件。典型的TCB由多数硬件（除I/O设备外），一部分操作系统内核和具有超级用户权力的大部分或全部用户程序（如UNIX系统中完成SETUID的root用户程序）组成。nTCB的重要组成部分是引用监控程序引用监控程序示意图2021/3/11471可信系统2建立职责联系 可信UNIX系统增强了责任性，把每个账户与实际用户联系起来，审计每个行动，并把每个行动与系统中特定用户联系在一起。3

207、自由存取控制 n自由存取控制（Discretionary Access Control， DAC）决定用户能否访问所需的数据，放在试图使用的对象（文件、设备等）中。n可信系统扩充了标准的自由存取控制规则，包括： 限制在可执行文件上设置SUID和SGID位的能力。 限制用chown改变文件属主的能力。 每当写文件时清除SUID, SGID和黏着位，以防潜在滥用它们的权限。4对象重用n在重新分配存储器对象（无论在RAM，还是在辅助存储器中）资源之前，清除其中的信息 。2021/3/11472可信系统5授权与特权 系统特权与进程相关 子系统授权与用户相关 子系统是文件、设备和提供特殊功能的命令三者的

208、相关集合。6识别与认证 可信UNIX系统扩展了标准UNIX系统的识别与认证机制，对可以使用的口令类型有更多强制性规则，生成和修改口令也有新的过程。 7审计 记账子系统保持系统活动的有限记录 审计（Auditing）子系统给审计管理员提供扩展的系统活动历史 2021/3/11473可信系统8受保护子系统n可信系统在以下三个方面扩展了受保护子系统的概念： 对用户和组提供更精确的控制，由用户和组对特定系统资源组合（私有信息）进行维护。 提供单独的用户数据库，允许它运行维护私有信息的程序。 不需要用户作为子系统管理员注册，而是利用数据库核实子系统授权。 2021/3/1147411.4.5 安全性能评

209、测标准n1985年，美国国防部正式公布了一个有关可信计算机系统安全性能的评测标准（TCSEC）的文件“橙皮书” n分为7个级别，其中A级安全性最高，D级最低。2021/3/11475“橙皮书”安全准则准则DC1 C2B1 B2 B3A1安全策略 自由存取控制 对象重用 标号 标号完整性 以标记信息的导出 标记人工可读的的输出 强制存取控制 设备标记 职责 识别与认证 审计 可信路径 安全性能评测标准2021/3/11476准则DC1 C2B1 B2 B3A1保证 系统体系结构 系统完整性 安全性测试 设计说明和检验 隐藏通道分析 可信的设施管理 配置管理 可惜的恢复 可信的分布 文档 安全特征用户指南 可信设施手册 测试文档 设计文档 “橙皮书”安全准则（续表）安全性能评测标准2021/3/11477