第五章内存管理课件

第五章第五章 存储管理存储管理 软件称为计算机的灵魂，存储器软件称为计算机的灵魂，存储器则是灵魂展现活力的舞台，栖身的场则是灵魂展现活力的舞台，栖身的场所，也是与人交互信息的通道。所，也是与人交互信息的通道。第五章存储管理软件称为计算机的灵魂，存储器则是灵魂内内存存是是CPUCPU直直接接存存取取指指令令和和数数据据的的存存储储器器。任任何何一一个个程程序序（包包括括应应用用程程序序和和OSOS本本身身）必必须须被被装装入入内内存存，才才可可能能被被执执行行。尽尽管管RAMRAM芯芯片片集集成成度度越越狱狱越越来来越越高高，价价格格不不断断降降低低，由由于于其其需需求求量量大大，整整体体价价格格仍仍较较昂昂贵贵，而而且且受受CPUCPU寻寻址址能能力力的的限限制制，内内存存容容量量仍仍有有限限。因因此此，对对主主存存的的管管理理和和有有效效利利用用仍仍然然是是当当含含今今操操作作系系统统十十分分重重要要的的内内容容。内内存存区区域域被被分分为为两两大大区区域域：系系统统空空间间，用用户户进进程程空空间间。本本章章主主要要讲讲述述用用户户区区域域的的管理方法和基本技术管理方法和基本技术内存是CPU直接存取指令和数据的存储器。任何一个程序（包本章主要内容5.1存储管理基本概念存储管理基本概念5.2分区式存储管理分区式存储管理5.3页式存储管理页式存储管理5.4淘汰算法与抖动现象淘汰算法与抖动现象5.5段式存储管理段式存储管理5.6段页式存储管理段页式存储管理本章主要内容5.1存储管理基本概念5.2分区式存储管理55.1.15.1.1物理内存和虚拟存储器物理内存和虚拟存储器物理内存和虚拟存储器物理内存和虚拟存储器1.1.1.1.物理内存物理内存物理内存物理内存 0000000000000000HH00000001H00000001H003FFFFEH003FFFFEH003FFFFFH003FFFFFH4 4MBMB物理地址空间物理地址空间物理地址空间物理地址空间5.1存储管理基本概念存储管理基本概念2 2虚拟地址（相对地址）：相对于某个基准量（例虚拟地址（相对地址）：相对于某个基准量（例虚拟地址（相对地址）：相对于某个基准量（例虚拟地址（相对地址）：相对于某个基准量（例0 0）编址）编址）编址）编址时所使用的地址。时所使用的地址。时所使用的地址。时所使用的地址。用户程序经编译后形成一个以用户程序经编译后形成一个以用户程序经编译后形成一个以用户程序经编译后形成一个以0 0地址为始地址的线性或多地址为始地址的线性或多地址为始地址的线性或多地址为始地址的线性或多维虚地址空间，这样每个进程都有这样一个空间。每个指令维虚地址空间，这样每个进程都有这样一个空间。每个指令维虚地址空间，这样每个进程都有这样一个空间。每个指令维虚地址空间，这样每个进程都有这样一个空间。每个指令或数据单元都在这个虚空间中拥有的地址，称为虚拟地址或数据单元都在这个虚空间中拥有的地址，称为虚拟地址或数据单元都在这个虚空间中拥有的地址，称为虚拟地址或数据单元都在这个虚空间中拥有的地址，称为虚拟地址（逻辑地址）（逻辑地址）（逻辑地址）（逻辑地址）5.1.1物理内存和虚拟存储器1.物理内存00000003 3虚虚虚虚拟拟拟拟存存存存储储储储器器器器：进进进进程程程程中中中中目目目目标标标标代代代代码码码码、数数数数据据据据等等等等的的的的虚虚虚虚拟拟拟拟地地地地址址址址组组组组成成成成的的的的空空空空间间间间称称称称为为为为虚虚虚虚拟拟拟拟存存存存储储储储器器器器。不不不不考考考考虑虑虑虑物物物物理理理理内内内内存存存存的的的的大大大大小小小小和和和和信信信信息息息息存存存存放放放放的的的的实实实实际际际际地地地地址址址址，它它它它只只只只考考考考虑虑虑虑相相相相互互互互关关关关连连连连的的的的信信信信息息息息之之之之间间间间的的的的相相相相对对对对位位位位置置置置，其其其其容容容容量量量量只只只只受受受受计计计计算算算算机机机机的的的的寻寻寻寻址址址址方方方方式式式式和和和和地地地地址址址址结结结结构构构构限限限限制制制制。每每每每个个个个进进进进程程程程拥拥拥拥有有有有自自自自己己己己的的的的虚虚虚虚拟拟拟拟存储器。可以为用户提供比实际内存更大的空间。存储器。可以为用户提供比实际内存更大的空间。存储器。可以为用户提供比实际内存更大的空间。存储器。可以为用户提供比实际内存更大的空间。5.1.25.1.2存储管理的主要任务（目的、研究的课题）存储管理的主要任务（目的、研究的课题）存储管理的主要任务（目的、研究的课题）存储管理的主要任务（目的、研究的课题）1.1.1.1.内存的分配与回收内存的分配与回收内存的分配与回收内存的分配与回收 2 2地址变换地址变换地址变换地址变换（1 1）地址重定位：）地址重定位：）地址重定位：）地址重定位：（2 2）静静静静态态态态地地地地址址址址重重重重定定定定位位位位：例例例例：假假假假设设设设目目目目标标标标程程程程序序序序分分分分配配配配的的的的内内内内存存存存起起起起始始始始地地地地址址址址为为为为BABA，目目目目标标标标程程程程序序序序中中中中的的的的某某某某条条条条指指指指令令令令或或或或数数数数据据据据的的的的虚虚虚虚拟拟拟拟地地地地址址址址为为为为VAVA，则则则则其其其其对对对对应的物理地址是应的物理地址是应的物理地址是应的物理地址是MAMABABAVAVA。（3 3）动动动动态态态态地地地地址址址址重重重重定定定定位位位位：地地地地址址址址变变变变换换换换机机机机构构构构通通通通常常常常由由由由一一一一个个个个公公公公用用用用的的的的基基基基址址址址寄寄寄寄存存存存器器器器BRBR和和和和一一一一个个个个（或或或或多多多多个个个个）虚虚虚虚拟拟拟拟地地地地址址址址寄寄寄寄存存存存器器器器VRVR组组组组成成成成。只只只只要要要要改改改改变变变变BRBR的内容，就可以改变程序在内存的存放空间。的内容，就可以改变程序在内存的存放空间。的内容，就可以改变程序在内存的存放空间。的内容，就可以改变程序在内存的存放空间。3虚拟存储器：进程中目标代码、数据等的虚拟地址组成的空间称100100BRBR+1001001 1100 222100 22221002100内存内存内存内存LOAD 1,1000LOAD 1,10006006000 05005001000 222 1000 222 某程序的地址空间某程序的地址空间某程序的地址空间某程序的地址空间200020001001001 1100 222100 22221002100内存内存内存内存LOAD 1,1100LOAD 1,11006006002222220 050050010001000某程序的地址空间某程序的地址空间某程序的地址空间某程序的地址空间20002000LOAD 1,1100LOAD 1,1100LOAD 1,1000LOAD 1,1000100BR+10011002222100内存LOAD1,3.3.3.3.内存信息的共享和保护内存信息的共享和保护内存信息的共享和保护内存信息的共享和保护如：如：如：如：当前的程序状态字为当前的程序状态字为当前的程序状态字为当前的程序状态字为2 24.4.4.4.内存扩充内存扩充内存扩充内存扩充正确的访问正确的访问正确的访问正确的访问：LOAD1,5000STORE2,5200LOAD2,7000不正确的访问不正确的访问不正确的访问不正确的访问：LOAD1,2500读写保护STORE1,7000写保护2k4k6k8k0RW2W3W内存内存常用的保护方法：上下界保护法；保护键法；常用的保护方法：上下界保护法；保护键法；常用的保护方法：上下界保护法；保护键法；常用的保护方法：上下界保护法；保护键法；3.内存信息的共享和保护如：当前的程序状态字为24.内存扩5.2.15.2.1固定式分区（静态分区）固定式分区（静态分区）固定式分区（静态分区）固定式分区（静态分区）优缺点：技术简单；但主存利用率不高，存在严重的优缺点：技术简单；但主存利用率不高，存在严重的优缺点：技术简单；但主存利用率不高，存在严重的优缺点：技术简单；但主存利用率不高，存在严重的内碎片内碎片内碎片内碎片。5.2分区式存储管理分区式存储管理分区的基本思想是将内存区域划分成若干个大小不等的区分区的基本思想是将内存区域划分成若干个大小不等的区域，每个区域称为一个分区，每个分区存放一道进程对应的程域，每个区域称为一个分区，每个分区存放一道进程对应的程序和数据，使进程在内存中占用一个连续的区域，而且进程只序和数据，使进程在内存中占用一个连续的区域，而且进程只能在所在分区内运行。能在所在分区内运行。操作系统操作系统进程进程A(6KB)进程进程B(35KB)020KB124KB256KB60KB28KB1分区分区2分区分区3分区分区4分区分区区号分区长度起始地址状态18KB20KB1232KB28KB0364KB60KB14132KB124KB0固定分区：个数、大小不变。固定分区：个数、大小不变。固定分区：个数、大小不变。固定分区：个数、大小不变。5.2.1固定式分区（静态分区）优缺点：技术简单；但主存5.2.25.2.2可变式分区（动态分区）可变式分区（动态分区）可变式分区（动态分区）可变式分区（动态分区）操作系统操作系统进程进程D(70KB)操作系统操作系统进程进程E(40KB)操作系统操作系统进程进程E(40KB)进程进程A(16KB)进程进程A(16KB)(26KB)(10KB)(10KB)进程进程B(90KB)进程进程B(90KB)进程进程B(90KB)进程进程C(30KB)进程进程C(30KB)(30KB)(94KB)进程进程D(70KB)进程进程D(70KB)(24KB)(24KB)(a)某时刻状态某时刻状态(b)加入进程加入进程D(c)撤销进程撤销进程A和和C1.1.分区大小、个数变化。分区大小、个数变化。分区大小、个数变化。分区大小、个数变化。内碎片，拼接内碎片，拼接内碎片，拼接内碎片，拼接2.2.分配与释放：已分配分区表和空闲分区表（链）分配与释放：已分配分区表和空闲分区表（链）分配与释放：已分配分区表和空闲分区表（链）分配与释放：已分配分区表和空闲分区表（链）5.2.2可变式分区（动态分区）操作系统进程D(70KB)3.地址变换与内存保护地址变换与内存保护基址寄存器基址寄存器BR和限长寄存器和限长寄存器LR。假设。假设CPU要访问的逻要访问的逻辑地址辑地址LA，若，若LALR，则说明地址越界，将产生保护性地，则说明地址越界，将产生保护性地址越界中断，系统转出错处理。若址越界中断，系统转出错处理。若LALR，则，则LA与与BR中中的基址形成有效的物理地址的基址形成有效的物理地址PA。4.优缺点优缺点主要优点：主要优点：（1）实现了多个作业或进程对内存的共享，有助于多道程序）实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。设计，从而提高了系统的资源利用率。（2）该方法要求的硬件支持少，管理算法简单，因而实现容）该方法要求的硬件支持少，管理算法简单，因而实现容易。易。主要缺点：主要缺点：（1）内存利用率仍然不高。存在着严重的碎小空闲区（碎片）内存利用率仍然不高。存在着严重的碎小空闲区（碎片）不能利用的问题。不能利用的问题。（2）作业或进程的大小受分区大小控制，除非配合采用覆盖）作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术来实现内存的扩充。和交换技术来实现内存的扩充。（3）难以实现各分区间的信息共享。）难以实现各分区间的信息共享。3.地址变换与内存保护基址寄存器BR和限长寄存器LR。5.3页式存储管理页式存储管理 在分区式存储管理方案中，一个进程总占用一块连续的在分区式存储管理方案中，一个进程总占用一块连续的内存区域，因此产生了内存区域，因此产生了“零头零头”问题。虽然采用拼接技术可问题。虽然采用拼接技术可以使零散的以使零散的“零头零头”连成一片，但要花费大量的处理机时间。连成一片，但要花费大量的处理机时间。为了更好地解决零头问题，人们提出了另一种内存存储管理为了更好地解决零头问题，人们提出了另一种内存存储管理方案，即方案，即分页式存储管理方案分页式存储管理方案。该管理方案将一个进程存放。该管理方案将一个进程存放在不连续的内存区域中。有在不连续的内存区域中。有静态页式管理和动态页静态页式管理和动态页式管理。式管理。5.3页式存储管理在分区式存储管理方案中，一基本原理基本原理 系统首先把内存的存储空间等分成若干个大小相系统首先把内存的存储空间等分成若干个大小相系统首先把内存的存储空间等分成若干个大小相系统首先把内存的存储空间等分成若干个大小相等的小区域，每个小区域称之为等的小区域，每个小区域称之为等的小区域，每个小区域称之为等的小区域，每个小区域称之为页面或存储块页面或存储块页面或存储块页面或存储块。页面页面页面页面按按按按0 0、1 1、2 2、3 3 的格式依次编号。同样，进程的虚的格式依次编号。同样，进程的虚的格式依次编号。同样，进程的虚的格式依次编号。同样，进程的虚拟地址空间也被分成若个与页面大小相等的多个片段，拟地址空间也被分成若个与页面大小相等的多个片段，拟地址空间也被分成若个与页面大小相等的多个片段，拟地址空间也被分成若个与页面大小相等的多个片段，称之为称之为称之为称之为页页页页，编号为编号为编号为编号为0 0、1 1、2 2、3 3 。分配内存时，进。分配内存时，进。分配内存时，进。分配内存时，进程的每一个页装入内存的一个页面，有静态和动态分程的每一个页装入内存的一个页面，有静态和动态分程的每一个页装入内存的一个页面，有静态和动态分程的每一个页装入内存的一个页面，有静态和动态分配配配配(一次全部满足或部分满足）一次全部满足或部分满足）一次全部满足或部分满足）一次全部满足或部分满足）。同一进程的多个页同一进程的多个页同一进程的多个页同一进程的多个页可以分配在页号不连续的页面内。可以分配在页号不连续的页面内。可以分配在页号不连续的页面内。可以分配在页号不连续的页面内。5.3.15.3.1静态页式管理静态页式管理静态页式管理静态页式管理1.1.内存分配内存分配内存分配内存分配基本原理5.3.1静态页式管理1.内存分配进程进程进程进程1 1的虚拟地址空间的虚拟地址空间的虚拟地址空间的虚拟地址空间012页号页号页号页号进程的静态内存分配进程的静态内存分配进程的静态内存分配进程的静态内存分配。121314151617181920内存内存内存内存 OSOS进程进程进程进程1 1进程进程进程进程1 1进程进程进程进程2 2进程进程进程进程2 2进程进程进程进程2 2进程进程进程进程1 1进程进程进程进程2 201234页号页号页号页号进程进程进程进程2 2进程进程进程进程2 2的虚拟地址空间的虚拟地址空间的虚拟地址空间的虚拟地址空间。进程1的虚拟地址空间012页号进程的静态内存分配（1 1）页表）页表2.2.数据结构数据结构（2 2）请求表）请求表（3 3）存储页面表）存储页面表（1）页表一个进程往往有多个页，而这些页在内存可以不连续存 页表如下图所示页表如下图所示：页号页面号012113218进程进程进程进程1 1页表页表页表页表 作用：1.1.1.1.记录一个进程在内存中的分配情况；记录一个进程在内存中的分配情况；记录一个进程在内存中的分配情况；记录一个进程在内存中的分配情况；2.2.2.2.实现逻辑地址到物理地址的变换。实现逻辑地址到物理地址的变换。实现逻辑地址到物理地址的变换。实现逻辑地址到物理地址的变换。进程进程进程进程 2 2页表页表页表页表页号页面号014115217319420页表如下图所示：页号页面号0121133 3 3 3.地址结构及地址变换地址结构及地址变换地址结构及地址变换地址结构及地址变换（1 1）地址结构）地址结构）地址结构）地址结构在学习利用在学习利用在学习利用在学习利用页表是怎样完成地址变换之前，必须了解地址页表是怎样完成地址变换之前，必须了解地址页表是怎样完成地址变换之前，必须了解地址页表是怎样完成地址变换之前，必须了解地址结构。在页面管理中，分页系统自动把逻辑地址解释为两部分，结构。在页面管理中，分页系统自动把逻辑地址解释为两部分，结构。在页面管理中，分页系统自动把逻辑地址解释为两部分，结构。在页面管理中，分页系统自动把逻辑地址解释为两部分，高位部分为页号，低位部分为页内地址。因此，逻辑地址用一个高位部分为页号，低位部分为页内地址。因此，逻辑地址用一个高位部分为页号，低位部分为页内地址。因此，逻辑地址用一个高位部分为页号，低位部分为页内地址。因此，逻辑地址用一个数对数对数对数对（p,dp,dp,dp,d）来表示，其中来表示，其中来表示，其中来表示，其中p p p p表示所在的页号，表示所在的页号，表示所在的页号，表示所在的页号，d d d d表示页内地址。表示页内地址。表示页内地址。表示页内地址。d d d d、p p p p所占的位数取决于页的大小。所占的位数取决于页的大小。所占的位数取决于页的大小。所占的位数取决于页的大小。为了简化地址变换过程和分页，通常页的大小为为了简化地址变换过程和分页，通常页的大小为为了简化地址变换过程和分页，通常页的大小为为了简化地址变换过程和分页，通常页的大小为2 2的的的的n n次幂。次幂。次幂。次幂。如：如：如：如：1024(21024(21010)=1)=1k,4096(2k,4096(21212)=4k)=4k。若页的大小为若页的大小为若页的大小为若页的大小为2 2n n，则则则则 d=nd=n p=p=有效地址长度有效地址长度有效地址长度有效地址长度-n n3.地址结构及地址变换（1）地址结构为了简化地址变换过程和分例：假设计算机CPU有效地址为16位，且页大小为1K。分页系统的地变换机构自动把这个地址解释为分页系统的地变换机构自动把这个地址解释为分页系统的地变换机构自动把这个地址解释为分页系统的地变换机构自动把这个地址解释为页号（页号（页号（页号（6 6 6 6位）和页内相对地址位）和页内相对地址位）和页内相对地址位）和页内相对地址d d d d（10101010位）。位）。位）。位）。0 pd159地址构图地址构图地址构图地址构图d=452 10 01110001002500p=2例例：十进制地址：十进制地址：十进制地址：十进制地址：二进制地址：二进制地址：二进制地址：二进制地址：计算方法：计算方法：若给出一个逻辑地址为若给出一个逻辑地址为若给出一个逻辑地址为若给出一个逻辑地址为A A，页面大页面大页面大页面大小为小为小为小为L L（字节），则：字节），则：字节），则：字节），则：p pint(A/L)int(A/L)d=(A)mod(L)d=(A)mod(L)。例：假设计算机CPU有效地址为16位，且页大小为1K。（2 2）地址变换）地址变换）地址变换）地址变换首先，当进程被调度运行，操作系统自动将该进程的首先，当进程被调度运行，操作系统自动将该进程的首先，当进程被调度运行，操作系统自动将该进程的首先，当进程被调度运行，操作系统自动将该进程的页表起址和页表长度（该地址通常在页表起址和页表长度（该地址通常在页表起址和页表长度（该地址通常在页表起址和页表长度（该地址通常在PCBPCB内），装入页表地内），装入页表地内），装入页表地内），装入页表地址寄存器中，当址寄存器中，当址寄存器中，当址寄存器中，当CPUCPU访问某个虚拟地址时，分页系统硬件机访问某个虚拟地址时，分页系统硬件机访问某个虚拟地址时，分页系统硬件机访问某个虚拟地址时，分页系统硬件机构自动完成逻辑地址到物理地址的转换。构自动完成逻辑地址到物理地址的转换。构自动完成逻辑地址到物理地址的转换。构自动完成逻辑地址到物理地址的转换。例：例：例：例：设页的大小为设页的大小为设页的大小为设页的大小为1 1KK，某进程有一条指令某进程有一条指令某进程有一条指令某进程有一条指令LOAD 1LOAD 1，25002500，当当当当CPUCPU访问这条指令时，要进行访问这条指令时，要进行访问这条指令时，要进行访问这条指令时，要进行地址变换地址变换地址变换地址变换。5.3.25.3.2动态页式管理动态页式管理动态页式管理动态页式管理1.1.内存中的页称为内存中的页称为“实页实页”，把在外存中页称为，把在外存中页称为“虚页虚页”。2 2 2 2页表页表页表页表 页号页号页面页面号号驻留驻留位位访问访问位位修改修改位位外存外存地地址址3 3 3 3缺页中断机构缺页中断机构缺页中断机构缺页中断机构（2）地址变换5.3.2动态页式管理1.内存中的页称为“页表长度页表长度 页表地址页表地址控制寄存器控制寄存器22452452有效地址有效地址页号页号 页面号页面号00221133228888452452物理地址物理地址102420482900虚拟空间虚拟空间10010002500250012341234。内内 存存LOAD1,2500LOAD1,25001234123421488644页表长度页表地址控制寄存器2452有效地址页号页面号5.3.35.3.3指令存取速度与页面大小的问题指令存取速度与页面大小的问题指令存取速度与页面大小的问题指令存取速度与页面大小的问题 1.1.1.1.页面大小的选择页面大小的选择页面大小的选择页面大小的选择如果页面太大，页式管理就退化为分区管理，同时导致页如果页面太大，页式管理就退化为分区管理，同时导致页如果页面太大，页式管理就退化为分区管理，同时导致页如果页面太大，页式管理就退化为分区管理，同时导致页内内内内“碎片碎片碎片碎片”过大。而页面太小，页表占用内存空间太多。一个过大。而页面太小，页表占用内存空间太多。一个过大。而页面太小，页表占用内存空间太多。一个过大。而页面太小，页表占用内存空间太多。一个系统的页表占用内存的空间大小与主存大小和页大小有关。系统的页表占用内存的空间大小与主存大小和页大小有关。系统的页表占用内存的空间大小与主存大小和页大小有关。系统的页表占用内存的空间大小与主存大小和页大小有关。如：内存大小为如：内存大小为如：内存大小为如：内存大小为1616兆，页大小为兆，页大小为兆，页大小为兆，页大小为2 2K K，则页面数为则页面数为则页面数为则页面数为 16 16*1024/2=81921024/2=8192（个）（个）（个）（个）若一个页表的表目占若一个页表的表目占若一个页表的表目占若一个页表的表目占2 2个字节，那么页表占用内存的空间大小个字节，那么页表占用内存的空间大小个字节，那么页表占用内存的空间大小个字节，那么页表占用内存的空间大小 8192 8192*2/1024=16 2/1024=16K K2.2.2.2.指令访问速度指令访问速度指令访问速度指令访问速度 页式管理系统中，存取一个数据或访问一条指令要访问两次页式管理系统中，存取一个数据或访问一条指令要访问两次页式管理系统中，存取一个数据或访问一条指令要访问两次页式管理系统中，存取一个数据或访问一条指令要访问两次主存：页表、真正的内存地址。显然，这种方法比通常执行指令主存：页表、真正的内存地址。显然，这种方法比通常执行指令主存：页表、真正的内存地址。显然，这种方法比通常执行指令主存：页表、真正的内存地址。显然，这种方法比通常执行指令的速度慢了一倍。的速度慢了一倍。的速度慢了一倍。的速度慢了一倍。为了提高查表速度，可在地址变换机构中增设一个具有并行查为了提高查表速度，可在地址变换机构中增设一个具有并行查为了提高查表速度，可在地址变换机构中增设一个具有并行查为了提高查表速度，可在地址变换机构中增设一个具有并行查找能力的高速寄存器来存储当前常用的页号和对应的页面号。这找能力的高速寄存器来存储当前常用的页号和对应的页面号。这找能力的高速寄存器来存储当前常用的页号和对应的页面号。这找能力的高速寄存器来存储当前常用的页号和对应的页面号。这些高速寄存器称之为些高速寄存器称之为些高速寄存器称之为些高速寄存器称之为快表快表快表快表。5.3.3指令存取速度与页面大小的问题2.指令访问速度在地址变换过程中，首先查找快表，若要找的页号p在快表5.4 淘汰算法与抖动淘汰算法与抖动 5.4.1 5.4.1 淘汰算法淘汰算法淘汰算法淘汰算法 1 1 最佳（最佳（OptimalOptimal）淘汰算法淘汰算法通常把选择要换出页的算法称为淘汰算法。而一个好的通常把选择要换出页的算法称为淘汰算法。而一个好的淘汰算法，应使缺页率尽可能小。淘汰算法，应使缺页率尽可能小。访页顺序访页顺序0253242032132343内内存存实实页页000000000011114422222222222222253344433333333缺页中断缺页中断它可作为衡量其它算法优劣的一个标准。它可作为衡量其它算法优劣的一个标准。5.4淘汰算法与抖动5.4.1淘汰算法12.先进先出淘汰算法先进先出淘汰算法访页顺序序0 02 25 53 32 24 42 20 03 32 21 13 32 23 34 43 3内内存存实页0 00 00 03 33 33 33 30 00 00 00 00 02 22 22 22 22 22 22 22 24 44 44 43 32 23 33 33 33 34 44 45 55 55 55 52 22 22 23 31 11 11 11 11 13 3缺缺页中断中断FIFOFIFO算法容易实现，但是它所依据的理由与普遍的进程运行算法容易实现，但是它所依据的理由与普遍的进程运行规律不符。它只适用于规律不符。它只适用于CPUCPU按线性顺序访问地址空间的进程。按线性顺序访问地址空间的进程。BeladyBelady现象：在未给进程或作业分配足它所要求的页面数时，现象：在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多时，缺页的次数反而会增加的陷有时会出现分配的页面数增多时，缺页的次数反而会增加的陷阱现象。阱现象。2.先进先出淘汰算法访页顺序02532420321323.最近最少使用（最近最少使用（LRU）淘汰算法）淘汰算法访页顺序访页顺序0253242032132343内内存存实实页页000333300011114422222222222222255544433333333缺页中断缺页中断（1）计数器法（2）栈（3）寄存器法 R实页实页R7R6R5R4R3R2R1R0101010010210101100300000100401101011511010110600000011 LRU LRU虽然是一种较好的淘汰算法，但是完全实现虽然是一种较好的淘汰算法，但是完全实现LRULRU淘淘汰算法的代价比较大。汰算法的代价比较大。3.最近最少使用（LRU）淘汰算法访页顺序04 4LRULRU的近似算法的近似算法（1）最近未使用NUR算法。第1类：R0，M0，没有被访问过，没有被修改过，是最佳的淘汰页；第2类：R0，M1，没有被访问过，被修改过；第3类：R1，M0，被访问过，没有被修改过；第4类：R1，M1，被访问过，被修改过；(2）最不经常使用NFU（NotFrequentlyUsed）算法。该算法是在需要淘汰某一页时，选择到当前时间为止，被访问次数最少的那一页。这只需在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加1，而发生缺页时，则淘汰计数器值最小的那一页，并将所有的计数器清零。4LRU的近似算法（1）最近未使用NUR算法。(2）最不经5.4.2 5.4.2 抖动现象与工作集抖动现象与工作集抖动现象与工作集抖动现象与工作集系统需要花费大量的时间忙于进行这种频繁的页面调换，从系统需要花费大量的时间忙于进行这种频繁的页面调换，从而无法完成用户所要求的工作。这种现象称之为而无法完成用户所要求的工作。这种现象称之为“抖动现象抖动现象”现现象。象。防止抖动现象方法：一种是选择好的淘汰算法，以减少缺页防止抖动现象方法：一种是选择好的淘汰算法，以减少缺页次数。一种是扩大次数。一种是扩大工作集工作集:是指进程在某个时间段里要访问的页的是指进程在某个时间段里要访问的页的集合。如果能够预知进程在某段时间的工作集，并在此之前把该集合。如果能够预知进程在某段时间的工作集，并在此之前把该集合调入内存，至该段时间终了时，再将其在下一时间段时不需集合调入内存，至该段时间终了时，再将其在下一时间段时不需要访问的哪些页换出内存，这样就会可以减少页的交换。要访问的哪些页换出内存，这样就会可以减少页的交换。5.4.2抖动现象与工作集系统需要5.5.1 5.5.1 静态段式存储管理静态段式存储管理静态段式存储管理静态段式存储管理 1 1 1 1思想思想思想思想 2 2 2 2地址空间和地址结构地址空间和地址结构地址空间和地址结构地址空间和地址结构例：例：例：例：CALL X|CALL X|CALL X|CALL X|；LOAD 1,A|6LOAD 1,A|6LOAD 1,A|6LOAD 1,A|6；STORE 1,B|STORE 1,B|STORE 1,B|STORE 1,B|。3 3 3 3数据结构数据结构数据结构数据结构 5.5 段式存储管段式存储管理理s s w w 232316 1516 150 0CALL 3,120CALL 3,120（1）段表：）段表：（2）内存空闲区表（或链）：）内存空闲区表（或链）：（3）请求表：）请求表：5.5.1静态段式存储管理1思想2地址空间和地段、段表及段在内存空间占用情况3.地址变换段、段表及段在内存空间占用情况3.地址变换5.5.2 5.5.2 动态段式存储管理动态段式存储管理动态段式存储管理动态段式存储管理段段号号内存内存始始址址段段长驻留留位位访问位位修改修改位位外存外存地地址址存取存取方方式式增增补位位段表段表缺段中断处理缺段中断处理5.5.2动态段式存储管理段号内存始址段长驻留位访问5.5.3 5.5.3 分段和分页的主要区别分段和分页的主要区别分段和分页的主要区别分段和分页的主要区别（1）段是面向用户的，页是面向系统的。（2）页的大小是固定的，由系统决定；段的大小不固定，由用户决定。（3）从用户的角度看，分页系统的用户程序空间是一维连续的线性空间；段的地址空间是二维的，由段名和段内相对地址组成。（4）从管理的角度看，分页系统的二维地址是在地址变换过程中由系统的硬件机构实现的，对用户是透明的。分段系统的在地址变换过程中的二维地址是由用户提供的。因而，页内没有地址越界问题，而段内的相对地址则存在地址越界问题。5.5.45.5.4段的信息共享段的信息共享段的信息共享段的信息共享5.5.3分段和分页的主要区别（1）段是面向用户5.5.55.5.5段的动态链接段的动态链接段的动态链接段的动态链接（1）静态链接（2）动态链接5.5.5段的动态链接（1）静态链接（2）动态链接5.5.75.5.7段式存储管理的优缺点段式存储管理的优缺点段式存储管理的优缺点段式存储管理的优缺点1优点优点（1）便于信息的共享和保护。）便于信息的共享和保护。（2）实现了内存的扩充。）实现了内存的扩充。（3）便于信息的变化处理。）便于信息的变化处理。（4）便于实现动态链接。）便于实现动态链接。2缺点缺点（1）增加了计算机成本。）增加了计算机成本。（2）存在碎片问题。）存在碎片问题。（3）段的长度受内存可用空间大小的限制。）段的长度受内存可用空间大小的限制。（4）与页式存储管理类似，淘汰算法选择不当，可能产）与页式存储管理类似，淘汰算法选择不当，可能产生抖动现象。生抖动现象。5.5.65.5.6段式存储管理的内存保护段式存储管理的内存保护段式存储管理的内存保护段式存储管理的内存保护地址越界保护法存取控制保护法地址越界保护法地址越界保护法 存取控制保护法存取控制保护法 5.5.7段式存储管理的优缺点5.5.6段式存储管理的内5.5段页式存储管理段页式存储管理 段段式式存存储储管管理理大大大大方方便便了了用用户户，便便于于信信息息共共享享和和信信息息的的动动态态增增加加，但但存存在在内内存存的的碎碎片片问问题题。页页式式存存储储管管理理则则大大大大提提高高了了主主存存的的利利用用率率，但但不不便便于于信信息息的的共共享享。因因此此，结结合合二二者者的的优优点点的的一一种种新新的的存存储储管管理理方方案案被被提提了了出出来来，这这就就是是段段页页式存储管理。式存储管理。5.5段页式存储管理段式存储管理大大方1.1.基本思想：用户段式，系统页式。基本思想：用户段式，系统页式。基本思想：用户段式，系统页式。基本思想：用户段式，系统页式。2.2.数据结构：一进程一个段表，每一段对应一个页表。数据结构：一进程一个段表，每一段对应一个页表。数据结构：一进程一个段表，每一段对应一个页表。数据结构：一进程一个段表，每一段对应一个页表。5.6.15.6.1实现原理实现原理实现原理实现原理1.基本思想：用户段式，系统页式。5.6.1实现原理3.3.地址结构及地址变换地址结构及地址变换地址结构及地址变换地址结构及地址变换结构：（结构：（结构：（结构：（s,s,（p,dp,d）5.6.2 5.6.2 段页式存储管理的其它问题段页式存储管理的其它问题段页式存储管理的其它问题段页式存储管理的其它问题3.地址结构及地址变换5.6.2段页式存储管理的其它问题