导图社区 408-操作系统-框架、真题
- 340
- 26
- 4
- 举报
408-操作系统-框架、真题
2022操作系统新增考点；往年408真题分析；操作系统基础知识总结。
编辑于2022-01-02 16:00:06- 计算机408…
- 相似推荐
- 大纲
操作系统
冲刺学习-考纲新增及疑难点复习
新知识点
【宏内核】，【微内核】，外核 （含例题）
【例题】【0-1模拟卷-2-27】 微内核与宏内核
题干
B正确
系统服务以模块的方式组合，具有更强的灵活性
错误选项辨析
A，增加了IPC（进程间通信）的时间，运行速度更慢，稳定性更强
C，进程间通信是核心功能，运行在内核态
D，微内核将部分非核心的内核功能模块放到用户态执行，多个模 块可以看作用户进程，一个模块出现问题并不会导致整个系统的崩溃，因此该设计具有更强 的稳定性
宏内核
直接理解 （中央集权）
1、操作系统中所有的系统相关功能都被封装在内核中 （集成）
例如
进程管理
内存管理
文件管理
I/O管理
2、内核程序与外部程序处于不同的内存地址 空间中， 并通过各种方式防止外部程序直接访问内核结构 （地址保护）
3、程序只有通过一套称作系统调用 （system call）的界面访问内核结构 （封装）
特点
优点
所有系统服务均在内核中实现
各个模块之间协作的时候非常方便 方便使用数据、程序
例如：运行某个文件 可能同时涉及到所有模块协作
缺点
一旦某个服务崩溃，整个系统崩溃
微内核
直接理解 （部分放权）
1、只有最基本的操作系统功能才能放在内核中
2、不是最基本的服务和 应用程序在微内核之上构造，【并在用户模式下运行】
小细节
1、内存管理、进程通信等一些基础功能放在内核中实现
2、绝大多数系统服务由用户态下的 Server 进程 来提供
不同的服务模块处于不同的地址空间下
特点
优点
安全性高
一个服务崩溃并不会引起整个系统的崩溃
缺点
效率降低
当需要多个模块协作时，需要依赖 IPC（进程间通信），会降低效率
外核
应用程序可以有限制的访问系统资源（网络 socket、内存 VMA 等）
调度器 （含例题）
例题
【记忆】【0-1模拟卷2-24】闲逛进程、调度器
题干
知识点回顾
闲逛进程是内核的第一个进程，在其它进程均不处于就绪态的时候占用 CPU
该进程 拥有【最低的优先级】因此才能够保证在不存在其它任何可执行进程时才占用 CPU
闲逛进程运 行的越多，说明 CPU 越空闲
错误选项辨析
A，闲逛进程也是进程，必然需要PCB来作为唯一标识以及其 它运行资源
B，闲逛进程仅在CPU空闲时占用CPU防止空转而死机
D，调度器不属于任何一个单独的进程，而是嵌在中断服务程序中
调度器执行步骤 （作用：调度+切换）
1、获得处理器的控制权
2、把当前正在运行的进程状态（PCB，process control block）保存下来
3、选择一个新的就绪进程来执行
4、把新选择出来的进程分发给处理器运行，这一步会把第二步中的状态再加载到 CPU 寄存 器中。
闲逛进程（idle process）
特点
1、系统中的第一个进程
2、（运行优先级最低）当没有其它就绪进程需要执行的时候占用处理器
其它时 候不参与调度
3、只有在就绪队列中无进程时才会被调度
作用
占用 CPU
防死机
等待被调度
【重要】【内存映射文件】 （含例题）
内存映射文件的例题
题干
B，各选项解答
A，错误 内存映射建立的是文件到虚拟内存之间的映射
B，正确
C，错误 内存映射文件提高了读写效率！ 也提高了灵活性
传统的文件读写需要copy两次数据
内存映射文件只需要copy一次
D，错误 常规情况下，可以在用户态下访问内存映射文件 但是一旦发生缺页异常，还需要内核态的介入！
内存映射文件
什么是内存映射文件
内存映射文件，是一种将【自身逻辑地址】与 【某一段】【内存虚拟地址】绑定的文件
例子
如文件大小为 256KB,则通过内存映射，文件可以将自身空 间映射到虚拟地址 (2048+0)KB——（2048+256）KB 的虚拟内存空间上
优势
仅仅通过对虚拟内存空 间的访问，即可完成对文件的访问
因此读写文 件均可通过读写虚拟内存的方式实现
灵活
效率高
特点
进行内存映射 mmap()的过程没有产生数据拷贝
只是进行了逻辑上的映 射
对文件内容的访问依赖对虚拟内存的访问
内存映射文件与传统访问文件方式的区别
传统的访问文件的方法 （需要两次数据拷贝）
1、通过read（）系统调用将【文件数据】读到【内核中的缓冲区】
2、从【缓冲区】copy到【用户空间】
内存映射文件的方法 （只需要一次数据拷贝）
用户直接通过虚拟内存方式访问磁盘信息
【重要】虚拟机 （例题说明）
题干
示意图
C，各选项及其解释
A，错误
应用A位于虚拟机上，A发起系统调用由虚拟机的OS提供模拟的系统调用服务，并不会引起宿主机的CPU状态切换
B，错误
在虚拟机OS看来，它的下层即是系统底层硬件！ 因此，虚拟化程序事项虚拟机OS提供硬件接口，模拟硬件功能
C，正确
D，错误
应用A，应用B位于不同的虚拟机上，因此它们之间的通信需要通过【网络通信】
【重要】SSD固态硬盘 （例题说明）
SSD例题
SSD寿命的计算
题干
解答
是什么
0、示意图
1、原理
基于闪存技术（Flash Memory） 属于电可擦除ROM，EEPROM
2、组成
1、闪存翻译层
闪存翻译层通过【电路】工作
不同于机械硬盘用磁头
作用
翻译逻辑块号
找到对应的物理地址 对应 页
2、闪存芯片
每个闪存芯片由多个块（block）组成
每个块由多个页（page）组成
SSD的特点
1、读写性能
1、以页（page）为基本读/写单位
类比机械硬盘 以扇区 为读/写单位
2、以块（block）为【擦除】单位
块中的每一页可以【写一次】， 【读无数次】
3、支持随机访问
给定逻辑地址，【闪存翻译层】可以通过【电路】迅速定位到对应的物理地址
4、读写细节
1、读 快
2、写 慢
3、擦除的细节
1、一个块中的 x 页已经写入数据， 此时新来的逻辑地址映射到 x 页所在地址， SSD即将进行擦除操作
2、首先，将【 x 页所在的 块】 中的【所有页的数据】，全部复制到一个【新的块】中（被擦除过的）
此时闪存翻译层会更改相应的电路逻辑，以保证可以映射到新的物理地址
3、擦除 原 x 页 所在块的 所有数据 将 该块擦除
4、擦除结束后，写入当前要写入 x 页的数据
2、与机械硬盘的对比
SSD
SSD读写速度快，随机访问性能高，用电路控制访问位置
SSD安静无噪音、耐摔抗震、能耗低、造价更贵
SSD的一个"块"被擦除次数过多（重复写同一个块）可能会坏掉
机械硬盘
机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟
机械硬盘的扇区不会因为写的次数太多而坏掉
3、磨损均衡技术
思想
将擦除操作平均分布在各个块上， 以提升总体使用寿命
注意，每个块是有擦除寿命的
分类
动态磨损均衡
写入数据时，闪存翻译层优先选择累计擦除次数较少的块
静态磨损均衡
SSD监测并自动进行数据分配、迁移， 让【老旧的闪存块】承担以【读】为主的储存任务， 让【较新的闪存块】承担更多的【写】任务
疑难点
疑难点 1： 内核级线程和用户级线程
例题
【疑难题解题技巧】【19-23】内核级线程、用户级线程
题干
解答
B错误，根据我们的【解题思路】，OS无法感知到用户级线程，因此不会为每个用户级线程建立一个TCB
ACD正确，记忆
A.内核级线程的调度由操作系统完成
C. 用户级线程间的切换比内核级线程间的切换效率高
D. 用户级线程可以在不支持内核级线程的操作系统上实现
【12-31】进程、线程
题干
解答
A不太严谨，进程是资源分配的基本单位
错误选项辨析
B，讲反了，进程是资源分配的基本单位，线程是调度的基本单位
C，只有系统级线程的切换需要内核的支持；OS感知不到用户级线程，何谈线程切换
D，同一进程的线程不占有资源，共享相同的进程公共资源
解题思路
此类问题的破局要点只有一个：判断内核是否被操作系统感知到。内核级线程会被操作系统 感知，用户级线程不会。把握这一点一切问题都会迎刃而解。
疑难点 2： 进程的阻塞和唤醒
例题
【19-24】进程唤醒
题干
解答
C，①②都伴随着临界资源的增加 （I/O设备）（临界区）； ③进程运行->就绪
经验之谈：一般和CPU有关的不会阻塞
【18-27】进程阻塞
题干
解答
C，①②都伴随着临界资源的增加 （临界区）（磁盘）； ③进程运行->就绪
经验之谈：一般和CPU有关的不会阻塞
【15-25】执行->就绪
题干
解答
D
【14-26】读磁盘结束后OS对于进程的操作
题干
解答
A，I/O完成后进程进入就绪态
记忆点
解题思路
阻塞
指进程因为得不到满足而被阻塞在阻塞队列中
【重要】【常见的阻塞条件】
1、阻塞 I/O 下，进程进行了 I/O 操作（包括读磁盘和读其它外设），等待 I/O 完成
2、进程把自己阻塞在了信号量或者管程上
3、进程申请了被占用的【无忙等待锁】
值得注意的是自旋锁（忙等待锁）不会进入阻塞态，会一直执行
4、进程进行了特殊的系统调用如 sleep 等
5、进程间通信时没有收到预期的信息（管道、信号等机制下）
6、新数据尚未到达。对于一个计算进程，如果新的输入数据还没有到达，计算进程需要阻 塞等待
唤醒
指进程从【阻塞态】变为【就绪态】
这里不涉及 CPU 的争夺，只关注进程 是否满足竞争 CPU 的前置条件
疑难点 3： 进（线）程间的隔离与共享机制
例题
解题思路
1、进程间是存在一定的隔离性的，不同的进程一定拥有不同的地址空间（页表或段表）
2、至于 其它，我们一定要仔细分析题目要求我们的不同进程是要共同掌握资源的哪一部分，哪一部 分共享的话会出现问题。基于这一点，我们才可以准确作答
疑难点 4： 中断、异常和系统调用解析
例题
知识点回顾
1.中断和异常，及其处理
选择题记忆内容
中断是操作系统的基本工作方式 中断驱动
中断是硬件机制
中断的基本概念
中断（外中断）
原因
由CPU执行指令之外的因素导致
例子
1、I/O设备的结束中断
告诉CPU外设已经完成了I/O操作
2、时钟中断
时间片已经用完
异常（内中断）
原因
CPU执行指令过程中的因素导致
内容及例子
1、陷入 trap
描述
由程序引发，通常用于请求系统服务
例子
系统调用
2、故障 fault
描述
由错误引起的，可能被内核程序修复
内核程序修复完故障后会把CPU的使用权还给应用程序
例子
缺页故障
程序非法操作码
地址越界
算术溢出
注意浮点数下溢不算异常，CPU会令下溢的数为0。 然而浮点数上溢就会溢出，产生故障
3、终止 abort
描述
由致命错误引发
内核程序无法修复该错误
遇到这种情况直接终止该程序
杀死
例子
整数除以0
非法使用特权指令
补充
中断流程共2步
1、硬件完成（中断隐指令）
1、关中断
2、保存断点
PC、PSW压入到堆栈中
3、跳转中断处理程序
将中断程序的起始地址送PC 【事实上共用同一个中断服务程序，通过中断向量的不同区分选择哪种服务】
2、中断程序【OS】完成
4、保存现场和屏蔽字（保存上下文）
通用寄存器内的内容
5、开中断
6、执行中断服务程序
7、关中断
8、还原现场和屏蔽字
9、开中断
10、中断返回
一般通过中断向量表来找到对应的中断处理程序
2.系统调用 （是异常的一种）
基础
是什么
操作系统提供给应用程序的使用的接口
应用程序通过系统调用请求系统内核服务
为什么
系统中的各种共享资源都由操作系统统一管理 这些共享资源可能会引起争抢
例如：存储分配 I/O传输 管理文件
因此与资源相关的操作必须通过系统调用向操作系统提出服务请求，并由操作系统代为完成
这样可以保证系统的稳定性和安全性
怎么做
1、传递系统调用参数
2、应用程序执行陷入指令 （trap指令、访管指令）
（处于用户态）
执行陷入指令会引起内中断
3、执行处理系统调用的内核程序
（处于内核态）
4、返回应用程序
其他
系统调用与库函数的区别
总览
简述
部分库函数涉及到系统调用，有些库函数不涉及系统调用
疑难点 5： 缺页处理的细节分析
例题
解题思路
缺页本身是一种异常 （CPU 内部查表失败触发） 【异常需要立即处理】
【缺页】专属于【请求分页存储系统】而不是虚拟 页式存储系统
一定对应实体页
缺页可能会引发页面置换算法
【重要】【缺页处理完后】将【再次处理本条访存指令】
关 于中断或异常处理完毕后是执行本指令还是下一条指令应该根据实际情况来判断
缺页处 理程序的实体是分配一个内存页面用来承载外存交换的对应页并且修改页表的对应表项
疑难点 6： 由磁盘或文件系统的结构引发的一系列问题
例题
解题思路
磁盘是一种外设，相对于内存它是一种大容量低速的设备
这里可能使用 cache 的思想 来对磁盘数据进行一种缓冲处理
磁盘与内存进行数据交换的物理单位是扇区
但是在文件系统中，文件数据分配的最小单位 是【簇】（或者叫【磁盘块】，【数据块】，【逻辑块】等，特殊情况下物理块貌似也指磁盘簇，根据语境分 析）
也就是说，即使只是多出来 1bit 的数据，我们也需要多分配一个簇来承载它
磁盘分为多个分区，每个分区都被文件系统管理
文件系统看到的是一个抽象的磁盘
其单 位为簇
但是真实访问磁盘需要定位磁盘的物理位置
文件的物理地址一般 指它的磁盘簇号和簇内地址
但是当涉及到磁盘这个物理设备本身时，簇这个单位又变成了 逻辑上的，柱面磁道扇区成为了此处的物理地址，所以我们必须要对语境进行仔细分析
疑难点 7： 管程
例题
解题思路
【记忆】知识点-管程
为什么会出现管程
1、信号量机制不足
信号量程序编写困难，易出错
管程是什么
【管程】是一种用于【多线程】【 互斥访问】 【共享资源】的【程序结构】 （【由编程语言支持】，【由编译器实现互斥访问】）
它需要上锁
它可以实现高级的同步机制
它由【有关资源的数据结构】和在 【其上的定义的一组过程】组成
如何实现、使用
1、采用面向对象方法，简化了线程间的同步控制，因此管程通常是【语言级提供的功能】
进程只能通过调用管程中的过程间接访问管程中的数据结构
2、任一时刻最多只有一个线程执行管程代码
特别注意点
已经进入管程的线程，如果被阻塞了； 它可能把管程的使用权让给其他线程 （因此【同一时间可能有多个进程在管程的临界区中】，但是只能有一个进程执行）
因为管程在Wait()操作中，开头会上锁，但过程中会开锁
3、正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复
管程的组成
一个锁 +n 个条件变量
知识点-条件变量
条件变量是什么
条件变量是管程内的等待机制
类似于信号量机制中的“信号量”
用于实现进程同步
为什么要用条件变量
进入管程的线程因资源被占用而进入等待状态
每个条件变量表示一种等待原因，对应一个 【等待队列】。
怎么做
Wait()操作
1、将自己阻塞在等待队列中
2、唤醒一个等待者或【释放管程的互斥访问】 【18年真题来看，仅仅是释放管程的互斥访问】
Signal()操作
将等待队列中的一个线程唤醒
如果等待队列为空，则等同空操作
这里区别于V()操作，V()操作误用会让系统误认为有很多资源； Signal()则没有影响
条件变量 与 信号量 的区别
条件变量在执行wait、signal 操作时， 它【不涉及条件变量数值的改变（它没有值）】； 它仅仅【涉及对进程的阻塞和唤醒】
因为条件变量对应一个【等待队列】 wait、signal 仅仅是对该队列进行操作
【互斥访问】【条件变量】由【编译器】实现
而信号量的PV操作涉及对信号量值的改变
疑难点 8： 管道
例题
解题思路
【例】关于【管道】的一些细节补充
题干
补充知识点
1、管道的实质
管道的实质是内核利用 【环形队列】 的数据结构在 【内核缓冲区】 中的一个实现，默认设置大小为4K
读和写的位置都是自动增长的，不能随意改变，一个数据只能被读取一次，读取后数据就会从缓冲区中移除
当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写
2、管道的特点
1、管道由父进程创建，由子进程继承，因此只能在有血缘关系的进程之间进行信息传递【A正确】
2、管道实际上存放在内核维护的内存上，被抽象成一个文件。 每次访问管道需要系统调用实现
3、管道是半双工
数据只能向一个方向流动；双方需要互相通信时，需要建立起两个管道
4、管道的通信方式为：写端每次都将数据写入管道缓冲区的 末尾 ，而读端每次都从管道缓冲区的 头部 读出数据
5、读进程可以有多个，但是写进程只能有一个
选项解析
正确
A：管道由父进程创建，由子进程继承，因此只能在有血缘关系的进程之间进行信息传递
C：一个管道只能进行单向通信，且写入管道中的数据只能被读取一次
错误及分析
B：管道实质上是一个存放在外存中的文件，所以需要用读写文件的系统调用来访问
管道存放在内存中
D：所有数据都被读取后，若管道写端的引用计数为 0，则读管道的进程会进入阻塞态。
写端引用计数：表示还有多少个进程要对管道进行写操作
写计数为0说明没有进程可以对管道进行写操作了
阻塞的目的是什么？
等待别的进程继续写入
此时已经没有进程要写入，阻塞没有任何意义
这时候会直接返回 -1
那么什么时候会进入阻塞态？
当引用计数不为 0 时，即还有进程要写数据，此时读会被阻塞
疑难点 9： 进程并行类选择题
例题
解题思路
疑难点 11： 信号量的设计与使用
例题
解题思路
【同步关系】：先 x 再 y
一种普适的设计方案是设计一个初值为 0 的信号量 S,y 操作需要先 P(S),而 x 操作完成后 再 V(S)
【一般制约关系】：大家竞争临界区资源
【多重制约关系】：x 类，y 类，z 类等多个类型之间存在制约关系且每类操作可能不止出现一 次，而相同类型的操作间可能存在制约关系，也可能不存在制约关系。
【类型之间的制约关系】：设置一个类型间竞争的信号量，用于类型间竞争，这个信号量的 申请和释放往往需要配合一个对该类数据的计数器来完成（注意：计数器本身也是需要用信 号量来完成互斥修改的）
【类型内的制约关系】：为每个需要内部制约的操作类型再申请一个信号量，来实现类型内 的同步互斥。
疑难点 12： 不知道题目解题角度的题型
例题
解题思路
记忆内容-真题知识点
计算机系统概述
【16-23】操作系统的发展及各阶段的矛盾
题干
知识点-OS的发展
1、手工操作阶段 （人工纸带）
主要矛盾
人机速度矛盾，资源利用率低
2、批处理阶段
单道批处理 （引入脱机I/O，监督程序）
主要矛盾
CPU等待I/O导致利用率低
多道批处理 （引入中断）
主要矛盾
引入了中断技术，但是无交互性，只能通过作业说明书交互
3、分时操作系统 （引入时间片轮转）
4、实时操作系统
5、PC操作系统
A，各选项解析
①错，批处理系统不能允许用户直接交互，只能通过作业说明书交互
②正确
③正确
【记忆】【17-28】多道程序系统的优点
题干
D、解答
单道程序每次只能执行一道程序，如果程序进行I/O，则会让CPU空闲等待I/O完成
因此多道程序相比于单道程序，CPU，I/O利用率高；
多道程序可以并发执行程序，因此系统吞吐量大
【18-23】关于多任务系统的描述
题干
解答
①正确
一般来说，支持并发也一般支持并行
②显然正确
③不一定，单CPU也可以实现多任务操作！
【12-22】中断隐指令
中断流程共2步
1、硬件完成（中断隐指令）
1、关中断
2、保存断点
PC、PSW压入到堆栈中
3、引入中断处理程序
将中断程序的起始地址送PC
2、中断程序完成（OS完成）
4、保存现场和屏蔽字（保存上下文）
通用寄存器内的内容
5、开中断
6、执行中断服务程序
7、关中断
8、还原现场和屏蔽字
9、开中断
10、中断返回
【12-24】中断处理与子程序调用的区别
【15-22】关于异常的描述
题干
正确，记忆
A．内部异常的产生与当前执行指令相关
B．内部异常的检测由 CPU 内部逻辑实现
C．内部异常的响应发生在指令执行过程中
D错误
对于非法指令，可能会产生CPU无法处理的异常，此时需要终止进程，这时就不能返回到发生异常的指令处继续执行！
【15-23】处理外部中断
题干
B，解答
OS保存即中断程序完成的内容，即保存通用寄存器的内容
中断知识点回顾
1、硬件完成（中断隐指令）
1、关中断
2、保存断点
PC、PSW压入到堆栈中
3、引入中断处理程序
将中断程序的起始地址送PC
2、中断程序完成（OS完成）
4、保存现场和屏蔽字（保存上下文）
通用寄存器内的内容
5、开中断
6、执行中断服务程序
7、关中断
8、还原现场和屏蔽字
9、开中断
10、中断返回
【17-24】系统调用的流程
题干
记忆题，答案选C
记忆-系统调用的流程
1、要执行系统调用的进程将先传递系统调用参数
2、执行陷入指令，由用户态进入核心态；并将返回地址压入堆栈中
3、执行系统调用对应的内核服务程序
4、返回用户态
【18-22】关于外部中断
题干
C正确
CPU 只有在处于中断允许状态时，才能响应外部设备的中断请求
错误选项辨析
A，中断的优先级由中断屏蔽字决定！
B，通用寄存器的内容由中断服务程序完成
回顾中断相关知识点
中断流程共2步
1、硬件完成（中断隐指令）
1、关中断
2、保存断点
PC、PSW压入到堆栈中
3、引入中断处理程序
将中断程序的起始地址送PC
2、中断程序完成（OS完成）
4、保存现场和屏蔽字（保存上下文）
通用寄存器内的内容
5、开中断
6、执行中断服务程序
7、关中断
8、还原现场和屏蔽字
9、开中断
10、中断返回
D，CPU需要判断 1、是否处于开中断状态； 2、中断请求的优先级是否高于当前执行的程序
【记忆】【21-22】多重中断
题干
A错误
中断服务程序是在内核中执行的，必须要保障在内核态下可以套娃执行
其他选项当结论记忆
B.CPU 只有在检测到中断请求信号后，才会进入中断响应周期
C.进入中断响应周期时，CPU 一定处于中断允许（开中断）状态
D.若CPU 检测到中断请求信号，则一定存在未被屏蔽的中断源 请求信号
【20-21】关于中断的一些补充知识点
题干
中断补充知识点
1、【内中断、异常】都是不可屏蔽的，发生异常要立刻执行
2、外中断分为两类
【NMI不可屏蔽中断】
不受关中断影响
不受中断标志位影响
【INTR可屏蔽中断】
B显然错误
【19-25】系统调用知识点回顾
题干
系统调用-知识点
1、用户可以在用户态调用OS的服务，但是执行系统调用服务程序时，CPU一定处于内核态
2、用户程序需要通过系统调用使用OS的设备管理服务
3、操作系统不同，底层逻辑、实现方式均不相同，为应用程序提供的系统调用接口也不同
4、系统调用是用户在程序中调用操作系统提供的子功能【接口】
C正确
【记忆】【21-32】通过系统调用完成的操作
题干
C，解答
用户程序请求OS为其服务
A、B都是OS自动完成的
D是调用库函数，与系统调用无关
【21-23】特权指令回顾
题干
B，解答
常见特权指令
I/O指令
访问程序状态指令
存取特殊寄存器指令
其他选项
A，trap指令时在用户态执行
C，数据传送指令都可以执行
D，设置断点可以在用户态执行
进程管理
【12-30】处理机调度时机理解记忆
C．在进程处于临界区时，【只要不破坏临界区资源的使用规则】是可以进行处理机调度的！
适合进行处理机调度的情况
A．在进程结束时能进行处理机调度
B．创建新进程后能进行处理机调度
C．在进程处于临界区时进行处理机调度
【只要不破坏临界区资源的使用规则】
例如：通常访问临界资源可能 是慢速的外设（如打印机），如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的
D．在系统调用完成并返回用户态时能进行处理机调度
不适合进行处理机调度的情况
①在处理中断的过程中
②进程在操作系统内核程序临界区中
③其他需要完全屏蔽中断的原子操作过程中
【12-31】进程与线程的对比理解记忆
A正确
【14-26】进程读磁盘后OS对其的操作？
题干
A，解答
进程申请读磁盘操作的时候，因为要等待 I/O 操作完成，会把自身阻塞，此时进程就变为了阻塞状态
当 I/O 操作完成后，进程得到了想要的资源，就会从阻塞态转换到就绪态（这是操作系统的行为）
错误选项辨析
B，若降低进程优先级会使得其不易获得处理机资源，因此不合理
C，读磁盘完成≠要给进程分配内存
D，算法未知，不能确定会更改时间片的大小
【记忆】【14-31】管道的相关知识点
题干
C正确
进程对管道进行读操作和写操作都可能被阻塞
各错误选项辨析
A，管道是半双工通信，同一时间只能单向传播，因此要实现双向数据传输需要两个管道
B，管道是一种特殊的文件，与进程间通信相关，它存储在内存中！因此与磁盘容量大小无关
D，读进程只有一个，但是写进程可以有多个！
【例】关于【管道】的一些细节补充
题干
补充知识点
1、管道的实质
管道的实质是内核利用 【环形队列】 的数据结构在 【内核缓冲区】 中的一个实现，默认设置大小为4K
读和写的位置都是自动增长的，不能随意改变，一个数据只能被读取一次，读取后数据就会从缓冲区中移除
当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写
2、管道的特点
1、管道由父进程创建，由子进程继承，因此只能在有血缘关系的进程之间进行信息传递
2、管道实际上存放在内核维护的内存上，被抽象成一个文件。 每次访问管道需要系统调用实现
3、管道是半双工
数据只能向一个方向流动；双方需要互相通信时，需要建立起两个管道
4、管道的通信方式为：写端每次都将数据写入管道缓冲区的 末尾 ，而读端每次都从管道缓冲区的 头部 读出数据
5、读进程可以有多个，但是写进程只能有一个
选项解析
正确
A：管道由父进程创建，由子进程继承，因此只能在有血缘关系的进程之间进行信息传递
C：一个管道只能进行单向通信，且写入管道中的数据只能被读取一次
错误及分析
B：管道实质上是一个存放在外存中的文件，所以需要用读写文件的系统调用来访问
管道存放在内存中
D：所有数据都被读取后，若管道写端的引用计数为 0，则读管道的进程会进入阻塞态。
写端引用计数：表示还有多少个进程要对管道进行写操作
写计数为0说明没有进程可以对管道进行写操作了
阻塞的目的是什么？
等待别的进程继续写入
此时已经没有进程要写入，阻塞没有任何意义
这时候会直接返回 -1
那么什么时候会进入阻塞态？
当引用计数不为 0 时
相关知识点补充
【15-25】可能导致进程由执行态变为就绪态的是？
题干
解答
D，被高优先级进程抢占
错误分析
A，B，C都会使进程从执行态到阻塞态！
【记忆】【15-26】死锁相关
题干
知识点回顾
死锁预防
死锁避免
死锁检测
解答
①错误，前半句话是死锁预防方法！
②、③正确
【16-27】自旋锁代码解读
题干
解答
错误
A错误，该程序中，进程只有就绪态和执行态，不存在阻塞态的进程
区别与信号量机制
C错误，让权等待的意思是若进程不能被满足，则应释放掉CPU资源并进入阻塞态
显然本程序不涉及阻塞态，因此不满足让权等待原则
D错误，如果该语句处于关中断状态，则会一直霸占CPU资源，因此不合理排除
正确
B正确
【记忆】【16-29】进程工作集窗口
题干
知识点-进程工作集窗口
在任一时刻t，都存在一个集合，它包含所有最近k次（本题窗口大小为6）内存访问所访问过的页面。这个集合w（k，t）就是工作集。
求工作集时还需要去掉重复的页面
因此去除掉重复的工作集，本题选A
【记忆】【16-32】管程
题干
【记忆】管程知识点
为什么会出现管程
1、信号量机制不足
信号量程序编写困难，易出错
管程是什么
【管程】是一种用于【多线程】【 互斥访问】 【共享资源】的【程序结构】 （【由编程语言支持】，【由编译器实现互斥访问】）
它需要上锁
它可以实现高级的同步机制
它由【有关资源的数据结构】和在 【其上的定义的一组过程】组成
如何实现、使用
1、采用面向对象方法，简化了线程间的同步控制，因此管程通常是【语言级提供的功能】
进程只能通过调用管程中的过程间接访问管程中的数据结构
2、任一时刻最多只有一个线程执行管程代码
特别注意点
已经进入管程的线程，如果被阻塞了； 它可能把管程的使用权让给其他线程 （因此【同一时间可能有多个进程在管程的临界区中】，但是只能有一个进程执行）
因为管程在Wait()操作中，开头会上锁，但过程中会开锁
3、正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复
管程的组成
一个锁 +n 个条件变量
解答
A错误，管程不仅能实现进程间的互斥，而且能实现进程间的同步
记忆
B．管程是由【编程语言支持的进程同步机制】
由编译器实现进程互斥访问
C．任何时候只能有一个进程在管程中执行
D．管程中定义的变量只能被管程内的过程访问
管程特点
① 局部于管程的数据只能被局部于管程内的过程所访问
② 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
③每次仅允许一个进程在管程内执行某个内部过程
【记忆】【17-27】基于时间片调度的进程调度算法
题干
B显然错误，时间片用完后，进程由执行变为就绪态
记忆知识点
A．时间片越短，进程切换的次数越多，系统开销也越大
C．时钟中断发生后，系统会修改当前进程在时间片内的剩余时间
时钟中断是系统中特定的周期性时钟节拍。操作系统通过它来确定时间间隔，实现时间的延时和任务的超时
D．影响时间片大小的主要因素包括响应时间、系统开销和进程数量等
现代操作系统为了保证性能最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等因素确定时间片大小
【记忆、回顾】【18-24】求系统平均周转时间
题干
回顾知识点
周转时间=作业完成时间-作业提交时间 = 等待时间+运行时间
带权周转时间 = 周转时间 ÷ 要求服务时间
响应比 = （等待时间+要求服务时间）÷ 要求服务时间
解答
【记忆】【18-28】管程的【条件变量】
题干
知识点-条件变量
条件变量是什么
条件变量是管程内的等待机制
类似于信号量机制中的“信号量”
用于实现进程同步
为什么要用条件变量
进入管程的线程因资源被占用而进入等待状态
每个条件变量表示一种等待原因，对应一个 【等待队列】。
怎么做
Wait()操作
1、将自己阻塞在等待队列中
2、唤醒一个等待者或【释放管程的互斥访问】 【18年真题来看，仅仅是释放管程的互斥访问】
Signal()操作
将等待队列中的一个线程唤醒
如果等待队列为空，则等同空操作
这里区别于V()操作，V()操作误用会让系统误认为有很多资源； Signal()则没有影响
条件变量 与 信号量 的区别
条件变量在执行wait、signal 操作时， 它【不涉及条件变量数值的改变（它没有值）】； 它仅仅【涉及对进程的阻塞和唤醒】
因为条件变量对应一个【等待队列】 wait、signal 仅仅是对该队列进行操作
【互斥访问】【条件变量】由【编译器】实现
而信号量的PV操作涉及对信号量值的改变
D正确，各选项及其解析
D，x.wait()操作会将该进程阻塞在x的阻塞队列中（记忆）
错误辨析
A，对条件变量的互斥访问由【编译器】实现
B，唤醒操作由signal()实现
C，条件变量没有值！只对应一个阻塞队列
【18-29】时钟中断可能造成的影响
题干
解答
①②③均正确
【18-32】让权等待 临界区访问的四个原则
题干
知识点回顾：临界区的访问规则
1、空闲让进
没有进程在临界区时，任何进程可进入
2、忙则等待
有进程在临界区时，其他进程均不能进入临界区
3、有限等待
等待进入临界区的进程不能无限期等待
4、让权等待 （不一定要实现）
不能进入临界区的进程，应释放 CPU（如转换到阻塞状态）
C，正确
让权等待的含义：当进程不能进入临界区时，应该释放掉占有的处理机资源，进入阻塞状态
其他选项
A，Peterson方法 （满足了忙则等待、有限等待） 【没有实现让权等待】
是一个用于实现互斥锁的并发程序设计算法（双线程互斥）
可以控制两个线程访问一个共享的单用户资源而不发生访问冲突
B、D可以满足忙则等待
D是自旋锁
设计初衷是忙则等待
【疑难题解题技巧】【19-23】内核级线程、用户级线程
题干
解题思路
此类问题的破局要点只有一个：判断内核是否被操作系统感知到。内核级线程会被操作系统 感知，用户级线程不会。把握这一点一切问题都会迎刃而解。
解答
B错误，根据我们的【解题思路】，OS无法感知到用户级线程，因此不会为每个用户级线程建立一个TCB
ACD正确，记忆
A.内核级线程的调度由操作系统完成
C. 用户级线程间的切换比内核级线程间的切换效率高
D. 用户级线程可以在不支持内核级线程的操作系统上实现
【19-24】进程唤醒
题干
解答
C，①②都伴随着临界资源的增加 （I/O设备）（临界区）； ③进程运行->就绪
经验之谈：一般和CPU有关的不会阻塞
【19-43】哲学家进餐问题
题干
解答
核心思想
通过设置有限资源来避免死锁
具体解答
【20-32】进程互斥必须要的条件
题干
临界区访问的四个原则
1、空闲让进
没有进程在临界区时，任何进程可进入
2、忙则等待
有进程在临界区时，其他进程均不能进入临界区
3、有限等待
等待进入临界区的进程不能无限期等待
4、让权等待 （不一定要实现）
不能进入临界区的进程，应释放 CPU（如转换到阻塞状态）
C，解答
①满足【忙着等待】
②满足【空闲让进】
③满足【有限等待】
④说的是【让权等待】，不一定需要实现，如Peterson算法
【21-24】OS创建新进程的相关操作
题干
B，解答
OS创建新进程的一般步骤
1、申请空白的PCB
2、为进程分配必要资源
3、初始化PCB
【记忆】【21-27】可能引起进程调度的操作有？
题干
【进程调度、切换】知识点回顾
进程调度是从就绪队列中选择一个进程分配CPU进入运行态
进程切换一定发生在进程调度后， 但进程调度不一定会产生进程切换，因为就绪队列可能为空，仍然运行原先的进程
D，以上均可能引发进程调度程序的执行
【21-45】信号量机制(用开关中断尝试实现信号量互斥)
题干
各小题及其解答
（1）
题干
解答
因为信号量S是能够被多个进程共享的变量，多个进程都可以通过wait()和signal()对S进行读、写操作。 因此对S的访问必须互斥
（2）
题干
解答
1、方法 1 错误
在方法 1 中的 wait()中，关中断进入while循环之后其他进程就无法修改S的值，会死循环
2、方法 2 正确
（3）
题干
解答
不能，因为开/关中断指令都是特权指令 【特权指令属于内核】，不能为用户程序使用！
内存管理
【12-25】对于虚拟存储器的理解
1、在离散分配的内存管理方式的基础上实现
2、虚拟存储器的容量仅由CPU寻址范围决定
【13-30】页式管理的细节
题干
B，解释说明
1、逻辑地址->页面的过程
2、分析
1、用户访问内存产生缺页！ 因此页面不会发生越界错误！ I 错误
越界错误一定发生在 取得逻辑地址之后，查询页表之前
2、在没有空闲页框时可能会置换页面 II 正确
3、缺页一定会分配内存 III 正确
【14-28】能加快虚实地址转换的操作有？
题干
解答
【记忆】【14-30】Belady异常现象
题干
记忆
只有FIFO、CLOCK、改进CLOCK等队列型算法可能产生Belady现象
【记忆】【14-32】多级页表
题干
D，正确
错误选项解析
A错，多级页表不仅不会加快地址的变换速度，还因为增加更多的查表过程，会使地址变换速度减慢
B错，如果访问过程中多级的页表都不在内存中，会大大增加缺页的次数
一级页表常驻内存，二级页表不常驻内存
C错，D对，考虑以下这种情况，显然会增加页表项占用的字节数
【记忆】【15-30】页面置换策略和页面分配策略
题干
C，解答
【15-46】大题-二级页表
题干
各小问及其解答
（1）
页大小 = 页框大小 = 2^12B = 4KB
虚拟地址空间页的总数 = 2^(10+10) = 1 M页
（2）
1、确定页目录项和页表项的个数
页目录项个数 = 2^10个
有几个页目录项表示有几个一级页表
页表项个数 = 2^20 个
一个页表项表示一个页表里的一条数据，该数据表示【虚页号-实页号】的映射
2、计算它们各自占用的页数
页目录项占用：4×2^10 ÷ 2^12 = 1 页
页表项占用：4×2^20 ÷ 2^12 = 1024页
3、总页数 = 1 + 1024 = 1025
（3）
对这两个虚拟地址进行划分，发现页目录号相同， 因此它们是同一个二级页表，只需要访问一个二级页表
【16-26】改进的CLOCK算法
题干
解答
【17-25】内存分配回收（审题！）
题干
题干小细节
1、回收空闲分区后，需要考虑能否和上下分区进行合并
2、题干说了要对空闲分区进行重新排列（从小到大）
B，解答：
【19-28】分段存储管理系统中的【共享段】 （可以类比文件系统的管理，包括inode表，系统级文件打开表，进程级文件打开表）
题干
B，错误
因为进程的各自逻辑不同，因此段S在不同进程中的段号可能不同
类比进程级文件打开表，各自的指针可能不同
正确选项与文件系统相关操作的类比
A，类比 inode 仅拷贝一份放在 inode 表中
C，类比P1，P2共享系统级文件打开表中的表项
D，类比文件删除，当系统级文件打开表中inode的引用计数为 0 时才删除表项，并将对应的inode表表项置为空闲
【记忆】【19-32】动态分区分配算法性质特点
题干
动态分区分配特点单独总结 （选择题考点）
缺点
【低地址】产生许多【小碎片】
最先匹配 （首次适应算法）
产生【最多】的【不必要小碎片】
最佳匹配
会使得很快【没有大块内存】使用
最坏匹配
优点
高地址有大块的内存
最先匹配 （首次适应算法）
避免大块内存被拆分
最佳匹配
中等大小分配较多时效果好
最坏匹配
C
【记忆】【20-28】影响分页系统访存时间的因素有
题干
D，解答
【①缺页率】
影响缺页中断的频率，缺页率越高，平均访存时间越长
【②磁盘读写时间】
影响缺页中断的处理时间，中断处理时间越长，平均访存时间越长
【③内存访问时间】
影响访问页表和访问目标物理地址的时间
【④执行缺页处理程序的CPU时间】
影响缺页中断的处理时间，中断处理时间越长，平均访存时间越长
【必看】【20-46】多级页表
题干
各小题及其解答
（1）
题干
解答
（2）
题干
解答
虚拟地址空间
必须连续 （数组 a 的元素逻辑上必须相邻）
物理地址空间
可以不连续 （相邻的逻辑页在物理内存上不一定相邻）
（3）
题干
解答
按行访问局部性更好
由第一问可知，每一个数组元素行正好存放在同一个逻辑页内； 而同一列元素均位于不同的逻辑页内
文件管理
【12-28】read系统调用详细理解
A，1，2正确
read系统调用详解
1、前提
在操作系统中，要【读一个文件】首先要用 【open 系统调用】将该文件【打开】
open 系统调用的参数
1、文件的路径名
2、文件名
小细节补充
【read 系统调】用只需要使用 【open 系统调用返回的文件描述符fd】， 并不使用文件名作为参数
2、read系统调用的参数
1、文件描述符 fd
2、buf 缓冲区首址
3、传送的字节数 n
3、read系统调用的功能
试图从 fd 所指示的文件中读入 n 个字节的数据，并将它们送至由指针 buf 所指示的缓冲区中
【15-29】访问文件的磁盘块个数？
题干
知识点
索引结点读入内存后
直接索引只需要访问一次磁盘块
x级索引访问x次磁盘块
因此只需要计算该地址处于哪个索引结点下即可得到访问磁盘块次数
B，解答
【14-27】位图，簇
题干
解答
【记忆】【15-31】【位图】文件系统
题干
知识点：位图
顾名思义，一位表示一个盘块是否被占用
解答
【17-30】文件系统用户访问权限
题干
解答
这些权限是需要一起考虑的，因此一个状态对应一bit
【待议】【17-31】文件系统小细节
题干
回顾【描述符表，打开文件表，inode表关系】
三者关系
1、（进程级）文件描述符表
1、【进程】每次打开一个【文件】，系统就会在 【该进程的用户文件描述符表】中分配一个相应的表项
2、【表项的索引】返回给该进程，用于标志该文件，这个索引就是常说的【文件描述符】
3、每个进程都有它独立的描述符表
2、打开文件表（又叫做系统级的描述符表）
表格中各条目称为 打开【文件句柄（open file handle）】
一个【打开文件句柄】存储了与一个打开文件相关的全部信息
1. 当前文件偏移量
（调用read()和write()时更新，或使用lseek()直接修改）
2. 打开文件时所使用的状态标识
（即，open()的flags参数）
3. 文件访问模式
（如调用open()时所设置的只读模式、只写模式或读写模式）
4. 与信号驱动相关的设置
5. 对该文件i-node对象的引用
6. 文件类型
（例如：常规文件、套接字或FIFO）和访问权限
7. 一个指针，指向该文件所持有的锁列表
8. 文件的各种属性，包括文件大小以及与不同类型操作相关的时间戳
3、inode表
B，解答
①选项逻辑上就不对
两个进程读同一个文件，它们读写的顺序可能就不同，如果读写指针一直相同，会极大影响各自的执行逻辑
②正确，硬链接指向同一个索引结点inode
如上图所示
进程A的文件描述符表的 fd0
指向打开文件表第 0 项
对应的 f 指向inode表中的第1976项
进程B的文件描述符表 fd3
指向打开文件表第 86 项
对应的 f 指向inode表中的第1976项
③正确
【记忆】【17-26】文件磁盘空间分配
题干
解答
操作系统以簇/块 为基本单位进行分配文件
簇/块 一般为磁盘扇区的整数倍
示意图
【18-31】如何提高文件访问速度
题干
解答
①②③④均正确
【18-46】文件系统，文件长度计算
题干
各小题及其解答
（1）求文件长度
题干
解答
明确几个原则
1、一个文件对应一个inode节点
2、一个直接地址项指向一个文件簇
3、簇可以存放【直接地址项】或者【数据】
因此文件最大长度：
（2）求存放图片个数
题干
解答
文件系统能存放多少个文件与以下因素有关
1、索引结点indoe 的个数
一个inode对应一个文件
2、数据簇的大小，不能超过最大容量
因此本题解答
（3）访问不同文件需要的时间
题干
解答
分析原则
考虑inode结点的结构
1、直接索引
能直接访问就直接访问，省时间
2、间接索引
【记忆】【19-26】文件系统管理空闲磁盘块的数据结构（FAT表知识点补充）
题干
知识点补充
1、传统的文件系统管理空闲磁盘块的方法
空闲表法
空闲链表法
位示图法
成组链接法
2、【FAT表知识点补充】
1、文件分配表（FAT）的表项与物理磁盘块一一对应，并且可以用一个特殊的数 字-1表示文件的最后一块，用-2表示这个磁盘块是空闲的
（当然，规定用-3、-4来表示 也是可行的）
2、因此文件分配表（FAT）不仅记录了【文件中各个块的先后链接关系】，同时还 标记了空闲的磁盘块，操作系统可以【通过FAT对文件存储空间进行管理】
B，解答
I/O管理
【12-26】I/O子系统层次结构
题目
A
知识点示意图
知识点回顾
3.I/O 子系统的层次结构
总览图
软件层次结构
用户层 I/O 软件
实现与用户交互的接口
用户可直接【系统调用】在用户层提供的、与 I/O 操作有 关的库函数，对设备进行操作。
使用【逻辑设备名】作为参数
设备独立软件
用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、以友 设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间
将【逻辑设备名】映射到【物理设备】，实现设备的分配
设备驱动程序
与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动 I/O 设 备工作的【驱动程序】。
例如：计算数据的磁盘柱面号，磁头号，扇区号
中断处理程序
用于保存被中断进程的 CPU 环境，转入相应的中断处理程序进行处理，处 理完并恢复被中断进程的现场后，返回到被中断进程。
硬件层次结构
硬件设备
I/O 设备通常包括一个机械部件和一个电子部件
电子部件称为设备控制器（或适配器）
在个人计算机中，通常是一块 插入主板扩充槽的印刷电路板
机械部件则是设备本身
I/O 调度
定义
不同进程请求同一个 I/O 设备服务的时候，选择合适的进程来分配 I/O 设备资源。
【12-32】提高I/O性能的方法
题干
提高I/O性能的方法
A．重排 I/O 请求次序
重排 I/O 请求次序也就是进行 I/O 调度，从而使进程之间公平地共享磁盘访问
减少 I/O完成所需要的平均等待时间
C．预读和滞后写
缓冲区结合预读和滞后写技术对于具有重复性及阵发性的 I/O 进程改善磁盘 I/O 性能很有帮助
D．优化文件物理块的分布
优化文件物理块的分布可以 【减少寻找时间与延迟时间】，从而提高磁盘性能
【记忆】【16-31】SPOOLing技术
题干
SPOOLing-知识点回顾
总览
1、需要在外存上开辟【输入井、输出井】
2、需要实现输入进程SP1、输出进程SP2并发执行
因此需要多道程序设计技术支持
3、SPOOLing实现了将独占设备改成共享设备
即让多个作业共享一台独占设备
4、【外部设备】和【输入井、输出井】之间的数据传输由系统控制
D，如知识点所述
【记】【17-32】DMA执行流程
题干
【B】，DMA仅在启动和完成时需要CPU处理
1、（CPU）启动DMA控制器 （即②选项）
2、DMA控制磁盘和内存交换数据（③选项）
3、传送完成后DMA向CPU发送中断请求（①选项）
4、CPU执行“DMA结束”中断服务程序（④选项）
【记忆-磁盘初始化的流程】【17-29】磁盘逻辑格式优化程序的作用
题干
知识点-磁盘初始化流程
1、低级格式化（物理格式化） 【分扇区】【确定磁盘校验码所占的位数】 （一般由厂商完成）
将磁盘的各个磁道划分为扇区，并确定管理扇区所需要的数据结构 （如【扇区校验码】）（校验码用于检验扇区中的数据是否发生错误）
示意图
2、磁盘分区（如划分C、D、F盘） 【分柱面】
示意图
3、进行【逻辑格式化】 【创建文件系统】
包括：【创建文件系统的根目录】，【对空闲磁盘块进行管理的数据进行初始化】（如位图，空闲分区表）
B，解答
如上述知识点所示
②、④正确
【必看】【16-47】FAT表
题干
各小问及其解答
（1）求目录文件内容
题干
解答
（2）求FAT表长度，求文件长度
题干
解答
1、求FAT 的最大长度
1、FAT表中 1 表项存放簇号，占 2 B
因此共有 2^16 个簇
2、FAT表最多需要将所有的簇都存在表中，因此最大长度为： 2^16 × 2 B = 2^17B = 128 KB
2、文件系统支持的最大长度
即 FAT 表存满，一个表项对应一个簇 2^16 × 4 KB = 256MB
（3）考察表项
题干
解答
知识点
FAT表中的每个表项存放下一个簇号
108存放在FAT的106号表项中
106存放在FAT的100号表项中
（4）访问簇
题干
需要读【48】【106】号簇， 解答
1、已知条件
FAT 表， dir目录已经在内存中
2、读 dir/dir1/file1 第5000个字节的具体流程
1、访问 内存中的 dir 目录文件的内容 得知 dir1 所处在第48号簇
【读48号簇】
2、dir1 读入内存，得到以下信息
3、读取 file1 的5000个字节
1、一个簇 4KB = 4096B 因此需要读 file 1 的 第二簇
2、需要通过 FAT 表去查找 100号簇的下一个簇
3、由于 FAT 表在内存中，因此直接访问第 106 号簇
【18-30】磁盘调度算法
题干
A，正确
因为只有A可以严格按照磁道到达的时间先后顺序执行
BCD均错误，考虑以后一系列新来的磁道恰好是磁头移动的第一个磁道的情况
【20-22】DMA细节补充
题干
C，见解析
DMA细节补充
每准备好32位数据，DMA 控制器就发出一次【总线请求/DMA请求】
相对于 CPU，DMA 控制器的总线使用权的优先级更高
因为I/O会不断地写入数据到数据缓冲寄存器中， 如果不及时将数据缓冲寄存器的数据取走， 会造成数据的丢失， 因此DMA控制器的总线使用权的优先级更高
在整个数据块的传送过程中，CPU可以访问主存储器
数据块传送结束时，会产生 【"DMA 传送结束"/DMA中断】中断请求
而【DMA中断】发生在整块数据传送完之后
几种DMA控制方式的回顾
1、停止CPU访问主存
适用背景
DMA要成组地传送数据
流程
1、【DMA接口】向CPU发信号，要求CPU放弃 地址线、数据线、控制线相关的使用权
此时CPU基本处于【不工作状态】或【保持原始状态】
2、【DMA接口】获得总线使用权，开始传输数据
3、传完数据后，DMA接口通知CPU
2、DMA、CPU交替
适用背景
【CPU工作周期】大于【主存存取周期】
流程
将CPU工作周期分为两部分， 各供DMA、CPU专门使用
3、周期挪用/周期窃取
适用背景
是前两种方式的折中
各种情况下的流程
1、CPU不访存
停止CPU给DMA
2、CPU正在访存
等存取周期结束给DMA
3、同时访存
CPU放弃访存，给DMA挪用几个存取周期
【记忆必看】【20-30】具体设备独立性的系统
题干
知识点
0、回顾
软件层次结构
用户层 I/O 软件
实现与用户交互的接口
用户可直接【系统调用】在用户层提供的、与 I/O 操作有 关的库函数，对设备进行操作。
使用【逻辑设备名】作为参数
设备独立软件
用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、以友 设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间
将【逻辑设备名】映射到【物理设备】，实现设备的分配
设备驱动程序
与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动 I/O 设 备工作的【驱动程序】。
例如：计算数据的磁盘柱面号，磁头号，扇区号
中断处理程序
用于保存被中断进程的 CPU 环境，转入相应的中断处理程序进行处理，处 理完并恢复被中断进程的现场后，返回到被中断进程。
1、物理设备可以视为特殊的文件，因此可以用文件名访问
例如：插入U盘后可以通过文件名来访问U盘内容
2、【应用程序/用户程序】通过逻辑设备名来访问物理设备
3、【驱动程序】负责建立【逻辑设备】和【物理设备】的映射关系
D错误，解答
更换物理设备后，无需修改应用程序。 只需要修改驱动程序即可
【21-46】磁盘如何格式化；操作系统如何启动
题干
各小题及其解答
（1）系统启动OS的执行次序
题干
解答
1、ROM中的引导程序
2、磁盘引导程序
3、分区引导程序
4、操作系统的初始化程序
（2）硬盘格式化及操作系统的安装次序 【知识点回顾补充】
题干
解答
1、磁盘物理格式化
1、低级格式化（物理格式化） 【分扇区】【确定磁盘校验码所占的位数】 （一般由厂商完成）
将磁盘的各个磁道划分为扇区，并确定管理扇区所需要的数据结构 （如【扇区校验码】）（校验码用于检验扇区中的数据是否发生错误）
示意图
2、对磁盘进行分区
2、磁盘分区（如划分C、D、F盘） 【分柱面】
示意图
3、磁盘逻辑格式化
3、进行【逻辑格式化】 【创建文件系统】
包括：【创建文件系统的根目录】，【对空闲磁盘块进行管理的数据进行初始化】（如位图，空闲分区表）
4、操作系统的安装
（3）相关操作
题干
解答
磁盘扇区的划分 - 物理格式化
文件系统根目录建立 - 逻辑格式化
习题摘录
基础卷
1、关于操作系统并发特性的描述
正确的
A、宏观上的并发执行在微观角度看依然是串行。
C、并发执行的各进程独占了一个逻辑上的处理器。
操作系统的虚拟性
D、并发特性一般可以极大的提高整个系统的 CPU 利用率。
如在I/O操作时CPU并发执行其他进程，避免空转
B、并发执行的各进程不可嗯感知到其它进程的存在
错误的
B、并发执行的各进程不可能感知到其它进程的存在
错误，因为存在进程间通信
2、关于中断隐指令中保存程序断点的描述（细节）
正确的
A、必须在关中断的环境下才能确保无误的执行。
必须的，中断隐指令是 硬件 自动执行的，它包含3个步骤
1、关中断
2、保存断点
3、跳转到中断服务程序
错误的
B、各进程把各自的程序断点放置在公共的内核堆栈上。
各进程自带内核堆栈、用户堆栈！
示意图
错在 公共 两字上
C、所谓的断点保存，即是把程序中断完成后需要执行的下一条指令的物理地址保存在内 核堆栈中。
错在 物理地址 ！
PC中保存的是下一条指令，逻辑地址！需要进行操作得到物理地址！
D、断点完成保存后即可进行开中断操作以确保系统对中断的及时响应
中断流程共2步
1、硬件完成（中断隐指令）
1、关中断
2、保存断点
PC、PSW压入到堆栈中
3、引入中断处理程序
将中断程序的起始地址送PC
2、中断程序完成
4、保存现场和屏蔽字（保存上下文）
通用寄存器内的内容
5、开中断
6、执行中断服务程序
7、关中断
8、还原现场和屏蔽字
9、开中断
10、中断返回
可以看到，我们需要保存上下文后才开中断！
3、关于系统调用的说法
正确的
A、系统调用一定在用户态下发起
B、系统调用必须依赖于自陷指令（trap）
C、系统调用从本质上说，是程序自发产生的异常
异常（内中断）
原因
CPU执行指令过程中的因素导致
内容及例子
1、陷入 trap
描述
由程序引发，通常用于请求系统服务
例子
系统调用
2、故障 fault
描述
由错误引起的，可能被内核程序修复
内核程序修复完故障后会把CPU的使用权还给应用程序
例子
缺页故障
3、终止 abort
描述
由致命错误引发
内核程序无法修复该错误
遇到这种情况直接终止该程序
杀死
例子
整数除以0
非法使用特权指令
错误的
D、应用程序要访问此刻不存在于内存中的数据，必须依赖系统调用来完成
不在内存 = 在外存中 访问外存的方法
1、文件系统的读文件操作 （属于系统调用！属于异常/内中断-trap）
2、虚拟内存中的缺页中断 （属于故障！属于异常/内中断-fault）
4、关于进程间通信的说法
正确的
共享内存方式下不需要内核参与每一次消息的传递
同一进程的不同线程间的数据共享不需要内核的参与
错误的
消息队列系统不需要内核参与每一次消息的传递
简述消息队列
在内核中提供专门的消息传递队列，来为进程通信服务
每一次传送信息，都会发生用户态向内核态的切换
管道系统不需要内核参与每一次消息的传递
简述管道
管道是一种特殊的文件，因此访问管道即读写文件，需要内核参与
5、关于进程间切换的说法
知识点
进程切换
进程调度
处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行， 以实现进程并发地执行。
正确
C、进程切换后，第一次访问内存不可能 TLB 命中
TLB中存放的是虚拟页号和页框号的映射关系，在进程切换后会将新进程的页面调入内存，并清空TLB
更新TLB会将原先进程在TLB中的关系移出TLB
第一次访存时，TLB中一定没有新进程的页面，因此TLB一定不命中
错误
A、用户进程间的切换在用户态下实现。
是在内核态进行切换的
B、进程间切换确切的说仅仅包含通用寄存器状态、进程地址空间和程序执行位置的切换
进程切换不单单仅有上述内容，还包含PSW、文件打开表等一系列操作
D、进程切换是进程调度的必然结果。
进程调度是从就绪队列中选择一个进程分配CPU进入运行态
进程切换一定发生在进程调度后， 但进程调度不一定会产生进程切换，因为就绪队列可能为空，仍然运行原先的进程
6、关于信号量的说法
正确
C、非抢占式调度方式下，V 操作不会造成当前运行的进程的状态变化
正确，考虑一个抢占式调度的细节
在抢占式调度方式下，V()操作后，信号量加一，会使得阻塞队列中的某个进程进入就绪状态
如果进入就绪状态的进程的优先级比当前运行的进程的优先级高，则当前的进程可能会被抢占，而进入就绪态
错误
A、若信号量为负，则在信号量返回正值之前，所有申请该信号量的进程都会维持在阻塞 状态。
举一个反例
当前信号量为 -7 表示有7个进程申请打印机被阻塞
这时来了一个V()操作，信号量+1
此时，会从阻塞队列中选取一个进程进入就绪队列！
因此A的后半句说法显然是错误的
B、信号量之所以可以实现“忙则等待”，是因为内部封装了自旋锁
自旋锁（忙等待锁） （若无法满足，不会阻塞，一直等待）
简单理解自旋锁
这是我的桃子，你们不能摘（上锁了）只能在边上看着（不会让进程阻塞）
每隔一段时间你们可以问我能摘桃了吗（等待+询问【此时询问的进程还在运行】），得到我许可后才可以摘桃（释放自旋锁）
自旋锁的定义
当一个线程尝试去获取某一把锁的时候，如果这个锁此时已经被别人获取(占用)，那么此线程就无法获取到这把锁
该线程将会等待，间隔一段时间后会再次尝试获取
“忙则等待”
简单理解“忙则等待”
大爷（临界区）正忙着呢，哪凉快哪呆着去（申请资源失败，进入阻塞态）
该思路通过（无忙等待锁）实现
遇到上锁的就把自己阻塞了
D、非抢占式调度方式下，P 操作可能会导致当前进程丢失 CPU 使用权而进入就绪态。
P()操作会使得资源减少，可能导致当前运行的进程进入阻塞态！
强化学习
相关基础知识
中断和异常相关
【例题】会导致用户态、内核态切换的是？
题干
B，解答
中断和异常会导致用户态切换到内核态
1 会导致异常-abort 内核会杀死进程
3 是系统调用，执行trap
函数调用不会发生切换
【例】用户态、内核态相关知识 下列在内核态下才可以执行的是？
题干
各选项解析
答案
A：涉及到修改系统寄存器行为
例如 虚拟页 -> 实体页 的过程
显然不能由用户直接执行，需要OS来实现
由用户实现会产生严重的后果
D：读写文件操作必须要OS来执行
其他选项
B：系统调用是由用户态下执行的
系统调用=trap=INT=陷入
C：进程访问任何地址都是通过虚拟地址访问的，所以不一定需要在内核态下才能执行
【记】【0-1模拟卷2-22】CPU响应异常的时间为？
题干
B，解答
异常又称为内中断，与 CPU 或者内存有关， 【异常不能屏蔽】， 且【一旦发生异常需要立即处理】
【记忆】
CPU响应中断（外中断）的时间： 中断周期（执行周期结束后？）
CPU响应异常的时间： 立即响应
【重点，系统调用大类】
【例题1】对于系统调用描述正确的是？
题干
AB正确，知识点回顾 CD错误，错误辨析
正确
A、所有系统调用都触发同一地址上存放的中断处理程序。
系统调用采用软中断的方式 在Linux中采用 INT80 指令
系统调用 访管指令 trap指令 INT 80（Linux） 含义相同
系统调用后【都会】进入【 80 号中断】， 并将所有需要的信息推入【寄存器】中
即系统调用时采用的是相同的一个中断
那么，不同的系统调用如何区别呢？ 通过寄存器的数据来判断！
B、不同的系统调用需要传递的参数数量可能不同
举两个例子
read(xxx)
一个参数
exit()
没有参数
错误
C、用户态的程序可以把系统调用所需要的参数放入堆栈中供操作系统使用
系统调用程序会把参数推入【寄存器】，而不是堆栈
执行系统调用时，程序处于用户态 此时只能放入【用户堆栈】 然而执行系统调用过程中，操作系统只能访问【内核堆栈】！ 因此不能放入堆栈中
D、不同的操作系统为应用程序提供统一的系统调用接口
不同的操作系统，系统调用的接口可能不同！ 举个例子：IOS和Android的接口就不同！
操作系统的描述
【记忆】【0-1模拟卷-2-23】批处理系统？
题干
知识点
批处理系统可以接收一次打包多个作业进行有序工作
批处理系统在处理打包作业的过程中不能与用户产生交互
批处理系统中的作业运行在用户态，操作系统运行在内核态
特权级 (Privilege) 机制，它让应用程序运行在用户态，而操作系统运行在内核态，且实现用户态和内核态的隔 离
批处理系统 (Batch System) 的核心思想是：将多个程序打包到一起输入计算机。而当 一个程序运行结束后，计算机会自动加载下一个程序到内存并开始执行。这便是最早的真正 意义上的操作系统。
C错误，解答
批处理系统能够终止出错的应用程序， 转而运行下一个应用程序 因而不会影响后续作业的进行
进程管理
进程、线程概念相关
【大类】进程状态转换
例题1，常见进程状态切换
题干
解答
A：分配CPU
B：时间片用完
C：错误
D：设备就绪
【小细节】例题2，时钟中断与进程状态切换
题干
解答
可能引起的
A：运行态->就绪态
时间片用完
D：就绪态->运行态
分配时间片
C：阻塞态->就绪态
例如sleep(); 函数 进程将自己休眠，过了一定时间由OS唤醒
常见情况： 1、由某个进程唤醒（比如让出临界区，唤醒阻塞队列的某个进程） 2、由OS唤醒（如sleep()函数）
不可能引起的
B：运行态->阻塞态
只能是进程自己阻塞自己
【大类】（记忆）进程、线程基本知识点
【例】对于进程的描述
题干
解答
进程是此时此刻的内存和CPU的状态 是个动态的概念，用PCB记录
D，程序是指令的集合！
【例】关于进程和线程的描述
题干
解答
错误
A 错误：操作系统各项初始化工作都完成后，可能存在某个时间点没有任何进程在执行。
操作系统靠程序驱动执行，若没有进程，CPU就一直空转，不会再有其他状态
B错误：每个进程都独占一个页表和 TLB
每个进程独占页表 正确
死知识
但是不独占TLB，快表是硬件实现的！ 每个进程独占显然不现实
正确
C：同一进程的不同线程共享代码段和页表，但是不共享寄存器和堆栈
因为寄存器和堆栈与线程的逻辑相关
D：操作系统中的第一个进程一定是由内核启动的
死知识
【例】线程不共享的内容？
题干
不同线程共享
A：全局变量
数据段
B：库函数
代码段
C：页表
不共享
D：堆栈
堆栈、寄存器等内容不共享
【0-1模拟卷-2-30】线程共享的内容
题干
解答
管道！知识点回顾
管道可以看作一个打开文件，可以被不同线程共享
不可共享内容
堆栈，寄存器状态都是程序运行 的必要资源，无法被不同线程共享。局部变量存放在堆栈上，自然也无法共享
【记忆】进程不能被挂起的时间？
知识回顾
挂起：将进程从内存换入到外存
解答
进程在I/O时不能被挂起
进程与I/O的交换实际上是【物理内存】与I/O设备的交换； 也是【进程的虚拟地址】与I/O进行交互
最后等效为【内存+磁盘】与I/O交互
【例】系统线程相关
题干
答案及分析
A
系统动态DLL在载入时会形成线程池
这些线程占有内存，但是出于阻塞状态
当其他不同进程调用时相当于进程的执行线程调用函数，把系统线程需要的数据推到寄存器和相应的位置 然后进行线程切换，切换到系统线程进行执行
【大类】进程间通信
【例】关于【管道】的一些细节补充
题干
补充知识点
1、管道的实质
管道的实质是内核利用 【环形队列】 的数据结构在 【内核缓冲区】 中的一个实现，默认设置大小为4K
读和写的位置都是自动增长的，不能随意改变，一个数据只能被读取一次，读取后数据就会从缓冲区中移除
当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写
2、管道的特点
1、管道由父进程创建，由子进程继承，因此只能在有血缘关系的进程之间进行信息传递
2、管道实际上存放在内核维护的内存上，被抽象成一个文件。 每次访问管道需要系统调用实现
3、管道是半双工
数据只能向一个方向流动；双方需要互相通信时，需要建立起两个管道
4、管道的通信方式为：写端每次都将数据写入管道缓冲区的 末尾 ，而读端每次都从管道缓冲区的 头部 读出数据
5、读进程可以有多个，但是写进程只能有一个
选项解析
正确
A：管道由父进程创建，由子进程继承，因此只能在有血缘关系的进程之间进行信息传递
C：一个管道只能进行单向通信，且写入管道中的数据只能被读取一次
错误及分析
B：管道实质上是一个存放在外存中的文件，所以需要用读写文件的系统调用来访问
管道存放在内存中
D：所有数据都被读取后，若管道写端的引用计数为 0，则读管道的进程会进入阻塞态。
写端引用计数：表示还有多少个进程要对管道进行写操作
写计数为0说明没有进程可以对管道进行写操作了
阻塞的目的是什么？
等待别的进程继续写入
此时已经没有进程要写入，阻塞没有任何意义
这时候会直接返回 -1
那么什么时候会进入阻塞态？
当引用计数不为 0 时
进程调度
【重要】【进程切换】
【记忆、理解】【例】 【进程切换】对存储系统的影响
题干
各选项解析
正确（记忆内容）
A：页表被切换
B：TLB 被清空
记忆内容拓展
进程发生切换，一定会使得页表切换 TLB清空
发生进程切换后的一段时间内， 虚拟地址转换为物理地址的时间会变长 直观感受就是程序运行变慢
线程发生切换，不会导致页表切换 TLB不会清空
线程共享进程的资源（这里特指页表） 线程切换不会使得TLB失效 因而切换线程比切换进程快
错误
C：原进程数据所在的 cache 块失效
错误
进程切换影响的是页表、TLB
对应的是虚拟地址 向 物理地址的转换
Cache 中存储的仅仅是物理地址
虚拟地址不影响物理地址
D：新进程的页表从外存被载入内存， 其载入内存的起始位置被系统标记为页表起始地址
新进程的页表从外存被载入内存
错误，新的进程页表可能就存在内存中，无需从外存中调入
其载入内存的起始位置被系统标记为页表起始地址
【记忆】【0-1模拟卷2-25】进程切换的全过程那些量不会发生改变？
题干
解答
进程切换不会改变打开一个文件的进程个数，因此答案选 D
进程切换中可能改变的量
用户进程切换需要触发中断调用【内核中的调度器】， 切换【页表、堆栈和寄存器状态】等
【例】CPU调度相关概念，平均周转时间
题干
解答
B （1+2+3）/ 3 = 2
相关知识点
作业周转时间
作业从 提交 到 完成 的时间间隔
平均周转时间
（作业 1 周转时间+作业 2 周转时间+......+作业 n 周转时间）/n。
【例】进程调度的相关细节
题干
各选项解答
正确
B：短剩余时间调度算法属于抢占式调度算法
课本原话
直观上理解是合理的
错误
A、非抢占式调度意味着进程在执行结束或意外退出前，不会主动放弃 CPU
当进程申请I/O操作时，进程会把自己阻塞
C、进程调度发生后，必然会引发进程切换
不一定，进程调度时就绪队列可能没有就绪进程，此时方才在执行的进程会重新进入执行态，此时没有进程切换
回顾下进程切换的一些特点
D、上下文切换只可能发生在进程（线程）切换发生时
首先明确：上下文切换即切换堆栈、寄存器信息。
可能发生上下文切换的情况
1、中断！
2、进程切换
【例，记忆】什么时候才能kill进程？
题干
解答
A，运行态！（记忆）
进程同步、互斥
信号量与PV操作
解决信号量问题的一般流程
例题1，信号量
题干
答案及分析
C
因为题干提到共享一个资源， 因此信号量S最大只能为 1
负数代表有多少个进程被阻塞
例题2，信号量算法题考查 （简单大题例题）
题干
分析
解决信号量问题的一般流程
1、分析制约关系
2、设计制约信号量
3、设计进程
父母进程（类似）
儿女进程（类似）
4、检查特殊情况
【大题例题】（待理）
题干
分析
1、分析制约关系
2、设计制约信号量
3、设计进程
4、检查特殊情况
【2009-45】 较为简单的信号量模拟
题干
解答
0、回顾解题的一般步骤
1，2、分析制约关系，设计信号量
3、根据信号量，插入P、V操作及其他约束操作
1、写各个进程的大框架
2、写 mutex 的约束
3、写 empty 的约束
4、写 odd，even 的约束
4、检查，敲定终稿
【记忆】锁
【0-1 好题】利用锁实现互斥机制 （类似16-27）
题干
代码解读
&lock
表示锁信号量，当 lock== 1 时 表示已经上锁
while( Test&Set(&lock) );
是自旋锁的代码
当lock=1 时，Test&Set(&lock) = 1，会一直执行while语句
当lock=0 时，Test&Set(&lock) = 0， 执行完这条语句后，会把 lock 的值置 1 然后跳出while循环
Critical section;
表示临界区
lock = 0;
表示进程 i 访问完临界区后释放锁
选项解读
错误
A：多个进程竞争临界区，若有一个进程从临界区离开，则会有一个进程从阻塞态被唤醒
由代码可知，进程会一直忙则等待（一直执行while的代码）， 进程只会在就绪态和执行态之间切换
C：对临界区的访问满足空闲让进，忙则等待，有限等待和让权等待的基本原则。 （互斥访问的四个原则）
空闲让进
lock == 0 时可以进入， 即满足空闲让进原则
忙则等待
lock == 1 时表示临界区忙， 进程会一直执行while循环等待
有限等待
进程执行完后会释放锁， 其他进程可以进入临界区
让权等待
等待的时候释放CPU资源
D：上述代码可以满足进程访问临界区时的先进先出
不一定，假设使用时间片轮转法 有6个进程正在运行自旋锁， 当临界区的进程运行完释放自旋锁后，我们不知道会轮到哪一个执行 因此满足先进先出
正确
B：Test&Set()在执行过程中不会被中断。
Test&Set是原子操作， 因此不会被中断
【0-1模拟卷2-26】关于锁的说法
题干
B，解答
A错误，锁的 lock 和 signal 之间的操作并不是硬件提供的原子操作，而是利用锁的特性形成的 【临界区代码】
B正确，锁具有阻塞进程的功能，则必须为这些进程提供阻塞队列
C错误，【自旋锁】依靠【自循环】 来实现互斥，在锁打开后刚好被调度到的进程可以进入临界区，而【不是依据先后顺序进入】
D错误，【管程 中的进程】在进行【条件变量的 wait()操作】时也会释放锁
【记忆】管程
【记忆】【例】关于管程的说法正确的是？
题干
知识点回顾
答案ABCD 分析
A：管程是一个语言成分,管程的互斥访问完全由编译程序在编译时自动添加上
管程相当于一个语言级的类，就是给程序员使用的
B：管程和信号量在功能上等价
管程实现了程序级的同步互斥
C：管程提供了一个执行环境，其中同一时刻只能有一个进程在执行
【记忆】
D：多个进程可能同时存在于管程维护的临界区中
特别注意点
已经进入管程的线程，如果被阻塞了； 它可能把管程的使用权让给其他线程 （因此同一时间可能有多个进程在管程的临界区中，但是只能有一个进程执行）
一个进程在管程中运行
多个进程被阻塞在管程中
死锁相关
死锁预防
1、银行家算法例题1
题干
解答
（1）求Need矩阵
解答
用Max矩阵 减去 Allocation矩阵
（2）判断系统是否处于安全状态？ 是则给出安全序列
解答
（3）来一个请求，判断是否能满足
题干
解答
内存管理
【大类】动态分区分配
【例题1】内存分配算法 （最佳适应）
题干
解答
最佳适应的基本思想
将分区升序排列
每次分配最小最适合的分区
图解
【例题2】各动态分区算法特点比较
题干
A，知识点回顾
分页存储管理
【多级页表】
【例题1】一级、二级页表
题干
C、解答
【例题2】二级页表
题干
C、解答 注意，用虚拟地址空间
【小知识点】 页表大小一般和页面大小相同 但是具体得看题目！
【必看】【20-46】多级页表
题干
各小题及其解答
（1）
题干
解答
（2）
题干
解答
虚拟地址空间
必须连续 （数组 a 的元素逻辑上必须相邻）
物理地址空间
可以不连续 （相邻的逻辑页在物理内存上不一定相邻）
（3）
题干
解答
按行访问局部性更好
由第一问可知，每一个数组元素行正好存放在同一个逻辑页内； 而同一列元素均位于不同的逻辑页内
【例题】缺页过程中可能会发生的情况
题干
C，解答
1、回忆缺页异常相关的知识点
1、缺页异常发生在查找内存中的页表没有找到的情况下
此时内存中没有调入目标页面
2、通过页表，去磁盘找对应的页面，调入内存中
1、修改有效位 （所以一定会修改页表）
2、读出页面 （一定涉及到磁盘/IO）
3、页面调入内存对应页框中 （涉及到分配页框）
虚拟存储管理
【综合例题】例1
题干
各小题及解析
1、分析逻辑地址
题干
解答
分析题设给定条件确定地址信息 将逻辑地址转换分段解析
2、经FIFO替换后得到物理地址
题干
解答
先确定要置换的页号 借页表得到页框号 将逻辑地址中的逻辑页号替换为页框号得到物理地址
3、经CLOCK算法替换得到物理地址
题干
解答
1、回顾CLOCK算法流程
2、确定替换的页号，找到页框号 完成逻辑->物理地址的映射 （替换更改访问位的次序如图所示）
【例】虚拟存储器的容量
题干
D，解答最大容量与地址空间有关
虚拟存储器的实际容量 = min{2^MAR， 主存+辅存}
简单例题 1
题干
解析
1、虚拟地址访问TLB得到物理地址 （最好情况）
2、物理地址访问Cache得到指令或数据 （最好情况）
【2009-46】【综合，虚拟存储管理】 46.页面访问的流程及其所需要的时间
题干
解答
（1）依次几个访问虚拟地址所需要的时间
题干
<0> 确认地址形式
页面大小 4KB（没讲默认按字节编址） 页内偏移 12 位
虚拟地址 16 位，虚拟页号 4位
<1> 2362H
此时 TLB 和 Page
<2> 1565H
此时 TLB 和 Page
<3> 25A5H
此时 TLB 和 Page
（2）求虚地址对应的物理地址
题干
解答
文件管理
文件的物理结构相关
例题1， 目录文件存放的信息是？
题干
解答
1、目录文件是一种特殊的文件
2、目录文件中存储着它的 【目录项】（可以理解为目录项=数据文件的FCB）
可以理解为一个文件夹下，放着子文件和子文件夹 子文件、子文件夹在该目录文件对应的磁盘中均以目录项的形式存储
例题2，关于UNIX索引结构 （记忆内容）
题目
解答
inode中存放了文件的元信息 也存放了索引结构！！！
系统调用 + 打开文件 例题
题干
A
各小点分析
（√）I. 若文件的数据不在内存中，则该进程进入睡眠等待状态
文件数据不在内存=>进行I/O读磁盘
进程请求I/O操作会进入等待状态
（√）II. 请求 read 系统调用会导致 CPU 从用户态切到核心态
系统调用会发生特权级的切换
（×）III. read 系统调用的参数应包含文件的名称
read文件前会先open文件！
打开文件知识点回顾！
open操作时会将inode，必要数据结构调入内存中维护的文件描述符表中 通过文件描述符来read文件！
访问磁盘相关的例题
1、给定相关信息，求平均查找一个文件需要访问磁盘多少次
题干
解答
（1）程序以块为单位访问磁盘
OS中姑且认为 块=盘块=物理块=数据块
（2）计算一个盘块中可以装载的目录项个数
（3）求平均访问次数
2、给定图示，求需要读磁盘多少次
题干
解答
【重要大类】硬链接，软链接
重要例题 1
题干
B，解析
0、inode相关知识点
1、画示意图
2、说明
1、root常驻内存，下面直接存放着x，a的目录项
2、红色部分为题目描述的 【“在 root/x/y 目录下创建 root/a/b/file 的硬链接 newfile”】操作
1、root/x/y是一个目录文件
它的由一条一条目录项组成
2、相当于在该表下创建了一个新的目录项， 目录项的文件名是newfile，inode编号是3
3、根据inode编号，找到inode表中对应的inode结点inode3
inode3中维护着newfile文件的元信息
其中，newfile文件的磁盘信息是 root/a/b/file
也就是说，访问root/x/y/newfile 就是访问root/a/b/file
3、各个选项对应的目录项如图蓝色所示
4、分析
A是在目录文件y下新创建文件newfile，会改变inode的元信息
改变了inode的时间戳
B显然不受影响，选B
C在图上表示同一个iNode 它们被引用次数+ 1 ，发生改变
改变了inode 的链接数
D与C效果相同
练手例题 2
题干
示意图及解答
B
【912文件系统】例题 （画出文件结构即可解题）
题干-背景知识介绍
初始状态 注意后续题目每一步都是连贯的
23.1
状态
前一状态
当前状态
画图解答
23.2
状态
前一状态
当前状态
画图解答
23.3
状态
前一状态
当前状态
画图解答
23.4
状态
前一状态
当前状态
画图解答
23.5
状态
前一状态
当前状态
画图解答
23.6
状态
前一状态
当前状态
画图解答
I/O管理
（记忆）完成设备相关操作的程序是？
题干
答案
设备驱动程序
【例】缓冲区例题 （类比计组流水线）
题干
B、解答
单缓冲分析
双缓冲分析
【例】SPOOLING相关
0-1例题1
题干
B：虚拟出多台打印机（虚拟设备）
知识点回顾
【I/O软件层次相关】
【0-1模拟卷2-32】
题干
解答
1、在 I/O 软件的层次结构中，用户软件利用底层提供的系统调用和其它服务编写库函数， 设备独立性软件产生系统调用，并使用设备驱动程序提供的操作设备的抽象接口， 它将设备抽象成了文件，隐藏了具体设备的细节，其提供的功能均与设备细节无关。
2、设备驱动程序真实的操作设备，并提供给上层具体设备的操作接口。
3、中断处理程序在 I/O 完成后，通过读取设备的寄存器状态，给用户对应的返回，因此同样会与 I/O 设备进行一定的交互
记忆内容-知识点索引
中断与异常
进程与线程
进程基础
Unix下进程的创建
进程间通信的三种方式
线程基础
进程与线程的比较
用户线程
内核线程
CPU调度
调度的层次（记）
CPU调度衡量参数（记）
经典调度算法
同步、互斥
经典同步问题
死锁避免-银行家算法
动态分区策略及其特点
分页存储管理
虚拟存储管理
页面置换算法
软链接，硬链接
重要习题
文件系统层次结构（选择题）
索引分配
磁盘空闲空间管理
常用磁盘调度算法
设备相关知识
（记忆）完成设备相关操作的程序是？
题干
答案
设备驱动程序
整体框架（参考考纲）
计算机系统概述
(一)操作系统的基本概念
(二)操作系统的发展
(三)程序运行环境
1. CPU 运行模式
内核模式
1、一旦触发中断，则一定在内核态下运行
2、内核态可能的情况
1、涉及访问 I / O 设备的过程
用户不能直接访问 I/O 设备 必须由操作系统代为完成
2、访问内核态才能访问的寄存器如PSW
3、开中断、关中断（成对先后出现）一定发生在内核态
用户模式
特殊的用户态指令
1、访管指令 （trap指令） （INT 80）（Linux中）
2、命令解释程序
具体的命令处理需要中断进入内核态处理
3、系统调用 （程序接口）
系统调用的最后一步就是访管指令
2.中断和异常，及其处理
选择题记忆内容
中断是操作系统的基本工作方式 中断驱动
中断是硬件机制
中断的基本概念
中断（外中断）
原因
由CPU执行指令之外的因素导致
例子
1、I/O设备的结束中断
告诉CPU外设已经完成了I/O操作
2、时钟中断
时间片已经用完
异常（内中断）
原因
CPU执行指令过程中的因素导致
内容及例子
1、陷入 trap
描述
由程序引发，通常用于请求系统服务
例子
系统调用
2、故障 fault
描述
由错误引起的，可能被内核程序修复
内核程序修复完故障后会把CPU的使用权还给应用程序
例子
缺页故障
程序非法操作码
地址越界
算术溢出
注意浮点数下溢不算异常，CPU会令下溢的数为0。 然而浮点数上溢就会溢出，产生故障
3、终止 abort
描述
由致命错误引发
内核程序无法修复该错误
遇到这种情况直接终止该程序
杀死
例子
整数除以0
非法使用特权指令
补充
中断流程共2步
1、硬件完成（中断隐指令）
1、关中断
2、保存断点
PC、PSW压入到堆栈中
3、引入中断处理程序
将中断程序的起始地址送PC
2、中断程序完成
4、保存现场和屏蔽字（保存上下文）
通用寄存器内的内容
5、开中断
6、执行中断服务程序
7、关中断
8、还原现场和屏蔽字
9、开中断
10、中断返回
一般通过中断向量表来找到对应的中断处理程序
3.系统调用 （是异常的一种）
基础
是什么
操作系统提供给应用程序的使用的接口
应用程序通过系统调用请求系统内核服务
为什么
系统中的各种共享资源都由操作系统统一管理 这些共享资源可能会引起争抢
例如：存储分配 I/O传输 管理文件
因此与资源相关的操作必须通过系统调用向操作系统提出服务请求，并由操作系统代为完成
这样可以保证系统的稳定性和安全性
怎么做
1、传递系统调用参数
2、应用程序执行陷入指令 （trap指令、访管指令）
（处于用户态）
执行陷入指令会引起内中断
3、执行处理系统调用的内核程序
（处于内核态）
4、返回应用程序
其他
系统调用与库函数的区别
总览
简述
部分库函数涉及到系统调用，有些库函数不涉及系统调用
4.程序的链接与装入
补充
高级语言转化为指令流的过程
5.程序运行时内存映像与地址空间
(四)操作系统结构分层
模块化
总览
宏内核
微内核
特点
尽可能地把内核功能转移到（用户态）
用户模块间通信使用消息传递
进程间通信
鸿蒙就是一个微内核结果
好处
灵活
安全
缺点
性能
外核
(五)操作系统引导
BIOS
说明
通常存储在内存的ROM中
操作系统的装载流程
(六)虚拟机
进程管理
(一)进程与线程
1.进程概念
进程的基本概念
进程是什么？
进程的定义
进程是指一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。
进程是程序的一次执行。
进程是运行中的程序。
进程的本质
进程＝程序+运行状态
进程的本质是当前所有的内存状态和 CPU 状态的总和。
程序即已经存放于内存中的代码和数据
运行状态表示 CPU 中各寄 存器状态（例如 PSW，通用寄存器、PC 程序计数器等）
进程是操作系统抽象出的概念
进程的组成
1、代码
2、数据
3、状态寄存器
程序计数器 PC,程序状态字寄存器 PSW
4、通用寄存器
AX,BX,CX...
5、进程占用的系统资源
已打开文件，已占用的内存等。
进程的特点
1、动态性
可动态地创建、结束进程
2、并发性
进程可以被独立调度并占用处理机运行
3、独立性
不同进程的工作不相互影响。
4、制约性
因访问共享数据/资源或进程间同步而产生制约。
进程是（资源分配）的最小单位。
为什么引入进程？
引入进程的目的是为了更好地使多道程序并发执行，提高资源利用率和系统吞吐量
补充
程序执行的本质
程序是存储在磁盘上的可执行程序，本质上为链接好的指令流。
进程内的堆栈
每个进程都有自己的堆栈 一个进程通常有 用户堆栈 和 内核堆栈
堆栈寄存器SP永远指向栈顶元素
当发生运行模式切换时，也会发生堆栈的切换
进程控制块（PCB）
PCB是什么
PCB 是进程存在的唯一标识
PCB包含的信息
总览图
1、进程标识信息
2、处理机现场保存
3、进程控制信息
为什么引入PCB
操作系统希望对 PCB 的组织管理来管理进程
补充
而 PCB 就是进程的运行状态以及控制信息抽象出的数据结构。
2.进程的状态与转换
进程的状态
就绪态
进程所有除 CPU 以外的条件均已满足，等待获取 CPU 后便可以直接运行。
运行态
进程占用 CPU 处于运行中的状态。
阻塞态（等待态）
进程等待某些事件或者除 CPU 以外的某些资源得到满足后才能运 行的状态
要点
1、阻塞态和就绪态的区分方式在于所需要的资源是否只有 CPU；
2、单 CPU 单核的情况下，处于运行态的进程始终只有一个；
3、进程处于就绪态的原因只有还没有分配到 CPU，但是进程处于阻塞态的原因可能 是多种多样的，而每一类原因造成阻塞的进程都会单独构建一个 PCB 队列。
就绪态不能直接到阻塞态！ 只有运行起来的进程才可以在某一时间进入阻塞态！
创建态
系统还在为进程提供初始资源的状态。在这个阶段，进程可能还在创建 PCB 或分配进程地址空间。
退出态
进程运行终止后，把系统资源返还的状态。
进程退出说明
1、正常退出（自愿退出）
2、错误退出（自愿）
3、致命错误（强制退出）
4、被系统或其它进程杀死（强制退出）
就绪挂起态
进程在外存，但只要进入内存，获得CPU即可运行
等待挂起态
进程在外存并等待事件发生
等待->等待挂起
当就绪队列的进程需要更多的内存资源时，等待队列中的进程可能会被移到外存（进入等待挂起态）
挂起与激活
挂起
进程被暂时放回磁盘来减少进程占用内存
激活
把一个进程从外存转入内存
进程状态的转换
总览图
各种状态转换
创建->就绪
进程初始资源分配完毕后就进入就绪态
就绪->运行
就绪进程分配到 CPU 资源即可进入运行态
运行->就绪
运行中的进程被调度系统或者更高优先级的进程抢占 CPU
等待->就绪
等待进程等待的事件被满足后就进入就绪态等待 CPU 资源的分配
运行->退出
1、正常退出（自愿退出）
2、错误退出（自愿）
3、致命错误（强制退出）
4、被系统或其它进程杀死（强制退出）
运行->阻塞
申请资源失败
注意事项
1、不包含就绪到阻塞态（等待态）的转移，因为即使进程突然缺乏了条件，也必须 要运行起来了才能感知到条件缺失；
2、只有运行中的程序才会退出；
3、阻塞进程只能先进入就绪态等待 CPU 的分配而不能直接进入运行态。
进程切换
含义
暂停当前运行进程，从运行状态变成其他状态；
调度另一个进程从就绪状态变成运行状态。
新的运行进程占用 CPU（即 PC 指向该进程的代码段）
进程切换的要求
切换前，保存进程上下文；
切换后，恢复进程上下文；
快速切换
进程控制块 PCB:内核的进程状态记录
内核为每个进程维护了对应的进程控制块（PCB)；
内核将相同状态的进程的 PCB 放置在同一队列
进程的创建
进程都是由进程创建的，第一个进程是由操作系统创建的内核进程。
Unix 进程创建系统调用 fork/exec
fork 的含义
A 进程调用了 fork（）则会产生一个 A 进程的拷贝 B 进程
但是在这个过程中， 父进程的 fork（）返回被创建进程的 pid， 子进程的 fork()返回 0。
exec()的含义
exec()函数具有一个文件名作为参数，表示当前进程从此以后写入该文件作为 执行代码。
进程内存状态的复制方式 Copy-on-write
根据 A 复制出了进程 B，一开始时，A 和 B 共享同一片地址空间
共享同一片地址空间，只有当某个进程需要 对内存进行写操作时，才会分配新的内存空间来存储这个被修改的变量
这种方法就节约了 新进程重新分配和复制地址空间的开销。
3.线程的实现
线程（Thread）的基本概念
线程是什么
线程的定义
线程最直接的理解就是"轻量级进程"
是一个基本的 CPU 执行单元
是程序执行流的最小单元
线程是进程中的一个实体，是被系统独立调度和分派的基本单位
线程的组成
线程ID
程序计数器
寄存器集合
堆栈
线程的特点
线程是 CPU 调度的基本单位
1、线程使用所在进程的地址空间，不需要额外的大规模资源分配
2、线程需要独占 CPU 来执行指令，因此需要满足 CPU 状态保存的需求
线程是进程中的一个实体，是被系统独立调度和分派的基本单位
线程间关系
（1）实体之间可以并发执行
（2）实体之间共享相同的地址空间
线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源
可与同属一个进程的其他线程共享进程所拥有的全部资源
一个线程可以创建和撤销另一个线程
同一进程中的多个线程之间可以并发执行
由于线程之间的相互制约，致使线程在运行中呈现出间断性
线程的状态
就绪态
运行态
阻塞态（等待态）
三种基本状态
TCB线程控制块
类似PCB
为什么引入线程？
引入线程的目的则是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。
线程与进程的比较
王道书
1）调度
在传统的操作系统中，拥有资源和独立调度的基本单位都是进程
在引入线程的 操作系统中，线程是独立调度的基本单位，进程是拥有资源的基本单位。
在同一进程中，线程的切换不会引起进程切换
在不同进程中进行线程切换，如从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。
2）拥有资源
不论是传统操作系统还是设有线程的操作系统，进程都是拥有资源的基本单 位
线程不拥有系统资源（也有一点儿必不可少的资源），但线程可以访问其隶属进程的系统资源
3）并发性
在引入线程的操作系统中，不仅进程之间可以并发执行，而且多个线程之间也 可以并发执行，从而使操作系统具有更好的并发性，提高了系统的吞吐量。
4）系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设 备等，因此操作系统所付出的开销远大于创建或撤销线程时的开销。
类似地，在进行进程切换时，涉及当前执行进程CPU环境的保存及新调度到进程 CPU环境的设置
而线程切换时只需保存和设置少量寄存器内容，开销很小
此外，由于同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信非常容易实现，甚至无须操作系统的干预。
5）地址空间和其他资源（如打开的文件）
进程的地址空间之间互相独立，同一进程的各 线程间共享进程的资源，某进程内的线程对于其他进程不可见。
6）通信方面
进程间通信（IPC）需要进程同步和互斥手段的辅助，以保证数据的一致性， 而线程间可以直接读/写进程数据段（如全局变量）来进行通信。
简略
进程
1、进程是资源分配单位
2、进程拥有一个完整的资源平台
线程
1、线程是CPU调度单位
2、线程只独享指令流执行的必要资源
如寄存器和栈
3、线程能减少并发执行的时间和空间开销
4、线程的创建时间比进程短
5、线程的终止时间比进程短
6、同一进程内的线程切换时间比进程短
7、由于同一进程的各线程间共享内存和文件资源， 线程可不通过内核进行直接通信
用户线程
定义
线程功能由一组用户级的线程库函数来完成线程的管理
包括线程的创建、终止、 同步和调度等
特征
1、不依赖操作系统的内核来实现， 可用于不支持线程的多进程操作系统
1、内核不了解用户线程的存在
2、可用于不支持线程的多进程OS
2、在用户空间形成线程机制
3、同一进程内的用户线程切换速度快
在用户态就可以实现 无需切换核心态
4、允许每个进程拥有自己的线程调度算法
缺点
1、线程发起系统调用后，其所在的整个进程进入等待状态
2、不支持基于线程的处理机抢占
3、只能按进程分配CPU时间
内核线程
定义
由内核通过系统调用实现的线程机制
由内核完成线程的创建、终止和管理
特征
1、由内核维护 PCB 和 TCB
2、线程执行系统调用而被阻塞不影响其他线程
3、线程的创建、终止和切换相对开销较大
涉及到内核态切换
4、内核以线程为单位进行 CPU 时间分配
4.进程与线程的组织与控制
5.进程间通信
是什么
一个进程请求使用另一个进程提供的数据
为什么
为什么只有进程间通信，而不存在线程间通信？
进程间存在数据隔离
线程若处在同一进程，共享该进程的数据，因此无需通信
怎么做
共享内存
定义及其示意图
通过修改页表，使得两个进程的地址空间共享同一片物理空间
从而让这两个进程在 这片共享内存中分配。
示意图
特点
1、在通信建立时需要操作系统参与
2、通信建立后不需要操作系统参与
进程直接通过读写内存来实现通信
消息传递
定义
在内核中提供专门的消息传递队列，来为进程通信服务
分类及其示意图
1、直接通过内核
示意图
2、通过内核中的mailbox 信箱
示意图
特点
每一次传送信息，都会发生用户态向内核态的切换
系统调用发起时机：每次通信时。
管道
定义
A 与 B 通信时，由系统指定特地的管道文件作为双方通信的管道，两进程通过对该文 件的读写来实现通信。
示意图
特点
管道建立时发生用户态向内核态的切换
读写管道本身就是读写文件，需要系统调用即内核参与
系统调用发起时机：读写管道时
三者区别
1、内核参与的时机
1、建立时参与
共享内存
通信建立时参与
2、每次通信都参与
消息传递
消息通过内核传递
管道
相当于读写文件
(二)CPU 调度与上下文切换
1.调度的基本概念
定义
处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行， 以实现进程并发地执行。
CPU调度与进程切换的联系
CPU调度
目标
选择合适的就绪进程进行切换
对象
就绪队列中进程的 PCB
即进程寄存器和内存信息的映射
进程切换
目标
根据选定的就绪进程信息，进行必要的上下文保存与恢复后，让 CPU 执行该 进程。
对象
寄存器和内存本身
联系
处理机调度为进程切换提供目标进程
调度的层次
作业调度（高级调度）
（关 键词：外存调入内存，创建进程，分配资源）
作业调度的主要功能是根据作业控制块中的信息，审查系统能否满 足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存， 并为它们创建进程、分配必要的资源
然后再将新创建的进程插入就绪队列，准备执行。
中级调度（中程调度、内存调度）
内存中不能有太多的进程，把进程从内存移到外存， 当内存有足够空间时，再将合适的进程换入内存，等待进程调度
中级调度实际上就是存储 器管理中的对调功能
进程调度（低级调度）
在内存中处于就绪态的进程中选择一个分配处理机运行
extra：作业调度和中级调度的区别
作业调度在一个进程的生命周期中只有一次
作业调度是第一次为作业分配内存和其它资源，此后作业才被 称为进程
而中级调度只会引发进程状态的 变化（挂起与非挂起）
三者示意图
2.调度的目标
3.调度的实现
调度器/调度程序(scheduler)
调度的时机与调度方式 (抢占式/非抢占式)
非抢占式调度
定义
一个进程除非运行结束或者自己主动放弃 CPU，否则不会被其它进程抢占 CPU
调度时机
当前运行进程运行结束或者主动放弃 CPU 时
调度发起者
当前运行进程
放弃 CPU 的原因
1、等待某些事件的发生
如使用 I/O 设备后等待 I/O 完成
2、等待某些资源的满足
如进行一次 P 操作时信号量不满足执行条件
特点
1、调度不太频繁
CPU 利用率一般更高
2、实时性比较差
一般用于批处理操作系统
不能用于大部分实时操作系 统和分时操作系统。
3、系统开销小。
注意
在非抢占式调度下，进程不会出现从运行态向就绪态的切换
进程退出运行态只可能 进入退出态或者阻塞态。
抢占式调度
定义
进程在执行过程中，也可能因为时间片用完或者有更高优先级进程进入就绪态而被抢 占 CPU
调度时机
1、当前进程主动放弃 CPU
（运行结束或者进入等待态）
2、当前进程时间片用完或有更高优先级的进程进入就绪态。
调度发起者
一般为操作系统
特点
频繁调度，实时性强
调度的时机
引发调度的事件
1、非抢占式调度下，当前进程运行结束或进入等待态
2、抢占式调度下，当前进程时间片用完或有更高优先级的进程进入就绪态
不能调度的情况
1、当前进程处于中断处理过程中
（中断处理不属于任何一个进程，不应被 切换）
2、进程在操作系统内核程序临界区中；
3、屏蔽中断过程中
4、原子操作过程中
调度相关参数
CPU 利用率
用于进程实际运行的时间 / 总时间
系统吞吐率
单位时间完成作业的个数
作业周转时间
作业从 提交 到 完成 的时间间隔
平均周转时间
（作业 1 周转时间+作业 2 周转时间+......+作业 n 周转时间）/n。
带权周转时间
作业周转时间/作业实际运行时间
平均带权周转时间
（作业 1 带权周转时间+作业 2 带权周转时间+......+作业 n 带权周转时 间）/n
等待时间
进程从创建到完成，处于就绪状态的时间之和
该参数不影响作业执行时间和输 入/输出时间，只取决于调度算法
响应时间
用户提交请求到系统首次响应的时间间隔
闲逛进程
内核级线程与用户级线程调度
4.典型调度算法
先来先服务调度算法 （FCFS）
特点
非剥夺算法
优点
算法简单
对长作业有利
有利于CPU繁忙型作业
缺点
效率低
对短作业不利（相对于SJF和高响应比）
不利于I/O繁忙型作业
评价
不公平
平均等待时间较差
短作业(短进程、短线程) 优先调度算法（SJF）
优点
平均等待时间、平均周转时间最少
缺点
对长作业不利
未考虑作业的紧迫程度
评价
不公平
平均周转时间最小
需要精准预测计算时间
可能导致饥饿
优先级调度算法
分类
剥夺式算法
非剥夺式算法
进程优先级是否可变分类：
静态优先级
优先级在创建进程后优先级不改变
动态优先级
优先级在进程运行过程中动态变化
优先级原则
系统 > 用户
交互 > 非交互
I/O型 > 计算型
高响应比优先调度算法
响应比
（等待时间+执行时间）/ 执行时间
特点
执行时间相同，等待越久，响应比越高
克服了饥饿
兼顾了长作业
时间片轮转调度算法
类型
剥夺式算法
特点
深受时间片影响
时间片过大
退化为FCFS
时间片过小
进程频繁切换，CPU开销增大
时间片由以下因素确定
1、系统响应时间
2、就绪队列中的进程数目
3、系统的处理能力
评价
公平
平均等待时间较差
多级反馈队列调度算法 （MLFQ）
类型
抢占式算法
多种算法集成
FCFS+时间片+优先级调度
思想
1、只有当前等待队列不为空的、最高优先级的队列会被分配时间片
只有高优先级的等待队列为空时， 才给次高优先级的等待队列中的进程分配时间片
2、若当前时间片执行时，有更高优先级的进程进入等待队列，会剥夺当前进程资源，将其重新放回该队列末尾；转而给高优先级进程分配时间片
3、得到时间片的进程用完时间片后，若仍然没执行完，进入次一级优先队列等待
体现
同一队列中
FCFS
时间片
不同队列间
优先级调度
特点
时间片随优先级而改变
高优先级的时间片长度小于低优先级
CPU密集型进程优先级下降很快
I/O密集型进程优先级停留在高优先级
5.上下文及其切换机制
(三)同步与互斥
1.进程同步、互斥及其相关概念
进程同步
是什么
并发的多个进程（线程）需要按照某种次序执行某些程序以合作完成某种功能的 制约关系。
又称直接制约关系
为什么
为了协调进程间互相制约的关系
临界资源
多道程序系统中存在许多进程，它们共享各种资源，然而有很多资源一次只能供 一个进程使用
临界区
临界区指的是一个访问共用资源的程序片段 （例如：共用设备或是共用存储器）
而这些共用资源又无法同时被多个线程访问
有线程进入临界区段时，其他线程或 是进程必须等待
2.临界区互斥
临界区的访问规则
1、空闲让进
没有进程在临界区时，任何进程可进入
2、忙则等待
有进程在临界区时，其他进程均不能进入临界区
3、有限等待
等待进入临界区的进程不能无限期等待
4、让权等待
不能进入临界区的进程，应释放 CPU（如转换到阻塞状态）
临界区实现方法
实现临界区互斥的基本方法
软件实现方法 （均未实现让权等待） （复杂）
单标志法
满足忙则等待
不符合空闲让进
双标志法先检查
若程序并发执行，可能会同时进入临界区
不满足忙则等待
双标志法后检查
不满足空闲让进
Peterson's Algorithm
硬件实现方法
中断屏蔽方法
硬件指令方法 （原子操作法）
1、test-and-set
2、exchange
3.锁
基本概念
保证线程持续运行的一种机制
锁的本质是由一位内存、一个阻塞队列和申请锁、释放锁的方法组成的数据结构
锁机制
总览
忙则等待
无忙则等待
特点
对于任何一个锁来说，只有第一个申请到锁的线程才可 以继续运行
除非申请到锁的进程主动释放锁
否则其它的进程都会被阻塞并且进入该锁的 阻塞队列
优点
1、适用于单处理器或共享主存的多处理器中任意数量的进程同步
2、简单并容易证明
3、支持多临界区
缺点
1、忙则等待会消耗处理器
2、可能导致饥饿
3、可能会导致死锁
4.信号量
什么是信号量
信号量是操作系统提供的一种协调共享资源访问的方法
信号量表示系统资源的数量
信号量的组成
整形 (sem)变量
原子操作 （PV操作前都会上锁）
P()
sem 减 1
如 sem<0, 进入等待, 否则继续
V()
sem 加 1
如 sem≤0,唤醒一个等待进程
信号量的特性
只能通过 P()和 V()修改
信号量的操作是原子操作
P()可能使进程阻塞
V()不可能使进程阻塞
5.管程与条件变量
管程例题
管程
为什么会出现管程
1、信号量机制不足
信号量程序编写困难，易出错
管程是什么
【管程】是一种用于【多线程】【 互斥访问】 【共享资源】的【程序结构】（【由编程语言支持】）
它需要上锁
它可以实现高级的同步机制
它由【有关资源的数据结构】和在 【其上的定义的一组过程】组成
如何实现、使用
1、采用面向对象方法，简化了线程间的同步控制，因此管程通常是【语言级提供的功能】
进程只能通过调用管程中的过程间接访问管程中的数据结构
2、任一时刻最多只有一个线程执行管程代码
特别注意点
已经进入管程的线程，如果被阻塞了； 它可能把管程的使用权让给其他线程 （因此同一时间可能有多个进程在管程的临界区中，但是只能有一个进程执行）
因为管程在Wait()操作中，开头会上锁，但过程中会开锁
3、正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复
管程的组成
一个锁 +n 个条件变量
条件变量
条件变量是什么
条件变量是管程内的等待机制
为什么要用条件变量
进入管程的线程因资源被占用而进入等待状态
每个条件变量表示一种等待原因，对应一个 等待队列。
怎么做
Wait()操作
1、将自己阻塞在等待队列中
2、唤醒一个等待者或释放管程的互斥访问
Signal()操作
将等待队列中的一个线程唤醒
如果等待队列为空，则等同空操作
这里区别于V()操作，V()操作误用会让系统误认为有很多资源； Signal()则没有影响
6.经典同步问题
生产者-消费者问题
哲学家进餐问题
读者-写者问题
读者优先
写者优先
公平对待
(四)死锁
1.死锁的概念
死锁的定义
由于竞争资源或者通信关系，两个或更多线程在执行中出现，永远相互等待只 能由其他进程引发的事件。
补充：进程访问资源的流程
请求/获取
申请空闲资源
使用/占用
进程占用资源
释放
资源状态由占用变成空闲
死锁的策略
1.死锁预防
破坏死锁产生的四个必要条件
2.死锁避免
通过避免系统进入不安全状态来避免死锁
3.死锁检测和解除
允许死锁发生，增加死锁检测机制，并且通过某些方式解除死锁
死锁的必要条件
互斥
任何时刻只能有一个进程使用一个资源实例
持有并等待
进程保持至少一个资源，并正在等待获取其他进程持有的资源
非剥夺
资源只能在进程使用后自愿释放
循环等待
2.死锁预防 （确保系统永远不会进入死锁状态）
策略
限制申请方式
死锁预防针对死锁的四个必要条件的操作
互斥预防
把共享资源封装成可同时访问
持有并等待
要求进程一次申请完所有所需资源
非剥夺
如进程请求不能立即分配的资源，则释放已占有资源
循环等待
对资源排序，要求进程按顺序请求资源
3.死锁避免 （只允许不会出现死锁的进程请求资源）
死锁避免的目的
避免死锁是避免 系统处于不安全状态
基本概念
安全状态
安全状态与死锁的关系
系统处于安全状态，一定没有死锁
系统处于不安全状态，可能出现死锁
银行家算法（待补）
4.死锁检测和解除
死锁检测
死锁检测的理念
死锁检测算法的使用
死锁检测算法的使用取决于： 1、死锁多久可能会发生， 2、多少进程需要被回滚。
死锁解除
进程终止
策略
终止所有的死锁进程
一次终止一个死锁进程
终止进程的考量
1、进程的优先级
2、以运行时间、还需运行的时间
3、进程已经占有的资源
4、进程还需要的资源
5、终止进程的数目
资源抢占
策略
最小成本目标
进程回退
策略
返回到安全状态
内存管理
(一)内存管理基础
1.内存管理的基本概念
基本概念
什么是内存管理
软件运行时对计算机内存资源的分配和使用的技术
为什么要内存管理？（目的）
最主要的目的是如何 高效，快速的分配，并且在适当的时候释放和回收内存资源。
怎么做
1、如何为每一个进程分配对应的物理内存空间
2、如何为每一个进程的 各个模块分配地址空间
3：如何实现进程的逻辑地址空间与物理地址的对应
内存管理的特征
抽象
进程通过逻辑地址访问自身的内存地址空间
保护
每个进程有自己的独立地址空间
共享
进程间也可以通过某些方式共享相同的物理内存。
虚拟化
进程可以访问比物理内存空间更大的虚拟内存空间
程序装入与链接
从高级语言源文件到进程执行完毕的步骤
预处理
编译
汇编
链接
装载
运行
主要步骤
编译
由编译程序将用户源代码编译成若干目标模块
链接
将编译后形成的一组目标模块及其所需要的库函数链接在一起，形成一个完整的装入模块
装入
将装入模块装入到内存
链接的分类
静态链接
装入时动态链接
运行时动态链接
装入的分类
绝对装入
描述
逻辑地址 = 物理地址
特点
适用于单道程序
可重定位装入/静态重定位
描述
逻辑地址与物理地址简单地映射
特点
0、在装载的时候形成逻辑地址
1、装入内存时必须一次性分配给它需要的所有空间（连续的）
2、一旦装入内存，位置不可移动，也不能再申请空间
动态运行装入
描述
利用重定位寄存器实现逻辑地址与物理地址的映射关系
MMU实现逻辑地址到物理地址的转换
特点
0、运行的时候形成逻辑地址
1、映射机制本身由硬件机制实现， 映射关系的确定需要软件参与
2、同一个进程不需要分配连续的内存空间
地址检查
地址生成的过程
逻辑地址与物理地址空间
逻辑地址空间
在 CPU 运行的进程看到的地址， 起始地址 0， 直到 MAXprog
逻辑地址和虚拟地址什么关系？
物理地址空间
硬件支持的地址空间： 起始地址 0， 直到 MAXmem
内存保护
2.连续分配管理方式
内存分配的基础概念
连续内存分配
给进程分配一块不小于指定大小的连续的物理内存区域
内存碎片
不能被充分利用的一部分空闲内存
外部碎片
分配单元之间的未被使用内存
可以通过紧凑来解决
内部碎片
分配单元内部的未被使用内存
动态分区分配
概念
当程序被加载执行时，分配一个进程指定大小的分区(块、内存块)。
分区的地址是 连续的
操作系统需要维护的数据结构
1、所有进程的已分配分区
2、空闲分区
动态分区分配策略 及其特点
动态分区分配特点单独总结 （选择题考点）
缺点
【低地址】产生许多【小碎片】
最先匹配 （首次适应算法）
产生【最多】的【不必要小碎片】
最佳匹配
会使得很快【没有大块内存】使用
最坏匹配
优点
高地址有大块的内存
最先匹配 （首次适应算法）
避免大块内存被拆分
最佳匹配
中等大小分配较多时效果好
最坏匹配
各动态分区匹配算法详情
最先匹配（首次适应算法）
策略
1、空闲分区按地址从低到高链接
升序
2、分配内存时按顺序找到第一个可以满足要求的空闲分区
3、释放分区时检查是否可与临近的空闲分区合并
特点
优点
最简单
通常也是最好、最快的
高地址空间有大块的内存
缺点
分配大块时较慢
会使得内存低地址部分出现很多小的空闲分区，会增加后续的开销
最佳匹配（最佳适应算法）
策略
1、空闲分区按容量大小从低到高链接
升序
2、分配内存时按顺序找到第一个可以满足要求的空闲分区
3、释放分区时检查是否可与临近的空闲分区合并
特点
优点
较小尺寸分配较多时，效果很好
可避免大块内存被拆分
可减小外部碎片的大小
相对简单
缺点
释放分区较慢
容易产生外部碎片
会产生最多的外部碎片
最坏匹配（最坏适应算法）
策略
1、空闲分区按容量大小从高到低链接
降序
2、分配内存时按顺序找到第一个可以满足要求的空闲分区
3、释放分区时检查是否可与临近的空闲分区合并
特点
优点
中等大小分配较多时，效果很好
避免出现太多的小碎片
缺点
释放分区较慢
容易产生外部碎片
会很快使得没有可用的大内存块
邻近适应算法（循环首次适应算法）
策略
1、从首次适应算法演化而来
2、分配内存时从上次查找结束的位置开始
3、释放分区时检查是否可与临近的空闲分区合并
特点
通常比首次适应算法差
碎片整理
概念
通过调整进程占用的分区位置来减少或避免分区碎片
方式
紧凑
概念
通过移动分配给进程的内存分区，以合并外部碎片
条件
所有的应用程序可动态重定位
分区对换
概念
通过抢占并回收处于等待状态进程的分区，以增大可用内存空间
连续内存分配方式的缺点
1、分配给程序的物理内存必须连续
2、存在外碎片和内碎片
3、内存分配的动态修改困难
4、内存利用率较低
3.非连续分配管理方式
0.非连续分配的基本概念
非连续分配的设计目标
提高内存利用效率和管理灵活性
非连续分配的理念
1、允许一个程序的使用非连续的物理地址空间
2、允许共享代码与数据
3、支持动态加载和动态链接
非连续分配需要解决的问题
1、如何实现虚拟地址和物理地址的转换
1、硬件实现
灵活，开销大
2、软件实现
够用，开销小
2、如何选择非连续分配中的内存分块的大小
段式存储管理
页式存储管理
1.分页管理方式
1、为什么引入分页存储管理？
固定分区、动态分区不能满足提高内存利用率的需求
固定分区会产生内部碎片
动态分区会产生外部碎片
我们希望避免内存碎片的产生！提高内存利用率
2、分页存储管理的思想
将 主存和进程 都按大小固定且相等的 物理块 进行划分
块相对较小
比固定分区要小很多
进程按 块 申请内存，不会产生外部碎片； 仅可能平均产生半块页内碎片
3、分页存储的几个基本概念、 及其主要问题
1、页（号）、页框、块 （重点区分）
页（号）：进程中的块
页框：内存中的块
块：外存中的块
2、逻辑地址结构
3、页表
目的
记录所有 页（号） 到 页框 的映射
组成
页表由一条条 页表项 组成 （下面是页表项的组成）
逻辑页号（页号）
表示该逻辑页在进程中的位置
物理页帧号（页框号）
表示该逻辑页对应的物理页帧号
再加上页内偏移量可以得到物理地址
物理地址 = 页框 + 页内偏移量
存在位
表示该逻辑页是否已经存在于内存中
修改位
表示该逻辑页是否经过了修改
引用位
表示该逻辑页最近是否被使用过
4、实际地址 （地址变换）
根本
最终会映射到内存上
操作
实际地址 = 页框 + 页内偏移量
5、分页管理的主要问题
1、每次访存都需要进行逻辑地址->物理地址的转换， 如果地址转换过慢，会影响访存速度
通过快表TLB解决
2、每个进程引入页表用于存储映射信息， 页表不能过大，否则会影响内存利用率
通过多级页表解决
4、引入快表 TLB 的分页管理方式
1、快表TLB是什么
快表是相联存储器
可以按照存储内容存取
位于Cache中
读写速度快
2、为什么引入快表
1、引入快表前的问题
1、每次访问数据或指令需要访存2次
1、访问内存中的页表，确定物理地址
2、访问物理地址，得到数据或指令
2、相较于通常执行指令的速度慢了一半
2、引入快表的目的
加快地址映射
3、引入快表TLB之后一些名称变化
1、页表（内存中）
称为慢表
2、快表TLB（位于Cache中）
4、引入快表TLB后的地址变换过程
1、CPU给出逻辑地址后，查找快表
2、若快表命中，直接将 页框 和 页内偏移量 组合得到物理地址
一次访存即可
3、若快表未命中，则查找页表（慢表）， 读取页表项，组合得到物理地址， 并将页表项调入快表中
两次访存
若快表已满需要页面替换算法
5、多级页表
1、多级页表是什么
2、为什么引入多级页表
节约内存空间，提高内存利用率
对单页表结构来说，逻辑页即使不存在于内存中，也必须建立对 应的页表项防止访问出现问题
而在多级页表结构中，只要第一级页表对应的页目录项中的 存在位是 0
那么与此相关的第二级页表等均不再需要保存也不会出现问题，因此可以大量 节约内存空间
6、分页管理的优点
内存利用和优化转移到后备存储
2.分段管理方式
分段的基础概念
分段的思想
按照程序自身的逻辑划分为若干个段
每个段有一个段名
每段从0开始编址
分段的优点
相较于分页更容易实现信息的共享和保护 （内存保护）
对于不可修改的代码（非临界资源） 是可以被共享的
页表不是按逻辑划分因此部分页面中的内容不能被共享
3.段页式管理方式
思想
段表+页表
优点
集合了分页和分段的优点
(二)虚拟内存管理
1.虚拟内存基本概念
1、存储器层次结构
2、计算机应对内存空间不够用的方法
覆盖（overlay） （交换程序的模块）
描述
应用程序手动把需要的指令和数据保存在内存中
思路
依据程序逻辑结构，将程序划分为若干功能相对独立的模块
将不会同时执行的模块 共享同一块内存区域
必要部分（常用功能）的代码和数据常驻内存
可选部分
（不常用功 能）放在其他程序模块中,只在需要用到时装入内存
不存在调用关系的模块可相互覆盖， 共用同一块内存区域。
不足
增加了编程的复杂程度
需程序员划分功能模块，并确定模块间的覆盖关系
增加了执行时间
外存装入覆盖模块
时间换空间
交换（swapping） （交换整个进程）
描述
操作系统自动把暂时不能执行的程序保存到外存中
思路
实现方法
可将暂时不能运行的程序放到外存
换入换出的基本单位
整个进程的地址空间
换出
把一个进程的整个地址空间保存到外存
换入
将外存中某进程的地址空间读入到内存
虚拟存储
描述
在有限容量的内存中，以页为单位自动装入更多更大的程序
目标
结合覆盖和交换的优点
3、虚拟存储技术的目标
定义
只把部分程序放到内存中，从而运行比物理内存大的程序
这个过程由操作系统自动 完成，无需程序员的干涉
特点
实现进程在内存与外存之间的交换，从而获得更多的空闲内存空间，在内存和外存之 间只交换进程的部分内容
4、虚拟页式存储管理
虚拟页式存储管理的内容
1、页式管理
2、请求调页
3、页面置换
虚拟页式存储中的页表项结构
总览图
1、逻辑页号
表示该逻辑页在进程中的位置
2、访问位
该页面是否被访问过 （读或写）
页面置换算法的依据之一
3、修改位
在内存中该页面是否被修改过
页面置换算法需要考虑的因素之一
4、保护位
该页是否允许访问方式
5、驻留位
该页是否在内存中
1 表示存在
0表示在外存中
访问该页面会导致缺页异常
6、物理页帧号（页框号）
表示该逻辑页对应的物理页帧号
缺页异常的处理流程
虚拟页式存储管理的性能
虚拟页式存储中的外存管理
1、如何保存未被映射的页？
交换空间（磁盘或文件）
采用特殊格式存储未被映射的页面
2、虚拟页式存储中的外存选择
代码段
可执行二进制文件
动态加载的共享库程序段
动态调用的库文件
其他段
交换空间
2.请求分页管理方式
3.页框分配
全局置换算法
思路
全局置换算法为进程分配可变数目的物理页面
全局置换算法要解决的问题
进程在不同阶段的内存需求是变化的，分配给进程的内存也需 要在不同阶段有所变化
全局置换算法需要确定分配给进程的物理页面数
CPU 利用率与并发进程数的关系
总览图
1、进程数少时，提高并发进程数，可提高 CPU 利用率
2、并 发进程导致内存访问增加，并发进程的内存访问会降低了访存的局部性特征
3、局部性特征的 下降会导致缺页率上升和 CPU 利用率下降
页框不够大后CPU利用率降低
工作集置换算法
工作集
是什么
工作集是指在某段时间间隔内，进程要访问的页面 集合。
例子
怎么做
组成
常驻集
是什么
在当前时刻，进程实际驻留在内存当中的页面集合
取决于什么
系统分配给进程的物理页面数目
页面置换算法
工作集置换算法
核心思想
换出不在工作集中的页面
算法描述
例子
抖动
定义
在页面置换过程中，一种最糟糕的情形是， 刚刚换出的页面马上又要换入主存， 刚刚换入的页面马上又要换出主存， 这种频繁的页面调度行为称为抖动
原因
某个进程频繁访问的页面数目高于可用的物理页帧数目
僧多粥少
1、进程物理页面太少，不能包含工作集
2、造成大量缺页，频繁置换
3、进程运行速度变慢
虚拟内存技术可在内存中保留更多的进程以提高系统效率。
在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。
然而，如果管理不当，那么处理机的大部分时间都将用于交换块，即请求调入页面的操作，而不是执行进程的指令，因此会大大降低系统效率。
4.页面置换算法
1、最佳置换算法(OPT)
思想
置换在未来最长时间不访问的页面
实现
缺页时，计算内存中每个逻辑页面的下一次访问时间
算法特征
缺页最少，是理想情况
问题
实际系统中无法实现
2、先进先出置换算法(FIFO)
思路
选择在内存驻留时间最长的页面进行置换
实现
维护一个记录所有位于内存中的逻辑页面链表，链表元素按驻留内存的时间排序
链 首最长，链尾最短
出现缺页时，选择链首页面进行置换，新页面加到链尾
特点
实现简单，性能较差
3、最近最少使用置换算法(LRU)
思路
选择最长时间没有被引用的页面进行置换
实现
缺页时，计算内存中每个逻辑页面的上一次访问时间，选择上一次使用到当前时间最 长的页面。
4、时钟置换算法(CLOCK)
数据结构
在页表项中增加访问位，描述页面在过去一段时间的内访问情况
各页面组织成 环形链表
指针指向最先调入的页面
算法实现
页面装入内存时，访问位初始化为 0
访问页面（读/写)时，访问位置 1
缺页时，从指针当前位置顺序检查环形链表
访问位为 0，则置换该页
访问位为 1，则访 问位置 0，并指针移动到下一个页面，直到找到可置换的页面
5、页面置换算法分析
Belady 现象
采用 FIFO 等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象
可能包含 belady 的算法
FIFO
CLOCK
不包含 belady 的算法
LRU
OPT
5.内存映射文件(Memory-Mapped Flies)
6.虚拟存储器性能的影响因素及改进方法
文件管理
(一)文件系统基础
1.文件系统相关的概念概念
文件
文件是什么
由字节序列构成的数据项集合
文件是文件系统的基本数据单位
文件名是文件的标识符号
用户视角
文件是一个可持久化的数据结构
操作系统视角
所有相关信息在磁盘上集合
文件的属性
名称
文件系统标识某个文件的唯一标识，文件名唯一
位置
指向设备和设备上文件的指针
文件有什么
数据
分类、索引
对数据划分
权限
文件系统
文件系统是什么
文件系统是OS中管理持久性数据的子系统，提供数据存储和访问功能
文件系统的功能
1、分配文件磁盘空间
管理文件块
位置
顺序
管理空闲空间
位置
分配算法
策略
2、管理文件集合
定位
文件及其内容
命名
通过名字找到文件
文件系统结构
文件 组织方式
3、数据可靠和安全
2.文件元数据和 索引节点inode
总览示意图及解析
示意图
解析
1、关于【目录文件】 【目录项】
目录文件
是一种特殊的文件，它在磁盘上的内容是一条一条目录项
目录项
文件名称 + inode编号
2、关于【inode表/块】 【inode】
inode表/块 （索引节点表）
磁盘上的一张表格
通常在文件系统被挂载时调入内存
表格的每一项是 inode编号 : inode节点
inode （索引节点）
记录了该文件除 目录项信息（即文件名称、inode编号） 以外的【文件元信息】
文件的元信息
3、打开文件的流程
1、系统找到这个文件名，及其对应的inode编号
2、根据inode编号去inode表中找对应的inode
3、根据inode中的信息，去磁盘对应位置找到文件
索引节点inode
定义
inode，用来记录文件的元信息
inode 编号
文件大小
访问权 限
创建时间
修改时间
数据在磁盘的位置等
索引节点是文件的唯一标识
一个文件对应一个索引节点
可以根据索引节点访问该文件的全部信息
索引节点和文件一一对应，它们都被存储在磁盘中
其他相关定义
索引节点表
磁盘中维护的一张表格，记录了索引节点号与索引节点磁盘位置的对应关系
通常在文件系统挂载时被转入内存
因此通常在访问表的时候不需要访问外存
索引节点号
索引节点的编号
inode的引用计数
指向同一个inode的用户目录项的个数
示意图
根据目录项中的索引结点编号，我们可以找到索引结点inode （目录项存放文件名+索引结点编号）
3.文件的操作 建立，删除，打开，关闭，读，写。
打开文件
文件访问模式
进程访问文件数据前必须先“打开”文件
内核跟踪进程打开的所有文件
操作系统为每个进程维护一个打开文件表
文件描述符是打开文件的标识
打开文件的数据结构
文件描述符
对每个进程来说每个被打开的文件都有一个文件描述符， 是一个非负整数
打开文件表
每个进程一个进程打开文件表，其索引为进程对应的文件描述符
一个系统级的打开文件表
有文件被打开时，文件卷就不能被卸载【文件被打开时不能删除】
windows下的例子
文件描述符
是什么
操作系统在打开文件表中维护的打开文件状态和信息
组成
文件指针
最近一次读写位置
每个进程分别维护自己的打开文件指针
文件打开计数
当前打开文件的次数
最后一个进程关闭文件时，将其从打开文件表中移除
文件的磁盘位置
缓存数据访问信息
访问权限
每个进程的文件访问模式信息
几个值得注意的点
1、每个进程的打开文件表会记录文件指针
用来表示各进程分别访问文件的位置
2、系统级的打开文件表有一个引用计数，表示打开该文件的进程个数
只有引用计数变为0时，才将该文 件从表项中移除，并从内存中移除对应的数据结构
3、文件描述符是每个进程各自拥有的
同一个打开文件在不同进程中可能文件描述符不同
4.文件共享
5.文件的逻辑结构与物理结构
0.两者关系示意图
物理结构交换信息以扇区为单位
通常认为一个扇区512B
逻辑结构以数据块为交换单位 （文件系统操作的就是逻辑上的块）
将多个物理扇区绑定为一个数据块
1.文件的逻辑结构
定义
用户视角看到的文件的数据组织方式
无结构文件（流式文件）
对文件内信息不再划分单位，它是依次 的一串字符流构成的文件。
有结构文件（记录式文件）
用户把文件内的信息按逻辑上独立的 含义划分信息单位，每个单位称为一个逻辑记录（简称记录）
所 有记录通常都是描述一个实体集的，有着相同或不同数目的数据项， 记录的长度可分为定长和不定长记录两类。
常见的组织形式
顺序文件
文件按一条一条记录的顺序排列，分为串结构和顺序结构，按照 记录某关键字顺序排列的文件为顺序结构，反之为串结构
索引文件
为每一条记录建立索引，可以快速访问某一条记录的位置
索引顺序文件
将记录分为若干组，每组为顺序结构记录，再为每一个组建 立索引
直接文件或散列文件
记录的位置由其键值直接确定或者由其散列值确定
2.文件的物理结构
6.文件实现
0.什么叫文件实现？
1、文件分配
2、文件存储空间的管理
1.文件分配
什么是文件分配？
借助inode把文件的逻辑地址转化为磁盘物理地 址。
文件分配的重点
文件数据存取的基本单位是数据块
1、如何把分布在不同数据块上的文件数据组织成一个逻辑上的整体
2、如何把一个文件的逻辑地址转化为对应的数据块号+块内地址
文件分配的方式
连续分配
定义
文件在磁盘上占据连续的数据块。类似于数组方法
inode 或 FCB 中的磁盘数据信息
开始块的地址和文件分配区域的长度
优缺点
实现简单、只适用于长度固定的文件、增删文件会产生外部碎片
优点
文件读取表现好
高效的顺序和随机访问
缺点
碎片（外部）
文件增长问题
链式分配
显式链接
定义
用于链接文件各数据块的指针，从每个数据块中的块末尾中提取出来，显式地存 放在内存的一张链表中。该表在整个磁盘仅设置一张，每个表项中存放对应块的下一块链接 指针，即下一个盘块号。这张表叫做文件分配表（FAT）。
FAT表存在内存中
FAT表不仅记录文件的分配信息，并且还“兼职”了空闲块的管理。
inode 或 FCB 中的磁盘地址信息
文件的第一个盘块号
优缺点
进行随机查找操作的时候，不用进行那么多次磁盘访问，只需要访问内存中的链表就可 以了
无法快速访问任意块
丢失了任何一块的信息则 所有信息均会丢失
隐式链接
定义
每个文件代表一个磁盘块的链表，在每个块的结尾保存下一块的地址
inode 或 FCB 中的磁盘地址信息
文件的开始块和结束块
优缺点
优点
可以灵活改变文件长度
缺点
无法快速访问任意块
丢失了任何一块的信息则 所有信息均会丢失
索引分配
定义
为文件分配索引块（也是一种数据块），在索引块中记录文件信息所存储的数据块
inode 或 FCB 中的磁盘地址信息
索引块的地址
文件头包含了索引数据块指针
优缺点
优点
创建、增大、缩小很容易
没有碎片
支持直接访问
缺点
当文件很小时，存储索引的开销
如何处理大文件？
具体细节
大文件的索引分配
链式索引块 (IB+IB+…)
多级索引块(IB*IB *…)
UFS多级索引分配
示意图
文件头包含13个指针
10 个指针指向数据块 第11个指针指向索引块 第12个指针指向二级索引块 第13个指针指向三级索引块
效果
提高了文件大小限制阈值
动态分配数据块，文件扩展很容易
小文件开销小
只为大文件分配间接数据块，大文件在访问数 据块时需要大量查询
2.文件存储空间管理
文件卷
定义
把磁盘上的一部分区域组织在一起，作为一个逻辑上的分区，供同一个文件系统使用
文件卷分区
示意图
组织结构
超级块
用来存储文件系统的详细信息
比如块个数、块大小、空闲块等等。一个文件系统 对应一个超级块。
注意一个细节：文件系统被挂载时，超级块就被放入内存！
因此寻找空闲的磁盘块就不需要访问外存！
索引节点区
用来存储索引节点
数据块区
用来存储文件或目录数据
各分区数据进入内存的时机
超级块
文件系统被挂载时放入内存
索引节点区
当文件被访问时把对应的索引节点放入内存
磁盘空闲空间管理
空闲分区的管理对应文件系统的超级块
对应文件系统的超级块中，在文件系统挂载时装入了内存
空闲表法
总览
空闲表法属于连续分配方式
它与内存的动态分配方式类似，为每个文件分配一块连续的存 储空间
1、系统为外存上的所有空闲区建立一张空闲盘块表
每个空闲区对应一个空闲表项
其中包括表项序号、该空闲区第一个盘块号、该区的空闲盘块数等信息
2、再将所有空闲区按 其起始盘块号递增的次序排列。
空闲链表法
空闲盘块链
将磁盘上的所有空闲空间，以盘块为单位拉成一条链
当用户因创建文件而请 求分配存储空间时，系统从链首开始，依次摘下 适当的数目的空闲盘块分配给用户
当用户 因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾
空闲盘区链
将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链
在每个 盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明盘区大小（盘块数）的信息
分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。
在回收盘区时，同样 也要将回收区与相邻接的空闲盘区相合并。
位图法
用位图代表空闲数据块列表
使用简单但是可能会是一个大的很大向量表
(二)目录
1.目录的基本概念
目录
定义
是一个特殊的文件，它包含一组目录项
目录项/文件控制块
目录项描述该目录下的文件信息
文件名
inode
目录项所使用的数据结构被称为 文件控制块（FCB） 选择题中可以这么理解 目录项 = FCB
目录系统需要解决的问题
1、为用户显示每个目录里面的文件的 文件名；
2、根据对应的文件名组成的路径找到 对应的文件数据和进行必要的安全检查；
其他相关定义
根目录
本文件系统的最上一层目录，经常常驻内存
当前目录
进程当前正在使用的目录
绝对路径
某文件项相对根目录的路径
相对路径
某文件项相对当前目录的路径
2.几种目录结构
单级目录结构
只有一个根目录文件和目录表，所有文件均占有一个目录项且同级
二级目录结构
为每个用户分配一个目录
树形目录结构
目录结构呈现为树形，无环、跨边和前向边
无环图目录结构
目录结构为无环图形状，可能出现跨边和前向边，对应软链接和硬链接
3.目录的操作
搜索文件
创建文件
删除文件
列目录
重命名文件
遍历路径
4.硬链接与软链接
1、前提 （均作为目录项理解）
无论是软链接还是硬链接，它们均是对某个目录项进行拷贝，自身仍然是目录项
2、硬链接
示意图
思想
不同文件名，对应同一个inode编号，进而对应同一个inode节点
硬链接操作流程
1、创建一个目录项 f2
2、f2直接指向目标文件的inode节点m
3、该inode节点引用数目加一
若删除示意图中原文件的目录项f1
则硬链接 f2仍然指向inode
inode节点引用数目减一
3、软链接 （快捷方式就是一种软链接）
示意图
软链接操作流程
1、创建一个目录项 f3
2、f3 通过新建的inode节点n指向磁盘上的文件，该文件记录的是目标文件的目录项 f1 的绝对路径
3、通过软链接方法，inode节点m并不会引用计数加一
特别的【软链接直接复制目标结点的引用计数】
若删除示意图中原文件的目录项f1
则软链接 f3 不会指向目标文件
5、目录实现
什么叫目录实现？
采取合适的 数据结构来存储每一个目录文件中的目录项
几种实现方式
线性列表
描述
把各个目录项按照线性方式排列
检索方式
暴力搜索
优缺点
实现简单，但是效率比较低
哈希法
描述
根据目录项的文件名作哈希，把目录项存储在对应的位置
检索方式
hash
优缺点
检索速度快，但是容易造成空间浪费
键树（trie）
描述
根据文件名构建 trie 树，然后在 trie 树上检索对应文件名对应的目录项
检索方式
trie 查找
优缺点
搜索速度快，占用空间更小（平均比 O(n)还小），但是算法比较复杂
(三)文件系统
1.文件系统的全局结构(layout)
文件系统层次结构
定义
一种操作系统的组织结构，其提供了一种隔离操作系统各层功能的 模型
总示意图
用户调用接口
表述
文件系统为用户提供与文件及目录相关的调用
如新建、打开、读写、关闭、 删除文件，建立、删除目录等
此层由若干程序模块组成，每一模块对应一条 系统调用，用户发出系统调用时，控制即转入相应的模块
文件目录系统
表述
文件目录系统的主要功能是管理文件目录
其任务有管理活跃文件目录表、管 理读写状态信息表、管理用户进程的打开文件表、管理与组织在存储设备上的 文件目录结构、调用下一级存取控制模块。
存取控制验证
表述
实现文件保护主要由该级软件完成
它把用户的访问要求与 FCB 中指示的访问 控制权限进行比较，以确认访问的合法性
逻辑文件系统与文件信息缓冲区
表述
主要功能是根据文件的逻辑结构将用户要读 写的逻辑记录转换成文件逻辑结构内的相应块号。
物理文件系统
表述
物理文件系统的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址
分配模块
表述
分配模块的主要功能是管理辅存空间，即负责分配辅存空闲空间和回收辅存空 间
设备管理程序模块
表述
设备管理程序模块的主要功能是分配设备、分配读写用缓冲区、磁盘调度、启 动设备、处理设备中断、释放设备读写缓冲区、释放设备等
文件系统在外存中的结构
文件系统在内存中的结构
2.外存空闲空间管理方法
3.虚拟文件系统
示意图
VFS虚拟文件系统可以让不同的文件卷挂载不同的文件系统
4.文件系统挂载(mounting)
I/O管理
(一)1/O 管理基础
I/O系统的组成
I/O软件
内容
包括驱动程序、用户程序、管理程序、升级补丁等
如何控制
通常采用I/O指令和通道指 令实现 CPU与I/O设备的信息交换。
I/O硬件
内容
包括外部设备、设备控制器和接口、I/O总线等
如何控制
设备控制器
控制I/O设 备的具体动作
I/O接口与主机（总线）相连
进程与I/O
进程使用 I/O 的方式
I/O 指令
通过 I/O 端口号访问设备寄存器
特殊的 CPU 指令
out 0x21,AL
内存映射 I/O
设备的寄存器/存储被映射到内存物理地址空间中
通过内存 load/store 指令完成 I/O 操作
MMU 设置映射
硬件跳线或程序在启动时设置地址
进程获取 I/O 设备的方式
注意
不同的 I/O 设备以及 CPU 之间是可以并行工作的
除非它们的工作有特殊的互斥要求 （如读写同一块内存）
同步 I/O
向 I/O 设备读写数据的时候，进程进入阻塞态
阻塞I/O: “Wait”
直到 I/O 操作完成，再唤醒该进 程
异步 I/O
向 I/O 设备读写数据的时候，进程使用指针标记好缓冲区便可以继续执行
异步I/O: “Tell Me Later”
当 I/O 操作完成后再由外设触发外部中断通知进程
除非 I/O 操作不执行进程就无法继续执行
1.设备
设备的基本概念
I/O 设备
计算机中除 CPU、主存储器以及它们之间的总线以外，其它挂载在计算机上的设 备均为 I/O 设备。
设备挂载
将一个设备挂接到一个已经存在的目录上
我们要访 问存储设备中的文件，必须将文件所在的分区挂载到一个已存在的 目录上， 然后通过访问这个目录来访问存储设备。
设备的分类
通常分类
输入设备
键盘
鼠标i
输出设备
显示器
显示存储器VRAM
打印机
外存
磁盘
磁盘阵列
光盘存储器
SSD固态硬盘
按使用特性分类
人机交互类外部设备
用于同计算机用户之间交互的设备
如打印机、显示器、鼠标、键盘 等
特点
数据交换速度相对较慢
通常是以字节为单位进行数据交换
存储设备
用于存储程序和数据的设备
如磁盘、磁带、光盘等
目的
用于数据交换
特点
速度较快
通常以块为单位进行数据交换
一个块由多个字节组成
网络通信设备
用于与远程设备通信的设备
如各种网络接口、调制解调器等
特点
其速度介于 前两类设备之间
网络通信设备在使用和管理上与前两类设备也有很大不同
按传输速率分类
低速设备
传输速率
每秒几个到数百个字节
例子
键盘
鼠标
中速设备
传输速率
每秒数千个字节至数万个字节
例子
打印机
高速设备
传输速率
数百个千字节至千兆字节
例子
磁带
磁盘
光盘
按信息交换的单位分类
块设备
信息的存取总是以数据块为单位
它属 于有结构设备
基本特征
传输速率较高
可寻址
例子
磁盘
字符设备
用于数据输入/输出的设备为字符设备
因为其传输的基本单位是字符
它 属于无结构类型
基本特征
传输速率低
不可寻 址
中断驱动
例子
打印机
交互式终端机
一般意义上的 I/O 过程
前情提要
I/O 设备均包含各自的设备寄存器
计算机可以通过一些特殊的指令和方式实现设备寄存器 和内存或 CPU 单元的数据交换
I/O 操作的目的
一般指外设与内存的数据交换
1、外设与 其设备寄存器的数据交换
2、设备寄存器与内存/CPU 的数据交换
I/O 接口
在各个外设与主机之间传输数据时进行各种协调工作的逻辑部件
协调包括传输过程中速度的匹配、电平和格式转换等。
I/O 端口
定义
I/O端口是指接口电路中可被 CPU直接访问的寄存器
常见端口
数据端口
状态端口
控制端口
若干端口加上相应的控制逻辑电路组成接口
描述
通常，CPU能对数据端口执行读写操作，但对状态端口只能执行读操作，对控制端口只能执行写操作。
要想CPU能访问I/O端口必须对各个端口进行编号
对I/O端口编址方式的分类
1、统一编址（存储器映射方式）
思想
把I/O 端口当作存储器的单元进行地址分配
编内存的地址，访外存的速度
特点
这种方式CPU不需要设置专门的I/O指令，用统一的访存指令就可以访问I/O端口。
优点
不需要专门的输入/输出指令，灵活方便
可使端口有较大的编址空间
缺点
端口占用存储器地址，使内存容量变小
利用存储器编址的I/O设备进行数据输入/输出操作，执行速度较慢。
2、独立编址（I/O映射方式）
思想
将I/O端口的地址空间与主存地址空间视为两个独立的地址空间
需要设置专门的I/O指令来访问I/O端口
专人专事
优点
程序编制清晰，便于理解
缺点
输入/输出指令少，一般只能对端口进行传送操作
尤其需要CPU提供存储器读/写、I/O设备读/写两组控制信号，增加了控制的复杂性。
2. I/O 控制方式
程序直接控制方式
思想
计算机从外部设备读取数据到存储器，每次读一个字的数据
对读入的每个字，CPU需要对外设状态进行循环检查
直到确定该 字已经在I/O控制器的数据寄存器中
特点
CPU与I/O设备串行操作
效率低下
轮询方式
思想
由CPU定时发出询问，依序询问每一个周边设备是否需要其服务
有即给予服务，服务结束后再问下一个周边，接着不断周而复始
优点
实现较易
缺点
效率偏低
中断方式
思想
设备独立完成对自身设备寄存器的读写操作
完成该操作后， 向CPU发出中断信号
由CPU来完成设备寄存器与内存的数据交换
特点
设备寄存器与内存的数据交换借助CPU的 寄存器
依然需要CPU参与具体的传输过程
DMA 方式(直接内存存取)
思想
在 I/O 设备和内存之间开辟直接的数据交换通路，彻底“解放” CPU。
特点
基本单位是数据块
内存和设备直接传输数据
仅在传 送一个或多个数据块的开始和结束时，才需 CPU 干预
整块数据的传送是在 DMA 控制器的 控制下完成的。
DMA 方式的工作过程
1、CPU 读写数据时，它给 I/O 控制器发出一条命令，启动 DMA 控制器， 然后继续其他工作
2、之后 CPU 就把控制操作委托给 DMA 控制器，由该控制器负责处理
3、DMA 控制器直接与存储器交互，传送整个数据块，每次传送一个字，这个过程不需要 CPU 参与
4、当传送完成后，DMA 控制器发送一个中断信号给处理器
通道方式
思想
对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有 关的控制和管理为单位的干预。
同时，又可以实现 CPU、通道和 I/O 设备三者的并行操作
从而更有效地提高整个系统的资源利用率
I/O 通道的本质
一台精简版的处理器
只具有实现外设与内存间数据交换的功能
通道与 DMA 方式区别
从一次传输一个数据块变成了一次传输一组数据块
3.I/O 子系统的层次结构
总览图
软件层次结构
用户层 I/O 软件
实现与用户交互的接口
用户可直接【系统调用】在用户层提供的、与 I/O 操作有 关的库函数，对设备进行操作。
使用【逻辑设备名】作为参数
设备独立软件
用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、以友 设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间
将【逻辑设备名】映射到【物理设备】，实现设备的分配
设备驱动程序
与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动 I/O 设 备工作的【驱动程序】。
中断处理程序
用于保存被中断进程的 CPU 环境，转入相应的中断处理程序进行处理，处 理完并恢复被中断进程的现场后，返回到被中断进程。
硬件层次结构
硬件设备
I/O 设备通常包括一个机械部件和一个电子部件
电子部件称为设备控制器（或适配器）
在个人计算机中，通常是一块 插入主板扩充槽的印刷电路板
机械部件则是设备本身
I/O 调度
定义
不同进程请求同一个 I/O 设备服务的时候，选择合适的进程来分配 I/O 设备资源。
4.输入输出应用程序接口
字符设备接口
块设备接口
网络设备接口
阻塞/非阻塞 I/O
(二)设备独立软件
1.缓冲区管理
磁盘缓存
缓存
数据传输双方访问速度差异较大时，引入的速 度匹配中间层
磁盘缓存是磁盘扇区在内存中的缓存区
磁盘缓存的调度算法很类似虚拟存储调度算法
磁盘的访问频率远低于虚拟存储中的内存访问 频率
通常磁盘缓存调度算法会比虚拟存储复杂
单缓存
双缓存
循环缓冲
描述
包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区， 最后一个缓冲区指针指向第一个缓冲区，多个缓冲区构成一个环形
2.设备分配与回收
3.假脱机技术(SPOOLing)
总览图
作用
将一个独占设备虚拟化为多个设备，让多个进程均可“独占”设备
原理
将输入或输出的请求先存储起来，在特定的时间模拟设备的输入输出
组成
输入井
磁盘上作为输入的缓冲区，模拟设备输入。
输出井
磁盘上作为输出的缓冲区，模拟进程的输入
输入进程
实现输入井中数据输入的进程
输出进程
实现输出井中数据输出的进程
输入缓冲区
输入进程执行时所使用的内存空间
输出缓冲区
输出进程执行时所使用的内存空间
如何理解 spooling 假脱机技术？
4.设备驱动程序接口
(三)外存管理
1.磁盘
磁盘结构
示意图
磁盘I/O传输时间
总览图
寻道时间
定位到期望的磁道所花费的时间，记为 Ts
旋转延迟
从零扇区开始处到达目的地花费的时间 平均旋转延迟时间=磁盘旋转一周时间的一半
1/r =旋转一周的时间 1/2r即平均旋转延迟
传输时间
磁盘数据传输的时间
b = 传输的比特数 N = 磁道上的比特数 r = 磁盘转数
磁盘地址
磁盘调度方法 （显著影响寻道时间Ts）
定义
通过优化磁盘访问请求顺序来提高磁盘访问性能
FIFO
思路
按顺序处理请求
公平对待所有进程
特点
在有很多进程的情况下，接近随机调度的性能
例子
SSTF（最短服务时间优先）
思路
选择从磁臂当前位置需要移动最少的 I/O 请求
总是选择最短寻道时间
例子
SCAN（扫描算法）（电梯算法）
思路
磁臂在一个方向上移动，访问所有未完成的请求， 直到磁臂到达该方向上最后的磁道
调换方向
注意
SCAN算法会访问边界，再返回
如下例中，14是最左侧的磁道，但是在本算法中还需要访问0再折返
例子
LOOK
思路
是SCAN算法的改进
在扫描到最靠近x端的磁道时进行折返，不会像SCAN一样扫描到最边缘磁道
C-SCAN（循环扫描算法）
思路
限制了仅在一个方向上扫描
当最后一个磁道也被访问过了后，磁臂返回到磁 盘的另外一端再次进行
磁头粘着(Arm Stickiness)现象
定义
SSTF、SCAN 及 CSCAN 等算法中，可能出现磁头停留在某处不动的情况
可能原因
进程反复请求对某一个磁道的访问
格式化
低级格式化
把磁盘分为扇区以便磁盘控制器的读写
高级格式化
对磁盘或磁盘中的分区(partition)进行初始化的一种操作
这种操作通常会导 致现有的磁盘或分区中所有的文件被清除。
分区
2.固态硬盘
描述
微小型高档笔记本计算机采用高性能 Flash Memory 作为硬盘来记录数据，这种"硬盘"称固态硬盘。固态硬盘除需要 Flash Memory 外，还需要其他硬件和软件的支持。
读写性能特性
磨损均衡
【重要】文件操作专题 【含例题】 （本专题下 inode 可视为 FCB ）
创建文件
创建文件的定义
创建一个空文件
为其提供文件所需要的基本资源
创建文件的主要步骤
1.为文件创建一个文件目录项
2.为文件创建一个 inode 结构并分配 inode 号
将 inode 编号与文件名映射关系保存在 1 中 分配的文件目录项中
目录项 = 文件名 - inode编号
3.将 1 中创建的文件目录项写入到父目录的数据区
删除文件 【含例题】
重要例题
【13-23】
题干
A，解答
A错误
以删除/var/log/messages 这个文件为例
/var/log/messages所在的目录是/var/log
显然删除这个文件并不会删除 log！
B、C、D均正确 补充小细节
注意C的说法，删除FCB或收回FCB均正确！
【21-25】
题干
A，解答
A错误！
注意：【快捷方式是软链接！】 【符号方式也是软链接】
删除文件后，软链接的内容仅仅不能访问，软链接并没有被删除
B、C、D均正确
【0-1模拟卷-2-29】
题干
C，正确
删除某个目录文件下的文件，会导致该目录文件的目录项变化==其他文件实体修改
例如删除 ：root/a/t.txt 删除 t.txt 后，目录文件 root/a 的目录项就会发生变化！
错误选项辨析
A错误，文件删除时，并不需要对文件所占的数据块进行清空，而只需要在标识磁盘空闲空间 的数据结构（如位图）上进行对应数据块的标记处理即可
B错误，【首先明确，符号链接==软链接！】 当文件A还有未被删除的硬链接时（文件计数不为 1）， 则A不会删除文件实体 【错在符号链接这！】
会不会删除文件实体关键看两个条件：
1、删除的是不是硬链接
2、文件inode结点的引用计数是否为 1
删除软链接一定不会删除文件实体
D错误（不严谨），已经被某进程打开的文件如果没有完 全关闭则无法被删除【记忆！】
因此打开文件表中不会包含被删除的文件，删除文件不会引发系统级 打开文件表的变化
windows下的例子
删除文件定义
回收文件占用的资源
inode
目录项
磁盘簇
数据存储在硬盘的时候都是以簇为单位
删除文件的主要步骤 【例子】
描述
以/var/log/messages 这个文件为例，删除 messages 这个文件的过程大致如下
流程
1、找到/var/log/messages 所在的 inode
通过文件名找到 inode 节点编号 通过 inode 节点编号找到 inode 节点
2、删除/var/log 目录上有关 messages 的条目
3、清空索引中/var/log/messages 对应的 inode 数据，将此 inode 对应的【位图（bitmap）】改为空闲
文件的删除并不是真的把对应位置全部清0，仅仅是更改位图（bitmap）上的标志位
1 表示该块被占用不可用 0 则可用
【删除文件】 的速度大于 【写文件】 的速度就是因为： 删除文件时只需要将位图的 1 置 0，一大块存储区域就可使用 而写文件时需要每一位都去写入
inode 也有类似 位图的数据结构
4、将/var/log/messages 所占用的磁盘块重新标记为空闲
删除文件的注意事项
1、只有文件实体的 inode 的引用计数为 1（不存在其它还未被删除的硬链接）时，才会执 行以上全部操作，【否则只删除对应的目录项】
一般不删除文件，只删除目录项 仅有 1 个目录项 指向 文件实体时才会删除文件
1、有多个目录项指向文件时，删除文件类似割韭菜 2、仅有一个目录项指向文件，删除文件就是刨韭菜根了
2、注意是清空文件对应的 inode 而不是删除，实际上只需要将 inode 置为空闲并不需要清 空 inode 也可以达到同样的效果；
inode 也有类似 位图 的数据结构
3、只需要将磁盘块标记为空闲即可，并不需要真实的删除磁盘簇中的数据。因此，删除文 件的操作往往比复制文件（写文件）要快很多
4、已经被某进程打开的文件如果没有完 全关闭则无法被删除
文件打开 （含例题）
例题
【0-1模拟卷-2-31】进程打开文件的操作
题干
知识点回顾
进程打开文件必然在系统级打开文件表中建立新的表项（之前该文件未被打开）或者 使对应表项引用计数加一（之前该文件已被打开）
之前被打开过
引用计数加一
之前没被打开过
创建表项
文件控制块被写入内存发生在文件第一 次被打开的时候，当再次打开同一文件时，操作系统只需要给进程一个到该 FCB 存放区的指 针即可。【B错】
不同进程对同一个文件具有的权限是不同的，因此不是所有的进程都可以读写任意 文件
【14-29】文件打开
题干
B正确，FCB等价于inode
A错误，仅仅将inode读入内存
C、D错误，首次打开不会涉及文件读写操作
知识点-文件打开
【进程级打开文件表】、 【系统级打开文件表】， 【inode表】 （示意图）
【文件打开的基本流程】
1、根据【文件路径/文件名】检索到文件的【inode节点】，将inode 放入内存中的inode表中
2、在【系统级打开文件表（直接）】和 【进程级打开文件表（间接）】中建立一个表项指向inode节点
3、【进程级打开文件表】中对应的 fd 返还给PCB作为文件描述符
文件打开的两种情况
1、文件已经被打开
1、根据【文件路径/文件名】，去【系统级打开文件表】中查找 inode指针 （成功找到）
例如 【系统级打开文件表】中第 0 项找到目标 inode结点，对应【inode表】中的 1976项
2、文件已经被打开，则给【进程级打开文件表】分配一个表项，用该表项指向【系统级打开文件表】中对应的一项； 被指向的【系统级打开文件表】的表项【被引用记数 + 1】
给【进程A的进程级打开文件表】分配一个表项，让它指向系统级打开文件表中的 0 项；【系统级打开文件表】对应的表项引用计数 + 1
3、PCB为文件分配一个表项，结构为：【文件描述符fd - 文件指针】
PCB为该文件分配文件描述符 fd0
【特别注意的是】
文件指针是用来标识，表示当前【读/写文件】进行到了buffer中的哪里
因此数据缓冲区的首指针是在读文件时才返回给用户进程的
2、文件尚未被打开
1、根据【文件路径/文件名】，去【系统级打开文件表】中查找 （查找失败）
找到文件a在磁盘中对应的位置
将文件a对应的 inode 结点放到内存中的【inode表中】
2、在【系统级文件打开表】中新增一个表项，该表项指向【inode表】中对应的结点
3、在【进程级文件打开表】中新增一个表项，指向【系统级文件打开表】对应的表项
4、PCB为文件分配一个文件描述符fd，作为进程级文件打开表项的指针
文件关闭
知识点-文件关闭 （文件打开的逆过程）
1、根据要关闭的【文件路径/文件名】找到对应的文件描述符 fd
2、删除fd对应【进程级打开文件表】的表项， 并根据该表项去【系统级打开文件表中】查找引用计数， 如果【系统级打开文件表】对应的表项的引用计数为 1 ，则删除该表项； 并删除该表项在【inode表】中对应的表项
文件的读写
1、要进行文件读写，首先要打开文件！
读写文件根据【文件描述符】去【进程级打开文件表】中找到对应的文件指针，从而定位到文件对应的磁盘空间
2、读写文件是先在内存中读写，然后再通过内外存交换对磁盘内容进行更替
3、读写文件的基本单位时文件簇
即使读写 1 bit 都需要进行一个磁盘簇的数据交换
文件系统在外存上的结构
1、超级块（super block）
考点：空闲磁盘使用情况
例如：位图（bitmap）
用 1 bit 标记磁盘是否被访问
知识点
文件系统中第一个块被称为超级块
Unix中管理空闲磁盘快的方法——成组链接法（超级块）
这个块存放【文件系统本身的结构信息】
超级块记录了每个区域的大小
超级块也存放未被使用的磁盘块的信息
2、i-节点表
i-节点表实际上是一个映射关系
超级块的下一个部分就是 i-节点表
每个文件都有一些属性，如文件的大小、 文件所有者、和创建时间等，这些性质被记录在一个称为 i-节点的结构中
所有 i-节点都有 相同的大小，并且 i-节点表是这些结构的一个列表，文件系统中每个文件在该表中都有一个 i-节点。
3、数据区
文件系统的第 3 个部分是数据区； 【文件的内容保存在这个区域】
磁盘上所有块的 大小都一样。如果文件包含了超过一个块的内容，则文件内容会存放在多个磁盘块中
一个 较大的文件很容易分布上千个独立的磁盘块中.