Instructions:
MSc Software Workshop (30382)
Assignment 1 (Spring 2020)
Weight: 1.5%, Total Marks: 100
Submission deadline: Check canvas
This worksheet will be assessed in a viva. Skipping viva will lead to zero marks.
Furthermore note that we will not provide JUnit tests for this worksheet. However you should submit such tests for those parts of your programs that can be tested with JUnit
tests.
Youshouldfollowthestrictnamingconventionfortheconstructors,getters,andsetters.
Javadoc and other Java comments are mandatory. Absence of any documentation will
lead to penalty.
Late submission also lead of a penalty of 5% marks.
You should only submit the .java files for the following questions. Please strictly follow
the name convention for methods.
Submission is by submitting a single zip file. E.g., aaa111-WS2-1.zip (assuming
aaa111 is your login name).
Q1. [Threads] [Difficulty: Medium] [Marks: 40]
The method countPrimes given in the class CountPrimes counts the quantity of prime numbers1 in a given range of integers and returns them (source code given). An execution of this program (MyProgram.java) is given below:
Write a multi-threaded version of this program that should be able to speed up this calculation by utilizing available CPU cores on your computer. For example, running a multi-threaded version of the same program can yield the following output:
Counting primes between 3000001 and 6000000 196033 primes found so far.
Total elapsed time: 2.372 seconds.
Counting primes between 3000001 and 6000000 using 8 threads…
Thread1: 25051 primes found so far. Thread2: 49901 primes found so far. Thread3: 74574 primes found so far. Thread4: 99132 primes found so far. Thread5: 123507 primes found so far. Thread6: 147869 primes found so far. Thread7: 171976 primes found so far.
1 https://en.wikipedia.org/wiki/Prime_number
Page 1 of 3
Thread8: 196033 primes found so far.
The number of primes is 196033.
Total elapsed time: 0.42 seconds.
Create another class CountPrimesThread that is based on CountPrimes and utilized threads.
Write a method countPrimesWithThreads(int numberOfThreads) inside MyProgram.java which accepts a parameter representing the number of processors in a computer and then create threads based upon that number. It will do so by dividing the work up among several threads. Each thread will be assigned a part of the full range of integers, and it will count the primes in its assigned part. At the end of its computation, the thread has to add its count to the overall total of primes in the entire range. The variable that represents the total is shared by all the threads, since each thread has to add a number to the total.
At the end compare the time taken by both algorithms (threaded vs non-threaded)
Hint: Runtime.getRuntime().availableProcessors();
Q2. [Network & Sockets] [Difficulty: Easy] [Marks: 20]
Create a very basic messaging program in which a client and server program can talk to each other. The user on the client end types a message, and it is transmitted to the server, which displays it to the user on that end. Then the user of the server types a message that is transmitted to the client. Then the client user types another message, and so on. This continues until one user or the other enters “quit” when prompted for a message. When that happens, the connection is closed and both programs terminate. Write two classes ChatServer and ChatClient for this purpose.
Q3. [Threads] [Difficulty: Medium] [Marks: 40]
Dining philosophers problem: Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available but cannot start eating before getting both forks. The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.
Page 2 of 3
A simple implementation implementing Dining philosophers problem is given with the handout (Q3) and produces following output:
Philosopher 1 grabbed fork forkA
Philosopher 1 grabbed fork forkB
Philosopher 5 grabbed fork forkA
Philosopher 4 grabbed fork forkD
Philosopher 4 grabbed fork forkE
Philosopher 4 eat
Philosopher 2 grabbed fork forkB
Philosopher 3 grabbed fork forkC
…
This implementation is not correct since Philosopher 5 should not able to grab forkA since it is already grabbed by Philosopher 1. Furthermore, there can be deadlock if every philosopher pick one fork each.
Provide a deadlock free implementation of Dinning Philosopher problem. Provide an updated code along with explanation about why the problem occurred previously and how you solved it?
Page 3 of 3