操作系統(tǒng)-第八章課件

操作系統(tǒng)第八章文件系統(tǒng)1操作系統(tǒng)第八章文件系統(tǒng)1第八章文件系統(tǒng)文件系統(tǒng)的概念文件的邏輯結(jié)構(gòu)與存取方法文件的物理結(jié)構(gòu)與存儲(chǔ)設(shè)備文件存儲(chǔ)空間管理文件目錄管理2文件存取控制文件的使用文件系統(tǒng)的層次模型總結(jié)第八章文件系統(tǒng)文件系統(tǒng)的概念2文件存取控制文件系統(tǒng)的概念文件系統(tǒng)的引入文件與文件系統(tǒng)的概念文件的分類3文件系統(tǒng)的概念文件系統(tǒng)的引入3文件系統(tǒng)的概念文件系統(tǒng)的引入操作系統(tǒng)對(duì)計(jì)算機(jī)的管理：硬件資源管理：CPU、存儲(chǔ)器和設(shè)備的管理；軟件資源管理：系統(tǒng)程序、工具軟件、庫函數(shù)和用戶程序與數(shù)據(jù)。4編輯程序、編譯程序與鏈接程序等。文件系統(tǒng)的概念文件系統(tǒng)的引入4編輯程序、編譯程序與鏈接程序文件系統(tǒng)的概念文件系統(tǒng)的引入目的：如何對(duì)軟件資源（程序和數(shù)據(jù)）進(jìn)行透明地快速存?。客该鳎簩?duì)文件的操作與文件的物理結(jié)構(gòu)和存取介質(zhì)無關(guān)。對(duì)文件的操作只需要給定的一個(gè)代表程序和數(shù)據(jù)的名稱->文件名5文件系統(tǒng)的概念文件系統(tǒng)的引入5文件系統(tǒng)的概念文件系統(tǒng)的引入文件系統(tǒng)需要完成的工作：必須對(duì)磁盤等存儲(chǔ)空間進(jìn)行統(tǒng)一管理，包括分配和回收。為用戶提供一個(gè)可見的文件邏輯結(jié)構(gòu)，獨(dú)立于物理設(shè)備，以實(shí)現(xiàn)按名存取。實(shí)現(xiàn)文件的物理結(jié)構(gòu)：在存儲(chǔ)設(shè)備上按照一定順序存放，方便存放和加工信息。完成對(duì)文件信息的查找。完成對(duì)文件的共享和保護(hù)。6文件系統(tǒng)的概念文件系統(tǒng)的引入6文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件：一組賦名的相關(guān)聯(lián)字符流集合。無結(jié)構(gòu)的流式文件。（源程序和目標(biāo)代碼）由相關(guān)聯(lián)記錄（一個(gè)有意義的信息單位）的集合。記錄式文件。（數(shù)據(jù)庫）記錄：N（N>1）個(gè)字節(jié)組成的具有特定意義的信息單位。7文件系統(tǒng)的概念文件與文件系統(tǒng)的概念7文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件：設(shè)備與文件的統(tǒng)一管理的問題：從字符流的角度出發(fā)，設(shè)備可以看成是特殊的文件。簡化了設(shè)備管理與文件系統(tǒng)的接口設(shè)計(jì)。文件名問題：由英文字母、數(shù)字和其他字符組成。區(qū)分英文字母大小寫。首字母建議用字母，特殊字符建議用“_”替代。8文件系統(tǒng)的概念文件與文件系統(tǒng)的概念8文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件系統(tǒng)：操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)。功能：為用戶建立、撤銷、讀寫、修改和復(fù)制文件，對(duì)文件按名存取，和存取控制。9文件系統(tǒng)的概念文件與文件系統(tǒng)的概念9文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件系統(tǒng)的特點(diǎn)：友好的用戶接口，用戶不必關(guān)心文件的物理位置。按文件名存取，用戶不必關(guān)心文件的物理結(jié)構(gòu)。某些文件可以被多個(gè)用戶共享。文件系統(tǒng)的存儲(chǔ)介質(zhì)容量大，磁盤，光盤等。10文件系統(tǒng)的概念文件與文件系統(tǒng)的概念10文件系統(tǒng)的概念文件的分類按文件的性質(zhì)和用途系統(tǒng)文件：由操作系統(tǒng)核心和系統(tǒng)程序、數(shù)據(jù)組成，用戶只能通過系統(tǒng)調(diào)用執(zhí)行它們。庫文件：由各種標(biāo)準(zhǔn)子程序庫組成，用戶可以讀取、執(zhí)行，但不能修改。用戶文件：由用戶的各種程序和數(shù)據(jù)庫組成，只能由文件的所有者或者所有者授權(quán)的用戶使用。11文件系統(tǒng)的概念文件的分類11文件系統(tǒng)的概念文件的分類按文件的組織普通文件：組織格式為系統(tǒng)中規(guī)定的最一般格式的文件，例如字符流組成的文件。目錄文件：由文件的目錄信息構(gòu)成的特殊文件，用于檢索普通文件的。特殊文件：輸入輸出設(shè)備，與設(shè)備管理程序緊密相連。12文件系統(tǒng)的概念文件的分類12文件系統(tǒng)的概念文件的分類按信息的流向：輸入文件、輸出文件和輸入輸出文件。按保護(hù)級(jí)別：只讀文件、讀寫文件、可執(zhí)行文件和不保護(hù)文件。13文件系統(tǒng)的概念文件的分類13邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是用戶可見的結(jié)構(gòu)。邏輯結(jié)構(gòu)設(shè)計(jì)的原則：最少的變動(dòng)最短的時(shí)間最小的體積最便捷的操作14邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)14邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)字符流的無結(jié)構(gòu)文件：管理簡單，查找困難。適合于對(duì)基本信息單位操作不多的文件。記錄式的有結(jié)構(gòu)文件：方便用戶對(duì)記錄進(jìn)行修改、追加、查找和管理等操作。15邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)15邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)記錄：一個(gè)具有特定意義的信息單位組成：記錄在文件中的邏輯地址與記錄名對(duì)應(yīng)的一組關(guān)鍵字、屬性和屬性值。常用的記錄式結(jié)構(gòu)文件：連續(xù)結(jié)構(gòu)、多重結(jié)構(gòu)、轉(zhuǎn)置結(jié)構(gòu)和順序結(jié)構(gòu)。16邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)16邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)連續(xù)結(jié)構(gòu)把記錄按生成的先后順序排列的結(jié)構(gòu)。特點(diǎn)：適用性強(qiáng)，適用于所有文件。記錄的排列順序與記錄的內(nèi)容無關(guān)，有利于記錄的追加和變更。對(duì)關(guān)鍵字搜索時(shí)，需要遍歷全體文件，搜索性能差。17邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)17邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)多重結(jié)構(gòu)把記錄按關(guān)鍵字和記錄名排列成行列式的結(jié)構(gòu)。特點(diǎn)：同一個(gè)關(guān)鍵字可以同時(shí)屬于不同的記錄。對(duì)關(guān)鍵字搜索速度快。18邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)18邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)多重結(jié)構(gòu)優(yōu)化空間：將行列式中0項(xiàng)去掉，改以多個(gè)隊(duì)列存儲(chǔ)。19邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)19邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)轉(zhuǎn)置結(jié)構(gòu)將每個(gè)關(guān)鍵字指向記錄的指針保存在關(guān)鍵字的域中。特點(diǎn)：適合于根據(jù)關(guān)鍵字的記錄搜索。20邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)20邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)順序結(jié)構(gòu)把文件中的關(guān)鍵字按規(guī)定的順序排列起來。特點(diǎn)：適合按某種優(yōu)先順序來搜索或追加、刪除記錄。例子：《人民日?qǐng)?bào)》新聞按登載日期的時(shí)間先后順序組成文件，如果想要搜索某一時(shí)期的歷史事件，只需要將時(shí)間范圍縮小到那一時(shí)期即可。21邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)21邏輯結(jié)構(gòu)和存取方法存取方法文件的存?。赫业轿募膬?nèi)容所在的邏輯地址。用途：用戶通過文件的存取來完成對(duì)文件的修改、追加和搜索等操作。三種方式：順序存取法、隨機(jī)存取法和按關(guān)鍵字存取法。22邏輯結(jié)構(gòu)和存取方法存取方法22邏輯結(jié)構(gòu)和存取方法存取方法順序存取法按照文件的邏輯地址順序存取。記錄式文件：按記錄的排列順序來存取，當(dāng)前記錄Ri，下一次讀取為相鄰記錄Ri+1。字符流文件：存取指針順序增長變化，當(dāng)前指向P，下一次讀取指向P+len，len為當(dāng)前讀取字符串長度。23邏輯結(jié)構(gòu)和存取方法存取方法23邏輯結(jié)構(gòu)和存取方法存取方法隨機(jī)存取法根據(jù)記錄的編號(hào)來存取文件的任意一個(gè)記錄。根據(jù)存取命令自如地移動(dòng)讀寫指針。24邏輯結(jié)構(gòu)和存取方法存取方法24邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取文件的存取根據(jù)給定的關(guān)鍵字或記錄名進(jìn)行的。做法：搜索要進(jìn)行存取的記錄的邏輯位置；將邏輯位置轉(zhuǎn)換到相應(yīng)的物理地址，然后進(jìn)行存取。適用于復(fù)雜的文件系統(tǒng)（數(shù)據(jù)庫管理系統(tǒng)）25邏輯結(jié)構(gòu)和存取方法存取方法25邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取搜索的過程：搜索算法：線性搜索法散列法二分搜索法26邏輯結(jié)構(gòu)和存取方法存取方法26邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取線性搜索法：從頭開始順序查找時(shí)間復(fù)雜度：O(N)27邏輯結(jié)構(gòu)和存取方法存取方法27邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取散列法：定義一個(gè)散列函數(shù)h(k)，使得對(duì)于給定的關(guān)鍵字k，散列函數(shù)都能將k變換得到其邏輯地址。散列沖突：對(duì)于k1!=k2，有h(k1)=h(k2)=A。兩個(gè)關(guān)鍵字的散列變換沖突。時(shí)間復(fù)雜度：O(1)28邏輯結(jié)構(gòu)和存取方法存取方法28邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取散列沖突的解決方法開放地址法：當(dāng)h(k1)產(chǎn)生的值h1沖突，再計(jì)算一個(gè)值h2,如果h2沖突，再計(jì)算一個(gè)直到不沖突為止hihi=(h(k1)+di)%tt為搜索長度di=a*i或c*(i*i)或隨機(jī)數(shù)。線性散列/平方散列/隨機(jī)散列29邏輯結(jié)構(gòu)和存取方法存取方法29邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取二分搜索法典型的二分查找時(shí)間復(fù)雜度：O(logN)條件：已排序的對(duì)象序列。30邏輯結(jié)構(gòu)和存取方法存取方法30物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的存取在搜索到目標(biāo)記錄的邏輯地址后要確定物理地址。邏輯地址到物理地址的映射和文件的物理結(jié)構(gòu)緊密相連。文件系統(tǒng)的存取方法和邏輯結(jié)構(gòu)也與物理存儲(chǔ)介質(zhì)有關(guān)。文件的物理結(jié)構(gòu)和文件的存儲(chǔ)設(shè)備。31物理結(jié)構(gòu)和存儲(chǔ)設(shè)備31物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)是指文件在存儲(chǔ)設(shè)備上的存放方法。文件信息的邏輯地址到物理地址的變換是有文件的物理結(jié)構(gòu)決定的。文件的存儲(chǔ)設(shè)備通常劃分為大小相等的若干物理塊。常用的文件物理結(jié)構(gòu)包括：連續(xù)文件、串聯(lián)文件和索引文件。32物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)32物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)連續(xù)文件邏輯上連續(xù)的文件信息依次存放到物理塊中。33物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)33物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)連續(xù)文件優(yōu)點(diǎn)：地址變換簡單，知道了起址和長度就能很快進(jìn)行物理存取。缺點(diǎn)：文件建立時(shí)確定了文件長度，不能動(dòng)態(tài)增長；刪除后容易留下無法使用的零頭空間。34物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)34物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)串聯(lián)文件

用非連續(xù)的物理塊存放文件信息，每個(gè)物理塊設(shè)有指向后繼物理塊的指針。35物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)35物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)串聯(lián)文件特點(diǎn)：建立文件時(shí)不需要指明長度，只需第一個(gè)塊號(hào)?？梢詣?dòng)態(tài)增長，增刪、插入操作容易實(shí)現(xiàn)。搜索效率低，鏈表式搜索需要遍歷整個(gè)鏈。36物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)36物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)索引文件系統(tǒng)為每個(gè)文件建立一張索引表，表中記錄邏輯塊和物理塊的對(duì)應(yīng)。37物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)37物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)索引文件當(dāng)一個(gè)索引表大于一個(gè)物理塊，如何存放？多重索引。38物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)38物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)索引文件索引結(jié)構(gòu)的特點(diǎn)：適合順序存取也適合隨機(jī)存取。增加了索引表增加了存儲(chǔ)空間開銷。每次讀取文件需要訪問磁盤兩次。（可以將索引表放入內(nèi)存）39物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)39物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備順序存取存儲(chǔ)設(shè)備——磁帶直接存取存儲(chǔ)設(shè)備——磁盤磁盤設(shè)備允許文件系統(tǒng)直接存取磁盤上的任意物理塊。40物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備40物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤硬盤結(jié)構(gòu)包括：盤片、磁頭、盤片主軸、控制電機(jī)、磁頭控制器、數(shù)據(jù)轉(zhuǎn)換器、接口、緩存等幾個(gè)部份。所有的盤片（一般硬盤里有多個(gè)盤片，盤片之間平行）都固定在一個(gè)主軸上。在每個(gè)盤片的存儲(chǔ)面上都有一個(gè)磁頭，磁頭與盤片之間的距離很?。ㄋ詣×艺饎?dòng)容易損壞），磁頭連在一個(gè)磁頭控制器上，統(tǒng)一控制各個(gè)磁頭的運(yùn)動(dòng)。磁頭沿盤片的半徑方向動(dòng)作，而盤片則按照指定方向高速旋轉(zhuǎn)，這樣磁頭就可以到達(dá)盤片上的任意位置了。41物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備41物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤42物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備42物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤的容量：磁頭數(shù)×磁道(柱面)數(shù)×每道扇區(qū)數(shù)×每扇區(qū)字節(jié)數(shù)磁頭（head）數(shù)：每個(gè)盤片一般有上下兩面，分別對(duì)應(yīng)1個(gè)磁頭，共2個(gè)磁頭；磁道（track）數(shù)：磁道是從盤片外圈往內(nèi)圈編號(hào)0磁道，1磁道...，靠近主軸的同心圓用于?？看蓬^，不存儲(chǔ)數(shù)據(jù)；柱面（cylinder）數(shù)：同磁道數(shù)量；扇區(qū)（sector）數(shù)：每個(gè)磁道都別切分成很多扇形區(qū)域，每道的扇區(qū)數(shù)量相同；圓盤（platter）數(shù)：就是盤片的數(shù)量。 43物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備43物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備44物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備44物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤的數(shù)據(jù)定位：LBA(邏輯扇區(qū)號(hào))=磁頭數(shù)×每磁道扇區(qū)數(shù)×當(dāng)前所在柱面號(hào)+每磁道扇區(qū)數(shù)×當(dāng)前所在磁頭號(hào)+當(dāng)前所在扇區(qū)號(hào)–1例如：CHS=0/0/1，則根據(jù)公式LBA=255×63×0+63×0+1–1=0物理0柱面0磁頭1扇區(qū)，是邏輯0扇區(qū)45物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備45文件存儲(chǔ)空間管理文件的存儲(chǔ)設(shè)備以大小相等的物理塊為單位。文件存儲(chǔ)空間的管理實(shí)質(zhì)是空閑塊的組織和管理問題。有3種不同的空閑塊管理方法：空閑文件目錄、空閑塊鏈和位示圖。46文件存儲(chǔ)空間管理46文件存儲(chǔ)空間管理空閑文件目錄文件存儲(chǔ)設(shè)備中的空閑塊的塊號(hào)統(tǒng)一放在一個(gè)空閑文件目錄的物理塊中。每個(gè)表項(xiàng)存儲(chǔ)一個(gè)空閑區(qū)，一個(gè)空閑區(qū)包括一個(gè)或多個(gè)空閑塊?？臻e文件目錄管理的空閑區(qū)的申請(qǐng)和釋放類似于內(nèi)存空閑區(qū)的管理。47文件存儲(chǔ)空間管理空閑文件目錄47文件存儲(chǔ)空間管理空閑塊鏈空閑塊鏈把文件存儲(chǔ)設(shè)備上的所有空閑塊鏈接在一起。申請(qǐng)空間時(shí)，從鏈表頭部摘取所需要的空閑塊，然后調(diào)整頭指針。釋放空間時(shí)，新的空閑塊插入鏈尾上?？臻e塊的鏈接方式：按空閑區(qū)大小順序鏈接、按釋放先后順序鏈接和成組鏈接。48文件存儲(chǔ)空間管理空閑塊鏈48文件存儲(chǔ)空間管理空閑塊鏈成組鏈接法前兩種方式在增加或移動(dòng)空閑塊時(shí)需要對(duì)空閑塊鏈做較大的調(diào)整，系統(tǒng)開銷大?；驹恚核锌臻e塊50塊一組，組的劃分從后向前，每組的第一塊用來存放前一組的各塊的塊號(hào)和總塊數(shù)。49文件存儲(chǔ)空間管理空閑塊鏈49文件存儲(chǔ)空間管理空閑塊鏈成組鏈接法第一組前面沒有其他組，所以第一組為49塊；最后一組的塊數(shù)可能不到50塊，因?yàn)榭偟膲K數(shù)可能不是50的倍數(shù)。最后一組的各塊號(hào)和總塊數(shù)存放在文件資源表中。50文件存儲(chǔ)空間管理空閑塊鏈50文件存儲(chǔ)空間管理空閑塊鏈成組鏈接法分配和釋放過程51文件存儲(chǔ)空間管理空閑塊鏈51文件存儲(chǔ)空間管理位示圖從系統(tǒng)內(nèi)存中劃分若干個(gè)字節(jié)，為每個(gè)文件存儲(chǔ)設(shè)備建立一張位示圖，反映各設(shè)備的使用情況。位示圖中的每個(gè)比特位對(duì)應(yīng)一個(gè)物理塊的分配情況，0表示未分配，1表示已分配。位示圖法分配與回收時(shí)不需要再文件存儲(chǔ)設(shè)備上查找文件目錄或鏈接塊號(hào)，即不需要啟動(dòng)外設(shè)即可完成，因此速度快。52文件存儲(chǔ)空間管理位示圖52文件目錄管理文件名及其結(jié)構(gòu)信息需要按一定的組織結(jié)構(gòu)排列，以方便搜索查找。文件目錄管理：存儲(chǔ)空間有效利用、快速搜索、解決文件命名沖突以及文件共享。文件的組成文件目錄的介紹便于共享的文件目錄目錄管理53文件目錄管理文件名及其結(jié)構(gòu)信息需要按一定的組織結(jié)構(gòu)排列，以文件目錄管理文件的組成文件說明和文件體文件體：文件本身的信息文件說明：文件控制塊（FCB）文件名、與文件名相對(duì)應(yīng)的文件內(nèi)部表示以及在文件存儲(chǔ)設(shè)備上的第一個(gè)物理塊地址。文件說明組成文件目錄54文件目錄管理文件的組成54文件目錄管理文件目錄文件目錄：單級(jí)目錄、二級(jí)目錄和多級(jí)目錄單級(jí)目錄：文件系統(tǒng)為所有文件建立一張目錄表，每個(gè)文件占用一個(gè)表項(xiàng)。目錄表存放在存儲(chǔ)設(shè)備的固定區(qū)域，系統(tǒng)啟動(dòng)后調(diào)入內(nèi)存。文件系統(tǒng)通過該表完成對(duì)文件的創(chuàng)建、搜索和刪除等操作。55文件目錄管理文件目錄55文件目錄管理文件目錄單級(jí)目錄的讀寫處理過程56文件目錄管理文件目錄56文件目錄管理文件目錄單級(jí)目錄的問題：命名沖突問題：單表目錄中只能按連續(xù)結(jié)構(gòu)或順序結(jié)構(gòu)存放，文件名與文件一一對(duì)應(yīng)，相同文件名被視為同一文件。搜索速度問題：單表目錄每次搜索需要對(duì)所有文件遍歷，因此速度慢。57文件目錄管理文件目錄57文件目錄管理文件目錄二級(jí)目錄各個(gè)文件的說明信息被組織成目錄文件，且以用戶為單位化為不同的組。MFD主目錄：不同組名的存取控制信息存放的目錄。UFD用戶文件目錄：用戶文件說明所組成。58文件目錄管理文件目錄58文件目錄管理文件目錄二級(jí)目錄59文件目錄管理文件目錄59文件目錄管理文件目錄二級(jí)目錄同名沖突問題：可以輕易解決，因?yàn)橥煌M。文件共享問題：可以通過將共享的文件設(shè)置相應(yīng)的共享指針。查找速度：n個(gè)文件劃分成m個(gè)子集，r為每個(gè)用戶子集的文件數(shù)，則n<=m*r(存在共享文件）。查找速度有n變?yōu)閙+r，一般m+r<=n，因此查找速度>單級(jí)目錄。60文件目錄管理文件目錄60文件目錄管理文件目錄多級(jí)目錄：二級(jí)目錄層次關(guān)系的推廣61文件目錄管理文件目錄61文件目錄管理文件目錄多級(jí)目錄特點(diǎn)：層次清楚，便于管理。解決了文件的重名沖突問題。查找速度塊。62文件目錄管理文件目錄62文件目錄管理便于共享的文件目錄共享文件的必要性：節(jié)約存儲(chǔ)空間。實(shí)現(xiàn)文件共享的3種方法：繞道法鏈接法基本文件目錄表（BFD）63文件目錄管理便于共享的文件目錄63文件目錄管理便于共享的文件目錄繞道法根據(jù)文件的固有名，從當(dāng)前目錄出發(fā)向上返回到與共享文件所在路徑的交叉點(diǎn)，再順序下訪。固有名：目錄名+文件名繞道法需要繞彎路訪問多級(jí)目錄，搜索效率不高。64文件目錄管理便于共享的文件目錄64文件目錄管理便于共享的文件目錄鏈接法在相應(yīng)目錄表之間進(jìn)行鏈接，一個(gè)目錄中的鏈指針指向被共享文件所在目錄。65文件目錄管理便于共享的文件目錄65文件目錄管理便于共享的文件目錄基本文件目錄表66文件目錄管理便于共享的文件目錄66文件目錄管理目錄管理BFD,MFD,SFD等構(gòu)成了目錄文件。目錄文件的存放位置？外存文件存儲(chǔ)設(shè)備中：每次訪問文件需要多次讀寫外部文件存儲(chǔ)設(shè)備，耗時(shí)嚴(yán)重。內(nèi)存中：系統(tǒng)啟動(dòng)時(shí)讀入內(nèi)存，將消耗較大內(nèi)存。折中的辦法：把當(dāng)前正在使用的目錄表copy到內(nèi)存中。67文件目錄管理目錄管理67文件目錄管理目錄管理將當(dāng)前使用的文件目錄表copy到內(nèi)存需要完成：把有關(guān)的目錄文件復(fù)制到內(nèi)存指定區(qū)域（打開文件fopen）用戶不再訪問時(shí)，刪除有關(guān)文件的目錄文件（關(guān)閉文件fclose）fopen，fclose以系統(tǒng)調(diào)用的方式提供。68文件目錄管理目錄管理68文件目錄管理目錄管理打開文件的步驟：1.把主目錄MFD中相應(yīng)的表項(xiàng)copy到內(nèi)存；2.根據(jù)1得到的標(biāo)識(shí)符對(duì)應(yīng)的BDF的表項(xiàng)復(fù)制到內(nèi)存；3.搜索2提供的SFD，知道找到文件名對(duì)應(yīng)的標(biāo)識(shí)符ID；4.根據(jù)3得到的標(biāo)識(shí)符查找BDF，把相應(yīng)的表項(xiàng)復(fù)制到內(nèi)存。69文件目錄管理目錄管理69文件存取控制

文件的存取控制：一個(gè)用戶對(duì)文件的使用權(quán)限，即讀、寫、執(zhí)行的許可權(quán)問題。對(duì)擁有讀、寫、執(zhí)行權(quán)限的用戶，允許對(duì)文件進(jìn)行相應(yīng)操作。對(duì)沒有讀、寫、執(zhí)行權(quán)限的用戶，禁止對(duì)文件進(jìn)行相應(yīng)操作。防止一個(gè)用戶冒充其他用戶對(duì)文件進(jìn)行存取。防止擁有存取權(quán)限的用戶誤用文件。70文件存取控制文件的存取控制：70文件存取控制

文件的存取控制的步驟：審定用戶的存取權(quán)限；比較用戶權(quán)限與用戶的本次存取要求是否一致；將存取要求和被訪問的文件的保密性比較，查看是否有沖突。驗(yàn)證用戶存取操作的4中方式：存取控制矩陣、存取控制表、口令和密碼術(shù)。71文件存取控制文件的存取控制的步驟：71文件存取控制

存取控制矩陣二維矩陣：一維用戶，一維文件，每個(gè)矩陣元素為相應(yīng)的權(quán)限。特點(diǎn)：占用空間大，查找速度慢。72文件名

用戶WangLeeZhangA.CRWEERWEB.CRWRRWED.CRWWEE.CRWRW文件存取控制存取控制矩陣72文件名文件存取控制

存取控制表每個(gè)文件都有一張存取控制表，按權(quán)限將用戶分組。文件打開時(shí)，存取控制表copy到內(nèi)存中，以保證高效驗(yàn)證。73用戶組

文件A.CZhangRWEA組RWB組REWangR文件存取控制存取控制表73用戶組文件存取控制

口令方式為每一個(gè)文件設(shè)置一個(gè)口令，訪問文件時(shí)先驗(yàn)證口令?？诹畲嬖谖募f明中；共享的實(shí)現(xiàn)通過分享口令；口令的占用空間小，驗(yàn)證耗時(shí)短；口令的保密性弱，修改權(quán)限不便。74文件存取控制口令方式74文件存取控制

密碼方式密碼方式與口令方式的不同：編解碼的代碼鍵并沒有存放在系統(tǒng)中，而是由用戶掌握。密碼方式的特點(diǎn)：保密性高，編解碼耗時(shí)。75文件存取控制密碼方式75文件的使用文件系統(tǒng)提供的幾種系統(tǒng)調(diào)用關(guān)于設(shè)置和用戶對(duì)文件的存取權(quán)限的服務(wù)；關(guān)于建立、改變和刪除目錄的服務(wù)；關(guān)于文件共享、設(shè)置訪問路徑的服務(wù)；創(chuàng)建、打開、讀寫、關(guān)閉以及撤銷文件的服務(wù)。chmod、mkdir、cd、rmdir、create、open、write、close等76文件的使用文件系統(tǒng)提供的幾種系統(tǒng)調(diào)用76文件系統(tǒng)的層次模型定義：層次結(jié)構(gòu)按照系統(tǒng)提供的功能劃分各種不同的層次，下層為上層提供服務(wù)，上層使用下層的功能。特點(diǎn)：上下層無需了解對(duì)方的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)方法，只需要關(guān)心接口。系統(tǒng)出錯(cuò)時(shí)，容易查錯(cuò)和調(diào)整。77文件系統(tǒng)的層次模型定義：77文件系統(tǒng)的層次模型Madnick的8層文件系統(tǒng)78文件系統(tǒng)的層次模型Madnick的8層文件系統(tǒng)78總結(jié)與作業(yè)總結(jié)：文件和文件系統(tǒng)的基本概念文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)存儲(chǔ)空間的管理方法文件目錄（文件名與物理地址之間的映射）作業(yè)：8.1479總結(jié)與作業(yè)總結(jié)：79操作系統(tǒng)第八章文件系統(tǒng)80操作系統(tǒng)第八章文件系統(tǒng)1第八章文件系統(tǒng)文件系統(tǒng)的概念文件的邏輯結(jié)構(gòu)與存取方法文件的物理結(jié)構(gòu)與存儲(chǔ)設(shè)備文件存儲(chǔ)空間管理文件目錄管理81文件存取控制文件的使用文件系統(tǒng)的層次模型總結(jié)第八章文件系統(tǒng)文件系統(tǒng)的概念2文件存取控制文件系統(tǒng)的概念文件系統(tǒng)的引入文件與文件系統(tǒng)的概念文件的分類82文件系統(tǒng)的概念文件系統(tǒng)的引入3文件系統(tǒng)的概念文件系統(tǒng)的引入操作系統(tǒng)對(duì)計(jì)算機(jī)的管理：硬件資源管理：CPU、存儲(chǔ)器和設(shè)備的管理；軟件資源管理：系統(tǒng)程序、工具軟件、庫函數(shù)和用戶程序與數(shù)據(jù)。83編輯程序、編譯程序與鏈接程序等。文件系統(tǒng)的概念文件系統(tǒng)的引入4編輯程序、編譯程序與鏈接程序文件系統(tǒng)的概念文件系統(tǒng)的引入目的：如何對(duì)軟件資源（程序和數(shù)據(jù)）進(jìn)行透明地快速存??？透明：對(duì)文件的操作與文件的物理結(jié)構(gòu)和存取介質(zhì)無關(guān)。對(duì)文件的操作只需要給定的一個(gè)代表程序和數(shù)據(jù)的名稱->文件名84文件系統(tǒng)的概念文件系統(tǒng)的引入5文件系統(tǒng)的概念文件系統(tǒng)的引入文件系統(tǒng)需要完成的工作：必須對(duì)磁盤等存儲(chǔ)空間進(jìn)行統(tǒng)一管理，包括分配和回收。為用戶提供一個(gè)可見的文件邏輯結(jié)構(gòu)，獨(dú)立于物理設(shè)備，以實(shí)現(xiàn)按名存取。實(shí)現(xiàn)文件的物理結(jié)構(gòu)：在存儲(chǔ)設(shè)備上按照一定順序存放，方便存放和加工信息。完成對(duì)文件信息的查找。完成對(duì)文件的共享和保護(hù)。85文件系統(tǒng)的概念文件系統(tǒng)的引入6文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件：一組賦名的相關(guān)聯(lián)字符流集合。無結(jié)構(gòu)的流式文件。（源程序和目標(biāo)代碼）由相關(guān)聯(lián)記錄（一個(gè)有意義的信息單位）的集合。記錄式文件。（數(shù)據(jù)庫）記錄：N（N>1）個(gè)字節(jié)組成的具有特定意義的信息單位。86文件系統(tǒng)的概念文件與文件系統(tǒng)的概念7文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件：設(shè)備與文件的統(tǒng)一管理的問題：從字符流的角度出發(fā)，設(shè)備可以看成是特殊的文件。簡化了設(shè)備管理與文件系統(tǒng)的接口設(shè)計(jì)。文件名問題：由英文字母、數(shù)字和其他字符組成。區(qū)分英文字母大小寫。首字母建議用字母，特殊字符建議用“_”替代。87文件系統(tǒng)的概念文件與文件系統(tǒng)的概念8文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件系統(tǒng)：操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)。功能：為用戶建立、撤銷、讀寫、修改和復(fù)制文件，對(duì)文件按名存取，和存取控制。88文件系統(tǒng)的概念文件與文件系統(tǒng)的概念9文件系統(tǒng)的概念文件與文件系統(tǒng)的概念文件系統(tǒng)的特點(diǎn)：友好的用戶接口，用戶不必關(guān)心文件的物理位置。按文件名存取，用戶不必關(guān)心文件的物理結(jié)構(gòu)。某些文件可以被多個(gè)用戶共享。文件系統(tǒng)的存儲(chǔ)介質(zhì)容量大，磁盤，光盤等。89文件系統(tǒng)的概念文件與文件系統(tǒng)的概念10文件系統(tǒng)的概念文件的分類按文件的性質(zhì)和用途系統(tǒng)文件：由操作系統(tǒng)核心和系統(tǒng)程序、數(shù)據(jù)組成，用戶只能通過系統(tǒng)調(diào)用執(zhí)行它們。庫文件：由各種標(biāo)準(zhǔn)子程序庫組成，用戶可以讀取、執(zhí)行，但不能修改。用戶文件：由用戶的各種程序和數(shù)據(jù)庫組成，只能由文件的所有者或者所有者授權(quán)的用戶使用。90文件系統(tǒng)的概念文件的分類11文件系統(tǒng)的概念文件的分類按文件的組織普通文件：組織格式為系統(tǒng)中規(guī)定的最一般格式的文件，例如字符流組成的文件。目錄文件：由文件的目錄信息構(gòu)成的特殊文件，用于檢索普通文件的。特殊文件：輸入輸出設(shè)備，與設(shè)備管理程序緊密相連。91文件系統(tǒng)的概念文件的分類12文件系統(tǒng)的概念文件的分類按信息的流向：輸入文件、輸出文件和輸入輸出文件。按保護(hù)級(jí)別：只讀文件、讀寫文件、可執(zhí)行文件和不保護(hù)文件。92文件系統(tǒng)的概念文件的分類13邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是用戶可見的結(jié)構(gòu)。邏輯結(jié)構(gòu)設(shè)計(jì)的原則：最少的變動(dòng)最短的時(shí)間最小的體積最便捷的操作93邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)14邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)字符流的無結(jié)構(gòu)文件：管理簡單，查找困難。適合于對(duì)基本信息單位操作不多的文件。記錄式的有結(jié)構(gòu)文件：方便用戶對(duì)記錄進(jìn)行修改、追加、查找和管理等操作。94邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)15邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)記錄：一個(gè)具有特定意義的信息單位組成：記錄在文件中的邏輯地址與記錄名對(duì)應(yīng)的一組關(guān)鍵字、屬性和屬性值。常用的記錄式結(jié)構(gòu)文件：連續(xù)結(jié)構(gòu)、多重結(jié)構(gòu)、轉(zhuǎn)置結(jié)構(gòu)和順序結(jié)構(gòu)。95邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)16邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)連續(xù)結(jié)構(gòu)把記錄按生成的先后順序排列的結(jié)構(gòu)。特點(diǎn)：適用性強(qiáng)，適用于所有文件。記錄的排列順序與記錄的內(nèi)容無關(guān)，有利于記錄的追加和變更。對(duì)關(guān)鍵字搜索時(shí)，需要遍歷全體文件，搜索性能差。96邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)17邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)多重結(jié)構(gòu)把記錄按關(guān)鍵字和記錄名排列成行列式的結(jié)構(gòu)。特點(diǎn)：同一個(gè)關(guān)鍵字可以同時(shí)屬于不同的記錄。對(duì)關(guān)鍵字搜索速度快。97邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)18邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)多重結(jié)構(gòu)優(yōu)化空間：將行列式中0項(xiàng)去掉，改以多個(gè)隊(duì)列存儲(chǔ)。98邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)19邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)轉(zhuǎn)置結(jié)構(gòu)將每個(gè)關(guān)鍵字指向記錄的指針保存在關(guān)鍵字的域中。特點(diǎn)：適合于根據(jù)關(guān)鍵字的記錄搜索。99邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)20邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)順序結(jié)構(gòu)把文件中的關(guān)鍵字按規(guī)定的順序排列起來。特點(diǎn)：適合按某種優(yōu)先順序來搜索或追加、刪除記錄。例子：《人民日?qǐng)?bào)》新聞按登載日期的時(shí)間先后順序組成文件，如果想要搜索某一時(shí)期的歷史事件，只需要將時(shí)間范圍縮小到那一時(shí)期即可。100邏輯結(jié)構(gòu)和存取方法邏輯結(jié)構(gòu)21邏輯結(jié)構(gòu)和存取方法存取方法文件的存?。赫业轿募膬?nèi)容所在的邏輯地址。用途：用戶通過文件的存取來完成對(duì)文件的修改、追加和搜索等操作。三種方式：順序存取法、隨機(jī)存取法和按關(guān)鍵字存取法。101邏輯結(jié)構(gòu)和存取方法存取方法22邏輯結(jié)構(gòu)和存取方法存取方法順序存取法按照文件的邏輯地址順序存取。記錄式文件：按記錄的排列順序來存取，當(dāng)前記錄Ri，下一次讀取為相鄰記錄Ri+1。字符流文件：存取指針順序增長變化，當(dāng)前指向P，下一次讀取指向P+len，len為當(dāng)前讀取字符串長度。102邏輯結(jié)構(gòu)和存取方法存取方法23邏輯結(jié)構(gòu)和存取方法存取方法隨機(jī)存取法根據(jù)記錄的編號(hào)來存取文件的任意一個(gè)記錄。根據(jù)存取命令自如地移動(dòng)讀寫指針。103邏輯結(jié)構(gòu)和存取方法存取方法24邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取文件的存取根據(jù)給定的關(guān)鍵字或記錄名進(jìn)行的。做法：搜索要進(jìn)行存取的記錄的邏輯位置；將邏輯位置轉(zhuǎn)換到相應(yīng)的物理地址，然后進(jìn)行存取。適用于復(fù)雜的文件系統(tǒng)（數(shù)據(jù)庫管理系統(tǒng)）104邏輯結(jié)構(gòu)和存取方法存取方法25邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取搜索的過程：搜索算法：線性搜索法散列法二分搜索法105邏輯結(jié)構(gòu)和存取方法存取方法26邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取線性搜索法：從頭開始順序查找時(shí)間復(fù)雜度：O(N)106邏輯結(jié)構(gòu)和存取方法存取方法27邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取散列法：定義一個(gè)散列函數(shù)h(k)，使得對(duì)于給定的關(guān)鍵字k，散列函數(shù)都能將k變換得到其邏輯地址。散列沖突：對(duì)于k1!=k2，有h(k1)=h(k2)=A。兩個(gè)關(guān)鍵字的散列變換沖突。時(shí)間復(fù)雜度：O(1)107邏輯結(jié)構(gòu)和存取方法存取方法28邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取散列沖突的解決方法開放地址法：當(dāng)h(k1)產(chǎn)生的值h1沖突，再計(jì)算一個(gè)值h2,如果h2沖突，再計(jì)算一個(gè)直到不沖突為止hihi=(h(k1)+di)%tt為搜索長度di=a*i或c*(i*i)或隨機(jī)數(shù)。線性散列/平方散列/隨機(jī)散列108邏輯結(jié)構(gòu)和存取方法存取方法29邏輯結(jié)構(gòu)和存取方法存取方法按關(guān)鍵字存取二分搜索法典型的二分查找時(shí)間復(fù)雜度：O(logN)條件：已排序的對(duì)象序列。109邏輯結(jié)構(gòu)和存取方法存取方法30物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的存取在搜索到目標(biāo)記錄的邏輯地址后要確定物理地址。邏輯地址到物理地址的映射和文件的物理結(jié)構(gòu)緊密相連。文件系統(tǒng)的存取方法和邏輯結(jié)構(gòu)也與物理存儲(chǔ)介質(zhì)有關(guān)。文件的物理結(jié)構(gòu)和文件的存儲(chǔ)設(shè)備。110物理結(jié)構(gòu)和存儲(chǔ)設(shè)備31物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)是指文件在存儲(chǔ)設(shè)備上的存放方法。文件信息的邏輯地址到物理地址的變換是有文件的物理結(jié)構(gòu)決定的。文件的存儲(chǔ)設(shè)備通常劃分為大小相等的若干物理塊。常用的文件物理結(jié)構(gòu)包括：連續(xù)文件、串聯(lián)文件和索引文件。111物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)32物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)連續(xù)文件邏輯上連續(xù)的文件信息依次存放到物理塊中。112物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)33物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)連續(xù)文件優(yōu)點(diǎn)：地址變換簡單，知道了起址和長度就能很快進(jìn)行物理存取。缺點(diǎn)：文件建立時(shí)確定了文件長度，不能動(dòng)態(tài)增長；刪除后容易留下無法使用的零頭空間。113物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)34物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)串聯(lián)文件

用非連續(xù)的物理塊存放文件信息，每個(gè)物理塊設(shè)有指向后繼物理塊的指針。114物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)35物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)串聯(lián)文件特點(diǎn)：建立文件時(shí)不需要指明長度，只需第一個(gè)塊號(hào)?？梢詣?dòng)態(tài)增長，增刪、插入操作容易實(shí)現(xiàn)。搜索效率低，鏈表式搜索需要遍歷整個(gè)鏈。115物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)36物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)索引文件系統(tǒng)為每個(gè)文件建立一張索引表，表中記錄邏輯塊和物理塊的對(duì)應(yīng)。116物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)37物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)索引文件當(dāng)一個(gè)索引表大于一個(gè)物理塊，如何存放？多重索引。117物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)38物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)索引文件索引結(jié)構(gòu)的特點(diǎn)：適合順序存取也適合隨機(jī)存取。增加了索引表增加了存儲(chǔ)空間開銷。每次讀取文件需要訪問磁盤兩次。（可以將索引表放入內(nèi)存）118物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)39物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備順序存取存儲(chǔ)設(shè)備——磁帶直接存取存儲(chǔ)設(shè)備——磁盤磁盤設(shè)備允許文件系統(tǒng)直接存取磁盤上的任意物理塊。119物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備40物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤硬盤結(jié)構(gòu)包括：盤片、磁頭、盤片主軸、控制電機(jī)、磁頭控制器、數(shù)據(jù)轉(zhuǎn)換器、接口、緩存等幾個(gè)部份。所有的盤片（一般硬盤里有多個(gè)盤片，盤片之間平行）都固定在一個(gè)主軸上。在每個(gè)盤片的存儲(chǔ)面上都有一個(gè)磁頭，磁頭與盤片之間的距離很?。ㄋ詣×艺饎?dòng)容易損壞），磁頭連在一個(gè)磁頭控制器上，統(tǒng)一控制各個(gè)磁頭的運(yùn)動(dòng)。磁頭沿盤片的半徑方向動(dòng)作，而盤片則按照指定方向高速旋轉(zhuǎn)，這樣磁頭就可以到達(dá)盤片上的任意位置了。120物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備41物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤121物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備42物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤的容量：磁頭數(shù)×磁道(柱面)數(shù)×每道扇區(qū)數(shù)×每扇區(qū)字節(jié)數(shù)磁頭（head）數(shù)：每個(gè)盤片一般有上下兩面，分別對(duì)應(yīng)1個(gè)磁頭，共2個(gè)磁頭；磁道（track）數(shù)：磁道是從盤片外圈往內(nèi)圈編號(hào)0磁道，1磁道...，靠近主軸的同心圓用于?？看蓬^，不存儲(chǔ)數(shù)據(jù)；柱面（cylinder）數(shù)：同磁道數(shù)量；扇區(qū)（sector）數(shù)：每個(gè)磁道都別切分成很多扇形區(qū)域，每道的扇區(qū)數(shù)量相同；圓盤（platter）數(shù)：就是盤片的數(shù)量。 122物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備43物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備123物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備44物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備磁盤的數(shù)據(jù)定位：LBA(邏輯扇區(qū)號(hào))=磁頭數(shù)×每磁道扇區(qū)數(shù)×當(dāng)前所在柱面號(hào)+每磁道扇區(qū)數(shù)×當(dāng)前所在磁頭號(hào)+當(dāng)前所在扇區(qū)號(hào)–1例如：CHS=0/0/1，則根據(jù)公式LBA=255×63×0+63×0+1–1=0物理0柱面0磁頭1扇區(qū)，是邏輯0扇區(qū)124物理結(jié)構(gòu)和存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備45文件存儲(chǔ)空間管理文件的存儲(chǔ)設(shè)備以大小相等的物理塊為單位。文件存儲(chǔ)空間的管理實(shí)質(zhì)是空閑塊的組織和管理問題。有3種不同的空閑塊管理方法：空閑文件目錄、空閑塊鏈和位示圖。125文件存儲(chǔ)空間管理46文件存儲(chǔ)空間管理空閑文件目錄文件存儲(chǔ)設(shè)備中的空閑塊的塊號(hào)統(tǒng)一放在一個(gè)空閑文件目錄的物理塊中。每個(gè)表項(xiàng)存儲(chǔ)一個(gè)空閑區(qū)，一個(gè)空閑區(qū)包括一個(gè)或多個(gè)空閑塊。空閑文件目錄管理的空閑區(qū)的申請(qǐng)和釋放類似于內(nèi)存空閑區(qū)的管理。126文件存儲(chǔ)空間管理空閑文件目錄47文件存儲(chǔ)空間管理空閑塊鏈空閑塊鏈把文件存儲(chǔ)設(shè)備上的所有空閑塊鏈接在一起。申請(qǐng)空間時(shí)，從鏈表頭部摘取所需要的空閑塊，然后調(diào)整頭指針。釋放空間時(shí)，新的空閑塊插入鏈尾上?？臻e塊的鏈接方式：按空閑區(qū)大小順序鏈接、按釋放先后順序鏈接和成組鏈接。127文件存儲(chǔ)空間管理空閑塊鏈48文件存儲(chǔ)空間管理空閑塊鏈成組鏈接法前兩種方式在增加或移動(dòng)空閑塊時(shí)需要對(duì)空閑塊鏈做較大的調(diào)整，系統(tǒng)開銷大?；驹恚核锌臻e塊50塊一組，組的劃分從后向前，每組的第一塊用來存放前一組的各塊的塊號(hào)和總塊數(shù)。128文件存儲(chǔ)空間管理空閑塊鏈49文件存儲(chǔ)空間管理空閑塊鏈成組鏈接法第一組前面沒有其他組，所以第一組為49塊；最后一組的塊數(shù)可能不到50塊，因?yàn)榭偟膲K數(shù)可能不是50的倍數(shù)。最后一組的各塊號(hào)和總塊數(shù)存放在文件資源表中。129文件存儲(chǔ)空間管理空閑塊鏈50文件存儲(chǔ)空間管理空閑塊鏈成組鏈接法分配和釋放過程130文件存儲(chǔ)空間管理空閑塊鏈51文件存儲(chǔ)空間管理位示圖從系統(tǒng)內(nèi)存中劃分若干個(gè)字節(jié)，為每個(gè)文件存儲(chǔ)設(shè)備建立一張位示圖，反映各設(shè)備的使用情況。位示圖中的每個(gè)比特位對(duì)應(yīng)一個(gè)物理塊的分配情況，0表示未分配，1表示已分配。位示圖法分配與回收時(shí)不需要再文件存儲(chǔ)設(shè)備上查找文件目錄或鏈接塊號(hào)，即不需要啟動(dòng)外設(shè)即可完成，因此速度快。131文件存儲(chǔ)空間管理位示圖52文件目錄管理文件名及其結(jié)構(gòu)信息需要按一定的組織結(jié)構(gòu)排列，以方便搜索查找。文件目錄管理：存儲(chǔ)空間有效利用、快速搜索、解決文件命名沖突以及文件共享。文件的組成文件目錄的介紹便于共享的文件目錄目錄管理132文件目錄管理文件名及其結(jié)構(gòu)信息需要按一定的組織結(jié)構(gòu)排列，以文件目錄管理文件的組成文件說明和文件體文件體：文件本身的信息文件說明：文件控制塊（FCB）文件名、與文件名相對(duì)應(yīng)的文件內(nèi)部表示以及在文件存儲(chǔ)設(shè)備上的第一個(gè)物理塊地址。文件說明組成文件目錄133文件目錄管理文件的組成54文件目錄管理文件目錄文件目錄：單級(jí)目錄、二級(jí)目錄和多級(jí)目錄單級(jí)目錄：文件系統(tǒng)為所有文件建立一張目錄表，每個(gè)文件占用一個(gè)表項(xiàng)。目錄表存放在存儲(chǔ)設(shè)備的固定區(qū)域，系統(tǒng)啟動(dòng)后調(diào)入內(nèi)存。文件系統(tǒng)通過該表完成對(duì)文件的創(chuàng)建、搜索和刪除等操作。134文件目錄管理文件目錄55文件目錄管理文件目錄單級(jí)目錄的讀寫處理過程135文件目錄管理文件目錄56文件目錄管理文件目錄單級(jí)目錄的問題：命名沖突問題：單表目錄中只能按連續(xù)結(jié)構(gòu)或順序結(jié)構(gòu)存放，文件名與文件一一對(duì)應(yīng)，相同文件名被視為同一文件。搜索速度問題：單表目錄每次搜索需要對(duì)所有文件遍歷，因此速度慢。136文件目錄管理文件目錄57文件目錄管理文件目錄二級(jí)目錄各個(gè)文件的說明信息被組織成目錄文件，且以用戶為單位化為不同的組。MFD主目錄：不同組名的存取控制信息存放的目錄。UFD用戶文件目錄：用戶文件說明所組成。137文件目錄管理文件目錄58文件目錄管理文件目錄二級(jí)目錄138文件目錄管理文件目錄59文件目錄管理文件目錄二級(jí)目錄同名沖突問題：可以輕易解決，因?yàn)橥煌M。文件共享問題：可以通過將共享的文件設(shè)置相應(yīng)的共享指針。查找速度：n個(gè)文件劃分成m個(gè)子集，r為每個(gè)用戶子集的文件數(shù)，則n<=m*r(存在共享文件）。查找速度有n變?yōu)閙+r，一般m+r<=n，因此查找速度>單級(jí)目錄。139文件目錄管理文件目錄60文件目錄管理文件目錄多級(jí)目錄：二級(jí)目錄層次關(guān)系的推廣140文件目錄管理文件目錄61文件目錄管理文件目錄多級(jí)目錄特點(diǎn)：層次清楚，便于管理。解決了文件的重名沖突問題。查找速度塊。141文件目錄管理文件目錄62文件目錄管理便于共享的文件目錄共享文件的必要性：節(jié)約存儲(chǔ)空間。實(shí)現(xiàn)文件共享的3種方法：繞道法鏈接法基本文件目錄表（BFD）142文件目錄管理便于共享的文件目錄63文件目錄管理便于共享的文件目錄繞道法根據(jù)文件的固有名，從當(dāng)前目錄出發(fā)向上返回到與共享文件所在路徑的交叉點(diǎn)，再順序下訪。固有名：目錄名+文件名繞道法需要繞彎路訪問多級(jí)目錄，搜索效率不高。143文件目錄管理便于共享的文件目錄64文件目錄管理便于共享的文件目錄鏈接法在相應(yīng)目錄表之間進(jìn)行鏈接，一個(gè)目錄中的鏈指針指向被共享文件所