CS423UG -- Operating Systems Design
Prof. Indranil Gupta
MP 1: Thread Scheduling
Due date: Monday, September 19, 2005 at 10:00 am CDT
In this assignment, students are to implement several common thread scheduling algorithms.
First, please form groups of up to 2 students. You may use the newsgroups for this purpose, or hang around after lecture to form groups.
In the final report for each MP (see below), please include a paragraph (< 100 words) describing the division of responsibility for the MP among the 2 group members.
We will be using the EWS workstations. Information about the workstations is available on the EWS homepage. We will be using EWS Sun Blade workstations in the DCL (dclsn[1-30].ews.uiuc.edu), or those in the Grainger Engineering Library (glsn[1-35].ews.uiuc.edu). Information about the workstations are available here. If you want to connect those machines remotely, take a look at this. General user guide can be found here as well.
You may want to log in to one of these machines, to see if your account actually exists. All engineering students should have EWS accounts by now. If any students cannot log in, please email TAs (ta423ug@cs.uiuc.edu). We will create accounts for you as soon as possible.
Now, you should obtain the given code for this machine problem. The code can be downloaded from here. It is tarred and gzipped. Here is a short script to retrieve the file:
Please do not download the Nachos code from the official Nachos website. The construction of this MP required changes to some key files.
You will see tar listing out the files it's creating for you. Do not issue this command again from this directory unless you want to overwrite all changes you have made! If you wish to replace individual files, untar the mp1given.tar.gz file in a different directory and copy the relevant files. Everything you need for this assignment will be put in the subdirectory threads.
For this MP, the only files you will be changing are scheduler.cc and scheduler.h.
To compile your code, use the following commands: (from the threads directory)
Note: you must use gmake (instead of make) to compile your programs.
Before beginning you should familiarize yourself with the Nachos code. Links to information about Nachos will be placed on the resources section of the course web site. There will also be a short Nachos tutorial given, please see the course web site for more information.
The code you will be changing and writing for this MP will be placed in scheduler.cc and scheduler.h. Do not change any of the other files.
Chapter 2 of the text describes several common scheduling algorithms. Some of them, such as Shortest Job First, require advanced knowledge of the amount of time each process will take. Such knowledge is entirely possible in some systems. A printer, for example, will be able to compute printing time in advance, possibly based on the number of pages of each job. The print jobs could then be scheduled using Shortest Job First scheduling. Most modern CPU schedulers, however, are not able to take advantage of the run times of the processes they schedule. Because Nachos simulates a CPU scheduler, you will be only implementing scheduling algorithms which do not rely on the process run time.
Here are a few pointers that may help as you begin your reading.
Look for “MP1” in the source code comments. This tag indicates places where you may (or may not, depending on your implementation) need to add code to implement the scheduling algorithms.
Look at Scheduler::FindNextToRun() in scheduler.cc. This is the function which implements the scheduling algorithm. Based on the scheduling policy set by Scheduler::SetSchedPolicy(), implement the appropriate algorithm.
Look at Scheduler::ShouldISwitch() in scheduler.cc. This function decides whether the current thread which has just called Fork should be preempted by the newly created thread.
Look at Scheduler::ReadyToRun() in scheduler.cc. This is the function which adds a new thread to the ready list.
We can associate priorities with Nachos threads. In their original form, nachos threads do not have any priority associated with them. Threads that are ready to run are kept on a readyList. A threads priority is an integer between the constants MIN PRIORITY and MAX PRIORITY defined in the Threads class. During thread creation when the priority of the thread is not mentioned it is set equal to the priority of the parent thread. The priority of the first thread of the process is equal to NORM PRIORITY, also defined in Threads class. NOTE: Lower priorities are lower numbers and run after higher priority threads.
Modify the thread scheduler to schedule available threads based on the order of their arrival. FCFS is a non-preemptive scheduling algorithm, which means no other threads can preempt the currently running thread.
This testcase is contained in test.0.cc, and the expected output is in test.0.std. The test case itself is called test0.
Modify the thread scheduler to schedule available threads based on their priority. Newly arriving threads with a high priority will preempt a currently running thread with a lower priority.
This testcase is contained in test.1.cc, and the expected output is in test.1.std. The test case itself is called test1.
Next, modify the thread scheduler to schedule available threads in a round-robin order. For this you will need to familiarize yourself with timer.cc in the machine subdirectory. The interrupt handlers are provided for you. Note that no default timer is set at startup. The time quantum to be used is TimerTicks, which is #defined to be 40.
This testcase is contained in test.2.cc, and the expected output is in test.2.std. The test case itself is called test2.
For this part of the assignment, you will implement a scheduler that is a loose approximation to part of the scheduler in the Linux 2.4 kernel. You can read about the Linux scheduler here. This information is not needed for this assignment, but may be interesting reading.
You will modify the thread scheduler to schedule all threads of the same priority level in a round-robin order. If all the threads have the same priority level, this algorithm will exhibit the same behavior as normal Round Robin scheduling. The difference is that all high-priority threads must be allowed to finish before any lower priority threads may run. A newly arriving thread will not preempt a currently running thread until the current thread has finished its quantum. The time quantum to be used is TimerTicks, which is #defined to be 40. This algorithm is approximately similar to the way the Linux kernel handles real time threads.
This testcase is contained in test.3.cc, and the expected output is in test.3.std. The test case itself is called test3.
While every attempt was made to make this description as clear as possible, there are bound to be questions about it. Please post any questions to the newsgroup.
Note:
At the bottom of the output of each test case, you will notice a line like:
Ticks: total 1740, idle 0, system 1740, user 0
The idle ticks need not match for your solution to be correct. The threads must be
scheduled in the same order, however.
Compare the performance of 4 algorithms -- FCFS, round robin, preemptive priority scheduling, and priority-based round-robin scheduling -- using your implementations. Write THREE task sets that are different from the test cases provided to you, and measure metrics -- this should include (but need not be limited to) waiting times, turnaround times, throughput, and efficiency. Use the ticks made available by Nachos. You can call the following two methods defined in Statistics class: PrintElapsedTicks and GetElapsedTicks. Statistics class has been defined in machine/stats.h and machines/stats.cc, and used to show various statistics. You can take a look at, for example, threads/threadtest.cc, to see how to call these methods.
Clearly, this measurement may not be authoritative since you are not programming with a real scheduler (Nachos may be subject to scheduling delays due to the REAL scheduler in Solaris). However, this will give you a feel for what it is like to create test cases and compare different algorithms.
Write a 2 page report on your results. The 2 page limit includes everything -- your results, and the paragraph describing how you split the work for the entire MP among the 2 group members, and anything else you want to say. Please submit only 1 report per group. Any report exceeding the limit will be given a zero. The 2 page report should be different from the README. You may use Word, latex or any other editor for the report. Remember -- clarity of presentation is as important as content.
There are 4 symbolic links to the nachos executable in the threads directory:
There is a "standard" output file to match of the tests. The standard output is the output of the TA's solution, and you are expected to match it exactly. These standard outputs have the extension .std and their names match the number of the test. For instance, test.0.std is the output for FCFS, test.1.std is the output for Preemptive Priority, etc.
You can see if your output matches like this:
If there are no differences between the two files, diff produces no output. If there are differences, diff will show what those differences are. Change the numbers accordingly for each test.
You should hand in both your report and code. Report is due at the start of lecture, in class. Again, the report should be typed and printed out.
In the directory containing your modified files, type ~cs423ug/handin. Follow the instructions after you run handin: Type in MP number (for this MP, it is 1), and check whether your netid is correct or not. The handin program will automatically copy scheduler.cc, scheduler.h, and README.txt. README.txt should include you and your partner's netids, names, MP number, and any comments that you want to include. Please make sure you have all three files with exactly same filename (case-sensitive) in the directory. Before handin is completed, it will show the files that you submitted.
The following is an example of running handin.
glsn2> ~cs423ug/handin /===================================================\ | CS 423 UG | | Fall 2005 | | Welcome to handin | \===================================================/ -> Type in the Machine Problem number (1, 2, 3, 4): 1 Handin currently believes that your are: kim28 Enter y if this is correct or anything else otherwise y ------------- THIS IS THE INFO WE HAVE --------------- | | login-id: kim28 | MPNumber: 1 | Current Time: Sat Sep 17 13:00:28 CDT 2005 ------------------------------------------------------ -> Your MP has been handed in successfully. These are the files that you submitted: .: total 28 -rw-r--r-- 1 kim28 stdt 43 Sep 16 17:42 README.txt -rw-r--r-- 1 kim28 stdt 9907 Sep 12 10:35 scheduler.cc -rw-r--r-- 1 kim28 stdt 1960 Aug 30 2004 scheduler.h Handin successful
In summary, you will need to hand in scheduler.cc, scheduler.h, and README.txt online through command-line based handin. A printed-out 2-page report should be submitted at the start of lecture, in class. Please summarize in the report any test cases that you used, and do not submit them online.
Your grade will largely be based on the quality of measurement report and correctness of your code, which is judged by your code's ability to produce correct output in the test cases (though there are errors and omissions which the test cases don't catch). Style and legibility will be a part of your score. Crashing or failing to compile is, of course, not a correct behavior. It is very likely that you will receive no points if we cannot compile your code.
The provided test cases will not be used for grading. Passing the provided test cases does not guarantee the whole 60% of your grades.Any revisions will be listed at the top of the page and announced in the course newsgroup. Please use the newsgroup or send an email to both TAs (ta423ug@cs.uiuc.edu) if you have any questions.
Last modified by: Jintae Kim
Modified on: September 15, 2005