【OS】FCFS,SJF,SRT
班级:软1708
姓名:黄万鸿
学号:201792015
算法选择:FCFS,SJF,SRT
[TOC]
运行结果展示
程序内部，使用时钟进行每次时间+1的模拟，为了简化输出，只输出重要的时间点（非每个单位时间都输出）
第一部分:FCFS
执行过程:
结果评估:
第二部分:SJF
执行过程: 
结果评估:
第三部分:SRT
执行过程: 
结果评估:
源代码
1.主函数
static void Main(string[] args)
{
//从命令行获取数据
List<sim_process> sps = getTask_FromCom();
List<sim_process> sps_c1 = new List<sim_process>();
List<sim_process> sps_c2 = new List<sim_process>();
sps.ForEach((item) => sps_c1.Add(new sim_process(item.need_T, item.taskname, item.arriveT)));
sps.ForEach((item) => sps_c2.Add(new sim_process(item.need_T, item.taskname, item.arriveT)));
sceduler sc = new sceduler();
//创建模拟进程
foreach(sim_process spi in sps)
{
sc.insertprocess(spi);
}
sc.FCFS();
sc.cleanqueue();
foreach (sim_process spi in sps_c1)
{
sc.insertprocess(spi);
}
sc.SJF();
sc.cleanqueue();
foreach (sim_process spi in sps_c2)
{
sc.insertprocess(spi);
}
sc.SRT();
Console.ReadLine();
}
获取数据的函数
static List<sim_process> getTask_FromCom()
{
List<sim_process> sps = new List<sim_process>();
Console.WriteLine("请按 进程号 到达时间 要求执行时间 的格式输入(输入-1结束):");
while (true)
{
int[] c=new int[3];
string input = Console.ReadLine();
string[] ss = input.Split(' ');
for(int i = 0;i<ss.Length;i++)
{
if (Int32.Parse(ss[i]) == -1) return sps;
c[i] = Int32.Parse(ss[i]);
}
sps.Add(new sim_process(c[2], c[0].ToString(), c[1]));
}
return sps;
}
模拟作业类
class sim_process
{
static Random r = new Random();
public int pid;
public string taskname;
public int need_T; //任务所需时间
public int arriveT = 0;
public int waitT = 0;
public int endT = 0;
public int startT = 0;
public sim_process(int T,string name,int arrt=0) //提供所需时间，名字，到达时间（默认为0）
{
need_T = T;
taskname = name;
arriveT = arrt;
pid = r.Next(0,10000) ; //随机获取一个虚拟PID
}
}
调度器类
class sceduler
{
List<sim_process> queue = new List<sim_process>(); //任务列表
int curT = 0;
public void cleanqueue() //清空任务列表
{
queue = new List<sim_process>();
}
public void initTimer()
{
curT = 0;
}
public void insertprocess(sim_process sp) //加入一个任务到任务列表
{
queue.Add(sp);
}
//先来先服务
public void FCFS()
{
foreach (sim_process sp in queue)
{
Console.WriteLine("作业" + sp.taskname + "(区间时间=" + sp.need_T.ToString() + ") 加入任务列表，等待调度 simulate pid=" + sp.pid.ToString());
}
Console.WriteLine("----------------------Sceduling Start(FCFS)------------------------");
List<sim_process> curQueue = new List<sim_process>(); //调度列表
List<sim_process> exesx = new List<sim_process>(); //一个list保存执行顺序
int curRUN = -1; //当前执行的任务标志（代表当前执行调度列表中的哪任务）
int i = queue.Count; //记录需要执行的进程数
int curT = 0;
//开始执行调度
while (true)
{
//检测是否有进程进入
foreach (sim_process s in queue)
{
if (s.arriveT == curT)
{
curQueue.Add(s);
Console.WriteLine("In " + curT.ToString() + " Task:" + s.taskname + " arrived");
}
}
//调度为空，那就不管，时间+1后继续
if (curQueue.Count == 0) { curT++; continue; }
//是否空闲，空闲则调度一个
if (curRUN == -1)
{
curRUN = 0;
//修改信息，循环是为了找到当前正在执行的任务在任务列表中的位置
for (int k = 0; k < queue.Count; k++)
{
if (queue[k].pid == curQueue[0].pid)
{
queue[k].startT = curT;
exesx.Add(queue[k]);
}
}
Console.WriteLine("In T=" + curT.ToString() + " Task:" + curQueue[curRUN].taskname + " start");
}
//非空闲，看是否结束
else
{
for (int k = 0; k < queue.Count; k++)
{
if (queue[k].pid == curQueue[0].pid)
{
//Console.WriteLine(queue[k].startT.ToString() +","+ queue[k].need_T.ToString());
if (queue[k].startT + queue[k].need_T == curT)//一个任务的结束条件
{
Console.WriteLine("In T=" + curT.ToString() + " Task:" + curQueue[curRUN].taskname + " End");
curRUN = -1;
i--;
curQueue.RemoveAt(0);
queue[k].endT = curT;
//检查看是否需要开启新进程
if (curQueue.Count != 0)
{
curRUN = 0;
int j = 0;
for (; j < queue.Count; j++)
{
if (queue[j].pid == curQueue[curRUN].pid)
{
queue[j].startT = curT;
//queue[j].waitT++;
exesx.Add(queue[j]);
break;
}
}
Console.WriteLine("In T=" + curT.ToString() + " Task:" + queue[j].taskname + " start");
}
}
}
}
}
/*foreach (sim_process s in queue)
{
Console.WriteLine("t=" + curT.ToString() + " 调度作业:" + s.taskname);
s.waitT = curT;
curT += s.need_T;
s.endT = curT;
}*/
for (int k = 1; k < curQueue.Count; k++)
{
for (int l = 0; l < queue.Count; l++)
{
if (queue[l].pid == curQueue[k].pid)
{
queue[l].waitT++;
}
}
}
if (i <= 0) break;
curT++;
}
Console.WriteLine("t=" + curT.ToString() + " 调度结束");
Console.WriteLine("----------------------Sceduling End(FCFS)------------------------");
//开始评估
Console.WriteLine("----------------------Evaluation(FCFS)------------------------");
int avgwait = 0;
double avgdc = 0;
double avgzz = 0;
foreach (sim_process s in queue)
{
avgzz += (s.endT - s.arriveT);
avgwait += s.waitT;
Console.WriteLine("Task:" + s.taskname + " arrive at:" + s.arriveT.ToString() + " end at:" + s.endT.ToString() + " Wait Time:" + s.waitT.ToString() + " 周转时间:" + (s.endT - s.arriveT).ToString() + " 带权周转时间:" + ((s.endT - s.arriveT) / (double)s.need_T).ToString());
avgdc += ((s.endT - s.arriveT) / (double)s.need_T);
}
Console.WriteLine("Average Wait:" + (avgwait / queue.Count).ToString());
Console.WriteLine("平均周转:" + (avgzz / queue.Count).ToString());
Console.WriteLine("平均带权周转:" + (avgdc / queue.Count).ToString());
foreach (sim_process sr in exesx)
{
Console.Write(sr.taskname + "->");
}
Console.Write("\n\n\n\n");
cleanqueue();
}
public void SJF()
{
foreach (sim_process sp in queue)
{
Console.WriteLine("作业" + sp.taskname + "(区间时间=" + sp.need_T.ToString() + ") 加入队列 simulate pid=" + sp.pid.ToString());
}
Console.WriteLine("----------------------Sceduling Start(SJF)------------------------");
List<sim_process> curQueue = new List<sim_process>();
List<sim_process> exesx = new List<sim_process>();
int curRUN = -1;
int i = queue.Count; //记录需要执行的进程数
int curT = 0;
//开始执行调度
while (true)
{
//检测是否有任务进入，若有的话，加入调度队列
foreach (sim_process s in queue)
{
if (s.arriveT == curT)
{
curQueue.Add(s);
Console.WriteLine("In " + curT.ToString() + " Task:" + s.taskname + " arrived");
}
}
if (curQueue.Count == 0) { curT++; continue; } //如果调度队列为空，不管
//是否空闲，空闲则调度一个
if (curRUN == -1)
{
curRUN = 0;
//寻找最短作业
for (int m = 0; m < curQueue.Count; m++)
{
if (curQueue[m].need_T < curQueue[curRUN].need_T) { curRUN = m; }
}
//修改原进程信息
for (int k = 0; k < queue.Count; k++)
{
if (queue[k].pid == curQueue[curRUN].pid)
{
queue[k].startT = curT;
exesx.Add(queue[k]);
}
}
Console.WriteLine("In T=" + curT.ToString() + " Task:" + curQueue[curRUN].taskname + " start");
}
//非空闲，看是否结束
else
{
for (int k = 0; k < queue.Count; k++)
{
if (curRUN == -1) break;
if (queue[k].pid == curQueue[curRUN].pid)
{
//Console.WriteLine(queue[k].startT.ToString() +","+ queue[k].need_T.ToString());
if (queue[k].startT + queue[k].need_T == curT)
{
Console.WriteLine("In T=" + curT.ToString() + " Task:" + curQueue[curRUN].taskname + " End");
curQueue.RemoveAt(curRUN);
curRUN = -1;
i--;
queue[k].endT = curT;
//检查看是否需要开启新进程
if (curQueue.Count != 0)
{
curRUN = 0;
//寻找最短作业
for (int m = 0; m < curQueue.Count; m++)
{
if (curQueue[m].need_T < curQueue[curRUN].need_T) { curRUN = m; }
}
int j = 0;
for (; j < queue.Count; j++)
{
if (queue[j].pid == curQueue[curRUN].pid)
{
queue[j].startT = curT;
//queue[j].waitT++;
exesx.Add(queue[j]);
break;
}
}
Console.WriteLine("In T=" + curT.ToString() + " Task:" + queue[j].taskname + " start");
}
}
}
}
}
/*foreach (sim_process s in queue)
{
Console.WriteLine("t=" + curT.ToString() + " 调度作业:" + s.taskname);
s.waitT = curT;
curT += s.need_T;
s.endT = curT;
}*/
for (int k = 0; k < curQueue.Count; k++)
{
if (k == curRUN) continue;
for (int l = 0; l < queue.Count; l++)
{
if (queue[l].pid == curQueue[k].pid)
{
queue[l].waitT++;
}
}
}
if (i <= 0) break;
curT++;
}
Console.WriteLine("t=" + curT.ToString() + " 调度结束");
Console.WriteLine("----------------------Sceduling End(SJF)------------------------");
Console.WriteLine("----------------------Evaluation(SJF)------------------------");
int avgwait = 0;
double avgdc = 0;
double avgzz = 0;
foreach (sim_process s in queue)
{
avgzz += (s.endT - s.arriveT);
avgwait += s.waitT;
Console.WriteLine("Task:" + s.taskname + " arrive at:" + s.arriveT.ToString() + " end at:" + s.endT.ToString() + " Wait Time:" + s.waitT.ToString() + " 周转时间:" + (s.endT - s.arriveT).ToString() + " 带权周转时间:" + ((s.endT - s.arriveT) / (double)s.need_T).ToString());
avgdc += ((s.endT - s.arriveT) / (double)s.need_T);
}
Console.WriteLine("Average Wait:" + (avgwait / queue.Count).ToString());
Console.WriteLine("平均周转:" + (avgzz / queue.Count).ToString());
Console.WriteLine("平均带权周转:" + (avgdc / queue.Count).ToString());
foreach (sim_process sr in exesx)
{
Console.Write(sr.taskname + "->");
}
Console.Write("\n\n");
cleanqueue();
}
public void SRT()
{
foreach (sim_process sp in queue)
{
Console.WriteLine("作业" + sp.taskname + "(区间时间=" + sp.need_T.ToString() + ") 加入队列 simulate pid=" + sp.pid.ToString());
}
Console.WriteLine("----------------------Sceduling Start(SRT)------------------------");
List<sim_process> curQueue = new List<sim_process>();
List<sim_process> exesx = new List<sim_process>();
List<sim_process> queue2 = new List<sim_process>();
queue.ForEach((item) => queue2.Add(new sim_process(item.need_T,item.taskname,item.arriveT)));
bool[] ifstart = new bool[queue.Count];
for (int x = 0; x < ifstart.Length; x++)
{
ifstart[x] = false;
}
int curRUN = -1;
int i = queue.Count; //记录需要执行的进程数
int curT = 0;
//开始执行调度
while (true)
{
//检测是否有任务进入，若有的话，加入调度队列
//Console.WriteLine("In T=" + curT.ToString());
foreach (sim_process s in queue)
{
if (s.arriveT == curT)
{
curQueue.Add(s);
Console.WriteLine("In " + curT.ToString() + " Task:" + s.taskname + " arrived");
}
}
if (curQueue.Count == 0) { curT++; continue; } //如果调度队列为空，不管
//是否空闲，空闲则调度一个
if (curRUN == -1)
{
curRUN = 0;
//寻找最短作业
for (int m = 0; m < curQueue.Count; m++)
{
if (curQueue[m].need_T < curQueue[curRUN].need_T) { curRUN = m; }
}
//修改原进程信息
for (int k = 0; k < queue.Count; k++)
{
if (queue[k].pid == curQueue[curRUN].pid)
{
if (!ifstart[k])
{
queue[k].startT = curT;
ifstart[k] = true;
}
exesx.Add(queue[k]);
}
}
Console.WriteLine("In T=" + curT.ToString() + " Task:" + curQueue[curRUN].taskname + " start");
}
//非空闲，看是否结束/抢占
else
{
for (int k = 0; k < queue.Count; k++)
{
if (curRUN == -1) break;
if (queue[k].pid == curQueue[curRUN].pid)
{
//Console.WriteLine(queue[k].startT.ToString() +","+ queue[k].need_T.ToString());
if (curQueue[curRUN].need_T <= 0)
{
Console.WriteLine("In T=" + curT.ToString() + " Task:" + curQueue[curRUN].taskname + " End");
curQueue.RemoveAt(curRUN);
curRUN = -1;
i--;
queue[k].endT = curT;
//检查看是否需要开启新进程
if (curQueue.Count != 0)
{
curRUN = 0;
//寻找最短作业
for (int m = 0; m < curQueue.Count; m++)
{
if (curQueue[m].need_T < curQueue[curRUN].need_T) { curRUN = m; }
}
Console.WriteLine(curRUN+curQueue[curRUN].taskname);
int j = 0;
for (; j < queue.Count; j++)
{
if (queue[j].pid == curQueue[curRUN].pid)
{
if (!ifstart[j])
{
queue[j].startT = curT;
ifstart[j] = true;
}
//queue[j].waitT++;
exesx.Add(queue[j]);
break;
}
}
Console.WriteLine("In T=" + curT.ToString() + " Task:" + queue[j].taskname + " start");
}
}
else
{
int min = curRUN;
//寻找最短作业
for (int m = 0; m < curQueue.Count; m++)
{
if (curQueue[m].need_T < curQueue[curRUN].need_T) { min = m; }
}
Console.WriteLine("T="+curT.ToString()+" 最短作业为:" + curQueue[min].taskname);
if (!(min == curRUN))
{
curRUN = min;
//修改原进程信息
for (int k2 = 0; k2 < queue.Count; k2++)
{
if (queue[k2].pid == curQueue[min].pid)
{
if (!ifstart[k2])
{
queue[k2].startT = curT;
ifstart[k2] = true;
}
Console.WriteLine("In T=" + curT.ToString() + " Task:" + queue[k2].taskname + " start");
exesx.Add(queue[k2]);
}
}
}
}
}
}
for (int k = 0; k < curQueue.Count; k++)
{
if (k == curRUN) continue;
for (int l = 0; l < queue.Count; l++)
{
if (queue[l].pid == curQueue[k].pid)
{
queue[l].waitT++;
}
}
}
if (i <= 0) break;
}
curT++;
if (curRUN != -1)
{
curQueue[curRUN].need_T--;
}
}
Console.WriteLine("t=" + curT.ToString() + " 调度结束");
Console.WriteLine("----------------------Sceduling End(SRT)------------------------");
Console.WriteLine("----------------------Evaluation(SRT)------------------------");
int avgwait = 0;
double avgdc = 0;
double avgzz = 0;
for (int i2=0;i2<queue.Count;i2++)
{
sim_process s = queue[i2];
avgzz += (s.endT - s.arriveT);
avgwait += s.waitT;
Console.WriteLine(queue2[i2].need_T);
Console.WriteLine("Task:" + s.taskname + " arrive at:" + s.arriveT.ToString() + " end at:" + s.endT.ToString() + " Wait Time:" + s.waitT.ToString() + " 周转时间:" + (s.endT - s.arriveT).ToString() + " 带权周转时间:" + ((s.endT - s.arriveT) / (double)queue2[i2].need_T).ToString());
avgdc += ((s.endT - s.arriveT) / (double)queue2[i2].need_T);
}
Console.WriteLine("Average Wait:" + (avgwait / queue.Count).ToString());
Console.WriteLine("平均周转:" + (avgzz / queue.Count).ToString());
Console.WriteLine("平均带权周转:" + (avgdc / queue.Count).ToString());
foreach (sim_process sr in exesx)
{
Console.Write(sr.taskname + "->");
}
Console.Write("\n\n");
cleanqueue();
}
}