о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



QoSƵý
ӵʪ¸
ժҪýƵƵһµʵʱӦãҪһͳһĲϵͳ֧ǿʵʱӦã񣩣ͳĲϵͳUNIXWindows NTеĵȲԲܺܺõָ֧Ӧ.һµQoSڴ˻֧ýġQoSʽ㷨㷨ۺϿ˶ýĳɹʺʧԴ޵ǰ£֤ýķ.ͨģ⡢Ƚ϶Ը㷨.
ؼʡQoS ȣ ý
ͼšTP37
TASK SCHEDULING BASED ON QoS CONTROL FOR CONTINUOUS MEDIA SERVICES
ZHANG Yong-Jun, LIU Ye, and CHEN Fu-Jie
(Department of Computer Science, National University of Defense Technology, Changsha 410073)
(Graduate School, Unversity of Science and Technology of China, Beijing 100039)
AbstractContinuous media service is a new kind of real-time applications. It requires that hard and soft real-time tasks should be supported in an integrated operating system framework. But the scheduling policies in traditional OSe.g., UNIX or Windows NTcan't support this application to the best. This paper proposes a new QoS method, based on which a QoS-based heuristic task scheduling algorithm supporting continuous media streams is described. The algorithm takes into account the success ratio and consecutive fail count of multimedia tasks in order to guarantee the quality of all media streams. Finally, simulation and comparison are performed to validate the effectiveness of this algorithm.
Key wordsQoS, task scheduling, continuous media stream
1
ý弼ķչӦõ֧ƽ̨˸ߵҪϵͳеȼʵʱۺ㷨Ľ䷢չıȻ.ȻĿǰʵʱȡõĳɹҪǻǿʵʱԼĵ㷨͵Ȳԣearliest deadline firstEDFrate monotonic schedulingRMS1ԼǵһЩĽΣ23ݵ, 㷨ҲҪǿʵʱhard real-timeӦ.ǿʵʱϵͳУҪеڹ涨ʱޣdeadlineڱɣͿɴѻʧ.
ڶýµʵʱӦУһֵڣûɣɴʧ.磬ƵƵУ֡ĶʧܼʱᵼQoSԵ½˶ýӦϵͳΪʵʱϵͳ.ڶýӦõԣθЧϵͳеĸԴΪע.оڶýϵͳ㷨ΪǰʵʱýҪо.
ĿǰһЩýUNIXNTƽ̨ԶýĵһֱӽUNIXNTеĵ÷ʱȼĵȲԣȻܺܺõشʵʱԼĶý.ף4˻ڴֵmultimedia server algorithms㷨еQoSͨýռCPUʱıʵ֣㷨ӣʵֱȽ.ף5һӦڶýĶ֡ģͣÿʵִʱ䷢仯ʱпܵ´󲿷񶼲ڹ涨ޣdeadline.
һֶԶýQoS·ڴ˻һQoSƵý㷨.ѶýķΪƵƽ33msҪһܱ֡ʱɣΪɹʧ.QoSͨСɹʺʧ.֮ȥ㷨QoSĳɹΪ׼ȷؿ̻ýĳЩýܱȷִжµQoS½.ͨģ⣬ͨķʱEDF㷨Ƚϣ㷨нϺܣʵ.
2ģͼ㷨
ý壨VODϣÿƵƵĴΪһ񣬼һɱȵʵ壬ÿýĴΪCPCΪִʱ䣬PΪִ.ƵĴٶӦﵽ30֡/sÿ֡ĴΪһʵ.ÿʵĴʱ൱Լ33msɣңƵĴΪִΪ33msй.ǰԼʱɵʵΪʵɹΪʵʧ.
ÿýQoSƣ3SQFڶSʵУҪɹQʧܵʵܳF.Q/SΪСɹʣFΪʧ.ȵĳSʵжSQʵʧܣʧܵʵĳֳFΪûýķQoS.
񼯣EDFMLFmin laxity first㷨CPUʣô񼯿ɱȷȣ1.񼯵CPUʳ1ʱٲEDFMLF㷨޷Ԥ.
ڶýӦϵͳУƵƵֻҪһQoSΪǿɽܵ.˵ϵͳؽϴʱQoSķΧڣͨʵĳЩķ֤ϵͳķ.
2.1ģ
ͨϵͳnǿʵʱmýһ̨CPUϣģ£
ϵͳǿʵʱ
ϵͳжý
񶼶Ϊִ.УriΪTiĳʼͷʱ䣻ciΪTi£worst-caseִʱ䣻piΪTiִ.Ti,jΪTiĵjʵTi,jýĳݵλƵеһ֡.ĿǰͨʹõѹTi,jĴʱTi,kͬjk.ˣTi,jͷʱɶΪrij1piʱޣdeadlineɶΪrijpi.Ti,jdeadline֮ǰȷɣΪɹΪʧ.
SiQiΪTiִеSiʵУҪɹQiQi/SiΪTiĳɹ.FiΪTiʧ.ýQoSɲSiQiFiƣҲ˵ԶýĵȱQi/SiĳɹʣҪֹFiʧ.FiֻóɹýƬ.
ϵͳУ뱣֤ǿʵʱʱ.ڶýȼһҪǿʵʱ.
2.2QoSƵĵ㷨
㷨Ļ˼ǵϵͳؽϴʱΪʧܣܵʧֲܷеУԾ֤QoS.νýQoSӳΪִеȼ.
ʽȼֵúH(T)Ϊÿýȼ.QoSH(T)ҪִеĳɹʣҪʧܵ.H(T)Ҫвʾ.H(T)Ķ£

УʾTiѾֵʵʧʾTiSi1ʵܹʧܵĴ.ͳƿͨλĴλʵ.ΪTjSi״̬ƣ1ʾʵִгɹƣ0ʾʧ.(Ti)ʾTiִʵҪԣƵI֡ĴӦP֡B֡ȼ.(Ti)ȡֵΧ01֮.


ͼ1ģʾͼ

£ΪϵɸҪ.µıֵĳɹʧȼֵеҪ.
ǶH(Ti)ֵԽ󣬱ΪǰTiĳʵȼԽ.H(Ti)ļ㹫ʽԵ˵ĳýǰʵҪԣҲֵQoSýĿ.
жõH(T)ֵͬEDF㷨ǽڲȼ.ϵͳģͼ1ʾ.
3㷨
ͨģԻQoSƵĵ㷨.ֱַʱ㷨EDF㷨бȽ.


ͼ2㷨ģ1
3.1ʱ㷨ıȽ
ģõĲƽغÿQoS.ͨģöýQoSܱĸʣʧʣʱ㷨бȽ.
ģУýܹΪ15.Ϊ˷㣬ýQoSͬ£1ʱ㷨ʱƬΪ1ms.㷨ģȽϵĽͼ2ʾ.
ͼ2֪ͨʱ㷨ȣQoSĵ㷨ʺڴý.䵱ϵͳؽϴʱ㷨ʧʵͣܽϺõýҪQoS.
3.2EDF㷨ıȽ
ģУýܹΪ10.ýQoSͬ£1S=30Q=24F=4.
.ôTi,jʱ(deadline)ΪjPiEDF㷨ݴdeadline.ϵͳĳʼͷʱΪ0.
ͼ3ʾ񱻵ȵĳɹʣΪϵͳе.ͼ4еʾʧܴQoSĸ.ͼ3ͼ4еģEDF㷨ܵȱΪ4710QoS.ûQoSƵĵ㷨QoS.


ͼ3㷨ģ2


ͼ4㷨ģ3
4
ʵʱӦϵͳУΪ˱֤ϵͳеڹ涨deadline֮ǰɣϵͳʱҪ.
Tý񣩣C, P, S,Q, FִУCPSQFĺͬ϶.Ƶļ㹫ʽΪжʽ2Ƿ.ԽϵͳִУᵼQoS͵QoS֮£ܾ.

,mϵͳ.ϱrtmtֱʾʵʱͶý.
5
ýһµQoSʾڴ˻һQoSʽ㷨ͨģ⡢Ƚ֤㷨Ч.
߼飺ӵУ19721ʿо.ҪоΪʵʱݴϵͳý.ʣŮ1971˶ʿоҪоΪý弼ATM.¸ӣУ1935ڣʿʦҪоΪܼϵṹֲʽý弼.
ߵλӵ¸ӡѧѧѧϵɳ410073
ʡйѧѧоԺ100039
ο
1Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of Association for Computer Machinery, 1973, 20(1): 4661
2Sha L, Rajkumar R. Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. Proc of the IEEE, 1994, 82(1): 6882
3Tindell K W. An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Systems, 1994, 6(2): 133151
4Hiroyuki Kaneko, Stankovic J A. Integrated scheduling of multimedia and hard real-time tasks. Umass Computer Science Technical Report. 1996, 9643
5Mok A K, Chen D. A multiframe model for real-time tasks. In: Proc of 17th Real-Time Symposium, 1996. 2229
յڣ1998-09-28
޸ڣ1999-03-22
