操作系统存储管理.ppt

,第三章 操作系统,计算机基础教学课件,第三章 操作系统,2,3.1 引论 3.2 存储管理 3.3 处理器管理 3.4 设备管理 3.5 文件管理 3.6 操作系统的用户接口,第三章 操作系统,3,3.1 引论,3.1.1 什么是操作系统3.1.2 操作系统的分类3.1.3 操作系统的功能和特性,3.1.1 什么是操作系统？,操作系统是最基本的系统软件，是用户和计算机之间的接口,是控制和管理计算机硬件和软件资源，合理的组织计算机工作流程以及方便用户的程序的集合。,3.1.1 什么是操作系统？,计算机系统中硬件和各种软件构成层次关系，硬件是核心(裸机)。,计算机硬件,操作系统,系统实用程序,应用软件,操作系统设计人员,程序员,最终用户,第三章 操作系统,6,手工操作阶段早期批处理阶段执行系统阶段多道程序系统手工操作阶段：程序的读入、编译、装配和执行都由操作人员人工控制。速度慢、效率低。早期批处理阶段：早期联机批处理：早期脱机批处理-用磁带进行I/O 操作,减少了人工干预的时间,操作系统的发展过程,第三章 操作系统,7,3.执行系统阶段采用通道和中断技术，实现 I/O 与处理机并发运行。通道是一种硬件，它控制一台或几台外设，使外设和内存之间直接进行数据传输，而与CPU无关。中断技术使系统能暂时中止正在运行的程序，转向中断处理程序，而被终止的程序在一定条件下又能重新恢复运行。各种中断程序及负责输入输出的控制程序统称为执行系统,常驻内存。,第三章 操作系统,8,4.多道程序系统执行系统中，CPU一次只能执行一个作业。多道程序是指在一台机器上同时运行若干道程序。系统按照各个程序在各个时刻对资源的需求进行时间分配。,3.1.2 操作系统的分类,三大类：多道批处理系统、分时系统、实时系统,多道批处理操作系统多道内存中可存放多道作业；批处理用户与作业之间没有交互作用，用户不能直接控制作业的运行。作业用户要求计算机执行的工作。由作业步组成。,作业被调入系统，先存放在外存缓冲区中，形成作业队列，系统按照一定的调度原则或根据作业的优先程度从作业中调出一个或多个作业进入内存运行。适用于大型计算机系统，要求对资源的分配及作业的调度有精心的设计，管理功能强。,第三章 操作系统,10,3.1.2 操作系统的分类,分时系统：多个用户分享同一台计算机，将CPU在时间上分割成很小的时间段，称为时间片，系统将CPU的时间片轮流分配给多个用户，每个用户通过自己的终端直接控制程序的运行，进行人机交互。由于时间片分割很小，使每个用户感觉自己独占计算机一样。（多路性、交互性、独占性）单道分时：内存中只留一道作业，开销大。前台和后台分时：前台无作业时运行后台作业。多道分时：内存放多道作业，轮流运行，不必调进调出。,第三章 操作系统,11,实时系统：特点：要求对外部发生的随机事件作出及时响应，并对它进行及时处理。适用于工业控制系 或事务处理系统。有较强的中断处理机构，可靠性要求比较高。,3.1.2 操作系统的分类,三种操作系统经常组合起来使用，形成通用操作系统。,实时过程控制：用于工业生产的自动控制、导弹发射和飞机 飞行等控制实验过程控制。实时信息处理：对信息作及时处理，用于机票预订、银行或 商店的数据处理等,操作系统的功能(5个)处理器管理：解决CPU的分配策略、实施方法，以及资源的分配和回收等。(进程控制、进程同步、进程调度、进程通信)存储管理：解决多道程序在内存中的分配，当进程被撤消时回收分配出去的内存，通过对内外存联合管理来扩大存储空间。(内存分配、内存保护、内存扩充)设备管理：对设备进行分配、调度，为用户使用I/O设备提供方便的命令和操作界面。(设备分配、传输控制、设备独立性),3.1.3 操作系统的功能和特性,操作系统的功能文件管理(文件系统)：唯一地标识计算机系统中的每组信息，以便能对它们进行合理的访问和控制。(文件存储空间管理、目录管理、文件操作管理、文件保护)用户接口：提供两种用户接口，以便用户提出 请求和说明服务。程序一级的接口：用户可在程序中直接调用，通过系统调用命令向系统提出各种 资源请求和服务请求。作业控制语言和操作命令：批处理系统中采用。(分时和实时系统中用户通过终端和键盘提出请求),3.1.3 操作系统的功能和特性,第三章 操作系统,14,2.操作系统的特性（4个基本特性）并发性：（OS的最根本特性）可同时运行多道程序，操作系统需解决各活动之间的切换，控制各活动之间的影响及同步操作等问题。共享性：资源共享。相关问题是如何合理分配资源。不确定性：与确定性相互依存，同一程序、相同的数据要求运行结果是确定的。但系统对发生的不可预测的事件的响应应该是不确定的，如程序运行中的错误处理及各种外设的中断申请都应该是不确定的。虚拟性：物理上的实体逻辑上的对应物。,3.1.3 操作系统的功能和特性,第三章 操作系统,15,3.2 存储管理,3.2.1 存储管理的功能及有关概念3.2.2 实存储管理3.2.3 虚拟存储管理,3.2.1 存储管理的功能及有关概念,存储管理分为两大类：实存储管理虚拟存储管理。,第三章 操作系统,17,1、存储器的分级结构,高速缓冲存储器（cache）：又称缓存，速度快、容量小、价格贵，用来存放使用最频繁的信息，以及缓冲CPU与内存之间的速度差。主存储器：又称内存，是程序运行时存放系统和用户的指令及数据的设备。外部存储器：又称外存，如硬盘、磁盘、光盘等；存取速度慢、容量大、价格便宜；可以存放大量的系统和用户的程序及数据；不能由CPU直接读取。,2、存储管理功能,内存分配：解决如何合理分配内存空间保证以保证各作业互不冲突，提高内存的利用率和运行效率。,(内存分配、地址转换、存储保护和内存扩充),第三章 操作系统,19,2、存储管理功能,2）地址转换或重定位地址空间和存储空间 名空间：源程序存放的空间（一般从0开始）地址空间：目标程序占有的地址范围（逻辑地址或相对地址的集合）存储空间：目标程序装入内存后占用的一系列物理单元的集合（物理地址或绝对地址）,重定位：当用户程序调入内存时，需把相对地址转换为绝对地址，同时要对程序中与地址相关的指令进行修改，这一过程称为重定位。静态重定位：通过CPU中一对界地址寄存器来实现。集中一次进行地址转换，在执行过程中不再改变。下界：作业在内存中的起始地址上界：作业在内存中的终止地址,第三章 操作系统,21,动态重定位：在程序执行过程中进行，当CPU访问内存指令时由动态变换机构自动进行地址转换。,3)存储保护：在静态重定位系统中，应满足D x L，否则执行错误处理程序。对动态重定位系统的存储保护将结合有关的存储方式来讨论4)内存扩充：当作业的地址空间大于分配到的存储空间时需采取内存扩充技术。常采用的内存扩充技术：覆盖、交换、虚拟存储,第三章 操作系统,22,3.2.2 实存储管理,分区分配可重定位分区分配覆盖技术交换技术,当作业要求调入内存时，存储管理要提供一个不小于作业地址空间的连续存储空间，当空间不够时，常采用覆盖或交换技术扩充内存。几种常用的实存储管理方法：,第三章 操作系统,23,1、分区分配:适应于小型、微型机上的多道系统,思想：将内存划分为若干个分区，每个分区分配给一个作业，用静态重定位方式进行地址转换，用硬件措施保证各作业互不干扰。划分方式上有固定分区和可变分区两种。固定分区分配：存储器事先被划分为若干个大小不等的分区，存储管理程序根据调入内存作业的最大存储量，找出一个足够大的分区分配给它。系统为每个分区设置一个目录，说明该分区的大小、起始位置、分配状况等信息，所有分区目录构成一个内存状态表。特点：分区大小固定，状态表的结构可以是顺序表也可以是链表；分区的分配和回收算法简单。缺点：内存利用率低，有“碎片”，作业所需空间和分区大小不一定恰好相等。,312kB320kB352kB384kB504kB1024kB,内存,内存状态表,返回,第三章 操作系统,25,例：某系统使用固定分区分配管理，现有1k、9k、33k、121k多道作业进入内存，画出占有空间情况，问浪费多大？,空余空间：7233111=72k,第三章 操作系统,26,2）可变分区分配(动态存储管理)：内存利用率高只有当作业调入内存时，才按作业大小建立分区，当作业执行完后又释放此空间。采用链结构来构造分区目录。空间分配：由于多作业调入内存运行，有些作业运行结束后释放所占空间，内存区呈现占用块与空闲块交叉存在的状态，如图3.8所示。在每块开始与结束的几个字节中存放有关本块状态的信息，称为控制信息区，并把所有的空闲块链成一个双向链表，如图3.9所示。其中,L link和 Rlink为链表左右指针，tag=0表示空闲块，tag=1表示占用块，size 是本块的大小，up link 为本块的起始地址。,第三章 操作系统,27,可变分区分配,图 3.8,图 3.9 控制信息区,占用块,空闲块,第三章 操作系统,28,空间分配例题,设某系统用户区大小为5000字节，地址为1 5000，初始状态如下图a所示，依次分配给5个作业P1 P5,作业占用区大小分别为1000，300，600，900，700。P0 为余下的空闲块，各占用块和空闲块情况如下页图b和c所示。,图 a,1001,1301,2801,1901,图b占用块,图c空闲块,av,3501,第三章 操作系统,30,空间回收：当作业执行完毕后，系统将空间收回，插入到空闲块链表中，但插入时还要判断左右相邻块是否空闲，若是则合并成一个较大的空间,它可通过每一块中头尾的控制信息区的tag标志来判断。设当前回收块起始地址为p,大小为n,则应判断它左邻居p-1和右邻居p+n的tag是否为0，若不为0则将当前回收块插入到空闲块链表中。若出现有tag为0的相邻块，则应修改原空闲块的大小，将本回收块和相邻块合并。,P-1,P,P+n,n,第三章 操作系统,31,空间回收例题在空间分配例题中，当作业P4完成后，应回收P4分区到空闲块链表中，见图a；当P5作业完成后，回收使由于其左右邻居均为空闲块，因此应进行合并，见图b所示。,3501,1901,图a,图b,av,1901,P4 释放,av,P5释放,第三章 操作系统,33,3）空闲区分配算法：由于空闲链表中各空闲块的大小不同，在分配是由一个如何分配的问题。通常有三种分配策略。首次适应法:将找到的第一个大小不小于所需大小n的空闲块，将其一部分分配给用户。最佳适应法：将空闲块链表中一个不小于n而最接近n的空闲块的一部分分配给用户。最差适应法：将空闲块链表中不小于n且是链表中最大空闲块的一部分分配给用户。,第三章 操作系统,34,总结：最佳适应法适用于请求分配内存大小范围较广的系统；最差适应算法每次都从内存中取最大的结点进行分配，从而使链表中结点大小趋于均匀，适用于请求分配内存较均匀的系统；首次适应法通常适用于实现不能掌握运行时可能出现的分配情况。从时间上比较，首次适应法分配时需查询空闲块链表，但回收时只要插入到表头即可；最差适应算法分配时不需查询链表，而回收时要将剩余部分插入链表适当位置；最佳适应法无论分配和回收，仅需查找链表，最费时间。,第三章 操作系统,35,2、可重定位分区分配,碎片问题和存储区的紧缩：碎片问题：在可变分区分配中，内存区由于各作业的多次请求和释放出现大量的碎片，浪费了大量的内存空间。存储器的“紧缩”：为了把分散的碎片集中起来成为一个大分区，需移动各用户程序，使它们集中在主存的一端。2)程序浮动和重定位程序浮动：将主存中用户程序进行移动动态重定位：程序浮动需对程序中所有与地址有关的项重新进行定位，此工作是在程序运行过程中进行的，也就是在CPU每次访问内存单元前进行的。,第三章 操作系统,36,动态重定位实现过程：先将用户作业的目标程序原封不动的装入主存某一分区，即用户程序中与地址有关的各项均保持原来的相对地址，例如下页图b中 Load 1,1000 指令（1000为相对地址）。当该用户程序被调度到处理器上执行时，操作系统将该用户作业区的起始地址（图b中的10023）减去用户目标程序的相对起始地址（图a 为0），然后将减得的值装入定位寄存器中。当处理器要访问主存时，操作系统将程序中的相对地址与定位寄存器中的内容相加，得到主存的绝对地址去访问数据，如图b中绝对地址为11023。,第三章 操作系统,37,0,0100,1000,0100,定位寄存器,10023,地址空间（a),存储空间(b),动态重定位示意图,加法器,第三章 操作系统,38,存储器紧缩的两种解决方法：1）在某个分区释放后立即紧缩，这样系统中始终存在一个连续的自由分区而无碎片。这对于分区的分配管理十分容易，但紧缩工作进行频繁，花费时间较多。2）在请求分配分区找不到足够大的自由分区时再进行紧缩。这样紧缩的次数大大减少，但分配管理较复杂。,第三章 操作系统,39,3、覆盖技术,当用户作业的地址空间大于主存可用空间时，各作业就无法运行。覆盖技术可实现在较小的空间中运行较大的作业。,要进行覆盖的作业必须满足树状的模块结构，其中根部为常驻内存部分，称为根段，其余部分均为覆盖部分；同层模块同一时刻只有一个模块被调用；共享的覆盖空间以最大模块空间分配；,第三章 操作系统,40,A(20kb),B(50kb),C(20kb),F(30kb),E(40kb),D(20kb),根部,树枝,树叶,B,21kb,70kb,C,D,E,B和C可以互相覆盖,F和D,E可以互相覆盖,不用覆盖时需要180kb,用覆盖时需要110kb,覆盖描述语言：ODLROOT A(BF，C(D，F)END,第三章 操作系统,41,4、交换技术,在分时、实时及批处理系统中均有应用，基本思想是只允许一个或几个用户作业保留在主存中。缺点：当作业较大时花费的代价较大。,小结：覆盖和交换技术作为扩充内存的方法，通常与分区分配方法结合使用。但仍存在不足，例如覆盖技术要求用户按模块化结构编制程序，并要写出覆盖文件；交换技术是以整个作业为单位进行内外存交换，当作业较大时花费的代价较大。由此引发了虚拟存储技术的出现。,第三章 操作系统,42,3.2.3 虚拟存储管理,“实存”：作业运行时整个作业的地址空间必须全部装入内存的一个连续空间中，反之作业就无法运行。“虚存”（虚拟存储管理）：用软件方法来扩充存储器，虚拟存储器的概念是指一种实际上并不存在的虚假存储器，它能提供给用户一个比实际内存大得多的存储空间。,基本概念：虚拟地址：程序访问的逻辑地址。实在地址：处理器可直接访问的主存地址。虚拟地址空间：虚拟地址的集合。实在地址空间：计算机主存。注：程序和数据所在的虚拟地址必须放入主存的实在地址中才能运行。因此要建立虚拟地址和实在地址的对应关系，这种地址转换由动态地址映像机构来完成。,第三章 操作系统,44,1、分页存储管理,（1）分页管理的基本概念 页面、页架（块）页面：用户作业的地址空间划分单位 页架：内存的划分单位页面大小页架大小例：假设系统选择页的大小为1k字节，则一个3k字节的作业将被划分为3页。此时主存有5个空白块（块2、3、8、9、11）。因此，当作业2的三块装入内存时可以选择任意3个空白块。图中假定第0页装入主存的块2中，第一页装入块3中，第2 页装入块8中（主存中块9和块11空闲）。,第三章 操作系统,45,分页映射存储图,地址空间,页号,页架号,主存空间,作业2的页表,作业2的地址空间,0,100,2500,3k,1k,2k,0,2k,3k,4k,5k,6k,7k,8k,9k,10k,11k,12k,作业1,0-1块,2块,作业3,8块,作业3,作业2第0页,作业2第2页,作业2第1页,页架号,第三章 操作系统,46,分页系统中的地址结构虚拟地址(逻辑地址):（p,d）p页号，d页内地址(相对地址)页的大小为2的幂。例：页面大小512Byte,给定逻辑地址 A=(1320)8 则 p=INTA/L=1,d=A MOD L=320,地址空间(逻辑地址),页表地址器存器,页号,页架号,状态,主存空间,页表,页架号,0,1,10,10320,页表长,页表起始地址,p,d,p,d,地址变换机构,8进制地址表示,第三章 操作系统,48,例1：已知PMT，逻辑地址为3500，设页面大小为1k，求物理地址。,例2：一个分页管理逻辑地址长16位，页面大小为4096BYTE，逻辑地址为2F6AH，且0、1、2页依次为5、10、11物理块，求物理地址。,0,1,2,3,5,8,10,12,PMT,分配给每道程序的页架数有限内存中页面要随时更换（“抖动”现象）更换算法：根据作业过去访问页面的情况推测未来对页面访问的可能性。,（3）页面变换算法,第三章 操作系统,50,1）先进先出法（FIFOFirst Input First Output）设有一用户程序共分为5页，其执行时页面变化的规律称为页面走向P，分配给该程序的页架数M为3，其页面淘汰过程如下，,P=,M=3,F=,页面走向,先进,后进,适用于按线性顺序访问地址的程序，否则效率不高。,第三章 操作系统,51,2）最近最少使用法（LRUleast recently used）基本思想：过去一段时间中不被访问的页面，在最近的将来不被访问的可能性也最大，应将这种页面首先淘汰。缺点：实现较困难，工作量大，软硬件开销大。,第三章 操作系统,52,LRU页面替换过程,页架号 页号 引用位 指针,页架号 页号 引用位 指针,q,第三章 操作系统,53,P=,M=3,F=,页面走向,先进,后进,例：用LRU算法计算上例的页面淘汰过程及缺页中断率,第三章 操作系统,54,（4）分页管理的存储保护,通过页表地址寄存器中的页表长度来实现保护。（5）分页管理的优缺点 优点:不要求作业在内存中连续存放，较好的解决了碎片问题。作业地址空间不受内存限制，对一些不常用的部分不必常驻内存，为用户提供足够大存储空间，从而有利于多道程序作业。缺点：要求一定的硬件支持，增加了成本。系统要增加页表及其管理程序，从而增加了内存的开销。同时CPU要占有一定时间来处理页面交换。,2、分段存储管理,分段管理的基本概念（适用于模块化结构）段分段地址结构：段表、段地址寄存器 段表（SMT）：段号、长度、起始地址、段的状态 以及存取权限段地址寄存器：,逻辑地址,（2）分段管理中的地址转换,当作业要进行存储访问时，由硬件地址转换机构与段表地址寄存器找到段表中相应段的记录，从而将段式地址空间的二维地址转换成实际内存地址。如下图，将逻辑地址s=2,w=292转换成实际地址8292。,逻辑地址,段表地址器存器,段号,长度,起址,状态,s w,主存空间,8292,地址转换机构,SMT表,（3）分段管理的存储保护,（4）分段管理的优缺点,优点:便于程序模块化处理；便于处理变化的数据；便于共享分段。缺点：要求一定的硬件支持，增加了成本。分段尺寸的大小受到主存的限制。由于段的长度不固定，会出现“碎片”问题，处理机要为存储器的紧缩付出代价。,3、段页式存储管理,段页式管理的基本概念段页结构作业的地址空间采用分段方式，作业的每一段采用分页方式。段页地址结构段表、页表、段地址寄存器,逻辑地址,（2）段页地址转换,主存空间 页架号,状态 页号 页架号,PMT0,PMT3,逻辑地址,SMT,段表地址器存器,页表长度,页表起始地址,状态,物理地址,（3）段页式管理的优缺点,优点:段页式管理具有分页、分段管理的优点，是使用的最广泛、最灵活的一种存储管理技术。缺点：需要更多的硬件支持，增加了硬件的成本，同时也增加了软件的复杂性和管理开销。许多大中型计算机，如IBM370/168、Multics等都采用这种段页式虚拟存储器。,第三章 操作系统,61,4.分页环境下程序的行为特性,程序行为特征的局部性时间局部性：某个地址最近被访问了，很快又再次被访问。空间局部性：某个地址最近被访问了，其附近的地址也会被访问。(2)页面大小的确定微型小型机：128k 512k；中型机：1k 4k(3)程序结构对系统运行效率的影响提高程序访问的局部性，减少访问的离散性。,第三章 操作系统,62,例：有一矩阵A:ARRAY1:100,1:100 OF integer;先行后列存储，如一个进程有3页存储空间，每页200个整数，其中1页已放程序，且已在内存，分别就程序A和程序B的执行国过程计算缺页次数。,程序A:for i=1 to 100 do for j=1 to 100 do Ai,j=0;,程序B:for j=1 to 100 do for i=1 to 100 do S=Ai,j+S;,第三章 操作系统,63,作业,教材第71页习题中的 3.8(采用书上例题数据),第三章 操作系统,64,作业说明,3.8 在分页管理的页面淘汰算法中，若M=4，计算FIFO及LRU两种算法下页面中断率，并与M=3比较。,P=,M=4,F=,先进,后进,M=3时，FIFO的页面中断率为75%。最先进入内存的页面可能是经常被使用的页面，这样就会引起页面频繁的变换，因此 FIFO算法随着被分配的页架数增加反而上升的现象。,第三章 操作系统,65,作业说明,P=,M=3,F=,下面是LRU在M=3时的页面交换。,第三章 操作系统,66,作业说明,P=,M=4,F=,M=4时，LRU的页面中断率为66.7%,比较M=3时，f=83.3%要少。因此 LRU算法随着被分配的页架数增加缺页中断率下降。,下面是LRU在M=4时的页面交换。,