Title: WRITEUP for Project 4, Fall 2004 Date: 12/03/2004 Group: Name Email Tushar Makhija tmakhija@usc.edu Apoorva Jindal apoorvaj@usc.edu Nithin Dinker Kamath nkamath@usc.edu I. Requirements: 1. In this part of the project we have to implement the Project 2 part 3 now within a distributed system. We are using project 3 part 3 and hence all the semaphores used in the Sleeping Barber synchronisation problem will now be network semaphores. Here we are primarily going to implement a distributed Sleeping Barbers across all your Nachos clients. Whether they are in different Nachos clients, or on the same client in a different process, or the same process. All Nachos user programs are all part of the same barbershop.We are going to have both the Customers and Barbers will be using the distributed semaphore calls from Project 3 Part 3, to implement this problem. 2. a) In Part 2 we have to implement a mechanism to handle lost packets over the implementation of Part 1 .Here we would use the -l parameter in Nachos. This is the parameter to 'loose' packets. We have to code for values of -l to be less than 1 and test the code to work within a finite amount of time with values between 0.2 and 0.3. b) The client thread cannot just wait for a response for service from the server. Hence if a reply essage gets lost we require to code for re-sending the same message( request) back to server after a time interval else we will deadlock. Thus here we require a timing thread to account for every send and receive. 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. 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. Variables: On the server side we create 2 new Global variables: noOfFreeBarbers and noOfBarbers. We also create 2 new global lists:freeBarberList and sleepingCustomer. The list keeps track of the barbers that are free and the customers that are waiting to be served respectively. All the customers wil be served irrespective of which client they belong to. We also have to define 4 new Systems calls: int getBarberNumber_Syscall(): This system call gets the value of number of free barber (viz. val ),that the given instance from the server. It returns (2*val+1). Next it increments the global variable noOfBarbers by 1 . The message from the client to the server is in the format "0 Barber". The acknowledgement from the server is in the format "Barber %d" Using the return value we get from getBarberNumber(), we creat two network semaphores using the int Network_CreateSemaphore_Syscall(int semIdentifier, int initialValue). void registerBarber_Syscall(int barberSemaphore): This system call increments the global variable noOfFreeBarbers by 1 and adds the corresponding semaphore id to the freebarberList. The message from the client to the server is in the format "1 Barber". The acknowledgement from the server is in the format "Barber %d" int findBarber_Syscall(): This system call is executed by the customer. When a customer is created and calls this function, we check the noOfFreeBarbers on the server. If it is not zero then we decrement it, and search the list freeBarber list. The top value (the semaphore identifier of the barber is read and returned to the customer. If however no barber is available then the customer is put into the waiting list sleepingCustomers. The message from the client to the server is in the format "0 Barber". The acknowledgement from the server is in the format "Barber %d". void freeBarber_Syscall(int barberSemaphore): After the barber finishes cuutting the hair he calls this function. We first check if there are any customers waiting in the sleepingCustomer list. If the list is not NULL then the semaphore id is assigned to the top most customer waiting. If there are no customer waiting, noOfFreeBarbers is incremented and the semaphore id is added to the freeBarberList. When a barber is created it calls: = getBarberNumber(). Then two semaphores and are created as mentioned as above. After the barber registers himself with the server he downs the semaphore , signalling that he is sleeping. When a customer arrives it is given a barber number using the system call: = findBarber(). After this the customer does a up on semaphore signalling the barber to wake up and start cutting the hair. Then the customer downs the semaphore , waiting for the barbr to finish. The barber yields, simulating a hir cut, and then ups , telling the customer that hair cut is done. The customer then exits and the barber calls FreeBarber to make himself available to any waiting customer. If there are no waiting customer then the barber goes ack to sleep by doing a down on semaphore .s Also note that whenever we fork a new thread we will associate a new mail box id with that thread given by the global variable availableMailBox and then we incfrement it. To ensure mutual exclusion we have a lock associated with it given by the availableMailBoxLock. For the Bonus Part 3 we have made the following modifications: On the server side we declare a new class passForkedThread. This class' function is forked to make it multithreaded. The class will have the following parameters inPktHeader, OutPktHeader, message. We also have locks on semaphore tables and semaphores. Hence when call the CreateSemaphore call we along with the semaphore we create corresponding locks. For the sleeping Barber Implementation, along with the variables previously created we create: barberLock: to control access to noOFBarbers, noOfFreeBarbers and freeBarberList SleepingCustomerLock: For syncronisation and deadlock prevention while modifying the sleepingCustomerQueue. The server has a main thread which keeps on checking the received messages. When a message, then the main thread forks another thread and passes on the parameters: message, inpktHdr, inMailHdr. 2. We have implemented this part along with the bonus part 3. On the client side the following modifications were made. When a client wants to create a semaphore, like part 1 we call Network_CreateSemaphore_Syscall(int semIdentifier, int initialValue). We also maintain a variable called SequenceNo which uniquely identifies the message.After the system call is called the thread forks a timer thread. this thread has the following variables: The message, sequenceNo inPktHeader, outPktHeader and a variable "status" which is set to zero. The function of the timer thread is to wait for a certain amount of time and after that check the "status" variable. If the variable is set to 1 then kill itself or otherwise resend the message and wait again. When the original thread does the receive() function and if it has received a reply from the sever then the thread sets the timer variable "status" to 1. The function also passes the message and sends information to the ack thread. The ack thread: This thread receives the messages from the client threads and puts then in a data structure. It also sends ack message to the server. destroySemaphore and Up have same functionality and are modified like the createSemaphore system call. That is a timer thread is forked after calling the system call. The Down call is slightly different. Here the server returns a acknowledgement saying that it has received the request for the down. Note: this is just the akc and not the reply which says thay down is actually executed. Here we set the timer variable to 2 and not 1. When we get the actual reply we set the timer variable to 1. The remaining part is same like other system calls. On the server side the following modifications are made: The server has a main thread which keeps on checking the received messages. It also has a list in which it saves the MailBox, SequenceNo and the PostID When a message is received it first checks the list to see if it is a new message or a resend. If the message is new then the main thread forks another thread and passes on the parameters: message, inpktHdr, inMailHdr, semaphore and a lock. If the message is a resend then the main thread asks the corresponding thread to send back the reply again. IV. Implementation: 1. 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 test directory: Makefile In the network directory: sharedSemaphore.cc, sharedSemaphore.h Files Added: In the test directory: barberShop.c,multiBarberShop.c Data Structures Added, and the file they were added to: freeB -- in sharedSemaphore.h, freeB::freeB(int val) -- in sharedSemaphore.cc freeB::~freeB() -- in sharedSemaphore.cc Functions added and in which file: In userprog/exception.cc:int getBarberNumber_Syscall(), void registerBarber_Syscall(int barberSemaphore), int findBarber_Syscall(), void freeBarber_Syscall(int barberSemaphore). Functions modified and in which file: In threads/system.cc: void Initialize(int argc, char **argv) In threads/main.cc: int main(int argc, char **argv) In network/nettest.cc: void implementSemaphoreServer(). V. Testing: VI. Discussion: