导图社区 408王道操作系统
- 134
- 1
- 0
- 举报
408王道操作系统
按王道的教科书以及视频整理，其中每章的LL为王道的每章难易点总结，黄色部分为高频重要内容。
编辑于2024-03-01 01:23:46
- 相似推荐
- 大纲
操作系统
计算机系统概述
LL
本章主要考察选择题，概念多，但不难理解。其中，1.4、1.5、1.6包含新考点。 1.1 操作系统的基本概念 ● 这一节没什么好说的 1.2 操作系统发展历程 ● 要能理解各类操作系统的优点、缺点、用途，不排除考简答题的可能。 1.3 操作系统运行环境 ● 本节是第一章的核心，要能理解中断、异常、系统调用的作用和原理，做完课后题之后，尝试动手梳理中断、异常、系统调用的处理过程 ● 在计算机组成原理第七章会详细学习“中断”的硬件原理，可与本节一起复习 1.4 操作系统结构 ● 在2022之前，只考宏内核、微内核两种体系结构。2022修改大纲后，又增加了分层法、模块化、外核。 ● 可以确定的是，本节只可能考小题，大概率是对比各种体系结构间的优缺点，注意理解课件中给大家的总结的那张表即可 1.5 操作系统引导 ● “操作系统引导”是2022年大纲新增内容，但早在2021年就在408大题中，以简答题的方式考察过，那个题目的得分率不高。因此2022年大纲新增“操作系统引导”只是一种补救行为，是为了将2021年超纲考察的知识合理化。 1.6 虚拟机 ● 本节同样是2022大纲新增内容，目前还没考过，如果考，大概率是对比第一类和第二类虚拟机的特性，注意理解课件中给大家的总结的那张表即可
OS基本概念
概念
操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供用户和其他软件方便的接口和环境，是计算机系统中最基本的系统软件
特征
并发
指计算机系统中同时存在多个运行的程序，具有处理和调度多个程序同时执行的能力 通过分时得以实现
共享
互斥共享
同时访问
虚拟
利用多道程序设计将一个物理上的CPU虚拟为多个逻辑上的CPU，称为虚拟处理机 利用虚拟存储器技术将一台机器的物理存储器变为虚拟存储器 利用虚拟设备技术将一台物理I/O设备虚拟为多台逻辑上的I/O设备 虚拟技术：时分复用、空分复用
异步
在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，即进程的异步性
功能
管理
处理机管理：处理机的分配以进程为基本单位，对处理机的管理可归结为对进程的管理，进程管理的主要功能：进程控制、进程同步、进程通信、死锁处理、处理机调度
存储器管理：给多道程序的运行提供良好的环境，包括内存分配与回收、地址映射、内存保护与共享和内存扩充
文件管理：包括文件存储空间的管理、目录管理即及文件读写管理与保护
设备管理：包括缓冲管理、设备分配、设备处理和虚拟设备
接口
命令接口
联机命令接口：交互式命令接口，适用于分时或实时系统的接口
脱机命令接口：批处理命令接口，适用于批处理系统，由一组作业控制命令组成
程序接口
在程序中进行系统调用来使用程序接口
扩充机器
没有任何软件支持的计算机称为裸机，将覆盖了软件的机器称为扩充机器/虚拟机
OS发展历程
手工操作阶段
所有工作都要人工干预，缺点：资源利用率低、CPU利用不完全
批处理阶段
单道批处理系统
自动性、顺序性、单道性 优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升 缺点：内存中仅能有一道程序运行，CPU有大量的时间是在空闲/等待I/O完成
多道批处理系统
多道、宏观上并行、微观上串行 多道程序并发执行，共享计算机资源，资源利用率大幅提升，系统吞吐量增大 缺点：用户响应时间长，没有人机交互功能
分时操作系统
计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互 优点：用户请求可以被及时响应，解决了人机交互问题，允许多个用户同时使用一台计算机，且操作相互独立 缺点：不能优先处理紧急任务
实时操作系统
及时性、可靠性 硬实时：必须在规定的时刻完成 软实时：可接受偶尔违反时间规定 优点：能优先处理紧急任务
网络操作系统和分布式计算机系统
网络操作系统：网络中各种资源的共享及各台计算机之间的通信 分布式计算机系统：分布性、并行性，任何工作都可分布在几台计算机上，由它们并行工作、协同完成
个人计算机操作系统
如Windows XP、MacOS，方便个人使用
OS运行环境
处理器运行模式
将CPU的运行模式划分为用户态和核心态 内核态运行内核程序，可以执行特权指令 用户态运行应用程序，只能执行非特权指令
中断和异常的概念
外中断
时钟中断
I/O中断请求
异常(内中断)
软件中断
故障：由错误条件引起的，可能被内核程序修复，内核程序修复后会把CPU使用权还给应用程序，让它继续执行下去，如：缺页故障、除数为0、运算溢出
陷入：由陷入指令引发，是应用程序故意引发的
硬件中断
终止：由致命错误引起，内核程序无法修复该错误，因此一般不再将CPU使用权还给引发终止的应用程序，而是直接终止该应用程序，如：控制器出错、存储器校验错
系统调用
指操作系统提供给应用程序（程序员/编程人员）使用的接口，可理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务
按功能分类：设备管理、文件管理、进程控制、进程通信、内存管理
OS结构
分层法
最底层是硬件，最高层是用户接口，每层只能调用紧邻它的低层的功能和服务 优点：便于系统的调试和验证，简化了系统的设计和实现；易扩充和易维护 缺点：合理定义各层比较困难，依赖关系固定后往往显得不够灵活；效率较差
模块化
将操作系统按功能划分为若干个具有一定独立性的模块，每个模块具有某方面的管理功能，并规定好各模块间的接口，使各模块能通过接口通信 内核=主模块+可加载内核模块 主模块：只负责核心功能如进程调度、内存管理 可加载内核模块：可以动态加载新模块到内核，无需重新编译整个内核 优点：提高了系统设计的正确性、可理解性和可维护性 逻辑清晰易于维护，确定模块间接口后即可多模块同时开发 支持动态加载新的内核模块，增强OS适应性 任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高，加速开发过程 缺点：模块间的接口规定很难满足对接口的实际需求；各模块设计者齐头并进，每个决定无法建立在上一个已验证的正确决定的基础上，因此无法找到一个可靠的决定顺序
宏内核
将OS的主要功能模块都作为系统内核运行在核心态 优点：高性能 缺点：内核代码庞大、结构混乱、难以维护 Windows、Android、iOS、macOS、Linux、UNIX
微内核
将内核中最基本的功能(进程管理调度、低级存储器管理、中断和陷入处理)保留在内核 微内核OS：内核足够小、基于C/S服务器模式、应用“机制与策略分离”原理、采用面向对象技术 优点：扩展性和灵活性、可靠性和安全性、可移植性、功能少、结构清晰、方便维护、分布式计算 缺点：需要频繁地在核心态和用户态之间切换，性能低 Windows NT
外核
内核负责进程调度、进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全。 优点：减少了映射层，将多道程序与用户操作系统代码加以分离，且相应的负载不重
OS引导
虚拟机
使用虚拟技术，将一台物理机器虚拟化为多台虚拟机器，每个虚拟机器都可以独立运行一个操作系统
第一类虚拟机管理程序
直接运行在硬件上
第二类虚拟机管理程序
运行在宿主操作系统上
进程与线程
LL
小题和大题的重点章节。全部小题都要认真做，而大题可以有侧重地做。截至2022年，所有大题都是考察 2.3 同步与互斥。因此，一轮复习重点做 2.3 的课后大题，其他小节的大题可降低优先级，时间不够可以直接不做。 2.1 进程与线程 ● 本节内容多，概念杂，但难度不高，主要考选择题。没什么技巧可言，认真学、认真做题就行。 2.2 处理机调度 ● 本节主要考概念型小题 ● 2.2.4 典型的调度算法看起来很可能考大题，但事实并非如此。很多同学在第一次复习时，会花大量时间完成本节全部大题，其实没必要。 ● 第一轮复习，可以重点看看大题12题（2016真题），其他大题随便选两个练练手即可。 2.3 同步与互斥 ● 操作系统大题重点来了，从2009年至2022年，共考了7年，考察频率非常高。 ● 大题通常会让你用PV操作解决同步、互斥。需要使用到 2.3.4、2.3.6（23版王道书）相关知识，手写代码，方能搞定此类大题。除 2.3.4、2.3.6 之外的其他部分，以“能解决小题”为目标来学习，不要求手写代码。 ● 2.3.6 是非常非常非常重要的，掌握好 2.3.6 相当于拿下了一个8分的大题。其中包含三大类问题：生产者-消费者问题、哲学家进餐问题、读者-写者问题。特别提醒各位408考生，今年要注意“读者-写者问题”，个人预言很可能考。 ● 本节的课后大题值得在第一轮复习时就做一做，如果时间太紧，建议至少挑五六个题练练手，如果没有思路可以看看习题讲解视频。 ● 第二轮强化课会带大家梳理PV操作大题的解题思路。建议自己先多做一些题目练练手，先自主练习，再听强化课效果更佳。如果自己没做过题，直接听强化课是不行的。 2.4 死锁 ● 本节不难，主要考察小题，截至2022年尚未出现大题 ● 不过，需留意 2.4.3 死锁避免，即银行家算法，未来有考察大题的可能性。因此本节的课后大题中，涉及到“银行家算法”的题目可以挑两三题练练手，防止出题老师来骗、来偷袭
进程与线程
进程的概念和特征
概念
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位 进程是动态的，进程实体/映像是静态的
组成
进程实体(进程映像)包括PCB、程序段、数据段，PCB是进程存在的唯一标志 操作系统对进程进行管理工作所需的信息都存在PCB中 PCB是给操作系统用的，程序段、数据段是给进程自己用的
特征
动态性(最基本)，进程是程序的一次执行过程，是动态地产生、变化和消亡的
并发性，内存中有多个进程实体，各进程可并发执行
独立性，进程是能独立运行、独立获得资源、独立接受调度的基本单位
异步性，各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题
结构性，每个进程都会配置一个PCB，结构上看，进程由程序段、数据段、PCB组成
进程的状态和转换
\
进程的组织
PCB
进程描述信息：进程标识符PID、用户标识符PID（主要为共享和保护服务）
进程控制和管理信息：进程当前状态、进程优先级、代码运行入口地址、程序的外存地址、进入内存时间、处理机占用时间、信号量使用
资源分配清单：代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标
处理机相关信息：通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、状态字
程序段
数据段
进程控制
进程控制用的程序段称为原语，原语执行期间不允许中断，它是一个不可分割的基本单位 通过关中断、开中断指令（内核程序，运行在核心态）实现“原子性”
进程的创建
进程的终止
进程的阻塞和唤醒
进程通信
共享存储
消息传递
直接通信：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息
间接通信：发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息。这种中间实体一般称为信箱，该通信方式广泛应用于计算机网络中
管道通信
线程和多线程模型
线程的基本概念
线程是一个基本的CPU执行单位，也是程序执行流的最小单位 引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，减小并发时的时空开销，提升了系统的并发度 引入线程后，进程只作为除CPU之外的系统资源的分配单位
线程ID、程序计数器、寄存器集合、堆栈
线程与进程的比较
调度：引入前进程是拥有资源和独立调度的基本单位，引入后线程是独立调度的基本单位
并发度：一个进程中的多个线程之间可并发执行，不同进程中的线程也能并发执行 使操作系统具有更好的并发性，提高了系统资源的利用率和吞吐量
拥有资源：进程是系统拥有资源的基本单位，而线程不拥有系统资源，但线程可以访问其隶属进程的系统资源，表现在属于同一进程的所有线程都具有相同的地址空间
独立性：每个进程都拥有独立的地址空间和资源，同一进程的多个线程共享进程的地址空间和资源
系统开销：线程切换开销小，进程切换开销大
支持多处理机系统：对于多线程进程，可以将进程中的多个线程分配到多个处理机上执行
线程的属性
线程是轻型实体，不拥有系统资源，但每个线程有一个唯一的标识符和线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态
不同的线程可以执行相同的程序
同一进程中的各个线程共享该进程拥有的资源
多CPU的计算机系统中，各线程可同时占用不同的CPU
线程有就绪、阻塞、运行三种基本状态
线程的状态和转换
线程的组织与控制
线程的实现方式
用户级线程ULT：有关线程管理的所有工作都由应用程序在用户空间中完成，内核意识不到线程的存在 优点：线程切换不需要切换到内核空间，节省了模式切换的开销；调度算法可以是进程专用的，不同的进程可以根据自身的需要对自己的线程选择不同的调度算法；用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分 缺点：当线程执行一个系统调用时不仅该线程被阻塞，且进程内的所有线程都被阻塞，不能发挥多处理机的优势，内核每次分配给一个进程的仅有一个CPU，因此进程中仅有一个线程能执行
内核级线程KLT：线程管理的所有工作是在内核空间内实现的，内核空间为每个内核级线程设置一个线程控制块 优点：能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行 如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可运行其他进程中的线程；内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小；内核本身可采用多线程技术，可以提高系统的执行速度和效率 缺点：同一进程中的线程切换需要从用户态转到核心态进行，系统开销大
组合方式：内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程
多线程模型
多对一模型：多个用户级线程映射到一个内核级线程 优点：线程管理开销小、效率高 缺点：如果一个线程在访问内核时发生阻塞，则整个进程都会被阻塞；在任何时刻，只有一个线程能够访问内核，多个线程不能同时在多个处理机上运行
一对一模型：每个用户级线程映射到一个内核级线程 优点：并发度高 缺点：每创建一个用户线程，相应地就需要创建一个内核线程，开销较大
多对多模型：n个用户线程映射到m个内核级线程上 优点：并发度高、开销小、效率高
处理机调度
调度的概念
概念
处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现程序并发地执行。 处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题
层次
高级(作业)调度：从外存上处于后备队列的作业中挑选一个，给它们分配内存、输入/输出设备等必要的资源。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB
中级(内存)调度：从处于挂起状态的进程中选取一个重新调入内存，实际上是存储器管理中的对换功能
低级(进程)调度：从就绪队列中选取一个进程，将处理机分配给它，是操作系统中最基本的一种调度，进程调度的频率很高，在一般的操作系统中都必须配置进程调度
三级调度的联系
调度的目标
CPU利用率：CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
系统吞吐量：单位时间内完成作业的数量
周转时间：作业完成时间-作业提交时间 平均周转时间=各作业周转时间之和/作业数 带权周转时间=作业周转时间/作业实际运行的时间
等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低 对进程来说，等待时间指进程建立后等待被服务的时间之和 对作业来说，不仅考虑建立进程后的等待时间，还有作业在外存后备队列中等待的时间
响应时间：从用户提交请求到首次产生响应所用的时间
调度的实现
调度程序
排队器、分派器、上下文切换器
调度的时机、切换与过程
需要进行进程调度与切换的情况
主动放弃处理机： 1.进程正常终止 2.运行过程中发生异常而终止 3.进程主动请求阻塞（如等待I/O）
被动放弃处理机： 1.分给进程的时间片用完 2.有更紧急的事需要处理（如I/O中断） 3.有更高优先级的进程进入就绪队列
不能进行进程调度与切换的情况
在处理中断的过程中
进程在操作系统内核程序临界区中
在原子操作过程中（原语）
进程调度方式
非剥夺调度方式
只允许进程主动放弃处理机 优点：系统开销小、实现简单，适用于大多批处理系统 缺点：无法及时处理紧急任务，不适合分时系统和实时系统
剥夺调度方式
当一个进程正在处理机上执行时，如果有更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程 优点：提高系统吞吐率和响应效率，可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断），适用于分时操作系统、实时操作系统
闲逛进程
进程切换时，没有其他就绪进程时，运行闲逛进程idle 优先级最低，可以是0地址指令，占一个完整的指令周期 能耗低，不需要CPU以外的资源，不会被堵塞
两种线程的调度
用户级线程调度：内核选择一个进程并给予时间控制，由进程中的调度程序决定哪个线程运行，线程切换在同一进程中进行，仅需要少量的机器指令
内核级线程调度：内核选择一个特定线程运行，不需要考虑该线程属于哪个进程 内核级线程的线程切换需要完整的上下文切换，修改内存映像、使高速缓存失效，导致若干数量级的延迟
典型的调度算法
先来先服务FCFS
短作业优先SJF
题目中未说明则默认SJF是非抢占式的
高响应比优先HRRN
早期批处理的算法比较
优先级
时间片轮转
多级队列
多级反馈队列
交互式系统的算法比较
进程切换
上下文切换
切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态，称为上下文切换。上下文是指某一时刻CPU寄存器和程序计数器的内容，进行上下文切换时内核会将旧进程状态保存在其PCB中然后加载经调度而要执行的新进程的上下文。 上下文切换流程： 1.挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器 2.更新PCB信息 3.把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列 4.选择另一个进程执行并更新PCB 5.跳转到新进程PCB中的程序计数器所指向的位置执行 6.恢复处理机上下文
上下文切换的消耗
上下文切换与模式切换
用户态和内核态之间的切换称为模式切换 上下文切换只能发生在内核态
同步与互斥
同步与互斥的基本概念
临界资源：一次仅允许一个进程使用的资源 临界资源的访问过程分为四部分： 1.进入区：检查可否进入临界区并设置标志 2.临界区：访问临界资源的那段代码 3.退出区：清除正在访问临界区的标志 4.剩余区：代码中的其余部分
同步：又称直接制约关系，多个进程需要相互配合地完成工作
互斥：间接制约关系，同一时间段仅允许一个进程访问临界资源 准则： 空闲让进：临界区空闲时允许一个进程访问 忙则等待：临界区正在被访问时，其他试图访问的进程需要等待 有限等待：要在有限时间内进入临界区。保证不会饥饿 让权等待：进入不了临界区的进程要释放处理机，防止忙等
实现临界区互斥的基本方法
软件实现方法
单标志法
双标志先检查法
双标志后检查法
Peterson's Algorithm
遵循了空闲让进、忙则等待、有限等待三个原则，但是仍未遵循让权等待的原则
硬件实现方法
中断屏蔽方法
硬件指示方法
TestAndSet指令
Swap指令
互斥锁
信号量
信号量机制
整型信号量
记录型信号量
用信号量实现进程互斥、同步、前驱关系
进程互斥
进程同步
前驱关系
对比
管程
管程
组成
管程的名称 局限于管程内部的共享数据结构说明 对该数据结构进行操作的一组过程 对局限于管程内部的共享数据设置初始值的语句
特征
局限于管程的数据只能被局限于管程的过程所访问 一个进程只有通过调用管程内的过程才能进入管程访问共享数据 每次仅允许一个进程进入管程执行某个内部过程，从而实现进程互斥
条件变量
经典同步问题
生产者-消费者
系统中有一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待 缓冲区是临界资源，各进程必须互斥访问
问题分析： 关系分析：生产者和消费者对缓冲区的互斥访问是互斥关系，同时生产者和消费者对产品的生产/消耗是同步关系 思路：解决互斥和同步PV操作的位置 信号量设置：
复杂生产者-消费者
桌面上有一个只能放一个水果的盘子，爸爸放苹果，妈妈放橘子，儿子只吃橘子，女儿只吃苹果，当盘子为空时父母才可以放水果，当盘子有自己需要的水果时，孩子才会吃水果
问题分析： 关系分析：爸爸和妈妈是互斥，爸爸和女儿、妈妈和儿子是同步
读者-写者
哲学家进餐
问题分析：
防止死锁发生
吸烟者
问题分析： 关系分析：供应者与抽烟者分别是同步关系，抽烟者对抽烟是互斥关系 思路：4个进程，供应者向三个抽烟者提供材料，抽烟者回应供应者信号 信号量设置：分别定义offer1、2、3为三个抽烟者所需要的材料，信号量finish为互斥的抽烟动作
死锁
死锁概念
定义
在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。若无外力干涉，这些进程都无法向前推进
原因
系统资源的竞争：对不可剥夺资源的竞争
进程推进顺序非法：进程在运行过程中，请求和释放资源的顺序不当；信号量使用不当（进程间彼此等待对方发来的信息）
死锁产生的必要条件
处理策略
死锁预防
破坏互斥
把互斥使用的资源改造为允许共享使用，比如SPOOLing技术 缺点：大部分资源不可以共享使用，且为了系统安全要保护这种互斥性
破坏不剥夺
方案一：当某个进程请求新的资源得不到满足时，必须立即释放保持的所有资源，待以后需要时再重新申请 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺，一般需要考虑各进程的优先级 缺点：实现起来比较复杂；释放已获得的资源可能造成前一段工作的失效，只适用于易保存和恢复状态的资源如CPU；增加系统开销，降低系统吞吐量；若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就需要放弃，以后再重新申请，如果一直发生这样的情况就会导致进程饥饿
破坏请求并保持
采用静态分配方法，进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行，一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的资源 缺点：有些资源可能仅在运行初期或者运行快结束时才使用，系统资源被严重浪费，资源利用率低；会导致饥饿现象，由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行
破坏循环等待
采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（编号相同的资源）一次申请完 缺点：编号必须相对稳定，限制了新类型设备的增加；进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；必须按规定次序申请资源，用户编程麻烦
死锁避免
系统安全状态
安全状态：指系统能按某种进程推进顺序(P1,P2……Pn)为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。 安全状态的P1，P2……Pn序列称为安全序列 只要能找到一个安全序列，系统就是安全状态 若系统处于安全状态一定不会发生死锁，若系统进入不安全状态，可能发生死锁
银行家算法
安全性算法
死锁检测和解除
资源分配图
死锁定理
死锁解除
内存管理
LL
本章分值高，大题多，常和计组一起考，即进行跨学科综合考察，可以说是操作系统最重要的一章。第一轮复习，除了搞定小题外，需要完成一些关键大题（一轮必做大题已在打卡表中说明）。 3.1 内存管理概念 ● 从历年真题来看，本节的大题主要出在 3.1.4_基本分页存储管理，需要认真学习深入理解 ● “覆盖与交换”已从408大纲中删除，但仍然要学，“交换”的思想很重要，有助于理解“进程挂起”等其他考点 ● 本节内容整体逻辑性较强，光靠听课看书一定是理解不透的，做大题有助于打通任督二脉。必做大题已在打卡表中说明。似懂非懂的大题记得看习题讲解视频。 ● 学完本节、且做完小题之后，自己在纸上手写梳理（默写）一遍“逻辑地址转物理地址的具体过程”，分为几种情况： ○ ①在分页系统中，如果具有一级页表，地址转换的过程是？—— 梳理完做大题第7题 ○ ②在分页系统中，如果具有一级页表，且具有快表机构，地址转换的过程是？——梳理完之后，做大题第9题、第10题 ○ ③在分段系统中，地址转换的过程是？——梳理完之后，做大题第6题、第5题 ○ ④在分页系统中，如果具有两级页表，地址转换的过程是？——梳理完做大题第4题 3.2 虚拟内存管理 ● 3.2.1~3.2.4 是大题的考察重点，各知识点之间逻辑较强，注意理解，不要死记硬背 ● 3.2.6 是2022大纲新增内容，大概率考概念型选择题，不会考很深 ● 3.2.8 地址翻译涉及计算机组成原理相关知识（Cache），第一轮复习可以先不深究，等计组也复习完之后，第二轮再来啃这块硬骨头。如果你所报考的院校不考计组，则3.2.8 可以直接不学。 ● 第一轮必做的大题已在打卡表中给出，做起来肯定会很吃力，没关系。这些大题有助于打通任督二脉，将第三章知识融会贯通。似懂非懂的大题记得看习题讲解视频。
内存管理概念
基础知识
基本原理和要求
内存管理：操作系统对内存的划分和动态分配 功能：内存空间的分配与回收、地址转换、内存空间的扩充、内存共享、存储保护
程序的链接与装入
编译：由编译程序将用户源代码编译成若干目标模块
链接
静态链接：在程序运行之前，先将各目标模块及他们所需的库函数链接成一个完整的装配模块，以后不再拆开
装入时动态链接：将用户源程序编译后得到的一组目标模块，在装入内存时，采用边装入边链接的方式。 优点是便于修改和更新，便于实现对目标模块的共享
运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接 优点：能加快程序的装入过程，还可节省大量的内存空间
装入
绝对装入
只适用于单道程序环境，灵活性差，编译器负责地址转换 在编译时，若知道程序将驻留在内存的某个位置，则编译程序将产生绝对地址的目标代码，绝对装入程序按照装入模块中的地址，将程序和数据装入内存。
可重定位装入
编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时完成的） 静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间，适用于早期多道批处理系统
动态运行时装入
编译、链接后的装入模块的地址都是从0开始的，装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址，这种方式需要一个重定位寄存器的支持 采用动态重定位时允许程序在内存中发生移动；可将程序分配到不连续的存储区，在程序运行前只需装入它的部分代码即可投入运行，在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间 适用于现代操作系统
逻辑地址与物理地址
编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址/逻辑地址 物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取
进程的内存映像
代码段、数据段、进程控制块PCB、堆、栈
内存保护
在CPU中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界
采用重定位寄存器和界地址寄存器来实现这种保护，重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值。 重定位寄存器用来“加”，逻辑地址加上重定位寄存器中的值就能得到物理地址 界地址寄存器用来“比”，通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界 加载重定位寄存器和界地址寄存器时必须使用特权指令，只有操作系统内核才可以加载这两个存储器，允许操作系统内核修改这两个寄存器的值，而不允许用户程序修改
内存共享
可重入代码称为纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码
内存分配与回收
单一连续分配➡️固定分区分配➡️动态分区分配➡️页式存储管理(离散分配)➡️分段存储管理
覆盖与交换
覆盖
将内存分成一个固定区和若干覆盖区，将经常活跃的部分放在固定区，其余部分按调用关系分段，让那些不可能被同时访问的程序段共享一个覆盖区 必须由程序员声明覆盖结构，操作系统完成自动覆盖 缺点：对用户不透明，增加了用户编程负担
交换技术
换出：把处于等待状态(或在CPU调度原则下被剥夺运行权利)的程序从内存移到辅存，把内存空间腾出来 换入：把准备好竞争CPU运行的程序从辅存移到内存 中级调度(内存调度)，就是要决定将哪个处于挂起状态的进程重新调入内存
总结
连续分配管理方式
单一连续分配
内存分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；在用户区内存中，仅有一道用户程序，即整个内存的用户空间由该程序独占 优点：简单无外部碎片，无需进行内存保护，因为内存中永远只有一道程序 缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率低
固定分区分配
是最简单的一种多道程序存储管理方式，将用户空间划分为若干个固定大小的分区，每个分区只装入一道作业，形成了最早的、最简单的一种可运行多道程序的内存管理方式 分区大小相等：缺乏灵活性 分区大小不等：划分为若干个较小的分区、适量的中等分区和少量大分区 优点：实现简单无外部碎片 缺点：当程序因为太大而放不进任何一个分区时，需要采用覆盖技术来使用内存空间；当程序小于固定分区大小时，造成空间浪费，即内部碎片，不能实现多进程共享一个主存区，所以存储空间利用率极低。
动态分区分配
在进程装入内存时，根据进程的大小动态地建立分区，使分区的大小正好适合进程的需要，因此系统分区的大小和数目是可变的
分配算法
首次适应First Fit
空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链/表，找到大小能满足要求的第一个空闲分区 优点：最简单、最好、最快 缺点：导致低地址部分出现很多碎片，每次分配查找时都要经过这些分区，增加开销
邻近适应Next Fit
又称循环首次适应分区，分配内存时从上次查找结束的位置开始继续查找 缺点：在内存空间的尾部分裂成小碎片，比首次适应算法要差
最佳适应Best Fit
空闲分区按容量递增次序链接，找到第一个能满足要求且最小的空闲分区分配给作业 缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、很难以利用的内存块，会产生很多外部碎片
最坏适应Worst Fit
空闲分区按容量递减次序链接，找到第一个能满足要求的最大的分区，分割一部分分配给作业 缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了
总结
回收
回收区与插入点的前/后一空闲分区相邻：将这两个分区合并，并修改前/后一分区表项的大小为两者之和 回收区同时与插入点的前、后两个分区相邻：将这三个分区合并，修改前一分区表项的大小为三者之和，取消后一分区表项 回收区没有相邻的空闲分区：此时应为回收区新建一个表项，填写始址与大小并插入空闲分区链
非连续分配管理方式
基本分页存储管理
基本概念
由于页号是隐含的，因此每个页表项占3B，存储整个页表至少需要3*(n+1)B 页表项连续存放，页号不占存储空间 页表记录的只是内存块号，而不是内存块的起始地址，J号内存块的起始地址=J*内存块大小
如何确定一个逻辑地址对应的页号、页内偏移量？ 如果每个页面大小为2K B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号。则计算机硬件可以很快速的把逻辑地址拆分成(页号,页内偏移量)
基本地址变换机构
总结
具有快表的地址变换机构
快表TLB是一种访存速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此相对，内存中的页表常称为慢表
两级页表
没必要让整个页表常驻内存，只将几个特定的页面存入内存，在需要访问页面时才把页面调入内存(虚拟存储技术)，可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存 若想访问的页面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存
基本分段存储管理
分段
段表
分段分页的对比
地址变换机构
系统中设置段表寄存器，用来存放段表始址F和段表长度M 1.从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W，注意题目中的逻辑地址是二进制还是十进制 2.比较段号S和段表长度M，若S>=M,则产生越界中断，否则继续执行 3.段表中段号S对应的段表项地址=段表始址F+段号S*段表项长度，取出该段表项的前几位得到段长C。若段内偏移量>=C,则产生越界中断，否则继续执行 4.取出段表项中该段的始址b,计算E=b+W,用得到的物理地址E去访问内存
段的保护与共享
分段管理的保护方法主要有两种： 存取控制保护，地址越界保护（将段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度，则产生越界中断；再将段表项中的段长和逻辑地址中的段内偏移进行比较，若段内偏移大于段长，也会产生越界中断；分页管理只需判断页号是否越界，页内偏移是不可能越界的）
段页式管理
分段、分页的优缺点分析
虚拟内存管理
虚拟内存概念
传统存储管理方式的特征：
局部性原理
虚拟存储器的定义和特征
袁春风
主存——磁盘
请求分页管理方式
页框分配
给一个进程分配的物理页框的集合就是这个进程的驻留集
内存分配策略
固定分配局部置换：为每个进程分配一定数目的物理块，在进程运行期间都不改变。所谓局部置换是指如果进程在运行中发生缺页，则只能从分配给该进程在内存的页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。 缺点：难以在刚开始就确定应该为每个进程分配多少个物理块才算合理，太少会频繁出现缺页中断，太多会降低CPU和其他资源的利用率
可变分配全局置换：先为每个进程分配一定数目的物理块，操作系统保持一个空闲物理块的队列，在进程运行期间可根据情况适当地增加或减少，所谓全局置换是指如果进程在运行中发生缺页，系统从空闲物理块队列中取出一块分配给该进程，并将所缺页调入。 优点：比固定分配局部置换更加灵活，可以动态增加进程的物理块 缺点：会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降
可变分配局部置换：为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，因此不会影响其他进程的运行。若进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直至该进程缺页率趋于适当程度；反之，若进程在运行中的缺页率特别低，则可适当减少分配给该进程的物理块
调入页面时机
预调页：根据局部性原理，预测那些不久后便会被访问的页面调入内存，但目前预调页的成功率仅约60%，用于进程的首次调入，在运行前调入
请求调页：进程在运行期间发现缺页时才将所缺页面调入内存，每次只能调入一页，每次调页都要磁盘I/O操作，I/O开销较大，在运行时调入
从何处调入页面
请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区采用连续分配方式，文件区采用离散分配方式，对换区的磁盘I/O速度比文件区的更快
页面置换算法
最佳置换算法OPT
先进先出FIFO
最近最久未使用LRU
时钟CLOCK/最近未用算法
总结
抖动和工作集
抖动
刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存 原因：进程频繁访问的页面数目高于可用的物理块数
工作集
在某段时间间隔内，进程要访问的页面集合，基于局部性原理，可以用最近访问过的页面来确定工作集。工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，若分配给进程的物理块小于工作集大小，则该进程就很有可能频繁的缺页
内存映射文件
虚拟存储器性能影响因素
地址翻译
文件管理
LL
本章是操作系统的难点，也是重点。 由于 4.1、4.2 的内容息息相关，因此视频课程中，会将两个小节的知识点穿插讲解，视频都是以 4.1_x 命名的。并不是没有更新 4.2 的视频，而是将 4.2 的内容穿插在 4.1 讲解了。 由于视频的讲解顺序与王道书并不是完全一致，因此建议大家参考“打卡表”推荐的顺序来学习。 4.1+4.2 文件系统基础+目录 ● 4.1、4.2 这两个小节是操作系统大题的超高频出题点，且难度大，综合性强，需要认真学习，深入理解。 ● 文件的逻辑结构、文件的物理结构 是初学者不易理解的两块知识。为了帮助大家捋清二者关系，专门录制了视频“4.1_5_逻辑结构VS物理结构.mp4”，需认真领会。 ● 打开目录的背后，发生了什么，需要结合 4.2 的大题深入理解（重要大题已在“打卡表”给出） ● 第一次学习，有些知识会觉得抽象，这很正常。这个部分最好的学习方法是：学完视频和王道书，一定要做几个关键大题，把这些大题搞懂了，就能捋清底层逻辑。“必做大题”已在“打卡表”中给出。 4.3 文件系统 ● 4.3 几乎都是新考点，大概率以选择题考察为主。 ● “4.3.3 外存空闲空间管理” 是唯一一个老考点，其中，“位示图法”可能结合大题考计算，今年要注意“位示图法” 和“5.3 磁盘管理”的大题，学完5.3后，建议再回来做 4.3 的两个大题。 ● “4.3.4 虚拟文件系统”部分，王道书和考点精讲视频 分别参考两本国外经典教材，阐述的重点各不相同。由于这个部分是全新考点，选择题的考法尚未确定，因此书和视频分别参考两本教材，可以给大家提供更全面的备考知识。 5.3 磁盘管理和固态硬盘 ● 文件管理、磁盘管理 可能会一起考大题。 ● 在23王道书中，学完第四章，建议先跳学 5.3，然后再学 5.1、5.2 ● “5.3.4 固态硬盘”是全新考点，以考察选择题为主。
文件系统基础
文件的基本概念
文件是以硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等
文件控制块和索引结点
文件的属性
名称、类型、创建者、所有者、位置、大小、保护、创建时间、最后一次修改时间、最后一次存取时间
文件控制块FCB
基本信息：名称、物理位置、逻辑结构、物理结构 存取控制信息：文件主、核准用户、一般用户的存取权限 使用信息：文件建立、修改时间 FCB的有序集合被称为文件目录
索引结点
文件描述信息单独形成一个称为数据结构的索引结点 文件目录中的目录项仅由文件名和指向该文件所对应的i结点的指针构成 提高文件检索速度！
磁盘索引结点：包含文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件链接计数、文件存取时间 内存索引结点：增加了索引结点编号、状态、访问计数、逻辑设备号、链接指针
文件的操作
基本操作
create创建文件： 提供参数：所需外存大小、文件存放路径、文件名 流程：在外存中找到空闲空间、根据存放路径找到目录文件，创建目录项
delete删除文件： 提供参数：文件存放路径、文件名 流程：根据文件存放路径找到目录文件，找到目录项；回收磁盘块；删除目录项
打开文件： 提供参数：文件存放路径、文件名、对文件的操作类型 流程：根据文件路径找到目录文件的目录项，检查操作权；将目录项复制到内存中的打开文件表中，将对应索引号返回给用户，之后用户使用打开文件表的编号来指明操作文件 打开文件时并不会把文件数据直接读入内存
读文件： 提供参数：文件路径及文件名（打开文件索引号）、读入数据量、读指针位置 流程：找到文件，从读指针位置开始读入指定的数据量，并更新打开文件表的读指针
写文件： 提供参数：文件路径及文件名（打开文件索引号）、写入数据量、写指针位置、写入外存的数据在内存的位置 流程：找到文件，从指定的内存位置，从写指针位置开始写入指定的数据量，并更新打开文件表的写指针
打开与关闭
操作系统维护一个包含所有打开文件信息的表（打开文件表），调用open根据文件名搜索目录，将指明文件的属性（包括文件在外存上的物理位置）从外存复制到内存的打开文件表的一个表目中，并将该表目的编号返回给用户 在多个不同进程可以同时打开文件的操作系统中，通常采用两级表：每个进程表和整个系统表 系统打开文件表为每个文件关联一个打开计数器，每个close操作使count递减，当打开计数器为0时，表示该文件不再被使用，可从系统打开文件表中删除相应条目
文件保护
口令保护
用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应口令，同时告诉允许共享该文件的其他用户。用户请求访问时必须提供相应的口令 优点：保存口令的空间开销不多，验证口令的时间开销也很小 缺点：正确的“口令”存放在系统内部，不够安全
加密保护
用户对文件进行加密，文件被访问时需要使用密钥。 优点：保密性强，节省了存储空间 缺点：编码和译码要花费一定时间
访问控制
在每个文件的FCB中增加一个访问控制列表ACL，该表中记录了各个用户可以对该文件执行哪些操作 优点：使用复杂的访问方法 缺点：长度无法预计并且可能导致复杂的空间管理 精简的访问列表采用拥有者、组、其他三种用户类型
文件的逻辑结构
无结构文件
数据由一系列二进制流或字符流组成，又称“流式文件”
有结构文件
由一组相似的记录组成，又称“记录式文件”，每条记录由若干个数据数据项组成。根据各条记录的长度是否相等可分为定长记录和可变长记录 按逻辑结构可分为顺序文件、索引文件、索引顺序文件、散列文件
顺序文件：文件中的记录一个接一个地顺序排列，记录在物理上是顺序存储或链式存储 在对记录进行批量操作，即每次要读/写一大批记录时，顺序文件的效率是所有逻辑文件中最高的 串结构：按存入时间排序，无法随机存取；顺序结构：按关键字排序，可随机存取
索引文件： 对于变长记录文件，建立索引表，按关键字排序，包含指针(逻辑起始地址)、长度 文件在物理上可离散存放 优点：检索速度快，适用于对信息处理的及时性要求高的场合 缺点：索引表太大，存储空间利用率低
索引顺序文件
索引表中一组记录对应一个索引表项，组与组之间的关键字可以无序，组内必须有序 索引表项含关键字和指向每组第一个记录的逻辑地址的指针
索引文件和索引顺序文件都提高了存取的速度，但因为配置索引表而增加了存储空间
散列文件
通过散列函数转换的关键字的值确定记录的物理地址，没有顺序的特性 有很高的存取速度，但会引起冲突
文件的物理结构
连续分配
每个文件在磁盘上占有一组连续的块 物理块号=起始块号+逻辑块号 优点：支持顺序访问和直接访问(随机访问)；实现简单、在顺序读/写时存取速度快 缺点：文件长度不宜动态增加、反复增删文件后会产生外部碎片、很难确定一个文件需要空间的大小因而只适用于长度固定的文件、存储空间利用率低
链接分配
采用离散分配的方式，消除了磁盘的外部碎片，提高了磁盘的利用率，可以动态地为文件分配盘块，无需事先知道文件的大小，对文件的插入、删除和修改也很方便
隐式链接： 目录项中含有文件第一块和最后一块的指针 优点：方便文件拓展，不会有外部碎片问题，外存利用率高 缺点：只支持顺序访问，不支持随机访问，查找效率低 把几个盘块组成簇，可减少查找时间，但增加了内部碎片
显式链接：把用于链接文件各物理块的指针，从每个物理块的末尾中提取出来，显示地存放在内存的一张链接表中，整个磁盘仅设一张，称为文件分配表FAT 优点：方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。地址转换不需要访问磁盘，因此文件的访问效率更高 缺点：文件分配表占用存储空间
索引分配
为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块，索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块 优点：支持随机访问，方便文件拓展 缺点：索引表需要占用一定的存储空间，增加系统开销 链接方案：将多个索引块连接起来存放 多层索引：建立多层索引，使第一层索引块指向第二层索引块，还可根据文件大小的要求建立第三层、第四层索引块
混合索引
总结
逻辑结构与物理结构的对比
目录
概念
FCB的有序集合称为文件目录，一个FCB就是一个文件目录项 与文件管理系统和文件集合相关联的是文件目录，包含有关文件的属性、位置和所有权等 要求：按名存取、检索速度快、可以共享、可以重名
结构
单级
整个系统中只建立一张目录表，每个文件占一个目录项 单级目录实现了“按名存取”，但是不允许文件重名 不适用于多用户操作系统
两级
主文件目录：记录用户名及相应用户文件目录所在的存储位置 用户文件目录：记录该用户的文件FCB 解决了不同用户文件的“重名”问题，提高了检索速度，又保证了文件的安全 但是缺乏灵活性，不能实现文件的分类
树形
用户要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串，各级目录之间用“/”隔开，从根目录出发的路径称为绝对路径
无环图
对比
操作
实现
文件共享
硬链接
基于索引结点，在索引结点中有一个链接计数count，用于表示链接到本索引结点上的用户目录项的数目
软链接
只有文件主才拥有指向其索引结点的指针，共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针。访问文件的开销大，增加了启动磁盘的频率。
文件系统
结构
I/O控制：包括设备驱动程序和中断处理程序，在内存和磁盘系统之间传输信息
基本文件系统：向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块
文件组织模块：组织文件及其逻辑块和物理块，将逻辑块地址转换成物理块地址
逻辑文件系统：用于管理元数据信息，通过文件控制块来维护文件结构，负责文件保护
布局
文件系统在磁盘中的结构： 主引导记录MBR：位于磁盘的0号扇区，用来引导计算机，MBR后面是分区表，给出每个分区的起始和结束地址。MBR做的第一件事是确定活动分区，读入引导块。 引导块：MBR执行引导块中的程序后，该程序负责启动该分区中的操作系统。每个分区都有一个引导块 超级块：包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被载入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等 文件系统中空闲块的信息：可以使用位示图或指针链接的形式给出
文件系统在内存中的结构： 内存中的信息用于管理文件系统并通过缓存来提高性能。 内存中的安装表：包含每个已安装文件系统分区的有关信息 内存中的目录结构的缓存：包含最近访问目录的信息。对安装分区的目录，它可以包括一个指向分区表的指针。 整个系统的打开文件表：包含每个打开文件的FCB副本及其他信息 每个进程的打开文件表：包含一个指向整个系统的打开文件表中的适当条目的指针以及其他信息
外存空闲空间管理
存储空间的划分：将物理磁盘划分为一个个文件卷，将各个文件卷划分为目录区、文件区，包含文件系统的分区称为卷。目录区主要存放文件目录信息FCB、用于磁盘存储空间管理的信息
空闲表法
连续分配方式，为文件分配连续的存储空间，采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。回收磁盘块时注意表项合并问题
空闲链表法
空闲盘块链：将磁盘上的空闲空间以盘块为单位拉成一条链，分配时从链首摘下若干空闲盘块分配给用户，修改链头指针，回收时将空闲盘块插入链的末尾 优点：分配和回收一个盘块的过程很简单 缺点：但为一个文件分配盘块时可能要重复操作多次，效率较低，且空闲盘块链很长 空闲盘区链：将所有空闲盘区拉成一条链，每个盘区除含用于指示下一个空闲盘区的指针外，还有能指明本盘区大小（盘块数）的信息 优点：效率高、空闲盘块链短 缺点：分配与回收过程复杂
位示图法
成组链接法
用来存放一组空闲盘块号的盘块称为成组链块 成组链接法：把顺序的n个空闲盘块号保存在第一个成组链块中，其最后一个空闲盘块则用于保存另一组空闲盘块号，系统只需保存指向第一个成组链块的指针
盘块的分配：
盘块的回收：
虚拟文件系统
虚拟文件系统VFS为用户程序提供了文件系统操作的统一接口，屏蔽了不同文件系统的差异和操作细节，用户可以通过VFS提供的统一调用函数来操作不同文件系统的文件，无需考虑具体的文件系统和实际的存储介质 虚拟文件系统的特点：VFS要求下层的文件系统必须实现某些规定的函数功能（open/read/write）一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求 ；每打开一个文件，VFS就在主存中新建一个vnode,用统一的数据结构表示文件，无论该文件存储在哪个文件系统。vnode只存在于主存中，而inode即会被调入主存，也会在外存中存储
为实现VFS，Linux主要抽象了四种对象类型：超级块对象、索引结点对象、目录项对象、文件对象
文件系统挂载mounting：即文件系统安装/卸载 文件系统挂载要做的事：1.在VFS中注册新挂载的文件系统。内存中的挂载表包含每个文件系统的相关信息，包括文件系统类型、容量大小等。2.新挂载的文件系统要向VFS提供一个函数地址列表3.将新文件系统加到挂载点，也就是将新文件系统挂载在某个父名录下
分区和安装
I/O管理
LL
本章是操作系统和计算机组成原理的交叉章节，可能在计组部分考察大题。从历年真题来看，操作系统部分常考小题，暂未考过大题。本章考试要求不高，概念较多，是相对简单的一章。 5.1 I/O管理概述 ● 本节内容大部分与计组第七章重合，主要考小题，重点考“5.1.2 I/O控制方式” ● 对于王道书“5.1.3 I/O软件层次结构”，需记忆每个层次的名字、层次之间的顺序；各层次的作用尽量结合其名字去理解，做到“有印象”即可。 ● 23版王道书“5.1.4 应用程序I/O接口”、“5.2.5 设备驱动程序接口”为22大纲新增内容，近两年有可能出选择题，需要注意。 5.2 设备独立性软件 ● 本节的视频讲解顺序与23版王道书有区别，可根据“打卡表”建议顺序学习 ● “设备分配与回收”相关的几个数据结构需要记忆名字和作用，容易混淆、遗忘 5.3 磁盘管理和固态硬盘 ● 本节内容建议在第四章之后学习，复习建议见上文“第四章 文件管理”部分
I/O管理概述
I/O设备
分类
按使用特性
人机交互类外部设备：数据传输速度慢，鼠标、键盘等
存储设备：数据传输速度快，移动硬盘、光盘等
网络通信设备：速度介于两者之间，调制解调器等
传输速度
低速设备：几字节～数百字节/秒，键盘、鼠标等
中速设备：数千～上万个字节/秒，如激光打印机等
高速设备：数百千～千兆字节/秒，磁盘机、光盘机等
信息交换单位
块设备：信息交换以数据块为单位，属于有结构设备，如磁盘等 传输速率高、可寻址，可对它随机读/写任一块
字符设备：信息交换以字符为单位，属于无结构类型，如交互式终端机、打印机等 传输速率低、不可寻址，时常采用中断I/O方式
I/O接口（设备控制器）
与CPU的接口
用于实现CPU与控制器之间的通信，CPU通过控制线发出命令，通过数据线取出/放回数据 有数据线、地址线、控制线 数据线通常与两类寄存器相连：数据寄存器和控制/状态寄存器
与设备的接口
数据、控制、状态三种类型的信号
I/O逻辑
用于实现对设备的控制，负责接收和识别CPU的各种命令（地址译码），并负责对设备发出命令
设备控制器的功能
接收和识别CPU发来的命令；数据交换；标识和报告设备的状态；地址识别；数据缓冲；差错控制
I/O端口
I/O端口是指设备控制器中可被CPU直接访问的寄存器 数据寄存器：实现CPU与外设之间的数据缓冲 状态寄存器：获取执行结果和设备的状态信息，以让CPU知道是否准备好 控制寄存器：由CPU写入，以便启动命令或更改设备模式 为实现CPU与I/O端口通信： 独立编址：为每个端口分配一个I/O端口号，所有I/O端口形成I/O端口空间，普通用户程序不能对其访问，只有操作系统使用特殊的I/O指令才能访问端口 缺点：需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号 统一编址：又称内存映射I/O，每个端口被分配唯一的内存地址，且不会有内存被分配这一地址，通常分配给端口的地址靠近地址空间的顶端 优点：简化了指令，可以采用对内存进行操作的指令来对控制器进行操作
I/O控制方式
程序直接控制方式
CPU对外设状态进行循环检查，直到确定该字已经在I/O控制器的数据寄存器中 优点：简单易于实现 缺点：CPU和I/O设备只能串行工作，导致CPU的利用率相当低
中断驱动方式
CPU向I/O控制器发送读命令后可以继续做其他工作，直到I/O设备主动打断CPU的运行并请求服务 优点：比程序直接控制方式有效 缺点：但传输的基本单位仍然是字，数据中的每个字在存储器与I/O控制器之间的传输都必须经过CPU，导致中断驱动方式仍会消耗较多的CPU时间
DMA方式
在I/O设备和内存之间开辟直接的数据交换通路，彻底解放CPU 基本单位是数据块，所传送的数据是从设备/内存直接送入内存/设备，仅在传送一个或多个数据块的开始和结束时，才需要CPU干预，整块数据的传送是在DMA控制器的控制下完成的。
DMA控制器中的寄存器： 命令/状态寄存器CR：接收从CPU发来的I/O命令、有关控制信息或设备的状态 内存地址寄存器MAR：在输入时，它存放把数据从设备传送到内存的起始目标地址 数据寄存器DR：暂存从设备到内存或从内存到设备的数据 数据计数器DC：存放本次要传送的字（节）数
DMA控制器的工作过程： CPU接收到I/O设备的DMA请求时，它给DMA控制器发出一条命令，同时设置MAR和DC初始值，启动DMA控制器，然后继续其他工作。之后CPU就把控制操作委托给DMA控制器，由该控制器负责处理。DMA控制器直接与存储器交互，传送整个数据块，每次传送一个字，这个过程不需要CPU参与。传送完成后，DMA控制器发送一个中断信号给处理器。因此只有在传送开始和结束时才需要CPU的参与
优点：数据传输以块为单位，CPU介入频率进一步降低。数据传输效率增加，CPU和I/O设备的并行性得到提升 缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块，如果要读/写离散的数据块要发出好几条I/O指令
通道控制方式
I/O通道是指专门负责输入/输出的处理机。I/O通道方式是DMA方式的发展，可以进一步减少CPU的干预，即把对一个数据块的读/写为单位的干预，减少为对一组数据块的读/写及有关控制和管理为单位的干预。实现CPU、设备、I/O设备三者的并行操作，有效提高整个系统的资源利用率。 通道指令的类型单一，没有自己的内存，通道所执行的通道程序是放在主机的内存中的，即与CPU共享内存 DMA方式需要CPU来控制传输的数据块大小、传输的内存位置，而通道方式中这些信息是由通道控制的，每个DMA控制器对应一台设备与内存传递数据，一个通道可以控制多台设备与内存的数据交换
缺点：实现复杂，需要专门的通道硬件支持 优点：CPU、通道、I/O设备可并行工作，资源利用率很高，一个通道可以控制多台设备与内存的数据交换
总结
I/O软件层次结构
用户层I/O软件
实现与用户交互的接口，用户可直接调用在该层提供的、与I/O操作相关的库函数对设备进行操作，用户层软件必须通过系统调用来获取操作系统服务
设备独立性软件
用于实现用户程序与设备驱动器的统一接口、设备命令、设备的保护及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间 功能1:执行所有设备的公有操作，对设备的分配与回收、将逻辑设备名映射为物理设备名、对设备进行保护，禁止用户直接访问设备、缓冲管理、差错控制、提供独立于设备的大小统一的逻辑块，屏蔽设备之间信息交换单位大小和传输速率的差异 2.向用户层提供统一接口 建立逻辑设备名到物理设备名的映射关系：根据设备类型选择调用相应的驱动程序 操作系统可以采用两种方式管理逻辑设备表LUT： 1.整个系统只设置一张LUT，就意味着所有用户不能使用相同的逻辑设备名，只适用于单用户操作系统 2.为每个用户设置一张LUT，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。系统会在用户登录时为其建立一个用户管理进程，而LUT就存放在用户管理进程的PCB中
设备驱动程序
与硬件直接相关，负责具体实现系统对设备发出的操作命令，驱动I/O设备工作的驱动程序。设置设备寄存器、检查设备状态等。计算柱面号、磁头号、扇区号
中断处理程序
用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断进程
硬件
总结
应用程序I/O接口
字符设备接口
数据的存取和传输是以字符为单位，键盘、打印机等 传输速率较低、不可寻址，在输入/输出时通常采用中断驱动方式 get和put操作：字符设备不可寻址，只能采取顺序存取方式，为字符设备建立一个字符缓冲区，通过get和put操作读写字符 独占设备，接口要提供打开和关闭操作以实现互斥共享
块设备接口
数据的存取和传输是以数据块为单位，磁盘等 传输速率较高、可寻址，磁盘设备的I/O常采用DMA方式 隐藏了磁盘的二维结构，将磁盘所有的扇区从0到n-1依次编号，将二维结构变成一种线性序列；将抽象命令映射为低层操作；内存映射接口通过内存的字节数组来访问磁盘，而不提供读写磁盘操作，映射文件到内存的系统调用返回包含文件副本的一个虚拟内存地址。 read/write系统调用：向块设备的读写指针位置读/写多个字符 seek系统调用：修改读写指针位置
网络设备接口
又称为网络套接字socket接口 socket系统调用：创建一个网络套接字，需指明网络协议（TCP？UDP） bind将套接字绑定到某个本地端口，connect将套接字连接到远程地址，read/write从套接字读/写数据
阻塞/非阻塞I/O
阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待，大多数操作系统提供的I/O接口都是采用阻塞I/O eg:字符设备接口——从键盘读一个字符get 非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待 eg:块设备接口——往磁盘写数据write
设备独立性软件
高速缓存与缓冲区
缓冲区的作用： 缓和CPU与I/O设备之间速度不匹配的矛盾 减少对CPU的中断频率，放宽对CPU中断响应时间的限制 解决数据粒度不匹配的问题 提高CPU与I/O设备之间的并行性
单缓冲
主存中设置一个缓冲区，当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满后，才能从缓冲区把数据传出 Max（C，T）+M
双缓冲
主存中分配两个缓冲区 假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空 结论：采用双缓冲策略，处理一个数据块的平均耗时为Max（T，C+M） 当M+C<T，可使块设备连续输入；当C+M>T,可使CPU不必等待设备输入
若两台机器之间仅配置单缓冲，则它们在任意时刻都只能实现单方向的数据传输
循环缓冲
将多个大小相等的缓冲区链接成一个循环队列，循环缓冲用于输入/输出时，需要有指针in和out。in指针指向可以输入数据的第一个空缓冲区，out指针指向可以提取数据的第一个满缓冲区
缓冲池
由多个系统公用的缓冲区组成，空缓冲队列、装满输入数据的缓冲队列(输入队列)和装满输出数据的缓冲队列(输出队列)，还应具有4种缓冲区：用于收容输入数据的工作缓冲区、用于提取输出数据的工作缓冲区、用于收容输出数据的工作缓冲区及用于提取输出数据的工作缓冲区
设备分配与回收
概述
数据结构
设备控制表DCT
控制器控制表COCT
通道控制表CHCT
系统设备表SDT
步骤
策略
设备分配方式： 静态分配：对独占设备的分配，在进程运行前为其分配全部所需资源，运行结束后归还资源，不会出现死锁但设备的使用率低 动态分配：进程运行过程中动态申请设备资源，一旦用完立即释放。有利于提高设备利用率但若分配算法不当，有可能造成进程死锁
安全性
逻辑设备名到物理设备名的映射
在系统中设置一张逻辑设备表LUT，将逻辑设备名映射为物理设备名 LUT表项包括逻辑设备名、物理设备名和设备驱动程序入口地址，当进程用逻辑设备名来请求分配设备时，系统为它分配一台物理设备，并在LUT中建立一个表目，当以后进程再利用该逻辑设备名请求I/O操作时，系统通过查找LUT来寻找对应的物理设备和驱动程序
SPOOLing技术
用软件的方式模拟脱机技术 输入井和输出井：磁盘开辟的两个存储区域，输入井模拟脱机输入时的磁盘，用于收容I/O设备输出的数据。输出井模拟脱机输出时的磁盘，收容用户程序的输出数据。一个进程的输入/输出数据保存为一个文件，所有进程的数据输入/输出文件链接成一个输入/输出队列
输入缓冲区和输出缓冲区：内存中开辟的缓冲区，输入缓冲区用于暂存由输入设备送来的数据，输出缓冲区暂存从输出井送来的数据
输入进程和输出进程：用于模拟脱机输入/输出时的外围控制机
共享打印机：独占设备，SPOOLing技术改造成共享设备，将物理上的设备虚拟成逻辑上的多台设备
SPOOLing技术特点：提高了I/O的速度，将对低速I/O设备执行的I/O操作演变为对磁盘缓冲区中数据的存取，缓和CPU与I/O设备之间的速度不匹配的矛盾；将独占设备改造为共享设备；实现了虚拟设备功能
设备驱动程序接口
磁盘和固态硬盘
磁盘
磁盘是表面涂有磁性物质的物理盘片，通过一个称为磁头的导体线圈从磁盘存取数据 根据磁头是否可移动分为固定头磁盘和移动头磁盘，根据盘片是否可更换分为固定盘磁盘和可换盘磁盘
磁盘的管理
磁盘初始化
1.进行低级/物理格式化，划分扇区。一个扇区可分为头、数据区域、尾三个部分组成，管理扇区所需的各种数据结构一般存放在头、尾两个部分，包括扇区校验码
分区
2.将磁盘分区，每个分区由若干个柱面组成（C盘、D盘等） 3.逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（位示图、空闲分区表）
引导块
坏块
对于简单磁盘：在逻辑格式化时，对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如在FAT表上标明（坏块对操作系统不透明） 对于复杂磁盘：磁盘控制器（磁盘内部的一个硬件部件）会维护一个坏块链表，在磁盘出厂前进行低级格式化时就将坏块链进行初始化，会保留一些备用扇区用于替换坏块，称为扇区备用，坏块对操作系统透明
磁盘调度算法
一次磁盘读/写需要的时间
寻道时间
延迟时间 硬盘一周11.1ms,Tr为5.55ms,软盘旋转速度为300～600转/分，Tr为50～100ms
传输时间Tt
延迟时间和传输时间都与磁盘转速相关，且为线性相关，而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间
磁盘调度算法
先来先服务FCFS
根据进程请求访问磁盘的先后顺序进行调度 优点：公平；若请求访问的磁盘比较集中，则算法性能还可以 缺点：若有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差
最短寻找时间SSTF
优先处理与当前磁头最近的磁道，可以保证每次的寻道时间最短，但是并不保证总的寻道时间最短 优点：性能较好，平均寻道时间短 缺点：可能产生饥饿现象（磁头可能在一个小区域内来回移动）
扫描SCAN 电梯算法
在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求，即规定磁头运动方向，只有磁头移动到最外侧磁道时才能往内移动，移动到最内侧磁道时才能往外移动
LOOK调度算法： 边移动边观察，在磁头移动方向上已经无请求时，可立即改变磁头移动方向 优点：比起SCAN算法来，不需要移动到最外/内侧才能改变磁头方向，缩短寻道时间
循环扫描C-SCAN
只有磁头向某个特定方向移动时才处理磁道访问请求，返回时直接快速移动至起始端而不处理任何请求 缺点：只有到达最边上的磁道时才能改变磁头移动方向，比SCAN算法的平均寻道时间更长
C-LOOK调度算法： 在C-SCAN的基础上边移动边观察，在磁头移动方向上已经无请求时，可立即改变磁头移动方向
减少延迟时间
采用交替编号的策略，让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小 采用（柱面号，盘面号，扇区号）而非（盘面号，柱面号，扇区号）的物理地址，在读取地址连续的磁盘块时，可以减少磁头移动消耗的时间 错位命名：让相邻盘面的扇区编号“错位”，使读取连续的逻辑地址所需要的延迟时间更小
固态硬盘