Description
Problem 1
In this problem, we will examine how different scheduling policies affect performance. The table below shows the
time when each process arrives in the ready queue and the time each process takes.
Process Arrival Time Execution Time
P1 0 12
P2 1 8
P3 3 6
P4 6 4
CSC 246
P5 10 2
P6 15 1
We will examine three different polices:
1. FIFO
2. Round Robin with time quantum = 4
3. MLFQ where 1) the i-th queue has a time quantum q=2^(i-1) (2 to the power i-1), 2) all processes start in the
first queue with i equals to 1 and move to the next queue once the time quantum in the current queue is used
up, 3) the rule to boost processes to the highest-priority queue from the lowest-priority queue will not be
applied, as the duration of the processes is short in this problem, 4) if a process in the i-th queue is running
and a process in the j-th queue (where j is less than i) becomes ready, the process in the j-th queue will run
immediately, 5) within each queue, we use FIFO, and preempted processes will not change its location in the
queue.
With round robin, it could happen that one process just arrives and enters the ready queue and another process is
preempted and returns to the ready queue. If this happens, put the preempted process behind newly arrived process
in the queue (so the newly arrived process will get to run earlier).
For polices with a time quantum, if a process finishes, regardless of whether the current quantum is used up, the
next process will be scheduled immediately.
(a) Draw a Gantt chart for each of the three different polices under the given workload. Make sure you label the
process ID and timestamp correctly.
(b) Also, for each schedule, compute average response time, average turnaround time, and average waiting time,
where the waiting time is the amount of time that is taken by a process in ready queue (being in the ready queue
means the process is not running).
Put your answers in problems.txt (ASCII file).
Problem 2
In this problem, we’re going to learn how to use Valgrind, a powerful debugging tool. Although Valgrind can detect
different types of bugs, we only focus on Helgrind, which is a part of Valgrind for data race detection.
The manual page for Helgrind contains a simple data race example and instructions on how to interpreting the race
error messages. We will try that example and check the results. The example under Section 7.4.1 is provided here
as race.c.
Compile it with “gcc -g -o race race.c -lpthread”
and then invoke Helgrind with “valgrind –tool=helgrind ./race”.
1. What is the output you get? Just copy and paste.
2. How does your output compare with the output listed on the manual page? Please also describe your
interpretation of the difference.
CSC 246
Put your answers in problems.txt (ASCII file).
Problem 3
Our goal here is to write multithreaded programs that can calculate various statistical values for a list of numbers
stored in a file, where a number takes one line in the file. The programs will be passed a file name on the command
line and will then use two different strategies.
In the first strategy, we create three worker threads. One thread will determine the sum of the numbers, the second
will determine the maximum value, and the third will determine the minimum value. Please name the source code
as prob_3_1.c and compile it to prob_3_1
In the second strategy, we again create three worker threads, but each thread now determine the sum, maximum,
and minimum values of roughly one third of numbers stored in the file. After all worker threads finish, the main
thread can determine the sum, maximum, and minimum values of all numbers stored in the file based on the results
from the worker threads. In this strategy, we want to give the three worker threads a similar amount of workload to
keep them balanced. You need to decide how you would like to divide the workload. Please name the source code
as prob_3_2.c and compile it to prob_3_2
For both strategies, the main thread should read the file and parse it, create worker threads, wait them to finish, and
finally print out the sum, maximum, and minimum values before finishing. The programs take only one parameter,
i.e., the name of a file storing numbers.
Since they are multithreaded programs, you need to be careful while testing and debugging. Make sure you reason
about all possible interleavings and use necessary synchronization operations in your code.
As always, if your code catch certain error conditions, print meaningful error messages in your own format. After
you finish, turn in your source files prob_3_1.c and prob_3_2.c, Makefile, and README.
