Homework 3
Assignment due:
Problems 1, 2, 3: Hand in at the start of class (9:30 am) on Tuesday, April 15th, or turnin electronically by the same time. Turnin typed (not hand-written) answers to the non-programming problems. If using electronic turnin, provide a pdf file named answers.pdf or answers.txt. Use 422assign3 as the name of the assignment for electronic turnin.
Problems 1-3 are worth 36 points (12 points each).
Program: Submit the program electronically by 8:00 pm on Friday, April 18th. See the end of this assignment for information on electronic turnin.
The programming exercise is worth 64 points.
A reminder: Homework assignments are individual efforts. The two projects can be done in teams of two, not the homework. You may discuss the meanings of questions with classmates, but the answers and programs you turn in are to be yours alone. For the exercises from the book, explain your answers clearly and succinctly.
Problem 1: Exercise 5.8, page 256-257
The Savings Account Problem. A savings account is shared by several people (processes). Each person may deposit or withdraw funds from the account. The current balance in the account is the sum of all deposits to date minus the sum of all withdrawals to date. The balance must never become negative. A deposit never has to delay (except for mutual exclusion), but a withdrawal has to wait until there are sufficient funds.
a.) I asked this as a question on Test #3 last spring (see Sample Test #3). You are to do parts b.) and c.)
b.) Write a monitor that services withdrawals FCFS. For example, suppose the current balance is $200, and one customer is waiting to withdraw $300. If another customer arrives, he must wait, even if he wants to withdraw at most $200. Assume there is a magic function amount(cv) that returns the value of the amount parameter of the first process delayed on cv. Use the Signal and Continue discipline.
c.) Suppose the magic amount function does not exist. Modify your answer to b.) to simulate it in your solution.
Problem 2: Exercise 5.10, page 257
Atomic Broadcast. Assume one producer process and n consumer processes share a bounded buffer having b slots. The producer deposits messages in the buffer; consumers fetch them. Every message deposited by the producer is to be received by all n consumers. Furthermore, each consumer is to receive the messages in the order they were deposited. However, consumers can receive messages at different times. For example, one consumer could receive up to b more messages than another if the second consumer is slow.
Develop a monitor that implements this kind of communication. Use the Signal and Continue discipline.
Problem 3: Exercise 7.7, page 354
Develop an implementation of a time-server process. The server provides two operations that can be called by client processes: one to get the time of day and one to delay for a specified interval. In addition, the time server receives periodic “tick” messages from a clock interrupt handler. Also show the client interface to the time server for the time of day and delay operations.