Nachos FAQ and Bug Database (for UW's version of Nachos)

1 Setup

 1.1 How do I install this thing on Linux?
 1.2 How do I install this thing on Windows?

2 General Assignment Information

 2.1 My program won't compile on the university computers
 2.2 I can compile Nachos, but I can't compile the code in the test directory
 2.3 When compiling in the test directory, the program says that it cannot find "coff2noff"
 2.4 How do I use the debuggers in the undergrad environment?
 2.5 I haven't changed anything, but when I run make, it keeps coming up with errors
 2.6 How do I set-up version control for Nachos?
 2.7 Can we use STL?
 2.8 My system is crashing is _smalloc, _malloc, built_in_new, and/or _new.
 2.9 I'm getting the error jump to case label crosses initialization of '...'
 2.10 Is there a way to get rid of the ^M at the end of the lines?
 2.11 Nachos isn't linking correctly for no particular reason. It often complains about LSeek() or something like that.
 2.12 How do I break a circular include?
 2.13 How can I optimize my marks?
 2.14 Miscellaneous tips and stuff (should be moved elsewhere)

3 Assignment 1

 3.1 When compiling a file (usually exception.cc), I get a lot of errors including stuff like parse error before `0'.
 3.2 A Note About Syscall.h.
 3.3 How much should we worry about the synchronization of file operations and file sharing/locking problems?
 3.4 Can we assume sizeof(void *) = sizeof(int)?
 3.5 Can we use pointers recasted as integers directly as file or process ids?
 3.6 My program seems to be calling the same system call over and over again.
 3.7 Do we have to implement ThreadFork()?
 3.8 ReadRegister() returns an integer. How do I cast it to a char *?
 3.9 I'm trying to implement Close(), Exit(), etc. in my syscall.cc but these functions are already defined in sysdep.cc, so it won't compile. What's the deal with this?
 3.10 In the Nachos Roadmap, it says to use Machine::ReadMem() and Machine::WriteMem(). But they are private, and I'm not allowed to change anything in the machine directory. What am I supposed to do?
 3.11 Why are ReadMem() and WriteMem() private?
 3.12 I want to add a public method to OpenFile that returns the file descriptor
 3.13 How do I read the filename string for Create() and Open() if no size is given?
 3.14 Should Write() stop printing characters if it encounters a 0 byte?
 3.15 I'm getting failed assertions in lib/sysdep.cc.
 3.16 I'm getting failed assertions in lib/sysdep.cc related to incorrect file ids or something like that. But I'm positive that my file ids are correct.
 3.17 Should there be a limit on the number of open files?
 3.18 Can you go over how we should write our system calls?
 3.19 I have a bus error on the line *paddr=pfn*pagesize + offset
 3.20 What do we do if a page contains both read-only and writable segments?
 3.21 I'm a little confused about address spaces. How is it possible to have multiple Nachos programs with 4k address spaces running when you have only 4k of RAM?
 3.22 I think I wrote my process creation stuff correctly, but it's not working right.
 3.23 So how do I set up a new process running?
 3.24 How do I pass the strings to the new program in ExecV?
 3.25 How do I initialize the registers of a newly started process
 3.26 I'm getting Undefined Reference errors for ExecV in my test programs
 3.27 When my program reads from the console, it doesn't actually get any of the characters I type until I press enter on the keyboard. Is that ok?
 3.28 When compiling start.s, I'm getting errors like Error: Rest of line ignored. First ignored character valued 0xd.
 3.29 It seems like time-slicing is already implemented
 3.30 How do I make my thread yield while it is waiting for synchconsole input/output etc.?
 3.31 coff2noff is giving me Unknown segment type: .sbss errors.
 3.32 How do I choose the time-slice quantum
 3.33 How do I call Thread::Fork()?
 3.34 So how exactly do I go about implementing Exec() again?
 3.35 What sort of synchronization should there be on console input and output?
 3.36 Is it ok if my OS hangs when all the running processes have exited (but none have called Halt())?
 3.37 I don't understand what the Read(), Write(), Open(), Close(), etc. system calls are supposed to do
 3.38 How do we get the hash table to work?
 3.39 Afer the last thread has exited, the resources for the last one don't get freed up.
 3.40 Common stack memory errors for assignment #1
 3.41 How do I free up the memory of a thread/address space?

4 Assignment 2

 4.1 How do you turn off time-slicing?
 4.2 All my string stuff has stopped working and everything is screwed up
 4.3 There's some assertion triggering in translate.cc about pageTable and TLB both being non-null
 4.4 My Nachos seems to run fine when running a single process, but it chokes while running multiple processes
 4.5 How do I implement expandable stacks?

5 Assignment 3

 5.1 How is the datasectors[] variable of the FileHeader object written to disk?
 5.2 The assignment says to support files up to 128k in the file system, but it's not practically possible to get files of that size
 5.3 Do we need a mechanism for shrinking files?
 5.4 What is the optimum behaviour for Remove?
 5.5 What file synchronization mechanism should we implement?
 5.6 Do we really need to implement all these doubly/triply indirect pointers?

6 Lectures

 6.1 What are some things I should know for the exam?

1 Setup

1.1 How do I install this thing on Linux?

Please check the newsgroup because the answer changes depending on what Linux setup you are using, etc. In particular, the TA Kevin Moule knows lots about installing Nachos on Linux.

Make sure that you do NOT download the Nachos source from the web page. It is out of date. Use the install_nachos script to download the source to your university account, and then copy these files to your Linux version

The uw-linux site for cs354 stuff often has useful information.

Remember that Linux is not officially supported for this course, so be sure to test your Nachos implementation on the university computers often. Many students have byte-ordering problems in their Linux code and have difficulty porting their code to Solaris. Be sure to leave plenty of time to do the port!

1.2 How do I install this thing on Windows?

Although it IS possible to install Nachos on Windows (giving you access to really slick Windows IDEs and debuggers), I do not know what source changes are necessary to do this. Please note that the variant of C++ that Visual C++ compiles is different from the variant of C++ that gcc compiles.

Last term, a student DID do a port of Nachos to Windows, and the source for that is still available, but I definitely do NOT recommend that students do Nachos development in Windows. As far as I know, even the student who did that Windows port did their Nachos development in UNIX.

Just to let you know, here are various issues related to Nachos development in Windows:

1. Most students who used Windows to do Nachos work only used Visual C++ to EDIT their code.

Even I have to admit that the Visual C++ editor is pretty nice. Unfortunately, if you are using Wincenter, Wincenter goes up and down all the time (especially around OS due dates when people decide to type up their Nachos documentation in Word) too which can be annoying. Plus, Wincenter is sort of slow and unresponsive.

2. Not all of Nachos can be ported (easily) to Windows.

In particular, the MIPS cross compiler hasn't been ported to Windows yet, so you will have to compile all your test programs on a UNIX system. This is even more annoying than it sounds because you will have to change your test programs a lot, and ftping your files around can get cumbersome.

3. As always, the final program must run in the undergrad environment

In particular, during the demo, you will have to run your program in the undergrad environment. You will also probably have to edit your code and recompile your OS during the demo, so it's to your benefit that you know how to do that process pretty well. Many of the groups I saw that did their development in Linux ended up having much greater difficulty porting their OS from Linux to Solaris than they had anticipated. Porting from Windows to Solaris will be even harder because not only do you have to worry about byte-ordering problems, you have to concern yourselves with differences in compliance to the C++ standard, differences in the behaviour of library functions, and the fact that the TAs won't be able to help you much with the port.

4. The VC debugger is nothing special

The ddd debugger available on undergrad is fully graphical like the VC debugger and has all the features you expect from a debugger (albeit it's a little slow to start-up), so the advantages of using VC for debugging are minimal. A lot of your debugging (especially in assignment #2) will probably involve examining trace output anyways, which doesn't involve using a debugger.

--

So those are the straight goods on doing Nachos development in Windows. It's possible, but it ain't pretty. Just knowing that some of the top groups last term crashed and burned on assignment #1 doing *LINUX* ports because they couldn't figure out byte ordering problems would automatically make me leery of doing a Windows port.

If I haven't swayed you though, I can point you to the port of Nachos to Windows that was done last term. I've never tried it, so I can't say whether it actually works or not though.

2 General Assignment Information

2.1 My program won't compile on the university computers

Are you in the build.solaris directory?

Are you logged into a Solaris servers like blanch, magnus, fenchel, fitch, etc.? Only some of the servers are set-up to compile Nachos code correctly. In particular, these servers will not compile Nachos correctly: wronski, picard, lassar, and hermite.

2.2 I can compile Nachos, but I can't compile the code in the test directory

Did you compile the coff2noff program?

The test programs will not compile correctly on lassar (which is considered to be an X-server and not supposed to be used for compiling anything). Compiler on another server instead.

2.3 When compiling in the test directory, the program says that it cannot find "coff2noff"

Did you compile the coff2noff program in the coff2noff directory?

When compiling coff2noff, you should use just "make" and NOT "make coff2noff".

2.4 How do I use the debuggers in the undergrad environment?

There are a variety of debuggers available on undergrad. The main ones that people use are gdb (simple text only compiler), xxgdb (simple graphical layer over gdb), and ddd (fancy graphical layer over gdb). Sometimes, purify is also available on the undergrad environment (tracks down memory errors).

Gdb, xxgdb, and ddd are basically the same program, so for simplicity, I'll simply discuss xxgdb (plus, ddd is a little bit slow sometimes on the undergrad computers). The commands for gdb are the same except you have to type in all the commands instead of clicking on buttons. Note, in the follwing discussion, when I say "use ...", I mean you should TYPE it, not click on the buttons. I will say "click on ..." when you should click on stuff. Clicking on buttons is equivalent to simply typing in the command displayed on the button and pressing return. The commands for ddd are all accessible via menus and buttons and stuff. To start the programs, go into the build.solaris directory and run "xxgdb nachos".

To set a breakpoint, use "break name-of-function". For example, "break Thread::Begin" or "break ExceptionHandler". Alternately, you can click on a line in the code window (to the LEFT of the actual text) and then click on the the "break" button to set a breakpoint there. To remove a breakpoint, click the "show brkpts" button to list all of your breakpoints, then use "delete breakpoint-number" to actually remove the breakpoint.

To actually get your code running, use "run arguments". For example, "run -x ../test/halt".

To examine a variable, use "print name-of-variable". Alternately, use "display name-of-variable" to add a watch on the variable so its value is always displayed. Use "undisplay variable-number" to stop displaying a variable.

When the program is at a break point, you can click on the "step" button to run the next line of code. Step will step-INTO function calls. You can also click on the "next" button to run the next line of code. Next will step-OVER function calls. The "cont" button will continue the execution of the program.

Use "backtrace" to get a listing of the call stack. Often, the place where a program crashes is deep in the library code, so it's difficult to know which line of YOUR code caused the crash. You can also click on the "up" and "down" buttons to traverse the call stack (i.e. see which function called your function etc.)

To exit, click on the "quit" button.

These commands should be sufficient for using the debuggers competently. Please note though that knowing how to use a debugger isn't the same as knowing how to debug. I've seen many people blindly step through thousands of lines of Nachos code for hours on end without making any progress on solving their bug. Debugging well requires good problem-solving skills and programming experience. A debugger is just one of a handful of debugging skills you will likely need for Nachos. In fact, for Nachos in particular, tracing, source control, and defensive programming are also often very useful (i.e. use of printfs/couts). Nachos comes with many useful tracing facilities. A debugger is usually good for figuring out simple crashing bugs.

2.5 I haven't changed anything, but when I run make, it keeps coming up with errors

There are two versions of make available on the undergrad systems. The cs354 makefiles are designed for use with GNU's make utility. It's possible that your system is confused and is incorrectly running the Sun's Solaris version of make instead of GNU' s version. This is likely caused because your $PATH variable is not configured properly for cs354 (it might contain too much incompatible stuff from cs241, cs342, or elsewhere). Fixing the .cshrc containing your $PATH is likely messy, so it's easier for y ou just to use "gmake" instead of "make" to compile your cs354 stuff (this forces the GNU version of make to be used and not Solaris's one).

2.6 How do I set-up version control for Nachos?

Various tools like rcs, sccs, and cvs are available on undergrad. Most people use cvs. I have some reservations with cvs because it's difficult to set-up, it automatically performs code merges without telling you (as opposed to using a check-in, check- out model on the repository), and it doesn't have obvious ways for doing certain common tasks (like backing out of changes, etc.). Admittedly, many people tout my reservations as being some of the best features of cvs. Regardless, cvs is probably better t han rcs and sccs (especially since we have instructions available on how to set-up a cvs repository on the course web page). For more information, go to the course web page, and click on "cvs informaton." Kevin Moule also has more cs354 cvs info on his we b page. Kevin Moule's page also discusses things like geting your permissions right on the repository which sometimes screw it up (especially for those people who've changed their UNIX configuration from the defaults).

Remember that there's no point in sticking things in a version controlled repository if you don't use it. Check things into it often, and version of milestones so that you can go back to those versions later if things go wrong.

2.7 Can we use STL?

Sure. Nachos should come with all the data structures that you need to use though (like lists, hash tables, bitmaps, etc.). One problem with STL though is that it creates large binaries, and you'll likely overflow your cs354 quota if you use STL extens ively.

2.8 My system is crashing is _smalloc, _malloc, built_in_new, and/or _new.

2.9 I'm getting the error jump to case label crosses initialization of '...'

2.10 Is there a way to get rid of the ^M at the end of the lines?

You can use dos2unix. Alternately, when you ftp files between Windows and UNIX machines, if you use ascii type transfers (instead of binary transfers), it automatically strips those out.

2.11 Nachos isn't linking correctly for no particular reason. It often complains about LSeek() or something like that.

Occasionally (especially when new files are added to the build process), weird errors pop up. Restart with a clean build. Do a

make distclean
make depend
make

In that order and see if problems still persits.

2.12 How do I break a circular include?

Avoid adding "#include"s in .h files if at all possible to remove circular include problems. To break a necessary circular include, switch to using pointers and forward declarations.

For example, change this:

  #include "synch.h"

  class MyClass {
    Lock theLock; /* Lock variable requires synch.h to be included */
  };

to this:

  /* Forward declaration of Lock class. No need to include "synch.h" */
  class Lock; 

  class MyClass {
    Lock *theLock; /* Pointers are ok with forward declarations */
  };

Then, in your corresponding .cc file, you should add

#include "synch.h"

at the beginning.

2.13 How can I optimize my marks?

2.14 Miscellaneous tips and stuff (should be moved elsewhere)

If you've got a bug--solve it first! Don't hack around it and keep on going. That's the worst thing you can do. Don't use some patchwork solution either. Make sure you know why your fix actually worked. Otherwise, these bugs have a habit of coming up l ater and haunting you.

For assignment #3, it's a VERY GOOD IDEA to make use of the tracing facilities. In particular, print out tracing comments on TLB faults, page faults, and when you swap out, swap in stuff. Make sure to print out detailed useful information in this traci ng output too. It's very useful for debugging your stuff.

Generic Semaphore problems

Here are some possible errors (some were described before by other people already on the newsgroup):

1. Initializing the sempahore to the wrong initial value (you initialize it to one value to use it as a queue and you initialize it to some different value if you want to use it as a lock)

2. Exiting prematurely from the function (especially for error conditions) without V()ing on the semaphore

3. P()ing on the semaphore to enter the semaphore and then never ever exiting the function to release it (stuck in some loop?)

4. Deadlock (Enter semaphore, then wait on another semaphore/lock that's being held by someone else).

As other people suggested, the only way to fix this bug is to continually read through the code, find repeatable test cases, and to add print statements to the actual semaphore code so that you can see what's stuck where, who forgot to release what lock, potential deadlocks, etc.

6 and/or 12 are magic numbers for the file system. If you start having seg faults when you have 6 or 12 directory entries, it suggests that you have a problem with your directory code

Also, be sure that your FileHeader (the parts that are to be persisted to the disk at least) is exactly 128 bytes in size or else you'll get lots of annoying errors.

3 Assignment 1

3.1 When compiling a file (usually exception.cc), I get a lot of errors including stuff like parse error before `0'.

Go to your list of #includes in that file. You likely have the line

#include "syscall.h"

there. Make sure that that line is the LAST file to be included before all your code starts. For more information, see A Note About Syscall.h.

3.2 A Note About Syscall.h.

If you look at userprog/syscall.h, you'll notice that it is used both by userprog/exception.cc and by programs in the test directory. Because syscall.h has these two different usages, it contains stuff that is used by programs from the test directory but not used by exception.cc.

In particular, it redefines ConsoleInput and ConsoleOutput to be 0 and 1. This is ok for programs in the test directory, but this can cause unexpected compiler errors in exception.cc. In particular, it conflicts with machine/console.h because the words ConsoleInput and ConsoleOutput are replaced with 0s and 1s, making the file uncompilable.

So to be safe, in exception.cc, make sure that syscall.h is the LAST file to be included. If you add more include statements to exception.cc, make sure that they come BEFORE syscall.h. Alternately, you can change syscall.h so that it uses something other than ConsoleInput and ConsoleOutput for its constants.

3.3 How much should we worry about the synchronization of file operations and file sharing/locking problems?

For assignment 1, you should THINK about sharing, but since the file system in assignment #1 "piggybacks" on the UNIX file system, you don't actually have to do anything (the UNIX file system will handle all your sharing problems).

So essentially, the answer is no.

Note: there are still a couple of potential sharing problems that might pop up, but if you give these a bit of thought, then you will easily avoid them.

3.4 Can we assume sizeof(void *) = sizeof(int)?

Although it IS true that sizeof(void*) == sizeof(int), I'm not sure why you'd want to do a messy cast like this.

The only reason I can think of for why you'd want to do this is that you want to return pointers for your File IDs and Process IDs. This is the wrong way to do it. This topic should be covered in class at some point, but you can also look at Can we use pointers recasted as integers directly as file or process ids?

3.5 Can we use pointers recasted as integers directly as file or process ids?

If you do this, then user programs can manufacture fake addresses and try to access other processes' files and other sensitive information. Other than being a security risk, it also means that I can crash your operating system really easily by passing in bogus File IDs and Process IDs which your OS will dereference and crash itself with.

So unless you're short on time, use some sort of map or hash table.

3.6 My program seems to be calling the same system call over and over again.

Run Nachos with the "-d m" option to show what instructions are being executed. This will let you know whether the system call is being repeatedly called.

If so, you may have forgotten to increment the PC register before returning from your system call. Remember to also increment the Next PC register as well. Since instructions are all 4 bytes long, you have to increment these registers by 4.

3.7 Do we have to implement ThreadFork()?

No.

It was leftover from previous years when students had to implement threads in addition to the other stuff. Please note though, that during the demos, the TAs may ask you what changes you would need to make to your OS in order to support multiple thread s. So be prepared to answer that sort of question.

3.8 ReadRegister() returns an integer. How do I cast it to a char *?

Short Answer:

Please see your TA.

Longer Answer:

kernel->machine->ReadRegister does return an integer. Although you can recast it to a character pointer, you probably don't want to do this.

Registers will contain a pointer to a memory location in the user address space (i.e. simulated memory). You do not have direct access to memory in the user address space, so trying to access it directly will cause problems. Instead, you have to pass t he memory location pointer to Machine::ReadMem and Machine::WriteMem to actually access the data there. Unfortunately, those methods are private.

So, for example, a pointer to address 0x5 will point to address 0x5 in simulated memory.

If you do

  char *mem = (char *)kernel->machine->ReadRegister(4);
  char firstCharacter = mem[0];

You will access address 0x5 in actual memory, which is wrong.

Instead, you could use the Translate() command (two versions are available--one in the class Machine and another in the class AddrSpace), to translate the virtual address to a physical address.

From there, you can use this physical address as an offset into the simulated memory (kernel->machine->mainMemory[paddr]), to get at the actual data.

3.9 I'm trying to implement Close(), Exit(), etc. in my syscall.cc but these functions are already defined in sysdep.cc, so it won't compile. What's the deal with this?

This is a common gotcha with Nachos (and with OSes in general). It's probably best to wait until Nachos gets covered in class, then those errors will all make sense. Alternately, you can see a TA or read up on the "System Calls and Exception Handling" and "Execution Trace of User-Level Process" section of the Nachos roadmap.

TRITE ANSWER:

As you correctly noted, you have multiple definitions of the Open, Exit, etc. functions. The Open() and Exit() functions exist in both sysdep.cc and your syscall.cc. The fix is that you shouldn't make functions called Open, Exit, etc. since those functions are already defined in sysdep.cc

DEEPER ANSWER:

(Background)

One of the services that an OS provides is protection. If I run a malicious program that attempts to overwrite memory and damage other programs and the OS, the OS should prevent that malicious program from doing anything bad.

So an OS must prevent itself from being compromised by malicious programs. But it's impossible to tell which programs are malicious and which aren't (well, Microsoft has a differing opinion on that matter, but let's ignore that for now). An OS must therefore prevent itself from being compromised by ALL programs. It protects itself by preventing ALL programs from reading memory locations that belong to the OS (where passwords or other important information might be stored), from writing to memory locations that belong to the OS (or programs might be able to change the OS around), or from running any code in the OS (a program might run the "format hard disk" code of the OS).

This is typically done by separating the memory system into two levels: a user-level and a kernel/supervisor-level. The OS (well, the important parts) sit in the kernel. Programs sit in the user-level. Programs can do whatever they want in the user-level--they can overwrite memory, read memory, run whatever. However, they do not have ANY access to the memory in the kernel. This prevents programs from doing bad things to the OS (additionally, the program is prevented from doing bad things to other programs because the user-level is, itself, "partitioned" into different spaces for different programs). By being confined in this way, a program is free to do bad things to itself, but cannot affect the OS or other programs. Unfortunately, this separation of the system into a user-level and supervisor-level means that programs are completely unable to access any part of the OS. They cannot call OS functions, access OS information, or pass any information to the OS.

If that's the case, how does a program get the OS to do anything? Well, if a program does anything illegal, the OS code in the kernel grabs control of the CPU and handles the error. For example, on a divide by zero error, your program gets interrupted, and the OS kernel code for handling divide-by-zero errors starts running.

This mechanism is the same mechanism used to switch from the user-level to the supervisor-level and run OS code. Essentially, a program fakes an error, and the OS code in the kernel will take control and start doing stuff. Since this is such a common thing to do, most CPUs provide an instruction specifically for faking an error. On the MIPS (which Nachos emulates), this instruction is called SYSCALL which generates a system call error.

(how this relates to nachos)

When implementing system calls, you DON'T just make Close(), Exit(), etc. functions. User programs aren't able to call functions in the OS. When one of your test programs calls the "Close()" function, it doesn't call a function in your OS. That's impossible since user-level programs don't have any access to any of the code in the supervisor-level.

So all the programs in the test directory are loaded into and run at the user-level of Nachos (every other part of the OS runs at the kernel-level). When, say, test/matmult calls Exit(), it's calling the function Exit() inside the file test/start.s. The code for that function sits in the user-level, and all it does is execute a syscall instruction to generate a System Call exception.

As mentioned before, on an exception, the OS stops the running program and takes control of the CPU to figure out how to handle the error. Since the OS sits in the kernel-level, an implicit switch from user-level to kernel-level occurs. Then, all the OS code and memory become available. In Nachos, when an exception occurs, the part of the OS that takes control is the ExceptionHandler() function in userprog/exception.cc (all non test/ code is kernel-level). If you look at the ExceptionHandler() code, you will notice that it checks if the exception was a system call or a legitimate error, and if it was a system call, it tries to do something appropriate.

So in a nutshell, DON'T create functions like Close(), Exit(), etc. because they will never get called. To implement system calls, go into the ExceptionHandler() code and add new code that will handle Close() (SC_Close), Exit() (SC_Exit), etc. system call exceptions. Of course, that, in itself, isn't that easy.

The function definitions in userprog/syscall.h are sort of red herrings because they don't actually exist in the kernel.

Anyways, this should all be covered in class eventually, so don't sweat it if you don't understand.

3.10 In the Nachos Roadmap, it says to use Machine::ReadMem() and Machine::WriteMem(). But they are private, and I'm not allowed to change anything in the machine directory. What am I supposed to do?

On every revision of Nachos, the creators flip-flop on whether ReadMem and WriteMem should be made public or private in the Machine object. In this revision, it appears that they have decided to make these functions private.

Nonetheless, these procedures are very useful. I suggest doing some cut & paste and making some sort of equivalent public ReadMemory() and WriteMemory() function calls available in exception.cc.

3.11 Why are ReadMem() and WriteMem() private?

I agree that it's a pain that ReadMem and WriteMem are private. By making them public, writing the io system calls become much easier.

But ReadMem and WriteMem do a LOT of work, and some students forget that. By forcing you to copy the code, you see some of the work that goes on behind the scenes in terms of what the memory system has to do in order to read and write a little bit of memory. Then, when you do Exec() (which is, in my opinion, the hardest part of the assignment), you won't be totally unprepared when you have to write ungodly amounts of similar memory management code yourself.

There are other reasons too, but it's all debatable, which is why Nachos keeps flip-flopping on whether ReadMem and WriteMem are public or private.

So in conclusion, the reason why they were made private was that too many students were getting butchered when they were working on Exec() because they were totally unprepared--they had no idea how the page tables worked or how to map memory or anything. By forcing you to look at how ReadMem() and WriteMem() work (by cut & pasting them), you will at least have an idea of what to do when you start working on Exec(). Also, some groups divided up the work poorly (e.g. "I'll work on the synchconsole and exceptions, Bob will work on file io, and Alice will implement Exec(), Exit(), and Join()"), so this balances out the work a bit and helps ensure that all group members have seen a bit of the memory stuff by the time they finish assignment #1.

3.12 I want to add a public method to OpenFile that returns the file descriptor

We'd prefer it if you created and maintained your own file-id numbers using a hashtable or map of some sort.

Although you can "borrow" your file-ids from UNIX, you'll lose out on things like security (one process will be able to access another process's files) and such. Plus, if you don't write this mapping code now, you'll end up having to write it for assignment #3, so you might as well do it now as oppposed to the end of the term when you have a gazillion assignments hanging over your head.

So if the reason you want to add filedescriptor code to OpenFile.h is so that you can avoid writing the hashtable/map code, it's ok, but you'll lose marks for it.

3.13 How do I read the filename string for Create() and Open() if no size is given?

Strings in C use the ASCIIZ format. The Z stands for "zero." So that means that the characters of the string are stored in ASCII format, one after the other. After the last character of the string, there's a zero. That's how you can tell how long the s tring is--by reading the string a character at a time until a zero is reached.

As a side note, that's why C strings must always be one byte larger than the number of characters in the string--because there always has to be a zero byte at the end to denote the end of the string.

3.14 Should Write() stop printing characters if it encounters a 0 byte?

No. It should write out exactly the number of characters specified by the size parameter.

3.15 I'm getting failed assertions in lib/sysdep.cc.

The error really depends on the type of error that is being generated. One trick that often works is to go to the line right before the assertion failure and add this line:

perror("ERROR HERE");

Right before the assertion failure, and it will print out the error that caused the assertion failure. Often, it's something annoying like running out of quota, permissions not set correctly, non-existent file, or something like that.

3.16 I'm getting failed assertions in lib/sysdep.cc related to incorrect file ids or something like that. But I'm positive that my file ids are correct.

You may have accidentally closed the file handle without knowing it (through an incorrect copy constructor or something like that). Put a breakpoint in locations in sysdep.cc that might close a file handle and see if that's the case.

3.17 Should there be a limit on the number of open files?

It's up to you. Most OSes do have limits. Document whatever you do. Your choice should be REASONABLE though. Can your OS really handle as many open files as you claim?

3.18 Can you go over how we should write our system calls?

A system call handler should:

  1. It should get the parameters for the system call by reading the appropriate registers.
  2. It should do whatever the system call is supposed to do
  3. It should set the appropriate registers with the return value of the system call
  4. It should increment PCReg and NextPCReg (by 4 since instructions are 4 bytes)
  5. It should "return" from the switch statement in the ExceptionHandler (unless it's something that doesn't need to return like Exit() or Halt() in which case a "break" is ok).

3.19 I have a bus error on the line *paddr=pfn*pagesize + offset

You might be calling the translate method incorrectly.

This is incorrect:

int *physAddr;
Translate(vaddr, physAddr, 1);

Translate writes the translated address into the memory location pointed to by paddr. In the above case, you are passing an uninitialized pointer into Translate. This is correct:

int physAddr;
Translate(vaddr, &physAddr, 1);
char characterIWant = kernel->machine->mainMemory[physAddr];
//woohoo!

3.20 What do we do if a page contains both read-only and writable segments?

A page can be either completely read-only or completely writable. You cannot make part of a page readable and part of a page writable. So there are two solutions to this:

1. You can modify the configuration of the ld-linker to output code where the segments are page-aligned.

I have read the docs on this. It requires a bit of knowledge about linkers and stuff, but it is doable and can potentially save you time mucking around with AddrSpace math.

2. Just allow different segments to cohabit the same page, but if r/o data and r/w data cohabit the same page, make sure you don't mark the page as r/o.

This isn't the best solution, but it works. Although it is not the BEST solution, it is a VALID solution because a user program will still be unable to crash the OS and muck around with other user programs. A user program WILL be able to mess itself up, but it's not up to an OS to protect a user program from itself (unless it's a really nice one).

Note: Despite what I just said up there, if at all possible, your OS should try to mark pages as r/o if it makes sense to do so.

3.21 I'm a little confused about address spaces. How is it possible to have multiple Nachos programs with 4k address spaces running when you have only 4k of RAM?

This is the sort of question where it's better to ask a TA or prof directly. Anyways, this explanation will probably cause more confusion than help, so it may be better to skip reading this. It looks at the idea of address spaces from a more abstract point of view.

With virtual addresses, each process has their own view of memory. Each process essentially thinks it has the whole computer to itself and can access all the memory.

So on a MIPS machine (which Nachos is trying to emulate), each program thinks it can access all the memory--all 4 Gigabytes of it. Since Nachos has only 4k of memory, this is clearly not the case.

Even though each process thinks it has access to the complete 4 gigabyte address space, most of the addresses don't actually refer to anything useful.

In Nachos, the AddrSpace object contains the mapping from virtual addresses to actual physical memory addresses in its pageTable. Since Nachos has only 4k of RAM, most of the mappings from virtual addresses to physical addresses are empty (page 300 maps to nothing, page 301 maps to nothing, page 302 maps to nothing, etc. etc.)

So storing the mappings for 4 GB of virtual address space is sort of wasteful.

One solution involves storing programs at the start of the address space. So a program that is loaded will have its code and data start at page 0 and go up to page 99. Then, you only store the mappings for virtual pages 0 to 99. For pages above 99, you don't bother storing any mappings.

To do this in the AddrSpace object, you would set numPages to 100, and then have the pageTable be an array of 100 page table mappings (assuming that the program uses 100 pages).

Since each program is of a different size, you have to do some messy mucking around to ensure that the pageTable array is of the proper size and that numPages is set correctly for each program loaded

There is another solution. In assignment #1, Nachos has only has 4k of memory, and no program can be loaded that is bigger than 4k because that's how much memory you have (Note: Your Nachos should be able to handle > 4k programs if it is configured to have > 4k of RAM). Since no program can take up more than 32 pages, you can just allocate 32 pageTable mappings for each program. For programs < 4k, this is a little wasteful because many of the mappings will be empty, but whatever.

To do this in the AddrSpace object, you would set numPages to always be NumPhysPages, and have the unused mappings be empty mappings (for example, if a program uses pages 0-29, page 30 will map to nothing and page 32 will map to nothing). You define an empty mapping simply by setting the valid bit of a page table entry to FALSE.

Of course, there are any number of different solutions. You could put an upper bound on the sizes of programs (say, 300 pages), and just allocate 300 pageTable mapping entries for each AddrSpace.

And once you get into assignment #2, you can do stuff like multi-level page tables etc.


> I am a little confused about setting numPages = NumPhysPages.  From what I
> understand, the process that's running will always stay in memory, so no one
> process can take all NumPhysPages, they are allocated according to the
> required size.  Say we have 2 process running, and we are creating a new one,
> and up to now, the 2 process occupied 19 frames.  Then the process 3 will be
> loaded into frame 20.  If process 3 takes up 6 pages, there will be 31-25+1=7
> pages of empty mapping.

We're disagreeing on what we mean by mapping. You are using the term
"mapping" to refer to which frames are occupied. In the example you
mentioned above, seven frames will indeed be free and "unmapped."

When I use the term mapping, I'm referring to the page table translation
entries that map virtual addresses to physical addresses.

So let's say we have two processes: program1 and program2. program1 takes
up three pages and program2 takes up four pages. This is how it might be
mapped into memory:

   program1
   --------           MainMemory
   page0 --------\    ----------
   page1 -------\ \---frame0
   page2 -----\  \----frame1
   page3 X     \------frame2
   ...           /----frame3
   page31X      / /---frame4
               / / /--frame5
              / / / /-frame6
   program2  / / / /  frame7
   -------- / / / /   frame8
   page0 --/ / / /    frame9
   page1 ---/ / /     frame10
   page2 ----/ /        ...
   page3 -----/       frame29
   page4 X            frame30
   page5 X            frame31
   ...
   page30X
   page31X

When I refer to mappings (or the more correct terminology is
TranslationEntry), I am referring to the lines that map the pages of one
process to the actual physical memory frames in main memory.

Since program1 takes up 3 pages and program2 takes up 4 pages, the total
number of free frames is 32-3-4 = 25.

Each process has their own view of memory. Each process thinks that its
memory begins at page0 (address 0). It thinks that its memory goes up to
4GB in size. Storing the TranslationEntries for 4GB of addresses (32
million Translation Entries) for each process is clearly inefficient.
Instead, we'll only store the first 32 TranslationEntries for each process
(so we set numPages to 32). 32 TranslationEntries means that a process can
have address mappings for at most the first 4KB of address space.

Since each program is much smaller than 32 pages in size, most of these
TranslationEntries are invalid (they map to nothing). These empty
TranslationEntries are marked as Xs in the diagram.

Note that program1 is only 3 pages in size, but it still uses 32
pageTable TranslationEntries. Similarly, program2 is only 4 pages in size,
but it still uses 32 pageTable TranslationEntries. Notice that the amount
of free memory is still 25 frames. The fact that the two processes have 32
pageTable TranslationEntries does not affect the actual amount of memory
used by the programs. program1 still uses only 3 pages/frames and program2
still uses only 4 pages/frames.

> I am a little confused about setting numPages = NumPhysPages.  so no one
> process can take all NumPhysPages, they are allocated according to the
> required size.  

Right. So that's the point. Because no one process will ever use more than
NumPhysPages, if we give each process NumPhysPages TranslationEntries in
its pageTable, it will always have more than enough TranslationEntries
to handle the translation from pages of the virtual address space to
actual physical memory frames. This is due to the fact that no process
will use more than the first NumPhysPages of pages in its address space.

> I am a little confused about setting numPages = NumPhysPages.  From what I
> understand, the process that's running will always stay in memory, so no one

A running process will always stay in memory. Once it has exited though,
it should be removed from memory and have its frames freed.



Just for comparisons sake, here is the above diagram except where the
number of TranslationEntries is exactly the number of pages needed by the
program (which I called solution one in the original post):

   program1
   --------           MainMemory
   page0 --------\    ----------
   page1 -------\ \---frame0
   page2 -----\  \----frame1
               \------frame2
                 /----frame3
                / /---frame4
               / / /--frame5
              / / / /-frame6
   program2  / / / /  frame7
   -------- / / / /   frame8
   page0 --/ / / /    frame9
   page1 ---/ / /     frame10
   page2 ----/ /        ...
   page3 -----/       frame29
                      frame30
                      frame31

If this explanation still confuses you, I suggest seeing one of the TAs.
These sorts of discussions are difficult to do over a newsgroup or e-mail.

3.22 I think I wrote my process creation stuff correctly, but it's not working right.

Here is a list of methods and functions that should never be called by your code. If you code calls any of these methods or functions, your implementation is likely wrong.

Another good indication that your code is wrong is if your code contains this line:

kernel->currentThread->Fork( ... )

This is due to the fact that Fork shouldn't be called on the current thread but on the new thread being created (don't confuse it with UNIX's fork).

3.23 So how do I set up a new process running?

The scheduling code is already written for you. Therefore, you NEVER have to explicitly switch threads or invoke the scheduler. To start a new process in Exec, you simply have to

  1. create a new process (a process is composed of a Thread and AddrSpace)
  2. set it up so that it is runnable (create a stack, and give it something to run when the process starts up)
  3. then add it to the ready-to-run queue

It should then return. The scheduler will automatically take care of scheduling the process to run.

Thread::Fork( ... ) does most of what you want to do. If you read the comments for Thread::Fork(...) everything should all fall into place hopefully.

3.24 How do I pass the strings to the new program in ExecV?

Remember that on the MIPS, arguments are passed in registers, NOT on the stack.

So if you look at the signature for "main"

void main(int argc, char *[]argv)

You will see that when main starts up, r4 should be initialized to argc and r5 should be initialized to argv.

You should also recall that in C/C++, arrays are actually implemented as pointers to arrays.

So in the following code

int MyArray[5];

MyArray is actually a POINTER to an array of five integers. MyArray is NOT the actual array itself.

Similarly,

char * argv[]

means that argv is a POINTER to an array of strings (char stars). argv is NOT the actual array itself. (so to be technical, argv is a pointer to an array of pointers to character strings.)

That's why argv fits inside a register. argv is a pointer to an array, not the actual array itself. You will have to create this array somewhere else.

So where is this somewhere else?

Where you decide to put the strings and the argv array is an implementation decision for you to decide. Two good places to put them are at the top of the stack or at the bottom of the stack. In either case, you should expand the address space to provide space for these strings and arrays and stuff. You should never exhaust your stack space because by expanding your address space you guarantee that the stack is always roughly the same size.

3.25 How do I initialize the registers of a newly started process

So how do you initialize the registers? Surely Nachos would have some convenient place for doing this? Right when the code in AddrSpace is first Executed on start-up, it should initialize the registers first, shouldn't it? It probably needs some thing, like some InitRegisters() function or something.

3.26 I'm getting Undefined Reference errors for ExecV in my test programs

You have to modify test/start.s to include an ExecV() function that will trigger a syscall. You can pretty much cut & paste the Exec code there.

3.27 When my program reads from the console, it doesn't actually get any of the characters I type until I press enter on the keyboard. Is that ok?

Yes.

3.28 When compiling start.s, I'm getting errors like Error: Rest of line ignored. First ignored character valued 0xd.

0xd is the '\r' character. In Win/DOS, ends of lines are indicated with the character sequence "\r\n". In UNIX, ends of lines are indicated with just "\n". (There are those oddball Mac people who use "\r".) You were likely doing development in Windows and then copied the files straight to UNIX without stripping out the \r. The extra \r is making the UNIX assembler confused. To tell for sure, you can load up the file in vi, where the \r will appear as a ^M. You should see Is there a way to get rid of the ^M at the end of the lines?

3.29 It seems like time-slicing is already implemented

The Nachos code supplied to you comes with a fully functional, round-robin, time-slicing scheduler. You do not have to implement time-slicing. You only need to choose an appropriate quantum for the time-slicing.

3.30 How do I make my thread yield while it is waiting for synchconsole input/output etc.?

You are thinking too much about the Nachos threading stuff. The Nachos scheduler is already implemented, and though it isn't perfect, it works pretty much as you would expect normal threading stuff to work. So in synchconsole, when it P()s on a semapho re, it WILL yield control to any other threads in the ready queue automatically. If you think too much about what's actually happening, you'll miss the point that the Nachos threading and concurrency library was designed to behave like real threads.

3.31 coff2noff is giving me Unknown segment type: .sbss errors.

Yeah, the linker script is incorrect. Go into test/script. Change these lines:

  .sbss  . : {
    *(.sbss)
    *(.scommon)
  }
  .bss  . : {
    *(.bss)
    *(COMMON)
  }

To this:

  .bss  . : {
    *(.sbss)
    *(.scommon)
    *(.bss)
    *(COMMON)
  }

3.32 How do I choose the time-slice quantum

Well, you could change the timer, but that isn't the best way of doing it. Perhaps when the timer triggers, you don't necessarily need to switch threads?

And how big should the quantum be? Well here are some factors you should consider:

  1. System Efficiency
  2. More specifically, what is the ratio of time spent in the running program vs. time spent doing context switches?
  3. Also, is your scheduling algorithm so complicated that it itself becomes a bottleneck in the system?
  4. Fairness
  5. Responsiveness
  6. More specifically, can a process hog timeslices? Can it fool the OS into giving it more time than other processes by using up most of its time slice but releasing right before it is going to get time-sliced out?

You don't necessarily need to solve all of these issues with your choice of quantum and time-slicing policy as long as it's something reasonable. You MUST justify your decision in your design doc. Ideally, your justification should include statistics and other analysis (you may have to modify the machine/stat stuff to get the stats you need, but probably not).

Just to let you know in advance, the following justifications are unacceptable (well, they might be worth a couple of marks at best):

  1. It seems to run ok
  2. 100 ticks seemed like the correct amount
  3. 100 ticks lets you run 100 instructions which is plenty
  4. Variations of the above

You should note, in particular, that a "tick" isn't actually a unit of time. It's just some arbitrary unit chosen by Nachos. A tick isn't a millisecond, it isn't a microsecond, it's the time needed to run user instruction.

3.33 How do I call Thread::Fork()?

FIX THIS MING!

class Kernel {
...
static void StartMe(AddrSpace *thisSpace);
...
};

void Kernel::StartMe(AddrSpace *thisSpace)
{
...
}

> Our code is:
>    kernel->currentThread->Fork( thenewprocess->space->Execute, NULL );

TECHNICAL ANSWER:

Execute() is a member function of the class AddrSpace. A member function
doesn't make sense outside of the context of the object it belongs to. So
you can't really take the "address" of a member function. You have to take
the address of both the member function AND the object. The C++ code to do
this is really messy, so the Nachos designers made the Fork command
instead just to expect a regular function (a freestanding function that
isn't part of an object). You have to construct a function that takes one
parameter and will call space->Execute() when it is called.

MORE USEFUL ANSWER:

Ok, there are several things wrong with that piece of code. 

1. thenewprocess->space

If you look at AddrSpace::Execute(), you'll see that the first thing it
does is that it sets the address space of the currentThread to refer back
to itself. You shouldn't link up the Thread object with an AddrSpace
object because this will be done when the new thread starts executing and
calls AddrSpace::Execute().

2. kernel->currentThread->Fork(...)

A Thread object's Fork() command will initialize the Thread, set up new
stacks, and add it to the scheduler. By using
kernel->currentThread->Fork(...), you are taking the currently running
thread, and creating a new stack for it and adding it again to the
scheduler. You want to take the new Thread object and create a stack for
it, not for the currentThread.

So use "thenewprocess->Fork(...)" instead.

3. Fork( ..., NULL );

Fork takes a function as its parameter. Once the new thread is forked off
and started, it will run this function that you specify. You can't
directly pass space->Execute() as a function. So you somehow need to
create a function that will call space->Execute(). You can then pass this
function as the parameter to Fork. 

3.34 So how exactly do I go about implementing Exec() again?

Note: Load your program into the address space before forking the Thread. Can you figure out why?

3.35 What sort of synchronization should there be on console input and output?

It's up to you. Just justify it in your design doc.

3.36 Is it ok if my OS hangs when all the running processes have exited (but none have called Halt())?

Yes.

3.37 I don't understand what the Read(), Write(), Open(), Close(), etc. system calls are supposed to do

3.38 How do we get the hash table to work?

MING Fix this too!

Well, using the hash table gets a little messy, and there are various techniques you can use for using it.

Since all you probably want to know is the quickest way to get it to work, here it is:

So in the hashtable, you want to map integers to OpenFile*.

Although it would be nice if you could just put OpenFile pointers in the hashtable directly, the design of the HashTable doesn't support that.

Instead, create some sort of struct that actually contains the OpenFile pointer and the integer that refers to it.

struct SomeStruct {
  OpenFileId id;
  OpenFile * file;
};

So instead of storing OpenFile pointers in the HashTable, you store SomeStruct pointers in there instead.

Since you search using OpenFileIds, the OpenFileId is your key.

So this is what you want:
typedef HashTable <OpenFileId, SomeStruct*> *TheHashTable;

Then, how the functions Hash() and GetKey() should be defined are easy to figure out.

So in the HashTable, the Key is the thing you use to search for things in the hash table. In this case, it's the OpenFileId (you supply an OpenFileId and it returns the SomeStruct*)

OpenFileId GetKey(SomeStruct *x) should take a SomeStruct * and return the search key (i.e. the OpenFileId that's inside the SomeStruct *).

The unsigned Hash(OpenFileId x) is supposed to take a key (OpenFileId) and return an integer that will be used as the hash value (if you don't remember what a hash is, you should review it in some data structures book). Since OpenFileId is already an inte
ger, you can just let Hash() return the OpenFileId directly without change.

Anyways, the unfortunate part of using this set-up is that the hashtable no longer stores OpenFile* but SomeStruct * instead. So to insert, you have to do this:

SomeStruct *hashEntry;
hashEntry->id = id; /* Whatever id you want to use to refer to the file */
hashEntry->file = ourfile; /* whatever the file is */
hashTable->Insert( hashEntry );

Well, using the hash table gets a little messy, and there are various
techniques you can use for using it.

Since all you probably want to know is the quickest way to get it to work,
here it is:

So in the hashtable, you want to map integers to OpenFile*.

Although it would be nice if you could just put OpenFile pointers in the
hashtable directly, the design of the HashTable doesn't support that.   

Instead, create some sort of struct that actually contains the OpenFile
pointer and the integer that refers to it.

struct SomeStruct {
  OpenFileId id;
  OpenFile * file;
};

So instead of storing OpenFile pointers in the HashTable, you store
SomeStruct pointers in there instead.

Since you search using OpenFileIds, the OpenFileId is your key.

So this is what you want:
  typedef HashTable <OpenFileId, SomeStruct*> *TheHashTable;
  TheHashTable *HT = new TheHashTable(xGetKey, xHash);      

Then, how the functions Hash() and GetKey() should be defined are easy to
figure out.

So in the HashTable, the Key is the thing you use to search for things in
the hash table. In this case, it's the OpenFileId (you supply an
OpenFileId and it returns the SomeStruct*)

OpenFileId xGetKey(SomeStruct *x) should take a SomeStruct * and return
the search key (i.e. the OpenFileId that's inside the SomeStruct *).

The unsigned xHash(OpenFileId x) is supposed to take a key (OpenFileId)
and return an integer that will be used as the hash value (if you don't
remember what a hash is, you should review it in some data structures
book). Since OpenFileId is already an integer, you can just let Hash()
return the OpenFileId directly without change.

Anyways, the unfortunate part of using this set-up is that the hashtable 
no longer stores OpenFile* but SomeStruct * instead. So to insert, you
have to do this:

SomeStruct *hashEntry;
hashEntry->id = id; /* Whatever id you want to use to refer to the file */
hashEntry->file = ourfile; /* whatever the file is */
hashTable->Insert( hashEntry );

3.39 Afer the last thread has exited, the resources for the last one don't get freed up.

It really isn't that much of a problem. Consider what would happen to a real OS if this were to happen.

Consider Windows. Let's say that all the threads in Windows were to try to delete themselves. If all the threads delete themselves, you cannot load new programs, you cannot run anything, you cannot do anything at all (the actual GUI of Windows runs in a thread too). If there are no threads running, then there is no code available that will actually do anything (well, technically this isn't quite true, but let's ignore that fact). So essentially, by deleting ALL the threads, you have shut down Windows.

If the OS has shut down, and you can't do anything with it, then who cares if the last thread stopped running but wasn't able to actually free up its memory? You can't do anything with that memory anyways since the OS has shut down. So it's no big deal. (note that the last thread in an OS CAN shut itself down. The main problem is that it can't delete itself, so it's memory can't be freed. This is because a thread can't delete itself while it's running (freeing up memory while it is running code that exists in that memory is bad). As you recall, the way around this is that a thread can tag itself for deletion, and then shut itself down, and then the next running thread will delete it. The very last thread in an OS can still tag itself for deletion and then shut down, but there won't be a new thread starting up to actually delete it).

3.40 Common stack memory errors for assignment #1

These are the most common memory reference errors that
I've seen other people make so far:

INCORRECT:

char *buffer;
for (int i=0; i<size; i++)
  ReadMem( vaddr + i, 1, &buffer[i] );

CORRECT:

char buffer[300];
for (int i=0; i<size; i++)
  ReadMem( vaddr + i, 1, &buffer[i] );

-------

INCORRECT:

int *paddr;
Translate(vaddr, paddr, 1);

CORRECT:

int paddr;
Translate(vaddr, &paddr, 1);
kernel->machine->mainMemory[paddr];

-------

INCORRECT:

char *getString( vaddr )
{
  char buffer[300];
  for (int i=0; i<size; i++)
    ReadMem( vaddr + i, 1, &buffer[i] );
  return buffer;
}

3.41 How do I free up the memory of a thread/address space?

4 Assignment 2

4.1 How do you turn off time-slicing?

Although the assignment #2 tips suggest turning off time-slicing, this is not necessary. If you are sure to only run test programs that consist of only a single process, you will not have any problems with weird multi-process bugs.

4.2 All my string stuff has stopped working and everything is screwed up

One possible problem is that you may have inadvertantly disabled string support in your OS. In the Nachos makefile, they give examples of how it must be changed to enable the TLB; however, you cannot copy these examples verbatim. The example given ther e is for a Nachos with TLB support but without string support. The DEFINES in your Makefile must include -DRDATA to include string support. If you accidentally removed, put it back.

4.3 There's some assertion triggering in translate.cc about pageTable and TLB both being non-null

A CPU can handle paging using page tables (like the x86 chips which actually has an internal hardware TLB) or use a TLB (like every other modern microprocessor). A CPU will not have both. That's why the assertion is triggering.

If you look at the constructor for Machine, it seems that pageTable is being properly initialized to NULL, so what's up? If you look in AddrSpace::RestoreState(), you will see that it sets the value of the pageTable variable there (whenever a new proce ss is time-sliced in, AddrSpace::RestoreState() will be called in order to configure the CPU to use the page tables of the new process). Since the "new CPU" no longer uses page tables but a TLB instead, this is no longer makes sense, so you can change Add rSpace::RestoreState() to stop doing that.

4.4 My Nachos seems to run fine when running a single process, but it chokes while running multiple processes

When you switch processes, do you clean out the TLB entries belonging to the previous process? If you don't, then the CPU may start using TLB entries belonging to a different address space, therefore causing trouble.

Do you save the dirty, used, etc. bits from the TLB during a process switch? If you don't copy these bits from the TLB into your page tables, the page tables won't have the latest page usage information from the TLB and may incorrect decisions about ho w to handle memory.

Good places to add "hooks" for a process switch are AddrSpace::RestoreState() (called when a process gets switched in) or AddrSpace::SaveState() (called before a process gets time-sliced out).

One side note: If you do modify AddrSpace::RestoreState() or AddrSpace::SaveState(), you have to be sure that you are deleting your old address spaces in the proper places. In particular, you definitely should not delete Addrspace objects in the SC_Exi t system call handler. If you do not know why, you should read the appropriate section in the assignment #1 questions. Alternately, if you're running out of time, a really bad hack is to set the kernel->currentThread->space to NULL in SC_Exit before you d elete the AddrSpace. This will generally fix the problem, but it's a really bad hack and wouldn't work in any real OS. Usually the TA won't notice though.

4.5 How do I implement expandable stacks?

5 Assignment 3

5.1 How is the datasectors[] variable of the FileHeader object written to disk?

5.2 The assignment says to support files up to 128k in the file system, but it's not practically possible to get files of that size

That is true. Your data structures should support files up to 128k in size, but you probably won't be able to create such a file.

5.3 Do we need a mechanism for shrinking files?

No.

5.4 What is the optimum behaviour for Remove?

5.5 What file synchronization mechanism should we implement?

5.6 Do we really need to implement all these doubly/triply indirect pointers?

6 Lectures

6.1 What are some things I should know for the exam?

If the exam was written by Professors Zima or Burkowski, it is advisable for you to know what giga- is, to know what mega- is, to know what kilo- is, to know what milli- is, to know what micro- is, to know what nano- is, to know what pico- is, and to k now powers of two up to a gigabyte. No, I'm not kidding.