Salsa - Multiprogramming in Nachos

Topics

Nachos Virtual Memory in Nachos
To understand how multiple processes execute in a system, think about how many students can work together by logging on to the same machine. It is the responsibility of the OS to coordinate their execution.
[ Source code in code/userprog| Lab| Quiz ]
Stock Nachos assumes only a single user program exists at any given time. Thus, mainMemory contains instructions for only one user program starting at location mainMemory . Thus, there is a one to one mapping between virtual and physical addresses - virtual address N maps to physical address N.
For the multiprogramming lab, you will need to add multiprogramming support to Nachos. This raises several new issues. First, now that we can have more than one process in memory, not all of them will begin from location mainMemory . Thus, we need a way to allocate memory to processes. Second, we need to coordinate access to the console device - only one process should be able to write to the console at any time. Third, understanding and implementing Exec and Join system calls becomes necessary.
Memory management
The run time mapping from virtual to physical addresses is done by the memory-management unit (MMU) in operating systems, which is a hardware device. A number of different schemes are used - Contiguous allocation, Paging, Segmentation, and Segmentation with paging. Here, we first describe contiguous allocation and paging and then discuss how to implement these in Nachos.
Contiguous allocation

This is one of the simplest memory allocation schemes. In this scheme, the instructions for the process are stored contiguously - in one block. Memory is divided into partitions, each containing exactly one process. Initially, all memory is available for user processes, and is considered as one large block of available memory. The operating system keeps a table indicating which parts of memory are available and which are occupied. When a process arrives and needs memory, the OS searches for a hole large enough for the process. If such a hole is available, memory is allocated to the process. When a process terminates, it releases its memory, which the operating system may then allocate to another process.

Thus, at any time, there is a set of holes, of various sizes, scattered in memory. When a process arrives, the operating system has to choose which hole to allocate to the process. Three strategies are commonly used for this purpose:

First-fit Allocate the first hole that is big enough. Search for a hole stops as soon as one big enough for the process is found.

Best-fit Allocate the smallest hole that is big enough. The whole set of holes needs to be examined. This strategy produces the smallest leftover hole.

Worst-fit Allocate the largest hole. Again, the whole set of holes need to be searched. This strategy produces the largest leftover hole which may be more useful than the smaller leftover hole from a best-fit approach.

Simulations have shown that first-fit and best-fit are better than worst-fit in terms of decreasing time and increasing storage utilization. All the strategies described above suffer from external fragmentation . This exists when there is enough free memory to allocate to a process but is spread out in non-contiguous holes - storage is fragmented into a number of small holes, enough to load a process but spread out in memory. One solution to this problem is compaction . This would shuffle memory so that all the free blocks would be combined together in one large block.

Another problem that may occur with contiguous allocation is internal fragmentation . If a process is allocated more memory than it needs because there was no hole available that was an exact fit, there is some memory that the process has that it does not require. Internal fragmentation is thus internal to a process.

Paging
Paging permits the physical address space of a process to be non-contiguous, thus allowing a process to be allocated physical memory wherever it is available. Physical memory is divided into fixed-sized blocks called frames . Logical memory is divided into equal-sized blocks called pages. When a process is to be loaded into memory, its pages are loaded into any available memory frames. A page table is maintained for each process. This contains the base address of each page in memory.
Every address generated by the CPU is divided into two parts - the page number and page offset . The page number is used to index into the page table to get the base address. This is combined with the page offset to determine the physical address. Note that with this scheme, there is no external fragmentation because any free frame can be allocated to a process that needs it. We may, however, still have internal fragmentation. If the memory requirements of a process are not exact multiples of the page size, the last frame allocated will not be completely full.

Each operating system has its own method of storing page tables. Most allocate a page table for each process. A pointer to the page table is stored with the other register values in the PCB. When the scheduler starts or switches to a process, it reloads the user registers and the correct page-table values from the page table for the process.
Implementation in Nachos - the AddrSpace class
To implement multiprogramming, you can provide any memory management scheme. For now, all virtual addresses map directly to physical addresses. To implement multiprogramming, you must change the way Nachos loads processes into memory. To see how this is done, see the constructor function of the AddrSpace class in addrspace.cc. Note the two private variables - pageTable and numPages . The first is a page table for the process and the second contains the number of pages the process occupies in memory. Since each process has a unique address space, there is a page table for each process.
pageTable = new TranslationEntry[numPages]; for (i = 0; i < numPages; i++) { pageTable[i].virtualPage = i; // for now, virtual page # = phys page # pageTable[i].physicalPage = i; pageTable[i].valid = TRUE; pageTable[i].use = FALSE; pageTable[i].dirty = FALSE; pageTable[i].readOnly = FALSE; // if the code segment was entirely on // a separate page, we could set its // pages to be read-only }
The above code fragment from the AddrSpace constructor, creates a page table for the process. Note that for each page the process occupies in memory, virtual page number is the same as the physical page. To implement multiprogramming, you must change this. Your memory management scheme must figure out what the physical page number for each virtual page is and fill it in.
To see how the MIPS simulator knows where to locate the instructions for a process, note the private variables pageTable and pageTableSize in the Machine class (machine.h ). When the scheduler switches between two processes, it calls a routine RestoreState(), defined in the AddrSpace class ( addrspace.cc). This routine initializes the pageTable and pageTableSize of the machine class to the page table for the process. Thus, the simulator's data structures are properly initialized to point to those of the process before it starts executing the instructions for that process.
Use a bitmap to keep track of what pages are occupied in memory. Look at bitmap.h in the userprog directory.

Exec and Join system calls

Each user process in Nachos runs as a kernel thread. To run a user process, you must do the following:

Create a new thread.

Allocate a new address space object for it.

Initialize its registers.

Make it invoke machine->Run().

The second step loads the instructions for the process into Nachos memory.
Any new process in Nachos is created through the Exec() system call. This means that the first user program would be loaded into Nachos memory through the StartProcess() (see progtest.cc in the userprog directory) routine and subsequent new processes will be created by that process calling Exec() . Of course, any child processes so created can call Exec() as well.
Exec(char *name) is responsible for running the executable with name "name" and return its address space identifier to the calling process. Thus, it must do the following:

Allocate a new address space for the new process.

Check if enough memory is available to run the new process. If not, the semantics you implement will determine what will happen next. You can either place the user process in a queue and wait for sufficient memory to become available or simply print a message saying the process cannot be loaded because of insufficient memory. Of course, in a real system, the second solution would be unacceptable.

If there is enough memory, create a new thread to run the process.

Make the new thread initialize its registers and user state and invoke machine->Run(). Note that it is necessary that the new thread itself invoke the simulator and not the parent.

The Join(SpaceId id) system call implements a wait by the calling process for a process with the SpaceId "id". It should return only when "id" has finished. Note that this may require the calling process to be put to sleep. (This is easily done because each user process runs as a thread and the thread class provides a way by which a thread can put itself to sleep.)

Both the Exec() and Join() system calls require some bookkeeping in order to work correctly. For the purpose of memory management and to implement Join() correctly, it is necessary to maintain a list of active processes in the system - a PCB list. Also, for each process in the system, you may need to maintain the following information:

How many children it has.

Who is its parent.

Whether its parent is waiting to join with it.

What resources is the process using, e.g., files opened by the process.

When a process calls Exit() , it should check if its parent is waiting for it to finish, if yes, it should wake the parent before it exits. You will also need to decide what to do with the children if a process wants to exit. Should the process wait for each child to finish or should it let them run? You are free to implement either semantics. Note that if you want to implement the former, there will be an implicit Join() for each Exec() call the process made.

Time slicing

A hardware timer generates a CPU interrupt every X milliseconds. The Nachos timer emulates a hardware timer by scheduling an interrupt to occur every TimerTicks. This is a variable defined in stats.h in the machine directory and denotes the average time between timer interrupts.

The Timer class (timer.cc ) implements this timer. Interrupts can be caused to occur at random or at fixed intervals. This is determined by the variable randomize of the Timer class. If set, interrupts occur at random intervals. This means that process switching takes place at random intervals. If randomize is not set, interrupts take place at fixed intervals, as defined by TimerTicks . Thus, if you define your time slice as, say, 30 units, you must cause an interrupt every 30 units instead of TimerTicks (one way to do this is to alter the routine TimeOfNextInterrupt in the Timer class).
Every time slice, the scheduler switches between processes.

This means that the MIPS simulator executes processes as deemed by the scheduler. Note that the registers and other data structures are properly initialized for the simulator as part of the switch. Thus, the simulator executes processes in a round-robin manner.
The timer object is allocated in system.cc.
Synchronized access to the console

With multiprogramming, there can be more than one process trying to read or write to the console. Thus, additional code needs to be written to coordinate this access. The console device does not provide this functionality. You may find is useful to implement a SynchConsole class on the lines of the simple ConsoleTest program in progtest.cc.

This class should use semaphores for both keyboard and display access. Thus, any process that wants to write to the console would first grab the display semaphore and use the PutChar() routine to write to the console. It then waits for the device to be ready (this is indicated by the console device through the interrupt handler when the write has actually completed). When the device is ready, the process can write more characters to the console (if required). Analogous operations are performed to read from the console - the process grabs the keyboard semaphore and waits for the console to be ready (this happens when a character actually arrives at the console). When the console is ready, the process reads from it using the GetChar() routine. This is done in a loop if there multiple characters need to be read.
Upon console I/O, the console device, schedules interrupts into the future to poll the console for characters. This may cause Nachos to continue execution even after all user process have finished and there are no more threads on the ready list. To get around this, user programs should call Halt() when they have finished execution.

Source code in code/userprog
Lab
Quiz
Back to Top
Last modified on 2 February 2004