Assignment Overview
Operating Systems
Assignment 3: CPUScheduling
In this assignment, you need to design and implement a C program that simulates a CPU scheduler. This scheduleriscapableofusingvariedschedulingalgorithmstoschedulea groupofcomputationtasks.
1. ImportantNote
Thereisazero-tolerancepolicyonacademicoffensessuchasplagiarismorinappropriate collaboration.By submitting your solution for this assignment, you acknowledge that the code submitted is your own work. You also agree that your code may be submitted to a plagiarism detection software (such as MOSS) that may have servers located outside Canada unless you have notified me otherwise, in writing, before the submission deadline. Any suspected act of plagiarism will be reported to the Facultys Academic Integrity Officer in accordance with Dalhousie Universitys regulations regarding Academic Integrity. Please note that:
1) The assignments are individual assignments. You can discuss the problems with your friends/classmates, but you need to write your program by yourself. There should not be much similarity in terms of coding.
2) When you refer to some online resources to complete your program, you need to understand the mechanism and write your own code. In addition, you should cite the sources via comments in your program.
2. Detailed Requirements
1) Overview:Inthisassignment,youneedtodesignandimplementaCprogramthatsimulatesaCPU scheduler. This scheduler is capable of using the following scheduling algorithms to schedule a group of computation tasks:
1
First-Come First-Served (FCFS): FCFS schedules tasks in the order in which they arrive at the ready queue.
Round-Robin (RR): Computation tasks are served in a round-robin fashion. When there are multiple tasks to be served, each task is executed for a time quantum, then the next task in the queue will be executed. When there is only one task to be served in the computer system, this single task will keep using CPU.
Non-preemptive Shortest-Job-First (NSJF): NSJF schedules tasks in order of the length of the tasks next CPU burst. No task could be preempted.
Preemptive Shortest-Job-First (PSJF): NSJF schedules tasks in order of the length of the tasks next CPU burst. When a new task arrives, if the next CPU burst of the new task is shorter than what is left of the currently-executing task, PSJF will preempt the currently- executing task.
2) Task Specification (i.e. Input File): The details of the tasks to be scheduled are included in a file named TaskSpec.txt. A sample TaskSpec.txt is provided in this assignment. However, the TA will use a varietyofdifferentscenariostotestyourprogram.
Each row of TaskSpec.txt includes the information of one task. Each row follows the format [task name],[arrival time],[burst time]. Here is the content of the sample TaskSpec.txt:
T1,0,8 T2,1,4 T3,2,9 T4,3,5
Actually, the tasks in the sample TaskSpec.txt are the same ones used to illustrate PSJF in the lecture notes. Youcanusethelecturenotestounderstandhowthesetasksshouldbe scheduled byPSJF.
3) Scheduling Results (i.e. Output File): Once your program is executed, your program needs to retrieve the details of the tasks to be scheduled from TaskSpec.txt. Thereafter, your program schedules these tasks according to FCFS, RR, NSJF and PSJF respectively. The scheduling results are stored in a file named Output.txt in the order of FCFS, RR, NSJF and PSJF. Namely, the scheduling result of FCFS should be the first component in Output.txt, which is followed by the scheduling result of RR, NSJF, and PSJF.
Foreachoftheschedulingalgorithms, theschedulingresultiscomposedofthreeparts:
a) Algorithm Name: It should be FCFS or RR or NSJF or PSJF.
b) Execution Sequence: This part includes a number of rows to indicate how the tasks are executed.
Each row consists of three field: task name, starting time, and ending time. These fields are
separated using tabs.
c) Average Waiting Time: The resulting average waiting time should be placed in a separate line.
Forexample,hereistheschedulingresultofPSJFwhenthesampleTaskSpec.txtissupplied to yourprogram: PSJF:
T1 0 1
2
T2 1 5
T4 5 10
T1 10 17
T3 17 26
Average Waiting Time: 6.5
4) AdditionalRequirements:
a) Whentwotasksarriveatthesametime,theirorderinTaskSpec.txtdeterminestheir execution order.
Namely, the task appears first is executed first.
b) TaskSpec.txtandOutput.txtareinthesamedirectoryasyourprogram.
c) The time unit in this assignment is millisecond.
d) For Round-Robin, the time quantum is fixed at 4 milliseconds.
5) ReadmeFile:YouneedtocompleteareadmefilenamedReadme.txt,whichincludesthe instructionsthat the TA could use to compile and execute your program on bluenose.
6) Submission:Pleasepayattentiontothefollowingsubmissionrequirements:
a) You should place Readme.txt in the directory where your program files are located.
b) Your program files and Readme.txt should be compressed into a zip file named
YourFirstName-YourLastName-ASN3.zip. For example, my zip file should be called Qiang-Ye-
ASN3.zip.
c) Finally,youneedtosubmityourzipfileforthisassignmentviabrightspace.
Notethatthereisanappendixattheendofthisdocument,whichincludesthecommands thatyoucanuse to compress your files on bluenose.
3. Grading Criteria
The TA will use your submitted zip file to evaluate your assignment. The full grade is 20 points. The details of the grading criteria are presented as follows.
Readme.txtwiththecorrectcompilation/executioninstructionsisprovided[1Point]
FCFS correctly schedules the tasks in TaskSpec.txt
o Taskexecutionsequenceiscorrect[2Points]
o Averagewaitingtimeiscorrect[1Point]
RR correctly schedules the tasks in TaskSpec.txt
o Taskexecutionsequenceiscorrect[4Points]
o Averagewaitingtimeiscorrect[1Point]
NSFJ correctly schedules the tasks in TaskSpec.txt
o Taskexecutionsequenceiscorrect[4Points]
o Averagewaitingtimeiscorrect[1Point]
PSFJ correctly schedules the tasks in TaskSpec.txt
o Taskexecutionsequenceiscorrect[4Points] o Averagewaitingtimeiscorrect[1Point]
3
Proper programming format/style (e.g. release the memory that is dynamically allocated when it is not needed any more; proper comments; proper indentation/variable names, etc.). [1Point]
Please note that when Readme.txt is not provided or Readme.txt does not include the compilation/executioninstructions,yoursubmissionwillbecompiledusingthestandard commandgcc -o A2 A3.c (or your filename), and you will receive a zero grade if your program cannot be successfully compiled on bluenose.
Appendix: How to Use Zip and Unzip on Bluenose
4
Reviews
There are no reviews yet.