操作系统概述
OS 是管理硬件资源、提供用户接口、协调多任务的核心系统软件。
功能与特征
- 四大功能：处理机管理、存储器管理、设备管理、文件管理
- 两大接口：命令接口（联机/脱机）、程序接口（系统调用）
- 四大特征：并发、共享、虚拟、异步
- 并发与并行的区别：宏观同时 vs 微观同时
发展与运行环境
- 发展：手工→批处理→分时→实时→网络/分布式
- 内核态/用户态：特权指令只能在核心态执行
- 中断与异常：内中断（异常）vs 外中断（中断）
- 系统调用：用户程序请求内核服务的唯一途径
体系结构
- 大内核：Linux、Unix，性能高但内核庞大
- 微内核：Windows NT 部分设计，模块化、可靠性高
- 宏内核/微内核/混合内核对比是常考点
【选择题】操作系统的主要特征包括？
答案：并发、共享、虚拟、异步。其中并发与共享是最基本特征，虚拟与异步由前两者派生。
【选择题】用户程序请求操作系统服务需要用到？
答案：系统调用。系统调用是用户态进入内核态、请求内核服务的程序接口。
【概念题】中断和异常有什么区别？
答案：异常（内中断）由 CPU 执行指令时内部事件引起（如缺页、除零）；中断（外中断）由外部设备等异步事件引起（如 I/O 完成、时钟）。
进程与线程
进程是资源分配单位，线程是 CPU 调度单位；同步互斥与死锁是重头戏。
进程基础
- PCB（进程控制块）是进程存在的唯一标志
- 三态模型：运行、就绪、阻塞；挂起/唤醒
- 进程创建、终止、阻塞、唤醒原语
- 线程：同一进程内线程共享地址空间与资源
- 进程与线程对比：资源分配 vs 调度单位
处理机调度
- 调度层次：高级（作业）、中级（内存）、低级（进程）
- FCFS：先来先服务，利于长作业
- SJF/SPF：短作业优先，平均等待最短，可能饥饿
- 优先级调度、时间片轮转 RR、多级反馈队列
同步与互斥
- 临界资源、临界区；同步（前驱关系）vs 互斥（竞争）
- 信号量机制：P（wait）减一、V（signal）加一，整型/记录型
- 经典问题：生产者-消费者、读者-写者、哲学家进餐
- 管程：封装共享资源，条件变量
死锁
- 必要条件：互斥、占有并等待、不可剥夺、循环等待
- 预防：破坏必要条件之一（如一次性申请所有资源）
- 避免：银行家算法（安全性检查）
- 检测与解除：资源分配图、剥夺/回滚/终止进程
【选择题】进程和线程的关系，下列说法正确的是？
答案：进程是资源分配的基本单位，线程是处理机调度的基本单位。同一进程的多线程共享进程资源，线程切换开销小于进程切换。
【选择题】产生死锁的四个必要条件是？
答案：互斥、占有并等待、不可剥夺、循环等待。四个条件必须同时满足才可能死锁。
【概念题】记录型信号量中 wait(S) 操作的过程是什么？
答案：S.value--；若 S.value<0 则进程阻塞并加入 S 的等待队列；signal 时 S.value++，若 ≤0 则唤醒队首进程。
内存管理
从连续分配到分页分段，再到虚拟内存与页面置换算法。
连续分配与覆盖交换
- 单一连续、固定分区、动态分区分配
- 动态分区算法：首次适应、最佳适应、最坏适应、邻近适应
- 外部碎片与紧凑（拼接）；内部碎片
- 覆盖技术与交换技术（对换）
分页与分段
- 基本分页：固定大小页框，逻辑地址 = 页号 + 页内偏移
- 页表：页号→页框号映射；两级/多级页表
- 基本分段：按逻辑意义分段，段表 + 段内偏移
- 分页无外部碎片有内部碎片；分段相反
- 段页式：先段后页
虚拟内存
- 局部性原理：时间局部性、空间局部性
- 请求分页：缺页中断、页面置换
- 地址变换：快表 TLB 加速查找
- 有效访问时间与缺页率的关系
页面置换算法
- OPT：最佳置换（理论，淘汰未来最久不用）
- FIFO：先进先出，可能 Belady 异常
- LRU：最近最久未使用（栈实现），性能好开销大
- CLOCK（时钟/二次机会）：近似 LRU，访问位标记
【计算题】某系统采用请求分页，缺页时需 100ns 处理，内存访问 10ns，缺页率 0.1，求有效访问时间。
答案：EAT = (1−p)×10 + p×(100+10) ≈ 10 + 0.1×100 = 20ns。按公式 EAT=(1−p)·t_m + p·t_缺页计算。
【选择题】可能发生 Belady 异常的页面置换算法是？
答案：FIFO。增加物理块数反而使缺页次数增加的异常现象只出现在 FIFO 等非栈式算法中，LRU/OPT 为栈式算法不会出现。
【概念题】虚拟存储器实现的理论基础是什么？
答案：局部性原理。程序运行具有时间与空间局部性，只需调入正在使用的部分页面即可运行，配合请求调入与置换实现大地址空间。
文件管理
文件逻辑结构、物理分配、目录结构、磁盘调度与文件系统。
文件与目录
- 文件属性：名称、类型、大小、权限、时间
- 逻辑结构：顺序文件、索引文件、索引顺序文件
- 目录结构：单级、两级、树形（当前主流）
- 文件控制块 FCB 与索引结点 i-node
- 文件共享：硬链接、软链接（符号链接）
物理分配方式
- 连续分配：顺序存取快，有外部碎片、不易扩展
- 链接分配：隐式链接（FAT 表）/ 显式链接
- 索引分配：索引块指向数据块，支持随机存取
- 多级索引、混合索引（Unix 的 direct+间接）
- 文件存储空间管理：空闲表、空闲链表、位示图、成组链接
磁盘管理
- 磁盘结构：磁道、扇区、柱面；磁盘访问时间 = 寻道+旋转+传输
- 调度算法：FCFS、SSTF（最短寻道）、SCAN（电梯）、C-SCAN
- 磁盘格式化与坏块处理
【选择题】适合随机存取且便于文件动态扩展的物理分配方式是？
答案：索引分配。索引块集中管理数据块地址，随机存取 O(1) 定位，扩展只需增加索引项。
【概念题】磁盘访问时间由哪三部分组成？
答案：寻道时间、旋转延迟时间、传输时间。三者之和为总访问时间，其中寻道时间占比通常最大。
【选择题】SCAN（电梯）调度算法的特点是？
答案：磁头沿一个方向移动并服务途经请求，到边界后反向。类似电梯运行，兼顾公平与效率。
输入输出管理
I/O 控制方式、缓冲、设备分配与 SPOOLing 技术。
I/O 设备与控制方式
- 设备分类：块设备（磁盘）、字符设备（键盘）、网络设备
- 程序直接控制：轮询，CPU 忙等
- 中断驱动：CPU 等待中断，改进轮询
- DMA：数据块直接在主存与设备间传送
- 通道：独立执行 I/O 指令的处理机
缓冲技术
- 作用：缓和 CPU 与 I/O 速度不匹配、减少中断次数、提高并行性
- 单缓冲、双缓冲、循环缓冲、缓冲池
- 缓冲区数据传送时间计算是常考点
设备分配与 SPOOLing
- 设备独立性：逻辑设备名映射到物理设备
- 设备分配数据结构：DCT、COCT、CHCT、SDT
- SPOOLing（假脱机）：输入井/输出井 + 缓冲 + 调度程序
- SPOOLing 将独占设备改造为共享设备（如共享打印机）
【选择题】DMA 方式与中断方式相比，主要优点是？
答案：数据传送不需要 CPU 逐字干预。DMA 控制器直接完成主存与设备间的成块数据传送，仅在开始/结束时打断 CPU。
【概念题】SPOOLing 技术如何将独占设备变为共享设备？
答案：利用输入井/输出井在磁盘上暂存数据，通过调度程序排队处理，多个进程可同时提交 I/O 请求，从而逻辑上共享独占设备。
【选择题】缓冲技术的主要作用不包括？
答案：增大磁盘容量（错误选项）。缓冲用于缓和速度不匹配、减少中断次数、提高并行性，与存储容量无关。