edited by
11,951 views
45 votes
45 votes
  1. Four jobs are waiting to be run. Their expected run times are $6, 3, 5$ and $x.$ In what order should they be run to minimize the average response time?
  2. Write a concurrent program using $\text{par begin-par end}$ to represent the precedence graph shown below.

edited by

4 Answers

Best answer
38 votes
38 votes
  1. Here, all we need to do for minimizing response time is to run jobs in increasing order of burst time.
  2. Schedule shorter jobs first, which will decrease the waiting time of longer jobs, and consequently average waiting time and average response time decreases.


  3. $6, 3, 5$ and $x.$

    If $X < 3 < 5 < $6,  then order should be $x,3,5,6$

    If $3 < 5 < 6 < x$, then order is $3,5,6,x$.

    If $3 < x < 5 < 6$, then order is $3,x,5,6.$  If $5 < x < 6$, then order is $3,5,x,6.$

Idea is that if you have $S_1 \to S_2$ then you create new semaphore a, assume that initial value of all semaphores is $0$. Then $S_2$ thread will invoke $P(a)$ & will get blocked. When $S_1$ get executed, after that it'll do $V(a)$ which will enable $S_2$ to run. Do like this for all edges in graph.
Let me write program for it.

Begin
Semaphores $a,b,c,d,e,f,g$
ParBegin $ S_1 V(a) V(b) V(c) V(d)$ Parend
ParBegin $P(a) S_2 V( e)$ Parend
ParBegin $P(b) S_3 V(f)$ Parend
ParBegin $P( c) P( e) S_4 V(g)$ Parend
ParBegin $P(d) P(f) P(g) S_5$ Parend
End

IF you reverse engineer this program you can get how this diagram came.

Parbegin Parend – Parallel execution

$P-$ Down, $V-$ Up

edited by
23 votes
23 votes

Part A.

Given:

$4$ processes whose Burst Time are $6,3,5,x$ respectively.

We have to find the order to execute them so that we could get minimal average Response time.

 

Solution :-

 

$Response\ time$ is defined as the time taken from submission of request to the first response by the CPU.

So we can run them in $Round\ Robin$ manner with $Time\ Quantum =1$ unit to get the minimal average response time.

The minimal average response time would be $ \frac {0+1+2+3}{4} = 1.5$ units

 

But by doing this we are not able to get any specific order of execution for the given set of processes. ($\because$ whatever be the value of $x$ and whatever be the sequence of execution, the average response time will not change.)

So the question asked will not make any sense.

Hence we need to choose an algo so that the order depends on the value of $x$.

The optimal choice among non-premptive algo would be $Shortest\ Job\ First$ since it gives minimal waiting time for all processes , thus also minimizing the average response time.

The criteria for selecting a process to execute in case of shortest job first is $Burst\ time.$

The process with minimal burst time would be executed first.

So for $6,3,5\ and\ x.$

If $x<3<5<6$,  then order should be $x,3,5,6$

If $3<5<6<x$, then order is $3,5,6,x.$

If $3<x<5<6$, then order is $3,x,5,6.$ 

If $5<x<6$, then order is $3,5,x,6$.


Part B.

In a concurrent program the statements written within the $Begin-End$ block would execute sequentially/serially and the statements written within the $ParBegin-ParEnd$ block would execute concurrently/parallely.

Now if we take a look at the diagram then the edge $S_1 \rightarrow S_4$ is redundant as it is already covered using $S_1 \rightarrow S_2 \rightarrow S_4$

So the program would be

Begin
      S1
      ParBegin
               Begin
                     S2
                     S4
               End
               S3
      ParEnd               
      S5
End

 

edited by
4 votes
4 votes
24) a. It will depends on value of x.. U can decide others 3 process sequence I.e 3,5,6 Now x can come anywhere depending on its value.. Remember we shld gve it in increasing order to minimize response time
–3 votes
–3 votes
The average response time depends upon the value of x

if x < 3

then the order is x,3,5,6

if the value of x >3 and x < 5

the the order is 3,x,5,6

if the value of x > 5 and x < 6

then the order is 3,5,x,6,

if the order > 6

then the order is

3,5,6,x

 

For the second question it will be S1---S2---S3---S4---S5  OR S1---S3----S2----S4----S5

Related questions

47 votes
47 votes
5 answers
1
26 votes
26 votes
3 answers
4
Kathleen asked Sep 26, 2014
5,178 views
Free disk space can be used to keep track of using a free list or a bit map. Disk addresses require $d$ bits. For a disk with $B$ blocks, $F$ of which are free, state the...