📄 http:^^www.cs.wisc.edu^~bart^537^programs^program3.html
字号:
Date: Mon, 11 Nov 1996 17:24:43 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Fri, 26 Apr 1996 15:22:04 GMTContent-length: 9355<html><head><title>CS 537 - Programming Assignment #3</title></head><body><table border=0 width=100% align=center><tr><td width=25%><td width=50% align=center><b>UNIVERSITY OF WISCONSIN-MADISON<br>Computer Sciences Department</b><td width=25%><tr><tr><td><b>CS 537<br>Spring 1996 </b><td><td align=right><b>Bart Miller</b><tr><td><td align=center><b>Programming Assignment #3</b><br>(Due Wednesday, May 1, at 5pm)<td></table><h2>Simulating CPU Scheduling Algorithms</h2>The goal of this assignment is to evaluate several CPU scheduling algorithms.We will use trace data from our local UNIX systems to test these algorithms.<p>Your assignment is to write a program that reads in the trace data andsimulates the CPU scheduling.You will keep track of various performance statistics and print these out atthe completion of the trace file.<h2>The Trace Files</h2>The trace files look similar to the ones you used for Program #1.Each line of the trace file will be of the form:<pre>CommandName StartTime CPUTime IOCount</pre>Each of these three pieces will be separated by some number of blank characters(spaces or tabs).<ul><li><i>CommandName</i>is a character string (maximum length of 10 characters) that containsthe name of the program;<li><i>StartTime</i>is the time in 10 millisecond increments (100ths of a second) since midnight -this is the time that the program arrived in the system;<li><i>CPUTime</i>is the total CPU time, in seconds, used by thisprogram;<li><i>IOCount</i>records the total number of bytes of disk I/O done by this program.Disk I/O always occurs in full blocks; blocks are8K (8192 bytes).We will ignore all other types of I/O (such as network or keyboard/display).</ul><p>The lines in the trace files are sorted by program starting time.<h2>Program Information</h2>Your program will be structured as a continuous loop that reads trace recordsand advances time.<h3>Important Events</h3>Your program will maintain a notion of current time.The "clock" in your simulator will be a variable that holds the value ofthe current time.the clock tick will be 1 ms.The clock will start at time 0 and advances each time a program runs orwhile the simulated CPU is idle and waiting.<p>Several things can happen while a simulator is running:<ol><li>The process that is currently running could complete:In this case, you need to update the various performance statistics (seebelow) and remove the process from any run/ready queues.<li>The process will start a disk I/O:In this case, you need to block the process until the I/O is completed.<li>A disk I/O will complete:The process that completed its I/O will be placed back in the appropriaterun/ready queue.<li>A new process will arrive (be ready to start):In this case, the current time of the simulator matches that the arrival timeof one or more jobs in the trace file.These jobs need to be placed the appropriate ready queues.</ol><h3>Scheduling Algorithms</h3><p>The details of the particular scheduling algorithm (you will implement several)should be isolated in a single class.All your program, except for the scheduling algorithm, should be thesame for the different versions.<ol><li>The first version of your program will implement Round Robin scheduling.Each process runs until it completes its time slice, blocks for disk I/O, terminates,a disk I/O completes, or another job arrives(i.e., if a new processarrives or a disk I/O completesduring the running process's time slice, the running processis interrupted).You will test this with time slices of 10 ms, 100 ms, and 1000 ms.<li>The second version of your program will implement Exponential Queues.As with RR,each process runs until it completes its time slice, blocks for disk I/O, terminates,a disk I/O completes, or another job arrives.Any time a process is interrupted (by a new process or by I/O completion), it isplaced back in the queues,<i>at the end of the queue</i>,for the correct priority.You will have 8 priority levels and the base (smallest time slice) will be10ms.When a process uses its full time slice, you descrease its priority and doubleits slice.When a process uses <i>less than half</i> of its timeslice, you increase its priorityand half its slice.<li>The third version of your program will implement STCP scheduling.For this version, you will be sorting the ready queue according to how muchtotal CPU time remains for each process.A newly arrived process or a disk I/O completing willpreempt the running process(so the currently running is interruptedand placed back in the queue,<i>according to how much CPU time it has remaining</i>).</ol><h3>Simulator Details</h3>Here are some important details:<ol><li>For all three versions, a context switch takes 1 ms:Taking a process out of execution takes 1 ms andstarting a process to execute also takes 1 ms.<li>When a process does an I/O operation, it blocks until the operation iscompleted.<li>Each process will perform a certain number I/O operations based on the<i>IOCount</i>field of it's trace record.Since, I/O is always done in blocks on 8K, you round <b>up</b> IOCount tothe next multiple of 8K:<center><tt>IOOperations = trunc ((IOCount + 8191) / 8192)</tt></center><li>You will use the<i>IOOperations</i> count and the<i>CPUTime</i>field to calculate how often the process will block for I/O.Divide the value<i>CPUTime</i>field by the number of I/O operations (round to the near millisecond).Note that we are assuming that I/O operations are evenly distributedthroughout the execution of a program.The I/O operation always occurs at the<b>end</b>of a CPU burst.<p>If the<i>CPUTime</i>does not divide evenly by the number of I/O operations,then the last CPU burst will be smaller than the other ones and <b>not</b>be followed by a disk I/O.<p>If the number of I/O operations is greater than the number of milliseconds of<i>CPUTime</i>,than the excess I/O operations will all be done at the end of the process (withno extra context switches between each operation).<p>Some examples:<ul><li>If the <i>CPUTime</i> is 20 and the number of I/O operationsis 4, then the process will need to start an I/O operation after each 5 ms ofexecution.So, the process will execute 5 ms, then do an I/O, execute another 5 ms,then do an I/O, and so on.<li>If the <i>CPUTime</i> is 23 and the number of I/O operationsis 4, then the process will execute exactly as the above case, with anadditional 3 ms CPU burst after the last disk I/O.<li>If the <i>CPUTime</i> is 5 and the number of I/O operations is 10, thenthe process will start one I/O operation after each 1 ms of exectution,with 6 I/O operations being done together at the end of the last CPUburst.</ul><li>Disk I/O operations take exactly the same amount of time: 20 ms each.Your computer has one disk and can do only one disk operation at a time.As soon as one operation is completed, the next can start (with no timein between).</ol><h3>Performance Data</h3>Your simulator will keep trace of several performance statistics and print outthese results when the simulator completes.These statistics are:<ol><li>Average Completion Time (ACT):For each job, you will calculate how it it took to run.The time is the difference between its completion time and arrival time.The ACT is the average of this value for all jobs in the trace file.<li>Minimum and Maximum Completion Time:You will also compute the minimum and maximum completion times over allthe jobs.<li>Throughput:This is the number of jobs per second.Divide thenumber of jobs that were executedbytotal running time of the simulator.<li>Utilization:This is the amount time spent doing useful computation.It does not include idle time or time spent doing context switches.Print out the total and as a percentage of the running time of the simulator.</ol><!--For each of the three versions, you will test your simulator on thedata files in ~cs537/TESTFILES/data.sched1 and ~cs537/TESTFILES/data.sched2.--><h2>Software Design Issues</h2>Good design on this assignment will save you, literally thousands of linesof code.A crucial class in each version of your program will be the class that doesthe queuing.In one version of the program, it does simple FIFO queuing. In anotherversion, it is a priority queue sorted by one of 8 priority levels.In the last version, it is a priority queue sorted by remaining CPU time.<p>All other parts of your program should be the same, so you can re-use themfor the different versions.<p>You have plenty of time for this assignment, but don't delay in gettingstarted!Work on a design and and initial structure for your classes, then come talkwith me or the TA's.<h2>Deliverables</h2><p>You should hand in a print-out of your program and Makefile.Your program listing should include a copy of the code for<b>each</b>scheduling algorithm, and one copyof the code for the rest of the program.These should be clearly labeled.<p>Your simulator should print out the statistics described above for eachsimulator run.<hr><H4>Last modified:Fri Apr 26 10:22:03 CDT 1996by<a href="http://www.cs.wisc.edu/~bart">bart</a></b></H4></body>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -