发布于2021-11-25 20:51 阅读(828) 评论(0) 点赞(13) 收藏(2)
目录
1、分别计算按FCFS算法和SJF算法调度以下进程时的平均周转时间和平均带权周转时间。
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
5、当前位示图的内容为3B2C35D815382F3F,如果为一个文件分配两个块,应分配哪些块?如果回收26块和39块,位示图会发生什么变化?
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、空闲空间管理方法:空闲表、空闲区链、位示图
进程名称 | 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
分区编号 | 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 |
页号 | 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
则:
(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次
(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
解:
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
进程号 | 进程请求资源向量(最大) | 已分配资源向量 |
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 没有安全序列,不可以分配
(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黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 java黑洞网 All Rights Reserved 版权所有,并保留所有权利。京ICP备18063182号-2
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!