Another Theory Question

Posted on 2004-11-11
Last Modified: 2010-04-17
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?

Question by:microcoop
    1 Comment
    LVL 7

    Accepted Solution

    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.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Threat Intelligence Starter Resources

    Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

    Suggested Solutions

    This article is filled with multiple code samples and explanations for mathematical calculations. They are as follows: 1. General tips 2. Quadratic formula 3. Object collision 4. Projectile path General Tips       Here are some of my tips f…
    Here we come across an interesting topic of coding guidelines while designing automation test scripts. The scope of this article will not be limited to QTP but to an overall extent of using VB Scripting for automation projects. Introduction Now…
    Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
    In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

    794 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    16 Experts available now in Live!

    Get 1:1 Help Now