多媒体操作系统

单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,92,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,单击此处编辑标题文的格式,单击此处编辑大纲正文的格式,第二个大纲级,第三个大纲级,第四个大纲级,第五个大纲级,第六个大纲级,第七个大纲级,第八个大纲级,第九个大纲级,2011-11-4,*,多媒体技术与应用,第,3,章 数据压缩技术,第,4,章 数据存储技术,第,5,章 数字音频技术,第,6,章 数字图形图像技术,第,7,章 数字视频技术,第,8,章 网络多媒体技术,第,9,章 多媒体操作系统,第,9,章 多媒体操作系统,数字电影、视频剪辑和音乐正在日益成为用计算机表示信息和进行消遣娱乐的常用方式。音频和视频文件通常保存在磁盘上，在需要的时候进行回放。音频和视频文件的特征与传统的文本文件存在很大的差异，而目前计算机的文件系统最初却是为文本文件设计的。因此，需要设计新的文件系统来处理音频和视频文件。不仅如此，保存与回放音频和视频同样给操作系统及其调度程序提出了新的和更高的要求。,9.1,视频剪辑与点播,通常，多媒体编辑系统需要在支持多媒体的操作系统上运行，以获得最好的性能。视频点播是重要的多媒体技术，这意味着消费者能够在家中使用电视遥控器（或鼠标）选择电影，并且立刻将其在电视机（或计算机显示器）上显示出来。视频点播要求基于特殊的基础设施，图,9-1,所示为两种可能的视频点播基础设施，每种都包含三个基本的组件：一个或多个视频服务器、一个分布式网络以及一个在每个房间中用来对信号进行解码的机顶盒。,图,9-1,视频点播使用不同的本地分布技术,9.1,视频剪辑与点播,视频服务器是一台功能强大的计算机，在其文件系统中存放着许多电影，并且可以按照点播请求回放这些电影。大型机有时用来作为视频服务器，因为大型机连接,1000,个大容量的磁盘是一件轻而易举的事情。,9.1,视频剪辑与点播,用户和视频服务器之间的分布式网络必须能够高速实时地传输数据。分布式网络总是使用光纤从视频服务器连接到客户居住点的汇接盒。,ADSL,系统是由电话公司经营的，在,ADSL,系统中，现有的双绞电话线提供了最后一公里的数据传输。有线电视是由有线电视公司经营的，在有线电视系统中，现有的有线电视电缆用于信号的本地分送。,ADSL,的优点是为每个用户提供了专用数据通道，因此带宽有保证，但是由于现有电话线的局限其带宽比较低（只有几,Mb/s,）。,9.1,视频剪辑与点播,有线电视使用高带宽的同轴电缆，带宽可以达到几,Gb/s,，但是许多用户必须共享相同的电缆，从而导致竞争，对于每个用户来说带宽没有保证。不过，为了与有线电视竞争，电话公司正在为住户铺设光缆，这样，光缆上的,ADSL,将比电视电缆有更大的带宽。,系统的最后一部分是机顶盒，这是,ADSL,或电视电缆终结的地方。机顶盒实际上就是一台计算机，只不过其中包含特殊的芯片用于视频解码和解压缩。机顶盒最少要包含,CPU,、,RAM,、,ROM,、与,ADSL,或电视电缆的接口，以及用于跟电视机连接的端子。,9.1,视频剪辑与点播,用户也可以使用现有的,PC,机并且在显示器上显示电影。从技术角度看，使用个人计算机代替机顶盒更有道理，因为计算机的功能更加强大，拥有大容量的磁盘，并且拥有更高分辨率的显示器。不管共用的是机顶盒还是个人计算机，在解码并显示电影的用户端，我们通常都要区分视频服务器和客户机进程。然而，以系统设计的观点，客户机进程是在机顶盒上运行还是在,PC,机上运行并没有太大的关系。对于桌面视频编辑系统而言，所有的进程都运行在相同的计算机上，分别发挥着服务器和客户的作用。,多媒体处理具有两个关键的特征，即多媒体使用极高的数据率和多媒体要求实时回放。,9.1,视频剪辑与点播,高数据率来自视觉与听觉信息的本性。眼睛和耳朵每秒可以处理巨大数量的信息，必须以这样的速率为眼睛和耳朵提供信息才能产生可以接受的观察体验。表,9-1,列举了几种数字多媒体源和某些常见硬件设备的数据率。需要注意的是，多媒体需要的数据率越高，则越需要进行压缩，并且需要的存储量也就越大。例如，一部未压缩的,2,小时长的,HDTV,电影将填满一个,570GB,的文件。存放,1000,部这种电影的视频服务器需要,570TB,的磁盘空间，按照目前的标准这可是难以想象的数量。还需要注意的是，没有数据压缩，目前的硬件不可能跟上这样的数据率。,表,9-1,某些多媒体和高性能,I/O,设备的数据率,（,1Mbps = 106,位,/,秒，,1GB = 230,字节）,9.1,视频剪辑与点播,多媒体对系统提出的第二个要求是需要实时数据传输。数字电影的视频部分每秒包含某一数目的帧。北美、南美和日本采用的,NTSC,制式每秒包含,30,帧（实际为,29.97,帧），世界上其他大部分地区采用的,PAL,和,SECAM,制式每秒包含,25,帧（,25.00,帧）。帧必须分别以,33.3ms,或,40ms,的精确时间间隔传输，否则电影看起来将会有起伏。,9.1,视频剪辑与点播,耳朵比眼睛更加敏感，传输时间中即使存在几毫秒的变动也会被察觉到。传输率的变动称为颤动，必须严格限制颤动以获得良好的性能。注意，颤动不同于延迟。如果图,9-1,中的分布式网络均匀地将所有的位淮确地延迟,5s,，电影将开始得稍稍晚一些，但是看起来却不错。但从另一方面来说，如果分布式网络在,100200ms,之间随机地延迟各帧，那就会明显影响播放质量。,9.1,视频剪辑与点播,提供服务质量保证的最常见的方法是预先为每一个新到的客户预留资源，包括,CPU,、内存缓冲区、磁盘传输容量以及网络带宽。如果一位新的客户到来并且想观看一部电影，但是视频服务器或网络计算出不具有为另一位客户提供服务的容量，那么它将拒绝新的客户，以避免降低向当前客户提供的服务质量。因此，多媒体服务器需要有资源预留方案和进入控制算法，以判定什么时候能够处理更多的任务。,9.2,多媒体进程调度,多媒体操作系统与传统操作系统有三个主要区别，即进程调度、文件系统和磁盘调度。,9.2.1,调度同质进程,最简单的一种视频服务器可以支持显示固定数目的电影，所有电影使用相同的帧率、视频分辨率、数据率以及其他参数。在这样的情况下，可以采用下述简单但是有效的调度算法。对每一部电影，存在一个进程（或线程），其工作是每次从磁盘中读取电影的一帧然后将该帧传送给用户。由于所有的进程同等重要，每一帧有相同的工作量要做，并且当它们完成当前帧的处理时将阻塞，所以采用轮转调度可以很好地做这样的工作。将调度算法标准化的唯一的额外要求是定时机制，以确保每一进程以恰当的频率运行。,9.2.1,调度同质进程,实现适当定时的一种方式是有一个主控时钟，该时钟每秒滴答适当的次数，例如针对,NTSC,制式，每秒滴答,30,次。在时钟的每一滴答，所有的进程以相同的次序相继运行。当一个进程完成其工作时，它将发出,suspend,系统调用释放,CPU,直到主控时钟再次滴答。当主控时钟再次滴答时，所有的进程再次以相同的次序运行。只要进程数足够少，所有的工作都可以在一帧的时间内完成，采用轮转调度就足够了。,9.2.2,一般实时调度,随着用户的数目不断变化，由于视频压缩的本性（,I,帧比,P,帧或,B,帧大得多），帧的大小剧烈变化，并且不同的电影可能有不同的分辨率。因此，不同的进程可能必须以不同的频率运行，具有不同的工作量，并且具有不同的最终时限。,这些考虑导致一个不同的模型：多个进程竞争,CPU,，每个进程有自己的工作量和最终时限。在下面的模型中，我们将假设系统知道每个进程必须以什么样的频率运行、有多少工作要做以及下一个最终时限是什么。多个相互竞争的进程，其中若干进程或全部进程具有必须满足的最终时限的调度就是实时调度。,9.2.2,一般实时调度,作为实时多媒体调度程序工作环境的一个例子，我们考虑三个进程,A,、,B,和,C,，如图,9-2,所示。进程,A,每,30ms,运行一次（近似,NTSC,制式速度），每一帧需要,10ms,的,CPU,时间。在不存在竞争的情况下，进程,A,将在突发,A1,、,A2,、,A3,等中运行，每一突发在前一突发的,30ms,之后开始。每个,CPU,突发处理一帧并且具有一个最终时限：它必须在下一个突发开始之前完成。,图,9-2,三个周期性的进程，每个进程播放一部电影；每一电影的帧率以及每帧的处理需求有所不同,9.2.2,一般实时调度,图,9-2,中，进程,B,每秒运行,25,次（例如,PAL,制式），进程,C,每秒运行,20,次（例如一个慢下来的,NTSC,或,PAL,流，意在使一个低带宽的用户连接到视频服务器）。每一帧的计算时间如图,9-2,中所示，进程,B,为,15ms,，进程,C,为,5ms,，没有使它们都具有相同的时间只是为了使调度问题更加一般化。现在，调度问题是如何调度,A,、,B,和,C,以确保它们满足各自的最终时限。,9.2.2,一般实时调度,到目前为止我们假设每个影片流有一个进程，实际上，每个影片流可能有两个甚至更多个进程，例如一个用于音频一个用于视频。它们可能以不同的速率运行并且每一脉冲可能消耗不同数量的,CPU,时间。然而，将音频进程加入到系统中并没有改变一般模型，因为我们的全部假设是存在,m,个进程。每个进程以一个固定的频率运行，对每一,CPU,突发有固定的工作量要求。,9.2.2,一般实时调度,在某些实时系统中，进程是可抢占的，在其他的系统中，进程是不可抢占的。在多媒体系统中，进程通常是可抢占的，这意味着允许有危险错过其最终时限的进程在正在运行的进程完成工作以前将其中断，然后当它完成工作之后，被中断的前一个进程再继续运行。这一行为只不过是多道程序设计。在多媒体系统中可抢占的实时调度算法比不可抢占的调度算法具有更好的性能。唯一要关心的是如果传输缓冲区在很少的几个突发中被填充，那么在最终时限到来之前该缓冲区应该是完全满的，这样它就可以在一次操作中传递给用户，否则就会引起颤动。,9.2.2,一般实时调度,实时算法可以是静态的也可以是动态的。静态算法预先分配给每个进程一个固定的优先级，然后使用这些优先级做基于优先级的抢占调度。动态算法没有固定的优先级。,9.2.3,速率单调调度,适用于可抢占的周期性进程的经典静态实时调度算法是速率单调调度（,Rate Monotonic Scheduling,，,RMS,），它可以用于满足下列条件的进程：,1,）每个周期性进程必须在其周期内完成。,2,）没有进程依赖于任何其他进程。,3,）每一进程在一次突发中需要相同的,CPU,时间量。,4,）任何非周期性进程都没有最终时限。,5,）进程抢占即刻发生而没有系统开销。,前四个条件是合理的。当然，最后一个不是，但是该条件使系统建模更加容易。,9.2.3,速率单调调度,RMS,分配给每个进程一个固定的优先级，优先级等于进程触发事件发生的频率。例如，必须每,30ms,运行一次（每秒,33,次）的进程获得的优先级为,33,，必须每,40ms,运行一次（每秒,25,次）的进程获得的优先级为,25,，必须每,50ms,运行一次（每秒,20,次）的进程获得的优先级为,20,。所以，优先级与进程的速率（每秒运行进程的次数）成线性关系，这正是为什么将其称为速率单调的原因。在运行时，调度程序总是运行优先级最高的就绪进程，如果需要则抢占正在运行的进程。已经证明在静态调度算法种类中,RMS,是最优的。,9.2.3,速率单调调度,图,9-3,演示了图,9-2,所示例子中速率单调调度是如何工作的。进程,A,、,B,和,C,分别具有静态优先级,33,、,25,和,20,，这意味着只要,A,需要运行，它就可以运行，抢占任何当前正在使用,CPU,的其他进程。进程,B,可以抢占,C,，但不能抢占,A,。进程,C,必须等待直到,CPU,空闲才能运行。,图,9-3 RMS,和,EDF,实时调度的一个例子,9.2.3,速率单调调度,在图,9-3,中，最初所有三个进程都就绪要运行，优先级最高的进程,A,被选中，并准许它运行直到它在,10ms,时完成，如图,9-3,中的,RMS,一行所示。在进程,A,完成之后，进程,B,和,C,以先后次序运行。合起来，这些进程运行花费了,30ms,时间，所以当,C,完成的时候，正是,A,再次运行的时候。这一轮换持续进行直到,t = 70,时系统变为空闲。,在,t = 80,时，进程,B,就绪并开始运行。然而，在,t = 90,时，优先级更高的进程,A,变为就绪，所以它抢占,B,并运行，直到在,t = 100,时完成。在这一时刻，系统可以在结束进程,B,或者开始进程,C,之间进行选择，所以它选择优先级最高的进程,B,。,9.2.4,最早最终时限优先调度,另一个流行的实时调度算法是最早最终时限优先（,Earliest Deadtime First, EDF,）算法。,EDF,是一个动态算法，它不像速率单调算法那样要求进程是周期性的。它也不像,RMS,那样要求每个,CPU,突发有相同的运行时间。只要一个进程需要,CPU,时间，它就宣布它的到来和最终时限。调度程序维持一个可运行进程的列表，该列表按最终时限排序。,EDF,算法运行列表中的第一个进程，也就是具有最近最终时限的进程。当一个新的进程就绪时，系统进行检查以了解其最终时限是否发生在当前运行的进程结束之前。如果是这样，新的进程就抢占当前正在运行的进程。,9.2.4,最早最终时限优先调度,图,9-3,给出了,EDF,的一个例子。最初所有三个进程都是就绪的，它们按其最终时限的次序运行。进程,A,必须在,t = 30,之前结束，,B,必须在,t = 40,之前结束，,C,必须在,t = 50,之前结束，所以,A,具有最早的最终时限并因此而先运行。直到,t = 90,，选择都与,RMS,相同。在,t = 90,时，,A,再次就绪，并且其最终时限为,t = 120,，与,B,的最终时限相同。调度程序可以合理地选择其中任何一个运行，但是由于抢占,B,具有某些非零的代价与之相联系，所以最好是让,B,继续运行，而不去承担切换的代价。,9.2.4,最早最终时限优先调度,为了消除,RMS,和,EDF,总是给出相同结果的想法，现在让我们看一看另外一个例子，如图,9-4,所示。,图,9-4,以,RMS,和,EDF,进行实时调度的另一个例子,9.2.4,最早最终时限优先调度,在这个例子中，进程,A,、,B,和,C,的周期与前面的例子相同，但是现在,A,每次突发需要,15ms,的,CPU,时间，而不是只有,10ms,。可调度性测试计算,CPU,的利用率为,0.500 + 0.375 + 0.100 = 0.975,。,CPU,只留下了,25%,，但是在理论上,CPU,并没有被超额预定，找到一个合理的调度应该是可能的。,对于,RMS,，三个进程的优先级仍为,33,、,25,和,20,，因为优先级只与周期有关系。这一次，进程,B,直到,t = 30,才结束，在这一时刻，进程,A,再次就绪要运行。等到,A,结束时，,t = 45,，此时,B,再次就绪，由于它的优先级高于,C,，所以,B,运行而,C,则错过了其最终时限。,RMS,失败。,9.2.4,最早最终时限优先调度,现在看一看,EDF,如何处理这种情况。当,t = 30,时，在,A2,和,C1,之间存在竞争。因为,C1,的最终时限是,50,，而,A2,的最终时限是,60,，所以,C,被调度。这就不同于,RMS,，在,RMS,中,A,由于较高的优先级而成为赢家。当,t = 90,时，,A,第四次就绪。,A,的最终时限与当前进程相同（同为,120,），所以调度程序面临抢占与否的选择。如前所述，如果不是必要最好不要抢占，所以,B3,被允许完成。,9.2.4,最早最终时限优先调度,在图,9-4,所示的例子中，直到,t = 150,，,CPU,都是,100,被占用的。然而，因为,CPU,只有,97.5,被利用，所以最终将会出现间隙。由于所有开始和结束时间都是,5ms,的倍数，所以间隙将是,5ms,。为了获得要求的,2.5%,的空闲时间，,5ms,的间隙必须每,200ms,出现一次，这就是间隙为什么没有在图,9-4,中出现的原因。,9.2.4,最早最终时限优先调度,根本上，使用静态优先级只有在,CPU,的利用率不太高的时候才能工作。对于,m = 3,、,4,、,5,、,10,、,20,和,100,，最大允许利用率为,0.780,、,0.757,、,0.743,、,0.718,、,0.705,和,0.696,。随着,m ,，最大利用率逼近,ln2,。换句话说，对于三个进程，如果,CPU,利用率等于或小于,0.780,，那么,RMS,总是可以工作的。在第一个例子中，,CPU,利用率为,0.808,而,RMS,工作正常，但那只不过是幸运罢了。对于不同的周期和运行时间，利用率为,0.808,很可能会失败。在第二个例子中，,CPU,利用率如此之高（,0.975,），根本不存在,RMS,能够工作的希望。,9.2.4,最早最终时限优先调度,与此相对照，,EDF,对于任意一组可调度的进程总是可以工作的，它可以达到,100,的,CPU,利用率，付出的代价是更为复杂的算法。因而，在一个实际的视频服务器中，如果,CPU,利用率低于,RMS,限度，可以使用,RMS,，否则，应该选择,EDF,。,9.3,多媒体文件系统,多媒体文件系统使用了与传统文件系统不同的范型。在传统的文件,I/O,系统中，进程要访问一个文件时，首先要发出,open,系统调用。如果该调用成功，则调用者被给予某种令牌以便在未来的调用中使用，该令牌在,UNIX,中被称为文件描述符，在,Windows,中被称为句柄。这时，进程可以发出,read,系统调用，提供令牌、缓冲区地址和字节计数作为参数。操作系统则在缓冲区中返回请求的数据。以后还可以发出另外的,read,调用，直到进程结束。在进程结束时它将调用,close,以关闭文件并返回其资源。,9.3,多媒体文件系统,由于实时行为的需要，这一模型对于多媒体并不能很好地工作，尤其是在显示来自远程视频服务器的多媒体文件时，该模型的工作效果更差。第一个问题是用户必须以相当精确的时间间隔进行,read,调用，第二个问题是视频服务器必须能够没有延迟地提供数据块。但是，当请求没有计划地到来并且预先没有保留资源时，做到这一点是十分困难的。,9.3,多媒体文件系统,为解决这些问题，多媒体文件服务器使用了一个完全不同的范型：像录像机（,VCR,）一样工作。为了读取一个多媒体文件，用户进程发出,start,系统调用，指定要读的文件（如哪些音频和字幕轨迹）和各种其他参数。接着，视频服务器开始以必要的速率送出帧，然后用户进程以帧进来的速率对它们进行处理。如果用户对所看的电影感到厌烦，发出,stop,系统调用可以将数据流终止。具有这种数据流模型的文件服务器通常被称为推送型服务器，因为它将数据推送给用户。而在传统的拉取型服务器中，用户不得不通过重复地调用,read,一块接一块地取得数据，每调用一次可以拉取出一块数据。这两个模型之间的区别如图,9-5,所示。,图,9-5,不同范型多媒体服务器的区别,9.3.1 VCR,控制功能,大多数视频服务器实现了标准的,VCR,控制功能，包括暂停、快进和倒带。暂停是相当简单的：用户发送一个消息给视频服务器，告诉它停止。视频服务器此时要做的全部事情是记住下一次要送出的是哪一帧。当用户要求服务器恢复播放时，服务器只要从它停止的地方继续就可以了。,然而，这里存在着一个复杂因素，服务器应该为每个流出的数据流保留诸如磁盘带宽和内存缓冲区等资源。当电影暂停时继续占用这些资源将造成浪费，特别是如果用户打算转而暂时去做另外一件事情的时候。当然，在暂停的时候可以很容易地将资源释放，但是这引入了风险：当用户试图恢复播放的时候，有可能无法重新获得这些资源。,9.3.1 VCR,控制功能,真正的倒带实际上非常简单，没有任何复杂性。服务器要做的全部事情就是注意到下一次要送出的帧是第,0,帧。还有比这更容易的吗？然而，快进和快倒（也就是在倒带的同时播放）就难处理多了。如果没有压缩，那么以,10,倍的速度前进的一种方法是每,10,帧只显示一帧，以,20,倍的速度前进则要求每,20,帧显示一帧。实际上，在不存在压缩的情况下，以任意速度前进和后退都是十分容易的。要以正常速度的,k,倍运行，只要每,k,帧显示一帧就可以了。要以正常速度的,k,倍后退，只要沿另一个方向做相同的事情就可以了。这一方法在推送型服务器和拉取型服务器上工作得同样好。,9.3.1 VCR,控制功能,压缩则使快进和快倒复杂起来。对于便携式摄像机的,DV,磁带，由于其每一帧都是独立于其他帧而压缩的，所以只要能够快速地找到所需要的帧，使用这一策略还是有可能的。由于视其内容不同每一帧的压缩量也有所不同，所以每一帧具有不同的大小，因而在文件中向前跳过,k,帧并不能通过数字计算来完成。此外，音频压缩是独立于视频压缩的，所以对于在高速模式中显示的每一视频帧，还必须找到正确的音频帧（除非在高于正常速度播放时将声音关闭）。因此，对一个,DV,文件进行快进操作需要有一个索引，该索引可以使帧的查找快速地实现，但是至少在理论上这样做是可行的。,9.3.1 VCR,控制功能,对于,MPEG,，由于使用,I,帧、,P,帧和,B,帧，这一方案即使在理论上也是不能工作的。向前跳过,k,帧（就算假设能这样做）可能落在一个,P,帧上，而这个,P,帧则基于刚刚跳过的一个,I,帧。没有基本帧，只有从基本帧发生的增量变化（这正是,P,帧所包含的）是无用的。,MPEG,要求按顺序播放文件。,9.3.1 VCR,控制功能,克服这一难题的另一个方法是实际尝试以,10,倍的速度顺序地播放文件。然而，这样做就要求以,10,倍的速度将数据拉出磁盘。此时，服务器可能试图将帧解压缩（这是正常情况下服务器不需要做的事情），判定需要哪一帧，然后每隔,10,帧重新压缩成一个,I,帧。然而，这样做给服务器增加了沉重的负担。这一方法还要求服务器了解压缩格式，正常情况下服务器不必了解这些东西。,作为替代，可以通过网络实际发送所有的数据给用户，并在用户端选出正确的帧，这样做就要求网络以,10,倍的速度运行，这或许是可行的，但是在这么高的速度下正常操作肯定不是一件容易的事情。,9.3.1 VCR,控制功能,总而言之，不存在容易的方法。唯一可行的策略是要求预先规划。可以做的事情是建立一个特殊的文件，包含每隔,10,帧中的一帧，并且将该文件以通常的,MPEG,算法进行压缩。这个文件是“快进”的文件。要切换到快进模式，服务器必须判定在快进文件中用户当前所在的位置。例如，如果当前帧是,48 210,并且快进文件以,10,倍的速度运行，那么服务器在快进文件中必须定位到,4821,帧并且在此处以正常速度开始播放。当然，这一帧可能是,P,帧或,B,帧，但是客户端的解码进程可以简单地跳过若干帧直到看见一个,I,帧。利用特别准备的快倒文件，可以用类似的方法实现快倒。,9.3.1 VCR,控制功能,当用户切换回到正常速度时，必须使用相反的技巧。如果在快进文件中当前帧是,5734,，服务器只要切换回到常规文件并且从,57 340,帧处继续播放。同样，如果这一帧不是一个,I,帧，客户端的解码进程必须忽略所有的帧直到看见一个,I,帧。,尽管有了这两个额外的文件可以做这些工作，这一方案还是有某些缺点。首先，需要某些额外的磁盘空间来存放额外的文件。其次，快进和倒带只能以对应于特别文件的速度进行。第三，在常规文件，快进文件和快倒文件之间来回切换需要额外的复杂算法。,9.3.2,近似视频点播,有,k,个用户取得相同的电影和这些用户取得,k,部不同的电影在本质上给服务器施加了相同的工作量。然而，通过对模型做一个小小的修改，就可能获得巨大的性能改进。视频点播面临的问题是用户可能在任意时刻开始观看一部电影，所以，如果有,100,个用户全部在晚,8,点左右开始观看某个新电影，很可能不会有两个用户在完全相同的时刻开始，所以他们无法共享一个数据流。使优化成为可能的修改是，通知所有用户电影只在整点和随后每隔（例如）,5,分钟开始。因此，如果一个用户想在,8:02,看一部电影，那么他必须等到,8:05,。,9.3.2,近似视频点播,这样做的收益是，不管存在多少客户，对于一部,2,小时的电影，只需要,24,个数据流。如图,9-6,所示，第一个数据流开始于,8:00,。在,8:05,，当第一个数据流处于第,9000,帧时，第二个数据流开始。在,8:10,，当第一个数据流处于第,18 000,帧并且第二个数据流处于第,9000,帧时，第三个数据流开始，以此类推直到第,24,个数据流开始于,9:55,。在,10:00,，第一个数据流终止并且再一次从第,0,帧开始。这一方案称为近似视频点播，因为视频并不是完全随着点播而开始，而是在点播之后不久开始。,图,9-6,近似视频点播以规则的间隔开始一个新的数据流，本例中间隔,5,分钟（,9000,帧）,9.3.2,近似视频点播,这里的关键参数是多长时间开始一个数据流。如果每,2,分钟开始一个数据流，那么对于一部,2,小时的电影来说就需要,60,个数据流，但是开始观看的最大等待时间是,2,分钟。运营商必须判定人们愿意等待多长时间，因为人们愿意等待的时间越长，系统效率就越高，并且同时能够被观看的电影就越多。一个替代的策略是同时提供不用等待的选择权，在这种情况下，新的数据流可以立刻开始，但是需要对系统做更多的修改以支持即时启动。,9.3.2,近似视频点播,在某种意义上，视频点播如同使用出租车：一招手它就来。近似视频点播如同使用公共汽车：它有着固定的时刻表，乘客必须等待下一辆。于是，播放最新大片可能吸引足够的客户，从而保证每,5,分钟开始一个新的数据流；但是对于传统经典影片，最好还是简单地在点播的基础上播映。,将近似视频点播（为的是效率）加上每个个体观众完全的,VCR,控制（为的是方便用户）是一种理想的组合。通过对模型进行略微的修正，这样的设计是有可能的，即具有,VCR,功能的近似视频点播。,9.4,文件存放,多媒体文件非常庞大，通常只写一次而读许多次，并且倾向于被顺序访问。它们的回放还必须满足严格的服务质量标准。总而言之，这些要求暗示着不同于传统操作系统使用的文件系统布局。,9.4.1,在单个磁盘上存放文件,最为重要的要求是数据能够以必要的速度流出到网络或输出设备上，并且没有颤动。为此，在传输一帧的过程中有多次寻道是极其不受欢迎的。在视频服务器上消除文件内寻道的一种方法是使用连续的文件。通常，在预先精心装载了电影的视频服务器上它工作得还是不错的，因为这些电影后来不会再发生变化。,9.4.1,在单个磁盘上存放文件,然而，视频、音频和文本的存在是一个复杂因素，即使视频、音频和文本每个都存储为单独的连续文件，从视频文件到音频文件，再从音频文件到文本文件的寻道在需要的时候还是免不了的。这使人想起第二种可能的存储排列，使视频、音频和文本交叉存放，但是整个文件还是连续的，如图,9-7,所示。此处，直接跟随第,1,帧视频的是第,1,帧的各种音频轨迹，然后是第,1,帧的各种文本轨迹，根据存在多少音频和文本轨迹，最简单的可能是在一次磁盘读操作中读入每一帧的全部内容，然后只将需要的部分传输给用户。,图,9-7,每部电影在一个连续文件中,交叉存放视频、音频和文本,9.4.1,在单个磁盘上存放文件,这一组织需要额外的磁盘,I/O,读入不必要的音频和文本，在内存中还需要额外的缓冲区空间存放它们。可是它消除了所有的寻道（在单用户系统上），并且不需要任何系统开销跟踪哪一帧在磁盘上的什么地方，因为整部电影存放在一个连续文件中。以这样的布局，随机访问是不可能的，但是如果不需要随机访问，这点损失并不严重。类似地，如果没有额外的数据结构和复杂性，快进和快倒也是不可能的。,9.4.1,在单个磁盘上存放文件,在具有多个并发输出流的视频服务器上，使整部电影成为一个连续文件的优点就失去了，因为从一部电影读取一帧之后，磁盘可能不得不从许多其他电影读入帧，然后才能返回到第一部电影。同样，对于一部电影既可以读也可以写的系统（例如用于视频生产或编辑的系统）来说，使用巨大的连续文件是很困难的。,9.4.2,两个替代的文件组织策略,这些考虑导致产生两个针对多媒体文件的文件存放组织。第一个是小块模型，如图,9-8 a,）所示。在这种组织中，选定磁盘块的大小比帧的平均大小，甚至是比,P,帧和,B,帧的大小要小得多。对于每秒,30,帧以,4Mbps,速率传输的,MPEG-2,而言，帧的平均大小为,16KB,，所以一个磁盘块的大小为,1KB,或,2KB,工作得比较好。这里的思想是每部电影有一个帧索引，这是一个数据结构，每一帧有一个帧索引项，指向帧的开始。每一帧本身是一连串连续的块，包含该帧所有的视频、音频和文本轨迹，如图,9-8,中所示。,图,9-8,不连续的电影存储,9.4.2,两个替代的文件组织策略,这样，读第,k,帧时首先要在帧索引中找到第,k,个索引项，然后在一次磁盘操作中将整个帧读入。由于不同的帧具有不同的大小，所以在帧索引中需要有表示帧大小的字段（以块为单位），即便对于,1KB,大小的磁盘块，,8,位的字段也可以处理最大为,255KB,的帧，这对于一个未压缩,NTSC,帧来说，就算它有许多音频轨迹也已经足够了。,存放电影的另一个方法是使用大磁盘块（比如,256KB,），并且在每一块中放入多个帧，如图,9-8 b,）所示。这里仍然需要一个索引，但是这次不是帧索引而是块索引。一般而言，一个磁盘块拥有的帧的数目不见得是整数，所以需要做某些机制来处理这一问题。解决这一问题有两种选择。,9.4.2,两个替代的文件组织策略,第一种选择如图,9-8 b,）所示，当下一帧填不满当前磁盘块的时候，则磁盘块剩余的部分就保持空闲伏态。这一浪费的空间就是内部碎片，与具有固定大小页面的虚拟内存系统中的内部碎片相同。但是，这样做在一帧的中间决不需要进行寻道。,另一种选择是填充每一磁盘块到尽头，将帧分裂开使其跨越磁盘块。这一选择在帧的中间引入寻道的需要，这将损害性能，但是由于消除了内部碎片而节约了磁盘空间。,9.4.2,两个替代的文件组织策略,作为对比，图,9-8 a,）中小块的使用也会浪费某些磁盘空间，因为在每一帧的最后一块可能有一小部分未被使用。对于,1KB,的磁盘块和一部由,216 000,帧组成的,2,小时的,NTSC,电影，浪费的磁盘空间总共只有,3.6GB,中的大约,108KB,。图,9-8 b,）浪费的磁盘空间计算起来非常困难，但是肯定多很多，因为在一个磁盘块的尽头有时会留下,100KB,的空间，而下一帧是一个比它大的,I,帧。,9.4.2,两个替代的文件组织策略,另一方面，块索引比帧索引要小很多。对于,256KB,的块，如果帧的平均大小为,16KB,，那么一个块大约可以装下,16,个帧，所以一部由,216 000,帧组成的电影在块索引中只需要有,13 500,个索引项，与此相对比，对于帧索引则需要,216 000,个索引项。因为性能的原因，在这两种情形中索引都应该列出所有的帧或磁盘块（也就是说不像,UNIX,那样有间接块）所以块索引在内存中占用了,13 500,个,8,字节的项（,4,个字节用于磁盘地址，,l,个字节用于帧的大小，,3,个字节用于起始帧的帧号），帧索引则在内存中占用了,216 000,个,5,字节的项（只有磁盘地址和帧的大小），比较起来，当电影在播放时，块索引比帧索引节省了接近,1MB,的,RAM,空间。,9.4.2,两个替代的文件组织策略,这些考虑导出了如下的权衡：,1,）帧索引：电影在播放时使用大量的,RAM,；磁盘浪费小。,2,）块索引（禁止分裂帧跨越磁盘块）：,RAM,用量低；磁盘浪费较大。,3,）块索引（允许分裂帧跨越磁盘块）：,RAM,用量低；无磁盘浪费；需要额外寻道。,9.4.2,两个替代的文件组织策略,因此，这里的权衡涉及回放时,RAM,的使用量、自始至终浪费的磁盘空间以及由于额外寻道造成的回放时的性能损失。但是，这些问题可以用各种方法来解决。采用分页操作在需要的时候及时将帧索引装入内存，可以减少,RAM,的使用量。通过足够的缓冲可以屏蔽在帧传输过程中的寻道，但是这需要额外的内存并且可能还需要额外的复制操作。好的设计必须仔细分析所有这些因素，并且为即将投入的应用做出良好的选择。,9.4.3,近似视频点播的文件存放,前面我们了解了视频点播的文件存放策略。对于近似视频点播，采用不同的文件存放策略可以获得更高的效率。近似视频点播将同一部电影作为多个交错的数据流送出。即使电影是作为连续文件存放的，每个数据流也需要进行寻道。有研究者设计了一种文件存放策略几乎可以消除全部这样的寻道。图,9-9,说明了这一方法的应用，图中的电影以每秒,30,帧的速率播放，每隔,5,分钟开始一个新的数据流（参见图,9-6,）。根据这些参数，,2,小时长的电影需要,24,个当前数据流。,图,9-9,针对近似视频点播的优化帧存放策略,9.4.3,近似视频点播的文件存放,在这一存放策略中，由,24,个帧组成的帧集合连成一串并且作为一个记录写入磁盘。它们还可以在一个读操作中被读回。考虑这样一个瞬间，数据流,24,恰好开始，它需要的是第,0,帧，,5,分钟前开始的数据流,23,需要的是第,9000,帧；数据流,22,需要的是第,18 000,帧，以此类推，直到数据流,0,，它需要的是第,20 700,帧。通过将这些帧连续地存放在一个磁道上，视频服务器只用一次寻道（到第,0,帧）就可以以相反的顺序满足全部,24,个数据流的需要。当然，如果存在某一原因要以升序为数据流提供服务，这些帧也可以以相反的顺序存放在磁盘上。,9.4.3,近似视频点播的文件存放,完成对最后一个数据流的服务之后，磁盘臂可以移到磁道,2,准备再次为这些数据流服务。这一方法不要求整个文件是连续的，但是对于若干个同时的数据流仍然给予了良好的性能。,简单的缓冲策略是使用双缓冲。当一个缓冲区正在向外播放,24,个数据流的时候，另一个缓冲区正在预先加载数据。当前操作结束时，两个缓冲区进行交换，刚才用于回放的缓冲区现在在一个磁盘操作中加载数据。,9.4.4,在单个磁盘上存放多个文件,实际上，在视频服务器上当然存在着许多电影。如果它们随机地散布在磁盘上，那么当多部电影被不同的客户同时观看时，时间将浪费在磁头在电影之间来回移动上。通过在磁盘上存放电影时将电影的流行性考虑进去，可以改进这一情况。,9.4.4,在单个磁盘上存放多个文件,对于许多种类的流行性事件，相对流行性的一个合理的近似遵循着一种令人惊奇的可预测模式。这一模式是哈佛大学的一位语言学教授,George Zipf,（,1902-1950,）发现的，被称为,Zipf,定律。该定律说的是，如果电影，图书、,Web,网页或者单词按其流行性进行排名，那么下一个客户选择排行榜中排名为,k,的项的概率是,C/k,。因而，前三部电影的命中率分别是,C/1,、,C/2,和,C/3,，其中,C,的计算要使全部项的和为,1,（归一化常数）。换句话说，如果有,N,部电影，那么,C/1 + C/2 + C/3 + C/4 + ,C/N = 1,9.4.4,在单个磁盘上存放多个文件,从这一公式，,C,可以被计算出来。对于具有,10,个、,100,个、,1000,个和,10 000,个项的总体，,C,的值分别是,0.341,、,0.193,、,0.134,和,0.102,。例如，对于,1000,部电影，前,5,部电影的概率分别是,0.134,、,0.067,、,0.045,、,0.034,和,0.027,。,有趣的是，将,Zpf,定律应用于美国,20,座最大城市的人口。,Zpf,定律预测第二大城市应该具有最大城市一半的人口，第三大城市应该具有最大城市三分之一的人口，以此类推虽然不尽完美，该定律却令人惊奇地吻合。,9.4.4,在单个磁盘上存放多个文件,对于视频服务器上的电影而言，,Zipf,定律表明最流行的电影被选择的次数是第二流行的电影的两倍，是第三流行的电影的三倍，以此类推。尽管分布在开始时下降得相当快，但是它有着一个长长的尾部，例如，排名,50,的电影拥有,C/50,的流行性，排名,51,的电影拥有,C/51,的流行性，所以排名,51,的电影的流行性是排名,50,的电影的,50/51,，只有大约,2,的差额。随着尾部进一步延伸，相邻电影间的百分比差额变得越来越小。一个结论就是，服务器需要大量的电影，因为对于前,l0,名以外的电影存在着潜在的需求。,9.4.4,在单个磁盘上存放多个文件,了解不同电影的相对流行性，使得对视频服务器的性能进行建模以及将该信息应用于存放文件成为可能。研究已经表明，最佳的策略令人惊奇地简单并且独立于分布。这一策略称为管风琴算法（概率直方图看起来像是一个稍稍不对称的管风琴）。该算法将最流行的电影存放在磁盘的中央，第二和第三流行的电影存放在最流行的电影的两边，在这几部电影的外边是排名第四和第五的电影，以此类推，如图,9-10,所示。,图,9-10,视频服务器上文件的管风琴分布,9.4.4,在单个磁盘上存放多个文件,如果每一部电影是如图,9-8,所示类型的连续文件，这样的存放方式工作得好；如果每一部电影被约束在一个狭窄的柱面范围之内，这样的存放方式也可以扩大其使用的范围。,该算法所做的是试图将磁头保持在磁盘的中央。当服务器上的电影有,1000,部时，根据,Zipf,定律分布排在前,5,名的电影代表了,0.307,的总概率，这意味着大约,30,的时间磁头停留在为排在前,5,名的电影分配的柱面中，如果有,1000,部电影可用，这是一个惊人的数量。,9.4.5,在多个磁盘上存放文件,为了获得更高的性能，视频服务器经常拥有可以并行运转的很多磁盘，有时会用到,RAID,。视频服务器通常希望高的性能而对于校正传输错误不怎么太关心。此外，如果,RAID,控制器有太多的磁盘要同时处理，那么,RAID,控制器可能会成为一个瓶颈。,更为普通的配置只是数目很多的磁盘，有时被称为磁盘园。这些磁盘不像,RAID,那样以同步方式旋转，也不像,RAID,那样包含奇偶校验位。一种可能的配置是将电影,A,存放在磁盘,1,上，将电影,B,存放在磁盘,2,上，以此类推，如图,9-11 a,）所示。实际上，使用新式的磁盘，每个磁盘上可以存放若干部电影。,图,9-11,在多个磁盘上组织多媒体文件的四种方式,9.4.5,在多个磁盘上存放文件,这一组织方式实现起来很简单，并且具有简单明了的故障特性：如果一块磁盘发生故障，其上的所有电影都将不再可用。注意，一家公司损失了一块装满了电