1、四川大学计算机操作系统试题四川大学 2000 年攻读硕士学位研究生入学考试试题操作系统部分（共 30 分）一、单项选择题（在下列四个备选答案中，选出一个正确答案，填在园括号中；每小题1 分，共 6分）1、动态式（或称可变式）分区管理的分配策略中的首次适应算法采用（A ）A 、按始址递增排列空闲区B、按始址递减排列空闲区C、按分区大小递增排列空闲区D、任意排列空闲区2、下列关于索引表的叙述， （ B）是正确的。A、索引表中每个记录的索引项可以有多个B、对索引文件存取时，必须先查找索引表C、索引表中含有索引文件的数据及其物理地址D、建立索引表的目的之一是为减少存贮空间3、目标程序所对应的地址空间是
2、（ B ）A 、各空间B、逻辑地址空间C、存贮空间D、物理地址空间4、既考虑作业等待时间，又考虑作业执行时间的调度算法是（B）A 、响应比高者优先B、短作业优先C、优先级调度D、先来先服务5、对一个文件的访问，常用（A ）共同控制A 、用户访问权限和文件属性B、用户访问权限和用户优先级C、优先级和文件属性D、文件属性和口令6、地址重定位的对象是（ D）A 、源程序B、编译程序C、目标程序D、执行程序二、填空题（每小题1分，共 6分）1、操作系统具有的四个基本特征是并发、共享、 虚拟、 异步。2、存贮器管理应具有以下的功能：内存分配、 内存保护、 地址映射、内存扩充。3、文件管理的基本功能有存储
3、空间管理、 目录管理、读写管理、。4、记录型信号量机制中， S Value0 时的值表示目前可用资源的数目，每次 P 操作意味着进程申请资源；若 SValue 0，则表示目前无可用资源，此时进程应阻塞。5、Spooling 系统是由磁盘中的输入井和 输出井，内存中的输入缓冲和输出缓冲以 及和输入进程和输出进程 所构成。6、为实现消息缓冲通信，在 PCB 中应增加 消息队列首地址 MQ 、 消息队列互斥量 MUTEX 和SM 消息队列资源信号量 三个数据项。三、解释术语（每个 2 分，共 6 分）1、虚拟存贮器 2、多道程序设计 3、内核虚拟存储器：具有请求调入和置换功能，能从逻辑上对内存容量加
4、以扩充的存储器系统称虚拟存储器。多道程序设计：在内存中同时存放若干个作业，让它们共享系统资源且并发运行的技术。四、简答题（每个 4 分，共 12 分）11、试归纳出在操作系统中引起进程调度可能有的原因有哪些？2、某虚拟存贮器的用户空间有 32 个页面，每页 1KB ，主存 16KB 。假定某时刻，系统为用户的第 0，1，2， 3 页分别分配的物理块号为 5，10，4，7，试将虚拟地址（ 16 进制） OAFC和 OE7B 变换为物理地址（仍用 16 进制数），并要给出简要的变换步骤。0AFC 0000 1010 11111100 第 2 页对应物理块号为 4，所以物理地址为 010010 11
5、111100 0x12FC 0E7B=0000 11 10 0111 1011 页号为 3 物理块号为 7 111 10 1111 11001E7C3、现有两个进程共享一个缓冲区（其大小为 1），完成一批（共 n 个）数据的处理任务，其中计算进程 CP 向缓冲区送数据，打印进程 PRT 从该缓冲区取数据，试利用信号实现这两个进程的同步（要求用一种结构化程序设计语言（类似）程序描述） 。2001 年读硕士学位研究生入学考试试题操作系统试题（ 30 分）1分，共 6一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案。每小题分）1、引入多道程序技术的前提条件之一是系统具有：3多个 CPU多
6、个终端中断功能分时功能2、一个进程释放了一台打印机后，有可能改变什么进程的状态：3自身进程输入 /输出进程另一个等待打印机的进程所有等待打印机的进程3、请求分页存贮管理的主要特点是：4消除了页内零头 便于动态链接便于信息共享扩充了主存4、在下列问题中，哪一个不是设备分配中应考虑的问题：1及时性设备的固有属性与设备无关性安全性5、设置当前目录的主要原因是： 2节省主存空间加快文件查找速度解决文件的重名和共享实现统一的目录管理6、死锁产生的原因之一是： 4系统中没有采用 Spooling 技术使用 PV 操作过多有共享资源存在资源分配不当二、判断改错题（每小题 2 分，共 6 分）1、假定有一组作
7、业（或进程） ，它们提交时间及要求运行的时间如下表所示（单位为小时，并以十进制计）作业号提交时间运行时间18.002.028.500.539.000.149.500.2T=1.725如果采用最短作业（或进程）优先调度算法，计算出该组作业的平均周转时间和平均带权周转时间 W=6.875。对吗？为什么？作业允许顺序 1342,完成时间分别为 10.0 10.1 10.3 10.8 周转时间分别为 2.0 1.1 0.8 2.3平均周转时间为 (21.1+0.8+2.3)/4=1.55平均带权周转时间（ 2/2+1.1/0.1+0.8/0.2+2.3/0.5）/4=5.152、某虚拟存贮器的用户空间
8、共有 32 个页面，每页 1KB ，主存 16KB 。假定某时刻，系统2为用户的第 0，1，2，3 页分配的物理块号分别为 5，10， 4， 7。有人将虚拟地址 OA5C （16进制数）变换成物理地址 125C（ 16 进制数），对吗？为什么？对的：3、判断下述同步算法的正确否？若有错，则要求改正。设 A ，B 为两个并发进程，它们共享一临界资源，其执行临界区的算法框图如下所示，其中设定的信号量 S1，S2 的初值均为0。三、术语解释（每小题 2 分，共 6 分）1、作业调度与进程调度作业调度：从后备队列选择作业调入内存， 并为其分配所需资源， 并挂在就绪队列上：进程调度：在多道程序环境下，内
9、核利用某种算法从就绪队列上选取进程，并分配，CPU 使他运行。2、零头与拼接零头：内存中出现许多容量太小导致无法利用的内存块拼接：移动分配区的内容，使所有作业的分区紧挨在一起，把空闲区留在另一段。3、Spooling四、简答题（每小题4 分，共 12 分）1、根据下面的并发执行程序，给出前趋图beginpsrbeginVara， b， c，d，e，f ，g：Semphore:= 0，0，0，0，0，0，0beginS1：V （a）：V （b）：end：beginP（a）：S2：V （ c）：V （d）：end：beginP（b）：S ： V（ e）：end：3beginP（c）：S4：V （
10、f）：end：beginP（d）：S5： V（ g）：end：beginP（e）：P（f）：P（ g）：S ： end：6Parendend2、可以通过哪些途径来提高内存的利用率？3、目前广泛采用的目录结构形式是哪种？它有什么优点？2001 操作系统试题答案一、单选题（每小题 1 分，共 6 分）1、 2、 3、 4、 5、 6、二、判断改错题（每小题 2分，共 6分）1、错。因为按最短作业优先调度算法，作业运行次序是作业 1，3，4，2 计算得的平均周志 T=1.55 和平均带权周转时间 W=5.1532、对。因为按地址变换规则计算如下：将逻辑地址 OA C 变成页号 P=（00010） 2
11、；W= （ 1001011100）2。（二进制表示）由页号 P 查出对应的块号 4，写成二进制形式为（00100） 2。将块号与 W 拼接成二进制形式：0 0 1 00100101110 0，写成 16 进制为 125C 即得3、错。因为 A ，B 两进程共享一个临界资源，必须互斥使用，设置一个公用（互斥）信号量 mutex=1（初值），算法框图如下所示：三、术语解释（每个 2 分，共 6 分）1、作业调度是指从后备队列上选择哪些作业调入内荐，分配其所需资源，然后将它挂在就绪队列上。而进程调度是指在多道程序环境下，内核按一定的调算法，从就绪队列中选出一进程，把处理机分配给它，让其运行。2、零头
12、是指在存贮管理中，内存出现许多容量太小，无法被利用的小区域。拼接是指移动某些已分配区的内容，使所有作业的分区紧挨在一起，而把空闲区留在另一端，这种技术叫拼接。3、Spooling 即同时联机外围操作，又称脱机操作。在多道程序环境下，可利用多道程序中的一道程序，来模拟脱机的输入输出功能，将独占设备改造为共享设备，实现虚拟设备功能。即在联机条件下，将数据从输入设备传送到磁盘，或从磁盘传送到输出设备。四、简答题（每小题 4 分，共 12 分）1、该程序对应的前趋图，如下所示42、可采用下述方法提高内存利用率：（1）改连续分配方式为离散分配方式，以减少内存的零头。（2）增加对换机制：将那些暂时不能运行
13、的进程，或暂时不需要的程序和数据，换出至外存，以腾出内存来装入可运行的进程。（3）引入动态链接机制：当程序在运行中需要调用某段程序时，才将该段程序由外存装入内存。这样可避免装入一些本次运行中不用的程序。（ 4）引入虚拟存贮机制，使更多的作业能被装入内存，并使 CPU 更加忙碌。（5）引入存贮器共享机制：允许一个正文段或数据段被若干个进程共享，以消灭内存中的重复拷贝。1、答：目前广泛采用的目录结构形式是树形目录结构，这具有以下优点：（1）能有效地提高对目录的检索速度；（2）允许文件重名：由于使用路径名检索文件，故用户在分目录中可使用其它用户相同文件名。（3）便于实现文件共享：包括不同用户用不同的
14、文件名访问同一个共享文件；比较容易实现文件共享。2002 年计算机学院攻读硕士学位研究生入学考试试题 操作系统一、单选题（在四个备选答案中， 选出一个正确的答案， 并将番号填在题干后的括号内）（每小题 1 分，共 6 分）1、提高单机资源利用率的关键技术是（ D ）A 、Spooling 技术 B、虚拟技术C、交换技术 D 、多道程序设计技术2、一进程基本状态可以从其它两种基本状态转变过去，这个基本状态一定是（C ）A 、执行状态B、阻塞状态C、就绪状态D、完成状态3、请求分页存贮管理的主要特点是（B）A 、消除了页内零点B、扩充了主存C、便于动态链接D 、完成状态4、当进程 A 使用磁带机时
15、，进程 B 又申请该磁带机，这种情况（ D）A 、是不可能出现的B、是没法解决的C、就是死锁D 、以上均不正确5、在下列问题中，哪一个不是设备分配应考虑的问题（C ）A 、设备的固有属性B、与设备无关性C、及时性D 、安全性6、文件系统是（ B）A 、文件的集合B、文件及文件管理软件的集合C、系统文件的集合D 、用户文件的集合二、填空题（每小题1分，共 6分）1、某页式存贮管理系统中，有效地址寄存器为16 位，其中低 98，13 号块中，向 1008号逻辑地址所对应的物理地址是。2、在上题 1 中，以 16 进制表达的逻辑地址01A2 所对应的物理地址是5。3、在一个请求页式系统中，假如一个作
16、业的页面走向为： 1，2，1，3，1，2，4，2，1，3， 4；分配给该作业的物理块数 M 为 2（初始为空，第一次缺页即算缺页次数） ，当用 FIFO置换算法时，所发生的缺而次数是 9 次。4、继续上题 3，再用 LRU 置换算法时，计算出访问过程中所发生的缺而次数是 8 次。5、如果利用 20 行，30 列的位示图来标志空闲盘块的状态，在进行盘盘块分配时，当第一次找到的空闲盘块（即该位置为 0）处于第 11 行，第 18 列，则相应的盘块号为318 。6、设有三个作业： J1，J2，J3 同时进入系统，其需要的处理时间以及各自的优先数分别为 24 单位， 1：3 单位， 2：6 单位， 3
17、 如果三个作业均为纯计算型，调度算法估用优先数大的优先，那么作业 J1从提交到完成的时间为单位。三、术语解释（每个1分，共 6分）1、临界区2、死锁3、系统调用4、复盖5、独享设备6、无结构文件：由字符流构成的文件。四、解答题（每小题4 分，共 12 分）1、设有一个飞机订票系统，有两终端，分别运行用户进程T1 和 T2，通过两个终端购票，若用 X 代表飞机票多少，试定出用 P， V 操作实现 T1，T2 售票管理的同步算法。2、对文件目录管理的要求是什么？一个目录表目（或文件控制块）应包含哪些类信息？3、试说明作业调度和进程调度之间的区别是什么？二者间如何协调工作？操作系统答案部分一、单选题
18、1、D2、C3、B4、D 5、C6、 B二、填充题1、45922、 0BA23、9 次4、8 次5、3186、 33 单位三、名词解释1、临界区：每个进程中访问临界资源的那段程序。2、死锁：指多个进程因竞争资源而造成的一种僵局，若无外力作用，这此进程都将永远不能再向前推进。3、系统调用：由操作系统提供的能完成一定功能的子程序，可供用户在编制程序中使用。4、复盖：指一个作业的若干程序段或几个作业的某些部分共享主存空间。5、独享设备：指一个用户或进程在使用期间不能为其它用户或者进程使用设备。如打印机等。四、简答题（每小题 4 分，共 12 分）1、解：设整型变量 X 代表飞机票的多少：互斥信号量
19、mutes=1（初值）：使用 P， V 操作的售票管理同步算法如下：Var mutex:semphore; mutex:=1;X: integer X:n;CobeginProcedure T1(X)beginP(mutex);read x;if X 1 then X:X-1;6V(mutex);andProcedure T2(X)beginP(mutex);readx;if X 1 then X:X=1;V(mutex);endcoend2、解：对文件管理的要求有：（1）实现“按名存取” ； （ 2）提高对目录检索的速度；（3）文件共享； （ 4）允许文件重名。一个目录表目包括的信息有：（1
20、）基本信息类：如文件名、文件物理地址、文件结构等；（2）存取控制信息：如文件主、核准用户、一般用户的存取权限；（3）使用信息类：如文件建立的日期、时间、大小以及当前使用信息等。3、解作业调度和进程调度的区别有：（1）作业调度为进程活动做准备，进程调度使进程活动起来；（2）作业调度次数少，进程调度频率高；（3）有的系统不设作业调度，但进程调度必不可少。二者间的协调工作是这样的：作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程来，并把它们的状态改为执行态，把 CPU 分配给它。当运行进程要等待某一事件时， 就让出 CPU，进入
21、相应的阻塞队列； 并进行进程调度。运行进程完成后，由作业调度进程善后处理工作。72003 年攻读硕士学位研究生入学考试试题考试科目：计算机基础（微机原理、 C 语言、操作系统、编译原理）科目代码： 867#适应专业：计算机系统结构、计算机软件与理论、计算应用技术操作系统试题（ 40 分）一、填空题（每小题 1 分，共 9 分）1在分时系统中进程从“执行就绪”状态的变化是由于 时间片用完 而引起，进程从“就绪执行”状态变化是由 进程调度 而引起。2在具有 n 个进程的系统中，允许 m 个进程（ n m1）同时进入它们的临界区，其信号量S 的值的变化范围是M-N=S=M。处于等待状态的进程数最多是
22、N-M个。3分段是信息的逻辑单位，分页则是信息的物理单位，两者在概念上是不同的。4在请求页式系统中， 当访问的页不在主存时， 由缺页中断处理程序将该页调入主存；当主存无空闲块时，必须换出一页。5引入操作系统的主要目的是提高资源利用率和方便用户。6将一台独享设备改造成共享设备， 是通过SPOOLING 程序模块完成的，需要有 大容量的后援存储器作支持。7采用多级目录可以解决文件的重命名，允许不同用户的文件取相同的的文件名。8系统中仅有两台磁带机分别为 P1， P2 两个进程占有，此时若两进程又分别申请对方占有的磁带机而处于阻塞状态，则进程P1，P2 进入 死锁状态。9为方便用户使用计算机，操作系
23、统向用户提供的接口有命令行和 程序接口；在新近的操作系统中还提供图形接口。二、简答题（每小题4 分，共 16 分）1简述页式存储管理和请求页式存贮管理有什么本质区别？2关于死锁的防止、避免和检测三者有什么不同？3试述文件在外存分配中的连续分配、链接分配和索引分配各自的主要优缺点是什么？4何谓多道程序设计？在操作系统中引入多道程序设计会带来什么好处？三、综合应用题（每小题5 分，共 15 分）1某单道程序设计系统中，三个作业A ，B，C 到达输入井的时间及需要的计算时间如下：作业名到达输入井时间需计算时间A8：501.5 小时B9：000.4 小时C9：301 小时当这三个作业全部到达输入井后，
24、系统以响应比最高者优先调度算法选择作业，忽略调度所用时间，则作业被选中的次序是怎样的？2试画出下面五条语句的前趋图：S1:a=5x; S2:b=a x; S3: c=4x; S4: d=b+c ; S5: e=d+3;并试用信号量的 P、V 操作实现上述语句的前趋关系，写出一个可并发执行的程序。3在采用分页存贮管理系统中，地址结构长度为 18 位，其中 11 至 17 位表示页号， 0 至 10位表示页内位移量。若有一作业的各页依次放入 2，3，7 号物理块中，试问：（1）主存容量最大可为多少 K ？分为多少块？每块有多大？（2）逻辑地址 1500 应在几号页内？对应的物理地址是多少？8操作系
25、统答案（共 40 分）一、填空题（每小题1分，共 9分）1时间片用完进程调度程序2 (n-m) smn-m3信息的逻辑单位信息的物理单位4缺页中断处理程序淘汰5方便用户提高资源利用率6 Spooling 程序模块大容量的后援存贮器7重名问题相同8死锁9命令接口 程序接口 图形接口二、简答题（每小题 4 分，共 16 分）1答：页式存贮管理是程序在逻辑上分页，主存分块。块的大小和页的大小相等，每块装入一页，用户程序在执行前全部装入主存。而请求页式存贮管理在分页和分块上同页式存贮管理，所不同的是请求页式存贮管理不要求将程序全部装入主存即可投入运行。即页式存贮管理要求全部装入，而请求页式只是部分装入
26、，然后采用部分替换技术。2答：三者的区别是：死锁的防止是通过破坏产生死锁的四个必要条件中的一个或多个条件，以确保系统不会产生死锁；死锁的避免是在产生一死锁的四个必要条件有可能成立时，即估计到系统可能要产生死锁时，采用其它方法以避免死锁的产生。死锁的检测则是允许系统进入死锁，定期检查系统是否已经产生死锁，若发生了死锁，再采用某种方法来解除死锁。3答：连续分配的优点是：顺序访问容易；顺序访问速度快。其缺点是：要求有连续的存贮空间，会产生碎片，降低利用率；须事先知道文件的长度，不利于文件的增生扩充。链接分配的主要优点是：不要求连续的存贮空间，能较好地利用外存；勿须先知文件长度，有利用文件的扩充。其缺点是：只适合顺序访问，不适
