In: Computer Science
Choose only one problem:
1- Write a multithreaded program that calculates various statistical values for a list of numbers. This program will be passed a series of numbers on the command line and will then create three separate worker threads. One thread will determine the average of the numbers, the second will determine the minimum value, and the third will determine the maximum value. The variables representing the average, minimum, and maximum values will be stored globally. The worker threads will set these values, and the parent thread will output the values once the workers have exited.
2- Write a program to solve the dining philosophers problem. Dining philosophers is a classic synchronization problem. Five silent philosophers sit around a table with a bowl of rice. A chopstick is placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat. Eating is not limited by the amount of rice left: assume an infinite supply. However, a philosopher can only eat while holding both the chopstick to the left and the chopstick to the right. Each philosopher can pick up an adjacent chopstick, when available, and put it down when holding it. These are separate actions: chopsticks must be picked up and put down one by one. The problem is how to design a discipline of behavior such that each philosopher won't starve, i.e. can forever continue to alternate between eating and thinking.
Dining Philosophers problem:
As stated in the question,Dining philosophers is a classic synchronization problem.
Here P1,P2,P3,P4,P5 are the philosophers sitting around the table with a bowl of rice in the centre.The blue lines indicated the chopsticks.At any instant, a philosopher is either eating or thinking. When a philosopher wants to eat, he uses two chopsticks - one from their left and one from their right. When a philosopher wants to think, he keeps down both chopsticks at their original place.
From the qusetion , it is clear that a philosopher can think for an indefinite amount of time. But when a philosopher starts eating, he has to stop at some point of time. The philosopher is in an endless cycle of thinking and eating.
Solution:
When one philosopher wants to eat the rice, he waits for the chopstick at his left and picks up that chopstick. He then waits for the right chopstick to be available, and then picks it up. After eating, he puts both the chopsticks down. But if all five philosophers are hungry at the same time, and each of them picks up one chopstick causing a deadlock situation as they are waiting for another chopstick forever.
Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
A solution of the Dining Philosophers Problem is to use a semaphore to represent a chopstick. A chopstick can be picked up by executing a wait operation on the semaphore and released by executing a signal semaphore.
Semaphore is simply a variable that is non-negative and shared between threads. A semaphore is a signaling mechanism, and a thread that is waiting on a semaphore can be signaled by another thread.A thread is a small set of instructions designed to be scheduled and executed by the CPU independently of the parent process.
Using these concepts,the program has been coded here in java:
</>
import java.util.concurrent.Semaphore;
import java.util.concurrent.ThreadLocalRandom;
public class Main {
static int philosopher = 5;
static philosopher philosophers[] = new
philosopher[philosopher];
static chopstick chopsticks[] = new chopstick[philosopher];
static class chopstick {
public Semaphore mutex = new Semaphore(1);
void grab() {
try {
mutex.acquire();
}
catch (Exception e) {
e.printStackTrace(System.out);
}
}
void release() {
mutex.release();
}
boolean isFree() {
return mutex.availablePermits() > 0;
}
}
static class philosopher extends Thread {
public int number;
public chopstick leftchopstick;
public chopstick rightchopstick;
philosopher(int num, chopstick left, chopstick right) {
number = num;
leftchopstick = left;
rightchopstick = right;
}
public void run(){
while (true) {
leftchopstick.grab();
System.out.println("philosopher " + (number+1) + " grabs left
chopstick.");
rightchopstick.grab();
System.out.println("philosopher " + (number+1) + " grabs right
chopstick.");
eat();
leftchopstick.release();
System.out.println("philosopher " + (number+1) + " releases left
chopstick.");
rightchopstick.release();
System.out.println("philosopher " + (number+1) + " releases right
chopstick.");
}
}
void eat() {
try {
int sleepTime = ThreadLocalRandom.current().nextInt(0, 1000);
System.out.println("philosopher " + (number+1) + " eats for " +
sleepTime);
Thread.sleep(sleepTime);
}
catch (Exception e) {
e.printStackTrace(System.out);
}
}
}
public static void main(String argv[]) {
for (int i = 0; i < philosopher; i++) {
chopsticks[i] = new chopstick();
}
for (int i = 0; i < philosopher; i++) {
philosophers[i] = new philosopher(i, chopsticks[i], chopsticks[(i +
1) % philosopher]);
philosophers[i].start();
}
while (true) {
try {
// sleep 1 sec
Thread.sleep(1000);
// check for deadlock
boolean deadlock = true;
for (chopstick f : chopsticks) {
if (f.isFree()) {
deadlock = false;
break;
}
}
if (deadlock) {
Thread.sleep(1000);
System.out.println("Everyone Eats");
break;
}
}
catch (Exception e) {
e.printStackTrace(System.out);
}
}
System.out.println("Exit The Program!");
System.exit(0);
}
}
output:
philosopher 1 grabs left chopstick. philosopher 2 grabs left chopstick. philosopher 2 grabs right chopstick. philosopher 2 eats for 385 philosopher 4 grabs left chopstick. philosopher 4 grabs right chopstick. philosopher 4 eats for 269 philosopher 4 releases left chopstick. philosopher 4 releases right chopstick. philosopher 4 grabs left chopstick. philosopher 5 grabs left chopstick. philosopher 2 releases left chopstick. philosopher 1 grabs right chopstick. philosopher 3 grabs left chopstick. philosopher 2 releases right chopstick. philosopher 1 eats for 878 philosopher 1 releases left chopstick. philosopher 1 releases right chopstick. philosopher 2 grabs left chopstick. philosopher 1 grabs left chopstick. Everyone Eats Exit The Program!