Ci sono SCRITTALEN thread ognuno dei quali controlla un “pixel” che si sposta da una coordinata iniziale a una finale su una board di dimensioni X,Y. I thread pixel vengono attivati da un thread scheduler in modo che compongano una lettera alla volta. Quando un pixel appartiene alla lettera che viene composta in un determinato momento diciamo che è il turno di quel pixel.
Lo schema per i thread pixel è il seguente:
pixel_code(id) {
attendi_turno(id); // attende il via dello scheduler, significa che il pixel appartiene alla lettera che viene composta in questo momento
finché non hai raggiunto la posizione {
/*** scegli una nuova posizione nx, ny **/
inizia_mossa(nx,ny);
finché nx, ny non è vuota {
fine_mossa(nx,ny);
/*** scegli una nuova posizione nx, ny **/
inizia_mossa(nx,ny);
}
/*** si muove sulla board condivisa in posizione nx,ny ***/
fine_mossa(nx,ny);
}
fatta_lettera(id); // comunica allo scheduler di aver raggiunto la posizione finale
}
Lo schema del thread scheduler è il seguente:
scheduler_code() {
per ogni turno { // quindi per ogni lettera da comporre
per ogni thread pixel j del turno { // per tutti i pixel che compongono la lettera
dai_turno(j); // dai il via al pixel j
}
per ogni thread pixel j del turno {
attendi_lettera(j); // attendi che il pixel j abbia raggiunto la posizione
}
}
}
L’associazione tra pixel e lettere viene fatta automaticamente dal programma. Si richiede di implementare le sole funzioni di sincronizzazione:
/************** PARTE DA CONSEGNARE **************/
// definire qui i semafori
void inizializza() {
}
void distruggi() {
}
void inizia_mossa(int x, int y) {
}
void fine_mossa(int x, int y) {
}
void attendi_lettera(int i) {
}
void fatta_lettera(int i) {
}
void attendi_turno(int i) {
}
void dai_turno(int i) {
}
/*********** FINE PARTE DA CONSEGNARE ************/
Il sorgente della verifica (al cui interno è necessario implementare le fuzioni descritte sopra) è disponibile qui. Provate a risolverla e poi confrontatevi con la soluzione qui sotto.
Soluzione commentata della verifica, da guardare solo DOPO averla risolta 🙂
/**
* Scopo della verifica è sincronizzare i thread pixel che compongono la scritta iniziale "BOCCIATO!!" in modo che
* questa si trasformi in "PROMOSSO :)". I thread pixel sono attivati da un thread scheduler in modo che compongano
* una lettera/carattere alla volta. È inoltre necessario rispettare i seguenti vincoli:
* - i pixel che compongono una lettera devono muoversi contemporaneamente (in caso contrario, infatti, scatta un
* timeout che termina il programma);
* - due o più pixel non possono occupare contemporaneamente la medesima casella.
*
* Per realizzare quanto richiesto, utilizziamo:
* - una matrice di semafori ('campo') per determinare quali posizioni del campo sono libere o meno: in particolare,
* il semaforo in posizione (x, y) sarà rosso se la posizione è già occupata da un pixel, verde altrimenti;
* - un vettore di semafori ('turno') usato dallo scheduler per comunicare ai pixel quando sono autorizzati ad
* iniziare lo spostamento;
* - un vettore di semafori ('mosso') usato dai pixel per comunicare allo scheduler che hanno terminato il loro
* spostamento.
*/
sem_t campo[X][Y];
sem_t turno[SCRITTALEN];
sem_t mosso[SCRITTALEN];
void inizializza() {
int i, j;
/* Inizialmente le posizioni del campo sono tutte libere, quindi tutti i semafori sono inizializzati a 1. */
for (i = 0; i < X; i++)
for (j = 0; j < Y; j++)
sem_init(&campo[i][j], 0, 1);
/* Lo scheduler non ha ancora autorizzato alcun pixel a muoversi, quindi i semafori del vettore 'turno' sono
* tutti inizializzati a 0. Inoltre nessun pixel ha chiaramente raggiunto la posizione finale, quindi anche
* i semafori del vettore 'mosso' sono a 0. */
for (i = 0; i < SCRITTALEN; i++) {
sem_init(turno + i, 0, 0);
sem_init(mosso + i, 0, 0);
}
}
void distruggi() {
int i, j;
/* Distruggi i vari semafori. */
for (i = 0; i < X; i++)
for (j = 0; j < Y; j++)
sem_destroy(&campo[i][j]);
for (i = 0; i < SCRITTALEN; i++) {
sem_destroy(turno + i);
sem_destroy(mosso + i);
}
}
void inizia_mossa(int x, int y) {
/* Accedi alla cella in posizione (x, y) in mutua esclusione: se è già occupata, attendi. */
sem_wait(&campo[x][y]);
}
void fine_mossa(int x, int y) {
/* Il pixel sta per abbandonare la casella: notifica che la posizione è libera. */
sem_post(&campo[x][y]);
}
void attendi_lettera(int i) {
/* Lo scheduler attende che il pixel con id 'i' abbia completato lo spostamento nella posizione finale. */
sem_wait(mosso + i);
}
void fatta_lettera(int i) {
/* Il pixel 'i' notifica al thread scheduler di essersi spostato con successo nella posizione finale. */
sem_post(mosso + i);
}
void attendi_turno(int i) {
/* Il pixel 'i' attende che lo scheduler autorizzi l'inizio dello spostamento. */
sem_wait(turno + i);
}
void dai_turno(int i) {
/* Lo scheduler autorizza il pixel 'i' ad iniziare a muoversi. */
sem_post(turno + i);
}