㈠ 基于优先数的时间片轮转调度算法调度处理器
没有完全符合的,但是差不多的,你自己改改吧!
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
typedef struct PCBA
{
char name[30];
int round;
int prio;
int cputime;
int needtime;
char state;
struct PCBA *next;
} PCB,*CurrentRunPCB,*LinkQueue;
CurrentRunPCB SelMosHeiPrio(LinkQueue *Q);//从Q链表中选择一个优先级最大的进程
void InitQueue(LinkQueue *Q);//初始化链表Q，如果链表没有头指针，可以省略；
void InsertQueue(LinkQueue * Q,PCB* run);
{
}//将Run结点插入链表Q中，表示就绪队列里多了一个进程
void Priosch(LinkQueue Wait_Queue,LinkQueue Finish_Queue)//优先法运行，从就绪队列Wait_Queue中选择进程执行，（选择队列中优先级最高的进程），执行结束的进程放入完成队列中；
{ while (WaitQueue!=NULL)
{
CurrentRunPCB run=SelMosHeiPrio(&WaitQueue); //run为就绪队列中优先级最高的进程
run->cputime+=2;//时间片为2
run->needtime-=2;
run->prio=50-run->needtime;//动态优先级，但是优先级随着运行时间的增加，优先级增加，所以谁优先级高会一直占用CPU
run->state='r';
if(run->needtime>0)
{ run->state='w';
InsertQueue(&WaitQueue,run) ;
}
else
{cout<<"当前运行进称为："<<run->name<<"运行结束后就绪队列情况："<<'\n';
run->state='F';
run->needtime=0;
InsertQueue(&FinishQueue,run) ;
Print(&WaitQueue);
}
//当然可以采用不看进程运行过程，直接将优先级高的运行完，插入完成队列
/*
CurrentRunPCB run=SelMosHeiPrio(&WaitQueue);
cout<<"当前运行进称为："<<run->name<<"运行结束后就绪队列情况："<<'\n';
Print(&WaitQueue);
run->cputime=run->needtime;
run->needtime=0;
run->prio=50;//动态优先级，但是优先级随着运行时间的增加，优先级增加，所以谁优先级高会一直占用CPU
run->state='F';
InsertQueue(&FinishQueue,run) ;*/
}
void Print(LinkQueue*Q)//将队列的元素显示输出，输出包含进程名，进程CPUTIME,NEEDTIME,状态，优先级
{LinkQueue p=*Q;
cout<<"name cputime needtime state prio'"<<'\n';
while (p!=NULL)
{ cout<<p->name<<'\t'<<p->cputime<<'\t'<<p->needtime<<'\t'<<p->state<<'\t'<<p->prio<<'\n';
p=p->next;
}
}
CurrentRunPCB DeQueue(LinkQueue*Q)//从就绪队列中取出一个进程
{LinkQueue p=*Q;
*Q=(*Q)->next;
p->next=NULL;
return p;
}
void Roundsch(LinkQueue WaitQueue,LinkQueue FinishQueue)//轮转法运行，从就绪队列Wait_Queue中选择进程执行一个时间片，执行结束的进程放入完成队列中；若一个时间片未能执行完的进程再插入到就绪队列
{ while (WaitQueue!=NULL)
{
CurrentRunPCB run=DeQueue(&WaitQueue);
cout<<"当前运行进称为："<<run->name<<"运行结束后就绪队列情况："<<'\n';
run->cputime+=2;//时间片为2
run->needtime-=2;
run->prio=50- run->cputime;
run->state='r';
if(run->needtime>0)
{InsertQueue(&WaitQueue,run) ;
run->state='w';
}
else
{run->state='F';
run->needtime=0;
InsertQueue(&FinishQueue,run) ;
}
Print(&WaitQueue);
}
cout<<"完成队列情况："<<'\n';
Print(&FinishQueue);
}
void SetAllpro(LinkQueue*Q)//设置优先级函数50-p->needtime
{int max=0;
LinkQueue p,t;
t=NULL;
p=*Q;
if (p!=NULL)
{
max=p->prio;
p=p->next;
while(p)
{
if (max<p->prio) max=p->prio;
p=p->next;
}
p=*Q;
t=*Q;
if (t==p&&max==t->prio)
{*Q=(*Q)->next;
t->next=NULL;
return t;}
else{
t=t->next;
while(t)
{
if (max==t->prio)
{
p->next=t->next;
t->next=NULL;
return t;
}
else{p=t;
t=t->next;
}
}
}
}
return t;
}
void main()
{
PCBA *pcb0,*pcb1,*pcb2,*pcb3,*pcb4; //five processes 五个进程
LinkQueue Wait_Queue,Finish_Queue; //两个队列 等待和完成
Wait_Queue=NULL; //给队列赋初值，如果带有头指针的链表，可以用函数；
Finish_Queue=NULL;
//InitQueue(&Wait_Queue);
//InitQueue(&Finish_Queue);
char ch;
//给各个进程设置初值
pcb0= new PCBA();
pcb1= new PCBA();
pcb2= new PCBA();
pcb3= new PCBA();
pcb4= new PCBA();
//example
strcpy(pcb0->name,"process1");
pcb0->round=2;
pcb0->prio=0;
pcb0->cputime=0;
pcb0->needtime=5;
pcb0->state='W';
pcb0->next=NULL;
strcpy(pcb1->name,"process2");
pcb1->round=2;
pcb1->prio=0;
pcb1->cputime=0;
pcb1->needtime=7;
pcb1->state='W';
pcb1->next=NULL;
strcpy(pcb2->name,"process3");
pcb2->round=2;
pcb2->prio=0;
pcb2->cputime=0;
pcb2->needtime=3;
pcb2->state='W';
pcb2->next=NULL;
strcpy(pcb3->name,"process4");
pcb3->round=2;
pcb3->prio=0;
pcb3->cputime=0;
pcb3->needtime=11;
pcb3->state='W';
pcb3->next=NULL;
strcpy(pcb4->name,"process5");
pcb4->round=2;
pcb4->prio=0;
pcb4->cputime=0;
pcb4->needtime=8;
pcb4->state='W';
pcb4->next=NULL;
//将各个进程插入就绪队列中
InsertQueue(&Wait_Queue,pcb0);
InsertQueue(&Wait_Queue,pcb1);
InsertQueue(&Wait_Queue,pcb2);
InsertQueue(&Wait_Queue,pcb3);
InsertQueue(&Wait_Queue,pcb4);
//利用此算法实现Wait_Queue中prio=50-needtime;
SetAllpro(&Wait_Queue);
cout<<"请输入选择的调度算法(1 or 2 or anykey exit!)："<<endl;
cin>>ch;
switch(ch)
{
case '1':
Print(&Wait_Queue);
Roundsch(Wait_Queue,Finish_Queue);
break;
case '2':
Print(&Wait_Queue);
Priosch(Wait_Queue,Finish_Queue);
break;
default :
cout<<"你选择了退出!"<<endl;
system("pause");
return;
}
return;
}
㈡ 操作系统实验 使用C++完成处理器调度
在C++环境下建立空进程，输入
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
struct pcb { /* 定义进程控制块PCB */
char name[10];
char state;
int super;
int ntime;
int rtime;
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
sort() /* 建立对进程进行优先级排列函数*/
{
PCB *first, *second;
int insert=0;
if(ready==NULL)
{
p->link=ready;
ready=p;
}
else /* 进程比较优先级,插入适当的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
first=first->link;
second=second->link;/*插尾*/
}
if(insert==0) first->link=p;
}
}
input() /* 建立进程控制块函数*/
{'
int i,num;
system("cls"); /*清屏*/
printf("\n 请输入进程号?");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n 进程号No.%d:\n",i);
p=getpch(PCB);
printf("\n 输入进程名:");
scanf("%s",p->name);
printf("\n 输入进程运行时间:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->state='w';
p->link=NULL;
sort(); /* 调用sort函数*/
}
}
int space()
{
int l=0; PCB* pr=ready;
while(pr!=NULL)
{
l++;
pr=pr->link;
}
return(l);
}
disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/
{
printf("\n qname \t state \t super \t ndtime \t runtime \n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->state);
printf("|%d\t",pr->super);
printf("|%d\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("\n");
}
check() /* 建立进程查看函数 */
{
PCB* pr;
printf("\n **** 当前正在运行的进程是:%s",p->name); /*显示当前运行进程*/
disp(p);
pr=ready;
printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/
{
printf("\n 进程 [%s] 已完成.\n",p->name);
free(p);
}
running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
{
(p->rtime)++;
if(p->rtime==p->ntime)
destroy(); /* 调用destroy函数*/
else
{
p->state='w';
sort(); /*调用sort函数*/
}
}
main() /*主函数*/
{
int len,h=0;
char ch;
input();
len=space();
while((len!=0)&&(ready!=NULL))
{
ch=getchar();
h++;
printf("\n The execute number:%d \n",h);
p=ready;
ready=p->link;
p->link=NULL;
p->state='R';
check();
running();
printf("\n 按任一键继续......");
ch=getchar();
}
printf("\n\n 进程已经完成.\n");
ch=getchar();
}
㈢ 设计一个按优先数调度算法实现处理器调度的程序。
#include "stdio.h"
#include "malloc.h"
#include "string.h"
typedef struct node{
int time;
int name;
char statement;
int num;
struct node *next;
}node,*L;
void createL(L &l,int n){
l=(L)malloc(sizeof(node));
if(!l)
printf("error!");
else
l->next=NULL;
L p,q;
q=l;
for(int i=0;i<n;i++){
p=(L)malloc(sizeof(node));
printf("请输入进程的名字name:\n");
scanf("%d",&p->name);
getchar();
printf("请输入该进程的运行时间time:\n");
scanf("%d",&p->time);
printf("请输入其优先级数num:\n");
scanf("%d",&p->num);
getchar();
printf("请输入其状态:\n");
p->statement=getchar();
p->next=q->next;
q->next=p;
q=p;
getchar();
}
}
void traL(L &l){
L p;
p=l->next;
printf("进程名\t运行时间\t优先数\t状态\n");
while(p){
printf(" %d\t%5d\t%11d\t %c",p->name,p->time,p->num,p->statement);
printf("\n");
p=p->next;
}
}
void Sort(L &l)
{
L tail=NULL;
while(tail!= l->next)
{
L pre = l;
L cur = pre->next;
while(cur != tail && cur->next != tail)
{
if( cur->num < cur->next->num )
{
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = cur;
}
pre = pre->next;
cur = pre->next;
}
tail = cur;
}
}
void run(L &l){
Sort(l);
L p,r,q;
q=l;
if(l->next!=NULL)
p=l->next;
int j=0;
printf("第k次运行\t进程名\t运行时间\t优先数\t状态\n");
while(p!=NULL){
j++;
printf("%5d\t %d\t%5d\t%11d\t %c",j,p->name,p->time,p->num,p->statement);
printf("\n");
p->num--;
p->time--;
if(p->time==0){
p->statement='E';
r=p;
if(p->next!=NULL)
{
l->next=p->next;
free(r);
p=l->next;
}
else
break;
}
else{
Sort(l);
if(l->next!=NULL)
p=l->next;
else
break;
}
}
}
void main(){
L l;
int n;
printf("请输入进程的数目n:\n");
scanf("%d",&n);
createL(l,n);
traL(l);
run(l);
}
//这是运行过的，应该符合你的要求！
㈣ 2018-06-09
一、常见的批处理作业调度算法
1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。
2.短作业优先调度算法(SPF): 就是优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。
3.最高响应比优先算法(HRN)：FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。
4. 基于优先数调度算法(HPF)：每一个作业规定一个表示该作业优先级别的整数，当需要将新的作业由输入井调入内存处理时，优先选择优先数最高的作业。
5.均衡调度算法，即多级队列调度算法
基本概念：
作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)
作业平均周转时间(T)＝周转时间/作业个数
作业带权周转时间（Wi）＝周转时间/运行时间
响应比＝（等待时间＋运行时间）/运行时间
二、进程调度算法
1.先进先出算法(FIFO)：按照进程进入就绪队列的先后次序来选择。即每当进入进程调度，总是把就绪队列的队首进程投入运行。
2. 时间片轮转算法(RR)：分时系统的一种调度算法。轮转的基本思想是，将CPU的处理时间划分成一个个的时间片，就绪队列中的进程轮流运行一个时间片。当时间片结束时，就强迫进程让出CPU，该进程进入就绪队列，等待下一次调度，同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。
3. 最高优先级算法(HPF)：进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式最高优先级算法和不可抢占式最高优先级算法。
4. 多级队列反馈法：几种调度算法的结合形式多级队列方式。
三、空闲分区分配算法
\1. 首先适应算法：当接到内存申请时，查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配。此算法简单，可以快速做出分配决定。
2. 最佳适应算法：当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其进行分割并分配。此算法最节约空间，因为它尽量不分割到大的空闲区，其缺点是可能会形成很多很小的空闲分区，称为“碎片”。
3. 最坏适应算法：当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。该算法的优点是避免形成碎片，而缺点是分割了大的空闲区后，在遇到较大的程序申请内存时，无法满足的可能性较大。
四、虚拟页式存储管理中的页面置换算法
1.理想页面置换算法(OPT)：这是一种理想的算法，在实际中不可能实现。该算法的思想是：发生缺页时，选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。
2.先进先出页面置换算法(FIFO)：选择最先进入内存的页面予以淘汰。
3. 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。
4.最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。
三、磁盘调度
1.先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置
2.最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题
3.扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。
4.循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。
对一个进程来说,一个重要的指标是它执行所需要的时间. 从进程提交到进程完成的时间间隔为周转时间.也就是等待进入内存的时间,在就绪队列中等待的时间,在 CPU中执行的时间和I/O操作的时间的总和.
例1.设一个系统中有5个进程，它们的到达时间和服务时间如下，A的到达时间为0，服务时间为3；B的到达时间为2，服务时间为6；C的到达时间为4，服务时间为4；D的到达时间为6，服务时间为5；E的 到达时间为8，服务时间为2，忽略1/0以及其他开销时间，若分别按先来先服务（fFCFS）进行CPU调度，其平均周转时间为？
10.2
6.4
8.6
4.5
先来先服务调度算法
进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间
A 0 3 0 3 3
B 2 6 3 9 7
C 4 4 9 13 9
D 6 5 13 18 12
E 8 2 18 20 12
周转时间 = 完成时间 - 到达时间
平均周转时间 = 所有进程周转时间 / 进程数 = （3+7+9+12+12）/ 5 = 8.6
单道批处理系统中有4个作业，J1的提交时间8.0，运行时间为2.0；J2的提交时间8.6，运行时间为0.6；J3提交时间8.8，运行时间为0.2；J4的提交时间9.0，运行时间为0.5。在采用响应比高者优先调度算法时，其平均周转时间为T为（）小时？
2.5
1.8
1.975
2.675
周转时间=作业完成时间-作业提交时间
响应比=（作业等待时间+作业执行时间）/作业执行时间
当提交J1时，只有J1作业，执行J1，J1的周转时间为2，此时时间为10.
J2、J3、J4提交时，由于正在执行J1，因此等待。
当J1执行完毕（此时时间为10），J2、J3、J4的等待时间分别为：1.4,1.2,1，
其响应比分别为：1.4/0.6+1=3.33 1.2/0.2+1=7 1/0.5+1=3，因此执行J3，J3的周转时间为1.2+0.2=1.4
当J3执行完毕（此时时间为10.2），J2和J4的等待时间分别为1.6,1.2，
其响应比分别为：1.6/0.6+1=3.66 1.2/0.5+1=3.4，因此执行J2，J2的周转时间为1.6+0.6=2.2
执行J2完毕后时间为10.8，接下来执行J4，执行完后时时间为11.3，J4的周转时间为2.3
于是平均周转时间为（2+1.4+2.2+2.3）/4=1.975
如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。
例3、
现有4个同时到达的作业J1,J2,J3和J4,它们的执行时间分别是3小时,5小时,7小时,9小时系统按单道方式运行且采用短作业优先算法,则平均周转时间是()小时
12.5
24
19
6
作业到达时间执行时间开始时间完成时间周转时间
J103033
J20 5388
J30781515
J409152424
平均周转时间（3+8+15+24）/4=12.5
有4个进程A,B,C,D,设它们依次进入就绪队列，因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位，设时间片为1。四个进程的平均周转时间为 （）？
15.25
16.25
16.75
17.25
17.75
18.25
A:1 4 4 3 3 2 2 2 1 1 1 共24
B:2 4 4 3 3 2 2 共20
C:3 4 共7
D:4 4 3 3 共14
字母后面的数字为等待的时间加运行时间
平均周转时间为（24+20+7+14）/4=16.25
例5、假设系统按单值方式运行且采用最短作业优先算法，有J1,J2,J3,J4共4个作业同时到达，则以下哪几种情况下的平均周转时间为10分钟?
执行时间J1:1分钟 J2:5分钟 J3:9分钟 J4:13分钟
执行时间J1:1分钟 J2:4分钟 J3:7分钟 J4:10分钟
执行时间J1:2分钟 J2:4分钟 J3:6分钟 J4:8分钟
执行时间J1:3分钟 J2:6分钟 J3:9分钟 J4:12分钟
首先，短作业优先则短时间的作业利用资源，其余的作业等待
根据平均周转时间概念，将所有作业"等待时间"加上"运行时间"除以"作业数量"即可得到平均周转时间
A： (J1执行1分钟 + J2等待1分钟 + J2执行5分钟 + J3等待6分钟 + J3执行9分钟 + J4等待15分钟 + J4执行13分钟) / 4 = 50/4 = 12.5
B： (J1执行1分钟 + J2等待1分钟 + J2执行4分钟 + J3等待5分钟 + J3执行7分钟 + J4等待12分钟 + J4执行10分钟) / 4 = 40/4 = 10
C： (J1执行2分钟 + J2等待2分钟 + J2执行4分钟 + J3等待6分钟 + J3执行6分钟 + J4等待12分钟 + J4执行8分钟) / 4 = 40/4 = 10
D： (J1执行3分钟 + J2等待3分钟 + J2执行6分钟 + J3等待9分钟 + J3执行9分钟 + J4等待18分钟 + J4执行12分钟) / 4 = 50/4 = 12.5
例6、假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。 表1 进程到达和需要服务时间 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2
表2 进程的完成时间和周转时间
进程 A B C D E 平均
FCFS 完成时间 3 9 13 18 20
周转时间 3 7 9 12 12 8.6
带权周转时间 1.00 1.17 2.25 2.40 6.00 2.56
SPF(非抢占) 完成时间 3 9 15 20 11
周转时间 3 7 11 14 3 7.6
带权周转时间 1.00 1.17 1.75 2.80 1.50 1.84
SPF(抢占) 完成时间 3 15 8 20 10
周转时间 3 13 4 14 2 7.2
带权周转时间 1.00 2.16 1.00 2.80 1.00 1.59
例7、假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示： 作业 进入系统时间 估计运行时间/分钟 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18
5 9:10 5
如果应用先来先服务和应用最短作业优先的作业调度算法，试将下面表格填写完整。
(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。
作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟
1 8:00 40 8：00 8：40 40
2 8:20 30 8：40 9：10 50
3 8:30 12 9：10 9：22 52
4 9:00 18 9：22 9：40 40
5 9:10 5 9：40 9：45 35
作业平均周转时间T= 43.4 217
2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。 作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟 1 8:00 40 8：00 8：40 40 2 8:20 30 8：52 9：22 62 3 8:30 12 8：40 8：52 22 4 9:00 18 9：27 9：45 45 5 9:10 5 9：22 9：27 17作业平均周转时间T= 37.2 186
CPU和两台输入/输出设备(I1,I2)多道程序设计环境下,同时有三个作业J1,J2,J3进行,这三个作业
使用CPU和输入/输出设备的顺序和时间如下所示:
J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)
J2:I1(25ms);CPU(30ms);I2(35ms)
J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);
假定CPU,I1,I2都能并行工作,J1的优先级最高,J2次之,J3优先级最低,优先级高的作业可以抢占优先级低的作业的CPU,但不能抢占I1,I2,作业从J3开始到完成需要多少时间?
㈤ 设计一个按优先数调度算法实现处理器调度的程序。 高手帮忙!!
#include <stdio.h>
#include <stdlib.h> //提供atoi()函数
#include <conio.c> //提供clrscr()函数
#define M 10 //字符串大小常量
#define N 3 //进程数常量
#define SLOT 2
typedef struct node{
char name[M];
int prio; //优先级
int round; //时间片长度
int cputime; //已经使用的cpu时间
int needtime;//需要多少cpu时间
int count; //计数器
char state; //进程的当前状态
struct node *next; //指向下一个进程
}PCB;
PCB *finish,*ready,*tail,*run;
void ShowHead(char *s1,char *s2);
int Menu_Select();
void Creat(int select);
void InsertPriority(PCB *q);
void InsertSlot(PCB *q);
void PrintOneProcess(int select,PCB *q);
void PrintAllProcess(int select);
void FirstIn();
void FIFODo(int select);
void PriorityDo(int select);
void SlotDo(int select);
void Quit();
main()
{
while(1)
{
clrscr();
switch(Menu_Select())
{
case 1:
Creat(1);
FIFODo(1);
printf("\n\n\t\t按回车键返回菜单...");
getchar();
getchar();
break;
case 2:
Creat(2);
PriorityDo(2);
printf("\n\n\t\t按回车键返回菜单...");
getchar();
getchar();
break;
case 3:
Creat(3);
SlotDo(3);
printf("\n\n\t\t按回车键返回菜单...");
getchar();
getchar();
break;
case 0:
Quit();
break;
}
}
}
/*打印每个界面的开头显示*/
void ShowHead(char *s1,char *s2)
{
printf("\t ==================%s========================\n\n",s1);
printf("\t\t\t\t%s\n\n",s2);
printf("\t ========================================================\n\n");
}
/*主菜单*/
int Menu_Select()
{
int choose;
char s[2];
clrscr();
printf("====================进程调度算法模拟程序=====================\n\n");
printf("\t\t 1.先进先出调度策略\n");
printf("\t\t 2.优先数调度策略\n");
printf("\t\t 3.时间片轮转调度策略\n");
printf("\t\t 0.退出系统\n\n");
printf("=============================================================\n\n");
do
{
printf("\n请输入你的选择(0-3):");
scanf("%s",s);
choose=atoi(s);
}while(choose<0 || choose>3);
return choose;
}
/*创建调度算法的链表*/
void Creat(int select)
{
PCB *p,*q; //q为就绪队列的最后一个结点
int i,time,rounds;
char na[M];
ready=NULL;
finish=NULL;
run=NULL;
if(select==1) //先进先出调度创建
{
printf("\nEnter name and time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='W';
p->next=NULL;
if(ready!=NULL) //就绪队列不为空
{
q->next=p;
q=p;
}
else //就绪队列为空
{
p->next=ready;
ready=p;
q=ready;
}
}
clrscr();
ShowHead("先进先出调度策略","FIFO dispatching algorithm ");
printf("\t\t name cputime needtime state\n");
PrintAllProcess(select); //打印出初始状态的信息
}
else if(select==2) //优先数调度创建
{
printf("\nEnter name and time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='W';
p->prio=50-time;
if(ready!=NULL) //就绪队列不为空的时候
InsertPriority(p);
else //就绪队列为空
{
p->next=ready;
ready=p;
}
}//end of for()
clrscr();
ShowHead("优先级调度策略","Priority dispatching algorithm ");
printf("\t\t name cputime needtime prio state\n");
PrintAllProcess(select); //打印出初始状态的信息
}//end of else if()
else if(select==3) //时间片轮转调度创建
{
printf("\nEnter name and the time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->count=0; //计数器
p->round=SLOT;
p->state='W';
if(ready!=NULL)
InsertSlot(p);
else
{
p->next=ready;
ready=p;
}
}
clrscr();
ShowHead("时间片轮转调度策略","Time slot dispatching algorithm ");
printf("\n\t\t name cputime needtime count slot state\n");
PrintAllProcess(select); //打印出初始状态的信息
}
run=ready; //从就绪队列取一个进程，使其运行，同时就绪队列的头指针后移
run->state='R';
ready=ready->next;
}
/*优先调度：把进程插入到合适的位置，就绪队列按优先级由高到低的顺序排列*/
void InsertPriority(PCB *q)
{
PCB *pre,*p;
int flag=1;
pre=NULL;
p=ready;
while(p!=NULL && flag)
{
if(p->prio>q->prio)
{
pre=p;
p=p->next;
}
else
flag=0;
}
if(pre==NULL)
{
q->next=ready;
ready=q;
}
else
{
pre->next=q;
q->next=p;
}
}
/*时间片轮转：把结点插入到就绪队列的末尾*/
void InsertSlot(PCB *q)
{
PCB *pre,*p;
pre=NULL;
p=ready;
while(p!=NULL)
{
pre=p;
p=p->next;
}
pre->next=q;
q->next=NULL; /*由于插入到队列的末尾，所以必须要使其的下一个结点为空值*/
}
/*打印一个信息*/
void PrintOneProcess(int select,PCB *q)
{
if(select==1)
printf("\t\t %-10s%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->state);
else if(select==2)
printf("\t\t %-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);
else if(select==3)
printf("\t\t %-10s%-10d%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->count,q->round,q->state);
}
/*将所有的进程打印出来，按运行，就绪，完成顺序打印*/
void PrintAllProcess(int select)
{
PCB *p;
if(run!=NULL)
PrintOneProcess(select,run);
p=ready;
while(p!=NULL)
{
PrintOneProcess(select,p);
p=p->next;
}
p=finish;
while(p!=NULL)
{
PrintOneProcess(select,p);
p=p->next;
}
}
/*把就绪队列的第一个进程调入运行*/
void FirstIn()
{
run=ready;
ready=ready->next;
run->state='R';
}
/*先进先出调度策略*/
void FIFODo(int select)
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) //进程执行结束
{
printf("\n\t\t name cputime needtime state\n");
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn();
PrintAllProcess(1);
}
}
}
/*优先级算法*/
void PriorityDo(int select)
{
while(run!=NULL)
{
printf("\n\t\t name cputime needtime prio state\n");
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-3;
if(run->needtime==0)
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn();
}
else if((ready!=NULL) && (run->prio < ready->prio))
{
run->state='W';
InsertPriority(run);
FirstIn();
}
PrintAllProcess(select);
}
}
/*时间片轮转算法*/
void SlotDo(int select)
{
while(run!=NULL)
{
printf("\n\t\t name cputime needtime count slot state\n");
run->count=run->count+1;
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) /*运行完成时*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn(); //就绪队列不为空，将就绪队列的第一个进程投入运行
}
else if(run->count==run->round) /*时间片已经到了，还未运行完成*/
{
run->count=0; //时间片
if(ready!=NULL)
{
run->state='W';
InsertSlot(run);
FirstIn();
}
}
PrintAllProcess(select); //打印本次的所有记录
}
}
void Quit()
{
char ch;
clrscr();
gotoxy(10,5);
printf("==========================================================\n\n");
printf(" Thank you for you using\n\n");
gotoxy(10,9);
printf("==========================================================\n\n");
gotoxy(13,15);
getchar();
printf("\n\t\tDo you really want to quit(y/Y or n/N):");
scanf("%c",&ch);
if(ch=='y' || ch=='Y')
{
printf("\n\t\t按任意键退出系统...");
getchar();
exit(0);
}
}
㈥ 进程调度方案设计 实现一个基本动态优先级的调度算法
前两天做操作系统作业的时候学习了一下几种进程调度算法，在思考和讨论后，有了一些自己的想法，现在就写出来，跟大家讨论下。，或者说只有有限的CPU资源，当系统中有多个进程处于就绪状态，要竞争CPU资源时，操作系统就要负责完成如何分配资源的任务。在操作系统中，由调度程序来完成这一选择分配的工作，调度程序所使用的算法即是调度算法。调度算法需要考虑的指标主要有尽量保证CPU资源分配的公平性；按照一定策略强制执行算法调度；平衡整个计算机系统，尽量保持各个部分都处于忙碌状态。而根据系统各自不同的特点和要求，调度算法又有一些侧重点和目标不同，因此，算法按照系统差异主要分为三大类：批处理系统中的调度算法，代表调度算法有：先来先服务、最短作业优先、最短剩余时间优先。交互式系统中的调度算法，代表调度算法有：轮转调度、优先级调度、多级队列、最短进程优先、保证调度、彩票调度、公平分享调度。实时系统中的调度算法，代表调度算法有：速率单调调度、最早最终时限优先调度。下面就上述提到的调度算法中挑出几个进行重点分析：保证调度保证调度是指利用算法向用户做出明确的性能保证，然后尽力按照此保证实现CPU的资源分配。利用这种算法，就是定一个进程占用CPU的时间的标准，然后按照这个标准去比较实际占用CPU的时间，调度进程每次使离此标准最远的进程得到资源，不断满足离所保证的标准最远的进程，从而平衡资源分配满足这个标准的要求。保证调度算法的优点是：能很好的保证进程公平的CPU份额，当系统的特点是：进程的优先级没有太大悬殊，所制定的保证标准差异不大，各个进程对CPU的要求较为接近时，比如说系统要求n个进程中的每个进程都只占用1/n的CPU资源，利用保证调度可以很容易的实现稳定的CPU分配要求。但缺点是，这种情况太过理想，当系统的各个进程对CPU要求的紧急程度不同，所制定的保证较为复杂的时候，这个算法实现起来比较困难。彩票调度彩票调度这种算法的大意是指向进程提供各种系统资源如CPU资源的彩票，当系统需要做出调度决策时，随机抽出一张彩票，由此彩票的拥有者获得资源。在彩票调度系统中，如果有一个新的进程出现并得到一些彩票，那么在下一次的抽奖中，该进程会有同它持有彩票数量成正比例的机会赢得奖励。进程持有的彩票数量越多，则被抽中的可能性就越大。调度程序可以通过控制进程的彩票持有数量来进行调度。彩票调度有很多优点：首先，它很灵活，系统增加分给某个进程的彩票数量，就会大大增加它占用资源的可能性，可以说，彩票调度的反应是迅速的，而快速响应需求正是交互式系统的一个重要要求。其次，彩票调度算法中，进程可以交换彩票，这个特点可以更好的保证系统的平衡性，使其各个部分都尽可能的处于忙碌状态。而且利用彩票调度还可以解决许多别的算法很难解决的问题，例如可以根据特定的需要大致成比例的划分CPU的使用。速率单调调度速率单调调度算法是一种可适用于可抢占的周期性进程的经典静态实时调度算法。当实时系统中的进程满足：每个周期性进程必须在其周期内完成，且进程之间没有相互依赖的关系，每个进程在一次突发中需要相同的CPU时间量，非周期的进程都没有最终时限四个条件时，并且为了建模方便，我们假设进程抢占即刻发生没有系统开销，可以考虑利用速率单调算法。速率单调调度算法是将进程的速率（按照进程周期所算出的每秒响应的次数）赋为优先级，则保证了优先级与进程速率成线性关系，这即是我们所说的速率单调。调度程序每次运行优先级最高的，只要优先级较高的程序需要运行，则立即抢占优先级低的进程，而优先级较低的进程必须等所有优先级高于它的进程结束后才能运行。速率单调调度算法可以保证系统中最关键的任务总是得到调度，但是缺点是其作为一种静态算法，灵活性不够好，当进程数变多，系统调度变得复杂时，可能不能较好的保证进程在周期内运行。最早最终时限优先调度最早最终时限优先调度算法是一个动态算法，不要求进程是周期性的，只要一个进程需要CPU时间，它就宣布它的到来时间和最终时限。调度程序维持一个可运行的进程列表，按最终时限排序，每次调度一个最终时限最早的进程得到CPU 。当新进程就绪时，系统检查其最终时限是否在当前运行的进程结束之前，如果是，则抢占当前进程。由于是动态算法，最早最终优先调度的优点就是灵活，当进程数不超过负载时，资源分配更优，但也同样由于它的动态属性，进程的优先级都是在不断变化中的，所以也没有哪个进程是一定可以保证满足调度的，当进程数超过负载时，资源分配合理度会急速下降，所以不太稳定。
㈦ 动态高优先权优先调度算法
动态高优先权优先调度算法：
动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。
算法代码模拟实现：
#include<stdio.h>
#include<stdlib.h>
#defineN6
//待插入就绪队列的进程数据
intid[N]={0,1,
2,3,4,
5};
intpriority[N]={9,38,17,
2,7,18};
intcpuTime[N]={0,
0,0,0,
0,0};
intallTime[N]={3,
2,3,6,
1,3};
//********************************
//
//模拟进程/PCB数据结构
//
//********************************
//
枚举进程的状态：就绪、执行、阻塞、完成
enumSTATE{Ready,Run,Block,Finish
};
//建立PCB结构体
structPCB{
intid;//标志数
intpriority;//优先数
intcpuTime;//
已占CPU时间
intallTime;//
还需占CPU时间
intblockTime;//已被阻塞的时间
STATEstate;//
进程状态
PCB*pre;//
PCB的前指针
PCB*nxt;//
PCB的后指针
};
//********************************
//
//模拟进程队列
//
//********************************
//进程入列
voidqueQush(PCB*process,PCB
*queHead)
{
process->pre=NULL;
process->nxt=
queHead->nxt;
if(queHead->nxt!=NULL){
//非第一个入列
queHead->nxt->pre=
process;
}
queHead->nxt=process;
}
//进程出列
voidquePop(PCB*process,PCB
*queHead)
{
if(process->pre!=NULL){
//不是头节点
process->pre->nxt=
process->nxt;
}
else{
queHead->nxt=
process->nxt;
}
if(process->nxt!=NULL){
//不是尾节点
process->nxt->pre=
process->pre;
}
//
清空进程指针
process->pre=process->nxt=
NULL;
}
//查看队列里进程的信息
voidqueWalk(PCB*queHead)
{
PCB*pro=queHead->nxt;
if(pro==NULL){
printf("(无进程) ");
return;
}
while(pro!=NULL)
{
printf("id:%d,
pri:%d,alltime:%d ",
pro->id,
pro->priority,
pro->allTime);
pro=
pro->nxt;
}
}
//********************************
//
//模拟就绪队列
//
//********************************
intreadyQueNum;//就绪队列的进程数量
PCBreadyQueHead;//
就绪队列的头部
PCB*readyMaxProcess;//就绪队列中优先级最高的进程
//进程插入到就绪队列
voidreadyQueQush(PCB
*process)
{
readyQueNum++;
process->state=Ready;
queQush(process,&readyQueHead);
}
//优先级最高的进程出列
PCB*readyQuePop()
{
readyQueNum--;
quePop(readyMaxProcess,
&readyQueHead);
returnreadyMaxProcess;
}
//每个时间片，更新就绪队列里进程的信息
voidreadyQueUpdate()
{
intmaxPriority=-1;
PCB*pro=readyQueHead.nxt;
if(pro==NULL){
//就绪队列没有进程
readyMaxProcess=
NULL;
return;
}
while(pro!=NULL)
{
pro->priority
++;
if(pro->priority>maxPriority)
{
maxPriority=
pro->priority;
readyMaxProcess=pro;
}
pro=
pro->nxt;
}
}
//返回就绪队列最高优先级的值
intreadyMaxPriority()
{
returnreadyMaxProcess->priority;
}
//查看就绪队列里进程的信息
voidreadyQueWalk()
{
printf("就绪队列里的进程信息为： ");
queWalk(&readyQueHead);
}
//********************************
//
//模拟阻塞队列
//
//********************************
#defineEndBlockTime3
//进程最长被阻塞时间
intblockQueNum;//阻塞队列的进程数量
PCBblockQueHead;//
阻塞队列的头部
PCB*blockMaxProcess;//阻塞队列中优先级最高的进程
//进程插入到阻塞队列
voidblockQueQush(PCB
*process)
{
blockQueNum++;
process->blockTime=0;
process->state=Block;
queQush(process,&blockQueHead);
}
//优先级最高的进程出列
PCB*blockQuePop()
{
blockQueNum--;
quePop(blockMaxProcess,
&blockQueHead);
returnblockMaxProcess;
}
//每个时间片，更新阻塞队列里进程的信息
voidblockQueUpdate()
{
intmaxPriority=-1;
PCB*pro=blockQueHead.nxt;
while(pro!=NULL)
{
pro->blockTime
++;
if(pro->blockTime>=EndBlockTime)
{
PCB*process=pro;
pro=pro->nxt;
//阻塞时间到，调入就绪队列
blockQueNum--;
quePop(process,
&blockQueHead);
readyQueQush(process);
}else
if(pro->priority>maxPriority)
{
//更新阻塞队列里优先级最高的进程指针
maxPriority=
pro->priority;
blockMaxProcess=pro;
pro=pro->nxt;
}
}
}
//查看阻塞队列里进程的信息
voidblockQueWalk()
{
printf("阻塞队列里的进程信息为： ");
queWalk(&blockQueHead);
}
//********************************
//
//模拟动态优先权的进程调度
//
//********************************
//初始化数据
voidinitData()
{
//
初始化就绪队列和阻塞队列
readyQueNum=blockQueNum=0;
readyMaxProcess=blockMaxProcess=NULL;
readyQueHead.pre=readyQueHead.nxt=NULL;
blockQueHead.pre=blockQueHead.nxt=NULL;
//
初始化进程进入就绪队列
inti,maxPriority=-1;
for(i=0;i<N;i
++)
{
//分配一个PCB的内存空间
PCB*pro=(PCB
*)malloc(sizeof(PCB));
//给当前的PCB赋值
pro->id
=id[i];
pro->priority
=priority[i];
pro->cpuTime
=cpuTime[i];
pro->allTime
=allTime[i];
pro->blockTime
=0;
if(pro->allTime>0){
//插入到就绪队列中
readyQueQush(pro);
//更新就绪队列优先级最高的进程指针
if(pro->priority>
maxPriority){
maxPriority=pro->priority;
readyMaxProcess=pro;
}
}
}
}
//模拟cpu执行1个时间片的操作
voidcpuWord(PCB
*cpuProcess)
{
cpuProcess->priority-=3;
if(cpuProcess->priority<0)
{
cpuProcess->priority=0;
}
cpuProcess->cpuTime++;
cpuProcess->allTime--;
//
显示正执行进程的信息：
printf("CPU正执行的进程信息为： ");
printf("id:M,pri:M,
alltime:M ",
cpuProcess->id,
cpuProcess->priority,
cpuProcess->allTime);
}
intmain()
{
inttimeSlice=0;//
模拟时间片
intcpuBusy=0;
//模拟cpu状态
PCB*cpuProcess=NULL;//当前在cpu执行的进程
//
初始化数据
initData();
//
模拟进程调度
while(1)
{
if(readyQueNum==0
&&blockQueNum==0
&&cpuBusy==0){
//就绪队列、阻塞队列和cpu无进程，退出
break;
}
//printf(" %d%d",
readyQueNum,blockQueNum);
if(cpuBusy==0)
{
//cpu空闲，选择一个进程进入cpu
if(readyQueNum>0)
{
//
选择绪队列优先级最高的进程
cpuProcess
=readyQuePop();
}else{
//
就绪队列没有进程，改为选择阻塞队列优先级最高的进程
cpuProcess
=blockQuePop();
}
cpuProcess->cpuTime=
0;
cpuProcess->state=
Run;
cpuBusy=1;
}
timeSlice++;
printf(" 第%d个时间片后： ",
timeSlice);
//
模拟cpu执行1个时间片的操作
cpuWord(cpuProcess);
if(cpuProcess->allTime==0){
cpuProcess->state=
Finish;
//释放已完成进程的PCB
free(cpuProcess);
cpuBusy=0;
}
//
更新就绪队列和阻塞队列里的进程信息
blockQueUpdate();
readyQueUpdate();
//
查看就绪队列和阻塞队列的进程信息
readyQueWalk();
blockQueWalk();
if(cpuBusy==1
&&readyQueNum>0
&&
cpuProcess->priority
<readyMaxPriority()){
//需抢占cpu，当前执行的进程调入阻塞队列
blockQueQush(cpuProcess);
cpuProcess=readyQuePop();
}
}
printf(" 模拟进程调度算法结束 ");
return0;
}