操作系统复习整理

思维导图
链接：https://pan.baidu.com/s/1h-FIl–j0zuPvMan-9iVBA?pwd=8765
提取码：8765

什么是操作系统

操作系统（Operating System， OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件。

• 操作系统是系统资源的管理者（设备管理、文件管理、存储器管理、处理机管理）
• 操作系统向上层提供方便易用的服务（封装思想：操作系统把一些硬件功能封装成简单易用的服务，使用户能更方便的使用计算机，用户无需关心底层硬件的原理，只需要对操作系统发出命令即可—例如GUI、命令接口（联机命令接口、脱机命令接口）、程序接口即系统调用）
• 操作系统是最接近硬件的一层软件（对硬件机器的扩展）

操作系统的特征

并发、 共享、虚拟、异步

• 并发：指两个或多个事件在同一时间间隔内发生。这些事件在宏观上同时发生，但在微观上是交替发生的。
  注意
  容易混淆----并行：指两个或多个事件在同一时刻发生。
  单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行
  多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行

• 共享：指操作系统中资源可供内存中多个并发执行的进程共同使用。
  互斥共享：同一时间段内只允许一个进程访问该资源（摄像头）
  同时共享:一段时间内由多个进程“同时”对其进行访问（文件发送时对硬盘资源的访问–宏观同时、微观交替）

• 虚拟：把物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在的，而逻辑上对应物是用户感受到的。
  时分复用技术（虚拟处理器）
  空分复用技术（虚拟存储器技术）

• 异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的。而是走走停停，以不可预知的速度向前推进。

操作系统的发展

操作系统的运行机制

中断与异常

中断的作用：让操作系统内核强行夺回CPU的控制权、使CPU从用户态变为内核态
中断的分类：
       内中断(也称异常)：与当前执行的指令有关，中断信号的来自CPU内部
              陷入：由陷入指令引发，是应用程序故意引发的。如：缺页故障
              故障：由错误条件引起的，可能被内核程序修复。
              终止：由致命错误引起，内核程序无法修复该错误。如：整数除0、非法使用特权指令
       外中断(也称中断)：与当前执行的指令无关，中断信号的来自CPU外部
              时钟中断
              I/O中断请求

系统调用

什么是系统调用：“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务
什么功能需要系统调用实现：凡是与共享资源有关的操作，会直接影响其他进程的操作，就一定需要操作系统介入，就需要通过系统调用来实现。例如：设备管理、文件管理、进程管理、进程通信、内存管理

进程的概念、组成与特征

进程和程序

• 程序：是静态的，就是个存放在磁盘里面的可执行文件，是一系列的指令集合
• 进程：是动态的，是程序的一次执行过程（同一程序的多次执行对应多个进程）

进程的组成

• PCB(进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息)
• 程序段（程序的代码–指令序列）
• 数据段（运行过程中产生的各种数据）

进程的特征

• 动态性**（最基本特性）**：进程是程序的一次执行，是动态地产出、变化和消亡的
• 并发性：内存中有多个进程实体，各进程可以并发执行
• 独立性：进程是能独立运、独立获得资源、独立接受调度的基本单位
• 异步性：各个进程按各自独立的、不可预知的速度向前推进、操作系统要提供“进程同步机制”来解决异步问题
• 结构性：每个进程都会配置一个PCB,结构上看，进程有程序段、数据段和PCB组成

进程的状态与转换

• 创建态：进程真正在被创建，操作系统为进程分配资源，初始化PCB
• 就绪态：已经具备运行条件，但是由于没有空闲CPU，而暂时不能运行
• 运行态：占有CPU，并在CPU上运行
• 阻塞态：因等待某一事件而暂时不能运行
• 终止态：进程正在从系统中撤销，系统会回收进程拥有的资源，撤销PCB
  

进程调度

进程调度方式

• 非剥夺调度方式（非抢占式）：只允许进程主动放弃处理机，在运行过程中即便有更紧迫的任务到达，当前进程依旧会继续使用处理机，直到该进程终止或主动要求进入阻塞态（实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统）
• 剥夺调度方式（抢占式）：当一个进程正在处理机上执行时，如果有一个更重要的或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程（可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统）

调度算法

调度算法的评价指标

• CPU利用率：CPU“忙碌”的时间占总时间的比例
  Eg：某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少？
  $$利用率=\frac{忙碌的时间}{总时间}$$
  $$CPU利用率=\frac{5+5}{5+5+5}=66.66\%$$
  $$打印机利用率=\frac{5}{5+5+5}=33.33\%$$
• 系统吞吐量：单位书剑内完成作业的数量
  $$系统吞吐量=\frac{总共完成了多少道作业}{总时间}$$
  Eg：某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？
  $$系统吞吐量=\frac{10}{100}=0.1道/秒$$
• 周转时间：从作业被提交给系统开始，到作业完成位置的这段时间间隔。
  $$周转时间=作业完成时间-作业提交时间$$
  $$平均周转时间=\frac{各作业周转时间之和}{作业数}$$
  $$带权周转时间=\frac{作业周转时间}{作业实际运行时间}=\frac{作业完成时间-作业提交时间}{作业实际运行时间}$$
  $$平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$$
• 等待时间：进程/作业等待被服务的时间之和
• 响应时间：从用户提交到首次产生响应所用的时间

各类调度算法

• 先来先服务（FCFS）
  算法思想：主要从“公平”的角度考虑
  算法规则：按照作业/进程到达的先后顺序进行服务
  是否可抢占：非抢占式算法
  优点：公平、算法实现简单
  缺点：排在长作业（进程）后面的短作业需要等待很长的时间，带权周转时间很大，对短作业来说用户体验不好，即对长作业有利，对短作业不利
  是否会导致饥饿：不会

• 短作业优先(SJF)
  算法思想：追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
  算法规则：最短的作业/进程优先得到服务
  是否可抢占：SJF和SPF是非抢占式的算法，但是也有可抢占的版本----最短剩余时间优先算法（SRTN）
  优点：“最短的”平均等待事件、平均周转时间
  缺点：不公平，对短作业有利，对长作业不利，可能产生饥饿现象，另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
  是否会导致饥饿现象：会

• 高响应比优先（HRRN）
  算法思想：要综合考虑作业/进程的等待事件和要求服务时间
  算法规则：每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
  是否可抢占：非抢占式算法。
  优点：综合考虑了等待时间与运行时间，等待时间相同时，要求服务时间短的优先，要求服务时间相同时，等待时间长的优先，对于长作业来说，随着等待时间越来越久，其响应比会越来越大，从而避免了长作业饥饿问题
  是否会导致饥饿：不会

• 时间片轮转（RR）
  算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都能得到相应
  算法规则：按照各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列对位重新排序
  是否可抢占：是，若进程未能在时间片内运行完，将被强行剥夺处理机使用权。
  优点：公平，响应快，适用于分时操作系统
  缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧迫程度
  是否会导致饥饿：不会

• 优先级调度算法
  算法思想：根据任务的紧急程度来决定处理顺序
  算法规则：调度时选择优先级最高的作业/进程
  是否可抢占：抢占式和非抢占式都有。非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
  优点：用优先级区分紧急程度，重要程度，适用于实时操作系统，可灵活地调整各作业/进程的偏好程度
  缺点：若源源不断地有高优先级进程到来，可能导致饥饿
  是否会导致饥饿：会

• 多级反馈队列
  算法思想：对其他电镀算法的折中权衡
  算法规则：
  1）设置多级反馈队列，各级队列优先级从高到低，时间片从小到大
  2）新进程到达时先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经是在最下级的队列，则重新放回该队列队尾
  3）只有第K级队列为空时，才会为k+1级队头的进程分配时间片
  是否可抢占：抢占式算法。在 k 级队列的进程运行过程中，若更上级的队列 （1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的 队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列 队尾。
  优缺点：对各类型进程相对公平（FCFS的优点）；每个新到达的进程都可以 很快就得到响应（RR的优点）；短进程只用较少的时间就可完成 （SPF的优点）；不必实现估计进程的运行时间（避免用户作假）； 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密 集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样
  I/O型进程就可以保持较高优先级）
  是否会导致饥饿：会

死锁

• 概念

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象（因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁，且在阻塞态）
饥饿：由于长时间得不到想要的资源，某进程无法向前推进的现象。
死循环：某一进程执行过程中一直跳不出某个循环现象。

• 死锁产生的必要条件
  互斥条件：只有对必须互斥使用的资源的抢夺才会导致死锁
  不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
  请求和保持条件：进程已经保持了至少一个资源，但是又提出了新的资源请求，而改资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
  循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

• 死锁的处理策略----预防死锁
  1）破坏互斥条件：将临界资源改造为可共享使用的资源
  2）破坏不剥夺条件：申请的资源得不到满足时，立即释放所拥有的所有资源；申请的资源被其他进程占用时，由操作系统协助剥夺
  3）破坏请求和保持条件：运行前分配好所有需要的资源，之后一直保持
  4）破坏循环等待条件:给资源编号，必须按编号从小到大的顺序申请资源

• 死锁的处理策略----避免死锁
  银行家算法

• 死锁的处理策略----死锁的检测与解除
  检测：1）数据结构----资源分配图 2）死锁检测算法：依次消除与不阻塞进程相连的边，直到无边可消
  解除：1）资源剥夺法 2）撤销进程法 3）进程回退法

内存连续分配管理

• 单一连续分配
  只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
  无外部碎片，有内部碎片
• 固定分区分配
  支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业
  无外部碎片，有内部碎片
• 动态分区分配
  支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区
  无内部碎片，有外部碎片（外部碎片可用“紧凑”技术解决）

注意：
内部碎片：分配给某进程的内存区域中，如果有些部分没用上
外部碎片：是指内存中的某些空闲分区太小而难以利用

动态分区分配算法

• 首次适应算法
  算法思想：每次都从弟弟仔开始查找，找到第一个能满足大小的空闲分区
  如何实现：空闲分区以地址递增次序排列，每次分配内存时顺序查找空闲分区链（或空闲分区表）,找到大小能满足要求的第一个空闲分区

• 最佳适应算法
  算法思想：由于动态分区分配时一种连续分配方式，为各进程分配的空间必须是连续的一整片区域，因此，为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区
  如何实现：空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
  缺点：每次都是选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块，因此这种方法会产生很多外部碎片

• 最坏适应算法（最大适应算法）
  算法思想：为了解决最佳适应算法的问题----即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用
  如何实现：空闲分区按容量递减的次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表）找到大小能满足要求的第一个空闲分区
  缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完，如果之后有"大进程"到达，就没有内存分区可用了

• 邻近适应算法
  算法思想：首次适应算法每次都从链头开始查找，这可能会导致低地址部分出现很多很小的空闲分区，而每次分配查找是，都要经过这些分区，因此也增加了查找的开销，如果每次都从上次查找结束的位置开始检索，就能解决上述问题
  如何实现：空闲分区按地址递增的顺序排列（可排成一个循环链表），每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到能满足要求的第一个空闲分区

页面置换算法

• 最佳置换算法
  每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率
  最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来访问到的是那个页面，操作系统无法提前预判页面访问顺序，因此，最佳置换算法是无法实现的。

• 先进先出置换算法
  每次选择淘汰的页面是最早进内存的页面
  实现方法：吧调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可，队列的最长长度取决于系统为进程分配了多少块内存
  分配三个内存块时，缺页次数：9次

  
  分配四个内存块时，缺页次数：10次

  
  Belady 异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
  只有FIFO算法会产生Belady异常，另外FIFO算法虽然实现简单，但该算法与进程实际运行的规律不适应，因为先进入的页面也可能最经常被访问，因此，算法性能差

• 最久未使用置换算法
  每次淘汰的页面是最近最久未使用的页面
  实现方法，赋予每个页面对应的页表项中，用访问字段记录该页面上自上次被访问以来所经历的时间t，当前要淘汰一个页面时，选择现有页中t值最大的，即最近最久未使用页面

  

• 时钟置换算法
  实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描。

• 改进的时钟置换算法
  算法规则：将所有可能被置换的页面排成一个循环队列第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为0第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中

总结：

磁盘调度算法

• 先来先服务算法（FCFS）
  假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道按照 FCFS 的规则，按照请求到达的顺序，磁头需要依次移动到 55、58、39、18、90、160、150、38、184 号磁道
  
  磁头总共移动了 45+3+19+21+72+70+10+112+146 = 498 个磁道
  响应一个请求平均需要移动 498/9 = 55.3 个磁道（平均寻找长度）
  优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去
  缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。
• 最短寻找时间优先（ SSTF）
  SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）
  假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道
  
  磁头总共移动了 (100-18) + (184-18) = 248 个磁道
  响应一个请求平均需要移动 248/9 = 27.5 个磁道（平均寻找长度）
  优点：性能较好，平均寻道时间短
  缺点：可能产生“饥饿”现象
• 扫描算法
  SSTF 算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。
  假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道
  
  磁头总共移动了 (200-100) + (200-18) = 282 个磁道
  响应一个请求平均需要移动 282/9 = 31.3 个磁道（平均寻找长度）
  优点：性能较好，平均寻道时间较短，不会产生饥饿现象
  缺点：①只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
  ②SCAN算法对于各个位置磁道的响应频率不平均（如：假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一段距离；而响应了184号磁道的请求之后，很快又可以再次响应 184 号磁道的请求了）
• LOOK调度算法
  扫描算法（SCAN）中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK 调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫 LOOK）
  假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道
  
  磁头总共移动了 (184-100) + (184-18) = 250 个磁道
  响应一个请求平均需要移动 250/9 = 27.5 个磁道（平均寻找长度）
  优点：比起 SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短
• 循环扫描算法（C-SCAN）
  SCAN算法对于各个位置磁道的响应频率不平均，而 C-SCAN 算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请 求。
  假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道
  
  磁头总共移动了 (200-100) + (200-0) + (90-0)= 390 个磁道
  响应一个请求平均需要移动 390/9 = 43.3 个磁道（平均寻找长度）
  优点：比起SCAN 来，对于各个位置磁道的响应频率很平均。
  缺点：只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了；并且，磁头返回时其实只需要返回到18号磁道即可，不需要返 回到最边缘的磁道。另外，比起SCAN算法来，平均寻道时间更长。
• C-LOOK调度算法
  C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK 算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
  假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道
  
  磁头总共移动了 (184-100) + (184-18) + (90-18)= 322 个磁道
  响应一个请求平均需要移动 322/9 = 35.8 个磁道（平均寻找长度）
  优点：比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短