Ho implementato un buffer circolare tramite file, che funziona molto meglio delle indicazioni che avevo dato in precedenza. Ho anche implementato il test dei produttori e consumatori. Da questo momento usate questo invece delle vecchie indicazioni. Si trova tutto in questa directory. Ulteriori istruzioni più sotto.
Il test usa la chiamata sem_reset() che tutti hanno implementato anche se non era parte dei requisiti. In effetti non è pratico lavorare senza, per cui assumo che abbiate implementato anche questa chiamata, che non fa altro che resettare a "non inizializzato" lo status di tutti i semafori, senza preoccuparsi troppo dello stato di eventuali processi bloccati sui semafori.
$ ./unit_test exec cc prod-cons.c -o prod-cons.o exec cc test.c -o test.o exec cc ktest.c -o ktest.o ./test.o value is 0, num blocked is 0 value is 1, num blocked is 0 value is 0, num blocked is 0 Child unblocked value is 0, num blocked is 0 value is 1, num blocked is 0 value is 0, num blocked is 0 value is 0, num blocked is 1 Child is blocked value is 0, num blocked is 0 Child exited with status 0 $I test di Silente, invece, producevano qualcosa di simile a questo:
$ ./unit_test ..................................OK $Se doveste usare i test di uno dei due, chi preferireste?
Nel test di Verbone viene prodotto tantissimo output, e non è chiaro, guardandolo, se il test ha avuto successo oppure no. Il test di Silente, invece, è chiarissimo. Quando c'è un errore, Silente stampa qualcosa tipo
$ ./unit_test .................................. ERROR: expected 2, but was 0 in 'valore di frobniz dopo la zork' ....... 1 errors $Se il test va bene, tutto quello che serve è stampare un puntino ad ogni asserzione, così sappiamo che non si è piantato. Se ci sono errori, devono essere in evidenza e con informazioni sufficienti a capire che asserzione è fallita e perché.
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.tgzPoi, 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.)
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:
Ho aggiornato la descrizione di come prendere spunto da servers/pm/forkexit.c per sapere come bloccare i semafori
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 proftpddopodiché 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é.
Elaborato di Sistemi Operativi I, II e Laboratorio; A.A. 2005/06 Autori: Rossi Paolo 123456 e Bianchi Mario 234567 Appello: giugno 2006
Tenete d'occhio il forum per gli annunci ed eventuali integrazioni.
Prima di iniziare a modificare i sorgenti di Minix, eseguire il comando
cp -rp /usr/src /usr/src.origper 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
#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.
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 0Nota: 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.
Dovete scaricare e compilare il test d'accettazione, che implementa il sistema produttori-consumatori usando i semafori. Dovete eseguire questo test e verificare che non produca messaggi di errore (se non scrive niente in output vuole dire che ha avuto successo.)
Il test è composto dai file prod_cons.c e buffer.[ch] . L'idea è che i produttori producono numeri interi in sequenza, ciascuno con una sequenza diversa. I consumatori prendono questi numeri e li appendono a un file. Quando i produttori e i consumatori hanno terminato, il programma di test riordina il file di output e verifica che ci siano tutti i numeri che ci devono essere.
Ovviamente, se il test di accettazione non funziona, il vostro elaborato non può essere consegnato.
Lo stile di impaginazione della documentazione deve essere simile a quello di questo documento.
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 testI vostri programmi di test devono trovarsi in /usr/src/test/cognome1-cognome2 e devono potersi compilare ed eseguire con make test
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.
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_testLa 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:
Quando sem_init in userspace funziona decentemente, provo a inserirla nel PM.
... 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 */ };
#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) {
...
}
#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) {
...
}
CFLAGS = -I. -Wall test: unit_test ./unit_test unit_test: unit_test.o semaphores.o cc -Wall unit_test.o semaphores.o -o unit_testQuando 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