基于时间片的调度算法

1. 基于优先级的时间片轮转进程调度算法

#include<iostream>
using namespace std;
struct PCB_Type{
char name;
int cpu_time;
};
struct QueueNode{
struct PCB_Type PCB;
struct QueueNode *next;
};

int main(){
int m,n,t;
int usecpu=0,unusecpu=0;
cout<<"输入就绪队列中的进程数目m：";
cin>>m;
cout<<"输入阻塞队列中的进程的数目n：";
cin>>n;
cout<<"输入唤醒系统资源的相隔时间片个数t：";
cin>>t;
struct QueueNode *readyhead=new QueueNode ,*readytail=new QueueNode,
*blockedhead=new QueueNode,*blockedtail=new QueueNode;
// readyhead=NULL;readytail=NULL;blockedhead=NULL;blockedtail=NULL;
readyhead=readytail;
blockedhead=blockedtail;
for(int i=1;i<=m;i++){
struct QueueNode *t1=new QueueNode;
cout<<"输入就绪队列中进程的name和cpu_time：";
cin>>t1->PCB.name>>t1->PCB.cpu_time;
readytail->next=t1;
readytail=t1;
}
for(int j=1;j<=n;j++){
struct QueueNode *t2=new QueueNode;
cout<<"输入阻塞队列中进程的name和cpu_time：";
cin>>t2->PCB.name>>t2->PCB.cpu_time;
blockedtail->next=t2;
blockedtail=t2;
}

cout<<"输出就绪队列的进程信息：";
for(struct QueueNode *t3=readyhead->next;t3!=readytail->next;t3=t3->next){
cout<<t3->PCB.name<<"、"<<t3->PCB.cpu_time<<"---> ";
}
cout<<"无进程";
cout<<endl;
cout<<"输出阻塞队列的进程信息：";
struct QueueNode *t4;
t4=blockedhead->next;
while(t4!=blockedtail->next){
cout<<t4->PCB.name<<"、"<<t4->PCB.cpu_time<<"---> ";
t4=t4->next;
}
cout<<"无进程";
cout<<endl<<"进程的运行顺序：";
int x=0;
while(readyhead!=readytail||blockedhead!=blockedtail){
if(readyhead!=readytail){
struct QueueNode *p=readyhead->next;
cout<<p->PCB.name<<",";
p->PCB.cpu_time--;
usecpu++;
if(readyhead->next!=readytail){
if(p->PCB.cpu_time>0){
readyhead->next=p->next;//出队列
readytail->next=p;
readytail=p;
}
else{
readyhead->next=p->next;
delete p;
}
}
else//队列中只有两个节点 头结点和尾结点
{
if(p->PCB.cpu_time<=0){readytail=readyhead;//只有进程为执行完，就继续执行，完成之后，把队列清空，释放指针p；就绪队列无进程
delete p;}
}

}
else
{
unusecpu++;
cout<<"_,";
}
x++;
if(x==t){
if(blockedhead!=blockedtail){

struct QueueNode *q=blockedhead->next;
if(blockedhead->next!=blockedtail)
{
blockedhead->next=q->next;
}
else
{
blockedhead=blockedtail;
}
readytail->next=q;
readytail=q;
x=0;
}
}
}
cout<<endl;
cout<<"cpu的利用率="<<usecpu<<"/"<<usecpu+unusecpu<<endl;
return 0;
}

#include"stdio.h"
#include"stdlib.h"
#include "string.h"
#define WAIT 1
#define RUN 2
#define FINISH 3

typedef struct pcb
{
int num;
struct pcb *next;
int priority;
int timeneed;
int state;
}pcb;/*用此结构体来模拟一个进程*/

struct pcb *head;
struct pcb *run;

pcb *jccreat(int n)/*此函数用于创建进程队列*/
{
int i=1;
pcb *head,*p,*q;

randomize();/*随机函数的初始化*/

head=(pcb *)malloc(sizeof(pcb));/*创建一个空表头*/
p=head;

for(i=1;i<=n;i++)/*用循环来创建指定个 结点*/
{
q=(pcb *)malloc(sizeof(pcb));
p->next=q;
q->num=i;
q->next=NULL;
q->priority=random(10);/*随机产生优先级*/
q->timeneed=random(10);/*随机产生运行时间*/
q->state=WAIT;
p=q;
}

return head;/*返回表头指针*/
}

pcb *getmaxpriority(struct pcb *head)/*此函数用来挑选一个优先级最大的进程来执行*/
{
struct pcb *p,*q;
int max;
p=head->next;
max=p->priority;/*初始max为队首结点的优先级*/
q=p;
while(p) /*当p不为空时，进行逐一比较*/
{
if(p->priority>max)/*逐一比较，选出优先级最大的结点*/
{max=p->priority;
q=p;}
p=p->next;
}
return q;
}

void delect(struct pcb *head,struct pcb *run)/*此函数用来将运行完的进程删除出进程队列*/
{
struct pcb *q=head;

while(q->next)/*扫描进程队列，找到执行完了的进程*/
{
if(q->next->num==run->num)/*判断是不是已完成的进程*/
{
if(run->next!=NULL)
q->next=run->next;
else q->next=NULL;
free(run);/*释放申请的空间*/
return;
}
q=q->next;
}

}

void control()/*此函数是用来控制各个进程的执行和调度*/
{
struct pcb *p;
run=head->next;/*初始让第一个进程运行*/
run->state=RUN;
while(run) /*当进程状态是不为空时运行*/
{
if(run->timeneed>0)/*如果当前run指针指向的进程所需时间不为零，状态为运行状态，就让这个进程运行*/
if(run->state==RUN)
{printf("pcb%d is running.\n",run->num);
printf("Waiting list:");/*显示整个等待队列*/
p=head->next;
while(p)
{
if(p!=run)
printf("pcb%d ",p->num);
p=p->next;
}
printf("\n");
delay(10000000);/*模拟进程运行*/
run->timeneed--;/*进程需要时间减一*/
run->priority=run->priority-3;/*进程优先级减三*/
}

if(run->timeneed!=0)
{
if(run->priority<=head->next->priority)/*如果当前运行完的进程的优先级低于队首进程的优先级*/
{run->state=WAIT;
run=getmaxpriority(head);/*则从进程队列中挑选一个优先级最大的进程来运行*/
run->state=RUN;}
}
else
{ printf("pcb%d is finished.\n",run->num);
delect(head,run);/*删除该结点*/
if(head->next!=NULL)/*判断进程队列是不是为空*/
{run=head->next;
run->state=RUN;}
else
{printf("All progresses are done.\n");

return;}
}
}
}

main()
{
int n;
int flag=1;

printf("Enter the number of the progresses:");
scanf("%d",&n);/*输入要创建的进程的数量*/

head=jccreat(n);/*创建进程队列，将链表的表头赋给head指针*/
run=head->next;/*run指针指向正在运行的进程的pcb*/
while(run)
{
printf("num: %d ,priority: %d ,timenees: %d \n",run->num,run->priority,run->timeneed);

run=run->next;
} /*将刚创建的进程队列打印出来*/
while(flag)/*由flag的值判断是否继续执行control()函数*/
{
if(head->next)/*判断进程是否完成*/
control();
else flag=0;
}
getch();
}

选一个把

2. 操作系统中关于时间片轮转调度算法！大家帮解答下！

时间片第一级1s，第二级2s，第三级4s...优先级第一级>第二级>第三级...首先A进入第一级执行1s，进入第二级，由于此时B还没有到达，所以A在第二级执行2s，完成，此时是第3s。B第2s已进入第一级，此时回到第一级B执行1s进入第二级，4s的时候c进入第一级，C执行1s进入第二级排在B的后面。此时候为5S，D没有到达，第一级没有进程，所以第二级B执行2S，进入第三级，此时为7S，D已进入第一级，D执行一S，转入第二级排在C后面，8S，E进入第一级，执行一S，进入第二级，排在D后面。第一级没有进程，第二级的C执行2S，进入第三级，D执行2s进入第三级，E执行1S完成，此时是14S。第二级没有进程，由第三级的D开始，执行3S完成，此时是17S，C执行1S完成，此时是18S，D执行2S完成，此时是20S。所以答案是，3，17，18，20，14

3. 常见的调度算法总结

一、FCFS——先来先服务和短作业（进程）优先调度算法

1. 先来先服务调度算法。

先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度， 也可用于进程调度。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。由此可知，本算法适合于CPU繁忙型作业， 而不利于I/O繁忙型的作业（进程）。

2. 短作业（进程）优先调度算法。

短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度， 也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。

二、FPF高优先权优先调度算法

1. 优先权调度算法的类型。

为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。 此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度， 将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，此时， 又可以进一步把该算法分成以下两种：

1)非抢占式优先权算法

2)抢占式优先权调度算法（高性能计算机操作系统）

2. 优先权类型 。

对于最高优先权优先调度算法，其核心在于：它是使用静态优先权还是动态优先权， 以及如何确定进程的优先权。

3.动态优先权

高响应比优先调度算法为了弥补短作业优先算法的不足，我们引入动态优先权，使作业的优先等级随着等待时间的增加而以速率a提高。 该优先权变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间；即 =（响应时间）/要求服务时间

三、基于时间片的轮转调度算法

1.时间片轮转法。

时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。 当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。

2. 多级反馈队列调度算法

多级反馈队列调度算法多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。 其实施过程如下：

1) 设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中， 为每个进程所规定的执行时间片就越小。

2) 当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。 如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度…… 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。

3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；

仅当第1到第（ i-1 ）队列空时， 才会调度第i队列中的进程运行，并执行相应的时间片轮转。

4) 如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列， 则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。

4. 时间片轮转调度算法的算法

多级反馈队列调度算法
(1) 设置多个就绪队列,并为各个队列赋予不同的优先级. 第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低.
该算法赋予各个队列中进程执行时间片的大小也各不相同:
在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小.
例如:第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍.
(2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度.当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n队列中便采取按时间片轮转的方式运行.
(3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行; 仅当第1~(i-1) 队列均空时,才会调度第i队列中的进程运行.如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程.?
性能
(1)终端型作业用户
(2) 短批处理作业用户
(3) 长批处理作业用户
满足了多数用户的需求 优先权调度算法
1,优先权调度算法的类型
非抢占式优先权算法
在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成; 或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程.这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中.
抢占式优先权调度算法
系统同样把处理机分配给优先权最高的进程,使之执行.但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程.
这种抢占式的优先权调度算法,能更好地满足紧迫作业的要求,常用于要求比较严格的实时系统中, 以及对性能要求较高的批处理和分时系统中.
2,优先权的类型
(1) 静态优先权
静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变.
一般地,优先权是利用某一范围内的一个整数来表示的,例如,0~7或0~255中的某一整数, 又把该整数称为优先数.只是具体用法各异:有的系统用0表示最高优先权,当数值愈大时,其优先权愈低;而有的系统恰恰相反.
确定进程优先权的依据有如下三个方面:
1.进程类型.(系统进程/用户进程)
2.进程对资源的需求.(需求量的大小)
3.用户要求.(用户进程紧迫程度)
(2) 动态优先权
动态优先权是指在创建进程时所赋予的优先权,可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能.
例如,我们可以规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高.若所有的进程都具有相同的优先权初值,则显然是最先进入就绪队列的进程,将因其动态优先权变得最高而优先获得处理机,此即FCFS算法.
优先权的变化规律可描述为:
由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP.据此,又可表示为:
3,高响应比优先调度算法
由上面的式子可以得到以下结论:
(1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业.
(2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务.
(3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高, 从而也可获得处理机.
该算法照顾了短作业,且不会使长作业长期得不到服务 1. 非抢占式调度算法
为每一个被控对象建立一个实时任务并将它们排列成一轮转队列,调度程序每次选择队列中的第一个任务投入运行.该任务完成后便把它挂在轮转队列的队尾等待下次调度运行.
2. 非抢占式优先调度算法.
实时任务到达时,把他们安排在就绪队列的对首,等待当前任务自我终止或运行完成后才能被调度执行.
3. 抢占式调度算法
1）基于时钟中断的抢占式优先权调度算法.
实时任务到达后,如果该任务的优先级别高于当前任务的优先级并不立即抢占当前任务的处理机,而是等到时钟中断到来时,调度程序才剥夺当前任务的执行,将处理机分配给新到的高优先权任务.
2）立即抢占的优先权调度算法.
在这种调度策略中,要求操作系统具有快速响应外部时间中断的能力.一旦出现外部中断,只要当前任务未处于临界区便立即剥夺当前任务的执行,把处理机分配给请求中断的紧迫任务，实时进程调度，实时进程抢占当前。 1 实现实时调度的基本条件
1-1. 提供必要的信息-就绪时间.
1-2. 开始截止时间和完成截止时间.
1-3. 处理时间.
1-4. 资源要求.
1-5. 优先级.
2. 系统处理能力强
在实时系统中,通常都有着多个实时任务.若处理机的处理能力不够强,则有可能因处理机忙不过来而使某些实时任务不能得到及时处理, 从而导致发生难以预料的后果.假定系统中有m个周期性的硬实时任务,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,系统可调度必须满足下面的限制条件:
当系统不可调度时解决的方法是提高系统的处理能力,其途径有二:
其一仍是采用单处理机系统,但须增强其处理能力, 以显着地减少对每一个任务的处理时间;
其二是采用多处理机系统.假定系统中的处理机数为N,则应将上述的限制条件改为:
3. 采用抢占式调度机制
当一个优先权更高的任务到达时,允许将当前任务暂时挂起,而令高优先权任务立即投入运行.采用这种方式去满足那些开始截止时间即将到来的任务.?
4. 具有快速切换机制
应具有的能力:
(1) 对外部中断的快速响应能力.为使在紧迫的外部事件请求中断时系统能及时响应,要求系统具有快速硬件中断机构,还应使禁止中断的时间间隔尽量短,以免耽误时机(其它紧迫任务).?
(2) 快速的任务分派能力.在完成任务调度后,便应进行任务切换.为了提高分派程序进行任务切换时的速度, 应使系统中的每个运行功能单位适当的小,以减少任务切换的时间开销.实时调度实例
一, 最早截止时间优先算法(EDF)
EDF算法用于非抢占调度方式
优先级:根据任务的开始截止时间来确定任务的优先级.
二,最低松弛优先算法(LLF)
例如:系统中有两个周期性实时任务A和B,任务A要求每20ms执行一次,执行时间为10ms;任务B要求每50ms执行一次,执行时间为25ms.这样可知A和B每次必须完成的时间和开始截止时间如图所示
优先级:根据任务紧急程度来确定任务优先级
A和B任务每次必须完成的时间
A1 (10) A2 (30) A3(50) A4 (70) A5(90) A6 (110) A7(130) A8(150)
0 、10、 20、 30 、40、 50 、60、 70、 80 、90 、100 、110、 120、130、 140、 150
B1(25) B2(75) B3(125)
A和B任务每次必须开始的时间
时间(ms) A截止时间 B截止时间 调度对象
0 A1(10) B1(25) A1
10 A2(20) B1(15) B1
30 A2(0) B1(15) A2
40 A3(10) B1(5) B1
45 A3(5) B2(30) A3
55 A4(15) B2(20) B2
70 A4(0) B2(20) A4
松弛度
松弛度
( 20-10-0 ) ( 50-25-0 )
(40-10-10 ) ( 50-25-10 )
(40-10-30) (50-5-30)
(60-10-40) (50-5-40)
(60-10-45) (100-25-45)
(80-10-55) (100-25-55)
(80-10-70) (100-10-70 )
3.4.1 多处理器系统的类型
(1) 紧密耦合(Tightly Coupted)MPS.
这通常是通过高速总线或高速交叉开关,来实现多个处理器之间的互连的.它们共享主存储器系统和I/O设备,并要求将主存储器划分为若干个能独立访问的存储器模块,以便多个处理机能同时对主存进行访问.系统中的所有资源和进程,都由操作系统实施统一的控制和管理.
3.4 多处理机系统中的调度
从处理器之间耦合的紧密程度上划分:
松散耦合(Loosely Coupled)MPS.
在松散耦合MPS中,通常是通过通道或通信线路,来实现多台计算机之间的互连.每台计算机都有自己的存储器和I/O设备,并配置了OS来管理本地资源和在本地运行的进程.因此,每一台计算机都能独立地工作, 必要时可通过通信线路与其它计算机交换信息,以及协调它们之间的工作.
根据系统中所用处理器的相同与否划分:
(1) 对称多处理器系统SMPS. 在系统中所包含的各处理器单元,在功能和结构上都是相同的,当前的绝大多数MPS都属于SMP系统.例如,IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的.?
(2) 非对称多处理器系统.在系统中有多种类型的处理单元,它们的功能和结构各不相同,其中只有一个主处理器,有多个从处理器：
1. 对称多处理器系统中的进程分配方式
在SMP系统中,所有的处理器都是相同的,因而可把所有的处理器作为一个处理器池(Processor pool),由调度程序或基于处理器的请求,将任何一个进程分配给池中的任何一个处理器去处理.在进行进程分配时,可采用以下两种方式之一.
1) 静态分配(Static Assigenment)方式
2) 动态分配(Dynamic Assgement)方式?
3.4.2 进程分配方式
静态分配(Static Assigenment)方式
一个进程从开始执行直到完成,都被固定分配到一个处理器上去执行.
2) 动态分配(Dynamic Assgement)方式
系统中设置有公共的就绪队列.分配进程时,可以将进程分配到任何一个处理器上.
动态分配方式的主要优点是消除了各处理器忙闲不均的现象
2. 非对称MPS中的进程分配方式?
对于非对称MPS,其OS大多采用主—从(Master-Slave)式OS,即OS的核心部分驻留在一台主机上(Master),而从机(Slave)上只是用户程序,进程调度只由主机执行.每当从机空闲时,便向主机发送一索求进程的信号,然后,便等待主机为它分配进程.在主机中保持有一个就绪队列,只要就绪队列不空,主机便从其队首摘下一进程分配给请求的从机.从机接收到分配的进程后便运行该进程,该进程结束后从机又向主机发出请求.
缺点:对主机要求高,出现故障导致整个系统瘫痪
1. 自调度(Self-Scheling)方式
1) 自调度机制?
在系统中设置有一个公共的进程或线程就绪队列, 所有的处理器在空闲时,都可自己到该队列中取得一进程(或线程)来运行.在自调度方式中,可采用在单处理机环境下所用的调度算法,如先来先服务(FCFS)调度算法,最高优先权优先(FPF)调度算法和抢占式最高优先权优先调度算法等.
3.4.3 进程(线程)调度方式
2) 自调度方式的优点?
1,系统中的公共就绪队列可按照单处理机系统中所采用的各种方式加以组织;其调度算法也可沿用单处理机系统所用的算法,即很容易将单处理机环境下的调度机制移植到多处理机系统中
2,只要系统中有任务(公共就绪队列不空)就不会出现处理机空闲的情况,也不会发生处理器忙闲不均的现象,因而有利于提高处理器的利用率.
3)自调度方式的缺点
3.4.4进程调度过程
1、进程名：作为进程的标识。
指针：进程按顺序排成循环链表，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址。
2、要求运行时间：假设进程需要运行的单位时间数。
已运行时间：假设进程已经运行的单位时间数，初值为0。
状态：可假设有两种状态，就绪状态和结束状态。进程的初始状态都为就绪状态。
3、每次运行所设计的处理器调度程序调度进程之前，为每个进程任意确定它的要求运行时间。
4、此程序是模拟处理器调度，因此，被选中的进程并不实际启动运行，而是执行
已运行时间+1
来模拟进程的一次运行，表示进程已经运行过一个单位时间。
.5、在所设计的程序中应有显示或打印语句，能显示或打印每次被选中的进程名以及运行一次后进程队列的变化。
6、为进程任意确定要求运行时间，运行所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
7、设有一个就绪队列，就绪进程按优先数（优先数范围0－100）由小到大排列（优先数越小，级别越高）。当某一进程运行完一个时间片后，其优先级应下调（如优先数加2或3）。
8、例如一组进程如下表： 进程名 A B C D E F G H J K L M 到达时间 0 1 2 3 6 8 12 12 12 18 25 25 服务时间 6 4 10 5 1 2 5 10 4 3 15 8

5. 基于优先数的时间片轮转调度算法调度处理器

没有完全符合的,但是差不多的,你自己改改吧!
#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;
}