【学习笔记】操作系统知识点整理
第一章 概述
第一节 操作系统的特征
一、并发（最基本）
注意（重要考点）：
单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行
多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行
很多人搞不清楚并发和并行的区别？
并发：多个事件在同一时刻内发生，操作系统并发性是指同时存在多个运行的程序。在宏观上是一起发生，但在微观上是交替执行的。
并行：同一时间内多个事件同时发生，宏观上，微观上都是都是发生的。
二、共享（最基本）
共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。
- 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问。
- 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。
三、虚拟
虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。
把你内存“变大了”，实际上没变大，但在感觉上变大了
四、异步
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
第二节 操作系统的发展
一、手工操作阶段（此阶段无操作系统）
缺点：独占全集。速度极慢。CPU利用不充分。
二、批处理阶段
Ⅰ、单道批处理系统
主要优点：缓解了一定程度的人机速度矛盾资源利用率有所提升。
主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。
Ⅱ、多道批处理系统
主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。
主要缺点：没有人机交互。
三、分时操作系统
分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。
主要优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。
主要缺点：不能优先处理一些紧急任务。操作系统对各个用户作业都是完全公平的，循环地为每个用户作业服务一个时间片，不区分任务的紧急性。
四、实时操作系统
主要优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队。
- 系统调用时操作系统为应用程序使用内核功能锁提供的结构。
第三节 操作系统运行机制
一、内核态和用户态
CPU有两种状态，“内核态”和“用户态”
- 处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
- 处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令
CPU能判断出指令类型，但是它怎么区分此时正在运行的是内核程序还是应用程序？
CPU中有一个寄存器叫程序状态字寄存器(PSW)，其中有个二进制位，1表示“内核态”，0表示“用户态”。
- 访管指令：只能是用户态使用，作用是将用户态转变为核心态
- 处于核心态时，可以执行除访管指令的所有指令
- 广义指令是指系统调用指令，可以由用户态调用，但只能由核心态运行
- 输入/输出指令涉及到中断，所以必须在核心态
- 计算机通过硬件完成操作系统由用户态到核心态的转换，这是通过中断机制来实现的
二、中断
Ⅰ、中断类型
中断：也称外中断，是指来自CPU外部的事件。很典型的是一个时钟中断（并发运行的基础），表示一个固定的时间片已到，让处理机处理计时、启动定时运行的任务等。
异常：也称内终端，是指来自CPU内部的事件。如程序的非法操作码、地址越界、运算溢出等，异常不能被屏蔽，一旦出现就应该立即处理。
如何处理中断？
不同的中断信号，需要用不同的中断处理程序来处理。当CPU检测到中断信号后，会根据中断信号的类型去查询“中断向量表”，以此来找到相应的中断处理程序在内存中的存放位置。
- 在中断相关操作中，保存被中断的断点/PC里面的内容是由硬件自动完成的。
三、系统调用
传递系统调用参数→执行陷入指令（用户态）→执行相应的内请求核程序处理系统调用（核心态）→返回应用程序
- 陷入指令/trap指令/访管指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态。
- 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。
第四节 操作系统的结构
一、操作系统的结构（新增考点分层，模块化，外核）
| 优点 | 缺点 | |
|---|---|---|
| 分层结构 | 易于调试和验证 易扩充和易维护 | 仅可调用相邻层 效率低，不可跨层调用 |
| 模块化 | 易于维护，逻辑清晰 各模块之间直接调用 | 难以调式和验证 |
| 大内核 | 性能高，内核个功能直接调用 | 复杂，难以维护，一个功能坏全部瘫痪（可靠性低） |
| 微内核 | 功能少，易于维护 某个出错不会导致整个崩溃 | 性能低，需要频繁切换状态 |
| 外核 | 更灵活使用硬件资源 减少资源的映射层提升效率 | 使系统更加复杂 降低系统的一致性 |
二、操作系统的加载
①CPU从一个特定主存地址开始，取指令，执行ROM中的引导程序（先进行硬件自检，再开机）。
②将磁盘的第一块一一主引导记录读入内存，执行磁盘引导程序，扫描分区表。
③从活动分区（又称主分区，即安装了操作系统的分区）读入分区引导记录，执行其中的程序。
④从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成“开机”的一系列动作。
三、虚拟机
第二章 进程与线程
第一节 进程
一、进程的概念
背景：为了实现操作系统的并发性和共享性，以便更好的描述和控制程序的并发执行，由此引入了进程的概念。
进程实体（进程映像）由三部分组成：程序段、数据段、PCB（进程控制块）组成。PCB是进程存在的唯一标志。PCB是给操作系统用的，而程序段和数据段是给进程自己使用的。
※进程映像是静态的，而进程则是动态的
- 学习技巧：进程控制会导致进程状态的转换。无论哪个进程控制原语，要做的无非三类事情：
1.更新PCB中的信息
a.所有的进程控制原语·定都会修改进程状态标志
b.剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c.某进程丌始运行前必然要恢复期运行环境
2.将PCB插入合适的队列
3.分配/回收资源
二、进程的状态
- 从运行态转变为就绪态有两种情况——时间片用完，有优先级更高级的进程需要运行。
- 只有运行态到阻塞态的转换是由进程自身决定的。
三、进程间的通信
为什么进程通信需要有操作系统的支持？
进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。为了保证安全，一个进程不能直接访问另一个进程的地址空间。
Ⅰ、共享存储
设置一个共享内存区域，并映射到进程的虚拟地址空间，要互斥的访问共享空间，有基于数据结构（低级）和基于存储区的共享（高级）
Ⅱ、消息传递
传递结构化的消息，系统提供“发送/接受原语”，两种方式，直接通信方式和间接通信方式
直接通信方式是将消息直接挂到接受进程的消息队列里。
间接通信方式是将消息先发送到中间体。
Ⅲ、管道通信
设置一个管道，其实就是一个内存缓冲区，一个管道只能实现半双工通信，实现双向同时通信要建立两个管道，各各进程之间要互斥访问。
一个管道只能有一个读进程，但能有多个写进程。当管道为空时，读进程阻塞；当管道不为空时，写进程阻塞。
第二节 线程
背景：有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件)
| 进程 | 线程 | |
|---|---|---|
| 资源 | 资源分配的基本单位哦 | 资源调度的基本单位 |
| 并发性 | 只能进程间并发 | 进程内也可以并发 |
| 系统开销 | 开销大 | 开销小 |
| 地址空间和资源 | 每个进程之间独立的地址空间和资源 | 共享地址空间和资源 |
Ⅰ、用户级线程
1.线程的管理工作由准来完成？
2.线程切换是否需要CPU变态？
3.操作系统是否能意识到用户级线程的存在？
4.这种线程的实现方式有什么优点和缺点？
1.用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换)。
2.用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
3.在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”。
4.优缺点
优点：用户级线程的切换在用户空问即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
Ⅱ、内核级线程
1.内核级线程的管理工作由操作系统内核完成。
2.线程调度、切换等工作都由内核负贵，因此内核级线程的切换必然需要在核心态下才能完成。
3.操作系统会为每个内核级线程建立相应的TCB(Thread Control Block,线程控制块)，通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”。
4.优缺点
优点：当个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
Ⅲ、多线程模型
| 一对一 | 多对一 | 多对多 | |
|---|---|---|---|
| 内容 | 将每个用户级线程映射到一个内核级线程 | 多个用户级线程映射到一个内核级线程 | 多个用户级线程映射到多个内核级线程上 |
| 优点 | 当一个线程被阻塞后，允许调度另一个线程运行，并发能力强 | 线程管理是在用户空间上进行的，效率比较高 | 克服多对一的缺点，有客服一对一开销大的缺点 |
| 缺点 | 每创建一个用户级线程，相应就需要创建一个内核级线程，开销大 | 如果一个线程阻塞，则都会发送阻塞，只允许一个线程运行 | / |
第三节 处理机调度
一、调度的分类
Ⅰ、高级调度（作业调度）：从后备队列中调入一个作业进入就绪队列中。
Ⅱ、中级调度（内存调度）：中级调度实际上是外存与内存之间的调度。把进程从外存调入。
Ⅲ、低级调度（进程调度）：从就绪队列中选取一个进程，然后使其由就绪态变为执行态。
二、
三、算法指标
- 周转时间反映的是等待时间+运行时间。
- 带权周转时间越大，表明要等待的时间相对运行时间越长。所以不是越大越好，而是越小越好。
四、调度算法
Ⅰ、先来先服务算法（FCFS）
算法思想：主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子)， 先请求 CPU 的进程首先分配到 CPU。当一个进程进入就绪队列时，它的 PCB 会被链接到队列尾部。当 CPU 空闲时，它会分配给位于队列头部的进程，并且这个运行进程从队列中移去。
算法规则：按照作业/进程到达的先后顺序进行服务
用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占?：非抢占式的算法，即一旦 CPU 分配给了一个进程，该进程就会使用 CPU 直到释放 CPU 为止，即程序终止或是请求 I/O。FCFS 算法对于分时系统（每个用户需要定时得到一定的 CPU 时间）是特别麻烦的。允许一个进程使用 CPU 过长将是个严重错误
优缺点
- 优点：公平、算法实现简单
- 缺点：排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。
- 是否会导致饥饿(某进程/作业长期得不到服务)：不会
Ⅱ、短作业优先调度算法（SJF）
算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间
算法规则：按”最短的作业/进程优先得到服务(所谓“最短”，是指要求服务时间最短)
用于作业/进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先(SPF, Shortest Process First) 算法”
是否可抢占?：SJF和SPF是非抢占式的算法。但是也有抢占式的版本--最短剩余时间优先算法( SRTN, Shortest Remaining Time Next )
最短剩余时间优先算法——每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间【剩余运行时间】比当前运行的进程剩余时间更短，则由新进程抢占CPU，而当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要根据该调度算法进行调度
优缺点
- 优点：“最短的”平均等待时间、平均周转时间。
- 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的， 并不一定真实，不一定能做到真正的短作业优先。
是否会导致饥饿(某进程/作业长期得不到服务)：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为 "饿死"
Ⅲ、高响应比优先调度算法
算法思想：要综合考虑作业/进程的等待时间和要求服务的时间
算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务【响应比>=1】 响应比等待时间要求服务时间要求服务时间响应比=等待时间+要求服务时间要求服务时间
用于作业/进程调度：即可用于作业调度，也可用于进程调度。
是否可抢占?：非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
优缺点
- 综合考虑了等待时间和运行时间(要求服务时间)
- 等待时间相同时，要求服务时间短的优先(SJF 的优点)
- 要求服务时间相同时，等待时间长的优先(FCFS 的优点)
- 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
是否会导致饥饿(某进程/作业长期得不到服务)：不会
这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。
Ⅳ、优先级调度算法
算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则：调度时选择优先级最高的作业/进程
用于作业/进程调度：既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中
是否可抢占?：抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需 在就绪队列变化时，检查是否会发生抢占。
优缺点
- 优点:用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
- 缺点:若源源不断地有高优先级进程到来，则可能导致饥饿
是否会导致饥饿(某进程/作业长期得不到服务)：可能会导致饥饿。
非抢占式的优先级调度算法:每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。
抢占式的优先级调度算法:每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。
静态优先级：优先级是在创建进程时就已经确定了，且整个运行期间保持不变。
动态优先级：在进程运行过程中，根据进程的情况的变化动态调整优先级。
一般来说：系统进程>用户进程；交互型>非交互型；I/O型进程>计算型进程。
Ⅴ、时间片轮转调度算法
算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
用于作业/进程调度：用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)
是否可抢占?：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟 装置发出时钟中断来通知CPU时间片已到
优缺点
- 优点：公平;响应快，适用于分时操作系统;
- 缺点：缺点:由于高频率的进程切换，因此有一定开销;不区分任务的紧急程度。
是否会导致饥饿(某进程/作业长期得不到服务)：不会。
（常考）时间片太长或太短会有什么影响？
如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。
另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。
Ⅵ、多级反馈队列调度算法（最好的算法）
综合以上的调度算法的优点
- FCFS算法的优点是公平
- SJF算法的优点是能尽快处理完短作业，平均等待/周转时间等参数很优秀
- 时间片轮转调度算法可以让各个进程得到及时的响应
- 优先级调度算法可以灵活地调整各种进程被服务的机会
题型总结：
第四节 同步与互斥
一、同步与互斥概念
Ⅰ、同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒。反之，当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。
Ⅱ、 互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待, 当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。
例如，在仅有一台打印机的系统中，有两个进程A和进程B，如果进程A需要打印时, 系统已将打印机分配给进程B,则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞状态变为就绪状态。
Ⅲ、两个进程同时进入临界区，同步机制应遵循以下准则：
- 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
- 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
- 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。
- 让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。
二、实现临界互斥的基本方法
Ⅰ、软件实现方法
①单标志法
算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。turn的背后逻辑是表示谦让。
问题：算法的目的是让对方互相访问，假如对方不想占用临界资源，则会导致临界资源空闲。违背了“空闲让进”。
②双标志法先检查
算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为tue,之后开始访问临界区。flag背后逻辑是表示意愿。
问题：可能会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。
③双标志法后检查
算法思想：双标志先检查法的改版。前·个算法的问题是先“检查”后“上锁”，但是这两个操作又无法气阿成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。
问题：当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。违反“空闲让进”和“忙则等待”。
④皮特森算法
算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一·个有礼貌的进程。
bool flag[2]; //表意愿 int turn =0; //表谦让 P0进程： flag[0]=true; //表示意愿，自己想进入临界资源 turn =1; //表示谦让，让对方先进入临界资源 while (flag [1]&turn==1); //能循环的条件是1.对方想进入2.对方表示不想谦让，二者都要满足，才能循环 critical section; flag[0]=false; remainder section; P1进程： flag[1]=true; turn =0; while (flag [0]&turn==0); critical section; flag[1]=false; remainder section;
Ⅱ、硬件实现方法
①中断屏蔽法
优点：简单、高效
缺点：
将屏蔽中断权力交给用户进程可能会对整个系统造成意想不到的影响。
屏蔽中断只会对当前占用的CPU有效，其他CPU会继续运行，因此不适合多处理器系统。
②硬件指令法
old记录是否已被上锁；再将lock设为true;检查临界区是否已被上锁(若已上锁，则循环重复前几步)
优点：实现简单，适合多处理机。
缺点：不满足让权等待，从而导致饥饿现象。
第五节 信号量机制
信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”（通过）和“V操作（释放）”。原语是指完成某种功能且不被分割不被中断执行的操作序列，通常可由硬件来实现完成不被分割执行特性的功能。
一、整型信号量
用一个整型信号量表示一个资源数，但只要信号量为S ≤ 0，则会一直不断测试，违反了“让权等待”。
wait(S){ while(S<=0); S=S-1; } signal(S){ S=S+1; }
二、记录型信号量(绝对的重点)
记录型信号量是不存在“忙等”现象的进程同步机制。（设置了阻塞队列解决忙等）除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于釆用了记录型的数据结构得名。
typedef struct{ int value; struct process *L; } semaphore;
- wait操作，S.value--，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到该类资源的等待队列S.L中，可见该机制遵循了“让权等待”的准则。
void wait(semaphore S) //相当于申请资源 S.value --; if (S.value <0){ add this process to S.L; block(S.L); } }
- signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，故S.value++。若加1后仍是S.value<=0，则表示在S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup 原语，将S.L中的第一个等待进程唤醒。
void signal(semaphore S) //相当于释放资源 S.value ++; if (S.value <=0){ remove a process P from S.L; wakeup(P); } }
什么时候执行block和wakeup？
申请资源时，当value小于0时，就会执行block，让其进入阻塞队列中。当一个进程执行完，若value还是小于等于0，则会执行wakeup操作。
三、实现同步，互斥，前驱关系
Ⅰ、实现同步
在“前操作”之后执行V(S)
在“后操作”之前执行P(S)
Ⅱ、实现互斥
信号量机构也能很方便地解决进程互斥问题。设S为实现进程Pl、P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1)。只需把临界区置于P(S)和V(S)之间，即可实现两进程对临界资源的互斥访问。
实现互斥（mutex）的P操作一定要在实现同步（empty）的P操作之后。否则就会导致”死锁“现象。而V操作的顺序颠倒没有影响。
三、经典同步问题
Ⅰ、生产者-消费者问题（最常考）
- 互斥：在任一时间只能有一个线程操作缓冲区（缓冲区时临界资源）
- 当缓冲区为空，消费者必须等待生产者（调度/同步约束）
- 当缓冲区为满，生产者必须等待消费者（调度/同步约束）
Ⅱ、读者-写者问题
读者写者问题是并发程序设计中的经典问题。问题描述为：对于同一个文件，读操作可以同时并行，读写操作互斥，写与写互斥。
Ⅲ、哲学家进餐问题
Ⅳ、吸烟者问题
四、管程
概念：信号量机制存在的问题：编写程序困难、易出错。于是，产生了一种新的进程同步工具——管程。
组成：
共享数据结构
对数据结构初始化的语句
一组用来访问数据结构的过程（函数）
- 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据。
这个”入口“其实就是指对该数据结构进行操作的一组过程（或函数）
- 每次仅允许一个进程在管程内执行某个内部过程。
第六节 死锁
一、死锁产生的条件
①互斥条件：资源是互斥使用的
②不剥夺条件：进程只能由自己释放
③请求和保持：已获得资源同时，还在请求另外一个资源
④循环等待：存在一个循环等待链
二、死锁预防——破坏死锁产生条件
| 内容 | 缺点 | |
|---|---|---|
| 破坏互斥条件 | 将临界资源改造为可共享使用的资源（如SPOOLing技术） | 可行性不高，很多时候无法破坏互斥条件 |
| 破坏不剥夺条件 | 方案一，申请的资源得不到满足时，立即释放拥有的所有资源 方案二，申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级） | 缺点：实现复杂；剥夺资源可能导致部分工作失效； 反复申请和释放导致系统开销大；可能导致饥饿 |
| 破坏请求和保持条件 | 运行前分配好所有需要的资源，之后一直保持 | 资源利用率低；可能导致饥饿 |
| 破坏循环等待条件 | 给资源编号，必须按编号从小到大的顺序申请资源（申请资源的顺序） | 不方便增加新设备；会导致资源浪费；用户编程麻烦 |
三、死锁避免
《银行家算法》
主要思想是避免系统进入不安全状态，在每次进行资源分配时，它首先检查系统是否由足够的资源满足要求，若有则先进行试分配，并对分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。
四、死锁检测和解除：
检测：利用资源分配图（资源有向图）来检测。
①资源剥夺：从死锁进程处抢夺资源。
②撤销进程法：强制撤销部分或全部死锁，并剥夺这些进程的资源。
③进程回退法：让进程回退到足以避免死锁的时候。
第三章 内存管理
第一节 概念
- 按字节编制就是每个存储单元为1字节，8bit
- 按字编制就是每个存储单位为1字，字的大小计算机的不同都不一样，现代计算机基本都为64bit
从你在idea上编辑源代码文件时，点击“播放”按钮，即运行按钮，会发生以下几件事
- 编译：把你写的代码文件生成目标模块，也就是机器语言，能让计算机“看得懂”
- 连接：把你写的各种文件给连接起来，即由目标模块生成为装入模块，也就是为装入内存做准备
- 装入：这个很简单了，就是将装入模块装入内存，形成物理地址
连接方式
连接也分情况好吧
①静态连接：把所有文件在装入前，一股脑先全部连接起来，待到装入时，再一股脑全部丢进去。有人说了，我内存寸土寸金，你这一股脑丢进去，我有的目标模块用不到，你不给我浪费了吗！？是的。所以要改进。
②装入时动态连接：采用边装入边连接。就是在装入时连接。优点嘛就是便于修改和更新，便于实现对目标模块的共享。实则并未解决上面问题。
③运行时动态连接：需要运行目标模块才连接装入。凡是用不到，就不会调入内存和装入到模块上。优点是装入速度快，还可以节省大量的内存空间。
装入方式
连接分情况，转入也要分情况。多个目标模块的起始地址通常从0开始。这也就是所谓的逻辑地址。那装入分情况好吧，有点是直接一一对应，即逻辑地址对应物理地址那样装。不需要地址转换。即绝对装入。这个只适合早期的单道程序。
第二种就是可重定位装入（静态重定位）。给一个映射关系，但是这个映射关系不会改变，存储空间必须时连续的。假如装不下去，由于只能继续往下装，所以会导致内存不够。但是其他空间地址的内存有空间。灵活性较差。
第三种就是动态运行时装入（动态重定位）。映射关系可以改变，“内存哪里有空就往哪里钻”。可以将程序分配到不连续的存储区。现代操作系统多采用这种方式。
第二节 内存分配
一、连续分配
内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；
内部碎片是处于区域内部或页面内部的存储块。占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。
外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
外部碎片是出于任何已分配区域或页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。
Ⅰ、单一连续分配
这种分配方式下，内存被分成系统区和用户区。内存中只能有一道用户程序，用户程序独占整个用户空间。
优点：实现简单，没有外部碎片（因为每次就给一个程序分配空间，当他运行完成，把空间释放，又还是一个完整的没有被分配的空间）。不一定需要内存保护（因为只有一个程序，不存在有其他程序越界访问的情况）
缺点：只能用于单用户有内部碎片，存储空间的利用率很低（因为每次就一个程序在里面运行，会导致分配给他的空间有很多一部分他根本就用不上，因此会导致大量的内部碎片）
Ⅱ、固定分区分配
为了能让多个程序运行，并且让他们在运行的时候不会相互干扰，所以把用户空间分成多个固定大小的分区，每一个分区只存入一个作业。
优点：实现简单，没有外部碎片（总会有一个分区可以放得下，所以不存在有很多很小的没有被分配的外部碎片）
缺点：当用户程序太大的时候，会降低性能，并且会产生内部碎片（如果剩下一个较大的空间而分配给了一个小的进程，就会导致内部碎片）
Ⅲ、动态分区分配
会根据进程的大小来进行动态的分区分配，不预先划分内存分区，只是在进程装入内存的时候再建立分区。
动态分配策略会涉及一些分配算法：
| 算法 | 优点 | 优点 | 缺点 | |
|---|---|---|---|---|
| 首次适应 | 综合看性能最好，算法开销小（不能排列地址） | 综合性能最好。算法开销小，不需要对空闲分区进行排序 | \ | |
| 最佳适应 | 优先使用更小的分区 | 按照空闲分区容量递增的次序 | 会有更大的分区被保留下来，更能满足大进程的需求 | 会产生很对难以利用的碎片，算法开销大，因为要重新对空闲分区进行排序 |
| 最坏适应 | 优先使用更大的分区 | 按照空闲分区容量递减的次序 | 可以减少难以利用的碎片 | 大分区很容易被用完，不利于大进程，而且算法开销大 |
| 邻近适应 | 首次适应后，每次查找从上次位置继续查找 | 空闲分区以地址递增次序排列 | 不用每次都从低地址开始检索，算法开销小 | 会使高地址的大分区也被用完 |
二、非连续分配
Ⅰ、基本分页存储管理（超重点）
引入思想：固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想——把内存分为一个个相等的小分区,再按照分区大小把进程拆分成一个个小部分。各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。
那它是怎么减少碎片的呢？举个简单的栗子就是：你拿了一桶水，给缺水地区的人们分水，为了公平，你要保证人们的杯子水是满的。但是最后总会碰到桶子里的水不够一杯。这就是基本分页的特点。内部碎片只会在为最后一个不完整的块申请一个主存空间时产生。这相对固定分区和动态分区已经好很多了。
那么程序的地址关系时如何映射到主存上呢？或者是说，当我知道一个程序的地址（逻辑地址），要如何才能找到内存地址（物理地址）。就要映入页表。
①页表
页表包括页号（由于顺序排放，所以是隐含的，实际不占据内存空间）和块号。
②地址转化
计算页号和偏移量：
页号=逻辑地址/页面长度（取除法的整数部分）
页内偏移量=逻辑地址%页面长度（取除法的余数部分)
③快表，又称相联存储器（TLB）
因为页表存放在内存种，每次访问内存导致访问变慢，所以在高速缓冲存储器中产生了快表。
目的就是加快执行速度。
④两级页表
背景：考虑这样一种情况，对于一个32位逻辑地址空间的分页系统，规定每一页的大小为4KB，每个表项占用4B，则这个页表需要占用4MB的内存空间，而且这段空间必须连续。显然这样的要求对于寸土寸金的内存空间来说太奢侈了，那么有没有什么好方法来解决这个问题呢？
二级页表就是将外部的页表进行拆分。离散将所需的页表存入内存，好处就是不用浪费主存空间去存储无用的页表项，也不用盲目地顺序查找页表。
Ⅱ、基本分段存储管理（超重点）
背景：分页是从计算机的角度考虑问题，目的是提高内存的利用率。分页通过硬件机制实现，对用户完全透明。而分段则方便编程，信息保护和共享，动态增长及动态链接等。
基本思想：按照用户进程自身的逻辑关系划分为若干段。每个段有一个段名，每段从0开始编址。内存分配时，以段为单位进行分配，段内连续，段间可以不连续
①段表
段号（隐含）+段号+本段在主存的起始地址
②分页与分段的区别
页是信息的物理单位。分页的主要日的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。
段的长度却不固定，取决于用户编写的程序。
分页的用户进程地址空问是一维的
分段的用户进程地址空问是二维的
Ⅲ、段页式管理
※每个进程都会有一个页表或者段表。段页式也不例外，每个进程都有一个段表，但段表里面分为了很多的页表。
第三节 虚拟内存管理
背景：由于传统存储管理方式的缺陷（连续分配和非连续分配）——一次性，作业必须一次性全部装入内存后才能开始运行和驻留性，就算用不到，也一直存在内存中，浪费了宝贵资源。
思想：基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空问不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。
实现方式：请求分页存储管理；请求分段存储管理；请求段页式存储管理。
其最大的容量是由计算机的地址结构决定的，比如说计算机是32位的操作系统，那么它的最大容量为 232 。
一、请求分页管理方式
请求分页存储管理方式和基本分页存储管理的主要区别是会调入调出（置换）
Ⅰ、页表机制
添加了：
- 状态位：是否已调入内存
- 访问字段：记录最近被访问的时间
- 修改位：页面调入内存后是否被修改
- 外存地址：页面在外存中存放的位置
在请求分页系统中，若要访问的页面不在内存中时，便会产生一个缺页中断，然后分两种情况，一是内存里面还有空间，则直接位几次呢分配一个空的空闲块。二是若内存没空间了，则要由页面置换算法选择一个页面淘汰，若淘汰页面被修改过，则要写回其外存。未修改过的不用写回外存，直接丢弃就好了。
Ⅱ、页面置换算法
既然前面提到了，在无内存空间时，要采用页面置换算法换出一个页面，那涉及了哪些页面置换算法呢？
| 内容 | 优缺点 | |
|---|---|---|
| 最佳置换算法（OPT） | 优先淘汰最长时间不会被访问的 | 缺页率最好，性能最好，但无法实现 |
| 先进先出置换算法（FIFO） | 优先淘汰最先进入内存的页面 | 实现简单，但性能很差，可能会出现Belady异常* |
| 最近最久未使用置换算法（LRU） | 优先淘汰最近最久没有被访问的页面 | 性能很好，但需要硬件支持，算法开销大，对所有页进行排序 |
| 时钟置换算法（CLOCK） | 循环扫描各页面，第一轮淘汰访问位=0，并将扫描过的页面访问位改位0。若第一轮没选中，则进行第二轮扫描 | 实现简单，算法开销小；但未考虑页面是否被修改，修改后置换还要换出外存，这是主要的开销 |
| 改进型的时钟置换算法 | 第一轮:从当前位置开始扫描到第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位 第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为0 第三轮:若第二轮扫描失败，则重新扫描，查找第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位 第四轮:若第三轮扫描失败，则重新扫描，查找第一个(0,1）的帧用于替换 | 算法开销较小，性能也不错 |
*：Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
二、页面分配策略
清楚一些名词
①驻留集：只请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集的大小一般小于进程的总大小。
太小，会导致缺页频繁，系统要花大量时间去处理缺页
太大，则会导致多道程序并发度下降（并发度下降CPU休息就多了）
②固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行过程中，物理块大小不变。
③可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。
④局部置换：发生缺页时准选进程自己的物理块进行置换。
⑤全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
⑥抖动现象：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动。主要原因就是分配的物理块太少。但给的多了，会降低并发度，所以给多少就要研究了。（这里涉及工作集，自行百度了解一下即可）
固定分配VS可变分配：区别在于进程运行期间驻留集大小是否可变。
局部置换VS全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出。
①固定分配局部置换：物理块在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)
②可变分配全局置换：刚开始会为每个进程分配一定数量的物理块，操作系统会保持一个空闲物理块队列。岂某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。(只要缺页就加新的物理块，壕！！但会影响其他进程)
③可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度：反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。（根据发生的缺页率来动态增加或减少进程的物理块，像屌丝，有多少用多少！)
内存映射文件
内存映射文件和标准IO操作最大的不同之处就在于它虽然最终也是要从磁盘读取数据，但是它并不需要将数据读取到OS内核缓冲区，而是直接将进程的用户私有地址空间中的一 部分区域与文件对象建立起映射关系，就好像直接从内存中读、写文件一样，速度当然快了。
“映射”就是建立一种对应关系,在这里主要是指硬盘上文件的位置与进程逻辑地址空间中一块相同区域之间一一对应,这种关系纯属是逻辑上的概念，物理上是不存在的。
题目总结：
①（多级页表）已知系统为32位实地址，采用48位虚拟地址，页面大小为4KB,页表项大小为8B。假设系统使用纯页式存储，则要采用4级页表，页内偏移12位。
解释：页面大小为4KB，所以页内偏移12位，而页面为4KB，页表项的大小为8B，最多能有 29 个页表项。
②
解释：这是个很新的考题，其中页的大小为4KB，说明页内的偏移量占12位，所以02A01H中的A01属于页内偏移量，02属于页号。
但是观察标志位为0，说明不在主存，就要调入主存，但是页框只有两个，已经被3，4占着了，那这时候就要置换页面，观察访问位，都被访问过，然后看修改位，优先调出未被修改的，所以会调出3号页面。页框号为60H。
第四章 文件管理
第一节 文件的分类
一、无结构文件（流式文件）
文件内部的数据就是一系列二进制流和字符流组成。又称“流式文件”。如windows中的txt文件。
二、有结构文件（记录式文件）
Ⅰ、顺序文件
1.串结构：记录顺序与关键字无关 2.顺序结构：记录按关键字顺序排列 3.可变长记录的顺序文件无法实现随机存取，定长记录可以 4.最大缺点：不方便增加和删除记录
顺序文件分为顺序存储和链式存储，哪些是可以随机存取？
链式存储是不能实现随机存取的。顺序存储，如果是可变长记录，无法实现随机存取。
如果是定长记录，可实现随机存取，若采用串结构，无法快速找到某关键字对应的记录。
若采用顺序结果，可以快速找到某关键字对应的记录。
Ⅱ、索引文件
正是由于顺序文件的查找，修改，增加的困难，所以引出了索引文件。
1.建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录。
2.索引表的结构：索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
3.若索引表按关键字顺序排列，则可支持快速检索
4.最大缺点：解决了顺序文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取，但索引表可能占用很多空间
Ⅲ、索引顺序文件
正是由于索引表有时候比文件还大，浪费了存储空间，所以引出了索引顺序文件。
1.同样建立一张索引表。但不同与索引文件的是，不是为每个记录都设置表项，而是将记录按照某个规则进行分组，对组进行设置表项。
2.检索记录时先顺序查索引表，找到分组，再顺序查找分组。
3.当记录过多时，可建立多级索引表。
4.缺点：索引文件和索引顺序文件都提高了存取的速度，但因为配置索引表而增加了存储空间。
题目：有一个顺序文件含有10000个记录，平均查找的记录数为5000个，采用索引顺序文件结构，则最好情况下平均只需查找()次记录。
解析：索引顺序文件，最好带情况是 � 组，每组有 � 个记录。所以第一次查找索引表是平均次数为50次，第二次查找顺序表平均50为次。故总共次数为100次。
第二节 文件目录
※一个文件对应一个FCB，一个FCB就是一个目录项，多个目录项构成目录文件。
FCB介绍：为了方便对文件的管理，会对每个文件都设立一个FCB（文件控制块）。文件控制块内容一般包含有文件名、文件类型、文件的物理地址、文件的起始块号、文件的存储权限、文件创建时间等等。
众多文件的FCB
一、目录结构
Ⅰ、单级目录：一个系统只有一张目录表，不允许文件重名。
Ⅱ、两级目录：不同用户的文件可以重名，但不能对文件进行分类。
Ⅲ、多级（树型）目录：不同目录下文件可以重名，可以对文件进行分类，从根目录出发是“绝对路径”，从当前目录出发的路径是“相对路径”。
Ⅳ、无环图目录路径：在树型目录的基础上，增加一些指向同一节点的有向边，便于共享，一个实际存在外存的文件，可以被多个文件目录指向。删除时，为共享文件设置一个计数器（用来表明有多少个文件被共享），计数器为0时才真正删除该结点。
二、索引结点
只包含文件名和指针（无类型、存取权限等等对查找没用的信息），因此每个目录项的长度大幅减小，大大提升了文件检索速度——由于目录项长度的减小，因此每个磁盘块可以存放更多个目录项。
第三节 文件的物理结构（十分重要）
一、连续分配
思想：要求每个文件在磁盘上占有一组连续的块。
如何进行地址转化？
文件目录中给出文件的起始块号和长度，当给出一个文件的逻辑块号i时，会找到该文件对应的目录项（FCB）。然后，就能找到起始地址，加i就可以得到物理地址
物理块号=起始块号+逻辑块号
可以随机访问
优点：支持顺序访问和直接访问，连续分配文件在读/写时速度最快
缺点：①连续分配当文件扩展时，十分不方便。
②连续分配会导致存储空间利用率低，会产生难以利用的空间碎片。
二、链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
Ⅰ、隐式链接
目录项记录了起始块号和结束块号。
思想：处理文件最后一个磁盘块外，每个磁盘块都会保存下一个盘块的指针，这个指针对于用户来说时透明的。
如何进行地址转化？
给出逻辑块号i，在目录项中可以找到起始块号，就可以依次知道后面的逻辑块号。所以读入i号逻辑块，总共需要i+1次磁盘I/O。
优点：方便文件拓展，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要消耗少量的存储空间。
Ⅱ、显式链接
思想：针对隐式链接的缺点，不支持随机访问，会设置一张FAT表，开机时，将FAT表读入内存，并常驻内存。FAT的各个表项长度相同，因此，物理块号字段可以是隐含的。
如何进行地址转化？
给出逻辑块号i，再在文件中找到FAT表，就可以知道文件的物理地址。
优点：很方便文件拓展，不会有碎片问题，外存利用率高。并支持随机访问。相对于隐式来说，地址转换不需要访问磁盘，因此文件的访问效率更高。只需要访问在内存中的FAT。
缺点：文件分配表的需要占用一定的存储空间。
三、索引分配
思想：设置一个索引表，索引表记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
于FAT表的区别：
在显示连接中的FAT表是一个磁盘对应一张，而索引分配方式中，索引表是一个文件对应一张。
优点：索引分配方式可以支持随机访问。文件拓展也很容易。
缺点：索引表占据一定的空间。
这时又引出新的问题，当文件过大，大到一个索引表无法表示全部的文件，这时候就需要用多个索引表。
索引结点：指向索引块的单个间接指针。 如果文件不能被直接块完全索引，则使用单个间接指针。 指向磁盘块的双重间接指针，该磁盘块是指向作为索引块的磁盘块的指针的集合。 如果文件太大而无法通过直接块以及单个间接指针完全索引，则使用双索引指针。 指向一个指针集合的磁盘块的三元索引指针。 每个指针分别指向一个磁盘块，该块还包含一组指针，这些指针分别指向一个包含指向文件块的指针的索引块。
高频考点：
①算出文件的最大长度：假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。若文件采用两层索引，则最大的文件长度可以达到256×256×1KB=64MB。
②索引分配如何进行地址转换？
要访问1026号逻辑块，则1026/256=4，1026%256=2，因此可以先将一级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。
题目：
1.在文件的索引节点中存放直接索引指针10个，一级和二级索引指针各1个。磁盘块大小为1KB,每个索引指针占4个字节。若某文件的索引节点已在内存中，则把该文件偏移量（按字节编址)为1234和307400处所在的磁盘块读入内存，需问的磁盘块个数分别是？
解析：“索引结点已存在内存中”说明不需要把索引结点从外存调入到内存，减少依次访问磁盘个数。八个直接索引所占的字节为8×1024B=8192B,这部分都是在直接索引里面就可以找到。只需要一次。但是一级索引为256×1024=262144，故要通过二级索引才可以找到，所以访问磁盘的次数为3次。
第四节 文件存储空间管理
一、管理方法
Ⅰ、空闲表法
会设置个一个空闲表，上面记录了空闲块第一个空闲块号和空闲块数，所以当有文件要申请空闲空间时就可以为其分配。分配方式有首次适应、最佳适应、最坏适应等决定要为文件分配哪个区间。
Ⅱ、空闲链表法
分为空闲盘块链和空闲盘区链
①空闲盘块链——以盘块为单位组成一条空闲链。适用离散分配的物理块。分配多个盘块需要进行多次操作。
②空闲盘区链——以盘区为单位组成一条空闲链。盘区是多个盘块组成。离散分配、连续分配都适用。唯一个文件分配多个盘块时效率更高。
Ⅲ、位示图法
位示图是利⽤⼆进制的⼀位来表示磁盘中⼀个盘块的使⽤情况，磁盘上所有的盘块都有⼀个⼆进制位与之对应。当值为 0 时，表示对应的盘块空闲，值为 1 时，表示对应的盘块已分配。
常考的一个点是：会盘块号于字号，位号的关系。
注意字号、位号、盘块号是否从0开始。
如果给出的盘块号、字号、位号都从1开始
如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件：③将相应位设置为“1”。
如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”。
Ⅳ、成组链接法（了解）
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。
※文件再打开时不会直接把文件数据读入内存。再读/写文件是才会把文件数据从外存调入到内存中。
第五节 文件保护
| 内容 | 优缺点 | |
|---|---|---|
| 口令保护 | 为文件设置一个口令，用户想要访问就必须提供口令 | 实现开销小，但是口令放在FCB不安全 |
| 加密保护 | 用一个密码对内容进行加密，访问时必须提供密码 | 安全性高，但加密/解密需要耗费一定的时间 |
| 访问控制 | 用一个ACL（访问控制表）记录各个客户对文件的访问权限 | 实现灵活，可以实现复杂文件的保护功能 |
第六节 磁盘
一、磁盘结构
柱面：硬盘通常由重叠的一组盘片构成，每个盘面都被划分为数目相等的磁道，并从外缘的"0"开始编号，从图2这张放大的硬盘结构图我们可以看出，具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面。磁盘的柱面数与一个盘面上的磁道数是相等的。
磁道：当磁盘旋转时，磁头若保持在一个位置上，则每个磁头都会在磁盘表面划出一个圆形轨迹，这些圆形轨迹就叫做磁道。
磁盘的物理地址：（柱面号，盘面号，扇区号）就可以唯一确定磁盘块的位置。
疑问：为什么柱面号要在盘面号的前面，原因就是为了减少移动磁头的次数。
二、磁盘调度算法
一次磁盘读/写操作需要的时间=寻道时间+延迟时间+传输时间。
由于延迟时间和传输时间都是与磁盘转速有关的，且是线性相关。而转速又是磁盘的固有属性，因此无法通过操作系统优化延迟时间和传输时间。所以只能优化寻找时间。
寻找时间可以根据不同的调入算法而不同：
①先来先服务算法（FCFS）
算法思想：根据进程请求访问磁盘的先后顺序进行调度。
优点：公平；如果请求访问的磁道比较集中的话，算法性能还算可以。
缺点：如果大量进程竞争使用磁盘，请求访问的磁道很分散，FCFS在性能上很差，寻道时间长。
例如，磁盘请求队列中的请求顺序分别为55,58,39,18,90,160,150,38,184，磁头的初始位置是磁道100，采用FCFS算法时磁头的运动过程如图5.16所示。磁头共移动了(45+3+19+21+72+70+10+112+146)=498个磁道，平均寻找长度=498/9=55.3。
②最短寻找时间优先（SSTF）
算法思想：优先处理的磁道是与当前磁头最近的磁道。可以保证每次寻道时间最短，但是不能保证总的寻道时间最短。（其实是贪心算法的思想，只是选择眼前最优，但是总体未必最优）
优点：寻道时间很短。
缺点：可能产生饥饿现象。
③扫描算法/电梯算法（SCAN）
算法思想：磁头扫描到最边上才能往回移动。
优点：性能较好，平均寻道时间较短，不会产生饥饿现象。
缺点：有时候请求到不了磁盘两边，但是磁头要扫描到两边。对各磁道的响应不平均。
④LOOK调度算法（边移动边观察）
算法思想：如果移动方向上已经没有别的请求，就可以立即改变磁头的移动方向。
优点：比起SCAN算法来说，不需要每次都移动到最外侧或最内侧才改变磁头方向，使得寻道时间进一步缩短。
⑤循环扫描算法（C-SCAN）
算法思想：返回时直接快速移动至起始端而不做任何请求。
优点：比起SCAN来说，对于各个位置磁道的响应频率很平均。
缺点：不需要每次都返回到磁道的起始端。
⑥C-LOOK调度算法
算法思想：解决C-SCAN问题，如果磁头移动方向上没有访问请求，则立即返回，并且磁头只需返回到有磁道访问请求的位置即可。
优点：进一步改进C-SCAN算法，使得寻道时间进一步缩短。
新增考点：
一、（固态硬盘）SSD
原理：基于闪存技术（与U盘一样），属于电可擦除ROM。
组成：闪存翻译层和闪存芯片
SSD擦除太多可能会坏掉，但是机械硬盘则不会坏。所以就产生了磨损均衡技术，把擦除平均分布再各个块上，以提升使用寿命。分为动态磨损均衡和静态磨损均衡。动态磨损均衡是为了写入数据时，优先选择累计擦除次数少的新闪存块儿，静态磨损技术则是让老旧的闪存块更多承担读，而新的闪存块更多承担写。
静态磨损均衡算法比动态磨损均衡算法表现更加优秀。
二、硬链接和软链接
Ⅰ、硬链接
硬链接指文件名与索引节点号（即inode号）的链接（所以创建一个新的文件,该文件使用stat命令查看时，links显示的是1），索引节点号（inode号）可以对应一个或多个文件名，并且这些文件名可以在同一或不同目录。
由于硬链接是直接将文件名与索引节点号（即inode号）链接，因此硬链接存在以下几个特点： 1、文件有相同的inode号及data block，这使得修改其中一个硬链接文件属性或文件数据时，其他硬链接文件都会发生相应修改；（bad）2、只能对已存在的文件进行创建；3、不能跨文件系统（即分区）进行创建；4、不能对目录文件进行创建；5、删除其中一个硬链接文件时，不会对其他硬链接文件产生影响。
Ⅱ、软链接
软链接类似于Windows的快捷方式。它实际上是一个特殊的文件，有着自己的索引节点号（即inode号）以及用户数据块（data block），但用户数据块（data block）中包含的是另一个文件的位置信息。
由于软链接有着自己的索引节点号（即inode号）以及用户数据块（data block），因此没有硬链接的诸多限制，它的特性如下：1、软链接有自己独有的文件属性、inode号和data block，但是编辑文件其实就是编辑源文件；2、可以对不存在的文件或目录进行创建；3、可以跨文件系统（即分区）进行创建，使用ln命令跨文件系统创建时，源文件必须是绝对路径，否则为死链接；4、可以对文件或目录文件进行创建；5、删除软链接并不影响源文件，但源文件被删除，则相关软链接文件变为死链接（dangling link），若源文件（原地址原文件名）重新被创建，则死链接恢复为正常软链接。
Ⅲ、区别
第一个特性，硬链接与源文件具有相同inode号和data block，修改文件属性或文件数据会应影响所有硬链接（包括源文件）；软链接虽然有自己的inode号和data block，但修改的其实还是源文件
第二个特性，硬链接不能对不存在的文件进行创建，但软链接可以（包括目录文件）
第三个特性，硬链接不可以跨文件系统（即分区）创建，软链接可以
第四个特性，硬链接不能对目录创建链接，但软链接可以
第五个特性，删除源文件，硬链接没有影响；软链接变成死链接，但在相同位置重新创建同名文件，软链接变成指向新文件的链接
三、虚拟文件系统
虚拟文件系统（VFS）是物理文件系统与服务之间的一个接口层，它对Linux的每个文件系统的所有细节进行抽象，使得不同的文件系统在Linux核心以及系统中运行的其他进程看来，都是相同的。严格说来，VFS并不是一种实际的文件系统。它只存在于内存中，不存在于任何外存空间。VFS在系统启动时建立，在系统关闭时消亡。
四、文件系统挂载
将额外的文件系统与根文件系统某个现存的目录建立关联关系，进而使得该目录作为其他文件访问入口的行为称之为挂载。
第五章 输入输出管理
第一节 I/O管理概述
一、I/O控制器（I/O接口）
Ⅰ为什么要单独设置一个控制器，为什么不直接用CPU控制？
①最肤浅的，为了能够让CPU能够和I/O设备进行通信
②协调I/O设备与总线之间的速度！
Ⅱ、I/O控制器主要功能和组成？
二、I/O控制方式（重点）
| 过程 | CPU干预频率 | 传输单位 | 数据流向 | |
|---|---|---|---|---|
| 程序直接控制方式 | CPU不断轮询查看设备状态 | 极高 | 字 | 设备-CPU-内存 内存-CPU-设备 |
| 中断驱动方式 | CPU指令执行完，查看有没有中断请求 | 高 | 字 | 设备-CPU-内存 内存-CPU-设备 |
| DMA | CPU发出请求后就可以做其他事，剩下事由DMA控制器完成，完成后向CPU发送完成信号 | 中 | 块 | 设备-内存 内存-设备 |
| 通道控制方式 | CPU发出请求后就可以做其他事，完成后向CPU发送完成信号 | 低 | 一组块 | 设备-内存 内存-设备 |
通道控制方式
进化过程：每一个阶段的优点都是解决了上一阶段的最大缺点。总体来说，整个发展过程就是要尽量减少CPU对/O过程的千预，把CPU从繁杂的/O控制事务中解脱出来，以便更多地去完成数据处理任务。
第二节 设备独立性软件
一、高速缓存和缓冲区
Ⅰ、目的：缓解CPU与设备的速度矛盾、减少对CPU的中断频率、解决数据粒度不匹配的问题、提高CPU与/IO设备之间的并行性。
Ⅱ、实现方法
①单缓冲
假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）
注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
处理一块数据平均使用的时间（常考）
①T>C（输入时间大于处理时间）
②T<C（输入时间小于处理时间）
结论：采用单缓冲策略，处理一块数据平均耗时Max(C,T)+M
②双缓冲
操作系统为其分配两个缓冲区
处理一块数据平均使用时间
双缓冲题目巾，假设初始状态为：工作区空，其中·个缓冲区满，另·个缓冲区空。
结论：采用双缓冲策略，处理一个数据块的平均耗时为Max(T,C+M)
③循环缓冲
④缓冲池
缓冲池由系统中共用的缓冲区组成。这些缓冲区按使用状沉可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）
另外，根据一·个缓冲区在实际运算巾扮演的功能不同，又设置了四种工作缓冲区：用于收容输入数据的工作缓冲区(hin)、用于提取输入数据的工作缓冲区(si)、用于收容输出数据的工作缓冲区(hout)、用于提取输出数据的工作缓冲区(sout)
三、高速缓冲和缓冲区的对比
四、SPOOLing技术（假脱机技术）
磁盘是一种高速设备，在与内存交换数据的速度上优于打印机、键盘、鼠标等中低速设备。试想一下，若没有SPOOLing技术，CPU要向打印机输出要打印的数据，打印机的打印速度比较慢，CPU就必须迁就打印机，在打印机把数据打印完后才能继续做其他的工作，浪费了CPU的不少时间。在SPOOLing技术下，CPU要打印机打印的数据可以先输出到磁盘的输出井中（这个过程由假脱机进程控制)，然后做其他的事情。若打印机此时被占用，则SPOOLing系统就会把这个打印请求挂到等待队列上，待打印机有空时再把数据打印出来。向磁盘输出数据的速度比向打印机输出数据的速度快，因此就节省了时间。提高了独占设备的利用率。
五、静态分配和动态分配
对独占型设备一般采用静态分配,即在作业级进行的分配,当一个作业运行之前由系统一次分配满足需要的全部设备,这些设备一直为该作业占用,直到作业撤消。这种分配不会出现死锁,但设备的利用效率较低。而共享设备一般采用的事动态分配。
