Ask Computer Engineering Expert

Phase 1: Build a thread system

Stock Nachos has an incomplete thread system. In this assignment, your job is to complete it, and then use it to solve several synchronization problems.

The first step is to read and understand the partial thread system we have written for you. This thread system implements thread fork, thread completion, and semaphores for synchronization. It also provides locks and condition variables built on top of semaphores.

After installing the Nachos distribution, run the program nachos (in the proj1 subdirectory) for a simple test of our code. This causes the methods of nachos.threads.ThreadedKernel to be called in the order listed in threads/ThreadedKernel.java:

The ThreadedKernel constructor is invoked to create the Nachos kernel.

This kernel is initialized with initialize().

This kernel is tested with selfTest().

This kernel is finally "run" with run(). For now, run() does nothing, since our kernel is not yet able to run user programs.

Trace the execution path (by hand) for the simple test cases we provide. When you trace the execution path, it is helpful to keep track of the state of each thread and which procedures are on each thread's execution stack. You will notice that when one thread calls TCB.contextSwitch(), that thread stops executing, and another thread starts running. The first thing the new thread does is to return from TCB.contextSwitch(). We realize this comment will seem cryptic to you at this point, but you will understand threads once you understand why the TCB.contextSwitch() that gets called is different from the TCB.contextSwitch() that returns.

Properly synchronized code should work no matter what order the scheduler chooses to run the threads on the ready list. In other words, we should be able to put a call to KThread.yield() (causing the scheduler to choose another thread to run) anywhere in your code where interrupts are enabled, and your code should still be correct. You will be asked to write properly synchronized code as part of the later assignments, so understanding how to do this is crucial to being able to do the project.

To aid you in this, code linked in with Nachos will cause KThread.yield() to be called on your behalf in a repeatable (but sometimes unpredictable) way. Nachos code is repeatable in that if you call it repeatedly with the same arguments, it will do exactly the same thing each time. However, if you invoke "nachos -s ", with a different number each time, calls to KThread.yield() will be inserted at different places in the code.

You are encouraged to add new classes to your solution as you see fit; the code we provide you is not a complete skeleton for the project. Also, there should be no busy-waiting in any of your solutions to this assignment.

Your project code will be automatically graded. We are in the process of setting up an autograder. In order for you to verify that your code is compatible with the autograder, there are some simple compatibility tests you can run before you submit.

Since your submissions will be processed by a program, there are some very important things you must do, as well as things you must not do.

For all of the projects in this class.

Do not modify Makefile, except to add source files. You will not be submitting this file (javac automatically finds source files to compile, so we don't need you to submit Makefile).

Only modify nachos.conf according to the project specifications. You will not be submitting this file either. Do not rely on any additional keys being in this file.

Do not modify any classes in the nachos.machine package, the nachos.ag package, or the nachos.security package. You will not be submitting any of these classes.

Do not add any new packages to your project. All the classes you submit must reside in the packages we provide.

Do not modify the API for methods that the autograder uses. This is enforced every time you run Nachos by Machine.checkUserClasses(). If an assertion fails there, you'll know you've modified an interface that needs to stay the way it was given to you.

Do not directly use Java threads (the java.lang.Thread class). The Nachos security manager will not permit it. All the threads you use should be managed by TCB objects (see the documentation for nachos.machine.TCB).

Do not use the synchronized keyword in any of your code. We will grep for it and reject any submission that contains it.

Do not directly use Java File objects (in the java.io package). In later projects, when we start dealing with files, you will use a Nachos file system layer.

When you want to add source files to your project, simply add entries to your Makefile. In this project,

The only package you will submit is nachos.threads, so don't add any source files to any other package.

The autograder will not call ThreadedKernel.selfTest() or ThreadedKernel.run(). If there is any kernel initialization you need to do, you should finish it before ThreadedKernel.initialize() returns.

There are some mandatory autograder calls in the KThread code. Leave them as they are.

Tasks:

Nachos implements kernel threads via the class KThread in the file threads/KThread.java. Implement KThread.join(). Suppose that thisThread is a thread object. Then, thisThread->join() should cause the caller to wait until the thread "represented" by thisThread finishes. If thisThread was already finished at the time of the call, then the call should return right away. Note that another thread does not have to call join(), but if it is called, it must be called only once. The result of calling join() a second time on the same thread is undefined. A thread must finish executing normally whether or not it is joined.

Implement condition variables directly, by using interrupt enable and disable to provide atomicity. We have provided a sample implementation that uses semaphores; your job is to provide an equivalent implementation without directly using semaphores (you may of course still use locks, even though they indirectly use semaphores). Once you are done, you will have two alternative implementations that provide the exact same functionality. Your second implementation of condition variables must reside in class nachos.threads.Condition2 (that is, in the file threads/Condition2.java).

Complete the implementation of the Alarm class (threads/Alarm.java), by implementing the waitUntil(int x) method. This class uses the hardware timer interrupt to provide two services: (a) preemption for preemptive CPU scheduling via the timerInterrupt() method , and (b) to allow a thread to suspend its own execution until time has advanced to at least now + x via the waitUntil(int x)method. This is useful for threads that operate in real-time, for example, for blinking the cursor once per second. Currently, waitUntil(int x) is implemented using busy waiting. Your task is to change the implementation of waitUntil(int x) so that the calling thread blocks. You will need to modify timerInterrupt() as well to wake up sleeping threads when it is time. There is no requirement that threads start running immediately after waking up; just put them on the ready queue in the timer interrupt handler after they have waited for at least the right amount of time. Do not fork any additional threads to implement waitUntil(); you need only modify waitUntil() and the timerInterrupt(). waitUntil is not limited to one thread; any number of threads may call it and be suspended at any one time.

Implement synchronous send and receive of one word messages (also known as Ada-style rendezvous), using condition variables (don't use semaphores!). Implement the Communicator class (file threads/Communicator.java) with operations, void speak(int word) and int listen(). speak() atomically waits until listen() is called on the same Communicator object, and then transfers the word over to listen(). Once the transfer is made, both can return. Similarly, listen() waits until speak() is called, at which point the transfer is made, and both can return (listen() returns the word). Your solution should work even if there are multiple speakers and listeners for the same Communicator (note: this is equivalent to a zero-length bounded buffer; since the buffer has no room, the producer and consumer must interact directly, requiring that they wait for one another). Each communicator should only use exactly one lock. If you're using more than one lock, you're making things too complicated.

Now that you have all of these synchronization devices, use them to solve this problem. You will find condition variables to be the most useful synchronization method for this problem. You've just been hired by Mother Nature to help her out with the chemical reaction to form water, which she doesn't seem to be able to get right due to synchronization problems. The trick is to get two H atoms and one O atom all together at the same time. The atoms are threads. Each H atom invokes a procedure hReady when it's ready to react, and each O atom invokes a procedure oReady when it's ready. For this problem, you are to write the code for hReady and oReady. The procedures must delay until there are at least two H atoms and one O atom present, and then one of the procedures must call the procedure makeWater (which just prints out a debug message that water was made). After the makeWater call, two instances of hReady and one instance of oReady should return. Write the code for hReady and oReady using either semaphores or locks and condition variables for synchronization. Your solution must avoid starvation and busy-waiting. The class file that you should edit is here (ReactWater.java). Please add this file to nachos/threads. The Autograder will create one ReactWater object and a bunch of threads. Each thread will invoke either the hReady or oReady routine. Your task is only to write the ReactWater class correctly.
What the Design Document Should Look Like

For each part above, you should:

Identify all Nachos classes that you will modify (and where you plan to do you modifications),

Identify all classes that you plan to implement and give the API for each class,

Provide high-level pseudocode for each method,

For each class, provide a logical argument why the pseudocode you have provided for the methods work together to solve the posed problem. For example, for number 4, you need to explain what happens when multiple senders and listeners are using the same Communicator object.

Test cases that you plan to use.

Basically, your design document should convince us (and you) that you have looked through the Nachos code, understand what's going on, and has a valid plan for writing and testing necessary code in a relatively short amount of time. So, it should include any information that is important towards this purpose. The above list is just a short "guide" and may not be all inclusive.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91227189
  • Price:- $70

Priced at Now at $70, Verified Solution

Have any Question?


Related Questions in Computer Engineering

Does bmw have a guided missile corporate culture and

Does BMW have a guided missile corporate culture, and incubator corporate culture, a family corporate culture, or an Eiffel tower corporate culture?

Rebecca borrows 10000 at 18 compounded annually she pays

Rebecca borrows $10,000 at 18% compounded annually. She pays off the loan over a 5-year period with annual payments, starting at year 1. Each successive payment is $700 greater than the previous payment. (a) How much was ...

Jeff decides to start saving some money from this upcoming

Jeff decides to start saving some money from this upcoming month onwards. He decides to save only $500 at first, but each month he will increase the amount invested by $100. He will do it for 60 months (including the fir ...

Suppose you make 30 annual investments in a fund that pays

Suppose you make 30 annual investments in a fund that pays 6% compounded annually. If your first deposit is $7,500 and each successive deposit is 6% greater than the preceding deposit, how much will be in the fund immedi ...

Question -under what circumstances is it ethical if ever to

Question :- Under what circumstances is it ethical, if ever, to use consumer information in marketing research? Explain why you consider it ethical or unethical.

What are the differences between four types of economics

What are the differences between four types of economics evaluations and their differences with other two (budget impact analysis (BIA) and cost of illness (COI) studies)?

What type of economic system does norway have explain some

What type of economic system does Norway have? Explain some of the benefits of this system to the country and some of the drawbacks,

Among the who imf and wto which of these governmental

Among the WHO, IMF, and WTO, which of these governmental institutions do you feel has most profoundly shaped healthcare outcomes in low-income countries and why? Please support your reasons with examples and research/doc ...

A real estate developer will build two different types of

A real estate developer will build two different types of apartments in a residential area: one- bedroom apartments and two-bedroom apartments. In addition, the developer will build either a swimming pool or a tennis cou ...

Question what some of the reasons that evolutionary models

Question : What some of the reasons that evolutionary models are considered by many to be the best approach to software development. The response must be typed, single spaced, must be in times new roman font (size 12) an ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As