[monitor] scheduler

Si deve realizzare uno scheduler che bilancia l’uso della CPU in modo equo. Ci sono N_THREAD thread che si comportano secondo il seguente schema:

while {

    // Thread 'id' chiede la CPU per un tempo time
    s.getCPU(id,time);

    // usa la CPU:
    //tra le due chiamate allo scheduler s solo questo thread è in esecuzione

    // rilascia la CPU
    s.releaseCPU();

}

I thread, identificati da ‘id’, chiedono la CPU per un tempo ‘time’. Lo scheduler s dà la CPU a uno solo thread: gli altri restano in attesa. Quando il thread ha concluso invoca s.releaseCPU() e lo scheduler libera il thread successivo.

L’assegnazione della CPU deve avvenire secondo un criterio di equità: il thread che ha usato meno la CPU fino a questo momento viene schedulato. (Se ci sono più thread candidati per lo scheduling ne viene eseguito uno arbitrario).

L’interfaccia permette di vedere la progressione dei thread. Vengono eseguiti alcuni test automatici sulla concorrenza e sull’equità che si possono disabilitare con la checkbox.

Screenshot from 2013-04-11 10:14:27

Realizzare il monitor Scheduler che implementi in modo corretto i metodi getCPU e releaseCPU. Il costruttore della classe Scheduler prende come parametro il numero di thread N_THREAD. Utilizzare il seguente test:

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Balancer{
    static JFrame frmMain;
    static Container pane;
    static JButton btnDo;
    static final int N_THREADS=5; // Numero di Thread che verranno eseguiti
    static JProgressBar[] bar = new JProgressBar[N_THREADS];
    static Scheduler s ; // Lo scheduler
    static JCheckBox testCheck;

    public static void main (String[] args){ //Main void
        int i,j;

        // Crea le componenti della GUI
        try {UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());}
        catch (Exception e) {}
        frmMain = new JFrame("Load balancer");
        frmMain.setSize(300, 80+25*N_THREADS); //Window size 300x100 pixels
        pane = frmMain.getContentPane();
        pane.setLayout(null); //Use the null layout
        frmMain.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); //Exit when X is clicked
        btnDo = new JButton("Go!");
        for (i=0;i<N_THREADS;i++) {
            bar[i] = new JProgressBar(0, 100); //Min value: 0 Max value: 100
            bar[i].setBounds(10, 10+25*i, 280, 20);
            pane.add(bar[i]);
        }
        pane.add(btnDo);
        btnDo.setBounds(100, 10+25*N_THREADS, 100, 25);
        testCheck = new JCheckBox("Test");
        testCheck.setMnemonic(KeyEvent.VK_C);
        testCheck.setSelected(true);
        testCheck.setBounds(10, 10+25*N_THREADS, 100, 25);
        pane.add(testCheck);
        frmMain.setResizable(false);
        frmMain.setVisible(true);
        btnDo.addActionListener(new btnDoAction());
    }

    // Azione collegata alla pressione del pulsante
    public static class btnDoAction implements ActionListener{
        public void actionPerformed (ActionEvent e){
            MyThread[] t = new MyThread[N_THREADS];
            int i;

            // non parte se già attivi
            synchronized(this) {
                if (!btnDo.isEnabled())
                    return;
                btnDo.setEnabled(false);
            }

            s = new Scheduler(N_THREADS); // crea il monitor
            for (i=0;i<N_THREADS;i++) // azzera le progress bar
                bar[i].setValue(0);

            // crea e lancia i thread
            for (i=0;i<N_THREADS;i++) {
                t[i] = new MyThread(s,i);
                t[i].start();
            }

            // attende la terminazione
            new CloseThread(t).start();
        }
    }

    // Il codice dei thread
    public static class MyThread extends Thread{
        Scheduler s;    // lo scheduler (monitor) comune
        int id;         // l'id dei thread
        public MyThread(Scheduler s, int id) {
            this.s = s;
            this.id = id;
        }
        public void run(){
            int time;   // tempo di esecuzione
            int i, tmp[] = new int[N_THREADS]; // array per i test

            System.out.println("Thread " + id + " started!");

            while (bar[id].getValue() < 100) {
                time = (int)(5*Math.random());
                try {

                    /**** id chiede la CPU per un tempo time ****/
                    s.getCPU(id,time);

                } catch (InterruptedException e) {};

                for (i=0;i<N_THREADS;i++)
                    tmp[i] = bar[i].getValue();

                try {
                    sleep(time*50);
                } catch (InterruptedException e) {};

                if (testCheck.isSelected() ) {
                    for (i=0;i<N_THREADS;i++) {
                        if (tmp[i] != bar[i].getValue()) {
                            System.out.println("I Thread " + i + " e " +id + " si muovono assieme!");
                            System.exit(1);
                        }
                        if (bar[i].getValue() < bar[id].getValue()) {
                            System.out.println("Il Thread " + i + " era più indietro del thread " + id + "! Errore bilanciamento!");
                            System.exit(1);
                        }
                    }
                }

                bar[id].setValue(bar[id].getValue() + time);
                bar[id].repaint();

                /**** rilascia la CPU ****/
                s.releaseCPU();
            }
            System.out.println("Thread " + id + " terminated!");

        }
    }

    // thread che attende la terminazione
    public static class CloseThread extends Thread{
        MyThread[] t;
        public CloseThread (MyThread[] t) {
            this.t = t;
        }

        public void run() {
            int i;

            // attende la terminazione
            for (i=0;i<N_THREADS;i++) {
                try {
                    t[i].join();
                } catch (InterruptedException ei) {}
            }

            // attiva di nuovo il bottone
            btnDo.setEnabled(true);

        }
    }
}
Visualizza la soluzione

/*
 * La verifica consiste nell'implementazione di uno scheduler semplificato
 * per una CPU single core. In particolare, lo scheduler deve:
 * - impedire l'assegnazione contemporanea della CPU a più thread;
 * - implementare un criterio di equità secondo il quale la CPU viene
 *   assegnata al thread che l'ha utilizzata per meno tempo.
 * Per implementare queste funzionalità, il monitor memorizza le seguenti
 * informazioni:
 * - un vettore di interi 'tempi' che tiene traccia del tempo di CPU usato
 *   da ciascun thread;
 * - una variabile booleana 'cpu_occupata' che tiene traccia del fatto che
 *   la CPU sia in uso da un thread o meno.
 */
public class Scheduler {
	private int[] tempi;
	private boolean cpu_occupata;

	public Scheduler(int N_THREADS) {
		/* Inizialmente nessun thread ha usato la CPU. Da specifica del
		 * linguaggio Java, le celle degli array sono già inizializzate
		 * a zero. */
		tempi = new int[N_THREADS];
		/* Inizialmente la CPU non è in uso. */
		cpu_occupata = false;
	}

	/* Calcola l'id del thread che ha usato per meno tempo la CPU. Non
	 * è necessario dichiarare il metodo synchronized perché viene usato
	 * solamente all'interno del metodo 'getCPU' che lo è già. Dichiararlo
	 * comunque synchronized non è un errore. */
	private int nextThread() {
		int next = 0;

		for (int i = 1; i < tempi.length; i++) {
			if (tempi[next] > tempi[i]) {
				next = i;
			}
		}
		return next;
	}

	public synchronized void getCPU(int id, int time) throws InterruptedException {
		/* Attendi se la CPU è già in uso da un altro thread o, nel caso non
		 * lo sia, se non sono il thread che l'ha usata per meno tempo. */
		while (cpu_occupata || id != nextThread()) {
			wait();
		}
		/* Ora la CPU è occupata. */
		cpu_occupata = true;
		/* Incrementa il tempo di CPU usato dal thread. */
		tempi[id] += time;
	}

	public synchronized void releaseCPU() {
		/* Rilascia la CPU. */ 
		cpu_occupata = false;
		/* Notifica il rilascio agli altri thread, in modo che quello che l'ha
		 * utilizzata per meno tempo ora possa acquisirla. */
		notifyAll();
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.