模拟计算机中进程调度
【实验目的】
在多道程序或者任务系统中，系统同时处于就绪状态的进程有若干个。也就是说能运行的进程数远远大于处理机个数，为了使系统中的各进程能有条不紊的运行，必须选择某种调度策略，以选择一进程占用处理机。这样便要求我们来设计模拟进程调度的算法，来模拟实现计算机中的进程安排。此次实验模拟三种，先来先服务，优先级调度，时间片轮转。
【实验原理】
[if !supportLists]1. [endif]首先是操作系统中
<1>.先来先服务调度，就是哪一个进程先到达的，它的优先级就是最高，优点是实现简单，只需要根据arrivetime实现一个排序就行，缺点也是多多，不赘述了；按照优先级调度的算法，这个算法里面，我们给进程安排了一个重要程度yxj，按照这个排好队，然后每执行一次优先级就下降，这个实现就比较困难了，体现在新的进程到来的插入，以及后面判断就绪；时间片轮转是一种比较好的算法，每个进程都可以排队使用处理机，一开始的就绪队列就是按照先来先服务排序的。
2.在实现中，用到了c语言中的指针数组知识，数据结构中链表的知识，尤其是链表的操作（插入，改变顺序等等）。体现了学科间的紧密结合与相互服务吧
【小结或讨论】
这次的实验感觉很有难度，实验指导书上要求的数据结构设计的链表指针已经是大一知识了，这也是自己很少锻炼的原因。尤其是数据结构，本身难度就很大，需要再好好的看一遍，弄清楚排序，插入，指向等诸多问题。不过操作系统中的概念得到了理解记忆，尤其是第二个优先级调度和第三个时间片，在处理进程后，优先级如何变化？这个进程要被插入到哪里？这个时间片用完进程这么安排很多问题。
看书，看数据结构以及操作系统课本，想清楚进程的去向等基本问题，多练习。
代码：
轮转调度：
#define N 20
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
struct pcb
{
char pname[N];//进程名
int runtime;//估计运行时间
int arrivetime;//到达时间
char state;//进程状态
struct pcb *next;//后继指针
struct pcb *prev;//前驱指针
};
int num=5;
pcb *p;
pcb *n;
pcb *time;
pcb *head;
pcb *tail;
pcb *head1;
int sum;
int i,j;
char R='r',C='c';
int current=0;
int inputprocess();//建立进程函数
//int readyprocess();//建立就绪队列函数
int readydata();//判断进程是否就绪函数
//int runprocess();//运行进程函数
int inputprocess(){ //按到达时间插入
for(i=0;i<num;i++){
pcb *p1=new pcb;
printf("输入进程的信息：\n");
printf("第%d个进程的名字:",i+1);
scanf("%s",p1->pname);
printf("第%d个进程的运行时间:",i+1);
scanf("%d",&(p1->runtime));
printf("第%d个进程的到达时间:",i+1);
scanf("%d",&(p1->arrivetime));
p1->state=R;
if(i==0){
p=p1;
p->next=NULL;
head=p;
}
else{
p=head;
while((p!=NULL)&&(p->arrivetime<p1->arrivetime))
p=p->next;
if(p==NULL){
p=head;
while(p->next!=NULL)
p=p->next;
p->next=p1;
p1->prev=p;
p1->next=NULL;
}
else{
if(p==head){
head=p1;
p1->next=p;
p->prev=p1;
}
else{
p1->prev=p->prev;
p->prev->next=p1;
p1->next=p;
p1=p->prev;
}
}
}
}
p=head;
while(p->next!=NULL)
p=p->next;
tail=p;
return 1;
}
void fuz(pcb *p1,pcb *p2){ //将p2中的值付给p1
p1->arrivetime=p2->arrivetime;
strcpy(p1->pname,p2->pname);
p1->runtime=p2->runtime;
p1->state=p2->state;
}
int readydata(){
for(p=head;p!=NULL;p=p->next)
{
if(p==head)
sum=p->arrivetime+p->runtime;
else{
if(sum<p->arrivetime)
sum=p->arrivetime+p->runtime;
else
sum=sum+p->runtime;
}
}
current=head->arrivetime;
p=head;
while(current<=sum){
printf("当前时间为:%d\n",current);
while((p!=NULL)&&(current==p->arrivetime)){
pcb *m=new pcb;
fuz(m,p);
if(p==head){
head1=m;
time=m;
time->next=NULL;
}
else{
for(time=head1;time->next!=NULL;time=time->next);
time->next=m;
m->prev=time;
m->next=NULL;
}
p=p->next;
}
head1->runtime--;
if(head1->next==NULL)
n=head1;
else
n=head1->next;
if(head1->runtime==0){
printf("进程%s已结束.\n",head1->pname);
head1->next->prev=NULL;
head1->next=NULL;
}
else{
for(time=head1;time->next!=NULL;time=time->next);
if(time!=head1){
time->next=head1;
head1->prev=time;
head1->next->prev=NULL;
head1->next=NULL;
}
}
head1=n;
printf("就绪队列中的进程为:");
for(time=head1;time!=NULL;time=time->next)
printf("%s",time->pname);
printf("\n");
current++;
}
return 1;
}
int main(){
inputprocess();
printf("进程名 到达时间 运行时间\n");
for(p=head;p!=NULL;p=p->next)
printf("%s %d %d\n",p->pname,p->arrivetime,p->runtime);
readydata();
return 1;
}
FCFS：
//FCFS，先来先服务
#include <iostream>
#include "string"
#include "algorithm"
using namespace std;
//进程类
class process{
public:
string name;//进程名
double arrive; //进程到达时刻
double service;//进程服务时间
void print(){
cout<<name<<"\t\t";
cout<<arrive<<"\t\t";
cout<<service<<"\t\t";
}
};
//比较两个进程到达时间的先后
bool compare(process a,process b){
return a.arrive<b.arrive;
}
int main(int argc, const char * argv[]) {
int n; //进程个数
process pro[10]; //进程数组
cout<<"请输入c进程个数: ";
cin>>n;
cout<<"请分别输入这些进程的:\n进程名\t到达时刻\t服务时间\n";
for(int i=0;i<n;i++){
cin>>pro[i].name;
cin>>pro[i].arrive;
cin>>pro[i].service;
}
//"algorithm"文件里的sort函数
sort(pro,pro+n,compare); //s进程数组按到达时间从小到大排序
cout<<"进程名\t到达时刻\t服务时间\t开始执行时刻\t完成时刻\t周转时间\t带权周转时间\n";
double begin=pro[0].arrive; //初始到达时间
for(int i=0;i<n;i++){
double end=begin+pro[i].service; //完成时刻
double zz=end-pro[i].arrive; //周转时间
double dqzz=zz/pro[i].service;
pro[i].print();
cout<<begin<<"\t\t\t";
cout<<end<<"\t\t";
cout<<zz<<"\t\t";
cout<<dqzz<<"\n";
begin=end>pro[i+1].arrive?end:pro[i+1].arrive;
}
cin>>n;
return 0;
}
SJF
//SJF
#include <iostream>
#include "string"
#include "algorithm"
using namespace std;
//进程类
class process{
public:
string name; //进程名
double arrive; //进程到达时刻
double service; //进程服务时间
void print(){
cout<<name<<"\t\t";
cout<<arrive<<"\t\t";
cout<<service<<"\t\t";
}
};
//比较两个进程到达时间的先后
bool compare(process a,process b){
return a.arrive<b.arrive;
}
//比较两个进程服务时间
bool compare2(process a,process b){
return a.service<b.service;
}
int main(int argc, const char * argv[]) {
int n; //进程个数
process pro[10]; //进程数组
cout<<"请输入c进程个数: ";
cin>>n;
cout<<"请分别输入这些进程的:\n进程名\t到达时刻\t服务时间\n";
for(int i=0;i<n;i++){
cin>>pro[i].name;
cin>>pro[i].arrive;
cin>>pro[i].service;
}
//"algorithm"文件里的sort函数
sort(pro,pro+n,compare); //s进程数组按到达时间从小到大排序
cout<<"进程名\t到达时刻\t服务时间\t开始执行时刻\t完成时刻\t周转时间\t带权周转时间\n";
double begin=pro[0].arrive; //初始到达时间
for(int i=0;i<n;i++){
double end=begin+pro[i].service;//完成时刻
double zz=end-pro[i].arrive; //周转时间
double dqzz=zz/pro[i].service; //带权周转时间
pro[i].print();
cout<<begin<<"\t\t\t";
cout<<end<<"\t\t";
cout<<zz<<"\t\t";
cout<<dqzz<<"\n";
int nn=0;
for(int j=1;j<n-i;j++){
if(end>=pro[i+j].arrive)
nn++;
}
if(nn>1)
sort(pro+i+1,pro+i+1+nn,compare2);
begin=end>pro[i+1].arrive?end:pro[i+1].arrive;
}
cin>>n;
return 0;
}
优先级调度算法
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct pcb
{
char pname[5];//进程名
int yxs;//优先数
int runtime;//估计运行时间
char state;//进程状态
struct pcb *next;//后继指针
struct pcb *prev;//前驱指针
};
//int num=5;//进程的个数
pcb *p; //定位到当前处理位置的指针
pcb *head; //头指针指向头节点
int sum=0;
int i,j,m;
char R='r',C='c';//进程的状态
//unsigned long current=0;
int inputprocess();//建立进程函数
int readydata();
int inputprocess(){
for(i=0;i<5;i++){
pcb *p1=new pcb;
printf("输入进程的信息：\n");
printf("第%d个进程的名字:",i+1);
scanf("%s",p1->pname);
printf("第%d个进程的运行时间:",i+1);
scanf("%d",&(p1->runtime));
printf("第%d个进程的优先数:",i+1);
scanf("%d",&(p1->yxs));
p1->state=R;
if(i==0)
{ //如果是插入第一个，直接插入即可
p=p1;
p->next=NULL;
head=p;
}
else{//如果不是第一个，那么需要按照优先数从小到大进行排序插入
p=head;
while((p!=NULL)&&(p->yxs<p1->yxs))
p=p->next;
if(p==NULL){ //p==NULL
p=head;//链表中优先级都比现在要插入的高
while(p->next!=NULL)
p=p->next;
p->next=p1;
p1->prev=p;
p1->next=NULL; //将p1插入到链表的尾端
}
else{//直接插入
if(p==head){ //p==head说明插入的位置为链表的表头，p1给head
head=p1;
p1->next=p;
p->prev=p1;
}
else{ //直接插入，p!=head情况，把p1插入到p前面
p1->prev=p->prev;
p->prev->next=p1;
p1->next=p;
p1=p->prev;
}
}
}
}
return 1;
}
int readydata(){//进程里面是不是有就绪函数
pcb *p1;//当前位置
for(p=head;p!=NULL;p=p->next)
sum+=p->runtime;//进程队列中所有进程运行时间总计
for(i=0;i<sum;i++){
p1=head;
printf("第%d次:\n",i+1);
for(p=head;p!=NULL;p=p->next)
if(p->yxs<p1->yxs)
p1=p;//找出链表中优先数最小的进程，运行该进程
p1->runtime--;//当前运行的进程运行时间减一
p1->yxs++;//当前运行的进程的优先数加一
if(p1->runtime==0){//如果运行时间减为0，则当前进程结束
printf("进程%s已结束.\n",p1->pname);
if(p1==head){
head=p1->next;
p1->next->prev=NULL;
p1->next=NULL;
}
else{
pcb *p2;
p2=p1;
p1->prev->next=p1->next;
p1->next->prev=p1->prev;
p1->next=NULL;
p1->prev=NULL;
}
}
else{
printf("当前进程:%s\n",p1->pname);
}
printf("队列中进程:");
for(p=head;p!=NULL;p=p->next)
if(p!=p1)
printf("%s ",p->pname);
printf("\n");
}
}
int main(){
inputprocess();
printf("输入的进程为:\n");
for(p=head;p!=NULL;p=p->next)
printf("%s %d %d\n",p->pname,p->yxs,p->runtime);
readydata();//判断进程
return 1;
}
sort排序函数
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
//在c++库中引用了一个文件<algorithm>,里面定义的sort函数就是用来给给定区间排序的。
//这个小例子实践这里面最终是从小到大输出。
int main()
{
int a[10]={9,12,17,30,50,20,60,65,4,49};
sort(a,a+10);
for(int i=0;i<10;i++)
cout<<a[i]<<' ';
cout<<endl;
return 0;
}
