2
$\begingroup$

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 contiguous piece of memory during a period of deterministic time.

In example,
User1 uses 2 bytes from 3rd to 5th iterations (inclusive)
User2 uses 1 bytes from 1st to 4th iterations (inclusive)
User3 uses 3 bytes from 5th to 8th iterations (inclusive)

It's easier for me represent it as table where users by rows, iterations by columns and values - quantity of required memory block.

      | 1 2 3 4 5 6 7 8
------+----------------
User1 | 0 0 2 2 2 0 0 0
User2 | 1 1 1 1 0 0 0 0
User3 | 0 0 0 0 3 3 3 3

The easiest solution - allocate enough memory for every user separately (6 bytes in this case). But I want to allocate some shared memory and distribute pointers so users use only unused memory.

One possible solution here is 5 bytes and (0, 2, 2) that means vector of pointers to memory blocks for every user.

So dynamic process will looks like:

iter 1 | x x 2 x x
iter 2 | x x 2 x x
iter 3 | 1 1 2 x x
iter 4 | 1 1 2 x x
iter 5 | 1 1 3 3 3
iter 6 | x x 3 3 3
iter 7 | x x 3 3 3
iter 8 | x x 3 3 3

(Here x - free bytes, values - byte's user identifier)

I've tried to solve this task with hypothesis that free memory block is also contiguous (in terms of task, we find iteration with the highest memory usage and add fake users that use the rest). Some cases can't proof this hypothesis.

$\endgroup$
  • $\begingroup$ What do you mean by "some cases can't proof this hypothesis"? $\endgroup$ – Yuval Filmus Aug 12 '17 at 9:42
  • $\begingroup$ I mean that sometimes it's impossible to keep unused memory is continuous. $\endgroup$ – Dmitry Kurtaev Aug 12 '17 at 9:52
  • $\begingroup$ @harold, Sounds like a nice observation. Want to write an answer with a bit of explanation? $\endgroup$ – D.W. Aug 12 '17 at 17:39
  • $\begingroup$ I think I can try to find some solutions in 2D packing algorithms. We minimize total memory usage and pack rectangular objects with single degree of freedom: they are fixed in time but not in space axis. $\endgroup$ – Dmitry Kurtaev Aug 12 '17 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.