The Gateway to Computer Science Excellence
+29 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.

in Operating System by Veteran (52.2k points)
edited by | 3.3k views
there is difference between par begin par end and co begin end???

4 Answers

+26 votes
Best answer
  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.


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

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

Parbegin Parend – Parallel execution

$P-$ Down, $V-$ Up

by Boss (41.9k points) 1 flag:
✌ Edit necessary (rohith1001 “Parbegin-Parend has been interchanged with Begin-End”)

edited by
co and par are same ?? what is meaning of co
co - concurrent

par-  parallel

I think they are same.
ok... par begin p(g)p(f)p(d) s5 rt ?
okay now ?

I think u have misplaced/interchanged the use of Parbegin & begin here..Becoz

ParBegin  S1 V(a) V(b) V(c) V(d) Parend        


ParBegin P(a) S2 V( e) Parend   

  can execute parallely .But u hv placed them inside begin meaning they execute one by one..

As it is not mentioned that algoritm must be non preemptive so Round Robin with TQ = 1 is the best approach here.
@Akash , What is the use of c and d semaphore here? I think you have used them because of the edges in the precedence graph s1 to s4 and s1 to s5. But are not these extra (I mean unnecessary)?
@ Akash Kanase, @Bikram Ballav Sir, @Hemant Parihar, I feel Himanshu 1 says it correct. Could you please crosscheck it once.

I too think the same.

Is this code right?

Please tell book or online source for learning and practising precedence graph questions

I agree with @Himanshu1.Parbegin-Parend is interchanged with Begin-End.

The correct program is as shown below:

Semaphores a,b,c,d,e,f,g all initialized to 0;
    Begin {S1; V(a); V(b); V(c); V(d);} End
    Begin {P(a); S2; V(e);} End
    Begin {P(b); S3; V(f);} End
    Begin {P(c); P(e); S4; V(g);} End
    Begin {P(d); P(f); P(g); S5;} End

The edges are named as shown below:


+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
by Active (2.4k points)
+2 votes

Part A.


$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



by Boss (23.8k points)

This is the best explanation.
–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



For the second question it will be S1---S2---S3---S4---S5  OR S1---S3----S2----S4----S5
by Active (1k points)
I have doubt..

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

So, cant we just use round robin with time quantum = 1. This way each process will use the cpu for the first time after (0,1,2,3) secs respectivly..! Making the average response time = (0+1+2+3) / 4.
@Harsh181996 I do think the same. Because minimum average time is always obtained by Round Robin and it is nowhere mentioned in question that the algorithm is non-preemptive.

Above answers are valid only when algorithm is supposed to be non- preemptive


what will be the value of x by this ?

Whatever be the value of x, the avg. response time will not change if we do RR scheduling with time quantum 1.

It is very valid question put up by Harsh181996 but I think if we had used the round robin algo then there wouldn't have been any interest in finding the order of execution of the processes as any order will give the same average RT. So the purpose of the question might get lost. 

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,280 answers
104,840 users