Title: WRITEUP for Project 1, Fall 2004 Date: 09/19/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 I of the project, we have to implement locks and condition variables. We have to write functions to acquire and release locks, and functions wait, signal and broadcast to implement a condition variable. While implementing, we will have to ensure proper error messages when something illegal happens, for example a thread which had not acquired the lock tries to release it or a waiting thread is signalled with the wrong lock. We also have to check that the implementation runs properly for the given test suite. 2. Part II of the project requires simulation of the working of a Carl's Jr. restaurant. This is basically a synchronization problem. There are several threads running in parallel, like one thread for each ordertaker, one thread for each customer, another thread for the manager and one thread for each cook. These threads access a lot of global shared variables and we have to ensure proper synchronization to avoid race conditions. We will have to make more than one monitor to synchronize interactions between these threads. We also have to ensure that a customer does not have to wait forever. II. Assumptions: 1. a) We assume that a condition variable is always used with the same lock. b) As specified in the specifications, we will implement Mesa semantics. c) We will use primitive thread routines as our building blocks. 2. a) It is a 24 hr. restaurant. Hence the manager thread will not get killed from within the program. The user will have to use ctrl-C to terminate the program. b) The first customer for a food item (except soda) always waits. This assumption is made because we assume that the manager creates the first cook for a food item when the first customer for that particular food item comes, ie. the food is cooked to order. c) The manager kills all the threads of the cooks cooking the food item if the quantity of the food item > 5. d) The manager forks new cooks the quantity of the food item falls below 2 or the order backlog becomes greater than 2. Note assumption b) when the first customer comes in. So the manager creates cooks only when either first cutomer comes in or the quantity of the food item falls below 2 or the order backlog becomes greater than 2. e) There are a fixed number (4 in our case) of order takers. f) There is only 1 line for customers, not different lines for each order taker. g) Whenever customer gets a number to wait, the manager bags the food. h) Soda is infinite. i) The manager will wake up only that customer who has the proper order number. j) The customer will order only one of the burgers, but any number of them. But this number cannot exceed 4. k) The customer can order a maximum of 4 fries. l) If a customer comes in and part of his order cannot be completed, then he has to wait. The ordertaker keeps aside the partial order from the already cooked food which is visible to the manager only, not the other ordertakers. It is the manager who bags the complete order. III. Design: 1. i) Locks: Class is Lock. The variables associated with this class are - name: Name of the lock. - value: This variable shows whether the lock is free or busy. - owner: This void* variable stores the thread pointer which has acquired the lock. - waitQ: This is a list which keeps a list of the waiting threads. It is FIFO in nature. All these variables are private. The constructor of a lock will take its name as the input. The three functions associated with this class are: a) isHeldByCurrentThread(): This function will check whether the owner of the lock is the same as the thread being executed in the CPU. It will compare the thread pointer of the the current thread in the CPU (which is obtained by using currentThread) with the thread pointer of the lock. If they match, it returns TRUE or else it returns FALSE. b) Acquire(): This function will allow a thread to acquire the lock. The first thing this function does is to disable interrupts as acquiring a lock is an atomic operation. The function checks if the owner of the lock is trying to reobtain the lock. If yes, then it throws up an error and returns back without doing anything. Then the function checks if the value is FREE. If it is free, then the thread can acquire the lock. To do so, it will make itself the owner ie. put the value of owner equal to its thread pointer, and make the value BUSY. If the value is BUSY, the thread will add its thread pointer to the list waitQ of the lock. Then it removes itself from the ReadyQ and gives up the CPU by calling currentThread->Sleep(). Before returning, the function will enable the interrupts. c) Release(): This function will allow a thread to release the lock. A thread will release the lock once it is out of the critical region. The first thing this function wull do is to disable the interrupts as releasing a lock is an atomic operation. Then, using the function isHeldByCurrentThread(), we will check whether the lock is being released by the same thread which had acquired it. If this condition is false, then we print out an error message saying that "Thread trying to release the lock is not the same as the owner of the lock" and return without releasing the lock but after restoring interrupts. If the condition is true, then we check if waitQ is NULL or not. If waitQ is NULL, then we make value = FREE and set owner = NULL, restore interrupts ans return. If waitQ != NULL, then we remove the thread in front of the waitQ, make it the owner by setting the variable owner = the thread pointer of the thread in front of the waitQ and put it on the ReadyQ. We restore interrupts before returning. ii) Condition Variables: class is Condition. The variables associated with this class are - name: Name of the condition variable. - Lock: This is a void* which stores the pointer of the lock which was used to lock it. This variable is set the first time the condition variable is called, then it remains constant. - waitQ: This is a list which keeps a list of the waiting threads. It is FIFO in nature. All these variables are private. The constructor of a condition variable will take its name as the input. The three functions associated with this class are, a) Wait(lock *condLock): This function makes a thread wait on the condition. The first thing this function does is to disable interrupts as it is an atomic operation. If the invoking thread is the first waiter (lock is NULL), then we set Lock = condLock, else we check if condLock == Lock or not. If they are not equal, then we print out an error message saying "The condition variable should always be used with the same lock", restore interrupts and return. The thread now releases the lock, puts itself on the waitQ of the of the condition variable and puts itself to sleep. When the thread is woken up, before implementing anything, it should reacquire the lock. So the thread reacquires the lock, restores interrupts and returns. b) Signal(lock *condLock): This function is used to signal a waiting thread that the condition it was waiting on is now true. The first thing this function does is to disable interrupts as it is an atomic operation. First we check if the waitQ is NULL ie are there any waiters. If there are no waiters, we restore interrupts and return. If there are waiters, we verify that condLock == Lock or not. If the condLock is not the same as the Lock, then we print as error message "The waiting thread is being signalled with a wrong lock", restore interrups and return. If they are the same, then we will wake up the first waiter in the waitQ, ie we remove it from the waitQ and add it to the ReadyQ. Restore interrupts and return. c) Broadcast(lock *condLock): This function is used to signal all the waiting threads. While there are waiting threads, we wake up one waiting thread by signalling it using signal(condLock). 2. A) Global Variables: i) Monitor 1: This captures the cutomer - ordertaker interaction. Monitor Variables: a) numOfFreeOrderTakers: No. of free order takers. b) listOfFreeOrderTakers: It is a list of free order takers. It stores a pointer to the instance of the free ordertaker. c) customerWaitQ: Waiting Queue of the customers waiting for the ordertaker. This is the wait queue for the monitor. ii) Monitor 2: This captures the manager-cook-ordertaker interaction for already cooked food. Monitor variables: i) available3DollarBurger, available6DollarBurger, availableVeggieBurger, availableFries: These variables store the already cooked available food items. iii) Montitor 3: This captures the manager-cook-ordertaker interaction governing the food to be cooked. Monitor variables: i) ordered3DollarBurger, ordered6DollarBurger, orderedVeggieBurger, orderedFries: ii) cookedOrdered3DollarBurger, cookedOrdered6DollarBurger, cookedOrderedVeggieBurger, cookedOrderedFries. Monitor 4: This captures the manager-customer-ordertaker interaction. Monitor Variables: i) pendingOrderQ: A queue which stores the pending orders. ii)cutomerManagerWaitQ: The wait queue for the customers. B) Classes: i) CustomerOrderTaker: This captures the cutomer - ordertaker interaction. The variables are, - numOfFreeOrderTakers: No. of free order takers. - listOfFreeOrderTakers: It is a list of free order takers. It stores a pointer to the instance of the free ordertaker. - cond: The condition variable associated with the monitor. The customers sleep on the condition if there is any ordertaker is free. - lock: The lock which controls access to these shared variables. Functions: a) Constructor: It intializes the four ordertaker instances and adds them to the list of free order takers. ii) AvailableFoodItems: This class keeps track of the food items that have already been cooked and available to the order taker for bagging. The variables are, - availableFoodItems: This array stores the count for each type of food item. - lock: The lock which controls the access to the available food items. Functions: a) Constructor: It intializes the availableFoodItems to zero. iii) CookedFoodItems: This class is used to keep track of the ordered food items as well as the food items which have been cooked to order. The variables are, - orderedFood: This array stores the count for each type of food item on which order was placed by the OrderTaker. The OrderTaker increments this when some or all food items for a particular order cannot be fulfilled. - cookedOrderedFood: The Cook threads increment this when they have cooked the food item against which an order had been placed. The manager checks this variable to decide whether an order has been completed or not. When an ordertaker gets an order which is partially complete, it will transfer the available food from available food to cookedOrderedFood and increment orderedFood also to keep both of them equal. Since only the manager has access to cookedOrderedFood, this prevents stealing of the food. - lock: This lock controls the access to the cookedOrderedFood and orderedFood. Used to prevent race condition between the Manager, OrderTaker and Cook threads. Functions: a) Constructor: Initializes both the arrays to 0. iv) ManagerCustomer: This class tracks the interaction between the Customers and the Manager. The variables are, - pendingOrderQ: This list stores the pointers of all the pending orders. - lock: The lock controls access to pendingOrderQ. Functions: a) Constructor: Creates a new list and a lock. v) orderDescpr: Class is orderDescpr. The variables associated with this class are - burgerType: A value from the enum variable 'burgers' (3DollarBurger, 6DollarBurger, veggieBurger) - numBurgers: Number of burgers a customer orders. - fries: boolean variable showing TRUE if a customer orders fries. - numberFries: Number of fries a customer orders. - soda: boolean variable showing TRUE if a customer orders soda. - cutomerThread: This is a thread* pointing to the customer who has placed the order. Functions: a) Constructor: It takes the burgerType, numBurgers, fries, numberFries, soda and customerThread as its input and sets the class variables. vi) Customer: Class is Customer. The variables associated with this class are - name: Customer Name. - burgerType: A value from the enum variable 'burgers' (3DollarBurger, 6DollarBurger, veggieBurger). Denotes the type of burger ordered. - numBurgers: Number of burgers a customer orders. - fries: boolean variable showing TRUE if a customer orders fries. - numberFries: Number of fries a customer orders. - soda: boolean variable showing TRUE if a customer orders soda. - whichOrderTaker: Pointer to the instance of the ordertaker which is serving the customer. Functions: a) Constructor: There are two types of constructors. The first constructor picks a random burger and random number of burgers, picks fries and soda and their number randomly. The second one is used to give a deterministic order. This is basically for testing purpose. The user will have to pass the burger, fries and soda information as inputs. We account for the error conditions, for example when a customer orders a burger not on the menu. b) enterCarlsJr(): This is the first function called on any new instance of a customer. It creates a orderDescpr describing its order. It first acquires the lock on CustomerOrderTaker, checks numOfFreeOrderTakers. If no order taker is free then the customer puts himself on a waitQ. When a order taker is present, the customer decrements numOfFreeOrderTakers, gets the instance pointer to a free order taker from listOfFreeOrderTakers, relases the lock and calls the function OrderTaker::Order(orderDescpr*) passing the order description to the ordertaker. The customer then pays the order taker (basically a print statement saying "Paying for food"). Then the customer calls OrderTaker::makeAvailable to make the ordertaker available to other customers. If the order taker's function 'Order' had returned TRUE, the function returns. But if had returned FALSE, which means that the order was not present and it has to be bagged by the manager, the customer places himself on the manager's waitQ. When signalled by the manager, it means that his order has been bagged and the function exits. vii) OrderTaker: Class is OrderTaker. The only variables associated with this class is the OrderTaker's name. Functions: a) Order(orderDescpr*): This function will take an order from the customer. It takes the customer's order description as its input. It acquires a lock on the available food variables. It checks whether all the food to satisfy the order is present or not. If it is present, it will decrement the available food variables, release the lock and ask the customer to pay. If the food for the order is not present, the orderTaker releases the lock on available food variables, acquires the lock on order food variables. It increments the respective ordered food variables. It releases the lock on order food variables and acquires the lock on pendingOrderQ. It adds the present orderDescpr to the pendingOrderQ. It releases the lock, asks the customer to pay and returns. We also check for the error condition when a customer order a burger not on the menu. b) MakeAvailable:: This function makes an ordertaker available for other customers. It acquires the lock to access numOfFreeOrderTakers and listOfFreeOrderTakers, increment numOfFreeOrderTakers, adds itself to listOfFreeOrderTakers, signals a customer in the waitQ and returns. viii) Manager: Class is Manager. The variables associated with this class are - listOfCooks: An array which keeps an instance list of the cooks who are cooking. Function: a) Constructor: Initializes the lists. b) managerWork(): Manager always remains awake and keeps on executing. So there is an infinite while loop running. Inside the while loop, manager does the following things. First it checks the status of each food. Since the code for each of the food items is the same, we write it our for only one of the food items, lets say for fries. The manager first acquires a lock on the order food variables. If (orderedFries - cookedOrderFries) > 2, the manager creates a new cook, adds it to listOfCooksForFries and forks it. If (orderedFries != cookedOrderFries) then the manager sets a local variable isEqual = FALSE else isEqual = TRUE. If orderedFries = 0, then a local variable isZero = TRUE or else it is FALSE. The manager then releases the lock on order food variables. Then the manager acquires the lock on available food variables. If ((isEqual == TRUE) && (availableFries > 5)), then the manager will kill all the cooks in the list listOfCooksForFries (isEqual checks that there are no backlog of orders). If ((isZero == FALSE) && (availableFries < 2)), then the manager will create a new cook for fries, add it to listOfCooksForFries and fork it. (isZero ensures food is cooked to order.) After doing the above for all the food items, the manager will then enter a loop for bagging customers. The manager will acquire a lock on pendingOrderQ variable. The manager will traverse the pendingOrder queue and extracts 10 orders. Then the manager releases the lock. Then the manager will acquire a lock on the order food variables. Using these variables, the manager checks whether an order has been completed or not. If it has been completed, it decrements the corresponding food variables denoting he has bagged the food. It releases the lock on the order food variables and acquires the lock on pendingOrderQ back. Those orders which have been completed are removed from the queue and the rest are prepended back to the queue. Using the customer thread stored in the orderDescpr, he will signal it to wake it up. The above two pieces of code are within an infinite loop and hence keep on getting executed. ix) Cook: Class is Cook. The variables associated with this class are - typeOfFood: This is an instance of an enum variable 'foodType' (3DollarBurger, 6DollarBurger, veggieBurger and fries). It stores which food the cook is cooking. - toBeKilled: When the manager wants to kill the cook, it will set this variable. The cook keeps on checking this variable and kills itself when it is set true. Functions: a) Constructor(typeOfFood). b) cookFood(): There is an infinite while loop in which the following code runs. To simulate a cook cooking, we wait for a random number of iterations. After the food is cooked, the cook will acquire a lock on the order food variables and check if ordered[typeOfFood] == cookedOrderedFries[typeOfFood]. If they are unequal, it will increment cookedOrderedFries[typeOfFood] and release the lock. Else it releases the lock, acquires the lock on available food variables, then it will increment availableFoodItems[typeOfFood]. It then checks if isToKilled is set TRUE. If it is, then the cook will kill itself. Since the above code is inside an infinite while loop, cook will go on cooking food until manager kills him. IV. Implementation: 1. Files Modified: In threads directory: synch.cc, synch.h, TestSuite.cc, main.cc, Makefile. In code directory: Makefile.common Files Added: NIL. Data Structures added, and the file they were added to: NIL Data Structures modified, and the file they were added to: class Lock: -- in file threads/synch.h { lockStatus value; void *owner; List *waitQ; void Acquire(); void Release(); bool isHeldByCurrentThread(); } class Condition: -- in file threads/synch.h { void Wait(Lock *conditionLock); void Signal(Lock *conditionLock); void Broadcast(Lock *conditionLock); Lock *condLock; List *waitQ; } Functions added and in which file: Lock::isHeldByCurrentThread -- in file threads/synch.cc Functions modified and in which file: Lock::Lock(char* debugName) -- in file threads/synch.cc Lock::~Lock() -- in file threads/synch.cc void Lock::Acquire() -- in file threads/synch.cc void Lock::Release() -- in file threads/synch.cc Condition::Condition(char* debugName) -- in file threads/synch.cc Condition::~Condition() -- in file threads/synch.cc void Condition::Wait(Lock* conditionLock) -- in file threads/synch.cc void Condition::Signal(Lock* conditionLock) -- in file threads/synch.cc void Condition::Broadcast(Lock* conditionLock) -- in file threads/synch.cc void t1_t1() -- in file threads/TestSuite.cc int main(int argc, char **argv) -- in file threads/main.cc 2. Files Modified: In threads directory: main.cc, Makefile. In code directory: Makefile.common Files Added: In threads directory: carlsJr.cc, carlsJr.h, carlsJrTestSuite.cc. Data Structures added, and the file they were added to: Added to file threads/carlsJr.h enum burger {Dollar3Burger, Dollar6Burger, VeggieBurger}; enum foodType {ThreeDollarBurger, SixDollarBurger, VegBurger, Fries}; class CustomerOrderTaker { int numOfFreeOrderTakers; List *listOfFreeOrderTakers; Condition *cond; Lock *lock; CustomerOrderTaker(); ~CustomerOrderTaker(); }; class AvailableFoodItems { int availableFood[4]; Lock *lock; AvailableFoodItems(); ~AvailableFoodItems(); }; class CookedFoodItems { int orderedFood[4]; int cookedOrderedFood[4]; Lock *lock; CookedFoodItems(); ~CookedFoodItems(); }; class ManagerCustomer { List *pendingOrderQ; Lock *lock; ManagerCustomer(); ~ManagerCustomer(); }; class OrderDescpr { burger burgerType; int numBurgers; bool fries; int numberFries; bool soda; Thread *customerThread; OrderDescpr(burger whichBurger, int numberOfBurgers, bool fry,int numFry, bool sod, Thread *thread); ~OrderDescpr(); }; class OrderTaker { char *name; OrderTaker(char *debugName); ~OrderTaker(); bool order(OrderDescpr* customerOrder); void makeAvailable(); }; class Customer { char *name; burger burgerType; int numBurgers; bool fries; int numberFries; bool soda; OrderTaker *whichOrderTaker; Customer(char *debugName); Customer(char *debugName, burger whichBurger, int numberOfBurgers, bool fry, int numFry, bool sod); ~Customer(); void enterCarlsJr(); }; class Manager { List *listOfCooks[4]; Manager(); ~Manager(); void managerWork(); }; class Cook { foodType typeOfFood; bool toBeKilled; Cook(foodType food); ~Cook(); void cookFood(); }; Data Structures modified, and the file they were added to: NIL Functions added and in which file: In file carlsJr.cc: void Initialize(); void createManager(); CustomerOrderTaker::CustomerOrderTaker(); CustomerOrderTaker::~CustomerOrderTaker(); AvailableFoodItems::AvailableFoodItems(); AvailableFoodItems::~AvailableFoodItems(); CookedFoodItems::CookedFoodItems(); CookedFoodItems::~CookedFoodItems(); ManagerCustomer::ManagerCustomer(); ManagerCustomer::~ManagerCustomer(); OrderDescpr::OrderDescpr(burger whichBurger, int numberOfBurgers, bool fry,int numFry, bool sod, Thread *thread); OrderDescpr::~OrderDescpr(); OrderTaker::OrderTaker(char *debugName); OrderTaker::~OrderTaker(); bool OrderTaker::order(OrderDescpr* customerOrder); void OrderTaker::makeAvailable(); Customer::Customer(char *debugName); Customer::Customer(char *debugName, burger whichBurger, int numberOfBurgers, bool fry, int numFry, bool sod); Customer::~Customer(); void Customer::enterCarlsJr(); void createNewCook(int typeOfFood) Manager::Manager(); Manager::~Manager(); void Manager::managerWork(); Cook::Cook(foodType food); Cook::~Cook(); void Cook::cookFood(); In file threads/CarlsJrTestSuite.cc: void t1(int i); void t2(int i); void t3(int i); void t4(int i); void t5(int i); void CarlsTest(); Functions modified and in which file: int main(int argc, char **argv) -- in file threads/main.cc V. Testing: 1. A) How to Test: We run the test cases in the test suite by typing in the command line, nachos -rs -T B) Test Output: a) The first test shows that a thread trying to release a lock it does not hold gives an error. A error message saying "Thread trying to release the lock is not the same as the owner of the lock" is printed. Also the test case tests that if the owner of the lock tries to acquire it again, so a error saying "Owner of the lock trying to own it again" is printed. b) The second test shows that a signal with no waiting threads is ignored. c) The third test shows that a signal wakes up only one thread. d) The fourth test will test that broadcast wakes up all waiting threads. e) The fifth test shows that signalling a thread waiting under one lock while holding another throws up an error. A error message saying "The waiting thread is being signalled with a wrong lock" is printed. 2. A) How to Test: nachos -rs - P2 B) Test Output: a) In the first test case, we sent in 20 customer ordering the same item. This is to test that in case of heavy demand for one item, the manager is able to manage cooks so as to serve each one of them. The output will show that all the customers get served. b) In the second test case, We send in 20 customers ordering burgers, fries and soda randomly. This is to test that when the order is available, ordertaker bags the food and when it is not the manager bags the food. To test this, we send in 5 customers intially, then wait for some time and then send in 15 more. The output will show that all the customers get served, though for some of them, the manager bags the food and some of them get food from the ordertaker immediately. c) In the third test case, we send in a customer ordering a burger not on the menu. An error saying that the burger ordered by the customer is not on the menu appears. d) In the fourth test case, we send in a customer which orders FRIES = FALSE but sends in number of fries != 0. A warning is printed telling the user that the customer has not ordered fries, yet the number of fries is non zero. The ordertaker will bag the food assuming that the customer has not ordered a fry. e) In the fifth test case, we send in a customer which orders just a soda. The customer will get its food immediately from the ordertaker and leave immediately. VI. Discussion: 1. Experiment expectation: The locks and the condition variables have been properly implemented. All the test cases should pass, for negative test cases proper error should be printed and the code should not crash. Experiment result: All the test cases pass. We ran the test case for 20 values of rs and all the test cases passed for every value of rs. Appropriate error is printed for negative test cases. Explanation: Both the expectations and the results match. Hence both locks and condition variables have been properly implemented. 2. Experiment expectation: All the test cases should pass. The customer should always get served. When an order is present, the ordertaker bags the food, else the manager should bag the food. The cooks should get killed after 5 units of the food item being cooked by the cook are extra. If no ordertaker is free, then the customer should go to sleep and be woken up by the ordertaker. If a customer's order cannot be processed imeediately, then it should go to sleep and be woken up by the manager only when its order is ready. Experiment result: All test cases give the desired output. All the customers get served. Customer - ordertaker interaction and customer - manager interaction is proper. The cooks get killed after 5 units of the food item being cooked by the cook are extra. Explanation: Carls Junior has been properly simulated as per the guidelines. VII. Miscellaneous: 1. NIL 2. a) Ours is a 24 hr. restaurant. After the first test case is implemented, the cooks cooking the particular burger and fries get killed only after they have cooked 5 extra food items. So, in the second test case, the customer ordering the burger and the fries get served immediately by the ordertaker which is one of the things we want to test. In a nutshell, when we go from first to second and second to third test case and so on, the manager is not killed and available food items inventory is not initialized again to zero. After all the test cases have been run, the grader will have to stop the program by using crtl-C. b) We are not printing the statement "cook killed" when a cook is killed because of the numerous print statements. We have commented out the print statement. If you want to check that cooks are indeed being killed, just uncomment the print statement in the file threads/carlsJr.cc, line 240. c) We have changed the files thread/Makefile and Makefile.common also as we have added new files. Please take care that when you compile our code, you do it with our Makefile and Makefile.common. We will be submitting our Makefile and Makefile.common with our code.