操作系统课程设计 -- 磁盘管理

本文最后更新于：2021年2月27日 上午

概览：操作系统课程设计 —— 磁盘管理的实现，包含Java与C++，均采用面向对象的思想，包含代码。

任务要求

本次课程设计的任务是虚拟实现部分操作系统的典型算法，加深对操作系统运行机制的掌握和理解。任务具体要求：

在Winidows/Linux/iOS/Android平台下（平台任选一个），以面向对象思想实现下面功能：

1、磁盘管理

建立一个4KB大小的文件模拟磁盘，按逻辑将其划分为1024块，每块大小4B。其中900块用于存放普通数据，124块用于存储兑换数据。存储管理需要支持：

（1）数据组织：对需要存放的文件数据加以组织管理，可以采用连续组织方式、显式连接（FAT）方式、单级索引组织方式、二级索引组织方式、混合索引方式（每组要求不同，具体见“课程设计分组”部分，下同）。

（2）空闲块管理：能够查询并返回当前剩余的空闲块，对空闲块管理可以采用位示图法、空闲盘块表法、空闲盘块连法、成组连接法。

（3）兑换区管理：能够写入、读出兑换区数据。

2、目录管理

为写入模拟磁盘的数据文件建立目录，目录可以是单级文件目录、双级文件目录、树形结构目录。在目录中选择某个文件可以将其数据读入模拟内存。目录中包含文件名、文件所有者、创建时间、文件结构、在磁盘中存放的地址等信息。目录管理需要支持：

（1）新建目录：在目录中新建空目录

（2）删除目录：删除空目录

（3）为文件建立目录项：一个文件被创建后，为该文件创建目录项，并将文件相关信息写入目录中。

（4）删除文件：删除目录中某个文件，删除其在磁盘中的数据，并删除目录项。如果被删除文件已经读入内存应该阻止删除，完成基本的文件保护。

3、内存管理

申请一块64字节的内存空间模拟内存，按逻辑划分为16块，每块4B。将目录中选中的文件读入内存，显示文件中信息。内存可以同时显示多个文件信息，每个文件固定分配4个内存块，如果4个内存块不能显示文件全部信息，采用页面置换策略，将已显示完的页换出内存，可以选择的置换策略有，全局置换、局部置换、FIFO、LRU。内存管理需要支持：

（1）分配内存块：为线程分配内存块，每个线程默认分配4块。

（2）回收内存：线程结束后回收其内存。

（3）空闲内存块管理：为进入内存的数据寻找空闲内存块。没有空闲内存时，应给出提示。

（4）块时间管理：提供数据块进入模拟内存的时间、访问时间的记录和查询功能，为页面置换算法提供支持，当某个内存块被选中时，更新其访问时间。

4、线程管理

本虚拟系统以线程为基本运行单位，线程本身采用编程语言提供的线程机制，不模拟。系统主要包括的线程有：

（1）数据生成线程：该线程负责生成外存数据，给定数据大小（按字节计算）、数据信息（英文字母）、存储目录、文件名后，该线程调用磁盘管理中空闲磁盘管理功能，申请所需大小的外存块，如果盘块不够给出提示。按照要求的数据组织方式，将数据存入磁盘块（按块分配磁盘），并调用目录管理功能为其在目录中建立目录项，更改空闲盘块信息。

（2）删除数据线程：该线程调用删除目录管理中文件删除功能删除数据（内存中文件不能删除）。并回收外存空间，更新空闲盘块信息。

（3）执行线程：选择目录中的文件，执行线程将文件数据从外存调入内存，为此，首先需要调用内存管理的空闲空间管理功能，为该进程申请4块空闲内存，如果没有足够内存则给出提示，然后根据目录中文件存储信息将文件数据从外存读入内存，此间如果4块内存不够存放文件信息，需要进行换页（选择的换页策略见分组要求），欢出的页面存放到磁盘兑换区。允许同时运行多个执行线程。文件数据在内存块的分布通过线程的页表（模拟）进行记录。

（4）线程互斥：对于64B的内存，线程需要互斥访问，避免产生死锁。不能访问内存的线程阻塞，等待被唤醒。

5、用户接口

对内存块、外存块、目录信息进行可视化显示，并能够动态刷新。文件调入内存过程、以及换页过程在块与块之间加入延时，以便观察。

对于实现以上功能，可以采用任何熟悉的编程语言，不做具体要求。

磁盘管理

由于我主要负责磁盘管理部分，所以只写了磁盘管理部分的代码。

Java代码

DiskBlock.java – 定义单独的一块磁盘块，即磁盘的最小结构。

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
package FileDiskDir;

public class DiskBlock {
    private int blockNum;//块号
    private String blockData;//块内数据

    public DiskBlock() {

    }

    public DiskBlock(int blockNum, String blockData) {
        this.blockNum = blockNum;
        this.blockData = blockData;
    }

    public int getBlockNum() {
        return blockNum;
    }

    public void setBlockNum(int blockNum) {
        this.blockNum = blockNum;
    }

    public String getBlockData() {
        return blockData;
    }

    public void setBlockData(String blockData) {
        this.blockData = blockData;
    }
}

DiskManage.java – 磁盘管理。

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
package FileDiskDir;

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class DiskManage {
    private Map<String, MixIndex> FileMixIndexMap = new HashMap<String, MixIndex>();//建立文件名和索引表的映射
    private DiskBlock[] MyDisk = new DiskBlock[1024];//1024个磁盘块
    private boolean[] MyDiskState = new boolean[1024];//位示图,false表示未被使用，true表示被使用
    private int freeDiskDataBlock;//数据区中空闲的磁盘块数
    private String diskTxtData;//磁盘txt的全部数据

    private static DiskManage instance = new DiskManage();

    public DiskManage() {
        freeDiskDataBlock = 900;
        serializeToDisktxt();
        diskTxtData = readDataFromDiskTxt();
    }

    public static DiskManage getInstance(){
        return instance;
    }

    //初始化文件DiskTxt
    private void serializeToDisktxt() {
        try {
            //将disk文件存满1024*4个#.
            File f = new File("src/file/disk.txt");
            byte data[] = new byte[4096];
            for(int i = 0;i<4096;i++){
                data[i] = '#';
            }

            // 创建基于文件的输出流
            FileOutputStream fos = new FileOutputStream(f);
            // 把数据写入到输出流
            fos.write(data);
            // 关闭输出流
            fos.close();

        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    //从DiskTxt读取磁盘所有的内容，存储为string
    private String readDataFromDiskTxt(){
        String data = "";
        try {
            //将disk文件存满1024*4个#.
            File f = new File("src/file/disk.txt");
            FileReader reader = new FileReader(f);
            BufferedReader br = new BufferedReader(reader);
            String lines;
            while((lines = br.readLine() )!= null){
                data += lines;
            }

            // 关闭输出流
            br.close();
            reader.close();

        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        return data;
    }

    //将全部数据写回磁盘文件
    private void writeDataToDiskTxt(String data){
        try {
            File f = new File("src/file/disk.txt");
            f.createNewFile();//创建新文件,有同名的文件的话直接覆盖
            FileWriter writer = new FileWriter(f);
            BufferedWriter out = new BufferedWriter(writer);
            out.write(data);
            out.flush();//将缓存区内容压入文件

            out.close();
            writer.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public int getFreeDiskDataBlock() {
        return freeDiskDataBlock;
    }

    //写数据到磁盘块
    public void WriteDataToBlock(int blockNum,String data){
        MyDisk[blockNum] = new DiskBlock();
        MyDisk[blockNum].setBlockData(data);

        MyDiskState[blockNum] = true;
        freeDiskDataBlock -= 1;

        //diskTxtData更新
        diskTxtData = readDataFromDiskTxt();

        //使用stringbuffer来替换
        StringBuffer sb = new StringBuffer(diskTxtData);
        for(int i=0;i<4;i++){
            sb.setCharAt(blockNum*4 + i,data.charAt(i));
        }

        //
        writeDataToDiskTxt(sb.toString());

    }

    //从磁盘块读数据
    public String ReadDataFromBlock(int blockNum){

        return MyDisk[blockNum].getBlockData();
    }

    //删除数据
    public void DeleteDataInBlock(int blockNum){
        MyDiskState[blockNum] = false;
        freeDiskDataBlock += 1;
    }

    //创建文件保留数据到磁盘
    public MixIndex SaveFileDataToDisk(String fileName,int size,String data){

        //创建文件的索引表
        MixIndex fileMixIndexTable = new MixIndex();

        //创建一个当前正在使用的索引表
        MixIndex nowMixIndexTable = fileMixIndexTable;

        //从位示图中寻找空闲的块,并且赋值
        int index = 0;//定义一个索引表里的index,同时表示字符串的读取位置
        for(int i=0;i<900;i++) {
            if(MyDiskState[i] == false){
                if(index < size){
                    if(index / 9 == 0 && index % 9 == 0 ){
                        //创建文件的新一级索引表
                        MixIndex newfileMixIndexTable = new MixIndex();
                        nowMixIndexTable.setIndirectIndex(newfileMixIndexTable);
                        nowMixIndexTable = newfileMixIndexTable;
                    }
                    nowMixIndexTable.setDirectIndexByIndex(index%9,i);
                    //位示图更新
                    MyDiskState[i] = true;
                    //写入对应磁盘块的数据
                    WriteDataToBlock(i,data.substring(index*4,index*4+4));//截取[index*4,index*4+4)这一部分
                    index++;
                }
                else break;
            }
        }
        //添加到FileMixIndexMap
        FileMixIndexMap.put(fileName,fileMixIndexTable);//是否可以？
        return fileMixIndexTable;
    }

    //读取文件在磁盘上的数据
    public String ReadFileDataInDisk(String fileName,int size){
        MixIndex fileMixIndexTable = FileMixIndexMap.get(fileName);
        String data = "";

        //计算次数
        int times = size / 9;
        int lasttimes = size % 9;
        for(int i=0;i< times;i++){
            for(int j = 0;j<9;j++){
                data += ReadDataFromBlock(fileMixIndexTable.getDirectIndex(j));
            }
            fileMixIndexTable = fileMixIndexTable.getIndirectIndex();
        }
        for(int i = 0;i<lasttimes;i++){
            data += ReadDataFromBlock(fileMixIndexTable.getDirectIndex(i));
        }
        return data;
    }
}

main.java – 测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import FileDiskDir.DiskManage;

public class Main {

    public static void main(String[] args) {

        System.out.println("Hello World!");

        DiskManage disk = new DiskManage();

        String data = "1234567812345678123456781234567812345678123456781234567812345678";

        disk.SaveFileDataToDisk("hello",16,data);

        System.out.println(disk.ReadFileDataInDisk("hello",16));

    }
}

java代码大致思路

  • 采用了普通的一维数组来表示位示图，用于记录磁盘块的状态。
  • MyDisk[1024] 来表示磁盘。存取操作都对这个数组进行。
  • Map<String, MixIndex> FileMixIndexMap 用来记录文件名与文件所存储的混合索引表的映射。
  • 文件的读取操作都是之后加入的，用于同步磁盘的情况。
  • 实际上的存储数据会有一定的bug（存储数据的第一部分，即索引表的第一部分读取时会出现问题）。

C++代码

common_data.h – 公共数据的结构体定义头文件

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
#pragma once

#include <iostream>
#include <string>
#include <map>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctime>
#include <Windows.h>
#include <iomanip>

using namespace std;

/*----------定义磁盘块-------------*/
struct DiskBlock {
	int BlockNum;//定义块号
	string data;//数据
};

/*----------定义索引表的结构-------------*/
//直接索引
struct DireIndexTable {
	int addr_1[10];
};

//一级间接索引
struct IndireIndexTable {
	DireIndexTable addr_2[10];
};

//混合索引
struct MixIndexTable {
	int addr_1[10];//10个直接索引，直接存储盘块号
	DireIndexTable addr_2[10];//10个一级索引，每个一级索引存储了10个直接索引
	IndireIndexTable addr_3[10];//10个二级索引
};

DiskManage.h – 磁盘管理类的定义头文件

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
#pragma once
#include "common_data.h"

/*----------磁盘管理类-------------*/
class DiskManage{

public:
	DiskBlock MyDisk[1024];//磁盘，有1024个块
	map<string, MixIndexTable*> MyMixIndexTable;//文件名与混合索引表的映射
	int BitMap[32][32];//位示图 32 * 32，0表示未被使用，1表示已经使用
	int FreeDataBlockNum;//空闲数据区的块数
	int FreeSwapBlockNum;//空闲交换区的块数
	
public:

	DiskManage();
	~DiskManage();

	/*----------单例模式创建实例-------------*/
	static DiskManage *getInstance();

	/*----------磁盘操作的最微操作-------------*/
	void WriteDataToBlock(int blockNum, string data);

	string ReadDataFromBlock(int blockNum);

	void DeleteDataInBlock(int blockNum);

	/*----------保存文件数据到磁盘，返回混合索引表-------------*/
	MixIndexTable* SaveFileDataToDisk(string fileName, int size, string data);

	/*----------保存内存数据到交换区，返回块号-------------*/
	int SaveMmToSwap(string data);

	/*----------读取文件数据-------------*/
	string ReadFileDataFromDisk(string fileName, int size);

	/*----------打印磁盘数据-------------*/
	void PrintMyDisk();

	void PrintBitMap();
};

DiskManage.cpp – 磁盘管理类的实现文件

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
#include "DiskManage.h"

DiskManage::DiskManage(){

	for (int i = 0; i < 1024; i++) {
		MyDisk[i].BlockNum = i;
		MyDisk[i].data = "####";
	}
	for (int i = 0; i < 32; i++) {
		for (int j = 0; j < 32; j++) {
			BitMap[i][j] = 0;
		}
	}
	FreeDataBlockNum = 900;
	FreeSwapBlockNum = 124;
}


DiskManage::~DiskManage(){
}

DiskManage * DiskManage::getInstance(){

	static DiskManage * instance;
	if (instance == nullptr) {
		instance = new DiskManage();
	}
	return instance;
}

void DiskManage::WriteDataToBlock(int blockNum, string data){

	MyDisk[blockNum].data = data;
	
	//修改位示图
	int i = blockNum / 32;
	int j = blockNum % 32;
	BitMap[i][j] = 1;

	/**
 * 900/32 =28 余4
 * 所以第一块swap坐标是cacheBlock【28】【4】
 * 第29行第五个
 */
	if (i >= 28 && j >= 4 ) {
		FreeSwapBlockNum -= 1;
	}
	else {
		FreeDataBlockNum -= 1;
	}
}

string DiskManage::ReadDataFromBlock(int blockNum){

	return MyDisk[blockNum].data;
	
}

void DiskManage::DeleteDataInBlock(int blockNum){

	MyDisk[blockNum].data = "####";

	//修改位示图
	int i = blockNum / 32;
	int j = blockNum % 32;
	BitMap[i][j] = 0;

	//修改空闲块数
	if (i >= 28 && j >= 4) {
		FreeSwapBlockNum += 1;
	}
	else {
		FreeDataBlockNum += 1;
	}

}

MixIndexTable * DiskManage::SaveFileDataToDisk(string fileName, int size, string data){

	MixIndexTable *mit = new MixIndexTable;

	int index = 0;

	//从位示图寻找空闲的块
	for (int blockNum = 0; blockNum < 900; blockNum++) {
		if (BitMap[blockNum / 32][blockNum % 32] == 0){
			if (index < size) {
				if (index < 10) {
					mit->addr_1[index] = blockNum;
				}
				else if (index >= 10 && index < 110) {
					mit->addr_2[(index - 10) / 10].addr_1[(index - 10) % 10] = blockNum;
				}
				else {
					mit->addr_3[(index - 110) / 100].addr_2[((index - 110) % 100) / 10].addr_1[((index - 110) % 100) % 10];
				}

				//位示图更新
				BitMap[blockNum / 32][blockNum % 32] == 1;
				//写入对应的数据
				WriteDataToBlock(blockNum, data.substr(index*4,4));
				index++;
			}
			else break;
		}
	}

	//加入文件名与混合索引表的映射
	MyMixIndexTable.insert(map<string,MixIndexTable*>::value_type(fileName,mit));
	return mit;

}

int DiskManage::SaveMmToSwap(string data){

	int blockNum = 900;
	//从位示图寻找空闲的块
	for (blockNum = 900; blockNum < 1024; blockNum++) {
		if (BitMap[blockNum / 32][blockNum % 32] == 0) {
			//位示图更新
			BitMap[blockNum / 32][blockNum % 32] == 1;
			//写入对应的数据
			WriteDataToBlock(blockNum, data);
			break;
		}
	}
	return blockNum;
}

string DiskManage::ReadFileDataFromDisk(string fileName, int size){

	MixIndexTable *mit = MyMixIndexTable.find(fileName)->second;
	string data = "";
	for (int i = 0; i < size; i++) {
		if (i < 10) {
			data.append(ReadDataFromBlock(mit->addr_1[i]));
		}
		else if (i >= 10 && i < 110) {
			data.append(ReadDataFromBlock(mit->addr_2[(i - 10) / 10].addr_1[(i - 10) % 10]));
		}
		else {
			data.append(ReadDataFromBlock(mit->addr_3[(i - 110) / 100].addr_2[((i - 110) % 100) / 10].addr_1[((i - 110) % 100) % 10]));
		}
	}
	return data;
}

void DiskManage::PrintMyDisk(){

	for (int i = 1; i <= 1024; i++) {
		cout << MyDisk[i-1].data << " ";
		if (i % 16 == 0) cout << endl;
	}
}

void DiskManage::PrintBitMap(){

	for (int i = 0; i < 32; i++) {
		for (int j = 1; j <= 32; j++) {
			cout << BitMap[i][j-1] << " ";
			if (j % 16 == 0) cout << endl;
		}
	}
}

mian.cpp – 测试文件

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
#include "DiskManage.h"
#include <conio.h>

int main()
{
	cout << "打印磁盘" << endl;
	DiskManage::getInstance()->PrintMyDisk();

	cout << "打印位示图" << endl;
	DiskManage::getInstance()->PrintBitMap();

	cout << "\t\t----模拟创建文件----" << endl;
	cout << "文件数据内容：1234xxzz5678ccvv9999oooo0x0xcccc1234xxzz5678ccvv9999oooo0x0xcccc" << endl;
	string data = "1234xxzz5678ccvv9999oooo0x0xcccc1234xxzz5678ccvv9999oooo0x0xcccc";
	DiskManage::getInstance()->SaveFileDataToDisk("hello",16,data);

	cout << "\t\t----创建文件完成----" << endl;

	cout << "打印磁盘" << endl;
	DiskManage::getInstance()->PrintMyDisk();

	cout << "打印位示图" << endl;
	DiskManage::getInstance()->PrintBitMap();

	cout << "\t\t----模拟数据写入交换区----" << endl;
	cout << "文件数据内容：cccc" << endl;
	data = "cccc";
	DiskManage::getInstance()->SaveMmToSwap(data);

	cout << "\t\t----数据写入交换区完成----" << endl;

	cout << "打印磁盘" << endl;
	DiskManage::getInstance()->PrintMyDisk();

	cout << "打印位示图" << endl;
	DiskManage::getInstance()->PrintBitMap();

	_getch();
	return 0;
}

C++代码思路

第一遍是用Java写的，当时思路还不够清晰明确，混合索引定义也有问题，而且代码还有BUG，而且出于整个组的代码合并的考虑，改写成了C++。并且重新建立了结构体，以及混合索引表的结构。

  • 混合索引表有三部分，第一部分是10个直接索引，直接指向存储数据的磁盘块号，这样能表示大小占10个块的数据；第二部分是10个间接索引，每个间接索引都指向了10个直接索引，实际上就是二维数组，这样能表示大小占100个块的数据；第三部分是10个二级索引，每个索引都指向了10个一级间接索引，而每个一级间接索引都能够指向10直接索引，实际上就是三维数组，这样就能够表示1000个块的数据。这样一个混合索引表最多能存储1110个块的数据，足够满足本次课设的要求。
  • 位示图采用了 32*32的二维数组来表示，然后块号到位示图位置的映需要通过简单的计算映射。
  • 建立了文件名与混合索引表的映射 – map<string, MixIndexTable*> MyMixIndexTable;这样就能根据文件名来找到文件对应的混合索引表了。
  • 磁盘的构造函数里初始化了磁盘的数据，全部为“####”，且设置了数据区与交换区的块数。
  • 分配外存采用了首次适应算法，即分配磁盘时永远从第一块磁盘开始进行搜索。

总结

本次课程设计做的比较心累，一方面时语言的不熟悉，一方面是对任务的要求不够清楚，比较模糊，最后是小组分工写代码，但要求代码合并到一起，没有统一的接口设置，代码写的非常混乱。

对比其他的大佬组，有大佬亲自定义了全部的框架与函数，只要求其他人实现函数就行，有的大佬写了图形界面，还有的大佬甚至用了安卓和数据库，我等菜鸡太卑微了~

代码下载

本次代码里有java实现的代码，以及小组最终去展示的C++代码。线程管理的那一部分完全没有做。

链接：https://pan.baidu.com/s/1HEWRvvY--VWiSOuBLwx3Fw
提取码：bm8g