实验要求
完成进程调度的可视化。
包括六种调度算法：
public enum SchdType { [Description("先来先服务")] FCFS, [Description("最短作业优先")] SJF, [Description("最短剩余时间优先")] SRTF, [Description("最高响应比优先")] HRRF, [Description("优先级调度")] PRIOR, [Description("轮转调度")] RR, }
设计思路
使用C# WindowsForm易于开发。
- 调度算法基于LINQ；
- 所有调度算法采用统一的接口；
- 用DataGridView呈现和更改初始数据；
- 用GDI+实现绘图。
数据结构
初始数据结构：
public class SimpleTask { [Unique] [DefaultValue("Task")] [Description("作业名")] public string Name { set; get; } [DefaultValue(0)] [Description("开始时间")] public int StartTime { set; get; } [DefaultValue(1)] [Description("运行时间")] public int ExecuteTime { set; get; } [DefaultValue(0)] [Description("优先级")] public int Priority { set; get; } }
初始化：
void InitTestData() { data.Rows.Add(new object[] { "A", 0, 3, 5 }); data.Rows.Add(new object[] { "B", 2, 6, 2 }); data.Rows.Add(new object[] { "C", 4, 4, 3 }); data.Rows.Add(new object[] { "D", 6, 5, 4 }); data.Rows.Add(new object[] { "E", 8, 2, 1 }); }
运行时调度结构：
public class SchdRestModel { public SimpleTask task { set; get; } public int rest { set; get; }//剩余运行时间 public double temp { set; get; }//用于存储响应比 }
输入输出结构：
public class SimulationResult { public List<SimpleTask> tasks { set; get; } public List<string> cpu_clips { set; get; } }
可视化结构：
public class VisualStruct { public DuringStruct during { set; get; } public List<Tuple<int, int>> cpu_clips { set; get; } } public class VisualData { public Dictionary<string, VisualStruct> visual { set; get; } public List<int> switches { set; get; } }
参数设置：
public class SchdSettings { private static int _TimeSpan = 1; public static int TimeSpan { set { _TimeSpan = value; } get { return _TimeSpan; } } public static readonly int MaxTimeSpan = 10; public static readonly int MinTimeSpan = 1; } public class VisualSettings { public static readonly int TimeSpanWidth = 30; public static readonly int TaskHeight = 30; public static readonly int TaskSpacing = 20; public static readonly int TaskBlanking = 20; public static readonly int TimeHeight = 20; public static readonly int DegreeHeight = 5; public static readonly int DispTextWidth = 100; public static readonly int Margin = 5; }
设计实现
一、接口及抽象类
调度接口：
public interface IProcessSchd { void ImportData(IEnumerable<SimpleTask> tasks); void SetCallback(Action<string> action); SimulationResult Simulate(); }
抽象基类：
public abstract class ProcessSchd : IProcessSchd { protected IEnumerable<SimpleTask> origin_tasks; protected Action<string> action; public void ImportData(IEnumerable<SimpleTask> tasks) { origin_tasks = tasks; } public void SetCallback(Action<string> action) { this.action = action; } public abstract SimulationResult Simulate(); }
工厂模式构建：
public class SchdFactory { static public IProcessSchd CreateSchdInstance(SchdType type) { return Assembly.GetExecutingAssembly().CreateInstance("SimuProcessSchd.Schd" + type.ToString()) as IProcessSchd; } }
二、通用算法
2.1 通用算法版本一（适用于除轮转调度以外的五种调度算法）
/// <summary> /// 通用调度算法版本一 /// </summary> /// <param name="task">运行时处理队列</param> /// <param name="blocked">是否独占式调度（非剥夺）</param> /// <param name="select">自定义任务竞取函数</param> /// <returns></returns> static public List<string> GetSimuResultDirectV1(IEnumerable<SchdRestModel> task, bool blocked, Func<IEnumerable<SchdRestModel>, int, IEnumerable<SchdRestModel>> select) { var list = new List<string>();//用于存放结果 var new_list = task.ToList();//当前任务队列的拷贝，用于调度 IEnumerable<SchdRestModel> selected = null; for (int i = 0; new_list.Count() > 0; i++)//进行运行时调度，当前队列为空时结束 { //当规定为可剥夺时，初始化任务竞取函数，用于选取下一任务 if (!blocked || (blocked && selected == null)) selected = select(new_list, i); if (selected.Count() > 0)//可以选取下一任务 { var running = selected.First();//取下一任务队列头 list.Add(running.task.Name);//当前时刻处理该任务并记录任务名 if (running.rest > 1)//当前任务还有剩余运行时间 { //当前运行的任务的剩余时间减一 new_list.Find(a => a.task.Name == running.task.Name).rest--; } else//当前任务已完成 { if (selected != null) selected = null;//清空竞取函数 //从调度队列中除去该任务 new_list.RemoveAll(a => a.task.Name == running.task.Name); } } else//已经没有任务可选取，收尾工作 { if (selected != null) selected = null; list.Add(null); } } return list; }
2.2 通用算法版本二（只适用于轮转调度）
/// <summary> /// 通用调度算法版本二 /// </summary> /// <param name="task">起始的任务队列</param> /// <returns>模拟调度结果</returns> static public List<string> GetSimuResultDirectV2(IEnumerable<SchdRestModel> task) { var list = new List<string>(); //采用双队列，后备和轮转 var backup = task.ToList(); // 后备队列 var round = new List<SchdRestModel>(); // 轮转队列 //当双队列都不为空时，继续运行，i为时刻 for (int i = 0; backup.Count > 0 || round.Count > 0; i++) { SchdRestModel current = null; // 检查后备 if (round.Count == 0)//当前轮转队列为空时，取后备队列 { round.AddRange( from x in backup where x.task.StartTime <= i orderby x.task.StartTime//按起始时间 orderby x.task.Priority//按优先级 select x); backup.RemoveAll(a => a.task.StartTime <= i);//做移动操作，将旧的删除 } // 处理轮转 if (round.Count > 0)//轮转不为空，则有任务 { current = round.First();//取队列头 round.RemoveAt(0);//清除 } // 取出队头并处理 if (current != null) { var min = Math.Min(current.rest, SchdSettings.TimeSpan);//轮转时独占时长的限制 current.rest -= min;//减去当前运行时间 for (int j = 0; j < min; j++) { list.Add(current.task.Name);//添加运行记录 } if (current.rest <= 0) { current = null;//没有剩余时间则丢弃 } i += min - 1;//时刻表推进，由于for循环对i有自增操作，所以这里减一 } else { list.Add(null);//结束标记 } // 再次处理后备 { round.AddRange( from x in backup where x.task.StartTime <= i + 1 orderby x.task.StartTime orderby x.task.Priority select x); backup.RemoveAll(a => a.task.StartTime <= i + 1); } // 将当前任务放至队尾 if (current != null) { round.Add(current); } } return list; }
三、具体算法
/// <summary> /// 先来先服务 /// </summary> public class SchdFCFS : ProcessSchd { public override SimulationResult Simulate() { var result = new SimulationResult() { tasks = origin_tasks.ToList() }; result.cpu_clips = SchdImplHelper.GetSimuResultDirectV1( from x in origin_tasks orderby x.StartTime select new SchdRestModel { task = x, rest = x.ExecuteTime, }, true, (a, i) => from x in a where x.task.StartTime <= i select x ); return result; } } /// <summary> /// 最短作业优先 /// </summary> public class SchdSJF : ProcessSchd { public override SimulationResult Simulate() { var result = new SimulationResult() { tasks = origin_tasks.ToList() }; result.cpu_clips = SchdImplHelper.GetSimuResultDirectV1( from x in origin_tasks orderby x.StartTime select new SchdRestModel { task = x, rest = x.ExecuteTime, }, true, (a, i) => from x in a where x.task.StartTime <= i orderby x.task.ExecuteTime select x ); return result; } } /// <summary> /// 最短剩余时间优先 /// </summary> public class SchdSRTF : ProcessSchd { public override SimulationResult Simulate() { var result = new SimulationResult() { tasks = origin_tasks.ToList() }; result.cpu_clips = SchdImplHelper.GetSimuResultDirectV1( from x in origin_tasks orderby x.ExecuteTime select new SchdRestModel { task = x, rest = x.ExecuteTime, }, false, (a, i) => from x in a where x.task.StartTime <= i orderby x.rest select x ); return result; } } /// <summary> /// 最高响应比优先 /// </summary> public class SchdHRRF : ProcessSchd { public override SimulationResult Simulate() { var result = new SimulationResult() { tasks = origin_tasks.ToList() }; result.cpu_clips = SchdImplHelper.GetSimuResultDirectV1( from x in origin_tasks orderby x.StartTime select new SchdRestModel { task = x, rest = x.ExecuteTime, }, true, (a, i) => from y in (from x in a where x.task.StartTime <= i select new SchdRestModel { task = x.task, rest = x.rest, temp = ((double)i - (double)x.task.StartTime) / (double)x.task.ExecuteTime }) orderby y.temp descending select y ); return result; } } public class SchdPRIOR : ProcessSchd { public override SimulationResult Simulate() { var result = new SimulationResult() { tasks = origin_tasks.ToList() }; result.cpu_clips = SchdImplHelper.GetSimuResultDirectV1( from x in origin_tasks orderby x.StartTime select new SchdRestModel { task = x, rest = x.ExecuteTime, }, false, (a, i) => (from x in a where x.task.StartTime <= i orderby x.task.Priority select x) ); return result; } } public class SchdRR : ProcessSchd { public override SimulationResult Simulate() { var result = new SimulationResult() { tasks = origin_tasks.ToList() }; result.cpu_clips = SchdImplHelper.GetSimuResultDirectV2( from x in origin_tasks select new SchdRestModel { task = x, rest = x.ExecuteTime, }); return result; } }