操作系统第20讲new

操作系统第20讲new第一页，共44页。本次课程主要内容磁盘存储器的管理磁盘调度磁盘高速缓存提高磁盘I/O速度的其它方法外存分配方式连续分配链接分配索引分配第二页，共44页。5.6磁盘存储器的管理

5.6.1磁盘性能简述1．数据的组织和格式3第三页，共44页。格式化后的磁盘：4第四页，共44页。2．磁盘的类型对磁盘，可以从不同的角度进行分类。最常见的有：将磁盘分成硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头(移动头)磁盘等。5第五页，共44页。3．磁盘访问时间

1)寻道时间Ts这是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即Ts=m×n+s其中，m是一常数，与磁盘驱动器的速度有关。对于一般磁盘，m=0.2；对于高速磁盘，m≤0.1，磁臂的启动时间约为2ms。这样，对于一般的温盘，其寻道时间将随寻道距离的增加而增大，大体上是5～30ms。6第六页，共44页。2)旋转延迟时间Tr这是指定扇区移动到磁头下面所经历的时间。不同的磁盘类型中，旋转速度至少相差一个数量级，如软盘为300r/min，硬盘一般为7200～15000r/min，甚至更高。对于磁盘旋转延迟时间而言，如硬盘，旋转速度为15000r/min，每转需时4ms，平均旋转延迟时间Tr为2ms；而软盘，其旋转速度为300r/min或600r/min，这样，平均Tr为50～100ms。7第七页，共44页。3)传输时间Tt这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt的大小与每次所读/写的字节数b和旋转速度有关:其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时，Tt与Tr相同。因此，可将访问时间Ta表示为8第八页，共44页。5.6.2磁盘调度1．先来先服务(FCFS，FirstComeFirstServed)9第九页，共44页。2．最短寻道时间优先(SSTF，ShortestSeekTimeFirst)10第十页，共44页。3．扫描(SCAN)算法11第十一页，共44页。4．循环扫描(CSCAN)算法12第十二页，共44页。5．NStepSCAN和FSCAN调度算法1)NStepSCAN算法在SSTF、SCAN及CSCAN几种调度算法中，都可能会出现磁臂停留在某处不动的情况，例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”(Armstickiness)。在高密度磁盘上容易出现此情况。N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。13第十三页，共44页。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当N值取得很大时，会使N步扫描法的性能接近于SCAN算法的性能；当N=1时，N步SCAN算法便蜕化为FCFS算法。14第十四页，共44页。2)FSCAN算法FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。15第十五页，共44页。5.6.3磁盘高速缓存1．磁盘高速缓存的形式这里所说的磁盘高速缓存，并非通常意义下的内存和CPU之间所增设的一个小容量高速存储器，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。16第十六页，共44页。5.6.4提高磁盘I/O速度的其它方法1．提前读(Read-ahead)用户(进程)对文件进行访问时，经常采用顺序访问方式，即顺序地访问文件各盘块的数据。在这种情况下，在读当前块时可以预知下一次要读的盘块。因此，可以采取预先读方式，即在读当前块的同时，还要求将下一个盘块(提前读的块)中的数据也读入缓冲区。从而大大减少了读数据的时间。这也就等效于提高了磁盘I/O的速度。17第十七页，共44页。2．延迟写延迟写是指在缓冲区A中的数据，并不立即将该缓冲区A中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾。随着空闲缓冲区的使用，缓冲区也缓缓往前移动，直至移到空闲缓冲队列之首。当再有进程申请到该缓冲区时，才将该缓冲区中的数据写入磁盘。这样，又可进一步减小等效的磁盘I/O时间。18第十八页，共44页。3．优化物理块的分布例如，将文件的第一个盘块安排在最里的一条磁道上，而把第二个盘块安排在最外的一条磁道上，这样，在读完第一个盘块后转去读第二个盘块时，磁头要从最里的磁道移到最外的磁道上。如果我们将这两个数据块安排在属于同一条磁道的两个盘块上，显然会由于消除了磁头在磁道间的移动，而大大提高对这两个盘块的访问速度。19第十九页，共44页。4．虚拟盘所谓虚拟盘，是指利用内存空间去仿真磁盘，又称为RAM盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中。这些对用户都是透明的。虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。虚拟盘与磁盘高速缓存的主要区别在于:虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。20第二十页，共44页。5.6.5廉价磁盘冗余阵列1．并行交叉存取21第二十一页，共44页。2．RAID的分级RAID在刚被推出时，是分成6级的，即RAID0级至RAID5级，后来又增加了RAID6级和RAID7级。22第二十二页，共44页。3．RAID的优点RAID自1988年问世后，便引起了人们的普遍关注，并很快地流行起来。这主要是因为RAID具有下述一系列明显的优点:(1)可靠性高。RAID最大的特点就是它的高可靠性。除了RAID0级外，其余各级都采用了容错技术。当阵列中某一磁盘损坏时，并不会造成数据的丢失，因为它既可实现磁盘镜像，又可实现磁盘双工，还可实现其它的冗余方式。所以此时可根据其它未损坏磁盘中的信息，来恢复已损坏的盘中的信息。它与单台磁盘机相比，其可靠性高出了一个数量级。23第二十三页，共44页。(2)磁盘I/O速度高。由于磁盘阵列可采取并行交叉存取方式，故可将磁盘I/O速度提高N-1倍(N为磁盘数目)。或者说，磁盘阵列可将磁盘I/O速度提高数倍至数十倍。(3)性能/价格比高。利用RAID技术来实现大容量高速存储器时，其体积与具有相同容量和速度的大型磁盘系统相比，只是后者的1/3，价格也只是后者的1/3，且可靠性高。换言之，它仅以牺牲1/N的容量为代价，换取了高可靠性；而不像磁盘镜像及磁盘双工那样，须付出50%容量的代价。24第二十四页，共44页。6.3外存分配方式

6.3.1连续分配1．连续分配方式在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。25第二十五页，共44页。26第二十六页，共44页。2．连续分配的主要优缺点连续分配的主要优点如下：(1)顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从b块开始存放的文件中的第i个盘块的内容，就可直接访问b+i号盘块。27第二十七页，共44页。(2)顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。28第二十八页，共44页。连续分配的主要缺点如下：(1)要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。(2)必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。29第二十九页，共44页。6.3.2链接分配1．隐式链接30第三十页，共44页。2．显式链接31第三十一页，共44页。6.3.3FAT和NTFS技术1．FAT1232第三十二页，共44页。每个文件的第一个盘块号放在自己的FCB中。整个系统有一张文件分配表FAT。在FAT的每个表项中存放下一个盘块号。对于1.2MB的软盘，每个盘块的大小为512B，在每个FAT中共含有2.4K个表项，由于每个FAT表项占12位，故FAT表占用3.6KB的存储空间。33第三十三页，共44页。由于每个FAT表项为12位，因此，在FAT表中最多允许有4096个表项，如果采用以盘块作为基本分配单位，每个盘块(也称扇区)的大小一般是512字节，那么，每个磁盘分区的容量为2MB(4096×512B)。同时，一个物理磁盘支持4个逻辑磁盘分区，所以相应的磁盘最大容量仅为8MB。34第三十四页，共44页。为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n(n为整数)个盘块，在MS-DOS的实际运用中，簇的容量可以仅有一个扇区(512B)、两个扇区(1KB)、四个扇区(2KB)、八个扇区(4KB)等。35第三十五页，共44页。2．FAT16对FAT12所存在的问题进行简单的分析即可看出，其根本原因在于，FAT12表最多只允许4096个表项，亦即最多只能将一个磁盘分区分为4096个簇。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。由此可以得出解决方法，那就是增加FAT表的表项数，亦即应增加FAT表的宽度，如果我们将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65536(216)个簇。我们把具有16位表宽的FAT表称为FAT16。在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64，由此得出FAT16可以管理的最大分区空间为216×64×512=2048MB。36第三十六页，共44页。3．FAT32每一簇在FAT表中的表项占据4字节(232)，FAT表可以表示4294967296项，即FAT32允许管理比FAT16更多的簇。这样就允许在FAT32中采用较小的簇，FAT32的每个簇都固定为4KB，即每簇用8个盘块代替FAT16的64个盘块，每个盘块仍为512字节，FAT32分区格式可以管理的单个最大磁盘空间大到4KB×232=2TB。37第三十七页，共44页。4．NTFSNTFS(NewTechnology)是一个专门为WindowsNT开发的、全新的文件系统，并适用于Windows2000/XP/2003。NTFS具有许多新的特征：首先，它使用了64位磁盘地址，理论上可以支持2的64次方字节的磁盘分区；其次，在NTFS中可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为32767个字符；第三，具有系统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行，第四，提供了数据的一致性，此外，NTFS还提供了文件加密、文件压缩等功能38第三十八页，共44页。在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可