操作系统 第4章 存储管理ppt课件

.,1,第4章存储管理,.,2,学习目标1.掌握存储管理的主要功能；2.掌握连续分配存储管理方式的实现；3.掌握离散分配存储管理方式的实现；4.掌握虚拟存储器的概念；5.掌握请求分页存储管理的页面分配算法；6.了解Linux中的存储管理。,.,3,存储器可分为：主存（内存）：速度快，价格贵，容量有限，暂时性存储辅存（外存）：速度慢，价格低廉，大容量，永久性存储,.,4,4.1存储管理的概念4.2连续分配方式4.3离散分配方式4.4虚拟存储器4.5Linux中的存储管理,.,5,4.1.1存储管理的功能,OS系统区,用户区,一般占据内存的低地址部分，存放操作系统内核程序，系统其它常驻程序。,存放用户程序和数据以及在用户态下运行的系统程序，它是用户作业可共享的内存区。,内存：,.,6,内存的分配和回收分配:存储管理系统对内存进行统一的分配,找出足够的空闲区分配给申请者,尽量减少“零头”;共享:在多道程序环境下，内存中的某些用户程序、系统程序、数据段可供不同的用户进程共享，以提供内存空间的利用率;回收:作业撤离或主动归还内存资源时，存储管理系统回收作业所占用的内存空间，使它们成为空闲区部分。,存储管理的功能,.,7,地址映射逻辑地址物理地址(进程地址空间中使用)(存储空间中使用）地址映射一般需要硬件或软件的配合。,.,8,逻辑地址、物理地址和地址映射,.,9,存储保护确保进入主存的每道程序都在自己的内存空间运行，互不干扰。既要防止一道程序由于发生错误而破坏其他程序，也要防止破坏系统程序。这种保护一般由硬件和软件配合完成。扩充主存容量借助于虚拟存储技术或其他自己覆盖技术，为用户提供比主存空间大的地址空间，从而达到扩充主存容量的目的。,.,10,4.1.2存储管理的方式,单道程序,多道程序,分“页”和分“块”,分“段”,.,11,覆盖和对换技术是解决大作业和小内存矛盾的两种存储管理技术，是多道程序环境下用来扩充内存的两种方法，其实质是对内存进行逻辑扩充。覆盖主要用于早期的操作系统，而对换在现代操作系统中仍具有较强的生命力。,4.1.3覆盖与对换技术,.,12,覆盖技术的思想：一个程序并不需要一开始就把它的全部信息装入内存再开始执行，不妨把程序划分成若干个功能上相对独立的程序段，并按照程序的逻辑结构，让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存(如磁盘)中，当有关程序段的先头程序段执行结束后，再把后续程序段调入内存中覆盖前面的程序段。,1.覆盖技术,.,13,图4.1覆盖示例,注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；,.,14,应用：系统程序的内部管理；优点：它打破了需要将一个程序的全部信息装入内存后程序才能运行的限制。它利用了相互独立的程序段之间的相互覆盖，逻辑上扩充了内存空间，从而在某种程度上实现了在小容量内存上运行较大的程序。缺点：规模较大或较复杂的程序难以分析和建立覆盖结构。,.,15,对换(或称交换)：是指把内存中暂不能运行的进程，或暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据，换入内存。对换是提高内存利用率的有效措施。以整个进程为单位，称之为“进程对换”；若对换以“页”或“段”为单位进行，则分别称之为“页面对换”或“分段对换”。为了实现进程对换，系统必须实现3个方面的功能：对换空间的管理、进程的换出以及进程的换入。,2.对换技术,.,16,4.1存储管理的概念4.2连续分配方式4.3离散分配方式4.4虚拟存储器4.5Linux中的存储管理,.,17,内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。但实际上用户程序往往只占用用户空间的一部分，最后要剩下一块连续空间，这部分空间将被浪费掉。适用于单用户、单任务的OS。优点是方法简单、易于实现。缺点是它仅适用于单道系统，因而不能使处理机和内存得到充分利用。,4.2.1单一连续分配,.,18,图4.2单一连续分配举例,即：系统区,浪费！,.,19,把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个或几个分区。操作系统占用其中一个分区。应用：适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享。问题：可能存在内零头和外零头。内零头：占用分区之内未被利用的空间外零头：占用分区之间难以利用的空闲分区（通常是小空闲分区）。,4.2.2固定分区分配,.,20,图4.3固定分区分配举例,.,21,优点：能使多个作业共享内存、数据结构简单等。缺点：内存不能被充分利用；还存在内存空间足够但却不能装入作业的情况。“内零头”或称为“内部碎片”。,固定分区的特点,.,22,动态分区是指内存分区的情况不固定，系统根据进程的需要动态地分配内存空间。动态分区又称为可变分区。1.动态分区管理原理(1)分区建立时刻。动态分区管理中的内存分区不是在系统初启时建立的，而是在系统运行过程中，即在作业装入时动态建立。(2)分区大小。分区大小不是事先设定的，而是根据作业对内存的需求量来确定。(3)分区个数。分区个数是变化不定的。,4.2.3动态分区分配,.,23,当系统初启时，用户区是一个完整的空闲区。当有作业申请内存时，则从空闲区中划出一块与作业的内存需求量相等的分区分配给他。在作业运行结束时，系统回收作业释放的分区。若与回收的分区邻接的是空闲区，则将它们合并为一个大的空闲区。当系统运行一段时间后，随着一系列的内存分配与回收，原来的一个完整空闲区便形成了若干个占用区和空闲区交错的布局。,.,24,图4.4动态分区分配举例,.,25,在动态分区中，一般使用分区链来管理内存，即利用指针将内存中所有分区连成一条存储区链。其实现方法是：在每个分区的起始部分，设置一个指向前一个分区的指针。在每个分区的尾部，则设置一个指向后一个分区的指针，并设置状态位(用以区分分区是否空闲，当分区被分配出去以后，把状态位由“0”改为“1”)和分区大小表目。,2.动态分区管理中的数据结构,.,26,(1)最佳适应算法(best-fit)：找到其大小与要求相差最小的空闲分区从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。为了加快查找速度，应将分区按其大小递增的顺序排列。,3.分区分配算法,.,27,找到最大的空闲分区基本不留下小空闲分区，但较大的空闲分区不被保留。优点：总是选择最大的空闲区，划分后剩下的空闲区也是最大的，这样的分区很可能仍然是有用的。缺点：由于最大的空闲区总是首先被分配而进行划分，当有大的作业到来时，其存储空间的申请往往不容易得到满足。在实现最坏适应算法时，应将分区按其大小递减的顺序排列。,(2)最坏适应算法(worst-fit),.,28,按分区的先后次序，从头查找，找到符合要求的第一个分区。优点：由于留在高地址部分的大的空闲区被划分的机会少，因而在大作业到来时就比较容易得到满足。缺点：由于低地址部分不断地被划分而形成许多难以利用的、很小的空闲分区，也会使查找可用空闲分区时的开销增加。,(3)首次适应算法(first-fit),.,29,WorstFit,22,.,30,(1)内存的分配系统利用某种分区分配算法，从分区链中找到所需的空闲分区。若这个空闲分区比所要求的大，则将它分成两部分：一部分成为已分配的分区，剩下部分仍为空闲区。修改两个分区的有关信息，并回送一个所分配分区的序号或该区的首地址。,4.分区分配操作,.,31,若回收分区不与其他空闲区邻接，则修改该回收分区的有关信息。若回收分区与其他空闲区邻接，则把相关分区合并，使之成为一个连续的大空闲区，并修改分区链和相关分区的信息。,(2)内存的回收,.,32,图4.5回收区与空闲区邻接的情况,.,33,4.1存储管理的概念4.2连续分配方式4.3离散分配方式4.4虚拟存储器4.5Linux中的存储管理,.,34,1.页式存储管理基本原理(1)等分内存把内存的存储空间划分成大小相等的若干隔存储块，称为块或页框，并为各块从“0”开始依次编以连续的块号，如0块、1块等。(2)逻辑地址空间分页把逻辑地址空间划分成若干个与块大小相等的片，称之为页或页面，并为各页从“0”开始依次编以连续的页号，如0页、1页等。,4.3.1页式存储管理,.,35,(3)地址结构在分页系统中，每个逻辑地址用一个数对(P，d)来表示。其中，P是页号，d是页内地址或称位移量。,31,12,11,0,图4.6分页系统中的地址结构,.,36,若给定一个逻辑地址A，页面大小为L，则：页号PINT(A/L)页内地址dAMODL其中，INT是整除函数，MOD是取余函数。例如，设A=2170B，L1KB，则可求得P2，d=122。,.,37,(4)内存分配原则系统以块为单位把内存分配给作业或进程，分给一个作业的各存储块，不一定是相邻和连续的。页与块对应。一个作业的连续几个页面，可能被装入内存中不相邻的存储块中。(5)页表和页表地址寄存器系统能在内存中找到每个页面所对应的物理块。系统又为每个进程建立了一张页面映射表，简称页表。页表的作用：实现从页号到物理块号的映射。,.,38,图4.7页表的作用,.,39,地址变换机构的任务：将逻辑地址中的页号转换为内存中的物理块号。页表的作用就是用于实现从页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的。,2.分页系统中的地址变换,.,40,地址变换过程：指令所给出地址分为两部分：逻辑页号，页内偏移地址查进程页表，得物理页号物理地址物理地址块号块的长度页内地址地址越界中断：页号大于页表长度，即访问地址超越进程的地址空间。,.,41,图4.8分页系统的地址变换机构,.,42,图4.8中说明的地址变换过程如下：(1)系统从作业申请表中取出页表始址1000和申请页面数4放入页表寄存器(PTR)。(2)由PTR得到作业J的页表所在位置。并由逻辑地址100可知，指令LOAD1,2500在第0页的第100单元之中。由于第2页与第8个页面对应，因此，该指令在内存中的地址为210241002148。(3)当CPU执行到2148单元的指令时，将指令中的逻辑地址2500转换成页号和页内地址，有P2，d452。,地址变换过程：,.,43,(4)将页号与PTR中页表长度相比较，进行地址越界检查；检查结果为有效地址，则依次检索页表中的页号，可知页号2对应的块号为8。(5)由：物理地址块号块的长度页内地址，即810244528644，得到待访问的逻辑地址2500的物理地址为8644。(6)从内存中地址为8644的单元中取数后放入寄存器1中，即完成此指令的执行。,.,44,注意：分页存储管理中每存取一个数据时，都要两次访问内存：第一次是通过访问内存中的页表，得到待存取数据的物理地址；第二次是根据得到的物理地址向该地址中写入数据(或从该地址中取所需数据)。为了提高地址变换速度，可在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“快表”，用以存放当前访问的那些页表项。,.,45,图4.9具有快表的地址变换机构,.,46,页的大小通常是：几KB到几十KB。小-内碎片小；大-页表短，管理开销小，交换时对外存I/O效率高。和目前计算机的物理内存大小有关。,.,47,1.分段存储管理方式的引入(1)方便编程(2)信息共享(3)信息保护(4)动态增长(5)动态链接,4.3.2段式存储管理,.,48,页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。分段存储管理以段为单位进行内存分配，并通过分段地址映射机构把段式地址转换成实际内存的物理地址。(1)分段在分段存储管理方式中，作业地址空间被划分成若干个段，每个段定义了一组逻辑信息。例如，有主程序段、子程序段、数据段及栈段等，如图4.10所示。,2.分段存储管理的基本原理,.,49,图4.10利用段表实现地址映射,.,50,每个段有自己的段名，通常用段号来代替段名。每个段从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息单位的长度决定，各段的长度是不相等的。由于每个作业地址空间被分成多个段，因而作业的地址空间是二维的，逻辑地址由段号和段内地址组成，逻辑地址表示成有序偶(S，d)。其中，S是段号，d是段内地址。,31,16,15,0,图4.11分段存储管理的地址结构,.,51,(2)段表段表实现了从逻辑段到物理内存区的映射。(3)地址变换结构分段系统中设置了段表寄存器，用于存放段表起始地址和段表长度。系统将逻辑地址中的段号与段表长度进行比较，若未越界，则根据段表起始地址和段号计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址是否超过该段的段长，若未越界，则将该段的起始地址与段内位移相加，从而得到要访问的物理地址。,.,52,图4.12分段系统的地址变换过程,.,53,当作业需要某共享段时，系统首先按段名查找共享段信息表，若该段已装入内存，则将该段的内存始址填入该作业的段表中，以实现段的共享。段的保护是为了实现段的共享和保证作业正常运行的一系列措施。一种是存取控制权保护措施，即在段表中增设“存取方式”一栏，例如，R表示可读，W表示可写，E表示可执行等。一种是地址变换过程中的地址越界保护措施。,(4)段的共享与保护,.,54,(5)分页和分段的主要区别,.,55,分段式存储管理着眼于方便用户，为用户提供了二维的地址空间，反映了程序的逻辑结构，并且有利于段的共享和保护、段的动态增长和动态链接的实现。分页式存储管理则是为了提高内存利用率，有效地克服内存碎片。将分段和分页两种存储管理方式结合起来，既方便用户又提高内存利用率，由此形成了段页式存储管理。,4.3.3段页式存储管理,.,56,(1)用分段方法来管理地址空间即按程序的自然逻辑关系把作业的地址空间分成若干段，每一段有自己的段号。这是段页式存储管理的段式特征。(2)用分页方法来分配和管理物理内存。即把整个内存分成大小相等的存储块。这是段页式存储管理的页式特征。(3)作业的每一段又采用分页方法。按照内存块的大小把每一段分成若干页。每一段都从0开始为本段的各页依次编以连续的页号。,1.段页式存储管理的基本原理,.,57,图4.13段页式系统中的地址空间,.,58,(4)逻辑地址结构,23,1716,1312,0,图4.14段页式存储管理中的逻辑地址结构,.,59,(5)内存分配内存以块为单位分配给作业的一页。(6)段表、页表和段表地址寄存器为了实现地址变换，系统为每个作业建立了一个段表，并为该作业段表中的每一个段分别建立一个页表，系统中还有一个段表地址寄存器，用于指出作业的段表起始地址和段表长度，如图4.15所示。,.,60,图4.15利用段表和页表实现地址映射,.,61,在段页式系统中，为实现地址变换，须配置段表寄存器，在其中存放段表起始地址TA和段长TL。当进行地址变换时，首先用逻辑地址的段号S与段长TL比较，若STL，则利用段表起始地址和段号求得该段号所对应的段表项段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，最后再用物理块号b和页内地址d构成一维的物理地址。,2.段页式存储管理的地址变换过程,.,62,图4.16段页式存储管理中的地址变换机构,.,63,各种存储方法比较,.,64,4.1存储管理的概念4.2连续分配方式4.3离散分配方式4.4虚拟存储器4.5Linux中的存储管理,.,65,1.虚拟存储器的引入一次性：指要求将作业全部装入内存后方能运行；驻留性：是指作业装入内存后，便一直驻留在内存中，直至作业运行结束。一次性和驻留性使内存中许多暂时不用甚至已经不再需要的信息占据大量的内存空间，而其他需要运行的作业却无法装入内存，这将严重影响内存利用率，从而也减少了系统吞吐量。,4.4.1虚拟存储的概念,.,66,时间局部性。如果程序中的某条指令一旦执行，则不久后该指令可能再次执行；如果某个数据结构被访问，则不久后该数据结构可能再次访问。程序中使用的循环、子程序、堆栈等都反映了这个特性。空间局部性。一旦程序访问了某个存储单元，则不久后，其附近的存储单元也将被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围之内。程序代码的顺序执行、对线性数据结构的访问等都反映了这一特性。,(1)局部性原理,.,67,虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。虚拟存储器的最大容量取决于机器的CPU地址结构。虚拟存储器的逻辑容量由内存容量和外存容量之和决定。,(2)虚拟存储器的相关定义,.,68,(1)离散性离散性是指虚拟存储器在内存分配时采用离散分配方式，这是其最基础的特征。(2)多次性多次性是指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存即可。以后每当运行到尚未调入的那部分程序时，再将其调入。,2.虚拟存储器的特征,.,69,(3)对换性指允许在作业的运行过程中进行换入、换出，即进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区(换出)，待以后需要时再将它们从外存调至内存(换入)。甚至还允许将暂时不运行的进程调至外存，待它们重又具备运行条件时再将进程调入内存。(4)虚拟性虚拟性是指能从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。,.,70,(1)请求分页系统这是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许装入部分页面的程序(及数据)，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。置换时以页面为单位。(2)请求分段系统这是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。置换是以段为单位进行的。,3.虚拟存储器的实现方式,.,71,1.请求分页存储管理的基本原理(1)页表的结构在分页存储管理中的页表项中只包含页号、块号，仅有这些信息对请求分页管理是不够的。例如，怎样知道某页是否在内存、又怎样表示一个页面中所包含的信息是否被修改过等。为此，必须通过扩充页表的表目来解决这些问题。通常在请求分页存储器管理中的页表的表目中应增加如下信息。,4.4.2请求分页存储管理方式,.,72,(1)页表的结构,.,73,图4.17请求分页中的页表结构,表示该页调入内存后是否被修改过,用于指示该页是否已调入内存,用于记录该页在一段时间内被访问的次数，或者最近已有多长时间未被访问,用于指出该页在外存上的地址，通常是物理块号,.,74,请求分页中地址变换的全部工作，包括存储空间的分配、页面的置换等都是在指令执行过程中完成的，更准确地说，是在CPU访问内存的过程中完成的。当处理机要执行一条指令时，首先形成操作数的地址，然后由地址变换机构自动地把其分成页号和页内地址。若访问的页已在内存中(状态位=0)，则遵循简单分页系统的地址变换过程；若发现该页不在内存中(状态位=1)，则产生缺页中断，利用中断处理程序完成该页的装入。,(2)地址变换机构,.,75,图4.18请求分页系统中的地址变换过程,.,76,缺页中断处理的过程如下：若内存中有空闲块，则根据该页在外存的地址，调入所需页面；若内存中没有空闲块，首先按照某种页面置换算法选择某页进行淘汰，以腾出空闲块供本次调入的页使用；若被选中淘汰的页面中的信息被修改过(修改位=1)，则还必须将被选中淘汰的页面写入外存；当所需页面调入内存后，需更新该页的页表项，最后即可恢复被中断指令的执行。,(3)缺页中断处理,.,77,图4.19缺页中断处理过程,.,78,预调页策略这是一种以预测为基础的调页策略，试图将那些预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存。请求调页策略请求调页策略是指当作业在运行中所需的页面不在内存时，则把所缺页面调入内存。由请求调页策略所确定调入的页，是一定会被访问的页。加之请求调页策略较易实现，故目前的虚拟存储器系统大多采用此策略。但这种策略在调页时需花费较大的系统开销，增加了磁盘的I/O启动频率。,(4)页面调入策略,.,79,与基本分页一样，有效地解决了内存碎片问题。作业地址空间不受内存容量的限制。增加了系统时间和空间的开销。可能引起抖动。如果刚被换出的页面很快有被访问，需要新调入，调入内存后不久该页面又被调出，如此反复、频繁调进调出更换页面，以致一个进程在运行中，将大部分时间花在完成页面置换工作上，则称该进程发生了抖动。,(5)请求分页管理的优缺点,.,80,在进程运行过程中，若所要访问的页面不在内存，则需将该页面从外存调入内存。如果此时内存已无空闲物理块时，为保证该进程能正常运行，系统必须从内存调出一页程序或数据送入磁盘的对换区中。但应将哪个页面调出，则需根据一定的算法来确定。通常，把选择调出页面的算法称为页面置换算法。页面置换算法的优劣将直接影响系统性能，不适当的页面置换算法可能导致进程发生抖动。一个好的页面置换算法，应具有较低的页面更换频率，避免系统发生抖动现象。,2.页面置换算法,.,81,(1)最佳页面置换算法最佳页面置换算法的基本思想是：从内存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。(2)先进先出页面置换算法先进先出(FIFO)页面置换算法的基本思想是：当需要淘汰一个页面时，总是选择驻留内存时间最长的页面进行淘汰，即先进入内存的页面先淘汰。其理由是：最早调入内存的页面，其不再被使用的可能性较大。,.,82,(3)最近最久未用页面置换算法最近最久未用(LRU)页面置换算法的基本思想是：根据一个作业在执行过程中过去的页面访问踪迹来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会在被访问。所以这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。这种算法因为要对页面先前的访问历史加以记录和更新，实现起来比较困难。在实际应用中得到推广的是一种简单而又有效的LRU近似算法,“最近不用”的算法。,.,83,4.1存储管理的概念4.2连续分配方式4.3离散分配方式4.4虚拟存储器4.5Linux中的存储管理,.,84,1.“按需分页”的段页式虚拟存储管理技术Linux是一个多任务操作系统。为了节省内存空间，也采用了虚拟存储技术，使得系统能够同时运行的进程比实际内存能容纳更多。Linux的内存管理采用“按需分页”技术实现段式存储管理。系统运行时，需要的内容以页面为单位调入内存，暂不执行的仍留于外存交换区，因而，涉及页面的管理及页面的换入换出操作。,4.5.1Linux存储管理概述,.,85,缓冲区高速缓存(BufferCache)。缓冲区高速缓存中包含了由块设备使用的数据缓冲区。页缓存(PageCache)。页高速缓存的作用是加速对磁盘上的内存映像文件或数据的访问速度。交换缓存(SwapCache)。交换文件中只保存被修改过的页面。硬件缓存(HardwareCache)。CPU中有一个常用的硬件高速缓存，以保存页表的内容，使CPU可直接得到页表内容，进行地址交换，不必经常读取内存中的页表。,2.高速缓冲,.,86,1.Linux中的页表为避