【正文】 :22:1408:22Feb237Feb23 ? 1越是無能的人，越喜歡挑剔別人的錯兒。 。達(dá)一算法的思想是，將最終時限比較接近的請求收集在一起分成若干批，并且以柱面的順序?qū)ζ溥M(jìn)行處理。這一可預(yù)測的負(fù)載可以用來使用為多媒體剪裁的算法對磁盤進(jìn)行調(diào)度。流行的電影將完整地存放在磁盤上。在高速緩存中保留 10秒鐘的磁盤塊是有可能的，但是要浪費(fèi)內(nèi)存。 ? 對于多媒體而言，通常的訪問模式是按順序從頭到尾觀看一部電影。對于同一部電影，系統(tǒng)現(xiàn)在可以發(fā)出對多個塊的請求每個請求要求讀數(shù)據(jù)到不同的內(nèi)存緩沖區(qū)，但是以這樣的方式，當(dāng)所有的請求都完成時，一個連續(xù)的電影片斷（包含多個幀）在內(nèi)存中將被連續(xù)地組裝好。固定的字節(jié)數(shù)從電影 A寫入磁盤 1，然后相同的字節(jié)數(shù)寫入磁盤 2，直到到達(dá)最后一塊磁盤（在本例的情形中是 A3單元）。 2023114 77 圖 910 視頻服務(wù)器上文件的管風(fēng)琴分布 電 影1 0電 影8電 影6電 影4電 影2電 影1電 影3電 影5電 影7電 影9電 影1 1使用頻率柱 面 在單個磁盤上存放多個文件 ? 如果每一部電影是如圖 98所示類型的連續(xù)文件，這樣的存放方式工作得好；如果每一部電影被約束在一個狹窄的柱面范圍之內(nèi)，這樣的存放方式也可以擴(kuò)大其使用的范圍。這一模式是哈佛大學(xué)的一位語言學(xué)教授 Gee Zipf（ 19021950）發(fā)現(xiàn)的，被稱為 Zipf定律。圖 99說明了這一方法的應(yīng)用，圖中的電影以每秒 30幀的速率播放，每隔 5分鐘開始一個新的數(shù)據(jù)流（參見圖 96）。 兩個替代的文件組織策略 ? 另一方面，塊索引比幀索引要小很多。這里的思想是每部電影有一個幀索引，這是一個數(shù)據(jù)結(jié)構(gòu)，每一幀有一個幀索引項(xiàng)，指向幀的開始。為此，在傳輸一幀的過程中有多次尋道是極其不受歡迎的。在 8:10，當(dāng)?shù)谝粋€數(shù)據(jù)流處于第 18 000幀并且第二個數(shù)據(jù)流處于第 9000幀時，第三個數(shù)據(jù)流開始，以此類推直到第 24個數(shù)據(jù)流開始于 9:55。利用特別準(zhǔn)備的快倒文件，可以用類似的方法實(shí)現(xiàn)快倒。向前跳過 k幀（就算假設(shè)能這樣做）可能落在一個 P幀上，而這個 P幀則基于剛剛跳過的一個 I幀。當(dāng)電影暫停時繼續(xù)占用這些資源將造成浪費(fèi)，特別是如果用戶打算轉(zhuǎn)而暫時去做另外一件事情的時候。在進(jìn)程結(jié)束時它將調(diào)用 close以關(guān)閉文件并返回其資源。為了獲得要求的 %的空閑時間， 5ms的間隙必須每 200ms出現(xiàn)一次，這就是間隙為什么沒有在圖 94中出現(xiàn)的原因?？烧{(diào)度性測試計(jì)算 CPU的利用率為 + + = 。 最早最終時限優(yōu)先調(diào)度 ? 另一個流行的實(shí)時調(diào)度算法是最早最終時限優(yōu)先（ Earliest Deadtime First, EDF）算法。 速率單調(diào)調(diào)度 ? RMS分配給每個進(jìn)程一個固定的優(yōu)先級，優(yōu)先級等于進(jìn)程觸發(fā)事件發(fā)生的頻率。每個進(jìn)程以一個固定的頻率運(yùn)行，對每一 CPU突發(fā)有固定的工作量要求。只要進(jìn)程數(shù)足夠少，所有的工作都可以在一幀的時間內(nèi)完成，采用輪轉(zhuǎn)調(diào)度就足夠了。注意，顫動不同于延遲。然而，以系統(tǒng)設(shè)計(jì)的觀點(diǎn)，客戶機(jī)進(jìn)程是在機(jī)頂盒上運(yùn)行還是在 PC機(jī)上運(yùn)行并沒有太大的關(guān)系。視頻點(diǎn)播要求基于特殊的基礎(chǔ)設(shè)施，圖 91所示為兩種可能的視頻點(diǎn)播基礎(chǔ)設(shè)施，每種都包含三個基本的組件：一個或多個視頻服務(wù)器、一個分布式網(wǎng)絡(luò)以及一個在每個房間中用來對信號進(jìn)行解碼的機(jī)頂盒。 2023114 4 圖 91 視頻點(diǎn)播使用不同的本地分布技術(shù) ∞ 分 布 式 網(wǎng) 絡(luò)光 纖視 頻 服 務(wù) 器同 軸 電 纜匯 接 盒 分 布 式 網(wǎng) 絡(luò)光 纖視 頻 服 務(wù) 器匯 接 盒∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞住 房銅 雙 絞 線a ） A D S Lb ） 有 線 電 視 視頻剪輯與點(diǎn)播 ? 視頻服務(wù)器是一臺功能強(qiáng)大的計(jì)算機(jī)，在其文件系統(tǒng)中存放著許多電影，并且可以按照點(diǎn)播請求回放這些電影。對于桌面視頻編輯系統(tǒng)而言，所有的進(jìn)程都運(yùn)行在相同的計(jì)算機(jī)上，分別發(fā)揮著服務(wù)器和客戶的作用。如果圖 91中的分布式網(wǎng)絡(luò)均勻地將所有的位淮確地延遲 5s，電影將開始得稍稍晚一些，但是看起來卻不錯。 一般實(shí)時調(diào)度 ? 隨著用戶的數(shù)目不斷變化，由于視頻壓縮的本性（ I幀比 P幀或 B幀大得多），幀的大小劇烈變化，并且不同的電影可能有不同的分辨率。 一般實(shí)時調(diào)度 ? 在某些實(shí)時系統(tǒng)中，進(jìn)程是可搶占的，在其他的系統(tǒng)中，進(jìn)程是不可搶占的。例如，必須每 30ms運(yùn)行一次（每秒33次）的進(jìn)程獲得的優(yōu)先級為 33，必須每 40ms運(yùn)行一次（每秒 25次）的進(jìn)程獲得的優(yōu)先級為 25，必須每 50ms運(yùn)行一次（每秒 20次）的進(jìn)程獲得的優(yōu)先級為 20。 EDF是一個動態(tài)算法，它不像速率單調(diào)算法那樣要求進(jìn)程是周期性的。 CPU只留下了 25%，但是在理論上 CPU并沒有被超額預(yù)定，找到一個合理的調(diào)度應(yīng)該是可能的。 最早最終時限優(yōu)先調(diào)度 ? 根本上，使用靜態(tài)優(yōu)先級只有在 CPU的利用率不太高的時候才能工作。 多媒體文件系統(tǒng) ? 由于實(shí)時行為的需要，這一模型對于多媒體并不能很好地工作，尤其是在顯示來自遠(yuǎn)程視頻服務(wù)器的多媒體文件時，該模型的工作效果更差。當(dāng)然，在暫停的時候可以很容易地將資源釋放，但是這引入了風(fēng)險(xiǎn)：當(dāng)用戶試圖恢復(fù)播放的時候，有可能無法重新獲得這些資源。沒有基本幀，只有從基本幀發(fā)生的增量變化（這正是 P 幀所包含的）是無用的。 VCR控制功能 ? 當(dāng)用戶切換回到正常速度時，必須使用相反的技巧。在 10:00，第一個數(shù)據(jù)流終止并且再一次從第 0幀開始。在視頻服務(wù)器上消除文件內(nèi)尋道的一種方法是使用連續(xù)的文件。每一幀本身是一連串連續(xù)的塊，包含該幀所有的視頻、音頻和文本軌跡，如圖 98中所示。對于 256KB的塊，如果幀的平均大小為 16KB，那么一個塊大約可以裝下 16個幀，所以一部由 216 000幀組成的電影在塊索引中只需要有13 500個索引項(xiàng)，與此相對比，對于幀索引則需要 216 000個索引項(xiàng)。根據(jù)這些參數(shù)， 2小時長的電影需要 24個當(dāng)前數(shù)據(jù)流。該定律說的是，如果電影，圖書、 Web網(wǎng)頁或者單詞按其流行性進(jìn)行排名，那么下一個客戶選擇排行榜中排名為 k的項(xiàng)的概率是 C/k。 ? 該算法所做的是試圖將磁頭保持在磁盤的中央。然后，再次在第一塊磁盤處繼續(xù)分條帶操作，寫入 A4單元，這樣進(jìn)行下去直到整個文件被寫完。這些請求可以并行處理。一個塊不太可能被使用兩次。一種替代的方法是試圖使兩部電影同步，這一方法可以通過改變兩部電影的幀率來實(shí)現(xiàn)，如圖 912所示。 文件高速緩存 ? 使用高速緩存的另一種方法是在磁盤上保存每部電影的最初幾分鐘。 動態(tài)磁盤調(diào)度 ? 不同的電影可能具有不同的數(shù)據(jù)率，所以對磁盤的請求或多或少是隨機(jī)到來的。 動態(tài)磁盤調(diào)度 ? 如果不同的視頻流具有不同的數(shù)據(jù)率，那么當(dāng)一個新的客戶出現(xiàn)時將引起一個嚴(yán)重的問題：該客戶是否應(yīng)該被接納？如果接納該客戶會導(dǎo)致其他的視頻流頻繁地錯過它們的最終時限，那么答案可能就是否。 2023年 2月 上午 8時 22分 :22February 7, 2023 ? 1行動出成果，工作出財(cái)富。 08:22:1408:22:1408:22Tuesday, February 7, 2023 ? 1知人者智，自知者明。 08:22:1408:22:1408:222/7/2023 8:22:14 AM ? 1越是沒有本領(lǐng)的就越加自命不凡。 2023年 2月 7日星期二 上午 8時 22分 14秒 08:22: ? 1比不了得就不比，得不到的就不要。 ? 使用 scanEDF算法可以將這兩個因素結(jié)合起來。 靜態(tài)磁盤調(diào)度 ? 就 NTSC回放而言，每 ，每個客戶將需要其文件中的下一幀，并且系統(tǒng)有 （系統(tǒng)對每個視頻流需要緩沖至少一幀，所以取第 k + 1幀可以與第 k幀的回放并行處理）。因此，大多數(shù)視頻服務(wù)器維護(hù)著一個請求頻繁的磁盤高速緩存。假設(shè)兩個用戶正在觀看同一部電影，但是在兩個用戶之間存在 10秒鐘的延遲。在傳統(tǒng)的 LRU緩沖區(qū)高速緩存背后的思想是，當(dāng)一個塊被使用之后，應(yīng)該將其保存在高速緩存中，以防很快再次需要訪問它。每個塊包含一個或多個幀或者其中的碎片。讓我們暫時假設(shè)所有的幀大小相同（也就是未壓縮）。該算法將最流行的電影存放在磁盤的中央，第二和第三流行的電影存放在最流行的電影的兩邊，在這幾部電影的外邊是排名第四和第五的電影，以此類推，如圖 910所示。 在單個磁盤上存放多個文件 ? 對于許多種類的流行性事件，相對流行性的一個合理的近似遵循著一種令人驚奇的可預(yù)測模式。有研究者設(shè)計(jì)了一種文件存放策略幾乎可以消除全部這樣的尋道。圖 98 b）浪費(fèi)的磁盤空間計(jì)算起來非常困難，但是肯定多很多，因?yàn)樵谝粋€磁盤塊的盡頭有時會留下 100KB的空間，而下一幀是一個比它大的 I 幀。對于每秒 30幀以 4Mbps速率傳輸?shù)?MPEG2而言，幀的平均大小為 16KB，所以一個磁盤塊的大小為 1KB或 2KB工作得比較好。 在單個磁盤上存放文件 ? 最為重要的要求是數(shù)據(jù)能夠以必要的速度流出到網(wǎng)絡(luò)或輸出設(shè)備上，并且沒有顫動。在 8:05，當(dāng)?shù)谝粋€數(shù)據(jù)流處于第 9000幀時，第二個數(shù)據(jù)流開始。當(dāng)然，這一幀可能是 P幀或 B幀，但是客戶端的解碼進(jìn)程可以簡單地跳過若干幀直到看見一個 I幀。 VCR控制功能 ? 對于 MPEG，由于使用 I幀、 P幀和 B幀，這一方案即使在理論上也是不能工作的。 ? 然而，這里存在著一個復(fù)雜因素，服務(wù)器應(yīng)該為每個流出的數(shù)據(jù)流保留諸如磁盤帶寬和內(nèi)存緩沖區(qū)等資源。以后還可以發(fā)出另外的 read調(diào)用，直到進(jìn)程結(jié)束。由于所有開始和結(jié)束時間都是 5ms的倍數(shù)，所以間隙將是 5ms。 2023114 32 圖 94 以 RMS和 EDF進(jìn)行實(shí)時調(diào)度的另一個例子 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 1 0 0 1 1 0 1 2 0 1 3 0 1 4 0CBAC 1B 1A 1C 2 C 3B 2 B 3 B 4A 2 A 3 A 4 A 5時 間 （ m s ）A 1 B 1 A 2 B 2失 敗R M SA 1 B 1 C 1 A 2 B 2 A 3 C 2 B 3 A 4 C 3 A 5 B 4E D F 最早最終時限優(yōu)先調(diào)度 ? 在這個例子中，進(jìn)程 A、 B和 C的周期與前面的例子相同，但是現(xiàn)在 A每次突發(fā)需要 15ms的 CPU時間，而不是只有10ms。在這一時刻，系統(tǒng)可以在結(jié)束進(jìn)程 B或者開始進(jìn)程 C之間進(jìn)行選擇，所以它選擇優(yōu)先級最高的進(jìn)程 B。當(dāng)然，最后一個不是，但是該條件使系統(tǒng)建模更加容易。然而，將音頻進(jìn)程加入到系統(tǒng)中并沒有改變一般模型，因?yàn)槲覀兊娜考僭O(shè)是存在 m個進(jìn)程。當(dāng)主控時鐘再次滴答時，所有的進(jìn)程再次以相同的次序運(yùn)行。傳輸率的變動稱為顫動，必須嚴(yán)格限制顫動以獲得良好的性能。不管共用的是機(jī)頂盒還是個人計(jì)算機(jī)，在解碼并顯示電影的用戶端，我們通常都要區(qū)分視頻服務(wù)器和客戶機(jī)進(jìn)程。視頻點(diǎn)播是重要的多媒體技術(shù)，這意味著消費(fèi)者能夠在家中使用電視遙控器（或鼠標(biāo)）選擇電影，并且立刻將其在電視機(jī)（或計(jì)算機(jī)顯示器）上顯示出來。大型機(jī)有時用來作為視頻服務(wù)器，因?yàn)榇笮蜋C(jī)連接 1000個大容量的磁盤是一件輕而易舉的事情。 ? 多媒體處理具有兩個關(guān)鍵的特征，即多媒體使用極高的數(shù)據(jù)率和多媒體要求實(shí)時回放。但從另一方面來說，如果分布式網(wǎng)絡(luò)在 100~200ms之間隨機(jī)地延遲各幀，那就會明顯影響播放質(zhì)量。因此，不同的進(jìn)程可能必須以不同的頻率運(yùn)行，具有不同的工作量，并且具有不同的最終時限。在多媒體系統(tǒng)中，進(jìn)程通常是可搶占的，這意味著允許有危險(xiǎn)錯過其最終時限的進(jìn)程在正在運(yùn)行的進(jìn)程完成工作以前將其中斷，然后當(dāng)它完成工作之后，被中斷的前一個進(jìn)程再繼續(xù)運(yùn)行。所以，優(yōu)先級與進(jìn)程的速率（每秒運(yùn)行進(jìn)程的次數(shù)）成線性關(guān)系，這正是為什么將其稱為速率單調(diào)的原因。它也