Hệ điều hành - Chapter 7: Multimedia

MultimediaChapter 77.1 Introduction to multimedia7.2 Multimedia files 7.3 Video compression 7.4 Multimedia process scheduling 7.5 Multimedia file system paradigms 7.6 File placement 7.7 Caching 7.8 Disk scheduling for multimedia 1Introduction to Multimedia (1)Video On Demand: (a) ADSL vs. (b) cable 2Introduction to Multimedia (2)Some data ratesmultimedia, high performance I/O devicesNote: 1 Mbps = 106 bits/sec but 1 GB = 230 bytes3Multimedia FilesA movie may consist of several files4Audio Encoding (1)Audio Waves Converted to Digitalelectrical voltage inputbinary number as output5Audio Encoding (2)Error induced by finite sampling called quantization noiseExamples of sampled soundtelephone – pulse code modulationaudio compact disks6Video EncodingScanning Pattern for NTSC Video and Television7Video CompressionThe JPEG Standard (1)RGB input data and block preparation8The JPEG Standard (2)One block of the Y matrix and the DCT coefficients9The JPEG Standard (3)Computation of the quantized DCT coefficients10The MPEG Standard (1)Order of quantized values when transmitted11The MPEG Standard (2)MPEG-2 has three kinds of frame: I, P, B Intracoded framesSelf-contained JPEG-encoded pictures Predictive framesBlock-by-block difference with last frame Bi-directional framesDifferences with last and next frame12The MPEG Standard (3)Consecutive Video Frames13Multimedia Process SchedulingPeriodic processes displaying a movieFrame rates and processing requirements may be different for each movie14Rate Monotonic SchedulingUsed for processes which meet these conditionsEach periodic process must complete within its periodNo process dependent on any other processEach process needs same CPU time each burstAny nonperiodic processes have no deadlinesProcess preemption occurs instantaneously, no overhead15Earliest Deadline First Scheduling (1)Real Time Scheduling algorithms RMS EDF16Earliest Deadline First Scheduling (2)Another example of real-time scheduling with RMS and EDF17Multimedia File System ParadigmsPull and Push Servers18VCR Control FunctionsRewind is simpleset next frame to zeroFast forward/backward are trickiercompression makes rapid motion complicatedspecial file containg e.g. every 10th frame19Near Video on DemandNew stream starting at regular intervals20Near Video on Demand with VCR FunctionsBuffering for Rewind21File PlacementPlacing a File on a Single DiskInterleavingVideo, audio, text in single contiguous file per movieFrame 1Frame 2Frame 3AudioFrameTextFrame22Two Alternative File Organization Strategies (1)Noncontiguous Movie Storage(a) small disk blocks(b) large disk blocks23Two Alternative File Organization Strategies (2)Trade-offs between small, large blocksFrame indexheavier RAM usage during movie playlittle disk wastage Block index (no splitting frames over blocks)low RAM usage major disk wastageBlock index (splitting frames over blocks allowed)low RAM usageno disk wastageextra seeks24Placing Files for Near Video on DemandOptimal frame placement for near video on demand25Placing Multiple files on a Single Disk (1)Zipf's law for N=20Squares for 20 largest cities in US sorted on rank order26Placing Multiple files on a Single Disk (2)Organ-pipe distribution of files on servermost popular movie in middle of disknext most popular either on either side, etc.27Placing Files on Multiple DisksOrganize multimedia files on multiple disks(a) No striping(b) Same striping pattern for all files(c) Staggered striping(d) Random striping28CachingBlock Caching(a) Two users, same movie 10 sec out of sync(b) Merging two streams into one29File CachingMost movies stored on DVD or tapecopy to disk when neededresults in large startup timekeep most popular movies on diskCan keep first few min. of all movies on diskstart movie from this while remainder is fetched30Disk Scheduling for MultimediaStatic Disk SchedulingIn one round, each movie asks for one frameOrder in which disk requests are processed Stream31Dynamic Disk SchedulingScan-EDF algorithmuses deadlines & cylinder numbers for scheduling32