操作系统复习题2016

操作系统复习题

复习题一

一、选择题

1．下列选择中，哪个不是操作系统关心的主要问题。（ D ）

A．管理计算机裸机； B．设计提供用户与计算机硬件系统间的界面； C．管理计算机系统资源； D．高级程序设计语言的编译器。 2．从用户角度看，操作系统是（ C ）。

A．计算机资源的管理者； B．计算机工作流程的组织者；

C．用户与计算机之间的接口； D．由按层次结构组成的软件模块的集合。 3．引入多道程序技术的前提条件之一是系统具有（ D ）

A．多个cpu； B．多个终端； C．中断功能； D．分时功能 4．分时系统的一个重要性能是响应时间，能改善响应时间的因素是（ B ）。

A．进程数目减少； B．CPU速度加快； C．优先数+非抢占式调度算法； D．进程数目增加。 5．在单处理机系统中实现并发技术后，下述说法正确的是（ C ）。

A．各进程在某一时刻并行运行，cpu与外设间并行工作； B．各进程在一个时间段内并发运行，cpu与外设间串行工作； C．各进程在一个时间段内并发运行，cpu与外设间并行工作； D．各进程在某一时刻并行运行，cpu与外设间串行工作。 6．用户程序向系统提出使用外设的请求方式是（ C ）。

A．作业申请； B．原语； C．系统调用； D．I/O指令。

7．用户进程调用系统调提出使用外设的请求，在执行系统调用前，用户进程运行在（ B ）；在执行系统调用过程中，用户进程运行在（ A ）。

A．系统态； B．用户态； C．系统态或用户态； D．内部态 二、填空题

1．多道程序设计是指每个时间段内有若干个进程在执行，但每一时刻只有一个进程执行。 2．在一台主机上同时连接多台终端，多个用户可以通过终端同时交互使用计算机资源，这种操作系统称为分时操作系统；允许多个用户将多个作业提交给计算机集中处理的操作系统称为批处理操作系统；计算机系统能及时处理过程控制数据并做出响应的操作系统称为实时操作系统。

3．操作系统的主要性能参数有系统资源利用率、系统吞吐量。

4．并发性是指在同一个时间间隔内，存在多个已经开始但还未结束的进程。

5．现代操作系统的两个最基本的特征是并发性和共享性。另外还有两个基本特性分别是虚拟性和异步性。 三、应用题

1．设某计算机系统有一个cpu、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到cpu运行，进程B后运行。进程A 的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms。进程B 的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图（可用甘特图）并说明：（1）运行过初中，cpu有无空闲等待？计算cpu利用率。（2）进程A和B运行过程中有无等待现象？

解：时序关系图如下：

50CPU输入设备打印机AB100150180200ABB300AA

（1） CPU有空闲，从100时刻到150时刻，CPU空闲，CPU的利用率为250/300*100%=83.3%。 （2）进程B在0~50时刻等待CPU。

复习题二

一、选择题

1．关于进程状态，下述说法正确的是（ D ）。

A．进程一旦形成，首先进入的是运行状态。 B．一个进程必须经过进程的三个基本状态才能结束。 C．进程可能同时处于某几种基本状态中。

D．分时系统中，一个正在运行的进程的时间片到且该进程还未运行结束，该进程将转

入就绪状态。

2．能从1种状态转变为3种状态的进程状态是（ D ）。

A．就绪； B．阻塞； C．完成； D．执行

3．系统有n（n＞2）个进程，且当前不再执行进程调度程序，下述哪种情况不可能发生？（ D ）

A．有一个运行进程，没有就绪进程，n-1个阻塞进程。 B．有一个运行进程，有一个就绪进程，n-2个阻塞进程。 C．有一个运行进程，n-1个就绪进程，没有阻塞进程。 D．没有运行进程，有2个就绪进程，n-2个阻塞进程。 4．所谓临界区是指访问临界资源的（ D ）。

A．一个缓冲区；B．一段数据区；C．同步机制；D．程序段 5．用V操作唤醒一个阻塞进程时，被唤醒进程的状态变为（ C ）。

A．运行； B．等待； C．就绪； D．完成 6．关于进程同步与互斥的说法错误的是（ B ）。

A．进程的同步与互斥都涉及到并发进程访问共享资源的问题。 B．进程的同步是进程互斥的一种特殊情况。

C．进程的互斥是进程同步的特例，互斥进程是竞争共享资源的使用，而同步进程之间

必然存在依赖关系。

D．进程互斥和进程同步有时候也称为进程同步。 7．关于进程通信的说法正确的是（ A ）。

A．进程通信有两种方式，直接通信和间接通信。 B．直接通信固定在一对进程之间。

C．间接通信是通过第三个进程转发信件的，不必在两个进程间直接相互通信。 D．间接通信方式以信箱为媒介实现通信，信箱由接收信件的进程设置。

8．若一个进程拥有100个线程，这些线程属于用户级线程，则该进程在系统调度执行时间上占用（ A ）个时间片

A．1； B．100； C．1/100； D．0 9．关于进程和线程的说法正确的是（ C ）。

A．线程是进程中可独立执行的子任务，一个进程可以包含一个或多个线程，一个线程

可以属于一个或多个进程。（错误，一个线程只能属于一个进程） B．线程又称为轻型进程，因为线程都比进程小。

C．多线程技术具有明显的优越性，如速度快、通信简便、并行性高等。 D．由于线程不作为资源分配单位，线程之间可以无约束地并发执行。

10.下列各项步骤中，哪一个不是创建进程所必须的步骤（ B ）。

A. 分配一个进程控制块PCB B. 由CPU调度程序为进程调度CPU

C. 为进程分配内存等必要的资源 D. 将PCB链入进程就绪队列 二、填空题

1．进程申请打印输出完成向系统发出中断后，进程的状态由阻塞态变化为就绪态。

2．一个正在执行的进程可能会因某种原因变为阻塞态、就绪态或终止态。

3．如果一个单处理机系统中有N个进程，运行进程最多1个，最少0个；就绪进程最多N-1个，最少0个；等待进程最多N个，最少0个。 4．进程申请CPU得不到满足时，其状态变为就绪态。

5．当进程由执行状态变为就绪状态时，CPU现场信息必须被保存在PCB中。 6．对临界资源的访问应采用互斥方式。

7．若信号量初值为3，当前值为-3，则表示有 3 个进程在该信号量上等待。

8．在具有N个进程的系统中，只允许1个进程（N≥1）进入它们的临界区，其信号量S的值的变化范围是1-N~1，处于等待状态的进程数最多是N-1个。

9．若有3个进程共享一个互斥段，每次最多允许1个进程进入互斥段，则信号量的变化范围是 -2~1。

三、应用题

1．设公共汽车上，司机和售票员的活动分别是：

司机的活动：启动车辆； 正常行车； 到站停车； 售票员的活动：

关车门； 售票； 开车门；

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用wait、signal操作实现它们的同步。

解：Semaphore S1=0,S2=0; 司机的进程： while(true)

{ wait(S1) 启动车辆； 正常行车； 到站停车； signal(S2) }

售票员的进程： while(true) {

关车门； signal(S1)

售票； wait(S2) 开车门； }

2．桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。

解：设置三个信号量S,So,Sa分别表示可否向盘中放水果，可否取桔子，可否取苹果。 初值分别为1，0，0。 Father() { while(1) { wait(S); signal(Sa); } } Mother() { while(1) { wait(S); signal(So); } } Son() { while(1) 取桔子; signal(S); 吃桔子; } } Daughter() { while(1) 取苹果; signal(S); 吃苹果; } } Cobegin { Father(); Mother(); Son(); Daughter(); } Coend { wait(So) { wait(Sa) 将苹果放入盘中; 将橘子放入盘中;

3．桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用wait、signal操作实现爸爸、儿子、女儿三个并发进程的同步。 解

设置三个信号量S,So,Sa ，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。 Father() { while(1) { wait(S); 将水果放入盘中; if(是桔子signal( (So); else signal(Sa); } } Son() { while(1) { wait (So) 取桔子 ) signal( (S); 吃桔子; } } Daughter() { while(1) { wait (Sa) 取苹果 signal( (S); 吃苹果; } } //并发执行 Cobegin { Father(); Son(); Daughter(); } Coend 4．有4个进程A,B,C,D共享一个缓冲区，进程A负责循环地从文件读一个整数放入缓冲区，进程B从缓冲区取出MOD 3为0的整数并累计求和；进程C从缓冲区取出MOD 3为1的整数并累计求和；进程D从缓冲区取出MOD 3为2的整数并累计求和.请用wait、signal操作写出能够正确执行的程序。

解：Semaphore mutex=1,S0=0,S1=0,S2=0;

int buffer=0,sumA=0,sumB=0,sumC=0,y=0 进程A while（true） {

从文件读入一个整数x; wait(mutex) buffer=x; signal( (mutex)

if buffer mod 3==0 signal(S0) else if buffer mod 3 ==1) signal(S1) else signal(S2) } 进程B while（true） {

wait(S0); wait(mutex); y=buffer; signal( (mutex) sumB=sumB+y; } 进程C while（true） {

wait(S1); wait(mutex); y=buffer; signal( (mutex) sumC=sumC+y; } 进程D while（true）

{

wait(S2); wait(mutex); y=buffer; signal( (mutex) sumD=sumD+y; } Cobegin

{进程A；进程B；进程C；进程D；} Coend

复习题三

一、选择题

1．既考虑作业的执行时间又考虑作业的等待时间的调度算法是（ C ）。

A．短作业优先；B．先来先服务；C．响应比高者优先；D．优先级调度

2．一个实时系统使用了4个周期事件，其周期分别为50ms，100ms，200ms，250ms。假设这4个周期事件分别需要35ms，20ms，10ms和x ms的CPU时间。保持系统可调度的最大x值是（ C ）

A．12 B．11 C．12.5 D．13

3．设系统有一类数量为M的独占性资源，系统中N个进程竞争该类资源，每个进程对资源的最大需求为W。当M,N,W分别取下列哪个值时，系统不会发生死锁的是（ B ）。

A．M=2;N=2;W=2; B．M=3;N=2;W=2; C．M=3;N=2;W=3; D．M=6;N=3;W=3; 4.关于安全状态的说法正确的是（ B ）

A.系统处于不安全状态一定会发生死锁。 B.系统处于不安全状态可能发生死锁。 C.不安全状态是死锁状态的一个特例。 D.系统处于安全状态时也可能发生死锁。 5．操作系统中，（ A ）负责对进程进行控制。

A.处理机管理功能 B.文件管理功能 C. 设备管理功能 D.存储管理功能 6．为了对紧急进程或重要进程进行调度，调度算法应采用（ B ）。

A.先来先服务法B. 优先级法 C.短作业优先法D. 时间片轮转法 7．避免死锁的一个著名的算法是（ B ）。

A．先入先出法 B．银行家算法 C．优先级算法 D．资源按序分配法

二、填空题

1．就绪队列中有n个就绪进程等待cpu调度，如果采用不同的调度算法，总共可能有n!种调度顺序。

2．有m(m>2)个进程的系统中出现死锁时，死锁进程的个数范围是2~m。 3．进程调度的方式有抢占式调度和非抢占式调度。 4．资源的有序分配策略可以破坏死锁的环路等待条件。

5．一个进程执行前必须获得所需要的所有资源，在只执行的过程中不在申请资源，这种策略可以破坏死锁的请求和保持条件。

6．产生死锁的四个必要条件是互斥条件、不抢占条件、请求和保持条件、环路等待条件。 7．作业从进入系统到最后完成，可能要经历三级调度，分别是： 高级调度 ， 中级调度

和 进程调度 。 三、应用题

1．有一个具有两道作业的批处理系统，作业调度采用短作业的调度算法，进程调度采用以优先数为基础的抢占式调度算法，有如下表所示的作业序列（表中所列作业优先数为进程优先数，数值越小，优先级越高）。 （1）列出所有作业进入内存的时刻及结束时刻。 （2）计算平均周转时间

作业名A B C D

到达时刻10：00 10：20 10：30 10：50

估计运行时间 40 30 50 20

优先数 5 3 4 6

解答：（1）10：00 A到达，无竞争，A进入内存，开始运行；

10：20 B到达，B进入主存，优先数为3，优于A，B开始运行； 10：30 C到达，由于内存中已经有两个进程，故不可进入；

10：50 B结束，同时D到达，同C争夺内存，D运行时间短，D被调度进入内存；A

的优先数高，开始运行；

11：10 A结束，C进入内存，C的优先数高于D，C开始运行； 12：00 C结束， D开始运行； 12：20 D结束。

（2）平均周转时间=280/4=70分钟

2．假设有4道作业，它们的提交时刻及执行时间由下表给出：

作 业 号 1 2 3 4 提交时刻 10.00 10.20 10.40 10.50 执行时间 2 1 0.5 0.3 计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。

解答：

先来先服务：调度顺序1，2，3，4 平均周转时间： （2+2.8+3.1+3.3)/4=2.8 平均带权周转时间：(1+2.8/1+31/5+11)/4=5.25 最短作业优先：调度顺序 1，4，3，2 平均周转时间（2+1.8+2.4+3.6)/4=2.45

平均带权周转时间（2/2+3.6/1+2.4/0.5+18/3)/4=3.85

3.设有P1、P2、P3、P4共4个进程同时依次进入就绪队列中，它们需要的处理器时间和优先级别如下所示：

进程 P1 P2 P3 P4 使用处理器时间（秒） 20 30 10 5 优先级 3 5 2 4 忽略调度所花费的时间，请回答下列问题：

（1）写出分别采用“先来先服务”和“非抢占式的优先数”调度算法选中的进程执行

的次序。

（2）在上述两种算法下，分别算出每个进程在就绪队列的等待时间和平均等待时间。 解答：解答：

（1） 用先来先服务的调度算法时，4个进程的调度次序是P1、P2、P3、P4。

用非抢占式的优先数调度算法时，4个进程的调度次序是P2、P4、P1、P3。

（2） 用先来先服务调度算法，每个进程在就绪队列中的等待时间分别为：

P1：0秒 P2：0+20=20秒 P3：0+20+30=50秒 P4：0+20+30+10=60秒

平均等待时间为：(0+20+50+60)／4=32.5秒

用非抢占式的优先数调度算法，每个进程在就绪队列中的等待时间分别为；

P1：30+5=35秒 P2：0秒

P3：20+30+5=55秒 P4：30秒

平均等待时间为：(35+0+55+30)／4=30秒

4．有一个多道批处理系统，作业调度采用“短作业优先”调度算法；进程调度采用“优先数抢占式”调度算法，且优先数越小优先级越高。如系统拥有打印机一台，采用静态分配（一旦分配，不能抢，直到进程使用完毕释放），忽略系统的调度开销。现有如下作业序列到达系统：

作业名 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.

解：(1)14:00无竞争，J1进入内存，调度J1运行20min

(2)14:20 资源满足，J2进入内存，由于J2的优先级高，调度J2，J2运行10min (3)14:30 J3到达，由于打印机不满足，故不能进入内存就绪，J2继续运行20min (4)14:50 J2结束，J4到达，资源满足，J4进入内存，由于J1的优先级高，调度

J1，J1运行10min (5) 15:00 J5到达，由于打印机不满足，故不能进入内存就绪，J1继续运行。 (6) 15:10 J1结束，释放打印机，短作业优先，J5进入内存。由于J5的优先级高，调度J5

(7)15:20 J5结束，释放打印机，J3进入内存。由于J3的优先级高，调度J3运行

(8) 16:10 J3结束，释放打印机。此时，内存中只有J4，调度J4 (8) 16:30 J4结束

作业的平均周转时间为（70+30+100+100+20）/5=64

作业的平均带权周转时间为（70/40+30/30+100/50+100/20+20/10）/5=2.35

5．设在某多道程序系统中有用户使用的内存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）全部进程执行结束所用的时间是多少？ 解：

解：在0时刻，进程0开始执行；

在4时刻，进程1到达，打印机资源不够，进入后备队列等待；调度进程0 在8时刻，进程0执行结束，释放15K内存和1台打印机。进程1的内存和打印机资源满足，进入内存就绪队列进而被调度执行。

在10时刻，进程2开始执行。

在11时刻，进程2结束，进程3到达，打印机资源不够，进入后备队列等待。调度进程1；

在13时刻，进程1执行结束，3资源满足，开始执行。

在16时刻，进程4到达，打印机资源不够，进程E进入后备队列等待。调度3执行。

在33时刻，进程3结束。进程4执行，47时刻结束。

进程0被选中2次；进程1被选中2次；进程2被选中1次；进程3被选中2次；进程4被选中1次；

全部进程执行结束所用时间为47分钟。

复习题四

一、选择题

1．在下列存储管理方案中，一个作业在内存中一定是连续存放的是（ A ）。

A．固定分区分配； B．分段存储管理方式； C．分页存储管理方式； D．段页式存储管理方式

2．在下列存储管理方案中，一个作业在内存中不一定是连续存放的是（ D ）。

A．单一连续分配；B．固定分区分配；C．可变分区分配；D．分段存储管理方式 3．要保证一个程序在主存中被改变了存放位置后仍能正确执行，则对主存空间应采用（ B ）。

A．静态重定位；B．动态重定位；C．动态分配；D．静态分配 4．下面关于重定位的说法错误的是（ A ）。

A．动态重定位中，地址转换工作是在作业装入过程中完成的。 B．用户程序中使用的从0地址开始的地址编号是逻辑地址。 C．动态重定位中装入内存的作业仍保持原来的逻辑地址。

D．静态重定位中，地址转换工作是在作业装入过程中完成的。 5．碎片最严重的存储管理方式是（ A ）

A．固定分区； B．可重定位分区； C．分页存储管理； D．分段存储管理。 6．以下有关动态分区管理的说法中正确的是（ A ）。

A．动态分区常采用的内存分配算法包括首次适应法、最佳适应和最坏适应算法等。 B．首次适应算法实现简单，但碎片过多使内存空间利用率降低。 C．最佳适应算法是最好的算法，但后到的较大作业很难得到满足。

D．最坏适应算法总是挑选可供作业使用的最小的空闲区，使剩下的分区成为内存碎片的可能性较大。

7．在固定分区管理中，为了提高内存的利用率，可采用如下技术（ A ）

A．按经常出现的作业大小来划分分区。

B．按作业对内存空间的需求量组成多个作业请求队列。 C．不同作业请求队列中的作业可以申请相同的分区。 D．大作业可以申请多个分区。

8．动态分区存储管理采用的地址转换公式是（ C ）

A．绝对地址=界限寄存器值+逻辑地址；B．绝对地址=下限寄存器值+逻辑地址； C．绝对地址=基址寄存器值+逻辑地址；D．绝对地址=块号*块长+页内地址； 9．以下各功能中，（ C ）不需要硬件的支持。

A．中断系统；B．地址映射；C．进程调度； D．页面调入； 10．分页存储管理方式中的页面是为（ B ）。 A．用户所感知的； B．操作系统所感知的； C．编译系统所感知的； D．连接装配程序所感知的。 11．联想存储器中的页，其信息（ C ）。

A．一定在外存中；B．一定在外存和内存中；C．一定在内存中；D．以上说法都不对。 12．分段存储管理中，处理零头问题可采用（ B ）方法。

A．重定位；B．拼接；C．Spooling技术；D．覆盖技术

13．采用分段存储管理时，一个程序如何分段是在（ B ）决定的。

A．分配主存时；B．用户编程时；C．装作业时；D．程序执行时 14．段式存储管理中分段是由用户决定的，因此（ B ）

A．段内的地址和段间的地址都是连续的。

B．段内的地址是连续的，而段间的地址可以是不连续的。 C．段内的地址是不连续的，而段间的地址是连续的。 D．段内的地址和段间的地址都是不连续的。 二、填空题

1．设有8页的逻辑空间，每页有1024B，它们被映射到32块的物理存储区中。那么，逻辑地址的有效位是13位，物理地址至少是15位。 2. 在一个分页系统中，页面的大小相等。

3. 分页存储管理方式中，操作系统将程序划分成若干大小相等的页面。

4．若分段存储管理中供用户使用的逻辑地址是24位，其中段内地址占用16位，则用户程序最多可分为256段。当把程序装入主存时，每段占用主存的最大连续区为64K字节。 6．在请求分页存储管理系统中，地址变换过程中，产生中断的原因可能是地址越界、请求的页不在内存）。

7．在请求分页存储管理系统中，需要的主要数据结构是页表。

8．请求分页存储管理系统必须至少具有的三种硬件支持是页表机制、地址转换机构、缺页中断机构。

9．实现虚拟存储器的关键技术是请求调入技术和置换技术。 三、简答题：

1．在分页、分段和段页式存储管理中，当访问一条指令时，需要访问内存几次？各做什么操作？

答：在分页存储管理中，至少访问两次，1次访问页表，1次访问指令； 在分段存储管理中，至少访问两次，1次访问段表，1次访问指令；

在段页式存储管理中，至少访问三次次，1次访问段表，1次访问页表，1次访问指令； 2．在固定分区管理、动态分区管理、分页存储管理、分段存储管理中，各会产生何种碎片？

答：在固定分区管理中，每个分区内都可能存在碎片；

在动态分区管理中，会存在一些很小的，不足以任何应用程序使用的小碎片； 在分页存储管理中，每个应用程序的最后一页可能存在碎片。

在分段存储管理中，可能存在小的内存区，不足以存放应用程序的一个连续的段，形成碎片。

四、应用题

1．在某多道程序系统中，供用户使用的内存空间为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 假设作业调度采用先来先服务算法，优先分配内存的低地址区域且不准移动已在内存中的作业，问：作业的调度顺序是什么？平均周转时间是多少？作业全部执行结束的时间是什么？ 解答：（1）8:00，调度作业1 （2）8:20，作业2的打印机不满足，未进入内存；作业3的内存资源满足，磁带机满足，进入内存。

（3）8:25，作业1结束，释放磁带机1台和打印机1台，释放15k的内存，但是由于作业2所需要的内存不满足，故未进入内存，打印机也未分配给它。调度作业3开始运行。 （4）8:30，作业4需要的内存资源和磁带机均满足，作业4进入内存。 （5）8:35，作业5到达，由于磁带机资源不满足，未进入内存。 （6）8:45，作业3运行结束，释放1台磁带机和60k内存，作业2的内存和打印机满足，进入内存，此时调度作业4开始运行。

（7）9:05，作业4运行结束，释放20k的内存和1台磁带机，调度作业2开始运行； （8）9:15，作业2结束，调度作业5开始运行 （9）9:30，作业5结束，至此全部作业执行完毕。 作业的调度顺序为：1,3,4,2，5；

平均周转时间（25+55+25+35+55）/5=39;

所有作业全部结束的时间是9:30，用时1.5小时。

2．某请求分页存储管理系统，允许用户空间为32个页面（每页1KB），主存为16KB，若一个用户程序有10页长，某时刻该进程的页表如下所示： 虚页号 0 1 2 3 4 5 6 其他 物理块号 8 7 4 10 5 3 2 无效 是否在TLB中 是 是 否 否 否 是 是 问：计算虚地址0AC5H、1AC5H对应的物理地址。 （2）页表存放在主存中，对主存的一次存取需要1.5ns，对TLB表的查找时间忽略为0，

试问这两次访问共耗费多少时间？ 解：（1）0AC5对应的二进制为0000101011000101，对应的页号为2，其物理地址为12C5 1AC5对应的二进制为0001101011000101，对应的页号为6，其物理地址为0AC5 （2）第一次访问两次内存，耗时1.5*2=3ns;第二次访问1次快表，1次内存，耗时1.5ns;两次共耗时4.5ns。

3．已知某系统页面长为4KB，页表项4B，采用多级分页策略映射64位虚拟地址空间，若限定第一级页表占1页，问需要采用几级页表？

解：由于每层页表的大小都不超过一页，所以每级的页号不超过10位。10*n+12>=64,所以采用6级页表。

4．一台机器有48位虚地址和32位物理地址，页面是8K，问在页表中需要多少个页表项？

481335

解：2/2=2

5.一个程序要把100×100的数组的初值置为“0”，现在假定有两个内存块可以用来存放数组信息，每个内存块可以存放200个数组元素，数组中的元素按行编址。两个内存块的初始状态都为空，若程序编写如下： （1）int A [100][ 100];

for i=1 to 100 for j=1 to 100

A[i][j]=0;; （2）int A [100][ 100];

for j=1 to 100 for i=1 to 100

A[i][j]=0;;

假设，程序已经在内存，当采用LRU页面置换算法时，（1）和（2）两个程序各会产生多少次缺页？ 解：（1）中，程序按行来访问，所以i=1时，缺页中断1次，调入两行，所以i=2时不再缺页中断，i=3时缺页中断1次，调入两行，所以i=2时不再缺页中断，以此类推，共缺页中断50次。

（2）中，程序按列进行访问，i=1、j=1时缺页中断，i=3,j=1时缺页中断，依次类推，j=1的前提下，i从1循环到100，共缺页中断50次；j=1循环到100共缺页中断50*100=5000次。

6.在请求页式存储管理系统中，页的大小为128B。有一个64*64的整型数组，系统按行存储，每个整数占用2B。若系统为它分配一个内存块存放数据，且程序已经驻留内存。试问实现为该数组清零操作时，可能产生多少次缺页中断？程序的代码编写如下： int A [64][64]; int i，j；

for （i=0； i<64;i++） for （j=0； j<64;j++） A[i][j]=0; 解：共64次缺页中断。

7.某操作系统的存储管理采用分页管理方式，系统的物理地址空间大小为32M，页的大小是4K，假定某进程的大小为32页，问： （1）写出逻辑地址格式；

（2）如果不考虑权限位，该进程的页表有多少项？每页至少多少位？

17

解：（1）逻辑地址空间4K*32=2，至少需要17位二进制 ，其中高5位表示页号，低12位

表示页内地址。

（2）页表项有32项，每页至少12位

8.在分页存储管理系统中，其页表存放在内存中。

（1）如果对内存的一次存取需要100微秒，则实现一次页面访问至少需要的存取时间是多少？

（2）若系统有快表，快表的命中率为80％，当页表项在快表中时，其查询快表的时间为20微秒，问此时的存取时间是多少？ 解：（1）实现一次页面访问至少访问两次内存，需要存取时间为100*2=200us （2）100+0.8*20+0.2*（100+20）=140us

9.在某请求分页存储管理系统中，假定访问内存的时间是10ms，平均缺页中断处理时间为25ms，平均缺页中断率为5%。试计算在请求分页存储管理系统中，平均有效访问时间是多少？ 解：在请求分页存储管理系统中，先访问页表，耗时10ms,若页在内存，则在访问一次内存，耗时10ms，若不在内存，缺页中断，耗时25ms,再访问一次内存，耗时10ms,故平均有效访问时间为10+10*0.95+（10+25）*0.05=21.25ms 10.假定某请求分页存储管理系统，内存的平均访问时间为1μs，辅存的平均访问时间为10ms，试问如果希望虚拟存储器的平均访问时间仅比内存的增加10%，则需要页面缺页率是多少？ 解：设页面失效率为x,则1*（1-x）+(1+10*1000)*x=1.1;x=0.001%

11.现有一请求分页的虚拟存储器，内存最多容纳4个页面，对于下面的引用串：1，2，3，4，5，3，4，1，6，7，8，9，5，4，5，4，2.分别采用FIFO,LRU,OPT页面替换算法，各将产生多少次缺页中断？ 解：（1）FIFO 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 5 2 3 4 3 4 1 5 1 3 4 6 5 1 6 4 7 5 1 6 7 8 8 1 6 7 9 8 9 6 7 5 8 9 5 7 4 8 9 5 4 5 4 2 2 9 5 4 共9+4=13次缺页中断 （2）LRU算法 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 5 2 3 4 3 4 1 5 1 3 4 6 6 1 3 4 7 6 1 7 4 8 6 1 7 8 9 6 9 7 8 5 5 9 7 8 4 5 9 4 8 5 4 2 5 9 4 2 共9+4=13次缺页中断 （3）OPT算法 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 5 3 4 3 4 1 6 6 5 3 4 7 6 5 7 4 8 8 5 7 4 9 9 5 7 4 5 4 5 4 2 2 5 7 4 共6+4=10次缺页中断

复习题五

一、选择题

1.用户进程请求打印一个输出文件的工作在以下哪一层完成。（ A ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序

2. 将一维磁盘块号转换为三维物理地址（柱面、磁道和扇区）的工作在以下哪一层完成。（ C ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 3. 获得设备驱动程序的入口地址的工作在以下哪一层完成。（ B ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 4. 将终端输入的字符转换为ASCII码的工作在以下哪一层完成。（ A ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 5. 向设备寄存器写命令的工作在以下哪一层完成。（ C ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 6. 检查用户是否有权使用设备的工作在以下哪一层完成。（ C ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 7. 维护一个最近使用块的缓存的工作在以下哪一层完成。（ B ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 8. 将二进制整数转化成ASCII码以便打印的工作在以下哪一层完成。（ A ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 9. 设备驱动进程被唤醒的工作在以下哪一层完成。（ D ）

A．用户层软件；B．设备独立性软件；C.设备驱动程序；D.中断处理程序 10．当中断发生后，进入中断处理的程序属于（C）

A．用户程序； B．可能是用户程序，也可能是操作系统程序； C．操作系统程序； D．以上说法都不对 11．引起I/O中断的事件有（ A ）。

A．数据传送完毕；B．指令错；C．缺页；D．访存越界

12．如果有多个中断同时发生，系统将根据中断优先级响应优先级最高的中断请求。若要调整中断事件的响应次序，可以利用（ D ）。

A．中断禁止；B．中断嵌套；C．中断响应；D．中断屏蔽

13．当用户程序执行访管指令（特权指令）时，中断装置将使CPU（ D ）

A．维持在用户态； B．维持在核心态；

C．从核心态转换到用户态； D．从用户态转换到核心态。 14．在SPOOLing系统中，用户进程实际分配到的是（ D ）

A．用户所要求的外设； B．一块内存区，及虚拟设备； C．共享设备的一部分存储区； D．虚拟设备的一部分空间； 15．有关设备的管理中说法错误的是（ B ）。

A．计算机系统为每台设备确定一个绝对号 B．每台设备都应该有一个惟一的相对号

C．申请设备时指定设备相对号使设备分配的灵活性强 D．启动设备时应指出设备的绝对号

16．对于硬盘上存放的信息，物理上读写的最小单位是一个（ C ）

A.二进位； B .字节； C.物理块 D.逻辑记录 17．下列磁盘调度算法中，（ B ）算法可能会随时改变移动臂的运动方向。

A．电梯；B．FCFS；C．循环扫描；D．以上都不对

二填空题

1．通道技术的引入，实现了处理器与设备的并行、设备与设备的并行、进程与进程的并发。 2．I/O控制发展的主要推动因素是将CPU从干预输入、输出的工作中解放出来。 3．I/O软件通常设为四个层次，分别是用户层软件、设备独立性软件、设备驱动程序和中断处理程序。 三、简答题

1．高速缓存和缓冲区的区别是什么？

答：高速缓存是用内存空间来暂存从磁盘中读出的一系列盘块中的信息，它逻辑上属于磁盘，而，物理上驻留在内存中的盘块。缓冲区是用于暂时存储数据的内存区域，逻辑上属于内存，物理上也是在内存。 四、应用题

1．一个快速磁盘转速为7200RPM（转/分），每磁道160个扇区，每扇区512字节，那么理想状态下，其数据传输速率为（9600KB/s）。 解答： 160*512/(1*60/7200)=9600KB/s

2．设L,M,N分别表示盘组的柱面数、盘面数、扇区数，B表示块号，则第i柱面、j磁头、k扇区所对应的块号B。给出它们之间的转换关系。

解析：块号从0开始编号，先编0柱面，再编1柱面，以此类推；针对某一柱面上的盘块，则先编0盘面，再编1盘，以此类推；针对某一盘面，按照扇区号编。即：（0柱面，0盘面，0扇区）对应0号块；（0柱面，0盘面，1扇区）对应1号块；（0柱面，0盘面，2扇区）对应2号块；……（0柱面，0盘面，N-1扇区）对应(N-1)号块; （0柱面，1盘面，0扇区）对应N号块；……（0柱面，1盘面，N-1扇区）对应2N-1号块；以此类推编号。

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）

3．假设一个磁盘组共100个柱面，每个柱面上有8个磁道，每个盘面被分成8个扇区。现有一个含有6400个逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从0开始，逻辑记录的编号也从0开始。文件信息从0柱面、0磁道、0扇区开始存放，试问：

（1）该文件的第3680个逻辑记录应该存放在什么位置？

（2）第78柱面的第6磁头的第6扇区中存放了该文件的第几个逻辑记录？ 解：一个柱面上有8*8=64个扇区， 3680/64=57余32 32/8=4余0

故 3680个逻辑记录存放在57号柱面、4磁头（盘面）、0扇区。 （2）78*64+6*8+6=5046

故第78柱面的第6磁头的第6扇区中存放了该文件的第5046个逻辑记录。 4.有10个记录在某磁盘的一个磁道上，假定这个磁道划分为10个扇区，每个扇区存放一个记录。现在要从磁道上顺序地将10个记录读出，如果磁盘转速为20ms转一周，处理程序每读出一个记录后花4ms进行处理。问处理完10个记录的总时间是多少？为缩短处理时间应如何安排这些记录？需要多少处理时间？ 解：如图所示，顺序存放

01234987607418369255

磁盘转速为20ms一周，所以，传输一条记录耗时2ms.

读第0条记录耗时2ms,处理该记录耗时4ms,此时，磁头位于第3条记录的起始位置。 磁头定位到第1条记录需要转过第3、4、5、6、7、8、9、0记录，故耗时8*2ms=16ms. 读第1条记录耗时2ms,处理该记录耗时4ms,此时，磁头位于第4条记录的起始位置。 磁头定位到第2条记录需要转过第4、5、6、7、8、9、0、1记录耗时8*2ms=16ms. 以此类推，

读出第9条记录耗时2ms,处理该记录耗时4ms。 处理完10个记录的总时间为：10*（2+4）+16*9=204ms

为缩短处理时间，安排记录时应将相邻的两条记录安排在相隔两个扇区的位置。如：第0记录放在0扇区，第1记录放在3扇区，第2记录放在6扇区，第3记录放在9扇区，第4记录放在2扇区，第5记录放在5扇区，第6记录放在8扇区，第7记录放在1扇区，第8记录放在4扇区，第9记录放在7扇区；

顺序存放优化存放

优化后，需要处理时间为10*（2+4）=60ms

6.有一移动臂磁盘，共100个磁道，每个磁道分8个扇区，磁盘转速为500r/s，磁头每移动一个磁道需要10ms，有一个用户请求访问第25磁道的第3扇区，并立即被系统响应，假设磁头当时处于15磁道上，磁头到达第25道时正处于1扇区的开始位置，试计算该用户至少需要等待多时时间？

解：因为磁盘转速为500r/s，转一圈耗时1/500=0.002s=2ms 寻道时间为：(25-15)*10ms=100ms 旋转延迟时间:2*2/8=0.5ms 传输时间为:2/8=0.25ms

用户至少需要等待时间为100+0.5+0.25=100.75ms

复习题六

一、选择题

1．对记录式文件，操作系统为用户存取文件信息的最小单位是（ C ）

A．字符； B．数据项； C．记录； D．文件

2．如果文件采用随机（直接）存取方法使用，且文件大小不固定，则应采用（ B ）物理结构。

A．直接； B．索引；C．随机；D．顺序 3．下列叙述中正确的是（ C ）。

A．在磁带上的顺序文件中插入新的记录时，必须复制整个文件； B．由于磁带的价格比磁盘便宜，用磁带实现索引文件更经济； C．变更磁盘上的顺序文件的记录内容时，不一定要复制整个文件； D．在磁盘上的顺序文件中插入新的记录时，必须复制整个文件

4.下述适合连续组织方式的场合是（ C ）；

A．从文件头部扩展；B．从文件中部扩展；C．从文件尾部扩展；D．从文件中部删除； 5. 下述适合链接组织方式的场合是（ A ）。

A．从文件头部删除；B．从文件中部扩展；C．从文件尾部扩展；D．从文件中部删除； 6.文件系统为每个文件另建立一张指示逻辑记录和物理记录之间的对应关系索引表，由此表和文件本身构成的文件是（ C ）。

A.顺序文件 B.链接文件 C.索引文件 D.逻辑文件

三、应用题

1．如果一个文件存放在100个数据块中，文件控制块、索引块或索引信息等都驻留在内存。下面各种情况下，需要做几次磁盘I/O操作？（假设每读或写一块磁盘块就是一次磁盘操作；假设在连续分配下，文件头部无空闲的磁盘块，但文件尾部有空闲的磁盘块）

（1）连续分配，将最后一个数据块搬到文件头部 （2）单级索引分配，将最后一个数据块搬到文件头部 （3）隐式链接分配，将最后一个数据块搬到文件头部 （4）采用隐式链接，将第一个数据插入文件尾部

解（1）每一个数据块的内容都要变化，故需要读出100块数据，写入100块数据，启动磁盘I/O200次

（2）1次，将索引块第一个表项的内容与最后一个表项的内容交换，然后启动1次I/O，将索引块的内容写入磁盘。

（3）102次，每个数据块的内容都要读入到内存，需要100次，第100个数据块要记下第一个块的块号，并写盘需要1次，第99块的连接指针要置空，并写盘需要1次。共102次 （4）102次，每个数据块的内容都要读入到内存，需要100次，第100个数据块要记下第一个块的块号，并写盘需要1次，第1块的连接指针要置空，并写盘需要1次。共102次 2．在UNIX中，外存组织方式采用增量式索引组织方式（混合索引），若盘块为1KB，每个盘块号占4个字节，即每块可放256个地址，如何将下列文件的偏移量转换为物理地址：9000，18000，420000

解：步骤1 将逻辑文件的字节偏移量转换为文件的逻辑块号和块内位移，方法是：将逻辑文件的字节偏移量/盘块大小，商为文件的逻辑块号，余数为块内偏移。

步骤2 将文件的逻辑块号转换为物理块号。使用混合索引结构，在索引节点中根据逻辑块号通过直接索引或间接索引找到对应的物理块号。 （1）9000/1024=9余783

其逻辑块号为9，故直接索引addr[8]中可以找到物理块号 （2）18000/1024=17余592

其逻辑块号为17，故直接索引addr[10]中可以找到物理块号 （3）420000/1024=410余160

其逻辑块号为410，故直接索引addr[11]中可以找到物理块号

3．某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项，假定物理块的大小是2K，每个索引项占用4B，问：

（1）该文件系统中最大的文件可以达到多大？ （2）假定一个文件的实际大小是128MB，该文件实际占用磁盘空间多大（包括间接索引块）？ 解：每个物理块可以存放2K/4=512个索引项

最大的文件大小为：8*2K+512*2K+512*512*2K=513M+16K

4．一个文件有100个磁盘块，假设文件控制块在内存。在下列情况下，分别计算并说明在连续组织方式和显示链接组织方式下，分别需要执行多少次磁盘I/O操作？（假设每读或写一块磁盘块就是一次磁盘操作；假设在连续组织方式下，文件头部无空闲的磁盘块，但文件尾部有空闲的磁盘块）

（1）在文件开始处添加一个磁盘块（需要往添加的磁盘块中写数据）； （2）在文件第50块前添加一个磁盘块（不需要往添加的磁盘块中写数据）； （3）删除文件第50块磁盘块；

（4）在文件结尾处删除一个磁盘块。 解：（1）连续分配，201次I/O；显示链接分配，1次I/O

（2）连续分配，102次I/O；显示链接分配，0次I/O （3）连续分配，100次I/O；显示链接分配，0次I/O （4）连续分配，0次I/O； 显示链接分配，0次I/O

显示链接分配集中于对文件分配表的修改。

5．若8个字（字长32位）组成的位示图管理内存，假定用户归还一个块号为100的内存块时，它对应位示图的位置是哪里？

解： （(100-1）/32+1=4,(100-1)mod 32 +1=4 ）（所有编号均从1开始）

6．假设一个磁盘组共有100个柱面，每个柱面有8个磁道，每个盘面被分为4个扇区。逻辑记录的大小与扇区大小相等，柱面、磁道、扇区的编号均从“0”开始，现用字长为16位的200个字（第0到199字）组成位示图来指示磁盘空间的使用情况。问：

（1）文件系统发现位示图中第15字第7位为0而准备分配给某一记录时，该记录会存放到磁盘的哪一块上？此块的物理位置（柱面号、磁道号和扇区号）是多少？

（2）删除文件是还要归还存储空间，第56柱面第6磁头第3扇区的块就变成了空白块，此时，位示图中的第几位应该由1改成0？

解：（1）15*16+7=247；247/(8*4)=7余23；23/4=5余3

该记录会存放到磁盘247块上。此块的物理位置（柱面号、磁道号和扇区号）是7柱面、5磁头，第3扇区

（2）56*32+6*4+3=1819,1819/16=113余11

位示图中的第113字的第11为应该由1改成0。

本文来源：https://www.bwwdw.com/article/nysp.html