操作系统课件os04存储管理

操作系统OperatingSystems,笫四章存储器管理,笫四章存储器管理,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管方式4.8页面置换算法4.9请求分段存储管理方式,图4-1计算机系统存储层次示意,制造成本趋高,访问速度趋慢,4.1存储器的层次结构,物理地址空间,把内存分成若干个大小相等的存储单元存储单元占8位，称作字节（byte）每个单元给一个编号这个编号称为内存地址物理地址、绝对地址、实地址物理地址空间：物理地址的集合称为物理地址空间（主存地址空间）,1000,逻辑地址空间,逻辑地址空间生成的目标程序占据一定的地址空间，称为程序的逻辑地址空间（简称逻辑空间）。每个目标程序都是以0为基址顺序进行编址的，在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。,4.2程序的装入和链接,4.2.1程序的装入,4.2.1程序的装入,绝对装入方式可重定位装入方式动态运行时装入方式,1.绝对装入方式,程序中的逻辑地址与实际内存地址完全相同。只能将目标模块装入内存中事先指定的位置。绝对装入方式只适用于单道程序环境。,2.可重定位装入方式,根据内存的当前情况，将装入模块装入到内存的适当位置。,又称静态重定位：地址变换在装入时一次完成,变为：LOAD1,12500,可重定位装入方式特点,可用于多道程序环境；可将装入模块装入到内存中任何允许的位置不允许程序运行时在内存中移动位置。在运行过程中它在内存中的位置可能经常要改变此时就应采用动态运行时装入的方式,LoadA,365,10000,12500,物理地址空间,12500,20000,LoadA,22500365,22500,3.动态运行时装入方式,在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址把这种地址转换推迟到程序真正要执行时才进行。装入内存后的所有地址都仍是相对地址。地址变换发生在程序执行过程中！动态重定位,4.3连续分配方式,单一连续分配固定分区分配动态分区分配伙伴系统动态重定位分区分配,4.3.1单一连续分配,只能用于单用户、单任务的操作系统中。如：MS-DOS把内存分为系统区和用户区两部分系统区仅提供给OS使用通常是放在内存的低址部分用户区是指除系统区以外的全部内存空间，提供给用户使用。,4.3.2固定分区分配,多道程序的存储管理固定分区存储管理的基本思想：主存空间被划分成数目固定不变的分区，每个分区只装入一个作业，若多个分区中都装有作业，则它们可以并发执行。,1划分分区的方法,分区大小相等。缺点是缺乏灵活性。这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合。分区大小不等。把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。可根据程序的大小为之分配适当的分区。,2内存分配,通常将分区按大小进行排队，并为之建立一张分区使用表,图4-5固定分区使用表,20KB,4.3.3动态分区分配,动态分区分配是根据进程的实际需要，动态地为之分配内存空间。所用的数据结构分区分配算法分区的分配与回收操作。,1分区分配中的数据结构,空闲分区表。设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目：包括分区序号、分区始址及分区的大小等数据项。空闲分区链。,2分区分配算法,首次适应算法(FirstFit)循环首次适应算法(nextfit)最佳适应算法(bestfit)最坏适应算法(worstfit)快速适应算法(quickfit),首次适应算法(FF),要求空闲分区链以地址递增的次序链接。,首次适应算法(firstfit),该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。为以后到达的大作业分配大的内存空间创造了条件。缺点低址部分不断被划分，会留下许多难以利用的、很小的空闲分区每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。,循环首次适应算法(nextfit),该算法是由首次适应算法演变而成的。在分配内存空间时不再是每次都从链首开始查找，是从上次找到的空闲分区的下一个空闲分区开始查找直至找到一个能满足要求的空闲分区从中划出一块与请求大小相等的内存空间分配给作业应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式,循环首次适应算法(nextfit),使内存中的空闲分区分布得更均匀减少了查找空闲分区时的开销会缺乏大的空闲分区。,最佳适应算法(bestfit),为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。,最坏适应算法(worstfit),优点可使剩下的空闲区不至于太小，产生碎片的几率最小对中、小作业有利，查找效率很高。缺点：它会使存储器中缺乏大的空闲分区。,练习,在动态分区分配存储管理下，按地址排列的内存空闲区为：10K、4K、20K、18K、7K、9K、12K和15K。对于下列的连续存储区的请求：12K、10K、9K，试问：使用首次适应算法、最佳适应算法、最坏适应算法和循环首次适应算法，哪个空闲区被使用？,首次适应分配算法要求空闲区按首址递增的次序组织空闲区表（队列）。顺序查找未分配区表或链表，直到找第一能满足长度要求的空闲区为止，分割此分区。按地址排列的内存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB请求序列：12KB;10KB;9KB:,8KB,9KB,最佳适应分配算法要求按空闲区大小从小到大的次序组成空闲区表挑选一个能满足用户要求的最小分区。按地址排列的内存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB按空闲区大小:4KB7KB9KB10KB12KB15KB18KB20KB请求序列：12KB;10KB;9KB:,最坏适应分配算法要求空闲区按大小递减的顺序组织空闲区表扫描整个未分配区链表，挑选一个最大的空闲区分割按地址排列的内存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB按空闲区大小:20KB18KB15KB12KB10KB9KB7KB4KB请求序列：12KB;10KB;9KB:,8KB,8KB,6KB,循环首次适应算法要求空闲区按首址递增的次序组织空闲区表（队列）。从未分配区的上次扫描结束处顺序查找。按地址排列的内存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB请求序列：12KB;10KB;9KB:,8KB,8KB,3分区分配操作1)分配内存,2)回收内存,只需修改其前一分区F1的大小用回收区的首址作为新空闲区的首址，大小为两者之和(c)使用F1的表项和F1的首址，取消F2的表项(d)回收区既不与F1邻接，又不与F2邻接,动态分区回收算法,F1XF2,F1F2,F1XF,A,XF2,变为,变为,变为,变为,X,F1,F1,F1,F2,F2,F1,X终止前,X终止后,X,B,X,当作业撤离时，已分配区表中的相应状态置为“空”，而将收回的分区登记到未分配区表中。,4.3.6可重定位分区分配,1动态重定位的引入,2动态重定位的实现,硬件地址变换机构的支持地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。,3动态重定位分区分配算法,动态重定位分区分配算法与动态分区分配算法基本上相同差别仅在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。,4.3.7对换,1对换(Swapping)的引入通过选择一个进程，把其暂时移出到磁盘，腾出空间给其他进程使用，同时把磁盘中的某个进程再换进主存，让其投入运行。选择哪个进程换出？把时间片耗尽或优先级较低的进程换出因为短时间内它们不会被投入运行；,“整体对换”或“部分对换”,“整体对换”或“进程对换”对换是以整个进程为单位的。被广泛地应用于分时系统中其目的是用来解决内存紧张问题，并可进一步提高内存的利用率。“部分对换”（“页面对换”或“分段对换”）对换是以“页”或“段”为单位进行的。是请求分页和请求分段式存储管理的基础其目的是为了支持虚拟存储系统。,三大功能,对换空间的管理进程的换出进程的换入,2对换空间的管理,外存分为文件区和对换区文件区通常的文件都是较长久地驻留在外存上对文件区采取离散分配方式主要目标:提高文件存储空间的利用率。对换区进程在对换区中驻留的时间短暂的，对换操作又较频繁主要目标:是提高进程换入和换出的速度。采取的是连续分配方式，较少考虑外存中的碎片问题。,对换区中的空闲盘块管理,在系统中应配置相应的数据结构以记录外存的使用情况。与动态分区分配方式中所用数据结构相似空闲分区表空闲分区链。每个表目中应包含两项：对换区的首址及其大小分别用盘块号和盘块数表示,3进程的换出与换入,进程的换出换出进程选择选择处于阻塞状态且优先级最低的进程