ѧ
JOURNAL OF SOFTWARE 
1999 10 5 Vol.10 No.5 1999



ȴĶýȺԴ
ռѧ
ժҪ ڷֲʽýϵͳȴԼȺԴ.ͨ ȴƫϵ,׼̬ȸ,㷨QNES(quasi-normality EDFscheduler).㷨PCP(priority ceiling protocol)SRP(stack resour ce policy)ЭʹԴ,ռʽܴȴԼͷʹԴص,ʺϵϵͳý.
ؼʡȴ,׼̬,Դ,PCP(priority ceiling protocol),SRP(stack resource policy).
ͼšTP316
Scheduling Tasks with Precedence Constraints and Shared Resource for Multimedia Streams
ZHANG Zhan-junYANG Xue-liang
Department of Computer ScienceGraduate School of Univers ity of Science and Technology of ChinaBeijing100039
AbstractSome issues of scheduling tasks with precedence constraints and shared resource are discussed in this paper. The authors present the scheduling algorithm QNES ( quasi-normalityEDFscheduler) by means of defining the notion of quasi- normality and making consistency of precedence constraints among tasks and parti al order on tasks. QNES can access shared resource based on PCP (priority ceilin g protocol) or SRP (stack resource policy) protocols, and has characters of preemption, dealing with precedence constraints among tasks and accessing sh ared resource, and is suitable to uni-processor systems.
Key wordsScheduling tasks with precedence constraints, quasi-normality, shared resource, PCP (priority ceiling protocol), SRP (stack resource policy).
ڷֲʽýϵͳ,֤ýķ(quanlity of service,QoS) Ҫ,ҲԴĿ.ýΪԴҪɲ,Ա ֤QoSҪ1.ýһƵƵɼѹ緢͡ աѹŵȵ.ڵýϵͳ,ȴ򡢷ʹԴ ص2.еĶý㷨,(early deadline first, EDF)(rate monotonic,RM)3ݺͶý糵(distributed m ultimedia scheduling algorithm,DMSr)1ݵȶǶ㷨,ʺ ɢڶϵͳĻ.Դʵķ,ȼЭ(priority ceilin g protocol,PCP)4ݺջԴ(stack resource policy,SRP)5 ҪҲǶ.ǶڵԵĶýϵͳ,Ǽڵϵ, Щ㷨.ʵʱϵͳܹȴ㷨,MAA(module allocation algorithm)㷨6ݡEDF㷨RM㷨7,Ƿռʽ,Ϊ ռʽȴдϵʹüЩ,Ӧõֲʽýϵͳо ,ѱ֤ӦõQoS.İ֮ȴͬһƫϵһ,չ ף8ἰ̬׼̬,չף9ἰĽڸȴԼ ,˻EDFȵ㷨QNES(quasi-normalityEDFscheduler). ȴԼʹԴ,ռʽ㷨,ʺϵýϵͳ.
Ŀǰ,㷨ʺϷֲʽýϵͳ,,ռʽEDFռʽRM3ݡ ռʽDMSr1ݡռʽEDFͷռʽRM7ݵ.DMSr㷨ܲС ;EDF㷨ɵȻ϶,ϴ;RM㷨֮1, Ƕǵȶ.GareyEDF㷨չ˵ȴ5,, Ƿռʽ.K.NahrstedtOMEGAϵͳģз˵ϵͳȵȺ, ʱƬ㷨2,ҲǷռʽ㷨.HuMAA㷨6 ͼʽ֮ȴ,Ƿռʽ.Դ,Sha PCPЭ4,BakerSRPЭ5,,ֻǿǶ Դ.ڷֲʽýԴ,ף9ݸ˻ڽڷʽԴ, I/O--CPU-֮Դƽⷽ,֤ȶý. 
Ƚ˵ϵͳжýȴ,չԴڵĸӦȴ ȣȻȴԼͬһƫϵһ,׼̬, 㷨QNES,㷨ļ㸴ӶȣŽԴPCPSRPЭ,֤EDF ĿԺͿɵ,˲QNES㷨ĵܺͿɵʵ ȫܽ.
1ȴ
ΪЧзֲʽýԴ,ף9ݶ˽ڵĸ.ڽڵĶ,ԺͶԵ,չ,ʹ֮ȴԼ.
1. һֲʽýSi6(i,Ui,Gi, Bi,di,gi).Цi,Bi,di,giֱʾýʡI/O 紦,ף9.
UiSim̼߳T1,T2,...,Tm,ȴϵ. ÿΪTj (pj,cj,dj,prj,rj,sj,fj,bj),j=1,2,...,m.pjΪ ִ,cjΪִʱ,djΪ,prjΪִʱ̬ȼ,rjΪ ʱ,sjΪʼִʱ,fjΪʱ,bjΪԴȴʱ.Ϊý ڵԵ,,djpj.,һpj=30ms,rj=100 ms,sj=100.2ms,dj=sj+pj=130.2ms.
GiΪѭͼ,Uiȴ.UiеΪGiеĽڵ, TjTk,ͼдһӽڵjڵkĻ.
,ƵƵĴ,UiеһƵݲɼѹ֡ ͡աƴװ֡ѹƵŵ.ݻϵͳĹԴ.ڵ ϵͳи֮ȴͼ1ʾ.ϵͳnƵ,nͬĽ.

ף2ָڵϵͳ,ý֮ȴԼ.Ϊ˵ ֮ȴȵҪ,Ƶ֡Ͱ֮ȺΪ.ͼ 2ʾ,ִʱΪ14ms,Ϊ30msִʱΪ4ms,Ϊ7.5ms. ʹõȶEDF,RMDMSr㷨ʱ.ûƵ֮֡ǰͽ ˰,ʹеİʹ.

2׼̬
2.1׼̬
ദȴĵȶEDF㷨.ΪEDF㷨Ƚϼ򵥡,кܿɵ ɵ,,Ƕ̬ȼֵ,䵽 .ͬ,ǵоҲǻEDF㷨е.ף8,Garey ˾ȴԼ,EDF̬(normality).
2. һȼUi,,Ti ,Tjti,tjStjSti djdiris tj,stjtjĿʼʱ,diTi,riTiĵʱ, EDF̬.
ýԵ,̬߰ȷ,Ƕýƫϵ.
3. ڶý,һƫϵ,TiTj rirjdidj,ri,diTiĵʱ,ô,Ƶʱr dͬƫϵһµ,TiTjƫϵ.
1. ڶý,ĵʱͬƫ ϵһ,ô,Խڵκ̬Ҳƫϵ.
֤TiTj,ǵʱsj<fi,sjTjĿ ʼʱ,fiTiĽʱ,ƫϵ.TiTjһt i,tj,ʹstj<sti.̬,ɶ2,djdiri>st j.ɵȵ,rjsjstj.ɶ3,rirjdi<dj. Ȼ,Υ.
2. ýEDF̬Ƿռʽ.
֤ɶ2,TiTjEDF̬,е ti,tj,StiStj didjrjsti.ɶ1 ,̬Ҳ,stistjrirj,Tit iִйвܱTjеtjռ.,Ƿռʽ, ִеԪ.
Ϊ˰̬չռʽ,2̬,׼̬( quasi-normality).
4. ڶýUi,,Ti ,Tjдti,tjrirjstjstidjdi,s tjtjĿʼʱ,diTi,riTiĵʱ, EDF׼̬.
3. ýEDF׼̬ռʽ.
֤ͼ3ʾ,ͼеĵ׼̬,̬.TiT jǰִ,ᶪʧ.ʹTiռTj,Ҳ׼̬Ķ,ռ ʽ.ͼ3Ҳ̬Ƿռʽķ.

4. ý̬Ҳ׼̬.
֤Ti,Tjrirj,ti,tj, stj<sti.̬ȵ,djdiri>stj.ڿɵȵ ristj,ri>stj,ֻdjdi,ʵ׼̬ .
ǿ,4ǲ,ͼ3ʾ.
5. ڶý,ĵʱͬƫϵ һ,ô,ҽڵĵ׼̬ʱ,ƫϵ.
֤.κ׼̬,TiTj,ڵʱ sj<fi,sjTjĿʼʱ,fiTiĽʱ,ƫϵ.һԶ3 ,rirjdi<dj,׼̬ȵdjdi.ì.
Ҫ.ڵƫϵ,Ti,Tjrirj, ti,tj,ʼʱstj<sti.Υ׼̬,ǽõd j>di.ζĵʱͬƫϵһµ.,ʹTiTj Ҳܱ֤Ti,Tjƫϵ,Ȼʵ.
2.2EDF׼̬
ɶ5ֻ֪Ҫýһƫϵ,ô׼̬ĵȾܱ֤ ƫϵ.QNES㷨,񵽴ʱͨ޸, ƫϵ,ȻٽEDF.

Quasi-Normality EDF Scheduling Algorithm.
1.QNES()
2.{
3.for i=1 to n  ϵͳn
4.{
5.for j=1 to m һm
6.dj=pj+rj;
7.while (Uiеδ)
8.{
9.j=ȡGiеһڵ㣻
10.if (jδ && jǰѴ)
11.{
12.dj=min({dj}{dk-ck:TjGi Tk})
13.dj=(dj<ǰ) ? dj:dj-;
14.}
15.}
16.}
17.ִEDF㷨;
18.}
㷨12,13мԿ,ֻҪTiTjrirj,ôdidj.13еĦ һСС,ܱ֤didj.,㷨QNESUiе ,Ա֤Giеƫϵ,ȻռʽEDF㷨,ͽȴĵ .EDFռʽ㷨ɲμף3.
6. QNES㷨ļ㸴ӶΪO(nm+nv),nϵͳеĽ,m Uiе,vGiеĻ.
֤QNES㷨ĵ6м㸴ӶΪO(m),12,13м㸴ӶΪ O(v),㷨ĵ3nѭ,㷨ļ㸴ӶΪO(nm+nv).
7. ýn,QNES㷨ĿɵΪ
֤QNES㷨ǵռʽEDF㷨,,QNES㷨Ŀɵ EDF㷨Ŀɵ,,w. nڡÿmϵͳ,ÿͬΪn,EDF ʽͿɵõ.
3ȴԼʹԴ
3.1PCPSRPЭ
,۷ֲʽýϵͳеԴ.ShaȼЭ(PCP), RM㷨ԷʹԴ.ChenLinPCPչӦEDF㷨ʹԴ.PCP Э鶨źŵȼЭͼЭ飺κʱ,źŵSȼc(S) ǰҪźŵȼȼ.һTjҪźŵƼʱ,ֻ еprj>c(SH)ʱܵõ,prjTjȼ,SHǵǰȼ ļźŵ.Ϊ˷ֹķ,һ״νٽ֮ǰ,һ.Bake rһƵЭ--ջԴ(SRP).Ϊ˷ֹ,SRP涨ֱ ǰҪԴﵽʱ,ٽռԴ.
3.2EDF׼̬ȷʹԴ
ChenLinPCPԼBakerSRPʹԴЭʵǽ̬EDFȵĹ Դ,Ƿռʽ.,ǽ׼̬ӦPCP,SRPЭ.
8. ڶý,ҽʱtִе ڼSt={tj:rjtprjpriTi,rirj},EDFڵ׼ ̬.
֤.Ti,Tj,rirj, stjsti.t=stjʱ,prjpri,EDF ,djdi,˵׼̬.
Ҫ.ʱt,һִеTj,rjt.VtǵʱСڵr jļ,TiVt,rirj.Tiһֱϵͳд,δִн ,,ٴһtiִеTjһtj,stj <sti.EDF׼̬,ǵõdjdi,EDFȼ ,prjpri,TjSt.
8˵,һۺʱ뼯St,ֱ֮ǰǲ뿪ϵ.һ Ҳ˵,һڷʹԴʱᱻ,ȴԴ.,ֻҪÿ ʼִʱ,ܲԳǷɵ.
9. ýκʹPCPЭEDFȷʹԴ ׼̬.
֤PCPЭ,ִеڼSt,ʹö8 ͿԵõ.
10. ýκʹSRPЭEDFȷʹԴ ׼̬.
֤SRPЭ,ִеڼSt,ʹö8 ͿԵõ.
11. ڶý,ĵʱͬƫ ϵһµ,ô,κʹPCPSRPЭEDFڵȷʹԴƫ ϵ.
ֱ֤Ӧö910Ͷ5ͿԵó.
11˵,ʹPCP,SRPЭEDFȶý׼̬ص,һ˵, ûEDFQNESʹPCPSRPЭʹԴȴ,Ա֤ ԴʵĴ,ᷢ.Ŀɵ.
12. ný,ÿm߳,,ʹPCPSRPЭQNESȿ .
֤ɶ8ó,ʹԴĶýִʱ ڼStеͣʱ.StϵĶó,Tiͣʱִʱ ʹԴʱ,Ci=ci+bi.ɶ7ɵõ.
4ʵ
ʵ黷100MbpsʽEthernetΪͻ˵̨Pentium/166MMXTM,һ̨ ΪPentium/200MMXTM,SCSIӲ,ALS007,RT-300Ƶ׽(2 5֡/s).WinSockClient/Serverֲʽ,ClientѡWindows95ϵͳ,Server ѡWindows NTϵͳ,QNES㷨VC++4.2,ɵԵƵϵͳṹ,ڵ ȴ.ʵĿǼQNES㷨ܺͶ12ɵЧ .ÿƵڰͼ1ʾȴ8,1ǵйز. ǷֱöʽEDF㷨QNES㷨,ͼ4(a),(b)ʾΪӳٺ ʧ.Կ,QNES㷨ĵԺ,EDFɵӳٺ߶ʧ ȴԼɵ.ڲöʽ,ڵз,ն ò,ݶʧ,Ӵӳ.ϵͳ40sʱ,ӳٳֵ146ms,ʧ 14.Ƿֱ12ڶ̬ϵͳԶ12Ŀɵ˲,ͼ4(c)ʾΪ ɵ仯Ĺϵ.ڵӵ129.2ʱ,ϵͳĿɵ ʼ½.ӵ12ʱ,ϵͳɵ½75%.

1Ƶ

(ms)ִʱ( ms)ʱ(ms)
Ƶɼ400.40.05
ѹ400.40.10
֡200.20.10 
100.10.05
100.10.05
֡ƴ200.20.10 
ѹ400.40.10 
Ƶ400.40.05

5 
ϵͳжýȴԼԴص.Ŀǰĵ㷨һǻ Եռʽ㷨.ʵʱϵͳܴȴԼĵȴǷռʽ, Բ.ԴPCPSRPЭҲǻڷռʽȵ.Ļڽڵģ, ֮ȴϵͬƫϵһ,׼̬;ȴԼռ ʽȺԴϵһQNES㷨,ͨ޸ĵߴﵽƫϵ,ʵ EDF׼̬,֤ȴϵ.Դ,֤QNES㷨 ʹԴ,֤ķʴ.QNESĿɵִʱ䡢ں ԴĴС.ʵ,QNES㷨ȴЧ,ɵӽֵ, Ӧڵý.Ŀǰ,һ㷨ڹҿƼƼĿ--ѧ ýϵͳӦ.

оõȻѧ͹ҿƼصƼĿר.
ռ,1967,ʿ,ʦ,ҪоΪýͨ,ֲʽý .
ѧ,1936,,ʿʦ,ҪоΪֲʽϵͳ, ý,CSCW.
ͨѶϵˣռ, 100039,йѧѧоԺѧϵ
ߵλйѧѧоԺѧϵ100039
ο
[1]ռ,ѧ.һ޶ķֲʽý糵㷨.ѧ,1999,2 2(1):2430
  (Zhang Zhan-jun, Yang Xue-liang. A jitterless pinwheel scheduling algorithm for  distributed multimedia. Chinese Journal of Computers, 1999,22(1):2430)
[2]Nahrstedt K, Smith J M. The QoS broker. IEEE Multimedia, 1995,2(1): 4051
[3]Nahrstedt K, Steinmetz R. Resource management in networked multimedia syste ms. IEEE Computer,1995,28(5):5263
[4]Chen M, Lin K. Dynamic priority ceilings: a concurrency control protocol fo r real-time systems. Journal of Real-Time Systems, 1990,12(2):108120
[5]Baker T P. Stack-based scheduling of realtime processes. Journal of Real- Time Systems, 1991,12(3):145154
[6]Hou Chao-ju. Allocation of periodic task modules with precedence and deadl ine constrains in distributed real-time systems. In: IEEE ed. IEEE Real-Time S ystem Symposium. New York: Academic Press, 1992. 146155
[7]Stankovic J A, Spuri M et al. Implication of classical schedu ling results for real-time systems. IEEE Computer, 1995,28(6):1625
[8]Garey M R, Johnson D S et al. Scheduling unit-time tasks wit h arbitrary release times and deadlines. SIAM Journal Computing, 1981,10(2):112 
[9]ռ,ѧ,ž.ڽڵķֲʽýԴ.ѧ,1998,21(11):970979 
(Zhang Zhan-jun, Yang Xue-liang, Zhang Jing. Based sessionresour cemanagement for  distributed multimedia. Chinese Journal of Computers, 1998,21(11):970979)
1998-03-27յԭ,1998-06-12յ޸ĸ
