Chi usa la CPU? Turni, attese e scheduling

Scarica la lezione, il laboratorio, gli esercizi e le soluzioni (PDF, 6 pagine)

Informatica · Scuola secondaria di secondo grado · Percorso proposto per il triennio

In breve

Quando più programmi sono pronti a lavorare, il sistema operativo deve scegliere chi usa la CPU. Una regola semplice serve i processi nell’ordine di arrivo; un’altra assegna turni brevi e ripetuti. Con tre processi e una linea del tempo scopriremo che iniziare presto non significa finire presto. Confronteremo FCFS e round robin misurando risposta, attesa e tempo totale di completamento. Non cercheremo un algoritmo “migliore in assoluto”: impareremo a scegliere un criterio e a dichiarare le ipotesi.

Obiettivi. Costruire una traccia temporale; aggiornare una coda; calcolare tre metriche; motivare un confronto usando dati, non impressioni.

Prerequisiti. Processo come programma in esecuzione; somme e medie; lettura di tabelle. Python è facoltativo. Durata indicativa: 70 minuti: introduzione 10, esempio 15, attività 20, esercizi e discussione 25. Tempi da adattare alla classe.

1. Una CPU, più attività pronte

Immagina tre programmi pronti: A deve elaborare molti dati, B fare un calcolo più breve, C completare una piccola operazione. Su un solo core, nel nostro modello, ne eseguiamo uno alla volta. Alternare i programmi permette di farli avanzare nello stesso intervallo complessivo: è concorrenza, non esecuzione simultanea su quel core.

Lo scheduler è il componente che sceglie la prossima attività fra quelle pronte. “Pronto” significa che il processo potrebbe usare la CPU, ma aspetta il proprio turno; un processo bloccato in attesa di dati non è semplicemente in coda per la CPU. Il passaggio fra attività richiede di conservare e ripristinare il loro stato: è il cambio di contesto. [1, §§7.1 e 7.7; 2, §§6.1.1–6.1.4]

Useremo una macchina di carta: un core, tutti i processi arrivano al tempo 0, ordine iniziale A–B–C, nessun I/O, nessuna priorità diversa, nessun costo di cambio di contesto. Ogni processo ha un solo tratto di lavoro CPU, detto burst, di durata nota e positiva. I tempi sono unità astratte: non secondi misurati su un computer reale. Queste semplificazioni servono a isolare la regola di scelta.

2. Tre domande, tre misure

Indichiamo con a l’istante di arrivo, s il primo avvio, f la fine e b il lavoro CPU richiesto. [1, §§7.2 e 7.6; 2, §6.2]

La formula dell’attesa vale qui perché non c’è I/O: tutto il tempo non passato sulla CPU è attesa in coda. Con periodi bloccati occorrerebbe separarli dall’attesa per la CPU. Per “risposta” adottiamo la convenzione del primo avvio, non il tempo necessario a mostrare un risultato sullo schermo. La media si calcola sommando i valori dei singoli processi e dividendo per il loro numero.

3. FCFS: chi arriva prima viene servito prima

First-Come, First-Served (FCFS) segue l’ordine di arrivo. Nel nostro caso, gli arrivi simultanei sono risolti con l’ordine dichiarato A–B–C. Una volta partito, un processo conserva la CPU fino alla fine del proprio burst: questa politica è non preemptive, cioè non gli toglie il turno a metà del lavoro. [1, §7.3; 2, §6.3.1]

Traccia FCFS: 0–7 A | 7–11 B | 11–12 C

Ogni intervallo include l’inizio ed esclude la fine: A usa sette unità, non otto. C chiede solo un’unità, ma inizia dopo undici. L’ordine può penalizzare un lavoro breve posto dietro uno lungo: è il problema illustrato dal convoy effect nelle fonti. Non è un errore aritmetico, ma una conseguenza della politica.

4. Round robin: un turno non è tutto il lavoro

Round robin (RR) usa una coda e un quantum q, la durata massima di un turno. Prendiamo q = 2. Estraiamo il primo processo, gli concediamo il minore fra quantum e lavoro residuo e, se non ha finito, lo rimettiamo in fondo. Se finisce prima, il prossimo parte subito: il turno non deve essere riempito artificialmente. RR è preemptive: alla scadenza può interrompere il processo e riprenderlo dopo, senza ricominciare da zero. [1, §7.7; 2, §§6.1.3 e 6.3.4]

Traccia RR, q = 2:

0–2 A | 2–4 B | 4–5 C | 5–7 A | 7–9 B | 9–11 A | 11–12 A

Dopo il primo turno A ha ancora 5 unità; la coda è B–C–A. C finisce al tempo 5: richiedeva un’unità e non consuma due unità solo perché q vale 2. Al tempo 9 rimane soltanto A; i segmenti 9–11 e 11–12 sono due turni consecutivi dello stesso processo, non due cambi ad altro processo.

Medie FCFS: R = 6; T = 10; W = 6. Medie RR q=2: R = 2; T = 26/3 ≈ 8,67; W = 14/3 ≈ 4,67. Per A, però, la fine slitta da 7 a 12. Una media migliore non significa un miglioramento per ogni processo. In entrambi i casi il lavoro CPU totale resta 12: cambiare l’ordine non elimina istruzioni.

5. Laboratorio: cambiare il quantum, non i dati

Materiali: foglio, matita e tre carte A:7, B:4, C:1. A coppie, una persona aggiorna la coda e l’altra controlla il tempo; scambiate i ruoli nella seconda prova. Non avviate processi reali, non cambiate impostazioni del computer e non usate dati personali.

Prima di calcolare, prevedete cosa succederà alla prima risposta di C se il turno scende da 2 a 1. Scrivete anche che cosa non potete ancora prevedere senza completare la traccia.

1. Ripartite dal tempo 0, con residui A=7, B=4, C=1 e coda A–B–C.
2. Simulate RR con q=1, senza saltare i turni di un processo incompleto.
3. Per ogni turno registrate inizio, processo, durata, fine, residuo e coda dopo il turno.
4. Annotate il primo avvio una sola volta e la fine solo quando il residuo diventa zero.
5. Calcolate R, T e W per ciascun processo, poi le medie.
6. Azzerate tutto e ripetete con q=7. Confrontate con q=2 e FCFS.

Continuate sul quaderno: per q=1 occorrono dodici righe. Consegna: due tracce complete, tabella delle metriche, previsione iniziale e conclusione di quattro righe. Nella conclusione indicate chi guadagna, chi perde e con quale misura. Controllo utile: la somma delle durate deve restare 12.

L’algoritmo, senza un linguaggio particolare

metti i processi nella coda iniziale
tempo = 0
finché la coda non è vuota:
    estrai il primo processo P
    se P non è mai partito: registra tempo come primo avvio
    durata = minimo(quantum, residuo di P)
    registra il segmento e aumenta tempo di durata
    sottrai durata dal residuo di P
    se il residuo è positivo: rimetti P in fondo
    altrimenti: registra tempo come fine di P

Estensione Python facoltativa. Il file locale laboratorio-scheduling.py applica queste stesse regole con una coda, senza dipendenze esterne. In un ambiente predisposto dal docente, eseguite python3 laboratorio-scheduling.py e confrontate ogni segmento con la vostra traccia. Il programma mostra FCFS e RR con q=1, 2 e 7. Non misura lo scheduler del sistema operativo: è una simulazione dei dati della lezione.

Perché non scegliere un quantum infinitamente piccolo?

Il modello ha costo di commutazione nullo, ma i computer reali impiegano tempo per cambiare contesto. Ridurre troppo il turno può aumentare la quota di tempo spesa nella gestione anziché nel lavoro utile. Un quantum grande riduce la frequenza delle interruzioni, ma può far aspettare più a lungo prima del primo avvio. Occorre un compromesso: dai soli dati di carta non ricaviamo un quantum ottimale per un PC reale. [1, §7.7, riquadro “Amortization Can Reduce Costs”; 2, §6.3.4]

6. Esercizi — prima delle soluzioni

Nome: …………………………………. Classe: ………… Data: …………

Per tutti i calcoli usa un core, nessun I/O e costo di cambio nullo. Gli intervalli non si sovrappongono. Spiega almeno un passaggio per risposta.

1 · Leggere le metriche

Un processo arriva a=3, parte per la prima volta a s=5, termina a f=12 e svolge b=6 unità di CPU. Calcola risposta, turnaround e attesa. Perché non basta fare “primo avvio meno arrivo” per trovare tutta l’attesa di un processo interrotto?

Spazio per il ragionamento:

……………………………………………………………………………………….

……………………………………………………………………………………….

2 · Correggere una traccia

Con A=7, B=4, C=1, arrivo simultaneo a 0, ordine A–B–C e RR q=2, una persona scrive: 0–2 A | 2–4 B | 4–6 C | 6–8 A. Individua il primo errore. Riscrivi il segmento di C e il turno di A immediatamente successivo, spiegando l’effetto sul tempo.

……………………………………………………………………………………….

……………………………………………………………………………………….

3 · Finire presto o iniziare presto?

Nuovo insieme: X=3, Y=3, Z=3; tutti arrivano a 0, ordine X–Y–Z. Disegna FCFS e RR con q=1. Calcola risposta media e turnaround medio per entrambi. La frase «RR migliora sempre tutte le medie» è corretta? Non usare i risultati di A, B e C al posto dei nuovi calcoli.

……………………………………………………………………………………….

……………………………………………………………………………………….

……………………………………………………………………………………….

4 · Dalla coda all’algoritmo

Nel pseudocodice del laboratorio si commette un errore: un processo incompleto viene rimesso in testa, invece che in fondo. Simula i primi quattro turni di A=7, B=4, C=1 con q=2. Quando comincia B? Quale proprietà dei turni si perde? Con questi tre lavori finiti si verifica necessariamente un’attesa infinita?

……………………………………………………………………………………….

……………………………………………………………………………………….

5 · Valutare una conclusione

«Con q=1 tutti e tre finiscono al tempo 12, quindi hanno tutti turnaround 12. Inoltre il computer reale sarà più veloce che con q=2». Trova due errori distinti. Usa i risultati del laboratorio per correggere il primo e le ipotesi del modello per discutere il secondo.

……………………………………………………………………………………….

……………………………………………………………………………………….

7. Soluzioni commentate

Laboratorio — q=1 e q=7

RR q=1: 0–1 A | 1–2 B | 2–3 C | 3–4 A | 4–5 B | 5–6 A | 6–7 B | 7–8 A | 8–9 B | 9–10 A | 10–11 A | 11–12 A.

q=1: medie R=1, T=8, W=4. C comincia e finisce prima rispetto a q=2; A e B terminano agli stessi istanti di q=2. q=7: traccia e medie coincidono con FCFS, perché ogni burst termina entro il primo turno e l’ordine resta A–B–C. Non basta in generale dire “quantum grande”: qui è almeno pari al maggiore dei tre burst. Le righe consecutive di A restano turni del simulatore, non prove di cambio a un altro processo.

1 · Le sottrazioni hanno significati diversi

R=5−3=2; T=12−3=9; W=9−6=3. Fra arrivo e fine ci sono nove unità: sei di lavoro e tre di attesa. Il tempo prima del primo avvio è solo due: il processo può aspettare ancora dopo un’interruzione. L’identità W=T−b usa l’assenza di I/O.

2 · Il turno può essere più breve del quantum

Il primo errore è 4–6 C: C ha solo un’unità residua. La correzione è 4–5 C | 5–7 A. Nessuno aspetta un’unità “vuota” per completare il quantum di C. I turni successivi vanno ricalcolati dalla nuova fine.

3 · Un controesempio all’“algoritmo sempre migliore”

FCFS: 0–3 X | 3–6 Y | 6–9 Z. Risposte 0, 3, 6: media 3. Fine e turnaround 3, 6, 9: media 6.

RR q=1: 0–1 X | 1–2 Y | 2–3 Z | 3–4 X | 4–5 Y | 5–6 Z | 6–7 X | 7–8 Y | 8–9 Z. Risposte 0, 1, 2: media 1. Fine e turnaround 7, 8, 9: media 8. RR qui migliora la prima risposta media ma peggiora il turnaround medio. Il vantaggio dipende dalla metrica e dai dati, non dal nome dell’algoritmo.

4 · La testa della coda cambia la politica

I primi quattro turni sono 0–2 A | 2–4 A | 4–6 A | 6–7 A. B inizia a 7. A scavalca ogni volta B e C: si perde la rotazione fra processi pronti. Con questi lavori finiti A termina e gli altri possono procedere, quindi non si dimostra un’attesa infinita. La simulazione non implementa più RR correttamente.

5 · Fine del gruppo e fine individuale non coincidono

Il gruppo termina al tempo 12, ma B finisce a 9 e C a 3: i turnaround con q=1 sono 12, 9 e 3, non tre volte 12. Inoltre non abbiamo misurato un computer reale e ignoriamo il costo dei cambi di contesto. Non possiamo trasformare un risultato del modello in una promessa di velocità reale; in questo modello il lavoro complessivo finisce a 12 sia con q=1 sia con q=2.

8. Da ricordare, senza scorciatoie

Risposta non è completamento. Nel lessico scelto, rispondere significa ottenere il primo turno; finire significa aver esaurito tutto il lavoro. Una buona risposta media può convivere con un turnaround medio peggiore.

Un turno non azzera il lavoro fatto. Dopo due unità di CPU, A passa da residuo 7 a 5. Quando torna in esecuzione riprende dal residuo, non ricomincia da 7.

Una media non descrive tutti. Per confrontare due politiche osserva sia il valore medio sia i singoli processi. Nel nostro esempio A finisce più tardi con RR anche se diverse medie migliorano.

La coda conta. L’ordine A–B–C è una regola esplicita per risolvere gli arrivi simultanei. Cambiarlo significa cambiare l’esperimento, non correggere un calcolo.

Il modello ha confini. I sistemi reali gestiscono I/O, arrivi in tempi diversi, thread, priorità, più core e costi di gestione. FCFS e RR sono qui politiche di riferimento, non la descrizione completa dello scheduler di un particolare sistema operativo.

Verifica di uscita

Spiega in due frasi perché, nei dati A=7, B=4, C=1, RR può far partire C prima senza ridurre il lavoro totale. Poi indica un dato mancante per prevedere il comportamento di un computer reale.

Risposta possibile: i turni brevi permettono a C di usare la CPU senza aspettare che A e B finiscano, ma le dodici unità di lavoro richieste restano le stesse. Per una previsione reale servirebbero, fra gli altri dati, i costi dei cambi di contesto e il carico effettivo.

Fonti per approfondire

[1] Remzi H. Arpaci-Dusseau e Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, capitolo 7, “Scheduling: Introduction”. Università del Wisconsin–Madison. Capitolo originale in PDF.

Locatori nel capitolo: §7.1, pp. 1–2, ipotesi del carico; §7.2, p. 2, equazione 7.1, turnaround; §7.3, pp. 2–4, FIFO/FCFS; §7.6, p. 6, equazione 7.2, primo avvio come risposta; §7.7, pp. 7–9, turni RR e compromesso del quantum, incluso il riquadro “Amortization Can Reduce Costs” a p. 8. La nota 3 a p. 6 distingue la convenzione del primo avvio da altre definizioni di risposta.

[2] John T. Bell, University of Illinois Chicago, “CPU Scheduling”. Note originali.

Locatori: §6.1.1, alternanza CPU/I/O; §6.1.2, scelta dalla ready queue; §§6.1.3–6.1.4, preemption e dispatcher; §6.2, turnaround, attesa e risposta; §6.3.1, FCFS; §6.3.4, round robin, quantum e costo dei cambi di contesto. Le note descrivono la risposta interattiva; la formula adottata nella lezione è esplicitamente quella di [1].

Gli esempi A–B–C, X–Y–Z, le attività e gli esercizi sono costruiti per questa lezione. Tabelle e dati sono simulati, non misure sperimentali. La spiegazione è una rielaborazione originale: non riproduce figure delle fonti.

Nota didattica. Revisione docente e prova in classe restano aperte. La classe destinataria e i tempi sono proposte da adattare, non una validazione didattica già svolta.

#!/usr/bin/env python3
"""Modello didattico: un core, tutti gli arrivi a zero, nessun I/O.
Nessun thread reale, nessuna modifica alle priorità del sistema, nessuna rete.
Eseguire: python3 laboratorio-scheduling.py
"""
from collections import deque

DATI = (("A", 7), ("B", 4), ("C", 1))


def simula(dati=DATI, quantum=None):
    """quantum=None: FCFS; intero positivo: round robin.

    Ordine iniziale = ordine dei dati. Tempi in unità astratte.
    Costo di commutazione nullo. Le durate sono interi positivi.
    Restituisce segmenti (inizio, fine, nome) e metriche per processo.
    """
    if not dati or len({nome for nome, _ in dati}) != len(dati):
        raise ValueError("Occorrono processi con nomi univoci")
    if any(not isinstance(b, int) or isinstance(b, bool) or b <= 0 for _, b in dati):
        raise ValueError("Le durate devono essere interi positivi")
    if quantum is not None and (not isinstance(quantum, int) or isinstance(quantum, bool) or quantum <= 0):
        raise ValueError("Il quantum deve essere un intero positivo")
    residuo = dict(dati)
    coda = deque(nome for nome, _ in dati)
    primo, fine, traccia = {}, {}, []
    tempo = 0
    while coda:
        nome = coda.popleft()  # Estrai dalla testa della coda.
        primo.setdefault(nome, tempo)  # Registra solo il primo avvio.
        durata = residuo[nome] if quantum is None else min(quantum, residuo[nome])
        traccia.append((tempo, tempo + durata, nome))
        tempo += durata
        residuo[nome] -= durata
        if residuo[nome]:
            coda.append(nome)  # Incompleto: torna in fondo, non in testa.
        else:
            fine[nome] = tempo  # Completato: non rientra nella coda.
    metriche = []
    for nome, burst in dati:
        # Arrivo a=0: R=primo-a; T=fine-a; W=T-burst (qui senza I/O).
        metriche.append({"processo": nome, "burst": burst,
                         "primo_avvio": primo[nome], "fine": fine[nome],
                         "risposta": primo[nome], "turnaround": fine[nome],
                         "attesa": fine[nome] - burst})
    return traccia, metriche


def main():
    for quantum in (None, 1, 2, 7):
        nome = "FCFS" if quantum is None else f"RR q={quantum}"
        traccia, metriche = simula(quantum=quantum)
        print("\n" + nome)
        print(" | ".join(f"{a}-{b}:{p}" for a, b, p in traccia))
        print("Processo burst primo fine risposta turnaround attesa")
        for r in metriche:
            print(" ".join(str(v) for v in r.values()))
        for campo in ("risposta", "turnaround", "attesa"):
            print(f"Media {campo}: {sum(r[campo] for r in metriche) / len(metriche):.2f}")


if __name__ == "__main__":
    main()

processo,arrivo,burst,ordine_iniziale
A,0,7,1
B,0,4,2
C,0,1,3

politica,processo,burst,primo_avvio,fine,risposta,turnaround,attesa
FCFS,A,7,0,7,0,7,0
FCFS,B,4,7,11,7,11,7
FCFS,C,1,11,12,11,12,11
RR q=1,A,7,0,12,0,12,5
RR q=1,B,4,1,9,1,9,5
RR q=1,C,1,2,3,2,3,2
RR q=2,A,7,0,12,0,12,5
RR q=2,B,4,2,9,2,9,5
RR q=2,C,1,4,5,4,5,4
RR q=7,A,7,0,7,0,7,0
RR q=7,B,4,7,11,7,11,7
RR q=7,C,1,11,12,11,12,11

Revisione docente e prova in classe: aperte.