CS 3113 FA 21 Project 1 – CPU Scheduling

In this project, you will simulate CPU scheduling algorithms. Use will generate a set of statistics for your run and print the values to stdout. You must use C. Design your solution into small, testable parts.

Algorithms

You will implement one algorithm for this assignment. Given a known workload, design a system to read an instruction file and perform First-Come, First-Served (FCFS) Scheduling. Your code will then output several statistics of the scheduling algorithm.

Sample instruction file

P
p N
<pid> <burst> <priority>
<pid> <burst> <priority>
...

The first line of the file contains P, or the number of processes avaliable to run instructions. For this assignment, P will only equal 1. But you should start considering the case of P > 1. The second line of the file contains two integer values (p) and N (respectively) separated by a space. The (p) is the number of execution elements available to the system. In this case, you can consider these as the number of threads. N is the number of instructions in the lines to follow. Where 1 <= \(|p|\) <= 32, 1 <= \(p\) <= \(2^{15}\) and 1 <= N <= \(2^{15}\). We will only test (p) for values less than or equal to 32, but you should develop your program to support the larger value range.

After the first line, the instruction files contains three integer values per line. Each line represents an instruction that needs to be called. The first integer value is the process that needs to run. The second value is the amount of time needed to run on the CPU (the burst), the third value is the priority of the process. For this project you won’t need to deal with the priority, but you should be keeping track of the information as you will need it in future projects.

For example, if a row has the values 3 5 1, this is interpreted to mean that process 3 is requesting to run for 5 time units and has a priority of 1. Each process will be valid. The range of the burst will be greater than 1 and less than \(2^{10}\).

If an integer is listed under p it will have at least 1 instruction listed. Note: that processes may not be consecutive and are not all completed in one burst, you can assume that is because there is an underlying I/O call.

It is your job to simulate the instructions or simply calculate the total statistics listed below.

Output

The output should be seven lines of numbers printed to STDOUT.

<voluntary context switch>
<non-voluntary context switch>
<CPU Utilization>
<Δ Throughput>
<Δ turnaround time>
<Δ waiting time>
<Δ response time>

Each line is explained below.

(Non)Voluntary Context switches

Your code should output the number of times the scheduler changes the running processes. This value will be less than or equal to N. A context switch is only a change in process ids, if two consecutive instructions have the same process id there is no context switch. If an execution task (pid) switches but later has another burst, it is a nonvoluntary context switch. A voluntary context switch is caused by the completion of a task that is never continued. The voluntary context switch is listed first, then the non voluntary context switch number. Both values will be integers.

CPU Utilization

To calculate the CPU utilization you need to calculate the percentage of time that all the processes have been occupied. The range is between 0 and 100 percent for a typical one process, single threaded system. In this case, we only have one process that will always be occupied, so the value should be 100.00.

Throughput

Throughput is the amount of work each processor is completing per unit time. (We have not specified a time unit for this project.) In this case for the amount of total burst time, you should calculate the amount of execution elements that have been completed. The value should be a decimal value with two decimal places.

Turnaround time

Turnaround time of a task is the amount of time it takes from submission to task completion. In this case, all tasks are submitted at time 0. Your code should calculate the average turnaround time across all execution tasks. The value should be a decimal value with two decimal places.

Waiting time

Waiting time is the amount of time a task spends waiting on the Ready queue. This does not include the time a tasks spends executing on the CPU. In this project, we assume that if a task is not currenly being executed it should be on the ready queue. Compute the average waiting time for all execution elements; the value should be a decimal value with two decimal places.

Response time

Response time is the amount of time it takes for the task to start running. In this case, a task starts running the first time its pid is mentioned. Return the average response time for all tasks. As with other values, a decimal value is returned and should be rounded to two decimal places and only two decimal places printed.

Runing the code

Your code should take a single text file as a command line argument. If no command line argument is given, your code should read text from STDIN. Your code should then produce the output. It is recommended that you add debugging statements to your code and write them to STDERR. We will only check the values written to STDOUT to validate your code.

Example Run

ta@ta-laptop:~/fa21/TA/projects/1$ cat sample-in
1
4 5
1 1 1
2 5 5
3 4 2
4 2 6
4 5 4
ta@ta-laptop:~/fa21/TA/projects/1$ make
**output snipped**
ta@ta-laptop:~/fa21/TA/projects/1$ ./project1 sample-in
4
0
100.00
0.24
8.50
4.25
4.25
gregory@gregory-laptop:~/fa21/TA/projects/1$

Submission

We encourage you to create a private GitHub repository with the name cs3113fa21-project1. Add collaborators cegme and jmless98 by going to Settings > Manage Access. (Or Settings > Collaborators in older version of GitHub).

Your repository should have, at least, the following files:

/cs3113fa21-project1
├── .gitignore 
├── Makefile
├── project1.c
├── README
└── COLLABORATORS

When you are ready to submit, open the assignment’s submission area on Gradescope. You may make a submission by either uploading directly from your computer or linking to a GitHub or BitBucket repository. Gradescope will allow you to make multiple submissions, and get rapid feedback on those submissions. You will be able to choose to activate a previous submission up until the deadline.

Please make sure that you upload all of the required files.

Makefile

Include a makefile with the standard targets all and clean. The make all command should create an executable project1.
The make clean target should remove executables and temporary files.

README.md

The README file should be all uppercase with either no extension or a .md extension. You should write your name in it, an example of how to run the program, any bugs that should be expected, and a list of any web or external libraries that are used. The README file should make it clear contain a list of any bugs or assumptions made while writing the program. Note that you should not be copying code from any website not provided by the instructor. Using any code from previous semesters or students will results in an academic dishonesty violation. You should include directions on how to compile and use your code. You should describe all functions. You should describe any known bugs and cite any sources or people you used for help. Be sure to include any assumptions you make for your solution.

COLLABORATORS file

This file should contain a pipe separated list describing who you worked with and a small text description describing the nature of the collaboration. This information should be listed in three fields as in the example is below:

Katherine Johnson | kj@nasa.gov | Helped me understand calculations
Dorothy Vaughan | doro@dod.gov | Helped me with multiplexed time management
Stackoverflow | https://example | Helped me with a compilation bug

Deadline

Your submission/release is due on Tuesday, Nov 2nd at the end of day. The late policy of the course will be followed.

Grading

Grades will be assessed according to the following distribution:

80%: Correctness.
- This will be assessed by giving your code a range of inputs and checking the output.
20% Design and Readability. This category includes:
- The README file should be complete and descriptive.
- Correct and efficient code implementation
- Appropriate choice of function and variable names
- The COLLABORATORS file should be properly formatted and reflect all resources used.

Proper Academic Conduct

The code solution to this project must be done individually. Do not copy solutions to this problem from the network and do not look at or copy solutions from others.

Examples of Integrity violation

Situation	Integrity Violation?
	Students A and B meet and work on their assignment together. Neither student prepared anything in advance and the resulting work is identical.	Yes
	Students A and B create drafts of their assignment independently and get together to compare answers and discuss their understanding of the material. Each person decides independently whether to make changes that are discussed.	No
	Students A and B agree to prepare drafts of their assignments independently, but only Student A does. Student A shares her draft to Student B who reviews it and offers suggestions for improvement.	Yes
	Students A and B agree that student A will work the even problems and Student B will work the odd problems. They share their work.	Yes
	Students A and B agree that student A will work on a read function and Student B will work the sorting function. They share their solutions.	Yes
	Student A has completed a project and is helping Student B complete the same project. Student A explains to Student B what student B’s code actually does, which is different than what Student B thinks the code does. Student B determines how to modify the code independently.	No
	Student A has completed a project and is helping Student B complete the same project. Student B is having trouble getting one part of the program to work, so Student A texts Student B three lines of their solution.	Yes
	Student A has completed a project and is helping Student B complete the same project. Student B is having difficulty getting the program to work, so student A tells student B exactly what to type for several lines.	Yes
	Student A has completed a project and is helping student B complete the same project. Student B is having difficulty getting the program to work, so Student A suggests that Student B use a specific debugging strategy (e.g. “Print out the contents of the variable”).	No
	Student A has completed a project and is helping Student B complete the same project. Student A shows Student B an example program in the online textbook that will be helpful in figuring out the solution to the problem.	No
	Student A publishes solutions to an assignment on a public Internet page.	Yes
	Students A and B work on a project together. After they have finished it, student A takes the code and modifies it so the programs do not appear to be identical.	Yes
	Student A copy and pastes code from a public Internet page but changes the variable names.	Yes

Addendum

Back to Project List