习题1
1．单项选择题
（1）大中小型计算机是以 B 为中心的计算机系统。 A、CPU B、存储器 C、系统总线 D、通道 （2）以下关于操作系统的说法正确的是 B 。
A、批处理系统是实现人机交互的系统
B、批处理系统具有批处理功能，但不具有交互能力 C、分时系统是实现自动控制，无须人为干预的系统 D、分时系统即具有分时交互能力，又具有批处理能力
（3）操作系统的职能是管理软硬件资源、合理地组织计算机工作流程和 A 。 A、为用户提供良好的工作环境和接口
B、对用户的命令作出快速响应
C、作为服务机构向其它站点提供优质服务
D、防止有人以非法手段进入系统
（4）设计实时操作系统时，首先应考虑系统的 B。 A、可靠性和灵活性 B、实时性和可靠性 C、优良性和分配性 D、灵活性和分配性 （5）多道程序设计是指 D 。
A、在分布式系统中同一时刻运行多个程序 B、在一台处理器上并行运行多个程序 C、在实时系统中并发运行多个程序 D、在一台处理器上并发运行多个程序
（6）以下关于并发性和并行性的说法正确的是 B 。
A、并发性是指两个及多个事件在同一时刻发生
B、并发性是指两个及多个事件在同一时间间隔内发生 C、并行性是指两个及多个事件在同一时间间隔内发生 D、并发性是指进程，并行性是指程序 2．填空题
（1）微机是以 总线 为纽带构成的计算机系统。
（2）在批处理兼分时系统中，往往把由分时系统控制的作业称为 前台 作业，把由批处理系统控制的作业称为 后台 作业。
（3）在分时系统中，若时间片长度一定，则 用户数量越多 ，系统响应时间越慢。 （4）分布式操作系统能使系统中若干台计算机 协同 完成一个共同的任务，分解问题成为子计算并使之在系统中各台计算机上 并行执行 ，以充分利用各计算机的优势。
（5）用户通过网络操作系统可以 资源共享 、 网络通信 ，从而大大扩展了计算机的应用范围。
3．简答题
（1）什么是操作系统？现代操作系统的基本特征是什么？
操作系统是直接控制和管理计算机系统的软件和硬件资源，合理的安排计算机工作流程，便于用户使用的程序的集合。
并发性。
（2）什么是批处理系统，衡量批处理系统好坏的主要指标是什么？ 及时性。
（3）试述分时系统的原理及其特性。 及时性、同时性、独立性、交互性。时间片原则 （4）操作系统有哪几大特征？它的最基本特征是什么？ 虚拟性、异步性、并发性、共享性。
（5）网络操作系统与分布式操作系统的关键区别是什么？ 分布性。 4．综合应用题
有3个程序A、B、C在系统中单独处理占用的CPU时间和I/O设备时间如下表所示：
程序A 程序B 程序C CPU 20ms IO2 30ms IO1 20ms IO2 30ms CPU 30ms IO2 20ms CPU 30ms CPU 30ms CPU 20ms IO1 20ms IO1 20ms IO2 30ms CPU 30ms CPU 50ms IO1 40ms IO1 30ms
假定在具有2个CPU为X和Y的多机系统中，以多道程序设计方式，按如下条件执行上述3个程序，条件如下：
（1）X和Y运算速度相同，整个系统可以同时执行2个程序，并且在并行处理程序时速度也不下降。
（2）X的优先级比Y高，即当X、Y均能执行程序时，由X去执行。
（3）当多个程序同时请求CPU或I/O设备时，按程序A、B、C的次序分配所请求的资源。
（4）除非请求输入输出，否则执行中的程序不会被打断，也不会把控制转给别的CPU。而且因输入输出而中断的程序再重新执行时，不一定仍在同一CPU上执行。
（5）控制程序的介入时间可忽略不计。 （6）程序A、B、C同时开始执行。 求：（1）程序A、B、C同时开始执行到执行完毕为止的时间。（2）X和Y的使用时间。 程序运行情况如下图所示：
0 20 30 60 70 90 100 110 130 140 150 170 180 单位：ms 程序A 程序B CPU X CPU Y I/O1 I/O2 由上图可以看出
（1）A 170ms B 150ms C 180ms (2)X的使用时间 120ms Y的使用时间 90ms
程序C 习题2
1．单项选择题
（1）用户使用操作系统通常有3种手段，它们是终端命令、系统调用命令和 B 。
A、计算机高级指令 B、作业控制语言 C、宏命令 D、汇编语言 （2）系统调用的目的是 A 。
A、请求系统服务 B、终止系统服务 C、申请系统资源 D、释放系统资源
（3）在批处理系统中，用户使用 D 对作业的各种可能的控制要求进行控制。
A、命令驱动 B、访管指令 C、系统调用 D、作业说明书
（4）适合于交互式终端用户来说明作业加工步骤的手段是 E 。 A、汇编语言 B、高级语言 C、作业控制语言 D、系统功能调用 E、操作控制命令
2．填空题
（1）操作系统代码在 核心态 下运行，用户一般程序在 用户态 下运行。 （2）当用户程序要调用系统服务时，需要通过一条专门的指令来 实现用户态到核心态的转换 的切换，这条指令称为 访管指令 。
（3）操作系统为批处理用户提供 作业控制语言 ，为分时用户提供 操作系统命令 来说明作业加工步骤。
（4）作业控制语言是由一些 I/O命令、编译命令、操作命令、条件命令 的语句组成的。
（5）批处理控制方式也可以称为 脱机控制方式 ，交互式控制方式也可以称为 联机控制方式 。
（6）在批处理系统中，用户提交作业时必须同时提交用 作业控制语言 编写的 作业说明书 来说明对作业的控制意图。
3．名词解释
（1）作业控制级接口。 （2）程序级接口。 （3）用户态。 （4）核心态。 （5）特权指令。 （6）访管指令。 （7）系统调用。 4．简答题 （1）在用户和操作系统之间，通常提供了哪几种类型的接口？它们的主要功能是什么？ （2）什么是作业、作业步、作业流？
（3）命令驱动方式中命令的一般格式是什么？主要有哪几种命令类型？ （4）什么是特权指令？为什么要把指令分为特权指令和非特权指令？ （5）说明以下各条指令是特权指令还是非特权指令。
1）启动打印机； 2）结束进程； 3）计算e的n次方； 4）清内存
5）读时钟 6）修改指令地址寄存器内容。 12456 特权指令 3 非特权指令
（6）系统调用分为哪几类？它们各有什么作用？ （7）一个图形窗口通常由哪几部分组成？
习题3
1．单项选择题
（1）进程创建原语的任务是 B 。
A、为进程编制程序 B、为进程建立PCB表
C、为进程分配CPU D、为进程分配所需的各种资源 （2）进程从执行状态变为阻塞态的原因可能是 A 。 A、I/O事件发生 B、I/O事件完成 C、时间片到 D、某个进程被唤醒
（3）进程由执行态变化到就绪态的可能原因是 B 。 A、等待的事件发生 B、高优先级进程到来 C、I/O完成 D、等待某事件的发生
（4）进程在执行过程中，其状态总是在不停地发生变化，下面关于进程状态变化的说法正确的是 B 。
A、 进程一旦形成，首先进入的是运行状态 B、 在分时系统中，一个正在运行的进程的时间片如果终结，该进程将转入就绪状
态 C、 一个进程必须经过进程的三个基本状态才能结束 D、 三种进程状态是进程运行过程中的基本状态，进程可能同时处于某几种状态中 （5）进程的上下文是执行活动全过程的静态描述，它在 B 时切换。
A、 系统调度新进程占有CPU时 B、 进程因等待某一事件的发生而由运行态转为阻塞态时 C、 进程由阻塞态转为就绪态时 D、 作业因完成而撤出时
（6）以下进程状态的转换中， C 是不可能的。 A、运行态?就绪态 B、运行态?阻塞态
C、阻塞态?运行态 D、阻塞态?就绪态
（7）同一程序运行在不同的数据集上，创建了 B 的进程。 A、相同 B、不同 C、同步 D、互斥
（8）进程调度是从 A 中选择一个进程进入处理器中运行。 A、就绪队列 B、阻塞队列 C、提交队列 D、后备队列
2．填空题
（1）一个进程获得了除 CPU 外的一切资源，则称此进程处于就绪态。
（2）一个进程由于 等待某一事件发生或请求I/O设备 而暂时停止运行，这时即使把CPU分配给进程也无法运行，则称该进程处于阻塞态。
（3）在一个只有一个CPU的系统中，假如某时刻该系统中有10个进程并发执行，在略去调度时间所占用时间的前提下，则：
1）这时刻系统中处于运行态的进程最多有 1 个，最少有 0 个。 2）这时刻系统中处于就绪态的进程最多有 9 个，最少有 0 个。 3）这时刻系统中处于阻塞态的进程最多有 10 个，最少有 0 个。
（4）操作系统对进程的控制是根据 PCB 来进行的，对进程的管理是通过 PCB 来实现的。
3．基本概念的解释和辨析 （1）进程和程序 （2）进程和作业 （3）进程和线程 （4）原语和系统调用 （5）内核和微内核
（6）用户级线程和核心级线程 4．综合题
（1）某系统的进程状态转换图如图3．16所示，请说明：
1）引起各种状态转换的典型原因有哪些？
运行态→就绪态 时间片到或被更高优先级的进程抢占 就绪态→运行态 被调度
运行态→阻塞态 等待某一事件的发生而事件未发生 阻塞态→就绪态 等待的事件已发生
2）当观察系统中某些进程时，能够看到某一进程的一次状态转换能引起另一个进程的
运行 2 1 就绪 4 3 阻塞 图3．16某系统进程状态转换图 一次状态转换。在什么情况下，当一个进程发生转换3时能立即引起另一个进程发生转换2？
3）如图3．16，说明是否会发生下述因果转换： 2→1 会，在抢占式调度的情况下，更高优先级的进程到达 3→2 会，一个正在运行的进程因等待某一事件的发生而转入阻塞态，而就绪队列中有进程在等待运行 4→1 不会
（2）有一个单向链接的进程PCB队列，它的队首由系统指针指出，队尾进程链接指针为0。分别画出一个进程从队首入队和队尾入队的流程图。
（3）挂起状态和阻塞状态有何区别？在具有挂起操作的系统中，进程的状态有哪些？如何变迁？
被挂起进程处于静止状态，不能参与竞争CPU，直到被激活，但被挂起进程可能并不缺少资源；而阻塞进程是由于等待某一事件的发生，处于缺乏资源的状态。
（4）在创建一个进程时需要完成的主要工作是什么？在撤消一个进程时需要完成的主要工作又是什么？
创建进程的主要工作是为被创建进程创建一个PCB，并填入相应的初始值。并把该进程插入就绪队列。
撤消该进程的所有子孙进程。在撤消的过程中，被撤消进程的所有系统资源（内存、外设）应全部释放出来归还给系统，并将它们从所有队列中移出。如果被撤消进程正在处理器上运行，则要调用进程调度程序将处理器分配给其它进程。
（5）什么是可再入程序？其有何特性？
能被多个程序同时调用的程序。它具有以下性质：它是纯代码的，即它在执行过程中不改变自身代码，通常由指令和常量等程序逻辑中的不变部分组成；调用它的各程序应提供工作区，用以存放随着程序执行将发生变化的部分，诸如程序中的数组、变量和通用存储器内的信息。
（6）在使用线程的系统中，是每个线程有一个堆栈还是每个进程有一个堆栈？说明原因。
（7）线程通常有哪些状态？为了管理线程，操作系统一般提供哪些原语？ 线程状态：就绪态，运行态，阻塞态 原语：派生，阻塞，激活
习题4
1．单项选择题
（1）要避免出现与时间有关的错误，对若干进程的相关临界区的管理应满足以下除 C 外的要求。
A、 一次最多让一个进程在临界区中执行 B、 任何一个进入临界区执行的进程必须在有限时间内退出临界区 C、 避免进程进入相关临界区
D、 不能强迫一个进程无限期地等待进入它的临界区
（2）有三个进程P1、P2、P3共享同一个程序段，而每次最多允许两个进程进入该程序段，则信号量S的初值为 C 。
A、0 B、1 C、2 D、3
（3）在操作系统中wait、signal操作是一种 D 。 A、机器指令 B、系统调用命令 C、作业控制命令 D、低级进程通信
（4）用signal操作唤醒一个进程时，被唤醒进程的状态应变成 C 状态。 A、等待 B、运行 C、就绪 D、完成
(5)用信箱实现并发进程间的通信需要两个基本的通信原语，它们是 B 。 A、wait原语和signal原语 B、send原语和receive原语 C、R（S）和W（S） D、以上都不是 （6）用来实现进程同步与互斥的wait，signal操作，实际上是 D 的过程。 A、一个可被中断 B、一个不可被中断
C、两个可被中断 D、两个不可被中断 2．填空题
（1）临界资源是 一次仅允许一个进程访问 的资源，临界区是 进程中访问临界资源的那段代码 。
（2）信号量s>0时，表示 有s个可用的资源 ；当s=0时，表示 资源已经用完，但没有进程在等待 ；若s<0，则表示 有|s|个进程在等待资源 。
（3）设计进程同步机制的准则有 空闲让进 、 忙则等待 、 有限等待 和 让权等待 。 3. 基本概念解释和辨析 （1）同步与互斥。
（2）临界资源与临界区。 （3）高级通信与低级通信。 （4）直接通信与间接通信。 4．论述题
（1）什么是“忙等待”？如何克服“忙等待”？
如果在单处理器系统中，一个进程试图进入处于“忙”状态的临界区，则该进程只能不断测试临界区的状态，这就是“忙等待”。
让试图进入“忙”状态的临界区的进程“睡眠”等待，由释放资源的进程将其唤醒，便可克服“忙等待”的缺点。
（2）在解决进程互斥时，如果TS指令的执行可以中断，则会出现什么情况？而如果wait、signal的执行可分割，又会出现什么情况？
如果wait可被分割，则可能破坏“空闲让进”准则。如s.value=1，进程A执行wait操作，进行s.value--，s.value的值为0；如果此时被中断，进程B执行wait操作，进行s.value--，s.value的值为-1，则进程B将被阻塞；此时进程A恢复中断，由于s.value的值为-1，也将被阻塞，从而破坏了“空闲让进”准则。
如果signal可被分割，也有可能破坏“空闲让进”准则。如s.value=-1，进程C在等待s资源，进程A执行signal操作，进行s.value++，s.value的值为0；如果此时被中断，进程B执行signal操作，进行s.value++，s.value的值为1，进程B不会唤醒进程C；此时进程A恢复中断，由于s.value的值为1，也不会唤醒进程C，从而破坏了“空闲让进”准则。
（3）使用parbegin改写下面的表达式以获得最大程度的并行性。 (3*a*b+4)/(c+d)**(e-f)
typedef Fan_Type DataType; Fan_Type x;
Fan_Type P1( )
{ return(3*a*b+4); }
Fan_Type P2( ) { return(c+d); }
Fan_Type P3( ) { return(e-f); }
void main( )
{
}
（4）设有几个进程共享一互斥段，对于如下两种情况： （1）每次只允许一个进程进入临界区；
（2）最多允许m个进程(m 所采用的信号量是否相同？信号量值的变化范围如何？ (1)信号量值的变化范围为s.value<=1; (2)信号量值的变化范围为s.value<=m; （5）下面是两个并发执行的进程，它们能正确执行吗？若不能正确执行，请举例说明，并改正之（x是公共变量）。 void P1( ) { int y, z; x=1; y=0; if(x>=1) y=y+1; z=y; } void P2( ) { int t, u; x=0; t=0; if(x<1) t=t+z; u=t; } void main( ) { parbegin(P1( ), P2( )); } 不能正确执行。如进程P1执行过程中不被中断，进程运行结束后x, y, z的值均为1；但若进程P1执行到y=0时被中断，进程P2执行完毕后x的值为0，则P1恢复中断后获得的结果为x, y, z的值均为0，从而发生与时间有关的错误。 struct semaphore s; s.value=1; void P1( ) { int y, z; wait(s); x=1; y=0; if(x>=1) y=y+1; z=y; signal(s); } void P2( ) Fan_Type a, b, c; parbegin(a=P1, b=P2, c=P3); xa/b**c; { int t, u; wait(s); x=0; t=0; if(x<1) t=t+z; u=t; signal(s); } void main( ) { parbegin(P1( ), P2( )); } （6）共享存储区通信是如何实现的？ （7）假设某系统未直接提供信号量机制，但提供了进程通信工具。如果某程序希望使用关于信号量的wait、signal操作，那么该程序应如何利用通信工具模拟信号量机制？要求说明如何用send/receive操作及消息表示wait/signal操作及信号量。 5．应用题 （1）有三个并发进程R、W1和W2，共享两个各可存放一个数的缓冲区B1、B2。进程R每次从输入设备读入一个数，若读入的是奇数，则将它存入B1中，若读入的是偶数，将它存入B2中；当B1中有数，由进程W1将其打印输出；当B2中有数，进程W2将其打印输出。试编写保证三者正确工作的程序。 struct semaphone B1_Empty, B1_Full, B2_Empty, B2_Full; B1_Empty.value=1; B1_Full.value=0; B2_Empty.value=1; B2_Full.value=0; void R( ) { int a; While(1) { read a number a; if(a%2==1) { wait(B1_Empty); put a in B1; signal(B1_Full); } else { wait(B2_Empty); put a in B2; signal(B2_Full); } } } void W1( ) { while(1) { wait(B1_Full); print a number from B1; signal(B1_Empty); } } void W2( ) { while(1) { wait(B2_Full); print a number from B2; signal(B2_Empty); } } void main( ) { parbegin(R( ), W1( ), W2( )); } （2）8个协作的任务A、B、C、D、E、F、G、H分别完成各自的工作。它们满足下列条件：任务A必须领先于任务B、C和E；任务E和D必须领先于任务F；任务B和C必须领先与任务D；而任务F必须领先于任务G和H。试写出并发程序，使得在任何情况下它们均能正确工作。 （3）多个进程共享一个文件，其中只读文件的称为读者，只写文件的称为写者。读者可以同时读，但写者只能独立写。问： 1）说明进程间的制约关系，应设置哪些信号量？ 2）用wait、signal操作写出其同步程序。 3）修改上述算法，使得它对写者优先，即一旦有写者到达，后续的读者必须等待。而无论是否有读者在读文件。 见教材“读者-写者问题” （4）桌上有一空盘，可放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子；儿子专等吃盘中的桔子；女儿专等吃盘中的苹果。规定一次只能放一只水果，试写出爸爸、儿子、女儿正确同步的程序。 struct semaphone plate, apple, orange; plate.value=1; apple.value=0; orange.value=0; void father( ) { while(1) { prepare an apple or orange; wait(plate); put the apple or orange in plate; if(Apple) signal(apple); //如果放的是苹果 else signal(orange); //如果放的是桔子 } } void son( ) { while(1) { wait(orange); get an orange from the plate; signal(plate); } } void daughter( ) { while(1) { wait(apple); get an apple from the plate; signal(plate); } } Void main( ) （5）三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用procuce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述（2009年全国硕士研究生入学考试题）。 struct semaphone full_odd, full_even, mutex, empty; full_odd.value=0; full_even.value=0; mutex.value=1; empty.value=N; void P1( ) { int X; while(1) { X=produce( ); wait(empty); wait(mutex); put( ); if(X%2==0) signal(full_even); else signal(full_odd); signal(mutex); } } void P2( ) { wait(full_odd); wait(mutex); getodd( ); countodd( )=countodd( )+1; signal(empty); signal(mutex); } void P3( ) { wait(full_even); wait(mutex); geteven( ); counteven( )=counteven( )+1; signal(empty); signal(mutex); } void main( ) { parbegin(P1( ), P2( ), P3( )); } （6）放小球问题：一个箱子里只有白色和黑色两种小球，且数量足够多。现在需要从中取出一些小球放入一个袋子中。约定：1）一次只能放入一个小球；2）白球的数量至多只能比黑球少N个，至多只能比黑球多M个（M，N为正整数）。请用信号量机制实现进程的同步与互斥。 struct semaphone mutex1, mutex2; int black=0, white=0; mutex1.value=1; mutex2.value=1; void put( ) { while(1) { wait(mutex1); get a black ball or white ball from the box; signal(mutex1); wait(mutex2); if(Black) //如果取到的是黑球 if(black-white void main( ) { parbegin(put( )); } 习题5 1．单项选择题 （1）当作业进入完成状态时，操作系统 B 。 A、 将删除该作业并收回其所占资源，同时输出结果 B、 将该作业的控制块从当前作业队列中删除，收回其所占资源，并输出结果 C、 将收回该作业所占资源并输出结果 D、 将输出结果并删除内存中的作业 （2）批处理作业是被成批存入 A ，以等待作业调度选择。 A、输入井 B、输出井 C、映象区 D、内存 （3）一种即有利于短作业又兼顾长作业的作业调度算法是 A 。 A、最高响应比优先 B、先来先服务 C、短作业优先 D、均衡调度 （4）在批处理系统中，周转时间是 B 。 A、作业运行时间 B、作业等待时间和运行时间之和 C、作业的相对等待时间 D、作业被调度进入内存到运行完毕的时间 （5）在操作系统中，作业处于 B 状态时，已处于进程管理之下。 A、提交 B、后备 C、运行 D、完成 （6）在作业调度中，若采用优先级调度算法，为了尽可能使处理器和外部设备并行工作，有如下三个作业：J1以计算为主，J2计算和输入输出兼顾，J3以输入输出为主，则它们的优先级从高到低的排列顺序是 B 。 A、J1，J2，J3 B、J2，J3，J1 C、J2，J3，J1 D、J3，J1，J2 （7）一个作业被成功调度后，系统为其创建相应的进程，该进程的初始状态是 。 A、执行态 B、阻塞态 C、就绪态 D、等待访问设备态 2．填空题 （1）作业调度是从处于 后备 状态的队列中选取适当的作业投入运行。从作业提交给系统到作业完成的时间间隔叫做 周转时间 。 等待时间 是指作业从进入后备队列到被调到程序中的时间间隔。假定把下列四个作业同时提交系统并进入 后备 队列，当使用短作业优先调度算法时，单道环境下，四个作业的平均等待时间是 ，平均周转时间是 ；当使用高优先数优先的调度算法时，作业的平均等待时间是 ，平均周转时间是 。 作业 1 2 3 4 所需运行时间（小时） 2 5 8 3 优先数 4 9 1 7 （2）在一个具有分时兼批处理的系统中，总是优先调度 分时作业 。 3．简答题 （1）什么是分层次调度？在分时系统中有作业调度的概念吗？如果没有，为什么？ （2）作业调度和进程调度的主要功能分别是什么？ （3）作业调度的性能评价标准有哪些？这些性能评价标准在任何情况下都能反映调度 策略的优劣吗？ （4）为什么说多级反馈队列调度算法能较好地满足各类用户的需要？ （5）假设就绪队列中有10个进程，系统将时间片设为200ms，CPU进行进程切换要花费10ms，试问系统开销所占的比率约为多少？ （6）在批处理系统、分时系统和实时系统中一般常采用哪种调度算法？ （7）若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为a、b、c，且满足关系a （8）简述UNIX System V中进程调度算法的特点。 3．应用题 （1）考虑5个进程P1、P2、P3、P4、P5，它们的创建时间、运行时间及优先数如下表所示。规定进程的优先数越小，优先级越高。试描述在采用下述几种调度算法时各个进程运行过程，并计算采用每种算法时的进程平均周转时间。假设忽略进程的调度时间。 1）先来先服务调度算法； 2）时间片轮转调度算法（时间片为1ms）； 3）非剥夺式优先级调度算法； 4）剥夺式优先级调度算法。 进程 P1 P2 P3 P4 P5 创建时间 0 2 4 6 8 运行时间（ms） 3 6 4 5 2 优先数 3 5 1 2 4 1）先来先服务调度算法 作业号 P1 P2 P3 P4 P5 进入时间 0 2 4 6 8 运行时间（ms） 3 6 4 5 2 开始执行时间 0 3 9 13 18 完成时间 3 9 13 18 20 周转时间 3 7 9 12 12 平均周转时间T＝（3+7+9+12+12）/ 5=8.6ms 平均带权周转时间W=(3/3+7/6+9/4+12/5+12/2) / 5=2.56 2)时间片轮转调度算法 当时间片q=1时，列出下表，找出运行序列： 时刻 0～1 1～2 2～3 3～4 4～5 5～6 6～7 7～8 运行进程 P1 P1 P2 P1 P2 P3 P2 P4 排队进程 P1 P2 P3 P2 P4 P3 P3 P2 时刻 10～11 11～12 12～13 13～14 14～15 15～16 16～17 17～18 运行进程 P5 P4 P3 P2 P5 P4 P3 P2 排队进程 P4 P3 P2 P3 P2 P5 P2 P5 P4 P5 P4 P3 P4 P3 P2 P3 P2 P2 P4 P4 8～9 9～10 作业号 P1 P2 P3 P4 P5 P3 P2 进入时间 0 2 4 6 8 P2 P5 P4 P5 P4 P3 运行时间 3 6 4 5 2 18～19 19～20 完成时间 4 18 17 20 15 P4 P4 周转时间 4 16 13 14 7 平均周转时间T＝（4+16+13+14+7）/ 5=10.8ms 平均带权周转时间W=(4/3+16/6+13/4+14/5+7/2) / 5=2.15 3) 非剥夺式优先级调度算法 作业号 P1 P2 P3 P4 P5 进入时间 0 2 4 6 8 运行时间 3 6 4 5 2 优先数 3 5 1 2 4 完成时间 3 9 13 18 20 周转时间 3 7 9 12 12 平均周转时间T＝（3+7+9+12+12）/ 5=8.6ms 平均带权周转时间W=(3/3+7/6+9/4+12/5+12/2) / 5=2.56 4)剥夺式优先级调度算法 0 3 4 8 13 15 20 P1 P2 P3 P4 P5 作业号 P1 P2 P3 P4 P5 进入时间 0 2 4 6 8 运行时间 3 6 4 5 2 优先数 3 5 1 2 4 完成时间 3 20 8 13 15 周转时间 3 18 4 7 7 平均周转时间T＝（3+18+4+7+7）/ 5=7.8ms 平均带权周转时间W=(3/3+18/6+4/4+7/5+7/2) / 5=1.98 9．有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的剥夺式调度算法。下表所示为作业序列，作业优先数即为进程优先数，优先数越小优先级越高。 进程 A B C D 到达时间 10：00 10：20 10：30 10：50 估计运行时间 40分 30分 50分 20分 优先数 5 3 4 6 （1）列出所有作业进入内存时间及结束时间。 （2）计算平均周转时间。 作业名 到达时间 估计运行时间 优先数 进入内存时间 执行结束时间 周转时间 A 10.00 40分 ５ 10.00 11.10 70 B 10:20 30分 3 10.20 10.50 30 C 10:30 50分 4 11.10 12.00 90 D 10:50 20分 6 12,00 12.20 90 T=70分 1．单项选择题 （1）以下关于死锁的必要条件的叙述中错误的是 。 A、只要具备了死锁的必要条件，就一定发生死锁现象 B、解决死锁问题可以从死锁的必要条件出发 C、一旦出现死锁，处于死锁状态的进程一定同时具备死锁的必要条件 D、死锁的四个必要条件之间不是完全独立的，但也不是等价的 （2）以下关于死锁检测的叙述中错误的是 。 A、只要检测出死锁（尚未解除），则再申请该类资源的进程一定会卷入死锁 B、只要检测出死锁（尚未解除），则使用该类资源的所有进程一定卷入了死锁 C、死锁检测方法对系统资源的分配不加限制，只要有剩余资源就可以分配 D、死锁检测中系统需要反复检测各进程资源申请和分配情况 （3）以下关于死锁问题的说法中正确的是 。 A、死锁问题是无法解决的，但可以避免 B、死锁的预防是通过破坏进程进入不安全状态来实现的 C、通过避免死锁四个必要条件中的任何一个就可以实现死锁避免 D、死锁的检测和解除是配合使用的，当系统检测到出现死锁时，就通过死锁解除 方法解除死锁 （4）以下关于系统的安全状态的描述中正确的是 。 A、系统处于不安全状态一定会发生死锁 B、系统处于不安全状态可能会发生死锁 C、系统处于安全状态时也可能会发生死锁 D、不安全状态是死锁状态的一个特例 （5）资源的静态分配算法在解决死锁问题中用于 。 A、死锁预防 B、死锁避免 C、死锁检测 D、死锁解除 （6）有3个进程共享7个同类资源，为使系统不会发生死锁，每个进程最多可以申请 个资源。 A、1 B、2 C、3 D、4 （1）A （2）B （3）D （4）B （5）A 2．填空题 （1）解决死锁的方法可以有多种，其中死锁的预防是通过 破坏死锁的必要条件之一 来实现的，死锁的避免是通过 防止系统进入不安全状态 来实现的。 （2）死锁的避免，就是通过保持系统处于 安全状态 来避免死锁，所以每当有进程提出资源分配请求时，系统应分析 各进程已占资源数、尚需资源数和系统中可以分配的剩余资源数，然后决定是否为当前的申请者分配资源。 （3）死锁检测要解决两个问题，一是 判断系统 是否出现了死锁，二是当有死锁发生时怎样去 解除死锁 。 （4）为了避免死锁，可以采用 银行家 算法进行资源安全分配。 （5）系统出现死锁，不仅与 设备 分配策略有关，而且与 进程 执行的相对速度有关。 （6）当检测到系统发生死锁时，可采用 解除所有死锁进程 、 逐个撤销死锁进程 和 抢占死锁进程的资源供其它进程使用 来解除死锁。 3．简答题 （1）何谓死锁？给出只涉及一个进程的死锁例子。 （2）死锁预防和死锁避免。 （3）为什么说采用有序资源分配法不会产生死锁？ （4）安全状态和不安全状态。 4．应用题 （1）假设系统由相同类型的m个资源组成，有n个进程，每个进程至少请求一个资源。证明：当n个进程最多需要的资源之和小于m+n时，该系统无死锁。 【分析】设ai为第i个进程对资源的最大需求数，如果每个进程均获得了最大需求数减1个资源，显然，此时系统只要还有1个资源，就不会发生死锁。 【证明】根据以上分析，有： (a1-1)+(a2-1)+?+(ai-1)?+(an-1)≤m-1 即 a1+a2+?+ai?+an≤m+n-1 亦即 a1+a2+?+ai?+an （2）考虑下列资源分配策略：对资源的申请和释放可以在任何时候进行。如果一个进程提出资源请求时得不到满足，若此时无由于等待资源而被阻塞的进程，则自己就被阻塞；若此时已有等待资源而被阻塞的进程，则检查所有由于等待资源而被阻塞的进程，如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。 1）这种分配策略会导致死锁吗？如果会，请举一个例子；如果不会，请说明产生死锁的哪一个必要条件不成立？ 2）这种分配方式会导致某些进程的无限等待吗？为什么？ 1）不会，因为资源集中在了最后一个申请该资源而陷入等待的进程，条件成熟时，最 后一个进程能够完成工作，释放资源给其它进程。它破坏了“不可剥夺条件”。 2）由于后来进程总要剥夺先到的而处于阻塞状态进程的资源，因此，先到的进程可能由于长期得不到资源而处于无限期等待状态。 （3）某系统有同类资源m个，被n个进程共享，请分别讨论当m>n和m≤n时每个进程最多可以请求多少个这类资源，才能使系统一定不会发生死锁？ 当m>n时，每个进程最多可以请示该类资源数为 INT(m/n)+1 当m≤n时，每个进程最多可以请示该类资源数为 1 （4）某系统有R1、R2、和R3共3类资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见表6-6，此时系统的可用资源向量为(2,1,2)。 P1 P2 P3 P4 最大资源需求量 R1 R2 R3 3 2 2 6 1 3 3 1 4 4 2 2 已分配资源数量 R1 R2 R3 1 0 0 4 1 1 2 1 1 0 0 2 问题： 1）将系统中各类资源总数和此刻各进程对资源的需求数目用向量或矩阵表示出来； 2）如果此时P1和P2均发出资源请求向量Request(1,0,1)，为了保证系统的安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因。 3）如果（2）中两个请求立即得到满足后，系统此刻是否处于死锁状态？ 1）系统中各类资源总数向量为（9，3，6） ?2?2 需求矩阵为??1??4 22?02?? 03??20?2）当P1和P2均发出资源请求向量Request(1,0,1)时，应把资源分配给P2，因为此时如果把资源分配给P1，则需求矩阵为： ?1?2??1??421?02??03??20? 而系统可用资源向量为（1，1，1），显然，系统资源已不足以帮助任何一个进程完成任务，系统将进入不安全状态。而把资源分配给P2后，需求矩阵为： ?2?1??1??422?01??03??20?而系统可用资源向量为（1，1，1），显然，存在安全序列< P2，P1，P4，P3>，系统仍然处于安全状态。 3）如果（2）中两个请求立即得到满足后，系统此刻处于不安全状态，但并不是死锁状态。 习题7 1．单项选择题 （1）要把以“0”为参考地址的装配模块装入到以550为起始地址的存储空间，若采用静态重定位，则原程序中的指令“LOAD 1 455”应改为 ，程序才能正确运行。 A、LOAD 1 1005 B、LOAD 1 550 C、LOAD 1 95 D、LOAD 1 455 （2）在动态重定位中，重定位寄存器中装入的是 。 A、目标模块装入的实际起始地址 B、目标模块的相对基地址 C、实际起始地址加上相对地址 D、实际起始地址减去目标模块的相对基地址 （3）、在固定分区存储管理中，装入内存的所有作业的相对地址空间总和 内存中除操作系统之外的所有空间。 A、可以大于 B、一定小于 C、一般小于 D、以上说法都不对 （4）在可变分区分配方案中，某一作业完成后，系统将回收其主存空间，并与相邻空闲区合并，引起空闲区数减一的是 。 A、无上邻接空闲区，也无下邻接空闲区 B、无上邻接空闲区，但有下邻接空闲区 C、有上邻接空闲区，但无下邻接空闲区 D、有上邻接空闲区，也有下邻接空闲区 （5）可变分区存储管理中的移动技术可以 。 A、缩短访问周期 B、增加主存容量 C、集中空闲区 D、加速地址转换 （6）采用分页式存储管理使处理器执行指令的速度 。 A、有时提高有时降低 B、降低 C、不受影响 D、提高 （7）在分段式存储管理中， 。 A、以段为单位分配内存，每段是一个连续存储区 B、段与段之间必定连续 C、段与段之间必定不连续 D、每段是等长的 （8）段页式存储管理中，逻辑地址的格式一般为 。 A、 段号 B、 页号 C、 段号 D、 页号 段内地址 段号 页号 页内地址 段内地址 页内地址 （1）A （2）D （3）C （4）D （5）C （6）B （7）A 2．填空题 （1）为了有效地管理计算机的内存资源，存储管理应具备 存储分配 、地址映射 、 存储保护 和 内存扩充 四大功能。 （2）可以把存储管理方式分为 连续分配方式 、 离散分配方式 和 虚拟存储管理 等三种。 （3）为了适应最佳适应算法，空闲分区表中的空闲分区要 按空闲区大小的升序 进行排序；而为了适应最坏适应算法，空闲分区表中的空闲分区要按空闲区大小的降序 进行排序。 （4）页式存储管理中，页式虚拟地址与内存物理地址的映射是由 页表 和 硬件地址转换机构 来完成的。 （5）段页式存储管理中，虚拟空间的最小单位是 页 而不是 段 。内存可以等分成若干个 块 ，且每个段所拥有的程序和数据在 内存 中可以分开 存放 。 3．名词解释： （1）逻辑地址空间；（2）存储空间；（3）地址重定位；（4）静态重定位；（5）动态重定位。 4．简答题 （1）．存储管理研究的主要课题是什么？见教材 （2）请总结各种存储管理方式下的重定位的地址转换方法。见教材 （3）可变分区存储管理中的内存分配有哪些算法？试比较其优缺点。见教材 （4）可变分区的分区回收有几种情况？试说明之。见教材 （5）简述分页存储管理的基本原理。见教材 （6）请画出分页情况下的地址变换过程，并说明页面尺寸为什么一定要是2的幂？见教材 （7）试比较分页与分段存储管理的优缺点。见教材 （8）某作业大小为8A5H字节，从内存53FH处开始装载，当作业的相应进程在CPU上运行时： 1）若采用上、下界寄存器保护，寄存器的值各为多少？如何进行保护？ 2）若采用基址、限长寄存器保护，寄存器的值各为多少：如何进行保护？ 1）上界寄存器：53FH；下界寄存器：DE4H。小于上界寄存器，大于下界寄存器的访问请求为非法。 2）基址寄存器：53FH；限长寄存器：8A5H。小于基址寄存器，大于基址寄存器+限长寄存器的访问请求为非法。 （9）试说明在分页存储管理系统中，地址变换过程可能会因为哪些原因而产生中断？ 1）越界中断 2）缺页中断 （10）在分页存储管理系统中，某进程的页表如下（表中数据为十进制）：若页面大小为2KB，试将虚地址0A3BH和6E1CH变换为物理地址。 页号 0 1 2 3 4 5 物理块号 10 7 12 6 15 11 6 7 8 2 （1）将虚地址0A3BH转换成二进制，并从第11位（页大小为2KB=211B），高位部分为页号，低位部分为页内地址： 0 得页号为1，查页表知对应的物理块号为7，则物理地址为： 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 即虚地址0A3BH变换为物理地址后为3A3BH。 （2）将虚地址6E1CH转换成二进制，并从第11位（页大小为2KB=211B），高位部分为页号，低位部分为页内地址： 0 得页号为13，查页表，该进程没有第13页，产生越界中断。 （11）某分段存储管理中采用如下段表： 段 号 0 1 2 3 4 段的长度（字节） 380 20 105 660 50 内存起始地址 95 525 3300 860 1800 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 试回答： 1）将虚地址（0，260），（2，200），（4，42）变换为物理地址。 2）存取内存中的一条指令或数据至少要访问几次内存？ 1）①虚地址（0，260），查段表知第0段的长度为380，地址合法，物理地址为95+260=355。 ②虚地址（2，200），查段表知第2段的长度为105，段内地址200>段长105，地址非法，产生越界中断。 ③虚地址（4，42），查段表知第4段长度为50，地址合法，物理地址为1800+42=1842。 2）存取内存中的一条指令或数据至少要2次访问内存。 （12）比较下述几种存储映象技术的优缺点： 1）直接映象； 2）相关映象； 3）直接和相关相结合的映象。 见教材 习题8 1．单项选择题 （1）虚拟存储器是 。 A、可提高计算机运算速度的设备 B、容量扩大了的主存 C、实际上不存在的存储器 D、可以容纳总和容量超过主存容量的多个作业同时运行的一个地址空间 （2）在快表（联想存储器）中的页，其信息 。 A、一定在内存中 B、一定在外存中 C、在外存和内存中 D、以上说法都不对 （3）在请求分页系统中，LRU算法是指 。 A、近期被访问次数最少的页先淘汰 B、以后再也不用的页先淘汰 C、最早进入内存的页先淘汰 D、近期最长时间以来没被访问的页先淘汰 （4）在请求分页式存储管理中，采用FIFO淘汰算法，若分配的物理块数增加，则缺页中断次数 。 A、一定增加 B、一定减少 C、可能增加也可能减少 D、不变 （5）在请求分页式存储管理机制的页表中有若干个表示页表换进、换出的信息位，其中用在转换出内存时是否写盘的依据的是 。 A、状态位P B、访问字段A C、修改位M D、外存地址 （6）能够实现虚拟存储管理的存储管理方式是 。 A、可变分区存储管理 B、固定分区存储管理 C、分页式存储管理 D、单一连续分区存储管理 （7）在请求分页式存储管理方式中，能使用户程序大大超过内存的实际容量。虚存的实现实际上是利用 为用户构建一个虚拟空间。 A、内存 B、外存 C、联想存储器 D、页表 （1）D （2）A （3）D （4）C （5）C （6）C （7）B 2．填空题 （1）实现虚拟存储后，从系统角度看， 扩充了内存 ，从用户角度看，用户可以在超出 用户作业空间 的存储空间中编写程序，大大方便了用户。 （2）在请求分页式存储管理中，当查找的页不在 内存 ，要产生 缺页中断 。 （3）在提供虚拟存储管理的系统中，用户的逻辑地址空间主要受 系统的寻址能力 、 外存容量 的限制。 （4）页面置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致进程发生 抖动 。 2．名词解释： （1）虚拟存储器；（2）时间局限性；（3）空间局限性；（4）抖动；（5）工作集。 3．简答题 （1）什么是虚拟存储器，为什么要引入虚拟存储器的概念？ （2）虚拟存储器的最大容量由什么决定？ （3）什么是局部性原理？ （4）在请求分页系统中，页表应包括哪些数据项？每项的作用是什么？ （5）在请求分页系统中，常采用哪几种页面置换算法？ （6）在请求分段系统中，段表应包括哪些数据项？每项的作用是什么？ （7）采用可变分区方式管理内存时，能实现虚拟存储器吗？ （8）在页面置换算法中，LRU和NRU哪个更常用？为什么？ 4．应用题 某进程的页面访问序列为：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2， 3，6，假定分给该进程4个物理块，计算在采用下列置换算法时的缺页中断次数和缺页中断率。 （1）LRU； （2）FIFO； （3）OPT。 （1）LRU置换算法 页面访问序列 1 1 2 2 1 3 3 2 1 4 2 1 5 4 2 1 5 3 4 2 1 2 3 4 2 1 1 3 4 - - 6 2 1 2 3 6 2 1 2 3 5 6 2 1 2 1 5 6 6 1 2 1 5 5 6 - - - 7 7 3 2 1 6 3 2 1 2 3 6 6 3 2 1 2 3 6 7 6 3 2 1 2 3 3 7 6 3 3 1 2 2 2 7 6 6 6 1 - - + - - - + + + + + + + + + 缺页中断次数=10 缺页中断率=10/20=50% （2）FIFO置换算法 页面访问序列 1 1 2 2 1 3 3 2 1 4 2 1 5 4 4 4 5 3 3 3 4 2 2 2 3 1 1 1 2 - - 6 6 5 4 3 2 2 6 5 4 1 2 3 1 1 3 2 2 1 6 6 2 5 5 6 - 7 7 3 1 2 6 3 2 6 6 2 7 7 6 3 3 7 1 1 3 - 1 2 3 6 1 1 3 3 2 2 1 1 6 6 2 2 7 7 6 6 - + - + + + + + + + + + + + + + 缺页中断次数=14 缺页中断率=14/20=70% （3）OPT置换算法 页面访问序列 1 1 2 2 1 3 2 1 3 4 2 1 5 2 1 2 2 1 2 1 1 3 3 3 3 4 4 4 5 - - 6 2 1 3 6 2 1 2 3 6 - 1 2 3 2 3 6 3 6 3 6 2 2 1 1 1 - - - 7 6 3 2 7 + 6 3 2 3 2 2 2 3 3 6 6 6 7 7 7 - - - 1 2 3 6 2 3 6 6 3 6 3 3 6 2 2 2 1 1 1 1 + - - - + + + + + + 缺页中断次数=8 缺页中断率=8/20=40% 习题9 1．选择题 （1）以下关于I/O设备的中断控制方式说法正确的是 。 A、CPU对I/O设备直接进行控制，采取忙等待方式 B、仅在传送一个或多个数据块的开始和结束时，才需CPU干预 C、CPU委托专用的I/O处理机来实现I/O设备与内存之间的信息交换 D、在传输过程中，CPU与I/O设备处于并行工作状态，只是当传输结束时，才由控制器向CPU发送中断信号 （2）通道是一种 。 A、保存I/O信息的部件 B、传输信息的电子线路 C、通用处理机 D、专用处理机 （3）CPU对通道的请求形式是 。 A、自陷 B、通道命令 C、中断 D、转移命令 （4）缓冲有硬件缓冲和软件缓冲之分，硬件缓冲使用专用的寄存器作为缓冲器。软件缓冲使用 作为缓冲区。 A、在内存中划出的单元 B、专用的寄存器 C、在外存中划出的单元 D、高速缓冲区 （5）以下不是I/O控制中DMA控制方式的特点的是 。 A、进行成批的数据传送交换 B、用专门的I/O处理机 C、传送开始和结束时需要CPU干预 D、采用盗窃总线控制权方式 （6）使用户编制的程序与实际使用的物理设备无关是由 功能实现的。 A、设备分配 B、设备驱动 C、虚拟设备 D、设备独立性 （7）SPOOLing技术利用了 。 A、外设概念 B、虚拟设备概念 C、磁带概念 D、存储概念 （8）磁盘输入输出操作中，需要做的工作可以不包括 。 A、移动移动臂使磁头移动到指定的柱面 B、确定磁盘的容量 C、旋转磁盘使指定的扇区处于磁头位置下 D、让指定的磁头读写信息，完成信息传送操作 （9）执行一次磁盘输入输出操作所花费的时间包括 。 A、寻道时间、延迟时间、传送时间和等待时间 B、寻道时间、等待时间、传送时间 C、等待时间、寻道时间、延迟时间和读写时间 D、寻道时间、延迟时间、传送时间 （10）在磁盘调度算法中， 算法可能导致某些访问请求长时间得不到服务，从而造成饥饿现象。 A、FCFS B、SSTF C、SCAN D、CSCAN （11）如果有多个中断同时发生，系统将根据中断优先级响应优先级最高的中断请求。若要调整中断事件的响应次序，可以利用 。 A、中断向量 B、中断嵌套 C、中断响应 D、中断屏蔽 （1）D （2）D （3）B （4）A （5）B （6）D （7）B （8）B （9）D （10）B （11）D 2．填空题 （1）I/O设备按传输速率分类，可分为 低速设备 、 中速设备 和 高速设备 等三种；按信息交换的单位分类，可分为 字符设备 和 块设备 。按资源分配的角度分类，可分为 独占设备 、 共享设备 和 虚拟设备 。 （2）缓冲区管理是为了缓和CPU与I/O设备间速度不匹配的矛盾 、减少中断CPU的次数，放宽对中断响应的要求、提高CPU、通道和I/O设备之间的并行性 的矛盾。 （3）按照信息交换的方式，一个系统中可设立三种类型的通道，即 字节多路通道 、数组选择通道 和 数组多路通道 。 （4） 设备独立性 也称设备无关性，其基本思想是：用户程序不直接使用 物理设备名 ，而只能使用 逻辑设备名 ；系统在实际执行时，将 逻辑设备名 转换为 物理设备名 。 （5）、打印机虽然是独享设备，但是通过 SPOOLing技术 ，可以将它改造为一台可供多个用户共享的设备。 3．简答题 （1）有几种I/O控制方式？各有什么特点？ （2）什么是通道？通道、CPU、内存和外设之间的工作关系如何？ （3）什么是缓冲？为什么要引入缓冲？ （4）在某系统中，从磁盘将一块数据输入到缓冲区需要花费的时间为T，CPU对一块数据进行处理的时间为C，将缓冲区的数据传送到用户区所花的时间为M，那么在单缓冲和双缓冲情况下，系统处理大量数据时，一块数据的处理时间为多少？ （5）简述缓冲池的组成及工作原理。 （6）为什么要引入SPOOLing系统？简述SPOOLing系统的组成及工作原理。 （7）什么是中断？什么是中断处理？什么是中断响应？ （8）用于设备分配的数据结构有哪些？它们之间的关系是什么？ （9）什么叫“设备独立性”？如何实现“设备独立性”？ （10）什么是设备驱动程序？为什么要有设备驱动程序？用户进程怎样使用驱动程序？ （11）磁盘访问时间有哪几部分组成？每部分时间应如何估算？其中哪一个时间是磁盘调度的主要目标？ （12）目前常用的磁盘调度算法有哪几种？每种算法优先考虑的问题是什么？ 4．应用题 某活动头磁盘有200个磁道，编号为0~199。磁头当前位置在143道服务。对于请求序列86、147、91、177、94、150、102、175、130，求在下列调度策略下的寻道顺序及寻道长度。 （1）FCFS。 （2）SSTF。 （3）SCAN（磁头移动方向先从小到大）。 （4）CSCAN（磁头移动方向先从小到大）。 （1）FCFS 被访问的下一磁道号 移动距离 （当前磁道为143） (磁道数) 86 57 147 61 91 56 177 86 94 83 150 56 102 48 175 73 130 45 平均寻道长度 62.78 FCFS调度算法 （2）SSTF （3）SCAN 被访问的下一磁道号 移动距离 （当前磁道为143） (磁道数) 147 4 150 3 130 20 102 28 94 8 91 3 86 5 175 89 177 2 平均寻道长度 18 SSTF调度算法 被访问的下一磁道号 移动距离 （当前磁道为143） (磁道数) 147 4 150 3 175 25 177 2 130 47 102 28 94 8 91 3 86 5 平均寻道长度 13.89 FCFS调度算法 （4）CSCAN 被访问的下一磁道号 移动距离 （当前磁道为143） (磁道数) 147 4 150 3 175 25 177 2 86 91 91 5 94 3 102 8 130 28 平均寻道长度 18.78 FCFS调度算法 习题10 1．单项选择题 （1）文件可以按多种方法分类，下列不属于按用途分类的文件类型是___________。 A、临时文件 B、系统文件 C、库文件 D、用户文件 （2）文件的逻辑记录的大小是___________。 A、不相同的 B、相同的 C、恒定的 D、可相同也可不相同 （3）文件的逻辑结构的组织形式是由___________确定的。 A、编译系统 B、主存容量 C、操作系统 D、应用程序 （4）同一个文件存贮在不同的存储介质上，其组织形式___________。 A、必定不同 B、可以不同 C、必定相同 D、应该不同 （5）图像文件的逻辑结构形式是 。 A、流式文件 B、记录式文件 C、索引文件 D、链接文件 （6）文件的物理结构的组织形式是与___________有关的。 A、文件长度 B、记录个数 C、外存分配方式 D、目录结构 （7）在MS—DOS中，文件在磁盘上的存储结构是___________。 A、顺序结构 B、链接结构 C、索引结构 D、流式结构 （8）以下不是文件控制块FCB中所包含的信息的是___________。 A、文件的符号名 B、文件的逻辑结构 C、文件的存取权限 D、文件的建立日期 （9）文件系统采用多级目录结构的目的是___________。 A、解决文件的命名冲突 B、节省存储空间 C、易于实现文件的共享 D、A和C （10）文件系统实现按名存取主要是靠___________来实现的。 A、查找作业表 B、查找文件目录 C、地址转换机构 D、查找位示图 （11）文件系统中用___________管理文件。 A、指针 B、目录 C、页表 D、堆栈结构 （12）下面___________不是文件存储空间管理方法。 A、位示图法 B、成组链接法 C、空闲块链接法 D、顺序组织法 （13）下面___________不是实现文件存取控制的方法。 A、安全登录 B、用户权限表 C、存取控制矩阵 D、存取控制表 （14）NTFS是___________操作系统使用的文件系统。 A、Windows NT/2000 B、Windows 98 C、UNIX D、Linux （15）___________操作系统不能访问FAT文件系统。 A、Windows NT/2000 B、Windows 98 C、Macintosh D、Linux （1）A （2）D （3）D （4）B （5）A （6）C （7）B （8）B （9） D （10）B （11）B （12）D （13）A （14）A （15）C 2．填空题 （1）由用户确定的文件结构称为文件的逻辑结构，逻辑文件从结构上分为_流式文件_和_记录式文件__两种。 （2）从用户观点出发观察到的文件组织结构称为文件的_逻辑结构_，而文件在外存上的存储组织形式称为文件的_物理结构_。 （3）文件的外存分配方式有连续分配、_链接分配__和_索引分配__。 （4）_文件控制块FCB_的有序集合称为文件目录。 （5）如果每个盘块的大小为4KB，每个索引表项占4B，则一个盘块可有_1024_个索引表项，一级索引可以管理的最大文件为_4MB_，二级索引可以管理的最大文件为__4GB_。 （6）从用户的角度看，文件系统的功能是要实现_按名存取_。为了达到这一目的，一般要建立__文件目录_。 （7）为了实现按名存取，系统为每个文件设置用于描述和控制文件的数据结构，它至少要包括__文件名_和存放文件的__物理位置_，这个数据结构称为_文件控制块FCB_。 （8）用_位示图__指示磁盘空间使用情况时，其中的每一位与一个_磁盘块_对应。 （9）文件控制块的有序集合称为_文件目录_，一个文件控制块FCB就是一个_目录项_。 （10）目录查询技术有_线性检索法_和_Hash法__两种。 3．问答题 （1）名词解释：数据项、记录、文件和文件系统。 （2）请按各种不同方法对文件进行分类。 （3）文件系统应具备哪些功能？ （4）文件的逻辑组织和物理组织各指什么？ （5）文件的组织和存取中Hash文件有何优点？有何局限性? （6）文件存储空间的管理有哪几种常用的方法？试比较各种方法的优缺点。 （7）文件目录的作用是什么？一个目录项中应包括哪些信息？ （8）目前广泛采用的目录结构形式是哪种?它有什么优点? （9）设某系统的磁盘空间共有5000块，若用位示图管理磁盘空间，位示图的每个字有32位，并且物理块号、字号、位号均从1开始。试问： 1）位示图需要多少个字构成？ 2）计算位示图第9个字第22位对应的物理块号。 3）求物理块号106对应的字和位。 （10）基于索引结点的共享方法有何优缺点? （11）基于符号链的文件共享方法有何优缺点? （12）什么是管道文件？ （13）为什么要对文件进行保护？有哪些常用的方法？ （14）系统如何利用存取控制表和存取权限表来实现对文件的保护? （15）文件的转储有几种方法？文件恢复的过程是什么？