臺灣博碩士論文加值系統

本論文提出一個基於網路流量之嵌入式系統優先權化(PRIFIC）工作排程方法。此管理方法藉由動態分配系統資源的方式，不僅能提高系統資源之使用率，同時更能有效免除因較高優先權之工作，長時間佔有系統資源所造成的網路資料遺失率上升。此管理方法乃是先萃取網路流量特徵，再藉由網路流量預測模型以及一個稱為主要成份分析（PCA）的演算法進行流量預測，最後配合一個適應性的網路工作排程模型進行資源之分配。PCA演算法主要是用來減少網路流量特徵的維度，它能夠有效率地減少網路流量預測演算法的計算複雜性。
簡而言之， PRIFIC 排程法具有網路流量預測和保證服務品質的能力。依據實驗結果可得知此管理方法在固定流率及隨機流率形態資料之網路工作排程上均有很好的表現。

This thesis proposes a PRIoritized TrafFIC-dependent (PRIFIC) task scheduling scheme based on the traffic prediction approach that. The PRIFIC manages network tasks by dynamically allocating system resources, so that it can not only prevent the network tasks from starvation state but also improve the utilization of system resources. The PRIFIC is constructed by employing an eigentraffic feature extraction model, a traffic prediction model, and an adaptive task scheduling model. Besides, an additional reference algorithm which is called principal component analysis (PCA) is adopted to reduce the dimensions of traffic features. It can efficiently reduce the computation complexity of the proposed PRIFIC algorithm.
In summary, the PRIFIC has advantages of traffic prediction and QoS-enabling. According to the simulation results, the proposed PRIFIC exhibits excellent task scheduling performance in both constant traffic and random traffic applications.

Contents......................................................................I
List of Tables...............................................................II
List of Figures.............................................................III
Chapter 1 Introduction........................................................1
1.1. Task and Task Scheduling in Embedded OS..........................1
1.2. Motivation.......................................................3
1.3. Thesis Organization..............................................4
Chapter 2 Task Scheduling in Embedded OS......................................6
2.1. Task Scheduling..................................................6
2.1.1. Round Robin with Time-Slicing Task Scheduling................8
2.1.2. Priority Task Scheduling....................................10
2.2. Comparing Scheduling Policies for Network Tasks.................12
2.3. Packet Scheduling Criteria vs. Task Scheduling Criteria.........15
Chapter 3 Prioritized Traffic-Dependent Task Scheduling......................19
3.1. PRIFIC Task Scheduling..........................................19
3.1.1. Prioritized Network Task....................................20
3.1.2. Traffic-Dependent Task Scheduling...........................22
3.2. Traffic Prediction Algorithm....................................23
3.2.1. Traffic Feature Extractor...................................24
3.2.2. Calculating Eigentraffics and Traffic Prediction............26
3.2.3. The Eigentraffics Calculation Scheme........................31
3.3. Adaptive Scheduling Algorithm ..................................32
Chapter 4 Analysis of PRIFIC.................................................36
4.1. Analysis of Traffic Prediction Algorithm........................36
4.2. Analysis of Task Scheduling Algorithm...........................41
4.3. Analysis of Dynamic Prediction Algorithm........................44
Chapter 5 Simulation Results.................................................56
5.1. Simulation Method...............................................56
5.2. PRIFIC Task Scheduling with Poisson Random Traffic .............59
5.2.1. Simulation Results..........................................65
5.3. Effects of , and ............................................69
5.3.1. Simulation Results..........................................71
Chapter 6 Conclusions and Discussion.........................................75
6.1 Conclusions......................................................75
6.2 Future Work......................................................76
References...................................................................77

[1]Lidinsky, W.,IEEE Standard P802.1D Information tecnology Telecommunications
and information exchange between systems - Common specifications - Part 3:
Media Access Control (MAC) Bridges: Revision, 24.11.1997 [defered
14.3.1999]
[2]Shenker S. et al. Specification of Guaranteed Quality of Service. RFC 2212,
September 1997.
[3]Yu-Chung Wang, Kwei-Jay Lin: Implementing a General Real-Time Scheduling
Framework in the RED-Linux Real-Time Kernel. IEEE Real-Time Systems
Symposium 1999: 246-255
[4]C.L. Liu and J. Layland. Scheduling Algorithms for Multiprogramming in a
Hard Real-Time Environment. Journal of the ACM, 20(1):46-61, 1973.
[5]A. Demers, S. Keshav, and S. Shenker. Analysis and Simulation of a Fair
Queueing Algorithm. In Journal of Internetworking Research and Experience,
pp.3-26, October 1990.
[6]M. A. Turk and A. p. Pentland , “Eigenfaces for recognition,” J.
Cognitive Networks, vol. 3, no. 1, pp. 71-86, Mar. 1991
[7]K. Fukunaga, Introduction to statistical Pattern Recognition,” 2nd ed.
Boston, MA: Academic, 1990.
[8]L. Sirovich and M. Kirby, “Low-dimensional procedure for the
charactization of human faces,” j.Opt. Soc. Amer. A, vol. 4, no 3, pp. 529-
524, Mar. 1987.
[9]John Wiley and Sons, Queueing Systems, WILEY, 1997.
[10]M. Barabanov and V. Yodaiken, Introducing Real-Time Unix. Linux Journal,
No. 34, Feb 1997
[11]Y.C. Wang and K.J. Lin. Enhancing the real-time capability of the Linux
kernel. In Proc. of 5th RTCSA’98, Hiroshima, Japan, Oct 1998.
[12]A. Dmers, S. Keshav, and S. Shenker. Analysis and Simulation of a Fair
Queuing Algorithm. Proc. ACM SIGCOMM’89, pages 1-12, September 1989.
[13]D. D. Clark, S. Shenker, and L. Zhang, “Supporting Real-Time Applications
in an Integrated Services Packet Network Architecture and Mechanism,”
Proc. ACM SIGCOMM’92, August, 1992.
[14]D. Ferrari, A. Banerjea, and H. Zhang, ”Network Support for Multimedia :
A discussion of the Telnet Approach,” Technical Report TR-92-072,
Computer Science Division, University of California at Berkeley, November
1992.
[15]S. J. Golestani, ”Duration-Limited Statistical Multiplexing of Delay
Sensitive Traffic in Packet Networks,” Proc.INFOCOM’91, 1991.
[16]C. Kalmanek, H. Kanakia, and S. keshav, “Rate Controlled Servers for Very
High-Speed Networks, ” Proc. GlobeCom’90, pp.300.3.1-300.3.9., 1990.
[17]J. Hyman, A Lazar, and G. Pacitici, “Real-Time Scheduling with quality of
Service Constraints,” IEEE JSAC, vol. 9, no. 9, pp. 1052-63, September
1991.
[18]Wroclawski J. Specification of Controlled-Load Network Element Service.
RFC 2211, September 1997.