操作系統文件管理算法研究畢業論文(編輯修改稿)

　

【文章內容簡介】 意大小進行設置，還可以使用鼠標直接從虛擬機窗口中切換到主機中，不需要Ctrl+Alt。 VMware Tools的安裝很簡單： 　　 Tools。 ，最后重新啟動虛擬機即可。 VI（VIM）編輯器 　VI 編輯器是Visual interface的簡稱，通常稱之為VI。它在Linux上的地位就像Edit程序在DOS上一樣。它可以執行輸出、刪除、查找、替換、塊操作等眾多文本操作，而且用戶可以根據自己的需要對其進行定制，這是其他編輯程序所沒有的。 　　VI 編輯器并不是一個排版程序，它不像Word或WPS那樣可以對字體、格式、段落等其他屬性進行編排，它只是一個文本編輯程序。沒有菜單，只有命令，且命令繁多。Vi有3種基本工作模式：命令行模式、文本輸入模式和末行模式。 VIM是VI的加強版，比vi更容易使用。vi的命令幾乎全部都可以在vim上使用。 GCC編譯器GCC（GNU Compiler Collection，GNU編譯器套裝），是一套由 GNU 開發的編程語言編譯器。它是一套 GNU編譯器套裝以 GPL 及 LGPL 許可證所發行的自由軟件，也是 GNU計劃的關鍵部分，亦是自由的類Unix及蘋果電腦 Mac OS X 操作系統的標準編譯器。 　　GCC 原名為 GNU C 語言編譯器，因為它原本只能處理 C語言。GCC 很快地擴展，變得可處理 C++。之后也變得可處理 Fortran、Pascal、ObjectiveC、Java, 以及 Ada與其他語言。 GCC基本規則gcc所遵循的部分約定規則： 　　.c為后綴的文件，C語言源代碼文件； 　　.a為后綴的文件，是由目標文件構成的檔案庫文件； 　　.C，. 為后綴的文件，是C++源代碼文件； 　　.h為后綴的文件，是程序所包含的頭文件； 　　.i 為后綴的文件，是已經預處理過的C源代碼文件； 　　.ii為后綴的文件，是已經預處理過的C++源代碼文件； 　　.m為后綴的文件，是ObjectiveC源代碼文件； 　　.o為后綴的文件，是編譯后的目標文件； GCC基本用法在使用Gcc編譯器的時候，我們必須給出一系列必要的調用參數和文件名稱。GCC編譯器的調用參數大約有100多個，其中多數參數我們可能根本就用不到，這里只介紹其中最基本、最常用的參數。 　　GCC最基本的用法是∶gcc [options] [filenames] 　　其中options就是編譯器所需要的參數，filenames給出相關的文件名稱。 　　c，只編譯，不連接成為可執行文件，通常用于編譯不包含主程序的子程序文件。 　　o output_filename，確定輸出文件的名稱為output_filename，同時這個名稱不能和源文件同名。如果不給出這個選項。 　　g，產生符號調試工具(GNU的gdb)所必要的符號資訊，要想對源代碼進行調試，我們就必須加入這個選項。 　　O，對程序進行優化編譯、連接，采用這個選項，整個源代碼會在編譯、連接過程中進行優化處理，這樣產生的可執行文件的執行效率可以提高，但是，編譯、連接的速度就相應地要慢一些。 　　O2，比O更好的優化編譯、連接，當然整個編譯、連接過程會更慢。 　　Idirname，將dirname所指出的目錄加入到程序頭文件目錄列表中，是在預編譯過程中使用的參數。C程序中的頭文件包含兩種情況∶ 　　A)include 　　B)include “” 其中，A類使用尖括號( )，B類使用雙引號(“ ”)。對于A類，預處理程序cpp在系統預設包含文件目錄(如/usr/include)中搜尋相應的文件，而B類，預處理程序在目標文件的文件夾內搜索相應文件。 GDB調試工具GDB是GNU開源組織發布的一個強大的UNIX下的程序調試工具。一般來說，GDB主要幫助你完成下面四個方面的功能： 　　啟動你的程序，可以按照你的自定義的要求隨心所欲的運行程序。 　　可讓被調試的程序在你所指定的調置的斷點處停住。（斷點可以是條件表達式） 　　當程序被停住時，可以檢查此時你的程序中所發生的事。 　　動態的改變你程序的執行環境。第四章 文件管理算法研究與模擬文件系統對于設計和實現者來說，他們感興趣的是，在磁盤上怎么樣安排文件和目錄存儲，如何管理磁盤空間以及怎樣使文件系統文件目錄等問題。磁盤格式化時，系統把磁盤存儲空間分成許多磁道。每個磁道又分成若干個扇區（又叫做磁盤塊）。之后用fdisk命令對硬盤進行分區，即使只有一個分區，也必須用fdisk命令進行分區。分區的目的，就是制作文件卷，形成文件系統。一個文件卷一般都被劃分成引導扇區、文件系統管理區和文件數據區。其中，文件數據區用來存放系統文件和用戶文件。用戶可以通過文件系統提供的API，創建、打開、關閉和對文件進行讀寫。當用戶的文件不再需要時，就應該刪除。把一個文件放到磁盤上時，可以組織成連續文件、鏈接文件或索引文件等。因此，磁盤空間的分配方法也有兩種，一種是連續空間的分配，一種是不連續空間的分配（又叫動態分配）。本章將研究磁盤空間的管理，目前大多操作系統用的方案是位示圖，空閑塊成組鏈表。 位示圖算法研究假定現有一個磁盤組，共有40個柱面。每個柱面4個磁道，每個磁道又劃分成4個物理記錄。磁盤的空間使用情況用位示圖表示。位示圖用若干個字構成，每一位對應一個磁盤道。“1”表示占用，“0”表示空閑。為了簡單，假定字長為16位，一個字可用來模擬磁盤的一個柱面。系統設置一個變量S記錄當前的空閑磁盤塊個數。位示圖的初始狀態由戶自己設定。申請一個磁盤塊時，由磁盤塊分配程序查位示圖，找出一個為0的位，并計算磁盤的物理地址（即求出它的柱面號、磁道號和扇區號）。①由位示圖計算磁盤的相對塊號的公式如下： 相對塊號=字號*16+位號②再將相對塊號轉換成磁盤的物理地址： 柱面號=(相對塊號/16)的商，也即柱面號=字號 磁道號=（（相對塊號/16的余數）/4）的商，也即（位號/4）的商 物理塊號=（（（相對塊號/16）的余數）/4）的余數，也即（位號/4）的余數當釋放一個相對物理塊時，運行回收程序，計算該塊在位示圖中的位置，再把相應由“1”改為“0”。計算公式如下： 先由磁盤的三維地址柱面號、磁道號和扇區號計算相對塊號： 相對塊號=柱面號*16+磁道號*4+物理塊號 再計算字號和位號： 字號=相對塊號/16的商，也即字號=柱面號 位號=磁道號*（物理塊數/每磁道）+物理塊號。 磁盤空間分配的流程 磁盤空間回收的流程 位示圖模擬 程序用一個8*8的二維數組做為管理磁盤分配的位示圖，‘1’代表該磁盤塊已分配，‘0’代表未分配，詳細程序見附錄。程序模擬的結果圖如下 ： 磁盤的分配圖 磁盤的回收 UNIX系統文件管理成組連接算法UNIX系統把每100個空閑塊作為一組，每一組的第一個空閑塊中登記下一組空閑塊的塊號和空閑塊數，余下不足100塊的那部分空閑塊的塊號及塊數登記在一個專用塊中，登記最后一組塊號的那個空閑塊，其中第2個單元填“0”，表示該塊中指出的塊號是最后一組的塊號，空閑塊鏈到此結束。系統初始化時先把專用塊內容讀到內存，當需分配空閑塊時，就直接在內存中可找到哪些塊。 但要把一組中的第一個空閑塊分配出去之前應把登記在該塊中的下一組的塊號及塊數保存到專用塊中。 當一組空閑塊被分配完后，則再把專用塊的內容讀到內存，指出另一組可供分配的空閑塊。當歸還一塊時，只要把歸還塊的塊號登記到當前組中且空閑塊數加1。如果當前組已滿100塊，則把內存中的內容寫到歸還的那塊中，該歸還塊作為新組的第一塊。假設初始化時系統已把專用塊讀入內存L單元開始的區域中，分配和回收的算法如下： 分配一個空閑塊 查L單元內容（空閑塊數）： 當空閑塊數1, i :＝L＋空閑塊數； 從i單元得到一空閑塊號； 把該塊分配給申請者； 空閑塊數減1。 當空閑塊數＝1 取出L＋1單元內容（一組的第一塊塊號或0）； 其值＝0無空閑塊，申請者等待 不等于零把該塊內容復制到專用塊,該塊分配給申請者； 把專用塊內容讀到主存L開始的區域。 歸還一塊 查L單元的空閑塊數； 當空閑塊數100 空閑塊數加1； j :＝L＋空閑塊數； 歸還塊號填入j單元。 當空閑塊數＝100 把主存中登記的信息寫入歸還塊中； 把歸還塊號填入L＋1單元； 將L單元置成1。 采用成組連接后，分配回收磁盤塊時均在內存中查找和修改，只是在一組空閑塊分配完或空閑的磁盤塊構成一組時才啟動磁盤讀寫。比單塊連接方式效率高。 成組鏈接程序模擬首先定義磁盤分配數組并初始化，9個一維數組分別表示9個空閑塊，程序運行時，先將專用塊A〔0〕復制到內存中，然后進行功能選擇，分配時，查MA，從中找出空閑塊號，當一組的空閑塊只剩第一塊時，應把該塊中指出的下一組的空閑塊數和塊號復制到專用塊這，然后把該塊分配給申請者，當一組的空閑塊分配完后則把專用塊內容（下一組鏈接情況）復制到內存，再為申請者分配。 回收時，輸入待回收的塊號，查找該塊是否已被分配，若未分配，退出，否則，當前組不滿規定塊數時，將歸還塊登記入該組，若當前組已滿，則另建一新組，這時歸還塊作為新一組的第一塊，應把內存中登記的一組鏈接情況MA復制到歸還塊中，然后在MA這重新登記一個新組。顯示分組情況。系統初始化時先將專用塊內容讀入 內存 ，當有申請空閑塊要求時，就直接在內存專用塊中找到哪些塊是空閑的，每分配一塊后把空閑塊數減 1。但要把一組中第一塊分配出去之前，可以先把登記在該塊中的下一組的塊號保存在專用塊中(此時 ，原專用塊中的信息巳經無用了 ，因它指示的一組空閑塊都已分配掉)。當中文組空閑塊分配完后,則將下一組內容讀入內存專用塊中，以便繼續分配時查找。程序模擬圖如下： 磁盤塊的分配圖 磁盤的回收參考文獻[1]湯小丹．計算機操作系統[M].西安：西安電子科技大學出版社，.[2]西爾伯沙．實用操作系統概念[M].北京：高等教育出版社，2001.[3]陳向群. 操作系統教程[M].北京：北京大學出版社. .[4][M].北京：.[5][M].北京:電子工業出版社,2004[6][M]. 北京:人民郵電出版社,2000[7][M].北京:清華大學出版社,2000[8][M].北京: 科學出版社,2000[9][M].西安：西安電子科技大學出版社,2001[10][M].北京：機械工業出版社，2002致謝非常感謝老師在我大學的最后學習階段——畢業設計階段給自己的指導，從最初的定題，到資料收集，到寫作、修改，到論文定稿，他給了我耐心的指導和無私的幫助。為了指導我們的畢業論文，他放棄了自己的休息時間，他的這種無私奉獻的敬業精神令人欽佩，在此我向他表示我誠摯的謝意。同時，感謝所有任課老師和所有同學在這四年來給自己的指導和幫助，是他們教會了我專業知識，教會了我如何學習，教會了我如何做人。正是由于他們，我才能在各方面取得顯著的進步，在此向他們表示我由衷的謝意，并祝所有的老師培養出越來越多的優秀人才，桃李滿天下！附錄位示圖模擬include include