操作系统原理 郭 平 王在模 何静媛 重庆大学计算机学院.

Presentation on theme: "操作系统原理 郭 平 王在模 何静媛 重庆大学计算机学院."— Presentation transcript:

1 操作系统原理 郭 平 王在模 何静媛 重庆大学计算机学院

2 参考书 汤子瀛，计算机操作系统，西安电子科技大学出版社，1988年 孙仲秀等，操作系统教程 高等教育出版社1995年12月(第二版)
William Stallings, Operating Systems(3rd edition), 清华大学 出版社, 1998年6月 David A. Solomon, Mark E. Russinovich, Inside Microsoft Windows 2000, 3rd Edition, Microsoft Press, 2000

3 课程主要内容 用户接口 进程管理 处理机管理 存储管理 文件系统 外部设备管理 期末考试 操作系统的功能 管理系统软硬件资源 扩展计算机的功能 向用户提供服务

4 课程的目的与要求 课程目的 对操作系统的基本概念和基本结构有清楚的认识 从资源管理的角度领会操作系统的原理、功能和技术
提高运用理论知识解决实际问题的能力。 课程要求 掌握现代操作系统的基本概念、基本原理和基本方法 能设计并使用程序设计语言编制和调试操作系统的关键算法和组成模块 了解和熟悉操作系统在计算机系统中的作用和地位，与硬件和其它软件的关系 了解操作系统控制计算机系统工作的全过程

5 第一章 绪论 什么是操作系统 操作系统的发展历史 操作系统的分类 操作系统的特征 操作系统的功能 操作系统的结构 常用的操作系统

6 03 / 2004 什么是操作系统 操作系统的地位和目标 操作系统的作用和组成 操作系统举例 驶多飞集团的演示

7 操作系统的地位和目标 图1.1 计算机系统的组成 应用软件 软件 编辑软件，编译软件 系统软件 计算机系统 操作系统 (层次结构)
硬件及固件（裸机） 应用软件 系统软件 编辑软件，编译软件 操作系统 图1.1 计算机系统的组成

8 操作系统在计算机系统中的地位 操作系统的地位：紧贴系统硬件之上，所有其他软件之下（是其他软件的共同环境）

9 引入操作系统的目标 有效性（系统管理人员的观点）：管理和分配硬件、软件资源， 合理地组织计算机的工作流程
方便性（用户的观点）：提供良好的、一致的用户接口，弥补 硬件系统的类型和数量差别 可扩充性（开放的观点）：硬件的类型和规模、操作系统本身 的功能和管理策略、多个系统之间的资源共享和互操作

10 操作系统的定义 操作系统是计算机系统中的一个由一系列模块构成的系统软件，它管理和控制计算机系统中的硬件和软件资源，合理地组织计算机的工作流程，以便有效地利用软硬件资源为用户提供一个功能强、使用方便的工作环境，从而在计算机和用户之间起到接口的作用。

11 操作系统的认识与研究观点 OS是计算机硬件、软件资源的管理者
03 / 2004 操作系统的认识与研究观点 OS是计算机硬件、软件资源的管理者 管理对象包括：计算机系统中的软硬件资源。CPU、存储器、外部设备、信息（数据和软件）； 管理的内容：资源的当前状态（数量和使用情况）、资源的分配、回收和访问操作，相应管理策略（包括用户权限）。 管理方式：协调软硬件的工作、调用。 OS是用户使用系统硬件、软件的接口 系统命令（命令行、菜单式、命令脚本式、图形用户接口GUI）； 系统调用（形式上类似于过程调用，在应用编程中使用）。 进程管理 计算机系统中运行程序的协调，提高资源的利用率 从微观上研究和观测操作系统 驶多飞集团的演示

12 操作系统举例 MS OS: MS DOS, MS Windows 3.x, Windows 95, Windows NT, Windows 2000及以上 UNIX: BSD, SRV4, OSF1, SCO UNIX, AIX, Solaris, Linux NOS: Novell Netware RTOS: VxWorks, pSoS, Nucleus

13 操作系统的发展历史 推动操作系统发展的主要动力 手工操作 单道批处理系统(simple batch processing) 多道批处理系统(multiprogramming system) 分时系统(time-sharing system) 实时系统(real-time system)

14 “需求推动发展” 推动操作系统发展的主要动力 提高资源的利用率和系统性能：计算机发展的 初期，计算机系统昂贵，用作集中计算
(2) 方便用户：用户上机、调试程序，分散计算时的事务处理和非专业用户（商业和办公、家庭） (3) 器件的发展：CPU的位宽度（指令和数据）、快速外存

15 手工操作 1946 ~ 50年代（电子管），集中计算（计算中心），计算机资源昂贵； 工作方式
用户：用户既是程序员，又是操作员；用户是计算机专业人员； 编程语言：为机器语言； 输入输出：纸带或卡片； 计算机的工作特点 用户独占全机：不出现资源被其他用户占用，资源利用率低； CPU等待用户：计算前，手工装入纸带或卡片；计算完成后， 手工卸取纸带或卡片；CPU利用率低；

16 主要矛盾 计算机处理能力的提高，手工操作的低效率（造成浪费）； 用户独占全机的所有资源； 提高效率的途径 专门的操作员，批处理

17 早期批处理系统 （batch processing, ,uniprogramming)
50年代末 ~ 60年代中（晶体管）：利用磁带把若干个作业分类编成作业执行序列，每个批作业由一个专门的监督程序（Monitor）自动依次处理。可使用汇编语言开发。 批处理中的作业的组成： 用户程序 数据 作业说明书（作业控制语言） 批： 供一次加载的磁带或磁盘，通常由若干个作业组装成，在处理中使用一组相同的系统软件（系统带）

18 批处理方式 联机批处理 用户提交作业：以纸带或卡片为介质； 操作员合成批作业：结果为磁带介质； 批作业处理：对批作业中的每个作业进行相同的处理：从磁带读入用户作业和编译链接程序，编译链接用户作业，生成可执行程序；启动执行；执行结果输出。 这时的问题：慢速的输入输出处理仍直接由主机来完成。输入输出时，CPU处于等待状态。

19 脱机批处理 卫星机：完成面向用户的输入输出（纸带或卡片），中间结果暂存在磁带或磁盘上。 作业控制命令由监督程序(monitor)来执行，完成如装入程序、编译、运行等操作。 特点：利用卫星机完成输入输出功能。主机与卫星机可并行工作。 优点：同一批内各作业的自动依次更替，改善了主机CPU和I/O设备的使用效率，提高了吞吐量。 缺点：磁带或磁盘需要人工装卸，作业需要人工分类，监督程序易遭到用户程序的破坏（由人工干预才可恢复）。

20 通道和中断技术 60年代初，发展了通道技术和中断技术，这些技术的出现使监督程序在负责作业运行的同时提供I/O控制功能。
通道：用于控制I/O设备与内存间的数据传输。启动后可独立于CPU运行，实现CPU与I/O的并行。 通道有专用的I/O处理器，可与CPU并行工作 可实现 I/O联机处理 中断是指CPU在收到外部中断信号后，停止原来工作，转去处理该中断事件，完毕后回到原来断点继续工作。 中断处理过程：中断请求，中断响应，中断点（暂停当前任务并保存现场），中断处理例程，中断返回（恢复中断点的现场并继续原有任务 可处理算术溢出和非法操作码，死循环（利用时钟中断进行超时限定） 监督程序发展为执行系统(executive system)，常驻内存

21 多道程序系统 (multiprogramming system)
60年代中 ~ 70年代中（集成电路），利用多道批处理提高资源的利用率。 多道批处理的运行特征 多道：内存中同时存放几个作业； 宏观上并行运行：都处于运行状态，但都未运行完； 微观上串行运行：各作业交替使用CPU； 在当前运行的作业需作I/O处理时，CPU转而执行另一个作业。

22 优点： 资源利用率高：CPU和内存利用率较高； 作业吞吐量大：单位时间内完成的工作总量大； 缺点： 用户交互性差：整个作业完成后或中间出错时，才与用户交互，不利于调试和修改； 作业平均周转时间长：短作业的周转时间显著增长； 软件支持：作业管理与调度，CPU管理，I/O管理，内存管理，外存管理 多道批处理系统——标志操作系统基本形成

23 分时系统(time-sharing system)
03 / 2004 分时系统(time-sharing system) 70年代中期至今 “分时”的含义分时是指多个用户分享使用同一台计算机。多个程序分时共享硬件和软件资源。 多个用户分时：单个用户使用计算机的效率低，因而允许多个应用程序同时在内存中，分别服务于不同的用户。有用户输入时由CPU执行，处理完一次用户输入后程序暂停，等待下一次用户输入－－时走时停 前台和后台程序(foreground & background)分时：后台程序不占用终端输入输出，不与用户交互－－现在的图形用户界面(GUI)，除当前交互的程序(输入焦点)之外，其他程序均作为后台 通常按时间片(time slice)分配：各个程序在CPU上执行的轮换时间。 （注意区分：硬件各部分的分时，如CPU和DMA使用总线和内存）。 驶多飞集团的演示

24 抢先式和非抢先式 ——分时系统的两种基本模式
抢先式和非抢先式(preemptive & non-preemptive)：出让CPU是OS强迫或程序主动 抢先式：OS强行出让CPU； 非抢先式：程序主动出让CPU；

25 分时系统的特点 人机交互性好：在调试和运行程序时由用户自己操作。 共享主机：多个用户同时使用。 用户独立性：对每个用户而言好象独占主机。 现在的许多操作系统都具有分时处理的功能，在分时系统的基础上，操作系统的发展开始分化，如实时系统、通用系统、个人系统等。

26 实时系统(real-time system)
用于工业过程控制、军事实时控制、金融等领域，包括实时控制、实时信息处理 要求：响应时间短，在一定范围之内；系统可靠性高 任务的类型： 周期性实时任务： 非周期性实时任务：截止时间(deadline)，开始截止时间 （最晚开始时间）和完成截止时间（最晚完成时间） 目前的操作系统，通常具有分时、实时和批处理功能，又称作通用操作系统。可适用于计算、事务处理等多种领域，能运行在多种硬件平台上，如 UNIX系统、Windows NT等。－－通用化、小型化

27 操作系统的分类 操作系统分类主要讨论操作系统的内部特征。 批处理操作系统 分时操作系统 实时操作系统 个人计算机操作系统 网络操作系统 分布式操作系统 返回

28 批处理操作系统 (Batch Processing Operation System)
作业的处理流程 作业提交：作业的输入； 作业执行 作业完成：作业的输出；

29 图1 批处理系统中作业处理及状态

30 单道(uniprogramming)和多道批处理的比较
内存使用 每次一个作业 每次多个作业 作业次序 顺序,先进先出 无确定顺序 多道程序系统和多处理系统(multiprocessing system)的区别：前者指多个程序同时在内存中交替运行，后者指多个处理器。

31 批处理的主要特征 用户脱机使用计算机：作业提交后直到获得结果之前，用户无法与作业交互。 作业成批处理 多道程序并行：充分利用系统资源。

32 多道批处理系统的资源利用效率特征 多道批处理系统的资源利用效率特征是基于各作业对系统资源的需求差异得到的。
例如：有3个作业A、B、C，分别为计算、检索和打印作业，单道运行时间分别为5分、15分和10分钟。它们可并行在15分钟内完成3个作业。各资源的利用效率为：

33 出现：作业管理、处理机管理、存储管理、设备管理、文件系统管理(file system)
多道批处理系统上的技术 作业调度：作业的现场保存和恢复－－上下文切换 资源共享：资源的竞争和同步－－互斥(exclusion)和同步(synchronization)机制 内存使用：提高内存使用效率（为当前由CPU执行的程序提供足够的内存）－－覆盖(overlay)，交换(swap)和虚拟存储(virtual memory) 内存保护：系统存储区和各应用程序存储区不可冲突－－存储保护 文件非顺序存放、随机存取 出现：作业管理、处理机管理、存储管理、设备管理、文件系统管理(file system)

34 分时操作系统 (Time Sharing Operating System)
分时的定义 把计算机的系统资源（尤其是CPU时间）进行时间上的分割，每个时间段称为一个时间片（time slice），每个用户依次轮流使用时间片。

35 分时系统的特征 多路性：多个用户同时工作。
共享系统资源，提高了资源利用率。节省维护开支，可靠性高：笨终端－－至今仍在使用。促进了计算机的普遍应用，提高资源利用率：远地用户通过终端（较便宜）联机使用。 独立性：各用户独立操作，互不干扰。 交互性：系统能及时对用户的操作进行响应，显著提高调试和修改程序的效率：缩短了周转时间。

36 分时系统的类型 单道分时：调入-调出(Roll-in/Roll-out)，I/O开销太大（在有卫星机处理I/O时，单道分时是有用的）
前台后台分时：后台存放批处理作业，内存的划分是固定的，不灵活 多道分时：需要解决加载程序时地址空间重定位的问题

37 分时系统的主要问题 及时接受输入：多个I/O端口，设立多路缓冲区 及时响应： 提高对换速度（快速外存）、 限制用户数目、
缩短时间片（可能引起对换次数增多，开销增大，程序总运行时间增大） 减少对换信息量： 可重入代码(re-entrant code)； 请求页式存储管理：只对换部分程序

38 实时操作系统 (Real Time Operating System)
实时操作系统主要用于过程控制、事务处理等有实时要求的领域，其主要特征是实时性和可靠性。 实时系统的特征 实时时钟管理：提供系统日期和时间、定时和延时等时钟管理功能； 过载保护：缓冲区排队，丢弃某些任务，动态调整任务周期； 过载是指进入系统的任务数目超出系统的处理能力。 高度可靠性和安全性：容错能力（如故障自动复位）和冗余备份（双机，关键部件）；

39 实时系统与批处理系统和分时系统的区别 专用系统：许多实时系统是专用系统，而批处理与分时系统通常 是通用系统。
实时控制：实时系统用于控制实时过程，要求对外部事件的迅速 响应，具有较强的中断处理机构。 高可靠性：实时系统用于控制重要过程，要求高度可靠，具有较 高冗余。如双机系统。 事件驱动和队列驱动：实时系统的工作方式：接受外部消息，分 析消息，调用相应处理程序进行处理。 可与通用系统结合成通用实时系统：实时处理前台作业，批处理 为后台作业。

40 网络操作系统 (NOS, Network Operating System)
网络操作系统是在通常操作系统功能的基础上提供网络通信和网络服务功能的操作系统。网络操作系统为网上计算机进行方便而有效的网络资源共享，提供网络用户所需各种服务的软件和相关规程的集合。 网络功能与操作系统的结合程度是网络操作系统的重要性能指标。早期的作法是通常操作系统附加网络软件，过渡到网络功能成为操作系统的有机组成部分。它们的区别在于：网络功能的强弱、使用是否方便等。

41 计算机网络 一些自主的计算机系统，通过通信设施相互连接，完成信息交换、资源共享、互操作和协同工作等功能。
引入计算机网络的目的：完成新的应用（进行自动的信息交换），提高性能－价格比（共享昂贵资源）

42 网络操作系统的功能 通常操作系统的功能：处理机管理、存储器管理、设备管理、文件管理等； 网络通信功能：通过网络协议进行高效、可靠的数据传输；
网络资源管理：协调各用户使用； 网络服务：文件和设备共享，信息发布； 网络管理：安全管理、故障管理、性能管理等； 互操作：直接控制对方比交换数据更为困难；

43 分布式操作系统(Distributed Operating System)
分布式系统：处理和控制的分散（相对于集中式系统）。 分布式系统是以计算机网络为基础的，它的基本特征是处理上的分布，即功能和任务的分布。 分布式操作系统的所有系统任务可在系统中任何处理机上运行，自动实现全系统范围内的任务分配并自动调度各处理机的工作负载。

44 分布式操作系统与网络操作系统的比较 耦合程度：
分布式系统是紧密耦合系统：分布式OS是在各机上统一建立的"OS同质"，直接管理CPU、存储器和外设；统一进行全系统的管理； 网络通常容许异种OS互连，各机上各种服务程序需按不同网络协议"协议同质"。 并行性： 分布式OS可以将一个进程分散在各机上并行执行"进程迁移"； 网络则各机上的进程独立。 透明性：用户是否知道或指定资源在哪个机器上（如CPU、内存或外设）。 分布式系统的网络资源调度对用户透明，用户不了解所占有资源的位置； 网络操作系统中对网络资源的使用要由用户明确指定； 健壮性：分布式系统要求更强的容错能力（工作时系统重构）

45 个人计算机操作系统 (Personal Computer Operating System)
针对单用户使用的个人计算机进行优化的操作系统。 个人计算机操作系统的特征 应用领域：事务处理、个人娱乐， 系统要求：使用方便、支持多种硬件和外部设备（多媒体设备、网络、远程通信）、效率不必很高。 常用的个人计算机操作系统 单用户单任务：MS DOS 单用户多任务：OS/2, MS Windows 3.x, Windows 95, Windows NT, Windows 2000 Professional 多用户多任务：UNIX(SCO UNIX, Solaris x86, Linux, FreeBSD)

46 操作系统的特征 操作系统的特征 操作系统的服务 返回

47 操作系统的特征 并发(concurrency) 共享(sharing) 虚拟(virtual) 异步性(asynchronism)

48 并发(concurrency) 多个事件在同一时间段内发生。操作系统是一个并发系统，各进程间的并发，系统与应用间的并发。操作系统要完成这些并发过程的管理。并行(parallel)是指在同一时刻发生。 在多道程序处理时，宏观上并发，微观上交替执行（在单处理器情况下）。 程序的静态实体是可执行文件，而动态实体是进程（或称作任务），并发指的是进程。

49 共享(sharing) 多个进程共享有限的计算机系统资源。操作系统要对系统资源进行合理分配和使用。资源在一个时间段内交替被多个进程所用。
互斥共享（如音频设备）：资源分配后到释放前，不能被其他进程所用。 同时访问（如可重入代码，磁盘文件） 资源分配难以达到最优化

50 虚拟(virtual) 一个物理实体映射为若干个对应的逻辑实体－－分时或分空间。虚拟是操作系统管理系统资源的重要手段，可提高资源利用率。
CPU－－每个用户（进程）的"虚处理机" 存储器－－每个进程都占有的地址空间（指令＋数据＋堆栈） 显示设备－－多窗口或虚拟终端(virtual terminal)

51 异步性(asynchronism) 也称不确定性，指进程的执行顺序和执行时间的不确定性；
进程的运行速度不可预知：分时系统中，多个进程并发执行，"时走时停"，不可预知每个进程的运行推进快慢 判据：无论快慢，应该结果相同－－通过进程互斥和同步手段来保证 难以重现系统在某个时刻的状态（包括重现运行中的错误） 性能保证：实时系统与分时系统相似，但通过资源预留以保证性能

52 操作系统的服务 服务类型 程序执行和终止（包括分配和回收资源） I/O操作 文件系统操作
通信：本机内，计算机之间（通常通信服务的使用者为进程， 而不是笼统说"主机"） 配置管理：硬件、OS本身、其他软件 差错检测 服务提供方式：系统命令和系统调用

53 操作系统的功能 处理机管理 存储管理 设备管理 信息管理 用户接口 返回

54 处理机管理 完成处理机资源的分配调度等功能。处理机调度的单位可为进程或线程。
进程控制：创建、撤销、挂起、改变运行优先级等－－主动改变进程的状态 进程同步：协调并发进程之间的推进步骤，以协调资源共享；－－交换信息能力弱 进程通信：进程之间传送数据，以协调进程间的协作；－－交换信息能力强，也可以用来协调进程之间的推进 进程调度：作业和进程的运行切换，以充分利用处理机资源和提高系统性能；－－未必是进程控制操作所引起（可能是时间片轮转、I/O操作） 同一类型内的公平性、高效率（吞吐量大）、作业周转时间等

55 存储管理 管理目标：提高利用率、方便用户使用、提供足够的存储空间、方便进程并发运行。 存储分配与回收
存储保护：保证进程间互不干扰、相互保密；如：访问合法性检查、 甚至要防止从"垃圾"中窃取其他进程的信息； 地址映射（变换）：进程逻辑地址到内存物理地址的映射； 内存扩充（覆盖、交换和虚拟存储）：提高内存利用率、扩大进程 的内存空间；

56 设备管理 设备管理的目标是：方便的设备使用、提高CPU与I/O设备利用率；
设备操作：利用设备驱动程序（通常在内核中）完成对设备的操作。还需处理外设的IRQ。 设备独立性(device independence)：提供统一的I/O设备接口，使应用程序独立于物理设备，提高可适应性；在同样的接口和操作下完成不同的内容。 设备分配与回收：在多用户间共享I/O设备资源。 虚拟设备(virtual device)：设备由多个进程共享，每个进程如同独占。 缓冲区管理：匹配CPU和外设的速度，提高两者的利用率（单缓冲区、双缓冲区和公用缓冲区）

57 信息管理 解决软件资源的存储、共享、保密和保护。 文件存储空间管理：解决如何存放信息，以提高空间利用率和读 写性能。
目录管理：解决信息检索问题。文件的属性（如文件名）、单一 副本赋予多文件名 文件的读写管理和存取控制：解决信息安全问题。系统设口令“哪 个用户“、用户分类”哪个用户组“、文件权限”针对用户或用户组 的读写权" 软件管理：软件的版本、相互依赖关系、安装和拆除等

58 用户接口 目标：提供一个友好的用户访问操作系统的接口。操作系统向上提供两种接口：
系统命令：供用户用于组织和控制自己的作业运行。命令行、菜单式或GUI"联机"；命令脚本"脱机" 编程接口：供用户程序和系统程序调用操作系统功能。系统调用和高级语言库函数；

59 操作系统的结构 随着操作系统的发展，功能越强，OS自身代码量越大－－采用良好 的结构：有利于保证正确性以及自身修改和扩充。 返回

60 操作系统的设计原则 可维护性：容易修改与否称为可维护性；有三种可能的维护： 改错性维护：改正已发现的错误；
适应性维护：修改软件，使之适应新的运行环境（硬件环境和软件环境）；如：操作系统的移植。 完善性维护：增加新功能； 可靠性：可靠性包括两方面： 正确性：正确实现所要求的功能和性能； 稳健性：对意外（故障和误操作）作出适当的处理； 可理解性：易于理解，以方便测试、维护和交流； 性能：有效地使用系统资源；尽可能快地响应用户请求；

61 整体或模块结构 monolithic system or modular system
整个系统按功能进行设计和模块划分。系统是一个单一的、庞大的的软件系统。这种结构思想来源于服务功能观点，而不是资源管理的观点。 模块结构的特点：模块由众多服务过程（模块接口）组成，可以随意调用其他模块中的服务过程 优点：具有一定灵活性，在运行中的高效率 缺点：功能划分和模块接口难保正确和合理；模块之间的依赖关系（功能调用关系）复杂（调用深度和方向），降低了模块之间的相对独立性－－不利于修改

62 分层结构或虚拟机 layered system or virtual machine
从资源管理观点出发，划分层次。在某一层次上代码只能调 用低层次上的代码，使模块间的调用变为有序性。系统每加一层， 就构成一个比原来功能更强的虚拟机。有利于系统的维护性和可 靠性。

63 分层结构的特点 优点： 功能明确，调用关系清晰（高层对低层单向依赖），有利于保证设计和实现的正确性
低层和高层可分别实现（便于扩充）；高层错误不会影响到低层；避免递归调用 缺点：降低了运行效率 各系统对具体划分多少层次有不同的看法。

64 分层原则 被调用功能在低层：如文件系统管理－－设备管理－－设备驱动程序 活跃功能在低层：提高运行效率
资源管理的公用模块放在最低层：如缓冲区队列、堆栈操作 存储器管理放在次低层：便于利用虚拟存储功能 最低层的硬件抽象层：与机器特点紧密相关的软件放在最低层。如Windows NT中的HAL－－单处理、多处理 资源分配策略放在最外层，便于修改或适应不同环境 调用跨越的层次：相邻层（最严格）、所有下层、部分下层

65 客户/服务器模型或微内核结构 client-server model or microkernel
把操作系统分成若干分别完成一组特定功能的服务进程，等待客户提出请求；而系统内核只实现操作系统的基本功能(如：虚拟存储、消息传递)。 微内核(micro-kernel)：将更多操作系统功能放在核心之外，作为独 立的服务进程运行； 服务进程（或称作“保护子系统”） 客户进程（系统客户和应用客户）－－需支持多进程 本地过程调用 (LPC, Local Procedure Call)：一种进程之间请求- 应答式的消息（Message）传递机制。 消息：是一定格式的数据结构。①发起调用，送出请求消息②请求消 息到达并进行处理③送出回答消息④整理回答消息，返回结果；如： 对文件create, read, write

66 微内核模式的特点 优点： 良好的扩充性：只需添加支持新功能的服务进程即可 可靠性好：调用关系明确，执行转移不易混乱
便于网络服务，实现分布式处理：以同样的调用形式，在下层 可通过核心中的网络传送到远方服务器上 (远地过程调用 RPC, Remote Procedure Call) 缺点： 消息传递比直接调用效率要低一些 (但可以通过提高硬件性能来 补偿 ) RPC的过程：RPC应用程序－－RPC Stub(client)－－Network－－RPC Server－－进行本地调用

67 常用的操作系统 1.7.1 MS DOS 1.7.2 MS Windows 3.x, Windows 95, Windows NT, Windows 2000 1.7.3 UNIX 返回

68 MS DOS的历史 MS DOS IBM PC, CPU 8088/8086, BIOS 单用户单任务，简单分层结构，16位
1981年：PC-DOS 1.1：IBM PC，只支持软盘的个人操作系统； 1983年：DOS2.0：PC XT，支持硬盘和目录的层次结构，并提供丰富的系统命令； 1984年：DOS3.0：PC AT (Intel CPU)，它把286作为一个快速的8086使用； 1987年：DOS3.3：提供对IBM PS/2的支持（如3.5"软驱），提供了更多的应用； 1988年：DOS4.0：支持大于32M的硬盘； 1991年：DOS5.0：改进对扩展内存的支持；

69 MS DOS的结构 DOS BIOS(Basic Input/Output System)：由一组与硬件相关的设备驱动程序组成，实现基本的输入/输出功能； DOS核心：提供一套独立于硬件的系统功能：内存管理、文件管理、字符设备和输入/输出、实时时钟等； 命令处理程序：对用户命令进行分析和执行；

70 MS DOS的特点 字符用户界面。作业管理：命令行，批处理程序（BAT文件），菜单式。编程时通过软中断调用(int 21h)来使用系统功能。不区分用户。 "准多任务"：通过内存驻留程序TSR(Terminated and Stay Resident)来实现，通过时钟中断或键盘中断"热键hotkey"来激活其他任务。 不支持虚拟存储，没有存储保护。采用段式分配(内存块)，可直接访问的最大地址空间为1MB。其余的内存只能通过作为扩展内存(XMS)或扩充内存(EMS)来使用。 XMS是段式分配，通过内存数据搬移来使用XMS区域 EMS是页式分配，通过页面的映射来使用EMS区域 或者用支持保护方式的编程工具 文件系统为FAT(File Allocation Table)格式（磁盘卷，多级目录，文件名 8+3 个字符；分区容量最大为2GB）；有文件属性，没有区分用户的访问权限保护。 设备驱动程序在系统起动时加载。分为字符设备和块设备。

71 MS Windows 3.x, Windows 95, Windows NT, Windows 2000
CPU 80386 单用户多任务（分时系统），16位/16和32位混合/32位 Windows的历史 1990年：Windows 3.0（成功版本），16位OS，仿Apple Macintosh给出友好的用户界面； 1993年：Windows NT 3.1, 32位OS，支持DOS和Windows应用程序； 1999年12月：Windows 2000(Professional, Server, Advanced Server)，32位OS；

72 Windows NT体系结构

73 简化的Windows2000体系结构

74 Windows 2000的特点 支持对称多处理机 真正的32位操作系统：除16位应用的支持代码，没有16位的代码；
完全的代码可重入(reentrant)：同一段代码可由多个应用同时访问； 图形用户界面GUI（和字符用户界面）。 抢先式多任务和多线程。支持动态链接。 虚拟存储：段页式(有存储保护)。 兼容16位Windows应用： 文件系统：NTFS(HPFS)，支持安全控制 设备驱动程序：VxD(virtual driver)。 可移植：适用于多种硬件平台。 容错能力。 面向对象特性：用对象来表示所有资源。

75 UNIX的历史 UNIX 多用户多任务，16/32/64位 BSD, SVR4（模块式结构）, OSF/1（微内核结构）
1965年：MIT的Multics，由于规模和进展而没有达到目标； 1969年：AT&T，PDP-11上的16位操作系统； 1974年：UNIX系统正式发表(第五版)，在大学得到使用和好评； 1980年：University of California at Berkeley为VAX11发表BSD4.0；以后，UNIX就以AT&T和Berkeley为主分别开发，有多种变种； 1989年：UI (UNIX International)发表UNIX system V Res4.0；使BSD和System V在用户界面上统一； 1991年芬兰大学生Linus Benedict Torralds开发了第一个Linux版本。 1994年：Linux 1.0，现在的最新内核版本是2.4

76 Bell实验室 早期UNIX和C 加州大学 伯克利分校 BSD4 At&T 的系统V SCO UNIX Solaris HP-UX AIX Linux

77 传统的UNIX结构

78 现代UNIX结构

79 UNIX系统的特点 字符用户界面和图形用户界面GUI(X Window)。 抢先式多任务，多线程。支持动态链接。支持对称式多处理。
虚拟存储：段页式，有存储保护。 文件系统：多级目录，文件卷可以在子目录下动态装卸。无文件属性，可有别名。 采用设备文件的形式（读写，参数控制）。设备驱动程序修改后需要重新编译连接生成内核。 支持多种硬件平台。 易移植：主要代码用C语言写成； 变种很多，很难标准化。

80 小结 OS地位、目的、作用和组成 OS发展：主要动力 OS分类：批处理、分时、实时、（通用）、多处理、网络和分布式、PC
OS的结构：模块－－层次－－Client-Server OS的特征和服务 OS功能

81 从宏观上研究一个程序从录入到运行，最后获得运行结果的全过程 用户接口 作业的概念 作业的建立 作业的状态和调度 作业管理在OS中的地位
第二章 作业管理 从宏观上研究一个程序从录入到运行，最后获得运行结果的全过程 用户接口 作业的概念 作业的建立 作业的状态和调度 作业管理在OS中的地位

82 操作系统作为用户提供两种接口，其中一类是为一般用户提供的操作命令接口，另一类为提供给编程人员的系统调用（system call）接口
§1、用户接口 操作系统作为用户提供两种接口，其中一类是为一般用户提供的操作命令接口，另一类为提供给编程人员的系统调用（system call）接口 命令调用 系统调用 用户接口的发展

83 命令调用方式 命令形式 内部命令 系统启动时与操作系统一起装入内存——OS的一部分 例 DOS：Type,Dir,copy,……
Windows:资源管理器中的菜单、按钮，…… 外部命令 以文件形式存放，调用时装入内存 DOS：Edit,…… Windows:桌面上的图标，快捷方式（图标），……

84 使用命令的方式 联机方式：单个命令，以交互方式通过OS与计算机系统进行会话 优点：用户直接参与控制，灵活 不足：重复输入命令，繁琐且效率低 脱机方式：批命令，使用批处理命令或由命令编写的批处理文件 优点：系统按批处理要求自动执行，用户不干预，效率高 不足：不便于及时调整要执行的命令集合，灵活性差

85 系统调用 系统调用的含义 系统调用是操作系统为编程人员提供的接口，各种操作系统的核心中都设计有一组一组的用于实现各种系统功能的子程序作为机器指令的扩充。系统将这些子程序“开放”给用户，方便用户可靠地调用系统有关的资源，而用户不必从头熟悉或重新编写子程序。每当用户在程序中需要操作系统提供某种服务是，便可利用一条条相应的系统调用命令，去调用所需的系统过程。 例 DOS：库函数，…… Windows:API，……

86 系统调用的分类（书P32） 设备管理 文件管理 进程管理 进程通信 存储管理 调用中的几个概念 陷入（访管）指令—把由于系统调用引起的处理机中断的指令称为陷入（访管）指令。 用户态（目态）——处理机在用户程序中执行 系统态（管态）——处理机在系统程序中执行

87 系统调用的处理过程 访管指令有“参数区”、“参数”和“操作数”组成。“操作数”用来表示请求操作系统所要干的工作，并说明是否要有参数区和具体参数。参数或参数区的首址通常约定放在某个通用寄存器中 CPU执行到“访管”指令时，将“访管”指令存入主存中的约定单元，然后产生“访管”中断，根据参数区、参数和操作数引出操作系统来处理“访管”中的具体要求。

88 用户程序 陷入处理机构 系统子程序

89 用户接口（界面）的发展 用户界面的发展 第一代用户界面为一维界面，主要有命令行界面和编程人员在程序中的系统调用，如DOS及UNIX 均采用此种界面方式。 第二代用户界面为二维界面又称为图形界面，以窗口（windows）,图标（icon）、菜单（menu）为典型特征，由APPLE 公司开创，以Microsoft 公司的MS-Windows为里程碑，在UNIX系统下有X-window。 第三代用户界面为三维界面，又称为虚拟现实（virtual reality），如三维动画设计、可视电话及网络视频会议等。 界面管理的任务 作为面向最终用户的“作业”管理来看，用户界面已经成为计算机系统的一个重要组成部分，是计算机科学与心理学、图形艺术和人类学的交叉研究领域。寻求最佳的人机通信方式已是多媒体、虚 现实和科学计算、可视化等技术所追求的目标，也是界面管理的、最终任务。

90 §2、作业的概念 作业（job） 用户角度 我们把一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作称为一个作业。 系统角度 从计算机系统的角度看，作业是一个比程序更广的概念，它由程序、数据和作业说明书三部分组成。 系统通过作业说明书控制文件形式的程序和数据，使之操作和执行。在批处理系统中，作业是抢占内存的基本单位。也就是说，批处理系统是以作业为单位把程序和数据调入内存以便执行的。

91 作业步（job steps） 用户把要求计算机系统做的一项相对独立的工作叫做一个作业步。例如图中，编译、链接、执行就是作业步。 作业由不同的顺序相连的作业步组成，一般来说，每一个作业产生下一个作业步的输入文件。 作业同步（job synchronization） 所谓作业同步是指在一个作业中，下一个作业步能否执行下去，取决于前一个作业步是否成功完成。 作业流（job stream） 在系统控制下，将一批作业依此输入到后援存储器中等待运行，这样就形成了一个作业流。

92 作业类型（job type） 用户作业分为两大类 批量型作业可分为两种，利用作业说明书实行自动控制方式的作业称为脱机作业；利用控制台键盘操作命令直接控制的作业称为联机作业。 终端型作业又称为交互型或会话型作业，通常在分时操作系统环境下运行，用户在终端上利用键盘命令控制和监督作业的运行，而系统把作业运行的情况和结果也及时反馈在用户终端上。在大型的操作系统中，常把终端用户作业称为“前台”作业，把批量型作业称为“后台”作业。

93 作业说明书 作业说明书主要包括三方面的内容，即作业的基本描述、作业控制描述和资源要求，它由系统提供的控制命令及相关参数并按规定的语法书写 作业基本情况描述 用户名  作业名 使用语言名 允许最大处理时间 等等 作业控制描述 控制方式 操作顺序 出错处理 等等 作业资源要求描述 要求处理时间 内存空间 外存类型和数量 处理机优先级 库函数或实用程序 等等

94 作业输入方式 联机输入方式 联机输入方式大多用于交互式系统中，用户和系统通过交互会话方式输入作业。近年来由于多媒体技术（Multi-Media）的发展，逐步形成了手写输入、语音输入、光电输入等输入方式。 脱机输入方式 脱机输入方式又称为预处理方式，脱机输入方式利用低档个人计算机进行输入处理。在低档个人机上，用户通过联机方式把作业首先输入到后援存储器，如磁盘或磁带上；然后，用户把装有输入数据的后援存储器拿到主机的高速外围设备上和主机相连，从而在较短的时间内完成作业的输入。 脱机输入方式的优点是解决了作业的快进快出，相应提高了CPU的利用率。但其缺点也是明显的，主要有： 需要人工干预，出错率受人的因素影响 增加了作业周转时间 不易实现优先级调度算法

95 直接藕合方式 它用一个大容量的共用存储器，把多台用作输入的低档机、共用存储器和主机固定连接起来，保留了脱机输入方式的优点，又克服了该方式需人工干预的缺点。 低档ＰＣ机 共用存储器 主　机

96 假脱机输入方式 假脱机技术(SPOOLing或SPOOLer) SPOOLing技术实际上是一种外围设备同时联机操作技术（simultaneous peripheral operation on-line）的缩写。又称为排队转儲技术。 工作原理 SPOOLing系统既不同于脱机方式，也不同于直接藕合方式。它在输入和输出之间增加了“输入井”和“输出井”的排队转儲环节，以消除用户的“联机”等待时间。在系统输入模块收到作业输入请求信号后，输入管理模块中的读过程负责将信息从输入装置中读入输入井缓冲区。当缓冲区满时，由写过程将信息从缓冲区写到外存的输入井中，读过程和写过程反复循环，直到一个作业输入完毕。当读过程读到一个硬件结束标志之后，系统再次驱动写过程把最后一批信息写入外存输入井并调用中断处理程序结束该次输入。然后，系统为该作业建立作业控制块，从而使输入井中的作业进入作业等待队列，等待作业调度程序选中后进入内存运行。系统在管理输入井过程中可以“不断”读入输入的作业，直到输入结束或输入井满而暂停。

97 外 存 输入井 输出井 输入装置 通 道 输出装置 通 道 主机系统 输入管理 模块 输出管理 SPOOLING系统

98 网络输入方式 当用户需要从计算机网络中将 一台计算机的信息要求传送到联网的另一台主机上进行浏览（Browser）操作或执行下载（Download）等任务要求时，就构成网络输入方式。主要涉及网络通信技术。

99 §4、作业的管理和调度 作业的状态和处理流程 作业从录入到输出在计算机中经历不同的阶段，相应地处于不同的状态。状态的变化反映了作业的处理流程
见教材86页图4.1 作业控制块 - 作业控制块（JCB，Job Control Block)是系统感知作业 存在的标志

100 作业控制块的结构 作业在作业管理中是系统分配资源的基本单位，对收容状态的作业调度算法 确定何时开始执行

101 调度的层次 处理机的调度一般可以分为4级： （1）作业调度 （2）交换调度 （3）进程调度 （4）线程调度

102 作业调度功能 采用作业控制块（JCB）表格，记录系统中各作业工作状况； 根据选定的调度算法，从后备作业中选出一部分（多道情况）或一个作业投入运行； 为被选中的作业做好运行前的准备，包括建立系统相应的“进程”执行单元以及为这些“进程”分配系统资源，首先判断用户的资源要求是否能够满足； 作业处理后的善后处理工作，例如，回收资源和记帐等工作

103 作业调度中状态的转换过程 见书本89页图4.3

104 调度算法设计的目标 系统尽量大的吞吐量 CPU保持忙 I/O保持忙 对所有类型的作业尽量公平 设计调度算法要考虑的主要因素 算法应符合系统的总目标 资源使用均衡，系统效率尽量高 保证进入系统的作业在规定的时间内完成

105 短作业得到了优先执行，提高了系统的效率。 当作业不断进入时，长的作业有可能长时间等待
常用的作业调度算法 先来先服务（first come first serve,FCFS） 作业执行次序与作业进入输入井次序相同。 优点 实现简单 对相同的或均衡的作业较为合理 缺点 不利于运行时间短的作业。 最短作业优先法（shortest job fist,SJF） 最短作业优先法也就是选ti值小的优先，也就是只考虑运行时间。 短作业得到了优先执行，提高了系统的效率。 当作业不断进入时，长的作业有可能长时间等待

106 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。
最高响应比优先法（highest response-ratio next, HRN） 最高响应比优先法（HRN）是对FCFS方式和SJF 方式的一种综合平衡。HRN 调度策略调度同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比或称响应系数比R定义下： R=（W+T）/T=1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。 优点 同时具有FCFS算法及SJF 算法的优点 缺点 实现复杂，每次调度前要对所有作业扫描一遍，比较以后再调度。

107 算法评价 作业i的周转时间 Ti=作业完成时间-作业提交时间 最短周转时间=min{Ti} 最长周转时间=max{Ti} 平均周转时间 平均带权周转时间(wi0是权值，且Wi=1) 最后结束时间=max{作业完成时间} 其中Wi=Ti/Tri, Tri为执行时间

108 有5个作业，它们进入后备作业队列的到达时间如下所示，采用先来先服务的作业调度算法，求每个作业的周转时间以及它们的平均周转时间。
例题: 有5个作业，它们进入后备作业队列的到达时间如下所示，采用先来先服务的作业调度算法，求每个作业的周转时间以及它们的平均周转时间。 作业 达到时间 所需CPU时间 1 10．1 0．7 2 10．3 0．5 3 10．5 0．4 4 10．6 5 10．7 0．2

109 按照先来先服务的作业调度算法，调度的顺序为1，2， 3，4，5，每个作业的完成时间和周转时间如下所示：
解： 按照先来先服务的作业调度算法，调度的顺序为1，2， 3，4，5，每个作业的完成时间和周转时间如下所示： 作业 到达时间 所需CPU时间 完成时间 周转时间 1 10．1 0．7 10．8 2 10．3 0．5 11．3 3 10．5 0．4 11．7 1．2 4 10．6 12．1 1．5 5 10．7 0．2 12．3 1．6 不难算出它们的平均周转时间是1.2。

110 有5个作业，它们进入后备作业队列的到达时间如下所 示。采用最短作业优先的作业调度算法，求每个作业的周转时 间以及它们平均周转时间。
例题: 有5个作业，它们进入后备作业队列的到达时间如下所 示。采用最短作业优先的作业调度算法，求每个作业的周转时 间以及它们平均周转时间。 作业 达到时间 所需CPU时间 1 10．1 0．7 2 10．3 0．5 3 10．5 0．4 4 10．6 5 10．7 0．2

111 不难算出它们的平均周转时间为1.02。 解： 按照短作业优先的作业调度算法，因为作业1首先到达，首先应该调度
作业1进入内存运行，它的周转时间T1是 0.7。在它于CPU时间10.8 完成时，作业2、3、4、5都已经在后备队列中等候，因此，此时的调 度顺序应该是：5、3、4、2。作业5在时刻10.8进入内存，运行0.2 后结束，因此它的周转时间T5=(完成时间-到达时间)= =0.3， 每个作业的完成时间和周转时间如下所示： 作业 到达时间 所需CPU时间 进入内存时间 完成时间 周转时间 1 10．1 0．7 10．8 2 10．3 0．5 11．8 12．3 3 10．5 0．4 11．0 11．4 0．9 4 10．6 1．2 5 10．7 0．2 0．3 不难算出它们的平均周转时间为1.02。

112 有4个作业，它们进入后备作业队列的到达时间如下图所示，采用最高响应比优先算法，求每个作业的周转时间以及它们的平均周转时间。
例题 有4个作业，它们进入后备作业队列的到达时间如下图所示，采用最高响应比优先算法，求每个作业的周转时间以及它们的平均周转时间。 作业 到达时间 所需CPU时间 1 8．0 2 8．5 0．5 3 9．0 0．1 4 9．5 0．2

113 解： 刚开始，后备作业队列中只有作业1，因此立即将它投入运行，它于CPU时间10完成。开始重新调度时，作业2、3、4都已经达到 后备队列。根据最高响应比优先的调度算法，应该计算这一时刻 这三个作业各自具有的响应比。比如对于作业2，它是CPU时间 8.5达到后备队列的，现在是CPU时间10.0，它已经等待了 ( )=1.5。它所需的运行时间是0.5。因此该时刻它的响 应比是1.5/0.5=3。下表给出了这一时刻三个作业各自的已等待 时间和响应比。由于这是作业3具有最高的响应比，因此它是第2个调度的对象。

114 作业 到达时间 所需CPU时间 已等待时间 响应比 2 8．5 0．5 1．5 3 9．0 0．1 1 10 4 9．5 0．2 2．5 当前CPU时间=10.0

115 作业3在CPU时刻10.1运行完毕，作业2和作业4是参与调
度的对象，此时，它们的已等待时间和各自响应比如下表所示。可以看出，这次选中的应该是作业2，因为它的响应比是3.2。 作业 到达时间 所需CPU时间 已等待时间 响应比 2 8．5 0．5 1．6 3．2 4 9．5 0．2 0．6 3 当前CPU时间=10.1

116 作业2在CPU时刻10.6完成.作后调度运行的作业是作业4,它在CPU 时刻10.8完成.于是,这4个作业的完成时间和周转时间如下表所示:
进入内存时间 完成时间 周转时间 1 8.0 10.0 2 10.1 10.6 2.1 3 1.1 4 10.8 1.3 这4个作业的平均周转时间为1.625。

117 例 假设某多道程序设计系统有供用户使用的主存空间100K，磁带机2台，打印机1台。系统采用可变分区方式管理主存，对磁带机和打印机采用静态分配。现有一作业序列如下：

118 假设采用先进先出调度算法，优先分配主存的低地址区且不准移动已在主存中的作业，在主存中的作业平分CPU时间。请回答：
作业调度的次序 最大的作业周转时间 最小的作业周转时间 作业平均周转时间 作业全部执行结束的时间

119 作业执行分析

120 作业调度的次序：1，3，4，2，5 周转时间计算 最大的作业周转时间=55分钟 最小的作业周转时间=30分钟 作业平均周转时间=43分钟 作业全部执行结束的时间=9:30

121 §5、作业管理在OS中的地位 作业管理是OS中对业务处理的宏观管理
分时系统中，由于人机交互，作业管理的功能减弱，各作业步常由交互方式由人工控制和完成。 通用OS中，有作业管理模块。用户可以选择人机交互方式或作业管理方式。

122 重点小结 熟悉人机界面的发展特点。 利用种操作系统（DOS、Windows、UNIX或Linux），来体会操作系统的功能。 掌握系统调用的原理及基本的系统调用的使用。 通过上机练习掌握作业调度算法的模拟编程。 掌握调度算法的基本评价方法和评价参数计算

123 第三章 进程与处理机管理 处理机（CPU）是计算机系统的重要资源，提高CPU的效率是提高整个系统效率的关键。CPU的管理是OS的核心内容。
第三章 进程与处理机管理 处理机（CPU）是计算机系统的重要资源，提高CPU的效率是提高整个系统效率的关键。CPU的管理是OS的核心内容。 进程及其基本特征 进程描述及状态 进程控制 进程调度 进程互斥与同步 进程通信 死锁 线程 处理机管理

124 §1、进程及其基本特征 程序执行分析 程序顺序执行 将具有独立功能的程序独占处理机运行直到得到最终结果称为程序顺序执行 特点
顺序性：程序按预先的逻辑顺序依次执行 封闭性：程序的执行结果由初始条件确定，不受外界影响 可再现性：程序的执行结果与它执行的速度、环境无关 资源独占：程序执行时独占CPU 假设程序A={IA，PA，OA}，B={IB，PB，OB}。A、B的顺序执行为： IAPA  OA  IB  PB  OB 总的执行时间TS=TA+TB

125 程序并行执行 多个程序的执行与其它程序无关，它们独占各自的CPU 特点：顺序、封闭、可再现、资源独占、多个CPU 对前述的程序A、B，其并行执行为： IA  PA  OA IB  PB  OB 总的执行时间TP=max{TA，TB }

126 即：PA与IB，OA与PB在时间上重叠，这时只需一个CPU就可以了。 总的执行时间TM= T(IA)+max{T(PA), T(IB)}
程序并发执行 例 对前述的程序A、B，若执行为： IA  PA  OA IB  PB  OB 即：PA与IB，OA与PB在时间上重叠，这时只需一个CPU就可以了。 总的执行时间TM= T(IA)+max{T(PA), T(IB)} +max{T(OA), T(PB)}+T(OB) 显然: TS > TM > TP ,在不增加系统资源的条件下， TM对应的执行方式较顺序执行（TS）效率高 一组在逻辑上互相独立的程序（程序段）在执行过程中其执行时间在客观上互相重叠，即一个程序（程序段）的执行尚未结束，另一个程序（程序段）的执行就已开始的执行方式称为程序的并发执行。

127 特点 间断性：就CPU来看程序的执行是不连续的 非封闭性：程序的执行结果与初始条件相关，同时受外界影响 不可再现性：程序的执行结果与它执行的速度、环境有关 资源共享：多个程序的执行共享CPU 例: procedure getdata(a) begin L1: a  (top) L2: top  top-1 end procedure setdata(b) L3: top  top-1 L4: (top) b

128 当getdata与setdata并发执行时其结果不再具有封闭性和可再现性。考虑如下执行序列时的结果： L1 L2 L3 L4
为确保并发执行的程序其结果具有封闭性和可再现性，必须协调各程序间的执行速度，即对并发执行进行一定的限制。 顺序执行与并发执行的比较

129 数据集——接受程序规定操作的一组存储单元的内容
进程 定义 一个具有独立功能的程序（程序段）对某个数据集在处理机上的执行过程和分配资源的单位——称进程 程序（程序段）——一个操作序列 数据集——接受程序规定操作的一组存储单元的内容 特征 动态性：进程是程序在并发系统的一次执行，一个进程有一个从产生到消失的生命期； 并发性：正是为了描述程序在并发系统内执行的动态特征才引入了进程，没有并发就没有进程 独立性：每个进程的程序都是相对独立的顺序程序，可以按自己的方向和速度独立地向前推进 制约性：进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯 结构性：进程=PCB（进程控制块）+程序+数据集合。

130 程序与进程的对比 程序与进程的类比

131 §2、进程的描述及状态 系统为感知、操作、控制进程，需要对其描述，以说明其执行环境。 描述的含义
系统中用于描述进程存在和反映其变化的物理实体——进程静态描述 描述的内容 进程控制块（PCB，Process control block）——系统感知进程的唯一实体 程序（程序段）——进程完成的功能 数据结构集——执行时的工作区和操作对象

132 进程控制块（PCB） 作用 系统感知进程的标识 反映进程的动态特征 与进程一一对应，常驻内存 进程控制块将构成并发执行控制和维护系统工作的依据 组成 描述信息 进程名或进程标识号——识别进程 用户名或用户标识号——进程隶属的用户 家族关系——进程树 控制信息 当前状态 优先级别 程序开始地址 计时信息 通信信息

133 PCB基本信息 资源管理信息 占用内存大小及管理用数据结构指针 对换或覆盖信息 共享程序段大小及起始地址 I/O设备相关信息
指向文件系统的指针及有关标识 CPU现场保护区 PCB基本信息

134 进程上下文是进程执行活动全过程的静态描述 进程上下文结构
层次结构 正文集 PCB 各种控制表指针 数据集 栈 区 各种寄存器 PCB结构 虚存与实存映射表 核心栈：系统调用序列 进程上下文 用户级上下文 系统级上下文 用户程序段 用户数据段 用户堆栈 …… 静态部分 动态部分：相关寄存器及其值

135 进程状态 一般来说，一个进程在它的生命周期有三种基本状态，分别为就绪(ready)、执行(execute)和等待(waiting)。一个进程在刚创建初期处于“进入”状态，在运行终止后处于“完成”状态。 就绪——进程具备运行条件，但尚未占用CPU，即进程已拥有除CPU外运行所需的全部资源 执行——进程正在占用CPU 等待——进程由于等待 某一事件不能享用CPU，即进程除CPU外还等待获得其它资源

136 进程状态转换 随着资源在进程间的重新分配，进程的状态将发生变化。引起状态变化的原因有： CPU调度（低级调度）：CPU调度按某种原则从就绪队列中调度一个进程到CPU上运行，该进程就从就绪状态变为运行状态；与此同时，原运行进程从运行状态变为就绪状态。因此，这两种状态变化是同时发生的。 进程在运行过程中需要等待某一事件，例如，等待分配某一资源，等待I/O操作完成等。一个进程在需要等待某一事件时主动退出CPU，并使自己处于阻塞状态，引起状态变化。 如果进程所等待的事件发生了变化，例如，一次I/O完成了，于是进程便被解除阻塞状态，变为就绪状态。 一个具体的进程在任何一个指定的时刻必须而且只能处于一种状态。

137 进程除上述基本状态外，不同的OS为更好地管理系统资源扩展了一些状态，如：
状态转换图 撤消 就绪 执行 等待 创建 调度/获得CPU 阻塞/等待资源 唤醒/获得资源 失去CPU 进程除上述基本状态外，不同的OS为更好地管理系统资源扩展了一些状态，如： 就绪 内存就绪 外存就绪 执行 管态 目态 设备等待 文件等待 数据等待 内存等待 等待

138 含有挂起状态的状态转换 就绪挂起 挂起 释放 撤消 执行 调度/获得CPU 创建 失去CPU 就绪 阻塞/等待资源 唤醒/获得资源 等待
等待挂起 挂起 释放

139 进程状态转换的说明 进程之间的状态转换并非都是可逆的。进程既不能从等待变为运行，也不能从就绪变为等待。 进程之间的状态转换并非都是主动的，在很多情况下都是“它动的”。事实上，只有运行到等待的转换是进程的主动行为（主动调用调度管理程序），其它都是它动的，例如，从执行到就绪，通常是时钟中断引起的，从等待到就绪，是一个进程把另一个进程唤醒。 进程组织 进程家族 相关进程按父子关系组织成层次结构 子进程又父进程创建并继承父进程的资源 撤消一个进程时，其子孙进程一并被撤消 状态队列 进程按其状态形成队列 一种状态一个队列

140 §3、进程控制 进程控制的任务 创建、撤消进程及完成进程各状态间的转换，从而达到多进程高效率并 发执行和协调、实现资源共享的目的 原语
系统态下执行的某些具有特定功能的程序段——原语 分类 机器指令级：执行期间不允许中断 功能级：不允许并发执行 特点：不可分割，或者全执行或者不执行 作用： 在系统态下执行，且都是为了完成某个系统管理所需要的功能和被 高层软件调用 在操作系统中，一般都把进程控制用的程序段做成原语，用于进程控制 的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等

141 进程的创建 创建方式 由系统统一创建。例如在批处理系统中，由操作系统的作业调度程序为用户进程创建相应的进程以完成用户作业所要求的功能。 由父进程创建。例如在UNIX操作系统中，父进程创建子进程以完成并行工作。

142 创建原语 入口 查PCB链表 无 有空PCB 创建失败 有 取空表PCB(i) 将参数添入PCB(i) PCB(i)入就绪队列
返回 创建失败 有 无

143 撤消进程 原因 该进程已完成所要求的功能——正常终止 由于某种错误导致进程撤消——非正常终止 祖先进程要求撤消子孙进程——非正常终止 方法 调用撤消原语 注意：谁调用撤消原语

144 撤消原语 入口 查进程链表或进程家族 有此PCB 释放该进程占有的资源 释放该PCB结构 返回 出错处理 有 无 该PCB有子进程

145 原因：资源请求且未被满足。资源可以是：输入数据，写数据到设备，与其它进程交换数据，…… 注意：谁调用阻塞原语 阻塞原语
进程阻塞 原因：资源请求且未被满足。资源可以是：输入数据，写数据到设备，与其它进程交换数据，…… 注意：谁调用阻塞原语 阻塞原语 入口 保存当前进程的CPU现场 置该进程的状态 进程入等待队列 转进程调度

146 由系统进程唤醒：系统统一控制事件的发生并将“事件发生”这一消息通知等待进程。
原因：请求的资源被满足 进程唤醒方法 由系统进程唤醒：系统统一控制事件的发生并将“事件发生”这一消息通知等待进程。 由事件发生进程唤醒：在这种情况下，事件发生进程和唤醒进程之间是合作关系。 唤醒原语 入口 从等待队列中摘下被唤醒进程 置被唤醒进程的状态 被唤醒进程入就绪队列 转进程调度或返回

147 §4、进程调度 进程调度被认为是系统中的低级调度，其目的是按照一定的策略和方法将 处理机分配给某个就绪进程并为该进程的执行准备环境
进程调度的功能 记录系统中所有进程的执行情况 选择占有处理机的进程 调度策略与算法 进程上下文切换 保存正在执行进程的现场，为将要执行的进程准备现场 处理机回收 进程被撤消后须回收被占用的处理机

148 进程调度的时机 正在执行中的进程执行完毕 正在执行中的进程被阻塞 分时系统中时间片用完 执行完系统调用等系统程序后返回用户进程时 更高优先级的进程处于就绪状态 进程调度中的上下文切换 进程在其上下文所确定的环境中运行，当执行的进程发生改变或出现进程调度时，需要进行上下文切换 上下文切换的内容 决定是否做或是否允许做上下文切换 切换上下文——原则是不破坏原进程的上下文 处理机切换

149 进程调度算法 先来先服务（FCFS，first come first service） 这种调度算法按照进程进入就绪队列的先后顺序来调度进程。获得处理机的进程，未遇到其他情况时，一直运行下去。系统只需具备一个先进先出的队列，这种方法是一种最常见策略，并且在没有其他信息时，也是一种最合理的策略。 优点是实现简单 缺点是对那些执行时间较短的进程来说，将等待较长的时间，从而降低CPU的利用率。 在实际操作系统中，FCFS算法常常和其它的算法配合起来使用，例如，基于优先级的调度算法就是对具有同样优先级的进程采用FCFS算法。

150 轮转调度（RR，round robin） 轮转调度算法是系统把所有就绪进程按先后次序排队，处理机总是优先分配给就绪队列中的第一个就绪进程，并分配它一个固定的时间片（如100毫秒）。当该运行进程用完规定的时间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程，分给这个进程相同的时间片，每个运行完时间片的进程，当未遇到任何阻塞时，就回到就绪队列的尾部，并等待下次转到它时再投入运行。于是，只要是处于就绪队列中的进程，按此种算法迟早总可以分得处理机投入运行。 轮转法只能用来调度分配那些可以抢占的资源。这可以抢占的资源可以随时剥夺，而且可以将它们再分配给别的进程。CPU是可抢占的资源的一种。但打印机等是不可抢占的资源。另外，时间片长度的选择是根据系统对响应时间的要求和就绪队列中所允许的最大进程数确定的。

151 每个队列分配不同的时间片（如，t,2t,3t,……） 在这些队列中轮流进行进程调度 把所有就绪进程按下述方法排成n个队列
多级反馈轮转法（RRMF，round robin with multiple feedback） 算法1 把所有就绪进程按下述方法排成多个队列 新创建的与时间片用完的进程队列 发生I/O请求的队列 其它情况的队列 每个队列分配不同的时间片（如，t,2t,3t,……） 在这些队列中轮流进行进程调度 算法2 把所有就绪进程按下述方法排成n个队列 第k次被调度的进程时间片用完后被放入第 ((k+1) mod n)+1 个队列 新创建的进程放入第一个队列 依次调度第一个，第二个，……，第n个队列中的进程执行

152 为每个进程分配一个优先级，调度时总是调度优先级最高的进程执行
优先级算法 算法 为每个进程分配一个优先级，调度时总是调度优先级最高的进程执行 当出现比当前正在执行的进程优先级更高的就绪进程时，调度该进程执行，原执行进程的状态转换为就绪 优先级确定方法 静态优先级的确定 用户指定作业的优先级，与之相关的进程有相同的优先级 系统进程较用户进程有更高的优先级 系统根据进程的类别设置优先级，如：I/O繁忙类，CPU繁忙类，I/O与CPU均衡类，…… 动态优先级的确定 进程占有CPU时间越长，被阻塞后再次称为就绪状态时，优先级越低 就绪进程等待执行的时间越长，其优先级越高

153 调度算法评价 定性评价 调度算法可靠性 是否回引起系统故障，上下文破坏等 调度算法简洁性 算法实现是否容易等 定量评价（书P87） CPU利用率 进程响应时间 ……

154 §5、进程互斥与同步 进程间的制约 例1 进程1、进程2共享打印机缓冲区（公有资源），显然它们应互斥地向缓冲区写数据——间接制约 例2
进程1、进程2共享它们之间的缓冲区（私有资源），显然应同步地使用缓冲区——直接制约 进程1 进程2 打印机缓冲区 写 进程1 进程2 缓冲区 写 读

155 一组在异步环境下的并发进程，由于不允许并发进程交叉使用共享公有资源，从而限制各进程的执行速度的过程称为并发进程间的间接制约
产生制约的原因 进程并发执行——>资源共享 资源有限——>资源竞争 制约的分类 间接制约（由共享和竞争公共资源引起的制约） 一组在异步环境下的并发进程，由于不允许并发进程交叉使用共享公有资源，从而限制各进程的执行速度的过程称为并发进程间的间接制约 直接制约（由共享和竞争私有资源引起的制约） 一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发执行进程间的直接制约 互斥：因间接制约而形成的进程执行方式 同步：因直接制约而形成的进程执行方式

156 临界资源与临界区 临界资源 任意时刻只允许一个进程使用的资源 如：打印机、键盘、一些数据、表格、队列等 临界区 访问临界资源的程序（程序段），即不允许并发进程交叉执行的程序（程序段） 如：写打印机缓冲区的程序，…… 临界资源的访问方式——互斥

157 进程互斥执行应满足的准则 不能假设各并发进程的相对执行速度 各并发进程享有平等的、独立的竞争和使用共有资源的权利 在不采取任何措施的条件下，在临界区内任一指令结束时，其它并发进程可以进入临界区 并发进程中的某个进程不在临界区时，它不阻止其它进程进入临界区 并发进程中的若干个进程申请进入临界区时，只允许一个进程进入 并发进程中的某个进程从申请进入临界区开始，应在有限时间内进入临界区，也应在有限时间之内退出临界区

158 当有进程进入临界区时，设置锁的状态为关(s=0) 当进程从临界区退出时，设置锁的状态为开(s=1) 只有锁的状态为开时，进程才能进入临界区
进程互斥的实现方法 加锁实现 原理 锁的初始状态为开(s=1) 当有进程进入临界区时，设置锁的状态为关(s=0) 当进程从临界区退出时，设置锁的状态为开(s=1) 只有锁的状态为开时，进程才能进入临界区 加锁后的临界区程序 lock (s) 临界区 unlock (s) 代码 function lock (s) function unlock (s) { { repeat until s= s=1 s= } }

159 当Lock的执行结束，s=0执行之前时间片到，或者CPU被强占，会出现什么情况？如何解决？
分析 当Lock的执行结束，s=0执行之前时间片到，或者CPU被强占，会出现什么情况？如何解决？ 不足： 只要有一个进程由于执行LOCK（S）而进入临界区，则其它进程在检查锁状态时都将反复执行LOCK（S）原语，从而导致处理机繁忙。

160 信号量 例 交通系统中的信号灯——它表示当前道路是否可以通行 信号量——某种资源可以使用的状况，用整型变量s表示 s>0——资源还有s个可供使用 s=0——资源也用尽 s<0——有| s |个进程等待使用资源 例：设S表示系统中可使用的打印机数量，有 S=1——表示还有一台打印机可供使用 S=0——表示目前没有打印机可供使用 S=-1——表示有一个进程等待使用打印机

161 P、V操作（信号量操作） 用P、V操作来修改信号量S的值 P操作 入口 S=S-1 调用进程入等待队列 S>=0 转进程调度
调用进程继续执行 是 否

162 唤醒等待队列中的一个进程，并置状态为就绪
V操作 考虑：这里的等待队列因请求什么资源而等待？ 入口 S=S+1 唤醒等待队列中的一个进程，并置状态为就绪 S<=0 调用进程继续执行 是 否

163 S对应的资源同一时刻最多只能有一个进程使用 访问资源前调用P操作，访问结束时调用V操作 PA PB … …… P P(S)
原理 设信号量S为全局变量，初值为S=1 S对应的资源同一时刻最多只能有一个进程使用 访问资源前调用P操作，访问结束时调用V操作 使用资源的两个互斥进程描述为 PA PB … …… P P(S) <资源调用> <资源调用> V(S) V(S) …… ……

164 例：怎样使用PV操作管理交通路口的自动计数系统。
定义一个信号量S，初始值为1，则程序描述如下： begin count:integer; count:=0; s:semaphore; s:=1; cobegin PROCESS Observer L1:observer a lorry; P(S); count:=count+1; V(S); goto L1 end; PROCESS Reporter begin P(S); print count; count:=0; V(S) end; coend; End;

165 例：怎样使用PV操作管理航空售票系统。请阅读下面的程序，并找出其中的问题。
begin s:semaphore; s:=1; cobegin PROCESS Pi(i=1,2,3,…,n) {按旅客要求找到Ai}; P(S); Ri:=Aj; if Ri≥1 then begin Ri:=Ri-1; Aj:=Ri; V(S); {输出一张票} end else {输出“票已经售完”} end; coend; ….. begin {按旅客要求遭到Ai}; P(S); Ri:=Aj; if Ri≥1 then begin Ri:=Ri-1; Aj:=Ri; V(S); {输出一张票} end else {输出“票已经售完”} end;

166 以上程序有缺陷，请仔细阅读并改正。 begin s:semaphore; s:=1; rc:integer; rc:=0; cobegin
例：读者-写者问题。 假设有一个共享文件，系统允许进程对文件F读或写，但规定： （1）多个进程可以同时读文件。 （2）任一个进程在对文件F进行修改时不允许其它进程对文件进行读或修改。 （3）当有进程在读文件是不允许任何进程去修改文件。 begin s:semaphore; s:=1; rc:integer; rc:=0; cobegin PROCESS Readeri(i=1,2,…) rc:=rc+1; if rc=1 then P(S); read file F; rc:=rc-1; if rc=0 then V(S) end PROCESS Writeri(i=1,2,…) begin P(S); writer file F; V(S); end coend; end; 以上程序有缺陷，请仔细阅读并改正。

167 l begin s,sr:semaphore; rc:integer; s:=1; sr:=1; rc:=0; cobegin
修改之后的程序为： begin s,sr:semaphore; rc:integer; s:=1; sr:=1; rc:=0; cobegin PROCESS Readeri(i=1,2,…) P(sr); rc:=rc+1; if rc=1 then P(S); V(sr); read file F; rc:=rc-1; if rc=0 then V(S) end PROCESS Writeri(i=1,2,…) begin P(S); writer file F; V(S); end coend; end;

168 显然PC与PP在执行时必须协调速度，即对Buf的操作应该是：PC写，PP取， PC写，PP取， PC写，PP取，…… 问题要求PC与PP同步
进程同步的实现 例 计算进程PC将计算结果写到缓冲区Buf中，打印进程PP从Buf中取出数据进行打印。要求是 只有Buf为空时，PC才能写入数据； 只有Buf为满时，PP才能取出数据 从Buf中取出数据后，Buf为空 初始时Buf为空 分析 显然PC与PP在执行时必须协调速度，即对Buf的操作应该是：PC写，PP取， PC写，PP取， PC写，PP取，…… 问题要求PC与PP同步 实现同步的方法可以是 PP等PC写之后再取 PC等PP取之后再写

169 设Buf有两个状态：Bufempty，Buffull 用State记Buf的状态…… PP与PC为 PP PC …… ……
求解 设Buf有两个状态：Bufempty，Buffull 用State记Buf的状态…… PP与PC为 PP PC …… …… repeat repeat until State=Bufempty until State=Buffull 计算 取出Buf中的内容 Buf  计算结果 Buf清空 State=Buffull State=Bufempty …… …… 上述Bufempty，Buffull成为PP与PC之间的公用变量，但对系统或其它进程来讲并不知道它们的存在，故称其为PP与PC的私有信号量

170 <使用同步资源> <使用同步资源> V(T) V(S) …… ……
用P、V操作实现进程同步 原理 为并发进程设置信号量， 初始化它们的值 用P、V操作限定进程的执行顺序 同步进程的模式 PA PB …… …… P(S) P(T) <使用同步资源> <使用同步资源> V(T) V(S) …… …… 这里，S、T的初值根据具体问题确定

171 例 前述例子中，设初始值S=1，T=0 PP PC …… …… P(S) P(T) Buf  计算结果 Buf清空 V(T) V(S)

172 生产者进程向缓冲区中写数据，每次写一个单元 消费者进程读缓冲区中的数据，每次写一个单元 缓冲区至少有一个单元有数据（满）时，才能读
生产者—消费者问题 进程互斥和同步问题可以抽象为生产者—消费者问题 生产者生产出产品后，消费者才能消费 当部分产品消费后，生产者才继续生产 一件产品，不能既在生产又在消费 该问题可形式化为 有界缓冲区共n个单元 生产者进程向缓冲区中写数据，每次写一个单元 消费者进程读缓冲区中的数据，每次写一个单元 缓冲区至少有一个单元有数据（满）时，才能读 缓冲区至少有一个单元无数据（空）时，才能写 生产者进程与消费者进程不能同时操作缓冲区 生产与消费同步 生产与消费互斥 P1 p2 … Pn ……

173 设生产者进程的私有信号量：avail——当前可用的缓冲区单元数，初值为n
假设：PA——生产者进程， PB——消费者进程 生产者与消费者的互斥 设公共信号量：mutex，初值为1 PA PB …… …… P（mutex） P（mutex） 生产者生产 数据  缓冲区 缓冲区  数据 消费者消费 V（mutex） V（mutex） …… …… 生产者与消费者的同步 设生产者进程的私有信号量：avail——当前可用的缓冲区单元数，初值为n 设消费者进程的私有信号量：full——缓冲区中有数据的单元数，初值为0 生产者与消费者的同步为：

174 PA PB …… …… P（avail） P（full） 生产者生产 数据  缓冲区 缓冲区  数据 消费者消费
…… …… P（avail） P（full） 生产者生产 数据  缓冲区 缓冲区  数据 消费者消费 V（full） V（avail） …… …… 生产者与消费者问题的解 P（avail） P（full） P（mutex） P（mutex） 生产者生产 数据  缓冲区 V（full） V（avail） V（mutex） V（mutex） …… ……

175 问题 设有三个进程R,W1,W2，共享一个缓冲器B，B中每次只能存放 一个数，进程R每次启动输入设备读一个数并且把它存在缓冲 器B中。若存放到缓冲器的数是奇数，则由W1进程打印，否则 则由W2进程打印。同时规定进程R仅当缓冲器无数时或缓冲器 中的数已经被打印后才能存放新的数；W1和W2对缓冲器中的 内容不能重复打印，也不能冲空的缓冲器中取数。要求用PV操 作管理者三个并发进程，是它们能正确的工作。 S:表示是否可以把数存入缓冲器。 SO:表示缓冲器中是否有奇数，初值为“0”，表示无奇数。 SE:表示缓冲器中是否有偶数，初值为“0”，表示无偶数。

176 PRECESS W1 y:integer; begin L2:P(SO); y：=B； V(S); {打印y中的数}； goto L2； end; Begin S,SO,SE:semaphone; B:integer; S:=1;SO:=0;SE:=0; Cobegin PRECESS R x:integer; begin L1:{从输入设备读一个数} x：=读入的数； P(S); B:=X; if B=奇数 then V(SO) else V(SE) goto L1 end; PRECESS W2 z:integer; begin L3:P(SE); z：=B； V(S); {打印z中的数}； goto L3； end; coend; End;

177 例题2 有m个生产者和r个消费者共享容量为n的缓冲器 ，每个生产者都要把各自生产的物品存入缓冲 器，而每个消费者都要从缓冲器中取出物品去
消费。要求用PV操作对这些生产者和消费者进 行正确管理。 定义四个信号量如下： S1:互斥信号量，用于m个生产者之间互斥； S2:互斥信号量，用于r个消费者之间互斥； SP与SG为同步信号量；

178 Begin B:array[0..m] of integer; k,t:integer; S1,S2,SP,SG:semaphone; K:=0;t:=0; s1:=1;s2:=1;SP:=n;SG:=0; Cobegin PROCESS produceri(i=1,2,…,m) begin L1:produce a product; P(SP); P(S1); B[k]:=product; k:=(k+1)mod n; V(S1); V(SG); goto L2 End; PROCESS consumeri(i=1,2,…,r) begin L2: P(SG); P(S2); take a product from B[t]; t:=(t+1)mod n; V(S2); V(SP); comsume; goto L2 End; coend’;

179 §6、进程通信 通信——指进程间相互传递信息（数据） 分类 低级通信 传送控制信息，一般为一个或几个字节，目的是控制进程的速度
如：信号量，锁，…… 高级通信 传送大量数据，目的是交换信息（数据） 如：消息，查询结果，……

180 通信方式与特点 主从式 通信的进程被分为主进程和从进程 特点 主进程可以自由地使用从进程的资源或数据 从进程的动作受主进程的控制 主进程与从进程的关系是固定的 例 终端控制进程与终端进程

181 会话式 通信的进程分别称为使用进程和服务进程。使用进程调用服务进程提供的服务 特点 使用进程在使用服务进程之前必须得到服务进程的许可
服务进程按使用进程的要求提供服务，对所提供服务的控制由服务进程完成 在每次通信时，服务进程与使用进程间的关系是固定的 服务进程与使用进程在不同的通信中关系是可变的 例 用户进程与磁盘管理进程间的通信

182 只要存在空缓冲区或邮箱，发送进程就可发送消息 发送与接收进程无直接联系，甚至可以不知道对方的存在 通过缓冲区或邮箱来存放被传送的消息
消息或邮箱机制 通信进程分为发送进程和接收进程，它们是平等的 进程间通过缓冲区或邮箱交换大量信息 组成 消息 缓冲区或邮箱 特点 只要存在空缓冲区或邮箱，发送进程就可发送消息 发送与接收进程无直接联系，甚至可以不知道对方的存在 通过缓冲区或邮箱来存放被传送的消息 发送进程 接收进程 操作 数据 …… PS PR 缓冲区或邮箱

183 共享存储区方式 通信进程通过对同一共享数据区的操作来交换信息 特点 共享数据区是每个互相通信进程的一个组成部分 传送的数据量大，速度快 注：无论那种通信方式，都需要解决进程间的同步或互斥

184 在自己的内存空间申请发送缓冲区 将数据填入缓冲区 发送——将缓冲区挂入消息队列 在自己的内存空间申请接收缓冲区 接收——摘取消息队列中的消息
消息缓冲通信 原理 发送进程 在自己的内存空间申请发送缓冲区 将数据填入缓冲区 发送——将缓冲区挂入消息队列 接收进程 在自己的内存空间申请接收缓冲区 接收——摘取消息队列中的消息 约束 发送进程写缓冲区和消息队列时，禁止其它进程访问该缓冲区与消息队列 接收进程取消息队列时，禁止其它进程访问该消息队列 发送进程申请不到缓冲区时，不能发送 消息队列为空时，接收进程不能接收消息

185 甲进程在发送消息前，在本进程所占空间中开辟一发送区； 使用send原语
甲乙两进程的发送与接收过程 甲进程发送过程 甲进程在发送消息前，在本进程所占空间中开辟一发送区； 使用send原语 send程序向系统申请一个消息缓冲区，将发送区中消息正文、长度和发送进程名填入； 将缓冲区挂到接收消息的乙进程消息链链尾； 退出send，甲进程继续执行 乙进程接收过程 乙进程在接收消息前，在本进程所占空间中开辟一接收区； 使用receive原语 receive程序将乙进程消息链区中第一个消息缓冲区中的内容、长度、本消息发送者名字，填入接收区； 将缓冲区从消息链中摘除，释放缓冲区； 退出read程序，乙进程继续执行

186 Begin 向系统申请一个消息缓冲区 P(mutex) 将发送区消息m送入新申请的消息缓冲区 将消息缓冲区挂入接收进程的消息队列
Send(m)： Begin 向系统申请一个消息缓冲区 P(mutex) 将发送区消息m送入新申请的消息缓冲区 将消息缓冲区挂入接收进程的消息队列 V(mutex) V(SM) End Receive(n)： P(SM) 摘下消息队列中的消息n 将消息n从缓冲区复制到接收区 释放缓冲区 ?信号量的初值确定

187 邮箱头：描述邮箱名称、大小、方向、拥有该邮箱的进程 邮箱体：存放消息
邮箱通信 原理 由发送进程申请建立一个与接收进程相连接的邮箱 发送进程将消息送往邮箱，接收进程从邮箱中取走消息 邮箱组成 邮箱可以设置成发送与接收进程之间大小固定的私有数据结构 邮箱由邮箱头和邮箱体组成 邮箱头：描述邮箱名称、大小、方向、拥有该邮箱的进程 邮箱体：存放消息 发送进程 接收进程 邮箱头 …… 邮箱体

188 通信要求 发送消息时，至少邮箱中有一个空格能存放该消息 接收消息时，至少邮箱中有一个消息存在 发送进程与接收进程 设formnum为邮箱中空格数，mesnum为邮箱中消息数 Deposit(m) Remove(m) begin begin P(formnum) P(mesnum) 选择一个空格x 选择一个满格x 将消息m放入x 将x中的消息放入m 置x的标志为满 置x的标志为空 V(mesnum) V(formnum) end end ? Formnum与mesnum的初值是什么 Deposit与Remove之间是同步？互斥？其它？ 多个Deposit间是同步？互斥？其它？ 多个Remove间是同步？互斥？其它？

189 §7、死锁 死锁的概念 死锁是两个或两个以上的进程中的每一个都在等待其中另一个进程释放资源而被封锁，它们都无法向前推进，陷入永久等待状态，这种现象称为死锁。 特点 占有一定的资源，等待对方释放资源 获得对方资源前不释放自己占有的资源 比较：死锁与死循环，死锁与死机 P1 P2 请求 请求 拥有 拥有 S1 S2

190 死锁的起因 资源有限 系统提供的资源个数少于并发进程所需要的该类资源数 资源竞争 进程的并发性造成对资源的竞争使用。一般我们不可能为所要求资源的进程无限制地提供资源。 关于死锁的进一步说明 死锁是进程之间的一种特殊关系，是由资源竞争引起的僵局关系，因此，当我们提到死锁时，至少涉及到两个进程。虽然单个进程也可能锁住自己，但那是程序设计错误而不是死锁 当出现死锁时，首先要弄清楚被锁的是哪些进程，因竞争哪些资源被锁 在多数情况下，系统出现死锁，是指系统内的一些而不是全部进程被锁，它们是因竞争某些而不是全部资源而进入死锁的，若系统的全部进程都被锁住，我们称系统处于瘫痪状态 系统瘫痪意味着所有进程都进入了睡眠（阻塞）状态，但所有进程都睡眠了，如果其中至少有一个进程可由I/O中断唤醒的话，这并不一定就是瘫痪状态

191 产生死锁的必要条件 互斥条件 在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待直至其占用者释放——资源的互斥使用 部分分配 进程每次申请它所需资源的一部分，在申请分配或等待新资源的同时继续占有已分配的资源 不剥夺条件 进程所获得的资源在未使用完之前，不能被其它进程强行夺走，而只能由获得资源的进程自己释放； 环路条件 存在一个等待资源的进程循环链，链中的每个进程所获得的资源是下一个进程申请（等待）的资源 显然，上述条件中的任意一个不满足，死锁就不会发生

192 死锁的表示 死锁可以用有向图来表示，有向图形成环路则形成死锁。例如，有P1，P2两个进程，共享一台打印机资源R1和一台输入机R2，在工作使用时，共享资源被独占。 死锁定理 如果不出现任何环，则此时系统内不存在死锁 如果出现了环，且处于此环中的每类资源均只有一个实体时，则有环就出现死锁，此时，环是系统存在死锁的充分必要条件 如果系统资源分配图中出现了环，但处于此环中的每类资源的个数不全为1，则环的存在只是产生死锁的必要条件而不是充分条件 P1 P2 R1 R2 已占有 正申请

193 允许进程同时访问某些资源，如采用SPOOLING技术 问题 这种方法不能解决访问那些固有不允许被同时访问的资源带来的死锁问题。
解决死锁问题的基本方法 解决死锁的方法一般可分为预防、避免、检测与恢复 死锁预防：打破造成死锁的四个必要条件中的一个 使互斥或不可剥夺条件不成立 允许进程同时访问某些资源，如采用SPOOLING技术 问题 这种方法不能解决访问那些固有不允许被同时访问的资源带来的死锁问题。 使资源的部分分配条件不成立 预先分配各并发进程所需要的全部资源 多数情况下，一个进程在执行前不可能提出它所需要的全部资源 资源浪费太大 进程的并发性降低，系统性能降低

194 把资源分类，使进程在申请、保持资源时不形成环路。如进程申请的资源总是比已占有的资源的类别更高，释放的次序与此相反
使环路条件不成立 把资源分类，使进程在申请、保持资源时不形成环路。如进程申请的资源总是比已占有的资源的类别更高，释放的次序与此相反 问题 限制进程对资源的请求 增加系统开销

195 避免死锁 静态预先分配所有资源，又称为银行算法。即事先静态说明而后静态分配，破坏部分分配条件，但这种方法的资源利用率低。 资源轨迹图
设系统有打印机一台，绘图机一台 A进程：I1处申请一台打印机，I3处释放；I2处申请一台绘图机，I4处释放 B进程：I5处申请一台绘图机，I7处释放；I6处申请一台打印机，I8处释放

196 Two process resource trajectories
安全区 不安全区 Two process resource trajectories

197 安全状态：从该状态出发，系统能保证所有进程都能完成 不安全状态：从该状态出发，系统不能保证所有进程都能完成 例：假设系统共有10个资源
安全与不安全状态 安全状态：从该状态出发，系统能保证所有进程都能完成 不安全状态：从该状态出发，系统不能保证所有进程都能完成 例：假设系统共有10个资源 (a) (b) (c) (d) (e) (a) (b) (c) (d)

198 单种资源银行家算法 (a) (b) (c) Three resource allocation states safe unsafe

199 多种资源银行家算法 算法： （1）查找资源申请矩阵，是否存在申请资源数不超过剩余资源数的行。 如果不存在这样的行，系统会死锁
（2）如果存在，该进程能正常结束，标记该行为结束，将其所有资源撤 消并归还 （3）重复上述步骤，如果所有的进程都能标记为结束，那么系统安全， 否则会产生死锁

200 根据进程数目和对每个资源的需求量，写出需求矩阵：B=（bij)mxn bij=(Pi,Rj)——进程i对资源j的需求量
受控资源分配法： 1969年由Haberman提出，分配资源前先检查会不会发生死锁，要求各进程说明所需资源，将资源分类，按不同策略分配，又称为静态说明动态分配。 算法 假设每类资源仅有一个 根据进程数目和对每个资源的需求量，写出需求矩阵：B=（bij)mxn bij=(Pi,Rj)——进程i对资源j的需求量 以进程为顶点建立仅含顶点的图 当Pi有资源Rj请求时，向图中添加起点为Pi的有向边，边上标记为Rj ，终点是除Pi外其它申请资源Rj的进程。检查图中是否包含回路，若是则可能出现死锁，拒绝资源Rj的分配，撤消具有标记Rj的边，并阻塞进程Pi 。 当有进程完成时，从图中删除该进程顶点以及相关的边。

201 例 B= R1 R2 R3 R4 R5 R1 R1 P1 P2 P1 P2 P1 P2 R3 R3 P3 P4 P3 P4 P3 P4
初始状态 P1申请R1，分配 P2申请R3，分配

202 R2 R1 P1 P2 R1 P1 P2 R3 阻塞队列 P2（R2） R3 R3 R3 P3 P4 P3 P4 R2 P2申请R2，形成回路 不分配R2，阻塞P2 R1 R1 P1 P2 P1 P2 阻塞队列 P2（R2） P3（R2） R3 R3 R2 R3 R3 P3 P4 P3 P4 R2 P3申请R2，形成回路 不分配R2，阻塞P3

203 阻塞队列 P2（R2） P3（R2） P1 P2 P3 P4 P4申请R4，分配 R1 R3 R4 P1申请R2，分配 R1，R2 R2 P1执行完成，释放R1、R2 唤醒P2，分配R2 R3、R2 ………… 问题：当某些资源的数量大于1时，上述方法是否适用？如何改进？

204 Pretend there is no problem Reasonable if deadlocks occur very rarely
死锁的检测与恢复 确定当前状态是否存在死锁？ 存在死锁时包含哪些进程？ The Ostrich Algorithm（驼鸟算法） Pretend there is no problem Reasonable if deadlocks occur very rarely cost of prevention is high UNIX and Windows takes this approach It is a trade off between convenience correctness

205 单个多种资源下死锁检测 例子 设系统当前的状态是

206 Note the resource ownership and requests
资源分配图 Note the resource ownership and requests A cycle can be found within the graph, denoting deadlock

207 2）若图中存在顶点N的标记为未搜索，将N作为起点，标记为已搜索，执行下面3）-7），否则转8） 3）将L初始化为空，并清除所有的有向边标记
算法 L标记顶点集合 1）标记图中的所有顶点未作搜索 2）若图中存在顶点N的标记为未搜索，将N作为起点，标记为已搜索，执行下面3）-7），否则转8） 3）将L初始化为空，并清除所有的有向边标记 4）将当前顶点添加到L的尾，检测该顶点在L中是否出现两次。若是，L中包含了死锁环，算法结束 5）从当前顶点出发，检测是否存在以它为起始顶点且未标记的有向边，若是进行5），否则转6） 6）随机选取一条未标记的有向边，标记它，并以它的终止顶点为当前顶点，返回3） 7）删除L中的最后一个顶点。若L为空，表明本次搜索中所经历的顶点不会出现在死锁环中。转1）。若L不为空，以L的最后一个顶点为当前顶点，转3） 8）当前状态不会出现死锁，算法结束。 如何实现该算法？

208 Data structures needed by deadlock detection algorithm
多个多种资源下死锁检测 Data structures needed by deadlock detection algorithm A= E= C= R=

209 问题：如何实现该算法？ 基于上述数据结构，进程Pi可完成的条件是： C(i,j)+R(i,j)<Aj 1≤j ≤m 算法：
1）设置每个进程的状态为未标记 2）寻找未标记且满足下述条件的进程Pi 3）若Pi不存在，转4），否则修该A为： Aj= Aj+ R(i,j) ≤j ≤m 并标记Pi 4）若所有的进程都被标记，那么当前的状态不会造成死锁，否则当前饿状态将造成死锁。算法结束。 问题：如何实现该算法？

210 例： An example for the deadlock detection algorithm

211 将某些资源从其它进程强占过来分配给另一些进程 要求：强占不影响原进程恢复后的执行 问题：与资源的属性有关，难实现 回退法恢复
死锁的恢复策略 剥夺法恢复 将某些资源从其它进程强占过来分配给另一些进程 要求：强占不影响原进程恢复后的执行 问题：与资源的属性有关，难实现 回退法恢复 系统执行过程中设置若干断点，并保存现场 采用回滚方式释放资源以解除死锁 要求：保护的现场不能频繁覆盖 问题：断点的设置时机与多大的空间开销 杀死进程 从系统中撤消某些进程，释放资源以解除死锁 要求：保证系统的数据等的一致性 问题：难于判断是否能保证一致性 问题：谁实施恢复？死锁进程本身？为什么？

212 处理死锁的综合措施 Howard在1973年提出将解决死锁的基本方法组合起来，并对由不同类资源竞争所引起的死锁采用对它来说是最佳的方法来解决，以此来全面解决死锁问题。这一个思想是基于以下事实：系统内的全部资源可按层次分成若干类，对于每一类，可以使用最适合它的办法来解决死锁问题。由于使用了资源分层技术，在一个死锁环中，通常只包含某一层次的资源，每一个层次可以使用一种基本的方法。因此，整个系统就不会受控于死锁了。

213 Other Issues Two-Phase Locking Phase One
process tries to lock all records it needs, one at a time if needed record found locked, start over (no real work done in phase one) If phase one succeeds, it starts second phase, performing updates releasing locks Note similarity to requesting all resources at once Algorithm works where programmer can arrange program can be stopped, restarted

214 Nonresource Deadlocks
Possible for two processes to deadlock each is waiting for the other to do some task Can happen with semaphores each process required to do a P(S) on two semaphores (mutex and another) if done in wrong order, deadlock results Starvation Algorithm to allocate a resource may be to give to shortest job first Works great for multiple short jobs in a system May cause long job to be postponed indefinitely even though not blocked Solution: First-come, first-serve policy

215 §8、线程 概念 进程的基本属性 资源的拥有者 给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状态、优先级、调度 调度单位 进程是一个执行轨迹 以上两个属性构成进程并发执行的基础

216 进程的不足 时间空间开销大 进程的创建、撤消和切换要花费大量的时间 进程控制块较复杂，使空间开销较大 限制并发度的提高 进程作为执行单位，仍使得一些本可以并发的操作不能并发执行 例 对LAN中的文件服务器，有几个独立的文件服务请求时，能否同时处理？ 程序执行时，能否把菜单显示与部分数据处理同时进行？ 一个由多个独立部分组成的程序能否着几个部分同时执行？ 一个进程当I/O阻塞时，与I/O无关的部分能否继续执行？

217 线程的定义 线程有时称轻量级进程，它是进程中的一个运行实体，是CPU调度的更基本单位 线程是由进程派生出来的一组代码（指令组）的执行过程 线程的特点 将进程的两个属性分开处理 资源分配单位是进程 代码执行的单位是线程 线程是由进程派生出来的 一个进程可以产生多个线程 线程共享进程的资源

218 更好的并发性 进程并发 线程并发 更小的系统开销 创建和撤消一个新线程花费时间少 两个线程的切换花费时间少。如果机器设有“存储[恢复]所有寄存器”指令，则整个切换过程用几条指令即可完成 同一进程内的线程之间相互通信无须调用内核 适合多处理机系统

219 线程模型 线程与进程的关系 (a) Three processes each with one thread
(b) One process with three threads

220 线程与进程数据间的关系

221 线程的适用范围 （1）服务器中的文件管理或通信控制。 （2）前后台处理。 （3）异步处理。

222 线程的分类 用户级线程(User Level Thread)

223 特点 线程库 由应用程序完成所有线程的管理 通过线程库(用户空间) 一组管理线程的过程 核心不知道线程的存在 线程切换不需要核心态特权
调度是应用特定的 线程库 创建、撤消线程 在线程之间传递消息和数据 调度线程执行 保护和恢复线程上下文

224 核心不知道线程的活动，但仍然管理对应进程的活动 当线程调用系统调用时，整个进程阻塞
对用户级线程的核心活动 核心不知道线程的活动，但仍然管理对应进程的活动 当线程调用系统调用时，整个进程阻塞 但对线程库来说，线程仍然是运行状态，即线程状态是与进程状态独立的 用户级线程的优点和缺点 优点： 线程切换不调用核心 调度是应用程序特定的：可以选择最好的算法 ULT可运行在任何操作系统上（只需要线程库） 缺点： 大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞 核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上

225 核心级线程(Kernel Level Thread)

226 特点 所有线程管理由核心完成 没有线程库，但对核心线程工具提供API 核心维护进程和线程的上下文 线程之间的切换需要核心支持 以线程为基础进行调度 例子：Windows NT，OS/2 核心级线程的优点和缺点 优点： 对多处理器，核心可以同时调度同一进程的多个线程 阻塞是在线程一级完成 核心例程是多线程的 缺点： 在同一进程内的线程切换调用内核，导致速度下降

227 线程的状态与转换 分派 唤醒 继续 抢占 停止 可运行 睡眠 用户级线程 活跃 连接在LWP上

228 第4章 处理机调度   4.1 分级调度

229 4.1.1 作业的状态及转换 一个作业从用户提交给计算机系统到执行结束退 出系统，一般都要经历提交、收容、执行和完成 等4个状态。 提交状态 -----作业处于从输入设备进入外部存储设备的过程 称为“提交状态”。 收容状态 -----作业的全部信息已经进入输入井，但是未被调度 到执行，称作业处于“收容状态”。

230 执行状态 ----作业获得了系统中的所需资源，建立了一组进程， 称作业在“执行状态”。作业在执行过程中，按照 进程的活动又可用“就绪、等待、执行”三种子状 态。 完成状态 ----当作业正常运行结束或发生错误而终止时，进入 “完成状态”。在该状态下，系统需做诸如打印结 果、回收资源等善后工作。

231 上述作业的各种状态及转换可以通过下图来说明：
提交状态 作业调度 收容状态 执行状态 完成状态 作业注册 内存 就绪 等待 执行 外存 交换调度 进程调度 线程调度 作业的状态及转换

232 作业从进入系统并驻留在外存的后备队列上开始， 直至作业运行完毕，可能要经历下述四级调度。 一、高级调度 二、交换调度 三、进程调度
4.1.2 调度的层次 作业从进入系统并驻留在外存的后备队列上开始， 直至作业运行完毕，可能要经历下述四级调度。 一、高级调度 二、交换调度 三、进程调度 四、线程调度 继续

233 高级调度 又称为作业调度，用于决定把外存上处于后备队列中的作业调入 内存，并为它们创建进程、分配必要的资源，然后，将新创建的进程
排在就绪队列中，准备执行。在作业调度中，必须解决两个问题： 1） 接纳多少个作业：多道程序的度数的确定应该系统的规模和运行 速度，做适当的折中。 2） 接纳哪些作业：应该将作业从外存中调入内存，将取决于所采用 的调度算法。关于各种不同的调度算法将随后讨论。 返回

234 进程调度 该调度决定就绪队列中的哪个进程将获得 处理机，然后将处理机分配给该进程的操作，进程调度可采用如下两种方式： 1）非抢占方式：
一旦把处理机分配给某进程，边让该进程一直执行，知道 该进程完成或发生某个事件而被阻塞时，才将处理机分配给 其它进程，决不允许某进程抢占已经分配出去的处理机。 2）抢占方式： 允许调度程序根据某个原则，去停止某个正在执行的进程 ，将已经分配给该进程的处理机，重新分配给另一个进程。 抢占的原则有“时间片原则”、“优先权原则”和“短作业优先原 则”。 返回

235 交换调度 又称中级调度，引入中级调度的主要目的，是为了提高内存的利用率和系统吞吐量，因此，那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调到外存去等待。当这些进程重新具备运行条件时，且内存有空闲，就将那些就绪进程重新调入内存。 返回

236 线程调度 指进程在执行状态中，多个线程之间的转换调度。上述四种 不同的调度过程如下图所示。 返回 作业的状态及转换 收容状态 交换调度
提交状态 作业调度 收容状态 执行状态 完成状态 作业注册 内存 就绪 等待 执行 外存 交换调度 进程调度 线程调度 作业的状态及转换 返回

237 4.1.3 作业与进程的关系 作业： 是一个静态的概念，是用户向计算机提交的任务单位。 进程： 是动态的概念。是作业在内存中执行的资源分配的基本单位。 一个作业的执行通常需要一个或以上的进程。

238 4.2 作业调度 作业调度是按照某种规则，从后备作业队列中挑选作业进入内存，参与处理机的竞争的过程。

239 作业调度中用到的数据结构 作业控制块： 当一个作业提交给系统 时，系统要为作业开辟一个 作业控制块JCB，以便随时 记录作业的信息。系统通过
用户名 作业名 作业类型 内存需求量 外设类型与需求数量 作业提交时间 作业优先级数 作业运行时间（估计） 其它 作业控制块： 当一个作业提交给系统 时，系统要为作业开辟一个 作业控制块JCB，以便随时 记录作业的信息。系统通过 JCB感知进程的存在，右图 中给除了JCB可能包含的信 息。

240 作业调度的功能  1) 记录系统中各个作业的状况。 每个作业在个阶段所要求和分配的资源 以及该作业的状态都记录字它的JCB中，根 据JCB中的有关信息，作业调度程序对作业 进行调度和管理。 2）从后备队列中挑选出一部分作业投入运行。 作业调度程序根据不同的调度算法，选 择出对系统最有利的若干作业进入内存执 行。

241 3）为选中的作业做好执行前的准备工作和结束后的善后工作。
作业调度程序为选中的作业建立进程，分配所需资源。 当作业运行结束后，作业调度程序需要回收所占用 的资源，撤消与该作业有关的全部进程和作业控制块等。 作业状态的转换可以由以下流程图来描述：

242 出口 后备队列中 有作业吗？ 资源要求 能满足吗？ 是 否 从后备队列中选 出一个作业 审核资源要求 放弃作业 分配资源 建立进程 进程调度 (a) 后备状态到执行状态的转变 撤消作业的所有进程，以及JCB (b) 执行状态到完成状态的转变 回收分配给作业的全部资源 计算作业的执行费用 调度下一个作业

243 作业的调度算法 作业调度目标 （1）公平对待后备作业队列中的每一个作业。 （2）使进入内存的多个作业能均衡地使用系 统中的资源。
（3）力争在单位时间内尽可能多地为作业提 高服务，提高系统吞吐量。

244 在批处理系统中，使用“周转时间”来描述系统
的吞吐能力，若作业到达系统的时间为Tsi,作业完 成的时间为Tei，则该作业的周转时间Ti为 Ti=Tei-Tsi 对于一批n个作业而言，它们的平均周转时间T为： T=(T1+T2+…+Tn)/n

245 另外也可使用“带权周转时间”来描述调度算
法的优劣。带权周转时间是作业周转时间与作业执行时 间的比： Wi=Ti/Tri （其中Ti是作业周转时间，包括作业在后备队列中的等待时间和执行时间，Tri是指作业的执行时间） 对于n个作业而言，平均带权周转时间为： W=(W1+W2+…+Wn)/n

246 调度算法 1)先来先服务（FCFS）调度算法 以作业进入后备队列的先后次序，作为作业调度程序挑选作业的依据，这就是先来先服务作业调度算法的基本思想。

247 有5个作业，它们进入后备作业队列的到达时间如下所示，采用先来先服务的作业调度算法，求每个作业的周转时间以及它们的平均周转时间。
例题: 有5个作业，它们进入后备作业队列的到达时间如下所示，采用先来先服务的作业调度算法，求每个作业的周转时间以及它们的平均周转时间。 作业 达到时间 所需CPU时间 1 10．1 0．7 2 10．3 0．5 3 10．5 0．4 4 10．6 5 10．7 0．2

248 按照先来先服务的作业调度算法，调度的顺序为1，2， 3，4，5，每个作业的完成时间和周转时间如下所示：
解： 按照先来先服务的作业调度算法，调度的顺序为1，2， 3，4，5，每个作业的完成时间和周转时间如下所示： 作业 到达时间 所需CPU时间 完成时间 周转时间 1 10．1 0．7 10．8 2 10．3 0．5 11．3 3 10．5 0．4 11．7 1．2 4 10．6 12．1 1．5 5 10．7 0．2 12．3 1．6 不难算出它们的平均周转时间是1.2。

249 2)轮转法 轮转法的基本思想就是将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占用的CPU而派到继续队列的末尾，等待下依次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程或作业。 在轮转法中，时间片的大小的确定是非常重要的，通常，时间片大小的确定需要考虑以下几个因素： 系统对响应时间的要求   就绪队列中进程的数目   系统的处理能力

250 1、首先设置多个就绪队列，并为各个队列赋予不同的优先权。第一个队列的优先权做高，第二次之，其余的队列依次降低。如图所示：
3)多级反馈轮转法 该调度算法实施过程如下： 1、首先设置多个就绪队列，并为各个队列赋予不同的优先权。第一个队列的优先权做高，第二次之，其余的队列依次降低。如图所示： 就绪队列3 就绪队列n 就绪队列1 就绪队列2 至CPU S1 S2 S3 （时间片：S1<S2<S3）

251 2、予各个队列中进程执行时间片的大小也各不相同，在优先权越高的队列中，每个进程的执行时间片就规定得越小。
3、一个新进程进入内存后，首先将它放入第一个队列末尾，按FCFS的原则调度。该进程如果在一个时间片内没有执行完毕，则转入第二个队列的末尾，同样地再按照FCFS被调度执行，若在时间片内还未结束，则转入带第三个队列末尾，依次类推。在最后的队列中则按照轮转发进行调度执行，直到进程运行结束。 4、只有当优先权高的队列为空时，才能调度优先权次高队列中的进程。

252 系统或用户按照某中原则为作业或进程指定一个 优先级来表示该作业或进程所享有的调度优先权。 当调度作业或进程时，选择优先级高的投入运行。
4）优先级调度算法 系统或用户按照某中原则为作业或进程指定一个 优先级来表示该作业或进程所享有的调度优先权。 当调度作业或进程时，选择优先级高的投入运行。 确定优先级的方法有两种： 1、静态优先级法 2、动态优先级法 继续

253 静态优先级法 静态优先级法是在创建进程时确定的，且规定它在进程 的整个运行期间保持不变。确定进程优先级的依据有： （1）进程类型。如系统进程优先权一般高于用户进程。 （2）进程对资源的要求。如进程运行的估计时间及内存 需求量小的进程应该被赋予较高的优先权。 （3）根据用户的要求。根据用户所付费用来确定优先权。 该方法简单易行，系统开销小，适合于要求不太高的系统。 返回

254 动态优先级法 动态优先级是指在创建进程时赋予的优先权，可以随进程的推进而 改变，以便获得更好的调度性能。 动态优先权的确定一般遵循以下原则：
（1）根据进程在占有CPU时间的长短来确定。一个进程 占用CPU的时间越长，再次获得的优先权越低，反 之，越高。 （2）根据就绪进程等待CPU的时间片长短来确定。若进 程在就绪队列中等待的时间越长，则获得的优先 权越高。 返回

255 5）最短作业优先法 每个用户对自己作业所需耗费的CPU时间 做一个估计，填写在作业说明书中。作业调度 程序工作时，总是从后备作业队列中挑选所需 CPU时间最少、且资源能够得到满足的作业进 入内存投入运行。该算法的吞吐量优于其它方 法，但是有可能使得哪些长作业永远得不到调 度执行的机会。

256 有5个作业，它们进入后备作业队列的到达时间如下所 示。采用最短作业优先的作业调度算法，求每个作业的周转时 间以及它们平均周转时间。
例题: 有5个作业，它们进入后备作业队列的到达时间如下所 示。采用最短作业优先的作业调度算法，求每个作业的周转时 间以及它们平均周转时间。 作业 达到时间 所需CPU时间 1 10．1 0．7 2 10．3 0．5 3 10．5 0．4 4 10．6 5 10．7 0．2

257 不难算出它们的平均周转时间为1.02。 解： 按照短作业优先的作业调度算法，因为作业1首先到达，首先应该调度
作业1进入内存运行，它的周转时间T1是 0.7。在它于CPU时间10.8 完成时，作业2、3、4、5都已经在后备队列中等候，因此，此时的调 度顺序应该是：5、3、4、2。作业5在时刻10.8进入内存，运行0.2 后结束，因此它的周转时间T5=(完成时间-到达时间)= =0.3， 每个作业的完成时间和周转时间如下所示： 作业 到达时间 所需CPU时间 进入内存时间 完成时间 周转时间 1 10．1 0．7 10．8 2 10．3 0．5 11．8 12．3 3 10．5 0．4 11．0 11．4 0．9 4 10．6 1．2 5 10．7 0．2 0．3 不难算出它们的平均周转时间为1.02。

258 6）最高响应比优先算法 先来先服务的算法重点考虑的是作业在后备作业队列里的等待时间，因此对短作业不利；短作业优先的调度算法重点考虑的是作业所需要的CPU时间，因此对长作业不利。作高响应比优先算法试图综合这两方面的因素，以便能更好地满足各种用户的需要。 作业的响应比，是指作业的等待时间与所需运行时间之比，即： 响应比=等待时间/所需CPU时间.

259 有4个作业，它们进入后备作业队列的到达时间如下图所示，采用最高响应比优先算法，求每个作业的周转时间以及它们的平均周转时间。
例题 有4个作业，它们进入后备作业队列的到达时间如下图所示，采用最高响应比优先算法，求每个作业的周转时间以及它们的平均周转时间。 作业 到达时间 所需CPU时间 1 8．0 2 8．5 0．5 3 9．0 0．1 4 9．5 0．2

260 解： 刚开始，后备作业队列中只有作业1，因此立即将它投入运行，它于CPU时间10完成。开始重新调度时，作业2、3、4都已经达到 后备队列。根据最高响应比优先的调度算法，应该计算这一时刻 这三个作业各自具有的响应比。比如对于作业2，它是CPU时间 8.5达到后备队列的，现在是CPU时间10.0，它已经等待了 ( )=1.5。它所需的运行时间是0.5。因此该时刻它的响 应比是1.5/0.5=3。下表给出了这一时刻三个作业各自的已等待 时间和响应比。由于这是作业3具有最高的响应比，因此它是第2个调度的对象。

261 作业 到达时间 所需CPU时间 已等待时间 响应比 2 8．5 0．5 1．5 3 9．0 0．1 1 10 4 9．5 0．2 2．5 当前CPU时间=10.0

262 作业3在CPU时刻10.1运行完毕，作业2和作业4是参与调
度的对象，此时，它们的已等待时间和各自响应比如下表所示。可以看出，这次选中的应该是作业2，因为它的响应比是3.2。 作业 到达时间 所需CPU时间 已等待时间 响应比 2 8．5 0．5 1．6 3．2 4 9．5 0．2 0．6 3 当前CPU时间=10.1

263 这4个作业的平均周转时间为1.625。 作业2在CPU时刻10.6完成.作后调度运行的作业是作业4,它在CPU
时刻10.8完成.于是,这4个作业的完成时间和周转时间如下表所示: 作业 进入内存时间 完成时间 周转时间 1 8.0 10.0 2 10.1 10.6 2.1 3 1.1 4 10.8 1.3 这4个作业的平均周转时间为1.625。

264 4.3 进程调度 什么是进程调度? 当系统中有多个进程就绪时，必须决定先执行哪一个。也就是说，必须决定把CPU分配给谁用。操作系统作出这一个决定的程序称为“进程调度程序”，该程序中采用的调度算法，称为进程调度算法。

265 进程调度的功能 （1）记录系统中所有进程的有关情况。这些信 息记录在进程的PCB表中，调度程序根据 PCB表中的信息调度一个进程占据处理机。
（2）确定分配处理机的算法。 （3）完成处理机的分配。进程调度程序负责进 程见上下文的切换（即有关变量的值、 寄存器的值和PCB信息的保存和恢复） （4）完成处理机的回收。

266 引起进程调度的原因 （1）正在执行的进程执行完毕。 （2）执行中进程因为各种原因被阻塞起来进入 等待状态。
（3）在分时系统中时间片已经用完。 （4）在CPU执行方式是可剥夺时，就绪队列中 的某些进程的优先级变得高于某个进程的 优先级时，也将引起进程调度。

267 进程上下文切换 什么是上下文？ 进程上下文是指由正文段、数据段、硬件寄存器的内 容及有关的数据结构组成的环境。
在发生进程调度时，系统必须要做上下文的切换，其切换包括 以下步骤： （1）决定上下文切换的时机 （2）保存当前执行进程的上下文。 （3）使用合适的调度算法，选择一个处于就绪状态的 进程。 （4） 装配所选进程的上下往年，将CPU控制权交给所 选进程。

268 进程调度算法 常见的进程调度算法有： 1）  先来先服务算法 2）  时间片轮转法 3）  优先级法 4）  多级反馈队列调度算法

269 例题1: 有一个分时系统，允许10个终端用户同时工作，时间片长度为100ms。如对用户的每一个请求，CPU将耗费300ms的时间进行处理，作出回答。试问终端用户提出两次请求的时间间隔最少多少？

270 解： 因为时间片长度为100ms，有10个终端用户同时工作，所以轮流一次需要花费1s。就是说在1s内，一个用户可以获得100ms的CPU时间。又因为对终端用户的每一次请求，CPU都要耗费300ms进行处理后才能作出应答，于是终端用户两次请求的时间间隔最少应为3s，在次期间提出请求，系统就无法顾及，不可能予以处理。

271 例题2： 在多道程序设计系统中，有5个作业，在该系统中采用先来先服务的作业调度算法和进程调度算法，内存中可供5个作业使用的空间为100KB，在需要时按照顺序分配，作业进入系统后，不能在内存中移动。试求每个作业的周转时间和它们的平均周转时间。 作业 达到时间 所需CPU时间 所需内存量 1 10．1 0．7 15KB 2 10．3 0．5 70KB 3 10．5 0．4 50KB 4 10．6 20KB 5 10．7 0．2 10KB

272 解：由于是多道程序设计系统，按照先来先服务的调度算法，作业1在10. １时被装入内存,并立即投入运行．作业2在10
解：由于是多道程序设计系统，按照先来先服务的调度算法，作业1在10.１时被装入内存,并立即投入运行．作业2在10.3时被装入内存．但因为采用的是先来先服务的进程调度算法，所以作业２进程只能等待作业１进程运行完毕后才能投入运行．这是，内存还剩余１５ＫＢ．随后达到后备作业队列的作业３、作业４，由于没有足够的存储量提供分配，因此暂时无法把它们调入内存运行．当作业５在１０．７到达时，由于她只需要１０ＫＢ的存储量，因此可以装入内存等待调度运行，如图(a)所示．这时内存还剩下５ＫＢ的空闲区没有使用．在作业１运行完毕撤离系统时，归还它所占用的１５ＫＢ内存，但由于题目规定不允许作业在内存中移动，因此一头一尾的两个分散空闲区无法合并，如图(b)所示．只有到时刻１１．３作业２运行完毕，腾空所占用的７０ＫＢ存储区，并与前面相连的１５ＫＢ空闲区合并成为８５ＫＢ的空闲区后，作业３和作业４才得以进入内存．但由于作业５先于它们进入内存，按照先来先服务的进程调度算法，这是的调度顺序应该是５、３、４．下页是各作业的周转时间． 继续

273 系统的平均周转时间为：（0.7+1.0+1.4+1.7+0.8）/5=1.12 返回 作业 到达时间 所需CPU时间 进入内存时间
开始运行时间 完成时间 周转时间 1 10．1 0．7 10．8 2 10．3 0．5 11．3 3 10．5 0．4 11．5 11．9 1．4 4 10．6 12．3 1．7 5 10．7 0．2 0．8 系统的平均周转时间为：（ ）/5=1.12 返回

274 返回 (a)到10.7时 内存的情况 (b)到10.8作业1运 行完时内存的情况 (c)到11.3作业2运行 完成时内存的情况
作业1(15KB) 作业2(70KB) 作业5(10KB) 空闲（5KB) 空闲(15KB) 作业2(70KB) 作业5(10KB) 空闲（5KB) 作业3(50KB) 作业4(20KB) 空闲(15KB) 作业5(10KB) 空闲（5KB) (a)到10.7时 内存的情况 (b)到10.8作业1运 行完时内存的情况 (c)到11.3作业2运行 完成时内存的情况 返回

275 4.6 实时系统中的调度 实时系统的特点 实时系统与其它系统的最大区别，其处理时间和控制的正确性不仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间。 实时系统的特点要求实时操作系统具有以下能力： 1)很快的进程或线程切换速度。 2)快速的中断响应能力。 3)基于优先级的随时抢先式调度策略。

276 实时调度算法   在实时调度算法中，有许多算法是根据任务的截止时间进行调度的。为此，系统应该向调度程序提供有关任务的下述一些信息： （1）就绪时间。 （2）开始截止时间和完成截止时间。 （3）处理时间。 （4）资源要求。 （5）优先级。

277 常用的调度算法有： （1）时间片轮转的调度算法
当一个实时任务到达时，它被挂在轮转队列的末尾，等待这属于自己的时间片到来。这种调度算法只适用于一般实时信息处理系统，不能处于要求严格的实时系统。

278 （2） 非抢占式优先权调度算法 当一个优先级高的实时任务到达时，它被安排在就绪队列的队首，等待当前任务终止或完成后才能被调度执行。该调度算法适用于不太严格的实时控制系统中。 非抢占式优先权调度算法 当前进程 实时进程 实时进程请求调度 调度实时进程运行 调度时间 当前进程运行完毕

279 （3）于优先级的固定点抢占式调度算法 在某个实时任务到达时，如果该任务的优先级高于当前任务的优先级，在时钟中断到来时，调度程序便剥夺当前任务的执行，将处理机分配给高优先级的执行。该算法能有较好的响应效果，可适用于大多数实时系统。 调度时间 基于优先级的固定点抢占式调度算法 当前进程 实时进程 实时进程请求调度 调度 实时进程运行 时钟中断到

280 （4）基于优先级的随时抢先式调度算法 在该调度算法中，要求系统具有快速响应外部事件中断的能力，一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。 基于优先级的随时抢占式调度算法 当前进程 实时进程 实时进程请求调度 实时进程抢占当前 进程，并立即执行 调度时间

281 实时调度实例 什么是时限调度算法？ 时限调度算法是一种以满足时限要求为调度原则的算法。在实时系统中的用户要求时限有两种，即处理开始时限和处理结束时限。该算法可适用于周期性调度与非周期性调度两种。下图表示了四个具有开始截止时间的非周期任务的调度情况： 具有开始截止时间的非周期实时任务的调度 1 3 开始截止时间 任务到达 执行任务 2 4 t

282 系统首先调度任务1执行，在任务1执行期间，任务2、
3又先后到达。由于任务3的开始截止时间早于任务2， 故系统在1后将调度任务3执行。在此期间又来了任务4， 其开始截止时间仍是早于任务2的，故在任务3执行完 后，系统又调度任务4执行，最后才调度任务2执行。 接下来是一个使用时限调度算法调度周期性实时任务 的例子。

283 设实时系统从两个不同的数据源DA和DB 周期性地收集数据并进行处理，其中DA的时 限要求以30ms为周期。DB的时限要求以75ms 为周期。设DA所需处理时限为15ms，DB所需 处理时限为38ms，则与DA和DB有关进程的事 件发生时限（就绪时限）执行时限及结束时 限如下图：

284 进程 事件发生时限 执行时限 结束时限 DA（1） 15 30 DA（2） 60 DA（3） 90 …… DB（1） 38 75 DB（2） 150 DB（3） 225

285 各进程的调度顺序和相对时间如下图所示： DA(1) DA(2) DA(3) DA(4) DB(1) DB(2) 15 30 45 60 75
90 105 130 t

286 如上图，在开始时，DA（1）和DB（1）的结束时
程DA（1）执行。DA（1）的实际结束是为15，小于30 的时限要求。紧接着，进程DB（1）被调度执行。在 执行时间为30ms时，进程DA（2）进入就绪状态。由 于DA（2）的结束时限为60，近于DB（10的结束时限 75，从而DB（1）被DA（2）抢先。DA（2）的实际 结束时间为45，小于要求时限60。 在DA（2）结束之后，DB（1）再次占有处理机继 续执行，当DB（1）执行实现为60ms时，进程DA（3） 进入就绪状态。但是，由于DA（3）的结束时限为90 ，远于DB(1)的结束时限75，从而DB（1）继续执行。

287

288 第5章 存储管理 相关概念： 内存和外存 计算机系统中的存储器可分为两种：内存储器（内存）和辅助存储器（外存）。内存可被CPU直接访问，而后者不能，外存与CPU之间只能在输入输出的控制系统的管理下，进行信息交换。

289 5.1 虚拟存储器  虚拟存储器的产生原因 在早期的计算机存储管理方案中要求把作业“一次全部装入”到内存，这就带来了一个很大的问题；如果一个作业太大，以至于内存都容纳不下，那么，这个作业就无法投入运行。因此小内存和大作业之间存在着的这个矛盾，在多道程序设计时，当要求内存中存在多个作业程序时，就更显得突出了。虚拟存储器的概念就在这样的背景下产生了。

290 虚拟存储器的概念 虚拟存储器是一种扩大内存容量的设计技术，她把辅助存储器作为计算机内存存储器的后援。当作业提交给系统时，首先进入辅存，运行时，只将其中有关部分装入内存，其他部分仍在辅存中，当运行过程中需要用到不存在内存的信息时，再把它们调入，以保证程序的正常运行。这样一个看上去容量很大、但实际上不存在的大存储器，就被称为“虚拟存储器”。

291 地址变换的问题 1、什么是内存物理地址？ 内存是由一个个存储单元组成，这些内存单元按照一定顺序编号，称为该单元的地址。我们把这些“单元地址”称为“绝对地址”或“物理地址”。

292 2、什么是逻辑地址？ 用户的源程序经过编译程序的加工，产生出相对于“0”编址的目标程序，再经过连接装配，产生出一个”0”编址的更大的地址空间。这个地址空间被称为是用户程序的“相对地址空间”或“逻辑地址空间”。

293 当程序执行时，需要装入内存中，但是此时程序中的指令地址是“相对地址”，要使程序正常运行，需要将“相对地址”变换成“绝对地址”，如：
3、地址是怎样变换的？ 当程序执行时，需要装入内存中，但是此时程序中的指令地址是“相对地址”，要使程序正常运行，需要将“相对地址”变换成“绝对地址”，如： 20KB+100 20KB+3000 100 20KB 23KB 22KB 操作系统 XXXXXX Call 100 …… 21KB 内存  XXXXX Call 100 100 1KB 2KB 3KB 3000 用户程序的虚地址空间 (a) 100 20KB 23KB 22KB 操作系统 XXXXXX Call 20580 …… 20KB+100 20KB+3000 21KB 内存 (c) 25KB 22KB 24KB 操作系统 XXXXXX Call 22628 …… 20KB 22KB+100 22KB+3000 23KB 内存 (d) (b) 图5-1 地址变换示意图

294 其中程序A中的一条入口地址为3000的一条指令 为“call 100”,在装入内存之后，由于程序的启始地址不 再为“0”，故程序中的指令需要做相应的转换。在上图 中所示的情况中，“call 100”变成了“call ‘2KB+100’”。 因此在操作系统中，把用户程序指令中的相对地址变 换成所在绝对地址空间中的绝对地址的过程，称为“地 址重定位”。“地址的重定位”可分为“静态地址重定位” 和“动态地址重定位”。

295 静态地址重定位 在程序运行之前，就为用户程序实行了地址重定位的工作， 称这种地址重定位为“静态重定位”。该重定位方法有如下的特 点:
1) 静态重定位是在程序运行之前完成地址重定位工作的。 2) 静态重定位由软件实现，无须硬件提供支持。 3) 实行静态重定位时，地址重定位工作是在装入时被一次集 中完成的。 4) 绝对地址空间里的目标程序与原相对地址空间的目标程序 面目已不相同，因为前者进行了地址调整。 5) 实施静态重定位后，若用户在内存中做了移动，那么程序 指令中的地址就不再反映所在的存储位置了，除非重新进 行地址重定位。

296 动态地址重定位 动态地址重定位是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。动态地址重定位依靠硬件地址变换机构完成。 硬件地址转换机构一般由一个“基地址寄存器”和一个“虚地址寄存器”组成，用户程序不做任何修改地装入分配给它的存储区域。当调度到用户程序运行时，则转换成实际的物理地址。

297 关于动态地址重定位可以如下图所示的过程说明：
25KB 22KB 24KB 操作系统 XXXXXX Call 100 …… 20KB 22KB+100 22KB+3000 23KB 内存 22628 + 100 虚地址寄存器 (b) 用户程序的虚地址空间 基地址寄存器 XXXXX Call 100 100 22528 1KB 2KB 3000 3KB (a) (a)图表示用户程序虚拟地址空间的组成情况； (b)图表示用户程序装入到内存中的情况。

298 现在将地址的静态重定位和动态重定位做一个综合比较：
（1）地址转换时刻：静态地址重定位在程序运行之前完成 地址转换的；动态地址重定位却是将地址转换的时刻 推迟到指令执行时进行的。 （2）谁来完成任务：静态地址重定位是由软件完成地址转 换工作的；动态地址重定位则由一套硬件提供的地址 转换机构来完成。 （3）完成的形式：静态地址重定位是在装入时一次集中地 把程序指令中所有要转换的地址全部加以转换；而动 态地址重定位则是每执行一条指令时，对其地址加以 转换。 （4）完成的结果：实行静态重定位，原来的指令地址部分 被修改；实行动态地址重定位，只是按照所形成的地 址去执行这条指令，并不对指令本身做任何修改。

299 内外存数据传输的控制的问题 内存大小总是有限的，而程序的大小是无 法限制的，所以我们需要对内存进行扩充。此 时就提出了一个问题：按什么样的方式来控制 内存和外存之间的数据流动呢？最基本的控制 方法有两种：“用户程序控制”和“操作系统控 制”。

300 “用户程序控制”方法的例子是“覆盖”。 “覆盖”技术的实质可以使用下例来说明：
用户程序的调用结构如图(a)所示，通过连接装配的处理，该作业将形成一个需要存储量180KB的相对地址空间，如图(b)所示。由于程序中的若干子程序不可能同时调用，所以我们可以按照图(c)分配内存空间，此时将50KB和40KB的存储区称为覆盖区。 继续

301 覆盖技术程序示例 MIAN(10KB) A(50KB) B(30KB) C(30KB) D(20KB) E(40KB) MAIN(10KB)
MIAN(10KB) A(50KB) B(30KB) C(30KB) D(20KB) E(40KB) MAIN(10KB) A(50KB) B(30KB) C(30KB) D(20KB) E(40KB) 连接装配 180K (a) (b) MAIN A或B C或D或E (c) …… 50KB 40KB 10KB 返回 覆盖技术程序示例

302 “交换”方式的示意图入下所示，“请求调入和预调 入”控制方法的具体方案将在每种存储管理方法中详细讨 论 .
操作系统控制方式可以分为两种： “交换”和“请求调入和预调入”方式。 “交换”方式的示意图入下所示，“请求调入和预调 入”控制方法的具体方案将在每种存储管理方法中详细讨 论 . 辅助存储器 作业1 作业2 作业3 换出 换入 图5-4内外存之间的交换示意图 操作系统 用户区 内存

303 内存的分配与回收的问题   内存的分配与回收使内存管理的主要功能之一，为了合理利用内存，设计内存的分配和回收方法时，必须考虑的因素： 一、分配结构 二、放置策略 三、交换策略 四、调入策略 五、回收策略

304 内存信息的共享与保护的问题 在多道程序设计的环境下，内存中的许多用户或系统程序可以提供不同的用户进程共享。为了防止用户程序与用户程序之间形，以及用户程序与系统程序之间的干扰和破坏，我们必须对内存内进行保护。常见的内存保护法是“上下界存储保护法”。即在CPU中设置一对专用的寄存器—上界寄存器和下界寄存器，如下图所示：

305 当系统调度到哪一个作业进程运行时，就把该作业在内存 中的低端地址装入下界寄存器，把高端地址装入上界寄存器，
a b c d 第1分区 第2分区 第3分区 上界寄存器 下界寄存器 操作系统 作业1 作业2 作业3 上下界寄存器保护法示意图 当系统调度到哪一个作业进程运行时，就把该作业在内存 中的低端地址装入下界寄存器，把高端地址装入上界寄存器， 在运行作业1时，硬件回自动检测指令中的地址，若超出a或 b,则会产生出错中断。

306 5.2 分区存储管理 基本原理： 操作系统为每一个进程划分一块适当大小的存 储区，用来连续存放进程的程序和数据，使各 进程能并发执行。分区管理可以分为“固定分区 ”和“动态分区”两种方法。

307 固定分区法 思想： 操作系统将内存区划分成大小不等的若干连续分区，每个分区尺寸在划分后保持不变。因此操作系统可以为每一个分区设置一个后备作业队列，形成多队列管理方式。如图(a)所示；也可以采用多个分区只设置一个后备作业队列，如图（b），当某个分区空闲时，到队列中挑选作业，投入运行。 继续

308 固定分区的作业组织方式 C B A D F E (b) 20KB 256KB 操作系统 第2分区(32KB) 第3分区(64KB)
第 1 分 区 (8KB) (a) C B A D F E 20KB 256KB 操作系统 第2分区(32KB) 第3分区(64KB) 第4分区(132KB) 第 1 分 区 (8KB) C B A D F E (b) 返回 固定分区的作业组织方式

309 操作系统设置一张“分区分配表”，用来记录各分区的信息及当前 的使用情况。如表所示：
需要的数据结构： 操作系统设置一张“分区分配表”，用来记录各分区的信息及当前 的使用情况。如表所示： 分区号 起始地址 长度 使用标志 1 20KB 8KB 作业1 2 28KB 32KB 作业6 3 60KB 64KB 4 124KB 132KB 作业2

310 当需要装一个作业入内存时，系统的步骤为：
①扫描分区分配表，找到标志为“0”的分区。 ②比较作业尺寸与该分区的长度，若能容纳该 作业，则分配给该作业。 ③修改分区分配表中该分区的标志为“非0”。

311 分区的分配与释放 分区的分配： 若采用的是一个队列的管理方案，则当一个分区被释放时，需要在队列中选出一个作业运行，可以有以下几种方案：
（1）选出第一个可容纳的作业。该方案虽然实现简单，选择率高，但是可能会因为一个小作业进入而浪费掉该分区的大部分存储空间，存储利用率不高。 （2）在队列中找出该分区能容纳的最大的作业。由于每个分配出的分区产生出的内部碎片小，因此，此方案存储空间的利用率高；缺点是对小作业不公平。

312 分区的释放： 当作业运行结束时，在分区分配表中找到它使用的 表目，将该表目的标志置为“0”。 地址重定位与存储保护: 在固定分区方案中，每个分区只能装入一个作业， 故应该对程序实行静态重定位。即操作系统将一个分 区分配给某个作业时，装入程序就把该作业程序指令 中的相对地址与分区的起始地址相加，得到绝对地址。 该分区管理方法的存储保护使用“上下界存储保护法”。 具体的原理请参考图5-5。

313 动态分区法 思想： 当作业装入内存时，若内存中有足够的存储空间满足作业的要求，则就划分出一个同样大小的空间分配给该作业。内存分区的建立是在作业的处理过程中进行的，大小可随作业的大小变化，这就改变了固定分区中小作业也要占据大内存的现象，从而提高了内存的利用率。 动态分区的工作过程可用以下示意图说明:

314 操作系统 内存 20KB 空闲区 (236KB) 256KB 作业A (16KB) 作业B (100KB) 作业C (70KB) 作业D (75KB) 空闲区 (220KB) 作业A (16KB) 操作系统 内存 20KB 256KB 作业B (100KB) 作业C (70KB) 作业D (75KB) 36KB (b) (a) 继续

315 作业C (70KB) 作业D (75KB) 操作系统 内存 20KB 256KB 作业A (16KB) 36KB (c) 作业B (100KB) 空闲区 (120KB) 136KB 作业D (75KB) 操作系统 内存 20KB 256KB 作业A (16KB) 36KB (d) 作业B (100KB) 空闲区 (50KB) 136KB 作业C (70KB) 206KB 继续

316 图 动态分区存储管理的工作过程 操作系统 内存 20KB 256KB 作业A (16KB) 36KB 空闲区 (100KB) (50KB)
20KB 256KB 作业A (16KB) 36KB 空闲区 (100KB) (50KB) 136KB 作业C (70KB) 206KB 作业D (75KB) 111KB 作业D (75KB) 操作系统 内存 20KB 256KB 作业A (16KB) 36KB (e) 空闲区 (100KB) (50KB) 136KB 作业C (70KB) 206KB 内存 操作系统 20KB 作业A (16KB) 36KB 空闲区 (100KB) 136KB 作业C (70KB) 206KB 空闲区 (50KB) 256KB (e) (f) 图 动态分区存储管理的工作过程

317 当内存中的一个分区被释放时，与它前后相邻接的分区可能会有四种关系出现。如下图：
可以看出,随着作业对内存的的不断申请与释放,分区的数目不断增加,每个分区的尺寸在不断减小,这种情况持续下去,就会导致存在很多尺寸极小的分区,这些分区分配不出去,就形成了”外部碎片”。解决这个问题的方法就是“空闲区的合并”。 当内存中的一个分区被释放时，与它前后相邻接的分区可能会有四种关系出现。如下图： / / / / / / / / / 上空闲区 释放区 下空闲区 (a) (b) (c) (d)

318 （1）图(a)表示释放区的前后都是空闲区，因此合并后的空闲区的首地址就是上空闲区的起始地址，长度为三个分区的长度总和。
（2）图(b)表示释放区的前面是空闲区，合并后的空闲区的首地址就是上空闲区的起始地址，长度为两个个分区的长度总和。 （3）图(c)中表示释放区的后面是空闲区，合并后的空闲区的首地址就是该释放区的起始地址，长度为两个分区的长度总和。 （4）图(d)中表示释放区的前后都不是空闲区，无合并情况。

319 动态分区的管理与组织常用的两种方法为：表格法、链表法. 表格法： 在表格法中需要用到的数据结构为：可用表和请求表
动态分区的管理与组织用到的数据结构 动态分区的管理与组织常用的两种方法为：表格法、链表法. 表格法： 在表格法中需要用到的数据结构为：可用表和请求表 区号 分区长度 起始地址 1 16K 40K 2 24K 78K 3 9K 100K 进程号 请求大小 P1 13K P2 20K 请求表 可用表

320 分区的分配与回收 （1） 扫描请求表，读出表中的请求空间的某个进程。 （2） 将进程的请求长度与可用表中的每个可用分区大 小进行比较，找到合适的空闲区，分配给该进程。 （3） 更新可用表和请求表。 （4） 进程释放空间时，将相邻的空闲区进行联结合并， 更新可用表。

321 链表法 链表法是利用每个内存空闲区的头几个单元存放本空闲区的大小及下一个空闲区的起始地址，从而将所有的空闲区链接起来。空闲区的示意图如(a)所示，链表如图(b)所示。 空闲区 size next (a) 8KB 60KB 32KB 212KB 300KB NULL 20KB 链首指针 (b) 空闲分区组成的链表

322 分区的分配与回收 （1）扫描请求表，读出表中的请求空间的某个进程。 （2）搜索链表，找到合适的空闲区，分配给该进程。 （3）更新链表。
（4）进程释放空间时，将相邻的空闲区进行联结合并， 更新链表。

323 在上述分区分配过程中的步骤(2)，寻找合适的分区常用
的方法有以下三种： （1）最先适应算法 把最先找到的、满足存储需要的空闲分区作为分配的 对象。优点：查找时间短，实现简单；缺点：容易将大的分区分割成小块，对大作业不利。 （2）最佳适应算法 从当前所有空闲区中找出一个能够满足存储需求的、最小的空闲区作为分配的对象。优点：保证了大作业的需求。缺点：容易形成小的碎片空闲区，不容易分配。 （3）最坏适应算法 从当前所有空闲区中找出满足需求的、最大的空闲区作为分配对象。优点：不留下碎片空闲区。

324 动态分区存储管理的特点： (1)作业一次性全部装入到一个连续的存储分区中。 (2)分区是按照作业对内存的需求来划分的，因此，不
会出现内部碎片的问题。 (3)有硬件支持，实现指令地址的动态重定位。

325 动态分区管理的缺点： (1)没有解决小内存运行大作业的问题。 (2)虽然避免了内部碎片，但是会引起极小的分 区难以得到利用，形成外部碎片。

326 分区管理的优点： (1) 现了多个作业对内存的共享，提高了系统的资源利用率。 (2) 件支持少，算法简单，易实现。 缺点： (1) 内存利用率不高，内存中存在严重的碎片。 (2) 作业受分区大小的限制。 (3) 难以实现个分区的信息共享。

327 作业： 如图(a)所示，现在有两个空闲分区， 是111KB-161KB，一个是231KB-256KB。作业D到达，提出存储需求20KB，问：如果系统实行最先适应算法、最佳适应算法、最坏适应算法时，分别应该把哪一个空闲区分配给它？分配后的内存情形用图形标出。(此时内 0存空闲区采用链表法管理，空闲区按照地址递增顺序排列)。

328 操作系统 作业A的分区（16K） 作业B的分区（75K） 空闲区（50K） 作业C的分区（70K） 空闲区（25K） 20K 36K 111K 161K 231K 256K (a) 操作系统 作业A的分区（16K） 作业B的分区（75K） 空闲区（30K） 作业C的分区（70K） 空闲区（25K） 20K 36K 111K 161K 231K 256K (b) 作业D的分区（20K） 131K 操作系统 作业A的分区（16K） 作业B的分区（75K） 空闲区（50K） 作业C的分区（70K） 空闲区（25K） 20K 36K 111K 161K 231K 256K (c) 作业D的分区（20K） 251K

329 答： 当系统采取最先适应算法时，两个空闲区都能满足作业D的需求，此时系统按照空闲区地址递增的顺序构成链表，则最先搜索到的空闲区应该是大小为50KB的空闲区，此时分配后的内存如图(b)所示。 当系统采取最佳适应算法时，空闲区链表应当按照空闲区的大小顺序重新排列，则搜索到满足条件的最小的空闲区应该是大小为25KB的空闲区，此时分配后的内存如图(c)所示。当系统采取最坏适应算法时，则搜索到满足条件的最大的空闲区应该是大小为50KB的空闲区，此时分配后的内存如图(b)所示。

330 5.3 页式存储管理 基本思想 分区管理存在着严重的外部碎片问题，而且作业的大小受到分区大小的限制，而分页管理可以很好的解决这些问题。在分页存储管理中，系统将内存划分成大小相等的许多分区，称为“页面”。页面的编号为0,1,2,…如图(a) 所示。用户作业的地址空间也被划分成大小与“页面”相同的分区，称为“页”，如图(b)所示。此时用户程序的虚拟地址由两部分组成：页号与页内地址，如图(c)所示。这个二维地址可以转换成一维的，具体转换公式为： 一维地址=页号*分页尺寸+也内位移量 继续

331 操作系统 作业A（第2页） 作业A（第0页） 作业A（第1页） 20K 24K 28K 36K 40K 256K 32K …… (a) 44K 页面0~4 页面5 页面6 页面7 页面8 页面9 页面10 内存 用户作业的地址空间 第0页 4KB 8KB 12KB 第1页 第2页 (1,1092) 5188 1092 (b) (c) 页号 页内地址 9 10 19 只要内存中有足够多的空闲页面，用户作业中的某一页装入哪一个页面都是可以的。上图中，作业装入了页面6、页面8和页面10这三个不连续的存储块中。因此解决了分区管理中作业必须连续存放的缺陷。 返回

332 静态页面管理 静态页面管理在作业或进程执行之前，把该作业或进程的程序段和数据全部装入内存中的各个页面，利用页表和硬件地址变换机构实现虚拟地址到物理地址的映射。该存储管理方法中使用的数据结构主要有“页表”和“请求表”。

333 最简单的页表由页号与页面号组成，每个进程至少有一个页表, 记录了该进程的页与页面的对应关系。如图(a)所示： 请求表
  请求表 请求表记录了作业或进程在内存中的实际对应位置，其表项如 图(b)所示： 进程号 请求页面数 页表始址 页表长度 状态 1 20 1024 已分配 2 34 1044 3 18 1078 页号 页面号 9 1 21 2 22 (a) (b)

334 存储页面表 存储页面表每个系统一张，每个字位代表一个页面。若页面已 分配，则对应的字位置为1；反之，置为0。我们可以按照下面的
公式计算出存储页面表中的该位代表的页面号： 页面号=字节号*8+位号 1 空闲页面总数为：6 位号 字节号

335 内存的分配与回收 分配： 如图所示： 回收： 当进程执行完毕时， 删除对应的页表， 并修改存储页面表 （位图）中相应的标志。
读出进程请求的的页面数n 设置页表，将页表始址，页表长度置入请求表中，置状态为“已分配” 搜索存储页面表，分配n个页面，将页面号填入页表中 扫描存储页面表，系统中有n个空闲页面吗？ 是 否 返回 无法分配 分配： 如图所示： 回收： 当进程执行完毕时， 删除对应的页表， 并修改存储页面表 （位图）中相应的标志。

336 分页存储管理的地址转换 1、地址结构与数对（页号，页内位移）的形成 在分页管理的地址变换中，首先遇到的问题就是将一维的
相对地址（虚拟地址）转换成二维的数对，转换具体的计算公式为：   页号=虚拟地址/页面尺寸（注：“/”运算表示整除） 页内位移=虚拟地址%页面尺寸 （注：“%”运算表示求余数） 2、用数对中的“页号”去查找作业的页表，得到相应的页面号。 3、将得到的页面号通过计算得到物理地址，计算公式为： 物理地址=页面号*页面尺寸+页内位移

337 以上的地址转换过程全部由硬件地址变换机构自动完 成。下图给出了地址变换过程：
页表控制寄存器 起始地址 长度 CPU 虚地址 页号 页内位移 物理地址 页面号 内存 操作系统 …… +

338 从上图可以看出，程序取数据或指令需要经过页表变换才能得到实际物理地址，因此必须访问内存两次，这就比通常的指令执行速度慢一倍。基于这样的情况，我们可以在地址变换机构中加入一个高速联想寄存器，构成一张快表，存入当前进程最常用的页号与页面号，从而提高查找速度。

339 利用快表的地址变换过程如下图： 快表 相对地址 页号 页内位移 内存 操作系统 …… + 页表控制寄存器 起始地址 长度 绝对地址 页面号

340 在设置了快表的系统中，系统总是先通过快表中的所有表项进行并行比较，如果发现了匹配的页，则将页面号直接取出，只有当快表中没有匹配的页号时，则按照普通的方式进行地址转换。

341 例题： 1、假定CPU访问一次内存的时间为200ns，访问一次快表的时间是40ns，若快表的饿命中率为90%，试问现在进行一次内存存取的平均时间是多少？比只采用页表下降了多少？

342 解： 现在，通过快表进行内存存取的时间是200ns+40ns=240ns；通过页表进行内存存取的时间是 =400ns。由于快表的命中率为90%，因此现在进行一次内存存取的平均时间是： （200+40）*90%+（ ）*10%=256ns 不采用快表，只有页表进行内存存取，每次需要400ns，也就是说，采用快表比只采用页表少花 =144ns，144ns在400ns中所占的比率为： （144/400）*100%=36%，即下降了36%。

343 例题: 假定访问页表的时间为100ns，访问联想寄存器的时间为20ns，希望把进行一次内存访问的平均时间控制在140ns之内，试问这是要求联想寄存器的命中率是多少？

344 解： 题中给出访问页表的时间为100ns，也就是说访问一次内存需要100ns，于是通过页表进行一次内存存取的时间为100ns+100ns，通过快表进行一次内存存取的时间为100ns+20ns，设命中率为 x，于是有如下等式成立： ( )*(1-x)+(100+20)*x=140 x=75% 即命中率至少应为75%。

345 动态页式存储管理 动态页面管理在作业或进程执行之前，把 该作业或进程的程序段和数据部分装入内存，其
它部分则在运行过程中动态地装入。这种管理方 法实现了虚拟存储器的概念，解决了作业大而内 存小的矛盾。

346 在动态页式存储管理中，页表被扩充，扩充之后的页表如下 图所示：
页号 页面号 缺页中断位 外存起始地址 改变位 其中： 缺页中断位：该位为“1”表示此页已在内存中； 为“0”表示该页不在内存中。 外存起始地址：该页在辅助存储器中的起始地址。 缺页时，缺页中断程序会根据该地址将所需的页调入内存。 改变位：该页被淘汰时，若曾在内存中被修改，则改变位为“1”； 否则为“0”。根据该位将修改后的页的内容重新写到外存中。

347 由于程序部分地调入内存，所以在执行过程中，其它的页会不断地调入内存，系统采用中断的方式来实现页的调入。称为“缺页中断”。整个中断的过程如下图说示：
保留当前进程的现场 选择一页淘汰 否 调入所需要的虚页 修改页表和存储页面表 恢复被中断进程现场 把该页写回外存 有空闲页面吗？ 该页被修改过吗？ 是 缺页中断

348 缺页中断与一般中断的区别如下： （1）缺页中断是在执行一条指令时产生的中断，并立即转去处理。而一般中断则是在一条指令执行结束后，当发现有中断请求时才去响应和处理。 （2）缺页中断处理完成后，仍返回到原指令去重新指令，因为那条指令并未执行。而一般中断则是返回到下一条指令去执行，因为上一条指令已经执行结束了。

349 当系统执行到某指令，但是该指令页没在内存时，系统会请求调 入该页，若此时内存中没有空闲的页面，此时就必须选择一个页
面淘汰，究竟选择哪一个作为被淘汰的页面，这就涉及到一个置 换的策略问题，常用的置换算法有如下几种： （1）随机淘汰算法。 （2）先进先出算法： （3）最近最久未使用页面置换算法（LRU）。 继续

350 选择在内存中驻留时间最长的一页将其淘汰。系统按照 进入内存的先后顺序将页面连接成链表。每次选择表头 的页面置换，而新换入的页链入表尾。
先进先出算法： 选择在内存中驻留时间最长的一页将其淘汰。系统按照 进入内存的先后顺序将页面连接成链表。每次选择表头 的页面置换，而新换入的页链入表尾。 例题： 设进程P共有8页，切已经在内存中分配有3个页面，程序访问内存的顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。这些数字代表进程需要的程序和数据的页号。计算在执行过程中的缺页率。

351 解：在该进程执行过程中，链表的变化过程如下：
(1) 7 链表首指针 链表尾指针 (2) 7 链表首指针 链表尾指针 7,0 (3) 7 1 链表首指针 链表尾指针 7,0,1 链表首指针 7,0,1,2 链表尾指针 1 2 (4) (6) 2 3 链表首指针 链表尾指针 7,0,1,2,0,3,0 (5) 1 2 3 链表首指针 链表尾指针 7,0,1,2,0,3

352 (7) 3 4 链表首指针 链表尾指针 7,0,1,2,0,3,0,4 (8) 4 2 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2 (10) 2 3 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2,3,0 (9) 4 2 3 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2,3 链表尾指针 (12) 1 2 链表首指针 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1 (11) 3 1 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2,3,0,3,2,1 可以看出，在该题中缺页率为12/17=70.5%

353 若给进程P分配4个页面时，我们可以利用同样方法计算 出发生缺页中断的此时为9次，缺页率为9/17=52.9%
在正常情况下，如果分配给一个进程或作业的页面数 越多，缺页率越低，但是有时并非如此，从上述例题中， 我可以看出当分配给进程的页面数增多时，缺页率反而上 升，这种现象成为Belady现象。 返回

354 最近最久未使用页面置换算法（LRU）。 该方法的着眼点是在要进行页面淘汰时，检查这些 对象的被访问时间，总是把最常时间未被访问过的页面
淘汰出去。 LRU算法需要叫多的硬件支持，系统花费大，故常使 用近似算法，最近没有使用页面淘汰算法是常用的近似算 法。该算法所需的页表及算法流程如下图：

355 查询指针前进一步， 指向下一个表目 选择该页面淘汰 置页面访问位为0 入口 返回 页面访问位=0？ 是 否 页号 页面号 6 1 13 2
6 1 13 2 32 访问位 返回

356 存储保护 地址越界保护： 由页表控制寄存器中页表的长度与虚地址相比较来完成。如：在读取页表的时候，将虚地址中的页号与页表长度比较，若页号大于页表长度，则访问越界。 存取控制保护： 在页表中增加一个保护位，说明对该页的“读、写”的控制，当要访问访问某个页面时，系统会自动检查所做的操作是否满足该页在页表所记录的存取控制的要求。

357 页式管理的优缺点 页式管理有如下优点： （1）它不要求进程的在内存中连续存放，因此 有效地解决了外部碎片。 （2） 实现了虚拟存储方式，提高了内存的利用 率，有利于组织多道程序执行。

358 缺点： （1）需要相应的硬件支持，增加了机器成本。 （2）实现动态页式管理需要增加系统开销，如 缺页中断等。
（3）虽然消除了外部碎片，但是进程中的最后 一页中总有一部分空间得不到利用，形成 内部碎片。 （4）在内外存信息交换时的淘汰算法的选择不 当时，产生抖动现象（即整个系统内外存 之间的页面交换频繁，CPU的利用率显著 降低）。

359 5.5 段式与段页式存储管理 段式存储管理基本思想
5.5 段式与段页式存储管理 段式存储管理基本思想 分区存储管理与分页存储管理不易实现作业与进程之间的程序共享。而段式存储管理则可以有效地解决程序共享的问题。 在该管理方式中，系统将程序按照内容或过程分成段，每段有自己的名字，用户程序的地址空间是二维的。系统一段为单位来分配内存，然后通过地址映射机构将虚拟地址转换成实际的物理地址。多个进程可以通过段名来实现子程序的共享。

360 段式存储管理的虚存空间 段式管理的虚存空间是二维的，它是由“段号”与“段内地址”组成。不同分段中的“段号”是没有顺序关系的（即段与段之间的地址不是连续的），而且段的大小是不等的。

361 段式存储管理用到的数据结构 非共享段表 与页式存储管理类似，系统为每个作业或进程建立一张段
表，保存非共享段的信息。以便实现动态地址变换和缺段 中断处理，段表的结构如下图所示： 段号 起始地址 长度 存取方式 内存内外 访问位 2067 89 只读 内 1 6532 1000 读/写 外 2 7780 567

362 共享段表 系统中所有的共享段信息组成了共享段表，共享段表具有如下表项: 段号 段长 内存始址 外存始址 进程号 存取控制 共享记数器

363 共享段分配的过程如下： （1）第一个进程请求共享段时，为该共享段分配内存， 将该段的信息填入进程的非共享段表中。同时在
共享段表中增加一表项，填入有关数据，置共享 计数器为1。 （2）其它进程请求共享段时，该进程的非共享段表增 加一表项，填入该共享段的物理地址。同时在共 享段表中，填上调用进程名等信息。将共享计数 器+1。 当某个进程不需要共享段时，将该共享段的共享 计数器-1，只有当某个共享段的共享计数器为0时， 系统才能回收共享段的内存。

364 段式系统中共享段的示意图如下： 操作系统 段1 …… 进程1的非 共享段表 段2 共享段1 段n ．．．．．． 进程1的地址空间 共享段2
进程2的非 进程2的地址空间 操作系统 共享段1 ．．．．．． 共享段2 内存

365 缺段中断机制 当进程所需的段还未 调入内存时，便由缺段中 断机构产生 中断信号。由 系统调用缺断处理程序将 所需段调入内存。缺段处
修改段表及空闲区链 按照合适的算法淘汰一个或几个段来相成一个合适的空区 合并空闲区，以形成一个合适的空闲区 为新段分配内存区 内存中有合适 的空闲区吗？ 否 是 请求新段 返回 空闲区容量总 和能否满足？ 当进程所需的段还未 调入内存时，便由缺段中 断机构产生 中断信号。由 系统调用缺断处理程序将 所需段调入内存。缺段处 理过程如下：

366 段式管理的地址变换 地址变换可以使 用如下流程来 描述： 访问虚地址（段号，段内地址） 否 扫描非共享段表，比较段内地址是否小于段长
越界中断处理 修改访问位，若是写操作，则置访问位为“1” 形成物理地址： 该段内存起始地址+段内地址 扫描非共享段表，比较段内地址是否小于段长 是 返回 访问虚地址（段号，段内地址） 是否符合存取方式 该段是否在内存中 存取控制保 护中断处理 缺段中断处理 段式管理的地址变换 地址变换可以使 用如下流程来 描述：

367 段的保护 地址越界保护： 利用段表中的段长项与虚地址中的段内地址进行比 较，若段内地址大于段长，系统就会产生保护中断。 存取控制保护与页式管理类似。

368 段式管理的优缺点 优点： （1）便于程序模块化处理。在分段中，每个程序模块构 成各自独立的分段，并采用段的保护措施，模块之
间不受干扰，因此模块化程序的处理比较好解决。 （2）便于子程序的共享。 （3）段长可以根据需要动态增长，对那些需要不断吸收 新数据的段来说，非常有用。 （4）便于动态链接。由于分段的地址空间是二维的，而 且分段是独立的程序模块，因此可以在程序执行过 程中调入相应的段进行动态链接。而分页管理中， 作业则必须在执行之前链接好，以便实现线性的地 址空间。 （5）实现了虚拟存储管理，而且内外存交换的是一段完 整的信息。

369 缺点： （1）需要更多的硬件支持，提高了机器成本。 （2）为了满足分段的动态增长和碎片的拼接， 给系统带来了一定的难度和开销。 （3）分段的最大尺寸受内存可用空间的限制。 （4）在内外存信息交换时的淘汰算法的选择不 当时，产生抖动现象。

370 段页式存储管理   段式存储管理与页式存储管理各有优缺点，如页式管理能较好地解决系统碎片问题，而段式存储管理能很好地实现程序共享，因此，将页式管理与段式管理的思想结合起来进行内存的管理应该是更具优势的。段页式存储管理就是基于这种思想提出来的。

371 基本思想 在段页式存储管理中，一个程序首先被划分成若干段，每段赋予不同的段号，然后，对每段又划分成固定大小的页，如下图所示。因此程序的虚地址空间由三个部分组成：段号、页号与页内位移量。内存可用区也被划分成若干个大小相等的页面。且每段的信息可以在内存中分开存放，因此，分段的大小不受内存区的限制，可以利用动态页面请求的方式实现虚拟存储。

372 0页 1页 2页 3页 作业A的0号段 4K 8K 12K 16K 作业A的1号段 操作系统 页面0 页面1 页面2 内存 页面3 页面4 页面5 页面6 页面7 页面8 页面9 ．．．．．． 段号 页号 页内位移量

373 段页式存储管理中的数据结构 段表 系统为每个作业建立一张段表，段表中的设置了段 号、页表长度、页表起始地址等属性。 页表 每个段被分成若干页，故每个段需要建立一张页表，将段中虚页与的内存中的页面对应起来。段表与页表之间的关系可以使用下图来描述：

374 起始地址 段表长度 段表地址寄存器 段号 … 页表长度 4 1024 1 7 1028 2 3 1031 段表 页号 页面号 6 9 12 第0段页表 32 第2段页表 内存 操作系统 ……

375 段页式存储管理中的地址变换 在段页式存储管理中，用户程序的虚地址转换成物理地址，需要三次访问内存：第一次是由段表地址寄存器得到段表的起始地址去访问段表，得到对应段的也表起始地址；第二次是访问页表得到物理地址；第三次根据物理地址访问内存中的物理单元。

376 为了提高访问速度，可以在系统中设置高速的联想寄存器， 可以显著提高地址变换的效率。加入高速联想寄存器的地址变
起始地址 段表长度 段表地址寄存器 段号 … 页表长度 段表 操作系统 …… 页号 页面号 页表 物理地址 页内位移 相对地址 页内位移量 + 为了提高访问速度，可以在系统中设置高速的联想寄存器， 可以显著提高地址变换的效率。加入高速联想寄存器的地址变 换过程可以仿效页式管理中快表的地址变换机构。 内存

377 段页式存储管理的优缺点 优点： 由于段页式管理是分页与分段管理方式的结合，所以具有两者的优点。 缺点: （1）增加了软件的管理开销，需要的硬件也增 加了，提高了机器成本。 （2）各种表格也需要占据内存空间。 （3）与分页管理一样，存在着内零头的问题。 （4）地址变换机构，需要昂贵的高速联想寄存 器，否则，指令执行速度很低。

378 5.6 局部性原理和抖动问题 什么是局部性原理？ 绝大部分的程序在执行过程中的某段时间内，CPU总是集中的地访问程序中的某一个部分而不是随即地访问程序的所有部分。这种现象称为局部性原理。

379 什么是抖动问题 工作集： 实验表明，任何程序在部分防如内存时，都有一个临界值的要求，当内存分配小于这个临界值时，内存和外存之间的交换频率将集聚增加，而内存分配大于这个临界值时，再增加内存分配也不能显著减少交换次数。这个内存要求的临界值称为“工作集”。内存与交换次数之间的关系如下图所示：

380 临界值 进程内存量 变换次数 工作集 当给进程分配的内存小于所要求的工作集时，由于内外存之间交换频繁，使得输入/输出处理的时间大大增加，造成CPU因等待数据空转，系统性能下降，形成了“系统抖动”。

381 解决系统抖动的方法： （1）       扩大进程的工作集 （2）       选择适当的页面淘汰算法。

382 第6章 进程与存储管理的示例 6.1 UNIX进程和存储管理简介 UNIX具有以下的特征： 1、开发性 2、多用户、多任务环境
第6章 进程与存储管理的示例 6.1 UNIX进程和存储管理简介 UNIX具有以下的特征： 1、开发性 2、多用户、多任务环境 3、功能强大、实现高效 4、提供了丰富的网络功能

383 UNIX系统进程建立的流程 在UNIX系统中，有两个重要进程：0#进程和1#进程。 0#进程 在UNIX系统中唯一只在核心态下执行的进程它具
有三个功能： （1）在初始化时创建1#进程。 （2）负责调度分配处理机。 （3）负责进程交换。 1#进程负责建立控制终端进程与Shell进程运行。

384 系统中各进程建立的流程如下： 系统自举 （UNIX内核入内存） 初始化程序设置各种表格与数据结构 建立0#进程 建立1#进程 建立终端进程
建立shell进程 用户输入 建立用户进程 显示提示符 执行结束 Shell进程等待 是 否 用户 进程执行 （UNIX内核入内存） ……

385 UNIX进程控制系统结构 UNIX进程控制系统由四个模块构成:与文件系统接口部分、进程创建与调度、进程间控制部分和存储管理部分。 UNIX进程控制系统主要功能有: (1) 进程创建与系统调用 (2) 进程通信 (3) 存储器管理 (4) 进程调度

386 进程控制系统的组成如下图所示: 进程创建与调度 进程间控制部分 存储管理部分 系统调用界面 文件 系统 与文件系统接口

387 6.2 UNIX进程结构 UNIX系统把一个程序看作是一个可执行文件，而把进程看作是“程序执行的实例”。 操作系统为处理机设置了两种运行状态：核心态和用户态。 核心态：表示进程在执行操作系统程序； 用户态：表示进程在执行用户程序，按照需要， 这两种状态在一定时机时进行转换。

388 在UNIX中，一个进程是由三个部分组成的： 进程控制块、 数据段、 共享正文段。
进程的组成 在UNIX中，一个进程是由三个部分组成的： 进程控制块、 数据段、 共享正文段。 继续

389 进程的控制块 UNIX的进程控制块由两个部分组成：进本控制块proc结构和扩充控制块user结构。 Proc结构： 记录着一个进程最基本、最常用的信息。Proc结构的内容是常驻内存的。它的信息主要有：

390 （1）进程的状态信息。进车工在其生命周期内有多种状 态，而且状态之间可以相互转换。 （2）进程的标识信息。该信息给出了用户的标识符和用
户组表示符，以及该进程父进程的标识号。 （3）进程的调度信息。如：进程的优先级数、内存（外 存）驻留时间、进程使用处理机的时间等。 （4）基本控制块与其它组成部分的联系信息。在UNIX 系统中，一个进程由进程控制块、数据段和共享正文 段组成，进程控制块又分为proc部分与user部分， 故在proc结构中，必须要有能够其他部分所在位置 的信息。 如：“数据段起始地址p_addr”、“数据段的长度p_size”、“共享正文段控制块指针p_textp”等。 返回

391 数据段是进程运行时用到的数据及工作区。注意：如果进程执行的程序不能被共享，则把它归入数据段中。UNIX数据段分成三个部分：
(1)系统数据区 (2)用户数据区 (3)用户栈区 继续 返回

392 系统数据区 在整个数据段前面，由两个部分组成：核心栈和进程的user结构。由于user结构位于这个区域前面，因此进程proc结构中的p_addr志向的既是进程数据段的其始地址，也是系统数据区的起始地址和user结构的起始地址。

393 进程的扩充控制块user结构中的信息有： （1）指向proc结构的指针(u_procp)，通过该指针，
proc结构与user结构就可以相互沟通了。 （2）现场保护信息。 （3）与文件结构和读写有关的信息。 （4）各种计时信息。 可以看出，user结构中记录的是系统运行时所必须涉及到的各种控制数据和信息。当进程没有占据处理机时，user结构中的信息可以不在内存中。这也是 UNIX将它安排在进程数据段中的理由。 返回

394 用户数据区 存放程序运行时需要用到的数据和非共 享的程序段。 用户栈区 进程运行在用户态时的工作区。 返回

395 进程的数据段是一个整体，是一个非常驻内存的整体。各个部分之间的关系可以如下图所示：
p_addr p_size Proc结构 User结构 核心栈 用户数据区 用户栈区 数据段 系统数据区 数据段长度 返回

396 共享正文段 “共享正文段”是指能够被多个进程共享的程序。UNIX在内存中专门开辟了一个text结构区域，其中每一个text结构对应一个共享正文段，记录关于这个正文段的有关信息。如共享正文段在磁盘对换区的地址（x_daddr），在内存的地址(x_caddr)，长度(x_size)所有进程数目(x_count)等。 返回

397 综上所述，一个进程的基本控制块proc结构、数据段（包含扩充控制块user结构）以及共享正文段三者之间的关系，可以使用下图描述：
．．．．．． X_caddr X_size X_daddr Text[ ]表 一个 正文 段的 text 结构 P_textp P_addr P_size Proc[ ]表 进程 proc U_procp 核心栈区 用户数据区 数据段 用户栈区 User 常驻内存部分 非常驻内存部分 共享 正文段

398 在UNIX中，进程的上下文由三个部分组成：
进程上下文的组成 在UNIX中，进程的上下文由三个部分组成： (1)用户级上下文 (2)寄存器上下文 (3)系统级上下文 继续

399 在系统中可分为正文段和数据段。进程在执行 时，可利用用户栈区来保存过程调用时的传递 参数和返回值。
用户级上下文 用户级上下文的主要成分是用户程序，它 在系统中可分为正文段和数据段。进程在执行 时，可利用用户栈区来保存过程调用时的传递 参数和返回值。 返回

400 （2）处理机状态寄存器的内容（处理机状态字）， 给出的是机器与该进程相关联的硬件状态。 （3）堆栈指针，指向堆栈中下一项的当前地址。
寄存器上下文 （1）程序计数器PC的内容 （2）处理机状态寄存器的内容（处理机状态字）， 给出的是机器与该进程相关联的硬件状态。 （3）堆栈指针，指向堆栈中下一项的当前地址。 （4）通用寄存器，存放进程在执行期间所产生 的中间结果或参数。 返回

401 系统级上下文 系统级上下文可分为静态和动态两个部分。 静态部分
静态部分 在进程的整个生命期内，系统级上下文的静态部分只有一个，其大小保持不变，它可包括三个部分：进程表项、user结构区、进程区表项、系统区表项和页表。 动态部分 在进程的整个生命期中，系统级上下文动态部分的大小是可变的，它包括核心栈、若干层寄存器上下文。 返回

402 进程的状态和状态转换 UNIX进程在其生命期内，可以处于多种不同的状态，并 记录在进程的proc结构中，进程状态的变迁图如下： 用户态运行
核心态运行 在内存就绪 在内存中睡眠 睡眠并换出 创建 僵死 系统调用 内存足够 内存不够 调度 时间片到 返回 唤醒 换出 终止 睡眠 fork 换出并就绪

403 进程的控制 在UNIX系统中，只设置了进程而没有线程，因此，进程 既是一个独立的拥有资源的基本单位，又是一个独立调
度的基本单位。为了对进程进行控制提供了一系列有关 的系统调用。用户可以利用这些调用来实现创建新进程、 终止一个进程的执行、改变进程优先级等功能。 对进程进行控制的主要系统调用有： （1）fork：创建一个新进程。 （2）exec：改变进程的原有代码（执行一个文件的调用）。 （3）exit：实现进程的自我终止。 （4）wait：将调用进程挂起、等待子进程终止，实现父进 程和子进程的同步。 继续

404 Fork系统调用的格式为：int fork( )
Fork系统调用设有参数，如果执行成功，则创建一个子进程，子进程继承了父进程的许多特征，并具有与父进程完全相同的用户级上、下文。Fork完成下列操作： （1）进程分配一个进程表项和进程标识符。 （2）检查同时运行的进程数目。 对普通用户，能否为之建立进程要受系统事先设定的、允许同时存在的进程数目的限制；超过此限制，则fork系统调用失败。

405 （3）拷贝进程表项中的数据 将父进程的进程表项中的数据拷贝到子进程表项中， 并设置进程的状态为“创建”状态。 （4）子进程继承父进程的所有文件 对父进程的当前目录和所有已经打开的文件的文 件表项中的引用计数加1。 （5）为子进程创建上、下文。 首先，由核心为子进程创建进程上、下文的静态 部分，并将其父进程上、下文的静态部分拷贝到 子进程的上、下文中。然后，再为子进程创建进 程上、下文的动态部分。至此，进程的创建即告 结束，再设子进程的状态为“内存中就绪”。最后， 返回子进程的标识符。 （6）子进程执行 当子进程被调度执行时，其user区的计时字段初始 化返回0。

406 Fork执行的流程图如下： 有足够的内存 否 区和交换区吗？ 创建失败 是 有足够的空闲 proc 结构块吗？
内存中有足够的 空间完成复制吗？ 发生调度且调 度到子系统？ 将子进程状态设为创建 将父进程proc结构项中的数据复制到子进程proc结构中 父进程的打开文件表引用数加1 当前目录索引结点和根目录引用数加1 父进程保存进程上下文，以使子进程被调度时从这里执行 在内存中对父进程 上下文进行逻辑复制 将子进程上下文换出 子进程入就绪队列 创建失败 返回子进程pid 返回0 否 是

407 例如下面是用C语言描述一个父进程创建子进程的过程。
Main() { int pid; printf(“just 1 process now.\n”); printf(“calling fork()…\n”); pid=fork(); if(pid==0) printf(“I’m the child.\n”); else if (pid>0) printf(“I’m the parent.\n”); else printf(“fork failed.\n”); printf(“program end.\n”); }

408 此程序运行的结果为： Just 1 process now Calling fork()… I’m the child.
I’m the parent. Program end. 注意程序末尾的两个“program end”的输出，产生这样输出的原因 就在于从fork( )系统调用后有两个并发的进程执行此语句以后的代码，对于父进程来说它满足pid>0的条件，因此执行其指定的输出语句并接着完成输出程序结束提示信息。对于子进程来说pid=0的条件满足，此时“I’m the child”信息被输出，并且最后一条语句被父进程和子进程个执行了一遍，出现了两条程序结束的信息，这也说明系统调用fork()的引用在系统中创建了新进程。 返回

409 Exec系统调用 Fork系统调用只是将附近成的拥护 上下文拷贝到新进程中，而UNIX又提供了一组系统调用exec，可将一个可执行的二进制文件覆盖在新进程的用户级上下文的存储空间上，用来更新用户级上下文。 Exec系统调用完成的操作有： (1)对可执行文件的检查 (2)回收内存空间 (3)分配存储空间 (4)参数拷贝 返回

410 对于一般进程，在其任务完成后应该尽快撤消。 为了及时回收进程所占的资源，并减少父进程的 干预，UNIX系统利用exit来实现进程的自我终止。
（1）关闭软中断 （2）回收资源 （3）写记帐信息 （4）设置进程为“僵死状态” 返回

411 wait系统调用 wait系统调用，用于将调用进程挂起，知道其子进程因暂停 或终止而发来软中断信号为止。如果在wait调用前，已经有
子进程暂停或终止，则调用进程做适当处理后返回。 Wait完成下列操作： （1）首先查找调用进程是否有子进程，若无，则返回出错码。 （2）若找到一个处于“僵死状态”的子进程，则将子进程的执 行时间加到父进程的执行时间上，并释放子进程的进程 表项。 （3）若未找到处于“僵死状态”的子进程，则调用进程便在可 被中断的优先级上睡眠，等待其子进程发来软中断信号 时被唤醒。 返回

412 文件系统基本概念 文件：文件是一组赋名的相关联字符流的集合，或者是相关联记录 （一个有意义的信息单位）的集合。 文件包括两部分：
文件体：文件本身的信息； 文件说明：文件存储和管理信息；如：文件名、文件内部标识、文件存储地址、访问权限、访问时间等；

413 文件系统基本概念（续） 文件系统：操作系统中与管理文件相关的软件和数据称为文 件系统。即：文件管理软件和被管理对象。
文件系统功能：它负责为用户建立文件，撤消、读写、修改和复制文件，还负责完成对文件的按名存取和进行存取控制。 目录：是由文件说明组成的用于文件检索的特殊文件。

414 文件系统特点 友好用户接口，用户只对文件进行操作，而不管文件结构和存放的物理位置。 对文件按名存取，对用户透明。 某些文件可以被多个用户或进程共享。 文件系统大都使用磁盘、磁带和光盘等大容量存储器作为存储介质，因此，可存储大量信息。

415 文件的分类 1、按文件的性质和用途分类： 2、按文件的组织形式分类： 3、按其他方法分类：

416 文件逻辑结构(文件的组织) 什么是文件逻辑结构？
是指从用户观点出发讨论文件内部的逻辑结构(logical structure)或用户访问模式；文件逻辑结构是用户可见的结构，是用户可以直接处理的数据结构，与物理存储无关。 文件逻辑结构的设计要求： 访问性能：便于检索；便于修改 存储性能：向物理存储转换方便，节省空间

417 文件逻辑结构分类 1、字符流（无结构）： 文件体为字节流，不划分记录，顺序访问，每次读写访问可以指定任意数据长度。是当前操作系统中常用的文件组织。如目标代码，源程序。 2、记录式（有结构）：文件由若干记录构成。记录是一个具有特定意义的信息单位。它由该记录在文件中的相对地址与该记录名所对应的一组键、属性及其属性值所组成。 记录的组成：见P200 图7.2 接下一页

418 文件逻辑结构——1、连续结构 记录式结构文件分类： 连续结构、多重结构、转置结构、顺序结构。 连续结构：
是一种把记录按生成的先后顺序连续排列的逻辑结构。 特点：适用性强，可用于所有文件（字符流式的无结构文件实质上记录长度为一个字符的连续结构文件），且记录的排列顺序与记录的内容无关。但按键值查找速度慢。

419 文件逻辑结构——2、多重结构 如果把记录按键和记录名排列成行列式结构，则一个包含n个记
录名、m个(m≤n)个键的文件构成 m＊n维行列式（如下左图）。 文件记录名和键构成的行列式 R1 R2 … RN 0 … 1 0 … … … … 0 j i K1 K2 … Km 元素aij为0表示键Ki不包含在记录Rj中。 元素aij为1表示键Ki包含在记录Rj中。 特点：用行列式方法浪费存储空间。

420 文件逻辑结构——2、多重结构（续） 多重结构：如果把记录按键组成记录队列(如下图） 则一个包含n个记录名、m个(m≤n)个键的文件构成
文件的多重结构图示 特点：多重结构比连续结构在由给定键的记录搜索速度方面要快。比用行列式节约存储空间。 K1 … Km Ri Rj Rz … Rx Ry Rw … 按键组成记录队列

421 文件逻辑结构——3、转置结构 转置结构： 把含有相同键的记录指针全部指向该键，也就是说，把所有与同一键对应的记录的指针连续地置于目录中该键的位置下 特点：转置结构最适合于由给定键的记录搜索。 文件的转置结构图示 … 含有Ki的所有记录指针 Ki Ri Rj Rw 接下一页

422 文件逻辑结构——4、顺序结构 顺序结构： 把文件中的键按规定的顺序排列起来就 形成了顺序结构文件（有序文件）。
特点：顺序结构可用多种查找方法，查找速度比较快。 接下一页

423 文件搜索包括对键的搜索和对记录的搜索 对键和记录的搜索过程 1）键的搜索过程： 确定给定键在文件中的位置即可。 2）记录搜索过程：
在含有该记录键值的所有记录中查找 所需记录。page 203 图8.6

424 对键和记录的搜索方法 线性搜索法（顺序查找）：算法简单，搜索速度较慢 ，平均比较次数是表长（项数）的1/2。
散列法：用散列函数h(k)计算键的逻辑地址。 散列冲突： h(k1)=h(k2)=A 散列冲突解决方法： （1）线性散列法：i=2、3、。。。 hi(k)=( h1(k)+di ）mod t （di=a*I， a是常数，t是表长） 或（di=r， r是随机数） （2）平方线性散列法： hi(k)= h1(k)+c*(i*i)mod t (c是常数) 3）二分搜索法：对顺序文件（有序文件），用二分搜索法较快。见图7.7

425 文件存取方法 三种文件存取方法 顺序存取、随机存取、按键存取（直接存取） 顺序存取：是按照文件的逻辑地址顺序存取。
随机存取：随机存取法允许用户根据记录编号来存取文件的任一记录，或者是根据存取命令把读写指针移到欲读写处来读写。 按键存取：文件的存取是根据给定的键或记录名进行的。按键存取法首先搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理地址后进行存取.

426 文件的物理结构 什么是文件的物理结构？ 文件的物理结构是指文件在存储设备上存放方法。 关于外存分配单位：
存储介质（如磁盘）与内存交换数据的单位是物理块，外存划分成大小相等的若干物理块，文件信息也被划分成与物理块大小相等的逻辑块，外存以块为单位分配。文件的一逻辑块中信息装入外存一物理块中。 一个记录的大小不一定刚好与一个物理块大小一致。 根据记录的大小，可以将一个记录装入多个物理块。也可以 将多个记录装入一个物理块中。 注意

427 物理结构分类（1、连续文件） 文件的物理结构分为三大类： 连续文件、串联文件、索引文件。
连续文件:它是一种最简单的物理文件结构,它把一个在逻辑上连续的文件信息依次存放到地址连续的物理块中.如图7.8 特点:算法简单 .缺点:文件动态增长困难，易造成外存碎片问题。 适用:对换区

428 物理结构分类（2、串联文件） 串联文件(也称为链接文件)：串联文件结构用非连续的物理块来存
放文件信息。这些非连续的物理块之间没有顺序关系，其中每一个 物理块设有一个指针，指向其后续连接的另一物理块，从而使得存 放同一文件的物理块连接成一个串联队列. 点击图示 。 （另见教材图8.9） 特点:外存可采用离散分配，解决了碎片问题，但搜索效率低，只适合 于顺序存取方式，不适合随机存取.

429 物理结构分类(3、索引文件) 索引结构要求系统为每个文件建立一张索引表，表中每一栏目 指出文件信息所在的逻辑块号和与之对应的物理块号。索引表
的物理地址则由文件说明信息项给出。 点击图示（另见教材图8.10） 特点:离散分配，方便随机存取 缺点:增加了存储空间的开销. 接下页

430 物理结构分类(3、索引文件续) 为索引表分配空间的方式: ①串联方式:索引表所占用的物理块用指针拉成一条链. ②索引方式:
索引表所占用的物理块用一张索引表来登记,这就构成多重(多级索引）. 见图8.11 ③多种寻址方式:(UNIX的文件寻址方式见第9章). 直接寻址：索引表存放在文件目录中。 （对文件头几块） 一次间接寻址：文件目录指出索引表。 （一级索引） 二次间接寻址：二级索引 三次间接寻址：三级索引

431 文件存储设备（1、顺序存储设备） 第i+1块 间隙 第i块 … 磁带结构 特点：只适合顺序存取。连续文件。 优点：容量大;顺序存取速度快
顺序存储设备。如磁带 第i+1块 间隙 第i块 … 磁带结构 特点：只适合顺序存取。连续文件。 优点：容量大;顺序存取速度快 磁带设备的存取速度与下列因素有关: 信息密度(字符数/英寸) 磁带带速(英寸/秒) 块间间隙

432 文件存取设备(2、直接存取设备) 柱面 磁头臂 扇区0 扇区1 扇区3 磁头 磁道 磁道0 磁道1 直接存取设备。如磁盘,光盘等.
磁盘的结构 柱面 磁头臂 扇区0 扇区1 扇区3 磁道 磁道1 磁道0 磁头

433 磁盘地址 磁盘上每个物理块有对应的地址: (柱面号、磁头号、扇区号) 磁盘物理地址与磁盘物理块号对应关系：
为了管理方便，文件系统使用的是磁盘物理块号，磁盘物理地址（三维）与磁盘物理块号（线性）有一一对应关系。启动磁盘输入输出要用磁盘物理地址。磁盘物理地址与磁盘物理块号之间的转换由操作系统中文件系统与设备管理接口实现。

434 直接存取设备的特点 1、适合连续文件、串联文件、索引文件 2、适合直接存取(按键存取.随机存取)

435 8.4文件存储空间管理 空闲物理块管理方法: 空闲文件目录(空闲盘区说明表) 空闲块链 位示图

436 空闲文件目录 空闲文件目录是一个特殊的目录，其中每个表项对应一个磁盘空闲区， 一个空闲区由多个连续的空闲块构成。 区号 首块号 块数 块号
1 40 5 40~44 2 60 3 60~62 80 6 80~85 … 分配算法、释放算法：类似于内存动态分区管理。 特点：空闲文件目录方法适用于连续文件结构的文件存 储区的分配和回收

437 空闲块链接法 有以下几种拉链方法: 空闲块链:空闲块链中每一结点是一个空闲物理块.
空闲块链接法把文件存储设备上的空闲块链接在一起。 有以下几种拉链方法: 空闲块链:空闲块链中每一结点是一个空闲物理块. 3 5 10 15 … free …… 空闲区链:以空闲区为单位拉链，一个空闲区是若干个连续的物理块。 3 6 5 4 13 12 11 … 21 20 free

438 成组链接法 链尾组:下一组块号指针为0(链尾标志)， 实际块号数只有n-1个 链首组:可能不足n个块号，链首组存放在文件资源表中,系统
成组链接法:(UNIX) 空闲块分组拉链. 将文件存储设备上的空闲块的块号分组，每组包含n个块号如:n=50,n=100， 并利用一组空闲块中的第一块存放链中下一组中的块号和块数，由此拉成 一条链。 块号n 。。。。。。 块号2 块号1 块数n 也是链中下一组指针 每组块号存储结构: 也作为栈指针使用 链尾组:下一组块号指针为0(链尾标志)， 实际块号数只有n-1个 链首组:可能不足n个块号，链首组存放在文件资源表中,系统 运行时,存放在内存空闲块号栈中。 接下一页

439 成组链接示意图 49 310 49 如:当前系统空闲块号按每组50个空闲块分组

440 成组链接法(分配与回收) 成组连接法的分配与回收:
空闲块号成组链的链首组存放在文件资源表中(盘上专用区)，系统运行时链首组被装入内存空闲盘块栈中。分配时将栈顶空闲块号弹出堆栈分配给文件使用。回收空闲块时，将空闲块号压入栈顶。分配回收过程中大部分时间在内存栈中进行，不需访问外存。只有在分配时遇栈空或回收时遇栈满才需启动磁盘，以装入下一组块号或将栈中一组块号写到磁盘。分配回收速度较快 。 接下一页

441 成组链接法举例1（分配） 例1：已知磁盘上有18个空闲块，块号依次为：
1、3、5、7、14、15、17、18、19、23、24、25、28、29、30、32、34， 请按5个块号为一组.成组拉链。 解: 因 17 ÷ 5 = 3 … 2 可知共应分为4组，链尾组4个块号，链首组3个块号。 成组拉链情况图所示: 5# # # 1 3 5 7 14 15 17 18 19 23 24 25 28 29 30 32 34 4 2 第四组 第三组 第二组 第一组 链首组 链尾组

442 成组链接法举例2 （分配） 例2:如前例成组链，为文件A分配两块之后， 1、3号空闲块依次出栈分配给文件A，成组链变为: 7 14 15 17 18 5 1 19 23 24 25 26 29 30 32 34 4 2 3 S-free 内存栈中 5# 第四组 第三组 第二组 第一组

443 成组链接法举例3 （分配） 例3.接着A又需2块，当前堆栈中只有一块号(5号)，需装入下一组块号到内存堆栈(简称堆栈装入)。执行过程如下：
将5#存放的一组块号装入堆栈. 将5#块分给文件A 将7#块分给文件A S-free 1 2 3 4 4 5 4 18 26 分配之后成组链的状态 17 25 34 15 24 32 14 23 30 内存栈中 19 29

444 成组链接法举例4 （回收） 例4.按着A释放块号5，系统回收该块号，成组链变为: 5 14 15 17 18 19 23 24 25 26
29 30 32 34 4 1 2 3 S-free 内存栈中 18# 第三组 第二组 第一组 26# 接下一页

445 成组链接法举例5 （回收） 例5.按着A释放块号1、3。由于内存栈已满一组块号，不能再压入回收块号，需将栈中的一组块号写入回收的块号对应的物理块中(简称栈满腾空)。 回收块号1、3之后.成组链的状态: 5 14 15 17 18 1 3 2 19 23 24 25 26 29 30 32 34 S-free 内存栈中 1# # # 第四组 第三组 第二组 第一组

446 成组链接法优点、特点 1、不需额外的空间存储空闲块信息 2、分配和回收大部分时间在内存，速度快。 3、启动一次磁盘可以读入或写出一组块号，
减少I/O次数 4、只适合非连续分配（链接文件、索引文件）

447 第七章 习题 PAGE202 ; (物理块长度改为512字节每个记录长度1024字节） 补充习题：已知磁盘上有21个空闲块，块号依次为： 1、3、5、7、14、15、17、18、19、23、24、25、28、29、30、32、34、41、43、45、21 1、请按6个块号为一组，成组拉链。 2、图示依次回收块号42、47、48后成组链的状态 3、为文件分配3块，指出分配块号，并图示分配 后成组链的状态 。

448 03 / 2004 文件链式结构图示 文件 A 的 FCB 存 储 器 首块号 1 2 3 首记录 4 驶多飞集团的演示

449 文件索引结构图示 FCB 索引表 1 2 4 3 b0 b1 b2 b3 b4 存 储 器 索引表地址 2 1 4 3 03 / 2004
4 3 b0 b1 b2 b3 b4 存 储 器 索引表地址 1 2 3 4 驶多飞集团的演示

450 7.5 文件目录管理 文件的说明:我们把文件名和对应该文件实施控制管理的控制管理信息
称为该文件的说明。存放文件说明信息的数据结构通常称为文件控制块. 文件目录:文件目录是文件说明信息集合。一个文件的说明 信息构成 文件目录中的一个表目。 目录文件：存放目录的文件称为目录文件，是一类特殊的文件。

451 对文件目录管理的要求 1)有效利用存储空间 2)快速检索文件 3)解决文件命名冲突问题 4)方便文件共享

452 文件目录结构 1)单级目录： 特点： 可实现按名存取，但未解决重名问题， 检索效率低. 见图7.15 2)二级目录：主目录(MFD):
特点： 可实现按名存取，但未解决重名问题， 检索效率低. 见图7.15 2)二级目录：主目录(MFD): 用户文件目录(UFD) 特点：基本解决重名问题，各用户之间 也可实现文件共享。搜索速度快于单级目录。 见图7.16 3)多级目录(树型目录)： 特点：层次清晰；解决了文件重名问题；查找搜索速度快. 见图 7.17

453 文件共享方法 实现文件共享的三种方法: 绕道法：用户指出文件访问的逻辑路径 2) 链接法：相关目录表之间进行链接。
3) 利用基本文件目录表实现共享 接下一页

454 （a）对文件的链接 （b）对目录的链接 图示： 文件的共享链接

455 便于共享文件目录组织 接下一页 为了便于共享和在文件查找过程中减少I/O次数，提高文件查找速度，将文件目录分成两个部分来存放:
1)符号文件目录SFD ，树型结构 SFD中仅包含文件名及文件ID。 2)基本文件目录BFD 、线性结构 BFD中包含除文件名外的其它所有信息 (如：物理块号、 结构、存取控制 …)。 BFD中的表目序号即为文件ID。 每一个物理文件在SFD和BFD中占一表目。 接下一页

456 采用基本文件目录的多级目录结构之例 Zhang的SFD 物理块号 9 8 7 6 5 4 3 2 1 标识符 id 空闲文件目录 Zhang
标识符 id 空闲文件目录 Zhang Wang Sub_d z.c f.c w.c b.c a.c 主目录(MFD) Wang的SFD Sub_d的SFD ID Zhang的SFD

457 利用不同SFD的表目中对应同一ID来共享同一物理文件
采用基本文件目录共享文件方法 利用不同SFD的表目中对应同一ID来共享同一物理文件

458 目录管理 为提高文件查找速度,减少I/O次数,在内存中用两张表存放当前 正在使用的文件的目录信息。 活动名字表:
存放活动文件的SFD表目，每个用户一张表。 活动文件表: 存放活动文件的BFD表目，整个系统一张表. 相应的系统调用: fopen()：打开文件，将对应SFD项从盘复制到内存活动名字表，BFD 项复制到内存活动文件表。见PAGE 196 fclose()：关闭文件，将文件I/O缓冲区写盘，删除文件在内存 的副本 (即回收内存空间，回收活动名字表 和 活动文件表中所占表目)。

459 7.6文件存取控制 文件系统存取验证模块的功能: 对于拥有读、写或执行权限的用户, 应让其对文件进行相应的操作.
对于没有拥有读、写或执行权限的用户，应禁止他们对文件进行相应的操作. 应防止一个用户冒充其他用户对文件进行存取。 应防止拥有存取权限的用户误用文件。

460 验证用户文件操作 验证用户的文件操作是否合法: 审定用户的存取权限. 比较用户权限的本次存取要求是否一致.
将存取要求和被访问文件的保密性比较，看是否有冲突. 存取控制验证方式: 存取控制矩阵; 存取控制表; 口令; 密码术.

461 存取控制矩阵 存取控制矩阵: 存取控制矩阵方式用一个二维矩阵来实现存取控制。 见P198 图7.20

462 见P198 图7.21 存取控制表 存取控制表: 以文件为单位把用户按某种关系划分为若干组，同时
规定每组的存取权限。每个文件的存取控制表存放在文件 说明中。存取控制验证效率高。 见P198 图7.21

463 口令方式 口令方式: 文件设置口令,输入口令正确才能操作文件. 缺点: 保密性差

464 密码方式 密码方式: 在用户创建源文件并将其写入存储设备时对文件进行 编码（加密），在读出文件时对其进行译码（解密、还原）。
加密过程见P199 图7.22 优点：保密性好 缺点：系统开销较大（加密、解密需花处理时间）

465 7.7 文件的使用 文件系统提供的四类服务：Page 199 文件系统用户接口：
命名接口:chmod mkdir cp ls rmdir 等 系统调用:create read close open delete 程序访问文件的一般过程: fd= open() / create() read(fd. …) / write(fd. …) close(fd)

466 7.8 文件系统层次模型 文件系统是一个层次结构，Madnick将文件系统划分为8层。 见图 层模型

467 文件系统层次模型举例 举例:P203 习题14 Read(SQRT , 5 , 15000)各层执行结果：
Read(fd , , ) //SFD 获得 SQRT的BFD //BFD 合法性检查 5 * 500 / 1000 = 2 … 500 //记录号转换成逻辑块号 (记录号 * 记录长度 / 物理块长度 = 相对块号 … 块内字节地址) 用相对块号2查BFD中的地址信息获得对应物理块号 物理块号转换成(柱面号 磁头号 扇区号 ) 启动I/O （与设备管理的接口）

468 第八章 设备管理 本章主要内容: 设备管理的功能和任务、数据传送控制方式、 中断技术、缓冲技术、设备分配、
第八章 设备管理 本章主要内容: 设备管理的功能和任务、数据传送控制方式、 中断技术、缓冲技术、设备分配、 I／O控制系统、设备驱动程序等内容 本讲主要内容: 设备管理的功能和任务 数据传送控制方式 中断技术

469 8.1.1 设备分类 按使用特性分类： 存储设备 输入输出设备 终端设备 脱机设备 P205 图 按从属关系分类： 系统设备 用户设备
8.1.1　设备分类 按使用特性分类： 存储设备 输入输出设备 终端设备 脱机设备　　　　　P205　图 按从属关系分类： 系统设备 用户设备　　　　　 按信息组织方式分类： 块设备 字符设备

470 8.1.2　设备管理的功能和任务 主要任务：见P205 主要功能：见P205

471 8.2　数据传送控制方式 什么是数据传送控制方式： 数据传送控制方式是指如何控制设备与内存之间的数据传输过程的方式。

472 数据传输控制方式的发展过程 程序（CPU）直接控制方式 中断驱动方式 DMA控制方式 通道控制方式

473 数据传送控制方式 程序直接控制方式 中断控制方式 DMA方式 通道方式　　　　　 点击标题进入

474 程序直接控制方式(programmed direct I/O) ： 由CPU直接控制内存和外围设备之间的信息传送。I/O操作
制，包括发送读写命令、循环测试设备状态、传输数据。 接下页

475 接下页 （b） CPU 外围设备 发Start命令 接收到Start命令 做接收或发送数据准备 设备标志触发 器为“Done” 否
程序直接控制方式图示 接收到Start命令 做接收或发送数据准备 等待CPU来的下条命令 标志触发器置“Done” 执行下条命令 开始数据传送 等待 发Start命令 准备完毕？ 设备标志触发 器为“Done” 外围设备 （a） 否 是 CPU 接下页 （b）

476 程序直接控制方式示例－CPU控制控制输入数据过程示例
向I/O部件发读命令 读I/O部件状态寄存器 检查状态 从I/O部件读字节数据 将该字节写入内存 No ready ready 该块读完 yes 下一 指令 no 接下页

477 程序直接控制方式优缺点 优点：控制简单。 缺点：1）CPU和外围设备只能串行工作。
　　3）由于程序直接控制方式依靠测试设备标志触发器的状态位来控制数据传送，因此无法发现和处理由于设备或其他硬件产生的错误。 适合：专用控制系统；外设较少、CPU速度较慢的系统。 返回

478 中断控制方式 工作方式：CPU向I/O部件发出命令后，转去做其他有用的工作。
后，利用中断通知CPU，再由CPU完成设备与内存的数据传输。 特点： CPU不必反复测试寄存器状态，节约了时间。CPU可以 与设备并行工作。但每个字节的数据传输都必须经过CPU寄存器转发。 中断控制方式结构图见 P208 图8.3 接下页

479 接下页 CPU 设备 向设备发Start命令， 将中断允许位置1 接收到CPU到Start指令 调度程序调度其他程序 准备数据并将其
中断控制方式处理过程 中断处理（处理数据传输） 接收到CPU到Start指令 准备数据并将其 置入缓冲寄存器 标志触发器置“Done” 调度程序调度其他程序 向设备发Start命令， 将中断允许位置1 缓冲寄存 器满吗？ 收到中断信号 了吗？ 设备 否 是 CPU 其他进程执行 被中断进程执行 接下页

480 中断控制方式输入数据CPU控制控制过程示例
向I/O部件发读命令 读I/O部件状态寄存器 检查状态 从I/O部件读字节数据 将该字节写入内存 OK 出错处理 该块读完 下一 指令 未OK 中断 接下页

481 中断控制方式优缺点 优点：CPU利用率较程序直接控制器有大大的 提高，且能支持多道程序和设备的并行操 作。
缺点：1）在一次数据（若干字节）传送过程中， 发生中断次数较多。 　　　2）CPU由于中断次数增多而无法响应中 断和出现数据丢失。 适合：低速的字符设备 返回

482 直接存储访问方式(DMA, Direct Memory Access)
工作方式：由程序设置DMA控制器中的若干寄存器值（如内存始址，传送字节数），然后发起I/O操作；在DMA控制之下完成内存与外设的成批数据交换，在操作完成时由DMA控制器向CPU发出中断。 特点：DMA与CPU分是共享总线，DMA通过挪用总线周期的方式把数据缓冲寄存器中的数据直接送到内存地址寄存器所指向的内存区域。 接下页

483 DMA方式下的I/O传送结构 见P210　图8.5 接下页

484 DMA方式下的数据传送处理过程 见P210　图8.6 接下页

485 直接存储访问方式优缺点 优点：CPU只需干预I/O操作的开始和结束，而一批数据传输由DMA控制，
无需CPU控制，提高了CPU与设备的并行工作程度，排除了中断方式中的 数据丢失现象。适于高速设备。如：磁盘 缺点：DMA方式对外围设备的管理和某些操作仍由CPU控制。系统中多个 DMA同时使用，可能造成内存地址冲突。管理和控制复杂化。 　　　DMA方式一次只能传送一批地址连续的数据块，如果需传送多个地 址不连续的数据块，则需启动DMA多次。 返回

486 通道控制方式(channel control)
通道的定义及工作方式： 　通道是一个独立于CPU的专管输入输出控制的处理机，它控制设备 与内存直接进行数据交换。它有自己的通道指令，由通道指令构成通 道程序。由CPU启动通道工作，通道通过执行通道程序控制数据传输， 并在操作结束时向CPU发中断信号，由CPU进行传输结束中断处理通道。 通道指令包括：1）操作码　 2）内存地址　 　　　　　　　3）读或写的字节计数　 　　　　　　　4）记录结束标志R 　　　　　　　5）通道程序结束位P 接下页

487 通道程序 通道程序： 通道程序根据进程提出的数据传输要求由系统自动生成，存放在内存。 通道程序示例：
一个六条通道指令所构成的简单通道程序，其功能是将内存中不同地址的数据写到三个记录中。 操作 P R 字节计数 内存地址 备注 WRITE 80 813 140 1034 1 60 5830 R1结束 300 2000 R2结束 250 1850 720 R3结束，程序结束 接下页

488 通道方式的数据传输结构 通道方式的数据传输结构：见P212 图8.7 通道类型：
选择通道(selector channel)：可以连接多个外设，而一次只能访问其中一个外设，执行一道通道程序（单道工作方式）。以块为单位传送数据，速度快，适合高速外部设备。如：磁盘，磁带。 字节多路(byte multiplexor channel)通道 ：以字节为单位传送数据，多个外设分时轮流使用通道（分时系统工作方式）。适合连接低速字符设备。 数组多路(block multiplexor channel)通道：以块为单位传送数据,可以并发访问多个外设，分时执行多道通道程序。适合连接中高速外部设备。如：磁盘，磁带。 接下页

489 通道方式的数据输入处理过程 通道控制方式的处理过程：
当进程要求设备输入数据时，CPU执行Start指令指明I/O操作、通道程序地址、设备号和对应的通道。 对应通道接收到CPU发来的启动指令之后开始工作，把存放在内存中的通道指令程序读出并执行，并设置对应设备的I/O控制其中的控制状态寄存器，是设备开始工作。 设备准备好数据，由通道把数据送往通道指令指定的内存区域。 若数据传送结束，通道通过中断请求线发中断信号请求CPU做中断处理。 　通道控制方式的描述过程见P212　 接下页

490 通道控制方式优点 优点：启动一次通道执行一个通道程序可以传送几批地址不连续的数据块。数据传输过程中对CPU的干扰比DMA更少，CPU利用率更高，对通道的控制更简单。 　　通道通过执行通道程序控制输入输出，比较灵活。 返回

491 8.3 中断技术 中断的基本概念： 中断：是指计算机在执行期间系统内发生任何非寻常的或非预期的
8.3　中断技术 中断的基本概念： 中断：是指计算机在执行期间系统内发生任何非寻常的或非预期的 急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行相 应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或调 度新的进程执行的过程　 中断源、响应中断、处理中断　　　 禁止中断：PSW中中断允许位。 用来禁止和开放中断。 屏蔽中断：PSW中的中断屏蔽字段。每位对应一类中断的中断屏蔽触 发器。用软件方法可以设置。用于屏蔽某些中断。 　　

492 中断的基本概念（续） 中断向量：PSW＋处理程序的入口地址。每类中断有对应的PSW及处理程序的入口地址。
关中断：即禁止中断，系统不响应中断。 中断嵌套：在处理中断的同时又响应别的中断。 屏蔽中断的运用：在中断处理程序正在执行时可以用屏蔽中断的方法。 屏蔽同级或同级以下的中断。 可用提高处理机优先级的方法禁止中断和屏蔽某些中断。 　　　

493 中断的分类与优先级 外中断：是指来自处理机和内存外部的中断。包括I/O中断、外部信号
中断、各种定时器引起的时钟中断以及调试程序中设置的中断点等引起 的调试中断等。狭义上一般称为中断。 　　　 内中断：主要指在处理机和内存内部产生中断。 内中断一般称为陷阱。 它包括程序运算引起的各种错误、系统调用等。 　　　 中断优先级：按中断源的轻重缓急响应中断，操作系统对不同的中断赋予不同的优先级。中断优先级决定系统响应中断的优先次序。 处理机优先级：现行程序的优先级，可用来禁止中断和屏蔽中断。　　

494 中断与陷阱的区别 陷阱通常由处理机正在执行的现行指令引起，而中断则是 由与现行指令无关的中断源引起的。
陷阱处理程序提供的服务为当前进程所用，而中断处理程 序提供的服务则不是为了当前进程的。 CPU在执行完一条指令之后，下一条指令开始之前响应中 断，而在一条指令执行中也可以响应陷阱。 　　

495 软中断 软中断： 软中断是通信进程之间用来模拟硬件中断的一种信号通信方式。 实现软中断通信的系统调用(如unix) ：
软中断是通信进程之间用来模拟硬件中断的一种信号通信方式。 　　　 实现软中断通信的系统调用(如unix) ： kill(pid,sig) 发送软中断信号 signal(sig,func) 进程设置软中断信号到 达时的处理方式

496 中断处理过程： 判断中断响应条件 关中断 保存被中断现场 分析中断原因 转中断处理程序 执行中断 处理子程序 恢复现场 开中断 返回中断点

497 中断处理过程（续） I/O中断的处理的控制过程、形式化描述： I/O Interrupt processing control: begin
unusable I/O Interrupt flag save status of interrupt program if Input Device i Ready then Call Input Device i Control fi if Output Device i Ready then Call Output Device i Control fi if Data Deliver Done then Call Data Deliver Done Control fi restore CPU status reset I/O Interrupt flag end Input Device i Control:…… Output Device i Control:…… Data Deliver Done Control:……

498 8.4 缓冲技术 缓冲的引入： 为了匹配CPU或用户应用进程与外设的处理速度；
减少对CPU的中断次数，提高CPU和I/O设备之间以及各个I/O设备 之间的并行性； 解决DMA或通道方式的瓶颈问题。 实现方法： 专用硬件缓冲器 内存专用缓冲器

499 缓冲的种类 单缓冲(single buffer)：设一个缓冲区，CPU和外设轮流使用， 一方处理完之后接着等待对方处理。
双缓冲(double buffer)：设两个缓冲区，CPU和外设都可以连 续处理而无需等待对方。要求CPU和外设的速度相近。 多缓冲(multiply buffer)：多个缓冲区，CPU和外设的处理速 度可以相差较大。如用于输入或输出的环形缓冲区。（一般是 专用） 缓冲池(buffer　pool)：由多个缓冲区构成，既可用于输入也 可用于输出，多个进程共享，可用于多种设备。（通用，利用 率高）

500 (a)单缓冲 ;(b)双缓冲; (c)循环缓冲
I/O设备 输入 用户进程 操作系统 (a) (b) (c) 　(a)单缓冲 ;(b)双缓冲; (c)循环缓冲

501 缓冲池的管理 缓冲区类型（三种） 空闲缓冲区（em)：没有数据的缓冲区。 输入缓冲区(in)：装满了输入数据的缓冲区
输出缓冲区(out)：装满了准备输出到设备的缓冲区 缓冲区工作方式（四种）： 1、设备正在输入数据到缓冲区。称为收容输入。 2、CPU正在读入输入缓冲区的内容到用户区。称为提取输入。 3、CPU正在输出数据到缓冲区。称为收容输出， 4、正在将输出缓冲区内容输出到实际设备，称为提取输出。 上述操作访问各个缓冲区队列时，需要进行相应的互斥操作。

502 缓冲池的管理（续） 缓冲区队列：三种：图如下所示： 工作缓冲区: 四种：图如下所示： CPU … F（em） F（in） F（out）
缓冲区1 缓冲区n L（out） L（in） L（em） 缓冲区2 工作缓冲区:　四种：图如下所示： hin sin sout hout 收容输入 提取输出 I/O设备 提取输入 收容输出 CPU

503 缓冲池管理（续） 四个操作： take_buf (type) (被get_buf调用)
　 add_buf (type) (被put_buf调用) 　 get_buf (type,number) (申请缓冲区供进程使用) 　 put_buf (type,work_buf) (将缓冲区放入相应队列，供进程使用) 参数说明： type: em in out Work_buf: hin hout sin sout

504 缓冲区状态转换图 hout out sout get_buf put_buf em hin in sin

505 get_buf 和put_buf 过程描述 设：互斥信号量 S（type） 初值为１
资源信号量　RS（type）　初值为ｎ（n为type队列长度） 　　　　　 如：em队列：初值为ｎ； 　　　　　 in队列：初值为０； out队列：初值为０ get_buf ( )程序描述如下： get_buf(type,number): begin P(RS(type)) P(S(type)) Pointer of buffer(number)=take_buf(type,number) V(S(type)) End put_buf ( )程序描述如下： put_buf(type,number) begin P(S(type)) add_buf(type,number) V(S(type)) V(RS(type)) end

506 以下数据结构用来记录设备或部件的标识状态等信息：
8.5.1　设备分配用数据结构 　以下数据结构用来记录设备或部件的标识状态等信息： 系统设备表　SDT：每个系统设备占一表目 设备控制表　DCT：每个设备一张 控制器控制表　COCT：每个控制器一张 通道控制表　CHCT：每个通道一张

507 设备分配数据结构及其关系图 DCT 设备控制表 SDF 设备类型 表目1 设备标识 设备忙／闲标记 获得设备的进程 表目i COCT指针
… 表目i 表目1 DCT指针 获得设备的进程 设备标识 设备类型 控制器等待队列尾 控制器等待队列首 COCT指针 设备忙／闲标记 控制忙／闲标记 CHCT指针 控制器标识 通道忙／闲标记 通道等待队列尾 通道等待队列首 通道标识 SDF DCT　设备控制表　 控制器控制表COCT CHCT　通道控制表 等待进程队列

508 8.5.2 设备分配原则 设备分配的原则： 合理使用外设(公平和避免死锁)，提高设备利用率。 与设备分配有关的设备属性：
独享设备：打印机等； 共享设备：磁盘、网卡等；虚拟设备。 设备分配方式： 静态分配：在进程分创建时分配，在进程退出时释放； 优缺点：不会出现死锁； 　　　　　设备利用率不高； 动态分配：在进程执行过程中根据需要分配，使用结束后释放； 优缺点：需要考虑死锁问题 　　　　有利于提高设备利用率

509 设备分配策略 设备分配策略：针对特定的设备采用特定的分配策略。
先来先服务(FCFS)：按I/O请求的先后顺序，排成I/O请求命令队列；按FCFS分配设备； 基于优先级：依据进程的优先级，指定I/O请求的优先级，排成不同优先级队列；按优先级高低分配设备；

510 设备分配算法 分配过程：如下所示 进程申请 I/O 分配设备 分配 控制器 分配通道 进程加入设 备等待队列 进程加入通 道等待队列
设备分配流程图见P222图　8.13 分配过程：如下所示 进程申请 I/O 分配设备 分配 控制器 分配通道 进程加入设 备等待队列 进程加入通 道等待队列 进程加入控制 字等待队列 成功 不成功 启动I/O

511 8.6 I/O进程控制 什么是I/O控制? 从用户进程的输入输出请求开始，给用户进程分配设备和启动有关设备进行I/O操作，以及在I/O操作完成之后响应中断，进行善后处理为止的整个系统过程为I/O控制。

512 I/O控制的功能 1）处理用户请求、分配设备、分配缓冲、启动设备 （启动过程） 2）处理I/O中断 （中断处理） 中断原因分析 唤醒
1）处理用户请求、分配设备、分配缓冲、启动设备 （启动过程） 2）处理I/O中断 （中断处理） 中断原因分析 唤醒 中断处理程序 设备分配程序 I/O请求处理 缓冲区管理 外设中断请求 用户进程I/O请求 I/O控制 中断响应 启动I/O 执行设备驱动程序或通道程序

513 I/O进程控制过程 I/O控制过程: 依据用户的控制命令对外设进行控制，并返回结果。控制过程可分为 以下6步：
转换：将抽象的命令转换为具体的一定次序的指令。 合法性检查：检查I/O操作请求的合法性。 可用性检查：检查控制器和设备的状态，判断是否可用。 参数设置：设置控制器和设备的参数，包括构造必要的通 道程序。 启动I/O：向控制器或设备发起I/O操作。 中断处理：提供必要的中断处理例程，以便I/O完成时调 用。

514 I/O控制的实现 三种方式: 作为请求I/O操作的进程的一部分实现: 要求I/O的进程具有实时性,即时处理设备中断。 作为当前进程的一部分：
　a:每类（个）设备设一专门的I/O进程，且该进程只能在系统态下执行。 　b:整个系统设一I/O进程，全面负责系统的数据传送工作。I/O进程可分 为输入进程和输出进程。 　c:每类（个）设备设一个专门的I/O进程，但该进程既可在用户态也可 在系统态下执行。

515 8.7 设备驱动程序 设备驱动程序 驱动物理设备和DMA控制器或I/O控制器等直接进行I/O操作的子程序
定操作的类型和数据流向等。 设备驱动程序的特征 中转数据和控制：不是数据和控制的源端和目的端（应用　　　　　　　　　　程序和设备） 与硬件特性密切相关：通常由硬件厂商提供。 向上屏蔽设备细节：不同类型设备通常其设备驱动程序接口不　　　　　　　　　同，同类设备的接口相同。 设备驱动程序是设备与应用程序间的接口：使应用程序可以用统一的方式来使用设备。

516 设备驱动程序（续） 系统用设备开关表对设备驱动程序进行管理，设备开关表
系统用设备开关表对设备驱动程序进行管理，设备开关表　 DST（Device Switch Table）包含每类设备各种子程序入 口地址，如下表所示： 设备类 Open Close Read Write 磁带 打印机 磁盘 　DST也是I/O控制进程使用的数据结构。它根据该表调用设备驱动程 序做启动相应操作。

517 补充－假脱机技术 利用假脱机技术(SPOOLing, Simultaneous Peripheral Operation On Line, 也称为虚拟设备技术)可把独享设备转变成具有共享特征的虚拟设备，从而提高设备利用率。 引入：在多道批处理系统中，专门利用一道或几道程序来完成对设备的I/O操作。无需使用外围I/O处理机。

518 假脱机的原理： SPOOLing程序和外设进行数据交换，可以称为“实际I/O”。一方面，SPOOLing程序预先从外设输入数据并加以缓冲，在以后需要的时候输入到应用程序；另一方面，SPOOLing程序接受应用程序的输出数据并加以缓冲，在以后适当的时候输出到外设。 在SPOOLing程序中，需要管理两级缓冲区：内存缓冲区和快速外存上的缓冲池，后者可以暂存多批I/O操作的较多数据。 应用程序进行I/O操作时，只是和SPOOLing程序交换数据，可以称为"虚拟I/O"。这时虚拟I/O实际上是从SPOOLing程序的缓冲池中读出数据或把数据送入缓冲池，而不是跟实际的外设进行I/O操作。

519 优点： 高速虚拟I/O操作：应用程序的虚拟I/O比实际I/O速度提高，缩短 应用程序的执行时间。另一方面，程序的虚拟I/O操作时间和实际 I/O操作时间分离开来。 实现对独享设备的共享：由SPOOLing程序提供虚拟设备，可以对 独享设备共享使用。 举例：打印机设备和可由打印机管理器管理的打印作业队列。 如：Windows NT中，应用程序直接向针式打印机输出需要15分钟， 而向打印作业队列输出只需要1分钟，此后用户可以关闭应用程序 而转入其他工作，在以后适当的时候由打印机管理器完成15分钟 的打印输出而无需用户干预。

520 补充：磁盘设备管理 CPU和内存的访问速度比磁盘要快若干个数量级，磁盘系统的性能 对整个系统的性能有重要影响，磁盘设备管理的目标就是提高磁盘
系统的性能。

521 磁盘I/O访问时间的组成 柱面定位时间：磁头移动到指定柱面的机械运动时间；
旋转延迟时间：磁盘旋转到指定扇区的机械运动时间；它与磁盘转速相关，如：软盘转速可为600rpm(每分钟转速)，硬盘可为3600rpm。 数据传送时间：从指定扇区读写数据的时间。 返回

522 磁盘数据的存储位置对磁盘I/O性能的影响
由于柱面定位时间在访问时间中占主要部分，合理组成磁盘数据的 存储位置可提高磁盘I/O性能。 例子：读一个128KB大小的文件： (1)文件由8个连续磁道(每个磁道32个扇区)上的256个扇区构成： 20ms+(8.3ms+16.7ms)*8=220ms; 其中，柱面定位时间为20ms，旋转延迟时间为8.3ms，一个磁道上32个 扇区数据传送时间为16.7ms； (2)文件由256个随机分布的扇区构成： (20ms+8.3ms+0.5ms)*256=7373ms; 其中，1扇区数据传送时间为0.5ms； 随机分布时的访问时间为连续分布时的33.5倍。

523 磁盘I/O调度策略 来自不同进程的磁盘I/O请求构成一个随机分布的请求队列。磁盘
先进先出算法 优先级算法 最短查找时间优先算法 扫描(SCAN)算法 双队列扫描(FSCAN)算法

524 先进先出(FIFO, First In First Out)算法：磁盘I/O执行顺序为磁盘I/O请求的先后顺序。

525 最短查找时间优先(SSTF, Shortest Service Time First)算法：
考虑磁盘I/O请求队列中各请求的柱面位置，选择从当前磁头位置 出发，移动臂移动距离最短的磁盘I/O请求。 该算法的目标是使每次磁头移动时间最少。它不一定是最短平 均柱面定位时间，但比FIFO算法有更好的性能。 可能会有进程处于饥饿状态。 扫描(SCAN)算法： 选择在磁头前进方向上从当前位置移动距离最短的磁盘I/O请求执 行，没有前进方向上的请求时才改变方向。（也叫电梯调度算法） 该算法是对SSTF算法的改进，磁盘I/O较好，且没有进程会饿死。

526 磁盘I/O调度举例： 例如：如果现在读写磁头正在53号柱面上执行输入输出操作，而等待 访问者按I/O请求的时间先后顺序依次要访问的柱面为：
98，183，37，122，14，124，65，67 先来先服务调度 磁头移动总距离640个柱面 平均移动距离＝640/8=80个柱面 0　14　37　53　65　67　98　122　124　183　199 最短寻找时间优先调度 磁头移动总距离236个柱面 平均移动距离＝236/8=29.5个柱面

527 磁盘I/O调度举例（续） 例如：如果现在读写磁头正在53号柱面上执行输入输出操作，而等待访问
98，183，37，122，14，124，65，67 SCAN调度算法：外移方向 磁头移动总距离208个柱面 平均移动距离＝208/8=26个柱面 0　14　37　53　65　67　98　122　124　183　199 SCAN调度算法：里移方向 磁头移动总距离299个柱面 平均移动距离＝299/8=37.4个柱面

528 第九章 UNIX文件和设备管理 9.1 文件系统的特点与文件类别 特点： UNIX的文件是无结构的字符流式文件。 文件可以动态的增长或减少
9.1　文件系统的特点与文件类别　 特点： UNIX的文件是无结构的字符流式文件。 文件可以动态的增长或减少 文件数据可由文件拥有者设置相应的访问权限而受到保护。 设备可通过文件系统隐蔽掉设备特性。 文件的分类： 目录文件：由文件系统中的各个文件的目录项所形成的文件。 普通文件：无结构、无记录概念的字符流式文件。 设备文件：设备文件有对应的目录项和I节点，但并不占有实际的物理 存储块。

529 9.2 文件系统数据结构及其关系图 文件系统的存储结构： 文件系统由每块512字节的或512字节倍数所构成的逻辑块序列组成。
9.2　文件系统数据结构及其关系图　 文件系统的存储结构： N# …… K＋ 2# K＋ 1# 1# 0# 引导块　超级块　索引结点表 数据块 1#… K# 文件系统由每块512字节的或512字节倍数所构成的逻辑块序列组成。 一个物理存储器可包含一个或多个文件系统。

530 几种常用的数据结构 　 资源管理结构filsys 磁盘i节点 目录项 内存索引节点 系统打开文件表 用户打开文件表　

531 资源管理结构filsys 资源管理结构filsys 该结构中含有文件系统空闲块分配用堆栈及i节点分配用数据结构。
　　　UNIX System V中的filsys结构如下： 　　　struct filsys { 文件卷总块数； 　　　　　 i节点表总块数； 　　　　　 空闲块栈区（小于或等于50）；//空闲块号成组链链头 　　　　　 空闲块栈指针； 　　　　　 空闲块栈互斥标志； 　　　　　 空闲块总数； 　　　　　 空闲i节点数组指针； 　　　　　 空闲磁盘i节点指针； 　　　　　 空闲i节点数组互斥标志； 　　　　 　空闲i节点总数； 　　　　 　filsys的修改标志，等； 　　　｝　

532 磁盘i节点 i节点（索引节点）：用来存放文件的说明信息。 磁盘i节点（BFD）:占64个字节。一块可放8个索引节点。 磁盘i节点结构 ：
　　　struct dinode { 文件模式；/*即文件类型*/ 　　　　　 与该i节点联接的文件数； 　　　　　 用户标识； 　　　　　 文件大小； 　　　　　 存储权限； 　　　　　 同组用户标识； 　　　　该文件所用物理块的块号；/*13个块号，四种寻址方式*/ 　　　　　 文件存取时间、修改时间和建立时间； 　　　　　 空闲i节点数组互斥标志； 　　　｝　

533 内存i节点、目录项 一个磁盘块可容纳32个目录项 2. 内存索引节点：inode 存放正在使用文件的磁盘i节点内容和当前使用状态信息
（如：　锁标志、引用计数等） 目录项 磁盘i节点标识符id 文件名 （14个字节）　　　　　（2个字节）　 一个磁盘块可容纳32个目录项

534 系统打开文件表及用户打开文件表 用户打开文件表： 用来登记被打开文件在系统打开文件表中的指针fp，用户打
系统打开文件表及用户打开文件表　 用户打开文件表： 用来登记被打开文件在系统打开文件表中的指针fp，用户打 开文件表表目序号作为文件描述符fd，用户进程使用fd 读写文件。 一个进程可同时打开20个左右的文件。用户打开文件表存放在每个 进程的user结构中。 系统打开文件表： 用来存放各进程使用和共享文件的有关信息： f-offset 文件读写指针 f-count 共享文件的进程计数（引用计数） f-inode 内存索引结点指针 f-flag　　 读写标志 其表目编号作为fp记入相应用户打开文件表中。

535 为什么引入系统打开文件表和用户打开文件表
为什么引入系统打开文件表和用户打开文件表　 为了实现用户进程对文件可能进行的三种读写方式： 第一种方式：多个用户读/写各自的文件。 第二种方式：多个用户共享一个文件、但彼此独立地对 文件进行读/写。读/写指针独立。 第三种方式：多个用户共享一个文件、且共享一个读/写 指针（如父子进程）。

536 9.3 资源管理和地址映射 资源管理: 磁盘i节点的分配与释放 内存i节点的分配与释放 系统打开文件表的分配与释放 文件地址映射:
9.3　资源管理和地址映射 资源管理: 磁盘i节点的分配与释放 内存i节点的分配与释放 系统打开文件表的分配与释放 文件地址映射: UNIX系统采用索引结构存放文件物理块的地址，并采用多种寻址方式。（多种索引方式）进行寻址。

537 磁盘i节点的分配与释放 磁盘i节点分配算法ialloc： 为新建文件分配磁盘i节点和内存i节点（见P233）
用法如下： 磁盘空闲i节点按编号由小到大顺序依次进入该数组。 铭记i节点：在空闲i节点数组中最大（最后）一个i节点。由它决定从索引 节点区搜索空闲i节点的起始位置。 在系统运行时将空闲i节点数组装入内存专用区（空闲i节点栈中）以减少 分配磁盘I节点时启动I/O的次数。 当空闲i节点数组中的i节点分配完时，启动I/O，从铭记i节点开始搜索一 批空闲索引节点，将其编号写入空闲i节点数组，直到数组装满或再也找不 到空闲i节点。 磁盘i节点分配算法ialloc：　 为新建文件分配磁盘i节点和内存i节点（见P233） 磁盘i节点释放算法ifree：　 见P233

538 内存i节点的分配与释放 分配内存i节点（iget）： iget根据给定的磁盘i节点号从内存i节点数组中搜索相应的内存i节点。
注意：访问计数加1 释放内存i节点（iput）： 当一个文件被关闭时，系统释放其内存i节点。UNIX系统中，释放内存I 节点的过程是iput。Iput首先判内存i节点的访问计数是否等于1，如果访问 计数等于1的话，则表示当前没有其他用户使用该文件，只需把内存i节点项 的内容复制回磁盘i节点后就可释放该内存i节点项。如果访问计数大于1，则 只需将访问计数减1即可。 注意：访问计数减1

539 系统打开文件表的分配与释放 见page 234 系统打开文件表项的分配（getf）：
　系统打开文件表的分配与释放 　系统打开文件表项的分配（getf）： 打开一个文件时需为该文件分配内存i节点、分配系统打开文件表表项。 填写有关内容，并建立数据结构之间的关系。 注意：父子进程共享文件时的处理、进程共享文件时的处理。 释放用户打开文件表项（close）、 释放系统打开文件表项（closef） 当一个文件被关闭时，系统释放其用户打开文件表项和系统打开文件表项以 及内存索引节点。 注意： 系统打开文件表项共享计数减1后为0时，才对内存索引节点共享计数减1， 只有当共享计数为0时才清空相应表项。 见page 234

540 地址映射 UNIX系统采用索引结构存放文件物理块的地址，并采用多种寻址方式 （多种索引方式）。
　地址映射 UNIX系统采用索引结构存放文件物理块的地址，并采用多种寻址方式 （多种索引方式）。 在i节点中，文件地址信息存放在di-addr[40]地址数组中，每个物理 块号占3个字节，共可放13个物理块号。 假定磁盘每块512字节，一个索引块可存放170个文件数据块号。 文件寻址方式：假定文件中某一逻辑地址A （文件中相对地址） 寻址方式 寻址范围(单位：字节） 文件规模 直接寻址 A＜10*512 小型文件 一次间接寻址 10*512≤A＜(10+170)*512 中型文件 二次间接寻址 (10+170)*512≤A＜( )*512 大型文件 三次间接寻址 ( )*512≤A＜( )*512 巨型文件

541 文件的地址映射图 索引块： 可存放170个块号 di.addr(12) di.addr(11) di.addr(10) …
　文件的地址映射图 索引块： 可存放170个块号 di.addr(12) di.addr(11) di.addr(10) … di.addr(2) di.addr(1) di.addr(0) 直接寻址 一次间址 二次间址 三次间址 数据块 428 91 331 334 952 i.di_addr[40]: di.addr(9)

542 将欲读写的文件逻辑地址（字节偏移量）A转换为文件逻辑块号L和块 内偏移W。
　文件地址映射过程 将欲读写的文件逻辑地址（字节偏移量）A转换为文件逻辑块号L和块 内偏移W。 W= A mod 512 A / 物理块长 ＝ A/512 L= 100 180 150 200 1 2 3 id-addr[10] 索引块 把文件逻辑块号转换为物理块号。 　　　　例如：　A=9000　 9000/512＝13…..344 　 可知: 逻辑块号为13　 　 因为： 10 ≤ 13 ＜10+170 　 所以：用一次间接寻址，从 id-addr（10） 中获得索引块的块号; 　 计算一次间接寻址索引块查表索引： 13 -10＝3 　　　 从索引块中取出第三项，假定物理块号是100 。 启动磁盘从100号物理块读取文件块到内存， 根据字节偏移344，得到相应文件信息。 100#

543 逻辑块号L与寻址方式关系 寻址方式 逻辑块号L 物理块号B 直接寻址 L＜10 di_addr[L] 一次间接寻址
二次间接寻址 (10+170) ≤L＜( ) 三次间接寻址 ( )≤L＜( )

544 9.4 目录与文件搜索方法——目录结构 目录结构：
　9.4　目录与文件搜索方法——目录结构 目录结构： UNIX目录采取树型目录结构，采用BFD和SFD结构管理文件。即一个文件的说明信息分成两部分两部分存放：索引节点（i节点)和目录项。 i节点存放在索引节点表中；目录项在某级目录文件中。 因此，对文件的搜索包括对目录的搜索和对i节点的搜索。

545 　目录文件的搜索 对目录文件的搜索： 线性搜索法：用文件名依次与目录文 件中各个目录项中文件名比较，直到匹配，然后取出其i节点号。

546 由于磁盘i节点表是顺序表结构， i节点编号即表序号，直接用i节点编号作为查表索引。
　对索引节点的搜索 对i节点的搜索：包括对磁盘i节点和内存i节点的搜索 1、磁盘i节点的搜索： 由于磁盘i节点表是顺序表结构， i节点编号即表序号，直接用i节点编号作为查表索引。 2、内存i节点的搜索： 由于内存i节点表采取散列表结构， 采用散列函数返回值作为查表地址。

547 散列函数定义：（x为i节点号 ）ihash(x)=&hinode[(int)(x)%128] 或
　内存索引节点表 内存i节点的搜索采用散列搜索法： 内存i节点散列表数据结构如下： struct hinode { struct inode * i-forw; } hinode[128]; 散列函数定义：（x为i节点号 ）ihash(x)=&hinode[(int)(x)%128] 或 ihash(x)= &hinode[(int)(x)&127 Hash冲突解决方法： 同一hash函数值的内存i节点构成一个队列， 队首由散列表hinode中的i-forw指出。

548 内存i节点组织图 i－forw … 对同一hash函数值的i节点的搜索采用顺序搜索方法 &hinode [0] [1]
… &hinode [i] [127] …… 对同一hash函数值的i节点的搜索采用顺序搜索方法 hinode[128]

549 文件搜索的实现——namei过程 算法namei描述详见：P236 namei过程： namei将文件路径名转换成文件的内存i节点指针。
其中： 目录变量：存放当前搜索过程的文件路径名中的某个分量 （目录名/文件名） 。 i节点变量：存放当前目录对应的i节点。初始为根。文件 名匹配成功后，被置为目录变量中的名字对应的i节点。 循环1次：从i节点变量对应的目录文件中搜索目录变量中 的名字。 算法namei描述详见：P236

550 文件系统的系统调用与低层算法如下图所示:
系统调用： create open close read write link unlink chown chmod pipe 文件系统的系统调用与低层算法如下图所示: 系统调用 中断和陷阱总控模块 文件系统低层算法 设备管理算法 trap指令　系统态 用户态

551 文件系统的系统调用（续） 打开文件建立进程与文件的通路： 三张表：用户打开文件表、 系统打开文件表、 内存i节点表
三张表表目地址（位置）表示： 　 fd:用户打开文件表中的位置；　　 fp:系统打开文件表中的位置； 　 内存i节点表地址。 系统打开文件表的共享文件进程计数（引用数)：表示有多少用户 打开文件表项指向该项。 4) 内存i节点表的访问计数（引用数）：表示有多少系统打开文件表 项指向该内存i节点。 见图 p238

552 系统调用read的实现过程描述 见P239

553 9.6 UNIX system V的中断和陷阱概念 中断：由与当前执行进程无关的事件引起。（如：I/O设备中断）
异常或陷阱：由与当前执行进程有关的事件引起。（如系统调用、 指令出错等） 中断、异常向量表SCB（系统控制块）：见P240　图9.8 中断和陷阱处理的几点不同： 中断和陷阱运行在不同的堆栈：中断处理在系统中断栈上运行； 陷阱在当前进程的核心栈上运行。 进入陷阱处理程序与处理机状态字（PSW)的中断优先级无关，而中 断响应与此有关。 3) 陷阱处理不发生进程切换；中断处理可能发生进程切换

554 UNIX system V的中断和陷阱总控程序
中断和陷阱总控程序：trap.s　汇编编写 中断和陷阱总控程序功能：当陷阱或中断发生时，处理机将自动地根据陷阱或中断名找到对应处理程序的入口地址，从而转入去执行相应的处理程序。陷阱或中断处理完恢复现场。

555 中断分类 进程调度中断：当runrun标志被设置时，则在中断或陷阱处理结 束时，产生进程调度中断信号，由进程0调用Xreshed过程进行处
理。 时钟中断：间隔时钟中断。间隔时间16.667微秒，时钟中断发生 60次（即1秒）时，由时钟中断处理程序设置调度标志runrun。 并计算各进程优先级。 电源失效和恢复 机器故障中断：进行现场保护与恢复，以及有关检验等。 设备中断：包括控制台中断、单总线适配器中断和多总线适配器 中断等。

556 中断处理： 中断处理包括三部分： 中断响应→陷阱总控程序→中断处理→退出中断 如果中断在用户态下发生，在中断返回时设置调度标志runrun
UNIX system V的中断和陷阱处理 中断处理： 中断处理包括三部分： 　　中断响应→陷阱总控程序→中断处理→退出中断 如果中断在用户态下发生，在中断返回时设置调度标志runrun 陷阱处理： 陷阱一般在用户态下发生。陷阱发生后，首先转入中断陷阱总控程序 trap.s，再转入公共陷阱入口处理程序trap trap调用形式：trap(sp, type, code, pc, ps) 栈指针　陷阱类型　系统调用代码　程序计数器　PSW内容

557 陷阱类型及处理流程 陷阱类型：12类陷阱 见P241 其中9种转换成软中断信号向当前进程发送； 对SYSCALL、SEGFLT(地址转换失效)、　RESCHED (进程调度)转相应处理程序进行处理。 trap程序处理流程（见P243　图9.9）

558 系统调用的处理 确定系统调用序号i i=code&377 若0<i<64,则是i真正的系统调用序号；
接参数指针再求系统调用号。 传递参数到user结构中：u.u-arg:参数指针，以便处理程序可以 通过该指针使用参数。 3) 转入系统调用处理程序：系统调用表system：参数个数，处理程 序入口。 4) 系统调用完后计算当前进程优先级。 若需重新调度，则执行调度程序，选择优先级高的进程执行。 检查发生系统调用的进程是否收到了软中断信号，如收到了软中断信号的话，则进行软中断处理。 返回

559 9.7　缓冲管理 块设备缓冲区管理 字符设备缓冲区管理

560 设备缓冲队列（b链:双向链表、散列队列）； 设备请求队列（块设备av链:单向链表） 。
块设备缓冲管理－缓冲池结构 缓冲池由200多个缓冲区构成，每个缓冲区由缓冲控制块（缓冲头部） 和缓冲数据区两部分构成。每个缓冲区有512/1024字节，能容纳一个磁盘 块数据。缓冲池中有三种缓冲队。 空闲缓冲队列（av队列双向链表）； 设备缓冲队列（b链:双向链表、散列队列）； 设备请求队列（块设备av链:单向链表） 。

561 缓冲控制块结构 逻辑设备号 块号 状态 指向缓冲数据区指针 指向空闲缓冲队列的 前向指针 后向指针 指向缓冲队列的前向指针
指向缓冲队列的后向指针

562 空闲缓冲队列结构 图2 图1 向前指针 空闲队列av头 buf[1] buf[2] buf[n＋1] 向后指针 buf[0]分配给进程
新释放空闲缓冲

563 设备缓冲队列结构 设备b链链接所有分配给各类设备使用的缓冲区。每类设备都有自己的设备b链。每类设备的设备b链按散列法组织成64个队列。 散列队列头标 b63 mod 64 b1 mod 64 b0 mod 64 64 128 63 127 191 1 63 用散列函数构造或搜索散列队列： i＝(b_dev+b) mod 64 b_dev:设备号　b:逻辑块号（b0~b64)

564 设备请求队列结构（块设备av链） 每个物理设备都有一个I/O请求队列，是由正在请求该块设备进行读/写操作的缓冲区所组织成的单向队列。

565 三个缓冲队列之间的关系 一个空缓冲区可能同时属于av链和某设备b链 （缓冲区已释放但数据有效） 一个设备请求队列中的缓冲区属于某个设备b链

566 块设备缓冲区的分配 块设备缓冲区的分配： 　 getblk(dev,blkno)过程用于为指定设备和指定盘块申请缓冲区，需处理5种情况（见P246） 　　getblk流程图： 　　getblk():该过程从空闲缓冲队列中获得一空闲缓冲区将其加入某一设备b链。需处理“延迟写”缓冲区。

567 块设备缓冲区的释放 块设备缓冲区的释放： brelse()过程 　　在“延迟写”、“异步写”方式或缓冲区使用完后，释放缓冲区，将释放缓冲区挂入av链链尾，但并不立即从设备b链中取下，以便当其中数据有效的情况下可被再次利用。此外需唤醒等待空缓冲区的进程。

568 缓冲区与内存用户区之间的数据传送（iomove、文件系统接口）
块设备缓冲区数据的读写 缓冲区数据读写包括两个方面： 磁盘块与缓冲区的读写； 缓冲区与内存用户区之间的数据传送（iomove、文件系统接口） 磁盘块 缓冲区 内存 用户区 bwrite bdwrite bawrite bread,breada iomove 缓冲区的数据读写

569 磁盘块读入数据到缓冲区有两种方式 一般读（bread）：读入指定设备指定块到内存缓冲区。调用
bread处理过程描述见P247 预先读:breada(bno1,bno2) bno1：立即读块号；bno2：异步读块号 将bno1立即读入缓冲区（同步方式） 将bno2采用异步方式读入。只启动传输，不等完成。 优点：当进程需bno2时，它可能已准备好，在内存缓冲区中。 这样可加快进程处理数据的速度。 breada过程描述见P248

570 缓冲区数据写到磁盘块的方式 同步写：启动磁盘，等待传输完成才释放缓冲区。 异步写：启动磁盘，不等待传输完成就释放缓冲区。
延迟写：不启动磁盘，打上“延迟写”标志释放缓冲区 bwrite(一般写)：实现同步、异步、延迟写操作： 　　　　 bwrite: 输入：缓冲区指针 　　　　 begin 　　　　　　 启动磁盘写； 　　　　　　 if 缓冲区标志写是同步进行 　　　　　　 then 等待传输完成后释放缓冲区 　　　　　　 fi 　　　　　　 if 缓冲区标志延迟写 　　　　　　 then 将该缓冲区放入空闲av队列 end

571 bawrite(异步写)：实现异步写。只需为缓冲区打上“异步写”标志，　　　　　　　　然后调用bwrite。
bdwrite(延迟写)：实现延迟写。只需为缓冲区打上“延迟写”标志，　　　　　　　　然后调用bwrite。 　　延迟写缓冲区是由getblk过程用异步写方式进行输出的。 异步写与延迟写的优缺点： 异步写的目的是程序提高写盘速度，而延迟写的目的则是为了让数据块 在内存内待尽量多的时间，以减少不必要的I/O操作。但反过来，由于 延迟写没有立即把数据写入磁盘，当系统发生瘫痪等时将产生磁盘数据 错误。

572 9.8 块设备驱动 I/O子系统：管理块设备和字符设备的程序模块，其核心是控制 外设的设备驱动程序。
9.8　块设备驱动 I/O子系统：管理块设备和字符设备的程序模块，其核心是控制　　　　　　外设的设备驱动程序。 本节主要介绍UNIX系统块设 备驱动原理 设备配置 设备文件的创建：mknod命令 参数：文件名及路径、文件类型、 主设 备号、次设备号 例：　mknod/dev/ttyb c 设备驱动程序的接口　 　硬件设备 设备驱动程序 文件系统 I/O指令、控制寄存器、中断向量 块设备开关表、字符设备开关表 　驱动程序与文件系统和硬件的接口：见P250　图9.14

573 设备开关表 字符设备开关表：　见P251　图9.15　 块设备开关表：　见P251　图9.15 主设备号是设备开关表的表目索引号　　　

574 close： 关闭设备。即释放一个进程占用的设备，断开用户进程 与设备的连接。
设备开关表(续） 系统调用： open:　打开设备。即分配设备给进程 close： 关闭设备。即释放一个进程占用的设备，断开用户进程 与设备的连接。 策略接口stratygy过程： 实现缓冲区与设备之间的I/O传输： 调用_strat启动控制器→调用_addr转换地址。 　　　　　　　　　　　→启动设备开始I/O传输。 　　　　　　　　　　　→调用iowait进入睡眠。 I/O中断发生后处理中断，唤醒睡眠进程。

575 设备中断 中断向量与对应的中断处理程序按设备类设置的。 图9。16 块设备驱动程序功能: (1)启动设备开始传输 　　　　　　　　　 (2)处理中断　　　　　 见P252

576 9.9 字符设备驱动--字符缓冲池 字符设备管理的数据结构： 字符设备开关表 缓冲区结构 缓冲队列 字符缓冲池
9.9　字符设备驱动--字符缓冲池 字符设备管理的数据结构：　 　字符设备开关表　缓冲区结构　缓冲队列 字符缓冲池 　字符缓冲池由150个缓冲区cblock组成，其中每个缓冲区可容纳　 64个字节，其结构如图：见P252 　图9.17　　　　　 缓冲池中有二类缓冲队列： 空闲缓冲队列。cfreelist 见P253　图9.18 I/O字符缓冲区队列：clist　分配给各种设备使用的字符缓冲区构成不同的缓冲队列。　见P253　图9.19

577 对字符缓冲区队列的操作 对字符缓冲区队列的操作：（6 种操作） 从空闲缓冲队列分配一个缓冲区给驱动程序。
把一个缓冲区释放后放入空闲缓冲队列。 从I/O缓冲队列中提取一个字符，并调整该I/O缓冲队列的字符计数。 把一个字符放入I/O缓冲队列中的最后一个缓冲的末尾。 从I/O缓冲队列中每次移走一个缓冲区中的所有字符或n(n>1)个字符。 往I/O缓冲队列中每次送一个缓冲区的字符或n(n>1)个字符。

578 以上6个操作由以下8个过程完成 getcf 6) putcb putcf 7) getcbp getc 8) putcbp putc
字符缓冲区队列的操作 以上6个操作由以下8个过程完成 getcf ) putcb putcf ) getcbp getc ) putcbp putc getcb 各函数的解释见P253

579 行规则程序：属内部接口程序。对输入输出数据提供格式变换功能。 工作方式：标准方式（要进行格式转换） 原始方式（不进行格式转换）
终端驱动程序－字符设备驱动程序之例 终端驱动程序包括： 行规则程序：属内部接口程序。对输入输出数据提供格式变换功能。 　　工作方式：标准方式（要进行格式转换） 原始方式（不进行格式转换） 　　功能：1）通过分析将输入字符串变成行 　　　　　2）处理删除键，以便用户能够从逻辑上部分地删除敲　　　　　入的字符序列。 　　　　　3）处理删除行的字符，从而使得在当前行上敲入的所　　　　　有字符无效。 　　　　　4）处理输入字符格式，例如把表格和空格符号变为空　　　　　格字符序列。 　　　　　5）把输入的字符回送到显示屏上。 　　　　　6）为终端挂起，断线或响应用户敲入的delete键向进　　　　　程发软中断信号。 　　　　　7）允许不做格式变换的原始方式。

580 终端驱动程序－字符设备驱动程序之例（续）
标准方式下的终端驱动程序。 使用三个I/O缓冲队列： 　　输出数据缓冲队列 　　原始输入缓冲队列 　　标准输入缓冲队列 终端驱动程序组成 ttwrite:调用行规则程序实现终端输出功能　见P255 ttread:实现从终端输入数据的功能　见P255 ttopen:打开终端 ttclose:关闭终端 ttioctl:分配/释放缓冲区，调整I/O队列