Appunti di Sistemi Operativi Enzo Mumolo e-mail address … · 2007-10-16 · Appunti di Sistemi...

Appunti di Sistemi Operativi

Enzo Mumolo

e-mail address :[email protected] address :www.units.it/mumolo

Indice

1 Esempi di programmazione concorrente 1

1.1 Scrittura di un grafo alle precedenze co un linguaggio concorrente . . . . . . . . . . . 11.2 Una soluzione ibrida al problema del Produttore/Consumatore . . . . . . . . . . . . 31.3 Realizzazione in Java del calcolo concorrente . . . . . . . . . . . . . . . . . . . . . . . 31.4 Mutua esclusione con la primitiva 'scambia' . . . . . . . . . . . . . . . . . . . . . . . 71.5 Metodo synchronized per la mutua esclusione . . . . . . . . . . . . . . . . . . . . . . 81.6 Un semplice problema di sincronizzazione . . . . . . . . . . . . . . . . . . . . . . . . 91.7 Una soluzione semaforica al problema del produttore/consumatore . . . . . . . . . . 101.8 Una soluzione semaforica al problema dei lettori/scrittori . . . . . . . . . . . . . . . . 121.9 Somma concorrente degli elementi di un array . . . . . . . . . . . . . . . . . . . . . . 141.10 Applicazione del problema dei lettori/scrittori alla sincronizzazione di un ponte . . . 161.11 Il prolema dei 5 �loso� mangiatori di spaghetti . . . . . . . . . . . . . . . . . . . . . 18

i

Capitolo 1

Esempi di programmazione concorrente

In questo capitolo vengono descritti ulteriori problemi di programmazione concorrente.

1.1 Scrittura di un grafo alle precedenze co un linguaggio concor-rente

Si consideri la seguente procedura in C:

float calcola(float a, float b, float c, float d, float e, float f)

{

float x, y, z, t;

x=a*sqrt(b) ; y=c*c*d; z=y+e ; t=y*f ; z =x*z ; t=x*t*t ;

return(z*t) ;

}

Si supponga di riscrivere la medesima procedura usando un linguaggio di programmazioneconcorrente. Precisamente, si riscriva la procedura usando le primitive

• (p=fork(processo), join(p))

• (cobegin, coend).

Si considerino i seguenti sei thread, espressi in pseudo-codice:

• T1(a,b) x=a*sqrt(b) ; return x ;

• T2(c,d) y=c*c*d; return y; T3(y,f) t=y*f ; return t ;

• T4(y,e) z=y+e ; return z ; T5(x,t) t=x*t*t ; return t ;

• T6(x,z) z=x*z ; return z ;

Con queste de�nizioni, la funzione in ambiente concorrente, è espressa con il seguente grafo :Usando un linguaggio di programmazione concorrente che realizza la concorrenza con le istruzioni

cobegin/coend, il grafo corrisponde al seguente programma concorrente:

float calcola(a,b,c,d,e,f) {

cobegin

T1;

T2;

coend;

1

1.1 Scrittura di un grafo alle precedenze co un linguaggio concorrente 2

AA BB FF CC DD EE

T1T1 T2T2

T3T3 T4T4

T5T5

T6T6

++

Figura 1.1 Grafo alle precedenze che rappresenta la funzione

cobegin

T3;

T4;

coend;

cobegin

T5;

T6;

coend;

return(z+t);

}

Usando invece un linguaggio che realizza la concorrenza con le primitive fork/join, si puòrealizzare il seguente programma concorrente:

float calcola(a,b,c,d,e,f) {

P1=fork(T1);

T2;

P2=fork(T4);

T3;

Join(P1);

T5;

Join(P2);

T6;

1.2 Una soluzione ibrida al problema del Produttore/Consumatore 3

Return(z+t):

}

1.2 Una soluzione ibrida al problema del Produttore/Consumatore

Per soluzione ibrida si intende qui utilizzare l'algoritmo di Peterson per la mutua esclusione e duesemafori per le sincronizzazioni. Lo pseudocodice di tale algoritmo é quindi il seguente:

produttore(){ consumatore(){

while(true){ while(true){

p=0; t=1; q=0; t=2;

elto=produci(); down(vuoto);

down(pieno); while(p!=1 && t==2) ;

while(q!=1 && t==1) ; elto=*ptr-- ;

*ptr++=elto ; q=1 ;

p=1 ; up(pieno) ;

up(vuoto) ; }

} }

}

Questo algoritmo usa un bu�er condiviso (puntato da ptr, puntatore condiviso), due semafori perla sincronizzazione del bu�er, pieno e vuoto, e tre variabili condivise, p, q e t per l'algoritmo diPeterson.

1.3 Realizzazione in Java del calcolo concorrente

In questo esempio si usa il calcolo concorrente per valutare un polinomio in un punto x.

/* principale.java */

/************************************************

Il grafo delle precedenze si puo' rappresentare nel modo seguente

P1 P2 P3 I thread valutano l'espressione

\ \ / 3*a^3+2*b^2+3*d^3 in modo

\ \ / concorrente.

\ \ / P1 -> x=3*a^3

\ P4 P2 -> y=2*b^3

\ / P3 -> z=3*d^3

\ / P4 -> t=y*z

\ / P5 -> k=x+t

P5

***********************************************/

import java.lang.*; import java.util.*;

public class principale {

public static void main(String[] args) {

////////////////////////////////

String[] str= new String[3];

1.3 Realizzazione in Java del calcolo concorrente 4

str[0]="2";

str[1]="3";

str[2]="4";

///////////////////////////////

double a,b,d;

a=Double.parseDouble(str[0]);

b=Double.parseDouble(str[1]);

d=Double.parseDouble(str[2]);

data item= new data(a,b,d);

P1 p1=new P1(item); // istanze

P2 p2=new P2(item);

P3 p3=new P3(item);

P4 p4=new P4(item);

P5 p5=new P5(item);

p1.start(); // calcolo concorrente

p2.start();

p3.start();

try { p2.join(); }

catch(InterruptedException e) {System.out.println("Errore P2");}

try { p3.join(); }


p4.start();

try { p1.join(); }


try { p4.join(); }


p5.start();

try { p5.join(); }


p1.stop();

p2.stop();

p3.stop();

p4.stop();

p5.stop();

System.out.println(" Fine programma ");

}

}

La classe data de�nisce le variabili condivise.

/* data.java */

public class data {

/*********************

Processi:


P1 -> x=3*a^3

P2 -> y=2*b^3

P3 -> z=3*d^3

P4 -> t=y*z

P5 -> k=x+t

*********************/

public double x, y, z, t, k, a, b, d; // variabili condivise

public data(){ // costruttori

x=0; y=0; z=0; t=0; k=0;

a=0; b=0; d=0;

}

public data(double aa,double bb,double dd) {

x=0; y=0; z=0; t=0; k=0;

a=aa;

b=bb;

d=dd;

}

}

/* P2.java */ import java.lang.*;

public class P1 extends Thread{

/** Calcola x=3*a^3 */

data item;

private double y=3; // esponente

private double c=3; // costante

private double x; // base

public P1(data d) {

item=d; // passaggio dell'oggetto "data" a P1

x=d.a; // valore di 'a'

}

public void run(){

potenza p=new potenza(x,y);

item.x=c*p.ans(); // x=3*a^3

System.out.println(" Calcolato x : " + item.x);

}

}

/* P2.java */


/** Calcola y=2*b^3 */

data item;




public P2(data d) {



x=d.b; // valore di 'b'

}

public void run(){


item.y=c*p.ans(); // y=2*b^3

System.out.println(" Calcolato y : " + item.y);

}

}

/* P3.java */


/** Calcola z=3*d^3 */

data item;




public P3(data d) {


x=d.d; // valore di 'd'

}

public void run(){


item.z=c*p.ans(); // z=3*d^3

System.out.println(" Calcolato z : " + item.z);

}

}

/* P4.java */


/** Calcola t=y*z */

data item;

private double y;

private double z;

public P4(data d) {


y=0; // l'assegnazione no va fatta al momento

z=0; // dell'istanziazione, perche' ora 'd.y' e 'd.z'

} // valgono entrambi '0'.

public void run(){

y=item.y; // ora avviene l'assegnazione

z=item.z;

item.t=y*z; // t=y*z

System.out.println(" Calcolato t : " + item.t);

}

}

/* P5.java */

1.4 Mutua esclusione con la primitiva 'scambia' 7


/** Calcola k=x+t */

data item;

private double x;

private double t;

public P5(data d) {


x=0; // valgono le stesse considerazioni fatte per P4

t=0; // in merito all'assegnazione dei valori alle variabili

}

public void run(){

x=item.x;

t=item.t;

item.k=x+t; // k=x+t

System.out.println(" Calcolato il risultato finale k : " + item.k);

}

}

/* potenza.java */

public class potenza {

/** Calcola x^y */

private double esp;

private double base;

public potenza(double x, double y) {

esp=y;

base=x;

}

public double ans(){

return Math.pow(base,esp);

}

}

1.4 Mutua esclusione con la primitiva 'scambia'

Si supponga che una architettura di un calcolatore o�ra al programmatore una istruzione atomica

scambia(a,b), che realizza la seguente funzione:

scambia(short &a, short &b){

short t;

t = *a; *a = *b; *b = t;

}

La mutua esclusione si può ottenere usando la procedura atomica scambia nel seguente modo, inun contesto cioé di attesa attiva:

Processo1{ processo2{

b=1; c=1;

while(true) { while(true) {

while(b==1) scambia(a,b); while(c==1) scambia(a,c);

1.5 Metodo synchronized per la mutua esclusione 8

Sezione_critica1(); Sezione_critica1();

scambia(a,b); scambia(a,c);

} }

} }

Ovviamente la variabile a é condivisa e inizializzata a zero.

1.5 Metodo synchronized per la mutua esclusione

Si consideri un programma multithreaded in java costituito dai seguenti due thread, dove la variabilei è condivisa tra i thread stessi:

public class scrivi1 extends Thread{ public class scrivi2 extends Thread{

public void run(){ public void run(){


i=1; i=2;

System.out.println(thread1 i=+i); System.out.println(thread2 i=+i);

} }

} }

} }

Lo scopo dei due thread é semplicemente quello di scrivere 1 e 2 rispettivamente, ma ovviamente icontext switch asincroni provocano degli interleaving per cui si possono avere delle scritture (errate)tipo:

thread1 i=2thread1 i=2Un semplice modo per risolvere il problema può essere di de�nire una classe condivisa, chiamata

diciamo S, come segue:

public class S{

private int i;

S(){i=0;}

synchronized void s1(){

i=1; System.out.println(Sono il thread scrivi1: i=+i);

}

synchronized void s2(){

i=2; System.out.println(Sono il thread scrivi2: i=+i);

}

}

Con questa classe, i thread scrivi1 e scrivi2 diventano:

public class scrivi1 extends Thread{ public class scrivi2() extends Thread{

S a; S b;

Scrivi1(S a){this.a=a;} Scrivi2(S a){this.b=a;}



a.s1(); b.s2();

} }

} }

}

1.6 Un semplice problema di sincronizzazione 9

1.6 Un semplice problema di sincronizzazione

Si supponga di avere un programma Java, costituito da due threads (riportati in seguito) che vengonoattivati in concorrenza dal programma principale. I due thread condividono la variabile i. Si vuoleche il programma produca una sequenza di numeri uguali, in particolare 5 5 5 5 etc.

public class Inc extends Thread{ public class Dec extends Thread{



System.out.println(i=+i); System.out.println(i=+i);

i++; i--;

} }

} }

} }

Ci si rende conto facilmente che questo codice puó non produrre la sequenza desiderata. Infatti,si supponga che la variabile i sia inizializzata a 5, e che ci sia un context switch dopo il while(true)del thread di sinistra, l'esecuzione del while(true) del thread di destra e un context switch subitodopo il while di destra. Cioè, il primo thread inizia, stampa 5, poi passa al secondo, che stampa 5e ritorna al primo, che incrementa i che passa a 6 e stampa 6, poi passa al secondo che stampa 6 edecrementa etc. La sequenza stampata é pertanto: 556655 etc.

Una possibile soluzione é, tralasciando le de�nizioni dei semafori:

public class Inc()extends Threads{

public void run(){

while(true){

mutex.down();

s1.down():

System.out.println(i=+i);

s2.up();

s3.down();

i++;

mutex.up();

}

}

}

public class Dec()extends Threads{

public void run(){

while(true){

s2.down();

System.out.println(i=+i);

i--;

s3.up();

s1.up():

}

}

}

1.7 Una soluzione semaforica al problema del produttore/consumatore 10

1.7 Una soluzione semaforica al problema del produttore/consumatore

Questa soluzione usa 3 semafori: mutex per la mutua esclusione, vuoto che é un semaforo contatoreche segnala il numero di spazi rimasti nell'array e pieno é un semaforo contatore che segnala ilnumero di elementi scritti nell'array.

/* principale.java */

public class principale {

private static data d= new data();

private static semaforo mutex= new semaforo(1);

private static semaforo vuoto= new semaforo(10);

private static semaforo pieno= new semaforo(0);


P1 P= new P1(d,mutex,pieno,vuoto);

P2 C= new P2(d,mutex,pieno,vuoto);

P.start();

C.start();

}

}

/* data.java */

public class data {

public int IN;

public int OUT;

public int buf[]=new int[10];

public int conta;

public data() {

IN=0;

OUT=0;

for(int i=0; i<10; i++) buf[i]=0;

conta=0;

}

}

/* semaforo.java */

import java.lang.*;

public class semaforo

extends Thread{

private int s;

public semaforo(int n) { s=n; }

synchronized public void down(){

if (s<=0) {

try{wait();} catch(InterruptedException e) {};

}

else s--;

}

synchronized public void up(){

s++;

notify();

1.7 Una soluzione semaforica al problema del produttore/consumatore 11

}

}

Il codice dei due thread, produttore e consumatore, segue:

/* P1.java */

import java.lang.*; import java.io.*;

public class P1

extends Thread { // produttore

private data d;

private semaforo mutex, pieno, vuoto;

/** Creates a new instance of P1 */

public P1(data d, semaforo mutex, semaforo pieno, semaforo vuoto) {

this.d=d;

this.mutex=mutex;

this.pieno=pieno;

this.vuoto=vuoto;

}

public void run (){

int i=1;

while(d.conta<50){

vuoto.down(); // vuoto va inizializzato a 10

mutex.down(); // mutex va inizializzato a 1

d.buf[d.IN]=i;

System.out.println(" P ha inserito "+i+" in buf["+d.IN+"] \n");

d.IN=(d.IN+1)%10;

i++;

d.conta++;

mutex.up();

pieno.up();

}

}

}

/* P2.java */

import java.lang.*;import java.io.*;

public class P2

extends Thread { // consumatore

private data d;

private int el;

private semaforo mutex, pieno, vuoto;

/** Creates a new instance of P2 */

public P2(data d, semaforo mutex, semaforo pieno, semaforo vuoto) {

this.d=d;

this.mutex=mutex;

this.pieno=pieno;

this.vuoto=vuoto;

}

public void run (){

while(d.conta<50){

pieno.down(); // pieno va inizializzato a 0

1.8 Una soluzione semaforica al problema dei lettori/scrittori 12

mutex.down(); // mutex va inizializzato a 1

el=d.buf[d.OUT];

System.out.println(" C ha letto buf["+d.OUT+"]="+el+"\n");

d.OUT=(d.OUT+1)%10;

d.conta++;

mutex.up();

vuoto.up();

}

}

}

1.8 Una soluzione semaforica al problema dei lettori/scrittori

import java.io.*; import java.lang.*;

class Semaforo {

int value;

public Semaforo()

{

value = 1;

}

public Semaforo(int value)

{

this.value = value;

}

public synchronized void up()

{

value++;

notify();

}

public synchronized void down()

{

while (value<=0)

{

try

{

wait();

}

catch(InterruptedException e) { };

}

value--;

}

}

class buffer {

public Semaforo mutex = new Semaforo(1);

public Semaforo blocco = new Semaforo(1);

public int nlett; // numero di lettori

1.8 Una soluzione semaforica al problema dei lettori/scrittori 13

}

class scrittore extends Thread {

buffer dato; // dati condivisi

int numero; // numero dello scrittore

int cont; // numero di scritture

public scrittore(buffer dato,int numero,int cont)

{

this.numero = numero;

this.dato = dato;

this.cont = cont;

}

public void run()

{

for (int i=0;i<cont;i++) // scrive "cont" volte

{

dato.blocco.down();

System.out.println("Scrittore numero "+numero+" ("+i+") Num lett "+dato.nlett);

dato.blocco.up();

}

}

}

class lettore extends Thread {

buffer dato;

int numero; // numero del lettore

int cont; // numero di letture

public lettore(buffer dato,int numero,int cont)

{

this.dato = dato;


this.cont = cont;

}

public void run()

{

for (int i=0;i<cont;i++)

{

dato.mutex.down();

dato.nlett++;

if (dato.nlett==1)

dato.blocco.down();

dato.mutex.up();

System.out.println("Lettore numero "+numero+" ("+i+")");

dato.mutex.down();

dato.nlett--;

if (dato.nlett == 0)

dato.blocco.up();

dato.mutex.up();

}

}

}

1.9 Somma concorrente degli elementi di un array 14

public class main {

public static void main(String argv[])

{

buffer cont= new buffer();

lettore l1 = new lettore(cont,1,1000); // inzializzo lettori

lettore l2 = new lettore(cont,2,1000);

lettore l3 = new lettore(cont,3,1000);

scrittore s1 = new scrittore(cont,1,5); // inizializzo scrittori

scrittore s2 = new scrittore(cont,2,5);

scrittore s3 = new scrittore(cont,3,5);

l1.start(); // faccio partire i thread

s1.start(); // in un ordine "misto"

l2.start(); // per rendere la cosa piu' interessante

s2.start();

l3.start();

s3.start();

}

}

1.9 Somma concorrente degli elementi di un array

Il programma esegue la somma concorrente di un array di 1000 elementi. Vengono realizzati trethread, il primo dei quali somma i primi 500 elementi dell'array, il secondo somma i secondi 500elementi e il terzo somma le due componenti. É un problema di sincronizzazione, risolto in questocaso con una primitiva semaforica.

public class SommaConcorr {

int array[] = new int[1000];

int primaMeta = 0;

int secondaMeta = 0;

int sommaTotale = 0;

public Semaforo fineArray = new Semaforo(-999);

public SommaConcorr() {

for(int i=0; i<1000; i++){

array[i]=(int)(Math.random()*100);

System.out.print(array[i] + " ");

}

SommaPrimaMeta prima = new SommaPrimaMeta();

SommaSecondaMeta seconda = new SommaSecondaMeta();

SommaTotale totale = new SommaTotale();

prima.start();

seconda.start();

totale.start();

}


SommaConcorr es = new SommaConcorr();

}

1.9 Somma concorrente degli elementi di un array 15

class Semaforo extends Thread{

private int s;

public Semaforo(int s){

this.s=s;

}


if (s<=0){

try{

wait();

}

catch (InterruptedException e){

System.out.println(e);

}

}

s--;

}


s++;

notify();

}

}

class SommaPrimaMeta extends Thread{

int i = 0;

public void run(){

while(i<500){

primaMeta = primaMeta + array[i];

fineArray.up();

i++;

}

}

}

class SommaSecondaMeta extends Thread{

int i = 500;

public void run(){

while(i<1000){

secondaMeta = secondaMeta + array[i];

fineArray.up();

i++;

}

}

}

class SommaTotale extends Thread{

boolean attesa = true;

public void run(){

while(attesa){

fineArray.down();

sommaTotale = primaMeta + secondaMeta;

1.10 Applicazione del problema dei lettori/scrittori alla sincronizzazione di un ponte 16

fineArray.up();

System.out.println("\nPrima metà: " + primaMeta);

System.out.println("Seconda metà: " + secondaMeta);

System.out.println("Somma totale: " + sommaTotale);

attesa = false;

}

}

}

}

1.10 Applicazione del problema dei lettori/scrittori alla sincroniz-zazione di un ponte

Un ponte a senso unico é attraversato da automobili in una sola direzione, e ci sono due semafori aidue punti d'accesso al ponte. Naturalmente se un semaforo é sul rosso l'altro é sul verde. In casodi mancanza di auto, dare la precedenza ad un lato del ponte a scelta del programmatore e, appenaarriva un'auto, consentirne l'attraversamento. Se c'é almeno un'auto che sta attraversando il pontein una certa direzione, il semaforo all'altro lato sará sul rosso per evitare l'attraversamento ad altreauto in direzione opposta. Sono consentite piú di una auto tutte nella stessa direzione. Quandotutte le auto sono passate e ci sono altre automobili in attesa sull'altro lato, il semaforo si inverte.Gli arrivi delle auto sono aleatori (funzione random), mentre il tempo di attraversamento é costanteper ogni auto. La singola auto viene rappresentata con un thread di java e i due semafori con duesemafori di java.

import java.util.Vector;

public class Ponte {

public static final boolean DESTRA = true;

public static final boolean SINISTRA = false;

public static final int NUMERO_AUTOMOBILI = 10;

Semaforo semaforoDestro = new Semaforo(1);

Semaforo semaforoSinistro = new Semaforo(0);

int transito = 0;

int attesaDestra = 0;

int attesaSinistra = 0;

public Ponte() {

for(int i=0; i<NUMERO_AUTOMOBILI; i++){

if((Math.random()*10)<5){

Automobile a = new Automobile(DESTRA);

a.start();

}

else{

Automobile a = new Automobile(SINISTRA);

a.start();

}

}

}

1.10 Applicazione del problema dei lettori/scrittori alla sincronizzazione di un ponte 17


Ponte es = new Ponte();

}

class Automobile extends Thread{

boolean lato;

long tempo;

public Automobile(boolean lato){

this.lato=lato;

}

public void run(){

try{

tempo = (long)(Math.random()*10*1000);

this.sleep(tempo);

if(lato==DESTRA){

System.out.println("\t\t\t\t\tArrivo a destra");

attesaDestra++;

semaforoDestro.down();

attesaDestra--;

transito++;

semaforoDestro.up();

System.out.println("\t\t\t\t\tInizio transito da destra");

this.sleep(1000);


transito--;

System.out.println("\t\t\t\t\tFine transito da destra");

if(transito==0 && attesaSinistra>0){

semaforoSinistro.up();

}

else{


}

}

else if(lato==SINISTRA){


if(transito==0&&attesaDestra==0){


}

else{


}

System.out.println("Arrivo a sinistra");

attesaSinistra++;

semaforoSinistro.down();

attesaSinistra--;

transito++;


System.out.println("Inizio transito da sinistra");

this.sleep(1000);

1.11 Il prolema dei 5 �loso� mangiatori di spaghetti 18

semaforoSinistro.down();

transito--;

System.out.println("Fine transito da sinistra");

if(transito==0){


}

else{


}

}

}

catch(InterruptedException e){


}

}

}

}

class Semaforo extends Thread{

private int s;

public Semaforo(int s){

this.s=s;

}


if (s<=0){

try{

wait();

}

catch (InterruptedException e){


}

}

s--;

}


s++;

notify();

}

1.11 Il prolema dei 5 �loso� mangiatori di spaghetti

Riprendiamo questo problema di sincronizzazione. In questo esempio si assegna un semaforo adogni forchetta.


class Semaforo {

int value;

public Semaforo()

{


value = 1;

}


{

this.value = value;

}


{

value++;

notify();

}


{

while (value<=0)

{

try

{

wait();

}


}

value--;

}

}

class Filosofo extends Thread {

Semaforo sx,dx; // semafori destro e sinistro

int numero; // numero del filosofo

public Filosofo(int numero,Semaforo sx, Semaforo dx) // costruttore

{

this.sx = sx;

this.dx = dx;


}

public void run()

{

while(true)

{

//Pensa

System.out.println("Filosofo "+numero+" pensa");

sx.down();

dx.down();

System.out.println("Filosofo "+numero+" mangia");

//mangia

sx.up();

dx.up();

}

}


}

public class main {


{

Semaforo s1 = new Semaforo(1); // inizializza semafori

Semaforo s2 = new Semaforo(1);




Filosofo f1 = new Filosofo(1,s1,s2); // inizializza filosofi

Filosofo f2 = new Filosofo(2,s2,s3);




f1.start(); // esegue thread

f2.start();

f3.start();

f4.start();

f5.start();

}

}

Questa soluzione puó andare in stallo, come si vede da questa traccia di funzionamento:

Filosofo 2 pensa Filosofo 3 pensa Filosofo 5 pensa Filosofo 4 pensa

Filosofo 4 mangia Filosofo 4 pensa Filosofo 4 mangia Filosofo 4

pensa Filosofo 2 mangia Filosofo 4 pensa Filosofo 2 pensa --STALLO--

Come ultimo esempio, riprendiamo questo problema di sincronizzazione assegnado un semaforoad ogni �losofo.


class Semaforo {

int value;

public Semaforo()

{

value = 1;

}


{

this.value = value;

}


{

value++;

notify();


}


{

while (value<=0)

{

try

{

wait();

}


}

value--;

}

}

class Dati {

char Stato[]; // array di stati

Semaforo s[]; // array di semafori

Semaforo mutex;

public Dati()

{

Stato = new char[5];

s = new Semaforo[5];

for (int i=0;i<5;i++)

s[i]= new Semaforo(); // crea semafori

mutex = new Semaforo();

}

}

class Filosofo extends Thread {

Dati dati;

int i;

public Filosofo(int i, Dati dati)

{

this.dati = dati;

this.i = i;

}

public int Sx(int i) // semaforo di sinistra

{

return i;

}

public int Dx(int i) // semaforo di destra

{

if (i==4)

return 1;

else

return (i+1);

}


public void Prendif(int i) // Cerca di prendere una forchetta

{

dati.mutex.down();

dati.Stato[i]='A'; // stato di "Affamato"

Test(i);

dati.mutex.up();

dati.s[i].down();

}

public void Rilasciaf(int i) // Rilascia la forchetta

{

dati.mutex.down();

dati.Stato[i] = 'P'; // stato di "Pensa"

Test(Sx(i));

Test(Dx(i));

dati.mutex.up();

}

public void Test (int i) // controlla se puo' prendere la forchetta

{

if (dati.Stato[i]=='A' &&

dati.Stato[Dx(i)]!='M' &&

dati.Stato[Sx(i)]!='M')

{

dati.Stato[i]='M'; // stato di "Mangia"

dati.s[i].up();

}

}

public void run()

{

while(true)

{

//Pensa

System.out.println("Filosofo "+i+" pensa");

Prendif(i);

//Mangia

System.out.println("Filosofo "+i+" mangia");

Rilasciaf(i);

}

}

}

public class main {


{

Dati dati = new Dati();

for(int i=0;i<5;i++) // inizializza stati filosofo

dati.Stato[0]='P';

Filosofo f1 = new Filosofo(0,dati); // inizializza filosofi

Filosofo f2 = new Filosofo(1,dati);





f1.start(); // esegue programma

f2.start();

f3.start();

f4.start();

f5.start();

}

}

Appunti di Sistemi Operativi Enzo Mumolo e-mail address … · 2007-10-16 · Appunti di Sistemi...

Documents

Transcript of Appunti di Sistemi Operativi Enzo Mumolo e-mail address … · 2007-10-16 · Appunti di Sistemi...