Questions tagged [resource-allocation]
The resource-allocation tag has no usage guidance.
31
questions
1
vote
1
answer
62
views
Heterogenous Resource Allocation Using Dynamic Programming
I'm working on a resource allocation problem, where there are $n$ different Items and $m$ different tasks ($n\geq m$). Also, The profit of assigning subset $I=\,(\, |I|\leq n)$ of items to task $j$ is ...
0
votes
1
answer
330
views
Resource Allocation Graph: Two processes want the same resource
In the example below, is this guaranteed to be safe? I see two processes that require the same resource. It's not a direct cycle but it seems to be a possible deadlock where P0 could get held up.
0
votes
0
answers
37
views
State of the art in register allocation for straight-line programs
TL;DR: I'm looking for the fastest known algorithm to perform optimal register allocation (optimal in the sense of minimizing the number of spills and reloads) for straight-line programs.
Context
I am ...
0
votes
0
answers
83
views
Why is the solution to Cinema Seat Allocation considered greedy?
LeetCode problem 1386. Cinema Seat Allocation requires finding the number of 4-person seating groups available (subject to certain constraints) after individual seat reservations have been made. The ...
1
vote
0
answers
45
views
Time based target allocation algo
I have following inputs:
$X$, where each $x_j$ is float and $1 \le j \le n$
$Y$, where each $y_j$ is int and $1 \le j \le n$
$a$ is a float scalar
I want to allocate/split $a$ in $n$ parts towards ...
2
votes
0
answers
52
views
Optimal allocation of heterogeneous divisible goods
In the context of my PhD on the simulation of the labor market with a multi-agent model, I encoutered a problem that doesn't seem to be really treated in the litterature, according to my searches on ...
2
votes
2
answers
106
views
Reasoning about resources: "resource logics"?
Are there extensions of predicate logic which focus on resource models, possibly even in actor models?
And if so, would it be possible to reason on a meta-level on how many resources should be ...
6
votes
2
answers
22k
views
Minimum number of processes for the deadlock?
A system has 6 identical resources and $N$ processes competing for
them. Each process can request at most two requests. Which one of the
following values of $N$ could lead to a deadlock?
1
2
3
4
My ...
1
vote
2
answers
633
views
Best approach to resource allocation problem
Problem
The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...
0
votes
0
answers
57
views
memory management - interview question
I was asked the following question in an interview and I don't understand what is the best solution for it -
Assume you have an application that needs memory. It asks for a program for this memory, 20 ...
0
votes
0
answers
32
views
Deadlock still occurs
Is it in in a deadlocked state?
In this graph, there is a deadlock initially I think. Since P1 is holding R1 and waiting for R2; P2 is holding R2 and waiting for R1 and R3; P3 is holding R3 and ...
2
votes
0
answers
2k
views
Resource Allocation Graph Algorithm
In the book Operating System Concepts, it is said that:
A claim edge $P_i \rightarrow R_j$ indicates that process $P_i$
may request resource $R_j$ at some time in the future.
[emphasis added]
...
2
votes
5
answers
14k
views
Deadlock and cycle in a resource allocation graph
Here is a resource allocation graph asked in my Operating Systems Theory midterm. The question is, "Is there a deadlock here? Explain your answer in detail"
Ra and Rb are resource sets and every dot ...
0
votes
0
answers
29
views
algorithm for scheduling tasks based on constraints and feedback loop if possible
I have a list of recurring tasks (1k+ tasks) and I am trying to find a optimal scheduling given a shared constrained resource.
In other respects the tasks are independent of each other
Each task is ...
16
votes
6
answers
2k
views
Why does garbage collection extend only to memory and not other resource types?
It seems like people got tired of manual memory management, so they invented garbage collection, and life was reasonably good. But what about every other resource types? File descriptors, sockets, ...
1
vote
0
answers
73
views
Modelling a queue to a resource pool (children queueing for balls)
I want to develop an algorithm to serve the queue of children queueing to a basket full of balls of different colour, where each ball can be painted within a known time any colour (of several colours ...
1
vote
1
answer
149
views
Problem class of assigning N persons to N tasks, zero costs with prefs
I am looking for the general problem class / computational complexity / algorithms for the following problem:
N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice ...
0
votes
0
answers
116
views
Resource allocation / optimization
At work I stumbled across this problem of allocating resources:
We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish ...
-1
votes
1
answer
259
views
I have a question about resource alocation to avoid dead lock
In the code below, three processes are competing for six resources labeled A to F.How can I modify the get request in each procedure in this graph to avoid dead lock You cannot move requests ...
2
votes
1
answer
81
views
Portfolio allocation with a few twists
A similar question has been asked here, but this one is more complicated and has more constraints.
I'm trying to find an algorithm to solve the following (real-life) problem:
A customer has $M$ ...
2
votes
0
answers
42
views
Static management of dynamic memory
I have some issue but I can't identify a way to solve it. I wanted to ask you what kind of problem it is?
We have a resource - contiguous computer memory. Also we have users which require some ...
0
votes
1
answer
1k
views
NP-hardness of resource allocation problem
I am tring to prove the NP-completeness of the following Binary Integer Linear Program (BILP):
$$ \text{min}\sum_i\sum_j x_{ij}\\
\text{subject to} \sum_jr_{ij}x_{ij} \geq R,\ \ \forall \ \ i \in [L]...
4
votes
1
answer
190
views
Distributing resources for maximum gain
This feels like it would be a well researched (or solved) problem, but I can't find the right words to search for it.
Suppose there is a collection of shared resources, and a collection of possible ...
1
vote
0
answers
107
views
Bin Packing across multiple iterations
I am working with an iterative application in a distributed setup. The application has n processes (P1, P2,...Pn) and m iterations. Each process may or may not perform any computation in a given ...
1
vote
0
answers
139
views
End-to-end bandwidth allocation to n pairs of nodes
Suppose there is a weighted graph representing a network with available bandwidth. I want to allocate end-to-end bandwidth between a set of pairs of nodes to transfer data. I want to find a path and ...
0
votes
0
answers
15
views
Relationship between flow and resource consumption in VNFs (Middleboxes)
A middlebox consumes some resources (CPU ticks, RAM, etc.) to process a traffic, e.g., a IDS consume 50% CPU and 20% RAM to process a 100M bps flow.
Here is the problem. 100M bps flow may consume ...
0
votes
0
answers
76
views
Yarn Resource Allocation
Say for an example,i have Color codes that are : A , B , C I want to repeat this colors so i ll put them as : 5A , 10B , 10C = 25 So now A will repeat 5 times ,B will repeat 10 times and C will repeat ...
1
vote
2
answers
3k
views
Help interpreting this deadlock question
I have this assignment question but I am a bit unsure how to go about answering it. The question is as follows and accompanied by the image below:
Three processes are competing for six resources ...
1
vote
1
answer
1k
views
How to determine how many dots are in a resource in a resource allocation graph?
I understand most concepts regard a resource allocation graph but I see that some resources have more dots (not sure what they are actually referred to) in them than others such as the example below, ...
1
vote
1
answer
507
views
How to determine number of instances for resources in a resource allocation graph? [duplicate]
I am struggling to determine the number of instances a resource will have. I have performed extensive research on this, but unfortunately have come up short. I am tasked with drawing a resource ...
-3
votes
1
answer
82
views
Determining execution times of a concurrent system with exclusive resources
A certain system consists of 2 CPUs. The CPU that is not being used is assigned to a task whose execution is requested. On this system, two tasks, A and B, are executed.These tasks both use a common ...