《【教学课件】第四章存储管理(上).ppt》由会员分享，可在线阅读，更多相关《【教学课件】第四章存储管理(上).ppt（58页珍藏版）》请在三一办公上搜索。
1、1,第四章 存储管理(上),存储管理概述()内存管理的基本原理()Windows 的内存管理外存管理的基本原理Windows 的外存管理高速缓存管理的基本原理Windows 的高速缓存管理,2,存储体系存储管理的功能逻辑地址和物理地址重定位技术,存储管理概述,3,存储体系,高速缓存：Data CacheTLB(Translation Lookaside Buffer)内存：DRAM,SDRAM等；外存：软盘、硬盘、光盘、磁带等；,4,存储管理的功能,存储分配和回收：分配和回收算法及相应的数据结构。地址变换：可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技
2、术和机构存储共享和保护：代码和数据共享地址空间访问权限（读、写、执行）存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）,5,逻辑地址和物理地址,逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。当程序装入内存时,操作系统要为该程序分
3、配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,6,地址映射,BA=1000,3456,。,。,。,1200,物理地址空间,mov ax,data1,data1 3456,源程序,mov ax,200,3456,0,100,200,编译连接,逻辑地址空间,逻辑地址和物理地址,mov ax,1200,1000,1100,7,重定位技术,重定位：在可执行文件装入时需要解决可执行文件中地址（指令和数据）和内存地址的对应。由操作系统中的装入程序来完成。重定位方法：绝对装入可重定位装入动态装入,8,绝对装入(absolut
4、e loading),优点：装入过程简单。缺点：过于依赖于硬件结构，不适于多道程序系统。,在可执行文件中记录内存地址，装入时直接定位在上述(即文件中记录的地址)内存地址。,9,可重定位装入(relocatable loading),优点：不需硬件支持，可以装入有限多道程序缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。,在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。即：装入时根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。,10,动态装
5、入(dynamic run-time loading),优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。缺点：需要硬件支持（通常是CPU），OS实现较复杂。它是虚拟存储的基础。,在可执行文件中记录虚拟内存地址，装入和执行时通过硬件地址变换机构，完成虚拟地址到实际内存地址的变换。,11,单一连续区存储管理分区存储管理页式和段式存储管理虚拟存储器,内存管理的基本原理,12,单一连续区存储管理,内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用
6、于单用户、单任务的OS。优点：易于管理。缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。,用户程序,操作系统,0,xFFF,F,0 x0000,13,把内存分为一些大小相等或不等的分区(partition)，每个进程占用一个或几个分区。操作系统占用其中一个分区。特点：适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享。问题：可能存在内碎片和外碎片。内碎片：占用分区之内未被利用的空间外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。,分区存储管理,14,固定分区(fixed partitioning),分区大小相等：只适合于多
7、个相同程序的并发执行（处理多个类型相同的对象）。分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,把内存划分为若干个固定大小的连续分区。,15,固定分区(大小相同),固定分区(多种大小),16,动态分区(dynamic partitioning),动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。优点：没有内碎片。缺点：有外碎片。,17,动态分区(dynamic partitioning),18,分区分配算法,寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分
8、区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。,19,最先匹配法(first-fit)：按分区的先后次序，从头查找，找到符合要求的第一个分区该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。下次匹配法(next-fit)：按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。最佳匹配法(best-fit)：找
9、到其大小与要求相差最小的空闲分区从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。最坏匹配法(worst-fit)：找到最大的空闲分区基本不留下小空闲分区，但较大的空闲分区不被保留。,分区分配算法,20,页式和段式存储管理,简单页式简单段式段页式,页式和段式存储管理是通过引入进程的逻辑地址，把进程地址空间与实际存储位置分离，从而增加存储管理的灵活性。,21,简单页式(simple paging),1.简单页式管理的基本原理,将程序的逻辑地址空间和物理内存划分为固定大小的页或页面(page or page frame)，程序加载时，分配其所需的所有页，这些页不必连
10、续。需要CPU的硬件支持。,22,23,优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。缺点：程序全部装入内存。,24,2.简单页式管理的数据结构,进程页表：每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；逻辑页号（本进程的地址空间）物理页面号（实际内存空间）；物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用状况。数据结构：位示图，空闲页面链表；请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里；,25,3.简
11、单页式管理的地址变换,指令所给出地址分为两部分：逻辑页号，页内偏移地址查进程页表，得物理页号物理地址为缩短查找时间，可以将页表从内存装入到快表(TLB,Translation Lookaside Buffer)，按内容查找(associative mapping)，即逻辑页号物理页号,逻辑地址,26,页式地址变换,27,简单段式(simple segmentation),1.简单段式管理的基本原理,将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。,28,程序通过分段(segmentation)划分为多个模
12、块，如代码段、数据段、共享段。可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括通过动态链接进行代码共享优点：没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。缺点：进程全部装入内存。,29,B,0,S,A,0,N,Y,0,L,X,0,P,M,0,K,逻辑段号,0,1,2,3,4,进程,的地址空间,1000,3200,5000,6000,8000,P,K,S,L,N,主存,K,3200,P 1500,L 6000,N 8000,S 5000,长度,段地址,0,1,2,3,4,操作系统,30,2.简单段式管理的数据结构,进程段表：描述组成进程地
13、址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(base address)和段长度系统段表：系统内所有占用段空闲段表：内存中所有空闲段，可以结合到系统段表中,31,3.简单段式管理的地址变换,32,页式管理和段式管理的比较,分页是出于系统管理的需要，分段是出于用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。页大小是系统固定的，而段大小则通常不固定。逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地址空间；分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。,3
14、3,虚拟存储器(VIRTUAL MEMORY),局部性原理虚拟存储器的原理虚拟存储技术的种类页面调度策略置换算法,34,局部性原理,局部性原理(principle of locality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。,35,虚拟存储器的原理,在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执
15、行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。,36,引入虚拟存储技术的好处,大程序：可在较小的可用内存中执行较大的用户程序；大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)并发：可在内存中容纳更多程序并发执行；,37,虚拟存储技术的种类,虚拟页式虚拟段式段页式,38,虚拟页式(virtual paging),需要在
16、进程页表中添加若干项标志位：存在位（present bit，内存页和外存页），修改位(modified bit)访问统计：在近期内被访问的次数，或最近一次访问到现在的时间间隔外存地址,在简单页式存储管理的基础上，增加请求调页和页面置换功能。,对进程页表的修改,39,虚拟页式的进程页表,40,虚拟段式(virtual segmentation),需要在进程段表中添加若干项：标志位：存在位(present bit)，修改位(modified bit/dirty bit)，增长位（该段是否增长过，在虚拟页式中没有该位）访问统计：如使用位(use bit)存取权限：如读R，写W，执行X外存地址地址变换
17、和缺段中断：指令和操作数必定不会跨越在段边界上,在简单段式存储管理的基础上，增加请求调段和段置换功能。,41,虚拟段式管理的段表,42,段页式(combined paging and segmentation),存储管理的分配单位是：段，页逻辑地址的组成：段号，页号，页内偏移地址。地址变换：先查段表，再查该段的页表。缺段中断和缺页中断。,是虚拟页式和虚拟段式存储管理的结合。,43,虚拟段页式管理中的段表和页表,44,段页式地址变换,45,页面调度,请求调页(demand paging)：只调入发生缺页时所需的页面。优点：容易实现。缺点：对外存I/O次数多，开销较大预调页(prepaging)：
18、在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。优点：提高调页的I/O效率。缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。,1.调入策略(fetch policy),调入策略确定在外存中的页面调入时机。在虚拟页式管理中有两种常用策略。,46,2.分配策略(assignment policy),在虚拟段式管理中，如何对物理内存进行分配，可采用最佳适应、最先适应等。在虚拟页式和段页式管理中，地址变换最后通过页表进行，因此不必考虑分配策略。,47,3.清除策略(cleaning policy),请求清除(demand cleaning)：该页被置换时才调出，把
19、清除推迟到最后一刻。缺点：调入所缺页面之前还要调出已修改页面，缺页进程的等待时间较长，预清除(precleaning)：该页被置换之前就调出，因而可以成批调出多个页面。缺点：可能形成不必要的开销。已修改页面被调出之后仍停留在内存，如果这些页面被置换之前就被再次修改，则这些页面可以返还到进程的常驻集，而之前所做的调出操作就成为不必要的开销。这种策略发展成为页面缓冲算法(page buffering)。,在虚拟页式管理中，何时将已修改页面调出到外存上。有两种常用清除策略：,48,4.置换算法(replacement policy),需要调入页面时，选择内存中哪个物理页面被置换。目标：把未来不再使用
20、的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测；页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法为在页表中加上锁定标志位(lock bit)。,49,最佳算法(OPT,optimal)最近最久未使用算法(LRU,Least Recently Used)先进先出算法(FIFO)轮转算法(clock)最不常用算法(LFU,Least Frequently Used)页面缓冲算法(page buffering),置换算法,50,1.最佳算法(OPT,optimal),选择“
21、未来不再使用的”或“在离当前最远位置上出现的”页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。,51,2.最近最久未使用算法(LRU,Least Recently Used),一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。,选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：,52,3.先进先出算法(FIFO),选择建立最早的页面被置换
22、。可以通过链表来表示各页的建立时间先后。性能较差:较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出。并且可能出现Belady现象。,Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。,53,Belady现象,进程P有5页,程序访问页的顺序为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；,54,如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；,进程P有5页,程序访问页的顺序为：1,2,3,4,1,2,
23、5,1,2,3,4,5；,Belady现象,Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。,55,4.轮转算法(clock),每页有一个使用标志位(use bit)，若该页被访问则置user bit=1。置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找use bit=0的页面作为被置换页。指针经过的user bit=1的页都修改user bit=0，最后指针停留在被置换页的下一个页。,也称最近未使用算法(NRU,Not Recently Used)，它是LRU(最近最久未使用算法)和FIFO的折衷。,56,轮转
24、算法,57,5.最不常用算法(LFU,Least Frequently Used),选择到当前时间为止被访问次数最少的页面被置换；每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；,58,6.页面缓冲算法(page buffering),被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。如果页面未被修改，就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表。,它是对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；,空闲页面和已修改页面，仍停留在内存中，如果这些页面被再次访问，只需较小开销，就可以返还作为进程的内存页。,
