4003-440 and 4003-713 Operating Systems
Homework #6
Due January 29, 2007
Name: __David Oguns______Section: __02______
1. Servers can be designed to limit the number of open connections. Forexample, a server may wish to have only N socket connections at anypoint in time. As soon as N connections are made, the server will notaccept another incoming connection until an existing connection is released.Explain how semaphores can be used by a server to limit thenumber of concurrent connections.
A semaphore could be created and initialized to N, the number of simultaneous connections supported. Before accepting a connection the server would wait on the semaphore and after the connection is terminated, it would signal on the semaphore.
2.Show that, if the wait() and signal() semaphore operations are notexecuted atomically, then mutual exclusion may be violated.
If P1 and P2 are two processes that need to use semaphore S which is initialized to 1, they would first try to wait on S. The implementation of wait has to test the value of S, and then decrement the value of S if S is greater than 0 before returning and allowing access to the semaphore. If two processes are able to call wait at the same time, both could test the value of S before decrementing and both will decrement S making it an invalid value, and both being able to execute their critical section at the same time.
3. The Sleeping-Barber Problem.Abarbershop consists of awaiting roomwith n chairs and a barber room with one barber chair. If there are nocustomers to be served, the barber goes to sleep. If a customer entersthe barbershop and all chairs are occupied, then the customer leaves theshop. If the barber is busy but chairs are available, then the customer sitsin one of the free chairs. If the barber is asleep, the customer wakes upthe barber.Consider this as an instance of the Producer-Consumer problem. Identify the producer(s), the consumer(s) and the contents and maximum size of the bounded queue. Write the pseudocode to coordinate the barber and the customers.
The producers of this problem are the customers. They produce work for the consumer, the barber. The contents of the queue for the consumer are the consumers sitting in the n chairs. The maximum size of the queue is n.
PSUEDOCODE: Initialize S to n.
Producer:
while(true)//keep the consumers coming
{
wait(S);
//get hair cut
}
Consumer:
while(true)
{
if(S < n)
{
//do haircut
signal(S);
}
}
4. Discuss the tradeoff between fairness and throughput of operations in the readers-writers problem. Propose a method for solving the Readers-Writersproblem without causing starvation.
In the readers-writers problem, the writer(s) may be starved if the readers are constantly reading from the resource. They will keep the semaphore tied up and the writer will never have an opportunity to write. This is unfair for the writer but optimal for reader throughput since any number of readers can read at the same time without any negative effects. To be more fair to the writer(s), it should create a queue when they need to read and wait for only the currently reading readers to complete and the semaphore to be available. Any new readers that wish to read from the semaphore are placed behind the write in the queue. After the readers are complete, the writer takes its turn with the semaphore. After it is done, any and all of the waiting readers can do their work.
This solution also solves a potential coherency problem with synchronized access to data where a read operation may come after a write and thus reads old data.
5. Write a the pseudocode for a monitor that implements an alarm clock that enables a calling programto delay itself for a specified number of time units (ticks). You mayassume the existence of a real hardware clock that invokes a procedure tick in your monitor at regular intervals.
Monitor AlarmClock
{
condition self;
int delay;
void pause(int time)
{
delay = time;
self.wait();
}
void tick(int delta)//assuming delta is the amount of time that has passed
{
delay -= delta;
if(delay <= 0)
self.signal();
}
}