操作系统(第四版)第06-2章.ppt

1,第九章磁盘存储器管理,2,概述,物理块与存储介质物理块(块)在文件系统中，文件的存储设备常常划分为若干大小相等的物理块。同时也将文件信息划分成相同大小的逻辑块（块），所有块统一编号。以块为单位进行信息的存储、传输，分配存储介质:磁盘，磁带，光盘,3,1.磁带,永久保存大容量数据顺序存取设备：前面的物理块被存取访问之后,才能存取后续的物理块的内容,存取速度较慢，主要用于后备存储，或存储不经常用的信息，或用于传递数据的介质,4,第i块间隙第i+1块,5,2.磁盘,直接（随机）存取设备：存取磁盘上任一物理块的时间不依赖于该物理块所处的位置,6,磁道,扇区,7,柱面,扇区,磁臂,磁头,8,1)磁道与柱面,信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头所有盘面中处于同一磁道号上的所有磁道组成一个柱面物理地址形式：磁头号（盘面号）磁道号（柱面号）扇区号,9,2)磁盘系统与磁盘分类,磁盘系统由磁盘本身和驱动控制设备组成，实际存取读写的动作过程是由磁盘驱动控制设备按照主机要求完成的硬盘又分为两种：固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低,10,3)访盘请求完成过程,磁盘地址（设备号，柱面号，磁头号，扇区号），内存地址（源/目）一次访盘请求（读/写）完成过程由三个动作组成：寻道（时间）：磁头移动定位到指定磁道旋转延迟（时间）：等待指定扇区从磁头下旋转经过数据传输（时间）：数据在磁盘与内存之间的实际传输磁盘访问时间：（见教材P258页）,11,3.光盘,光盘容量大，速度快，价格便宜，但一般不可写可读写光盘驱动器价格贵，写过程很麻烦光盘的空间结构与磁盘类似,12,4.外存的特点,容量大，断电后仍可保存信息，速度较慢，成本较低两部分组成：驱动部分+存储介质种类很多外存空间组织与地址、与存取方式非常复杂I/O过程方式非常复杂,13,5.用户对外存的要求,用户对外存的使用：读写外存数据用户对外存的要求：方便、效率、安全(1)在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作(2)存取速度尽可能快，容量大且空间利用率高(3)外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权(4)可以方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况(5)以尽可能小的代价完成上述要求,14,磁盘调度算法,早期的磁盘调度算法先来先服务最短寻道时间优先各种扫描算法SCAN算法循环扫描算法N-Step-SCAN算法和FSCAN算法,15,5.6.2磁盘调度,1.先来先服务FCFS(First-Come,FirstServed),图5-23FCFS调度算法,16,2.最短寻道时间优先SSTF(ShortestSeekTimeFirst),图5-24SSTF调度算法,17,3.扫描(SCAN)算法,1)进程“饥饿”现象,SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(Starvation)现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必须优先满足。对SSTF算法略加修改后所形成的SCAN算法，即可防止老进程出现“饥饿”现象。,18,2)SCAN算法,图5-25SCAN调度算法示例,19,4.循环扫描(CSCAN)算法,图5-26CSCAN调度算法示例,20,5.N-Step-SCAN和FSCAN调度算法,1)N-Step-SCAN算法在SSTF、SCAN及CSCAN几种调度算法中，都可能出现磁臂停留在某处不动的情况，例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”(Armstickiness)。在高密度磁盘上容易出现此情况。N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当N值取得很大时，会使N步扫描法的性能接近于SCAN算法的性能；当N=1时，N步SCAN算法便蜕化为FCFS算法。,21,2)FSCAN算法FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。,22,9.2外存分配方法（文件的物理结构）,文件的物理结构文件的物理结构也即文件的外存分配方式。是从系统的角度来看文件，从文件在物理介质上的存放方式来研究文件,23,9.2.1连续分配,一个文件的信息存放在若干连续的物理块中由一组相邻的物理块组成，是对记录式文件取连续区分配而构成的文件。优点:简单支持顺序存取和随机存取顺序存取速度快所需的磁盘寻道次数和寻道时间最少,24,连续文件结构,25,连续文件例,磁盘空间的连续分配,26,连续分配的主要优缺点,连续分配的主要优点如下：(1)顺序访问容易(2)顺序访问速度快连续分配的主要缺点如下：(1)要求有连续的存储空间(2)必须事先知道文件的长度,27,链接分配,一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块优点：提高了磁盘空间利用率不存在外部碎片问题有利于文件插入和删除有利于文件动态扩充缺点：存取速度慢，不适于随机存取可靠性问题，如指针出错更多的寻道次数和寻道时间链接指针占用一定的空间链接结构的一个变形:文件分配表FAT,28,1.隐式链接,文件名始址末址,jeep925,文件目录,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,1,10,16,-1,25,磁盘空间的链接式分配,29,2.显式链接,为整个磁盘建立一张链接表，表的序号是物理盘块号，每个表项都有一个指针，指向该表项对应的盘块号存放的文件的下一个盘块号，文件的FCB中有一指针指向表中的文件的第一个物理盘块所对应的表项。该表称为文件分配表，FAT表。（见教材P266页图9-8）,30,链接分配的优缺点,链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即：(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。,31,9.2.3索引分配,一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中索引表：一个文件所有记录的关键字和其地址的对照表。一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块,32,1.单级索引分配,文件名索引表地址,文件目录,Jeep19,91611025-1-1-1,19,33,索引结构优缺点,优点：保持了链接结构的优点,又解决了其缺点：即能顺序存取,又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用外存空间缺点：较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间,34,多级索引,两级索引分配,35,混合索引方式,36,综合模式,UNIX文件系统采用的是多级索引结构(综合模式)。每个文件的索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址UNIX中采用了三级索引结构后，文件最大可达16兆个物理块,37,9.3空闲存储空间的管理,1.空闲块表（空白文件目录）将所有空闲块记录在一个表中，即空闲块表2.空闲块链表把所有空闲块链成一个链3.位图法用一串二进制位反映磁盘空间中分配使用情况,每个物理块对应一位,分配物理块为1，否则为0,38,1.空白的文件目录,一个连续的未分配区域称为“空白文件”，系统为所有这些“空白文件”单独建立一个目录。每个空白文件，在目录中建立一个表目。表目的内容包括：第一空白物理块的地址（块号）、空白块的数目。当请求分配存储空间时，系统依次扫描空白文件目录的表目，直到找到一个合适的空白文件为止当用户撤消一个文件时，系统回收该文件所占用的空间。扫描目录，寻找一个空表目，并将释放空间的第一物理号及它所占的物理块数填到这个表目中。,空白的文件目录（续）,仅当有少量的空白区时才有较好的效果如果存取空间中有着大量的小的空白区，则其目录变得很大，因而效率大为降低。这种分配技术适用于建立连续文件。,40,2.空闲块链,把其中所有的“空白块”链在一起。创建文件需要一个或几个物理块时，就从链头依次取下一块或几块。回收文件时回收块链到空白链上。根据构成链的基本元素的不同，有两种链表形式：空闲盘块链（分配和回收简单，但链很长）和空闲盘区链。（与空闲盘块链相反）,41,3位示图法,常用的管理存储空间的办法是建立一张位示图，以反映整个存取空间的分配请况用一串二进制位反映磁盘空间中分配使用情况,每个物理块对应一位,1表示对应的物理块已分配，0表示其对应的块未分配申请物理块时，可以在位示图中查找为0的位，返回对应物理块号归还时；将对应位转置0描述能力强，适合各种物理结构,42,1)位示图,位示图,通常用mn个位数构成位示图，因而将位示图描述为一个二维数组map。,43,2)盘块的分配,(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j式中，n代表每行的位数。(3)修改位示图，令mapi,j=1。,44,3)盘块的回收,(1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示图。令mapi,j=1。,45,9.4.3成组链接法,1.空闲盘块的组织,空闲盘块的成组链接法,46,2.空闲盘块的分配与回收,当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。,47,空闲盘块的分配与回收（续）,在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。,48,9.4磁盘容错技术,文件系统的安全：(1)通过存取控制机制来防止由人为因素所造成的文件不安全性。(2)通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。(3)通过“后备系统”来防止由自然因素所造成的不安全性。磁盘容错技术是通过增加冗余的磁盘驱动器、磁盘控制器等，来提高磁盘系统的可靠行。,49,磁盘容错技术的三个级别,低级容错技术SFTI主要用于防止磁盘表面发生缺陷所引起的数据丢失。中级容错技术SFT-II主要用于防止磁盘驱动器和磁盘控制器故障所引起的系统不能正常工作。高级容错技术SFT-III,50,1.第一级容错技术SFTI,采用双份目录，双份文件分配表及写后读校验等。FAT（文件分配表）：记录文件属性，物理地址等。系统每次启动时，对两份FAT检查是否一致。在磁盘上存放的文件目录和文件分配表FAT，是文件管理所用的重要数据结构。如果这些表格被破坏，将导致磁盘上的部分或全部文件成为不可访问的，因而也就等效于文件的丢失。为了防止这类情况发生，可在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表和FAT。其中，一份被称为主目录及主FAT；把另一份称为备份目录及备份FAT。,51,热修复重定向：在磁盘中划出一部分作为热修复重定向区，存放坏磁道的待写数据写后读校验：内存（写）盘时，从盘读出与内存校验看是否一致，不一致，重写入热修复重定向区，标记坏盘块。,52,2.第二级容错技术SFT-II,1)磁盘镜像：增设一个完全相同的磁盘驱动器。优点：磁盘驱动器发生故障时切换，仍能正常工作。缺点：磁盘的利用率为50。,磁盘镜像示意图,53,第二级容错技术SFT-II(续),2)磁盘双工将两台磁