Spiegazione sulla implementazione dei semafori e correzioni su alcuni

titoli di sezione

diff --git a/img/semtruct.dia b/img/semtruct.dia
index 0b7703416d1b1faffb709cb47ac273518e6af5f5..0744183d1a366cb2d7b2b3ddc1b6782e41b7f429 100644 (file)
Binary files a/img/semtruct.dia and b/img/semtruct.dia differ

diff --git a/ipc.tex b/ipc.tex
index a17bf4a0a5567930903cb7409d8f25f37359d737..da8d85a09c1e7eff365c4d02aa305fef2da2ed53 100644 (file)
--- a/ipc.tex
+++ b/ipc.tex
@@ -1933,6 +1933,7 @@ del sistema. Come vedremo esistono delle modalit
 diventa necessario indicare esplicitamente che si vuole il ripristino del
 semaforo all'uscita del processo.
 
 diventa necessario indicare esplicitamente che si vuole il ripristino del
 semaforo all'uscita del processo.
 

+

 \begin{figure}[!htb]
   \footnotesize \centering
   \begin{minipage}[c]{15cm}
 \begin{figure}[!htb]
   \footnotesize \centering
   \begin{minipage}[c]{15cm}


@@ -1953,12 +1954,14 @@ struct semid_ds
 \end{figure}
 
 A ciascun insieme di semafori è associata una struttura \var{semid\_ds},
 \end{figure}
 
 A ciascun insieme di semafori è associata una struttura \var{semid\_ds},

-riportata in \figref{fig:ipc_semid_ds}. Come nel caso delle code di messaggi
-quando si crea un nuovo insieme di semafori con \func{semget} questa struttura
-viene inizializzata, in particolare il campo \var{sem\_perm} viene
-inizializzato come illustrato in \secref{sec:ipc_sysv_access_control} (si
-ricordi che in questo caso il permesso di scrittura è in realtà permesso di
-alterare il semaforo), per quanto riguarda gli altri campi invece:
+riportata in \figref{fig:ipc_semid_ds}.\footnote{non si sono riportati i campi
+  ad uso interno del kernel, che vedremo in \figref{fig:ipc_sem_schema}, che
+  dipendono dall'implementazione.} Come nel caso delle code di messaggi quando
+si crea un nuovo insieme di semafori con \func{semget} questa struttura viene
+inizializzata, in particolare il campo \var{sem\_perm} viene inizializzato
+come illustrato in \secref{sec:ipc_sysv_access_control} (si ricordi che in
+questo caso il permesso di scrittura è in realtà permesso di alterare il
+semaforo), per quanto riguarda gli altri campi invece:

 \begin{itemize*}
 \item il campo \var{sem\_nsems}, che esprime il numero di semafori
   nell'insieme, viene inizializzato al valore di \param{nsems}.
 \begin{itemize*}
 \item il campo \var{sem\_nsems}, che esprime il numero di semafori
   nell'insieme, viene inizializzato al valore di \param{nsems}.


@@ -1968,6 +1971,7 @@ alterare il semaforo), per quanto riguarda gli altri campi invece:
   effettuata, viene inizializzato a zero.
 \end{itemize*}
 
   effettuata, viene inizializzato a zero.
 \end{itemize*}
 

+

 Ciascun semaforo dell'insieme è realizzato come una struttura di tipo
 \var{sem} che ne contiene i dati essenziali, la sua definizione\footnote{si è
   riportata la definizione originaria del kernel 1.0, che contiene la prima
 Ciascun semaforo dell'insieme è realizzato come una struttura di tipo
 \var{sem} che ne contiene i dati essenziali, la sua definizione\footnote{si è
   riportata la definizione originaria del kernel 1.0, che contiene la prima


@@ -1975,13 +1979,10 @@ Ciascun semaforo dell'insieme 
   ridotta ai soli due primi membri, e gli altri vengono calcolati
   dinamicamente. La si è utilizzata a scopo di esempio, perché indica tutti i
   valori associati ad un semaforo, restituiti dalle funzioni di controllo, e
   ridotta ai soli due primi membri, e gli altri vengono calcolati
   dinamicamente. La si è utilizzata a scopo di esempio, perché indica tutti i
   valori associati ad un semaforo, restituiti dalle funzioni di controllo, e

-  citati dalla pagine di manuale.} è riportata in \figref{fig:ipc_sem}. Di
-norma questa struttura non è accessibile in user space, ma lo sono, in maniera
-indiretta, tramite l'uso delle funzioni di controllo, i valori in essa
-specificati, che indicano rispettivamente: il valore del semaforo, il
-\acr{pid} dell'ultimo processo che ha eseguito una operazione, il numero di
-processi in attesa che esso venga incrementato ed il numero di processi in
-attesa che esso si annulli.
+  citati dalle pagine di manuale.} è riportata in \figref{fig:ipc_sem}. Questa
+struttura, come le altre, non è accessibile in user space, ma i valori in essa
+specificati possono essere letti in maniera indiretta, attraverso l'uso delle
+funzioni di controllo. 

 
 \begin{figure}[!htb]
   \footnotesize \centering
 
 \begin{figure}[!htb]
   \footnotesize \centering


@@ -2000,22 +2001,16 @@ struct sem {
   \label{fig:ipc_sem}
 \end{figure}
 
   \label{fig:ipc_sem}
 \end{figure}
 

-L'architettura dell'implementazione dei semafori è riportata in
-\figref{fig:ipc_sem_schema}.  Si è presa come riferimento l'architettura
-usata fino al kernel 2.2.x (ed illustrata anche in \cite{tlk}) in quanto), che
-viene mantenuta per compatibilità anche nel 2.4.x.
-
-\begin{figure}[htb]
-  \centering \includegraphics[width=15cm]{img/semtruct}
-  \caption{Schema della struttura di un insieme di semafori.}
-  \label{fig:ipc_sem_schema}
-\end{figure}
-
-Come per le code di messaggi anche per gli insiemi di semafori esistono una
-serie di limiti, i cui valori sono associati ad altrettante costanti, che si
-sono riportate in \tabref{tab:ipc_sem_limits}. Alcuni di questi limiti sono al
-solito accessibili e modificabili attraverso \func{sysctl} o scrivendo
-direttamente nel file \file{/proc/sys/kernel/sem}.
+I dati mentenuti nella struttura, ed elencati in \figref{fig:ipc_sem},
+indicano rispettivamente: 
+\begin{description*}
+\item[\var{semval}] il valore numerico del semaforo.
+\item[\var{sempid}] il \acr{pid} dell'ultimo processo che ha eseguito una
+  operazione sul semaforo
+\item[\var{semncnt}] il numero di processi in attesa che esso venga
+  incrementato.
+\item[\var{semzcnt}] il numero di processi in attesa che esso si annulli.
+\end{description*}

 
 \begin{table}[htb]
   \footnotesize
 
 \begin{table}[htb]
   \footnotesize


@@ -2043,6 +2038,14 @@ direttamente nel file \file{/proc/sys/kernel/sem}.
   \label{tab:ipc_sem_limits}
 \end{table}
 
   \label{tab:ipc_sem_limits}
 \end{table}
 

+
+
+Come per le code di messaggi anche per gli insiemi di semafori esistono una
+serie di limiti, i cui valori sono associati ad altrettante costanti, che si
+sono riportate in \tabref{tab:ipc_sem_limits}. Alcuni di questi limiti sono al
+solito accessibili e modificabili attraverso \func{sysctl} o scrivendo
+direttamente nel file \file{/proc/sys/kernel/sem}.
+

 La funzione che permette di effettuare le varie operazioni di controllo sui
 semafori (fra le quali, come accennato, è impropriamente compresa anche la
 loro inizializzazione) è \func{semctl}; il suo prototipo è:
 La funzione che permette di effettuare le varie operazioni di controllo sui
 semafori (fra le quali, come accennato, è impropriamente compresa anche la
 loro inizializzazione) è \func{semctl}; il suo prototipo è:


@@ -2342,16 +2345,71 @@ strutture non vengono ereditate attraverso una \func{fork} (altrimenti si
 avrebbe un doppio ripristino), mentre passano inalterate nell'esecuzione di
 una \func{exec} (altrimenti non si avrebbe ripristino).
 
 avrebbe un doppio ripristino), mentre passano inalterate nell'esecuzione di
 una \func{exec} (altrimenti non si avrebbe ripristino).
 

-Resta comunque insoluto il problema di fondo di questo meccanismo, che non si
-adatta al concetto di operazioni atomiche su un semaforo. Infatti siccome le
-richieste di ripristino si accumulano attraverso diverse chiamate a
-\func{semop}, si pone il problema di cosa fare all'uscita del processo quando
-viene eseguito il ripristino.  Il punto è se si deve porre il processo in
-stato di \textit{sleep} se non si può accedere al semaforo o andare avanti
-come se fosse stato impostato \macro{IPC\_NOWAIT}. La scelta del kernel è
-quella di effettuare le operazioni che non prevedono un blocco del processo ed
-ignorare silenziosamente le altre.  Questo comporta che un comportamento senza
-problemi può essere garantito solo per i semafori privati.
+Tutto questo però ha un problema di fondo. Per capire di cosa si tratta
+occorre fare riferimento all'implementazione usata in Linux, che è riportata
+in maniera semplificata nello schema di \figref{fig:ipc_sem_schema}.  Si è
+presa come riferimento l'architettura usata fino al kernel 2.2.x che è più
+semplice (ed illustrata in dettaglio in \cite{tlk}); nel kernel 2.4.x la
+struttura del System V IPC è stata modificata, ma le definizioni relative a
+queste strutture restano per compatibilità.\footnote{in particolare con le
+  vecchie versioni delle librerie del C, come le libc5.}
+
+\begin{figure}[htb]
+  \centering \includegraphics[width=15cm]{img/semtruct}
+  \caption{Schema della struttura di un insieme di semafori.}
+  \label{fig:ipc_sem_schema}
+\end{figure}
+
+Alla creazione di un nuovo insieme viene allocata una nuova strutture
+\var{semid\_ds} ed il relativo vettore di strutture \var{sem}. Quando si
+richiede una operazione viene anzitutto verificato che tutte le operazioni
+possono avere successo; se una di esse comporta il blocco del processo il
+kernel creaa una struttura \var{sem\_queue} che viene aggiunta in fondo alla
+coda di attesa associata a ciascun insieme di semafori\footnote{che viene
+  referenziata tramite i campi \var{sem\_pending} e \var{sem\_pending\_last}
+  di \var{semid\_ds}.}. Nella struttura viene memorizzato il riferimento alle
+operazioni richieste (nel campo \var{sops}, che è un puntatore ad una
+struttura \var{sembuf}) e al processo corrente (nel campo \var{sleeper}) poi
+quest'ultimo viene messo stato di attesa e viene invocato lo scheduler per
+passare all'esecuzione di un altro processo.
+
+Se invece tutte le operazioni possono avere successo queste vengono eseguite
+immediatamente, dopo di che il kernel esegue una scansione della coda di
+attesa (a partire da \var{sem\_pending}) per verificare se qualcuna delle
+operazioni sospese in precedenza può essere eseguita, nel qual caso la
+struttura \var{sem\_queue} viene rimossa e lo stato del processo associato
+all'operazione (\var{sleeper}) viene riportato a \textit{running}; il tutto
+viene ripetuto fin quando non ci sono più operazioni eseguibili o si è
+svuotata la coda.
+
+Per gestire il meccanismo del ripristino tutte le volte che per un'operazione
+si è specificato il flag \macro{SEM\_UNDO} viene mantenuta per ciascun insieme
+di semafori una apposita struttura \var{sem\_undo} che contiene (nel vettore
+puntato dal campo \var{semadj}) un valore di aggiustamento per ogni semaforo
+cui viene sommato l'opposto del valore usato per l'operazione. 
+
+Queste strutture sono mantenute in due liste,\footnote{rispettivamente
+  attraverso i due campi \var{id\_next} e \var{proc\_next}.} una associata
+all'insieme di cui fa parte il semaforo, che viene usata per invalidare le
+strutture se questo viene cancellato o per azzerarle se si è eseguita una
+operazione con \func{semctl}; l'altra associata al processo che ha eseguito
+l'operazione;\footnote{attraverso il campo \var{semundo} di
+  \var{task\_struct}, come mostrato in \ref{fig:ipc_sem_schema}.} quando un
+processo termina, la lista ad esso associata viene scandita e le operazioni
+applicate al semaforo.
+
+Siccome le richieste di ripristino si accumulano attraverso diverse chiamate a
+\func{semop} per semafori diversi, si pone il problema di come viene eseguito
+il ripristino all'uscita del processo, in particolare se questo può essere
+fatto atomicamente. Il punto è cosa succede quando una delle operazioni
+previste per il ripristino non può essere eseguita immediatamente perché ad
+esempio il semaforo è occupato; in tal caso infatti, se si pone il processo in
+stato di \textit{sleep} aspettando la disponibilità del semaforo (come faceva
+l'implementazione originaria) si perde l'atomicità dell'operazione. La scelta
+fatta dal kernel è pertanto quella di effettuare subito le operazioni che non
+prevedono un blocco del processo e di ignorare silenziosamente le altre;
+questo però comporta il fatto che il ripristino non è comunque garantito in
+tutte le occasioni.

 
 
 \subsection{Memoria condivisa}
 
 
 \subsection{Memoria condivisa}

diff --git a/network.tex b/network.tex
index 6f6148e4fd7d4896baf23f1869528c0ab117c609..eda82482741918e9aa3c7c0af62dde2ee1c5469f 100644 (file)
--- a/network.tex
+++ b/network.tex
@@ -390,7 +390,7 @@ Maggiori dettagli riguardo a caratteristiche, notazioni e funzionamento del
 protocollo IP sono forniti nell'appendice \capref{cha:ip_protocol}.
 
  
 protocollo IP sono forniti nell'appendice \capref{cha:ip_protocol}.
 
  

-\subsection{UDP: User Datagram Protocol)}
+\subsection{User Datagram Protocol (UDP)}

 \label{sec:net_udp}
 
 UDP è un protocollo di trasporto molto semplice, la sua descrizione completa è
 \label{sec:net_udp}
 
 UDP è un protocollo di trasporto molto semplice, la sua descrizione completa è


@@ -435,7 +435,7 @@ bene per le applicazioni in cui la connessione non 
 costituirebbe solo un peso di prestazioni mentre una perdita di pacchetti può
 essere tollerata, ad esempio quelle che usano il multicasting.
 
 costituirebbe solo un peso di prestazioni mentre una perdita di pacchetti può
 essere tollerata, ad esempio quelle che usano il multicasting.
 

-\subsection{TCP: Transport Control Protocol)}
+\subsection{Transport Control Protocol (TCP)}

 \label{sec:net_tcp}
 
 Il TCP è un protocollo molto complesso, definito nell'RFC~739 e completamente
 \label{sec:net_tcp}
 
 Il TCP è un protocollo molto complesso, definito nell'RFC~739 e completamente