操作系统-复习课件.ppt

《操作系统-复习课件.ppt》由会员分享，可在线阅读，更多相关《操作系统-复习课件.ppt（167页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、操作系统复习第一章 概述1单道批处理系统什么是批什么是批处理？理？是指计算机系统对一批作业自动进行处理的一种技术。什么是什么是单道批道批处理？理？内存中仅有一道作业的批处理方式。单道批处理系统是最早的OS。单道批道批处理的缺点理的缺点 用户作业仍是一道一道顺序执行，仍不能合理的利用资源。以主机为主的作业，外围设备空闲，相反，又会造成主机空闲。2多道批处理系统在计算机内存中同时存放若干道已开始运行尚未结束的程序，它们交替运行，共享系统中的各种硬、软件资源，从而使处理机得到充分利用。用户提交的作业放在外存上排成一个队列，称为后备队列；后由作业调度程序按一定算法选择若干个调入内存，使它们共享CPU和

2、系统中的资源。多道批多道批处理的理的优点点（1）提高CPU的利用率。（2）提高内存和I/O设备的利用率。（3）增加系统吞吐量。多道批多道批处理的缺点理的缺点（1）平均周转时间长。（2）无交互能力。3分时系统 分时系统是在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端以交互方式使用计算机，共享主机中的资源。主机主机终终端端分分时系系统的思想的思想 采用时间片轮转的方法，同时为许多终端用户服务，对每个用户能保证足够快的响应时间，提供交互会话功能。分分时系系统的工作方式的工作方式 一台主机连接了若干终端，用户交互式向系统提出请求。系统采用时间片轮转方式处理请求，并通过交互

3、方式在终端上向用户显示结果，用户根据结果发出下道命令。分分时系系统实现的关的关键问题（1）及时接收：系统应能及时接收并处理命令，再将结果返回给用户，实现人机交互。（2）及时处理：用户键入命令后能及时控制自己作业的运行。4实时系统 “实时”，是表示“及时”，而实时系统(Real-Time System)是 指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。实时系系统的的应用用（1）实时控制：实时采集现场数据并对所采集数据进行及时处理。如：钢铁冶炼和钢板轧制的自动控制、飞机自动驾驶系统等。（2）实时信息处理：计算机及时接收从远程终端发来的服务请求，

4、根据用户提出的问题对信息进行检索和处理，并在很短时间内对用户做出正确回答。如：银行、机票订购系统、股市行情实时信息处理系统等。5操作系统的特性5.1并发性并行性是指两个或多个事件在同一时刻发生。并发性是指两个或多个事件在同一时间间隔内发生。(与并发相似，但多指硬件支持）程序的并发执行，有效地改善了系统资源的利用率和提高了系统的吞吐量，但它使系统复杂化，操作系统必须具有控制和管理各种并发活动的能力。5.2共享性操作系统与多个用户的程序共同使用计算机系统中的资源。资源共享是指系统中的硬件和软件资源不再为某个程序所独占，而是供多个用户共同使用。由于资源属性的不同，存在两种形式的资源共享方式：（1）互

5、斥共享资源 （2）同时访问方式 并并发和共享共享是操作系统两个最基本的特征，这两者之间又是互为存在条件的。资源共享是以程序的并发为条件的，若系统不允许程序并发执行，自然不存在资源共享问题。若系统不能对资源共享实施有效的管理，也必将影响到程序的并发执行，甚至根本无法并发执行。5.3虚拟性 在操作系统中虚拟是指把一个物理上的实体，变为若干个逻辑上的对应物。物理实体(前者)是实的，而后者是虚的，相应地，用于实现虚拟的技术，称为虚拟技术。在OS中利用了多种虚拟技术，分别用来实现虚拟处理机、虚拟内存、虚拟外部设备和虚拟信道等。5.4异步性在多道程序环境下，允许多个进程并发执行，但由于竞争资源等因素的限制

6、，使进程的执行不是一气呵成，而是以“走走停停”的方式运行。多道程序环境下程序的执行，是以异步方式进行的；每个程序在何时执行，多个程序间的执行顺序以及完成每道程序所需的时间都是不确定和不可预知的。进程是以人们不可预知的速度向前推进，即进程的异步性。6操作系统的主要功能 从资源管理观点看，操作系统具有五大功能：处理机管理存储器管理设备管理文件管理接口的管理6.1处理机管理功能 处理机管理的主要任务是对处理机的分配和运行实施有效管理。对处理机管理，可归结为对进程的管理（进程控制、进程同步、进程通信、调度）。1进程控制当用户作业要运行时，应为之建立一个或多个进程，并为它分配除处理机以外的所有资源，将它

7、放入进程就绪队列。当进程运行完成时，立即撤销该进程，以便及时释放其所占有的资源。进程控制的基本功能就是创建和撤销进程以及控制进程的状态转换。2进程同步 进程同步是指系统对并发执行的进程进行协调。最基本的进程同步方式是使诸进程以互斥方式访问临界资源。此外，对于彼此相互合作、去完成共同任务的诸进程，则应由系统对它们的运行速度加以协调。3进程通信 对于相互合作的进程，在它们运行时，相互之间往往要交换一定的信息，这种进程间所进行的信息交换称为进程通信。4进程调度 当一个正在执行的进程已经完成，或因某事件而无法继续执行时，系统应进行进程调度，重新分配处理机。进程调度是指按一定算法，如最高优先算法，从进程

8、就绪队列中选出一进程，把处理机分配给它，为该进程设置运行现场，并使之投入运行。6.2存储器管理功能存储器管理的主要任务:为多道程序的并发运行提供良好环境；便于用户使用存储器；提高存储器的利用率；为尽量多的用户提供足够大的存储空间。1内存分配 多道程序能并发执行的首要条件是，各道程序都有自己的内存空间，因此，为每道程序分配内存是存储器管理的最基本功能。2内存保护 为保证各道程序都能在自己的内存空间运行而互不干扰，要求每道程序在执行时能随时检查对内存的所有访问是否合法。必须防止因一道程序的错误而扰乱了其它程序，尤其应防止用户程序侵犯操作系统的内存区。3地址映射 在多道程序的系统中，操作系统必须提供

9、把程序地址空间中的逻辑地址转换为内存空间对应的物理地址的功能。地址映射功能可使用户不必过问物理存储空间的分配细节，从而为用户编程提供了方便。4内存扩充 由于物理内存的大小可能限制了大型作业或多个作业的并发执行，为了满足用户的要求并改善系统性能，必须对内存加以扩充。但我们无须去真正地增加内存空间，而只须借助于虚拟技术，便可获得这样地效果，使系统能运行内存要求量远比物理内存大得多得作业，或让更多得作业并发执行。6.3设备管理功能设备管理的主要任务:完成用户程序请求的I/O操作；为用户程序分配I/O设备；提高CPU和I/O设备的利用率；提高I/O速度。6.4文件管理功能文件管理的主要任务：文件存储空

10、间的管理目录管理文件读、写管理和保护6.5向用户提供接口为方便用户使用操作系统，OS向用户提供了用户与操作系统的接口，该接口分为用户接口和程序接口两类。1.用户接口：用户可通过该接口控制自己的作业。又可分为联机用户接口、脱机用户接口和图形用户接口。2.程序接口 该接口是为用户程序在执行中访问系统资源而设置的，是用户程序取得操作系统服务的惟一途径。他由一组系统调用组成，每一个系统调用都是一个能完成特定功能的子程序，每当程序要求OS提供某种服务时，便调用具有相应功能的调用。第二章 进程管理1 前驱图（DAG）前驱图是一个有向无循环图，用于描述进程之间执行的前后关系。如：每个结点可以表示一条语句、一

11、个程序段或进程。结点间的有向边表示两个结点之间存在的偏序或前趋关系“”。下图是不是前驱图？前趋图中必须不存在循环，故上图不是前趋图。对于具有下述四条语句的程序段应具有什么样的前驱关系？S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b2.进程1 什么是进程进程是程序的一次执行。进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。进程是可与其他进程并发执行的程序，在一个数据集合上的运行过程。它是系统进行资源分配和调度的一个独立单位。进程的定程的定义：进程是程是进程程实体（程序段、数据体（程序段、数据段、段、PCB）的运行）的运行过程，是系程

12、，是系统进行行资源分配源分配和和调度的一个独立度的一个独立单位。位。进程与程序的区别是什么？程序是静态的，进程是动态的；程序的存在是永久的，进程是动态的产生和消亡的。进程具有并发性，而程序没有。进程可分配有资源，而程序没有。进程与程序的联系是什么？进程是由程序、数据和进程控制块（PCB）三部分构成的。进程的目标就是执行他所对应的程序。2 进程的特征动态性并发性独立性异步性 动态性：进程由创建而产生，由调度而执行，由撤销而消亡，是动态的。而程序只是一组有序指令的集合，是静态的。并发性：进程可以并发执行，而程序只能顺序执行。独立性：进程是一个能独立运行、独立分配资源、独立接受调度的基本单位。而程序

13、不能作为一个单位独立参与运行。3 进程控制块（PCB）创建进程时首先创建其PCB，系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。当进程完成时系统释放其PCB，进程随之消亡。进程与PCB是一一对应的。4 进程的三种基本状态就绪状态执行状态阻塞状态当进程已分配到除CPU以外的所有必要资源时，它便处于就绪状态，一旦获得CPU，便立即执行。当进程已分配到CPU，其程序正在执行，进程就进入执行状态。正在执行的进程，由于发生某个事件而暂时无法执行时，便放弃处理机而进入阻塞状态执行行就就绪阻阻塞塞进程三种状态的转换调度程序选择该程序为其分配CPU1 1 时间片用完；时间片用完；2

14、2 一高优先级进一高优先级进程处于就绪状态。程处于就绪状态。发生某事件而使进程发生某事件而使进程执行受阻，如访问临执行受阻，如访问临界资源时该资源正被界资源时该资源正被其进程访问。其进程访问。阻塞进程的事件消失阻塞进程的事件消失进程转化为就绪状态。进程转化为就绪状态。进程的三个基本状态是：执行状态、就绪状态和阻塞状态。转换如下：1就绪状态执行状态：进程分配到CPU资源2执行状态就绪状态：时间片用完3执行状态阻塞状态：I/O请求4阻塞状态就绪状态：I/O完成5 挂起操作正在执行的进程停止执行，就绪的不接受调度，对于阻塞的进程，即便引起阻塞的事件消失，也不能被调度。具有挂起操作的进程状态转换活动就

15、绪静止就绪：活动就绪（未被挂起的就绪状态）当用原语Suspend挂起后，状态改变。静止就绪活动就绪：当用激活原语Active激活后，状态改变。活动阻塞静止阻塞：活动阻塞（未被挂起的阻塞状态）当用原语Suspend挂起后，状态改变。静止阻塞静止就绪：进程所期待的事件出现后，状态改变。静止阻塞活动阻塞：用激活原语Active激活后，状态改变。6 创建状态和终止状态 在目前实际的系统中，为了管理的需要，还存在着两种常见的进程状态：（1）创建状态（2）终止状态创建状态 创建状态指已经为进程创建了PCB，但该进程所必须的资源尚未分配，故进程还不能被调度执行。终止状态 进程结束或出现无法克服的错误时，由操

16、作系统将其PCB清零，并将PCB空间返还系统，进程进入终止状态。进程五种基本状态的转换7.创建进程 在多道程序环境下，只有作为进程才能运行，因此为使程序运行必须为他创建进程。导致一个进程去创建另一个进程的典型事件：（1）用户登录（2）作业调度（3）提供服务（4）应用请求创建进程完成的主要工作有：（1）OS发现请求创建新进程事件后，调用进程创建原语Creat()；（2）申请空白PCB（3）为新进程分配资源（4）初始化进程控制块（5）将新进程插入就绪队列8进程的终止1 终止原因正常结束异常结束（越界错误、保护错、特权指令错、非法指令、运行超时、I/O故障等）外界干预（操作员干预、父进程请求、父进程

17、终止）9进程同步进程间的直接制约关系进程间的直接制约关系进程间的间接制约关系进程间的间接制约关系9.1基本概念进程程互互斥斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问。进程程同同步步：指多个相关进程在执行次序上的协调。临界界资源源:一次仅供一个进程使用的资源。（物理设备，软资源如变量，表格等）临界区：每个进程中访问临界资源的那段代码叫做临界区。同步机制遵循原则：（1）空闲让进：当无进程处于临界区时，任何有权使用临界区的进程可进入。（2）忙则等待：临界资源互斥访问。（3）有限等待：任何进入临界区的要求应在有限的时间内得到满足（4）让权等待：处于等待状态的进程应放弃占用CPU，以使

18、其他进程有机会得到CPU的使用权。9.2信号量机制信号量机制是一种卓有成效的进程同步工具。整型信号量整型信号量记录型信号量型信号量ANDAND型信号量型信号量信号量集信号量集9.2.1.整型信号量S：是表示资源数目的整形量。仅能通过如下两个标准的原子操作来访问。V操作signal(S)s:=s+1P操作 wait(S)while s=0 do no-op s:=s-1 整型信号量中的wait操作只要是信号量 S=0，就会不断测试，因此该机制为遵循让权等待原则，而是使进程处于忙等状态。9.2.2.记录型信号量semaphoresemaphore：采用了记录型数据结构的记录型信号量。type se

19、maphore=record value:integer；L:list of process；end资源数资源数等待进程链表指针等待进程链表指针procedure signal(S)var S:semaphore;begin s.value=s.value+1;if(s.value =0)then wakeup(s.L)；endprocedure wait(S)var S:semaphore;begin s.value=s.value-1;if(s.value 0)then block(s.L)；end 记录型信号量中当S.value=1andS2=1andandSn=1)for(i=1;i=

20、n;i+)Si:=Si-1;endforelseBlock(Sj.L)endifSsignal(S1,S2,Sn)for(i=1;i=tiandSn=tn)for(i=1;i=n;i+)Si:=Si-di;endforelseBlock(Sj.L)endifSsignal(S1,d1,Sn,dn)for(i=1;i=n;+i)Si:=Si+di;for(在Si.L中等待的每一个进程P)从等待队列Si.L中取出进程P;if(进程P通过Swait中的测试)进程P进入就绪队列;else 进程P进入某等待队列；endfor9.2.5经典进程的同步问题1生产者消费者问题2哲学家进餐问题3读者写者问题生产

21、者消费者问题缓冲池（n个缓冲区）有一群生产者进程在生产产品，并将这些产品提供给消费者进程消费。为使生产者进程和消费者进程并发执行，两者之间设置了一个缓冲池。生产者将所生产的产品放入缓冲池的一个缓冲区中，消费者进程可从中取走产品消费。他们之间必须保持同步，即不允许生产者进程向一个装满产品的缓冲区中投入产品，也不允许消费者进程到一个空缓冲区中去取产品。Buffer数组：具有n个缓冲区的缓冲池。In指针：输入指针，指示下一个可投放产品的缓冲区。Out指针：输出指针，指示下一个可从中获取产品的缓冲区。Counter：缓冲池中的产品数量。Nexp：存放每次刚生产出来的产品。Nextc：存放每次要消费的产

22、品。Noop：空操作。9.2.6生产者消费者问题1.记录型信号量解决生产者消费者问题var mutex,empty,full:semaphore:=1,n,0;buffer:array0,n-1 of item;In,out:integer:=0,0;Producer:repeat produce an item in nextp;wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)mod n;signal(mutex);signal(full);until false;Consumer:repeat wait(full);wait(mute

23、x);nextc:=buffer(out);out:=(out+1)mod n;signal(mutex);signal(empty);consumer the item in nextc;until false9.2.7.AND信号量解决生产者消费者问题var mutex,empty,full:semaphore:=1,n,0;buffer:array0,n-1 of item;In,out:integer:=0,0;Producer:repeat produce an item in nextp;Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)

24、mod n;signal(mutex,full);until false;Consumer:repeat Swait(full,mutex);nextc:=buffer(out);out:=(out+1)mod n;Ssignal(mutex,empty);consumer the item in nextc;until false第三章 处理机调度与死锁 在多道程序环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程。该任务是由进程调度程序完成的，它是操作系统设计的中心问题之一。1 调度队列模型1.1 仅有进程调度的调度队

25、列模型1.2 有进程调度和作业调度的调度队列模型1.3 同时具有三级调度的调度队列模型2进程调度算法1.先来先服务（FCFS）算法2.短作业SJB优先算法3.高优先权优先调度算法 4.高响应比优先调度算法5.轮转法 6.多级反馈队列 2.1 先来先服务（FCFS）算法 该算法既可用于作业调度，也可用于进程调度。进程调度时，把处理机分配给最先进入就绪队列的进程，直到该进程完成或阻塞时，才释放处理机。优点:实现简单。缺点:对短作业不利。2.2 短作业优先（SJF）算法 该算法从就绪队列中选出“运行”最短的进程，为之分配处理机。算法的缺点对长作业不利未考虑作业的紧迫程度FCFS和SJF的性能比较3死

26、锁多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。死锁的定义：如果一组进程中的每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。3.1产生死锁的原因1.竞争资源竞争不可抢占性竞争不可抢占性资源，如打印机。资源，如打印机。竞争可消耗性资源竞争可消耗性资源(由一个由一个进程产生，被另一进程使进程产生，被另一进程使用一短暂时间后便无用）用一短暂时间后便无用）2.进程推进顺序不当 除了系统中多个进程对多个资源的竞争会引发死锁，进程对资源请求和释放的顺序不当也会引发死锁。例：一台打印机R1，一台磁带机R2，可供

27、进程P1和P2使用。3.2产生死锁的必要条件1.互斥条件：进程对所分配到的资源排他性使用。2.请求和保持条件：进程保持了一个资源，又请求新的资源，阻塞后不释放所保持的资源。3.不剥夺条件：进程已获得的资源不能被强占。4.环路等待条件产生死锁必须同时具备上面的四个必要条件，只要上面的任何一个条件不成立，死锁就不会发生。3.3处理死锁的基本方法1.预防死锁：通过设置限制条件，破坏四个条件之一。2.避免死锁：在资源动态分配过程中，用某种方法防止系统进入不安全状态。3.检测死锁：通过检测及时发现死锁的发生。4.解除死锁：检测到死锁时，可通过撤销进程回收资源等方法解除死锁。3.4预防死锁和避免死锁3.4

28、.1预防死锁（1）摒弃请求和保持条件，资源一次性分配。（2）摒弃不剥夺条件，即当某进程新的资源未满足时，释放已占有的资源。（3）摒弃环路等待条件，系统给每类资源一个编号，每个进程按编号递增的顺序请求资源。3.4.2避免死锁在资源动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁发生。预防死锁的几种策略，会严重地损害系统性能。而避免死锁施加较弱的限制，从而获得了较满意的系统性能。1.安全状态 安全状态指系统能按某种（找到一个）进程顺序来为每个进程分配其所需资源，直至满足每个进程对资源最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。假定系统中有三个进

29、程P1、P2和P3，共有12台磁带机。其最大需求量和在T0时刻每个进程已经分配到的数量如下表所示：进 程 最 大 需 求 已 分 配 仍需要可 用P1P2P310495225273安全序列：安全序列：P2P3 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。如下又分给P3一台磁带机，则致使其他进程都无法推进，陷入僵局。进 程 最 大 需 求 已 分 配 仍需要可 用P1P2P31049523（2+1）526（7-1）2（3-1）2.利用银行家算法避免死锁银行家算法是最具代表性的避免死锁的算法，是为银行系统设计的，确保银行在发放贷款时，不会发生不能满足所有客户需要的情况。为实现

30、该算法，每一个新进程进入系统时，必须申明在运行过程中，可能需要每种资源类型的最大单元数目。如有足够的资源，再进一步计算分配后是否会处于不安全状态。3.5死锁的检测和解除当系统为进程分配资源时，若未采取任何限制性的措施，则系统必须提供检测和解除死锁的手段，若死锁发生，系统精确的确定与死锁有关的进程和资源，然后采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。3.5.1死锁的检测1.资源分配图资源进程申请边分配边2.资源分配图的简化（1）找一个即不阻塞又非孤立的进程结点，去掉分配边，将其变为孤立结点。（2）再把相应的资源分配给一个等待该资源的进程，将该结点也变为孤立结点。（3）若能消去所有的

31、边，则称该图可完全简化。3.死锁定理 S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。3.4.2死锁的解除当发现有进程死锁时，应立即把他们从死锁状态解脱出来。常用的方法如下：1.剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。2.2.撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。第四章 存储器管理 存储器是一种

32、宝贵的资源，对其进行有效的管理，直接影响到存储器的利用率，而且还对系统性能有重大影响。1多级存储器结构在存储层次中越往上，存储介质的访问速度越快，价格越高，存储容量越小。2程序的链接目的：链接程序将目标模块进行链接，形成装入模块根据链接时间不同，可分成以下三种方式静态链接方式装入时动态链接运行时动态链接静态链接方式：在程序运行之前，先将各目标模块及库函数链接成一个完整的装配模块，以后不再拆开。装入时动态链接：将用户源程序编译后所得到的一组目标模块在装入内存时边装入边链接。运行时动态链接：在程序执行中需要该模块时才进行链接。2.1.静态链接方式1.1.对相对地址进行修改2.变换外部调用符号2.2

33、装入时动态链接用户源程序经编译后所得到的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序找出相应的外部目标模块，把它装入内存。3程序的装入3.1绝对装入方式在编译时，编译程序知道程序将驻留在内存的位置，则编译程序将产生绝对地址的目标代码，装入模块便从驻留在内存的地址开始向上扩展。绝对装入程序按照装入模块中的地址将程序装入内存。适用于单道程序环境3.2可重定位装入方式多道程序下，编译程序不可能预知装入模块放在内存中的何处，此时应采用可重定位装入方式。在可重定位装入方式中：物理（绝对）地址=逻辑（相对）地址+内存起始地址可重定位装入方式的地

34、址变换是在装入时一次完成的，以后不再改变，因此叫做静静态重定位重定位可重定位装入方式不允许程序运行时在内存中移动，如果移动，必须对程序和数据的地址进行修改后方能运行。3.3动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。4连续分配方式连续分配方式是指为一个用户程序分配一个连续的内存空间。单一连续分配固定分区分配动态分区分配动态重定位分区分配4.1单一连续分配这是最简单的一种存储器管理方式，只能用于单用户单任务的操作系统。内存被分为系统区（仅提供

35、给OS使用，通常放在内存的低址部分）和用户区（除系统区以外的全部外存空间，提供给用户使用）。4.2固定分区分配这是最简单的一种可运行多道程序的存储管理方式，它的基本思想是将内存划分成若干个固定大小的区域，称为分区。每个分区只能装入一个作业，这样便允许有几道作业并发执行。1.划分分区方法（1）分区大小相等（2）分区大小不等2.内存分配为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表。4.3动态分区分配 内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。1.分区分配中的数

36、据结构（1）空闲分区表：系统中设置一张空闲分区表，用于记录每个空闲分区的情况。始址长度标志15K23K未分配48K20K未分配80K30K未分配空空0K0K15K15K38K38K48K48K68K68K80K80K110K110K120K120K（2）空闲分区链状态位，指示分区是否分配2.分区分配算法为把一个新作业装入内存，需按照一定的分配算法，从空闲分区表（链）中选出一个分区分配给作业。（1）首次适应算法分区的链接方式：地址递增。分配算法：从链首顺序查找一个大小能满足要求的空闲分区，按照作业大小，从中划出一块内存空间分，余下的空闲分区仍留在链中。优点：保留了高址部分的大空闲区。缺点：低址部

37、分不断划分，留下很多难以利用的小的空闲分区。增加查找可用空闲分区的时间。（2）循环首次适应算法分区的链接方式：地址递增。分配算法：从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个大小能满足要求的空闲分区为止。这就需要设置一起始查询指针，用于指示下一次起始查询的空闲分区。优点：空闲分区分布均匀，减少查找时间。缺点：缺乏大的空间。4.4碎片问题 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个不足以满足分配要求，但总和满足分配要求。这些空闲块被称为碎片。紧凑技术：通过在内存移动程序，将所有 小的空闲区域合并为大的空闲区域。4.5可重定位分区分配1.动态重定位的引入2.动态

38、重定位的实现5基本分页存储管理方式5.1离散分配方式的引入在动态分区的存储空间中，存在碎片问题。尽管用“紧凑”技术可以解决，但要花去不少的处理机时间，代价较高。为此，可将一个进程分散的装入许多不相邻接的分区中。5.2离散分配的两种方法分页存储管理方式：离散分配的基本单位是页。分段存储管理方式：离散分配的基本单位是段。5.3基本分页存储管理方式页面（页）（物理）块页内碎片页表实现了从页号到物理块号的映射。分页地址结构12-31位是页号，地址空间最多允许有1M页。0-11位是页内地址即每页大小为4KB页号P位移量W31121101B=8bit（位）1KB=1024B（字节）1MB=1024KB 对

39、某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：P=intA/L d=A mod L例：系统的页面大小为1KB，地址A=2170B，求P和d地址变换机构为了能将用户地址空间的逻辑地址变换为物理地址，在系统中必须设置地址变换机构。由于页内地址和物理块内地址是一一对应的，因此地址变换机构的任务就是将逻辑地址中的页号转换为内存中的物理块号。基本的地址变换机构5.4基本分段存储管理方式1分段存储管理方式的引入 在分页存储系统中，作业的地址空间是一维线性的，破坏了程序内部天然的逻辑结构,造成共享、保护的困难。引入分段存储管理方式，可以

40、满足用户和程序员的下述要求：（1）方便编程（2）信息共享（3）信息保护（4）动态增长（5）动态链接2分段系统的基本原理在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都有自己的名字。为简单起见，通常用段号来代替段名，每个段都从0开始编址。主程序段MAIN子程序段X数据段D段栈S段 号段内地址31 16 15 0段的长度由相应的逻辑信息组的长度决定，因此各段长度不等，整个地址空间被分成多段，因而是二维的。分段方式已经得到许多编译程序的支持，编译程序能根据源程序的情况产生若干个段。每个段最大长度为64KB，允许一个作业最长有64K个段。段表 系统为每个段分配一

41、个连续得分区，进程中的各段可以离散的移入内存中的不同分区。为使能从物理内存中找出每个逻辑段所对应的位置，应设立一个段表。硬件支持系统设置一对寄存器段表始址寄存器：用于保存正在运行进程的段表的始址段表长度寄存器：用于保存正在运行进程的段表的长度（例如上图的段表长度为3）地址变换机构分页和分段的主要区别（1）页是信息的物理单位，段则是信息的逻辑单位。（2）页的大小固定且由系统决定，而段的长度却不固定。（3）分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间则是二维的。6 虚拟存储器 虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留

42、在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。6.1 虚拟存储器的容量 虚拟存储器的逻辑容量由内存与外存的容量之和所确定。6.2 虚拟存储器的实现（1）分页请求系统：在分页系统的基础上，增加了请求调页功能和页面置换功能。（2）请求分段系统：在分段系统的基础上，增加了请求调段和分段置换功能。6.3请求分页存储管理方式 请求分页系统是在分页系统的基础上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求式分页系统在进程开始运行之前，装入部分页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面。请求分页

43、中的硬件支持页表机制状态位：指示该页是否调入内存。访问位：记录该页的访问次数或最近有多长时间未被访问，供选择换出页面时参考。修改位：指示此页是否在内存中被修改过。外存地址：指出该页在外存的地址，供调入时参考。内存分配策略和内存分配算法1.最小物理块的确定最小物理块指能保证进程正常运行所需要的最小物理块数，与计算机的硬件结构有关。2.物理块分配策略固定分配局部置换可变分配全局置换可变分配局部置换 3.物理块分配算法在采用固定分配策略时，将物理块分配给各个进程，可用下述方法平均分配算法按比例分配算法考虑优先权的分配算法 调页策略1.调页策略预调页策略：一次调入若干相邻的页，比一次调入一页更高效。所

44、以可采用预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入。目前调页的成功率约为一半。请求调页策略：当进程要访问的数据所在页面不在内存，便立即提出请求，由OS将所需页面调入内存。该策略每次只调入一页，故系统开销较大。从何处调页文件区文件区 对换区对换区存放文件存放文件存放从内存换出的进程存放从内存换出的进程外存对换区采用的是连续分配方式，文件区采用离散分配方式，故对换区的磁盘IO速度比文件区高。系统拥有足够对换区空间：进程运行前，便将与该进程有关的文件从文件区拷贝到对换区，缺页时全部从对换区调入，提高了调页速度。系统缺少足够的对换区空间：未被修改的文件都直接从文件区调入，被修改的

45、文件，换出时便需调到对换区，以后需要时再从对换区调入。UNIX方式：未运行过的页面都应从文件区调入。曾运行过但又被换出的页面放在对换区，下次调入时，应从对换区调入。页面置换算法 当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。最佳置换算法 先进先出置换算法 最近最久未用置换算法近似的LRU算法（NRU算法）1.最佳置换算法（Optimal）该算法所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但人们无法预知哪个页面最长时间不被访问，因而该算法无法实现，但可用其去评价其他算法。假

46、定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 2.先进先出置换算法（FIFO）该算法总是淘汰最先进入内存的页面。3.最近最久未使用置换算法（LRU）该算法选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。LRU置换算法的硬件支持（1）寄存器：为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为:R=Rn-1Rn-2Rn-3 R2R1R0 当进程访问相应物理块时，要将相应寄存器Rn-1位置为1，然后每隔一段时间就将寄存器右移一位。具有最

47、小数值的寄存器所对应页面就是最近最久未使用的页面。（2）栈：可以用栈来保存当前使用的各个页面的页面号，每当进程访问某页面时，便将该页面的页面号从栈中移出，压入栈顶。栈底的页面就是最近最久未使用页面。7请求分段存储管理方式 请求分段系统在进程开始运行之前，只需调入若干个分段，之后根据进程运行的需要，动态调入所缺段。4.8.1请求分段中的硬件支持1.段表机制段的基址：段在内存中的起始地址。存取方式：标识本段的读写存取属性。访问位：记录该段的访问次数或最近有多长时间未被访问，供选择换出段时参考。修改位：指示此段是否在内存中被修改过。存在位：指示此段是否调入内存增补位：表示本段在运行过程中是否做过动态增长。外存始址：指出该段在外存的起始地址。