系統(tǒng)分析師考試重點(diǎn)與難點(diǎn)——位示圖

1、系統(tǒng)分析師考試重點(diǎn)與難點(diǎn)位示圖希賽軟考學(xué)院王勇位示圖法在近年的系統(tǒng)分析師考試中出現(xiàn)較為頻繁，屬于考試重點(diǎn)，該考點(diǎn)涉及的知識點(diǎn)的難度并不大，但如果考生從未學(xué)習(xí)過相關(guān)知識就很容易出錯(cuò)。故筆者從系統(tǒng)分析師考試全程指導(dǎo)與系統(tǒng)分析師考試綜合知識試題分類精解中選取部分內(nèi)容以及例題組成該文，供考生參考。閱讀本文即可應(yīng)對相關(guān)考題。位示圖法是操作系統(tǒng)中一種管理空閑存儲空間的方法。管理空閑空間除使用位示圖法還可用：空閑區(qū)表法、空閑鏈表法、成組鏈接法本文將詳細(xì)介紹這幾種方法。1.空閑區(qū)表法空閑表法屬于連續(xù)分配方式。它與內(nèi)存管理中的動(dòng)態(tài)分區(qū)分配方式雷同。將外存空間上一個(gè)連續(xù)未分配區(qū)域稱為“空閑區(qū)”。操作系統(tǒng)為磁盤外存

2、上所有空閑區(qū)建立一張空閑表，每個(gè)表項(xiàng)對應(yīng)一個(gè)空閑區(qū)，空閑表包含“序號，第一空閑盤塊號，空閑盤塊數(shù)”等信息。它適用于連續(xù)文件結(jié)構(gòu)。序號第一空閑盤塊號空閑盤塊數(shù)12429331554-空閑盤塊表它為每個(gè)文件分配一個(gè)連續(xù)的存儲空間。系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對應(yīng)于一個(gè)空閑表項(xiàng)。2.空閑鏈表法是將所有的空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈的基本元素的不同，可有兩種鏈表方式：空閑盤塊鏈、空閑盤區(qū)鏈。 空閑盤塊鏈它是將磁盤上的所有空閑存儲空間，以盤塊為基本元素拉成一條鏈。優(yōu)點(diǎn)是用于分配和回收一個(gè)盤塊的過程非常簡單；缺點(diǎn)是空閑盤塊鏈可能很長。 空閑盤區(qū)鏈這是將磁盤上的所有空閑盤區(qū)（每個(gè)

3、盤區(qū)可包含若干個(gè)盤塊）拉成一條鏈。在每個(gè)盤區(qū)上除了含有用于指示下一個(gè)空閑盤區(qū)的指針外，還應(yīng)標(biāo)有指明本盤區(qū)大?。ūP塊數(shù)）的信息。這方法分配和回收過程較復(fù)雜，但空閑盤區(qū)鏈較短。3.位示圖法這種方法是在外存上建立一張位示圖（bitmap），記錄文件存儲器的使用情況。每一位僅對應(yīng)文件存儲器上的一個(gè)物理塊，取值0和1分別表示空閑和占用。文件存儲器上的物理塊依次編號為：0、1、2、。位示圖是利用二進(jìn)制的一位來表示磁盤中一個(gè)盤塊的使用情況。當(dāng)其值為“0”時(shí)，表示對應(yīng)的盤塊空閑；為“1”時(shí)表示已分配。由所有盤塊對應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖。位示圖也可描述為一個(gè)二維數(shù)組map：Var map:array1.

4、m,1.nof bit;0123456789101112131415011000111001011101000111111000011121110001111110000315位示圖盤塊的分配根據(jù)位示圖進(jìn)行盤塊分配時(shí)，可分三步進(jìn)行： ·順序掃描位示圖，從中找出一個(gè)或一組值均為“0”的二進(jìn)制位； ·將找到的二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號； ·修改位示圖，令mapi,j=1。 盤塊的回收盤塊的回收分兩步： ·將回收盤塊的盤塊號轉(zhuǎn)換成位于圖中的行號和列號。轉(zhuǎn)換公式為： i=(b-1)DIVn+1 j=(b-1)MODn+1 ·修改位示圖。令mapi

5、,j=0。例題1某文件管理系統(tǒng)在磁盤上建立了位示圖(bitmap)，記錄磁盤的使用情況。若磁盤上的物理塊依次編號為：0、1、2、，系統(tǒng)中字長為32位，每一位對應(yīng)文件存儲器上的一個(gè)物理塊，取值0和1分別表示空閑和占用，如下圖所示。 31 30 3 2 1 00110001假設(shè)將4195號物理塊分配給某文件，那么該物理塊的使用情況在位示圖中的第_(1)_個(gè)字中描述；系統(tǒng)應(yīng)該將_(2)_。 （1） A. 128 B. 129 C. 130 D. 131 （2） A. 該字的第3位置“0” B. 該字的第3位置“1” C. 該字的第4位置“0” D. 該字的第4位置“1” 例題分析本題其實(shí)是一道死的計(jì)

6、算題，與專業(yè)知識沒有什么關(guān)系。因?yàn)槲锢韷K編號是從0開始的，所以4195號物理塊其實(shí)就是第4196塊。因?yàn)樽珠L為32位，也就是說，每個(gè)字可以記錄32個(gè)物理塊的使用情況。4196/32=131.125，所以，4195號物理塊應(yīng)該在第131個(gè)字中（字的編號也是從0開始計(jì)數(shù)）。那么，具體在第131個(gè)字的哪一位呢？到第130個(gè)字為止，共保存了131*32=4192個(gè)物理塊（04191），所以，第4195塊應(yīng)該在第131個(gè)字的第3位記錄（要注意：0是最開始的位）。因?yàn)橄到y(tǒng)已經(jīng)將4195號物理塊分配給某文件，所以其對應(yīng)的位要置1。例題答案 DB例題2某磁盤盤組共有10個(gè)盤面，每個(gè)盤面上有100個(gè)磁道，每個(gè)磁

7、道有32個(gè)扇區(qū)，假定物理塊的大小為2個(gè)扇區(qū)，分配以物理塊為單位。若使用位圖（bitmap）管理磁盤空間，則位圖需要占用_(3)_字節(jié)空間。若采用空白文件管理磁盤空間，且空白文件目錄的每個(gè)表項(xiàng)占用5個(gè)字節(jié)，則當(dāng)空白文件數(shù)目大于_(4)_時(shí)，空白文件目錄占用的字節(jié)數(shù)大于位圖占用的字節(jié)數(shù)。 （3）A. 32000 B. 3200 C. 2000 D. 1600 （4）A. 400 B. 360 C. 320 D. 160 例題分析位圖（位示圖）用二進(jìn)制位表示磁盤中的一個(gè)盤塊的使用情況，0表示空閑，1表示已分配。磁盤上的所有盤塊都與一個(gè)二進(jìn)制位相對應(yīng)，由所有的二進(jìn)制位構(gòu)成的集合，稱為位圖。位圖法的優(yōu)點(diǎn)

8、是很容易找到一個(gè)或一組相鄰的空閑盤塊。位圖小，可以把它保存在內(nèi)存中，從而節(jié)省了磁盤的啟動(dòng)操作。已知磁盤盤組共有10個(gè)盤面，每個(gè)盤面上有100個(gè)磁道，每個(gè)磁道有32個(gè)扇區(qū)，則一共有10*100*32=32000個(gè)扇區(qū)。試題又假定物理塊的大小為2個(gè)扇區(qū)，分配以物理塊為單位，即一共有16000個(gè)物理塊。因此，位圖所占的空間為16000/8=2000字節(jié)。若采用空白文件管理磁盤空間，且空白文件目錄的每個(gè)表項(xiàng)占用5個(gè)字節(jié)，2000/5=400，因此，則當(dāng)空白文件數(shù)目大于400時(shí)，空白文件目錄占用的字節(jié)數(shù)大于位圖占用的字節(jié)數(shù)。例題答案CA4.成組鏈接法 在UNIX系統(tǒng)中，將空閑塊分成若干組，每100個(gè)空閑塊為一組，每組的第一個(gè)空閑塊登記了下一組空間塊的物理盤塊號和空閑塊總數(shù)，假如一個(gè)組的第一個(gè)空閑塊號等于0的話，有特殊的含義，意味著該組是最后一組，即無下一組空閑塊。空閑表法和空閑鏈法，都不適合用在大型文件系統(tǒng)中。在UNIX中采用的成組鏈接法兼?zhèn)淞藘煞N方法的優(yōu)點(diǎn)而克服了兩種方法均有的、表太長的缺點(diǎn)?？臻e盤塊的組織空閑盤塊號棧。文件區(qū)中的所有空閑盤塊，被分成若干個(gè)組。·將每一組含有的盤塊總數(shù)N和該組所有的盤塊號，記入其前一組的第一個(gè)盤塊的 S.free(0)S.free(99)中。·將第一組的盤塊總數(shù)和所有的盤塊號，記入空閑盤塊號棧中。·最末一組