《操作系统》课程复习资料
《操作系统》课程复习资料一、单项选择题：
1.若信号量S的初值为3，当前值为-1，则等待进程的个数为
A.2 B.1 C.3 D.0
2.采用段式存储管理的系统中，若地址用24位表示，其中8位段号，则允许每段的最大长度为[ C ]
A.2 的24次方 B.2 的16次方 C.2的8 次方 D.2的32次方
3.文件系统的按名存取主要是通过（）实现的。
A.存储空间管理 B.目录管理 C.文件安全性管理 D.文件读写管理
4.下面的叙述中，正确的是 [ B ]
A.线程是比进程更小的能独立运行的基本单位
B.引入线程可提高程序并发执行的程度，可进一步提高系统效率
C.线程的引入增加了程序执行时间的时空开销 D.一个进程一定包含多个线程
5.在分页存储管理中，主存的分配是 [ A ]
A.以物理块为单位 B.以作业大小为单位 C.以物理段为单位 D.以逻辑记录大小为单位
6.操作系统对文件实行统一管理，最基本的是为用户提供（）功能。 [ ]
A.按名存取 B.文件共享 C.文件保护 D.提高文件的存取速度
7.在下面的叙述中，正确的是 [ ]
A.同一进程的线程可并发执行，不同进程的线程只能串行执行
B.同一进程的线程只能串行执行，不同进程的线程可以并发执行
C.同一进程或不同进程内的线程都只能串行执行
D.同一进程或不同进程内的线程都可以并发执行
8.在有文件随机存取需求和长度动态增长的情况下，宜选择以下（）方式的文件存储结构。 [ ]
A.索引分配 B.连续分配 C.链接分配 D.都不对
9.通道是一种 [ ]
A.I/O 端口 B.数据通道 C.I/O专用处理器 D.软件工具
10.若磁盘柱面请求按到达时间顺序分别是55、39、18、90、160，磁头初始处于100柱面，移臂方向为向磁道号增加方向，则最短寻道时间调度算法下柱面访问次序是 [ ]
A.55、39、18、90、160 B.90、55、39、18、160
C.160、90、55、39、18 D.160、18、39、55、90
二、判断题：
1.文件系统采用混合索引分配方式时，设块长为512字节，每个块号长度为2字节，则采用二级索引可寻址的最大文件长度为256*256字节。 [ ]
2.在有线程的操作系统内，线程是资源分配的基本单位。 [ ]
3.在有线程的操作系统内，线程是处理器调度的基本单位。 [ ]
4.在分页存储管理中，作业的页面大小和内存物理块大小相同。 [ ]
5.如果信号量S的当前值为-5，则表示系统中共有5 个进程在等待S。 [ ]
6.采用三级索引的文件系统，存取一块盘块信息最多要访问4次磁盘。 [ ]
7.设备独立性是指设备驱动程序独立于具体使用的物理设备。 [ ]
8.操作系统以程序为单位分配系统资源。 [ ]
9.对临界资源应采用互斥访问方式来实现共享。 [ ]
三、名词解释
1.抖动 2.同步 3.文件的逻辑结构 4.并发 5.动态重定位
6.文件的物理结构 7.静态重定位 8.临界区 9.进程控制块PCB 10.固定分区分配
11.逻辑地址 12.进程的异步性 13.作业调度 14.死锁
四、简述题：
1.操作系统具有哪些基本特征？ 2.简述并发进程同步机制设计应遵循的四个原则。
3.简要说明处理机的三级调度。 4.Spooling技术如何使一台打印机虚拟成多台打印机？
5.简述请求分页存储管理实现虚拟存储的基本思想。
6.简述引入缓冲技术的原因。 7.死锁的4个必要条件是什么？
8.I/O系统一般分为几层，各层都负责什么工作？
9.动态（可变）分区管理技术中，当进程释放其所占内存分区时，操作系统要进行内存分区回收工作，将回收区插入空闲分区表（链）并进行空闲分区表（链）的修改。请简述内存分区回收时可能出现的几种情况以及该如何修改内存空闲分区表（链）。（假设空闲分区表按地址从低到高顺序排列）
10.如何理解操作系统是虚拟机？ 11.如何理解进程与程序的区别与联系？
12.分析常用几种文件物理结构及优缺点？
五、综合题：
1.设文件索引节点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节。若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件最大长度是多少。
2.有3个并发进程R、M、P，它们共享同一缓冲区。进程R负责从输入设备读信息，每读入一个记录后，就把它放进缓冲区中；进程M在缓冲区中加工读入的数据；进程P把加工后的记录打印输出。读入的记录经过加工输出后，缓冲区又可以存放下一个记录。
3.某操作系统采用可变分区分配存储管理方法，用户区为512K且始值为100，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，其初始时用户区的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请150K，释放100K。
请回答：采用首次适应算法，主存最后有哪些空闲块(给出始址,大小)？画出主存空闲区变化图。
4.设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页大小2048 字节，内存总共有8个存储块。
试问逻辑地址至少应为多少位？内存空间有多大？
5.三个进程P1、P2、P3互斥使用一个共享缓冲区。P1每次生成一个正整数送入缓冲区；P2每次用从缓冲区中取出一个奇数；P3每次从缓冲区中取出一个偶数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。
要求：用伪代码描述。（其中生成一个正整数用produce（）表示；将数据放入缓冲区用put()表示，取出一个奇数用getodd()表示，取出一个偶数用geteven()表示）
6.若递交给磁盘驱动程序的磁盘柱面请求按到达时间顺序分别是55、58、39、18、90、160、150、38、184，设磁头初始处于100柱面，移臂方向为向磁道号增加方向移动。
请给出最短寻道时间优先算法和电梯调度算法的平均寻道长度。
7.假定某页式系统，主存为64KB，分成16块，块号为0~15。设某作业有4页，其页号为0，1，2，3，被分别装入主存的2，4，1，6块。
试问：（1）写出该作业每一页在主存中的起始地址。
（2）逻辑地址用[页号、页内偏移]的形式给出，则逻辑地址,相应的内存地址分别是多少。
8.设系统中有5个进程{P0，P1，P2，P3，P4}和3类资源{A，B，C}，各类资源总数分别为10、5、7，在T0时刻的资源分配情况如下表所示：
请问：P1发出请求向量Request1（1，0，2），分析系统是否可同意请求。
9.在一个请求页式系统中，假如一个作业的页面需求走向为5，1，2，3，4，5，3，4，1，分配给该作业的物理块数M为3（初始为空，第一次缺页即算缺页次数）。
计算FIFO、LRU两种页面置换算法下，在访问过程中所发生的缺页次数和缺页率。
10.单道作业系统，有5个作业A，B，C，D，E几乎同时到达，预计它们的运行时间为10，6，2，4，8 min，其优先级分别为3，5，2，1，4，这里5为最高优先级。
要求：分别采用：（1）先来先服务算法（按A，B，C，D，E）；（2）优先级调度算法；
（3）时间片调度算法（时间片为2min）。
求平均周转时间分别是多少？
《操作系统》课程复习参考答案
一、单项选择题：
1.B 2.C 3.B 4.B 5.A 6.A 7.D 8.A 9.C 10.B
二、判断题：
1.√ 2.× 3.√ 4.√ 5.√ 6.√ 7.× 8.× 9.√
三、名词解释：
1.抖动：在页式虚拟存储管理技术中，刚被调出内存的页面又立即要用，需要调入内存，而刚被调入不就又要被调出，系统内这种页面频繁换进/换出的现象称为抖动。
2.同步：异步环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步
3.文件的逻辑结构：用户看到的文件的组织方式。
4.并发：并发性是指两个或多个事件在同一时间间隔内发生
5.动态重定位：动态重定位是在程序执行过程中，将要访问的程序或数据的逻辑地址转换成内存地址，完成重定位工作。
6.文件的物理结构：文件的物理结构是指文件在存储设备上的存放方法。
7.静态重定位：地址转换工作，即重定位是在作业执行前集中一次完成的，在作业执行过程中不再进行地址转换工作
8.临界区：进程中访问临界资源的那段代码称为临界区
9.进程控制块PCB：操作系统管理和控制进程的数据结构，用以记录与进程相关信息的，是系统感知进程存在的唯一标志。
10.固定分区分配：将内存划分为若干个固定大小的区域（分区），每个分区中装入一道作业，允许几道作业并发运行。11.逻辑地址：目标程序使用的地址单元称为逻辑地址
12.进程的异步性：进程按各自独立的、不可预知的速度向前推进
13.作业调度：指按一定的策略从外存上处于后备状态的作业中选择一个或多个，给它们分配内存、I/O设备等必要资源，并建立相应的进程，将其插入就绪进程队列。
14.死锁：多个进程在运行过程中因争夺资源而造成的一种僵局状态，若无外力作用，它们都将无法再向前推进，则称这一组进程出现死锁
四、简述题：
1.答：操作系统的基本特征有：并发性、共享性、虚拟性和不确定性。
并发性是指两个或多个事件在同一时间间隔内发生；共享性是指系统中硬件和软件资源可供多个用户程序共同使用；虚拟性是指把一个物理上的实体变为若干个逻辑上的对应物；不确定性是指多道程序环境中，由于资源等因素的限制，程序是以走走停停的方式运行的；系统中的每个程序何时执行，多个程序间的执行顺序以及完成每道程序所需的时间是不确定的，因而也是不可预知的。
2.答：（1）空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以便有效地利用临界资源。
（2）忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
（3）有限等待：对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死锁”状态。
（4）让权等待：当进程不能进入自己的临界区时，应立即释放处理机。
3.答：处理机调度一般分为3级：作业调度，交换调度，进程调度。其中，作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列；进程调度根据一定的调度算法从就绪队列中选出一个进程，并把其状态改为运行状态，把CPU分配给它。交换调度是位于高级调度和进程调度之间的一种调度，为了提高内存的利用率，系统将那些暂时不能运行的进程挂起，当内存空间宽松时，通过交换调度选择具备运行条件的进程，将其唤醒。总之，作业调度为进程活动做准备，而进程调度使进程正常活动起来，交换调度将暂时不能运行的进程挂起。
4.答：将一台独享打印机改造为可供多个用户共享的打印机，是应用Spooling技术的典型实例。具体做法是：系统对于用户的打印输出，并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送入其中；然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。若打印机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。
5.答：请求分页存储管理是在基本分页存储管理系统的基础上，增加了请求调页功能、页面置换功能从而实现虚拟存储。在请求分页存储管理中，作业运行之前，指要求将当前需要的一部分页面装入内存，便可启动作业运行。在作业执行过程中，当所要访问的页面不在内存时再通过调页功能将其调入，同时还可以将通过置换功能将暂时不用的页面换出到外存上，也便腾出内存空间。
6.答：引入缓冲技术是为了缓解CPU与I/O设备间速度不匹配的矛盾，提高它们之间的并行性，减少对CPU的中断次数，放宽CPU对中断响应时间的要求。缓冲区的大小一般和盘块大小相同，缓冲区的个数可以根据数据I/O速率和加工处理的速率之间的差异来确定，可设置单缓冲、双缓冲或多缓冲。
7.答：（1）互斥条件：进程对所分配到的资源进行排他性使用；
（2）请求和保持条件：进程提出了新的资源请求，但又对自己已获得的资源保持不放；
（3）不剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺；
（4）环路等待条件：发生死锁时，存在进程-资源的等待链。
8.答：I/O系统由用户层软件、设备独立性软件、设备驱动程序和中断处理程序组成。用户层软件使用系统调用接口来与I/O设备通信。内核的设备独立性软件接收I/O请求，然后它又通过设备驱动程序与I/O设备实现数据传输，在数据传输过程中调用相关的终端处理程序，设备驱动程序接收上一层的请求，并将逻辑I/O的调用装转换为对具体设备驱动程序的调用。设备驱动程序具体负责与设备有关的所有交互操作。中断处理程序用于进程上下文切换、读取设备状态等。
9.答：（1）回收区与插入点的前一个空闲分区F1相邻接：将回收区与前一区合并，不必增加新表项，只需修改F1的大小为两者之和。
（2）回收区与高地址F2分区邻接：此时将回收分区与该分区合并，回收区的首地址为新分区的首地址，大小为两者之和。
（3）回收区与前后分区F1和F2都邻接：将此3个分区合并，F1（前邻接区）的首地址为新分区的首址，大小为三者之和，取消F2表项。
（4）回收区与任何空闲区都不邻接：在插入点建立一个新表项，填写回收区的首地址和大小。插入到空闲区表的适当位置（后移插入点后的各个表项）
10.答：操作系统为用户提供了一种虚拟机，用户不再直接使用硬件机器（裸机），而是通过操作系统来使用和控制计算机，从而拥有一个功能更强，使用更方便的计算机，称为虚拟计算机。从虚拟机的观点看，操作系统分成若干层次，每一层完成特定的功能，提供对上一层的支持，构成上一层的运行环境，最内层的硬件是整个操作系统的基础，操作系统通过逐个层次的功能扩充，向用户提供全套服务，完成用户的作业要求。
11.答：两者的区别与联系是：
（1）进程是动态的概念，程序是静态的概念；
（2）进程具有并发性和异步性，程序的并发执行是通过进程实现的；
（3）进程是能独立运行的单位，是一个系统资源分配、运行调度的基本单位，程序没有独立性；
（4）程序和进程没有一一对应关系，一个进程可以顺序执行多个程序，一个程序可由多个进程共用。（5）进程具有生命周期，进程的存在是暂时的，程序的存在是永久的。
12.答：（1）顺序结构：是一种最简单的物理结构，它把逻辑上连续的文件信息一次存放在连续编号的物理块中。只要知道文件在存储设备上的起始地址和文件长度就能很快地进行存取。
（2）链接结构：将逻辑上连续的文件分散存放在若干不连续的物理块中，每个物理块有一个指针，指向其后续的物理块。只要指明文件第一个块号，就可以按链指针检索整个文件。这种结构的优点是文件长度容易动态变化，其缺点是不适合随机访问。
（3）索引结构：将逻辑上连续的文件存放在若干不连续的物理块中，系统为每个文件建立一张索引表，索引表记录了文件信息所在的逻辑块号。索引表也以文件的的形式存放在磁盘上，给出索引地址，就可以查找文件与文件逻辑块号对应的物理块号。这种结构的优点是既适合文件长度的动态变化，也适合随机访问。
（4）索引顺序结构：索引表每一项在磁盘上按顺序连续存放物理块中。
五、综合题：
1.答：数据块大小为256字节，每个地址项大小为4字节，则每个磁盘块最多存储索引项256/4=64个。
4个地址项是直接地址索引，可表示的文件最大长度是4×256字节=1K字节
2个地址项是一级间接地址索引，可表示的文件最大长度是（2×64）×256字节=32K字节
1个地址项是二级间接地址索引，可表示的文件最大长度是（1×64×64）×256=1024K字节。
所以综合起来，７个地址项全部利用上，可表示的单个文件最大长度是1K+32K+1024K=1057K。
2.答：设置三个信号量
Emptybuf：对应进程R要使用的资源，即空缓冲区，初值为1
Dataprocess：对应进程M要使用的资源，即待加工的数据记录，初值为0
Dataprint：对应进程P要使用的资源，即待打印的数据记录，初值为0
算法如下：
semaphore emptybuf, dataprocess, dataprint;
emptybuf.value=1 , dataprocess.value=dataprint.value=0
parbegin
process R { wait(emptybuf)；从输入设备读记录到缓冲区；signal(dataprocess)；}
process M {wait(dataprocess)； 在缓冲区加工记录；signal(dataprint.value)；}
process P {wait(dataprint.value);打印记录；signal(dataprint)；}
parend
3.答：最后剩余空闲块大小为362K。始址为250。主存空闲区变化图如下：
4.答：页式存储管理系统中的逻辑地址结构为：页号P+页内偏移W。本题设定每页为2048=211字节，所以页内偏移部分地址需要占11个二进制位，逻辑地址空间最大为16页，即逻辑地址空间大小为16×2048B=215B，所以页号部分地址需要占4个二进制位，即逻辑地址至少应为15个二进制位。由于内存有8个存储块，而存储块大小与页面大小相等，故内存空间大小为8×2048=214B.
5.答：
semaphore empty, fullodd, fulleven;
item buffer;
empty.value=N; fullodd.value=0; fulleven.value=0;
parbegin
process p1
{number=produce();
wait(empty);
wait(mutex)
put();
if(number MOD 2 = =1)
signal(fullodd);
else
signal(fulleven);
signal(mutex);
}
process p2
{wait(fullodd);
wait(mutex)
getodd();
signal(mutex)
signal(fullodd）;
};
process p3
{wait(fulleven);
wait(mutex)
geteven();
signal(mutex);
signal( fulleven);
}
Parend
6.答：（1）最短寻道时间优先算法：
柱面访问次序：90, 58, 55, 39, 38, 18, 150, 160, 184
总寻道长度=（100-90）+（90-58）+（58-55）+（55-19）+（39-38）+（38-18）+（150-18）+（160-150）+（184-160）=248
平均寻道长度=248/9=27.56
（2）电梯调度算法：
柱面访问次序：150, 160, 184, 90, 58, 55, 39, 38, 18
总寻道长度=（150-100）+（160-150）+（184-160）+（184-90）+（90-58）+（58-55）+（55-39）+（39-38）+（38-18）=250
平均寻道长度=250/9=27.78
7.答：（1）依照题意得页表为：
页号 块号
0 2
1 4
2 1
3 6
主存为64KB，分成16块，所以每块大小为作业64KB/16=4KB。所以，该作业各页在内存的起始地址如下：第0页的起始地址为4KB×2=8KB
第1页的起始地址为4KB×4=16KB
第2页的起始地址为4KB×1=4KB
第3页的起始地址为4KB×6=18KB
（2）逻辑地址位于0号页面，其内存地址是4KB×2+100B=8292B
逻辑地址位于1号页面，其内存地址是4KB×4+50B=16434B
8.答：（1）P1发出请求向量Request1（1，0，2），按银行家算法，分析系统是否可同意请求。
①Request1(1,0,2)≤Need1(1,2,2) ②Request1(1,0,2)≤Available(3,3,2)
③系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成资源变化情况如下表所示。
（2）再利用安全性算法检查此时系统是否安全。如下表所示。
即存在安全序列{P1,P3,P4,P2,P0}，故系统是安全的，可以立即将P1所申请的资源分配给它。
9.答：（1）采用FIFO页面置换算法，对应的页面置换情况如下表：
页面走向 5 1 2 3 4 5 3 4 1
物理块0 5 5 5 3 3 3 3 3 1
物理块1 1 1 1 4 4 4 4 4
物理块 2 2 2 2 5 5 5 5
缺页 缺 缺 缺 缺 缺 缺 缺
缺页7次，缺页率为7/9
（2）采用LRU页面置换算法，对应的页面置换情况如下表：
页面走向 5 1 2 3 4 5 3 4 1
物理块0 5 5 5 3 3 3 3 3 3
物理块1 1 1 1 4 4 4 4 4
物理块 2 2 2 2 5 5 5 1
缺页 缺 缺 缺 缺 缺 缺 缺
缺页7次，缺页率为7/9
10.答：（1）先来先服务调度算法：作业调度顺序是A，B，C，D，E
作业名称 提交时间 完成时间 周转时间
A 0 10 10
B 0 16 16
C 0 18 18
D 0 22 22
E 0 30 30
平均周转时间=（10+16+18+22+30）/5=19.2
（2）优先级调度算法：作业调度顺序是D，C，A，E，B
作业名称 提交时间 完成时间 周转时间
B 0 6 6
E 0 14 14
A 0 24 24
C 0 26 26
D 0 30 30
平均周转时间=（6+14+24+26+30）/5=20
（3）时间片轮转算法：作业调度顺序是A，B，C，D，E；A，B，D，E；A，B，E；A，E；A
作业名称 提交时间 完成时间 周转时间
A 0 30 30
B 0 22 22
C 0 6 6
D 0 16 16
E 0 28 28
平均周转时间=（30+22+6+16+28）/5=20.4
页:
[1]