優先順序演算法設計思路

㈠ 分別用隊列和優先順序隊列分支限界法解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;
}