要么改变世界,要么适应世界

模拟设计磁盘文件的链接存储结构

2020-07-02 21:24:00
306
目录

课题要求

  1. 磁盘文件的管理采用显式链接结构,将文件占用的物理块号和链接指针记录 在一张文件分配表(FAT)中。文件第一块的块号记录在索引结点中。文件目录 只记录文件名和索引结点的编号。索引结点的结构如下:

    索引结点编号 文件属性 创建时间 文件第一块块号 文件占用盘块数 备用
  2. 假定磁盘存储空间共有 100 个物理块用于存放数据, 目录文件和索引结点可 直接访问,不存放在这 100 个块中。

  3. 一个物理块可存放 3 个文件逻辑记录,并且假设文件逻辑记录定长。

  4. 要求用键盘输入的方式模拟用户读写请求,菜单格式建议如下:

    • Create(filename)
    • Write(filename, text, logical_record_no)
    • Read (filename, logical_record_no)
    • Delete(filename) 其中filename是要读写的文件名,text 是写入的内容,logical_record_no 是逻辑 记录号。CreateWriteReadDelete 分别表示创建一个文件,向文件的某个逻 辑记录写,从文件的某个逻辑记录读,删除一个文件。
  5. 文件存储空间管理采用位示图(位示图为 7 行,16 列)的方式。

  6. 要求程序可以打印FAT以及位示图的情况。

结构设计

数据结构

  • 结点项

    typedef struct Inode {
        int firstBlockId;     // 文件第一块块号
        int lastBlockId;      // 文件最后一块块号
        int usedBlocksNum;    // 文件占用的盘块数
        time_t createTime;    // 文件创建时间
        time_t LastEditTime;  // 文件上次修改时间
        int permission;       // 文件权限
        int isDelete;         // 该节点是否被标记“已删除”
        char standby[20];     // 备用
    } Inode;
    
  • 目录项

    typedef struct listItem {
        char fileName[256];  // 文件名字
        int nodeId;          // 文件对应的结点编号
    } listItem;
    
  • 物理盘块号

    typedef struct Block {
        // 每一个物理块有三块逻辑记录号
        char firstLogical[LOGICALSIZE];
        char secondLogical[LOGICALSIZE];
        char thirdogical[LOGICALSIZE];
    } Block;
    
  • 抽象磁盘

    typedef struct Disk {
        int FAT[BLOCKNUM];             // 最多有BLOCKNUM个表项
        int bitmap[ROW][COL];          // 示位图
        listItem directory[BLOCKNUM];  // 目录 最多有BLOCKNUM个目录项
        Inode FDI[BLOCKNUM];  // 索引结点集合 最多有BLOCKNUM个节点
        int fileNum;
        Block blocks[BLOCKNUM];  // 总的物理盘块数
        int freeBlock;           // 空闲盘块数量
    } Disk;
    

设计思路

程序一开始将磁盘格式化,然后根据用户选择进行相关操作。

  • 创建文件:

    首先申请一块空闲盘块(即默认一个文件初始占用一块盘块),同时将申请到的盘块记为“已使用”状态。

    申请方式是:选定一个随机数作为“基址”,假如该盘块已被占用,尝试申请该“基址”的下一块,假若仍然被占用,则继续往后尝试………

  • 读取文件:

    根据文件名,在目录中检索,将该文件对应的索引结点找到。然后根据欲读取的逻辑记录号进行尝试读取(一个文件最多拥有的逻辑记录号为:max = 3 * n - 1n是文件占用盘块数,即编号从零开始)。

    方法是:根据在检索目录得到的索引结点获得该文件占用的第一块盘块号,假如该盘块不是用户所要读取的盘块,则根据文件分配表获取下一块盘块号,不断重复上面过程,直到找到目的盘块号。

  • 写入文件

    • 写入数据:

      向某个文件的某个逻辑记录号中写入数据,写入之前检查逻辑记录号的合法性

    • 修改文件大小:假若新文件大小小于旧文件大小,则只保留新文件大小的数据

  • 删除文件:

    先根据文件名,在目录中检索出相应的索引结点,根据索引结点获得第一块盘块号,将该盘块置为“未使用状态”,并将这一盘块指向的下一块盘块(假如存在)也置为“未使用”,依此重复,直至该文件占用盘块全都归还。同时盘块对应的示位图也要更新状态。

源程序

/*
 * @Author: YaleXin
 * @Date: 2020-06-07 15:53:40
 * @LastEditTime: 2020-07-01 21:08:41
 * @LastEditors: YaleXin
 * @Description: 操作系统课程设计
 * @FilePath: \my_c_workspace\OS\design\main.c
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define LOGICALSIZE 1024  //一条逻辑记录的大小
#define BLOCKNUM 100      //物理块数
#define ROW 7             //示位图行数
#define COL 16            //示位图列数
#define FREE 0            //示位图中表示空闲状态
#define USED 1            //示位图中表示已用状态
const int OK = 1;
/**
 * 目录项
 */
typedef struct listItem {
    char fileName[256];  // 文件名字
    int nodeId;          // 文件对应的结点编号
} listItem;
typedef struct Block {
    // 每一个物理块有三块逻辑记录号
    char firstLogical[LOGICALSIZE];
    char secondLogical[LOGICALSIZE];
    char thirdogical[LOGICALSIZE];
} Block;
typedef struct Inode {
    int firstBlockId;     // 文件第一块块号
    int lastBlockId;      // 文件最后一块块号
    int usedBlocksNum;    // 文件占用的盘块数
    time_t createTime;    // 文件创建时间
    time_t LastEditTime;  // 文件上次修改时间
    int permission;       // 文件权限
    int isDelete;         // 该节点是否被标记“已删除”
    char standby[20];     // 备用
} Inode;
typedef struct Disk {
    int FAT[BLOCKNUM];             // 最多有BLOCKNUM个表项
    int bitmap[ROW][COL];          // 示位图
    listItem directory[BLOCKNUM];  // 目录 最多有BLOCKNUM个目录项
    Inode FDI[BLOCKNUM];  // 索引结点集合 最多有BLOCKNUM个节点
    int fileNum;
    Block blocks[BLOCKNUM];  // 总的物理盘块数
    int freeBlock;           // 空闲盘块数量
} Disk;
Disk d;
int dirLastIndex;  // 最后的目录项下标
int fdiLastIndex;  // 最后的索引结点下标
/**
 * 申请成功,则返回申请的物理块号
 * 否则返回-1
 */
int getFreeBlock() {
    if (d.freeBlock <= 0) return -1;
    // 随机申请一块物理块 假如已经被使用  则往后寻找
    srand((unsigned)time(NULL));
    int index = rand() % BLOCKNUM;
    int r = index / 16, c = index % 16;
    if (d.bitmap[r][c] == 0) {
        d.bitmap[r][c] = 1;
        d.freeBlock--;
        return index;
    } else {
        int i, j;
        if (c == 15) {
            i = (r + 1) % 7;
            j = 0;
        } else {
            i = r;
            j = (c + 1) % 16;
        }
        for (; i < 7; )
            for (; j < 16; ) {
                if (d.bitmap[i][j] == 0) {
                    d.bitmap[i][j] = 1;
                    d.freeBlock--;
                    return (i * 16 + j);
                }
                j++;
                if(j == 16){
                    i = (i + 1)%7;
                    j = 0;
                }
            }
    }
}
/**
 * 格式化
 */
void intial() {
    for (int i = 0; i <= 99; i++) d.FAT[i] = EOF;
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++) d.bitmap[i][j] = FREE;
    for (int i = 0; i < BLOCKNUM; i++) {
        d.blocks[i].firstLogical[0] = '\0';
        d.blocks[i].secondLogical[0] = '\0';
        d.blocks[i].thirdogical[0] = '\0';
    }
    d.fileNum = 0;
    dirLastIndex = 0;
    fdiLastIndex = 0;
    d.freeBlock = BLOCKNUM;
}
/**
 * 错误码:
 * 2:文件已存在
 * 3:磁盘空间不足
 */
int Create(char *fileName) {
    for (int i = 0; i < dirLastIndex; i++)
        if (!strcmp(d.directory[i].fileName, fileName) &&
            d.directory[i].nodeId != -1) {
            return 2;
        }
    int blockId = getFreeBlock();
    if (blockId == -1) {
        return 3;
    } else {
        int i;
        for (i = 0; i < fdiLastIndex; i++)
            if (d.FDI[i].isDelete) break;
        // 处理索引结点
        d.FDI[i].firstBlockId = d.FDI[i].lastBlockId = blockId;
        // 获取当前时间戳
        time(&(d.FDI[i].createTime));
        d.FDI[i].LastEditTime = d.FDI[i].createTime;
        d.FDI[i].permission = 444;
        d.FDI[i].usedBlocksNum = 1;
        d.FDI[i].isDelete = 0;
        int j;
        for (j = 0; j < dirLastIndex; j++)
            if (d.directory[j].nodeId == -1) break;
        // 处理目录项
        strcpy(d.directory[j].fileName, fileName);
        d.directory[j].nodeId = i;
        if (i == dirLastIndex) dirLastIndex++;
        if (j == fdiLastIndex) fdiLastIndex++;
        d.fileNum++;
        return OK;
    }
}
struct readReturn {
    int status;
    char msg[LOGICALSIZE];
};
/**
 * 返回值:
 * 1:读取正常
 * 2:文件不存在
 * 3:逻辑记录号错误
 */
struct readReturn Read(char *filename, int logical_record_no) {
    struct readReturn r;
    int i;
    for (i = 0; i < dirLastIndex; i++)
        if (!strcmp(filename, d.directory[i].fileName) &&
            d.directory[i].nodeId != -1)
            break;
    if (i >= dirLastIndex) {
        r.status = 2;
        return r;
    }
    int BlockId = logical_record_no / 3;
    if (BlockId + 1 > d.FDI[d.directory[i].nodeId].usedBlocksNum) {
        r.status = 3;
        return r;
    }
    int index = d.FDI[i].firstBlockId;
    for (int j = 0; j < BlockId; j++) index = d.FAT[index];
    switch (logical_record_no % 3) {
        case 0:
            strcpy(r.msg, d.blocks[index].firstLogical);
            break;
        case 1:
            strcpy(r.msg, d.blocks[index].secondLogical);
            break;
        case 2:
            strcpy(r.msg, d.blocks[index].thirdogical);
            break;
    }
    r.status = 1;
    return r;
}
/**
 * 错误码:
 * 2:文件不存在
 * 3:逻辑记录号错误
 */
int Write(char *filename, char *text, int logical_record_no) {
    int i;
    for (i = 0; i < dirLastIndex; i++)
        if (!strcmp(filename, d.directory[i].fileName) &&
            d.directory[i].nodeId != -1)
            break;
    if (i >= dirLastIndex) return 2;
    if (logical_record_no < 0 ||
        logical_record_no >= d.FDI[i].usedBlocksNum * 3)
        return 3;
    // 通过 firstBlockId 在 FAT 中寻找正确的位置写入
    int index = d.FDI[i].firstBlockId, blockId = logical_record_no / 3;
    for (int j = 0; j < blockId; j++) index = d.FAT[index];
    switch (logical_record_no % 3) {
        case 0:
            strcpy(d.blocks[index].firstLogical, text);
            break;
        case 1:
            strcpy(d.blocks[index].secondLogical, text);
            break;
        case 2:
            strcpy(d.blocks[index].thirdogical, text);
            break;
    }
    // 获取当前时间戳
    time(&(d.FDI[i].LastEditTime));
    return OK;
}
void tryCreate() {
    char fileName[256];
    printf("请输入新文件名:\n");
    scanf("%s", fileName);
    int status = Create(fileName);
    if (status == 2)
        printf("该文件已存在,请先删除旧文件再创建该文件。\n");
    else if (status == 3)
        printf("磁盘空间不足!无法创建新文件。\n");
    else
        printf("创建成功!\n");
    system("pause");
}
void tryRead() {
    char fileName[256];
    int logical_record_no;
    printf("请输入想要读取的文件名:\n");
    scanf("%s", fileName);
    printf("请输入想要读取的逻辑记录号(编号从零开始):\n");
    scanf("%d", &logical_record_no);
    struct readReturn r = Read(fileName, logical_record_no);
    if (r.status == 2) {
        printf("该文件不存在!请重新输入文件名。\n");
    } else if (r.status == 3) {
        printf("该文件没有该逻辑记录,请输入正确的逻辑记录号。\n");
    } else {
        printf("读取到的内容是\n%s\n", r.msg);
    }
    system("pause");
}
void tryWrite() {
    char fileName[256], text[1024];
    int logical_record_no, newBlockSize;
    int exit = 0, choice;
    while (!exit) {
        system("cls");
        printf("1.向文件中写入数据\n");
        printf("2.修改文件大小\n");
        printf("0.返回\n");
        printf("请输入您的选择:\n");
        scanf("%d", &choice);
        switch (choice) {
            case 1: {
                printf("请输入想要写入的文件名:\n");
                scanf("%s", fileName);
                printf("请输入想要写入的逻辑记录号(编号从零开始):\n");
                scanf("%d", &logical_record_no);
                printf("请输入您想要写入的信息(一次最多写入%d个字符)\n",
                       LOGICALSIZE);
                getchar();
                gets(text);
                int status = Write(fileName, text, logical_record_no);
                if (status == 2) {
                    printf("文件不存在,请输入正确的文件名!\n");
                } else if (status == 3) {
                    printf(
                        "您输入的逻辑记录号过大或者是负数,您可以通过增加文件大"
                        "小使得文件拥有该逻辑记录号\n");
                } else {
                    printf("写入成功!\n");
                }
                system("pause");
                break;
            }
            case 2: {
                printf("请输入您想要修改的文件名:\n");
                scanf("%s", fileName);
                printf(
                    "请输入该文件新大小(若新的大小小于原来的大小,则只保留新的"
                    "大小的数据,新大小应该是一个大于零的数字,单位:块):\n");
                scanf("%d", &newBlockSize);
                // 索引结点所在下标
                int i;
                for (i = 0; i < dirLastIndex; i++)
                    if (!strcmp(fileName, d.directory[i].fileName) &&
                        d.directory[i].nodeId != -1)
                        break;
                if (i >= dirLastIndex) {
                    printf("文件不存在,请输入正确的文件名!\n");
                    system("pause");
                    break;
                } else if (newBlockSize > d.FDI[i].usedBlocksNum) {
                    // 增加文件大小
                    int need = newBlockSize - d.FDI[i].usedBlocksNum, blockId;
                    while (need) {
                        blockId = getFreeBlock();
                        if (blockId == -1) {
                            printf(
                                "磁盘空间不足!只成功申请了 %d "
                                "个物理块,申请失败 %d 个\n",
                                newBlockSize - need, need);
                            system("pause");
                            break;
                        }
                        need--;
                        d.FAT[d.FDI[i].lastBlockId] = blockId;
                        d.FDI[i].lastBlockId = blockId;
                        d.FDI[i].usedBlocksNum++;
                    }
                    time(&(d.FDI[i].LastEditTime));
                    printf("修改成功!\n");
                    system("pause");
                    break;
                } else if (newBlockSize < d.FDI[i].usedBlocksNum) {
                    // 减小文件
                    int index = d.FAT[d.FDI[i].firstBlockId], count = 1;
                    while (count < newBlockSize) {
                        index = d.FAT[index];
                        count++;
                    }
                    // 回收后面的磁盘空间
                    while (newBlockSize - count > 0) {
                        int old = d.FAT[index];
                        index = d.FAT[index];
                        d.FAT[old] = EOF;
                        count++;
                    }
                    time(&(d.FDI[i].LastEditTime));
                    printf("修改成功!\n");
                    system("pause");
                    break;
                }
            }
            case 0:
                return;
            default:
                printf("您输入有误,请重新输入!\n");
                system("pause");
                break;
        }
    }
}
void showBitmap() {
    printf("“0”代表空闲,“1”代表已用\n");
    for (int i = 0; i < 7; i++)
        for (int j = 0; j < 16; j++) {
            if (i * 16 + j >= BLOCKNUM) {
                printf("\n");
                system("pause");
                return;
            } else {
                printf("%d ", d.bitmap[i][j]);
            }
            if (j == 15) printf("\n");
        }
}
void showFiles() {
    printf(
        "----------------------------------------------------------------------"
        "--------------\n");
    printf("|%-20s|%-19s|%-19s|%-10s|%-10s|\n", "文件名", "创建日期",
           "修改日期", "权限信息", "文件大小");
    for (int i = 0; i < dirLastIndex; i++)
        if (d.directory[i].nodeId != -1) {
            printf(
                "|%-20s|%4d-%2d-%2d %2d:%2d:%2d|%4d-%2d-%2d "
                "%2d:%2d:%2d|%-10d|%-10d|\n",
                d.directory[i].fileName,
                // 年份从1900开始算起,因此要加上1900
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_year +
                    1900,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_mon + 1,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_mday,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_hour + 8,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_min,
                gmtime(&(d.FDI[d.directory[i].nodeId].createTime))->tm_sec,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_year +
                    1900,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_mon +
                    1,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_mday,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_hour +
                    8,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_min,
                gmtime(&(d.FDI[d.directory[i].nodeId].LastEditTime))->tm_sec,
                d.FDI[d.directory[i].nodeId].permission,
                d.FDI[d.directory[i].nodeId].usedBlocksNum);
        }
    printf(
        "----------------------------------------------------------------------"
        "--------------\n");
    system("pause");
}
/**
 * 错误码:
 * 2:文件不存在
 */
int Delete(char *fileName) {
    int i;
    for (i = 0; i < dirLastIndex; i++)
        if (!strcmp(d.directory[i].fileName, fileName) &&
            d.directory[i].nodeId != -1)
            break;
    if (i >= dirLastIndex) return 2;
    int nextIndex = d.FDI[d.directory[i].nodeId].firstBlockId;
    int row, col, pre;
    while (d.FAT[nextIndex] != EOF) {
        row = nextIndex / COL;
        col = nextIndex % COL;
        d.bitmap[row][col] = FREE;
        pre = nextIndex;
        nextIndex = d.FAT[nextIndex];
        d.FAT[pre] = -1;
    }
    row = nextIndex / COL;
    col = nextIndex % COL;
    d.bitmap[row][col] = FREE;
    d.FDI[d.directory[i].nodeId].isDelete = 1;
    d.directory[i].nodeId = -1;
    return OK;
}
void tryDelete() {
    char fileName[11];
    printf("请输入您想要删除的文件:\n");
    scanf("%s", fileName);
    int status = Delete(fileName);
    if (status == 2) {
        printf("该文件不存在,请重新输入!\n");
    } else {
        printf("删除成功!\n");
    }
    system("pause");
}
void showFAT() {
    int i = 0, len = 25, j = 1, t, k;
    for (; j <= 4; j++) {
        t = i;
        for (k = 1; k <= 114; k++) printf("-");
        printf("\n");
        printf("|%-12s|", "编号");
        for (; i < j * len; i++) printf("%-3d|", i);
        printf("\n");
        printf("|%-12s|", "下一块盘块号");
        for (i = t; i < j * len; i++) printf("%-3d|", d.FAT[i]);
        printf("\n");
        for (k = 1; k <= 114; k++) printf("-");
        printf("\n\n");
    }
    system("pause");
}
int main() {
    // 初始化磁盘 即格式化
    intial();
    int exit = 0, choice;
    while (!exit) {
        system("cls");
        printf("1.创建文件\n");
        printf("2.读取文件\n");
        printf("3.写入文件\n");
        printf("4.删除文件\n");
        printf("5.显示示位图\n");
        printf("6.列出所有文件\n");
        printf("7.打印FAT\n");
        printf("0.退出系统\n");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                tryCreate();
                break;
            case 2:
                tryRead();
                break;
            case 3:
                tryWrite();
                break;
            case 4:
                tryDelete();
                break;
            case 5:
                showBitmap();
                break;
            case 6:
                showFiles();
                break;
            case 7:
                showFAT();
                break;
            case 0:
                exit = 1;
                break;
            default:
                printf("输入有误,请重新输入!\n");
                system("pause");
                break;
        }
    }
}

小插曲

在验收前的十几分钟突然发现getFreeBlock()函数有bug,当时立马从腾讯会议中退出来,测试了好久发现是for循环有问题,之前的写法是这样:

for (; i < 7; i =( i + 1 ) % 7)
	for (; j < 16; j = (j + 1) % 16) {
                
}

这样子内循环一直结束不了,造成了死循环。之前一直没发现这个问题是因为之前测试的时候,一般不会把文件大小改得很大,所以不会触发这个循环。

历史评论
开始评论