Esercizio - Implementare il banchiere e calcolarne la complessità (eserciziario, esercizio 3 e laboratorio 6)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 3; laboratorio 6, task 3 e 4). Implementare l'algoritmo del banchiere e determinarne la complessità computazionale. Nel laboratorio si parte dal programma banker.c (adattato da una fonte pubblica): con gli stati iniziali dati va portato in uno stato sicuro (task 3) e poi esteso ad analizzare due grafi di allocazione (task 4). Teoria: Deadlock - condizioni, prevenzione, evitamento e rilevamentoUn deadlock (stallo) è una situazione in cui un insieme di processi attende all'infinito risorse possedute da altri processi dello stesso insieme; può verificarsi solo se valgono insieme quattro condizioni (mutua esclusione, hold and wait, assenza di prelazione, attesa circolare); il grafo di allocazione delle risorse (archi di richiesta P->R e di assegnazione R->P) senza cicli esclude lo stallo, con un ciclo lo implica se ogni risorsa ha una sola istanza, e lo rende solo possibile se ha più istanze; si può prevenire (negare una delle quattro condizioni, per esempio ordinare le risorse per negare l'attesa circolare), evitare (stato sicuro: esiste una sequenza sicura; algoritmo del grafo con archi di rivendicazione per istanza singola, algoritmo del banchiere con Available, Max, Allocation, Need = Max - Allocation e complessità O(m n^2) per istanze multiple), rilevare e ripristinare (grafo wait-for per istanza singola, algoritmo di rilevamento per istanze multiple; terminazione dei processi o prelazione delle risorse con scelta della vittima e rollback), oppure ignorare.Deadlock - condizioni, prevenzione, evitamento e rilevamento →.

Il programma del laboratorio

banker.c ha tre processi e tre risorse:

con avail = {0, 0, 0}. Calcola need = max - alloc e poi ripete un ciclo "scorri tutti i processi non finiti, se need[i] <= avail aggiungi alloc[i] ad avail e segna finish[i]" finché in un giro nessun processo finisce. Stampa SAFE sequence e la sequenza se tutti finiscono, altrimenti UNSAFE system.

Esito sul dato iniziale. $Need$: $P_0 = (1,0,0)$, $P_1 = (0,0,1)$, $P_2 = (0,1,0)$. Con avail $= (0,0,0)$ nessuno ha $Need \le 0$ (ognuno vuole almeno un'istanza): UNSAFE.

Task 3. Si modifica lo stato iniziale. La soluzione del corso (banker_new.c) cambia solo le prime due righe di alloc: $P_0 = (1,1,0)$ e $P_1 = (0,1,0)$. Controllo: ora $Need_0 = (0,0,0)$, $Need_1 = (1,0,1)$, $Need_2 = (0,1,0)$. Con avail $= (0,0,0)$: $P_0$ ha bisogno di nulla, finisce e restituisce $(1,1,0)$; ora $P_1$ vuole $(1,0,1)$ e $R_3$ manca; ma $P_2$ ($(0,1,0) \le (1,1,0)$) finisce: avail $= (1,1,1)$; infine $P_1$ ($(1,0,1) \le (1,1,1)$). Stato SAFE con la sequenza $P_0 \to P_2 \to P_1$.

Task 4: due grafi (nello stesso formato, avail ricavato da quanto non è assegnato).

• Grafo A ($R_1$ e $R_2$ con 2 istanze ciascuna; $R_1$ assegnata a $T_2$ e $T_3$; $R_2$ assegnata a $T_1$ e $T_4$; richieste $T_1 \to R_1$ e $T_3 \to R_2$). Allocation (colonne $R_1, R_2$): $T_1 = (0,1)$, $T_2 = (1,0)$, $T_3 = (1,0)$, $T_4 = (0,1)$; Max $=$ Allocation $+$ richieste: $T_1 = (1,1)$, $T_2 = (1,0)$, $T_3 = (1,1)$, $T_4 = (0,1)$; avail $= (0,0)$. $T_2$ ($Need = 0$) finisce: avail $(1,0)$; $T_1$ ($(1,0)$) finisce: $(1,1)$; $T_3$ ($(0,1)$), poi $T_4$. SAFE, sequenza $T_2, T_1, T_3, T_4$. Il grafo ha un ciclo ($T_1 \to R_1 \to T_3 \to R_2 \to T_1$) ma con più istanze non è deadlock.
• Grafo B (cinque risorse a istanza singola e cinque thread). Dal disegno: $R_1 \to T_2$, $R_2 \to T_1$, $R_4 \to T_3$, $R_5 \to T_4$, $R_3 \to T_5$ (assegnazioni); $T_1 \to R_1$, $T_2 \to R_3$, $T_2 \to R_4$, $T_2 \to R_5$, $T_3 \to R_5$, $T_4 \to R_2$ (richieste). Tutte le risorse sono assegnate: avail $= 0$. Solo $T_5$ ha $Need = 0$ e finisce, liberando $R_3$; nessun altro può proseguire ($T_2$ vuole anche $R_4$ e $R_5$, $T_1$ vuole $R_1$, $T_4$ vuole $R_2$, $T_3$ vuole $R_5$). UNSAFE: c'è il ciclo $T_2 \to R_5 \to T_4 \to R_2 \to T_1 \to R_1 \to T_2$, risorse a istanza singola, quindi è un deadlock vero tra $T_1, T_2, T_4$ (e $T_3$, che attende $R_5$ di $T_4$, è bloccato dietro di loro).

I due stati sono stati verificati con un programma Python che ripete lo stesso algoritmo.

Implementazione completa con le due funzioni

Il programma seguente generalizza banker.c: usa funzioni, accetta le matrici da costanti e include anche l'algoritmo di richiesta (request). È compilato con zig cc -Wall -Wextra -Wpedantic per Linux senza avvisi; non è stato eseguito qui (binari Linux su Windows), ma lo stesso algoritmo in Python dà i risultati attesi.

#include <stdio.h>
#include <string.h>

#define N 5          /* numero di processi */
#define M 3          /* numero di tipi di risorsa */

static int available[M] = {3, 3, 2};
static int max_[N][M] = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
static int alloc[N][M] = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};

static void need_of(int need[N][M])
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            need[i][j] = max_[i][j] - alloc[i][j];
}

/* Algoritmo di sicurezza: ritorna 1 se lo stato e' sicuro e scrive la sequenza in seq[]. */
static int is_safe(const int avail[M], int seq[N])
{
    int need[N][M], work[M], finish[N] = {0}, count = 0;
    need_of(need);
    memcpy(work, avail, sizeof work);

    while (count < N) {                         /* al piu' N giri */
        int found = 0;
        for (int i = 0; i < N; i++) {           /* N processi */
            if (finish[i])
                continue;
            int ok = 1;
            for (int j = 0; j < M; j++)         /* M risorse */
                if (need[i][j] > work[j]) {
                    ok = 0;
                    break;
                }
            if (ok) {
                for (int j = 0; j < M; j++)
                    work[j] += alloc[i][j];     /* il processo termina e restituisce tutto */
                finish[i] = 1;
                seq[count++] = i;
                found = 1;
            }
        }
        if (!found)
            return 0;                           /* nessuno puo' finire: stato non sicuro */
    }
    return 1;
}

/* Algoritmo di richiesta: 1 = concessa, 0 = il processo deve attendere, -1 = errore. */
static int request(int i, const int req[M])
{
    int need[N][M], seq[N];
    need_of(need);
    for (int j = 0; j < M; j++)
        if (req[j] > need[i][j])
            return -1;                          /* supera il massimo dichiarato */
    for (int j = 0; j < M; j++)
        if (req[j] > available[j])
            return 0;                           /* risorse non disponibili */

    int new_avail[M];                           /* simula l'assegnazione */
    for (int j = 0; j < M; j++) {
        new_avail[j] = available[j] - req[j];
        alloc[i][j] += req[j];
    }
    int safe = is_safe(new_avail, seq);
    if (safe) {
        memcpy(available, new_avail, sizeof available);   /* conferma */
        return 1;
    }
    for (int j = 0; j < M; j++)                 /* annulla la simulazione */
        alloc[i][j] -= req[j];
    return 0;
}

int main(void)
{
    int seq[N];
    if (is_safe(available, seq)) {
        printf("stato SICURO, sequenza:");
        for (int i = 0; i < N; i++)
            printf(" P%d", seq[i]);
        printf("\n");
    } else {
        printf("stato NON sicuro\n");
    }

    int r1[M] = {1, 0, 2};
    int r2[M] = {3, 3, 0};
    int r3[M] = {0, 2, 0};
    printf("P1 chiede (1,0,2): %d\n", request(1, r1));   /* atteso 1 */
    printf("P4 chiede (3,3,0): %d\n", request(4, r2));   /* atteso 0: non disponibile */
    printf("P0 chiede (0,2,0): %d\n", request(0, r3));   /* atteso 0: stato non sicuro */
    return 0;
}

Il main ripete l'esempio delle slide: totali $A=10$, $B=5$, $C=7$ con cinque thread. Risultati attesi (calcolati a mano e con Python): stato iniziale sicuro con sequenza $P_1, P_3, P_4, P_0, P_2$ (la scansione per indice ne trova una, diversa da quella delle slide $P_1, P_3, P_4, P_2, P_0$, che è pure valida); la richiesta $(1,0,2)$ di $P_1$ è concessa; la richiesta $(3,3,0)$ di $P_4$ deve attendere perché dopo la prima available $= (2,3,0)$; la richiesta $(0,2,0)$ di $P_0$ è rifiutata perché lo stato sarebbe non sicuro.

Complessità

Nell'algoritmo di sicurezza:

• ogni "giro" scorre i $N$ processi; per ciascuno non finito controlla fino a $M$ componenti: $O(N \cdot M)$ per giro;
• ogni giro ha successo (almeno un processo finisce) oppure l'algoritmo si ferma: ci sono al più $N$ giri;
• in totale $O(N \cdot N \cdot M) = O(M \cdot N^2)$.

L'algoritmo di richiesta aggiunge $O(M)$ per i controlli e una chiamata alla sicurezza: il costo resta $O(M \cdot N^2)$. È un costo che si paga a ogni richiesta, perciò in pratica pochi sistemi lo usano (anche perché richiede di conoscere in anticipo i massimi). Una versione che, dopo aver finito un processo, non riparte dall'inizio ma tiene una lista dei processi pronti può ridurre il termine a $O(M \cdot N)$ per giro, ma il caso peggiore resta quadratico in $N$ a meno di strutture dati più elaborate.

Domande d'esame

Qual è la complessità del controllo di sicurezza del banchiere con $n$ processi e $m$ risorse? Traccia. $O(m \cdot n^2)$: al più $n$ giri, ognuno scorre $n$ processi e confronta $m$ componenti.