ch4：存储器管理

nullnull第四章 存储器管理教学目的及 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 教学目的及要求掌握存储器管理的功能 掌握动态分区管理原理 掌握对换技术的概念 熟练掌握先进先出页面置换算法和最近最久未使用页面置换算法。 掌握请求页式管理、段式、段页式地址变换及其越界保护重点和难点 重点和难点 分页存储管理的基本方法、地址变换机构和页表机制； 分段存储管理的基本原理， 分页与分段的主要区别； 先进先出页面置换算法和最近最久未使用页面置换算法主要外语词汇主要外语词汇Virtual memory Logical Address Physical Address fixed partition variable partition (dynamic partition) Swapping FIFO Least recently used补充：存储体系补充：存储体系存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。 其依据是访问速度匹配关系、容量要求和价格。 寄存器-内存-外存 寄存器-缓存-内存-外存 微机中的存储层次组织： 访问速度越慢，容量越大，价格越便宜； 最佳状态应是各层次的存储器都处于均衡的繁忙状态 null存储层次结构快速缓存： Data Cache TLB(Translation Lookaside Buffer)转换后援缓冲器 内存：DRAM, SDRAM,DDR2,DDR3等； 外存：软盘、硬盘、光盘、磁带等；存储器容量计算方法存储器容量计算方法存储容量：是该存储设备上可以存储数据的最大数量，通常使用千字节（kb kilobyte）、兆字节（MB megabyte）、吉字节（GB, gigabyte）、太字节（TB ，terabyte）)等来衡量。下面括号中的数字为2的指数(即多少次方) 1KB=2(10)B=1024B； 1MB=2(20)B=1024KB； 1GB=2(30)B=1024MB。 1TB==2(40)B =1024GB 计算机数制计算机数制二进制（Binary system） 八进制（Octal system） 十进制（Decimal system） 十六进制（Hexadecimal system） 十六进制转二进制： (ACEF)H=1010 1100 1110 1111B补充：内存工作原理补充：内存工作原理 1、存储单元：若干个二进制位（4，8，16位等） 2、单元地址：所有的存储单元按顺序排列，每个单元都有一个编号。地址编号也用二进制数——绝对地址/物理地址 补充：内存工作原理 补充：内存工作原理3、寻址：通过地址编号寻找在存储器中的数据单元。存储器地址的范围多少决定了二进制数的位数. 例：如果存储器有1024个（1KB）单元，地址编码为0～1023，对应的二进制数是0000000000～1111111111，需要用10位二进制来表示，也就是需要10根地址线，或者说，10位地址码可寻址1KB的存储空间。 4、存储容量：存储器中所有存储单元的总和，存储容量的单位是KB、MB与GB。null0000H 0001H 0002H FFFFH存储单元 （字节）null例 CPU 从内存读取地址为44H中的数据54R44H54null例 CPU 将数据35放入内存地址为 48H中W48H35null第四章   存储器管理 4.1 存储器管理的功能4.2 连续分配方式4.3 基本分页存储管理方式4.5 虚拟存储器的基本概念4.4 基本分段存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式4.6 请求分页存储管理方式存储器管理的目的存储器管理的目的Program must be brought into memory and placed within a process for it to be run. 存储器管理实质：对内存空间的用户区进行管理。 内存分为系统区和用户区两部分：系统区仅提供给OS使用，通常位于内存的低址部分；用户区供用户使用。 存储器管理目的：尽可能地方便用户使用存储器和提高内存空间的利用率。存储器管理的功能存储器管理的功能地址转换 虚拟存储器（内存空间的扩充） 内外存数据传输的控制 内存的分配与回收 内存信息的共享与保护4.1 存储管理的功能4.1 存储管理的功能4.1.1 地址转换 4.1.2 虚拟存储器（内存空间的扩充） 4.1.3 内外存数据传输的控制 4.1.4 内存的分配与回收 4.1.5 内存信息的共享与保护 4.1.6 存储器管理方式4.1.1地址转换4.1.1地址转换Addresses may be represented in different ways during these steps. Addresses in the source program are generally symbolic (such as count). A compiler will typically bind these symbolic addresses to relocatable addresses (such as "14 bytes from the beginning of this module"). The linkage editor or loader will in turn bind these relocatable addresses to absolute addresses (such as 74014). Each binding is a mapping from one address space to another. Binding of Instructions and Data to MemoryBinding of Instructions and Data to Memory Address binding of instructions and data to memory addresses canhappen at three different stages. Compile time: If memory location known a priori, absolute code can be generated; must recompile code if starting location changes. Load time: Must generate relocatable code if memory location is not known at compile time. Execution time: Binding 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). Multistep Processing of a User Program Multistep Processing of a User Program <程序的链接和装入过程程序的链接和装入过程程序的链接和装入过程：将一个用户源程序转变为一个可在内存中执行的程序，需要经过： 编译:由编译程序将用户源代码编译成若干个目标模块。 链接:由链接程序将编译后形成的目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块。 装入:由装入程序将装入模块装入内存。用户程序的链接和装入过程用户程序的链接和装入过程地址转换（地址重定位或地址映射）地址转换（地址重定位或地址映射）内存空间是内存地址的集合，是一维线性空间。 地址转换：建立相对地址（逻辑地址）与内存绝对地址（物理地址）的关系。逻辑地址空间和物理地址空间 Logical vs. Physical Address Space逻辑地址空间和物理地址空间 Logical vs. Physical Address SpaceAn address generated by the CPU is commonly referred to as a logical address, whereas an address seen by the memory unit--that is, the one loaded into the memory-address register of the memory--is commonly referred to as a physical address. The compile-time and load-time address-binding methods generate identical logical and physical addresses. However, the execution-time address-binding scheme results in differing logical and physica1 addresses. In this case, we usually refer to the logical address as a virtual address. nullWe use logical address and virtual address interchangeably in this text. Logical-address space: The set of all logical addresses generated by a program; physical-address space: the set of all physical addresses corresponding to these logical addresses. Thus, in the execution-time address-binding scheme, the logical- and physical-address spaces differ. Logical vs. Physical Address SpacenullThe concept of a logical address space that is bound to a separate physical address space is central to proper memory management. Logical address – generated by the CPU; also referred to as virtual address. Physical address – address seen by the memory unit.Logical vs. Physical Address实现地址重定位或地址映射的方法实现地址重定位或地址映射的方法static linking：system language libraries are treated like any other object module and are combined by the loader into the binary program image. dynamic linking：Linking postponed until execution time. This feature is usually used with system libraries, such as language subroutine libraries. Without this facility all programs on a system need to have a copy of their language library (or at least the routines referenced by the program) included in the executable image. This requirement wastes both disk space and main memory. 实现地址重定位或地址映射的方法实现地址重定位或地址映射的方法静态地址重定位(可重定位装入方式）：由装入内存时一次完成地址变换，以后不再改变。 动态地址重定位(动态运行时装入方式)：程序执行过程中，在CPU访问内存之前，将要访问的程序或数据相对地址转换成内存绝对地址。需要硬件（重定位寄存器）支持。4.1.2 虚拟存储器4.1.2 虚拟存储器虚拟存储器: 把辅助存储器作为对主存储器的扩充, 向用户提供一个比实际主存大得多的地址空间。 虚拟存储的基本原理 程序装入时，只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。 内存中只存放经常被访问的程序和数据段，待到进程执行过程中需要放在辅助存储器中的信息时，再从外存中自动调入内存。 4.1.3 内外存数据传输的控制4.1.3 内外存数据传输的控制控制内存和外存之间的数据流动的方式： （1）户程序自己控制：用户程序自己控制内外存之间的数据对换的例子(覆盖) （2）操作系统控制： 对换(swapping):把在内存中处于等待状态的进程换出内存，而把等待事件已经发生、处于就绪态的进程换入内存。 请求调入(on demand)和预调入(on prefetch)： 请求调入方式是在程序执行时，如果所要访问的程序段或数据段不在内存中，则操作系统自动地从外存将有关的程序段和数据段调入内存。 预调入是由操作系统预测在不远的将来会访问到的那些程序段和数据段部分，并在它们被访问之前系统选择适当的时机将它们调入内存。SwappingSwappingA process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution. Backing store fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images. Roll out, roll in swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed. Modified versions of swapping are found on many systems, i.e., UNIX, Linux, and Windows.nullFigure Swapping of two processes using a disk as a backing store.4.1.4 内存的分配与回收4.1.4 内存的分配与回收 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 内存的分配和回收方法时须考虑的策略和数据结构： 分配结构：登记内存使用情况和供分配程序使用的表格与链表。 放置策略：确定调入内存的程序和数据在内存中的放置位置。是一种选择内存空闲区的策略。 对换策略：在需要将某个程序段和数据调入内存时，如果内存中没有足够的空闲区，对换策略被用来确定把内存中的哪些程序段和数据段调出内存，以便腾出足够的空间。 调入策略：外存中的程序段和数据段什么时间按什么样的控制方式进入内存。调入策略与内外存数据流动控制方式有关。 回收策略：包括回收的时机，以及对所回收的内存空闲区和已存在的内存空闲区的调整。4.1.5 内存信息的共享与保护4.1.5 内存信息的共享与保护内存信息共享：在多道程序设计环境下，内存中的许多用户或系统程序和数据段可供不同的用户进程共享。提高内存的利用率。 内存信息保护: 被允许共享的部分之外，各进程不能对别的进程的程序和数据段产生干扰和破坏。 常用的内存信息保护方法：越界检查、存取控制检查和环保护机构三种。4.1.6 存储器管理方式4.1.6 存储器管理方式 按照逻辑连续分得物理空间是否连续分为两类： 1 连续分配方式（逻辑空间连续分得的物理空间连续）： 固定分区 可变（动态）分区方式 2 离散分配方式（逻辑连续分得物理空间不连续）： 分页存储管理方式 分段存储管理方式 段页式存储管理方式4.2 连续分配方式4.2 连续分配方式 4.2.1 单一连续分配4.2.2 固定分区分配4.2.3 动态分区分配4.2.5 对换4.2.4 可重定位分区分配4.2.1 单一连续分配4.2.1 单一连续分配Main memory usually into two partitions: Resident operating system usually held in low memory with interrupt vector. User processes held in high memory 单一连续分配Single-partition allocation：只适用于单用户、单任务的操作系统。 内存用户区仅能存放一道作业。 优点：管理简单、开销小。 缺点：资源利用率低4.2.2 固定分区分配4.2.2 固定分区分配固定分区管理Multiple-partition allocation：Hole – block of available memory; holes of various size are scattered throughout memory. When a process arrives, it is allocated memory from a hole large enough to accommodate it. Operating system maintains information about: a) allocated partitions b) free partitions (hole) nullOSprocess 5process 8process 2OSprocess 5process 2OSprocess 5process 2OSprocess 5process 9process 2process 9process 10Multiple-partition allocationnull固定分区管理基本原理： 系统初启时，将内存用户空间划分为若干个固定大小的区域，分区大小在系统运行期间不再变化，每个分区只装入一个进程。 涉及到的问题： 划分分区的方法 内存分配 1.划分分区的方法1.划分分区的方法 划分分区的方法： 分区大小相等：所有的内存分区大小相等。 分区大小不等：可根据程序的大小为之分配适当的分区。 2.内存分配2.内存分配 分区说明表说明各分区号、分区大小、起始地址和分区状态。 固定分区分配的优缺点固定分区分配的优缺点优点：可使多道程序共存于内存。 缺点： 并发进程的数目受分区个数的限制。 存在内存碎片。 用户程序的大小受分区大小的严格限制。4.2.3 动态分区分配4.2.3 动态分区分配动态分区（Dynamic Storage-Allocation Problem）的基本思想：根据进程的实际需要，动态地为之分配内存空间，分区大小刚好满足进程的实际需要。 动态分区涉及到的问题： 1.数据结构 2.分区分配算法 3.分区的分配与回收操作 1.数据结构1.数据结构1）空闲分区表：用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。 2）空闲分区链：实现对空闲分区的分配和链接。空闲链结构空闲链结构2.动态分区时的分配方法2.动态分区时的分配方法First-fit Allocate the first hole that is big enough. Best-fit Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. Produces the smallest leftover hole. Worst-fit Allocate the largest hole; must also search entire list. Produces the largest leftover hole. First-fit and best-fit better than worst-fit in terms of speed and storage utilization. 2.动态分区时的分配方法2.动态分区时的分配方法动态分区时的分配方法从空闲分区表（链）中寻找空闲区的常用方法： 首次适应算法(first fit algorithm) 循环首次适应算法(next fit algorithm) 最佳适应算法(best fit algorithm) 最坏适应算法(worst fit algorithm) 快速适应算法(quick fit algorithm) （1）首次适应法(first fit algorithm)（1）首次适应法(first fit algorithm)空闲分区按起始地址递增的次序排列。 内存分配方法： 一旦找到大于或等于所要求内存长度的分区，则结束探索。 然后，从所找到的分区中划出所要求的内存长度分配给用户，把余下的部分留在空闲分区表中或链中。 缺点：内存的低端留下很多难以利用的小空闲分区，查找速度慢。（2）循环首次适应算法(next fit algorithm)（2）循环首次适应算法(next fit algorithm)由首次适应算法演变而成。 内存分配方法： 每次分配都从上次分配的位置之后开始查找，并将第一个能满足要求的空闲分区分割并分配出去。 优点：内存的空闲分区分布更为均匀，减少查找空闲分区的开销。 缺点：会使内存中缺乏大的空闲分区。（3）最佳适应算法(best fit algorithm)（3）最佳适应算法(best fit algorithm)将空闲区按大小递增的次序排列。 内存分配方法： 从空闲分区表（链）首开始顺序查找，并将第一个能满足要求的空闲分区分割并分配出去。 缺点：会在内存留下大量难以利用的小空闲分区。 动态分区算法演示动态分区算法演示运行动态分区算法演示程序3.动态分区时的分配与回收3.动态分区时的分配与回收动态分区时的分配与回收主要解决的问题： (1)利用某种分区算法，从空闲分区表（链）中找到所需大小的空闲区。 (2))进程运行完释放内存资源时，回收并合并相邻的空闲区，并将其插入空闲分区表（链）。动态分区时的拼接动态分区时的拼接 1)该空闲区的上相邻区是空闲区： 将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址。 2)该空闲区的下相邻区是空闲区： 将释放区与下空闲区合并 将释放区的起始地址作为合并区的起始地址。 3)该空闲区的上下两相邻分区都是空闲区： 将三个空闲区合并为一个空闲区。 新空闲区的起始地址为上空闲区的起始地址。 4)两相邻区都不是空闲区： 释放区作为一个新空闲区插入空闲分区表（链） 。动态分区分配的优缺点动态分区分配的优缺点优点：内存分区的个数和每个分区的大小都将随着系统中运行作业的情况而变化。 缺点：内存中会产生很多小的空闲分区。4.2.4 可重定位分区分配4.2.4 可重定位分区分配1. 可重定位（动态重定位）的引入 2.可重定位（动态重定位）的实现1. 可重定位（动态重定位）的引入1. 可重定位（动态重定位）的引入动态分配存在的问题：内存中有若干个小空闲分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。 “拼接”或“紧凑”技术 ：通过移动内存中作业的位置，把原来多个分散的小空闲分区拼接成一个大空闲分区。“拼接”或“紧凑”示意图“拼接”或“紧凑”示意图2.可重定位（动态重定位）的实现2.可重定位（动态重定位）的实现实现原理：在动态分区分配方式的基础上增加紧凑功能，即在找不到足够大的空闲分区、而空闲分区总和能满足用户需求时，对内存空间进行紧凑。 需要硬件地址变换机构的支持，即增设一个重定位寄存器，用于存放程序(数据)在内存中的起始地址。 程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。动态重定位示意图动态重定位示意图4.2.5 对换(swapping)4.2.5 对换(swapping)对换技术：把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。 对换技术可从逻辑上扩充内存空间。 可分为整体对换（进程对换）和部分对换（页面对换或分段对换） 对换实现三方面的功能对换实现三方面的功能对换空间的管理：对换空间设置在高速磁盘，采取简单的连续分配方式。 进程的换出：首先选择处于阻塞状态且优先级最低的进程换出。 进程的换入：把换出时间最久(换出到磁盘上)的已“就绪”状态进程作为换入进程。 对换技术的特点对换技术的特点 优点： 增加并发运行的程序数目； 编写程序时不影响程序结构。 缺点： 对换入和换出的控制增加处理机开销； 程序整个地址空间都进行传送。 4.3 基本分页存储管理方式4.3 基本分页存储管理方式为什么要引进分页技术? 分区管理方式存在严重的“碎片”问题，使内存的利用率不高。 分区管理方式要求进程连续存放，使进程的大小仍受分区大小或内存可用空间的限制。 分区管理方式不利于程序段和数据的共享碎片（Fragmentation）碎片（Fragmentation）外碎片External Fragmentation：– total memory space exists to satisfy a request, but it is not contiguous. 内碎片Internal Fragmentation：– allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used. Reduce external fragmentation by compaction Shuffle memory contents to place all free memory together in one large block. Compaction is possible only if relocation is dynamic, and is done at execution time.4.3 基本分页存储管理方式4.3 基本分页存储管理方式4.3.1 页面与页表 4.3.2 地址变换机构 4.3.3 两级和多级页表 4.3.4 内存块的分配与回收 4.3.1 页面与页表4.3.1 页面与页表1.页面或页 ：将一个进程的逻辑地址空间分成若干个大小相等的片。 2.物理块或页框：把内存空间分成与页面相同大小的若干个存储块。3.地址结构 3.地址结构 分页地址结构：页号和位移量（页内地址）。 逻辑地址=页号*页长+页内地址 内存地址=物理块号*页长+页内地址 页长为4KB，拥有1M页的地址结构: 地址转换方法及实例地址转换方法及实例若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：其中，INT是整除函数，MOD是取余函数。例：已知页面大小为1 KB，设逻辑地址A=2170B。则由上式可以求得页号P = 2，页内地址d = 122。分页式存储管理的地址变换分页式存储管理的地址变换地址结构与数对（页号，页内位移）的形成15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 3000IK256程序如何存储？程序如何存储？思考题 思考题 一个实行分页式存储管理的系统，内存块尺寸为2KB/块，现有一个用户，其相对地址空间为0-5129B，若将此作业装入内存，系统分配给他的存储容量为多少字节？4.页表4.页表页表：为每个进程建立一张页面映像表。程序如何运行？程序如何运行？4.3.2 地址变换机构4.3.2 地址变换机构 地址转换地址转换页表Page table is kept in main memory. Page-table base register (PTBR) 页表基址寄存器：points to the page table. Page-table length register (PTLR) 页表长度寄存器：indicates size of the page table.基本地址变换方式的缺点基本地址变换方式的缺点Every data/instruction access requires two memory accesses. 每次数据/指令访问需要两次内存访问 One for the page table one for the data/instruction. The two memory access problem can be solved by the use of a special fast-lookup hardware cachecalled associative memory or translation look-aside buffers (TLBs) 联想存储器或旁视转换缓冲区基本地址变换方式的缺点基本地址变换方式的缺点CPU在每存取一个数据时，都要两次访问内存：页表存放在内存中。 第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内位移拼接，形成物理地址。 第二次访问内存时，从第一次所得地址中获得所需数据(或向此地址中写入数据)。 改进方法：具有快表（相联寄存器）的地址变换机构具有快表的地址变换机构具有快表的地址变换机构特点特点减少访问内存时间 增加存储空间 命中率：通过快表实现内存访问的成功率示例示例假定CPU访问一次内存时间为200ns，访问一次快表时间为40ns，快表命中率为90%，试问现在进行一次内存存取的平均时间是多少？比只采用页表下降了多少？ 采用快表： （200＋40）×90%＋(200+200)×(1-90%)＝256ns 只采用页表： 两次访问主存的时间: 200ns×2＝400ns。 4.3.3 两级和多级页表4.3.3 两级和多级页表Most modern computer systems support a large logical-address space (232 to 264). In such an environment, the page table itself becomes excessively large.nullExample:logical-address space 32-bit; page size --- 4 KB (212); each entry--- 1 bytes;page table entries:? ---may consist of up to 1 million (232/212). physical-address space for the page table alone: --- may need up to 1 MB Logical address: Clearly, we would not want to allocate the page table contiguously in main memory. null● Two-Level Paging Algorithm 两级分页算法 ---the page table itself is also paged logical-address space 32-bit; page size --- 4 KB (212);page the page table an index into the outer page tablethe displacement within the page of the outer page tableTwo-Level Page-Table SchemeTwo-Level Page-Table SchemeAddress-Translation SchemeAddress-Translation SchemeAddress-translation scheme for a two-level 32-bit paging architecture Because address translation works from the outer page table inwards, this scheme is also known as a forward-mapped page table（向前映射页表）. The Pentium-II uses this architecture. null● Three-Level Paging Algorithm 三级分页算法 For a system with a 64 bit logical-address space, a two-level paging schemes no longer appropriate. Example: logical-address space 64-bit; page size --- 4 KB (212); The inner page table---1 page long---210 4 entries（采用两层分页）分页存储管理地址转换思考题分页存储管理地址转换思考题在一分页存储管理系统，页面大小为4KB。已知某进程的第0、1、2、3、4页依次存在内存中的6、8、10、14、16物理块号中，现有逻辑地址为12138B, 3A5CH ，分别求其所在的页号、页内相对地址、对应的物理块号以及相应的物理地址。 特点特点减少访问内存时间 增加存储空间 命中率：通过快表实现内存访问的成功率例例假定CPU访问一次内存时间为200ns，访问一次快表时间为40ns，快表命中率为90%，试问现在进行一次内存存取的平均时间是多少？比只采用页表下降了多少？ 采用快表： （200＋40）×90%＋(200+200)×(1-90%)＝256ns 只采用页表： 两次访问主存的时间: 200ns×2＝400ns。 4.3.4 内存块的分配与回收4.3.4 内存块的分配与回收1.存储分块表 2.位图 3.单链表1、存储分块表1、存储分块表1、存储分块表 操作系统设一张表格，记录内存中每一块的使用情况 null内存储器空闲块 链表起址块号状态2.位图2.位图用二进制位与内存块的使用状态建立起联系，0为空闲，1为已分配位号 0 1 2 3 4 5 6 7 字节号0 1块号=字节号*8+位号null3.单链表内存储器空闲块 链表起址分页存储管理特点分页存储管理特点1 内存被分成大小相等的块 2 用户作业相对地址空间被分成相同大小的页 3 不要求占用连续存储空间 4 有内部碎片：平均不超过半页 5 要求全部装入内存4.4 基本分段存储管理方式4.4 基本分段存储管理方式4.4.1 分段存储管理方式的引入 4.4.2 分段系统的基本原理 4.4.3 信息共享 4.4.4 段页式存储管理方式 4.4.1 分段存储管理方式的引入4.4.1 分段存储管理方式的引入 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接 4.4.2 分段系统的基本原理4.4.2 分段系统的基本原理作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息，有自己的段名和段长，并都采用首地址为0的一段连续地址空间。 内存空间的划分与动态分区相似，只不过将分配对象由整个程序变为段。 逻辑上连续的多个段在内存中可以不必连续存放。1.分段地址中的地址结构1.分段地址中的地址结构 在该地址结构中，允许一个作业最长有 64 K个段，每个段的最大长度为64 KB。 2．段表2．段表段表：在系统中为每个进程建立一张段映射表。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。利用段表实现地址映射利用段表实现地址映射3．地址变换机构3．地址变换机构4．分页和分段的主要区别4．分页和分段的主要区别页是信息的物理单位，段是信息的逻辑单位； 页的尺寸由系统确定，段的尺寸因段而异； 页式地址空间是一维的，段式地址空间是二维的。 分段地址转换示例分段地址转换示例在分段存储管理中，有某作业的段表如下： 已知该作业中的6个逻辑地址为： (1) [0,430]; (2) [3,400]; (3) [1,10]; (4) [2,2500]; (5) [4,42]； （6）[1,11]。试求其对应的物理地址。段号 段长 基址0 600 219 1 14 2300 2 100 90 3 580 1327 4 96 19544.4.3　信息共享4.4.3　信息共享4.4.4 段页式存储管理方式4.4.4 段页式存储管理方式段页式系统的基本原理： 分段和分页原理的结合 即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。作业地址空间和地址结构作业地址空间和地址结构利用段表和页表实现地址映射利用段表和页表实现地址映射段页式系统中的地址变换机构段页式系统中的地址变换机构4.5 虚拟存储器的基本概念4.5 虚拟存储器的基本概念Questions： 1、大进程能否运行在小的内存空间上？ 2、如何在有限的内存空间上运行更多的进程？ 4.5 虚拟存储器的基本概念4.5 虚拟存储器的基本概念基本存储器管理方式出现下面情况： (1) 有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行。 (2) 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。4.5 虚拟存储器的基本概念4.5 虚拟存储器的基本概念 4.6.1　虚拟存储器的引入 4.6.2　虚拟存储器的实现方法 4.6.3　虚拟存储器的特征 4.6.1　虚拟存储器的引入4.6.1　虚拟存储器的引入1．常规存储器管理方式的特征 一次性及驻留性：使许多在程序运行中不用或暂不用的程序(数据)占据了大量的内存空间，使得一些需要运行的作业无法装入运行。 2．局部性原理(principle of locality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。 时间局限性、空间局限性　3．虚拟存储器的定义　3．虚拟存储器的定义保证进程执行需要的部分程序和数据驻留内存，一段时间内进程都能顺利执行。 虚拟存储器：指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。 用户感觉上的，由实际内存和部分外存构成的存储空间称为“虚拟存储器”。 null 虚拟存储器的概念图 虚拟存储需要解决的问题虚拟存储需要解决的问题（1）程序运行时，如何发现信息不在内存? （2）不在内存的信息，如何调入内存?4.6.2　虚拟存储器的实现方法4.6.2　虚拟存储器的实现方法1．分页请求系统：在分页系统的基础上，增加请求调页功能和页面置换功能所形成的页式虚拟存储系统。 允许只装入少数页面的程序(及数据)，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。 置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。2．请求分段系统2．请求分段系统在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。 它允许只装入少数段的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。 置换是以段为单位进行。4.6.3　虚拟存储器的特征4.6.3　虚拟存储器的特征 1．多次性：一个作业被分成多次调入内存运行。 多次性是虚拟存储器最重要的特征 2．对换性：允许在作业的运行过程中进行换进、换出。 3．虚拟性：从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。 虚拟性是以多次性和对换性为基础的 4.6 请求分页存储管理方式4.6 请求分页存储管理方式在简单页式存储管理的基础上，增加请求调页和页面置换功能。 例： 某计算机的内存储器容量为32KB，系统将其划分成32个1KB大小的块。地址结构长度为221，即整个虚拟存储器最大可以有2MB。null最多2048页每页1KB第0页 第1页 第2页 第2045页 第2046页 第2047页虚拟存储器内存储器辅助存储器第0块 第1块 第2块 第29块 第30块 第31块4.6 请求分页存储管理方式4.6 请求分页存储管理方式 4.6.1　请求分页中的硬件支持 4.6.2　内存分配策略和分配算法 4.6.3　调页策略 4.6.1　请求分页中的硬件支持4.6.1　请求分页中的硬件支持 1．页表机制 2．缺页中断机构 3．地址变换机构 1．页表机制1．页表机制(1) 状态位P：指示该页是否已调入内存。供程序访问时参考。 (2) 访问字段A：记录本页在一段时间内被访问的次数。供选择换出页面时参考。 (3) 修改位M：表示该页在调入内存后是否被修改过。 供置换页面时参考。 (4) 外存地址：指出该页在外存上的地址，供调入该页时参考。2．缺页中断机构2．缺页中断机构系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。 缺页中断是一种特殊的中断，与一般的中断相比，有明显的区别： (1) 在指令执行期间产生和处理中断信号。 (2) 一条指令在执行期间，可能产生多次缺页中断。null2.缺页中断处理过程0 518 4KB 8KB 8300 12KB作业2 虚拟地址空间作业2 第2页作业2的页表内存储器辅助存储器①⑥⑤④③②null缺页中断处理过程3．地址变换机构3．地址变换机构在分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等。null3.地址变换机构课后思考题：课后思考题：分析缺页中断与一般中断的区别。4.6.2　内存分配策略和分配算法4.6.2　内存分配策略和分配算法1.物理块的分配策略 1) 固定分配局部置换(Fixed Allocation，Local Replacement) 2) 可变分配全局置换(Variable Allocation，Global Replacement) 3) 可变分配局部置换(Variable Allocation，Local Replacement) 2) 可变分配全局置换2) 可变分配全局置换先为系统中的每个进程分配一定数目的物理块，OS自身也保持一个空闲物理块队列。 当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的(缺)页装入其中。 从内存中选择一页调出时，可以选择任一进程的页。2.物理块分配算法2.物理块分配算法 1) 平均分配算法 2) 按比例分配算法：根据进程大小按比例分配物理块。 3) 考虑优先权的分配算法 把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。 4.6.3　调页策略4.6.3　调页策略 1．调入页面的时机 2．确定从何处调入页面 3．页面调入过程1．调入页面的时机1．调入页面的时机 1) 预调页策略 以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。 2) 请求调页策略 当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。 4.7 页面置换算法4.7 页面置换算法4.7.1最佳置换算法 4.7.2先进先出置换算法 4.7.3最近最久未使用(LRU)置换算法 4.7.4Clock置换算法 4.7.5最少使用（LFU)置换算法 4.7.6页面缓冲算法（PBA） null程序页面走向程序执行过程中页号的变化序列0 100 104 108 1KB 1120 1124 2KB 2400 3KB第0页 第1页 第2页0 100 104 108 1KB 1120 1124 2KB 2400 3KB第0页 第1页 第2页虚拟存储器虚拟存储器null程序运行时页面走向缺页率(page fault rate)缺页率(page fault rate)缺页率=“缺页次数 / 内存访问次数”(比率) 页面置换算法页面置换算法功能：需要调入页面时，选择内存中哪个物理页面被置换。称为replacement policy。 目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。null页面置换过程4.7.1最佳置换算法4.7.1最佳置换算法最佳置换算法: 其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。 该算法是无法实现的，但可以利用该算法去评价其它算法。 最佳置换算法举例最佳置换算法举例假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 请画出采用最佳置换算法时的置换图，并给出缺页次数和缺页率。 利用最佳页面置换算法时的置换图利用最佳页面置换算法时的置换图结论：发生了6次页面置换，缺页次数为9，缺页率为：9/204.7.2先进先出置换算法4.7.2先进先出置换算法总是淘汰最先进入内存的页面。 对上边的例子， 采用FIFO置换算法时的置换