計(jì)算機(jī)操作系統(tǒng)第八章課件剖析8.1外存的組織方式連續(xù)鏈接索引8.1.1連續(xù)組織方式連續(xù)分配的主要優(yōu)缺點(diǎn)連續(xù)分配的主要優(yōu)點(diǎn)如下：(1)順序訪問容易。(2)順序訪問速度快。連續(xù)分配的主要缺點(diǎn)如下：(1)要求有連續(xù)的存儲(chǔ)空間。(2)必須事先知道文件的長(zhǎng)度。(3)插入刪除不便(4)動(dòng)態(tài)增長(zhǎng)困難8.1.2鏈接組織方式1.隱式鏈接2.顯式鏈接8.1.3FAT技術(shù)8.1.4NTFS的文件組織方式8.1.5索引組織方式1.單級(jí)索引組織方式鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題，但又出現(xiàn)了另外兩個(gè)問題，即：

(1)不能支持高效的直接存取。要對(duì)一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號(hào)。

(2)FAT需占用較大的內(nèi)存空間。索引塊：分配給文件的所有盤塊號(hào)都記錄在索引塊中支持直接訪問，不產(chǎn)生外部碎片2.多級(jí)索引組織方式大文件可采用多級(jí)索引分配方式兩級(jí)索引分配盤塊1KB，盤塊號(hào)4字節(jié)，一索引塊存放256盤塊，二級(jí)索引包含的盤塊總數(shù)是256*256=64K個(gè)，文件容量=64k*1k=64M3.增量式索引組織方式UNIXSystemV索引結(jié)點(diǎn)，共iaddr(0)-iaddr(12)13個(gè)地址項(xiàng)。假如每個(gè)盤塊的大小為4KB，盤塊號(hào)占4字節(jié)。(1)直接地址。為了提高對(duì)文件的檢索速度，在索引結(jié)點(diǎn)中可設(shè)置10個(gè)直接地址項(xiàng)，即用iaddr(0)~iaddr(9)來存放直接地址。換言之，在這里的每項(xiàng)中所存放的是該文件數(shù)據(jù)的盤塊的盤塊號(hào)。假如每個(gè)盤塊的大小為4KB，當(dāng)文件不大于40KB時(shí)，便可直接從索引結(jié)點(diǎn)中讀出該文件的全部盤塊號(hào)。(2)一次間接地址。對(duì)于大、中型文件，只采用直接地址是不現(xiàn)實(shí)的。為此，可再利用索引結(jié)點(diǎn)中的地址項(xiàng)iaddr(10)來提供一次間接地址。這種方式的實(shí)質(zhì)就是一級(jí)索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個(gè)盤塊號(hào)記入其中。在一次間址塊中可存放1K個(gè)盤塊號(hào)，因而允許文件長(zhǎng)達(dá)4MB。(3)多次間接地址。當(dāng)文件長(zhǎng)度大于4MB+40KB時(shí)(一次間址與10個(gè)直接地址項(xiàng))，系統(tǒng)還須采用二次間址分配方式。這時(shí)，用地址項(xiàng)iaddr(11)提供二次間接地址。該方式的實(shí)質(zhì)是兩級(jí)索引分配方式。系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的盤號(hào)。在采用二次間址方式時(shí)，文件最大長(zhǎng)度可達(dá)4GB。同理，地址項(xiàng)iaddr(12)作為三次間接地址，其所允許的文件最大長(zhǎng)度可達(dá)4TB。8.2文件存儲(chǔ)空間的管理以盤塊為單位為新文件分配存儲(chǔ)空間8.2.1空閑表法和空閑鏈表法1.空閑表法連續(xù)分配1）空閑表序號(hào)第一空閑盤塊號(hào)空閑盤塊數(shù)12429331554——2)存儲(chǔ)空間的分配與回收空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。例如，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時(shí)，先順序地檢索空閑表的各表項(xiàng)，直至找到第一個(gè)其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進(jìn)程)，同時(shí)修改空閑表。系統(tǒng)在對(duì)用戶所釋放的存儲(chǔ)空間進(jìn)行回收時(shí)，也采取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對(duì)相鄰接者應(yīng)予以合并。2.空閑鏈表法(1)空閑盤塊鏈。

(2)空閑盤區(qū)鏈。8.2.2位示圖法1.位示圖利用二進(jìn)制的一位表示磁盤盤塊使用情況。0閑1分2.盤塊的分配(1)順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位(“0”表示空閑時(shí))。(2)將所找到的一個(gè)或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。假定找到的其值為“0”的二進(jìn)制位，位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算：

b=n(i-1)+j

式中，n代表每行的位數(shù)。(3)修改位示圖，令map［i,j］=1。3.盤塊的回收(1)將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。轉(zhuǎn)換公式為：

i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示圖。令map［i,j］=0。優(yōu)點(diǎn)：很容易找到一個(gè)或一組相鄰接的空閑盤塊?？煞旁趦?nèi)存中。8.2.3成組鏈接法1.空閑盤塊的組織2.空閑盤塊的分配與回收當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，須調(diào)用盤塊分配過程來完成。該過程首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。若該盤塊號(hào)已是棧底，即S.free(0)，這是當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)。由于在該盤塊號(hào)所對(duì)應(yīng)的盤塊中記有下一組可用的盤塊號(hào)，因此，須調(diào)用磁盤讀過程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號(hào)棧的內(nèi)容，并把原棧底對(duì)應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。然后，再分配一相應(yīng)的緩沖區(qū)(作為該盤塊的緩沖區(qū))。最后，把棧中的空閑盤塊數(shù)減1并返回。在系統(tǒng)回收空閑盤塊時(shí)，須調(diào)用盤塊回收過程進(jìn)行回收。它是將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加1操作。當(dāng)棧中空閑盤塊號(hào)數(shù)目已達(dá)100時(shí)，表示棧已滿，便將現(xiàn)有棧中的100個(gè)盤塊號(hào)，記入新回收的盤塊中，再將其盤塊號(hào)作為新棧底。8.3提高磁盤I/O速度的途徑8.3.1磁盤高速緩存1.數(shù)據(jù)交付方式（數(shù)據(jù)交付指針交付）2.置換算法（LRU、NRU、LFU）3.周期性地寫回磁盤（UNIX系統(tǒng)的update程序調(diào)用SYNC）提高磁盤I/O速度的其它方法8.3.3廉價(jià)磁盤冗余隊(duì)列RedundantArrayofInexpensiveDisk,RAID3.RAID的優(yōu)點(diǎn)8.4提高磁盤可靠性的技術(shù)容錯(cuò)技術(shù)磁盤容錯(cuò)技術(shù)系統(tǒng)容錯(cuò)技術(shù)級(jí)別第一級(jí)低級(jí)磁盤容錯(cuò)技術(shù)第二級(jí)中級(jí)磁盤容錯(cuò)技術(shù)第三級(jí)系統(tǒng)容錯(cuò)技術(shù)8.4.1第一級(jí)容錯(cuò)技術(shù)SFT-Ⅰ防止磁盤表面缺陷造成數(shù)據(jù)丟失1.雙份目錄和雙份文件分配表在磁盤上存放的文件目錄和文件分配表FAT，是文件管理所用的重要數(shù)據(jù)結(jié)構(gòu)。如果這些表格被破壞，將導(dǎo)致磁盤上的部分或全部文件成為不可訪問的，因而也就等效于文件的丟失。為了防止這類情況發(fā)生，可在不同的磁盤上或在磁盤的不同區(qū)域中，分別建立(雙份)目錄表和FAT。其中，一份被稱為主目錄及主FAT；把另一份稱為備份目錄及備份FAT。2.熱修復(fù)重定向和寫后讀校驗(yàn)(1)熱修復(fù)重定向(Hot-Redirection)。(2)寫后讀校驗(yàn)(ReadafterwriteVerification)方式。8.4.2第二級(jí)容錯(cuò)技術(shù)SFT-Ⅱ防止磁盤驅(qū)動(dòng)器和控制器故障導(dǎo)致系統(tǒng)不能正常工作1.磁盤鏡像(DiskMirroring)。2.磁盤雙工(DiskDuple