КДП/Лаб 1 2024

Извор: SI Wiki
< КДП
Датум измене: 3. мај 2024. у 12:39; аутор: DjoleRkc (разговор | доприноси) (→‎Решење за Dining Philosophers)
(разл) ← Старија измена | Тренутна верзија (разл) | Новија измена → (разл)
Пређи на навигацију Пређи на претрагу

Прва лабораторијска вежба 2024. године одржана је 29. i 30. априла и носила је 10 бодова (3 бода Moodle 7 бодова задатак). Укупно је било 4 групе.

Улазни тест Група 1 и 2

1. задатак

Уколико нит А позове a(), а нит Б позове b(), шта ће се десити са нити Б? 

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

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

	A obj = new A();
}

Одговор: Зауставиће се док се не изврши a()

2. задатак

Који од следећег су валидни начини да се иницијализује нит? 

  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. задатак

Прва нит извршава readMethod() и закључала је readLock. Друга нит је позвала 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();
            }
        }
    }
}

Чему служи параметар у конструктору ReentrantReadWriteLock? Одговор: FIFO Fairness

Шта се дешава са другом нити? Одговор: Блокира се на writeLock

Улазни тест Групe 3

1. задатак

Када нит T увек трајно престаје да се извршава?

  1. Када нит позове wait над неким објектом.
  2. Када се заврши њена run метода.
  3. Када позове своју interrupt методу.
  4. Ниједан од понуђених одговора.

2. задатак

Који од наведених исказа су тачни?

  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. задатак

Уколико нит threadA тренутно извршава методу обј.а(), а потом нит threadB позива методу обј.б(), који од понуђених одговора су тачни, уколико је дат следећи део кода? 


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. Десиће се грешка приликом извршавања.
  2. Аргумент конструктора ReentrantReadWriteLock означава да могу две нити истовремено да позивају закључавање.
  3. Нити А и Б могу истовремено да извршавају критичне секције у методама a() и b() (респективно).
  4. Нит Б ће бити блокирана док нит А не заврши позив методе a().
  5. Аргумент конструктора ReentrantReadWriteLock означава да ли ће се буђење нити обављати по FIFO принципу.
  6. Нит Б неће извршити закључавање, јер услов if-a није испуњен.

Улазни тест Групe 4

1. задатак

Који од следећег су валидни начини да се иницијализује нит? 

  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. задатак

Који од наведених исказа су тачни?

  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. задатак

Како правилно осигурати међусобно искључивање критичне секције?

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.


Поставка Свих Група

У зависности од групе било је потребно решити један од следећих проблема:

1. Решити Atomic Broadcast проблем користећи AtomicInteger и опционо Semaphore . Бафер садржи B елемената. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

2. Решити H2O проблем користећи CyclicBarrier. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

3. Решити Dining Philosophers проблем користећи AtomicInteger и регионе. филозофи који су раније изразили жељу за храном треба раније да буду опслужени . Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

4. Решити Child Care проблем користећи ConcurrentLinkedQueue и друге произвољне синхронизационе директиве. Родитељ доводи једно или више деце у обданиште и чека све док се не појави место, како би оставио сву децу одједном и отишао. Родитељ може и да одведе једно или више деце, такође одједном. Мора се поштовати редослед доласка родитеља који остављају децу и васпитачица које одлазе са посла. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

Решење за 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);
			}

		}
	}

}

Решење за 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);
	}
	
}

Решење за 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();
		}
	}
}

Решење за Child Care

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Преузето из „https://siwiki.rs/w/index.php?title=КДП/Лаб_1_2024&oldid=7623”