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

1、第1章 操作系统引论1.1操作系统的目标与作用操作系统的目标：方便性有效性：有效性包含的第一层含义是提高系统资源的利用率,第二层含义是，提高系统吞吐量可扩充性开放性用户实现与操作系统通信的三种方式：命令方式系统调用图标窗口操作系统会管理处理机、存储器、I/O设备以及文件，处理机管理是应用于分配和控制处理机；存储器管理主要负责内存的分配与回收；I/O设备管理是负责I/O设备的分配与操纵；文件管理是用于实现对文件的存取、共享和保护。1.2几种操作系统单道批处理系统，内存中只允许存放一个作业，当前正在运行的作业驻留内存，执行顺序是先进先出。在单道批处理系统中，一个作业单独进入内存并独占系统资源，直到

2、运行结束后下一个作业才能进入内存，当进行输入操作时，cpu处于等待状态。单道批处理系统的缺点是系统中的资源得不到充分的利用。多道批处理系统，用户所提交的作业先存放在外存上，并排成一个队列成为“后备队列”。然后由作业调度程序按一定的算法，从后备队列中选择若干个作业调入内存，使它们共享cpu和系统中各种资源。多道批处理系统的优点有：1.资源利用率高2.系统吞吐量大缺点有：1.平均周转时间长2.无交互能力分时系统，是指一台主机上连接多个带有显示器和键盘的终端，同事允许多个用户通过主机的终端，以交互方式使用计算机，共享主机中的资源。分时系统的特性为：1.多路性2.独立性3.及时性4.交互性实时系统，是

3、指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间。实时系统的特征有：1.多路性2.独立性3.及时性4.交互性5.可靠性1.3操作系统的基本特征并发，是指一个时间段中有几个进程都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，担任一个时刻点上只有一个进程在处理机上运行。这里要和并行加以区分，并行是两个或多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔内发生。进程，是指在做系统中能独立运行并作为资源分配的基本单位共享，是指系统中的资源可供内存这中多个并发执行的进程共同使用。由于资源的属性不同，所以多个进程对资源的共享方式也不同，可以分为互斥共享和同

4、时访问。虚拟，是指通过技术（spooling技术）把一个物理实体变成若干个逻辑上的对应物。异步，是指进程以人们不可预知的速度向前推进（和线程的异步性类似）1.4操作系统的主要功能处理机管理功能：1.进程控制2.进程同步3.进程通信4.调度（作业调度，进程调度）存储器管理功能：1.内存分配2.内存保护3.地址映射4.内存扩充设备管理功能：1.缓冲管理2.设备分配3.设备处理文件管理功能：1.文件存储空间管理2.目录管理3.文件读写管理与保护第2章 进程的描述和控制2.1前趋图和程序的执行前趋图的画法（略）程序顺序执行时特征：1. 顺序性：指处理机严格按照程序所规定的顺序执行，即每一操作必须在下一

5、个操作开始之前结束；2. 封闭性：在程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态只有本程序才能改变它，程序一旦开始执行，其中执行结果不受外界因素影响；3. 可再现性：这种只要称必须执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是”走走停停”地执行，都可获得相同的结果。程序并发执行时的特征：1. 间断性2.失去封闭性3.不可再现性2.2进程的描述进程的定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。进程的特征：动态性；并发性；独立性

6、；异步性。进程的三种基本状态：就绪态ready；执行态running；阻塞态block释放I/O请求时间片完进程调度I/O完成许可执行终止阻塞就绪创建三种基本状态的转换：进程控制块pcb的作用： 作为独立运行基本单位的标志； 能实现间断性与运行方式； 提供进程管理所需要的信息； 提供进程调度所需要的信息； 实现与其他进程的同步与通信；进程控制块中的信息： 进程标识符（外部标识符，内部标识符）；处理机状态（通用寄存器，指令寄存器，程序状态字psw，用户栈指针）； 进程调度信息（进程状态，进程优先级，其他信息，事件）； 进程控制信息（程序和数据的地址，进程同步和通信机制，资源清单，链接指针）；进程

7、控制块的组织方式：线性方式；链接方式；索引方式；2.3进程控制OS内核的作用：保护内核中的程序，防止其遭受其他应用的破坏；提高OS的运行效率；处理机的执行状态：系统态（管态）：具有较高的特权，能执行一切的指令，访问所有的寄存器和存储区，传统的OS都在系统态与运行；用户态（目态）：具有较低的特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区；原语：由若干条指令组成的，用于完成一定功能的过程。原语的操作称为原子操作，一个原子操作中的所有动作要么全做，要么全不做（类似于）2.4进程同步临界资源：一次仅允许一个进程使用的共享资源；临界区：每个进程访问临界资源的那段代码。每次只允许一个进程进入

8、临界区，进入后不允许其他进程进入；同步机制应遵循的规则：空闲让进；忙则等待；有限等待；让权等待；信号量机制整型信号量：信号量S是一个整数，S大于等于零是代表可供并发进程使用的资源实体数，当S小于零时则表示正在等待使用临界区的进程数，它仅能被两个原子操作来访问，分别是wait(S)和signal(S)，它们被称为P、V原语，它们的代码如下：wait(S)signal(S)while(S<=0)S+; S-;记录型信号量：记录型信号量是在整型信号量的基础上，添加一个进程链表指针list，用于链接所有等待进程，它所包含的数据项可描述如下：typedef structint value;stru

9、ct 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型信号量：将进程在整个运行过程中需要要的所有资源，一次性全部地分配给进程，带进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。就

10、是在wait操作中增加了一个“AND”条件，故称为AND同步。两个操作的代码如下：Swait(S1，S2，.，Sn）while(TRUE)if(Si>=1&&.&&Sn>=1)for(i=1;i<=n;i+)Si-;break;elseplace the process in the waiting queue associated with the first Si found withSi<1,and set the program count of this process to the beginning of Swait ope

11、rationSsignal(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。

12、由此形成一般化信号量机制。对应的Swait和Ssignal代码如下：Swait(S1,t1,d1,.,Sn,tn,dn);Ssignal(S1,d1,.,Sn,dn);信号量的应用：利用信号量实现进程互斥；利用信号量实现前趋关系；管程：系统中的各个硬件资源和软件资源均可以用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。利用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据结构实施的操作定义为一组过程。代表共享资源的数据结构，以及由对该数据结构实施操作的一组过程做组成的资源管理程序，共同构成了一个操守做系统的资源管理模块，我们

13、称之为管程。wait()：挂起调用进程并释放管程，直至另一进程正在条件变量上执行signal()signal()：如果有其他他的进程因对条件变量执行wait()而被挂起，便释放之。如果没有进程等待，这信号被忽略，不保存。管程的语法描述如下：Monitor monitor_name /管程名share variable declarations; /共享变量说明cond declaration; /条件变量说明public:/能被进程调用的过程void P1(.)/对数据结构操作的过程.void P2(.)./管程主体initialization code;/初始化代码.管程的特性：模块化抽象数

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

15、步问题生产者消费者问题利用记录型信号量利用AND型信号量利用管程哲学家进餐问题利用记录型信号量利用AND型信号量读者写者问题利用记录型信号量利用信号量集机制2.6进程通信进程通信的类型共享存储器系统1. 基于共享数据结构的通信方式：要求进程公用某些数据结构，借意义实现进程间的信息交换2. 机遇与共享存储区的通信方式：为了传输大量数据，在内存中话术了一块共享存储区域，进程可以通过对该共享区的读或写交换信息，实现通信。管道通信系统；消息传递系统；1. 直接通信方式：是指发送进程利用OS所提供的发送原语，直接把消息发送给目标进程2. 间接通信方式：是指发送和接受进程，都通过共享中间实体的方式进行消息

16、的接收和发送，完成进程间的通信第3章 处理机调度死锁3.1处理机调度的层次和调度算法的目标处理及调度的层次：高级调度：高级调度的对象是作业，其主要功能是根据某种算法，决定将外存上处于后背队列中的哪几个作业调入内存，为他们创建进程、分配必要的资源，并将它们放入就绪队列低级调度：调度的对象是进程，其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。中级调度：引入中级调度的主要目的是，提高内存利用率和系统吞吐量。把那些暂时不能运行的进程，调至外存等待，此时进程的状态成为就绪驻外存状态处理机调度算法的目标：处理机调度算法的共同目标：1. 提高资源利

17、用率；2. 公平性3. 平衡性4. 策略强制执行批处理系统的目标1. 平均周转时间短2. 系统吞吐量高3. 处理机利用率高分时系统的目标1. 响应时间快2. 均衡性实施系统的目标1. 截止时间的保证2. 可预测性cpu利用率=cpu有效工作时间÷（cpu有效工作时间+cpu空闲等待时间）周转时间：对于一个进程来说，一个重要的指标是它实行所需要的时间。从进程提交到进程完成时间间隔为周转时间，也就是等待进入内存的时间，在就绪队列中等待的时间，在cpu中执行的时间和I/O操作的时间的总和3.2作业与作业调度作业：正在执行的一个或多个相关的进程被称为作业作业步：一般情况下，一个作业可划分成若

18、干个部分，每个部分称为有一个作业步。作业控制块（JBC）：作业在系统中存在的标志，保存了系统对作业进行管理和调度所需的全部信息作业运行的三个状态：后备状态、运行状态、完成状态作业运行的三个阶段：收容阶段、运行阶段、完成阶段先来先服务算法（FCFS）：每次调度室从就绪的进程队列中选择有一个最先进入该队列的进程，为之分配处理机，使其投入运行短作业优先算法（SJF）：以作业的长短来计算优先级，作业越短，优先级越高。作业的长短是根据作业所要求的运行时间来衡量的短作业优先算法的缺点：必须预知作业的运行时间对长作业非常不利无法实现人机交互无法保证紧迫性作业得到及时处理优先级调度算法（PSA）：先调用优先级

19、高的进程，优先级体现了进程的紧迫程度高响应比优先调度算法(HRRN)：为每个做作业引入一个动态优先级，即优先级是可以改变的，令它随等待时间延长而增加，这将使作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。高响应比优先调度算法优先级=（等待时间+要求服务时间）÷要求服务时间3.3进程调度进程调度的任务：保存处理机的现场信息按某种算法选取进程把处理器分配给进程进程调度的机制排队器：事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列分派器：一句进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分排器到新选出进程的上下文切换，将处理机分配给新选出的进

20、程上下文切换器进程调度的方式：非抢占方式：一旦把处理机分配给某进程后，就一直让它运行下去，绝不会因为时钟中断或任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程抢占方式的原则：优先权原则短进程优先原则时间片原则轮转调度算法：每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护

21、一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。优先级调度算法：非抢占式优先级调度算法抢占式优先级调度算法优先级的类型：静态优先级动态优先级3.4实时调度最早截止时间优先算法：根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高。最低松弛度优先算法：根据任务的紧急（或松弛）程度决定优先级，任务紧急程度越高，其优先级越高3.5死锁死锁定义：如果一组进程中的每一个进程都在等待仅有该组进程中的其它进程才能引发的事件，那么该组进程是死锁的引起死锁的原因：竞争不可抢占性资源引起死锁竞争可消耗资源引起死锁进程推进顺序不当引起死锁死锁产生的必要条件：互斥条件，进程对所分配到的资

22、源进行排他性使用。请求和保持条件，进程已经保持了至少一个在资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放不可抢占条件，进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放循环等待条件，在发生死锁是，必然存在一个进程和资源的循环链3.6预防死锁破坏“请求和保持”条件破坏“不可抢占”条件破坏“循坏等待”条件3.7避免死锁安全状态：是指系统能按某种进程推进顺序为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大要求，是每个进程都可以顺利地完成。此时这个序列称为安全序列，如果系统无法找到这样一个安全序列，则称系统处于不安

23、全状态。利用银行家算法避免死锁：每个进程在进入系统时，它必须申明在运行过程工，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。银行家算法的数据结构：可利用资源向量Available：是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Availablej=K，则表示系统中现有Rj类资源K个。最大需求矩阵Max：这是个n×m的矩阵，它定义了系统中n个进程中的每个

24、进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。分配矩阵Allocation：也是n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的 数目为K。需求矩阵Need：这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵满足以下关系：Needi,j=Maxi,j-Allocationi,j银行家算法的描述：设进程cusneed提出请求REQUEST i，则银行

25、家算法按如下规则进行判断。(1)如果REQUEST cusneed i<= NEEDcusneedi，则转（2)；否则，出错。(2)如果REQUEST cusneed i<= AVAILABLEi，则转（3)；否则，等待。(3)系统试探分配资源，修改相关数据：AVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。安全性检查算法：(1) 设置工作向量Work，

26、它表示系统可供他提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行开始时，赋初值Work=Available；设置Finish向量表示系统是否具有足够的资源分配给进程，是指运行完成，赋初值Finishi=false；当有足够资源分配给进程时，再令Finishi=true。(2) 从进程集合中找到一个能满足下述条件的进程：Finish=false;Needi,j<=Workj；若找到，执行（3），否则执行（4）(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Workj=Workj+Allocationi,j;Finishi=true;GOTO 2(4) 如所有的进程Fi

27、nishi= true，则表示安全；否则系统不安全。银行家算法考计算题具体例子课本P113(第三版P110)3.8死锁的检测与解除死锁的解除：终止进程：终止所有的进程逐个终止进程第4章 存储器管理4.1存储器的层次结构存储器的多层结构：由上至下，容量越来越大，速度越来越慢寄存器：寄存器是中央处理器内的组成部分，它是有限存储容量的高速存储部件，可用来暂存指令、数据和地址高速缓存是存在于主存和寄存器之间的以及存储器主要用于备份主存中较常用的数据，以减少处理机对主存的访问次数，这样可以大幅度地提高程序执行的速度。主存：用于保存进程运行时的程序和数据。磁盘缓存：用于暂时存放频繁使用的一部分磁盘数据和信

28、息。4.2程序的装入和链接程序运行的三个步骤：编译，有编译程序对用户源程序进行编译，形成若干个目标模块；链接，由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块；装入，有装入程序将装入模块装入内存；程序装入的方式：绝对装入方式，用户程序经编译后产生绝对地址的目标代码。可重定位装入方式，目标模块的启示地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。根据内存的当前情况，将装入模块装入到内存的适当位置。地址变换通常是在装入是依次完成的，以后不再改变，所以是静态重定位。动态运行装入方式，程序在运行过程中在内存的位置可能改变，装入程序包装入模块

29、装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行程序链接的方式：静态链接方式，在程序运行之前，先将各个目标模块及他们所需要的库函数链接成一个完整的装配模块，以后不再拆开。装入时动态链接，在目标模块装入内存时，边装入边链接。即在装入一个目标模块时，若发现一个外部模块调用，即引起装入程序去找出相应的外部模块，并将它装入内存以及修改目标模块中的相对地址。运行时动态链接，将某些目标模块的链接，推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并把它链接到调用者模块上。4.3连续分配存储管理方

30、式基于顺序搜索的动态分区分配算法：首次适应算法，从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业。循环首次适应算法，在分配内存空间时，不再每次从表头开始查找，而是从上次找到空闲区的下一个空闲开始查找，知道找到第一个能满足要求的空闲区位置，并从中划出一块玉请求大小相等的内存空间分配给作业。最佳适应算法，从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。最坏适应算法，扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有空闲

31、分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区是否能满足作业要求。4.5分页存储管理方式页面：分页存储试讲一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始。物理块：把内存空间分成与页面相同大小的若干存储块，称为物理块，加以编号，从0#号开始在为进程分配内存时，以块为单位将进程中若干个页分别装入到多个可以不相邻接的物理块中。地址结构：包含两个部分，前一部分为页号P，后一部分为位偏移量W，即页内地址。对于某特定机器，其地址结构是一定。若给定一个逻辑地址空间中的地址为A，页面大小为L，则页面号P和页内地址d可以按下式计算出：P=int(A/L

32、) d=A% L页表：在分页系统，允许将进程到的各个页离散地存储在内存不同的物理块中，为保证系统能在内存中找到每个页面所对应的物理块，系统为每个进程建立了一张页面映像表，简称页表。地址变换机构：基本的地址变换机构，页表的功能可以由一组专门的寄存器来实现。一个页表项用一个寄存器。由于寄存器具有较高的访问速度，因而有利于提高地址变换的速度；但由于寄存器成本较高，且大多数现代计算机的页表又可能很大，使页表项的总数可达几千甚至几十万个，显然这些页表项不可能都用寄存器来实现，因此，页表大多驻留在内存中。在系统中只设置一个页表寄存器PTR(Page-Table Register)，在其中存放页表在内存的始

33、址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址(相对地址)分为页号页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项

34、在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。左图示出了分页系统的地址变换机构。具有快表的地址变换机构，由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这种方式将使计算机的处理速度降低近1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是得不

35、偿失的。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”，在IBM系统中又取名为TLB(Translation Lookaside Buffer)，用以存放当前访问的那些页表项。此时的地址变换过程是：在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内

36、存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则OS必须找到一个老的且已被认为不再需要的页表项，将它换出。右图示出了具有快表的地址变换机构。4.6分段存储管理方式分段式存储管理方式引入的目的：方便编程：按逻辑关系分为若干个段，每个段从0编址，并有名字和长度，访问的逻辑地址由段名和段内偏移量决定。信息共享：共享是以信息为逻辑单位，页是存储信息的物理单位，段却是信息的逻辑单位。信息保护：保护也是信息为逻辑单位。动态链接：动态链接以段为单位。动态增长：实际应用中，某些段（数据段）会不断增长，前面的存

37、储管理方法均难以实现。分段：在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。通常用一个段号来代替段名，每个段都从0开始编制，并采用一段连续的地址空间。段表：在分段式存储管理系统中，为每个分段分配了一个连续的分区，进程中各个段离散地装入内存中不同分区，系统为每个进程建立一张段映射表，简称段表地址变换机构页式存储管理段式存储管理目的实现非连续分配,解决碎片问题更好满足用户需要信息单位页（物理单位）段（逻辑单位）大小固定（由系统定）不定（由用户程序定）内存分配单位页段作业地址间一维二维优点有效解决了碎片问题有效提高内存的利用率更好地实现数据共享与保护段长可动态增长便于

38、动态链接段页式存储管理方式基本原理：段页式存储管理是分段和分页原理的结合，即先将用户程序分成若干个段（段式），并为每一个段赋一个段名，再把每个段分成若干个页（页式）。其地址结构由段号、段内页号、及页内位移三部分所组成。地址变换：用段号与段寄存器中的段长进行比较，若小于段长则利用段表始址和段号找出该段页表的始址,(否则越界中断)， 再用逻辑地址中的段内页号在页表中找到相应的块号，最后与页内位移形成物理地址。第5章 虚拟存储器5.1虚拟存储器概述常规存储器管理方式的特征：一次性：作业在运行前需一次性地全部装入内存。驻留性：作业装入内存后，便一直驻留内存，直至作业运行结束。局部性原理：指程序在执行时

39、呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。局部性又表现为时间局部性(由于大量的循环操作，某指令或数据被访问后，则不久可能会被再次访问)和空间局部性（如顺序执行，指程序在一段时间内访问的地址，可能集中在一定的范围之内）。虚拟存储器的定义：是指仅把作业的一部分装入内存便可运行作业的存储管理系统，它具有请求页调入功能和页置换功能，能从逻辑上对内存容量进行扩充，其逻辑容量由外存容量和内存容量之和决定，其运行速度接近于内存，成本接近于外存。虚拟存储器的特征：多次性对换性虚拟性5.3页面置换算法（计算题）最佳置换算法（无法实现）先进先出置换算

40、法：置换先进的物理块最近未使用和最少使用置换算法：置换最近未使用和最少使用的物理块5.4“抖动”与工作集抖动，同事在系统中运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺职业调入内存。第6章 输入输出系统6.1 I/O系统的功能、模型和接口I/O系统的基本功能：隐藏物理设备的细节与物理设备的无关性提高处理机和I/O设备的利用率对I/O设备进行控制确保对设备的正确共享错误处理I/O设备的层次结构：用户层I/O软件设备独立性软件设备驱动程序中断处理程序6.2 I/O设备和设备控制器设备控制器的基本功能：接收和识

41、别命令数据交换标识和报告设备的状态地址识别数据缓冲区差错控制设备控制器的组成：设备控制器与处理机接口设备控制器与设备接口I/O逻辑I/O通道：为了建立独立的I/O操作，不仅使数据的传递能独立于cpu，而且也希望有关对I/O操作、住址、管理及其结束处理尽量独立，以保证cpu有更多的时间去进行数据处理，在cpu和设备控制器之间增设了I/O通道。I/O通道的类型：字节多路通道，用于连接多个慢速的和中速的设备，这些设备的数据传送以字节为单位。每传送一个字节要等待较长时间，如终端设备等。因此，通道可以以字节交叉方式轮流为多个外设服务，以提高通道的利用率。这种通道的数据宽度一般为单字节。数组选择通道，用于

42、连接多台高速设备，但它只含有一个分配型子通道。数组多路通道，以数组为单位在若干高速传输操作之间进行交叉复用。6.3中断机构和中断处理程序中断：指cpu对I/O设备发来的中断信号的一种响应。cpu暂停正在执行的程序，保留cpu环境后，自动地转去执行该I/O设备的终端处理程序。执行完后，再回到断点，继续执行原来的程序。中断向量表：中断向量表中的表项对应了一种设备中断处理程序的入口地址多中断源的处理方式：屏蔽中断嵌套中断中断处理程序的步骤：测定是否有未响应的中断信号保护被中断进程的cpu环境转入相应的设备处理程序中断处理回复CPU的现场并退出中断。6.4设备驱动程序对I/O设备的控制方式：使用轮询的

43、可编程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磁盘存储器的性能和调度一个物理记录存储在一个扇区上，磁盘上能存储的物理记录块的数目是由扇区数、次倒数以及磁盘面数所决定的。磁盘调度算法：先来先服务：根据进程请求访问磁盘的先后次序进行调度；最短寻道时间优先：选择访问的磁道与当前磁头所在磁道到距离最近，每次寻道时间最短，不能保证平均寻道时间最短。可能导致一些请求无限期推延，产生饥饿现象。扫描算法：不仅考虑当前磁道距离，优先考虑在磁道前进方向的最短时间，排除磁头在盘面上的往复运动