Post on 23-Feb-2018
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 1/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 1
Parte VI
Sistemi Multimedia
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 2
Multimedia
• Materiali multimediali:
– Letteralmente più di un medium (es. testo e immagini)
– Tipicamente filmati con audio (digital video)
• Modalità di distribuzione e fruizione:
– DVD: riprodotti direttamente dal PC
– Video clip: brevi filmati scaricati dalla rete
– Video on demand: film scelti dagli utenti e distribuiti su
• Video server – Grandi server per la distribuzione in tempo reale di
materiali multimediali
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 3
Problemi
• Organizzazione e dimensione dei file
– Diversi tipi di informazione: video, audio, sottotitoli
– Lettura e scrittura veloce da e per la memoria di massa• Trasmissione dell’informazione
– Ampiezza della banda
– Non sempre possibili broadcast e multicast
• Riproduzione in tempo reale
– Modalità di fruizione simile a quella VCR – Ritardi, anche brevi, percepiti come non accettabili
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 4
Tecnologie di distribuzione
(a) ADSL (b) Tramite cavo per TV
Oggi anche cablaggio in fibra ottica dell’utente finale
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 2/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 5
Velocità di trasmissione
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 6
File Multimediali
Organizzati in molti subfile, con necessità di sincronizzazione
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 7
Codif ica dell’audio
(a) Segnale continuo
(b) Campionamento
(c) Quantizzazione
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 8
Codif ica dell’audio: standard
• PCM (telefonia)
– Campionamento a 8 KHz
– 7 bit per campione (USA), 8 bit (Europa) – 56 kbs, 64 Kbps• CD (musicale)
– Campionamento a 44.1 KHz (insufficiente per i cani) – 16 bit per campione (64k livelli) – 1.411 Mbps (stereo)
NB Il range dinamico dell’orecchio è dell’ordine di 106
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 3/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 9
Codif ica del video: standard
• NTSC (USA)
– Never Twice the Same Color
– 525 righe 30 frame al secondo, 4:3
• PAL (Europa)
– È lo standard più diffuso
– 625 righe 25 frame al secondo, 4:3
• SECAM (Francia)
– Adottato anche nell’Europa dell’Est – Come PAL, differisce per la codifica del colore
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 10
Codif ica del colore
• Sui monitor codifica RGB (Red Green Blue)
• Nella TV – Un segnale di luminanza
– Due segnali di crominanza
• Gli standard differiscono nella codifica di luminanza ecrominanza
• Compatibile con il bianco e nero (luminanza)
• L’occhio è più sensibile alla luminanza
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 11
Video digitale
• Frame costituiti da matrici di pixel
• Codifica RGB (Red Green Blue), 24 bit per pixel
• 25 frame al secondo, progressivo (non interallacciato)
• Sfarfallio eliminato dalla frequenza di refresh (>50 Hz)• Risoluzione dell’immagine:
– VGA: 640 x 480 – SVGA: 800 x 600 – XGA: 1024 x 768 – HDTV 720p: 1280 x 720
– HDTV 1080i: 1920 x 1080
• XGA a 25 frame/s richiede 427 Mbps
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 12
Compressione delle immagini
• Riduce la banda necessaria entro limiti accettabili
• Può introdurre una perdita di informazione
– Lossless: processo invertibile senza perdita – Lossy: con perdita di informazione
• Processo asimmetrico
– Codifica: nel server, in genere fuori linea
– Decodifica: nel client, in tempo reale
•Codifica lenta non accettabile in contesti in tempo reale: adesempio videoconferenza
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 4/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 13
Compressione JPEG (passo 1)
• Comprime immagini fisse con rapporti anche di 1:20• Standard ISO 10918
• Immagine di partenza RGB, 640x480, 24 bit/pixel• Codifica in tre matrici con elementi di 8 bit: – Y: matrice 640x480 di luminanza – I e Q: matrici 320x240 di crominanza
• Le matrici I e Q sono ottenute (con perdita) mediando suquattro punti contigui
• Si sottrae a ciascun elemento 128 per avere 0 nel caso medio
• Ogni matrice è divisa in blocchi di 8x8: – Y ha 4800 blocchi – I e Q hanno 1200 blocchi ciascuna
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 14
Matrici di crominanza e luminanza
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 15
Compressione JPEG (passo 2)
• Si applica una DCT (Discrete Cosine Transformation) a ciascunblocco di 8x8 elementi
• Perdite dovute alla discretizzazione
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 16
Compressione JPEG (passo 3)
• I coefficienti DCT sono quantificati dividendoli per i coefficienti diuna matrice di quantificazione
• I coefficienti meno importanti sono ridotti a 0• La matrice premette di stabilire il livello di compressione
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 5/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 17
Compressione JPEG (passi 4 e 5)
• Il coefficiente (0,0), che è la media della matrice, è espressocome differenza da quello del blocco precedente• Linearizzazione dei 64 coefficienti• Sequenze di valori uguali sono compresse
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 18
Compressione MPEG 2
• Standard per la compressione di filmati digitali
• MPEG-1 (ISO 11172) per qualità VCR (352x240 NTSC)
• MPEG-2 (ISO 13818) per qualità broadcast• Riesce ad usare un canale televisivo 5 MHz
• Due livelli di compressione:
– Ridondanza spaziale: ciascun frame è compresso conJPEG
– Ridondanza temporale: sfrutta la sovrapposizione diinformazioni tra frame successivi
• DV (Digital Video) usa solo la ridondanza spaziale
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 19
MPEG 2: t ipi di frame
• Un filmato MPEG contiene tre tipi di frame:
– I (Intracoded frames): frame completi ed autocontenuti.Costituiscono punti fermi cui ‘agganciare’ la decodifica
del filmato (sintonizzazione, FF e RW,…) – P (Predictive frames): espressi come differenza, blocco
per blocco dal frame precedente
– B (Bidirectional frames): espressi come differenze, bloccoper blocco, sia dal frame precedente che dal framesuccessivo. Presuppongono bufferizzazione di almeno tre
frame in ricezione
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 20
MPEG 2: macroblocchi
• Blocchi di 16x16 per la luminanza, e 8x8 per la crominanza• Un frame aggancia i suoi macroblocchi a quelli del frame
precedente (successivo), anche in posizione diversa• L’ampiezza della ricerca è lasciata all’implementazione
• Si codificano le differenze con il macroblocco dell’altro frame• Le differenze sono compresse con JPEG
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 6/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 21
Multimedia file server
• Consentono la fruizione tramite rete di materiale multimediale
• Il server gestisce più utenti che vedono, eventualmente,
filmati diversi in tempi diversi
• Il server gestisce contemporaneamente più stream
• Ciascuna stream consta nell’invio di una sequenza di quadri(frame), a 25 o 30 frame/s
• Per servire una stream il server utilizza due tipi di risorse:
– CPU per elaborare i frame, costruire i pacchetti e gestire iprotocolli
– Dischi per leggere i frame dalla memoria di massa
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 22
Strategie push e pull
• (a) strategia tradizionale, pull server , il client richiede ogni volta
• (b) push server , il client chiede solo la prima volta
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 23
Scheduling dei processi
• Vincoli real-time per garantire flussi costanti
• Richieste di CPU potenzialmente diverse• Processi con struttura periodica
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 24
Schedulabilità
• Scheduling di m processi periodici
• Ci : richiesta di CPU del processo i per ciascun frame
• Pi : periodo con cui i frame del processo i devono esseretrasmessi
• Condizione di schedulabilità:
• Criterio di ammissione: prima di ammettere un nuovoprocesso occorre controllare la schedulabilità
Σi=1
mCi
Pi
≤ 1
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 7/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 25
RMS: Rate Monothonic Scheduling
• Condizioni di applicabilità
– Periodicità dei processi
– Indipendenza dei processi
– Costanza delle richieste di CPU
– Nessun altro processo ha vincoli real time
– Preemption istantanea a costo nullo
• Sceduling a priorità fisse inversamente proporzionali ai
periodi• Le priorità sono preemptive
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 26
EDF: Earlier Deadline First
• Condizioni di applicabilità
– Processi anche non periodici – Richieste di CPU anche variabili
– I processi specificano di volta in volta la dedline
• Lo scheduler mantiene una lista delle deadline
• La CPU è data al processo con deadline più prossima
• Se arriva un nuovo processo con deadline più vicina, il
processo corrente viene interrotto• Dà sempre risultati migliori del RMS
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 27
Esempio 1
• Entrambi gli algoritmi danno buoni risultati (quasi gli stessi)
• Periodicamente la CPU rimane inattiva (utilizzazione < 1)
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 28
Esempio 2
• RMS fallisce perché il processo C manca la sua deadline
• EDF sceglie C perché ha una deadline più vicina di A
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 8/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 29
Funzioni VCR
• Il server deve supportare le funzioni tipiche dei VCR
– Pausa: non crea problemi, ma congela le risorse
– Rewind: ok soprattutto se si torna all’inizio
– FF e FB: avanti e indietro a velocità k, crea problemi acausa della compressione MPEG2
• Non tutti i frame sono di tipo I, cioè autocontenuti
• Troppo costoso per il server decomprimere, a velocità k, e
generare uno stream di frame I• Troppo costoso inviare al client tutto lo stream a velocità k
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 30
Stream precalcolati
• Sono parte del file multimediale predisposta fuori linea• Contengono un sottoinsieme dei frame (p.es. 1 su 10), poi
compressi separatamente• Il server mantiene la corrispondenza fra i tre stream• Quando salta cerca il primo frame I per ‘agganciarsi’
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 31
Near Video on Demand
• Gli stream che partono a tempi fissi ΔS (es. ogni 5 minuti)
• Il cliente si aggancia al prossimo stream (con un’attesa)• Lo stesso stream è destinato a molti utenti• Pochi stream per ogni film (es. 24 per ΔS = 5 minuti, e film di 2 ore)
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 32
Near Video on Demand con VCR
• Si vogliono aggiungere le funzioni di controllo VCR
• Ogni client, in condizioni di regime, bufferizza un intervallo ΔT sia all’indietro che in avanti
• Questo richiede, in certi periodi, di ricevere due stream
• Nella finestra bufferizzata ci si muove senza difficoltà
• Se si salta oltre il buffer:
– Viene fatto partire uno stream ‘privato’
– Questo dura fino a che non si aggancia il più vicino
stream, al massimo Δ
S – Nel frattempo si legge anche dallo stream successivo
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 9/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 33
Esempio
• ΔS = ΔT = 5 minuti
• L’utente inizia la visione alle 8.15
• Per cinque minuti vengono ricevuti lo stream delle 8.15 e quellodelle 8.20, poi il buffer è pieno e si continua su quello delle 8.20
• Dopo un po’ l’utente comincia a fare FB
• Si invia uno stream privato di FB, fino a che non torna a play
• Si invia all’utente uno stream privato, ma riceve anche lo streamsuccessivo
• Lo stream privato cessa quando si cominciano ad usare i framebufferizzati dello stream successivo
• L’uso di stream privati consente anche di iniziare la visione in unmomento qualsiasi
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 34
Esempio (continua)
(a) situazione a regime (d) 4 minuti dopo il salto(b) salto al minuto 12 (e) di nuovo a regime
(c) tre minuti dopo il salto
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 35
Allocazione di file multipli
• Più file sullo stesso disco
• Minimizzare le seek in base alle frequenze dei file
• Distribuzione delle frequenze di Zipf: – Verificata in moltissimi casi simili: libri più letti, lettere più
usate, nomi più usati, città più popolate …..
– Con N film la frequenza del film i-simo in ordine di popolaritàè C/i dove C è una costante di normalizzazione
C/1 + C/2 + C/3 + C/4 + ………….+ C/N = 1
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 36
Distr ibuzione di Zipf
• Zipf per N=20• Popolazione delle 20 maggiori città degli Stati Uniti
7/24/2019 SO-VI-4p-Sistemi Operativi
http://slidepdf.com/reader/full/so-vi-4p-sistemi-operativi 10/10
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 37
Distribuzione a canne d’organo
• Ordinamento spaziale, sui cilindri, basato sulla frequenza• Il film più visto al centro del disco
• Si dimostra che minimizza il tempo complessivo di seek• Con 100 film, la Zipf dice che il 30% del tempo si rimane nei
cilindri allocati ai 5 film più visti
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 38
Caching
• Il normale caching del file system (LRU) non è efficace
• Accesso tipicamente sequenziale, salvo rewind
• Occorre sfruttare la ‘predicibilità’ intrinseca dell’applicazione• Block caching
– Sfrutta la concomitanza di più stream
– Caching dei soli film con più utenti
• File caching
– Impossibile tenere su disco tutti i film a catalogo
– Alcuni film sono residenti su disco
– Per altri viene mantenuto l’inizio per ridurre lo startup
Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 39
Disk scheduling statico
• Tempo diviso in round, della durata di un frame• Le richieste di ogni round vengono riordinate per ottimizzarle
• Si massimizza il numero di stream che possono essere gestite• Necessario comunque il doppio buffering
• Possibili anche più frame per round, e più round per frameSistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 VI - 40
Disk scheduling dinamico
• Ogni richiesta ha associata una deadline ed un cilindro• Algoritmo Scan-EDF
– Raggruppa le richieste in batch in base alla deadline – Ottimizza all’interno del batch in base al cilindro (es.
ascensore)• L’ammissione di un nuovo utente dipende dalle caratteristiche
del film: meglio commedie e love story che film d’azione