操作系统复习alldocx.docx

操作系统复习alldocx.docx

《操作系统复习alldocx.docx》由会员分享，可在线阅读，更多相关《操作系统复习alldocx.docx（14页珍藏版）》请在冰点文库上搜索。

操作系统复习alldocx

操作系统复习

第一章

考点：

操作系统的定义，基本特性以及主耍功能（选择、填空）

1•定义：

操作系统是一组控制和管理计算机硬件和软件资源、合理地対各类作业进行调度、以及方便用户使用的程序集合。

2.基本特性：

并发性（最重要特征）、共享性、虚拟性、异步性

所谓共享是指系统屮的资源可供内存屮多个并发执行的进程（线程）共同使用。

资源属性的不同，对资源共享的方式也不同。

实现资源共享的两种方式：

（1）互斥共享方式

⑵同吋访问方式

3.主耍功能：

处理器管理、存储器管理、设备管理、文件管理、用户Z间的接口

第二章

考点：

进程、程序、线程的概念（简答）；

PCB结构、进程状态（三种基木状态）；

进程同步和互斥的含义（选择，填空）；

临界资源、临界区、以及同步机制原则；

信号量P或V操作时的信号量值的变化；

经典进程同步问题（综合题）

1•进程的定义：

进程是进程实体的运行过程（程序在并发环境中的执行过程），是系统进行资源分配和调度的基本单位。

进程的特征

动态性并发性独立性异步性

进程结构

PCB进程控制块->动态特征的集中反映

程序段描述要完成的功能

数据段->操作对象及工作区

2.程序的定义：

是为实现特定FI标或解决特定问题而用计算机语言编写的命令序列的集合。

3.线程的定义：

它是一个基本的CPU执行单元，也是程序执行流的最小单元，rtl线程ID、程序计数器、寄存器集合和堆栈组成。

线程是进程中的一个实体，一个进程中包含多个线程,他们可以利用进程所拥有的资源，是被系统独立调度和分派的基本单位。

4.PCB（进程控制块）结构：

为了描述和控制进程的运行，系统为每个进程定义了一个数据结构-进程控制块，它是进程实体的一部分，是操作系统屮最重要的记录型数据结构。

在进程控制块中，主耍包含四方面信息：

进程标识符、处理机状态、进程调度信息、进程控制信息。

5.进程三种基木状态：

就绪状态、执行状态、阻塞状态

就绪执行执行・・>阻塞阻塞・・>就绪执行->就绪

&进程的同步：

进程间共同完成一项任务时直接发生相互作用的关系。

同步进程间具有合作关系；

在执行吋间上必须按照一定的顺序协调进行；

7.进程的互斥：

并发执疔的多个进程由于竞争同一资源而产生的相互排斥的关系。

进程间相互合作的关系是同步关系，而対资源争用的关系是互斥关系。

若T进程使用同一临界资源时必须互斥执行。

8.临界资源：

一次仅允许一个进程使用的共享资源如：

打印机、磁带机、表格

9•临界区：

在每个进程中访问临界资源的那段程序;进程必须互斥进入临界区；

10.同步机制原则:

空闲让进、忙则等待、有限等待、让权等待

□•信号量P操作（wait）>V操作（signal）时时的信号量值的变化:

Wait操作：

申请一个单位资源

procedurewait（S）

varS:

semaphore;/*定义记录型信号量*/

begin

S.value:

=S.value

/*如果资源不足则阻塞该进程*/

ifS.value<0thenblock（S.L）;

end

Signal操作：

释放一个单位资源

procedureSignal（S）

varS:

semaphore;/*定义记录型信号量*/

begin

S.value:

=S.value+l;

厂如果阻塞队列中冇进程，则唤醒该进程*/

ifS.valueWOthenwakeup（S.L）;

end

S.value20时,代表系统中可用资源的数目;

S.value<0时，绝对值表示已阻塞的进程数量（等待使用资源的进程个数）；

S.value的初始值为1时：

只允许一个进程访问临界资源，是互斥信号量；

12.经典进程同步问题

前趋图是一个有向无循环图，用于描述进程之间执行的前示关系。

利用p、v操作实现进程同步（前驱图）

51a=x+y;sl->s2

52b=a+3;

A二0（信号量）

Plp2

SI；P（A）;

V（A）;S2;

第三章

考点：

作业经历的三级调度

各种调度算法基本思想，计算周转时间，平均周转时间

死锁概念、产生原因以及死锁的必要条件，死锁的预防、避免处理方法（简答，填空）银行家算法（作业）

1.处理机调度的层次（三级调度）：

高级调度（创建）、低级调度（找进程执行）、小级调度（激活挂起）

2.短作业（进程）优先调度算法基本思想：

从后备队列屮选择一个或多个若干运行时间最短的作业调入内存运行。

3.高优先权优先调度算法基本思想：

从后备队列中选择优先级高的的作业调入内存运行。

4.死锁的概念：

多个进程在运行过程中因竟争资源而造成的一种僵局。

各并发进程彼此等待对方拥有的资源，且在得到对■方资源前不释放口己的资源。

5.死锁产生原因：

竞争资源。

资源（打印机、公用队列）数日不能满足进程的需要；

进程间推进顺序非法。

进程在运行过程中，请求和释放资源的顺序不当，也同样会导致进程死锁。

竞争资源引起死锁：

可剥夺和非可剥夺性资源

竞争非可剥夺性资源

竞争临时性资源

6.产生死锁的必要条件：

（1）互斥条件

⑵请求和保持条件

（3）不剥夺条件

⑷坏路等待条件

7•处理死锁的基本方法

⑴预防死锁。

-》摒弃“请求和保护”条件

互斥条件（错）

请求和保持条件（对）

不剥夺条件（对）

环路等待条件（对）

预防死锁的方法

1•摒弃“请求和保持”条件解决方案（and型信号罐）

AND型信号量

基本思想：

将进程在整个运行中需要的所有资源，一次性全部分配给进程，待进程使用完后—•起释放。

2.摒弃“不剥夺”条件解决方案（强制回收）

3.摒弃“环路等待”条件解决方案（资源按序分配策略）

⑵避免死锁。

-》银行家算法

⑶检测死锁。

⑷解除死锁。

-》剥夺资源

死锁的解除常采用的两种方法：

剥夺资源（基木方法）

撤销进程

系统不发生死锁，满足不等式：

n（k-l）+l^m

（n是进程个数，k是进程所需垠大资源数，m是系统提供资源数）

8•银行家算法

（1）可利用资源向量Available；

⑵最人需求矩阵Max；

⑶分配矩阵Allocation；

（4）需求矩阵Need；

Need[i,j]=Max[i,j]-Allocation[ij]

设Request!

是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。

Pi发出资源请求示，按下述步骤进行检杏：

⑴如果Requesti[j]^Need[iJ],转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Requesti[j]

（3）系统试探着把资源分配给进程Pi,并修改下而数据结构中的数值：

Available[j]:

=Available[j]-Requesti[j]

Allocation[izj]:

=Allocation[ij]+Requesti[j];

Need[izj]:

=Need[iJ]-Requesti[j];

（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

若安全,才将资源分配给进程Pi；否则，将木次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法

（1）设置两个向量:

1工作向MWork:

系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:

=Available;

2Finish:

系统是否有足够的资源分配给进程，便Z运行完成。

开始吋先做Finish[i]:

=false;当有足够资源分配给进程时，再令Finish[i]:

=true<>

⑵从进程集合屮找到满足卜-述条件的进程：

1Finish[i]=false;

2Need[i,j]WWork[j]；

若找到，执行步骤（3）,否则，执行步骤（4）。

⑶当进程Pi获得资源后，可顺利执行，直至完成，

并释放出分配给它的资源，故应执行：

Work[j]:

=Work[i]+Allocation[i,j];

Finish[i]:

=true;gotostep2;

⑷如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

对待死锁，一般应考虑死锁的预防、避免、检测和解除。

典型的银行家算法属于避免死锁,

摒弃“请求和保护”条件属于预防死锁，而剥夺资源是解除死锁的基本方法。

第四章

考点：

动态分区分配思想、算法、回收

基本分页系统的地址转换过程

基木分段系统的地址转换过程

段页式存储管理系统的原理

虚拟存储的概念

页面置换算法的原理（OPT、FIFO、LRU）

1.动态分区分配思想：

当有进程需分配，以进程为单位在内存屮找到相等人小的空间进行切割。

2•动态分区分配算法：

首次适应算法FF（每次从头开始）

循环首次适应算法（找到下次的位置）

最佳适应算法（容虽以从小到大顺序）

最坏适应算法（容最以从大到小顺序）

快速适应算法（分类搜索）

3.回收内存

情况1：

与插入点的前一个空闲区F1相邻接

情况2：

与插入点的后一个空闲区F1和邻接

情况3：

同时与插入点的前、后两个空闲区相邻接

情况4：

既不与F1邻接，又不与F2邻接

4.基本分页系统的地址转换过程

分页地址中的地址结构如F:

3112110

页号P

位移量W

位移量W乂称页内地址：

每页大小:

212=4KB

地址空间中最多有：

22O=1M页

逻辑地址A页而人小L页号P页内地址d

■■

A

P=INT-—

L

■■

d=\A]MODL

5•基木分段系统的地址转换过程

3116150

段号

段内地址

允许一个作业最多有64K个段

每个段的最大长度为64KB

6.段页式存储管理系统的原理

分段和分页原理结合；

先将用户进程分成若干个段；

再把每个段分成若干个页，并为每个段赋予一个段名;

段号⑸

段内页号（P）

页内地址（W）

作业地址空间和地址结构

三次访问内存

第一次访问段表，从中取得页表起始地址；

笫二次访问页表，从屮取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；

第三次真正访问数据或指令；

7.焜拟存储的概念（局部性原理）

虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

虚拟存储器的实现方法

建立在离散分配的存储管理方式基础上

分页请求系统

请求分段系统

8.页面置换算法的原理（OPT、FIFO、LRU）

最佳置换算法（OPT）->离得最远淘汰

最住證换算法选择的被淘汰页面，将是以后永不使用的，或许是在最长（未來川寸间内不再被

访问的页面；

先进先出（FIFO）页面置换算法・・>最先进内存的淘汰

淘汰最先进入内存的页面，即选择在内存中驻留吋间最久的页面予以淘汰。

最近最久未使用（LRU）置换算法左边最远淘汰

由于无法预测各页面将來的使丿lj情况，只能利用“最近的过去”作为“最近的我将來”的近似，选择最近最久未使用的页而了以淘汰；

第五章

考点：

I/O控制方式

缓冲管理种类

Spooling技术

磁盘调度算法（FCFS、SSTF、SCAN、CSCAN）

1.1/0控制方式

程序I/O方式

CPU要不断地测试I/O设备的状态，因为在CPU中无中断机构，使I/O设备无法向CPU报告它已完成了一个字符的输入操作。

中断驱动I/O控制方式

在I/O设备输入每个数据的过程屮，无须CPU干预，可使CPU与I/O设备并行工作。

仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理。

使CPU和I/O设备都处于忙碌状态，从而提高了整个系统的资源利用率及吞吐最。

直接存储器访问（DMA）I/O控制方式

数据传输的基木单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块；

数据传送是从设备直接送入内存的，或者相反；

仅在传送一个或多个数据块的开始和结束吋，才需CPU干预，整块数据的传送是在控制器的控制下完成。

I/O通道控制方式

I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读（或

写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预。

2.缓冲管理种类

单缓冲

用户发出I/O请求；

OS在主存中分配一缓冲区用于暂存用户输入的一行数据；

输入期间，用户进程被挂起以等待数据输入完毕；

输出时，用户进程将一行数据输入到缓冲区示，继续执行处理，当户用已有第二行数据输出时，如果第一行数据尚未被提取完毕，则用户进程阻塞；

双缓冲

也称缓冲对换

输入时，将数据送入第一缓冲区，装满后便转向第二缓冲区。

同时，从第一缓冲区屮移出数据，并送入用户进程，接着由CPU对数据进行计算；

双缓冲，系统处理一块数据的吋间可以粗略地认为是Max（C,T）o

如果C

如果C>T,则可使CPU不必等待设备输入；

循环缓冲

多个缓冲区；

多个指针；

缓冲池

于既可用于输入又可用于输出的公用缓冲池，其中至少应含有以下三种类型的缓冲区：

1空（闲）缓冲区；

2装满输入数据的缓冲区；

3装满输岀数据的缓冲区。

3.Spooling技术

是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。

共享打卬机

当川户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事：

1山输出进程在输出井中为之屮请一个空闲磁盘块区，并将要打印的数据送入其中；

2输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打卬队列上。

4.磁盘调度算法（FCFS、SSTF、SCAN、CSCAN）

先來先服务（FCFS）算法

按访问请求到达的先后次序服务

最短寻道时间优先（SSTF）算法

优先选择距当而磁头最近的访问请求进行服务，主要考虑寻道优先

扫描（SCAN）算法

当设备无访问请求时，磁头不动；

当有访问请求时，磁头按一个方向移动，在移动过程中対遇到的访问请求进行服务；

然后判断该方向上是否还有访问请求，如果有则继续扫描；

否则改变移动方向，并为经过的访问请求服务，如此反复。

循环扫描（CSCAN）算法

总是从0号柱面开始向里扫描；

按照各自所要访问的柱面位置的次序去选择访问者；

移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号林面;返回时不为任何的等待访问者服务；

返回后可再次进行扫描。