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

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