MultimediaIntroduction to Multimedia (1)Introduction to Multimedia (2)Multimedia FilesAudio Encoding (1)Audio Encoding (2)Video EncodingVideo CompressionThe JPEG Standard (1)The JPEG Standard (2)The JPEG Standard (3)The MPEG Standard (1)The MPEG Standard (2)The MPEG Standard (3)Multimedia Process SchedulingRate Monotonic SchedulingEarliest Deadline First Scheduling (1)Earliest Deadline First Scheduling (2)Multimedia File System ParadigmsVCR Control FunctionsNear Video on DemandNear Video on Demand with VCR FunctionsFile PlacementTwo Alternative File Organization Strategies (1)Two Alternative File Organization Strategies (2)Placing Files for Near Video on DemandPlacing Multiple files on a Single Disk (1)Placing Multiple files on a Single Disk (2)Placing Files on Multiple DisksCachingFile CachingDisk Scheduling for MultimediaDynamic Disk Scheduling1Chapter 7Multimedia7.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 multimedia2Introduction to Multimedia (1)Video On Demand: (a) ADSL vs. (b) cable3Introduction to Multimedia (2)• Some data rates– multimedia, high performance I/O devices• Note: 1 Mbps = 106bits/sec but 1 GB = 230bytes4Multimedia FilesA movie may consist of several files5Audio Encoding (1)• Audio Waves Converted to Digital– electrical voltage input– binary number as output6Audio Encoding (2)• Error induced by finite sampling– called quantization noise• Examples of sampled sound– telephone – pulse code modulation– audio compact disks7Video EncodingScanning Pattern for NTSC Video and Television8Video CompressionThe JPEG Standard (1)RGB input data and block preparation9The JPEG Standard (2)One block of the Y matrix and the DCT coefficients10The JPEG Standard (3)Computation of the quantized DCT coefficients11The MPEG Standard (1)Order of quantized values when transmitted12The MPEG Standard (2)MPEG-2 has three kinds of frame: I, P, B1. Intracoded frames- Self-contained JPEG-encoded pictures2. Predictive frames- Block-by-block difference with last frame3. Bi-directional frames- Differences with last and next frame13The MPEG Standard (3)Consecutive Video Frames14Multimedia Process Scheduling• Periodic processes displaying a movie• Frame rates and processing requirements may be different for each movie15Rate Monotonic SchedulingUsed for processes which meet these conditions1. Each periodic process must complete within its period2. No process dependent on any other process3. Each process needs same CPU time each burst4. Any nonperiodic processes have no deadlines5. Process preemption occurs instantaneously, no overhead16Earliest Deadline First Scheduling (1)• Real Time Scheduling algorithms – RMS – EDF17Earliest Deadline First Scheduling (2)Another example of real-time scheduling with RMS and EDF18Multimedia File System ParadigmsPull and Push Servers19VCR Control Functions• Rewind is simple– set next frame to zero• Fast forward/backward are trickier– compression makes rapid motion complicated– special file containg e.g. every 10thframe20Near Video on DemandNew stream starting at regular intervals21Near Video on Demand with VCR FunctionsBuffering for Rewind22File PlacementFrame 1Frame 2 Frame 3AudioFrameTextFramePlacing a File on a Single Disk• Interleaving– Video, audio, text in single contiguous file per movie23Two Alternative File Organization Strategies (1)• Noncontiguous Movie Storage(a) small disk blocks(b) large disk blocks24Two Alternative File Organization Strategies (2)Trade-offs between small, large blocks1. Frame index- heavier RAM usage during movie play- little disk wastage• Block index (no splitting frames over blocks)- low RAM usage - major disk wastage• Block index (splitting frames over blocks allowed)- low RAM usage- no disk wastage- extra seeks25Placing Files for Near Video on DemandOptimal frame placement for near video on demand26Placing Multiple files on a Single Disk (1)• Zipf's law for N=20• Squares for 20 largest cities in US– sorted on rank order27Placing Multiple files on a Single Disk (2)• Organ-pipe distribution of files on server– most popular movie in middle of disk– next most popular either on either side, etc.28Placing Files on Multiple DisksOrganize multimedia files on multiple disks(a) No striping(b) Same striping pattern for all files(c) Staggered striping(d) Random striping29CachingBlock Caching(a) Two users, same movie 10 sec out of sync(b) Merging two streams into one30File Caching• Most movies stored on DVD or tape– copy to disk when needed– results in large startup time– keep most popular movies on disk• Can keep first few min. of all movies on disk– start movie from this while remainder is fetched31Disk Scheduling for MultimediaOrder in which disk requests are processed ÆStreamStatic Disk Scheduling• In one round, each movie asks for one frame32Dynamic Disk Scheduling• Scan-EDF algorithm– uses deadlines & cylinder numbers for