2025年操作系统精髓与设计原理·第五版复习题及答案

2025年操作系统精髓与设计原理·第五版复习题及答案一、进程管理1.简述进程与线程的本质区别及操作系统对二者的调度差异。进程是资源分配的基本单位，拥有独立的地址空间、文件描述符等资源；线程是CPU调度的基本单位，共享所属进程的资源。操作系统调度进程时需切换页表、寄存器等上下文，开销较大；调度线程仅需切换线程私有寄存器（如PC、栈指针），上下文切换更轻量。现代OS（如Linux）通过轻量级进程（LWP）实现用户级线程与内核级线程的映射，部分系统支持多对一、一对一、多对多等线程模型。2.某系统采用多级反馈队列调度算法，设有3个队列Q1（时间片1ms）、Q2（时间片2ms）、Q3（时间片4ms），优先级Q1>Q2>Q3。若进程P1在Q1中运行0.5ms后被抢占，P2在Q2中运行2ms后完成，P3在Q3中运行5ms未完成，描述各进程的后续调度流程。P1因未用完Q1时间片（1ms）被抢占（可能因更高优先级进程到达），下次调度时仍留在Q1；P2在Q2中用完2ms时间片后完成，无需调整队列；P3在Q3中运行5ms（超过时间片4ms），被剥夺CPU并降级到下一级队列（若Q3为最低级则保留），下次调度时在Q3中获得4ms时间片继续执行。该算法通过动态调整进程优先级，平衡短作业响应时间与长作业吞吐量。3.死锁预防需破坏死锁的四个必要条件，举例说明如何破坏“请求和保持”条件与“循环等待”条件。破坏“请求和保持”：采用静态分配策略，进程在运行前一次性申请所有所需资源（如某些实时系统的资源预分配），但可能导致资源利用率低下。破坏“循环等待”：对资源进行全局编号，进程按递增顺序申请资源（如将打印机设为1号、扫描仪设为2号，进程需先申请1号再申请2号），避免形成环形等待链。需注意，破坏“互斥”（如共享可抢占资源）仅适用于部分可抢占资源（如内存），对临界资源（如打印机）不可行。4.比较银行家算法与死锁检测算法的核心区别及应用场景。银行家算法是死锁避免策略，通过模拟资源分配后的状态是否安全（存在安全序列）决定是否分配资源，需已知进程最大需求、当前分配和可用资源，适用于资源种类少、进程数量有限的系统（如数据库事务调度）。死锁检测算法是事后处理，定期检查资源分配图是否存在环（如使用资源分配表和等待表构建有向图），检测到死锁后通过终止部分进程释放资源，适用于资源动态分配频繁、无法预知最大需求的场景（如通用服务器系统）。5.进程上下文切换时，操作系统需要保存和恢复哪些关键信息？以x86架构为例说明。需保存：通用寄存器（EAX、EBX等）、指令指针（EIP）、栈指针（ESP）、状态寄存器（EFLAGS）、页目录基址寄存器（CR3）等。恢复时按相反顺序加载。例如，当从用户进程A切换到内核线程B时，首先将A的用户态寄存器压入内核栈，保存CR3（切换页表），然后加载B的内核栈中的寄存器值，更新EIP到B的下一条指令。上下文切换的开销主要来自寄存器拷贝和TLB刷新（若页表切换），现代OS通过内核线程与用户线程的绑定（如Linux的clone系统调用）减少切换次数。二、内存管理6.分页系统中，逻辑地址到物理地址的转换需经过哪些步骤？若页表项包含有效位、修改位、访问位、保护位，各字段的作用是什么？步骤：①将逻辑地址拆分为页号（高位）和页内偏移（低位）；②通过页表基址寄存器找到页表，以页号为索引查找页表项；③检查有效位（1表示页在内存，0表示缺页），若有效则取帧号，与页内偏移拼接得到物理地址；④若无效则触发缺页中断，调入页面后更新页表。字段作用：有效位（标记页是否在内存）、修改位（标记页是否被写过，换出时需写回磁盘）、访问位（用于页面置换算法，如LRU）、保护位（设置读/写/执行权限，防止越权访问）。7.虚拟内存的缺页率受哪些因素影响？若系统缺页率过高（如超过10%），可能的原因及解决方法是什么？影响因素：物理内存容量（容量小则缺页率高）、页面置换算法（LRU比FIFO更优）、进程工作集大小（若工作集大于物理内存则频繁缺页）、程序局部性（局部性差的程序访问分散，缺页多）。缺页率过高的可能原因：物理内存不足（如同时运行大量进程）、置换算法选择不当（如FIFO产生Belady异常）、进程工作集未被正确驻留（如颠簸现象）。解决方法：增加物理内存、优化置换算法（改用LRU或其近似实现）、调整进程数量（通过交换技术将部分进程换出到磁盘）、预取页面（根据局部性原理提前加载可能访问的页面）。8.比较分段与分页的主要区别，说明段页式管理如何结合二者优势。分页是物理划分（用户不可见），页大小固定（如4KB），解决内存碎片问题；分段是逻辑划分（用户可见），段大小可变（如代码段、数据段），支持共享和保护。段页式管理先将地址空间分段（用户视角），每段再分页（物理视角）：逻辑地址=段号+段内页号+页内偏移。通过段表找到段的页表基址，再通过页表找到帧号，最终得到物理地址。优势：既利用分段的逻辑独立性（方便共享、保护），又利用分页的内存利用率（减少碎片），但增加了地址转换复杂度（需访问段表和页表，可能引入TLB加速）。9.某系统物理内存4GB（页帧大小4KB），逻辑地址空间64位，采用三级页表，页表项大小8字节。计算各级页表的页号位数及页表占用的内存空间（假设每个页表恰好占满一个页面）。物理内存4GB=2^32B，页帧大小4KB=2^12B，故物理地址需32位，其中页内偏移12位，帧号20位（32-12=20）。逻辑地址64位，三级页表需将页号分为三级（P1、P2、P3），剩余位为页内偏移（12位）。总页号位数=64-12=52位，三级页表均分52位（假设均分），则每级页号约17-18位（实际可能根据页表项数调整）。每个页表项8字节，一个页面（4KB）可存放4KB/8B=512个页表项，故每级页号需9位（2^9=512）。三级页号共27位（9×3），页内偏移12位，剩余64-27-12=25位（可能为扩展或保留）。每个页表占4KB，三级页表共需3×4KB=12KB（假设每个页表仅一个页面，实际可能更多，因逻辑地址空间大时页表需多级展开）。10.简述LRU（最近最久未使用）置换算法的实现方式，说明为何实际OS中常用其近似算法（如二次机会算法）。LRU需记录每个页面最后一次被访问的时间，置换时选择时间最旧的页面。实现方式：①为每个页表项添加访问位（每访问一次置1），定期扫描并记录时间戳（硬件支持）；②使用双向链表，访问页面时移到链表头部，置换时删除尾部页面。实际OS中，LRU需要维护严格的时间顺序，硬件成本高（如需要为每个页面维护64位时间戳），且扫描所有页面的时间开销大。近似算法（如二次机会）仅用访问位（0或1），扫描时将访问位为1的页面置0并跳过，遇到访问位为0的页面置换，近似模拟LRU行为，降低实现复杂度。三、文件系统与I/O管理11.比较连续分配、链接分配、索引分配的优缺点，说明UNIX文件系统（如ext4）采用的分配方式及优化。连续分配：文件数据块连续存放，支持顺序和随机访问（直接计算物理地址），但易产生外部碎片（如文件删除后留下无法利用的小空间），且文件扩展困难（需移动后续数据）。链接分配：数据块通过指针链接，无外部碎片，文件扩展灵活（添加新块并修改前一块指针），但仅支持顺序访问（需遍历指针链），指针易损坏导致数据丢失。索引分配：通过索引块记录所有数据块地址，支持随机访问（索引块中直接查找），扩展灵活（添加新块到索引块），但索引块本身占用空间（小文件需额外空间存储索引）。ext4采用混合索引分配：i节点（索引节点）包含12个直接块指针、1个一级间接块指针（指向一个块，该块存64个数据块指针，假设块大小4KB，指针8字节）、1个二级间接块指针（指向一级间接块的块）、1个三级间接块指针。小文件（≤12×4KB=48KB）直接用直接块，大文件通过间接块扩展，平衡了空间和访问效率。12.磁盘调度算法中，SCAN与C-SCAN的区别是什么？某磁盘有200个磁道（0-199），当前磁头在100，移动方向向磁道号增加方向，请求序列为10、50、150、180、120，分别用SCAN和C-SCAN计算总寻道长度。SCAN（电梯算法）：磁头沿一个方向移动，处理所有请求，到达端点后反向。C-SCAN：磁头单向移动处理请求，到达端点后立即回到起点（不处理返回路径的请求），模拟循环扫描。SCAN调度顺序（方向→199）：100→120→150→180（到180后，下一个请求是199方向无更高请求，反向→0）→50→10。寻道长度：(120-100)+(150-120)+(180-150)+(180-50)+(50-10)=20+30+30+130+40=250。C-SCAN调度顺序：100→120→150→180（到180后，磁头移动到199，然后立即回到0，处理剩余请求）→10→50。寻道长度：(120-100)+(150-120)+(180-150)+(199-180)+(199-0)+(10-0)+(50-10)=20+30+30+19+199+10+40=348（注：实际C-SCAN在到达端点后直接跳转，寻道长度为199-180（到端点）+(0-199)（跳转）+(10-0)+(50-10)，但通常计算时忽略跳转的物理移动，仅算处理请求的路径，可能更合理的顺序是100→120→150→180→199（端点）→0→10→50，寻道长度为(120-100)+(150-120)+(180-150)+(199-180)+(10-0)+(50-10)=20+30+30+19+10+40=149，需根据具体定义调整）。13.简述SPOOLing技术的核心思想及在打印机管理中的应用。SPOOLing（外部设备联机并行操作）通过磁盘作为缓存，将独占设备模拟为共享设备。核心思想：①输入井/输出井（磁盘上的缓冲区）存储I/O数据；②输入进程/输出进程（守护进程）负责将数据从输入设备→输入井（预输入），或从输出井→输出设备（缓输出）；③用户进程只需与输入井/输出井交互，无需直接占用物理设备。打印机管理中，用户进程提交打印任务时，先将数据写入输出井（磁盘），输出进程按顺序将输出井中的数据发送到打印机。这样多个用户可同时“共享”打印机（实际按序打印），避免了进程因等待打印机而阻塞，提高了CPU利用率。14.文件系统的一致性检查（如fsck）主要检查哪些内容？举例说明如何修复目录项不一致的问题。一致性检查内容：①索引节点（i节点）的引用计数是否与目录项中的硬链接数一致；②数据块的分配位图与实际占用情况是否一致（避免重复分配或未释放）；③目录项的父目录指针是否正确（防止循环目录）；④文件大小与实际占用的数据块数是否匹配（避免元数据错误）。修复目录项不一致：例如，某文件在目录A中有一个条目（硬链接数1），但i节点的链接计数为2。检查所有目录，找到另一个指向该i节点的目录B（可能是误删除的条目），若B存在则恢复其目录项；若不存在则将i节点的链接计数减为1，避免数据块被错误保留（可能导致空间泄漏）。四、并发与同步15.信号量机制中，P（wait）操作与V（signal）操作的原子性为何重要？若P操作不原子，可能导致什么问题？P操作（S.value--）的原子性确保“检查S.value≥0→若≥0则占用资源”的过程不可中断，避免多个进程同时看到S.value>0而同时进入临界区，破坏互斥。若P操作不原子，假设S.value=1，进程A检查到S.value≥0，尚未执行S.value--时被进程B抢占，B也检查到S.value≥0并执行S.value--（S.value=0），此时A恢复执行并再次S.value--（S.value=-1），两个进程都进入临界区，导致数据不一致。16.用信号量解决读者-写者问题（写者优先），要求写出信号量定义及伪代码。信号量定义：mutex：互斥访问读者计数器（read_count），初始值1；write_lock：控制写者进入，初始值1；read_preference：实现写者优先，初始值1（写者到达时抢占该信号量，阻止新读者进入）。伪代码：写者进程：wait(write_lock);写操作;signal(write_lock);读者进程：wait(read_preference);//写者优先，新读者需等待read_preferencewait(mutex);read_count++;if(read_count==1)wait(write_lock);//第一个读者阻止写者signal(mutex);signal(read_preference);//释放read_preference，允许后续读者或写者竞争读操作;wait(mutex);read_count--;if(read_count==0)signal(write_lock);//最后一个读者释放写者signal(mutex);说明：写者通过wait(write_lock)直接抢占，读者需先获取read_preference（写者到达时会先抢占read_preference，阻止新读者进入），确保写者不会被连续到达的读者饿死。17.比较互斥锁（mutex）与条件变量（conditionvariable）的使用场景，说明如何用二者配合实现“当缓冲区满时生产者等待”的逻辑。互斥锁用于保护临界区（确保同一时间只有一个线程访问共享资源），条件变量用于线程间的协调（当某个条件不满足时阻塞，条件满足时被唤醒）。二者配合使用：互斥锁保证对共享变量（如缓冲区状态）的原子访问，条件变量传递条件变化的信号。实现生产者-消费者（缓冲区满等待）：定义：mutex：互斥锁，初始化为1；cond_full：条件变量，初始化为0（表示缓冲区未满）；缓冲区大小N，当前计数count=0。生产者：lock(mutex);while(count==N){//检查缓冲区是否满wait(cond_full,mutex);//释放mutex并阻塞，被唤醒时重新获取mutex}将数据放入缓冲区;count++;unlock(mutex);signal(cond_empty);//唤醒等待的消费者（假设cond_empty表示缓冲区非空）说明：wait操作原子地释放mutex并阻塞线程，避免在等待条件时持有锁导致其他线程无法修改条件。18.分析管程（monitor）与信号量的区别，为何管程更易于实现正确性？信号量通过P/V操作控制同步，逻辑分散在各个进程中，易因错误的P/V顺序导致死锁或竞态条件（如忘记释放信号量）。管程将共享变量及对其的操作封装在一个模块中，通过条件变量（condition）实现同步，同一时间仅一个进程进入管程，操作逻辑集中，减少了因分散控制导致的错误。例如，管程的入口由编译器自动加锁，退出时自动解锁，程序员只需关注条件等待（wait）和条件通知（signal），降低了编程复杂度。五、操作系统安全19.比较自主访问控制（DAC）与强制访问控制（MAC）的核心区别，举例说明Linux的文件权限（rwx）属于哪种模型。DAC由资源所有者决定访问权限（如用户A创建文件，可设置用户B的读权限），灵活性高但易因所有者误操作导致安全漏洞。MAC由系统强制实施全局策略（如多级安全策略，用户按密级（秘密、机密、绝密）访问对应密级的资源），适用于高安全需求场景（如军事系统）。Linux的文件权限（用户、组、其他的rwx位）属于DAC，文件所有者可通过chmod命令修改权限（如设置文件为仅自己可写）。20.操作系统如何通过地址空间隔离实现进程安全？以x86的保护模式为例说明段寄存器的作用。地址空间隔离确保进程只能访问自己的地址空间，无法越界访问其他进程或内核空间。x86保护模式下，每个进程有独立的页表（CR3寄存器指向），用户态进程的线性地址通过页表转换为物理地址时，若页表项的用户/超级用户（U/S）位为0（内核页），用户态访问会触发页错误异常（PF），被内核捕获并终止非法访问。段寄存器（如CS、DS）存放段选择子，包含描述符表索引和特权级（RPL），通过访问全局描述符表（GDT）或局部描述符表（LDT）获取段基址、限长和权限，防止越界访问段内地址。21.简述可信计算基（TCB）的定义，说明其在操作系统安全中的作用。TCB是系统中所有保护机制的集合（包括硬件、固件、软件），负责实施安全策略。其作用是确保系统关键操作（如进程切换、内存分配、文件访问）符合安全策略，TCB的失效会直接导致系统安全漏洞。例