操作系统习题详解与重点复习资料

操作系统习题详解与重点复习资料*关键点：PV操作的顺序不能颠倒。对互斥信号量`mutex`的P操作必须在对同步信号量`empty`或`full`的P操作之后，以避免死锁。V操作的顺序则无关紧要。习题3：进程调度算法*题目：设有三个作业A、B、C，它们到达系统的时间分别是0、1、2，所需运行时间分别是3、2、1。若分别采用先来先服务调度算法（FCFS）和短作业优先调度算法（SJF，非抢占式），试计算各作业的周转时间和平均周转时间。*详解：*周转时间=作业完成时间-作业到达时间。*平均周转时间=所有作业周转时间之和/作业数。*FCFS调度算法：*调度顺序严格按照到达时间：A->B->C。*A：到达时间0，运行时间3→完成时间0+3=3→周转时间3-0=3。*B：到达时间1，运行时间2→完成时间3+2=5→周转时间5-1=4。*C：到达时间2，运行时间1→完成时间5+1=6→周转时间6-2=4。*平均周转时间=(3+4+4)/3=11/3≈3.67。*SJF调度算法（非抢占式）：*每次选择当前已到达且运行时间最短的作业。*t=0时，只有A到达，调度A运行。A需运行3个单位时间，于t=3完成。*在A运行期间（t=0到t=3），B在t=1到达，C在t=2到达。t=3时，就绪队列中有B（运行时间2）和C（运行时间1）。选择最短的C运行。*C运行1个单位时间，于t=3+1=4完成。*此时就绪队列中只有B，调度B运行，B运行2个单位时间，于t=4+2=6完成。*调度顺序：A->C->B。*A：完成时间3→周转时间3-0=3。*B：完成时间6→周转时间6-1=5。*C：完成时间4→周转时间4-2=2。*平均周转时间=(3+5+2)/3=10/3≈3.33。*结论：SJF在本例中获得了更短的平均周转时间，体现了其缩短平均等待时间的优势。三、内存管理核心知识回顾：*内存管理的功能：内存分配、地址映射、内存保护、内存扩充（虚拟内存）。*连续分配管理方式：单一连续分配、固定分区分配、动态分区分配（首次适应算法、最佳适应算法、最坏适应算法、邻近适应算法）。*分页存储管理方式：*页面与物理块、页表、地址结构（页号P+页内偏移量W）。*地址变换过程（基本地址变换、具有快表的地址变换）。*分段存储管理方式：*段、段表、地址结构（段号S+段内偏移量W）。*地址变换过程。*分页与分段的比较（页是物理单位，段是逻辑单位；页大小固定，段大小可变等）。*段页式存储管理方式：结合分段与分页的优点，先分段，段内再分页。*虚拟内存的基本概念：*定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。*特征：多次性、对换性、虚拟性。*理论基础：局部性原理（时间局部性、空间局部性）。*请求分页存储管理：*页表项的扩展（状态位P、访问字段A、修改位M、外存地址）。*缺页中断处理。*页面置换算法：最佳置换算法（OPT，理想但不可实现）、先进先出置换算法（FIFO，可能出现Belady异常）、最近最久未使用置换算法（LRU）、时钟置换算法（CLOCK/NRU）、改进型时钟置换算法。理解各算法的原理、优缺点及页面置换过程。*页面分配策略（固定分配局部置换、可变分配全局置换、可变分配局部置换）与调入策略。典型习题详解：习题4：分页地址变换*题目：某分页系统中，页面大小为4KB（1KB=1024B）。若某进程的页表如下所示，试将逻辑地址0A5CH（十六进制）转换为物理地址。页号物理块号:---::-------:051102338*详解：*步骤1：将逻辑地址转换为二进制，并确定页号和页内偏移量。*页面大小4KB=2^12B，所以页内偏移量占12位。*逻辑地址0A5CH（十六进制）转换为二进制：0000101001011100。*总长度为16位。前（16-12）=4位为页号P，后12位为页内偏移量W。*页号P：00001010的高4位？不对，0A5CH是4位十六进制，共16位二进制。页面大小4KB，页内偏移是12位，所以前4位是页号。*0A5CH→二进制：`0000101001011100`*页号P=高4位：`0000`（二进制）=0（十进制）。*页内偏移量W=低12位：`101001011100`（二进制）。将其转换为十六进制是A5CH，十进制是2652。*步骤2：查页表，得到物理块号。*页号0对应的物理块号为5。*步骤3：计算物理地址。*物理地址=物理块号×页面大小+页内偏移量。*物理块号5，页面大小4KB→5×4KB=20KB=20×1024=____B。*页内偏移量W为2652B。*物理地址=____+2652=____B。*或用十六进制计算：物理块号5（十六进制为5），页面大小4KB=1000H。物理块号左移12位（即乘以1000H）得到5000H。页内偏移W为A5CH。物理地址=5000H+A5CH=5A5CH。*答案：物理地址为5A5CH（十六进制）或____（十进制）。习题5：LRU页面置换算法*题目：在一个请求分页系统中，假设一个进程的页面走向为：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。当分配给该进程的物理块数分别为3和4时，试用LRU页面置换算法计算访问过程中的缺页次数和缺页率。*详解：*LRU（最近最久未使用）算法：当需要置换一页时，选择最近一段时间内最久没有被访问过的页面予以淘汰。*缺页率=缺页次数/总的页面访问次数。*物理块数m=3：*初始化：物理块为空，缺页次数=0。*访问序列及物理块状态变化（括号内为最近最久未使用的页面，*表示缺页）：1.7：[7](空)(空)→*缺页1→块：7,_,_(最近使用:7)2.0：[7][0](空)→*缺页2→块：7,0,_(最近使用:0,7)3.1：[7][0][1]→*缺页3→块：7,0,1(最近使用:1,0,7)4.2：最久未使用7→置换7为2→[2][0][1]→*缺页4→块：2,0,1(最近使用:2,1,0)5.0：已在块中→块：2,0,1(最近使用:0,2,1)6.3：最久未使用1→置换1为3→[2][0][3]→*缺页5→块：2,0,