OS
OS
Catcat Head笔记参考:
1:https://juejin.cn/column/7040763019336351757
2:b站王道计算机考研 操作系统
3:校内PPT
4苏州大学慕课 操作系统
以下是课件8-13
内存 文件 IO 部分的知识点整理
内存
认识两个寄存器
代码分模块编译之后 要链接起来构成一个完成的逻辑地址之后再装入
在装入的这一步 要了解动态装入:
装入模块在装入的时候并不进行地址转换
等要执行的时候才会去和基址寄存器进行转换
- 更好的内存空间利用率
- 没有被使用的例程不被载入
- 当需大量代码来处理不经常使用的功能时非常有用
在链接这一步 要了解动态链接 执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。
内存管理
内存管理要解决的事情:
- 内存空间的分配与回收
- 内存空间的扩展
- 逻辑地址与物理地址的转换
内存空间的扩展
1.覆盖技术
2.交换技术
中级调度(内存调度)
3.紧缩
把一些小的空闲内存结合成一个大的块。
只有重定位是动态的时候，才有可能进行紧缩，紧缩在执行时期进行
进程的哪些内存要交换到磁盘？
运行时创建或修改的内容：栈和堆
在磁盘的什么位置保存被换出的进程？
交换区（备份区）：系统指定一块特殊的磁盘区域作为交换空间（swap space），包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问
交换时机？
只要不用就换出（很少再用）
内存空间不够或有不够的危险时换出
如何选择被换出的进程？
可优先换出阻塞进程；可换出优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…。(注意，PCB会常驻内存，不会被换出外存)
内存空间的分配与回收 连续分配
单一连续分配: 把内存分为系统区和用户区
内存只能放一个进程:无外部碎片
固定分区分配
使用 固定分区使用表记录分区的使用情况
- 优点：实现简单，无外部碎片。
- 缺点:
- 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能;
- 会产生内部碎片，内存利用率低。
动态分区分配
动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要，所以内存中分区的大小是不等的。因此系统内存分区的大小和数目是可变的。
这种动态分区方式下系统要用什么样的数据结构记录内存的使用情况?
空闲分区表or空闲分区链(双端链表)
当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?
动态分区分配算法:
如何进行分区的分配与回收操作?假设系统采用的数据结构是“空闲分区表”如何分配和回收?
分配懒得写了
回收的时候:
- 前面有空闲分区
- 后面有空闲分区
- 前后有空闲分区
- 前后都没空闲分区
首次适应算法(First Fit)
每次都从低地址开始查找，找到第一个能满足大小的空闲分区
最佳适应算法(Best Fit)
即优先使用更小的空闲区。
最坏适应算法(Worst Fit)
每次分配时优先使用最大的连续空闲区
邻近适应算法(Next Fit)
空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)
邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用(最大适应算法的缺点)
综合下来还是一开始的首次适应算法最优
内存空间的分配与回收 非连续分配
分页存储管理
基本概念还是要清楚的
页框:物理内存分成大小相等的块 也叫页帧 (内存块)
页面:逻辑内存分为大小相等的块
页表:一个进程有一个页表 存储在PCB中 运行时放入内存 体现页号和内存块的对应关系
叽里咕噜听不懂,直接看最后的整个机制吧:
引入 快表(联想寄存器TLB) :**时间局部性 ** 空间局部性
引入 两级页表 原因:
1.页面很大的时候 会占用多个连续内存块 不符合离散思想
2.页表不需要常驻内存 因为时空局部性
(这张图还没引入二级页表)
- CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
计算页号P和页内偏移量W (如果用十进制数手算，则P=A/L，W=A%L;但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量)
比如32位逻辑地址空间 页表项4B 页面大小4KB
由页面大小就可以知道 页内偏移最大为2的十二次方 所以需要12个二进制表示
则 页号 32-12=20个位表示 那么最大页表项就为2的20次方
显然 页面大小4KB存储4B的页表项只能存2的10次方个
因此将页表分块 每1024个页表项做一个二级页表
引入页目录表管理 该目录需要1024个 指向1024个二级页表存放的内存块号
这样划分之后 再回到我们32位的逻辑机制 可以发现 页内偏移所需位数没有变 还是12个 但是我们把原来表示页表项的前20为划分成了两部分 前十位1024个表示 一级页号
后十位 1024个表示二级页号
最后找到二级页号之后拿着去快表中找
如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此,若快表命中，则访问某个逻辑地址仅需一次访存即可。
对快表的访存速度远大于对主表的访存速度
如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。
因此，若快表未命中，则访问某个逻辑地址需要两次访存(注意:在找到页表项后，应同时将其存入快表,以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)。由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。
注意 上面说的两次访存是没有二级页表的情况
如果有N级页表 那么在快表位命中的情况下 访存次数是N+1
为什么是N+1?取N次页表 和1次数据
- 因为局部性原理，一般来说快表的命中率可以达到90%以上。
联想寄存器的查找需要时间单位a微秒
假设内存一次存取需要b微秒
命中率 = l
页表级别=N
EAT = l (a + b) + (1 – l) (a+(N+1)*b)
分段存储管理
搞懂分页存储 分段存储也没啥问题 把所有”段”换成”页”就行 然后要了解一些他们的区别
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。 不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的。可修改的代码是不能共享的(比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致)
段页式存储管理
(段号 页号 页内偏移)
虚拟存储技术 (属于内存空间扩充的措施之一)
传统存储管理方式的缺点:很多暂时用不到的数据也会长期占用内存，导致内存利用率不高
特征：
- 一次性： 作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:
- 作业很大时，不能全部装入内存，导致大作业无法运行;
- 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
- 驻留性： 一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。
虚拟存储技术的提出是基于局部性原理提出来的
高速虚拟存储技术的提出是基于局部性原理提出来的缓冲技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中
虚拟内存—区分开物理内存和用户逻辑内存
- 只有部分运行的程序需要在内存中
- 逻辑地址空间能够比物理地址空间大
- 允许多个进程共享同一地址空间
- 允许更有效的进程创建
虚拟内存的实际容量= min (内存和外存容量之和，CPU寻址范围)
请求分页管理方式 1页表机制 2缺页中断 3地址变换
页表机制
允许一个程序只装入部分页面即可投人运行，需要信息时动态调入，这种装入信息的策略称为请调策略
1发现所访问页面不在主存:
操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置。
2如果不在主存 如何处理
缺页中断(内中断)
每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
进程阻塞 有空闲块分配空闲块 没空闲块就替换 替换出去的页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
这张图重点说是
缺页率（缺页的概率）：0 <= p <= 1.0
如果 p = 0 ，没有缺页
如果 p = 1， 每次访问都缺页
有效访问时间（ EAT ）
EAT = (1 – p) x 内存访问时间+ p x 页错误时间
页错误时间=处理缺页中断
+[页交换出去时间 ]
+读入页时间
+重启进程开销
页面置换算法
最佳置换算法(OPT，Optimal)： 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
先进先出置换算法(FIFO)：每次选择淘汰的页面是最早进入内存的页面
实现方法： 把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
Belady异常： 当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差
最近最久未使用置换算法(LRU， least recently used)： 每次淘汰的页面是最近最久未使用的页面
实现方法： 赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面【该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大】。
LRU近似算法
(访问位，修改位)
修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。
二次机会算法:
就是简单时钟算法 只有一个访问位
绕一圈 找 0 如果是1则置为零 如果是0 就返回
绕第二圈 返回 0
一共转两圈
算法规则: 将所有可能被置换的页面排成一个循环队列
- 第一轮：从当前位置开始扫描到第一个(0,0) 的帧用于替换。本轮扫描不修改任何标志位
- 第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0, 1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
- 第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0, 0)的帧用于替换。本轮扫描不修改任何标志位
- 第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0, 1)的帧用于替换。
- 由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描
先找(0,0)
如果没有 找(0,1) 且访问位置设置为0
再找(0,0)
如果没有 则找(0,1)
一共四轮
驻留集:请求分页存储管理中给进程分配的物理块的集合。
不能太大也不能太小
固定分配:分配了就不变
可变分配 :分配了可变
局部置换: 发生缺页时只能选进程自己的物理块进行置换。
全局置换:将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
预调页策略： 根据局部性原理(主要指空间局部性，即:如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的那些内存单元)，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入(运行前调入)，由程序员指出应该先调入哪些部分。
请求调页策略： 进程在运行期间发现缺页时才将所缺页面调入内存(运行后调入)。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大。
抖动颠簸现象
刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)
为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率
局部模型(Locality model)
进程从一个局部移到另一个局部
局部可能重叠
为什么颠簸会发生
分配的页框数 < 局部大小之和
工作集： 指在某段时间间隔里，进程实际访问页面的集合。操作系统会根据“窗口尺寸”来算出工作集。
文件
逻辑结构VS物理结构
逻辑结构就是给人看的
物理结构是给机器看的
空间换时间:
索引文件 在数据库实践中常见的措施 数据库表过大的时候 按主键遍历查询会特别慢 为常查询的字段建立索引 能够大大提高相应速度(logn VS n)
建立索引固然消耗存储空间 但是查找速度大大提升
文件目录
知道了文件内部可以怎么存 现在要讨论如何在计算机中找到一个文件 那就需要文件目录的帮助
首先文件控制快FCB 存储文件的存放信息
几个目录结构要清楚
单级 两级(主文件目录 用户目录 打开linux操作系统就可以清楚了解 home/下存放着不同用户各自的目录) 多级都是一个道理 一层不够再加一层
然后要知道往下查一层 就要对应一层IO操作
无环图目录结构 硬链接
(结合linux中iNode和block的知识
简单来说 硬链接是创建一条箭头 指向block
软连接是创建一个新的inode 指向block 然后在block中存放源文件的路径(当成快捷方式理解))
在无环图目录结构中:
其实也就是允许硬链接的存在,可以让不同用户指向同一个文件(感觉就是浅拷贝)
一个目录项的大小乘以FCB能存放的最多文件数目 其实就是一个FCB的大小
那如果一个FCB需要放到越多的物理块 是不是遍历一遍就要IO的次数越多
所以尽可能的降低一个FCB的大小就可以减少IO
怎么降低呢,FCB就存两个信息 一个是文件名(因为要按名索引) 一个是指向其他信息的指针信息(要找到剩余信息)
PPT里讲的平均查找次数的计算 有可能访问第一个物理块就找到要找的文件 也可能5000次才找到 所以平均值的计算:(min+max)/2
文件权限控制
owner group public
一共9位二进制 三位表示一个用户的权限 RWX分别表示读 写 操作
111 就是最高的权限 ==7
所以chmod 777 就是赋予最高权限
761 ==111 110 001
物理结构
物理结构一定要和逻辑结构分清楚 还是那句话 逻辑结构是用户自己敲的 物理结构是机器自己完成的 用户平时看不到
对用户来说 看到的是逻辑块号和块内地址
操作系统负责把其转化为实际存放的(物理块号,物理地址)
重点就在于这个转换的过程
顺序分配: 创建数组的时候 其实就是申请了一个连续的空间
转化过程: 起始块号+逻辑块号
且因为物理空间上是相连的 所以磁头读取的时候比较快
链接分配 显示链接 引入一个FAT(文件分配表 常驻内存) 存放(物理块号,下一块)的信息 好处在
1 可以直接查逻辑块号对应的物理块号
2 因为在内存 不需要IO操作 空间换时间的例子之一
索引分配
在FCB存放 (文件名,索引块)
作为索引块的那个物理快存放该文件的各个(逻辑块号,物理块号)的对应关系
和之前的显示链接不同的是: 每个文件存一张表 显示链接是所有文件一张表
但是如果索引块不能在一个物理块中存储怎么办:
1:链接
2多层索引
文件最大长度的计算方法
两层索引为例子:
每一层的索引表大小不能超过一个物理块
物理块大小/索引表项大小 得到项数n
n*n *物理块大小 就可以得到文件的最大长度
计算逻辑快和物理块号的对应也很简单 一层层除下去就行
I/O次数也要会看
k层索引结构 且顶级索引表维没有调入内存 需要k+1次IO操作
3混合索引
为啥需要混合索引呢
因为操作系统内部有很多小文件 可以存放在一个物理块内
如果还建立多层索引 增大IO次数 就不合适了
混合索引可以既满足大文件的查找需求 也能兼顾小文件的快速IO
空闲空间管理
文件卷就是分盘 C D E盘
卷内又划分为目录区和文件区
空闲表和空闲链表没啥特别的
位示图:
(字号,位号)转变为盘快号: b=n*i+j
成组链接法:在逻辑卷的目录区存放一个超级块 在系统启动的时候放入内存
每一组的第一个要存放 1:下一组的盘块数量 2:存放的盘块号
释放出来的空闲块 如果有位置就占空位置 如果无空位置 就在最前面开一个新的组
IO内核子系统
假脱机SPOOLing
cache:
文件系统的层次架构
从上到下 依次是:
逻辑文件系统:
管理文件系统中的元数据
除了文件数据外的所有结构数据
文件按名存取
文件目录组织管理
把文件名转换为文件ID，文件句柄
管理FCB
存储保护
文件组织模块:
管理文件、逻辑块和物理块
把文件的逻辑地址转换为物理地址
管理空闲空间
为文件分配物理块
基本文件系统:
物理块读写和向驱动程序发送控制命令
各种文件系统了解一下:
有点不太想看具体内容了
一台主机可能接入多台设备 如果不同设备使用不同的文件系统 那如何统一呢,就通过虚拟文件系统实现(VFS):
向上提供系统调用接口(API)
向下提供各个文件系统的接入接口
磁盘结构和管理
RAID 是为了提高磁盘的可靠性和性能
可靠性:通过冗余数据
性能:数据分散,来实现并行读写(位级分散(字节),块级分散(块)))
RAID0：性能
RAID1：可靠性
二者兼备:
RAID01
先做分散，再镜像
性能好
RAID10
先做镜像再做分散
可靠性好
寻道时间Ts=s(启动磁头臂)+m*n(磁头跨越一个磁道的时间 乘以 n条磁道)
延迟时间 旋转磁盘产生 TR=(1/2)*(1/r) r:磁盘转速
传输时间Tt=(1/r)*(b/N) b是读或写的字节数 N是每个磁道的字节数
磁盘调度算法
延迟时间 传输时间取决于硬件
操作系统能够优化的是寻道时间
优化的措施就是不同的调度算法:
FCFS: 先来先服务
SSTF: 最短寻找时间有先 找磁头最近的 可能会在小区域内循环
SCAN: 为了防止小区域循环 到了最外侧才可以往内走 缺点有二 1:有不必要的移动 2:每个磁道的相应并不平均
LOOK: 针对SCAN的第一个缺点 边走边看 往外走无磁道访问就马上掉头
C-SCAN: 针对SCAN的第二个缺点 往某个方向一直走到底部之后 直接从另一端开始
C-LOOK: 结合LOOK 改进C-SCAN 如果前进端没有请求了 即可从头开始
I/O系统
基础的概念了解一下就行
重点在后面
对I/O设备的控制方式
首先要了解I/O控制器是干嘛的
CPU数据流向可能两种:
轮询 Polling
CPU一直不停的问状态寄存器 你忙不忙
要是不忙就处理进程
缺点显而易见 CPU长期忙等 干活了但是效率很低
那为了不忙等(摸鱼) 就有新的方式
中断机制
也就是检测到IRL 就中断当前的事情 来干活(执行完每条指令后检测)
但是上面的措施都存在一个问题 那就是读取或者输出是一个字一个字输出,且我们都知道频繁的中断会消耗较多的时间
那还有办法:
让内存直接和DMA打交道 CPU给出命令就行
