计算机操作系统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开始的，程序中的其它地址也都 是相对于起始地址计算的。根据内存的当前情况，将装入模块装入到内存的适当位置。地址变换通常是在装入是依次完成的，以后不再改变，所以是静态重定位。③动态运行装入方式，程序在运行过程中在内存的位置可能改变，装入程序包装入模块 装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换 推迟到程序真正要执行时才进行

程序链接的方式：

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

块调用，即引起装入程序去找出相应的外部模块，并将它装入内存以及修改目标模块中的相对地址。③运行时动态链接，将某些目标模块的链接，推迟到执行时才进行。即在执行过程中， 若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并把它 链接到调用者模块上。

4.3连续分配存储管理方式

基于顺序搜索的动态分区分配算法：

①首次适应算法，从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲 区分配给作业。②循环首次适应算法，在分配内存空间时，不再每次从表头开始查找，而是从上次找到 空闲区的下一个空闲开始查找，知道找到第一个能满足要求的空闲区位置，并从中划出 一块玉请求大小相等的内存空间分配给作业。③最佳适应算法，从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区。为 适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开 始查找到第一个满足要求的自由分区分配。④最坏适应算法，扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业 使用。该算法要求将所有空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时 只要看第一个分区是否能满足作业要求。 4.5分页存储管理方式

页面：分页存储试讲一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始。

物理块：把内存空间分成与页面相同大小的若干存储块，称为物理块，加以编号，从0#号开始

在为进程分配内存时，以块为单位将进程中若干个页分别装入到多个可以不相邻接的物理块中。

地址结构：包含两个部分，前一部分为页号P，后一部分为位偏移量W，即页内地址。对于某特定机器，其地址结构是一定。若给定一个逻辑地址空间中的地址为A，页面大小为L，则页面号P和页内地址d可以按下式计算出：

P=int(A/L) d=A% L

页表：在分页系统，允许将进程到的各个页离散地存储在内存不同的物理块中，为保证系统能在内存中找到每个页面所对应的物理块，系统为每个进程建立了一张页面映像表，简称页表。

地址变换机构：

①基本的地址变换机构，页表的功能可以由一组专门的寄存器来实现。一个页表项用一个寄存器。由于寄存器具有较高的访问速度，因而有利于提高地址变换的速度；但由于寄存器成本较高，且大多数现代计算机的页表又可能很大，使页表项的总数可达几千甚至几十万个，显然这些页表项不可能都用寄存器来实现，因此，页表大多驻留在内存中。在系统中只设置一个页表寄存器PTR(Page-Table Register)，在其中存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址(相对地址)分为页号页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。左图示出了分页系统的地址变换机构。

②具有快表的地址变换机构，由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这种方式将使计算机的处理速度降低近1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”，在IBM系统中又取名为TLB(Translation Lookaside Buffer)，用以存放当前访问的那些页表项。此时的地址变换过程是：在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则OS必须找到一个老的且已被认为不再需要的页表项，将它换出。右图示出了具有快表的地址变换机构。

4.6分段存储管理方式

分段式存储管理方式引入的目的： ①方便编程：按逻辑关系分为若干个段，每个段从0编址，并有名字和长度，访问的逻辑地址由段名和段内偏移量决定。②信息共享：共享是以信息为逻辑单位，页是存储信息的物理单位，段却是信息的逻辑单位。③信息保护：保护也是信息为逻辑单位。④动态链接：动态链接以段为单位。⑤动态增长：实际应用中，某些段（数据段）会不断增长，前面的存储管理方法均难以 实现。

分段：在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。通常用一个段号来代替段名，每个段都从0开始编制，并采用一段连续的地址空间。

段表：在分段式存储管理系统中，为每个分段分配了一个连续的分区，进程中各个段离散地装入内存中不同分区，系统为每个进程建立一张段映射表，简称段表

地址变换机构

目的 信息单位 大小 内存分配单位 作业地址间 优点 页式存储管理 实现非连续分配,解决碎片问题 页（物理单位） 固定（由系统定） 页 一维 有效解决了碎片问题 有效提高内存的利用率 段式存储管理 更好满足用户需要 段（逻辑单位） 不定（由用户程序定） 段 二维 更好地实现数据共享与保护段长可动态增长 便于动态链接 段页式存储管理方式

基本原理：段页式存储管理是分段和分页原理的结合，即先将用户程序分成若干个段（段 式），并为每一个段赋一个段名，再把每个段分成若干个页（页式）。其地址结构由段号、 段内页号、及页内位移三部分所组成。

地址变换：用段号与段寄存器中的段长进行比较，若小于段长则利用段表始址和段号找 出该段页表的始址,(否则越界中断)， 再用逻辑地址中的段内页号在页表中找到相应的 块号，最后与页内位移形成物理地址。

第五章 虚拟存储器

5.1虚拟存储器概述

常规存储器管理方式的特征：

①一次性：作业在运行前需一次性地全部装入内存。

②驻留性：作业装入内存后，便一直驻留内存，直至作业运行结束。

局部性原理：指程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限 于某个部分，相应地，它所访问的存储空间也局限于某个区域。局部性又表现为时间局 部性(由于大量的循环操作，某指令或数据被访问后，则不久可能会被再次访问)和空间 局部性（如顺序执行，指程序在一段时间内访问的地址，可能集中在一定的范围之内）。

虚拟存储器的定义：是指仅把作业的一部分装入内存便可运行作业的存储管理系统，它 具有请求页调入功能和页置换功能，能从逻辑上对内存容量进行扩充，其逻辑容量由外 存容量和内存容量之和决定，其运行速度接近于内存，成本接近于外存。

虚拟存储器的特征：①多次性②对换性③虚拟性

5.3页面置换算法（计算题）

①最佳置换算法（无法实现）

②先进先出置换算法：置换先进的物理块

③最近未使用和最少使用置换算法：置换最近未使用和最少使用的物理块 5.4“抖动”与工作集

抖动，同事在系统中运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺职业调入内存。

第六章 输入输出系统

6.1 I/O系统的功能、模型和接口

I/O系统的基本功能：①隐藏物理设备的细节②与物理设备的无关性③提高处理机和I/O设备的利用率④对I/O设备进行控制⑤确保对设备的正确共享⑥错误处理

I/O设备的层次结构：①用户层I/O软件②设备独立性软件③设备驱动程序④中断处理程序

6.2 I/O设备和设备控制器

设备控制器的基本功能：①接收和识别命令②数据交换③标识和报告设备的状态④地址识别⑤数据缓冲区⑥差错控制

设备控制器的组成：①设备控制器与处理机接口②设备控制器与设备接口③I/O逻辑

I/O通道：为了建立独立的I/O操作，不仅使数据的传递能独立于cpu，而且也希望有关对I/O操作、住址、管理及其结束处理尽量独立，以保证cpu有更多的时间去进行数据处理，在cpu和设备控制器之间增设了I/O通道。

I/O通道的类型：

①字节多路通道，用于连接多个慢速的和中速的设备，这些设备的数据传送以字节为单位。每传送一个字节要等待较长时间，如终端设备等。因此，通道可以以字节交叉方式轮流为多个外设服务，以提高通道的利用率。这种通道的数据宽度一般为单字节。

②数组选择通道，用于连接多台高速设备，但它只含有一个分配型子通道。 ③数组多路通道，以数组为单位在若干高速传输操作之间进行交叉复用。 6.3中断机构和中断处理程序

中断：指cpu对I/O设备发来的中断信号的一种响应。cpu暂停正在执行的程序，保留cpu环境后，自动地转去执行该I/O设备的终端处理程序。执行完后，再回到断点，继续执行原来的程序。

中断向量表：中断向量表中的表项对应了一种设备中断处理程序的入口地址 多中断源的处理方式：①屏蔽中断②嵌套中断

中断处理程序的步骤：①测定是否有未响应的中断信号②保护被中断进程的cpu环境③转入相应的设备处理程序④中断处理⑤回复CPU的现场并退出中断。 6.4设备驱动程序

对I/O设备的控制方式：

①使用轮询的可编程I/O方式；②使用中断的可编程I/O方式；③直接存储器访问方式（DMA direct memory access）；④I/O通道控制方式； 6.5与设备无关的I/O软件

与设备无关软件的基本概念：

①以物理设备名使用设备；②引入了逻辑设备名；③逻辑设备名到物理设备名称的转换；

假脱机技术（spooling技术）

spooling技术：在联机情况下实现的同事外围操作的技术 spooling系统主要由以下四部分构成：

①输入井和输出井；②输入缓冲区和输出缓冲区；③输入进程和输出进程；④井管理程序； spooling系统的特点：

①提高I/O的速度；②将独占设备改造为共享设备；③实现了虚拟设备功能； 6.7缓冲区管理

引入缓冲区的原因：

①缓和CPU与I/O设备间速度不匹配矛盾；②减少对CPU的中断频率，放宽对CPU中断响应时间的限制；③解决数据粒度不匹配的问题；④提高CPU和I/O设备之间的并行性； 6.8磁盘存储器的性能和调度

一个物理记录存储在一个扇区上，磁盘上能存储的物理记录块的数目是由扇区数、次倒数以及磁盘面数所决定的。

磁盘调度算法：

①先来先服务：根据进程请求访问磁盘的先后次序进行调度；②最短寻道时间优先：选择访问的磁道与当前磁头所在磁道到距离最近，每次寻道时间最短，不能保证平均寻道时间最短。可能导致一些请求无限期推延，产生饥饿现象。③扫描算法：不仅考虑当前磁道距离，优先考虑在磁道前进方向的最短时间，排除磁头在盘面上的往复运动，避免“饥饿”现象。④循环扫描算法：为了减少扫描算法造成的某些进程请求被严重推迟，规定磁头单向移动。⑤N-step-scan算法：将磁盘请求队列分成若干个长度为N的子队列，磁盘调度按先来先服务算法处理子队列，而处理队列按扫描算法，可以避免粘着现象⑥FSCAN算法：实质上是N-step-scan算法的简化，只讲磁盘请求队列分为两个子队列。

第七章 文件管理

7.1文件和文件系统

数据项：

①基本数据项：用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，又称为字段。②组合数据项：由若干个基本数据项组成，简称组项。

记录：一组想干数据项集合，用于描述一个对象在某方面的属性。 文件：由创建者所定义的、具有文件名的一组相关元素的集合。

文件的属性包括：①文件类型②文件长度③文件物理位置④文件建立时间 文件操作：

文件的基本操作：①创建②删除③写文件④设置文件读/写位置 文件的“打开”和“关闭”操作:

当用户第一次请求对某文件进行操作时，必须先利用open系统调用将该文件打开。所谓“打开”是指系统将指名文件的属性，丛外存拷贝到内存打开文件表中的一个表目中，并将该表目编号返回给用户。“关

闭”操作，OS会将把该文件从打开文件表中的表目上删除掉。

7.2文件的逻辑结构

按文件是否有结构可以吧文件分为有结构文件和无结构文件，有结构文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项

按文件的组织方式可以把文件分为：

①顺序文件，由一系列记录安某种顺序排列所形成的文件，其中的记录可以是定长记录 或可变长记录。②索引文件，为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对 记录的检索速度。③索引顺序文件，为每个文件建立一张索引表时，为一组记录中的第一个记录建立索引 表项。

顺序结构文件排列方式：①串结构②顺序结构 记录寻址方式： 1.隐式寻址方式：系统设置一个读指针指向当前记录的逻辑地址，待读完时，指针跳跃 和记录等长的距离

2.显示寻址方式：

①通过文件中记录的位置：通过0到N-1的整数来标识文件中的记录；②利用关键字：用户指定一个字段作为关键字，通过指定的关键字来查找该记录。

索引文件：一张指示逻辑记录和物理记录之间对应关系的表。索引表中的每项成为索引 项。

索引顺序文件：主文件按主关键字有序的文件成为索引顺序文件。

直接文件：在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立 对应关系，利用这种关系实现存取的文件叫直接文件。

哈希文件：哈希文件也称为散列文件，是利用哈希存储方式组织的文件，亦称为直接存 取文件。它类似于哈希表，即根据文件中关键字的特点，设计一个哈希函数和处理冲突 的方法，将记录哈希到存储设备上。 7.3文件目录

文件管理程序可借助于文件控制块中的信息，对文件施以各种操作。文件与文件控制块FCB一一对应，而人们把文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项。通常，一个文件目录也被看做是一个文件，称为目录文件。

FCB一般应包括下列的文件属性信息：

1.文件标志和控制信息；2.文件逻辑结构信息；3.文件物理结构信息；4.文件使用信息；5.文件管理信息； 7.4文件共享

有向无循环图DAG：允许一个文件可以有多个父目录，即有多个属于不同用户的多个目录，同时指向同一个文件。

利用索引结点：文件的屋里地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。

利用符号实现文件共享：允许一个文件或子目录有多个父目录，但其中仅有一个作为主父目录，其它几个父目录都是通过符号链接方式与之相链接的。

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