Introduction

In this assignment, you are given a working thread system, which is part of Nachos; your job is to explore the use of threads, semaphores, and locks, and to use them to solve synchronization problems. This project should be done individually.

Assuming you did Project 1, you already have the Nachos files that are necessary for this assignment in your account. If you did not do Project 1, see the section entitled "Getting Started" in the Project 1 assignment.

The first step in this project is to prepare for the assigned problems by reading some of the Nachos source code. Most of this code should be familiar to you from Project 1, while only a small amount of code is new. As in Project 1, I suggest that you read the files in the order described below, and as you do so, read the corresponding sections in Thomas Narten's "A Road Map Through Nachos" and Archna Kalra's "Salsa - An Operating Systems Tutorial".

For Project 1, you read through the following code. For this project, you might want to read through it once again, while thinking primarily about how it handles threads.

• threads/main.ce, threads/threadtest.cc - a simple test of the thread routines.

• threads/system.h, threads/system.cc - Nachos startup/shutdown routines.

• threads/thread.h, threads/thread.cc - thread data structures and thread operations such as thread fork, thread sleep and thread finish.

• threads/scheduler.h, threads/scheduler.cc - manages the list of threads that are ready to run.

• threads/switch.h, threads/switch.s - assembly language magic for starting up threads and context switching between them. Don't worry ifyou &)n't understand these twofiles - you are not responsible.for understanding them

• threads/list.h, threads/list.cc - generic list management.

• threads/utility.h, threads/utility.cc- some useful definitions and debugging routines.

After re-familiarizing yourself with the code above, read through the following files to see how Nachos

implements semaphores. Note that the structure for locks and condition variables is in place, but the code to implement them is missing. You might also want to review the material in Lectures 11 to14 online describing how semaphores and locks are imple mented.

threads/synch.h, threads/synch.cc - synchronization routines: semaphores, locks, and condition variables.

Finally, read through the following files to see how Nachos puts semaphores to a practical use. threads/synchlist.h, threads/synchlist.cc - synchronized access to lists using locks and condition variables (useful as an example of the use of synchronization primitives).

Tracing Through and Debugging Nachos Source Code

The first step in this project is to read and understand the thread system in Nachos, which implements thread fork, thread completion, and semaphores for synchronization. To copy the necessary files and compile Nachos, see the Project 1 instructions on the course home page entitled "How to get an early start." Run the resulting program "nachos" in the thread directory for a simple test of the code. Trace the execution path (as in the Project I assigment) for the simple test case provided.

There are three main ways to study and debug your Nachos program:

• using Nachos DEBUG/ASSERT function :

  the function itself is specified in threads /utility. h. The output produced by this routine is controlled by the command line options given to nachos at run-time. These options are described in threads/main.cc and threads/system.cc. The debugging option is "-d". Run "nachos -d t" to see what your code is doing. You can add your own DEBUG calls and your own options. The "C" and "W" flags might also be useful.

• using printf:

  you can use printf statements to output the values the variables assume at different times of program execution. Caveat: the output is not displayed immediately but rather buffered. Use f f lush () to force immediate printing;

• using gdb:

  gdb is a general purpose source level debugger. Using it is a comprehensive way of debugging your Nachos programs. Check the course's webpage for reference materials on gdb. You should try using gdb before asking the TA or the instructor for help with your code.

Writing Properly Synchronized Code

Part of the goal of this project is to learn how to write code that synchronizes multiple threads, which may be important in later projects since all threads share a common address space in Nachos. Note that properly synchronized code should work no matter what order the scheduler chooses to run the threads on the ready fist. In other words, the TA or I should be able to put a call to Thread:: Yield (causing the scheduler to choose another thread to run) an3nKtLere in your code where interrupts are enabled without changing the correctness of your code.

Identifying Your Changes

So that the TA and I can easily identify which code you have changed or added, surround all changes and additions in your code by comments in the following form:

/ / PROJECT 2 CHANGES START HERE

<your changed code goes here>

/ / PROJECT 2 CHANGES END HERE

Use your own judgment about how much code to surround in a single comment.

Questions

1. (30 points) In the file threads/threadtest.cc, write a function TestList with the functionality described below. Modify threads/main.cc so that if Nachos is called with the "-tt" command line option, ThreadTest is called, while if Nachos is called with the "-tl" command line option, TestList is called.

   Your function TestList should fork two threads named A and B. A should loop 10 times, printing out a single character A each time using a printf statement. Similarly, B should loop 10 times, printing out a single character B each time using a printf statement. After writing this code, in a file called proj2.prob1, do the following:

   1. Include a sample run to demonstrate that everything you implemented works.
   2. Run Nachos using the "t", "i", and "m" debugging flags, and explain briefly what is happening (don't include the program output as it'll be too long-just explain what's happening).
   3. If you insert calls to Thread: Yield inside A so that it yields after printing each A; and add similar calls inside B, does the output change? If so, show the new output, and explain why it changes (you might want to use the debugging flags again to figure this out). If not, explain why it doesn't change. (Note - after you add these Yields, comment them out when you email the code to the TA.)
   4. If you did not complete this problem, clearly describe what you have done, what is not working, and how you would go about finishing the problem if you had more time.

2. (10 points) Modify your solution to problem I above so that the loops in A and B are protected by semaphores (i.e., so that the loops are mutually-exclusive critical sections). After writing this code, in a file called proj2.prob2, do the following:
   1. Include a sample run to demonstrate that everything you implemented works.
   2. Run Nachos using the "t", "i", and "m" debugging flags, and explain briefly what is happening (don't include the program output as it'll be too long-just explain what's happening).
   3. If you insert calls to Thread:Yield inside A so that it yields after printing each A, and add similar calls inside B, does the output change,? If so, show the new output, and explain why it changes (you might want to use the debugging flags again to figure this out). If not, explain why it doesn't change. (Note - after you add these Yields, comment them out when you email the code to the TA.)
   4. If you did not complete this problem, clearly describe what you have done, what is not working, and how you would go about finishing the problem if you had more time.

3. (30 points) Implement locks and condition variables using the Nachos semaphores and other high-level functions. More specifically, the public interface to locks has been provided in threads/synch.h (read that file, including the comments). What you need to do is to define any necessary private data and implement the interface in threads/synch.cc. It should not take you very much code to implement these locks, and there are some helpful hints in the section "6.3 Synchronization" in "A Road Map Tbrough Nachos" (available on the class web page).

After implementing locks, modify your solution to problem 2 so that it now uses locks, instead of semaphores, to provide mutual exclusion. After writing this code, in a file called prob2.prob3, do the following:

1. Include a sample run to demonstrate that everything you implemented works.
2. Run Nachos using the "t", "i", and "m" debugging flags, and explain briefly what is happening (don't include the program output as it'll be too long-just explain what's happening).
3. If you insert calls to Thread:Yield inside A so that it yields after printing each A, and add similar calls inside B. Does the output change? If so, show the new output, and explain why it changes (you might want to use the debugging flags again to figure this out). If not, explain why it doesn't change. (Note - after you add these Yields, comment them out when you email the code to the TA.)
4. If you did not complete this problem, clearly describe what you have done, what is not working, and how you would go about finishing the problem if you had more time. \
4. (30 points) Implement a solution to the Dining Philosophers Problem with five philosophers using Locks and Condition Variables. After writing this code, in a file called prob2.prob4, do the following:
   1. Include a sample run to demonstrate that everything you implemented works printing out whenver a philosopher changes state.
   2. Run Nachos using the "t", "i", and "m" debugging flags, and explain briefly what is happening (don't include the program output as it'll be too long-just explain what's happening).
   3. If you insert calls to Thread:Yield inside the code for each philosopher so that it yields while the philosopher is philosophising does the output change? If so, show the new output, and explain why it changes (you might want to use the debugging flags again to figure this out). If not, explain why it doesn't change. (Note - after you add these Yields, comment them out when you email the code to the TA.)
   4. If you did not complete this problem, clearly describe what you have done, what is not working, and how you would go about finishing the problem if you had more time.

Where to Get Help

• For questions on what the assignment is asking, please contact Prof. Farrell.
• For questions on Nachos, please contact either the TA (Mr. Seung-Su Yang) or Prof. Farrell.
• For help with your code or debugging, please contact the TA.

Also, if there are corrections or amplifications to this project, or if someone asks a question and we feel the answer may be relevant to other people, that information will be posted on the course home page under the project assignment.

Cooperation versus Cheating

See the class syllabus, and contact me if you have any questions. For this project, you are allowed to study the Nachos source code with your friends, but you are not allowed to work with anyone else to actually solve the problems, and you are certainly not allowed to copy anyone else's solution.

Submitting Your Project

When you finish, submit the files proj1.probl, proj2.prob2, proj1.prob3, proj2.prob4, main.cc, threadtest.cc, synch.cc, synch.h, and any other files that your modified to the TA for grading by typing the following commands in the threads directory:

mutt -s -Project 2 for Your Name Here" syang@cs.kent.edu <shar.out

rm shar.out

The first line puts your files into a single file called shar.out, and the second line emails that file to the TA (replace "Your Name Here" with your own name).

Important warning - once you submit your files, DON'T TOUCH THEM AGAIN - if your email didn't reach the TA, or something happens, the TA may need to ask you to resubmit your files. However, before he lets you do so, he will ask you to log on in his presence, and he will check the modification dates on your files to make sure that they haven't been modified after the due date (if they have been, you will be assessed the appropriate late penalties)..

The project is due at 11:59pm on Tuesday 18 November 2003. For a discussion of my late policy, see the course syllabus.