《操作系统》期末考试卷及答案

《操作系统》期末考及答案一、单项选择题（每题2分，共20分）1.在进程状态转换中，不可能发生的转换是（）A.运行态→就绪态B.就绪态→运行态C.阻塞态→运行态D.阻塞态→就绪态2.某系统采用可变分区存储管理，当前内存分配表中记录的空闲分区为（100KB,200KB）、（300KB,150KB）、（500KB,100KB），若要为一个180KB的进程分配内存，采用最佳适应算法会选择的分区是（）A.100KB起始的200KB分区B.300KB起始的150KB分区C.500KB起始的100KB分区D.无法分配3.以下关于线程的描述中，错误的是（）A.同一进程的线程共享进程的地址空间B.线程是CPU调度的基本单位C.引入线程会增加进程切换的开销D.线程可分为用户级线程和内核级线程4.某页式虚拟存储系统中，页大小为4KB，逻辑地址空间为32位，则页号占（）位A.10B.12C.20D.225.下列磁盘调度算法中，可能导致“饥饿”现象的是（）A.先来先服务（FCFS）B.最短寻道时间优先（SSTF）C.扫描算法（SCAN）D.循环扫描算法（CSCAN）6.文件系统中，文件的逻辑结构若采用记录式结构，其基本单位是（）A.字节B.块C.记录D.扇区7.信号量机制中，P操作（wait操作）的本质是（）A.释放资源B.申请资源C.更新信号量值D.唤醒阻塞进程8.死锁的四个必要条件中，通过“资源有序分配法”可以破坏的是（）A.互斥条件B.请求和保持条件C.不可抢占条件D.循环等待条件9.在I/O控制方式中，CPU利用率最高的是（）A.程序直接控制方式B.中断驱动方式C.DMA方式D.通道控制方式10.以下关于虚拟内存的描述，错误的是（）A.虚拟内存扩大了物理内存的容量B.虚拟内存通过离散分配方式实现C.需要页表或段表支持地址转换D.可能导致“抖动”现象二、填空题（每空1分，共15分）1.操作系统的主要功能包括处理机管理、（）、文件管理、设备管理和用户接口。2.进程的三种基本状态是运行态、（）和阻塞态。3.时间片轮转调度算法中，时间片的长度应略大于（）的时间，否则会增加进程切换开销。4.内存分配的连续分配方式包括单一连续分配、固定分区分配和（）。5.页表的作用是实现（）到物理地址的映射。6.虚拟内存的理论基础是（）原理，包括时间局部性和空间局部性。7.文件的物理结构主要有顺序结构、（）和索引结构三种。8.设备管理中的SPOOLing技术通过（）实现了虚拟设备功能。9.死锁预防的策略包括破坏互斥条件、破坏请求和保持条件、破坏不可抢占条件和（）。10.某系统有3个同类资源，被2个进程共享，每个进程最多需要2个资源，则系统（）（填“会”或“不会”）发生死锁。11.在磁盘访问时间中，（）是指磁头移动到指定磁道所需的时间。12.信号量S的初值为2，执行两次P操作后，S的值为（）；若此时有3个进程申请该资源，其中（）个进程会进入阻塞队列。13.目录管理的关键是实现（），即通过路径名快速找到文件的索引节点。三、简答题（每题6分，共30分）1.简述进程与线程的主要区别。2.说明请求分页存储管理中缺页中断的处理流程。3.比较FCFS和SSTF磁盘调度算法的优缺点。4.解释文件系统中“文件控制块（FCB）”的作用及主要包含的信息。5.举例说明如何利用信号量机制解决两个进程的互斥问题。四、综合题（共35分）1.（10分）某系统采用优先级调度算法（优先级数值越小优先级越高），忽略进程调度开销，现有4个进程P1-P4，到达时间和服务时间如下表所示：|进程|到达时间（ms）|服务时间（ms）|优先级||------|----------------|----------------|--------||P1|0|8|3||P2|1|4|1||P3|2|5|4||P4|3|3|2|（1）画出进程调度的甘特图；（2）计算平均周转时间（周转时间=完成时间-到达时间）。2.（10分）某虚拟存储系统的逻辑地址为16位，页大小为1KB，页表如下所示（页表项中“存在位”为1表示页面在内存中，“物理块号”单位为KB）：|页号|存在位|物理块号||------|--------|----------||0|1|5||1|0|8||2|1|3||3|1|7|（1）逻辑地址0x3A5（十六进制）对应的页号和页内偏移量是多少？（2）该地址是否会产生缺页中断？说明理由；（3）若产生缺页中断，简述处理流程；若不产生，计算对应的物理地址（十六进制）。3.（15分）某银行自动取款机（ATM）有2台，同时最多允许2个用户使用。用户需要先在取号机取号（取号操作互斥），然后等待叫号。当ATM空闲时，叫号系统从等待队列中选择一个用户使用ATM。请：（1）定义实现该场景所需的信号量（包括名称、初值及含义）；（2）用伪代码描述用户进程的执行流程（包含取号、等待叫号、使用ATM、释放ATM的过程）；（3）说明如何避免用户取号后长时间无法被叫号的问题。---答案及解析一、单项选择题1.C解析：阻塞态的进程需要等待事件完成（如I/O结束）后才能转换为就绪态，无法直接转换为运行态。2.A解析：最佳适应算法选择满足需求且最小的空闲分区。180KB需要分区大小≥180KB，可用分区中200KB是最小的满足条件的分区（100KB起始的200KB分区）。3.C解析：线程共享进程资源，进程切换需要切换地址空间，而线程切换只需切换线程上下文，因此线程切换开销更小。4.C解析：页大小4KB=2¹²B，逻辑地址32位，页号占32-12=20位。5.B解析：SSTF优先处理最近磁道的请求，可能导致某些远磁道请求长期得不到服务（饥饿）。6.C解析：记录式文件的逻辑结构以记录为基本单位，如数据库中的一条记录。7.B解析：P操作通过减少信号量值申请资源，若信号量≤0则阻塞进程。8.D解析：资源有序分配法要求进程按固定顺序申请资源，破坏循环等待条件。9.D解析：通道控制方式由通道独立处理I/O操作，CPU仅需启动和结束时干预，利用率最高。10.A解析：虚拟内存并未扩大物理内存容量，而是通过逻辑地址空间扩展了程序可用的内存范围。二、填空题1.内存管理2.就绪态3.一次中断处理4.动态分区分配5.逻辑地址（页号）6.局部性7.链式结构（链接结构）8.磁盘缓存（输入井/输出井）9.破坏循环等待条件10.不会解析：最大需求总和=2+2=4≤3+1（系统资源+1），根据银行家算法，存在安全序列。11.寻道时间12.0；1解析：初始S=2，两次P操作后S=0；第三个进程执行P操作时S=-1，进入阻塞队列。13.按名存取三、简答题1.进程与线程的主要区别：（1）资源分配：进程是资源分配的基本单位，线程共享进程资源；（2）调度：线程是CPU调度的基本单位；（3）并发性：同一进程的线程间并发开销更小；（4）独立性：进程间独立性强，线程间共享地址空间；（5）开销：线程创建/切换开销小于进程。2.请求分页缺页中断处理流程：（1）CPU访问逻辑地址，查页表发现存在位为0，触发缺页中断；（2）保存当前进程现场；（3）检查页表项的外存地址，确定缺失页面位置；（4）若内存有空闲块，直接分配；否则选择淘汰页面（需换出修改过的页面到外存）；（5）将缺失页面从外存调入内存，更新页表存在位和物理块号；（6）恢复进程现场，重新执行引发中断的指令。3.FCFS与SSTF比较：FCFS：按请求顺序调度，公平无饥饿，但寻道时间长（尤其当请求分散时）；SSTF：优先处理最近磁道请求，平均寻道时间短，但可能导致远磁道请求饥饿（某些请求长期等待）。4.文件控制块（FCB）的作用及信息：作用：是文件存在的标志，包含文件的基本信息，用于文件系统管理文件。主要信息：（1）基本信息（文件名、文件类型、文件物理位置）；（2）存取控制信息（文件主权限、用户权限）；（3）使用信息（创建时间、修改时间、访问次数）。5.信号量解决两进程互斥示例：定义互斥信号量mutex，初值为1。进程A：while(1){P(mutex);//申请临界区临界区操作;V(mutex);//释放临界区}进程B：while(1){P(mutex);临界区操作;V(mutex);}当一个进程进入临界区时，mutex减为0，另一进程执行P操作会阻塞，直到前一进程释放mutex（V操作），确保互斥访问。四、综合题1.（1）甘特图：0-1ms：P1运行（唯一到达进程）；1ms：P2到达（优先级1最高），抢占P1；1-5ms：P2运行（服务4ms，完成时间5ms）；5ms：就绪队列有P1（剩余7ms）、P3（到达2ms，服务5ms）、P4（到达3ms，服务3ms），优先级P4（2）>P1（3）>P3（4）；5-8ms：P4运行（服务3ms，完成时间8ms）；8ms：就绪队列有P1（剩余7ms）、P3（剩余5ms），P1优先级3高于P3的4；8-15ms：P1运行（剩余7ms，完成时间15ms）；15ms：P3运行（服务5ms，完成时间20ms）。甘特图时间线：0-1(P1),1-5(P2),5-8(P4),8-15(P1),15-20(P3)（2）周转时间计算：P1：15-0=15ms；P2：5-1=4ms；P3：20-2=18ms；P4：8-3=5ms；平均周转时间=(15+4+18+5)/4=42/4=10.5ms2.（1）逻辑地址0x3A5=二进制1110100101（16位），页大小1KB=2¹⁰B，页号占高位6位（16-10=6），页内偏移占10位。0x3A5的二进制为001110100101，前6位（001110）=14（页号），后10位（10100101）=0xA5（偏移量）。（2）页号14是否在页表中？题目页表页号0-3，说明逻辑地址空间页号范围0-3（因为16位地址，页大小1KB，总页数=2¹⁶/2¹⁰=64页，页号0-63），但题目页表仅给出0-3页的信息，假设页号14对应的页表项存在位为0（题目未明确，需按常规判断）。或可能题目页表为部分页表，实际逻辑地址0x3A5=933（十进制），页号=933/1024=0（整数除法），页内偏移=933%1024=933。此时页号0的存在位为1，不会缺页。（注：原题可能存在页号计算歧义，正确计算应为页号=逻辑地址/页大小=0x3A5/0x400=0（十六进制0x3A5=933，0x400=1024，933<1024，页号0）。（3）页号0存在位为1，物理块号5（单位KB），物理地址=51024+933=50x400+0x3A5=0x1400+0x3A5=0x17A5（十六进制）。3.（1）信号量定义：-mutex：初值1，用于取号机的互斥访问；-atm：初值2，表示可用ATM数量；-wait_queue：初值0，用于用户等待叫号（或直接用atm的P/V操作管理