Title: WRITEUP for Project 3, Fall 2004 Date: 11/02/2004 Group: Name Email Tushar Makhija tmakhija@usc.edu Apoorva Jindal apoorvaj@usc.edu Nithin Dinker Kamath nkamath@usc.edu I. Requirements: 1. In Part 1, we have to implement software-management of the TLB and also implement software page translation for TLB misses. We also have to implement a Inverted Page Table ( IPT ) . The IPT maps physical pages to virtual pages and also the process owner. We have one IPT for the entire OS. On a TLB 'miss' i.e the page is not found in the TLb, hardware generates a PageFaultException, then we will search through the IPT , match the process_id and virtual address, then load the entry into the TLB and then retsart the instruction. We will be running from the vm directory hence pageTable = NULL and the TLB gets initialized. 2. In Part 2, we are required to implement the virtual memory management. We need to manage a page table for each process, since a page can be present in either the main memory or the executable or the swap file. For each page table entry, we will have to track its location in the swap file. In case of a page fault, if we have to replace a page in the main memory, we will have to use a page replacement scheme. We have to implement three different Page Replacement Schemes: Random, FIFO and LRU. 3. In Part 3, we need to implement semaphores which will be shared across processes. This will enable inter process synchronization. For this purpose, there will be a server nachos which will keep all the semaphores within itself and the clients, which when need semaphores, will have to send a message to the server calling an up or a down on the semaphore. So, we have to change the semaphore system call implementation in exception.cc to handle semaphores shared across processes. We will also have to code for the server which keeps tracks of all the sempahores. II. Assumptions: 1. a) We will continue to have NumPhysPages to 512 in machine.h as we had for Project 2. b) We have implemented only the part when there is no virtual memory but the physical memory map is obtained from the IPT and not the pagetables of the address space. c) Though we have tested this portion, we are not providing specific test cases to test this. If part 2 runs fine, then part 1 has to run fine. 2. a) The Code and Init data doesn't change over the time. b) Each process has its own swap file. c) Change the numPhysPages to 32. d) Retain nachos.ld in the Makefile in the test directory. e) The page replacement scheme will be selected using -P at the command line. 3. a) The server will always have the machine ID 0 that is, the command line option for starting the server nachos is nachos -m 0. b) There will be no loss of packets. c) The port number of the server will be hardcoded to be 0 in all the clients. d) All the clients will be passed the machine id of the server using the command line argument -o 0. e) Whenever we are running nachos using the command line option "-m", the semaphore system call will assume that we want to use semaphores which are shared across processes. f) The inbox mailbox number is 0 and outbox mailbox number is 1 for everyone. g) The server never stops. Since the server does not know when to stop, it will never terminate by itself. It will have to be terminated by using ctrl-C. h) The clients and the server is not multi threaded, i.e. each of them has a single thread only. III. Design: 1. Please note that IPT is guarded by IptLock. Though we are not stating it explicitly, any attempt to access IPT will have to preceeded by acquiring IptLock. TLB software implementation: TLB is managed by nachos internally. We have to take care of TLB implementation on a context switch and on a TLB miss. Note that TLB is a TranslationEntry instance. So, it has a valid bit which shows us that it is page in TLB is a valid page for the process in the memory. On a TLB 'miss' we we have a PageFaultException because the mapping does not exist in the TLB. On a TLB miss nachos detects a page fault and generates an interrupt . This is the page fault exception. We catch the exception in exception.cc in ExceptionHandler. We get the virtual page by int type=machine->ReadRegister(39). This will give us the virtual address stored in BadVAddrReg (register number 39). The PageFaultException returns the failing virtual address on the exception and it is stored in Reg 39 BadVAddrReg. Then we get the virtual page number by unsigned int vpn=(unsigned)virtAddr/Pagesize; Now we also have to check whether the address is valid or not. If vpn>numPages, then the address is not valid. In the addressSpace, we will make numPages public so that we can check if the given address is valid or not. S/W page translation on a TLB miss i.e search in Inverted Page Table: Whenever the corresponding mapping between the virtual and the physical pages is not found in the TLB we would have to look for it in the IPT. The inverted page table is a mapping from the physical page to the virtual page. Inverted Page Table: class IPTentry: Variables: int vPage: The page number in virtual memory. int pPage: The page number in physical memory bool valid_bit: If this bit is FALSE the page is not in memory. bool dirty_bit: This bit is set by the hardware every time the page is modified. Addrspace *Process_Id: The addresspace of the process. bool use_bit; int replacing;:to prevent race conditions while replacing a page. Useful when a page is being replaced by a process and it is context switched out. so no other process should attempt to read the page. We will define the class in addrspace.h IptEntry *ipt It is initialised in addrspace.cc ipt = new IptEntry[NumPhyPages]; for (i = 0; i < NumPhyPages; i++) ipt[i].valid = FALSE; Populating/ updating the IPT: In part 1 we assume that everything is preloaded in memory. we have all the 512 pages in memory . The TLB miss will cause a sequential search for the virtual address ( and Process_Id) The PageFaultException will give us the faulting virtual address . We can compute the virtual page number and now it is to be searched inside the IPT ( we have to take care of the Process_Id). We sequentially search the entire physical memory using IPT to find the physical page location using the virtual page number and Process_Id. Once the page is found we have to load it into the TLB. We use FIFO to upload the page into TLB. For this purpose, we define a global variable whichTLBPage in system.h and initialize it to 0. This will help us keep track of which page in TLB is to be changed next. Whenever we upload a page in TLB, we do a whichTLBPage = (whichTLBPage + 1)%TLBSize. Updating the TLB: When we update the TLB we disable the interrupts. Let i = the physical page which we need to upload into the TLB. // disable interrupts tlb[whichTLBPage].virtualPage = IPT[i].vPage; tlb[whichTLBPage].physicalPage = IPT[i].pPage; tlb[whichTLBPage].valid = TRUE; tlb[whichTLBPage].use = FALSE tlb[whichTLBPage].dirty = FALSE; tlb[whichTLBPage].readOnly = FALSE; Then do whichTLBPage = (whichTLBPage + 1)%4. // enable interrupts What to do on a Context Switch: We keep a global variable oldThread which is set in scheduler.cc to the oldThread which was running in the CPU. Then we make the following changes in RestoreState in AddrSpace.cc: We comment out machinePageTable = pageTable. Then we check if the address space of the currentThread is the same as the address space of the oldThread. If they are, then we do nothing, if they are different then invalidate every TLB entry by setting TLB[i].valid = FALSE. But before doing so, populate all the TLB bits like TLB[i].dirty to the IPT or physical memory. Since nachos only changes TLB bits, we have to ensure that the corresponding bits in IPT also get changed. Changes in copyin, copyinz and copyout: When reading from the main memory, since machine->pageTable does not exist now, we will have to change these functions such that they use machine->Translate function to convert the virtual address to the physical address. In case of a pageFaultException, we haveto catch it and modify the system calls which use these functions to take care of the page faults. Especially we have to take care that the PCReg does not get incremented when a pageFault occurs. 2. We have defined 2 global variables for the Page Replacement Schemes. The first variable replaceType will store the type of the Replacement Scheme that will be used. It is set to 0 if FIFO is implemented, 1 for Random Page Replacement Scheme and 2 for LRU Page Replacement Scheme. It is set from the parameter (-P ) entered at the command line. The variable FIFOPage will store the page number of the next page to be replaced in the FIFO Replacement Scheme. It is initialized to 0. Class AddrSpaceEntry: This class is basically a super class which includes all the members of the TranslationEntry class as well as some additional members. It will be used instead of the TranslationEntry while creating the pageTable member of the AddrSpace class. This class has the constructor and the following variables: int inExecutable: Tells if the data in the page should be read from executable int swapOffset: Stores the offset at which this page has been written in the swap file bool onDisk: Tells if the page is present in the swap file. TRUE if in swap file or else FALSE These are the parameters borrowed from the TranslationEntry class: int virtualPage: The page number in virtual memory int physicalPage: The page number in real memory (relative to the start of "mainMemory" bool valid: If this bit is set, the translation is ignored. (In other words, the entry hasn't been initialized.) bool readOnly: If this bit is set, the user program is not allowed to modify the contents of the page. bool use: This bit is set if the page has been referenced or modified. bool dirty: This bit is set if the page has been modified and not written to swap file. Instead of a pageTable = new TranslationEntry[numPages], a address space will have a public pageTable = new AddrSpaceEntry[numPages] as its variable. A new class called SwapFile is also created to handle the Reading/Writing Operations to the Swap The class members are: char *fileName: Name of the swap file OpenFile *swapPointer: The file pointer to the swap file int OffSet: Stores the OffSet for reading or writing the next page in the swap file Lock *swapLock: Lock to prevent Deadlocks or Race Conditions during swap operations void *space: The pointer to the address space of the process to which this file belongs. The functions of this class are: SwapFile(char * Name): It is basically the constructor of the class It creates a file on the disk named "swap Process_Id" Where Process_Id is the address space pointer of the process. void WriteSwap(char * buf, int virtualpageNo): This function writes into the swap file. It takes the char * buf which is the data to be written and the virtualPageNo, the page's virtual page number to which the data belongs. We use the function WriteAt to write the page at Offset. We store this value of offset in the pageTable entry for this page. char * ReadSwap(int OSet): This function reads from the swap file and returns the data read. If takes the virtual page number as the input and finds the offset in the swap file through the page table entry for that page. The AddrSpace class also has a new variable Swap of type SwapFile which will store the name of the swap file of that process. The AddrSpace class will also have locks to protect access to the swap file (swapFileLock) and the pageTable (pageTableLock). Whenever we attempt to access any of these, we will have to acquire the locks first. Also the AddrSpace class will have a new variable OpenFile *executable as The executable file will never be closed as long as the AddrSpace is not destroyed. We will have to close the executable in the destructor of the AddrSpace. Also we will store the nachos header in the address space class in the variable NOffH. Modifications done to AddrSpace constructor: We will find the code data size, init data size and uninit data size and stack size. Then we create a new instance of AddrSpaceEntry called pageTable of size numPages. We then map the pages. NOTE only virtual addresses are mapped and not their physical addresses. If they are pages having code or init data, we set inExecutable = 1, else it is 0. pageTable[i].virtualPage = i; pageTable[i].physicalPage = -1; pageTable.inExecutable = 1 or 0; pageTable[i].valid = TRUE; pageTable[i].dirty = FALSE; pageTable[i].readOnly = FALSE; We will also set the other variables: pageTable[i].onDisk=FALSE The FALSE represents that the uninit data has not been uploaded yet or stack pages have not been created yet. These data will only be written onto the disk when we encounter the page fault for the first time and modifications are made to the page and that page is replaced. Since we are always keeping the executable open, the code and init data pages can directly be uploaded from the executable. We are also saving the OpenFile pointer to the executable in a variable called exec We will have to make similar changes to NewStack function which is extending the address space when a new thread is added. In this case, now we know that all new pages added belong to stack. So, we do nothing with them except for extending the pageTable properly. We also make pageTable[i].onDisk = FALSE for the same reason as in the case of AddrSpace constructor. That is these data will only be written onto the disk when we encounter the page fault for the first time. PageFaultException: When ever we encounter a page fault, we first search for it in the IPT as described in part 1. If the page is not found in the main menory, we will have to replace a page in the main memory. Which page in main memory to replace is found by a page replacement scheme. We store the physical page which is being replaced in ReplacePage. We will implement the following page replacement schemes: FIFO Page Replacement Scheme: Here we make the ReplacePage = FIFOPage and update the next page to be replaced using FIFOPage = (FIFOPage+1)%NumPhysPages. Random Page Replacement Scheme: Here the rand() function in math.h is used to calculate the page to be replaced. ReplacePage = (rand()%NumPhysPages) LRU Page Replacement Scheme: Here we find the time since the page was last used. The page that was used the Least Recently is replaced. min = machine->getTimeUsed(0); minPage = 0; for(i = 1; count < NumPhysPages; count++) { if (machine->getTimeUsed(count) < min) { min = machine->getTimeUsed(count); minPage = count; } ReplacePage = minPage; } Here care is taken the replacement scheme will only start working only when all the pages in the memory has been occupied. That is if a free page is available in the memory, then that page is allorted and no other page is replaced. We set ipt[ReplacePage].replacing = 1 to indicate that the page has been selected to be replaced. Page Replacement: Here is how the page is replaced. If ipt[ReplacePage].valid == TRUE and ipt[ReplacePage].dirty == TRUE, it means that the data in the main memory has been modified and needs to be written onto the disk. We first copy the data (Whole page) in the main memory into a kernel variable copyBuf, byte by byte as follows while ( n >= 0 && n < PageSize) { copyBuf[n] = machine->mainMemory[physicalAddress]; n++; physicalAddress++; } The data in the copyBuf is then transferred into the corresponding swap file using ipt[ReplacePage].Process_Id->Swap->WriteSwap(copyBuf, virtualReplacePage). Now IPT is updated to store which page (the virtual page number and the Process_Id) is entering the main memory. Also the page table of currentThread->space is updated to store the physical page into which the virtual page is being mapped to by assigning currentThread->space->pageTable[vpn].physicalPage = ipt[ReplacePage].pPage. Now if the replacing page has inExecutable=1 and onDisk = 0 (because both code and uninit data can be present on the same page), then we have to read from the executable and load the same into the memory. This is done in the same way (using ReadSegemen) as it was done in the AddrSpace Constructor for Project 2. But we have to find the correct length to be read from the executable and the inFileAddress of the current page in the file first. So we use the nachos header from the address space to get the code and initData size, infileAddr and virtualaddress. If the Replacing page has onDisk = true, then we have to read it from the disk (Swap file). We do it using newBuf = currentThread->space->Swap->ReadSwap(vpn); and transfer it into the main memory, byte by byte while ( n >= 0 && n < len) { { machine->mainMemory[physicalAddress] = newBuf[n++]; physicalAddress++; } If the page is not in the executable, not on the disk, then we just zero out the page. After the page has been uploaded in the main memory, the TLB is also updated in the same manner as in part 1. 3. We have to implement the server as well as the client. We first discuss the implementation of the client and then of the server. Client: To implement the clients, we will have to change the semaphore system calls. Firstly, we will define three global variables in system.h:useNetworkSemaphores which will be set to 1 if "-m" is passed to nachos as a command line option else it is 0, machineID which will store the command line option passed with -m and serverID which will store the command line option passed with -o. The semaphore system calls will now look something like: a) CreateSemaphore(int identifier, int initialValue): If useNetworkSemaphores == 1, then have to send a message to the server requesting a new semaphore. First we need the name of the semaphore. The user program will pass the initial value of the semaphore as well as an integer identifier to the CreateSemaphore in this case. The CreateSempahore will read the integer value and then using sprintf, we will form a string "Sempahore %d" where %d will be replaced by the integer identifier from the user program. The client will then create a message to be sent to the server. The message from client to server will look like, "0 Sempahore %d %d " where 0 denotes the operation CreateSemaphore and Sempahore %d is the name of the semaphore. Using postOffice->Send we will send the message to serverID to mailbox 0 and then wait for the ack. The ack back from the server will of the format "%d " where %d will have the identifier to the semaphore which was created. It should be the same as the identifier input from the user program. If it is not, then throw up an error. Semaphore has now been created. Return back to the user program now. Thus each user program will identify a semaphore as an integer. Also each user program will have to send in a common integer identifier as the input to refer to a common semaphore. Note: All the strings are parsed using strtok function using space as the delimiter. b) Up(int identifier): If useNetworkSemaphores == 1, then have to send a message to the server requesting an up on the semaphore identified using identifier. Using sprintf, we will form a string "Sempahore %d" where %d will be replaced by the integer identifier from the user program. The client will then create a message to be sent to the server. The message from client to server will look like, "1 Sempahore %d " where 1 denotes the operation Up and Sempahore %d is the name of the semaphore. Using postOffice->Send we will send the message to serverID to mailbox 0 and then wait for the ack. The ack back from the server will of the format "%d " where %d will have the identifier to the semaphore which was created. It should be the same as the identifier input from the user program. If it is not, then throw up an error. c) Down(int identifier): If useNetworkSemaphores == 1, then have to send a message to the server requesting a down on the semaphore identified using identifier. Using sprintf, we will form a string "Sempahore %d" where %d will be replaced by the integer identifier from the user program. The client will then create a message to be sent to the server. The message from client to server will look like, "2 Sempahore %d " where 2 denotes the operation Down and Sempahore %d is the name of the semaphore. Using postOffice->Send we will send the message to serverID to mailbox 0 and then wait for the ack. The ack back from the server will of the format "%d " where %d will have the identifier to the semaphore which was created. It should be the same as the identifier input from the user program. If it is not, then throw up an error. d) DestroySemaphore(int identifier): If useNetworkSemaphores == 1, then have to send a message to the server requesting a DestroySemaphore on the semaphore identified using identifier. Using sprintf, we will form a string "Sempahore %d" where %d will be replaced by the integer identifier from the user program. The client will then create a message to be sent to the server. The message from client to server will look like, "3 Sempahore %d " where 3 denotes the operation DestroySemaphore and Sempahore %d is the name of the semaphore. Using postOffice->Send we will send the message to serverID to mailbox 0 and then wait for the ack. The ack back from the server will of the format "%d" where %d will have the identifier to the semaphore which was created. It should be the same as the identifier input from the user program. If it is not, then throw up an error. This completes the implementation of the client. Server: In main.cc, if the the input command line argument with "-m" is 0, then call implementSemaphoreServer() which has been written in nettest.cc. Now we describe implementSemaphoreServer(). After a few intializations described below, we have an infinite loop running. The first statement of the infinite loop is a postOffice->Receive on mailbox number 0. On receiving a message, we first scan the string using strtok and the space as the delimiter. The message should of the form "%d %s". Using %d in the message, the server identifies which operation is needed to be performed. If it is 0, we have to create a semaphore, if it is 1, we have to do a up, a 2 means a down and a 3 means DestroySemaphore. To manage these semaphores, we create four new classes. First we describe these four classes. class sharedSemaphore: This function is quite similar to the semaphore class but does not put the threads to sleep when semaphore's value is zero. Variables: a) int value: the value of the sempahore. b) List *waitQ: The waitQ of the sempahore. functions: a) constructor: takes the initial value as its input. b) destructor: deletes the waitQ. c) void *Up(): If waitQ is empty, increments the value else it removes the topmost entry in the list and returns back the entry. d) bool Down(void *entry): If value > 0, returns TRUE, else puts the entry in the waitQ and returns FALSE. e) bool isWaitQEmpty(): Returns TRUE if waitQ is empty else returns FALSE. class entryToBeSaved: This class is used to save the information about the client which called a down on a semaphore whose value is 0. variables: a) PacketHeader inPacketHdr; b) MailHeader inMailHdr; class sharedSemaphoreTableEntry: This class stores the sharedSemaphore pointer (semaphorePointer) being used by the user program, its integer identifier (int whichSemaphore), int markedForDeletion which is used for while destroying semaphores when there are threads in the wait queue, and a pointer to the next sharedSemaphoreTableEntry. The functions of the class are as follows: a) sharedSemaphoreTableEntry(sharedSemaphore *semaphorePointer, int whichSemaphore): Constructor b) ~sharedSemaphoreTableEntry(): Destructor class sharedSemaphoreTable: This class keeps a list of all the semaphores used by the user programs. It has two private variable, first and last which points to the start and end of the list. The functions of the class are as follows: a) sharedSemaphoreTable(): Constructor b) ~sharedSemaphoreTable(): Destructor c) void Append(sharedSemaphoreTableEntry *toBeAdded): Add sharedSemaphore to the list. d) int Remove(sharedSemaphoreTableEntry *sem): Removes the sharedSemaphoreTableEntry from the sharedSemaphoreTable. e) sharedSemaphoreTableEntry *whichSemaphore(int valueOfSemaphore): Find the sharedSemaphoreTableEntry corresponding to the integer identification valueOfSemaphore. f) bool isEmpty(): Checks if the list is empty or not. We initialize SharedSemaphoreTable = new sharedSemaphoreTable before the infinite while loop. Now we describe what a server needs to do for each of the semaphore functions. CreateSemaphore: We will scan the message using strtok and seperate into "Semaphore", "%d" and "%d" where the first integer identifies the semaphore and the second integer specifies the intial value. Then we check in the SharedSemaphoreTable if there exists a sharedSemaphore for the given integer value. If it exists, then using sprintf, compose an ack "%d " where %d is the integer identifier to of the sharedSempahore, and send it back to inPktHdr.from to mail box id inMailHdr.from. If it does not exist, create a new sharedSemaphore with the given intial value, create a new sharedSemaphoreTableEntry, append it to SharedSemaphoreTable and send an ack back same as described above (which contains the integer identifier). Up: We will scan the message using strtok and seperate into "Semaphore" and "%d" where the integer identifies the semaphore. Then we check in the SharedSemaphoreTable if there exists a sharedSemaphore for the given integer value. If not, send back an ack having a "-1 ". Compose an ack "%d " where %d is the -1, and send it back to inPktHdr.from to mail box id inMailHdr.from. If there exists a sharedSemaphore, then get the sharedSemaphoreEntry from the SharedSemaphoreTable and get the sharedSemaphore from sharedSemaphoreEntry. Now call a Up on the sharedSemaphore. If the Up returns NULL, then compose an ack "%d " where %d is the integer identifier to of the sharedSempahore, and send it back to inPktHdr.from to mail box id inMailHdr.from. If it returns a value, then first send an ack "%d " where %d is the integer identifier of the sharedSempahore to inPktHdr.from to mail box id inMailHdr.from. The value returned will be an instance of entryToBeSaved. Then send another Ack "%d " where %d is the integer identifier of the sharedSempahore to entryToBeSaved.inPktHdr.from to mail box id entryToBeSaved.inMailHdr.from. Then we check if the sharedSemaphore has been marked for deletion and the waitQ is empty. If both the conditions are TRUE, then delete the sharedSemaphore, delete the sharedSemaphoreTableEntry and remove it from the SharedSemaphoreTable. Down: We will scan the message using strtok and seperate into "Semaphore" and "%d" where the integer identifies the semaphore. Then we check in the SharedSemaphoreTable if there exists a sharedSemaphore for the given integer value. If not, send back an ack having a "-1 ". Compose an ack "%d " where %d is the -1, and send it back to inPktHdr.from to mail box id inMailHdr.from. If there exists a sharedSemaphore, then get the sharedSemaphoreEntry from the SharedSemaphoreTable and get the sharedSemaphore from sharedSemaphoreEntry. Now create an instance of entryToBeSaved and assign entryToBeSaved.inPktHdr = inPktHdr entryToBeSaved.inMailHdr = inMailHdr. Now call a Down on the sharedSemaphore and pass the entryToBeSaved to it. If down returns TRUE, then send an ack "%d " where %d is the integer identifier of the sharedSempahore to inPktHdr.from to mail box id inMailHdr.from else do nothing. DestroySemaphore: We will scan the message using strtok and seperate into "Semaphore" and "%d" where the integer identifies the semaphore. Then we check in the SharedSemaphoreTable if there exists a sharedSemaphore for the given integer value. If not, send back an ack having a "-1 ". Compose an ack "%d " where %d is the -1, and send it back to inPktHdr.from to mail box id inMailHdr.from. If there exists a sharedSemaphore, then get the sharedSemaphoreEntry from the SharedSemaphoreTable and get the sharedSemaphore from sharedSemaphoreEntry. Now check if there is any thread waiting in the waitQ of the sharedSemaphore. If there is none, then destroy the sempahore else mark it for deletion. IV. Implementation: 1. Files Modified: In the userprog directory: exception.cc,addrspace.h,addrspace.cc In the threads directory:system.h, system.cc, scheduler.cc Data Structures Added, and the file they were added to: IptEntry in addrspace.cc Functions added and in which file: IptEntry::IptEntry() -- in userprog/addrspace.cc IptEntry:: ~IptEntry() -- in userprog/addrspace.cc Functions modified and in which file: void ExceptionHandler(ExceptionType which) -- in userprog/exception.cc void RestoreState() -- in userprog/addrspace.cc void Initialize(int argc, char **argv) -- in threads/system.cc void Scheduler::Run (Thread *nextThread) -- in threads/scheduler.cc int copyin(unsigned int vaddr, int len, char *buf) -- in userprog/exception.cc int copyinz(unsigned int vaddr, int len, char *buf) -- in userprog/exception.cc int copyout(unsigned int vaddr, int len, char *buf) -- in userprog/exception.cc int Create_Syscall(unsigned int vaddr) -- in userprog/exception.cc int Open_Syscall(unsigned int vaddr) -- in userprog/exception.cc int Write_Syscall(unsigned int vaddr, int len, int id) -- in userprog/exception.cc int Read_Syscall(unsigned int vaddr, int len, int id) -- in userprog/exception.cc int Exec_Syscall(unsigned int vaddr) -- in userprog/exception.cc 2. Files Added: NONE Files Modified: addrspace.h, addrspace.cc, exception.cc, Makefile -- in userprog directory system.cc, main.cc, system.h -- in threads directory Makefile -- in vm directory machine.h -- in machine directory Data structures added: class AddrSpaceEntry in file userprog/addrspace.cc, userprog/addrspace.h AddrSpaceEntry() int dataType bool inMemory bool onDisk int virtualPage int physicalPage bool valid bool readOnly bool use bool dirty class SwapFile in userprog/addrspace.cc, userprog/addrspace.h char *fileName; int OffSet; SwapFile(char * Name); void WriteSwap(char * buf, int OSet); char * ReadSwap(int Oset); Data structures modified: class AddrSpace in userprog/addrspace.cc, userprog/addrspace.h SwapFile Swap unsigned int noChangeSize NoffHeader NOffH OpenFile *exec int initDataStart Functions Added:AddrSpaceEntry::AddrSpaceEntry() -- in userprog/addrspace.cc, userprog/addrspace.h SwapFile::SwapFile(char * Name) -- in userprog/addrspace.cc, userprog/addrspace.h void SwapFile::WriteSwap(char * buf, int OSet) -- in userprog/addrspace.cc, userprog/addrspace.h char * SwapFile::ReadSwap(int Oset) -- in userprog/addrspace.cc, userprog/addrspace.h Functions Modified: AddrSpace::AddrSpace() -- in userprog/addrspace.cc, userprog/addrspace.h AddrSpace::~AddrSpace() -- in userprog/addrspace.cc, userprog/addrspace.h AddrSpace::NewStack() -- in userprog/addrspace.cc, userprog/addrspace.h In threads/system.cc: void Initialize(int argc, char **argv) In userprog/exception.cc: void ExceptionHandler(ExceptionType which) In threads/main.cc: int main(int argc, char **argv) 3. Files Modified: In the network directory: nettest.cc, Makefile In the userprog directory: exception.cc, Makefile In the threads directory: main.cc, system.cc, system.h In the code directory: Makefile.common In the test directory: Makefile Files Added: In the network directory: sharedSemaphore.cc, sharedSemaphore.h In the test directory: test11.c, test12.c, test14.c, test15.c Data Structures Added, and the file they were added to: sharedSemaphore, entryToBeSaved, sharedSemaphoreTableEntry, sharedSemaphoreTable -- in sharedSemaphore.h Functions added and in which file: In network/sharedSemaphore.cc: sharedSemaphore::sharedSemaphore(int val), sharedSemaphore::~sharedSemaphore(), void *sharedSemaphore::Up(), bool sharedSemaphore::Down(void *entry), bool sharedSemaphore::isWaitQEmpty(), entryToBeSaved::entryToBeSaved(PacketHeader pkt, MailHeader mail), entryToBeSaved::~entryToBeSaved(), sharedSemaphoreTableEntry::sharedSemaphoreTableEntry(sharedSemaphore *sem, int val), sharedSemaphoreTableEntry::~sharedSemaphoreTableEntry(), sharedSemaphoreTable::sharedSemaphoreTable(), sharedSemaphoreTable::~sharedSemaphoreTable(), void sharedSemaphoreTable::Append(sharedSemaphoreTableEntry* toBeAdded), int sharedSemaphoreTable::Remove(sharedSemaphoreTableEntry* sem), bool sharedSemaphoreTable::isEmpty(), sharedSemaphoreTableEntry *sharedSemaphoreTable::whichSempahore(int valueOfSemaphore). In network/nettest.cc: void implementSemaphoreServer(). In userprog/exception.cc: int Network_CreateSemaphore_Syscall(int semIdentifier, int initialValue), void Network_DestroySemaphore_Syscall(int semIdentifier), void Network_Up_Syscall(int semIdentifier), void Network_Down_Syscall(int semIdentifier). In test/test11.c: int main() In test/test12.c: int main() In test/test14.c: int main() In test/test15.c: int main() Functions modified and in which file: In threads/system.cc: void Initialize(int argc, char **argv) In userprog/exception.cc: void ExceptionHandler(ExceptionType which) In threads/main.cc: int main(int argc, char **argv) V. Testing: 1. Part 1 is tested while testing for part 2. It can be tested independently by increasing the NumPhysPages to 512 and uncommenting the IPT population in the addrspace constructor and newStack. 2. a) How to test: nachos -x ../test/matmult -rs -P Test output: Matrix multiplication program. We are printing out the value passed to exit system call, which in this case is the result of the matrix multiplication. The value printed out should be 7220. b) How to test: nachos -x ../test/sort -rs -P Test output: Sorting program. We are printing out the value passed to exit system call, which in this case is the result of the sort. The value printed out should be 1023. c) How to test: nachos -x ../test/vmtest1 -rs -P Test Output: A single small sequential test. d) How to test: nachos -x ../test/vmtest2 -rs -P Test Output: A single large sequential test. e) How to test: nachos -x ../test/r_vmtest1 -rs -P Test output: A single small random test. f) How to test: nachos -x ../test/r_vmtest2 -rs -P Test output: A single large random test. g) How to test: nachos -rs -P -x ../test/test1 Test Output: Forks two threads. Corresponding messages from all the threads should be printed. h) How to test: nachos -rs -P -x ../test/test3 Test Output: Forks five threads. Corresponding messages from all the threads should be printed. i) How to test: nachos -rs -P -x ../test/test4 Test Output: Execs another process which forks three more threads. Corresponding messages from all the threads should be printed. j) How to test: nachos -rs -P -x ../test/test2 Test Output: Execs two matmult processes. Both should run to completion. 3. a) How to test: Open two different windows. Type on Window 1: nachos -m 0 Window 2: nachos -m 1 -o 0 -x ../test/test11 Test Output: test11 has a sequence of createSemaphore, up, down and destroySemaphore. b) How to Test: Open five different windows. Type on Window 1: nachos -m 0 Window 2: nachos -m 1 -o 0 -x ../test/test12 Window 3: nachos -m 2 -o 0 -x ../test/test14 Window 4: nachos -m 3 -o 0 -x ../test/test12 Window 5: nachos -m 4 -o 0 -x ../test/test14 Test Output: test 12 creates semaphore, calls a up and exits. test14 creates a semaphore, calls a down, destroys it before exiting. By giving a small delay, it can be seen that a process does not wake up until someone calls an up on the semaphore, thus showing proper inter process synchronization has been achieved. c) How to test: Open two different windows. Type on Window1: nachos -m 0 Window 2: nachos -m 1 -o 0 -x ../test/test15 Test Output: test15 calls a up, down and destroySemaphore on an invalid semaphore. corresponding error messages should be printed out. VI. Discussion: 3. Experiment expectation: All the test cases should pass. The processes should be properly synchronized and proper error messages should be printed out. Experiment result: All test cases pass. Explanation: Implementation of inter process synchronization using a semaphore server is correct. vii. Miscellaneous: 1. Please note the changes in the Makefile.common, and Makefiles in network, userprog, test and vm. Without these changes, the code will not compile. 2. Please note the changes in machine.h 3. Please retain nachos.ld in the makeFile in the test directory. 4. Run the server before the clients in part 3.