计算机组织与结构第6章-3节

1、计算机组织与结构授课教师：李静梅授课班级：20122011、2012、2013时间：2013年秋季学期软件学院必修课软件学院必修课软件学院必修课软件学院必修课一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式二、页式虚拟存储器的构成二、页式虚拟存储器的构成三、替换算法三、替换算法6.3 6.3 虚拟存储器虚拟存储器在虚拟存储器中，应用程序员直接用机器在虚拟存储器中，应用程序员直接用机器指令的地址码对整个程序统一编址，这个地址指令的地址码对整个程序统一编址，这个地址宽度所对应的程序空间可以比实际主存的空间宽度所对应的程序空间可以比实际主存的空间大得多，程序不必作任何修改就可以以接近实大得多，程

2、序不必作任何修改就可以以接近实际主存的速度在虚拟存储器上运行。际主存的速度在虚拟存储器上运行。 6.3 6.3 虚拟存储器虚拟存储器一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式虚拟存储器是通过增设的地址映象表机构来实现辅存在虚拟存储器是通过增设的地址映象表机构来实现辅存在主存中的定位的。这种定位技术是把程序分割若干较小的段主存中的定位的。这种定位技术是把程序分割若干较小的段或页，用相应的映象表机构来指明该程序的某段或某页是否或页，用相应的映象表机构来指明该程序的某段或某页是否已装入主存。若已装入主存，则应同时指明其在主存中所处已装入主存。若已装入主存，则应同时指明其在主存中所处的开始位

3、置；若未装入主存，则去辅存中调段或页，并建立的开始位置；若未装入主存，则去辅存中调段或页，并建立程序空间和实存空间的地址映象关系，这样，程序执行时通程序空间和实存空间的地址映象关系，这样，程序执行时通过查映象表将虚地址变换成实地址再访主存。过查映象表将虚地址变换成实地址再访主存。 由于采用的存储映象算法不同，就形成了多种不同的存由于采用的存储映象算法不同，就形成了多种不同的存储管理方式。虚拟存储器常用的管理方式有储管理方式。虚拟存储器常用的管理方式有3种：种： 段式存储管理段式存储管理页式存储管理页式存储管理段页式存储管理段页式存储管理 1 1、段式存储管理、段式存储管理（1 1）段式管理的基

4、础：）段式管理的基础：主要是基于结构化程序设计的思想。一个复杂的大主要是基于结构化程序设计的思想。一个复杂的大程序总可以分解成多个逻辑上相对独立的模块。这些模块可以是主程序、程序总可以分解成多个逻辑上相对独立的模块。这些模块可以是主程序、子程序，也可以是表格、数组、树或向量等。模块的大小可以各不相同，子程序，也可以是表格、数组、树或向量等。模块的大小可以各不相同，每个模块都可以是一个单独的程序段，每段都从每个模块都可以是一个单独的程序段，每段都从0 0开始相对编址。开始相对编址。 一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式（2 2）段式管理的定义：）段式管理的定义：把主存和用户程序按

5、段分配的存储管理方式称为虚把主存和用户程序按段分配的存储管理方式称为虚拟存储器的段式管理。拟存储器的段式管理。（3 3）段式管理的方法：）段式管理的方法：其管理方法与过程如图其管理方法与过程如图6.116.11所示。所示。 1 1、段式存储管理、段式存储管理（4 4）段式存储管理的优点：）段式存储管理的优点：使大程序可分块编制，多人并行，缩短编制时间。使大程序可分块编制，多人并行，缩短编制时间。各段的修改、增删不影响其他各段的编址。各段的修改、增删不影响其他各段的编址。各用户以段的连接形成的程序空间可以与主存的实际容量无关。各用户以段的连接形成的程序空间可以与主存的实际容量无关。可对主存中的程

6、序和数据共享。可对主存中的程序和数据共享。容易以段为单位实现存储保护。容易以段为单位实现存储保护。 一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式（5 5）操作系统的主存区域管理）操作系统的主存区域管理占用区域表：占用区域表：每一行用来指明主存中哪些区域已被占用，被哪道程序的哪个每一行用来指明主存中哪些区域已被占用，被哪道程序的哪个段占用，以及该段在主存中的起点和长度，该段进入主存后是段占用，以及该段在主存中的起点和长度，该段进入主存后是否被修改过等信息。否被修改过等信息。可用区域表：可用区域表：每一行则指明每一个未被占用区的基址和区域大小。每一行则指明每一个未被占用区的基址和区域大小。

7、当一个段由辅存装入主存时：就要将其在占用区域表中增加一当一个段由辅存装入主存时：就要将其在占用区域表中增加一项，并修改可用区域表。项，并修改可用区域表。当一个段从主存退出时：当一个段从主存退出时：就要将其在占用区域表的行的有关字段内容移入到就要将其在占用区域表的行的有关字段内容移入到可用区域表中，并与其它行进行归并处理，得到新的可用区域可用区域表中，并与其它行进行归并处理，得到新的可用区域表。表。1 1、段式存储管理、段式存储管理一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式（5 5）操作系统的主存区域管理）操作系统的主存区域管理当一个段由辅存装入主存时：当一个段由辅存装入主存时：通常有

8、两种可用区域的分配算法：通常有两种可用区域的分配算法：首先分配算法：首先分配算法：顺序扫视可用区域表，当找到第一个不小于要调入段的长度的顺序扫视可用区域表，当找到第一个不小于要调入段的长度的可用区域时，就立即进行分配。可用区域时，就立即进行分配。最佳分配算法：最佳分配算法：先扫视全部可用区域表，然后寻找一个可用区进行分配，使之先扫视全部可用区域表，然后寻找一个可用区进行分配，使之分配后段间剩余的可用区零头最小。分配后段间剩余的可用区零头最小。例例62：图：图6.12(a)所示，所示，A、B、C表示已经调入的程序在存储空间的分配情况，阴表示已经调入的程序在存储空间的分配情况，阴影表示内存空间目前

9、可用。现有程序影表示内存空间目前可用。现有程序D、E、F需要依次调入，请采用不同的分配需要依次调入，请采用不同的分配算法分别进行调度分配。算法分别进行调度分配。 1 1、段式存储管理、段式存储管理一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式两种分配算法实现后的内存情况如图两种分配算法实现后的内存情况如图(b)(b)、(c)(c)所示。所示。结论：结论：本例并不意味着首先分配算法就一定好，也完全可本例并不意味着首先分配算法就一定好，也完全可以出现相反的情况。所以，一般而言，各有优缺点，要酌以出现相反的情况。所以，一般而言，各有优缺点，要酌情取舍。情取舍。 2 2、页式存储管理、页式存储管

10、理一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式（1）段式管理的缺点）段式管理的缺点段表中的地址字段必须是主存中的任意一个绝对物理地址；段表中的地址字段必须是主存中的任意一个绝对物理地址；段表中的段长字段也应该是任意长的一个段；段表中的段长字段也应该是任意长的一个段；存储空间仍有浪费。存储空间仍有浪费。 增加了辅助硬件增加了辅助硬件开销，降低了查开销，降低了查表速度表速度 图图6.13 段式管理方法无法调入时段式管理方法无法调入时 2 2、页式存储管理、页式存储管理一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式（2）页式存储管理的定义）页式存储管理的定义把主存空间和程序空间机械等分

11、成固定大小的页（一页一般在把主存空间和程序空间机械等分成固定大小的页（一页一般在512B到到几几KB），按页顺序编号，让程序的起点必须处在主存中某一页面的起点上。），按页顺序编号，让程序的起点必须处在主存中某一页面的起点上。如图如图6.14所示。所示。 图图6.14 页式存储管理方法中的页表结构图页式存储管理方法中的页表结构图 2 2、页式存储管理、页式存储管理一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式（3）页式存储管理方法：）页式存储管理方法：具体原理如图具体原理如图6.15所示。所示。 图图6.15页式管理的定位映象机构及地址变换过程图页式管理的定位映象机构及地址变换过程图 2

12、2、页式存储管理、页式存储管理一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式（4）页式存储管理的优缺点：）页式存储管理的优缺点：优点：优点：对用户是完全透明的；对用户是完全透明的；映象表的硬件开销小；映象表的硬件开销小；地址变换速度快；地址变换速度快；主存空间利用率高；主存空间利用率高；存储空间保护；存储空间保护；缺点：缺点：不考虑程序的模块性，机械等分成大小相同的页；产生的页内零头无不考虑程序的模块性，机械等分成大小相同的页；产生的页内零头无法利用；法利用；页表有时过长，也会多占用空间；页表有时过长，也会多占用空间； 3 3、段式管理与页式管理的比较（见表）、段式管理与页式管理的比较（

13、见表） 一、不同的虚拟存储管理方式一、不同的虚拟存储管理方式 段式管理页式管理划分 大小不固定固定（机械） 起点任意的起点固定 终点段长决定固定 调入可用连续空间大于等于调入段的长度只要有空页 零头损失大小 透明性对应用程序员不透明透明 共享可以不太方便 1 1、地址的映像与变换、地址的映像与变换 二、页式虚拟存储器的构成二、页式虚拟存储器的构成 地址的映象：地址的映象：是指虚页调入实存的规则，即多用户虚页号是指虚页调入实存的规则，即多用户虚页号NvNv按怎样的对应关系按怎样的对应关系装入主存中哪些页面位置的问题就是地址的映象。装入主存中哪些页面位置的问题就是地址的映象。地址的变换：地址的变换

14、：是指程序按照某种映象被装入实存后，在执行时，多用户虚地址是指程序按照某种映象被装入实存后，在执行时，多用户虚地址NsNs如何变换成对应的实地址如何变换成对应的实地址npnp。地址的变换与所采用的地址映象密切相关。地址的变换与所采用的地址映象密切相关。页面失效：页面失效：要访问的虚页不在实际主存中，就发生了页面失效。要访问的虚页不在实际主存中，就发生了页面失效。页面争用（实页冲突）页面争用（实页冲突）：当某一虚页调入主存某一实页位置时，该位置已被其：当某一虚页调入主存某一实页位置时，该位置已被其它虚页占用，即两个或两个以上虚页想要进入主存中同一个页面位它虚页占用，即两个或两个以上虚页想要进入主

15、存中同一个页面位置的现象。置的现象。映象方法的选择标准：映象方法的选择标准：实页冲突少实页冲突少地址变换速度快地址变换速度快实现简单实现简单辅助硬件少辅助硬件少成本低成本低 这样，每完成一次这样，每完成一次I/OI/O操作操作CPUCPU只需二次进管，只需二次进管，大大减少了对目态程序的大大减少了对目态程序的干扰，提高干扰，提高CPUCPU与外设操与外设操作的重叠程度。同时，系作的重叠程度。同时，系统中多个通道都有自己的统中多个通道都有自己的通道程序，可以并行工作，通道程序，可以并行工作，且每个通道上挂接的多台且每个通道上挂接的多台外设也是并行工作的。外设也是并行工作的。CPUCPU与多道程序

16、与多道程序CPUCPU与多个通道与多个通道通道与通道通道与通道每个通道的各个设备之间每个通道的各个设备之间二、具有通道的计算机系统结构二、具有通道的计算机系统结构都是并行的都是并行的三、通道的类型三、通道的类型三、通道的类型三、通道的类型(1(1、字节多路通道、字节多路通道) ) 适用于连接大量象光电机等字符类低速设备，通道适用于连接大量象光电机等字符类低速设备，通道的的“数据宽度数据宽度”为单字节，以字节交叉方式轮流地为多台外为单字节，以字节交叉方式轮流地为多台外设服务。字节多路通道可以有多个子通道，彼此能独立地设服务。字节多路通道可以有多个子通道，彼此能独立地执行通道指令。各个子通道间是并

17、行工作的，以字节宽度执行通道指令。各个子通道间是并行工作的，以字节宽度分时进出主通道，接在每个子通道上多台设备也能分时使分时进出主通道，接在每个子通道上多台设备也能分时使用子通道。用子通道。三、通道的类型三、通道的类型(2(2、数组多路通道、数组多路通道) ) 宜于挂多台高速的磁盘存储器，宜于挂多台高速的磁盘存储器，“数据宽度数据宽度”为定长块，为定长块，以成组交叉方式轮流的为多台外设服务，假定定长块为以成组交叉方式轮流的为多台外设服务，假定定长块为K。三、通道的类型三、通道的类型(3(3、选择通道、选择通道) ) 宜于接高优先级的高速磁盘等设备，宜于接高优先级的高速磁盘等设备，“数据宽度数据

18、宽度”为可为可变长块，某台设备被选中使用通道后，就独占通道，直到变长块，某台设备被选中使用通道后，就独占通道，直到把设备的信息量传完才释放通道。把设备的信息量传完才释放通道。四、通道的极限流量分析四、通道的极限流量分析通道流量：通道在数据传送期间，单位时间内所传送的字通道流量：通道在数据传送期间，单位时间内所传送的字 节数。节数。通道的极限流量：通道在数据传送期间，所能达到的最大通道的极限流量：通道在数据传送期间，所能达到的最大 流量。流量。f ffmaxf 极限流量与三个因素有关极限流量与三个因素有关 选择一次设备所花的时间选择一次设备所花的时间TS传送一个字节的时间传送一个字节的时间TD

19、通道的工作方式通道的工作方式1.1.通道极限流量的设计通道极限流量的设计 字节多路通道：字节多路通道：数组多路通道：数组多路通道：选择通道：选择通道：显然，显然，T TS S和和T TD D都是定值，当都是定值，当NKNK时，总有：时，总有： DSTTbytef1maxDSTKTKblockfmaxDSTNTNselectfmaxselectfblockfbytefmaxmaxmax2.2.诸设备要求诸设备要求j j号子通道提供的流量能力分析号子通道提供的流量能力分析 分析对象为分析对象为j j号子通道，上边挂接了号子通道，上边挂接了PjPj台外设台外设 ：若若j j为字节多路通道：为字节多路

20、通道：若若j j为数组多路通道：为数组多路通道：若若j j为选择通道：为选择通道： Pjijbytefjifjbytef1maxjblockfjifMAXjblockfPjimax1jselectfjifMAXjselectfPjimax1字节多路通道：字节多路通道：数组多路通道：数组多路通道：选择通道：选择通道：显然，显然，T TS S和和T TD D都是定值，当都是定值，当NKNK时，总有：时，总有： DSTTbytef1maxDSTKTKblockfmaxDSTNTNselectfmaxselectfblockfbytefmaxmaxmax2.2.诸设备要求诸设备要求j j号子通道提供的

21、流量能力分析号子通道提供的流量能力分析2.2.诸设备要求诸设备要求j j号子通道提供的流量能力分析号子通道提供的流量能力分析 显然，设备要求通道的实际最大流量只有小于等于显然，设备要求通道的实际最大流量只有小于等于通道所能达到的极限，才能保证挂在通道所能达到的极限，才能保证挂在j j号子通道上的所有号子通道上的所有设备在满负荷工作的最坏情况下不丢失信息，这一条也设备在满负荷工作的最坏情况下不丢失信息，这一条也是通道流量设计的最基本原则。是通道流量设计的最基本原则。 3.3.整个整个I/OI/O系统流量的设计系统流量的设计 21112maxmax11maxmaxmmjmmjmjjselectfj

22、blockfjbyteff1112111211mjPjimmjmmjPjiPjijifMAXjifMAXjif 可以用等式左右两边的差值的大小衡量可以用等式左右两边的差值的大小衡量I/OI/O系统系统流量利用率的情况。差值越小，利用率越高，设计流量利用率的情况。差值越小，利用率越高，设计就越合理。另外，就越合理。另外，CPUCPU要使用主存，通道也要访问主要使用主存，通道也要访问主存，所以计算机系统的主存流量应为二者的流量之存，所以计算机系统的主存流量应为二者的流量之和。和。 例例5 55 5：设有一字节多路通道，由：设有一字节多路通道，由3 3个子通道组成。共有个子通道组成。共有5 5台外设

23、分别挂在这台外设分别挂在这3 3个子通道上，其中个子通道上，其中A A、B B二个高速印字二个高速印字机各占一个子通道，各自以每机各占一个子通道，各自以每25s25s的时间间隔发一个字的时间间隔发一个字节请求；节请求；C C、D D是二台低速印字机，是二台低速印字机，E E是一台光电输入机，是一台光电输入机，它们它们3 3台外设合用一个子通道，台外设合用一个子通道，C C、D D各自以每各自以每150s150s的时的时间间隔发一个字节请求，而间间隔发一个字节请求，而E E以每以每800s800s的时间间隔发一的时间间隔发一个字节请求。个字节请求。 例例5 56 6：若通道的：若通道的Ts = 9.8us,TTs = 9.8us,TD = 0.2us, = 0.2us,某类低速某类低速设备每隔设备每隔500us500us发出一个字节数字传送请求，问至多可发出一个字节数字传送请求，问至多可以挂几台这类低速设备？对以挂几台这类低速设备？对A、B、C、D、E、F 6 6台高速设台高速设备，若一次通信传送的字节数不少于备，若一次通信传送的字节数不少于10241024个字节，问个字节，问哪些可以挂在通道上？哪些不能？哪些可以挂在通道上？哪些不能？A、B、C、D、E、F6 6台高速设备发出申请的时间间隔：台高速设备发出申请的时间间隔：