操作系统¶
⚙️ 计算机操作系统（详细知识点大纲）
第一章 操作系统引论¶
1.1 操作系统的目标和作用¶
- 操作系统的四个主要目标：方便性、有效性、可扩充性、开放性
- OS作为用户与计算机硬件系统之间的接口（命令、系统调用、图标窗口）
- OS作为计算机系统资源的管理者（处理机、存储器、I/O设备、文件）
- OS实现了对计算机资源的抽象
1.2 操作系统的发展过程¶
• 人工操作方式（脱机输入/输出技术） • 单道批处理系统（特征、缺点、自动装入） • 多道批处理系统（特征：多道、宏观并行、微观交替；优缺点；需要解决的问题） • 分时系统（引入原因：人机交互；关键技术：时分复用、时间片；特征：多路性、交互性、独占性、及时性） • 实时系统（应用场景；类型：周期性/非周期性、硬实时/软实时；特征：高及时性、高可靠性） • 微机操作系统（单用户单任务、单用户多任务、多用户多任务） • 嵌入式系统、网络操作系统与分布式操作系统简介 • 1.3 操作系统的基本特征 • 并发（Concurrence）：并行与并发的区别；并发的重要意义 • 共享（Sharing）：互斥共享方式（临界资源）；同时访问方式 • 并发与共享的互为存在条件关系 • 虚拟（Virtual）：时分复用技术（虚拟处理机、虚拟设备）；空分复用技术（虚拟存储器） • 异步（Asynchronism）：进程推进速度的不可预知性
1.4 操作系统的主要功能¶
• 处理机管理：进程控制、进程同步、进程通信、调度（作业/进程） • 存储器管理：内存分配与回收、内存保护、地址映射、内存扩充（虚拟存储） • 设备管理：缓冲管理、设备分配、设备处理（驱动） • 文件管理：文件存储空间管理、目录管理、文件的读/写管理和存取保护 • 操作系统与用户接口：用户接口（命令接口、图形接口）、程序接口（系统调用）
1.5 操作系统结构设计¶
• 传统结构：无结构（模块组合）、模块化结构、分层结构 • 微内核（Microkernel）结构：基本概念、核心功能（机制与策略分离）、优点与缺点
第二章 进程的描述与控制¶
2.1 前趋图和程序执行¶
• 前趋图的定义、有向无环图（DAG）表示方法 • 程序顺序执行时的特征：顺序性、封闭性、可再现性 • 程序并发执行时的特征：间断性、失去封闭性、不可再现性
2.2 进程的描述¶
• 进程的定义与特征：结构性、多个进程共存、动态性（最基本特征）、并发性、独立性、异步性 • 进程的基本状态与转换： • 三状态模型：就绪（Ready）、执行（Running）、阻塞（Blocked/Wait） • 五状态模型：增加创建（Created）、终止（Terminated） • 挂起状态（Suspend）的引入原因：终端用户需要、父进程请求、负荷调节、操作系统需要 • 带挂起状态的进程状态转换图（活动/静止就绪、活动/静止阻塞） • 进程控制块（PCB）： • PCB 的作用：进程存在的唯一标志 • PCB 中的信息：进程标识符、处理机状态、进程调度信息、进程控制信息 • PCB 的组织方式：线性表、链接方式、索引方式
2.3 进程控制¶
• 操作系统的内核：支撑功能（中断处理、时钟管理、原语操作）、资源管理功能 • 原语（Primitive）：由关中断和开中断实现，执行期间不允许被中断 • 进程的创建：创建原语的执行步骤（申请PCB、分配资源、初始化PCB、插入就绪队列） • 进程的终止：终止原语（正常/异常/外界干预）、资源回收、子进程处理 • 进程的阻塞（Block原语）与唤醒（Wakeup原语）：成对出现 • 进程的挂起（Suspend原语）与激活（Active原语）
2.4 进程同步¶
• 进程同步的基本概念：直接制约（速度协同）、间接制约（资源共享/互斥） • 临界资源与临界区：进入区、临界区、退出区、剩余区 • 同步机制应遵循的 4 条准则：空闲让进、忙则等待、有限等待、让权等待 • 硬件同步机制：关中断、Test-and-Set (TS/TSL) 指令、Swap (XCHG) 指令 • 信号量机制（Semaphore）： • 整型信号量（不满足让权等待，存在“忙等”） • 记录型信号量（包含 value 和 链表 L，解决忙等） • AND型信号量（Swait / Ssignal，针对多资源分配） • 信号量集（一般化的信号量机制） • 管程机制（Monitor）：管程的定义、条件变量、局部于管程的变量 • 2.5 经典进程同步问题（★核心重点） • 生产者-消费者问题（单生产者单消费者、多生产者多消费者、信号量死锁陷阱） • 哲学家进餐问题（死锁现象及 3 种解决方法：至多4人、同时拿两侧、奇偶编号） • 读者-写者问题（读者优先、写者优先的信号量实现） • 2.6 进程通信（IPC） • 进程通信的类型：共享存储器系统（高级/低级）、管道（Pipe）通信系统、消息传递系统、客户机-服务器系统（套接字、RPC） • 消息传递通信的实现方式：直接通信（消息队列）、间接通信（信箱） • 2.7 线程（Threads）的基本概念 • 引入线程的动机：减少并发时的时空开销（创建、撤销、切换） • 线程与进程的比较（★高频对比）：调度的基本单位、资源拥有的基本单位、并发性、系统开销、地址空间与通信 • 线程的状态：就绪、执行、阻塞 • 线程控制块（TCB）的构成 • 2.8 线程的实现 • 内核支持线程（KST）：特征、优缺点 • 用户级线程（ULT）：特征、优缺点、组合方式 • 线程互斥与同步的实现
第三章 处理机调度与死锁¶
• 3.1 处理机调度的层次和调度算法的目标 • 高级调度（作业调度）：接纳外存中的作业进入内存，创建PCB • 低级调度（进程调度）：从就绪队列中选择进程分配CPU（最频繁） • 中级调度（内存对换）：提高内存利用率和吞吐量，将暂时不能运行的进程调至外存（挂起） • 调度队列模型与调度算法共同的目标：CPU利用率、系统吞吐量、周转时间、等待时间、响应时间 • 3.2 作业与作业调度 • 作业的三个状态：收容状态、执行状态、完成状态 • 作业步（Job Step）与作业控制块（JCB） • 作业调度算法： • 先来先服务（FCFS） • 短作业优先（SJF）：对长作业不利（饥饿现象）、未考虑紧迫性 • 高响应比优先（HRRN）：响应比 (R_p = \frac{等待时间 + 要求服务时间}{要求服务时间} = 1 + \frac{等待时间}{要求服务时间}) • 3.3 进程调度 • 进程调度的机制：排队器、分派器、上下文切换器 • 进程调度方式：非抢占方式（Non-preemptive）、抢占方式（Preemptive）（抢占原则：优先权、短作业、时间片） • 进程调度算法： • 时间片轮转（RR）：时间片大小对系统性能的影响 • 优先级调度算法：静态优先级（确定依据）、动态优先级（随等待时间、执行时间改变） • 多级反馈队列（Multilevel Feedback Queue）调度算法：综合性能最好 • 3.4 死锁概述 • 死锁的定义：多个进程因竞争资源而造成的一种僵局，若无外力作用将无法向前推进 • 产生死锁的原因：竞争不可剥夺资源、进程推进顺序非法 • 死锁产生的四个必要条件：互斥条件、不可抢占条件、请求和保持条件、循环等待条件 • 处理死锁的方法：预防死锁、避免死锁、检测死锁、解除死锁 • 3.5 预防死锁（静态方法） • 破坏“请求和保持”条件：协议一（全分配法）、协议二（释放当前再申请） • 破坏“不可抢占”条件：因资源未满足而释放已占有的所有资源 • 破坏“循环等待”条件：资源顺序分配法（缺点：限制新设备增加、资源浪费） • 3.6 避免死锁（动态方法） • 系统安全状态：安全序列的定义；安全状态与死锁状态的关系 • 银行家算法（Banker's Algorithm）： • 数据结构：Available、Max、Allocation、Need • 算法步骤：Request 与 Need、Available 比较；试探性分配 • 安全性检查算法（Safety Algorithm）：寻找安全序列的过程 • 3.7 死锁的检测与解除 • 死锁检测：资源分配图（圆圈代表进程、方框代表资源）；死锁定理（简化资源分配图法） • 检测时机：每次资源请求、定时检测、CPU利用率下降时 • 死锁解除方法：资源剥夺法、撤销进程法（终止全部、逐个终止）、进程回退法
第四章 存储器管理¶
• 4.1 存储器管理概述 • 存储器的多级结构：寄存器 → 高速缓存(Cache) → 主存(内存) → 辅存(外存) • 程序的链接和装入： • 编译（Compile）、链接（Link）、装入（Load） • 链接方式：静态链接、装入时动态链接、运行时动态链接 • 装入方式：绝对装入、可重定位装入（静态重定位）、动态运行时装入（动态重定位） • 4.2 连续分配存储管理方式 • 单一连续分配（单用户、单任务系统） • 固定分区分配（分区大小相等、分区大小不等；内存分配表） • 动态分区分配（分区大小按需生成）： • 空闲分区表与空闲分区链 • 动态分区分配算法： • 首次适应（FF）：按地址递增，查找快，低地址碎片多 • 循环首次适应（NF）：从上次查找结束处开始，空闲分区分布均匀，缺乏大分区 • 最佳适应（BF）：按大小递增，找到最匹配的，产生最多外部碎片 • 最坏适应（WF）：按大小递减，总挑最大的用，缺乏大分区 • 基于顺序搜索的动态分区分配算法的缺点 • 紧凑（Compaction）技术：解决外部碎片，需要动态重定位支持 • 4.3 基本分页存储管理方式 • 分页的基本概念：页面和物理块（大小通常为2的幂）、逻辑地址结构（页号P + 页内地址W） • 页表（Page Table）：页号到物理块号的映射；页面大小与页表长度的关系 • 地址变换机构： • 基本地址变换机构：页表寄存器（PTR）、地址转换两次访存问题 • 具有快表（TLB）的地址变换机构：联想存储器（实现单次访存或大幅降低平均访存时间） • 两级和多级页表：解决页表占用连续大内存的问题；外层页表/页目录表 • 4.4 基本分段存储管理方式 • 引入目的：满足程序员在方便编程、分段共享、分段保护、动态链接、动态增长方面的需要 • 分段基本概念：段是逻辑单位、段号S + 段内地址W、二维地址空间 • 段表（Segment Table）：段号、段长、基址 • 地址变换机构：段表寄存器、越界检查（与段长比较） • 分页与分段的主要区别（★极高频）： • 页是物理单位（消碎片），段是逻辑单位（满足用户需要） • 页的大小固定由系统决定，段的长度不固定由用户程序决定 • 分页的地址空间是一维的，分段的地址空间是二维的 • 4.5 段页式存储管理方式 • 基本原理：先分段，再将段内分页 • 地址结构：段号S + 页号P + 页内位移W • 空间结构：段表、页表与物理块的对应关系 • 地址变换过程：需要三次访存（查段表、查页表、读写数据）；可利用快表优化 • 4.6 虚拟存储器的基本概念 • 传统存储管理方式的特征：一次性、驻留性（导致大作业无法运行、多道程序度低） • 局部性原理：时间局部性、空间局部性（工作集理论的基础） • 虚拟存储器的定义：具有请求调入和置换功能，能从逻辑上对内存容量进行扩充的存储器系统 • 虚拟存储器的特征：多次性、对换性、虚拟性 • 虚拟存储器的实现方式：请求分页系统、请求分段系统 • 4.7 请求分页存储管理方式 • 页表机制（请求页表）：增加 状态位P、访问位A、修改位M、外存地址 • 缺页中断机构：属于内部中断（异常/陷阱）；在一指令执行期间产生和处理；一条指令可能产生多次缺页 • 地址变换机构：增加了缺页检查、调页、页面置换步骤 • 4.8 页面置换算法（★核心计算点） • 先进先出（FIFO）：Belady异常（分配物理块增加，缺页率反而上升） • 最佳置换（OPT）：淘汰未来最长时间不用的页面（理想化算法，用于衡量其他算法） • 最近最久未使用（LRU）：淘汰过去最久未访问的页面；硬件支持（寄存器或栈） • 时钟（Clock）置换算法： • 简单Clock（使用1位访问位，循环扫描） • 改进型Clock算法：组合（访问位A，修改位M），分4种优先级淘汰，减少磁盘I/O次数 • 4.9 页面分配策略与抖动 • 驻留集大小：固定分配局部置换、可变分配全局置换、可变分配局部置换 • 调页策略：预调页策略、请求调页策略；调页来源（对换区、文件区） • “抖动”（Thrashing）现象：同时运行的进程太多，频繁发生缺页置换，导致系统吞吐量急剧下降 • 抖动产生的原因：多道程序度过高、页面分配策略不当 • 消除抖动的方法：调节多道程序度、利用工作集（Working Set）模型
第五章 保护和安全¶
• 5.1 安全与保护的基本概念 • 安全性（Security）与保护（Protection）的区别 • 威胁类型的划分：机密性、完整性、可用性、真实性 • 5.2 保护机制 • 保护域（Protection Domain）：进程、对象与权限的集合 • 访问控制矩阵（Access Control Matrix）：行表示域（Domain），列表示对象（Object） • 访问控制矩阵的实现转化： • 访问控制列表（ACL）：按列（对象）存储权限信息 • 能力表（Capability List）：按行（域/用户）存储权限信息 • 5.3 计算机网络与系统安全 • 数据加密技术：对称加密（DES/AES）、非对称加密（RSA） • 认证技术：数字签名、身份认证（密码、生物特征、动态令牌） • 防火墙（Firewall）技术：包过滤、代理服务器 • 5.4 内部与外部攻击（恶意软件） • 特洛伊木马（Trojan Horse）、计算机病毒（Virus）、计算机蠕虫（Worm） • 缓冲区溢出（Buffer Overflow）攻击原理与防范机制
第六章 输入输出系统 (I/O)¶
• 6.1 I/O 系统的组件和管理目标 • I/O 设备分类：按传输速率（低速、中速、高速）、按信息交换单位（字符设备、块设备）、按共享属性（独占、共享、虚拟） • 设备控制器（I/O Interface）：控制器的功能（命令接收、数据交换、状态说明、地址识别）、控制器的组成 • I/O 通道：引入目的（减轻CPU负担），通道指令（CCW），通道类型（字节多路、数组选择、数组多路） • 6.2 I/O 控制方式（★演进过程） • 程序I/O方式（轮询/忙等）：CPU不断测试状态位，极度浪费CPU • 中断驱动I/O方式：以字节为单位，完成时发送中断，CPU与设备并行（但中断频繁） • 直接存储器访问（DMA）方式：以数据块为单位，整块传输由DMA控制器完成，仅在开始和结束需CPU干预 • 通道控制方式：由专用通道CPU执行通道程序，控制多台设备与内存的数据交换 • 6.3 I/O 软件的层次结构 • 用户层I/O软件：实现与用户交互，提供库函数（如 printf）和SPOOLing技术 • 设备独立性软件（Device-Independent I/O Software）： • 逻辑设备与物理设备名称的映射（LUT表） • 系统调用、设备分配、设备保护、缓冲管理、差错控制 • 设备驱动程序（Device Driver）：将抽象请求转为具体命令，直接控制设备控制器 • 中断处理程序（Interrupt Handler）：处理I/O完成时的硬件中断，恢复现场，唤醒阻塞进程 • 6.4 缓冲区管理 • 引入缓冲区的目的：缓和CPU与I/O设备间速度不匹配的矛盾、减少对CPU的中断频率、提高CPU与I/O设备的并行性 • 缓冲区的形式： • 单缓冲（Single Buffer） • 双缓冲（Double Buffer）：实现双向并行传输 • 循环缓冲（Circular Buffer）：多缓冲队列 • 缓冲池（Buffer Pool）：统一管理，收容输入、提取输入、收容输出、提取输出工作缓冲区 • 6.5 设备分配 • 设备分配中的数据结构：系统设备表（SDT）、设备控制表（DCT）、控制器控制表（COCT）、通道控制表（CHCT） • 设备分配原则：充分发挥设备效率、避免死锁、实现设备独立性 • 设备分配步骤：找DCT → 找COCT → 找CHCT（完全匹配成功才分配） • 6.6 SPOOLing 技术（假脱机系统） • SPOOLing 系统的组成：输入井和输出井（外存）、输入缓冲区和输出缓冲区（内存）、输入进程和输出进程 • 核心思想：利用共享设备（通常是磁盘）来模拟独占设备（如打印机），将独占设备改造为共享设备 • SPOOLing 的特点：提高了I/O速度、将独占设备改造成共享设备、实现了虚拟设备功能
第七章 文件管理¶
• 7.1 文件和文件系统 • 文件的定义与属性（名称、类型、大小、创建时间、保护信息） • 文件系统的层次结构：对象及其属性、对对象操纵的方便接口、文件系统软件（管理机构） • 文件的操作：创建、删除、读、写、设置读写指针（Seek）、打开（Open）、关闭（Close） • “打开文件”操作的实质：将文件的属性（FCB）从外存复制到内存的“打开文件表”中，返回文件描述符/句柄 • 7.2 文件的逻辑结构 • 文件的逻辑结构分类：有结构文件（记录式文件）、无结构文件（流式文件，如字节流） • 有结构文件的类型： • 顺序文件：定长/变长、顺序存取快 • 索引文件：通过索引表解决变长记录文件的随机存取问题 • 索引顺序文件：将记录分组，建立组索引，减少索引表本身占用的空间 • 7.3 目录管理 • 文件控制块（FCB）：包含文件名、文件结构、物理位置、存取控制信息 • 索引节点（Inode）机制：将文件名与文件描述信息（Inode）分离，减少目录项所占空间，从而大幅减少查找文件时所需的磁盘I/O次数 • 目录结构： • 单级目录（重名问题、查找慢） • 二级目录（主文件目录+用户文件目录，解决重名） • 多级树形目录（路径名、当前目录/工作目录、绝对路径与相对路径） • 无环有向图目录结构（实现文件共享） • 7.4 文件共享与保护 • 文件共享实现方式： • 基于索引节点的共享（硬链接 Hard Link）：同一Inode，删除时计数减一 • 利用符号链实现共享（软链接/快捷方式 Symbolic Link）：包含目标文件路径名，删除原文件后软链接失效 • 文件保护机制：存取控制矩阵、存取控制列表（ACL）、用户分类法（Owner, Group, Others，如Linux的 rwxrwxrwx）
第八章 磁盘存储器的管理¶
• 8.1 外存分配方式（文件的物理结构 ★高频考核） • 连续分配（Sequential Allocation）： • 原理：文件存放在连续的物理块中 • 优缺点：支持顺序和随机访问，速度极快；产生外部碎片，不便于文件动态增长 • 链接分配（Linked Allocation）： • 隐式链接：每个物理块含指向下一块的指针（不支持随机访问，可靠性差） • 显式链接：指针集中存放在内存的文件分配表（FAT）中（支持随机访问，查表快） • 索引分配（Indexed Allocation）： • 原理：为每个文件分配一个索引块，记录该文件所有物理块号 • 大文件解决方案：链接索引块、多级索引（如两级索引、UNIX三级索引结构） • 8.2 文件存储空间管理（空闲块管理） • 空闲表法（连续分配使用） • 空闲链表法（空闲格子链、空闲盘块链） • 位示图法（Bitmap）：利用二进制的一位（0/1）表示盘块空闲与否（重点：行列号与盘块号的转换计算） • 成组链接法（UNIX系统采用）：将空闲块分组，每组第一块记录下一组的信息，兼顾内存开销与存取效率 • 8.3 磁盘存储器管理与调度 • 磁盘的物理结构：磁头（Heads）、柱面（Cylinder）、扇区（Sector） • 磁盘访问时间计算公式：(T_a = T_s（寻找时间） + T_r（旋转延迟时间） + T_t（传输时间）) • 磁盘调度算法（★核心计算点）： • 先来先服务（FCFS）：公平，但寻道距离可能极长 • 最短寻找时间优先（SSTF）：优先选择与当前磁头最近的请求（会导致“饥饿”现象） • 扫描算法/电梯算法（SCAN）：磁头单向移动到尽头再回头，避免饥饿 • 循环扫描算法（CSCAN）：磁头单向移动服务，返回时直接回起点，不提供服务，改善两端请求的等待时间 • 8.4 磁盘容错技术 • 磁盘高速缓存（Disk Cache） • RAID（独立磁盘冗余阵列）技术： • RAID 0：条带化，无冗余，速度快 • RAID 1：镜像，双份存储，高可靠 • RAID 5：分布式奇偶校验，兼顾性能与安全
第九章 操作系统接口¶
9.1 联机用户接口（命令接口）¶
• 联机用户接口的定义 • 命令解释程序：Shell（Linux/Unix）、CMD / PowerShell（Windows） • 脱机用户接口（批处理用户接口）：作业控制块（JCB）、作业控制语言（JCL）
9.2 🌟 程序接口与系统调用（★高频理论）¶
• 系统调用（System Call）的定义：用户程序请求操作系统内核服务的唯一途径 • 系统调用与通用库函数、普通用户命令的区别 • 系统调用的分类：进程控制、文件系统管理、设备管理、内存管理、信息维护、通信 • 系统调用的中断变态机制： • CPU 状态切换：用户态（目态） → 核心态（管态/内核态） • 触发机制：执行访管指令 / 陷入指令（如 x86 的 int 0x80 或 sysenter，ARM 的 SVC） • 参数传递方式：寄存器传递、内存地址表（堆栈传递）