09年考研操作系统试题
21.假设某计算机的存储系统由Cache和主存组成，某程序执行过程中访存1000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是(D) A．5% B.9.5% C.50% D.95%
22.下列选项中，能引起外部中断的事件是(A)
A．键盘输入 B.除数为0 C.浮点运算下溢 D.访存缺页 23.单处理机系统中，可并行的是D
I 进程与进程 II 处理机与设备 III 处理机与通道 IV 设备与设备 A．I、II和III B. I、II和IV C. I、III和IV D. II、III和IV 24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是 D A．时间片轮转调度算法 B.短进程优先调度算法 C.先来先服务调度算法 D.高响应比优先调度算法
25.某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是 C A．2 B.3 C.4 D.5
26．分区分配内存管理方式的主要保护措施是 A
A．界地址保护 B.程序代码保护 C.数据保护 D.栈保护
27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是C A．2的8次方字节 B.2的16次方字节 C.2的24次方字节 D.2的32次方字节 28.下列文件物理结构中，适合随机访问且易于文件扩展的是B A．连续结构 B.索引结构
C.链式结构且磁盘块定长 D.链式结构且磁盘块变长
29.假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是A
A．110，170，180，195，68，45，35，12 B.110，68，45，35，12，170，180，195 C.110，170，180，195，12，35，45，68 D.12，35，45，68，110，170，180，195
30.文件系统中，文件访问控制信息存储的合理位置是A
A．文件控制块 B.文件分配表 C.用户口令表 D.系统注册表
31．设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是B A．0、1 B.1、1 C.1、2 D.2、1
32．程序员利用系统调用打开I/O设备时，通常使用的设备标识是A A．逻辑设备名 B.物理设备名 C.主设备号 D.从设备号
45.（7分）三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。
1
信号量empty表示缓冲区中空闲单元，其初值应设置为N；oddfull表示缓冲区中装有奇数的单元，其初值应设置为0；evenfull表示缓冲区中装有偶数的单元，其初值也应设置为0。另外还需设置一个互斥信号量mutex以防止三个进程同时对缓冲区进行操作，其初值应设置为1。
P1进程可描述为： P1(){ int number; While(1){
Number=produce(); Wait(empty); Wait(mutex); Put();
If(number%2==0) signal(evenfull); else signal(oddfull); signal(mutex); } }
P2(){
While(1){
Wait(oddfull); Wait(mutex); getodd();
signal(empty); signal(mutex); countodd(); } }
P3(){
While(1){
Wait(evenfull); Wait(mutex); geteven(); signal(empty); signal(mutex); counteven(); } }
46.（8分）请求分页管理系统中，假设某进程的页表内容如下表所示。
页表内容 页号 页框（Page Frame）号 有效位（存在位） 0 1 2 101H — 254H 1 0 1 页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为
2
2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：
（1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。
（2） 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。 （1）
①： 逻辑地址2362H——页号为2，页内地址为362H。
先访问TLB，时间为10ns，未命中；再去访问页表，时间为100ns，获得对应页在内存，其对应的物理块号254H，从而拼接成物理地址254362H，同时将第2页的信息装入TLB中；最后根据这个物理地址访问内存，时间为100ns。故，访问到虚地址对应单元的数据总共需要210ns.
②： 逻辑地址1565H——页号为1，页内地址为565H。
先访问TLB，时间为10ns，未命中；再去访问页表，时间为100ns；因对应页不在内存，将产生缺页中断，中断处理的时间为108ns（其中包括更新页表和TLB等），在中断处理时，因为内存已满，须淘汰一个内存页，LRU算法将选择淘汰第0页；接着重新执行指令，访问TLB（10ns）便可得到页对应的物理块号，拼接成物理地址，最后根据这个物理地址访问内存，时间为100ns。故，访问到该虚地址对应单元的数据总共需要：10+100+108+10+100=328ns.
③： 逻辑地址25a5H——页号为2，页内地址为5a5H。
先访问TLB，时间为10ns，命中(在①时已将该页信息装入TLB)，获得对应的物理块号254H，从而拼接成物理地址2545a5H；最后根据这个物理地址访问内存，时间为100ns。故，访问到虚地址对应单元的数据总共需要110ns.
（2） 逻辑地址1565H的页号为1，页内地址为565H。按照上述访问序列，在访问到该地址时，查页表时将发生缺页中断，中断处理时因内存已满，须淘汰一个内存页，由于第2页刚被访问过，不能被淘汰出去，所以LRU算法将选择淘汰第0页，也就是说，第1页将存放内存的第101H号页框中。因此逻辑地址1565H对应的物理地址为101565H.
第一章操作系统引论
1.1操作系统目标和作用
1、下列选择中，哪些不是操作系统关心的主要问题。（浙大2003） （1）管理计算机裸机；（2）设计提供用户与计算机硬件系统间的界面； （3）管理计算机系统资源；（4）高级程序设计语言的编译器。 2、说明操作系统与硬件、其他系统软件以及用户之间的关系。
提示：操作系统是覆盖在硬件上的第一层软件，他管理计算机的硬件和软件资源，并向用户提供良好的界面。操作系统与硬件紧密相关，它直接管理着硬件资源，为用户完成于硬件相关的操作，从而极大地方便了用户对硬件资源的使用，并提高资源的利用率。操作系统又是一种特殊的系统软件，其他的系统软件都运行在操作系统基础之上，
3
可获得操作系统提供的大量服务，即操作系统是其他系统软件与硬件的接口。而一般用户使用计算机除了需要操作系统支持外，还需要用到大量的其他系统软件和应用软件，使其工作更加方便和高效。它们之间的层次关系为：其他用户，应用程序，其他系统软件，操作系统，计算机硬件。
3、选择：从用户角度看，操作系统是（）。（选项：计算机资源的管理者；计算机工作流程的组织者；用户与计算机之间的接口；由按层次结构组成的软件模块的集合。）
1.2操作系统发展过程
1、引入多道程序技术的前提条件之一是系统具有（3）（西电00） （1）多个cpu；（2）多个终端；（3）中断功能；（4）分时功能
2、判断：所谓多道程序设计，即指每一时刻有若干个进程在执行。F（南京大学00） 3、判断：采用多道程序设计的系统中，系统的程序道数越多，系统效率越高。F （西电01）
4、判断：由于采用了分时技术，用户可以独占计算机的资源。F
5、分布式操作系统与网络操作系统本质上的不同之处在于（实现各计算机之间的通信；共享网络中的资源；满足较大规模的应用；系统中若干台计算机相互协同完成同一任务） 6、若程序A和B单独执行时分别用TA和TB，TA=1h，TB=1.5h，其中处理器工作时间分别为TA=18min，TB=27min。如果采用多道程序设计方法，让A，B并行工作，假定处理器利用率达到50%，另加15min系统开销，请问系统效率提高百分之几？ 提示：1-[(18+27)/50%+15]/2.5h
7、在操作系统中引入并发可以提高系统效率，若有两个程序A和B，A程序执行时所做的工作按次序需要用cpu：10s，设备1：5s，cpu：5s，设备2：10s，cpu10s；程序B执行时所做的工作按次序需要用设备1：10s，cpu：10s，设备2：5s，cpu：5s，设备2：10s。如果在顺序环境下执行两个程序，则cpu的利用率为（）；如果在并发环境下执行两个程序，则cpu的利用率为（）。 8、设某计算机系统有一个cpu、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到cpu运行，进程B后运行。进程A 的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms。进程B 的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图（可用甘特图）并说明：（1）运行过初中，cpu有无空闲等待？计算cpu利用率。（2）进程A和B运行过程中有无等待现象？
9、判断：多道程序设计是利用了CPU和通道的并行工作来提高系统利用率的。 10、判断：多道程序设计可以缩短系统中作业的执行时间。
11、判断：在一个兼顾分时操作系统和批处理系统中，通常把终端作业称为前台作业，而把批处理型作业称为后台作业。
12、判断：批处理系统不允许用户随时干预自己程序的运行。 13、判断：Windows操作系统完全继承了分时系统的特点。
4
14、( C)不是Unix系统的特色。
A.“交互的分时系统” B.“以全局变量为中心的模块结构” C.“模块之间调用关系简明” D.“可以分成内核和外壳”
15、实现多道程序系统的最主要硬件支持是什么？ 解 中断系统和通道技术。
(1) 很多进程的切换是由时钟中断引起的，尤其是分时系统。用户程序进行系统调用时通过软中断来实现，如TRAP。通道和外设的操作也要向操作系统发送中断。 (2) 在多道程序系统中，当CPU要求在主存和外设间传输数据时，通过发出I/O指令命令通道工作，通道独立地在内存和外设间进行数据传输，I/o操作完成后，通道以中断方式通知CPU，从而实现了CPU计算与I/O操作的并行。
16、填空：在一台主机上同时连接多台终端，多个用户可以通过终端同时交互使用计算机资源，这种系统称为（）操作系统；允许多个用户将多个作业提交给计算机集中处理的操作系统称为（）；计算机系统能及时处理过程控制数据并作出响应的操作系统称为（）。 17、分时系统的一个重要性能是响应时间，下述（）因素与改善响应时间有关： 选项：CPU速度快；时间片；轮转调度法；优先数+非抢占式调度算法；进程数目增加。
18、衡量整个计算机性能的指标有（）：用户接口；资源利用率；系统中进程数量；吞吐量；周转时间。
19、判断：单用户系统中，任何时刻，只能有一个用户进程。
20、填空：操作系统的主要性能参数有（系统资源利用率、系统吞吐量）
21、下列作业类型中，适合在分时系统中运行的有_____、______；适合在批处理系统中运行的有_____、______。（选项：学习编程；数据统计；发送电子邮件；整理硬盘） 22、判断：linux是与Unix兼容的操作系统，它不仅仅是只能运行在PC机上。
1.3操作系统的基本特性
1、判断：并发是并行的不同表述，其原理相同。（清华1998） 2、并发性的概念是（）。（北京理工01） 3、在单处理机系统中实现并发技术后，判断：
（1）各进程在某一时刻并行运行，cpu与外设间并行工作； （2）各进程在一个时间段内并行运行，cpu与外设间串行工作；
（3）各进程在一个时间段内并行运行，cpu与外设间并行工作。（四川大学01） 2、填空：现代操作系统的两个最基本的特征是（）、（）。（川大2005）
1.4操作系统的主要功能
1、在用户程序中要将一个字符送到显示器上显示，使用操作系统提供的（）接口：（系统调用；函数；原语；子程序）
5
2、系统调用的作用是什么？请给出实现系统调用的步骤。
3、用户程序向系统提出使用外设的请求方式是（）：作业申请；原语；系统调用；I/O指令。
4、判断：系统调用与用户程序之间的调用不同之处是处理机状态的改变。 5、判断：命令解释程序是操作系统的一个程序，它必须在核心态下运行。
6、用户进程通过系统调用fork创建一个新进程，在执行系统调用前，用户进程运行在（）；在执行fork过程中，用户进程运行在（）。（选项：系统态；用户态；系统态或用户态；内部态）
6、判断：系统调用命令就是访管指令，它的功能是由硬件直接提供的。 7、比较一般的过程调用和系统调用：
答：（1）运行在不同的系统状态：一般过程调用，其调用程序和被调用程序都运行在相同的状态：系统态或用户态。而系统调用的调用过程运行在用户态，被调用过程运行在系统态。（2）通过软中断进入：一般过程调用不涉及系统状态状态转换，可直接由调用过程转向被调用过程；而系统调用通常是通过软中断机制，先由用户态转换为系统态，经核心分析后，再转向相应的系统调用处理子程序。（3）返回问题：一般过程调用在被调用过程执行完后将返回到调用过程继续运行。但对于采用抢占式调度的系统中，当从系统调用返回时，有可能会重新调度。
第二章 进程管理
2.1 进程的基本概念
1、进程申请打印输出完成向系统发出中断后，进程的状态变化为（）。（南京邮电01） 2、判断：当一个进程从等待态变为就绪态，则一定有一个进程从就绪态变成运行态。 3、如果一个单处理机系统中有N个进程，
? 运行进程最多几个，最少几个？ ? 就绪进程最多几个，最少几个？ ? 等待进程最多几个，最少几个？
解答： 运行进程最多1个，最少0个；
就绪进程最多N-1个，最少0个； 等待进程最多N个，最少0个；
4、判断：在一个N个进程的单处理机系统中，有可能出现N个进程都被阻塞的情况。 5、补充内容：
特权指令
指具有特殊权限的指令。这类指令只用于操作系统或其他系统软件，一般不直接提供给用户使用。 在多用户、多任务的计算机系统中特权指令必不可少。它主要用于系统资源的分配和管理，包括改变系统工作方式，检测用户的访问权限，修改虚拟存储器管理的段表、页表，完成任务的创建和切换等。 常见的特权指令有以下几种:
6
（1）有关对I/O设备使用的指令 如启动I/O设备指令、测试I/O设备工作状态和控制I/O设备动作的指令等。
（2）有关访问程序状态的指令 如对程序状态字（PSW）的存取指令等。 （3）存取特殊寄存器指令 如存取中断寄存器、时钟寄存器、设置中断屏蔽、关中断、置基址寄存器等指令。 （4）其他指令：清内存，停机
6、关于进程状态，判断：
（1）进程一旦形成，首先进入的是运行状态。 （2）一个进程必须经过进程的三个基本状态才能结束。 （3）进程可能同时处于某几种基本状态中。
（4）分时系统中，一个正在运行的进程的时间片到，该进程将转入就绪状态。
7、只能在管态下执行的指令有（从内存中取数指令；把运算结果写内存指令；算术运算指令；I/O指令；读时钟指令；置时钟指令、寄存器清零指令；屏蔽所有中断；改变存储器映像图；改变磁盘空间分配位图；） 8、在一个分时系统中，用户提交了一个作业，作业内容包括：请求内存缓冲区；计算并将结果存于内存缓冲区；请求打印机；将缓冲区中的内容在打印机上输出；释放打印机；释放内存；结束。
讨论进程可能的状态变化。
9、判断：在单CPU的系统中，任何时刻都有一个进程处于运行状态。 10、判断：进程申请CPU得不到满足时，其状态变为阻塞态。 11、能从1种状态转变为3种状态的是（）：就绪；阻塞；完成；执行 12、判断：进程在运行中，可以自行修改自己的PCB。
13、判断：当进程申请CPU得不到满足时，它将处于阻塞状态。
14、判断：当进程由执行状态变为就绪状态时，CPU现场信息必须被保存在PCB中。 15、操作系统通过PCB来控制和管理进程，用户进程可从PCB中读出与本身运行状态相关的信息。
16、若一个进程实体由PCB、正文段、数据段和堆栈段组成，请指出下列C语言程序中的内容位于哪一段中：外部变量、局部变量、函数调用实参传递值、用molloc（）要求动态分配的存储器、常数值。
（局部变量：堆栈段；静态局部变量：数据段；外部变量：数据段；函数调用参数：堆栈段；malloc分到的存储区：数据段）
17、unix为什么要把PCB分为进程表项（Proc区）和U区？
提示：因为进程表项中的内容对核心来说必须总是可存取的，而U区中的域只能由正在运行的进程来存取。只有当创建一个进程时，核心才为其分配U区空间，那些不与任何进程相联系的进程表项是不需要U区的。
18、以unix为例，说明Operating System Function Execute Within User Process 的实现模型。
7
提示：unix存在两类进程：系统进程和用户进程。前者在核心态下执行os代码，后者在用户态下执行用户程序。当用户进程因中断或系统调用进入内核态，此时发生了模式切换，但没有发生进程上下文切换。这时，系统进程开始执行，而这两个进程（用户/系统进程）使用同一个PCB，实质是一个进程，仅执行的程序不同，映射的物理地址空间不同，使用的堆栈不同。
19、进程和程序直接可以形成一对一、一对多、多对一、多对多的关系，请分别举例说明在什么情况下会形成这样的关系？
提示：进程与程序一对多：一个进程中执行多个程序；多对一：分时系统中的编译程序为多个终端用户的源程序进行编译；多对多：
20、UNIX系统中进程由三部分组成：进程控制块，正文段和数据段。这意味着一个程序的正文与数据可以是分开的，这种分开的目的是为了( ABC ) A.可共享正文 B.可共享数据
C.可重入 D.方便编程 E.以上全部
21、对于运行于unix系统的以下程序，其执行后 的输出结果是（） Void main() { }
22、在分时系统中，导致进程创建的典型事件是（2）（选项：用户注册；用户登录；用户记账）；在批处理系统中，导致进程创建的典型事件是（2）（选项：作业录入；作业调度；进程调度）；由系统专门为允许中的应用进程创建新进程的事件是（）（选项：分配资源；进行通信；共享资源）；（）（选项：分配PCB；分配内存；分配CPU；分配外设；插入就绪队列）不是创建进程所必需的步骤。
23、系统有n（n＞2）个进程，且当前不再执行进程调度程序，判断下述情况十分可能发生： （1）有一个运行进程，没有就绪进程，n-1个阻塞进程。 （2）有一个运行进程，有一个就绪进程，n-2个阻塞进程。 （3）有一个运行进程，n-1个就绪进程，没有阻塞进程。 （4）没有运行进程，有2个就绪进程，n-2个阻塞进程。
24、判断：在单处理机上，进程就绪队列和阻塞队列都只能由一个。 25、判断以下关于unix进程组成的说法：
（1）进程由进程控制块、正文段、数据段三部分组成； （2）进程控制块包括基本控制块和扩充控制块，常驻内存； （3）正文段是指可供多个进程共享的程序；
（4）数据段分为用户栈区、用户数据区和系统工作区。 提示：
8
printf(“hello1”); Fork(); printf(“hello2”);
Proc结构或称进程表项进程控制块User结构Unix进程正文段：可共享程序段用户栈区数据段用户数据区：非共享程序段和用户工作数据系统工作区：包括核心栈和user结构 26、下列内容中属于进程上下文的是：（）（选项：用户打开文件表；PCB；中断向量；核心栈）
27、根据Bernstein条件，则如下4条语句中： S1：a=x+y; S2: b=z+1; S3:c=a-b; S4:w=c+1;
S1和S2能否并发执行？S3和S4呢？ 28、某系统的进程状态变迁如图所示：（1）说明一个进程发生变迁1、3和5的原因；（2）当发生一个变迁时可能引起另一个变迁的发生，则这两个变迁称为因果变迁。下述因果变迁是否会发生？如果有可能的话，会在什么情况下发生？3→5；3→2；2→1；4→1；4→5. （3）根据此状态变迁图说明该系统的调度策略和调度效果。
运行2低优先就绪135阻塞4高优先就绪首次选择100ms，以后选择500ms 2.2 进程控制：
1、下列程序执行时，系统的输出可能是什么？ {
a=55;
9
}
pid=fork(); if (pid==0){ } Else { }
sleep(7);
Printf(“a=%d\\n”,a); Wait(0);
Printf(“parent child exited\\n”); sleep(5); a=99; sleep(5);
printf(“child leaving\\n”); exit(0);
2.3进程同步：
Int I;
(for i=1;i<=10;i++) Total=total+1;
1、临界资源：P1、P2两个进程执行代码相同，共享total变量：
问：最后total可能的最小值、最大值（2，20） 2、判断：临界区就是临界资源所在的区域。
3、所谓临界区是指（一个缓冲区、一段数据区、同步机制、一段程序）（南京理工01） 4、判断：对临界资源应采用互斥的方式来实现共享。（北京理工02）
5、下面活动分别属于进程的哪种制约关系？（1、几个同学去图书馆借书；几个同学在打篮球；流水生产线上的各道工序；对一个产品的生产和消费；）（北京理工96） 6、填空：若信号量 初值为3，当前值为-3，则表示有（）个进程在该信号量上等待？ 7、下面是两个并发执行的进程，他们能正确运行吗？若不能请修改。（北航02） Parbegin
Int x; P1 {
int y,z;
10
P2: { }
}
X=1;y=0;
If x>=1 then y=y+1; Z=y;
x=0;t=0;
If x<=1 then t=t+2; U=t;
8、双进程临界区问题的算法，其中布尔型数组blicked[2]初始值为{false，false}，整型turn初始值为0，id代表进程编号（0，1），请说明正确否？（违反忙则等待原则） Do{
blocked[id]=true; While(turn!=id) { }
编号为id的进程的临界区 Blocked[id]=false;
编号为id的进程的非临界区 }while（true）；
9、在具有N个进程的系统中，允许M个进程（N≥M≥1）同时进入它们的临界区，其信号量S的值的变化范围是（），处于等待状态的进程数最多是（）个。 10、判断以下解决双进程临界区问题的算法是否正确： Process Pi(i=0,1):
Do{
Flag[i]=true; While(flag[1-i]);
critical section flag[i]=false;
While(blocked[1-id]); Turn=id;
remainder section
}while(1);
11
11、用V操作唤醒一个等待进程时，被唤醒进程的状态变为（）。（选项：运行；等待；就绪；完成）
12、若有3个进程共享一个互斥段，每次最多允许两个进程进入互斥段，则信号量的变化范围是（）。 13、关于进程同步与互斥的说法，判断：
（1）进程的同步与互斥都涉及到并发进程访问共享资源的问题。 （2）进程的同步是进程互斥的一种特殊情况。
（3）进程的互斥是进程同步的特例，互斥进程是竞争共享资源的使用，而同步进程之间必然存在依赖关系。
（4）进程互斥和进程同步有时候也称为进程同步。 14、判断：临界区是不可中断的程序。
15、判断：如果在加锁法实现互斥时，将未进入临界区的进程排队等待，从而让其有被再调度 的机会，加锁法和P、V原语实现互斥时其效果是相同的。
16、由于并发进程执行的随机性，一个进程对另一个进程的影响是不可预测的，甚至造成结果的不正确，下面对造成不正确的因素的描述正确的是：（）（选项：与时间有关；与进程占用的处理机有关；只与执行速度有关；只与外界的影响有关）
17、有两个优先级相同的进程A、B如下，令信号量S1和S2的初值均为0，已知Z=3，则A、B并发运行结束后X、Y、Z的值分别是：
A Y=2; Y=Y+3; V(S1); Z=Y+0; P(S2); Z=Y+Z; B X=2; X=X+3; P(S1); X=X+Y; V(S2); Y=Y+Z; 18、信号量是一个整型变量，可在其上做加1或减1的操作。
2.4 经典进程同步问题
1、一个供应商用汽车给某超市送货，并把汽车上的货物用超市的三轮车运到仓库中，超市的工作人员也用三轮车从仓库中取货去出售。假设共有3辆三轮车，仓库中只能容纳10辆三轮车的货物，且每次从汽车上取货只能共给一辆三轮车，仓库也只能容纳一辆三轮车进入。用信号量实现向仓库中送货及从仓库中取货的同步算法。 2、有一个仓库，可以存放A、B两种产品，但要求：
① 每次只能存入一种产品（A或B）； ② A产品数量－B产品数量 其中M、N是正整数，使用P、V操作描述产品A与产品B的入库过程。 12 3、一组生产者进程和一组消费者进程共享10个缓冲区，每个缓冲区可以存放一个整数；生产者进程每次一次性向3个缓冲区写入3个整数，消费者进程每次从缓冲区取出一个整数。用信号量实现进程的同步关系。 4、写者优先的读者写者问题： wmutex:semaphore=1 //读者与写者之间、写者与写者之间互斥使用共享数据 S：semaphore=1 //当至少有一个写者准备访问共享数据时，它可使后续的读者等待 写完成 S2：semaphor＝1 //阻塞第二个以后的等待读者 readcount,writecount: semaphore = 0,0; //当前读者数量、写者数量 mutex1 :semaphore = 1 //多个读者互斥使用readcount mutex2 :semaphore = 1 //多个写者互斥使用writecount Cobegin: Reader: begin Repeat Wait（S2）； wait(S); wait(mutex1) if readcount=0 then wait(wmutex); readcount++; signal (mutex1); signal(S); signal（S2）； reading… wait(mutex1); readcount--; if readcount=0 then signal(wmutex); signal(mutex1); until false; begin; writer: begin repeat; wait(mutex2); if writecount=0 then wait(S); writecount++; signal （mutex2）; wait(wmutex); writing… signal(wmutex); wait(mutex2); writecount--; if writecount=0 then signal(S); signal （mutex2）; until false; end; 13 coend; 5、有座可双向通行的单车道桥，最大载重负荷为4辆汽车。请给出任一辆车通过该桥的管理算法。 6、设公共汽车上，司机和售票员的活动分别是： 司机的活动：启动车辆； 正常行车； 到站停车； 售票员的活动： 关车门； 售票； 开车门； 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。 设两个信号量S和C，初值为S＝0；C＝0； 司机： L1： 正常行车 售票员： L2： 售票 到站停车 P（S） V（S） 开车门 P（C） 关车门 启动开车 V（C） GO TO L1 GO TO L2 7、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。 S, S1, S2 :semaphore=1,0,0; Cobegin: Process Father: Begin: L1: P(S); Put Apple; V(S1)； GO TO L1； End； Process Mother: Begin: L2: P(S); Put Orange; V(S2)； GO TO L2； End； Process Son: Begin: 14 L3: P(S2); Get Orange; V(S)； GO TO L1； End； Process Daughter: Begin: L4: P(S1); Get Apple; V(S)； GO TO L4； End； CoEnd; 8、进程A1、A2、……An1通过m个缓冲区向进程B1、B2……Bn2不断地发送消息。发送和接收工作遵循如下规则： （1） 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度； （2） 对每一个消息，B1，B2，…，Bn都必须接收一次，读入各自的数据区内； （3）m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。 解答：本题是生产者——消费者问题的一个变形，一组生产者A1，A2，…….An1和一组消费者B1，B2，……Bn2公用m个缓冲区，每个缓冲区只要写一次，但需要读n2次，因此，我们可以把这一组缓冲区看成n2组缓冲区，每个发送者需要同时写n2组缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。 Mutex,empty[n2],full[n2]:semaphore; Mutex=1; //多进程互斥使用缓冲区 empty[0,1,……n2]={m,m,……m}; full[0,1,…..n2]={0,0,……0}; int I; Cobegin: Process Ai Begin: Loop: Int I; For ( I=0; I 将消息放入缓冲区； v(Mutex); for( I=0; I Process Bi Begin: 15 Loop: P (full[I]); P(Mutex); 从消息缓冲区取出消息； v(Mutex); v(empty[I]); Goto Loop; End; CoEnd; 9、进程A、B、C坐在圆桌旁讨论问题（面朝圆桌），每个人都从其右边那个人的信箱里取得讨论的问题，回答完一个问题后提出一个新问题放在左边的信箱中。假设A右边的信箱可放3个问题，B右边的信箱可以放2个问题，C右边的信箱可以放3个问题，初始时A右边的信箱中有2个问题。用信号量写出三个人讨论问题的同步算法。 A信箱A信箱BC信箱CB 10、战地指挥官通过无线电不断向他的三个士兵下达作战指令，但是他必须在得到所有士兵对前一条指令的“确认”之后才能下达新的指令。请用信号量或管程进行指挥官和士兵之间的协同管理。 11、有三个并发进程R,M,P，它们共享了一个可循环使用的缓冲区B，该缓冲区共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存入缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符是，则把它改成“，”；进程P负责吧处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。用P，V操作写出能正确并发执行的程序。 12、有4个进程A,B,C,D共享一个缓冲区，进程A负责循环地从文件读一个整数放入缓冲区，进程B从缓冲区取出MOD 3为0的整数并累计求和；进程C从缓冲区取出MOD 3为1的整数并累计求和；进程D从缓冲区取出MOD 3为2的整数并累计求和.请用PV操作写出能够正确执行的程序。 2.5 进程通信 1、在UNIX中，（）用于吧一个进程的输出连接到另一个进程的输入（普通文件；索引文件；目录文件；管道文件） 2、关于进程通信的说法，判断： （1）进程通信有两种方式，直接通信和间接通信。 （2）直接通信固定在一对进程之间。 16 （3）间接通信是通过第三个进程转发信件的，不必在两个进程间直接相互通信。 （4）间接通信方式以信箱为媒介实现通信，信箱由接收信件的进程设置。 2.6线程 1、以下描述中，（）并不是多线程系统的特长。（浙大06） （1）利用线程并行地执行矩阵乘法运算； （2）Web服务器利用线程响应HTTP请求 （3）键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应该应用的键盘输入 （4）基于GUI的debugger用不同的线程分别处理用户输入、计算、跟踪等操作。 2、若一个进程拥有100个线程，这些线程属于用户级线程，则该进程在系统调度执行时间上占用（）个时间片：1；100；1/100；0 3、判断：属于同一个进程的线程可以共享进程的程序段和数据段。 4、关于进程和线程的说法，判断： （1）线程是进程中可独立执行的子任务，一个进程可以包含一个多多个线程，一个线程可以属于一个或多个进程。 （2）线程又称为轻型进程，因为线程都比进程小。 （3）多线程技术具有明显的优越性，如速度快、通信简便、并行性高等。 （4）由于线程不作为资源分配单位，线程之间可以无约束地并行执行。 第三章 处理机调度与死锁 3.3 调度算法 1、既考虑作业的执行时间又考虑作业的等待时间的调度算法是（）。（选项：短作业优先；先来先服务；响应比高者优先；优先级调度） 2、给定一组作业J1,J2,…Jn，它们的运行时间分别为T1,T2,…Tn，假定这些作业是同时到达，并且将在一台cpu上按单道方式运行。证明：若按最短作业优先调度算法运行这些作业，则平均周转时间最短。（东南大学、北京大学） 证明：先对J1,J2,…Jn按照T1,T2,…Tn的大小升序排列，得到K1,K2…,Kn，这组进程的运行时间t1<=t2<=…<=tn。SJF调度就是从K1到Kn这个序列。设SJF调度这n个进程的周转时间之和Z，则： T=Z/n=[t1+(t1+t2)+ (t1+t2+t3)+…+ (t1+t2+t3+…+tn)]/n =[n*t1+(n-1)*t2+(n-2)*t3+…+1*tn]/n 因为n>(n-1)>(n-2)>…>1,所以t1<=t2<=…<=tn时，平均周转时间最小。 3、判断：在剥夺优先级调度方式下，现运行进程的优先级不低于系统中所有进程的优先级。 17 4、设某计算机系统有一个cpu，一台输入设备，一台打印机。现有两个进程同时进入就绪状态，且进程A先得到cpu运行，进程B后运行。进程A的运动轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图，并说明开始运行后，cpu有无空闲等待？计算cpu的利用率。（浙大05） 3、一个操作系统具有分时兼批处理的功能，设个一个合理的调度策略，使得分时作业响应快，批作业也能及时得到处理。 4、一个具有分时兼批处理功能的操作系统应怎样调度和管理作业? 要点提示： 1)优先接纳终端作业，仅当终端作业数小于系统可以允许同时工作的作业数时，可以调度批处理作业。 2)允许终端作业和批处理作业混合同时执行。 3)把终端作业的就绪进程排成一个就绪队列，把批处理作业的就绪进程排入另外的就绪队列中。 4)有终端作业进程就绪时，优先让其按“时间片轮转”法先运行。没有终端作业时再按确定算法选批处理作业就绪进程运行。 4、现有两道作业同时执行，一道以计算为主，另一道以输出为主，应该如何为两作业设置处理器的优先级？ 5、有5个待运行的作业为A,B,C,D,E，各自运行时间为9，6，3，5，x，试问采用哪种运行次序使得平均响应时间最短？ 提示：假设x<3，x在3和5间，在5和6间，在6和9间分别讨论。 6、某个操作系统的设计目标是同时支持实时任务和交互式任务，它的实现采用混合式多线程策略，处理器调度策略采用多队列策略，在系统资源不足时，可采用中级调度来平衡系统负载。 （1）问该系统中存在着哪些与处理器调度有关的实体？（进程、内核级线程、用户级线程） （2）设计一个合理的多队列进程调度策略，它既能满足实时任务调度的需要，又能从外设访问角度来满足交互式任务调度的需要。 提示：划分成实时优先级层次和交互式优先级层次，其中前者优先级层次高。实时优先级层次包括多个优先级，可以组织成多个就绪线程队列或一个优先级队列；可采用抢占式优先级调度策略，时间片较长。交互式优先级层次可以分成3个就绪队列，按照优先级从高到低依次为：访问字符设备的就绪线程队列、访问块设备的就绪线程队列、时间片完成的就绪线程队列，其中优先级较高的就绪线程队列具有较短的时间片。 7、（浙大02）假设一个计算机系统具有如下特征：处理一次中断，平均耗时1ms；一次进程调度，平均耗时2ms；将CPU分配给选中的进程，又平均需要1ms。再假设其定时器芯片每秒产生100次中断，问： （1）系统将百分之几的CPU时间用于时钟中断处理？（提示：每秒处理中断的时间是100ms，100ms/1s=10% 18 （2）如果采用轮转法调度，10个时钟中断为一个时间片，那么，系统将百分之几的CPU时间用于进程调度（包括雕刻、分配CPU和引起调度的时钟中断处理时间）？ 每次调度所花时间=一次进程调度2ms+分配cpu的1ms+引起调度的时钟中断1ms，每秒会进行10次调度，则：（2ms+1ms+1ms）*10/1s=4% 8、有一个多道批处理系统，作业调度采用“短作业优先”调度算法；进程调度采用“优先数抢占式”调度算法，且优先数越小优先级越高。如系统拥有打印机一台，采用静态方法分配，忽略系统的调度开销。现有如下作业序列到达系统： 作业名 J1 J2 J3 J4 J5 到达系统时间 14：00 14：20 14：30 14：50 15：00 Cpu运行时间 40min 30min 50min 20min 10min 打印机需求 优先数 1 0 1 0 1 4 2 3 5 1 回答：（1）按作业运行结束的次序排序；（2）作业的平均周转时间和平均带权周转时间是多少？ 提示：作业调度与内存大小有关，本题没有给条件，所以只需考虑进程调度，得出结束次序为：J2,J1,J5,J3,J4. 9、设在某多道程序系统中有用户使用的内存100KB，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程剩余时间相同时采用先来先服务的算法，进程调度时间选择在进程执行结束或新进程创建时。现有进程如下： 进程 0 1 2 3 4 创建时间 0 4 10 11 16 要求执行时间 8 4 1 20 14 要求内存 15KB 30KB 60KB 20KB 10KB 申请打印机 1 1 0 1 1 假设系统优先分配内存低地址区域，且不允许移动，那么： （1）给出进程调度算法选中进程的次数。 （2）全部进程执行结束所用的时间是多少？ 10、就绪队列中有n个就绪进程等待cpu调度，如果采用不同的调度算法，总共可能有（）种调度顺序。（浙大06） 11、一个实时系统使用了4个周期事件，其周期分别为50ms，100ms，200ms，250ms。假设这4个周期事件分别需要35ms，20ms，10ms和x ms的CPU时间。保持系统可调 19 度的最大x值是多少？ 提示：该实时系统是以周期进行调度，即m个周期事件，时间i以周期Pi发生，需要Ci秒钟CPU时间处理一个事件，那么可处理负载的条件是：C1/P1+C2/P2+C3/P3+C4/P4=35/50+20/100+10/200+x/250≤1,则x≤12.5ms。 3.5 死锁的基本概念 1、判断：死锁是指系统中的全部进程都处于阻塞状态。（北京理工01） 2、判断：PV操作不仅可以用来实现进程同步，还可以用来防止进程的死锁。（南京理工01） 3、有3个进程P1,P2和P3并发工作，进程P1需要资源S3和S1，进程P2需要资源S1和S2，进程P3需要资源S2和S3.那么： （1）若对资源分配不加限制，可能发生什么情况？ （2）为保证进程正确地工作，应采用怎样的资源分配策略？ 4、设系统有一类数量为M的独占性资源，系统中N个进程竞争该类资源，个进程对资源的最大需求为W。当M,N,W分别取下列个值时，系统可能发生死锁？（上海交大） （1）M=2;N=2;W=2; （2）M=3;N=2;W=2; （3）M=3;N=2;W=3; （4）M=5;N=3;W=2; （1）M=6;N=3;W=3; 5、在有m个进程的系统中出现死锁时，死锁进程的个数范围是（）（北大97） 6、死锁现象并不是计算机系统所独有的，判断下列哪些现象是死锁的体现：（浙大06） （1）杭州西泠桥塞车，因为大修，桥上只有一个车道供双方通行； （2）高速公路大堵车，因为桥被台风吹跨了； （3）两列相向行驶的列车在单轨铁路上迎面相遇； （4）两位木匠钉地板，每位木匠必须有榔头和钉子才能工作。一位只握一把榔头，而另一位没有榔头，却有钉子； 7、资源的有序分配策略可以破坏死锁的（）条件。 8、如下图所示，相交的四条单行线不幸塞车。（浙大03） 9、在多进程的并发系统中，肯定不会因竞争( D )而产生死锁。 A.打印机 B.磁带机 C.磁盘 D.CPU 20 根据死锁四个条件分析，判断是否死锁现象。请添加新的规则，以保证不再出现死锁。 10、在哲学家就餐问题中，对哲学家Pi（i=0，1，2，3，4）有循环进程Si： Pi做学问； Pi取左手边的筷子和右手边的筷子； Pi就餐； Pi将两根筷子分别放回原处。 问：（1）说明该系统是个会死锁的系统； （2）请分别用死锁预防、死锁避免、死锁检测与恢复改造系统。 11、假定某计算机系统有R1设备3台，R2设备4台，它们被P1,P2,P3,P4这4个进程所共享，且已知这四个进程均以下面所示的顺序使用现有设备：申请R1→申请R2→申请R1→释放R1→释放R2→释放R1。（1）该系统运行过程中是否会有产生死锁的可能？为什么？（提示：有，因为满足产生死锁的四个必要条件）（2）如果有可能，举例说明，并画出表示该死锁状态的进程资源图。 12、关于安全状态的说法，判断： （1）系统处于不安全状态一定会发生死锁。 （2）系统处于不安全状态可能发生死锁。 （3）不安全状态是死锁状态的一个特例。 （4）系统处于安全状态时也可能发生死锁。 13、判断：参与死锁的所有进程都占有资源。 14、化简下图，并判断是否为死锁状态？ 21 P1R1R2R3P2R4P3 15、银行家算法是通过破坏死锁四个必要条件中的（）来避免死锁的。 16、设系统中仅有一类资源共3个，系统有3个进程共享该资源，每个进程至少请求一个资源，若他们所需要的资源最大量总和是X，则发生死锁的必要条件是：（） 第四章 存储器管理 1、计算机系统是如何保护操作系统不受破坏，各用户程序之间也相互不被破坏呢？ 提示：在内存划分用户空间和系统空间，用界限寄存器记录系统空间的下届；用户空间也划分成多个空间，不同用户的程序在内存的地址不可交错。 2、在下列存储管理方案中，一个作业在内存中一定是连续存放的有（）。（选项：单一连续分配；固定分区分配；可变分区分配；段式；可重定位分区分配；页式；段页式） 3、要保证一个程序在主存中被改变了存放位置后仍能正确执行，则对主存空间应采用（）。（选项：静态重定位；动态重定位；动态分配；静态分配） 4、试给出几种存储保护方法，并说明各适用何种场合？ （1）界限寄存器法：适用于分区存储管理；（2）锁钥相配法：适用于分页和分区存储管理；（3）设置存取权限法：适用于分段存储管理。 5、存储保护是否可以完全由软件实现？为什么？ 答：存储保护的主要任务是确保每道程序都只能在自己的存储区域内访问，因此对每次内存访问都要进行越界检查。如果越界检查完全由软件实现，则会降低程序的执行速度，因此越界检查通常由硬件实现，而发现越界后的处理需要与软件配合来完成。所以存储保护功能是由软硬件协同完成的。 6、下面关于重定位的说法，判断： （1）绝对地址是内存空间的地址编号。 （2）用户程序中使用的从0地址开始的地址编号是逻辑地址。 （3）动态重定位中装入内存的作业仍保持原来的逻辑地址。 （4）静态重定位中，地址转换工作是在作业装入过程中完成的。 7、内存利用率不高主要表现在哪些方面？可通过哪些途径来提高内存利用率？ 答：内存利用率不过主要表现在：（1）内存中存在大量的、分散的、难以利用的碎片；（2）暂时或长期不能运行的程序和数据占据了大量内存空间；（3）当作业较大时内存只能装入少量作业，当它们被阻塞时将使CPU空闲，从而也会降低内存利用率；（4）内存中存在大量重复的拷贝。提高内存利用率的途径：（1）改连续分配为离散分配，减少内存碎片；（2）增加对换机制，将那些暂时不用的程序和数据换出到外存；（3）采用虚拟存储技术，是更多的作业装入内存；（4）引入动态装入和链接机制，尽量避免装入本次运行中不用的程 22 序；（5）引入存储器共享机制，减少内存中的重复拷贝。 8、可重入代码：又称为“纯代码”，是一种允许多个进程同时访问的代码，在执行过程中不允许有任何改变。 9、从供选择的答案中选出与下列叙述关系最密切的存储管理方法。 （1）支持多道程序设计，算法简单，但存储器碎片多；（2）能消除碎片，但用于存储器紧缩处理的时间长；（3）克服了碎片多和紧缩处理时间长的缺点，支持多道程序设计，但不支持虚拟存储；（4）支持虚拟存储，但不能以自然的方式提供存储器的贡献和存取保护机制；（5）运行动态链接和装入，能消除碎片，支持虚拟存储。 选择：A 段页式； B 基本分页； C请求分页式；D 可重定位式；E固定分区；F单一连续分配。 10、下面关于存储器管理功能的论述，判断：（2，5） （1）即使在多道程序设计环境下，用户也能设计用内存物理地址直接访问内存的程序。 （2）内存分配最基本的任务是为每道程序分配内存空间，其他追求的主要目标是提高存储空间的利用率。 （3）为了提高内存保护的灵活性，内存保护通常由软件实现。 （4）交换技术已不是现代操作系统中常用的一种技术。 （5）地址映射是指将程序空间中的逻辑地址变为内存空间的物理地址。 （6）虚拟存储器能在物理上扩充内存容量。 11、碎片最严重的存储管理方式是（） （1）固定分区；（2）可变分区；（3）分页；（4）分段。 12、某程序在逻辑地址100处有一条指令LOAD 1,500，而500单元内存放数据51888.假设程序被分配到内存起始地址5000单元时，试用图示意，采用下述各种方式下的该指令及数据地址的物理地址及相应的地址变换过程。 （1）静态重定位。 （2）采用重定位寄存器实现动态重定位。 （3）采用页表映像方式，假定页面大小为100B，其页面各页存放到50、51、52、?59物理块上。 13、在分页、分段和段页式存储管理中，当访问一条指令时，需要访问内存几次？各做什么操作？ 4.3 连续分配 1、有一个系统其内存容量为1024KB，有8个作业同时到达，各作业需要的内存量何运行时间如表所示： 作业编号 1 2 需要内存量（KB） 140 80 运行时间（s） 3 1 23 3 4 5 6 7 8 100 60 50 30 15 20 3 2 1 3 2 3 假定系统初启时，将内存1024KB按作业的编号顺序分给各道作业，并假定是多CPU下，分配到内存的作业都可以立即运行。问：（1）1s后，内存空白区按首次适应何最佳适应算法的链接方式链接，将如何链接？（2）2s后，其内存空白区按上述两种算法如何链接？（3）在（2）后，此时有一个作业9要求进入内存，它需要内存量为12KB，按上述两种算法，将把哪一块空白区分给它？ 2、在某多道程序系统中，供用户使用的内存空间为100KB，磁带机2台，打印机1台。系统采用可变式分区分配方式管理内存，对磁带机和打印机采用静态分配方式，并假设输入、输出操作的时间忽略不计。现有一作业序列如表所示： 作业号 1 2 3 4 5 到达时间 8：00 8：20 8：20 8：30 8：35 要求计算时间（min） 25 10 20 20 15 要求内存（KB） 15 30 60 20 10 申请磁带机数 1 1 1 1 申请打印机数 1 1 1 假设作业调度采用先来先服务算法，优先分配内存的低地址区域且不准移动已在内存中的作业，问：作业的调度顺序是什么？平均周转时间是多少？作业全部执行结束的时间是什么？ 3、unix中，关于交换进程的叙述，正确的有（）。（选项：（1）交换进程用于实现虚拟存储系统；（2）换出进程时，注意不换出正被共享的正文段；（3）当对换区有就绪进程且内存有足够空间时，则立即把它换入内存；（4）为了换进一个进程而必须换出别的进程时，总是先换出睡眠态进程） 4、以下有关可变分区管理的说法中，判断： （1）可变分区管理常采用的内存分配算法包括最先适应、最佳适应和最坏使用算法。 （2）最先适应算法实现简单，但碎片过多使内存空间利用率降低。 （3）最佳适应算法是最好的算法，但后到的较大作业很难得到满足。 （4）最差适应算法总是挑选最大的空闲区用于分割，使得剩下的分区仍可使用。 5、在某系统中采用基址、限长寄存器的方法来保护存储信息，判断是否越界的判别式为（）。 6、假定存储器空闲块有如下结构： 350B250B500B 请构造一串内存请求序列，首次适应分配算法能满足该请求序列，而最佳适应分配算法则不能。 7、在固定分区管理中，为了提高内存的利用率，可采用如下技术（1，2） （1）按经常出现的作业大小来划分分区。（2）按作业对内存空间的需求量组成多个作业请求队列。（3）不同作业请求队列中的作业可以申请相同的分区。（4）大作业可以申请多个分区。 8、可变分区存储管理采用的地址转换公式是（3） 24 （1）绝对地址=界限寄存器值+逻辑地址；（2）绝对地址=下限寄存器值+逻辑地址； （3）绝对地址=基址寄存器值+逻辑地址；（4）绝对地址=块号*块长+页内地址； 9、除了操作系统所占用的存储区安排在内存顶部，其余是安排给用户的可用存储空间，采用从两头向中间的分配可变分区管理方法有何优点？ 答：这样做可以使作业集中在两端，不必移动信息就会使得空闲空间总是集中在一起，且集中在内存的中部。特别是当只有两个作业的情况下，一个作业被撤后，不必移动信息，就会使空闲区连成一片，可使作业移动最小。 4.4 基本分页管理 1、填空：设有8页的逻辑空间，每页有1024B，它们被映射到32块的物理存储区中。那么，逻辑地址的有效位是（）位，物理地址至少是（）位。（西北工大00） 2、判断：在分页系统中，减少页面大小，可以减少内存的浪费，所以页面越小越好。 3、判断：在一个分页系统中，根据需要，页面的大小可以不相等（北京理工） 4、判断：页式存储管理中，用户应将自己的程序划分成若干大小相等的页面。（北航04） 5、关于分页系统的页面大小，判断： （1）页面大的好处是页表较小。（2）页面小的好处是可以减少由内部碎片引起的内存浪费。（3）通常，影响磁盘访问时间的主要因素不在于页面的大小，所以使用时可优先考虑大的页面。 6、以下各功能中，（）不需要硬件的支持。（选项：中断系统；地址映射；进程调度；时钟管理；页面调入；文件打开；） 7、一台计算机为每个进程提供65536字节的地址空间，划分为4K字节的页。一个特定的程序有32768字节的正文、16386字节的数据和15870字节的堆栈。这个程序能装入地址空间吗？如果页面长度是512字节，能放下吗？ 8、分页系统中的页面是为（）。 选项：用户所感知的；操作系统所感知的；编译系统所感知的；连接装配程序所感知的。 9、联想存储器中的页，其信息（3） （1）一点在外存中；（2）一定在外存和内存中；（3）一定在内存中；（4）以上说法都不对。 4.5 基本分段管理 1、判断：段页式结合了段式和页式的优点，所以段页式的内部碎片和页式一样少 2、在固定式分区管理、可变式分区管理、页式管理、段式管理、段页式管理中，各会产生何种碎片？ 3、段式存储管理中，处理零头问题可采用（）方法。（重定位；拼接；Spooling技术；覆盖技术） 4、采用段式存储管理时，一个程序如何分段是在（）决定的。（选项：分配主存时；用户编程时；装作业时；程序执行时） 5、若段式存储管理中供用户使用的逻辑地址是24位，其中段内地址占用16位，则用户程序最多可分为（）段。当把程序装入主存时，每段占用主存的最大连续区为（）字节。 25 6、段式存储管理中分段是由用户决定的，因此（） （1）段内的地址和段间的地址都是连续的。（2）段内的地址是连续的，而段间的地址是不连续的。（3）段内的地址是不连续的，而段间的地址是连续的。（1）段内的地址和段间的地址都是不连续的。 4.6虚拟存储器基本概念 1、简述“虚拟”在操作系统中的应用。 提示：虚拟存储管理、虚拟设备、分时系统中的cpu等。 2、判断：虚拟存储器的大小等于或小于内存和外存的容量之和。（西电） 3、判断：虚拟存储器的大小可比主存容量大，也可比主存容量小。（电子科大） 4、判断：cpu的地址空间决定了计算机的最大存储容量 5、交换扩充了主存，因此，交换也实现了虚拟存储器，对吗？ 6、总体上说，按需调页是个很好的虚拟内存管理策略。但是有些情况并不适合，判断：（堆栈；线性搜索；矢量运算；二分法搜索（浙大06） 提示：按需调页适合运行的程序师具有局部性现象的程序，即最好是对数据进行顺序访问的程序。矢量运算就是数组运算，数组存放是连续的，所以数组运算就是临近的数据的运算，满足局部性。二分法搜索先找中间的那个元素，如果没有找到，就再找前面数过去的1/4位置或倒数1/4的位置，再这样找下去，显然每次搜寻的元素都不是相邻的，所以不满足局部性。 7、判断：请求页式存储管理系统中，若把页面的大小增加一倍，则缺页中断次数也减少一半。 8、在虚拟分页存储管理中，（）没有优先考虑最近使用过的页面。（选项：最优页面替换算法；第二次机会算法；LRU算法；时钟页面替换算法；NFU算法；最近未使用页面算法）一台小型计算机有4个页框（页0-页3）。在第一个时钟周期时R位是0111（页0是0，其他是1）。在随后的时钟周期中这个值是1011，1010，1101，0010，1010，1100，0001。如果使用带有8位计数器的老化算法，最后一个周期后页2的计数器值是（）。 9、在一个32位计算机的虚拟页式存储管理系统中，怎样解决页表非常庞大的问题？请给出具体解决方案（假设页面大小为4K，用户空间为2GB，每个内存块用4字节表示） 10、测得某个采用按需调页策略的系统部分状态数据为：CPU利用率20%，对换空间的磁盘利用率98%，其他设备的利用率5%，由此断定系统出现异常。此种情况下（）能提高利用率（安装一个更快的硬盘；通过扩大硬盘容量增加对换空间；增加运行进程数；加内存条来增加物理内存容量；更换速度更快的CPU；采用更快的I/O设备。） （浙大98） 11、在请求分页系统中，地址变换过程可能会因为（）、（）、（）等原因而产生中断。 12、在请求分页管理系统中，需要哪些数据结构？（页表、块位图） 13、某请求页式系统，允许用户空间为32个页面（每页1KB），主存为16KB，若一个用户程序有10页长，某时刻该进程的页表如下所示： 虚页号 0 物理块号 8 26 是否在TLB中 是 1 2 3 4 5 6 其他 7 4 10 5 3 2 无效 是 否 否 否 是 是 问：（1）计算虚地址0AC5H、1AC5H对应的物理地址。 （2）页表存放在主存中，对主存的一次存取需要1.5ns，对TLB表的查找时间忽略为0，试问这两次访问共耗费多少时间？（浙大04） 14、已知某系统页面长为4KB，页表项4B，采用多层分页策略映射64位虚拟地址空间，若限定最高层页表占1页，问需要采用几层分页策略？ 提示；由于每层页表的大小都不超过一页，所以每层的页号不超过10位。10*n+12>=64,所以采用6层。 15、一台机器有48位虚地址和32位物理地址，页面是8K，问在页表中需要多少个页表项？一个倒置的页表需要多少页表项呢？ 16、一个程序要把100×100的数组的初值置为“0”，现在假定有两个内存块可以用来存放数组信息，每个内存块可以存放200个数组元素，数组中的元素按行编址。两个内存块的初始状态都为空，若程序编写如下： （1）int A [100,100]; For i=1 to 100 For j=1 to 100 A[i,j]=0; （1）int A [100,100]; For j=1 to 100 For i=1 to 100 A[i,j]=0; 当采用LRU页面置换算法时，（1）和（2）两个程序各会产生多少次缺页？ 17、在请求页式存储管理系统中，页的大小为128字节。有一个64*64的整型数组，系统按行存储，每个整数占用两个字节。若系统为它分配一个贮存块存放数据，且程序已经驻留内存。试问实现为该数组清零操作时，可能产生多少次缺页中断。程序的代码编写如下： int A [64,64]; int i，j； For （i=0； i<64;i++） For （j=0； j<64;j++） A[i,j]=0; 18、某页式虚存系统中，假定访问内存的时间是10ms，平均缺页中断处理时间是25ms，平均缺页中断率为5％。计算在该虚存系统中，平均有效访问时间是多少？ 19、某操作系统的存储管理采用页式管理系统，系统的物理地址空间大小为32M，页的大小 27 是4K，假定某进程的大小为32页，问： （1）写出逻辑地址格式； （2）如果不考虑权限位，该进程的页表有多少项？每项至少多少位？ 20、已知某系统页长4KB，页表项4B，采用多层分页策略映射64位虚址空间。若限定最高层页表占1页，问它可以采用几层分页策略？ 21、一台计算机上的一条指令执行平均需要k纳秒，其上的某个操作系统处理一次页故障需要n纳秒，如果计算机上的程序执行平均m条指令发生一次缺页，问实际的指令执行时间为多少？ 提示：=(m*k+n)/m 22、在分页系统中，其页表存放在内存中。 （1）如果对内存的一次存取需要100微秒，则实现一次页面访问至少需要的存取时间是多少？ （2）若系统有快表，快表的命中率为80％，当页表项在快表中时，其查询快表的时间为20微秒，问此时的存取时间是多少？ 23、有一页式系统，其页表存放在主存中。 （1）如果对主存的一次存取需要1.5微秒，试问实现一次页面访问的存取时间是多少？ （2）如果系统增加快表，平均命中率为85％，若忽略快表查找时间，问此时的存取时间为多少？ 24、在页式虚拟存储管理系统中，假定驻留集为M个页帧（初始所有页帧均为空），在长为P的引用串中具有N个不同页号（N>M），对于FIFO何LRU两种页面替换算法，试求出页故障的上限和下限，说明理由。 25、假定某一页式虚拟存储器，内存的平均访问时间为1微秒，辅存的平均访问时间为10毫秒，问如果希望虚拟存储器的平均访问时间仅比内存的增加10％，则需要页面失效率是多少？ 26、一个计算机有cache，有一个用作虚拟内存的磁盘。若从cache中读取一个字所用的时间为Ans，从内存中将一个字读入cache的时间为Bns，从磁盘中将一个字调入内存的时间为Cns。若在cache中读取一个字的命中率是（n-1）/n，在内存中读取一个字的命中率是(m-1)/m,则平均访问时间是多少？ 27、内存的利用率不高主要表现为哪几种形式？可以通过哪些途径来提高内存的利用率？ 28、人们观察到在两次页故障之间执行的指令数与分配给程序的页框数成正比，即可用内存加倍，页故障的平均间隔也加倍。假设一条普通指令需要1μs，但若发生了页面故障就需要2001μs。一个程序运行了60s，期间发生了1500次页面故障，如果该页面的可用内存时原来的2倍，这个程序运行需要多少时间： 提示：处理页面故障的时间=2001-1=2000μs，该程序共有指令数=（60s-1500*2000μs）/μs=57000000条，增加内存后，该页面故障次数为1500/2次，页面故障处理时间为 28 =750*2000μs=1500000μs，则该程序运行时间为=1500000μs+57000000μs=58.5s。 29、假定占有M块（初始为空）的进程有一个页访问串，这个页访问串的长度为p，其中涉及到q个不同的页号，对于任何页面置换算法，问：（1）缺页中断次数的下届和上届分别是多少？ 30、覆盖技术与虚拟存储技术有何本质不同？交换技术与虚拟存储有何不同？ 提示：覆盖技术中，覆盖段由用户设计，用户自身对内存的划分要参与操作；虚拟存储技术是由系统提供逻辑空间给用户使用，而用户并不真正了解内存的情况，物理空间的划分和管理由系统完成；交换技术是讲内存中暂时没有运行的进程调出内存，但并没有提供大于实际内存空间的逻辑空间给用户使用，该技术并不是直接面向用户的；虚拟技术可以调出正在运行的进程的内容，它是提供更大的逻辑空间供用户使用，是直接面向用户的。 31、某计算机系统执行一条指令需10ns，一次缺页需额外的20ms，如果每1000000条指令发生一次缺页，则指令平均执行时间为多少？ 32、在某页式虚存管理系统中，假定访问内存的时间是10ms，平均缺页中断处理时间为25ms，平均缺页中断率为5%。试计算在该虚存系统中，平均有效访问时间是多少？ 33、请求分页系统必须至少具有三种硬件支持（一定量内存和较大量外存、地址转换机构、缺页中断机构）。 34、实现虚拟存储器的关键技术是（请求调入技术和置换技术）。 35、unix为实现请求分页管理，使用了哪些数据结构？ 答：（1）页表：（2）磁盘块描述表：记录虚页号对应的盘块号。（3）页框数据表：用于描述每个页框。（4）对换使用表：描述对换设备上的每一页的使用情况。 36、虚拟存储系统的基础是程序的局部性理论，此理论的基本含义是（选项:程序执行时对主存的访问是不均匀的；代码的顺序执行；变量的连续访问）；局部性有两种形式：时间局限性和（选项：指令局部性；数据局部性；空间局部性）。它们的意义分别为（选项：最近被访问的单元，很可能在不久的将来还要被访问；最近被访问的单元，很可能它附近的单元也即将被访问；结构化程序设计，很少出现转移语句；程序中循环语句的执行一般时间很长）。根据局部性理论，Denning提出了（选项：Cache结构的思想；工作集理论；LRU算法；） 37、作业在执行中发生缺页中断，经操作系统处理后，应让其执行（）指令。 选择：被中断的前一条；被中断的那一条；被中断的后一条；启动时的第一条。 38、什么是Belady现象？ 答：Belady现象是指在使用FIFO置换算法转换时，在进程或作业没有得到它所要求的全部页面的情况下，有时会出现的分配给它的页面数越多，缺页次数反而也越多的现象。 39、名词解释：抖动，工作集。 答：在虚拟存储系统中，由于大量页面的换入换出操作导致CPU利用率急剧下降的现象。工作集是在某段时间间隔里，进程实际要访问的页面的集合。 40、在某页式虚存系统中，假定访问内存的时间是10ns，平均缺页中断处理时间为25ms，平均缺页中断率为5%，试计算在该虚存系统中，平均有效访问时间是多少？ =25ms*5%+10ns*（1-5%） 40、unix系统中的存储管理时采用（A3）方式；对换空间采用（B2）管理方式。 A：（1）请求分页；（2）动态分段；（3）段页式且支持请求调页；（4）段页式且支持请求调段。 B：（1）固定分区；（2）动态分区；（3）分页；（4）分段 29 41、下面的程序设计技术和数据结构，对于请求分页的环境而言，（3，5，6）是好的，（2，7）是坏的。 （1）栈；（2）hash表；（3）顺序检索；（4）二分查找；（5）纯代码；（6）向量操作；（7）间接寻址 42、假定某一页式虚拟存储器，内存的平均访问时间为1μs，辅存的平均访问时间为10ms，试问如果希望虚拟存储器的平均访问时间仅比内存的增加10%，则需要页面失效率是多少？ 答：设页面失效率为f，则虚拟存储器的平均访问时间为： （1-f）*1μs+f*10ms=1+9999*f（μs），据题意，1.10＞1+9999*f，所以，f＜0.00001 43、虚拟存储管理利用了交换区、内存已经Cache。假设从Cache读取一个字节数据需Ans；如果该数据不在Cache，却在内存，则从内存读至Cache需Bns，然后还需从Cache得到；如果该数据既不在Cache，又不在内存，则从交换区读入内存需Cns，然后还需传至Cache，才能读取。已知Cache的命中率为n，内存的命中率为m，求平均访问时间。 44、现有一请求分页的虚拟存储器，内存最多容纳4个页面，对于下面的引用串：1，2，3，4，5，3，4，1，6，7，8，9，5，4，5，4，2.分别采用FIFO,LRU,OPT页面替换算法，各将产生多少次缺页中断？ 第五章 设备管理 5.1 I/O系统 1、判断：（1）共享设备必须是可寻址的和可随机访问的设备。 （2）字符设备的基本特征是可寻址到字节，即能指定输入的源地址和输出的目标地址； （3）共享设备是指同一时间内运行的多个进程能同时访问的设备； （4）在分配共享设备和独占设备时都可能引起死锁； （5）通道是处理输入、输出的软件； （6）所有外围设备的启动工作都由系统统一来做； （7）来自通道的I/O中断由设备管理负责处理； （8）编制好的通道程序是存放在主存储器中的。 （9）只有引入通道后，cpu计算与I/O操作才能并行执行。 （9）设备控制器是可编址设备，当用于控制多台设备时，则具有多地址（对） （10）处理器与外围设备的并行工作能力是由（）提供的：硬件；系统软件；应用软件；支援软件。 （11）存储型设备可以作为主存储器的扩充，信息传输单位为块。 （12）按设备的使用特性，可将计算机设备分为存储型设备和输入输出设备。 （13）输入输出型设备负责主存储器与外围设备间的信息传输，信息传输单位是字符。 （14）存储型设备一般属于共享设备，而输入输出型设备则属于独占设备。 （15）独占设备一般不宜采用静态分配策略。 30 （16）作业指定独占设备的方式包括直接指定设备绝对号和指定设备类与相对号两种。 （17）指定绝对设备号的方式使设备分配的适应性好、灵活性强，用户程序中经常使用。 （18）在unix系统中，标准输入和标准输出都是终端设备，即键盘和显示器。 （19）在unix系统中，使用“＞”或“》”可以使输出重定向，“＜”可以使输入重定向。 （20）在unix系统中，管道pipe是连接在进程间的可共享文件。 （21）在unix系统中，Shell文件相当于MS-DOS的批处理文件，直接执行即可。 2、填空：通道技术的引入，实现了（处理器与设备的）并行、（设备与设备的）并行、（进程与进程的）并行。 3、把设备作为特殊文件处理，系统可以不必提供设备驱动程序。 4、下面关于设备属性的论述中正确的是（2） （1）字符设备的一个基本特性是可寻址的，即能指定输入时的源地址和输出时的目标地址；（2）共享设备必须是可寻址的和可随机访问的设备；（3）共享设备是指在同一时刻内，允许多个进程同时访问的设备；（4）在分配共享设备和独占设备时，都可能引起死锁。 5、以下关于外部设备的说法，错误的是（4） （1）外部设备分为存储型和I/O型两种。（2）存储型设备可以作为内存的扩充，信息传送单位为块。（3）I/O型设备负责内存与外设之间的信息传递，信息传输的单位是字符。（4）存储型设备一般属于共享设备，而I/O型设备则属于独占设备。 6、下面关于设备管理的论述中正确的是（1，2，3） （1）所以外设的启动工作都是由系统统一来做。（2）来自通道的I/O中断事件由设备管理负责处理。（3）编制好的通道程序存放在内存中。（4）由用户给出的设备编号是设备的绝对号。 7、计算机系统启动设备是按（3）来启动的。 （1）设备名；（2）设备相对号；（3）设备绝对号；（4）设备地址 5.2 I/O控制 1、I/O控制发展的主要推动因素是什么？ 答：（1）力图减少CPU对I/O操作的干预，把CPU从繁重的I/O控制中解脱出来，以充分发挥CPU数据处理的能力；（2）缓和CPU的高速性和I/O设备的低速性之间速度不匹配的矛盾，以提高CPU的利用率和系统吞吐量；（3）提高CPU和I/O设备的并行程度，使他们处于忙碌状态。 5.3缓冲管理 1 高速缓存和缓冲区的区别： 两者都是介于一个高速设备和一个低速设备之间的，但是它们之间有着很大的区别：（1）两者存放的数据不同。高速缓存上放的是低速设备上某些数据的一个拷贝，即高速缓存上有的数据低速设备上一定有；而缓冲区则是放置低速设备传递给高速设备的数据，然后再从缓冲区送到高速设备，而在低速设备上不一定有备份；（2）两者的目的不同：高速缓存是为了 31 存放低速设备上经常要被访问的数据，如果不能命中，高速设备仍然要访问低速设备；而缓冲区是为了缓和高速设备与低速设备间速度不匹配的矛盾而设置的，高速设备和低速设备间通信每次都要经过缓冲区，高速设备不会直接去访问低速设备。 2、判断：换冲技术是借用外存储器的一部分区域作为缓冲池。 3、在缓冲区实现机制中，为什么要将缓冲区的头部和缓冲体分开？ 提示：（1）使系统更加安全，不会产生越界访问；（2）可以提高访问效率，比如将头部放入cache，可以减少缓冲区查找时间。 4、在某系统中，从磁盘将一块数据输入到缓冲区需要花费的时间为T，cpu对一块数据进行处理的时间为C，将缓冲区的数据传送到用户区所花的时间为M，那么单缓冲和双缓冲情况下，系统处理大量数据是，一块数据的处理时间为多少？ 5、UNIX中是如何进行块设备缓冲区管理的？ 6、判断：缓冲技术是以空间换取时间，而且只能在设备使用不均衡时起到平滑作用（对） 7、在多用户系统中，实现减排驱动程序需要字符缓冲技术，请给出两种实现字符缓冲的方法。 8、若数据输入一缓冲区的设计tio始终大于对该数据的处理时间tc或者反之。试问，对上述两种情况各应采取哪种缓冲区较为合适？ 答：若tio大于tc，采用单缓冲；反之，应采用循环缓冲或者缓冲池。 9、unix如何管理缓冲区？ 答：unix分别为字符设备和块设备设置了缓冲区。（1）字符设备缓冲区管理：系统设置了一组字符缓冲区，供各种字符设备使用。其中，每个缓冲区的大小为70字节，包括4项：第一个字符位置，最后一个字符位置，指向下一个缓冲区的指针，余下的64个字节存放数据。所有空闲缓冲区链接成一个队列。缓冲区的分配和释放均可在链首处进行。（2）块设备缓冲区管理：类似缓冲池管理。每个缓冲区分成两部分：用于存放管理控制信息的缓冲首部和存放数据的缓冲区，两者一一对应，但物理上不相连，而是独立存储，只是在缓冲首部中用一个指针指向对应的缓冲区。缓冲首部还包括设备号和块号，以分别指出对应的文件系统和磁盘上的数据块。为了对缓冲区进行管理，系统设置一个双向链接的空闲链表，系统初启时，将所有的缓冲区首部链入空闲链表中。为了加速对缓冲区的查找，系统把所有缓冲区按设备号及块号所计算的散列值组织成多个散列队列，每个散列队列仍是一个双向链表。由于每一个缓冲区都在一个散列队列中，而空闲缓冲区又应链入空闲缓冲区队列，因此一个空闲缓冲区可同时链入两个队列中，从而使对一空闲缓冲区的查找可通过两种方式进行：A 若要获取任意一个空闲缓冲区，从空闲链首摘下一个即可；B 若要寻找一特定的空闲缓冲区，则搜索散列队列更方便。 10、假定吧磁盘上一个数据块中信息输入到一单缓冲区的时间T为100μs，将缓冲区中数据传送到用户区的时间M为50μs，而CPU对这一块数据进行计算的时间C为50μs，这样系统对每一块数据的处理时间为（150μs），如果将单缓冲改为双缓冲，则系统对每一块数据的处理时间为（100μs）。 5.4 I/O软件的设计目标 补充内容：中断处理： 32 （1）中断的概念：所谓中断是指CPU对系统发生的某个事件做出的一种反应，它使CPU暂停正在执行的程序，保留现场后自动执行相应的处理程序，处理该事件后，再返回断点继续执行被“打断”的程序。 引起中断的事件称为中断源。中断源向CPU提出的处理请求称为中断请求，发生中断时，被打断的程序的暂停点称为断点。 （2）中断类型： 1）按功能划分：（1）机器故障中断，如机器校验错、电源故障、主存出错；（2）I/O中断，如打印机输出结束中断、磁盘传输出错中断；（3）外中断，如计时部件发生的计时中断；（4）程序性中断，如非法操作码、算术溢出、除数为0，地址越界等；（5）访管中断，如分配内存，分配外设进行I/O操作。 2）按中断事件来源划分： 目前，很多小型机系统和微型机系统都采用这种分类方式。①中断：它是由CPU以外的事件引起的，如I/O中断、时钟中断、控制台中断等。利用中断实现设备与CPU的通信。中断是异步的，因为从逻辑上讲，中断的产生与当前正在执行的进程无关。②异常：它是来自CPU内部的事件或程序执行中的事件引起的过程。如CPU本身故障、通路校验错、主存奇偶错、非法操作码、地址越界、页面失效、调试指令、算术操作溢出、程序故障、访管指令等引起的事件。异常是同步的，又分为出错、陷入和可编程异常。出错和陷入之间最重要的区别是处理完异常事件返回时，出错事件会重新执行导致异常的那条指令，如缺页故障；而陷入事件不会重新执行那条指令它主要用于程序调试。可编程异常是由于用户在C程序中使用了系统调用而引发的过程。异常是不能被屏蔽的，一旦出现应立即响应并加以处理。 （3）中断处理过程： ①中断响应（硬件即中断装置操作）：中断处理是由软硬件结合实现的。发生中断时，CPU暂停执行当前的程序，转去处理中断。这个由硬件对中断请求作出反应的过程，称为中断响应。通常，CPU执行完一条指令后，立即检查有无中断请求（A 判别自愿性中断，只要检查操作码是否为访管指令；B 判别强迫性中断，则要检查中断寄存器内容。若为0，则无中断；若非0，则表示有中断事件发生。）。若有，而且“中断允许”触发器为1（表示CPU可以响应中断请求），则立即做出响应。一般来说，中断响应顺序执行下述三步动作： 1）暂停当前程序的执行； 2）保存原程序的断点信息（主要是PC计数器的值和程序状态字的内容）； 每个程序都有一个程序状态字（PSW）来反映本状态的执行状态，如基本状态（下一条指令的地址、条件码、管态/目态、计算/等待等）、中断码和中断屏蔽位等内容。处理器设有一个“程序状态字寄存器”用来存放当前运行程序的PSW。程序状态字可分为当前PSW（当前正在占用处理器的进程的PSW）、旧PSW（保存的被中断进程的PSW）和新PSW（中断处理程序的PSW）。 当出现中断事件后，把被中断进程的PSW保存为旧PSW，即完成断点信息保护。 33 3）转到相应的中断处理程序：CPU接到中断后，就从中断控制器中得到中断号，使用中断号查询中断向量表（里面存放了中断处理程序的入口地址和中断处理时的程序状态字PSW），然后转入中断处理程序。 中断装置通过“交换PSW”过程完成此项任务，即把出现的中断事件存放到当前PSW中断码位置，然后把该当前PSW保存为旧PSW，再把操作系统中断处理程序的新PSW送到程序状态字寄存器中，成为当前的PSW. ②中断处理： 中断响应后就由软件（中断处理程序）进行相应处理。操作系统的中断处理程序对中断事件进行处理时，大致要做三方面的工作： 1）保护被中断进程的现场信息： 把中断时的通用寄存器，控制寄存器内容及旧PSW保存到被中断进程的进程控制块中或内存中一个专门设置的中断现场保护栈中。 2）分析中断原因： 根据旧PSW的中断码可知发生该中断的具体原因。 3）处理发生的中断事件 核心调用中断处理程序，对中断进行具体处理。例如，调用终端中断处理程序ttyintr，判断终端输入输出是否正常完成。如果正常完成，则驱动程序便可做结束处理；如果还有数据要传送，则继续进行传送；如果是异常结束，则根据异常原因作相应处理。 4）恢复现场： 相应中断处理程序执行以后，要退出中断。 A 选取可以立即执行的进程。通常，退出中断后，应恢复到原来被中断的进程断点继续执行。如果原来被中断的进程是在核心态下工作，则不进行进程切换，因为进程在核心态下运行的是操作系统程序，涉及整个系统资源的管理，需要优先执行。如果原来被中断进程是用户态进程，且此时系统中存在比它优先级更高的进程，则重新进行调度。 B 恢复工作现场：把先前保存在中断现场区中的信箱（如PC、PSW，各通用寄存器中的信息等）取出复原。从时间顺序上讲，先恢复环境信息（各通用寄存器内容），再恢复控制信息（PC、PSW）。通常，使用一条不可中断的特权指令来复原控制信息。 （3） 中断优先级和中断屏蔽 1） 中断优先级 是硬件设计时确定的。中断装置按预定的顺序来响应同时出现的中断事件，这个预定的顺序称为“中断优先级”。中断优先级是按中断事件的重要性和紧迫程度来确定的 ，是由硬件设计时固定下来的。一般情况下，优先级的高低顺序依次为： 硬件故障中断 、 自愿中断 、 程序性中断 ， 外部中断和输入输出中断 . 2）中断的嵌套处理 3）中断屏蔽的作用。中断优先级只是规定了中断装置响应同时出现的中断的次序，当中断装置响应了某个中断后中断处理程序在进行处理时，中断装置也可能去响应另一个中断事件。因此会出现优先级低的中断事件的处理打断优先级高的中断事件的处理，使得中断事件的处理顺序与响应顺序不一致，而且会形成多重嵌套处理，使多现场保护、程序返回等工作变的复杂。 中断屏蔽技术就是为了解决上述问题而提出的在一个中断处理没有结束之前不响应其他中断事件，或者只响应比当前级别高的中断事件。于是，当中断装置检查到有中断事件后，便去查看PSW中中断屏蔽标志，如果没有屏蔽就响应该中断；否则，暂时不响应该中断，待屏蔽标志消除后再响应。自愿中断是不能屏蔽的。 4）中断禁止：是指在可引起中断的事件发生时系统部接收该中断信号，因而就不可能 34 提出中断请求而导致中断，就是不让某些事件产生中断。它常用在执行某些特殊工作的条件下，如求余运算，算术运算中强制忽略某些中断，如定点溢出等。在中断禁止的情况下，CPU正常运行，根本不理睬所发生的那些事件。 从概念上讲，中断屏蔽和中断禁止是不同的。前者表示硬件接受了中断，但系统暂时不响应，要延迟一段时间，待中断开放后，被屏蔽的中断就能被响应并得到处理。而后者，硬件不准许事件提出中断请求，从而使中断被禁止。 1、I/O软件通常设为四个层次：用户空间I/O软件、设备独立性软件、设备驱动程序和中断处理程序，问以下各项工作是在哪个层次上完成的？ （1）用户进程请求打印一个输出文件； （2）将一维磁盘块号转换为三维物理地址（柱面、磁道和扇区） （3）获得设备驱动程序的入口地址； （4）将终端输入的字符转换为ASCII码； （5）设备驱动进程被唤醒； （6）向设备寄存器写命令； （7）检查用户是否有权使用设备； （8）将二进制整数转化成ASCII码以便打印。（用户层） （9）维护一个最近使用块的缓存。 2、当中断发生后，进入终端处理的程序属于（用户程序；可能是用户程序，也可能是os程序；os程序；） 3、判断：在中断处理过程中，必须屏蔽中断（错） 4、由系统通过逻辑设备表实现逻辑设备到物理设备的映射。当更换物理设备时，用户的程序不用改，仅修改逻辑设备表。 5、计算机中断系统中，断点、恢复点与PC寄存器之间的关系是什么？中断源有哪些基本类型？ 提示：引起中断的事件称为中断源，中断源通常由硬件发现。中断处理程序是由操作系统处理的，属于操作系统的组成部分。 6、计算机系统中判别是否有中断事件发生应是在( B ) A.进程切换时 B.执行完一条指令后 C.执行P操作后 D.由用户态转入核心态时 7、中断装置的职能主要有三点： 1)检查是否有中断事件发生。 2)若有中断发生，保护好被中断进程的断点及现场信息，以便进程在适当时候能恢复驼行。 3)启动操作系统的中断处理程序。 8、引起I/O中断的事件有（1，2）。（选项：数据传送完毕；设备出错；设备正在处理数据；指令错；缺页；访存越界） 9、如果有多个中断同时发生，系统将根据中断优先级响应优先级最高的中断请求。若要调整中断事件的响应次序，可以利用（）。（选项：中断禁止；中断嵌套；中断响应；中断屏蔽） 10、当用户程序执行访管指令时，中断装置将使CPU（）：维持在用户态；维持在核心态；从核心态转换到用户态；从用户态转换到核心态。 35 11、中断处理程序占用处理器时，要从（）取出信息，才能分析中断发生的原因：当前PSW；新PSW；旧PSW；当前指令的操作码。 12、缺页中断属于（程序性中断），CTRl+C中断属于（外部中断）。 13、判断：中断时用户程序转换到操作系统程序的驱动源。 14、判断：采用DMA方式控制数据I/O操作要比通道 传输速度慢一些。 15、下面的事件（）不是引起中断的事件。（选项：掉电；打印完毕；程序出错；除0出错） 5.5设备分配 1、常用的I/O调度算法有哪些？试说明I/O调度中为什么不能采用时间片轮转法。 提示：原因如下：（1）独占设备的固有属性决定了不能采取时间片轮转法；（2）I/O设备的速度比cpu慢，I/O设备间来回切换的开销很大，采用时间片轮转法会导致大量的时间浪费在设备的启动和切换上；（3）由于各种I/O设备的数据传输速率相差较大，时间片的大小不好确定。 2、一个spooling系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。I通过输入缓冲区为P输入数据，P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长的数据块为单位。这些数据块均存储在同一磁盘上。因此，spooling系统的数据块通信原语始终保证满足：i+o<=max，（1），其中max为磁盘容量（以数据块为单位），i为磁盘上输入数据块总数，o为磁盘上输出数据块总数。请说明该系统在什么情况下死锁，并说明如何修正约束条件（1）防止死锁。 提示：当i=max时，o=0，若此时输入、输出缓冲区均放满数据，则I/P/O均阻塞，进入死锁状态；将（1）修改为：i+o<=max,且i<=max-1即可。 3、在spooling系统中，用户进程实际分配到的是（）：用户所要求的外设；一块内存区，及虚拟设备；共享设备的一部分存储区；虚拟设备的一部分空间； 4、（）是操作系统中采用的以空间换时间的计数。（Spooling技术；虚拟存储技术；覆盖与交换技术；通道技术） 5、有关设备的管理中，( ADE )是正确的。 A.“计算机系统为每台设备确定一个绝对号” B.“每台设备都应该有一个惟一的相对号” C.“申请设备时指定绝对号可提高设备的使用率” D.“申请设备时指定设备相对号使设备分配的灵活性强” E.“启动设备时应指出设备的绝对号” 6、实现虚拟设备的硬件条件是什么?操作系统应设计哪些功能程序? 硬件条件是：配置大容量的磁盘，要有中断装置和通道， 操作系统应设计好“预输入”程序，“井管理”程序，“缓输出”程序。 7、什么是虚拟设备？为什么要引入虚拟设备？实现虚拟设备时所依赖的关键技术是什么？ 答：虚拟设备是指通过某种技术，把一个物理设备变成若干台逻辑设备。逻辑设备实际上并不存在，只是给用户的一种感觉。 引入虚拟设备的原因是为了克服独占设备所具有的速度较慢、资源的利用率较低的缺 36 点，以提高设备的利用率。 实现虚拟设备所依赖的关键技术是分时技术。即多个用户进程通过分时的方式使用同一台物理设备。宏观上，是若干进程在同时执行I/O操作，而微观上，则是一台物理设备分时地为每个进程服务。目前最广泛的虚拟设备技术是SPOOLing技术。 8、SPOOLing对一个批处理系统是必要的，为什么？对一个分时系统需要吗？在多道程序系统中，为什么要实行SPOOLing技术？ 答：SPOOLing对一个批处理系统是必要的，原因是：SPOOLing能实现作业的预输入缓输出功能，从而可在系统提供的输入井中，形成作业的预备队列，为作业调度提供方便；另外，SPOOLing还能实现虚拟设备功能，支持多道作业对系统配置的少量设备的需求。分时和批处理都需要缓输出功能。在多道程序系统中，系统的共享设备数量有限，为避免竞争使用独占设备而死锁，利用SPOOLing技术把独占设备改造成共享设备，这样不但提高了独占设备的利用率，还提高了I/O的速度，从而提高了CPU与外设的并行度。 9、假设一个单处理机系统，以单道批处理方式处理一个作业流，作业流中有两道作业，其占用CPU计算时间、输入卡片数、打印输出行数如表所示： 作业号 A B 占用CPU计算时间（分） 输入卡片张数（张） 输出行数（行） 3 2 100 200 2000 600 其中，卡片输入机速度为1000张/min；打印机速度为1000行/min。试计算： （1）不采用SPOOLing技术，计算这两道作业的总运行时间（从第一个作业输入开始，到 第二个作业输出完成为止）。 （2）如果采用SPOOLing技术，计算这两道作业的总运行时间。 答：（1）=（0.1+3+2）+（0.2+2+0.6）=7.9分 （2）=0.1+3+2+0.6=5.7分 5.6磁盘管理 1、一个快速磁盘转速为7200RPM，每磁道160个扇区，每扇区512字节，那么理想状态下，其数据传输速率为（）。 2、判断：优化在磁盘上文件物理块的分布可显著减少寻道时间，因此能有效地提高磁盘I/O的速度。 3、设L,M,N分别表示盘组的柱面数、盘面数、扇区数，B表示块号，则第i柱面、j磁头、k扇区所对应的块号B为：B=(i*M*N)+(j*N)+k 式中，i=0，1，?，L-1；j=0，1，?，M-1；k=0，1，?，N-1 同样，根据B可以计算磁盘位置： 柱面号i=int（B,M*N） 磁头号j=int（mod（B,M*N）,N） 扇区号k=mod（mod（B,M*N）,N） 4、假定磁盘的存取臂现在处于6＃柱面上，有如下表所示的六个请求等待访问磁盘，试列出最省时间的响应顺序。（答：6，2，1，4，3，5） 37 序号 1 2 3 4 5 6 柱面号 7 5 15 7 20 5 磁道号 6 5 20 4 9 15 扇区号 3 6 6 4 3 2 2、假定有4各记录A,B,C,D，顺序放在磁盘的某磁道上，该磁道划分为4块，每块存放一个记录。现在要顺序处理这些记录，如果磁盘的转速为20ms转一周，处理程序每读出一个记录后花5ms时间进行处理。问：处理完这4个记录需要多少时间？为了缩短处理时间应如何安排这些记录？并计算处理的总时间。 3、磁盘调度的相关问题：各种调度算法 4、在某系统中，数据从磁盘读入缓冲区，然后从缓冲区传人用户区，再在用户区中处理。假设该磁盘系统中文件在磁道上非连续存放，磁头从一个磁道移至另一个磁道需要时间t1，逻辑上相邻数据块的平均距离为d磁道，每块的旋转延迟时间及传输道缓冲区的传输时间分别为t2和t3。问读取N个数据块的磁盘访问时间一共是多少？另外，假设将缓冲区的数据传送到用户区所花费的时间为t4且t4远远小于读取一个数据块的磁盘访问时间，CPU对一块数据进行处理的时间为t5。问分别在单缓冲和双缓冲情况下，一块数据的总处理时间是多少？ 8、假设一个磁盘组共100个柱面，每个柱面上有8个磁道，每个盘面被分成8个扇区。现有一个含有6400个逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从0开始，逻辑记录的编号也从0开始。文件信息从0柱面、0磁道、0扇区开始存放，试问： （1）该文件的第3680个逻辑记录应该存放在什么位置？ （2）第78柱面的第6磁道的第6扇区中存放了该文件的第几个逻辑记录？ 9、有10个记录在某磁盘的一个磁道上，假定这个磁道划分为10个扇区，每个扇区存放一个记录。现在要从磁道上顺序地将10个记录读出，如果磁盘转速为20ms转一周，处理程序每读出一个记录后花4ms进行处理。问处理完10个记录的总时间是多少？为缩短处理时间应如何安排这些记录？需要多少处理时间？ 10、对于硬盘上存放的信息，物理上读写的最小单位是一个（）（选项：二进位；字节；物理块；逻辑记录） 11、一个软盘有40个柱面，寻道时移过每个柱面花费6ms，若不采取任何使文件的块尽量紧密存放的措施，则逻辑上相邻的块平均间隔13个柱面，如果采取一定的措施使得文件中相邻的块尽可能放在一起，则块间的平均间隔是2个柱面。假定读写时找到柱面后平均旋转时间为100ms，传输速率为每块25ms，则在此两种情况下传输一个100块的文件各需要多长时间？ 12、下列磁盘电动算法中，（2，5）算法可能会随时改变移动臂的运动方向。 （1）电梯；（2）FCFS；（3）循环扫描；（4）最短寻道时间 13、有一移动臂磁盘，共100个磁道，每个磁道分8个扇区，磁盘转速为500r/s，磁头每移动一个磁道需要10ms，有一个用户请求访问第25磁道的第3扇区，并立即被系统响应， 38 假设磁头当时处于15磁道上，磁头到达第25道时正处于1扇区的开始位置，试计算该用户至少需要等待多时时间？ 答：寻道时间=（25-15）*10=100ms 延迟时间=（3-1）*0.25=0.5ms 传输时间=0.25ms 第六章 文件系统 1、文件系统的性能对整体系统的性能影响很大，请说明在实现文件系统时可以从哪些方面提高文件系统的性能。 提示：目录管理；文件使用方式：打开、关闭；文件保护（包括文件恢复、口令、密码、访问控制等）；提高磁盘读写速度的方法（磁盘高速缓存、提前读、延迟写、优化物理块分布、并行交叉存取等） 2、有关文件管理与设备管理的关系，判断： （1）文件管理与设备管理时操作系统好 的两个完全独立的功能，二者不存在任何关系。 （2）设备管理与文件系统密切相关，文件系统是设备管理的基础，设备管理必须依赖文件管理才能最终完成相应的功能。 （3）文件系统为用户按名存取服务，实现逻辑文件与物理文件之间的映射，而文件信息的存取是设备管理部分完成的。 （4）设备管理时文件系统的基础，文件管理是设备管理的一部分。 3、可通过哪些途径改善文件系统的性能？ 答：（1）改进文件的目录结构以及检索目录的方法，来减少对文件的查找时间；（2）选择好的文件存储结构，以提高对文件的访问速度；（3）通过采用磁盘高速缓存、优化物理块的分布、利用提前读、延迟写或虚拟盘等方法来提高磁盘I/O速度，以提高对数据的传送速度。 6.1文件和文件系统 1、使用文件时，通常要显示地进行OPEN、CLOSE操作。 （1）这样做的目的是什么？（2）能否取消？应如何做？（3）取消后有什么不利？ 提示：（3）取消open，则每次使用文件都要判断文件是否已经打开，增加系统开销；取消close，则文件打开后会一直驻留在内存直到进程或系统结束、浪费系统资源。 2、判断：打开文件的功能就是将文件复制到主存。 3、判断：特殊文件是指其用途是由用户特殊规定的文件。 4、打开一个UNIX系统的文件，需要几个数据结构？之间的联系如何？ 提示：索引节点、内存索引节点表，系统打开文件表、用户打开文件表、每个open返回给进程一个文件描述符，它是用户打开文件表中的表项序号，它在用户打开文件表中对应的表项指向系统打开文件表中唯一的表项。一个被打开文件的所有实例所对应的表项指向内存索引节点表中的同一表项。 5、在文件系统中可命名的最小数据单位是（数据项），用户以（记录）为单位对文件进行后 39 存取、检索等，对文件存储空间的分配则以（文件）为单位。 选项：字符串；数据项；记录；文件；文件系统 6.2文件逻辑结构 1、假定磁带的记录密度为每英寸800个字符，每一个逻辑记录长为160个字符，块与块之间的间隙为0.6英寸，现有1000个逻辑记录需要存储到磁带上，问： （1）不采用成组操作时，磁带空间的利用率是多少？ （2）采用以5个逻辑记录为一组的成组操作时，磁带空间的利用率是多少？ （3）为了是磁带空间的利用率大于50％，采用记录成组的块因子至少是多少？ 2、某用户文件共10个逻辑记录，每个逻辑记录的长度为480个字符，现把该文件存放到磁带上，若磁带的记录密度为800字符/英寸，块与块之间的间隙为0.6英寸，回答下列问题： (1)不采用记录成组操作时磁空间的利用率为__________。 (2)采用记录成组操作且块因子为5时，磁带空间的利用率为__________。 (3)当按上述方式把文件存放到磁带上后，用户要求每次读一个逻辑记录存放到他的工作区。 当对该记录处理后，又要求把下一个逻辑记录读入他的工作区，直至10个逻辑记录处理结束。系统应如何为用户服务? 提示：(1)利用率为50% (2)利用率为83% (3)设置长度为2400字符的主存缓冲区；找到该文件的存放位置，启动磁带机读出第一块内容存入主存缓冲区；进行记录分解，按用户要求依次把主存缓冲区中的五个记录传送到用户工作区；启动磁带机读第二块内容存入主存缓冲区，把第6至10个逻辑记录按用户要求依次传送到用户工作区。 4、下列叙述中正确的是（3，4）。 （1）在磁带上的顺序文件中插入新的记录时，必须复制整个文件；（2）由于磁带的价格比磁盘便宜，用磁带实现索引文件更经济；（3）在磁带上的顺序文件的最后添加新纪录时，不必复制整个文件；（4）变更磁盘上的顺序文件的记录内容时，不一定要复制整个文件；（5）在磁盘上的顺序文件中插入新的记录时，必须复制整个文件 5、对记录式文件，操作系统为用户存取文件信息的最小单位是（）（选项：字符；数据项；记录；文件） 6.3外存分配方式 1、判断：同一文件在不同的存储介质上应该用相同的组织形式。 2、如果文件采用直接存取方法使用，且文件大小不固定，则应采用（）物理结构。（选项：直接；索引；随机；顺序） 1、如果一个文件存放在100个数据块中，文件控制块、索引块或索引信息等都驻留在内存。下面各种情况下，需要做几次磁盘I/O操作？ （1）连续分配，将最后一个数据块搬到文件头部（200次） （2）单级索引分配，将最后一个数据块搬到文件头部（0次） （3）隐式链接分配，将最后一个数据块搬到文件头部（0次） 40 （4）采用隐式链接，将第一个数据插入文件尾部（102次） 2、在UNIX中，若盘块为1KB，每块可放256个地址，如何将下列文件的偏移量转换为物理地址：9000，18000，420000 3、某文件系统中，外存为硬盘，物理块大小为512B。有文件A，包含590个逻辑记录，每个记录占255B，每个物理块存放2个逻辑记录。文件A所在的目录如图所示。每个目录项占127B，每个物理块放4个目录项。问： （1）若文件采用串联结构，链接字占2B，那么要将A读入内存，至少需要存取几次硬盘？（300次） （2）若文件采用连续结构，那么要将A的第480号记录读入内存，至少要存取几次硬盘？（5次） Root Bin dev etc boot usr tmp Mike marv you he File dir1 dir2 A B C D E 4、某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项，假定物理块的大小是2K，每个索引项占用4B，问： （1）该文件系统中最大的文件可以达到多大？ （2）假定一个文件的实际大小是128MB，该文件实际占用磁盘空间多大（包括间接索引块）？ 5、一个文件有100个磁盘块，假设文件控制块在内存。在下列情况下，分别计算并说明在连续分配和显示链接分配方式下，分别需要执行多少次磁盘I/O操作？（假设每读或写一块磁盘块就是一次磁盘操作；假设在连续分配下，文件头部无空闲的磁盘块，但文件尾部有空闲的磁盘块） （1）在文件开始处添加一个磁盘块（需要往添加的磁盘块中写数据）； （2）在文件第50块前添加一个磁盘块（不需要往添加的磁盘块中写数据）； （3）删除文件第50块磁盘块； （4）在文件结尾处删除一个磁盘块。 6、假定磁盘块的大小为1KB，对于540MB的硬盘，其文件分配表FAT需要占用多少存储空间？如果硬盘容量是1.2GB呢？ 7、判断：使用链接结构组织的文件适合于采用随机访问的方式。 8、在磁盘上有一个文件系统，磁盘每块512字。假定每个文件在目录中占有一个目录项，该目录项给出了文件名、第一个索引块的地址、文件长度（块数）。在索引块中（包括第一个索引块）前面511个字指向文件块，即第i个索引项（i=0，1，2，…510）指向文件的第i块，索引块中最后一个字指向下一个索引块，最后一个索引块中最后一个字为null。假定目录在存储器中，每个文件的逻辑块号均从0开始编号，逻辑块与物理块长相同。对这样的 41 索引物理结构，该系统应如何将逻辑块号变换成物理块号？ 提示：（1）计算组号：a=m/511,再计算组内块号：b=mQ1,设置i=0，转（2） （2）若i==a，则读出该组内第b+1个索引项，该索引项指向的块号就是物理块号，结束；若i！=a，读出第512项索引项，并读出该索引项对应的索引块，转（2）。 9、有一个文件系统如下图所示。图中的方框表示目录，圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址（各占2个字节，共4个字节）。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后4个字节供拉链使用。下级文件在上级目录文件中的次序在图中为从左至右。每个磁盘块有512字节，与普通文件的一块等长。普通文件的文件控制块内容包括：该文件的有关描述信息和文件地址信息，其中前10个地址直接指示该文件前10个块的地址，第11、12、13个地址分别是一级索引、二级索引、三级索引。问： （1）一个普通文件最多可以有多少个数据块？ （2）若要读文件J中的某一块，最多启动磁盘多少次？ （3）若要读W文件中的某一块，最少启动磁盘多少次？ （4）就（3）而言，为最大限度减少启动磁盘的次数，可采用什么方法？此时，磁盘最多启动多少次？ 根目录ABCDEFGHIJKLMNPQRSTUVW 13、回答：（1）在unix文件系统中，inode节点包括哪些内容？（2）当两个进程打开同一个文件是，在内核中是否会存在该文件的两个i节点？两个进程读写文件的偏移量是否始终相同？（3）假设unix文件系统采用2级索引结构，每个磁盘块大小为4K字节，保存一个 22 磁盘块号需要4个字节，则文件的最大长度可以为多少个字节？（40K+2K） 14、假设某个采用页式虚拟内存管理的unix类型的操作系统中，每个i节点中包含12个直接块指针以及一次、二次、三次间接指针各一个。另外，假设页面大小和磁盘扇区大小都是8192字节，每个磁盘块指针占用64位。假设该操作系统的文件系统带有按照磁盘扇区大小划块的内存缓冲区，且被访问的文件已被打开。若某用户程序要访问该文件第13423956个字节，最多需要多少次磁盘访问？请说明每次访问磁盘的目的。 42 15、设一个文件占据了100个物理块，对于连续结构、链接结构和索引结构的文件，如果要将一块信息按下述要求操作，假设文件的文件控制块已经在内存，问分别要启动多少次磁盘I/O操作？ （1）加在文件的首部（连续结构201次，链接结构1次，索引结构1次） （2）加在文件中间（101次，51次，1次） （3）加在文件的尾部（1次，2次，1次） （4）从文件的首部删去（0次，1次，1次） （5）从文件的中间删去（98次，52次，1次） （6）从文件的尾部删去（0次，1次，1次） 15、采用直接存取法存取文件时，对（索引文件）效率最高，对（链接文件）效率最低。 16、文件结构、文件存储设备和存取方法之间的关系。 文件的物理结构密切依赖于文件存储器的特性和存取方法。常用的文件存储器有磁带和磁盘、磁带属于顺序存储设备，适合构造连续结构文件，相应的存取法通常是顺序存取法。磁盘属于直接存储设备，各种物理结构都可采用：如果采用顺序存取法，几种物理结构都可以存钱；如果采用直接存取法，则索引文件效率最高，连续文件效率居中，串联文件效率最低。 17、文件存储器、文件物理结构和存取方法的关系： 存储设备 文件结构 存取方法 磁盘 连续 顺序、直接 链接 顺序 索引 顺序、直接 磁带 连续 顺序 18、判断：文件的物理结构与具体的文件存储设备无关。 19、假定unix系统中的磁盘块大小为512B，现在要对一个已经打开的1M大小的文件遍历一遍，将要发生多少次磁盘完成中断？ 20、对于连续文件、串联文件和索引文件三种物理结构，连续文件适合的场合是（没有）；串联文件适合的场合是（全适合）；索引文件适合的场合是（3，4）。 （1）从文件头部扩展；（2）从文件中部扩展；（3）从文件尾部扩展； （4）从文件头部删除；（5）从文件中部删除；（6）从文件尾部删除 21、下面说法正确的是（1，4） （1）在磁带上的顺序文件中插入新的记录时，必须复制整个文件； （2）在磁盘上的顺序文件中插入新的记录时，必须复制整个文件； （3）在索引顺序文件的最后添加新的记录时，一定复制整个文件； （4）在磁带上的顺序文件的最后添加新的记录时，不必复制整个文件。 6.4 目录管理 1、在某个文件系统中，每个盘块为512B，FCB为64B，其中文件名占8B，如果采用类似UNIX系统的方法，将文件名与文件其他描述信息分开存放，在文件目录项中只包括文件名和索引节点的编号，索引节点编号占2B，对一个存放在磁盘上的1024个目录项的目录，试比较引入索引节点前后，为找到其中一个文件的FCB，平均启动磁盘的次数。 2、在实现文件系统时吧文件目录的目录项分成两部分：索引节点和符号目录项，有什么好处？ 3、设置当前目录的主要原因是（节省主存空间；加快文件查找速度；节省辅存空间；便于打开文件） 4、UNIX系统中，数据结构磁盘索引节点(dinode)中有数据项di_nlink，活动索引节点(inode) 43 中有数据项i_count而系统打开文件表(file)中有数据项f_count。简述这三个数据结构之间的联系。并指出这三个数据项的作用。 提示：di_nlink指出文件(或目录)的连接数是(相对)静态的 i_count则是活动的，即正在使用该内存i节点的计数，即动态的 nlink方便使用不同目录(尤其是“离”得较远时)，打开一文件后即f_count 为 1,i_count增1;关闭时各减1 f_count为0时，系统打开文件表项为自由的 i_count为0时，内存活动索引节点表项为自由的 di_nlink为0时，该文件被删除，收回文件空间和i_node空间 5、使用文件系统时，通常要显式地进行OPEN和CLOSE操作，这样做的目的是什么？如果一个文件系统采用基于文件分配表的多级目录结构，假设文件分配表大小为500KB，盘块大小为1KB，文件分配表的每一个表项占2.5字节，根目录区大小为32KB，目录项大小为16B，计算文件系统可管理的数据区大小，根目录中容纳的文件数目。并针对该文件系统，说明OPEN操作过程中对文件系统的操作。 6.5文件存储空间的管理 1、在UNIX系统中有卷资源表如图所示： （1） 现有一个进程要释放4个物理块，其块号为150＃、156＃、172＃、177＃，画出卷 资源表的变化。 （2） 在（1）的基础上假定一个进程要求分配5个空闲块，画出分配后的卷资源表。 S_nfree=98 S_nfree[0]=120 S_nfree[1]=121 ? S_nfree[96]=145 S_nfree[97]=210 2、在UNIX中，每个i节点中有10个直接地址和一、二、三级间接索引。若每个盘块512B，每个盘块地址4B，则一个1MB的文件分别占用多少间接盘块？20MB的文件呢？ 3、若8个字（字长32位）组成的位示图管理内存，假定用户归还一个块号为100的内存块时，它对应位示图的位置为（4，4） 4、假设一个磁盘组共有100个柱面，每个柱面有8个磁道，每个盘面被分为4个扇区。逻辑记录的大小与扇区大小相等，柱面、磁道、扇区的编号均从“0”开始，现用字长为16位的200个字（第0到199字）组成位示图来指示磁盘空间的使用情况。问： （1）文件系统发现位示图中第15字第7位为0而准备分配给某一记录时，该记录会存放到磁盘的哪一块上？此块的物理位置（柱面号、磁道号和扇区号）是多少？ （2）删除文件是还要归还存储空间，第56柱面第6磁道第3扇区的块就变成了空白块，此时，位示图中的第几位应该由1改成0？ 44 6.6文件共享和保护 1、判断：用户对文件的访问，将由用户访问表、目录访问权限及文件属性三者的权限所确定。 2、为防止用户使用共享文件时可能造成文件被破坏，通常可采用（）方法来保护文件。（选项：建立多个副本；定时转储文件；规定使用权限；设置口令） 3、系统及安全管理的主要任务是防止（未经核准的用户进入系统）；用户级安全管理的主要任务是为用户（分配“文件访问权”）；目录级安全管理的主要任务是为保护系统的（各级目录）；文件级安全管理的主要任务是控制（用户对文件的访问）。 45