实验三 进程调度
一．实验目的
加深理解并模拟实现进程（作业）调度算法。
1）熟悉常用的进程调度算法，如FCFS、SPF、FPF、高响应比优先、时间片轮转；
2）结合所学的数据结构及编程知识，选择三种进程调度算法予以实现。
二．实验属性
该实验为设计性实验。
三．实验仪器设备及器材
普通PC386以上微机
四．实验要求
本实验要求2学时完成。
本实验要求完成如下任务：
1） 编程实现单处理机系统中的进程调度，要求从FCFS、SPF、FPF、高响应比优先、时间片轮转算法中至少选择三个；
2） 最后编写主函数对所做工作进行测试。
实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。
五：实验具体设计
此程序模拟了两种调度算法，FCFS和SPF，首先FCFS就是按照进程的创建顺序依次顺序进行，流程图为：
进程顺序执行
SPF:
每次都进行循环，选出在该时间刻运行时间最短的进程优先执行。
程序代码具体详解：
1. 创建一结构体作为进程控制器
typedef struct PCB
{
int ID;
char state;
int arrivetime;
int starttime;
int finishtime;
int servicetime;
struct PCB *next;
}pcb;
定义全局变量作为计时器
int time;//计时器
2. 创建进程链表：
从txt文件中读取数据，构造一条不含头结点的单链表
void Create_process()
{
ifstream inFile;
inFile.open("test.txt");
inFile>>n;
inFile.get();
int i=0;
for (;i<n;i++)
{
p=(pcb *)malloc(sizeof(pcb));
inFile>>p->ID;
inFile>>p->arrivetime;
inFile>>p->servicetime;
p->starttime=0;
p->finishtime=0;
p->state='F';
p->next=NULL;
if(head==NULL)
{
head=p;q=p;time=p->arrivetime;
}
if(p->arrivetime < time)
time=p->arrivetime;
q->next=p;
q=p;
}
3. 若执行FCFS算法，按顺序遍历链表
void fcfs1()
{
int i;
p=head;
for(i=0;i<n;i++)
{
if(p->state=='F')
{
q=p;
run_fcfs1(q);
}
p=p->next;
}
}
void run_fcfs1(pcb *p1)
{
time = p1->arrivetime > time? p1->arrivetime:time;
p1->starttime=time;
printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID);
time+=p1->servicetime;
p1->state='T';
p1->finishtime=time;
printf("ID号 到达时间 开始运行时间 服务时间 完成时间 \n");
printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);
}
4. 若执行SPF算法，每次都从链表头开始遍历链表，找出arrivetime<=time并且运行时间最短的节点，执行该节点进程，最后再删除该节点。
void fcfs2()
{
while(head)
{
p=head;
q=p;
int Run_time=p->servicetime;
while (p!=NULL)
{
if (p->arrivetime<=time)
{
if (p->servicetime<Run_time)
{
q=p;
}
p=p->next;
}
else
p=p->next;
}
run_fcfs2(q);
pcb *pre;
if (q==head)
{
head=head->next;
}
else
{
pre=head;
while(pre->next!=q)
pre=pre->next;
if(q->next==NULL)
pre->next=NULL;
else
pre->next=q->next;
}
}
}
void run_fcfs2(pcb *p1)
{
p1->starttime=time;
printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID);
time+=p1->servicetime;
p1->state='T';
p1->finishtime=time;
printf("ID号 到达时间 开始运行时间 服务时间 完成时间 \n");
printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);
}
六：程序执行效果：
实验总结：
模拟实验调度算法，用到的具体知识还主要是数据结构中的知识，在这次实验中，FCFS算法实现还算比较简单，SPF算法稍微有一些麻烦，主要是在进行查找运行时间最短的节点，并需要满足到达时间<time,并且还要是没有执行的节点，这一点稍微有些麻烦。
源码
#include <windows.h>
#include <fstream.h>
#include <stdio.h>
#include <iostream>
typedef struct PCB
{
int ID;
char state;
int arrivetime;
int starttime;
int finishtime;
int servicetime;
struct PCB *next;
}pcb;
int time;//计时器
int n; //进程个数
pcb*head=NULL;
pcb*p,*q;
void fcfs1();
void fcfs2();
void run_fcfs1(pcb *p1);
void Create_process();
void Create_process()
{
ifstream inFile;
inFile.open("test.txt");
inFile>>n;
inFile.get();
int i=0;
for (;i<n;i++)
{
p=(pcb *)malloc(sizeof(pcb));
inFile>>p->ID;
inFile>>p->arrivetime;
inFile>>p->servicetime;
p->starttime=0;
p->finishtime=0;
p->state='F';
p->next=NULL;
if(head==NULL)
{
head=p;q=p;time=p->arrivetime;
}
if(p->arrivetime < time)
time=p->arrivetime;
q->next=p;
q=p;
}
inFile.close();
}
void run_fcfs1(pcb *p1)
{
time = p1->arrivetime > time? p1->arrivetime:time;
p1->starttime=time;
printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID);
time+=p1->servicetime;
p1->state='T';
p1->finishtime=time;
printf("ID号 到达时间 开始运行时间 服务时间 完成时间 \n");
printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);
}
void run_fcfs2(pcb *p1)
{
p1->starttime=time;
printf("\n现在时间：%d,开始运行作业%d\n",time,p1->ID);
time+=p1->servicetime;
p1->state='T';
p1->finishtime=time;
printf("ID号 到达时间 开始运行时间 服务时间 完成时间 \n");
printf("%d%10d%12d%12d%12d\n",p1->ID,p1->arrivetime,p1->starttime,p1->servicetime,p1->finishtime);
}
void fcfs1()
{
int i;
p=head;
for(i=0;i<n;i++)
{
if(p->state=='F')
{
q=p;
run_fcfs1(q);
}
p=p->next;
}
}
void fcfs2()
{
while(head)
{
p=head;
q=p;
int Run_time=p->servicetime;
while (p!=NULL)
{
if (p->arrivetime<=time)
{
if (p->servicetime<Run_time)
{
q=p;
}
p=p->next;
}
else
p=p->next;
}
run_fcfs2(q);
//删除该节点
pcb *pre;
if (q==head)
{
head=head->next;
}
else
{
pre=head;
while(pre->next!=q)
pre=pre->next;
if(q->next==NULL)
pre->next=NULL;
else
pre->next=q->next;
}
}
}
void main()
{
Create_process();
int i;
cout<<"输入1或2或0"<<endl;
cin>>i;
while(i!=0)
{
if (i==1)
{
fcfs1();
cout<<"输入1或2或0"<<endl;
cin>>i;
}
else if (i==2)
{
fcfs2();
cout<<"输入1或2或0"<<endl;
cin>>i;
}
}
}
第二篇：操作系统实验之进程调度报告
实验一:进程调度
一、实习内容
1．模拟批处理多道操作系统的进程调度；
2．模拟实现同步机构避免并发进程执行时可能与时间相关的错误；
二、实习目的
进程调度时进程管理的主要内容之一，通过设计，编制，调试一个简单的进程调度模拟系统，对进程调度，进程运行状态变换及PV操作加深理解和掌握。
三、实习题目
采用剥夺式优先算法，对三个进程进行模拟调度
模拟PV操作同步机构，用PV操作解决进程进入临界区的问题。
【提示】
（1）对三个进程进行模拟调度，对各进程的优先数静态设置，P1,P2,P3三个进程的优先数为1，2，3，并指定P1的优先数最高，P3的优先数最低，每个进程都处于执行态“e”，就绪态“r”，等待态“w”三种状态之一，并假定初始态为“r”。
（2）每一个进程用一个PCB表，PCB表的内容根据具体情况设置，该系统在运行过程中能显示或打印各进程和参数的变化情况，以便观察各进程的调度。
（3）在完成必要的初始化后，便进入进程调度程序，首先由P1进入执行，当执行进程因等待某各事件被阻塞或唤醒某个进程等待进程时，转进程调度。
（4）在进入临界区前后，调PV操作。
（5）如果被唤醒的进程优先数高于现有执行的进程，则剥夺现行进程的执行权。
（6）当三个进程都处于等待状态时，本模拟系统退出执行。
四、示例
1.数据结构：
（1）进程控制块PCB
struct{
int id;
char status;
int priority;
int waiter1;
}
（2）信号量
struct{
int value;
int waiter2;
}sem[2]
（3）现场保护栈stack
char stack[11][4]
每个进程都有一个大小为10个字的现场保护栈，用来保护被中断时的断点地址等信息。
（4）全局变量
int i;用以模拟一个通用寄存器
char addr;用以模拟程序计数器
int m1,m2;为系统设置的公用数据被三个进程共享使用。
五、程序框图：
六、程序说明：
本程序是用C语言编写，模拟三个进程的运行情况，过程在运行中要调用P操作申请信号量，如果该过程得到其申请的信号量，就继续运行，否则P操作阻塞该申请过程的运行，并将过程置为所申请信号量的等待者，如果已有其它过程在等待同一信号量则将该申请过程排在所有等待进程之后。
过程运行中除了调用P操作申请信号量外，还要调用V操作释放信号量，V操作在释放信号量之后，还将唤醒因申请此信号量而被阻塞的过程。
在程序运行的三个过程（PROCESS1,PROCESS2,PROCESS3），其中过程运行中通过P操作申请信号量1，过程2通过V操作释放信号量2，然后做一次操作申请信号量2。
三个过程之间存在这样一种关系：过程1消耗的信号量1由过程2通过V操作产生，而过程3即释放信号量2也消耗信号量2。
三个过程的运行通过进程调度模块同意安排，调度模块通过FIND()函数找到第一个就绪过程，如果当前没有过程已在运行，就直接运行此过程，如果有，则比较两者的优先数，然后运行优先权高者。
七、源程序：
#include <stdio.h>
int m1;
int m2;
struct{
int id;
int waiter1;
int priority;
char status;
}pcb[4];
struct{
int value;
int waiter2;
}sem[3];
char stack[11][4];
int i,ep;
char addr;
void init();
int find();
int w2();
int process1();
int process2();
int process3();
int p(int,int ,char); int v(int,int ,char);
main(){
init();
printf("系统程序开始执行\n"); for(;;){
if(find()!=0) w2(); else break;
}
printf("系统程序结束\n"); }
void init(){
int j,k;
pcb[0].status='w';
pcb[0].priority=4;
for(j=1;j<=3;j++){
pcb[j].id=j;
pcb[j].status='r';
pcb[j].waiter1=0;
pcb[j].priority=j;
}
for(j=1;j<=2;j++){
sem[j].value=1;
sem[j].waiter2=0;
}
i=0;
ep=0;
addr='0';
m1=0;
m2=0;
for(j=1;j<=10;j++){
for(k=1;k<=3;k++)
stack[j][k]='0';
}
}
int find(){
int j;
for(j=1;j<=3;j++)
if(pcb[j].status=='r') return(j); return(0);
}
int w2(){
int pd;
pd=find();
if(pd==0) return(0);
else if(ep==0){
pcb[pd].status='e';
ep=pd;
printf("进程%d正在执行\n",ep);
}
else if(pcb[pd].priority<pcb[ep].priority){ pcb[ep].status='r';
printf("读取进程%d\n",pcb[pd].id); pcb[pd].status='e';
ep=pd;
}
printf("运行进程%d\n",ep);
i=stack[1][ep];
addr=stack[2][ep];
switch(ep){
case 1:process1();
break;
case 2:process2();
break;
case 3:process3();
break;
default:printf("当前进程出现错误%d\n",ep); break;
}
}
int process1(){
if(addr=='m') goto m;
i=1;
a:
printf("进程1在信号量sem[1]上调用P操作\n"); if(p(1,1,'m')==0) return(0);
else goto m;
m:
printf("打印进程1...m1=%d\n",m1);
printf("打印进程1...i=%d\n",i);
i+=5;
goto a;
}
int process2(){
if(addr=='m') goto m;
if(addr=='n') goto n;
i=1;
a:
printf("进程2在信号量sem[2]上调用P操作\n"); if(p(2,2,'m')==0) return(0);
m:
m1=2*m2;
printf("进程2在信号量sem[1]上调用V操作m1=%d\n",m1); if(v(1,2,'n')==0) return(0);
else{
n:
printf("打印进程2...i=%d\n",i);
i+=10;
goto a;
}
}
int process3(){
if(addr=='m') goto m;
if(addr=='n') goto n;
i=1;
a:
if(i>4){
printf("进程3在信号量sem[2]上调用P操作\n"); if(p(2,3,'n')==0) return(0);
}
n:
m2=i;
printf("进程3在sem[2]信号量上调用V操作m=%d\n",m2); if(v(2,3,'m')==0) return(0);
else{
m:
i+=1;
goto a;
}
}
int p(int se,int p,char ad){
int w;
sem[se].value--;
if(sem[se].value==0) return(1);
printf("阻塞当前进程%d\n",p);
pcb[p].status='w';
ep=0;
pcb[p].waiter1=0;
w=sem[se].waiter2;
if(w==0) sem[se].waiter2=p;
else{
while(pcb[w].waiter1!=0) w=pcb[w].waiter1; pcb[w].waiter1=p;
}
stack[1][p]=i;
stack[2][p]=ad;
return(0);
}
int v(int se,int p,char ad){
int w;
sem[se].value++;
if(sem[se].value>0) return(1);
w=sem[se].waiter2;
sem[se].waiter2=pcb[w].waiter1;
pcb[w].status='r';
printf("唤醒进程%d\n",w);
stack[1][p]=i;
stack[2][p]=ad;
return(0);
}