优先级算法设计思路

㈠ 分别用队列和优先级队列分支限界法解0—1背包问题

利用优先级分支限界法设计0/1背包问题的算法，掌握分支限界法的基本思想和算法设计的基本步骤，注意其中结点优先级的确定方法，要有利于找到最优解的启发信息。

要求：设计0/1背包问题的分支限界算法，利用c语言（c++语言）实现算法，给出程序的正确运行结果。

注意：
1. 把物品按照单位体积的价值降序排列；
2. 构造优先级分支限界法的状态空间树，共n层，第i层每个节点的两个分支分别代表第i个物品的取和不取；
3. 节点上需要保存的值有：S代表已装入背包的物品的总体积，V代表已装入背包的物品的总价值，u代表当前节点的上界，计算公式如下：
u=V+（C-S）（vi+1/si+1）
其中C是背包的总容积，vi+1代表第i+1个物品的价值，si+1代表第i+1个物品的体积。
4. 选择适当的数据结构（如最大堆，或者基本的线性数组）实现算法，输出最后结果。

㈡ css优先级计算规则

梳理这部分是因为在使用组件模式开发h5应用会出现组件样式修改未生效的问题，在解决样式修改的问题前，需要理清楚CSS样式生效的优先级。样式根据引入和声明需要分开介绍，分为 引入样式优先级 和 声明样式优先级 。

引入样式优先级

引入样式优先级一般是在外部样式、内部样式、内联样式之间应用同一个样式的情况是使用， 优先级如下：

外部样式 | 内部样式 < 内联样式

外部样式 和 内部样式 ，最后出现的优先级最高，例如：

<!-- 内联样式 --><spanstyle="color:red;">Hello</span><styletype="text/css">/* 内部样式 */h3{color:green;}</style><!-- 外部样式 style.css --><linkrel="stylesheet"type="text/css"href="style.css"/>

因此，对于一些重置的样式集，比如 normalize.css/reset.css 必须写在所有样式的前面。

PS: 没有外联样式， 参考 。

声明样式优先级

1. 大致的优先级

一般来说满这个规则：

继承不如指定

!important > 内联 > ID > Class|属性|伪类 > 元素选择器

:link、:visited、:hover、:active按照LVHA（LoVe HAte）顺序定义

上面是优先级算法反映出的大致结果，在一般的开发中熟记即可。如果需要进一步研究原理，则了解下优先级算法。

2. 优先级算法

选择器的特殊性值分为四个等级，如下：

等级标签内选择符ID选择符Class选择符/属性选择符/伪类选择符元素选择符

示例<span style="color:red;">#text{color:red;}.text{color:red;} [type="text"]{color:red}span{color:red;}

标记位x,0,0,00,x,0,00,0,x,00,0,0,x

特点:

每个等级的初始值为0，

每个等级的叠加为选择器出 现的次数相加

不可进位，比如0,99,99,99

依次表示为：0,0,0,0

每个等级计数之间没关联

等级判断从左向右，如果某一位数值相同，则判断下一位数值

如果两个优先级相同，则最后出现的优先级高，!important也适用

通配符选择器的特殊性值为：0,0,0,0

继承样式优先级最低 ，通配符样式优先级高于继承样式

计算示例：

a{color: yellow;} /*特殊性值：0,0,0,1*/

div a{color: green;} /*特殊性值：0,0,0,2*/

.demo a{color: black;} /*特殊性值：0,0,1,1*/

.demo input[type="text"]{color: blue;} /*特殊性值：0,0,2,1*/

.demo *[type="text"]{color: grey;} /*特殊性值：0,0,2,0*/

#demo a{color: orange;} /*特殊性值：0,1,0,1*/

div#demo a{color: red;} /*特殊性值：0,1,0,2*/

生效示例：

<ahref="">第一条应该是黄色</a><!--适用第1行规则--><divclass="demo"><inputtype="text"value="第二条应该是蓝色"/><!--适用第4、5行规则，第4行优先级高--><ahref="">第三条应该是黑色</a><!--适用第2、3行规则，第3行优先级高--></div><divid="demo"><ahref="">第四条应该是红色</a><!--适用第6、7行规则，第7行优先级高--></div>

关于伪类LVHA的解释

a标签有四种状态：链接访问前、链接访问后、鼠标滑过、激活，分别对应四种伪类:link、:visited、:hover、:active；

当鼠标滑过a链接时，满足:link和:hover两个伪类，要改变a标签的颜色，就必须将:hover伪类在:link伪类后面声明；

当鼠标点击激活a链接时，同时满足:link、:hover、:active三种状态，要显示a标签激活时的样式（:active），必须将:active声明放到:link和:hover之后。因此得出LVHA这个顺序。

这个顺序能不能变？可以，但也只有:link和:visited可以交换位置，因为一个链接要么访问过要么没访问过，不可能同时满足，也就不存在覆盖的问题。

在组件中的应用

目前的前端开发为了增加开发效率，会对常用组件进行封装，此外，组件还会添加一些必要的结构样式。但是业务的设计文稿中可不一定按照预先写好的默认样式，需要在开发业务时根据组件的DOM结构修改默认样式，此时会出现样式不生效的问题。

例如下面的结构，如果对Title直接增加样式类，则肯定不会生效，因为Title的DOM结构为两层(组件样式定义规定不能使用ID选择器，且类选择器满足最小标记原则)），故样式最多为0,0,2,x。因此，样式多层标记就可提高自定义样式的优先级，例如下方的SCSS写法。

<Pageclass="test"><Headerclass="test__header"><Navbar><Titleclass="test__header--title">Toolbar</Title></Navbar></Header><Content></Content></Page>

.test{.test__header{.test__header--title{height:100px;}}}

此外，对于Page组件的样式标记策略推荐使用 金字塔形(树形) ，比如上面的SCSS书写，这样可以保证内部自定义样式不会受到外部干扰，减少不必要的麻烦。

链接：https://www.jianshu.com/p/1c4e639ff7d5

㈢ 先来先服务调度算法。 优先级调度算法。 短作业优先调度算法 轮转调度算法 响应比高优先调度算法

你试一下

#include<stdio.h>
//using namespace std;
#define MAX 10
struct task_struct
{
char name[10]; /*进程名称*/
int number; /*进程编号*/
float come_time; /*到达时间*/
float run_begin_time; /*开始运行时间*/
float run_time; /*运行时间*/
float run_end_time; /*运行结束时间*/
int priority; /*优先级*/
int order; /*运行次序*/
int run_flag; /*调度标志*/
}tasks[MAX];
int counter; /*实际进程个数*/
int fcfs(); /*先来先服务*/
int ps(); /*优先级调度*/
int sjf(); /*短作业优先*/
int hrrn(); /*响应比高优先*/
int pinput(); /*进程参数输入*/
int poutput(); /*调度结果输出*/

void main()
{ int option;
pinput();
printf("请选择调度算法（0~4）:\n");
printf("1.先来先服务\n");
printf("2.优先级调度\n");
printf(" 3.短作业优先\n");
printf(" 4.响应比高优先\n");
printf(" 0.退出\n");
scanf("%d",&option);
switch (option)
{case 0:
printf("运行结束。\n");
break;
case 1:
printf("对进程按先来先服务调度。\n\n");
fcfs();
poutput();
break;
case 2:
printf("对进程按优先级调度。\n\n");
ps();
poutput();
break;
case 3:
printf("对进程按短作业优先调度。\n\n");
sjf();
poutput();
break;
case 4:
printf("对进程按响应比高优先调度。\n\n");
hrrn();
poutput();
break;
}
}
int fcfs() /*先来先服务*/
{
float time_temp=0;
inti;
intnumber_schel;
time_temp=tasks[0].come_time;
for(i=0;i<counter;i++)
{
tasks[i].run_begin_time=time_temp;
tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;
tasks[i].run_flag=1;
time_temp=tasks[i].run_end_time;
number_schel=i;
tasks[number_schel].order=i+1;
}
return 0;
}

int ps() /*优先级调度*/
{
float temp_time=0;
inti=0,j;
intnumber_schel,temp_counter;
intmax_priority;
max_priority=tasks[i].priority;
j=1;
while((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].priority>tasks[i].priority)
{
max_priority=tasks[j].priority;
i=j;
}
j++;
} /*查找第一个被调度的进程*/
/*对第一个被调度的进程求相应的参数*/
number_schel=i;
tasks[number_schel].run_begin_time=tasks[number_schel].come_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].order=1;
temp_counter=1;
while (temp_counter<counter)
{
max_priority=0;
for(j=0;j<counter;j++)
{if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if (tasks[j].priority>max_priority)
{
max_priority=tasks[j].priority;
number_schel=j;
}
} /*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
temp_counter++;
tasks[number_schel].order=temp_counter;

}return 0;
}

int sjf() /*短作业优先*/
{
float temp_time=0;
inti=0,j;
intnumber_schel,temp_counter;
float run_time;
run_time=tasks[i].run_time;
j=1;
while((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].run_time<tasks[i].run_time)
{
run_time=tasks[j].run_time;
i=j;
}
j++;
} /*查找第一个被调度的进程*/
/*对第一个被调度的进程求相应的参数*/
number_schel=i;
tasks[number_schel].run_begin_time=tasks[number_schel].come_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].order=1;
temp_counter=1;
while (temp_counter<counter)
{
for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{run_time=tasks[j].run_time;number_schel=j;break;}
}

for(j=0;j<counter;j++)
{if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if(tasks[j].run_time<run_time)
{run_time=tasks[j].run_time;
number_schel=j;
}
}
/*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
temp_counter++;
tasks[number_schel].order=temp_counter;
}return 0;
}

int hrrn() /*响应比高优先*/
{ int j,number_schel,temp_counter;
float temp_time,respond_rate,max_respond_rate;
/*第一个进程被调度*/
tasks[0].run_begin_time=tasks[0].come_time;
tasks[0].run_end_time=tasks[0].run_begin_time+tasks[0].run_time;
temp_time=tasks[0].run_end_time;
tasks[0].run_flag=1;
tasks[0].order=1;
temp_counter=1;
/*调度其他进程*/
while(temp_counter<counter)
{
max_respond_rate=0;
for(j=1;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{respond_rate=(temp_time-tasks[j].come_time)/tasks[j].run_time;
if (respond_rate>max_respond_rate)
{
max_respond_rate=respond_rate;
number_schel=j;
}
}
} /*找响应比高的进程*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].run_flag=1;
temp_counter+=1;
tasks[number_schel].order=temp_counter;
}
return 0;
}
int pinput() /*进程参数输入*/
{ int i;
printf("please input the processcounter:\n");
scanf("%d",&counter);

for(i=0;i<counter;i++)
{printf("******************************************\n");
printf("please input the process of %d th :\n",i+1);
printf("please input the name:\n");
scanf("%s",tasks[i].name);
printf("please input the number:\n");
scanf("%d",&tasks[i].number);
printf("please input the come_time:\n");
scanf("%f",&tasks[i].come_time);
printf("please input the run_time:\n");
scanf("%f",&tasks[i].run_time);
printf("please input the priority:\n");
scanf("%d",&tasks[i].priority);
tasks[i].run_begin_time=0;
tasks[i].run_end_time=0;
tasks[i].order=0;
tasks[i].run_flag=0;
}
return 0;
}
int poutput() /*调度结果输出*/
{
int i;
float turn_round_time=0,f1,w=0;
printf("name number come_time run_timerun_begin_time run_end_time priority order turn_round_time\n");
for(i=0;i<counter;i++)
{
f1=tasks[i].run_end_time-tasks[i].come_time;
turn_round_time+=f1;
w+=(f1/tasks[i].run_time);
printf(" %s, %d, %5.3f, %5.3f, %5.3f, %5.3f, %d, %d,%5.3f\n",tasks[i].name,tasks[i].number,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,tasks[i].order,f1);
}
printf("average_turn_round_timer=%5.2f\n",turn_round_time/counter);
printf("weight_average_turn_round_timer=%5.2f\n",w/counter);
return 0;
}

㈣ 最短作业优先算法

以下是最短作业优先算法

最短作业优先调度算法是对预计执行时间短的作业（进程）优先分派处理机，通常后来的短作业不抢先正在执行的作业。这种算法称为这种算法会根据作业长短，也就是作业服务时间的多少来调度作业，服务时间短的会被优先调度执行。

通常情况下，对于简单的时间触发式调度器来说，待命任务列表的数据结构的设计要尽可能缩短最坏情况下，程序在调度器关键部分的执行时间，以防止其他任务一直在待命列表中，无法及时执行。

因此，在这种调度器中，应尽可能避免抢占式任务，甚至应该关闭调度器之外的所有中断。当然，待命任务列表的数据结构也应根据这个系统需要的最大任务数量做进一步的优化。

㈤ 求一份儿C语言优先级调度算法要求如下

#include "string.h"
#define n 10 /*假定系统中可容纳的作业数量为n*/
typedef struct jcb
{char name[4]; /*作业名*/
int length; /*作业长度，所需主存大小*/
int printer; /*作业执行所需打印机的数量*/
int tape; /*作业执行所需磁带机的数量*/
int runtime; /*作业估计执行时间*/
int waittime; /*作业在系统中的等待时间*/
int next; /*指向下一个作业控制块的指针*/
}JCB; /*作业控制块类型定义*/
int head; /*作业队列头指针定义*/
int tape,printer;
long memory;
JCB jobtable[n]; /*作业表*/
int jobcount=0; /*系统内现有作业数量*/
shele( )
/*作业调度函数*/
{float xk,k;
int p,q,s,t;
do
{p=head;
q=s=-1;
k=0;
while(p!=-1)
{ if(jobtable[p].length<=memory&&jobtable[p].tape<=tape&&jobtable[p].printer<=printer)
{ /*系统可用资源是否满足作业需求*/
xk=(float)(jobtable[p].waittime)/jobtable[p].runtime;
if(q==0||xk>k) /*满足条件的第一个作业或者作业q的响应比小于作业p的响应比*/
{k=xk; /*记录响应比*/
q=p;
t=s;
}/*if*/
}/*if*/
s=p;
p=jobtable[p].next; /*指针p后移*/
}/*while*/
if(q!=-1)
{ if(t==-1) /*是作业队列的第一个*/
head=jobtable[head].next;
else
jobtable[t].next=jobtable[q].next;
/*为作业q分配资源：分配主存空间；分配磁带机;分配打印机*/
memory=memory-jobtable[q].length;
tape=tape-jobtable[q].tape;
printer=printer-jobtable[q].printer;
printf("选中作业的作业名：%s\n",jobtable[q].name);
}
}while(q!=-1);
}/*作业调度函数结束*/

main( )
{char name[4];
int size,tcount,pcount,wtime,rtime;
int p;
/*系统数据初始化*/
memory=65536;
tape=4;
printer=2;
head=-1;
printf("输入作业相关数据(以作业大小为负数停止输入)：\n");
/*输入数据，建立作业队列*/
printf("输入作业名、作业大小、磁带机数、打印机数、等待时间、估计执行时间\n");
scanf("%s%d%d %d %d %d",name,&size,&tcount,&pcount,&wtime,&rtime);
while(size!=-1)
{/*创建JCB*/
if(jobcount<n)p=jobcount;
else { printf("无法再创建作业\n");
break;
}
jobcount++;
/*填写该作业相关内容*/
strcpy(jobtable[p].name,name);
jobtable[p].length=size;
jobtable[p].printer=pcount;
jobtable[p].tape=tcount;
jobtable[p].runtime=rtime;
jobtable[p].waittime=wtime;
/*挂入作业队列队首*/
jobtable[p].next=head;
head=p;
/* 输入一个作业数据*/
printf("输入作业名、作业大小、磁带机数、打印机数、等待时间、估计执行时间\n");
scanf("%s%d%d%d%d%d",name,&size,&tcount,&pcount,&wtime,&rtime);
}/*while*/
shele( ); /*进行作业调度*/
}/*main( )函数结束*/

㈥ 如果让你来设计一个调度算法,你会考虑哪些因素

介绍中间调度？
作业调度，也被称为宏观调度或高级调度，其主要任务是选择在选定的作业的作业分配内存，输入和输出设备和其他必要的储备货币地位的某些原则的外部存储器资源，并建立一个过程，以使工作的过程中，以获得竞争处理器的权利。
B?。进程调度，也被称为微调度或低级别的调度，其主要任务是根据一些策略和方法来选择一个在该准备状态的方法，该处理器被分配给它。
C。提高内存的利用率和系统吞吐量，引入一个的中级调度
作业调度需要进行哪两个决定？
接受的工作，接受了哪些工作。
3。，剥夺抢占式调度方式的原则吗？
时间片原则，B优先的原则; c短作业（进程）的原则，优先
调度方式和调度算法的选择，应遵循的准则？
面向用户的标准周转时间短的响应时间保证在年底的时候，和优先级的标准。
B?。为提高系统吞吐量，系统的标准，处理器的利用率，对各种资源的平衡利用。
为什么多级反馈队列能更好地满足不同用户的需求呢？
终端类型作业的用户终端类型作业用户提交的作业，大部分... 展开

㈦ 算法设计策略有哪些

算法设计策略如下：

1、分治html

分治法的设计思想是，将一个难以直接解决的大问题，分割成k个规模较小的子问题，这些子问题相互独立，且与原问题相同，而后各个击破，分而治之。算法。

5、分支限界

回溯法是对解空间进行深度优先搜索，事实上任何搜索遍整个解空间的算法都可解决问题。因此采用通用图搜索的任何实现做为搜索策略都可解决问题，只要作到穷举便可。除了深度优先搜索以外，咱们还可采用广度优先搜索，而分支限界法则是对解空间进行优先级优先搜索。

㈧ 编译原理简单优先算法分析

优先关系矩阵： 矩阵的行和列都是终结符，矩阵元素是终结符的优先关系。
为什么你的矩阵有非终结符

㈨ 操作系统进程调度算法模拟

第一部分： 实时调度算法介绍

对于什么是实时系统，POSIX 1003.b作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由Donald Gillies提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。

一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普通的 Linux操作系统的进程调度以及各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。最后分析了将Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时Linux是如何解决这些问题的。

1. 实时CPU调度算法分类

各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven scheling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven scheling-SD）、以及基于时间的进程调度算法（Time-driven scheling-TD），下面对这三种调度算法逐一进行介绍。

1.1. 基于优先级的调度算法

基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]：

静态优先级调度算法：

这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。

动态优先级调度算法：

这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中， EDF算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限（Deadline）来分配优先级，具有最近的截止期限的任务具有最高的优先级。

1.2. 基于比例共享调度算法

虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD算法）更为适合。

比例共享调度算法指基于CPU使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成正比。

我们可以通过两种方法来实现比例共享调度算法[Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片。

比例共享调度算法可以分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法（Lottery）等。

比例共享调度算法的一个问题就是它没有定义任何优先级的概念；所有的任务都根据它们申请的比例共享CPU资源，当系统处于过载状态时，所有的任务的执行都会按比例地变慢。所以为了保证系统中实时进程能够获得一定的CPU处理时间，一般采用一种动态调节进程权重的方法。

1.3. 基于时间的进程调度算法

对于那些具有稳定、已知输入的简单系统，可以使用时间驱动（Time-driven:TD）的调度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。

这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有任务需要被执行而CPU却保持空闲的情况。

2. 通用Linux系统中的CPU调度

通用Linux系统支持实时和非实时两种进程，实时进程相对于普通进程具有绝对的优先级。对应地，实时进程采用SCHED_FIFO或者SCHED_RR调度策略，普通的进程采用SCHED_OTHER调度策略。

在调度算法的实现上，Linux中的每个任务有四个与调度相关的参数，它们是rt_priority、policy、priority（nice）、counter。调度程序根据这四个参数进行进程调度。

在SCHED_OTHER 调度策略中，调度器总是选择那个priority+counter值最大的进程来调度执行。从逻辑上分析，SCHED_OTHER调度策略存在着调度周期（epoch），在每一个调度周期中，一个进程的priority和counter值的大小影响了当前时刻应该调度哪一个进程来执行，其中 priority是一个固定不变的值，在进程创建时就已经确定，它代表了该进程的优先级，也代表这该进程在每一个调度周期中能够得到的时间片的多少； counter是一个动态变化的值，它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始，priority的值被赋给 counter，然后每次该进程被调度执行时，counter值都减少。当counter值为零时，该进程用完自己在本调度周期中的时间片，不再参与本调度周期的进程调度。当所有进程的时间片都用完时，一个调度周期结束，然后周而复始。另外可以看出Linux系统中的调度周期不是静态的，它是一个动态变化的量，比如处于可运行状态的进程的多少和它们priority值都可以影响一个epoch的长短。值得注意的一点是，在2.4以上的内核中， priority被nice所取代，但二者作用类似。

可见SCHED_OTHER调度策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个epoch中也会得到自己应得的那些CPU执行时间，另外它也提供了不同进程的优先级区分，具有高priority值的进程能够获得更多的执行时间。

对于实时进程来说，它们使用的是基于实时优先级rt_priority的优先级调度策略，但根据不同的调度策略，同一实时优先级的进程之间的调度方法有所不同：

SCHED_FIFO：不同的进程根据静态优先级进行排队，然后在同一优先级的队列中，谁先准备好运行就先调度谁，并且正在运行的进程不会被终止直到以下情况发生：1.被有更高优先级的进程所强占CPU；2.自己因为资源请求而阻塞；3.自己主动放弃CPU（调用sched_yield）；

SCHED_RR：这种调度策略跟上面的SCHED_FIFO一模一样，除了它给每个进程分配一个时间片，时间片到了正在执行的进程就放弃执行；时间片的长度可以通过sched_rr_get_interval调用得到；

由于Linux系统本身是一个面向桌面的系统，所以将它应用于实时应用中时存在如下的一些问题：

Linux系统中的调度单位为10ms，所以它不能够提供精确的定时；

当一个进程调用系统调用进入内核态运行时，它是不可被抢占的；

Linux内核实现中使用了大量的封中断操作会造成中断的丢失；

由于使用虚拟内存技术，当发生页出错时，需要从硬盘中读取交换数据，但硬盘读写由于存储位置的随机性会导致随机的读写时间，这在某些情况下会影响一些实时任务的截止期限；

虽然Linux进程调度也支持实时优先级，但缺乏有效的实时任务的调度机制和调度算法；它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来，并且它们自身也没有明确的调度机制；

3. 各种实时Linux系统

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大学（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，为了在Linux系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作系统（我们也称之为RT-Linux的实时子系统），而将普通Linux系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通Linux系统中的任务可以通过FIFO和实时任务进行通信。RT-Linux的框架如图 1所示：

图 1 RT-Linux结构

RT -Linux的关键技术是通过软件来模拟硬件的中断控制器。当Linux系统要封锁CPU的中断时时，RT-Linux中的实时子系统会截取到这个请求，把它记录下来，而实际上并不真正封锁硬件中断，这样就避免了由于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。当有硬件中断到来时， RT-Linux截取该中断，并判断是否有实时子系统中的中断例程来处理还是传递给普通的Linux内核进行处理。另外，普通Linux系统中的最小定时精度由系统中的实时时钟的频率决定，一般Linux系统将该时钟设置为每秒来100个时钟中断，所以Linux系统中一般的定时精度为 10ms，即时钟周期是10ms，而RT-Linux通过将系统的实时时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。

RT-Linux实时子系统中的任务调度可以采用RM、EDF等优先级驱动的算法，也可以采用其他调度算法。

RT -Linux对于那些在重负荷下工作的专有系统来说，确实是一个不错的选择，但他仅仅提供了对于CPU资源的调度；并且实时系统和普通Linux系统关系不是十分密切，这样的话，开发人员不能充分利用Linux系统中已经实现的功能，如协议栈等。所以RT-Linux适合与工业控制等实时任务功能简单，并且有硬实时要求的环境中，但如果要应用与多媒体处理中还需要做大量的工作。

意大利的RTAI( Real-Time Application Interface )源于RT-Linux，它在设计思想上和RT-Linux完全相同。它当初设计目的是为了解决RT-Linux难于在不同Linux版本之间难于移植的问题，为此，RTAI在 Linux 上定义了一个实时硬件抽象层，实时任务通过这个抽象层提供的接口和Linux系统进行交互，这样在给Linux内核中增加实时支持时可以尽可能少地修改 Linux的内核源代码。

3.2. Kurt-Linux

Kurt -Linux由Kansas大学开发，它可以提供微秒级的实时精度[KurtWeb] [Srinivasan]。不同于RT-Linux单独实现一个实时内核的做法，Kurt -Linux是在通用Linux系统的基础上实现的，它也是第一个可以使用普通Linux系统调用的基于Linux的实时系统。

Kurt-Linux将系统分为三种状态：正常态、实时态和混合态，在正常态时它采用普通的Linux的调度策略，在实时态只运行实时任务，在混合态实时和非实时任务都可以执行；实时态可以用于对于实时性要求比较严格的情况。

为了提高Linux系统的实时特性，必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率，会引起调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾， Kurt-Linux采用UTIME所使用的提高Linux系统中的时钟精度的方法[UTIMEWeb]：它将时钟芯片设置为单次触发状态（One shot mode），即每次给时钟芯片设置一个超时时间，然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生，但并非一定需要系统时钟频率达到此精度。它利用CPU的时钟计数器TSC (Time Stamp Counter)来提供精度可达CPU主频的时间精度。

对于实时任务的调度，Kurt-Linux采用基于时间（TD）的静态的实时CPU调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。

Kurt -Linux相对于RT-Linux的一个优点就是可以使用Linux系统自身的系统调用，它本来被设计用于提供对硬实时的支持，但由于它在实现上只是简单的将Linux调度器用一个简单的时间驱动的调度器所取代，所以它的实时进程的调度很容易受到其它非实时任务的影响，从而在有的情况下会发生实时任务的截止期限不能满足的情况，所以也被称作严格实时系统（Firm Real-time）。目前基于Kurt-Linux的应用有：ARTS（ATM Reference Traffic System）、多媒体播放软件等。另外Kurt-Linux所采用的这种方法需要频繁地对时钟芯片进行编程设置。

3.3. RED-Linux

RED -Linux是加州大学Irvine分校开发的实时Linux系统[REDWeb][ Wang99]，它将对实时调度的支持和Linux很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

为了提高系统的调度粒度，RED-Linux从RT-Linux那儿借鉴了软件模拟中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时，RED-Linux的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队，并不执行真正的中断处理程序。

另外为了解决Linux进程在内核态不能被抢占的问题， RED-Linux在Linux内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。

RED-Linux的设计目标就是提供一个可以支持各种调度算法的通用的调度框架，该系统给每个任务增加了如下几项属性，并将它们作为进程调度的依据：

Priority：作业的优先级；

Start-Time：作业的开始时间；

Finish-Time：作业的结束时间；

Budget：作业在运行期间所要使用的资源的多少；

通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值，几乎可以实现所有的调度算法。这样的话，可以将三种不同的调度算法无缝、统一地结合到了一起。

㈩ 设计一个按响应比高者优先调度算法实现进程调度的程序。

只帮你写点开头，后面你应该会的
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>

typedef struct node
{
char name[10];
int prio;
int round;
int cputime;
int needtime;
int count;
char state;
struct node *next;
}PCB;
PCB *finish,*ready,*tail,*run,; //队列指针
int N; //进程数

void zhunbei()
{
run=ready; //就绪队列头指针赋值给运行头指针
run->state='G'; //进程状态变为运行态]
ready=ready->next; //就绪队列头指针后移到下一进程
}
//输出标题函数
void output1(char a)
{
if(toupper(a)=='P') //优先级法
cout<<" "<<endl;
cout<<"进程名 占用CPU时间 已运行时间 还要的时间 轮转时间片 状态"<<endl;
}