retagged by
6,801 views
12 votes
12 votes

Below is the precedence graph for a set of tasks to be executed on a parallel processing system $S$.

What is the efficiency of this precedence graph on $S$ if each of the tasks $T_1, \dots, T_8$ takes the same time and the system $S$ has five processors?

  1. $25\%$
  2. $40\%$
  3. $50\%$
  4. $90\%$
retagged by

6 Answers

Best answer
17 votes
17 votes

Maximum number of tasks that could have been executed in four unit time using five processors = 4*5 =20

Number of tasks executed = 1+1+3+3=8

Efficiency = 8/20 =40%

Answer is B: 40%

selected by
13 votes
13 votes
System has 5 processors. Time to complete each process i.e. Ti is same.

Reasoning :
T1 executes on Processor 1. other 4 processors are idle.
T2 executes on Processor 1, other 4 Processors are idle.
T3, T4, T5 can run parallely on different different processors. Now 3 processors are working and 2 are still unused.
T6, T7, T8 can run parallely on different different processors. now 3 processors are working and 2 are still idle.

Total 5*4 =40 instance of processors. 8 out of 20 are working.
Efficiency = (8/20)*100 = 40%
2 votes
2 votes

Answer is C  = 50%

As per the below question paper and key:

http://www.eduers.com/gre/CompSci.pdf

1 votes
1 votes
Here Number of tasks =8

Number of processors =5

Efficiency is ratio of speed up and number of processors

Speed up is number of task executed in single processor system

Efficiency =((8/4)/5)⨉100=40%
Answer:

Related questions

6 votes
6 votes
1 answer
1
go_editor asked Jun 24, 2016
5,543 views
In a system using single processor, a new process arrives at the rate of six processes per minute and each such process requires seven seconds of service time. What is th...
7 votes
7 votes
4 answers
4
go_editor asked Jun 22, 2016
6,388 views
Consider a 32-bit machine where four-level paging scheme is used. If the hit ratio to TLB is 98%, and it takes 20 nanosecond to search the TLB and 100 nanoseconds to acce...