一、 需求分析
说明程序设计的任务和目的，明确规定下述内容：
加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应 算法、最佳适应算法和最坏适应算法的实现方法。
(1) 输入的形式和输入值的范围；
已在程序中预置好内存和进程等信息
(2) 输出的形式；
按内存地址从低到高的顺序输出内存状态和进程的分配结果
(3) 程序所能达到的功能；
模拟首次适应算法、循环首次适应 算法、最佳适应算法和最坏适应算法对内存进行分配
(4) 测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。
进程信息
内存信息（一个 . 代表一个内存单元，| 代表 内存块之间的划分）
二、 概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
进程对象
classProcess
{
publicstring name;
publicint needSpace;
}
内存块对象
classSpace
{
privatestaticstring usedFlag = "1";
privatestaticstring freeFlag = ".";
publicint id;//空间编号（从小到大排序）
publicint startIndex;//空间开始索引
publicint freeStartIndex;//空闲指针[空间内的相对位置0-空间大小]
publicint freeSize;//空间块空闲大小
publicList<string> SpaceDetail;//空间详情
privateList<string>SpaceDetailNote;//【辅助变量】空间详情描述，便于观察分配结果
privateint NoteStartIndex;//【辅助变量】空间块空闲大小
}
内存对象
classRAM
{
publicint size;//内存大小
publicList<Space> spaceDetail;//内存块详情
}
三、 详细设计
实现程序模块的具体算法。
publicbool FirstPartition(List<Process> processList)
publicbool CycleFirstPartition(List<Process> processList)
publicbool BestPartition(List<Process> processList)
publicbool WorstPartition(List<Process> processList)
四、 调试分析
(1) 调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析；
完全采用C#用面向对象的方式编写，编程过程十分顺利
五、 用户使用说明
程序的使用说明，列出每一步的操作步骤。
运行程序---查看结果
六、 测试结果
列出测试结果，包括输入和输出。
七、 附录
带注释的源程序，注释应清楚具体；
using Lab4;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Lab4
{
class Process
{
public string name;
public int needSpace;
public Process(string name, int needSpace)
{
this.name = name;
this.needSpace = needSpace;
}
}
class Space
{
private static string usedFlag = "1";
private static string freeFlag = ".";
public int id;//空间编号（从小到大排序）
public int startIndex;//空间开始索引
public int freeStartIndex;//空闲指针[空间内的相对位置0-空间大小]
public int freeSize;//空间块空闲大小
public List<string> SpaceDetail;//空间详情
private List<string> SpaceDetailNote;//【辅助变量】空间详情描述，便于观察分配结果
private int NoteStartIndex;//【辅助变量】空间块空闲大小
public Space(int id, int startIndex, int size)
{
this.id = id;
this.startIndex = startIndex;
freeStartIndex = 0;
freeSize = size;
SpaceDetail = new List<string>(); SpaceDetailNote = new List<string>(); NoteStartIndex = 0;
for (int i = 0; i < size; i++)
{
SpaceDetail.Add(freeFlag); SpaceDetailNote.Add(freeFlag);
}
}
public void useSpace(Process process)
{
for (int i = freeStartIndex; i < freeStartIndex + process.needSpace; i++)
{
SpaceDetail[i] = usedFlag;
}
freeSize -= process.needSpace;
freeStartIndex = SpaceDetail.Count - freeSize - 1;
SpaceDetailNote.RemoveRange(NoteStartIndex, process.needSpace); SpaceDetailNote.Insert(NoteStartIndex, process.name + "[" + process.needSpace + "]"); NoteStartIndex++;
}
public void printSpace()
{
for (int i = 0; i < SpaceDetail.Count; i++)
{
Console.Write(SpaceDetail[i]);
}
}
public void printSpaceNote()
{
for (int i = 0; i < SpaceDetailNote.Count; i++)
{
Console.Write(SpaceDetailNote[i]);
}
}
}
class RAM
{
public int size;//内存大小
public List<Space> spaceDetail;//内存块详情
public RAM(int[] spaceSizeArray)
{
size = 0;
spaceDetail = new List<Space>();
for (int i = 0; i < spaceSizeArray.Length; i++)
{
spaceDetail.Add(new Space(i, size, spaceSizeArray[i]));
size += spaceSizeArray[i];
}
}
public void printRAM(bool printNote = false)
{
//打印前将存储块从小到大排序
spaceDetail = spaceDetail.OrderBy(m => m.id).ToList();
Console.WriteLine("当前RAM状态如下： \n");
foreach (var space in spaceDetail)
{
space.printSpace();
Console.Write("|");
//Console.WriteLine(space.id + "[" + space.startIndex + "," + (space.startIndex + space.SpaceDetail.Count-1) + "]");
}
Console.WriteLine("\n");
if (printNote)
{
foreach (var space in spaceDetail)
{
space.printSpaceNote();
Console.Write("|");
//Console.WriteLine(space.id + "[" + space.startIndex + "," + (space.startIndex + space.SpaceDetail.Count-1) + "]");
}
Console.WriteLine("\n");
}
}
//首次适应算法
public bool FirstPartition(List<Process> processList)
{
Console.WriteLine("首次适应算法进行中...");
//默认分配成功次数
int succcefulCount = 0;
//遍历所有进程
for (int i = 0; i < processList.Count; i++)
{
//遍历所有空间块
for (int j = 0; j < spaceDetail.Count; j++)
{
//如果空间充足
if (spaceDetail[j].freeSize >= processList[i].needSpace)
{
//分配空间并转至处理下一进程
spaceDetail[j].useSpace(processList[i]);
succcefulCount += 1;
break;
}
}
}
return succcefulCount == processList.Count ? true : false;
}
//循环首次适应算法
public bool CycleFirstPartition(List<Process> processList)
{
Console.WriteLine("循环首次适应算法进行中...");
//记录上次空间块的位置和1个进程比较空间块的次数
int spaceIndex = 0, compareCount = 0;
//默认分配成功次数
int succcefulCount = 0;
//遍历所有进程
for (int i = 0; i < processList.Count; i++)
{
//切换到新进程时重置比较次数
compareCount = 0;
//循环遍历所有空间块
while (compareCount < spaceDetail.Count)
{
//如果比较了所有空间块则终止，防止死循环！
if (compareCount == spaceDetail.Count)
{
compareCount = spaceDetail.Count;//同时跳出第二层循环
break;
}
//取模运算,防止循环越界!
if (spaceIndex >= spaceDetail.Count)
{
spaceIndex = spaceIndex % spaceDetail.Count;
}
//如果空间充足
if (spaceDetail[spaceIndex].freeSize >= processList[i].needSpace)
{
//分配空间并转至处理下一进程
spaceDetail[spaceIndex].useSpace(processList[i]);
succcefulCount++;
spaceIndex++;//移动指针到下一空间
break;
}
spaceIndex++;//移动指针
}
}
return succcefulCount == processList.Count ? true : false;
}
//最佳适应算法
public bool BestPartition(List<Process> processList)
{
Console.WriteLine("最佳适应算法进行中...");
//默认分配成功次数
int succcefulCount = 0;
//遍历所有进程
for (int i = 0; i < processList.Count; i++)
{
//空间块排序(按剩余空间从小到大)
spaceDetail = spaceDetail.OrderBy(m => m.freeSize).ToList();
//取出空间访问顺序
List<int> orders = (from t in spaceDetail select t.id).ToList();
//按访问顺序遍历所有空间块
for (int j = 0; j < orders.Count; j++)
{
int order = orders[j];
Space space = (from t in spaceDetail where t.id == order select t).FirstOrDefault();
//如果空间充足
if (space.freeSize >= processList[i].needSpace)
{
//分配空间并转至处理下一进程
spaceDetail[j].useSpace(processList[i]);
succcefulCount += 1;
break;
}
}
}
return succcefulCount == processList.Count ? true : false;
}
//最坏适应算法
public bool WorstPartition(List<Process> processList)
{
Console.WriteLine("最坏适应算法进行中...");
//默认分配成功次数
int succcefulCount = 0;
//遍历所有进程
for (int i = 0; i < processList.Count; i++)
{
//空间块排序(按剩余空间从大到小)
spaceDetail = spaceDetail.OrderByDescending(m => m.freeSize).ToList();
//取出空间访问顺序
List<int> orders = (from t in spaceDetail select t.id).ToList();
//按访问顺序遍历所有空间块
for (int j = 0; j < orders.Count; j++)
{
int order = orders[j];
Space space = (from t in spaceDetail where t.id == order select t).FirstOrDefault();
//如果空间充足
if (space.freeSize >= processList[i].needSpace)
{
//分配空间并转至处理下一进程
spaceDetail[j].useSpace(processList[i]);
succcefulCount += 1;
break;
}
}
}
return succcefulCount == processList.Count ? true : false;
}
}
class Tool
{
public static void PrintProcessList(List<Process> processList)
{
Console.WriteLine("----------进程列表如下: \n");
for (int i = 0; i < processList.Count; i++)
{
Console.Write("进程名 " + processList[i].name + " 进程所需空间大小" + processList[i].needSpace+"\n");
}
Console.WriteLine("\n提示： . 表示未使用, 1 表示已被进程占用 \n");
}
}
}
class Program
{
static void Main(string[] args)
{
Console.WriteLine("----------动态分区分配算法----------- \n");
//初始化进程
List<Process> processList = new List<Process>();
processList.Add(new Process("A", 7));
processList.Add(new Process("B", 18));
processList.Add(new Process("C", 9));
processList.Add(new Process("D", 20));
//初始化内存
int[] spaceSizeArray = new int[] { 16, 16, 8, 32, 64, 32 };
//打印信息
Tool.PrintProcessList(processList);
var r1 = new RAM(spaceSizeArray); r1.printRAM();
if (r1.FirstPartition(processList))
{
r1.printRAM(true);
}
else
{
Console.Write("警告:RAM不足,部分进程未处理!!! \n");
r1.printRAM(true);
}
var r2 = new RAM(spaceSizeArray); r2.CycleFirstPartition(processList); r2.printRAM(true);
var r3 = new RAM(spaceSizeArray); r3.BestPartition(processList); r3.printRAM(true);
var r4 = new RAM(spaceSizeArray); r4.WorstPartition(processList); r4.printRAM(true);
Console.ReadLine();
}
}