Introduction to Multiprogramming

AddrSpace

At the moment Nachos is using a one to one mapping scheme. If multiprogramming is implemented this scheme must be changed. The constructor functions of the AddrSpace class in addrspace.cc will help you understand how this should be done. The variable pageTable is the page table for the process and numPages is number of pages it occupies in memory.

    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 code above is cut out from the AddrSpace constructor, which creates a page table for a process. As you can see, the virtual and the physical page has the same number. It is your job to change this when implementing multiprogramming.

The AddrSpace class and machine.h will be useful to understand how paging works. Using a bitmap (see bitmap.h) to locate occupied pages in memory is recommended.

Exec and Join system calls

To be able to run a user process, the routine below must be followed:

• Create a new thread.
• Allocate a new address space object for it.
• Initialize its registers.
• Make it invoke machine->Run() .

All the new processes are created trough the Exec() system call. Using Exec(char *name) will execute and return its address space identifier to the calling process. When calling Exec following will be done:

The process will allocate a new address space. It will check if enough memory is available. If there is not enough memory two things can happen. Either you can implement a process queue, where processes will wait until sufficient amount of memory is available. The second thing is just to print an error message. But if you have got enough memory, create a new thread to run the process. Then initialize the thread registers and invoke machine->run.

Join(SpaceId id) is a system call that implements a wait, by waiting for the process with the SpaceId "id".

Exec() and Join() need some extra information to work correctly, therefore all active processes in the system are gathered in a list. This list is a list of PCB's (process control blocks) and for each entry in the list, he following information should be stored:

• Number of children.
• The parent-process' id.
• Whether its parent is waiting to join with it.
• What resources is the process using.

When Exit() is called, you should implement it so the process checks if the parent is waiting for it to finish, in this case, the process should wake the parent and exit. You should also decide whether a child process should be terminated when the parent exits.

Time slicing

Nachos use Round Robin scheduling algorithm. That means each process gets a time slice to occupy the CPU. If it is not done during its time slice, it will be put back in ready queue with. The timer object is defined in system.cc.

Continue to Lab 2 Tutorial