Project 2/3 - Scheduling

The goal of this project is to expose you to a simple operating system implementation and replace the existing scheduler with a more sophisticated scheduler, namely Lottery-based Scheduling.

Due Dates

This is a three-week, two-part assignment.

Part I is due on Monday, February 24, 2003. 11:59pm (one minute before midnight).

IMPORTANT NOTE: Do not turn in project 2 in until after Friday, February 22 at 8am. If you do so, the turnin script will think you are turning in Project 1 (late), and we may not see your turned in project 2.

Part II is due on Friday, March 7 at 11:59pm (one minute before midnight, the day before spring break begins).

You can work either alone or in a group of 2, but you must have the same groups for parts I and II.

Reminder: NO LATE ASSIGNMENTS. Do not turn in an assignment late. Turn in whatever you have working. Partial work does count, as long as you make it clear in your write-up what you have accomplished, and where you got stuck.

Instructions for submitting the assignment are available online. If you encounter problems, contact the TA.

Resources

• The main NachOS web page. Here you will find a lot of documentation that will help you in reading/modifying the code. I suggest you also read the overview paper The Nachos Instructional Operating System.
• A version of NachOS is available here. Downloaded this version into your directory, and compile it. If you download NachOS from somewhere else, I cannot guarantee that it will work...but I have tested this version on our CS systems, and it seems to work.

  On the Linux boxes, go into the code/build.linux directory and type make depend then make nachos.

  On the Solaris boxes, go into the code/build.solaris directory and type gmake depend then gmake nachos. Be sure to use gmake not make.

  To test to see if the compile worked, try ./nachos. Unfortunately we do not have a cross compiler installed on our systems, so you will not be able to use any of the test programs in the test directory. This is not a problem for this assignment.

• Lottery scheduling paper This publication is more information than you will need about lottery scheduling, but it will provide a good reference. (a local link, ps or pdf)

Project Description

Part I

Learning about NachOS. A brief introduction: NachOS is an instructional operating system emulator. It emulates a MIPS architecture machine, and runs an operating system on top of this simulator. Everything runs in user-mode, so no matter how hard you try, you will not be able to mess up your neighbor while you are working on your assignment. The architecture is assumed to be a single processor, and threads are preemptible. I'll let you read more of the official documentation to get a feel for what NachOS is good for. Note: the documentation and system may be old, but that does not mean you can't learn something valuable from it. The main idea here is to get your feet wet with some OS programming at a level where you won't hang yourself by doing something wrong. Besides, the notion of emulation before real implementation presented by NachOS is a good model for the real world.

Part I of this assignment is not a lot of coding, but it is a lot of reading other people's code, making sure that you understand it, and showing me that you understand it. The manipulation of the code will come in Part II. For this assignment, you will turn in a written document, addressing each of the questions below. This document can be either plain text, or a postscript/pdf generated from LaTeX or word. Do not submit a .doc file. Your answers to the questions need not be long, but you must show that you have read the code, and know the important, necessary details that you will use during Part II.

Caution When you turn this in, you will be using the standard turnin script. DO NOT, by mistake, turn in the entire directory which contains your copy of NachOS. We don't need 40 copies of NachOS in the cs256/cs456 accounts!

To start, you will need to download NachOS. A helpful hint: when reading the code, start with the .h file, then move to the .cc file. Also, start by reading the overview paper The Nachos Instructional Operating System.

1. Briefly describe NachOS (7-10 lines of text).
2. How does NachOS handle interrupts, such as I/O? Hint: look in mipssim.cc to find the main Run() loop of the simulator execution. Then look in interrupt.cc to see how OneTick() and CheckIfDue() work. Why is this important to know when you are writing the scheduler? How is a quantum defined in NachOS?
3. What is the default scheduler implementation? Hint: Look at scheduler.h and scheduler.cc. Why is it necessary to have interrupts disabled in the routines called from within scheduler.cc?
4. What does SWITCH (in switch.s) do? Provide some detail, but don't just read the code.
5. What are the relevant parts of the process control block? This can be found in the Tread object in NachOS. What modifications will be necessary to implement Lottery Scheduling?
6. You can test the multi-threading of NachOS by running it with ./nachos -K. This will execute the thread SelfTest which is part of threads/thread.cc. Increase the number of times the SimpleThread goes through the loop to about 50. Despite the fact that the quantum you found for the question above is greater than one, why does the SimpleThread switch after every loop? What happens if you comment out the line kernel->currentThread->Yield();? Is this what you expected based on the quantum you found above? What happens if you change the call kernel->currentThread->Yield(); to kernel->interrupt->OneTick();? Explain what is going on here! Don't get too complicated, but show me that you know why NachOS is behaving this way.
7. Give reasonable pseudoCode for the lottery scheduler. Reasonable means that you need to describe both the normal execution, and at least identify all of the exceptional cases that you will run up against.

   One reason to do this well: we will read your answers to these questions as quickly as possibly after you submit them. We will read your pseudocode, and if we detect problems (either you are trying to do too much, or are missing something key), we will be able to provide feedback before you get too far into your scheduling implementation. Don't send us code right now (we won't read that). Just good, solid pseudocode.

8. 456 Only Rewrite the thread testing routines to demonstrate the use of a semaphore. Be sure to use the OneTick() appropriately (if you don't know what this means, answer question number 6 above. If you still don't know what this means, come talk with either myself or Isaac.) put your modified version of thread.cc in the directory you turn in.

Part II.

Change the NachOS scheduler to be a lottery scheduler. Your implementation should match the description from the paper. You should implement nice. To see how nice is supposed to work on a Unix machine, read man nice. In your modified version of NachOS, a thread will call a nice method in order to change it's own nice level.

Include in your write-up a discussion of what would need to be changed in your scheduler if it was to be implemented on a multi-processor machine? Choose either a master-slave implementation or a shared memory implementation and discuss the impacts on the operating system. You should try, where possible, to refer to the specific modules of NachOS where changes would be relevant. Let me emphasize, DO NOT CODE THIS, simply write about it. But write about it in detail. I will make available in each of the labs, some material about general multi-processor issues. DO NOT remove this material from the labs. If you notice it missing, tell the TA. He can make a new copy for the lab.

Your writeup should also include clear documentation of where you made changes, and what the impact of those changes was. You should also provide evidence that your scheduler is working by providing an appropriate multi-threaded test routine and a sample output. This test routine need not do any actual work.

Another component of your writeup should be an evaluation of your priority scheduling mechanism. My suggestion is that you start up a bunch of threads with varying priorities, they can be very simple, looping programs that run for a long time, and evaluate their scheduling behavior. You will need to keep some statistics about threads to do this. Also apply these statistic gathering utilities to NachOS with the original scheduling algorithm to provide a basis for comparison. This may be one of the more time consuming parts of your project, but it is also one of the most important. This class is not simply to teach you about operating systems, you will also learn techniques to evaluate your work which you will be able to apply in the future.

To turn this in, you will NOT turn in your entire copy of NachOS. Just turn in the bits which you changed. So, keep good notes as you go about which files you changed, and the importance of the changes in each file. This will help you as you go about making modifications, and it will help us in grading.

456 extension: implement a mechanism to temporarily redistribute lottery-tickets for waiting threads. For example, when a process is stuck waiting on a semaphore, transfer its lottery tickets temporarily to the process that holds the lock. Warning: this is more complicated than it seems. Be sure that your test program exploits semaphores, and include in your writeup a complete description/discussion of this extension.