Title: WRITEUP for Project 2, Fall 2004 

Date: 10/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 of the project we have to implement the following system calls: Yield, Exit, CreateSemaphore, DestroySemaphore, Up and Down. A few issues we have to take care of are that pointers to kernel data structures are not passed to the user program in CreateSemaphore. Another issue to take care of is in the exit system call, whether the thread is the last thread of the process or whether the thread is the last thread of the last process.

2.
In part 2 of the project, we have to implement the following system calls: Fork and Exec. These system calls require multiprogramming. In fork, we have to create a new thread, assign a stack to it, fork it and put it in the ready Queue. In exec, we have to create a new process. The process has to be assigned an address space and the first thread has to be forked. 

3.
In part 3 of the project, we have to implement the sleeping barber synchronization problem by using the system calls implemented in parts 1 and 2. There can be multiple barbers and customers as well as there can be more than one processes running. 

II. Assumptions:
1.
a) Since we are  not implementing a join, there is no concept of a parent and a child.
b) Only an integer value, which is not the pointer to the semaphore instance, will be visible to the user programs.

2. 
a) We assume that there are 512 pages of memory available in nachos. We will change NumPhysPages to 512 in machine.h.
b) We are allowing the process to have a maximum of 15 threads.
c) There will be no change in the number of pages available to the process once the address space allocation is done. While allocating memory we are taking care that we allocate enough pages for the stack of 15 threads.
d) If a process has more than 15 threads, when the 16th thread asks for stack space, we generate a error message and halt the NACHOS


3. 
a) We are assuming that the maximum number of barbers is fixed = MaxNoOfBarbers. 
b) The customer goes to the first available barber. 
c) We have used the book "Modern Operating Systems" by Andrew S. Tanenbaum for guidelines and psuedo code of the sleeping barber problem.

III. Design:
1.
Semaphores:
First make changes in syscall.h. Write Add new syscall codes, SC_CreateSemaphore 11, SC_DestroySemaphore 12, SC_Up 13 and SC_Down 14. Then add the new function prototypes,
int CreateSemaphore(int value);
void DestroySemaphore(int whichSemaphore);
void Up(int whichSemaphore);
void Down(whichSemaphore);

Make changes in the start.s directory by copying and pasting the lines for halt system call and then replacing it with CreateSemaphore, DestroySemaphore, Up, Down.

Functions:
CreateSemaphore: We will keep a global list (which will be accessible by using a lock semaphoreTableLock). Each element in that list belongs to a class semaphoreTableEntry which has variables, semaphore instance pointer, the integer value whichSemaphore, destroySemaphoreValue which stores the number of threads which have called destroySemaphore on the particular semaphore and a pointer to the address space of the process with which the particular semaphore is associated. CreateSemaphore will read the intial value from R4 and create an instance of the class Semaphore. Then it will acquire semaphoreTableLock and update the list by adding its entry. Then it will write its unique integer value to the register R2.
DestroySemaphore: It takes the unique integer value of the particular semaphore to be destroyed. First we check that the thread calling the destroysemaphore belongs to the process. Then we mark the semaphore to be destroyed, but it cannot be destroyed if there are other threads running in the same process because, they might want to use this semaphore. So the semaphore will not be destroyed until the number of threads in the process is equal to the number of threads who have called the destructor. We will use a condition variable to implement this.
Up: It takes the unique integer value of the semaphore, it checks if the thread belongs to the correct process, it looks up the semaphore instance pointer from the table after acquiring the lock and then calls the V operation on the semaphore.
Down: It takes the unique integer value of the semaphore, it checks if the thread belongs to the correct process, it looks up the semaphore instance pointer from the table after acquiring the lock and then calls the P operation on the semaphore.

If in any of the above functions, if the passed whichSemaphore integer is not a valid value, an error will be printed. 
Yield: It just calls currentThread::Yield.
Exit: We will maintain a global variable numOfActiveThreads which will count the number of active threads across all the processes. Its intial value will be one because of the main thread which executes with StartProcess. Also each process maintains a counter in its processTable numOfThreads which counts the number of threads in the process. If the thread is not the last thread in the process, it just calls currentThread::Finish on itself. If it is the last thread of the process but not the last active thread in nachos, then it calls currentThread::Finish on itself after deleting the address space of the process and all the semaphores associated with this process. If the thread is the last active thread in nachos, then it deletes the address space of the process, the semaphores associated with the process and call interrupt->Halt() to stop the nachos.

2.
Functions:
Exec(): We first find the virual address of the process from the register r4 using  vaddr=machine->ReadRegister(4) .
Then the file name is extracted by using copyinz as used in the implementation of open_syscall. After getting the file name, which is stored in buf, the file is opened. 
The file pointer, filePointer, is given by filePointer=fileSystem->open(buf) and the addrspace space=new addrspace  (filepointer) is executed to allocate new address space for the process. A new thread called processThread is created and space that was created is allocated to this thread. This thread then forks the function exec_thread by calling processThread->Fork(exec_thread).

void exec_thread(): This function increments the numberOfActiveThreads count. It also initializes all the registers by calling currentThread->space->initRegister(). 
Previous state is restored using currentThread->space->RestoreState() before the thread is executed, machine->Run().

Fork(): This system call forks a new thread in the same address space. Like Exec we get the virtual address of the function pointer vaddr reading the register R4. A new thread called kernelThread is created. Stack space is then assigned by calling the function newStack(currentThread->space).The kernelThread then forks the function kernel_Thread.

kernel_Thread(int vaddr): This function updates and assigns the virtual address, vaddr, to the PCReg and makes PCReg+4 as the next available PCReg. We restore the state, then we write to the stack register value of numPages * PageSize - 16, and then call the machine->run().

newStack(): Newstack creates new stack space for the thread. Then it adds divRoundUp(UserStackSize,PageSize) new pages to numPages, uses bitmap (as in the address space constructor) to find out the available free pages and updates the PageTable. Also the stackpage and number of threads is also incremented. If no memory is available then this function returns a error message. 

deleteStack(): This function is basically called to free the physical memory. Once a thread has finished using the stack memory, it needs to be freed. We first read the stack register and then calculate the stackpage number. We then free the physical memory of that page and preceeding 7 pages by using memMap.Clear(pageTable[i].physicalPage) (i gives the pagenumber). We also invalidate the entries of the these pages in the pagetable, pageTable[i].valid = FALSE;

3.
Global Variables:
Semaphore: customer: Counts the number of customers waiting for a barber. Initial value = 0
Semaphore: barber: Counts number of free awake barbers. Initial value = 0.
Array of ints: CustomerHairType[MaxNoOfBarbers] = 0 if barber has not been created, 1 for long, 2 for medium and 3 for short and 4 if the barber is not serving anyone yet.
Binary Semaphore: mutex: For mutual exclusion for the global variable CustomerHairType. Initial value = 1.
Array of binary semaphores: start_cut[MaxNoOfBarbers]: To signal the barber that he can start cutting the hair of the customer after he has placed his hair type in CustomerHairType. Initial value = 0.
Array of binary semaphores: finish_cut[MaxNoOfBarbers]: To signal the customer that his hair has been cut and he can leave the shop. Initial value = 0.

Functions: 
Barber(): First each barber has to be assigned a number. This number value is stored in an integer num. First the barber downs mutex. Then he goes sequentially through the array CustomerHairType to find the first position of 0. As soon as he finds one, he stores the number where he found the 0 in num, changes CustomerHairType[num] to 4 and up's mutex. Now this number gets assigned to the particular barber. The rest of this function is inside an infinte loop. Inside the infinite loop, the barber will first down the number of customers to check if there are any waiting customers. If there are none, then the barber goes to sleep. If he is woken up, then that means there is a customer in to have his hair cut. So he calls a up on barber. Then he calls a down on start_cut[num] because he cannot start cutting until the customer has entered his hair type in CustomerHairType[num]. When he is woken up, then acquires (calls a down) on mutex, reads CustomerHairType[num]. Then calls a up on mutex. If CustomerHairType[num] = 1, yields 3 times, CustomerHairType[num] = 2, yields 2 times CustomerHairType[num] = 1, yields once. Then he ups finish_cut[num] to tell the customer that the hair cut is done and he can leave. Then the infinite loop will execute again.

Customer(): First the customer does an up on customer. Then he does a down on barber. If he goes ahead, it means that a barber is free. Then it acquires (does a down on) mutex, searches through CustomerHairType for a 4. When it gets a 4, it stores the num value in the variable barberNo, sets the value of CustomerHairType[barberNo] to his hair type. Then the customer releases the mutex (calls a up on it), then calls a up on start_cut[barberNo] and then does a down on finish_cut[barberNo]. Then it calls Exit(0).

IV. Implementation: 

2.
Files Modified:  In the userprog directory:addrspace.h,  addrspace.cc , exception.cc
	         In the test directory: makefile
                 In the threads directory:synch.h and synch.cc
                 In code directory: Makefile.common 
                 In machine directory:machine.h

Files Added:In the test directory:codetest.c, test1.c , tesxt2.c , test3.c, test4.c, test5.c

Data Structures added, and the file they were added to: NIL

Data Structures modified, and the file they were added to: class addrspace -- in file  userprog/addrspace.h

Variables added, and the file they were added to: maxNoOfThreads -- in file userprog/addrspace.h

Variables modified, and in which file: NumPhyPages -- in machine/machine.h

Functions added and in which file:	NewStack() --    in file userprog/addrspace.h
					deleteStack() -- in file userprog/addrspace.h
					void addrspace::NewStack() -- in file userprog/addrspace.cc
					void sddrspace::deleteStack() --  in file userprog/addrspace.cc
					void kernel_Thread(int virAddr) -- in file userprog/exception.cc
					void Fork_Syscall(int viraddr) --  in file userprog/exception.cc   
					void exec_Thread() -- in file userprog/exception.cc
					int Exec_Syscall(int viraddr) -- in userprog/exception.cc
					void testfork() -- in test/codetest.c
					int main() -- in test/codetest.c
					void testfork() -- in test/test1.c
					int main() -- in test/test1.c
					void testfork() -- in test/test2.c
					int main() -- in test/test2.c
					void testfork() -- in test/test3.c
					int main() -- in test/test3.c
					int main() -- in test/test4.c
					void testfork() -- in test/test5.c
					int main() -- in test/test5.c

Functions modified and in which file:	void addrspace::addrspace() -- in file userprog/addrspace.cc

3.
Files Modified:	In the test directory: makefile

Files Added: In the test directory: barberShop.c and multiBarberShop.c

Data Structures added, and the file they were added to: NIL
 
Data Structures modified, and the file they were added to: NIL

Variables added, and the file they were added to:
MaxNoOfBarbers int barber, int customer, int mutex, int CustomerHairType[MaxNoOfBarbers], int start_cut[MaxNoOfBarbers], int finish_cut[MaxNoOfBarbers]

Variables modified, and in which file: NIL

Functions added and in which file:
void barber(), void customer1(), void customer2(), void customer3(), int main() in test/barberShop.cc
int main() in test/multiBarberShop.cc

Functions modified and in which file:NIL

V. Testing:
2.
a) nachos -x ../test/codetest -rs <integer>
This test case is used to test Fork and Exec system calls.
b) nachos -x ../test/test1 -rs <integer>
This test case is used to test the Fork system call implementation. 5 processes are forked and then exited to carry out the test.
c) nachos -x ../test/test2 -rs <integer>
This case tests the condition wherein a number of processes are created and NACHOS thus goes out of memory. Here we expect that NACHOS exits gracefully with an error message.
d) nachos -x ../test/test3 -rs <integer>
In this test case we test that when the number of threads forked in a process exceeds the maximum limit, gives an error message and exits gracefully
e) nachos -x ../test/test4 -rs <integer>
This test is designed to check the implementation of Exec system call.
f) nachos -x ../test/test5 -rs <integer>
In this test case we check the Yield, Exec and Fork system call implementations. For this purpose a sequence of fork, execs and yields are executed.

3. 
a) nachos -x ../test/barberShop -rs <integer>
This test checks the implementation of Sleeping Barber Syncronization problem. We create 3 barbers and then calls 9 customers (3 each for diffrent type of Hair_CutStyle. Additionally it also tests the successful implementaion of Part 1 and Part 2 of the Project.
b) nachos -x ../test/multiBarberShop -rs <integer>
Here we Exec barberShop multiple number of times. Hence we check whether we have successfully implemented Parts 1 and 2 and also made NACHOS, which is inherently an Unirocess system, run multiple processes at the same time.

VI. Discussion: