操作系统引论
操作系统的发展过程
多道批处理系统
多道批处理系统的设计思想？
答：多道批处理系统的设计思想是通过合理调度作业、有效管理内存、处理I/O操作等手段，在一个时间段内尽可能多地利用系统资源，从而提高整体计算效率（提高CPU利用率）
操作系统的基本特性（重点）
操作系统的4个基本特性
答：****并发、共享、虚拟和异步
并发和并行
什么是并发和并行？
答：****并发是指两个或多个事件在同一时间间隔内发生。并行是指两个或多个事件在同一时刻发生。
**在多道程序环境下，****并发**是指在一段时间内宏观上有多个程序在同时运行；但在单处理机系统中，每一时刻仅能有一道程序执行，故在微观上这些程序只能分时交替执行。
什么是进程？什么是线程？
**答：进程是指在系统中能独立运行并能作为资源分配对象的基本单位。****线程是CPU调度**的基本单位。
什么是临界资源？
答：在一段时间内只允许一个进程访问的资源，称为临界资源（或独占资源）。
操作系统的运行环境
操作系统内核
操作系统内核的功能
答：****支撑功能和资源管理功能
- 支撑功能
三种最基本的支撑功能
答：****中断处理、时钟管理和原语操作
- 资源管理
**答：**进程管理，存储器管理，设备管理
进程的描述与控制
前驱图和程序执行
程序顺序执行
程序顺序执行的特征
答：顺序性、封闭性、可再现性
程序并发执行
程序并发执行的特性
答：间断性、失去封闭性、不可再现性。
进程的描述
进程的定义与特征
进程的定义
答：传统OS中的进程定义为：“进程是程序的执行过程，是系统进行资源分配和调度的一个独立单元”。
进程的特征
答：动态性、并发性、独立性、异步性
进程的基本状态与转换
进程管理中的数据结构
PCB的作用
答：PCB的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，即一个能与其他进程并发执行的进程。
- 作为独立运行基本单位的标志
- 实现间断性运行方式
- 提供进程管理所需要的信息
- 提供进程调度所需要的信息
- 实现与其他进程的同步与通信
线程的概念
线程与进程的区别（重点）
**答：**在定义层面上，进程是资源分配的基本单位，而线程是CPU调度和执行的基本单位；在资源分配方面，每个进程有自己独立的地址空间和资源，而线程共享所属进程的资源，包括内存地址空间；在调度和执行方面，进程切换开销大，线程切换开销小；并发性方面，不同进程间可以并发执行，当然线程也可以实现并发执行，在同一个进程中的多个线程之间可更高效地共享数据。
处理机调度与死锁
处理机调度概述
处理机调度的层次
**高级调度：**将外存处于后备队列中的作业调入内存。
低级调度（进程调度、短程调度）：将内存就绪队列的进程调入处理机。
**中级调度****：**将内存中暂时不能运行的进程调入外存等待。
调度算法
先来先服务调度算法FCFS
什么是FCFS算法？
答：FCFS在每一次调度时会从就绪队列中选一个最先进入队列的进程分配给处理机
短作业优先调度算法SJF
什么是短作业优先调度算法？
答：SJF调度算法是根据作业的长短来计算优先级，作业越短，优先级越高。（与运行时间有关）
优先级调度算法
高响应比优先调度算法HRRN
HRRN调度算法既考虑了作业的等待时间，又考虑了作业的运行时间，因此既照顾了短作业，又不会使长作业等待的时间过长。从而改善了处理机调度的性能
轮转调度算法RR
- RR调度算法的基本原理
在RR调度算法中，系统会将所有的就绪进程按FCFS策略排成一个就绪队列。系统可以设置每隔一段时间执行一个时间片。
多级反馈队列调度算法
不必事先知道各个进程所需的执行时间，是目前公认较好的进程调度算法。
死锁概述
计算机系统中的死锁
引起死锁的3个原因
答：竞争不可抢占资源引起死锁，竞争可消耗资源引起死锁，进程推进顺序不当引起死锁。
死锁的定义，必要条件与处理方法
- 死锁的定义
答：如果一组进程中的每个进程都在等待仅由该组进程中的其他进程才能引发的事件发生，那么该组进程是**死锁**的。
- 死锁产生的必要条件
死锁产生的4个必要条件
答：****互斥条件，请求和保持条件，不可抢占条件，循环等待条件
死锁预防
死锁预防的方法
答：破坏“请求和保持条件”，破坏“不可抢占”条件，****破坏“循环等待”条件
死锁避免
系统安全状态
在避免死锁的方法中，把系统状态分为安全状态和不安全状态两种。当系统处于**安全状态时可避免发生死锁，而当系统处于不安全状态时，则可能**会进入死锁状态。
避免死锁的实质在于，使系统在进行资源分配时进入不安全状态
利用银行家算法避免死锁（重点）
进程同步（重点）
进程同步的基本概念（重点）
进程同步概念的引入
什么是进程同步？
答：我们把**异步环境下的一组并发进程因直接制约而互相发送消息、互相合作、互相等待，使得各进程按一定的速度执行的过程，称为进程同步****。**
临界区问题
什么是临界区？
答：每个进程中访问资源的那段代码称为临界区。
解决临界区问题的同步机制的4条准则（重点）
答：****空闲让进、忙则等待、有限等待、让权等待
管程机制
什么是管程？为什么要有管程？
答：管程是OS的一个资源管理模块，对共享数据结构实施操作的一组过程组成的资源管理程序。通俗的讲，就是为了方便管理进程的同步操作wait和siginal而产生的一种进程同步工具，防止因同步操作不当导致系统死锁。
经典的进程同步问题
生产者——消费者问题
可以通过信号量机制或管程机制解决
存储器管理
程序的装入与链接
程序的装入
程序装入的三种方式
答：绝对装入方式，可重定位转入方式，动态运行时装入方式。
程序的链接
程序链接的三种方式
答：静态链接，装入时动态链接，运行时动态链接。
连续分配存储管理方式
动态分区分配
动态分区分配算法
- 基于顺序搜索的动态分区分配算法（顺序分配算法）
- 首次适应算法
- 循环首次适应算法
- 最佳适应算法
- 最坏适应算法
- 基于索引搜索的动态分区分配算法（索引分配算法）
- 快速适应算法
- 伙伴算法
- 哈希算法
动态重定位分区分配
什么是紧凑？
答：通过移动内存中作业的位置，把原来分散的多个小分区拼接成一个大分区的方法，称为“紧凑”，亦称**“紧缩”或“拼接”****。**
分页存储管理方式
分页存储管理是一种将内存空间和程序的逻辑空间划分为固定大小页面的存储管理方式。在这种方式下，内存被划分成多个大小相等的物理页面（也称为页框），程序的逻辑地址空间被划分为大小相同的页面。
- 逻辑结构与物理地址的转换
- 地址结构：逻辑地址由两部分组成，即页号和页内偏移量。
- 页表的作用：系统通过页表来实现逻辑地址到物理地址的转换。
- 快表（TLB）：为了提高地址转换的速度，许多系统采用了快表。
分段存储管理方式
分段存储管理方式是将用户程序的地址空间划分为若干个大小不等的段。每个段都有一个段名（在程序中用段名来访问相应的段）和段长，并且是一个独立的逻辑单位，通常具有完整的逻辑意义。
- 逻辑地址与物理地址的转换
- 地址结构：逻辑地址由段号和段内偏移量两部分组成。
- 段表的作用：系统通过段表来实现逻辑地址到物理地址的转换。
分页和分段的区别（重点）
分页和分段的主要区别
- 页是信息的物理单元：分页是系统管理上的需要，完全是系统行为，对用户不可见。分段管理的段是逻辑单位，分段的目的是为了满足用户需要。
- 页的大小固定且由系统决定：页的管理方式是由硬件实现的，每个系统只能有一种大小的页面。而段长度不固定，其取决于用户所编写的程序。
- 分页的用户程序地址空间是一维的：分页是系统行为，用户程序的地址属于单一的线性地址空间，程序员仅用一个标识位即可表示一个地址。而分段是用户行为，用户程序的地址空间是二维的，程序员在标记一个地址时，要给出段名和段内地址。
虚拟存储器
虚拟存储器概述
常规存储器管理方式的特征和局部性原理
局部性原理
- 程序在执行时，除少部分的转移和过程调用指令外，在大多数情况下是顺序执行。
- 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域
- 程序中存在许多循环结构，这些结构虽然只由少数指令构成，但是它们将会多次执行。
- 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。
虚拟存储器的定义与特征
虚拟存储器的定义
答：****虚拟存储器是一种逻辑上扩充内存容量的存储器系统。它为程序员提供了一个比实际物理内存空间大得多的虚拟地址空间。
虚拟存储器的特征
答：****多次性，对换性，虚拟性
请求分页存储管理方式
请求分页中的硬件支持
什么是缺页中断？
答：在请求分页系统中，每当所要访问的页面不在内存中，便可产生一个缺页中断，请求OS将缺页调入内存。
页面置换算法
什么是抖动？
答：抖动就是刚换出的页，很快又要被访问，因此需要将它重新调入，以致一个进程在运行中吧大多数时间花在页面置换工作上。像这样称为进程发生了抖动。
最佳页面置换算法和先进先出页面置换算法
- 最佳页面置换算法OPT
最佳页面置换算法是理论上的算法。选择淘汰的页面是以后永不使用或在将来最长时间内不会被访问的页面。最佳页面置换算法通常可以保证最低缺页率。”向后看“
- 先进先出页面置换算法FIFO（重点）
FIFO算法总会淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
最近最久未使用页面置换算法和最少使用页面置换算法（硬件）
- 最近最久未使用页面置换算法LRU（重点）
LRU页面置换算法会选择最近最久未使用的页面予以淘汰，“向前看”
- 最少使用页面置换算法LFU
在采用最少使用LFU页面置换算法时，应为内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该页面置换算法会将最近时期使用最少的页面作为淘汰页。
例题：
“抖动”与工作集
产生“抖动”的原因
答：产生抖动的原因是，同时在系统中运行的进程太多，导致分配给每个进程的物理块太少，不能满足进程正常运行的基本需求，致使每个进程在运行时会频繁地出现缺页，必须请求系统将所缺之页调入内存。
输入/输出系统
I/O系统的基本功能、模型与接口
I/O系统的层次结构
I/O系统的结构层次
答：****4个结构层次。用户层软件、与设备无关的I/O软件、设备驱动软件、中断处理软件。
I/O设备和设备控制器
设备控制器
设备控制器的主要功能
答：控制**一个或多个I/O设备****，以实现I/O设备和计算机之间的数据交换。**
设备控制器的分类
答：可以把设备控制器分为两类。一类是**用于控制字符设备的控制器，另一类是用于控制块设备的控制器****。**
I/O设备的控制方式（重点）
- 使用轮询的可编程I/O方式
可编程 I/O（PIO - Programmed I/O）是一种数据传输方式，其中轮询是其主要的控制手段。在这种方式下，CPU 需要不断地查询设备的状态寄存器，以确定设备是否准备好进行数据传输。
- 使用中断的可编程I/O方式
使用中断的可编程 I/O 方式是一种高效的数据传输机制。在这种方式下，外部设备在准备好进行数据传输（如数据输入时设备已获取数据，或数据输出时设备已准备好接收数据）时，会主动向 CPU 发送一个中断请求信号。
- 直接存储DMA方式
直接存储器访问（DMA - Direct Memory Access）是一种在计算机系统中用于快速数据传输的技术。它允许外部设备（如磁盘驱动器、网卡等）直接与内存进行数据交换，而无需 CPU 的过多干预。
- I/O通道方式
I/O 通道方式是一种比 DMA（直接内存访问）方式更高级的 I/O 控制方式。它可以使 CPU、通道和 I/O 设备并行操作，从而更有效地提高整个系统的资源利用率和运行速度。通道是一个独立于 CPU 的专管输入 / 输出控制的处理机，它控制设备与内存直接进行数据交换。
中断和中断处理程序
中断简介
中断的类型
答：中断可以分为**硬件中断和软件中断两大类。硬件中断又分为外部硬件中断和内部硬件中断；软件中断分为系统调用中断和程序性异常中断****。**
什么是中断向量表？
答：中断向量表（Interrupt Vector Table）是一个存储中断向量的数据结构。中断向量是指向中断处理程序入口地址的指针（在一些简单的系统中可能还包括一些相关的中断处理参数）。它就像是一个 “索引目录”，当一个中断发生时，CPU 可以通过查找这个表来确定应该跳转到哪个中断处理程序去执行，以响应相应的中断事件。
与设备无关的I/O软件
与设备无关软件的作用
答：提供设备驱动程序的统一接口，缓冲管理，差错控制，独占设备的分配和回收，提供独立于设备的逻辑数据块。
设备分配与回收
- 设备分配中的数据结构
- 设备控制表
- 控制器控制表
- 通道控制表
- 系统控制表
用户层的I/O软件
假脱机系统SPOOLing
假脱机系统的组成
答：****输入井和输出井，输入缓冲区和输出缓存区，输入进程和输出进程，井管理程序。
磁盘性能概述和磁盘调度
磁盘性能概述
- 磁盘的访问时间
- 寻道时间T_s_：指把磁臂（磁头）移动到指定磁道上的时间，该时间是启动磁臂的时间k与移动n条磁道所花费的时间之和，即T_s = m × n + k_
早期磁盘调度算法
- FCFS调度算法
根据进程请求访问磁盘的先后顺序进行调度
- SSTF调度算法（优先级调度）
根据要求访问的磁道与当前磁头所在的磁道距离进行调度，优先调度磁头距离磁道最近的进程。
基于扫描的磁盘调度算法
- SCAN调度算法
SCAN算法是对SSTF调度算法的优化，可防止低优先级出现饥饿现象。SCAN调度算法不仅会考虑欲访问的磁道与当前磁道间的距离，还会优先考虑磁头当前的移动方向。
- CSCAN调度算法
CSCAN调度算法是对SCAN算法的优化，防止因磁头由里向外移动越过某一磁道后，恰好又有一道进程访问此磁道造成的进程等待。CSCAN调度算法规定磁头单向移动，如只是自里向外移动，当磁头移动到最外层时，磁头立即返回最里面的磁道。
- NStepSCAN调度算法和FSCAN调度算法
- **NStepSCAN调度算法：**这个算法是为了防止进程对某一磁道的“垄断”现象。n步SCAN算法是将磁盘的请求分为N个子序列，磁盘调度按FCFS调度算法处理子队列。每一个子队列又采用SCAN调度算法。当N=1时，NStepSCAN调度算法退化成了FCFS调度算法。
- FSCAN调度算法：FSCAN调度算法是对NStepSCAN的简化，即FSCAN调度算法只将磁盘请求队列分为两个子队列。
文件管理
文件和文件管理系统
文件操作
什么是文件的打开和关闭操作
答：打开是指系统指定文件的属性，从外存复制到内存的打开文件表的一个目录中，并将该表目的编号（索引号）发给用户。关闭是指系统调用关闭此文件之后，OS将此文件从打开表中的表目上删除。
文件的逻辑结构
- 文件的逻辑结构：指从用户角度出发所观察到的文件组织形式，即文件是一系列逻辑记录所组成的。
- 文件的物理结构：又称文件的存储结构，是指系统将文件存储在外存上形成的一种存储组织形式。
有结构文件的逻辑结构（分类）
答：****顺序文件，索引文件，索引顺序文件
文件目录
文件目录的作用
答：****（1）实现文件的“按名存取”（2）提高目录的检索速度（3）文件共享（4）允许文件重名
文件控制块和索引节点
- 文件控制块FCB
文件控制块就是一个文件目录项。通常一个文件目录也被看做一个文件，称为目录文件。
- FCB中包含的三类信息：基本信息类，存取控制信息类，使用信息类
- 索引节点
主要用于记录除文件名之外的文件所有信息
- 索引节点包括磁盘索引节点和内存索引节点
文件保护
文件保护的目的
答：防止人为因素导致文件不安全，如数据泄露；防止系统某部分的故障导致文件文件不安全；防止自然因素导致文件的不安全。
磁盘存储器管理
外存的组织方式（重点）
外存的3种组织方式
答：****连续组织方式，链接组织方式，索引组织方式
连续组织方式
连续组织方式的优点
答：顺序访问容易，顺序访问速度快
连续组织方式的缺点
答：会产生许多外部碎片；必须事先知道文件的长度；不能灵活地删除和插入记录；对于动态增长的文件，很难分配空间。
链式存储方式
链式存储方式的优点
答：消除了外部碎片提高了外存利用率；非常容易插入、删除和修改记录；能适应文件的动态增长，无需知道文件的大小。
链式存储方式的缺点
答：存储密度较低；不便于随机访问；遍历效率相对较低
索引组织方式
- 单级索引组织方式
单级索引组织方式的优点
答：支持直接访问，不会产生外部碎片，处理大文件比链式组织方式好
单级索引组织方式的缺点
答：每建立一个索引文件都需要分配一个索引块，针对中小型文件时，索引块的利用率会很低。
- 多级索引组织文件
多级索引组织文件的优点
答：大大加快了系统对大型文件的查找速度。
多级索引组织文件的缺点
答：系统在访问一个盘块时，所需启动磁盘的次数会随着索引级数的增加而增多。
- 增量式索引组织方式
增量式索引组织方式的优点
答：能较为全面的照顾到大中小作业，可以采用多种组织方式来构成文件的物理结构。
增量式索引组织方式的缺点
答：索引更新复杂，索引碎片问题，数据与索引的一致性问题。
文件存储空间的管理
位示图法
位示图法是一种用于磁盘空间管理的方法。它使用一个二进制位（bit）的矩阵（即位示图）来表示磁盘存储空间的使用情况。在这个矩阵中，每一位对应磁盘上的一个物理块。例如，如果位示图中的某一位为 0，表示对应的磁盘物理块是空闲的；如果为 1，则表示该磁盘物理块已经被分配使用。
成组链接法
成组链接法是一种用于磁盘空间管理的有效方法，主要应用在文件系统中。它将磁盘中的空闲块分组，每组的第一个空闲块中记录了下一组空闲块的信息，包括下一组空闲块的起始块号和空闲块数量。除了最后一组外，每组的空闲块数通常是固定的。例如，假设每组有 100 个空闲块，第一组的第一个空闲块（假设块号为 10）中除了自身可用外，还记录了下一组空闲块的起始块号（比如 200）和数量（100）