辅导CPU scheduling algorithm、讲解C/C++语言、辅导C/C++程序、辅导CPU留学生
- 首页 >> C/C++编程Answer all the questions below. Once you are finished, print the code of
Question 2 on paper and submit the paper at the start of the lecture on the
due date. Put your name (in English) and student ID number on the paper.
Also add to your paper a picture of your program running.
In addition, upload the C file (only the C file) for Question 2 on iSpace.
Late homework assignments will not be accepted, unless you have a valid
written excuse (medical, etc.). You must do this assignment alone. No
team work or "talking with your friends" will be accepted. No copying from
the Internet. Cheating means zero.
0) The goal of this homework assignment is to implement the Earliest
Deadline First real-time CPU scheduling algorithm, which is the scheduling
algorithm that students often use when doing their homework assignments.
Warning: there are many different ways to write the code for this homework
assignment, which makes detecting cheating easier...
Note: sice there are many different ways to write the code, make sure that
you put MANY comments in your code explaining how your code works! Also
give good meaningful names to your variables (including arrays), otherwise
you will lose points.
1) Write a program that does the following.
- Asks the user to enter the number of processes to schedule. You can
assume that this number is always strictly positive, there is no need to
check for that in your program.
- For each process to schedule, ask the user the enter the burst time and
the period for the process. You can assume that all burst times and
periods are strictly positive, and that the period for a given process is
always at least as big as the burst time of the same process, there is no
need to check for all these things in your program. You can also assume
that all processes have the same arrival time: zero.
Here is an example of what running the program must look like (where 2, 25,
50, 35, and 80 are inputs typed by the user on the keyboard):
============================================================
Enter the number of processes to schedule: 2
Enter the burst time of process 1: 25
Enter the period of process 1: 50
Enter the burst time of process 2: 35
Enter the period of process 2: 80
============================================================
Once your program has read all this information from the user, your program
must schedule the processes using the Earliest Deadline First algorithm and
print the computed schedule on the screen. The printed schedule must start
at time 0 and continue up to (but not including) MaxTime, where MaxTime is
the Least Common Multiple of all the periods.
Here is some C code that you can use in your program to compute the Least
Common Multiple of an array of integers:
// Greatest Common Divisor (recursive version)
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
// Least Common Multiple
int lcm(int a[], int num) {
int result = 1;
for(int i = 0; i < num; i++) {
result *= a[i] / gcd(result, a[i]);
}
return result;
}
If you give an array of process periods to this lcm function then the
function returns as result the Least Common Multiple of all the periods.
The second argument num of the lcm function is the number of elements in
the array.
When scheduling the processes, your program must indicate:
- when a process’s current CPU burst starts;
- when a process’s current CPU burst ends;
- when a process is preempted (replaced on the CPU) by another process;
- when MaxTime is reached and the scheduling ends.
Here is an example of what running the program must then look like (where
2, 25, 50, 35, and 80 are inputs typed by the user on the keyboard):
============================================================
Enter the number of processes to schedule: 2
Enter the burst time of process 1: 25
Enter the period of process 1: 50
Enter the burst time of process 2: 35
Enter the period of process 2: 80
0: process 1 starts
25: process 1 ends
25: process 2 starts
60: process 2 ends
60: process 1 starts
85: process 1 ends
85: process 2 starts
100: process 2 preempted!
100: process 1 starts
125: process 1 ends
125: process 2 starts
145: process 2 ends
150: process 1 starts
175: process 1 ends
175: process 2 starts
210: process 2 ends
210: process 1 starts
235: process 1 ends
240: process 2 starts
250: process 2 preempted!
250: process 1 starts
275: process 1 ends
275: process 2 starts
300: process 2 ends
300: process 1 starts
325: process 1 ends
325: process 2 starts
350: process 2 preempted!
350: process 1 starts
375: process 1 ends
375: process 2 starts
385: process 2 ends
400: MaxTime reached
============================================================
(Compare this output with the Gantt chart on slide 5.45 of the lecture notes.)
Your program must also indicate when a process misses its deadline and by
how many milliseconds the deadline was then missed. Here is another
example of what running the program must then look like (where 2, 25, 50,
50, and 80 are inputs typed by the user on the keyboard):
============================================================
Enter the number of processes to schedule: 2
Enter the burst time of process 1: 25
Enter the period of process 1: 50
Enter the burst time of process 2: 50
Enter the period of process 2: 80
0: process 1 starts
25: process 1 ends
25: process 2 starts
75: process 2 ends
75: process 1 starts
100: process 1 ends
100: process 1 starts
125: process 1 ends
125: process 2 starts
160: process 2 missed deadline (15 ms left)
160: process 2 preempted!
160: process 1 starts
185: process 1 ends
185: process 2 starts
240: process 2 missed deadline (10 ms left)
240: process 2 preempted!
240: process 1 starts
250: process 1 missed deadline (15 ms left)
290: process 1 ends
290: process 2 starts
320: process 2 missed deadline (30 ms left)
320: process 2 preempted!
320: process 1 starts
345: process 1 ends
345: process 2 starts
350: process 2 preempted!
350: process 1 starts
375: process 1 ends
375: process 2 starts
400: MaxTime reached
============================================================
Here is another example of what running the program must look like (where
3, 20, 40, 40, 80, 30, and 60 are inputs typed by the user on the
keyboard):
============================================================
Enter the number of processes to schedule: 3
Enter the burst time of process 1: 20
Enter the period of process 1: 40
Enter the burst time of process 2: 40
Enter the period of process 2: 80
Enter the burst time of process 3: 30
Enter the period of process 3: 60
0: process 1 starts
20: process 1 ends
20: process 3 starts
50: process 3 ends
50: process 1 starts
70: process 1 ends
70: process 2 starts
80: process 2 missed deadline (30 ms left)
80: process 2 preempted!
80: process 1 starts
100: process 1 ends
100: process 3 starts
120: process 3 missed deadline (10 ms left)
120: process 3 preempted!
120: process 1 starts
140: process 1 ends
140: process 2 starts
160: process 2 missed deadline (50 ms left)
160: process 2 preempted!
160: process 3 starts
180: process 3 missed deadline (20 ms left)
180: process 3 preempted!
180: process 1 starts
200: process 1 ends
200: process 1 starts
220: process 1 ends
220: process 2 starts
240: MaxTime reached
============================================================
2) Modify your program so that it now also prints the Average Waiting Time.
Since processes are executed periodically, computing the Average Waiting
Time must be done as follows:
- compute the sum of all the waiting times for all the processes from time
0 up to (but not including) MaxTime.
- compute the number of times all the processes start a new CPU burst from
time 0 up to (but not including) MaxTime (this number is also equal to
the total number of periods for all the processes from time 0 up to (but
not including) MaxTime);
- divide the total waiting time by the total number of burst times to get
the Average Waiting Time.
Here is an example of what running the program must then look like (where
2, 25, 50, 35, and 80 are inputs typed by the user on the keyboard):
============================================================
Enter the number of processes to schedule: 2
Enter the burst time of process 1: 25
Enter the period of process 1: 50
Enter the burst time of process 2: 35
Enter the period of process 2: 80
0: process 1 starts
25: process 1 ends
25: process 2 starts
60: process 2 ends
60: process 1 starts
85: process 1 ends
85: process 2 starts
100: process 2 preempted!
100: process 1 starts
125: process 1 ends
125: process 2 starts
145: process 2 ends
150: process 1 starts
175: process 1 ends
175: process 2 starts
210: process 2 ends
210: process 1 starts
235: process 1 ends
240: process 2 starts
250: process 2 preempted!
250: process 1 starts
275: process 1 ends
275: process 2 starts
300: process 2 ends
300: process 1 starts
325: process 1 ends
325: process 2 starts
350: process 2 preempted!
350: process 1 starts
375: process 1 ends
375: process 2 starts
385: process 2 ends
400: MaxTime reached
Sum of all waiting times: 145
Number of CPU bursts: 13
Average Waiting Time: 11.153846
============================================================
Here is another example of what running the program must then look like
(where 3, 20, 40, 40, 80, 30, and 60 are inputs typed by the user on the
keyboard):
============================================================
Enter the number of processes to schedule: 3
Enter the burst time of process 1: 20
Enter the period of process 1: 40
Enter the burst time of process 2: 40
Enter the period of process 2: 80
Enter the burst time of process 3: 30
Enter the period of process 3: 60
0: process 1 starts
20: process 1 ends
20: process 3 starts
50: process 3 ends
50: process 1 starts
70: process 1 ends
70: process 2 starts
80: process 2 missed deadline (30 ms left)
80: process 2 preempted!
80: process 1 starts
100: process 1 ends
100: process 3 starts
120: process 3 missed deadline (10 ms left)
120: process 3 preempted!
120: process 1 starts
140: process 1 ends
140: process 2 starts
160: process 2 missed deadline (50 ms left)
160: process 2 preempted!
160: process 3 starts
180: process 3 missed deadline (20 ms left)
180: process 3 preempted!
180: process 1 starts
200: process 1 ends
200: process 1 starts
220: process 1 ends
220: process 2 starts
240: MaxTime reached
Sum of all waiting times: 380
Number of CPU bursts: 13
Average Waiting Time: 29.230769
============================================================
Here are a few extra instructions:
- Give meaningful names to your variables so we can easily know what each
variable is used for in your program.
- Put comments in your code (in English!) to explain WHAT your code is
doing and also to explain HOW your program is doing it.
- Make sure all your code is properly indented (formatted). Your code
must be beautiful to read.
- Include a picture of your program running, even if your program is not
completely finished.
Failure to follow these instructions will result in you losing points.
The End!