《中科大操作系统原理与实现课件8_memory1.pdf》由会员分享，可在线阅读，更多相关《中科大操作系统原理与实现课件8_memory1.pdf（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.操作系统原理与设计第8章 Main Memory1陈香兰中国科学技术大学计算机学院2009年11月.提纲backgroundStorage hierarchyMemory protectionProgram execution,loading&linkingContiguous Memory AllocationSwappingSwapping(对换).BackgroundIStorage hierarchyImemory protectionIProgram execution,loading&linking.OutlinebackgroundStorage hierarchyMemory
2、 protectionProgram execution,loading&linkingContiguous Memory AllocationSwappingSwapping(对换).Storage hierarchy II存储器是计算机系统的重要组成部分I容量、价格和速度之间的矛盾I内存、外存；易失性和永久性I内存，是稀缺资源I在现代计算机系统中，存储通常采用层次结构来组织Storage hierarchyIStorage systems in a computersystem can be organized in ahierarchyISpeed,access timeICost pe
3、r bitIVolatility.Memory VS.registerISame:Access directly for CPUIRegister nameIMemory addressIDifferent:access speedIRegister,one cycle of the CPU clockIMemory,Many cycles(2 or more)IDisadvantage:ICPU needs to stall frequently&this is intolerableIRemedyIcache.CachingICaching(高速缓存技术）ICopying informat
4、ion into faster storage systemIWhen accessing,first check in the cache,Iif In:use it directlyINot in:get from upper storage system,and leave a copy inthe cacheIUsing of cachingIRegisters provide a high-speed cache for main memoryIInstruction cache&data cacheIMain memory can be viewed as a fast cache
5、 for secondarystorageI.OutlinebackgroundStorage hierarchyMemory protectionProgram execution,loading&linkingContiguous Memory AllocationSwappingSwapping(对换).Memory protectionIBase register protection schemeIBase registerLimit registerIMemory outside is protectedIOS has unrestricted access to bothmoni
6、tor and users memoryILoad instructions for the base/limitregisters are privileged.OutlinebackgroundStorage hierarchyMemory protectionProgram execution,loading&linkingContiguous Memory AllocationSwappingSwapping(对换).Program execution,loading&linking IIVon Neumann architecture(冯诺依曼体系结构)IProgram must b
7、e brought into memoryIMain memory is usually too small.Program execution,loading&linking IIIProgram must be placed withina process for it to be executedIUser programs:Where toplace the program?Iseveral steps.Address TypesIAbsolute address 绝对地址IAddress seen by the memory unitIPhysical address 物理地址IRe
8、lative address 相对地址ILinear address 线性地址ILogical address 逻辑地址IGenerated by the CPUIVirtual address 虚拟地址IWhen can the absolute address can be decided?.Example.Address BindingIAddress binding of instructions and data to memoryaddresses can happen at three different stagesICompile time:If memory locatio
9、n known a priori,absolutecode can be generated;must recompile code if startinglocation changes;MS-DOS.COM-format programsILoad time:Must generate relocatable code if memorylocation is not known at compile timeIExecution time:Binding delayed until run time if the processcan be moved during its execut
10、ion from one memory segmentto another.Need hardware support for address maps(e.g.,base and limit registers).Logical vs.Physical Address SpaceIThe concept of a logical address space that is bound to aseparate physical address space is central to proper memorymanagementILogical address generated by th
11、e CPU;also referred to as virtual addressIPhysical address address seen by the memory unitIin compile-time and load-time address-binding schemesILogical addr=physical addrIin execution-time address-binding schemeILogical addr=physical addrIneed MMU.Memory-Management Unit(MMU)IHardware device that ma
12、ps virtual to physical addressIIn MMU scheme,the value in the relocation register is addedto every address generated by a user process at the time it issent to memoryIDynamic relocation using a relocation registerIThe user program deals with logical addresses;it never seesthe real physical addresses
13、.Program loading&linkingShall we put the entire program&data of a process in physicalmemory before the process can be executed?IFor better memory space utilizationIDynamic loadingIDynamic linkingIOverlaysISwappingI.Program loading II3 modesIAbsolute loading modeIrelocatable loading modeIdynamic run-
14、time loading1.Absolute loading mode(绝对装入方式)Icompiling absolute code with absolute addressesIloading 必须装入到指定的地址I无需对程序和数据的地址进行修改I适用于单道系统2.relocatable loading mode(可重定位装入方式)Imostly,the loading address can not be known at compile time,but only be decided at load time.Icompiling relocatable code with rel
15、ative addressesIloading must relocate.Program loading III通常把在装入时对目标程序中指令和数据的修改过程称为重定位(relocation)。I由于地址变换是在装入时一次性完成的，以后不再改变，故称为静态重定位(static relocation)I可用于多道系统dynamic run-time relocation(动态运行时重定位)I有时候，程序会在内存中移动位置I例如对换I需要能支持在运行过程中动态改变程序在内存中的位置I方法：推迟重定位时机即从相对地址到绝对地址的转换推迟到程序真正执行时才进行I因此，装入内存中的代码和数据的地址仍然
16、是相对地址I需要重定位寄存器的支持3.Dynamic Loading(动态运行时装入方式)I根据程序运行的局部性.Program loading IIIIRoutine is not loaded until it is calledIBetter memory-space utilization;unused routine is never loaded.IUseful when large amounts of code are needed to handleinfrequently occurring casesIError routineINo special support fr
17、om OS is required implemented throughprogram designIDue to the users.Overlays 覆盖技术IKeep in memory only those areneeded at any given time.INeeded when process is largerthan amount of memoryallocated to it.IImplemented by user,nospecial support needed from OS,programming design of overlaystructure is
18、complex.Program linking II多个源程序编译多个目标模块/库。需要链接成可装入模块Iaccording to the time of linkingIstatic linking(静态链接方式)Iload-time dynamic linking(装入时动态链接)Irun-time dynamic linking(运行时动态链接)Istatic linkingI在程序运行之前，先将各目标模块以及它们所需要的库函数，链接成一个完整的装配模块，以后不再拆开。I各目标模块内：相对地址I存在目标模块之间的调用关系I外部调用符号I要解决的问题：I修改相对地址：多个相对地址空间一个统
19、一的相对地址空间I变换外部调用符号.Program linking IIIload-time dynamic linkingI在装入时，根据外部模块调用事件，使用装入程序去寻找相应的外部目标模块，并装入，在装入时，修改相对地址I优点：I便于修改和更新I便于实现对目标模块的共享I运行时动态链接(Dynamic Linking)I程序的每次运行，可能要执行的目标模块集是不同的I全部装入？按需装入？ILinking postponed until execution timeISmall piece of code,stub,used to locate the appropriatememory-
20、resident library routineIStub replaces itself with the address of the routine,andexecutes the routineIOS needed to check if routine is in processes memory addressIDynamic linking is particularly useful for libraries sharedlibrariesI优点：程序运行前的装入速度加快；省空间.Contiguous Memory AllocationContiguous Memory Al
21、locationEach process is contained in a single contiguous section of memoryI单一连续IMultiple-partition allocationI固定分区I动态分区.单一连续分配Ithe most simple methodIat most one process at a timeIMain memory usually divided into twopartitions:IResident OS,usually held in lowmemory with interrupt vectorIUser process
22、es then held in highmemory.protection1.MMU2.Maybe not use any protection.Multiple-partition allocationImake several user porcesses reside in memory at the sametime.IUser partition is divided into n partitionsIEach partition may contain exactly one processIwhen a partition is free,a process in input
23、queue is selectedand loaded into the free partitionIwhen a process terminates,the partition becomes available foranother processIthe degree of multiprogramming is bound by the number ofpartions.Ifixed-partition VS.dynamic-partition.Fixed-sized-partition scheme(固定分区)IIThe simplest multi-partition met
24、hod:IBM OS/360(MFT)Ithe memory is divided into several fixed-sized partitionsIpartition size:equal VS.not equalIData Structure&allocation algorithm.Fixed-sized-partition scheme(固定分区)IIIdisadvantageIpoor memory utilityIInternal fragmentation&external fragmentationIExternal Fragmentation total memory
25、space exists tosatisfy a request,but it is not contiguousIInternal Fragmentation allocated memory may be slightlylarger than requested memory;this size difference is memoryinternal to a partition,but not being usedI?dynamic partition.dynamic partition（动态分区）IIHole block of available memoryIInitially,
26、all memory is considered one large hole;IWhen a process arrives,a hole large enough is searched.Iffound,the memory is allocated to the process as needed,therest memory of the partition is keep available to satisfy futurerequests.Iholes of various size are scattered throughout memoryIOS maintains inf
27、ormation about:Ia)allocated partitionsb)free partitions(hole).dynamic partition（动态分区）II.dynamic partition（动态分区）III.Dynamic Storage-Allocation ProblemIHow to satisfy a request of size n from a list of free holesIFirst-fit（首次适应）:Allocate the first hole that is bigenoughI循环首次适应IBest-fit（最佳适应）:Allocate
28、the smallest hole that is bigenough;must search entire list,unless ordered by sizeIProduces the smallest leftover holeIWorst-fit（最差适应）:Allocate the largest hole;must alsosearch entire listIProduces the largest leftover holeIFirst-fit and best-fit better than worst-fit in terms ofspeed and storage ut
29、ilization.分区分配操作I分配I设请求的分区大小为u.size；I利用某种分配算法，找到待分配的分区，大小为m.sizeI根据上述分区分配算法，有m.sizeu.sizeI判断m.size-u.size与min size的大小min size为事先约定的最小分区大小I，分割，分割出来的分配出去，余下的加入空闲数据结构I否则，直接分配I将分配到的分区的首地址返回I可以看出，动态分区分配方式中内部碎片最大不超过min size.分区回收操作 II回收，要考虑合并I向前合并I只需修改前一个空闲分区表项中的大小I向后合并（图）I只需修改后一个空闲分区表项中的起始地址和大小I与前后同时合并I修改
30、前一个空闲分区表项中的大小，并取消后一个分区表项I无相邻空闲分区，无需合并I建立一个新的表项，填写相关信息，插入I上述过程中，根据链表的维护规则，可能需要调整相应表项在空闲链表中的位置.分区回收操作 IIIdisadvantageI随着分配的进行，空闲分区可能分散在内存的各处I尽管有回收，但内存仍然被划分的越来越碎，形成大量的外部碎片IsolutionIcompaction(紧凑).compaction(紧凑).IReduce external fragmentation by compactionIShuffle memory contents to place all free memor
31、y together inone large blockICompaction is possible only if relocation is dynamic,and isdone at execution time(运行时的动态可重定位技术)II/O problemILatch job in memory while it is involved in I/OIDo I/O only into OS buffersI动态重定位分区分配算法：引入紧凑和动态重定位技术的动态分区分配算法.OutlinebackgroundStorage hierarchyMemory protectionPr
32、ogram execution,loading&linkingContiguous Memory AllocationSwappingSwapping(对换).Swapping(对换)II最早用于MIT的CTSS中I单用户时间片对换I对换是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存I能提高内存利用率I对换的单位：I进程：整体对换；进程对换I页、段：部分对换I对换技术需要实现三个方面的功能I对换空间的管理I进程的换出I进程的换入.Swapping(对换)IIIBacking storefas
33、t disk large enough to accommodate copies of all memoryimages for all users;must provide direct access to these memory imagesI为提高速度，考虑连续分配方式，忽略碎片问题I需提供数据结构对空闲盘块进行管理I方法类似动态分区分配方法I进程的换出I第一步：选择被换出的进程IRR scheduling:swapped out when a quantum expiresIPriority-based scheduling:Roll out,roll inLower-priori
34、ty process is swapped out so higher-priorityprocess can be loaded and executed.I第二步：换出.Swapping(对换)IIII确定要换出的内容非共享的程序和数据段的换出共享的程序和数据段的换出：计数器I申请对换空间，换出，并修改相关数据结构I进程的换入I第一步：选择被换入的进程I考虑“静止就绪状态”的进程其他原则I第二步：申请内存并换入I申请成功I申请失败：利用对换技术腾出内存IContext switchISwapped in&out cost too muchIMajor part of swap time i
35、s transfer time;total transfer time isdirectly proportional to the amount of memory swappedIAssume:process size 1MB,disk transfer rate 5MB/sec,average latency 8ms.Swapping(对换)IVITransfer time=1MB/(5MB/sec)=1/5 sec=200 msISwap time=208 msISwap out&in=416IFor RR scheduling,time quantum should 416msIProblems exist for pending I/O processes swappingIModified versions of swapping are found on many systems(i.e.,UNIX,Linux,and Windows)ISystem maintains a ready queue of ready-to-run processeswhich have memory images on disk.Schematic View of Swapping.谢谢！