SO-VI-4p-Sistemi Operativi

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


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


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


Tecnologie di distribuzione

(a) ADSL (b) Tramite cavo per TV

Oggi anche cablaggio in fibra ottica dell’utente finale




Velocità di trasmissione


File Multimediali

Organizzati in molti subfile, con necessità di sincronizzazione


Codif ica dell’audio

(a) Segnale continuo

(b) Campionamento

(c) Quantizzazione


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




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


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


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


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




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


Matrici di crominanza e luminanza



• Si applica una DCT (Discrete Cosine Transformation) a ciascunblocco di 8x8 elementi

• Perdite dovute alla discretizzazione



• 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




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


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


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


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




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


Strategie push e pull

• (a) strategia tradizionale, pull server , il client richiede ogni volta

• (b) push server , il client chiede solo la prima volta


Scheduling dei processi

• Vincoli real-time per garantire flussi costanti

• Richieste di CPU potenzialmente diverse• Processi con struttura periodica


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




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


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


Esempio 1

• Entrambi gli algoritmi danno buoni risultati (quasi gli stessi)

• Periodicamente la CPU rimane inattiva (utilizzazione < 1)


Esempio 2

• RMS fallisce perché il processo C manca la sua deadline

• EDF sceglie C perché ha una deadline più vicina di A




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


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’


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)


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




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


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


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


Distr ibuzione di Zipf

• Zipf per N=20• Popolazione delle 20 maggiori città degli Stati Uniti




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


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


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

SO-VI-4p-Sistemi Operativi

Documents

Transcript of SO-VI-4p-Sistemi Operativi