档案系统汇总课件.ppt

1、第第 6 章章 檔案系統檔案系統著作權所有 旗標出版股份有限公司本章提要本章提要l檔案系統的基本概念 l目錄結構 l檔案系統結構 26-1檔案系統的基本概念檔案系統的基本概念 l檔案是一群資訊的集合，而檔案系統則是一群檔案的集合 l目錄：又稱為資料夾l為了便於使用者組織與管理檔案及其他檔案系統物件l是包含檔案系統物件名稱的物件 l要存取檔案，必須在檔案名稱前方加上它所對應的目錄路徑 l可以再分為絕對路徑與相對路徑 l絕對路徑範例：C:DRIVERSNETWORKWINDOWSl相對路徑範例：.TOOL 3圖圖6-1 目錄與檔案路徑目錄與檔案路徑4作業系統分辨檔案類型的方法作業系統分辨檔案類型的

2、方法l使用特定的副檔名來表示檔案的類型l在檔案的特定位置尋找由一個或一連串位元組所組成的神奇數字l由作業系統負責提供支援，將檔案型態的資訊視為是檔案相關資訊的一部份5圖圖6-2 變更副檔名的訊息範例變更副檔名的訊息範例6表表6-1 常見的副檔名常見的副檔名 檔案型態常見副檔名執行檔exe,bin,com原始程式檔c,cpp,bas,asp函式庫lib,dll文字檔txt,doc圖形檔gif,jpg,bmp影片檔mpg,avi串流檔asf,rm,wmf壓縮檔rar,zip音效檔wav,mp3,mid網頁檔html,htm,xml7檔案的屬性檔案的屬性 l名稱l型態l位置l大小l保護l擁有者l日期

3、資訊8實作討論-Unix的inode nInode：Unix的檔案控制結構，包含了Unix系統所需的所有檔案相關資訊ninode的資訊內容：q檔案模式q鏈結數目q擁有者IDq群組IDq檔案長度q檔案位址q前次存取時間q前次修改時間qinode修改時間9著作權所有 旗標出版股份有限公司Inode檔案模式欄位的位元意義n12-14：檔案型態n9-11：執行旗標n8：擁有者的讀取權限n7：擁有者的寫入權限n6：擁有者的執行權限n5：群組讀取權限n4：群組寫入權限n3：群組執行權限n2：其他人讀取權限n1：其他人寫入權限n0：其他人執行權限10著作權所有 旗標出版股份有限公司分割區分割區 l分割區：為

4、了便於管理，我們會將一個實體磁碟裝置切割為一或多個邏輯上的磁碟l檔案系統中有時也會包含分割區的資訊，用來記錄檔案存放的邏輯裝置 lDOS、Windows系統：分割區是檔案路徑名稱的一部份，例如C:My DocumentOperatingSystem.doc lUnix、Linux系統：分割區會被掛載到單一的檔案系統命名空間。如果掛載點的目錄中已經有檔案：l某些系統會要求用來擔任掛載點的目錄必須是空的l有些系統是將目錄內原本的資料隱藏起來11圖圖6-3 分割區的掛載分割區的掛載 分割區hd1/bootbinhome檔案檔案分割區hd2/KevinJackyJolin檔案檔案檔案/bootbinh

5、ome檔案檔案KevinJackyJolin檔案檔案檔案使用者看到的統一命名空間12實作討論-Unix的分割區掛載命令 n在Unix中，分割區的掛載是使用mount命令：mount-F FSType generic_options-o specific_opetions -O special|mount_pointn例如：mount F ufs/dev/dsk/c0t1d0s5/usrnmount a：會將/etc/vfstab檔案中所有mount at boot欄位為yes的檔案系統掛載起來numount：將已掛載的分割區卸除 13著作權所有 旗標出版股份有限公司/etc/vfstab的內容

6、範例n用來記錄掛載資訊的檔案要掛載的裝置 執行fsck的裝置 掛載點 檔案系統 fsck 開機時 掛載選項 類型 回合數 掛載？#device devicemount FSfsckmountmount#to mount to fsckpointtypepassat bootoptions#fd-/dev/fdfd-no-/proc-/procproc-no-/dev/dsk/c0t1d0s1-swap-no-/dev/dsk/c0t1d0s0/dev/rdsk/c0t1d0s0/ufs1no-/dev/dsk/c0t1d0s5/dev/rdsk/c0t1d0s5/usrufs1no-/dev/

7、dsk/c0t1d0s6/dev/rdsk/c0t1d0s6/varufs1no-/dev/dsk/c0t1d0s7/dev/rdsk/c0t1d0s7/homeufs2yes-swap-/tmptmpfs-yes-14著作權所有 旗標出版股份有限公司mount的執行範例 Saturn/home/usr/kevin:mount/on/dev/dsk/c0t1d0s0 read/write/setuid/intr/largefiles/xattr/onerror=panic/dev=800008 on Mon Sep 27 22:50:21 2004/usr on/dev/dsk/c0t1d0s

8、5 read/write/setuid/intr/largefiles/xattr/onerror=panic/dev=80000d on Mon Sep 27 22:50:21 2004/proc on/proc read/write/setuid/dev=4440000 on Mon Sep 27 22:50:20 2004/etc/mnttab on mnttab read/write/setuid/dev=4500000 on Mon Sep 27 22:50:20 2004/dev/fd on fd read/write/setuid/dev=4540000 on Mon Sep 2

9、7 22:50:22 2004/var on/dev/dsk/c0t1d0s6 read/write/setuid/intr/largefiles/xattr/onerror=panic/dev=80000e on Mon Sep 27 22:50:23 2004/var/run on swap read/write/setuid/xattr/dev=1 on Mon Sep 27 22:50:23 2004/home on/dev/dsk/c0t1d0s7 read/write/setuid/intr/largefiles/xattr/onerror=panic/dev=80000f on

10、Mon Sep 27 22:50:25 2004/tmp on swap read/write/setuid/xattr/dev=2 on Mon Sep 27 22:50:25 200415著作權所有 旗標出版股份有限公司Unix與Windows在路徑名稱表示上的差異 nWindows：q路徑中的各個目錄之間，是以反斜線（）隔開q不區分大小寫q完整路徑中包含代表分割區的磁碟代號nUnix：q目錄的名稱是以斜線（/）來作區隔，q物件名稱的大小寫不同，就會被視為是不同的物件q將分割區掛載在同一命名空間中，不須特別表示在路徑中n範例：q在Windows中的完整路徑名稱：c:driversnetwo

11、rkwindowsinfcache.1q在Unix中會表示為：/drivers/network/windows/infcache.116著作權所有 旗標出版股份有限公司針對行程指定的根目錄針對行程指定的根目錄l有些系統可以針對個別的行程指定一個目錄，作為該行程的根目錄l該行程將只能看到這個目錄以下的部份l當系統中不需要提供檔案共享時，也可以將每個使用者的家目錄，指定為該使用者所有行程的根目錄l可以用來增進應用程式的安全性17檔案系統的功能檔案系統的功能 l建立檔案l刪除檔案l讀取檔案l寫入檔案l屬性變更18實作討論-Windows 2000/XP的檔案系統 nWindows 2000/XP支援

12、多種檔案系統：qCDFS與UDFqFAT系列：提供向後的相容性qNTFS：企業級的檔案系統nNTFS提供的重要功能：q回復性q安全性q大型磁碟與大型檔案的支援q多重資料串流q通用型索引機制19著作權所有 旗標出版股份有限公司實作討論-Linux的檔案系統 nUnix是Linux作業系統的設計基礎，但除此之外，Linux還支援Ext2、Ext3、Reiser、NFS，以及微軟平台上的檔案系統 nLinux提供一個統一的介面，稱為虛擬檔案系統（VFS），負責處理所有使用者對檔案系統所下的指令 n虛擬檔案系統會將指令轉換為不同檔案系統所對應的程式來執行20著作權所有 旗標出版股份有限公司圖6-4 L

13、inux的虛擬檔案系統使用者行程虛擬檔案系統使用者模式核心模式Ext2Ext3FAT32proc21著作權所有 旗標出版股份有限公司Linux 的裝置檔案 n利用各種不同的裝置檔案來對應到各種裝置，讓使用者依照一般檔案的存取方式，將資料寫入裝置或從裝置讀取資料n與裝置控制相關的虛擬檔案系統：qproc：用來存取系統核心狀態資訊的虛擬檔案系統qdev：所有可用的裝置（不管實際上是否存在），都會以樹狀結構儲存在dev目錄之下 nLinux 2.4以上版本改用devfs作為裝置的虛擬檔案系統22著作權所有 旗標出版股份有限公司6-2 目錄結構目錄結構 l樹狀目錄，可分為：l單層目錄l雙層目錄l多層目

14、錄l圖狀目錄，可分為：l非循環圖狀目錄l一般圖狀目錄 23圖圖6-5 雙層目錄範例雙層目錄範例/binsbinusrdevetcboot檔案檔案檔案檔案檔案檔案24圖圖6-6 多層目錄範例多層目錄範例/binsbinusrdevetcboot檔案檔案檔案檔案檔案KevinJackyJolin檔案檔案檔案25非循環圖狀目錄非循環圖狀目錄 l當檔案系統允許其中的物件擁有多個名稱時，就成為圖狀目錄l如果在圖狀目錄中只允許檔案物件具有多個名稱，則稱為非循環圖狀目錄 l可以讓不同的使用者在各自的目錄底下，以不同的檔名來共用同一組檔案l檔案系統中必須加上一些檔案存取的保護機制l檔案刪除的相關問題 26圖圖

15、6-7 非循環圖狀目錄範例非循環圖狀目錄範例/binsbinusrdevetcboot檔案檔案檔案檔案檔案KevinJolin檔案27實作討論-Windows 的檔案捷徑 n有時候，為了便於存取，我們可能會希望在不同的目錄下，都能夠看到相同的檔案 n在Windows下面，我們可以在檔案圖示上按下右鍵，選擇建立捷徑，以便幫檔案建立捷徑，然後再搬移到適當的目錄下 n請注意：捷徑與複製並不相同 q任一使用者對捷徑內容的修改，都會反應在原始檔案中，但對複本內容的修改或刪除，並不會影響到原始檔案 q刪除捷徑並不會影響原始的檔案，但是刪除原始檔案後，捷徑則無法使用 28著作權所有 旗標出版股份有限公司圖6

16、-8 Windows的檔案捷徑29著作權所有 旗標出版股份有限公司圖6-9 Windows捷徑範例a.對檔案捷徑測試範例建立捷徑與複本b.刪除原始檔案捷徑測試範例之後30著作權所有 旗標出版股份有限公司實作討論Unix的檔案捷徑 nln（link）命令：根據所使用的參數，可以分別達到類似捷徑或別名的效果 q執行ln命令而不加參數時，會建立硬式鏈結：新建立的檔案會直接指向原始檔案的內容q如果加上-s參數，則會建立象徵式鏈結：在新建立的鏈結檔案中放入所要連結的檔案名稱n在Unix中，硬式鏈結只能作用在相同檔案系統中，象徵性鏈結則可以跨檔案系統建立鏈結檔案 31著作權所有 旗標出版股份有限公司象徵式

17、鏈結的執行範例n建立名稱為sample1.txt的象徵式鏈結Saturn/home/usr/kevin:ln s ln_sample.txt samples/sample1.txtn執行刪除ln_sample.txt的動作，然後再試圖在螢幕上顯示sample1.txt Saturn/home/usr/kevin:rm ln_sample.txtSaturn/home/usr/kevin:cat samples/sample1.txtcat:cannot open samples/sample1.txt 錯誤訊息n嘗試顯示ln_sample.txt的內容 Saturn/home/usr/kevi

18、n:cat ln_sample.txtcat:cannot open ln_sample.txt 錯誤訊息32著作權所有 旗標出版股份有限公司硬式鏈結的執行範例n顯示原始檔案內容，建立硬式鏈結，刪除原始檔案，顯示硬式鏈結檔案內容：Saturn/home/usr/kevin:cat ln_sample.txthard link test 檔案內容Saturn/home/usr/kevin:ln ln_sample.txt samples/sample2.txtSaturn/home/usr/kevin:rm ln_sample.txtSaturn/home/usr/kevin:cat sampl

19、es/sample2.txthard link test 檔案內容ninode中的鏈結數目欄位，就是用來記錄目前連到檔案內容物件的硬式鏈結總數 33著作權所有 旗標出版股份有限公司一般圖狀目錄一般圖狀目錄l如果系統允許使用者對目錄也建立多個名稱，則可能會形成包含封閉環的一般圖狀目錄l這種架構就很容易造成檔案搜尋的問題l在提供這種功能的系統中，可能必須要限制搜尋的目錄層次，或是去偵測是否有封閉環的存在lUnix採取的是有限程度的目錄捷徑功能：只有作業系統才能為目錄建立多個名稱，而使用者只能為檔案建立多個名稱l每當有新目錄建立時，檔案系統會在其中加入.與.兩個目錄捷徑，分別指向目前所在的目錄與它上

20、一層的父目錄34圖圖6-10 一般圖狀目錄範例一般圖狀目錄範例/KevinJacky檔案檔案Jacky_dirKevin_dir356-3檔案系統結構檔案系統結構 l對於作業系統而言，要找到檔案內部的某一特定位置可能是個相當複雜的任務l對於磁碟這類裝置而言，它的輸出/輸入都是以固定大小的區塊為單位，稱為實體區塊l使用者所看到的檔案，則是由所謂邏輯記錄所組成l每筆邏輯記錄又可能由一組欄位所構成l檔案的邏輯記錄大小通常都不會與實體記錄完全一致，因此，作業系統會將檔案視為是由一組固定長度的邏輯區塊所組成l每個實體區塊會儲存一個邏輯區塊，以及相關的區塊管理資訊 36圖圖6-11 檔案的邏輯結構範例檔案

21、的邏輯結構範例欄位0(姓名）欄位1（性別）欄位n（血型）記錄0王小明男O記錄1李大同男A記錄k方英英女AB37檔案系統的結構組織檔案系統的結構組織 l裝置驅動程式：負責實際的I/O運算l基本檔案系統：電腦系統與外部裝置間的主要界面，處理兩者間的區塊交換l檔案組織模組：負責邏輯位置與實體位置的對應，以及磁碟上閒置區塊的管理l邏輯檔案系統：提供使用者的存取界面，管理目錄結構，並且維護檔案與目錄的存取權38圖圖6-12 檔案系統結構檔案系統結構邏輯檔案系統檔案組織模組基本檔案系統裝置驅動程式使用者程式輔助儲存裝置39邏輯檔案系統邏輯檔案系統 l檔案系統與使用者間的界面，負責管理使用者對檔案的存取l提

22、供不同的存取方法l循序存取 l隨機存取 l索引存取 l根據檔案擁有者或系統管理者的設定，來控管不同使用者對檔案的存取權限40循序存取循序存取 l依循著資料在檔案中的存放順序進行存取l作業系統會為每個開啟的檔案建立指標：檔案的讀取或寫入運算並不需要指定位置，而是發生在檔案指標所指的位置l有時也提供快轉或退後的功能l是磁帶裝置的基本存取方法，但在磁碟之類的隨機存取裝置中，也可以採用這種運作方式檔案指標（讀寫發生點）讀寫進行方向檔案開頭檔案結尾41隨機存取隨機存取 l隨機存取：又稱為直接存取l可以在任意時間點，隨意存取檔案中任意的邏輯位置l邏輯區塊的編號是由0開始遞增l假設每個邏輯區塊的長度為102

23、4位元組，則要存取第3750個位元組的資料，就必須存取編號3的邏輯區塊l3750/1024=第4個區塊l實體區塊則可能會處於磁碟中不連續的位置上l不是所有實體裝置都支援直接存取的模式42課堂練習 假設每個邏輯區塊的長度為512位元組，請分別計算下列位元組所在的邏輯區塊編號：第2630個位元組 第3481個位元組 第1個位元組 第1024個位元組43練習解答 第2630個位元組2630/512 -1=6 1=5 第3481個位元組3481/512 -1=6 第1個位元組1/512 -1=0 第1024個位元組1024/512 -1=144索引存取索引存取 l利用邏輯記錄中的某個欄位做為索引，建立

24、指向特定資料區塊的指標l當索引檔案本身過於龐大時，也可以建立多層的索引結構姓名指標王小明方英英李大同姓名性別血型王小明男O李大同男A方英英女AB索引檔檔案45同步與非同步的檔案存取同步與非同步的檔案存取 l檔案的讀取或寫入運算可以再細分為同步式或非同步式l當行程進行同步式的I/O運算時，它會進入懸置狀態，直到整個I/O運算結束之後，才繼續後續的動作l非同步式I/O運算則會立即將控制權還給行程，讓行程得以繼續執行後續的動作，就好像I/O已經完成一樣l如果是採取非同步式運算，作業系統就必須提供某些機制，以便在I/O運算真正完成之後通知行程：l傳送信號給行程l將行程的某個變數設為特定的值l提供行程特

25、殊的系統呼叫來測試I/O運算的狀態l當應用程式採用非同步式I/O的時候，也必須在正常流程之外，另行加入I/O完成或失敗的測試與處理機制l在一般情況下，作業系統預設的是同步的I/O運算 46檔案存取控制檔案存取控制 l用來限制誰有權存取檔案，以及有哪些存取權利 l存取控制的設計可以分為兩部份：l決定有哪幾種可能的檔案運算：l讀取l寫入l刪除l表列l執行l變更存取權限l判斷某人是否有存取的權利：以使用者的身分為基礎 47如何簡化存取控制如何簡化存取控制 l假設在一個多使用者系統中共有L個使用者，M個檔案，且每個檔案有N種存取權，如果要做到完全的控制，就需要維護L*M*N項的管理資訊 l簡化方式：l

26、減少所需管控的權限種類（N值）l減少所需管控的使用者數量（L值）48課堂練習假設某系統共有50位使用者，3000筆檔案，且每個檔案有6種可能的運算方式，1.如果要做到完整的控制（使用者,檔案,運算方式），一共需要儲存多少項資訊？2.如果這個系統將使用者分為5個群組，則需要儲存的資訊（群組,檔案,運算方式）減少為多少項？3.如果這個系統再將檔案運算方式簡化為4種（新增、修改/刪除、執行、變更權限），可以再減少為多少項？49練習解答1.50*3000*6=900,0002.5*3000*6=90,0003.5*3000*4=60,00050實作討論-Unix的檔案存取控制 nUnix檔案的存取權限

27、：以r、w、與x分別代表讀取、寫入、與執行 nUnix將使用者分為三大類：q擁有者：檔案的建立者，或是經由chown命令指定為檔案擁有者 Saturn/home/usr/kevin:ls l chap1.txt-rw-r-r-1 kevin staff 7 Nov 16 18:06 chap1.txtSaturn/home/usr/kevin:chmod Jacky chap1.txtSaturn/home/usr/kevin:ls l chap1.txt-rw-r-r-1 jacky staff 7 Nov 16 18:06 chap1.txtq擁有群組：檔案所屬的群組，使用chgrp命令可

28、以變更檔案所屬的使用者群組 Saturn/home/usr/kevin:chgrp teacher chap1.txtSaturn/home/usr/kevin:ls l chap1.txt-rw-r-r-1 kevin teacher 7 Nov 16 18:06 chap1.txtq其他：除了上述兩種使用者外其餘所有使用者的存取權限 擁有者權限擁有群組權限其他者權限51著作權所有 旗標出版股份有限公司改變檔案的存取權限n假設Kevin的目錄下有兩個檔案chap1.txt與chap2.txt，以及兩個子目錄sample1與sample2：Saturn/home/usr/kevin:ls-l

29、total 8-rw-r-r-1 kevin staff 7 Nov 16 18:06 chap1.txt-rw-r-r-1 kevin staff 7 Nov 16 18:06 chap2.txtdrwxr-xr-x 2 kevin staff 512 Nov 16 18:06 sample1/drwxr-xr-x 2 kevin staff 512 Nov 16 18:06 sample2/n將chap1.txt改為只允許擁有者讀寫，將目錄sample1設為不允許其他人讀（列表）或執行（進入該目錄）Saturn/home/usr/kevin:chmod 600 chap1.txtSatur

30、n/home/usr/kevin:chmod 750 chap1.txtSaturn/home/usr/kevin:ls-l total 8-rw-1 kevin staff 7 Nov 16 18:06 chap1.txt-rw-r-r-1 kevin staff 7 Nov 16 18:06 chap2.txtdrwxr-x-2 kevin staff 512 Nov 16 18:06 sample1/drwxr-xr-x 2 kevin staff 512 Nov 16 18:06 sample2/52著作權所有 旗標出版股份有限公司課堂練習 在Unix系統中，如果要將一個檔案設為只有擁

31、有者能讀寫，其他人只能讀取，請問應該如何以八進位來表示它的權限？如果是要設定為所有人都能讀取與執行呢？53練習解答1.rw-r-r-1101001002=64482.r-xr-xr-x 1011011012=555854檔案的鎖定檔案的鎖定 l鎖定的範圍l鎖定的種類l讀取鎖定，又稱為共享鎖定l寫入鎖定，又稱為互斥鎖定l鎖定的形式l強制式鎖定l諮詢式鎖定55實作討論-Unix的檔案鎖定函式 nUnix提供flock函式，能夠針對整個檔案進行共享或互斥的諮詢式鎖定 qint flock(int fd,int operation);n如果要執行的是共享鎖定，則行程必須具有該檔案的讀取權利；如果要執行

32、互斥鎖定，則需要該檔案的寫入權利n在執行flock的時候，如果該檔案已經被別的行程鎖住，則行程會停在flock中，直到取得鎖定為止 n如果有行程不執行flock而直接讀寫該檔案，作業系統並不會阻止56著作權所有 旗標出版股份有限公司邏輯區塊的組成邏輯區塊的組成 l固定式的組成方式l不跨越區塊變動的組成方式 l允許跨區塊變動的組成方式 57固定式的組成方式：固定式的組成方式：l如果系統中的檔案都是由固定長度L的記錄所組成，且區塊的長度為B，則每個區塊中會放入B/L筆記錄l當區塊長度無法被記錄長度整除時，區塊的結尾就會剩下一些空間l如果需要存取某筆記錄，就可以先利用B/L的值計算它所屬的區塊位置，

33、再計算該筆記錄在區塊中的位移量記錄0區塊區塊0區塊區塊1圖6-15(a)固定式的組成方式 記錄1記錄2記錄3記錄4記錄5記錄6記錄7記錄8記錄958不跨越區塊變動的組成方式不跨越區塊變動的組成方式l如果系統提供可變長度的記錄，則儘可能將最多的完整記錄存放在單一區塊內，但是不允許記錄橫跨兩個區塊儲存l所有記錄的長度都必須小於區塊的長度l這種設計同樣會有內部碎片的問題，且作業系統無法單靠計算就找出所需的記錄位置，而必須有其他資訊的輔助 記錄0區塊區塊0區塊區塊1圖6-15(b)不跨越區塊變動的組成方式 記錄1記錄2記錄3記錄4記錄5記錄659允許跨區塊變動的組成方式允許跨區塊變動的組成方式l單一記

34、錄可以儲存在多個區塊中，因此，記錄的長度不會受到限制，並且不會有剩餘空間的問題l雖然空間利用率比較好，但是同樣無法單靠計算來找出所需的位置l即使是長度小於區塊長度的記錄，也可能會橫跨兩個區塊 記錄0區塊區塊0區塊區塊1圖6-15(c)允許跨區塊變動的組成方式 記錄1記錄2記錄3記錄4記錄560課堂練習 假設某檔案包含下列邏輯記錄，且每個邏輯區塊的大小為1024位元組，請說明在不跨越區塊與跨越區塊的配置方法下，這些邏輯記錄的位置邏輯記錄長度邏輯記錄長度02301580222032204660510061練習解答 不跨越區塊：區塊1：包含記錄0、1（共810B），剩餘214B 區塊2：包含記錄2、

35、3（共440B），剩餘584B 區塊3：包含記錄4、5（共760B），剩餘264B 跨越區塊：區塊1：包含記錄0、1、2的一部份，剩餘0B 區塊2：包含記錄2、3、4、5（共986B），剩餘38B62實體區塊的配置實體區塊的配置 l在將記錄組成邏輯區塊時，作業系統是將邏輯區塊視為是連續的空間，並且從0開始依序編號 l檔案系統的一項重要工作：為這些邏輯區塊安排它們的實體儲存位置l常用的磁碟空間配置方法：l連續式配置l鏈結式配置l索引式配置 63連續式配置連續式配置 l將檔案的邏輯區塊儲存在連續的實體區塊中：所有實體區塊配置方法中最簡單的一種l檔案目錄只需要儲存檔案在實體裝置的起始位址和長度即可l

36、資料的存取速度快l如何在可用空間中找到足夠存放所有資料的連續區塊：l先適法 l最適法 l最不適法 l在經過一段時間的檔案增刪之後，磁碟中可能會散佈許多的小洞（外部碎片）l磁碟重組：可以重新排列所有檔案的位置，把檔案分散的區塊重組為連續的磁碟區塊，並且將可用的空間聚集在一起64圖圖6-16 連續式配置範例連續式配置範例00010203040506070809101112131415161718192021222324先適法最適法最不適法包含兩個區塊的新檔案65圖6-17 Windows XP的磁碟重組工具66著作權所有 旗標出版股份有限公司鏈結式配置鏈結式配置 l將檔案放在不連續的磁碟空間中，然

37、後利用鏈結串列連在一起l每個實體區塊中除了存放邏輯區塊之外，還會存放一個指標，指向下個邏輯區塊的實際儲存位置l檔案的目錄或控制資訊表中會存放第一個邏輯區塊的儲存位置 l必須先取得第（N-1）個區塊的指標，才能知道第N個區塊的位置l優點：l可以增加空間配置上的彈性，避免外部碎片的問題l如果檔案長度增加，也不需要重新搬移檔案l可以利用磁碟重組來提升檔案存取速度。l缺點：l只能提供循序的檔案存取方式 67圖圖6-18 鏈結式配置範例鏈結式配置範例00010203040506070809101112131415161718192021222324檔案位置file1目錄68實作討論DOS的檔案配置 nM

38、S-DOS的檔案系統就是採取鏈結式配置n檔案配置表（FAT）是存放在磁碟分割區的開頭數個磁區中，包含檔案名稱、該檔案第一個區塊的編號、和它在實體磁碟中的位置n檔案的每個區塊中包含記錄下個區塊編號的指標，最後一個區塊的指標中則是特殊的檔案結束數值n未使用區塊的指標會設為0n當需要為檔案配置新的磁區時，只要搜尋到第一個指標為0的區塊，將新區塊的區塊編號放入原本最後一個區塊的指標中，再將新區塊的指標改為檔案結束數值即可69著作權所有 旗標出版股份有限公司索引式配置索引式配置 l鏈結式配置的一種變形：存放鏈結指標（索引）的區域稱為索引表格或索引區塊l目錄中存放的是指向索引表的指標，或者是索引表本身 l

39、大型檔案所需的索引總數可能超過單一索引區塊可容納的數量，常見的調整方式包括：l鏈結索引：將幾個索引區塊以指標連在一起l多層索引：建立一層以上的索引階層。假設區塊指標的長度為4 bytes在8KB的區塊中，每個區塊可以放置2K個索引（8K/4）兩層式索引一共可以存放2K*2K（4M）個區塊指標最大檔案長度為4M*8K=32GBl混合式索引：在索引區塊中同時提供直接索引與間接索引l小檔案：使用直接索引l大檔案：利用間接索引建立第二層或更多層的索引70圖圖6-19 索引式配置範例索引式配置範例00010203040506070809101112131415161718192021222324檔案索引

40、表file120目錄10210871索引區塊的管理索引區塊的管理 l在索引式配置下，每個邏輯區塊都必須有一個對應的索引項目 l當大型檔案所需的索引總數超過單一索引區塊可容納的數量時，常見的調整方式包括：l鏈結索引：將幾個索引區塊以指標連在一起l多層索引：建立一層以上的索引階層。假設區塊指標的長度為4 bytes在8KB的區塊中，每個區塊可以放置2K個索引（8K/4）兩層式索引一共可以存放2K*2K（4M）個區塊指標最大檔案長度為4M*8K=32GBl混合式索引：在索引區塊中同時提供直接索引與間接索引l小檔案：使用直接索引l大檔案：利用間接索引建立第二層或更多層的索引 72實作討論Unix的UF

41、S檔案系統 n許多Unix系統都支援的UFS檔案系統，就是採取混合式索引n它會在目錄中為每個檔案建立15個指標，如圖6-20q第1-12個指標是直接指標：n假設每個區塊為4KB，則長度小於48K（12個實體區塊）的檔案都可以直接存取q第13個指標指向一個間接索引區塊n假設每個索引的長度為4，則該區塊可容納1K個指標（4K/4）n檔案總長度將近4M位元組（4K*1K）q第14個指標指向一個雙重間接索引區塊n該區塊中的所有指標都是間接索引指標q第15個指標將會指向三重間接區塊n這種混合式的索引配置，可以說是兼顧了存取效率與檔案長度的彈性 73著作權所有 旗標出版股份有限公司圖6-20 混合式索引配

42、置範例 011121314磁碟直接指標第一層間接指標第二層間接指標第三層間接指標74著作權所有 旗標出版股份有限公司課堂練習 假設在UFS檔案系統下，每個區塊為4KB，且每個索引的長度為4B，請問它所能儲存的最大檔案長度為多少？75練習解答每個區塊為4KB，每個索引的長度為41個區塊可容納1K個指標第1-12個直接指標：12*4K=48KB第13個間接指標：指向1K個索引指標1K*4K=4MB第14個雙重間接指標：指向1K個間接索引指標1K*1M=4G第15個三重間接指標：指向1K個雙重間接索引區塊1K*4G=4T總長度=48K+4M+4G+4T 4T76可用空間的管理可用空間的管理 l系統會

43、維護一個可用空間串列，記錄目前尚未使用的所有可用磁碟區塊l當新增檔案時，作業系統會從串列中取出所需的區塊l當刪除檔案時，配置給該檔案的區塊則會被放回串列中 l建立可用空間串列的方法：l位元映射 l鏈結串列 l計數法 77位元映射位元映射l建立可用空間串列最簡單的一種方式，其中的每個位元循序對應到硬碟上的一個實體區塊l當該實體區塊是可用區塊時，就將其對應的位元值設為1l如果已被使用，則對應的位元就是0lEx.假設有個磁碟的第1、3、5、6、7個區塊是可用區塊，其餘是已被使用的區塊（從0開始編號），則位元映射的第一個位元組是二進位的01010111l如果磁碟太大，位元映射就會缺乏效率 l可以用叢集

44、為單位建立位元映射，以降低所需的位元數 78實作討論麥金塔的位元運算 n在位元映射的設計下，要找到某個區塊，必須經過特殊的位元運算n為了節省時間，許多電腦都為此提供了特殊的位元操作指令q例如Intel從80386、Motorola從68020（powerPC）開始，都提供了傳回暫存器中第一個非0位元位置的指令n麥金塔作業系統會循序檢查位元映射中的每個字組，以找出第一個可用區塊（第一個非0位元），並使用下面的公式來換算出這個區塊的編號：每個字組的位元數*為0的字組總數+第1個非0位元在字組的位置n假設每個字組有32位元，且位元映射中的前100個字組值都是0，第101個字組的第3個位元為1，則第1

45、個可用區塊是：32*100+3=3203 第3203個區塊（區塊編號3202）79著作權所有 旗標出版股份有限公司鏈結串列鏈結串列l利用鏈結將所有可用區塊連在一起l當作業系統需要可用區塊時，只需要利用開頭指標取出串列開頭的第一個區塊，然後將開頭指標移到第二個區塊即可 l同樣可以利用叢集做為資料存取的基本單位80計數法計數法l只記錄每段可用空間的開頭位置，與這段空間中的區塊總數l可以很容易搜尋到所需要的磁碟空間l如果磁碟中的可用空間夠集中時，所需的資訊儲存空間會遠小於鏈結串列所有指標所佔用的空間l如果磁碟的可用空間太過分散的時候，計數法反而會造成空間的浪費 81圖圖6-21 以計數法記錄圖以計數法記錄圖6-19的可用空間的可用空間00010203040506070809101112131415161718192021222324索引起始區塊總數11325331174232可用空間列表82