操作系统复习笔记

---

---

第1章 绪论

1.1 操作系统的定义和特性

操作系统：是一个大型的程序系统

• 它负责计算机系统软、硬件资源的分配
• 控制和协调并发活动
• 提供用户接口，使用户获得良好的工作环境

简而言之：管理并调度资源；为用户提供接口

不同视角理解

• 终端用户：界面和命令
• 应用程序员：编程接口API
• 系统程序员：管理和调度资源；提供接口
• 例
  

操作系统地位：

操作系统特性

• 并发性：同时处理多个任务的能力
• 共享性：为多个并发任务提供资源共享
• 不确定性：具有处理随机事件的能力(中断处理能力，自动化能力…)

1.2 操作系统功能

进程管理

• 进程控制：创建，暂停，唤醒，撤销
• 进程调度：调度策略，优先级
• 进程通信：进程间通信

存储管理：为应用程序运行高效提供内存空间；支持多道程序设计

• 内存分配
• 内存共享
• 内存保护
• 虚拟内存

设备管理：提供统一的设备使用接口，管理设备分配和使用

• 设备无关性
• 设备传输控制
• 设备驱动

文件管理：文件和目录管理，提供简便统一的信息存取和管理方法，并解决信息共享、数据的存取控制等问题

• 存储空间管理
• 文件操作
• 目录操作
• 文件和目录的存取权限管理

1.3 操作系统的性能

吞吐率：在单位时间内处理信息的能力

响应能力：从接收数据到输出结果的时间间隔

资源利用率：设备使用的频度

可移植性：改变硬件环境仍能正常工作的能力：代码修改量

可靠性：发现、诊断和恢复系统故障的能力

1.4 操作系统的发展历史

四个经典阶段

计算机硬件发展的四个经典阶段

• 电子管时代
• 晶体管时代
• 集成电路时代
• 大规模集成电路时代

操作系统发展的四个典型阶段：

手工操作、单道批处理、多道批处理、分时操作系统

手工操作

• 电子管时代
• 结构特点
  • 硬件：电子管、接线面板（按钮/开关）
  • 程序：二进制（卡片/纸带，打孔）
• 使用特点
  • 上机：编程（打孔），预约，操作机器（开关/接线）
  • 程序启动与结束：手工处理
• 缺点
  • 效率低：CPU运行时间少 100min=50(装)+10(运行)+40(拆)
  • 用户独占
  • 缺少交互

单道批处理系统

• 晶体管时代
• 工作过程
  • 多个作业输入到磁盘形成作业队列
  • 监控程序依次自动处理磁盘中每个作业（装入-运行-撤出-装入-运行-撤出）
  • 运行完毕，通知用户取结果
  • 具体例子
    • 将卡片装入1401机（读卡），将程序读入磁带
    • 将磁带装入7094机（计算），完成计算
    • 将磁带装入1401机，打印结果
• 工作特点
  • 一批：作业队列
  • 自动：识别作业
  • 单道：串行
• 实现方式1：联机批处理
  
  • 特点：主机控制输入输出
  • 缺点：系统效率低
• 实现方式2：脱机批处理
  
  • 特点：卫星机控制输入输出
  • 优点：系统效率高
  • 缺点：调度不灵活；保护问题
• CPU利用情况：
  • 例：read(dev,x);y=f(x);
    
  • 现象：外设工作时CPU休闲，CPU工作时外设休闲
  • 结论：CPU和外设效率低
  • 改进：增加启动和测试两个函数代替read():StartRead(dev,x),WhileReading();
    
  • I/O,CPU交迭条件
    • 程序设计合理：I/O发生时，程序可以做一些其他工作
    • 系统提供工具：程序可以启动设备和测试设备

多道批处理系统

• 多道程序设计技术：在内存中存放多道程序,当某道程序因为某种原因（例如请求I/O时）不能继续运行时，监控程序便调度另一程序投入运行。这样可以使CPU尽量处于忙碌状态，提高系统效率。采用多道程序设计技术实现的处理系统称为多道批处理系统
• 设计目的：提高系统的利用率（或吞吐量）CPU与外设并行，外设之间也并行
• 例子：
  
• 设计思想
  • 多个程序同时在计算机/虚拟机上运行
  • 物理资源的共享
    • 时分：分成多个时段：不同进程错开使用不同时段
    • 空分：分成多个单元：不同进程同时使用不同单元
• 特点
  • 多道：内存同时存放多道程序
  • 宏观并行，微观串行
• 意义：操作系统形成
• 缺点
  • 作业处理时间长
  • 运行过程不确定
  • 交互能力差

分时操作系统

• 60年代硬件两个重大进展
  • 中断技术：CPU收到外部信号（中断信号后，停止当前工作，转去处理该外部事件，处理完毕后回到原来工作的中断处（断点）继续原来的工作
  • 通道技术：专门处理外设与内存之间的数据传输的处理机
• 背景
  • 中断技术
  • 大规模集成电路
  • 事务性任务和程序涌现：要求交互性高，响应快速
  • 要求：多任务多用户
• 多终端计算机：主机采用分时技术轮流为每个终端服务，每个终端都感觉到 是“独占”主机
• 分时技术：主机以很短的“时间片” 为单位，把CPU循环地轮流分配给每个作业（终端 /用户）使用，直到全部作业被运行完
  • 特点：时间片：较短时间间隔；相应及时：独占主机
• 特点
  • 多路调制性：多用户联机使用同一台计算机
  • 独占性：用户感觉独占计算机
  • 交互性：及时相应用户的请求
• 实例：Linux：50ms或可设置， Win：?

进一步发展

实时操作系统/嵌入式操作系统

• 背景

  • 实时要求：军事，工业控制，智能仪器等
  • 要求：某些任务要优先紧急处理且系统安全可靠

• 特点

  • 可靠性
  • 安全性
  • 强调作业完成的时限和可预测性
    • 硬实时系统：必须限时完成，工业控制，制导系统
    • 软实时系统：尽可能块完成，广播通讯

微机操作系统（PC机）

• 特点：良好的层次结构。BIOS+OS，可移植性好；适应性好，易学易用
• 苹果、Win

多处理机操作系统

• 定义

  • 并行系统；紧耦合系统

  • 包含两个或多个功能相当的处理器

  • 共享内存，共享I/O，共享外设

  • 一个操作系统控制

• 特点：

  • 并行处理能力
  • 紧耦合、存在瓶颈、可扩展性差
  • 不支持大规模并行计算；不支持分布处理

网络操作系统

• 定义

  • 独立自治的计算机相互连接形成一个集合

  • 普通OS+网络通信+网络服务

  • Unix/Linux/Win

• 特点

  • 多个处理部件
  • 无公共内存
  • 具备消息通信机制

• 局限性

  • 不能支持透明的资源存取
  • 不能对网络资源进行有效、统一的管理
  • 不能支持合作计算

分布式操作系统

• 定义：分布的多个通用资源部件，经过网络互联，由操作系统对资源进行全局统一的管理和调度
• 特点
  • 可扩展性、增加性能、高可靠性
  • 特殊的计算机网络。
  • 主机自治，又相互协调，运行分布式程序
• 与计算机网络的区别
  • 分布式系统：虚拟为“单台”处理机
  • 计算机网络：指明主机位置

适合学习和研究的简化操作系统：Minix OS

• 微内核架构
• 类Unix

推荐学习的大型开源操作系统：Linux

---

第2章 操作系统结构与硬件支持

2.1 操作系统的逻辑结构

OS的设计和实现思路

整体式结构(单体式结构，宏内核结构)

定义：模块化结构/单体内核结构/宏内核结构。操作系统由大量过程构成。每个过程都有明确参数列表、返回值类型。大多数过程是可以相互间调用。

以模块为基本单位构建：每个模块具有特定的功能

优点

• 模块的设计、编码和调试独立
• 模块之间可以自由调用

缺点

• 错误容易扩散
• 开发和维护困难
• 可伸缩性差

实例

• UNIX：单体内核，对外提供一组系统调用，设备驱动与内核其他部分分开

• Linux：单体内核，支持动态可安装模块，模块可以在内核运行时编译或安装

层次结构

定义：功能模块按调用次序排成若干层，各层单向依赖或单向调用

分层原则

• 硬件相关——最底层：硬件相关的功能放在最底层
• 外部特性——最外层：与用户策略或用户交互相关的功能放在最顶层
• 中间层——调用次序或消息传递顺序：中间层各层按调用次序或消息传递顺序安排
• 共性服务和活跃功能——较低层：共性的和活跃的服务放在较低的层次

优点

• 结构清晰，避免循环调用
• 整体问题局部化，系统的正确性容易保证
• 有利于操作系统的维护、扩充、移植

微内核结构(客户/服务器结构)

客户：应用程序

服务器：操作系统

微内核：足够小，提供OS最基本的核心功能和服务

• 实现与硬件紧密相关的处理
• 实现一些较基本的功能
• 负责客户和服务器间的通信

核外服务器：完成OS的绝大部分功能，等待客户提出请求

• 由若干服务器或进程共同构成：例如线程/进程服务器，虚存服务器，设备管理服务器等，以进程形式运行在用户态

实例OS

Windows NT内核

• 微内核 + 分层结构
• 可扩展、可移植、可靠、安全的操作系统
• 支持对称多处理机
• 面对不同硬件，编译时采用不同组件
• 内核采用可扩展核子软件模型 ：仅实现基本功能

	实质	优点	缺点	代表
宏内核	将图形、设备驱动及文件系统等功能 全部在内核中实现，和内核运行在同一地址空间	减少进程间通信和状态切换的系统开销，获得较高的运行效率	内核庞大，占用资源较多且不易剪裁；系统的稳定性和安全性不好。	UNIX Linux
微内核	只实现OS基本功能，将图形、文件系统、设备驱动及通信功能放在内核之外。	内核精练，便于剪裁和移植；系统服务程序运行在用户地址空间，系统的稳定性和安 全性较高	用户状态和内核状态 需要频繁切换，从而导致系统效率不如单体内核。	Minix WinCE

2.2 处理机的态

操作系统基本硬件结构：CPU、内存、中断、时钟

操作系统安全问题

• 防止进程的信息被非法访问
• 防止进程随意存取系统资源
• 防止进程修改系统安全机制

解决方案

1. 软件被设置为可信软件与不可信软件两类
   • 保护机制能区分可信软件和不可信软件
     • 可信软件权限高：可以修改安全保护机制、可以存取系统资源
     • 不可信软件功能受限
   • CPU能区分当前软件的类型并设置不同的工作模式
2. 设置访问屏障
   • CPU根据当前工作模式，限定可使用的指令集
   • 设置可信软件和不可信软件之间的访问屏障

CPU

态：即CPU的工作状态。是对资源和指令使用权限的描述

• 核态：能够访问所有资源和执行所有指令(管理程序/OS内核)
• 用户态：仅能访问部分资源，其它资源受限(用户程序)
• 管态：介于核态和用户态之间

硬件要求

• 在处理器中包含有一个模式位，表明当前的权限状态。
• 指令执行前增加“权限状态是否满足”的条件判断。
• Intel CPU：PE位，PG位，地址映射机制，权限核验

特权指令

• 涉及外部设备的输入/输出指令：IN/OUT
• 修改特殊寄存器的指令: LGDT/LIDT/CLTS(装载特殊寄存器)
• 改变机器状态的指令：HALT(停止CPU工作)，STI/CTI(允许/禁止中断)

硬件和OS对CPU的观察

• 硬件按“态”来区分CPU的状态
• OS按“进程”来区分CPU的状态

		A	B	C	D
硬件→	核心态	K			K
硬件→	用户态		U	U

Interl CPU的态

• Ring0~Ring3(内→外)
• PL(Privilege Level) = 00, 01, 10, 11
• 段：一段连续内存
• 段描述符：描述段的属性，8字节
  • 段基址
  • 段界限
  • 段属性：段类型、访问该段所需最小特权级…

段描述符

字节7	字节6 字节5	字节4 字节3 字节2	字节1 字节0
段基址1	段属性+一部分段限长	段基址2	段限制长2

字节6字节5

7	6	5	4	3210	7	65	4	3210
G	D	0	AVL	段限长1	P	DPL	S	TYPE

程序段A访问程序段B时的权限检查（态）：JMP B, CALL B

当前特权级CPL：Current Privilege Level

请求特权级RPL：Requested Privilege Level

描述符特权级DPL：Descriptor Privilege Level

• 程序A CPL=0/1/2/3 RPL=0123
• 程序B DPL=0/1/2/3
• 合法访问
  • 一致代码段： CPL >= DPL
  • 非一致代码段 CPL = DPL && RPL <= DPL

	特权级(低→高)	特权级(高→低)	相同特权级
一致代码段	Y	N	Y
非一致代码段	N	N	Y
数据段	N	Y	Y

Unix/Linux OS：仅支持Ring0，Ring1和Ring3

• Ring0：特权指令，OS内核或驱动程序
• Ring1：管态
• Ring3：应用程序

Windows：仅支持Ring0和Ring3

• Ring0：特权指令，OS内核或驱动程序
• Ring3：应用程序

用户态向核态转换

• 用户请求OS提供服务
• 发生中断
• 用户进程产生错误（内部中断）
• 用户态企图执行特权指令

核态向用户态转换：一般是中断返回RET

内存

定义：存储程序和数据的部件

分类依据
按与CPU的联系	主存：直接和CPU交换信息	辅存：不能直接和CPU交换信息
按存储元的材料	半导体存储器：常作主存	磁存储器：磁带，磁盘	光存储器：光盘
按存储器读写工作方式	RAM	ROM

理想存储：速度快，容量大，成本低

实际存储：寄存器、高速缓存（CACHE）、主存、磁盘

工作

• 访问缓存(命中，HIT)
• 访问内存(没有命中，MISS)
• 访问辅存(缺页，PAGE_FAULT)

中断

定义：指CPU对突发的外部事件的反应过程或机制。CPU收到外部信号（中断信号）后，停止当前工作，转去处理该外部事件，处理完毕后回到原来工作的 中断处（断点）继续原来的工作

作用

• 实现并发活动

• 实现实时处理

• 故障自动处理

中断源：引起系统中断的事件称为中断源

中断类型

• 强迫中断和自愿中断
  • 强迫中断：程序没有预期：例：I/O、外部中断
  • 自愿中断：程序有预期。例：执行访管指令
• 外中断（中断）和内中断（俘获）
  • 外中断：由CPU外部事件引起。例：I/O，外部事情。
  • 内中断：由CPU内部事件引起。例：访管中断、程序中断
• 外中断：不可屏蔽中断和可屏蔽中断
  • 不可屏蔽中断：中断的原因很紧要，CPU必须响应
  • 可屏蔽中断：中断原因不很紧要，CPU可以不响应

断点：程序中断的地方，将要执行的下一指令的地址 CS:IP

现场：程序正确运行所依赖的信息集合。PSW（程序状态字）、PC、相关寄存器

进入中断服务程序：破坏主程序的现场

现场的两个处理过程

• 现场的保护：进入中断服务程序之前，栈
• 现场的恢复：退出中断服务程序之后，栈

中断响应过程

1. 识别中断源
2. 保护断点和现场
3. 装入中断服务程序CS:IP
4. 进入中断服务程序
5. 恢复现场和断点
6. 中断返回：IRET

栈

外部中断/INT指令：PUSH SS、PUSH SP、PUSHF、PUSH CS、PUSH IP

IRET：POP IP、POP CS 、POPF 、POP SP 、POP SS(通过IRET进入特定的代码段/任务)

堆栈不变无特权级变化，堆栈变表示有特权级变化

中断响应的实质

• 交换指令执行地址
• 交换CPU的态
• 工作：现场保护和恢复；参数传递（通信）

时钟

定义：以固定间隔产生时钟信号，提供计算机所需的节拍

作用：时间片；提供绝对时间；提供预定的时间间隔；WatchDog

类型：绝对时钟；相对时钟

---

第3章 用户界面

3.1 用户环境和构造

用户环境：用户工作的软件环境，（桌面环境、命令行环境）

用户环境构造：按照用户要求和硬件特性安装和配置操作系统（提供操作命令和界面，提供系统用户手册）

3.2 操作系统的生成

定义：根据硬件环境和用户需要，配置和构建操作系统。

前提

• 操作系统由可拆装模块构成
• 有交互式配置工具
• 有映像构建（build）工具

Linux操作系统的生成

1. 获取Linux内核的源代码（最好是当前版本）

   • http://www.kernel.org/
   • cd /usr/src
   • tar zxvf linux-2.6.38-12.tar.gz

2. 选择和启动内核配置程序

   • cd /usr/src/linux-2.6.38-12
   • make xconfig(图形窗口模式)
   • 或make menuconfig

3. 根据需要配置内核模块和参数

4. 重新编译新的内核

   • make dep
   • make clean
   • make bzImage ./arch/i386/boot/bzImage

5. 编译和安装模块

   • make modules
   • make modules_install 模块被编译且安装到/usr/lib/<内核版本号> 目录下

6. 启动新内核

   • cp bzImage /boot/bzImage

   • GRUB(与发行版本有关)：配置/boot/grub/grub.conf

     title newLinux build by Zhang San Feb.28.2019
     root (hd0,1)
     kernel /boot/bzImage ro root=/dev/hda2
     

   • LILO(早期版本)：配置/etc/lilo.conf后lilo使之生效

     image=/boot/bzImage
     label=newLinux build by Zhang San Feb.28, 2012
     

3.3 操作系统的启动

实模式和保护模式

实模式：实地址模式，REAL MODE

• 程序按照8086寻址方法访问0~FFFFFh（1MB）空间
• 寻址方式：物理地址（20位）= 段地址：偏移地址
• CPU单任务运行

实模式1M空间
前640K[0000-9FFF]	基本内存
中间128K[A000-BFFF]	显卡内存
末尾256K[C000-FFFF]	BIOS

保护模式：（内存保护模式，PROTECT MODE）

• 寻址方式：段（ 16位）和偏移量（ 32位），寻址4GB
  • 段的新含义和新工作机制
  • 段的属性：起始地址，存取属性，权限，…
  • 段页式虚拟内存管理机制(段，页）
  • 新增多个寄存器 GDR,LDR,CR0,CR1,CR2,…
• 虚拟地址，进程，封闭空间
• 应用程序和操作系统的运行环境都被保护
• CPU支持多任务

系统BIOS

定义：Basic I/O System，基本输入输出系统

BIOS256K空间
[C000-C7FF]	显卡BIOS
[C800-CBFF]	IDE控制器BIOS
[F000-FFFF]	系统BIOS

功能

• CMOS设置
• 基本IO设备中断服务
• POST上电自检
• 系统自举/加载OS

POST

定义：当用户按下PowerOn或者Reset键加电，开始执行FFFF0单元的指令(JUMP POST),开始自检

• 初始化基本硬件：CPU、显卡、内存…
• 自检正常不ix提示，错误则通过喇叭提示

系统自举/加载OS

定义：开机时将OS载入内存并运行为用户建立用户环境

• 查找显卡BIOS,调用显卡BIOS
• 依次查找其它设备执行相应设备的BIOS
• 显示启动画面：BIOS信息，主板信息，芯片组型号
• 根据用户指定顺序从硬盘或光驱等媒介启动OS
• OS启动后，由OS接管计算机

两种方式：现场引导方式(OS文件存储在本都存储设备)、逐步引导方式(滚雪球方式)

操作系统的启动(滚雪球)

定义：从加电到用户工作环境准备好的过程

1. 初始引导
2. 核心初始化
3. 系统初始化

初始引导

目的：把OS内核装入内存并使之开始工作接管计算机系统

过程

1. 加电自检，POST
2. 跳入BIOS的启动程序
   • 读取0面0道第1扇区的内容
   • MBR：主启动记录：引导程序所在
3. 运行引导程序
   • 根据参数，读取硬盘指定位置的OS内核到内存
   • 初始化基本参数
4. OS内核：逐步加载OS剩余部分，知道最后完全控制计算机

核心初始化

目的：OS内核初始化系统的核心数据

典型工作：

• 各种寄存器的初始化
• 存储系统和页表初始化
• 核心进程构建

系统初始化

目的：为用户使用系统作准备，使系统处于待命状态。

主要工作

• 初始化文件系统
• 初始化网络系统
• 初始化控制台
• 初始化图形界面

启动实例

DOS

构成

• io.sys: 提供DOS与BIOS的调用接口
• msdos.sys: 进程管理、存储管理、文件管理、解释系统调用
• command.com:Shell命令和键盘命令解释及执行

启动过程

• POST：加电后BIOS启动主机自检程序
• 初始引导
  • BIOS从MBR读入引导程序，装入内存的特定位置
  • 引导程序运行将io.sys及msdos.sys读入内存
  • DOS运行起来取代BIOS接管整个系统
• 核心初始化：操作系统读入config.sys配置系统核心
• 系统初始化：读入Command.com，执行autoexec.bat，系统待命

Windows

启动过程

• POST：加电后BIOS启动主机自检程序
• 初始引导
  • BIOS从MBR读入引导程序，装入内存的特定位置
  • 引导程序启动DOS7.0，调入操作系统核心
  • WINDOWS开始接管系统
• 核心初始化：资源状态、核心数据等初始化
• 系统初始化 GUI界面生成，系统处于待命/消息接受状态

Linux

启动过程

• POST
• MBR
• KERNEL映像
• KERNEL映像自解压并执行
• 内核初始化
• 内核启动

MBR

主启动扇区MBR：:BootLoader或更强功能的启动管理

• 提供菜单：可选择不同的启动项目
• 加载核心文件：直接指向可启动的程序区段加载OS操作系统
• 跳转其他Loader：跳转到其他PBR(分区引导记录)的boot loader加载OS

启动扇区：BootLoader，引导OS

MBR工作

1. 初启过程：POST→CMOS设置（/硬盘/软盘/USB）→读取MBR→控制权交给MBR
2. MBR工作
   • MBR读取分区表
     • 查找并确认唯一活动分区：确认其他的分区都不是活动分区
     • MBR读取活动分区PBR，并加载到内存
   • PBR控制后续引导过程：读OS内核

MBR的结构

MBR结构
446B[000-1BD]	boot loader
64B[1BE-1FD]	硬盘分区表
2B[1FE-1FF]	Magic number 55 AA

Boot Loader：三部分

• Boot code
• Error message
• Disk signature

操作系统的安装

安装过程

1. 把OS映像拷贝到存储空间：拷贝/安装位置：硬盘
2. 写启动相关的数据和代码（Boot Code）
   • MBR扇区（Master Boot Record Sector）
   • PBR扇区（Partition Boot Record）
   • 512字节

多操作系统安装：安装顺序；MBR重新或MBR追加

3.4 操作系统的用户界面

定义：OS提供给用户控制计算机的机制，又称用户接口

用户界面类型

1. 操作界面
2. 系统调用(程序界面)

操作界面

1. 图形用户界面(GUI)：窗口，图标，菜单，按钮，鼠标(消息，事件)
2. 键盘命令(CMD)：在控制台环境下接收键盘输入的命令(普通命令、批处理、shell)

shell

定义：shell时操作系统与用户交互的界面

特点：Shell表现为通过控制台执行用户命令的方式；Shell本身不执行命令，仅仅是组织和管理命令

分类：Bsh Csh Ksh(Bsh+Csh) Bash(Bsh升级+Ksh)

Bsh的主要功能

• 命令行编辑功能

• 命令和文件名补全功能：tab键

• 命令历史功能

• 命令别名功能

• 提供作业控制功能

• 具有将命令序列定义为功能键的功能

• 管道与重定向

  • 标志输入/输出

    输入/输出文件	设备	文件编号
    标准输入文件	键盘	0
    标准输出文件	显示器	1
    标准错误输出文件	显示器	2

  • 重定向

    • 输入重定向 < 将命令输入由默认的键盘更改/重定向为指定的文件
    • 输出重定向
      • > 将命令输出由默认的显示器更改/重定向为指定的文件
      • >> 将命令输出重定向并追加到指定文件的末尾
    • 错误重定向
      • 2> 将命令的错误输出重定向指定文件（先清空）
      • 2>> 将命令的错误输出重定向指定文件（追加到末尾）
    • 输出与错误组合重定向：&> 将命令的正常输出和错误输出重定向指定文件

  • 管道操作

    • |用于连接左右两个命令，将|左边命令的输出作为右边命令的输入

• Shell Script脚本编程

脚本

功能：脚本（Script）通过类似程序的方式执行具有一定逻辑顺序的命令序列完成较复杂的功能和人机交互

• 脚本程序保存在文本文件中
• 脚本程序是Shell命令语句的集合
• 所有命令逐行执行（按逻辑）
• 凡能shell中直接执行的命令，都可以在脚本中使用
• 脚本中还可以使用一些不能在shell下直接执行的语句

运行方法

1. 直接运行（用缺省版本的shell运行脚本程序）
2. 使用某个特定版本的Shell执行脚本 Bsh xx.sh
3. 在脚本文件首行指定Shell
   • 在脚本开头增加一行： #!/bin/bash
   • 可从/etc/shell获知所有可用shell及其绝对路径

3.5 系统调用

定义：操作系统内核为应用程序提供的一系列服务/函数

例如：printf、exit、fopen、fgetc、21H(09)

特点

• 一般涉及核心资源或硬件的操作 printf涉及显卡操作，fopen涉及文件磁盘
• 系统调用运行于核态
• 每个系统调用具有唯一的编号：ID
• 系统调用过程会产生中断：自愿中断
  • 访管指令是硬件指令，该指令引起OS内某个具有特定服务功能的内核代码执行（不是一段微指令）。
  • 访管指令执行时先设置模式位，再转入内核空间某个固定的位置（自陷中断处理）。然后由该位置代码负责转入相应的OS服务程序执行。执行完后返回用户空间。
  • 类似硬件中断，称为访管中断

系统调用的实现

• 调用N号系统调用，使用指令：SVC N
• N：系统调用的编号 SVC: SuperVisor Call，访管指令
• SVC是中断指令

DOS：INT 21H

Linux：INT 80H

执行过程

1. 设置模式位
2. 转入内核某固定位置（自陷中断处理）
3. 跳转到相应OS服务例程，执行
4. 返回用户空间

隐式系统调用

特点

• 类似API函数
• 在高级语言中使用（printf exit)
• 包含INT 80h中断指令/系统调用

3.5 Linux系统调用

实质

• 系统调用是Linux内核的出口
• 系统调用通过软中断(INT 80H)向内核发出服务请求
• 系统调用采用API方式向用户提供，遵循 POSIX标准

工作原理

1. 应用程序使用隐式方式调用系统调用xyz()
2. xyz()在Libc中编译为含有INT 0x80指令的代码
3. system_call时0x80号中断服务的一部分，指定各系统调用的入口。例如sys_xyz()
4. 具体实现各个系统调用。例如：sys_xyz()

系统调用封装在unistd.h中

---

第4章 进程管理

4.1 进程概念

定义：进程是程序在某个数据集合上的一次运行活动

数据集合：软/硬件环境，多个进程共存/共享的环境

进程特征：

• 动态性：进程是程序的一次执行过程，动态产生/消亡
• 并发性：进程可以同其他进程一起向前推进；
• 异步性：进程按各自速度向前推进
• 独立性：进程是系统分配资源和调度CPU的单位

	程序	进程
动静	程序是静态的：一组指令的有序集合	进程是动态的：程序的一次执行过程
持久	程序是长存的：在介质上长期保存	进程是暂存的：在内存驻留
对应	一个程序可能有多个进程	一个程序可能有多个进程

进程的类型

• 按使用资源的权限
  • 系统进程：指系统内核相关的进程
  • 用户进程：运行于用户态的进程
• 按对CPU的依赖性
  • 偏CPU进程：计算型进程
  • 偏I/O进程：侧重于I/O的进程

4.2 进程的状态

进制的状态

• 运行状态（Running）：进程已经占有CPU，在CPU上运行。
• 就绪状态（Ready）：具备运行条件但由于无CPU，暂时不能运行
• 阻塞状态（Block）【等待（Wait）】：因为等待某项服务完成或信号来到而不能运行的状态
  • 例如等待：系统调用，I/O操作，合作进程的服务或信号

进程状态的变化

变化	服务：系统调用/IO操作，信号：事件
就绪→运行	进程调度
运行→就绪	时间片到；被抢占
运行→阻塞	服务请求；等待信号
阻塞→就绪	服务完成；信号来到

具有新建(new)和终止(terminate)状态的进程状态

支持挂起(suspend)和解挂(resume)操作的进程状态

活动阻塞（正常阻塞）静止阻塞（阻塞时挂起）

活动就绪（正常就绪）静止就绪（就绪时挂起）

变化	服务：系统调用/IO操作，信号：事件
活动就绪→运行	进程调度
运行→活动就绪	时间片到；被抢占
运行→活动阻塞	服务请求；等待信号
活动阻塞→活动就绪	服务完成；信号来到
活动就绪→静止就绪	挂起
静止就绪→活动就绪	解挂
运行→静止就绪	挂起
静止阻塞→活动阻塞	解挂
活动阻塞→静止阻塞	挂起
静止阻塞→静止就绪	信号来到

Linux的进程状态

• 可运行态
  • 就绪：TASK_RUNNING，在就绪队列中等待调度
  • 运行：
• 睡眠态/阻塞态/等待态
  • 深度睡眠：TASK_UNINTERRUPTIBLE（不可中断）：不能被其他进程通过信号和时钟中断唤醒
  • 浅度睡眠：TASK_INTERRUPTIBLE（可中断）：可被其他进程的信号或时钟中断唤醒
• 僵死态：TASK_ZOMBIE，进程终止执行，释放大部分资源
• 挂起态：TASK_STOPPED，进程被挂起

ps aux查看STAT R=TASK_RUNNING S=TASK_UNINTERRUPTIBLE I=空闲 Z=TASK_ZOMBIE

4.3 进程控制块

定义：描述进程的状态、资源、和相关进程的关系的一种数据结构；PCB是进程的标志，随进程创建和撤销

进程=程序+PCB

Linux的进程控制块结构体 task_struct

Linux进程标识

• pid：进程ID，getpid()
• ppid：父进程ID，getppid()
• pgid：组进程ID
• uid：用户ID
• gid：用户组ID

进程的上下文切换

• Context，进程运行环境≈PCB
• 分时系统的进程切换
  • 进程的上下文在CPU中交换
  • 换入进程的上下文进入CPU（从栈+PCB上来）
  • 换出进程的上下文离开CPU（到栈+PCB上去）

进程A	OS	进程B
执行		空闲
执行→空闲	保存PCB(A)	空闲
空闲		空闲
空闲	加载PCB(B)	空闲→执行
空闲		执行
空闲		执行
空闲	保存PCB(B)	执行→空闲
空闲		空闲
空闲→执行	加载PCB(B)	空闲
执行		空闲

4.4 进程控制

定义：在进程生存全期间，对其全部行为的控制

四个典型的进程控制：创建进程；撤消进程；阻塞进程；唤醒进程

原语：由若干指令构成的具有特定功能的函数，具有原子性，其操作不可分割。

进程控制原语：创建原语；撤消原语；阻塞原语；唤醒原语

进程创建

功能：创建一个具有指定标识（ID）的进程

参数：进程标识、优先级、进程起始地址、CPU初始状态、资源清单等

过程

1. 创建一个空白PCB
2. 赋予进程标识符ID
3. 为进程分配空间
4. 初始化PCB：默认值
5. 插入相应的进程队列
6. 新进程插入就绪队列

进程撤销

功能：撤消一个指定的进程，收回进程所占有的资源，撤消该进程的PCB

参数：被撤消的进程名（ID）

时机：正常结束；异常结束；外界干预

过程

1. 在PCB队列中检索出该PCB
2. 获取该进程的状态
3. 若该进程处在运行态，立即终止该进程
   • 【递归】先“撤销”子进程
   • 子进程挂接到init进程下
4. 释放进程占有的资源
5. 将进程从PCB队列中移除

进程阻塞

功能：停止进程执行，变为阻塞

参数：阻塞原因（不同原因构建有不同的阻塞队列）

时机

• 请求系统服务：由于某种原因，OS不能立即满足进程的要求
• 启动某种操作：进程启动某操作，阻塞等待该操作完成
• 新数据尚未到达：A进程要获得B进程的中间结果，A进程等待
• 无新工作可作/idle进程/pause()：进程完成任务后，自我阻塞，等待新任务到达

过程

1. 停止运行
2. 将PCB “运行态”改“阻塞态”
3. 插入对应的阻塞队列
4. 转调度程序

进程唤醒

功能：唤醒处于阻塞队列当中的某个进程

参数：被唤醒进程的标识

时机

• 系统服务由不满足到满足
• I/O完成
• 新数据到达
• 进程提出新请求（服务）

4.5 Windows进程控制

进程创建

system(“c:\\test.exe”);

WinExec(“c:\\test.exe”, SW_SHOWMAXIMIZED);

ShellExecute(NULL, “open”, “c:\\test.exe”);

CreateProcess(NULL, “c:\\test.exe”, NULL, NULL, false, 0, NULL, NULL, NULL, &si, &pi)

CreateProcess = system + WinExec + ShellExecute

CreateProcess：创建新进程

• 创建进程内核对象，创建虚拟地址空间
• 装载EXE和/或DLL的代码和数据到地址空间中
• 创建主线程和线程内核对象
• 启动主线程，进入主函数（main）

进程撤销

void ExitProcess(UINT uExitCode);

void TerminateProcess(HANDLE hProcess, UINT uExitCode);

4.6 Linux进程控制

进程创建

fork

pid_t fork(void); 子进程中，pid = 0；父进程中，pid > 0

父进程和子进程

• 子进程：新建的进程
• 父进程：fork( )的调用者P
• 子进程是父进程的复制
• 父进程和子进程并发运行

fork函数执行流程

1. 分配task_struct结构
2. 为新进程堆栈分配物理页
3. 拷贝父进程的内容：正文段、用户数据段及系统数据段task_struct的大部分内 容，并对子进程中有别于父进程的项进行初始化
4. 把新进程的task_struct结构地址保存在task指针数组中
5. 子进程由fork()创建后，通常处于就绪状态

init进程

• 在Linux系统初启时，生成init进程(1号进程)
• 其他进程由当前进程通过系统调用fork( )建立

Unix

• fork：复制当前进程创建子进程
• exec：读取可执行文件并载入进程空间执行

Linux

• 父进程的资源被设置为只读，当父进程或子进程试 图修改某些内容时，内核才在修改前将该部分进行拷贝——写时复制
• fork的实际开销只是复制父进程的页表以及给子进程创建唯一的PCB

exec函数族

功能：装入一个指定的可执行程序运行，使子进程具有和父进程完全不同的新功能

流程

1. 根据文件名找到相应的可执行文件
2. 可执行文件的内容填入子进程的地址空间
3. exec调用成功就会进入新进程执行且不再返回
4. exec调用失败返回-1，继续在克隆来的地址空间中从调用点向下执行

进程撤销

exit：调用void exit(int status)终结进程，进程终结时要释放资源并向父进程报告

• 利用status向父进程报告结束时的退出代码
• 变为僵尸状态，保留部分PCB信息供wait收集
  • 正常结束还是异常结束
  • 占用总系统cpu时间
  • 缺页中断次数
• 调用schedule()函数，选择新进程运行

进程阻塞

wait：进程调用wait(int &status)阻塞自己

• 检测有无子进程结束
  • 没有：等待子进程结束：继续阻塞
  • 有：wait收集该子进程信息并彻底销毁它后返回
• Status接收子进程退出时的退出代码
  • status：按位处理
  • 若忽略子进程的退出信心：pid = wait(NULL)

sleep:Sleep(int nSecond),进程暂停执行nSecond秒

• 系统暂停调度该进程
• 相当于windows挂起操作resume( )，挂起指定秒

4.7 线程

定义：线程是进程内的一个执行路径

特点

• 一个进程可以创建和包含多个线程
• 线程之间共享CPU可以实现并发运行
• 创建线程比创建进程开销要小
• 线程间通信十分方便

线程的应用如果把程序中某些函数创建为线程，那么这些函数将可以并发运行

进程=资源集+线程组

线程技术典型适用场景

• 多个功能需要并发的地方
• 需要改善窗口交互性的地方
• 需要改善程序结构的地方
• 多核CPU上的应用，充分发挥多核性能

4.8 进程相互制约关系

进程的互斥关系：多个进程由于共享具有独占性的资源，必须协调各进程对资源的存取顺序：确保没有任何两个或以上的进程同时进行资源存取

临界资源：一次只允许一个进程独占访问（使用）的资源，是资源。临界资源的访问具有排他性

临界区：进程中访问临界资源的程序段，是程序。并发进程不能同时进入“临界区”

临界区四个访问原则

1. 忙则等待 当临界区忙时，其他进程必须在临界区外等待
2. 空闲让进 当无进程处于临界区时，任何有权进程可进入临界区
3. 有限等待 进程进入临界区的请求应在有限时间内得到满足
4. 让权等待 等待进程放弃CPU。（让其它进程有机会得到CPU）

访问临界区方法

• 硬件：中断屏蔽；测试并设置；交换指令
• 软件：锁；信号量

进程的同步关系：若干合作进程为了共同完成一个任务，需要相互协调运行步伐：一个进程A开始某个操作之前要求另一个进程B必须已经完成另一个操作，否则进程A只能等待。

另一种解释：合作进程中某些操作之间需要满足某种先后关系或某个操作能否进行需要某个前提条件满足，否则只能等待

4.9 进程同步

锁机制

基本原理

• 设置一个“标志”S，表明临界资源“可用”还是“不可用”
• 在进入临界区之前检查标志是否“可用”
  • 若为“不可用”状态：进程在临界区之外等待
  • 若为“可用”状态
    • 进入临界区,并将标志修改为“不可用”（Lock）
    • 在临界区内访问临界资源
    • 退出临界区,并将标志修改为“可用”状态（UnLock）

锁机制未满足让权等待

信号灯与PV操作

信号灯定义为二元矢量(S,q)

S：整数，初值非负（S又称信号量）

q：队列(进程PCB集合)，初值为空集

P操作：申请资源，当前资源不足则阻塞排队，排队的进程数为-S

P(S, q) {
    S--;
    if (S < 0) {
        Insert(Caller, q);
        Block(Caller);
        转调度函数();
    }
}

V操作：释放资源，意味着肯定有资源出现，S<=0意味着有+1之前有进程在排队，选一个运行

V(S, q) {
    S++;
    if (S <= 0) {
        Remove(q, PID);
        Wakeup(PID);
    }
}

P-V操作的应用

• 实现进程互斥
  • 实质是实现对临界区的互斥访问
    • 1个临界资源：允许最多1个进程处于临界区
    • M个临界资源：允许最多M个进程同时处于临界区
  • 应用过程
    • 进入临界区之前先执行P操作(申请资源)
    • 离开临界区之后再执行V操作(释放资源)
    • S的初值设置要合理。
• 实现进程同步
  • 同步机制实质
    • 运行条件不满足时，能让进程暂停
    • 运行条件满足时，能让进程立即继续
  • 应用过程
    • 暂停当前进程：在关键操作之前执行P操作，必要时可以暂停
    • 继续进程：在关键操作之后执行V操作
    • 定义有意义的信号量S，并设置合适的初值，不合理的S会发生死锁

司机与售票员例子

S1 = 0 门是否关好 S2 = 0 车是否停稳

司机	售票员
	关门
	V(S1)
P(S1)
起步;
行驶;	售票
停车;
V(S2);
	P(S2)
	开门

生产者消费者问题

一群生产者通过缓冲区向一群消费者提供产品，共享缓存区

互斥关系 int mutex = 1

• 生产者与消费者不能同时访问
• 生产者与生产者不能同时访问
• 消费者与消费者不能同时访问

同步关系

• 放入缓冲区时缓冲区未满 int Data = 0
• 拿出缓存区时缓冲区未空 int Space = 5

producer() {
    while(1) {
        生产1个数据;
        P(Space);
        P(mutex);
        存1个数据到缓冲区;
        V(mutex);
        V(Data);
    }
}

consumer() {
    while(1) {
        P(Data);
        P(mutex);
        取1个数据到缓冲区;
        V(mutex);
        V(Space);
        消费一个数据;
    }
}

读者写者问题

有读者读书；有多个读者；有编者编书；有多个编者

互斥关系int w_mutex = 1

• 读者与写者不能同时拿书
• 写者与写者不能同时拿书
• 读者与读者不互斥，但要保证原子性 int cnt = 1, r_mutex = 1

读者优先：当存在读操作时，编操作有可能将被无限延迟

Readder() {
    while(1) {    
        P(r_mutex);	// 保证修改cnt的操作原子性
        if (++cnt == 1) P(w_mutex);
        V(r_mutex); // 保证修改cnt的操作原子性
        	读书;
        P(r_mutex);
        if (--cnt == 0) V(w_mutex);
        V(r_mutex)
    }
}

Editor() {
    while (1) {
        P(w_mutex);
        编书;
        V(w_mutex);
    }
}

写者优先：当有读操作时，如果有编者请求访问，这时应禁止后续的读操作请求应让当前读操作执行完毕后立即让编者进程执行。 只有在无编者操作的情况下才允许读进程再次运行

同步关系：如果串行顺序是 R1 W1 R2的话，不能让W1被R2挤占 int editor_first = 1

Reader() {
    while(1) {
        P(editor_first); // 保证读写公平
        P(r_mutex);	// 保证修改cnt的操作原子性
        if (++cnt == 1) P(w_mutex);
        V(r_mutex); // 保证修改cnt的操作原子性
        V(editor_first); // 保证读写公平
        	读书;
        P(r_mutex);
        if (--cnt == 0) V(w_mutex);
        V(r_mutex)
    }
}

Editor() {
    while (1) {
        P(editor_first); // 保证读写公平
        P(w_mutex);
        编书;
        V(w_mutex);
        V(editor_first); // 保证读写公平
    }
}

4.10 Windows同步机制与应用

---

第5章 资源分配与调度

5.1 死锁

定义：两个或多个进程无限期地等待永远不会发生的条件的一种系统状态（每个进程都永远阻塞）

另一个定义：在两个或多个进程中，每个进程都已持有某种资源，但又继续申请其它进程已持有的某种资源。此时每个进程都拥有其运行所需的一部分资源，但是又都 4不够，从而每个进程都不能向前推进，陷于阻塞状态。这种状态称死锁。

原因：

1. 系统资源有限：资源数目不足以满足所有进程的需要，引起进程对资源的竞争而产生死锁。
2. 并发进程的推进顺序不当：进程在运行过程中，请求和释放资源的顺序不当，导致进程产生死锁

例子：假如顺序不当，如果Space=0，生产者获得了mutex权利但不能放数据，等待消费者消费；但消费者无法获得mutex所以无法消费。结果死锁

producer() {
    while(1) {
        生产1个数据;
        p(mutex); // P(Space);
        p(Space); // P(xmutex);
        存1个数据到缓冲区;
        V(mutex);
        V(Data);
    }
}

consumer() {
    while(1) {
        P(Data);
        P(mutex);
        取1个数据到缓冲区;
        V(mutex);
        V(Space);
        消费一个数据;
    }
}

死锁结论

• 陷入死锁的进程至少是2个
• 参与死锁的进程至少有2个已经占有资源
• 参与死锁的所有进程都在等待资源
• 参与死锁的进程是当前系统中所有进程的子集
• 死锁会浪费大量系统资源，甚至导致系统崩溃

死锁的必要条件

1. 互斥条件：资源具有独占性，进程互斥使用资源。
2. 不剥夺条件：进程在释放资源前（即访问完）不能被其他进程剥夺。
3. 部分分配条件：进程所需资源逐步分配，需要时申请和分配。占有一些资源，同时申请新资源。
4. 环路条件：多个进程构成环路，环中每个进程已占用的资源被前一进程申请，而自己所需新资源又被环中后一进程所占用

5.2 解决死锁

预防死锁

定义：通过设置某些限制条件，破坏死锁四个必要条件中的一个或多个，来防止死锁

操作：

1. 破坏互斥条件：难
2. 破坏不剥夺条件：代价大
3. 破坏部分分配条件：预先静态分配
   • 全部分配法：进程运行前将所需全部资源一次性分配给它。因此进程在运行过程中不再提出资源请求， 从而避免出现阻塞或者死锁
   • 特点
     • 进程仅当其所需全部资源可用时才开始运行
     • 应用设计和执行开销增大：进程运行前估算资源需求
     • 执行可能被延迟：进程所需资源不能全部满足时
     • 资源利用率低：资源被占而不用
   • 改进：资源分配的单位由进程改为程序步
4. 破坏环路条件：有序资源分配
   • 执行方法：系统中的每个资源分配有一个唯一序号，进程每次申请资源时只能申请序号更大的资源，如果进程已占有资源的序号最大为M，则下次只能申请序号大于M的资源，而不能再申请序号小于或等于M的资源
   • 资源分配策略
     • 若不符合则拒绝该申请，并撤销该进程
     • 若符合且资源可用则予以分配
     • 若符合但资源不可用则不分配，陷于阻塞

特点：(早期)广泛使用。

缺点：由于限制太严格，导致资源利用率和吞吐 量降低

避免死锁

定义：在资源的分配过程中，用某种方法分析该次分配是否可能导致死锁？若会则不分配；若不会就分配

银行家算法：只需要较弱的限制条件，可获得较高的资源利用率 和系统吞吐量。缺点：实现较难

检测死锁和恢复死锁

定义：允许死锁发生，但可通过检测机制及时检测出死锁状态，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除，将进程从死锁状态解脱出来

检测方法：复杂

恢复方法：撤消或挂起一些进程，以回收一些资源

缺点：难

Windows，Linux：死锁解决

鸵鸟策略：视而不见，交给用户

---

第6章 进程调度

6.1 进程调度概念

调度定义：在一个队列中，按某种策略选择一个最合适个体

调度分类

• 长程调度/宏观调度/作业调度
• 中程调度/交换调度
• 短程调度/进程调度
• I/O调度/设备调度

进程调度定义：在合适的时候以一定策略选择一个就绪进程运行

进程调度的目标：部分原则之间存在自相矛盾

1. 响应速度尽可能快
2. 进程处理的时间尽可能短
3. 系统吞吐量尽可能大
4. 资源利用率尽可能高
5. 对所有进程要公平
6. 避免饥饿
7. 避免死锁

1和2：交互程序和后台程序的矛盾

1和3：响应速度快CPU频繁切换；系统吞吐量大CPU有效工作时间长

2和5：处理时间尽快则特定进程优先；但是部分进程会饥饿

量化进程调度指标

	周转时间t	平均周转时间	带权周转时间w	平均带权周转时间
定义	进程提交给计算机到完成所花费的时间
计算	t=tc-ts=进程完成时间-进程提交时间	t=Σti/n	w=t/tr=t/进程运行时间	w=Σwi/n
意义	说明进程在系统中停留时间的长短	平均周转时间越短，意味着这些进程在系统内停留的时间越短，因而系统吞吐量也就越大，资源利用率也越高	进程在系统中的相对停留时间

6.2 进程调度算法

先来先服务调度

算法：按照作业进入系统的时间先后次序来挑选作业。先进入系统的作业优先被运行

特点

• 容易实现，效率不高
• 只考虑作业的等候时间，而没考虑运行时间的长短。因此一个晚来但是很短的作业可能需要等待很长时间才能被运行，因而本算法不利于短作业

短作业优先调度算法

算法：参考运行时间，选取时间最短的作业投入运行

特点

• 易于实现，效率不高
• 忽视了作业等待时间，一个早来但是很长的作业将会在很长时间得不到调度，易出现资源“饥饿”的现象

响应比高者优先调度算法

响应比：作业的响应时间和与运行时间的比值

响应比=响应时间/运行时间=(等待时间 + 运行时间)/运行时间= 1 + 等待时间/运行时间 = 加权周转时间w

算法：调度作业时计算作业列表中每个作业的响应比，选择响应比最高的作业优先投入运行

特点

• 响应比 = 1 + 等待时间 / 运行时间
• 有利于短作业
• 有利于等候已久的作业
• 兼顾长作业

优先数调度算法

算法：根据进程优先数，把CPU分配给最高的进程。进程优先数 = 静态优先数 +动态优先数

静态优先数：进程创建时确定，在整个进程运行期间不再改变

• 基于进程所需的资源多少
• 基于程序运行时间的长短
• 基于进程的类型[IO/CPU,前台/后台,核心/用户]

动态优先数：动态优先数在进程运行期间可以改变

• 当使用CPU超过一定时长时
• 当进程等待时间超过一定时长时
• 当进行I/O操作后

循环轮转调度法

算法

• 把所有就绪进程按先进先出的原则排成队列。新来进程加到队列末尾。
• 进程以时间片q为单位轮流使用CPU刚刚运行了一个时间片的进程排到队列末尾，等候下一轮调度；
• 队列逻辑上是环形的

优点

• 公平性：每个就绪进程有平等机会获得CPU
• 交互性：每个进程等待(N-1)*q的时间就可以重新获得CPU

时间片大小

• 如果q太大：交互性差，甚至退化为FCFS调度算法
• 如果q太小：进程切换频繁，系统开销增加

改进

1. 时间片的大小可变(可变时间片轮转调度法)
2. 组织多个就绪队列（多重时间片循环轮转）

调度方式

定义：当一进程正在CPU上运行时，若有更高优先级的进程需要运行，系统分配CPU的方法

非剥夺方式：让正在运行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把 CPU分配给新来的更高优先级的进程。

剥夺方式：当更高优先级的进程来到时，便暂停正在运行的进程，立即把CPU分配给新来的优先级更高的进程。

6.3 Linux进程调度算法

特点

• 基于优先级调度
• 支持普通进程，也支持实时进程
• 实时进程优先于普通进程
• 普通进程公平使用CPU时间

---

第7章 主存管理

7.1 存储管理的功能

存储器功能需求：容量大、速度快、信息永久保存、多道程序并行

实际存储器体系：三级存储体系：CPU→Cache(快、小、贵)→内存(适中)→辅存(慢、大、廉)

基本原理：当内存太小不够用时，用辅存来支援内存；暂时不运行的模块换出到辅存上，必要时再换入内存。

多道程序并行的问题

1. 共享：代码和数据共享，节省内存
2. 保护：不允许内存中的程序相互间非法访问

存储管理的功能

1. 地址映射
2. 虚拟存储
3. 内存分配
4. 存储保护

地址映射

定义：也叫地址重定位、地址重映射。把程序中的地址变换成真实的内存地址的过程。（虚拟地址/虚地址/逻辑地址）→（实地址/物理地址）

虚拟地址/源程序包括：地址，变量，标号，函数名

方式：固定地址映射、静态地址映射、动态地址映射

固定地址映射

定义：编程或编译时确定逻辑地址和物理地址映射关系

特点

• 程序加载时必须放在指定的内存区域
• 容易产生地址冲突，运行失败
• 不能适应多道环境

静态地址映射

定义：程序装入时由操作系统完成逻辑地址到物理地址的映射。保证在运行之前所有地址都绑定到主存

逻辑地址：VA(Virtual Addr.)

装入基址：BA(Base Addr.)

物理地址：MA(Memory Addr.)

MA = BA + VA

特点

• 程序运行之前确定映射关系：不能边运行边映射
• 程序装入后不能移动：如果移动必须放回原来位置
• 程序占用连续的内存空间

动态地址映射

定义：在程序执行过程中把逻辑地址转换为物理地址，例如 MOV AX,[500]; 访问500单元时执行地址转换

基址寄存器：BAR(重定位寄存器)，运行现场的数据

MA = BA([BAR]) + VA

实现方案：进程进入主存时根据进程的现场设置BAR，引用具体命令时，用BAR重定位。

• 要通过硬件实现：
  • CPU引用指令中主存地址时先进行重定位，再将重定位以后的地址值作为主存的引用地址。
• 重定位寄存器：
  • 进程装入主存时不做任何修改
  • 重定位寄存器作为进程运行现场的一部分：进程换入进入运行态时，重定位寄存器要恢复

连续的进程空间用几个不连续的物理块存放的方法

• 按段编译，虚拟地址格式：段+段内位移
• 不同段放入不同的物理块
• 每个段维护一个段寄存器（/重定位寄存器）即可：段式存储分配技术

特点

• 程序占用的内存空间可动态变化：若程序移动及时更新基址BA
• 程序不要求占用连续的内存空间：需要记录每段放置的基址BA
• 便于多个进程共享代码：共享代码作为独立的一段存放

缺点：需要MMU(内存管理单元)支持，软件复杂

虚拟存储

问题

1. 程序过大或过多时，内存不够，不能运行
2. 多个程序并发时地址冲突，不能运行

虚拟存储的基本原理(问题1的解决)

• 借助辅存在逻辑上扩充内存，解决内存不足
• 过程：迁入和迁出
  • 迁入：将要运行的部分装入内存（迁入）
  • 迁出：把当前不运行的部分暂时存放在辅存
• 前提：短时间内进程不运行的部分往往占大部分（程序局部性）

程序局部性原理

• 时间局部性：一条指令或数据，会在较短时间内被重复访问：循环语句
• 空间局部性：短时间内，任一内存单元及其邻近单元会在短时间内被集中访问：表、数组
• 结论：程序在一个有限的时间段内访问的代码和数据往往集中在有限的地址范围内。因此，一般情况下，把程序的一部分装入内存在较大概率上也足够让其运行一小段时间

虚拟存储前提：足够的辅存；适量的内存；地址变换机构

虚拟存储的应用：页式虚拟存储，段式虚拟

内存分配

定义：为程序运行分配足够的内存空间

问题

• 放置策略
  • 程序调入内存时将其放置在哪个/哪些内存区？
  • 全部分配或部分分配（即按需分配/存储扩充）？
• 调入策略：何时把要运行的代码和要访问的数据调入内存？
• 淘汰策略：迁出（/淘汰）哪些代码或数据以腾出内存空间？

存储保护功能

定义：保证在内存中的多道程序只能在给定的存储区域内活动并互不干扰

防止访问越界、防止访问越权

方法

• 界址寄存器：适于连续物理分区中的情形
  • 在CPU中设置一对下限寄存器和上限寄存器存放程序在内存中的下限地址和上限地址
  • 程序访问内存时硬件自动将目的地址与下限寄存器和上限寄存器中存放的地址界限比较，判断是否越界
  • 基址寄存器和限长寄存器
• 存储键保护 适于不连续物理分块的情形，也可用于共享中的权限。

7.2 物理内存管理

方法:单一区存储管理（不分区存储管理）；分区存储管理；内存覆盖技术；内存交换技术

单一内存管理

定义：用户区不分区，完全被一个程序占用(DOS)

优点：简单，不需复杂硬件支持，适于单用户单任务OS

缺点：程序运行占用整个内存，内存浪费，利用率低

分区存储管理

定义：把用户区内存划分为若干大小不等的分区，供不同程序使用；最简单的存储管理,适合单用户单任务系统。

分类：固定分区；动态分区

固定分区

定义：把内存固定地划分为若干个大小不等的分区供各个程序使用。每个分区的大小和位置都固定，系统运行期间不再重新划分

分区表：记录分区的位置、大小和使用标志

区号	大小	起址	占用标志
1	16K	20K	0/1
2	32K	36K	0/1
3	64K	68K	0/1
4	124K	132K	0/1

特点

• 在程序装入前，内存已被分区，不再改变。
• 每个分区大小不同，适应不同大小的程序。
• 系统要维护分区表

缺点

• 浪费内存：程序比所在分区小
• 大程序可能无法运行：程序比最大分区大，无法装入

应用建议：程序大小、个数、装入顺序等都固定时的情景；根据分区表安排程序装入顺序

动态分区

定义：在程序装入时创建分区，使分区的大小刚好与程序的大小相等

特点：分区动态建立；分区的个数和大小均可变；存在内存碎片

分区的选择(放置策略)

• 空闲区表：描述内存空闲区的位置和大小的数据结构
• 分区选择：从空闲区表中选择一个空闲分区给用户使用

	首次适应算法	最佳适应算法	最坏适应算法
空闲区表排序	空闲区首址递增排序	空闲区大小递增排序	空闲区大小递减排序
目的	尽可能先利用低地址空间	尽量选中满足要求的最小空闲区(最容易产内存碎片)	尽量使用最大的空闲区，一次查找

分区的分配

功能：从用户选中的分区中分配/分割所需大小给用户（从低地址开始）；剩余部分作为空闲区登记在空闲区表

分区的回收

功能：回收程序占用的分区，将其适当处理后登记到空闲区表中；若释放区与现有空闲区相邻则合并

内存拼接

1. 规定门限值：分割空闲区时，若剩余部分小于门限值，则此空闲区不进行分割，而是全部分配给用户。
2. 内存拼接技术：将所有空闲区集中一起构成一个大的空闲区
   • 内存拼接的时机
     • 释放区回收的时候：拼接频率过大，系统开销大
     • 系统找不到足够大的空闲区时：空闲区的管理复杂
     • 定期：空闲区的管理复杂
   • 缺点：消耗系统资源；离线拼接；重新定义作业
3. 程序拆分：解除程序占用连续内存的限制，把程序分拆几个部分装入不同分区，充分利用碎片

覆盖Overlay

定义：在较小的内存空间中运行较大的程序，将内存分为常驻区和覆盖区

常驻区：被某段单独且固定地占用的区域，核心段

覆盖区：能被多段共用（覆盖）的区域，可划分多个

工作原理

• 程序分为若干代码段或数据段
• 将程序常用的段装入常驻区
• 不常用的段装入覆盖区
  • 正运行的段处于覆盖区
  • 暂时不运行的段放在硬盘中(覆盖文件)；
  • 即将运行的段装入覆盖区(覆盖旧内容)

意义：减少程序对内存需求

例子

对对换Swapping

原理：内存不够时把进程写到磁盘；当进程要运行时重新写回内存

优点：增加进程并发数；不考虑程序结构

缺点：换入和换出增加CPU开销；对换单位太大（整个进程）

对换问题：程序换入时的地址重定位；减少对换传送的信息量；外存对换空间的管理方法

OS：UNIX、Linux、Windows都采用了Swapping

总结

特点	缺点
源程序直接使用内存物理地址	程序间容易访问冲突
程序必须全部装入内存才能运行	内存太小程序无法运行
程序占用连续的一片内存	产生内存碎片
多程序同时运行容易相互干扰	不安全

因此需要虚拟内存技术

7.3 虚拟内存管理

定义：虚拟内存是面向用户的虚拟封闭存储空间

• 线性地址空间
• 4G=2³²Byte
• 封闭空间(进程空间)
• 和物理地址分类(地址无冲突)
• 程序员编程时使用线性虚拟地址

目标：

• 使得大的程序能在较小的内存中运行
• 使得多个程序能在较小的内存中运行（能容纳下）
• 使得多个程序并发运行时地址不冲突（方便，高效）
• 使得内存利用效率高：无碎片,共享方便

实现思路

• 把程序一部分装入内存在较大概率上也足够让其运行一小段时间
• 程序运行的局部性：程序在一个有限的时间段内访问的代码和数据往 往集中在有限的地址范围内
• 代码分段；逐段装入；逐段运行；逐段迁出；宏观/微观；时间换空间

典型虚拟内存管理方式：页式、段式、段页式

页式虚拟存储管理

定义：把进程空间（虚拟）和内存空间都划分成等大小的小片（4K，2K，1K）

页：进程的小片

页框：内存的小片

页面大小的选择

• 1KB，2KB，4KB
• 太大：浪费内存
• 太小：页面增多，页表长度增加，浪费内存；换页频繁，系统效率低

进程装入和使用内存的原则

• 内存以页框为单位分配使用
• 进程以页为单位装入内存
  • 只把程序部分页装入内存便可运行
  • 页在内存中占用的页框不必相邻
  • 需要新页时，按需从硬盘调入内存
  • 不再运行的页及时删除，腾出空间

页式地址映射

虚拟地址的种类：页式地址

虚拟地址VA

• 页号P = VA/页大小
• 页内偏移W = VA%页大小

页面映射表：记录页与页框(也称块)之间的对应关系。也叫页表

页号	页框号	页面其他特性
0	5	含存取权限在内的其他特性：读、写、执行
1	65	是否被访问过？
2	13	是否被修改过？

页表的建立

• 操作系统为每个进程建立一个页表：页表长度和首址存放在进程控制块中
• 当前运行进程的页表驻留在内存：页表长度和首址由页表长度寄存器和页表首址寄存器指示

页表的扩充

中断位I：标识该页是否在内存：若I=１，不在内存；若I =０，在内存

辅存地址：该页在辅存上的位置

页号	页框号	中断位I	辅存地址
		1
		0

访问位：标识该页最近是否被访问：０，最近没有被访问 １，最近已被访问

修改位：标识该页的数据是否已被修改：０，该页未被修改 １，该页已被修改

页号	页框号	访问位	修改位
		1	0
		0	1

页式地址映射

1. 从VA分离页号P和页内偏移W
2. 查页表：以P为索引查页框号P’
3. 计算物理地址MA=P’×页大小+W；CPU=P’<

防止越界访问页面

防止越界访问其他进程：检查访问的目的页号X是否在进程内

检查标准：0 <= X < 虚拟页数

越界则产生越界中断

快表机制(Cache)

定义：快表是普通页表（慢表）的部分内容的复制

工作机制：地址映射时优先访问快表，合理的页面调度策略能使快表具有较高命中率

• 若在快表中找到所需数据，则称为“命中”
• 没有命中时，需要访问慢表，同时更新快表

页共享

在页表中填上共享的页框号，从而实现页面共享，共享页面在内存只有一份真实存储

例子如文本编辑器：150KB代码段和50KB数据段，有10进程并发执行该文本编辑器

• 占用内存=10×(150＋50)KB＝2M
• 如果采用代码段共享，代码段在内存只有一份真实存储占用内存=150+10×50=650KB

缺页中断

定义：在地址映射过程中，当所要访问的目的页不在内存时，则系统产生异常中断

缺页中断处理程序：中断处理程序把所缺的页从页表指出的辅存地址调 入内存的某个页框中，并更新页表中该页对应的页框号以及修改中断位I为0

缺页率 f = 缺页次数 / 访问次数

影响缺页次数的因素

• 淘汰算法
• 分配给进程的页框数：分配的越少，越容易缺页
• 页本身的大小：页面越小，越容易缺页
• 程序本身
  • 局部性越好，越不容易缺页
  • 跳转或分支越多越容易缺页

缺页中断与普通中断

• 相同：处理过程：保护现场、中断处理、恢复现场
• 不同
  • 响应时机：普通中断在指令完成后响应；缺页中断在指令执行过程中发生
  • 发送频率：一条指令执行时可能产生多个缺页中断

淘汰策略

页面抖动：页面在内存和辅存间频繁交换的现象；“抖动”会导致系统效率下降

好的淘汰策略：具有较低的缺页率（高命中率）；页面抖动较少

LRU的实现

• 硬件
  • 页面设置一个移位寄存器R。页面被访问则重置为1；
  • 周期性地(周期很短)将所有页面的R左移1位（右边补0）
  • 当需要淘汰页面时选择R值最大的页
  • R的位数越多且移位周期越小就越精确，但硬件成本也越高
  • R的位数太少，可能出现多个为0页面的情况，难以比较
• 近似
  • 利用页表访问位，页被访问时其值由硬件置1
  • 软件周期性（T）地将所有访问位置0
  • 当淘汰页面时根据该页访问位来判断是否淘汰
    • 访问位为1：在时间T内，该页被访问过，保留该页
    • 访问位为0：在时间T内，该页未被访问过，淘汰该页
  • 缺点周期T难定：访问位为0的页过多或访问位为1的页过多，找不到合适的页淘汰。

LFU的实现

• 每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1
• 发生缺页中断时，淘汰计数值最小的页面，并将所 有计数清零

	最佳算法OPT	先进先出FIFO	最久未使用LRU	最不经常使用LFU
思想	淘汰不再需要或最远将来才会用到的页面	淘汰在内存中停留时间最长的页面	淘汰最长时间未被使用的页面	淘汰内存中使用次数最少的
特点	理论上最佳，实践中该算法无法实现
优点		实现简单：页面按进入内存的时间排序，淘汰队头页面
缺点		进程只有按顺序访问地址空间时页面命中率才最理想
异常		对于一些特定的访问序列，分配页框越多，缺页率越高

二级页表

页表存在的问题

• 32位OS(4G空间)，每页4K，页表每个记录占4字节
  • 页表所占内存： 4G/4K * 4Byte = 4M
  • 页表所占页框： 4M/4K = 1K(连续)
• 问题1：页表全部装入过度消耗内存
• 问题2：难以找到连续1K个页框存放页表

解决

• 仅将页表的部分内容调入内存
• 将4M的超大页表分拆存储到离散的1K个页框中（内存中即存页表的信息，也存程序的信息）
• 为了对小页表进行管理和查找，另设置一个叫页目录的表，记录每个小页表的存放位置（即页框号）
  • 页目录实际是一个特殊页表：每个记录存放的是小页表的编号和其所在的页框号之间的对应关系
• 页目录：一级页表，小页表：二级页表

页目录	二级页表10位	页框10位
12位	10位	10位

不足

页面划分无逻辑含义；页的共享不灵活；页内碎片

段式虚拟存储管理

进程分段：把进程按逻辑意义划分为多个段，长度不定。进程由多段组成(代码段、数据段、堆栈段)

段式内存管理系统的内存分配：以段为单位装入，每段分配连续的内存；段和段之间不要求相邻

段式地址映射

虚拟地址的种类：段式地址

虚拟地址VA：包含段号S和段内位移W，没有固定长度

段表：记录每段在内存中映射的位置

段号	段长	段基地址
S	L(W<=L)	B

段地址映射

1. 从VA分离段号S和段内偏移W
2. 查段表：以S为索引查询该段的基地址B和长度L
3. 计算物理地址MA=B+W

段表的扩充

段号	段长	段基地址	中断位	访问位	修改位	R	W	X
S	L(W<=L)	B

页共享

• 共享段在内存中只有一份存储
• 共享段被进程映射到自己的空间（写入段表）
• 需要共享的模块都可以设置为单独的段

不足

段需要连续的存储空间；段的最大尺寸受到内存大小的限制；在辅存中管理可变尺寸的段比较困难

页式VS段式

	页式	段式
地址	一维地址空间	二维地址空间
长度	大小固定	可变
划分意义	无	有
共享方向性	相对不方便	相对方便
用户可见性	不可见	可见
偏移	无溢出	有溢出

段页式虚拟存储管理

定义：在段式存储管理中结合页式存储管理技术；在段中划分页，内存按页划分，按页装入；

段页式地址映射

虚拟地址的种类：段页式地址

虚拟地址VA：包含段号S、页号P、页内偏移W

同时采用段表和页表实现地址映射

• 系统为每个进程建立一个段表
• 系统为每个段建立一个页表
• 段表给出每段的页表基地址及页表长度（段长）
• 页表给出每页对应的页框

段页地址映射

1. 从VA分离段号S、页号P、页内偏移W
2. 查段表：以S为索引查询页表的基地址B和页表长度L
3. 查页表：以P为索引查询页框号P’
4. 计算物理地址MA=P’+W

7.4 Linux内存文件系统/proc

特点：内存文件系统；为用户访问内核信息提供接口(CPU,内核信息)

/proc下重要文件与子目录

• /proc/pid 关于某个进程（PID=数字）的信息目录。
  • /proc/pid/pagemap允许用户查看虚拟页映射的物理页
    • 记录式文件，64位一条
    • 0~54为页框号
    • 55~60页偏移
    • 61reserved for future use
    • 62page swapped
    • 63page present
    • 根据VA算出P和W，从文件开头+P*64bit找到相应记录，分析后55位即找到页框号
• /proc/cpuinfo 处理器信息，如类型、制造商、型号和性能。
• /proc/devices 当前运行的核心配置的设备驱动的列表。
• /proc/dma 显示当前使用的DMA通道。
• /proc/filesystems 核心配置的文件系统。
• /proc/interrupts 显示使用的中断
• /proc/ioports 当前使用的I/O端口。
• /proc/kcore 系统物理内存映象。
• /proc/kmsg 核心输出的消息。也被送到syslog 。

---

第8章 设备管理

8.1 设备管理概念

设备类型和特征

按交互对象分类

• 人机交互设备：显示设备、键盘、鼠标、打印机
• 与CPU等交互的设备：磁盘、磁带、传感器、控制器
• 计算机间的通信设备：网卡、调制解调器

按交互方向分类

• 输入设备：键盘、扫描仪

• 输出设备：显示设备、打印机

• 双向设备：输入/输出：硬盘、软盘、网卡

按外设特性分类

• 使用特征：存储、输入/输出
• 数据传输率：低速(键盘)、中速(打印机)、高速(网卡、磁盘)
• 信息组织特征(Linux)：字符设备(如打印机), 块设备(如磁盘),网络设备

设备管理主要功能

状态跟踪、设备分配、设备映射、设备控制/设备驱动、缓冲区管理

状态跟踪

生成设备管理器的数据结构，动态地记录各种设备的状态

设备分配

设备分配功能是设备管理的基本任务。

设备分配程序按照一定的策略，为申请设备的进程分配设备，记录设备的使用情况

设备映射

物理设备：I/O系统中实际安装的设备

物理名：ID或字符串

逻辑设备：应用软件使用的设备

逻辑名：友好名(Friendly Name)，(\\\\.\\MyDevice, Win), (/dev/Mydevice, Linux)

设备映射：

• 逻辑设备映射到物理设备
• 从应用软件的角度看，逻辑设备是一类物理设备的抽象
• 从设备管理程序的角度看，物理设备是逻辑设备的实例

设备独立性：

• 物理设备对用户透明，用户使用统一规范的方式使用设备
• 用户编程使用逻辑名，由系统实现逻辑设备到物理设备的转换

设备驱动

设备驱动功能：

• 对物理设备进行控制，实现I/O操作。

• 把来自应用的服务请求（例如读/写命令）转换为一系列I/O指令，控制设备完成相关操作。

  • read/write->I/O

• 向用户提供统一的设备使用接口

  • read/write/open
  • 把外设作为特别文件处理

设备驱动特点：

• 设备驱动程序与硬件密切相关。
• 每类设备都要配置特定的驱动程序
• 驱动程序一般由设备厂商根据操作系统要求编写。
• 操作系统仅对与设备驱动的接口提出要求

I/O缓冲区管理

I/O缓冲区管理的任务：

• 组织I/O缓冲区
• 为使用者提供获得和释放I/O缓冲区的手段

8.2 设备分配

独占型设备：包括了所有字符型设备

• 每次只能供一个进程单独使用
• 使用前申请——使用——使用后释放

共享型设备：包括了所有块设备

• 宏观，供多个进程同时占用；微观，多个进程交替使用

分配方法：独占分配，共享分配，虚拟分配

• 独占分配：申请成功——开始使用——用完释放

• 共享分配：即时申请（存储块）即时分配；因为要保证一次I/O操作原子性，有可能阻塞。

• 虚拟分配：申请独占设备，实际分配虚拟设备

虚拟分配详细内容

虚拟技术：在一类物理设备上模拟另一类物理设备的技术。通常借助辅存的一部分区域模拟独占设备，将独占设备转化为共享设备。

虚拟设备：用来模拟独占设备的部分辅存称为虚拟设备，虚拟独占设备

输入井：模拟输入设备的辅存区域

输出井：模拟输出设备的辅存区域

虚拟分配：进程申请独占设备，采用虚拟技术将该独占设备虚拟化出来的虚拟设备(部分辅存)分配给它

SPOOLing：虚拟技术和虚拟分配的具体实现方案，外围设备同时联机操作（假脱机输入输出操作）

• 磁盘中开辟的存储空间
  • 输入井：模拟脱机输入时的磁盘
  • 输出井：模拟脱机输出时的磁盘
• 内存中开辟的存储空间
  • 输入缓冲区：暂存输入数据，以后再传送到输入井
  • 输出缓冲区：暂存输出数据，以后再传送到输出设备
• 预输入进程
  • 模拟脱机输入的卫星机，将用户要求的数据从输入设备通过输入缓冲区再传送输入井。
  • 当用户进程需要数据时，直接从输入井读入所需数据
• 缓输出进程
  • 模拟脱机输出的卫星机。用户进程将输出数据从内存先传送到输出井。
  • 当输出设备空闲时，再将输出井的数据送到输出设备上
• 总结
  • 任务执行前：预先将程序和数据输入到输入井中
  • 任务运行时：使用数据时，从输入井中取出
  • 任务运行时：输出数据时，把数据写入输出井
  • 任务运行完：外设空闲时输出全部数据和信息
• 优点
  • “提高了”I/O速度：实际提高了I/O的效率，I/O的速度由机器本身决定
  • 将独占设备改造为“共享”设备：实现了虚拟设备功能

8.3 缓冲技术

缓冲：是两种不同速度的设备之间传输信息时平滑传输过程的常用手段

缓冲类别：

• 硬件缓冲器：容量较小，一般放在接口中，不需要CPU直接管理，不会影 响系统性能
• 软件缓冲区：容量较大，一般放在内存中。提前读/延后写

缓冲作用

• 连接不同数据传输速度的设备
  • 例子1：设备驱动与控制器的工作串行
    
  • 例子2：设备驱动与控制卡并行工作（双缓冲）
    
• 协调数据记录大小的不一致
  • 两个设备或设备与CPU之间的数据大小不一致
  • 例子1：网络消息的包和帧
    
  • 例子2：串行设备中字节与块或页
    
• 正确执行应用程序的语义拷贝
  • 例子1：write(Data, Len)向磁盘写入Data，确保写入磁盘的Data是write调用时刻的Data
    • 方法1：内核写完再返回(实时性差)，如果写完后到返回前这段时间中，可能write写入内容发生变化，导致语义改变。
    • 方法2：内核设置缓冲区，完成内核复制即返回；事后由内核把缓冲区写入磁盘(实时性差)；语义拷贝

提前读和延后写

作用：对存储设备而言；提高数据传输效率；减少进程访问目标设备的次数；

提前读：进程处理一个输入数据时，直接从I/O缓冲区读入，正确的数据已被提前读入到I/O缓冲区

• 内核提前从输入设备中把数据读到I/O缓冲区
• 但不一定是正确的数据
• 同步问题：ABC有顺序
  
  

延后写：进程输出数据时，仅把数据写入I/O缓冲区中。此后，待输出设备空闲时，缓冲区的数据写入输出设备

• 用户处理数据的同时内核输出（有延后）前一数据
• 同步问题
  
  

缓冲区构造

双缓冲：

环形缓冲：若干缓冲单元首尾链接形成一个环

• 两个线程：输出线程（读），输入线程（写）
• 三个指针：输入指针in，输出指针out，开始指针：start
• 开始时in = out = start
• 输入，判断 in == out
  • 相等，等待（系统没有空缓冲区了）
  • 不相等，信息送入*in, in = 缓冲区.next
• 输出，判断 out == in
  • 相等，等待（系统数据可取）
  • 不相等，取出*out, out = 缓冲区.next

8.4 设备驱动程序

Linux内核模块

Loadable Kernel Module： LKM

作用：解决单体内核机制的不足

• 一种未经链接的可执行代码
• 可以动态地加载或卸载模块
• 经过链接可称为内核的一部分

简单模块程序：

#include  
static int hello_init(void) 
{ 
	printk(\"Hello, Kernel!\\n\"); // 输出到内核信息 dmseg查看
	return 0; 
} 
static void hello_exit() 
{ 
	printk(\"Exit Kernel!\\n\"); 
} 
module_init(hello_init);	// insmod安装时调用， lsmod查看安装结果
module_exit(hello_exit);	// rmmod卸载时调用

Linux驱动程序（LDD）

Linux设备分类

• 字符设备（如串口设备）
  • 以字节为单位逐个进行I/O操作
  • 字符设备中的缓存是可有可无
  • 不支持随机访问
• 块设备（如IDE硬盘设备）
  • 块设备的存取是通过buffer、cache来进行
  • 可以进行随机访问
  • 支持可安装文件系统
• 网络设备
  • 通过BSD套接口访问（Socket）

设备文件

• 硬件设备作为文件看待
• 使用文件接口打开、关闭、读写和I/O控制设备
  • 字符设备和块设备通过设备文件访问
  • 主设备号
    • 标识该设备的种类，标识驱动程序
    • 1~255
    • Linux内核支持动态分配主设备号
  • 次设备号
    • 标识同一设备驱动程序的不同硬件设备
    • 次设备号只在驱动程序内部使用，内核直接把次设备号传递给驱动程序，由驱动程序管理
  • Linux可以在/dev目录下找到设备文件
    

驱动程序基本接口

• 面向用户程序的接口
• 面向I/O管理器的接口
  • 注册函数
  • 注销函数
  • 数据结构
  • 请求队列
• 面向设备的接口：把用户请求转化为端口操作IN/OUT
  • 无条件传送
  • 查询传送
  • 中断传送
  • DMA传送

字符驱动程序示例

4个面向用户的接口

static int chr_open(struct inode *pinode, struct file *pfile)
{
    printk(KERN_EMERG \"line:%d, %s is called\\n\", __LINE__, __FUNCTION__);
    return 0;
}
static int chr_read(struct file *pfile, char __user *buff, size_t size, loff_t *off)
{
    printk(KERN_EMERG \"line:%d, %s is called\\n\", __LINE__, __FUNCTION__);
    return 0;
}
static int chr_write(struct file *pfile, char __user *buff, size_t size, loff_t *off)
{
    printk(KERN_EMERG \"line:%d, %s is called\\n\", __LINE__, __FUNCTION__);
    return 0;
}
static int chr_release(struct inode *pinode, struct file *pfile)
{
    printk(KERN_EMERG \"line:%d, %s is called\\n\", __LINE__, __FUNCTION__);
    return 0;
}

file_operations结构体

struct file_operations {
	struct module *owner;
	loff_t (*llseek) (struct file *, loff_t, int);
	ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
	ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
	ssize_t (*aio_read) (struct kiocb *, const struct iovec *, unsigned long, loff_t);
	ssize_t (*aio_write) (struct kiocb *, const struct iovec *, unsigned long, loff_t);
	int (*readdir) (struct file *, void *, filldir_t);
	unsigned int (*poll) (struct file *, struct poll_table_struct *);
	int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
	long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);
	long (*compat_ioctl) (struct file *, unsigned int, unsigned long);
	int (*mmap) (struct file *, struct vm_area_struct *);
	int (*open) (struct inode *, struct file *);
	int (*flush) (struct file *, fl_owner_t id);
	int (*release) (struct inode *, struct file *);
	int (*fsync) (struct file *, struct dentry *, int datasync);
	int (*aio_fsync) (struct kiocb *, int datasync);
	int (*fasync) (int, struct file *, int);
	int (*lock) (struct file *, int, struct file_lock *);
	ssize_t (*sendfile) (struct file *, loff_t *, size_t, read_actor_t, void *);
	ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);
	unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
	int (*check_flags)(int);
	int (*dir_notify)(struct file *filp, unsigned long arg);
	int (*flock) (struct file *, int, struct file_lock *);
	ssize_t (*splice_write)(struct pipe_inode_info *, struct file *, loff_t *, size_t, unsigned int);
	ssize_t (*splice_read)(struct file *, loff_t *, struct pipe_inode_info *, size_t, unsigned int);
};

具体file_operation定义和初始化

static const struct file_operation chr_fops =
{
    .read		= chr_read,
    .write		= chr_write,
    .release 	= chr_release,
    .open		= chr_open,
};

2个面向IO管理器的接口

static int __init chr_init(void) {
    printk(KERN_EMERG \"Install chr driver.\\n\");
    alloc_chrdev_region(&dev_no, 0, 1, \"chr_demo\");	// 动态分配设备号
    cdev_init(&chr_dev, &chr_fops); //初始化cdev结构，绑定fops
    chr_dev.owner = THIS.MODULE;
    cdev_add(&chr_dev, dev_no, 1); //注册设备
    
    dev_class = class_create(THIS_MODULE, \"chr_demo\");
    device_create(dev_class, NULL, dev_no, NULL, \"chr_demo\"); //创建设备文件
    return 0;
}
static int __exit chr_init(void) {
    printk(KERN_EMERG \"Uninstall chr driver.\\n\");
    device_destroy(dev_class, dev_no);
    class_destroy(dev_class);
    cdev_del(&chr_dev); //注销设备
    unregister_chrdev_region(dev_no, 1); //释放占用的设备号
}
module_init(chr_init);
module_exit(chr_exit);

Makefile

obj-m := chr_driver.o
KDIR := /lib/modules/`uname -r`/build
PWD := $(shell pwd)
default:
	make -C $(KDIR) M=$(PWD) modules
clean:
	rm -rf *.o *.mod.* *.ko *.symvers *.order

测试

驱动程序模块插入内核

insmod chr_driver.ko

查看是否载入

cat /proc/devices

从内核移除设备

rmmod chr_driver

测试程序

int main(void)
{
    int fd;
    char buf = 0x01;
    fd = open(\"/dev/chr_demo\", O_RDWR); // 打开设备文件
    printf(\"%d\\n\", fd);
    read(fd, &buf, 1); 	// 读
    write(fd, &buf, 1); // 写
    close(fd);
    return 0;
}

---

第9章 文件管理

9.1 文件系统概念

文件定义：文件是系统中信息存放的一种组织形式

• 文件是若干信息项的构成，信息项可以是字节，可以是结构化数据
• 用户通过读写指针来存取文件的信息项
• 文件具有文件名。用户通过文件名存取文件

文件分类：

• 文件用途分类
  • 系统文件：包括操作系统的可执行程序和数据文件。这种文件不对用户开放，仅供系统使用
  • 库文件：系统为用户提供的各种标准函数库和实用程序等。用户只能使用，而无权对其进行修改。
  • 用户文件：用户创建的文件，如用户可执行程序，源程序，数 据文件等。这种文件的使用和修改权均属于用户
• 文件操作权限分类
  • 只读文件：只允许读操作
  • 读写文件：允许进行读写操作
  • 不保护文件：不作任何操作限制
• 文件性质分类
  • 普通文件：指一般的用户文件和/或系统文件
  • 目录文件：由目录项组成的文件。目录项:文件名，文件属性，文件存放地址…
  • 设备文件：把设备作为文件管理和使用

文件属性

• 指定文件的类型、操作特性和存取保护等一组信息。
• 文件的属性一般存放在文件所在的目录文件的目录项中。
• MS-DOS系统中，文件属性占目录项的一个字节（00000001表示文件仅读，00000010表示隐含文件等）

文件系统：

• 定义：负责管理文件的机构称为文件系统。
• 功能
  • 负责文件的创立、撤销、读写、修改、复制和存取等
  • 管理存放文件的存储设备
• 目标：让用户以文件名来存取文件

9.2 文件结构

逻辑结构：

• (用户的观点)
• 为用户提供逻辑结构清晰、使用方便的文件
• 强调文件信息项的构成方式和用户的存取方式

物理结构：

• (系统的观点)
• 文件在存储设备（例:硬盘）上的存储结构
• 强调合理利用储存空间，缩短I/O存取时间。

文件的逻辑结构

记录式文件：

• 信息项由记录组成，一个记录包含若干成员
• 例
  • 学生记录：姓名，学号，性别，成绩
  • 学生花名册文件：包含若干个学生记录
• 特点
  • 文件中需保存记录长度和数量等说明信息
  • 浪费存储空间

流式文件：现代OS中文件是流式，由应用解释文件（比如pdf阅读器打开pdf文件）

• 信息项是字节，文件长度就是字节的数量
• 优点
  • 文件无需额外的说明信息或控制信息
  • 节省存储空间

文件的存取：

• 顺序存取：按文件信息单位排列的顺序依次存取

  • 读写指针：当打开文件时，文件的读写指针指向第1个信息单位(字节或记录)，每存取1个信息单位后读写指针自动加1而指向下一个信息单位

• 随机存取：直接存取，每次存取操作时先确定存取位置

  • 对流式或定长记录文件比较容易确定存取位置。
  • 对不定长的记录式文件比较麻烦
    • 从首记录顺序查询，直到找到目的记录为止。
    • 建立索引：索引可作为文件一部分也可单独建索引文件

• 文件读写示例

  FILE *pFile = fopen(\"demo.txt\", \"rb\");
  char *pBuf;
  fseek(pFile, 0, SEEK_END);	// 移动文件指针到末尾
  int len = ftell(pFile);		// 获取文件指针偏移量
  pBuf = new char[len];
  rewind(pFile);				// 指针移动到文件头
  fread(pBuf, 1, len, pFile);	// 读
  fclose(pFile);
  

文件的物理结构

连续文件

• 文件：按逻辑顺序存放在存储设备的连续物理块中
• 文件目录：记录文件长度（块数）和首个物理块号
• 特点：文件建立时给出文件最大长度并登记文件起始位置
• 优点
  • 简单
  • 支持顺序存取和随机存取
  • 顺序存取速度快：所需磁盘寻道次数和寻道时间最少
• 缺点
  • 文件不易动态增长
    • 预留空间：浪费
    • 重新分配和移动
  • 不利于文件插入和删除
  • 外部碎片问题

串联文件：文件信息存放在不连续的存储块中（FAT文件系统）

• 文件：每个存储块有一个指针(next)，指向文件下一个逻辑块所在的存储块
• 文件目录：文件名+存储指针（指向第一个存储块）
• 特点：串联文件适用于顺序存取。随机存取较为困难
• 优点
  • 提高了磁盘空间利用率，不存在外部碎片问题
  • 有利于文件插入和删除
  • 有利于文件动态扩充
• 缺点
  • 存取速度慢，不适于随机存取
  • 可靠性问题：例如某个next链接指针出错
  • next链接指针占用一定的空间

索引文件：文件存放在不连续的物理块中，系统建立索引表记录文件的逻辑块和存储块的对应关系

• 文件：索引表+数据区，索引表类似页表，且索引表本身要占据额外的存储空间，查文件索引，由逻辑块号查得物理块号
• 文件目录：文件名+索引指针（指向（指向第一个存储块的索引指针））
• 优点
  • 保持了链接结构的优点，又解决了其缺点
  • 即能顺序存取，又能随机存取
  • 满足了文件动态增长、插入删除的要求
  • 能充分利用外存空间
• 缺点
  • 索引表本身带来了系统开销：内外存空间，存取时间

9.3 文件存储和目录

文件存储空间管理

定义：记录当前磁盘的使用情况，创建文件时分配存储空间，删除文件时收回存储空间

空闲文件：一片连续空闲区当作一个特殊文件，该文件由多个连续的空闲存储块组成。所有的空闲文件代表存储设备的空闲空间

记录磁盘空闲块的方法：空闲文件目录，空闲块链、位示图

空闲文件目录：记录所有空闲文件，每个表项对应一个空闲文件

• 表项：文件号、第一个空闲块号、空闲块个数

空闲块链：把存储设备上的所有空闲块链接在一起

• 当申请者需要空闲块时，分配程序从链头开始摘取所需要的空闲块，然后调整链首指针。
• 当回收空闲块时，把释放的空闲块逐个加在链尾上

位示图：从内存中划出若干个字节，每位对应1个存储块

• 该位为1：对应存储块空闲
• 该位为0：对应存储块已分配

文件目录管理

文件目录：文件名址录，记录文件名和存放地址的目录表

为了对大量文件进行分门别类的管理，提高文件检索的效率，现代操作系统往往将文件的一些属性也记录在目录中

目录文件：文件目录以文件形式存于外存，这个文件叫目录文件

文件目录的功能：将文件名转换为外存物理位置的功能

文件全名和路径：包括从根目录开始到文件为止的通路上所有子目录路径

• 子目录名之间用正斜线“/”或反斜线“\\”隔开
• 子目录名组成的部分又称为路径名
• 每个文件都有唯一路径名
• 两种路径名形式
  • 绝对路径名：从根目录直到指定的文件
  • 相对路径名：从当前目录直到指定的文件

Linux的目录是树形结构

文件的保护

• 仅允许执行E
• 仅允许读R
• 仅允许写W
• 仅允许在文件尾写A
• 仅允许对文件进行修改U
• 允许改变文件的存取枚限C
• 允许取消文件D
• 权限可进行适当的组合

文件操作

• 创建文件
• 写文件
• 读文件
• 文件定位
• 删除文件
• 截短文件
• 属性设置和读取

目录操作

• 创建目录

  • 管理存放文件的存储设备

• 目标：让用户以文件名来存取文件

9.2 文件结构

逻辑结构：

• (用户的观点)
• 为用户提供逻辑结构清晰、使用方便的文件
• 强调文件信息项的构成方式和用户的存取方式

物理结构：

• (系统的观点)
• 文件在存储设备（例:硬盘）上的存储结构
• 强调合理利用储存空间，缩短I/O存取时间。

文件的逻辑结构

记录式文件：

• 信息项由记录组成，一个记录包含若干成员
• 例
  • 学生记录：姓名，学号，性别，成绩
  • 学生花名册文件：包含若干个学生记录
• 特点
  • 文件中需保存记录长度和数量等说明信息
  • 浪费存储空间

流式文件：现代OS中文件是流式，由应用解释文件（比如pdf阅读器打开pdf文件）

• 信息项是字节，文件长度就是字节的数量
• 优点
  • 文件无需额外的说明信息或控制信息
  • 节省存储空间

文件的存取：

• 顺序存取：按文件信息单位排列的顺序依次存取

  • 读写指针：当打开文件时，文件的读写指针指向第1个信息单位(字节或记录)，每存取1个信息单位后读写指针自动加1而指向下一个信息单位

• 随机存取：直接存取，每次存取操作时先确定存取位置

  • 对流式或定长记录文件比较容易确定存取位置。
  • 对不定长的记录式文件比较麻烦
    • 从首记录顺序查询，直到找到目的记录为止。
    • 建立索引：索引可作为文件一部分也可单独建索引文件

• 文件读写示例

  FILE *pFile = fopen(\"demo.txt\", \"rb\");
  char *pBuf;
  fseek(pFile, 0, SEEK_END);	// 移动文件指针到末尾
  int len = ftell(pFile);		// 获取文件指针偏移量
  pBuf = new char[len];
  rewind(pFile);				// 指针移动到文件头
  fread(pBuf, 1, len, pFile);	// 读
  fclose(pFile);
  

文件的物理结构

连续文件

• 文件：按逻辑顺序存放在存储设备的连续物理块中
• 文件目录：记录文件长度（块数）和首个物理块号
• 特点：文件建立时给出文件最大长度并登记文件起始位置
• 优点
  • 简单
  • 支持顺序存取和随机存取
  • 顺序存取速度快：所需磁盘寻道次数和寻道时间最少
• 缺点
  • 文件不易动态增长
    • 预留空间：浪费
    • 重新分配和移动
  • 不利于文件插入和删除
  • 外部碎片问题

[外链图片转存中…(img-B0pSobgd-1641814982957)]

串联文件：文件信息存放在不连续的存储块中（FAT文件系统）

• 文件：每个存储块有一个指针(next)，指向文件下一个逻辑块所在的存储块
• 文件目录：文件名+存储指针（指向第一个存储块）
• 特点：串联文件适用于顺序存取。随机存取较为困难
• 优点
  • 提高了磁盘空间利用率，不存在外部碎片问题
  • 有利于文件插入和删除
  • 有利于文件动态扩充
• 缺点
  • 存取速度慢，不适于随机存取
  • 可靠性问题：例如某个next链接指针出错
  • next链接指针占用一定的空间

[外链图片转存中…(img-E834Y4YH-1641814982958)]

索引文件：文件存放在不连续的物理块中，系统建立索引表记录文件的逻辑块和存储块的对应关系

• 文件：索引表+数据区，索引表类似页表，且索引表本身要占据额外的存储空间，查文件索引，由逻辑块号查得物理块号
• 文件目录：文件名+索引指针（指向（指向第一个存储块的索引指针））
• 优点
  • 保持了链接结构的优点，又解决了其缺点
  • 即能顺序存取，又能随机存取
  • 满足了文件动态增长、插入删除的要求
  • 能充分利用外存空间
• 缺点
  • 索引表本身带来了系统开销：内外存空间，存取时间

[外链图片转存中…(img-euIsRz9K-1641814982959)]

9.3 文件存储和目录

文件存储空间管理

定义：记录当前磁盘的使用情况，创建文件时分配存储空间，删除文件时收回存储空间

空闲文件：一片连续空闲区当作一个特殊文件，该文件由多个连续的空闲存储块组成。所有的空闲文件代表存储设备的空闲空间

记录磁盘空闲块的方法：空闲文件目录，空闲块链、位示图

空闲文件目录：记录所有空闲文件，每个表项对应一个空闲文件

• 表项：文件号、第一个空闲块号、空闲块个数

[外链图片转存中…(img-GDWPsEWC-1641814982959)]

空闲块链：把存储设备上的所有空闲块链接在一起

• 当申请者需要空闲块时，分配程序从链头开始摘取所需要的空闲块，然后调整链首指针。
• 当回收空闲块时，把释放的空闲块逐个加在链尾上

位示图：从内存中划出若干个字节，每位对应1个存储块

• 该位为1：对应存储块空闲
• 该位为0：对应存储块已分配

[外链图片转存中…(img-V84ZHY5i-1641814982959)]

文件目录管理

文件目录：文件名址录，记录文件名和存放地址的目录表

为了对大量文件进行分门别类的管理，提高文件检索的效率，现代操作系统往往将文件的一些属性也记录在目录中

目录文件：文件目录以文件形式存于外存，这个文件叫目录文件

文件目录的功能：将文件名转换为外存物理位置的功能

文件全名和路径：包括从根目录开始到文件为止的通路上所有子目录路径

• 子目录名之间用正斜线“/”或反斜线“\\”隔开
• 子目录名组成的部分又称为路径名
• 每个文件都有唯一路径名
• 两种路径名形式
  • 绝对路径名：从根目录直到指定的文件
  • 相对路径名：从当前目录直到指定的文件

Linux的目录是树形结构

文件的保护

• 仅允许执行E
• 仅允许读R
• 仅允许写W
• 仅允许在文件尾写A
• 仅允许对文件进行修改U
• 允许改变文件的存取枚限C
• 允许取消文件D
• 权限可进行适当的组合

文件操作

• 创建文件
• 写文件
• 读文件
• 文件定位
• 删除文件
• 截短文件
• 属性设置和读取

目录操作

• 创建目录
• 删除目录