Another Theory Question

I'm asking this on the C++ board because I really think it's the best place, although it isn't coding.
I am studying for a test, but one concept eludes me.

If I have a real memory unit of 1024 locations

Then requests come in of process of these sizes
90, 120, 80, 130, 70

Then the 2nd and 5th process finishes

I then have this table of additional requests for memory. Each answer is suppose to depend on the other answers

 Request   Best Fit    Worst Fit    First Fit
a      65        420         490            90
b      45        90           555           155
c      70        135         600            420
d     15        490         670             490
e     25        505         685            505

I am supposed to know how to give the starting location or the memory allocated to each process. Each answer depends of the previous answers. Can anyone jst help me get started understanding this?

microcoopAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

HoweverCommaCommented:
Hmmm... It took me a few minutes to get a grasp on what you were wanting... I think I understand.

Based on your presentation I believe your Byte count is zero based as the best fit for a is 90 (vs 91) where the second process is cleared and the first process was allocated 90.

Create 2 dimensional arrays as such

Dim MemAllocated(x,2)      where x is of course the Max number of open processes
Dim MemDeAllocated(x,2)

MemAllocated(x,0) will hold the number of bytes allocated
MemAllocated(x,1) will hold the start byte

MemAllocated(0,0)=90     MemAllocated(0,1)=0
MemAllocated(1,0)=120   MemAllocated(1,1)=90
MemAllocated(2,0)=80     MemAllocated(2,1)=210
MemAllocated(3,0)=130     MemAllocated(3,1)=290
MemAllocated(4,0)=70    MemAllocated(4,1)=420


 
If you want to calculate the WORST fit simply add up the running total of bytes allocated.
This would mean you did not ever deallocate anything 'fragmenting' your current used memory pool.

Now the 2nd and 5th process finish & you need 65 bytes and in this process you are trying to create contiguous storage as best you can (you didn't mention that but it is obvious).

Now bytes 90-210 (120) are available.
and 420-1023  is now avail as process 5 finished too.

And set these to
MemAllocated(1,0)=0   MemAllocated(1,1)=0
MemAllocated(4,0)=0    MemAllocated(4,1)=0


To find the FIRST fit check your Deallocated array for the first position it will fit in, use that and update the deallocated pools start byte and total available if it did not use all of it.
Then repeat the process for each request in order. Since 60 and 45 eat up 110 of 120 then 70 will not fit then its first position is 420

MemDeAllocated (0,0)=120 MemDeAllocated (0,1)=90
updated after allocating 65 for first fit
MemDeAllocated (0,0)=55 MemDeAllocated (0,1)=155
and then 45
MemDeAllocated (0,0)=10 MemDeAllocated (0,1)=200

Do not put the 70 from process 5 in the deallocated pool since nothing after that has been used 420 and up are available and the first fit will be pulled from the last byte allocated in the MemAllocated array.
by finding the maximum MemAllocated(x,1) value (here it is 290) and adding the corresponding MemAllocated(x,0) value
This is your first fit, if there are no fits in the deallocated pool.


Now the data you supplied with the answers causes me some confusion. What is best fit here? I would THINK that it would be keeping thing contiguous. By your data this is not the case unless some set of rules that you have not stated.
They really make no sense unless you are ALWAYS going to know in advance the next sequence of requests and then you are trying to use the smallest amount of space in the 1024 at all times (fragmenting or not).
If this is the case a more advanced algorithm that I will leave up to you, I have done enough I think for you to grasp what is going on here.
But what you will want to do (and this is ASSUMING) you know the next 5 requests before having to allocate any.
iterate through A+B, A+B+C until one is over the number of bytes in the deallocated pool and see how many bytes were left over with the highest valid combination. Then go with B+C, B+C+D then C+D, C+D+E and then D+E the one that fills the space most which is what was done here will use that position. I hope you understand what I am saying here I am having a hard time putting it to words.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.