CPSC 457 - Principles of Operating Systems - Assignment 3

This assignment is to familierize you working with threads, specifically pthreads. You will use threads to construct a simple simulation of ordering at a coffee shop.

The Ordering Simulation

Customers arrive at the shop and enter a queue to place an order for drinks. Drink orders can be quick, medium or slow and customers may order one or more drinks at a time. Once the customer has given their order to the barista, they must wait for their order to be completed. When an order is received it must be recorded in the cash register and then it must be produced. When producing a drink order the barista must wait for a set period of time (to simulate actual work happening). Once an order has been completed it can be given to the customer.

The Coffee Shop Simulation

You have been provided with a skeleton that implements two threads to manage customers, the customer thread and the cleanup thread. The customer thread creates new customers at random intervals and creates orders for those customers. The clean up thread receives the orders once the baristas have produced them. There are two buffers, one for baristas to take orders from customers and one for customers to take prodcuts from the baristas. The skeleton produces customers at roughly a rate of 1 every 500ms and drinks take 200ms, 400ms or 800ms to produce.

You will implement the barista threads, as well as the necessary concurrency protection to ensure that the buffers are updated correctly. pthreads implements all of the tools you will need for concurrency protection, you will just have to use them.

Baristas are created when the shop is created and receive orders, "take cash" and make drinks. When taking orders and making drinks baristas can either work in the train model where a barista takes an order and then makes the drinks for that order or a space model where one barista takes orders and gives them to another barista to produce. When implementing the space model you will need to implement a thrid buffer.

Notes

In responce to several e-mails I have received.

• In the skeleton The cash variable is intended to simulate a cash register, which should be a protected variable that only one barista can update at a time. It's actual value is arbitrary, in my solution I incremented it by the total time of the order.
• In the space model baristas taking orders from customers should store those orders in another buffer for baristas filling orders to take from.

Evaluation

Simulations are usually used to allow us to expand our knowledge about the world. Here we are interestested in seeing some results based on our coffee shop simulations. You will probably want to modify your program to more easily modify simulations based on the conditions we would like to create.

1. Time to Completion - with 4 baristas determine how long your simulation takes to complete for a number of customers ranging from 5 to five hunderd (increasing by 5 for each experiment). Graph the results, compairing number of customers to completion time for both the space model and the train model?
2. Space Model vs Train Model - For 100 customers, how long does it take baristas to server all the orders? Run one set of experiments using the space model and one using the train model. Run your experiments for a variety of number of baristas from 2 to 10. Graph your results, compairing model and barista number to completion time and discuss which model is better (if any difference is apperent).
3. Customers to the breaking point - For 4 baristas, how quickly over a 10 second period do customers have to enter for the simulation to break down and the entry queue to be filled faster than the baristas can fufill orders? Graph the result, comparing number of customer/10seconds to completion time, increasing the number of customers per 10 seconds by 5 until the completion time is no longer reasonable. How many customers can a barista serve (how much does adding a barista improve the time to failure?)

   Note: I realize this one is confusing. What I would like to know is what is the rate of cusomters (# of customers arrived over a period of time) at which your baristas can no longer empty the buffer faster than it will fill. This should be notable in your completion times by a spike as increasing numbers of customers have to wait for longer and longer times.

   You can adjust the rate at which customers arive by changing the function in the customer thread that generates new customers at a specific point in time.

4. A question of interest - Ask and answer a question of interest that can be explored by changing the conditions of the simulation (number of customers, number of baristas, etc.) You can use the existing parts of the simulation or add new parts. Graph the results of your expriment and discuss. If you'd like a simple case, what happens if you add a second type of order (say food, that takes significantly longer to prepare) to your simulation?

Remembe,r that because your simulation involves randomness a single sample is not sufficient. Take several samples for each condition and graph the averages for each. A script (like a bash script) may help make running your experiments easier.

Functional Requirements

Your assignment must:

• Implement baristas working in the space model or the train model.
• Implement producer-consumer protection for all buffers.
• Include a document discussing the 4 simulation evaluation questions, including graphs and textual discussion.

Non-Functional Requirements

Your assignment must:

• Be written in C and use pthreads.
• Compile without warnings (using gcc's -Wall option)
• Be well-commented.
• Must cite all out-of-class resources.
• Include a usage statement
• Include a makefile which compiles your assignment.
• Include a README explaining the assumptions you've made, how to compile and run your program and any other notes we should know.
• Be your personal, original work.

Question 1 - Is the simulation good enough?

Simulations allow us to experiment with real-life concepts by simplifying some aspects of real-life and by changing other aspects. Does this simulation do a good job of simulation a coffee shop? Suggest some modifications to the simulation and what you would achieve by implementing them.

Question 2 - Monitors

Monitors are a high-level synchronization tool that must have language support to be implemented. Discuss why this is and discuss why more primitive synchronization tools (such as mutexes and semaphores) are still used in higher level languages.

Question 3 - Deadlocks

Most modern operating systems do nothing to prevent deadlocks. Why? What assumptions do the developers make that allow them to ignore the deadlock problem? Is it a good idea to ignore deadlocks?

Question 4 - Deadlock Detection

With the following table determine if the system is in a safe state or not and explain why? The available array is <3, 2, 2>.

Question 5 - Swapping vs Paging

Discuss the benefits and draw backs of swapping and paging for memory management. Paging is almost universally used, why?

Question 6 - Disk Scheduling

Consider a disk with 2500 cylinders number 0 - 2499. The drive is currently serving a request at cylinder 210 and heading towards cylinder 2500. For a pending queue (in FIFO order) caculate the total distance (in cylinders) that the disk arm must move to satisfy all requests for each disk-scheduling algorithm.Queue: 119, 554, 1198, 2101, 2000, 1618, 1619

• FCFS
• SSTF
• SCAN
• LOOK
• C-SCAN
• C-LOOK

Question 7 - RAID and disk failure

Increasing the number of disks attached to the system increases your chance of disk failure. Why is this so? Do all RAID configurations offer a benefit worth the increased risk? If so, which ones and why?

Question 8 - Directory Structure

Most directory systems go out of their way to avoid cycles in the graph (or tree) or directories. Why? If you did allow cycles how could you ensure that a file is properly deleted once there are no references to it?

Question 9 - KibiBytes vs KiloBytes

What is the difference between a KibiByte and KiloByte (both mathimatically and semanticaly). Why has the distinction been introduced? Is it a good solution?

Question 10 - Time

*nix systems track the time in seconds since Midnight, January 1, 1970. How long is it possible for these systems to track the time using a) a signed 32 bit integer, b) an unsigned 32bit integer or c) a 64bit integer? What date (year and month) will each of these wrap around to cause a "y2k" problem?