Concurrency and Synchronization Solution

    • Objectives

Process synchronization and coordination is a central topic in Operating Systems. In running concurrent process, a major problem could occur: race condition. The use of sempahores, locks, conditions, and other constructs can help to synchronize concurrent processes and avoid such problems. This assignment is two-fold. The rst part covers a solution to a variant of a classical problem in synchronization | the dining philosophers problem. In the second part, the objective is to solve a particular problem using di erent number of threads and to gain some insights about the performance of multithreading with increased number of threads.

    • Part 1 - Variant of Dining Philosophers with Waiter

The dining-philosophers problem is a classical problem in synchronization. It represents a large class of concurrenceny problems where a limited number of resources need to be allocated to a certain number of processes without deadlock nor starvation.

For simplicity, we consider ve philosophers each sitting on a chair around a circular table. These philosophers spent their life only thinking and eating. The scenario is that a bowl of spaghetti/rice is placed in the middle of the table, a plate is given to each philosophers but only ve single chopsticks are placed between these plates. Typically the philosophers spend their time thinking without interaction with others around the table. When a philosopher becomes hungry, s/he tries to pick up the two chopsticks that are closest (left and right) one at a time. When the hungry philosopher manages to pick up two chopsticks, s/he can eat without releasing the chopsticks. Only when s/he nished eating to begin thinking, s/he will put the chopsticks back on the table. A typical solution

1


to this problem was discussed in class but it does not avoid deadlock. One solution in the literature is the Waiter Solution.





















This provides a simple way to solve the Dining Philosophers problem, assuming an external entity called the waiter taking into account the following:

    1. No chopsticks are placed on the table. Instead, a philosopher should request each of the two chopsticks from a waiter.

    2. For convenience, we assume that all philosophers request their left chopstick rst, then their right chopstick.

    3. The waiter always provides chopsticks upon request unless only one chopstick remains unused. In that case, the waiter honors the request only if a right chopstick is requested; requests for a left chopstick are deferred until another philosopher nishes eating.

2.1    Variant of the Waiter solution

In this part you need to implement a monitor solution to the waiter approach of the dinning philosophers problem using semaphores. You need to consider the following in your implementation:

    1. Suppose that we have 5 philosophers.

    2. Assume that the waiter has n chopsticks where n takes an integer value from 5 to 10. Your program should take this value n as input.



2


    3. Use a random number between 1 and 5 to select which philosopher changes its state from Thinking to Hungry. You may assume that the eating time for each philosopher is xed to 5 seconds.

    4. You can avoid starvation by not allowing a philosopher to eat again before all the other philosophers had their turn to eat.

    5. Once every philosopher has eaten 3 times, your program should report the average amount of time that the philosophers had to wait to begin eating after becoming hungry.

In addition to your implementation’s code, you should provide a brief report that shows the averages’ times that philosophers spent waiting to eat after becoming hungry in 25 runs of your program, ve runs for each value of n from 5 to 10. (Your report should include all of those 25 averages).

    • Part 2 - Composite Numbers & Mutli-threading

In multithreading, multiple components of a program could be executed at the same time. These components are known as threads and are lightweight processes available within the process. So multithreading leads to maximum utilization of the CPU by multitasking. In this part you will apply multithreading on the problem of nding composite numbers and compare the performance of your solution using various number of threads.

A composite number1 c is a number that has more than two factors, including 1 and c. For example, 12 is a composite number because it can be divided by 1; 2; 3; 4; 6 and 12. So, the number 12 has 6 factors. One way to nd if a number is a composite is to check if it can be divided by 2; 3; 5; 7; 11; and 13. If it is even, we can start with division by 2, and if the number ends with 0 or 5, we can divide by 5.

In this part you need to do the following:

    1. Write a program that reads a set of integers and determine how many of the input numbers are composite numbers.

    2. Rewrite your program to using multi-threading. To do so you need to do the following:

        (a) Assume that your program uses n threads.

        (b) Distribute the work involved as equally as possible among these n threads.

        (c) Structure your program to read the number of threads as an optional parameter on a command line. For instance, if you program is Mycomposite, then you can run it with n threads using: Mycomposite -n


1The number 1 is not considered as composite number.


3


    (d) Run your program with di erent values of n = 1; 2; 4; 8; 16 and measure the turnaround time for each these values. For the timing involved, you can use the time command on linux shell.

time    ./MyComposite

    3. Make sure that the range of numbers you use in the above is big enough for multi-threading e ects to be observable.

    4. Provide a brief performance report showing the time against the number of threads used, and comment on the expected computation time vs the usage of multiple threads.

    • To Submit

You need to submit source les, executables, along with a Make le that will be used to compile and link your shell. You also need to submit a PDF detailing your report for both Part 1 and Part 2. Please include the reports in a single PDF. These les and reports should be combined into a tar le that will unpack the les into a directory whose name is your user-id, followed by your surname. The tar le will be submitted on the D2L page of the course.

    • Grades

This assignment will carry 25% (15+10).

    • Deadline

March 30, 2022 before 11:55 P.M. Late submission is subject to the regular penalty of 20% for every day or part of the day.
















4