《计算机统考重难点班讲义(操作系统)-第三讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义(操作系统)-第三讲.ppt（48页珍藏版）》请在三一办公上搜索。
1、操作系统重难点串讲,讲师：翔高教育一级培训师地点：上海,第5章 设备管理,重难点导航,DMA控制方式的流程，DMA方式和通道方式以及中断方式的区别引入缓冲的目的快速缓存和缓冲区的区别SPOOLing技术的概念、目的、以及实现过程磁盘访问的时间常用磁盘调度算法的应用,3,I/O控制方式,程序I/O方式,在程序I/O方式中，由于CPU的高速性和I/O设备的低速性，致使CPU的绝大部分时间都处于等待I/O设备完成数据I/O的循环测试中，造成对CPU的极大浪费。在该方式中，CPU之所以要不断地测试I/O设备的状态，就是因为在CPU中无中断机构，使I/O设备无法向CPU报告它已完成了一个字符的输入操作。
2、,中断驱动I/O控制方式,在I/O设备输入每个数据的过程中，由于无须CPU干预，因而可使CPU与I/O设备并行工作。仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理。可见，这样可使CPU和I/O设备都处于忙碌状态，从而提高了整个系统的资源利用率及吞吐量。例如，从终端输入一个字符的时间约为100 ms，而将字符送入终端缓冲区的时间小于 0.1 ms。若采用程序I/O方式，CPU约有 99.9 ms的时间处于忙等待中。采用中断驱动方式后，CPU可利用这 99.9 ms的时间去做其它事情，而仅用 0.1 ms的时间来处理由控制器发来的中断请求。可见，中断驱动方式可以成百倍地提高CPU的利用
3、率。,直接存储器访问DMA I/O控制方式,DMA(Direct Memory Access)控制方式的引入,该方式的特点是：数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块；所传送的数据是从设备直接送入内存的，或者相反；仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。可见，DMA方式较之中断驱动方式，又是成百倍地减少了CPU对I/O的干预，进一步提高了CPU与I/O设备的并行操作程度。,I/O通道控制方式,I/O通道控制方式的引入,I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(
4、或写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。同时，又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。例如，当CPU要完成一组相关的读(或写)操作及有关控制时，只需向I/O通道发送一条I/O指令，以给出其所要执行的通道程序的首址和要访问的I/O设备，通道接到该指令后，通过执行通道程序便可完成CPU指定的I/O任务。,缓 冲 管 理,缓冲的引入,缓和CPU与I/O设备间速度不匹配的矛盾。(2)减少对CPU的中断频率，放宽对CPU中断响应时间的限制。(3)提高CPU和I/O设备之间的并行性。,SPOOLing技术,为了缓和CP
5、U的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术。该技术是利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上；或者相反。事实上，当系统中引入了多道程序技术后，完全可以利用其中的一道程序，来模拟脱机输入时的外围控制机功能，把低速I/O设备上的数据传送到高速磁盘上；再用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上。这样，便可在主机的直接控制下，实现脱机输入、输出功能。此时的外围操作与CPU对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作称为SPOOLing(Simultaneaus Periphernal Operatin
6、g On-Line)，或称为假脱机操作。,SPOOLing系统的组成,图 5-19 SPOOLing系统的组成,共享打印机,共享打印机技术已被广泛地用于多用户系统和局域网络中。当用户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事：由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中；输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。,SPOOLing系统的特点,提高了I/O的速度。(2)将独占设备改造为共享设备。(3)实现了虚拟设备功能。,磁盘访问时间,
7、1)寻道时间Ts 这是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即Ts=mn+s其中，m是一常数，与磁盘驱动器的速度有关，对一般磁盘，m=0.2；对高速磁盘，m0.1,磁臂的启动时间约为2 ms。这样，对一般的温盘，其寻道时间将随寻道距离的增加而增大，大体上是530 ms。,2)旋转延迟时间T 这是指定扇区移动到磁头下面所经历的时间。对于硬盘，典型的旋转速度大多为5400 r/min，每转需时11.1 ms，平均旋转延迟时间T为5.55 ms；对于软盘，其旋转速度为300 r/min或600 r/min，这样，平均T为50100
8、ms。,3)传输时间Tt 这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt的大小与每次所读/写的字节数b和旋转速度有关：,其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时，Tt与T相同，因此，可将访问时间Ta表示为：,磁盘调度,1.先来先服务FCFS(First-Come,First Served),最短寻道时间优先SSTF(Shortest Seek Time First),图 5-24 SSTF调度算法,2)SCAN算法,图 5-25 SCAN调度算法示例,经典例题解析,【例1】下面关于设备属性的论述中，正确的是_。【浙江大学200
9、4】A字符设备的基本特征是可寻址到字节，即能指定输入的源地址或输出的目标地址B共享设备必须是可寻址的和可随机访问的设备C.共享设备是指同一时间内允许多个进程同时访问的设备D在分配共享设备和独占设备时都可能引起进程死锁解析：可寻址是块设备的基本特征，故A不对。共享设备是指一段时间内允许多个进程同时访问的设备，在同一时间内，即对某一时刻共享设备仍然允许一个进程访问，故C不正确。分配共享设备是不会引起进程死锁的。故D不正确。答案选B,19,【例2】某移动臂磁盘的柱面由外向里从0开始顺序编号，假定当前磁头停在100号柱面而且移动方向是向外的，现有一个请求队列在等待访问磁盘，访问的柱面号分别为190、1
10、0、160、90、100、125、30、20、140和25。请给出分别采用最短寻找时间优先和电梯调度算法处理上述请求的次序，并分别计算出它们的平均寻道长度。【四川大学2005】解析：处理上述请求的次序以及平均寻道时间如下表示：采用最短寻找时间优先算法时处理各请求的次序为：90、80、125、140、160、190、30、25、20、10平均寻道时间为：L(0090)+(9080)+(12580)+(140125)+(160140)+(190160)+(9030)+(3025)十(2520)+(2010)1021,20,采用电梯调度算法时的次序为：90、80、30、25、20、10、125、14
11、0、160、190平均寻道时间为：(10+10十50+5+5+10+115十15+20+30)1027,21,第6章 文件管理,22,重难点导航,文件的打开操作和关闭操作记录式文件和流式文件的区别连续分配、链接分配及索引分配访问磁盘的次数混合索引方式访问的磁盘容量和读取所需的磁盘I/O次数树形目录结构的文件共享,23,2.文件的“打开”和“关闭”操作,所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请求。系统
12、这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索。这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉。,文件的逻辑结构,对于任何一个文件，都存在着以下两种形式的结构：（1）文件的逻辑结构(File Logical Structure)。(2)文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。,外存分配方式,连续分配,图 6-7 磁盘空间的连续分配,连续分配的主要优缺点,连续分配的主要优点如下：顺序访问
13、容易。(2)顺序访问速度快。,连续分配的主要缺点如下：要求有连续的存储空间。(2)必须事先知道文件的长度。,链接分配,隐式链接,图 6-8 磁盘空间的链接式分配,索引分配,单级索引分配 链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即：(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。,图 6-11 索引分配方式,2.多级索引分配,图 6-12 两级索引分配,图 6-13 混合索引方式,(1)直接地址。为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)i
14、addr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据的盘块的盘块号。假如每个盘块的大小为 4 KB，当文件不大于40 KB时，便可直接从索引结点中读出该文件的全部盘块号。,(2)一次间接地址。对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1K个盘块号，因而允许文件长达4 MB。,(3)多次间接地址。当文件长度大于4 MB+40 KB时(一次间址与10个直接地址项)，系统还须采用二次间址
15、分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4 GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4 TB。,目 录 管 理,对目录管理的要求如下：实现“按名存取”。(2)提高对目录的检索速度。(3)文件共享。(4)允许文件重名。,文件控制块和索引结点,文件控制块 基本信息类 文件名；文件物理位置；文件逻辑结构；文件的物理结构(2)存取控制信息类(3)使用信息类,图 6-14 MS-DOS的文件控制块,目录结构,1.单级目录结构,
16、图 6-16 单级目录,单级目录的优点是简单且能实现目录管理的基本功能按名存取，但却存在下述一些缺点：(1)查找速度慢(2)不允许重名(3)不便于实现文件共享,两级目录,图 6-17 两级目录结构,具有以下优点：提高了检索目录的速度(2)在不同的用户目录中，可以使用相同的文件名。(3)不同用户还可使用不同的文件名来访问系统中的同一个共享文件,3.多级目录结构,(1)目录结构,图 6-18 多级目录结构,(2)路径名。在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。在该路径上从树的根(即主目录)开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名(
17、path name)。系统中的每一个文件都有惟一的路径名。例如，在图 6-18 中用户B为访问文件J，应使用其路径名/B/F/J来访问。,(3)当前目录(Current Directory)。当一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶(数据文件)为止的、包括各中间结点(目录)名的全路径名。这是相当麻烦的事，同时由于一个进程运行时所访问的文件，大多仅局限于某个范围，因而非常不便。基于这一点，可为每个进程设置一个“当前目录”，又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行。此时各文件所使用的路径名，只需从当前目录开始，逐级经过中间的目录文件，最后到达要
18、访问的数据文件。把这一路径上的全部目录文件名与数据文件名用“/”连接形成路径名，如用户B的当前目录是F，则此时文件J的相对路径名仅是J本身。这样，把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name)；而把从树根开始的路径名称为绝对路径名(absolute path name)。,利用符号链实现文件共享,在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共享文件删除后，
19、其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。,经典例题分析,【例1】文件系统的主要目的是()。【电子科大 2008】A实现对文件的按名存取 B实现虚拟存储C.提高外存的读写速度 D用于存储系统文件解析：本题考查文件系统的作用。文件系统是帮助管理文件的，使得用户能够按照文件名称或者目录名称访问文件或目录，而不用知道其具体的内部机制是什么样的，即对用户透明。答案选A,46,【例2】位示图(Bitmap)可用于磁盘空间的管理。设某系统磁盘共有500块，块号从0499；第0字的第0位表示第0块，第0字的第1位表示第1
20、块，由此类推，若用位示图法管理这500块的盘空间，当字长为32位时，第i个字第j位对应的块号是_。A32i+jB32i+j+1C32i+i-32D32i+j-32-1解析：第0字的第32位是第32块，以此类推，第i一1字的第32位是32i，第j位是32i+j块。所以答案A,47,【例3】UNIX系统中，正确描述文件目录和索引结点的概念是()。【电子科大 2008】A文件目录和索引结点相同 B文件目录和索引结点无联系C文件目录中有文件的控制信息 D索引结点中有文件的控制信息解析：本题考查UNIX操作系统中的文件目录与索引结点的概念。它们之间存在着联系，一般是索引结点中有文件的控制信息。答案选D,48,
