CSCI 3120 Assignment 3

Due date: 11:59pm, Sunday, July 9, 2023, submitted via Git

Objectives
This assignment has several objectives: (i) to provide an opportunity to write a multithreaded program;
(ii) to reinforce your understanding of locks, critical sections, and process synchronization; and (iii) to pro-
vide additional practice in C programming and understanding specifications.

Preparation:
1. Complete Assignment 0 or ensure that the tools you would need to complete it are installed.
2. Review the Assignment 1 and 2 specifications. Assignment 3 builds on Assignment 2.
3. Complete Assignment 2 and/or review the provided solution to Assignment 2.
4. Clone your assignment repository:
https://git.cs.dal.ca/courses/2023-summer/csci-3120/assignment-3/????.git
where ???? is your CSID.
5. Copy either your own solution or the provided solution as a starting point for Assignment 3 because
Assignment 3 builds on Assignment 2. A solution will be accessible on June 17 from Brightspace.
6. Important: If you are using CLion with CMake you will need to modify your CMakeLists.txt file by
adding the following bolded statements:
cmake_minimum_required(VERSION 3.18)
project(prosim C)

set(CMAKE_C_STANDARD 99)
set(THREADS_PREFER_PTHREAD_FLAG ON)

add_executable(prosim main.c)
find_package(Threads REQUIRED)
target_link_libraries(prosim PRIVATE Threads::Threads)

The repository has the same structure and caveats as Assignment 1 and Assignment 2.

Background1
Systems today consist of multiple cores, multiple processors, and even multiple nodes (think of a data
center). A node is a self-contained computing server that is managed by its own OS but, collaborates with
other nodes to perform a computation. We would like to simulate a multi-node system. One important
feature of multi-node systems is that each node has its own clock, which are not necessarily synchronized
and run at slightly different speeds. We use a multithreaded simulator to simulate a multi-node system.

Problem Statement
Extend your program from Assignment 2 (or the provided solution) to make your simulator multithreaded
so that it spawns multiple threads, one for each node. Your program will read in a process description and
output the states of the processes as the simulation runs. After the simulation, output the amount of time
each process spent running, blocked, and waiting. Each process will be assigned a node to run on and will
run concurrently with other processes on other nodes.

1
This background description assumes that you have read and understood the background for Assignment 1 and 2.
Please see the Problem Statement in Assignment 1 and Assignment 2, for a process description specifica-
tion.

Your program must do the following:

1. Load process descriptions in the same manner as in Assignment 2.
2. Create threads, one per node to be simulated.
3. Admit the processes on their assigned nodes.
4. Simulate the processes on each node, outputting the process’ state changes, like Assignment 2.
5. When a process enters the finished state, it is added to an ordered list.
6. Once all the processes finish, a summary of the processes is outputted (like Assignment 2), in the
order that they have completed.

Input
Your program will read its input from stdin. The input is a process description, like Assignment 2, with the
following differences: First, the first line of the process description contains three integers instead of two,
specifying the number of processes, NumProcs, to simulate; the quantum length, Quantum, in clock ticks
of the simulated system; and the number of nodes to simulate, NumNodes. I.e.,
NumProcs Quantum NumNodes
where, NumNodes is a positive integer. Second, the first line of each program description in the process
description has an additional integer:
Name Size Priority Node
where, Name, Size, and Priority are the same as in Assignment 2, and Node specifies the node on which
this process is to run. Note: 1 ≤ Node ≤ NumNodes.

Processing
The process descriptions can be loaded in the same manner as in Assignment 2, after the format changes
(described above) are implemented. It is recommended that the processed be loaded into a shared array
for easy access by the threads.

Each node should be simulated by a thread. The main program should create one thread per node and
then wait until all threads complete. Note: At most 99 nodes will be simulated and at most 99 processes
will run on each node.

Each node has its own ready and blocked queues, as well as its own clock. Note: This may require that
some of the static or global variables be placed into structs that are passed around so that each thread
has its own copy of the variables. Each node should:
1. Admit the processes assigned to it (from the shared array of processes)
2. Run the simulation of processes that are assigned to this node.
3. When a process enters the finished state, it should be added to a commonly shared list of finished
processes.
4. Once all processes on a node are finished, the thread can end.

The finished processes should be ordered in the list according to the time that they finish. If two processes
finish at the same time, the tie is broken by the Node number (smaller Node number goes first). If two
processes finish at the same time on the same node, the tie is broken by the process id (smaller ID goes
first). The process ID is the order in which the processes were admitted, starting with 1. The process IDs
are the same as in Assignment 2. Hint: Use a shared priority queue to store the finished processes and
use formula
Priority = Finish TimeÍ100Í100 + NodeÍ100 + Process ID
when inserting the finished processes into the queue. This will automatically sort them, first by time, then
by node, and lastly by process id.

Once all nodes have completed the simulation, the main thread prints out a summary of all processes in
the order that the finished. (See Output section.)
Critical Sections
There will be a couple critical sections in your simulator where you will need mutex locks. For example,
the shared priority queue for finished processes and printing output are both good candidates.

Output
The output for this assignment is the same as that of Assignment 2, except that when a process changes
state, output:
[Node] Time: process PID State
where Node is the node on which the process is running, zero padded to 2 digits, Time is the current time
in clock ticks, zero padded to 5 digits, PID is the process id, and State is one of new, ready, running,
blocked, or finished. Each output should be on a separate line and terminated by new line. (See
example.)

The output summary for each process should be of the form:

| Time | Proc Node.PID | Run run_time, Block block _time, Wait wait_time
where
• Time is the finish time of the process.
• Node is the node on which the process was simulated.
• PID is the process id of the process.
• run_time is the sum ticks of all DOOPs performed by the process.
• block_time is the sum ticks of all BLOCKs performed by the process.
• wait_time is the sum ticks that the process spent in the ready queue.
Summaries should be outputted in order as specified in the previous section and should be terminated by
new lines. (See examples.)

Note: that the order of the output will likely be different for each run because the scheduler may schedule
the threads differently on each run. However, as long the output from each thread is in order, and each
output is on its own line and is uncorrupted, that is fine.

Note: The functionality tests will normalize the output of your programs by sorting it to compare it to the
expected output.

Note: The functionality tests EXPECT there to be differences in sequence order from run to run. In fact, if
there is not difference, that means there is too little concurrency and the tests will fail.
Example:
Input Output: Order of thread may differ on each run!
5 5 3 [01] 00000: process 1 new
Proc1 3 1 1 [01] 00000: process 1 ready
DOOP 4 [01] 00000: process 2 new
BLOCK 5 [01] 00000: process 2 blocked
HALT [01] 00000: process 1 running
[01] 00004: process 2 ready
Proc2 3 1 1 [03] 00000: process 1 new
BLOCK 4 [03] 00000: process 1 ready
DOOP 5 [01] 00004: process 1 blocked
HALT [01] 00004: process 2 running
[03] 00000: process 1 running
Proc3 3 1 2 [02] 00000: process 1 new
DOOP 4 [02] 00000: process 1 ready
BLOCK 4 [02] 00000: process 2 new
HALT [01] 00009: process 1 finished
[01] 00009: process 2 finished
Proc4 3 1 2 [02] 00000: process 2 ready
DOOP 3 [03] 00005: process 1 ready
BLOCK 4 [03] 00005: process 1 running
HALT [03] 00008: process 1 blocked
[03] 00013: process 1 finished
Proc4 3 1 3 [02] 00000: process 1 running
DOOP 8 [02] 00004: process 1 blocked
BLOCK 5 [02] 00004: process 2 running
HALT [02] 00007: process 2 blocked
[02] 00008: process 1 finished
[02] 00011: process 2 finished
| 00008 | Proc 02.01 | Run 4, Block 4, Wait 0
| 00009 | Proc 01.01 | Run 4, Block 5, Wait 0
| 00009 | Proc 01.02 | Run 5, Block 4, Wait 0
| 00011 | Proc 02.02 | Run 3, Block 4, Wait 4
| 00013 | Proc 03.01 | Run 8, Block 5, Wait 0

Note: The order of the threads will change from execution to execution.

Assignment Submission
Submission and testing are done using Git, Gitlab, and Gitlab CI/CD. You can submit as many times as you
wish, up to the deadline. Every time a submission occurs, functional tests are executed and you can view
the results of the tests. To submit use the same procedure as Assignments 1 and 2.

Hints and Suggestions

• You will need to use locks to protect critical sections in your program. The sample solution has two
critical sections. One is easy to identify, the other less so.
• You will need to ensure that global/static variables used by the simulation are gathered into a struct
that is instantiated by each thread.
• If you had any issues with your Assignment 2, consider using the solution for Assignment 2 to do
Assignment 3
Grading
The assignment will be graded based on three criteria:
Functionality: “Does it work according to specifications?”. This is determined in an automated fashion by
running your program on a number of inputs and ensuring that the outputs match the expected outputs.
The score is determined based on the number of tests that your program passes. So, if your program
passes t/T tests, you will receive that proportion of the marks.

Quality of Solution: “Is it a good solution?” This considers whether the approach and algorithm in your
solution is correct. This is determined by visual inspection of the code. It is possible to get a good grade
on this part even if you have bugs that cause your code to fail some of the tests.

Code Clarity: “Is it well written?” This considers whether the solution is properly formatted, well docu-
mented, and follows coding style guidelines. A single overall mark will be assigned for clarity. Please see
the Style Guide in the Assignment section of the course in Brightspace.

If your program does not compile, it is considered non-functional and of extremely poor quality, mean-
ing you will receive 0 for the solution.

The following grading scheme will be used:

Task 100% 80% 60% 40% 20% 0%
Functionality
Proportionate to the fraction of tests passed.
(20 marks)
Solution uses Solution uses multi- Solution uses Solution creates An at-
multithread- threading correctly. multithreading threads but thread tempt

code does not compile

No code submitted or
Solution Quality ing, is thread- The solution is correctly and state is not correct, has been
(20 marks) safe, and is thread-safe but is thread state is does not use multi- made.
maximally con- not maximally con- correct. Solution threading correctly
current. current. is not thread-safe. or is not thread-safe.
Code Clarity Code looks Code looks good Code is mostly Code is hard to read Code is
(10 marks) professional and mostly follows readable and and follows few of illegible
Indentation, for- and follows all style guidelines. mostly follows the style guidelines.
matting, naming, style guidelines some of the style
comments guidelines.

Assignment Testing without Submission

Testing via submission can take some time, especially if the server is loaded. You can run the tests without
submitting your code by using the provided runtests.sh script. Please see the last section of Assign-
ment 2 on how to run tests without submission. Please note that buggy multithreaded applications can
be CPU hogs if left spinning, so please be sure to properly terminate your program.

Also, please note that multithreaded applications behave differently on different systems, so testing it on
the remote server is very important.