程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

《操作系统》期末复习题

发布于2021-11-25 20:51     阅读(828)     评论(0)     点赞(13)     收藏(2)


目录

第一部分 基本概念

第一章:

第二章

第三章

第四章

第五章

第六章

第七章

第八章

第九章

第二部分 综合题:计算、分析

1、分别计算按FCFS算法和SJF算法调度以下进程时的平均周转时间和平均带权周转时间。

2、在如下分区表的基础上,按照首次适应和最佳适应三种算法依次分配五个进程P0、P1、P2、P3、P4时的进程开始地址。五个进程的大小为P0:200k,P1:15K,P2:100K,P3:80K,P4:20K。

3、一个分页式存储管理系统中页面大小为2K(2048字节),某进程的页表内容如下表所示。请将该进程的逻辑地址1FD3和205C转换为物理地址。

4、在一个请求分页虚拟存储器系统中,假定某个进程将按如下顺序访问页面:1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6

4、某磁盘有8192个磁道,编号为0~8191,在完成了磁道1250处的请求后,当前正在磁道3500处为一个请求服务。若此时请求队列的先后顺序为1000,4000,3300,5600,1300,6000,1200,2500。回答下述问题:

5、当前位示图的内容为3B2C35D815382F3F,如果为一个文件分配两个块,应分配哪些块?如果回收26块和39块,位示图会发生什么变化?

6、在系统的当前时刻,进程的资源请求和分配情况见下表:

7、有4个并发执行的进程A,B,C,D。在执行时它们都要读共享文件F,但限制进程A和进程B不能同时读文件F,进程C和进程D也不能同时读文件F。请问用PV操作管理时:


第一部分 基本概念

填空、选择、判断、简答

第一章:

1、什么是操作系统:操作系统是控制和管理计算机硬件和软件资源、合理地组织计算机工作流程,并方便用户使用计算机的一组程序集合

2、常见操作系统

Windows XP、Windows 2003、Windows 2000、Windows Vista

Linux、Unix

IBM AIX、IBM OS/2

Sun Solaris

3、操作系统分类:单道批处理系统、多道批处理系统、分时系统、实时系统、微机操作系统、网络操作系统、分布式操作系统、嵌入式操作系统

4、多道:在内存中同时装入多个程序,并使它们并发地执行。

5、分时:并发执行的多个程序均匀地分享CPU时间的运行方式。

6、多道批处理系统的优缺点

优点:CPU、内存以及I/O设备等资源的利用率高;系统吞吐量(单位时间内完成的总工作量)大。

缺点:平均周转时间(作业进入内存到运行结束时间)长;没有交互能力。

7、分时系统的特点

多路性:多个用户同时使用一台计算机;

独立性:用户之间互不干扰,就像各自独立使用一台计算机一样;

及时性:用户的各种请求(如输入数据)能够得到及时的响应;

交互性:用户通过各自的终端,与自己运行的程序进行交流。

8、操作系统的特点

并发性两个或多个程序在一段时间内同时执行。它们不是绝对地并行执行,而是在这一段时间内交替执行。并发性是操作系统最主要的特征。

共享性:系统资源可供多个并发执行的程序共同使用。分为互斥共享和非互斥共享两种。

虚拟性:通过软件方式,将一个物理资源变成多个虚拟的对等资源。

异步性:多个程序的执行顺序和一个程序的执行与中断次数无法确定。但是其结果始终是确定的。

9、操作系统的功能

处理机管理功能:进程控制

存储器管理功能:内存分配、内存保护、内存扩充以及地址转换

设备管理功能:缓冲区管理、设备分配和回收、设备驱动

文件和磁盘存储管理功能:目录管理、文件读写、存取控制、磁盘空间分配、空闲空间管理

用户接口:操作接口(分命令接口和图形接口)、程序接口(即系统调用)

第二章

1、进程的含义和组成:进程是某个程序在一组OS数据集合基础上的一次运行过程。进程运行所依赖的OS数据集合叫做进程控制块(PCB),所以进程由程序和PCB组成。

2、PCB的组成及其意义

3、进程的特点

动态性:是程序的一次并发执行过程,具有一定的生命周期。 每个进程在执行过程中都会按“执行-暂停-执行”方式推进,因此可以对不同阶段的进程定义不同的状态。

并发性:两个或多个进程在一段时间内“同时”执行,但某一瞬间只执行其中之一。因此实际上这些进程是交替执行的。

独立性:任何进程都是一个程序的一次独立运行过程,也是系统进行资源分配和调度的单位。

异步性:进程按不可预知的速度向前推进,所以OS应提供相应的措施保证其并发性。

结构性:每个进程都程序(由代码和数据组成)和PCB组成。

4、进程的状态

就绪(Ready)状态:此时进程等待CPU,并获得了除CPU以外所有的运行所需资源。由于存在多个就绪进程,OS将将它们排列成一个就绪队列。

执行(Running)状态:进程获得了CPU,并正在运行的状态。单CPU系统中只能有一个进程处于执行状态。

阻塞(Blocked)状态:进程由于等待除CPU以外的其它资源或I/O操作结束,而不能继续执行的状态。由于存在多个多个阻塞进程,系统将它们排列成一个或多个阻塞队列。

5、进程的状态转换关系

执行到就绪:执行进程被操作系统强制剥夺CPU,从而变成就绪进程。

就绪到执行:就绪进程被操作系统调度,从而变成执行进程。

执行到阻塞:由于申请资源未获准,或开始了I/O操作,执行进程将CPU让给其它就绪进程,从而变成阻塞进程。

阻塞到就绪:阻塞进程得到所请求资源,或执行的I/O操作结束,从而变成就绪进程。

6、进程控制:原语,状态转换原因及对应原语block,wakeup,create,terminate,schedule

第三章

1、进程同步与互斥,临界资源,临界区

2、记录型信号量的定义与应用

P(s){undefined

   s.value--;

if(p.value<0)

      block(s.L);

}

3、经典同步问题:生产者-消费者,读者-写者

4、进程通信方法:共享存储器(内存、数据结构)、管道(匿名、有名)、消息传递(直接、间接)

第四章

1、调度的种类:进程调度,作业调度,交换

2、进程调度算法:将CPU分配给就绪进程的算法,具体类型包括先来先服务调度算法(FCFS)、短作业(或进程)优先调度算法(SJF)、时间片轮转调度算法、优先权调度算法。

3、死锁的含义,产生死锁的4个必要条件及其含义,死锁的解决方法

4、银行家算法与安全算法

第五章

分区和分页的原理、地址转换过程、分配和回收步骤

1、动态分区式内存分配的含义:根据所要运行的程序大小,在内存中动态地划分出一个区域,并将程序转入该区域。等到程序运行结束时又回收此区域。

2、常用的动态分区分配算法:首次适应算法、循环首次适应算法、最佳适应算法、最差适应算法

3、空闲分区表的应用:分配时的变化、回收时的变化

4、分页式存储管理方法的基本原理:页、块以及页表

用户程序开始执行时,根据CPU中规定的大小,把用户程序划分成多个小块(称为“页面”)。每个页面装入内存中相同大小的不连续区域(该区域称为“物理块”)。同时建立该进程的页表,记录哪个页面装在哪个块内。

5、分页式存储管理方法的地址变换过程

将程序指令从内存读入CPU

根据块大小,将指令中的地址划分成两个部分:页号、页內地址

从内存页表中查找与页号对应的页表项,得到块号;

将指令中的页号替换成块号,完成地址转换

6、具有快表的分页式存储管理:提高地址转换速度

7、分段存储管理:地址格式,分配策略(段内连续分配,段间离散分配),地址转换

第六章

1、虚拟存储器:具有请求调入和置换(交换)功能,能从逻辑上扩充内存容量的存储管理系统。该系统应由硬件和软件配合实现。

2、虚拟存储器的容量:实际容量为内存容量和交换空间容量,最大容量为内存容量+外存容量。

3、虚拟存储器的实现方式:请求分页、请求分段

4、请求分页系统的原理,页表组成

5、置换算法:将外存的页面调入内存的同时,将内存中暂时不使用的页面换到外存的策略。一个好的置换算法应尽量避免“抖动”现象。

6、地址转换过程(缺页中断),置换算法(OPT、FIFO、LRU)

第七章

1、设备分类:独占设备、共享设备、虚拟设备

2、I/O控制方式的类型:程序访问方式、中断控制方式、直接存储器访问DMA方式、通道方式

3、缓冲区的分类:单缓冲、双缓冲、循环缓冲、缓冲池

4、设备分配数据结构(DCT、COCT、CHCT、SDT),分配流程,逻辑设备(实现设备无关)、虚拟设备(实现共享设备,spooling技术)

第八章

1、文件分类

逻辑结构划分:有结构文件(定长记录、变长记录)、无结构文件(流式)

物理结构划分(丛文件记录之间的关系):顺序文件、链接文件、索引文件

按存取控制划分:可执行文件、只读文件、可读写文件

2、文件目录结构:目录信息的结构(FCB、索引节点),树目录结构

第九章

1、外存空间的分配方式(从文件块之间的关系):连续分配、链接分配、索引分配

2、磁盘调度算法:对于多个磁盘访问请求,OS根据不同策略完成不同顺序的访问操作。其目的是减少磁头移动距离,提高整体访问性能。

3、常见的磁盘调度算法:先来先服务(FCFS算法)、最短寻道时间优先(SSTF)、扫描算法(SCAN算法,电梯算法)、循环扫描算法(CSCAN算法)

4、空闲空间管理方法:空闲表、空闲区链、位示图

第二部分 综合题:计算、分析

1、分别计算按FCFS算法和SJF算法调度以下进程时的平均周转时间和平均带权周转时间。

进程名称

A

B

C

D

E

到达时间

0

1

2

3

4

服务时间

4

3

5

2

4

解:

FCFS(先来先服务)算法

进程名称

A

B

C

D

E

到达时间

0

1

2

3

4

服务时间

4

3

5

2

4

完成时间

4

7

12

14

18

周转时间

(完成时间-到达时间)

4

6

10

11

14

带权周转时间

(周转时间/服务时间)

1

2

2

5.5

3.5

平均周转时间=(4+6+10+11+14)/5=9

平均带权周转时间=(1+2+2+5.5+3.5)/5=2.8

SJF(短作业优先)算法

进程名称

A

B

C

D

E

到达时间

0

1

2

3

5

服务时间

4

3

5

2

1

完成时间

4

10

15

6

7

周转时间

(完成时间-到达时间)

4

9

13

3

2

带权周转时间

(周转时间/服务时间)

1

3

2.6

1.5

2

平均周转时间=(4+9+13+3+2)/5=6.2

平均带权周转时间=(1+3+2.6+1.5+2)/5=2.02

2、在如下分区表的基础上,按照首次适应和最佳适应三种算法依次分配五个进程P0、P1、P2、P3、P4时的进程开始地址。五个进程的大小为P0:200k,P1:15K,P2:100K,P3:80K,P4:20K。

分区编号

1

2

3

4

5

6

起始地址

10K

200K

250K

320K

500K

850K

分区大小

100K

30K

50K

150K

300K

220K

解:所有进程的分配结果如下表所示。

首次适应是指根据进程的大小,在分区表中查找第一个能够装下进程内容的分区。对于本例来说,P0进程为200K,在分区表中从左到右查找能够装下P0进程的分区(即分区大小>=进程大小)为5号分区,所以P0进程的起始地址为5号分区的起始地址500K。分配P0后5号分区就会变成起始地址700K(原始起始地址500K+进程P0大小200K)、大小为100K(原始大小300K-P0进程大小200K),以此类推,可计算出其他进程的起始地址。

最佳适应是指查找某个分区大小最接近当前进程大小。对于P0进程来说,最接近其容量(必需大于等于)的分区为6号分区,所以P0进程在最佳适应分配算法的处理下,起始地址为6号分区的起始地址850K。分配P0进程后6号分区变成起始地址为1050K,大小为20K的分区,可以最佳装入P1进程,因此P1进程的起始地址为1050K。

答题时上述分析过程不需要写出,只需要写出下面的表格即可。

P0

P1

P2

P3

P4

首次适应:

500K

10K

320K

25K

200K

最佳适应

850K

1050K

10K

320K

200K

3、一个分页式存储管理系统中页面大小为2K(2048字节),某进程的页表内容如下表所示。请将该进程的逻辑地址1FD3和205C转换为物理地址。

页号

0

1

2

3

4

块号

3

7

12

13

31

解法1:

(1FD3)16=1*163+15*162+13*161+3*160=(8147)10,因此页号=(8147整除2048)=3,页内偏移地址=(8147取余2048)=2003,查页表可知页号3对应的块号为13,即3号页装入13号块,因此物理地址=13*2048+2003=28627。

(205C)16=2*163+0*162+5*161+12*160= (8284)10,因此页号=(8284整除2048)=4,页内偏移地址=(8284取余2048)=92,查页表可知4号页装入31号块,因此物理地址=31*2048+92=63580。

解法2:

(1FD3)16=(00011   11111010011)2,因此页号为3,查页表得到块号13=(1101) 2,最终物理地址为(01101   11111010011)2=(6fd3)16

4、在一个请求分页虚拟存储器系统中,假定某个进程将按如下顺序访问页面:1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6

则:

(1)在内存中只为该进程分配3个物理块,请使用先进先出置换算法计算出访问过程中所发生的置换次数;

(2)如果为该进程分配4个物理块,并使用LRU算法,置换次数又为多少?

解:

先进先出算法:

1

2

3

4

2

1

5

6

2

1

2

3

7

6

3

2

1

2

3

6

3

4

4

1

5

6

2

1

1

3

7

6

6

2

1

1

3

6

2

2

3

3

4

1

5

6

2

2

1

3

7

7

6

2

2

1

3

1

1

1

2

2

3

4

1

5

6

6

2

1

3

3

7

6

6

2

1

置换次数为14次

LRU算法:

1

2

3

4

2

1

5

6

2

1

2

3

7

6

3

2

1

2

3

6

4

2

1

5

6

2

1

2

3

7

6

3

2

1

2

3

6

3

3

4

2

1

5

6

2

1

2

3

7

6

3

2

1

2

3

2

2

2

3

4

2

1

5

6

6

1

2

3

7

6

3

3

1

2

1

1

1

1

1

3

4

2

1

5

5

6

1

2

2

7

6

6

6

1

置换次数为6次

4、某磁盘有8192个磁道,编号为0~8191,在完成了磁道1250处的请求后,当前正在磁道3500处为一个请求服务。若此时请求队列的先后顺序为1000,4000,3300,5600,1300,6000,1200,2500。回答下述问题:

(1)采用SSTF(最短寻道时间优先)算法完成上述请求。请写出磁头移动的顺序,并计算平均寻道长度。

(2)采用SCAN(电梯)算法完成上述请求。请写出磁头移动的顺序,并计算平均寻道长度。

解:

SSTF(最短寻道时间优先)算法:哪个进程的寻道位置与当前位置最近,先为该进程服务

(1) 3500->3300 移动200

(2) 3300->4000 移动700

(3) 4000->2500 移动1500

(4) 2500->1300 移动1200

(5) 1300->1200 移动100

(6) 1200->1000 移动200

(7) 1000->5600 移动4600

(8) 5600->6000 移动400

平均寻道长度=(200+700+1500+1200+100+200+4600+400)/8= 1112.5

SCAN(电梯)算法:模仿电梯动作规律,由于磁头从1250到达3500,因此先向大磁道号方向处理,再向小磁道号方向处理

(1) 3500->4000 移动500

(2) 4000->5600 移动1600

(3) 5600->6000 移动400

(4) 6000->3300 移动2700

(5) 3300->2500 移动800

(6) 2500->1300 移动1200

(7) 1300->1200 移动100

(8) 1200->1000 移动200

平均寻道长度=(500+1600+400+2700+800+1200+100+200)/8= 937.5

5、当前位示图的内容为3B2C35D815382F3F,如果为一个文件分配两个块,应分配哪些块?如果回收26块和39块,位示图会发生什么变化?

解:

3B2C35D815382F3F=(00111011  00101100  00110101  11011000  00010001  00111000   00111111    11111111),因此分配6和7块。回收后位示图为(00111011  00101100  00110101  01011000  00010001  00111000   00111111    11111111)=3B2C35 58 11 38 2F 3F

6、在系统的当前时刻,进程的资源请求和分配情况见下表:

进程号

进程请求资源向量(最大)

已分配资源向量

A

3 4 5

1 1 1

B

5 4 3

1 1 1

C

4 0 4

1 0 1

D

8 4 2

1 1 1

E

7 6 8

1 1 1

此时系统的可用资源向量为:3 5 4,试判断下述请求可否满足,并说明原因:

此时进程E申请资源,申请向量为:1 0 0

此时进程D申请资源,申请向量为:1 0 0

解:

此时进程E申请资源,申请向量为:1 0 0,预分配后的资源情况如下:

进程号

最大

已分配

还需

可利用

A

3 4 5

1 1 1

2 3 4

2 5 4  

B

5 4 3

1 1 1

4 3 2

C

4 0 4

1 0 1

3 0 3

D

8 4 2

1 1 1

7 3 1

E

7 6 8

2 1 1

5 5 7

     A  B  C  E  D  有安全序列,可以分配

此时进程D申请资源,申请向量为:1 0 0,预分配后的资源情况如下:

进程号

最大

已分配

还需

可利用

A

3 4 5

1 1 1

2 3 4

2 5 4  

B

5 4 3

1 1 1

4 3 2

C

4 0 4

1 0 1

3 0 3

D

8 4 2

2 1 1

6 3 1

E

7 6 8

1 1 1

6 5 7

 A  B  C   没有安全序列,不可以分配

7、有4个并发执行的进程A,B,C,D。在执行时它们都要读共享文件F,但限制进程A和进程B不能同时读文件F,进程C和进程D也不能同时读文件F。请问用PV操作管理时:

(1)应怎样定义信号量?写出信号量的初值和含义。

(2)写出能使它们正确执行的程序。

解:

(1)  S1=1   S2=1,分别表示A和B、C和D之间的互斥信号量

(2)  A  P(S1)  读文件F  V(S1)

    B  P(S1)  读文件F  V(S1)

    C  P(S2)  读文件F  V(S2)

    D  P(S2)  读文件F  V(S2)



所属网站分类: 技术文章 > 博客

作者:java小王子

链接:http://www.javaheidong.com/blog/article/331400/99dff7e33fe3764ca886/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

13 0
收藏该文
已收藏

评论内容:(最多支持255个字符)