Assign resources to processes for k processes will be active

Assignment Help Software Engineering

Reference no: EM1370340

Suppose you are managing a system in which asynchronous processes make use of shared resources. Thus, the system has a set of n processes and a set of m resources. At any given point in time, each process specifies a set of resources that it requests to use. Each resource might be requested by many processes at once; but it can only be used by a single process at a time. Your job is to allocate resources to processes that request them. If a process is allocated all the resources it requests, then it is active; otherwise it is blocked. You want to perform the allocation so that as many processes as possible are active. Thus, we phrase the Resource Reservation problem as follows: given a set of process and resources, the set of requested resources for each process, and a number k, is it possible to allocate resources to processes so that at least k processes will be active? Consider the following list of problems, and for each problem either give a polynomial time algorithm or prove that the problem is NP-complete.

(a) The general Resource Reservation problem defined above.
(b) The special case of the problem when k=2.
(c) The special case of the problem when there are two types of resources, say rooms and equipments, each process requires at most one resource of each type.
(d) The special case of the problem when each resource is requested by at most two processes.

Reference no: EM1370340

Questions Cloud

Explain what is the relevant cost of each recharger : Explain What is the relevant cost of each recharger if they make it themselves and What is the relevant cost of each recharger if they outsource?

Analyze use of databases in business environment : Create the 2-3 page memorandum analyzing use of databases in the business environment. Include what database applications must be used: Microsoft Access, IBM DB2, Oracle, etc.

Explain what are the total relevant costs of accepting : Explain What are the total relevant costs of accepting the special order and From a quantitative basis, should they accept the special order and By what amount will the rink's net income increase or decrease if they accept the special order?

Basic assumption about the velocity of money transforms : Determine the basic assumption about the velocity of money transforms the equation of exchange into the quantity theory of money?

Assign resources to processes for k processes will be active : Given a set of process and resources, set of requested resources for each process, and number k, is it possible to assign resources to processes so that at least k processes will be active?

Question about gdp : The question used this table that demonstrate the value of GDP in the nation of Purintania. The figures demonstrate are in millions of 1980 dollars and current dollars.

Explain what is your leadership perspective towards : Explain what is your leadership perspective towards this trend as a means to achieve a sustainable competitive advantage?

Cost-output relationships : For each of following cost-output relationships, explain the shape (U-shape, decreasing, increasing, constant) of the average total cost and marginal cost functions

What are the various manufacturing processes : What are the various manufacturing processes and which manufacturing process is most appropriate for a real estate organization and why?

User Account

All Pages