Sistemi Operativi

Come si studia

Riconosci, applica, verifica.

Il pattern dice cosa guardare, il template dà il codice da adattare, la checklist ferma gli errori prima della consegna.

1Riconosci il pattern

C1 / Monitor · 4 pattern

Generazioni e snapshot

Ricetta e controlli

Si riconosce da — "tutti quelli attualmente in attesa", cambio chiave, media o numero comune

Ricetta

Fotografa count/result, chiudi la generazione, segnala solo dopo aver congelato i dati.

Nuovi arrivi separati · Risultato non sovrascritto · Reset eseguito dall ultimo

Vedi gli esempi svolti →

Rendez-vous esatto

Ricetta e controlli

Si riconosce da — Gruppi di n, coppie, matching tra classi

Ricetta

Coda o condition per classe; l ultimo arrivato compone il gruppo e assegna i risultati.

FIFO richiesta · Classi indipendenti · Nessun membro usato due volte

Vedi gli esempi svolti →

Risveglio selettivo

Ricetta e controlli

Si riconosce da — Soglia, colore, chiave, posizione n-esima

Ricetta

Rappresenta separatamente le classi di attesa e segnala soltanto la guardia diventata vera.

Predicate diverse · Politica di fairness · Signal-urgent compreso

Vedi gli esempi svolti →

Scenario a fasi

Ricetta e controlli

Si riconosce da — Nave, torneo, volo, porto, conferenza

Ricetta

Esplicita stato/fase, contatori di completamento e transizioni che aprono la fase successiva.

Una sola transizione · Riutilizzabilita · Nessun processo della fase futura entra prima

Vedi gli esempi svolti →

C2 / Semafori · 4 pattern

Passaggio del testimone

Ricetta e controlli

Si riconosce da — Risvegliare il gruppo corretto senza far entrare nuovi processi

Ricetta

Il leader non libera mutex: segnala la coda. Ogni risvegliato aggiorna lo stato e passa il testimone; l ultimo riapre mutex.

Chi riapre mutex? · Segnali esatti · Nessun segnale residuo

Vedi gli esempi svolti →

Semaforo per classe

Ricetta e controlli

Si riconosce da — Livelli, priorita, colori o soglie differenti

Ricetta

Usa q[class] e waiting[class]. Un solo semaforo non puo scegliere una guardia logica specifica.

Classe corretta · Contatore decrementato · Scan termina

Vedi gli esempi svolti →

Semafori privati

Ricetta e controlli

Si riconosce da — FIFO/LIFO selettivo, processo n-esimo, scelta esplicita del destinatario

Ricetta

Accoda un semaforo binario privato per chiamante e segnala esattamente il record scelto.

Un solo proprietario · Rimozione atomica · Credito non contato due volte

Vedi gli esempi svolti →

Credito o consegna diretta

Ricetta e controlli

Si riconosce da — Implementare un semaforo custom

Ricetta

Se nessuno aspetta, incrementa value. Se qualcuno aspetta, consegna direttamente la V senza incrementare value.

Invariante nP <= init+nV · No doppio credito · Fairness dichiarata

Vedi gli esempi svolti →

C2 / Message passing · 4 pattern

Inbox locale

Ricetta e controlli

Si riconosce da — Ricezione da mittente specifico sopra arecv(ANY)

Ricetta

Ogni messaggio non richiesto viene conservato in una lista locale, mai scartato.

FIFO per mittente · ANY gestito · Un solo messaggio rimosso

Vedi gli esempi svolti →

Sincronia con ACK

Ricetta e controlli

Si riconosce da — Costruire send sincrona sopra servizio asincrono

Ricetta

DATA contiene sender e sequence; il ricevente invia ACK solo quando consegna quel messaggio.

ACK non ambiguo · Chiamate concorrenti · Tag distinti

Vedi gli esempi svolti →

Marker a se stessi

Ricetta e controlli

Si riconosce da — Ricezione completamente non bloccante senza primitive native

Ricetta

Invia un marker unico a te stesso e drena fino al marker per fotografare i messaggi gia pendenti.

Assunzione FIFO esplicita · Token unico · Marker non esposto all utente

Vedi gli esempi svolti →

Frammentazione

Ricetta e controlli

Si riconosce da — Messaggi arbitrari sopra pacchetti limitati

Ricetta

Aggiungi messageId, indice frammento, totale e mittente; ricomponi per chiave composta.

Messaggi concorrenti · Ultimo frammento · Ordine e duplicati

Vedi gli esempi svolti →

G1 / Parte generale · 4 pattern

Registro degli eventi

Ricetta e controlli

Si riconosce da — Qualsiasi Gantt con CPU e I/O

Ricetta

Mantieni ready queue, code dei device e prossimo evento. Disegna il Gantt come output del registro.

Arrivi simultanei · Fine I/O · Preemption motivata

Vedi gli esempi svolti →

Page replacement

Ricetta e controlli

Si riconosce da — FIFO, LRU, MIN, stack, Belady, costruzione stringhe

Ricetta

Separa contenuto dei frame e metadati della politica. Su hit FIFO non cambia; LRU aggiorna la recenza.

Fault contati · Vittima motivata · Stato dopo ogni riferimento

Vedi gli esempi svolti →

FAT / fsck come grafo

Ricetta e controlli

Si riconosce da — Tabella FAT, free list, directory e incoerenze

Ricetta

Visita catene file e free list; marca proprietario, predecessore, cicli e blocchi irraggiungibili.

Cross-link · Blocco libero e allocato · Orfano o ciclo

Vedi gli esempi svolti →

Banchiere vettoriale

Ricetta e controlli

Si riconosce da — Stato safe, capitale minimo, piu valute

Ricetta

Need=Max-Allocated; scegli Need<=Available componente per componente e restituisci Allocated.

Sequenza completa · Unsafe non equivale a deadlock · Confronti vettoriali

Vedi gli esempi svolti →

2Applica il template

C1 — Monitor

Semaforo Binario con Monitor

Codice
monitor monobinario {
  int value;
  int blockedCount = 0;
  condition block;

  monobinario(int v) { value = v; }

  monoP() {
    if (value == 0) {
      ++blockedCount;
      block.wait();
      --blockedCount;   // ⚠️ OBBLIGATORIO dopo il risveglio (pattern waiting++/wait/waiting--)
    } else {
      value = 0;
    }
  }

  monoV() {
    if (value == 0 && blockedCount >= 1)
      block.signal();
    else
      value = 1;
  }
}

Lettori/Scrittori con Monitor

Codice
monitor ReadWrite {
  int readers = 0;
  int waitingWriters = 0;
  bool writing = false;
  condition ok2read, ok2write;

  procedure entry startRead() {
    if (writing || waitingWriters > 0) {
      ok2read.wait();
    }
    readers++;
    ok2read.signal();  // risveglia altri lettori in coda
  }

  procedure entry endRead() {
    readers--;
    if (readers == 0)
      ok2write.signal();
  }

  procedure entry startWrite() {
    waitingWriters++;
    if (readers > 0 || writing)
      ok2write.wait();
    waitingWriters--;
    writing = true;
  }

  procedure entry endWrite() {
    writing = false;
    if (waitingWriters > 0)
      ok2write.signal();
    else
      ok2read.signal();
  }
}

Produttore/Consumatore (Storage a Componenti)

Codice
monitor storage {
  int components[16];
  (condition, int) waiting[16];  // (coda, conteggio)

  procedure entry add(int[16] c) {
    for (int i = 0; i < 16; ++i) {
      components[i] += c[i];
      repeat(waiting[i].second)  // sveglia tutti in attesa
        waiting[i].first.signal();
    }
  }

  procedure entry get(int[16] requirements) {
    for (int i = 0; i < 16; ++i) {
      if (requirements[i] > components[i]) {
        ++waiting[i].second;
        while (requirements[i] > components[i])
          waiting[i].first.wait();
        --waiting[i].second;
      }
      components[i] -= requirements[i];
    }
  }
}

Rendez-vous "at least N"

Codice
Regola

---

monitor alrv {
  int waiting = 0;
  int target = 0;
  condition ok;

  procedure entry at_least(int n) {
    if (n <= 1) return;  // no attesa necessaria
    waiting++;
    if (waiting >= n) {
      target = n;
      repeat(n - 1) ok.signal();
      waiting -= n;
    } else {
      ok.wait();
    }
  }
}

C2 — Semafori

Semaforo Generale da Binari (Fair, FIFO)

Codice
class Semaphore {
  int value;
  int blocked = 0;
  binary_semaphore mutex(1);
  binary_semaphore sem(0);

  Semaphore(int init) { value = init; }

  void P() {
    mutex.P();
    if (value == 0) {
      blocked++;
      mutex.V();
      sem.P();       // si blocca qui
      blocked--;
    }
    value--;
    mutex.V();
  }

  void V() {
    mutex.P();
    value++;
    if (blocked > 0) {
      sem.V();       // sveglia un P in attesa
    } else {
      mutex.V();
    }
  }
}

Semaforo a Priorità LIFO

Codice
class OrderedLifoSemaphore {
  BinarySemaphore mutex(1);
  int initial, nP, nV = 0, 0, 0;
  OrderedStack<BinarySemaphore> s;

  OrderedLifoSemaphore(int init) { initial = init; }

  void PLP(int prio) {
    mutex.P();
    // ⚠️ CORRETTO: initial - (nP+1) + nV < 0  (il +1 era un errore → faceva passare P con risorse già esaurite)
    if (initial - nP - 1 + nV < 0) {
      BinarySemaphore new_sem(0);
      s.push(prio, new_sem);
      mutex.V();
      new_sem.P();
    }
    nP++;
    mutex.V();
  }

  void PLV() {
    mutex.P();
    nV++;
    if (initial - nP + nV >= 0 && !s.empty())
      s.pop().V();   // sveglia priorità max (LIFO)
    else
      mutex.V();
  }
}

Passaggio del Testimone — Template Universale

Codice
Regola

Regola fondamentale: chi avvia la catena **NON rilascia la mutex**. La mutex viene passata di processo in processo insieme al testimone. L'ULTIMO risvegliato (counter == 0) fa finalmente `mutex.V()`.

binary_semaphore mutex(1);
semaphore s(0);
int counter = 0;

// ===== PROCESSO CHE SI BLOCCA =====
void attendi() {
    mutex.P();
    counter++;               // mi registro tra i bloccati
    mutex.V();               // RILASCIO PRIMA di bloccarmi
    s.P();                   // QUI MI BLOCCCO
    // ===== RISVEGLIATO =====
    counter--;
    if (counter > 0)
        s.V();               // PASSO IL TESTIMONE al prossimo
    else
        mutex.V();           // ULTIMO: RILASCIO LA MUTEX
}

// ===== PROCESSO CHE SBLOCCA TUTTI =====
void sblocca() {
    mutex.P();
    // ... operazioni sui dati condivisi ...
    s.V();                   // sveglia il PRIMO
    // ⚠️ NON fare mutex.V()! La rilascerà l'ultimo risvegliato
}

wait4 — Blocchi di 4 (applicazione del template)

Codice
binary_semaphore mutex(1);
semaphore ok2go(0);
int n = 0;

void wait4() {
    mutex.P();
    n++;
    if (n >= 4) {
        n--;                 // io NON sono tra i bloccati
        ok2go.V();           // sveglia il PRIMO. NON rilascio mutex!
    } else {
        mutex.V();           // rilascio prima di bloccarmi
        ok2go.P();           // mi blocco
        n--;                 // RISVEGLIATO
        if (n > 0)
            ok2go.V();       // testimone al prossimo
        else
            mutex.V();       // ultimo: libero mutex
    }
}

sumstop/sumgo — Accumulo e Sblocco (applicazione del template)

Codice
int sum = 0;
semaphore s(0);
binary_semaphore mutex(1);

void sumstop(int v) {
    mutex.P();
    sum += v;
    mutex.V();               // rilascio PRIMA di bloccarmi
    s.P();                   // BLOCCATO
    // RISVEGLIATO:
    sum -= v;                // tolgo il MIO valore dalla somma
    if (sum > 0)
        s.V();               // testimone al prossimo
    else
        mutex.V();           // ultimo: libero mutex
}

int sumgo() {
    mutex.P();
    int tot = sum;           // catturo la somma
    s.V();                   // sveglia il PRIMO. NON rilascio mutex!
    return tot;
}

Barriera "All Out" (SAU)

Codice
Regola

---

binary_semaphore mutex(1);
semaphore all_out(0);
int in_section = 0, exiting = 0;

void SAU_enter() {
  mutex.P();
  in_section++;
  mutex.V();
}

void SAU_exit() {
  mutex.P();
  if (++exiting == in_section) {
    repeat(in_section - 1) all_out.V();  // sveglia tutti
    in_section = 0;
    exiting = 0;
    mutex.V();
  } else {
    mutex.V();
    all_out.P();    // aspetta gli altri
  }
}

C2 — Message Passing

Asincrono → Sincrono (con ACK)

Codice
void ssend(msg_t msg, pid_t dest) {
  asend((getpid(), msg), dest);
  (_, ack) = arecv(dest);   // aspetta ACK
}

msg_t srecv(pid_t sender) {
  (pid, msg) = arecv(sender);
  asend(ACK, pid);
  return msg;
}

Bloccante → Non-Bloccante (Dummy Messages)

Codice
bool skip = false;

T | None nbreceive(pid_t p) {
  if (!skip)
    asend((get_pid(), null), get_pid());  // dummy per sbloccare
  (pid, data) = areceive(p || get_pid());
  if (pid == get_pid() && data == null) {
    skip = false;
    return None;
  }
  skip = true;
  return data;
}

pssend/psreceive (message passing affidabile)

Codice
void pssend(T data, pid_t p) {
  asend((get_pid(), data), p);
  (pid_t, T) response;
  while ((response = areceive(p)) && response.second != ACK)
    asend(response, get_pid());  // reindirizza messaggi non-ACK
}

T | None psreceive(pid_t p) {
  res = nbreceive(p);
  if (res != None) {
    asend(ACK, res.first);
    return res.second;
  }
  return None;
}

mulsend — invio N copie

Codice
void mulsend(pid_t dest, T msg, int times) {
  for (int i = 0; i < times; ++i) {
    asend(dest, (msg, get_pid()));
    arecv(dest);  // aspetta ACK per ogni copia
  }
}

T multrecv(pid_t sender) {
  (msg, snd) = arecv(sender || ANY);
  asend(snd, ACK);
  return msg;
}

chained_send — invio a catena

Codice
Regola

---

void chained_send(T msg, list<pid_t> dests) {
  ssyncsend(msg, dests[0]);           // aspetta primo
  for (int i = 1; i < dests.size(); i++)
    ssyncsend(dests[i-1], dests[i]);  // ogni destinatario inoltra
}

T chained_recv(void) {
  msg = ssyncrecv(ANY);
  return msg;
}

G1 — Scheduling

Template SMP Biprocessore

Codice
Regola

**Dati input tipici:** ``` P1: cpu 4ms, I/O 4ms, cpu 2ms P2: cpu 2ms, I/O 4ms, cpu 5ms P3: cpu 5ms, I/O 3ms, cpu 3ms P4: cpu 10ms, I/O 1ms I/O: 1 unità, FIFO Priorità: P1 > P2 > P3 > P4 ``` **Metodo:** 1. Tracciare l'asse del tempo, due colonne CPU 2. All'inizio: processi ordinati per priorità sulle CPU libere 3. Quando un processo va in I/O: libera la CPU → schedulare il prossimo ready 4. Quando I/O completa: il processo torna ready → preemption se ha priorità > running 5. I/O è bloccante: il processo non può continuare finché I/O non completa 6. Context switch cost = 0 (salvo indicazione contraria)

Template Round-Robin Multilivello

Codice
Regola

``` Livello ALTO (FIFO): processi periodici H, K (ogni 6ms, 1ms CPU) Livello BASSO (RR, q=3ms): P e Q (normali con I/O) Regola: i processi ad alta priorità prevalgono SEMPRE ```

ED (Earliest Deadline) — Test di Schedulabilità

Codice
Regola

Per processi periodici con solo CPU: ``` Test di Liu & Layland: U = Σ(Ci/Ti) ≤ 1 Ci = tempo CPU per istanza Ti = periodo Se U > 1 → NON schedulabile Se U ≤ 1 → DA VERIFICARE costruendo lo schedule ``` ---

3Verifica prima di consegnare

Prima di scrivere C1/C2

Semafori

Monitor

Message passing

G1 scheduling

Ultimi dieci minuti

Ordine consigliato allo scritto

1Leggi tutto e riconosci i pattern.
2Metti al sicuro C1, la parte più stabile.
3Avvia G1 o la parte generale più lineare.
4Affronta C2 con invariante e testimone espliciti.
5Lascia il 10-15% del tempo alla verifica.