黄阿信的个人博客

课题要求

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

索引结点编号文件属性创建时间文件第一块块号文件占用盘块数备用
假定磁盘存储空间共有 100 个物理块用于存放数据，目录文件和索引结点可直接访问，不存放在这 100 个块中。
一个物理块可存放 3 个文件逻辑记录，并且假设文件逻辑记录定长。
要求用键盘输入的方式模拟用户读写请求，菜单格式建议如下：
- Create（filename）
- Write（filename， text， logical_record_no）
- Read (filename, logical_record_no)
- Delete（filename） 其中filename是要读写的文件名，text 是写入的内容，logical_record_no 是逻辑记录号。Create、Write、Read、Delete 分别表示创建一个文件，向文件的某个逻辑记录写，从文件的某个逻辑记录读，删除一个文件。
文件存储空间管理采用位示图（位示图为 7 行，16 列）的方式。
要求程序可以打印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 - 1，n是文件占用盘块数，即编号从零开始）。

方法是：根据在检索目录得到的索引结点获得该文件占用的第一块盘块号，假如该盘块不是用户所要读取的盘块，则根据文件分配表获取下一块盘块号，不断重复上面过程，直到找到目的盘块号。
写入文件
- 写入数据：
  
  向某个文件的某个逻辑记录号中写入数据，写入之前检查逻辑记录号的合法性
- 修改文件大小：假若新文件大小小于旧文件大小，则只保留新文件大小的数据
删除文件：

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

源程序

/*
 * @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) {
                
}

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

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

课题要求

结构设计

数据结构

设计思路

源程序

小插曲