大学操作系统课程经典习题解析

大学操作系统课程经典习题解析操作系统作为计算机专业的核心课程，其概念抽象、知识点密集，对理解计算机系统的工作原理至关重要。习题练习是巩固理论知识、培养分析与解决问题能力的关键环节。本文将选取若干操作系统课程中的经典习题，进行深入解析，旨在帮助读者更好地理解和掌握核心概念与解题思路。一、进程管理与调度进程管理是操作系统的核心功能之一，涉及进程状态转换、调度算法、进程同步与互斥等关键知识点。例题1：进程状态转换题目：试分析在一个单处理器系统中，一个进程的生命周期内可能经历的状态转换，并说明在何种情况下会发生这些转换。解析：进程的基本状态通常包括就绪（Ready）、运行（Running）和阻塞（Blocked）。在某些系统中，还可能引入新建（New）和终止（Terminated）状态。1.就绪→运行：处于就绪状态的进程已获得除处理器外的所有必要资源。当处理器空闲时，操作系统的进程调度程序会从就绪队列中选择一个进程投入运行，该进程的状态便从就绪转为运行。这是调度程序主动选择的结果。2.运行→阻塞：正在运行的进程在执行过程中，可能因需要等待某一事件的发生（如等待I/O操作完成、等待某一资源可用、等待来自其他进程的信号）而无法继续执行。此时，该进程会主动放弃处理器，进入阻塞状态。3.阻塞→就绪：当阻塞进程所等待的事件完成后（如I/O操作结束、所需资源可用），该进程将从阻塞状态转变为就绪状态，重新加入就绪队列，等待调度程序再次将其选中并分配处理器。4.运行→就绪：这种转换通常有两种情况。一是在抢占式调度策略下，一个优先级更高的进程进入就绪队列，操作系统会暂停当前运行的低优先级进程，使其回到就绪队列。二是在非抢占式调度策略下，当前运行进程的时间片用完（若采用时间片轮转调度算法），操作系统会将其从运行状态切换到就绪状态，以便让其他就绪进程获得执行机会。5.新建→就绪：当一个新进程被创建时，系统为其分配了必要的资源（如PCB）并初始化后，该进程便进入就绪状态，等待调度执行。6.运行→终止：运行中的进程完成其任务后，或因发生错误而异常终止时，会从运行状态转变为终止状态。此时，操作系统会回收该进程所占用的资源。理解进程状态转换的关键在于把握导致状态转换的事件以及各状态的本质特征：就绪状态是“万事俱备，只欠CPU”；运行状态是“正在CPU上执行”；阻塞状态是“等待某个事件，CPU空闲也无法执行”。例题2：进程调度算法题目：设有三个进程P1、P2、P3先后（但几乎同时）到达系统，它们的运行时间分别为A、B、C（此处A、B、C为具体时间值，为避免数字，可理解为短、中、长三个不同时长），且均为计算型作业。试比较在先来先服务（FCFS）、短作业优先（SJF）和时间片轮转（RR，时间片设为一个较小值）三种调度算法下的平均周转时间和平均带权周转时间，并讨论各算法的优缺点。解析：为简化分析，我们假设P1、P2、P3到达时间均为0（或非常接近，忽略到达时间差），运行时间分别为“短”（S）、“中”（M）、“长”（L），且S<M<L。*先来先服务（FCFS）：*调度顺序：P1→P2→P3(假设到达顺序如此)*各进程完成时间：S,S+M,S+M+L*各进程周转时间：S-0=S,(S+M)-0=S+M,(S+M+L)-0=S+M+L*平均周转时间：(S+(S+M)+(S+M+L))/3=(3S+2M+L)/3*平均带权周转时间：(S/S+(S+M)/M+(S+M+L)/L)/3=(1+(S/M+1)+(S/L+M/L+1))/3=(3+S/M+S/L+M/L)/3*优点：简单、公平，易于实现。*缺点：未考虑进程特性，短进程可能因长进程在前而等待时间过长，平均周转时间较长，即所谓的“convoyeffect”（护航效应）。*短作业优先（SJF）：*调度顺序：P1(S)→P2(M)→P3(L)(因为S<M<L)*各进程完成时间：S,S+M,S+M+L(与FCFS相同顺序，因此完成时间、周转时间、平均周转时间、平均带权周转时间计算公式与FCFS相同，但此处是因为我们假设了到达顺序与SJF顺序一致。若到达顺序不同，例如长作业先到，则SJF会有显著改善。)**假设另一种情况：P3先到，然后P2，然后P1，但它们几乎同时到达，SJF仍会选择P1先运行。**优点：在所有作业同时到达的情况下，SJF能获得最短的平均周转时间和平均带权周转时间，对短作业有利。*缺点：对长作业不利，可能导致长作业“饥饿”；需要预先知道进程的运行时间，在实际中有时难以精确获得；未考虑进程的紧急程度（优先级）。*时间片轮转（RR）：*假设时间片为q(q远小于S,M,L)。*调度顺序：P1运行q→P2运行q→P3运行q→P1运行q→P2运行q→P3运行q→...直到进程完成。*对于短进程P1，它将在⌈S/q⌉个时间片后完成。同理，P2在⌈M/q⌉个时间片，P3在⌈L/q⌉个时间片后完成。*平均周转时间会介于FCFS和SJF之间（在所有进程同时到达的batch环境下）。时间片的大小对RR算法的性能影响很大。*优点：公平性较好，每个进程都能得到及时响应，适用于分时系统。*缺点：存在上下文切换开销；时间片选择不当，可能导致系统性能下降（时间片过短，上下文切换频繁；时间片过长，退化为FCFS）。总结：SJF在理想情况下性能最优，但依赖于预知运行时间。FCFS简单但对短作业不友好。RR是交互系统的主要调度方式，关键在于时间片的选择。二、死锁问题死锁是并发环境下进程因竞争资源而可能导致的一种僵局状态。例题3：死锁的必要条件与预防题目：简述死锁产生的四个必要条件，并说明针对每个条件可以采取哪些预防措施。解析：死锁产生必须同时满足以下四个必要条件：1.互斥条件（MutualExclusion）：资源被进程排他性地占有，即一个资源在同一时刻只能被一个进程使用。*预防措施：尽可能使资源可共享使用。例如，采用SPOOLing技术将独占设备（如打印机）转换为共享的虚拟设备。但对于某些本质上就是独占的资源（如临界区），此条件无法破坏。*预防措施：*方法一：进程在开始执行前，一次性申请其所需的全部资源。若所有资源均能满足，则分配；否则，一个资源也不分配，进程等待。*方法二：进程在需要新资源时，必须先释放已持有的全部资源，然后重新申请包括所需新资源在内的所有资源。*缺点：资源利用率低，可能导致大量进程饥饿。3.不可剥夺条件（NoPreemption）：进程已获得的资源在未使用完毕之前，不能被其他进程强行夺走，只能由该进程主动释放。*预防措施：当一个持有某些资源的进程请求新的资源而无法得到满足时，释放其已持有的所有资源，待以后需要时再重新申请。*缺点：实现复杂，可能造成前序工作的丢失，尤其是对某些资源（如打印机打印到一半）。*预防措施：对系统中的所有资源类型进行编号，并规定进程必须按资源编号递增的顺序申请资源。这样可以确保资源请求序列是线性的，从而避免了循环等待。*缺点：资源编号固定，限制了进程对资源的灵活申请；可能导致某些资源长期闲置，降低资源利用率。总结：预防死锁的思路是至少破坏四个必要条件中的一个。但每种方法都有其优缺点，实际系统设计中需权衡利弊。例题4：银行家算法（死锁避免）题目：某系统有同类资源m个，被n个进程共享。假设每个进程最多需要k个该类资源。试问：当m、n、k满足什么条件时，系统一定不会发生死锁？请说明理由。解析：要保证系统一定不会发生死锁，即无论进程如何请求资源，总能找到一种资源分配序列使所有进程都能顺利完成。思考角度：最坏情况下，每个进程都已经获得了尽可能多的资源，但仍差一个资源就能完成。此时，如果系统中还有至少一个资源可供分配，那么这个资源分配给任何一个进程，该进程就能完成并释放其所有资源，从而使其他进程也能获得足够资源。*每个进程最多需要k个资源。最坏情况下，每个进程已分配(k-1)个资源。*n个进程总共已分配n*(k-1)个资源。*如果系统此时还有至少1个资源剩余(m-n*(k-1)≥1)，那么这个剩余资源可以分配给任意一个进程，使其得到k个资源而顺利完成。该进程完成后释放其所有k个资源，系统剩余资源变为(m-n*(k-1)-1)+k=m-n*(k-1)+(k-1)=m-(n-1)*(k-1)。此时，剩余资源足以分配给其他进程。*因此，为保证不发生死锁，需满足：m≥n*(k-1)+1。结论：当m≥n*(k-1)+1时，系统一定不会发生死锁。三、内存管理内存管理主要涉及内存的分配与回收、地址重定位、虚拟内存等技术。例题5：分页存储管理题目：在分页存储管理系统中，已知页面大小为固定值，逻辑地址结构为：页号P|页内偏移量W。若给定逻辑地址A，如何计算其对应的页号和页内偏移量？若页表起始地址为PTBR，页表项长度为e，如何计算该逻辑地址对应的物理块号？并简述地址转换过程。解析：分页系统中，逻辑地址是连续的，被划分成大小相等的页（Page），物理内存被划分成与页大小相等的物理块（Block/Frame）。1.计算页号(P)和页内偏移量(W)：*设页面大小为L字节，通常L是2的幂次方，例如L=2^k字节。*逻辑地址A是一个无符号整数。*页内偏移量W=AmodL。它表示该地址在页面内的相对位置。由于L是2^k，modL运算等价于取A的低k位二进制数。*页号P=AdivL(或A>>k)。它表示该地址所在的页面编号。等价于取A的高(m-k)位二进制数，其中m是逻辑地址的总位数。2.计算物理块号并进行地址转换：*页表（PageTable）是用于记录逻辑页号到物理块号映射关系的数据结构，每个进程一张页表。*页表基址寄存器（PTBR）存放当前运行进程的页表在内存中的起始地址。*页号P作为页表的索引。第P个页表项（PTE）的起始地址为：PTBR+P*e。*从该页表项中可以读取到该逻辑页所对应的物理块号(F)。若页表项中存在有效位（或存在位），需先检查该位是否为1，以确认页面是否在内存中（若无，则发生缺页中断）。*物理地址(PA)的计算公式为：PA=F*L+W。由于W小于L，它直接作为物理块内的偏移量。地址转换过程简述：1.CPU产生逻辑地址A。2.将A分解为页号P和页内偏移W(P=A>>k,W=A&(L-1),其中L=2^k)。3.检查P是否超过页表长度（即是否为有效的页号），若无效则产生地址越界中断。4.以P为索引，访问页表寄存器(PTBR)指向的页表，找到对应的页表项(PTE)。5.检查PTE中的存在位（有效位）。若为0，表示页面不在内存，发生缺页中断，由操作系统处理。6.若存在位为1，从PTE中取出物理块号F。7.计算物理地址PA=F*L+W。8.将PA送往内存地址总线，进行实际内存访问。四、文件系统文件系统负责文件的组织、命名、存储、访问和管理。例题6：索引文件的物理结构题目：某文件系统采用混合索引分配方式组织文件的数据块。其中，FCB（文件控制块）中包含10个直接索引项、1个一级间接索引项、1个二级间接索引项和1个三级间接索引项。假设磁盘块大小为B字节，每个磁盘块号占b字节。请计算该文件系统支持的单个文件最大长度是多少？解析：混合索引分配是综合利用直接索引、一级间接索引、二级间接索引和三级间接索引来定位文件数据块的方法。其核心思想是通过索引块来扩展对文件数据块的寻址能力。*磁盘块大小为B字节，每个磁盘块号占b字节。因此，一个磁盘块中最多可以存放(B/b)个磁盘块号（索引项）。记N=B/b。N是每级间接索引块所能指向的下一级块的数量。1.直接索引：FCB中有10个直接索引项，每个直接指向一个数据块。*数据块数=10*可寻址文件大小=10*B2.一级间接索引：FCB中有1个一级间接索引项，它指向一个一级间接索引块。该索引块中存放的是若干个直接指向数据块的块号。*一级间接索引块可指向的数据块数=N=B/b*可寻址文件大小=N*B=(B/b)*B3.二级间接索引：FCB中有1个二级间接索引项，它指向一个二级间接索引块。该索引块中存放的是若干个指向一级间接索引块的块号，每个