大题部分0s信科复习题模板.docx
《大题部分0s信科复习题模板.docx》由会员分享，可在线阅读，更多相关《大题部分0s信科复习题模板.docx（16页珍藏版）》请在冰点文库上搜索。
大题部分0s信科复习题模板
os复习题
一.选择题（20分）
自己准备，多为概念的理解，多数在平日讲过的每章的题里能找到类似题。
二.判断题（10分）
自己准备，多为概念的理解，多数在平日讲过的每章的题里能找到类似题。
三.概念与简述题（20分）
从下面的题里出，下面的题里大约考其中50%。
1.并发:
是指两个或多个事件在同一时间间隔内发生。
2.并行:
是指两个或多个事件在同一时刻同时发生。
3.裸机:
计算机系统中的硬件常被称为裸机。
4.虚拟机:
由计算机硬件和操作系统所组成的计算机系统称为“虚拟机”。
5.抖动现象:
刚被调出的信息又被调入内存，调入后不久又被调出内存，又被调入内存，调入后不久又被调出内存，如此反复，这种现象就是抖动现象。
6.Belady现象:
在未给作业分配满足需要的主存块数时，分配物理页增多，缺页次数反而升高的现象。
该现象一般发生在先来先服务页面置换算法中
7.设备的独立性:
采用“设备类、相对号”的方式使用设备时，用户编制程序时不必指定特定的设备。
在程序中使用由“设备类、相对号”定义的逻辑设备。
程序执行时系统根据用户指定的逻辑设备转换成与其对应的具体物理设备，并启动该物理设备工作。
于是用户编制程序时使用的设备与实际使用哪台设备无关。
把这种特性称为“设备的独立性”。
8.微内核技术：
微内核技术是指精心设计的、能实现现代操作系统核心功能的小型内核，它短小精炼，不仅运行在核心态，而且开机后常驻内存。
微内核中仅包括操作系统中最主要、最基本、最底层的功能，它不是一个完整的操作系统，它为通用操作系统的开发提供底层支持，在此内核的基础上结合模块化、层次化设计方法以及面向对象技术可以非常方便地开发出具有各种特点的操作系统。
9.中断：
中断是指计算机在执行期间，系统内发生非寻常的急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或选择优先级高的新的进程执行的过程。
10.死锁的4个必要条件：
互斥，不剥夺，部分分配，环路条件。
11.画出进程3个基本状态之间的转换图。
写出与进程运行状态改变有关的引发进程调度的原因（至少3种）。
答：
（1）当前进程执行完
（2）当前进程由执行态进入阻塞态。
（3）当前执行的进程所分配的时间片用完。
12.在磁盘上有一个文件系统，磁盘每块512字。
假定每个文件在目录中占有一个目录项，该目录项给出了文件名、第一个索引块的地址、文件长度（块数）。
在索引块中（包括第一个索引块）前面511个字指向文件块，即第i个索引项（i=0，1，2，…510）指向文件的第i块，索引块中最后一个字指向下一个索引块，最后一个索引块中最后一个字为null。
假定目录在存储器中，每个文件的逻辑块号均从0开始编号，逻辑块与物理块长相同。
对这样的索引物理结构，该系统应如何将逻辑块号变换成物理块号？
（采用举例、画图等方式进行描述）
答：
根据逻辑块号确定该逻辑块所在的索引块和在索引块中的位置，方法：
逻辑块号除以511得到的整数部分为所在的索引块号，余数部分为在索引块中的位置；然后在索引块的链中，找到逻辑块所在的索引块，并读入内存，分离出逻辑块所在物理块号。
假设逻辑块号是788，该逻辑块所在的索引块号=788/511=1，索引块中的位788%511=277，在文件的目录项中找到首个索引块（第0个索引块）的地址，把该索引块读入内存，把最后一项分离出来，即第1索引块所在的物理块号，把该物理块读入内存，分离出277项，即为所求的物理块号。
四．分析计算题（50分）
从下面的题里出同类型类似题，考试时所有题都要算出最终结果，不能象下面一些例子只摆式子，另外下例不保证答题过程和答案完全正确，仅供参考题型和解题思路。
1.分页管理，访问虚拟页序列是7,0,1,2,0,3,0,4,2,3,0,3，分配到3个物理页面，画出不同页面置换算法结果，得出缺页率。
（1）先进先出FIFO
（2）最近最久未使用页面置换算法LRU（3）理想型淘汰算法OPT（缺页率能化简的要化简，下例中的没化简）
（4）假设访问一次内存100ns，缺页中断处理时间20ms，求LRU算法中这些页面的平均访问时间。
（以ns为单位）
（1）FIFO，缺页10次，所以缺页率10/12
7
0
1
2
0
3
0
4
2
3
0
3
1
7
7
7
2
2
2
2
4
4
4
0
0
2
0
0
0
0
3
3
3
2
2
2
2
3
1
1
1
1
0
0
0
3
3
3
是否缺页
是
是
是
是
否
是
是
是
是
是
是
否
（2）LRU,缺页9次，所以缺页率9/12（这里没对每列重新排序，你可以象书上那样对页面重新排序，把需要替换的排到最下面）
7
0
1
2
0
3
0
4
2
3
0
3
1
7
7
7
2
2
2
2
4
4
4
0
0
2
0
0
0
0
0
0
0
0
3
3
3
3
1
1
1
3
3
3
2
2
2
2
是否缺页
是
是
是
是
否
是
否
是
是
是
是
否
（3）OPT，缺页7次，所以缺页率7/12
7
0
1
2
0
3
0
4
2
3
0
3
1
7
7
7
2
2
2
2
2
2
2
2
2
2
0
0
0
0
0
0
4
4
4
0
0
3
1
1
1
3
3
3
3
3
3
3
是否缺页
是
是
是
是
否
是
否
是
否
否
是
否
（4）200ns*3/12+（200ns+20*10^6ns）*9/12
2.某操作系统的存储管理采用页式管理系统，系统的物理地址空间大小为4MB，页的大小是1KB，假定该系统中进程空间的大小为16MB，问：
（1）逻辑页号和页内地址各多少位
（2）物理页号和页内地址各多少位
（3）一共有多少个物理页
（4）采用位示图管理内存空间，问位示图要占多少字节？
答：
1KB=2^10字节，所以页内地址占10个二进制位
4MB=2^22字节，页内地址占了10位,所以物理页号占12位
16MB=2^24字节，页内地址占了10位,所以逻辑页号占14位
一共有2^22/2^10=2^12页
每页占位示图中1bit，一共有2^12页，所以位示图需要2^12/8=2^9字节。
综上以上分析
（1）14位,10位
（2）12位，10位
（3）2^12个物理页
（4）位示图占2^9字节。
3.假定某磁盘的旋转速度是每圈20毫秒，格式化时每个盘面被分成个10扇区，现有个10逻辑记录存放同一在磁盘上，安排如图1所示。
处理程序要顺序处理这些记录，每读出一条记录后处理程序要花4毫秒的时间进行处理，然后再顺序读下一条记录并进行处理，知道处理完成这些记录，回答
（1）顺序处理完这10条记录总共花费了多少时间？
（2）请给一种记录优化分布的方案，使处理程序能在短时间内处理完这10条记录，并计算优化分布时需要花费的时间。
（3）假设每个磁盘块大小为1KB,问该磁盘的数据传输率为多少（单位KB/S）
图1逻辑记录的存放次序
答：
（1）磁盘旋转一个扇区所需时间=20/10=2ms
则读出并处理一条记录所需时间=2+4=6ms,共10条记录需要60ms.
转到下个需要处理的扇区需要花费20-4=16ms，这样的等待时间需要9次，共16*9=144ms
所以一共花费60+144=204ms。
（2）一种记录优化分布的方案如图2所示。
这种记录优化分使处理程序在处理完前一条逻辑记录时磁头正好旋转到下一条逻辑记录所在的扇区，处理所需的时间最短，处理完这10条记录需要花费的时间=10*（2+4）+9*0=60ms。
图2逻辑记录优化环分布
（3）20ms转一圈，读出10个扇区，每个扇区1KB,即20ms读出了10KB，10KB/20ms=500KB/S。
4.分页系统，快表命中率60%，一次内存存取时间为1ns，缺页时要发生置换，如果无页面修改标记，一个缺页中断要8000ns，有修改标记的，一个缺页中断要20000ns，两种情况各占40%，60%，为保证有效访问时间不超过5ns，求允许的最大缺页率f是多少
EAT=a（&+t）+（1-a）[（1-f）（&+t+&+t）+f（&+t+t1+&+t）]<=5ns
其中a=60%,t=1ns,&=0,t1=8000*40%+20000*60%代入即可解得f。
5.设存在三个过程get、copy和put分别对缓冲区S和T进行操作，其中get负责将数据块存入缓冲区S，copy负责从缓冲区S读出数据并复制到缓冲区T中，put负责从缓冲区T中读出数据并打印，如图所示。
请用P、V操作描述上述三个过程。
设信号量：
sempty:
表示S允许存入（为1表示允许），初值为1;
sfull：
表示S允许取出（为1表示允许），初值为0;
tempty:
表示T允许存入（为1表示允许），初值为1;
tfull:
表示T允许取出（为1表示允许），初值为0;
对进程的描述：
Main（）
{
Cobegin
Get（）;
Copy（）;
Put（）;
Coend
}
Get（）
{
While
（1）
{获取一数据x;P（sempty）;buff（S）=x;V（sfull）;}
}
copy（）
{
While
（1）
{P（sfull）;y=buff（S）;V（sempty）;
p（tempty）;buff（T）=y;v（tfull）;}
}
put（）
{
While
（1）
{P（tfull）;z=buff（T）;V（tempty）;输出数据z;}
}
6.P1、P2、P3互斥使用一个N单元的缓冲区，P1用produce（）生成一个正整数，用put（x）把该数放入缓冲区某一空单元；P2用getodd（）从缓冲区取出一个奇数，用countodd（）统计奇数个数；P3用geteven（）从缓冲区取出一个偶数，用counteven（）统计偶数个数，写出P1、P2、P3的伪代码。
答：
定义信号量empty，表示空单元个数，初值为N；定义信号量odd表示放奇数单元的个数，初值为0；定义信号量even表示放偶数单元的个数，初值为0；定义信号量mutex，用于实现缓冲区互斥，初值为1。
P1（）:
Begin
L1:
x=produce（）
p（empty）
p（mutex）
put（x）
v（mutex）
ifx%2=1thenv（odd）
elsev（even）
gotoL1
end
P2（）:
Begin
L2:
P（odd）
P（mutex）
Getodd（）
v（mutex）
v（empty）
countodd（）
gotoL2
end
P3（）:
Begin
L3:
P（even）
P（mutex）
Geteven（）
v（mutex）
v（empty）
counteven（）
gotoL3
end
7.各作业情况如下：
作业号
到达时刻
开始时刻
运行需时
结束时刻
次序
优先级别
1
0
2
4
2
1
5
9
3
2
8
1
4
3
3
8
优先级为小值优先，求平均周转时间和带权平均周转时间?
1.先来先服务2.短作业优先3.静态优先（小的优先）
答：
1.先来先服务
作业号
到达时刻
开始时刻
运行需时
结束时刻
次序
优先级别
1
0
0
2
2
1
4
2
1
2
5
7
2
9
3
2
7
8
15
3
1
4
3
15
3
18
4
8
0时刻只有作业1到达，所以先执行1；2时刻作业2和3都到达，2先到所以执行2；7时刻作业3和作业4都到达，3先所以执行3，再执行4
平均周转时间=[（2-0）+（7-1）+（15-2）+（18-3）]/4=9
平均带权周转时间=[（2-0）/2+（7-1）/5+（15-2）/8+（18-3）/3]/4
2.短作业优先
作业号
到达时刻
开始时刻
运行需时
结束时刻
次序
优先级别
1
0
0
2
2
1
4
2
1
2
5
7
2
9
3
2
10
8
18
4
1
4
3
7
3
10
3
8
0时刻只有作业1到达，所以先执行1；2时刻作业2和3都到达，2短所以先执行2；7时刻作业3和4都到达，4短所以执行4，最后执行3
平均周转时间=[（2-0）+（7-1）+（18-2）+（10-3）]/4=7.75
平均带权周转时间=[（2-0）/2+（7-1）/5+（18-2）/8+（10-3）/3]/4
3.静态优先级
作业号
到达时刻
开始时刻
运行需时
结束时刻
次序
优先级别
1
0
0
2
2
1
4
2
1
13
5
18
4
9
3
2
2
8
10
2
1
4
3
10
3
13
3
8
0时刻只有作业1到达，所以先执行1；2时刻作业2和3都到达，3优先值小所以先执行3；10时刻作业2和4都到达，4优先值小所以执行4，最后执行2
平均周转时间=[（2-0）+（18-1）+（10-2）+（13-3）]/4=9.25
平均带权周转时间=[（2-0）/2+（18-1）/5+（10-2）/8+（13-3）/3]/4
8.系统中磁头停留在磁道号为70的磁道上，这时先后有4个进程提出了磁盘访问请求，要访问磁盘的磁道号按申请到达的先后顺序依次为45,68,28,90.移动臂的运动方向：
沿磁道号递减的方向移动。
若分别采用FCFS磁盘调度算法、SSTF算法、SCAN算法时，磁头移动的顺序和所需寻道长度分别是多少？
如果每移动一个柱面需要3ms，移动时间分别是多少？
FCFS：
70---45---68---28---90
寻道长度=（70-45）+（68-45）+（68-28）+（90-28）=150,移动时间150*3ms
SSTF：
70---68---90---45---28
寻道长度=（70-68）+（90-68）+（90-45）+（45-28）=86，移动时间86*3ms
SCAN：
70---68---45---28---90
寻道长度=（70-68）+（68-45）+（45-28）+（90-28）=104,移动时间104*3ms
因为题里给出移动方向，所以电梯调度只有这一种，否则应为两种答案
如果做CSCAN（单项扫描，也叫循环扫描）：
方向规定为从外向里，在本题里访问次序应为70----90-----28------45-------68
寻道长度等自己算
9．现有四个进程P1，P2，P3，P4共享R1，R2，R3三类资源，资源分配情况如表1所示，采用银行家算法
（1）目前系统是否处于安全状态？
（2）现在如果进程P2提出申请资源数量为（1,0,1），能否为它分配？
（3）P2申请资源后，若P1再请求（1,0,1），能否为它分配？
（4）P1申请资源后，若P3再请求（0,0,1），能否为它分配?
表1系统当前资源分配表
进程
Max
R1R2R3
Allocation
R1R2R3
Need
R1R2R3
Available
R1R2R3
P1
3
2
2
1
0
0
2
2
2
112
P2
6
1
3
5
1
1
1
0
2
P3
3
1
4
2
1
1
1
0
3
P4
4
2
2
0
0
2
4
2
0
MAX表示各进程最大需求资源数，Allocation表示已经分配的资源数，Need表示仍需要的资源数，Available表示现在可用的资源数。
这几项不需要都给出，要注意表里给出的是什么。
以下为简答：
（1）通过分析，举出一个安全序列，P2、P3、P4、P1，说明系统能够按这一次序执行完所有进程，那么就说明当前系统处于安全状态。
（需要具体说明为什么有这个安全序列）
（2）分配给P2后剩下资源为（0,1,1），P2此时需求变为（0,0,1），仍可以使P2执行完毕，即仍存在
（1）中的安全序列，因此可以分配。
（3）此时剩余资源是（0,1,1），不能满足P1的请求（1,0,1），因此P1进入阻塞状态，不能进行分配。
（4）P1申请资源后进入阻塞状态，此时剩余资源仍是（0,1,1），若分配给P3（0,0,1），则剩余（0,1,0），不足以满足任何进程执行完，此时不存在安全序列，因此不能分配。
10.各进程情况如下：
进程号
到达时刻
开始时刻
运行需时
结束时刻
次序
1
0
3
2
2
6
3
4
4
4
6
5
5
8
2
采用最高响应比优先算法，求平均周转时间和带权平均周转时间?
答：
最高响应比优先
进程号
到达时刻
开始时刻
运行需时
结束时刻
次序
1
0
0
3
3
1
2
2
3
6
9
2
3
4
9
4
13
3
4
6
15
5
20
5
5
8
13
2
15
4
0时刻只有进程1到达，所以先执行1；3时刻只有进程2到达，所以执行2；9时刻进程3、4、5都到达,进程3此时响应比是1+（9-4）/4=2.25,进程4此时响应比是1+（9-6）/5=1.6,进程5此时响应比是1+（9-8）/2=1.5，所以执行进程3；13时刻还剩进程4和5，进程4此时响应比是1+（13-6）/5=2.4,进程5此时响应比是1+（13-8）/2=3.5，所以执行进程5，然后再进程4
平均周转时间=[（3-0）+（9-2）+（13-4）+（20-6）+（15-8）]/5=8
平均带权周转时间=[（3-0）/3+（9-2）/6+（13-4）/4+（20-6）/5+（15-8）/2]/5
11.进程PA用于向缓存区A存放数据，进程PB从缓存区A中取数据加工,加工后放入缓存区B中，进程PC把缓存区B中的数据取出输出，用P、V操作实现进程PA、PB、PC间的同步。
（写清楚每个信号量代表的意义及初值，用伪代码实现这三个进程）
答：
设信号量Aempty表示缓冲区A是否允许放数据，值为1时表示允许，初值为1；信号量Afull表示缓冲区S是否允许取数据，值为1时表示允许，初值为0；信号量Bempty表示缓冲区B是否允许放数据，值为1时表示允许，初值为1；信号量Bfull表示缓冲区B是否允许取数据，值为1时表示允许，初值为0。
进程PA、PB、和PC描述如下：
PA（）
begin
L1：
取存入缓冲区A的数据x
P（Aempty）
把数据x存入缓冲区A中
V（Afull）
gotoL1
end
PB（）
begin
L2：
P（Afull）
把缓冲区A的数据存入x中
V（Aempty）
对x进行加工
P（Bempty）
把加工后的x存入缓冲区B中
V（Bfull）
gotoL2
end
PC（）
begin
L3：
P（Bfull）
把缓冲区B的数据存入x中
V（Bempty）
打印数据x
gotoL3
end
升级会员 