文档库

最新最全的文档下载
当前位置:文档库 > 操作系统复习

操作系统复习

一、操作系统的概念:操作系统是控制和管理计算机硬件和软件资源,合理地对各种资源进行分配和调度,规范计算机工作流程,方便用户使用的程序的集合。

操作系统的基本特征

1并发性

并发是两或多个事件在同一时间间隔内发生。

并行是指两或多个事件在同一时刻发生。

–2共享性

互斥共享:一段时间只允许一个进程访问该资源

同时访问:计算机系统中还有一些资源,允许同一时间内多个程序对它们进行访问。

–3虚拟性

4异步性

分时系统的产生

概念:指一台主机上连接了多个带有显示器和键盘的终端,同时允许多个用户

共享主机中的资源,各个用户都可通过自己的终端以交互方式使用计算机。

特征:多路性、及时性、独立性、交互性

二、操作系统提供的服务和用户接口:命令接口、图形接口、程序接口

处理机执行时的工作状态:

管态(核心态)

目态(用户态)

系统调用是应用程序请求操作系统内核完成某一功能的一种特殊的过程调用。

进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。是系统进行资源分配和调度的单位

进程和程序的区别

程序静态的,进程是动态的。

程序和进程的组成不同:进程=程序+数据+PCB

程序的存在是永久的,进程是有生命周期的

一个程序可以对应多个进程,一个进程可包含多个程序。

进程的特征:动态性、结构性、异步性、独立性

进程的状态:运行状态、就绪状态、阻塞状态

操作系统复习

1.如果系统中有N个进程,运行的进程最多几个,最少几个;就绪进程最多几个最少几个;等待进程最多几个,最少几个?

[解答]:在单处理机系统中,处于运行状态的进程最多为1个,最少为0个;处于

就绪进程最多为N-1个,最少为0个;处于阻塞的进程最多为N个,最少为0个。

进程控制块(PCB)是进程存在的唯一标志

调度算法:

例:如下一组进程P1、P2、P3,到达系统的先后顺序分别如下面三图所示,计算各种顺序的平均周转时间

先来先服务FCFS

操作系统复习

操作系统复习

操作系统复习

操作系统复习

操作系统复习

操作系统复习

短作业优先SJF

操作系统复习

操作系统复习

高响应比优先调度HRRF 响应比= 1+等待时间/运行时间

操作系统复习

操作系统复习

例题:假如5个就绪进程其到达系统和所需CPU 时间如下表所示(单位:毫秒),如果忽略I/O 以及其他开销分别计算采用FCFS 、非抢占式SJF 、HRRF 调度算法进行CPU 调度的平均周转时间。

操作系统复习

(1)采用FCFS 的调度顺序为

平均周转时间为:

T=((3-0)+(9-2)+(13-4)+(18-6)+(20-8))/5=8.6 (2)采用非抢占SJF 的调度顺序为:

平均周转时间为: T=7.6

(3)HRRF 算法:

在时刻0时进程A 就绪,此时,CPU 空闲,故A 运行,到了时刻2时进程B 就绪,进程A 结束后,进程B 进入运行,接着进程C 、D 、E 先后到达,进入就绪状态。进程B 运行结束后,调度程序要从C 、D 和E 中选择一个投入运行,为此,计算它们的响应比:

RRc=9/4=2.25 RRd=8/5=1.60 RRe=3/2=1.50 因此,C 进程被选择投入运行。进程运行4个单位后结束

A B C

D E 0

3

9

13

18

20 A B E C

D

3

9

11

15

20

进程C 运行4个单位后结束,调度程序需要从D 和E 进程挑选一个运行,为此,计算它们的响应比: RRd=12/5=2.40 RRe=7/2=3.5

因此,选择E 投入运行。综上所述,进程的调度顺序为: 平均周转时间为:T=8.0

四、进程间的同步关系:指系统中一些进程需要相互合作,共同完成一项任务而相互等待的关系。 进程互斥:由于竞争同一个物理资源而相互制约。这种对共享资源的排他性的使用关系就是进程的互斥关系。

临界资源:统中某些资源一次只允许一个进程使用,称这样的资源为临界资源或互斥资源或共享变量. 临界区:进程中访问临界资源的一段代码。 进程通信

根据进程之间通信量大小,分为:低级通信机制、高级通信机制 高级通信方式分类:管道通信机制、共享存储区通信机制、消息传递通信机制

死锁的概念:如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件 (这里指释放资源),则称一组进程或系统此时发生了死锁 死锁产生原因:1.资源有限 2.并发进程之间的推进顺序不当

死锁产生的必要条件:互斥条件、不剥夺条件、占有等待条件、环路等待条件

设信号量a=b=c=d=0

操作系统复习

操作系统复习

操作系统复习

操作系统复习

操作系统复习

银行家算法:在银行家算法中,若出现下述资源分配情况:

Process Allocation Need Available P0

0 0 3 2 0 0 1 2 1 6 2 2 P1

1 0 0 0 1 7 5 0 P

2 1

3 5

4 2 3

5

6 P3 0 0 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6

试问:

① 该状态是否安全?

② 若进程 P2 提出请求 Request( 1, 2, 2, 2 )后,系统能否将资源分配给它? 解:

现在对该时刻的状态进行安全分析: 由于Available 向量为(1,6,2,2),所以Work 向量初始化为(1,6,2,2)该时刻的安全性检查表如下:

操作系统复习

由于Request2(1,2,2,2)

操作系统复习

然后进行安全性检测,此时Available 为(0,4,0,0),所以Work 初始化为(0,4,0,0)。 此时的Work 小于任意的Need[i]向量,所以系统处于不安全状态,即认为不能分配资源(0,2,0)给P2。

五、用户程序处理过程:编辑――编译――链接――装入――运行阶段

◆ 内部碎片:在一个分区内部出现的碎片(即被浪费的空间)称做内部碎片。 ◆ 外部碎片:在所有分区之外新增的碎片称做外部碎片。

若作业A 的逻辑地址空间为11K ,还按刚才块的大小4K 划分,则可以分为几页? 11/4=2.75,2页多不到3页,把它按3页对待,编号为第0页、第1页、第2页。

如果给定的逻辑地址是A ,页面的大小为L ,则页号p 和页内地址w 可按下式求得:

p=INT[A/L],w=[A] MOD L

其中,INT 是向下整除的函数,MOD 是取余函数。 例如,设系统的页面大小为1KB,A=3456.

p=INT(3456/1024)=3,w= 3456 MOD 1024=384。

则逻辑地址3456就可以用数对(页号,页内地址)→(3,384)来表示。 分页存储管理:

某页表的内容如图所示,作业在地址空间所规定的页长为1KB ,对于CPU 所给出的有效地址:37390、40462,其对应的物理地址分别为:()、()。

操作系统复习

操作系统复习

分段式存储管理:

假设有下面的段表:

下面逻辑地址的物理地址分别是多少?

①[0,430];②[1,12];③[2,500]; ④[3,400]; ⑤[4,122]

操作系统复习

解:

①:649;②:2312;③:越界;④:1727;⑤:越界

虚拟存储器特征;虚拟性、对换性、多次性

页面置换算法:

最佳置换算法(OPT):其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。

先进先出(FIFO)算法:总是淘汰最先进入内存的页面,即选择在内存中停留时间最长(年龄最老)的一页予以淘汰。

最近最久未使用(LRU)置换算法:当需要置换一页时,选择在最近一段时间里最久没有使用过的页面予以淘汰。

考虑下面存储访问序列,该程序的大小为460字(以下数字均为十进制数字):

10、11、104、170、73、309、185、245、246、434、458、364

该页面的大小为100字,该程序的基本可用内存为200字,计算采用FIFO、LRU和OPT 置换算法的缺页次数。

解:

因为页面的大小为100字,该程序的基本可用内存为200字,即可用内存为2块。程序的存储访问序列可转换为如下页面访问序列:

1、1、

2、2、1、4、2、

3、3、5、5、4

采用FIFO、LRU和OPT置换算法的访问序列如下:

操作系统复习

由图可知FIFO算法的缺页次数为6次,LRU的缺页次数为7次,OPT的缺页次数为5次。

系统抖动:由于入页出页不当,导致频繁页面调入/调出或CPU时间用于交换而非执行进程指令的一种行为特征。

形成原因:多个进程剧烈竞争使用内存。

六、文件分类:

按用途分类:系统文件、用户文件、库文件

按文件性质:普通文件、目录文件、设备文件

按存取控制属性:执行、只读文件、读写文件

逻辑结构和物理结构

(1) 文件的逻辑结构。这是从用户观点出发所观察到的文件组织形式,是用户可以直接处理的数据及结构,它独立于文件的物理特性。

(2) 文件的物理结构。又称为文件的存储结构,是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关,而且与所采用的外存分配方式有关。

七、设备的分类

按传输速率分类:低速设备、中速设备、高速设备

按信息交换的单位分类:字符型设备、块设备

从资源分配角度进行划分:独占设备、共享设备、虚拟设备

按设备的从属关系分类:系统设备、用户设备

设备控制器的组成

(1) 设备控制器与处理器的接口

该接口用于实现CPU与设备控制器之间的通信。共有三类信号线:数据线、地址线和控制线。数据线通常与三类寄存器相连接。第一类是数据寄存器,在控制器中可以有一个或多个数据寄存器,它用于存放从设备送来的数据或从CPU和内存送来的数据;第二类是控制寄存器,用于存放从CPU送来的控制信息;第三类是状态寄存器,用于存放设备的状态信息。

(2) 设备控制器与设备的接口

在一个设备控制器上,可以连接一个或多个设备。因此,在控制器中便有一个或多个设备接口,一个接口连接一台设备。在每个接口中都存在数据、控制和状态三种类型的信号。控制器中的I/O逻辑根据处理器发来的地址信号去选择相应的设备接口。

(3) I/O逻辑

设备控制器中的I/O逻辑用于实现对设备的控制。它通过一组控制线与处理器交互,I/O逻辑接收处理器发送的控制命令并对其进行译码。当CPU要启动一个设备时,一方面将启动命令发送给控制器;另一方面又同时通过地址线把地址发送给控制器,由I/O逻辑对收到的地址进行译码,再根据所译出的命令对所选择设备进行控制。

(4) 寄存器

为了实现与CPU通信,每个控制器都要有几个寄存器,即控制寄存器、状态寄存器和数据寄存器。

磁盘访问时间:

寻道时间是磁臂将磁头移动到包含目标扇区的柱面时间。

寻道时间Ts:Ts = m ×n + s

s为启动磁臂时间m是常数,与磁盘驱动器速度有关n为磁头移动的磁道条数

旋转延迟时间是磁盘需要将目标扇区转动到磁头下的时间。

旋转延迟时间Tr:Tr =

r为磁盘的转速

r* 2 1

数据处理时间是指从磁盘读出数据或向磁盘写入数据的时间。

数据传输时间Tt : r 为磁盘的转速 N 为一条磁道上的字节数 b 为每次读写的字节数 磁盘调度

先来先服务(FCFS) 例如,有8个进程先后提出磁盘I/O 请求,其I/O 对各个柱面上块的请求顺序如下:56,130,23,110,75,180,36,68。

如果磁头开始位于100,那么它将从100移到56,接着再移到130,23,110,75,180,36,最后到68,总的磁头移动为628柱面 。

操作系统复习

操作系统复习

rN

b Tt

访问队列:56、130、23、110、75、180、36、68. 磁头开始于100.

访问队列:56、130、23、110、75、180、36、68. 磁头开始于100.

●SCAN调度优先考虑磁头当前的移动方向

当磁头正在由里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这样由里向外访问,直至再无更外的磁道需要访问时,才将磁臂换向为由外向里移动,如此循环,磁头在整个磁盘上来回扫描。

访问队列:56、130、23、110、75、180、36、68. 磁头开始于100.

操作系统复习

●C-SCAN算法

磁头只是自里向外移动,当磁头移到最外要访问的磁道后,磁头立即返回到最里的欲访问的磁道,亦即将最小磁道号紧接着最大磁道号构成循环,进行循环扫描。

访问队列:56、130、23、110、75、180、36、68. 磁头开始于100.

操作系统复习