模拟实现操作系统(进程管理、存储管理、文件管理).doc

数学与信息工程学院
操作系统

软件工程系

课 程 设 计 报 告

班 级： XXXXXXXX
组长学号：XXXXXXXX
组长姓名：XXXXXXXX
指导教师：XXXXXXXX
设计时间：XXXXXXXX

摘要
此次我们小组就之前在操作系统课上所学习到的知识以及原有的编程经验，并参考课本上各种算法模式，实现一个元素较为齐全的单用户操作系统。
此次课程设计报告主要由以下四部分组成：
概要部分：大体说明此次实现操作系统的作用以及性能
课程设计任务及要求部分：主要阐述系统的主要功能模块以及每个模块计划采用的实现方法和原理。
系统设计：主要通过代码的展示以及算法描述（包括自然语言以及流程图）描述主要模块的实现流程。
程序设计及实现：该部分需要结合此次实践周的尾声，由学生负责操作并交由任课老师验收

关键词：操作系统，文件系统，……

目录
摘要 2
1 概要 4
2 课程设计任务及要求 4
3 系统设计 4
3.1进程管理 4
3.1.1 进程设置 4
3.1.2 进程调度流程 5
3.1.3进程调度算法--优先级进程调度算法（抢占式） 6
3.1.4进程调度算法--时间片轮转调度算法（RR） 8
3.2存储管理 10
3.2.1页的设置 10
3.2.2页查找流程 11
3.2.3页置换策略流程图 12
3.2.4页置换策略—先进先出算法（FIFO） 13
3.2.5页置换策略—最近最久未使用算法（LRU） 14
3.2.6页置换策略—最近最不常用算法（LFU） 16
3.3文件管理 18
3.3.1文件的设置 18
3.3.2创建文件和目录 19
3.3.3 显示该目录下的所有文件 20
3.3.4修改文件类型 20
3.3.5打开文件或文件夹方法 21
3.3.6文件或文件夹重命名 22
3.3.7删除该目录下某个文件 22
3.3.8删除时释放FAT表的空间 23
3.3.9返回上一层目录 24
3.3.10文件追加内容 24
3.3.11追加内容时修改FAT表 25
3.3.12打印FAT表内容 25
3.3.13根据绝对路径寻找文件 26
4 程序设计与实现 27

1 概要
操作系统是我们软件工程系学生所要学习的重要学科，操作系统对计算机系统资源的整合与管理也是具有举足轻重的作用，是所有软件与计算机硬件的唯一接口，所有的用户在使用计算机时都会得到OS提供的便捷服务。本次我们实现的操作系统无图形界面，需要输入相关指令进行操作，并以此实现我们对计算机中进程、存储、文件的管理。
2 课程设计任务及要求
1． 理解操作系统相关理论；
2． 利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；
3． 总体设计
(1)根据相应的题目及要求，设计合理、有效的数据结构。
(2)模块设计。
(3)算法设计清晰、正确，考虑算法的效率。
4． 详细设计
软件编码符合软件工程的规范。
5． 测试结果及分析
测试用例完整，测试结构正确
3 系统设计
3.1进程管理
3.1.1 进程设置
设置进程的基本信息（进程号、到达时间、响应比、随机生成 需要运行时间），设置初始化进程列表，设置进程数量为8个。

代码实现：

public static List<double []> task_info=new ArrayList<>();//进程列表
public static int task_num=8;//进程数

public static void init_task()//初始化进程列表
{
for(int i=0;i<task_num;i++)
{
double[] t=new double[4];
t[0]=i;//进程号
t[1]=0;//到达时间
t[2]=0;//响应比
t[3]=(int)(Math.random()*100)%20+1;//随机生成 需要运行时间

task_info.add(t);
}
}

进程控制块PCB

public class PCB {
int ID;//进程标识数
int status;//进程状态
int outputFileCount;//要输出的文件数
int outPut_X;//进程输出时的临时变量
}

3.1.2 进程调度流程
进程调度流程描述：

小组实现的调度算法有：优先级进程调度、时间片轮转算法
进程调度函数的主要工作：将正在运行的进程保存在该进程对应进程控制块中；从就绪队列中选择一个进程；将该进程中进程控制块中记录的各寄存器内容恢复到CPU各个寄存器内
以下为进程调度算法的总体算法描述（图表1）：

图表 1进程调度框架图

3.1.3进程调度算法--优先级进程调度算法（抢占式）
算法描述：
进程调度采用抢占式优先级调度算法，只要系统中出现一个新的就绪进程，就进行优先权比较 。若出现优先权更高的进程，则立即停止当前执行，并将处理机分配给新到的优先权最高的进程。

图表 2 优先级进程调度算法
代码实现：

public static void HRRN(){

for(int i=0;i<task_num;i++)
{
get_ratio(); //每次循环时计算一次响应比
double [] tem=get_a_task();//从进程列表中得到一个最高响应比的任务
System.out.print(tm.format(new Date())+"第"+(int)tem[0]+"号进程开始运行--->");
try {
Thread.sleep((long) tem[3]*1000);//模拟进程执行所需要的时间
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(tm.format(new Date())+"进程结束运行<---用时为"+(int)tem[3]+"s");
//加入进程周转时间列表
double[] exe_t=new double[2];
exe_t[0]=tem[0];
exe_t[1]=System.currentTimeMillis() - tem[1];
execute_time.add(exe_t);
}
show_time();//显示每个进程的周转时间
}

3.1.4进程调度算法--时间片轮转调度算法（RR）
算法描述：
进程采用时间片轮转调度算法，根据先来先服务的原则，将需要执行的所有进程按照到达时间的大小排成一个升序的序列，每次都给一个进程同样大小的时间片，在这个时间片内如果进程执行结束了，那么把进程从进程队列中删去，如果进程没有结束，那么把该进程停止然后改为等待状态，放到进程队列的尾部，直到所有的进程都已执行完毕

图表 3 时间片轮转调度算法流程图
代码实现：

try {
while (true) {
double[] t = new double[4]; //表示一个进程
t = (double[])task_q.take();
int current_task_time=(int)t[3]; //需要运行时间
int task_NO=(int)t[0]; //进程号
System.out.print(tm.format(new Date())+"第" +task_NO+"号进程开始运行-- ");
if(current_task_time<=Circle_size)//如果能够在本时间片中运行完成
{
Thread.sleep((long) current_task_time*1000);//模拟运行所需时间
System.out.println(tm.format(new Date())+"该任务已经运行完成--本次用时"+current_task_time+"S");
double[] exe_t=new double[2];
exe_t[0]=task_NO;
exe_t[1]=System.currentTimeMillis()-t[1];//计算该进程所用的周转时间
execute_time.add(exe_t);//加入到周转时间队列
}
else {//如果不能再本次时间片中运行完
t[3]=t[3]-Circle_size; //减去1个时间片
task_q.put(t); //插入进程队列尾部
Thread.sleep(Circle_size*1000);
System.out.println(tm.format(new Date())+"本次时间片用完~~进程进入【等待】状态");
}

if(task_q.size()==0)//如果进程队列为空了，就退出循环
break;
}
}

3.2存储管理
3.2.1页的设置
public class page {
private int pageNumber;//页号
private int physicsNumber;//物理页号
private boolean state;//状态位
private int visitCount;//访问字段
private boolean change;//修改位
private int CRTAddress;//外存地址

public page()
{
this.pageNumber = -1;
this.physicsNumber = -1;
this.state = false;
this.visitCount = 0;
this.change = false;
this.CRTAddress = -1;
}
public page(int pageNumber, int physicsNumber, boolean state, int visitCount, boolean change, int CRTAddress)
{
this.pageNumber = pageNumber;
this.physicsNumber = physicsNumber;
this.state = state;
this.visitCount = visitCount;
this.change = change;
this.CRTAddress = CRTAddress;
}

3.2.2页查找流程
页查找流程描述：
采用页式管理存储方案，系统区包括PCB区域、数组模拟内存等

图表 4 页查找流程图

3.2.3页置换策略流程图
存储管理流程描述：
存储管理部分主要实现主存空间的分配和回收、存储保护。
算法包括：先来先服务算法、最少使用算法、最近最不常用算法

3.2.4页置换策略—先进先出算法（FIFO）
/* 1. First In First Out (FIFO) */
public static void FIFO( int n, String pages[], String frame[] ){
String page;
boolean flag;
int pageFaultCounter = 0, page_fault = 0;
/* while there are pages */
for( int pg=0 ; pg < n ; pg++ ){
page = pages[ pg ];
flag = true;
for( int j=0 ; j < frame.length ; j++ ){
if( frame[j].equals( page ) ){
flag = false;
break;
}
}
if( flag ){
frame[ pageFaultCounter ] = page;.
pageFaultCounter++;
if( pageFaultCounter == frame.length )
{
pageFaultCounter=0;
}
System.out.print( "frame: " );
for( int j=0 ; j < frame.length ; j++ )
{
System.out.print( frame[j]+" " );
}
System.out.print( " --> page fault!" );
System.out.println();
page_fault++;
}
else{
System.out.print( "frame: " );
for( int j=0 ; j < frame.length ; j++ ){
System.out.print(frame[j]+" " );
}
System.out.print( " --> page hit!" );
System.out.println();
}
}
System.out.println( "\nTotal Page Fault/s:" + page_fault + "\n" );
}

3.2.5页置换策略—最近最久未使用算法（LRU）
/* Least Recently Used (LRU) */
public static void LRU( int n, String pages[], String frame[], int frameSize ){
String page = " ";
boolean flag;
int k = 0, page_fault = 0;
String a[] = new String[ frameSize ]; */
String b[] = new String[ frameSize ];
for(int i = 0 ; i < frameSize ; i++ ){
a[ i ] = " ";
b[ i ] = " ";
}

for( int pg = 0 ; pg < n ; pg++ ){
page = pages[ pg ];
flag = true;
for( int j=0 ; j < frameSize ; j++ ){
if( frame[ j ].equals( page ) ){
flag = false;
break;
}
}

for( int j=0 ; j < frameSize && flag ; j++ ){
if( frame[ j ].equals(a[ frameSize-1 ] ) ){
k = j;
break;
}
}

if( flag ){
frame[ k ] = page;
System.out.print( "frame: " );
for(int j = 0 ; j < frameSize ; j++)
System.out.print( frame[j] + " " );
System.out.println( " --> page fault!" );
page_fault++;
}
else{
System.out.print( "frame: " );
for( int j=0 ; j < frameSize ; j++ )
System.out.print( frame[ j ]+" " );
System.out.println( " --> page hit!" );
}

int p = 1;
b[ 0 ] = page;
for( int j=0 ; j < a.length ; j++ ){
if( !page.equals( a[ j ] ) && p < frameSize ) {
b[ p ] = a[ j ];
p++;
}
}
for( int j = 0 ; j < frameSize ; j++ ){
a[ j ] = b[ j ];
}
}
System.out.println( "\nTotal Page Fault/s: "+ page_fault + "\n" );
}
3.2.6页置换策略—最近最不常用算法（LFU）
/* Least Frequently Used (LFU) */
public static void LFU( int n, String pages[], String frame[], int frameSize ){
int k = 0, page_fault = 0;
int leastFrequency;
String page;
int Frequency[] = new int[ frameSize ];
boolean flag = true;
for(int i = 0 ; i < frameSize ; i++ ){
Frequency[ i ] = 0;
}
for( int pg = 0 ; pg < n ; pg++ ){
page = pages[ pg ];
flag = true;

for( int j=0 ; j < frameSize ; j++ ){
if( page.equals( frame[ j ] ) ){
flag = false;
Frequency[ j ]++;
break;
}
}

if( flag ){
leastFrequency = Frequency[ 0 ];
for( int j = 0 ; j < frameSize ; j++ ){
if( Frequency[ j ] < leastFrequency ){
leastFrequency = Frequency[ j ];
break;
}
}
for( int j = 0 ; j < frameSize ; j++ ){
if( leastFrequency == Frequency[ j ] ){
frame[ j ] = page;
k = j;
break;
}
}
Frequency[ k ] = 1;
System.out.print( "frame: " );
for( int j = 0 ; j < frameSize ; j++ ){
System.out.print( frame[ j ]+" " );
page_fault++;
}
System.out.println( " --> Page fault!" );
}
else{
System.out.print( "frame: " );
for( int j = 0 ; j < frameSize ; j++ )
System.out.print( frame[ j ]+" " );
System.out.print( " --> Page hit!" );
System.out.println();
}
}
System.out.println( "\nTotal Page Fault/s: " + page_fault + "\n" );
}

3.3文件管理

图表 5 文件管理流程图
文件管理流程描述：
文件管理主要实现以下功能：文件设置 文件和目录的创建 修改文件类型 打开文件或文件夹功能 删除目录下的文件 删除空目录、修改、添加、释放FAT表
3.3.1文件的设置
方法描述：
建立一个fileModel方法用来记录文件以及目录的相关属性，相关属性见以下代码及注释：

public class fileModel {
//fileModel类用来记录文件或目录的相关属性
public Map<String, fileModel> subMap = new HashMap<String, fileModel>();
private String name; //文件名或目录名
private String type; //文件类型
private int attr; //用来识别是文件还是目录
private int startNum; //在FAT表中起始位置
private int size; //文件的大小
private fileModel father = null; //该文件或目录的上级目录
3.3.2创建文件和目录
方法描述：
用“createFile”方法创建一个文件。首先需要判断该路径下是否有多余的空间建立目标文件，其次需要判定在该路径下是否有相同扩展名的同名文件，如若存在同名文件，则系统提示该文件创建失败；如若没有同名文件，则文件添加继续，记录上层目录并于父目录添加文件
判断是否存在所建路径的函数如下：

public void createFile( String name, String type, int size ) {

if( fat[ 0 ] >= size ) { //判断磁盘剩余空间是否足够建立文件
fileModel value = nowCatalog.subMap.get( name ); //该目录下是否寻找同名目录或文件
if( value != null ) { //判断该文件是否存在
if( value.getAttr() == 3 ) { //若存在同名目录 继续创建文件
int startNum = setFat( size );
fileModel file = new fileModel( name, type, startNum, size );
file.setFather( nowCatalog ); //纪录上一层目录
nowCatalog.subMap.put( name, file ); //在父目录添加该文件
totalFiles.put( file.getName(), file );
fat[ 0 ] -= size;
System.out.println( "File is successfully created!" );
showFile();
} else if( value.getAttr() == 2 ) { //若同名文件已存在，创建失败
System.out.println("File fails to create because the file already exists");
showFile();
}
} else if( value == null ) { //若无同名文件或文件夹，继续创建文件
int startNum = setFat( size );
fileModel file = new fileModel( name, type, startNum, size );
file.setFather( nowCatalog ); //纪录上一层目录
nowCatalog.subMap.put( name, file ); //在父目录添加该文件
totalFiles.put( file.getName(), file );
fat[0] -= size;
System.out.println( "File is successfully created!");
showFile();
}
} else {
System.out.println("File fails to create because insufficient disk space！");
}

}

3.3.3 显示该目录下的所有文件
方法描述：
用showFile方法显示指定目录下的所有文件，显示的目录文件格式如下：

public void showFile() {
System.out.println("------------------ < " + nowCatalog.getName() + " > ------------------");

if( !nowCatalog.subMap.isEmpty() ) {
for( fileModel value : nowCatalog.subMap.values() ) {
if(value.getAttr() == 3) { //目录文件
System.out.println("文件名:" + value.getName());
System.out.println("操作类型:" + "文件夹");
System.out.println("启动磁盘块:" + value.getStartNum());
System.out.println("大小: " + value.getSize());
System.out.println("<-------------------------------------->");
}
else if(value.getAttr() == 2) {
System.out.println("文件名:" + value.getName() + "." + value.getType());
System.out.println("操作类型: " + "可读 & 可写 文件");
System.out.println("启动磁盘块:" + value.getStartNum());
System.out.println("大小:" + value.getSize());
System.out.println("<-------------------------------------->");
}
}
}
for(int i =0; i<2; i++)
System.out.println();
System.out.println("磁盘剩余空间:" + fat[ 0 ] + " " + "退出系统，请输入:exit");
System.out.println();
}

3.3.4修改文件类型
方法描述：
判断要更改的文件的所在路径是否存在，再判断要更改的文件是否存在，判断语句如下：

public void changeType( String name, String type ) {

nowCatalog = nowCatalog.getFather();
if( nowCatalog.subMap.containsKey( name ) ) {
fileModel value = nowCatalog.subMap.get( name );
if(value.getAttr() == 2){
value.setType(type);
nowCatalog.subMap.remove(name);
nowCatalog.subMap.put(name, value);
System.out.println("Modify type success!");
showFile();
}
else if(value.getAttr() == 3) {
System.out.println("Change error because the folder can not modify type!！");
openFile( value.getName() );
}
}
else {
System.out.println("Modify error, please check whether the input file name is correct！");
}
}

3.3.5打开文件或文件夹方法
方法描述：
首先判断该文件或文件夹所在路径是否正确，如若路径正确，则打开对应文件或文件夹，反之系统显示未找到该文件
public void openFile( String name ) {
if( nowCatalog.subMap.containsKey( name ) ) {
fileModel value = nowCatalog.subMap.get(name);
if(value.getAttr() == 2) {
nowCatalog = value;
System.out.println("The file has been opened and the file size is: " + value.getSize() );