计算机操作系统期末重点.doc

第5章 内存管理• 寄存器：是存储容量有限的高速存储部件• 特点• 位于CPU内• 寄存器以名字标识， 没有地址编号• 作用• 可用来暂存指令、数据和地址• 分类• 通用寄存器• 指令指针寄存器• 标志寄存器• 段寄存器• 虚拟存储技术 使用户程序的大小和结构不受主存容量和结构的限制，即使在用户程序比实际主存容量还要大的情况下，程序也能正确运行5.2.1分区管理基本原理固定分区管理• 固定分区是指系统在初始化时，将内存空间划分为若干个固定大小的区域1. 分区原则（1）分区大小划分• 分区大小相等：适合于多个相同程序的并发执行；• 分区大小不等：多个小分区、适量的中等分区、少量的大分区根据程序的大小，分配当前空闲的、适当大小的分区 （2）分区个数不变，大小不变2、固定分区管理• 使用的数据结构：分区状态表• 用于分配时查找未分配空间动态分区管理1. 分区原则• 根据用户进程对内存的需求而划分：• （1）根据作业的大小动态地划分分区；• （2）各分区的大小是不定的；• （3）内存中分区的数目也是不定的• 问题：各作业释放后的空间不连续，导致总的空闲空间很大却不能分配的情况发生易产生碎片（越分越小，直到成为小空闲区不能分配）。

• 固定分区的分配与回收• 分配• 多作业队列：将大小相近的作业放在同一个等待队列中 / • 单作业队列：所有作业放在一个等待队列中常见空闲区查找算法• 空闲区表的组织• 按空闲区大小的升序（或降序）组织；• 按空闲区首址升序（或降序）组织• 查找算法：以空闲区表组织的方法为基础,采用不同的方式选择空闲区• 最佳匹配（最佳适应算法）• 首次匹配（首次适应算法）• 下次匹配（*）• 最坏匹配• 快速匹配（*）1、最佳适应算法• 思想：尽可能分配大小与请求相匹配的空闲区• 组织方式：空闲区表按空闲区大小从小到大组织• 分配• 按申请的大小逐个与空闲区大小进行比较，找到与申请最接近的空闲区分配• 缺点：分割后的空闲区很小，直至无法使用，而造成浪费2、首次适应算法• 思想：尽可能在低地址实施分配• 保留高地址部分的大空闲区• 组织方式：按空闲区首址从小到大组织空闲区分区管理的优缺点• 主要优点• 实现了多道程序共享内存；• 实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销；• 实现存储保护的手段也比较简单• 主要缺点• 内存利用不够充分系统中总有一部分内存空间得不到利用，存在碎片• 内碎片：指分配给作业的存储空间中未被利用的部分。

固定分区分配中存在• 外碎片：系统中无法利用的小存储块动态分区分配中存在• 无法实现内存的扩充 当进程的地址空间大于内存空间时，进程无法运行也即进程的地址空间受实际内存空间的限制• 必须连续存放进程在内存中总是分配一块连续的存储空间，无法很好地利用碎片，虽然可以通过移动技术来整理内存空间，但代价较高• 必须一次性将作业全部调入内存，若内存没有足够的空间，则等待• 5.4 页式管理5.4.1 页式管理的基本原理页式管理的引入• 分区存储管理的主要问题是碎片问题• 问题描述 在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户程序利用而浪费• 问题产生原因• 作业要求分配的空间连续,主存有足够的空间但因不连续而不能分配• 解决问题的思路• 程序适应主存将程序分开存放—分页存储管理技术 • 分页的思想• 页(虚拟页)：程序地址空间分成大小相等的页面• 块(内存块、页块、页祯、内存页面)：把内存分成与页面大小相等的块• 思想：当一个用户程序装入内存时，针对每一页分配一个内存块一个作业的若干连续的页，可以分配到内存中若干不连续的块中1. 内存页面分配与回收• 页式存储管理的数据结构• (1)页表:页表包括用户程序空间的页面与内存块的对应关系。

页表每个进程至少一张• (2)请求表:表明各进程与其分页的页面之间的关联请求表整个系统一张• (3)存储页面表：表示内存的分配情况存储页面表一个系统一张，可用位示图表示• 图 5.17位示图 • 5.4.2静态页面管理• 2.分配算法• 利用页表、请求表、位示图进行分配3.页式地址变换(1)虚地址（线性地址、逻辑地址）(2)分页地址映射机制• 虚地址切分：页号与页内位移• 划分页号和页内地址的依椐：页的大小• 2X =页大小，X即为页号的最低位二进制表示虚地址页号页内位移十六进制表示页号、页内位移(3)地址变换• 使用二进制方法求物理地址① 将逻辑地址线性分割求出页号P和页内位移W：• 若逻辑地址以十六进制、八进制的形式给出，将逻辑地址转换成二进制；• 按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）；② 将位移量直接复制到内存地址寄存器的低位部分；③ 以页号查页表，得到对应块号，将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址• 使用十进制方法求物理地址• 根据逻辑地址求出页号P和页内位移W；• 页号P=逻辑地址 % 页大小(%表示整除)• 页内位移W=逻辑地址 mod 页大小• 根据页号查页表得块号B；• 物理地址=块号B×页大小+页内位移W• 公式说明• 物理地址＝块起始地址＋块内位移W • 块起始地址＝块长×块号 块长=页长• 块内位移＝页内位移 【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。

解：求虚地址0AFEH的物理地址：0000 1010 1111 1110P＝1 W＝010 1111 1110MR＝0100 1010 1111 1110＝4AFEH求虚地址1ADDH的物理地址：0001 1010 1101 1101P＝3 W＝010 1101 1101MR＝0010 1010 1101 1101＝2ADDH【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址解：转换虚地址 3412：P＝3412 ％ 2048 ＝1W＝ 3412 mod 2048 ＝ 1364MR=9*2048+1364=19796转换虚地址 7145：P＝7145 ％ 2048 ＝3W＝7145 mod 2048 ＝1001MR=5*2048+1001=11241问题：块号若为十六进制的字母表示，MR如何计算？(十六进制转换成十进制)例：考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：（1）逻辑地址至少需要多少二进制位表示？ （2）物理地址至少需要多少二进制位表示？分析 ：逻辑地址结构由两个部分组成： 前一部分表示该地址所在页面的页号P； 后一部分表示页内地址(页内位移)W。

物理地址中块号的地址位数决定了块的数量由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同解 ：因为页面数为8=2^3，故需要3位二进制数表示每页有1024个字节，1024=2^10，于是页内地址需要10位二进制数表示32个物理块，需要5位二进制数表示（32=2^5）1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示• 物理地址计算• 有一系统采用页式存储管理，某个作业大小是4GB，页大小为4KB，依次装入内存的第6、5、3、2块，• （1）画出页表；• （2）试将虚地址5000，12000转换成内存地址• 5.4.3 动态页式管理(请求页式管理)• 复习: 5.3 覆盖与交换技术• 实现内存扩充的方法：• 采用覆盖技术• 采用交换技术• 采用虚拟存储技术• 常用的虚拟存储技术• 请求分页存储管理• 请求分段存储管理• 请求段页式存储管理• 分页内存管理方式• 静态分页管理• 动态分页管理• 静态分页管理• 基本思想：进程开始执行前，将全部页装入内存。

• 动态分页管理（请求页式管理）• 基本思想：进程开始执行前，只需装入即将运行的页面，然后根据需要载入其他页面• 请求页式管理的调入策略• 预测调页：分析预测，运行前调入• 系统根据作业运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断• 缺点:系统无法预计系统中作业的运行情况，难以实现• 请求调页（请求分页）：缺页请求，运行时调入• 进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求将它所请求的页调入内存 • 请求页式管理的页表结构• 页表：反映该页是否在内存，在外存的位置，在内存的时间的长短，是否需要回写等• 页号：• 块号：• 中断位：0 表示该页在内存，1示该页不在内存（需要缺页中断）• 辅存地址：该页在辅存的位置• 修改位：0 表示该页调入内存后没有修改，1表示页调入内存后修改过• 引用位：0 表示最近没有被访问，1表示最近被访问过页号 块号 中断位 辅存地址 修改位 引用位请求分页的页表结构……• 5.4.4 请求页式管理的页面置换算法• 当要将辅存中的一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。

用来选择淘汰哪一页的规则叫做置换算法，也称为淘汰算法• 常用算法：• 先进先出算法FIFO：淘汰先调入内存的页• 最久未使用淘汰算法LRU：淘汰未被访问的页中时间最长的页• 最近未使用淘汰算法NUR：淘汰第1个最近未被访问的页（淘汰页表中第一个访问位为0的页）• 最不经常使用页面淘汰算法（LFU）：淘汰那些到当前时间为止访问次数最少的页页表中增加一个访问记数器 • 最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的这种算法是不可能的• 页面淘汰算法优劣的衡量标准：缺页中断率f’• f’＝f／a （a是总的页面访问次数，f是缺页中断次数）【例】一个进程已分到4个页帧（块）（M=4），其页表如下表所示，当进程访问第4页时产生缺页中断，请分别用FIFO、LRU、NRU算法决定将哪一页淘汰？是否需要回写？ 页表： 页号 页帧 装入时间 最近访问时间 访问位 修改位 2 0 60 161 。