Marco Lapegna » 15.I Sistemi Operativi distribuiti - parte seconda

Sistemi operativi per sistemi con molti processori

Come l’hardware anche il software di sistema può avere differenti “intensità” di accoppiamento:

• sistemi operativi per multiprocessor (MOS): accoppiamento stretto su sistemi multiprocessor;
• sistemi operativi distribuiti (DOS): accoppiamento stretto su sistemi multicomputer;
• sistemi operativi di rete (NOS): accoppiamento sw debole su sistemi multicomputer.

Sistemi operativi per multiprocessor (MOS)

Accoppiamento sw stretto su multiprocessor.

stessi obiettivi di un sistema operativo monoprocessore:

• un unico sistema operativo;
• potrebbe non essere considerato un vero e proprio sistema operativo distribuito, ma l’adattamento di un s.o. tradizionale ad un sistema multiprocessore.

L’utente ha l’impressione di una sola CPU:

• gestione centralizzata delle risorse;
  • unica ready queue;
  • memoria;

S.O. per multiprocessori

Il modo più semplice per organizzare un MOS consiste nel dividere staticamente la memoria quante sono le CPU.

Viene condiviso il codice del s.o. ma ogni CPU ha dati separati.

Le CPU lavorano come computer indipendenti.

Problema: non si sfrutta la condivisione.

S.O. per multiprocessori (segue)

Una seconda organizzazione si basa sul modello master/slave.

Una CPU esegue il s.o. mentre le altre eseguono i processi utente.

Risolve tutti i problemi di efficienza del modello precedente.

Problema: collo di bottiglia nella CPU1.

S.O. per multiprocessori (segue)

Una terza organizzazione mira ad eliminare la asimmetria dell’approccio precedente (modello Symmetric Multi Processor SMP).

Ogni CPU può eseguire sia il S.O. sia i processi utente e tutta la memoria è a disposizione di tutte le CPU.

Miglior bilanciamento nell’uso delle risorse.

Problema: sincronizzazione nell’accesso alle strutture dati del s.o.

S.O. per multicomputer

Indipendentemente dal tipo di s.o. i multiprocessori hanno il collo di bottiglia rappresentato dalle risorse comuni (soprattutto l’accesso alla memoria).

Lo stato dell’arte oggi è rappresentato dai multicomputer.

Due tipi di sistemi operativi

1. Sistemi operativi di rete: es. Unix con strumenti tipo ftp, telnet, NFS;
2. Sistemi operativi distribuiti: es. Amoeba.

Sistema operativo distribuito (segue)

Architettura microkernel, dove i processi sulle varie macchine comunicano e si sincronizzano attraverso scambio di messaggi: send, receive.

Il kernel locale (lo stesso per tutti i computer) gestisce le risorse fisiche locali (es: paginazione della memoria, scheduling della CPU).

Più difficile da realizzare.

Scheduling nei sistemi multiprocessori

Analogamente ai sistemi monoprocessori, lo scheduling nei sistemi multiprocessore ha come obiettivi:

• massimizzazione del throughput;
• minimizzazione del tempo medio di attesa.

Diversamente dai sistemi monoprocessori, lo scheduling nei sistemi multiprocessore deve:

• non solo decidere l’ordine con cui eseguire i processi;
• ma anche determinare quale processore deve eseguire un dato processo.

Osservazione: di solito su sistemi multiprocessore sono eseguiti applicazioni parallele composte da più processi (insieme di processi cooperanti e correlati).

Ruolo chiave dello scheduling nei sistemi operativi per sistemi a molti processori.

Scheduling dei processi

Il modo più semplice per sviluppare uno scheduler per un sistema multiprocessore è immaginare:

• un’unica coda di processi pronti (coda globale); oppure
• una coda di processi pronti per ogni CPU (code multiple);

gestite secondo una qualunque politica di scheduling monoprocessore.

Ogni volta che un processore risulta disponibile viene assegnato un processo in testa alla coda (alle code) al processore.

Esempio: P=2 processori

Problema

L’approccio descritto assegna i processi alla CPU “alla cieca”, senza tenere conto delle caratteristiche dei processi e delle CPU
(scheduling job-blind).

Due grossi svantaggi:

1. processi cooperanti di una stessa applicazione potrebbero essere schedulati “in sequenza” e non viene sfruttato il parallelismo (soprattutto se comunicano);
2. un processo prelazionato, potrebbe non essere schedulato sulla stessa CPU, e non può più utilizzare i dati che aveva nella propria cache.

Condivisione di tempo

Un sistema parallelo è composto da numerose CPU.

Obiettivo 1: Massimizzazione del parallelismo.

Strategia: raggruppare processi cooperanti di una stessa applicazione e schedularli assieme sulle varie CPU.

Scheduling a condivisione di tempo.

Partizionamento dello spazio

Un processo che già ha avuto accesso ad una CPU ha già delle pagine nei TLB (o nella cache) di quel processore.

Obiettivo 2: favorire l’affinità con la CPU.

Strategia: assegnare un processo ad una CPU (o a un numero ristretto di CPU che condividono un’area di memoria) in maniera da massimizzare i TLB hit.

Scheduling a partizionamento di spazio

Scheduling job aware

Gli algoritmi di scheduling a condivisione di tempo o a partizionamento dello spazio fanno parte di un approccio che tiene conto del tipo di job e per questo è chiamato: scheduling job aware.

Svantaggio: maggiore complessità dell’algoritmo di scheduling.

Esempio di scheduling

Algoritmo Smallest Number of Process First (SNPF).

Versioni con e senza prelazioni.
Coda globale a priorità: la priorità è inversamente proporzionale al numero di processi che compone l’applicazione.

I processi associati allo stesso job ricevono la stessa priorità e quindi sono spesso schedulati insieme:

• massimizzazione del parallelismo: si (se non c’ è prelaz.);
• massimizzazione dell’affinita’ con le CPU: buona ma non garantita.

Possibilità di posticipazione indefinita o di asincronia per applicazioni con molti processi.

Esempio: 4 CPU

SNPF con prelazione.

Esempio di scheduling (segue)

Algoritmo di coscheduling (schedulazione gang).

Basata su round robin.
Processi di una stessa applicazione vengono schedulati sempre insieme:

• massimizzazione del parallelismo: si;
• massimizzazione dell’affinita’ con le CPU: buona ma non garantita.

Non c’è posticipazione indefinita.

Esempio: 4 CPU

Coscheduling e q=20.