操作系统
2019-12-30 10:04:17 1 举报AI智能生成
登录查看完整内容
操作系统复习思维导图电子科大
作者其他创作
大纲/内容
操作系统
第二章 进程管理
进程描述与控制
进程的概念
进程的定义
进程由程序代码、相关数据及进程控制块组成。
进程的基本特征
动态性：（本质特性） 一个正在计算机上执行的程序实例，存在生命周期
并发性：（重要特性）任何进程都可以同其他进程一起向前推进
独立性： 各进程的地址空间相互独立，除非采用进程间通信手段
异步性： 按各自独立的、不可预知的速度向前推进
进程与程序比较
进程的状态
进程的轨迹：执行指令序列，用于描述单个进程的行为。
两状态进程状态模型
五状态进程模型
进程的三种基本状态
就绪状态： 当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行过程。
执行状态： 进程已获得CPU，其程序正在执行。
阻塞状态： 正在执行的进程由于等待发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，把这种暂停状态称为阻塞状态，有时也称为等待状态。
进程的三种基本状态及其转换
进程的五种状态
进程五状态转换模型
阻塞队列和就绪队列
单阻塞队列、单就绪队列
多阻塞队列、单就绪队列
被挂起的进程
多个进程竞争内存资源时可能导致下列现象
内存资源紧张：如何在有限的内存中装入尽量多的进程？
无就绪进程，处理机空闲： I/O操作速度远低于CPU计算速度，导致所有进程阻塞，等待I/O，此时该如何处理？
交换：把内存中一个进程的部分或全部移到磁盘中。
当内存紧张或内存中没有就绪进程时，操作系统将一个阻塞进程换出到磁盘中的挂起队列。
之后操作系统要么从挂起队列中取回一个进程，或者接纳一个新进程进入内存。
挂起状态
进程被交换到外存，状态变为挂起状态。
将内存中处于阻塞、就绪、甚至是执行状态的进程放到外存，不再参与CPU的竞争，我们把这种静止状态称为挂起状态。
具有一个挂起状态的进程状态转换
存在问题：如果挂起进程等待的事件没有发生，把挂起进程取回内存没有意义
进程挂起的原因
被挂起进程的特征
不能立即执行
挂起条件独立于阻塞条件
使之挂起的进程：自身、OS、父进程
激活挂起进程的进程：实施挂起操作的进程
阻塞与挂起
阻塞与否：进程是否等待事件
挂起与否：进程是否被换出内存
四种状态组合
就绪：进程在内存，准备执行
阻塞：进程在内存，等待事件
就绪/挂起：进程在外存，只要调入内存并获得CPU即可执行
阻塞/挂起：进程在外存，等待事件
进程控制结构
进程的物理存在
进程位置
进程最少必须包括一个或一组被执行的程序
进程制至少应有足够的内存空间来保存其相关程序和数据
程序的执行通常涉及用于跟踪过程调用和过程间参数传递的栈
进程属性
操作系统控制进程所需要的相关属性（进程控制块）
程序、数据、栈和属性的集合称为进程映像
进程映像的位置取决于所用的内存管理方案
进程控制块中的三类信息
进程标示符：唯一地标识一个进程
内部标识符： 操作系统为每个进程赋予的一个唯一整数，便于系统控制
父进程标识符： 用于标识父进程
用户标识符：\t标识创建进程的用户
处理机状态信息：主要是由处理器的各种寄存器中的内容组成的
通用寄存器（用户可视寄存器）： 通常有8-32个，暂存信息
控制和状态寄存器
程序计数器：要访问的下一条指令的地址
控制和状态寄存器：程序状态字（PSW）寄存器，如Intel X86的EFLAGS寄存器，存放条件码（是否溢出、进位等）、执行方式（内核或用户模式）、中断屏蔽标志等
栈指针：存放过程和系统调用参数及调用地址
进程控制信息：与进程调度和进程切换有关的信息
调度和状态信息
进程状态
进程优先级
进程调度所需的其它信息，如进程已等待CPU的时间总和、进程已执行的时间总和等；
事件，指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因
链接指针：如同一状态进程的链接；父子进程的链接
进程间通信： 指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等。
程序和数据的地址： 指分配给进程的段表或页表的指针
资源所有权和使用情况： 指示进程控制的资源，如打开的文件，处理器或其他资源的使用历史情况（供调度器使用）
进程控制块的组织方式
索引方式： 系统根据所有进程的状态建立几张索引表。
链接方式： 通过链接指针将PCB块连接起来，形成队列。
单一队列： 所有PCB块连接成一个队列
多级队列： 相同状态的PCB块连接成一个队列
内核功能与执行模式
内核功能
内核（操作系统的核心）
操作系统中包含重要系统功能的部分。
常驻内存，便于提高操作系统运行效能。
不同操作系统对内核的功能范围的设定不同
通常而言，操作系统内核的功能包括
资源管理功能
进程管理
进程创建和终止
进程的调度和分派
进程切换
进程同步和进程间通信的支持
管理进程控制块
存储管理
为进程分配地址空间
交换
页和段管理
I/O设备管理
I/O缓冲区的管理
为进程分配I/O通道和设备等
支撑功能
中断处理： 中断处理既是内核的基本功能，也是整个操作系统赖以活动的基础，操作系统的一切重要活动最终都依赖于中断。
时钟管理： 操作系统的很多功能都依赖于时钟，如时间片控制等。
记账（统计、监测）功能
执行模式
大多数处理器至少支持两种模式
与操作系统相关的处理器模式——内核模式（系统模式/控制模式）
与操作系统相关的处理器模式，具有更多优先权
运行操作系统的内核
某些指令只能在特权模式下运行
读取和修改程序状态字之类的控制寄存器的指令
原始I/O指令
与内存管理相关的指令
部分内存只能在特权模式下访问
与用户程序相关的处理器执行模式——用户模式
具有较少优先权的模式
用户程序在该模式下运行
采用两种模式的原因：保护操作系统和重要的操作系统表（如PCB）不受程序干扰
处理机如何知道它在什么模式下执行
当用户调用操作系统服务或中断促发系统例程时，相关位被置为内核模式
当从系统服务返回用户进程时，执行模式置为用户模式
模式切换：系统模式和用户模式之间的相互转换
模式切换的原因(用户to系统)：系统调用或中断
出现中断时，系统会作如下工作
将程序计数器置为中断处理程序的开始地址
从用户模式切换到内核模式，以便中断处理能执行特权指令
模式切换是否会必然导致进程切换： 不一定 （如I/O中断不一定伴随进程切换）
进程控制
实现方式：进程控制由原语来实现
原语:用于完成一定功能的过程。它是原子操作，执行过程中不允许被中断。
进程的创建与撤销
引起创建进程的典型事件
用户登陆：为终端用户创建一个进程
作业调度（非进程调度）：为被调度的作业创建一个进程
提供服务：如要打印时建立打印进程
已有进程请求：由已有进程创建子进程
创建进程（create原语）的步骤
给新进程分配一个唯一的进程标识符
为进程分配空间
初始化进程控制块
初始化标识信息
初始化处理机状态信息：如使程序计数器指向程序的入口地址，使栈指针指向栈顶等
初始化进程调度信息： 如设置进程的状态、优先级。
建立链接，将之插入就绪或就绪/挂起链表。
建立或扩充其它数据结构
引起进程终止的事件
正常结束：如exit，halt，logoff
异常结束：越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、被0除I/O故障
外界干预
父进程请求
父进程结束
进程终止过程（进程终止原语）
根据被终止进程的标识符找到其PCB，读出该进程的状态。
若该进程为执行状态，则终止其执行，调度下一个就绪进程执行。
若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程
将该进程所拥有的全部资源，或者归还给其父进程，或者归还给系统
将被终止进程（它的PCB）从所在队列（或链表）中移出，等待其他程序来搜集信息
进程的阻塞与唤醒
引起进程阻塞的事件
请求系统服务而得不到满足时，如向系统请求打印
启动某种操作而需同步时：例如进程访问临界区，而临界区暂时被锁定
无新工作可做
进程阻塞过程
正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block()把自己阻塞。
把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。
调度程序将处理机分配给另一就绪进程，并进行切换。
进程唤醒过程
当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup()，将等待该事件的进程从阻塞队列中移出；
将其PCB中的现行状态由阻塞改为就绪，插入到就绪队列中。
进程的挂起与激活
进程的挂起：当出现了引起进程挂起的事件时，系统将利用挂起原语suspend( )将指定进程挂起。
挂起原语的执行过程
检查被挂起进程的状态，状态改变：就绪 —> 就绪/挂起；阻塞 —> 阻塞/挂起。
插入相应的队列
进程的激活：当发生font color=\"#0076b3\
激活原语的执行过程
利用激活原语active()将指定进程从外存调入内存；检查该进程的状态，状态改变：就绪/挂起 —> 就绪；阻塞/挂起 —> 阻塞；
插入相应队列。
进程切换：调度另一个就绪进程占用处理器执行
何时会发生进程切换
进程切换与模式切换
模式切换：用户模式和内核模式之间的相互转换
中断/模式切换是否会必然导致进程切换
进程状态转换
模式切换与进程切换不同，模式切换可在不改变运行进程状态的情况下出现
如果当前运行进程将转换成另一个状态，如就绪、阻塞等，则操作系统必须使环境产生实质性的变化
进程切换步骤
保存处理器上下文环境，包括程序计数器和其它寄存器
更新当前处于运行状态进程的进程控制块
将进程的进程控制块移至相应队列（就绪、阻塞等）
选择另一进程执行
更新其进程控制块信息
恢复被选择进程的上下文环境
fork() 作用：创建一个新进程
调用格式：pid = fork()
在调用fork()之后，父进程和子进程均在下一条语句上继续运行
父、子进程的fork返回值不同
在子进程中返回时，pid为0；
在父进程中返回时，pid为所创建的子进程的标识
fork()创建子进程之后，执行返回父进程，或调度切换到子进程或其他进程
fork创建一个新进程（子进程），除了子进程标识符和其PCB结构中的某些特性参数不同之外，子进程是父进程的精确复制
父、子进程的运行是无关的，所以运行顺序也不固定。若要求父子进程运行顺序一定，则要用到进程间的通信。
线程
进程与线程
进程的两个基本属性
拥有资源的独立单位：一个进程包括一个保存进程映像的虚地址空间，拥有对资源的控制或所有权。
调度／执行的基本单位：一个具有状态和优先级，可被被操作系统调度并分派的实体。
线程的诞生
为区分这两个特点
调度并分派的单位通常称为线程或轻量级进程(LWP)
而资源所有权的单位通常称为进程。
传统的每个进程中只有一个线程在执行（没有考虑线程的概念），称作单线程进程。
多线程(multithreading)：操作系统在单个进程内支持多个并发路径的能力。
进程与线程的比较
概念
进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
线程是进程中的一个实体，是独立调度和分派的基本单位
拥有的资源
进程，拥有资源的单位
线程，拥有少量私有资源
同一进程内的线程共享进程的资源
调度
传统操作系统
拥有资源的基本单位——进程
独立调度的基本单位——进程
引入线程的操作系统
独立调度的基本单位——线程
线程切换
同一进程中的线程间切换，不会引起进程切换
不同进程中的线程切换，将引起进程切换
并发性
进程之间，存在并发
同一进程的多个线程之间，亦存在并发
引入线程的操作系统具有更好的并发性，能更有效地使用系统资源和提高系统吞吐量
系统开销（与进程相比，线程优点）
创建、撤销进程的开销大于创建、撤销线程的开销
同一进程内线程切换的开销，小于进程切换开销
同一进程间的多个线程同步和通信较容易
有些类型的线程切换、同步和通信无需操作系统内核的干预
多线程并发
线程的基本状态：就绪状态、执行状态、阻塞状态
线程一般不具有挂起状态
一个进程可以创建和撤消一个或多个线程，同一进程中的多个线程可并发执行。
线程的基本操作
派生(Spawn)：系统创建进程时，同时也为该进程派生一个线程
阻塞(Block)：等待某事件时，释放处理机
解除阻塞(Unblock)：事件发生，状态变成就绪，插入就绪队列，等待调度执行
结束(Finish)： 线程执行完毕，释放其私有资源
线程类型：依据线程是否对内核透明
用户级线程
线程的创建、撤销和切换等操作全部由应用程序完成
操作系统内核不知道线程的存在，仍以进程为调度单位
Infomix支持用户级线程
用户级线程的优点
线程的管理和控制仅在用户级进行，切换开销小
调度更灵活
线程库独立于系统内核
用户级线程的缺点
用户级线程中的系统调用常常会引起线程及整个进程阻塞，削弱了线程的并发性
同一进程中的多线程无法利用多处理器技术
内核级线程
线程的创建、撤销和切换等操作由系统内核完成
内核级线程又称为轻量级进程LWP
操作系统以线程为调度单位
Windows 2000/XP、Linux和OS/2等操作系统采用了内核级线程技术
内核级线程的优点
内核可以同时把同一个进程的多个线程调度到多个处理器
如果进程中的一个线程被阻塞（包括页面故障），内核可以调度同一进程中的其他线程
内核例程也可以是多线程的
内核级线程的缺点
相对于用户级线程而言，模式切换开销大
混合线程
线程的创建、撤销、调度和同步等操作在用户级应用程序中完成
多个用户级线程被影射到一个或较少的某些内核级线程
Solaris操作系统采用了混合线程模式
用户级、内核级、混合线程模式的比较
进程的调度
调度的引入
如果有多个进程（线程）竞争CPU
需要选择下一个要运行的进程（线程）
OS中完成这部分工作的程序称为调度程序
调度程序使用的算法称为调度算法
调度的类型
处理器调度的类型
处理器调度的目的：满足系统目标（响应时间、吞吐量、处理器效率）的方式，把进程分配到一个或多个处理器上执行。
处理器调度分为三类
长程调度（高级调度、作业调度）
决定外存上处于后备队列中的哪个作业能够进入系统中被处理
为它们创建进程、分配必要的资源
将新创建的进程排在就绪队列（就绪/挂起）上，等待短程（中程）调度
长程调度需要考虑两个问题
何时创建一个新进程？
取决于多道程序的度，即允许同时在内存中运行的进程数。另外，若处理器的空闲时间超过了某个阈值，也可能会启动长程调度。
选择哪些作业来创建进程？
取决于长程调度算法
中程调度（中级调度）
对换功能的一部份，用以提高内存的利用率和系统的吞吐量
内存紧张时，选择一个进程换出到外存（换出）
内存充裕时，从外存选择一个挂起状态的进程调度到内存（换入）
只有支持进程挂起的操作系统才具有中程调度功能
短程调度（进程调度、低级调度）
决定就绪队列中的哪个进程应获得处理器
运行频率最高
现代操作系统几乎都具有短程调度功能
引发短程调度的事件：时钟中断、I/O中断、操作系统调用、信号（如信号量）
短程调度的主要目标：按照优化系统某些方面的方式，来分配处理器时间
调度的规则
基本概念
响应时间： 从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。
周转时间： 从作业被提交给系统开始，到作业完成为止的这段时间间隔，也称为作业周转时间。
截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间。
系统吞吐量：在单位时间内，系统所完成的作业数。
处理器利用率：处理器处于忙状态的时间百分比
面向用户的规则
响应时间快：尽可能使绝大多数用户的请求能在能够接受的响应时间内完成，常用于评价分时系统的性能。
平均周转时间短：常用于评价批处理系统的性能，涉及长程调度、中程调度和短程调度。
满足截止时间：常用于评价实时系统的性能。
面向系统的规则
系统吞吐量大： 常用于评价批处理系统的性能。
处理器利用率高
大、中型多用户系统较看重处理器的利用率
单用户微机或某些实时系统不看重处理器的利用率
各类资源的平衡使用： 使系统中的各种资源都尽量处于忙碌状态。
公平性： 对所有进程公平，不偏袒任何进程。
优先权：优先权高的进程应优先调度
几乎所有操作系统的调度算法都可考虑优先权原则
仅考虑优先权会导致进程饥饿，即某些低优先权进程长时间得不到调度。
可以考虑动态优先权，将进程排队的等待时间等因素纳入优先权的计算。
调度规则总结
面向用户，与性能相关：周转时间、响应时间、 最后期限（截止时间）
面向用户，与性能无关：可预测性
面向系统，与性能相关：吞吐量、 处理器利用率
面向系统，与性能无关：公平性、强制优先级、平衡资源
调度的决策方式
非剥夺（非抢占）方式
执行进程只有在执行完毕，或因申请I/O阻塞自己时，才中断其执行，释放处理机。
不利于“即时性”要求较高的分时和实时系统，主要用于批处理系统。
剥夺（抢占）方式
当新进程到来
具有较高优先权的进程进入就绪队列
基于时间片调度的系统中，时间片用完，中断当前进程的执行，调度新的进程执行。
会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统和分时系统
调度算法
定义
根据系统的资源分配策略所规定的资源分配算法
对于不同的系统目标，通常采用不同的调度算法
常见的调度算法
先来先服务（FCFS）
选择最先进入就绪队列的进程投入执行，即进程按照请求CPU的顺序使用CPU。
FCFS算法评价
属于非抢占调度方式
有利于CPU繁忙型的进程，而不利于I/O繁忙型的进程
平均周转时间长
对长进程（作业）有利，不利于短进程（作业）
时间片轮转调度算法（RR）
每个进程被分配一个时间片，如果在时间片结束时该进程还在运行，则剥夺其CPU并分配给另一个进程
被剥夺CPU的进程则插入到就绪队列末尾，等待下次调度
如果该进程在时间片内阻塞或结束，则立即切换CPU
评价
属于抢占调度方式
常用于分时系统或事务处理系统
时间片的设置与系统性能、响应时间密切相关
时间片太短：进程切换频繁，降低CPU效率
时间片太长：引起对短的交互请求的响应时间变长
在分时系统中，时间片大小的确定应综合考虑最大用户数目、响应时间、系统效率等多种因素
对CPU密集型（繁忙型）进程有利，对I/O型密集型（繁忙型）进程不利
CPU密集型进程可充分利用时间片
而I/O密集型进程每次短时间使用CPU，之后I/O阻塞，I/O操作完成加入就绪队列后，若有CPU密集型进程占用CPU，或就绪队列里已经有CPU密集型进程，则需要长时间等待
CPU密集型进程不公平的使用了大部分CPU时间
RR算法的改进：VRR算法
增加一个辅助队列，接收I/O阻塞完成的进程，调度优先于就绪队列，但占用的处理机时间小于就绪队列的时间片
算法分析：VRR算法比RR算法公平
短进程（作业）优先（SPF/SJF）
短进程或短作业优先调度，前提为执行时间预知
SPF评价
非抢占调度方式
该算法对长作业不利，可能导致长进程饥饿。
有利于短进程，减小了平均周转时间。
缺少剥夺机制，不适用于分时系统或事务处理环境。
作业（进程）的长短根据用户所提供的估计执行时间而定，用户估计不准时，导致该算法不一定能真正做到短作业优先调度。
剩余时间最短者优先算法（SRT）
调度程序总是选择预期剩余时间最短的进程
当一个新进程加入就绪队列时，如果它比当前运行的进程具有更短的剩余时间，就可能抢占当前正在运行的进程。
SRT算法评价
优点
既不像FCFS那样偏爱长进程，也不像RR算法那样会产生很多额外的中断（因时间片而产生），从而减少了开销
周转时间方面，SRT比SJF性能要好，短作业可以立即被选择执行
问题
需要估计预计的服务时间
存在进程饥饿现象
必须记录进程的已服务时间
响应比高者优先（HRRT）
当前进程执行完毕或需要阻塞时，选择就绪队列中响应比最高的进程投入执行
HRRN算法评价
实质上是一种动态优先权调度算法
是FCFS和SJF的结合，既照顾了短进程，又考虑了作业到达的先后次序，不会使长进程长期得不到服务
利用该算法时，每次调度之前，都须先做响应比的计算，会增加系统开销，且难以准确计算
采用了“惩罚长进程” 的思想
根据进程执行历史，调度基于抢占原则（按时间片）
采用动态优先级机制，可以获得较好的性能
Multilevel Queues，采用多级队列区别对待的方法“惩罚长进程”
多个独立的、优先级不同的就绪队列
各队列区别对待，即优先调度优先级高的队列
进程执行过程中可降级，即在整个生命周期内可能位于不同队列。
基于时间片轮转的反馈调度算法
评价：多级反馈队列调度算法具有较好的性能，能较好地满足各种类型用户的需要。
有利于终端型作业用户：\t常为短作业，能在第一队列所规定的时间片内完，对短作业用户有利
问题：当不断有新进程到来时，长进程可能饥饿
实时系统与实时调度
实时系统
系统能够及时（即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。
对于实时系统而言，系统的正确性不仅取决于计算的结果，而且还依赖于产生结果的时间。
实时任务：具有及时性要求的、常常被重复执行的特定进程，在实时系统中习惯称为任务。
截止时间
硬实时任务
软实时任务
周期性
周期性实时任务
非周期性实时任务
开始截止时间：任务在某时间以前，必须开始执行
完成截止时间： 任务在某时间以前必须完成
实时操作系统特点
可确定性：任务按照固定的、预先确定的时间或时间间隔进行
可响应性：关注系统在知道中断后为中断提供服务的的时间
用户控制：用户能够区分软、硬实时任务，并控制任务优先级
可靠性：实时响应和控制事件，保障性能
失效弱化：系统具有稳定性，当不能满足所有任务的实时性时，首先满足重要的、优先级高的任务的期限，减少系统故障
实时进程的调度方式
基于时间片的轮转抢占(剥夺)式调度
实时进程按时间片轮转的方式执行，到达的实时进程放在就绪队列尾
新到进程的时间片到时，调度
响应时间一般为秒级
广泛用于分时系统及一般实时处理系统
基于优先级的非抢占式调度
实时进程按优先级、非抢占方式执行，新到的实时进程放在就绪队列首部
当前进程阻塞或完成时，立即调度新到进程
响应时间一般在数百毫秒至数秒范围
多用于多道批处理系统及不太严格的实时系统
基于优先级的抢占点抢占调度
实时进程按优先级、抢占方式执行
当下一个剥夺点(时钟中断)到来时，立即占用CPU
响应时间一般在几毫秒至几十毫秒
用于一般实时系统
立即抢占式调度
响应时间为微秒至毫秒级
可用于苛刻的实时系统
实时调度的方法分类
静态表驱动调度法
用于调度周期性实时任务
按照任务周期到达的时间、执行时间、完成截止时间以及任务的优先级，制订调度表，调度实时任务
最早截止时间优先（EDF）调度算法即属于此类。
此类算法不灵活，任何任务的调度申请改动都会引起调度表的修改。
静态优先级抢占调度法
此类算法多用于非实时多道程序系统
优先级的确定方法很多，例如在分时系统中，可以对I/O 密集型和CPU密集型的进程赋予不同的优先级。
实时系统中一般根据对任务的限定时间赋予优先级，例如速度单调算法（RM）即是为实时任务赋予静态优先级。
基于动态规划的调度法
当实时任务到达以后，系统为新到达的任务和正在执行的任务动态创建一张调度表。
在当前执行进程不会错过其截止时间的条件下，如果也能使新到达任务在截止时间内完成，则立即调度执行新任务。
动态尽力调度法
实现简单，广泛用于非周期性实时任务调度
当任务到达时，系统根据其属性赋予优先级，优先级高的先调度。例如最早截止时间优先EDF调度算法就采用了这种方法。这种算法总是尽最大努力尽早调度紧迫任务，因此称为“最大努力调度算法”
缺点在于，当任务完成，或截止时间到达时，很难知道该任务是否满足其约束时间
限期（deadline）调度
调度所需的信息
就绪时间
启动的限期（starting deadline）
完成的限期（completion deadline）
处理的时间：任务执行到完成的时间
资源需求：任务执行过程中所需的资源集
优先级：度量任务的相对重要性
子任务结构：一个任务可分解为一个必须执行的子任务和一个可选执行子任务，前者有硬截止时间（hard deadline）
限期调度需要考虑的两个问题
下次调度哪个任务
采用什么抢占方式？
对于启动限期明确的任务，采用非抢占方式
对于具有完成限期的实时系统，采用抢占策略
针对具有完成限期的周期性实时任务
此类任务是周期性的，可预测的
采用最早截止时间优先调度算法EDF
根据任务的截止时间来确定任务的优先级
针对具有开始限期的非周期性实时任务
此类任务是非周期性的，不可预测的，若采用EDF算法，存在危险性。
若在任务就绪前，预先知道任务的开始截止时间，则可以采用允许CPU空闲的EDF调度算法
允许CPU空闲的EDF调度算法
优先调度截止时间最早的合格任务，并让该任务运行完毕
合格任务可以是还未就绪，但是事先知道其开始截止时间任务。
尽管CPU的利用率不高，但这种调度算法可以保证系统中的任务都能按要求完成。
速率单调调度算法RMS
任务速率：任务周期（以秒计）的倒数，以赫兹为单位
优先级的确定
任务周期越短，优先级越高
优先级函数是任务速度的单调递增的函数
系统按任务优先级的高低进行调度
优先级反转（优先级倒置、优先级逆转、优先级翻转）
是一种不希望发生的任务调度状态。在该种状态下，一个高优先级任务间接被一个低优先级任务所抢先，使得两个任务的相对优先级被倒置。
可发生于任何基于优先级的可抢占的调度方案中
已在火星探路者中发生
同步
相关的关键概念
临界资源：一次仅允许一个进程访问的资源为临界资源
临界区：把在每个进程中访问临界资源的那段代码称为临界区。
死锁：两个或两个以上的进程相互等待导致都不能执行
互斥：当一个进程在临界区访问临界资源时，其他进程不能进入该临界区访问共享资源
竞争：多个进程读写一个共享数据时依赖它们执行的相对时间
饥饿：一个进程已经完全具备了执行的条件，但是得不到CPU资源
忙等现象：当一个进程等待进入临界区时，它会继续消耗处理器的时间
原子操作：由一个或多个指令序列实现的动作或函数，对外不可见，一组指令要么都执行，要么都不执行。
活锁：两个或两个以上的进程为响应其他进程而持续改变自己状态，但是不做有用工作的情形
同步：多个进程在执行次序上的协调，相互等待消息
多道程序设计为什么需要同步？
进程是计算机中的独立个体，且具有异步性、并发性
资源是计算机中的稀缺个体，需共享，如CPU、内存、I/O设备
进程之间可能需要协作完成任务
进程间的交互方式
进程间的竞争资源
进程间不知道彼此的存在
进程竞争使用同一资源时，它们之间会发生冲突
这类资源如：I/O设备、存储器、处理器、时钟
进程竞争资源时，并发控制面临三个问题：互斥、死锁、饥饿
进程间通过共享合作
多个进程可能共享一个变量、共享文件或数据库
一个进程的结果可能取决于从另一个进程获得的信息
进程知道其他进程也可能共享同一个数据，因此必须合作
进程通过共享合作时，并发控制面临四个问题：互斥、死锁、饥饿、数据一致性
进程间通过通信合作
进程间通过通信完成同步和协调彼此活动
通信可由各种类型的消息组成，发送或接收消息的原语由操作系统或程序设计语言提供
不涉及对共享资源的访问
进程通过通信合作时，并发控制面临两个问题：死锁、饥饿
互斥
互斥的要求
空闲让进：如临界区空闲，则有进程申请就立即进入。
忙则等待：每次只允许一个进程处于临界区。
有限等待：保证进程在有限时间内能进入临界区(不会死锁或饥饿)。
让权等待：进程在临界区不能长时间阻塞等待某事件。
软件方法
介绍
通过在进入区设置和检查一些标志来判断是否有进程在临界区；
若已有进程在临界区，则在进入区通过循环检查进行等待
进程离开临界区后在退出区修改标志
无漏洞可用算法
软件方法——Peterson互斥算法
软件方法—Dekker互斥算法
软件方法的评价
软件方法始终不能解决“忙等”现象，降低系统效率
采用软件方法实现进程互斥使用临界资源比较困难
算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。
硬件方法
严格轮换：每个进程每次都从头执行到尾
屏蔽中断：刚刚进入临界区时就屏蔽中断，刚要出临界区就打开中断
用于单处理器系统
通过禁用中断，避免进程切换，实现互斥访问
缺点
执行效率明显下降
无法工作在多处理器环境
专用机器指令
在多处理器环境中，几个处理器共享访问公共主存；
处理器表现出一种对等关系，不存在主／从关系；
处理器之间没有支持互斥的中断机制；
处理器的设计者提出了一些机器指令，用于保证两个动作的原子性
如在一个周期中对一个存储器单元的读和写；
这些动作在一个指令周期中执行，不会被打断，不会受到其他指令的干扰。
例子
比较和交换指令：compare&swap （compare&exchange）
比较一个内存单元的值和一个测试值，如果相等，则发生交换
Exchange指令：原子性地交换寄存器和内存的值
优点：支持多处理机，简单易证明，支持多临界区
不足：忙等现象，可能死锁，可能饥饿
信号量
信号量实现进程互斥与同步的基本原理
两个或多个进程可以通过传递信号进行合作
迫使进程在某个位置暂时停止执行（阻塞）
直到它收到一个可以“向前推进”的信号（被唤醒）
将实现信号灯作用的变量称为信号量
信号量可视为一个值为整数的变量。具有三个操作
一个信号量可以初始化为非负数
semWait （Wait或P）操作使信号量的值减少1，若值变为负数，则阻塞执行semWait( Wait或P)操作的进程
semSignal（Signal或V）操作使信号量的值增加1，若值小于等于零，则被semWait(Wait或P)阻塞的进程解除阻塞
信号量的实现
semWait 和 semSignal作为原语实现
任意时刻只能有一个进程用semWait 和 semSignal 来操作控制信号量
可基于硬件的方式来保证进程互斥使用semWait 或 semSignal操控信号量
信号量分类
按数据类型分
二元信号量：信号量的值只能是0或1
计数信号量：非二元信号量/一般信号量
按组织方式分
强信号量：进程以FIFO方式从队列里移除
弱信号量：未规定阻塞进程从队列里移除的顺序
经典同步问题
生产者/消费者问题
描述及解决问题
注意
应先申请资源信号量，再申请互斥信号量，顺序不能颠倒
同一进程中的多个signal语句顺序可以颠倒
对于同一个信号量的wait与signal操作，既可以出现在同一个进程中，也可以出现在不同进程中。
对任何信号量的wait与signal操作必须配对。
在进入临界区前必须先执行wait操作，退出临界区后必须执行signal操作
示例
生产者/消费者问题示例1
题目
分析
伪代码
伪代码续
生产者/消费者问题示例2
生产者/消费者问题示例3
生产者/消费者问题4
读者和写者问题
问题描述
多个进程访问一个共享数据区（可为文件、内存空间、寄存器）
其中若干读进程只能读数据，若干写进程只能写数据
为数据库、文件、内存区及一组寄存器等的数据访问问题建立了一个通用模型
三种角色
读进程
写进程
共享数据
三种条件
同时读
互斥写
互斥读写
如何判断一个问题是生产者／消费者问题，还是读者／写者问题
生产者／消费者问题：数据消费后就没有了； 读者／写者问题：数据可多次读。
生产者／消费者问题：消费者彼此互斥； 读者／写者问题：读者可以同时读。
三种解决策略
读者优先
一旦有读者正在读数据，则允许随后的读者进入读数据
只有当全部读者退出，才允许写者进入写数据。
导致写者饥饿
读者优先变量设置
wsem：互斥信号量，用于Writers间互斥，Writers和Readers互斥
readcount：统计同时读数据的Readers个数
x：对变量readcount互斥算术操作
代码示例
注：if不可放在V（x）后，其作用是判断互斥
公平优先
写过程中，若其它读者、写者到来，则按到达顺序处理
公平优先的变量设置
wsem：互斥信号量，用于Writers间互斥，Reader互斥Writers
wrsem：互斥信号量，确定Writer 、Reader请求顺序
写者优先
当至少有一个写者声明想写数据时，则不再允许新的读者进入读数据
解决了写者饥饿问题，但降低了并发程度，系统的并发性能较差
写者优先的变量设置
rsem：互斥信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据。
第一个写者受rsem影响，一旦有第一个写者，后续写者不受rsem其影响。但是读者需要在rsem上排队。
writecount：用于控制rsem信号量
y：对变量writecount互斥算术操作
写者优先的思考
z信号量的作用
在rsem上不允许建造读进程的长队列，否则写进程将不能跳过这个队列.
读者和写者问题示例1
题目：有一座东西方向的独木桥，每次只能有一人通过，且不允许行人在桥上停留。东、西两端各有若干行人在等待过桥。请用P、V操作来实现东西两端行人过桥问题。
分析：多个写者共享数据；行人-写者；桥-共享数据；s：互斥信号量，用于写者互斥
读者和写者问题示例2
题目：有一座东西方向的独木桥，同一方向的行人可连续过桥。当某一方向有行人过桥时，另一方向行人必须等待。桥上没有行人过桥时，任何一端的行人均可上桥。请用P、V操作来实现东西两端人过桥问题。
分析：读者优先问题；行人首先上桥的一方为读者，另一方为写者；桥-共享数据；x：互斥信号量，用于读者互斥写者；countR：统计读者数目（同时在桥上的行人数目）；mutexR：对变量countR互斥算术操作
读者和写者问题示例3
题目：有一座东西方向的独木桥，同一方向的行人可连续过桥。当某一方向有行人过桥时，另一方向行人必须等待。桥上没有行人过桥时，任何一端的行人均可上桥。出于安全考虑，独木桥的最大承重为4人，即同时位于桥上的行人数目不能超过4。请用P、V操作来实现东西两端人过桥问题
分析：读者优先问题；行人首先上桥的一方为读者，另一方为写者；桥-共享数据；x：互斥信号量，用于读者互斥写者；countR：统计读者数目（同一方向要过桥的行人数目）；mutexR：对变量countR互斥算术操作；count: 位于独木桥上的行人数目
理发师睡觉问题
题目：理发店有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。如果没有顾客，则理发师睡觉。当一个顾客到来时，他必须叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等。如果没有空椅子，他就离开。
伪代码示例
理发师睡觉问题的类似问题
哲学家就餐问题
题目：5个哲学家围坐一张餐桌，5只餐叉间隔摆放，思考或进餐，进餐时必须同时拿到两边的餐叉，思考时将餐叉放回原处，两个哲学家不能同时使用同一把叉子，避免死锁和饥饿
资源分级：为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。
资源分级方法一：为餐叉编号；就餐前，先取用编号较低的餐叉，再取用编号较高的餐叉；就餐毕，先放下编号较高的餐叉，再放下编号较低的餐叉。
资源分级方法二：为哲学家编号；奇数号的哲学家必须首先拿左边的餐叉；偶数号的哲学家必须首先拿右边的餐叉。
服务生方法：引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉；最多允许4个哲学家同时进食
管程
管程的引入
管程是一个程序设计语言结构，采用了集中式的进程同步方法，提供了与信号量同样的功能，但更易于控制。
管程的概念(Monitor)
一个管程定义了一个共享数据结构和能为并发进程所执行（在该数据结构上）的一组操作（过程），这组操作能同步进程和改变管程中的数据。
共享数据结构是对系统中共享资源的抽象
对该共享数据结构的操作则定义为一组过程，通过调用这些过程实现对共享资源的申请、释放和其它操作。
管程的组成：局部数据+过程+初始化序列
管程的特点
局部数据变量只能被管程的过程访问，任何外部过程都不能访问
一个过程通过调用管程的一个过程来进入管程
在任何时候，只有一个进程在管程中执行，调用管程的其他任何进程都被阻塞，以等待管程可用。
若由于某种原因，一个正在管程中执行的进程必须阻塞，该如何处理？
释放管程供其它进程使用
用管程实现进程同步
管程通过使用条件变量提供对进程同步的支持
条件变量包含在管程中，只能在管程中访问
操作条件变量的两个函数
cwait(c)： 调用进程的执行在条件c上阻塞，管程可供其它进程使用。
csignal(c)： 恢复在条件c上阻塞的一个进程，若不存在阻塞进程，则什么都不做。
管程的结构
生产者/消费者问题的管程解决方法
消息传递
进程交互时，需要满足两个基本要求
同步：为实现互斥，进程间需要同步
通信：为实现合作，进程间需要交换信息
消息传递提供了上述两方面的功能
进程以消息的形式给指定的进程（目标）发送信息
进程通过接收原语receive接收消息，接收原语中指明源进程和消息
消息传递问题中的同步
发生进程调用原语时可能的两种情况
阻塞直到消息被目标进程收到
不阻塞
当一个进程调用接受原语时两种可能情况
若消息没有到达，接收者要么阻塞等待；要么放弃接受，继续执行
若消息已经到达，接收者接收消息并继续执行
消息传递的三种同步方式
阻塞发送，阻塞接收
发送者和接受者都阻塞，直到完成消息投递
考虑了进程间的紧密同步
有时被称为会合rendezvous
不阻塞发送，阻塞接收
发送者不阻塞，但是接收者阻塞直到请求的消息到达
最有效的一种组合
允许发送者可以尽快的向目的发送一条或多条消息
例如，如一个服务进程给其他进程提供服务或资源
不阻塞发送，不阻塞接收
不要求任何一方等待
send和receive原语确定目标和原进程的方式有两类
直接寻址
Send原语包含目标进程的标识号
Receive原语有两种处理方式
显式的指明源进程：对于处理并发进程的合作有效
不可能指定源进程：如打印机服务进程，采用隐式寻址，接收到消息时将源地址保存下来
间接寻址
使用消息传递实现互斥
使用消息传递实现生产者/消费者问题
死锁
死锁原理
死锁定义：一组相互竞争系统资源或进行通信的进程间的永久阻塞。
当一组进程中的每个进程都在等待某事件，而只有同组进程中阻塞的其他进程能够促发该事件时，死锁发生
死锁是永久性的，无有效的解决方案
资源的分类
可重用资源
一次仅供一个进程安全使用且不因为使用而耗尽的资源
如处理器、I/O通道、内存外存、设备，以及诸如文件数据库信号量之类的数据结构之类的
可消耗资源
指可被创建（生产）和销毁（消耗）的资源
如中断、信号、消息和I/O缓冲中信息
死锁的条件
互斥（必要条件）：一次只有一个进程可以使用一个资源。
占用且等待（必要条件）：当进程等待其他资源时，继续占有已经分配的资源。
不可抢占（必要条件）：不能强行抢占进程已经占有的资源
循环等待（充分条件）：存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。
注：必要条件是死锁产生的前提，但不一定产生死锁。
死锁的解决：三种方式
死锁预防：防止死锁产生条件的发生
设计一个系统来排除系统发生死锁的可能性
两类方法
间接方法：防止三个必要条件中的任意一个条件发生
直接方法：防止循环等待的发生
四个条件的预防方法及可行性
死锁避免：允许三个必要条件，根据当前资源分配状态来做出资源分配决策，保证不产生死锁
动态检查：在系统运行过程中，检查进程的资源申请，根据检查结果决定是否分配资源。
若分配后系统可能发生死锁，则不予分配（阻塞）
否则予以分配
需要预知资源的请求
死锁避免的两种方法
资源分配拒绝：若一个进程的资源增加请求会导致死锁，则不予分配
银行家算法
Dijkstra算法
设计思想：当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分配这些资源；否则，暂时不分配，阻塞进程
安全状态与不安全状态
安全状态 与 不安全状态的思考
进程启动拒绝：若一个进程请求会导致死锁，则不启动该进程
死锁避免的优点
无须死锁预防中的抢占和回滚进程（释放最初占有的资源）
比起死锁预防，限制少
死锁避免的使用限制
必须事先声明每个进程请求的最大资源
进程必须是独立的，他们执行顺序没有同步要求
分配资源的数量必须是固定的
占有资源时，进程不能退出
死锁检测与解除：不限制资源访问或约束进程行为，而是检测死锁的存在并尝试解除
死锁检测
死锁预防策略很保守
死锁检测则相反
优点：可以尽早发现死锁；实现相对简单
缺点：频繁的检测会耗费处理器大量的时间
死锁检测算法步骤
子主题
死锁检测：从资源分配图化简的角度解决问题
资源分配图的化简
在资源分配图中，找出其全部请求都能满足的进程节点Pi，消去Pi所有的请求边和分配边，使之成为孤立的结点。
重复以上步骤，直至无法化简为止。
资源分配图的化简示例
可完全简化图
能消去图中所有的边，使所有的进程结点都成为孤立结点的资源分配图
当资源分配图是不可完全化简时，存在死锁
解除：检测到死锁后，按照某种可能的策略来解除
第3章 内存管理
基本内存管理
程序的加载与链接
高级语言的源代码转化为进程的3个基本步骤
编译： 由编译程序将用户源代码编译成若个目标模块
链接：由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的加载模块。
加载（装入）：\t由加载程序将加载模块装入内存。
程序的加载
加载的任务
将可加载模块装入内存
地址重定位：将执行文件中的逻辑地址转化为内存物理地址的过程
加载方式分类（地址映射建立方式）
绝对加载方式
程序中的逻辑地址与实际内存地址完全相同：不需对程序和数据的地址进行修改。
在编译时就知道程序将驻留在内存中的具体位置，编译程序产生绝对地址的目标代码
绝对加载方式的优点：实现简单，无须进行逻辑地址到物理地址的变换
绝对加载方式的缺点
程序每次必须装入同一内存区
程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址
不适于多道程序系统
可重定位加载方式（静态重定位）
编译时采用相对地址，即编译器假设是加载到从零开始的内存位置。
逻辑地址与装入内存后的物理地址无直接关系：允许将程序装入与逻辑地址不同的物理内存空间
必须进行重定位，即加载程序根据加载的位置将逻辑地址转换为物理地址
静态重定位技术：地址映射在程序加载时进行，以后不再更改程序地址。
静态重定位加载方式的优点：易实现，无需硬件支持。
静态重定位加载方式的缺点：程序重定位后就不能移动，因而不能重新分配内存，不利于内存的有效利用
运行时加载（动态重定位）方式
程序的地址转换不是在加载时进行，而是在程序运行时动态进行
为使地址转换不影响指令执行速度，运行时动态加载需要硬件支持，即重定位寄存器，用于保存程序在内存中的起始地址。
程序被执行时，通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地址
运行时加载方式的优点
程序不必连续存放在内存中，可分散存储，可移动；
便于共享
有利于紧凑、碎片问题的解决；
主流方式。
运行时加载方式的缺点
需要硬件支持，实现存储管理的软件算法比较复杂
同一地址，可能多次转换。
程序加载方法小结
程序的链接
链接的含义
源程序经过编译后，可得到一组目标模块
链接程序将这组目标模块链接，产生一个包含完整程序和数据模块的加载模块
链接方式（链接的时机）
静态链接
在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块（又称执行模块），以后不再拆开。
静态链接需要解决的两个问题
相对地址的修改：由编译程序产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，在链接成一个加载模块时修改模块的相对地址
变换外部引用地址：将每个模块中所用的外部调用符号也都变换为相对地址
静态链接方式的缺点
不利于代码共享：每个应用都含有目标模块的拷贝
不利于模块的独立升级：每次对某个目标模块的修改升级，都要打开整个加载模块。
可能链接一些不会执行的模块，浪费存储空间和处理机时间。
加载时动态连接
待加载的模块在加载内存时，如果该模块中有到外部模块的引用，加载程序将查找这些模块并加载内存，并把这些引用修改为相对应用程序模块开始处的相对地址
优点：便于各个模块的独立升级；便于实现模块的共享
缺点：可能链接一些不会执行的模块，浪费存储空间和处理机时间；模块加载后不能移动位置
运行时动态链接
在程序执行中需要某目标模块时，由操作系统去找到该模块并将之加载内存，随后把它链接到调用者模块上。
凡在执行过程中未被用到的目标模块，不会被调入内存和被链接到加载模块上，这样不仅可加快程序的加载过程，而且可节省大量的内存空间
支持分段系统
内存管理的需求
重定位
程序员事先并不知道在某个程序执行期间会有其他哪些程序驻留在内存中
需要把活动进程换入或换出内存，进而使处理器的利用率最大化
进程下次换入时若要放置在与换出前相同的区域，会存在诸多困难
需要将进程重定位到内存的不同区域
进程寻址的需求
操作系统需要知道进程控制信息、栈和入口点位置
处理器需要处理程序内部的内存访问，处理下列指令的地址转换：跳转指令、数据访问指令
地址类型
逻辑地址：与当前数据在内存中的物理分配无关的访问地址，执行前要转换成物理地址
相对地址：逻辑地址的特例，相对于某些已知点的存储单元
物理地址：内存中的实际地址
重定位的硬件支持
基地址寄存器：存放作业的起始地址
界限寄存器：存放作业界限地址
保护
进程以外的其他进程中的程序不能未经授权地访问（进行读操作或写操作）该进程的内存单
程序在内存中的位置不可预测
需要既支持重定位也支持保护的机制
共享
多个进程正在执行同一程序时，允许每个进程访问该程序的同一个副本，要比让每个进程有自己独立的副本更有利。
需要既支持重定位也支持共享的机制
逻辑组织：内存被组织成线性（或一维）地址空间
分段可以满足该需求
程序按模块组织
可以独立编写和编译模块
可以为不同的模块提供不同的保护级别（只读、只执行）
模块可以被多个进程共享，与用户看待问题的方式一致
物理组织
在内存和外存之间完成移动信息的任务应该交给OS而不是程序员，因为：
内存分区
内存管理的主要操作是处理器把程序加载内存中执行内存管理包含虚拟内存的复杂方案基于分段和分页两种基本技术
内存管理技术
固定分区
操作系统占据内存中某些固定部分，用户进程使用其余部分
分区数量固定
每个分区装入一个进程
两种划分方式
分区大小相等
分区大小相等存在问题
程序可能太大而不能放到一个分区中：程序员必须使用覆盖技术设计程序，任何时候程序只有一部分放入内存
内存的利用率非常低
很小的程序也必须占据一个完整分区
内部碎片：由于装入的数据块小于分区大小，分区内部存在空间浪费
分区大小不等
可以缓解分区大小相等的问题，使内部碎片更小
固定分区存在的问题
分区的数量在系统生成阶段已经确定，因而限制了系统活动（未挂起）进程的数量
小作业不能有效地利用分区空间
使用情况：早期IBM OS/MFT
动态分区
分区大小和数量不固定
分配与进程需求完全一致的空闲内存空间
在早期的IBM主机操作系统 OS/MVT 所使用
相关概念
外部碎片
动态分区方法在内存中产生越来越多的碎片
内存利用率下降
紧凑(压缩)
解决外部碎片问题的技术
操作系统移动进程，使进程占用的空间连续
所有空闲空间连成一片
紧凑费时，浪费处理器时间
动态分区分配算法
首次匹配（First Fit）
思想：从头开始扫描内存，选择大小足够的第一个可用块
实现：要求空闲分区以地址递增的顺序链接，从链首开始查找
简单，快速
为大作业分配大的内存空间创造条件
内存前端出现很多小的空闲分区，且每次查找都要经过这些分区
循环匹配/下次匹配(Next Fit)
思想：从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块
实现：空闲分区按地址从低到高排列（链接）
比首次匹配性能差，常常在内存末尾分配空间，导致空闲的分区分布均匀
缺少大的空闲块，需要更多次数紧凑
最佳匹配(Best Fit)
思想：选择空间大小与需求最接近的空闲块分配
实现：空闲分区按容量大小从小到大链接
产生的外部碎片都很小
内存中形成很多小到无法满足任何分配需求的块
需要更频繁的进行内存压缩（紧凑）
最坏（差）匹配(Worst Fit)
思想：选择满足需求的最大的空闲分区分配
实现：空闲分区按容量从大到小链接
每次分配留下的空闲空间较大，便于再次利用
大的空间不容易保留，对大作业不利
分区分配算法示例
伙伴系统
伙伴系统的引入
固定分区方案限制了活跃进程的数量。并且，如果分区大小与进程大小不匹配，则内存空间的利用率非常低。
动态分区方案维护复杂，并且引入了紧凑的额外开销
固定分区和动态分区的折中方案：伙伴系统
具体方法
最初，可用于分配的空间被视为一个大小为2U的块
2^L = 分配的最小块的大小
2^U =分配的最大块的大小
通常， 2^U是内存中整个可分配空间的大小
伙伴系统评价
较为合理的折中方案，一定程度上克服了固定分区和动态分区的缺陷
是并行程序分配和释放的一种有效方案
UNIX内核存储分配中使用了一种经过改进的伙伴系统
分页
基础概念
将内存划分成大小固定、相等的块，且块相对较小
进程也划分成同样大小的块
页：进程中的块
页框：内存中的块
将进程的页装入内存的页框
页表
操作系统为每个进程维护一个页表
包括进程中每个页对应的页框位置
处理器需要知道如何访问当前进程的页表
处理器使用页表来生成一个物理地址
分页的逻辑地址 = 页号 + 页内偏移
32位机的分页存储系统逻辑地址结构示意图
页号与页内地址的计算
对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式：
分页的逻辑地址到物理地址的转换
根据逻辑地址页号查页表，得到对应的页框号，放入物理地址高位部分
逻辑地址页内偏移 = 物理地址页内偏移
页表的存储
页表存放在内存
PCB保存有页表的起始地址
页表寄存器存放当前运行进程的页表的起始地址
普通分页系统地址转换示例
分页存储管理的优点
存在页内碎片，但碎片相对较小，内存利用率较高
实现了离散分配
无外部碎片
分页存储管理的缺点
需要专门的硬件支持，尤其是快表
不支持动态链接，不易实现共享
分段
一个程序可以划分成几个段
段长度可以不等
每个段都从0开始编址，并占用一段连续的地址空间
有最大段长限制
逻辑地址两部分组成：段号、段内偏移量
分段类似动态分区：分段使一个程序可以占据多个分区，且不必连续
消除了内部碎片
对用户和程序员
分页对用户透明，分段对用户可见
给程序员提供了组织程序和数据更方便的手段
程序员或编译器将程序和数据划分到不同的段
为实现模块化程序设计，程序和数据可能会进一步被划分成多个段
不便：程序员或编译器需要清楚最大段长的限制
分段的逻辑地址结构
逻辑地址=段号+段内偏移
段表：记录逻辑段和物理段的对应情况
段的大小不等，导致逻辑地址和物理地址间没有简单的对应关系
地址转换需要经历以下步骤：
分段存储管理的优点：便于程序模块化设计、便于动态链接、便于保护和共享、无内部碎片
分段存储管理的缺点
地址转换需要硬件的支持——段表寄存器
分段的最大尺寸受到主存可用空间的限制
有外部碎片
分页和分段的比较
虚拟内存管理
虚拟内存的支持条件
要使虚存比较实用且有效，两方面因素
分页或分段的硬件支持
操作系统必须有管理页或段在内存和辅存之间移动的软件
虚拟内存术语
虚拟内存：在存储分配机制中， 辅存可被看作主存的一部分来完成寻址。程序使用的地址与内存物理存储的地址不同，程序生成的地址会自动转换为物理地址。虚拟存储的大小受计算机系统寻址机制和可用辅存容量的限制，而不受主存实际大小限制
虚拟地址：在虚拟内存中分配给某一位置的地址，它使得该位置可被访问，就好像是主存的一部分那样。有时也称为逻辑地址
虚拟地址空间：分配给进程的虚拟存储
地址空间：用于某进程的内存地址范围
实地址：内存中存储位置的地址
硬件和控制结构
分页和分段内存管理的两个基本特征
进程中所有内存访问都是逻辑地址，这些逻辑地址会在运行时动态地转换为物理地址。
一个进程可划分为许多块（页和段），在执行过程中，这些块不需要连续地位于内存中
若上述特征存在，则在一个进程执行过程中，该进程不需要所有页或所有段都在内存中。
进程的执行过程
操作系统仅读取包含程序开始处的一个或几个块进入内存
任意时刻，进程驻留在内存的部分——驻留集
访问一个不在内存中的逻辑地址时（称为内存失效），产生一个中断
操作系统把被中断的进程置为阻塞状态
操作系统把该进程中包含引发内存失效的部分读入内存
操作系统产生一个磁盘I/O读请求
在执行磁盘 I/O期间，操作系统调度另外一个进程运行
磁盘I/O完成后产生中断，操作系统将相应的进程置于就绪状态
提高系统资源利用率的方法
内存中保留多个进程
每个进程仅装入了部分块
任何时刻内存中的进程至少有一个处于就绪状态
提高了处理器的利用率
进程可以比内存的全部空间还大
基于分页和分段的技术，操作系统和硬件只加载程序的一部分
程序员面对的是一个巨大内存，大小与磁盘存储器相关
实存与虚存
实存储器（实存）：主存，实际的物理内存
虚拟内存（虚存）
通常分配在磁盘上
更有效地支持并发，并能减轻用户对内存的严格限制
使用和不使用虚存技术下分页和分段的特点
局部性和虚拟内存
进程只有部分块在内存，这样可在内存中保留更多进程
当内存空间几乎被进程块占据时，每读取一块，必须把另一块换出，如果出现抖动
抖动：即将要用到的块被换出，系统又得很快将它取回，导致页面被频繁地换入换出，缺页率急剧增加
虚拟内存通常与使用分页的系统联系在一起
每个进程都有自己的页表：分页的虚存方案中，页表项变得更复杂
首个使用分页实现虚拟的Atlas计算机
页表项
存在位P：表明对应的页是否在内存
页框号：若页在内存，则有对应的页框号
修改为M：表明相应页上次装入内存到现在是否修改过
是，换出时要更新辅存上对应页
否，换出时不必更新
页表项结构
分页系统中的地址转换
页表位于内存
进程运行时，一个寄存器保存页表的起始地址
虚拟地址的页号用于检索页表，查找对应页框号
页框号与虚拟地址的偏移量结合起来形成物理地址
虚存分页系统地址转换示例
解答
庞大的页表组织
每个进程一个页表，如果进程的逻辑地址空间大，则页表庞大
例如，在Vax机中，每个进程虚存空间可达2^31=2GB，若每个页大小2^9=512字节，则需要2^22个页表项
大多数虚拟内存方案在虚存而非内存中保存页表
页表和其他页一样服从分页管理
进程运行时，它的页表至少一部分在内存，这部分包含正在运行页的页表项
庞大页表的离散存储解决方案——多级页表
两级页表
将页表进行分页，典型情况下，每页大小最大限制与进程分页大小一致，如Pentium处理器
建立页目录，每项指向一页页表
如果页目录长度为X，一个页表的包含的页表项数为Y，则一个进程可以有XY页。
32位地址的两级页表
页尺寸4KB（2^12），4G(2^32)的虚拟地址空间(用户地址空间)由2^20页组成
每个页表项4字节，页表大小总共需要4MB（2^22B）
巨大页表空间需2^10页存储，因此可保留在虚存中，并建立根页表来索引
根页表包含2^10个页表项，占用4KB内存
4KB根页表、4MB用户页表、4GB用户地址空间
两级分页的逻辑地址结构
两级分页中的地址转换
虚拟地址（逻辑地址）结构中分离出根页表号
检索根页表，查找关于用户页的页表项
如果不在内存，产生一次缺页中断
若在内存，用虚拟地址中间页号（如前例虚拟地址中间10位）检索用户页表，查找对应的页表项
得到页框号，和页内偏移量一起形成物理地址
二级页表示例
二级页表示例1
二级页表示例2
32位逻辑地址空间、4KB页面、4B页表项、求逻辑地址4197721的物理地址？
多级页表
对于某些机器，二级页表也可能非常大
采用多级页表，对外层页表再进行分页，如三级页表
建立多级页表
会增加额外的存储空间
页表的级数越多，地址转换过程越复杂，转换的速度也越慢。
倒置页表（倒排页表）
虚拟地址的页号部分使用一个简单的散列函数映射到散列表中
无论有多少进程、支持多少虚拟页，页表都只需要实存中的一个固定部分
页表结构称为“倒排”的原因是，它使用页框号而非虚拟页号来索引页表项
转换检测缓冲区TLB( 快表)
快表的引入
每次虚存访问都可能会引起两次物理地址访问
一次取相应的页表项
另一次取需要的数据
为了克服这个问题，大多数虚拟内存方案都为页表项使用了一个特殊的高速缓存，称为转换检测缓冲区TLB（快表）
TLB包含最近用过的页表项
具有快表的地址转换流程
给定一个虚拟地址，处理器首先检查TLB
若命中：即页表项在TLB中，检索页框号形成物理地址
若未命中：即页表项不在TLB中，检索进程页表，查找相应页表项
若“存在位”已置位，页位于内存，用页框号+偏移量形成物理地址
若“存在位”未置位，页不在内存，产生缺页中断，装入所需页，更新页表
页表项的直接查找和关联查找(即TLB查找)
TLB包含整个页表中的部分表项，因此不能简单地把页号编入TLB的索引
TLB中的项必须包括页号和完整的页表项
处理器的硬件机制允许同时查询许多TLB页，以确定是否存在匹配的页号
TLB操作和内存高速缓存（Cache）操作
页表项可能在TLB中，也可能在内存或磁盘中
被访问的字可能在高速缓存中，也可能在内存或磁盘中
页尺寸
页的大小的影响
页越小，内部碎片的总量越少
每个进程需要的页的数量越多
页数量越多，进程的页表越大
对于多道程序设计环境中的大程序，这意味着活动进程有一部分页表在虚存而非内存，则一次内存访问可能产生两次缺页中断
一次读取所需页表
一次读取进程页
基于大多数辅存设备的物理特性，希望页尺寸比较大，从而实现更有效的数据传输
缺页率：发生缺页的次数与总访问次数的比值。
缺页率与页尺寸的关系
页尺寸很小时，缺页率低
页尺寸增加时，缺页率增加
页尺寸较大时，缺页率下降
缺页率与分配页框数的关系
对固定的页尺寸，当分配给进程的页框数增加时，缺页率下降
允许程序员把内存视作由多个地址空间或段组成
段大小不等，可以动态变化
内存访问时：段号+段内偏移量
分段优点
简化了对不断增长的数据结构的处理
允许程序独立地改变或重新编译
有助于进程间的共享
有助于保护
段的组织：每个进程一个段表，每个段表项包括
存在位P，标识相应的段是否位于内存
是，段表项还包括段基址：相应段在内存中的起始地址段长度
修改位M，标识相应的段是否已被修改
是，换出时需要写回辅存
否，换出时不需写回
其他控制位，如用于保护和共享
段表项结构
分段系统中的地址转换
逻辑地址=段号+段内偏移量，寄存器存储段表地址
根据段表地址和段号查找段表，找到相应段在内存中的基地址
得到物理地址=基地址+段内偏移量
段页式
段页式的逻辑地址
用户地址空间被程序员划分成若干段，每段划分成若干页
程序员的角度：逻辑地址 = 段号+段内偏移量
系统的角度：段内偏移量 = 页号+页内偏移量
段表和页表
每个进程一个段表
每个段一个页表
段表项：含段长和对应页表的起始地址
页表项：含页框号、存在位P、修改位M等
段页式结构
段页式的地址转换
虚拟地址（逻辑地址） = 段号 + 页号 + 偏移量，寄存器存放段表起始地址
根据段表起始地址和段号查找段表，得到对应段的页表起始地址
根据页表起始地址和页号查找页表，得到页框号
页框号和偏移量构成物理地址
在段页式系统中，为了获得一条指令或数据，至少需访问几次内存？
第一次，访问段表，从中获得该段的页表首址；
第二次，访问页表，从中取出逻辑地址指定的页面所在的页框号，并将该页框号和页内偏移量相加，形成物理地址；
第三次，根据物理地址，取出对应存储单元的指令或数据。
保护和共享
分段有助于实现保护和共享机制
保护：每个段都包括一个长度和一个基地址，可以控制非法访问
共享：一个段可以在多个进程的段表中被引用，实现共享
分页中的共享：假定每个页面4KB，160KB的共享代码需要40个页面，每个进程需要40个页表项来存储相应信息
分段中的共享：共享部分作为一个段，每个进程仅需一个段表项来存放共享段信息。
分段有助于实现共享示例
操作系统软件
内存管理设计的三个基本选择
是否使用虚拟技术
使用分页还是分段，或二者同用
为各种存储管理特征采用的算法
属于操作系统软件领域的问题，是本节的主题
为实现虚拟内存，操作系统需要考虑的策略（软件方面）
读取策略：决定某页何时进入内存
请求调页
仅在引用页面时，才把相应的页面调入内存
进程首次启动时，会发生很多缺页中断
局部性原则表明，大多数将来访问的页面都是最近读取的页面，一段时间后，缺页中断会降低到很低的水平。
预调页
额外读取所缺页面以外的页面
考虑大多数辅助储设备的特性：寻道、旋转延迟等
若进程的页面连续存储在辅存中，则一次读取多个页面会更有效
如果额外读取的页面未使用，则低效
放置策略
确定进程驻留在内存中的位置
分段系统中的重要设计内容，如首次匹配、循环匹配等
分页或段内分页是无关紧要的，因为硬件以相同的效率执行地址转换功能
对于非一致存储访问，需要自动放置策略
页面置换涉及的问题：具体淘汰哪个页面用以置换
置换策略
读取新页时，如何选择内存中要淘汰的页面
目标：最近最不可能访问的页面
置换策略越精细，实现它的硬件和软件开销就越大
页框锁定
当页框被锁定时，当前存储在该页框中的页面不能被置换
操作系统内核和重要的数据结构保存在锁定的页框中
操作系统内核和重要的数据结构保存在锁定的页框中
通过将锁定位与每个页框相关联来实现锁定
评价置换算法的重要指标：缺页率——给定时间内，发生缺页的次数与总访问页框次数的比值。
几种基本的置换算法
最佳(OPT)
置换下次访问距当前时间最长的页面
理想算法，缺页率最少
最近最少使用（LRU）
置换内存中最长时间未引用的页面
根据局部性原理，这也是最近最不可能访问的页面
难以实施
每页添加最近访问时间戳——开销大
建立链表——开销大
先进先出 (FIFO)
将分配给进程的页框视为循环缓冲区
页面以循环方式删除——简单的置换策略
置换驻留在内存中时间最长的页面
时钟 (CLOCK)
每个页框关联一个使用位
当页面首次加载到内存中或被引用时，使用位设置为1
用于置换的候选页框集视作一个循环缓冲区
发生缺页中断时
重复上述过程。
注意：命中时表针不移动
几种置换算法比较（固定分配，局部置换）
改进的Clock算法
在Clock算法基础上，优先置换最近未访问、未修改页面
每个页框处于下列情形之一（u:访问位，m:修改位）
算法流程
3. 若第2步失败，则再次重新扫描，重复第1步，并在必要时重复第2步。
改进型时钟置换算法实现简单，性能比较理想，被广泛采用。
页缓冲
置换的页，如果要写回辅存，代价较大
在内存中采用页缓冲，提高了分页性能，并允许使用更简单的页面替换策略。
置换的页面
未修改，放入空闲页链表尾部
已修改，放入修改页链表尾部
置换策略和高速缓存大小
对于较大的高速缓存，替换页会对性能产生影响
如果选择替换的页在高速缓存中，则该高速缓存块及内存中所对应的页将失效
在使用页缓冲的系统中，可以使用页缓冲区中的页放置策略来提高高速缓存性能
大多数操作系统通过从页缓冲区中选择任意页框来放置高速缓存中需置换的页
驻留集管理
页框分配，即给每个活动进行分配多少个页框
分配给每个进程的内存越小，可以驻留在内存中的进程越多
若一个进程在内存中的页面少，则缺页率相对较高
给进程分配的页框数超出一定大小后，由于局部性原理，缺页率下降到稳定水平
置换范围，即计划置换的页集局限于产生缺页的进程本身，还是内存内的所有进程
固定分配
在内存中为进程提供固定数量的页框
发生缺页时，必须替换该进程的其中一个页面
可变分配
允许分配给进程的页框数在进程的生命周期内变化
置换范围
置换策略的作用范围分为全局和局部两类。
两种类型的策略的实施都是在没有空闲页框时由缺页中断激活。
局部置换：仅在产生缺页中断的进程的驻留页中选择置换对象
全局置换：在整个内存中选择置换对象，只要不是锁定的页，都可以作为候选页
置换与分配的关系
固定分配，局部置换
需要事先确定分配给一个进程的页框数量
如果给进程分配的数量太小，将会产生较高的缺页率
注：如果分配的页框数太多，内存中只能有较少的程序
增加了处理器的空闲时间
增加了花在交换上的时间
可变分配，全局置换
最容易实现的方法，在很多操作系统里采用
操作系统维护一个空闲页框列表
当缺页中断发生时，一个空闲页框分配给缺页的进程
如果没有空闲页框，操作系统必须选择一个内存中的页框（没有锁定，没有被内核占用）作为置换对象
如果选择置换对象不当，将容易再次产生缺页中断，使用页缓冲可以缓解这个问题。
可变分配，局部置换
当一个新进程装入内存时，分配一定数量的页框作为它的驻留集
当缺页中断发生时，从进程驻留集中选择一页用于置换
不时重新评估进程的页框分配情况，增加或减少分配的页框，以提高整体性能
可变分配，局部置换的关键要素
决定驻留集大小的原则
驻留集大小变化的时机
驻留集管理示例示例
解答续
有效访问时间
平均访问时间（平均有效访问时间）
若缺页率为p，内存的访问时间为ma，发生缺页时的访问时间为da，则平均访问时间为(1-p)*ma+p*da
发生缺页时访问时间的构成
缺页中断服务时间
页面写出时间（若需置换）
页面调入时间——20ms（寻道时间+旋转时间+数据传送时间）
重新访问内存指令时间
注：由于ma很小（<10ns），因此很低的缺页率也会导致很大的平均访问时间。
有效访问时间示例
有效访问时间示例1
有效访问时间示例2题目
有效访问时间示例2解答
有效访问时间示例2解答续
工作集
对于固定的Δ ，工作集大小随时间变化的情况：稳定阶段和快速变化阶段交替出现
工作集策略
根据工作集来决定驻留集的大小
周期性的从驻留集中移去不在工作集中的页（近似LRU）
只有驻留集包含工作集时，才执行进程
工作集策略实际难以应用
工作集大小随时间变化
给每个进程测量工作集不现实， Δ最优值未知
近似工作集策略的应用(代表性算法PFF，VSWS)
用缺页率指导驻留集
缺页率低于某个阈值，减小驻留集
缺页率超过某个阈值，增加驻留集
注：驻留集包含工作集（驻留集中有未工作的进程）缺页率低：分配页框足够多（反之亦然）
清除策略
加载控制
决定驻留在内存中的进程的数量
对于有效的内存管理来讲非常重要
内存驻留的进程太少，当所有进程阻塞时，大量时间花在交换上。
内存驻留的进程太多会导致抖动
L=S准则
发生缺页的平均时间L等于处理缺页故障的平均时间S，此时处理器的利用率最大
监测Clock算法中指针扫描的速度
速度低，缺页率低，增加多道程序度
速度高，缺页率高或多道程序度高，降低多道程序度
控制多道程序度
需挂起一个或多个驻留进程
选择哪些进程挂起
最低优先级进程
缺页中断的进程
最后被激活的进程
具有最小驻留集的进程
最大空间的进程
具有最大剩余执行时间的进程
第一章 概述
操作系统的含义及目标
操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。
操作系统的作用
作为用户/计算机接口的操作系统
作为资源管理器的操作系统
内存管理、处理机管理、作业管理、I/O设备管理、文件管理
操作系统的发展及主要类型
操作系统的基本类型及其特征
串行处理
简单批处理系统
多道批处理系统
在简单批处理系统，处理器必须等待I / O指令完成才能继续处理
引入多道程序设计技术，当一个作业需要等待I / O时，处理器可以切换到另一个作业
多道程序设计技术可以显著提高系统设备利用率
分时系统
实时系统
批处理系统多道程序设计与分时的比较
操作系统的主要成就
操作系统的基本特征
并发性（并发基于进程）
虚拟性
异步性
操作系统的体系结构
无结构操作系统
模块化结构
分层式结构
微内核
现代操作系统的特征
多线程
对称多处理
分布式的操作系统
面向对象的设计
第4章 I/O管理与磁盘调度
I/O设备
计算机系统中参与I/O的设备大致可分为三类
人可读
适用于计算机和用户之间的交互
如打印机，终端（显示器、 键盘和鼠标等）
机器可读
适用于与电子设备通信
如磁盘驱动器、USB密钥、传感器和控制器等
通信
适用于远程设备通信
如调制解调器、网卡等
I/O设备的差异
数据传输速率
可能会相差几个数量级
应用
设备用途对操作系统及应用软件和策略都有影响
控制l的复杂性
不同设备控制接口复杂性不一样，这些差异对操作系统的影响，被控制该设 备的I/O模块的复杂性过滤
传输单元
数据可按字节、字节流、块等单元传输
数据表示
不同设备采用不同的数据编码方式
错误条件
错误的性质、报告错误的方式、错误的后果以及响应范围都不一样
I/O控制方式
I/O功能的三种控制方式
程序 I/O方式（可编程I/O方式，忙—等方式）
CPU代表进程给I/O模块发送I/O命令
该进程进入忙等待，等待操作完成，才可以继续执行。
中断驱动I/O方式
如果I/O指令是非阻塞的，则继续执行后续指令
如果I/O指令是阻塞的，当前进程阻塞，调度其他进程。
每次传输一个数据即产生中断
直接存储器访问(DMA)方式
DMA模块控制内存和I/O模块之间的数据交换
处理器给DMA模块发送请求，整块数据传送结束，才中断处理器
直接存储器访问（DMA）工作流程
DMA与中断驱动I/O方式比较
中断频率
中断驱动I/O：每次传输一个数据即产生中断。
DMA：一块数据全部传送结束时才中断CPU
数据传输
中断驱动I/O：数据传送在中断处理时由CPU控制完成
DMA：数据传送在DMA控制器的控制下完成
DMA：块设备，如磁盘
中断驱动I/O：字符设备，如键盘、鼠标
三种I/O方式小结
通道控制方式
I/O通道控制方式
在有的大、中型计算机系统中，还配置了I/O通道或I/O处理机。
一个设备可以连接到多个控制器上，而一个控制器又连接到多个通道上。
这种连接方式可以在不增加成本的基础上，增加设备到主机的通路。
I/O通道与DMA比较
DMA：CPU每发出一条I/O指令，以一个数据块为单位完成数据读写。CPU控制传输方向、数据大小、数据在内存的位置。
I/O通道：是 DMA 方式的发展，有自己的I/O 指令集，通过执行通道程序，与设备控制器共同实现对I/O设备的控制
以一组数据块为单位完成数据的读(或写)控制。
通道控制传输方向、数据大小、数据在内存的位置。
通道可实现 CPU、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。
I/O功能的发展
操作系统的设计问题
I/O的设计目标
效率
I/O设计的主要任务
I/O 操作通常是计算机系统的瓶颈
与内存和处理器相比，大多数I/O设备的速度都很低
最受关注的是磁盘I/O
通用性
用一种统一的方式处理所有设备
处理器看待I/O设备的方式要统一；操作系统管理I/O设备和I/O 操作的方式要统一
设备的多样性使得实现通用性较困难
因此使用层次化的、模块化的方法设计I/O功能
层次化的设计
操作系统的功能可以根据复杂性、特征时间尺度和层次的抽象来分开
具体可以采用层次划分的方式来组织操作系统的功能
每一层执行相关的子功能
分层定义，使得某层的功能变化不影响其他层次
I/O功能组织模型
逻辑I/O：把设备当作逻辑资源处理，不关心控制设备的细节。
设备I/O：请求的操作和数据被转换成对应的I/O指令、通道指令和控制器指令，并可以使用缓冲提高效率。
调度和控制：与硬件真正发生交互的软件层。处理中断，收集和报告I/O状态。
设备独立性/设备无关性
应用程序独立于具体使用的物理设备
逻辑I/O模块允许应用程序使用逻辑设备名（设备标识符）及简单的设备操作命令与设备打交道
逻辑设备表：记录逻辑设备到物理设备的映射
设备I/O模块将逻辑I/O的请求和操作转换成对相应物理设备的I/O访问控制。
I/O功能组织的代表性结构 ——针对某个通信设备
逻辑I/O模块被通信架构替代
通信架构本身也包含许多层
I/O功能组织的代表性结构——文件系统
逻辑I/O具体包含了三层
目录管理：符号文件名被转换成标识符，通过该标识符可以访问文件描述符表或索引表
文件系统：处理文件的逻辑结构和用户指定的操作，如打开、关闭、读写等
物理组织：基于辅存设备的物理磁道和扇区结构，对文件的逻辑访问转换成对辅存物理地址的访问
I/O缓冲
假设从磁盘读入数据，每次读一块（512字节），没有缓冲时
对磁盘单元发送一个I/O命令，并等待数据完成，进程可以忙等（低效），也可以被暂停等待中断
程序被阻塞，需要等待较慢的I/O
这种I/O操作干扰了操作系统的交换决策：进程不能全部换出，读入数据的区域需要驻留内存
缓冲引入
在输入请求发出前开始输入传送
在输出请求发出后一段时间后才开始执行输出传送
缓冲
设备分类
面向块的设备
信息保存在块中，块的大小固定
一次传送一个块
通过块号访问数据
代表设备：磁盘、USB卡
面向流的设备
以字节流的方式输入/输出数据
没有块的结构
代表设备：终端、打印机、通信端口、鼠标及其他大多数非辅存设备
缓冲类型
无缓冲：无缓冲时，操作系统之间在需要时访问设备
每块数据的处理时间为：T+C T:传输数据到用户内存的时间，C为计算时间
单缓冲：操作系统在内存中给I/O请求分配一个缓冲区
面向块设备的单缓冲
采用预读/预先输入
期望输入的数据块最终会被使用
输入的数据被放到系统缓冲区中
传送完成时，进程将数据块移到用户空间，并立即请求下一块
相对于没有系统缓冲的情况，预读方式可以提高数据获取速度
可以在读取下一块数据时，处理已经读入的数据
不足
使操作系统的逻辑变得更复杂
操作系统需要记录给每个进程分配的系统缓冲情况区
交换逻辑也受到影响
面向流的单缓冲
每次传送一行
适用于滚动模式的终端（哑终端）
用户每次输入一行，以回车键结束输出时，也是每次输出一行，如行式打印机
每次传送一个字节
适用于表格式的终端
用户每次击键很重要
其他外围设备如传感器、控制器等
双缓冲
使用两个缓冲
进程向一个缓冲区中传送（或取出）数据时，操作系统正在清空（或填充）另一个缓冲区
也称为缓冲交换
循环缓冲
使用两个或多个缓冲区 构成循环缓冲
当希望I/O操作跟上进程执行速度时，使用循环缓冲
缓冲的作用
缓解I/O设备速度与CPU速度不匹配的矛盾
当进程的需求大于I/O设备的服务能力时，进程推进与I/O设备的操作将不能并驾齐驱
进程每处理完一块数据后得停下等待
在多道程序环境中，当存在多种I/O活动和多种进程活动时，缓冲可以提高操作系统效率，提高单个进程的性能
Spooling技术
SPOOLing技术（磁盘中的缓冲)
在磁盘中建立I/O缓冲区，缓和CPU的高速性与I/O设备低速性间的矛盾
在联机(即CPU控制)情况下实现的同时外围操作称为SPOOLing ，或称为假脱机操作；
通过SPOOLing技术便可将一台独占物理I／O设备虚拟为多台逻辑I／O设备，从而允许多个用户共享一台物理I／O设备。
SPOOLing的组成：输入（输出）进程（井、缓冲）
SPOOLing技术的应用
打印机：独占设备。利用SPOOLing技术，将其改造为共享设备，从而提高设备的利用率。
SPOOLing的特点
提高I/O速度： 对低速I/O设备进行的操作，演变为对输入/输出井中数据的存取。
将独占设备改造为共享设备： 实际上并没为任何进程分配设备，而只是在输入井或输出井中为进程分配一个存储区和建立一张I/O请求表。
实现了虚拟设备功能：系统实现了将独占设备变换为若干台对应的逻辑设备的功能。
虚拟设备：通过虚拟技术将一台独占物理设备变换为若干台逻辑设备，供若干个用户(进程)同时使用
磁盘调度
磁盘存储器
磁盘设备可包括一或多个物理盘片，每个磁盘片分一个或两个存储面
每个磁盘面被组织成若干个同心环，这种环称为磁道
每条磁道逻辑上划分成若干个扇区
不同盘面相同的磁道成为柱面
磁盘类型
固定头磁盘： 每条磁道上都有一读/写磁头，速度快，成本高
移动头磁盘： 每一个盘面仅配有一个磁头，结构简单，成本低
磁盘存储器示意图
磁盘性能参数
磁盘I/O操作的细节取决于：计算机系统、操作系统、I/O通道和控制器硬件的特性
读写头的位置
当磁盘驱动器开始工作时，磁盘以一个恒定的速度旋转
为了读或写，磁头定位于指定的磁道和该磁道中指定扇区的开始处。
寻道操作
磁头可移动系统：将磁头移动到指定磁道
磁头固定的系统：机械自动选择合适的磁头
寻道时间Ts：在磁头可移动系统中，将磁头臂移动到指定磁道所需的时间
旋转延迟Tr
磁头定位到指定磁道后，等待磁盘旋转，将待访问的扇区移动到磁头位置所花时间称为旋转延迟。
平均旋转延迟：Tr=1/2r
例
对于一个转速为3600r/m的硬盘而言，其每旋转一周的时间为 16.6ms，其平均旋转延迟为8.3ms。
对于一个转速为300r/m的软盘而言，其每旋转一周的时间为 200ms，其平均旋转延迟为100ms。
传输时间Tt
向磁盘传送或从磁盘传送数据的时间，取决于磁盘的旋转速度
传输时间：Tt=b/rN
T为传输时间，b表示要传送的字节数，r表示旋转速度，N表示一个磁道中的字节数
磁盘访问时间Ta：Ta=Ts+Tr+Tt=Ts+1/2r+b/rN
磁盘访问时间比较例子
磁盘调度策略
磁盘调度策略概要
根据进程请求访问磁盘的先后顺序，处理队列中的访问需求，
公平
大量进程竞争一个磁盘时，性能接近随机调度
优先级Priority (PRI)
调度的控制不属于磁盘管理软件的范畴
目标不是优化磁盘的利用，而是满足操作系统的其他需求
给短的批处理作业和交互式作业赋予较高优先级
提供了较好的交互响应时间
长作业得等待较长的时间
对数据库系统，这类策略性能较差
LIFO后进先出
优先处理新到请求
在事务处理系统中，由于顺序读取文件，利用局部性，优先处理新到的请求，可以减少磁臂移动
大量请求到达导致磁盘忙碌时，会出现先到请求的饥饿
最短服务时间优先/最短寻道时间优先 (SSTF)
选择从磁臂当前位置开始移动最短距离的磁盘I/O请求
总是选择最短寻道时间的请求
SCAN，也称为电梯算法
磁头只沿着一个方向移动
在移动途中满足所有未完成的请求，直到到达移动方向的尽头，或者在这个方向上没有其他请求(此改进称为LOOK算法)，然后掉头，沿反方向扫描
偏爱那些最靠里和最靠外的磁道请求
C-SCAN (Circular SCAN)
限定只朝一个方向扫描
当磁臂沿指定方向扫描到磁盘最后一个磁道时，磁臂返回到反方向末端，再次沿指定方向扫描
改进：磁臂沿指定方向扫描，在这个方向上没有其他请求时，磁臂返回到反方向第一个有请求的磁道，此改进称为C-LOOK算法
N-Step-SCAN
引入
SSTF、SCAN和C-SCAN具有磁头臂黏着现象
当一个或多个进程对同一个磁道有较高访问速度时，磁头臂黏在相应磁道上不移动
为了避免黏着问题，N-Step-SCAN将磁盘访问请求序列分为若干个子队列，每个子队列的长度为N
每次使用SCAN方法处理一个队列
当前队列正在处理时，新到的访问请求必须加到其他队列中
当扫描到最后一个队列，如果队列中的请求数小于N，则下次再扫描
N较大时，性能接近SCAN; N=1时，就是FIFO
FSCAN
使用两个子队列
当扫描开始时，所有请求都放在一个队列中，另一个队列为空
扫描过程中，新到的请求被放到另外一个队列中
当原来队列里的请求处理完毕时，才会处理另一个队列里的请求
RAID
独立磁盘冗余阵列（RAID）的由来
目的：当时CPU效能每年大约增长30～50%，而磁盘只能成长约7%——平衡计算机的运算能力
便宜的磁盘 -〉独立的磁盘组
同时，提出了容错和逻辑数据备份技术
独立磁盘冗余阵列
共有0-6的七个级别
各级别介绍
RAID Level 0
不是真正的 RAID，不提供冗余功能
用户数据和系统数据被视为存储在一个逻辑磁盘，这个逻辑磁盘被划分成多个条带
这些条带被映射到多个物理磁盘中
RAID Level 1
通过简单的镜像来提供冗余功能
写数据时没有因奇偶校验产生的开销
当一个磁盘失效时，可以通过另外一个盘访问数据
写性能比 RAID 0无明显优势
主要的问题是成本问题
RAID Level 2
使用并行访问技术，所有磁盘参与每个I/O请求
条带非常小(通常为一个字节或一个字)
为数据盘中相应位计算错误校验码，校验码通常使用汉明码，保存在多个校验盘相应位中
在可能发生很多磁盘错误的环境中，RAID2是一个有效选择
RAID Level 3
不管磁盘阵列有多大，只需要一个冗余盘
采用奇偶校验，为所有盘中同一位的集合计算奇偶校验位
采用了并行访问技术，所有磁盘参与每个I/O请求，数据分布在较小的条带中
可以达到很高的数据传输率
RAID Level 4
只需要使用一个冗余磁盘来完成奇偶校验
数据以较大的条带分布在各个盘中，每个磁盘单独运转，不同I/O请求可以同时满足
为所有数据磁盘中同一位置的位计算逐位的奇偶校验位，这个位保存在奇偶检验盘中
开销：写数据时还需要计算校验位并存放在校验位中。
RAID Level 5
与RAID4相似，不同的是奇偶校验条带循环分布在各个盘中。
避免一个RAID4奇偶检验盘潜在的瓶颈问题。任意一个盘上的数据失效不会引起数据丢失
RAID Level 6
采用了两种不同的奇偶校验计算，分别保存在不同磁盘的不同块中
高可靠性：除了同级数据异或校验区外，还有一个针对每个数据块的独立校验区。使得即使有两个包含用户数据的磁盘发生错误，也可以重新生成数据。
产生了额外开销：写数据时需生成两个校验盘数据
磁盘高速缓存
高速缓存（Cache memory）
比内存小，比内存快的存储器，用在处理器和内存之间
基于局部性原理，减少了对内存的平均访问时间
磁盘高速缓存（Disk cache）
为磁盘扇区而设置，位于内存的缓冲区
包含了磁盘某些扇区的副本
LRU算法（Least Recently Used）
置换策略最常用的算法
位于磁盘高速缓存中最近最少使用的块被换出
逻辑实现
用指向磁盘高速缓存的指针栈来组织块
最近被访问过的块被放在栈顶（用栈顶指针指向）
当一个块被引用或从磁盘放入磁盘高速缓存时，将它放在栈顶（用栈顶指针指向）
位于栈底的块即是置换对象（用栈底指针指向）
最不常使用置换算法LFU (Least Frequently Used)
置换访问次数最少的块
为每个块关联一个计数器
每次访问时，对应块的计数器增加1
当需要置换时，选择计数器值最小的块置换
LFU问题
如果一个块短期内被频繁访问，计数器值迅速增加，之后即使长时间不访问，也不会被选作置换对象
解决办法：将磁盘高速缓存分区
第5章 文件系统
概述
文件
文件：用户或系统创建的数据集
从用户的角度来看，文件是操作系统的重要组成部分
文件拥有的理想属性
长期存在：文件存储在硬盘或其它辅存中，用户退出系统时文件不会消失
可在进程间共享：文件有名字，具有允许受控共享的相关访问权限
结构：文件可以组织成为层次结构或更复杂的结构，以反映文件之间的关系
文件系统
提供存储数据的手段，且提供一系列对文件进行操作的功能接口
为文件维护一组属性
典型文件操作：创建、删除、打开、关闭、读、写
文件结构术语
域：基本数据单元；包含一个值；定长或变长
记录
一组相关域的集合，可视为应用程序的一个单元
定长或变长
一组相似记录的集合
可被用户和应用程序视为一个实体
通过名字访问
访问控制通常在文件级实施
数据库
相关的数据集合
数据元素之间存在明确的关系
供不同的应用程序使用
由一种或多种类型的文件组成
文件管理的目标
满足数据管理要求和用户需求
保证文件中的数据有效
优化性能
为各种类型的存储设备提供I/O支持
最大限度地减少丢失或破坏数据的可能性
为用户进程提供标准I/O接口例程集
在多用户系统中为多个用户提供I/O支持
用户的最小需求范围
设备驱动
最底层
直接与外围设备（或它们的控制器或通道）通信
负责启动设备上的I/O操作
处理I/O请求的完成
通常视为操作系统的一个组成部分
基本文件系统
称为物理I/O层
与计算机外部环境的基本接口
处理在磁盘间或磁带系统间的数据块
关注数据块在辅存的放置位置
关注数据块在内存缓冲区的放置位置
基本I/O管理程序
负责所有文件I/O的初始化和终止
维护处理设备I/O，调度和文件状态的控制结构
选择要执行I/O的设备
关注调度磁盘和磁带访问以优化性能
I/O缓冲区的指定和辅存的分配
访问方法
文件系统中与用户最近的一层
提供应用程序和文件系统以及保存数据的设备之间的标准接口
不同的访问方法反映了不同的文件结构以及访问和处理数据的不同方式
文件管理的要素
文件组织和访问
文件组织
文件组织：指文件中记录的逻辑结构，由用户访问记录的方式确定
选择文件组织的5个重要原则：快速访问、易于修改、节约存储空间、维护简单、可靠性
原则的优先级取决于使用文件的应用程序
堆文件：变长记录、可变域集、按时间先后排序
最简单的文件组织形式
按照到达的顺序收集数据
每条记录由一串数据组成
目的是积累大量数据并保存
通过穷举查找方法检索记录
顺序文件：定长记录、固定顺序的固定域集、按关键字域排序
最常见的文件组织形式
记录有固定的格式；
所有记录的长度都相同：每个域的位置、长度等相同；
每个记录中有一个关键域，唯一标识这个记录
记录按照关键域存储和排序
通常用于批处理应用中
可以很容易地存储在磁盘和磁带
索引顺序文件
保留顺序文件的关键特征：记录按照关键域组织
增加了支持随机访问的索引和溢出文件
索引提供快速接近目标的查找能力
溢出文件类似日志文件，要往文件中插入记录时，可以将其放在溢出文件中，并由主文件中它(即所插入记录)的前一个记录通过指针指向；
可按批处理方式合并溢出文件
索引可以有多级
索引文件
只能通过索引访问记录
可以使用变长度记录
完全索引包含主文件中每条记录的索引项
部分索引只包含有感兴趣域的记录的索引项
主要用于信息及时性要求比较严格且很少对所有数据进行处理的应用程序
例子是航空公司订票系统和商品库存控制系统
直接文件或散列文件
直接访问磁盘中任意一个地址已知的数据块
使用基于关键字的散列
典型应用场景
快速访问
固定长度的记录
一次只访问一条记录
文件目录
文件目录里每个文件项包含的信息
基本信息
文件名：由创建者（用户或程序）选择的名字，在同一个目录中必须唯一
文件类型：如文本文件、二进制文件、加载模块等
文件类型：如文本文件、二进制文件、加载模块等文件组织 供那些支持不同组织形式的系统使用
地址信息
卷：指示存储文件的设备
起始地址：文件在辅存中的起始物理地址（如磁盘的柱面、磁道和扇区）
使用大小：文件的当前大小，单位为字节、字或块
分配大小：文件的最大尺寸
访问控制信息
所有者：文件主，可以授权或拒绝其他用户的访问、改变给予他们的权限
访问信息：该单元的最简单形式包括每个授权用户的用户名和口令
权限信息：控制读、写、执行及在网上传输
使用信息
数据创建：文件首次放到目录中的时间
创建者身份：通常是当前所有者，但不一定必须是当前所有者
最后一次访问的日期：最后一次读取文件内容的时间
最后一次读用户的身份：最后一次执行读操作的用户
最后一次修改的日期：最后一次修改、插入或删除文件内容的时间
最后一次修改者的身份：最后一次进行修改操作的用户
最后一次备份的日期：最后一次把文件备份到另一个存储介质中的日期
当前使用：当前文件活动的信息，如打开文件的进程、加锁等
目录操作类型
目录结构
单级结构
两级结构
层次结构
树状结构
每一级目录可以包含文件，也可以包含下一级目录。
只有一个根目录，而且除根目录外，其余每个目录或者文件都有唯一的一个上级目录。
单个主目录
多个子目录
路径名
任何文件可以按照根目录或主目录向下到各个分支，最后达到该文件的路径来定位。
多个文件可以同名，只要保证它们的路径名是唯一的即可。
工作目录
对于用户，总有一个当前路径与之相关联，称作工作目录。
绝对路径：从根目录开始指定的目录
相对路径：从当前工作目录开始
无循环图结构
在树型目录的基础上，允许多个目录项指向同一个数据文件或者目录文件，实现了目录或者数据文件的共享。
不同的主目录可以共享一个文件和分目录，而不是各自拥有文件或分目录的拷贝。
Unix的目录结构即属于无循环图结构
目录项的删除
若对应的文件只有一个引用时，同时删除该文件。
若对应的文件存在多个引用时，只删除引用，而不删除文件。只有在所有文件引用都被删除后才删除文件。
单级结构/简单列表
在整个文件系统中只建立一张目录表，其中每个目录项对应一个文件。
主要优点是实现简单。
缺点：不允许文件重名；文件查找速度慢。
主目录：每个用户一个目录项，提供地址和访问控制信息
用户目录：用户文件的简单列表，文件名称须唯一
文件共享
用户对文件的代表性访问权限
用户对文件的访问权限与用户身份相关
文件共享的实现
文件共享的实现：一份物理存储；多个别名
在Unix操作系统上，可通过链接实现文件共享
链接分类
硬链接：基于索引结点
多个文件名链接到同一个索引结点
索引节点的引用计数记录在索引节点的链接计数中，若其减至0，则文件被删除。
链接文件和被链接文件必须位于同一个文件系统中
不能建立指向目录的硬链接
例：$ ln a b
软链接/符号链接：基于符号链接
特殊类型的文件，其链接内容是另一个目录或文件的路径。
建立符号链接文件，并不影响原文件——它们是独立的文件。
例：$ ln –s a b
为a创建一个符号链接b
rm b：a不受影响
rm a：a不存在，b能被控制但无法访问
缺点：空间和时间开销更大
硬连接与软链接的对比
记录组块
块是与辅存进行I/O操作的基本单位
为执行I/O，记录必须组织成块
对于给定的块大小，有三种组块方
辅存管理
文件分配
在辅存中，文件由许多块组成
操作系统或文件管理系统负责为文件分配块
文件分配采用的方法可能会影响到空闲空间管理的方法
给文件分配的是一个或多个分区（一组连续的已分配块)
文件分配表（FAT)
用于跟踪分配给文件的分区的数据结构
预分配与动态分配
预分配策略要求在文件创建时声明文件的最大尺寸
对于许多应用程序，很难可靠地估计文件的最大尺寸
用户和应用程序往往估大文件的最大尺寸，从而造成浪费
动态分配只有在需要时才给文件分配空间
分区大小
分区大小的选择策略
大小可变的大规模连续分区
性能较好
避免浪费
文件分配表较小
空间难以再次利用
块
小的固定分区能提供更大的灵活性
需要较大表或更复杂的结构来管理块的分配情况
邻近性不再是主要目的
主要目的是根据需要来分配块
文件分配方法
连续分配
大小可变的预分配策略：创建文件时，分配一组连续的块
文件分配表里每个文件只需一个表项：说明起始块和长度
适合顺序文件，检索容易
问题：外部碎片；预分配可能带来的问题。
连续分配——紧凑后：解决外部碎片问题
链式分配
隐式链接：每个块都包含指向下一个块的指针
文件分配表里每个文件只需要一个表项：声明起始块和长度
可以根据需要分配块，加入链中
适合顺序处理文件
问题：多个块离散分配，使得局部性原理不再适用，若需要一次读入多个块，得访问磁盘不同的部分
链式分配——合并后：周期性合并文件；克服前述问题
显式链接：用于链接文件各物理块的指针，显式地存放在文件分配表FAT中，该表在整个磁盘分区中仅一张
基于块的索引分配
分配给文件的每个块在索引中都有一个表项
索引作为单独的块来保存，文件分配表中的表项指向索引块
每个文件在文件分配表中都有一个一级索引
基于长度可变分区的索引分配
分配给文件的每个分区在索引中都有一个表项
基于大小可变分区分配可提高局部性
基于分区索引的文件整理可以减少索引数量，但是基于块索引则不行
注：索引方式支持顺序访问和直接访问，是最普遍的一种文件分配方式
一个块(索引块)容纳不了一个文件 的所有盘块的索引项时，怎么办？
需要若干个索引块进行存储
引入多级索引：对索引块再建立索引
空闲空间管理
分配给文件的空间需要管理，未分配给任何文件的空间也需要管理
为了实现文件分配技术，首先必须知道磁盘中的哪些块是可用的
件分配表外，还需要磁盘分配表（DAT）
位示图（位表，Bit Tables）
使用一个向量，向量中的每一位对应于磁盘中的每一块
0表示空闲块，1表示已使用块
适用于任何文件分配方法
非常小
很容易找到一个或一组连续的空闲块
链接空闲分区
使用指向每个空闲区的指针和它们的长度值，可将空闲区链接在一起
不需要磁盘分配表，仅需要指向链开始处的指针和第一个分区长度，空间开销可以忽略不计
适用于所有的文件分配方法
存在碎片
每次分配块时，在把数据写到块中之前，需要先读取这个块，以便找到指向新的第一个空闲块的指针
索引
将空闲空间视为一个文件，并使用索引表为文件分配空间
为了提高效率，索引应基于可变大小的分区而不是块
空闲块列表
卷
UNIX文件管理
UNIX区分6种类型的文件
索引节点
UNIX文件系统驻留在单个逻辑磁盘或磁盘分区
0 条评论
回复 删除
下一页
