ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



DRT-UNIXϵͳ*
Ƽİڷ
ժҪǷֲʽʵʱϵͳĺ֮һ.¸ʵʱϵͳȣDRT-UNIXϵͳʵһ㷨㷨ŵ˷.
ؼʡֲʽʵʱϵͳʵʱ񣬵ȣ
ͼšTP316
Task Scheduling in DRT-UNIX System
PANG Li-ping,L,Wen-an HAN Zong-fen
(School of Computer Science and Technology Huazhong University of Science and TechnologyWuhan430074)
AbstractTask scheduling is one of the key problems in distributed real-time systems. The task scheduling in real-time systems is introduced in this paper. Having taken some practical circumstances in DRT-UNIX system into account, an algorithm of task scheduling is proposed and the merits of the algorithm are analysed. 
Key wordsDistributed real-time operating system, real-time task, scheduling.
΢Ӽͼѧķչѱ㷺Ӧڿѧо͹ҵ.ֲʽʵʱϵͳʵʱԡɿԡչԡݴԡԺͲԵȷһʵʱϵͳΪͻǿܹิʵʱӦõҪˣֲʽʵʱϵͳֲ֧ʽʵʱϵͳǵѧоȵ֮һ.DRT-UNIXϵͳƵĻUNIXķֲʽʵʱϵͳ.
ֲʽʵʱϵͳʡؼʵʱԺͿԤ.ʵʱϵͳȷԲ߼ȷйأʱйϵˣʵʱϵͳҪĿϵͳʵʱʱԼصȲִǣʹڸԵ(deadline)֮ǰ.Ƿֲʽʵʱϵͳĺ֮һ֤ڲκ£ֲʽʵʱϵͳһNPѶ1.ĽDRT-UNIXϵͳ.
1 
1. һTpiԪʽ.
Tpi=Ci,Pi,Ri,Di,0<CiDi0<Pi0Ri,
Ciʾʱ䣨ͨ£TpiļʱҪСCiPiʾڣRiʾʱ䣬Diʾ.
TpiĵkִУfk1УʱΪRi+(k-1)*PiʱΪCi;ΪRi+(k-1)*Pi+Di.ÿڵһִпɳΪһʵһִ.
2. һTapjԪʽ.
Tapj=Cj,Rj,Dj,0<Cj0Rj0<Rj+CjDj,
Cjʾʱ䣬Rjʾʱ䣬Djʾ.
3. һʵʱM={Tp1,Tp2,...,Tpi,Tap1,Tap2,...,Tapj}ദȼMһӼMi(i=1,2,...,k)ʹ
a Mi(i=1,2,...,k)ཻң
b ÿһMi(i=1,2,...,k)е񣬵Ƿһִ̨еʱԵʱԼ.
abĵȳΪб֤ȣ2ݣܱ֤ÿʵʱǰɣkΪֵĴĿ.ٶ⣬еԴǿ.ȻĽⲻΨһģӼĸkҲΨһȻϣӼMiĸkԽСԽ.б֤ӼMiĸkСʱͳΪŽ⣬ŽһNPѶ.
2ʵʱϵͳȸ
Ƿֲʽʵʱϵͳпɱȼ֤ʵ壬ڴԽ̵ʽ.ֲʽʵʱϵͳҪǵغܶ࣬еأʹ쳣ӣʧȥʵüֵ.ʵӦУΪ˼⣬ֻǲ.ʱ򶼼ϵͳ֮Դ㹻ģҲ֮临ӵͬ⣬ʱԼ.ڱеҲԴΪǰ.
ʵʱͷ.ͨһʵʱϵͳ񲢴.һ˵ϵͳҪҪռôʱ϶ࣻϵͳΪ˴һЩ¼ִеռôʱ٣ҷĿҲС.ȵĳȵܱ֤ʱԼĻϣٿεȷ񣬲֤. 
ȻֲʽʵʱϵͳҪȵʵʱϵͳӵö࣬ǰԺΪģбҪһµʵʱϵͳ.ʵʱϵͳͨûȼĿռ.ĿǰΪֹȽϳĻȼĵ㷨ȽдԵ㷨:㷨Сɳʱ㷨ʵ㷨.㷨Сɳʱ㷨ڶ̬ȼ㷨ʵ㷨ھ̬ȼ㷨.֤,ڵʵʱϵͳУʵ㷨㷨ֱŵľ̬Ͷ̬ȼ㷨3.һ˵̬ȼ㷨Ҫھ̬ȼ㷨.,ĵȣ㷨ȡõĴϿɸߴ100%ʵ㷨һΪ88%4.Զԣ̬ȼȱ迪󣬶̬ȼ򵥵ö࣬ʵ㷨ŵľ̬ȼ㷨һЩŵ㣬Լӱ仯ͿЧش㷨ȶԡԷӦȼ5ݣԣʵ㷨ڹʵʱоȵ֮һƵڵʵʱϵͳʵ㷨ȵĳֱҪ4.
 ֲʽʵʱϵͳNPѶ⣬˺ܶ˳òͬʽ㷨ѰҴŽ.ڷֲʽʵʱϵͳУͨͬһÿʵͬһ̨У񲻴ڶ̬Ǩƣ̬Ǩƣʵ϶ȡһ־̬Ȳ.µȷ6ݣÿоֲȫֵķֲʽ.
ϵͳеÿڵȷɱڵϵͬʱκνڵ㣬ֲ޷֤÷ʱԼʱύֲʽȣǨƵһʵĽڵȥ.ֲͬ㷨ֻڷǨʱǨƲԵȷͬӶʵе𣬵ܵ˵ĿҲǱȽϴ.
ֲʽʵʱϵͳǹоȵ֮һ.ЩоеĽϵ֣̽ʵʵؽ٣ʵԲǿ;еȫʵõĽǶȳΪʹ򻯣һЩ򵥵ĵ㷨޿ȡ֮;бҪⷽһоһЩʵأΪDRT-UNIXϵͳһЧʵõб֤㷨.
3DRT-UNIXϵͳ
ʵʱϵͳҪĿʱԼǶ˵ʵʱòþ̬.ֻʱԼ£ྲ̬㷨,RMNF7,RMFF7,FFDUF,RMBFȣǶǻʵ㷨ģ㷨һ֮,Ҫڵ.ʵУʵʱӦõС.ĽӦĴҪ.Ϊ˷˵⣬¼˵.
(1) ϵͳͬģ
(2) ÿ̨ϲûڹ̶ȼĿռȲԣ
(3) ύʵʱͷ
(4) ֻϵͳʼ֮ǰһύϵͳйвٽκ
(5) TpiԣRi=0DiPi
(6) ֮临ӵͬ⣬ڵʱ֮ͬͨŵΪһֿǽнϵĶ䵽ͬһ̨ϣ
(7) ͨȵĸϵͳЩƽ̯ļʱȥ,ʱͿϵͳ.
3.1ԷĴ
һֲʽʵʱϵͳУϵͳʼʱȷϵͳйʱпܵ.,Բþ̬ȵķʽ֤ޣڷ,䵽,þ̬ȵķʽѱ֤.ʲôʱ򣬷ʵҪɽڵϵľֲͨ˵Ľ̵ȣȷ֤ޣһѼȴﵽϺõĵܾԱ֤.һָ񣩶̬ǨƵķֲʽʵʱϵͳУһڵ㷢Լܱ֤ĳһޣԽǨƵϵͳһʵĽڵУԱ֤.DRT-UNIXϵͳУڲþ̬ȣǨƣֻòһʩȣȥԴ.
Ȼģֲʽʵʱϵͳһ㶼Ӧñ.һӦñ£ʱCСʱPǿԤ֪ģɸЩϢϵͳڷӦ.ڷʵҲһ.һ˵һӦñ£Ŀֻ࣬һڷԶ輸ڷļʱΪʱCں޾Ϊ񵽴СʱPʱΪ0.
ڷSɼ򵥵رʾΪS=C,PڷSӦĻ˼SȥԴ.ڷSʱΪSTAʼֵΪ0ÿϵͳȵڷSʱ£
(1) STA=STA+C
(2) ڷڵȴյϵͳӦ񣬲STAмȥõʱ䣻
(3) ûзڵȴҲûз񵽴ȴڵȴڵȴȼߵΪTpiϵͳͽ÷ڷSĴʱTpiֱTpiķռϣϵͳSĴʱ꣬ӦشSTAмȥõʱ䣻ȵTpiʱTpiS黹ղõʱ(STA)SⲿʱӦ򡰽ǰȼߵ.
ʵ,ڷSʱ䲢ϵͳÿڷļʱCĴʱCϵͳУSʱָܱһζεʱƬʵϣϵͳÿڷĴʱΪC.ڷSûύеһȲ䴦ȻеķڷSڵĴ.еķɸڷSϵͳеĳһ̨ϴȥԴʵʱ񣨰ͷ񣩵ĵתΪԵһĵȣȼ˵ȱĹϵͳΪĿԤ.
3.2Ĵ
. һ̨һ񣬰ȼӸߵ͵˳,ΪTp1Tp2...,TpnеTpm

Nm=min{k|Wm(k,k*Pm)1},
m1k0x>0㣬ڸôϴڿе.
֤TpjȼΪjjԽСӦȼԽ.ȿһTpi޵
Cj*t/Pj+Ciʱ0,tTp1Tp2...,Tpi-1ִTpiĵ1ִԴۻʱԺTpi+1Tpi+2...,TpnִΪǵȼTpiܹͣռ.ҽCj*t/Pj+Citt<Dnʱܱ֤Tpiĵ1ִޣΪtʱ̴Tpiĵ1ִȼߵ㣻Ȼ,Cj*t/Pj+Ci=tСtֵTpiĵ1ִʱ.ûȼΪiȼļҪʼʱ0iæڽTpiĵ1ִʱ.
Wi(1,Di)1Tpiĵ1ִܵõ֤Wi(1,Pi)1iæڽ.Wi(1,Di)1Wi(1,Pi)>1Tpiĵ1ִܵõ֤ڳʱPiʱiæȴδ.,ǿTpiĵ2ִTpi䣨ʱΪ2*CiΪPi+DiTpiҽWi(2,Pi+Di)1ʱTpiĵ2ִܵõ֤ʱWi(2,2*Pi)>1ͱTpiִ޵ʵϣTpiǰNiִiæڵһ֣ΪܵĴʲᳬ1Niֵ޵ģWi(k,(k-1)*Pi+Di)1Tpiܵõ֤.ƣÿһTpjWj(k,(k-1)*Pj+Dj)1Wj(k,(k-1)*Pj+Dj)1ÿһ޶ܵõ֤Ҳڸôϴڿе.
˵еɸҪѡһȼԣ磬ڡҪԵȷȼҪע⣬ȼһͱֲ.
㷨. 
(1) ŶӣнϵڷǼ˳һλڶеǰ棬ڷǼ˳ڶеĺ棬ź˳ΪTp1Tp2...,Tpm
(2) ʼi=1M=1
(3) TpiMi=i+1
(4) (4.1) j=1
(4.2) TpiĳЩнϵTpiЩнϵȱȵģM=j+1ת(3)jTpiнϵڵĴţ
(4.3) Tpiѷ䵽jϵһڸôϴڿеȣ
Tpiѷ䵽jϵڷǼ˳УΪ1,2,...,n㣺ôСڻ1Wy(k,(k-1)*Py+Dy)1,Tpi䵽jȥת(5)
j=MM=j+1ת(3)j=j+1,ת(4.3)
(5) еѷϣ㷨ֹi=i+1ת(4).
עMֵǵȸĴ.
4㷨ܷ˵
Ϊ˼⣬۶ദʵʱϵͳʱغϣһڣ޾ǱڵĽʱ.ͬ㷨RMNF,RMFF,FFDUF,RMBFȣȣĵ㷨ŵСڣһ̶ϻ㷨Ӧ÷Χ.Ϊ㷨һ޵ʱͨģʵȽϱ㷨RMNF,RMFF,FFDUF,RMBF㷨,:ͬһʵʱñĵ㷨Ĵں漸㷨ĴҲ˵һЩͬ㷨˵ĵ㷨÷Χܲǲ.
ģʵУݱĿʼĶ壬ÿTpi4ʱCi,Pi,ʱRiDi.⣬㷨¼裺Ri=0DiPi.Щ£(ÿ10)еÿһΪ룬ͬʱRMNF,RMFF,FFDUF,RMBF㷨ף6㷨ͱĵ㷨ֱдȷܷе񶼷ϣһȣ͵õĴ.Ƚʾͬһñ㷨Ĵ㷨ҪĶ࣬ʵζű㷨㷨Ƚϣ÷ΧҪһЩҲϺ.
Σ㷨ܹͬʱ֤ͷޣǿϵͳĿԤ.ĿǰУ۵ͬʱ֤ദϵͳͷ⣻е׽רε񣬴Ӷ֤ޣδ漰ȷ⣻⻹һЩоڼѱ֤޵£ڷֻڲӰĵȵǰ跨ӿӦʱ䣬ȴȾԵر֤ޣӶϵͳԤ.ĵ㷨ͬʱ֤ͷޣǿϵͳԤ.
⣬Щ㷨ԣ㷨нϵĵ.ԭǣнϵĶ䵽ͬһ̨.ȷìܡԽǷڲͬĴϣͬʱ֮ͬͨŵȿǽʵĴ.
5
ֲʽʵʱϵͳһܸӵ⣬һõͨý⣬ѧоʱһЩ.һ㷨ĻϣΪDRT-UNIXϵͳһ㷨Ȼ㷨һЩĽ֮ǵػ޵.һоǰ.I/OԼͨŵȴĳԴĵȣԴڸͬϵĵҲо.
*оõԤл.
ͨѶϵˣƼ,人430074,ѧѧ뼼ѧԺ
߼飺ƼŮ1944ڣҪоΪ/ֲʽƣֲʽʵʱϵͳ.
İ1973˶ʿҪоΪֲʽʵʱϵͳUNIXϵͳ.
ڷңŮ1950ڣҪоΪֲʽʵʱϵͳ.
ߵλѧѧ뼼ѧԺ人430074
οף
1Burns A. Scheduling hard real-time systems: a review. Software Engineering Journal, 1991,6(3)116128
2.ֲʽϵͳʵ磬1990
(Liu Jian. Distributed Computer Systems. Beijing: People's Posts & Telecommunications Publishing House, 1990)
3Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of ACM, 1973,20(1):4661
4Lehoczky J P, Sha L, Ding Y. The rate-monotonic scheduling algorithm: exact characterization and average case behavior. In: Doug Locke ed. Proceedings of IEEE Real-time Systems Symposium. Los Alamitos, CA: IEEE Computer Society Press, 1989. 166181
5Sha L, Lehoczky J P, Rajkumar R. Solutions for some practical problems in prioritized preemptive scheduling. In: Kang Shin ed. Proceedings of IEEE Real-time Systems Symposium. 1986. 181191
6Burchard A, Liebeherr J, Oh Y F et al. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Transactions on Computers, 1995,44(12):14291442
7Dhall S K, Liu C L. On a real-time scheduling problem. Operations Research, 1978,26(1):127140
ոڣ1998-06-15޸ڣ1998-09-21
