Description
In assignment 3, you’re going to implement scheduling policies, and write programs that use threads, locks, and condition variables.
You’re going to do this by simulating running tasks on a multi-CPU system with threads.
Assignment 3 is due Friday, July 16th, 2021 at 4:30pm CDT (Winnipeg time).
General submission requirements
Submissions that violate any of the following will not be evaluated (i.e., you will receive a score of 0 for the assignment):
All solutions must be written in C. No other languages are accepted.
All solutions must include a working Makefile.
oForget how to make a Makefile? Never knew how to make a Makefile? Thankfully, you can go to https://makefiletutorial.com and find some very easy to use basic examples.
oYour Makefile should contain a clean rule. When
make clean
is run in your directory, all the temporary files, including the executable should be removed (e.g., rm -f my_prog).
All solutions must be compiled by issuing the command make in the directory containing the Makefile. No other build commands are acceptable, even if documented in the README.md.
All solutions must include a Markdown-formatted README.md file that minimally describes how to run your submission.
oForget how to make a README.md? Never knew how to make README.md? Thankfully, you can go to https://readme.so/ and build a nice, Markdown-formatted README.md with a nice preview and some handy buttons to help you build it.
All solutions must run to successful completion. Premature termination for any reason (no obvious output, Segmentation Fault, Bus Error, etc.) is considered to be a solution implementation that does not run.
Code that runs for an unreasonably long time (e.g., > 30 seconds) without terminating is also considered to be a solution implementation that does not run.
All solutions must compile. Code that does not compile will not be evaluated.
Programs must produce no errors when compiled with the flags
-Wall -Wpedantic -Wextra -Werror
Note that -Werror prevents your code from being compiled when warnings are present.
If these flags are not in your Makefile, your submission will be treated as though it does not compile.
Your code must compile and run on a machine on aviary.cs.umanitoba.ca.
No late submissions will be accepted. The assignment deadline is enforced electronically. Submissions will not be accepted by e-mail.
Reminder: All submitted code will be evaluated using an automated similarity testing tool, alongside commonly available online solutions for problems.
Question 1 - Simulating Scheduling
This scheduling policy is so real. (Pixabay License)
In this question, you’ll be writing a simulator that:
Implements different process scheduling policies, and
Simulates the behaviour of those scheduling policies running on a multi CPU system using threads (where each “CPU” is one thread)
You will also be comparing the performance of different scheduling policies using this simulator.
Your simulator will implement two different scheduling policies:
1.Shortest job first (non-preemptive, not priority-based)
2.Multi-level feedback queue (preemptive, priority-based)
Implementation
While the overall design of your program is up to you, a recommended architecture that generally makes sense to use here looks like:
Recommended architecture.
1.Before the simulator starts, you will load the workload (your set of tasks) into the scheduler, and initialize all of your “CPU” threads. The “CPU” threads should wait after they have been initialized until the dispatcher notifies them that tasks are available.
2.When the simulator starts, your scheduling policy will decide which task should be executed next given the complete set of tasks that are waiting to run.
3.The dispatcher will notify all waiting “CPU” threads that a new task is available to be executed. One of the “CPU” threads will take the task and “run” it.
4.The “CPU” threads will each run one task at a time. Running a task here means doing two things: Deciding if/when the task will make a system call (i.e., request I/O) and sleeping until either the task is done, the time slice is complete, or the time until the task makes a system call elapses.
Once sleeping is done, your “CPU” should update the appropriate accounting values for the task before placing the task back into the queue or into the done area.
5.If a task still has time left to complete, it will be sent back to the scheduling policy to be rescheduled. Note that when the task is rescheduled, it may or may not be “run” on the same CPU again (we’re not implementing processor affinity).
6.If a task does not have any time left to complete after running on the CPU, the CPU will put the task into the “Done” area.
7.When there are no tasks left to be scheduled, the simulator shuts down and produces a report.
If you implement your scheduler using this architecture, your implementation will require several locks, minimally where the CPUs get a task from the dispatcher, where the CPUs return the task to the running queue, and where the CPUs write tasks into the “Done” area. The level of granularity that you choose to implement in terms of locking the queue here is your decision.
You’re also going to need to use condition variables to tell CPUs that are not currently working on a task that a new task is available.
Workload
Tasks are initially loaded from a file, and are put in the scheduler’s ready queue before the start of the simulation (in other words, all tasks arrive at the same time).
The file of tasks has a space-delimited format:
task_name task_type task_length odds_of_IO
There are 4 types of tasks to run, which are indicated by an id:
id 0 - Short tasks
id 1 - Medium tasks
id 2 - Long tasks
id 3 - I/O tasks
Note: I/O tasks are effectively the same as “Long tasks”, where the only difference is that I/O tasks have a higher chance of doing an I/O operation (see taskmaker.py to get an idea of how the tasks are created).
Here’s an example of a single line that’s generated by taskmaker.py, which represents the properties for one task:
io_task_1 3 100 50
This line can be decoded into a task in your system as:
task_name: “io_task_1”
task_type: 3, io task
task_length: 100 microseconds left to complete
odds_of_IO: 50%
You can find a file of tasks here. Note that your program will be evaluated on a different tasks.txt than what is provided here, so you should be sure to generate at least one other workload using taskmaker.py and verify that your program does not crash on different input.
I/O
The odds of a task yielding the processor for I/O is a percentage out of 100.
The strategy that you can use to determine whether or not a task makes a system call (does I/O) is using random numbers. When a task starts on a CPU, generate a random number between 0 and 100. If the number you generate is less than or equal to the “odds_of_IO” for a task, then the task will do I/O. If the number you generate is greater than the “odds_of_IO” for a task, then the task will not do I/O.
If a task does do I/O, then you should generate another random number based on how much time the task could possibly execute for. The random number that you should generate should be between 0 and the length of a time slice (this is for both preemptive and non-preemptive policies).
If a task does not do I/O, then it should just run for it’s complete time slice or for it’s entire run time, depending on the policy you’re implementing.
I/O in this system is satisfied instantly. That means that if a task does I/O, it should be placed back into the scheduler and it should be eligible to be scheduled, possibly immediately.
“Running” tasks
The tasks that you’re running don’t actually do anything, they just go to sleep. Once you’ve decided how long your task is going to run for, the “CPU” thread should just go to sleep for that long, in microseconds.
You can use the following code snippet to “run” your task:
#include
#define NANOS_PER_USEC 1000
#define USEC_PER_SEC 1000000
static void microsleep(unsigned int usecs)
{
long seconds = usecs / USEC_PER_SEC;
long nanos = (usecs % USEC_PER_SEC) * NANOS_PER_USEC;
struct timespec t = { .tv_sec = seconds, .tv_nsec = nanos };
int ret;
do
{
ret = nanosleep( &t, &t );
// need to loop, `nanosleep` might return before sleeping
// for the complete time (see `man nanosleep` for details)
} while (ret == -1 && (t.tv_sec || t.tv_nsec));
}
Policies
SJF
Shortest Job First is a non-preemptive scheduling policy — jobs will either run to completion or will yield the processor doing I/O.
Even though this is not a preemptive scheduling policy, for the purposes of doing I/O, you should consider a time slice to be 50 microseconds.
Note that the SJF scheduling policy is described in section 7.4 of OSTEP.
MLFQ
Your implementation of a multi-level feedback queue (MLFQ) should match what is described in Chapter 9 of OSTEP. Specifically, it should implement the final set of rules that are described:
The set of rules from chapter 9.
The configuration for your implementation of MLFQ should be:
1.Three (3) priority levels.
2.Quantum length for all queues is 50 microseconds.
3.Time allotment for tasks is 200 microseconds before their priority is lowered.
4.The value for S should be 5000 microseconds (or as close as possible).
Queues
You are welcome to implement your own queue(s) as a linked data structure in C, but you also have other options:
1.Use the queue wrapper library defined in sys/queue.h (see man queue).
2.Use a “ticket-based” queuing/priority system, similar to the ticket lock implementation described in Chapter 28 of OSTEP.
3.Use an array/some arrays and constantly sort them by some property of each task.
Measuring time
You will ultimately be reporting on the average turnaround time and response time for each type of task in the system. In that your tasks will actually take time to complete, you should be measuring real time.
As in assignment 1, you can use clock_gettime to get the current time with sufficient granularity. You almost certainly want to use CLOCK_REALTIME.
Also as in assignment 1, you should take a look at Profiling Code Using clock_gettime by Guy Rutenberg for a complete example on how to compute differences between times gathered from clock_gettime. The code in Guy’s blog post is explicitly permitted to be used in your own solutions.
Running
Your program should take two command-line arguments:
1.The number of CPUs in the system you’re simulating, and
2.The scheduling policy that should be used to order tasks.
Some examples:
./a3q1 4 sjf # 4 "CPUs" with shortest job first policy
./a3q1 2 mlfq # 2 "CPUs" with the multi-level feedback queue policy
Your program does not need to take the name of the tasks file on the command-line. Instead, it should use a file with the exact name tasks.txt, e.g.,
FILE *task_file = fopen("tasks.txt", "r");
Output
Print the following statistics at the end of the simulation:
Average turnaround time for each type of task.
Average response time for each type of task.
Sample output
Using sjf with 4 CPUs.
Average turnaround time per type:
Type 0: 861 usec
Type 1: 2476 usec
Type 2: 16384 usec
Type 3: 18239 usec
Average response time per type:
Type 0: 900 usec
Type 1: 2017 usec
Type 2: 1092 usec
Type 3: 9816 usec
Report and analysis
Run the scheduling policies that you implemented 5 times each with 1 CPU, 2 CPUs, 4 CPUs, and 8 CPUs. Compute an average turnaround and response time for each type of task for each scheduling policy for these settings.
Include these results in your README.md, and explain whether or not the results that you’re seeing make sense by answering the following:
Is the difference in turnaround time and response time for each policy what you expected to see? Why or why not?
How does adjusting the number of CPUs in the system affect the turnaround time or response time for tasks? Does it appear to be highly correlated?
Tables in text
Working with tables in text (e.g., Markdown) is sorta painful, but almost all popular text editors have extensions or plugins that help ease this pain:
Text Tables by RomanPeshkov is one that seems to be popular for VS Code.
VIM Table Mode by Dhruva Sagar is one that I use personally in vim.
Evaluation
Implementation
5 points are awarded for code quality and design:
Level Description
0 The code is very poor quality (e.g., no comments at all, no functions, poor naming conventions for variables, etc).
1–3 The code is low quality, while some coding standards are applied, their use is inconsistent (e.g., inconsistent use of comments, some functions but functions might do too much, code is repeated that should be in a function, etc).
This is the maximum level you can earn if the implementation of your program is substantially incomplete.
4–5 The code is high quality, coding standards are applied consistently throughout the code base.
5 points are awarded for implementation of shortest job first:
Level Description
0 No attempt is made to answer this question or code does not run or compile.
1–2 The submitted implementation of SJF is substantially incomplete, or is not multi-threaded.
3–4 The submitted implementation of SJF is substantially complete and is minimally multi-threaded. Submitted implementation may not (for example) implement I/O correctly.
5 The submitted implementation of SJF is complete and is fully multi-threaded.
10 points are awarded for implementation of multi-level feedback queue (5 × 2):
Level Description
0 No attempt is made to answer this question or code does not run or compile.
1–2 The submitted implementation of MLFQ is substantially incomplete, or is not multi-threaded.
3–4 The submitted implementation of MLFQ is substantially complete and minimally multi-threaded. Submitted implementation may not (for example) implement priority boosting correctly.
5 The submitted implementation of MLFQ is complete and is fully multi- threaded.
Report
5 points are awarded for the report:
Level Description
0 No report is included, or neither SJF or MLFQ is implemented (you can’t earn points for a report if you don’t implement the policies).
1–3 A report for only one of SJF or MLFQ is included. The report may not adequately describe expected behaviours with adjusting CPUs.
4–5 A report for both SJF and MLFQ is included. Report adequately compares the policies, and adequately describes expected behaviours with adjusting CPUs.
Submitting your assignment
Submissions will be made using the handin command available on all CS UNIX systems.
If your files are in a folder named my_a3, you would run the command:
handin 3430 a3 my_a3
If you need more information, you can see man handin.