★ FEATURED ARTICLE 简介本资源是桂林电子科技大学《操作系统》课程期末复习专用手写笔记面向计算机及相关专业本科生聚焦核心考点梳理与应试提分。笔记内容覆盖操作系统基本概念、进程管理三态模型、调度算法、同步与死锁、存储管理分区/分页/分段、页面置换算法、文件管理目录结构、物理组织、索引方式及设备管理缓冲、虚拟设备等全模块重点特别标注高频考点如银行家算法、快表命中计算、多重索引地址转换与避坑提示如‘不考’‘偏轻’类说明便于高效冲刺。资源为单个PDF文件大小4.47MB排版清晰、手写批注丰富适合作为教材补充与考前速查资料。目前已有544人学习下载内容源自真实课堂笔记逻辑连贯、术语准确、例题穿插助力系统回顾与难点突破。1. 桂电操作系统期末复习手写笔记一张覆盖6大核心模块、直击23个高频考点与11处易翻车陷阱的知识地图这份《桂电操作系统期末复习手写笔记.pdf》不是零散知识点堆砌而是一张高度凝练、考频精准、错点明确的“应试型知识地图”。它把操作系统这门课拆解为进程管理15分、存储管理30分、文件系统15分、设备管理10分、死锁与同步25分、处理器基础5分六大权重模块其中存储管理占比最高、文件系统结构最细、死锁计算最易失分——这和多数高校期末命题规律高度吻合。笔记用“☆”标出必考题型如银行家算法、页面置换、多重索引寻址用“不考”“偏轻”“☆不考”等短语果断过滤低频内容如线程细节、死锁检测算法把有限复习时间锚定在真题常驻区。适合两类人一是已学完教材但抓不住重点的中阶学习者需要一张能快速定位“哪里该停、哪里该冲”的导航图二是考前72小时冲刺者需要一份能直接上手演算、对照自查、避开经典坑位的实战笔记。它不讲原理推导不炫技术深度只回答一个问题这张卷子你到底要会哪23个具体动作2. 进程管理与调度三态模型、五种算法、四类时间指标的闭环计算链2.1 进程状态转换从用户态/核心态切入理解“为什么不能乱跳”进程状态不是静态标签而是由硬件中断机制内核权限控制共同驱动的动态闭环。笔记开篇即强调“用户态只能运行用户程序非特权指令”这句话背后是CPU的特权级Ring 0–3设计用户态Ring 3无法直接执行in/out指令访问I/O端口也无法修改页表基址寄存器CR3所有越权操作都会触发保护异常#GP由内核接管。这就是“用户态→核心态”必须通过系统调用、中断或异常的底层原因。三态模型就绪、运行、阻塞的转换箭头本质是内核对资源可用性的实时响应就绪→运行调度器选中加载PC/SP寄存器切换到用户栈运行→就绪时间片用尽触发时钟中断保存现场入就绪队列运行→阻塞发起read()等阻塞系统调用内核将PCB移入等待队列调度新进程提示考试中若出现“进程从运行态直接变为新建态”一定是错的——新建态New只在fork()创建子进程时出现且仅持续极短时间分配PCB、初始化字段之后立即进入就绪态。这是状态机建模的基本约束。2.2 调度算法五种算法的计算逻辑、适用场景与得分关键点调度算法是计算题主力笔记明确列出5种必考类型并给出统一解题模板先画Gantt图 → 标注每个进程的到达时间AT、服务时间BT、完成时间CT、周转时间T CT−AT、带权周转时间W T/BT→ 求平均值。每种算法的核心判据如下算法类型选择依据关键限制典型失分点先来先服务FCFS到达时间最早非抢占式忽略“到达时间”排序误按提交顺序排短作业优先SJF剩余服务时间最短非抢占式混淆“服务时间”与“剩余时间”未重排序列最短剩余时间优先SRTF当前剩余服务时间最短抢占式时间片切分错误未在每个时间点重新比较剩余时间优先级调度非抢占优先级数值最小或最大需看题设非抢占式未声明优先级定义高数高优 or 低数高优轮转调度RR时间片轮转超时即切换抢占式时间片边界计算错误如q4t0–3为第1片t4–7为第2片以SRTF为例某题给定进程P1(AT0,BT8), P2(AT1,BT4), P3(AT2,BT9)t0P1运行剩余7t1P2到达剩余4 7 → 抢占P1P2运行t5P2完成此时P1剩余7, P3剩余9 → P1运行t12P1完成P3运行至t21最终CT[12,5,21], T[12,4,19], 平均T11.67。所有算法都必须严格按时间轴推进不可跳跃假设。2.3 周转时间相关指标为什么“带权周转时间”才是公平性标尺单纯看周转时间T会掩盖长作业对短作业的挤压。例如FCFS下P1(BT1), P2(BT100)若P1先到则T11, T2101平均T51但若P2先到T1101, T2100平均T100.5——平均值失真。而带权周转时间WT/BT消除了服务时间量纲前者W11/11, W2101/1001.01, 平均W≈1.005后者W1101/1101, W2100/1001, 平均W51W值越接近1说明调度越公平。考试中若要求“评价算法优劣”必须同时给出平均T和平均W缺一不可。笔记在此处用红笔标注“只算T不写W扣1分”。2.4 易错点进程管理中4个被反复忽略的底层细节易漏点①用户态/核心态切换必然伴随栈切换为什么因为用户栈无权访问内核数据结构。当系统调用发生时CPU自动将SS:ESP用户栈指针压入内核栈并加载内核栈段寄存器SS0和栈顶ESP0。若题目问“中断处理时使用哪个栈”答“内核栈”而非“当前进程栈”。易漏点②阻塞态进程无法被调度器选中但可被信号唤醒阻塞态进程不在就绪队列中调度器遍历就绪队列时根本看不到它。但当I/O完成设备驱动会调用wake_up_process()将其PCB移入就绪队列——这个动作独立于调度周期。考试若问“阻塞进程何时能再次运行”答“被唤醒后进入就绪态等待下次调度”而非“时间片到时”。易漏点③进程控制块PCB是进程存在的唯一标志创建进程分配PCB初始化字段PID、状态、寄存器上下文、内存映射等撤销进程回收PCB释放资源。没有PCB就没有进程。若题目说“父进程退出后子进程继续运行”必须指出“子进程PCB仍存在被init进程收养”。易漏点④系统调用号是内核API的索引不是功能名sys_read、sys_write等函数名是内核源码标识用户层通过int 0x80x86或syscall指令系统调用号如__NR_read0触发。考试若让写“读文件的系统调用”答“read()库函数最终触发系统调用号0”而非“调用sys_read函数”。3. 死锁与同步信号量建模、银行家算法、哲学家进餐的三层抽象3.1 信号量机制P/V操作如何精确控制临界资源访问信号量Semaphore是解决进程同步的基石工具笔记强调其原子性、整型变量、阻塞队列三大特性。sem_wait()P操作伪代码为void sem_wait(sem_t *s) { while (s-value 0) { // 循环检查非if add_current_to_queue(s); // 加入等待队列 block(); // 主动放弃CPU } s-value--; // 原子减1 }关键点在于P操作必须循环检查busy-waiting而非单次判断否则在多核环境下两个进程可能同时读到value1均通过检查导致value被减两次变为-1破坏互斥性。V操作则相反void sem_post(sem_t *s) { s-value; // 原子加1 if (s-value 0) { // 有进程在等 wake_up_one(s-queue); // 唤醒一个 } }注意考试中若出现“信号量初值为1表示1个资源”这是错的——初值为1表示最多允许1个进程进入临界区即实现互斥与资源数量无关。资源数由后续P/V次数决定。3.2 银行家算法Need矩阵、Work向量、安全序列的手算全流程银行家算法是死锁避免的核心笔记用“苹果过桥”类比桥是系统资源苹果是进程每个苹果需声明过桥所需木板数Max已拿木板数Allocation剩余需求数Need Max − Allocation。算法步骤如下初始化Work Available当前空闲资源向量找进程Pi满足Need[i] ≤ WorkPi能被满足假设Pi完成Work Work Allocation[i]归还资源重复2–3直到所有进程被标记或找不到满足条件的Pi若全部标记则存在安全序列否则系统不安全例系统有3类资源A,B,CAvailable[3,3,2]4个进程进程MaxAllocationNeedP0[7,5,3][0,1,0][7,4,3]P1[3,2,2][2,0,0][1,2,2]P2[9,0,2][3,0,2][6,0,0]P3[2,2,2][2,1,1][0,1,1]Work[3,3,2]查P1Need[1][1,2,2]≤Work → Work[32,30,20][5,3,2]查P3Need[3][0,1,1]≤Work → Work[52,31,21][7,4,3]查P0Need[0][7,4,3]≤Work → Work[70,41,30][7,5,3]查P2Need[2][6,0,0]≤Work → Work[73,50,32][10,5,5]安全序列P1→P3→P0→P2失分重灾区忘记更新Work向量、Need计算错误Max−Allocation搞反、未验证所有进程是否被纳入序列。3.3 死锁四必要条件如何用“循环等待”反推资源分配图死锁发生的四个必要条件互斥、占有并等待、非抢占、循环等待中“循环等待”是唯一可观测、可画图验证的条件。笔记要求必须掌握资源分配图Resource Allocation Graph绘制矩形框表示资源类如R1有3个实例标为●●●圆圈表示进程P1,P2...有向边P→R进程申请资源请求边有向边R→P资源已分配给进程分配边若图中存在有向环则系统可能发生死锁注意有环≠一定死锁需结合资源实例数判断。例如P1→R1, R1→P2, P2→R2, R2→P1构成环P1→R1→P2→R2→P1且R1/R2各只有1实例则必然死锁。提示考试若给资源分配图问“是否死锁”第一步标出所有资源实例数第二步找环第三步验证环中每个资源类的实例是否被完全占用。三步缺一不可。3.4 易错点同步与死锁中3个被严重低估的建模陷阱易漏点①信号量初值决定资源上限而非进程数若有5台打印机应设sem_init(printer_sem, 0, 5)初值为5。若误设为1则最多1个进程能用打印机违背资源池本意。考试中“n个同类资源”必对应信号量初值n。易漏点②银行家算法中“Available”是当前空闲量不是总量Total Allocation Available Need对所有进程求和。若题目只给Allocation和Need必须先算Total再求Available Total − ΣAllocation。直接抄题干Available值是常见错误。易漏点③哲学家进餐问题中“拿左叉再拿右叉”是死锁根源但“按编号顺序拿叉”只是充分条件编号法奇数号哲学家先左后右偶数号先右后左打破循环等待但若所有哲学家同时拿编号小的叉仍可能因竞争失败而阻塞。真正可靠的是引入服务员mutex集中授权。考试若问“如何避免死锁”答“破坏循环等待条件规定拿叉顺序”即可但需知其局限性。4. 存储管理分区/分页/分段的地址转换、快表加速、页面置换的硬核计算4.1 动态分区分配五种算法的碎片化本质与首次适应的工程取舍动态分区将内存划分为大小不等的连续块分配算法直接影响外部碎片。笔记对比五种策略算法选择逻辑碎片特点实际应用首次适应First Fit从低地址起找第一个够大的空闲区中等碎片查找快Linux早期buddy系统变种最佳适应Best Fit找大小最接近需求的空闲区碎片最多产生大量微小块理论研究少实用最坏适应Worst Fit找最大的空闲区大块减少中等碎片减少后续大作业失败率邻近适应Next Fit从上次查找位置继续搜索查找开销略降碎片类似FF某些嵌入式系统快速适应Quick Fit维护多个空闲链表按大小分类查找O(1)但合并复杂高性能服务器关键洞察首次适应虽产生中等碎片但因其查找路径最短、实现最简、缓存友好成为教学与工业首选。考试中若问“为何常用首次适应”答“平衡碎片率与查找效率且易于实现”。4.2 分页地址转换逻辑地址拆分、页表查询、快表TLB命中率的量化影响分页将逻辑地址分为页号Page Number 页内偏移Page Offset。假设32位地址、4KB页则页内偏移占12位2^124096页号占20位2^201M页。地址转换流程CPU给出逻辑地址MMU提取页号查页表页号作索引得物理页框号Frame Number物理地址 Frame Number × Page Size Offset快表TLB是页表的高速缓存其命中率H直接影响有效访存时间EMATEMAT H × (TLB_access_time Memory_access_time) (1−H) × (TLB_access_time 2×Memory_access_time)若TLB访问10ns内存访问100nsH0.95EMAT 0.95×(10100) 0.05×(10200) 104.5 10.5 115ns若无TLBH0EMAT200ns →TLB使访存提速约74%提示考试中若给TLB命中率、访问时间必考EMAT计算。公式中“2×内存访问”是因为先查页表1次内存再访数据1次内存。4.3 页面置换算法FIFO/LRU/Clock的实现差异与Belady现象当缺页中断发生且无空闲页框时需置换一页。三种主流算法FIFO淘汰最早装入的页。简单但存在Belady异常增加页框数缺页率反而上升。例访问序列3,2,1,0,3,2,4用3页框缺页9次用4页框缺页10次。LRU最近最少使用淘汰最久未被访问的页。理想但硬件难实现通常用栈模拟每次访问将页移到栈顶栈底即LRU页或计数器为每页设访问时间戳。Clock时钟算法FIFO的改进版为每页设引用位R bit。指针循环扫描遇R0则置换遇R1则清R并跳过。R位由硬件在每次访问时置1OS定时清零。例页框数3访问序列7,0,1,2,0,3,0,4初始R0加7,0,1 → 页框[7,0,1]R[1,1,1]访27的R1→清00的R1→清01的R1→清0指针回77的R0→置换7 → [2,0,1]后续同理...考试重点Clock算法必须写出R位变化过程只写置换结果不得分。4.4 易错点存储管理中4个被忽视的硬件协同细节易漏点①页内偏移位数由页大小决定与虚拟地址长度无关4KB页 → 偏移12位16MB页 → 偏移24位。若题干说“32位地址、页大小4KB”偏移固定12位页号必为20位。混淆会导致地址拆分错误。易漏点②快表TLB是关联存储器按内容寻址非按地址寻址TLB中存页号页框号对CPU送页号TLB并行匹配所有项。若答“TLB像数组一样用页号当索引”是根本性错误。易漏点③二级页表中页目录项PDE存页表基址页表项PTE存页框号逻辑地址拆为页目录索引 页表索引 页内偏移。先查页目录得页表物理地址再查页表得页框号。考试若问“二级页表减少内存浪费的原理”答“只分配实际使用的页表空页表不占内存”。易漏点④抖动Thrashing的根因是进程工作集大于分配页框数非页面置换算法本身即使LRU最优若给每个进程只分配2页而其工作集需5页仍会频繁缺页。解决抖动需增加分配页框数或挂起部分进程而非换算法。5. 文件系统多重索引结构、磁盘空间管理、目录实现的物理与逻辑分离5.1 文件物理结构顺序/链接/索引的I/O性能与可靠性权衡文件在磁盘上的组织方式直接影响读写效率与容错能力顺序结构文件块在磁盘上连续存放。优点顺序读写极快一次寻道批量传输缺点文件增长需预留空间删除后产生大块外部碎片。链接结构每块含指向下一块的指针。优点无外部碎片文件可动态增长缺点随机访问需O(n)遍历指针占存储空间单点损坏导致链断裂。索引结构索引块存所有数据块地址。优点支持随机访问O(1)寻址无外部碎片缺点小文件浪费索引块空间。笔记强调现代文件系统如ext4、NTFS均采用混合索引——直接块12个存小文件一级间接块存256个块地址支持中文件二级/三级间接块支持超大文件。5.2 多重索引寻址直接/间接索引的容量计算与寻址路径以UNIX System V为例假设盘块大小1KB盘块号占4字节直接索引12个地址 → 支持12×1KB 12KB一级间接1块存256个地址1024/4256 → 256×1KB 256KB二级间接1块存256个一级间接块地址 → 256×256×1KB 64MB三级间接1块存256个二级间接块地址 → 256×64MB 16GB总容量 12KB 256KB 64MB 16GB ≈ 16GB寻址路径示例读取第10000字节字节10000 ÷ 1024 9.76 → 第10块块号90起始块号9 12 → 直接索引第9项 → 得物理块号 → 读取若读第1000000字节≈976KB块号976 12且976 12256268 → 属一级间接范围一级间接块地址 直接索引第12项 → 读该块块内偏移 (976−12) × 4 3856 → 取第3856–3859字节得物理块号提示考试必考“某字节对应第几块”及“该块地址存于何处”需熟练进行“字节→块号→索引层级→地址位置”三级换算。5.3 文件空间管理位示图、空闲链表、成组链接法的适用场景位示图Bitmap用1位表示1块是否空闲。优点分配/回收O(1)定位适合大磁盘缺点图本身占空间1TB磁盘需125MB位图。空闲链表所有空闲块连成链表头指针存超级块。优点无额外空间开销缺点分配/回收需遍历随机性差。成组链接法UNIX将空闲块分组如100块/组每组首块存下一组地址。超级块存当前组首块地址。优点兼顾空间效率与速度UNIX实证可靠。笔记指出成组链接法是考试重点因其结合了链表与索引思想。分配时取当前组首块若该组只剩1块则读取其存的下一组地址回收时若当前组未满插入若已满新建一组并更新链接。5.4 易错点文件系统中3个被轻视的元数据一致性风险易漏点①目录项Directory Entry不存文件内容只存文件名与i-node号i-node才是文件元数据大小、权限、时间戳、数据块地址的载体。删除文件删除目录项i-node引用计数减1仅当引用计数为0才真正释放数据块。考试若问“rm命令做了什么”答“解除目录项与i-node的链接”而非“删除文件内容”。易漏点②软链接与硬链接的本质区别在于i-node引用方式硬链接多个目录项指向同一i-node共享数据块软链接新建文件内容为路径字符串有自己的i-node。故硬链接不能跨文件系统i-node号全局唯一软链接可以。易漏点③文件系统挂载mount的本质是将设备的根目录接入主目录树挂载点目录如/mnt/usb的内容被隐藏访问时重定向到被挂载设备的根。卸载umount前必须确保无进程在该目录下工作否则“device busy”错误。考试若问“为什么挂载后原目录内容看不见”答“VFS层将路径解析重定向至新设备的根i-node”。6. 设备管理与复习清单缓冲技术、虚拟设备、设备独立性的落地检查表6.1 缓冲技术单缓冲/双缓冲/循环缓冲的吞吐量瓶颈分析I/O速度远低于CPU缓冲是缓解鸿沟的核心手段单缓冲CPU向缓冲区写设备从缓冲区读。CPU必须等设备读完才能写下一单元 →CPU与设备串行工作吞吐量 min(CPU处理速率, 设备传输速率)。双缓冲设缓冲区A、B。CPU写A时设备读B完成后交换角色。CPU与设备可部分重叠但仍有等待CPU写完A需等设备读完B才能写B。循环缓冲多缓冲N个缓冲区组成环。CPU总可写空闲缓冲区设备总可读满缓冲区。当N足够大CPU与设备完全并行吞吐量趋近两者较大者。笔记用数据说话设CPU处理1单元1ms设备传输1单元2ms单缓冲吞吐量0.5单元/ms双缓冲下CPU写A1ms设备读B2ms3ms处理2单元 → 0.67单元/ms循环缓冲N≥3时可稳定在1单元/msCPU瓶颈。注意考试中若问“双缓冲能否消除等待”答“不能完全消除仅减少等待时间”因CPU与设备速率不匹配时慢方总会拖累快方。6.2 虚拟设备技术SPOOLing如何将独占设备变为共享资源SPOOLingSimultaneous Peripheral Operations On-Line是虚拟设备的典型实现以打印机为例输入井磁盘上模拟输入设备的区域输出井磁盘上模拟输出设备的区域输入进程将用户作业从输入设备读入输入井输出进程将输出井中作业送打印机用户进程不再直接操作打印机而是向输出井写数据快输出进程后台慢慢打印慢。本质是用磁盘空间换取设备并发性将独占设备打印机虚拟为多个逻辑设备。关键点SPOOLing要求输入/输出井足够大且输入/输出进程与用户进程异步协作。若输出井满用户进程需阻塞此时退化为假脱机。6.3 设备独立性逻辑设备名→物理设备号→驱动程序的三级映射设备独立性指应用程序用逻辑名如/dev/lp0访问设备无需关心物理细节。实现依赖三层映射逻辑设备表LUT进程私有存逻辑名, 物理设备号对系统设备表SDT全局存物理设备号, 控制器号, 驱动程序入口控制器表存控制器状态、通道信息当进程打开/dev/lp0查LUT得物理设备号D1查SDT得D1对应控制器C1及驱动print_driver调用print_driver.open()初始化C1好处更换打印机型号只需更新SDT中D1对应的驱动入口应用代码零修改。6.4 复习清单一份可打印、可勾选、可速查的考前72小时行动指南别再泛泛而读。这份清单按真题出现频率和计算复杂度排序每项对应笔记中明确标注的位置如P12、P23打印后逐条打钩序号复习任务检查方式预估耗时笔记页码1默写三态模型转换图含触发条件时间片/IO/中断闭眼画图标注所有箭头条件8minP52手算SRTF调度给定5进程AT/BT画Gantt图求平均T和W对照答案误差≤0.115minP83银行家算法全流程给Need/Allocation/Available找安全序列写出每步Work向量变化20minP154分页地址转换32位地址/4KB页求页号/偏移画两级页表寻址路径标出每级访问的物理地址12minP195Clock页面置换给访问序列和R位初值模拟3轮指针扫描标出每次R位变化和置换页18minP226多重索引寻址计算1000000字节所在块号指出该地址存于直接/间接哪一层写出“字节→块号→索引层级→地址位置”三步15minP277SPOOLing结构图画输入井/输出井/输入进程/输出进程四要素及数据流箭头方向必须正确输入进程→输入井→用户进程10minP318设备独立性三级映射默写LUT/SDT/控制器表各自存什么举例说明open()调用时的数据流向10minP32血泪经验我曾因没练熟第3项银行家考场上卡在Work向量更新浪费22分钟。从那以后我每次模拟考前必做3遍银行家手算强制自己写出每一步Work值哪怕超时也要写完。现在看到Need矩阵手指会自动开始加法——肌肉记忆比理解更可靠。最后检查三件事所有计算题是否保留小数点后两位考试要求所有“不考”标记的内容是否彻底划掉如线程、死锁检测所有“☆”必考点是否至少演算过2次如页面置换、多重索引希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
