操作系統(tǒng)文件管理算法研究畢業(yè)論文

1、<p>　　畢 業(yè) 設(shè) 計(jì)（論 文）</p><p>　　題目： 操作系統(tǒng)文件管理算法研究</p><p>　?。ㄓ⑽模?On the Research of the File Management Algorithm in Operating System</p><p>　　院 別： </p>

2、;<p>　　專 業(yè)： </p><p>　　姓 名： </p><p>　　學(xué) 號(hào)： </p><p>　　指導(dǎo)教師： </p><p>

3、　　日 期： </p><p>　　操作系統(tǒng)文件管理算法研究</p><p><b>　　摘要</b></p><p>　　文件管理是操作系統(tǒng)中一項(xiàng)重要的功能。其重要性在于，在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，用戶的程序和數(shù)據(jù)，操作系統(tǒng)自身的程序和數(shù)據(jù)，甚至各種輸出輸入設(shè)備，都是以文件形式出現(xiàn)的。隨著信息化進(jìn)

4、程，文件管理越來(lái)越受到企業(yè)的重視，但是企業(yè)在進(jìn)行文件管理的過(guò)程中，經(jīng)常會(huì)碰到以下的問(wèn)題：海量文件存儲(chǔ)，管理困難；查找緩慢，效率低下；文件版本管理混亂；文件安全缺乏保障；文件無(wú)法有效協(xié)作共享；知識(shí)管理舉步維艱等。所以文件管理逐漸成為國(guó)內(nèi)外業(yè)界研究的熱點(diǎn)。文章通過(guò)對(duì)現(xiàn)在的主流的文件管理算法及數(shù)據(jù)結(jié)構(gòu)進(jìn)行研究，并編寫程序模擬，論證了在各種不同的算法下，文件管理的優(yōu)缺點(diǎn)，得出在各種不同情況下使用何種算法的來(lái)管理文件。</p>&l

5、t;p>　　關(guān)鍵詞：文件管理；文件存儲(chǔ)；文件管理算法</p><p>　　On the Research of the File Management Algorithm in Operating System</p><p><b>　　ABSTRACT</b></p><p>　　File management is one of i

6、mportant function in the operating system. In the modern computer system. The user program and data, the operating system’s program and data ,even more all kinds of output input device are the documents form. With the pr

7、ocess of information, file management more and more get the attention of the enterprise. But in the process of file management, the following question often come in enterprise: mass file storage, management difficultly;

8、search slow; file version managem</p><p>　　Key words: file management; filestore; file management algorithm</p><p><b>　　目錄</b></p><p>　　第1章 緒 論1</p><p>　　

9、1.1操作系統(tǒng)文件管理概述1</p><p>　　1.1.1操作系統(tǒng)的定義1</p><p>　　1.1.2操作系統(tǒng)文件管理概述2</p><p>　　1.2操作系統(tǒng)文件管理的意義2</p><p>　　第2章 文件管理4</p><p>　　2.1 文件與文件系統(tǒng)4</p><

10、;p>　　2.1.1 文件的定義4</p><p>　　2.1.2 文件系統(tǒng)概念4</p><p>　　2.1.3 文件系統(tǒng)的功能5</p><p>　　2.1.4 文件的分類5</p><p>　　2.2 文件的邏輯結(jié)構(gòu)與存取方式5</p><p>　　2.3 文件的物理結(jié)構(gòu)與存儲(chǔ)介質(zhì)6</p

11、><p>　　2.3.1 文件的物理結(jié)構(gòu)6</p><p>　　2.4 文件目錄10</p><p>　　2.4.1 文件目錄組成10</p><p>　　2.4.2 文件目錄結(jié)構(gòu)11</p><p>　　2.5 文件系統(tǒng)的實(shí)現(xiàn)12</p><p>　　2.5.1 文件記錄塊13<

12、/p><p>　　2.5.2 磁盤空間的管理13</p><p>　　第3章 編程環(huán)境介紹18</p><p>　　3.1 Vmware18</p><p>　　3.1.1 構(gòu)建虛擬機(jī)18</p><p>　　3.1.2 安裝Linux操作系統(tǒng)19</p><p>　　3.1.3 安裝V

13、Mware Tool20</p><p>　　3.2 VI（VIM）編輯器20</p><p>　　3.3 GCC編譯器21</p><p>　　3.3.1 GCC基本規(guī)則21</p><p>　　3.3.2 GCC基本用法21</p><p>　　3.4 GDB調(diào)試工具22</p><

14、p>　　第四章 文件管理算法研究與模擬24</p><p>　　4.1 位示圖算法研究24</p><p>　　4.2 位示圖模擬27</p><p>　　4.3 UNIX系統(tǒng)文件管理成組連接算法28</p><p>　　4.4 成組鏈接程序模擬29</p><p><b>　　參考文獻(xiàn)32

15、</b></p><p><b>　　致謝33</b></p><p><b>　　附錄34</b></p><p><b>　　第1章 緒 論</b></p><p>　　在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，用戶的程序和數(shù)據(jù)，操作系統(tǒng)自身的程序和數(shù)據(jù)，甚至各種輸出輸入設(shè)備，

16、都是以文件形式出現(xiàn)的?？梢哉f(shuō)，盡管文件有多種存儲(chǔ)介質(zhì)可以使用，如硬盤、軟盤，光盤，閃存，記憶棒等等，但是，它們都以文件的形式出現(xiàn)在操作系統(tǒng)的管理者和用戶面前。所以，文件管理是操作系統(tǒng)中的一項(xiàng)重要的功能。</p><p>　　操作系統(tǒng)文件管理概述</p><p><b>　　操作系統(tǒng)的定義</b></p><p>　　操作系統(tǒng)的功能包括管理計(jì)算機(jī)

17、系統(tǒng)的硬件、軟件及數(shù)據(jù)資源；控制程序運(yùn)行；改善人機(jī)界面；為其它應(yīng)用軟件提供支持等，使計(jì)算機(jī)系統(tǒng)所有資源最大限度地發(fā)揮作用，為用戶提供方便的、有效的、友善的服務(wù)界面。 </p><p>　　許多操作系統(tǒng)制造者對(duì)OS的定義也不大一致，例如有些OS集成了圖形用戶界面，而有些OS僅使用文本接口，而將圖形界面視為一種非必要的應(yīng)用程序。 </p><p>　　操作系統(tǒng)理論在計(jì)算機(jī)科學(xué)中為歷史悠久而又活

18、躍的分支，而操作系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)則是軟件工業(yè)的基礎(chǔ)與內(nèi)核。</p><p>　　操作系統(tǒng)的主要功能是資源管理，程序控制和人機(jī)交互等。計(jì)算機(jī)系統(tǒng)的資源可分為設(shè)備資源和信息資源兩大類。設(shè)備資源指的是組成計(jì)算機(jī)的硬件設(shè)備，如中央處理器，主存儲(chǔ)器，磁盤存儲(chǔ)器，打印機(jī)，磁帶存儲(chǔ)器，顯示器，鍵盤輸入設(shè)備和鼠標(biāo)等。信息資源指的是存放于計(jì)算機(jī)內(nèi)的各種數(shù)據(jù)，如文件，程序庫(kù)，知識(shí)庫(kù)，系統(tǒng)軟件和應(yīng)用軟件等。 </p>&

19、lt;p>　　操作系統(tǒng)位于底層硬件與用戶之間，是兩者溝通的橋梁。用戶可以通過(guò)操作系統(tǒng)的用戶界面，輸入命令。操作系統(tǒng)則對(duì)命令進(jìn)行解釋，驅(qū)動(dòng)硬件設(shè)備，實(shí)現(xiàn)用戶要求。以現(xiàn)代觀點(diǎn)而言，一個(gè)標(biāo)準(zhǔn)個(gè)人電腦的OS應(yīng)該提供以下的功能： </p><p>　　進(jìn)程管理（Processing management）</p><p>　　記憶空間管理（Memory management） </p&g

20、t;<p>　　文件系統(tǒng)（File system） </p><p>　　網(wǎng)絡(luò)通訊（Networking） </p><p>　　安全機(jī)制（Security） </p><p>　　使用者界面（User interface） </p><p>　　驅(qū)動(dòng)程序（Device drivers）</p><p>

21、　　操作系統(tǒng)文件管理概述</p><p>　　文件管理是操作系統(tǒng)的五大職能之一，主要涉及文件的邏輯組織和物理組織，目錄的結(jié)構(gòu)和管理。所謂文件管理，就是操作系統(tǒng)中實(shí)現(xiàn)文件統(tǒng)一管理的一組軟件、被管理的文件以及為實(shí)施文件管理所需要的一些數(shù)據(jù)結(jié)構(gòu)的總稱（是操作系統(tǒng)中負(fù)責(zé)存取和管理文件信息的機(jī)構(gòu)）從系統(tǒng)角度來(lái)看，文件系統(tǒng)是對(duì)文件存儲(chǔ)器的存儲(chǔ)空間進(jìn)行組織，分配和回收，負(fù)責(zé)文件的存儲(chǔ)，檢索，共享和保護(hù)。從用戶角度來(lái)看，文件系統(tǒng)

22、主要是實(shí)現(xiàn)"按名取存"，文件系統(tǒng)的用戶只要知道所需文件的文件名，就可存取文件中的信息，而無(wú)需知道這些文件究竟存放在什么地方。其功能在于：</p><p>　　①統(tǒng)一管理文件存儲(chǔ)空間(即外存)，實(shí)施存儲(chǔ)空間的分配與回收。 </p><p>　?、诖_定文件信息的存放位置及存放形式。 </p><p>　?、蹖?shí)現(xiàn)文件從名字空間到外存地址空間的映射，即實(shí)

23、現(xiàn)文件的按名存取。 </p><p>　?、苡行?shí)現(xiàn)對(duì)文件的各種控制操作(如建立、撤銷、打開、關(guān)閉文件等)和存取操作(如讀、寫、修改、復(fù)制、轉(zhuǎn)儲(chǔ)等) </p><p>　?、輰?shí)現(xiàn)文件的高速存取 </p><p>　　操作系統(tǒng)文件管理的意義</p><p>　　文件管理是操作系統(tǒng)中一項(xiàng)重要的功能。其重要性在于，在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，用戶的程序和數(shù)

24、據(jù)，操作系統(tǒng)自身的程序和數(shù)據(jù)，甚至各種輸出輸入設(shè)備，都是以文件形式出現(xiàn)的?？梢哉f(shuō)，盡管文件有多種存儲(chǔ)介質(zhì)可以使用，如硬盤、軟盤，光盤，閃存，記憶棒等等，但是，它們都以文件的形式出現(xiàn)在操作系統(tǒng)的管理者和用戶面前。</p><p>　　隨著信息化進(jìn)程，文件管理越來(lái)越受到企業(yè)的重視，但是企業(yè)在進(jìn)行文件管理的過(guò)程中，經(jīng)常會(huì)碰到以下的問(wèn)題：海量文件存儲(chǔ)，管理困難；查找緩慢，效率低下；文件版本管理混亂；文件安全缺乏保障；文件

25、無(wú)法有效協(xié)作共享；知識(shí)管理舉步維艱等。所以文件管理逐漸成為國(guó)內(nèi)外業(yè)界研究的熱點(diǎn)。</p><p><b>　　第2章 文件管理</b></p><p>　　在計(jì)算機(jī)系統(tǒng)中，信息的組織、存取、加工和保管等工作主要是由文件系統(tǒng)來(lái)完成的。文件系統(tǒng)是操作系統(tǒng)中一個(gè)重要的組成部分。而且，對(duì)大多數(shù)用戶來(lái)說(shuō)，除了人機(jī)界面之外，文件系統(tǒng)是用戶經(jīng)常訪問(wèn)，直接處理的一個(gè)部分。</

26、p><p>　　2.1 文件與文件系統(tǒng)</p><p>　　研究文件系統(tǒng)有兩種不同的觀點(diǎn)，一種是用戶的觀點(diǎn)，另一種是操作系統(tǒng)的觀點(diǎn)。從用戶的觀點(diǎn)看文件系統(tǒng)，主要是關(guān)心文件由什么組成，如何命名，如何保護(hù)文件，可以進(jìn)行何種操作等等。從操作系統(tǒng)的觀點(diǎn)看文件系統(tǒng)，主要關(guān)心文件目錄是怎樣實(shí)現(xiàn)的，怎么樣管理存儲(chǔ)空間，文件存儲(chǔ)位置，磁盤實(shí)際動(dòng)作方式等問(wèn)題。</p><p>　　2.1

27、.1 文件的定義</p><p>　　文件是一組帶標(biāo)識(shí)的、在邏輯上有完整意義的信息項(xiàng)的序列。這個(gè)標(biāo)識(shí)符為文件名，信息項(xiàng)構(gòu)成了文件內(nèi)容的基本單位。</p><p>　　一般地，文件建立在存儲(chǔ)器空間里，以便使文件能夠長(zhǎng)期保存。文件是一個(gè)抽象機(jī)制，它提供了一種把信息保存在存儲(chǔ)介質(zhì)上，而且便于以后存取的方法，用戶不必關(guān)心文件實(shí)現(xiàn)的細(xì)節(jié)。</p><p>　　2.1.2 文件

28、系統(tǒng)概念</p><p>　　所謂文件系統(tǒng)，是操作系統(tǒng)中統(tǒng)一管理信息資源的一種軟件。它管理文件的存儲(chǔ)、檢索、更新，提供安全可靠的共享和保護(hù)手段，并且方便用戶使用。</p><p>　　從用戶的角度來(lái)看，文件系統(tǒng)負(fù)責(zé)為用戶建立文件、讀寫文件、修改文件、復(fù)制文件和撤消文件。文件系統(tǒng)還負(fù)責(zé)完成對(duì)文件的按名存取和對(duì)文件進(jìn)行存取控制。</p><p>　　2.1.3 文件系統(tǒng)

29、的功能</p><p>　　作為一個(gè)統(tǒng)一的文件管理機(jī)構(gòu)，文件系統(tǒng)具有下述功能：</p><p>　?。?）統(tǒng)一管理文件的存儲(chǔ)空間，實(shí)施存儲(chǔ)空間的分配與回收。</p><p>　?。?）實(shí)現(xiàn)文件從名字空間到外存地址空間的映射，即實(shí)現(xiàn)文件的按名存取，以對(duì)用戶透明的方式管理名字空間。</p><p>　?。?）實(shí)現(xiàn)文件信息的共享，并提供文件的保護(hù)和

30、保密措施。</p><p>　　（4）向用戶提供一個(gè)方便使用的接口。</p><p>　?。?）系統(tǒng)維護(hù)及向用戶提供有關(guān)信息。</p><p>　?。?）保持文件系統(tǒng)的執(zhí)行效率。</p><p>　?。?）提供與I/O的統(tǒng)一接口。</p><p>　　2.1.4 文件的分類</p><p>　　

31、（1）根據(jù)文件的性質(zhì)和用途：系統(tǒng)文件、用戶文件、庫(kù)文件。</p><p>　?。?）根據(jù)文件中數(shù)據(jù)的形式：源文件、目標(biāo)文件、可執(zhí)行文件。</p><p>　?。?）根據(jù)存取控制屬性：只執(zhí)行文件、只讀文件、讀寫文件。</p><p>　?。?）根據(jù)組織形式和處理方式：普通文件、目錄文件、特殊文件。</p><p>　　2.2 文件的邏輯結(jié)構(gòu)與存

32、取方式</p><p>　　文件的邏輯結(jié)構(gòu)就是用戶所看到的文件的組織形式。文件邏輯結(jié)構(gòu)是一種經(jīng)過(guò)抽象的結(jié)構(gòu)，所描述的是記錄在文件中信息的組織形式工。文件中的這些信息到底在物理介質(zhì)上是如何組織存儲(chǔ)的，與用戶沒有直接關(guān)系。</p><p>　　從用戶角度看，按文件的邏輯結(jié)構(gòu)可以把文件劃分成三類：無(wú)結(jié)構(gòu)的字符流式文件、定長(zhǎng)記錄文件和不定長(zhǎng)記錄文件構(gòu)成的記錄樹，如圖2.1所示：</p>

33、<p><b>　　圖 2.1</b></p><p>　　用戶通過(guò)對(duì)文件的存取來(lái)完成對(duì)文件的各種操作，文件的存取方式是由文件的性質(zhì)和用戶使用文件的情況而確定的。常用的存取方法有：順序存取、隨機(jī)存取和按鍵存取等三種方式。</p><p>　　2.3 文件的物理結(jié)構(gòu)與存儲(chǔ)介質(zhì)</p><p>　　2.3.1 文件的物理結(jié)構(gòu)</

34、p><p>　　常用的文件物理結(jié)構(gòu)有順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)和I節(jié)點(diǎn)結(jié)構(gòu)。</p><p><b>　　1、順序結(jié)構(gòu)</b></p><p>　　文件信息存放在若干連續(xù)的物理塊中。如下圖中，文件count從編號(hào)為0的物理塊開始存儲(chǔ)，占用兩個(gè)連續(xù)的物理塊；文件mail從編號(hào)為19的物理塊開始存儲(chǔ)，占用6個(gè)連續(xù)的物理塊。</p>&l

35、t;p>　　圖2.2 文件的順序結(jié)構(gòu)</p><p><b>　　順序結(jié)構(gòu)的優(yōu)點(diǎn)：</b></p><p>　　1、簡(jiǎn)單：存儲(chǔ)與管理都簡(jiǎn)單，且容易實(shí)現(xiàn)。</p><p>　　2、支持順序存取和隨機(jī)存取。</p><p>　　3、順序存取速度快。</p><p>　　4、所需的磁盤尋道次數(shù)和尋

36、道時(shí)間最少。</p><p><b>　　順序結(jié)構(gòu)的缺點(diǎn)：</b></p><p>　　1、需要為每個(gè)文件預(yù)留若干物理塊以滿足文件增長(zhǎng)的部分需要。</p><p>　　不利于文件插入和刪除。</p><p><b>　　2、鏈表結(jié)構(gòu)</b></p><p>　　文件信息存放在

37、若干不連續(xù)的物理塊中，各塊之間通過(guò)指針連接，前一個(gè)物理塊指向下一個(gè)物理塊。下圖說(shuō)明文件jeep存儲(chǔ)時(shí)所占用的物理塊。</p><p>　　圖2.3 文件的鏈表結(jié)構(gòu)</p><p><b>　　優(yōu)點(diǎn)</b></p><p>　　1、提高了磁盤空間利用率，不需要為每個(gè)文件預(yù)留物理塊。</p><p>　　2、有利于文件插入和

38、刪除。</p><p>　　3、有利于文件動(dòng)態(tài)擴(kuò)充。</p><p><b>　　缺點(diǎn)</b></p><p>　　1、存取速度慢，不適于隨機(jī)存取。</p><p>　　2、當(dāng)物理塊間的連接指針出錯(cuò)時(shí)，數(shù)據(jù)丟失。</p><p>　　3、更多的尋道次數(shù)和尋道時(shí)間。</p><p

39、>　　4、鏈接指針占用一定的空間，降低了空間利用率。</p><p><b>　　3、索引結(jié)構(gòu)</b></p><p>　　文件信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個(gè)文件建立一個(gè)專用數(shù)據(jù)結(jié)構(gòu)，稱為索引表，并將存放文件信息的物理塊的塊號(hào)存放在索引表中。</p><p>　　索引表是磁盤塊地址數(shù)組,其中第i個(gè)條目指向文件的第i塊。如下圖所示

40、：</p><p>　　圖2.4 文件的索引結(jié)構(gòu)</p><p><b>　　優(yōu)點(diǎn)</b></p><p>　　1、不需要為每個(gè)文件預(yù)留物理塊。</p><p>　　2、既能順序存取，又能隨機(jī)存取。</p><p>　　3、滿足了文件動(dòng)態(tài)增長(zhǎng)、插入刪除的要求。</p><p&g

41、t;<b>　　缺點(diǎn)</b></p><p>　　1、較多的尋道次數(shù)和尋道時(shí)間。</p><p>　　2、索引表本身帶來(lái)了系統(tǒng)開銷。如：內(nèi)外存空間，存取時(shí)間等。</p><p>　　4、多級(jí)索引結(jié)構(gòu)——UNIX的I節(jié)點(diǎn)</p><p>　　UNIX文件系統(tǒng)采用的是多級(jí)索引結(jié)構(gòu)（綜合模式）。每個(gè)文件的索引表為13個(gè)索引項(xiàng)，

42、每項(xiàng)2個(gè)字節(jié)。最前面10項(xiàng)直接存放文件信息的物理塊號(hào)（直接尋址）。如果文件大于10塊，則利用第11項(xiàng)指向一個(gè)物理塊，該塊中最多可放256個(gè)文件物理塊的塊號(hào)（一次間接尋址）。對(duì)于更大的文件還可利用第12和第13項(xiàng)作為二次和三次間接尋址。UNIX中采用三級(jí)索引結(jié)構(gòu)后，文件最大可達(dá)16兆個(gè)物理塊。如下圖所示：</p><p>　　圖2.5 I節(jié)點(diǎn)結(jié)構(gòu)</p><p><b>　　2.4

43、 文件目錄</b></p><p>　　在一個(gè)計(jì)算機(jī)系統(tǒng)中保存有許多文件，用戶在創(chuàng)建和使用文件時(shí)只給出文件的名字，由文件系統(tǒng)根據(jù)文件名找到指定文件。為了便于對(duì)文件進(jìn)行管理，設(shè)置了文件目錄，用于檢索系統(tǒng)中的所有文件。</p><p>　　2.4.1 文件目錄組成</p><p>　　文件系統(tǒng)的一個(gè)最大的特點(diǎn)是“按名存取”，用戶只要給出文件的符號(hào)名就能方便地

44、存取在外存空間的文件信息，而不必關(guān)心文件的具體物理地址。而實(shí)現(xiàn)文件符號(hào)到文件物理地址映射的主要環(huán)節(jié)是檢索文件目錄。系統(tǒng)為每個(gè)文件設(shè)置一個(gè)描述性數(shù)據(jù)結(jié)構(gòu)——文件控制塊FCB，文件目錄就是文件控制塊的有序集合，即把所有文件控制塊有機(jī)地組織起來(lái)，就構(gòu)成了文件目錄。</p><p>　　（1）文件控制塊FCB結(jié)構(gòu)</p><p>　　FCB是系統(tǒng)為管理文件而設(shè)置的一個(gè)數(shù)據(jù)結(jié)構(gòu)。FCB是文件存在的標(biāo)

45、志，它記錄了系統(tǒng)管理文件所需要的全部信息。</p><p>　　FCB通常應(yīng)包括以下內(nèi)容：</p><p>　　文件名，文件號(hào)，用戶名，文件地址，文件長(zhǎng)度，文件類型，文件屬性，共享計(jì)數(shù)，文件的建立日期，保存期限，最后修改日期，最后訪問(wèn)日期，口令，文件邏輯結(jié)構(gòu)，文件物理結(jié)構(gòu)等。</p><p><b>　　（2）目錄文件</b></p>

46、;<p>　　為了實(shí)現(xiàn)對(duì)文件目錄的管理，通常將文件目錄以文件的形式長(zhǎng)期保存在外</p><p>　　存空間，這個(gè)文件就被稱為目錄文件。通常，目錄文件是長(zhǎng)度固定的記錄式文件。</p><p>　　2.4.2 文件目錄結(jié)構(gòu)</p><p>　　文件目錄結(jié)構(gòu)分為一級(jí)目錄結(jié)構(gòu)，二級(jí)目錄結(jié)構(gòu)和多級(jí)目錄結(jié)構(gòu)。</p><p>　　圖2.6

47、 一級(jí)目錄結(jié)構(gòu)</p><p>　　圖2.7 二級(jí)目錄結(jié)構(gòu)</p><p>　　圖2.8 多級(jí)目錄結(jié)構(gòu)</p><p>　　2.5 文件系統(tǒng)的實(shí)現(xiàn)</p><p>　　前面討論的文件系統(tǒng)，主要是從用戶的角度探討問(wèn)題。這里是將從實(shí)現(xiàn)的角度討論文件系統(tǒng)如何實(shí)現(xiàn)，也就是文件系統(tǒng)的內(nèi)在物理結(jié)構(gòu)。</p><p>　　文件的使

48、用者關(guān)心文件是如何命名、可以進(jìn)行哪些文件操作。文件目錄是如何組織的、如何檢索或查找文件目錄等問(wèn)題。</p><p>　　而設(shè)計(jì)和實(shí)現(xiàn)者感興趣的是，在磁盤上怎樣安排文件和目錄存儲(chǔ)，如何管理磁盤空間以及怎樣使文件系統(tǒng)有效而可靠地工作等。</p><p>　　文件系統(tǒng)實(shí)現(xiàn)的關(guān)鍵是，找到一種符合設(shè)計(jì)要求的方法，把文件記錄到磁盤塊上去。所謂文件的物理結(jié)構(gòu)，是從系統(tǒng)的角度來(lái)看文件，從文件在物理介質(zhì)上的

49、存放方式來(lái)研究文件。</p><p>　　2.5.1 文件記錄塊</p><p>　　文件的存儲(chǔ)設(shè)備常常劃分為若干大小相等的物理塊。同時(shí)也將文件信息劃分成邏輯塊，所有塊統(tǒng)一編號(hào)。以塊為單位進(jìn)行信息的存儲(chǔ)、傳輸和分配。</p><p>　　從用戶的角度來(lái)看文件，是把每一個(gè)文件看作是一個(gè)整體的，不考慮文件實(shí)際在磁盤上的存放方法。事實(shí)上，文件有大有小，磁盤的存儲(chǔ)空間也有大

50、小，另外，文件傳輸時(shí)也必須分塊。</p><p>　　這樣，在文件系統(tǒng)中，是以塊作為分配和傳送信息的基本單位。顯然，對(duì)于字符流的無(wú)結(jié)構(gòu)文件來(lái)說(shuō)，每一個(gè)物理塊中存放長(zhǎng)度相等的文件信息。不過(guò)，對(duì)于記錄式文件來(lái)說(shuō)，由于記錄長(zhǎng)度可以是固定的，也可以是可變的，而且其長(zhǎng)度不一定剛好等于其物理塊的長(zhǎng)度，從而有可能給由記錄的邏輯地址到物理地址的變換帶來(lái)了額外的負(fù)擔(dān)。</p><p>　　2.5.2 磁盤空

51、間的管理</p><p>　　一個(gè)存儲(chǔ)設(shè)備上的空閑空間登記表（FSL）動(dòng)態(tài)跟蹤記錄該存儲(chǔ)設(shè)備上所有空閑塊的數(shù)目和塊號(hào)。該數(shù)據(jù)結(jié)構(gòu)雖稱為表，但不一定以二維表形式實(shí)現(xiàn)。為方便高效安全起見，一般把FSL放在存儲(chǔ)實(shí)體上。</p><p>　　由于設(shè)備空間是有限的，故不再使用的空間必須回收以重用，然后在建立文件等操作中重新動(dòng)態(tài)分配?？梢娫谖募h除、文件建立、寫文件等操作中都會(huì)訪問(wèn)與修改空閑空間表。在

52、實(shí)際系統(tǒng)中四種不同的方案，分別為位示圖、空閑塊表、空閑塊鏈表、成組鏈表。</p><p><b>　　位示圖</b></p><p>　　位示圖法的基本思想是利用一串二進(jìn)制的值來(lái)反映磁盤空間的分配使用情況。每一個(gè)磁盤物理塊對(duì)應(yīng)一個(gè)二進(jìn)制位，如果物理塊為空閑，則相應(yīng)的二進(jìn)制位為0；如果物理塊已分配，則相應(yīng)的二進(jìn)位為1，如圖所示：</p><p>

53、<b>　　圖 2.9 位示圖</b></p><p>　　申請(qǐng)磁盤物理塊時(shí)，可在位示圖中從頭查找為0的字位，將其改為1，返回對(duì)應(yīng)的物理塊號(hào)；歸還物理塊時(shí)，在位示圖中將該塊所對(duì)應(yīng)的字位改為0。</p><p>　　磁盤空閑空間登記數(shù)據(jù)結(jié)構(gòu)在大部分情況下以位示圖實(shí)現(xiàn)。</p><p>　　位示圖描述能力強(qiáng)，一個(gè)二進(jìn)位就描述一個(gè)物理塊的狀態(tài)，因而位

54、示圖較小，可以復(fù)制到內(nèi)存，使查找既方便又快速。位示圖適用于各種文件物理結(jié)構(gòu)的文件系統(tǒng)。</p><p>　　位示圖的主要優(yōu)點(diǎn)是能夠簡(jiǎn)單有效地盤上找到n個(gè)連續(xù)空閑塊。的確，很多計(jì)算機(jī)提供了位操作指令，使位示圖查找能夠高效進(jìn)行。例如，Intel x86微處理器系列就有這樣的指令：返回指定寄存器的所有位中值為1的第一位。</p><p>　　Linux的文件系統(tǒng)Ext2就是采用位示圖來(lái)描述數(shù)據(jù)塊

55、和索引節(jié)點(diǎn)的使用情況的。</p><p><b>　　2、空閑塊表</b></p><p>　　文件系統(tǒng)建立一張空閑塊表，該表記錄了全部空閑的物理塊：包括首空閑塊號(hào)和空閑塊個(gè)數(shù)?？臻e塊表方式特別適合于文件物理結(jié)構(gòu)為順序結(jié)構(gòu)的文件系統(tǒng)。</p><p>　　建立新文件時(shí)，系統(tǒng)查找空閑塊表，尋找合適的表項(xiàng)，分配一組連續(xù)的空閑塊。如果對(duì)應(yīng)表項(xiàng)所擁有空

56、閑塊個(gè)數(shù)恰好等于所申請(qǐng)值，就將該表項(xiàng)從空閑塊表中刪去。當(dāng)刪除文件時(shí)，系統(tǒng)收回它所占用的物理塊，考慮是否可以與原有空閑塊相鄰接，合并成更大的空閑區(qū)域，最后修改有關(guān)表項(xiàng)。</p><p>　　圖 2.10 空閑塊表</p><p><b>　　3、空閑塊鏈表</b></p><p>　　系統(tǒng)將所有的空閑物理塊連成一個(gè)鏈，用一個(gè)空閑塊首指針指向第一個(gè)

57、空閑塊，然后每個(gè)空閑塊含有指向下一個(gè)空閑塊的指針，，最后一塊的指針為空，表示鏈尾。</p><p>　　圖 2.11 空閑塊鏈接表</p><p>　　在圖2.11中，空閑塊首指針維持一個(gè)指向盤塊12的指針，該塊是第一個(gè)空閑盤塊。盤塊12包含一個(gè)指向盤塊13的指針，盤塊13指向盤塊14等等。這種模式效率低，要遍歷整張表，必須讀第一個(gè)塊，需要大量I/O時(shí)間。</p><p

58、>　　外存空間的申請(qǐng)和釋放以塊為單位，申請(qǐng)時(shí)從鏈?zhǔn)兹∫粔K，釋放時(shí)將其鏈入鏈尾，空閑塊鏈表節(jié)省內(nèi)存，但申請(qǐng)釋放速度較慢，實(shí)現(xiàn)效率較低。</p><p><b>　　4、成組鏈接</b></p><p>　　對(duì)鏈接表的改進(jìn)就是將空閑盤塊分成若干組，每一組空閑盤塊的地址存放在另一空閑盤塊組的第一個(gè)空閑塊中，該組中其余n-1個(gè)空閑盤塊是實(shí)際空閑的。假設(shè)每100個(gè)空閑塊為

59、一組。通常第一組可能不足100塊，第一組空閑盤塊的地址通常放在一個(gè)專用塊中，專用塊的第1個(gè)單元給出下一組空閑盤塊的個(gè)數(shù)，第2個(gè)單元以后存放下一組空閑盤塊的地址；第二組有100個(gè)空閑盤塊，其地址放在第一組中的第一個(gè)空閑盤塊中，該塊的第1個(gè)單元給出第一組空閑盤塊的個(gè)數(shù)，第2個(gè)以后存放第二組空閑盤塊的地址；依次類推，組與組之間形成鏈接關(guān)系。最后一組有99個(gè)空閑盤塊，其地址放在前一組中的第一個(gè)空閑盤塊中，而該塊中的第2個(gè)單元填“0”，表示該塊中

60、存放的是最后一組的塊號(hào)，空閑塊鏈到些結(jié)束，這種方式稱為成組鏈接。</p><p>　　系統(tǒng)在初始化時(shí)先把專用塊內(nèi)容讀到內(nèi)存中，當(dāng)需分配空閑塊時(shí)，就直接在內(nèi)存中找到哪些塊是空閑的，每分配一塊后把空閑塊數(shù)減1.但在把一組中的第一個(gè)空閑塊分配出去之前，就把登記在該塊中的下一組的塊號(hào)及塊數(shù)保存到專用塊中。婁一組空閑塊被分配完后，則再把專用塊的內(nèi)容讀到內(nèi)存中，指出另一組可供分配的空閑塊。</p><p&

61、gt;　　圖2.12 成組鏈接</p><p>　　采用成組鏈接后，分配、回收空閑塊時(shí)均在內(nèi)存中查找和修改，只有在一組空閑塊分配完或空閑的磁盤塊構(gòu)成一組時(shí)才需要啟動(dòng)磁盤讀寫。因些，成組鏈接的管理方式比普通鏈接方式效率高。</p><p>　　第3章 編程環(huán)境介紹</p><p>　　3.1 Vmware</p><p>　　VMWare (

62、Virtual Machine ware)是一個(gè)“虛擬PC”軟件公司.它的產(chǎn)品可以使你在一臺(tái)機(jī)器上同時(shí)運(yùn)行二個(gè)或更多Windows、DOS、LINUX系統(tǒng)。與“多啟動(dòng)”系統(tǒng)相比，VMWare采用了完全不同的概念。多啟動(dòng)系統(tǒng)在一個(gè)時(shí)刻只能運(yùn)行一個(gè)系統(tǒng)，在系統(tǒng)切換時(shí)需要重新啟動(dòng)機(jī)器。VMWare是真正“同時(shí)”運(yùn)行，多個(gè)操作系統(tǒng)在主系統(tǒng)的平臺(tái)上，就象標(biāo)準(zhǔn)Windows應(yīng)用程序那樣切換。而且每個(gè)操作系統(tǒng)你都可以進(jìn)行虛擬的分區(qū)、配置而不影響真實(shí)硬

63、盤的數(shù)據(jù)，你甚至可以通過(guò)網(wǎng)卡將幾臺(tái)虛擬機(jī)用網(wǎng)卡連接為一個(gè)局域網(wǎng)，極其方便。安裝在VMware操作系統(tǒng)性能上比直接安裝在硬盤上的系統(tǒng)低不少，因此，比較適合學(xué)習(xí)和測(cè)試。</p><p>　　3.1.1 構(gòu)建虛擬機(jī)</p><p>　　1.運(yùn)行VMware Workstation 6，單擊“File→New→Virtual Machine”命令，進(jìn)入創(chuàng)建虛擬機(jī)向?qū)А?lt;/p><

64、;p>　　2.在彈出的歡迎頁(yè)中單擊“下一步”按鈕。 </p><p>　　3.在“Virtual machine configuration”選項(xiàng)區(qū)域內(nèi)選擇“Custom”單選按鈕。 </p><p>　　4.在Choose the Virtual Machine Hardware Compatibility頁(yè)中，選擇虛擬機(jī)的硬件格式，可以在Hardware compatibilit

65、y下拉列表框中，在VMware Workstation 6、VMware Workstation 5或VMware Workstation 4三者之間進(jìn)行選擇。通常情況下選擇Workstation 6的格式，因?yàn)樾碌奶摂M機(jī)硬件格式支持更多的功能，選擇好后單擊“下一步”按鈕。 </p><p>　　5.在Select a Guest Operating System對(duì)話框中，選擇要?jiǎng)?chuàng)建虛擬機(jī)類型及要運(yùn)行的操作系統(tǒng)，

66、這里選擇Windows 2000 Professional操作系統(tǒng)，單擊“下一步”按鈕。 </p><p>　　6.在Name the Virtual Machine對(duì)話框中，為新建的虛擬機(jī)命名并且選擇它的保存路徑。 </p><p>　　7.在Processors選項(xiàng)區(qū)域中選擇虛擬機(jī)中CPU的數(shù)量，如果選擇Two，主機(jī)需要有兩個(gè)CPU或者是超線程的CPU。 </p><

67、;p>　　8.在Memory for the Virtual Machine頁(yè)中，設(shè)置虛擬機(jī)使用的內(nèi)存，通常情況下，對(duì)于Windows 98及其以下的系統(tǒng)，可以設(shè)置64MB；對(duì)于Windows 2000/XP，最少可以設(shè)置96MB；對(duì)于Windows 2003，最低為128MB；對(duì)于Windows Vista虛擬機(jī)，最低512MB。 </p><p>　　9.在Network Type頁(yè)中選擇虛擬機(jī)網(wǎng)卡的“

68、聯(lián)網(wǎng)類型” </p><p>　　選擇第一項(xiàng)，使用橋接網(wǎng)卡(VMnet0虛擬網(wǎng)卡)，表示當(dāng)前虛擬機(jī)與主機(jī)(指運(yùn)行VMware Workstation軟件的計(jì)算機(jī))在同一個(gè)網(wǎng)絡(luò)中。 </p><p>　　選擇第二項(xiàng)，使用NAT網(wǎng)卡(VMnet8虛擬網(wǎng)卡)，表示虛擬機(jī)通過(guò)主機(jī)單向訪問(wèn)主機(jī)及主機(jī)之外的網(wǎng)絡(luò)，主機(jī)之外的網(wǎng)絡(luò)中的計(jì)算機(jī)，不能訪問(wèn)該虛擬機(jī)。 </p><p>　

69、　選擇第三項(xiàng)，只使用本地網(wǎng)絡(luò)(VMnet1虛擬網(wǎng)卡)，表示虛擬機(jī)只能訪問(wèn)主機(jī)及所有使用VMnet1虛擬網(wǎng)卡的虛擬機(jī)。主機(jī)之外的網(wǎng)絡(luò)中的計(jì)算機(jī)不能訪問(wèn)該虛擬機(jī)，也不能被該虛擬機(jī)所訪問(wèn)。 </p><p>　　選擇第四項(xiàng)，沒有網(wǎng)絡(luò)連接，表明該虛擬機(jī)與主機(jī)沒有網(wǎng)絡(luò)連接。 </p><p>　　10.在Select I/O Adapter Type頁(yè)中，選擇虛擬機(jī)的SCSI卡的型號(hào)，通常選擇默認(rèn)值

70、即可。 </p><p>　　11.在Select a Disk頁(yè)中，選擇Create a new virtual disk(創(chuàng)建一個(gè)新的虛擬硬盤)。 </p><p>　　12.在Select a Disk Type頁(yè)中，選擇創(chuàng)建的虛擬硬盤的接口方式，通常選擇默認(rèn)值即可。 </p><p>　　13.在Specify Disk Capacity頁(yè)中設(shè)置虛擬磁盤大小

71、，對(duì)于一般的使用來(lái)說(shuō)，選擇默認(rèn)值即可。 </p><p>　　14.在Specify Disk File頁(yè)的Disk file選項(xiàng)區(qū)域內(nèi)設(shè)置虛擬磁盤文件名稱，通常選擇默認(rèn)值即可，然后單擊完成按鈕。</p><p>　　3.1.2 安裝Linux操作系統(tǒng)</p><p>　　在虛擬機(jī)中安裝操作系統(tǒng)，和在 VMware真實(shí)的計(jì)算機(jī)中安裝沒有什么區(qū)別，但在虛擬機(jī)中安裝

72、操作系統(tǒng)，可以直接使用保存在主機(jī)上的安裝光盤鏡像(或者軟盤鏡像)作為虛擬機(jī)的光驅(qū)(或者軟驅(qū))。 　　</p><p>　　可以用打開前文創(chuàng)建的Windows 2000虛擬機(jī)配置文件，在Virtual Machine Settings頁(yè)中的Hardware選項(xiàng)卡中，選擇CD-ROM項(xiàng)，在Connection選項(xiàng)區(qū)域內(nèi)選中Use ISO image單選按鈕，然后瀏覽選擇Windows XP安裝光盤鏡像文件Red ha

73、t Enterprise Linux AS v5.4-i386-dvd.ISO。如果使用安裝光盤，則選擇Use physical drive并選擇安裝光盤所在光驅(qū)。 　　</p><p>　　選擇光驅(qū)完成后，然后單擊工具欄上的播放按鈕，打開虛擬機(jī)的電源，用鼠標(biāo)在虛擬機(jī)工作窗口中單擊一下，進(jìn)入虛擬機(jī)。 　　</p><p>　　以后在虛擬機(jī)中安裝操作系統(tǒng)，就和在主機(jī)中安裝一樣了。</p

74、><p>　　3.1.3 安裝VMware Tool</p><p>　　在虛擬機(jī)中安裝完操作系統(tǒng)之后，接下來(lái)需要安裝VMware Tools。VMware Tools相當(dāng)于VMware虛擬機(jī)的主板芯片組驅(qū)動(dòng)和顯卡驅(qū)動(dòng)、鼠標(biāo)驅(qū)動(dòng)，在安裝VMware Tools后，可以極大提高虛擬機(jī)的性能，并且可以讓虛擬機(jī)分辨率以任意大小進(jìn)行設(shè)置，還可以使用鼠標(biāo)直接從虛擬機(jī)窗口中切換到主機(jī)中，不需要Ctrl+A

75、lt。 </p><p>　　VMware Tools的安裝很簡(jiǎn)單： </p><p>　　1.從VM菜單下選擇安裝VMware Tools。 </p><p>　　2.按照提示安裝，最后重新啟動(dòng)虛擬機(jī)即可。</p><p>　　3.2 VI（VIM）編輯器</p><p>　　VI 編輯器是Visual interf

76、ace的簡(jiǎn)稱，通常稱之為VI。它在Linux上的地位就像Edit程序在DOS上一樣。它可以執(zhí)行輸出、刪除、查找、替換、塊操作等眾多文本操作，而且用戶可以根據(jù)自己的需要對(duì)其進(jìn)行定制，這是其他編輯程序所沒有的。 </p><p>　　VI 編輯器并不是一個(gè)排版程序，它不像Word或WPS那樣可以對(duì)字體、格式、段落等其他屬性進(jìn)行編排，它只是一個(gè)文本編輯程序。沒有菜單，只有命令，且命令繁多。Vi有3種基本工作模式：命令行

77、模式、文本輸入模式和末行模式。 </p><p>　　VIM是VI的加強(qiáng)版，比vi更容易使用。vi的命令幾乎全部都可以在vim上使用。</p><p>　　3.3 GCC編譯器</p><p>　　GCC（GNU Compiler Collection，GNU編譯器套裝），是一套由 GNU 開發(fā)的編程語(yǔ)言編譯器。它是一套 GNU編譯器套裝</p>&

78、lt;p>　　以 GPL 及 LGPL 許可證所發(fā)行的自由軟件，也是 GNU計(jì)劃的關(guān)鍵部分，亦是自由的類Unix及蘋果電腦 Mac OS X 操作系統(tǒng)的標(biāo)準(zhǔn)編譯器。 　　GCC 原名為 GNU C 語(yǔ)言編譯器，因?yàn)樗局荒芴幚?C語(yǔ)言。GCC 很快地?cái)U(kuò)展，變得可處理 C++。之后也變得可處理 Fortran、Pascal、Objective-C、Java, 以及 Ada與其他語(yǔ)言。</p><p>　　3

79、.3.1 GCC基本規(guī)則</p><p>　　gcc所遵循的部分約定規(guī)則： </p><p>　　.c為后綴的文件，C語(yǔ)言源代碼文件； </p><p>　　.a為后綴的文件，是由目標(biāo)文件構(gòu)成的檔案庫(kù)文件； </p><p>　　.C，.cc或.cxx 為后綴的文件，是C++源代碼文件； </p><p>　　.h為后

80、綴的文件，是程序所包含的頭文件； </p><p>　　.i 為后綴的文件，是已經(jīng)預(yù)處理過(guò)的C源代碼文件； </p><p>　　.ii為后綴的文件，是已經(jīng)預(yù)處理過(guò)的C++源代碼文件； </p><p>　　.m為后綴的文件，是Objective-C源代碼文件； </p><p>　　.o為后綴的文件，是編譯后的目標(biāo)文件； </p>

81、;<p>　　3.3.2 GCC基本用法</p><p>　　在使用Gcc編譯器的時(shí)候，我們必須給出一系列必要的調(diào)用參數(shù)和文件名稱。GCC編譯器的調(diào)用參數(shù)大約有100多個(gè)，其中多數(shù)參數(shù)我們可能根本就用不到，這里只介紹其中最基本、最常用的參數(shù)。 </p><p>　　GCC最基本的用法是∶gcc [options] [filenames] </p><p&g

82、t;　　其中options就是編譯器所需要的參數(shù)，filenames給出相關(guān)的文件名稱。 </p><p>　　-c，只編譯，不連接成為可執(zhí)行文件，編譯器只是由輸入的.c等源代碼文件生成.o為后綴的目標(biāo)文件，通常用于編譯不包含主程序的子程序文件。 </p><p>　　-o output_filename，確定輸出文件的名稱為output_filename，同時(shí)這個(gè)名稱不能和源文件同名。如

83、果不給出這個(gè)選項(xiàng)，gcc就給出預(yù)設(shè)的可執(zhí)行文件a.out。 </p><p>　　-g，產(chǎn)生符號(hào)調(diào)試工具(GNU的gdb)所必要的符號(hào)資訊，要想對(duì)源代碼進(jìn)行調(diào)試，我們就必須加入這個(gè)選項(xiàng)。 </p><p>　　-O，對(duì)程序進(jìn)行優(yōu)化編譯、連接，采用這個(gè)選項(xiàng)，整個(gè)源代碼會(huì)在編譯、連接過(guò)程中進(jìn)行優(yōu)化處理，這樣產(chǎn)生的可執(zhí)行文件的執(zhí)行效率可以提高，但是，編譯、連接的速度就相應(yīng)地要慢一些。 </

84、p><p>　　-O2，比-O更好的優(yōu)化編譯、連接，當(dāng)然整個(gè)編譯、連接過(guò)程會(huì)更慢。 </p><p>　　-Idirname，將dirname所指出的目錄加入到程序頭文件目錄列表中，是在預(yù)編譯過(guò)程中使用的參數(shù)。C程序中的頭文件包含兩種情況∶ </p><p>　　A)#include <myinc.h> </p><p>　　B)#i

85、nclude “myinc.h” </p><p>　　其中，A類使用尖括號(hào)(< >)，B類使用雙引號(hào)(“ ”)。對(duì)于A類，預(yù)處理程序cpp在系統(tǒng)預(yù)設(shè)包含文件目錄(如/usr/include)中搜尋相應(yīng)的文件，而B類，預(yù)處理程序在目標(biāo)文件的文件夾內(nèi)搜索相應(yīng)文件。</p><p>　　3.4 GDB調(diào)試工具</p><p>　　GDB是GNU開源組織發(fā)布的

86、一個(gè)強(qiáng)大的UNIX下的程序調(diào)試工具。</p><p>　　一般來(lái)說(shuō)，GDB主要幫助你完成下面四個(gè)方面的功能： </p><p>　　1、啟動(dòng)你的程序，可以按照你的自定義的要求隨心所欲的運(yùn)行程序。 </p><p>　　2、可讓被調(diào)試的程序在你所指定的調(diào)置的斷點(diǎn)處停住。（斷點(diǎn)可以是條件表達(dá)式） </p><p>　　3、當(dāng)程序被停住時(shí)，可以檢查

87、此時(shí)你的程序中所發(fā)生的事。 </p><p>　　4、動(dòng)態(tài)的改變你程序的執(zhí)行環(huán)境。</p><p>　　第四章 文件管理算法研究與模擬</p><p>　　文件系統(tǒng)對(duì)于設(shè)計(jì)和實(shí)現(xiàn)者來(lái)說(shuō)，他們感興趣的是，在磁盤上怎么樣安排文件和目錄存儲(chǔ)，如何管理磁盤空間以及怎樣使文件系統(tǒng)文件目錄等問(wèn)題。磁盤格式化時(shí)，系統(tǒng)把磁盤存儲(chǔ)空間分成許多磁道。每個(gè)磁道又分成若干個(gè)扇區(qū)（又叫做磁盤

88、塊）。之后用fdisk命令對(duì)硬盤進(jìn)行分區(qū)，即使只有一個(gè)分區(qū)，也必須用fdisk命令進(jìn)行分區(qū)。分區(qū)的目的，就是制作文件卷，形成文件系統(tǒng)。一個(gè)文件卷一般都被劃分成引導(dǎo)扇區(qū)、文件系統(tǒng)管理區(qū)和文件數(shù)據(jù)區(qū)。其中，文件數(shù)據(jù)區(qū)用來(lái)存放系統(tǒng)文件和用戶文件。用戶可以通過(guò)文件系統(tǒng)提供的API，創(chuàng)建、打開、關(guān)閉和對(duì)文件進(jìn)行讀寫。當(dāng)用戶的文件不再需要時(shí)，就應(yīng)該刪除。把一個(gè)文件放到磁盤上時(shí)，可以組織成連續(xù)文件、鏈接文件或索引文件等。因此，磁盤空間的分配方法也有兩

89、種，一種是連續(xù)空間的分配，一種是不連續(xù)空間的分配（又叫動(dòng)態(tài)分配）。</p><p>　　本章將研究磁盤空間的管理，目前大多操作系統(tǒng)用的方案是位示圖，空閑塊成組鏈表。</p><p>　　4.1 位示圖算法研究</p><p>　　假定現(xiàn)有一個(gè)磁盤組，共有40個(gè)柱面。每個(gè)柱面4個(gè)磁道，每個(gè)磁道又劃分成4個(gè)物理記錄。磁盤的空間使用情況用位示圖表示。位示圖用若干個(gè)字構(gòu)成，

90、每一位對(duì)應(yīng)一個(gè)磁盤道?！?”表示占用，“0”表示空閑。為了簡(jiǎn)單，假定字長(zhǎng)為16位，一個(gè)字可用來(lái)模擬磁盤的一個(gè)柱面，其位示圖如圖4.1所示。系統(tǒng)設(shè)置一個(gè)變量S記錄當(dāng)前的空閑磁盤塊個(gè)數(shù)。位示圖的初始狀態(tài)由戶自己設(shè)定。</p><p><b>　　圖4.1</b></p><p>　　申請(qǐng)一個(gè)磁盤塊時(shí)，由磁盤塊分配程序查位示圖，找出一個(gè)為0的位，并計(jì)算磁盤的物理地址（即求出

91、它的柱面號(hào)、磁道號(hào)和扇區(qū)號(hào)）。</p><p>　?、儆晌皇緢D計(jì)算磁盤的相對(duì)塊號(hào)的公式如下：</p><p>　　相對(duì)塊號(hào)=字號(hào)*16+位號(hào)</p><p>　?、谠賹⑾鄬?duì)塊號(hào)轉(zhuǎn)換成磁盤的物理地址：</p><p>　　柱面號(hào)=(相對(duì)塊號(hào)/16)的商，也即柱面號(hào)=字號(hào)</p><p>　　磁道號(hào)=（（相對(duì)塊號(hào)/16的余

92、數(shù)）/4）的商，也即（位號(hào)/4）的商</p><p>　　物理塊號(hào)=（（（相對(duì)塊號(hào)/16）的余數(shù)）/4）的余數(shù)，也即（位號(hào)/4）的余數(shù)</p><p>　　當(dāng)釋放一個(gè)相對(duì)物理塊時(shí)，運(yùn)行回收程序，計(jì)算該塊在位示圖中的位置，再把相應(yīng)由“1”改為“0”。計(jì)算公式如下：</p><p>　　先由磁盤的三維地址柱面號(hào)、磁道號(hào)和扇區(qū)號(hào)計(jì)算相對(duì)塊號(hào)：</p><

93、;p>　　相對(duì)塊號(hào)=柱面號(hào)*16+磁道號(hào)*4+物理塊號(hào)</p><p><b>　　再計(jì)算字號(hào)和位號(hào)：</b></p><p>　　字號(hào)=相對(duì)塊號(hào)/16的商，也即字號(hào)=柱面號(hào)</p><p>　　位號(hào)=磁道號(hào)*（物理塊數(shù)/每磁道）+物理塊號(hào)</p><p>　　分配算法和回收算法流程分別如圖4.2和4.3所示。&l

94、t;/p><p>　　圖4.2 磁盤空間分配的流程</p><p>　　圖4.2 磁盤空間回收的流程</p><p><b>　　4.2 位示圖模擬</b></p><p>　　程序用一個(gè)8*8的二維數(shù)組做為管理磁盤分配的位示圖，‘1’代表該磁盤塊已分配，‘0’代表未分配，詳細(xì)程序見附錄。程序模擬的結(jié)果圖如下 ：</p

95、><p>　　圖4.3 磁盤的分配</p><p>　　圖 4.4 磁盤的回收</p><p>　　4.3 UNIX系統(tǒng)文件管理成組連接算法</p><p>　　UNIX系統(tǒng)把每100個(gè)空閑塊作為一組，每一組的第一個(gè)空閑塊中登記下一組空閑塊的塊號(hào)和空閑塊數(shù)，余下不足100塊的那部分空閑塊的塊號(hào)及塊數(shù)登記在一個(gè)專用塊中，登記最后一組塊號(hào)的那個(gè)空閑塊

96、，其中第2個(gè)單元填“0”，表示該塊中指出的塊號(hào)是最后一組的塊號(hào)，空閑塊鏈到此結(jié)束。系統(tǒng)初始化時(shí)先把專用塊內(nèi)容讀到內(nèi)存，當(dāng)需分配空閑塊時(shí)，就直接在內(nèi)存中可找到哪些塊。 </p><p>　　但要把一組中的第一個(gè)空閑塊分配出去之前應(yīng)把登記在該塊中的下一組的塊號(hào)及塊數(shù)保存到專用塊中。 </p><p>　　當(dāng)一組空閑塊被分配完后，則再把專用塊的內(nèi)容讀到內(nèi)存，指出另一組可供分配的空閑塊。當(dāng)歸還一塊

97、時(shí)，只要把歸還塊的塊號(hào)登記到當(dāng)前組中且空閑塊數(shù)加1。如果當(dāng)前組已滿100塊，則把內(nèi)存中的內(nèi)容寫到歸還的那塊中，該歸還塊作為新組的第一塊。假設(shè)初始化時(shí)系統(tǒng)已把專用塊讀入內(nèi)存L單元開始的區(qū)域中，分配和回收的算法如下： </p><p>　　1、分配一個(gè)空閑塊 </p><p>　　查L(zhǎng)單元內(nèi)容（空閑塊數(shù)）： </p><p>　　當(dāng)空閑塊數(shù)>1, i :＝L＋空閑

98、塊數(shù)； </p><p>　　從i單元得到一空閑塊號(hào)； </p><p>　　把該塊分配給申請(qǐng)者； </p><p><b>　　空閑塊數(shù)減1。 </b></p><p>　　當(dāng)空閑塊數(shù)＝1 取出L＋1單元內(nèi)容（一組的第一塊塊號(hào)或0）； </p><p>　　其值＝0無(wú)空閑塊，申請(qǐng)者等待 <

99、/p><p>　　不等于零把該塊內(nèi)容復(fù)制到專用塊,該塊分配給申請(qǐng)者； </p><p>　　把專用塊內(nèi)容讀到主存L開始的區(qū)域。 </p><p><b>　　2、歸還一塊 </b></p><p>　　查L(zhǎng)單元的空閑塊數(shù)； </p><p>　　當(dāng)空閑塊數(shù)<100 空閑塊數(shù)加1； </p&

100、gt;<p>　　j :＝L＋空閑塊數(shù)； </p><p>　　歸還塊號(hào)填入j單元。 </p><p>　　當(dāng)空閑塊數(shù)＝100 把主存中登記的信息寫入歸還塊中； </p><p>　　把歸還塊號(hào)填入L＋1單元； </p><p><b>　　將L單元置成1。 </b></p><p>

101、;　　采用成組連接后，分配回收磁盤塊時(shí)均在內(nèi)存中查找和修改，只是在一組空閑塊分配完或空閑的磁盤塊構(gòu)成一組時(shí)才啟動(dòng)磁盤讀寫。比單塊連接方式效率高。</p><p>　　4.4 成組鏈接程序模擬</p><p>　　首先定義磁盤分配數(shù)組并初始化，9個(gè)一維數(shù)組分別表示9個(gè)空閑塊，程序運(yùn)行時(shí)，先將專用塊A〔0〕復(fù)制到內(nèi)存中，然后進(jìn)行功能選擇，分配時(shí)，查MA，從中找出空閑塊號(hào)，當(dāng)一組的空閑塊只剩第一

102、塊時(shí)，應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號(hào)復(fù)制到專用塊這，然后把該塊分配給申請(qǐng)者，當(dāng)一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復(fù)制到內(nèi)存，再為申請(qǐng)者分配。 回收時(shí)，輸入待回收的塊號(hào)，查找該塊是否已被分配，若未分配，退出，否則，當(dāng)前組不滿規(guī)定塊數(shù)時(shí)，將歸還塊登記入該組，若當(dāng)前組已滿，則另建一新組，這時(shí)歸還塊作為新一組的第一塊，應(yīng)把內(nèi)存中登記的一組鏈接情況MA復(fù)制到歸還塊中，然后在MA這重新登記一個(gè)新組。顯示分組情況。系統(tǒng)初始

103、化時(shí)先將專用塊內(nèi)容讀入 內(nèi)存 ，當(dāng)有申請(qǐng)空閑塊要求時(shí)，就直接在內(nèi)存專用塊中找到哪些塊是空閑的，每分配一塊后把空閑塊數(shù)減 1。但要把一組中第一塊分配出去之前，可以先把登記在該塊中的下一組的塊號(hào)保存在專用塊中(此時(shí) ，原專用塊中的信息巳經(jīng)無(wú)用了 ，因它指示的一組空閑塊都已分配掉)。當(dāng)中文組空閑塊分配完后,則將下一組內(nèi)容讀入內(nèi)存專用塊中，以便繼續(xù)分配時(shí)查找。</p><p><b>　　程序模擬圖如下：<

104、;/b></p><p>　　圖4.5 磁盤塊的分配</p><p>　　圖 4.6 磁盤的回收</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]湯小丹．計(jì)算機(jī)操作系統(tǒng)[M].西安：西安電子科技大學(xué)出版社，2007.05.</p><p>　　[2]西爾伯沙．實(shí)用操作

105、系統(tǒng)概念[M].北京：高等教育出版社，2001.</p><p>　　[3]陳向群. 操作系統(tǒng)教程[M].北京：北京大學(xué)出版社. 2006.6.</p><p>　　[4]張堯?qū)W.計(jì)算機(jī)操作系統(tǒng)教程[M].北京：清華大學(xué)出版社.2000.8.</p><p>　　[5]鳳羽.操作系統(tǒng)[M].北京:電子工業(yè)出版社,2004</p><p>　　

106、[6]馬季蘭.操作系統(tǒng)原理與Linux[M]. 北京:人民郵電出版社,2000</p><p>　　[7]孟靜.操作系統(tǒng)原理教程[M].北京:清華大學(xué)出版社,2000</p><p>　　[8]周蘇.操作系統(tǒng)原理實(shí)驗(yàn)[M].北京: 科學(xué)出版社,2000</p><p>　　[9]湯子瀛.計(jì)算機(jī)操作系統(tǒng)[M].西安：西安電子科技大學(xué)出版社,2001</p>

107、<p>　　[10]A.S.Tanenbaum.現(xiàn)代操作系統(tǒng)[M].北京：機(jī)械工業(yè)出版社，2002</p><p><b>　　致謝</b></p><p>　　非常感謝老師在我大學(xué)的最后學(xué)習(xí)階段——畢業(yè)設(shè)計(jì)階段給自己的指導(dǎo)，從最初的定題，到資料收集，到寫作、修改，到論文定稿，他給了我耐心的指導(dǎo)和無(wú)私的幫助。為了指導(dǎo)我們的畢業(yè)論文，他放棄了自己的休息時(shí)間

108、，他的這種無(wú)私奉獻(xiàn)的敬業(yè)精神令人欽佩，在此我向他表示我誠(chéng)摯的謝意。同時(shí)，感謝所有任課老師和所有同學(xué)在這四年來(lái)給自己的指導(dǎo)和幫助，是他們教會(huì)了我專業(yè)知識(shí)，教會(huì)了我如何學(xué)習(xí)，教會(huì)了我如何做人。正是由于他們，我才能在各方面取得顯著的進(jìn)步，在此向他們表示我由衷的謝意，并祝所有的老師培養(yǎng)出越來(lái)越多的優(yōu)秀人才，桃李滿天下！</p><p><b>　　附錄</b></p><p>

109、;<b>　　1、位示圖模擬</b></p><p>　　#include <stdio.h> </p><p>　　#include <stdlib.h> </p><p>　　void Initbitmap(int map[8][8]) </p><p><b>

110、;　　{ </b></p><p>　　int cylinder,track,sector;</p><p>　　char choice='Y';</p><p>　　printf("初始化位視圖...\n");</p><p>　　while(choice=='y'||cho

111、ice=='Y')</p><p><b>　　{</b></p><p>　　printf("柱面號(hào):");</p><p>　　scanf("%d",&cylinder);</p><p>　　printf("磁道號(hào):");</

112、p><p>　　scanf("%d",&track);</p><p>　　printf("物理記錄號(hào):");</p><p>　　scanf("%d",&sector);</p><p>　　map[cylinder][4*track+sector]=1;</p&

113、gt;<p>　　printf("contiune?");</p><p>　　getchar();</p><p>　　scanf("%c",&choice);</p><p><b>　　} </b></p><p><b>　　}

114、 </b></p><p>　　void allocate(int map[8][8]) </p><p><b>　　{ </b></p><p>　　int i,j; </p><p>　　int flag=0;</p><p>　　int cylinder,track

115、,sector;</p><p>　　for(i=0;i<8;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<8;j++) </p><p>　　if(map[i][j]==0) {map[i][j]=1;flag=1;break;} </p>

116、<p>　　if(flag==1) break; </p><p><b>　　}</b></p><p>　　if(flag==1)</p><p><b>　　{ </b></p><p>　　cylinder=i; </p><p>　　tr

117、ack=j/4; </p><p>　　sector=j%4; </p><p>　　printf("分配到的柱面號(hào)、磁道號(hào)、物理記錄數(shù)"); </p><p>　　printf("%d\t%d\t%d",cylinder,track,sector); </p><p>　　printf(