交通923、927操作系统电子-课件zgsosjiaoan

107一月2023北京交通大学计算机学院翟高寿主讲教师：翟高寿（副教授）联系电话：(办)电子邮件：制作人：翟高寿制作单位：北京交通大学计算机学院《操作系统》207一月2023北京交通大学计算机学院翟高寿第四章存储器管理4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器概念及关键技术4.6请求分页存储管理方式4.7请求分段存储管理方式307一月2023北京交通大学计算机学院翟高寿用户程序处理过程内存装入程序源程序装入模块链接程序库编译程序……目标模块407一月2023北京交通大学计算机学院翟高寿程序的链接链接过程根据外部访问符号名表，将经过编译或汇编得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块关键问题修改相对地址变换外部调用符号链接方式静态链接方式、装入/运行时动态链接方式507一月2023北京交通大学计算机学院翟高寿程序链接示意图目标模块模块ACALLB;Return;L-1相对地址0模块BCALLC;Return;M-10模块CCodeReturn;N-10装入模块模块AJSR“L”;Return;L-1相对地址0模块BJSR“L+M”;Return;L+M-1L模块CCodeReturn;L+M+N-1L+M607一月2023北京交通大学计算机学院翟高寿链接方式比较静态链接方式可执行文件、难以实现“内存”模块共享装入时动态链接便于软件版本的修改和更新便于实现目标模块为多个应用程序共享运行时动态链接将某些目标模块的链接推迟到执行时根据是否需要再完成707一月2023北京交通大学计算机学院翟高寿程序的装入基本目标及相关问题由装入程序将装入模块载入到内存装入位置、地址变换（重定位）及时机装入方式绝对装入方式（单道程序环境）静态可重定位装入方式（多道程序环境）动态运行时装入方式（运行中移动位置）关键概念相对地址、绝对地址、重定位及其寄存器807一月2023北京交通大学计算机学院翟高寿绝对装入模块和可重定位装入模块

JMP1424CodeLOAD1,2224

---------------

Data14242224绝对地址1024绝对装入模块PROGRAMJMPAddriCodeLOAD1,Addrj

------------------DATADataAddriAddrj符号地址目标模块

JMP400CodeLOAD1,1200

---------------

Data4001200相对地址0可重定位装入模块907一月2023北京交通大学计算机学院翟高寿（静态/动态）可重定位重定位程序装入或执行时对装入模块或目标程序中的指令及数据地址的修改过程静态重定位由重定位装入程序在将装入模块装入内存时一次性完成重定位需要连续存储空间，装入后不能移动动态重定位需要特殊硬件（地址变换机构）支持，以保证地址转换不会影响指令的执行速度便于动态链接和代码共享1007一月2023北京交通大学计算机学院翟高寿动态重定位示意图CPU10000相对地址2500+重定位寄存器内存物理地址12500LOAD1,250036510000101001250015000LOAD1,2500365010025005000作业J1107一月2023北京交通大学计算机学院翟高寿第四章存储器管理4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器概念及关键技术4.6请求分页存储管理方式4.7请求分段存储管理方式1207一月2023北京交通大学计算机学院翟高寿4.2

连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4可重定位分区分配4.2.5对换1307一月2023北京交通大学计算机学院翟高寿单一连续分配方式内存划分为系统区和用户区整个用户区为一个用户独占，仅驻留一道程序静态链接和动态重定位技术、存储器保护措施仅适用于单用户、单任务操作系统中CPU界限寄存器基址寄存器逻辑地址<+是物理地址内存否地址错1407一月2023北京交通大学计算机学院翟高寿4.2

连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4可重定位分区分配4.2.5对换1507一月2023北京交通大学计算机学院翟高寿固定分区分配方式用户区分为若干固定区域每个分区可装入一道作业分区划分方法(等分/不等分)内存分配与分区说明表可用于多道程序存储管理A:B:C=150:300:500操作系统作业A作业B作业C存储空间分配情况0300K450K750K1250K1750K分区号大小KB始址K状态1150300已分配2300450已分配3500750已分配45001250已分配1607一月2023北京交通大学计算机学院翟高寿4.2

连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4可重定位分区分配4.2.5对换1707一月2023北京交通大学计算机学院翟高寿动态分区分配方式基本思想根据进程的实际需求，动态地对内存空间进行分配、回收及划分关键问题分区分配用数据结构分区分配算法分区分配与回收操作碎片（零头）处理1807一月2023北京交通大学计算机学院翟高寿分区分配用数据结构(A)空闲分区表分区号大小KB始址K状态156200空闲2100332空闲378520空闲462690空闲5………(B)空闲分区链前向指针0后向指针0N+2N+2N个字节可用分区大小分区状态1907一月2023北京交通大学计算机学院翟高寿分区分配算法首次适应算法FF要求空闲分区链以地址递增次序链接查找开销大，但有利于大作业分配循环首次适应算法首次适应+起始查寻指针+循环查找减少查找开销，但不利于大作业分配最佳适应算法追求既能满足要求且又最小的空闲分区要求空闲分区按大小递增次序链接微观意义上的最佳与宏观上的零头问题2007一月2023北京交通大学计算机学院翟高寿动态分区内存分配流程从头开始查找可变分区分配用数据结构开始m.size≧u.size?检索完否?m.size-u.size≦size?从当前分区划出u.size大小的分区是否否否修改分配用数据结构并执行分配是返回是检索下一分区信息移出当前分区2107一月2023北京交通大学计算机学院翟高寿动态分区内存回收情况F1回收区回收区F2F1回收区F2回收区2207一月2023北京交通大学计算机学院翟高寿动态分区内存回收流程顺序查找分配用数据结构直至找到某分区之m.addr>collected.addr或m.size=0开始是返回回收区与前一空闲区合并同时修正分配用数据结构非第一分区且与前一空闲区相邻?否非最末分区且与后一空闲区相邻?回收区与后一空闲区合并同时修正分配用数据结构与后一空闲区相邻?与后一空闲区合并同时修正分配用数据结构是是回收区collected.size=0?否插入回收区并调整分配用数据结构否是2307一月2023北京交通大学计算机学院翟高寿4.2

连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4可重定位分区分配4.2.5对换2407一月2023北京交通大学计算机学院翟高寿动态重定位分区分配方式紧凑连续分配要求程序装入内存空间的连续性分区分配产生的零头/碎片问题通过移动把多个分散拼接成大分区用户程序内存地址变化及地址修正问题动态重定位动态运行时装入方式及重定位寄存器动态重定位分区分配算法动态分配分区算法+紧凑功能2507一月2023北京交通大学计算机学院翟高寿紧凑（拼接）技术操作系统用户程序220KB用户程序532KB用户程序325KB用户程序635KB操作系统用户程序2用户程序5用户程序3用户程序6112KB紧凑前紧凑后2607一月2023北京交通大学计算机学院翟高寿动态重定位分区分配流程从头开始查找可变分区分配用数据结构开始找到不小于u.size的空闲分区否?空闲分区总和不小于u.size?进行拼凑形成连续空闲区修改分配用数据结构是否否按动态分区方式进行分配，修改分配用数据结构返回是2707一月2023北京交通大学计算机学院翟高寿4.2

连续分配方式4.2.1单一连续分配4.2.2固定分区分配4.2.3动态分区分配4.2.4可重定位分区分配4.2.5对换2807一月2023北京交通大学计算机学院翟高寿多道程序环境下的对换对换的概念及意义内存（进程、程序、数据）外存提高内存利用率对换实现机制UNIX：对换进程（中级调度）对换实现方式进程对换：分时系统页面/分段对换：虚拟存储技术2907一月2023北京交通大学计算机学院翟高寿对换空间的管理文件区和对换区功能、管理目标及管理方式对换区使用情况数据结构空闲分区表/链（盘块为基本单位）对换区分配与回收操作分配算法分配操作回收操作3007一月2023北京交通大学计算机学院翟高寿进程的换出和换入进程的换出被换出进程的选择（进程状态+优先级+内存驻留时间）换出过程（换出非共享或不再共享的程序及数据段对换空间申请换出内存释放内存分配数据结构及PCB修改）进程的换入被换入进程的选择（进程状态+换出时间）换入过程（内存申请换入

PCB修改）3107一月2023北京交通大学计算机学院翟高寿