1、1,5.2.3 記錄成組技術(shù) 問題: 邏輯記錄的長度和物理塊大小不相等或不是整倍數(shù)時(shí)該如何處理? 記錄成組技術(shù)將多個(gè)邏輯記錄合成一組并保存在物理塊上的方法,2,1邏輯記錄長度為物理塊大小的整數(shù)因子 一個(gè)物理塊可以裝下整數(shù)個(gè)記錄。 計(jì)算記錄所在的相對(duì)塊號(hào)的方法是： 相對(duì)塊號(hào) = 記錄地址 DIN 物理塊大小 對(duì)于連續(xù)文件和串聯(lián)文件來說，知道了相對(duì)塊號(hào)和文件首地址，順序查找即可找到相應(yīng)的物理塊。,3,對(duì)于索引文件，要對(duì)索引表作適當(dāng)?shù)男薷摹?一種方法：利用文件的相對(duì)塊號(hào)作為索引，而不是記錄號(hào) 相對(duì)塊號(hào) = 記錄號(hào) DIN 每個(gè)物理塊存放的記錄數(shù) 再根據(jù)索引表查到相應(yīng)的物理塊號(hào)地址，最后確定該記錄在物

2、理塊中的地址，從而得到最終的地址。,4,對(duì)于哈希文件，一個(gè)物理塊容納多個(gè)記錄正好可以把Hash函數(shù)值相同的記錄放在同一個(gè)物理塊中來處理鍵值沖突，如果記錄填滿一個(gè)物理塊時(shí)，則可申請(qǐng)一個(gè)新的物理塊。,5,2邏輯記錄長度不為物理塊大小的整數(shù)因子 解決方法有三種： (1) 空間空閑法，即只存放整數(shù)個(gè)記錄，讓剩余空間空閑。 (2) 調(diào)整物理塊的大小?？梢愿鶕?jù)文件記錄長度改變磁盤的磁道、扇區(qū)劃分格式，使其可以放下整數(shù)個(gè)記錄。但一般說來，改變格式也不是十分方便的，況且還涉及到其它問題，如已經(jīng)存入的信息如何處理等，所以這種方法通常是不用的。,6,(3) 擴(kuò)充軟件法。這種辦法允許記錄跨物理塊存儲(chǔ)，并采用擴(kuò)充軟件

3、功能的辦法來適應(yīng)記錄的存取。如圖所示，第3條記錄在物理塊1和物理塊2中各有一部分。 算法： 根據(jù)邏輯地址，確定第三條記錄的始地址， 即記錄頭； 確定記錄的首地址所在的物理塊號(hào)； 計(jì)算記錄的首地址在物理塊內(nèi)的相對(duì)地址； 計(jì)算記錄在第一個(gè)物理塊中的有效長度； 計(jì)算記錄剩余的長度，如果等于0，則說明讀取完畢，否則計(jì)算出記錄剩余部分的邏輯地址。,7,5.2.4 文件存儲(chǔ)空間管理 文件的存儲(chǔ)有兩種策略： 一種是為文件分配連續(xù)的存儲(chǔ)空間，即連續(xù)的存儲(chǔ)塊 增加文件內(nèi)容需移動(dòng)；刪除文件會(huì)有碎片。 另一種是為文件分配不一定連續(xù)的塊。 現(xiàn)在幾乎所有的文件系統(tǒng)都把文件存儲(chǔ)空間分成固定大小的塊來存儲(chǔ)文件。存儲(chǔ)文件的塊

4、與塊之間不必相鄰。這樣，可以更有效地利用外存空間，但是分配和回收的速度可能會(huì)受到影響。,8,1塊大小的考慮 由于文件是按塊分配的，塊的大小是一個(gè)十分重要的問題。 如果塊過大，可能會(huì)造成空間的浪費(fèi)。塊過小，意味著每個(gè)文件都由許多塊組成，必然會(huì)影響文件的存取速度。 一般系統(tǒng)中，文件存儲(chǔ)塊的大小常采用512 B、1 KB或2 KB。當(dāng)然，隨著時(shí)間的推移，用戶對(duì)資源的需求在增加，塊的大小也應(yīng)隨之改變。例如，1984年調(diào)查表明，UNIX系統(tǒng)的文件大小平均在1 KB左右，而到1997年，一般系統(tǒng)中文件的平均長度已升至10 KB以上。,9,2空閑塊管理（物理塊的分配和回收的問題） 三種方法： 1) 空白文件

5、目錄 把一個(gè)連續(xù)的未分配區(qū)域（可能包含若干個(gè)空閑塊）看作一個(gè)文件，稱為空白文件。系統(tǒng)為所有的空白文件建立一個(gè)目錄，即空白文件目錄。每個(gè)空白文件對(duì)應(yīng)于空白文件目錄中的一個(gè)表目，分配回收類似內(nèi)存的可變式分區(qū)存儲(chǔ)管理算法（有合并）。,10,2) 空閑塊鏈接法 空閑塊鏈接法可以分為：空閑盤塊鏈、空閑盤區(qū)鏈及成組鏈接法。 (1) 空閑盤塊鏈 所有空閑盤塊鏈接在一起，設(shè)一個(gè)指針，指向鏈頭 空閑盤塊鏈法的分配與回收過程都十分簡單，但是空閑盤塊鏈可能會(huì)很長。,11,(2) 空閑盤區(qū)鏈。 空閑盤區(qū)鏈法是將若干連續(xù)的空閑盤塊作為一個(gè)空閑盤區(qū)，每個(gè)區(qū)含有一個(gè)指向下一個(gè)空閑盤區(qū)的指針及本空閑盤區(qū)大小的說明，所有空閑盤

6、區(qū)形成一個(gè)鏈，設(shè)一個(gè)指針，指向鏈頭，如圖5-16所示。 分配算法可以參考內(nèi)存的可變式分區(qū)存儲(chǔ)管理算法(有合并)。 為了提高對(duì)空閑盤區(qū)鏈的查找速度，通常在內(nèi)存建立空閑盤區(qū)的鏈表。 空閑盤區(qū)鏈法的分配與回收過程比較復(fù)雜，但是空閑盤區(qū)鏈較短。,12,(3) 成組鏈接法。 在UNIX系統(tǒng)中采用了一種改進(jìn)的方法。 它把文件存儲(chǔ)空間的空閑盤塊分組，再將每組具體的空閑盤塊號(hào)及個(gè)數(shù)記錄到另一組的第一個(gè)空閑盤塊中，組與組之間通過每組的第一塊鏈接起來，將當(dāng)前使用的一組空閑盤塊號(hào)及塊數(shù)放在空閑盤塊號(hào)棧中。 系統(tǒng)啟動(dòng)后，文件存儲(chǔ)空間的分配與回收通過已進(jìn)入內(nèi)存的空閑盤塊號(hào)棧進(jìn)行； ?？諘r(shí)，將鏈接的下一組空閑盤塊號(hào)及塊數(shù)

7、調(diào)入； 棧滿時(shí)，將棧中的空閑盤塊號(hào)作為一組，加入鏈中，這就是成組鏈接法，如圖5-17所示。,13,圖5-17 空閑盤塊的成組鏈接法,14,圖5-21 成組鏈接法的一次分配過程(分配三塊),15,圖5-18 成組鏈接法分配算法,16,圖5-20 成組鏈接法的一次回收過程 (回收12、125、65、156),17,圖5-19 成組鏈接法回收算法,18,5.2文件結(jié)構(gòu)和文件存取 5.2.1 文件邏輯結(jié)構(gòu)及文件存取(順序;直接;按鍵) 5.2.2 文件物理結(jié)構(gòu) 連續(xù);鏈接;索引(簡單;鏈接式;多級(jí)索引);散列 5.2.3 記錄成組技術(shù) 5.2.4 文件存儲(chǔ)空間管理 1.塊大小的考慮 2.空閑塊管理 1

8、)空白文件目錄 2)空閑塊鏈接法(空閑盤塊鏈;空閑盤區(qū)鏈;成組鏈接法) 3)位示圖 3.磁盤I/O調(diào)度算法,19,3) 位示圖 通過位示圖進(jìn)行文件存儲(chǔ)空間的分配與回收。 首先，為文件存儲(chǔ)空間建立位示圖，位示圖中的字位與文件存儲(chǔ)空間的物理塊一一對(duì)應(yīng)，反映文件存儲(chǔ)空間的使用情況。 在位示圖中，字位為0，表示對(duì)應(yīng)物理塊是空閑的；字位為1，表示對(duì)應(yīng)的物理塊已被占用。 假如0字0位對(duì)應(yīng)文件存儲(chǔ)空間的200號(hào)物理塊，則1字8位的0表示文件存儲(chǔ)空間的224號(hào)物理塊是空閑塊，而2字0位的1表示文件存儲(chǔ)空間的232號(hào)物理塊是已被占用的，如圖5-22所示。,20,圖5-22 位示圖,21,分配時(shí)，需要將位示圖中為

9、0的字位換算成對(duì)應(yīng)的文件存儲(chǔ)空間的物理塊號(hào)，并修改字位為1； 回收時(shí)，需要將回收的物理塊號(hào)對(duì)應(yīng)于位示圖的相應(yīng)字位，并將其置為0，以備后用。 例如圖5-22所示， 分配時(shí)，若找出i行j列為0，則可知其對(duì)應(yīng)的空閑塊號(hào)b=i16+j+200，分配b塊后，將i行j列置為1。 回收時(shí)，若回收塊號(hào)為b，則位示圖上對(duì)應(yīng)位號(hào)為 i=(b-200) DIN 16 j=(b-200) MOD 16 然后就可將i行j列置為0.,22,3磁盤I/O調(diào)度算法 磁盤是可以被多個(gè)進(jìn)程共享的設(shè)備。當(dāng)進(jìn)程有磁盤I/O請(qǐng)求時(shí)，通常將進(jìn)程阻塞在磁盤I/O的等待隊(duì)列上。對(duì)于阻塞在磁盤I/O等待隊(duì)列上的進(jìn)程，應(yīng)選擇適當(dāng)?shù)恼{(diào)度算法，使得

10、進(jìn)程的平均尋道時(shí)間為最少，又不致落下某些進(jìn)程，使之得不到調(diào)度。 1) 先來先服務(wù)調(diào)度算法(FCFS) 根據(jù)進(jìn)程訪問磁盤的先后次序進(jìn)行調(diào)度。該算法簡單、公平，每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)落下某些進(jìn)程的請(qǐng)求。但是當(dāng)磁盤I/O阻塞隊(duì)列中相鄰進(jìn)程訪問磁道的跳躍性較大時(shí)，則尋道長度較大，尋道時(shí)間較長。,23,2) 最短尋道時(shí)間優(yōu)先調(diào)度算法(SSTF) 選擇與當(dāng)前磁頭所在磁道距離最近的進(jìn)程I/O請(qǐng)求進(jìn)行調(diào)度，使得每次的尋道長度與時(shí)間最短。 這種調(diào)度算法通常比先來先服務(wù)調(diào)度算法有較好的調(diào)度性能，但是當(dāng)磁頭所在磁道附近不斷有新的I/O請(qǐng)求到達(dá)時(shí)，則距離磁頭位置較遠(yuǎn)進(jìn)程的I/O請(qǐng)求可能被落下，長時(shí)間得不到調(diào)度，以致被“餓死”。,24,3) 掃描算法(SCAN) 掃描算法是當(dāng)前磁頭沿一個(gè)方向移動(dòng)時(shí)，對(duì)所遇到的磁道上的I/O請(qǐng)求依次響應(yīng)，直至該移動(dòng)方向再無I/O請(qǐng)求時(shí)，磁臂換向；磁頭向反方向移動(dòng)時(shí)，再對(duì)所遇磁道上的I/O請(qǐng)求依次響應(yīng)，往返交替。這種調(diào)度算法可以防止最短尋道時(shí)間優(yōu)先調(diào)度算法中某些進(jìn)程被“餓死”的現(xiàn)象。 掃描算法有較好的尋道性能，但是當(dāng)有進(jìn)程的I/O請(qǐng)求到達(dá)剛被掃描過的磁道時(shí)，則這個(gè)請(qǐng)求會(huì)被推遲，直到磁頭沿此方向掃描到頭換向后，再次掃描到這個(gè)I/O請(qǐng)求