上海大学《操作系统》期末试卷（A卷）

上海大学《操作系统》期末试卷（A卷）2023—2024学年第一学期计算机科学与技术专业闭卷考试时间120分钟满分100分姓名学号专业班级考试日期题号一二三四五总分复核满分3010102030100—得分考生须知：本卷为闭卷考试，不得携带教材、笔记、纸条及任何电子设备。选择题、填空题、判断题的答案写在答题纸（卡）指定位置，写在试卷上无效。计算与设计题须写出必要的步骤、依据和结论，只写答案不得满分。编制说明：公开渠道未检索到2023年该课程A卷原卷全文，本卷依据上海大学计算机科学与技术专业《操作系统》课程的教学范围（汤小丹《计算机操作系统》体系）与同年份常见题型结构、分值分布还原命题，供复习自测使用，不代表原卷。一、单项选择题（共15小题，每小题2分，共30分）在每小题给出的四个选项中，只有一个选项符合题目要求，请将所选字母填入题后括号内。1．操作系统的四个基本特征是（）

A．并发、共享、虚拟、异步B．并发、实时、虚拟、异步

C．并行、共享、分时、异步D．并发、共享、虚拟、实时2．下列各项中，不属于进程基本特征的是（）

A．动态性B．并发性C．独立性D．永久性3．下列进程状态转换中，正常情况下不可能发生的是（）

A．就绪→运行B．运行→就绪

C．运行→阻塞D．阻塞→运行4．在分时系统中，为使多个终端用户都能获得及时响应，最适宜的进程调度算法是（）

A．先来先服务B．短作业优先

C．时间片轮转D．高响应比优先5．若信号量S的当前值为−3，则表明（）

A．有3个进程正在使用该资源B．该资源共有3个

C．有3个进程在该信号量的等待队列中D．有3个进程即将释放该资源6．用PV操作实现进程互斥时，互斥信号量的初值应设为（）

A．0B．1C．−1D．临界资源的个数7．下列选项中，不属于产生死锁的必要条件的是（）

A．互斥条件B．请求并保持条件

C．不可剥夺条件D．进程优先级相同8．银行家算法用于（）

A．死锁的预防B．死锁的避免

C．死锁的检测D．死锁的解除9．在分页存储管理中，页表的主要作用是（）

A．记录进程的逻辑地址B．实现页号到物理块号的转换

C．记录内存空闲区的分配情况D．实现页面的置换10．在其他条件相同的情况下，页面尺寸增大，通常会使（）

A．页表项减少，页内碎片增大B．页表项增多，页内碎片增大

C．页表项减少，页内碎片减小D．页表项增多，页内碎片减小11．下列页面置换算法中，可能出现Belady异常的是（）

A．LRUB．OPTC．FIFOD．Clock12．在采用索引结点（inode）的文件系统中，文件名通常存放在（）

A．索引结点中B．目录项中

C．超级块中D．文件的第一个数据块中13．与连续分配相比，链接分配的主要缺点是（）

A．不能顺序访问文件B．不支持文件的动态增长

C．随机访问效率低D．会产生外部碎片14．下列磁盘调度算法中，可能导致某些请求长期得不到服务的是（）

A．先来先服务B．最短寻道时间优先

C．扫描算法D．循环扫描算法15．SPOOLing系统的主要作用是（）

A．把独占设备改造为可供多个进程共享的虚拟设备

B．提高CPU的主频

C．减少内存占用

D．实现设备的即插即用二、填空题（共10空，每空1分，共10分）16．进程控制块PCB是进程存在的唯一标志；进程切换时，必须保存和恢复的主要是进程的________。17．若系统中有n个进程共享一台打印机，用信号量实现互斥，则该信号量S的取值范围是________。18．死锁定理指出，系统处于死锁状态的充分条件是资源分配图________。19．在分页存储管理中，逻辑地址由页号和________两部分组成。20．设页面大小为4KB，则逻辑地址0x2A1F（十进制10783）对应的页号是________。21．在请求分页系统中，若被淘汰的页面在内存中曾被修改过，则必须先将它________。22．为实现文件共享，可在目录项中存放指向同一索引结点的________。23．磁盘访问时间由寻道时间、旋转延迟时间和________三部分组成。24．在I/O控制方式中，以数据块为单位、由控制器直接在主存与设备之间传送数据的是________方式。25．文件系统中，用于记录磁盘空闲块且便于大容量磁盘管理的方法是________。三、判断题（共10小题，每小题1分，共10分）判断下列说法是否正确，正确的写“正确”，错误的写“错误”。26．线程是资源分配的基本单位，进程是处理机调度和执行的基本单位。（）27．采用抢占式调度比非抢占式调度的系统开销更小。（）28．当系统中所有进程都处于阻塞状态时，处理机处于空闲状态。（）29．信号量的值小于0时，其绝对值等于等待在该信号量上的进程数目。（）30．死锁预防是通过破坏产生死锁的四个必要条件之一来防止死锁发生的。（）31．分页系统中每个进程有一张页表，页表寄存器中存放该页表的始址和长度。（）32．引入虚拟存储器后，进程的逻辑地址空间可以大于内存的物理地址空间。（）33．页面尺寸越大，系统的缺页率一定越低。（）34．采用树形目录结构后，同一文件在不同目录下也不能重名。（）35．磁盘的寻道时间取决于磁头当前所在磁道与目标磁道之间的距离。（）四、简答题（共4小题，每小题5分，共20分）36．简述进程与线程的主要区别（至少列出四点）。37．简述请求分页系统中的地址变换过程，并说明产生缺页时系统的处理步骤。38．简述死锁与饥饿的区别。39．简述SPOOLing系统的组成及工作过程。五、综合应用题（共3小题，共30分）40．（10分）某系统用有界缓冲区存放产品，缓冲区最多可存放n个产品。生产者进程不断生产产品并放入缓冲区，消费者进程不断从缓冲区取出产品消费。要求：（1）定义所需的信号量，说明每个信号量的物理含义与初值；（2）用PV操作写出生产者进程和消费者进程的程序（可用while(1)循环描述）；（3）说明生产者程序中两个P操作的先后顺序为什么不能颠倒。41．（10分）某请求分页系统页面大小为1KB，为某进程分配3个物理块，该进程的页面访问次序为：2，3，2，1，5，2，4，5，3，2，5，2。要求：（1）设初始时内存为空，分别求FIFO和LRU两种置换算法下的缺页次数与缺页率；（2）若逻辑地址为2500（十进制），页号2对应的物理块号为6，求该逻辑地址的页号、页内偏移和物理地址。42．（10分）某系统有A、B、C三类资源，当前可用资源Available=（3，3，2），5个进程的已分配资源Allocation与尚需资源Need如下表所示。要求：进程Allocation（A，B，C）Need（A，B，C）P00，1，07，4，3P12，0，01，2，2P23，0，26，0，0P32，1，10，1，1P40，0，24，3，1（1）系统当前是否处于安全状态？若是，给出一个安全序列，并写出安全性检查过程；（2）若此时P4提出资源请求Request=（3，3，0），系统能否立即满足该请求？说明理由。参考答案与评分标准选择题、填空题、判断题按标准答案给分，不倒扣；简答题按要点给分，答出关键含义即可得分，表述完整、逻辑清晰可给满分；综合应用题按步骤给分，结论错误但过程正确可给步骤分。一、单项选择题（每小题2分，共30分）题号答案解析1A操作系统的基本特征是并发、共享、虚拟、异步。“实时”是操作系统的一种类型，不是基本特征；“并行”与“并发”含义不同。2D进程有创建、就绪、运行、阻塞、终止的生命周期，动态性是它与程序的根本区别，不存在“永久性”这一特征。3D阻塞进程必须等待所等事件发生（如I/O完成）先转为就绪，再由调度程序选中才能运行，不能由阻塞直接转为运行。4C时间片轮转让每个就绪进程轮流获得一个时间片，保证各终端用户的响应时间；FCFS、SJF都会使部分用户等待过久。5CS<0时，其绝对值表示在该信号量等待队列中阻塞的进程数；S≥0时表示尚可用的资源数目。6B互斥信号量初值为1，表示临界资源只有一个，同一时刻仅允许一个进程进入临界区。7D四个必要条件是互斥、请求并保持、不可剥夺、循环等待；进程优先级高低与是否发生死锁无关。8B银行家算法在每次分配前试算并判断系统是否仍处于安全状态，属于死锁避免策略。9B页表项记录页号对应的物理块号及状态位等，地址变换时以页号查页表得到块号，再与页内偏移拼接。10A页面增大则页数减少，页表项随之减少；而每页最后一页平均浪费的内部碎片增大。11CFIFO可能出现物理块增多而缺页率反而上升的Belady异常；LRU、OPT属堆栈型算法，不会出现该异常。12B索引结点集中存放文件类型、大小、物理地址、链接计数等属性，文件名保存在目录项中，便于按名查找与硬链接共享。13C链接分配用指针把盘块串联，只能顺序访问，访问第i块须从头遍历；它支持动态增长，也不产生外部碎片。14BSSTF总选距当前磁头最近的请求，远处请求可能被不断到来的近处请求“插队”而长期得不到服务；SCAN、C-SCAN按方向扫描，可保证有限等待。15ASPOOLing借助输入井、输出井把独占设备虚拟成多进程可共享的设备，即虚拟设备技术。二、填空题（每空1分，共10分）16．现场信息（处理机状态，即CPU各寄存器内容和程序状态字等）17．1～−(n−1)（即初值1，最多有n−1个进程在等待）18．不可完全简化19．页内偏移（页内地址）20．2（10783÷4096=2余2591，故页号2，页内偏移2591）21．写回磁盘（换出到外存）22．索引结点编号（指针）23．传输时间24．DMA（直接存储器访问）25．位示图（位图）三、判断题（每小题1分，共10分）题号答案解析26错误说反了：进程是资源分配的基本单位，线程是处理机调度和执行的基本单位。27错误抢占式调度需要时钟中断、现场保护、调度判断等额外工作，系统开销更大。28正确没有就绪进程时调度程序无可选对象，处理机无事可做而空闲（实际系统中运行空闲进程）。29正确S的绝对值即等待队列中的进程数目，这是记录型信号量的基本含义。30正确预防策略就是至少破坏四个必要条件中的一个，如资源有序分配破坏循环等待。31正确每进程一张页表，页表寄存器存放页表始址与页表长度，后者用于逻辑地址的越界检查。32正确虚拟存储依靠部分装入、按需调入和页面置换，使逻辑地址空间可超过物理内存容量。33错误页面增大可减少页表项和缺页次数，但一次调入过多可能用不到的数据，缺页率也可能上升，并非必然降低。34错误树形目录中不同目录下允许有同名文件，只有“全路径名”才在整个系统中唯一。35正确寻道时间是磁头移动到目标磁道所需时间，与两者间跨越的磁道数（距离）正相关。四、简答题（每小题5分，共20分）36．参考答案（答出四点即可得5分，每点1.25分）地位不同：进程是资源分配的基本单位，拥有独立的地址空间和资源；线程是处理机调度和执行的基本单位，本身几乎不拥有资源。地址空间与共享：同一进程内的多个线程共享该进程的代码段、数据段和打开的文件等资源；不同进程的地址空间相互独立。切换开销不同：进程切换需切换页表、刷新TLB、保存完整现场，开销大；线程切换在同一地址空间内进行，只需保存少量寄存器，开销小。通信方式不同：进程间通信须借助管道、消息、共享内存等IPC机制；线程间可直接读写共享变量，但必须配合同步互斥。并发粒度与健壮性：线程创建、撤销更快，并发粒度更细；一个线程出错可能导致所属进程终止，而一个进程崩溃一般不影响其他进程。37．参考答案（5分）地址变换过程（2分）：把逻辑地址拆成页号P和页内偏移W；以P检索该进程的页表（页表项含存在位、访问位、修改位、物理块号和外存地址）；若存在位为1，则物理地址=物理块号×页面大小+W，并可按需填入快表（TLB）加速后续访问。缺页处理步骤（3分）：检查访问是否合法，非法则终止进程（越界或越权）。在内存中找一个空闲物理块；若无空闲块，按置换算法选一页淘汰。被淘汰页若修改位为1，先写回磁盘；否则可直接覆盖。从外存把所缺页面调入所选物理块，修改页表项（存在位置1、更新块号）并更新快表。恢复被中断进程的现场，重新执行引起缺页的那条指令。与基本分页的区别：基本分页要求所有页一次性全部装入内存，地址变换中不会产生缺页中断；请求分页按需调入，页表增加存在位、访问位、修改位和外存地址，并增设缺页中断机构与页面置换机制。38．参考答案（5分）死锁：两个或两个以上进程因争夺资源而相互等待对方释放，形成循环等待，若无外力干预，这一组进程都将永久阻塞、无法推进。它是“一组进程”之间的僵持，系统整体停滞。饥饿：某个进程因资源分配或调度策略不当，长期得不到所需资源（如低优先级进程的CPU总被高优先级进程抢占），但系统整体仍在运行，其他进程可以完成。主要区别（每点1分）：死锁涉及多个进程并存在循环等待；饥饿通常只涉及单个进程，不存在循环等待。死锁不借助外力无法解除；饥饿在策略改变或资源释放后可能自行解除。死锁时相关进程全部无法推进，系统可能整体瘫痪；饥饿时系统仍在推进。死锁属于资源竞争导致的永久阻塞；饥饿属于分配策略不公平导致的长期等待。39．参考答案（5分）组成（2分）：输入井和输出井（磁盘上的存储区域）、输入缓冲区和输出缓冲区（内存区域）、输入进程和输出进程（又称预输入进程、缓输出进程）、井管理程序。工作过程（2分）：用户进程输出数据时，先把数据写入输出井，由输出进程在设备空闲时依次把输出井中的数据送到设备输出；用户进程输入数据时，由输入进程提前把设备上的数据读入输入井，用户进程再从输入井读取。整个过程由井管理程序负责井的申请、分配与释放。作用（1分）：把打印机一类独占设备改造成可供多个进程“同时”使用的共享设备（虚拟设备），使进程不必等待慢速设备，提高设备利用率和系统并行性。五、综合应用题（共30分）40．参考答案（10分）（1）信号量定义（3分，每个信号量含义与初值各0.5分）c

semaphoremutex=1;//互斥信号量，保证同一时刻只有一个进程访问缓冲区

semaphoreempty=n;//同步信号量，表示空闲缓冲区数目，初值为n

semaphorefull=0;//同步信号量，表示已有产品（满缓冲区）数目，初值为0（2）进程程序（5分，生产者2.5分、消费者2.5分；信号量使用正确但循环结构略有差异不扣分）c

voidproducer(){

while(1){

item=produce();//生产一个产品

P(empty);//申请一个空缓冲区，缓冲区满则等待

P(mutex);//进入临界区

buffer[in]=item;//放入产品

in=(in+1)%n;

V(mutex);//退出临界区

V(full);//产品数加1，唤醒等待的消费者

}

}

voidconsumer(){

while(1){

P(full);//申请一个产品，缓冲区空则等待

P(mutex);//进入临界区

item=buffer[out];//取出产品

out=(out+1)%n;

V(mutex);//退出临界区

V(empty);//空缓冲区数加1，唤醒等待的生产者

consume(item);//消费产品

}

}（3）顺序不能颠倒的原因（2分）生产者必须先执行P(empty)再执行P(mutex)。若颠倒为P(mutex)后P(empty)：当缓冲区已满时，生产者已占有mutex并阻塞在empty上；此时消费者要取产品，必须先执行P(mutex)，但mutex被生产者占用，消费者也被阻塞。双方互相等待对方释放自己持有的资源，形成死锁。消费者同理，必须先P(full)再P(mutex)。两个V操作的先后不影响正确性，但一般先V(mutex)释放临界区再V同步信号量。41．参考答案（10分）（1）缺页次数与缺页率（6分，每种算法3分：过程2分、结果1分）页面大小为1KB，访问串共12次。FIFO的置换过程如下（“是”表示缺页）：访问次序123456789101112访问页号232152453252内存块内容22,32,32,3,13,1,51,5,25,2,45,2,42,4,32,4,34,3,53,5,2是否缺页是是否是是是是否是否是是FIFO在第1、2、4、5、6、7、9、11、12次访问时缺页，共9次，缺页率=9÷12=75%。LRU的置换过程如下（每次淘汰最久未被访问的页）：访问次序123456789101112访问页号232152453252内存块内容22,32,32,3,12,1,51,5,25,2,42,4,54,5,35,3,23,2,53,5,2是否缺页是是否是是否是否是是否否LRU在第1、2、4、5、7、9、10次访问时缺页，共7次，缺页率=7÷12≈58.3%。结论：本访问串下LRU优于FIFO，说明置换算法直接决定缺页率高低。（2）地址转换（4分）页面大小为1KB=1024B。页号P=2500÷102