Spiegazione sulla implementazione dei semafori e correzioni su alcuni
authorSimone Piccardi <piccardi@gnulinux.it>
Fri, 25 Oct 2002 18:19:56 +0000 (18:19 +0000)
committerSimone Piccardi <piccardi@gnulinux.it>
Fri, 25 Oct 2002 18:19:56 +0000 (18:19 +0000)
titoli di sezione

img/semtruct.dia
ipc.tex
network.tex

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.
 
+
 \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},
-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}.
@@ -1968,6 +1971,7 @@ alterare il semaforo), per quanto riguarda gli altri campi invece:
   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
@@ -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
-  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
@@ -2000,22 +2001,16 @@ struct sem {
   \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
@@ -2043,6 +2038,14 @@ direttamente nel file \file{/proc/sys/kernel/sem}.
   \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 è:
@@ -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).
 
-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}
index 6f6148e4fd7d4896baf23f1869528c0ab117c609..eda82482741918e9aa3c7c0af62dde2ee1c5469f 100644 (file)
@@ -390,7 +390,7 @@ Maggiori dettagli riguardo a caratteristiche, notazioni e funzionamento del
 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 è
@@ -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.
 
-\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