Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

0
votes
0answers
12 views

Serial allocation/ dictatorship for envy free up to 1 item

If we have a resource allocation setting where there are $n$ agents and $m$ items, how can we use serial dictatorship to find an allocation that is envy free up to 1 item with time complexity O(mn)
0
votes
0answers
14 views

algorithm to static allocation of previously known size and order

I need to allocate and free sizes of memory statically (not in run-time). The different between this and the dynamic allocation problem is that I know exactly when everything is going to happen. e.g. ...
0
votes
0answers
19 views

Maximizing benefits of performed tasks by purchasing less reusable devices

Suppose to accomplish a task $t_i$ from a finite task set $T=\{t_1, \ldots, t_n\}$, we need a set of reusable devices $D(t_i) = \{d_1, \ldots, d_m \}$ from a finite device set ${\cal D}$ such that 1) ...
-1
votes
1answer
51 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 ...
0
votes
1answer
22 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
0answers
11 views

metrics of utilization and starvation

Given n homogeneous machines $R$ and m homogeneous jobs $Q$ and an allocation schedule $F$ that maps $R\rightarrow Q$ w.r.t. time, what are the different metrics for ...
0
votes
0answers
117 views

Is this resource-allocation graph safe?

Consider the system illustrated below with 6 processes and 4 resources each with a single instance. The graph below is not a wait-for graph. An edge P1 -> P2 means that the node (process) P2 is data ...
1
vote
1answer
41 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$ ...
1
vote
0answers
731 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
0answers
34 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
0answers
21 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 ...
0
votes
1answer
196 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
1answer
178 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
0answers
60 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
0answers
79 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
0answers
12 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
0answers
62 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 ...
10
votes
6answers
638 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, ...
6
votes
2answers
6k 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 ...
1
vote
1answer
114 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 ...
1
vote
2answers
1k 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
1answer
202 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, ...
-3
votes
1answer
39 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 ...
1
vote
4answers
6k 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 ...