第9章多媒體操作系統(tǒng)課件1第9章多媒體操作系統(tǒng)數(shù)字電影、視頻剪輯和音樂正在日益成為用計(jì)算機(jī)表示信息和進(jìn)行消遣娛樂的常用方式。音頻和視頻文件通常保存在磁盤上，在需要的時(shí)候進(jìn)行回放。音頻和視頻文件的特征與傳統(tǒng)的文本文件存在很大的差異，而目前計(jì)算機(jī)的文件系統(tǒng)最初卻是為文本文件設(shè)計(jì)的。因此，需要設(shè)計(jì)新的文件系統(tǒng)來處理音頻和視頻文件。不僅如此，保存與回放音頻和視頻同樣給操作系統(tǒng)及其調(diào)度程序提出了新的和更高的要求。第9章多媒體操作系統(tǒng)數(shù)字電影、視頻剪輯和音樂正在日益成為9.1視頻剪輯與點(diǎn)播通常，多媒體編輯系統(tǒng)需要在支持多媒體的操作系統(tǒng)上運(yùn)行，以獲得最好的性能。視頻點(diǎn)播是重要的多媒體技術(shù)，這意味著消費(fèi)者能夠在家中使用電視遙控器（或鼠標(biāo)）選擇電影，并且立刻將其在電視機(jī)（或計(jì)算機(jī)顯示器）上顯示出來。視頻點(diǎn)播要求基于特殊的基礎(chǔ)設(shè)施，圖9-1所示為兩種可能的視頻點(diǎn)播基礎(chǔ)設(shè)施，每種都包含三個(gè)基本的組件：一個(gè)或多個(gè)視頻服務(wù)器、一個(gè)分布式網(wǎng)絡(luò)以及一個(gè)在每個(gè)房間中用來對(duì)信號(hào)進(jìn)行解碼的機(jī)頂盒。9.1視頻剪輯與點(diǎn)播通常，多媒體編輯系統(tǒng)需要在支持多媒體圖9-1視頻點(diǎn)播使用不同的本地分布技術(shù)圖9-1視頻點(diǎn)播使用不同的本地分布技術(shù)49.1視頻剪輯與點(diǎn)播視頻服務(wù)器是一臺(tái)功能強(qiáng)大的計(jì)算機(jī)，在其文件系統(tǒng)中存放著許多電影，并且可以按照點(diǎn)播請(qǐng)求回放這些電影。大型機(jī)有時(shí)用來作為視頻服務(wù)器，因?yàn)榇笮蜋C(jī)連接1000個(gè)大容量的磁盤是一件輕而易舉的事情。9.1視頻剪輯與點(diǎn)播視頻服務(wù)器是一臺(tái)功能強(qiáng)大的計(jì)算機(jī)，在9.1視頻剪輯與點(diǎn)播用戶和視頻服務(wù)器之間的分布式網(wǎng)絡(luò)必須能夠高速實(shí)時(shí)地傳輸數(shù)據(jù)。分布式網(wǎng)絡(luò)總是使用光纖從視頻服務(wù)器連接到客戶居住點(diǎn)的匯接盒。ADSL系統(tǒng)是由電話公司經(jīng)營的，在ADSL系統(tǒng)中，現(xiàn)有的雙絞電話線提供了最后一公里的數(shù)據(jù)傳輸。有線電視是由有線電視公司經(jīng)營的，在有線電視系統(tǒng)中，現(xiàn)有的有線電視電纜用于信號(hào)的本地分送。ADSL的優(yōu)點(diǎn)是為每個(gè)用戶提供了專用數(shù)據(jù)通道，因此帶寬有保證，但是由于現(xiàn)有電話線的局限其帶寬比較低（只有幾Mb/s）。9.1視頻剪輯與點(diǎn)播用戶和視頻服務(wù)器之間的分布式網(wǎng)絡(luò)必須9.1視頻剪輯與點(diǎn)播有線電視使用高帶寬的同軸電纜，帶寬可以達(dá)到幾Gb/s，但是許多用戶必須共享相同的電纜，從而導(dǎo)致競爭，對(duì)于每個(gè)用戶來說帶寬沒有保證。不過，為了與有線電視競爭，電話公司正在為住戶鋪設(shè)光纜，這樣，光纜上的ADSL將比電視電纜有更大的帶寬。系統(tǒng)的最后一部分是機(jī)頂盒，這是ADSL或電視電纜終結(jié)的地方。機(jī)頂盒實(shí)際上就是一臺(tái)計(jì)算機(jī)，只不過其中包含特殊的芯片用于視頻解碼和解壓縮。機(jī)頂盒最少要包含CPU、RAM、ROM、與ADSL或電視電纜的接口，以及用于跟電視機(jī)連接的端子。9.1視頻剪輯與點(diǎn)播有線電視使用高帶寬的同軸電纜，帶寬可9.1視頻剪輯與點(diǎn)播用戶也可以使用現(xiàn)有的PC機(jī)并且在顯示器上顯示電影。從技術(shù)角度看，使用個(gè)人計(jì)算機(jī)代替機(jī)頂盒更有道理，因?yàn)橛?jì)算機(jī)的功能更加強(qiáng)大，擁有大容量的磁盤，并且擁有更高分辨率的顯示器。不管共用的是機(jī)頂盒還是個(gè)人計(jì)算機(jī)，在解碼并顯示電影的用戶端，我們通常都要區(qū)分視頻服務(wù)器和客戶機(jī)進(jìn)程。然而，以系統(tǒng)設(shè)計(jì)的觀點(diǎn)，客戶機(jī)進(jìn)程是在機(jī)頂盒上運(yùn)行還是在PC機(jī)上運(yùn)行并沒有太大的關(guān)系。對(duì)于桌面視頻編輯系統(tǒng)而言，所有的進(jìn)程都運(yùn)行在相同的計(jì)算機(jī)上，分別發(fā)揮著服務(wù)器和客戶的作用。多媒體處理具有兩個(gè)關(guān)鍵的特征，即多媒體使用極高的數(shù)據(jù)率和多媒體要求實(shí)時(shí)回放。9.1視頻剪輯與點(diǎn)播用戶也可以使用現(xiàn)有的PC機(jī)并且在顯示9.1視頻剪輯與點(diǎn)播高數(shù)據(jù)率來自視覺與聽覺信息的本性。眼睛和耳朵每秒可以處理巨大數(shù)量的信息，必須以這樣的速率為眼睛和耳朵提供信息才能產(chǎn)生可以接受的觀察體驗(yàn)。表9-1列舉了幾種數(shù)字多媒體源和某些常見硬件設(shè)備的數(shù)據(jù)率。需要注意的是，多媒體需要的數(shù)據(jù)率越高，則越需要進(jìn)行壓縮，并且需要的存儲(chǔ)量也就越大。例如，一部未壓縮的2小時(shí)長的HDTV電影將填滿一個(gè)570GB的文件。存放1000部這種電影的視頻服務(wù)器需要570TB的磁盤空間，按照目前的標(biāo)準(zhǔn)這可是難以想象的數(shù)量。還需要注意的是，沒有數(shù)據(jù)壓縮，目前的硬件不可能跟上這樣的數(shù)據(jù)率。9.1視頻剪輯與點(diǎn)播高數(shù)據(jù)率來自視覺與聽覺信息的本性。眼表9-1某些多媒體和高性能I/O設(shè)備的數(shù)據(jù)率（1Mbps=106位/秒，1GB=230字節(jié)）表9-1某些多媒體和高性能I/O設(shè)備的數(shù)據(jù)率109.1視頻剪輯與點(diǎn)播多媒體對(duì)系統(tǒng)提出的第二個(gè)要求是需要實(shí)時(shí)數(shù)據(jù)傳輸。數(shù)字電影的視頻部分每秒包含某一數(shù)目的幀。北美、南美和日本采用的NTSC制式每秒包含30幀（實(shí)際為29.97幀），世界上其他大部分地區(qū)采用的PAL和SECAM制式每秒包含25幀（25.00幀）。幀必須分別以33.3ms或40ms的精確時(shí)間間隔傳輸，否則電影看起來將會(huì)有起伏。9.1視頻剪輯與點(diǎn)播多媒體對(duì)系統(tǒng)提出的第二個(gè)要求是需要實(shí)9.1視頻剪輯與點(diǎn)播耳朵比眼睛更加敏感，傳輸時(shí)間中即使存在幾毫秒的變動(dòng)也會(huì)被察覺到。傳輸率的變動(dòng)稱為顫動(dòng)，必須嚴(yán)格限制顫動(dòng)以獲得良好的性能。注意，顫動(dòng)不同于延遲。如果圖9-1中的分布式網(wǎng)絡(luò)均勻地將所有的位淮確地延遲5s，電影將開始得稍稍晚一些，但是看起來卻不錯(cuò)。但從另一方面來說，如果分布式網(wǎng)絡(luò)在100~200ms之間隨機(jī)地延遲各幀，那就會(huì)明顯影響播放質(zhì)量。9.1視頻剪輯與點(diǎn)播耳朵比眼睛更加敏感，傳輸時(shí)間中即使存9.1視頻剪輯與點(diǎn)播提供服務(wù)質(zhì)量保證的最常見的方法是預(yù)先為每一個(gè)新到的客戶預(yù)留資源，包括CPU、內(nèi)存緩沖區(qū)、磁盤傳輸容量以及網(wǎng)絡(luò)帶寬。如果一位新的客戶到來并且想觀看一部電影，但是視頻服務(wù)器或網(wǎng)絡(luò)計(jì)算出不具有為另一位客戶提供服務(wù)的容量，那么它將拒絕新的客戶，以避免降低向當(dāng)前客戶提供的服務(wù)質(zhì)量。因此，多媒體服務(wù)器需要有資源預(yù)留方案和進(jìn)入控制算法，以判定什么時(shí)候能夠處理更多的任務(wù)。9.1視頻剪輯與點(diǎn)播提供服務(wù)質(zhì)量保證的最常見的方法是預(yù)先9.2多媒體進(jìn)程調(diào)度多媒體操作系統(tǒng)與傳統(tǒng)操作系統(tǒng)有三個(gè)主要區(qū)別，即進(jìn)程調(diào)度、文件系統(tǒng)和磁盤調(diào)度。9.2多媒體進(jìn)程調(diào)度多媒體操作系統(tǒng)與傳統(tǒng)操作系統(tǒng)有三個(gè)主9.2.1調(diào)度同質(zhì)進(jìn)程最簡單的一種視頻服務(wù)器可以支持顯示固定數(shù)目的電影，所有電影使用相同的幀率、視頻分辨率、數(shù)據(jù)率以及其他參數(shù)。在這樣的情況下，可以采用下述簡單但是有效的調(diào)度算法。對(duì)每一部電影，存在一個(gè)進(jìn)程（或線程），其工作是每次從磁盤中讀取電影的一幀然后將該幀傳送給用戶。由于所有的進(jìn)程同等重要，每一幀有相同的工作量要做，并且當(dāng)它們完成當(dāng)前幀的處理時(shí)將阻塞，所以采用輪轉(zhuǎn)調(diào)度可以很好地做這樣的工作。將調(diào)度算法標(biāo)準(zhǔn)化的唯一的額外要求是定時(shí)機(jī)制，以確保每一進(jìn)程以恰當(dāng)?shù)念l率運(yùn)行。9.2.1調(diào)度同質(zhì)進(jìn)程最簡單的一種視頻服務(wù)器可以支持顯示9.2.1調(diào)度同質(zhì)進(jìn)程實(shí)現(xiàn)適當(dāng)定時(shí)的一種方式是有一個(gè)主控時(shí)鐘，該時(shí)鐘每秒滴答適當(dāng)?shù)拇螖?shù)，例如針對(duì)NTSC制式，每秒滴答30次。在時(shí)鐘的每一滴答，所有的進(jìn)程以相同的次序相繼運(yùn)行。當(dāng)一個(gè)進(jìn)程完成其工作時(shí)，它將發(fā)出suspend系統(tǒng)調(diào)用釋放CPU直到主控時(shí)鐘再次滴答。當(dāng)主控時(shí)鐘再次滴答時(shí)，所有的進(jìn)程再次以相同的次序運(yùn)行。只要進(jìn)程數(shù)足夠少，所有的工作都可以在一幀的時(shí)間內(nèi)完成，采用輪轉(zhuǎn)調(diào)度就足夠了。9.2.1調(diào)度同質(zhì)進(jìn)程實(shí)現(xiàn)適當(dāng)定時(shí)的一種方式是有一個(gè)主控9.2.2一般實(shí)時(shí)調(diào)度隨著用戶的數(shù)目不斷變化，由于視頻壓縮的本性（I幀比P幀或B幀大得多），幀的大小劇烈變化，并且不同的電影可能有不同的分辨率。因此，不同的進(jìn)程可能必須以不同的頻率運(yùn)行，具有不同的工作量，并且具有不同的最終時(shí)限。這些考慮導(dǎo)致一個(gè)不同的模型：多個(gè)進(jìn)程競爭CPU，每個(gè)進(jìn)程有自己的工作量和最終時(shí)限。在下面的模型中，我們將假設(shè)系統(tǒng)知道每個(gè)進(jìn)程必須以什么樣的頻率運(yùn)行、有多少工作要做以及下一個(gè)最終時(shí)限是什么。多個(gè)相互競爭的進(jìn)程，其中若干進(jìn)程或全部進(jìn)程具有必須滿足的最終時(shí)限的調(diào)度就是實(shí)時(shí)調(diào)度。9.2.2一般實(shí)時(shí)調(diào)度隨著用戶的數(shù)目不斷變化，由于視頻壓9.2.2一般實(shí)時(shí)調(diào)度作為實(shí)時(shí)多媒體調(diào)度程序工作環(huán)境的一個(gè)例子，我們考慮三個(gè)進(jìn)程A、B和C，如圖9-2所示。進(jìn)程A每30ms運(yùn)行一次（近似NTSC制式速度），每一幀需要10ms的CPU時(shí)間。在不存在競爭的情況下，進(jìn)程A將在突發(fā)A1、A2、A3等中運(yùn)行，每一突發(fā)在前一突發(fā)的30ms之后開始。每個(gè)CPU突發(fā)處理一幀并且具有一個(gè)最終時(shí)限：它必須在下一個(gè)突發(fā)開始之前完成。9.2.2一般實(shí)時(shí)調(diào)度作為實(shí)時(shí)多媒體調(diào)度程序工作環(huán)境的一圖9-2三個(gè)周期性的進(jìn)程，每個(gè)進(jìn)程播放一部電影；每一電影的幀率以及每幀的處理需求有所不同圖9-2三個(gè)周期性的進(jìn)程，每個(gè)進(jìn)程播放一部電影；每一電影199.2.2一般實(shí)時(shí)調(diào)度圖9-2中，進(jìn)程B每秒運(yùn)行25次（例如PAL制式），進(jìn)程C每秒運(yùn)行20次（例如一個(gè)慢下來的NTSC或PAL流，意在使一個(gè)低帶寬的用戶連接到視頻服務(wù)器）。每一幀的計(jì)算時(shí)間如圖9-2中所示，進(jìn)程B為15ms，進(jìn)程C為5ms，沒有使它們都具有相同的時(shí)間只是為了使調(diào)度問題更加一般化?，F(xiàn)在，調(diào)度問題是如何調(diào)度A、B和C以確保它們滿足各自的最終時(shí)限。9.2.2一般實(shí)時(shí)調(diào)度圖9-2中，進(jìn)程B每秒運(yùn)行25次（9.2.2一般實(shí)時(shí)調(diào)度到目前為止我們假設(shè)每個(gè)影片流有一個(gè)進(jìn)程，實(shí)際上，每個(gè)影片流可能有兩個(gè)甚至更多個(gè)進(jìn)程，例如一個(gè)用于音頻一個(gè)用于視頻。它們可能以不同的速率運(yùn)行并且每一脈沖可能消耗不同數(shù)量的CPU時(shí)間。然而，將音頻進(jìn)程加入到系統(tǒng)中并沒有改變一般模型，因?yàn)槲覀兊娜考僭O(shè)是存在m個(gè)進(jìn)程。每個(gè)進(jìn)程以一個(gè)固定的頻率運(yùn)行，對(duì)每一CPU突發(fā)有固定的工作量要求。9.2.2一般實(shí)時(shí)調(diào)度到目前為止我們假設(shè)每個(gè)影片流有一個(gè)9.2.2一般實(shí)時(shí)調(diào)度在某些實(shí)時(shí)系統(tǒng)中，進(jìn)程是可搶占的，在其他的系統(tǒng)中，進(jìn)程是不可搶占的。在多媒體系統(tǒng)中，進(jìn)程通常是可搶占的，這意味著允許有危險(xiǎn)錯(cuò)過其最終時(shí)限的進(jìn)程在正在運(yùn)行的進(jìn)程完成工作以前將其中斷，然后當(dāng)它完成工作之后，被中斷的前一個(gè)進(jìn)程再繼續(xù)運(yùn)行。這一行為只不過是多道程序設(shè)計(jì)。在多媒體系統(tǒng)中可搶占的實(shí)時(shí)調(diào)度算法比不可搶占的調(diào)度算法具有更好的性能。唯一要關(guān)心的是如果傳輸緩沖區(qū)在很少的幾個(gè)突發(fā)中被填充，那么在最終時(shí)限到來之前該緩沖區(qū)應(yīng)該是完全滿的，這樣它就可以在一次操作中傳遞給用戶，否則就會(huì)引起顫動(dòng)。9.2.2一般實(shí)時(shí)調(diào)度在某些實(shí)時(shí)系統(tǒng)中，進(jìn)程是可搶占的，9.2.2一般實(shí)時(shí)調(diào)度實(shí)時(shí)算法可以是靜態(tài)的也可以是動(dòng)態(tài)的。靜態(tài)算法預(yù)先分配給每個(gè)進(jìn)程一個(gè)固定的優(yōu)先級(jí)，然后使用這些優(yōu)先級(jí)做基于優(yōu)先級(jí)的搶占調(diào)度。動(dòng)態(tài)算法沒有固定的優(yōu)先級(jí)。9.2.2一般實(shí)時(shí)調(diào)度實(shí)時(shí)算法可以是靜態(tài)的也可以是動(dòng)態(tài)的9.2.3速率單調(diào)調(diào)度適用于可搶占的周期性進(jìn)程的經(jīng)典靜態(tài)實(shí)時(shí)調(diào)度算法是速率單調(diào)調(diào)度（RateMonotonicScheduling，RMS），它可以用于滿足下列條件的進(jìn)程：1）每個(gè)周期性進(jìn)程必須在其周期內(nèi)完成。2）沒有進(jìn)程依賴于任何其他進(jìn)程。3）每一進(jìn)程在一次突發(fā)中需要相同的CPU時(shí)間量。4）任何非周期性進(jìn)程都沒有最終時(shí)限。5）進(jìn)程搶占即刻發(fā)生而沒有系統(tǒng)開銷。前四個(gè)條件是合理的。當(dāng)然，最后一個(gè)不是，但是該條件使系統(tǒng)建模更加容易。9.2.3速率單調(diào)調(diào)度適用于可搶占的周期性進(jìn)程的經(jīng)典靜態(tài)9.2.3速率單調(diào)調(diào)度RMS分配給每個(gè)進(jìn)程一個(gè)固定的優(yōu)先級(jí)，優(yōu)先級(jí)等于進(jìn)程觸發(fā)事件發(fā)生的頻率。例如，必須每30ms運(yùn)行一次（每秒33次）的進(jìn)程獲得的優(yōu)先級(jí)為33，必須每40ms運(yùn)行一次（每秒25次）的進(jìn)程獲得的優(yōu)先級(jí)為25，必須每50ms運(yùn)行一次（每秒20次）的進(jìn)程獲得的優(yōu)先級(jí)為20。所以，優(yōu)先級(jí)與進(jìn)程的速率（每秒運(yùn)行進(jìn)程的次數(shù)）成線性關(guān)系，這正是為什么將其稱為速率單調(diào)的原因。在運(yùn)行時(shí)，調(diào)度程序總是運(yùn)行優(yōu)先級(jí)最高的就緒進(jìn)程，如果需要?jiǎng)t搶占正在運(yùn)行的進(jìn)程。已經(jīng)證明在靜態(tài)調(diào)度算法種類中RMS是最優(yōu)的。9.2.3速率單調(diào)調(diào)度RMS分配給每個(gè)進(jìn)程一個(gè)固定的優(yōu)先9.2.3速率單調(diào)調(diào)度圖9-3演示了圖9-2所示例子中速率單調(diào)調(diào)度是如何工作的。進(jìn)程A、B和C分別具有靜態(tài)優(yōu)先級(jí)33、25和20，這意味著只要A需要運(yùn)行，它就可以運(yùn)行，搶占任何當(dāng)前正在使用CPU的其他進(jìn)程。進(jìn)程B可以搶占C，但不能搶占A。進(jìn)程C必須等待直到CPU空閑才能運(yùn)行。9.2.3速率單調(diào)調(diào)度圖9-3演示了圖9-2所示例子中速圖9-3RMS和EDF實(shí)時(shí)調(diào)度的一個(gè)例子圖9-3RMS和EDF實(shí)時(shí)調(diào)度的一個(gè)例子279.2.3速率單調(diào)調(diào)度在圖9-3中，最初所有三個(gè)進(jìn)程都就緒要運(yùn)行，優(yōu)先級(jí)最高的進(jìn)程A被選中，并準(zhǔn)許它運(yùn)行直到它在10ms時(shí)完成，如圖9-3中的RMS一行所示。在進(jìn)程A完成之后，進(jìn)程B和C以先后次序運(yùn)行。合起來，這些進(jìn)程運(yùn)行花費(fèi)了30ms時(shí)間，所以當(dāng)C完成的時(shí)候，正是A再次運(yùn)行的時(shí)候。這一輪換持續(xù)進(jìn)行直到t=70時(shí)系統(tǒng)變?yōu)榭臻e。在t=80時(shí)，進(jìn)程B就緒并開始運(yùn)行。然而，在t=90時(shí)，優(yōu)先級(jí)更高的進(jìn)程A變?yōu)榫途w，所以它搶占B并運(yùn)行，直到在t=100時(shí)完成。在這一時(shí)刻，系統(tǒng)可以在結(jié)束進(jìn)程B或者開始進(jìn)程C之間進(jìn)行選擇，所以它選擇優(yōu)先級(jí)最高的進(jìn)程B。9.2.3速率單調(diào)調(diào)度在圖9-3中，最初所有三個(gè)進(jìn)程都就9.2.4最早最終時(shí)限優(yōu)先調(diào)度另一個(gè)流行的實(shí)時(shí)調(diào)度算法是最早最終時(shí)限優(yōu)先（EarliestDeadtimeFirst,EDF）算法。EDF是一個(gè)動(dòng)態(tài)算法，它不像速率單調(diào)算法那樣要求進(jìn)程是周期性的。它也不像RMS那樣要求每個(gè)CPU突發(fā)有相同的運(yùn)行時(shí)間。只要一個(gè)進(jìn)程需要CPU時(shí)間，它就宣布它的到來和最終時(shí)限。調(diào)度程序維持一個(gè)可運(yùn)行進(jìn)程的列表，該列表按最終時(shí)限排序。EDF算法運(yùn)行列表中的第一個(gè)進(jìn)程，也就是具有最近最終時(shí)限的進(jìn)程。當(dāng)一個(gè)新的進(jìn)程就緒時(shí)，系統(tǒng)進(jìn)行檢查以了解其最終時(shí)限是否發(fā)生在當(dāng)前運(yùn)行的進(jìn)程結(jié)束之前。如果是這樣，新的進(jìn)程就搶占當(dāng)前正在運(yùn)行的進(jìn)程。9.2.4最早最終時(shí)限優(yōu)先調(diào)度另一個(gè)流行的實(shí)時(shí)調(diào)度算法是9.2.4最早最終時(shí)限優(yōu)先調(diào)度圖9-3給出了EDF的一個(gè)例子。最初所有三個(gè)進(jìn)程都是就緒的，它們按其最終時(shí)限的次序運(yùn)行。進(jìn)程A必須在t=30之前結(jié)束，B必須在t=40之前結(jié)束，C必須在t=50之前結(jié)束，所以A具有最早的最終時(shí)限并因此而先運(yùn)行。直到t=90，選擇都與RMS相同。在t=90時(shí)，A再次就緒，并且其最終時(shí)限為t=120，與B的最終時(shí)限相同。調(diào)度程序可以合理地選擇其中任何一個(gè)運(yùn)行，但是由于搶占B具有某些非零的代價(jià)與之相聯(lián)系，所以最好是讓B繼續(xù)運(yùn)行，而不去承擔(dān)切換的代價(jià)。9.2.4最早最終時(shí)限優(yōu)先調(diào)度圖9-3給出了EDF的一個(gè)9.2.4最早最終時(shí)限優(yōu)先調(diào)度為了消除RMS和EDF總是給出相同結(jié)果的想法，現(xiàn)在讓我們看一看另外一個(gè)例子，如圖9-4所示。9.2.4最早最終時(shí)限優(yōu)先調(diào)度為了消除RMS和EDF總是圖9-4以RMS和EDF進(jìn)行實(shí)時(shí)調(diào)度的另一個(gè)例子圖9-4以RMS和EDF進(jìn)行實(shí)時(shí)調(diào)度的另一個(gè)例子329.2.4最早最終時(shí)限優(yōu)先調(diào)度在這個(gè)例子中，進(jìn)程A、B和C的周期與前面的例子相同，但是現(xiàn)在A每次突發(fā)需要15ms的CPU時(shí)間，而不是只有10ms?？烧{(diào)度性測(cè)試計(jì)算CPU的利用率為0.500+0.375+0.100=0.975。CPU只留下了25%，但是在理論上CPU并沒有被超額預(yù)定，找到一個(gè)合理的調(diào)度應(yīng)該是可能的。對(duì)于RMS，三個(gè)進(jìn)程的優(yōu)先級(jí)仍為33、25和20，因?yàn)閮?yōu)先級(jí)只與周期有關(guān)系。這一次，進(jìn)程B直到t=30才結(jié)束，在這一時(shí)刻，進(jìn)程A再次就緒要運(yùn)行。等到A結(jié)束時(shí)，t=45，此時(shí)B再次就緒，由于它的優(yōu)先級(jí)高于C，所以B運(yùn)行而C則錯(cuò)過了其最終時(shí)限。RMS失敗。9.2.4最早最終時(shí)限優(yōu)先調(diào)度在這個(gè)例子中，進(jìn)程A、B和9.2.4最早最終時(shí)限優(yōu)先調(diào)度現(xiàn)在看一看EDF如何處理這種情況。當(dāng)t=30時(shí)，在A2和C1之間存在競爭。因?yàn)镃1的最終時(shí)限是50，而A2的最終時(shí)限是60，所以C被調(diào)度。這就不同于RMS，在RMS中A由于較高的優(yōu)先級(jí)而成為贏家。當(dāng)t=90時(shí)，A第四次就緒。A的最終時(shí)限與當(dāng)前進(jìn)程相同（同為120），所以調(diào)度程序面臨搶占與否的選擇。如前所述，如果不是必要最好不要搶占，所以B3被允許完成。9.2.4最早最終時(shí)限優(yōu)先調(diào)度現(xiàn)在看一看EDF如何處理這9.2.4最早最終時(shí)限優(yōu)先調(diào)度在圖9-4所示的例子中，直到t=150，CPU都是100％被占用的。然而，因?yàn)镃PU只有97.5％被利用，所以最終將會(huì)出現(xiàn)間隙。由于所有開始和結(jié)束時(shí)間都是5ms的倍數(shù)，所以間隙將是5ms。為了獲得要求的2.5%的空閑時(shí)間，5ms的間隙必須每200ms出現(xiàn)一次，這就是間隙為什么沒有在圖9-4中出現(xiàn)的原因。9.2.4最早最終時(shí)限優(yōu)先調(diào)度在圖9-4所示的例子中，直9.2.4最早最終時(shí)限優(yōu)先調(diào)度根本上，使用靜態(tài)優(yōu)先級(jí)只有在CPU的利用率不太高的時(shí)候才能工作。對(duì)于m=3、4、5、10、20和100，最大允許利用率為0.780、0.757、0.743、0.718、0.705和0.696。隨著m→∞，最大利用率逼近ln2。換句話說，對(duì)于三個(gè)進(jìn)程，如果CPU利用率等于或小于0.780，那么RMS總是可以工作的。在第一個(gè)例子中，CPU利用率為0.808而RMS工作正常，但那只不過是幸運(yùn)罷了。對(duì)于不同的周期和運(yùn)行時(shí)間，利用率為0.808很可能會(huì)失敗。在第二個(gè)例子中，CPU利用率如此之高（0.975），根本不存在RMS能夠工作的希望。9.2.4最早最終時(shí)限優(yōu)先調(diào)度根本上，使用靜態(tài)優(yōu)先級(jí)只有9.2.4最早最終時(shí)限優(yōu)先調(diào)度與此相對(duì)照，EDF對(duì)于任意一組可調(diào)度的進(jìn)程總是可以工作的，它可以達(dá)到100％的CPU利用率，付出的代價(jià)是更為復(fù)雜的算法。因而，在一個(gè)實(shí)際的視頻服務(wù)器中，如果CPU利用率低于RMS限度，可以使用RMS，否則，應(yīng)該選擇EDF。9.2.4最早最終時(shí)限優(yōu)先調(diào)度與此相對(duì)照，EDF對(duì)于任意9.3多媒體文件系統(tǒng)多媒體文件系統(tǒng)使用了與傳統(tǒng)文件系統(tǒng)不同的范型。在傳統(tǒng)的文件I/O系統(tǒng)中，進(jìn)程要訪問一個(gè)文件時(shí)，首先要發(fā)出open系統(tǒng)調(diào)用。如果該調(diào)用成功，則調(diào)用者被給予某種令牌以便在未來的調(diào)用中使用，該令牌在UNIX中被稱為文件描述符，在Windows中被稱為句柄。這時(shí)，進(jìn)程可以發(fā)出read系統(tǒng)調(diào)用，提供令牌、緩沖區(qū)地址和字節(jié)計(jì)數(shù)作為參數(shù)。操作系統(tǒng)則在緩沖區(qū)中返回請(qǐng)求的數(shù)據(jù)。以后還可以發(fā)出另外的read調(diào)用，直到進(jìn)程結(jié)束。在進(jìn)程結(jié)束時(shí)它將調(diào)用close以關(guān)閉文件并返回其資源。9.3多媒體文件系統(tǒng)多媒體文件系統(tǒng)使用了與傳統(tǒng)文件系統(tǒng)不9.3多媒體文件系統(tǒng)由于實(shí)時(shí)行為的需要，這一模型對(duì)于多媒體并不能很好地工作，尤其是在顯示來自遠(yuǎn)程視頻服務(wù)器的多媒體文件時(shí)，該模型的工作效果更差。第一個(gè)問題是用戶必須以相當(dāng)精確的時(shí)間間隔進(jìn)行read調(diào)用，第二個(gè)問題是視頻服務(wù)器必須能夠沒有延遲地提供數(shù)據(jù)塊。但是，當(dāng)請(qǐng)求沒有計(jì)劃地到來并且預(yù)先沒有保留資源時(shí)，做到這一點(diǎn)是十分困難的。9.3多媒體文件系統(tǒng)由于實(shí)時(shí)行為的需要，這一模型對(duì)于多媒9.3多媒體文件系統(tǒng)為解決這些問題，多媒體文件服務(wù)器使用了一個(gè)完全不同的范型：像錄像機(jī)（VCR）一樣工作。為了讀取一個(gè)多媒體文件，用戶進(jìn)程發(fā)出start系統(tǒng)調(diào)用，指定要讀的文件（如哪些音頻和字幕軌跡）和各種其他參數(shù)。接著，視頻服務(wù)器開始以必要的速率送出幀，然后用戶進(jìn)程以幀進(jìn)來的速率對(duì)它們進(jìn)行處理。如果用戶對(duì)所看的電影感到厭煩，發(fā)出stop系統(tǒng)調(diào)用可以將數(shù)據(jù)流終止。具有這種數(shù)據(jù)流模型的文件服務(wù)器通常被稱為推送型服務(wù)器，因?yàn)樗鼘?shù)據(jù)推送給用戶。而在傳統(tǒng)的拉取型服務(wù)器中，用戶不得不通過重復(fù)地調(diào)用read一塊接一塊地取得數(shù)據(jù)，每調(diào)用一次可以拉取出一塊數(shù)據(jù)。這兩個(gè)模型之間的區(qū)別如圖9-5所示。9.3多媒體文件系統(tǒng)為解決這些問題，多媒體文件服務(wù)器使用圖9-5不同范型多媒體服務(wù)器的區(qū)別圖9-5不同范型多媒體服務(wù)器的區(qū)別419.3.1VCR控制功能大多數(shù)視頻服務(wù)器實(shí)現(xiàn)了標(biāo)準(zhǔn)的VCR控制功能，包括暫停、快進(jìn)和倒帶。暫停是相當(dāng)簡單的：用戶發(fā)送一個(gè)消息給視頻服務(wù)器，告訴它停止。視頻服務(wù)器此時(shí)要做的全部事情是記住下一次要送出的是哪一幀。當(dāng)用戶要求服務(wù)器恢復(fù)播放時(shí)，服務(wù)器只要從它停止的地方繼續(xù)就可以了。然而，這里存在著一個(gè)復(fù)雜因素，服務(wù)器應(yīng)該為每個(gè)流出的數(shù)據(jù)流保留諸如磁盤帶寬和內(nèi)存緩沖區(qū)等資源。當(dāng)電影暫停時(shí)繼續(xù)占用這些資源將造成浪費(fèi)，特別是如果用戶打算轉(zhuǎn)而暫時(shí)去做另外一件事情的時(shí)候。當(dāng)然，在暫停的時(shí)候可以很容易地將資源釋放，但是這引入了風(fēng)險(xiǎn)：當(dāng)用戶試圖恢復(fù)播放的時(shí)候，有可能無法重新獲得這些資源。9.3.1VCR控制功能大多數(shù)視頻服務(wù)器實(shí)現(xiàn)了標(biāo)準(zhǔn)的VC9.3.1VCR控制功能真正的倒帶實(shí)際上非常簡單，沒有任何復(fù)雜性。服務(wù)器要做的全部事情就是注意到下一次要送出的幀是第0幀。還有比這更容易的嗎？然而，快進(jìn)和快倒（也就是在倒帶的同時(shí)播放）就難處理多了。如果沒有壓縮，那么以10倍的速度前進(jìn)的一種方法是每10幀只顯示一幀，以20倍的速度前進(jìn)則要求每20幀顯示一幀。實(shí)際上，在不存在壓縮的情況下，以任意速度前進(jìn)和后退都是十分容易的。要以正常速度的k倍運(yùn)行，只要每k幀顯示一幀就可以了。要以正常速度的k倍后退，只要沿另一個(gè)方向做相同的事情就可以了。這一方法在推送型服務(wù)器和拉取型服務(wù)器上工作得同樣好。9.3.1VCR控制功能真正的倒帶實(shí)際上非常簡單，沒有任9.3.1VCR控制功能壓縮則使快進(jìn)和快倒復(fù)雜起來。對(duì)于便攜式攝像機(jī)的DV磁帶，由于其每一幀都是獨(dú)立于其他幀而壓縮的，所以只要能夠快速地找到所需要的幀，使用這一策略還是有可能的。由于視其內(nèi)容不同每一幀的壓縮量也有所不同，所以每一幀具有不同的大小，因而在文件中向前跳過k幀并不能通過數(shù)字計(jì)算來完成。此外，音頻壓縮是獨(dú)立于視頻壓縮的，所以對(duì)于在高速模式中顯示的每一視頻幀，還必須找到正確的音頻幀（除非在高于正常速度播放時(shí)將聲音關(guān)閉）。因此，對(duì)一個(gè)DV文件進(jìn)行快進(jìn)操作需要有一個(gè)索引，該索引可以使幀的查找快速地實(shí)現(xiàn)，但是至少在理論上這樣做是可行的。9.3.1VCR控制功能壓縮則使快進(jìn)和快倒復(fù)雜起來。對(duì)于9.3.1VCR控制功能對(duì)于MPEG，由于使用I幀、P幀和B幀，這一方案即使在理論上也是不能工作的。向前跳過k幀（就算假設(shè)能這樣做）可能落在一個(gè)P幀上，而這個(gè)P幀則基于剛剛跳過的一個(gè)I幀。沒有基本幀，只有從基本幀發(fā)生的增量變化（這正是P幀所包含的）是無用的。MPEG要求按順序播放文件。9.3.1VCR控制功能對(duì)于MPEG，由于使用I幀、P幀9.3.1VCR控制功能克服這一難題的另一個(gè)方法是實(shí)際嘗試以10倍的速度順序地播放文件。然而，這樣做就要求以10倍的速度將數(shù)據(jù)拉出磁盤。此時(shí)，服務(wù)器可能試圖將幀解壓縮（這是正常情況下服務(wù)器不需要做的事情），判定需要哪一幀，然后每隔10幀重新壓縮成一個(gè)I幀。然而，這樣做給服務(wù)器增加了沉重的負(fù)擔(dān)。這一方法還要求服務(wù)器了解壓縮格式，正常情況下服務(wù)器不必了解這些東西。作為替代，可以通過網(wǎng)絡(luò)實(shí)際發(fā)送所有的數(shù)據(jù)給用戶，并在用戶端選出正確的幀，這樣做就要求網(wǎng)絡(luò)以10倍的速度運(yùn)行，這或許是可行的，但是在這么高的速度下正常操作肯定不是一件容易的事情。9.3.1VCR控制功能克服這一難題的另一個(gè)方法是實(shí)際嘗9.3.1VCR控制功能總而言之，不存在容易的方法。唯一可行的策略是要求預(yù)先規(guī)劃。可以做的事情是建立一個(gè)特殊的文件，包含每隔10幀中的一幀，并且將該文件以通常的MPEG算法進(jìn)行壓縮。這個(gè)文件是“快進(jìn)”的文件。要切換到快進(jìn)模式，服務(wù)器必須判定在快進(jìn)文件中用戶當(dāng)前所在的位置。例如，如果當(dāng)前幀是48210并且快進(jìn)文件以10倍的速度運(yùn)行，那么服務(wù)器在快進(jìn)文件中必須定位到4821幀并且在此處以正常速度開始播放。當(dāng)然，這一幀可能是P幀或B幀，但是客戶端的解碼進(jìn)程可以簡單地跳過若干幀直到看見一個(gè)I幀。利用特別準(zhǔn)備的快倒文件，可以用類似的方法實(shí)現(xiàn)快倒。9.3.1VCR控制功能總而言之，不存在容易的方法。唯一9.3.1VCR控制功能當(dāng)用戶切換回到正常速度時(shí)，必須使用相反的技巧。如果在快進(jìn)文件中當(dāng)前幀是5734，服務(wù)器只要切換回到常規(guī)文件并且從57340幀處繼續(xù)播放。同樣，如果這一幀不是一個(gè)I幀，客戶端的解碼進(jìn)程必須忽略所有的幀直到看見一個(gè)I幀。盡管有了這兩個(gè)額外的文件可以做這些工作，這一方案還是有某些缺點(diǎn)。首先，需要某些額外的磁盤空間來存放額外的文件。其次，快進(jìn)和倒帶只能以對(duì)應(yīng)于特別文件的速度進(jìn)行。第三，在常規(guī)文件，快進(jìn)文件和快倒文件之間來回切換需要額外的復(fù)雜算法。9.3.1VCR控制功能當(dāng)用戶切換回到正常速度時(shí)，必須使9.3.2近似視頻點(diǎn)播有k個(gè)用戶取得相同的電影和這些用戶取得k部不同的電影在本質(zhì)上給服務(wù)器施加了相同的工作量。然而，通過對(duì)模型做一個(gè)小小的修改，就可能獲得巨大的性能改進(jìn)。視頻點(diǎn)播面臨的問題是用戶可能在任意時(shí)刻開始觀看一部電影，所以，如果有100個(gè)用戶全部在晚8點(diǎn)左右開始觀看某個(gè)新電影，很可能不會(huì)有兩個(gè)用戶在完全相同的時(shí)刻開始，所以他們無法共享一個(gè)數(shù)據(jù)流。使優(yōu)化成為可能的修改是，通知所有用戶電影只在整點(diǎn)和隨后每隔（例如）5分鐘開始。因此，如果一個(gè)用戶想在8:02看一部電影，那么他必須等到8:05。9.3.2近似視頻點(diǎn)播有k個(gè)用戶取得相同的電影和這些用戶9.3.2近似視頻點(diǎn)播這樣做的收益是，不管存在多少客戶，對(duì)于一部2小時(shí)的電影，只需要24個(gè)數(shù)據(jù)流。如圖9-6所示，第一個(gè)數(shù)據(jù)流開始于8:00。在8:05，當(dāng)?shù)谝粋€(gè)數(shù)據(jù)流處于第9000幀時(shí)，第二個(gè)數(shù)據(jù)流開始。在8:10，當(dāng)?shù)谝粋€(gè)數(shù)據(jù)流處于第18000幀并且第二個(gè)數(shù)據(jù)流處于第9000幀時(shí)，第三個(gè)數(shù)據(jù)流開始，以此類推直到第24個(gè)數(shù)據(jù)流開始于9:55。在10:00，第一個(gè)數(shù)據(jù)流終止并且再一次從第0幀開始。這一方案稱為近似視頻點(diǎn)播，因?yàn)橐曨l并不是完全隨著點(diǎn)播而開始，而是在點(diǎn)播之后不久開始。9.3.2近似視頻點(diǎn)播這樣做的收益是，不管存在多少客戶，圖9-6近似視頻點(diǎn)播以規(guī)則的間隔開始一個(gè)新的數(shù)據(jù)流，本例中間隔5分鐘（9000幀）圖9-6近似視頻點(diǎn)播以規(guī)則的間隔開始一個(gè)新的數(shù)據(jù)流，本例519.3.2近似視頻點(diǎn)播這里的關(guān)鍵參數(shù)是多長時(shí)間開始一個(gè)數(shù)據(jù)流。如果每2分鐘開始一個(gè)數(shù)據(jù)流，那么對(duì)于一部2小時(shí)的電影來說就需要60個(gè)數(shù)據(jù)流，但是開始觀看的最大等待時(shí)間是2分鐘。運(yùn)營商必須判定人們?cè)敢獾却嚅L時(shí)間，因?yàn)槿藗冊(cè)敢獾却臅r(shí)間越長，系統(tǒng)效率就越高，并且同時(shí)能夠被觀看的電影就越多。一個(gè)替代的策略是同時(shí)提供不用等待的選擇權(quán)，在這種情況下，新的數(shù)據(jù)流可以立刻開始，但是需要對(duì)系統(tǒng)做更多的修改以支持即時(shí)啟動(dòng)。9.3.2近似視頻點(diǎn)播這里的關(guān)鍵參數(shù)是多長時(shí)間開始一個(gè)數(shù)9.3.2近似視頻點(diǎn)播在某種意義上，視頻點(diǎn)播如同使用出租車：一招手它就來。近似視頻點(diǎn)播如同使用公共汽車：它有著固定的時(shí)刻表，乘客必須等待下一輛。于是，播放最新大片可能吸引足夠的客戶，從而保證每5分鐘開始一個(gè)新的數(shù)據(jù)流；但是對(duì)于傳統(tǒng)經(jīng)典影片，最好還是簡單地在點(diǎn)播的基礎(chǔ)上播映。將近似視頻點(diǎn)播（為的是效率）加上每個(gè)個(gè)體觀眾完全的VCR控制（為的是方便用戶）是一種理想的組合。通過對(duì)模型進(jìn)行略微的修正，這樣的設(shè)計(jì)是有可能的，即具有VCR功能的近似視頻點(diǎn)播。9.3.2近似視頻點(diǎn)播在某種意義上，視頻點(diǎn)播如同使用出租9.4文件存放多媒體文件非常龐大，通常只寫一次而讀許多次，并且傾向于被順序訪問。它們的回放還必須滿足嚴(yán)格的服務(wù)質(zhì)量標(biāo)準(zhǔn)。總而言之，這些要求暗示著不同于傳統(tǒng)操作系統(tǒng)使用的文件系統(tǒng)布局。9.4文件存放多媒體文件非常龐大，通常只寫一次而讀許多次9.4.1在單個(gè)磁盤上存放文件最為重要的要求是數(shù)據(jù)能夠以必要的速度流出到網(wǎng)絡(luò)或輸出設(shè)備上，并且沒有顫動(dòng)。為此，在傳輸一幀的過程中有多次尋道是極其不受歡迎的。在視頻服務(wù)器上消除文件內(nèi)尋道的一種方法是使用連續(xù)的文件。通常，在預(yù)先精心裝載了電影的視頻服務(wù)器上它工作得還是不錯(cuò)的，因?yàn)檫@些電影后來不會(huì)再發(fā)生變化。9.4.1在單個(gè)磁盤上存放文件最為重要的要求是數(shù)據(jù)能夠以9.4.1在單個(gè)磁盤上存放文件然而，視頻、音頻和文本的存在是一個(gè)復(fù)雜因素，即使視頻、音頻和文本每個(gè)都存儲(chǔ)為單獨(dú)的連續(xù)文件，從視頻文件到音頻文件，再從音頻文件到文本文件的尋道在需要的時(shí)候還是免不了的。這使人想起第二種可能的存儲(chǔ)排列，使視頻、音頻和文本交叉存放，但是整個(gè)文件還是連續(xù)的，如圖9-7所示。此處，直接跟隨第1幀視頻的是第1幀的各種音頻軌跡，然后是第1幀的各種文本軌跡，根據(jù)存在多少音頻和文本軌跡，最簡單的可能是在一次磁盤讀操作中讀入每一幀的全部內(nèi)容，然后只將需要的部分傳輸給用戶。9.4.1在單個(gè)磁盤上存放文件然而，視頻、音頻和文本的存圖9-7每部電影在一個(gè)連續(xù)文件中交叉存放視頻、音頻和文本圖9-7每部電影在一個(gè)連續(xù)文件中579.4.1在單個(gè)磁盤上存放文件這一組織需要額外的磁盤I/O讀入不必要的音頻和文本，在內(nèi)存中還需要額外的緩沖區(qū)空間存放它們?？墒撬怂械膶さ溃ㄔ趩斡脩粝到y(tǒng)上），并且不需要任何系統(tǒng)開銷跟蹤哪一幀在磁盤上的什么地方，因?yàn)檎侩娪按娣旁谝粋€(gè)連續(xù)文件中。以這樣的布局，隨機(jī)訪問是不可能的，但是如果不需要隨機(jī)訪問，這點(diǎn)損失并不嚴(yán)重。類似地，如果沒有額外的數(shù)據(jù)結(jié)構(gòu)和復(fù)雜性，快進(jìn)和快倒也是不可能的。9.4.1在單個(gè)磁盤上存放文件這一組織需要額外的磁盤I/9.4.1在單個(gè)磁盤上存放文件在具有多個(gè)并發(fā)輸出流的視頻服務(wù)器上，使整部電影成為一個(gè)連續(xù)文件的優(yōu)點(diǎn)就失去了，因?yàn)閺囊徊侩娪白x取一幀之后，磁盤可能不得不從許多其他電影讀入幀，然后才能返回到第一部電影。同樣，對(duì)于一部電影既可以讀也可以寫的系統(tǒng)（例如用于視頻生產(chǎn)或編輯的系統(tǒng)）來說，使用巨大的連續(xù)文件是很困難的。9.4.1在單個(gè)磁盤上存放文件在具有多個(gè)并發(fā)輸出流的視頻9.4.2兩個(gè)替代的文件組織策略這些考慮導(dǎo)致產(chǎn)生兩個(gè)針對(duì)多媒體文件的文件存放組織。第一個(gè)是小塊模型，如圖9-8a）所示。在這種組織中，選定磁盤塊的大小比幀的平均大小，甚至是比P幀和B幀的大小要小得多。對(duì)于每秒30幀以4Mbps速率傳輸?shù)腗PEG-2而言，幀的平均大小為16KB，所以一個(gè)磁盤塊的大小為1KB或2KB工作得比較好。這里的思想是每部電影有一個(gè)幀索引，這是一個(gè)數(shù)據(jù)結(jié)構(gòu)，每一幀有一個(gè)幀索引項(xiàng)，指向幀的開始。每一幀本身是一連串連續(xù)的塊，包含該幀所有的視頻、音頻和文本軌跡，如圖9-8中所示。9.4.2兩個(gè)替代的文件組織策略這些考慮導(dǎo)致產(chǎn)生兩個(gè)針對(duì)圖9-8不連續(xù)的電影存儲(chǔ)圖9-8不連續(xù)的電影存儲(chǔ)619.4.2兩個(gè)替代的文件組織策略這樣，讀第k幀時(shí)首先要在幀索引中找到第k個(gè)索引項(xiàng)，然后在一次磁盤操作中將整個(gè)幀讀入。由于不同的幀具有不同的大小，所以在幀索引中需要有表示幀大小的字段（以塊為單位），即便對(duì)于1KB大小的磁盤塊，8位的字段也可以處理最大為255KB的幀，這對(duì)于一個(gè)未壓縮NTSC幀來說，就算它有許多音頻軌跡也已經(jīng)足夠了。存放電影的另一個(gè)方法是使用大磁盤塊（比如256KB），并且在每一塊中放入多個(gè)幀，如圖9-8b）所示。這里仍然需要一個(gè)索引，但是這次不是幀索引而是塊索引。一般而言，一個(gè)磁盤塊擁有的幀的數(shù)目不見得是整數(shù)，所以需要做某些機(jī)制來處理這一問題。解決這一問題有兩種選擇。9.4.2兩個(gè)替代的文件組織策略這樣，讀第k幀時(shí)首先要在9.4.2兩個(gè)替代的文件組織策略第一種選擇如圖9-8b）所示，當(dāng)下一幀填不滿當(dāng)前磁盤塊的時(shí)候，則磁盤塊剩余的部分就保持空閑伏態(tài)。這一浪費(fèi)的空間就是內(nèi)部碎片，與具有固定大小頁面的虛擬內(nèi)存系統(tǒng)中的內(nèi)部碎片相同。但是，這樣做在一幀的中間決不需要進(jìn)行尋道。另一種選擇是填充每一磁盤塊到盡頭，將幀分裂開使其跨越磁盤塊。這一選擇在幀的中間引入尋道的需要，這將損害性能，但是由于消除了內(nèi)部碎片而節(jié)約了磁盤空間。9.4.2兩個(gè)替代的文件組織策略第一種選擇如圖9-8b9.4.2兩個(gè)替代的文件組織策略作為對(duì)比，圖9-8a）中小塊的使用也會(huì)浪費(fèi)某些磁盤空間，因?yàn)樵诿恳粠淖詈笠粔K可能有一小部分未被使用。對(duì)于1KB的磁盤塊和一部由216000幀組成的2小時(shí)的NTSC電影，浪費(fèi)的磁盤空間總共只有3.6GB中的大約108KB。圖9-8b）浪費(fèi)的磁盤空間計(jì)算起來非常困難，但是肯定多很多，因?yàn)樵谝粋€(gè)磁盤塊的盡頭有時(shí)會(huì)留下100KB的空間，而下一幀是一個(gè)比它大的I幀。9.4.2兩個(gè)替代的文件組織策略作為對(duì)比，圖9-8a）9.4.2兩個(gè)替代的文件組織策略另一方面，塊索引比幀索引要小很多。對(duì)于256KB的塊，如果幀的平均大小為16KB，那么一個(gè)塊大約可以裝下16個(gè)幀，所以一部由216000幀組成的電影在塊索引中只需要有13500個(gè)索引項(xiàng)，與此相對(duì)比，對(duì)于幀索引則需要216000個(gè)索引項(xiàng)。因?yàn)樾阅艿脑?，在這兩種情形中索引都應(yīng)該列出所有的幀或磁盤塊（也就是說不像UNIX那樣有間接塊）所以塊索引在內(nèi)存中占用了13500個(gè)8字節(jié)的項(xiàng)（4個(gè)字節(jié)用于磁盤地址，l個(gè)字節(jié)用于幀的大小，3個(gè)字節(jié)用于起始幀的幀號(hào)），幀索引則在內(nèi)存中占用了216000個(gè)5字節(jié)的項(xiàng)（只有磁盤地址和幀的大?。容^起來，當(dāng)電影在播放時(shí)，塊索引比幀索引節(jié)省了接近1MB的RAM空間。9.4.2兩個(gè)替代的文件組織策略另一方面，塊索引比幀索引9.4.2兩個(gè)替代的文件組織策略這些考慮導(dǎo)出了如下的權(quán)衡：1）幀索引：電影在播放時(shí)使用大量的RAM；磁盤浪費(fèi)小。2）塊索引（禁止分裂幀跨越磁盤塊）：RAM用量低；磁盤浪費(fèi)較大。3）塊索引（允許分裂幀跨越磁盤塊）：RAM用量低；無磁盤浪費(fèi)；需要額外尋道。9.4.2兩個(gè)替代的文件組織策略這些考慮導(dǎo)出了如下的權(quán)衡9.4.2兩個(gè)替代的文件組織策略因此，這里的權(quán)衡涉及回放時(shí)RAM的使用量、自始至終浪費(fèi)的磁盤空間以及由于額外尋道造成的回放時(shí)的性能損失。但是，這些問題可以用各種方法來解決。采用分頁操作在需要的時(shí)候及時(shí)將幀索引裝入內(nèi)存，可以減少RAM的使用量。通過足夠的緩沖可以屏蔽在幀傳輸過程中的尋道，但是這需要額外的內(nèi)存并且可能還需要額外的復(fù)制操作。好的設(shè)計(jì)必須仔細(xì)分析所有這些因素，并且為即將投入的應(yīng)用做出良好的選擇。9.4.2兩個(gè)替代的文件組織策略因此，這里的權(quán)衡涉及回放9.4.3近似視頻點(diǎn)播的文件存放前面我們了解了視頻點(diǎn)播的文件存放策略。對(duì)于近似視頻點(diǎn)播，采用不同的文件存放策略可以獲得更高的效率。近似視頻點(diǎn)播將同一部電影作為多個(gè)交錯(cuò)的數(shù)據(jù)流送出。即使電影是作為連續(xù)文件存放的，每個(gè)數(shù)據(jù)流也需要進(jìn)行尋道。有研究者設(shè)計(jì)了一種文件存放策略幾乎可以消除全部這樣的尋道。圖9-9說明了這一方法的應(yīng)用，圖中的電影以每秒30幀的速率播放，每隔5分鐘開始一個(gè)新的數(shù)據(jù)流（參見圖9-6）。根據(jù)這些參數(shù)，2小時(shí)長的電影需要24個(gè)當(dāng)前數(shù)據(jù)流。9.4.3近似視頻點(diǎn)播的文件存放前面我們了解了視頻點(diǎn)播的圖9-9針對(duì)近似視頻點(diǎn)播的優(yōu)化幀存放策略圖9-9針對(duì)近似視頻點(diǎn)播的優(yōu)化幀存放策略699.4.3近似視頻點(diǎn)播的文件存放在這一存放策略中，由24個(gè)幀組成的幀集合連成一串并且作為一個(gè)記錄寫入磁盤。它們還可以在一個(gè)讀操作中被讀回?？紤]這樣一個(gè)瞬間，數(shù)據(jù)流24恰好開始，它需要的是第0幀，5分鐘前開始的數(shù)據(jù)流23需要的是第9000幀；數(shù)據(jù)流22需要的是第18000幀，以此類推，直到數(shù)據(jù)流0，它需要的是第20700幀。通過將這些幀連續(xù)地存放在一個(gè)磁道上，視頻服務(wù)器只用一次尋道（到第0幀）就可以以相反的順序滿足全部24個(gè)數(shù)據(jù)流的需要。當(dāng)然，如果存在某一原因要以升序?yàn)閿?shù)據(jù)流提供服務(wù)，這些幀也可以以相反的順序存放在磁盤上。9.4.3近似視頻點(diǎn)播的文件存放在這一存放策略中，由249.4.3近似視頻點(diǎn)播的文件存放完成對(duì)最后一個(gè)數(shù)據(jù)流的服務(wù)之后，磁盤臂可以移到磁道2準(zhǔn)備再次為這些數(shù)據(jù)流服務(wù)。這一方法不要求整個(gè)文件是連續(xù)的，但是對(duì)于若干個(gè)同時(shí)的數(shù)據(jù)流仍然給予了良好的性能。簡單的緩沖策略是使用雙緩沖。當(dāng)一個(gè)緩沖區(qū)正在向外播放24個(gè)數(shù)據(jù)流的時(shí)候，另一個(gè)緩沖區(qū)正在預(yù)先加載數(shù)據(jù)。當(dāng)前操作結(jié)束時(shí)，兩個(gè)緩沖區(qū)進(jìn)行交換，剛才用于回放的緩沖區(qū)現(xiàn)在在一個(gè)磁盤操作中加載數(shù)據(jù)。9.4.3近似視頻點(diǎn)播的文件存放完成對(duì)最后一個(gè)數(shù)據(jù)流的服9.4.4在單個(gè)磁盤上存放多個(gè)文件實(shí)際上，在視頻服務(wù)器上當(dāng)然存在著許多電影。如果它們隨機(jī)地散布在磁盤上，那么當(dāng)多部電影被不同的客戶同時(shí)觀看時(shí)，時(shí)間將浪費(fèi)在磁頭在電影之間來回移動(dòng)上。通過在磁盤上存放電影時(shí)將電影的流行性考慮進(jìn)去，可以改進(jìn)這一情況。9.4.4在單個(gè)磁盤上存放多個(gè)文件實(shí)際上，在視頻服務(wù)器上9.4.4在單個(gè)磁盤上存放多個(gè)文件對(duì)于許多種類的流行性事件，相對(duì)流行性的一個(gè)合理的近似遵循著一種令人驚奇的可預(yù)測(cè)模式。這一模式是哈佛大學(xué)的一位語言學(xué)教授GeorgeZipf（1902-1950）發(fā)現(xiàn)的，被稱為Zipf定律。該定律說的是，如果電影，圖書、Web網(wǎng)頁或者單詞按其流行性進(jìn)行排名，那么下一個(gè)客戶選擇排行榜中排名為k的項(xiàng)的概率是C/k。因而，前三部電影的命中率分別是C/1、C/2和C/3，其中C的計(jì)算要使全部項(xiàng)的和為1（歸一化常數(shù)）。換句話說，如果有N部電影，那么

C/1+C/2+C/3+C/4+…＋C/N=19.4.4在單個(gè)磁盤上存放多個(gè)文件對(duì)于許多種類的流行性事9.4.4在單個(gè)磁盤上存放多個(gè)文件從這一公式，C可以被計(jì)算出來。對(duì)于具有10個(gè)、100個(gè)、1000個(gè)和10000個(gè)項(xiàng)的總體，C的值分別是0.341、0.193、0.134和0.102。例如，對(duì)于1000部電影，前5部電影的概率分別是0.134、0.067、0.045、0.034和0.027。有趣的是，將Zpf定律應(yīng)用于美國20座最大城市的人口。Zpf定律預(yù)測(cè)第二大城市應(yīng)該具有最大城市一半的人口，第三大城市應(yīng)該具有最大城市三分之一的人口，以此類推雖然不盡完美，該定律卻令人驚奇地吻合。9.4.4在單個(gè)磁盤上存放多個(gè)文件從這一公式，C可以被計(jì)9.4.4在單個(gè)磁盤上存放多個(gè)文件對(duì)于視頻服務(wù)器上的電影而言，Zipf定律表明最流行的電影被選擇的次數(shù)是第二流行的電影的兩倍，是第三流行的電影的三倍，以此類推。盡管分布在開始時(shí)下降得相當(dāng)快，但是它有著一個(gè)長長的尾部，例如，排名50的電影擁有C/50的流行性，排名51的電影擁有C/51的流行性，所以排名51的電影的流行性是排名50的電影的50/51，只有大約2％的差額。隨著尾部進(jìn)一步延伸，相鄰電影間的百分比差額變得越來越小。一個(gè)結(jié)論就是，服務(wù)器需要大量的電影，因?yàn)閷?duì)于前l(fā)0名以外的電影存在著潛在的需求。9.4.4在單個(gè)磁盤上存放多個(gè)文件對(duì)于視頻服務(wù)器上的電影9.4.4在單個(gè)磁盤上存放多個(gè)文件了解不同電影的相對(duì)流行性，使得對(duì)視頻服務(wù)器的性能進(jìn)行建模以及將該信息應(yīng)用于存放文件成為可能。研究已經(jīng)表明，最佳的策略令人驚奇地簡單并且獨(dú)立于分布。這一策略稱為管風(fēng)琴算法（概率直方圖看起來像是一個(gè)稍稍不對(duì)稱的管風(fēng)琴）。該算法將最流行的電影存放在磁盤的中央，第二和第三流行的電影存放在最流行的電影的兩邊，在這幾部電影的外邊是排名第四和第五的電影，以此類推，如圖9-10所示。9.4.4在單個(gè)磁盤上存放多個(gè)文件了解不同電影的相對(duì)流行圖9-10視頻服務(wù)器上文件的管風(fēng)琴分布圖9-10視頻服務(wù)器上文件的管風(fēng)琴分布779.4.4在單個(gè)磁盤上存放多個(gè)文件如果每一部電影是如圖9-8所示類型的連續(xù)文件，這樣的存放方式工作得好；如果每一部電影被約束在一個(gè)狹窄的柱面范圍之內(nèi)，這樣的存放方式也可以擴(kuò)大其使用的范圍。該算法所做的是試圖將磁頭保持在磁盤的中央。當(dāng)服務(wù)器上的電影有1000部時(shí)，根據(jù)Zipf定律分布排在前5名的電影代表了0.307的總概率，這意味著大約30％的時(shí)間磁頭停留在為排在前5名的電影分配的柱面中，如果有1000部電影可用，這是一個(gè)驚人的數(shù)量。9.4.4在單個(gè)磁盤上存放多個(gè)文件如果每一部電影是如圖99.4.5在多個(gè)磁盤上存放文件為了獲得更高的性能，視頻服務(wù)器經(jīng)常擁有可以并行運(yùn)轉(zhuǎn)的很多磁盤，有時(shí)會(huì)用到RAID。視頻服務(wù)器通常希望高的性能而對(duì)于校正傳輸錯(cuò)誤不怎么太關(guān)心。此外，如果RAID控制器有太多的磁盤要同時(shí)處理，那么RAID控制器可能會(huì)成為一個(gè)瓶頸。更為普通的配置只是數(shù)目很多的磁盤，有時(shí)被稱為磁盤園。這些磁盤不像RAID那樣以同步方式旋轉(zhuǎn)，也不像RAID那樣包含奇偶校驗(yàn)位。一種可能的配置是將電影A存放在磁盤1上，將電影B存放在磁盤2上，以此類推，如圖9-11a）所示。實(shí)際上，使用新式的磁盤，每個(gè)磁盤上可以存放若干部電影。9.4.5在多個(gè)磁盤上存放文件為了獲得更高的性能，視頻服圖9-11在多個(gè)磁盤上組織多媒體文件的四種方式圖9-11在多個(gè)磁盤上組織多媒體文件的四種方式809.4.5在多個(gè)磁盤上存放文件這一組織方式實(shí)現(xiàn)起來很簡單，并且具有簡單明了的故障特性：如果一塊磁盤發(fā)生故障，其上的所有電影都將不再可用。注意，一家公司損失了一塊裝滿了電影的磁盤并沒有一家公司損失了一塊裝滿了數(shù)據(jù)的磁盤那么糟糕，因?yàn)殡娪斑€可以從DVD重新裝載到一塊空閑的磁盤中。這一方法的缺點(diǎn)是負(fù)載可能沒有很好地平衡，如果某些磁盤上裝載的是目前十分熱門的電影，而另外的磁盤上裝載的是不太流行約電影，則系統(tǒng)就沒有被充分利用。當(dāng)然，一旦知道了電影的使用頻率，那么手工移動(dòng)某些電影以平衡負(fù)載也是可能的。9.4.5在多個(gè)磁盤上存放文件這一組織方式實(shí)現(xiàn)起來很簡單9.4.5在多個(gè)磁盤上存放文件第二種可能的組織方式是將每一部電影在多塊磁盤上分成條帶，圖9-11b）所示為4部電影的例子。讓我們暫時(shí)假設(shè)所有的幀大小相同（也就是未壓縮）。固定的字節(jié)數(shù)從電影A寫入磁盤1，然后相同的字節(jié)數(shù)寫入磁盤2，直到到達(dá)最后一塊磁盤（在本例的情形中是A3單元）。然后，再次在第一塊磁盤處繼續(xù)分條帶操作，寫入A4單元，這樣進(jìn)行下去直到整個(gè)文件被寫完。電影B、C和D以同樣的模式分成條帶。9.4.5在多個(gè)磁盤上存放文件第二種可能的組織方式是將每9.4.5在多個(gè)磁盤上存放文件由于所有的電影在第一塊磁盤開始，這一條帶模式的一個(gè)可能的缺點(diǎn)是跨磁盤的負(fù)載可能不平衡。一種更好地分散負(fù)載的方法是交錯(cuò)起始磁盤，如圖9-11c）所示。還有一種試圖平衡負(fù)載的方法是對(duì)每一文件使用隨機(jī)的條帶模式，如圖9-11d）所示。9.4.5在多個(gè)磁盤上存放文件由于所有的電影在第一塊磁盤9.4.5在多個(gè)磁盤上存放文件到目前為止，我們一直假設(shè)所有的幀大小相同，而對(duì)于MPEG-2電影，這一假設(shè)是錯(cuò)誤的：I幀比P幀要大得多。有兩種方法可以處理這一新出現(xiàn)的問題：按幀分條帶或按塊分條帶。按幀分條帶時(shí)，電影A的第一幀作為連續(xù)的單位存放在磁盤l上，不管它有多大。下一幀存放在磁盤2上，以此類推。電影B以類似的方式分條帶，或者在同一塊磁盤上開始，或者在下一塊磁盤上開始（如果是交錯(cuò)條帶），或者是在隨機(jī)的一塊磁盤上開始。因?yàn)槊看巫x入一幀，這一條帶形式并沒有加快任何給定電影的讀入，然而它比圖9-11a）更好地在磁盤間分散了負(fù)載，如果有許多人決定今晚觀看電影A而沒有人想看電影C，圖9-11a）的表現(xiàn)將很糟糕。9.4.5在多個(gè)磁盤上存放文件到目前為止，我們一直假設(shè)所9.4.5在多個(gè)磁盤上存放文件總的來說，在所有的磁盤間分散負(fù)載將更好地利用總的磁盤帶寬，并因此而增加能夠服務(wù)的顧客數(shù)目。分條帶的另一種方法是按塊分條帶。對(duì)于每部電影，固定大小的單元連續(xù)（或隨機(jī)）寫到每塊磁盤上。每個(gè)塊包含一個(gè)或多個(gè)幀或者其中的碎片。對(duì)于同一部電影，系統(tǒng)現(xiàn)在可以發(fā)出對(duì)多個(gè)塊的請(qǐng)求每個(gè)請(qǐng)求要求讀數(shù)據(jù)到不同的內(nèi)存緩沖區(qū)，但是以這樣的方式，當(dāng)所有的請(qǐng)求都完成時(shí)，一個(gè)連續(xù)的電影片斷（包含多個(gè)幀）在內(nèi)存中將被連續(xù)地組裝好。這些請(qǐng)求可以并行處理。9.4.5在多個(gè)磁盤上存放文件總的來說，在所有的磁盤間分9.4.5在多個(gè)磁盤上存放文件當(dāng)最后一個(gè)請(qǐng)求被滿足時(shí)，可以用信號(hào)通知請(qǐng)求進(jìn)程工作已經(jīng)完成了，此時(shí)它就可以將數(shù)據(jù)傳送給用戶。許多幀過后，當(dāng)緩沖區(qū)下降到最后幾幀時(shí)，更多的請(qǐng)求將被發(fā)出，以便預(yù)裝載另外一個(gè)緩沖區(qū)。這一方法使用了大量的內(nèi)存作為緩沖區(qū)，從而使磁盤保持忙碌。在一個(gè)具有1000個(gè)活躍用戶和1MB緩沖區(qū)的系統(tǒng)上（例如，在4塊磁盤中的每塊上使用256KB的磁盤塊），將需要1GB的RAM作為緩沖區(qū)。在1000個(gè)用戶的服務(wù)器上，這樣的內(nèi)存用量只是“小意思”，應(yīng)該不會(huì)有問題。9.4.5在多個(gè)磁盤上存放文件當(dāng)最后一個(gè)請(qǐng)求被滿足時(shí)，可9.4.5在多個(gè)磁盤上存放文件關(guān)于條帶的最后一個(gè)問題是在多少個(gè)磁盤上分條帶。在一個(gè)極端，每部電影將在所有的磁盤上分成條帶。例如，對(duì)于2GB的電影和1000塊磁盤，可以將2MB的磁盤塊寫在每塊磁盤上，這樣就沒有電影兩次使用同一塊磁盤。在另一個(gè)極端，磁盤被分區(qū)為小的組（如同圖9-11那樣），并且每部電影被限制在一個(gè)分區(qū)中。前者稱為寬條帶，它在平衡磁盤間負(fù)載方面工作良好。它的主要問題是每部電影使用了所有磁盤，如果一塊磁盤出現(xiàn)故障，那么就沒有電影可以觀看了。后者稱為窄條帶，它將遭遇熱點(diǎn)（廣受歡迎的分區(qū)）的問題，但是損失一塊磁盤將只是葬送存放在其分區(qū)中的電影。9.4.5在多個(gè)磁盤上存放文件關(guān)于條帶的最后一個(gè)問題是在9.5高速緩存?zhèn)鹘y(tǒng)的LRU文件高速緩存對(duì)于多媒體文件而言工作得并不好，這是因?yàn)殡娪暗脑L問模式與文本文件有所不同。在傳統(tǒng)的LRU緩沖區(qū)高速緩存背后的思想是，當(dāng)一個(gè)塊被使用之后，應(yīng)該將其保存在高速緩存中，以防很快再次需要訪問它。對(duì)于多媒體而言，通常的訪問模式是按順序從頭到尾觀看一部電影。一個(gè)塊不太可能被使用兩次。除非用戶對(duì)電影進(jìn)行倒帶操作以再次觀看某一場景。因此，通常的高速緩存技術(shù)是行不通的。然而，高速緩存仍然是可以有幫助的，只不過是要以不同的方式使用。9.5高速緩存?zhèn)鹘y(tǒng)的LRU文件高速緩存對(duì)于多媒體文件而言9.5.1塊高速緩存可以利用多媒體系統(tǒng)的可預(yù)測(cè)性，使高速緩存成為十分有益的技術(shù)。假設(shè)兩個(gè)用戶正在觀看同一部電影，其中一個(gè)用戶在另一個(gè)用戶2秒鐘之后開始觀看。當(dāng)?shù)谝粋€(gè)用戶取出并觀看了任何一個(gè)給定的塊之后，很有可能第二個(gè)用戶在2秒鐘后將需要相同的塊。系統(tǒng)很容易跟蹤哪些電影只有一個(gè)觀眾，哪些電影有兩個(gè)或更多個(gè)在時(shí)間上相隔很近的觀眾。9.5.1塊高速緩存可以利用多媒體系統(tǒng)的可預(yù)測(cè)性，使高速9.5.1塊高速緩存因此，只要一部電影中的一個(gè)塊讀出后很快會(huì)再次需要，對(duì)其進(jìn)行高速緩存就是有意義的，當(dāng)然是否進(jìn)行高速緩存還取決于它要被高速緩存多長時(shí)間以及內(nèi)存有多緊張。這里應(yīng)該使用不同的策略，而不是將所有磁盤塊保留在高速緩存之中，并且在高速緩存被填滿之后淘汰最近最少使用的。對(duì)于在第一個(gè)觀眾之后△T時(shí)間之內(nèi)有第二個(gè)觀眾的每一部電影，可以將其標(biāo)記為可高速緩存的，且高速緩存其所有磁盤塊直到第二個(gè)觀眾（也可能是第三個(gè)觀眾）使用。對(duì)于其他的電影，根本不需要進(jìn)行高速緩存。9.5.1塊高速緩存因此，只要一部電影中的一個(gè)塊讀出后很9.5.1塊高速緩存這一思想還可以進(jìn)一步發(fā)揮。在某些情況下，合并兩個(gè)視頻流是可行的。假設(shè)兩個(gè)用戶正在觀看同一部電影，但是在兩個(gè)用戶之間存在10秒鐘的延遲。在高速緩存中保留10秒鐘的磁盤塊是有可能的，但是要浪費(fèi)內(nèi)存。一種替代的方法是試圖使兩部電影同步，這一方法可以通過改變兩部電影的幀率來實(shí)現(xiàn)，如圖9-12所示。9.5.1塊高速緩存這一思想還可以進(jìn)一步發(fā)揮。在某些情況圖9-12兩個(gè)視頻流的合并與同步圖9-12兩個(gè)視頻流的合并與同步929.5.1塊高速緩存在圖9-12a）中，兩部電影均以每分鐘1800幀的NTSC速率播放，由于用戶2開始晚了10秒鐘，他將在整部電影播放過程中落后10秒鐘。然而，在圖9-12b）中，當(dāng)用戶2到來時(shí)，用戶1的視頻流將放慢，在接下來的3分鐘里，它不是以每分鐘1800幀的速率播放，而是以每分鐘1750幀的速率播放，3分鐘后，它正處于第5550幀。與此同時(shí)，用戶2的視頻流在最初的3分鐘里以每分鐘1850幀的速率播放，3分鐘后，它同樣也處于第5550幀。從此刻之后，兩個(gè)視頻流均以正常速度播放。9.5.1塊高速緩存在圖9-12a）中，兩部電影均以每9.5.1塊高速緩存在追趕階段，用戶1的視頻流運(yùn)行速度慢了2.8%，而用戶2的視頻流運(yùn)行速度快了2.8％。用戶不太可能會(huì)注意到這一點(diǎn)。然而，如果對(duì)此有所擔(dān)心，那么追趕階段可以在比3分鐘更長的時(shí)間間隔上展開。一種降低一個(gè)用戶的速度以便與另一個(gè)視頻流合并的可選方法是，給用戶以在他們的電影中包含廣告的選項(xiàng)，與無廣告的電影相比，其觀看價(jià)格比較低。用戶還可以選擇產(chǎn)品門類，這樣廣告的侵?jǐn)_就會(huì)小一些而更有可能被觀看。通過對(duì)廣告的數(shù)目、長度和時(shí)間安排進(jìn)行巧妙的操作，視頻流就可以被阻滯足夠長的時(shí)間，以便與期望的視頻流取得同步。9.5.1塊高速緩存在追趕階段，用戶1的視頻流運(yùn)行速度慢9.5.2文件高速緩存在多媒體系統(tǒng)中高速緩存還能夠以不同的方式提供幫助。由于大多數(shù)電影都非常大（3~6GB），視頻服務(wù)器通常不能在磁盤上存放所有這些文件，所以要將它們存放在DVD上。當(dāng)需要一部電影的時(shí)候，它總是可以被復(fù)制到磁盤上，但是存在大量的啟動(dòng)時(shí)間來查找電影并將其復(fù)制到磁盤上。因此，大多數(shù)視頻服務(wù)器維護(hù)著一個(gè)請(qǐng)求頻繁的磁盤高速緩存。流行的電影將完整地存放在磁盤上。9.5.2文件高速緩存在多媒體系統(tǒng)中高速緩存還能夠以不同9.5.2文件高速緩存使用高速緩存的另一種方法是在磁盤上保存每部電影的最初幾分鐘。這樣，當(dāng)一部電影被請(qǐng)求時(shí)，可以立刻從磁盤文件開始回放，與此同時(shí)，電影從DVD復(fù)制到磁盤上。通過始終在磁盤上存放電影足夠長的部分，電影的下一個(gè)片斷在它需要之前就已經(jīng)取到磁盤上的概率會(huì)很高。如果一切都進(jìn)行得很好，整部電影將在它需要之前就已經(jīng)在磁盤上了，然后它將進(jìn)入高速緩存并且停留在磁盤上以備隨后有更多的請(qǐng)求。如果太多的時(shí)間過去而沒有另外的請(qǐng)求，電影將從高速緩存中刪除，以便為更為流行的電影騰出空間。9.5.2文件高速緩存使用高速緩存的另一種方法是在磁盤上9.6多媒體磁盤調(diào)度多媒體對(duì)磁盤提出了與傳統(tǒng)的、面向文本的應(yīng)用程序（例如編譯器或字處理器）有所不同的要求。特別是，多媒體要求極高的數(shù)據(jù)率和數(shù)據(jù)的實(shí)時(shí)傳輸。這些都不是輕易就能夠提供的。此外，在視頻服務(wù)器的情形中，讓一個(gè)服務(wù)器同時(shí)處理幾千個(gè)客戶還存在著經(jīng)濟(jì)壓力。這些需求影響著整個(gè)系統(tǒng)。9.6多媒體磁盤調(diào)度多媒體對(duì)磁盤提出了與傳統(tǒng)的、面向文本9.6.1靜態(tài)磁盤調(diào)度盡管多媒體對(duì)系統(tǒng)的所有部分提出了巨大的實(shí)時(shí)和數(shù)據(jù)率要求，但是它還有一個(gè)特性使其比傳統(tǒng)的系統(tǒng)更加容易處理，這就是可預(yù)測(cè)性。在傳統(tǒng)的操作系統(tǒng)中，對(duì)磁盤塊的請(qǐng)求是以相當(dāng)不可預(yù)測(cè)的方式發(fā)出的。磁盤子系統(tǒng)所能做的最好不過是對(duì)于每個(gè)打開的文件執(zhí)行一個(gè)磁盤塊的預(yù)讀，除此之外，它走夠做的全部事情就是等待請(qǐng)求的到來，并且在請(qǐng)求時(shí)對(duì)它們進(jìn)行處理。多媒體就不同了，每個(gè)活動(dòng)的視頻流對(duì)系統(tǒng)施加明確的負(fù)載，使系統(tǒng)成為高度可預(yù)測(cè)的。9.6.1靜態(tài)磁盤調(diào)度盡管多媒體對(duì)系統(tǒng)的所有部分提出了巨9.6.1靜態(tài)磁盤調(diào)度就NTSC回放而言，每33.3ms，每個(gè)客戶將需要其文件中的下一幀，并且系統(tǒng)有33.3ms的時(shí)間提供所有的幀（系統(tǒng)對(duì)每個(gè)視頻流需要緩沖至少一幀，所以取第k+1幀可以與第k幀的回放并行處理）。這一可預(yù)測(cè)的負(fù)載可以用來使用為多媒體剪裁的算法對(duì)磁盤進(jìn)行調(diào)度。9.6.1靜態(tài)磁盤調(diào)度就NTSC回放而言，每33.3ms9.6.2動(dòng)態(tài)磁盤調(diào)度不同的電影可能具有不同的數(shù)據(jù)率，所以對(duì)磁盤的請(qǐng)求或多或少是隨機(jī)到來的。每一讀請(qǐng)求需要指定要讀的是哪一磁盤塊，另外還要指定什么時(shí)間需要該磁盤塊，也就是最終時(shí)限。為簡單起見，我們假設(shè)對(duì)于每次請(qǐng)求實(shí)際的服務(wù)時(shí)間是相同的。以這種方法，我們可以從每次請(qǐng)求減去固定的服務(wù)時(shí)間，得到請(qǐng)求能夠發(fā)出并且還能滿足最終時(shí)限的最近的時(shí)間。因?yàn)榇疟P調(diào)度程序所關(guān)心的是對(duì)請(qǐng)求進(jìn)行調(diào)度的最終時(shí)限，所以這樣做使模型更為簡潔。9.6.2動(dòng)態(tài)磁盤調(diào)度不同的電影可能具有不同的數(shù)據(jù)率，所9.6.2動(dòng)態(tài)磁盤調(diào)度當(dāng)系統(tǒng)啟動(dòng)的時(shí)候，還沒有掛起的磁盤請(qǐng)求。當(dāng)?shù)谝粋€(gè)請(qǐng)求到來的時(shí)候，它立即得到服務(wù)。當(dāng)?shù)谝淮螌さ腊l(fā)生的時(shí)候，其他請(qǐng)求可能到來，所以當(dāng)?shù)谝淮握?qǐng)求結(jié)束的時(shí)候，磁盤驅(qū)動(dòng)器可能要選擇下一次處理哪個(gè)請(qǐng)求。某個(gè)請(qǐng)求被選中并開始得到處理。當(dāng)該請(qǐng)求結(jié)束的時(shí)候，再一次有一組可能的請(qǐng)求：它們是第一次沒有被選中的請(qǐng)求和第二個(gè)請(qǐng)求正在被處理的時(shí)候新到來的請(qǐng)求。一般而言，只要一個(gè)磁盤請(qǐng)求完成，磁盤驅(qū)動(dòng)器就有若干組掛起的請(qǐng)求，必須從中做出選擇。9.6.2動(dòng)態(tài)磁盤調(diào)度當(dāng)系統(tǒng)啟動(dòng)的時(shí)候，還沒有掛起的磁盤9.6.2動(dòng)態(tài)磁盤調(diào)度在選擇下一個(gè)磁盤請(qǐng)求時(shí)，有兩個(gè)因素起著重要的作用：最終時(shí)限和柱面。從性能的觀點(diǎn)來看，保持請(qǐng)求存放在柱面上并且使用電梯算法可以將總尋道時(shí)間最小化，但是可能導(dǎo)致存放在邊緣柱面上的請(qǐng)求錯(cuò)過其最終時(shí)限。從實(shí)時(shí)的觀點(diǎn)來看，將請(qǐng)求按照最終時(shí)限排序并且以最終時(shí)限的順序?qū)λ鼈冞M(jìn)行處理，可以將錯(cuò)過最終時(shí)限的機(jī)會(huì)最小化，但是可能增加總尋道時(shí)間。使用scan-EDF算法可以將這兩個(gè)因素結(jié)合起來。達(dá)一算法的思想是，將最終時(shí)限比較接近的請(qǐng)求收集在一起分成若干批，并且以柱面的順序?qū)ζ溥M(jìn)行處理。9.6.2動(dòng)態(tài)磁盤調(diào)度在選擇下一個(gè)磁盤請(qǐng)求時(shí)，有兩個(gè)因素9.6.2動(dòng)態(tài)磁盤調(diào)度如果不同的視頻流具有不同的數(shù)據(jù)率，那么當(dāng)一個(gè)新的客戶出現(xiàn)時(shí)將引起一個(gè)嚴(yán)重的問題：該客戶是否應(yīng)該被接納？如果接納該客戶會(huì)導(dǎo)致其他的視頻流頻繁地錯(cuò)過它們的最終時(shí)限，那么答案可能就是否。存在兩種方法計(jì)算是否接納新的客戶。一種方法是假設(shè)每個(gè)客戶平均地需要某些數(shù)量的資源，如磁盤帶寬、內(nèi)存緩沖區(qū)、CPU時(shí)間等。如果剩下的每一資源對(duì)于一個(gè)平均的顧客來說都是足夠的，則接納新的客戶。9.6.2動(dòng)態(tài)磁盤調(diào)度如果不同的視頻流具有不同的數(shù)據(jù)率，9.6.2動(dòng)態(tài)磁盤調(diào)度另一種算法更為復(fù)雜。它要關(guān)注新顧客想要看的特定的電影，查找該電影的（預(yù)先計(jì)算的）數(shù)據(jù)率，而對(duì)于黑白片和彩色片、卡通片和故事片、愛情片和戰(zhàn)爭片，數(shù)據(jù)率都不相同。愛情片運(yùn)動(dòng)緩慢，具有較長的場景和緩慢的淡入淡出，所有這些都會(huì)充分得到壓縮，而戰(zhàn)爭片具有許多快速的切換和迅速的運(yùn)動(dòng)，因此具有許多I幀和較大的P幀。如果服務(wù)器對(duì)于新客戶想要看的電影而言具有足夠的容量，那么就準(zhǔn)許接納，否則就拒絕接納。9.6.2動(dòng)態(tài)磁盤調(diào)度另一種算法更為復(fù)雜。它要關(guān)注新顧客9.7實(shí)驗(yàn)：關(guān)于操作系統(tǒng)多媒體功能的研究9.7.1工具/準(zhǔn)備工作9.7.2實(shí)驗(yàn)內(nèi)容與步驟9.7.3實(shí)驗(yàn)總結(jié)9.7.4實(shí)驗(yàn)評(píng)價(jià)（教師）9.7實(shí)驗(yàn)：關(guān)于操作系統(tǒng)多媒體功能的研究9.7.1工謝謝各位謝謝各位106第9章多媒體操作系統(tǒng)課件107第9章多媒體操作系統(tǒng)數(shù)字電影、視頻剪輯和音樂正在日益成為用計(jì)算機(jī)表示信息和進(jìn)行消遣娛樂的常用方式。音頻和視頻文件通常保存在磁盤上，在需要的時(shí)候進(jìn)行回放。音頻和視頻文件的特征與傳統(tǒng)的文本文件存在很大的差異，而目前計(jì)算機(jī)的文件系統(tǒng)最初卻是為文本文件設(shè)計(jì)的。因此，需要設(shè)計(jì)新的文件系統(tǒng)來處理音頻和視頻文件。不僅如此，保存與回放音頻和視頻同樣給操作系統(tǒng)及其調(diào)度程序提出了新的和更高的要求。第9章多媒體操作系統(tǒng)數(shù)字電影、視頻剪輯和音樂正在日益成為9.1視頻剪輯與點(diǎn)播通常，多媒體編輯系統(tǒng)需要在支持多媒體的操作系統(tǒng)上運(yùn)行，以獲得最好的性能。視頻點(diǎn)播是重要的多媒體技術(shù)，這意味著消費(fèi)者能夠在家中使用電視遙控器（或鼠標(biāo)）選擇電影，并且立刻將其在電視機(jī)（或計(jì)算機(jī)顯示器）上顯示出來。視頻點(diǎn)播要求基于特殊的基礎(chǔ)設(shè)施，圖9-1所示為兩種可能的視頻點(diǎn)播基礎(chǔ)設(shè)施，每種都包含三個(gè)基本的組件：一個(gè)或多個(gè)視頻服務(wù)器、一個(gè)分布式網(wǎng)絡(luò)以及一個(gè)在每個(gè)房間中用來對(duì)信號(hào)進(jìn)行解碼的機(jī)頂盒。9.1視頻剪輯與點(diǎn)播通常，多媒體編輯系統(tǒng)需要在支持多媒體圖9-1視頻點(diǎn)播使用不同的本地分布技術(shù)圖9-1視頻點(diǎn)播使用不同的本地分布技術(shù)1109.1視頻剪輯與點(diǎn)播視頻服務(wù)器是一臺(tái)功能強(qiáng)大的計(jì)算機(jī)，在其文件系統(tǒng)中存放著許多電影，并且可以按照點(diǎn)播請(qǐng)求回放這些電影。大型機(jī)有時(shí)用來作為視頻服務(wù)器，因?yàn)榇笮蜋C(jī)連接1000個(gè)大容量的磁盤是一件輕而易舉的事情。9.1視頻剪輯與點(diǎn)播視頻服務(wù)器是一臺(tái)功能強(qiáng)大的計(jì)算機(jī)，在9.1視頻剪輯與點(diǎn)播用戶和視頻服務(wù)器之間的分布式網(wǎng)絡(luò)必須能夠高速實(shí)時(shí)地傳輸數(shù)據(jù)。分布式網(wǎng)絡(luò)總是使用光纖從視頻服務(wù)器連接到客戶居住點(diǎn)的匯接盒。ADSL系統(tǒng)是由電話公司經(jīng)營的，在ADSL系統(tǒng)中，現(xiàn)有的雙絞電話線提供了最后一公里的數(shù)據(jù)傳輸。有線電視是由有線電視公司經(jīng)營的，在有線電視系統(tǒng)中，現(xiàn)有的有線電視電纜用于信號(hào)的本地分送。ADSL的優(yōu)點(diǎn)是為每個(gè)用戶提供了專用數(shù)據(jù)通道，因此帶寬有保證，但是由于現(xiàn)有電話線的局限其帶寬比較低（只有幾Mb/s）。9.1視頻剪輯與點(diǎn)播用戶和視頻服務(wù)器之間的分布式網(wǎng)絡(luò)必須9.1視頻剪輯與點(diǎn)播有線電視使用高帶寬的同軸電纜，帶寬可以達(dá)到幾Gb/s，但是許多用戶必須共享相同的電纜，從而導(dǎo)致競爭，對(duì)于每個(gè)用戶來說帶寬沒有保證。不過，為了與有線電視競爭，電話公司正在為住戶鋪設(shè)光纜，這樣，光纜上的ADSL將比電視電纜有更大的帶寬。系統(tǒng)的最后一部分是機(jī)頂盒，這是ADSL或電視電纜終結(jié)的地方。機(jī)頂盒實(shí)際上就是一臺(tái)計(jì)算機(jī)，只不過其中包含特殊的芯片用于視頻解碼和解壓縮。機(jī)頂盒最少要包含CPU、RAM、ROM、與ADSL或電視電纜的接口，以及用于跟電視機(jī)連接的端子。9.1視頻剪輯與點(diǎn)播有線電視使用高帶寬的同軸電纜，帶寬可9.1視頻剪輯與點(diǎn)播用戶也可以使用現(xiàn)有的PC機(jī)并且在顯示器上顯示電影。從技術(shù)角度看，使用個(gè)人計(jì)算機(jī)代替機(jī)頂盒更有道理，因?yàn)橛?jì)算機(jī)的功能更加強(qiáng)大，擁有大容量的磁盤，并且擁有更高分辨率的顯示器。不管共用的是機(jī)頂盒還是個(gè)人計(jì)算機(jī)，在解碼并顯示電影的用戶端，我們通常都要區(qū)分視頻服務(wù)器和客戶機(jī)進(jìn)程。然而，以系統(tǒng)設(shè)計(jì)的觀點(diǎn)，客戶機(jī)進(jìn)程是在機(jī)頂盒上運(yùn)行還是在PC機(jī)上運(yùn)行并沒有太大的關(guān)系。對(duì)于桌面視頻編輯系統(tǒng)而言，所有的進(jìn)程都運(yùn)行在相同的計(jì)算機(jī)上，分別發(fā)揮著服務(wù)器和客戶的作用。多媒體處理具有兩個(gè)關(guān)鍵的特征，即多媒體使用極高的數(shù)據(jù)率和多媒體要求實(shí)時(shí)回放。9.1視頻剪輯與點(diǎn)播用戶也可以使用現(xiàn)有的PC機(jī)并且在顯示9.1視頻剪輯與點(diǎn)播高數(shù)據(jù)率來自視覺與聽覺信息的本性。眼睛和耳朵每秒可以處理巨大數(shù)量的信息，必須以這樣的速率為眼睛和耳朵提供信息才能產(chǎn)生可以接受的觀察體驗(yàn)。表9-1列舉了幾種數(shù)字多媒體源和某些常見硬件設(shè)備的數(shù)據(jù)率。需要注意的是，多媒體需要的數(shù)據(jù)率越高，則越需要進(jìn)行壓縮，并且需要的存儲(chǔ)量也就越大。例如，一部未壓縮的2小時(shí)長的HDTV電影將填滿一個(gè)570GB的文件。存放1000部這種電影的視頻服務(wù)器需要570TB的磁盤空間，按照目前的標(biāo)準(zhǔn)這可是難以想象的數(shù)量。還需要注意的是，沒有數(shù)據(jù)壓縮，目前的硬件不可能跟上這樣的數(shù)據(jù)率。9.1視頻剪輯與點(diǎn)播高數(shù)據(jù)率來自視覺與聽覺信息的本性。眼表9-1某些多媒體和高性能I/O設(shè)備的數(shù)據(jù)率（1Mbps=106位/秒，1GB=230字節(jié)）表9-1某些多媒體和高性能I/O設(shè)備的數(shù)據(jù)率1169.1視頻剪輯與點(diǎn)播多媒體對(duì)系統(tǒng)提出的第二個(gè)要求是需要實(shí)時(shí)數(shù)據(jù)傳輸。數(shù)字電影的視頻部分每秒包含某一數(shù)目的幀。北美、南美和日本采用的NTSC制式每秒包含30幀（實(shí)際為29.97幀），世界上其他大部分地區(qū)采用的PAL和SECAM制式每秒包含25幀（25.00幀）。幀必須分別以33.3ms或40ms的精確時(shí)間間隔傳輸，否則電影看起來將會(huì)有起伏。9.1視頻剪輯與點(diǎn)播多媒體對(duì)系統(tǒng)提出的第二個(gè)要求是需要實(shí)9.1視頻剪輯與點(diǎn)播耳朵比眼睛更加敏感，傳輸時(shí)間中即使存在幾毫秒的變動(dòng)也會(huì)被察覺到。傳輸率的變動(dòng)稱為顫動(dòng)，必須嚴(yán)格限制顫動(dòng)以獲得良好的性能。注意，顫動(dòng)不同于延遲。如果圖9-1中的分布式網(wǎng)絡(luò)均勻地將所有的位淮確地延遲5s，電影將開始得稍稍晚一些，但是看起來卻不錯(cuò)。但從另一方面來說，如果分布式網(wǎng)絡(luò)在100~200ms之間隨機(jī)地延遲各幀，那就會(huì)明顯影響播放質(zhì)量。9.1視頻剪輯與點(diǎn)播耳朵比眼睛更加敏感，傳輸時(shí)間中即使存9.1視頻剪輯與點(diǎn)播提供服務(wù)質(zhì)量保證的最常見的方法是預(yù)先為每一個(gè)新到的客戶預(yù)留資源，包括CPU、內(nèi)存緩沖區(qū)、磁盤傳輸容量以及網(wǎng)絡(luò)帶寬。如果一位新的客戶到來并且想觀看一部電影，但是視頻服務(wù)器或網(wǎng)絡(luò)計(jì)算出不具有為另一位客戶提供服務(wù)的容量，那么它將拒絕新的客戶，以避免降低向當(dāng)前客戶提供的服務(wù)質(zhì)量。因此，多媒體服務(wù)器需要有資源預(yù)留方案和進(jìn)入控制算法，以判定什么時(shí)候能夠處理更多的任務(wù)。9.1