Skip to content

Note for Project 2

Jump to bottom Edit New page
thinkhy edited this page Jun 9, 2014 · 75 revisions

Phase 2: Multiprogramming

Overview

The second phase of Nachos is to support multiprogramming. As in the first assignment, we give you some of the code you need; your job is to complete the system and enhance it.

Setup

  • Step 1

to read and understand the part of the system we have written for you - UserKernel.java - a multiprogramming kernel. - UserProcess.java - a user process; manages the address space, and loads a program into virtual memory. - UThread.java - a thread capable of executing user MIPS code. - SynchConsole.java - a synchronized console; makes it possible to share the machine's serial console among multiple threads.

  • This test program is found in test/halt.c and represents the simplest supported MIPS program.

The test directory includes C source files (.c files) and Nachos user program binaries (.coff files). The binaries can be built while in the test directory by running gmake, or from the proj2 directory by running gmake test.

  • To run the halt program, go to the test directory and gmake; then go to the proj2 directory, gmake, and run nachos -d ma. Trace what happens as the user program gets loaded, runs, and invokes a system call (the 'm' debug flag enables MIPS disassembly, and the 'a' debug flag prints process loading information).

  • There are multiple stages to building a Nachos-compatible MIPS binary (all of which are handled by the test Makefile):

    1. Source files (.c) are compiled into object files (.o) by mips-gcc.
    2. Some of the object files are linked into libnachos.a, the Nachos standard library.
    3. start.s is preprocessed and assembled into start.o. This file contains the assembly-language code to initialize a process. It also provides the system call "stub code" which allows system calls to be invoked.
    4. An object file is linked with libnachos.a to produce a Nachos-compatible MIPS binary, which has the extension *.coff. (COFF stands for Common Object File Format and is an industry-standard binary format which the Nachos kernel understands.)
    5. Note that if you create a new test file (*.c), you will need to append your program name to the variable TARGETS in the Makefile inside test directory

  • You can run other test programs by running

    nachos -x PROGNAME.coff

    where PROGNAME.coff is the name of the MIPS program binary in the test directory.

Task I: Implement the file system calls

(30%, 125 lines) Implement the file system calls (creat, open, read, write, close, and unlink, documented in syscall.h). You will see the code for halt in UserProcess.java; it is best for you to place your new system calls here too. Note that you are not implementing a file system; rather, you are simply giving user processes the ability to access a file system that we have implemented for you.

  • We have provided you the assembly code necessary to invoke system calls from user programs (see start.s; the SYSCALLSTUB macro generates assembly code for each syscall).

  • You will need to bullet-proof the Nachos kernel from user program errors; there should be nothing a user program can do to crash the operating system (with the exception of explicitly invoking the halt() syscall). In other words, you must be sure that user programs do not pass bogus arguments to the kernel which causes the kernel to corrupt its internal state or that of other processes. Also, you must take steps to ensure that if a user process does anything illegal -- such as attempting to access unmapped memory or jumping to a bad address -- that the process will be killed cleanly and its resources freed.

  • You should make it so that the halt() system call can only be invoked by the "root" process -- that is, the first process in the system. If another process attempts to invoke halt(), the system call should be ignored and return immediately.

  • Since the memory addresses passed as arguments to the system calls are virtual addresses, you need to use UserProcess.readVirtualMemory and UserProcess.writeVirtualMemory to transfer memory between the user process and the kernel .

  • User processes store filenames and other string arguments as null-terminated strings in their virtual address space. The maximum length of for strings passed as arguments to system calls is 256 bytes. [5]

  • When a system call wishes to indicate an error condition to the user, it should return -1 (not throw an exception within the kernel!). Otherwise, the system call should return the appropriate value as documented in test/syscall.h.

  • When any process is started, its file descriptors 0 and 1 must refer to standard input and standard output. Use UserKernel.console.openForReading() and UserKernel.console.openForWriting() to make this easier. A user process is allowed to close these descriptors, just like descriptors returned by open().

  • A stub file system interface to the UNIX file system is already provided for you; the interface is given by the class machine/FileSystem.java. You can access the stub filesystem through the static field ThreadedKernel.fileSystem. (Note that since UserKernel extends ThreadedKernel, you can still access this field.) This filesystem is capable of accessing the test directory in your Nachos distribution, which is going to be useful when you want to support the exec system call (see below). You do not need to implement any file system functionality. You should examine carefully the specifications for FileSystem and StubFileSystem in order to determine what functionality you should provide in your syscalls, and what is handled by the file system.

Refer to: machine/Machine.java:

   if (Config.getBoolean("Machine.stubFileSystem"))
        stubFileSystem = new StubFileSystem(privilege, testDirectory);

  • Do not implement any kind of file locking; this is the file system's responsibility. If ThreadedKernel.fileSystem.open() returns a non-null OpenFile, then the user process is allowed to access the given file; otherwise, you should signal an error. Likewise, you do not need to worry about the details of what happens if multiple processes attempt to access the same file at once; the stub filesystem handles these details for you.

  • Your implementation should support up to 16 concurrently open files per process, including stdin and stdout. Each file that a process has opened should have a unique file descriptor associated with it (see syscall.h for details). The file descriptor should be a non-negative integer that is simply used to index into a table of currently-open files by that process. Note that a given file descriptor can be reused if the file associated with it is closed, and that different processes can use the same file descriptor (i.e. integer) to refer to different files.

NOTE:

There is one stub per system call, that places the code for the system call into register r2, and leaves the arguments to the system call alone (in other words, arg1 is in r4, arg2 is in r5, arg3 is in r6, arg4 is in r7)

/** Index of return value register 0 */
public static final int regA0 = 4;

/** Index of argument register 1 */
public static final int regA1 = 5;

/** Index of argument register 2. */
public static final int regA2 = 6;

/** Index of argument register 3. */
public static final int regA3 = 7;

System Calls

  • creat

Attempt to open the named disk file, creating it if it does not exist, and return a file descriptor that can be used to access the file.

Note that creat() can only be used to create files on disk; creat() will never return a file descriptor referring to a stream.

Returns the new file descriptor, or -1 if an error occurred.

Why not created? It's Ken Thompson's mistake. Fore more details, refer to http://unix.stackexchange.com/questions/10893/what-did-ken-thompson-mean-when-he-said-id-spell-create-with-an-e

  • open

Attempt to open the named file and return a file descriptor.

Note that open() can only be used to open files on disk; open() will never return a file descriptor referring to a stream.

Returns the new file descriptor, or -1 if an error occurred.

  • read

Attempt to read up to count bytes into buffer from the file or stream referred to by fileDescriptor.

On success, the number of bytes read is returned. If the file descriptor refers to a file on disk, the file position is advanced by this number.

It is not necessarily an error if this number is smaller than the number of bytes requested. If the file descriptor refers to a file on disk, this indicates that the end of the file has been reached. If the file descriptor refers to a stream, this indicates that the fewer bytes are actually available right now than were requested, but more bytes may become available in the future. Note that read() never waits for a stream to have more data; it always returns as much as possible immediately.

On error, -1 is returned, and the new file position is undefined. This can happen if fileDescriptor is invalid, if part of the buffer is read-only or invalid, or if a network stream has been terminated by the remote host and no more data is available.

  • write

Attempt to write up to count bytes from buffer to the file or stream referred to by fileDescriptor. write() can return before the bytes are actually flushed to the file or stream. A write to a stream can block, however, if kernel queues are temporarily full.

On success, the number of bytes written is returned (zero indicates nothing was written), and the file position is advanced by this number. It IS an error if this number is smaller than the number of bytes requested. For disk files, this indicates that the disk is full. For streams, this indicates the stream was terminated by the remote host before all the data was transferred.

On error, -1 is returned, and the new file position is undefined. This can happen if fileDescriptor is invalid, if part of the buffer is invalid, or if a network stream has already been terminated by the remote host.

  • close

Close a file descriptor, so that it no longer refers to any file or stream and may be reused.

If the file descriptor refers to a file, all data written to it by write() will be flushed to disk before close() returns. If the file descriptor refers to a stream, all data written to it by write() will eventually be flushed (unless the stream is terminated remotely), but not necessarily before close() returns.

The resources associated with the file descriptor are released. If the descriptor is the last reference to a disk file which has been removed using unlink, the file is deleted (this detail is handled by the file system implementation).

Returns 0 on success, or -1 if an error occurred.

  • unlink,

Delete a file from the file system. If no processes have the file open, the file is deleted immediately and the space it was using is made available for reuse.

If any processes still have the file open, the file will remain in existence until the last file descriptor referring to it is closed. However, creat() and open() will not be able to return new file descriptors for the file until it is deleted.

Returns 0 on success, or -1 if an error occurred.

Variables

  • add file descriptors array(non-static) in class UserProcess: int fd[MAX_FD]; MAX_FD=16

NOTE, The file descriptor should be a non-negative integer that is simply used to index into a table of currently-open files by that process. Note that a given file descriptor can be reused if the file associated with it is closed.

  • static constant variables: STDOUT and STDIN, its file descriptors 0 and 1 must refer to standard input and standard output

  • static constant variable: maximum length of strings passed as arguments to system calls

Design

Test strategy

Tests file syscalls (creat, open, read, write, close, unlink), as well as stdin/stdout. If anything is printed to the console aside from what is expected, the test will fail.

  • testID 0 : creates a file, checks syscall creat works
  • testID 1 : calls syscall creat/close/unlink and checks that they work
  • testID 2 : tests if your syscall close actually closes the file
  • testID 3 : tests if your syscall open fails gracefully when stubFileSystem's openfile limit's exceeded
  • testID 4 : tests if all files get closed when process exits normally
  • testID 5 : tests your syscall read by reading some bytes from a file
  • testID 6 : tests that each of your processes's file descriptors are independent from other processes
  • testID 7 : copies between files, tests creat, open, read, write, close
  • testID 8 : tests that write fails gracefully on bad arguements (e.g. bad address)
  • testID 9 : tests that read fails gracefully on bad arguments (e.g. writing back to a readonly part of virtual memory)
  • testID 10: tests that stdin uses console
  • testID 11: tests stdout

Test Cases(Update 6/5/2014)

  • See filesyscall.c
  • Build testcase: issue 'cd nachos/test/&&make'

Task II: Implement support for multiprogramming

(25%, 100 lines) Implement support for multiprogramming. The code we have given you is restricted to running one user process at a time; your job is to make it work for multiple user processes.

Come up with a way of allocating the machine's physical memory so that different processes do not overlap in their memory usage. Note that the user programs do not make use of malloc() or free(), meaning that user programs effectively have no dynamic memory allocation needs (and therefore, no heap). What this means is that you know the complete memory needs of a process when it is created. You can allocate a fixed number of pages for the processe's stack; 8 pages should be sufficient.

We suggest maintaining a global linked list of free physical pages (perhaps as part of the UserKernel class). Be sure to use synchronization where necessary when accessing this list. Your solution must make efficient use of memory by allocating pages for the new process wherever possible. This means that it is not acceptable to only allocate pages in a contiguous block; your solution must be able to make use of "gaps" in the free memory pool.

Also be sure that all of a process's memory is freed on exit (whether it exits normally, via the syscall exit(), or abnormally, due to an illegal operation).

Modify UserProcess.readVirtualMemory and UserProcess.writeVirtualMemory, which copy data between the kernel and the user's virtual address space, so that they work with multiple user processes.

The physical memory of the MIPS machine is accessed through the method Machine.processor().getMemory(); the total number of physical pages is Machine.processor().getNumPhysPages(). You should maintain the pageTable for each user process, which maps the user's virtual addresses to physical addresses. The TranslationEntry class represents a single virtual-to-physical page translation.

The field TranslationEntry.readOnly should be set to true if the page is coming from a COFF section which is marked as read-only. You can determine this using the method CoffSection.isReadOnly().

Note that these methods should not throw exceptions when they fail; instead, they must always return the number of bytes transferred (even if that number is zero).

Modify UserProcess.loadSections() so that it allocates the number of pages that it needs (that is, based on the size of the user program), using the allocation policy that you decided upon above. This method should also set up the pageTable structure for the process so that the process is loaded into the correct physical memory pages. If the new user process cannot fit into physical memory, exec() should return an error.

Note that the user threads (see the UThread class) already save and restore user machine state, as well as process state, on context switches. So, you are not responsible for these details.

Main points

  • We suggest maintaining a global linked list of free physical pages (perhaps as part of the UserKernel class). Be sure to use synchronization where necessary when accessing this list.

  • Modify UserProcess.readVirtualMemory and UserProcess.writeVirtualMemory

  • Modify UserProcess.loadSections() so that it allocates the number of pages that it needs

  • The field TranslationEntry.readOnly should be set to true if the page is coming from a COFF section which is marked as read-only.

  • You should maintain the pageTable for each user process, which maps the user's virtual addresses to physical addresses.

  • You can allocate a fixed number of pages for the processe's stack; 8 pages should be sufficient.

    /** The number of pages in the program's stack. */ protected final int stackPages = 8;

Design

UserKernel class

  • Maintain a global linked list of free physical pages, add variable UserKernel.pageLinks
  • Add interface UserKernel.getFreePage() which will remove the first element in the page link list and return the number of free page.
  • Add interface UserKernel.addFreePage() add a free page into page linked list.

UserProcess class

  • Maintain the pageTable for each user process, which maps the user's virtual addresses to physical addresses.
    • Add variable UserProcess.pageTable
  • Modify UserProcess.UserProcess() find available physical pages and map virtual pages to physical pages
  • Modify UserProcess.readVirtualMemory() translate virtual address to physical address
  • Modify UserProcess.writeVirtualMemory() translate virtual address to physical address
  • Modify UserProcess.loadSections()
    • Invoke UserKernel.getFreePage to allocates the number of physical pages and fill page table that will be used to translate virtual address to physical address.
    • Set TranslationEntry.readOnly = true while COFF section is marked as read-only(invoke CoffSection.isReadOnly() )
    • Allocate physical pages for stack(8pages=8*4K) and argument(reserve the last page)
  • Implement UserProcess.unloadSections(): back out physical pages and release page table.
    • Update 5/8/2014: DON'T forget to invoke coff.close in UserProcess.unloadsections

Test

  • Note: readVirtualMemory and writeVirtualMemory are tested by high level syscall like open, read and write.

  • testID 0: tests that you support fragmentation in physical memory.

    • e.g. if physical memory 10 pages, exec P1 4 pages big, exec P2 1 page big, exec P3 4 pages big, P2 exits. then exec P4 2 pages big should succeed

  • testID 1: tests readVirtualMemory with an invalid range

  • testID 2: tests writeVirtualMemory with an invalid range

  • testID 3: tests readVirtualMemory small valid range, make sure read right data

  • testID 4: tests writeVirtualMemory small valid range, make sure wrote right data

  • testID 5: tests readVirtualMemory with a large valid range, make sure read right data

  • testID 6: tests writeVirtualMemory with a large valid range, make sure wrote right data

Task III: Implement the system calls for process management

(30%, 125 lines) Implement the system calls (exec, join, and exit, also documented in syscall.h).

Again, all the addresses passed in registers to exec and join are virtual addresses. You should use readVirtualMemory and readVirtualMemoryString to transfer memory between the kernel and the user process. Again, you must bullet-proof these syscalls.

Note that the state of the child process is entirely private to this process. This means that the parent and child do not directly share memory, file descriptors, or other state. Note that two processes can of course open the same file; for example, all processes should have file descriptors 0 and 1 mapped to the system console, as described above.

Unlike KThread.join(), only a process's parent can join to it. For instance, if A executes B and B executes C, A is not allowed to join to C, but B is allowed to join to C.

join takes a process ID as an argument, used to uniquely identify the child process which the parent wishes to join with. The process ID should be a globally unique positive integer, assigned to each process when it is created. (Although for this project the only use of the process ID is in join, for later project phases it is important that the process ID is unique across all running processes in the system.) The easiest way of accomplishing this is to maintain a static counter which indicates the next process ID to assign. Since the process ID is an int, then it may be possible for this value to overflow if there are many processes in the system. For this project you are not expected to deal with this case; that is, assume that the process ID counter will not overflow.

When a process calls exit(), its thread should be terminated immediately, and the process should clean up any state associated with it (i.e. free up memory, close open files, etc). Perform the same cleanup if a process exits abnormally.

The exit status of the exiting process should be transferred to the parent, in case the parent calls the join system call. The exit status of a process that exits abnormally is up to you. For the purposes of join, a child process exits normally if it calls the exit syscall with any status, and abnormally if the kernel kills it (e.g. due to an unhandled exception).

The last process to call exit() should cause the machine to halt by calling Kernel.kernel.terminate(). (Note that only the root process should be allowed to invoke the halt() system call, but the last exiting process should call Kernel.kernel.terminate() directly.)

Main points

  1. Note that the state of the child process is entirely private to this process. Note that two processes can of course open the same file;
  2. Only a process's parent can join to it;
  3. Join takes a process ID as an argument, used to uniquely identify the child process which the parent wishes to join with. It is important that the process ID is unique across all running processes in the system. Should maintain a static counter which indicates the next process ID to assign, assume that the process ID counter will not overflow.
  4. When a process calls exit(), its thread should be terminated immediately, and the process should clean up any state associated with it.
  5. The exit status of the exiting process should be transferred to the parent, in case the parent calls the join system call.
  6. The last process to call exit() should cause the machine to halt by calling Kernel.kernel.terminate().

###System calls

  1. exit

Terminate the current process immediately. Any open file descriptors belonging to the process are closed. Any children of the process no longer have a parent process. status is returned to the parent process as this process's exit status and can be collected using the join syscall. A process exiting normally should(but is not required to) set status to 0. exit() never returns.

  1. join

Suspend execution of the current process until the child process specified by the processID argument has exited. If the child has already exited by the time of the call, returns immediately. When the current process resumes, it disowns the child process, so that join() cannot be used on that process again. processID is the process ID of the child process, returned by exec(). status points to an integer where the exit status of the child process will be stored. This is the value the child passed to exit(). If the child exited because of an unhandled exception, the value stored is not defined. If the child exited normally, returns 1. If the child exited as a result of an unhandled exception, returns 0. If processID does not refer to a child process of the current process, returns -1.

  1. exec

Execute the program stored in the specified file, with the specified arguments, in a new child process. The child process has a new unique process ID, and starts with stdin opened as file descriptor 0, and stdout opened as file descriptor 1. file is a null-terminated string that specifies the name of the file containing the executable. Note that this string must include the ".coff" extension. argc specifies the number of arguments to pass to the child process. This number must be non-negative. argv is an array of pointers to null-terminated strings that represent the arguments to pass to the child process. argv[0] points to the first argument, and argv[argc-1] points to the last argument. exec() returns the child process's process ID, which can be passed to join(). On error, returns -1.

###Design

UserKernel class

Data Structure

  • UserKernel.nextPid: Maintain a static counter which indicates the next process ID to assign, assume that the process ID counter will not overflow.
  • UserKernel.processMap: static member map<int,UserProcess>, maintain a map which stores processes, key is pid, value is the process which holds the pid.

Interface

  • UserKernel.getNextPid: static interface, thread-safe. Increase counter, return next Pid.
  • UserKernel.getProcessByID: static interface. Get process from processMap by pid.
  • registerProcess(pid, process): static interface, thread-safe. Insert a <key, value> pair into process map.
  • unregisterProcess(pid): static interface, thread-safe. Remove an element in process map for key pid. Return the removed process.

UserProcess class

Data Structure

  • UserProcess.pid: process ID.
  • UserProcess.ppid: parent process, private member.
  • UserProcess.children: LinkedList, child processes, private member.
  • UserProcess.exitStatus: exit status, a process exiting normally should(but is not required to) set status to 0.
  • UserProcess.exitCondition: condition variable which is used to notify parent process.
  • UserProcess.thread: thread associated with this process

Interface

  • getppid(): static interface, return pid of parent process.

  • modify UserProcess.UserProcess(): add two lines, one line to get a unique pid, another to register new process to map in UserKernel.

  • modify UserProcess.execute(): save new thread to private member UserProcess.thread

  • void exit(int status)

           close open file descriptors belonging to the process
       set pid of parent process to 0(root process)
       set any children of the process no longer have a parent process(at here we assign zombie's parent as ROOT).
       set the process's exit status to the number that caller specifies(normal) or -1(exception)
       unload sections and release memory pages by invoking unloadSections()
       finish associated thread's running

  • int join(int processID, int *status);

       If the specified process is a child of this process,
          remove the child pid in this process's children list;
   Else
          return -1;

   If the child has not exited by the time of the call,
        Child process's thread joins current thread by invoking KThread.join()

   Store the exit status of child process to status pointed by the second argument
   If the child exited normally, 
          returns 1;
   Else If the child exited as a result of an unhandled exception, 
          returns 0;

  • int exec(char *file, int argc, char *argv[])

       + if argc is less than 1
   +   return -1
   +if filename doesn't have the ".coff" extension
   +   return -1;
   get args from address of argv
   create a new process by invoking UserProcess.newUserProcess()
   allocate an unique pid for child process
   * copy file descriptors to the new process. [NOT required in this]
   set new process's parent to this process.
   add new process into this process's children list.
   register this new process in UserKernel
   invoke UserProcess.execute to load executable file and create new UThread
   + If normal, return new process's pid.
   + Otherwise, on error return -1.

Test Strategy

  • testID 1 : tests that your syscall exit finishes the thread of the process immediately
  • testID 2 : runs exec multiple times and checks each child gets unique PID
  • testID 3 : tests your syscall join to a child
  • testID 4 : tests exec with error arguments (e.g. bad file name)
  • testID 5 : tests your syscall join to a non-child
  • testID 6 : tests your syscall join to a child that caused unhandled exception
  • testID 7 : tests that your exit syscall releases all resources

Test Case

  • See isprmgr.c
  • Build testcase: issue 'cd test&&make'

Task IV: Implement a lottery scheduler

(15%, 50 lines+existing priority scheduler ) Implement a lottery scheduler (place it in threads/LotteryScheduler.java). Note that this class extends PriorityScheduler, you should be able to reuse most of the functionality of that class; the lottery scheduler should not be a large amount of additional code. The only major difference is the mechanism used to pick a thread from a queue: a lottery is held, instead of just picking the thread with the most priority. Your lottery scheduler should implement priority donation. (Note that since this is a lottery scheduler, priority inversion can't actually lead to starvation! However, your scheduler must do priority donation anyway.)

  • In a lottery scheduler, instead of donating priority, waiting threads transfer tickets to threads they wait for. Unlike a standard priority scheduler, a waiting thread always adds its ticket count to the ticket count of the queue owner; that is, the owner's ticket count is the sum of its own tickets and the tickets of all waiters, not the max. Be sure to implement this correctly.

  • Your solution should work even if there are billions of tickets in the system (i.e. do not keep an array containing an entry for every ticket).

  • When LotteryScheduler.increasePriority() is called, the number of tickets held by a process should be incremented by one. Similarly, for decreasePriority(), the number should be decremented by one.

  • The total number of (real) tickets in the system is guaranteed not to exceed Integer. MAX_VALUE.

###Design

###Test

Test Strategy

  • TestID 1: Forks off some threads with different numbers of tickets and verifies that the lottery scheduler picks them with the right probabilities.
  • TestID 2: The total number of tickets in the system is guaranteed not to exceed Integer.MAX_VALUE.
  • TestID 3: Test ThreadGrader7 (no ticket transfers (priority donation))
  • TestID 4: Tests Lottery Scheduler with a couple waiters in the queue
  • TestID 5: Tests Lottery Scheduler with a few waiters in the queue
  • TestID 6: Tests Lottery Scheduler with a many waiters in the queue
  • TestID 7: Test ThreadGrader6a (with ticket transfers (priority donation))
  • TestID 8: Small lottery scheduler test with priority donation
  • TestID 9: Medium lottery scheduler test with priority donation
  • TestID 10: Big lottery scheduler test with priority donation

Test Case

Reference

Add a custom footer
Add a custom sidebar

Clone this wiki locally