1. A counting semaphore can have any arbitrary integral value. A process using s
ID: 3681369 • Letter: 1
Question
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.
Explanation / Answer
Q1)
the code will be:
Struct Semaphore
{
Int value;
Queue type l; -----(set of processes blocked)
}
Down(Semaphore S)
{
s.value= svalue-1;
if(S.value<0)
{
Put process (PCB) in l,
Sleep();
}
Else
Return;
}
Up(Semaphore S)
{
S.value= S.value+1;
If(S.value<=0)
{
Select a process from l
Wake up();
}
}
instruction general code:
2) There are 4 cases for efficiency for round robin scheduling.
(a) Q=infinity (b) Q>T (c) S<Q<T (d) Q=S (e) Q nearly 0
3)
Priority Scheduling always selects the process(es) with the highest priority currently ready to run. If there is more than one process having the currently highest priority, you need a second scheduling algorithm to choose among these processes. Non-preemptive Priority Scheduling only selects a new process to run if the running process finished its work or yields (voluntarily) to the scheduler.
Preemptive Priority Scheduling is the same algorithm but if a new process having a higher priority than the currently running process arrives, it gets selected immediately. The new process has not to wait until the currently running process finishes or yields.
For example:
Arrival Time Burst Time Priority
P1 0 5 3
P2 2 6 1
P3 3 3 2
The gantt chart would look this this:
| P1 | P3 | P2 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.