内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式分页存储管理方式分段存储管理段页式存储管理存储器的层次结构存储器是计算机系统的重要组成部分容量、价格和速度之间的矛盾内存、外存；易失性和永久性内存，是稀缺资源在现代计算机系统中，存储通常采用层次结构来组织多级存储器结构主存与寄存器高速缓存和磁盘缓存多级存储器结构Storage systems in a computer system can be organized in a hierarchySpeed, access timeCost per bitVolatility主存 vs. 寄存器Same: Access directly for CPURegister nameMemory addressDifferent: access speedRegister, one cycle of the CPU clockMemory, Many cycles (2 or more)Disadvantage: CPU needs to stall frequently & this is intolerableRemedyCache高级缓冲技术cachingCachingCopying information into faster storage systemWhen accessing, first check in the cache, ifIn: use it directlyNot in: get from upper storage system, and leave a copy in the cacheUsing of cachingRegisters provide a high-speed cache for main memoryInstruction cache & data cacheMain memory can be viewed as a fast cache for secondary storageMagnetic disks 磁盘Transfer time 传输时间TT data size * Transfer rateTransfer rate (n M/s)-1 ( n Byte/us )-1 1/n us/BytePositioning time 定位时间Seek time 寻道TsRotational latency 旋转延迟TRTP Ts +TR m msTT VS. TPPlease Store data closely 内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式分页存储管理方式分段存储管理段页式存储管理程序执行的基础知识Von Neumann architecture 冯诺依曼体系结构Program must be brought into memoryMain memory is usually too smallProcessProgram must be placed within a process for it to be executed作业池User programsWhere to place the programseveral steps（图）地址的类型Absolute address 绝对地址Address seen by the memory unitPhysical address 物理地址Logical address 逻辑地址Generated by the CPUVirtual address 虚拟地址When can the absolute address can be decided?Address binding 地址的绑定Address binding 地址绑定地址绑定, the binding of instructions and data to memory, 可以在三种三种时刻进行Compile timeIf memory location known a priori, absolute code can be generated; must recompile code if starting location changes.Load timeMust generate relocatable code if memory location is not known at compile time.Execution timeBinding delayed until run time if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps (e.g., base and limit registers)Memory-Management Unit (MMU)Hardware device, 逻辑地址 物理地址Relocation register 重定位寄存器Added to every address generated by a user process at the time it is sent to memoryE.g. MS-DOS on 80x86User program deals with logical addresses, it NEVER sees the real physical addresses.是否需要将进程的所有代码和数据一次性装入？Shall we put the entire program & data of a process in physical memory before the process can be executed?For better memory space utilizationDynamic loadingDynamic linkingOverlaysSwapping程序的装入绝对装入方式可重定位装入方式动态运行时装入方式绝对装入方式编译时，产生absolute code，即使用绝对地址的代码装入时，必须装入到指定的地址无需对程序和数据的地址进行修改适用于单道系统可重定位装入方式大多数情况下，不能预知装入地址，只能在装入时确定编译时，产生可重定位代码，即使用相对地址的代码装入时，必须重定位通常把在装入时对目标程序中指令和数据的修改过程称为重定位。由于地址变换是在装入时一次性完成的，以后不再改变，故称为静态重定位可用于多道系统动态运行时重定位有时候，程序会在内存中移动位置例如对换需要能支持在运行过程中动态改变程序在内存中的位置方法：推迟重定位时机即从相对地址到绝对地址的转换推迟到程序真正执行时才进行因此，装入内存中的代码和数据的地址仍然是相对地址需要重定位寄存器的支持动态运行时装入方式根据程序运行的局部性，让程序及其数据在需要时才被装入Better memory-space utilization; unused routine is never loaded.Useful when large amounts of code are needed to handle infrequently occurring casesError routine No special support from OS is required implemented through program designDue to the users 程序的链接多个源程序编译多个目标模块；库。需要链接成可装入模块根据链接时间的不同静态链接方式：装入前很早就链接装入时动态链接：边装入，边链接运行时动态链接：运行时才链接静态链接方式静态链接方式：在程序运行之前，先将各目标模块以及它们所需要的库函数，链接成一个完整的装配模块，以后不再拆开。各目标模块内：相对地址存在目标模块之间的调用关系外部调用符号要解决的问题：修改相对地址：多个相对地址空间一个统一的相对地址空间变换外部调用符号装入时动态链接在装入时，根据外部模块调用事件，使用装入程序去寻找相应的外部目标模块，并装入，在装入时，修改相对地址优点：便于修改和更新便于实现对目标模块的共享运行时动态链接程序的每次运行，可能要执行的目标模块集是不同的全部装入？按需装入？运行时动态链接将对某些模块的链接推迟到程序执行时才进行需要操作系统配合优点：程序运行前的装入速度加快；省空间作业：从一个源程序到一个在内存中可执行的程序，一般需要哪几个步骤？有哪几种地址类型？有哪几种程序装入方式和链接方式？内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式分页存储管理方式分段存储管理段页式存储管理连续内存分配方式（contiguous memory allocation）连续分配存储管理方式单一连续固定分区动态分区对换内存通常被划分为两个分区（partitions）:系统区：常驻操作系统系统区：常驻操作系统，通常位于内存低端用户区：提供给用户（进程）使用，用户区：提供给用户（进程）使用，常位于内存高端连续内存分配是指：从用户区中为每个进程分配一个单独的、连续的内从用户区中为每个进程分配一个单独的、连续的内存空间存空间。主要有以下两种方式单一连续分配方式多分区式分配方式固定分区式动态分区式（可变分区式）单一连续分配方式最简单只能用于单用户、单任务系统存储保护机制存储管理单元，MMU或者不采用任何存储保护机制出于信任，或采用再启动方式，多分区式分配方式支持多道程序，用户区被进一步划分为若干个分区每一个分区装载一个进程多道程序度与分区的个数有关根据分区大小是固定的还是可变的固定分区方式大小固定；等大小 or 不等大小动态分区方式（可变分区方式）动态&可变：内存的划分是动态的，分区的大小随进程的大小确定，分区的数目随系统的运行而不断变化固定分区分配方式支持多道程序，用于60年代IBM360的MFT中分区的划分方法，两种等大小不等大小但分区的大小一旦确定就不再发生变化分配算法：按大小顺序建立分区使用表0分区号 大小（KB） 起始地址(K) 状态11530已分配23045已分配35075已分配4100125已分配操作系统作业A作业B作业C30K45K75K125K225K固定分区使用表固定分区使用表分配算法缺点内存利用率低定义：内部碎片和外部碎片内部碎片：已经分配出去但得不到利用的存储区域外部碎片：不能被利用的小分区解决方案：动态分区动态分区分配方式能根据进程实际需要的内存大小，动态分配能减少内部碎片关键数据结构：记录内存的使用情况，特别是空闲内存分配算法分配和回收操作数据结构空闲分区表空闲分区表，占用额外的空间空闲分区链空闲分区链，利用空闲分区序号 分区大小起始地址 状态前向指针N个字节可用后向指针N2N200分区分配算法在将一个新作业装入内存时，要从空闲分区表或空闲分区链中，选出一个分区分配给该作业，有三种常见的分配算法首次适应算法FF：First Fit循环首次适应算法最佳适应算法：Best Fit=smallest最差适应算法：Worst Fist largest思考在一个系统中内存有如下的空闲区，10KB，4KB，20KB，18KB，7KB，9KB，12KB，以及15KB。在分别使用首次适应，最佳适应，最差适应以及循环首次适应算法，对下列3个连续空间分配，得到的空闲分区分别是什么？12KB10KB9KB分区分配操作分配设请求的分区大小为u.size；利用某种分配算法，找到待分配的分区，大小为m.size根据上述分区分配算法，有m.sizeu.size判断m.size-u.size与min_size的大小min_size为事先约定的最小分区大小，分割，分割出来的分配出去，余下的加入空闲数据结构否则，直接分配将分配到的分区的首地址返回可以看出，动态分区分配方式中内部碎片最大不超过min_size回收，要考虑合并向前合并只需修改前一个空闲分区表项中的大小向后合并（图）只需修改后一个空闲分区表项中的起始地址和大小与前后同时合并修改前一个空闲分区表项中的大小，并取消后一个分区表项无相邻空闲分区，无需合并建立一个新的表项，填写相关信息，插入上述过程中，根据链表的维护规则，可能需要调整相应表项在空闲链表中的位置动态分区分配分析随着分配的进行，空闲分区可能分散在内存的各处尽管有回收，但内存仍然被划分的越来越碎，形成大量的外部碎片OSprocess 5process 8process 2OSprocess 5process 2OSprocess 5process 2OSprocess 5process 9process 2process 9process 10解决方案之一：紧凑Compaction针对外部碎片：采用紧凑的方法紧凑：通过移动进程在内存中的位置，把多个分散的小分区拼成大分区需要动态重定位技术支持动态重定位分区分配算法：引入紧凑和动态重定位技术的动态分区分配算法基本与动态分区分配算法相同思考紧凑的时间开销：若计算机读一个32位的时间是10ns，那么紧凑128MB的空间需要多长时间？Swapping 对换最早用于MIT的CTSS中单用户时间片对换对换是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存能提高内存利用率对换的单位：进程：整体对换；进程对换页、段：部分对换对换技术需要实现三个方面的功能对换空间的管理进程的换出进程的换入Backing store，对换空间Fast disk, large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images.为提高速度，考虑连续分配方式，忽略碎片问题需提供数据结构对空闲盘块进行管理方法类似动态分区分配方法进程的换出第一步：选择被换出的进程Some approachesRR scheduling: swapped out when a quantum expiresPriority-based scheduling: Roll out, roll inLower-priority process is swapped out so higher-priority process can be loaded and executed.第二步：换出确定要换出的内容非共享的程序和数据段的换出共享的程序和数据段的换出：计数器申请对换空间，换出，并修改相关数据结构进程的换入第一步：选择被换入的进程考虑“静止就绪状态”的进程其他原则第二部：申请内存并换入申请成功申请失败：利用对换技术腾出内存Schematic View of SwappingSwapping (cont.)Context switch Swapped in & out cost too muchAssume: process size 1MB, disk transfer rate 5MB/sec, average latency 8msTransfer time =1MB / (5MB/sec) = 1/5 sec = 200 msSwap time = 208 msSwap out & in = 416Major part of swap time is transfer time For RR scheduling, time quantum should 416msProblems exist for pending I/O processes swapping内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（离散分配方式（Discrete Memory Allocation）分页存储管理方式分页存储管理方式碎片碎片页页分段存储管理分段存储管理从逻辑上进行分段从逻辑上进行分段段页式存储管理段页式存储管理内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（离散分配方式（Discrete Memory Allocation）分页存储管理方式分页存储管理方式碎片碎片3bEffective memory-access time, time needed for every data/instruction access需要2次访存Access the page table & Access the data/instructionSolution:A special fast-lookup hardware cache called associative registers or translation look-aside buffers (TLBs)联想存储器，快表Associative registersEach register : a key & a value Parallel search (high speed)Expensive, typically 82048 entriesAddress translation (A, A)If A is in associative register, get frame # out. Otherwise get frame # from page table in memory联想存储器，快表TLB miss（TLB缺失）If the page number is not in the associative registersGet & storeHit ratio（命中率）The percentage of times that a page number is found in the associative registersContext switch TLB flushedTLB replacement algorithm具有块表的地址变换机构+Effective Access Time 有效存取时间设： Associative Lookup = time unit;memory cycle time = t time unit;Hit ratio = Effective Access Time (EAT)EAT = (t + ) + (2t + )(1 )= 2t + tIf (20 ns), t(100 ns), 1(80%), 2(98%):TLB hit: 20+100=120 nsTLB miss: 20+100+100=220 nsEAT1 = 120*0.8 + 220 * 0.2 = 140 nsEAT2 = 120*0.98 + 220 * 0.02 = 122 ns思考从页表中读取数据的时间开销是5ns，从块表中读取数据的开销则是1ns，为使平均开销降为1ns，则块表的命中率至少为多少？Memory Protection 内存保护If page size 2n, page & frame is aligned at 2n, so Memory protection implemented by associating protection bit with each frameProvide read only, read-write, execute-only protection orValid-invalid“valid”: the associated page is in the process logical address space, and is thus a legal page.“invalid”: the page is not in the process logical address space.Valid/invalid bit exampleAddress space 214Page size 2KBProcess size (010468) Page 5 has internal fragmentationPTLR=6Page 6 & 7 are invalid104861024012287两级和多级页表考虑：地址空间：32位；页大小4KB；有220即1M个页需要页表项：1M个假设，每个页表项使用32位表示，需要4MB的空间解决方案：进一步离散两级页表对页表分页，建立外层页表（页目录）则上述4MB的页表，进一步分为1K个页需要1K个页目录项假设每个页目录项使用32位表示，需要4KB因此，逻辑地址where p1 is an index into the outer page table, and p2 is the displacement within the page of the outer page table.page numberpage offsetp1p2d101012两级页表举例具有两级页表的地址变换机构+多级页表及其性能Level number = L, effect memory accesses time = (L+1)t考虑高速缓存技术：Cache hit rate of 98 percent yields:effective access time = 0.98 120 + 0.02 520= 128 nanoseconds.which is only a 28 percent slowdown in memory access time.内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（离散分配方式（Discrete Memory Allocation）分页存储管理方式分页存储管理方式碎片碎片页页分段存储管理分段存储管理从逻辑上进行分段从逻辑上进行分段段页式存储管理段页式存储管理分段存储管理方式引入分段的目的，是为了满足用户在编程和使用上的需求（逻辑上）在用户看来：A program is a collection of segments. A segment is a logical unit such as:main program,procedure, function,method,Objectlocal variables,global variables,common block,stack,symbol table逻辑地址空间A collection of segmentseach segment Two dimensional address spaceA logical addressCompiler automatically constructs segments reflecting the input program.Pascal compilerFORTRAN compilerC compiler, such as gcc, 段号段号段内地址段内地址3116 150Logical view of segmentation分段的硬件支持段表2-D logical address 1-D physical addresses; 每个段表项包括段在内存中的基地址段的长度Segment-table base register (STBR) Points to the segment tables location in memory.Segment-table length register (STLR)Indicates number of segments used by a program; Segment number s is legal if s STLR.段表举例分段的地址变换机构段表始址段表始址段表长度段表长度+段号段号S 位移量位移量W分页和分段的主要区别角度和目的不同分页：面向系统，物理上离散，减少外部和内部碎片，提高内存利用率页是信息的物理单位分段：面向用户，逻辑上离散，满足用户的需求段是信息的逻辑单位，意义相对完整大小不同分页：大小固定，由硬件决定分段：不固定，划分由程序决定，在编译时确定地址空间的维数不同分页：1维分段：2维，段名段内偏移分段举例 4300 + 53 = 4353 3200 + 852 = 4052How about ?分段的好处Relocation，可重定位，方便编程Dynamic, by segment table Sharingshared segmentssame segment number ProtectionUse segment table entryProtection bitRead-only, execute-only, read/writeValidation bit, 0illegal segmentProtection & sharing at segment level动态增长动态链接段的共享关于代码的重入可重入代码，又称为“纯代码”，是一种允许多个进程同时访问的代码。绝对不允许可重入代码在执行中有任何改变针对段的内存管理由于段长不固定，采用动态分区管理方式分配：首次适应、最佳适应等等由于大小不固定，存在外部碎片可能要考虑“紧凑”由于采用动态分区管理方式内部碎片很少内容提要存储器的层次结构程序执行的基础知识、程序的装入和链接连续分配存储管理方式离散分配方式（离散分配方式（Discrete Memory Allocation）分页存储管理方式分页存储管理方式碎片碎片页页分段存储管理分段存储管理从逻辑上进行分段从逻辑上进行分段段页式存储管理段页式存储管理段页式存储管理方式考虑在分段的基础上分页与单纯的分段相比在段表项中存放的不是段的起始地址，而是段所对应的页表的起始地址段页式举例：IA32体系结构中的段页机制IA32是基于分段的，分页可选常见的段寄存器如：CS, DS, ES, FS, GS, SSIA32使用全局描述符表GDT或者局部描述符表LDT每个描述符描述一个段，包括段大小、访问权限、基地址等使用段选择子索引一个段IA32的地址表示为，段：段内偏移Linear address = segment base + segment offset在不使用分页机制的情况下，线性地址就是物理地址否则，线性地址通过页表机制转换成物理地址IA32 address translation2-level page table作业什么是内部碎片；什么是外部碎片画出最基本的分页地址变换机构。分页和分段的主要区别是什么？