Identifying parallelism, Operating System

Assignment Help:

Identifying parallelism

A formal way to identify parallelism in an activity is to draw a task dependence graph in a directed graph in which each vertex represents a task to be completed. An edge from vertex u to vertex means that task u must be completed before task v begins, so that task v "depends on" u. If there is no path from u to v, then the tasks are independent and may be performed concurrently. Consider the following problem: Alice is the leader of a crew of workers who maintain a large estate. There are four principal tasks: mowing the lawns, pruning the trees and hedges, repairing the fences, and inspecting the work to ensure it has all been done satisfactorily. Mowing must be completed before the work is inspected, as must the pruning and fence repair. The estate has a security system which must be switched off before work commences (i.e. before Alice and her team arrives), and switched on again after the team leaves.

  • Draw the dependence graph corresponding to the above problem, showing all the tasks involved. (In a project management plan, this scheme is often referred to as a "work breakdown structure").
  • Alice has 8 people in her crew, including herself. (The crew members are: Alice, Bert, Cressida, Dominic, Edgar, Frank, Gus and Harriet). Alice will be solely responsible for inspecting the work, but decides that she herself and three other people (Bert, Dominic and Gus) will mow the estate's four lawns (referred to as north, south, west and east lawns, each of which are of equal area), two other people (Cressida and Frank) will prune the trees, whilst Edgar and Harriet will repair the fences. Redraw the graph to show the allocation of the crew to particular tasks. (Hint: a single task in the original graph may be come multiple tasks in the revised version, each of which is performed by a particular person).
  • Alice is a fast worker, and can mow any of the lawns in one hour, as can Dominic. Frank and Gus can complete any of the manual tasks in two hours. Bert, Cressida, Edgar and Harriet take three hours to do their work. If the manual work starts at 10:00 a.m. in the morning, at what time scan Alice inspect the work? In your answer, refer to the dependence graph showing the allocation of crew to tasks.

Since mowing is done first and then all team members start the work simuntaneosly and Alice can only inspect after each has finished their task the time taken by the slowest team members will be seen here.

Harriert/Bert/Credessia and Edgar take 3 hrs each to complete their task.

The manual work starts at 10.00 AM so the inspection will start 3+3 =6 hrs after that.


Related Discussions:- Identifying parallelism

What is independent process, What is independent process? A process is ...

What is independent process? A process is independent it cannot influence or be affected by the other processes implementing in the system. Any process does not share data with

Explain operating systems for mainframe computers, What are the main differ...

What are the main differences between operating systems for mainframe computers and personal computers? The design goals of operating systems for those machines are quite diffe

What are kernels and what do kernels do, What are kernels and what do kerne...

What are kernels and what do kernels do? The kernel is a program that comprises the central core of a computer operating   system. It has entire control over everything that

Unix, difference between soft link and hard links

difference between soft link and hard links

Real time operating system, PART A Question 1 Using your own words...

PART A Question 1 Using your own words, explain what a continuous random variable and a continuous probability density function are. Give examples. Question 2 Gi

Naming scheme for servers in an enterprise, Problem: Within a corporate...

Problem: Within a corporate environment, there are usually many servers located across various departments. Naming of servers is often a tedious task. In many circumstances, w

Explain demand paging in virtual memory system, Question 1 Explain with di...

Question 1 Explain with diagram all possible states a process visits during the course of its execution Question 2 Discuss Inter-process Communication. What is critical-secti

What are the benefits of multithreaded programming, What are the benefits o...

What are the benefits of multithreaded programming? The advantages of multithreaded programming can be broken down into four main categories: Responsiveness Resourc

Create a gantt chart for scheduling algorithms, Question: (a) The follo...

Question: (a) The following table (table 1.0) gives the length of the CPU burst time in milliseconds of processes P 1 to P 4 . Assume the processes arrived in the order P 1 ,

Explain gui based operating system, GUI - Short for Graphical User Interfa...

GUI - Short for Graphical User Interface a GUI Operating System contains icons and graphics and is commonly navigated by using a computer mouse. Below are some instances of GUI Op

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd