2019 Spring, CSCI 3150 – Bonus 2Contents1 Introduction 31.1 Process States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 The Ready Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Scheduling Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 CPU Scheduler Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 The assignment package 52.1 Get starter package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 os-sim.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.2 process.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.3 student.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Your assignment 83.1 To begin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2 Your job . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2.1 FCFS Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913.2.2 Round-Robin Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . 103.2.3 Static Priority Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Check your results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.3.1 Run our grader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.3.2 Running statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.4 Submit your assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Grading 155 Change Log 156 Questions 167 Academic Honesty 168 General Notes 1621 IntroductionIn this assignment, you are requested to implement a CPU scheduler for a (simulated)OS written by us. Hopefully, you will get some more solid knowledge on scheduling, multithreading,and synchronization by doing this assignment. We thank Umakishore Ramachandran,Kevin Han, and Adithya Nott from Georgia Tech when preparing this assignment.1.1 Process StatesIn our simulated OS, there are five possible states for a process, which are listed in theprocess state t (an enum type variable) in os-sim.h: NEW - The process is being created, and has not yet begun executing. READY - The process is ready to execute, and is waiting to be scheduled on a CPU. RUNNING - The process is currently executing on a CPU. WAITING - The process has temporarily stopped executing, and is waiting on an I/Orequest to complete. TERMINATED - The process has completed.There is a field named state in the PCB (Process Control Block 1, see the definition inos-sim.h), which must be updated with the current state of the process. The simulated OSwill use this field to collect statistics. Fig. 1 shows the transition of different process states.1.2 The Ready QueueOn most systems, there are a large number of processes, but only one or two CPUs on whichto execute them. When there are more processes ready to execute than CPUs, processesmust wait in the READY state until a CPU becomes available. To keep track of the processeswaiting to execute, our simulated OS keeps a ready queue where the processes are in READYstate.1https://en.wikipedia.org/wiki/Process_control_block3Figure 1: Process StatesSince the ready queue can be accessed by multiple processors, which may add or removeprocesses from the ready queue, the ready queue must be protected by some form ofsynchronization — for this assignment, it shall be a mutex lock.1.3 Scheduling Processesschedule() is the core function of the CPU scheduler. It is invoked whenever a CPUbecomes available for running a process. schedule() must search the ready queue, select arunnable process, and call the context switch() function to switch that process onto theCPU.There is a special process, the idle process, which is scheduled whenever there are noprocesses in READY state.1.4 CPU Scheduler InvocationThere are four events that our simulated OS will invoke schedule(): yield() - A process completes its CPU operations and yields the processor to performan I/O request. wake up() - A process that previously yielded completes its I/O request, and is readyto perform CPU operations. wake up() is also called when a process in the NEW state4becomes runnable. preempt() - When using a Round-Robin or Static Priority scheduling algorithm, aCPU-bound process may be preempted before it completes its CPU operations. terminate() - A process exits or is killed.The CPU scheduler also contains one other important function: idle(). idle() is calledwhen the idle process 2is scheduled. In the real world, the idle process puts the processorin a low-power mode and waits. For our simulated OS, you will use a pthread conditionvariable to block the thread until a process enters the ready queue.2 The assignment package2.1 Get starter packageYou should have opened a Github account and told us your github account by filling up aGoogle form during your assignment 0. So, after logging in your Github account, come herehttps://classroom.github.com/a/Vi-drgTh to get a new repo for this assignment. Thenew repo should contain the starter package for this assignment.You are given the following files to implement the simulated OS:2https://unix.stackexchange.com/questions/361245/what-does-an-idle-cpu-process-do5Name Description/os-sim.c Code for the simulated OS which calls your CPUscheduler (Don’t touch)./os-sim.h Header file for the simulator (Don’t touch)./process.c Descriptions of the simulated processes (Don’ttouch)./process.h Header file for the process data (Don’t touch)./student.c This file contains stub functions for your CPUscheduler (Work on it)./student.h Header file for your code to interface with the simulatedOS (Don’t touch)./Makefile Makefile to compile os-sim (Don’t touch)./grader.py We will run this script to grade your assignment(Don’t touch).2.2 Remarks2.2.1 os-sim.cThe simulated OS is implemented by pThread. One thread per CPU and one thread asa “supervisor” for our simulation. The CPU threads will simulate the currently-runningprocesses on each CPU, and the supervisor thread will print output and dispatch events tothe CPU threads. Fig. 2 demonstrates the function calls in the simulated OS.Since the code you write will be called from multiple threads, the CPU scheduler youwrite must be thread-safe! This means that all data structures you use, including your readyqueue, must be protected using mutexes.The number of CPUs is specified as a command-line parameter to the simulator. For thisassignment, we will simulate an OS with 1, 2, or 4 CPUs.Also, for assignment purposes, the simulated OS executes much slower than a real systemwould. In the real world, a CPU burst might range from one to a few hundred milliseconds,whereas in this simulator, they range from 0.2 to 2.0 seconds.6Figure 2: Function calls in the simluated OS2.2.2 process.cThis file contains the processes that we will submit to the simulated OS.We use eight hard-coded simulated processes, five CPU-bound and three I/O-bound, asshown in following figure. The simulated OS will submit these processes to the ready queuesequentially, and you need to implement the correct scheduling algorithm to select the nextjobs to run.For simplicity, we have labeled each starting with a “C” or ”I” to indicate whether it isCPU-bound or I/O-bound. For this assignment, priorities range from 0 to 10, with 10 beingthe highest priority. Note that the I/O-bound processes have been given higher prioritiesthan the CPU-bound processes.72.2.3 student.cThis file contains the implementation of CPU scheduler.As we introduced in Section 1.3 and Section 1.4, it contains the core function schedule()and other five events function yield(), wake up(), preempt(), terminate() and idle().Besides, the main() is also in this file.3 Your assignment3.1 To beginMake, then run ./os-sim 2, an OS with two CPUs will be simulated and you shall seesomething like this:The simulator generates a Gantt Chart, showing the current state of the simulated OSat every 100ms interval. The leftmost column shows the current time, in seconds. The nextthree columns show the number of Running, Ready, and Waiting processes, respectively. Thenext two columns show the process currently running on each CPU. The rightmost column8shows the processes which are currently in the I/O queue, with the head of the queue on theleft and the tail of the queue on the right.As you can see, nothing is executing. This is because the CPU scheduler has not beenimplemented yet! Once you complete this assignment, you will see the processes executingon the CPUs.3.2 Your jobYour job is to implement the following three CPU scheduling algorithms for the CPU schedulerin student.c:First-Come, First Served (FCFS) - Runnable processes are kept in a first-in, firstoutready queue. FCFS is non-preemptive; once a process begins running on a CPU,it will continue running until it either completes or blocks for I/O. Round-Robin (RR) - Similar to FCFS, except preemptive. Each process is assigneda timeslice when it is scheduled. At the end of the timeslice, if the process is stillrunning, the process is preempted, and moved to the tail of the ready queue. Static Priority- The processes with the highest priorities always get the CPU. Lowerpriorityprocesses may be preempted if a process with a higher priority becomesrunnable.3.2.1 FCFS SchedulerImplement the CPU scheduler using the FCFS scheduling algorithm. You may do thishowever you like, however, we suggest the following: Implement a thread-safe ready queue using a linked list. A linked list will allow you toreuse this ready queue for the Round-Robin and Static Priority scheduling algorithms. Implement the yield(), wake up(), and terminate() handlers. preempt() is notnecessary for this stage of the assignment. See the overview and the comments in thecode for the proper behavior of these events.9 Implement idle(). idle() must wait on a condition variable that is signalled whenevera process is added to the ready queue. Implement schedule(). schedule() should extract the first process in the readyqueue, then call context switch() to select the process to execute. If there are norunnable processes, schedule() should call context switch() with a NULL pointeras the PCB to execute the idle process.Here are some notes for your implementation: Remember to update the state field of the PCB. The simulator will read this field togenerate the Running, Ready, and Waiting columns, and to generate the statistics atthe end of the simulation. There is a field in the PCB, next, which you may use to build linked lists of PCBs. Four of the five entry points into the scheduler (idle(), yield(), terminate(), andpreempt()) should cause a new process to be scheduled on the CPU. In your handlers,be sure to call schedule(), which will select a runnable process, and then callcontext switch(). When these four functions return, the library will simula代写CSCI 3150作业、Round-Robin Scheduler作业代做、代写c++语言作业、c++编程语言作业调te theprocess selected by context switch(). context switch() takes a timeslice parameter, which is used for preemptive schedulingalgorithms. Since FCFS is non-preemptive, use -1 for this parameter to give the processan infinite timeslice.3.2.2 Round-Robin SchedulerAdd Round-Robin scheduling functionality to your code. You should modify main() to add acommand line option, -r, which selects the Round-Robin scheduling algorithm, and acceptsa parameter, the length of the timeslice. For this assignment, timeslices are measured intenths of seconds. E.g.:./os-sim -r 5should run a Round-Robin scheduler with timeslices of 500 ms. While:./os-sim should continue to run a FCFS scheduler.10Table 1: The test casestest ID parameters Purpose0 ./os-sim 1 test FCFS with one CPU1 ./os-sim 2 test FCFS with two CPUs2 ./os-sim 4 test FCFS with four CPUs3 ./os-sim 1 -r 1 test RR with one CPU and timeslices of 100ms4 ./os-sim 2 -r 1 test RR with two CPUs and timeslices of 100ms5 ./os-sim 1 -r 5 test RR with one CPU and timeslices of 500ms6 ./os-sim 2 -r 5 test RR with two CPUs and timeslices of 500ms7 ./os-sim 1 -p test Static Priority with one CPU8 ./os-sim 2 -p test Static Priority with two CPUs9 ./os-sim 4 -p test Static Priority with four CPUs3.2.3 Static Priority SchedulingAdd Static Priority scheduling to your code. Modify main() to accept the -p parameter toselect the Static Priority algorithm. The -r and default FCFS scheduler should continue towork. The scheduler should use the priority specified in the static priority field of thePCB. This priority is a value from 0 to 10, with 0 being the lowest priority and 10 being thehighest priority.For Static Priority scheduling, you will need to make use of the current[] array andforce preempt() function. The current[] array should be used to keep track of theprocess currently executing on each CPU. Since this array is accessed by multiple CPUthreads, it must be protected by a mutex. current mutex has been provided for you. Theforce preempt() function preempts a running process before its timeslice expires. Yourwake up() handler should make use of this function to preempt a lower priority processwhen a higher priority process needs a CPU 3.In this part, you will need a priority queue not a First-in-First-out queue as the readyqueue. One suggestion is to extend the linked list implementation you wrote for the FCFSalgorithm. The common approach is to add priority push() or priority pop() function3If the new arrived process have the same priority with the lowest priority process which is currentlyexecuting on the CPU, we do not preempt the running process.11for the queue.3.3 Check your resultsBefore running the grader, please set the CPU number of the virtual machine as 4. Becausethe different cpu number will affect the expected range of evaluation metrics (will be describedin following section). The excepted range in the grader is determined according to 4cpus.3.3.1 Run our graderAfter you have finished the assignment, run grader.py to check whether you can pass thegiven test cases. There are 10 test cases which are briefly introduced in Table 1. You havetwo ways to run our grader:python3 grader.pywill run all 10 test cases, whilepython3 grader.py iwill only run the ith test case.If you correctly finish the assignment and type the following commands:python3 grader.pyyou shall see something like this:12Otherwise, the grader will output the fail reason of each test case. All possible reasonsare listed below: Running timeout (we set a running time limit for each test case) The number of context switches is not within the valid range The total execution time is not within the valid range The total time spent in READY state is not within the valid range3.3.2 Running statisticsIf you successfully complete the assignment, then executing ./os-sim with a set of validparameters will print the executed process schedule and its statistics:1. Number of context switches2. Total execution time133. Total time spent in READY stateThese numbers are a bit non-deterministic. However, there is an expected range for eachnumber, and we will check whether your numbers are in the given range.To understand the source of non-deterministic behavior, see the following example. Supposethere are two CPUs (CPU1 and CPU2) in the simulated OS, and there are two processes(P1 and P2) to be scheduled. At time 5, process P1 finishes and process P2 arrives. Since inreal world, time is continuous and thus there is no such thing called the “same” time, therebecomes 2 possibilities:1. P2 arrives before P1 is ’finishing’, so the scheduler schedules P2 to CPU2, and thenschedules idle() to CPU1. There are 2 context switches.2. P2 arrives after P1 has finished, so if the scheduler schedules P2 to CPU1, then only1 context switch.143.4 Submit your assignmentFollow the procedure in assignment 1.Warning: DO NOT change the file names or otherwise you will get 0 marks4 Grading1. The TA will fetch and grade your latest version in your repo as of April 25, 2018,11:00AM. Remember to commit and push before the deadline!2. 10 test cases in total as listed in Table 1.3. Passing one test case will earn you 10 marks.4. If you need help for using pthreads, you can refer to https://computing.llnl.gov/tutorials/pthreads/ and Google.5 Change Log1.0 this document156 QuestionsIf you have doubts about the assignment, you are encouraged to ask questions on Piazzausing the corresponding tag. Please focus on knowledge. Unhealthy questions/commentsthat focus on scores and grades are not encouraged.If you find any (possible) bugs, send private questions on Piazza to us instead— otherwise that may cause unnecessary panic among the class if that is not a real bug.7 Academic HonestyWe follow the University guide on academic honesty against any plagiarism.8 General Notes This specification and our grading platform are both based our given course VM. Youshould compile, debug and run the assignment program on that VM. So, if you insistto develop on another platform other than our VM and got any question, test it onour VM before you ask. The TA reserves the right to adjust your scores for any request that requires their extramanual effort. Unless specified, you should work and fill your code in designated areas. There arecases that the modification outside the designated area leads to misbehavior of the autograder. Proceed with caution and look back the changes if your output is different fromwhat is shown in the grader. While we have already tried our best to prepare this assignment, we reserve all therights to update the specification and the grading scheme. If there are any mistakes/bugswhich are on ours, the TA will step in and do manual grading to ensureyou get what you deserve. Please respect each other. Any irresponsible, unfair, biasedsentiment would regard as a disciplinary case.16 If this is a programming assignment, only C is allowed, not even C++. If this is ascripting assignment, only bash shell script is allowed, not even Python. Furthermore,for C programming assignments, use the “exit” function parsimoniously because itmight influence the grader as well. Therefore, use “return” instead of “exit” wheneverpossible. Although this is not an algorithm class, you still shouldn’t implement your assignmentwith very poor complexity. While the TAs will try their best to run your programas long as they could, they reserve the right to terminate a test case and regard thatas a failed test case when a program takes unreasonably long time to finish (try tocompare your running time with the TA’s demo if it is given), or until when the TAscan’t run any longer due to the deadline the TA needs to submit your final scores tothe department. When grading, the TAs will execute the grader program to run the whole test suite(which consists of all test cases). The TAs won’t grade each individual test caseseparately. (Frequently Asked) [Output format] If the assignment package includes a demo,then our grader defines test cases based on the given demo. In that case, your outputshall exactly follow that demo. For example, hypothetically, if our demo outputs amessage like:command not foundwith two spaces between “not” and “found”. Your output shall also match that inorder to pass the test. The good news is that, if our given demo has not implementedsomething (e.g., missed certain error checking), you also don’t need to do so. Notest cases would be defined based on something that our demo has notimplemented. (Frequently Asked) [Scope of error handling] The scope of error checking andhandling shall refer to both our given demo (if given) and our given test cases.First, the corresponding output message shall exactly follow our demo. Second, you17are informed that our demo may have implemented more error checking that what ourgrader will test. In that case, it is fine that you implement only the error checking thatis tested by our grader. So, one top tip is:CHECK THE (SOURCE OF)TEST CASES BEFORE YOU ASK (Frequently Asked) [No hidden test case] We are not intended to run any secret/extratest cases that deliberately break your assignment. That is, WYSIWYG — yourfinal score shall be generally indicated by what the grader reports when it runs onthe course VM. However, we do reserve the right to run some additional test cases toavoid any mis-conduct (e.g., hard-coding the results), and/or invite you to explain thesource code to the teaching assistants and adjust the scores accordingly. We welcome discussions among classmates. But don’t share your assignment with theothers in any means. For example, don’t put your source code in any public venue (e.g,public repo, your homepage, Facebook). We handle plagiarism strictly. On submittingthis assignment, you are agreed that your code’s copyright belongs to the ChineseUniversity of Hong Kong. Unless with our written approval, you must not releaseyour source code and this specification now and forever. If you share your code withanyone without our written consent, that would regard as a disciplinary case as longas you are still a CUHK student (i.e., even after this course). If you share your codewith anyone without our written consent after your graduation, that would regard asa breach of copyright and we reserve all the rights to take the corresponding legalactions. Google is your friend. We encourage you use Google for help to do the assignment.However, if you happen to find any source codes related to this assignment, you stillcannot copy it but use your own way to implement it. You need to put down your listof source code references as comments in the top of your source code.18 (Frequently Asked) [Late Policy] TAs will only grade the latest version submittedbefore the deadline, no late submission is allowed. It is your responsibility to makesure you added, committed, and pushed the final version before the deadline. You arerequired to check whether your final version is really in Github Classroom.19转自：http://www.7daixie.com/2019042536755754.html
网友评论