We’re rewarding the question askers & reputations are being recalculated! Read more.
10

I agree that no deadlock is possible here. If there are three or fewer processes, there clearly cannot be a deadlock because there are enough resources for every process to just hold two resources the whole time. So any deadlock must have at least four participating processes. To participate in a deadlock, a process must hold at least one resource. Further,...


5

This is a knapsack problem. In the most basic version, you have a single resource (e.g., space in your knapsack) and you're trying to choose which items to put in it so you can carry the greatest value. People have also studied multi-constraint knapsack problems, which is the variant you're directly asking about. The bad news is that knapsack problems are, ...


4

GC deals with a predictable and reserved resource. The VM has total control over it and has total control over what is created and when. The key words here are "reserved" and "total control". On the other hand, handles and are resources allocated by the OS, and pointers are... well pointers to resources allocated outside the managed space. Because of that, ...


3

There are many programming techniques to help manage these kinds of resources. C++ programmers often use a pattern called Resource Acquisition is Initialization, or RAII for short. This pattern ensures that when an object that holds onto resources goes out of scope, it will close the resources it was holding on to. This is helpful when the object's ...


3

This appears to be one of the reasons languages with garbage collectors implements finalizers. Finalizers are intended to allow a programmer to clean up an object's resources during garbage collection. The big problem with finalizers is that they aren't guaranteed to run. There's a pretty good write-up on using finalizers here: Object finalization and ...


3

I did some thinking and then searching and all RAG conditions of this example leads to conclusion that there is no deadlock (altho there is a cycle here). Beside after searching I found this where you can find this: Which clearly stands Graph With A Cycle But No Deadlock Are you sure that you have your graph correct here?


2

The dots represent the number of clients a resource can serve simultaneously. So, in the example in the question, resources $R_1$ and $R_3$ can only serve one client at a time, $R_2$ can serve two and $R_4$ can serve up to three clients at the same time.


2

If you set $N = 2$, and $r_{i0} = r_{i1} = r_i$ for each $i$, and set $R = \frac12 \sum_{i \in [L]} r_i$, then the feasibility of this linear program is precisely the Partition problem. Namely, a feasible solution chooses for each $i \in [L]$ either $x_{i0}$ or $x_{i1}$, so that summing the $r_i$ for those $i$ for which you chose $x_{i0}$ equals $R$, and ...


2

All memory is equal, if I ask for 1K, I don’t care where in the address space the 1K comes from. When I ask for a file handle, I want a handle to the file I wish to open. Having a file handle open on a file, often blocks access to the file by other processes, or machine. Therefore file handles must be closed as soon as they are not needed, otherwise they ...


1

This problem is known as maximum matching of a bipartite graph. Basically let vertex $p_i$ (resp., $q_i$) represent the $i$th person (resp., task). And we connect $p_i$ and $q_j$ with an undirected edge iff person $i$ can do task $j$. The answer of the original problem is exactly the maximum matching of the new graph. For algorithms, the classical Hungarian ...


1

Do you mean a resource-aware logic? If so, yes, there's linear logic [Girard, 1987] (as was already noted in the comments). It has had a big influence on the study of concurrency and implicit computational complexity. You might be interested in the latter, where reasoning is focused on the efficiency of programs. What do you mean exactly by "actor models"? ...


1

I'd suggest using integer linear programming (ILP). You need to buy an integer number of stocks, so you can use integer variables to represent the amount of each stock you buy. ILP can express constraints (requirements that must be true). The main limitation is that the objective function you are trying to minimize must be a linear function of the ...


1

I would think that even with 5 processes, deadlock isn't possible. If 5 processes each need up to 2 of six identical resources, we could assume that each acquires one resources, and then we have 5 processes with a single resource left. Sure, four processes may have to wait when one process acquired the last resource, but eventually that process will free a ...


1

Introduction Consider a Petri Net model of the three processes. Assume the following: Every resource (A, B, C, D, E, F) has one unit only. All three processes run on a single processor. The processor can execute one and only one process at a time. This means that if a process is executing its Get() or Release() function or critical region, no other process ...


1

Here is one bad scenario: P0 obtains A and B. P1 obtains D and E. P2 obtains C and F. At this point, we have reached deadlock, since P0 is waiting for P2 to release C, P1 is waiting for P0 to release B, and P2 is waiting P1 to release D.


Only top voted, non community-wiki answers of a minimum length are eligible