STUDENT DOCUMENTATION: MULTIPROGRAMMING & SYSTEM CALLS

Ajay Salpekar

5^th February 2004

1.              Why are we on this Earth?

This student documentation is written for the following purposes:

1.              To provide a ready reference for System Calls and their Nachos-specific implementation, in conversational yet cogent language

2.              To explain concepts early on so you don’t have to spend time scrounging for information, and instead, can concentrate on design, perhaps even coming up with a more optimized operating systems code that performs better

3.              To answer certain intuitive questions that arise when confronted with the system calls project for the first time – from basics like ‘What files would I have to modify?’ to more frightening ones like ‘It’s three hours to submission deadline, so do I really have to write new code that keeps track of Active Threads?!’

2.              System Calls, but why?

You’re building an Operating System here, layer by layer. The most basic is the Locks and Condition Variables that you need to provide Mutual Exclusion – to share OS resources. In this project, you’re implementing Multiprogramming, which will use the layer you built in the previous project. What is the goal of multiprogramming? It is, to allow multiple User Programs to run simultaneously, while sharing OS resources. Let us remind ourselves that we build OSes so that users can use them. Hence – System Calls. In order for a user program to use any function the OS provides, there must be a standard interface provided to the user – so the user can just use these functions that your OS provides, in a standard manner, with known arguments. Now, these are not standard functions which would allow userprogs to use (maybe even abuse) OS resources arbitrarily. These syscall functions will transfer control form the user mode to the kernel mode, while ensuring that bad arguments are not being passed (since you are coding for the syscalls, you’ll need to put in these argument checks).

            Consider a user program using the system call Exec(“../test/helloworld”), upon running, this causes a new process to be created, using the executable file ‘helloworld’ from the ‘test’ directory. Note that any user program will use Exec syscall in the same manner – hence the standard interface. The user need not bother about how you (the OS) interprets/copies/handles the syscall and the parameters the user supplied (namely, the name and path of the executable file). The same applies to every other syscall as well.

            As far as the functioning of a general syscall goes, it works like this: a hardware ‘trap’ is used to switch to kernel mode, and this ‘jump’ will be made without knowing in advance what function is to be performed. The OS syscall handler code will actually need to look in a standard location (like say a machine register), recognize the syscall, and execute accordingly. The syscall may or may not return a value to the userprog.

3.              What Files do I modify?

Putting this section right up here at the beginning seems silly I know, but you’d need to read this before you read the Nachos-specific implementation of syscalls that follows.

syscall.h

You will find the syscall numbers and the prototypes (not the actual syscall function) of the syscalls here. So the syscall function call in your user program must follow exactly this format. s

exception.cc

Please, learn and love this file. It is yours to hold, modify, create, and mess up. At the end of the fourth project, this file was two thousand lines long in our case. Right now it’s a few hundred. This is where the actual code for your syscalls will go.

So your Exec syscall could be a function called ExecSyscall() in this file. This is distinct from the Exec() function prototype you will have in syscall.h. Exec() is what the user sees and uses. This call generates a trap to kernel, which is reflected by the use of the ExecSyscall(). This should be clear after the next section.

start.s

This is assembly level code, and is mostly copy paste work for you guys, whenever a new syscall is to be incorporated into Nachos. The syscall number is copied to machine register R2 by the stub. Additional arguments will be copied to registers R4, R5 and R6. Certain syscalls (like Exit()) have return values, which will also be stored in R2 upon return from kernel more.

You may need to tinker with progtest.cc and perhaps even completely remodel addrspace.h and addrspace.cc if the project so requires. Of course, you’ll also need to modify the usual suspects system.cc and system.h. And, as a rule for life, don’t touch the machine directory.

4.              How Syscalls work (in Nachos!)

This is covered very well in class, and on the Nachos tutorial on the website, so as per the purpose of this documentation, I shall try to make this follow the Nachos implementation as closely as possible. This explanation is not as explicit as it could have been, for the reason that you, in this class are required to think for yourselves and discover things on your own. This explanation merely hopes that a head start would help you come up with smarter OS code, instead of just barely managing to make it work.

            The Nachos MIPS machine sees your syscalls in the user program and during runtime, will cause a trap to Nachos kernel. This is where the handoff occurs from User Mode to Kernel Mode (just like you discussed in class). During the execution of the behemoth Case-Switch structure in OneInstruction() (the function that recognizes and dispatches the actual execution), the exception is raised through the function RaiseException() (an exception may be due to a syscall, or an error, look in machine.h for details). As a result, the ExceptionHandler() function (in exception.cc) is called by RaiseException().

            Now for instance, consider that the exception is due to an Exec syscall (the exception number will be 2, look in syscall.h, this means that the integer 2 will be pushed into register R2). The ExceptionHandler() function will then call your syscall function - ExecSyscall(), which will execute the logic required to create the new user process. The argument (in this case the filename) is to be passed on to this function; so think hard and devise means to get the filename from the userprog into your kernel syscall function. Standard practice (for the rest of your 402) to figure out a technique to do something in Nachos: Scavenge from Nachos itself. Now this may sound bad, but it’s really a good way. When in doubt, look at Nachos code itself. I’m sure you did this out of desperation in the first project anyway. This way, you learn more about Nachos code, and you get your solution too. Of course, there is effort involved, because you won’t be able to directly use Nachos’ technique; you will need to modify it to suit your purpose. So look at all the other syscalls that your Nachos comes inbuilt with, and look at User Mode – Kernel Mode interaction in baseline Nachos, and see what techniques you can pick up.

5.              Syscalls – The beast itself

There isn’t just one way to implement a syscall, there are many. By this I mean the logical steps involved, and not the resplendent variety of code lines you may come up with. Of course, the syscall will do exactly the same thing in everyone’s implementation, but there is still plenty of specific design that goes into it - subtle differences in logic flow can mean perceptibly different code. What follows is a coarse grained explanation of the syscall logic, in plain English: you’re supposed to break this into sequential steps, and find devious means to implement what you ‘say’, in Nachos.

5.1.      Fork & Exec

Before you proceed, you should tell yourself that Nachos Fork/Exec are distinct from Unix Fork/Exec – knowing one will help you in the other, but the syscall purpose and implementation is very different. Now since that guised disclaimer of sorts is out of the way, let us see what we expect from our Fork syscall.

Say this out loud if you have to: in Nachos, we Fork a new Thread, and we Exec a new Process. So what Fork does, is it creates a new Stack, in the same address space as the parent process. Now a process, very, very crudely put, is an executable file. Since that executable file can have many functions in it, there can be many threads in a process, each with its designated (UserStackSize in Nachos is 8 by default) pages of stack.

So if there are say three threads in a process, then currentThread->space on all these three threads will result in the same pointer, because they all share the same address space.

5.1.1.   So now what does Fork have to do?

The Fork syscall function is supposed to give this infant thread an address space, which is of course the address space of the parent process. Then it’s supposed to give this thread its own set of stack pages. And finally, you must fork this new, ready-to-go thread with an internal Nachos kernel fork (because every userprog thread must be reflected by its corresponding kernel-mode thread). So, usually, the last thing you do inside your Fork syscall, is to call the Nachos thread fork, jumping control to another function, which is the reflected thread in kernel mode. Within this kernel thread, you will need to handle registers, and the commands to make the MIPS machine actually run this forked code. Please be very clear about this, discuss this amongst yourselves, and with the graders too.

5.1.2.   And what about Exec?

Exec will open up your user program from its file (check out filesystem commands) and create a new address space for this new process (now check out the AddrSpace functions in addrspace.cc/h and StartProcess function in progtest.cc to get a good idea – always look to Nachos for help). Now again, you must Nachos-fork a corresponding kernel thread for this new process. This you should know – every process has one thread by default – the main() thread in the executable file or the .c file rather. So if in addition to the main() function, you have say three more functions in your userprog, then within Nachos, your userprog will constitute four threads. Clear to everybody? Yes or no?

5.2.         Now to Exit

Exit is usually the longest syscall in terms of number of code lines. It’s also the most messy, and yet, it’s easily the most fun, because there’s more logic to it and less Nachos-specifics. With Exit, you need to consider all logical cases possible. Is the thread that is exiting the last thread in its process? Now is this process the last userprog process in Nachos? These possibilities are important because when the thread exits, you as the OS programmer have to take care of the mess it leaves behind – its stack, or in case of the last thread of a process, its entire address space. You may have to delete or deallocate these legacies. What you must do is, separate these cases in your function, and treat them separately. A lot of the code in these cases may be repetitive, so try to optimize (after you get it working of course).

 There are other questions you must ask yourselves: How do I finally kill this thread? How do I finally terminate Nachos when I need to? How do I know whether there may be other threads being serviced? How do I determine when there are no more threads left? You may have to keep track of how many active threads there are, in order to ensure correct Nachos halting.

            You will have to tinker around with Exit quite a bit. Try running your code after ever design addition, so you know which of the actions causes your Nachos to misbehave on you.

5.3.         Oddments

You may or may not be required to implement syscalls for Acquire/Release/Wait/Signal/Broadcast. But it doesn’t hurt to know a little more. Not much anyway. So just like your userprog calls Fork and Exec, it could call the above syscalls. Think about how you may go about implementing these – it’s rather abstract at first. Even simple things seem dense. For example, how are you going to get the userprog to pass the actual name of the lock to your kernel? Some liberal typecasting might be required. Think about it.

6.              Accessories?

            Standard instruction – Lock down everything, almost everything. In each of your syscalls, you’re either accessing/modifying sensitive shared resources (stack, address space) or you’re checking shared variables (counters, thread numbers and the like). So use locks appropriately, especially in Fork and Exec where you are assigning address spaces and creating your new stack.

Another thing - you may or you may not need to create this abysmal, yet useful thing which we refer to as a ‘Process Table’. For this project, this design decision depends on how you’re keeping track of the threads. You know you’re going to keep track of each process with its address space pointer; but what about the threads? What is it that threads have/own/possess that can be used to identify them?

            I suggest you spend some overtime in gdb/ddd looking at the entire execution flow of Nachos. You can actually spend hours inside the execution of a simple test program because each instruction executes with probably fifteen or so internal Nachos-function calls (You will see the MIPS simulator that Nachos sits on, work its way through the instruction, calling function after function, simulating a real live hardware platform). You will probably need to do this anyway because debugging the second project is rather heavy work. But this is the best way of understanding Nachos and how it works as a functional Operating System on a MIPS simulator.

            The ddd ‘Backtrace’ is a very useful tool. Use it to see where your errors and loops occurred. Use the data displays liberally – ddd actually lets you see the data members of each instance of an object or structure with arrows and data fields, which can be expanded or collapsed. Also try inferring things with the stack display command in gdb – it helps you follow pointers well and track down annoying segfaults.

            Bullet Proof. Bullet Proof. Bullet Proof. It’s good discipline, and makes your OS watertight. And in some cases, graderproof. On the whole, it’s good OS programming. In every function you write, put in checks for null pointer assignments, nonexistent files, nonexistent allocations of memory, and anything else that might bring down your code. Be systematic about it; try to tear your own code apart – that’s the best way. And please, do this only after you’re sure that everything else works okay.

            Lastly, the test cases for this project are probably the most interesting. And it is a big challenge for your code to actually hold up to all that strain. Your test cases should demonstrate that (ideally) any number and sequence of Forks and Execs should work just fine. In case you’re doing Wait/Signal/Broadcast as well, the same applies – any valid combination. Testing harshly should show you how correct your Exit function really is – you should be able to beef it up once you see where threads or processes are slipping through, or not being accounted for.

7.              Enough.

The multiprogramming project and the virtual memory project are when you will understand Nachos the best. Try and make your syscalls work flawlessly, you may need them in other projects. Spend more time designing and less time debugging – don’t we all just wish for that. And don’t hate Nachos so much – it all works out well for you in the end.