今天陆秋老师检查我们的实验,我是我们这组第一个检查的,所以老师问到挺多源代码和每个算法具体实现的步骤和方法,我刚刚开始有点紧张,但是代码基本是自己写的,屏住压力,还是很好地解决了老师所提出的问题,操作系统的实习作用很大,在有限时间内,完成老师布置的任务,还有也提高了自己编程的能力和思维,收获很大。想了想,未来的道路很长,既然选择了这条道路就应该走下去。
下面附上实验三个设计的源代码:第一个是短作业和最高优先算法;第二个是磁盘调度,第三个是哲学家就餐设计算法
#include<stdio.h>
struct sjf {
int yxj;
char name[10]; //进程名
float arrivetime; //到达时间
float servicetime;//服务时间
float starttime; //开始时间
float finishtime;//完成时间
float zztime;//周转时间
float dqzztime;//带权周转
};
sjf p[100]; //定义一个全局指针
void Sinput(sjf *p, int N) //输入函数
{
int i;
for (i = 0; i<N; i++)
{
printf("输入第%d进程的名称,到达时间,服务时间:", i+1);
scanf("%s%f%f", &p[i].name, &p[i].arrivetime, &p[i].servicetime); //循环输入名字,到达时间,服务时间
}
}
void Ssinput(sjf *p, int N) //输入函数
{
int i;
for (i = 0; i<N; i++)
{
printf("输入第%d进程的名称,到达时间,服务时间:,优先级", i+1);
scanf("%s%f%f%d", &p[i].name, &p[i].arrivetime, &p[i].servicetime,&p[i].yxj); //循环输入名字,到达时间,服务时间
}
}
void Sprint(sjf *p, int N) //输出函数
{ int k;
printf("run order:");
printf("%s",p[0].name);
for(k=1;k<N;k++)
{
printf("-->%s",p[k].name); //输出的顺序
}
printf("\nname\tarrive\tservice\tstart\tfinish\tzztime\tdqzztime\n");
for(k=0;k<=N-1;k++)
{
printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k].name,p[k].arrivetime,
p[k].servicetime,p[k].starttime,p[k].finishtime,(p[k].finishtime-p[k].arrivetime),
((p[k].finishtime-p[k].arrivetime)/p[k].servicetime));
//周转时间等于结束时间减去到达时间,带权周转时间等于周转时间除服务时间
}
}
void Ssort(sjf *p, int N) //排序算法
{
for (int i = 1; i < N; i++) { //按冒泡算法排序
for (int j = 1; j <= i; j++)
{
if((p[i].arrivetime<=p[j].arrivetime)) //先排序到达时间,如果到达时间小于或等于下一个则看服务时间
{
if(p[i].servicetime<p[j].servicetime) //如果前一个的服务时间小于后一个则交换
{
sjf temp; //定义一个临时的指针方便交换
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
}
}
void Sssort(sjf *p, int N) //排序算法
{
int qq;
for (int i = 1; i < N; i++)
{ //按冒泡算法排序
for (int j = 1; j <= i; j++)
{
if((p[i].arrivetime<=p[j].arrivetime)) //先排序到达时间,如果到达时间小于或等于下一个则看服务时间
{
if(p[i].yxj<p[j].yxj) //如果前一个的服务时间小于后一个则交换
{
sjf temp; //定义一个临时的指针方便交换
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
}
qq=p[N].yxj;
}
void Sdeal(sjf *p,int N,float arrivetime,float servicetime,float finishtime) //处理运行函数
{
int k;
for(k=0;k<=N;k++)
{
if(k==0){
p[k].starttime=p[k].arrivetime;
p[k].finishtime=p[k].arrivetime+p[k].servicetime;} //将第一个数据写入
else{
if (p[k-1].finishtime<p[k].arrivetime) //如果结束时候下一个还没有到达
{
p[k].starttime=p[k].arrivetime; //则开始时间等于下一个到达时间
p[k].finishtime=p[k].starttime+p[k].servicetime;//结束时间等于开始时间加服务时间
}
else
{
p[k].starttime=p[k-1].finishtime; //开始时间等于结束时间
p[k].finishtime=p[k-1].finishtime+p[k].servicetime;//结束时间等于服务时间加结束时间
}
} //结束时间等于前一个的完成时间(这个的开始时间)加服务时间
}
}
void SJF(sjf *p, int N) //函数调用函数
{
float arrivetime=0,servicetime=0,finishtime=0; //初始化定义
Ssort(p, N);
Sdeal(p,N,arrivetime,servicetime,finishtime);
Sprint(p, N);
}
int main()
{
int M;
printf("短作业优先调度算法\n");
printf("输入进程数:");
scanf("%d", &M);
Sinput(p, M);
SJF(p, M);
}
最高级优先算法:
#include <stdio.h>//运行模板:a 5 2 b 2 2 c 1 1
#include <stdlib.h>
struct PCB{
char p_name[20];
int p_priority;//优先级别
int p_needTime;//需要的时间
int p_runTime;//运行的时间
char p_state;//状态是如何的,等待状态还是运行状态。
struct PCB* next;
};
void HighPriority();//高优先级
void Information();
char Choice();
struct PCB* SortList(PCB* HL);
int main()
{
Information();
char choice = Choice();
switch(choice)
{
case '1':
system("cls");
HighPriority();
break;
default:
break;
}
system("pause");
return 0;
}
void Information()
{
printf(" 按回车键进入演示程序");
getchar();
system("cls");
}
char Choice()
{
printf("\n\n");
printf(" 1.演示最高优先数优先算法。");
printf(" 按1继续:");
char ch = getchar();//回车
return ch;
system("cls");
}
void HighPriority()
{
struct PCB *processes, *pt;//p、processes、pt三个链表。
//pt作为临时节点来创建链表,使用for语句,限制进程数为3个
processes = pt = (struct PCB*)malloc(sizeof(struct PCB));//pt=processes
for (int i = 0; i != 3; ++i)
{
struct PCB *p = (struct PCB*)malloc(sizeof(struct PCB));
printf("进程号No.%d:\n", i);
printf("输入进程名:");
scanf("%s", p->p_name);
printf("输入进程优先数:");
scanf("%d", &p->p_priority);
printf("输入进程运行时间:");
scanf("%d", &p->p_needTime);
p->p_runTime = 0;//(*p).p_runtime,p指向结构体成员runtime
p->p_state = 'W';
p->next = NULL;
pt->next = p;
pt = p;//把p插到pt中去。
printf("\n\n");
}
getchar(); //接受回车
//processes作为头结点来存储链表(原句子)
processes = processes->next;//依次查看processes的值
int cases = 0;
struct PCB *psorted =processes;
while (1)
{
++cases;
pt = processes;
//对链表按照优先数排序
//psorted用来存放排序后的链表(存放进程的信息:时间)
psorted = SortList(psorted);//排序后的链表。(依靠优先数来排序的)
printf("The execute number: %d\n\n", cases);
printf("**** 当前正在运行的进程是:%s\n", psorted->p_name);
psorted->p_state = 'R';
printf("qname state super ndtime runtime\n");
printf("%s\t%c\t%d\t%d\t%d\t\n\n", psorted->p_name, psorted->p_state, psorted->p_priority, psorted->p_needTime, psorted->p_runTime);
psorted->p_state = 'W';
psorted->p_runTime++;//执行完一次后,runtime加一
psorted->p_priority--;//优先级减一
printf("**** 当前就绪状态的队列为:\n\n");
pt = psorted->next; //让pt指向已经排序的队列
while (pt != NULL)
{
printf("qname state super ndtime runtime\n");
printf("%s\t%c\t%d\t%d\t%d\t\n\n", pt->p_name, pt->p_state, pt->p_priority, pt->p_needTime, pt->p_runTime);
pt = pt->next;
}
//pt指向已经排序的链表,判断链表是否有已用时间等于需要时间的
pt = psorted;
struct PCB *ap;
ap = NULL; //ap指向pt的前一个节点
while (pt != NULL)
{
if (pt->p_needTime==pt->p_runTime)//条件是当前进程需要运行的时间等于他所运行的时间
{
if (ap==NULL)
{
pt = psorted->next;//把第二个进程的地址给pt(下一步ndtime和runtime不等,跳出if语句)
psorted = pt;
}
else
ap->next=pt->next;
}
ap=pt;
pt=pt->next;//依次执行剩下的进程,(当进程的ndtime和runtime相同时又跳进if语句)
}
if (psorted->next==NULL)
break;
getchar();
}
}
struct PCB* SortList(PCB* HL)//将进程的优先级排序
{
struct PCB* SL;
SL = (struct PCB*)malloc(sizeof(struct PCB));
SL = NULL;
struct PCB* r = HL;
while (r != NULL)
{
struct PCB* t = r->next;
struct PCB* cp = SL;//cp是头结点
struct PCB* ap = NULL;
while (cp != NULL)
{
if (r->p_priority > cp->p_priority)
break;
else
{
ap = cp;//把第一个进程的地址给ap1068
cp = cp->next;//cp的地址为空(为了每次对比完优先级之后,退出循环)
}
}
if (ap == NULL)
{
r->next = SL;
SL = r;
}
else
{
r->next = cp;
ap->next = r;
}
r = t;//比较下一个进程和第一个进程的过渡
}//如果r等于null,返回SL
return SL;
}
磁盘调度算法:
#include<iostream>
#include<ctime>
using namespace std;
void SSTF(int a[],int n);
void CSCAN(int a[],int n);
int main()
{
int n; //磁道的个数
int s; //功能号
cout<<"请输入当前磁道的个数,按Enter键显示生成的随机磁道号:"<<endl;
cin>>n;
int *a=new int[n];//申请一个整型变量空间,赋初值为n,并定义一个整型指针a指向该地址空间
cout<<"生成的随机磁道号为:";
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
a[i]=(rand()%100)+1;
cout<<a[i]<<" ";
}
cout<<endl;
while(1)
{
cout<<endl;
cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;
cout<<" ┃ 磁盘调度算法功能列表 ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 1、最短寻道时间算法(SSTF) ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 2、循环扫描算法(CSCAN) ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 0、退出 ┃"<<endl;
cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;
cout<<endl;
cout<<"请选择所需功能的前置编号:";
cin>>s;
if(s>3)
{
cout<<"数据输入有误!请重新输入:"<<endl;
}
else
{
switch(s){
case 0: exit(0);break ;
case 1:SSTF(a, n);break;
case 2:CSCAN(a,n);break;}
}
}
return 0;
}
//最短寻道时间算法(SSTF)
void SSTF(int a[],int n)
{
int temp;
int k=1;
int now,l,r;
int i,j;
double sum=0;
//将磁道号按递增排序
for(i=0;i<n;i++)
for(j=i+1;j<n;j++){
if(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
cout<<"按递增顺序排好的磁道显示为:"<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";//输出排好的磁道顺序
}
cout<<endl;
cout<<"请输入当前的磁道号:";
cin>>now;//确定当前磁头所在位置
cout<<"磁盘调度顺序为:"<<endl;
if(a[n-1]<=now){//当前磁头位置大于最外围欲访问磁道(比如21,90,当前的磁道为91,顺序为91,1)
for(i=n-1;i>=0;i--)
cout<<a[i]<<" ";
sum=now-a[0];
}
else
if(a[0]>=now)//当前磁头位置小于最里欲访问磁道(比如21,90,当前的磁道为91,顺序为21,91)
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=a[n-1]-now;
}
else//不大也不小,在范围之内
{
while(a[k]<now)//确定当前磁道在已排的序列中的位置
{
k++;
}
l=k-1;//在磁头位置的前一个欲访问磁道
r=k;//磁头欲访问磁道
while((l>=0)&&(r<n))
{
if((now-a[l])<=(a[r]-now))//选择离磁头近的磁道
{
cout<<a[l]<<" ";//(比如37,44,49,64,84,93,当前的磁道为65,则调度后的循序为:64(为a[l]),49,44,37,84 93)
sum+=now-a[l];
now=a[l];
l=l-1;
}
else
{
cout<<a[r]<<" ";//(比如22 26 62 67 88 而当前的磁道为87,则磁盘调度的顺序为88 67 62 23 22 )
sum+=a[r]-now;
now=a[r];
r=r+1;
}
}
if(l=-1)//磁头位置里侧的磁道已访问完,这是针对(now-a[l]<a[r]-now的情况)
{
for(j=r;j<n;j++)//访问磁头位置外侧的磁道
{
cout<<a[j]<<" ";
}
sum+=a[n-1]-a[0];
}
if(r==n)//磁头位置外侧的磁道已访问完,这是针对(else的情况)
{
for(j=k-1;j>-1;j--) //访问磁头位置里侧的磁道
{
cout<<a[j]<<" ";
}
sum+=a[n-1]-a[0];
}
}
cout<<endl;
cout<<"移动的总道数为:"<<sum<<endl;
cout<<"移动的平均道数为:"<<(sum/n)<<endl;
}
//循环扫描算法(CSCAN)
void CSCAN(int a[],int n)
{
int temp;
int now,l,r;
int i,j;
double sum=0;
int k=1;
for(i=0;i<n;i++)//对访问磁道按由小到大顺序排列输出
for(j=i+1;j<n;j++){
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
cout<<"按递增顺序排好的磁道为:"<<endl;
for( i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"请输入当前的磁道号:";
cin>>now;//确定当前磁道号
if(a[n-1]<=now)//磁头位置大于最外围欲访问磁道
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=now-2*a[0]+a[n-1];
}
else
if(a[0]>=now)//磁头位置小于最里欲访问磁道
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=a[n-1]-now;
}
else //磁头位置在最里侧磁道与最外侧磁道之间
{ int d;
while(a[k]<now)
{
k++;
}
l=k-1;//在磁头位置的前一个欲访问磁道
r=k; //磁头欲访问磁道
cout<<"请输入当前磁头移动的方向 (0 表示向内 ,1表示向外) : ";
cin>>d; //确定磁头访问的方向
cout<<"磁盘调度顺序为:";
if(d==0||d==1)
{
if(d==1) //磁头向外侧访问
{
for(j=r;j<n;j++)//先访问外侧磁道再转向最里欲访问磁道
{
cout<<a[j]<<" ";
}
for(j=0;j<r;j++)
{
cout<<a[j]<<" ";
}
sum=2*a[n-1]-now-2*a[0]+a[l];
}
if(d==0) //磁头向内侧访问
{
for(j=r-1;j>=0;j--)
{
cout<<a[j]<<" ";
}
for(j=n-1;j>=r;j--)
{
cout<<a[j]<<" ";
}
sum=2*a[n-1]-2*a[0]+now-a[r];
}
}
else
cout<<"请输入0或1!";
}
cout<<endl;
cout<<"移动的总道数为:"<<sum<<endl;
cout<<"移动的平均道数为:"<<(sum/n)<<endl;
}
哲学家就餐设计算法:
#include <windows.h>
#include <time.h>
#include <string>
#include <iostream>
#include <assert.h>
using namespace std; //控制活动线程数目的信号量(保护线程共享资源)
bool tools[6]; //全局变量,用餐工具
CRITICAL_SECTION cs; //信号量, 在线程中使用,临界区
class Philosopher
{
private:
int number;
int status; /*标记当前哲学家的状态,0表示正在等待(即处于饥饿状态),1表示得到两支筷子正在吃饭,2表示正在思考*/
public:
Philosopher(int num=0): status(2), number(num) { }
int find() const { return number; }
int getinfo() const { return status; }
void Change() ; //状态改变函数
};
void Philosopher::Change()
{
EnterCriticalSection (&cs) ; //进入临界区
if(status==1) //正在进餐
{
tools[number%6]=true; //放下左手工具
tools[(number-1)%6]=true; //放下右手工具
status=2; //改变状态为思考
}
else if(status==2) //思考中
{
status=0; //改变状态为等待
}
else if(status==0) //等待中
{
if(tools[number%6]&&tools[(number-1)%6]) //左右手两边工具均为空闲状态
{
tools[number%6]=false; //拿起左手工具
tools[(number-1)%6]=false; //拿起右手工具
status=1;
}
}
LeaveCriticalSection (&cs) ;
}
string print(Philosopher *pA)
{
//pA->Change();
int i=pA->getinfo();
string str;
if(i==0)
str="等待";
else if(i==1)
str="就餐";
else str="思考";
return str;
}
string toolstatus(bool a)
{
string state;
if(a==true)
state="闲";
if(a==false)
state="用";
return state;
}
int main()
{
char con = 'y'; //判断是否继续
for(int i=0;i<6;i++)
tools[i]=true; //3组刀叉都未使用,初始化
Philosopher P1(1),P2(2),P3(3),P4(4),P5(5),P6(6);
InitializeCriticalSection (&cs) ; //初始化初始化临界区
cout<<"-----------------------状态说明示意图:-----------------------"<<endl;
cout<<"刀3号 哲学家号1的状态 叉1号 哲学家号2的状态 刀1号\n"<<endl;
cout<<"哲学家号6的状态"<<" "<<"哲学家号3的状态\n"<<endl;
cout<<"叉3号 哲学家号5的状态 刀2号 哲学家号4的状态 叉2号"<<endl;
cout<<"餐具的状态,“用”表示使用中,“闲”表示空闲中。"<<endl;
cout<<"--------------------------"<<endl;
cout<<"哲学家们开始生活:"<<endl;
cout<<endl;
cout<<endl;
while(con=='y')
{
P1.Change();
P2.Change();
P3.Change();
P4.Change();
P5.Change();
P6.Change();
cout<<"当前状态为:"<<endl;
cout<<toolstatus(tools[5])<<" "<<print(&P5)<<" "<<toolstatus(tools[4])<<" "<<print(&P2)<<" "<<toolstatus(tools[1])<<endl;
cout<<print(&P6)<<" "<<print(&P3)<<endl;
cout<<toolstatus(tools[0])<<" "<<print(&P1)<<" "<<toolstatus(tools[3])<<" "<<print(&P4)<<" "<<toolstatus(tools[2])<<endl;
cout<<"--------------------------"<<endl;
cout<<"若要继续下一状态,输入y;输入其他,结束程序:";
cin>>con;
Sleep(20);
}
DeleteCriticalSection (&cs) ; //退出资源区
return 0;
}
嗯,就差不多这样了...