第4章存储器管理(2).ppt

2020/5/30，第4章内存管理。计算机系统中的内存可分为两种类型：内部内存和辅助内存。前者可以由中央处理器直接访问，而后者不能。辅助存储器和中央处理器只能在输入/输出控制系统的管理下交换信息。由于内存可以被中央处理器直接访问，所以它是计算机系统中极其重要的资源。在操作系统中，管理中的内存部分称为“内存管理”。内存能否合理使用将在很大程度上影响整个计算机系统的性能。exit，2020/5/30，4.3连续分配模式，连续分配模式：为用户程序分配连续内存空间，单个连续分配固定分区分配动态分区分配动态重定位分区分配，2020/5/30，4.3连续分配模式，单个连续分配只能用于单用户、单任务操作系统。内存分为两部分：系统区和用户区。系统区域由操作系统使用，通常由用户区域的低地址部分的用户使用。只有一个程序驻留在主内存中，整个用户区域只属于一个用户。当用户的作业空间大于用户区域时，无法加载作业。4.3连续分配方法固定分区分配将内存中的用户空间划分成若干个固定大小的区域，每个分区只能加载一个作业，一个作业只能加载到一个分区中，这样就可以同时加载和执行多个作业。当存在空闲分区时，可以从存储在外部的备份队列中选择适当大小的作业来加载该分区。作业完成后，可以从备份队列中选择另一个作业来加载分区(分区大小可以相同或不同)。2020/5/30，4.3.3动态分区分配。动态分区存储管理的基本思想是：当一个作业需要被加载到内存中时，如果内存中有足够的存储空间来满足该作业的需求，那么一个与该作业的相对地址空间大小相同的分区被划分并分配给它。2020/5/30，分区分配算法，(1)第一自适应分配算法(FF)(2)循环第一自适应分配算法(NF)(3)最优自适应分配算法(BF)(4)最差自适应分配算法(WF)(5)快速自适应分配算法(QF)，2020/5/30，4.3.4伙伴系统，固定分区和动态分区都有缺点。固定分区限制活动进程的数量。当进程大小与可用分区不匹配时，内存空间利用率很低。动态分区方法算法复杂，回收空闲分区时需要进行分区合并等。并且系统开销很大。伙伴系统方法是上述两种记忆方法的折衷。2020/5/30，4.3.4 partner system，partner system规定，无论分配的分区或空闲分区，其大小都是2的k次幂，k是整数，lkM，其中：2l表示分配的最小分区的大小，2m表示分配的最大分区的大小，2020/5/30，4.3.4 partnership，假设存储空间的大小是2M，M是正整数。伙伴系统之所以得名，是因为它的每个块都有一个大小相同的对应“伙伴”块。对于一个N字节的存储请求(N2M)，伙伴系统首先确定2k的最小K值。如果在空闲区域表中可以找到2k大小的空闲块，则分配它；否则，找到一个更大的空闲块，并将其分成两半，重复分割过程，直到生成并分配2k大小的空闲块。因为它被分成两半，所以将有2k大小的空闲块，即它的“伙伴”块。当回收时，如果它的“伙伴”块是空闲的，它将被合并成一个大的空闲块。如果这个空闲块的“伙伴”块仍然空闲，它将继续合并，直到它的“伙伴”块不空闲。2020/5/30，4.3.5哈希算法，利用快速哈希搜索的优点和可用空间表中空闲分区的分布规律，建立哈希函数，构造以空闲分区大小为关键字的哈希表。该表的每个条目记录一个相应的空闲分区列表头指针。在分配空闲分区时，根据所需空闲分区的大小，通过哈希函数计算得到相应的空闲分区链表，实现最优分配策略。，2020/5/30，4.3.6可重定位分区分配。在连续分配中，系统或用户程序必须装入连续的内存空间。不能使用的小分区被称为“碎片”将主内存中的所有作业移动到相邻的位置。这样，多个原本分散的小分区被拼接成一个大分区，从而可以将作业加载到该区域中。2020/5/30，4.3.6可重定位分区分配，2020/5/30，这种通过移动将多个分散的小分区拼接成大分区的方法称为“拼接”或“压缩”，而改变作业在主内存中的位置的工作称为“移动”。移动的程序或数据必须重新定位。动态重定位的动态重定位分区分配算法的实现(当没有足够的空闲分区来满足用户需求时，这种算法是紧凑的)。2020/5/30，4.3.7交换。为什么引入交换？内存中的一些进程被阻塞，占用了大量内存。许多作业等待内存系统将内存中的一些进程临时移动到外部内存。外部存储器中的一些进程被交换到存储器中，并占据前者所占据的区域。这项技术是内存和外部内存之间进程的动态调度。2020/5/30，交换技术，交换指的是将不能在主存储器中暂时运行的进程或暂时不使用的程序和数据交换到外部存储器，并将已经具备运行条件的进程或进程所需的程序或数据交换到主存储器的技术。有两种交换方式。如果交换是基于整个过程，它被称为“整个交换”或“过程交换”。这种交换在分时系统中被广泛使用。其目的是解决主存不足的问题，进一步提高主存的利用率。如果以“页”或“段”为单位进行交换，则分别称为“页交换”或“段交换”，也统称为“部分交换”。这种交换方法是请求分页和请求分段内存的基础，其目的是支持虚拟存储系统。2020/5/30，交换空间的管理。外部存储分为文件区和交换区。文件区用于存储文件。其管理的主要目标是提高文件存储空间的利用率。(离散分配)交换区用于存储从内存中交换出来的进程。它的管理主要是提高进出交换的速度。(连续分配模式)，2020/5/30，交换空间管理。为了管理交换区中的空闲磁盘块，应该在系统中配置相应的数据结构来记录外部存储的使用情况。其形式类似于内存动态分区分配模式中使用的数据结构，即也可以使用自由分区表或自由分区链。空闲分区表中的每个条目应该包含两项，即交换区的头地址及其大小，它们的单位是磁盘块号和磁盘块号。交换区的分配和恢复以及分配算法与动态分区相同。2020/5/30，进程换出、换入和进程换出选择原则：首先选择阻塞或休眠、低优先级、长时间等待进程，然后选择就绪状态、低优先级、长时间等待进程，2020/5/30，进程换出进程，选择换出进程(仅非共享进程)启动磁盘，然后换出、释放内存以修改进程控制块和内存分配表的结构，2020/5/30，进程换入进程：选择如果成功，如果换入失败，进程控制块、内存分配表和其他结构将首先被换出修改。2020/5/30，连续分配方法比较，2020/5/30，4.4基本分页存储管理方法，无论采用什么方法，分区存储管理都会出现碎片，从而降低内存利用率。虽然可以使用一种紧凑的方法来解决碎片问题，但是系统开销太高并且没有实用价值。必须寻求新技术来解决这个问题，因此寻呼技术应运而生。分页技术是由曼彻斯特大学提出的，大约在1960年在阿特拉斯计算机上实现。这项技术对操作系统的发展产生了深远的影响。2020/5/30，在内存中移动作业的主要原因是，在此之前，用户作业必须加载到连续的存储区域才能正确运行。如果不移动，就无法获得大的可用分区，也无法将大的连续分区分配给用户作业。如果用户的作业可以分散并加载到几个不连续的分区中，并且仍然可以保证正确运行，那么就不需要在内存中移动作业。分页存储管理打破了这种“连续”限制，将存储管理向前推进了一步。2020/5/30，4.4.1页和页表，作业地址空间被划分为相同大小的连续页，存储器被划分为相同大小的连续块(也称为页帧)，当作业进入存储器时，它们的不同页对应于存储器中的不同块，并且连续页可以对应于不连续块。页面，用户程序分区根据逻辑页面将用户程序分成大小相等的部分，称为页面。页码从0编译而来。页面中的地址与0，2020/5/30的地址相关。根据页面的大小，内存空间被分成大小相等的区域。它被称为块或内存块(物理页面、页面框架)。当为一个进程分配内存时，进程中的几个页面被分别加载到多个物理块中，这些物理块不能以块为单位彼此相邻。由于一个进程的最后一页通常少于一个片段，因此会形成一个不可用的片段，称为“页内片段”。逻辑上相邻的页面不一定物理上相邻。2020/5/30。地址结构中用户程序的划分由系统自动完成，对用户是透明的。通常，页面的大小是2的整数幂。因此，地址的上部是页码，下部是页内地址，2020/5/30。特定机器的地址结构是确定的。假设逻辑地址空间中的地址是a，页大小是l，页号p和页内地址d可以如下获得：2020/5/30，在图(a)中，内部存储器的总容量是256KB，操作系统需要20KB。如果块的大小为4KB，则有64个块，操作系统占据前5个块，其他块分配给用户。在分页存储管理中，块是存储分配的单位。用户作业仍然相对于“0”寻址，以形成连续的相对地址空间。操作系统接受用户的相对地址空间，然后根据内存块的大小划分空间。在图(b)中，作业a的相对地址空间大小为11KB。根据4KB的划分，它有超过2页，小于3页的大小，但它被视为3页，编号为第0页、第1页和第2页。2020/5/30，因此用户相对地址空间中的每个相对地址可以用“页码，页内位移”来表示。不难看出，对的数量(页号、页内位移)与相对地址一一对应。例如，在图(b)中，相对地址5188对应于对的数量(1，1092)，其中“1”是相对地址所在页面的页码，“1092”是相对地址和页面起始位置之间的位移(4KB=4096)。例如，相对地址9200对应于对的数量(2，108)，“2”是相对地址所在页面的页码，“108”是相对地址和相对地址所在页面的起始位置之间的位移(8KB=8192)。2020/5/30，有了这些准备，如果可以解决在完整地输入不连续的存储块之后作业可以正常运行的问题，那么分配存储块是非常容易的，因为只要存储器中有足够的空闲块，就可以在作业中输入页面的任何块。例如，在图(a)中，作业a被加载到三个分立的存储块中，例如块8、块11和块6。2020/5/30，下面是一个图例，说明如何确保作业在进入非连续存储块后完好无损地正常运行。假设块大小是1KB，作业a的相对地址空间是3KB，有一个指令调用在相对地址100调用子程序，子程序的入口地址是3000(当然是相对地址)。作业A进入系统后分为3页，如图(A)所示。现在，页0、页1和页2被顺序加载到内部存储器的三个不连续块4、9和7中，如图(b)所示。2020/5/30，记录作业a的页面和块对应关系，如图(c)所示，这表明作业a的页面0在块4中，页面1在块9中，页面2在块7中当指令“call3000”被执行时，其中的相对地址3000被转换成对：(2，952)，表示该地址位于作业相对地址空间中的第2页上，并且从该页的起始位置的位移为952。具体计算公式如下：页码=INT相对地址/块大小页内位移=相对地址模块大小。使用对中的“页号”来检查作业a的页和块对应表(如图c所示),以知道相对地址空间中的页2的内容现在在存储器的块7中。将第7个内存块的起始地址和页内偏移量相加，得到相对地址3000的当前绝对地址，即7KB 952=8120。此时，系统将执行正确执行的指令“call8120”。2020/5/30，从上面的描述可以看出，在分页存储管理中，用户程序完整地进入每个存储块。指令中相对地址的重定位是在指令执行时进行的，属于动态重定位，地址的动态重定位是通过以下内容实现的：(1)将相对地址转换成对(页码、页内位移)；(2)建立操作页面和块对应表；(3)根据页码核对页码，分块对应表；(4)绝对地址由块的起始地址和页内位移形成。为了将页号和页内地址转换成存储器地址，页表必须具有数据结构，以记录页号和块以及相关信息之间的对应关系。这种数据结构称为页表。页表的功能是实现从页号到物理块号的地址映射。2020/5/30，系统为每个过程建立页表，页表的长度和第一地址存储在过程的过程控制块(印刷电路板)中。占用处理器的当前进程的页表必须驻留在内存中，其头地址和长度由地址转换机制的页表寄存器指示。2020/5/30，页表内容，页表包含以下项目：页码：注册程序地址空间的页码。块号：注册对应页面的内存块号其他：注册与存储信息保护相关的信息。例如，如图所示，作业1将2页分别加载到内存的块5和块6中。作业2将3页的块2、4和7加载到内存中；作业3将第8个块的1页加载到内存中。2020/5/30，4.4.2地址转换机制，地址转换机制的任务是实现从逻辑地址到物理地址的转换。也就是说，程序地址被转换成存储器地址。该转换过程在程序执行过程中完成，并且是动态地址映射。在现代计算机系统中，系统提供的地址映射硬件完成地址映射工作。在基本地址转换机制系统中，设置页表寄存器PTR，其中存储存储器中页表的起始地址和页表的长度。当不执行正常进程时，页表的起始地址和页表的长度存储在进程的印刷电路板上。当调度程序调度一个进程时，这两个数据被载入页表寄存器。例如，2020/5/30，设置页面长度为1K，程序地址字长为16位，用户程序空间和页面表如图所示。2020/5/30，说明了当执行指令MOVr1，2500时，地址转换步骤如