第22讲 第四章总复习

河北科技师范学院大专课程

操作系统第二十二讲主讲人：曾晓宁2023/1/31第4章内存管理4.1内存管理功能4.2分区管理4.3页式管理4.4段式管理4.5段页式管理2023/1/314.1内存管理功能4.1.1内存的分配与回收(重点是研究内存分配给多个用户使用和各种分配算法）4.1.2地址重定位（研究各种地址变换机构以及静态和动态重定方法）4.1.3内存的共享与保护（研究保护各类程序、数据区的方法）4.1.4虚拟存储器（主要研究虚拟存储器和各种调度算法）2023/1/31静态重定位和动态重定位地址重定位：目标程序只有通过链接、装入内存才能运行，当程序装入内存时，每道程序不可能都从内存空间的0地址开始装入。因此，程序的逻辑地址与分配到的内存的物理地址不一致，为使程序能正确运行，必须将程序的逻辑地址空间中的逻辑地址转换为内存空间中的物理地址，这一过程称为地址重定位。有静态重定位和动态重定位两种方式；2023/1/31(1)静态地址重定位/静态地址映射静态地址重定位：是指当目标程序被装入内存时，由重定位装入程序，一次性完成逻辑地址到物理地址的转换。在程序执行之前由操作系统完成的。在运行过程中，不再进行地址转换。是由重定位装入程序按照公式：

物理地址=逻辑地址+起始地址把目标程序中所有的逻辑地址转换成物理地址；2023/1/31(2)动态地址重定位是指把目标程序装入内存时，并不立即把逻辑地址转达换为物理地址，而是在程序运行过程中，当CPU访问程序和数据时，才进行地址转换。2023/1/314.2分区管理

也称连续分配方式，是指程序装入的内存空间必须是连续的，操作系统占用一个区域，其它区域供系统中的多个进程共享，这种方法称为分区存储管理。 这是最简单的一种存储管理,按分区划分的时机可分为4.2.1单分区4.2.2固定分区4.2.3可变分区2023/1/314.2.1单分区基本思想：在任一时刻，只有一个进程存在，且这个进程总是从用户区的起始地址开始连续存放，从装入到执行完毕，独占整个用户区。适用于单用户单任务的OS。2023/1/314.2.2固定分区基本思想：把内存空间划分成若干个固定大小的连续存储区，称为分区。每个分区只能装入一道程序，内存被划分成几个分区，就允许装入几道程序。2023/1/31内存不事先进行划分，而是在装入程序时，根据装入程序的实际需要来分配内存空间，这样，内存分区的个数、各分区的大小、在内存中活动的内存个数都是随时间变化的。4.2.3可变分区2023/1/31系统启动后，整个用户区是一个完整的大空闲区。当要装入一个程序时，系统从空闲区中按需要划分一个分区分配给该程序。内存空间经过多次分配和回收后原来一块大的空闲区被分割成了若干个占用区和空闲区。此时，如果要装入一个程序，系统则根据需求和内存空间的使用情况来决定是否分配。若能找到一个满足程序需要的空闲区，则从该空闲区中划出一块与程序大小相同的区域分配给它；剩下的区域又形成一个较小的空闲区；若有相邻的空闲区，则合并成一个较大的空闲区。2023/1/31空闲分区链在每个空闲分区的起始单元设置两个域，一个域用于存放空闲分区的大小；另一个域存放指向下一个空闲分区起始地址的指针。操作系统开辟一个单元，存放第1个空闲分区的起始地址，这个单元被称为“链首指针”。最后一个空闲分区的next中存放标志“NULL”表明它是最后一个。这样就可以把所有的空闲分区按一定规则排列链接成一个链表。2023/1/31常用的内存分配算法当装入一个程序时，按一定的分配算法，从空闲分区链中查找满足需求的空闲分区进行分配，常用的分配算法有以下4种：（1）首次适应算法（2）循环首次适应算法（3）最佳适应算法（4）最坏适应算法2023/1/31方面算法排序方法开始位置确定依据首次适应法地址从小到大链首第一个大小能满足要求的循环首次适应法地址从小到大上次找到的下一个分区第一个大小能满足要求的最佳适应算法长度从小到大链首最佳的、第一个大小能满足要求的、最坏适应算法长度从大到小链首长度最大的2023/1/31回收区不与任何空闲区相邻：将回收区作为一个空闲区节点，直接插入到空闲分区链的适当位置。回收区与后空闲区相邻：则把回收区合并到后空闲分区，不必为回收区创建新节点，只需把后空闲分区节点的起始地址改为回收区的首地址，大小为二者大小之和。分区的回收2023/1/31回收区与前空闲区相邻：将回收区与前空闲区合并为一个空闲区。不必为回收区创建新节点，其首址仍为前空闲区首址，大小改为回收区大小与空闲区大小之和。回收区与前后两个空闲区相邻：将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三个区大小之和，并删除原后空闲区节点。2023/1/31覆盖技术与交换技术在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾；覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现；2023/1/31页式管理允许将程序分散地装入到内存中若干个不连续的空闲分区中，可以全部装入，也可以部分装入。即有效地解决了碎片问题，又能充分利用内存空间，提高了内存利用率。4.3页式管理2023/1/31

用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂；分页时，系统自动将逻辑地址分为页号和页内地址两部分，地址的高位部分为页号，低位部分为页内地址。页号页内地址0111231页号P页内位移量W每页大小：212=4KB地址空间中最多有：210=1M页2023/1/31设逻辑地址为n位页内地址为m位则每页大小为2m最多包含2n-m页mn-mn2023/1/31逻辑地址A（已知）页面大小L（已知）页号P页内地址d页面大小L逻辑地址0A则P=[A/L]d=AmodL逻辑地址/每页大小=商…..余数商：页号余数：页内地址2023/1/31计算时要注意：若给出的地址为16进制，则将其转换为二进制，然后，根据页长及逻辑地址的长度，分别取出逻辑地址的高几位和低几位就得到页号及页内地址。如页长为2K，逻辑地址为16位，则高5位为页号，低11位为页内地址。若给出的地址为10进制，则用公式：

逻辑/页长商为页号，余数为页内地址。如程序地址为8457，

页长为4KB，则8457/4096可得：商为2，余数为256。2023/1/31思想：要求程序全部装入内存后，才能开始运行。在装入程序时，首先把程序划分成若干个大小相等的页面，然后系统按块为单位，将程序的每一页分散地装入到内存的物理块中；一个程序有多少页，就给它分配多少物理块，且这些物理块可以不连续。静态页式管理2023/1/31页表页面系统为了能在内存中找到每个页面对应的物理块而为进程建立一张页面映像表，简称页表。页表作用：实现从页号到物理块号的地址映射。记录了页面与内存物理块之间的对应关系。包含页号和块号两项内容。2023/1/31地址转换分页中的地址映射其实与通常的地址映射的概念是一样的，即把程序地址转换成内存地址，这个转换过程是在程序执行过程中完成的，是动态地址映射。在现代计算机系统中，由系统提供的地址映射硬件来完成地址映射工作。2023/1/31实现从逻辑地址到物理地址的转换。实际上是把逻辑地址中的页号，转换为内存中的物理块号。地址变化任务是借助于页表来完成的。基本任务2023/1/31越界中断页表始址页表长度页表寄存器页号块号逻辑地址页号P块号P’页号P页内地址W物理地址块号P’块内地址W＞页表地址转换过程：2023/1/31解决这个问题的一种方法是把最近访问过的页表放在一组快速存储器中（Cache），从而加快访问内存的速度。把这种快速存储器组成的页表称为快表，用于存放最近访问过的的页表项。快表又叫联想存储器；快表2023/1/31页式虚存管理在静态页式管理的基础上，增加了请求调页功能和页面置换功能来实现虚拟存储器功能。页式虚存管理中，进程开始运行之前，不是装入全部页面，而是只装入立即使用的那部分页面，其余的页面在外存中。在进程运行过程中，当需要访问的页面不在内存中时，则将它们从外存调入内存，动态的装入这些页面。如果此时内存已满，则需要根据某种算法，淘汰某个页面，以便装入需要的页面。2023/1/31驻留位：用来标识该页是否在内存，为1表示在内存，为0表示不在内存；外存地址：表示该页在外存的位置，供调入该页时参考；访问字段：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。修改位：用于表示该页在内存中是否被修改过，为0表示没被修改过，为1表示被修改过。决定了是否需要再将该页写入外存。也可用于页面淘汰。页号驻留位物理块号外存地址访问字段修改位2、扩充页表2023/1/313、缺页中断在页式虚存管理系统中，可以通过查询页表中的驻留位来确定该页是否在内存。当所要访问的页面不在内存时，便产生缺页中断，根据页表中的外存地址找到该页在外存中的位置。再将该页从外存调入内存。2023/1/315、内存分配策略在页式虚存管理系统中，给进程分配内存空间可以采用固定分配和可变分配两种策略。固定分配：在创建进程时，根据进程类型或程序员的要求，系统为每个进程在内存中分配一定数目的物理块；且在进程运行期间不再改变。有平均分配算法、按比例分配算法、优先级分配可变分配：先为每个进程分配一定数目的物理块；在进程运行中，发现缺页时，可在内存中再找一个空闲块分配给该进程；即进程分得的物理块数可动态地改变。2023/1/316、页面置换策略1）在进行页面置换时，可以采用以下两种策略：①全局置换是指当进程在运行中发现缺页，且此时内存空间已满时，由OS从内存中按照某种页面置换算法选择一页调出内存，该页可以是内存中任一进程的页。②局部置换当进程产生缺页中断时，只能从该进程在内存的物理块中选择一页换出，始终保持分配给该进程的物理块数不变。2023/1/312）页面置换策略通常要和内存分配策略配合使用，一般有以下3种组合：①固定分配局部置换策略②可变分配全局置换策略③可变分配局部置换策略2023/1/31页面置换算法1．最佳置换算法（OPT算法）2．先进先出页面置换算法（FIFO算法）3．最近最少使用页面置换算法（LRU算法）4．Clock置换算法(LRU近似算法)2023/1/311．最佳置换算法（OPT算法）思想：置换以后不再被访问或在以后最迟才会访问的页。特点：本算法可以保证最低的缺页率，但由于无法预知哪一个页面是未来最长时间内不再被访问的。因而该算法是无法实现的。但是，可把它作为一种评价标准，比较其他实用方法的优劣，所以，最优算法只具有理论上的意义。2023/1/312．先进先出算法（FIFO算法）思想：总是先淘汰最先进入内存的页面即选择内存中驻时间最长的页面予以淘汰；即先进入内存的页面先被置换掉。理由：最先进入内存的页面不再被访问的可能性最大。

特点：算法简单，容易实现，只要把内存中的页面，按进入内存的先后次序排成一个队列，新进入的页面排在队尾，淘汰页面时，总是从队首进行。但它会淘汰经常访问的页面，不适应进程实际运行的规律。很少使用。2023/1/313．最近最少使用页面置换算法（LRU算法）思想：根据页面调入内存后的使用情况进行决策，当需要置换一页时，选择最近一段时间最长时间没有被访问的页面予以淘汰。这种算法考虑了程序设计的局部性原理。如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰。2023/1/31思想：每页设置一位访问位。在进程的页表中增加一个指针项，将内存中的页面链接成一个循环队列，并用一个指针指向循环队列中下一个将被置换的页面。当把一个页面调入内存，或访问某页时，将该页面对应页表中的访问位置为1。4．Clock转换算法（LRU近似算法）2023/1/31在淘汰页面时，从指针所指的当前位置开始，扫描循环队列：若访问位为1，则重新置为0，跳过该页；若访问位是0，则淘汰该页，指针推进一个位置；若循环队列中所有页面的访问位均为1，则把它们全部重置为0，指针重新指向起始位置，并淘汰该页，然后指针推进一个位置。2023/1/315、改进的clock置换算法淘汰页面时，由于内存中的每一页在外存上都有一份副本，所以，若淘汰页未被修改过，则不需要再将该页写到外存上；否则，必须将该页重新写回到磁盘。这样淘汰未被修改的页面，可以减少系统的开销和启动磁盘的次数；因此，可以同时使用页表中的访问位和修改位来对clock转换算法进行改进。选择未使用过的页同时又是未修改过的页面。（A=0、M=0）2023/1/31以段为单位进行存储管理的，首先要把用户程序按一定的逻辑关系划分成若干个段，且每个段具有完整的逻辑意义。每个程序段都有一个段名，每一段段内也从0开始编址，段内地址是连续的，而段与段的地址不一定连续，且各段长度也不一定相等。4.4段式管理2023/1/312、逻辑地址结构在用户程序中，可通过段名和段内符号名来确定一个地址。例如，给出（A，X）可确定一个地址。程序经过编译之后，段名用一个段号来代替，段内符号名转换成段内地址。2023/1/31所以，逻辑地址由段号和段内地址两部分组成，是一个二维地址结构。描述如下：段号段内地址假定地址长度为32位，其中段号占24~31位，段内地址占0~23位，在该地址结构中，用户程序最多可分成256段，每段的长度最大可达16MB。