KDP/Lab 1 2024

Izvor: SI Wiki
Pređi na navigaciju Pređi na pretragu

Prva laboratorijska vežba 2024. godine održana je 29. i 30. aprila i nosila je 10 bodova (3 boda Moodle 7 bodova zadatak). Ukupno je bilo 4 grupe.

Ulazni test Grupa 1 i 2

1. zadatak

Ukoliko nit A pozove a(), a nit B pozove b(), šta će se desiti sa niti B? 

public class A {
	public synchronized void a() {
		//neki kod ...
	}

	public synchronized void b() {
		//neki kod..
	}

	A obj = new A();
}

Odgovor: Zaustaviće se dok se ne izvrši a()

2. zadatak

Koji od sledećeg su validni načini da se inicijalizuje nit? 

  1. Runnable r = new Runnable() {
	    public void run(){ /*neki kod*/ }
	};

  2. Runnable r = new Runnable() {
		public void run(){ /*neki kod*/}
	};
Thread t = new Thread(r);

  3. Thread t = new Thread();

  4. public class Nit extends Thread {
	public void run(){ /*neki kod*/ }
}
Nit t = new Nit();

  5. Thread t = new Thread() {
	public void run(){ /*neki kod*/ }
};

3. zadatak

Prva nit izvršava readMethod() i zaključala je readLock. Druga nit je pozvala writeMethod(). 

public class LockExample {
    private static final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();

    public void readMethod() {
        rwLock.readLock().lock();
        try {
            // Neki kod...
        } finally {
            rwLock.readLock().unlock();
        }
    }

    public void writeMethod() {
        if (!rwLock.isWriteLocked()) {
            rwLock.writeLock().lock();
            try {
                // Neki kod..
            } finally {
                rwLock.writeLock().unlock();
            }
        }
    }
}

Čemu služi parametar u konstruktoru ReentrantReadWriteLock? Odgovor: FIFO Fairness

Šta se dešava sa drugom niti? Odgovor: Blokira se na writeLock

Ulazni test Grupe 3

1. zadatak

Kada nit T uvek trajno prestaje da se izvršava?

  1. Kada nit pozove wait nad nekim objektom.
  2. Kada se završi njena run metoda.
  3. Kada pozove svoju interrupt metodu.
  4. Nijedan od ponuđenih odgovora.

2. zadatak

Koji od navedenih iskaza su tačni?

  1. ArrayBlockingQueue je pogodan za rešavanje ProducerConsumer problema.
  2. Za implementaciju ProducerConsumer problema, može se koristiti par metoda add(E e) i remove() objekta tipa BlockingQueue, bez dodatnih sinhronizacionih elemenata/direktiva.
  3. Za implementaciju ProducerConsumer problema, može se koristiti par metoda putFirst(E e) i takeLast() objekta tipa BlockingDeque, bez dodatnih sinhronizacionih elemenata/direktiva.
  4. Za implementaciju ProducerConsumer problema, može se koristiti par metoda transfer(E e) i take() objekta tipa TransferQueue, bez dodatnih sinhronizacionih elemenata/direktiva.
  5. Za implementaciju ProducerConsumer problema, može se koristiti par metoda putFirst(E e) i takeFirst() objekta tipa BlockingDeque, bez dodatnih sinhronizacionih elemenata/direktiva.

3. zadatak

Ukoliko nit threadA trenutno izvršava metodu obj.a(), a potom nit threadB poziva metodu obj.b(), koji od ponuđenih odgovora su tačni, ukoliko je dat sledeći deo koda? 


public class A {
  private ReentrantReadWriteLock rw = new ReentrantReadWriteLock(true);

  public void a() {
    try {
      rw.readLock().lock();
      // kritična sekcija A...  // <- threadA
    } finally {
      rw.readLock().unlock();
    }
  }

  public void b() {
    try {
      if (rw.getReadLockCount()==0) {
        rw.writeLock().lock();
      }
      // kritična sekcija B...
    } finally {
      rw.writeLock().unlock();
    }
  }
}

A obj = new A();
  1. Desiće se greška prilikom izvršavanja.
  2. Argument konstruktora ReentrantReadWriteLock označava da mogu dve niti istovremeno da pozivaju zaključavanje.
  3. Niti A i B mogu istovremeno da izvršavaju kritične sekcije u metodama a() i b() (respektivno).
  4. Nit B će biti blokirana dok nit A ne završi poziv metode a().
  5. Argument konstruktora ReentrantReadWriteLock označava da li će se buđenje niti obavljati po FIFO principu.
  6. Nit B neće izvršiti zaključavanje, jer uslov if-a nije ispunjen.

Ulazni test Grupe 4

1. zadatak

Koji od sledećeg su validni načini da se inicijalizuje nit? 

  1. Runnable r = new Runnable() {
	    public void run(){ /*neki kod*/ }
	};

  2. Runnable r = new Runnable() {
		public void run(){ /*neki kod*/}
	};
Thread t = new Thread(r);

  3. Thread t = new Thread();

  4. public class Nit extends Thread {
	public void run(){ /*neki kod*/ }
}
Nit t = new Nit();

  5. Thread t = new Thread() {
	public void run(){ /*neki kod*/ }
};

2. zadatak

Koji od navedenih iskaza su tačni?

  1. ArrayBlockingQueue je pogodan za rešavanje ProducerConsumer problema.
  2. Za implementaciju ProducerConsumer problema, može se koristiti par metoda add(E e) i remove() objekta tipa BlockingQueue, bez dodatnih sinhronizacionih elemenata/direktiva.
  3. Za implementaciju ProducerConsumer problema, može se koristiti par metoda putFirst(E e) i takeLast() objekta tipa BlockingDeque, bez dodatnih sinhronizacionih elemenata/direktiva.
  4. Za implementaciju ProducerConsumer problema, može se koristiti par metoda transfer(E e) i take() objekta tipa TransferQueue, bez dodatnih sinhronizacionih elemenata/direktiva.
  5. Za implementaciju ProducerConsumer problema, može se koristiti par metoda putFirst(E e) i takeFirst() objekta tipa BlockingDeque, bez dodatnih sinhronizacionih elemenata/direktiva.

3. zadatak

Kako pravilno osigurati međusobno isključivanje kritične sekcije?

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.


Postavka Svih Grupa

U zavisnosti od grupe bilo je potrebno rešiti jedan od sledećih problema:

1. Rešiti Atomic Broadcast problem koristeći AtomicInteger i opciono Semaphore . Bafer sadrži B elemenata. Potrebno je da program bude maksimalno konkurentan i otporan na prekide.

2. Rešiti H2O problem koristeći CyclicBarrier. Potrebno je da program bude maksimalno konkurentan i otporan na prekide.

3. Rešiti Dining Philosophers problem koristeći AtomicInteger i regione. filozofi koji su ranije izrazili želju za hranom treba ranije da budu opsluženi . Potrebno je da program bude maksimalno konkurentan i otporan na prekide.

4. Rešiti Child Care problem koristeći ConcurrentLinkedQueue i druge proizvoljne sinhronizacione direktive. Roditelj dovodi jedno ili više dece u obdanište i čeka sve dok se ne pojavi mesto, kako bi ostavio svu decu odjednom i otišao. Roditelj može i da odvede jedno ili više dece, takođe odjednom. Mora se poštovati redosled dolaska roditelja koji ostavljaju decu i vaspitačica koje odlaze sa posla. Potrebno je da program bude maksimalno konkurentan i otporan na prekide.

Rešenje za Atomic Broadcast

Test.java

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Test {

	private static final int consumersCount=3;
	private static final int b=5;


	public static void main(String[] args) {

		AtomicInteger[][] reads = new AtomicInteger[b][consumersCount];

		Semaphore mutex = new Semaphore(1);

		AtomicInteger[] buffer = new AtomicInteger[b];

		for (int i = 0; i < buffer.length; i++)
			buffer[i] = new AtomicInteger(0);

		Consumer[] consumers = new Consumer[consumersCount];

		Producer p = new Producer(consumersCount, buffer, reads,b,mutex);
		p.start();

		for (int i = 0; i < b; i++)
			for(int j=0;j<consumersCount;j++)
				reads[i][j] = new AtomicInteger(1);

		for (int i = 0; i < consumersCount; i++) {
			consumers[i] = new Consumer(buffer, reads,b,mutex,i);
			consumers[i].start();
		}
	}

}

Producer.java

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Producer extends Thread {

	private final int consumers;
	private AtomicInteger[] buffer;
	private AtomicInteger[][] reads;
	private Semaphore mutex;
	private int b;

	public Producer(int consumers, AtomicInteger[] buffer, AtomicInteger[][] reads, int bb, Semaphore mutex) {
		this.consumers = consumers;
		this.buffer = buffer;
		this.reads = reads;
		b=bb;
		this.mutex = mutex;
	}

	@Override
	public void run() {
		for (int i = 0; i <b; i++) {
			for (int j = 0; j < consumers; j++)
				while(reads[i][j].get() == 0)
					Thread.onSpinWait();

			int rand = (int)(Math.random() * 10);
			System.out.println("Producer produced element: " + rand );
			mutex.acquireUninterruptibly();
			buffer[i].set(rand);
			mutex.release();

			mutex.acquireUninterruptibly();
			for (int j2 = 0; j2 < consumers; j2++)
				reads[i][j2].set(0);

			mutex.release();
		}
	}

}

Consumer.java

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Consumer extends Thread {

	private int id;
	private AtomicInteger[][] reads;
	private AtomicInteger[] buffer;
	private Semaphore mutex;
	private int b;

	public Consumer(AtomicInteger[] buff, AtomicInteger[][] r, int bb,Semaphore mutex, int i) {
		buffer = buff;
		reads=r;
		id=i;
		this.mutex = mutex;
		b=bb;
	}

	@Override
	public void run() {
		for (int i = 0; i < b; i++) {
			while(reads[i][id].get() == 1)
				Thread.onSpinWait();
			mutex.acquireUninterruptibly();
			int elem = buffer[i].get();
			System.out.println("Consumer "+id+" consumed element "+elem +"from place "+i);
			reads[i][id].set(1);
			mutex.release();

			try {
				sleep((int)(Math.random()*2000));
			} catch (InterruptedException e) {
				throw new RuntimeException(e);
			}

		}
	}

}

Rešenje za H2O

Test.java

package H20;

import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;

public class Test {
	public static void main(String[] args) {
		int cnt = 10;
		
		Barrier barrier = new Barrier(new CyclicBarrier(3));
		
		Hydrogen[] h = new Hydrogen[cnt*2];
		Oxygen[] o = new Oxygen[cnt];
		
		for(int i = 0; i < cnt; i++) {
			o[i] = new Oxygen(barrier);
			h[2*i] = new Hydrogen(barrier);	
			h[2*i + 1] = new Hydrogen(barrier);	
			
			o[i].start();
			h[2*i].start();
			h[2*i+1].start();
		}
		
	}
}

Oxygen.java

package H20;

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.Semaphore;

public class Oxygen extends Thread {
	
	Barrier barrier;
	
	Oxygen(Barrier b){
		barrier = b;
	}
	
	@Override
	public void run() {
		while(true) {
			try {
				Thread.sleep((int)(Math.random() * 4000));
			} catch (InterruptedException e) {}
			
			
			barrier.oxygen.acquireUninterruptibly();

			barrier.oCount++;
			
			try {
				System.out.println("Kiseonik pristigao na barijeru");
				
				if(barrier.barrier.await() == 0) {
					System.out.println("\nFORMIRANJE VODE!\n");
					
					barrier.hCount = 0;
					barrier.oCount = 1;
					
					barrier.hydrogen.release(2);
					barrier.oxygen.release(1);
				}
				
			} catch (InterruptedException | BrokenBarrierException e) {
				e.printStackTrace();
			}
			
		}
	}

}

Hydrogen.java

package H20;

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.Semaphore;

public class Hydrogen extends Thread {
	
	Barrier barrier;
	
	Hydrogen(Barrier b){
		barrier = b;
	}
	
	@Override
	public void run() {
		while(true) {
			try {
				Thread.sleep((int)(Math.random() * 4000));
			} catch (InterruptedException e) {}
			
			barrier.hydrogen.acquireUninterruptibly();

			barrier.hCount++;
			
			try {
				System.out.println("Vodonik pristigao na barijeru");
				
				if(barrier.barrier.await() == 0) {
					System.out.println("\nFORMIRANJE VODE!\n");
					barrier.hCount = 0;
					barrier.oCount = 1;
					
					barrier.hydrogen.release(2);
					barrier.oxygen.release(1);
				}
				
			} catch (InterruptedException | BrokenBarrierException e) {
				e.printStackTrace();
			}
			
		}
	}
}

Barrier.java

package H20;

import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.Semaphore;

public class Barrier {
	CyclicBarrier barrier;
	Semaphore hydrogen, oxygen;
	int hCount, oCount;
	
	Barrier(CyclicBarrier cb){
		barrier = cb;
		hCount = 0;
		oCount = 0;
		hydrogen = new Semaphore(2);
		oxygen = new Semaphore(1);
	}
	
}

Rešenje za Dining Philosophers

Test.java

package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Test {

	public static final int N = 5;

	public static void main(String[] args) {

		Philosopher[] philosophers = new Philosopher[N];
		AtomicInteger[] forks = new AtomicInteger[N];

		for (int i = 0; i < forks.length; i++)
			forks[i] = new AtomicInteger(1);

		Table table = new Table();

		for (int i = 0; i < N; i++) {
			philosophers[i] = new Philosopher(forks, i, N, table);
			philosophers[i].start();
		}

	}

}

Table.java

package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Table {

	AtomicInteger ticket;
	int next;

	public Table() {
		ticket = new AtomicInteger(0);
		next = 0;
	}

}

Philosopher.java

package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Philosopher extends Thread {

	AtomicInteger[] forks;
	int id,left,right,N,myTicket;
	Table t;


	public Philosopher(AtomicInteger[] forks, int id, int n,Table table) {
		this.forks = forks;
		this.id = id;
		N = n;
		left = id;
		right = (id+1)%n;
		t = table;
	}

	@Override
	public void run() {
		while(true) {
			int choice = (int)(Math.random() * 2);

			switch (choice) {
			case 0: {
				eat();
				break;
			}
			case 1:{
				think();
				break;
			}
			default:
				throw new IllegalArgumentException("Unexpected value: " + choice);
			}
		}
	}


	public void think() {
		System.out.println("Philosopher "+id+" thinking");
		try {
			sleep((int)(Math.random() * 3000));
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}



	public void eat() {
		myTicket = t.ticket.getAndIncrement();
		synchronized (forks) {

			System.out.println("Philosopher "+id+" wants to eat");

			while(forks[left].intValue() == 0 || forks[right].intValue() == 0 || myTicket != t.next)
				try {
					forks.wait();
				} catch (InterruptedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			System.out.println("Philosopher "+id+" started eating");
			t.next++;
			forks[left].set(0);
			forks[right].set(0);

		}

		try {
			sleep((int)(Math.random() * 2000));
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		synchronized (forks) {

			System.out.println("Philosopher "+id+" finished eating");
			forks[left].set(1);
			forks[right].set(1);
			forks.notifyAll();
		}
	}
}

Rešenje za Child Care

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Preuzeto iz „https://siwiki.rs/w/index.php?title=КДП/Лаб_1_2024&oldid=7623”