每一個可以努力的日子,都是一份厚禮。
連續磁盤存儲空間的分配和回收
一、實習內容
模擬磁盤空閑空間的表示方法,以及模擬實現磁盤空間的分配和回收。
二、實習目的
磁盤初始化時把磁盤存儲空間分成許多塊(扇區),這些空間可以被多個用戶共享。用戶作業在執行期間常常要在磁盤上建立文件或把已經建立在磁盤上的文件刪去,這就涉及到磁盤存儲空間的分配和回收。一個文件存放到磁盤上,可以組織成順序文件(連續文件)、鏈接文件(串聯文件)、索引文件等,因此,磁盤存儲空間的分配有兩種方式,一種是分配連續的存儲空間,另一種是可以分配不連續的存儲空間。怎樣有效地管理磁盤存儲空間是操作系統應解決的一個重要問題,通過本實習來掌握磁盤存儲空間的分配和回收算法。
三、實習題目
連續磁盤存儲空間的分配和回收
四、設計思想
1.設計思路
(1)要在磁盤上建立順序文件時,必須把按序排列的邏輯記錄依次存放在磁盤的連續存儲空間中。可假定磁盤初始化時,已把磁盤存儲空間劃分成若干等長的塊(扇區),按柱面號和盤面號的順序給每一塊確定一個編號。隨着文件的建立、刪除、磁盤存儲空間被分成許多區(每一區包含若干塊),有的區存放着文件,而有的區是空閑的。當要建立順序文件時必須找到一個合適的空閑區來存放文件記錄,當一個文件被刪除時,則該文件佔用的區應成為空閑區。為此可用一張空閑區表來記錄磁盤存儲空間中尚未佔用的部分,格式如下:
序號 起始空閑塊號 空閑塊個數 狀態
1 5 6 未 分 配
2 14 3 未 分 配
3 21 30 未 分 配
4 空 表 目
(2)建立文件時,先查找空閑區表,從狀態為“未分配”的表項中找出一個塊數能滿足要求的區,由起始空閑塊號能依次推得可使用的其它塊號。若不需要佔用該區的所有塊時,則剩餘的塊仍應為未分配的空閑塊,這時要修改起始空閑塊號和空閑塊數。若佔用了該區的所有塊,則相應登記欄中的狀態修改成“空表目”。刪除一個文件時,需要考慮空閑塊的合併情況。
(3)當找到空閑塊後,必須啟動磁盤把信息存放到指定的塊中,啟動磁盤必須給出由三個參數組成的物理地址:盤面號、柱面號和物理記錄號(即扇區號)。故必須把找到的空閑塊號換算成磁盤的物理地址。
為了減少移臂次數,磁盤上的信息按柱面上各磁道順序存放。現假定一個盤組共有200個柱面,(編號0-199)每個柱面有20個磁道(編號0-19,同一柱面上的各磁道分布在各盤面上,故磁道號即盤面號),每個磁道被分成等長的6個物理記錄(編號0-5,每個盤面被分成若干個扇區,故每個磁道上的物理記錄號即為對應的扇區號)。那麼,空閑塊號與磁盤物理地址的對應關係如下:
物理記錄號 = 空閑塊號 % 6
磁道號 = (空閑塊號 / 6 )% 20
柱面號 = (空閑塊號 / 6)/ 20
(4)刪除一個文件時,從文件目錄表中可得到該文件在磁盤上的起始地址和邏輯記錄個數,假定每個邏輯記錄占磁盤上的一塊,則可推算出歸還後的起始空閑塊號和塊數,登記到空閑區表中。換算關係如下:
起始空閑塊號 = (柱面號20 + 磁道號)6 + 物理記錄號
空閑塊數 = 邏輯記錄數
(5)設計磁盤存儲空間的分配和回收程序,把分配到的空閑塊轉換成磁盤物理地址,把歸還的磁盤空間轉換成空閑塊號。
2.主要數據結構
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | struct FreeBlockMenu { long FBbegin;//起始空閑塊號 long num;//空閑塊個數 struct FreeBlockMenu *next; struct FreeBlockMenu *front; }; struct FiletoWrite { char name[10];//裝入的文件名,供回收磁盤空間時查找 long size;//文件大小 long addr_zhumian;//裝入磁盤的首地址_柱面號 long addr_cidao;//裝入磁盤的首地址_磁道號 long addr_jilu;//裝入磁盤的首地址_物理記錄號 struct FiletoWrite *next; struct FiletoWrite *front; }; |
3.主要代碼結構及代碼段分析
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 | //分配磁盤空間 int getMalloc() { int flag = 0; struct FreeBlockMenu *p = FBhead; struct FiletoWrite *File; File = (struct FiletoWrite *)malloc(sizeof(struct FiletoWrite)); printf("請輸入裝入的文件名:\n"); scanf("%10s",File->name); printf("請輸入所需要的磁盤空間大小:\n"); scanf("%d",&File->size); for(p = FBhead->next;p != NULL;p = p->next) { flag = 1; if(p->num >= File->size ) { //分配空間,塊號轉化為物理地址 File->addr_zhumian = (p->FBbegin/6)/20; File->addr_cidao = (p->FBbegin/6)%20; File->addr_jilu = p->FBbegin%6; //加入文件鏈表中 File->next = Filehead->next; if(Filehead->next != NULL) Filehead->next->front = File; Filehead->next = File; File->front = Filehead; if(p->num > File->size) { //修改該塊的起始地址和塊數 p->FBbegin = p->FBbegin + File->size; p->num = p->num - File->size; } else if(p->num == File->size) { //從空閑塊表中刪除該結點 if(p->front != NULL) { if(p->next != NULL) { p->front->next = p->next; p->next->front = p->front; free(p); } else { p->front->next = p->next; free(p); } } else { p->next->front = p->front; free(p); } } printf("\n分配磁盤成功!\n該文件的物理地址為:(柱面號 磁道號 物理塊號)\n"); printf(" %d %d %d\n",File->addr_zhumian,File->addr_cidao,File->addr_jilu); } } if(flag == 0) { printf("對不起,目前沒有足夠的磁盤空間分配給該文件。"); return 0; } } int showDisk(); //回收磁盤空間 int setFree() { char name[10]; int flag = 0; struct FiletoWrite *p = Filehead; printf("請輸入要刪除的文件名:\n"); scanf("%10s",&name); for(p = Filehead;p != NULL;p = p->next) { if(strcmp(p->name , name)==0)//找到該文件 { flag = 1; int houhebing=0,qianhebing=0; long m = p->addr_zhumian; long n = p->addr_cidao; long k = p->addr_jilu; long addr =120*m + 6*n + k;//塊號 //先考慮和後面的部分或許會有合併的情況 long int tail=addr+p->size; struct FreeBlockMenu *pNode,*qNode; pNode=FBhead->next; while(pNode!=NULL) { if(pNode->FBbegin==tail) { pNode->FBbegin=addr; pNode->num=pNode->num+p->size; houhebing=1; qNode=pNode; break; } pNode=pNode->next; } //再考慮是否可以和前面的進行合併 pNode=FBhead->next; while(pNode!=NULL) { if(pNode->FBbegin+pNode->num==addr) { if(houhebing==0) { pNode->num=pNode->num+p->size; qianhebing=1; break; } else if(houhebing==1) { pNode->num+=qNode->num; pNode=FBhead; while(pNode->next!=qNode) pNode=pNode->next; pNode->next=qNode->next; free(qNode); qianhebing=1; break; } } pNode=pNode->next; } //如果沒有和前面的或者後面的進行合併,則新建一個表目 if(qianhebing==0 && houhebing==0) { pNode=(struct FreeBlockMenu*)malloc(sizeof(struct FreeBlockMenu)); pNode->FBbegin=addr; pNode->num=p->size; if(FBhead->next==NULL) { FBhead->next=pNode; pNode->front=FBhead; pNode->next=NULL; FBhead->front=NULL; } else { pNode->next=FBhead->next; FBhead->next->front=pNode; FBhead->next=pNode; pNode->front=FBhead; } } //在文件鏈表中刪除該文件 struct FiletoWrite *pPrev=p->front; if(p->next==NULL) { pPrev->next=NULL; free(p); } else { pPrev->next=p->next; p->next->front=pPrev; } } } if(flag == 0) printf("沒有該文件!\n"); else printf("刪除文件成功!\n"); } //顯示磁盤空閑區表 int showDisk() { struct FreeBlockMenu *p = FBhead; printf("\n磁盤空閑塊表\n"); printf("起始地址 空閑塊大小\n"); for(p = FBhead->next;p != NULL;p = p->next) printf(" %ld %ld\n",p->FBbegin,p->num); } int main() { char choose; FBhead = (struct FreeBlockMenu *)malloc(sizeof(struct FreeBlockMenu)); if(FBhead == NULL) { printf("error in allocating...\n"); } else printf("successed\n"); struct FreeBlockMenu *pNew=(struct FreeBlockMenu*)malloc(sizeof(struct FreeBlockMenu)); pNew->FBbegin = 0; pNew->num = 24000; pNew->next = pNew->front = NULL; FBhead->next=pNew; FBhead->front=NULL; pNew->front=FBhead; pNew->next=NULL; Filehead = (struct FiletoWrite *)malloc(sizeof(struct FiletoWrite)); Filehead->next = Filehead->front = NULL; char buf[128]; do { system("clear"); printf("---------------------------\n"); printf("1.請求磁盤空間\n"); printf("2.回收磁盤空間\n"); printf("3.顯示磁盤空閑區表\n"); printf("4.退出\n"); printf("---------------------------\n"); printf("請選擇:"); scanf("%c",&choose); switch(choose) { case '1': getMalloc(); gets(buf);break; case '2': setFree(); gets(buf);break; case '3': showDisk(); gets(buf);break; case '4': exit(1);break; default: gets(buf); printf("輸入錯誤!請重新輸入。\n"); break; } printf("\n"); getchar(); }while(choose != '4'); } |
五、上機實習所用平台及相關軟件
本程序在Linux平台(Ubuntu8.04.1)下,使用vi編輯器編寫,g++編譯通過。
六、調試過程
測試數據:
文件名 請求磁盤空間大小
aaa 20
bbb 1000
ccc 2000
ddd 3000
測試結果:
截圖(略)
七、總結
(1)磁盤空閑區表和文件的數據結構我均使用了雙鏈表來構建,這樣可以很方便地訪問到前驅節點,更容易進行鏈表節點的刪除操作,節省了很多時間。
(2)在程序中充分考慮到出錯處理。比如在功能選擇菜單中,若用戶輸入非法字符則提示“輸入錯誤!請重新輸入”;在用戶申請磁盤空間時,若要求的空間大小大於空閑空間大小,則提示“沒有足夠的磁盤空間”;在回收磁盤空間時,若用戶輸入的文件名不存在,則提示“沒有該文件”。這樣提高了程序的健壯性。
(3)在回收磁盤空間時,分情況討論空閑塊的合併。先考慮和後面的空閑塊或許會有合併的情況,再考慮是否可以和前面的塊進行合併,如果沒有和前面或者後面的空閑塊進行合併,則新建一個表目。這樣程序結構清晰,邏輯性強。
(4)通過本實驗,我進一步加深了對連續磁盤空間的分配回收過程的理解,同時也得到了將系統理論實踐的機會,熟練了編程能力。
這篇文章由lovelucy於2008-12-24 15:17發表在後端架構。你可以訂閱RSS 2.0 也可以發表評論或引用到你的網站。除特殊說明外文章均為本人原創,並遵從署名-非商業性使用-相同方式共享創作協議,轉載或使用請註明作者和來源,尊重知識分享。 |
批評不自由
則讚美無意義
Google Chrome 30.0.1599.101 Windows 7 大約10年前
要是調試的話還少什麼。比如頭文件什麼的。