## Concurrency

 Question 1
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 T1, T2, T3,….T8 takes the same time and the system S has five processors?
 A 25% B 40% C 50% D 90%
Operating-Systems       Concurrency       ISRO CS 2011
Question 1 Explanation:
From the precedence graph, we say that the following tasks executed sequentially
I. T1 ,T2
II. T3 and T6
III. T4 and T7
IV. T5 and T8
(T3,T6),(T4,T7) and (T5,T8) will execute parallely.
So total number of processes that can be executed in 4 units time using 5 available processors = 5*4 = 20
Maximum number of tasks are 8
Efficiency = 8/20 * 100 = 40%
 Question 2
A particular parallel program computation requires 100 seconds when executed on a single CPU. If 20% of this computation is strictly sequential, then theoretically the best possible elapsed times for this program running on 2 CPUs and 4 CPUs respectively are
 A 55 and 45 seconds B 80 and 20 seconds C 75 and 25 seconds D 60 and 40 seconds
Operating-Systems       Concurrency       ISRO CS 2013
Question 2 Explanation:
→From the given data, one CPU will require 100 seconds to complete given task.
→20% of computation is done by sequential which means 20% of 100 seconds (20 seconds)
→Remaining computation 80% of work(80 seconds) can be done by the parallel processing.
→2 Processors: 20 % of sequential work is done by processor p1 (20 sec) and remaining 80 % of work (80 seconds) can be distributed among p1 and p2 equally(each process will get 40 sec). so time required = 20 + 40 = 60 seconds
→4 Processors: 20 % of work is done by any of the processor sequentially(20 seconds) and remaining 80 % of work (80 seconds) can be divided among 4 processors(each process will get 20 sec), so maximum time required = 20 + 20 = 40 seconds
There are 2 questions to complete.