Elaborato di Sistemi Operativi, a.a. 2005/06

Docente Matteo Vaccari

Aggiornamento 12/06/2006

Per salvare il vostro elaborato su un immagine di floppy disk, lanciate qemu con l'opzione -fda floppy.img dove floppy.img è un file che contiene un immagine di floppy, come questa. Create un tar, per esempio rossi-bianchi.tgz ed eseguite il comando

  doswrite /dev/fd0 rossi-bianchi.tgz < rossi-bianchi.tgz

Poi, per estrarre dall'immagine di floppy il tar, si possono usare su Linux gli mtools. In /etc/mtools.conf, mettete una riga tipo

  drive m: file="floppy.img"

e poi date il comando

  mdir m:
  mcopy m:ROSSI-BI.TGZ
  mv ROSSI-BI.tgz rossi-bianchi.tgz

(in msdos il nome del file è limitato a 8+3 caratteri.)

Aggiornamento 08/06/2006

Chiarimento: mi aspetto che realizziate due programmi di test; il primo, lo "unit test", è dato in pseudo codice. Dovete tradurre lo pseudocodice in un programma C funzionante. Il secondo è il programma produttori-consumatori.

Mi aspetto che sia possibile realizzare l'elaborato modificando esclusivamente:

uno o più file di include di sistema
il process manager (PM)
la libreria C

Oltre ovviamente a scrivere i programmi di test. Mi aspetto che il PM venga modificato aggiungendo (preferibilmente) un solo file C che contenga tutte le funzioni aggiuntive necessarie, con eventualmente un file ".h" di corredo.

Ho aggiornato la descrizione di come prendere spunto da servers/pm/forkexit.c per sapere come bloccare i semafori

Aggiornamento 18/05/2006

Per spostare i file da e verso Minix, la cosa più semplice è usare ftp. Occorre configurare la rete in Minix. E' abbastanza facile, seguendo queste istruzioni. Poi occorre che il proprio PC sia collegato in rete, con un server dhcp. Il dhcp serve perché dovrà fornire un indirizzo a qemu. Poi qemu, una volta ottenuto il suo indirizzo di rete, crea una sua sottorete interna e assegna un indirizzo a Minix, tipo 10.0.2.15

Si può configurare un ftp server sul proprio PC. Ad esempio, sulla mia macchina Linux io do il comando

  sudo proftpd

dopodiché in Minix posso dare il comando

  ftp 111.111.111.111

(sostituire con l'indirizzo IP del proprio PC.) In alternativa, si può usare Pisolo come server ftp. Occorre farsi dare un account, e poi da minix si può dare il comando

  ftp pisolo.sciva.uninsubria.it

Prima di fare trasferimenti di file, occorre di solito dare il comando "passive", che istruisce ftp ad aprire connessioni solo nella direzione dal client al server.

Se lavorate molto con ftp, consiglio di installare ncftp (con packman) perché è molto meglio del client "ftp" standard.

In teoria sarebbe molto più semplice usare scp. Ho provato a installare il pacchetto openssh: ssh funziona, ma scp no. Non ho capito perché.

Regole

L'elaborato consiste nel realizzare un insieme di modifiche al sistema operativo Minix
Lo studente ha facoltà di servirsi del laboratorio dell'Università, oppure di un computer privato.
Il lavoro è da svolgersi in coppia non sono ammesse terne. Solo nel caso lo studente sia lavoratore o abbia qualche problema particolare per cui non può lavorare in coppia, è ammesso realizzare l'elaborato da soli.
E' ammesso discutere il problema fra studenti; ma non è ammesso scambiarsi programmi o frammenti di programma. Proteggete le vostre directory per evitare che terzi possano copiare il vostro codice.
Non è ammesso copiare pezzi di programma da risorse che potete trovare su Internet o altrove.
L'elaborato va consegnato per email entro sette giorni dalla data dell'appello; se per esempio l'appello è il giorno 10, l'elaborato va consegnato entro la mezzanotte del giorno 3. Tutti i file che modficate devono iniziare con una intestazione di questa forma:
```
Elaborato di Sistemi Operativi I, II e Laboratorio; A.A. 2005/06
Autori:    Rossi Paolo 123456 e Bianchi Mario 234567
Appello:   giugno 2006
```
La realizzazione di questo elaborato è condizione necessaria per superare l'esame

Tenete d'occhio il forum per gli annunci ed eventuali integrazioni.

Dettagli pratici

Prima di iniziare a modificare i sorgenti di Minix, eseguire il comando

cp -rp /usr/src /usr/src.orig

per conservare una versione originale non modificata dei sorgenti, che servirà in seguito per calcolare le differenze.

La versione ufficiale che dovete usare del kernel di Minix è 3.1.2. Non vale la 3.1.1.

Il banner del sistema operativo, che appare sulla console quando premo F7, deve mostrare i vostri nomi in questo modo:

Minix 3.1.2 Modificato da Rossi Paolo 123456 e Bianchi Mario 234567

Tema: i semafori

Aggiungiamo al kernel di minix delle nuove chiamate di sistema che implementano, per conto dei programmi utente, delle nuove chiamate di sistema.

#include <minix/semaphore.h>
#define NUM_SEMAPHORES 10
int sem_init(int semaphore_id, int value); 
int sem_down(int semaphore_id); 
int sem_up  (int semaphore_id); 
int sem_status(int semaphore_id, int* value, int* num_blocked);

Devono essere supportati 10 semafori, disponibili globalmente a tutti i processi. Quindi semaphore_id deve assumere valori compresi fra 0 e 9.

int sem_init(int semaphore_id, int value); inizializza un semaforo. Se il semaforo non era mai stato inizializzato prima, viene inizializzato al valore specificato. Se il semaforo era già stato inizializzato, la chiamata fallisce e restituisce -1, settando errno a EBUSY.

int sem_down(int semaphore_id); esegue una down sul semaforo, con la semantica usuale dei semafori. Se il semaforo non è stato inizializzato, la chiamata fallisce (restituisce -1) settando errno a ENOENT. Similmente per sem_up().

int sem_status() deve restituire il valore corrente del semaforo, e il numero di processi bloccati su di esso. Ha lo scopo di permetterci di testare la correttezza dell'implementazione. Come le altre chiamate restituisce -1 se il semaforo non è inizializzato e setta errno a ENOENT.

Test della soluzione

Per testare che il sistema funzioni correttamente, occorre realizzare un certo numero di programmi di test.

Unit test

Lo pseudo codice del test:

inizializzo un semaforo a 0
sem_status deve riportare i valori 0, 0 
faccio una up
sem_status deve riportare i valori 1, 0 
faccio una down
sem_status deve riportare i valori 0, 0 
faccio partire un processo figlio
il figlio esegue una down (mi aspetto che si blocchi); 
il genitore esegue una sleep(1) per dare tempo al figlio di bloccarsi
il genitore verifica che sem_status riporti 0, 1
il genitore verifica che waitpid riporti che il figlio non è terminato
il genitore esegue una up, e poi una sleep(1) per dare tempo al figlio di terminare
il figlio si sveglia e termina con una exit(0)
il genitore verifica che sem_status_riporti 0, 0
il genitore verifica con waitpid che il figlio è terminato con status 0

Nota: normalmente non accettiamo algoritmi che dipendono fa temporizzazioni (tipo sleep(1)). E infatti nel codice di produzione non dovrebbero esserci. Qui siamo nel codice di test, dove sono ammesse, dato che in generale è difficile testare il codice concorrente.

E' possibile elaborare questo schema; per testare in maniera più efficace metterei tutto questo codice in un ciclo che testa separatamente ciascuno dei 10 semafori. E' raccomandabile testare più di un processo in coda sullo stesso semaforo; altrimenti si rischia che il codice che accoda e scoda i processi in attesa non funzioni.

Test di accettazione

Realizzare un sistema produttore-consumatore. Lo pseudocodice si trova sul testo. La sincronizzazione va fatta con i semafori. Il buffer condiviso viene simulato con un file: i produttori appendono dati al file. Il consumatore tenta di leggere solo quando i semafori gli danno il permesso di leggere; quindi è garantito che ci sia un elemento da leggere. Se la read restituisce 0, significa che non è stato rispettato il protocollo (vale a dire, cerchiamo di leggere da un buffer vuoto.) Il programma di test deve prevedere questa evenienza e stampare un messaggio di errore.

Durante l'esecuzione il file intermedio crescerà di dimensione indefinitamente, al contrario del buffer circolare convenzionale implementato in RAM, che occupa una quantità di memoria costante. In una implementazione realistica utilizzeremmo un meccanismo di memoria condivisa; ma in Minix questi meccanismi non sono disponibili, percui ci accontentiamo di simulare il buffer su un file.

Il programma main deve inizializzare i semafori, creare il file di buffer "/tmp/buffer.txt", e lanciare tre produttori e un consumatore. I produttori scrivono sul buffer un record di dimensione costante, che contiene un numero, rappresentato in forma decimale. Il record è di 10 caratteri, di cui 9 sono usati per rappresentare il numero e il decimo è il carattere CR (ASCII 13). Ad esempio

000000123<cr>

Il primo produttore produce una sequenza di numeri crescenti a partire da zero. Il secondo produce una sequenza che parte da 1000. Il terzo produce una sequenza che parte da 10000. Il consumatore legge questi numeri e produce in standard output la somma corrente di tutti i numeri che ha letto.

Documentazione

Il lavoro deve essere opportunamente documentato. La documentazione deve trovarsi nel file /usr/src/test/cognome1-cognome2/semafori.txt e deve comprendere:

nome, cognome e numero di matricola degli autori
strutture dati utilizzate
algoritmi utilizzati
[opzionale] interpretazione del tema: se avete riscontrato delle ambiguità del tema dell'elaborato, descrivete come le avete interpretate
[opzionale] limiti della soluzione; se sapete che ci sono alcuni casi (non previsti dal tema d'esame) in cui la vostra soluzione non funziona, documentateli. Se ci sono direzioni interessanti in cui questo lavoro potrebbe essere continuato, descrivetele (brevemente)
[opzionale] se avete sviluppato estensioni non previste dal tema, descrivetele

La documentazione deve essere presentata sotto forma di file di testo, di nome semafori.txt. Cercate di fare in modo che si presenti bene, anche se si tratta di un semplice file di testo. (File in formati proprietari prodotti da word processor non verranno presi in considerazione).

Lo stile di impaginazione della documentazione deve essere simile a quello di questo documento.

Modalità di consegna

L'elaborato va consegnato sotto forma di file tgz (vedi "man tar") con nome della forma rossi-bianchi.tgz. Il tar deve contenere solo i file che sono stati modificati o creati. Un esempio di comando potrebbe essere:

  cd /usr/src
  tar cvzf include/semaphores.h \
           include/minix/callnr.h \
           test/rossi-bianchi/unit-test.c \
           test/rossi-bianchi/prod-cons.c \
           test/rossi-bianchi/Makefile \
           test/rossi-bianchi/semafori.txt \
           lib/other/semaphores.c \
           lib/other/Makefile \
           servers/pm/table.c ... ecc. ecc.

Testate che il file contenga effettivamente tutto quello che serve per far funzionare i programmi di test! Io testerò il vostro sistema con i comandi

# ripristino i sorgenti originali di minix 3.1.2
mv /usr/src /usr/src.old
cp -r /usr/src.orig /usr/src
# estraggo l'elaborato
cd /usr/src
tar xvzf rossi-bianchi.tgz
# compilo le librerie
cd /usr/src/lib ; make install
# compilo il kernel
cd /usr/src/tools ; make install
reboot
# eseguo i vostri test
cd /usr/src/test/rossi-bianchi ; make test

I vostri programmi di test devono trovarsi in /usr/src/test/cognome1-cognome2 e devono potersi compilare ed eseguire con make test

Suggerimenti

La realizzazione dei semafori comporta l'uso, per ogni semaforo, di una lista di processi bloccati sul semaforo e di un intero. La manipolazione di questa struttura dati non richiede l'uso di un mutex. Questo per il seguente motivo: il codice che manipola i semafori sarà presumibilmente realizzato all'interno del process manager (PM). Il PM esegue con una priorità superiore rispetto a qualsiasi processo utente. Quindi è impossibile che l'esecuzione di una syscall possa essere interrotta da un'altra syscall, perché nessun processo utente può interrompere il PM per chiamare un'altra syscall.

Definiamo un nuovo flag in servers/pm/mproc.h, che indica che un proc è in attesa perché bloccato su un semaforo

  #define SEM_WAITING    0x4000   /* in attesa su un semaforo */

Deve essere una potenza di due, quindi rappresentato con un singolo bit a 1, per poterlo settare indipendentemente da tutti gli altri.

Per mettere un processo che chiama una syscall in sleep, si può prendere spunto dalla funzione do_waitpid(), in servers/pm/forkexit.c, che implementa sia la wait(2) che la waitpid(2).

  mp->mp_flags |= SEM_WAITING;  /* in attesa su un semaforo */
  return(SUSPEND);                 /* do not reply, let it wait */

Nel main del PM, si vede che se una funzione do_xxx() restituisce SUSPEND, allora non viene mandata la risposta al processo che ha chiamato la syscall. In questo modo il processo resta bloccato in attesa della sua risposta.

Nella sem_up() occorre risvegliare uno degli eventuali processi in attesa. Per sapere quali sono questi processi, occorre conservare una lista. Per risvegliare il processo, una volta che abbiamo il puntatore alla sua posizione nella proc table, si può prendere spunto dalla funzione cleanup(), in servers/pm/forkexit.c

  int index_of_waiting_proc = dequeue_from_my_semaphore_queue();

  /* Wake up the parent by sending the reply message. */
  setreply(index_of_waiting_proc, 0);
  mproc[index_of_waiting_proc].mp_flags &= ~SEM_WAITING;  /* no longer waiting */

La manipolazione delle liste: in generale Minix cerca di evitare tutte le allocazioni dinamiche. Quindi non troviamo nessuna chiamata di "malloc" nel codice del kernel, nè nei server PM o FS. La maniera Minix di implementare la lista dei processi in attesa è di definire un campo in più nella tabella dei processi (quella del process manager, definita in mproc.h), che punta all'eventuale prossimo processo nella coda. E' sufficiente un campo, perché un processo può essere in attesa su un solo semaforo per volta. Chiaro che, volendo, nel PM si potrebbe implementare la lista con malloc(), dato che il PM è un processo user-space.

Propedeutico alla realizzazione di questo esercizio è l'esercizio di aggiungere una chiamata di sistema, proposto in fondo alle mie istruzioni per Minix. Se non sai fare quello, non provare a fare questo.

Raccomandazione

Non datemi codice disordinato: fate che sia leggibile, ordinato, ben indentato.

Traccia di soluzione

Conviene lavorare per gradi, facendo evolvere la soluzione e lo unit test insieme. Il mio primo obiettivo dovrebbe essere di realizzare soltanto metà della semantica dei semafori, vale a dire fare finta che siano delle semplici variabili intere, con la sem_down che non blocca mai. In questo modo posso testare le mie funzioni in user space, senza bisogno di fare un reboot del kernel ad ogni passo. Quando i "semafori dimezzati" funzionano, posso installarli nel PM, e vedere se il mio unit test continua a funzionare.

Una volta che ho i semafori dimezzati correttamente installati nel kernel, aggiungere la parte che blocca i processi nella sem_down e li risveglia nella sem_up diventa fattibile. Primo stadio: un primo programma di test. Testo solo il funzionamento di sem_init().

 
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <semaphores.h>

void assert_equal(int expected, int actual, char * message) {
  if (expected != actual) {
    fprintf(stderr, "ERROR %d != %d, %s (%d)\n", 
	    expected, actual, message, errno);
  }
}

main(void) {
  assert_equal(0,  sem_init( 0, 0), "sem_init(0, 0) fallisce");  
  assert_equal(-1, sem_init( 0, 0), "reinizializzaz di sem 0 non fallisce");
  assert_equal(-1, sem_init(-1, 0), "sem_init(-1, 0) non fallisce");  
  assert_equal(0,  sem_init( 1, 3), "sem_init(1, 3) fallisce");
  ...

  exit(0);
}

Per compilare occorre definire le funzioni sem_*; le mettiamo in un file semaphores.c

#include <semaphores.h>

int sem_init(int semaphore_id, int value) {
  return 0;
}

int sem_status(int semaphore_id, int *value, int *num_blocked) {
  return 0;
}

int sem_up(int semaphore_id) {
  return 0;
}

Per compilare ed eseguire uso un semplice Makefile:

CFLAGS = -I. -Wall

test: unit_test
	./unit_test

unit_test: unit_test.o semaphores.o
	cc -Wall unit_test.o semaphores.o -o unit_test

La sequenza di lavoro è: scrivo un semplice test. Aggiungo quanto occorre perché compili. Lo eseguo e verifico che fallisca. Poi modifico il codice di produzione (semaphores.c) per fare riuscire il test. Aggiusto il codice per rimuovere ripetizioni e sporcizia, sempre verificando che il test continui a funzionare, e ricomincio.

Usate delle asserzioni per verificare ogni dettaglio del comportamento delle syscall:

che la sem_up incrementi il valore di un semaforo
che la sem_down lo decrementi
che la sem_up o sem_down falliscano su un semafono non inizializzato,
...

Quando sem_init in userspace funziona decentemente, provo a inserirla nel PM.

Modifico src/include/minix/callnr.h per aggiornare il numero di chiamate di sistema, e definire costanti SEM_INIT, SEM_STATUS, ecc per le nostre syscall.
copio il mio semaphores.c in servers/pm.
aggiorno il Makefile del PM.

aggiorno la tabella delle syscall nel PM. Le nostre syscall saranno implementate nelle funzioni do_sem_init, do_sem_status, ecc.

...
	no_sys,		/* 93 = truncate */
	no_sys,		/* 94 = ftruncate */
	do_sem_init,	/* 95 = sem_init */
	do_sem_status,	/* 96 = sem_status */
	do_sem_up,	/* 97 = sem_up */
	do_sem_down,	/* 98 = sem_down */
};

definisco le do_* in proto.h

aggiungo a semaphores.c le funzioni do_*, inizialmente vuote. La do_sem_init potrà essere implementata in termini della nostra sem_init. Il mio semaphores.c sarà simile a questo:

#include <semaphores.h>
#include "pm.h"
#include <minix/callnr.h>
#include <minix/endpoint.h>
#include <signal.h>
#include "mproc.h"
#include "param.h"

int do_sem_init(void) {
  int semaphore_id = m_in.m1_i3;
  int value = m_in.m1_i2;
  return sem_init(semaphore_id, value);
}

int do_sem_status(void) {
  ...
}

int do_sem_up(void) {
  ...
}

int do_sem_down(void) {
  ...
}
#endif

struct sem {
  int value;
  ...
} sem[NUM_SEMAPHORES];


int sem_init(int semaphore_id, int value) {
  if (semaphore_id < 0 || semaphore_id >= NUM_SEMAPHORES) {
    return -1;
  }
  sem[semaphore_id].value = value;
  ...
  return 0;
}

int sem_status(int semaphore_id, int *value, int *num_blocked) {
  ...
}

int sem_up(int semaphore_id) {
  ...
}

int sem_down(int semaphore_id) {
  ...
}

Creo un file sem_stub.c che contenga tutte le stub in spazio utente delle chiamate di sistema sem_*

#include <lib.h>
#include <semaphores.h>

PUBLIC pid_t sem_init(int semaphore_id, int value)
{
  message m;
  m.m1_i3 = semaphore_id;
  m.m1_i2 = value;
  return(_syscall(MM, SEM_INIT, &m));
}

int sem_status(int semaphore_id, int *value, int *num_blocked) {
  ...
}

int sem_up(int semaphore_id) {
  ...
}

int sem_down(int semaphore_id) {
  ...
}

È utile avere un makefile per eseguire rapidamente compilazione e test.

CFLAGS = -I. -Wall

test: unit_test
	./unit_test

unit_test: unit_test.o semaphores.o
	cc -Wall unit_test.o semaphores.o -o unit_test

Quando il semplice test che tratta il semaforo come se fosse un semplice contatore funziona anche compilato nel PM, possiamo cominciare a testare che la sem_down blocchi effettivamente il processo chiamante se il semaforo vale 0. Modifichiamo l'unit_test:

  pid = fork();
  if (0 == pid) {
    /* il processo figlio deve bloccarsi */
    sem_down(0);
    exit(0);
  } else {
    int r, status;
    /* diamo tempo al figlio di entrare nella down */
    sleep(1);
    sem_status(0, &value, &nb);
    assert_equal(1, nb, "nb non vale 1 dopo la seconda down");
    /* se waitpid mi restituisce 0 vuol dire che il processo figlio
       è ancora vivo; quindi deve essere bloccato  */
    r = waitpid(...);
    assert_equal(0, r, "il processo figlio non si e' bloccato!!!");
  }

Mi aspetto che questo test fallisca fino a quando non modifico la sem_down per fare in modo che blocchi i processi.

Il test a questo punto è ancora incompleto. Quando funziona, e sempre a piccoli passi, lo estendo per verificare che

la sem_up risveglia il processo bloccato (eseguo la sem_up nel genitore, poi ancora la waitpid per verificare se questa volta il processo figlio ha terminato.)
se blocco due o tre processi su un semaforo, e poi li posso risvegliare con delle up

Probabilmente vi verrà comodo realizzare una ulteriore syscall sem_reset(void) che resetta lo stato di tutti i vostri semafori, in modo da poter eseguire più volte i test senza che un'esecuzione precedente faccia fallire il test.