題目二：處理機(jī)調(diào)度—實(shí)時(shí)調(diào)度算法EDF和RMS

1、目錄一 .設(shè)計(jì)目的 ?2二 .設(shè)計(jì)容 ?2三 .設(shè)計(jì)準(zhǔn)備 ?2四 .設(shè)計(jì)過程 ?3五 .設(shè)計(jì)結(jié)果并分析 ?12六 .系統(tǒng)的結(jié)構(gòu)，原理框圖和模塊等的詳細(xì)說明?14七 .用戶使用說明書和參考資料 ?15八 .設(shè)計(jì)體會(huì) ?16一設(shè)計(jì)目的深入理解處理機(jī)調(diào)度算法，了解硬實(shí)時(shí)概念，掌握最早截止期優(yōu)先調(diào)度算法。 EDF(Earliest Deadline First)和速率單調(diào)調(diào)度算法RMS（Rate Monotonic Scheduling ）的可調(diào)度條件，并能在可調(diào)度情況下給出具體調(diào)度結(jié)果。二 設(shè)計(jì)容在 Linux 環(huán)境中采用用戶級(jí)線程模擬實(shí)現(xiàn)EDF和 RMS兩種實(shí)時(shí)調(diào)度算法。給定一組實(shí)時(shí)任務(wù)， 按照

2、EDF算法和 RMS算法分別判斷是否可調(diào)度。在可調(diào)度的情況下，創(chuàng)建一組用戶級(jí)線程，分別代表各個(gè)實(shí)時(shí)任務(wù)，并按算法所確定的調(diào)度次序安排各個(gè)線程運(yùn)行，運(yùn)行時(shí)在終端上畫出其 Gantt 圖。為避免圖形繪制沖淡算法，Gantt 圖可用字符表示。三 設(shè)計(jì)準(zhǔn)備（理論、技術(shù)）1.EDF算法和 RMS算法的可調(diào)度條件及調(diào)度原則。（ 1）EDF為可搶占式調(diào)度算法，其調(diào)度條件為：sum（ci/ti ） 1（ 2）RMS算法為不可搶先調(diào)度算法，其調(diào)度條件為：sum（ci/ti ） n（exp（in （2）/n ）-1 ）2. 在 linux 環(huán)境中創(chuàng)建用戶級(jí)線程的函數(shù)。（1）創(chuàng)建用戶級(jí)線程的庫函數(shù)為：Int pth

3、read_creat（pthread_t *THREAD，Pthread_attr_t *ATTR，Void * （*START_ROUTINE）（ void* ），Void *ARG）pthread_creat（tid ，NULL，func ，arg ）；其中第一個(gè)參數(shù)是 pthread_t 型的指針，用于保存線程 id ；第二個(gè)參數(shù)是 pthread_attr_t 的指針，用于說明要?jiǎng)?chuàng)建的線程的屬性， NULL 表示使用缺省參數(shù)； 第三個(gè)參數(shù)指明了線程的入口， 是一個(gè)只有一個(gè)（void * ）參數(shù)的函數(shù)；第四個(gè)參數(shù)是傳給線程入口函數(shù)的參數(shù)。四 設(shè)計(jì)過程（設(shè)計(jì)思想、代碼實(shí)現(xiàn)）（1）實(shí)時(shí)任務(wù)用

4、 task 數(shù)據(jù)結(jié)構(gòu)描述，設(shè)計(jì)四個(gè)函數(shù)：Select_proc（）用于實(shí)現(xiàn)調(diào)度算法，被選中任務(wù)執(zhí)行 proc（），在沒有可執(zhí)行任務(wù)時(shí)執(zhí)行 idle（），主函數(shù) main（）初始化相關(guān)數(shù)據(jù)，創(chuàng)建實(shí)時(shí)任務(wù)并對任務(wù)進(jìn)行調(diào)度。（ 2）為模擬調(diào)度算法，給每個(gè)線程設(shè)置一個(gè)等待鎖，暫不執(zhí)行的任務(wù)等待在相應(yīng)的鎖變量上。 主線程按調(diào)度算法喚醒一個(gè)子線程， 被選中線程執(zhí)行一個(gè)時(shí)間單位， 然后將控制權(quán)交給主線程判斷是否需要重新調(diào)度。（3）實(shí)驗(yàn)代碼#include"math.h"#include"sched.h"#include"pthread.h"#inc

5、lude"stdio.h"#include"stdlib.h"#include"semaphore.h"typedef struct/ 實(shí)時(shí)任務(wù)描述char task_id;int call_num;/ 任務(wù)發(fā)生次數(shù)int ci;/任務(wù)處理時(shí)間int ti;/任務(wù)發(fā)生周期int ci_left;int ti_left; /record the reduction of ti ciint flag;/ 任務(wù)是否活躍 ,0否，2 是int arg;/參數(shù)pthread_t th;/任務(wù)對應(yīng)線程task;void proc(int *arg

6、s);void *idle();int select_proc(int alg);int task_num=0;int idle_num=0;intalg;/ 所選算法，1 forEDF，2 for RMSint curr_proc=-1;int demo_time=100;/ 演示時(shí)間task *tasks;pthread_mutex_t proc_wait10; /the biggest number of taskspthread_mutex_t main_wait,idle_wait;float sum=0;pthread_t idle_proc;int main(int argc,c

7、har *argv)pthread_mutex_init(& main_wait , NULL);pthread_mutex_lock(& main_wait);/ 下次執(zhí)行l(wèi)ock等待pthread_mutex_init(& idle_wait , NULL);pthread_mutex_lock(& idle_wait);/下次執(zhí)行l(wèi)ock等待printf("Please input number of real time task:n");int c;scanf("%d",& task_num);/任務(wù)數(shù)ta

8、sks=(task *)malloc(task_num *sizeof(task);while(c=getchar()!='n'&& c!=EOF);/ 清屏int i;for(i=0 ; i<task_num ; i+)pthread_mutex_init(& proc_waiti , NULL);pthread_mutex_lock(& proc_waiti);for(i=0;i<task_num;i+)printf("Pleased input task id,followed by Ci and Ti:n"

9、); scanf("%c,%d,%d,",&tasksi.task_id,& tasksi.ci,& tasksi.ti);tasksi.ci_left=tasksi.ci;tasksi.ti_left=tasksi.ti;tasksi.flag=2;tasksi.arg=i;tasksi.call_num=1;sum=sum+(float)tasksi.ci / (float)tasksi.ti;while(c=getchar()!='n'&&c!=EOF); / 清屏printf("Please inpu

10、t algorithm,1 for EDF,2 for RMS:"); scanf("%d",&alg);printf("Please input demo time:");scanf("%d",& demo_time);double r = 1;/EDF 算法，最早截止期優(yōu)先調(diào)度if(alg = 2)/RMS 算法，速率單調(diào)調(diào)度r=(double)task_num)*(exp(log(2)/(double)task_num)-1);printf("r is %lfn",r);if(sum

11、>r) /綜合EDF和RMS算法任務(wù)不可可調(diào)度的情況/不可調(diào)度printf("(sum=%lf>r=%lf),not schedulable!n",sum,r);exit(2);/ 創(chuàng)建閑逛線程pthread_create(& idle_proc , NULL , (void*)idle , NULL);for(i=0 ;i<task_num ;i+)/ 創(chuàng)建實(shí)時(shí)任務(wù)線程pthread_create(&tasksi.th, NULL, (void*)proc, &tasksi.arg);for(i=0;i<demo_time;

12、i+)int j;if(curr_proc=select_proc(alg)!=-1)/ 按調(diào)度算法選擇線程pthread_mutex_unlock(&proc_waitcurr_proc);/ 喚醒pthread_mutex_lock(&main_wait);/主線程等待else/無可運(yùn)行任務(wù)，選擇閑逛線程pthread_mutex_unlock(&idle_wait);pthread_mutex_lock(&main_wait);for(j=0;j<task_num;j+)/Ti-,直至為 0 時(shí)開始下一周期if(-tasksj.ti_left=0)t

13、asksj.ti_left=tasksj.ti;tasksj.ci_left=tasksj.ci;pthread_create(&tasksj.th,NULL,(void*)proc,&tasksj.arg );tasksj.flag=2;printf("n");sleep(10);void proc(int *args)while(tasks*args.ci_left>0)pthread_mutex_lock(&proc_wait*args); /等待被調(diào)度if(idle_num!=0)printf("idle(%d)",

14、idle_num);idle_num=0;printf("%c%d",tasks*args.task_id,tasks*args.call_num);tasks*args.ci_left-;/ 執(zhí)行一個(gè)時(shí)間單位if(tasks*args.ci_left=0)printf("(%d)",tasks*args.ci);tasks*args.flag=0;tasks*args.call_num+; /pthread_mutex_unlock(&main_wait);/ 喚醒主線程;void *idle()while(1)pthread_mutex_lo

15、ck(&idle_wait);/ 等待被調(diào)度printf("->");idle_num+;/空耗一個(gè)時(shí)間單位pthread_mutex_unlock(&main_wait);/ 喚醒主線程;int select_proc(int alg)int j;int temp1,temp2;temp1=10000;temp2=-1;if(alg=2)&&(curr_proc!=-1)&&(taskscurr_proc.flag!=0)return curr_proc;for(j=0;j<task_num;j+)if(task

16、sj.flag=2)switch(alg)case 1:/EDF 算法if(temp1>tasksj.ci_left)temp1=tasksj.ci_left;temp2=j;case 2:/RMS 算法if(temp1>tasksj.ti)temp1=tasksj.ti;temp2=j;return temp2; /return the selected thread or task number ;五 設(shè)計(jì)結(jié)果并分析六系統(tǒng)的結(jié)構(gòu)、原理框圖和模塊等的詳細(xì)說明最早截止期優(yōu)先調(diào)度優(yōu)先選擇完成截止期最早的實(shí)時(shí)任務(wù)。對于新到達(dá)的實(shí)時(shí)任務(wù)，如果完成截止期先于正在運(yùn)行任務(wù)的完成截止期，則重新分配處理器，即剝奪。最早截止期優(yōu)先調(diào)度結(jié)果（EDF算法）Gantt 圖a1b1a2b1a3b2a4b2a5.01020304555607090100速度單調(diào)調(diào)度于1973 年提出，面向周期性實(shí)時(shí)任務(wù)，屬于非剝奪式調(diào)度的疇。 速率單調(diào)調(diào)度將任務(wù)的周期作為調(diào)度參數(shù)，其發(fā)生頻率越高。則調(diào)度級(jí)別越高。速率單調(diào)調(diào)度結(jié)果（RMS算法） Gantt 圖a1b1c1a2b2a3.a4 b3 c202060160180220240300320360460七 用戶使用說明書和參考資料參考文獻(xiàn)：左萬歷，周長林，濤編著計(jì)算機(jī)操作系統(tǒng)教程徐英慧，馬忠梅，王磊，王琳編著ARM9嵌入式系統(tǒng)