文件物理結構和存儲空間管理

磁碟結構:

磁碟也和記憶體一樣分塊，並且塊大小和記憶體塊大小相同，方便數據交換。

一、文件物理結構

1、連續分配

文件連續分配在磁碟的塊上，查找效率最高，磁頭移動最快，但是產生碎片最多，不容易擴展。

下麵用Python實現以下連續分配的邏輯

class Category: #文件目錄
    def __init__(self,size):
        self.table=[]
        self.disk = Disk(size) #模擬磁碟

    def append(self,file_name,length):
        t=[None]*2
        t[0] = file_name
        t[1] = self.disk.Distribution(length)
        self.table.append(t)


class Disk:
    def __init__(self,size):
        self.table=[None]*size
    def Distribution(self,length):
        for index,v in enumerate(self.table):
            if v==None and len(self.table)-length>0:
                for j in range(index,index+length):
                    self.table[j] = True
                return index

        print("磁碟已經滿了")
        return -1
if __name__ == '__main__':
    category = Category(100)
    category.append("one",20)
    category.append("three",30)
    category.append("tow",15)

    print(category.table)
    print(category.disk.table)

2、鏈接分配

(1) 顯式鏈接（支持隨機訪問）

文件目錄表FCB：

FAT文件分配表(長駐記憶體，方便查找):

一個磁碟一張FAT表

上面a.txt文件依次存放在0->3->6這三個塊中

(2)隱式鏈接

只支持順序訪問、存在連續的塊中,每個塊同時也有指向下一個塊的指針

FCB

下麵用Python模擬

class Category:
    def __init__(self,fat_size):
        self.table=[]
        self.fat = FAT(fat_size)

    def append(self,file_name,size):
        file =[None]*3
        file[0] = file_name
        file[1] = size
        file[2] = self.fat.FindEmpty()
        if file[2]==-1:
            print("沒有空閑塊")
            return
        self.fat.Distribution(file[2],file[1])
        self.table.append(file)






class FAT:
    def __init__(self,size):
        self.table=[]
        for i in range(size):
            t = list()
            t.append(i)
            t.append(None)
            self.table.append(t)





    def Distribution(self,cur,size):
        self.table[cur][1] = -1
        for c in range(size):
            self.table[cur][1] = self.FindEmpty()
            cur = self.table[cur][1]
        self.table[cur][1] = -1

    def FindEmpty(self):
        for i in self.table:
            if i[1]==None:
                return i[0]
        return -1


if __name__ == '__main__':
    fat_size = 100
    category = Category(fat_size)
    #
    category.append("one",4)
    category.append("tow",2)

    category.append("three",20)


    print(category.table)
    for w in category.fat.table:
        print(w[0],w[1])

3、索引分配

支持隨機訪問

FCB

索引表(每個文件都有一個索引表，FCB保存著索引表的物理塊號)

上面文件存放的塊號為6->98->5->12->4，一個索引表不夠可以鏈接另外一個物理塊再創建一個索引表

，這種鏈式效率慢，一般採用多級索引。

二、文件存儲空間管理

分區

一個磁碟分為好幾個文件捲或區，A盤B盤D盤等，這些都是邏輯分區，

通常將一個磁碟分為好幾個邏輯分區，也可以把好幾個磁碟劃為一個邏輯分區

分區結構

在一個分區內分為目錄區和文件區，目錄區存放目錄基本信息和索引、文件區存放具體數據

文件空閑空間管理

1、空閑區鏈表法

將連續的空閑塊鏈接成鏈表，使用時尋找最佳空閑區、如何刪除空閑鏈表節點、回收時加入鏈接尾部

2、位示圖法

位為1代表非空閑塊，根據磁碟塊號算出位的位置，然後管理