5-網(wǎng)絡(luò)控制系統(tǒng)的調(diào)度方法

2023/12/211基于網(wǎng)絡(luò)的智能控制吳迎年wuyingnian@126.com2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院2網(wǎng)絡(luò)控制系統(tǒng)調(diào)度方法1、網(wǎng)絡(luò)控制系統(tǒng)中的調(diào)度問(wèn)題2、實(shí)時(shí)系統(tǒng)及其任務(wù)調(diào)度3、靜態(tài)RM調(diào)度算法

4、動(dòng)態(tài)EDF調(diào)度算法5、網(wǎng)絡(luò)控制系統(tǒng)調(diào)度與控制的協(xié)同設(shè)計(jì)6、TRUETIME

仿真工具箱2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院3網(wǎng)絡(luò)控制系統(tǒng)調(diào)度方法網(wǎng)絡(luò)控制系統(tǒng)研究?jī)?nèi)容:（1）對(duì)網(wǎng)絡(luò)的控制(ControlofNetwork)：對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)、網(wǎng)絡(luò)數(shù)據(jù)流量等的調(diào)度與控制，是對(duì)網(wǎng)絡(luò)自身的控制,其目的是為了提高網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS,QualityofService）；（2）通過(guò)網(wǎng)絡(luò)進(jìn)行控制（ControlthroughNetwork）：指控制系統(tǒng)的各節(jié)點(diǎn)（傳感器、控制器、執(zhí)行器等）之間通過(guò)網(wǎng)絡(luò)進(jìn)行連接并傳輸數(shù)據(jù)，針對(duì)網(wǎng)絡(luò)的不確定特性，通過(guò)設(shè)計(jì)先進(jìn)的控制算法來(lái)提高整個(gè)網(wǎng)絡(luò)控制系統(tǒng)的質(zhì)量（QoP,QualityofcontrolPerformance）。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院4網(wǎng)絡(luò)服務(wù)質(zhì)量

:指網(wǎng)絡(luò)的吞吐量，傳輸效率，誤碼率，時(shí)延可預(yù)測(cè)性和任務(wù)的可調(diào)度性等。提高網(wǎng)絡(luò)服務(wù)質(zhì)量的方法

:網(wǎng)絡(luò)的體系結(jié)構(gòu)設(shè)計(jì)，通信介質(zhì)的選擇，先進(jìn)的網(wǎng)絡(luò)調(diào)度方法等，其中網(wǎng)絡(luò)調(diào)度可以在網(wǎng)絡(luò)結(jié)構(gòu)與通信介質(zhì)等物理性質(zhì)確定的情況下，有效地提高網(wǎng)絡(luò)的服務(wù)質(zhì)量，因此是網(wǎng)絡(luò)控制系統(tǒng)中研究如何提高網(wǎng)絡(luò)服務(wù)質(zhì)量的一種受到普遍重視的方法。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院55.1網(wǎng)絡(luò)控制系統(tǒng)的調(diào)度問(wèn)題5.1.1網(wǎng)絡(luò)控制系統(tǒng)的調(diào)度1、網(wǎng)絡(luò)調(diào)度問(wèn)題：指網(wǎng)絡(luò)中的節(jié)點(diǎn)在共享的網(wǎng)絡(luò)資源中發(fā)送數(shù)據(jù)，并且發(fā)生碰撞時(shí)，規(guī)定數(shù)據(jù)包以怎樣的優(yōu)先級(jí)（順序）和何時(shí)發(fā)送數(shù)據(jù)包的問(wèn)題。研究層面：（1）設(shè)計(jì)介質(zhì)層網(wǎng)絡(luò)的通信協(xié)議，稱為協(xié)議層調(diào)度；（2）設(shè)計(jì)應(yīng)用層的節(jié)點(diǎn)優(yōu)化調(diào)度算法，稱為應(yīng)用層調(diào)度。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院62、協(xié)議層調(diào)度：指數(shù)據(jù)鏈路層通過(guò)一個(gè)鏈路活動(dòng)調(diào)度器控制現(xiàn)場(chǎng)裝置對(duì)總線的訪問(wèn)，通常是網(wǎng)絡(luò)接口設(shè)備按照特定的協(xié)議規(guī)范來(lái)決定那些并發(fā)數(shù)據(jù)包的發(fā)送順序。特點(diǎn)：通過(guò)特定的網(wǎng)絡(luò)協(xié)議來(lái)實(shí)現(xiàn)某些調(diào)度算法的，因此調(diào)度缺乏靈活性，只能適應(yīng)少數(shù)的算法。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院7

網(wǎng)絡(luò)協(xié)議是調(diào)度研究的基礎(chǔ),了解現(xiàn)有網(wǎng)絡(luò)協(xié)議特點(diǎn)對(duì)改進(jìn)工作很必要.根據(jù)控制網(wǎng)絡(luò)的時(shí)間延遲特性,網(wǎng)絡(luò)可分為三類(lèi):

隨機(jī)網(wǎng)絡(luò)、有界網(wǎng)絡(luò)和常值網(wǎng)絡(luò).

信息在網(wǎng)絡(luò)上傳輸產(chǎn)生的時(shí)延,如果是隨機(jī)的,則網(wǎng)絡(luò)為隨機(jī)網(wǎng)絡(luò);如果是有界的,則為有界網(wǎng)絡(luò);如果維持定值,則為常值網(wǎng)絡(luò).Ethernet、令牌網(wǎng)和CAN分別是它們的典型代表.2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院83、應(yīng)用層調(diào)度：指上層（傳輸層以上）的應(yīng)用程序根據(jù)需要來(lái)主動(dòng)地決策數(shù)據(jù)的發(fā)送規(guī)則，該規(guī)則與具體的網(wǎng)絡(luò)協(xié)議無(wú)關(guān)。網(wǎng)絡(luò)的作用僅僅是用于傳輸數(shù)據(jù)，不能實(shí)現(xiàn)調(diào)度決策。目前應(yīng)用層的網(wǎng)絡(luò)調(diào)度方法主要有4種：（1）借用CPU調(diào)度方法（2）設(shè)計(jì)網(wǎng)絡(luò)調(diào)度協(xié)議（3）調(diào)度與控制協(xié)同設(shè)計(jì)（4）反饋控制實(shí)時(shí)調(diào)度2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院9（1）借用CPU調(diào)度方法：目前借用單處理器的網(wǎng)絡(luò)調(diào)度方法主要有兩種：（a）靜態(tài)調(diào)度：對(duì)于調(diào)度算法而言，各任務(wù)的發(fā)送規(guī)則是事先確定的，如時(shí)限、計(jì)算時(shí)間、優(yōu)先權(quán)關(guān)系、任務(wù)釋放時(shí)間等。以RM（RateMonotonic）算法及其衍生算法為代表。（b）動(dòng)態(tài)調(diào)度：任務(wù)的時(shí)間約束關(guān)系并沒(méi)有完全確定，新任務(wù)的到達(dá)時(shí)間是未知的，在網(wǎng)絡(luò)資源充足的環(huán)境下，系統(tǒng)仍然能夠保證所有的任務(wù)時(shí)限。以EDF（EarliestDeadlineFirst）算法及其衍生算法為代表。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院10（2）設(shè)計(jì)網(wǎng)絡(luò)調(diào)度協(xié)議借鑒單處理器動(dòng)態(tài)調(diào)度的思想，結(jié)合控制系統(tǒng)的特點(diǎn)，設(shè)計(jì)開(kāi)發(fā)新的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)發(fā)送規(guī)則。其特點(diǎn)是在網(wǎng)絡(luò)控制系統(tǒng)穩(wěn)定的前提下，保證網(wǎng)絡(luò)節(jié)點(diǎn)的動(dòng)態(tài)優(yōu)化調(diào)度。典型方法是Walsh等人提出的一種給時(shí)間關(guān)鍵信息動(dòng)態(tài)分配網(wǎng)絡(luò)資源的TOD(try-once-discard)協(xié)議。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院11（3）調(diào)度與控制協(xié)同設(shè)計(jì)指在網(wǎng)絡(luò)控制系統(tǒng)設(shè)計(jì)中，將系統(tǒng)控制與網(wǎng)絡(luò)優(yōu)化統(tǒng)一考慮，研究在滿足系統(tǒng)控制指標(biāo)條件下的網(wǎng)絡(luò)調(diào)度方法，以及同時(shí)滿足系統(tǒng)控制指標(biāo)優(yōu)化和網(wǎng)絡(luò)可調(diào)度性的采樣周期的選擇方法。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院12（4）反饋控制實(shí)時(shí)調(diào)度一般實(shí)時(shí)調(diào)度算法是一種開(kāi)環(huán)調(diào)度算法，即一旦調(diào)度確立，就不能根據(jù)連續(xù)的反饋來(lái)進(jìn)行相應(yīng)地調(diào)整。反饋控制實(shí)時(shí)調(diào)度指將反饋控制的思想應(yīng)用到實(shí)時(shí)調(diào)度算法中，根據(jù)網(wǎng)絡(luò)反饋回來(lái)的信息來(lái)調(diào)節(jié)任務(wù)或調(diào)度器的參數(shù)，從而有效地提高網(wǎng)絡(luò)系統(tǒng)的傳輸性能。該研究方法的難點(diǎn)在于分布式環(huán)境中，如何有效地同步獲取反饋信息。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院135.1.2NCS調(diào)度中的幾個(gè)基本概念圖1實(shí)時(shí)網(wǎng)絡(luò)傳輸任務(wù)的時(shí)間參數(shù)圖2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院14（1）到達(dá)時(shí)間（ai）：數(shù)據(jù)包形成，開(kāi)始加入發(fā)送隊(duì)列，準(zhǔn)備發(fā)送。此為一個(gè)發(fā)送周期的開(kāi)始。（2）開(kāi)始發(fā)送時(shí)刻（si）：數(shù)據(jù)包開(kāi)始發(fā)送的時(shí)刻。（3）阻塞時(shí)間（bi）：數(shù)據(jù)包達(dá)到后，等待直至開(kāi)發(fā)發(fā)送所需要的時(shí)間，即bi=si-ai。網(wǎng)絡(luò)數(shù)據(jù)包的傳輸中任務(wù)是非搶優(yōu)的，bi由兩部分組成：bh,i：等待所有更高優(yōu)先級(jí)的任務(wù)傳輸完畢的時(shí)間bl,i：正在發(fā)送的較低優(yōu)先級(jí)的任務(wù)發(fā)送完畢所需要的時(shí)間其最大值分別記為：2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院15（4）傳輸時(shí)間（ci）：數(shù)據(jù)包由源地址經(jīng)網(wǎng)絡(luò)傳送到目的地址所需要的時(shí)間，一般由數(shù)據(jù)包的大小和網(wǎng)絡(luò)介質(zhì)的速率決定。（5）完成時(shí)間（fi）：一次傳輸結(jié)束的時(shí)間。（6）傳輸時(shí)延（τi）：數(shù)據(jù)包到達(dá)隊(duì)列至數(shù)據(jù)包完成數(shù)據(jù)包傳輸完成之間的時(shí)間。顯然

（7）時(shí)限（di）：為保證NCS的性能，傳輸必須在某個(gè)時(shí)間之前完成，該時(shí)間就稱為時(shí)限。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院16（8）網(wǎng)絡(luò)占用率（U）：其中NCS中N個(gè)對(duì)象的傳感器按周期pi

發(fā)送數(shù)據(jù)。（9）可調(diào)度性：指網(wǎng)絡(luò)控制系統(tǒng)的所有數(shù)據(jù)傳輸都能在任務(wù)時(shí)限內(nèi)完成。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院175.1.3網(wǎng)絡(luò)調(diào)度的幾種基本方法1、協(xié)議層調(diào)度2、TOD網(wǎng)絡(luò)調(diào)度協(xié)議3、反饋控制實(shí)時(shí)調(diào)度。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院18協(xié)議層調(diào)度方法：1、Ethernet使用載波偵聽(tīng)多路訪問(wèn)/沖突檢測(cè)（CSMA/CD）網(wǎng)絡(luò)協(xié)議，為隨機(jī)網(wǎng)絡(luò)的代表。2、令牌網(wǎng)是有界網(wǎng)絡(luò)的代表,分為令牌總線和令牌環(huán)兩類(lèi).ControlNet、MAP(IEEE802.4)、Profi-bus都屬于令牌總線。3、CAN通信協(xié)議采用多主競(jìng)爭(zhēng)機(jī)制（CSMA/AMP）網(wǎng)絡(luò)協(xié)議，是常值網(wǎng)絡(luò)的代表。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院19TOD（Try-OnceDiscade）網(wǎng)絡(luò)動(dòng)態(tài)調(diào)度協(xié)議1、MEF-TOD協(xié)議內(nèi)容：（1）NCS中每個(gè)節(jié)點(diǎn)都有一個(gè)優(yōu)先級(jí)，該優(yōu)先級(jí)與誤差范數(shù)成正比，該誤差指最近發(fā)送的數(shù)據(jù)值與實(shí)際測(cè)量數(shù)據(jù)值的差；（2）誤差最大的節(jié)點(diǎn)擁有發(fā)送數(shù)據(jù)的最大優(yōu)先級(jí)；（3）如果兩個(gè)或更多的節(jié)點(diǎn)信息具有相同的優(yōu)先權(quán)，則按事先約定的規(guī)則來(lái)解決這種碰撞。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院202、最大允許傳輸時(shí)間間隔MATI（MaximumAllowableTransferInterval）：傳輸時(shí)間間隔指NCS訪問(wèn)網(wǎng)絡(luò)的時(shí)間間隔?？梢宰C明，在MEF-TOD或靜態(tài)調(diào)度下，某個(gè)NCS系統(tǒng)，當(dāng)MATI小于某個(gè)與NCS性能相關(guān)的數(shù)值時(shí)，NCS系統(tǒng)是全局指數(shù)穩(wěn)定的。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院21（1）大多數(shù)實(shí)時(shí)調(diào)度算法是開(kāi)環(huán)的調(diào)度算法，不能根據(jù)負(fù)載變化的情況進(jìn)行動(dòng)態(tài)調(diào)節(jié)以提高系統(tǒng)的性能；（2）開(kāi)環(huán)調(diào)度的決策依據(jù)是基于對(duì)任務(wù)參數(shù)的最差情形估計(jì)得到，因此系統(tǒng)的冗余度太大，導(dǎo)致系統(tǒng)的占有率不足；（3）對(duì)于軟實(shí)時(shí)系統(tǒng)，許多情況下應(yīng)根據(jù)負(fù)載參數(shù)的平均水平（如平均執(zhí)行時(shí)間）來(lái)做出相應(yīng)的決策，以此來(lái)動(dòng)態(tài)地處理有界的瞬時(shí)負(fù)載；（4）反饋調(diào)度能夠根據(jù)反饋回來(lái)的信息有效地調(diào)節(jié)任務(wù)或調(diào)度器的參數(shù)，從而提高系統(tǒng)的性能；對(duì)于資源不足（過(guò)載）的情況下的軟實(shí)時(shí)系統(tǒng)，提供了較好的解決方案。反饋控制實(shí)時(shí)調(diào)度：2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院22（1）被控量（被測(cè)量）：網(wǎng)絡(luò)占用率根據(jù)：取決于系統(tǒng)的目標(biāo)?？刂葡到y(tǒng)的各個(gè)任務(wù)的數(shù)據(jù)在網(wǎng)絡(luò)上傳輸時(shí)要受到網(wǎng)絡(luò)帶寬的限制，對(duì)于軟實(shí)時(shí)系統(tǒng)來(lái)說(shuō)，適當(dāng)?shù)貋G棄數(shù)據(jù)包同樣能夠保證系統(tǒng)的性能，因此可以使用任務(wù)對(duì)網(wǎng)絡(luò)資源的需求作為受控量。（2）控制量：任務(wù)提交時(shí)對(duì)網(wǎng)絡(luò)占用率的需求根據(jù)：控制量必須能夠影響被控變量的值。（3）參考輸入：所有調(diào)度任務(wù)網(wǎng)絡(luò)占用率的期望值Us反饋調(diào)度器：2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院23圖2NCS反饋調(diào)度器結(jié)構(gòu)任務(wù)監(jiān)視器控制器調(diào)度器任務(wù)過(guò)濾器累加器Us+_任務(wù)控制網(wǎng)絡(luò)2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院241、Monitor任務(wù)監(jiān)視器監(jiān)控待傳輸?shù)娜蝿?wù)，計(jì)算任務(wù)的實(shí)際網(wǎng)絡(luò)占用率。2、累加器把監(jiān)視器得到的數(shù)據(jù)與網(wǎng)絡(luò)占用率期望值累加。（1）（2）2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院253、PID控制器把誤差值轉(zhuǎn)化為任務(wù)需求的網(wǎng)絡(luò)占有率，從而使得實(shí)際網(wǎng)絡(luò)占用率盡可能接近設(shè)定的期望值。（1）當(dāng)時(shí)，說(shuō)明網(wǎng)絡(luò)即將飽和，應(yīng)該減少任務(wù)數(shù)；（2）當(dāng)時(shí)，說(shuō)明網(wǎng)絡(luò)資源充足，可以增加相應(yīng)的任務(wù)數(shù)。（3）其中IW為積分項(xiàng)的時(shí)間窗口，DW為微分項(xiàng)的時(shí)間窗口。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院264、任務(wù)過(guò)濾器根據(jù)PID控制器的輸出來(lái)增加或減少輸入任務(wù)的數(shù)量。5、EDF調(diào)度器按RM或EDF算法對(duì)各個(gè)任務(wù)進(jìn)行調(diào)度發(fā)送。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院275.2實(shí)時(shí)系統(tǒng)及其任務(wù)調(diào)度5.2.1實(shí)時(shí)系統(tǒng)概述1、實(shí)時(shí)系統(tǒng)：在確定的時(shí)間內(nèi)執(zhí)行計(jì)算或處理事務(wù)并對(duì)外部的異步事件做出響應(yīng)的計(jì)算機(jī)系統(tǒng)。實(shí)時(shí)系統(tǒng)從輸入時(shí)刻到輸出時(shí)刻之間的時(shí)滯必須小到可接受時(shí)限內(nèi)。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院282、分類(lèi)標(biāo)準(zhǔn)：系統(tǒng)對(duì)時(shí)間要求的嚴(yán)格程度。（1）硬實(shí)時(shí)系統(tǒng)：如果一個(gè)系統(tǒng)未能在指定時(shí)間內(nèi)就某一事件做出響應(yīng)而失敗，則該失敗被認(rèn)為是一種全面的系統(tǒng)失敗。一般用于航天系統(tǒng)或核反應(yīng)堆系統(tǒng)，系統(tǒng)較復(fù)雜。（2）軟實(shí)時(shí)系統(tǒng)：系統(tǒng)對(duì)某些任務(wù)的響應(yīng)時(shí)間允許一定程度上的超時(shí)限，而不會(huì)導(dǎo)致系統(tǒng)的失敗。大多數(shù)系統(tǒng)都屬于軟實(shí)時(shí)系統(tǒng)，網(wǎng)絡(luò)控制系統(tǒng)通常是軟實(shí)時(shí)系統(tǒng)。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院293、實(shí)時(shí)系統(tǒng)組成：在實(shí)時(shí)系統(tǒng)中，一個(gè)應(yīng)用通常由一組任務(wù)構(gòu)成，每個(gè)任務(wù)完成應(yīng)用中的一部分功能，組合后為用戶提供特定的服務(wù)。例如在一個(gè)計(jì)算機(jī)控制的飛行器飛行控制應(yīng)用包括：數(shù)據(jù)采集任務(wù)自動(dòng)導(dǎo)航任務(wù)控制任務(wù)2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院304、實(shí)時(shí)系統(tǒng)特點(diǎn)：時(shí)間約束性：指各任務(wù)不僅應(yīng)滿足相互之間的拓?fù)浼s束和時(shí)序約束，還要遵從各自的絕對(duì)時(shí)間約束和相對(duì)時(shí)間約束?？深A(yù)測(cè)性：可預(yù)測(cè)性是指系統(tǒng)能對(duì)實(shí)時(shí)任務(wù)的執(zhí)行時(shí)間進(jìn)行判斷，確定是否能夠滿足任務(wù)的時(shí)限要求?？煽啃裕捍蠖鄶?shù)實(shí)時(shí)系統(tǒng)要求有較高的可靠性，可靠性己成為衡量實(shí)時(shí)系統(tǒng)性能的不可缺少的重要指標(biāo)。與外部環(huán)境的交互作用性：外部物理環(huán)境往往是被控子系統(tǒng)，兩者相互作用構(gòu)成完整的實(shí)時(shí)系統(tǒng)。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院315、實(shí)時(shí)調(diào)度：是實(shí)時(shí)系統(tǒng)的核心，為不同實(shí)時(shí)并發(fā)任務(wù)使用獨(dú)占的、有限的資源確定一種調(diào)度策略，以使所有實(shí)時(shí)任務(wù)的處理都不錯(cuò)過(guò)截止時(shí)間。實(shí)時(shí)調(diào)度算法特征：（1）硬實(shí)時(shí)與軟實(shí)時(shí)（2）搶優(yōu)與非搶優(yōu)（3）動(dòng)態(tài)與靜態(tài)（4）集中與分布2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院32（1）硬實(shí)時(shí)與軟實(shí)時(shí)

硬實(shí)時(shí)：必須保證所有時(shí)限都要被嚴(yán)格地滿足，否則將會(huì)導(dǎo)致嚴(yán)重的后果。軟實(shí)時(shí)：并不要求所有的時(shí)間要求均嚴(yán)格地滿足，可忍受一種最大近似。（2）搶優(yōu)與非搶優(yōu)

搶優(yōu)：允許在更高優(yōu)先級(jí)的任務(wù)到來(lái)時(shí)暫時(shí)掛起當(dāng)前的任務(wù)，以后在沒(méi)有更高優(yōu)先級(jí)的任務(wù)要運(yùn)行時(shí)對(duì)恢復(fù)它的處理。非搶優(yōu)：一旦一個(gè)任務(wù)啟動(dòng)后，它將占有處理機(jī)直到執(zhí)行結(jié)束。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院33（3）動(dòng)態(tài)與靜態(tài)

動(dòng)態(tài)：在運(yùn)行期間進(jìn)行調(diào)度。靜態(tài)：在運(yùn)行前事先就調(diào)度好的。（4）集中與分布

集中：用一臺(tái)機(jī)器來(lái)收集所有的信息并做出所有的決定。分布：各個(gè)處理機(jī)可以獨(dú)立做出決定。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院345.2.2實(shí)時(shí)調(diào)度與網(wǎng)絡(luò)調(diào)度1、基本概念：（1）調(diào)度：給定一組實(shí)時(shí)任務(wù)和系統(tǒng)資源，確定每個(gè)任務(wù)何時(shí)何地執(zhí)行的整個(gè)過(guò)程。（2）實(shí)時(shí)調(diào)度：在確定的時(shí)間內(nèi)執(zhí)行計(jì)算或處理事務(wù)并對(duì)外部的異步事件做出響應(yīng)的計(jì)算機(jī)系統(tǒng)。也可稱為CPU（處理器）調(diào)度算法，基本上分為兩類(lèi)：靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。

靜態(tài)調(diào)度：RM（RateMonotonic）調(diào)度算法及其衍生算法是靜態(tài)調(diào)度算法。

動(dòng)態(tài)調(diào)度：EDF（EarliestDeadlineFirst）調(diào)度算法及其衍生算法是靜態(tài)調(diào)度算法。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院352、網(wǎng)絡(luò)調(diào)度與實(shí)時(shí)調(diào)度比較相同點(diǎn)：都有共享資源的限制。實(shí)時(shí)系統(tǒng)：多個(gè)任務(wù)不能同時(shí)使用CPU的計(jì)算資源網(wǎng)絡(luò)系統(tǒng)：多數(shù)據(jù)共用一條網(wǎng)絡(luò)傳輸介質(zhì)不同點(diǎn)：實(shí)時(shí)系統(tǒng)：調(diào)度是可以搶優(yōu)的網(wǎng)絡(luò)系統(tǒng)：調(diào)度是可以非搶優(yōu)的2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院36網(wǎng)絡(luò)調(diào)度與實(shí)時(shí)調(diào)度比較網(wǎng)絡(luò)調(diào)度CPU調(diào)度任務(wù)數(shù)據(jù)包的傳輸任務(wù)的執(zhí)行pi數(shù)據(jù)包的傳輸周期任務(wù)執(zhí)行周期ci數(shù)據(jù)包的傳輸時(shí)間任務(wù)的計(jì)算時(shí)間fi數(shù)據(jù)包傳輸?shù)慕Y(jié)束時(shí)刻任務(wù)執(zhí)行的結(jié)束時(shí)刻di數(shù)據(jù)包傳輸?shù)臅r(shí)限任務(wù)執(zhí)行的時(shí)限U網(wǎng)絡(luò)使用率CPU使用率搶優(yōu)非搶優(yōu)可搶優(yōu)2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院375.3靜態(tài)RM調(diào)度算法1、RM算法介紹：

RM（RateMonotonic）調(diào)度算法，中文稱為“比率單調(diào)調(diào)度算法”，是實(shí)時(shí)系統(tǒng)中單處理器的基于優(yōu)先級(jí)的靜態(tài)調(diào)度算法5.3.1實(shí)時(shí)系統(tǒng)的RM調(diào)度算法2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院382、RM算法描述：（1）根據(jù)任務(wù)的周期hi分配優(yōu)先權(quán)：任務(wù)的周期越短，其優(yōu)先權(quán)越高；（2）任務(wù)的優(yōu)先權(quán)在任務(wù)執(zhí)行之前已經(jīng)確定，不會(huì)隨時(shí)間改變，因此是一種靜態(tài)的調(diào)度算法；（3）實(shí)時(shí)系統(tǒng)中的RM算法是搶優(yōu)的，即當(dāng)前執(zhí)行的任務(wù)會(huì)被新到達(dá)的優(yōu)先級(jí)更高的任務(wù)打斷。（4）RM算法在所有的固定優(yōu)先級(jí)分配算法中是最優(yōu)的；（5）RM算法是穩(wěn)定的：確保優(yōu)先級(jí)高的任務(wù)先執(zhí)行。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院393、RM可調(diào)度定理：一組n個(gè)相互獨(dú)立、可搶優(yōu)的實(shí)時(shí)周期任務(wù)，用RM算法的可調(diào)度條件為任務(wù)的總占有率U滿足如下不等式：（1）其中ci

為任務(wù)所需的執(zhí)行時(shí)間，hi

為任務(wù)的周期。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院40例5.1：兩個(gè)并發(fā)的周期實(shí)時(shí)任務(wù)，執(zhí)行時(shí)間為c1=c2=3ms，任務(wù)周期為h1=4ms，h2=6ms，任務(wù)時(shí)限d1=h1，d2=h2。計(jì)算RM算法的可調(diào)度性。解：任務(wù)的占有率為：由RM算法的可調(diào)度條件可知用RM算法不可調(diào)度。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院41說(shuō)明：（1）根據(jù)RM算法，由于h1<h2，則任務(wù)1的優(yōu)先級(jí)高于任務(wù)2的優(yōu)先級(jí)，因此兩個(gè)任務(wù)同時(shí)到達(dá)時(shí)，任務(wù)1先處理；（2）經(jīng)過(guò)3ms任務(wù)1處理完畢，進(jìn)行任務(wù)2的處理；（3）任務(wù)1處理1ms后，任務(wù)1的下一個(gè)周期來(lái)到，于是打斷任務(wù)2的執(zhí)行，進(jìn)行任務(wù)1的處理；（4）如此反復(fù)，結(jié)果為任務(wù)1所有的任務(wù)周期都沒(méi)有超過(guò)時(shí)限要求，但任務(wù)2所有的周期任務(wù)都超過(guò)了時(shí)限的要求。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院424、RM算法缺點(diǎn)：（1）對(duì)非周期任務(wù)的調(diào)度效率低；（2）不能有效的對(duì)非調(diào)和的周期性操作進(jìn)行調(diào)度；（3）不能靈活地處理操作調(diào)用時(shí)資源需求的變化。

總體而言，靜態(tài)調(diào)度在資源的利用率和保證運(yùn)行時(shí)對(duì)資源的訪問(wèn)之間進(jìn)行了折衷，限制了實(shí)時(shí)系統(tǒng)適應(yīng)系統(tǒng)狀態(tài)和配置變化的能力。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院435.3.2NCS的RM調(diào)度算法1、算法描述：（1）指非搶優(yōu)的RM調(diào)度算法；（2）與實(shí)時(shí)系統(tǒng)的搶優(yōu)式調(diào)度算法相比，唯一的區(qū)別就是網(wǎng)絡(luò)RM調(diào)度算法中，任務(wù)的執(zhí)行是非搶優(yōu)的，即當(dāng)前執(zhí)行的任務(wù)不會(huì)被新到達(dá)的優(yōu)先級(jí)更高的任務(wù)打斷，直到該任務(wù)執(zhí)行完，才能執(zhí)行隊(duì)列中等待的高優(yōu)先級(jí)任務(wù)。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院442、非搶優(yōu)RM可調(diào)度定理：一組n個(gè)相互獨(dú)立、非搶優(yōu)的實(shí)時(shí)周期任務(wù)（其優(yōu)先級(jí)按下標(biāo)值遞減，下標(biāo)i為1任務(wù)的優(yōu)先級(jí)最高，下標(biāo)i為N任務(wù)的優(yōu)先級(jí)最低），其可調(diào)度條件為對(duì)于所有的，都滿足如下不等式：（2）其中為任務(wù)被低優(yōu)先級(jí)任務(wù)阻塞的最差情形的阻塞時(shí)間，即（3）2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院45例5.2同樣對(duì)于例5.1，對(duì)于任務(wù)1，即i=1，應(yīng)用非搶優(yōu)RM可調(diào)度定理，有對(duì)于任務(wù)2，即i=2，應(yīng)用非搶優(yōu)RM可調(diào)度定理，有由非搶優(yōu)RM算法的可調(diào)度條件可知：用非搶優(yōu)RM算法不可調(diào)度。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院46說(shuō)明：（1）根據(jù)RM算法，由于h1<h2，則任務(wù)1的優(yōu)先級(jí)高于任務(wù)2的優(yōu)先級(jí)，因此兩個(gè)任務(wù)同時(shí)到達(dá)時(shí)，任務(wù)1先處理；（2）經(jīng)過(guò)3ms任務(wù)1處理完畢，進(jìn)行任務(wù)2的處理；（3）任務(wù)1處理1ms后，任務(wù)1的下一個(gè)周期來(lái)到，但是對(duì)于非搶優(yōu)調(diào)度，任務(wù)1不能打斷任務(wù)2的執(zhí)行，于是繼續(xù)進(jìn)行任務(wù)2的處理；（4）任務(wù)2再經(jīng)過(guò)2ms后處理完畢，于是進(jìn)行任務(wù)1的處理；（5）如此反復(fù)，結(jié)果為任務(wù)1所有的任務(wù)周期都超過(guò)了時(shí)限要求，但任務(wù)2所有的周期任務(wù)都沒(méi)有超過(guò)時(shí)限的要求。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院475.4動(dòng)態(tài)EDF調(diào)度算法1、EDF算法介紹：

EDF（EarliestDeadlineFirst）調(diào)度算法，是實(shí)時(shí)系統(tǒng)中單處理器的基于優(yōu)先級(jí)的動(dòng)態(tài)調(diào)度算法。中文可稱為“最小時(shí)限優(yōu)先”動(dòng)態(tài)調(diào)度算法。5.4.1實(shí)時(shí)系統(tǒng)的EDF調(diào)度算法2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院482、EDF算法描述：（1）根據(jù)任務(wù)距離時(shí)限要求的長(zhǎng)度(di-ci)來(lái)分配任務(wù)的優(yōu)先級(jí)：距離時(shí)限越小的任務(wù)獲得的優(yōu)先級(jí)越高；（2）任務(wù)的優(yōu)先權(quán)不是固定不變的，而是隨時(shí)間變化的，任務(wù)的優(yōu)先級(jí)相對(duì)于時(shí)間是不確定的；（3）實(shí)時(shí)系統(tǒng)中的EDF算法是搶優(yōu)的，即當(dāng)前執(zhí)行的任務(wù)會(huì)被新到達(dá)的優(yōu)先級(jí)更高的任務(wù)打斷。（4）EDF調(diào)度算法是所有可搶優(yōu)式調(diào)度算法中最優(yōu)的：即EDF算法無(wú)法調(diào)度的任務(wù)集，其他任何優(yōu)先級(jí)調(diào)度算法都無(wú)法調(diào)度。（5）EDF調(diào)度算法不穩(wěn)定：任務(wù)集過(guò)載時(shí)無(wú)法預(yù)料那些任務(wù)超時(shí)限。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院493、EDF可調(diào)度定理：一組n個(gè)相互獨(dú)立的實(shí)時(shí)周期任務(wù)，用EDF算法的可調(diào)度條件為任務(wù)的總占有率U滿足如下不等式：（4）其中ci

為任務(wù)所需的執(zhí)行時(shí)間，hi

為任務(wù)的周期。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院50例5.3：兩個(gè)并發(fā)的周期實(shí)時(shí)任務(wù)，執(zhí)行時(shí)間為c1=c2=3ms，任務(wù)周期為h1=6ms，h2=4ms，任務(wù)時(shí)限d1=h1，d2=h2。計(jì)算EDF算法的可調(diào)度性。解：任務(wù)的占有率為：由EDF算法的可調(diào)度條件可知用EDF算法不可調(diào)度。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院51說(shuō)明：（1）根據(jù)EDF算法，由于h2<h1，則任務(wù)2距離時(shí)限要求更小，其優(yōu)先級(jí)高于任務(wù)1的優(yōu)先級(jí)，因此兩個(gè)任務(wù)同時(shí)到達(dá)時(shí)，任務(wù)2先處理；（2）經(jīng)過(guò)3ms任務(wù)2處理完畢，進(jìn)行任務(wù)1的處理；（3）任務(wù)1處理1ms后，任務(wù)2的下一個(gè)周期來(lái)到，但由于此時(shí)任務(wù)1距離時(shí)限的要求為2ms（6ms-3ms-1ms），而任務(wù)2新的任務(wù)周期距離時(shí)限要求為4ms，因此任務(wù)1的優(yōu)先級(jí)高，任務(wù)1繼續(xù)執(zhí)行；（4）如此反復(fù)，結(jié)果為任務(wù)1和任務(wù)2都有超過(guò)時(shí)限要求的現(xiàn)象發(fā)生。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院52（5）與RM算法比較，此時(shí)任務(wù)1獲得了更多的資源，即EDF算法對(duì)資源的分配更加均衡。（6）由于軟實(shí)時(shí)系統(tǒng)在某種程度上能夠承受部分的任務(wù)超過(guò)時(shí)限的要求，因此EDF算法的均衡調(diào)度對(duì)于軟實(shí)時(shí)系統(tǒng)任務(wù)的保證是很重要的。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院534、EDF算法優(yōu)缺點(diǎn)：（1）克服了RM的利用率限制；（2）可以處理調(diào)和與非調(diào)和周期的情況；（3）可以在單獨(dú)靜態(tài)優(yōu)先級(jí)水平上分發(fā)操作而不需用頻率來(lái)確定操作的優(yōu)先級(jí)。（4）需要較高的系統(tǒng)開(kāi)銷(xiāo)來(lái)在運(yùn)行時(shí)對(duì)操作進(jìn)行評(píng)估。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院545.4.2NCS的EDF度算法1、算法描述：（1）指非搶優(yōu)的EDF調(diào)度算法；（2）與實(shí)時(shí)系統(tǒng)的搶優(yōu)式調(diào)度算法相比，唯一的區(qū)別就是網(wǎng)絡(luò)EDF調(diào)度算法中，任務(wù)的執(zhí)行是非搶優(yōu)的，即當(dāng)前執(zhí)行的任務(wù)不會(huì)被新到達(dá)的優(yōu)先級(jí)更高的任務(wù)打斷，直到該任務(wù)執(zhí)行完，才能執(zhí)行隊(duì)列中等待的高優(yōu)先級(jí)任務(wù)。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院552、非搶優(yōu)EDF可調(diào)度定理：令為有n個(gè)任務(wù)的任務(wù)集，其中是一系列按周期非遞減順序排列的周期性任務(wù)，ci

為任務(wù)Ti

的最長(zhǎng)執(zhí)行時(shí)間，hi

為任務(wù)Ti

的周期，di=hi

為任務(wù)Ti

的時(shí)限，則當(dāng)且僅當(dāng)以下條件成立，T

在非搶優(yōu)EDF調(diào)度算法下可調(diào)度：（6）（5）證明略。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院563、非搶優(yōu)EDF可調(diào)度分析算法：依據(jù)非搶優(yōu)EDF可調(diào)度定理給出的實(shí)用的可調(diào)度分析算法。例5.5：設(shè)實(shí)時(shí)系統(tǒng)中有如下4個(gè)任務(wù)，任務(wù)的時(shí)間屬性如表1所示。表1任務(wù)時(shí)間屬性idi/mshi/msci/ms1441266238824161622023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院57

di=hi，應(yīng)用時(shí)限等于周期的非搶優(yōu)EDF可調(diào)度判定算法，判斷該任務(wù)集是否可調(diào)度。令處理器利用率：表2中給出了取不同值時(shí)任務(wù)集的時(shí)間需求關(guān)系。由表中數(shù)據(jù)可以看出，i取值不同時(shí)，均滿足可調(diào)度條件。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院58表2i

取不同值時(shí)任務(wù)集的時(shí)間需求關(guān)系i252375415112023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院59（1）NCS是由網(wǎng)絡(luò)和控制組成的控制系統(tǒng)，其閉環(huán)性能不僅依賴于控制算法的設(shè)計(jì)，還依賴于對(duì)網(wǎng)絡(luò)資源的合理調(diào)度。（2）合適的傳輸協(xié)議和調(diào)度策略可以保證網(wǎng)絡(luò)的服務(wù)質(zhì)量。（3）NCS中的采樣周期同時(shí)涉及控制與調(diào)度兩個(gè)方面，因此，綜合考慮控制與網(wǎng)絡(luò)調(diào)度兩個(gè)方面指標(biāo)的NCS中采樣周期的優(yōu)化選擇，就是調(diào)度與控制協(xié)同設(shè)計(jì)的一個(gè)基本的途徑。5.5網(wǎng)絡(luò)控制系統(tǒng)調(diào)度與控制的協(xié)同設(shè)計(jì)2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院605.5.1具有網(wǎng)絡(luò)時(shí)延的NCS模型對(duì)于線性時(shí)不變系統(tǒng)，一個(gè)網(wǎng)絡(luò)控制子系統(tǒng)Loopi的系統(tǒng)模型表示如下：（7）（8）2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院61假如網(wǎng)絡(luò)時(shí)延小于一個(gè)采樣周期hi

，相應(yīng)系統(tǒng)（7）（8）的離散模型為：（9）（10）（11）式中Li為增益矩陣。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院62每個(gè)控制子系統(tǒng)的性能通過(guò)性能指標(biāo)函數(shù)：式中Qi

為正半定矩陣。（12）2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院635.5.2NCS采樣周期的優(yōu)化1、優(yōu)化原因：NCS采樣周期時(shí)既受控制對(duì)象穩(wěn)定性的約束，也受網(wǎng)絡(luò)可調(diào)度性約束。解決這個(gè)矛盾的方法是在一定約束條件下取得總體性能的折中。2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院642、優(yōu)化模型：（1）目標(biāo)函數(shù)：（13）pi

為權(quán)系數(shù)，Ji

是各控制回路的性能指標(biāo)函數(shù)。（2）系統(tǒng)穩(wěn)定性條件（14）2023/12/21北京信息科技大學(xué)自動(dòng)化學(xué)院65（3）調(diào)度約束條件EDF調(diào)度算法（定理5.4）：（16）（15）RM調(diào)度算法（定理5.2）：（17）2