1. A counting semaphore can have any arbitrary integral value. A process using such semaphore does not block until a down() invoked by the process on the semaphore makes the value negative. A negative value of the counting semaphore indicates that many processes blocked on the semaphore. An up() on the semaphore will wakeup a blocked process if the value is still negative. Describe how such a counting semaphore can be implemented using only binary semaphores and ordinary machine instructions. You may also use simple integer variables and list data structure.

2. Measurements of a certain system have shown that the average process runs for a Time T before blocking on I/O. A context-switch requires a time S, which is pure overhead (waste of CPU time). For a round-robin scheduling with quantum time Q, give a formula for the CPU efficiency, when Q >= T. The formula is an expression that involves some or all of the time values T, S, and Q. Explain how you derived your expression

3. Consider a preemptive priority scheduling algorithm based on dynamically changing priorities. Greater priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate W; when it is running, its priority changes at a rate R. All processes are given a priority of 0 when they enter the ready queue. Explain how the processes are scheduled (that is, how they are ordered) when 0 < W < R.