Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Marco Lapegna » 12.I S.O. multimediali – parte seconda


Algoritmi di scheduling per il multimedia

un processo la cui deadline sia a rischio dovrebbe interrompere il processo in esecuzione

Uso di algoritmi con prelazione

Gli algoritmi di scheduling con prelazione possono essere:

  • Con priorità prefissate (es. algoritmo di schedulazione a frequenza monotona);
  • Con priorità dinamiche (es. algoritmo di schedulazione a scadenza più vicina).

Schedulazione a frequenza monotona

Rate Monotonic Scheduling (RMS)

Utilizzabile quando:

  • Ogni processo periodico va completato entro una sua deadline;
  • I processi sono indipendenti;
  • Ogni processo richiede la stessa quantità di calcolo in ogni periodo;
  • I processi non periodici non hanno deadline;
  • Overhead per il cambio di contesto nullo (per semplicità).

Algoritmo con prelazione e con priorità, dove la priorità è uguale alla frequenza.

Esempio (1)

3 processi, A, B e C:

  • A periodo P=30ms → frequenza = 33.3 volte/sec
  • B periodo P=40ms → frequenza = 25 volte/sec
  • C periodo P=50ms → frequenza = 20 volte/sec

Esempio (2)

3 processi, A, B e C (stesse frequenze dell’esempio precedente)

  • A tempo di esecuzione = 15ms (10ms nell’esempio precedente);
  • B stesso tempo di esecuzione dell’esempio precedente;
  • C stesso tempo di esecuzione dell’esempio precedente.

Perché?


Schedulabilità dell’algoritmo RMS


Schedulabilità dell’algoritmo RMS


Schedulazione alla deadline più vicina

Earliest Deadline First (EDF)

Non richiede che:

  • I processi siano periodici;
  • I processi abbiano lo stesso tempo di esecuzione.

Utile in caso di carico variabile della CPU

Algoritmo con prelazione dove la priorità è calcolata in base alla deadline più vicina

Esempio EDF


Schedulabilità dell’algoritmo EDF


RMS vs EDF


Funzioni Video Cassette Recorder (VCR)


Semantica del file system

Analogamente ai processi, anche l’accesso ai file multimediali ha esigenze di garanzie di rispetto delle scadenze con caratteristiche di regolarità:

  • nel tempo (accesso a intervalli di tempo costante);
  • nello spazio (accesso prevalentemente sequenziale).

La semantica dell’accesso ai file per sistemi general purpose basata sulle funzioni:

  • open, close;
  • read, write.

Non è indicata

Implementazione con open e read


Soluzione alternativa


Funzioni pausa e riavvolgimento

Funzione pausa: il file system del video server memorizza il numero del blocco successivo e interrompe il flusso. Con un nuovo start si riprende da dove ci si era fermati.

Funzione riavvolgimento: il file system del video server annota che il blocco successivo è il blocco 0.


Avanti e dietro veloce (es. 10x)

File non compresso: una velocita’ 10x viene realizzata inviando un frame ogni 10.

File compresso: i frame compressi non hanno tutti la stessa dimensione a causa del differente contenuto:

  • Il server decomprime tutti i frame e ne spedisce uno ogni 10 (lavoro aggiuntivo del server);
  • Spedire il file a una velocita’ 10x e far selezionare al client un frame ogni 10 ( la rete potrebbe non supportare la velocita’);
  • Tenere memorizzato sul server un file con un frame ogni 10 (spazio aggiuntivo sul server per tutte le velocita’ di riproduzione).

In ogni caso soluzione non facile

I materiali di supporto della lezione

Silberschatz , Galvin, Gagne – Sistemi Operativi 8a ed. Capitolo 20

Tanenbaum – Moderni sistemi operativi 3a ed. Capitolo 7

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion