第1章 操作系统概述

1. 操作系统基本概念

【基础知识】

• 操作系统：控制和管理整个计算机系统的硬件和软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。
• 操作系统是计算机系统中最基本的系统软件。
• 操作系统的基本特征：并发、共享、虚拟、异步（并发和共享最基本）
  • 并发：两个或多个事件在同一时间间隔内发生。（可以不同时，并行必须同时）
  • 共享：系统中的资源可供内存中的多个并发执行的进程共同使用。
    • 方式：互斥共享方式（临界资源）、同时访问方式（宏观，微观可能不同时）
  • 虚拟：把一个物理上的实体变为若干逻辑上的对应物。
    • 虚拟处理器技术：通过多道程序设计技术，采用让多道程序并发执行的方法。
    • 同时服务多用户，虚拟处理器、虚拟存储器（逻辑上扩充容量）
    • 时分复用技术（CPU分时共享）、空分复用技术（虚拟存储器）
  • 异步：运行随机，可能产生与时间有关的错误，环境相同保证结果相同。
• 操作系统功能：处理机管理、存储器管理、设备管理、文件管理、用户接口、扩充机器
  • 处理机管理：进程的管理（进程控制、同步、通信、死锁、处理机调度）
  • 存储器管理：内存分配与回收、地址映射、内存保护与共享、内存扩充
  • 文件管理：文件存储空间的管理、目录管理、文件读写管理与保护
  • 设备管理：完成用户I/O请求，缓冲管理、设备分配、设备处理和虚拟设备
  • 用户接口：
    • 命令接口：联机（交互式、分时实时）/脱机（批处理），包括命令解释器
    • 程序接口（系统调用，提供给编程人员/应用程序，目的是请求系统服务，也叫广义指令）
  • 资源扩充

【错题整理】

• 用户可以通过命令接口和系统调用两种方式来使用计算机。
• 用户在程序中试图读某文件的第100个逻辑块，使用操作系统提供的系统调用接口。文件I/O需要在内核态运行，读写都是通过系统调用实现的。
• 操作系统与用户通信接口通常不包括缓存管理指令，缓存透明，操作系统不提供系统调用。
• 单处理机系统只有独立于CPU的才能并行，如处理机与设备、处理机与通道、设备与设备。
• 多道程序系统不必支持虚拟存储管理，但可能导致竞争死锁从而降低CPU利用率。
• 库函数和系统调用的区别和联系：
  • 库函数是语言或应用程序的一部分，可以运行在用户空间中。而系统调用是操作系统的一部分，是内核为用户提供的程序接口，运行在内核空间中，而且许多库函数都会使用系统调用来实现功能。未使用系统调用的库函数，其执行效率通常要比系统调用的高。因为使用系统调用时，需要上下文的切换及状态的转换（由用户态转向和核心态）。

1. 操作系统发展历程

【基础知识】

• 手工操作阶段：人机矛盾，CPU和I/O设备之间速度不匹配的矛盾
• 批处理阶段（单道批处理系统、多道批处理系统）
  • 单道批处理系统：自动性、顺序性、单道性（CPU等I/O效率低）
  • 多道批处理系统：多道、宏观上并行、微观上串行，中断技术，资源利用率高、系统吞吐量大、响应时间长、不提供人机交互能力（制约性、间断性、共享性）
• 分时操作系统：分成很短的时间片轮流分配给各联机作业
  • 多个用户通过终端同时共享一台主机，同时交互操作互不干扰（支持多道程序设计）
  • 不同于多道批处理系统，这个实现了人机交互
  • 特征：同时性、交互性、独立性、及时性
• 实时操作系统
  • 硬实时系统：绝对地在规定时刻发生，绝对保证
  • 软实时系统：偶尔违反时间规定且不会引起任何永久性的损害
• 网络操作系统和分布式计算机系统：
  • 网络操作系统：网络资源共享、计算机间通信
  • 分布式计算机系统：通信方式交换信息、地位同等、资源共享、子系统且可重构、并行
• 个人计算机操作系统：最广泛，Windows、Linux、MacOS等

【错题整理】

• 实时操作系统必须在被控制对象规定时间内处理来自外部的事件。
• 实时系统的进程调度通常采用抢占式的优先级高者优先算法。
• 分时系统的一个重要性能是系统的响应时间，对操作系统的优先级+非抢占式调度算法因素进行改进有利于改善系统的响应时间。
• 分时系统追求的目标是比较快速响应用户。
• 在IBM-PC中，操作系统称为微型计算机操作系统。
• 多任务操作系统具有并发和并行的特点，不一定需要多CPU。
• 批处理操作系统特点：用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行，交互能力差。
• 分时操作系统特点：可让多个用户同时使用计算机，人机交互性较强，具有每个用户独立使用计算机的独占性，系统响应及时。
• 实时操作系统特点：能对控制对象作出及时反应，可靠性高，响应及时，但资源利用率低
• CPU利用率=\frac{CPU运行时间}{程序运行总时间}

1. 操作系统运行环境

【基础知识】

• 处理器运行模式
  • 两种程序：操作系统内核程序、用户自编程序（应用程序）
  • 指令类型
    • 特权指令：不允许用户直接使用的指令，只允许操作系统使用，如I/O指令、置中断指令、读写内存寄存器等
    • 非特权指令：允许用户直接使用的指令，不直接访问软硬件资源，仅限于访问用户地址空间
  • 运行模式：用户态（目态）和核心态（管态、内核态）
  • 内核：时钟管理、中断机制、原语、系统控制的数据结构及处理
• 中断和异常的概念
  • 中断（外中断）：来自CPU执行指令外部的事件，用于信息输入/输出。
    • 可屏蔽中断、不可屏蔽中断
    • 缺页处理、时钟中断等
  • 异常（内中断）：来自CPU执行指令内部的事件，不能屏蔽立即处理。
    • 故障（指令执行异常）、自陷（实现安排）、终止（硬件故障）
    • 除零异常、非法操作、地址越界、算数溢出、缺页、陷入指令
• 系统调用（也叫广义指令）
  • 需要特权指令，运行在核心态，因此CPU状态需要通过硬件中断/异常处理机制/访管指令从用户态转为核心态（该过程由硬件完成），内核进行处理。

【错题整理】

• 当计算机提供了核心态和用户态时，输入/输出指令必须在核心态下执行，因为需要中断操作。
• 操作系统中，通道技术是一种硬件技术。
• 用户程序设计时，使用系统调用命令，该命令经过编译后，形成若干参数和陷入（trap）指令。无法形成屏蔽中断指令。
• 中断处理是操作系统必须提供的功能，输入输出一定需要中断而中断在核心态。
• 用户程序在用户态要使用特权指令引起的中断属于访管中断。也就是转成核心态处理。
• 进程调度由操作系统实现，不需要硬件的支持。
• 在中断发生后，进入中断处理的程序属于操作系统程序。
• 置时钟指令与时间片有关，只能在核心态下运行。
• 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是程序状态字寄存器（PSW）。子程序调用只存下一条指令的地址（PC），中断处理需要保存PC和PSW。
• 处理外部中断是，应该由操作系统保存的是通用寄存器的内容、中断屏蔽字，同时初始化中断向量表，而中断点PC和PSW由硬件保存。
• 执行系统调用的过程：1️⃣ 传递系统调用参数 2️⃣ 执行陷入trap指令 3️⃣ 执行相应的服务程序 4️⃣ 返回用户态
• 处理器为什么要区分核心态和用户态两种操作方式？在什么情况下进行两种方式的切换？
  • 区分执行态的主要目的是保护系统程序。用户态到核心态的转换发生在中断产生时，而核心态到用户态的转换则发生在中断返回用户程序时。
• 为什么说知道出现中断和通道技术后，多道程序概念才变得有用？
  • 多道程序并发执行是指有的程序正在CPU上执行，而另一些程序正在I/O设备上进行传输，CPU和外设时间重叠必须有中断和通道技术的支持：
    • 通道独立于CPU运行，询问方式无法真正做到并行。
    • 中断技术CPU停下工作处理中断请求。
  • 二者结合实现CPU和I/O设备并行工作，通道进行输入/输出，通道工作结束中断请求，CPU暂停处理中断，这样真正做到了CPU和I/O设备并行工作。

1. 操作系统结构、引导、虚拟机

• 分层式OS：单层依赖，系统效率较低，功能分层设计
• 微内核：进程间通信、调度、与硬件紧密相关、中断和陷入处理，服务越少越稳定但效率不高
• Windows是宏内核操作系统。
• 计算机操作系统的引导程序位于硬盘中。
• 计算机启动过程：1️⃣ CPU加电，CS:IP指向FFFF0H 2️⃣ 执行JMP指令跳转到BIOS 3️⃣ 登记BIOS中断程序入口地址 4️⃣ 硬件自检 5️⃣ 进行操作系统引导
• 虚拟机没有实现真正的并行，多核处理机实现真正的并行。
• BIOS将控制权交给启动设备，CPU将主引导记录MBR加载到内存中，MBR检查分区表并将PBR加载到内内存加以执行。
• 操作系统初始化过程中需要创建中断向量表，以实现通电自检POST。

第2章 进程与线程

1. 进程与线程

【基础知识】

• 进程控制块（PCB）：描述进程的基本情况和运行状态，进而控制和管理进程（进程存在的唯一标志）
• 进程实体/进程映像 = 程序段 + 相关数据段 + PCB（映像静态，进程动态）
• 进程：进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
  • 特征：动态性、并发性、独立性、异步性
  • 状态：运行态、就绪态、阻塞态、创建态、终止态（最重要）

• PCB通常包含进程描述信息、进程控制和管理信息、资源分配清单和处理机相关信息。
• PCB组织方式：链接方式（队列）、索引方式（索引表）
• 进程控制用的程序称为原语，特点是执行期间不允许中断，不可分割的基本单位。
• 进程控制（原语）
  • 创建：子进程继承父进程拥有的资源
  • 终止：正常结束、异常结束、外界干预
  • 阻塞：请求资源失败、等待某种操作的完成、新数据尚未到达或无新任务可做
  • 唤醒：期待的I/O操作已完成、期待的数据已到达
• 进程的通信
  • 低级通信：PV；高级通信：高效率传输大量数据
    • 共享存储：共享空间写/读，使用同步互斥工具（PV），数据结构（低级）、存储区（高级）
    • 消息传递：格式化的消息为单位，发送消息和接收消息两个原语，直接通信/间接通信
    • 管道通信：生产者-消费者方式，先进先出，互斥、同步、确定对方存在；限制管道的大小，读进程也可能工作得比写进程快。只能由创建进程访问，可以继承。
• 线程：目的是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。
  • 基本的CPU执行单元，程序执行流的最小单元，被系统独立调度和分派的基本单位
  • 线程 = 线程ID + 程序计数器 + 寄存器集合 + 堆栈
  • 不拥有系统资源，和同一进程的线程共享进程拥有的全部资源
  • 三种基本状态：就绪、阻塞、运行
• 线程与进程的比较：
  • 调度：线程是独立调度的基本单位，线程切换代价远低于进程。
  • 并发性：不同进程可以并发，同一进程中不同线程/不同进程不同线程也能并发。
  • 拥有资源：线程不拥有资源，可以访问隶属进程的系统资源，同一进程的所有线程具有相同的地址空间
  • 独立性：每个进程拥有独立的地址空间和资源，除了共享全局变量不允许其他进程访问。线程共享进程的地址空间和资源。
  • 系统开销：进程切换涉及进程上下文的切换，线程切换只需保存和设置少量寄存器内容，因此线程间同步与通信非常容易实现，甚至无需操作系统的干预。
  • 支持多处理机系统：传统单线程进程只能运行在一个处理机，多线程进程可以吧进程中的多个线程分配到多个处理机上执行。
• 线程控制块（TCB）：线程标识符、寄存器（程序计数器、状态寄存器、通用寄存器）、线程运行状态、优先级、线程专有存储区、堆栈指针（独享的）。
• 线程的实现方式
  • 用户级线程（ULT）
    • 用户控件完成，内核意识不到线程存在（切换不需要内核支持）
    • 节省模式切换开销，可选不同调度算法，与操作系统平台无关
    • 系统调用阻塞进程所有线程阻塞，不能发挥多处理机的优势
  • 内核级线程（KLT）
    • 内核空间实现，能发挥多处理机的优势，一个线程阻塞不影响其他线程，内核支持线程具有很小的数据结构和堆栈，内核支持线程切换快开销小，内核本身可以多线程
    • 需要从用户态转到核心态，系统开销大。（线程调度在内核实现）
  • 组合方式：线程库
• 多线程模型：
  • 多对一模型：效率高，一个阻塞全部阻塞，只有一个线程能访问内核
  • 一对一模型：并发能力强，开销大
  • 多对多模型：上述两种的优点

【错题整理】

• 在单处理器系统中，若同时存在10个进程，则处于就绪队列的进程最多有9个。
• 一个进程释放了一台打印机，它可能会改变另一个等待打印机的进程。
• 程序封闭性只进程执行结果只取决于进程本身。并发进程失去封闭性是指共享变量，执行结果与速度有关。
• 进程跟时间片的关系只有就绪态的影响，时间片到进程从执行状态转为就绪态。
• 通常用户进程被建立后随着进程运行的正常或不正常而撤销。
• C语言程序分为三个段：
  • 正文段：二进制代码、常量
  • 数据堆段：动态分配的存储区
  • 数据栈段：临时使用的变量（未赋值的局部变量、参数传递值）
• 系统动态DLL库中的系统线程，被不同的进程所调用，它们是相同的线程。
• 只要就绪队列不空处理器效率就不变，不管多忙都是那样的效率。
• 两个合作进程无法利用高级语言程序设计中的全局变量/数据库交换数据，全部巨量是针对同一进程而言的。
• 设备分配不会导致创建新进程，设备分配是通过在系统中设置相应的数据结构实现的。
• 降低进程优先级的合理时机是进程时间片用完。
• 管道只允许单向通信，大小通常为内存的一页，读写都可能阻塞，可以多进程（父子进程）
• 进程与程序之间可以形成一对一、一对多、多对一、多对多的关系，请分别举例说明在什么情况下会形成这样的关系。
  • 执行一条命令或运行一个应用程序时，进程和程序之间形成一对一的关系。进程在执行过程中可以加载执行不同的应用程序，从而形成一对多的关系；以不同的参数或数据多次执行同一个应用程序时，形成多对一的关系；并发地执行不同的应用程序时，形成多对多的关系。
• 父进程创建子进程和主程序调用子程序有何不同？
  • 父进程创建子进程后，父进程和子进程同时执行（并发）。主程序调用子程序后，主程序暂停在调用点，子程序开始执行，直到子程序返回，主程序才开始执行。
• 为何进程之间的通信必须借助于操作系统内核功能？简单说明进程通信的几种主要方式。
  • 每个进程有自己独立的地址空间。在操作系统和硬件的地址保护机制下，进程无法访问其他进程的地址空间，必须借助于系统调用函数实现进程之间的通信。
  • 主要方式：共享内存区、消息传递、管道系统、共享文件
• 什么是多线程？多线程和多任务有什么区别？
  • 多线程是指在一个程序中可以定义多个线程并同时运行它们，每个线程可以执行不同的任务。
  • 区别：多任务是针对操作系统而言的，代表操作系统可以通知执行的程序个数；多线程是针对一个程序而言的，代表一个程序可以同时执行的线程个数，而每个线程可以完成不同的任务。

1. 处理机调度

【基础知识】

• 调度的层次（三级调度）
  • 高级调度（作业调度）：内存和辅存之间的调度
  • 中级调度（内存调度）：多挂起态，存储器管理中的对换功能
  • 低级调度（进程调度）：最基本，从就绪队列选取进程分配处理机
• 调度算法评价标准：
  • CPU利用率 = \frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}
  • 系统吞吐量：单位时间内CPU完成作业的数量
  • 周转时间
    • 周转时间 = 作业完成时间 - 作业提交时间
    • 平均周转时间=(作业1的周转时间+\cdots+作业n的周转时间)/n
    • 带权周转时间=\frac{作业周转时间}{作业实际运行时间}
    • 平均带权周转时间=(作业1的带权周转时间+\cdots+作业n的带权周转时间)/ n
  • 等待时间：进程处于等处理机的时间之和
  • 响应时间：从用户提交请求到系统首次产生相应所用的时间
• 调度的实现
  • 调度程序 = 排队器 + 分排器 + 上下文切换器
  • 不能调度的情况：处理中断中、进程在内核临界区（一般临界区是可以的）、其他需要完全屏蔽中断的原子操作过程中
  • 应该调度的请况：发生引起调度条件且当前进程无法继续运行下去、中断处理结束或自陷处理结束后
  • 调度方式
    • 非抢占调度方式/非剥夺方式：实现简单、系统开销小，不能用于分时系统/实时系统
    • 抢占调度方式/剥夺方式：暂停当前进程，分配给更重要紧迫的进程
  • 两种线程的调度
    • 用户级线程调度：进程中的调度程序决定
    • 内核级线程调度：内核选择，赋予时间片，超过时间片强制挂起
• 典型调度算法
  • 先来先服务（FCFS）调度算法
    • 不可剥夺，算法简单，效率低，长作业有利、短作业不利，有利于CPU繁忙型、不利于I/O繁忙型作业。
  • 短作业优先（SJF）调度算法
    • 对长作业不利，完全未考虑紧迫程度，作业长短根据估计执行时间而定
    • 平均等待时间、平均周转时间最少
  • 优先级调度算法
    • 非抢占式优先级调度算法/抢占式优先级调度算法；静态优先级/动态优先级
    • 系统进程>用户进程；交互型进程>非交互型进程；I/O型进程>计算型进程
  • 高响应比优先调度算法
    • 对FCFS和SJF综合考虑，计算响应比选最高的投入运行
    • 响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}，克服了饥饿现象
  • 时间片轮转调度算法
    • 主要适用于分时系统，FCFS但仅能运行一个时间片
    • 时间片长短因素：系统的响应时间、就绪队列中的进程数目和系统的处理能力
  • 多级队列调度算法
    • 设置多个就绪队列，每个队列不同的调度算法
  • 多级反馈队列调度算法（融合了前几种算法的优点）
    • 动态调整优先级和时间片大小，设置多个就绪队列，赋予各个队列的进程运行时间片的大小各不相同，每个队列采用FCFS算法，按队列优先级调度。
• 进程切换
  • 上下文切换
    • 上下文是指某一时刻CPU寄存器和程序计数器的内容，旧状态保存在PCB中
    • 流程：挂起一个进程➡️更新PCB信息➡️把进程的PCB移入相应的队列➡️选择另一个进程执行并更新其PCB➡️跳转到新进程的PCB中的程序计数器所指向的位置执行➡️恢复处理机上下文

【错题整理】

• 时间片轮转调度算法是绝对可抢占的。
• 作业是从用户角度出发的，它由用户提交，以用户任务为单位；进程是从操作系统出发的，由系统生成，是操作系统的资源分配和独立运行的基本单位，以操作系统控制为单位。
• 中断向量本身是用于存放中断服务例行程序的入口地址，因此中断向量地址就应是该入口地址的地址。
• 某单CPU系统中输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms, 3ms, 4ms，且都按输入、计算、输出的顺序执行，则执行完3个作业需要的时间最少是17ms。
  • 这种题画“甘特图”

• 注意进程调度和进程切换的时间，每一次都是三个都要累加的。
• 为什么说多级反馈队列调度算法能较好地满足各类用户的需要？
  • 对终端型作业用户而言，作业大多属于交互型作业，比较短小，系统只要能使这些作业在第1级队列所规定的时间片内完成，便可使终端型作业用户感到满意；
  • 对于短批处理作业用户而言，也是第1级队列中执行一个时间片即可完成，稍长也只需要第2级队列、第3级队列中各执行一个时间片即可完成，周转时间仍然较短；
  • 对于长批处理作业用户而言，依次1, 2, ..., n级队列中运行，然后按时间片轮转方式运行，用户不用担心其作业长期得不到处理。
• 画图一定要看好是哪种调度策略，是非抢占还是抢占。
• 批处理系统可能有处理多道作业的功能，比如两道作业：
  • 作业调度采用SJF，进程调度采用抢占式优先级调度算法
  • 作业由内存调度，进程由处理机调度。因此这种情况两个设备的空闲状况都要分析，作业只要内存还有位置就可以加入，此时进入进程调度环节抢占处理机。能处理几道作业就能放几个作业，满了需要等作业完成之后再进入（可能竞争）。
  • 新作业加进来CPU，进程调度需要比较的是原作业的剩余时间。
• 静态优先数：当就绪队列中总有优先数比较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。
• 设计动态优先数：priority=nice+k_1\times cpuTime-k_2\times waitTime, 其中k1>0, k2>0, 用于分别调整cpuTime和waitTime在priority中所占的比例。waitTime可使长时间等待的进程优先数减少，从而避免出现饥饿现象。

1. 同步与互斥

【基础知识】

• 临界资源：一次仅允许一个进程使用的资源。进程中访问临界资源的代码称为临界区。
  • 临界资源的访问：进入区、临界区、退出区、剩余区
• 同步/制约关系：为完成某种任务而建立的两个或多个进程，这些进程因为在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。这种直接制约关系来源于合作。
• 互斥/间接制约关系：当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程推出临界区后，另一进程才允许去访问此临界资源。
  • 同步机制准则：空闲让进、忙则等待、有限等待、让权等待。
• 实现临界区互斥的基本方法：
  • 软件实现方法：单标志法、双标志法先检查、双标志法后检查、Peterson's Algorithm。
  • 硬件实现方法：中断屏蔽方法、硬件指令方法
• 互斥锁
  • 进入临界区acquire()获得锁，退出临界区release()释放锁，硬件机制完成。
  • 主要缺点：忙等待。进程因某时间的发生而无法继续执行时，仍占有CPU，并通过不断地执行循环测试指令来等待该事件的完成。因此通常用于多处理器系统。
• 信号量
  • 标准原语wait和signal，也即“P操作”和“V操作”
  • 类型：
    • 整型信号量：未遵循“让权等待”，而是“忙等”
    • 记录型信号量：不存在“忙等”，整型变量value和进程链表L
  • 在同步问题中，若某个行为要用到某种资源，则在这个行为前面P这种资源一下；若某个行为会提供某种资源，则在这个行为后面V这种资源一下。
  • 在互斥问题中，P、V操作要夹紧使用互斥资源的那个行为，中间不能有其他冗余代码。
• 管程
  • 管程定义了一个数据结构和能为所有并发进程所执行（在此数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
  • 组成：管程的名称、局部于管程内部的共享数据结构说明、对该数据结构进行操作的一组过程（或函数）、对局部于管程内部的共享数据设置初始值的语句。
  • 管程把对共享资源的操作封装起来，每次只允许一个进程进入管程，从而实现进程互斥。
  • 条件变量：x.wait 和 x.signal，类似于PV操作，可以实现进程的阻塞/唤醒；但没有值，仅实现了“排队等待”功能。
• 经典同步问题
  • 生产者-消费者问题
    • 找好同步互斥关系，一对关系一个信号量
    • 类似于互斥信号量mutex初始值1，full记录满缓冲区数，empty记录空缓冲区数
  • 读者-写者问题
    • rsem上只有一个，读者压力单一进程（？）
  • 哲学家进餐问题
  • 吸烟者问题

【错题整理】

• 进程并发执行不需要信号量就能实现。
• 信号量初值可以是任意整数，互斥量小于0就表明临界区有一个进程，其绝对值表示等待进入临界区的进程数。
• 一个正在访问临界资源的进程，由于申请等待I/O操作而被中断时，它允许其他进程抢占处理器，但不得进入该进程的临界区。
• 临界区是指并发进程访问共享变量段的代码程序。
• 用V操作唤醒一个等待进程时，被唤醒进程变为就绪态。
• 信箱是一种间接通信方式。
• 若x是管程内的条件变量，则当进程执行x.wait()时所执行的工作是阻塞该进程，并将之插入x的阻塞队列中。
• 硬件方法swap和TestAndSet指令不能实现让权等待，Peterson算法满足有限等待（也即不能进入临界区的执行态进程可以不用立即放弃CPU）但不满足让权等待，记录型信号量由于引入阻塞机制，消除了不让权等待的情况。
• 大题11-27没看

1. 死锁

【基础知识】

• 死锁：多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。
• 原因：系统资源的竞争、进程推进顺序非法
• 死锁产生的必要条件：
  • 互斥条件
  • 不剥夺条件（获得资源只能自己释放）
  • 请求并保持条件（一次性分配策略）
  • 循环等待条件（资源有序分配策略）
• 死锁的处理策略：死锁预防、避免死锁、死锁的检测和解除
  • 死锁预防：破坏死锁必要条件（可以确保不发生死锁）
  • 死锁避免：防止进入不安全状态
    • 系统安全状态：找安全序列
    • 银行家算法
      • 两个判断：最大声明、剩余资源
      • 假设给它还安全吗？安全性分析，能找到安全序列就分配，不安全就不分配
  • 死锁检测和解除
    • 资源分配图化简
    • 死锁定理
    • 死锁解除：资源剥夺法、撤退进程法、进程回退法
  • 从上到下，从严到宽，并发性从小到大

【错题整理】

• 不死锁至少需要有一个进程的资源能足够，n个进程，每个需要m个资源，共需要n*m+1
• 死锁状态一定是不安全状态
• 分配策略：静态分配、按序分配、银行家算法

第3章 内存管理

1. 内存管理概念

【基础知识】

• 内存管理的主要功能：
  • 内存空间的分配和回收
  • 地址转换：逻辑地址转为相应的物理地址
  • 内存空间的扩充：虚拟存储技术/自动覆盖技术
  • 内存共享：允许多个进程访问内存的统一部分
  • 存储保护：保证各道作业在各自的存储空间运行，互不干扰。
• 程序的链接与装入
  • 编译 ➡️ 链接 ➡️ 装入
  • 链接：静态链接、装入时动态链接、运行时动态链接
  • 装入：绝对装入、可重定位装入（静态重定位）、动态运行时装入（动态重定位）
• 逻辑地址与物理地址
  • 逻辑地址空间：链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。（链接过程形成）
  • 物理地址空间：内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。
• 进程的内存映像
  • 要素：代码段、数据段、进程控制块PCB、堆、栈
• 内存保护
  • 方法一：在CPU中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界
  • 方法二：采用重定位寄存器（又称基地址寄存器）和界地址寄存器（又称限长寄存器）来实现这种保护。
• 内存共享
  • 可重入代码/纯代码：允许多个进程同时访问但不允许被任何进程修改的代码。
• 内存分配与回收：页式存储管理
• 连续分配管理方式
  • 单一连续分配：系统区和用户区；简单、无外部碎片、无需内存保护；只能单用户、单人物操作系统，存储利用率极低。
  • 固定分区分配：最简单的多道程序存储管理方式。分区大小可等可不等。放不进去要覆盖技术，太小也要占一个浪费空间（内部碎片），存储空间利用率低。
  • 动态分区分配/可变分区分配：分区大小数目可变。紧凑技术整理内部碎片。
    • 首次适应：地址递增排序顺序查找，满足要求的第一个空闲分区分配给作业。（最简单、最好最快，开销大）
    • 邻近适应/循环首次适应：分配内存从上次查找结束时的位置开始继续查找。（产生小碎片）
    • 最佳适应：空闲分区容量递增排序，找到满足要求且最小的空闲分区分配给作业。（性能差，产生最多外部碎片）
    • 最坏适应：容量递减排序找到最大的能满足要求的分区，从中分割一部分给作业。
• 基本分页存储管理
  • 分页思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。
  • 进程中的块：页/页面；内存中的块：页框/页帧；外存中的块：块/盘块。
  • 逻辑地址：前一部分为页号P（0-11位），后一部分为页内偏移量W（12-31位）
  • 页表记录页面在内存中对应的物理块号，页表一般存放在内存中。
  • 基本地址变化机构：页表寄存器
    • 页面大小L，逻辑地址A，物理地址E
    • 页号P=A/L，页内偏移量W=A%L
    • 比较页号P和页表长度M，P大于等于M越界中断
    • P对应页表项地址=页表始址F+页号P*页表项长度，取出表项内容b即物理块号
    • E = b * L + W
  • 快表（相联存储器TLB）加速，主存中页表称为慢表。
• 基本分段存储管理
  • 地址空间段内要求连续，段间不要求连续
  • 方便编程、分段共享、分段保护、动态链接、动态增长
  • 逻辑地址：段号S和段内偏移量W两部分组成。
  • 段表：段号+段长+本段在主存的始址
  • 地址变换机构：段表寄存器
    • 段号S大于等于段表长度M，越界中断
    • 段表项地址 = 段表始址F + 段号S * 段表项长度；偏移量大于等于段长C则越界中断
    • 始址b，段内偏移量W，E = b + W
• 段页式管理：段号、页号、页内偏移量

【错题整理】

• 段页式存储管理中，地址映射表是每个进程一张段表，每个段一张页表。
• 静态装入是编程时就把物理地址计算好/装配程序完成，动态重定位是在执行过程。
• 分页式有内部碎片，动态分区/分段式有外部碎片，固定式/段页式都有内部碎片。
• 对重定位存储管理方式，应该在整个系统中设置一个重定位寄存器。
• 分段是在编程时决定的。
• 分段存储管理方法有利于程序的动态链接。
• 可重入程序是通过减少对换数量方法来改善系统性能的。
• 分区存储管理代价最小。
• 分页存储管理方式提供一维地址结构。
• 大题6-12没看

1. 虚拟内存管理

• 对于顺序执行程序，缺页中断次数=访问的页帧数（类似于页数？）
• 虚拟内存特征：多次性、对换性、离散性
• 无论采用什么页面置换算法，每种页面第一次访问不可能在内存中，必然发生缺页，所以缺页次数大于等于页号数。
• 虚拟存储器的最大容量是由计算机的地址结构决定的，虚拟地址空间是2的位数次方，但是虚拟内存的实际容量是外存+内存。只能基于非连续分配技术。
• LRU置换算法：需要排序，最接近OPT
• 修改位和访问位供置换算法参考
• CPU利用率低但是用于交换的磁盘利用率高，说明物理内存严重短缺。
• 固定分配不能全局置换
• 缺页异常需要从硬盘中调页到内存中，将新调入的页与页框建立对应关系，并修改该页的存在位。
• 页缓冲队列长度不影响缺页率
• 算列表级数：（用到的位数-偏移量）/ 单个的项数
• 页面大小->页内偏移；页号剩余高位；

第4章 文件管理

1. 文件系统基础

• 文件系统在创建一个文件时，为它建立一个文件目录项
• 打开文件操作的主要工作是将该文件的FCB存入内存的活跃文件目录表，也就是把指定文件的目录项复制到内存指定的区域。
• FCB即文件目录项包括文件基本信息、存取控制信息、使用信息组成。不包括物理位置。
• 系统级安全管理包括注册和登录。用户注册登录是系统级安全管理。
• 文件的逻辑结构是为了方便用户设计的。
• 使用索引，采用索引顺序文件时，最好情况是有记录条数的平方根组。如10000条分成100组，每组100条记录，查找100组需要（1+100）/2=50.5次，组内查找平均需要（1+100）/2=50.5次，所以总共需要101次。
• 在磁盘上，最易导致存储碎片发生的物理文件结构是顺序存放。（外部碎片）
• 索引文件中，每个表项中含有相应记录的关键字和逻辑地址
• 一个文件首次打开操作系统需要将文件控制块读到内存中。

1. 目录

• 文件系统采用多级目录结构的目的是解决命名冲突。
• 符号链接引用计数值直接复制；硬链接+1；删除的时候符号直接删，硬-1，值不为0不能删
• 硬链接就是索引结点链接，一个文件一个索引结点，不同进程打开同文件指针位置不同。

1. 文件系统

• 位示图方法是空闲块管理方法，用于管理磁盘空间。
• 文件存储空间管理实质上是对外存空闲区的管理。
• 位示图位置确定：块号在二维数组找位置，记得检查从0还是从1开始
• 为了实现VFS，Linux主要抽象了四种对象类型：
  • 超级快对象
  • 索引结点对象
  • 目录项对象
  • 文件对象

第5章 输入/输出（I/O）管理

1. I/O管理概述

• 虚拟设备是指采用虚拟技术将一台独占设备转换为若干逻辑设备。引入虚拟设备是为了克服独占设备速度慢、利用率低的特点。
• DMA方式主要用于块设备，而I/O是典型的块设备，在I/O设备和主存之间建立一条数据通路不经过CPU。
• 为了便于上层软件的编制，设备控制器通常需要提供控制寄存器、状态寄存器和控制命令。
• 在设备控制器中用于实现设备控制功能的是I/O逻辑。
• DMA控制器中包括命令/状态寄存器，内存地址寄存器，数据寄存器。跟堆栈指针没关系。
• 字节多路通道用作连接大量的低速或中速I/O设备。
• 通道 控制 设备控制器，设备控制器 控制 设备工作，通道是硬件。
• I/O中断是CPU与通道协调工作的一种手段，所以在通道完成通道程序的执行时，便要产生中断。
• 将系统调用参数翻译成设备操作命令的工作由设备无关的操作系统软件完成。
• I/O软件四层：用户层、设备无关软件层、设备驱动程序、中断处理程序。因此用户发出I/O请求后，正确处理流程是用户程序 ➡️ 系统调用处理程序 ➡️ 设备驱动程序 ➡️ 中断处理程序。

1. 设备独立性软件

• 为了使并发进程能有效地进行输入和输出，最好采用缓冲池结构的缓冲技术。缓冲技术中的缓冲池在主存中。
• 单缓冲区传数据：总时间 = max(传入缓冲区时间，CPU处理时间）+ 缓冲到用户区时间
• 双缓冲区传数据：总时间 = max(传入缓冲区时间，CPU处理时间)
• 缓冲区解决I/O速度比CPU慢造成的矛盾，如果I/O本身就快缓冲区没必要设计。
• 设备的分配方式：独享分配、共享分配、虚拟分配
• SPOOLing技术是操作系统中采用的一种将独占设备改造为共享设备的技术，提高独占设备的利用率，通过这种技术处理后的设备称为虚拟设备。
  • 输入井和输出井是磁盘固定区域，用于暂存数据缓和CPU
  • SPOOLing技术需要磁盘空间（输入井和输出井）、内存空间（输入/输出缓冲区）
  • 不需要外围计算机，由预输入程序、井管理程序和缓输出程序。
  • 用空间换时间的技术，独占静态分配，共享动态分配
  • 程序员利用系统调用打开I/O设备时，通常使用的设备标识是逻辑设备名；而程序实际执行时使用物理设备名，它们之间的转换是由设备无关软件层完成的。
  • 输入井和输出井是系统实现的，跟用户作业没关系
• 读写设备操作是由设备驱动程序控制完成的

1. 磁盘和固态硬盘

• 磁盘上的文件以块为单位读写
• 硬盘的操作系统引导扇区产生在对硬盘进行高级格式化时
• 先来先服务可能会随时改变磁头的运动方向
• 固态硬盘基于闪存技术，没有机械部件，速度明显高于磁盘，随机写比较慢只是相对读而言，仍然比常规硬盘快的，容易磨损。
• 固态硬盘的静态磨损均衡算法比动态磨损均衡算法的表现更优秀。
• SCAN电梯调度算法：往一头走到底，再往另一个方向走
• 低级格式化：分扇区；逻辑格式化：创建文件系统
• 以簇为单位进行空间分配，进一