Laboratorio di Sistemi Operativi PDF

laboratorio di sistemi operativi semafori Daniele Radicioni argomenti del laboratorio UNIX introduzione a UNIX; integrazione C: operatori bitwise, precedenze, preprocessore, pacchettizzazione del codice, compilazione condizionale e utility make; controllo dei processi; se...

laboratorio di sistemi operativi semafori Daniele Radicioni argomenti del laboratorio UNIX introduzione a UNIX; integrazione C: operatori bitwise, precedenze, preprocessore, pacchettizzazione del codice, compilazione condizionale e utility make; controllo dei processi; segnali; pipe e fifo; code di messaggi; semafori; memoria condivisa; introduzione alla programmazione bash. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 2 credits il materiale di queste lezioni è tratto: - dai lucidi del Prof. Gunetti degli anni scorsi; - Michael Kerrisk, The Linux Programming interface - a Linux and UNIX® System Programming Handbook, No Starch Press, San Francisco, CA, 2010; - W. Richard Stevens (Author), Stephen A. Rago, Advanced Programming in the UNIX® Environment (2nd Edition), Addison- Wesley, 2005; Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 3 introduzione: i semafori a che servono diversamente dagli altri strumenti per IPC visti finora, i semafori non servono a trasferire dati fra processi. - sono utilizzati per permettere ai processi di sincronizzare le proprie azioni: per esempio permettono di sincronizzare l'accesso a un blocco di memoria condivisa, per impedire a un processo di accedere alla memoria condivisa mentre un altro processo la sta aggiornando Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 5 cos'è un semaforo Un semaforo è un intero mantenuto dal kernel il cui valore è sempre ≥ 0. - È possibile effettuare varie operazioni su un semaforo, fra cui: 1.impostare il semaforo ad un certo valore; 2.aggiungere un numero al valore corrente del semaforo; 3.sottrarre un numero dal valore corrente del semaforo; e 4.attendere che il valore del semaforo sia 0. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 6 cos'è un semaforo Le ultime due operazioni (sottrarre un numero e attendere lo 0) possono causare il blocco del chiamante. - Nel decrementare il valore del semaforo il kernel blocca qualsiasi tentativo di ridurlo sotto 0. - Analogamente, l'attesa dello 0 blocca il chiamante se il semaforo non è attualmente a 0. In entrambi i casi, il chiamante resta bloccato finché qualche altro processo modifica il semaforo a un valore che consente all'operazione di procedere; a questo punto il kernel risveglia il processo bloccato. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 7  the use of a semaphore to synchronize the actions of two processes that alternate move the semaphore value between 0 and 1. Process A Process B Create semaphore Michael Kerrisk, The Linux Programming interface - a Linux and UNIX® System Programming Handbook, No Starch Press, San Initialize semaphore to 0 Subtract 1 from semaphore blocks Add 1 to semaphore resumes Time Francisco, CA, 2010. Subtract 1 from semaphore blocks Add 1 to semaphore resumes Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 8 Figure 47-1: Using a semaphore to synchronize two processes In terms of controlling the actions of a process, a semaphore has no meaning and of itself. Its meaning is determined only by the associations given to it by t utilizzo dei semafori I passi per utilizzare i semafori sono: - Creazione o apertura di un set di semafori utilizzando la semget(). - Inizializzazione dei semafori presenti nel set, usando l'operazione SETVAL o SETALL della semctl(). - Esecuzione delle operazioni sui valori del semaforo, utilizzando semop(). I processi che utilizzano il semaforo tipicamente usano tali operazioni per indicare l'acquisizione e il rilascio di una risorsa condivisa. - Quando tutti i processi hanno terminato di usare il set di semafori, rimozione del set per mezzo dell'operazione IPC_RMID della semctl(). Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 9 set di semafori I semafori di System V sono resi complessi dal fatto di essere allocati in gruppi detti set di semafori. - Il numero di semafori in un set è specificato al momento della creazione del set, per mezzo della system call semget(). - Molto spesso si utilizza un solo semaforo alla volta, ma la system call semop() consente di eseguire atomicamente un gruppo di operazioni su vari semafori in uno stesso set. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 10 00 int main(int argc, char *argv[]) { 01 int semid; 02 if (argc == 2) { // ----------- creo e inizializzo un sem -------- 03 union semun arg; 04 $./handle_sem 0 semid = semget(IPC_PRIVATE, 1, S_IRUSR | S_IWUSR); 05 if (semid creato == -1) ddErrExit("semid"); e inizializzato semaforo con ID = 371130369 06 arg.val = atoi(argv); $./handle_sem 371130369 -2 & 07 if (semctl(semid, 0, SETVAL, arg) == -1) 08 ddErrExit("semctl"); 71130 09 about to semop eatinizializzato printf("creato 2021-11-12__04:59:14. semaforo con ID = %d\n", semid); 10 $}./handle_sem 371130369 else { // -------- +3 eseguo un'operazione sul primo semaforo ----- 11 structabout 71136: sembuftosop; // laat semop struttura che definisce l'operazione 2022-11-12__04:59:47. 12 semid = atoi(argv); 71136: semop completed at 2022-11-12__04:59:47. 13 sop.sem_num = 0; // specifica il primo semaforo nel set 14 71130: semop= atoi(argv); sop.sem_op completed at 2022-11-12__04:59:47. 15 + Done./handle_sem // 371130369 aggiungo, sottraggo -2 0 o attendo 16 $ sop.sem_flg = 0; // per ora NON settiamo flag per effettuare 17 // operazioni speciali 18 printf("%ld: about to semop at %s\n", 19 (long) getpid(), get_curr_time()); 20 if (semop(semid, &sop, 1) == -1) 21 ddErrExit("semop"); 22 printf("%ld: semop completed at %s\n", 23 (long) getpid(), get_curr_time()); 24 } 25 exit(EXIT_SUCCESS);} Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 11 00 int main(int argc, char *argv[]) { 01 int semid; 02 if (argc == 2) { // ----------- creo e inizializzo un sem -------- 03 union semun arg; 04 semid = semget(IPC_PRIVATE, 1, S_IRUSR | S_IWUSR); 05 if (semid == -1) ddErrExit("semid"); 06 arg.val = atoi(argv); 07 if (semctl(semid, 0, SETVAL, arg) == -1) 08 ddErrExit("semctl"); 09 printf("creato e inizializzato semaforo con ID = %d\n", semid); 10 } else { // -------- eseguo un'operazione sul primo semaforo ----- 11 struct sembuf sop; // la struttura che definisce l'operazione 12 semid = atoi(argv); 13 sop.sem_num = 0; // specifica il primo semaforo nel set 14 sop.sem_op = atoi(argv); 15 // aggiungo, sottraggo o attendo 0 16 sop.sem_flg = 0; // per ora NON settiamo flag per effettuare 17 // operazioni speciali 18 printf("%ld: about to semop at %s\n", 19 (long) getpid(), get_curr_time()); 20 if (semop(semid, &sop, 1) == -1) 21 ddErrExit("semop"); 22 printf("%ld: semop completed at %s\n", 23 (long) getpid(), get_curr_time()); 24 } 25 exit(EXIT_SUCCESS);} Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 12  Creating or Opening a Semaphore Set #include #include int semget(key_t key, int nsems, int semflg); Returns semaphore set identifier on success, or -1 on error L'argomento key è una chiave generata specificando un numero casuale, o usando il valore IPC_PRIVATE o una chiave restituita da ftok(). Se stiamo usando semget() per creare un nuovo set di semafori, allora nsems specifica il numero di semafori in quell'insieme, e deve essere maggiore di 0. Se invece stiamo usando la semget() per ottenere l'identificatore di un set esistente, nsems deve essere minore o uguale alla dimensione del set (o si incorrerà nell'errore EINVAL). - NB: non è possibile modificare il numero Daniele Radicioni didisemafori - Laboratorio presenti Sistemi Operativi, in- turno corso A un dato T1 set. 13  hyphen preceding this string indicates the type of this fil pret this string, we break these 9 characters into sets of 3 tively indicate whether read, write, and execute permiss set indicates the permissions for owner, which has read, w sions enabled. The next set indicates the permissions f #include but not write. The final set are t #include which doesnDt have any permissions enabled. The header file defines constants that st_mode int semget(key_t key, int nsems, intofsemflg); the stat structure, in order to check whether are set. (These constants are also defined via the inclusion types the open() system call.) These constants are shown in Returns semaphore set identifier on success, or -1 Table 15-4: Constants on for file errorbits permission Constant Octal value Permission bit L'argomento semflg è una S_ISUID 04000 Set-user-ID Set-group-ID maschera di bit che specifica S_ISGID 02000 S_ISVTX 01000 Sticky i permessi da assegnare a S_IRUSR S_IWUSR 0400 0200 User-read User-write un nuovo set di semafori o S_IXUSR S_IRGRP 0100 040 User-execute Group-read da verificare su un set S_IWGRP 020 Group-write S_IXGRP 010 Group-execute esistente. S_IROTH 04 Other-read S_IWOTH 02 Other-write S_IXOTH 01 Other-execute Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 14 In addition to the constants shown in Table 15-4, three equate to masks for all three permissions for each of the and other: S_IRWXU (0700), S_IRWXG (070), and S_IRWXO (07). The header file in Listing 15-3 declares a function, fi  #include #include int semget(key_t key, int nsems, int semflg); Returns semaphore set identifier on success, or -1 on error Zero o più dei seguenti flag possono essere messi in OR (|) nel semflg per controllare l'operazione semget(): - IPC_CREAT. Se non esiste un set di semafori con la chiave specificata, crea un nuovo set. - IPC_EXCL. Se è stato specificato anche IPC_CREAT, e un set di semafori con la chiave specificata esiste già, restituisci un fallimento, con errore EEXIST. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 15 Semaphore Control Operations #include #include int semctl(int semid, int semnum, int cmd,... ); Returns nonnegative integer on success; returns -1 on error L'argomento semid è l'identificatore del set di semafori sul quale l'operazione viene eseguita. Per le operazioni su un singolo semaforo l'argomento semnum identifica un semaforo all'interno del set. Per le altre operazioni questo argomento è ignorato, e possiamo lasciarlo a 0. L'argomento cmdDaniele specifica l'operazione. Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 16  #include #include int semctl(int semid, int semnum, int cmd,... ); Returns nonnegative integer on success (see text); returns -1 on error union semun { Alcune operazioni richiedono un // value for SETVAL quarto argomento di nome arg. int val; // buffer for IPC_STAT, IPC_SET si tratta di una union che deve essere struct semid_ds* buf; // array for GETALL, SETALL esplicitamente definita nei nostri unsigned short* array; programmi (a meno che non sia già // Linux specific part #if defined(__linux__) presente in , come in // buffer for IPC_INFO struct seminfo* __buf; Mac OS X). #endif }; Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 17 Generic control operations int semctl(int semid, int semnum, int cmd,... ); Le seguenti operazioni (IPC_RMID, IPC_STAT, IPC_SET) sono le stesse applicabili agli altri tipi di oggetti IPC di System V. - IPC_RMID. Rimuove immediatamente il set di semafori e l'associata struttura semid_ds. Qualsiasi processo bloccato in chiamate semop() in attesa su semafori è immediatamente svegliato, e semop() riporta l'errore EIDRM. L'argomento arg non è richiesto. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 18 Generic control operations int semctl(int semid, int semnum, int cmd,... ); - IPC_STAT. Copia la struttura semid_ds associata con il set di semafori nel buffer puntato da arg.buf. - IPC_SET. Aggiorna i membri della struttura semid_ds associata al set di semafori utilizzando i valori nel buffer puntato da arg.buf. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 19 Retrieving and initializing semaphore values int semctl(int semid, int semnum, int cmd,... ); Le seguenti operazioni prelevano o inizializzano il valore (o i valori) di un singolo semaforo o di tutti i semafori del set. La copia del valore di un semaforo richiede permessi in lettura sul semaforo, mentre l'inizializzazione del valore richiede permessi in scrittura. - GETVAL. Come risultato della chiamata, semctl() restituisce il valore del semaforo (numero) semnum nel set di semafori specificato da semid. L'argomento arg non è richiesto. - SETVAL. Il valore del semaforo semnum nel set riferito da semid è inizializzato alDaniele valore arg.val. Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 20  union semun { int val; struct semid_ds* buf; int semctl(int semid, int semnum, unsigned short* array; int cmd,... ); #if defined(__linux__) struct seminfo* __buf; #endif }; Le seguenti operazioni prelevano o inizializzano il valore (i valori) di un singolo semaforo o di tutti i semafori nel set. - GETALL. Preleva i valori di tutti i semafori nel set riferito da semid, copiandoli nell'array puntato da arg.array. Il programmatore deve garantire che l'array sia abbastanza capiente. semnum è ignorato. - SETALL. Inizializza tutti i semafori del set riferito da semid, usando i valori forniti nell'array puntato da arg.array. semnum è ignorato. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 21 Retrieving per-semaphore information Le seguenti operazioni restituiscono (attraverso il valore restituito dalla funzione) informazioni sul semaforo numero semnum del set riferito da semid. Per tutte queste operazioni, è richiesto il permesso in lettura sul set di semafori, e l'argomento arg non è richiesto. - GETPID. Restituisce il PID dell'ultimo processo che ha eseguito una semop() su questo semaforo; questo è riferito come il valore sempid. Se nessun processo ha ancora eseguito una semop() su questo semaforo, restituisce 0. - GETNCNT. Restituisce il numero di processi attualmente in attesa di un incremento del valore del semaforo; questo è riferito come il valore semncnt. - GETZCNT. Restituisce il numero di processi attualmente in attesa che il valore del semaforo divenga 0; questo è riferito come valore semzcnt. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 22  union semun { struct semid_ds { int val; struct semid_ds* buf; struct ipc_perm sem_perm; unsigned short* array; #if defined(__linux__) time_t sem_otime; struct seminfo* __buf; #endif time_t sem_ctime; }; unsigned short sem_nsems; }; Ogni set di semafori ha associata una struttura semid_ds data; I membri della struttura semid_ds sono implicitamente aggiornati da varie system call sul semaforo, e alcuni membri della struttura sem_perm possono essere aggiornati esplicitamente con l'operazione semctl() IPC_SET. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 23  struct semid_ds { struct ipc_perm sem_perm; time_t sem_otime; time_t sem_ctime; unsigned short sem_nsems; }; - sem_perm. Quando il set di semafori è creato, i membri di questa struttura sono inizializzati. I membri uid, gid, e mode possono essere aggiornati con l'operazione IPC_SET. - sem_otime. Questo membro è settato a 0 alla creazione del set di semafori, ed aggiornato all'ora corrente ad ogni semop() che va a buon fine, o quando il valore del semaforo è modificato in seguito a un'operazione SEM_UNDO. - sem_ctime. Questo membro è impostato all'ora corrente al momento della creazione del semaforo, e in seguito a ogni operazione IPC_SET, SETALL, o SETVAL. - sem_nsems. Membro inizializzato al momento della creazione del set di semafori: contiene il numero Daniele di semafori Radicioni - Laboratorio nel di Sistemi set. corso A - turno T1 Operativi, 24 esercizio programma per monitorare lo stato dei semafori: prende in input l'ID, e stampa quando è stato modi cato, l'orario dell'ultima semop(), e poi crea una tabella (utilizzare le opzioni di formattazione per allineare i valori) in cui sono riportati: numero semaforo; valore; SEMPID, SEMNCNT e SEMZCNT. GETNCNT. Return the number of processes currently waiting for the value of this semaphore to increase; this is referred to as the semncnt value. GETZCNT. Return the number of processes currently waiting for the value of this semaphore to become 0; this is referred to as the semzcnt value. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 25 fi problemi di inizializzazione e race condition 00 semid = semget(key, 1, IPC_CREAT | IPC_EXCL | perms); 01 if (semid != -1) { // semaforo creato 02 union semun arg; 03 04 // ------ XXXXXXX 05 06 arg.val = 0; // inizializzazione 07 if (semctl(semid, 0, SETVAL, arg) == -1) 08 ddErrExit("semctl"); 09 } else { // --- non abbiamo creato il sem: esisteva già? 10 if (errno != EEXIST){ // errore inatteso dalla semget() 11 ddErrExit("semget 1"); 12 } else { // errore era EEXIST: semaforo già esistente 13 semid = semget(key, 1, perms); // preleviamone l'ID 14 if (semid == -1) 15 ddErrExit("semget 2"); 16 } 17 } 18 // esecuzione di un'azione sul semaforo 19 sops.sem_op = 1; // aggiunta di 1 20 sops.sem_num = 0; // al semaforo 0 21 sops.sem_flg = 0; // senza specificare opzioni 22 if (semop(semid, sops, 1) == -1) ddErrExit("semop"); Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 27 race condition se due processi eseguono il codice precedente allo stesso tempo, potrebbe verificarsi una sequenza errata se il primo processo viene interrotto al punto marcato nel codice con XXXX. Questa sequenza pone i seguenti problemi. - il processo B esegue una semop() su un semaforo non inizializzato (cioè, che contiene un valore arbitrario!). - la chiamata semctl() nel processo A sovrascrive le modifiche fatte dal processo B. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 28 00 semid = semget(key, 1, IPC_CREAT | IPC_EXCL | perms); 01 if (semid != -1) { // semaforo creato 02 union semun arg; 03 04 // ------ XXXXXXX 05 06 arg.val = 0; // inizializzazione 07 if (semctl(semid, 0, SETVAL, arg) == -1) 08 ddErrExit("semctl"); 09 } else { // --- non abbiamo creato il sem: esisteva già? 10 if (errno != EEXIST){ // errore inatteso dalla semget() 11 ddErrExit("semget 1"); 12 } else { // semaforo già esistente 13 semid = semget(key, 1, perms); // preleviamone l'ID 14 if (semid == -1) 15 ddErrExit("semget 2"); 16 } 17 } 18 // esecuzione di un'azione sul semaforo 19 sops.sem_op = 1; // aggiunta di 1 20 sops.sem_num = 0; // al semaforo 0 21 sops.sem_flg = 0; 22 if (semop(semid, sops, 1) == -1) ddErrExit("semop"); Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 29  case, for example, if a parent creates and initializes the semaphore before creating child processes with which it shares the semaphore. In such cases, it is sufficient for the first process to follow its semget() call by a semctl() SETVAL or SETALL operation. Process A Process B First semget() succeeds Michael Kerrisk, The Linux Programming interface - a Linux and UNIX® System Programming Handbook, No Starch Press, San (because set didn’t exist) time slice time slice expires begins First semget() fails (so this process knows set exists) Second semget() succeeds Francisco, CA, 2010. Executes semop() time slice time slice begins ends semctl() initializes semaphore Key Executes semop() Executing Waiting Daniele Radicioni - Laboratorio di Sistemi Operativi, for CPU on CPUcorso A - turno T1 30 Figure 47-2: Two processes racing to initialize the same semaphore soluzione La soluzione a questo problema è basata su una caratteristica dell'inizializzazione del membro sem_otime della struttura semid_ds associata con il set di semafori. - Al momento della creazione del set di semafori, il membro sem_otime è inizializzato a 0, ed è modificato solo da una successiva chiamata alla semop(). Possiamo quindi eliminare la race condition inserendo del codice per forzare il secondo processo (quello che NON crea il semaforo) ad attendere finché il primo processo ha inizializzato il semaforo ed eseguito la propria semop() che aggiorni il membro sem_otime. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 31 00 semid = semget(key, 1, IPC_CREAT | IPC_EXCL | perms); 01 02 if (semid != -1) { // ---- semaforo creato 03 union semun arg; 04 struct sembuf sop; 05 06 arg.val = 0; // inizializzazione 07 if (semctl(semid, 0, SETVAL, arg) == -1) 08 ddErrExit("semctl 1"); 09 10 13 sop.sem_num = 0; // semaforo numero 0 14 sop.sem_op = 0; // attendi per il valore 0 15 sop.sem_flg = 0; 16 if (semop(semid, &sop, 1) == -1) 17 ddErrExit("semop"); 18 19 } else { // ---- non abbiamo creato il semaforo 20... 21 } Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 32 00 semid = semget(key, 1, IPC_CREAT | IPC_EXCL | perms); 01 02 if (semid != -1) { // ---- semaforo creato 03 union semun arg; 04 struct sembuf sop; 05 06 arg.val = 0; // inizializzazione 07 if (semctl(semid, 0, SETVAL, arg) == -1) 08 ddErrExit("semctl 1"); 09 10 13 sop.sem_num = 0; // semaforo numero 0 14 sop.sem_op = 0; // attendi per il valore 0 15 sop.sem_flg = 0; 16 if (semop(semid, &sop, 1) == -1) 17 ddErrExit("semop"); 18 19 } else { // ---- non abbiamo creato il semaforo 20... 21 } Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 33 00 if (semid != -1) { // ---- semaforo creato 01... 02 } else { // ---- non abbiamo creato il semaforo 03 if (errno != EEXIST) ddErrExit("semget 1"); 04 // il sem era già stato creato 05 const int MAX_TRIES = 10; 06 int j; 07 union semun arg; 08 struct semid_ds ds; 09 semid = semget(key, 1, perms); // preleviamo l'ID 10 if (semid == -1) ddErrExit("semget 2"); 11 // Attesa che un altro processo chiami semop() 12 arg.buf = &ds; 13 for (j = 0; j < MAX_TRIES; ++j) { 14 if (semctl(semid, 0, IPC_STAT, arg) == -1) 15 ddErrExit("semctl 2"); 16 if (ds.sem_otime != 0) // è stata eseguita Semop()? 17 break; // sì, usciamo dal ciclo 18 sleep(1); // diversamente, attendiamo e ritentiamo 19 } 20 if (ds.sem_otime == 0) // siamo usciti ma sem_otime è 0 21 ddErrExit("Existing semaphore not initialized"); 22 } Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 34 00 semid = semget(key, 1, IPC_CREAT | IPC_EXCL | perms); 01 02 if (semid != -1) { // ---- semaforo creato 03 06 } else { // ---- non abbiamo creato il semaforo 07 // il sem era già stato creato 08 // Attesa che un altro processo chiami semop() 09 } 10 // esecuzione di un'azione sul semaforo 11 sops.sem_num = 0; 12 sops.sem_op = (short) atoi(argv); 13 sops.sem_flg = 0; 14 if (semop(semid, sops, 1) == -1) 15 ddErrExit("semop"); Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 35 note questa soluzione al race problem non è richiesta in tutte le applicazioni. - e in alcune varianti di BSD è inefficace, in quanto il momento di esecuzione della semop() non viene registrato dal campo sem_otime… - in generale non ne abbiamo bisogno se un processo è in grado di creare e inizializzare il semaforo prima che qualsiasi altro tenti di utilizzarlo. - è questo il caso, per esempio, in cui un genitore crea e inizializza il semaforo prima di creare i processi figli con cui condivide il semaforo in questi casi, è sufficiente che il genitore subito dopo la semget() esegua un'operazione SETVAL o SETALL con la system call semctl(). Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 36 operazioni sui semafori operazioni sui semafori #include #include int semop(int semid, struct sembuf *sops, unsigned int nsops); Returns 0 on success, or -1 on error La system call semop() esegue una o più operazioni sui semafori nel set identificato da semid. - l'argomento sops è un puntatore a un array che contiene le operazioni da eseguirsi, e - nsops è la dimensione dell'array (che deve contenere almeno un elemento). Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 38 sembuf: semaphore operations struct sembuf { unsigned short sem_num; // numero semaforo short sem_op; // operazione da eseguire short sem_flg; // flags operazione // (IPC_NOWAIT and SEM_UNDO) }; Le operazioni sono eseguite atomicamente e nell'ordine in cui compaiono nell'array. Gli elementi dell'array sops sono strutture con queste caratteristiche: - Il membro sem_num identifica, all'interno del set, il semaforo sul quale si intende effettuare l'operazione. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 39  struct sembuf { sembuf: semaphore unsigned short sem_num; // operazione da eseguire operations short sem_op; short sem_flg; }; Il membro sem_op specifica l'operazione da eseguire: - Se sem_op è maggiore di 0, il valore di sem_op è aggiunto al valore del semaforo. Quindi altri processi in attesa di diminuire il valore del semaforo possono essere svegliati per eseguire le proprie operazioni. Il processo chiamante deve avere diritti di scrittura sul semaforo. - Se sem_op è uguale a 0, il valore del semaforo è testato per vedere se attualmente è uguale a 0. Se sì, l'operazione è completata immediatamente; diversamente, la semop() si blocca finché il valore del semaforo diviene 0. Il chiamante deve avere Daniele permessi Radicioni in scrittura - Laboratorio sul semaforo. di Sistemi Operativi, corso A - turno T1 40  struct sembuf { sembuf: semaphore unsigned short sem_num; // operazione da eseguire operations short sem_op; short sem_flg; }; Se sem_op è minore di 0, decrementa il valore del semaforo del valore specificato da sem_op. - Se il valore corrente del semaforo è maggiore o uguale al valore assoluto specificato da sem_op, l'operazione è completata immediatamente. - Diversamente, semop() si blocca finché il valore del semaforo è stato aumentato tanto da permettere che l'operazione venga eseguita (senza produrre un valore negativo). Il chiamante deve avere diritti di scrittura sul semaforo. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 41 semantica sottostante l'incremento del valore di un semaforo corrisponde a rendere disponibile una risorsa così che altri processi possano utilizzarla; il decremento del valore di semaforo corrisponde a riservare la risorsa per un uso esclusivo da parte di questo processo. - Il tentativo di ridurre il valore di un semaforo può restare bloccato se il valore del semaforo è troppo basso, cioè se qualche altro processo ha già ottenuto l'uso esclusivo per la risorsa in questione. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 42 cosa accade a un processo bloccato Quando una system call semop() si blocca, il processo resta bloccato finché: - un altro processo modifica il valore del semaforo così che la richiesta possa procedere; - un segnale interrompe la system call semop(). In questo caso la semop() fallisce con l'errore EINTR. - un altro processo cancella il semaforo identificato da semid. In questo caso, la semop() fallisce con l'errore EIDRM. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 43  struct sembuf { non-blocking semop() unsigned short sem_num; // operazione da eseguire short sem_op; short sem_flg; }; È possibile prevenire il blocco della semop() nell'esecuzione di un'operazione su un dato semaforo specificando il flag IPC_NOWAIT nel membro sem_flg della struttura sembuf. - In questo caso, invece di restare bloccata, la semop() fallisce con l'errore EAGAIN. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 44 operations on multiple semaphores è possibile eseguire una semop() per compiere operazioni su molteplici semafori in uno stesso set. questo gruppo di operazioni è eseguito atomicamente; cioè, o la semop() esegue tutte le operazioni, o si blocca fino a quando non diventa possibile eseguirle simultaneamente tutte. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 45 operations on multiple semaphores consideriamo un esempio: - l'uso di semop() per eseguire operazioni su tre semafori in un set. - Le operazioni sui semafori 0 e 2 possono non essere in grado di procedere immediatamente, a seconda dei valori correnti dei semafori. - se l'operazione sul semaforo 0 non può essere eseguita immediatamente, allora nessuna delle operazioni richieste viene eseguita, e la semop() pone in attesa il chiamante. - se l'operazione sul semaforo 0 può essere eseguita immediatamente, ma non l'operazione sul semaforo 2, allora se è stato specificato il flag IPC_NOWAIT sul semaforo 2, nessuna delle operazioni è eseguita, e la semop() restituisce immediatamente con l'errore EAGAIN. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 46 struct sembuf sops; sops.sem_num = 0; sops.sem_op = -1; // DECREMENTO di 1 il semaforo 0 sops.sem_flg = 0; sops.sem_num = 1; sops.sem_op = 2; // INCREMENTO di 2 il semaforo 1 sops.sem_flg = 0; sops.sem_num = 2; sops.sem_op = 0; // ATTESA che il semaforo 2 valga 0 sops.sem_flg = IPC_NOWAIT; if (semop(semid, sops, 3) == -1) { if (errno == EAGAIN) printf("Operation would have blocked\n"); else errExit("semop"); // si è verificato qualche altro errore Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 47 gestione di blocchi multipli l'ordine in cui vengono soddisfatte le richieste If multiple processes are blocked trying to decrease the value of a semaphore by the same amount, then it is indeterminate which process will be permitted to perform the operation first when it becomes possible. On the other hand, if processes are blocked trying to decrease a semaphore value by different amounts, then the requests are served in the order in which they become possible. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 49 starvation (by decrease amount) Suppose that a semaphore currently has the value 0, and process A requests to decrease the semaphore’s value by 2, and then process B requests to decrease the value by 1. If a third process then adds 1 to the semaphore, process B would be the first to unblock and perform its operation, even though process A was the first to request an operation against the semaphore. In poorly designed applications, such scenarios can lead to starvation, whereby a process remains blocked forever because the state of the semaphore is never such that the requested operation proceeds. Also in case multiple processes adjust the semaphore in such a way that its value is never more than 1, process A remains blocked forever. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 50 starvation (by multiple sem operations) Starvation can also occur if a process is blocked trying to perform operations on multiple semaphores. Consider the following example, with a pair of semaphores, both of which initially have the value 0: 1. Process A makes a request to subtract 1 from semaphores 0 and 1 (blocks). 2. Process B makes a request to subtract 1 from semaphore 0 (blocks). 3. Process C adds 1 to semaphore 0. At this point, process B unblocks and completes its request, even though it placed its request later than process A. - Again, it is possible to devise scenarios in which process A is starved while other processes adjust and block on the values of the individual semaphores. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 51 Implementing a Binary Semaphores Protocol complessità e semplificazione La API per i semafori di System V semaphores è complessa, - perché il valore dei semafori può essere modificato di quantità arbitrarie, - perché i semafori sono allocati in set di semafori, e le operazioni sono eseguite su set di semafori. Entrambe queste caratteristiche forniscono funzionalità più estese di quelle tipicamente necessarie, quindi è utile implementare protocolli più semplici. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 53 binary semaphores Un protocollo largamente utilizzato è quello dei semafori binari. Un semaforo binario ha due valori: available (libero) e reserved (in uso). Sui semafori binari sono definite due operazioni: - Reserve (wait, o P): Tenta di riservare questo semaforo per uso esclusivo. Se il semaforo è già stato riservato da un altro processo, l'operazione si blocca fino a quando il semaforo è rilasciato. - Release (signal, o V): Libera un semaforo correntemente riservato, così che possa essere riservato da un altro processo. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 54  un modo abituale per rappresentare questi stati è utilizzare il valore 1 per indicare free e il valore 0 per riservato, con le operazioni reserve e release: l'una decrementa di uno il valore del semaforo, l'altra lo incrementa di uno. Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 55 implementazione tutte le funzioni in questa implementazione hanno due argomenti, che identificano un set di semafori e il numero di un semaforo all'interno di quel set. int initSemAvailable(int semId, int semNum); int initSemInUse(int semId, int semNum); int reserveSem(int semId, int semNum); int releaseSem(int semId, int semNum); Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 56 // Initialize semaphore to 1 (i.e., "available") int initSemAvailable(int semId, int semNum) { union semun arg; arg.val = 1; return semctl(semId, semNum, SETVAL, arg); } // Initialize semaphore to 0 (i.e., "in use") int initSemInUse(int semId, int semNum) { union semun arg; arg.val = 0; return semctl(semId, semNum, SETVAL, arg); } Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 57 // Reserve semaphore - decrement it by 1 int reserveSem(int semId, int semNum) { struct sembuf sops; sops.sem_num = semNum; sops.sem_op = -1; sops.sem_flg = 0; return semop(semId, &sops, 1); } // Release semaphore - increment it by 1 int releaseSem(int semId, int semNum) { struct sembuf sops; sops.sem_num = semNum; sops.sem_op = 1; sops.sem_flg = 0; return semop(semId, &sops, 1); } Daniele Radicioni - Laboratorio di Sistemi Operativi, corso A - turno T1 58