操作系统_内存管理

内容提要•存储器的层次结构•程序执行的基础知识、程序的装入和链接•连续分配存储管理方式•分页存储管理方式•分段存储管理•段页式存储管理存储器的层次结构•存储器是计算机系统的重要组成部分–容量、价格和速度之间的矛盾–内存、外存；易失性和永久性–内存，是稀缺资源•在现代计算机系统中，存储通常采用层次结构来组织–多级存储器结构–主存与寄存器–高速缓存和磁盘缓存多级存储器结构MagnetictapesOpticaldiskMagneticdiskElectronicdiskMainmemoryCacheregisters•Storagesystemsinacomputersystemcanbeorganizedinahierarchy–Speed,accesstime–Costperbit–Volatility主存vs.寄存器•Same:AccessdirectlyforCPU–Registername–Memoryaddress•Different:accessspeed–Register,onecycleoftheCPUclock–Memory,Manycycles(2ormore)•Disadvantage:–CPUneedstostallfrequently&thisisintolerable•Remedy–Cache高级缓冲技术caching•Caching–Copyinginformationintofasterstoragesystem–Whenaccessing,firstcheckinthecache,if•In:useitdirectly•Notin:getfromupperstoragesystem,andleaveacopyinthecache•Usingofcaching–Registersprovideahigh-speedcacheformainmemory–Instructioncache&datacache–Mainmemorycanbeviewedasafastcacheforsecondarystorage–……Magneticdisks磁盘•Transfertime传输时间–TT≈datasize*Transferrate–Transferrate≈(nM/s)-1≈(nByte/us)-1≈1/nus/Byte•Positioningtime定位时间–Seektime寻道•Ts–Rotationallatency旋转延迟•TR–TP≈Ts+TR≈mms•TTVS.TP–PleaseStoredataclosely内容提要•存储器的层次结构•程序执行的基础知识、程序的装入和链接•连续分配存储管理方式•分页存储管理方式•分段存储管理•段页式存储管理程序执行的基础知识•VonNeumannarchitecture冯·诺依曼体系结构–Programmustbebroughtintomemory–Mainmemoryisusuallytoosmall•Process–Programmustbeplacedwithinaprocessforittobeexecuted–作业池–Userprograms•Wheretoplacetheprogram•severalsteps（图）SourceprogramCompilerorassemblerObjectmoduleLinkageeditorLoadmoduleLoaderIn-memorybinarymemoryImageOtherobjectmodulesSystemlibraryDynamicallyloadedsystemlibraryCompiletimeLoadtimeExecutiontime(runtime)DynamiclinkingMultistepprocessingofauserprogram地址的类型•Absoluteaddress绝对地址–Addressseenbythememoryunit–Physicaladdress物理地址•Logicaladdress逻辑地址–GeneratedbytheCPU–Virtualaddress虚拟地址•Whencantheabsoluteaddresscanbedecided?Addressbinding地址的绑定Addressbinding地址绑定,thebindingofinstructionsanddatatomemory,可以在三种时刻进行•Compiletime–Ifmemorylocationknownapriori,absolutecodecanbegenerated;mustrecompilecodeifstartinglocationchanges.•Loadtime–Mustgeneraterelocatablecodeifmemorylocationisnotknownatcompiletime.•Executiontime–Bindingdelayeduntilruntimeiftheprocesscanbemovedduringitsexecutionfromonememorysegmenttoanother.Needhardwaresupportforaddressmaps(e.g.,baseandlimitregisters)Memory-ManagementUnit(MMU)•Hardwaredevice,逻辑地址物理地址•Relocationregister重定位寄存器–Addedtoeveryaddressgeneratedbyauserprocessatthetimeitissenttomemory–E.g.MS-DOSon80x86•Userprogramdealswithlogicaladdresses,itNEVERseestherealphysicaladdresses.LogicaladdressPhysicaladdress14346Relocationregister14000+MemoryCPUMMU346Dynamicrelocationusingarelocationregister是否需要将进程的所有代码和数据一次性装入？•Shallweputtheentireprogram&dataofaprocessinphysicalmemorybeforetheprocesscanbeexecuted?•Forbettermemoryspaceutilization–Dynamicloading–Dynamiclinking–Overlays–Swapping–…程序的装入•绝对装入方式•可重定位装入方式•动态运行时装入方式绝对装入方式•编译时，产生absolutecode，即使用绝对地址的代码•装入时，必须装入到指定的地址•无需对程序和数据的地址进行修改•适用于单道系统可重定位装入方式•大多数情况下，不能预知装入地址，只能在装入时确定•编译时，产生可重定位代码，即使用相对地址的代码•装入时，必须重定位–通常把在装入时对目标程序中指令和数据的修改过程称为重定位。•由于地址变换是在装入时一次性完成的，以后不再改变，故称为静态重定位•可用于多道系统动态运行时重定位•有时候，程序会在内存中移动位置–例如对换•需要能支持在运行过程中动态改变程序在内存中的位置•方法：推迟重定位时机即从相对地址到绝对地址的转换推迟到程序真正执行时才进行•因此，装入内存中的代码和数据的地址仍然是相对地址•需要重定位寄存器的支持动态运行时装入方式•根据程序运行的局部性，让程序及其数据在需要时才被装入•Bettermemory-spaceutilization;unusedroutineisneverloaded.•Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases–Errorroutine•NospecialsupportfromOSisrequiredimplementedthroughprogramdesign–Duetotheusers程序的链接•多个源程序编译多个目标模块；库。需要链接成可装入模块•根据链接时间的不同–静态链接方式：装入前很早就链接–装入时动态链接：边装入，边链接–运行时动态链接：运行时才链接静态链接方式•静态链接方式：在程序运行之前，先将各目标模块以及它们所需要的库函数，链接成一个完整的装配模块，以后不再拆开。–各目标模块内：相对地址–存在目标模块之间的调用关系–外部调用符号•要解决的问题：–修改相对地址：多个相对地址空间一个统一的相对地址空间–变换外部调用符号装入时动态链接•在装入时，根据外部模块调用事件，使用装入程序去寻找相应的外部目标模块，并装入，在装入时，修改相对地址•优点：–便于修改和更新–便于实现对目标模块的共享运行时动态链接•程序的每次运行，可能要执行的目标模块集是不同的•全部装入？按需装入？•运行时动态链接将对某些模块的链接推迟到程序执行时才进行•需要操作系统配合•优点：程序运行前的装入速度加快；省空间作业：•从一个源程序到一个在内存中可执行的程序，一般需要哪几个步骤？•有哪几种地址类型？•有哪几种程序装入方式和链接方式？内容提要•存储器的层次结构•程序执行的基础知识、程序的装入和链接•连续分配存储管理方式•分页存储管理方式•分段存储管理•段页式存储管理连续内存分配方式（contiguousmemoryallocation）•连续分配存储管理方式–单一连续–固定分区–动态分区•对换•内存通常被划分为两个分区（partitions）:–系统区：常驻操作系统，通常位于内存低端–用户区：提供给用户（进程）使用，常位于内存高端•连续内存分配是指：从用户区中为每个进程分配一个单独的、连续的内存空间。•主要有以下两种方式–单一连续分配方式–多分区式分配方式•固定分区式•动态分区式（可变分区式）单一连续分配方式•最简单•只能用于单用户、单任务系统•存储保护机制–存储管理单元，MMU–或者不采用任何存储保护机制•出于信任，或采用再启动方式，多分区式分配方式•支持多道程序，–用户区被进一步划分为若干个分区–每一个分区装载一个进程–多道程序度与分区的个数有关•根据分区大小是固定的还是可变的–固定分区方式•大小固定；等大小or不等大小–动态分区方式（可变分区方式）•动态&可变：内存的划分是动态的，分区的大小随进程的大小确定，分区的数目随系统的运行而不断变化固定分区分配方式•支持多道程序，用于60年代IBM－360的MFT中•分区的划分方法，两种–等大小–不等大小但分区的大小一旦确定就不再发生变化•分配算法：–按大小顺序建立分区使用表0分区号大小（KB）起始地址(K)状态11530已分配23045已分配35075已分配4100125已分配操作系统作业A作业B作业C30K45K75K125K225K固定分区使用表•分配算法•缺点–内存利用率低•定义：内部碎片和外部碎片–内部碎片：已经分配出去但得不到利用的存储区域–外部碎片：不能被利用的小分区•解决方案：动态分区动态分区分配方式•能根据进程实际需要的内存大小，动态分配–能减少内部碎片•关键–数据结构：记录内存的使用情况，特别是空闲内存–分配算法–分配和回收操作数据结构•空闲分区表，占用额外的空间•空闲分区链，利用空闲分区序号分区大小起始地址状态前向指针N个字节可用后向指针N＋2N＋200分区分配算法•在将一个新作业装入内存时，要从空闲分区表或空闲分区链中，选出一个分区分配给该作业，有三种常见的分配算法–首次适应算法FF：FirstFit–循环首次适应算法–最佳适应算法：BestFit=smallest–最差适应算法：WorstFist＝largest思考•在一个系统中内存有如下的空闲区，10KB，4KB，20KB，18KB，7KB，9KB，12KB，以及15KB。在分别使用首次适应，最佳适应