操作系统
第一章 计算机系统概述
系统调用与库函数
第二章 进程管理
进程组织
- 用PCB来记录进程的相关数据，状态等
进程状态
进程控制
- 实现进程状态转换的方式
1.如果处于运行态，在运行的过程中发出了对某个进程的请求，就会进入阻塞态，去完成那个需要的进程，再回来完成这个
2.例：如果有突发特权请求，把PCB换标志位这一步没做好，问题就大了，所以用到原语，实行“开/关中断指令”，让这个过程一气呵成
进程通信
- 手机图册里的照片通过分享 - > 微信分享给朋友
共享存储
管道通信
线程与多线程
线程概念
- 线程：轻量级的进程，CPU基本的执行单元
用户级线程、内核级线程
- 通过线程库，把 用户级线程（用户能看到的） 映射到内核中的 内核级线程 （内核看到的）
轻量级线程（LWP）
调度器激活
多线程模型
多对一模型
- 一个线程堵塞后，整个进程都会阻塞，而且浪费多核处理器（只用到一核）
一对一模型
- 线程切换由系统内核完成，开销大
多对多模型
- 合理
进程调度
注意调度的是进程，为了更有效的实现多线程工作
1.进程调度方式
- 抢占式
- 非抢占式
2.调度的基本准则
3.调度算法
--- 早期批处理(交互性差) ---
1.先来先服务调度算法
2.短作业优先调度算法
-
默认为非抢占式
- 抢占式
- 注意
最短剩余时间优先 可证明为最短
3.高响应优先算法
-
避免了FCFS对短作业不友好 ， 又避免了SJF 导致长作业饥饿的现象，等待时间过长
-
用响应比 = （等待时间 + 要求服务时间 ）/ 要求服务时间
--- 交互性好 ---
（关心响应时间，而不是那些平均周转时间啥的）
4.时间片轮转调度算法
5.优先级调度算法
- 非抢占式
- 抢占式
-
静态优先级
-
动态优先级
-
补充
-
-
优缺点
-
******** 终极算法 ********
6.多级反馈队列调度算法
进程同步
- 因为现代的系统是并发的去执行进程，而有些情况下异步性会导致很大的问题（比如管道的写数据必须在读数据之前，而异步性可能使之没法实现），如何解决这个问题，引入进程同步的
进程互斥是特殊的进程同步
进程互斥和同步可以简称为同步
进程的同步和互斥是并发进程的两种重要的关系，进程互斥反映了进程间的竞争的关系，进程同步反映了进程间协作的关系，从以上对进程互斥和同步的分析中，进程互斥其实就是一种特殊的进程的同步，例如，进程的互斥是进程之间对临界区的一种排他访问，当有一个进程在临界区是，其他的进程不允许进入临界区。当在临界区中的进程完成任务离开临界区时，改进程归还了临界资源后，该进程通过V操作唤醒了其他等待进入临界区的进程，被唤醒的进程可以进入临界区，因此，互斥的进程也是存在一个进程依赖另一个进程发出的消息而形成一种制约与协作的关系，因此，互斥是一种特殊的同步，进程互斥和同步可以简称为同步。
进程的互斥和同步也有一些内在的不同。当一个临界区是空闲的，进程的互斥条件下，进程就可以进入临界区去去使用临界区的资源，在进程同步的情况下，当没有进程的在使用资源的时候，进程不一定能够使用共享资源的。例如生产者和消费者的问题，如果在消费者不在消费，那么缓冲容器是不被使用的，但是由于缓冲容器满的情况下，生产者不能使用共享的资源缓冲容器的。
(1).进程互斥
首先来看一下什么是进程互斥：
- 再首先看一下临界资源：一个时间段内只允许一个进程使用的资源是临界资源。（例如摄像头、打印机、内存缓冲区等）
- 对临界资源的访问，必须互斥的进行
- 怎么互斥的访问资源
如下: 进入区 -> 临界区 -> 退出区 -> 剩余区
** 注意 **
4.让权等待 就是说如果有一个进程因不能进入临界区而卡住，整个进程不能继续进行下去，直接干脆先把这个进程放弃使用处理机，别光占着耽误事，多线程嘛，先让别人先干活
(2).实现临界区互斥的方法
1.软件实现
算法1: 单标志法
- 每个进程进入临界区的权限只能被另一个进程赋予，轮着来
int turn = 0; //表示当前允许进入临界区的进程号，刚开始只允许 P0 进入临界区
如果 P1 先上处理机运行，则会一直卡在 while(turn !=1 ) ,直到 P1 的时间片用完，切换P0 上处理机运行，接着就会按照①②③④运行，运行完成后把临界区让给 P1 使用
- 问题：如果刚开始P0不运行的话（就不会运行后面的 turn = 1），临界区在这段时间就空闲 ，违背了 空闲让进的 原则
算法2：双标志先检查
bool flag[2];
flag[0] = false;
flag[1] = false; //刚开始设置两个进程都不想进入临界区
- 问题：会出现两个都为 true 的情况，P0、P1两个进程 则会并发执行 ，就可能同时访问临界区，所以违反了 忙则等待 的原则
算法3：双标志后检查
- 因为上面的双标志检查法会出现：当检查完一个进程的时候，还没来的急上锁，另一个进程也检查成功，要进行，导致同时访问临界区 。为了避免这种情况 ， 我们先上锁再检查
算法4： Peterson算法
解决了 空闲让进，忙则等待，有限等待的问题
但是没有遵循让权等待 -> 另一个等待的进程还会分到时间片，在while中浪费cpu时光
2.硬件实现
1.中断屏蔽方法
- 权限比较高，只适用于内核进程，不适合用户进程
2.硬件指令方法
TestAndSet指令（TS / TSL）
- 和peterson算法有相似的地方，使用了不同的实现方式罢了，都会出现不满足 让权等待 的弊端
Swap 指令(Exchange / XCHG)
- 思路相同，实现方式的差异，还是不满足 忙则等待
(3).信号量
- 目的是在上面的软硬件方法的基础上实现 让权等待 的机制
整型信号量
-
问题：会发生忙等
-
使用原语 wait(S) 不可中断，所以检查和上锁一气呵成 ，但是 中间卡while 的时候要是不中断这个wait 函数的话，岂不是一直卡在这里了 ？？？
记录型信号量
- 终于解决了忙等 的问题了 ： 用 阻塞 和 唤醒
注意：初始时 semaphore S = 1 ，当第一个进程使用wait 时，S 就置为0了，再来一个的时候就会变为 -1 就阻塞
value 是提前 -- 和提前 ++ ，
- wait时：第一个进程使 S = 0 ，第二个进程使S = -1，
- wakeup时：待运行的第二进程 S = -1 先++ ，使得 S = 0 ，所以wakeup 的条件是 S <= 0
1.信号量机制实现进程互斥（完美的）
注意：初始时（我把mutex简写为S ，也是为了和进程互斥的S比照） semaphore S = 1 ，当第一个进程使用wait 时，S 就置为0了，再来一个的时候就会变为 -1 就阻塞
value 是提前 -- 和提前 ++ ，
- wait时：第一个进程使 S = 0 ，第二个进程使S = -1，
- wakeup时：待运行的第二进程 S = -1 先++ ，使得 S = 0 ，所以wakeup 的条件是 S <= 0
2.信号量机制实现进程同步
注意：初始时 S = 0 哦，和进程互斥的S = 1不一样
3.信号量机制实现前驱关系
- 就是上面同步方式的 关系叠加
4.总结
(4).经典同步问题
1.生产者-消费者问题
- 必须时互斥的访问缓冲区，防止并发时出现同时 写入一个缓冲区段的情况 ，导致一个被覆盖
-
颠倒 P 的执行顺序会导致死锁
-
颠倒 V 的执行无所谓
-
尽量别把 使用产品 放到P 、V操作之间，会增大时间，耽误别的进程访问临界区和进程的继续执行
2.读者-写者问题
3.哲学家进餐问题
(5).管程
死锁
进程 A 占用打印机 ，进程 B 占用输入设备
现在 A 要是使用输入设备 ，进程 B 要使用打印机
A 对B说 ：只有你停止使用输入设备我才停止使用打印机
B 对A说 ：只用你停止使用打印机我才停止使用输入设备
hhhhhh
.............
不断的争吵，两个进程永远得不到处理，就在那互相耗着
死锁概念
(1).死锁定义
产生死锁的条件：
当一组进程内的每个进程都在等待一个事件，而这一事件只能由这一组进程的另一个进程引起，那么这组进程就处于死锁状态。这里所关心的主要事件是资源的获取和释放。资源可能是物理资源（例如，打印机、磁带驱动器、内存空间和 CPU 周期）或逻辑资源（例如，信号量、互斥锁和文件）。
(2).死锁产生的原因
死锁的处理策略
(1).死锁预防
破坏互斥条件
破坏不剥夺条件
破坏请求和保持条件
虽然让更多的进程可以得到运行，但是会导致有些进程出现饥饿现象
破坏循环等待条件
(2).避免死锁
(3).死锁的检测与解除
第三章 内存
内存管理概述
内存保护
内存扩充技术
覆盖技术
交换技术
虚拟存储技术
内存的分配与回收
1.连续分配管理方式
(1) 单一连续分配方式
- 无外部碎片 （所有的内存都用于一个进程）、有内部碎片 （内存剩余）
(2) 固定分区分配
- 无外部碎片 、有内部碎片 （内存剩余）
(3) 动态分区分配
采用动态重定位的装入方式：
-
目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确执行，这对于存储器紧缩、解决碎片问题是极其有利的；而静态重定位方式在程序执行前就完成 ， 后续不能修改 不利于解决压缩碎片 ，即不利于“ 紧凑 ”
-
一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不是顺序相邻的，只要各个模块有自己对应的定位寄存器就行。
-
每次进cpu之前，都要将 起始地址 放入 基址寄存器（重定位寄存器）
动态分区分配算法
-
首次适应算法
- 算法思想：每次从低地址开始查找，找到第一个满足大小的空闲分区
- 用到两种记录空闲区的数据结构：空闲分区表、空闲分区链 （都是地址从小到大的，不用像最佳适应算法啥的还按照内存块的大小分）
- 导致低地址会出现很多很小的空闲分区，而每次又必须经过这些分区 ， 增大了查找开销
-
最佳适应算法
- 会产生很多外部碎片
-
最坏适应算法（最大适应算法）
- 为了解决最佳适应算法产生很多外部碎片的缺点，最坏适应算法
- 算法思想： 与最佳适应算法相反 ， 每次分配时优先使用最大连续空闲区
-
邻近适应算法
-
算法思想：
-
VS 首次适应算法 ：
-
首次适应算法每次都从最小的低地址开始找 ， 所以遇到需要大内存空间的时候 ， 需要多往后找几次 ， 增加了查找的开销 ，但是 邻近适应算法每次都从上次结束的位置开始检索 ， 解决了上述问题 。
-
但是每次从上次结束的位置开始检索 ， 会导致高地址部分的大分区更可能被使用，被划分为小分区，最后导致无大分区可用
-
-
2.非连续分配管理方式
连续分配方式的缺点多多
- 固定分区分配：缺乏灵活性，会产生大量内部碎片，内存利用率很低
- 动态分区分配：会产生大量的外部碎片，虽然可以用 ”紧凑“ 技术，但是 “紧凑” 技术的时间代价
（1）基本分页存储管理
把进程的页面 放入 内存空间事先分好的 页框 中
如何实现地址由逻辑地址到物理地址的转换？
对于连续分配的情况:
- 是利用重定位寄存器的方式
对于非连续的方式 - > 当采用分页技术之后 ：
页框/页帧
- 内存中的块称为页框
页/页面
- 用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或者”页面“
页号
- 每个页面有一个编号 ，成为页号
页内偏移量
页表
-
为每个进程建立一张页表
-
页表 间接对应着每一页在内存块中的物理地址 ： 页号 -> 块号 -> M块号* 块的内存大小 = M号内存的起始地址
-
每个页表项的长度是相同的，页号是“ 隐含 ” 的：
是这样的：由于页表的页号是顺序的 0，1，2，3，4...... 排列的，所以最后可以删掉 ，只保留块号（页表项），这样一来节省了空间，还能知道块号的响应页号，把页表项长度除
页表长度
- 页表中有几个页表项 ， 即总共有几个页
页表项
-
通常是连续的方式装入内存 ， 而且为了能够方便的找到他的地址 ，有时还会增加页表项的长度（实际中会这样干），这些都是为了好查找对应页号的页表项的块值
一、基本地址变换机构
- 因为只需要告诉 cpu 一个信息（ “ 逻辑地址 ” ），所以是一维的
二、具有快表的地址变换机构
- 是基本地址变换机构的改进版
局部性原理
- 时间局部性：已经执行的指令可能不久之后再次执行
- 空间局部性：被访问过的某个数据，其附近的存储也很有可能被访问
快表（TLB）/ 联想寄存器
- 是一种访问速度比内存快很多的高速缓冲器，用来存放当前访问的若干页表项，以加速地址变换的过程，与此对应，内存中的页表常称为慢表
引入快表之后的地址变换过程 
与基本地址变换机构的比较
三、两级页表
单级页表的缺点明显：
-
问题一：页表必须连续存放，当页表很大时，需要占用很多个连续的页框
-
解决方法：外层页表 / 顶层页表 / 页目录表
两级页表其实就是用两个页表 增加存储的 灵活性
-
-
问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面
细节
- 若采用多级页表机制 ， 各级页表的大小不能超过一个页面（如果超过一个页面，另一部分就会分散存储，导致难以查询）
2.两级页表的访存次数的分析（假设没有快表机构）
两级页表对应的空间优化是以增加访存次数为代价的
所以三级（需4次访问）、四级（需5次访问） 级数越高，访存的次数越多
- 在没有快表机制的时候，n 级页表 ，访存次数是 n+1 次
（2）基本分段存储管理
- 与 ” 分页 “ 最大的区别就是 -- 离散分配时所分配地址空间的基本单位不同
1.分段
- 分段系统的逻辑地址由： 段号（段名） + 段内地址（段内偏移量）
2.段表
-
类似于页表 ， 由 段号 + 段长 + 段基址 组成
-
段号 ： 可以隐含 ，因为段表项的长度都是一样的 ， 用长度一除就可以得到
-
段长 ：不固定
-
段基址 ： 段表中存放段基址的部分要可以包含整个内存大小
3.地址变换
- 需要将页内偏移量与段长进行检查
与分页的对比
分页：主要目的是为了实现离散分配，提高内存的利用率
分段：目的是更好的满足用户的需求
-
因为每段的长度是不固定的，无法通过整数除法得出段号，无法通过求余得出段内偏移 ，所以段号和段内偏移一定要显示的给出
（ 段号 ， 段内偏移 ） ，因此分段管理的地址空间是二维的
-
-
-
分段比分页更容易实现信息的共享与保护
由于段是紧凑的 ， 不像页那么分散 ， 更容易实现共享 ， 只需要让各进程的段表项指向同一个段即可 ，理由如下
-
（3）段页式存储管理
1.段页式存储的由来
首先看一下 分页 和 分段 的优缺点:
2.段页式存储
： 先分段 + 再分页
-
- 将地址空间按照程序自身的逻辑关系划分成若干个段，在将各段分为大小相等的页面
-
- 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
-
- 逻辑地址结构（段号 ，页号，页内偏移量 ），用户编程的时候只需要给出段号和段内地址，之后系统会自动把段内地址拆分成页号和页内偏移量 ，用户只提供这两个信息，所以是二维的
- 段号 + 页号 + 页内偏移 ---> " 分段 " 是对用户可见的 ， 程序编程时需要显式地给出段号、段内地址。而将各段 “ 分页 ” 对用户是不可见的 ， 系统会根据段内地址自动划分 页号和页内偏移量
3.段表
-
每个段表项由三部分组成 ： 段号（存储时可隐藏，因为页表项的长度是固定的 ）+ 页表长度 + 页表存放块号（页表起始地址）
- 页表存放块号指向的内存块，存放着一个页表，有页表长度个页表项，每个页表项由页号、页面存放内存号块组成，由于每个页表项长度相等，页号是隐含的
4.地址变换
-
一切的开端都是PCB把信息（段表始址 + 段表长度）放入到段表寄存器中去
内存扩充技术之-> 虚拟内存
传统存储管理方式的特征、缺点
一次性：
作业必须一次性全部装入内存后才能开始运行。会造成两个问题：
①作业很大时，不能全部装入内存，导致大作业无法运行
②当大量作业要求运行时，由于内存无法容纳所有的作业，因此只有少量的作业能运行，导致多道程序并发度下降
驻留性：
一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。
局部性原理
虚拟内存的定义和特征
特征：
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
- 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行的过程中，将作业换入、换出。
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
如何实现虚拟内存技术
允许一个作业多次调入内存。如果采用连续分配的方式，会不方便实现。因此，虚拟内存的实现需要建立在理算分配的内存管理方式基础上。
- 操作系统要提供请求调页（或请求调段）功能
- 操作系统要提供页面置换（或段置换）的功能
1. 请求分页管理方式
页表机制
- 与基本分页管理相比，请求分页管理中，为了实现 “ 请求调页 ” ， 操作系统需要知道每个页面是否已经调入内存 ； 如果还没有调入，那么也需要该页面在外存中存放的位置 。
- 操作系统需要通过某些指标来决定到底换出哪个页面 ，
- 有的页面没有被修改过 ， 就不用浪费时间
- 有的页面被修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改过
（多了）
状态位：是否已调入内存
访问字段：可记录最近被访问过几次，或记录上次访问的时间，共置换算法先择换出页面时参考
修改位: 页面调入内存后是否被修改过
外存地址：页面在外存中的存放位置
缺页中断机构
地址变换机构
新增步骤1 ：请求调页（查到页表项时进行判断）
新增步骤2： 页面置换 （需要调入页面，但没有空闲内存块时进行）
新增步骤3： 需要修改请求页表中的新增的页表
具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是：
2. 请求分段管理方式
3. 请求段页式管理方式
页面置换算法
- 页面的换入、换出需要磁盘 I/O ，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率
(1).最佳置换算法（OPT）
- 我们手动计算时，可以看看后面哪个出现的最晚，但是计算机是不可预测的，所以这种方法是无法实现的
- 缺页时未必发生页面置换。若还有可用的空闲内存块，就不用进行页面置换
(2).先进先出置换算法（FIFO）
- 算法性能是很差的
- 会出现 Belady 异常
(3).最近最久未使用置换算法（LRU）
least recently used
- 每次淘汰的页面是最近最久未使用的页面
为什么硬件开销大？
答：
系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU算法必须要有硬件的支持。
根据历史推测未来
可以使用 链表 或者使用 栈 来表示，但是用栈的话，需要查找之前的重复然后删除，查找的时间过长，淘汰，但其实都有不少开销
(4).时钟置换算法（CLOCK）
又称最近未用算法（NRU）(Not Recently Used )
由来
-
上述 FIFO 和 LRU 的取长补短 ， 取 FIFO 的优点 ， 用数据结构的方式将使用过的内存块按照顺序存储起来（FIFO是按照进入的先后用队列存储的，CLOCK 是用循环队列）
-
取 LRU 的优点 ，记录过去内存使用的状态信息 ， （LRU 记录的是上次使用的时间 ， 时时刻刻都要变化，开销太大 ， 而CLOCK 往访问位记录的是 1、0 ，1 表示最近访问过 ， 0 表示最近没有访问过 ）
简单CLOCK算法实现方式
-
第一步 ： 为每个页面设置一个访问位 ， 再将内存中的页面都通过链接指针链接成一个循环队列 。当某页被访问时 ， 其访问位为1
（有五个内存块 ， 访问 1，3，4，2，5 后五个内存块的访问位 都变成 1 ） -
第二步 ：如果能找到页面刚不在内存中，需要淘汰一个页面 ，只需要检查页的访问位。如果是 0 ，就选择该页换出 ， 如果是 1 ，就将他置0，暂不换出 ，继续检查下一个页面
时钟转了一圈把 1 ，3 ，4 ，2 ，5 的访问位都变为0 后来到了1号页的位置 ， 由于一号页的访问位为 0 ，所以可以换页 ， 换成6 号页后访问页立马变为 1
-
如果在页表中能找到有内存块地址 ，表示不用调页 ，只需要在访问的时候将 此页表项中的访问位改为 1
（访问 3 ， 4 号页面后 ，把访问位改为 1 就完成了）
-
按照第二步 ， 把2号页替换为 7 号页后 ， 指针指向下一页
(5).改进型的时钟置换算法
-
简单时钟置换算法仅考虑到一个页面最近是否被访问过，而事实上还要考虑到要将已经修改的页面写回到外存中
-
而如果被淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存
-
增加一个修改位
实现方式
将所有可能被置换的页面排成一个循环队列
- 第一轮 ：
- 第二轮 ：
- 第三轮 ：
- 第四轮 ：
页面分配策略
驻留集
- 指请求分页分配管理中给进程分配的 物理块 的集合（也相当于分配几个页框）
- 在采用虚拟存储技术的系统中，驻留集大小一般小于进程的总大小
- 驻留集太小：会导致缺页频繁，系统要花费大量的时间处理缺页，实际用于进程推进的时间很少
- 驻留集太大：会导致多道程序并发度下降，资源利用率降低。所以应该选择一个适合的驻留集大小
页面分配、置换策略
固定分配
操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
可变分配
先为每个进程分配一定数量的物理块，在进程运行期间，可根据情况适当的增加或减少，即，驻留集大小可变
局部置换
发生缺页时只能选进程自己的物理块进行置换
全局置换
可以将操作系统保留的空闲物理块分配给缺页额进程，也可将别的进程持有的物理块置换到外存，再分配给缺页进程
固定分配局部置换
可变分配全局置换
损人利己型！
可变分配局部置换
调入页面的时机
预调页策略
- 运行前调入，主要用于进程首次调入
请求调页策略
- 运行时调入
从何处调页
1.系统拥有足够的对换区空间
2.缺少足够的对换区空间
3.UNIX方式
抖动（颠簸）现象
工作集
指在某段时间间隔内，进程的实际访问页面的集合
第四章 文件管理
1.概念
2.文件逻辑结构
无结构文件（流式文件）
- 简单
有结构文件（记录式文件）
根据各条记录的长度是否相等，又可分为定长记录和可变长记录
(1) 顺序文件
文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长或可变长的。各个记录在物理上可以顺序存储或链式存储。
串结构
- 记录之间的顺序与关键字无关
顺序结构
- 记录之间的顺序按关键字顺序排列
随机存取
- 只有定长记录可以实现随机存取
(2) 索引文件
- 由于可变长文件很普遍 ， 必须用可变长记录，但是要从头找到尾，速度太慢
- 可以建立一张索引表以加快文件检索的速度。每条记录对应一个索引项
(3) 索引顺序文件
- 两者的折中，并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项
- 一本数不能每一页都加目录 ， 每一章加一个目录
查找的效率问题：
当 10^6 分为 1000组 * 1000 时，找的还是比较慢 ， 所以采用多级索引
本质就是空间换时间
(4) 直接文件 / 散列文件
- 利用哈希函数
- 有很高的存取速度
- 但是会因不同关键字的散列值相同而引起冲突
3.目录结构
-
目录本身就是一种有结构文件,目录文件是由一条条记录组成（一条记录就是一个‘文件控制块 FCB ’）。每条记录（FCB）对应一个放在该目录下的文件，可能是PNG、txt......等类型的文件 ，当然也可能是一个目录文件
(1)文件控制块
概念
- FCB的有序集合称为 “ 文件目录 ”
- 一个FCB就是一个文件目录项（目录指的是FCB包含众多基本信息、存取控制信息、使用信息的目录）
- 基本信息：文件名、物理地址、逻辑结构、物理结构
- 存取控制信息：是否可读 / 可写、禁止访问的用户名单
- 使用信息：文件的建立时间、修改时间
作用
- 实现了文件名和文件之间的映射。使用户（用户程序）可以实现 “ 按名存取 ”
操作
- 搜索 ：
- 创建文件 ：
- 删除文件 ：
- 显示目录 ：
- 修改目录 ：
(2)索引节点
是对 FCB 的改进
(3)目录结构
Ⅰ 单极目录页表
- 早期操作系统并不支持多级目录，整个系统只建立一张目录表，每个文件占一个目录项
- 单级目录实现了 “ 按名存取 ” ，但是不允许文件重名
- 单级目录机构不适应于多用户操作系统
Ⅱ 两级目录页表
- 方便不同用户的访问限制
Ⅲ 多级目录页表
- 便于文件实现分类
- 相对路径的使用减少了磁盘访问量
缺点：
- 但是在树形目录中查找一个文件时，需要按路径名逐级访问中间结点 ， 这就增加了磁盘访问的次数 ， 无疑会影响查询的速度
- 不利于实现文件的共享
Ⅳ 无环图目录页表
- 可以用不同文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）
删除比较麻烦了就：
-
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点
-
用户提出删除请求时，只是删除该用户的FCB、并使共享计数器减 1 ，并不会直接删掉该结点。只有共享计数器减为0 时，才删除结点
-
4.实现
4.1.文件系统层次结构
用例子方便记忆：
4.2.目录实现
线性表
散列表
- 根据文件名得到一个值，返回一个指向线性表的指针
- 优点：大大缩短了查找目录的时间，插入和删除也比较简单
- 缺点：需要一些措施来避免冲突，散列表长度固定，散列函数对表长有依赖性
4.3.文件分配
- 首先，物理块与内存块大小是一致的
- 类似于内存中（页号 ，页内偏移 ）， 外存中 （逻辑块号 ， 块内地址 ）
- 操作系统负责 讲用户可见的（逻辑块号 ， 块内地址 ） 转化为 用户不可见的 物理地址的映射 （物理块号 ， 块内地址 ）
4.3.1 连续分配
地址变换过程
-
用户给出要访问的逻辑块号
-
检查用户提供的逻辑块号是否合法（逻辑块号 >= 长度 就不合法）
-
操作系统找到该文件对应的目录项 （FCB）
物理块号 = 起始块号 + 逻辑块号
-
只需转换块号就行 ，块的地址保持不变
文件拓展
-
文件A要拓展，需要再增加一个磁盘块，由于采用连续结构，因此文件A占用的磁盘块必须是连续的
优点
- 可以直接算出逻辑块号对应的物理块号 ， 因此连续分配支持 顺序访问 和 随机访问（直接访问）
- 连续分配的文件在 顺序读 / 写时速度最快 （ 读取某个磁盘块时，需要移动磁头。访问的两个磁盘相隔越远，移动磁头所需时间就越长 ）
缺点
- 不方便拓展
- 存储空间利用率低，会产生难以利用的磁盘碎片，可以用紧凑来处理碎片，但是需要耗费很大的时间代价
4.3.2 链接分配
隐式链接
地址转变过程：
- 用户给出要访问的逻辑号块
- 操作系统找到该文件对应的目录项（FCB）
- 从目录项中找到起始块号 i（即 0 号块），将0号逻辑块读入内存，由此知道1号逻辑块号存放的物理块号 ， 于是读入1号逻辑块 ，再找到2号逻辑块的存放位置......以此类推
因此，读入 i 号逻辑块，总共需要 i+1 次磁盘 I/O
优点：
- 方便拓展文件，不会产生碎片问题，外存利用效率高
缺点：
- 只支持顺序访问，不支持随机访问，查找效率低下
- 而且是在磁盘中查找下一个盘块，相比于显示链接（FAT表在内存中）慢很多
- 另外，指向下一个盘块的指针也需要耗费少量的存储空间
显式链接
-
把用于链接文件各物理块的指针显示地存放在一张表中。即 文件分配表（FAT）
地址转变过程：
- 用户给出要访问的逻辑号块
- 操作系统找到该文件对应的目录项（FCB）
- 从目录中找到起始块号，若 i > 0 , 则查询内存中的文件分配表FAT
- 往后找到 i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作
优点：
-
采用链式分配（显式链接），支持顺序访问，也支持随机访问（就查个小FAT表，又不用大张旗鼓的调用磁盘I/O 去访问 n+1 磁盘，就在FAT 表中找 n+1 遍就行了 ）
-
由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多
-
方便拓展
缺点：
- 文件分配表常驻内存（FAT）其实也没事，就占一点的空间
索引分配
- 相当于 ： 进程 -> 此进程的页表 -> 页号对应的内存块地址
- 索引分配也建立一张类似于页表的索引表 ，索引表中记录了文件各个逻辑块对应的物理块
- 文件名 -> 索引块（这个磁盘块中记录着逻辑块 与 物理块的对应关系）-> 物理块号地址
地址转换过程：
-
用户给出要访问的逻辑块号 i
-
操作系统找到该文件对应的目录项（FCB），好家伙，FCB 中加入了文件索引块的磁盘块号 这一项 ，如下
-
从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表中 i 号逻辑块在外存中的存放位置
（类似与内存中 通过逻辑页号查寻页表项）
优点：
- 可以支持随机访问
- 文件的拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表即可 ）
缺点：
- 不同于显式链接，文件分配表（FAT）是一个磁盘对应一张，而索引分配方式中，索引表是一个文件对应一张，多占空间
问题：一个磁盘块存不下很多的索引项怎么办？
答：
① 链接方案
② 多层索引
-
文件最大长度的计算！！！
-
访问一个数据块需要多少次磁盘操作？
③ 混合索引
- 文件最大长度的计算！！！
优点：
索引分配总结！！！
总结
4.4文件存储空间管理
存储空间的划分与初始化
- 安装Windows 系统的时候，首先必经的步骤是-------为磁盘分区
管理方法---空闲表法
- 类似于固定分区分配、动态分区分配中建立分区说明表 ， 空闲表法设置空闲盘块表
- 适用于“连续分配方式”
分配磁盘块
分配算法
类似于内存的动态分配
-
首次适应算法 ： 找到第一个能够满足存储大小的存储块
-
最佳适应算法 ： 先把存储块从小到大排序 ， 每次分配时 ， 从小的往大的找 ，外部碎片的很多
-
最坏适应算法 ： 上述排序后 ， 先从大的放，导致再有大的时放不下
-
邻近适应算法 ： 最佳适应算法的基础上 ，设置一个指针 ， 从上次结束的位置存放 ， 导致高地址利用大 ，低地址利用小 ， 减少查找开销
回收磁盘块
四种情况分析：
① 回收区的前后都没有相邻空闲区
② 回收区前后都是空闲区
需要进行表项合并
③ 回收区前面是空闲区
④ 回收区后面是空闲区
管理方法---空闲链表法
空闲盘块链
- 一块一块的分 ，灵活 ，但是分配多的时候麻烦
空闲盘区链
- 一片一片的分，为一个文件分配多个盘块时效率更高
管理方法---位示图法（常考）
分配、回收
管理方法---成组链接法
- 为了适应大型文件系统 ， 因为空闲表或空闲链表可能过大 。UNIX系统中采用成组链表法对磁盘进行管理
- 文件卷的目录区中专门用一个磁盘块作为 “ 超级块 ” ，当系统启动时需要将超级块读入内存 。并要求要保证内存与外存中的 “ 超级块 ” 数据一致
5.磁盘
5.1 磁盘的结构
5.2 磁盘调度算法
一次磁盘读/写操作需要的时间
寻找时间
- 将磁头移动到指定磁道所花费的时间
延迟时间
传输时间
磁盘调度算法
- 磁盘调度算法可以影响的是寻找时间 ， 延迟时间和传播时间都是转速影响（线性）
先来先服务算法（FCFS）
最短寻找时间优先（SSTF）
扫描算法（SCAN）
- 虽然解决了饥饿的问题 ， 但是 边上的访问频率大于里面的访问频率 --- > 对于各个位置磁道的响应频率不平均
LOOK调度算法
- 边移动边观察 ， 如果在磁头移动方向上没有别的请求 ， 就可以立即改变磁头移动的方向
循环扫描算法（C-SCAN）
- 规定只有磁头朝某个特定方向移动时才能处理磁道访问的请求 ， 而返回时直接快速移动至起始而不处理任何请求
C-LOOK 调度算法
- C-SCAN 算法的基础上 增加了 LOOK ，不用走到最外面或者最里面才折回
5.3 减少磁盘延时时间的方法
- 磁头读入一个扇区数据后需要一小段时间处理 ， 如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要更长的 “ 延迟时间 ” ，也就是要转动好几次磁盘
使用交替编号的方式
磁盘地址结构的设计
- 柱面号在前 ， 盘面号在后
- 读取地址连续的磁盘块时，采用（柱面号，盘面号 ， 扇区号） 的地址结构可以减少磁头移动消耗的时间
错位命名
- 交替编号是对同一个扇面的编号规则
- 错位命名是对不同扇面 + 同一个柱面 的编号规则，与 ”交替编号“ 相同，使得相邻盘面的扇区编号 “ 错位 ”
- 感觉是统计规律
5.4 磁盘的管理
1.磁盘初始化
2.引导块
3.坏块的管理
6.文件的基本操作
6.1创建文件
6.2删除文件
6.3打开文件
- 打开文件表大幅度提升打开文件的速度
6.4关闭文件
6.5读文件
6.6 写文件
7.文件共享
- 区别于文件复制 ， 共享的时候文件改变其他调用的地方也可以看到
基于索引结点的共享方式（硬链接）
- 索引结点 ： 是对文件目录项的瘦身策略 ，除了文件名之外的其他信息可以放到索引结点中
- 牛，连目录项中的其他信息都复用 ， 省空间省到家了直接 ！！！
实现
删除
- 只是要把用户目录中与该文件对应的目录项删除 ， 且索引结点的count 值减1
基于符号链的共享方式（软链接）
- 并不是把自己的目录项直接指向这个文件的索引结点，而是新创建了一个 Link 型的文件 ， link 型文件中记录了这个文件的存放路径，之后这个Link文件找到这个共享文件
- Windows 中快捷方式就是这样的
8.文件保护
口令保护
加密保护
访问控制
第五章 输入/输出（I/O）管理
5.1概念与分类
分类
5.2 I/O控制器
5.2.1 I/O控制器的功能
5.2.2 I/O控制器的组成
- 控制线传输的是，打算执行的命令
细节
- ① 一个 I/O 控制器可能会对应多个设备
- ② 这样一来 ，数据寄存器 、状态寄存器、控制寄存器等都要有多个 ， 给不同寄存器编址成为了关键
5.2.3 两种编址方式
内存映像 I/O
寄存器独立编址
5.3 I/O 控制方式
5.3.1 程序直接控制方式
完成一次读/写操作的流程
- 1.首先 CPU 向控制器发出读指令，设备启动，并且状态寄存器设为1（未就绪）
- 2.轮询检查控制器状态（ 其实再不断地执行程序循环，若状态位一直是1，说明设备还没准备好要输入地数据，于是CPU会不断地轮询 ）
- 3.输入设备准备好数据后将数据传给控制器 ，并报告自身状态
- 4.控制器将输入地数据放到数据寄存器中，并将状态寄存器改为0（已就绪状态）
- 5.CPU发现设备已经就绪，即可将数据寄存器中的内容读入CPU的寄存器中，再把CPU寄存器中的内容放入内存 设备 -》CPU寄存器转存 -》内存中
- 6.若还要继续读入数据，则 CPU 继续发出读指令
CPU干预的频率
数据的传送单位
- 每次读/写一个字
数据的流向
- 读操作（数据流入）: I/O 设备 - 》CPU -》内存
- 写操作（数据输出）： 内存 -》CPU -》I/O 设备 （其实这个 I/O 设备 的那些寄存器 都在内存的分块中）
- 每个字的读/写 都需要CPU帮助
优点
- 实现简单
缺点
- CPU 和 I/O 设备只能串行工作
- CPU 需要一直轮询检查，长期处于 ”忙等“ 状态，CPU 利用率太低
5.3.2 中断驱动方式
完成一次读/写操作的流程
CPU干预的频率
-
每次 I/O 操作之前、完成之后需要CPU 介入
-
等待 I/O 完成的过程中CPU 可以切换到别的进程执行
-
CPU 会在每个指令周期的末尾检查中断 ， 频率高但是啥事也不耽误
数据的传送单位
- 每次 读/写 一个字
数据的流向
- 读操作（数据流入）: I/O 设备 - 》CPU -》内存 （其实这个 I/O 设备 的那些寄存器 都在内存的分块中）
- 写操作（数据输出）： 内存 -》CPU -》I/O 设备
优点
缺点
-
- 2.
5.3.3 DMA控制方式
（Direct Memory Access 直接存储器访问 ， 主要用于块设备的 I / O 控制 ） ， 引入新的设备 DMA控制器
改进
DMA控制器
- 注意 ： 传输数据时不是一次就将一整块数据全部写到 内存中 ， 而是一个字节一个字节的写 ，直到写完为止
完成一次读/写操作的流程
- 省去了经过CPU中转的过程
CPU干预的频率
- 仅在传送一个或多个数据块的开始和结束时，才需要 CPU 干预
数据的传送单位
- 每次读 / 写一个或多个块（ 每次读写的只能是连续的多个快，且这些块读入后再内存中也必须是连续的 ）
- 当是离散的块时 ， 采用 DMA 方式同样是需要CPU 发出多条 I/O 指令
数据的流向
- 读操作（数据输入） ： I/O 设备 -》内存
- 写操作（数据输出） ：内存 -》 I / O 设备
优点
- 数据传输以 “ 块 ” 为单位，CPU 介入频率进一步降低
- 数据的传输不在需要经过CPU 再写入内存，数据传输效率进一步增加
- CPU 和 I/O 设备的并行性得到提升
缺点
- CPU 每发出一条 I/O 指令 ，只能读 / 写一个或多个连续的数据块
- 如果要读 / 写 多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成
5.3.4 通道控制方式
通道：一种硬件，可以理解为“ 弱鸡版的CPU ” 。通道可以识别并执行一系列的通道指令
通道是一个计算机词汇，属于操作码，记数段，内存地址段等。能够完成内存与外设之间数据的传输。一个独立于CPU的专门I/O控制的处理机，控制设备与内存直接进行数据交换。它有自己的通道命令，可由CPU执行相应指令来启动通道，并在操作结束时向CPU发出中断信号。
- 其实对上面的改进就是： 不用 CPU 直接告诉 DMA 要操作的内存地址啥的 ，而是通知 通道 去执行通道程序 ，就是去打个招呼 ，不是详述， 这样通道按照通道程序的内容工作，解放了CPU 详述的过程
完成一次读/写操作的流程
CPU干预的频率
数据的传送单位
- 每次读/写一组数据块
数据的流向
优点
- CPU 、通道 、 I/O设备可并行工作，资源利用率很高
缺点
- 实现复杂，需要专门的通道硬件支持
DMA vs 中断方式
DMA vs 通道
5.3.5 I/O 软件层次结构
用户层软件
设备独立性软件
-
也就是系统调用的处理程序
-
设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现
作用：
① 向上层提供统一的调用接口（如 read / write 系统调用）
② 设备的保护
- 原理与文件类似，设备被看做是一种特殊的文件，不同用户对文件的访问权限不一样，同理，对设备的访问权限也不一样
③ 差错处理
④ 设备的分配与回收
⑤ 数据缓冲区管理
- 屏蔽设备之间数据交换单位大小和传输速度的差异
⑥ 建立逻辑设备名到物理设备名的映射关系：根据设备类型选择调用响应的驱动程序
-
逻辑设备名：
- 类似于之前单用户系统和多用户系统
设备驱动程序
中断处理程序
5.3.6 I/O 核心子系统
I/O 调度
- 类似于磁盘调度（先来先服务算法、最短寻道算法、SCAN算法、、、、、）
- 当多个磁盘 I/O 请求到来时，用某种调度算法确定满足 I/O 请求的顺序
- 同理，打印机等设备也可以用先来先服务算法、优先级算法、短作业优先算法来确定 I/O 调度顺序
设备保护
- 不同的用户对各个文件有不同的访问权限
- 在UNIX系统中，设备被看作是一种特殊文件，每个设备有对应的 FCB 。 当用户请求访问某个设备时，系统根据FCB 中记录的信息来判断该用户是否有相应的访问权限，以此实现 “ 设备保护 ” 的功能。
5.3.7 假脱机技术（SPOOLing技术）
- 其实是用户层软件实现的 ， 408 中归为I/O核心子系统
1.概述
- 脱机主机的控制进行的输入/输出操作 ，使用外围控制机输入输出 而不是占用 CPU 去等待执行 相当于一个预存设备 。
2.假脱机技术实现原理
输入井和输出井
输入进程和输出进程
- “ 输入进程 “ 模拟脱机输入时的外围控制机
- ” 输出进程 “ 模拟脱机输出时的外围控制机
输入/输出缓冲区
3.共享打印机的原理分析
- 用假脱机技术实现 ” 独占式设备 “ 变为 ” 共享设备 “
过程：
当多个用户进程提出输出打印的请求时，系统会答应他们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
（1）在磁盘输出井中为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的），并将要打印的数据送入其中
（2）为用户进程申请一张空白的打印请求表（相当于 电工的操作票 ），并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件的队列上
（3）当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要求打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完成打印任务
5.3.8设备的分配与回收
设备分配时应考虑的因素
设备的固有属性
设备分配算法
设备分配中的安全性
-
安全分配方式 会用进程阻塞的方式只使用一个设备 ， 不会产生死锁
-
不安全方式在进程中可以同时使用多个设备 ， 会产生死锁
因为一般需要多个设备时才可能产生死锁
例：假设一个系统具有三个 CD 刻录机。假定有三个进程，每个进程都占用了一台 CD 刻录机。如果每个进程现在需要另一台刻录机，那么这三个进程会处于死锁状态。每个进程都在等待事件“CD刻录机被释放”，这仅可能由一个等待进程来完成。这个例子说明了涉及同一种资源类型的死锁。
静态分配与动态分配
静态分配
- 进程运行之前为其分配全部的所需资源 ， 运行结束后归还资源
这样破坏了请求和保持条件 ， 就不会发生死锁
动态分配
- 动态申请设备资源
设备分配管理中的数据结构
设备控制表（DCT）
控制器控制表（COCT）
通道控制表（CHCT）
系统设备表（SDT）
- 记录了系统中全部设备的情况，每一个设备对应一个表目
设备分配的步骤
缺点：
设备分配步骤的改进方法
- 设备类型即逻辑设备名
5.3.9缓冲区管理
缓冲区特性：满了之后才可以取数据 ， 空了之后才可以放数据
缓冲区概念
- 缓冲区是一个存储区域 ， 可以由专门的硬件寄存器组成，也可利用内存作为缓冲区
- 使用硬件作为缓冲区的成本比较高，容量也比较小，一般仅用在对速度要求非常高的场合 ， 如快表 cache
- 快表就是存放在高速缓冲存储器的部分页表。作为页表的Cache
作用：
- 缓和CPU 与 I/O 设备之间速度不匹配的矛盾
- 减少对 CPU 的中断频率 ， 放宽对 CPU 中断相应时间的限制 （每次只有 缓冲区的数据被填满了才会被执行 ）
- 解决数据粒度不匹配的问题
- 输出进程每次可以生成一块数据，但是 I/O 设备每次只能输出一个字符
- 利用缓冲区就可以 先存储下来 ， 然后将 字符一个个读或者一个个存
- 提高 CPU 与 I/O 设备之间的并行性
单缓冲
双缓冲
使用单 / 双 缓冲区在通信时的区别
- 单缓冲区决定了只能单向传输
循环缓冲
缓冲池
名词解释
绪论
时钟中断
- 主要工作是处理和时间有关的信息以及决定是否执行调度程序
- 和时间有关的所有信息包括：系统时间、进程的时间片、延时、使用CPU时间、各种定时器
各种中断
- 高分笔记 P287
指令周期
是指计算机从取指到指令执行完毕的时间
CPU周期
CPU周期亦称机器周期， 完成一个基本操作所需要的时间称为机器周期，基本操作如取指令、存储器]读、存储器写等。
通常用内存中读取一个指令字的最短时间来规定CPU周期。
----》一条指令执行过程被划分为若干阶段，每一阶段完成所需时间
时钟周期
又称震荡周期，是处理操作的最基本单位。在一个时钟周期内，CPU仅完成一个最基本的动作。
DMA
- 为什么DMA方式的优先级高于程序中断方式
DMA传送方式的优先级高于程序中断，两者的区别主要表现在对CPU的干扰程度不同。
程序中断请求不但使CPU停下来，而且要CPU执行中断服务程序为中断请求服务，这个请求包括了对断点和现场的处理以及CPU与外设的传送，所以CPU付出了很多的代价；DMA请求仅仅使CPU暂停一下，不需要对断点和现场的处理，并且是由DMA控制外设与主存之间的数据传送，无需CPU的干预，DMA只是借用了一点CPU的时间而已。
进程管理
并行性、并发性
- 并发性指的是多个程序（或线程、进程等）同时执行的能力 ，解决了计算机在处理多个任务时的瓶颈问题。
- 并行性（Parallelism）是指同一时间内，多个程序在多个处理器上同时执行的能力。相比并发性，它更强调任务的同时性执行和加速计算的能力。
并发性VS 并行性 ：
-
并发性强调多个任务在时间上的交替执行，而并行性强调多个任务在空间上的同时执行，各自独立地运行在不同的处理器上。
简单的说，并发性利用处理器分时，在一个时间段内将几个任务轮流进行，看起来就像是同时发生，就叫并发 ； 而并行性强调保障几个任务在多处理器上同时进行
进程映像
- 其实就是维持进程正常运行的静态数据，包括（ 程序段、相关数据、PCB构成 ）
进程
- 实体的运行过程，是系统进行资源分配和调度的基本单位
内核
- 内核通常被设计为一个运行在特权模式下的单独的程序，它具有最高的权限，可以访问所有的系统资源。负责调度进程、管理内存、文件系统、设备驱动程序等重要功能。
定时器(Timer)
- 是一种用于测量时间间隔、执行计划任务或触发事件的重要工具。定时器可以用于各种用途，包括调度任务、实现超时处理、测量程序执行时间、实现周期性任务等。
- 可以通过中断、时钟信号或其他机制来触发系统中注册的定时任务
周转时间
-
周转时间 = 等待时间 + 执行时间 = 作业完成时间 - 作业到达时间
-
平均周转时间 = 周转时间 / 作业个数
-
带权周转时间 = 周转时间 / 执行时间 = 等待时间 / 执行时间 + 1 （相当于短作业等待时间越长，带权周转时间越大，性能越差）
多道程序设计技术
管理单处理器系统中的多个进程
多道程序系统通过组织作业（编码或数据）使CPU总有一个作业可以运行
优点：从而提高了CPU的利用率、系统的吞吐量、和I/O设备利用率
缺点：付出开销来组织和切换作业
- 单道：内存中仅有一道程序运行，可以看成是串行的
- 多道：内存同时存放多道程序，宏观上并行，微观上串行
批处理
动态装入（Dynamic Loading）
- 允许程序在运行时动态地加载模块或库文件，而不需要在程序启动时将所有代码都加载到内存中。这种技术使得程序能够更加灵活地管理资源，并且可以根据需要动态加载所需的组件。
动态链接（Dynamic Linking）
- 是指在程序运行时将所需的库文件加载到内存中，并进行符号解析和重定位，使得程序可以调用这些库中的函数。这样可以节省内存空间，提高符号的共享和重用性。
动态装入和动态链接的区别：
-
动态链接更关注于共享库文件的加载和符号的解析，以提供程序与外部库的灵活连接
-
动态装入更关注于程序功能模块或资源的延迟加载和按需加载，以提高程序的灵活性和效率。
二元信号量，互斥量
- 二元信号量只取 0 / 1 值
- 互斥量类似于二元信号量。关键区别在于为其加锁（设定值为0）的进程和为其解锁（设为值1）的进程必须为同一个进程
自旋锁
- 一种互斥机制，进程在一个无条件循环中执行，等待锁变量的值可用
强 , 弱信号量
- 强信号量规定等待进程从等待队列中移除的顺序，为FIFO
- 弱信号量没有规定移出顺序
忙时等待 / 排队等待
忙式等待： 不进入等待状态的等待叫做忙式等待，进程并未真正的等待状态，实际为运行态或者就绪态
排队等待： 进程得到不共享资源时，进入阻塞状态，让出处理机给其他进程使用。
系统调用
系统调用是用户发起的，请求操作系统的服务
- 系统调用是操作系统提供给程序员或应用程序使用的接口，可以理解为给应用程序调用的特殊函数
- 应用程序通过系统调用请求操作系统的服务
- 与资源有关的操作，如存储分配、IO操作、文件管理等，都必须由系统调用的方式向操作系统请求，由操作系统对各个请求进行协调管理，这样可以保证系统的稳定性和安全性
- 系统调用的相关处理在核心态下进行，因为系统调用涉及到对系统资源的管理，对进程的控制，这些功能需要执行一些特权指令才能完成
进程、线程控制块
进程控制块 ---- PCB
线程控制块 -----
- 线程控制块的作用是提供操作系统对线程进行管理和调度所需的所有信息。当线程被创建时，会分配相应的线程控制块，并在执行过程中更新其中的状态和信息。操作系统通过访问线程控制块来实现对线程的调度、切换、资源管理等操作。
- 操作系统只为内核级线程建立一个线程控制块，用户级线程共享底层调用的内核级线程控制块
竞争条件 ( race condition )
内存管理
覆盖技术
目的：为了解决大作业和小内存的矛盾
- 把一个大的程序划分成一系列的覆盖（就是一段程序噻），每个覆盖是一个相对独立的程序单位。
- 把运行过程中不需要同时装入内存的覆盖组成一组，成为覆盖段
- 将这个覆盖段分配到同一个存储区域，这个存储区域称为覆盖区。每次只能将一个覆盖放入覆盖区内
- 利用在一个程序中使不同分区共享相同的内存区域
交换技术
- 把暂时不用的程序段及其数据区从内存迁移到外存中
工作集
操作系统中的工作集（Working Set）是指进程当前正在使用的内存页面集合。工作集的作用在于优化内存管理和提高系统性能，具体包括以下几个方面：
-
内存分配优化：通过监测工作集的变化，操作系统可以根据进程的内存需求进行动态的内存分配。当进程的工作集较小时，操作系统可以适时释放一部分内存资源，以便给其他进程使用。而当工作集增大时，则可以为进程分配更多的内存空间，避免频繁发生缺页中断和页面置换，提高运行效率。
-
页面置换决策：当系统内存不足时，操作系统需要选择哪些页面置换出去以腾出空间供其他页面加载。工作集可以提供有关进程当前使用的页面信息，使得操作系统能够更准确地选择置换页面，尽量避免置换掉进程正在使用的页面，从而减少缺页和性能下降的可能性。
-
缓存预取优化：操作系统可以根据工作集的变化情况，在进程需要某些页面之前，提前将其从磁盘读入内存中，以加快访问速度。这样可以有效减少页面访问延迟，提高应用程序的响应性能。
-
内存资源管理：通过监控进程的工作集大小，操作系统可以更好地管理和控制内存资源的分配。针对使用较大工作集的进程，可以进行优先级调度，保证其获得足够的内存资源，避免因内存瓶颈而导致的性能下降或系统崩溃。
综上所述，工作集在操作系统中的作用是提供关于进程当前内存使用情况的信息，以便操作系统做出合理的内存管理和优化策略，以提高系统性能和资源利用效率。
虚拟内存技术
内存映射文件
- 利用虚拟内存技术，将文件 I/O 作为普通内存访问
- 开始时，按照普通请求页面调度进行，产生页错误，这样一页或多页读入内存。以后文件的读写就按内存访问来处理。而不是使用系统调用 read() write()
反向页表-线性倒排(inverted page table)
哈希页表-散列倒排
文件管理
内存/磁盘索引结点
内存索引节点和磁盘索引节点主要有以下区别：
- 存储位置：内存索引节点存储在计算机的内存中，而磁盘索引节点存储在磁盘上。
- 访问速度：由于内存的读写速度比磁盘快得多，内存索引节点的访问速度更高。内存索引节点可以直接从内存中读取，而磁盘索引节点需要通过磁盘的物理读取操作来获取。
- 容量限制：内存的容量通常比磁盘小得多。因此，内存索引节点的容量受到内存大小的限制，而磁盘索引节点可以存储更大量级的数据。
- 持久性：内存是易失性存储，意味着断电或重启系统后，内存中的数据会丢失。因此，内存索引节点不具备持久性，需要在运行时动态构建。相反，磁盘是非易失性存储，磁盘索引节点可以持久保存在磁盘上，在系统重启后仍然可用。
- 更新频率：内存索引节点通常用于频繁更新的场景，因为其访问速度快，能够快速响应数据变化。磁盘索引节点一般用于静态或者较少更新的场景，因为磁盘访问速度相对较慢。
综上所述，内存索引节点适用于数据量较小且需要频繁访问和更新的情况，而磁盘索引节点适用于数据量较大、持久保存并且访问频率较低的情况。通常，磁盘索引节点会在运行时从磁盘加载到内存中，以提高数据的访问速度。
多个进程访问一个文件
- 文件描述符（File Descriptors）：在Unix-like系统中，每个进程都有一个打开文件描述符表，它是一个指向打开文件的索引。通过获取相同的文件描述符，多个进程可以访问同一个文件。这意味着它们可以独立地读取或写入文件，并且文件偏移量也是独立的。通过使用适当的同步机制（如锁），可以确保多个进程对文件的访问不会发生冲突。
文件系统
- 文件系统（File System）：一个文件系统（File System，缩写为FS）是指操作系统中用于管理存储设备上数据的一组算法和数据结构。它决定了数据在存储设备中的组织方式、如何读写数据以及如何管理文件和目录等元数据信息。
挂载点
挂载点（Mount Point）：挂载点是指一个目录，在该目录下的位置可以通过访问文件系统来访问该目录下的文件和子目录。在Unix-like操作系统中，挂载点通常位于根目录下的某个子目录中。
虚拟文件系统
磁盘物理格式化、逻辑格式化
-
物理格式化：
- 物理格式化是指在磁盘上创建扇区和磁道等物理结构的过程。在物理格式化时，磁盘被划分为多个扇区，每个扇区包含固定数量的数据块。物理格式化确定了磁盘的物理结构，包括扇区大小等。
- 扇区大小是在磁盘物理格式化时就确定的，通常是512字节或4KB。
-
逻辑格式化：
- 逻辑格式化是指在已经经过物理格式化的磁盘上创建文件系统的过程。在逻辑格式化时，磁盘被划分为文件系统所使用的磁盘块，这些磁盘块是文件系统管理的最小单位。
- 磁盘块大小是由文件系统来决定的，不同的文件系统可以有不同的磁盘块大小。常见的磁盘块大小包括4KB、8KB等。
设备管理
字符设备
- 能像字节流一样以串行顺序依次访问的设备，对它的读写是以字节为单位的 ；
- 其上层并没有磁盘文件系统，应用程序直接通过 read()、write()等系统调用读写字符设备文件
- 例如：鼠标、键盘等就属于字符设备
块设备
- 以数据块的形式存放数据，并通过mount方式挂载
- 块设备必须能够随机存取
- 除提供给内核字符设备一样的接口外，还要提供专门面向块设备的接口
- 此接口还必须支持挂载文件系统
块设备是i/o设备中的一类，是将信息存储在固定大小的块中，每个块都有自己的地址，还可以在设备的任意位置读取一定长度的数据，例如硬盘,U盘，SD卡等。
网络设备
P283
设备控制器
设备一般有机械部分和电子部分组成，设备的电子部分通常称之为设备控制器
- 设备控制器处于CPU 与 I/O设备之间，接受来自CPU 的命令，并控制I/O设备工作
- 设备控制器是一个可编址设备
- 当仅控制一个设备时，只用一个设备地址
- 当控制多个设备时，使用多个设备地址
组成：
- 控制寄存器 -》存放命令和参数
- 状态寄存器 -》供CPU查询设备状态
- 数据寄存器
设备独立性
- 是指用户程序独立于具体物理设备的一种特征
优点：
- 独立于某类设备中的某个具体设备 -> 用逻辑设备名来申请某类物理设备，改善资源利用率和适用性
- 独立性使用户独立于设备类型，入进行输出时，既可以用终端，也可以用打印机
设备独立性软件
- 也就是系统调用的处理程序
驱动程序
为每一类设备配置一个驱动程序
接受来自上层的设备独立性软件的抽象请求，将这些请求转换为设备控制器可以接受的具体命令
- 低层部分：由处理程序组成，当发生中断时调用，即为设备的中断处理程序
- 高层部分：由一些函数组成，在应用程序请求I/O操作时调用
- 一组共享变量：保存协调高层部分和低层部分所需要的状态信息
文件系统层
- 包括虚拟⽂件系统和其他⽂件系统的具体实现，它向上为应⽤程序统⼀提供 了标准的⽂件访问接⼝，向下会通过通⽤块层来存储和管理磁盘数据
通用块层
- 包括块设备的 I/O 队列和 I/O 调度器，它会对⽂件系统的 I/O 请求进⾏排队， 再通过 I/O 调度器，选择⼀个 I/O 发给下⼀层的设备层
设备层
- 包括硬件设备、设备控制器和驱动程序，负责最终物理设备的 I/O 操作
通道
本质是一个独立与CPU的简单的处理器，有运算和控制逻辑，有自己的指令系统，控制设备与内存直接进行数据交换 ；可由CPU执行相应指令来启动通道，并在操作结束时向CPU发出中断信号。 ； 通道没有自己的内存，需要和CPU共享内存
管道
- 管道（Pipe）：管道是一种半双工的、按顺序传输的字节流通信机制。它可以用于父子进程之间或者具有亲缘关系的进程之间进行通信。在Unix-like操作系统中，可以通过调用pipe系统调用创建一个管道，并使用fork系统调用来创建父子进程之间的通信管道。管道的数据传输是基于FIFO（先进先出）原则的，即写入的数据按照写入的顺序以字节流的形式被读取。
- 实际是一种固定大小的缓冲区（大小通常为内存的一页），只存在与内存中，一个管道可以实现双向的数据传输，但是同一时刻只能最多有一个方向的传输
安全
ACL
ACL是Access Control List的缩写，中文名为访问控制列表。ACL是一种常用于计算机系统中的安全机制，它通过定义用户或用户组对资源的访问权限，限制了未经授权的访问和操作。
在ACL中，每个资源都会有一个与之对应的ACL表，该表描述了谁可以访问该资源以及访问时所具备的权限。ACL表通常包括两个部分：访问控制项（ACE）和可访问用户列表。
访问控制项（ACE）是定义资源访问权限的基本单位，它包括一个安全标识符（SID）和一些访问控制标志（ACE Flags）。安全标识符可以是用户、用户组或者计算机，而访问控制标志则表示允许或拒绝该用户或用户组对资源的访问，以及访问时所具备的权限。
可访问用户列表则列出了所有被授权访问该资源的用户或用户组。当用户请求访问该资源时，系统会检查其身份是否在可访问用户列表中，并根据对应的访问控制项决定是否允许该用户访问。
ACL可以实现对不同级别的访问控制，例如读、写、删除等操作。它可以应用于各种资源，如文件、文件夹、打印机、网络等。ACL对于保障系统的安全性和完整性非常重要，它可以有效地限制未授权的访问和操作，保护系统免受恶意攻击和误操作的影响。
总之，ACL是一种常用于计算机系统中的安全机制，它通过定义用户或用户组对资源的访问权限，限制了未经授权的访问和操作。ACL表包括访问控制项和可访问用户列表，可以实现对不同级别的访问控制，应用于各种资源，如文件、文件夹、打印机、网络等。
PV操作疑惑
1.为什么在读者-写者问题中：readcount 和 writecount要互斥访问
2.
到底咋才能实现写者一进去就能写呢？？？？
标签：操作系统,访问,页表,进程,磁盘,CPU,内存 From： https://www.cnblogs.com/Lctrl/p/18004990