操作系统选综合练习.docx
《操作系统选综合练习.docx》由会员分享,可在线阅读,更多相关《操作系统选综合练习.docx(16页珍藏版)》请在冰点文库上搜索。
操作系统选综合练习
第一章作业
一、计算题
内存中有三个作业按照A---B---C的优先级次序执行,CPU计算和外设操作如下表所示:
请给出多道程序运行的时间关系图,完成这三个程序共用去多少时间?
分单通道和双通道讨论?
比单道方式节约多少时间?
(MS)
二、简述题
1、什么是操作系统?
2、操作系统有哪些特征?
3、如何理解操作系统的不确定性?
4、操作系统有哪些分类?
A
B
C
CPU计算
30
60
20
I/O
40
30
40
CPU计算
10
10
20
5、如何理解多道并发?
6请简述操作系统的引导过程
7、云操作系统如何理解?
8、什么是多核计算机,什么是网络操作系统?
第二章作业
一、基本理论题
1、进程,线程,管程之间的区别与联系?
2、什么是原语?
3、什么是进程调度?
4、内核功能有哪些?
5、信号量怎么理解?
6、举例说明死锁?
7、系统调用怎么理解?
8、临界区,临界资源?
9、进程创建的步骤?
10、进程状态切换的原因有哪些?
11、什么是挂起?
12、如何理解多核与多线程?
13、互斥与同步?
14、死锁产生的原因与条件?
15、什么是死锁定理?
16、如何理解银行家算法?
17、高级调度,中级调度,低级调度如何理解?
18、CPU的核心态如何理解?
二、算法题
1、分析生产者与消费者模型中的互斥与同步关系,设计恰当的信号量,给出P-v代码的实现
2、设计恰当的信号量实现读者---写者模型中的互斥与同步,要求分别给出读优先,写优先,读写公平的代码设计
3、哲学家进餐模型的互斥如何实现,请用两种不同的算法实现,分别给出代码设计
4、桌子上有一只盘子最多可容纳两个水果每次只能放入或取出一个水果。
爸爸专向盘子中放苹果apple妈妈专向盘子中放橘子orange
两个儿子专等吃盘子中的橘子两个女儿专等吃盘子中苹果。
请用P,V操作来
实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。
5、三个进程共用两个缓冲区S和T,GET负责送数据到S,COPY负责从S中复制数据,把复制好的数据送入到T中,PUT负责把T中的数据打印,要求S和T反复循环使用,请给出正确的P---v代码设计
三、计算题
1、P和Q两个进程优先级相同,信号量S1=S2=0并发执行后的X=?
Y=?
Z=?
VOIDP(VOID){Y=1;
Y=9;
Y+=3;
V(S1);Z=Y+1;
P(S2);
Y+=Z;
}
VOIDQ(VOID){X=1;
Y=8;
Y+=5;
P(S1);
X+=Y;
V(S2);
Z+=X;
}
2、
有三种类型的资源,5个进程,A资源的数量17,B的数量5个,C的数量20个,在T时刻系统状态如下所示:
进
MAX
ALLOCATION
程
A
B
C
A
B
C
P1
5
5
9
2
1
2
P2
5
3
6
4
0
2
P3
4
0
11
4
0
5
P4
4
2
5
2
0
4
P5
4
2
4
3
1
4
1、T时刻是否安全,若是给出安全序列
2、T时刻P2请求(0,3,4)能否分配为什么?
3、在
(2)的基础上P4请求(2,0,1)能否分配为什么?
4、在(3)的基础上P1请求(0,2,0)能否分配为什么?
3、
某系统有R1,R2,R3共三种资源,T0时刻P1,P2,P3,P4四个进程对资源的占用和需求情况如下所示:
系统的可用资源(2,1,2)
1、用向量或矩阵表达系统中各种资源总数和此时各个进程对资源的需求数量
如果此时P1和P2都发出REQUEST(1,0,为了保证系统的安全性应该如何分配资源给这两个进程,说明原因
2、如果
(2)中两个请求立即得到满足后,系统此时是否处于死锁状态。
进
MAX
ALLOCATION
程
R1
R2
R3
R1
R2
R3
P1
3
2
2
1
0
0
P2
6
1
3
4
1
1
P3
3
1
4
2
1
1
P4
4
2
2
0
0
2
第三章作业
一、基本知识点考核
1、什么是作业调度?
2、何为进程调度?
3、如何理解线程调度?
4、换入换出调度怎么理解
二、计算题
一、有一个具有两道作业的批处理系统,作业调度用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法,有如下的作业序列:
数值越小优先级越高
1、列出所有作业进入内存的时间和结束时间
2、计算平均周转时间
二、在一个单道批处理系统中,一组作业的提交时刻和运行时间如下所示:
计算以下三种作业调度算法的平均周转时间T。
1、先来先服务2、短作业优先法3、响应比高者优先
作业
到达时间
运行时间
优先数
A
10:
00
40分钟
5
B
10:
20
30分钟
3
C
10:
30
[50分钟
4
D
10:
50
20分钟
6
作业
提交时刻
运行时间
1
8.0
1.0
2
8.5
0.5
3
9.0
0.2
4
9.1
0.1
三、假定要在一台处理机上执行如表所示的作业,假定这些作业在时刻0以
1,2,3,4,5的顺序到达。
1、说明分别使用先来服务,时间片轮转法,时间片=1、短作业优先法以及非抢占式优先级调度算法时这些作业的执行情况。
2、针对上述的每种调度算法给出各自的平均周转时间,优先数越小优先级越高
作业
执行时间
优先级
1
10
3
2
1
1
3
2
p
4
1
4
5
5
2
第四章作业
一、基本理论题
1、存储管理主要研究哪些问题?
2、静态重定位与动态重定位有什么区别?
3、动态分区的基本思想是怎样的?
其空闲分区的分配算法有哪些?
4、什么是内存碎片?
5、基本页式管理的基本思想是什么?
6、分段的基本思想?
7、什么是虚拟存储器?
8、请求式分页的基本思想?
其页表表项结构是怎样的?
9、请求式分段的基本思想?
10、段页式的基本思想如何理解?
11、什么是动态链接?
用何种内存分配方法可以实现这种链接技术
12、请给出缺页中断的处理流程图
13、什么是局部性原理?
什么是抖动?
二、计算分析题
1、设有8页的逻辑空间,每页1024字节,它们被映射到32块的物理存储区中,那么,逻辑地址的有效位是多少位?
物理地址至少是多少位?
分页系统中,逻辑地址长度16位,页面大小2048字节,对应的页表如下所示:
现在有两个逻辑地址是0A5CH和2F6AH,经过地址变换后所对应的物理地址各是多少?
设有8页的逻辑空间,每页1024字节,它们被映射到32块的物理存储区中,那么,逻辑地址的有效位是多少位?
物理地址至少是多少位?
节,假设页号0,2,5,,17,20分别对应块号是5,20,8,14,36,求逻辑地址0A3CH,223CH分别对应的物理地址?
四、分页系统中,逻辑地址长度16位,页面大小2048字节,对应的页表如下所示:
现在有两个逻辑地址是0A5CH和2F6AH,经过地址变换后所对应的物理地
一、在可变分区管理中,用户区内存512KB,空白块用空闲区表的方法管理,如果分配时采用分配自由区低地址部分的方案,假设初始时全为空。
对于下述的申
请次序:
REQ(300K),REQ(100K),RELEASE300K),REQ(150K),REQ(30K),REQ(40K),REQ(60K),
RELEASE30K)回答下列问题:
1、采用首次适应算法,自由区有那些空块,给出其地址、大小?
2、如果采用最佳适应算法回答
(1)中的问题
3、如果再申请100KB,针对
(1)和
(2)各有什么结果?
二、假定存储器空闲块有如下结构:
请构造一串内存请求序列,首次适应分配算法能满足该请求序列,而最佳适应算法分配算法则不能。
三、设作业A,B,C的大小分别为30K,70K,和50K它们依次请求内存分配,内存现在有大小分别为100K,50K的两个空闲区,分别采用最佳适应算法和最差适应算法,画出内存分配的情况示意图。
段式管理系统中,有如下的段表以及逻辑地址,求逻辑地址:
(0,430)(1,10)
(2,500)(3,400)(4,112)(5,32)的物理地址各是多少?
段号
段基址
段长
0
210
500
1
2350
20
2
100
90
3
;1350
590
4
1948
95
第五章作业
一、本章基本理论题
1、文件管理的功能有哪些?
2、如何理解文件系统?
3、文件的物理结构?
4、文件的存取方法?
5、文件存储空间的管理方法?
6、FCB,目录,目录文件之间是什么关系?
7、文件共享如何实现?
8、文件保护有哪些方法?
9、文件的基本操作有哪些?
10、文件系统必须完成哪些工作?
11、为了保证文件的安全性,可以采取哪些措施?
二、算法题
某个文件系统,每个盘块为512B,文件控制块占64个B,其中文件名占8个字节,如果索引节点占2字节,对一个存放在磁盘上的256个目录项的目录,请比较引入索引节点前后,为了找到其中一个文件的FCB平均启动磁盘的次数。
答:
引入索引节点前:
256个目录项占用256*64/512=32个盘块,因此,在该目录检索到一个文件,平均启动磁盘的次数=(32+1)/2=17次
引入索引节点后:
每个目录项中只需要存放文件名和索引节点的编号,因此256
个目录项的目录共需要占用256*(8+2)/512=5个盘块。
因此,找到匹配的目录项平均需要启动3次磁盘,而得到索引节点编号后还需要启动磁盘将对应的索引节点读入内存,故平均启动磁盘4次。
可见,弓I入索引节点后,可大大减少启动磁盘的次数,从而有效提高文件检索的速度。
某系统的磁盘有500块,块号为0,1,2,…..499.
1、若用位示图法管理这500块的盘空间,当字长是32位时,此时位示图占了几
个字?
2、第I字的第J位对应的块号是多少?
(其中,I,j都从0开始编号
3、若块号从1开始编号,Ij也从1开始编号,第I字的第J位对应的块号是
多少?
4、若块号从0开始编号,Ij从1开始编号,第I字的第J位对应的块号是多
少?
如果盘快从1开始编号,每个盘快的大小是1KB,行号,列号从0开始编号.(位示图略去)
1、现要给文件分配两个盘块,请具体说明分配过程
2、如要释放磁盘的第300块,应如何处理
答;
(1)分配两个盘快的过程如下:
顺序检索位示图,从中找到第一个值为0的二进制位。
得到其行号i=2,列号j=2.,找到第二个值为0的二进制位,得到其行号i=3,列号j=6计算出两个空闲块的盘快号分别为:
B1=I1*16+J1+1=2*16+2+1=35B2=I2*16+J2+1=3*16+6+1=55
修改位示图,令map[2,2]=map[3,6]=1.并将对应块35、55分配出去
(2)计算第300块对应的行号I和列号J
I=INT((300-1)/16)=18J=(300-1)%16=11
修改位示图,令map[18,11]=0,表示对应块为空闲块第六章作业
一、本章基本理论题(知识点分布)
1、独占设备?
2、共享设备?
3、虚拟设备?
4、设备控制器?
5、通道?
6、信息传输控制方式有哪些?
7、为什么引入缓冲技术?
8、设备分配用到的数据结构有哪些?
9、什么是设备独立性?
10、I/O软件设计的目标/
11、什么是SPOOLING系统?
12、如何实现设备的独立性?
13、DMA与中断方式有什么区别?
14、什么是通道?
请给出通道方式下的CPU,通道,设备的工作流程图
15、请论述磁盘调度的电梯算法的基本思想?
16、外设软件分为哪四个层次?
说明一下工作在那层完成?
1)向设备寄存器写命令。
2)检查用户是否有权使用设备。
3)将二进制转成ASCII以便打印
17、DMA与通道方式有何不同?
18、设备管理的目标?
二、简述与算法
1、主机和外设之间信息传输的控制方式:
程序方式:
(单道方式)
由用户进程来直接控制内存和外设之间的数据传送,其优点是控制简单,也不要多少硬件支持,缺点是CPU和外设只能串行工作,设备之间也只能串行工作,无法发现和处理由于设备或其他硬件所产生的错误。
中断方式:
(第一次支持多道程序,做到了部分并行)
是通过向CPU发送中断的方式控制外设和CPU之间的数据传送,优点是:
大大提高了CPU的利用率并且能支持多道程序和设备的并行操作,缺点是:
由于数据缓冲寄存器比较小,如果中断次数较多,仍然占用大量的CPU时间,在外设
较多时,由于中断次数的急剧增加,可能造成CPU无法响应中断而出现中断丢失的现象。
DMA方式:
是在外设和内存之间开辟直接的数据交换通路进行数据传送。
优点:
除了在数据块开始传送时需要CPU的启动指令,在整个数据传送结束时需要发中断通知CPU进行中断处理之外,不需要CPU的频繁干涉。
缺点是在外设较多时多个DMA控制器的同时使用,会引发内存地址的冲突并使得控制过程进一步复杂化。
通道方式:
是使用通道来控制内存和外设之间的数据传送的方式,通道是一个独立于CPU的专门管理外设控制的I/O处理机,有自己的通道指令,这些指令由CPU启动,并在操作结束时向CPU发中断信号,这种方式的优点是进一步减轻了CPU的工作负担,增强了计算机系统的并行工作程度,缺点是增加了额外的硬件,造价昂贵
2、什么是中断?
给出中断处理的一般过程?
中断是指计算机在执行期间,系统内部外外设发生了某一个急需处理的事件,使得CPU暂停当前正在执行的程序而转去执行相应的事件处理程序,待处理完毕后返回断点处继续执行被中断的进程
中断处理的一般过程:
1、保存现场
由硬件自动把处理机状态字PSW和程序计数器PC中的内容保存到中断保留堆栈中
2、转中断处理程序,从相应的中断向量中获得中断处理程序的入口地址并装入程序计数器中,从而使CPU转向相应的中断处理程序
3、中断返回
中断处理完成后,通过中断返回指令,把保存在中断堆栈中被中断进程的现场信息取出来装入到相应的寄存器中使得CPU返回原先的断点处继续执行
3、、为什么要引入设备的独立性?
如何实现设备的独立性?
答:
引入设备的独立性,可使得应用程序独立于具体的物理设备,此时,用户用逻辑设备名称来申请使用某类物理设备。
为了实现设备的独立性,在应用程序中应使用逻辑设备名来请求和使用设备,系统中必须设置一张逻辑设备表,用来进行逻辑设备到物理设备的映射,其中每个表目包含了逻辑设备名,物理设备名和设备驱动程序入口地址三项,通过逻辑设备表来管理设备的分配和使用
4、什么是驱动程序?
为什么要有设备驱动程序?
用户进程怎样使用驱动程序?
答:
驱动程序驱动外部设备和相应DMA控制器或I/O控制器等器件,使之可以直接和内存进行I/O操作的子程序的集合。
他们负责设置相应设备的寄存器的值,启动设备进行操作,指定操作的类型和数据流向等。
设备驱动程序屏蔽了直接对硬件操作的细节,给编程者提供操作设备的接口用户进程通过调用设备驱动程序提供的接口来使用设备驱动程序
5、
设备驱动程序的处理过程是怎样的?
驱动程序是I/O进程与设备控制器之间的通信程序,它接收来自上层软件的,抽象的请求,再把它转换成具体要求后,发送给设备控制器,从而启动设备进行数据传送。
处理过程如下表示:
1、将抽象的请求转换成具体要求。
操作系统对用户屏蔽了有关物理设备的具体细节,并给用户一个一致的接口,因此,用户进程或上层软件发出的请求只能是一些抽象的命令,驱动程序必须将这些命令按设备控制器的要求的格式转换成具体的命令,如:
将READ命令中的盘块号按地址寄存器的格式转成盘面,磁道,扇区号等
2、检查I/O请求的合法性
3、读出并检查设备的状态
4、传送必要的参数
5、启动设备,进行数据传送
六、SPOOLING系统由那几部分组成?
请以打印机为例说明如何利用SPOOLING
技术实现多个进程对打印机的共享。
答:
SPOOLING系统由磁盘上的输入井和输出井,内存中的输入缓冲区和输出缓冲区以及输入进程和输出进程构成。
在用SPOOLING^术共享打印机时,对所有提出输出请求的用户进程,系统接受它们的请求时,并不真正把打印机分配给它们,而是给每个进程作两件事:
1、由输出进程在输出井中为它申请一个空闲缓冲区,并将要打印的数据送入其中。
2、输出进程给用户进程申请一张空白的用户打印请求表,把用户的打印请求填入表里,再将该表挂到打印队列上。
至此,用户进程觉得它的打印过程已经完成,而不必等待满速的打印过程的完成。
当打印机空闲时,输出进程从请求队列的对首取出一个打印请求表,根据表中的要求将要打印的数据从输出井传送到内存的输出缓冲区,再由打印机输出打印,打印完后,再处理下一个打印请求表直到打印队列为空。
这样,虽然系统中只有一个打印机,但系统并没有将它分配给任何用户进程,而只是给每个打印请求进程在输出井中分配一个存储区,这个存储区相当于一个逻辑上的打印机,使得每个用户进程都感觉自己在独占一个打印机,通过这样的方式实现对打印机的共享。
七、I/O软件的四个层次结构?
各层的功能?
(1)用户进程层执行输入输出系统调用,对I/O数据进行格式化,为假脱机输入/输出作准备
(2)独立于设备的软件实现设备的命名、设备的保护、成块处理、缓冲技术和设备分配
(3)设备驱动程序设置设备寄存器、检查设备的执行状态
(4)中断处理程序负责1/O完成时,唤醒设备驱动程序进程,进行中断处理
八、DMA和通道方式有什么不同?
DMA方式中,数据传送是在DMA控制器的控制下实现设备和内存之间的数据交换,这种方式适应于块设备的数据传输,通道方式与DMA方式类似,也是一种以内存为中心,实现设备和内存之间的数据交换,通道方式的数据传输是在通道控制器的控制下完成的,CPU只需要发出启动指令,指出通道相应的操作和I/O设备即可。
与DMA比较,通道方式所需要的CPU干预更少,系统并行度更高,效率更高
九、磁盘调度算法,假设磁盘有200个柱面,编号0-199,当前存取臂位置在143号柱面上,并刚刚完成了125号柱面的服务请求,如果存在以下的请求序列:
86,147,91,177,94,150,102,175,130请问:
为了完成上述请求下列算法中存取臂移动的总量是多少?
并写出存取臂移动的顺序。
(1)
先来先服务
(2)最短寻道法(3)电梯法
解答:
(1)先来先服务的顺序86,147,91,177,94,150,102,175,130移动总量565;
(2)最短寻道法的顺序:
147,150,130,102,94,91,86,175,177移动总量162;
(3)电梯法的顺序147,150,175,177,130,102,94,91,86移动总量是125
序号
柱面号
磁道号
块号
1
9
6
3
2
7
5
6
3
15
20
6
4
9
4
;4
5
20
9
5
6
7
15
2
十、假设磁盘存取臂当前处于8号柱面,有如下表所示的6个请求者等待访问磁盘,请给出最省时间的相应次序
参考答案:
6-2-4-1-3-5