本博客转载自http://blog.csdn.net/houchaoqun_xmu/article/details/55539362请尊重版权完整
操作系统系列
学习至此，发现很多学了但很久没用的知识，久而久之，慢慢遗忘。等哪天还需要的话，却发现已经忘得差不多了，即使整理了文档（word等），还是得从头再学一遍。读研第一学期，发现很多东西都可以从博客上学习到，也有不少博主呕心沥血整理了挺多有用的博文。于是，本人借此契机，也慢慢开始整理一些博文，不断改进完善中。整理博文（IT）有如下目的：
首要目的：记录“求学生涯”的所学所悟，不断修改，不断更新！（有读者的互动）其次目的：
在这“开源”的时代，整理并分享所学所悟是一种互利的行为！
博文系列：操作系统课程的相关实验
1.先来先服务FCFS和短作业优先SJF进程调度算法 2.时间片轮转RR进程调度算法 3.预防进程死锁的银行家算法 4.动态分区分配算法 5.虚拟内存页面置换算法 6.磁盘调度算法
6个实验相关的代码下载地址：http://download.csdn.net/detail/houchaoqun_xmu/9865648
-------------------------------
先来先服务FCFS和短作业优先SJF进程调度算法
一、概念介绍和案例解析
FCFS调度算法
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
案例剖析：
FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。
从表上可以看出，其中短作业C的带权周转时间竞高达100，这是不能容忍的；而长作业D的带权周转时间仅为1.99。据此可知，FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。
CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙型作业。
I/O繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属于I/O繁忙型作业。
案例剖析2：采用FCFS调度算法时的调度性能
上图表示出有五个进程A、B、C、D、E，它们到达的时间分别是0、1、2、3和4，所要求的服务时间分别是4、3、5、2和4，其完成时间分别是4、7、12、14和18。从每个进程的完成时间中减去其到达时间，即得到其周转时间，进而可以算出每个进程的带权周转时间。
SJF调度算法：
短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
为了和FCFS调度算法进行比较，我们仍利用FCFS算法中所使用的实例，并改用SJ(P)F算法重新调度，再进行性能分析。由上图中的(a)和(b)可以看出，采用SJ(P)F算法后，不论是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业D，其周转时间由原来的(用FCFS算法时)11降为3；而平均带权周转时间是从5.5降到1.5。这说明SJF调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。
SJ(P)F调度算法也存在不容忽视的缺点：
该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
二、实验介绍
问题描述：
设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个进程分别在T1,… ,Tn时刻到达系统，它们需要的服务时间分别为S1,… ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
程序要求：
---- 进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；选择算法1-FCFS，2-SJF。
---- 要求采用先来先服务FCFS和短作业优先SJF分别调度进程运行，计算每个进程的周转时间和带权周转时间，并且计算所有进程的平均周转时间和带权平均周转时间。
---- 输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等。
---- 输出：要求输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。
三、程序设计和开发
程序设计：
Initial()进行初始化。input()对到达时间和服务时间进行输入。get_firstProcess()获得第一个进程，FCFS和SJF算法的实现相同。FCFS()对算法进行处理。SJF()对算法进行处理。choose_Algorithm();对实现算法的类别进行选择：具有容错性特征。
FCFS：
[cpp]
view plain
copy
void FCFS() { int startWorkTime = 0; int first = get_firstProcess(); isFinished_FCFS[first] = true; FinishTime[first] = ArrivalTime[first] + ServiceTime[first]; startWorkTime += ServiceTime[first]; WholeTime[first] = FinishTime[first] - ArrivalTime[first]; WeightWholeTime[first] = WholeTime[first]/ServiceTime[first]; int nextProcess = n; for (int i=1;i<n;i++) { nextProcess = n; for (int j=0;j<n;j++) { if (!isFinished_FCFS[j]) { if (ArrivalTime[j]<=startWorkTime) { if (nextProcess==n) { nextProcess = j; } else { if (ArrivalTime[nextProcess]>ArrivalTime[j]) { nextProcess=j; } } } } } isFinished_FCFS[nextProcess] = true; FinishTime[nextProcess] = ServiceTime[nextProcess] + startWorkTime; startWorkTime += ServiceTime[nextProcess]; WholeTime[nextProcess] = FinishTime[nextProcess] - ArrivalTime[nextProcess]; WeightWholeTime[nextProcess] = (double)WholeTime[nextProcess]/ServiceTime[nextProcess]; } double totalWT = 0; double totalWWT = 0; for (int i=0;i<n;i++) { totalWT+=WholeTime[i]; totalWWT+=WeightWholeTime[i]; } AverageWT_FCFS = totalWT/n; AverageWWT_FCFS = totalWWT/n; display(); cout<<"平均周转时间="<<AverageWT_FCFS<<endl; cout<<"平均带权周转时间="<<AverageWWT_FCFS<<endl; cout<<"******************************************************"<<endl; }
SJF：
[cpp]
view plain
copy
void SJF() { int startWorkTime_SJF = 0; int first = get_firstProcess(); isFinished_SJF[first] = true; FinishTime[first] = ArrivalTime[first] + ServiceTime[first]; startWorkTime_SJF += ServiceTime[first]; WholeTime[first] = FinishTime[first] - ArrivalTime[first]; WeightWholeTime[first] = (double)WholeTime[first]/ServiceTime[first]; int nextProcess_SJF = n; for (int i=1;i<n;i++) { nextProcess_SJF = n; for (int j=0;j<n;j++) { if (!isFinished_SJF[j]) { if (ArrivalTime[j]<=startWorkTime_SJF) { if (nextProcess_SJF==n) { nextProcess_SJF = j; } else { if (ServiceTime[nextProcess_SJF]>ServiceTime[j]) { nextProcess_SJF = j; } } } } } isFinished_SJF[nextProcess_SJF] = true; FinishTime[nextProcess_SJF] = ServiceTime[nextProcess_SJF] + startWorkTime_SJF; startWorkTime_SJF += ServiceTime[nextProcess_SJF]; WholeTime[nextProcess_SJF] = FinishTime[nextProcess_SJF] - ArrivalTime[nextProcess_SJF]; WeightWholeTime[nextProcess_SJF] = (double)WholeTime[nextProcess_SJF]/ServiceTime[nextProcess_SJF]; } double totalWT = 0; double totalWWT = 0; for (int i=0;i<n;i++) { totalWT+=WholeTime[i]; totalWWT+=WeightWholeTime[i]; } AverageWT_SJF = totalWT/n; AverageWWT_SJF = totalWWT/n; display(); cout<<"平均周转时间="<<AverageWT_SJF<<endl; cout<<"平均带权周转时间="<<AverageWWT_SJF<<endl; cout<<"******************************************************"<<endl; }
四、实验结果分析
-- 输入数据：
-- 进程数n = 5
-- 到达时间：0 1 2 3 4
-- 服务时间：4 3 5 2 4
FCFS算法：
SJF算法：
五、实验源码
[cpp]
view plain
copy
#include <iostream> #include <iomanip> using namespace std; #define MaxNum 100 int ArrivalTime[MaxNum]; int ServiceTime[MaxNum]; int FinishTime[MaxNum]; int WholeTime[MaxNum]; double WeightWholeTime[MaxNum]; double AverageWT_FCFS,AverageWT_SJF; double AverageWWT_FCFS,AverageWWT_SJF; bool isFinished_FCFS[MaxNum]; bool isFinished_SJF[MaxNum]; static int n; void Initial() { cout<<"请输入作业（进程）个数n="; cin>>n; for (int i=0;i<n;i++) { ArrivalTime[i] = 0; ServiceTime[i] = 0; FinishTime[i] = 0; WholeTime[i] = 0; WeightWholeTime[i] = 0; AverageWT_FCFS = 0; AverageWT_SJF = 0; AverageWWT_FCFS = 0; AverageWWT_SJF = 0; isFinished_FCFS[i] = false; isFinished_SJF[i] = false; } } void input() { cout<<"请分别输入每个进程的到达时间："<<endl; for (int i=0;i<n;i++) { cin>>ArrivalTime[i]; } cout<<"请分别输入每个进程的服务时间："<<endl; for (int i=0;i<n;i++) { cin>>ServiceTime[i]; } cout<<"******************************************************"<<endl; cout<<"用户输入的进程个数n="<<n<<endl; cout<<"用户输入的服务时间分别为："<<endl; for (int i=0;i<n;i++) { cout<<ArrivalTime[i]<<" "; } cout<<endl; cout<<"用户输入的服务时间分别为："<<endl; for (int i=0;i<n;i++) { cout<<ServiceTime[i]<<" "; } cout<<endl<<"******************************************************"<<endl; } int get_firstProcess() { int first = MaxNum; for (int i=0;i<n;i++) { if (ArrivalTime[i]<=ArrivalTime[first]) { first = i; } } return first; } void display() { cout<<"******************************************************"<<endl; cout<<"进程相关信息如下："<<endl; cout<<setw(10)<<"进程名（ID）"<<" "; cout<<setw(10)<<"到达时间"<<" "; cout<<setw(10)<<"服务时间"<<" "; cout<<setw(10)<<"完成时间"<<" "; cout<<setw(10)<<"周转时间"<<" "; cout<<setw(10)<<"带权周转时间"<<endl; for (int i = 0;i<n;i++) { cout<<setw(10)<<i+1<<" "; cout<<setw(10)<<ArrivalTime[i]<<" "; cout<<setw(10)<<ServiceTime[i]<<" "; cout<<setw(10)<<FinishTime[i]<<" "; cout<<setw(10)<<WholeTime[i]<<" "; cout<<setw(10)<<WeightWholeTime[i]<<" "<<endl; } } void FCFS() { int startWorkTime = 0; int first = get_firstProcess(); isFinished_FCFS[first] = true; FinishTime[first] = ArrivalTime[first] + ServiceTime[first]; startWorkTime += ServiceTime[first]; WholeTime[first] = FinishTime[first] - ArrivalTime[first]; WeightWholeTime[first] = WholeTime[first]/ServiceTime[first]; int nextProcess = n; for (int i=1;i<n;i++) { nextProcess = n; for (int j=0;j<n;j++) { if (!isFinished_FCFS[j]) { if (ArrivalTime[j]<=startWorkTime) { if (nextProcess==n) { nextProcess = j; } else { if (ArrivalTime[nextProcess]>ArrivalTime[j]) { nextProcess=j; } } } } } isFinished_FCFS[nextProcess] = true; FinishTime[nextProcess] = ServiceTime[nextProcess] + startWorkTime; startWorkTime += ServiceTime[nextProcess]; WholeTime[nextProcess] = FinishTime[nextProcess] - ArrivalTime[nextProcess]; WeightWholeTime[nextProcess] = (double)WholeTime[nextProcess]/ServiceTime[nextProcess]; } double totalWT = 0; double totalWWT = 0; for (int i=0;i<n;i++) { totalWT+=WholeTime[i]; totalWWT+=WeightWholeTime[i]; } AverageWT_FCFS = totalWT/n; AverageWWT_FCFS = totalWWT/n; display(); cout<<"平均周转时间="<<AverageWT_FCFS<<endl; cout<<"平均带权周转时间="<<AverageWWT_FCFS<<endl; cout<<"******************************************************"<<endl; } void SJF() { int startWorkTime_SJF = 0; int first = get_firstProcess(); isFinished_SJF[first] = true; FinishTime[first] = ArrivalTime[first] + ServiceTime[first]; startWorkTime_SJF += ServiceTime[first]; WholeTime[first] = FinishTime[first] - ArrivalTime[first]; WeightWholeTime[first] = (double)WholeTime[first]/ServiceTime[first]; int nextProcess_SJF = n; for (int i=1;i<n;i++) { nextProcess_SJF = n; for (int j=0;j<n;j++) { if (!isFinished_SJF[j]) { if (ArrivalTime[j]<=startWorkTime_SJF) { if (nextProcess_SJF==n) { nextProcess_SJF = j; } else { if (ServiceTime[nextProcess_SJF]>ServiceTime[j]) { nextProcess_SJF = j; } } } } } isFinished_SJF[nextProcess_SJF] = true; FinishTime[nextProcess_SJF] = ServiceTime[nextProcess_SJF] + startWorkTime_SJF; startWorkTime_SJF += ServiceTime[nextProcess_SJF]; WholeTime[nextProcess_SJF] = FinishTime[nextProcess_SJF] - ArrivalTime[nextProcess_SJF]; WeightWholeTime[nextProcess_SJF] = (double)WholeTime[nextProcess_SJF]/ServiceTime[nextProcess_SJF]; } double totalWT = 0; double totalWWT = 0; for (int i=0;i<n;i++) { totalWT+=WholeTime[i]; totalWWT+=WeightWholeTime[i]; } AverageWT_SJF = totalWT/n; AverageWWT_SJF = totalWWT/n; display(); cout<<"平均周转时间="<<AverageWT_SJF<<endl; cout<<"平均带权周转时间="<<AverageWWT_SJF<<endl; cout<<"******************************************************"<<endl; } void choose_Algorithm() { cout<<"请选择算法“1-FCFS，2-SJF”"<<endl; int choose; cin>>choose; if (choose==1) { FCFS(); } else if(choose==2) { SJF(); } else { cout<<"请输入正确的选择“1-FCFS，2-SJF”"<<endl; cout<<"******************************************************"<<endl; choose_Algorithm(); } } int main() { Initial(); input(); choose_Algorithm(); system("pause"); return 0; }
