2012-12计算机操作系统期末总复习ppt课件.ppt

计算机操作系统计算机操作系统期末总复习期末总复习2012年12月操作操作系统系统基本概念基本概念处理机管理处理机管理设备管理设备管理作业管理作业管理用户接口用户接口存储管理存储管理文件管理文件管理操作系统定义操作系统定义OS的作用的作用OS特征特征OS的主要功能的主要功能OS分类分类OS结构设计结构设计多道程序设计多道程序设计进程基本概念进程基本概念进程同步互斥进程同步互斥进程间通信进程间通信进程调度进程调度死锁死锁I/O系统系统I/O控制方式控制方式缓冲技术缓冲技术I/O软件组成软件组成设备独立性设备独立性设备分配设备分配驱动程序驱动程序虚设备技术虚设备技术通道技术通道技术磁盘调度磁盘调度文件基本概念文件基本概念文件的逻辑结构文件的逻辑结构文件的物理结构文件的物理结构文件目录文件目录外存空间管理外存空间管理文件共享与保护文件共享与保护数据一致性数据一致性用户接口用户接口作业基本概念作业基本概念批处理系统作业管理批处理系统作业管理分时系统作业管理分时系统作业管理程序的装入与链接程序的装入与链接存储管理任务存储管理任务动态分区分配动态分区分配交换技术交换技术页式存储管理页式存储管理段式存储管理段式存储管理段页式段页式虚拟存储技术虚拟存储技术批处理操作系统批处理操作系统分时系统分时系统实时操作系统实时操作系统个人计算机操作系统个人计算机操作系统网络操作系统网络操作系统分布式操作系统分布式操作系统操作系统定义操作系统定义OS功能功能OS特征特征OS分类分类硬件运行环境硬件运行环境操作系统设计操作系统设计并发并发共享共享虚拟虚拟异步异步有效管理有效管理合理调度合理调度使用方便使用方便吞吐量吞吐量时间片时间片虚机器虚机器操作系统设计目标操作系统设计目标操作系统结构设计操作系统结构设计CPU状态状态系统堆栈系统堆栈中断技术中断技术时钟时钟通道通道地址映射地址映射存储保护存储保护处理机管理处理机管理存储管理存储管理设备管理设备管理文件管理文件管理用户接口用户接口操作系操作系统基本统基本概念概念第一章第一章 引论引论1 1、OSOS的定义与的定义与作用作用2 2、三种基本操作系统的基本原理和异同三种基本操作系统的基本原理和异同 多道程序设计多道程序设计、时间片轮转法时间片轮转法、及时性、及时性3 3、OSOS的特征和功能的特征和功能 4 4、用户接口用户接口 5 5、OSOS的结构设计的结构设计进程进程进程状态及转换进程状态及转换进程控制块进程控制块系统并发度系统并发度进程控制进程控制进程特性进程特性可重入程序可重入程序共享内存共享内存消息缓冲消息缓冲Send/Receive原语原语管道通信管道通信信箱信箱调度算法选择原则调度算法选择原则算法：算法：先进先出先进先出时间片轮转时间片轮转基于优先数基于优先数高响应比优先高响应比优先抢占式抢占式实时调度技术实时调度技术进程同步进程同步进程互斥进程互斥临界区临界区进程同步机制进程同步机制信号量信号量P、V操作操作生产者与消费者问题生产者与消费者问题读者写者问题读者写者问题哲学家进餐问题哲学家进餐问题死锁的有关结论死锁的有关结论产生死锁的产生死锁的必要条件必要条件死锁预防死锁预防死锁避免死锁避免死锁检测解除死锁检测解除资源分配图资源分配图多道程序设计多道程序设计进程基本概念进程基本概念进程同步互斥进程同步互斥进程间通信进程间通信进程调度进程调度死锁死锁顺序环境顺序环境并发环境并发环境与时间有关的错误与时间有关的错误不可在现性不可在现性进程进程管理管理第二章第二章 进程管理进程管理1、进程进程和和线程线程的概念的概念 n2、进程的基本状态及状态转换的原因进程的基本状态及状态转换的原因 3、PCB的作用的作用4、进程控制的原语操作、进程控制的原语操作5、进程、进程互斥、临界区互斥、临界区、进程同步的基本概念进程同步的基本概念、同步准则同步准则6、记录型记录型信号量信号量n7、信号量的应用信号量的应用 n8、经典进程同步问题；生产者与消费者问题经典进程同步问题；生产者与消费者问题9、进程间通信的原理和实现方法、进程间通信的原理和实现方法 信箱信箱第二章第二章 进程管理的典型问题进程管理的典型问题n进程的三种基本状态及其转变原因。进程的三种基本状态及其转变原因。n进程互斥、临界区进程互斥、临界区n三种经典同步问题及其变型三种经典同步问题及其变型n同步约束条件的分析，信号量的初值的设定同步约束条件的分析，信号量的初值的设定n单缓冲区的一个生产者一个消费者同步问题单缓冲区的一个生产者一个消费者同步问题n单缓冲区的一个生产者多个消费者同步问题单缓冲区的一个生产者多个消费者同步问题n多个生产者多个消费者多个缓冲区的同步问题多个生产者多个消费者多个缓冲区的同步问题第三章第三章 处理机调度与死锁处理机调度与死锁n1、处理机调度的、处理机调度的基本概念和种类基本概念和种类 2、选择调度算法的准则，周转时间，带权周转、选择调度算法的准则，周转时间，带权周转时间，响应时间时间，响应时间 n3、常见调度算法常见调度算法， 抢占，抢占，响应比响应比4、常见的两种实时调度算法常见的两种实时调度算法处理死锁的基本方法处理死锁的基本方法n5、死锁产生的原因，四个必要条件死锁产生的原因，四个必要条件6、死锁的预防死锁的预防7、利用银行家算法、利用银行家算法避免避免死锁死锁 8、死锁的检测与解除、死锁的检测与解除段式存储管理段式存储管理页式存储管理页式存储管理段页式存储管理段页式存储管理虚拟存储器虚拟存储器虚拟存储技术虚拟存储技术程序局部性原理程序局部性原理虚拟页式管理虚拟页式管理虚拟段式管理虚拟段式管理页面淘汰算法页面淘汰算法抖动（颠簸）抖动（颠簸）用户程序划分用户程序划分逻辑地址逻辑地址内存空间划分内存空间划分内存分配内存分配管理考虑管理考虑硬件支持硬件支持地址映射过程地址映射过程装入与链接装入与链接对换技术对换技术覆盖技术覆盖技术高速缓存高速缓存内存内存磁盘磁盘系统区系统区用户区用户区内存管理分配回收内存管理分配回收存储共享存储共享存储保护存储保护内存扩充内存扩充地址映射地址映射存储体系存储体系存储管理任务存储管理任务存储管理方案存储管理方案虚拟存储管理虚拟存储管理其他其他存储存储管理管理第四章第四章 存储管理的重点、难点存储管理的重点、难点n重定位的基本概念重定位的基本概念：为什么要引入：为什么要引入n如何提高内存利用率如何提高内存利用率：离散分配、对换机制、动态链离散分配、对换机制、动态链接、虚拟存储器、存储器共享接、虚拟存储器、存储器共享n动态分区分配方式动态分区分配方式：分配、回收算法：分配、回收算法n基本分页存储管理方式基本分页存储管理方式：为什么引入；：为什么引入；地址变换机构地址变换机构和过程和过程（含具有快表的情况）（含具有快表的情况）n基本分段存储管理方式：为什么引入；地址变换机构基本分段存储管理方式：为什么引入；地址变换机构和过程（含具有快表的情况）；信息的共享和保护和过程（含具有快表的情况）；信息的共享和保护n虚拟存储器虚拟存储器的基本概念：为什么要引入；的基本概念：为什么要引入；特征特征；实现；实现虚拟存储的关键技术虚拟存储的关键技术n请求分页系统的基本原理：请求分页系统的基本原理：页表机制页表机制；地址变换过程地址变换过程；页面置换算法页面置换算法第四章的典型问题第四章的典型问题n存储器管理的基本任务存储器管理的基本任务n动态重定位的概念动态重定位的概念、实现方式，什么情况下需要重定位、实现方式，什么情况下需要重定位n比较连续分配与离散分配比较连续分配与离散分配n基于空闲分区链的内存分配与回收算法的应用实例：基于空闲分区链的内存分配与回收算法的应用实例：首次首次适应法，循环首次适应法，最佳适应法适应法，循环首次适应法，最佳适应法n在某分页系统中，给定内存容量和物理块大小，计算物理在某分页系统中，给定内存容量和物理块大小，计算物理块的数量；对给定的进程页表，块的数量；对给定的进程页表，将给定的逻辑地址，计算将给定的逻辑地址，计算出其对应的物理地址并画出地址变换流程图出其对应的物理地址并画出地址变换流程图。n在某分段系统中对给定的进程段表，将给定的逻辑地址，在某分段系统中对给定的进程段表，将给定的逻辑地址，计算出其对应的物理地址并画出地址变换流程图计算出其对应的物理地址并画出地址变换流程图。n请求分页系统过程的各种问题，并用流程图的方式表示地请求分页系统过程的各种问题，并用流程图的方式表示地址变换过程址变换过程n对给定的问题，按各种对给定的问题，按各种页面置换算法，写页面调入过程，页面置换算法，写页面调入过程，计算和分析缺页率，并对多种算法的性能作比较分析计算和分析缺页率，并对多种算法的性能作比较分析设备管理重要性设备管理重要性设备独立性设备独立性设备分类设备分类设备管理任务设备管理任务设备管理功能设备管理功能用户进程用户进程与设备无关软件与设备无关软件设备驱动程序设备驱动程序中断处理程序中断处理程序SPOOLing技术技术共享打印机共享打印机设备管理设备管理设备分配回收设备分配回收独占设备分配独占设备分配共享设备分配共享设备分配 基本概念基本概念I/O软件组成软件组成缓冲技术缓冲技术设备处理设备处理虚设备技术虚设备技术设备驱动程序设备驱动程序设备设备管理管理磁盘访问时间磁盘访问时间磁盘调度磁盘调度l先来先服务先来先服务l最短寻道时间优先最短寻道时间优先l扫描（电梯算法）扫描（电梯算法）lCSCAN磁盘存储管理磁盘存储管理第五章设备管理的重点、难第五章设备管理的重点、难点点I/O I/O 控制方式：四种控制方式：四种I/O I/O 方式的基本原理方式的基本原理；四种；四种I/O I/O 方式由方式由低到高效的演变低到高效的演变缓冲管理缓冲管理n缓冲的概念，为什么引入缓冲缓冲的概念，为什么引入缓冲n单缓冲如何提高单缓冲如何提高I/O I/O 速度，它存在哪些不足，双缓冲、循速度，它存在哪些不足，双缓冲、循环缓冲又如何提高环缓冲又如何提高CPU CPU 与与I/O I/O 设备的并行性设备的并行性n缓冲池是为了解决什么问题而引入，缓冲池是为了解决什么问题而引入，引入缓冲池后系统将引入缓冲池后系统将如何处理如何处理I/O I/O 设备和设备和CPU CPU 间的数据输送间的数据输送n缓冲池的工作方式及缓冲池的工作方式及GetbufGetbuf和和PutbufPutbuf过程过程设备独立性设备独立性n什么是什么是设备独立性设备独立性n如何实现设备独立性如何实现设备独立性设备驱动程序设备驱动程序, , 纯代码纯代码第五章设备管理的重点、难点第五章设备管理的重点、难点虚拟设备和虚拟设备和SPOOLingSPOOLing 技术技术n什么是虚拟设备什么是虚拟设备n什么是什么是SPOOLingSPOOLing技术，技术，SPOOLingSPOOLing系统的组成系统的组成n如何利用如何利用SPOOLingSPOOLing技术实现共享打印机技术实现共享打印机磁盘调度磁盘调度n磁盘调度的磁盘调度的目标目标n磁盘访问时间磁盘访问时间的计算的计算nFCFSFCFS、SSTFSSTF、SCANSCAN、CSCAN CSCAN 等算法的应用等算法的应用及这些调度算法及这些调度算法的演变过程，分别解决了哪些问题的演变过程，分别解决了哪些问题；各算法的性能比较；各算法的性能比较第五章设备管理的第五章设备管理的典型问题典型问题n各种各种I/O I/O 控制方式的比较控制方式的比较n为什么引入缓冲区为什么引入缓冲区n缓冲如何提高缓冲如何提高I/O I/O 速度速度n为什么引入为什么引入设备独立性设备独立性，如何实现，如何实现n什么是什么是虚拟设备虚拟设备，实现虚拟设备的关键技术，实现虚拟设备的关键技术nSPOOLingSPOOLing技术技术的组成，如何利用的组成，如何利用SPOOLingSPOOLing 技术实现共享打技术实现共享打印机印机n设备处理程序的功能和处理过程设备处理程序的功能和处理过程n对各种对各种磁盘调度算法磁盘调度算法，计算访问次序和平均寻道时间，性，计算访问次序和平均寻道时间，性能能n磁盘访问时间的组成和计算磁盘访问时间的组成和计算文件控制块文件控制块文件目录文件目录目录文件目录文件目录项目录项树型目录结构树型目录结构目录项分解法目录项分解法目录检索目录检索文件文件文件系统文件系统文件分类文件分类文件管理功能文件管理功能文件逻辑结构文件逻辑结构文件物理结构文件物理结构文件存取方式文件存取方式外存空间管理外存空间管理主要数据结构主要数据结构文件系统使用文件系统使用文件系统安全、保护、保文件系统安全、保护、保密、可靠性、一致性密、可靠性、一致性系统打开文件表系统打开文件表用户打开文件表用户打开文件表物理块物理块磁盘结构磁盘结构磁带磁带文件目录文件目录文件基本概念文件基本概念文件系统实现文件系统实现存储介质存储介质创建、打开、读写、关闭、删创建、打开、读写、关闭、删除、拷贝、重命名除、拷贝、重命名文件存取控制文件存取控制 文件文件 管理管理第六章文件管理的重点、难第六章文件管理的重点、难点点文件的逻辑结构：顺序文件、索引文件和索引顺序文件文件的逻辑结构：顺序文件、索引文件和索引顺序文件n原理和特征原理和特征n组织方式、访问方法及各种文件形式的比较组织方式、访问方法及各种文件形式的比较外存分配方式：连续分配、外存分配方式：连续分配、链接分配和索引分配原理链接分配和索引分配原理、优缺、优缺点点n显示链接显示链接FATFAT、混合索引分配、混合索引分配目录管理：目录管理的要求目录管理：目录管理的要求n文件控制块（文件控制块（FCBFCB）n索引结点索引结点n目录结构目录结构：单级、两级和多级：单级、两级和多级文件磁盘空间管理文件磁盘空间管理n空闲表法和空闲链法空闲表法和空闲链法n位示图法位示图法：分配和回收的具体计算：分配和回收的具体计算n成组链接法成组链接法第六章第六章 文件管理的典型问题文件管理的典型问题n画出链接分配方式的链接情况和画出链接分配方式的链接情况和FAT FAT 的链接情况、的链接情况、FATFAT长度计长度计算等。算等。n混合索引分配的的寻址方式、地址转换的计算和索引结点的混合索引分配的的寻址方式、地址转换的计算和索引结点的地址映射图地址映射图n对给定的对给定的位示图位示图和文件的分配和回收需求，具体写出分配过和文件的分配和回收需求，具体写出分配过程和回收过程。程和回收过程。nUnixUnix系统的成组链接法系统的成组链接法n目录管理的要求目录管理的要求；目前广泛采用的目录结构及其优点；目前广泛采用的目录结构及其优点n说明在树形目录结构中线性检索的过程，并画出相应的流程说明在树形目录结构中线性检索的过程，并画出相应的流程图图n文件的共享文件的共享第七章第七章 操作系统接口操作系统接口n联机命令接口n联机命令联机命令n终端处理程序终端处理程序n命令解释程序命令解释程序n程序接口n系统调用系统调用与一般过程调用的区别n中断与陷入n图形用户接口选择、填空、判断题选择、填空、判断题主要考查操作系统课程的基本概念。以进程的基本概念为主，兼顾其它各章内容。特别是 Ch2,ch3,ch4三章名词解释名词解释1.多道程序系统 11.临界资源 2.进程 12.死锁3.管道 13.最小物理块数4.进程的静态优先权 14.脱机输入/输出5.低级调度 15.并发性6.重定位 16.进程控制块PCB7.地址变换 17.碎片（内、外）8.虚拟设备 18.纯代码（可重入代码）9.进程高级通信（低级通信）19.设备无关性10.文件控制块（FCB） 20.操作系统简答题简答题11.一个现代操作系统有哪些基本特征。2.进程有哪三个基本状态，画图说明引起进程状态切换的原因。3.简述进程同步机制遵循的四条准则。4.何谓临界资源和临界区? 5.何谓内存分配中的内碎片？ 6.简述分页存储管理系统的请求调页策略。7.简述段式管理和页式管理的特点。8.试述缺页中断与一般中断的主要区别。9.什么是设备的独立性？10.最基本的磁盘调度算法有哪三种？每种算法优先考虑的问题是什么？ 11.文件管理中对文件目录管理的要求有哪些？ 12.进行文件的“打开”操作时，为什么需要把进行该操作的用户的用户名作为操作的一个参数？ 13.试述文件的逻辑结构。14.试述文件存储空间管理中的位示图法。15.用户与OS之间的接口有哪些方式？它们在什么情况下使用的？简答题简答题21.操作系统的基本功能有哪些？ 2.简述进程的基本特征。3.简述产生进程死锁的必要条件，以及预防死锁的方法。4.何谓虚拟存储器? 5.磁盘文件的目录表通常包含哪些内容 ？ 6.简述文件系统中，文件按不同分类方法可以分为哪些种类的文件。7.简述资源信号量的物理含义。8.试述分时操作系统的的特征。9.设备管理中通常采用哪些数据结构。10.进程实体的组成包含哪三部分？ 11.进程调度通常采取哪两种方式 ？ 12.操作系统为用户提供了哪两类接口？ 13.MSDOS和UNIX系统的命令解释程序分别是什么？14.试述请求分页存储管理FIFO页面置换算法中的Belady现象。15.试述操作系统中设备管理的SPOOLING技术？计算题计算题1、作业（进程）的周转时间（平均周转时间、平均等待时间、平均带权周转时间 等）。 先来先服务，短作业/进程优先，时间片轮转，优先权，高响应比优先调度算法，响应比的计算2、动态分区分配的空闲分区表和内存分配图。 首次适应，循环首次适应，最佳适应，最坏适应等算法3、内存分页管理中，地址结构的计算。4、内存分页、分段管理中，将用户地址空间中的逻辑地址变换为内存空间中的物理地址。 页表（段表），地址变换机构计算题计算题5、请求分页技术中的页面置换算法，描述内存映象图，并计算出缺页率。 最佳置换OPT、FIFO、LRU等算法6、磁道访问的调度图以及计算平均寻道长度 FCFS、SSTF、SCAN、CSCAN算法7、用位示图管理磁盘，计算位示图的组织，实现盘块的分配和回收。8、画出文件链接分配方式的链接情况和FAT 的链接情况、FAT长度计算等9、外存空闲空间的成组链接法的分组计算和画成组链接图。设计题设计题利用信号量进行进程的同步、互斥的程序设计设计题设计题吃水果的同步关系吃水果的同步关系 有个盘子，可以容纳两个水果，每次只能放入或取出一个水果，爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃橘子，两个女儿专等吃苹果。试用信号量的P，V操作实现此过程，并给出信号量和初始值。分析：盘子是临界资源，而爸爸和妈妈可以同时向其中放水果，因此要设置一个互斥信号量mutex盘子最多容纳两个水果，因此，要对放入盘子的水果进行计数，就是要设置一个信号量empty,初值为2。由于盘子可以放两个水果，即当盘子里有一个水果时，存在即可以放也可以取的情况，因此，除了对放水果进行互斥外，对取水果也要互斥。此外，爸爸和女儿，妈妈和儿子之间存在同步关系，要设置信号量apple和orange实现同步，初值都是0。 begin var mutex=1,empty =2 :semaphore; var apple = 0,orange = 0:semaphore; cobegin process father begin repeat p(empty ); p(mutex); 放入苹果；放入苹果； v(mutex); v(apple); until false end process mother begin repeat p(empty ); p(mutex); 放入橘子；放入橘子； v(mutex); v(orange); until false end process son-i(i=1,2) begin repeat p(orange); p(mutex); 取橘子；取橘子； v(mutex); v(empty); until false end process daughter-i(i=1,2) begin repeat p(apple); p(mutex); 取苹果；取苹果； v(mutex); v(empty); until false end coendend 注：要注意盘子的容量，当盘子的容量大于时，不仅要考虑注：要注意盘子的容量，当盘子的容量大于时，不仅要考虑同步，还要考虑互斥。同步，还要考虑互斥。变形后：变形后：一个盘子，可以放一个水果，一个盘子，可以放一个水果，爸爸放苹果，妈妈放香蕉，一个儿子专等吃香蕉，一个女儿专爸爸放苹果，妈妈放香蕉，一个儿子专等吃香蕉，一个女儿专等吃苹果。等吃苹果。排队等候服务的同步关系排队等候服务的同步关系 税务局缴税大厅有n个柜员,每个纳税人进入缴税大厅后先取一个号,并且等着叫号,当一个柜员空闲后，就叫下一个号。试用信号量的P，V操作实现此过程，并给出信号量和初始值。分析:将纳税人号码排成一个队列,纳税人进入缴税大厅领取号码后,将号码由队尾插入;柜员空闲时,从队首取得纳税人号码,并且为这个纳税人服务,由于队列为若干进程共享,所以需要互斥。柜员空闲时,若有纳税人,就叫下一个纳税人为之服务。因此,需要设置一个信号量来记录等待服务的纳税人数。int mutex=1, taxpayer_count=0: semaphore; Taxpayer() while(1) 取号码；取号码； P（mutex）；）； 进入队列；进入队列； V（mutex）；）； V（taxpayer_count） Servers(i=1.n) while(1) P(taxpayer_count); P（mutex）；）； 从队列中取下一个号码；从队列中取下一个号码； V（mutex）；）； 为该号码持有者服务；为该号码持有者服务； 已知某分页系统，主存容量为已知某分页系统，主存容量为64K64K，页面大小为，页面大小为1K1K，对一个，对一个4 4页大的作业，其页大的作业，其0 0、1 1、2 2、3 3页分别页分别被分配到主存的被分配到主存的2 2、4 4、6 6、7 7块中。块中。 （1 1）将十进制的逻辑地址）将十进制的逻辑地址10231023、25002500、35003500、45004500转换成物理地址？转换成物理地址？ （2 2）以十进制的逻辑地址）以十进制的逻辑地址10231023为例画出为例画出地址变地址变换过程图换过程图？计算题例子计算题例子1 答答：逻辑地址逻辑地址10231023：1023/1K1023/1K，得页号为，得页号为0 0，页内地址，页内地址为为10231023，查页表找到对应的物理块号为，查页表找到对应的物理块号为2 2，故物理地，故物理地址为址为2 21K+1023=30711K+1023=3071 逻辑地址逻辑地址25002500：2500/1K2500/1K，得页号为，得页号为2 2，页内地址，页内地址为为452452，查页表找到对应的物理块号为，查页表找到对应的物理块号为6 6，故物理地，故物理地址为址为6 61K+452=65961K+452=6596 逻辑地址逻辑地址35003500：3500/1K3500/1K，得页号为，得页号为3 3，页内地址，页内地址为为428428，查页表找到对应的物理块号为，查页表找到对应的物理块号为7 7，故物理地，故物理地址为址为7 71K+428=75961K+428=7596 逻辑地址逻辑地址45004500：4500/1K4500/1K，得页号为，得页号为4 4，页内地址，页内地址为为404404，因页号不小于页表长度，故产生，因页号不小于页表长度，故产生越界中断越界中断。 （2）地址变换过程图地址变换过程图计算题例子计算题例子2 假定系统为某进程分配了假定系统为某进程分配了3 3个物理块，进程运个物理块，进程运行时的页面走向为行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,51,2,3,4,1,2,5,1,2,3,4,5开始时开始时3 3个物理块均为空，给出下列置换算法时页个物理块均为空，给出下列置换算法时页面置换情况面置换情况( (画出置换图画出置换图内存映象图内存映象图 ) )，并计，并计算出该算法的缺页率？算出该算法的缺页率？（1 1）先进先出淘汰算法（）先进先出淘汰算法（FIFOFIFO）；）；（2 2）最近最久未使用淘汰算法（）最近最久未使用淘汰算法（LRULRU）。）。（1）采用）采用FIFC置换算法：缺页率置换算法：缺页率=9/12=0.75 。置换图如下：。置换图如下： 页面走向页面走向123412512345物理块物理块1111444555555物理块物理块222211111333物理块物理块33332222244是否缺页是否缺页缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺（2）采用）采用LRU置换算法：缺页率置换算法：缺页率=10/12=0.83 。置换图如下：。置换图如下： 页面走向页面走向123412512345物理块物理块11114445333物理块物理块2222111144物理块物理块333322225是否缺页是否缺页缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺一个磁盘系统，平均寻道时间为一个磁盘系统，平均寻道时间为12ms，转速为，转速为10000转转/分，每个磁道有分，每个磁道有18个扇区，每个扇区个扇区，每个扇区512个字节。个字节。请问要读取一个扇区所花的时间是多少？请问要读取一个扇区所花的时间是多少？解：解： TA = TS + TR + TT= TS + 1/2r + b/rN TS = 12msTR = 1/2r = 60100000.5 = 3msTT = b/rN = (51260)(1851210000)= 0.33msTA = TS + TR + TT =12 + 3 + 0.33 = 15.33ms读取一个扇区所花的时间是读取一个扇区所花的时间是15.33ms。 计算题例子计算题例子3计算题例子计算题例子4设某磁盘有设某磁盘有200个柱面，编号为个柱面，编号为0，1，2，199，磁头刚从，磁头刚从140磁道移到磁道移到143磁道完成了读磁道完成了读写。若某时刻有写。若某时刻有9个磁盘请求分别对如下各磁道个磁盘请求分别对如下各磁道进行读写：进行读写： 86，147，91，177，94，150，102，175，130 试分别求试分别求SSTF及及SCAN磁盘调度算法响应请磁盘调度算法响应请求的次序求的次序(调度图调度图)、磁头移动的总距离及平均、磁头移动的总距离及平均寻道长度寻道长度 。（1）采用SSTF算法调度时，磁头（磁盘存取移动臂）移动的顺序为：143147150130102949186175177 磁头移动的总距离为：（147-143）+（177-175）=162（柱面） 平均寻道长度=162/9=18 （柱面）（2）采用SCAN算法调度时，磁头（磁盘存取移动臂）移动的顺序为：143147150175177130102949186 磁头移动的总距离为：（147-143）+（91-86）=125（柱面） 平均寻道长度=125/9=13.89（柱面）解：解：计算题例子计算题例子5假定盘块的大小为1KB,硬盘的大小为500MB,采用显示链接分配方式时,其FAT需占用多少存储空间（FAT表项占2.5个字节）?如果文件A占用硬盘的11, 12 , 16, 14四个盘块,试画出文件A中各盘块在FAT表中的链接情况。解：解：此时硬盘共有500M/1K=500K个盘块，FAT表项共有500K 2.5B=1250KBFATFCB计算题例子计算题例子6存放在某个磁盘上的文件系统，对于采用混合索引分配存放在某个磁盘上的文件系统，对于采用混合索引分配方式，其方式，其FCBFCB中共有中共有1313项地址项，第项地址项，第0 09 9个地址项为个地址项为直接地址，第直接地址，第1010个地址项为一次间接地址，第个地址项为一次间接地址，第1111个地个地址项为二次间接地址，第址项为二次间接地址，第1212个地址项为三次间接地址。个地址项为三次间接地址。如果每个盘块的大小为如果每个盘块的大小为512512字节，若盘块号需要字节，若盘块号需要3 3个字个字节来描述，而每个盘块最多存放节来描述，而每个盘块最多存放170170个盘块地址：个盘块地址：(1) (1) 该文件系统允许的最大长度是多少？该文件系统允许的最大长度是多少？(2) (2) 将文件的字节偏移量将文件的字节偏移量50005000、1500015000转换为物理块号转换为物理块号和块内偏移量。和块内偏移量。(3) (3) 假设某文件的索引结点已在内存中，但其他信息均假设某文件的索引结点已在内存中，但其他信息均在外存，为了访问该文件中某个位置的内容，最多需在外存，为了访问该文件中某个位置的内容，最多需要几次访问磁盘？要几次访问磁盘？图 混合索引方式 modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata混合索引分配方式混合索引分配方式 （1 1）文件的最大长度为：）文件的最大长度为： 10+170+17010+170+1702 2+170+1703 3=4942080=4942080块块=2471040KB=2471040KB（2 2）5000/5125000/512得商得商9 9，余数为，余数为392392。即逻辑块号为。即逻辑块号为9 9，块内偏，块内偏移为移为392392。故可直接从该文件的。故可直接从该文件的FCBFCB的第的第9 9个地址处得到物理个地址处得到物理盘块号，块内偏移为盘块号，块内偏移为392392。 15000/51215000/512得商为得商为2929，余数为，余数为152152。即逻辑块号为。即逻辑块号为2929，块，块内偏移为内偏移为152152。由于。由于102910+170,102910+170,而而29-10-1929-10-19，故可从，故可从FCBFCB的第的第1010个地址项，即一次间址项中得到一次间址块；并从一个地址项，即一次间址项中得到一次间址块；并从一次间址块的次间址块的1919项中获得对应的物理盘块号，块内偏移为项中获得对应的物理盘块号，块内偏移为152152。(3) (3) 由于文件的索引结点已在内存，为了访问文件中的某个由于文件的索引结点已在内存，为了访问文件中的某个位置的内容，最少需要位置的内容，最少需要1 1次访问磁盘（即通过直接地址直接次访问磁盘（即通过直接地址直接读文件盘块），最多需要读文件盘块），最多需要4 4次访问磁盘（第一次是读三次间次访问磁盘（第一次是读三次间址块，第二次读二次间址块，第三次读一次间址块，第四次址块，第二次读二次间址块，第三次读一次间址块，第四次是读文件盘块）是读文件盘块）计算题例子计算题例子7有一个计算机系统利用下图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。（1）现要为一文件分配两盘块，试具体说明分配过程。（2）若要释放磁盘的第300块，应如何处理？ 解：解：（1）分配过程 线性检索位示图得：i1=2，j1=2； i2=3，j2=6。 计算空闲盘块号： B1=i116+j1+1=216+2+1=35 B2=i216+j2+1=316+6+1=55 修改位示图： 令map2，2=map3，6=1，并将对应块35，55分配出去。 解：解：（2）释放过程 计算出第300块所对应的位示图中的行号i和列号j i=（300-1）/16=18 j= （300-1）% 16=11 修改位示图： 令map18，11=0 #计算题例子计算题例子8问题：问题：有一磁盘组共有有一磁盘组共有1515个盘面，每个盘面有个盘面，每个盘面有100100个磁道，个磁道，每个磁道有每个磁道有8 8个扇区。假设分配以扇区为单位（块），若个扇区。假设分配以扇区为单位（块），若使用位示图管理磁盘，试问：使用位示图管理磁盘，试问：（1 1）位示图需要占多少空间（字节）？）位示图需要占多少空间（字节）？（2 2）若空白文件目录的每个表目占用）若空白文件目录的每个表目占用5B5B，问什么时候空，问什么时候空白文件目录大于位示图？白文件目录大于位示图？解解：（：（1 1）由题知：总的扇区数是）由题知：总的扇区数是8 8* *100100* *15=1200015=12000，使用，使用位示图需要的位是位示图需要的位是12000bit=1500B12000bit=1500B。 （2 2）空白文件目录的每个表目占用）空白文件目录的每个表目占用5B5B，位示图需要，位示图需要1500B1500B，1500B1500B可存放的表目数是可存放的表目数是1500/5=3001500/5=300，故当空白文件目录的每个表目大于故当空白文件目录的每个表目大于300300时，空白文件目录时，空白文件目录大于位示图。大于位示图。例子例子9用户与用户与OSOS之间的接口有哪些方式？它们在什么情况下使用的？之间的接口有哪些方式？它们在什么情况下使用的？解答：解答：用户与操作系统之间的接口有以下方式：命令接口、用户与操作系统之间的接口有以下方式：命令接口、程序接口、图形用户接口。程序接口、图形用户接口。命令接口是用户在终端输入命令与系统交互或者是用户通命令接口是用户在终端输入命令与系统交互或者是用户通过提交作业控制说明书来控制系统运行。这种方式要求用过提交作业控制说明书来控制系统运行。这种方式要求用户记忆所以的命令，有较强的英语应用能力。户记忆所以的命令，有较强的英语应用能力。程序接口是通过系统调用来实现的，这种接口主要提供给程序接口是通过系统调用来实现的，这种接口主要提供给程序员使用，在程序员使用，在OSOS的外层软件或用户程序中，凡是与资源的外层软件或用户程序中，凡是与资源有关的操作都必须通过该接口向操作系统提出服务请求，有关的操作都必须通过该接口向操作系统提出服务请求，并由并由OSOS代为完成。代为完成。图形化用户接口直观、方便、易学，更适合于普通用户使图形化用户接口直观、方便、易学，更适合于普通用户使用。用。积极复习，积极复习，善用资料，善用资料，诚信考试，诚信考试，愉快寒假！愉快寒假！