计算机操作系统期末重点

-.z.第5章内存管理存放器：是存储容量有限的高速存储部件。特点位于CPU内。存放器以名字标识，没有地址编号。作用可用来暂存指令、数据和地址分类通用存放器指令指针存放器标志存放器段存放器虚拟存储技术 使用户程序的大小和构造不受主存容量和构造的限制，即使在用户程序比实际主存容量还要大的情况下，程序也能正确运行。分区管理根本原理

固定分区管理固定分区是指系统在初始化时，将内存空间划分为假设干个固定大小的区域1.分区原则〔1〕分区大小划分分区大小相等：适合于多个一样程序的并发执行；分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。〔2〕分区个数不变，大小不变2、固定分区管理使用的数据构造：分区状态表用于分配时查找未分配空间动态分区管理1.分区原则根据用户进程对内存的需求而划分：〔1〕根据作业的大小动态地划分分区；〔2〕各分区的大小是不定的；〔3〕内存中分区的数目也是不定的。问题：各作业释放后的空间不连续，导致总的空闲空间很大却不能分配的情况发生。易产生碎片〔越分越小，直到成为小空闲区不能分配〕。固定分区的分配与回收分配多作业队列：将大小相近的作业放在同一个等待队列中。单作业队列：所有作业放在一个等待队列中。常见空闲区查找算法空闲区表的组织按空闲区大小的升序〔或降序〕组织；按空闲区首址升序〔或降序〕组织。查找算法：以空闲区表组织的方法为根底,采用不同的方式选择空闲区。最正确匹配〔最正确适应算法〕首次匹配〔首次适应算法〕下次匹配〔*〕最坏匹配快速匹配〔*〕1、最正确适应算法思想：尽可能分配大小与请求相匹配的空闲区。组织方式：空闲区表按空闲区大小从小到大组织。分配按申请的大小逐个与空闲区大小进展比较，找到与申请最接近的空闲区分配。缺点：分割后的空闲区很小，直至无法使用，而造成浪费。2、首次适应算法思想：尽可能在低地址实施分配保存高地址局部的大空闲区。组织方式：按空闲区首址从小到大组织空闲区空闲区分区管理的优缺点主要优点实现了多道程序共享内存；实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销；实现存储保护的手段也比较简单。主要缺点内存利用不够充分。系统中总有一局部内存空间得不到利用，存在碎片。内碎片：指分配给作业的存储空间中未被利用的局部。固定分区分配中存在。外碎片：系统中无法利用的小存储块。动态分区分配中存在。无法实现内存的扩大。当进程的地址空间大于内存空间时，进程无法运行。也即进程的地址空间受实际内存空间的限制。〔*〕必须连续存放。进程在内存中总是分配一块连续的存储空间，无法很好地利用碎片，虽然可以通过移动技术来整理内存空间，但代价较高。〔*〕必须一次性将作业全部调入内存，假设内存没有足够的空间，则等待。〔*〕5.4页式管理

页式管理的根本原理页式管理的引入分区存储管理的主要问题是碎片问题。问题描述在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户程序利用而浪费。问题产生原因作业要求分配的空间连续,主存有足够的空间但因不连续而不能分配解决问题的思路程序适应主存。将程序分开存放—分页存储管理技术。分页的思想页(虚拟页)：程序地址空间分成大小相等的页面块(内存块、页块、页祯、内存页面)：把内存分成与页面大小相等的块。思想：当一个用户程序装入内存时，针对每一页分配一个内存块。一个作业的假设干连续的页，可以分配到内存中假设干不连续的块中。内存页面分配与回收页式存储管理的数据构造(1)页表:页表包括用户程序空间的页面与内存块的对应关系。页表每个进程至少一张。(2)请求表:说明各进程与其分页的页面之间的关联。请求表整个系统一张。(3)存储页面表：表示内存的分配情况。存储页面表一个系统一张，可用位示图表示。图5.17位示图静态页面管理2.分配算法利用页表、请求表、位示图进展分配。3.页式地址变换(1)虚地址〔线性地址、逻辑地址〕(2)分页地址映射机制虚地址切分：页号与页内位移划分页号和页内地址的依椐：页的大小。2*=页大小，*即为页号的最低位二进制表示虚地址二进制表示虚地址页号页内位移十六进制表示页号、页内位移(3)地址变换使用二进制方法求物理地址将逻辑地址线性分割求出页号P和页内位移W：假设逻辑地址以十六进制、八进制的形式给出，将逻辑地址转换成二进制；按页的大小别离出页号P和位移量W〔低位局部是位移量，高位局部是页号〕；将位移量直接复制到内存地址存放器的低位局部；以页号查页表，得到对应块号，将块号转换成二进制数填入地址存放器的高位局部，从而形成内存地址。使用十进制方法求物理地址根据逻辑地址求出页号P和页内位移W；页号P=逻辑地址%页大小(%表示整除)页内位移W=逻辑地址mod页大小根据页号查页表得块号B；物理地址=块号B×页大小+页内位移W公式说明物理地址＝块起始地址＋块内位移W块起始地址＝块长×块号块长=页长块内位移＝页内位移【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。解：求虚地址0AFEH的物理地址：0000101011111110P＝1W＝01011111110MR＝0100101011111110＝4AFEH求虚地址1ADDH的物理地址：0001101011011101P＝3W＝01011011101MR＝0010101011011101＝2ADDH【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解：转换虚地址3412：P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796转换虚地址7145：P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=11241问题：块号假设为十六进制的字母表示，MR如何计算？(十六进制转换成十进制)例：考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：〔1〕逻辑地址至少需要多少二进制位表示？〔2〕物理地址至少需要多少二进制位表示？分析：逻辑地址构造由两个局部组成：前一局部表示该地址所在页面的页号P；后一局部表示页内地址(页内位移)W。物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小一样，所以物理地址中块内地址与逻辑地址中的页内地址位数一样。解：因为页面数为8=2^3，故需要3位二进制数表示。每页有1024个字节，1024=2^10，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示〔32=2^5〕。〔1〕页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。〔2〕页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。物理地址计算有一系统采用页式存储管理，*个作业大小是4GB，页大小为4KB，依次装入内存的第6、5、3、2块，〔1〕画出页表；〔2〕试将虚地址5000，12000转换成内存地址。动态页式管理(请求页式管理)复习:5.3覆盖与交换技术实现内存扩大的方法：采用覆盖技术采用交换技术采用虚拟存储技术常用的虚拟存储技术请求分页存储管理请求分段存储管理请求段页式存储管理分页内存管理方式静态分页管理动态分页管理静态分页管理根本思想：进程开场执行前，将全部页装入内存。动态分页管理〔请求页式管理〕根本思想：进程开场执行前，只需装入即将运行的页面，然后根据需要载入其他页面。请求页式管理的调入策略预测调页：分析预测，运行前调入系统根据作业运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。缺点:系统无法预计系统中作业的运行情况，难以实现。请求调页〔请求分页〕：缺页请求，运行时调入进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求将它所请求的页调入内存。请求页式管理的页表构造页表：反映该页是否在内存，在外存的位置，在内存的时间的长短，是否需要回写等。页号：块号：中断位：0表示该页在内存，1示该页不在内存〔需要缺页中断〕辅存地址：该页在辅存的位置修改位：0表示该页调入内存后没有修改，1表示页调入内存后修改正引用位：0表示最近没有被访问，1表示最近被访问过页号页号块号中断位辅存地址修改位引用位请求分页的页表构造……请求页式管理的页面置换算法当要将辅存中的一页面并送入到全满的内存中时，必须把已在内存中的*一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法，也称为淘汰算法。常用算法：先进先出算法FIFO：淘汰先调入内存的页最久未使用淘汰算法LRU：淘汰未被访问的页中时间最长的页最近未使用淘汰算法NUR：淘汰第1个最近未被访问的页〔淘汰页表中第一个访问位为0的页〕最不经常使用页面淘汰算法〔LFU〕：淘汰那些到当前时间为止访问次数最少的页。页表中增加一个访问记数器。最正确算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。页面淘汰算法优劣的衡量标准：缺页中断率f’f’＝f／a〔a是总的页面访问次数，f是缺页中断次数〕【例】一个进程已分到4个页帧〔块〕〔M=4〕，其页表如下表所示，当进程访问第4页时产生缺页中断，请分别用FIFO、LRU、NRU算法决定将哪一页淘汰？是否需要回写？页表：页号页帧装入时间最近访问时间访问位修改位2060161011113016000022616210332016311FIFO：淘汰最先调入的页面〔页帧为3的页〕∵修改位为1，∴要回写。LRU：淘汰最久未访问的页〔页帧为1的页〕∵修改位为0，∴不要回写。NRU：淘汰最近未使用的页，淘汰第一个访问位为0的页〔页帧为0的页〕∵修改位为1，∴要回写。【例】对访问串：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3和4时，使用FIFO〔先进先出〕和LRU〔最久未使用〕置换算法的缺页率，结果说明了什么？〔设驻留集M表示分给该作业的内存块数〕分析：解FIFO： M＝3f’＝f／a＝9／12＝75% M＝4f’＝10／12≈83%LRU： M＝3f’＝f／a＝10／12≈83%M＝4f’＝f／a＝8／12≈67%Belady异常现象：对于FIFO算法，有时会出现当M增加时缺页次数不是减少，反而增加的现象。补充:抖动抖动主存和辅存之间的频繁的页面置换现象称为抖动，也称为颠簸，其导致系统效率急剧下降。产生抖动的原因：系统的淘汰算法不合理从而导致刚淘汰的页面马上又要访问的频繁的页面置换状态。系统在考虑置换算法时既要考虑有尽可能少的缺页率、置换算法的简单性、还要尽量防止系统抖动。段式管理的根本原理段程序按逻辑上有完整意义的段来划分，称为逻辑段。例如主程序、子程序、数据等都可各成一段。每个段的大小可以不相等。逻辑地址程序中的逻辑地址由段号和段内位移两局部〔二维〕组成。段号将一个程序的所有逻辑段从0开场编号，称为段号。段内地址每一个逻辑段都是从0开场编址，称为段内地址。段号段号S段内位移W程序逻辑地址—段式地址程序逻辑地址—段式地址第8章文件管理文件系统操作系统中负责管理和存取文件信息的软件。主要功能实现"按名存取〞。用户按照可见的文件逻辑构造提供的方式进展信息的加工和存取。这种逻辑构造独立于物理存储设备，对用户透明，用户不必了解文件存取的物理细节，由文件系统进展文件名到文件存储设备物理地址的映射。对磁盘等外存空间进展统一管理。用户创立文件时为其分配外存空间，用户删除或修改文件时回收或调整其外存空间，以提高外存空间的利用率。提供适宜的文件物理构造。文件在物理设备上的存放方式称为文件的物理构造，一个好的文件物理构造会给系统带来好的空间和时间利用率。完成对存放在存储设备上的文件信息的查找。提供用户接口。如键盘命令、图形菜单、批处理和系统调用函数，均由文件系统提供。提供有关文件自身的效劳，如文件的共享和保护以及文件完整性控制等。文件分类按文件性质和用途分类(*)按文件保护方式分类〔*〕按文件的逻辑存储构造分类有构造文件：由假设干个记录构成的文件，又称记录式文件；无构造文件：由字符序列所构成的文件，又称为流式文件。按用户观点分类普通文件(常规文件)：是指系统中最一般组织格式的文件，一般是字符流组成的无构造文件；目录文件：是由文件的目录信息构成的特殊文件，操作系统将目录也做成文件；特殊文件〔设备驱动程序〕：在UNI*或Linu*操作系统中，所有的输入输出外部设备都被看作特殊文件便于统一管理。按存取的物理构造分类(详见后面章节)顺序〔连续〕文件：链接文件：索引文件：例：每个盘块大小为1KB，每个盘块号占4个字节，假设采用一级索引方式，则在一个索引块中可存放多少个盘号？假设采用两级索引，则最多可存放的盘块数为多少？允许的文件最大长度是多少？分析：两级索引：见索引图文件长度：共有N个盘块，每个盘块的大小M=N*M解：一级索引方式，盘块数=1KB/4B=256个两级索引，盘块数=256*256=64K个允许的文件最大长度=64K*1K=64MB文件目录的管理包括存储空间的有效利用快速搜索文件命名冲突文件共享文件的组成文件包括两局部文件体文件说明〔FCB文件控制块〕根本信息文件名文件物理位置：文件构造：指示文件的逻辑构造和物理构造。存取控制信息使用信息文件目录文件目录：一个文件的文件说明信息称为该文件的目录。分类：一级目录、二级目录和多级目录一级目录思想：把所有的文件都登记在一张目录表中，按文件名查找目录得到文件存放的地址。操作：建立一个新文件时就在文件目录中增加一个目录项；每当删去一个文件时就在文件目录中删去该文件的目录项。补充:文件完整性定义：是指文件的不失真性分类：物理上的完整性：损坏存储设备逻辑上的完整性：掉电保证文件完整性的措施：转储〔备份〕周期性的全量转储周期性的增量转储周期性全量转储固定的时间周期：如一周一次所有文件转存缺点由于是全量转储，因而需要消耗很多的系统时间。由于转储时间长而可能导致在转储过程中文件系统被迫停顿工作。周期性增量转储固定的时间周期：短周期，如一天一次发生变化局部为了确定哪些文件发生了改变，系统必须对文件进展跟踪，并标记那些更新了的文件，周期性地对做了标记的文件进展转储，转储后去除更新标记。第9章设备管理设备的类别设备管理的对象：外部设备按系统和用户分类系统设备，安装操作系统时就记载在系统中。例如显示器、键盘、鼠标器、光盘驱动器等。用户设备，通常由用户根据需要自行添加的。如打印机等。按输入输出传送方式分类块设备以块为单位进展数据传输。字符设备以字符为单位进展数据传输。按资源特点分类独占设备共享设备虚拟设备按设备使用特性分类存储设备用来存储信息的设备。如磁盘等。I/O设备用来进展输入输出处理的设备。如键盘、显示器等。设备控制器功能设备控制器与处理机的接口—信息存储及通信；设备控制器与设备的接口—连接设备；I/O逻辑—实现对设备的控制。接收处理机发出的I/O命令；对收到的命令进展译码；对收到的地址进展译码；根据所译出的命令对所选设备进展控制。通道是一个专管输入输出的硬件，又称I/O处理机。功能：执行CPU发出的I/O指令，完成I/O操作。与一般处理机的不同:通道的指令类型单一。通道能执行的命令主要局限于与I/O操作有关的指令；通道没有自己的存储器。通道所执行的通道程序是放在主机的内存中的，与CPU共享内存。数据传输控制方式：CPU与外设之间的数据传输。数据传输要解决的问题：由谁来控制数据的传输？传输过程出错如何处理？传输完毕如何通知CPU？如何提高CPU与外设的并行度？数据传输控制方式分类程序查询方式中断方式DMA方式通道方式。程序查询方式用指令及循环测试控制CPU与外设之间的数据传送。数据传输过程如以下图所示：优点：程序查询方式实现简单，也无需硬件支持缺点：CPU的利用率极低。CPU在绝大多数时间内都处于循环测试的忙等待状态。多台外设之间只能串行工作。一段时间内CPU只能与一台外设交换数据。适用于CPU执行速度较慢且外设较少的系统。中断控制方式中断控制方式的引入程序查询方式CPU利用率低，需要不断查询，无法实现与外设并行工作解决方法：与外设交换数据的过程中，CPU可以转进程调度，交换完毕时再进展处理—中断控制方式中断控制方式以字节为单位进展数据传输。数据传输过程：缺点花费CPU的处理时间数据存放器容量：一字节数据存放器满或空时将会产生中断请求信号，容量的关系使得中断频繁假设系统中各种外设都采用中断方式进展数据传送，中断次数急剧增加，导致CPU无法及时响应，出现数据丧失现象。DMA控制方式(DirectMemoryAccess直接存储器存取)的引入中断控制方式以字节为单位进展数据传输，假设数据量大则导致中断频繁发生，CPU因频繁处理中断而使效率无法提高。解决方法：交换过程无需CPU处理,外设与内存直接交换数据—DMA控制方式。特点块传送。适用于块设备。直接传送。内存与I/O设备间的数据传送在DMA控制器的控制之下完成，不需要CPU的任何中间干预，仅在传送数据块的开场和完毕时才需要CPU的干预。DMA控制方式与中断控制方式的区别中断控制方式在每个数据传输完成后中断CPU一次，DMA方式是所有数据传输完成后中断CPU。中断控制方式的数据传输是在中断处理时由CPU控制完成，DMA方式是在DMA控制器的控制下完成。通道控制方式通道控制方式的引入DMA方式对外设的管理和操作由CPU完成，外设种类多使得管理和控制复杂。解决方法：使用专门用于I/O操作的硬件设备—通道。通道：一个独立于CPU的专门实现I/O控制的处理机，它控制设备与内存直接进展数据交换。通道控制与DMA控制的比较一样：设备与内存交换数据时无CPU干预不同DMA：数据的传送方向、存放数据的内存地址以及数据块的长度由CPU控制通道："CPU不干预〞更完全。9.4缓冲技术缓冲技术目的用来解决CPU与外设之间以及设备与设备之间速度不匹配的问题。解决系统中I/O负荷的不均衡问题。系统有时会产生大量的数据需要I/O，有时又会很长时间没有I/O，造成I/O负荷的不均匀。有效减少I/O次数，从而提高I/O速度。由于设备与CPU之间的数据传输方式是中断方式，采用缓冲技术能够将一批数据集中在一次中断中完成。本应传输一个字符中断一次,但可将字符存于缓冲区,例如够100字符再中断一次。缓冲技术思想缓冲的类型缓冲区物理介质：内存缓冲技术类型单缓冲双缓冲多缓冲缓冲池双缓冲为输入、输出设备分配两个缓冲区输入数据输入设备：输入缓冲区1，1满时输入缓冲区2进程：取缓冲区1，1空时取缓冲区2；输出数据进程：数据写入缓冲区1，1满时写入2输出设备：取缓冲区1输出，1空时取2缓冲池缓冲池的组成三种根本缓冲区空缓冲区—空缓冲队列；装满输入数据的缓冲区—输入队