操作系统大纲三四五剖析

1、12022-6-26第第3章章 存储器管理存储器管理n考试大纲要求考试大纲要求n（一）（一）内存管理基础内存管理基础1.内存管理概念内存管理概念程序装入与链接；逻辑地址与物理地址空间；内存保护。程序装入与链接；逻辑地址与物理地址空间；内存保护。2.交换与覆盖交换与覆盖3.连续分配管理方式连续分配管理方式4.非连续分配管理方式非连续分配管理方式分页管理方式；分段管理方式；段页式管理方式。分页管理方式；分段管理方式；段页式管理方式。22022-6-26存储器的层次结构存储器的层次结构 n多级存储器结构多级存储器结构n一般计算机，存储层次至少应具有三级：最高层为一般计算机，存储层次至少应具有三级：最

2、高层为CPU寄存寄存器，中间为主存，最底层是辅存。较高档计算机中，根据具器，中间为主存，最底层是辅存。较高档计算机中，根据具体功能分为体功能分为6层，如图层，如图寄存器高速缓存主存磁盘缓存磁盘可移动存储介质32022-6-26程序的装入程序的装入n程序的装入就是把程序装入内存空间。程序的装入就是把程序装入内存空间。n采用三种方式采用三种方式u（1）绝对装入方式：是由装入程序根据装入模块中）绝对装入方式：是由装入程序根据装入模块中的地址，将程序和数据装入内存。的地址，将程序和数据装入内存。u（2）可重定位方式）可重定位方式：是由装入程序根据内存当前的：是由装入程序根据内存当前的实际使用情况，将装

3、入模块装入到内存适当的地方。实际使用情况，将装入模块装入到内存适当的地方。u（3）动态运行时装入方式：动态运行时的装入程序，）动态运行时装入方式：动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟相对地址转换为绝对地址，而是把这种地址转换推迟到程序要真正执行时才进行。到程序要真正执行时才进行。42022-6-26程序的装入程序的装入n绝对装入方式：是由装入程序根据装入模绝对装入方式：是由装入程序根据装入模块中的地址，将程序和数据装入主存块中的地址，将程序和数据装入主存u若知道程序在内存

4、的位置，编译程序将产生若知道程序在内存的位置，编译程序将产生绝对地址目标模块绝对地址目标模块u绝对地址一般由编译程序给出绝对地址一般由编译程序给出u程序被装入内存后，由于程序中的逻辑地址程序被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，所以不允许改变与实际内存地址完全相同，所以不允许改变程序和数据的地址程序和数据的地址u只适于单道环境只适于单道环境52022-6-26程序的装入程序的装入u可重定位方式可重定位方式：是由装入程序根据主存当是由装入程序根据主存当前的实际使用情况，将装入模块装入到主存前的实际使用情况，将装入模块装入到主存适当的地方。适当的地方。F重定位：在装入时对目标程

5、序中指令重定位：在装入时对目标程序中指令和数据的修改过程。会使装入模块中和数据的修改过程。会使装入模块中的所有逻辑地址与实际装入内存的物的所有逻辑地址与实际装入内存的物理地址不同理地址不同62022-6-26程序的装入程序的装入u静态重定位方式静态重定位方式：u是指地址转换工作是在程序装入内存时由装配程序是指地址转换工作是在程序装入内存时由装配程序完成的。装配程序根据将要装入内存的起始地址，完成的。装配程序根据将要装入内存的起始地址，对程序模块中有关的地址部分进行调整和修改对程序模块中有关的地址部分进行调整和修改u（物理地址（物理地址=逻辑地址逻辑地址+程序存放在内存的起始地程序存放在内存的起

6、始地址），一旦确定下来之后不再改变，即静态地址重址），一旦确定下来之后不再改变，即静态地址重定位是在程序执行之前完成的地址转换。定位是在程序执行之前完成的地址转换。u它的优点：无需硬件支持，容易实现。缺点：程序它的优点：无需硬件支持，容易实现。缺点：程序经地址重定位后不能再移动，程序在内存空间只能经地址重定位后不能再移动，程序在内存空间只能连续存储，程序很难被若干个用户所共享。连续存储，程序很难被若干个用户所共享。72022-6-26程序的装入程序的装入u动态运行时装入方式：动态运行时的装动态运行时装入方式：动态运行时的装入程序，在把装入模块装入内存后，并入程序，在把装入模块装入内存后，并不立

7、即把装入模块中的相对地址转换为不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到绝对地址，而是把这种地址转换推迟到程序要真正执行时才进行。程序要真正执行时才进行。F适于多道环境F允许程序移动，如切换F动态重定位F需要特殊硬件支持（重定位寄存器）82022-6-26程序的装入程序的装入u动态重定位：动态重定位：u是指地址转换工作是在程序执行期间由硬件变换机是指地址转换工作是在程序执行期间由硬件变换机构动态实现地址转换的。构动态实现地址转换的。u物理地址物理地址=逻辑地址逻辑地址+重定位寄存器的内容。重定位寄存器的内容。u动态重定位的优点：用户程序在执行过程中内存可动态重定位的优

8、点：用户程序在执行过程中内存可移动，程序不必连续存放在内存中，可以放在不同移动，程序不必连续存放在内存中，可以放在不同区域，若干个用户可以共享同一程序段或数据段。区域，若干个用户可以共享同一程序段或数据段。缺点：需要附加硬件支持，实行存储管理的软件算缺点：需要附加硬件支持，实行存储管理的软件算法比较复杂。法比较复杂。92022-6-26程序的链接程序的链接 n链接程序的功能是将经过编译或汇编后所得到链接程序的功能是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。配成一个完整的装入模块。n实现链接的方法有实现链接的方

9、法有三种三种u静态链接：事先进行链接，以后不再拆开的链接方式静态链接：事先进行链接，以后不再拆开的链接方式u装入时动态链接：用户源程序经编译后所得到的目标装入时动态链接：用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。模块，是在装入内存时，边装入边链接的。u运行时动态链接：某些目标模块的链接，是在程序执运行时动态链接：某些目标模块的链接，是在程序执行中需要该（目标）模块时，才对它进行链接行中需要该（目标）模块时，才对它进行链接102022-6-26内存保护内存保护 内存保护就是防止各用户程序运行时相互内存保护就是防止各用户程序运行时相互被破坏被破坏,最重要的就是不能破坏操作

10、系统最重要的就是不能破坏操作系统.（1）界地址寄存器保护法）界地址寄存器保护法（2）访问授权保护）访问授权保护112022-6-262.交换与覆盖交换与覆盖 n采用交换与覆盖技术是为了节省内存。采用交换与覆盖技术是为了节省内存。n交换就是系统根据需要把主存中暂时不运行的交换就是系统根据需要把主存中暂时不运行的某个（或某些）进程的部分或全部信息移到外某个（或某些）进程的部分或全部信息移到外存，而把外存中的某个（或某些）进程移到相存，而把外存中的某个（或某些）进程移到相应的主存区，并使其投入运行应的主存区，并使其投入运行n覆盖就是指一个作业（或进程）或多个作业覆盖就是指一个作业（或进程）或多个作业

11、（或进程）的若干程序段或数据段共享主存的（或进程）的若干程序段或数据段共享主存的某个区域。实现方法是将一个作业（或进程）某个区域。实现方法是将一个作业（或进程）划分成若干个相互独立的段，将不同时运行的划分成若干个相互独立的段，将不同时运行的程序段或数据段组成覆盖。程序段或数据段组成覆盖。122022-6-263.连续分配方式连续分配方式 u连续分配方式：为一个用户程序分连续分配方式：为一个用户程序分配一个连续的内存空间配一个连续的内存空间F单一连续分配F固定分区分配 F动态分区分配F动态重定位分区分配132022-6-26连续分配方式连续分配方式 u单一连续分配单一连续分配142022-6-2

12、6连续分配方式连续分配方式 u固定分区分配固定分区分配F将内存中的用户空间划分为若干个固定大小将内存中的用户空间划分为若干个固定大小的区域的区域F每个分区中只装入一道作业，一个作业也只每个分区中只装入一道作业，一个作业也只能装入一个分区中，这样可以装入多个作业，能装入一个分区中，这样可以装入多个作业，使它们并发执行。当有一个空闲分区时，便使它们并发执行。当有一个空闲分区时，便可从外存的后备队列中，选择一个适当大小可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业运行完时，又的作业装入该分区；当该作业运行完时，又可从后备队列中选择另一个作业装入该分区可从后备队列中选择另一个作业装入

13、该分区（分区大小可以相同也可以不同）。（分区大小可以相同也可以不同）。 152022-6-26固定分区分配的管理特点固定分区分配的管理特点 n（1）一个作业只能装入一个分区，不能装入两个）一个作业只能装入一个分区，不能装入两个或多个相邻的分区。一个分区只能装入一个作业，或多个相邻的分区。一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不当分区大小不能满足作业的要求时，该作业暂时不能装入。能装入。n（2）通过对）通过对“分区使用表分区使用表”的改写，来实现主存的改写，来实现主存的分配与回收。作业在执行时，不会改变存储区域，的分配与回收。作业在执行时，不会改变存储区域，所以采用

14、静态地址重定位方式。此方法易于实现，所以采用静态地址重定位方式。此方法易于实现，系统开销小。系统开销小。n（3）当分区较大作业较小时，仍然浪费许多主存）当分区较大作业较小时，仍然浪费许多主存空间空间(内零头）。并且分区总数固定，限制了并发执内零头）。并且分区总数固定，限制了并发执行的作业数目。行的作业数目。162022-6-26动态分区分配动态分区分配n动态分区存储管理的基本思想是：动态分区存储管理的基本思想是：在作业要求装入内存储器时，如果当在作业要求装入内存储器时，如果当时内存储器中有足够的存储空间满足时内存储器中有足够的存储空间满足该作业的需求，那么就划分出一个与该作业的需求，那么就划分

15、出一个与作业相对地址空间同样大小的分区分作业相对地址空间同样大小的分区分配给它。配给它。172022-6-26采用的数据结构采用的数据结构 n为了实现分区分配，系统中必须配置相应为了实现分区分配，系统中必须配置相应的数据结构，用来记录内存的使用情况。的数据结构，用来记录内存的使用情况。比如空闲分区的情况，为作业分配内存空比如空闲分区的情况，为作业分配内存空间提供依据。常用的有空闲分区表和空闲间提供依据。常用的有空闲分区表和空闲分区链。分区链。182022-6-26分区分配算法分区分配算法 n（1）首次适应分配算法（）首次适应分配算法（FF）n（2）循环首次适应分配算法（）循环首次适应分配算法（

16、NF）n（2）最佳适应分配算法（最佳适应分配算法（BF）n（3）最坏适应分配算法（最坏适应分配算法（WF）192022-6-26(1)(1)首次适应法首次适应法n要求空闲区按要求空闲区按首址递增的次序组织的次序组织空闲区表（队列）。空闲区表（队列）。n分配：当进程申请大小为分配：当进程申请大小为SIZESIZE的内存时，系的内存时，系统从空闲区链的链首开始查询，直到首次找统从空闲区链的链首开始查询，直到首次找到等于或大于到等于或大于SIZESIZE的空闲区。从该区中划出的空闲区。从该区中划出大小为大小为SIZESIZE的分区分配给进程，余下的部分的分区分配给进程，余下的部分仍作为一个空闲区留在

17、空闲区链中，但要修仍作为一个空闲区留在空闲区链中，但要修改其首址和大小。改其首址和大小。n若找不到满足要求的，则分配失败，返回。若找不到满足要求的，则分配失败，返回。202022-6-26分析分析n注意：每次分配和回收后空闲区链都要按首址递增的次序排序。优点：优点：n这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。闲区。n缺点缺点u容易产生过多的小地址碎片；降低了主存空间利用率。容易产生过多的小地址碎片；降低了主存空间利用率。u每次查找都是从低址开始，增加了查找的开销每次查找都是从低址开始，增加了查找的开销n改进

18、改进u采用循环首次适应算法。采用循环首次适应算法。212022-6-26（2 2）循环首次适应算法）循环首次适应算法n不是每次都从链首开始找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。n设置查寻指针；n循环查找方式n使内存中的空闲分区分布得更均匀，减少了查找时的开销，但会缺乏大的空闲分区。222022-6-26（3 3）最佳适应法）最佳适应法n所谓最佳就是每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免大材小用。n要求按空闲区大小从小到大的次序组成空闲区链。232022-6-26最佳适应法最佳适应法优点：优点：n在系统中若存在

19、一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。n若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。缺点：缺点：n空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。242022-6-26（4 4）最坏适应算法）最坏适应算法n扫描整个空闲分区表，或链表，总是挑选一个最大的空闲区分割给作业使用。n要求按空闲区大小从大到小的次序组成空闲区链。n优点：可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、

20、小作业有利。n缺点：缺乏大的空闲分区，不利于大作业。252022-6-26可重定位分区分配可重定位分区分配 n在连续分配中，必须把一个系统或用户程序在连续分配中，必须把一个系统或用户程序装入一连续的内存空间。装入一连续的内存空间。n不能被利用的小分区称为不能被利用的小分区称为“零头零头”或或“碎碎片片”。n将主存中的所有作业进行移动，使它们相邻将主存中的所有作业进行移动，使它们相邻接。这样，原来分散的多个小分区便拼接成接。这样，原来分散的多个小分区便拼接成一个大分区，从而就可以把作业装入该区。一个大分区，从而就可以把作业装入该区。n这种通过移动，把多个分散的小分区拼接成这种通过移动，把多个分散

21、的小分区拼接成大分区的方法被称为大分区的方法被称为“拼接拼接”或或“紧凑紧凑”，改变作业在主存中位置的工作称为改变作业在主存中位置的工作称为“移动移动”。262022-6-26连续分配方式比较连续分配方式比较作业个数内部碎片外部碎片解决碎片方法相同点提高作业道数单一连续分配1有无无一个程序需全部、连续装入内存中。对换固定分区分配N（分区数）有无无动态分区分配不定无有紧凑272022-6-26非连续分配方式非连续分配方式n分页管理方式n分段管理方式n段页式管理方式282022-6-264.4.1页面与页表页面与页表 作业空间 页表 内存 页表寄存器 0 1 2 3 0 1 2 3 4 5 6 7

22、 ： 0 1 2 3 作业地址空间划分成连续的作业地址空间划分成连续的大小相同的大小相同的页面页面内存划分成连续的大小相等内存划分成连续的大小相等的的块块（也称为（也称为页框页框） 页面的大小与内存块的页面的大小与内存块的大小大小完全完全相同相同作业进入内存时其不同的作业进入内存时其不同的页面页面对应对应于内存中不同的于内存中不同的块，连续页面可以块，连续页面可以对应不对应不连续连续的块。的块。 292022-6-26（1）分页管理方式）分页管理方式n页面（用户程序划分）页面（用户程序划分）把用户程序按逻辑页划分成大小相等的部分，称为页（page） 。从0开始编制页号，页内地址是相对于0编址3

23、02022-6-26n内存空间内存空间按页的大小划分为大小相等的区域，称为块或内存块（物理页面，页框） 在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常不满一块而形成了不可利用的碎片称之为“页内碎片”逻辑上相邻的页，物理上不一定相邻逻辑上相邻的页，物理上不一定相邻312022-6-26n地址结构地址结构用户程序的划分是由系统自动完成的，对用户是用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为透明的。一般，一页的大小为2的整数次幂，因的整数次幂，因此，地址的高位部分为此，地址的高位部分为页号页号，低位部分为，低位部分

24、为页内地页内地址址页号页号 页内地址页内地址0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址04095322022-6-26页表页表n将页号和页内地址转换成内存地址，必须要有一个数据结构，用来登记页号和块的对应关系和有关信息。n这样的数据结构称为页表。n页表的作用就是实现从页号到物理块号的地址映射。332022-6-26页表内容页表内容n页表包含以下几个表项：页表包含以下几个表项：n页号：登记程序地址空间的页号。n块号：登记相应的页所对应的内存块号n其它：登记与存储信息保护有关的信息。页号块号其它05165213342022-6-26地址变换机构地址变换机

25、构n地址变换机构的任务是实现从逻辑地址到物理地址的转换。即把程序地址转换成内存地址，这个转换过程是在程序执行过程中完成的，是动态地址映射。n在现代计算机系统中，由系统提供的地址映射硬件来完成地址映射工作。352022-6-26例例n设页长为1K，程序地址字长为16位，用户程序空间和页表如图。362022-6-26计算时要注意：若给出的地址字为16进制，则将其转换为二进制，然后，根据页长及程序地址字的长度，分别取出程序地址字的高几位和低几位就得到页号及页内地址。如页长为2K，程序地址字为16位，则高5位为页号，低11位为页内地址。372022-6-26若给出的地址字为10进制，则用公式： 程序地

26、址字/页长 商为页号，余数为页内地址。如程序地址为8457， 页长为4KB，则8457/4096可得：商为2，余数为256。382022-6-26快表和联想存储器快表和联想存储器n在前述的页地址变换过程中有一个严重的问题，那就是每一次对内存的访问都要访问页表，页表是放在内存中的，也就是说每一次访问内存的指令至少要访问两次内存，运行速度要下降一半。n第一次访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，形成物理地址n第二次访问内存时，才是从第一次所得地址中获得所需数据（获向此地址中写入数据）392022-6-26n解决这个问题的一种方法是把页表放在一组快速存储器中（Cac

27、he），从而加快访问内存的速度。我们把这种快速存储器组成的页表称为快表，把存放在内存中的页表称为慢表。n快表又叫联想存储器（associative memory）或 TLB（Translation lookaside buffers）用以存放当前访问的那些页表项402022-6-26p页表页表地址越界地址越界 L比较比较P=Lpp. . .快表快表 b+页号页号p 页内地址页内地址dPd物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址地址映射机制地址映射机制412022-6-26两级页表和多级页表两级页表和多级页表n当页表项很多时，仅采用一级页表需要大片

28、连续空间，可将页表也分页，并对页表所占的空间进行索引形成外层页表。由此构成二级页表。n更进一步可形成多级页表。 422022-6-26二级页表结构及地址映射二级页表结构及地址映射101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页存空间432022-6-26页式存储管理方案小结页式存储管理方案小结n优点：解决了碎片问题优点：解决了碎片问题便于管理便于管理可以使程序和数据存放在不连续的主存空间可以使程序和数据存放在不连续的主存空间n缺点：不易实现共享缺点：不易实现共享不便于动

29、态连接不便于动态连接页表都有可能占用较大的存储空间。页表都有可能占用较大的存储空间。要求有相应的硬件支持，从而增加了系统要求有相应的硬件支持，从而增加了系统成本，也增加了系统开销成本，也增加了系统开销442022-6-26（2 2）分段管理方式）分段管理方式n引入段式管理方式主要是为了满足用户和引入段式管理方式主要是为了满足用户和程序员的需要程序员的需要u方便用户：用户希望逻辑分段方便用户：用户希望逻辑分段u信息共享信息共享u信息保护信息保护u动态增长动态增长u动态连接动态连接452022-6-26分段系统基本原理分段系统基本原理分段分段n用户程序划分 按程序自身的逻辑关系划分为若干个程序段，

30、每个程序段都有一个段名，且有一个段号。段号从0开始，每一段段内也从0开始编址，段内地址是连续的。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。n逻辑地址：由段号和段内地址组成段号 段内地址462022-6-26n内存划分内存划分内存空间被动态的划分为若干个长度不相内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起同的区域，称为物理段，每个物理段由起始地址和长度确定始地址和长度确定n内存分配内存分配以段为单位分配内存，每一个段在内存中以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少占据连续空间（内存随机分割，需要多少分配多少），分配多少），

31、但各段之间可以不连续存放但各段之间可以不连续存放472022-6-26n段表段表段映射表。每个程序有一个段表段映射表。每个程序有一个段表程序的每个段在表中占有一个表项，其中程序的每个段在表中占有一个表项，其中记录了该段在内存中的起始地址和段的长记录了该段在内存中的起始地址和段的长度。可放在内存中，也可放在寄存器中。度。可放在内存中，也可放在寄存器中。段表是用于实现从逻辑段到物理内存区的段表是用于实现从逻辑段到物理内存区的映射。映射。段号段号012段首址段首址段长度段长度58K20K100K110K260K140K482022-6-263 3、地址变换机构、地址变换机构段地址映射过程为：n系统中

32、设置了段表寄存器，用于存放段表始址和段表长度TL。n取出段号S和段内位移W。n若STL，段号太大越界。n根据段表始址找到段表，查找段号为S的表目，得到该段在内存的起始地址。n检查段内地址d是否起过该段的段长SL。若超过越界。n把段首地址与段内位移相加，形成内存物理地址。492022-6-26地址变换机构地址变换机构控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址502022-6-26n同页地址变换一样，在段地址变换过程中，也有两次访问内存的问题。为了加快访问内存的速度也可采

33、用快速存储器组成快表。512022-6-26 Cl Cb+段号段号S S 段内地址段内地址d比较比较比较比较b + d段段表表S= Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑地址Lb.SLb地址越界地址越界d=Ld=L地址映射及存储保护机制地址映射及存储保护机制地址越界地址越界地址越界地址越界比较比较522022-6-26段式存储管理方案小结段式存储管理方案小结优点：优点：便于动态申请内存便于动态申请内存管理和使用统一化管理和使用统一化便于共享便于共享便于动态链接便于动态链接缺点：产生外部碎片缺点：产生外部碎片532022-6-26（3 3

34、） 段页式存储管理方式段页式存储管理方式产生背景产生背景:结合页式段式优点，克服二者的缺点结合页式段式优点，克服二者的缺点n基本原理基本原理n地址变换过程地址变换过程542022-6-26基本原理基本原理n用户程序划分用户程序划分按段式划分（对用户来讲，按段的逻辑关系进行按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）划分；对系统讲，按页划分每一段）n逻辑地址逻辑地址n内存划分内存划分按页式存储管理方案按页式存储管理方案n内存分配内存分配以页为单位进行分配以页为单位进行分配段号段号段内地址段内地址页号页号页内地址页内地址552022-6-26n段表：记录了每一段的页表

35、始址和页表长度段表：记录了每一段的页表始址和页表长度n页表：记录了逻辑页号与内存块号的对应关页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页系（每一段有一个，一个程序可能有多个页表）表）n内存分配管理：同页式管理内存分配管理：同页式管理地址变换过程地址变换过程 562022-6-26段号 状态 页表大小 页表始址0111213041页号 状态存储块#0111213041操作系统主存页表段表段表大小 段表始址段表寄存器图 4-21 利用段表和页表实现地址映射 572022-6-26地址变换过程地址变换过程图 4-22 段页式系统中的地址变换机构段表寄存器段表始址段表长

36、度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度582022-6-26n在段页式系统中，为了获得一条指令数据，在段页式系统中，为了获得一条指令数据，须三次访问内存。须三次访问内存。1、访问内存中的段表，从中取得页表始址、访问内存中的段表，从中取得页表始址2、访问内存中的页表，从中取出该页所在的、访问内存中的页表，从中取出该页所在的物理块号，将该块号与页内地址一起形成指物理块号，将该块号与页内地址一起形成指令或数据的物理地址令或数据的物理地址3、从物理地址中取出指令或数据。、从物理地址中取出指令或数据。快表快表地址变换过程地址变换过程 592022-6-26

37、总结总结n固定分区的分配方式会产生内零头，因为是找出一个满足作业要求的空闲分区分配给作业，大小不一定刚好合适，分区中有一部分存储空间会被浪费。n在可变式分区分配中，是按照作业的大小找出一个分区来分配如果大于作业申请的空间，则一分为二，剩下的一分部作为系统的空闲分区，有可能很小无法利用而成为外零头。602022-6-26总结总结n为了解决外零头的问题，提出了离散的分配方式，在分页式存储管理中，存储空间被分面与页大小相等的物理块，作业的大小不可能都是物理块的整数倍，因此在作业的最后一页中有可能有部分空间未被利用，属于内零头。n分段式存储管理中，其内存分配方式类似于动态分区的分配，因此会产生外零头。

38、n段页式存储管理中，其内存分配方式类似于页式的分配，因此会产生内零头。612022-6-26（二）（二） 虚拟内存管理虚拟内存管理 n考试大纲要求考试大纲要求n1.虚拟内存基本概念虚拟内存基本概念2.请求分页管理方式请求分页管理方式3.页面置换算法页面置换算法最佳置换算法（最佳置换算法（OPT）；先进先出置换算法）；先进先出置换算法（FIFO）；最近最少使用置换算法（）；最近最少使用置换算法（LRU）；）；时钟置换算法（时钟置换算法（CLOCK）。）。4.页面分配策略页面分配策略5.抖动抖动抖动现象；工作集。抖动现象；工作集。622022-6-261 虚拟内存基本概念虚拟内存基本概念程序局部性

39、原理程序局部性原理时间局部性时间局部性一条指令被执行了，则在不久的将来它可能一条指令被执行了，则在不久的将来它可能再被执行，再被执行，如果某数据被访问过， 则不久以后该数据可能再次被访问。（循环操作）（循环操作）空间局部性空间局部性若某一存储单元被使用，则在一定时间内，若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用，与该存储单元相邻的单元可能被使用，即程序即程序在一段时间内所访问的地址，可能集中在一定在一段时间内所访问的地址，可能集中在一定的范围之内。的范围之内。（程序顺序执行）（程序顺序执行）632022-6-26虚拟存储器的定义虚拟存储器的定义 n虚拟存储器是指仅把

40、作业的一部分装入内虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体地说，存便可运行作业的存储器系统。具体地说，所谓虚拟存储器是指具有请求调入功能和所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对主存容量进行扩置换功能，能从逻辑上对主存容量进行扩充的一种存储器系统。实际上，用户所看充的一种存储器系统。实际上，用户所看到的大容量只是一种感觉，是虚的，故而到的大容量只是一种感觉，是虚的，故而得名虚拟存储器。得名虚拟存储器。642022-6-262.请求分页式存储管理请求分页式存储管理 n它是建立在纯分页基础上的，增加了请求调它是建立在纯分页基础上的，增加了请求调页功能、

41、页面置换功能所形成的请求分页存页功能、页面置换功能所形成的请求分页存储管理系统。储管理系统。n把作业分成大小相等的若干页，把主存分成把作业分成大小相等的若干页，把主存分成与页大小相等的若干块；对每个作业限定分与页大小相等的若干块；对每个作业限定分给它的主存块数，先把作业的部分页装入主给它的主存块数，先把作业的部分页装入主存的这些块中，在作业运行时再装入所需要存的这些块中，在作业运行时再装入所需要的页。的页。652022-6-26采用的数据结构采用的数据结构 n（1）页表）页表u页表用来记录作业的分配情况页表用来记录作业的分配情况。n（2）缺页中断机构）缺页中断机构u在请求分页系统中，每当所要访

42、问的页面不在在请求分页系统中，每当所要访问的页面不在主存时，便要产生一次缺页中断，请求操作将主存时，便要产生一次缺页中断，请求操作将所缺的页调入主存。所缺的页调入主存。（3）地址变换机构）地址变换机构662022-6-26页表表项页表表项页号、内存块号、状态位、访问位、修改位、页号、内存块号、状态位、访问位、修改位、外存地址外存地址n状态位状态位P：表示该页是否已调入内存，供：表示该页是否已调入内存，供程序访问时参考程序访问时参考n访问位访问位A：用于记录本页在一段时间内被：用于记录本页在一段时间内被访问的次数或最近已有多长时间未被访问，访问的次数或最近已有多长时间未被访问，供选择换出页面时参

43、考供选择换出页面时参考页号页号 内存块号内存块号 状态位状态位P访问位访问位A修改位修改位M外存地址外存地址672022-6-26页表表项页表表项页号、内存块号、驻留位、外存地址、访问页号、内存块号、驻留位、外存地址、访问位、修改位位、修改位n修改位：查看此页是否在内存中被修改过，修改位：查看此页是否在内存中被修改过，供置换页面时参考。供置换页面时参考。n外存地址：该页存放在外存上的地址。供外存地址：该页存放在外存上的地址。供调入该页时参考。调入该页时参考。页号页号 内存块号内存块号 状态位状态位P访问位访问位A修改位修改位M外存地址外存地址682022-6-26缺页中断（缺页中断（Page

44、Fault）机构机构n缺页中断机构缺页中断机构u在请求分页系统中，每当所要访问的页面不在主存时，在请求分页系统中，每当所要访问的页面不在主存时，便要产生一次缺页中断，请求操作将所缺的页调入主存。便要产生一次缺页中断，请求操作将所缺的页调入主存。缺页中断作为中断，它同样需要经历诸如缺页中断作为中断，它同样需要经历诸如保护保护CPU环境环境、分析中断原因分析中断原因、转入缺页中断处理程序进行处理转入缺页中断处理程序进行处理、恢复恢复CPU环境环境等几个步骤。等几个步骤。692022-6-26n缺页中断同一般中断的区别？缺页中断同一般中断的区别？缺页中断同一般中断都是中断，缺页中断同一般中断都是中断

45、，相同点是：保护现场相同点是：保护现场中断处理中断处理恢复现场恢复现场不同点：不同点：n在指令执行期间产生和处理中断信号。一般中断是在指令执行期间产生和处理中断信号。一般中断是一条指令完成后中断，缺页中断是一条指令执行时，一条指令完成后中断，缺页中断是一条指令执行时，发现所要访问的指令或数据不在内存时所产生的中发现所要访问的指令或数据不在内存时所产生的中断断n一条指令执行时可能产生多个缺页中断。如指令可一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。能访问多个内存地址，这些地址在不同的页中。702022-6-26下图用数字标出了缺页中断的处理过程：下图用数

46、字标出了缺页中断的处理过程：根据当前执行指令中的虚拟地根据当前执行指令中的虚拟地址，形成数对：（页号，页内址，形成数对：（页号，页内位移）。用页号去查页表，判位移）。用页号去查页表，判断该页是否在内存储器中断该页是否在内存储器中若该页的若该页的R位（缺页中断位）为位（缺页中断位）为“0”，表示当前该页不在内存，于，表示当前该页不在内存，于是产生缺页中断，让操作系统的中是产生缺页中断，让操作系统的中断处理程序进行中断处理。断处理程序进行中断处理。中断处理程序去查存储分块表，寻中断处理程序去查存储分块表，寻找一个空闲的内存块；查页表，得找一个空闲的内存块；查页表，得到该页在辅助存储器上的位置，并到

47、该页在辅助存储器上的位置，并启动磁盘读信息。启动磁盘读信息。把从磁盘上读出的信息装入到分配把从磁盘上读出的信息装入到分配的内存块中。的内存块中。n根据分配存储块的信息，修改页表中相应的表目内容，即将表目根据分配存储块的信息，修改页表中相应的表目内容，即将表目中的中的R位设置成为位设置成为“1”，表示该页已在内存中，在，表示该页已在内存中，在B位填入所分位填入所分配的块号。另外，还要修改存储分块表里相应表目的状态。配的块号。另外，还要修改存储分块表里相应表目的状态。n由于产生缺页中断的那条指令并没有执行，由于产生缺页中断的那条指令并没有执行，所以在完成所需页面的装入工作后，应该返回所以在完成所需

48、页面的装入工作后，应该返回原指令重新执行。这时再执行时，由于所需页原指令重新执行。这时再执行时，由于所需页面已在内存，因此可以顺利执行下去。面已在内存，因此可以顺利执行下去。712022-6-26页面调入策略页面调入策略 n（1）何时调入）何时调入n（2）何处调入）何处调入n（3）页面调入过程页面调入过程722022-6-26何时调入何时调入 n（1）预调入）预调入n采用一种以预测为基础的调入策略，将预计不久要采用一种以预测为基础的调入策略，将预计不久要使用的页调入主存。使用的页调入主存。n缺点：预计不准缺点：预计不准n场合：进程的首次调入场合：进程的首次调入n（2）请求调入）请求调入n当发生

49、缺页时，提出请求，由系统调入当发生缺页时，提出请求，由系统调入n优点：命中率优点：命中率100%，实现简单，实现简单n缺点：开销大，每次只调入一页缺点：开销大，每次只调入一页n场合：大多数场合：大多数732022-6-26何处调入何处调入n磁盘分对换区和文件区，有不同。磁盘分对换区和文件区，有不同。n（1）磁盘有足够的对换区时，全部从对换区）磁盘有足够的对换区时，全部从对换区调入页面。运行前拷入对换区调入页面。运行前拷入对换区n（2）磁盘无足够的对换区时，修改过的部分）磁盘无足够的对换区时，修改过的部分从对换区调入页面，没修改的部分从文件区从对换区调入页面，没修改的部分从文件区调入。调入。n（

50、3）UNIX方式：运行过的页面从对换区调方式：运行过的页面从对换区调入，未运行的页面从文件区调入入，未运行的页面从文件区调入742022-6-26页面调入过程页面调入过程n保护现场保护现场n转中断处理程序转中断处理程序n查页表，找到页的外存地址查页表，找到页的外存地址n内存未满则调入，修改页表内存未满则调入，修改页表n内存已满，则先置换。被置换的页若被修改内存已满，则先置换。被置换的页若被修改过，则写入磁盘。过，则写入磁盘。n将缺页调入内存，修改页表和快表将缺页调入内存，修改页表和快表n再访内存再访内存752022-6-263.页面置换算法页面置换算法n（1）最佳置换算法）最佳置换算法（OPT

51、）n（2）先进先出置换算法（）先进先出置换算法（FIFO）n（3）最近最久未使用算法（最近最久未使用算法（LRU）n（4）Clock置换算法置换算法762022-6-26最佳置换算法最佳置换算法n理想淘汰算法理想淘汰算法最佳页面算法（最佳页面算法（OPT） 选择以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面淘汰。采用最佳置换算法，通常可保证获得最低的缺页率。772022-6-26最佳置换算法最佳置换算法n假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：n7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1n 进程运行时， 先将7，0，1三

52、个页面装入内存。 以后， 当进程要访问页面2时， 将会产生缺页中断。此时OS根据最佳置换算法， 将选择页面7予以淘汰。引用率70770170122010320304243230321201201770101页框(物理块）203782022-6-26先进先出页面置换算法先进先出页面置换算法n先进先出（先进先出（FIFO）是人们最容易想到的页面淘汰算法。是人们最容易想到的页面淘汰算法。其做法是当要进行页面淘汰时，总是把最早进入内存其做法是当要进行页面淘汰时，总是把最早进入内存的页面作为淘汰的对象。的页面作为淘汰的对象。引用率7077017012201032310443023032101320177

53、0201页框2304204230230127127011792022-6-26n最近最久未用（最近最久未用（LRU）置换算法的着眼点是在要进置换算法的着眼点是在要进行页面置换时，检查这些页面的被访问时间，总是行页面置换时，检查这些页面的被访问时间，总是把最长时间未被访问过的页面置换出去。这是一种把最长时间未被访问过的页面置换出去。这是一种基于程序局部性原理的置换算法。也就是说，该算基于程序局部性原理的置换算法。也就是说，该算法认为如果一个页面刚被访问过，那么不久的将来法认为如果一个页面刚被访问过，那么不久的将来被访问的可能性就大；否则被访问的可能性就小。被访问的可能性就大；否则被访问的可能性就

54、小。最近最久未使用（最近最久未使用（LRU）置换算法）置换算法802022-6-26引用率70770170122010320304403230321132201710701页框4024320321021. LRU(Least Recently Used)置换算法的描述置换算法的描述 4.7.2 最近最久未使用（最近最久未使用（LRU）置换算法）置换算法812022-6-264.7.3 Clock4.7.3 Clock置换算法置换算法 1. 简单的简单的Clock置换算法置换算法 图 4-30 简单Clock置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位 0?选择该页面淘汰

55、是返回置页面访问位“ 0”否块号页号访问位指针0124034215650711替换指针822022-6-26832022-6-262. 改进型改进型Clock置换算法置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。 842022-6-26 其执行过程可分成以下三步

56、： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。 852022-6-264、页面分配策略、页面分配策略 内存分

57、配策略：固定和可变内存分配策略：固定和可变置换策略：全局和局部置换策略：全局和局部组合成组合成3种合适的策略：种合适的策略：n固定分配局部置换固定分配局部置换n可变分配全局置换可变分配全局置换1.可变分配局部置换可变分配局部置换862022-6-265.工作集工作集由于程序的局部性原理，进程在一段由于程序的局部性原理，进程在一段时间内集中访问一些固定页面的子集称为时间内集中访问一些固定页面的子集称为该进程的工作集。该进程的工作集。为了减少进程访问中的缺页次数，为为了减少进程访问中的缺页次数，为每个进程分配一定数量的页框作为工作集每个进程分配一定数量的页框作为工作集使用。使用。872022-6-

58、265.抖动抖动n采用某个淘汰算法淘汰一页时，如果算法选择采用某个淘汰算法淘汰一页时，如果算法选择不当，就会出现这样的现象：刚被淘汰的页面不当，就会出现这样的现象：刚被淘汰的页面马上又要用，因而要把它调入。调入不久再被马上又要用，因而要把它调入。调入不久再被淘汰，淘汰不久再次装入。如此反复，使整个淘汰，淘汰不久再次装入。如此反复，使整个系统处于频繁地调入调出状态，大降低系统的系统处于频繁地调入调出状态，大降低系统的处理效率，这种现象叫抖动。处理效率，这种现象叫抖动。n如果分配给进程的物理块号数与当前工作集大如果分配给进程的物理块号数与当前工作集大小一致，可以有效避免抖动现象。在实际中，小一致，

59、可以有效避免抖动现象。在实际中，可以通过调整淘汰算法，或者根据缺页率的大可以通过调整淘汰算法，或者根据缺页率的大小动态的分配给进程物理页块，都可以防止抖小动态的分配给进程物理页块，都可以防止抖动的发生。动的发生。882022-6-26第第4章章 文件管理文件管理n（一） 文件系统基础1. 文件概念2. 文件逻辑结构顺序文件；索引文件；索引顺序文件。3. 目录结构文件控制块和索引节点；单级目录结构和两级目录结构；树形目录结构；图形目录结构。4. 文件共享5. 文件保护访问类型；访问控制。892022-6-261 1 文件概念文件概念n文件文件是指具有文件名的若干相关元素的集合。是指具有文件名的若

60、干相关元素的集合。元素元素通常是记录。通常是记录。记录记录是一组有意义的是一组有意义的数据数据项项集合。集合。n文件类型文件类型902022-6-26文件操作文件操作n用户通过文件系统所提供的系统调用实施对文件的操作。n1、最基本的文件操作有：创建、删除、读、写、截断文件和设置文件的读、写位置912022-6-26文件操作文件操作2、文件的“打开”和“关闭”操作所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作