計(jì)算機(jī)操作系統(tǒng)第八章課件

1、第八章第八章 磁盤存儲(chǔ)器的管理磁盤存儲(chǔ)器的管理8.1 外存的組織方式外存的組織方式連續(xù)連續(xù) 鏈接鏈接 索引索引8.1.1 連續(xù)組織方式連續(xù)組織方式1230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目錄trf連續(xù)分配的主要優(yōu)缺點(diǎn)連續(xù)分配的主要優(yōu)缺點(diǎn)連續(xù)分配的主要優(yōu)點(diǎn)如下：(1)順序訪問容易。 (2) 順序訪問速度快。連續(xù)分配的主要缺點(diǎn)如下：(1)要求有連續(xù)的存儲(chǔ)空間。 (2) 必須事先知道文件的長度。(3)插入刪除不便(4)動(dòng)

2、態(tài)增長困難8.1.2 鏈接組織方式鏈接組織方式1. 隱式鏈接隱式鏈接25123056749101181314151217181916212223202526272429303128filestartendjeep925目錄101-1162. 顯式鏈接顯式鏈接012345物理塊號(hào)2FCBFAT04518.1.3 FAT技術(shù)6EOF11105EOF0123456789FATFCB A4FCB B98.1.4 NTFS的文件組織方式8.1.5 索引組織方式索引組織方式1. 單級(jí)索引組織方式單級(jí)索引組織方式 鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題， 但又出現(xiàn)了另外兩個(gè)問題， 即： (1) 不能

3、支持高效的直接存取。要對(duì)一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號(hào)。 (2) FAT需占用較大的內(nèi)存空間。 索引塊：分配給文件的所有盤塊號(hào)都記錄在索引塊中 支持直接訪問，不產(chǎn)生外部碎片123056749101181314151217181916212223202526272429303128countfile塊序號(hào)jeep19目錄91611025111192. 多級(jí)索引組織方式多級(jí)索引組織方式01210510625435635798510510625474035635711259853607401125主索引360第二級(jí)索引磁盤空間 大文件可采用多級(jí)索引分配方式 兩級(jí)索引

4、分配 盤塊1KB，盤塊號(hào)4字節(jié)，一索引塊存放256盤塊，二級(jí)索引包含的盤塊總數(shù)是256*256=64K個(gè)，文件容量=64k*1k=64M3.增量式索引組織方式modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata UNIX System V索引結(jié)點(diǎn)，共iaddr(0)-iaddr(12)13個(gè)地址項(xiàng)。假如每個(gè)盤塊的大小為 4 K

5、B，盤塊號(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è)盤塊的大小為 4 KB，當(dāng)文件不大于40 KB時(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è)盤

6、塊號(hào)， 因而允許文件長達(dá)4 MB。 (3) 多次間接地址。 當(dāng)文件長度大于4 MB+40 KB時(shí)(一次間址與10個(gè)直接地址項(xiàng))， 系統(tǒng)還須采用二次間址分配方式。這時(shí)，用地址項(xiàng)iaddr(11)提供二次間接地址。該方式的實(shí)質(zhì)是兩級(jí)索引分配方式。系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的盤號(hào)。在采用二次間址方式時(shí)，文件最大長度可達(dá)4 GB。 同理，地址項(xiàng)iaddr(12)作為三次間接地址， 其所允許的文件最大長度可達(dá)4TB。 8.2 文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理以盤塊為單位為新文件分配存儲(chǔ)空間以盤塊為單位為新文件分配存儲(chǔ)空間8.2.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法1. 空閑表

7、法空閑表法連續(xù)分配連續(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 位示圖法位

8、示圖法1. 位示圖位示圖 利用二進(jìn)制的一位表示磁盤盤塊使用情況。利用二進(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) 修改位示圖， 令mapi,j=1。3. 盤塊的回收盤塊的回收(1) 將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。 轉(zhuǎn)換公式為： i=(b-1)DIV n+1

9、j=(b-1)MOD n+1 (2) 修改位示圖。 令map i,j=0。 優(yōu)點(diǎn)：很容易找到一個(gè)或一組相鄰接的空閑盤塊?？煞旁趦?nèi)存中。8.2.3 成組鏈接法成組鏈接法1. 空閑盤塊的組織空閑盤塊的組織1004003993013001003002992022012991004003992013019907999790179007899780179997901空閑盤塊號(hào)棧S.free0198992. 空閑盤塊的分配與回收空閑盤塊的分配與回收 當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，須調(diào)用盤塊分配過程來完成。該過程首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用

10、戶，然后將棧頂指針下移一格。若該盤塊號(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)， 記

11、入新回收的盤塊中，再將其盤塊號(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）8.3.2提高磁盤I/O速度的其它方法 1.提前讀 2.延遲寫 3.優(yōu)化物理塊的分布 4.虛擬盤8.3.3 廉價(jià)磁盤冗余隊(duì)列 Redundant Array of Inexpensive Disk,RAID 1.并行交叉存取 2.RAID的分級(jí) 3. RAID的優(yōu)點(diǎn)8.4 提高磁盤可靠性的技術(shù) 容錯(cuò)技術(shù) 磁盤容錯(cuò)技術(shù) 系統(tǒng)容錯(cuò)技術(shù)級(jí)

12、別 第一級(jí) 低級(jí)磁盤容錯(cuò)技術(shù) 第二級(jí) 中級(jí)磁盤容錯(cuò)技術(shù) 第三級(jí) 系統(tǒng)容錯(cuò)技術(shù)8.4.1 第一級(jí)容錯(cuò)技術(shù)第一級(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)(Read after write Verification)方式。8.4.2 第二級(jí)容錯(cuò)技術(shù)第二級(jí)容錯(cuò)技術(shù)SFT-防止磁盤驅(qū)動(dòng)器和控制器故障導(dǎo)致系統(tǒng)不能正常工作防止磁盤驅(qū)動(dòng)器和控制器故障導(dǎo)致系統(tǒng)不能正常工作1.磁盤鏡像(Disk Mirroring)。磁盤控制器主機(jī)通道磁盤驅(qū)動(dòng)器2. 磁盤雙工