计算机操作系统1-7章复习概念

第一章 操作系统引论

1.1操作系统的目标与作用

操作系统的目标：①方便性②有效性：有效性包含的第一层含义是提高系统资源的利用率,第二层含义是，提高系统吞吐量③可扩充性④开放性

用户实现与操作系统通信的三种方式：①命令方式②系统调用③图标——窗口

操作系统会管理处理机、存储器、I/O设备以及文件，处理机管理是应用于分配和控制处理机；存储器管理主要负责内存的分配与回收；I/O设备管理是负责I/O设备的分配与操纵；文件管理是用于实现对文件的存取、共享和保护。 1.2几种操作系统

①单道批处理系统，内存中只允许存放一个作业，当前正在运行的作业驻留内存，执行顺序是先进先出。在单道批处理系统中，一个作业单独进入内存并独占系统资源，直到运行结束后下一个作业才能进入内存，当进行输入操作时，cpu处于等待状态。单道批处理系统的缺点是系统中的资源得不到充分的利用。

②多道批处理系统，用户所提交的作业先存放在外存上，并排成一个队列成为“后备队列”。然后由作业调度程序按一定的算法，从后备队列中选择若干个作业调入内存，使它们共享cpu和系统中各种资源。多道批处理系统的优点有：1.资源利用率高2.系统吞吐量大缺点有：1.平均周转时间长2.无交互能力

③分时系统，是指一台主机上连接多个带有显示器和键盘的终端，同事允许多个用户通过主机的终端，以交互方式使用计算机，共享主机中的资源。分时系统的特性为：1.多路性2.独立性3.及时性4.交互性

④实时系统，是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间。实时系统的特征有：1.多路性2.独立性3.及时性4.交互性5.可靠性

1.3操作系统的基本特征

①并发，是指一个时间段中有几个进程都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，担任一个时刻点上只有一个进程在处理机上运行。这里要和并行加以区分，并行是两个或多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔内发生。

进程，是指在做系统中能独立运行并作为资源分配的基本单位

②共享，是指系统中的资源可供内存这中多个并发执行的进程共同使用。由于资源的属性不同，所以多个进程对资源的共享方式也不同，可以分为互斥共享和同时访问。

③虚拟，是指通过技术（spooling技术）把一个物理实体变成若干个逻辑上的对应物。

④异步，是指进程以人们不可预知的速度向前推进（和线程的异步性类似） 1.4操作系统的主要功能

处理机管理功能：1.进程控制2.进程同步3.进程通信4.调度（作业调度，进程调度）

存储器管理功能：1.内存分配2.内存保护3.地址映射4.内存扩充 设备管理功能：1.缓冲管理2.设备分配3.设备处理

文件管理功能：1.文件存储空间管理2.目录管理3.文件读写管理与保护

第二章 进程的描述和控制 2.1前趋图和程序的执行

前趋图的画法（略） ①程序顺序执行时特征：

1.顺序性：指处理机严格按照程序所规定的顺序执行，即每一操作必须在下一个操作开始之前结束；

2.封闭性：在程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态只有本程序才能改变它，程序一旦开始执行，其中执行结果不受外界因素影响；

3.可再现性：这种只要称必须执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是”走走停停”地执行，都可获得相同的结果。

②程序并发执行时的特征：

1.间断性2.失去封闭性3.不可再现性

2.2进程的描述

进程的定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。

进程的特征：①动态性；②并发性；③独立性；④异步性。

进程的三种基本状态：①就绪态ready；②执行态running；③阻塞态block 三种基本状态的转换： 许可 就绪 创建

时间片完 I/O完成 进程调度

释放 执行 终止 I/O请求 阻塞

进程控制块pcb的作用：

① 作为独立运行基本单位的标志； ② 能实现间断性与运行方式； ③ 提供进程管理所需要的信息； ④ 提供进程调度所需要的信息； ⑤ 实现与其他进程的同步与通信； 进程控制块中的信息：

② 进程标识符（外部标识符，内部标识符）；

②处理机状态（通用寄存器，指令寄存器，程序状态字psw，用户栈指

针）；

③ 进程调度信息（进程状态，进程优先级，其他信息，事件）； ④ 进程控制信息（程序和数据的地址，进程同步和通信机制，资源清单，链接指针）；

进程控制块的组织方式：

①线性方式；②链接方式；③索引方式；

2.3进程控制

OS内核的作用：

①保护内核中的程序，防止其遭受其他应用的破坏；②提高OS的运行效率；

处理机的执行状态：

①系统态（管态）：具有较高的特权，能执行一切的指令，访问所有的寄存器和存储区，传统的OS都在系统态与运行；②用户态（目态）：具有较低的特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区； 原语：由若干条指令组成的，用于完成一定功能的过程。原语的操作称为原子操作，一个原子操作中的所有动作要么全做，要么全不做（类似于） 2.4进程同步

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

临界区：每个进程访问临界资源的那段代码。每次只允许一个进程进入临界区，进入后不允许其他进程进入；

同步机制应遵循的规则：①空闲让进；②忙则等待；③有限等待；④让权等待；

信号量机制

①整型信号量：信号量S是一个整数，S大于等于零是代表可供并发进程使用的资源实体数，当S小于零时则表示正在等待使用临界区的进程数，它仅能被两个原子操作来访问，分别是wait(S)和signal(S)，它们被称为P、V原语，它们的代码如下：

wait(S){ signal(S){

while(S<=0) S++;

; } S--; }

②记录型信号量：记录型信号量是在整型信号量的基础上，添加一个进程链表指针list，用于链接所有等待进程，它所包含的数据项可描述如下：

typedef struct{

int value;

struct process_control_block *list; }semaphore;

相应的，wait(S)和signal(S)的代码如下：

wait(semaphore *S){ signal(semaphore *S){

S->value--; S->value++; if(S-->value<0) if(S->value<=0)

block(S->list); wakeup(S->list);

} }

③AND型信号量：将进程在整个运行过程中需要要的所有资源，一次性全部地分配给进程，带进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。就是在wait操作中增加了一个“AND”条件，故称为AND同步。两个操作的代码如下：

Swait(S1，S2，...，Sn）{

while(TRUE){

if(Si>=1&&...&&Sn>=1){

for(i=1;i<=n;i++)

Si--; break;} else{

place the process in the waiting queue associated with the first Si found with

Si<1,and set the program count of this process to the beginning of Swait operation } } }

Ssignal(S1，S2，...，Sn）{

while(TRUE){

for(i=1;i<=n;i++){

Si++; Remove all the process waiting in the queue associated with Si into the ready queue } } }

④信号量集：对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请和释放。进程对信号量Si的测试值不再是1，而是该资源的分配下限值ti，即要求Si>=ti，否则不予分配。一旦允许分配，进程对该资源的需求值为di，即表示资源占用量，进行Si=Si-di操作，而不是简单的Si=Si-1。由此形成一般化信号量机制。对应的Swait和Ssignal代码如下：

Swait(S1,t1,d1,......,Sn,tn,dn); Ssignal(S1,d1,......,Sn,dn); 信号量的应用：

①利用信号量实现进程互斥；②利用信号量实现前趋关系；

管程：系统中的各个硬件资源和软件资源均可以用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。利用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据结构实施的操作定义为一组过程。代表共享资源的数据结构，以及由对该数据结构实施操作的一组过程做组成的资源管理程序，共同构成了一个操守做

系统的资源管理模块，我们称之为管程。

wait()：挂起调用进程并释放管程，直至另一进程正在条件变量上执行signal()

signal()：如果有其他他的进程因对条件变量执行wait()而被挂起，便释放之。如果没有 进程等待，这信号被忽略，不保存。

管程的语法描述如下：

Monitor monitor_name{ //管程名

share variable declarations; //共享变量说明 cond declaration; //条件变量说明 public: //能被进程调用的过程

void P1(......) //对数据结构操作的过程 {......}

void P2(......) {.......} ......

{ //管程主体

initialization code; //初始化代码 ...... } }

管程的特性：①模块化②抽象数据类型③信息掩蔽 管程和进程的不同：

①虽然二者都定义了数据结构，但进程定义的是私有数据结构PCB，过程定义的是公共数据结构；②二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关操作，而管程主 要是进行同步操作和初始化操作；③设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享紫云园的互斥使 用问题；④进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样 被调用，因而管程为被动工作方式，进程则为主动工作方式；⑤进程之间能并发执行，而管程择不能与其调用者并发；⑥进程具有动态性，由“创建”而诞生，由“撤销”而消亡，而管程则是操作系统中的 一个资源管理模块，工进程调用； 2.5经典进程同步问题

生产者——消费者问题

利用记录型信号量 利用AND型信号量

利用管程 哲学家进餐问题

利用记录型信号量 利用AND型信号量 读者——写者问题

利用记录型信号量 利用信号量集机制

2.6进程通信

进程通信的类型 ①共享存储器系统

1.基于共享数据结构的通信方式：要求进程公用某些数据结构，借意义实现进程间的信息交换

2.机遇与共享存储区的通信方式：为了传输大量数据，在内存中话术了一块共享存储区域，进程可以通过对该共享区的读或写交换信息，实现通信。 ②管道通信系统； ③消息传递系统；

1.直接通信方式：是指发送进程利用OS所提供的发送原语，直接把消息发送给目标进程

2.间接通信方式：是指发送和接受进程，都通过共享中间实体的方式进行消息的接收和发送，完成进程间的通信 第三章 处理机调度死锁

3.1处理机调度的层次和调度算法的目标

处理及调度的层次：

①高级调度：高级调度的对象是作业，其主要功能是根据某种算法，决定将外存上处于 后背队列中的哪几个作业调入内存，为他们创建进程、分配必要的资源，并将它们放入 就绪队列

②低级调度：调度的对象是进程，其主要功能是，根据某种算法，决定就绪队列中的哪 个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。

③中级调度：引入中级调度的主要目的是，提高内存利用率和系统吞吐量。把那些暂时 不能运行的进程，调至外存等待，此时进程的状态成为就绪驻外存状态

处理机调度算法的目标：

①处理机调度算法的共同目标： 1.提高资源利用率； 2.公平性 3.平衡性

4.策略强制执行 ②批处理系统的目标 1.平均周转时间短 2.系统吞吐量高 3.处理机利用率高 ③分时系统的目标 1.响应时间快 2.均衡性

④实施系统的目标 1.截止时间的保证 2.可预测性

cpu利用率=cpu有效工作时间÷（cpu有效工作时间+cpu空闲等待时间） 周转时间：对于一个进程来说，一个重要的指标是它实行所需要的时间。从进程提交到 进程完成时间间隔为周转时间，也就是等待进入内存的时间，在就绪队列中等待的时间， 在cpu中执行的时间和I/O操作的时间的总和 3.2作业与作业调度

作业：正在执行的一个或多个相关的进程被称为作业

作业步：一般情况下，一个作业可划分成若干个部分，每个部分称为有一个作业步。

作业控制块（JBC）：作业在系统中存在的标志，保存了系统对作业进行管理和调度所 需的全部信息

作业运行的三个状态：后备状态、运行状态、完成状态 作业运行的三个阶段：收容阶段、运行阶段、完成阶段

先来先服务算法（FCFS）：每次调度室从就绪的进程队列中选择有一个最先进入该队 列的进程，为之分配处理机，使其投入运行

短作业优先算法（SJF）：以作业的长短来计算优先级，作业越短，优先级越高。作业 的长短是根据作业所要求的运行时间来衡量的

短作业优先算法的缺点：①必须预知作业的运行时间②对长作业非常不利③无法实现人 机交互④无法保证紧迫性作业得到及时处理

优先级调度算法（PSA）：先调用优先级高的进程，优先级体现了进程的紧迫程度

高响应比优先调度算法(HRRN)：为每个做作业引入一个动态优先级，即优先级是可以 改变的，令它随等待时间延长而增加，这将使作业的优先级在等待期间不断地增加，等 到足够的时间后，必然有机会获得处理机。

高响应比优先调度算法优先级=（等待时间+要求服务时间）÷要求服务时间 3.3进程调度

进程调度的任务：

①保存处理机的现场信息 ②按某种算法选取进程 ③把处理器分配给进程 进程调度的机制

①排队器：事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列

②分派器：一句进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分排 器到新选出进程的上下文切换，将处理机分配给新选出的进程

③上下文切换器 进程调度的方式：

①非抢占方式：一旦把处理机分配给某进程后，就一直让它运行下去，绝不会因为时钟 中断或任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事 件而被阻塞时，才把处理机分配给其它进程

②抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该 进程的处理机重新分配给另一进程

抢占方式的原则：

①优先权原则②短进程优先原则③时间片原则

轮转调度算法：每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时 间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果 进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护 一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。

优先级调度算法：

①非抢占式优先级调度算法 ②抢占式优先级调度算法 优先级的类型： ①静态优先级 ②动态优先级 3.4实时调度

最早截止时间优先算法：根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高。

最低松弛度优先算法：根据任务的紧急（或松弛）程度决定优先级，任务紧急程度越高，其优先级越高 3.5死锁

死锁定义：如果一组进程中的每一个进程都在等待仅有该组进程中的其它进程才能引发的事件，那么该组进程是死锁的

引起死锁的原因：

①竞争不可抢占性资源引起死锁 ②竞争可消耗资源引起死锁 ③进程推进顺序不当引起死锁 死锁产生的必要条件：

①互斥条件，进程对所分配到的资源进行排他性使用。

②请求和保持条件，进程已经保持了至少一个在资源，但又提出了新的资源请求，而该 资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放

③不可抢占条件，进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时 由自己释放

④循环等待条件，在发生死锁是，必然存在一个进程和资源的循环链 3.6预防死锁

①破坏“请求和保持”条件 ②破坏“不可抢占”条件 ③破坏“循坏等待”条件 3.7避免死锁

①安全状态：是指系统能按某种进程推进顺序为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大要求，是每个进程都可以顺利地完成。此时这个序列称为安全序列，如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

②利用银行家算法避免死锁：每个进程在进入系统时，它必须申明在运行过程工，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的

资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。

银行家算法的数据结构：

①可利用资源向量Available：是个含有m个元素的数组，其中的每一个元素代表一类 可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。

②最大需求矩阵Max：这是个n×m的矩阵，它定义了系统中n个进程中的每个进程对 m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

③分配矩阵Allocation：也是n×m的矩阵，它定义了系统中每一类资源当前已分配给 每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目 为K。

④需求矩阵Need：这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。 如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

上述三个矩阵满足以下关系：

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

银行家算法的描述：

设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。

(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。 (3)系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i]; NEED[cusneed][i]-=REQUEST[cusneed][i];

(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原 状，进程等待。

安全性检查算法：

(1)设置工作向量Work，它表示系统可供他提供给进程继续运行所需的各类资源数目， 它含有m个元素，在执行开始时，赋初值Work=Available；设置Finish向量表示系统 是否具有足够的资源分配给进程，是指运行完成，赋初值Finish[i]=false；当有足够资 源分配给进程时，再令Finish[i]=true。

(2)从进程集合中找到一个能满足下述条件的进程：

①Finish[]==false; ②Need[i,j]<=Work[j]；

若找到，执行（3），否则执行（4）

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work[j]=Work[j]+Allocation[i,j]; Finish[i]=true; GOTO 2

(4)如所有的进程Finish[i]= true，则表示安全；否则系统不安全。

银行家算法考计算题

具体例子课本P113(第三版P110)

3.8死锁的检测与解除

死锁的解除：终止进程：

终止所有的进程 逐个终止进程

第四章 存储器管理

4.1存储器的层次结构

存储器的多层结构：

由上至下，容量越来越大，速度越来越慢

寄存器：寄存器是中央处理器内的组成部分，它是有限存储容量的高速存储部件，可用来暂存指令、数据和地址

高速缓存是存在于主存和寄存器之间的以及存储器主要用于备份主存中较常用的数据，以减少处理机对主存的访问次数，这样可以大幅度地提高程序执行的速度。

主存：用于保存进程运行时的程序和数据。

磁盘缓存：用于暂时存放频繁使用的一部分磁盘数据和信息。 4.2程序的装入和链接

程序运行的三个步骤： ①编译，有编译程序对用户源程序进行编译，形成若干个目标模块；②链接，由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块；③装入，有装入程序将装入模块装入内存；

程序装入的方式：

①绝对装入方式，用户程序经编译后产生绝对地址的目标代码。②可重定位装入方式，目标模块的启示地址通常是从0开始的，程序中的其它地址也都 是相对于起始地址计算的。根据内存的当前情况，将装入模块装入到内存的适当位置。地址变换通常是在装入是依次完成的，以后不再改变，所以是静态重定位。③动态运行装入方式，程序在运行过程中在内存的位置可能改变，装入程序包装入模块 装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换 推迟到程序真正要执行时才进行

程序链接的方式：

①静态链接方式，在程序运行之前，先将各个目标模块及他们所需要的库函数链接成一 个完整的装配模块，以后不再拆开。②装入时动态链接，在目标模块装入内存时，边装入边链接。即在装入一个目标模块时， 若发现一个外部模

本文来源：https://www.bwwdw.com/article/6mkt.html