CS 5/7343 Operating Systems and System Software
Programming Homework 2
Due Date: 10/19 (Mon) 11:59pm, no extension
This homework requires you to work with POSIX semaphores. For Linux, the support for POSIX mutex_locks and semaphore extension are described in section 7.3 in the textbook (10th edition). The following link contains a “toy” example that you can use to get a sense of how unnamed semaphore works. https://www.geeksforgeeks.org/use-posix-semaphores-c/
There is a restaurant named “ROOTS”. The restaurant serves 10 different dishes. For simplicity’s sake, we will use numbers 0-9 to denote them. The restaurant has a set of tables. Customers will come in, order dishes, eat and leave. However, the restaurant have a strange way of serving its customers.
The chef will produce whatever item he wants to produce and put it on a (FIFO) queue to be served. The customers at each table can only see what is the first item on the queue, and if the item is what they want, they will go and try grab it. In case more than one table want that item, the first one to get it will get it. Notice that it may be the case where nobody wants the dish that is currently being served. To avoid this from blocking the whole restaurant’s operation, if the front plate is not picked up by all the tables, the dish will be thrown away.
Once the customers at a table obtained what they need, they will pay the restaurant a tip, which is to be stored at the tip box.
Your goal for this project is to write a program to simulate the restaurant, using the main process to simulate the chef, and spawning threads to simulate each table.
Your program should contain a set of global variables that need to be shared among the threads (or between the main process and the thread). The following global variables should be included:
Foodqueue: the queue that store the food being produced. It should be represented by a FIFO queue of integer, and the queue should have a fixed length. What data structure you will use to implement the queue is up to you.
IsOpen: a boolean variable. If it is set to false, no table can grab any food from the Foodqueue, even if there is something on it. If it is set to true, than any table can go grab the food from the Foodqueue. It should be initialized to False. Notice that the main program can still accept new customers even if IsOpen is set to False.
TipBox: an integer storing the total amount of tips that is collected. It should be initialized to 0.
There may be other global variables that need to be defined.
Your main program should read in the name of an input file (via the command line argc/argv function). The file has the following format:
The first line of the file contains two numbers. The first number denote the number of tables. The second denote the capacity of the food queue.
Each subsequent line starts with a single character:
o A line start with ‘C’ denote a new customer. Following ‘C’ will be a blank space and then an integer, denoting the customer number (this is only needed for output). After that there will be another number, denoting the number of dishes that he/she wants. The rest of the line will list the dishes that he/she wants. Notice that the customer may offer the same dish multiple times.
When a new customer arrives, you should sit him/her to one of the available tables. If there is no table available, the customer will leave.
Notice that after you sit a customer, you should produce one dish and put it on the queue.
o A line start with ‘P’ denote that the chef is to produce that many number of dishes before the next customer arrives. Following ‘P’ will be a blank space and then an integer, denoting the number of dishes to be produced.
o A line start with ‘O’ toggle the value of IsOpen (from True to False and vice versa)
Your program should read in the first line of the file and then initialize the queue and create the tables. Each table should be a separate thread. You should assign an ID to each table (you can use the thread ID produced by the pthread_create() function if you want, or you can assign a number on your own). Notice that the ID is associated to the thread, not to individual customers.
Afterwards you should go into a loop, reading each line of the file and perform the task required for that command. That includes: checking whether there is an empty table; if so, assign the customer to that table; producing dishes and put them into the queue; check if the queue is full, and if so check if the first dish need to be discarded; signal the whole program is finishing and waiting for all the threads to be joined. (There may be other functions not specified here).
When you reach the end of the file, you should allow all the current customer to finish there dishes and leave, wait for all threads to finish and exit the program.
Whenever a dish is to be produced, a random dish is to be produced. You can use the random function srand48() and lrand48() to produce the dish. A small sample program to illustrate the function will be provided. (If your system do not support srand48() and lrand(48), then use srand() and rand() instead).
Each thread should simulate a table. Once the thread starts, it should wait for the parent process to assign a customer to it. Once the customer is assign, then the thread should monitor the queue of dishes and grab the dish when available. It should also check IsOpen variable to check whether the customer can try to grab the dish from the queue.
Every time a thread get hold of a dish, it should sleep for a random amount between 1-5,000 nanoseconds, using the function nanosleep(). (Sample code is provided). Once all the food of the customer is collected, the thread should then put a random amount of dollars (from 1 – 10) into the tipbox and the customer will leave.
Notice that a customer is finished does not mean the thread should be terminate. Once a customer finishes, the thread should ready itself to accept the next customer. The thread should only terminate when it receive a notice that the whole program is finishing. Even them, it should serve any remaining customer it has first.
Both the main process and the thread need to output certain info:
Whenever a dish is produced and put onto the queue, the main process should print the following line: “Dish produced”
Whenever the process read a line from the file, it should print the first character and (if available) the first number.
When a customer is assigned to a table, the thread should print “ assigned to ”
If a customer is dropped, the main process should print “ dropped”
When a customer picked up a dish, the correspond thread should print “ picked up ”
When a customer finishes and leave, the thread should print “ leaving ”
At the end of the program, the main process should print “total tip collected : ”
You can use either mutex_lock or semaphore to ensure correctness of the program. Notice that you should only ensure f1(), f2(), f3() be run atomically, you should allow as much of your code in the thread to run concurrently (not violating correctness, of course).
What to hand in
You should zip all your source code (including the main program) in a zip file. Please only include source code (e.g. .c, .h file).
Such a cheap price for your free time and healthy sleep
All online transactions are done using all major Credit Cards or Electronic Check through PayPal. These are safe, secure, and efficient online payment methods.