Homework 2

INSTRUCTIONS

Out: September 9, 2005.
Due: In 3112 SC at 6 pm September 23 (Friday), 2005. We will accept only solutions that are typed-up and printed out (figures and tables may be drawn by hand). No written solutions or online handins.
Resources you are allowed to use: Unless otherwise mentioned, the only resources you can use are the lectures slides, your notes, the Tanenbaum textbook, and any other textbook on OS's, architecture, data structures or previous CS material. You cannot refer to any online resources (unless otherwise mentioned). You cannot use ready-made solutions under any circumstances..
Relevant Lectures: 5-10.
Points: Unless otherwise mentioned, a problem is worth 5 points. The HW is worth a total of 40 points. If a question has multiple parts, the 5 points are split equally among the parts.
Warning: Homeworks are individual efforts. Although you are allowed to discuss HWs with your fellow students, you are expected to solve them yourself and type up the solution yourself. For detailed information on penalties, cheating and playing it safe, see this page.

UPDATES

Updates posted 9/11 for problems 5-8 (see italicized phrases in those problems).

PROBLEMS

1. Problem 2.38 from text.
2. Problem 2.40 from text. For (a), assume a quantum length of 100 ms.
3. Explain the differences in degree to which each of the following scheduling algorithms discriminate in favor of short processes: (1) FCFS (2) RR (3) Priority (4) Mutlilevel Feedback Queues.
4. Problem 2.11 from text.
5. (The Cigarette Smoker's Problem) A room has three smoker processes and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. The agent has an infinite supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a starvation-free program to synchronize the agent and the smokers. The only synchronization primitives you can use are semaphores and/or mutex variables. Clarification: You DON'T need to make your program deadlock free.
6. Problem 2.50 from text. Extra credit: Under what circumstances is your solution starvation-free? Deadlock-free?
7. Consider a system consisting of processes P1, P2, ... Pn, each of which has a unique priority number. Write a starvation-free monitor that allocates three identical line printers to these processes, using the priority numbers for deciding the order of allocation. Extra credit: if you show your program is deadlock-free.
8. (The Barbershop 3 Problem) In class, we saw a solution to the "Sleeping Barber Problem". Instead, now consider the "Barbershop 3 Problem" - the barbershop has three barbers -- Calvin, Terri, and Eddie. In addition, the shop has N waiting chairs. If a barber finds that there are no more customers to be served and no customers in the waiting chairs, the barber goes to sleep. If a customer enters the shop and all barbers are busy, as well as all waiting chairs are occupied, the customer leaves the shop.  If all barbers are busy, but there are available waiting chairs, the customer sits in one of the free chairs. If one or more barber is asleep, the customer wakes up one barber, but always prefers Calvin if possible (he's the best), then Terri (she's always angry), and only at last Eddie (he talks way too much). When a barber finishes a customer, if there are other customers waiting, the barber picks a customer to service (no customer preferences here!). Write a program for the above "Barbershop 3 Problem". The only synchronization primitives you can use are semaphores and/or mutex variables. Extra credit: if you show your program is starvation-free and deadlock-free.

Updated: Sep. 11, 2005. (c) Indranil Gupta.